Re: [問題] 請問如何填出最大的數字

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者walkwall (會走路的牆)時間8年前 (2017/04/25 01:44)推噓1(1推 0噓 11→)

留言12則, 2人參與討論串2/3 (看更多)

※ 引述《bamboo1106 (bamboo)》之銘言： : 有一個 5 * 5 的方格，要在裡面填上 1 ~ 5 的數字 : 其中要滿足以下條件： : 1 可以放在任何格子 : 2 必須放在旁邊有 1 的格子 : 3 必須放在旁邊有 1、2 的格子 : 4 必須放在旁邊有 1、2、3 的格子 : 5 必須放在旁邊有 1、2、3、4 的格子 : 旁邊指的是該格的上下左右證明是有想出來一些但最後一部分符合直覺卻並不嚴謹想貼出來大家討論看看 --[63解]-- 32413 24312 在證明的過程中做出來的 11342 11243 本板先前"蓋房子"討論題將5換成4可得61解 35251 25351 24132 34123 13241 12341 --[證明 : 最大值 <= 65]-- 每個2以上的格子都需要有較小的格子在旁邊支持可以說大數字格的分數來自相鄰小數字格的"貢獻" 故定義每格的"貢獻值" = 該格數值 + 0.5*OUT - 0.5*IN 其中 OUT/IN 表示該格對鄰格輸出/輸入貢獻如果是1的點最多4OUT 貢獻度MAX = 1 + 0.5*4 = 3 5的點要有四個較小的點支持貢獻度 = 5 - 0.5*4 = 3 這樣角落 / 四邊 / 中央貢獻度上限分別為 2 / 2.5 / 3 因此總貢獻度上限 = 2*4 + 2.5*12 + 3*9 = 65 貢獻度輸出輸入來自真實標號轉換無法額外增加故得證原始上限也是65 --[證明 : 最大值 <= 63]-- 標示為1的點與其周圍十字狀4格非1點視為一個disc 若兩個disc有重疊重疊區域貢獻度就無法到達上限 CASE 1 : 兩個disc的非1點重疊因為周圍有兩個1 因此相鄰1處必須為IN (否則1的點貢獻度會變少) 剩下兩個邊要OUT 就只能標2 貢獻度就只能到 : 2 + 0.5*2 - 0.5*2 = 2 若要標3 則需3IN 貢獻度只能到 : 3 + 0.5*1 - 0.5*3 = 2 故這樣重疊該點貢獻度就會少1 CASE 2 : 兩個disk的1點相鄰因為相鄰導致兩者只有一邊能算OUT IN的一邊貢獻度也會少1 當然要兩邊都當作非IN非OUT 貢獻度少 0.5*2 也是少1 因此若能證明 "覆蓋5*5方格的disc disc重疊至少兩組" 則原題得證要將十字disc完全鋪滿平面又要盡量避免重疊大部分必須採騎士間隔的方式也就是下圖這樣的排列方式　　ａ　ａＡａｂ□　　　其中大寫為1點　小寫為同disc的非1點　ｃａｂＢｂｃＣｃｄｂ□ 然而要鋪滿5*5 我們會發現不論怎麼挪移　ｃｄＤｄ□ 　□□ｄ□□ 都會出現左圖中□的位置無法覆蓋 (旋轉平移後同圖) 其中最左下與最右上的兩個□ 不論以何種disc要包含他們一定會跟周圍disc有所重疊故最少兩個重疊因此上限至少少2 : 65-2=63 故得證 [結論] 綜合結果得證本題上限恰為63 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.40.181.221 ※ 文章網址: https://www.ptt.cc/bbs/puzzle/M.1493055876.A.538.html