Trên mặt phẳng tọa độ giả lập cho một trò chơi điện tử, Bảo Long và Châu Mai cùng điều khiển một chiếc xe. Ban đầu, xe ở gốc tọa độ và hướng về chiều dương của trục $Ox$. Xe có thể đi theo một trong bốn hướng: lên, xuống, trái, phải. Hai bạn chơi luân phiên thực hiện các lượt đi như sau:

- Long cho xe đi thẳng theo hướng hiện tại với độ dài đường đi là số nguyên tùy ý từ 1 đến 10.
- Mai không di chuyển mà quay xe một góc $90^{\circ }$ cùng chiều hoặc ngược chiều kim đồng hồ.

Biết rằng Long đi trước và thực hiện tổng cộng $k$ lượt. Sau mỗi lượt của Long, hệ thống ghi nhận lại vị trí đỗ xe. Nếu có một vị trí đỗ nào trùng với vị trí được ghi nhận trước đó (kể cả gốc tọa độ) thì Mai thắng, nếu không thì Long thắng. Hãy xác định người có chiến thuật thắng nếu:

(1) $k=20$.

(2) $k=400$.

(1) Để giải quyết bài toán, ta sẽ chỉ ra một chiến thuật cụ thể giúp Long luôn giành chiến thắng.

Thật vậy, trong $k=20$ lượt đi của mình, Long sẽ thực hiện chính xác 10 lượt di chuyển theo phương ngang (trục $Ox$) và 10 lượt theo phương dọc (trục $Oy$). Điều kiện này hiển nhiên được thỏa mãn do xen kẽ giữa các lượt của Long là 19 lần Mai quay xe một góc $90^{\circ }$.

Gọi $P_0(0,0)$ là vị trí ban đầu và $P_1,P_2,\dots ,P_{20}$ là tọa độ của xe sau mỗi lượt đi tương ứng của Long. Ý tưởng cốt lõi của Long là tập trung kiểm soát hoàn toàn sự thay đổi tọa độ trên một trục, chẳng hạn trục $Ox$, nhằm đảm bảo chiếc xe không bao giờ quay lại một hoành độ đã từng đi qua.

Cụ thể, chiến thuật của Long được xây dựng như sau:

- Vào các lượt đi theo phương ngang (lượt lẻ: $1,3,5,\dots ,19$), Long sẽ quan sát hướng xe hiện tại: nếu xe đang hướng về chiều dương của $Ox$, Long quyết định đi thẳng 10 đơn vị; ngược lại, nếu xe hướng về chiều âm của $Ox$, Long đi thẳng 1 đơn vị.
- Đối với các lượt đi theo phương dọc (trục $Oy$), Long có thể chọn độ dài di chuyển tùy ý thỏa mãn luật chơi, chẳng hạn luôn chọn đi 1 đơn vị.

Ta sẽ chứng minh tính đúng đắn của chiến thuật này. Gọi $X_0=0$ và $X_1,X_2,\dots ,X_{10}$ lần lượt là tọa độ $x$ của xe ngay sau các lượt di chuyển ngang. Để thấy, độ lệch tọa độ giữa $X_{m-1}$ và $X_m$ hoàn toàn phụ thuộc vào hướng xe:

- Nếu hướng dương: $X_m=X_{m-1}+10\equiv X_{m-1}-1(\mathrm{mod}11)$.
- Nếu hướng âm: $X_m=X_{m-1}-1\equiv X_{m-1}-1(\mathrm{mod}11)$.

Như vậy, với mọi nỗ lực quay xe của Mai, ta luôn thu được một hệ thức bất biến theo modulo 11:

$$X_m\equiv X_{m-1}-1(\mathrm{mod}11).$$

Xuất phát từ $X_0=0$, các giá trị tiếp theo khi đối chiếu trên modulo 11 sẽ tạo thành dãy:

$$X_1\equiv 10,X_2\equiv 9,X_3\equiv 8,\dots ,X_{10}\equiv 1(\mathrm{mod}11).$$

Tập hợp 11 giá trị $\{X_0,X_1,\dots ,X_{10}\}$ có số dư đôi một khác nhau khi chia cho 11, từ đó suy ra 11 giá trị này trên thực tế là hoàn toàn phân biệt.

Bây giờ, quan sát dãy tọa độ $x$ của toàn bộ 21 điểm $P_0,P_1,P_2,\dots ,P_{20}$, ta thấy chúng có dạng:

$$X_0,X_1,X_1,X_2,X_2,\dots ,X_{10},X_{10}.$$

Điều kiện cần để hai điểm $P_i$ và $P_j$ trùng nhau là tọa độ $x$ của chúng phải bằng nhau. Nhờ tính phân biệt của tập các hoành độ $X_m$ vừa chứng minh, sự lặp lại tọa độ $x$ duy nhất chỉ có thể xảy ra ở các cặp điểm liền kề mang dạng $P_{2m-1}(X_m,Y_{m-1})$ và $P_{2m}(X_m,Y_m)$.

Tuy nhiên, xét tung độ tương ứng, ta luôn có $Y_m=Y_{m-1}\pm l_{2m}$. Vì luật chơi quy định nghiêm ngặt độ dài $l\ge 1$, ta lập tức có $Y_m\ne Y_{m-1}$. Điều này dẫn đến $P_{2m-1}\ne P_{2m}$.

Từ các lập luận trên, ta kết luận không có bất kỳ hai điểm nào trong 21 điểm trùng nhau, đồng nghĩa Bảo Long chắc chắn giành chiến thắng.

(2) Ta sẽ chứng minh rằng Châu Mai luôn có chiến thuật giành chiến thắng bằng cách ép chiếc xe không thể thoát ra khỏi một miền hữu hạn. Khi số lượng vị trí được ghi nhận vượt quá số điểm nguyên trong miền đó, theo nguyên lí Dirichlet, xe buộc phải đi qua một vị trí ít nhất hai lần.

Cụ thể, chiến thuật của Mai được xây dựng dựa trên sự độc lập giữa hai trục tọa độ. Trước mỗi lượt đi của Long, Mai sử dụng quyền quay xe $90^{\circ }$ của mình (chọn rẽ trái hoặc phải) để hướng chiếc xe vào chiều dương hoặc chiều âm của trục vuông góc mà Long sắp sửa đi tới. Gọi tọa độ hiện tại trên trục đó là $z$ ($z$ đóng vai trò là $x$ hoặc $y$). Mai sẽ quan sát $z$ và hành động như sau:

- Nếu $z\le 0$, Mai hướng xe về phía chiều dương của trục.
- Nếu $z>0$, Mai hướng xe về phía chiều âm của trục.

Ta sẽ chứng minh tính đúng đắn của chiến thuật này bằng cách chỉ ra mọi tọa độ $z$ luôn bị giới hạn. Giả sử Long di chuyển một khoảng $l$ (với $1\le l\le 10$):

- Ban đầu $z_0=0$. Mai chọn chiều dương, sau khi Long đi khoảng $l$, tọa độ tiếp theo là $z_1=l⟹z_1\in [1,10]$.
- Nếu vị trí hiện tại $z\in [1,10]$ (tức $z>0$): Mai chọn chiều âm. Tọa độ mới sẽ là $z^{\prime }=z-l$. Vì $1\le z\le 10$ và $1\le l\le 10$, ta suy ra $z^{\prime }\in [-9,9]$.
- Nếu vị trí hiện tại $z\in [-9,0]$ (tức $z\le 0$): Mai chọn chiều dương. Tọa độ mới sẽ là $z^{\prime }=z+l$. Vì $-9\le z\le 0$ và $1\le l\le 10$, ta có $z^{\prime }\in [-8,10]$.

Quy nạp theo số bước di chuyển, ta khẳng định kể từ $P_0$, tất cả các hoành độ $x$ và tung độ $y$ của xe luôn bị giam chặt trong đoạn số nguyên $[-9,10]$. Số lượng giá trị nguyên trong đoạn $[-9,10]$ là $10-(-9)+1=20$. Do cả $x$ và $y$ đều nhận tối đa 20 giá trị, số lượng vị trí phân biệt $(x,y)$ tối đa mà xe có thể đi tới là $20\times 20=400$ vị trí.

Trong trò chơi có $k=400$ lượt đi, hệ thống sẽ ghi nhận tổng cộng 401 vị trí (bao gồm cả gốc tọa độ $P_0$ ban đầu). Theo nguyên lí Dirichlet, khi xếp 401 điểm vào 400 vị trí khả dĩ, chắc chắn phải tồn tại ít nhất hai điểm trùng nhau. Điều này đồng nghĩa với việc Châu Mai chắc chắn giành chiến thắng.