Bài Tập Trắc Nghiệm Chuyên Đề: Bất biến, đơn biến và chiến thuật trò chơi (Toán học Lớp 10, 11, 12)

(AI giải đề cho tôi)
**Bài 2.** Đánh số các ô bởi tọa độ nguyên $(x,y)$, $1\le x,y\le 2026$; ô xuất phát là $A=(x_0,y_0)$.

**a)** Mỗi bước của quân mã đổi tọa độ điệu bộ $(\pm 1,\pm 2)$ hoặc $(\pm 2,\pm 1)$, do đó tổng $x+y$ thay đổi một lượng $\pm 1\pm 2$ hoặc $\pm 2\pm 1$, luôn là số **lẻ**. Vậy sau mỗi bước tính chẵn lẻ của $x+y$ đảo dấu; sau 2025 bước (số lẻ) thì ô kết thúc có tính chẵn lẻ của $x+y$ **khác** với ô xuất phát.

Các ô có đúng một đỉnh chung với ô xuất phát là 8 ô kề chéo, tức các ô $(x_0\pm 1,y_0\pm 1)$. Với mỗi ô như vậy ta có
$$(x+y)-(x_0+y_0)=(\pm 1)+(\pm 1)\in \{-2,0,2\},$$
luôn chẵn, tức các ô này có cùng tính chẵn lẻ của $x+y$ với ô xuất phát.

Điều này mâu thuẫn với kết luận trên. Vậy quân mã không thể sau 2025 bước dừng lại ở ô có đúng một đỉnh chung với ô xuất phát. (Điều kiện các ô phân biệt không cần dùng đến.)

**b)** Mỗi bước đi sang phải và lên trên nên quân mã chỉ có thể nhảy theo hai kiểu vector: $(1,2)$ hoặc $(2,1)$. Gọi $a$ là số bước kiểu $(1,2)$, $b$ là số bước kiểu $(2,1)$. Từ ô góc dưới trái $(1,1)$ đến ô góc trên phải $(2026,2026)$ phải có tổng dịch chuyển $(2025,2025)$:
$$a+2b=2025,2a+b=2025.$$
Trừ hai phương trình suy ra $a=b$, suy ra $3a=2025\Rightarrow a=b=675$. Tổng số bước là $675+675=1350$.

Mỗi đường đi tương ứng với một cách sắp xếp 675 bước kiểu $(1,2)$ và 675 bước kiểu $(2,1)$ trong 1350 bước, và ngược lại mọi cách sắp xếp như vậy đều cho một đường đi hợp lệ: vì theo trình tự các bước, cả hai tọa độ không giảm và tổng mỗi tọa độ đúng bằng 2025, nên mọi ô trung gian đều nằm trong bàn cờ (tọa độ mỗi tọa độ nằm trong $[1,2026]$).

Vậy số cách nhảy là
$$\left(\genfrac{}{}{0ex}{}{1350}{675}\right)=\frac{1350!}{675!675!}.$$

a) Chọn $m=18$. Khi đó Mario sẽ nhảy xa được đúng một lần với độ dài $b=14$ (mét). Cần phải di chuyển thêm $18-14=4$ (mét), không đủ cho một lần nhảy với độ dài $a=6$ (mét), nên Mario cần phải nhảy thêm 4 lần, mỗi lần với độ dài 1 mét. Vì vậy Mario phải nhảy đúng 5 lần.
Trong khi đó, có cách khác chỉ sau 3 lần nhảy, mỗi lần với độ dài 6 mét để đến đích với khoảng cách 18 mét, và do đó Mario sẽ thua.

b) Ta gọi một cặp $(a,b)$ là Tốt, nếu Mario luôn thắng với mọi số nguyên dương $m$. Trong trường hợp ngược lại, tức là nếu tồn tại một số nguyên dương $m$ sao cho Mario thua, thì ta nói $(a,b)$ là Không tốt.
Bổ đề. Cặp $(a,b)$ là không tốt khi và chỉ khi tồn tại số nguyên $n\ge 2$ sao cho
$$(n-1)a<b\le n(a-1).$$
Chứng minh bổ đề.
Điều kiện đủ. Giả sử $(n-1)a<b\le n(a-1)$. Rõ ràng khi đó $a>n$. Cho $m=na$, khi đó Mario sẽ nhảy một lần với độ dài $b$ mét. Khoảng cách còn lại cần phải di chuyển là $na-b\in [n;a)$, nên Mario sẽ phải nhảy thêm ít nhất $n$ lần, mỗi lần 1 mét. Tổng cộng Mario phải nhảy ít nhất $n+1$ lần. Tuy nhiên có cách khác đến đích với $n$ lần nhảy, mỗi lần $a$ mét, do đó Mario sẽ thua.
Điều kiện cần. Giả sử $(a,b)$ là một cặp không tốt, do đó có cách nhảy đến đích với số lần nhảy ít hơn cách của Mario. Gọi số lần nhảy tương ứng $(b,a,1)$ mét của Mario là $(x_1,y_1,z_1)$, $x_1\ge 0$, $y_1\ge 0$, $z_1\ge 0$. Suy ra tồn tại một bộ $(x_2,y_2,z_2)$ khác gồm các số nguyên không âm thỏa mãn
$$\{\begin{array}{l}{x}_{1}b+y_{1}a+z_1=x_{2}b+y_{2}a+z_2\\ x_1+y_1+z_1>x_2+y_2+z_2\\ x_1\ge x_2\end{array}$$
Từ các hệ thức trên suy ra $(x_1-x_2)b+(y_1-y_2)a=z_2-z_1<(x_1-x_2)+(y_1-y_2)$.
Do đó $(y_1-y_2)(1-a)>(x_1-x_2)(b-1)\ge 0$. Vì $a>1$ suy ra $y_1<y_2$.
Ngoài ra không thể xảy ra trường hợp $x_1=x_2$, vì khi đó ta phải có đánh giá $z_1-z_2=(y_2-y_1)a>a$, dẫn tới $z_1>a$: mâu thuẫn với cách chơi của Mario.
Vì vậy ta có hệ thức $(x_1-x_2)b+(z_1-z_2)=(y_2-y_1)a$.
Đặt $t=x_1-x_2\in {\mathbb{Z}}^{+}$, $u=y_2-y_1\in {\mathbb{Z}}^{+}$, $v=z_1-z_2\in \mathbb{Z}$. Suy ra $\{\begin{array}{l}tb+v=ua\\ t+v>u\end{array}$
Theo cách nhảy xa của Mario, ta có $v=z_1-z_2\le z_1<a$. Do đó
$$ua-a<ua-v=tb<ua+t-u,$$
dẫn tới $(u-1)a<tb<u(a-1)+t$. Chia cả hai vế cho $t>0$ ta nhận được
$$\frac{u-1}{t}a<b<\frac{u}{t}(a-1)+1.$$
Đặt $\lfloor \frac{u}{t}\rfloor =n\in {\mathbb{Z}}^{+}$, suy ra $(n-1)<\frac{u-1}{t}$ và $\frac{u}{t}\le n$. Do $b$ là số nguyên dương, ta suy ra $(n-1)a<b\le n(a-1)$. Do $n\ge \frac{b}{a-1}>1$ nên $n\ge 2$. Bổ đề được chứng minh.
Bây giờ, với mỗi $b\ge 3$ cố định, ta đếm số cặp $(a,b)$ tốt. Từ Bổ đề trên ta thấy rằng $(a,b)$ là không tốt khi và chỉ khi tồn tại số nguyên $n\ge 2$ sao cho $\frac{b}{n}+1\le a<\frac{b}{n-1}$.
Vì $(n-1)a<n(a-1)$ suy ra $n<a$. Từ đó với $(a,b)$ là không tốt, phải có $n(n-1)<b$.
Gọi $l$ là số nguyên dương sao cho $l(l-1)<b\le l(l+1)$. Khi đó $2\le n\le l$. Vậy cặp $(a,b)$ là không tốt khi và chỉ khi $2\le a<b$ và $a\in S$, ở đó tập $S$ là hợp của $(l-1)$ khoảng đôi một không giao nhau sau đây:
$$S=\left[\frac{b}{l}+1;\frac{b}{l-1}\right)\cup \left[\frac{b}{l-1}+1;\frac{b}{l-2}\right)\cup \cdots \cup \left[\frac{b}{3}+1;\frac{b}{2}\right)\cup \left[\frac{b}{2}+1;b\right),$$
Do đó cặp $(a,b)$ là tốt khi và chỉ khi $1<a<b$ và $a\notin S$. Dễ thấy với mọi $k$, $3\le k\le l$, có duy nhất một số nguyên dương $a=\lfloor \frac{b}{k-1}\rfloor$ nằm giữa hai khoảng liên tiếp $\left[\frac{b}{k-1}+1;\frac{b}{k-2}\right)$, $\left[\frac{b}{k}+1;\frac{b}{k-1}\right)$ và không thuộc hai khoảng này.
Tổng cộng có $(l-2)$ số $a$ như vậy. Ngoài ra, có $\lfloor \frac{b}{l}\rfloor -1$ số $a$ thỏa mãn $1<a<\frac{b}{l}+1$. Với một số $b\le 100$ cố định, có $\lfloor \frac{b}{l}\rfloor -1+(l-2)=\lfloor \frac{b}{l}\rfloor +(l-3)=:K(b)$ cặp $(a,b)$ tốt.
Nhận thấy $K(b)=\{\begin{array}{ll}l+l-3=2l-3,& l(l-1)<b\le l^2\\ l+1+l-3=2l-2,& l^2<b\le l(l+1)\end{array}$. Suy ra $K(b)=\lceil 2\sqrt{b}\rceil -3$.
Do đó số cặp tốt với $1<a<b\le 100$ là $T={\sum }_{b=3}^{100}\left(\lceil 2\sqrt{b}\rceil -3\right)$.
Nhận xét rằng với $91\le b\le 100$, $\lceil 2\sqrt{b}\rceil =20$. Do đó
$$T=(20-3)\cdot 10+\sum _{b=3}^{90}\left(\lceil 2\sqrt{b}\rceil -3\right).$$
Đặt $\lceil 2\sqrt{b}\rceil =c$, suy ra $4\le c\le 19$. Với mỗi số $c$ cố định, ta có $\lceil 2\sqrt{b}\rceil =c$ tương đương với $c-1<2\sqrt{b}\le c\iff \frac{(c-1{)}^2}{4}<b\le \frac{c^2}{4}$. (*)
Bằng cách xét tính chẵn lẻ của $c$, ta thấy có tất cả $\lfloor \frac{c}{2}\rfloor$ số $b$ thỏa mãn (*) với mỗi số $c$ cố định. Vì vậy, nếu đặt $d=\lfloor \frac{c}{2}\rfloor$, ta có
$$T=170+\sum _{c=4}^{19}(c-3)\lfloor \frac{c}{2}\rfloor =170+\sum _{d=2}^9(2d-3)d+\sum _{d=2}^9(2d-2)d$$
$$=170+\sum _{d=2}^9(4d-5)d=170+4\sum _{d=2}^9{d}^2-5\sum _{d=2}^{9}d=170+4\sum _{d=1}^9{d}^2-5\sum _{d=1}^{9}d-4+5$$
$$=171+4\cdot \frac{9\cdot 10\cdot 19}{6}-5\cdot \frac{9\cdot 10}{2}=171+1140-225=1086.$$
Đáp số: 1086 cặp.

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.