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

[walkwall (會走路的牆)]

※ 引述《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://www.ptt.cc/bbs/puzzle/M.1493134140.A.9F2.html
→ walkwall: >_0
→ walkwall: 可能還有個小尾巴  但我想就先停筆於此吧 (睡覺去...)
推 arthurduh1: 第一列放 11XX1 就會往上凸 3 格?
→ arthurduh1: 而且 case 2 的重疊會吃掉 2 格, 但只會吃貢獻度 1 哦
→ arthurduh1: 其實我說的討論就只是暴力分情況, 不過十字跟邊界
→ arthurduh1: 還有可能相交 2 格, 之前沒注意到.
→ walkwall: 您說得沒錯  最後其實我也想過兩格重疊但貢獻度只減一
→ walkwall: 這就是我說的小尾巴...雖然感覺能再舉些例子說清楚
→ walkwall: 但是我想就交給其他人完成了XD (狡猾溜走)
→ walkwall: 如果單邊要3格  則disc必須重疊  因此也可列為證明的特
→ walkwall: 殊例子  不影響證明