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)
Xếp 4 bạn (An, Bình, Chi, Dũng) phân biệt vào 6 chỗ ngồi là chọn và sắp thứ tự 4 chỗ trong 6 chỗ, tức là chỉnh hợp: số cách = $A_6^4=\frac{6!}{2!}=360$. Vậy đáp án A, khớp với đáp án nguồn (đề 1007, câu 1: A).

(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)
Câu 2: a) Cả hai Bình và An tham gia: chọn 6 bạn nữa từ 8 bạn còn lại và xếp hàng: $C_8^6\cdot 6!\cdot 8!$... chính xác là $C_8^6\cdot 8!=28\cdot 40320=1128960$ cách, không phải 20160 → Sai. b) Bình và An đứng hai đầu hàng: 2 cách hoán vị hai đầu, chọn và xếp 6 bạn từ 8 bạn còn lại vào 6 vị trí giữa: $2\cdot C_8^6\cdot 6!=2\cdot 28\cdot 720=40320$ → Đúng. c) Chỉ chọn 8 trong 10 bạn thì có $C_{10}^8=45$ cách chọn, nhưng 'sắp xếp' thành hàng ngang phải nhân với $8!$, tức $C_{10}^8\cdot 8!=1814400$ cách → Sai. d) Bình và An cùng tham gia và đứng cạnh nhau: coi hai bạn là một khối, chọn 6 bạn từ 8 bạn còn lại, xếp 7 phần tử (khối + 6 bạn) và hoán vị 2 người trong khối: $C_8^6\cdot 7!\cdot 2=28\cdot 5040\cdot 2=282240$ → Đúng. Kết quả khớp đáp án nguồn: SDSD.
a) (AI giải đề cho tôi)
Cả Bình và An tham gia: $C_8^6\cdot 8!=28\cdot 40320=1128960\ne 20160$ cách → Sai.
b) (AI giải đề cho tôi)
Bình, An ở hai đầu: $2\cdot C_8^6\cdot 6!=2\cdot 28\cdot 720=40320$ cách → Đúng.
c) (AI giải đề cho tôi)
Sắp xếp 8 bạn thành hàng ngang từ 10 bạn: $C_{10}^8\cdot 8!=45\cdot 40320=1814400$ cách, không phải chỉ $C_{10}^8$ → Sai.
d) (AI giải đề cho tôi)
Bình, An tham gia và cạnh nhau: $C_8^6\cdot 7!\cdot 2=28\cdot 5040\cdot 2=282240$ cách → Đúng.

(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)
Chọn 4 bạn từ 11 bạn sao cho có ít nhất 2 bạn nữ. Trường hợp 1: đúng 2 nữ, 2 nam: $C_5^2\cdot C_6^2=10\cdot 15=150$. Trường hợp 2: đúng 3 nữ, 1 nam: $C_5^3\cdot C_6^1=10\cdot 6=60$. Trường hợp 3: 4 nữ: $C_5^4=5$. Tổng: $150+60+5=215$ cách.

(AI giải đề cho tôi)
Số cách chọn và sắp xếp 4 chữ số khác nhau từ 6 chữ số 1;2;3;4;5;6 là $A_6^4=6\cdot 5\cdot 4\cdot 3=360$. Vậy đáp án là C.

Ta thực hiện các công đoạn sau:
- Coi Ngọc và Linh là một khối X. Số cách hoán vị nội bộ khối X là $2!=2$ cách.
- Xếp 4 bạn nam thành hàng ngang, có $4!=24$ cách.
- Khi đó tạo ra 5 khoảng trống. Để bạn nữ còn lại không đứng cạnh Ngọc và Linh, ta xếp khối X và bạn nữ còn lại vào 2 trong 5 khoảng trống đó. Số cách chọn và xếp là $A_5^2=20$ cách.
- Tổng số cách xếp là: $2\cdot 24\cdot 20=960$ (cách).

Tổng số sách trên giá là $6+5=11$ quyển. Số cách chọn 3 quyển sách bất kỳ từ 11 quyển là $C_{11}^3=165$ (cách). Để chọn 3 quyển có đủ cả hai loại sách, ta có các trường hợp sau:
- Trường hợp 1: Chọn 2 quyển Toán và 1 quyển Ngữ văn. Số cách chọn là: $C_6^2\cdot C_5^1=15\cdot 5=75$ (cách).
- Trường hợp 2: Chọn 1 quyển Toán và 2 quyển Ngữ văn. Số cách chọn là: $C_6^1\cdot C_5^2=6\cdot 10=60$ (cách).
Vậy tổng số cách chọn thỏa mãn yêu cầu đề bài là: $75+60=135$ (cách). Lưu ý: Có thể dùng phương pháp phần bù: $C_{11}^3-\left(C_6^3+C_5^3\right)=165-30=135$.

Việc chọn một cặp nam - nữ bao gồm hai công đoạn liên tiếp:
- Công đoạn 1: Chọn một học sinh nam, có 5 cách chọn.
- Công đoạn 2: Chọn một học sinh nữ, có 4 cách chọn.
Theo quy tắc nhân, ta có $5\times 4=20$ cách chọn.
Chọn đáp án (B)

(AI giải đề cho tôi)
Xếp 6 bạn (4 nam + 2 nữ, tất cả khác nhau) thành một hàng ngang là một hoán vị của 6 phần tử: $6!=720$ cách. Vậy đáp án A.

(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)
Gọi số có 2 chữ số là $\overline{ab}$ với $a$ là chữ số hàng chục ($a\in \{1,2,\dots ,9\}$) và $b$ là chữ số hàng đơn vị ($b\in \{0,1,\dots ,9\}$), điều kiện cần đếm là $b>a$. Với mỗi cách chọn 2 chữ số khác nhau từ tập $\{0,1,\dots ,9\}$, ta xếp chữ số lớn hơn ở hàng đơn vị và chữ số nhỏ hơn ở hàng chục; khi đó chữ số hàng chục khác 0 nên số luôn hợp lệ, và mỗi cách chọn cho đúng một số thỏa mãn. Vậy số số tự nhiên cần đếm là $C_{10}^2=\frac{10\cdot 9}{2}=45$. Đáp án D.

(AI giải đề cho tôi)
Số tự nhiên có 2 chữ số: chữ số hàng chục $a\in \{1,...,9\}$, hàng đơn vị $b\in \{0,...,9\}$ với $b>a$. Với mỗi $a$, có $9-a$ cách chọn $b$. Tổng: $8+7+6+5+4+3+2+1+0=36$. Vậy đáp án B.

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

(AI giải đề cho tôi)
Xếp 6 bạn (4 nam và 2 nữ, coi mỗi người là một đối tượng phân biệt) thành một hàng ngang là một hoán vị của 6 phần tử, số cách là $6!=720$. Vậy đáp án D.

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

$■$

a)
Gọi $A$ là tập hợp học sinh thích Toán $\Rightarrow n(A)=22$
Gọi $B$ là tập hợp học sinh thích Vật lý $\Rightarrow n(B)=18$
Gọi $C$ là tập hợp học sinh thích Hóa học $\Rightarrow n(C)=15$
Suy ra:
Thích cả Toán và Lý: $n(A\cap B)=9$
Thích cả Lý và Hóa: $n(B\cap C)=7$
Thích cả Toán và Hóa: $n(A\cap C)=6$
Thích cả ba môn: $n(A\cap B\cap C)=3$

Số học sinh thích ít nhất một trong ba môn là:

$n(A\cup B\cup C)=n(A)+n(B)+n(C)-n(A\cap B)-n(B\cap C)-n(A\cap C)+n(A\cap B\cap C)=36$ (học sinh)

b)
Từ câu a) số học sinh không thích môn nào là: $40-36=4$

Không gian mẫu chọn ngẫu nhiên 3 bạn từ 40 bạn: ${\mathrm{C}}_{40}^3=9880$ (cách)

Ta có số cách chọn 3 học sinh thích ít nhất một môn là: ${\mathrm{C}}_{36}^3=7140$ (cách)

Vậy số cách chọn 3 học sinh không thích ít nhất một môn là: $9880-7140=2740$ (cách)

(AI giải đề cho tôi)
Nhóm có 4 nữ, 5 nam (tổng 9 bạn). a) Số cách xếp 9 bạn thành hàng ngang là $9!=362880$ → đúng. b) Không gian mẫu: $C(9,3)=84$. Chọn đúng 1 nữ và 2 nam: $C(4,1)\cdot C(5,2)=4\cdot 10=40$. Xác suất $=40/84=10/21$ → đúng. c) Số cách chọn 3 bạn có đúng 1 nữ là $C(4,1)\cdot C(5,2)=40$, không phải 4 → sai. d) Xếp 5 nam trước: $5!=120$ cách, tạo 6 khoảng trống; chọn 4 trong 6 khoảng để xếp 4 nữ: $C(6,4)\cdot 4!=15\cdot 24=360$. Tổng $=120\cdot 360=43200$ cách, không phải $2880$ → sai. Kết quả khớp đáp án nguồn: a) Đúng, b) Đúng, c) Sai, d) Sai.
a) (AI giải đề cho tôi)
Xếp 9 bạn thành hàng ngang: $9!=362880$ cách.
b) (AI giải đề cho tôi)
$P=C(4,1)\cdot C(5,2)/C(9,3)=40/84=10/21$.
c) (AI giải đề cho tôi)
Số cách chọn đúng 1 nữ và 2 nam: $C(4,1)\cdot C(5,2)=40$ cách, không phải 4.
d) (AI giải đề cho tôi)
$5!\cdot C(6,4)\cdot 4!=120\cdot 15\cdot 24=43200$ cách, không phải $2880$.