Bài Tập Trắc Nghiệm Chuyên Đề: Quy tắc đếm, hoán vị/chỉnh hợp/tổ hợp (Toán học Lớp 10)

Trước hết, xét cách đi hình con rắn như sau của quân xe: bắt đầu từ góc dưới bên trái, đi sang phải, mỗi nước sang ô bên cạnh cho đến hết hàng, sau đó đi lên ô ở hàng ngay trên, rồi đi sang trái, mỗi nước sang ô bên cạnh cho đến hết hàng, rồi đi lên ô ở hàng phía trên, v.v. Với cách đi này, ta dễ thấy rằng hiệu số lớn nhất của 2 ô chung cạnh bằng 15.

Ta chứng minh đây là giá trị nhỏ nhất cần tìm.
Giả sử ngược lại rằng $n<15$. Xét các số ở hàng trên cùng.
Vì hiệu giữa hai số kề nhau trong hàng này không vượt quá 14, nên quân xe đi từ một số nhỏ hơn đến một số lớn hơn ở trên hàng này mà không đi qua một ô ở hàng dưới cùng (vì để xuống đó cần ít nhất 7 nước, và để quay lại cũng cần ít nhất 7 nước, cộng thêm một nước trong chính hàng dưới).

Do đó quân xe đã đi qua tất cả các ô của hàng trên cùng mà không đi xuống hàng dưới cùng.
Tương tự, quân xe di chuyển qua các ô của hàng dưới cùng mà không đi lên hàng trên cùng. Điều này có nghĩa là tất cả các số ở hàng trên cùng đều lớn hơn (hoặc đều nhỏ hơn) các số ở hàng dưới cùng.

Tương tự, tất cả các số ở cột ngoài cùng bên trái đều lớn hơn (hoặc đều nhỏ hơn) các số ở cột ngoài cùng bên phải.
Không mất tính tổng quát, giả sử các số ở cột ngoài cùng bên trái lớn hơn các số ở cột ngoài cùng bên phải, còn các số ở hàng dưới cùng lớn hơn các số ở hàng trên cùng.
Bây giờ, gọi $A$ là số của ô góc trên cùng bên trái và $B$ là số của ô góc dưới cùng bên phải.
Theo giả thiết, nếu xét theo cột thì $A>B$, còn nếu xét theo hàng thì $A<B$, mâu thuẫn.

Số cách xếp 10 người tùy ý là $10!=3628800$. Ta tìm số cách xếp sao cho có ít nhất 1 cặp anh em sinh đôi ngồi cạnh nhau. Ta xét 3 trường hợp sau:

Trường hợp 1: "cặp anh em sinh đôi thứ nhất ngồi cạnh nhau và cặp anh em sinh đôi thứ hai ngồi cạnh nhau". Có 2! cách xếp cặp anh em sinh đôi thứ nhất ngồi cạnh nhau. Có 2! cách xếp cặp anh em sinh đôi thứ hai ngồi cạnh nhau. Khi đó, có 8! cách sắp xếp thứ tự của 2 cặp anh em sinh đôi này và 6 người còn lại. Suy ra, TH1 có 2!.2!.8! = 161280 cách.

Trường hợp 2: "cặp anh em sinh đôi thứ nhất ngồi cạnh nhau và cặp anh em sinh đôi thứ hai không ngồi cạnh nhau". Có 2! cách xếp cặp anh em sinh đôi thứ nhất ngồi cạnh nhau. Có 7! cách xếp thứ tự cặp anh em sinh đôi thứ nhất và 6 người còn lại. Khi đó tạo ra 8 khoảng trống. Có $A_8^2$ cách xếp 2 anh em sinh đôi của cặp thứ hai vào 2 trong 8 khoảng trống này. Suy ra TH2 có $2!.7!.A_8^2=564480$ cách.

Trường hợp 3: "cặp anh em sinh đôi thứ hai ngồi cạnh nhau và cặp anh em sinh đôi thứ nhất không ngồi cạnh nhau". Tương tự như TH2, có $2!.7!.A_8^2=564480$ cách.

Suy ra, số cách xếp thoả yêu cầu bài toán là $3628800-161280-2.564480=2338560$ cách xếp.

Biến cố ngược lại là sau khi chọn sách xong có môn không còn lại quyển nào, vì tổng số sách của hai loại bất kì lớn hơn 5 quyển nên không thể cùng hết hai loại sách do đó chỉ có một môn hết sách. TH1: Không còn một quyển sách toán: $A_5^4\cdot A_6^1=720$. TH2: Không còn một quyển sách lý: $A_5^3\cdot A_7^2=2520$. TH3: Không còn một quyển sách hóa: $A_5^3\cdot A_7^2=2520$. Suy ra số cách tặng để có một môn không còn lại quyển nào là: 720+2520+2520=5760. Số cách tặng mỗi một trong ba loại sách trên đều còn lại ít nhất một quyển $A_{10}^5-5760=24480$. (Điểm: 0,25 + 0,25)

(AI giải đề cho tôi)
Chữ số 2 đứng liền giữa 1 và 3 nên khối ba chữ số liên tiếp là $123$ hoặc $321$ (2 cách). Coi khối này là một đại thể, cần xếp đại thể này cùng 4 chữ số khác chọn từ $\{0;4;5;6;7;8;9\}$ thành số có 7 chữ số khác nhau từng đôi một.

- Có chữ số 0: chọn thêm 3 chữ số từ 6 chữ số còn lại: $C_6^3=20$ cách. Xếp 5 đại thể: $5!=120$, trừ các cách 0 đứng đầu: $4!=24$, còn $120-24=96$. Số cách: $20\cdot 96=1920$.
- Không có chữ số 0: chọn 4 chữ số từ $\{4;5;6;7;8;9\}$: $C_6^4=15$ cách, xếp 5 đại thể: $5!=120$. Số cách: $15\cdot 120=1800$.

Tổng cho một khối: $1920+1800=3720$. Có 2 khối nên kết quả: $2\cdot 3720=7440$. Khớp đáp án chính thức B (7440) ở bảng đáp án mã đề 1009.

(AI giải đề cho tôi)
Số cần tìm có 5 chữ số đôi một khác nhau, các chữ số lấy từ tập $\{0,1,2,3,4,5,6\}$, chữ số đầu khác 0, và chia hết cho 6 tức chia hết cho cả 2 và 3.

Bước 1: Chọn 5 chữ số có tổng chia hết cho 3. Phân theo phần dư mod 3: nhóm dư 0 là $\{0,3,6\}$ (3 phần tử), nhóm dư 1 là $\{1,4\}$ (2 phần tử), nhóm dư 2 là $\{2,5\}$ (2 phần tử). Gọi $(a,b,c)$ là số chữ số chọn từ từng nhóm, $a+b+c=5$ và $b+2c\equiv 0(\mathrm{mod}3)$. Các trường hợp thỏa mãn:
- $(3,1,1)$: $b+2c=3\equiv 0$: có $C_3^3{C}_2^1{C}_2^1=4$ tập chữ số.
- $(1,2,2)$: $b+2c=6\equiv 0$: có $C_3^1{C}_2^2{C}_2^2=3$ tập chữ số.
(Các trường hợp $(3,2,0),(2,2,1),(2,1,2),\dots$ cho tổng dư $2,4,5$ không chia hết cho 3.)

Bước 2: Với mỗi tập chữ số, đếm các cách xếp thành số 5 chữ số, chữ số cuối chẵn (để chia hết cho 2) và chữ số đầu khác 0. Số các số = (số cách chọn chữ số cuối chẵn) × (hoán vị 4 chữ số còn lại) trừ đi các trường hợp chữ số đầu bằng 0.

Tập dạng $(3,1,1)$: $\{0,3,6,x,y\}$ với $x\in \{1,4\},y\in \{2,5\}$ (đều chứa 0):
- $\{0,3,6,1,2\}$: chữ số chẵn $\{0,6,2\}$: $3\cdot 4!-2\cdot 3!=72-12=60$.
- $\{0,3,6,1,5\}$: chẵn $\{0,6\}$: $2\cdot 24-1\cdot 6=42$.
- $\{0,3,6,4,2\}$: chẵn $\{0,6,4,2\}$: $4\cdot 24-3\cdot 6=78$.
- $\{0,3,6,4,5\}$: chẵn $\{0,6,4\}$: $3\cdot 24-2\cdot 6=60$.
Tổng: $240$.

Tập dạng $(1,2,2)$: chọn 1 phần tử từ $\{0,3,6\}$ cùng $\{1,4\},\{2,5\}$:
- $\{0,1,4,2,5\}$: chẵn $\{0,4,2\}$: $72-12=60$.
- $\{3,1,4,2,5\}$: chẵn $\{4,2\}$, không chứa 0: $2\cdot 24=48$.
- $\{6,1,4,2,5\}$: chẵn $\{6,4,2\}$, không chứa 0: $3\cdot 24=72$.
Tổng: $180$.

Kết quả: $240+180=420$ số. Đáp án A.

(AI giải đề cho tôi)
Gọi $x,y,z$ lần lượt là số học sinh nhận cặp (Toán, Lý), (Toán, Hóa), (Lý, Hóa). Vì mỗi học sinh nhận 2 cuốn và tổng số sách là 20 = 2·10 nên mọi sách đều được phát: $x+y=8$ (hết Toán), $x+z=7$ (hết Lý), $y+z=5$ (hết Hóa). Giải hệ: $x=5,y=3,z=2$ (thỏa $x+y+z=10$). Vậy chỉ có một cấu hình duy nhất. Vì học sinh là đối tượng phân biệt, số cách phát là số hoán vị của 10 học sinh vào các nhóm: $\frac{10!}{5!3!2!}=\frac{3628800}{120\cdot 6\cdot 2}=2520$. Khớp với đáp án nguồn 2520.

(AI giải đề cho tôi)
Tam giác vuông nội tiếp đường tròn $(O;\sqrt{2})$ thì cạnh huyền là đường kính. Có 18 cặp đỉnh đối nhau $(A_i,A_{i+18})$, mỗi cặp cho cạnh huyền $AB=2R=2\sqrt{2}$. Gọi $C$ là đỉnh thứ ba, góc ở tâm nuốt cung $AC$ là $\alpha =\frac{k\pi }{18}$ với $k\in \{1,2,\dots ,35\}$, $k\ne 18$. Hai cạnh góc vuông là $2\sqrt{2}\sin \frac{\alpha }{2}$ và $2\sqrt{2}\cos \frac{\alpha }{2}$, nên diện tích $S=\frac{1}{2}\cdot 2\sqrt{2}\sin \frac{\alpha }{2}\cdot 2\sqrt{2}\cos \frac{\alpha }{2}=2\sin \alpha =2\sin \frac{k\pi }{18}$. Để $S$ nguyên cần $\sin \frac{k\pi }{18}\in \left\{\frac{1}{2},1\right\}$ (các giá trị khác của $\sin \frac{k\pi }{18}$ đều vô tỉ). Với $\sin \frac{k\pi }{18}=\frac{1}{2}$: $k\in \{3,15,21,33\}$ cho $S=1$. Với $\sin \frac{k\pi }{18}=1$: $k\in \{9,27\}$ cho $S=2$. Lưu ý phải xét cả hai phía của đường kính: các giá trị $k$ và $36-k$ cho cùng diện tích nhưng đỉnh thứ ba khác nhau, nên mỗi đường kính có 6 lựa chọn đỉnh thứ ba. Vậy tổng số cách chọn là $18\times 6=108$.

(AI giải đề cho tôi)
Tam giác vuông nội tiếp đường tròn $(O;\sqrt{2})$ có cạnh huyền là đường kính. Có 18 đường kính nối các cặp đỉnh $A_i{A}_{i+18}$. Với mỗi đường kính, gọi $\theta$ là góc ở tâm giữa đỉnh góc vuông và một đầu mút của đường kính; $\theta$ là bội của $10^{\circ }$, $0^{\circ }<\theta <360^{\circ }$, $\theta \ne 180^{\circ }$. Hai cạnh góc vuông có độ dài $2\sqrt{2}\sin \frac{\theta }{2}$ và $2\sqrt{2}\left|\cos \frac{\theta }{2}\right|$, nên diện tích $S=\frac{1}{2}\cdot 8\left|\sin \frac{\theta }{2}\cos \frac{\theta }{2}\right|=2|\sin \theta |$.

Cần $2|\sin \theta |$ là số nguyên, tức $|\sin \theta |\in \left\{\frac{1}{2},1\right\}$ (loại $|\sin \theta |=0$ vì tam giác suy biến). Xét cả hai nửa mặt phẳng của đường kính ($\theta \in (0^{\circ },360^{\circ })$, $\theta \ne 180^{\circ }$):
- $|\sin \theta |=\frac{1}{2}\Rightarrow \theta \in \{30^{\circ },150^{\circ },210^{\circ },330^{\circ }\}$ (diện tích bằng 1);
- $|\sin \theta |=1\Rightarrow \theta \in \{90^{\circ },270^{\circ }\}$ (diện tích bằng 2).

Vậy mỗi đường kính có đúng 6 vị trí đỉnh góc vuông thỏa mãn (các cặp $\theta$ và $360^{\circ }-\theta$ cho hai tam giác khác nhau, nằm khác phía đối với đường kính). Số cách chọn là $18\times 6=108$.

Lời giải. Gọi $a_1,a_2,\dots ,a_{2000}$ là các số dương có tổng bằng 1 và $a_i\le \frac{1}{100}$ $(i=1,2,\dots ,2000)$.
Không mất tính tổng quát, giả sử $a_1\le a_2\le \dots \le a_{2000}$.
Giả sử không tồn tại một tập "co cụm bậc hai" có 51 phần tử được chọn từ 2000 số ở trên.
Xét tập $M_k=\{a_k,a_{k+1},\dots ,a_{k+50}\}$ với $k=1,2,\dots ,1950$. Rõ ràng $M_k$ không phải là một tập "co cụm bậc hai" nên ta có $a_k\le \frac{1}{2}{a}_{k+50}$ với mọi $k=1,2,\dots ,1950$.
Đặt $S_k=a_k+a_{k+50}+\cdots +a_{k+1950}$ với $k=1,2,\dots ,50$.
Theo chứng minh trên, ta có
$$a_{k+1900}\le \frac{1}{2}{a}_{k+1950}$$
$$a_{k+1850}\le \frac{1}{2}{a}_{k+1900}\le \frac{1}{2^2}{a}_{k+1950}$$
$$\dots$$
$$a_{k+50}\le \frac{1}{2}{a}_{k+100}\le \frac{1}{2^{38}}{a}_{k+1950}$$
$$a_k\le \frac{1}{2}{a}_{k+50}\le \frac{1}{2^{39}}{a}_{k+1950}$$

Suy ra
$$S_k\le \left(1+\frac{1}{2}+\frac{1}{2^2}+\cdots +\frac{1}{2^{39}}\right)a_{k+1950}=\left(\frac{1-1/2^{40}}{1-1/2}\right)a_{k+1950}$$
$$=\left(2-\frac{1}{2^{39}}\right)a_{k+1950}<2a_{k+1950}\le 2\cdot \frac{1}{100}=\frac{1}{50}.$$

Dẫn tới
$$\sum _{i=1}^{2000}{a}_i=\sum _{k=1}^{50}{S}_k<50\cdot \frac{1}{50}=1\text{(voˆ lyˊ)}.$$

Vậy điều giả sử là sai, do đó ta có đpcm. $\square$

Cách 2. Ta phân hoạch khoảng $\left(0,\frac{1}{100}\right]$ thành vô hạn các nửa khoảng rời nhau có dạng:

$$I_k=\left(\frac{1}{100\cdot 2^k},\frac{1}{100\cdot 2^{k-1}}\right]\text{với }k=1,2,\dots$$

Vì 2000 số đã cho đều dương và không vượt quá $\frac{1}{100}$, nên mỗi số thuộc đúng một khoảng $I_k$. Lấy hai số bất kỳ cùng thuộc một khoảng $I_k$, ta thấy tỉ số của chúng luôn nhỏ hơn 2 (do phần tử lớn hơn không vượt quá $\frac{1}{100\cdot 2^{k-1}}$, còn phần tử nhỏ hơn lại lớn hơn $\frac{1}{100\cdot 2^k}$). Do đó, các số nằm trong cùng một khoảng $I_k$ bất kỳ luôn tạo thành một tập "co cụm bậc hai".

Giả sử không có tập "co cụm bậc hai" nào gồm 51 phần tử. Khi đó, mỗi khoảng $I_k$ chứa tối đa 50 số.

Gọi $M$ là tập hợp gồm 2000 số đã cho và $n_k=|I_k\cap M|$ là số lượng phần tử của $M$ nằm trong khoảng $I_k$. Theo giả thiết phản chứng, ta có:

$$\{\begin{array}{l}\sum _{k=1}^{+\infty }{n}_k=2000\\ 0\le n_k\le 50,\forall k\in {\mathbb{Z}}^{+}\\ a\le \frac{1}{100\cdot 2^{k-1}},\forall a\in I_k\cap M\end{array}$$

Khi đó, tổng của 2000 số ban đầu được chặn trên như sau:

$$\sum _{a\in M}a=\sum _{k=1}^{+\infty }\left(\sum _{a\in I_k\cap M}a\right)\le \sum _{k=1}^{+\infty }{n}_k\cdot \frac{1}{100\cdot 2^{k-1}}$$

Đặt $c_k=\frac{1}{100\cdot 2^{k-1}}$. Với giả thiết $\{\begin{array}{l}0\le n_k\le 50\\ \sum _{k=1}^{+\infty }{n}_k=2000\end{array}$ và dãy $(c_k)$ giảm ngặt, ta có:

$$\sum _{k=1}^{40}50c_k-\sum _{k=1}^{+\infty }{n}_k{c}_k=\sum _{k=1}^{40}(50-n_k)c_k-\sum _{k=41}^{+\infty }{n}_k{c}_k$$
$$\ge c_{40}\sum _{k=1}^{40}(50-n_k)-c_{41}\sum _{k=41}^{+\infty }{n}_k$$
$$=c_{40}\left(2000-\sum _{k=1}^{40}{n}_k\right)-c_{41}\sum _{k=41}^{+\infty }{n}_k$$
$$=(c_{40}-c_{41})\sum _{k=41}^{+\infty }{n}_k\ge 0$$

Suy ra
$$\sum _{k=1}^{+\infty }{n}_k{c}_k\le \sum _{k=1}^{40}50c_k.$$

Dẫn tới:

$$\sum \text{caˊc soˆˊ}\le 50\left(\frac{1}{100}+\frac{1}{200}+\frac{1}{400}+\cdots +\frac{1}{100\cdot 2^{39}}\right)$$
$$=\frac{50}{100}\left(1+\frac{1}{2}+\frac{1}{2^2}+\cdots +\frac{1}{2^{39}}\right)$$
$$=\frac{1}{2}\left(\frac{1-1/2^{40}}{1-1/2}\right)=1-\frac{1}{2^{40}}<1\text{(voˆ lyˊ)}.$$

Vậy điều giả sử là sai. Suy ra phải có ít nhất một khoảng chứa từ 51 số trở lên, và chúng tạo thành tập "co cụm bậc hai" cần tìm. □

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}}$.

$■$

(AI giải đề cho tôi)
Đánh số 20 cây theo vòng tròn là $1,2,\dots ,20$. Cần chọn 4 cây trong 20 cây sao cho không có hai cây nào kề nhau trên vòng tròn. Số cách chọn $k$ phần tử từ $n$ phần tử xếp trên vòng tròn, đôi một không kề nhau, là $\frac{n}{n-k}\left(\genfrac{}{}{0ex}{}{n-k}{k}\right)$. Với $n=20,k=4$: $\frac{20}{16}\left(\genfrac{}{}{0ex}{}{16}{4}\right)=\frac{5}{4}\cdot 1820=2275$. Vậy có tất cả 2275 cách chặt bỏ 4 cây thoả mãn yêu cầ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.

Kí hiệu số nằm ở hàng $i$, cột $j$ là $a_{ij}$.

a) Với $n=3$ và $p=5$, xét bảng



Từ ô vuông $2\times 2$ phía trên bên trái, ta có $a=2$.

Tiếp theo, từ ô vuông $2\times 2$ phía trên bên phải, ta có $b=1$.

Hai ô vuông $2\times 2$ phía dưới cho ta $3\cdot 2\cdot c\cdot d\equiv 2\cdot 1\cdot d\cdot e\equiv 1(\mathrm{mod}5)$.

Vì thế $cd\equiv 1(\mathrm{mod}5)$ và $de\equiv 3(\mathrm{mod}5)$

Mặt khác, tích của sáu số ở hai hàng đầu là $4(\mathrm{mod}5)$.

Do tích của tất cả 9 số phải đồng dư với $-1\equiv 4(\mathrm{mod}5)$, ta được
$$4cde\equiv 4(\mathrm{mod}5),$$
hay $cde\equiv 1(\mathrm{mod}5)$. Kết hợp với $cd\equiv 1(\mathrm{mod}5)$ suy ra $e=1$, $d=3$, $c=2$.



b) Trước hết, ta nhận xét rằng nếu biết các số trên hàng đầu tiên và cột đầu tiên thì toàn bộ bảng được xác định duy nhất. Thật vậy, giả sử đã biết ba số $a_{i-1,j-1}$, $a_{i-1,j}$ và $a_{i,j-1}$.

Điều kiện đối với ô vuông $2\times 2$ tương ứng với
$$a_{i-1,j-1}{a}_{i-1,j}{a}_{i,j-1}{a}_{ij}\equiv 1(\mathrm{mod}p).$$
Vì ba số đã biết đều khác 0 modulo $p$, số $a_{ij}$ được xác định duy nhất modulo $p$, cụ thể
$$a_{ij}\equiv {\left(a_{i-1,j-1}{a}_{i-1,j}{a}_{i,j-1}\right)}^{-1}(\mathrm{mod}p).$$

Bắt đầu từ hàng đầu tiên và cột đầu tiên, ta lần lượt xác định hàng thứ hai từ trái sang phải, sau đó hàng thứ ba, và cứ tiếp tục như vậy. Do đó $2n-1$ số trên hàng đầu tiên và cột đầu tiên xác định duy nhất cả bảng.

Bây giờ ta xét tích của tất cả các số trên bảng. Đặt
$$B_j=\prod _{i=2}^n{a}_{ij}$$

Với hai cột liên tiếp $j$ và $j+1$, nhân các điều kiện của những ô vuông $2\times 2$ có hai hàng lần lượt là
$$(2,3),(4,5),\dots ,(n-1,n),$$
ta được ${\prod }_{i=2}^n{a}_{ij}{a}_{i,j+1}\equiv 1(\mathrm{mod}p)$ hay $B_j{B}_{j+1}\equiv 1(\mathrm{mod}p)$, do đó
$$B_2\equiv B_1^{-1},B_3\equiv B_1,B_4\equiv B_1^{-1},\dots$$

Vì $n$ lẻ nên $B_1{B}_2\cdots B_n\equiv B_1(\mathrm{mod}p)$ nên tích $n^2$ số trên bảng là
$$\prod _{i=1}^n\prod _{j=1}^n{a}_{ij}=\left(\prod _{j=1}^n{a}_{1j}\right)\left(\prod _{j=1}^n{B}_j\right)=\left(\prod _{j=1}^n{a}_{1j}\right)B_1=\left(\prod _{j=1}^n{a}_{1j}\right)\left(\prod _{i=2}^n{a}_{i1}\right)(\mathrm{mod}p).$$

Như vậy, điều kiện tích của tất cả các số trên bảng đồng dư với $-1$ chính là điều kiện tích của $2n-1$ số nằm trên hàng đầu tiên và cột đầu tiên đồng dư với $-1$ modulo $p$.

Ta chọn tùy ý $2n-2$ trong $2n-1$ số này. Mỗi số có $p-1$ cách chọn, nên có $(p-1{)}^{2n-2}$ cách chọn. Sau khi đã chọn $2n-2$ số, số còn lại được xác định duy nhất bởi yêu cầu tích của cả $2n-1$ số phải đồng dư với $-1$ modulo $p$. Vì tích của $2n-2$ số đã chọn khác 0 modulo $p$, số còn lại cũng khác 0 và do đó thuộc duy nhất một giá trị trong $\{1,2,\dots ,p-1\}$.

Với mỗi cách chọn như trên, toàn bộ các ô còn lại của bảng lại được xác định duy nhất bởi điều kiện trên các ô vuông $2\times 2$.

Vậy số lượng bảng TPDN bằng $\boxed{(p-1{)}^{2n-2}}$

Gọi bốn bạn nam là $B_1,B_2,B_3,B_4$ và bốn bạn nữ là $G_1,G_2,G_3,G_4$.

Với mỗi cặp $(G_i,B_j)$, do $G_i$ và $B_j$ cùng tham gia ít nhất một dự án, ta chọn một dự án mà cả hai cùng tham gia và ghi tên dự án đó vào ô $(i,j)$ của một bảng $4\times 4$.

Vì mỗi người tham gia tối đa 2 dự án nên trong mỗi hàng và mỗi cột của bảng có không quá 2 tên dự án khác nhau. Giả sử ngược lại rằng không có dự án nào có đồng thời ít nhất 2 bạn nam và ít nhất 2 bạn nữ. Khi đó, với mỗi dự án $D$, ta tô màu cho $D$ theo quy tắc:

- Tô xanh nếu $D$ có nhiều nhất 1 bạn nam.
- Nếu $D$ không được tô xanh, thì $D$ có ít nhất 2 bạn nam, nên theo giả sử phản chứng, $D$ có nhiều nhất 1 bạn nữ; khi đó tô $D$ màu hồng.

Như vậy mỗi dự án được gán đúng một màu, và mỗi ô của bảng mang màu của dự án được ghi trong ô đó. Bảng có 16 ô, nên theo nguyên lý Dirichlet, một trong hai màu xuất hiện ít nhất 8 lần.

Trường hợp 1: Có ít nhất 8 ô màu xanh.

Trong một hàng cố định, không thể có 3 ô màu xanh. Thật vậy, ba ô ấy nằm ở ba cột khác nhau, tức là liên quan đến ba bạn nam khác nhau. Vì một dự án màu xanh có nhiều nhất 1 bạn nam, nên ba ô xanh đó phải mang ba tên dự án khác nhau. Khi ấy bạn nữ tương ứng với hàng đó tham gia ít nhất 3 dự án, trái với giả thiết.

Vậy mỗi hàng có nhiều nhất 2 ô xanh. Nhưng tổng số ô xanh ít nhất là 8, nên cả bốn hàng đều có đúng 2 ô xanh.

Xét một hàng bất kỳ. Hai ô xanh trong hàng ấy phải mang hai tên dự án khác nhau. Hai ô còn lại là màu hồng; lấy một trong hai ô hồng đó. Dự án ghi trong ô hồng khác với cả hai dự án ở hai ô xanh, vì mỗi dự án đã được gán một màu duy nhất. Do đó bạn nữ của hàng này tham gia ít nhất 3 dự án, lại mâu thuẫn.

Trường hợp 2: Có ít nhất 8 ô màu hồng.

Lập luận hoàn toàn tương tự theo các cột. Trong một cột có đỉnh, không thể có 3 ô màu hồng, vì một dự án màu hồng có nhiều nhất 1 bạn nữ; do đó ba ô hồng ở ba hàng khác nhau phải tương ứng với ba dự án khác nhau, khiến bạn nam của cột ấy tham gia ít nhất 3 dự án.

Vì thế mỗi cột có nhiều nhất 2 ô hồng. Tổng số ô hồng ít nhất là 8, nên mỗi cột có đúng 2 ô hồng. Trong một cột, hai ô hồng tương ứng với hai dự án khác nhau, còn một ô xanh bất kỳ trong cột tương ứng với một dự án khác hai dự án ấy. Suy ra bạn nam của cột đó tham gia ít nhất 3 dự án, mâu thuẫn.

Cả hai trường hợp đều dẫn đến mâu thuẫn. Vậy giả sử phản chứng là sai.
Do đó tồn tại ít nhất một dự án có từ 2 bạn nam và 2 bạn nữ trở lên cùng tham gia.

Nhận xét.
Bằng lập luận tương tự, ta có thể tổng quát bài toán như sau: Với các số nguyên $a,b>1$, giả sử có $2(a-1)(b-1)+2$ bạn nam và $2(a-1)(b-1)+2$ bạn nữ tham gia, mỗi người tham gia không quá $a$ dự án. Khi đó, tồn tại ít nhất một dự án có $b$ bạn nam và $b$ bạn nữ trở lên cùng tham gia. Trường hợp $a=6$, $b=3$ ta được P3 IMO 2001.

a) Nếu $n$ không là số chính phương thì các ước của $n$ ghép thành các cặp $d,\frac{n}{d}$ nằm ở hai phía của $\sqrt{n}$. Vì thế $\tau (n)\le 2\lfloor \sqrt{n}\rfloor <2\sqrt{n}$.
Còn nếu $n$ là số chính phương thì $\sqrt{n}$ là ước không được ghép cặp, nên $\tau (n)\le 2\sqrt{n}-1<2\sqrt{n}$.
b) Ta sẽ chứng minh một số nguyên dương $m$ có dãy $m,\tau (m),\tau (\tau (m)),\dots$ không chứa số chính phương khi và chỉ khi $m$ là số nguyên tố.
Nếu $m$ là số nguyên tố thì $\tau (m)=2$ và $\tau (2)=2$ nên thoả mãn.
Giả sử $m$ là hợp số và dãy trên không chứa số chính phương. Khi đó $m$ không chính phương, nên $\tau (m)$ là số chẵn và $\tau (m)\ge 4$. Nếu $\tau (m)$ không chính phương thì nó lại là một hợp số. Hơn nữa, với mọi hợp số $m\ge 4$, câu a) cho ta $\tau (m)<2\sqrt{m}\le m$. Bởi vậy, nếu dãy không có số chính phương nào thì ta thu được một dãy giảm nghiêm ngặt gồm các hợp số, điều không thể xảy ra. Suy ra $m$ phải là số nguyên tố.
Áp dụng kết luận này cho $m=\tau (n)$, điều kiện bài toán tương đương với $\tau (n)$ là số nguyên tố.
Viết $n=q_1^{{\alpha }_1}\cdots q_t^{{\alpha }_t}$, ta có $\tau (n)=({\alpha }_1+1)\cdots ({\alpha }_t+1)$.
Tích này là số nguyên tố khi và chỉ khi $t=1$ và ${\alpha }_1+1$ là số nguyên tố.
Vậy tất cả các số cần tìm là $n=q^{p-1}$ trong đó $p,q$ là các số nguyên tố.

Đầu tiên ta có bổ đề sau:
Bổ đề: Trong một bảng $r\times s$ gồm các số $0,1$, giả sử mọi bảng con $2\times 2$ gồm hai hàng liên tiếp và hai cột liên tiếp đều có tổng ít nhất bằng 2. Khi đó số các số 1 trong bảng không nhỏ hơn
$$\min \left\{s\lfloor \frac{r}{2}\rfloor ,r\lfloor \frac{s}{2}\rfloor \right\}.$$
Chứng minh. Trước hết, xét một bảng $2\times s$. Với $1\le j\le s$, gọi $c_j$ là tổng các phần tử của cột thứ $j$. Theo giả thiết, ta có $c_j+c_{j+1}\ge 2$ với mọi $1\le j\le s-1$.
Ghép các cột thành các cặp liên tiếp $(1,2),(3,4),\dots$ ta được $$\sum _{j=1}^s{c}_j\ge 2\lfloor \frac{s}{2}\rfloor .$$
Do đó một bảng $2\times s$ như trên có ít nhất $2\lfloor s/2\rfloor$ số 1.
Trong trường hợp $s$ lẻ, giả sử $s=2k+1$ và bảng có đúng $2k$ số 1. Khi đó
$$(c_1+c_2)+(c_3+c_4)+\cdots +(c_{2k-1}+c_{2k})+c_{2k+1}=2k.$$
Mỗi tổng trong $k$ dấu ngoặc đều không nhỏ hơn 2, nên bắt buộc
$$c_{2k+1}=0,c_{2i-1}+c_{2i}=2$$
với mọi $1\le i\le k$. Từ $c_{2k}+c_{2k+1}\ge 2$ và $c_{2k+1}=0$, suy ra $c_{2k}=2$, do đó $c_{2k-1}=0$. Do đó
$$(c_1,c_2,\dots ,c_{2k+1})=(0,2,0,2,\dots ,0,2,0).$$
Vì mỗi cột chẵn chứa hai số 1, còn mỗi cột lẻ chỉ chứa các số 0, nên mỗi hàng của bảng có đúng $k$ số 1.
Bây giờ trở lại bảng $r\times s$ ban đầu. Nếu $r$ chẵn, ta ghép các hàng thành các cặp liên tiếp. Mỗi cặp hàng tạo thành một bảng $2\times s$, nên chứa ít nhất $2\lfloor s/2\rfloor$ số 1. Vì có $r/2$ cặp hàng, toàn bảng có ít nhất
$$\frac{r}{2}\cdot 2\lfloor \frac{s}{2}\rfloor =r\lfloor \frac{s}{2}\rfloor$$
số 1. Tương tự, nếu $s$ chẵn thì ghép các cột thành từng cặp liên tiếp, ta được ít nhất $s\lfloor \frac{r}{2}\rfloor$ số 1.
Như vậy, bổ đề đúng nếu $r$ hoặc $s$ chẵn.
Ta chỉ còn xét trường hợp $r=2h+1$, $s=2k+1$.
Không mất tính tổng quát, giả sử $h\le k$. Khi đó $\min \{(2k+1)h,(2h+1)k\}=(2k+1)h$.
Ta sẽ chứng minh bằng quy nạp theo $h$ rằng bảng có ít nhất $h(2k+1)$ số 1.
Với $h=0$, khẳng định hiển nhiên. Giả sử $h\ge 1$ và khẳng định đã đúng với $h-1$.
Gọi $t$ là số các số 1 trên hàng đầu tiên.
Nếu $t\ge h$, ta bỏ hàng đầu tiên. Phần còn lại là một bảng $2h\times (2k+1)$. Theo trường hợp số hàng chẵn đã chứng minh, bảng này có ít nhất $2h\lfloor \frac{2k+1}{2}\rfloor =2hk$ số 1.
Vì thế bảng ban đầu có ít nhất $2hk+h=h(2k+1)$ số 1.
Nếu $t\le h-1$, xét bảng $2\times (2k+1)$ tạo bởi hai hàng đầu tiên.
Theo kết quả ở đầu chứng minh, hai hàng này có ít nhất $2k$ số 1.
Nếu chúng có đúng $2k$ số 1, thì theo trường hợp đầu bảng đã xét, mỗi hàng phải có đúng $k$ số 1. Đặc biệt, hàng đầu tiên có đúng $k$ số 1, mâu thuẫn với $t\le h-1<k$ do $h\le k$. Vì vậy, hai hàng đầu tiên phải chứa ít nhất $2k+1$ số 1.
Bỏ hai hàng đầu tiên, ta còn lại một bảng
$$(2h-1)\times (2k+1)=(2(h-1)+1)\times (2k+1).$$
Vì $h-1\le k$, theo giả thiết quy nạp, bảng còn lại có ít nhất $(h-1)(2k+1)$ số 1. Do đó toàn bảng có ít nhất $(2k+1)+(h-1)(2k+1)=h(2k+1)$ số 1.
Cuối cùng, ta chứng minh cận dưới này đạt được. Nếu điền số 1 vào toàn bộ các vị trí thuộc các hàng có chỉ số chẵn và điền số 0 vào các vị trí còn lại, thì mỗi cặp hàng liên tiếp chứa đúng một hàng toàn số 1. Vì vậy, mỗi bảng con $2\times 2$ gồm hai hàng liên tiếp và hai cột liên tiếp có đúng hai số 1. Tổng số các số 1 trong cách điền này là $s\lfloor \frac{r}{2}\rfloor$.
Tương tự, nếu điền số 1 vào toàn bộ các cột có chỉ số chẵn và điền số 0 vào các vị trí còn lại, ta thu được một bảng thỏa mãn giả thiết và có $r\lfloor \frac{s}{2}\rfloor$ số 1. Chọn cách điền tương ứng với số nhỏ hơn trong hai số trên, ta thấy cận dưới đạt được. Vậy số các số 1 ít nhất là
$$\min \left\{s\lfloor \frac{r}{2}\rfloor ,r\lfloor \frac{s}{2}\rfloor \right\}.$$

Trở lại bài toán ban đầu:
Một khu vườn gồm $m\times n$ ô vuông đơn vị có $(m+1)\times (n+1)$ đỉnh. Ta xem các đỉnh này như một bảng gồm các số 0, 1, số 1 biểu thị đỉnh có đặt bóng điện, còn số 0 biểu thị đỉnh không đặt bóng điện. Khi đó bốn đỉnh của mỗi ô vuông đơn vị tạo thành một bảng con $2\times 2$ gồm hai hàng liên tiếp, hai cột liên tiếp.
a) Khu vườn có $2025\times 2026$ ô vuông đơn vị.
Xét các ô vuông nằm trên các hàng $1,3,5,\dots ,2025$ và các cột $1,3,5,\dots ,2025$, có tất cả
$$1013\cdot 1013=1013^2$$
ô vuông như vậy. Hai ô bất kỳ trong số này không có đỉnh chung. Vì mỗi ô phải có ít nhất một đỉnh được đặt bóng điện, nên các bóng điện chiếu sáng các ô trên phải đôi một khác nhau.
Do đó cần ít nhất $1013^2$ bóng điện.
Ta chứng minh cận dưới này đạt được. Đánh số các hàng đỉnh từ 1 đến 2026 và các cột đỉnh từ 1 đến 2027. Đặt bóng tại tất cả các đỉnh là giao điểm của một hàng đỉnh chẵn và một cột đỉnh chẵn.
Trong hai hàng đỉnh liên tiếp có đúng một hàng chẵn, và trong hai cột đỉnh liên tiếp có đúng một cột chẵn nên mỗi ô vuông đơn vị có đúng một đỉnh được đặt bóng điện, nên toàn bộ khu vườn được chiếu sáng. Số hàng đỉnh chẵn và số cột đỉnh chẵn bằng 1013, nên số bóng điện được dùng là $1013^2$.
Vậy số bóng điện ít nhất cần dùng là $1013^2$.
b) Để khu vườn vẫn được chiếu sáng khi một bóng điện bất kỳ bị cháy, mỗi ô vuông đơn vị phải có ít nhất hai đỉnh được đặt bóng điện. Thật vậy, nếu một ô chỉ có đúng một bóng điện thì khi bóng điện đó bị cháy, ô ấy sẽ không còn được chiếu sáng. Ngược lại, nếu mỗi ô có ít nhất hai bóng điện thì sau khi một bóng bất kỳ bị cháy, mỗi ô vẫn còn ít nhất một bóng hoạt động.
Bảng các đỉnh của khu vườn có kích thước $2026\times 2027$.
Điều kiện trên tương đương với việc mọi bảng con $2\times 2$ gồm hai hàng liên tiếp và hai cột liên tiếp đều có tổng ít nhất bằng 2.
Áp dụng bổ đề với $r=2026$ và $s=2027$, số bóng điện không nhỏ hơn
$$\min \left\{2027\lfloor \frac{2026}{2}\rfloor ,2026\lfloor \frac{2027}{2}\rfloor \right\}=2026\cdot 1013=2\cdot 1013^2$$
Theo trường hợp dấu bằng trong bổ đề, cận này đạt được bằng cách đặt bóng điện tại toàn bộ các đỉnh thuộc các cột đỉnh có chỉ số chẵn.
Vậy số bóng điện ít nhất cần dùng là $2\cdot 1013^2$.
c) Khi mở rộng khu vườn thành bảng $2026\times 2026$, bảng các đỉnh có kích thước $2027\times 2027$.
Tương tự câu trên và áp dụng bổ đề với $r=s=2027$, số bóng điện không nhỏ hơn
$$\min \left\{2027\lfloor \frac{2027}{2}\rfloor ,2027\lfloor \frac{2027}{2}\rfloor \right\}=2027\cdot 1013.$$
Theo trường hợp dấu bằng trong bổ đề, cận này đạt được bằng cách đặt bóng điện tại toàn bộ các đỉnh thuộc các hàng đỉnh có chỉ số chẵn hoặc toàn bộ các đỉnh thuộc các cột đỉnh có chỉ số chẵn.
Vậy số bóng điện ít nhất cần dùng là $2027\cdot 1013$.

Ta gọi các giao điểm của các đường kẻ trong bảng là các đỉnh lưới.

Bảng $n\times n$ có tất cả $(n+1{)}^2$ đỉnh lưới.

Mỗi quân đôminô phủ một hình chữ nhật kích thước $1\times 2$, do đó chứa đúng 6 đỉnh lưới.

Vì hai quân đôminô bất kỳ không có điểm chung (kể cả ở đỉnh), nên 6 đỉnh lưới thuộc hai quân khác nhau cũng đôi một phân biệt. Bởi vậy, nếu xếp được 661 quân thì:

$$6\cdot 661\le (n+1{)}^2.$$

Từ đây suy ra được $n+1\ge 63$ hay $n\ge 62$.

Để chỉ ra $n=62$ thoả mãn, ta xếp như sau:



Trên mỗi hàng thuộc tập hợp $\{1,3,5,\dots ,59\}$, ta đặt các quân đôminô nằm ngang phủ các cặp cột:

$$(1,2),(4,5),(7,8),\dots ,(61,62)$$

Có 30 hàng được chọn và trên mỗi hàng có 21 quân, nên ta đặt được 630 quân đôminô.

Trên hai hàng 61 và 62, ta đặt 31 quân đôminô thẳng đứng tại các cột: $1,3,5,\dots ,61$.

Cách sắp xếp trên cho ta 661 quân đôminô, do đó giá trị nhỏ nhất của $n$ bằng 62.

Kết luận: $n_{\min }=62$

Gọi $N$ là số học sinh đã xuất hiện trong ít nhất một lần họp mặt.
Với mỗi học sinh $s$, gọi $a_s$ là số lần họp mặt mà học sinh đó tham dự.
Tổng số lượt tham dự là ${\sum }_s{a}_s=10\cdot 20=200$.
Mỗi học sinh xuất hiện trong $a_s$ lần tạo ra $C_{a_s}^2$ cặp lần họp mặt có chung học sinh ấy.
Vì mỗi cặp trong $C_{10}^2=45$ cặp lần họp mặt có chung không quá 2 người nên ${\sum }_s{C}_{a_s}^2\le 2C_{10}^2=90$.
Với mọi số nguyên $a_s\ge 1$, ta có $C_{a_s}^2\ge a_s-1$ nên $200-N={\sum }_s(a_s-1)\le {\sum }_s{C}_{a_s}^2\le 90$.
Do đó $N\ge 110$. Ta sẽ chỉ ra đây chính là giá trị nhỏ nhất của $N$.
Đánh số các lần họp mặt từ 1 đến 10, với mỗi cặp $\{i,j\}$, đúng 2 học sinh chỉ tham dự hai lần $i$ và $j$ để có $2C_{10}^2=90$ học sinh loại này, hơn nữa với mỗi lần $i$, thêm 2 học sinh chỉ tham dự lần $i$ để có thêm 20 học sinh. Ở lần $i$, có $2\cdot 9=18$ học sinh gắn với 9 cặp $\{i,j\}$ và 2 học sinh riêng, tổng cộng đúng 20 người. Hai lần bất kỳ có chung đúng hai học sinh. Vậy trường hợp 110 học sinh này thỏa mãn mọi yêu cầu.
Vậy khối 12 năm học đó có ít nhất 110 học sinh.

Lời giải (Lim Olympic - Nghệ An TST - P4).

a) Vì $(a,b)=1$ nên mỗi ước dương của $ab$ biểu diễn duy nhất dưới dạng $uv$ với $u\mid a$ và $v\mid b$. Vì thế

$${\sigma }_k(ab)=\sum _{u\mid a}\sum _{v\mid b}(uv{)}^k=\left(\sum _{u\mid a}{u}^k\right)\left(\sum _{v\mid b}{v}^k\right)={\sigma }_k(a){\sigma }_k(b).$$

Ta chứng minh rằng từ mỗi số tốt $m>1$ luôn xây dựng được một số tốt $m^{\prime }>m$ sao cho $m\mid m^{\prime }$. Nếu tồn tại một số nguyên tố $q\mid {\sigma }_k(m)$ nhưng $q\nmid m$, đặt $m^{\prime }=mq$. Do $(m,q)=1$, ta có

$${\sigma }_k(m^{\prime })={\sigma }_k(m)(1+q^k).$$

Mặt khác, $m\mid {\sigma }_k(m)$, $q\mid {\sigma }_k(m)$ và $(m,q)=1$, nên $mq\mid {\sigma }_k(m)$. Bởi vậy $m^{\prime }$ là số tốt.

Xét trường hợp mọi ước nguyên tố của ${\sigma }_k(m)$ đều là ước của $m$. Viết

$$m=\prod _{i=1}^s{p}_i^{a_i},{\sigma }_k(m)=\prod _{i=1}^s{p}_i^{b_i}.$$

Do $m\mid {\sigma }_k(m)$ nên $b_i\ge a_i$ với mọi $i$. Lại có ${\sigma }_k(m)>m^k$, nên tồn tại $j$ sao cho $b_j>k{a}_j$. Đặt

$$m^{\prime }=p_j^{a_j+1}m.$$

Ta có $v_{p_j}(m^{\prime })=2a_j+1$ nên

$${\sigma }_k(m^{\prime })=\left(\sum _{h=0}^{2a_j+1}{p}_j^{hk}\right)\prod _{i\ne j}{\sigma }_k(p_i^{a_i})=\left(1+p_j^{(a_j+1)k}\right)\left(\sum _{h=0}^{a_j}{p}_j^{hk}\right)\prod _{i\ne j}{\sigma }_k(p_i^{a_i})=\left(1+p_j^{(a_j+1)k}\right){\sigma }_k(m).$$

Vì $b_j\ge k{a}_j+1\ge 2a_j+1$ và $b_i\ge a_i$ với $i\ne j$, ta có $m^{\prime }\mid {\sigma }_k(m)$.

Suy ra $m^{\prime }\mid {\sigma }_k(m^{\prime })$, nên $m^{\prime }$ cũng là số tốt.

Bây giờ lấy một ước nguyên tố lẻ $p$ của $2^k+1$. Khi đó

$${\sigma }_k(2p)=(1+2^k)(1+p^k).$$

Ta có $p\mid 1+2^k$ và $2\mid 1+p^k$, nên $2p\mid {\sigma }_k(2p)$. Do đó $n_1=2p$ là số tốt. Áp dụng liên tiếp ta thu được dãy vô hạn các số tốt $n_1<n_2<\cdots$ thỏa mãn $n_i\mid n_{i+1}$.

b) Từ ý trên, ta chỉ cần chứng minh nhận xét sau là bài toán được giải quyết:

Nhận xét. Với tập hữu hạn $\mathcal{P}\subset \mathbb{P}$, chỉ có hữu hạn số tốt mà mọi ước nguyên tố đều thuộc $\mathcal{P}$.

Đầu tiên ta chứng minh bổ đề sau:

Bổ đề 0.2. Với hai số nguyên tố phân biệt $p,q$, tồn tại hằng số $C_{p,q}$ sao cho

$$v_p\left({\sigma }_k(q^a)\right)\le C_{p,q}+{\log }_2(a+1),\forall a\ge 0$$

Chứng minh. Ta có ${\sigma }_k(q^a)=\frac{q^{k(a+1)}-1}{q^k-1}$

Nếu $p$ lẻ, đặt $d={\mathrm{ord}}_p(q^k)$. Khi đó $d\mid p-1$, nên $p\nmid d$.

Nếu $d\nmid a+1$ thì $p\nmid q^{k(a+1)}-1$, do đó $v_p\left({\sigma }_k(q^a)\right)=0$.

Nếu $d\mid a+1$, áp dụng LTE ta có

$$v_p\left(q^{k(a+1)}-1\right)=v_p\left(q^{kd}-1\right)+v_p\left(\frac{a+1}{d}\right).$$

Vì $p\nmid d$ nên $v_p\left(\frac{a+1}{d}\right)=v_p(a+1)\le {\log }_2(a+1)$.

Mặt khác, ${\sigma }_k(q^a)\mid q^{k(a+1)}-1$, nên

$$v_p\left({\sigma }_k(q^a)\right)\le v_p\left(q^{kd}-1\right)+{\log }_2(a+1).$$

trong đó $v_p(q^{kd}-1)$ là một hằng số chỉ phụ thuộc vào $p,q$.

Nếu $p=2$ thì $q$ lẻ. Nếu $a+1$ lẻ, ${\sigma }_k(q^a)$ là tổng của một số lẻ các số lẻ, nên $v_2\left({\sigma }_k(q^a)\right)=0$.

Nếu $a+1$ chẵn, áp dụng LTE ta có

$$v_2\left(q^{k(a+1)}-1\right)=v_2(q^k-1)+v_2(q^k+1)+v_2(a+1)-1.$$

Vì thế

$$v_2\left({\sigma }_k(q^a)\right)=v_2(q^k+1)+v_2(a+1)-1\le v_2(q^k+1)-1+{\log }_2(a+1).$$

trong đó $v_2(q^k+1)-1$ là một hằng số chỉ phụ thuộc vào $q$.

Như vậy, trong mọi trường hợp đều tồn tại hằng số $C_{p,q}$ sao cho

$$v_p\left({\sigma }_k(q^a)\right)\le C_{p,q}+{\log }_2(a+1).$$
$\square$

Để ý ta chỉ cần xét các số tốt có cùng một tập ước nguyên tố là $\{p_1,\dots ,p_s\}\subset \mathcal{P}$ và

$$n=\prod _{i=1}^s{p}_i^{a_i}$$

là một số tốt. Đặt $M=\max \{a_1,\dots ,a_s\}$. Vì ${\sigma }_k(p_i^{a_i})\equiv 1(\mathrm{mod}{p}_i)$ nên $p_i\nmid {\sigma }_k(p_i^{a_i})$ nên

$$a_i=v_{p_i}(n)\le v_{p_i}\left({\sigma }_k(n)\right)=\sum _{j\ne i}{v}_{p_i}\left({\sigma }_k(p_j^{a_j})\right)\le \sum _{j\ne i}{C}_{p_i,p_j}+(s-1){\log }_2(M+1).$$

Đặt $C_i={\sum }_{j\ne i}{C}_{p_i,p_j}$ và $C=\max \{C_1,\dots ,C_s\}$. Chọn $i\in \{1,2,\dots ,s\}$ sao cho $a_i=M$, ta được

$$M\le C+(s-1){\log }_2(M+1).$$

Để ý với $M$ đủ lớn thì $C+(s-1){\log }_2(M+1)<M$, do đó $M$ bị chặn.

Vì thế các số mũ $a_1,\dots ,a_s$ chỉ có hữu hạn giá trị. Suy ra chỉ có hữu hạn số tốt mà mọi ước nguyên tố đều thuộc $\mathcal{P}$, từ đó ta có điều phải chứng minh.