Bài Tập Trắc Nghiệm Chuyên Đề: Nguyên lý Dirichlet (Toán học Lớp 10, 11, 12)

(AI giải đề cho tôi)
Xét $n+1$ số: $1,11,111,\dots ,\underset{n+1\text{ chữ soˆˊ}}{\underbrace{11\dots 1}}$. Xét phần dư khi chia cho $n$: có $n+1$ số nhưng chỉ có $n$ phần dư khác nhau, nên theo nguyên lý Dirichlet tồn tại hai số $a_i=\underset{i}{\underbrace{11\dots 1}}$ và $a_j=\underset{j}{\underbrace{11\dots 1}}$ với $i>j$ có cùng phần dư khi chia cho $n$. Khi đó $n\mid a_i-a_j$. Mặt khác $a_i-a_j=\underset{i-j}{\underbrace{11\dots 1}}\underset{j}{\underbrace{00\dots 0}}=a_{i-j}\cdot 10^j$, tức là một số có biểu diễn thập phân gồm toàn các chữ số 1 và 0 (gồm $i-j$ chữ số 1 đứng đầu rồi $j$ chữ số 0). Vậy đặt $m=a_i-a_j$ thì $m$ là số nguyên dương, biểu diễn thập phân chỉ gồm chữ số 1 và 0, và $n\mid m$. Đpcm. (Kiểm tra: phép trừ hai số repunit cùng dạng luôn cho các chữ số 1 và 0; tính chất chia hết đúng do hai số cùng phần dư.)

Coi mỗi thành viên là một đỉnh và nối hai đỉnh khi hai thành viên tương ứng quen nhau. Ta thu được một đồ thị vô hướng đơn có tập đỉnh $V$, $|V|=99$. Với $u\in V$, kí hiệu $N(u)$ là tập các đỉnh kề với $u$ và $d(u)=|N(u)|$. Theo giả thiết, $81\le d(u)\le 90$ với mọi $u\in V$.

a) Ta sẽ đếm các bộ $(w,\{u,v\})$, trong đó $u,v$ là hai đỉnh phân biệt cùng thuộc $N(w)$.
- Cố định $w$, ta có số bộ là $$\sum _{w\in V}{C}_{d(w)}^2\ge 99C_{81}^2.$$
- Mặt khác, với mỗi cặp $\{u,v\}$, số cách chọn $w$ chính là $|N(u)\cap N(v)|$.
Vì có $C_{99}^2$ cặp đỉnh nên tồn tại một cặp $\{u,v\}$ có số người quen chung ít nhất bằng
$$\frac{99C_{81}^2}{C_{99}^2}=\frac{81\cdot 80}{98}=66+\frac{6}{49}>66.$$
Số người quen chung là một số nguyên, do đó cặp này có ít nhất 67 người quen chung.

b) Giả sử ngược lại rằng không tồn tại 10 đỉnh có cùng bậc và có một đỉnh kề chung. Khi đó không thể có trường hợp mọi đỉnh đều có bậc 81, vì khi đó tổng các bậc bằng $99\cdot 81$ là một số lẻ, trái với bổ đề bắt tay. Do đó tồn tại một đỉnh $v$ có $d(v)>81$.
Với mỗi $k\in \{81,82,\dots ,89\}$, tập $N(v)$ chứa nhiều nhất 9 đỉnh bậc $k$; nếu không, ta có ngay 10 đỉnh cùng bậc $k$ và cùng kề với $v$. Vì
$$|N(v)|>81=9\cdot 9,$$
trong $N(v)$ phải có một đỉnh $w$ bậc 90.
Xét tập $N(w)$ gồm 90 đỉnh. Với mỗi $k\in \{81,82,\dots ,90\}$, tập này chứa nhiều nhất 9 đỉnh bậc $k$. Có đúng 10 giá trị có thể của $k$, nên $N(w)$ phải chứa đúng 9 đỉnh thuộc mỗi bậc $81,82,\dots ,90$. Đặc biệt, $N(w)$ chứa 9 đỉnh bậc 90. Cùng với $w$, ta được một tập $A$ gồm 10 đỉnh, tất cả đều có bậc 90.
Với mỗi $u\in A$, trong 99 đỉnh có đúng $99-90=9$ đỉnh không kề với $u$, kể cả $u$. Do đó có không quá $10\cdot 9=90$ đỉnh không kề với ít nhất một đỉnh của $A$. Vì thế có ít nhất $99-90=9$ đỉnh kề với mọi đỉnh của $A$ nên có 10 đỉnh của $A$ có cùng bậc và có đỉnh kề chung, mâu thuẫn với phản chứng.
Vậy tồn tại 10 thành viên có cùng số lượng người quen và cùng quen chung một người.

(AI giải đề cho tôi)
Bài 1: Xét hai phép biến đổi $f(x)=\frac{1}{x}$ và $g(x)=1-x$ trên $\mathbb{R}\setminus \{0\}$. Từ $x\in A$ ta phải có đồng thời các phần tử: $x,\frac{1}{x},1-x,\frac{1}{1-x},\frac{x}{x-1},\frac{x-1}{x}$ (đây là các ảnh của $x$ dưới nhóm sinh bởi $f,g$, vì $f\circ f=\mathrm{id}$, $g\circ g=\mathrm{id}$, $f\circ g\circ f(x)=\frac{x}{x-1}$, v.v.). Nếu $x$ không phải điểm bất động của bất kỳ phép biến đổi nào trong 6 phép trên thì 6 giá trị này đôi một khác nhau, khi đó $A$ phải có ít nhất 6 phần tử, mâu thuẫn với ii). Xét các trường hợp trùng nhau:
• $x=\frac{1}{x}\Rightarrow x=\pm 1$. Với $x=1$ thì $1-x=0\notin \mathbb{R}\setminus \{0\}$, loại. Với $x=-1$: hợp lệ.
• $x=1-x\Rightarrow x=\frac{1}{2}$.
• $x=\frac{1}{1-x}\iff x^2-x+1=0$: vô nghiệm thực.
• $x=\frac{x}{x-1}\Rightarrow x=2$; $x=\frac{x-1}{x}\iff x^2-x+1=0$: vô nghiệm.
Như vậy mọi phần tử của $A$ phải nằm trong quỹ đạo $\left\{-1,\frac{1}{2},2\right\}$ (kiểm tra: từ $-1$ ta có $\frac{1}{-1}=-1$, $1-(-1)=2$; từ $2$ ta có $\frac{1}{2}$ và $1-2=-1$; từ $\frac{1}{2}$ ta có $2$ và $1-\frac{1}{2}=\frac{1}{2}$). Vì $A\ne \varnothing$ nên $A$ phải chứa trọn quỹ đạo này, vậy $A=\left\{-1,\frac{1}{2},2\right\}$. Thử lại: tập này có 3 phần tử $\le 5$, khác rỗng, và đóng dưới cả hai phép biến đổi. Vậy $A=\left\{-1,\frac{1}{2},2\right\}$ là tập duy nhất thỏa mãn.

Bài 2: Đánh số các số theo chiều tròn là $a_1,a_2,\dots ,a_{101}$ và đặt $S_0=0$, $S_i=a_1+a_2+\cdots +a_i$ với $i=1,2,\dots ,100$. Vì các $a_i$ đều nguyên dương và tổng bằng 300 nên $0=S_0<S_1<\cdots <S_{100}\le 299$ (do $a_{101}\ge 1$).
Xét 101 số $S_0,S_1,\dots ,S_{100}$ theo mô-đun 100: chúng chỉ có thể nhận 100 giá trị dư nên theo nguyên lý Dirichlet, tồn tại $0\le i<j\le 100$ sao cho $S_j\equiv S_i(\mathrm{mod}100)$, tức $S_j-S_i=100k$ với $k\in \{1,2,3\}$ (hiệu dương do dãy tăng ngặt).
• Nếu $k=3$: $S_j-S_i=300$, nhưng $S_j\le 299$, vô lý. Vậy $k\in \{1,2\}$.
• Nếu $k=1$: dãy các số viết liền nhau $a_{i+1},a_{i+2},\dots ,a_j$ có tổng $S_j-S_i=100$.
• Nếu $k=2$: dãy $a_{i+1},\dots ,a_j$ có tổng 200; khi đó phần còn lại của đường tròn, tức dãy $a_{j+1},\dots ,a_{101},a_1,\dots ,a_i$, cũng là dãy các số viết liền nhau trên đường tròn và có tổng $300-200=100$.
Vậy trong mọi trường hợp luôn tồn tại một dãy các số viết liền nhau có tổng bằng 100. Đpcm.