a. (3,0 điểm) Cho $A$ là bảng các ô vuông có kích thước $2026\times 2026$. Điền vào mỗi ô của bảng $A$ một số thuộc tập hợp $M=\{-1;0;1\}$. Có bao nhiêu cách điền sao cho tổng của bốn số trên mỗi bảng vuông con $2\times 2$ bất kì đều bằng 0?
b. (4,0 điểm) Trên mặt phẳng tọa độ $Oxy$, cho tập hợp $S$ gồm 62 điểm phân biệt có tọa độ nguyên sao cho không có 3 điểm nào thẳng hàng. Với mỗi cặp điểm phân biệt $A(x_A,y_A)$ và $B(x_B,y_B)$ thuộc $S$, ta xét đại lượng:
$$T(A,B)=(x_A-x_B{)}^2+70(y_A-y_B{)}^2.$$
Hai điểm $A,B$ được gọi là "liên kết" với nhau nếu $T(A,B)$ chia hết cho 3.
Chứng minh tồn tại một tam giác có ba đỉnh thuộc $S$, đôi một "liên kết" với nhau mà diện tích là một số nguyên chia hết cho 9.

a) Ta giải bài toán tổng quát cho bảng $n\times n$.

Gọi $a_{i,j}\in \{-1,0,1\}$ là số được điền vào ô thuộc hàng $i$, cột $j$.

Điều kiện đề bài cho $a_{i,j}+a_{i+1,j}+a_{i,j+1}+a_{i+1,j+1}=0$, hay $a_{i+1,j+1}=-a_{i,j}-a_{i+1,j}-a_{i,j+1}$.

Do đó, nếu đã biết hàng đầu tiên và cột đầu tiên thì ta lần lượt xác định được tất cả các ô còn lại của bảng. Đặt $x_i=(-1{)}^{i+1}{a}_{i,1}$ và $y_j=(-1{)}^{j+1}{a}_{1,j}$.

Ta có $x_1=y_1=a_{1,1}$. Từ điều kiện trên, bằng quy nạp theo $i+j$, ta thu được

$$a_{i,j}=(-1{)}^{i+j}(x_i+y_j-a_{1,1}).$$

bởi công thức đúng tại các ô $(i,j)$, $(i+1,j)$, $(i,j+1)$ thì công thức cũng đúng tại $(i+1,j+1)$ do

$$a_{i+1,j+1}=-a_{i,j}-a_{i+1,j}-a_{i,j+1}=(-1{)}^{i+j}(x_{i+1}+y_{j+1}-a_{1,1}).$$

Vì $a_{i,j}\in \{-1,0,1\}$ nên ta có điều kiện cần và đủ là $x_i+y_j-x_1\in \{-1,0,1\}$ với mọi $i,j$.

Giờ ta đếm số cách điền theo giá trị của $x_1=y_1$.

Trường hợp 1. $x_1=y_1=0$.

Khi đó điều kiện trở thành $x_i+y_j\in \{-1,0,1\}$. Ta xét dãy $x_2,\dots ,x_n$.

- Nếu $x_2=\cdots =x_n=0$ thì dãy $y_2,\dots ,y_n$ được chọn tùy ý trong $\{-1,0,1\}$, nên có $3^{n-1}$ cách.
- Nếu các $x_i$ chỉ nhận các giá trị $0,1$ và có ít nhất một giá trị bằng 1, thì có $2^{n-1}-1$ cách chọn dãy $(x_i)$. Khi đó mọi $y_j$ phải thuộc $\{-1,0\}$, nên có $2^{n-1}$ cách chọn dãy $(y_j)$.
- Tương tự, nếu các $x_i$ chỉ nhận các giá trị $-1,0$ và có ít nhất một giá trị bằng $-1$, ta cũng có $(2^{n-1}-1)2^{n-1}$ cách.
- Cuối cùng, nếu dãy $(x_i)$ chứa cả $1$ và $-1$, thì trong tổng số $3^{n-1}$ dãy, ta loại đi dãy toàn 0, các dãy chỉ chứa $0,1$ và có ít nhất một số 1, cùng các dãy chỉ chứa $-1,0$ và có ít nhất một số $-1$. Do đó số cách chọn là $3^{n-1}-1-2(2^{n-1}-1)=3^{n-1}-2^n+1$, và mọi $y_j$ buộc phải bằng 0.

Vậy số cách trong trường hợp này là

$$A=3^{n-1}+2(2^{n-1}-1)2^{n-1}+3^{n-1}-2^n+1=2\cdot 3^{n-1}+2\cdot 4^{n-1}-2^{n+1}+1$$

Trường hợp 2. $x_1=y_1=1$.

Điều kiện trở thành $x_i+y_j-1\in \{-1,0,1\}$, hay tương đương với $x_i+y_j\ge 0$.

- Nếu $x_2=\cdots =x_n=1$ thì dãy $y_2,\dots ,y_n$ được chọn tùy ý, nên có $3^{n-1}$ cách.
- Nếu các $x_i$ chỉ nhận các giá trị $0,1$ và có ít nhất một giá trị bằng $0$, thì có $2^{n-1}-1$ cách chọn dãy $(x_i)$. Khi đó mọi $y_j$ phải thuộc $\{0,1\}$, nên có $2^{n-1}$ cách chọn dãy $(y_j)$.
- Nếu dãy $(x_i)$ có ít nhất một giá trị bằng $-1$, thì có $3^{n-1}-2^{n-1}$ cách chọn. Khi đó tất cả $y_j$ đều phải bằng $1$.

Vậy số cách trong trường hợp này là
$$B=3^{n-1}+(2^{n-1}-1)2^{n-1}+3^{n-1}-2^{n-1}=2\cdot 3^{n-1}+4^{n-1}-2^n.$$

Trường hợp $x_1=y_1=-1$ hoàn toàn tương tự trường hợp trên, nên cũng có $B$ cách.

Vậy tổng số cách điền cần tính là
$$S_n=A+2B=4\cdot 4^{n-1}+6\cdot 3^{n-1}-2^{n+2}+1=4^n+2\cdot 3^n-4\cdot 2^n+1.$$

Với $n=2026$, số cách cần tính là $4^{2026}+2\cdot 3^{2026}-4\cdot 2^{2026}+1$.

b) Để ý 2 điểm $A(x_A,y_A)$ và $B(x_B,y_B)$ liên kết khi và chỉ khi $x_A\equiv x_B(\mathrm{mod}3)$ và $y_A\equiv y_B(\mathrm{mod}3)$.

Chia 62 điểm của $S$ vào 9 bộ theo cặp số dư $(x\mathrm{mod}3,y\mathrm{mod}3)$.

Theo nguyên lý Dirichlet, tồn tại một bộ chứa ít nhất $\lceil \frac{62}{9}\rceil =7$ điểm, giả sử là $A_1,\dots ,A_7$.

Khi đó mọi bộ hai điểm trong số này đều liên kết.

Giả sử các điểm trên có dạng $A_i=(3X_i+r,3Y_i+s)$ với $X_i,Y_i\in \mathbb{Z}$.

Với ba điểm $A_1(x_1,y_1)$, $A_2(x_2,y_2)$, $A_3(x_3,y_3)$, diện tích tam giác $A_1{A}_2{A}_3$ là
$$S_{A_1{A}_2{A}_3}=\frac{1}{2}\left|(x_2-x_1)(y_3-y_1)-(x_3-x_1)(y_2-y_1)\right|$$
$$=\frac{9}{2}\left|(X_2-X_1)(Y_3-Y_1)-(X_3-X_1)(Y_2-Y_1)\right|.$$

Xét 7 cặp $(X_i,Y_i)$ theo modulo 2, để ý tồn tại hai điểm, chẳng hạn $A_1,A_2$, sao cho $X_1\equiv X_2(\mathrm{mod}2)$ và $Y_1\equiv Y_2(\mathrm{mod}2)$. Chọn $A_3$ bất kỳ trong 5 điểm còn lại. Khi đó cả $X_2-X_1$ và $Y_2-Y_1$ đều chẵn, suy ra
$$(X_2-X_1)(Y_3-Y_1)-(X_3-X_1)(Y_2-Y_1)$$
là số chẵn. Vì thế diện tích tam giác $A_1{A}_2{A}_3$ là một số nguyên chia hết cho 9.

Nhận xét: Thậm chí ta chỉ cần tập $S$ gồm 37 điểm là đủ, và đây là giá trị tối ưu nhất có thể.