almost 3 years ago

0 緣起

基本上就是個為趕進度不擇手段的概念哈哈哈。

1 題目

基本上是這樣的,有個 大小的棋盤,其中某一個格子上面站了一隻史萊姆。請問你能不能用 3 個正方形拼成的 L形磚,把整個棋盤除了史萊姆以外不重疊地恰好鋪滿?如果能的話,該怎麼鋪呢?

2 解法

其實,我們只要用數學歸納法證明:無論史萊姆站在哪一格,上述鋪磚問題都可以達成。

如果盤面大小是 ,無論史萊姆站在哪一格,顯然剩下的形狀可以被一個 L形磚鋪滿。假設對於 大小的盤面上,任何一個站了一隻史萊姆的情況我們都可以用 L形磚鋪滿。現在考慮 ,我們把整個盤面分成四個 的子盤面,史萊姆會站在其中一個盤面上。我們在正中間放一片 L形磚,然後讓凹口朝向有史萊姆的那一個子盤面。

這時候我們就可以知道四個子盤面都恰好包含一個「被佔走的格子」,滿足歸納的條件。因此由歸納法可以證明出任何 的棋盤,只要被佔用一格,都仍可以被 L形磚鋪滿!

思考問題

  1. 如果史萊姆的大小是 ,在什麼樣的條件下我們可以保證 L形磚一定可以鋪滿盤面的其他地方?
  2. 證明存在一個 缺一角的 L形磚鋪法,至少要用四種顏色塗每一片磚,使得有邊相鄰的兩塊磚顏色都不相同。(即,這個鋪磚法無法三著色。)說不定有 的構造法?(三著布拉克)

3 擴展到三維

想像一下一個 的方塊去掉一小角的形狀 ,我們也可以用同樣方式證明:給定 空間中,某個格子已經擺了一隻史萊姆,可以用 把剩下的空間恰好鋪滿。

4 後記

拓展到三維這個想法第一次是在劉邦鋒教授所開授的「進階程式設計 ACP2009」期中考遇到的,當時覺得相當新奇。這題的程式碼其實沒有想像中好寫,尤其是要判斷八個部分分別遞迴下去的時候,不寫成迴圈真的不行哈哈。

5 奇怪的後記

螢幕快照 2016-02-26 下午4.56.23.png

要怎麼用 產生出以上的圖片呢~請參考下面的程式碼 :P

\begin{figure}[h]
\centering
\begin{subfigure}[c]{0.4\textwidth}
\begin{center}
\begin{tikzpicture}[scale=0.6]
\draw[black] (0,0) grid (8,8);
\fill[color=black] (6,2) rectangle (7,3);
\end{tikzpicture}
\end{center}
\end{subfigure}\ \ \ \
\begin{subfigure}[c]{0.4\textwidth}
\begin{center}
\begin{tikzpicture}[scale=0.6]
\foreach \i in {1, ..., 20} {
  \pgfmathsetmacro{\Xa}{random(180)};
  \pgfmathsetmacro{\Ya}{random(7)};
  \pgfmathsetmacro{\Za}{random(7)};
  \pgfmathparse{0.9*rnd+0.3};
  \def\cr{\pgfmathresult};
  \pgfmathparse{0.9*rnd+0.3};
  \def\cg{\pgfmathresult};
  \pgfmathparse{0.9*rnd+0.3};
  \def\cb{\pgfmathresult};
  \definecolor{MyColor}{rgb}{\cr,\cg,\cb};
\draw[fill=MyColor, cm={cos(\Xa), -sin(\Xa), sin(\Xa), cos(\Xa), (\Ya,\Za)}] (0,0)--(0,2)--(1,2)--(1,1)--(2,1)--(2,0)--cycle;
}
\end{tikzpicture}
\end{center}
\end{subfigure}
\end{figure}
← 分而治之法(四之二):(min, +) 矩陣相乘問題 分而治之法(六):摺紙條問題 →
 
comments powered by Disqus