※ 引述《walkwall (會走路的牆)》之銘言： : ※ 引述《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 > 6個] 邊界共16格 每個 disc 最多蓋住3格 因此邊界至少需6個 disc 才能蓋滿 因為中央也必須被覆蓋 包含正中央的disc 邊界只能蓋住某一邊中點1點 (距離才夠) 其餘五個disc必須都覆蓋3格 但這樣的極限例子無法覆蓋肋旁雙點(如下圖) 故得證 "disc > 6" ２２１３３ ２１１１３ ４　１　５ ４４６５５ ４６６６５ [至少兩個重複] 要覆蓋至少需7個disc 每個disc面積5格 每個disc核心都在5*5範圍內 又要保持不重疊 則四邊最多個各只有2格出界 故disc覆蓋面積最多 5*5+2*4=33格 要放入7*5=35格 依據鴿籠原理(?) 至少有2格重疊 重疊1格就會減少1點貢獻度上限 故最大上限為65-2=63 --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.40.181.221 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/puzzle/M.1493134140.A.9F2.html