※ 引述《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/cn.aspx?n=bbs/puzzle/M.1493134140.A.9F2.html