當前位置: 華文星空 > 體育

數學問題:棋盤上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 氣。