2023 成大邀請賽 pA 題解

前言

雖然這題的答案就是 cout << 1;，但因為我隊友不知道怎麼證明，所以就了這篇文章。

題目

題目網址

總之就是有一個九宮格，只填了三個數字 a /b/ c，試問滿足直排、橫排、兩個對角線上的所有數字的和都相同的解有幾個。

\(a\)	?	?
?	?	\(b\)
\(c\)	?	?

解題思路

直排、橫排、兩個對角線總共可以列出 8 個等式，而我們有七個未知數（缺的六個格字還有數字和）。
重新定義一下

\(a\)	\(x_1\)	\(x_2\)
\(x_3\)	\(x_4\)	\(b\)
\(c\)	\(x_5\)	\(x_6\)

\[ \begin{align*} y &= a+x_1+x_2 \\ &= x_3+x_4+b \\ &= c+x_5+x_6 \\ &= a+x_3+c \\ &= x_1+x_4+x_5 \\ &= x_2+b+x_6 \\ &= a+x_4+x_6 \\ &= x_2+x_4+c \end{align*} \]

其中會發現 \(y=x_1+x_4+x_5\)，是當

\[ \begin{align*} y &= a+x_1+x_2 \\ &= x_3+x_4+b \\ &= c+x_5+x_6 \\ &= a+x_3+c \\ &= x_2+b+x_6 \\ \end{align*} \]

的必然結果（由前三條等式減去後兩條等式的結果），因此可以將此式去掉，剩下七個等式，以順序 \(x_1, x_2, \cdots, x_6, y\) 排列，轉換成增廣矩陣。

\[ \left[ \begin{array}{ccccccc|c} -1 & -1 & 0 & 0 & 0 & 0 & 1 & a \\ 0 & 0 & -1 & -1 & 0 & 0 & 1 & b \\ 0 & 0 & 0 & 0 & -1 & -1 & 1 & c \\ 0 & 0 & -1 & 0 & 0 & 0 & 1 & a + c \\ 0 & -1 & 0 & 0 & 0 & -1 & 1 & b \\ 0 & 0 & 0 & -1 & 0 & -1 & 1 & a \\ 0 & -1 & 0 & -1 & 0 & 0 & 1 & c \\ \end{array} \right] \]

利用克拉瑪算出判別式 $\Delta$ 的值

這邊直接用計算機算，得到答案為 - 1。

\[ \Delta = \begin{vmatrix} -1 & -1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & -1 & -1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & -1 & -1 & 1 \\ 0 & 0 & -1 & 0 & 0 & 0 & 1 \\ 0 & -1 & 0 & 0 & 0 & -1 & 1 \\ 0 & 0 & 0 & -1 & 0 & -1 & 1 \\ 0 & -1 & 0 & -1 & 0 & 0 & 1 \\ \end{vmatrix} = -1 \]

這邊這題就是可以解了，因為 \(\Delta \neq 0\)，所以只有唯一解，且因為 \(\Delta = -1, \Delta_{x_1}, \Delta_{x_2}, \cdots, \Delta_{x_6}, \Delta_{y} \in \mathbb{Z}\)，故 \(x_1, x_2, \cdots, x_6, y \in \mathbb{Z}\)，所以答案必為 1。

用高斯消去法順便得到各個位置的值

稍微整理一下之後可以將增廣矩陣轉換成這樣，所以也就是只有一組解了

\[ \left[ \begin{array}{ccccccc|c} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 2c-b \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 2a+c-2b \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 2a+2c-3b \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & a+c-b \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 2a-b \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & a+2c-2b \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 3a+3c-3b \\ \end{array} \right] \]

寫到九宮格內如下

\(a\)	\(2c-b\)	\(2a+c-2b\)
\(2a+2c-3b\)	\(a+c-b\)	\(b\)
\(c\)	\(2a-b\)	\(a+2c-2b\)

但其實也不用砸這麼大的科技，就只要先找到 \(x_4\) 然後用同樣邏輯找到其他的就好了
\(a+x_3+c=x_3+x4+b \Rarr x_4 = a+c-b\)
然後 \(x_2, x_6\) 可以藉由對角線列出二元聯立方方程式解出來，最後 \(x_1, x_3, x_5\) 就迎刃而解了

程式碼

#include <bits/stdc++.h>
int main(){
    std::cout << 1;
    return 0;
}