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)

(AI giải đề cho tôi)
Tổ có $5$ học sinh nữ và $6$ học sinh nam, tổng cộng $5+6=11$ học sinh. Chọn ngẫu nhiên $1$ học sinh đi trực nhật có đúng $11$ cách (quy tắc cộng). Đáp án khớp với nguồn: B.

(AI giải đề cho tôi)
Chọn 3 em có nhiều nhất 1 nam: hoặc 0 nam 3 nữ, hoặc 1 nam 2 nữ. Số cách = $C_{15}^3+C_{20}^1\cdot C_{15}^2=455+20\cdot 105=455+2100=2555$. Vậy đáp án A.

(AI giải đề cho tôi)
a) Đúng: chọn 5 trong 11 học sinh là $C_{11}^5=462$ cách. b) Đúng: chọn 5 người có cả nam và nữ = tổng trừ trường hợp toàn nam hoặc toàn nữ: $C_{11}^5-C_6^5-C_5^5=462-6-1=455$ cách. c) Sai: chọn 5 người có ít nhất một nữ = $C_{11}^5-C_6^5=462-6=456$ cách (không phải 455). d) Sai: chọn 2 nữ trong 4 nữ còn lại: $C_4^2=6$; xếp 2 nữ đó vào giữa An và Vui: $2!=2$; thứ tự An–Vui trong khối: 2 cách; khi đó khối (An, 2 nữ, Vui) cùng 9 học sinh còn lại tạo thành 10 đối tượng xếp hàng: $10!$ cách. Tổng: $6\cdot 2\cdot 2\cdot 10!=24\cdot 3628800=87091200$ cách, khác 967.680.
a) (AI giải đề cho tôi)
Chọn 5 học sinh tùy ý từ 11 học sinh: $C_{11}^5=462$ cách.
b) (AI giải đề cho tôi)
Có cả nam và nữ: $C_{11}^5-C_6^5-C_5^5=462-6-1=455$ cách.
c) (AI giải đề cho tôi)
Ít nhất một nữ: $C_{11}^5-C_6^5=462-6=456$ cách, không phải 455.
d) (AI giải đề cho tôi)
Số cách là $C_4^2\cdot 2!\cdot 2\cdot 10!=87091200$ cách, khác 967.680.

(AI giải đề cho tôi)
Điều kiện: $n\ge 1$ (để $C_{n+2}^2$ và $A_{n+1}^1$ xác định).

Ta có $C_{n+2}^2=\frac{(n+2)(n+1)}{2}$ và $A_{n+1}^1=n+1$.

Phương trình trở thành:
$$5\cdot \frac{(n+2)(n+1)}{2}-(n+1)=319$$
$$\iff (n+1)\left(\frac{5(n+2)}{2}-1\right)=319\iff (n+1)(5n+8)=638.$$

Thử $n=10$: $(11)(58)=638$ thỏa mãn.

Xét phương trình $5n^2+13n-630=0$: $\Delta =13^2+4\cdot 5\cdot 630=12769=113^2$, nên $n=\frac{-13+113}{10}=10$ (nhận, $n\ge 1$) hoặc $n=\frac{-13-113}{10}=-12,6$ (loại).

Vậy $n=10$.

(AI giải đề cho tôi)
Gộp hai chữ số 1 và 2 đứng cạnh nhau thành một khối. Khối này có 2 cách xếp thứ tự bên trong (12 hoặc 21) và có 4 vị trí có thể đặt trong dãy 5 chữ số. Ba chữ số còn lại được chọn và xếp từ 5 chữ số còn lại của tập $\{0,3,4,5,6\}$.

- Tổng số cách khi chưa loại trừ trường hợp chữ số 0 đứng đầu: $2\cdot 4\cdot A_5^3=2\cdot 4\cdot 60=480$.
- Loại các số có chữ số 0 đứng đầu: khi đó khối (1,2) không thể ở vị trí đầu (vì 0 chiếm chỗ đầu), nên khối ở một trong 3 vị trí còn lại; chữ số đầu là 0, chọn và xếp 2 chữ số từ 4 chữ số còn lại: $2\cdot 3\cdot A_4^2=2\cdot 3\cdot 12=72$.

Vậy số số tự nhiên thỏa mãn là $480-72=408$ số.

Kiểm tra lại bằng cách đếm trực tiếp: khối ở vị trí đầu: $2\cdot A_5^3=120$; khối ở 3 vị trí sau (chữ số đầu khác 0, khác 1, 2): $2\cdot 3\cdot 4\cdot A_4^2=288$. Tổng $120+288=408$, khớp kết quả.

(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.

(AI giải đề cho tôi)
Chọn 3 học sinh sao cho mỗi khối có đúng 1 học sinh: chọn 1 trong 7 học sinh khối 12, 1 trong 6 học sinh khối 11 và 1 trong 5 học sinh khối 10. Theo quy tắc nhân, số cách chọn là $7\cdot 6\cdot 5=210$. Vậy đáp án là B.

(AI giải đề cho tôi)
Xem mỗi nhóm sách cùng môn như một 'khối'. Có $3!=6$ cách hoán vị 3 khối (Toán, Lý, Hóa). Trong mỗi khối, các sách khác nhau xếp được: Toán $5!=120$, Lý $3!=6$, Hóa $4!=24$ cách. Tổng: $3!\cdot 5!\cdot 3!\cdot 4!=6\cdot 120\cdot 6\cdot 24=103680$. Vậy chọn D.

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.

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

Quy ước các chỉ số theo modulo $n$. Với mỗi cách bố trí $x=(x_1,x_2,\dots ,x_n)$, đặt $x_i=1$ nếu đèn thứ $i$ sáng và $x_i=0$ nếu đèn thứ $i$ tắt. Khi đó $s_i=x_i+x_{i+1}+\cdots +x_{i+k-1}$.

a) Ta chứng minh điều kiện cần và đủ là $\gcd (n,k)=1$.

Trước hết, giả sử $d=\gcd (n,k)>1$. Xét cấu hình $x$ trong đó đúng các đèn có chỉ số đồng dư 1 modulo $d$ sáng, và cấu hình $y$ trong đó đúng các đèn có chỉ số đồng dư 2 modulo $d$ sáng. Trong $k$ vị trí liên tiếp, mỗi lớp đồng dư modulo $d$ xuất hiện đúng $k/d$ lần. Vì thế cả hai cấu hình đều cho $s_i=k/d$ với mọi $i$. Hai cấu hình khác nhau nhưng có cùng bản ghi, nên ta loại trường hợp này.

Ngược lại, giả sử $\gcd (n,k)=1$. Từ bản ghi, ta có $s_{i+1}-s_i=x_{i+k}-x_i$. Do $\gcd (n,k)=1$, dãy chỉ số $1,1+k,1+2k,\dots ,1+(n-1)k$ modulo $n$ đi qua tất cả các vị trí. Bắt đầu từ $x_1$ và dùng liên tiếp các đẳng thức trên, ta biểu diễn được $x_i=x_1+C_i$ với mọi $i$, trong đó mỗi $C_i$ hoàn toàn được xác định bởi bản ghi.

Thay vào $s_1=x_1+x_2+\cdots +x_k$, ta được $k{x}_1+C=s_1$, trong đó $C=C_1+C_2+\cdots +C_k$ đã biết. Vì $k>0$, giá trị $x_1$ được xác định duy nhất nên $x_1,x_2,\dots ,x_n$ cũng được xác định duy nhất.

Vậy điều kiện cần và đủ là $\gcd (n,k)=1$.

b) Đặt $d=\gcd (n,k)$, viết $n=dm$ và $k=dq$. Xét hai cấu hình $x,y$ và đặt $c_i=x_i-y_i$. Hai cấu hình cho cùng bản ghi khi và chỉ khi $c_i+c_{i+1}+\cdots +c_{i+k-1}=0$ với mọi $i$. Trừ hai đẳng thức liên tiếp, ta được $c_{i+k}=c_i$ với mọi $i$. Do đó $c_i$ không đổi trên mỗi lớp đồng dư modulo $d$.

Gọi giá trị của hiệu trên lớp thứ $r$ là $c_r$. Vì mỗi đoạn gồm $k=dq$ vị trí liên tiếp chứa đúng $q$ phần tử thuộc mỗi lớp đồng dư modulo $d$, điều kiện tổng bằng 0 tương đương với $c_1+c_2+\cdots +c_d=0$. Ngược lại, điều kiện này cùng với việc hiệu không đổi trên mỗi lớp đồng dư cùng cho ta điều kiện đủ để hai cấu hình cho cùng bản ghi.

Giờ ta chia các ngọn đèn thành $d$ đường ray.

Với $1\le r\le d$, đặt $X_r=(x_r,x_{r+d},\dots ,x_{r+(m-1)d})\in \{0,1{\}}^m$ là đường ray thứ $r$. Nếu một đường ray của $x$ chứa cả 0 và 1 thì bắt buộc $c_r=0$, nên đường ray đó được giữ nguyên trong $y$. Một đường ray toàn 1 chỉ có thể được giữ nguyên hoặc đổi thành toàn 0; tương tự, một đường ray toàn 0 chỉ có thể được giữ nguyên hoặc đổi thành toàn 1.

Với mỗi cấu hình $x=(x_1,x_2,\dots ,x_n)$, gọi

$$\varphi (x)=\left\{y\in \{0,1{\}}^n:y\text{ cho cuˋng bản ghi với }x\right\}.$$

Như vậy, $\varphi (x)$ là lớp gồm tất cả các cấu hình cho cùng một bản ghi với $x$, còn $|\varphi (x)|$ là số cấu hình thuộc lớp đó. Giả sử $x$ có đúng $u$ đường ray toàn 1, $v$ đường ray toàn 0 và $d-u-v$ đường ray hỗn hợp (tức có cả 0 và 1). Để thu được một cấu hình $y\in \varphi (x)$, ta chọn $j$ trong $u$ đường ray toàn 1 để đổi thành toàn 0, đồng thời chọn đúng $j$ trong $v$ đường ray toàn 0 để đổi thành toàn 1. Các đường ray còn lại được giữ nguyên. Do đó theo Vandermonde ta có

$$|\varphi (x)|=\sum _{j=0}^{\min (u,v)}{C}_u^j{C}_v^j=C_{u+v}^u,$$

Ta gán cho mỗi cấu hình $x$ trọng số $\frac{1}{|\varphi (x)|}$. Xét một lớp $\mathcal{L}$ có đúng $h$ cấu hình. Với mọi $x\in \mathcal{L}$, ta có $\varphi (x)=\mathcal{L}$, nên $|\varphi (x)|=h$. Vì thế tổng trọng số của các cấu hình thuộc $\mathcal{L}$ bằng

$$\sum _{x\in \mathcal{L}}\frac{1}{|\varphi (x)|}=h\cdot \frac{1}{h}=1.$$

Do đó, khi cộng trên tất cả các cấu hình, mỗi lớp tương đương, hay mỗi bản ghi phân biệt, được tính đúng một lần. Bởi vậy $T=\sum _{x\in \{0,1{\}}^n}\frac{1}{|\varphi (x)|}$ là số bản ghi cần tính.

Số cấu hình $x$ đúng $u$ đường ray toàn 1 và $v$ đường ray toàn 0 là $\frac{d!}{u!v!(d-u-v)!}(2^m-2{)}^{d-u-v}$ nên

$$T=\sum _{\begin{array}{c}u,v\ge 0\\ u+v\le d\end{array}}\frac{d!}{u!v!(d-u-v)!}(2^m-2{)}^{d-u-v}\frac{u!v!}{(u+v)!}=\sum _{u+v=0}^d{C}_d^{u+v}(u+v+1)(2^m-2{)}^{d-u-v}$$

Kết hợp với việc $(u+v)C_d^{u+v}=d{C}_{d-1}^{u+v-1}$ ta suy ra được

$$T=(2^m-1{)}^d+d(2^m-1{)}^{d-1}=(2^m+d-1)(2^m-1{)}^{d-1},$$

trong đó $d=\gcd (n,k)$ và $m=n/d$.

Vậy số bản ghi phân biệt có thể thu được là $T=\left(2^{n/d}+d-1\right){\left(2^{n/d}-1\right)}^{d-1}$ với $d=\gcd (n,k)$.

Trước hết ta có bổ đề quen thuộc sau:

Bổ đề: Với $N$ là hợp số thì $\phi (N)\le N-\sqrt{N}$.

Chứng minh: Thật vậy, gọi $p$ là ước nguyên tố nhỏ nhất của $N$. Khi đó $p\le \sqrt{N}$.

Trong các số $1,2,\dots ,N$ có đúng $N/p$ bội của $p$, và chúng không nguyên tố cùng nhau với $N$. Vì thế
$$N-\phi (N)\ge \frac{N}{p}\ge \sqrt{N}$$

① Giả sử $n$ thỏa mãn $\phi (\phi (n)+k)=n-k$. Ta có $n>k$ và $\phi (n)+k\ge 2$ nên
$$n-k=\phi (\phi (n)+k)\le \phi (n)+k-1.$$
Vì vậy $n-\phi (n)\le 2k-1$. Nếu $n$ là hợp số thì $\sqrt{n}\le n-\phi (n)\le 2k-1$ nên $n\le (2k-1{)}^2$.

Từ đó có hữu hạn hợp số $n$ thoả mãn yêu cầu đề bài.

(2) Giả sử với $k$ nào đó, phương trình có vô số nghiệm nguyên dương $n$. Để ý chỉ có hữu hạn hợp số nên phải có vô số nghiệm $n$ là số nguyên tố, thì $\phi (n)=n-1$ nên
$$\phi (n+k-1)=n-k.$$
Đặt $M=n+k-1$ thì $M-\phi (M)=2k-1$. Nếu $M$ là hợp số thì $\sqrt{M}\le 2k-1$ nên chỉ có hữu hạn giá trị hợp số $M$. Do có vô số giá trị $M$ nên phải có ít nhất 1 giá trị $M$ là số nguyên tố và khi đó
$$M-\phi (M)=1$$
Do đó $2k-1=1$ nên $k=1$. Ngược lại với $k=1$ thì mọi số nguyên tố $n$ thoả mãn yêu cầu nên giá trị duy nhất thoả mãn là $k=1$.