※ 引述《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://webptt.com/cn.aspx?n=bbs/puzzle/M.1493055876.A.538.html ※ 编辑: walkwall (114.40.181.221), 04/25/2017 01:53:30