Câu 4 (5.0 điểm). Cho $n$ là một số nguyên dương. Một hình vuông được chia thành $n\times n$ ô vuông đơn vị. Các giao điểm của những đường kẻ trong hình gọi là nút lưới. Ta chỉ di chuyển từ một nút lưới đến một nút lưới kề nó dọc theo một cạnh của ô vuông. Một đường đi nối hai nút được gọi là ngắn nhất nếu nó sử dụng ít bước di chuyển nhất. Một tập các nút lưới được gọi là “tốt” nếu với hai nút phân biệt bất kỳ thuộc tập đó, số đường đi ngắn nhất nối hai nút ấy là một số lẻ.

a) Giả sử $n$ là lũy thừa của 2. Chứng minh rằng tồn tại một tập tốt gồm $2n$ nút lưới.

b) Với $n$ tùy ý, hãy xác định số nút lưới lớn nhất có thể có trong một tập tốt.

Lời giải.

Ta phát biểu định lí Kummer như sau:

Định lí Kummer

Giá trị của $v_p(C_n^m)$ bằng với số lần “nhớ” khi cộng $m$ và $n-m$ trong hệ cơ số $p$, hay nói cách khác:

$$v_p(C_n^m)=\frac{S_p(m)+S_p(n-m)-S_p(n)}{p-1}$$

với $S_p(k)$ là tổng các chữ số của $k$ khi được biểu diễn ở hệ cơ số $p$.

Chứng minh: Áp dụng hệ thức Legendre $v_p(n!)=\frac{n-S_p(n)}{p-1}$, ta có:

$$v_p(C_n^m)=v_p\left(\frac{n!}{m!(n-m)!}\right)=v_p(n!)-v_p(m!)-v_p((n-m)!)=\frac{S_p(m)+S_p(n-m)-S_p(n)}{p-1}.$$

a) Giả sử tất cả các nút lưới có tọa độ $(x;y)$ với $x,y\in \mathbb{N}$ và $0\le x,y\le n$. Ta chọn $2n$ điểm, gồm $n+1$ điểm có $y=0$ và $n-1$ điểm có $y=n$ (trừ $(0;n)$ và $(n;n)$). Ta chứng minh tập hợp này là tập tốt.

Với 2 điểm $P_1(x_1;y_1)$ và $P_2(x_2;y_2)$, đặt $X=|x_1-x_2|$ và $Y=|y_1-y_2|$. Để đi từ $P_1$ đến $P_2$, ta cần đi tối thiểu $X$ cạnh song song với trục hoành và tối thiểu $Y$ cạnh song song với trục tung.

Do đó đường đi ngắn nhất cần $X+Y$ cạnh và có $C_{X+Y}^X$ đường đi, do cần chọn vị trí $X$ cạnh song song trục hoành trong $X+Y$ cạnh. Để $C_{X+Y}^X$ lẻ thì $v_2(C_{X+Y}^X)=0$, theo định lí Krummer ta có:

$$v_2(C_{X+Y}^X)=S_2(X)+S_2(Y)-S_2(X+Y)=0\iff S_2(X+Y)=S_2(X)+S_2(Y)$$

Hay nói cách khác, phép cộng $X$ cho $Y$ không có nhớ trong hệ nhị phân.

Với 2 điểm $P_1$ và $P_2$ phân biệt thì $Y=0$ hoặc $Y=n=2^k$ $(k\in \mathbb{N})$, do đó $k$ chữ số cuối của $Y$ luôn bằng 0 và phép cộng $X$ cho $Y$ không có nhớ. Vậy tập hợp $2n$ điểm này là tập tốt.

b) Xét $n$ là một số nguyên dương tùy ý. Đặt $k=\lfloor {\log }_{2}n\rfloor$, tức là $2^k\le n<2^{k+1}$. Ta sẽ chứng minh số nút lưới lớn nhất trong một tập tốt luôn là $2^{\lfloor {\log }_{2}n\rfloor +1}$.

Đầu tiên, ta chứng minh một tập tốt không thể có quá $2^{k+1}$ điểm.

Định nghĩa phép “cộng không nhớ” giữa hai số tự nhiên (ký hiệu là $\oplus$): cộng hai số trong hệ nhị phân theo từng cột nhưng bỏ hết các phép nhớ.

Ví dụ: $6\oplus 3$, ta có $6=(110{)}_2$ và $3=(011{)}_2$. Cột giữa $1+1=0$ (viết 0, không nhớ 1 sang trái) $\to 101_2=5$. Vậy $6\oplus 3=5$.

Gán cho mỗi nút $(x,y)$ một nhãn là số $x\oplus y$.

Nếu hai nút khác nhau $P_1(x_1,y_1)$ và $P_2(x_2,y_2)$ có cùng nhãn thì $x_1\oplus y_1=x_2\oplus y_2$. Suy ra

$$(x_1\oplus y_1)\oplus (x_2\oplus y_2)=(x_2\oplus y_2)\oplus (x_2\oplus y_2)=0(\text{vıˋ }a\oplus a=0)$$

Lại có: $p\oplus q=0$ kéo theo $p=q$ (vì $p=p\oplus 0=p\oplus (q\oplus q)=(p\oplus q)\oplus q=0\oplus q=q$). Áp dụng với $p=x_1\oplus x_2$ và $q=y_1\oplus y_2$, ta được $x_1\oplus x_2=y_1\oplus y_2$.

Đặt $x_1\oplus x_2=y_1\oplus y_2=d$. Do 2 điểm này phân biệt, $x_1\oplus x_2$ và $y_1\oplus y_2$ không đồng thời bằng 0 nên $d>0$ hay $d$ nguyên dương.

Gọi $j$ là vị trí đầu tiên tính từ phải sang trái mà $d$ có chữ số 1 $(j\ge 0)$. Hai số $x_1,x_2$ giống nhau ở mọi vị trí bên phải vị trí $j$ nhưng khác nhau tại vị trí $j$, nên $X=|x_1-x_2|$ chia hết cho $2^j$ và không chia hết cho $2^{j+1}$. Tức là trong hệ nhị phân, $X$ chắc chắn có chữ số 1 tại vị trí $j$. Chứng minh tương tự, $Y$ cũng có chữ số 1 tại vị trí $j$.

Theo Định lí Kummer, vị trí $j$ trong phép cộng $X$ cho $Y$ sẽ có nhớ, do đó $v_2\left(C_{X+Y}^X\right)>0$ nên số đường đi ngắn nhất giữa 2 điểm này là số chẵn (không thoả mãn tính chất tập tốt).

Vậy trong một tập tốt, hai nút khác nhau không thể cùng nhãn. Vì tọa độ các nút bị giới hạn bởi $0\le x,y\le n<2^{k+1}$, mỗi tọa độ được viết trong hệ nhị phân bằng nhiều nhất $k+1$ chữ số (ở các vị trí $0,1,\dots ,k$), do đó mọi nhãn $x\oplus y$ đều nhỏ hơn $2^{k+1}$. Do đó chỉ có tối đa $2^{k+1}$ nhãn khác nhau (từ 0 đến $2^{k+1}-1$) được gán, suy ra một tập tốt có nhiều nhất $2^{k+1}$ nút.

Chọn một lưới ô vuông $2^k\times 2^k$ bên trong lưới ô vuông $n\times n$ kể trên, ta có thể xây dựng một tập tốt gồm $2\cdot 2^k=2^{k+1}$ điểm theo cách xác định ở câu a).

Vậy, số nút lưới lớn nhất có thể có trong một tập tốt đối với $n$ tùy ý là $\boxed{2^{\lfloor {\log }_{2}n\rfloor +1}}$.

$■$