Trên bảng có viết dãy các số $0,1,2,\dots ,n$ với $n$ là một số nguyên dương lẻ. An và Bình cùng chơi một trò chơi bằng cách thay phiên nhau xoá các số có trên bảng. An là người đi trước. Gọi $A$ và $B$ lần lượt là tổng của các số mà An và Bình đã xoá.

a) Giả sử $n=7$. Hỏi An có bao nhiêu cách xoá để $\gcd (A,B)=1$?

b) Chứng minh rằng tồn tại vô hạn số nguyên dương $n$ lẻ sao cho An luôn có thể chọn các số để xoá thỏa mãn $\gcd (A,B)$ chẵn bất kể cách xoá số của Bình.

c) Với $n=81$, An thực hiện thao tác xoá các số sao cho giá trị của $\gcd (A,B)$ lớn nhất còn Bình thực hiện thao tác xoá sao cho giá trị của $\gcd (A,B)$ nhỏ nhất. Hỏi giá trị cuối cùng của $\gcd (A,B)$ là bao nhiêu nếu An và Bình đều thực hiện các thao tác xoá tối ưu?

a) Gọi $S$ và $T$ lần lượt là tập hợp các số An và Bình đã xoá.

Để ý rằng $A+B=0+1+\cdots +7=28$ và $\gcd (A,B)=\gcd (A,A+B)=\gcd (A,28)$, nên ta chỉ cần tính số tập hợp có 4 phần tử có tổng nguyên tố cùng nhau với 28. - Để $A$ lẻ, trong $S$ có 3 số lẻ và 1 số chẵn, hoặc 4 số lẻ và 3 số chẵn. Có $2\cdot \left(\genfrac{}{}{0ex}{}{4}{3}\right)\cdot \left(\genfrac{}{}{0ex}{}{4}{1}\right)=32$ bộ. - Để $A$ lẻ và chia hết cho 7, $A$ chỉ có thể nhận các giá trị là 7 hoặc 21 (do $6\le A\le 22$). Chỉ có hai tập hợp $S$ thỏa mãn, đó là $\{0,1,2,4\}$, $\{3,5,6,7\}$.

Do vậy, có $32-2=30$ cách xoá để $\gcd (A,B)=1$.

b) Ta chứng minh $n=8k-7$ thỏa mãn $(k\in {\mathbb{Z}}_{>0})$ đề bài.

Khi đó, trên bảng có $4k$ số chẵn và $4k$ số lẻ. Chiến thuật của An như sau:

- An xoá một số lẻ ở lượt đầu tiên.

- Ở những lượt tiếp theo, nếu Bình xoá số chẵn thì An xoá số chẵn. Nếu Bình xoá số lẻ và số lượng số lẻ còn lại lớn hơn 0, An cũng xoá số lẻ.

Với chiến thuật này, An xoá đúng $\frac{4k}{2}=2k$ số chẵn, do đó số số lẻ An xoá là số chẵn, tức là $A$ chẵn.

Do $A+B=0+1+\cdots +(8k-1)=(8k-1)4k$ là số chẵn nên $B$ cũng chẵn, do đó $2\mid \gcd (A,B)$.

c) Để ý rằng $A+B=0+1+\cdots +81=41\cdot 81$, nên $\gcd (A,B)\mid A+B=41\cdot 3^4$. Ta sẽ chỉ ra chiến thuật để An đảm bảo $A$ chia hết cho 41, và sẽ chỉ ra chiến thuật để Bình đảm bảo $B$ không chia hết cho 3.

Chiến thuật của An. Chia 82 số thành 41 cặp $(i,i+41)$ với $0\le i\le 40$. An bắt đầu bằng cách lấy số 0.

Kể từ lượt đầu tiên trở đi, nếu Bình xóa số còn lại trong cặp thì An xóa một số bất kỳ trong cặp mới. Nếu không, Bình đã xóa đúng một số trong một cặp nào đó. An chỉ cần xóa số còn lại trong cặp đó. Khi đó, sau lượt của An, An đảm bảo có đúng một cặp có một trong hai số bị xóa.

Do vậy, sau khi tất cả các số trên bảng bị xóa, An lấy đúng một số trong mỗi cặp. Khi đó $A\equiv 0+1+\cdots +40=41\cdot 20\equiv 0(\mathrm{mod}41)$. Do đó An đảm bảo $41\mid \gcd (A,B)$, hay $\gcd (A,B)\ge 41$.

Chiến thuật của Bình. Để ý rằng có 82 số chia hết cho 3, 27 số chia 3 dư 1, 27 số chia 3 dư 2. Khi đó, chia 82 số này thành 41 cặp:

- 14 cặp số, với mỗi cặp chia hết cho 3,

- 13 cặp số, với mỗi số trong cặp chia 3 dư 1,

- 13 cặp số, với mỗi số trong cặp chia 3 dư 2,

- 1 cặp còn lại, cặp này chứa một số chia 3 dư 1 và một số chia 3 dư 2.

Khi đó, khi An xóa số nào, Bình xóa số còn lại trong cặp. Sau 82 lượt chơi, An xóa tổng cộng 41 số, và một trong hai trường hợp sau xảy ra:

- Trong 41 số, có 14 số chia hết cho 3, 14 số chia 3 dư 1, 14 số chia 3 dư 2. Khi đó $A\equiv 14\cdot 0+14\cdot 1+13\cdot 2\equiv 1(\mathrm{mod}3)$.

- Trong 41 số, có 14 số chia hết cho 3, 13 số chia 3 dư 1, 14 số chia 3 dư 2. Khi đó $A\equiv 14\cdot 0+13\cdot 1+14\cdot 2\equiv 2(\mathrm{mod}3)$.

Trong cả hai trường hợp, $A$ không chia hết cho 3. Do đó, Bình đảm bảo $\gcd (A,B)\le 41$.

Vậy giá trị cuối cùng của $\gcd (A,B)$ là 41.