2020-12-08 思考題 JLU_ACM 2020

比賽鏈接

題目并不是很難，但是由于我過于SB，對題面理解有誤，想了老半天都想不出來，看了題解還覺得不對，但是實際上題解很真理，總之我就一SB，

題目簡述

給出一個大小為 N × N N\times N N×N 的棋盤，以及棋盤的初始狀態，要求反轉不超過 ? k 3 ? \left\lfloor\frac{k}{3}\right\rfloor ?3k?? 個棋子（ k k k 為棋子的總個數），使得修改后的棋盤符合“非終止”定義，輸出一種符合要求的修改方案，如果有多種合法方案，任意輸出一種方案即可，

我們用 A i , j ( 1 ≤ i , j ≤ N ) A_{i,j}\space(1\leq i, j\leq N) Ai,j? (1≤i,j≤N) 表示中第 i i i 行、第 j j j 列的狀態：

1. A i , j = ’.’ A_{i, j}=\text{'.'} Ai,j?=’.’ 表示該位置沒有棋子，沒有棋子的位置不允許進行狀態反轉的操作，
2. A i , j = ’X’ A_{i, j}=\text{'X'} Ai,j?=’X’ 表示該位置有棋子，棋子型別為 ’X’ \text{'X'} ’X’，反轉后棋子型別為 ’O’ \text{'O'} ’O’，
3. A i , j = ’O’ A_{i, j}=\text{'O'} Ai,j?=’O’ 表示該位置有棋子，棋子型別為 ’O’ \text{'O'} ’O’，反轉后棋子型別為 ’X’ \text{'X'} ’X’，

終止的定義是，棋盤上存在同種棋子的 “橫三連” 或者 “豎三聯”，形式化的表述為：

? i , j ∈ N , 1 ≤ i , j ≤ N \exist i,j \in \N,1\leq i, j\leq N ?i,j∈N,1≤i,j≤N 使得 A i , j = A i + 1 , j = A i + 2 , j =? ’.’ A_{i, j}=A_{i+1, j}=A_{i+2, j}\not=\text{'.'} Ai,j?=Ai+1,j?=Ai+2,j??=’.’ 或者 A i , j = A i , j + 1 = A i , j + 2 =? ’.’ A_{i, j}=A_{i, j+1}=A_{i, j+2}\not = \text{'.'} Ai,j?=Ai,j+1?=Ai,j+2??=’.’，

如果一種棋盤狀態不滿足終止的定義，那么我們就稱它 非終止，

有解性證明

接下來的內容中，我們將要證明：至少存在一種反轉次數不超過 ? k 3 ? \left\lfloor\frac{k}{3}\right\rfloor ?3k?? 個棋子的方案，使得操作后的棋盤狀態非終止，

定義：對棋盤上的每一個位置分類

我們在棋盤的每一個格子上寫一個數字，我們第 i i i 行 第 j j j 列的格子上，我們寫上數字 ( i + j ) m o d ?? 3 (i+j) \mod 3 (i+j)mod3，此后，被寫了相同數字的格子被劃分到同一類中，這樣我們就得到三類格子，

第一類格子的坐標的集合為 S 0 = { ( i , j ) : i , j ∈ N , 1 ≤ i , j ≤ N 且 ( i + j ) m o d ?? 3 = 0 } S_0 = \{(i, j): i, j \in \N, 1\leq i, j\leq N 且 (i+j)\mod 3 = 0\} S0?={(i,j):i,j∈N,1≤i,j≤N且(i+j)mod3=0}，
第二類格子的坐標的集合為 S 1 = { ( i , j ) : i , j ∈ N , 1 ≤ i , j ≤ N 且 ( i + j ) m o d ?? 3 = 1 } S_1 = \{(i, j): i, j \in \N, 1\leq i, j\leq N 且 (i+j)\mod 3 = 1\} S1?={(i,j):i,j∈N,1≤i,j≤N且(i+j)mod3=1}，
第三類格子的坐標的集合為 S 2 = { ( i , j ) : i , j ∈ N , 1 ≤ i , j ≤ N 且 ( i + j ) m o d ?? 3 = 2 } S_2 = \{(i, j): i, j \in \N, 1\leq i, j\leq N 且 (i+j)\mod 3 = 2\} S2?={(i,j):i,j∈N,1≤i,j≤N且(i+j)mod3=2}，

為了表述方便，如果 ( i , j ) ∈ S x (i, j)\in S_x (i,j)∈Sx?，我們稱位置 ( i , j ) (i, j) (i,j) 隸屬于分類 S x S_x Sx?，稱 ( i , j ) (i, j) (i,j)的類編號為 x x x（其中 x = ( i + j ) m o d ?? 3 x=(i+j)\mod 3 x=(i+j)mod3），

對 5 × 5 5\times 5 5×5 的棋盤，型別劃分如下：

+--+--+--+--+--+
| 2| 0| 1| 2| 0|
+--+--+--+--+--+
| 0| 1| 2| 0| 1|
+--+--+--+--+--+
| 1| 2| 0| 1| 2|
+--+--+--+--+--+
| 2| 0| 1| 2| 0|
+--+--+--+--+--+
| 0| 1| 2| 0| 1|
+--+--+--+--+--+

引理：“一類定全域”

不難說明，若 ? x ∈ { 0 , 1 , 2 } \exist x \in \{0, 1, 2\} ?x∈{0,1,2} 使得 ? ( i , j ) ∈ S x \forall (i,j)\in S_x ?(i,j)∈Sx? 有 A i , j ? = ′ X ′ A_{i, j}\not ='X' Ai,j??=′X′，則棋盤上棋子 ’X’ \text{'X'} ’X’既不存在“橫三連”，也不存在“豎三聯”，形式化表述為：

? i , j ∈ { 1 , 2 , ? ? , n } , A i , j = ’X’ , A i , j + 1 = ’X’ , A i , j + 2 = ’X’ \forall i, j\in \{1,2,\cdots,n\}, A_{i, j}=\text{'X'}, A_{i, j+1}=\text{'X'},A_{i, j+2}=\text{'X'} ?i,j∈{1,2,?,n},Ai,j?=’X’,Ai,j+1?=’X’,Ai,j+2?=’X’ 不可能同時成立，

? i , j ∈ { 1 , 2 , ? ? , n } , A i , j = ’X’ , A i + 1 , j = ’X’ , A i + 2 , j = ’X’ \forall i, j\in \{1,2,\cdots,n\}, A_{i, j}=\text{'X'}, A_{i+1, j}=\text{'X'},A_{i+2, j}=\text{'X'} ?i,j∈{1,2,?,n},Ai,j?=’X’,Ai+1,j?=’X’,Ai+2,j?=’X’ 也不可能同時成立，

這一點很好證明，無論如何選取 x x x，任意橫相連或者豎相連的三個位置上，都至少有一個隸屬于分類 S x S_x Sx?，因為任意橫相連或者豎相連相鄰的三個位置，他們的的類編號為 { ( i + j ) m o d ?? 3 , ( i + j + 1 ) m o d ?? 3 , ( i + j + 2 ) m o d ?? 3 } \{(i+j)\mod 3, (i+j+1)\mod 3, (i+j+2) \mod 3\} {(i+j)mod3,(i+j+1)mod3,(i+j+2)mod3} 恰好取遍 0 , 1 , 2 {0, 1, 2} 0,1,2 三個值，

演算法：“取兩類格子各自清除一種棋子”

為了表述方便，我們定義了一個函式 C C C 用來統計某種分類的所有格子中，某種棋子的出現次數：

C ( v , ’X’ ) = ∑ ( i , j ) ∈ S v [ A i , j = ’X’ ] C(v, \text{'X'})=\sum_{(i, j)\in S_v} [A_{i, j}=\text{'X'}] C(v,’X’)=(i,j)∈Sv?∑?[Ai,j?=’X’]

C ( v , ’O’ ) = ∑ ( i , j ) ∈ S v [ A i , j = ’O’ ] C(v, \text{'O'})=\sum_{(i, j)\in S_v} [A_{i, j}=\text{'O'}] C(v,’O’)=(i,j)∈Sv?∑?[Ai,j?=’O’]

由于 S 0 ∪ S 1 ∪ S 2 S_0 \cup S_1 \cup S_2 S0?∪S1?∪S2? 恰好覆寫整個棋盤，因此:

∑ v = 0 2 ( C ( v , ’X’ ) + C ( v , ’O’ ) ) = k \sum_{v = 0}^2(C(v, \text{'X'})+C(v, \text{'O'}))=k v=0∑2?(C(v,’X’)+C(v,’O’))=k

根據引理“一類定全域”，我們可以給出一種能夠使棋盤成為“非終止狀態”的操作方案，

1. 選擇一對整數 ( p , q ) (p, q) (p,q) 其中 p , q ∈ { 0 , 1 , 2 } p,q \in \{0, 1, 2\} p,q∈{0,1,2} 且 p =? q p\not = q p?=q，
2. 然后將位置集合 S p S_p Sp? 中所有的 ’X’ \text{'X'} ’X’ 反轉，此次操作后，棋盤上一定不存在三連 ’X’ \text{'X'} ’X’，
3. 最后將位置集合 S q S_q Sq? 中所有的 ’O’ \text{'O'} ’O’ 反轉，此次操作后，棋盤上一定不存在三連 ’O’ \text{'O'} ’O’，

經歷了這樣的操作后，我們得到的棋盤狀態一定是非終止狀態，

那么我們到底反轉了多少個位置呢？是否能夠證明，我們一定能找到一對 ( p , q ) (p,q) (p,q) 使得我們反轉的位置的總數小于等于 ? k 3 ? \left\lfloor\frac{k}{3}\right\rfloor ?3k?? 呢？

為了方便表述，我們再定義一個函式 S ( x , y ) S(x, y) S(x,y)：

S ( x , y ) = C ( x , ’X’ ) + C ( y , ’O’ ) S(x, y) = C(x, \text{'X'}) + C(y, \text{'O'}) S(x,y)=C(x,’X’)+C(y,’O’)

不難發現，當 x =? y x\not = y x?=y 時， S ( x , y ) S(x, y) S(x,y) 就是 p = x , q = y p=x, q=y p=x,q=y 時上述演算法反轉的格子的總數，

另外有：

S ( 0 , 0 ) + S ( 1 , 1 ) + S ( 2 , 2 ) = ∑ v = 0 2 ( C ( v , ’X’ ) + C ( v , ’O’ ) ) = k S(0, 0) + S(1, 1) + S(2, 2)=\sum_{v = 0}^2(C(v, \text{'X'})+C(v, \text{'O'}))=k S(0,0)+S(1,1)+S(2,2)=v=0∑2?(C(v,’X’)+C(v,’O’))=k

那么三分之一是怎么來的呢？

∑ i = 0 2 ∑ j = 0 2 S ( i , j ) = 3 × ∑ v = 0 2 ( C ( v , ’X’ ) + C ( v , ’O’ ) ) = 3 k \sum_{i=0}^2\sum_{j=0}^2S(i, j)=3 \times \sum_{v=0}^2(C(v, \text{'X'})+C(v, \text{'O'}))=3k i=0∑2?j=0∑2?S(i,j)=3×v=0∑2?(C(v,’X’)+C(v,’O’))=3k

我們給出的演算法總共只有六種方案，考慮將這些方案的操作次數求總和，

S ( 0 , 1 ) + S ( 0 , 2 ) + S ( 1 , 0 ) + S ( 1 , 2 ) + S ( 2 , 0 ) + S ( 2 , 1 ) = ( ∑ i = 0 2 ∑ j = 0 2 S ( i , j ) ) ? ( ∑ i = 0 2 S ( i , i ) ) = 3 k ? k = 2 k S(0, 1)+S(0, 2) + S(1, 0) + S(1, 2) + S(2, 0) + S(2, 1)=\left(\sum_{i=0}^2\sum_{j=0}^2S(i, j)\right)-\left(\sum_{i = 0}^2S(i, i)\right) = 3k-k=2k S(0,1)+S(0,2)+S(1,0)+S(1,2)+S(2,0)+S(2,1)=(i=0∑2?j=0∑2?S(i,j))?(i=0∑2?S(i,i))=3k?k=2k

根據抽屜原理（6個數中的最小值一定小于等于這六個數的平均數），有：

min ? { S ( 0 , 1 ) , S ( 0 , 2 ) , S ( 1 , 0 ) , S ( 1 , 2 ) , S ( 2 , 0 ) , S ( 2 , 1 ) } ≤ S ( 0 , 1 ) + S ( 0 , 2 ) + S ( 1 , 0 ) + S ( 1 , 2 ) + S ( 2 , 0 ) + S ( 2 , 1 ) 6 = 2 k 6 = k 3 \min\{S(0, 1) , S(0, 2) , S(1, 0) , S(1, 2) , S(2, 0) , S(2, 1)\}\leq \frac{S(0, 1)+S(0, 2) + S(1, 0) + S(1, 2) + S(2, 0) + S(2, 1)}{6} = \frac{2k}{6}=\frac{k}{3} min{S(0,1),S(0,2),S(1,0),S(1,2),S(2,0),S(2,1)}≤6S(0,1)+S(0,2)+S(1,0)+S(1,2)+S(2,0)+S(2,1)?=62k?=3k?

也就是說，我們找到六種方案中，反轉次數最少的方案反轉，其反轉次數一定小于等于 k 3 \frac{k}{3} 3k?，而反轉次數一定是整數，因此反轉次數一定 ≤ ? k 3 ? \leq \left\lfloor\frac{k}{3}\right\rfloor ≤?3k??，

Q . E . D . Q.E.D. Q.E.D.