Re: [中學] 組合數學, 棋盤擺數字, 相鄰數間隔最大值
※ 引述《t0444564 (艾利歐)》之銘言：
: 在n*n棋盤C中，兩個具有公共邊的格子就稱為相鄰的。將1,2,3...,nn分別填入各格中
: ，每格填一數。若兩格相鄰的數至多差g, 則稱g為一個C-間隙，求出最小的C-間隙~
: 答案是n，題目給的提示是
: 「若任兩相鄰的方格中的數字差都<=n-1，則可以找到一行與一列形成的十字滿足
: 其中任一格中的數字要不>=k+n要不<=k(其中k為任一個<=n^2-n的正整數)」
: 這個提示我也看不出來orz, 以及這個提示如何應用在這個題目中我也不會OAO...
假設任相鄰兩格差≦n-1
則 1~n(n-1)/2 與 n(n+1)/2~n^2 必被 n(n-1)/2+1~n(n-1)/2+n-1 這 n-1 格分成
不相鄰的兩個區域
但 n-1 格所隔開的次大區域頂多1+2+..+(n-2)<n(n-1)/2格,矛盾
1 2 ... n
n+1 n+2 ... 2n
... ... ...
(n-1)n+1 (n-1)n+2 ... n^2 是一種C-間隙為n的排法
故最小的C-間隙為n
---------------------------------------------------------------------------
提示的證明:
假設任相鄰兩格差≦n-1
則對任意 1≦k≦n^2
1~k 與 k+n~n^2 必定被 k+1~k+n-1 這 n-1 格分成不相鄰的兩個區域
=> 必有某行與某列不含 k+1~k+n-1 => 此行與此列落在同一區域
=> 此行與此列所成之十字的任一格都≦k或都≧k+n
: PS: 類似但是簡單很多的題目是
: 在n*n棋盤C中，兩個具有公共頂點的格子就稱為相連的。將1,2,3...,nn分別填入各格中
: ，每格填一數。若兩格相鄰的數至多差g, 則稱g為一個C-間隙，求出最小的C-間隙~
: Ans: n+1
因從1到n^2至多只需n-1步,故C-間隙≧(n^2-1)/(n-1)=n+1
1 2 ... n
n+1 n+2 ... 2n
... ... ...
(n-1)n+1 (n-1)n+2 ... n^2 是一種C-間隙為n+1的排法
故最小的C-間隙為n+1
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.24.64.106
※ 文章網址: http://www.ptt.cc/bbs/Math/M.1406465430.A.D12.html
推
07/27 21:58, , 1F
07/27 21:58, 1F
→
07/27 22:14, , 2F
07/27 22:14, 2F
→
07/27 22:24, , 3F
07/27 22:24, 3F
推
07/27 23:52, , 4F
07/27 23:52, 4F
→
07/27 23:53, , 5F
07/27 23:53, 5F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：