如題…如果不是9x9，而要推到任意正整數(nxn)時最多可以剪多少張郵票???

原題可以看2011IMAS國中組複試的試題

目前已有…(f(n)為在nxn方格內剪下郵票張數之最大值)
f(1)=0，f(2)=0，f(3)=1，f(4)=2，f(5)=5，f(6)=7，
f(7)=11，f(8)=15，f(9)=21
另外，對於正整數k
f(2^k+1)=(2^(2k)-1)/3
國中
  • 發表回應前，請先登入

回應

justpoppingin

2012-08-12 06:45
引用：

hansonyu123 寫道:
f(n)為在nxn方格內剪下郵票張數之最大值
對於正整數k
f(2^k+1)=(2^(2k)-1)/3

是否可以給出奇數階正方形作法的證明?或許能幫助偶數階的計算

math31415926

2012-08-17 06:01
我覺得奇數階的正方形應該可以先畫出交錯排列的格子當作原始圖形，然後保留所有長邊，內部合併後再循原方式求解。故邊長為2^k＋1時才會有公式解。
而證明則是因為原始圖形已充分利用正方形的每條邊，且選擇的不會形成封閉正方形(交錯排列則無直立的，操作過程依次證明斜的)，故剩下的會連接。
請大家檢驗是否正確。若真如此，則我們還是要以偶數階為基礎？

hansonyu123

2012-09-04 06:23
引用：

justpoppingin 寫道:
引用：

hansonyu123 寫道:
f(n)為在nxn方格內剪下郵票張數之最大值
對於正整數k
f(2^k+1)=(2^(2k)-1)/3

是否可以給出奇數階正方形作法的證明?或許能幫助偶數階的計算

對不起那麼晚才來回文

下界求法同解答
(最小值的)上界求法是數歸
對於2^n+1來說
分成四區(四區會有重疊部分)：左上2^(n-1)+1，左下同，右上同，右下同
每區按照2^(n-1)+1的剪法剪，再剪去中心那個郵票就會得到結果

下界跟上界相同就夾出來了