# 2024 NYCU應用數學系博覽會──六貫棋
*Time: 2024.02.24*

---
## Ansers:

### 六貫棋沒有和局？
思考棋局以下兩種情形

1. 若兩名玩家彼此都成功創建了一條連接路徑，則棋盤基本上將被分成兩個不連接的半部分，則必存在一個蜂巢格存在兩種顏色，這是被禁止的。
2. 若兩名玩家皆未完成連結路徑，則比賽將繼續進行，直到其中一名玩家有連結路徑為止。

故六貫棋不存在和局。

那思考一下，為甚麼一個棋盤填了兩種顏色就一定存在勝利路徑呢？ :thinking_face:
.
.
.
*不能偷看證明喔
不能偷看證明喔
不能偷看證明喔
不能偷看證明喔
不能偷看證明喔
不能偷看證明喔
不能偷看證明喔
不能偷看證明喔
不能偷看證明喔
不能偷看證明喔
不能偷看證明喔
不能偷看證明喔
尼確定要看證明ㄇ:face_with_monocle:*
.
.
.
.
.
.
.
.
.

其實這叫做"Hex Theorem"，在證明這個理論前，先來看看一個圖(graph)的引理(lemma)：

> **Lemma 1.**
> A finite graph whose vertices have degree at most two is the union of disjorint subgraphs, each of which is either (i) an isolated node, (ii) a single cycle, (iii) a simple path.
>
> 一個有限的圖，其節點的度數至多為二，可以表示為若干不相交的子圖的聯合，每個子圖可能是以下三種情況之一：
(i) 孤立節點，即只有一個節點，沒有與其他節點相連的邊。
(ii) 簡單循環，即構成一個環狀結構，每個節點恰好有兩條邊與之相連。
(iii) 簡單路徑，即一條連接兩個不同節點的路徑，沒有形成循環。

那已知這個lemma，然後將兩種顏色以x, o來表示，我們劃出下面這張圖：

(橘色點標示$u_1, u_2, u_3, u_4$; 分別對應綠色短線$e_1, e_2, e_3, e_4$)

我們將遊戲棋盤表示為一個圖$G=(V,E)$，其中包含一組節點$V$與一組邊$E$。六邊形棋盤空間的每個頂點都是$V$中的一個節點，而六角形棋盤空間的每條邊都是$E$中的一條邊。隨後，我們分別將兩組對邊標上$O$、$O'$以及$X$、$X'$表示兩位對手的領地。

定義X-face為一個標記為x的蜂巢(hexagons)或是在$X, X'$區域上的蜂巢。O-face也是以此類推。然後我們額外定四個節點$u_1, u_2, u_3, u_4$以及分別連結他們至核心圖的邊$e_1, e_2, e_3, e_4$，那麼這四個邊也位於X-face與O-face之間。

定義完之後、我們來試著證明一下Hex theorem！ :wink::wink:

> **Hex Theorem**
> If every tile of the Hex board is marked either 'x' or 'o', then there is either an x-path connecting regions $X$ and $X'$ or an o-path connecting regions $O$ and $O'$
>
> 如果六角棋盤的每個方塊都標記為 x 或 o，那麼必然存在一個 x-路徑連接區域 $X$ 和 $X'$，或者存在一個 o-路徑連接區域 $O$ 和 $O'$。

> **< Proof>**
>
> First we construct a subgraph $G' = (V,E')$ of $G=(V,E)$, with the same nodes but a subset of the edges. We define an edge to belong in $E'$ only if it lies between a X-face and an O-face. Therefore, $e_1, e_2, e_3, e_4\in E'$. The nodes $u_1, u_2, u_3, u_4$ have degree one.
>
>首先我們先建立子圖 $G' = (V,E')\in G$。這裡我們定義 $E'$包含了所有在X-face與O-face之間的邊。所以，$e_1, e_2, e_3, e_4$ 也屬於 $E'$。
>
> If all three hexagons around a node are marked the same, then the node is isolated in $G'$ and has degree zero. If a node is surrounded by two hexagons of one pattern and one hexagon of the other pattern,then that node has two incident edges. Hence, each node in the coregraph has degree either zero or two.
>
> 考慮所有不包含$u_1, u_2, u_3, u_4$的節點(nodes $v\in V$, $v\neq u_1, u_2, u_3, u_4$)，如果在某個節點附近的三個蜂巢都標記了同樣的符號，則節點有度數0；如果在某個節點附近的其中一個蜂巢為一個符號，而另外兩個蜂巢標記了另外一種符號，則該節點有度數2。所以，在核心圖裡面的所有節點度數不是0就是2。
>
> *(喝一口水吧 :tea: )*
>
> Since $G'$ has nodes with degree at most two, by the lemma 1, $G'$ is a union of disjoint subgraphs, each of which are isolated nodes, simple cycles, or simple paths. Each of the nodes $u_1,u_2,u_3,u_4$ are ends of some path because they have degree one. The disjointness of sub-graphs in $G'$ ensures that these paths do not cycle. Therefore, there exist two simple paths in $G'$, each connecting two of $u_1, u_2, u_3, u_4$.
>
> 因為 $G'$的所有節點度數最多是2，利用lemma 1我們知道 $G'$圖是多個不相交的(disjoint)子圖的聯集(union)，每個不相交子圖可能是孤立的節點(isolated node)，或是簡單循環(simple cycle)，抑或是簡單路徑(simple path)。再者，節點$u_1,u_2,u_3,u_4$的度數皆為1，因此他們會是某條路徑的結尾(end)。$G'$中那些子圖的不相交特性保證了這些路徑決不會循環。因此，$G'$中存在兩個簡單路徑連接$u_1,u_2,u_3,u_4$中的兩個節點。
>
> *(不要忘記呼吸 :face_with_monocle:)*
>
> Although the winner depends on the orientation of the paths, the paths do trace out a winning chain of hexagons. Therefore, for any arbitrary configuration of the Hex board, a winning path for one of the players exists.
>
> 雖然獲勝者的決定是取決於整個路徑的走向，但這些路徑確實勾勒出了一條贏棋的六邊形鏈。因此，對於六角棋盤的任何任意配置，都存在一條可以讓其中一位玩家獲勝的路徑。
>
> For example, in the figure below, the darkened edges and vertices belong to $G'$. There are two simple paths, one connecting $u_1$ and $u_4$, and another connecting $u_2$ and $u_3$. The paths mark out a winning chain for the O-player.
>
> 例如在圖中，粗黑色的邊和節點屬於圖$G'$，有兩條簡單的路徑，一條連接$u_1, u_4$，另一條則連接$u_2, u_3$。這些路徑標示出o選手的勝利路徑。
>
> $\diamond$

這邊的證明主要是參考Reference中第一篇。而往後延伸還能延伸到n維的情況，會利用Brouwer Fixed-Point Theorem等理論去解決n維棋局對應的的方程系統等等。這些內容都可以在以下的參考連結中找到喔~

總之謝謝蒞臨，希望你有所收穫 :blush::blush:

## References:
1. [MIT, *"HEX"* , SP.268, Spring 2011. ](https://web.mit.edu/sp.268/www/hex-notes.pdf)
2. [Hex Wiki- Draw](https://www.hexwiki.net/index.php/Draw)
3. [David Gale, *"The Game of Hex and the Brouwer Fixed-Point Theorem"*, The American Mathematical Monthly, vol. 86, 1979, pp. 818-827, Sep 24, 2008](https://maa.org/programs/maa-awards/writing-awards/the-game-of-hex-and-the-brouwer-fixed-point-theorem?fbclid=IwAR1GJZVgTIE-qZ4M_coa5Pv5AbV3p8FqLhiV4bmab30QldlJcln3ntqCUpE)