2018年4月28日 星期六

訓練數學感 172 ─ 鋪地磚至少需要幾塊 1x1?

http://4rdp.blogspot.tw/2018/04/172-1x1.html

「舖地磚」的圖片搜尋結果

有個房間地面 23 x 23 單位面積,利用 1x1、2x2、3x3 的正方形磁磚鋪滿,請問 1x1 磁磚最少要用幾塊?



這題目來自小朋友學校的資優挑戰題,看似簡單,應有高二程度。

6 則留言:

  1. 依直覺來排的話,大概就是先把3x3填滿,留下L狀的空間填2x2,這樣1x1最少可以只剩四塊。
    不過感覺還可以更少,不禁令人起疑。

    回覆刪除
    回覆
    1. 地磚排列方式不只一種,目前我排出來也是剩四個 1x1。最佳解就是把它轉化成一個 2x2替代,就可以不用 1x1,不過這可能嗎?

      刪除
    2. 我提一個剩1塊的思路。
      https://lh6.ggpht.com/-hqHG5k-8Xp8/UVE3WEHo9VI/AAAAAAAAG2A/J5iMWnXrB2I/s400/14_2_39.png
      類似第三圖
      用四個同樣的矩形先組成正方形的四個邊角,中間留下一塊正方形,務必令該正方形盡可能小。
      根據所給正方形面積,可計算每個矩形面積為
      (23*23-1)/4 = 132
      132 = 2*2*3*11
      令該正方形盡可能小時,長和寬需要盡可能接近
      用這4個數字組成的符合要求的長寬為11和12,僅差1
      用這樣的矩形組成正方形時,中間只差1塊1x1的小正方形。
      到這裡,還忽略了一個問題,我們能否用2x2和3x3組成11x12的矩形,
      用2x2和3x3組成的最小矩形是5x6,因爲6是23的最小公倍數,
      所以用3個2x2和2個3x3就可組成5x6這個矩形。到此整個矩形還剩下6x6的部分。
      我們用4個3x3填滿它就好了。
      至此,我們用了3個2x2和6個3x3組成了一個小矩形,這樣的矩形需要4個,
      所以共需要12個2x2和24個3x3,剩下的部分用1個1x1填滿就好。

      刪除
    3. 接下來不用1x1的方法就呼之欲出了。
      不用1x1,還要保證被23x23=529減去之後能整除4,
      那就剩下一塊3x3好了。
      每塊矩形面積為 (529-3x3)/4 = 130
      130 = 10x13
      哇!長和寬剛好差3!快要成功了!加油!

      刪除
    4. 但13或10並不能被6整除,所以只好作罷。
      要回家了,突然發現上面計算有很多錯……雖然結果是對的……
      勘誤
      所以用3個2x2和2個3x3就可組成5x6這個矩形。到此半個矩形還剩下6x6的部分。
      我們用4個3x3填滿它就組成了半個矩形,乘以2就有了整個矩形,
      至此,我們用了6個2x2和12個3x3組成了一個小矩形,這樣的矩形需要4個,
      所以共需要24個2x2和48個3x3,剩下的部分用1個1x1填滿就好。

      刪除
    5. 謝謝老師提供一個 1x1 的解法,至於不用 1x1 的方法,這需要再思考,直覺應該不是四個等大小的 13x10 矩形圍在外邊。

      刪除