当前位置: 华文星空 > 体育

数学问题:棋盘上n个黑色围棋子最少有几口气?

2024-04-27体育

随便写写,不一定对,有误请指出。

感觉考虑反向问题「给定的气数下最多能摆多少棋子」会更简单一些。

观察一些简单的结构:

?*? XXX

在这种结构中,无论 ? 的情况如何,只要 X 处全有子,那么,在 * 处也放子,气的数量不会增加。

X*? ?XX

同上。

所以答案的边界一定:

  • 只包含长度为 1,2 的边
  • 270° 角的两个边界长度都为 1
  • 所以答案一定形如:四个方向上最远的边的长度为 1 或 2,它们之间用 45° 折线连接。

    考虑按这四条边的长度对这种图案进行分类,依次为 1111 1122 1212 2222 分别称为 A B C D。

    除了 1122 情形外可以证明「对边」长度必然相等,且长宽之间对称。1122 情形规定两个 1 之间的折线段长度为宽 m ,12 之间的折线段长度为长 n 。长宽都是指由多少个 270° 拐弯构成。

    那么

    面积
    A(n,m) 2n+2m+4 2nm+n+m+1
    B(n,m) 2n+2m+5 2nm+n+2m+1
    C(n,m) 2n+2m+6 2nm+2n+2m+2
    D(n,m) 2n+2m+8 2nm+3n+3m+4

    2k 气时可以用 A 或 C 或 D 得到 \lfloor (k-2)^2/2\rfloor +k-1 或 \lfloor (k-3)^2/2\rfloor+2k-4 或 \lfloor (k-4)^2/2\rfloor+3k-8 个子。前者大于等于后两者。写出来就是 \lfloor(k^2-2k+2)/2\rfloor 。

    2k+1 气时可以用 B 得到 k(k-1)/2 个子。这比退化的前者要大。

    最终可以得到 t 气最多 \lfloor t^2/8-t/2+1\rfloor 子。

    反过来写就是 x 子最少 \lceil2+\sqrt{8x-4}\rceil 气。