Category Archives: Tổ hợp

Phương pháp chứng minh phản chứng (P2)

Bài 1.

Cho tập $B = 1, 2, 3, \dots, 16$ . Người ta ghi các số của tập B thành một vòng tròn (mỗi số ghi một lần). Hỏi có cách ghi để tổng thỏa:

a/ Tổng của hai số kế nhau bất kì lớn hơn hoặc bằng 17 được không? Tại sao?

b/ Tổng của ba số kế nhau bất kì lớn hơn 24 được không? Tại sao?

Lời giải

a/ Giả sử tồn tại cách ghi thỏa mãn. Khi đó, gọi 2 số kề với 1 là a và b.

Theo giả thiết, ta có:

${\begin{cases} 1 + a ⩾ 17 \\ 1 + b ⩾ 17 \end{cases} \Rightarrow {\begin{cases} a ⩾ 16 \\ b ⩾ 16 \end{cases} \Rightarrow$ Mâu thuẫn.

Vậy không tồn tại cách ghi thỏa mãn.

b/ Giả sử tồn tại cách ghi thỏa mãn.

Khi đó, ta tách số 16 ra và chia 15 số còn lại thành 5 bộ 3 số kề nhau. Và tổng của 16 số này phải lớn hơn hoặc bằng: $16 + 5 \cdot 25 = 141$

Mà $1 + 2 + 3 + \dots 16 = 136 \Rightarrow$ Mâu thuẫn

Vậy không tồn tại cách ghi thỏa mãn.

Bài 2.

Có tồn tại hay không một cách điền các số $0, 1, 2, 3, \dots, 9$ vào các đỉnh của một đa giác 10 đỉnh sao cho hiệu hai số ở hai đỉnh kề nhau chỉ có thể nhận một trong các giá trị sau: $- 5, - 4, - 3, 3, 4, 5$ .

Lời giải

Giả sử có cách xếp thỏa mãn.

Xét các số $0, 1, 2, 8, 9$ không thể đứng kề nhau và có đúng 10 số nên 5 số còn lại phải đứng xen kẽ với 5 số $0, 1, 2, 8, 9$ .

Xét số 7:

Khi đó hai số kề số 7 phải thuộc tập hợp ${0, 1, 2, 8, 9}$

Mà theo giả thiết 2 đỉnh kề nhau bất kì nhận một trong các giá trị – 3, – 4, – 5, 3, 4 hoặc 5 nên 2 số kề nhau với 7 đều bằng 2 $\Rightarrow$ Mâu thuẫn.

Vậy không có cách xếp nào thỏa mãn.

Bài 3.

Trong mặt phẳng tọa độ thì một điểm mà hoành độ và tung độ đều là các số nguyên được gọi là điểm nguyên. Chứng minh rằng không tồn tại tam giác đều nào mà các đỉnh đều là điểm nguyên.

Lời giải

Giả sử tồn tại tam giác đều có các đỉnh là các điểm nguyên.

Xét hình chữ nhật có các đỉnh là các điểm nguyên, sao cho đỉnh của tam giác đều thuộc cạnh của hình chữ nhật. Khi đó dễ dàng suy ra diện tích tam giác đều là số hữu tỷ.

Ta có diện tích tam giác đều $S = \frac{a^{2} \sqrt{3}}{4}$ với $a^{2} = x^{2} + y^{2}$ là số nguyên, $\sqrt{3}$ là số vô tỷ

Do đó, S là số vô tỉ $\Rightarrow$ Mâu thuẫn $\Rightarrow$ đpcm.

Bài 4.

Điền các số 1,2,3,…,121 vào một bảng ô vuông kích thước $11 \times 11$ sao cho mỗi ô chứa một số. Tồn tại hay không một cách điền sao cho hai số tự nhiên liên tiếp sẽ được điền vào hai ô có chung một cạnh và các tất cả các số chính phương thì nằm trong cùng một cột?

Lời giải

Giả sử tồn tại một cách điền số vào các ô thỏa yêu cầu đặt ra.

Khi đó bảng ô vuông được chia thành hai phần ngăn cách nhau bởi cột điền các số chính phương. Một phần chứa $11 n$ ô vuông $1 \times 1$ , và phần còn lại chứa $110 - 11 n$ ô vuông $1 \times 1$ , với $0 \leq n \leq 5.$

Nhận thấy rằng các số tự nhiên nằm giữa hai số chính phương liên tiếp $a^{2}$ và $(a + 1)^{2}$ sẽ cùng nằm về một phần và các số tự nhiên nằm giữa $(a + 1)^{2}$ và $(a + 2)^{2}$ sẽ nằm ở phần còn lại.

Ta có số lượng các số tự nhiên nằm giữa 1 và 4, 4 và 9, 9 và 16,…,100 và 121 lần lượt là $2, 4, 6, 8, \dots, 20$ .

Do đó một phần sẽ chứa $2 + 6 + 10 + 14 + 18 = 50$ số, phần còn lại chứa $4 + 8 + 12 + 16 + 20 = 60$ số.

Cả 50 và 60 đều không chia hết cho 11 $\Rightarrow$ Mâu thuẫn.

Vậy không tồn tại cách điền số thỏa yêu cầu đề bài.

Bài 5.

Mỗi phần tử của bảng vuông $25 \times 25$ hoặc là $+ 1$ hoặc $- 1$ . Gọi $a_{i}$ là tích của tất cả các phần tử của hàng thứ $i$ và $b_{j}$ là tích của tất cả các phần tử của cột thứ $j$ . Chứng minh rằng $a_{1} + b_{1} + \dots + a_{25} + b_{25} \neq 0$

Lời giải

Giả sử $a_{1} + b_{1} + \dots + a_{25} + b_{25} = 0$ .

Vì mỗi ô vuông chứa -1 hoặc 1 nên $a_{i}, b_{i} \in {1, - 1}$

Do đó trong 50 tích $a_{i}, b_{i} (i = \overset{―}{1, 25})$ sẽ có 25 tích có giá trị -1 và 25 tích có giá 1.

Khi thay thế một phần tử -1 trong bảng bằng 1 thì số các tích ngang dọc có giá trị -1 sẽ tăng 2 hoặc giảm 2 hoặc không thay đổi. Như vậy số các tích $a_{i}, b_{i}$ có giá trị -1 luôn là số lẻ (1)

Ta sẽ tiếp tục thay thế các phần tử -1 trong bảng bằng 1 cho đến khi tất cả các phần tử trong bảng đều bằng 1 thì khi đó số các tích ngang dọc $a_{i}, b_{i}$ có giá trị -1 là 0 $\Rightarrow$ Mâu thuẫn với (1) $\Rightarrow$ đpcm.

Phương pháp ánh xạ trong các bài toán tổ hợp

Leave a reply

Thầy Nguyễn Tăng Vũ

1/ Lý thuyết:

Cho $A$ và $B$ là hai tập hợp hữu hạn.

Nếu có một đơn ánh $f : X ⟶ Y$ thì $| X | \leq | Y | .$
Nếu có một toàn ánh $f : X ⟶ Y$ thì $| X | \geq | Y | .$
Nếu có một song ánh $f : X ⟶ Y$ thì $| X | = | Y | .$

2/ Bài tập:

Bài 1.

Cho $X = 1, 2, . ., n$ . Một tập con $S = s_{1}, s_{2}, \dots, s_{k}$ của X ( $s_{1} < s_{2} < \dots < s_{k}$ ) được gọi là \textit{m- tách được} $(m \in N)$ nếu $s_{i} - s_{i - 1} \geq m; i = 1, 2, \dots, k$ . Có bao nhiêu tập con m- tách được gồm $k$ phần tử của X, trong đó $0 \leq k \leq n - (m - 1) (k - 1)$ .

Lời giải

Gọi A là tập tất cả các tập con m- tách được gồm $k$ phần tử của X và B là tập tất cả các tập con gồm k phần tử của tập $Y = {1, 2, \dots, n - (k - 1) (m - 1)}$ .

Ta xây dựng song ánh từ A đến B như sau: Với $S = {s_{1}, s_{2}, \dots, s_{k}} \in A$ ( $s_{1} < s_{2} < \dots < s_{k}$ ) lấy tương ứng $f (S) = {s_{1}, s_{2} - (m - 1), s_{3} - 2 (m - 1), \dots, s_{k} - (k - 1) (m - 1)}$ . Dễ chứng minh đây là một song ánh. Từ đó có $C_{n - (k - 1) (m - 1)}^{k}$ tập thoả yêu cầu đề bài.

Bài 2.

Cho $X = 1, 2, \dots, n$ , với mỗi tập con khác rỗng $A_{i} = a_{1}, a_{2}, \dots, a_{i}$ (không mất tổng quát giả sử $a_{1} > a_{2} > \dots > a_{i}$ ) ta định nghĩa tổng hỗn tạp của $A_{i}$ là số $m (A_{i}) = a_{1} - a_{2} + a_{3} - \dots \pm a_{i}$ . Tính $\sum_{A_{i} \subset X} m (A_{i})$ .

Lời giải

Gọi B là tập tất cả các tập con không chứa phần tử n của X và C là tập tất cả các tập con có chứa phần tử n của X.

Ta xây dựng song ánh từ B đến C như sau: Với $S = {s_{1}, s_{2}, \dots, s_{k}} \in B$ ( $s_{1} < s_{2} < \dots < s_{k} < n$ ) lấy tương ứng $f (S) = {s_{1}, s_{2}, \dots, s_{k}, n},$ nhận thấy $f (S) \in C$ . Dễ chứng minh đây là một song ánh.

Ta có: $| B | = | C | = 2^{n - 1}; B \cup C = \emptyset; B \cap C = X$

Và $m (S) + m (f (S)) = n$

Do đó: $\sum_{A_{i} \subset X} m (A_{i}) = \sum_{B_{i} \subset B} m (B_{i}) + \sum_{C_{i} \subset C} m (C_{i}) = n \cdot 2^{n - 1}$

Bài 3.

Cho $X = 1, 2, \dots, n$ . Một tập con A của X được gọi là tập béo nếu mỗi phần tử của A đều không nhỏ hơn số phần tử của nó. Tập rỗng cũng là một tập béo. Đặt $a_{n}$ là số các tập béo của X mà trong mỗi tập không chứa hai số liên tiếp, $b_{n}$ là số các tập con của X mà hai phần tử bất kỳ hơn kém nhau ít nhất 3 đơn vị. Chứng minh $a_{n} = b_{n} .$

Lời giải

Gọi A là họ các tập béo thỏa yêu cầu đề bài, B là họ các các tập con của X có tính chất hai phần tử bất kỳ hơn kém nhau 3 đơn vị. Ta thiết lập một ánh xạ $f$ đi từ A đến B như sau: giả sử $x = {a_{1}, a_{2}, \dots, a_{k}} \in A$ , ta có thể giả sử $k \leq a_{1} < a_{2} < a_{3} < \dots < a_{k} \leq n$ . Đặt $b_{1} = a_{1} - k + 1, b_{2} = a_{2} - k + 2, \dots, b_{k} = a_{k}$ . Khi đó $a_{i + 1} \geq a_{i} + 2, i = 1, 2, \dots, k - 1.$

Suy ra $a_{i + 1} - a_{i} \geq 2$ do đó $b_{i + 1} - b_{i} \geq 3$ và $b_{1} \geq 1, b_{k} \leq n .$ Định nghĩa $f (x) = y = {b_{1}, b_{2}, \dots, b_{k}}$ , suy ra $y \in B$ . Vậy $f$ là một ánh xạ, hơn nữa dễ thấy $f$ là một song ánh do đó ta có điều cần chứng minh.

Bài 4.

Cho số nguyên dương $n$ và $d$ là một ước dương của $n$ . Gọi S là tập tất cả những bộ $(x_{1}, x_{2}, \dots, x_{n})$ nguyên dương thỏa $0 \leq x_{1} \leq x_{2} \leq \dots \leq x_{n} \leq n$ và $d | x_{1} + x_{2} + \dots + x_{n}$ . Chứng minh rằng có đúng một nửa các phần tử của S có tính chất $x_{n} = n$ .

Lời giải

$(x_{1}, x_{2}, \dots, x_{n - 1}, x_{n}) \in S$ mà $x_{n} \neq n$ ta cho tương ứng với bộ $(x_{1} + 1, x_{2} + 2, \dots, x_{n - 1} + 1, x_{n} + 1)$ , với $(x_{1}, x_{2}, \dots, x_{n - 1}, n) \in S$ ta cho tương ứng với bộ $(0, x_{1}, \dots, x_{n - 1}) .$ \

Dễ chứng minh $f$ là một song ánh, $f$ hoán vị S và $f (S) = S .$ Vì tổng tất cả các phần tử của các bộ trong S và $f (S)$ là như nhau trong khi tương ứng thứ nhất tăng tăng tổng này lên $n$ đơn vị, tương ứng thứ hai giảm tổng này đi $n$ đơn vị nên số lần xuất hiện của hai tương ứng này là như nhau. Từ đó suy ra điều cần chứng minh

Bài 5.

Gọi $a_{n}$ là số các xâu nhị phân độ dài $n$ không chứa ba bit 0, 1, 0 liên tiếp. Gọi $b_{n}$ là số các xâu nhị phân độ dài $n$ chứa bốn bit 0, 0, 1, 1 hoặc 1, 1, 0, 0 liên tiếp. Chứng minh rằng $b_{n + 1} = 2 a_{n}$ với mọi số nguyên dương $n$ .

Lời giải

Gọi $A_{n}, B_{n}$ lần lượt là tập các xâu nhị phân độ dài $n$ thỏa điều kiện thứ nhất và thứ hai. Với mỗi xâu nhị phân $(x_{1}, x_{2}, \dots, x_{n})$ ta cho tương ứng với một xâu nhị phân $(y_{0}, y_{1}, \dots, y_{n})$ xác định bởi $y_{0} = 0$ và $y_{i} = x_{1} + x_{2} + \dots + x_{i} m o d 2, i = 1, 2, \dots, n . (*)$

Khi đó $x_{i} = y_{i} + y_{i - 1} m o d 2, i = 1, 2, \dots, n .$

Dễ thấy (*) là một song ánh giữa tập tất cả các xâu nhị phân độ dài $n$ và tập tất cả các xâu nhị phân độ dài $n + 1$ trong đó có bit đầu tiên là 0. Hơn nữa xâu nhị phân $(x_{1}, x_{2}, \dots, x_{n})$ có 3 bit 0,1,0 liên tiếp theo thứ tự này khi và chỉ khi xâu nhị phân tương ứng $(y_{0}, y_{1}, \dots, y_{n})$ có 4 bit liên tiếp theo thứ tự là 0,0,1,1 hoặc 1,1,0,0. Nói cách khác một xâu nhị phân thuộc $A_{n}$ sẽ tương ứng với một xâu nhị phân thuộc $B_{n + 1}$ và bắt đầu bằng bit 0. Vì số xâu nhị phân thuộc vào $B_{n + 1}$ bắt đầu bằng bit 0 đúng bằng một nửa số xâu nhị phân thuộc vào $B_{n + 1}$ do đó ta có $b_{n + 1} = 2 a_{n}$ (điều phải chứng minh).

Đếm bằng 2 cách

Leave a reply

NGUYỄN QUANG TÂN

1/ Bài tập đếm số cặp

Bài 1.

Trong một ủy ban, mỗi thành viên thuộc đúng 3 tiểu ban, mỗi tiểu ban có đúng 3 thành viên. Chứng minh rằng số thành viên của ủy ban bằng số tiểu ban.

Lời giải

Gọi số thành viên là $n$ và số tiểu ban là $m$ .

Gọi $T$ là số cặp $(a, B)$ trong đó thành viên $a$ thuộc tiểu $B$ . Vì mỗi thành viên thuộc 3 tiểu ban nên: $T = 3 n$ ;

Vi mỗi tiểu ban có đúng 3 thành viên nên $T = 3 m$ ;

Vậy $3 m = 3 n$ nên $m = n$

Bài 2.

Trong trường học có một số câu lạc bộ. Biết rằng mỗi câu lạc bộ có đúng 30 học sinh. Vâ mỗi học sinh tham gia đúng 3 câu lạc bộ. Biết rằng tổng số câu lạc bộ và số học sinh bằng 440 . Tìm số học sinh của trường.

Lời giải

Ta đếm số cặp $(a, B)$ mà học sinh $a$ thuộc câu lạc bộ $B$ . Gọi $m$ là số câu lạc bộ và $n$ là số học sinh.

Ta có hệ $30 m = 3 n$ và $m + n = 440$ . Ta được $m = 40$ và $n = 400$ .

Bài 3. (IMC 2002)

Có 200 thí sinh tham gia một cuộc thi toán học. Các thí sinh phải giải 6 bài toán. Biết mỗi bài được giải đúng bởi ít nhất 120 thí sinh. Chứng minh rằng có hai thí sinh mà mỗi bài tập được giải bởi ít nhất một trong hai thí sinh.

Lời giải

Ta dùng phản chứng: Với mỗi cặp thí sinh bất kì đều có ít nhất 1 bài không giải được bởi cả hai thí sinh.

Gọi $T$ là số bộ $({t_{1}, t_{2}}; B)$ thỏa mãn thí $\sinh t_{1}, t_{2}$ cùng không giải được bài tập B.

Ta biết rằng mỗi bài được giải bởi ít nhất 120 thí sinh, vậy số thí sinh không giải được một bài nhỏ hơn hoặc bằng 80.

Nên $T \leq 6 C_{80}^{2} = 18960$

Mặt khác hai thí sinh bất kì có ít nhất một bài cùng không giải được nên $T \geq C_{200}^{2} = 19900 .$ Mâu thuẫn.

Vậy điều phản chứng là sai. Bài toán được chứng minh.

Bài 4. (Chọn đội tuyển thi Quốc Gia Khối chuyên ĐHSP 2013)

Cơ sở dữ liệu tạp chí của thư viện Quốc Gia có đúng 2016 loại khác nhau. Thư viện này cho phép 2013 thư viện địa phương kết nối để có thể khai thác cơ sở dữ liệu tạp chí của nó. Biết mỗi thư viện địa phương được phép khai thác ít nhất 1008 loại tạp chí khác nhau và 2 thư viện địa phương bất kì có tối đa 504 loại tạp chí mà cả 2 thư viện địa phương đó cùng đc phép khai thác. Chứng minh rằng không có quá 1 loại tạp chí trong cơ sở dữ liệu của thư viện Quốc Gia mà cả 2013 thư viện địa phương đều không thể khai thác được.

Lời giải

Giả sử có 2 tạp chí mà không thư viện địa phương nào cùng khai thác. Như vậy tập hợp các tạp chí mà các thư viện cùng khai thác là $X =$ ${1, \dots, 2014} .$ Gọi $T$ là số bộ $({T_{1}, T_{2}}, t)$ mà hai thư viện $T_{1}, T_{2}$ cùng khai thác tạp chí $t$ .

Vì mỗi thư viện khai thác chung tối đa 504 tạp chí nên: $T \leq 504 C_{2013}^{2}$ .

Giả sử số thư viện cùng khai thác tạp chí thứ $i$ là $a_{i}$ thi $\sum_{i = 1}^{2013} a_{i} \geq 2013.1008$ .

Ta có: $T = \sum_{i = 1}^{2014} C_{a_{i}}^{2} \geq \frac{2003.1008 (2003.1008 - 2014)}{2.2014}$

Suy ra: $504 C_{2013}^{2} \geq \frac{2003.1008 (2003.1008 - 2014)}{2.2014}$ . Điều này vô lý.

Bài 5. (Chọn đội tuyển HSG QG tỉnh Đồng Tháp năm học 2013)

CLB du khảo có n thành viên. Năm ngoái CLB đã tổ chức được 6 chuyến du khảo, mỗi chuyến có 5 thành viên tham dự. Một thành viên CLB nhận xét rằng hai chuyến du khảo bất kỳ có không quá hai thành viên chung. Hỏi CLB đó có ít nhất bao nhiêu thành viên?

Lời giải

Giả sử câu lạc bộ đó có $n$ thành viên. Tập hợp các học sinh tham gia chuyến du khảo thứ $i$ là $A_{i}$ . Ta có:

i) $| A_{i} | = 5$ ;

ii) $| A_{i} \cap A_{j} | \leq 2$

Giả sử thành viên thứ $i$ tham gia $a_{i}$ chuyến du khảo ta có $\sum_{i = 1}^{6} a_{i} = 30$ .

Gọi $T$ là số bộ $(A_{i}, A_{j}, k)$ trong đó thành viên $k$ tham gia cả hai chuyến du khảo $A_{i}$ và $A_{j}$

T=\sum_{i=1}^{n} C_{a_{i}}^{2} \geq \frac{15(30-n)}{n}

Vì hai chuyến du khảo bất kì có không quá 2 thành viên chung nên: $T \leq 2 C_{6}^{2} = 30$

Suy ra: $\frac{15 (30 - n)}{n} \leq 30 \Leftrightarrow n \geq 10$

2/ Bài tập đếm số bộ ba

Bài 6.

Trong một trương học có $m$ lớp với $m \geq 10$ , tổng số học sinh là $n$ . Với $n \leq 465$ , các lớp được đánh số từ 1 tới $m$ , biết rằng mỗi học sinh ở lớp $i$ quen $j$ học sinh ở lớp thứ $j$ . Tìm giá trị lớn nhất của $n$ .

Lời giải

Giả sử lớp thứ $i$ có $k_{i}$ học sinh. Từ quan hệ quen biết ta có: $k_{i} \cdot j = k_{j} \cdot i$ nên $\frac{k_{i}}{i} = t$ với mọi $i$ .

Vi $k_{1} + \dots + k_{m} = n \leq 465$ nên $t (1 + \dots + m) \leq 465$ mà $m \geq 10$ nên $t \frac{10.11}{2} = 55$

Suy ra $55 t \leq 465$ nên $n \leq 8$ . Vậy $n$ lớn nhất bằng 8 .

Bài 7. (Hong Kong TST 2003)

Có 15 học sinh tham gia một khóa học. Biết rằng mỗi ngày, có 3 học sinh phải trực vệ sinh cho lớp và sau khi kết thúc khóa học thì cứ 2 học sinh bất kì đều tham gia trực chung đúng 1 lần. Tính số ngày khóa học diễn ra.

Lời giải

Giả sử khóa học có $m$ ngày. Ta gọi $S$ là số bộ $(x, y, z)$ trong đó hai học $\sinh x, y$ cùng tham gia trực nhật vào ngày thứ $z$ của khóa học.

Vì 2 học sinh bất kỳ đều tham gia trực nhật chung đúng một lần nên $S =$ $C_{15}^{2} = 105$ . Mặt khác mỗi ngày có 3 học sinh tham gia trực nhật nên $S =$ $m C_{3}^{2} = 3 m$

Vậy $m = \frac{105}{3} = 35$ .

Bài 8. (IMO 1989)

Cho $n$ và $k$ là các số nguyên dương mà tồn tại một tập $T$ có $n$ điểm trong mặt phẳng sao cho

i) Không có 3 điểm nào thẳng hàng;

ii) $\forall P \in T$ có ít nhất $k$ điểm thuộc $T$ mà cách đều $P$ .

Chứng minh rằng $k \leq \frac{1}{2} + \sqrt{2 n}$

Lời giải

Gọi $S$ là số các bộ 3 điểm $({A, B}, C)$ mà $A, B$ cách đều $C$ .

Trước hết ta đếm theo ${A, B}$ : Với mỗi cạ̣p điểm ${A, B}$ thì các điểm cách đều $A$ và $B$ nằm trên trung trực của đoạn $A B$ . Mà không có 3 điểm nào thẳng hàng trong $T$ nên ta có chỉ có tối đa 2 điểm $C$ . Vậy $S \leq 2 C_{n}^{2}$ .

Ta đếm theo $C$ : Với mỗi điểm $C$ có ít nhất $k$ điểm trong $T$ cách đều $C$ nên số cặp ${A, B}$ ít nhất là $C_{k}^{2}$ . Do đó $S \geq n C_{k}^{2}$ .

Suy ra $2 C_{n}^{2} \geq n C_{k}^{2} .$ Từ đó ta có: $k \leq \frac{1}{2} + \sqrt{2 n}$

Bài 9.

Cho $X$ là một tập hữu hạn với $| X | = n$ và $A_{1}, A_{2}, \dots, A_{m}$ là các tập con của $X$ có đúng 3 phần tử thỏa mãn $| A_{i} \cap A_{j} | \leq 1 \forall i \neq j$ . Chứng minh rằng tồn tại một tập con $A \subset X$ với ít nhất $[\sqrt{2 n}]$ phần tử mà không chứa bất kì tập $A_{i} (1 \leq i \leq m)$ nào.

Lời giải

Giả sử $A \subset X$ là một tập con với số phần tử lớn nhất là $k$ mà không chứa bất kì tập $A_{i} (1 \leq i \leq m)$ nào.

Gọi $S$ là số bộ $({a, b}, c)$ thỏa mãn $c \notin A$ và ${a, b}$ là tập con của một trong một tập $A_{1}, \dots, A_{m}$ .

Ta đếm theo $c$ : Với mỗi $c \notin A$ do tính cực đại của $A$ thì sẽ tồn tại $A_{i} \subset$ $A \cup {c}$ khi đó chọn ${a, b} = A_{i} ∖ {c} .$

Do vậy $S \geq n - k$ .

Ta đếm theo ${a, b} :$ Do $| A_{i} \cap A_{j} | \leq 1 \forall i \neq j$ nên với mỗi ${a, b} \subset A$ tồn tại nhiều nhất một $A_{j} \supset {a, b}$ , khi đó ta chọn $c = A_{j} ∖ {a, b} .$ Do đó $S \leq C_{k}^{2}$ .

Suy ra $n - k \geq C_{k}^{2}$ hay $k^{2} + k \geq 2 n$ nên $k \geq - \frac{1}{2} + \frac{1}{2} \sqrt{1 + 8 n}$

Từ đó ta có: $k \geq ⌊ \sqrt{2 n} ⌋$ .

Bài 10. (APMO 2006)

Trong một rạp xiếc, có $n$ chú hề được trang điểm bằng một số trong tổng cộng 12 màu sơn. Biết rằng mỗi chú hề phải sử dụng ít nhất 5 màu. Ngoài ra, mỗi màu được sử dụng bởi không quá 20 chú hề. Chứng minh rằng $n \leq 48$

Lời giải

Gọi số chú hề sử dụng màu sơn thứ $i$ là $a_{i} \leq 20 .$ Ta có $T = \sum_{i = 1}^{12} a_{i} \geq$ 5n. Gọi $S$ là số bộ $(x, y, m)$ trong đó hai chú hề $x, y$ cùng sử dụng màu sơn thứ $m$

Ta có $S = \sum_{i = 1}^{12} C_{a_{i}}^{2} \geq \frac{T (T - 12)}{2.12} \geq \frac{5 n (5 n - 12)}{24}$

Vì mỗi màu sơn được sử dụng bởi không quá 20 chú hề, $S \leq 12 C_{20}^{2} = 2280$ . Ta có phương trình $\frac{5 n (5 n - 12)}{24} \leq 2280 \Rightarrow n \leq 48$

Bài 11. (China MO 1996)

Có 8 ca sĩ tham gia một chương trình văn nghệ với tổng cộng $m$ buổi hòa nhạc. Trong mỗi buổi hòa nhạc, có 4 ca sĩ tham gia và số lần tham gia của mỗi cặp ca sĩ là như nhau và bằng $n$ .
Tìm giá trị nhỏ nhất của $m$ .

Lời giải

Ta gọi $S$ là số bộ $(A, b, c)$ trong đó ca sĩ $b, c$ cùng tham gia buổi hòa nhạc $A .$

Vi hai ca sĩ bất kì cùng tham gia biểu diễn $n$ buổi nên $S = n C_{8}^{2}$ .

Mặt khác có $m$ buổi biểu diễn và mỗi buổi có đúng 4 ca sĩ tham gia nên $S = m C_{4}^{2}$

Do vậy $n C_{8}^{2} = m C_{4}^{2}$ hay $14 n = 3 m .$ Suy ra $14 ∣ m$ nên $m \geq 14$ . Giá trị nhỏ nhất của $m$ là 14 .

Dưới đây là một sách sắp xếp như vậy

Bài 12. (VMO 2005)

Cho bát giác lồi $A_{1} A_{2} \dots A_{8}$ mà không có ba đường chéo nào đồng quy. Giao của hai đường chéo tùy ý được gọi là một “nút”. Xét tất cả các tứ giác lồi được tạo thành bởi bốn đỉnh của bát giác đã cho và các tứ giác đó được gọi là “tứ giác con”. Hãy xác định số nguyên dương $n$ nhỏ nhất sao cho có thể tô màu $n$ nút để với mọi $i \neq k$ và $i, k \in 1, 2, \dots, 8$ thì các số $s (i, k)$ bằng nhau, trong đó $s (i, k)$ ký hiệu số tứ giác con nhận $A_{i}, A_{k}$ làm đỉnh và giao của hai đường chéo là một nút được tô màu.

Lời giải

Bài toán này chính là bài toán China MO 1996. Thật vậy nếu ta coi các đỉnh của đa giác là các ca sĩ. Mỗi một nút được tô màu là là một buổi biểu diễn. Khi đó số $s (i, k)$ chính là số buổi biểu diễn mà ca sĩ $A_{i}, A_{k}$ cùng tham gia.

Bài 13. (Chọn đội tuyển PTNK 2014)

Cho tập hợp $X = 1, 2, 3, \dots, 19$ và xét một họ $Ω$ gồm $k$ tập con có 7 phần tử của $X$ . Một tập hợp $A \subset X$ được gọi là “tập mẹ” của họ $Ω$ nếu như $A$ có 8 phần tử và tồn tại một tập hợp $B \in Ω$ sao cho $B \subset A .$ Gọi $d$ là số tất cả các tập mẹ của $Ω .$ Chứng minh rằng $d \geq \frac{3}{2} k$ .

Lời giải

Gọi $S$ là số bộ $(B, A)$ sao cho $B$ thuộc họ $Ω$ và $A$ là mẹ của $B$ .

Vì một tập $B$ thì có 7 phần tử, vậy $A$ muốn là mẹ của $B$ thì $A$ phải bổ sung thêm một trong 12 phần tử còn lại. Tức là mỗi tập $B$ sẽ có 12 tập mẹ. $S = k .12$ Mỗi tập $A$ có 8 tập con có 7 phần tử nên mỗi tập mẹ $A$ có nhiều nhất 8 tập $con B .$ Ta có $S \leq 8 d$

Suy ra: $12 k \leq 8 d$ . Vậy $d \geq \frac{3}{2} k$

Bài 14. (Russia 1996)

Ở một thành phố nọ, có 1600 đại biểu tham gia vào 16000 ủy ban và mỗi ủy ban có đúng 80 người tham gia. Chứng minh rằng có 2 ủy ban nào đó có ít nhất 4 đại biểu tham gia chung.

Lời giải

Gọi $a_{i}$ là số ủy ban mà đại biểu thứ $i$ tham gia. Ta gọi $T$ là số bộ $(x, Y)$ mà đại biểu $x$ tham gia ủy ban $Y$ .

Trước hết ta đếm theo $Y$ thì $T = 16000.80$ .

Bây giờ ta đếm theo $x$ thì $T = \sum_{i = 1}^{1600} a_{i}$ .

Suy ra $\sum_{i = 1}^{1600} a_{i} = 16000.80$

Ta chứng minh bằng phản chứng, giả sử 2 ủy ban bất kì có không quá 3 đại biểu chung.

Ta gọi $S$ là số bộ $(x, V, U)$ trong đó đại biểu $x$ cùng tham gia cả 2 ủy ban $U$ và $V$ . Ta có $S \leq 3 C_{16000}^{2}$

Bây giờ ta đếm theo $x$ thì $S = \sum_{i = 1}^{1600} C_{a_{i}}^{2} \geq \frac{T (T - 1600)}{2.1600}$ .

Từ đó ta rút ra điều vô lý.

Bài 15. (Bulgari MO 2006)

Một quốc gia có 16 thành phố và có 36 tuyến bay nối giữa chúng (chuyến bay ở đây là hai chiều). Chứng minh rằng ta có thể tổ chức một chuyến bay vòng quanh giữa 4 thành phố nào đó.

Lời giải

Ta chứng minh bằng phản chứng. Giả sử với 2 sân bay $A, B$ bất kì có không quá một thành phố $C$ có thể bay đến cả $A$ và $B$ .

Gọi $T$ là số bộ $(A, B, C)$ mà cả $A, B$ cùng bay được đến $C$ . Ta có $T \leq C_{16}^{2} = 120$

Giả sử thành phố thứ $i$ có thể bay đến được $a_{i}$ thành phố khác. Thì $\sum_{i = 1}^{16} a_{i} =$ $72 .$

Khi đó: $\sum_{i = 1}^{16} C_{a_{i}}^{2} \geq \frac{72 (72 - 16)}{2.16} > 120$ . Vô lý.

Bài 16. (Chọn đội tuyển Bình Thuận)

Trong một hội nghị có 155 đại biểu tham dự và có 2015 cặp đại biểu quen biết nhau. Chứng minh rằng có thể chọn ra 4 đại biểu để xếp lên một bàn tròn sao cho hai đại biểu ngồi cạnh nhau thì có quen biết nhau.

Lời giải

Bài này cách giải hoàn toán giống bài Bulgari MO $2006 .$

Bài 17.

Trong một trường có 1001 học sinh tham gia vào một số câu lạc bộ, các câu lạc bộ hợp với nhau để tổ chức $m$ hoạt động xã hội (một hoạt động có thể được tổ chức bởi một hoặc nhiều câu lạc bộ). Biết rằng
i) Mỗi câu lạc bộ đều có lẻ thành viên và nếu câu lạc bộ có $k$ thành viên thì nó tổ chức $\frac{k - 1}{2}$ hoạt động xã hội;
ii) Với mỗi học sinh bất kì và một hoạt động bất kì thì có đúng một câu lạc bộ vừa tổ chức hoạt động xã hội đó và nhận học sinh đó là thành viên;
iii) Hai học sinh bất kì tham gia đúng một câu lạc bộ;

Tìm $m$ .

Lời giải

Gọi $S$ là số bộ $(t, C, H)$ mà học sinh $t$ tham gia câu lạc bộ $C$ và câu lạc bộ $C$ tổ chức hoạt động $H$ . Vì với mỗi cặp $t$ và $H$ chỉ tồn tại duy nhất một $C$ nên $S = 1001 m$

Nếu một câu lạc bộ có $k$ thành viên thì nó tổ chức $\frac{k - 1}{2}$ . Giả sử có $n$ câu lạc bộ và câu lạc bộ thứ $i$ có $k_{i}$ thành viên thì $S = \sum_{i = 1}^{n} k_{i} \frac{k_{i} - 1}{2}$ .
Suy ra $\sum_{i = 1}^{n} \frac{k_{i}^{2} - k_{i}}{2} = 1001 m$ .
Gọi $T$ là số bộ $(a, b, C)$ là hai học sinh $a, b$ cùng tham gia câu lạc bộ $C$ . Vi hai học sinh bất kì chỉ tham gia đúng một câu lạc bộ nên $T = C_{1001}^{2}$ .
Mặt khác câu lạc bộ thứ $i$ có $k_{i}$ thành viên nên $T = \sum_{i = 1}^{n} C_{k_{i}}^{2}$ .
Suy ra $\sum_{i = 1}^{n} \frac{k_{i}^{2} - k_{i}}{2} = C_{1001}^{2}$
Vậy $10001 m = C_{10001}^{2}$ nên $m = 500$ .

Bài 18.

Một trường có $n$ học sinh và $m$ câu lạc bộ. Mỗi câu lạc bộ có ít nhất 2 thành viên. Nếu 2 câu lạc bộ có nhiều hơn một thành viên chung thì sô thành viên của 2 câu lạc bộ khác nhau.

a) Gọi $a_{i}$ là số câu lạc bộ có $i$ thành viên. Chứng minh $a_{i} \leq \frac{C_{n}^{2}}{C_{i}^{2}}$ ;

b) Chứng minh $m \leq n - 1$ ;

Lời giải

a) Ta gọi $S$ là số bộ $(x, y, C)$ mà hai học sinh $x, y$ cùng tham gia CLB C có $i$ thành viên. Trước hết ta đếm theo $x$ và $y$ . Vi 2 câu lạc bộ có cùng hai thànhviên $x, y$ chung thì số thành viên của 2 câu lạc bộ khác nhau nên có nhiều nhất một câu lạc bộ có $i$ thành viên và chứa $x, y$ .
Suy ra $S \leq C_{n}^{2}$
Bây giờ ta đếm theo $C$ , số câu lạc bộ có $i$ thành viên là $a_{i}$ nên số cách chọn $C$ là $a_{i}$ . Với mỗi câu lạc bộ có $i$ thành viên số số cách chọn $x, y$ là $C_{i}^{2}$ nên $S = a_{i} C_{i}^{2}$ suy ra $a_{i} C_{i}^{2} \leq C_{n}^{2}$
Vậy $a_{i} \leq \frac{C_{n}^{2}}{C_{i}^{2}}$ .
b) Ta có
$\begin{matrix} m = \sum_{i = 2}^{n} a_{i} \leq \sum_{i = 2}^{n} \frac{C_{n}^{2}}{C_{i}^{2}} = \sum_{i = 2}^{n} \frac{n (n - 1)}{i (i - 1)} \\ = n (n - 1) \sum_{i = 2}^{n} (\frac{1}{i - 1} - \frac{1}{i}) = n (n - 1) (1 - \frac{1}{n}) = (n - 1)^{2} \end{matrix}$

Bài 19.

Cho 6 điểm nằm trong mặt phẳng và không có ba điểm nào thẳng hàng. Mỗi cạnh nối hai điểm được tô bởi hai màu xanh / đỏ. Hỏi có ít nhất bao nhiêu tam giác được tô cùng màu?

Lời giải

Gọi $S$ là số bộ $(A, B, C)$ sao cho cạnh $A B, A C$ được tô cùng màu.

Giả sử số tam giác được tô cùng màu là $n$ thì số tam giác được tô không cùng màu là $C_{6}^{3} - n = 20 - n$

Với mỗi tam giác cùng màu số bộ $(A, B, C)$ là $3 .$

Với mỗi tam giác không được tô cùng màu thì số bộ $(A, B, C)$ là 1 . Vậy $S = 3 n + 20 - n = 20 + 2 n$ .

Với mỗi đỉnh $C$ là gọi $a_{1}$ là số cạnh màu đỏ nhận $C$ làm đầu mút và $a_{2}$ là số cạnh màu xanh nhận $C$ làm đầu mút. Ta có $a_{1} + a_{2} = 5$ .

Và $C_{a_{1}}^{2} + C_{a_{2}}^{2} \geq C_{3}^{2} + C_{2}^{2} = 4$ nên $S \geq 6.4 = 24$ .

Suy ra $20 + 2 n \geq 24$ nên $n \geq 2$ .

Bài 20. (Ukraina TST 2013)

Cho đa giác lồi có 17 đỉnh $A_{1} A_{2} A_{3} \dots A_{17}$ và với hai đỉnh $A_{i}, A_{j}$ bất kỳ trong số các đỉnh của đa giác, ta định hướng cho đoạn thẳng nối chúng để có vectơ: $\vec{A_{i} A_{j}}$ hoặc $\vec{A_{j} A_{i}}$ . Sau khi thực hiện với mọi cặp đỉnh, gọi $S$ là số tam giác có tổng các vectơ đặt trên 3 cạnh là $\vec{0}$ . Tim GTNN và GTLN của $S .$

Lời giải

Gọi số tam giác có tổng các vector trên 3 cạnh bằng $\vec{0}$ là $n$ .
Ta gọi $S$ là số bộ 3 diểm $(A, B, C)$ trong 17 đỉnh mà có hai vector $\vec{A C}, \vec{B C}$ hoặc $\vec{CA}, \vec{CB}$ tức là với với các vector đặt trên hai cạnh $A C, B C$ thì $C$ cùng là điểm đầu hoặc cùng là điểm cuối.

Với mỗi tam giác mà tổng các vector đặt trên các cạnh bằng $\vec{0}$ thì số bộ như trên bằng 0 .

Với mỗi tam giác mà tổng các vector đặt trên các cạnh khác $\vec{0}$ thì số bộ như trên bằng 2 .

Vậy $S = 2 (C_{17}^{3} - n) = 1360 - 2 n$

Với mỗi điểm $A_{i}$ ta gọi $d_{i}$ là số vector nhận $A_{i}$ là điểm đầu và $c_{i}$ là số vector nhận $A_{i}$ là điểm cuối.

Ta có $d_{i} + c_{i} = 16$ và $C_{c_{i}}^{2} + C_{d_{i}}^{2} \geq \frac{16 (16 - 2)}{2.2} = 56$ .

Nên $S \geq 56.17 = 952$

Suy ra $1360 - 2 n \geq 952 \Rightarrow n \leq 204$

Bài 21. (China MO 2007).

Trong một trường THPT, có 2007 học sinh nam và 2007 học sinh nữ. Mỗi học sinh tham gia không quá 100 CLB ở trường. Biết rằng hai học sinh bất kỳ khác giới tính đều có tham gia ít nhất 1 CLB chung nào đó. Chứng minh rằng có 1 CLB mà có ít nhất 11 thành viên nam và 11 thành viên nữ.

Lời giải

Ta chứng minh bằng phản chứng, giả sử mỗi câu lạc bộ đều có nhiều nhất 10 học sinh nam hoặc nhiều nhất 10 học sinh nữ. Gọi $S$ là số bộ $(A, B, C)$ mà học sinh nam $A$ và học sinh nữ $B$ tham gia câu lạc bộ $C$ .

Vì mỗi học sinh nam và học sinh nữ bất kì tham gia ít nhất một câu lạc bộ nên $S \geq 2007^{2}$

Ta chia các câu lạc bộ thành 2 trường hợp.

TH1: Câu lạc bộ có không quá 10 nam. Số học sinh nữ là 2007 và mỗi học sinh tham gia không quá một câu lạc bộ nên số cặp $(B, C)$ trong trường hợp này không vượt quá: 2007.100 vì thế số bộ $(A, B, C)$ không vượt quá 10.2007.100.

TH2: Câu lạc bộ có không quá 10 nữ. Số bộ $(A, B, C)$ trong trường hợp này không quá 2007.10.100.

Suy ra: $S \leq 2.2007 .10 .100 = 2000.2007$

Vi vậy $2007^{2} \leq 2000.2007$ . Vô lý.

Bài 22. (Trường Xuân 2013)

Cô giáo có tất cả $X$ viên kẹo gồm 11 loại kẹo khác nhau. Cô chia cho các học sinh của mình mỗi người một số viên kẹo và không có học sinh nào nhận nhiều hơn một viên kẹo ở cùng một loại kẹo. Cô yêu cầu hai học sinh khác nhau bất kì so sánh các viên kẹo mình nhận được và viết số loại kẹo mà cả hai cùng có lên bảng. Biết rằng mỗi cặp bất kì đều được lên bảng đúng một lần. Gọi tổng các số được viết lên bảng là $M$ . Xác định giá trị nhỏ nhất của $M$ .

a) Khi $X = 2013$

b) Khi $X = 2017$

Lời giải

Ta đánh số các loại kẹo từ 1 đến 11 giả sử số viên kẹo loại $i$ là $a_{i}$ . Ta có $\sum_{i = 1}^{11} a_{i} = X .$ Ta thấy $M = \sum_{i = 1}^{11} C_{a_{i}}^{2}$

a) Khi $X = 2013$ ta có $11 ∣ 2013$

Ta thấy $M \geq \frac{2013 (2013 - 11)}{2.11} = 183183$ Đẳng thức xảy ra khi $a_{i} = \frac{2013}{11} = 183$

b) Khi $X = 2017$ ta có $2017 = 11.183 + 4$ nên

$M \geq 7 C_{183}^{2} + 4 C_{184}^{2} = 183915$

Bài 23. (IMO 1998)

Trong một cuộc thi có $a$ thí sinh và $b$ giám khảo, trong đó $b \geq 3$ là một số nguyên lẻ. Mỗi giám khảo đánh giá một thí sinh là “đạt” hoặc “trượt”. Giả sử $k$ là một số sao cho, với 2 giám khảo bất kì, đánh giá của họ là như nhau với nhiều nhất $k$ thí sinh. Chứng minh rằng

$\frac{k}{a} \geq \frac{b - 1}{2 b}$

Lời giải

Gọi $T$ là số bộ $({g_{1}, g_{2}}, s)$ trong đó giám khảo $g_{1}$ và $g_{2}$ có cùng đánh giá với thí sinh $s .$

Vi hai giám khảo bất kì có cùng đánh giá với nhiều nhất $k$ thí sinh nên $T \leq k C_{b}^{2}$

Với một thí sinh $s$ bất kì, giả sử có $p$ giám khảo đánh giá “đạt” và $q$ giám khảo đánh giá “trượt”. Ta có $p + q = b$ và số cặp giám khảo có cùng đánh giá với s là:

$C_{p}^{2} + C_{q}^{2} = \frac{p^{2} + q^{2} - p - q}{2} \geq \frac{\frac{(b - 1)^{2}}{4} + \frac{(b + 1)^{2}}{4} - b}{2} = \frac{(b - 1)^{2}}{4}$

Bài 24. (China TST 1992)

Có 16 học sinh tham gia một cuộc thi có $n$ câu hỏi và mỗi câu hỏi có 4 lựa chọn. Biết rằng 2 học sinh bất kì có không quá 1 câu trả lời chung cho tất cả các câu hỏi. Tìm giá trị lớn nhất của $n$ .

Lời giải

Gọi $S$ là số bộ $({h_{1}, h_{2}}, c)$ mà 2 học sinh $h_{1}$ và $h_{2}$ có cùng câu trả lời với câu hỏi $c$ .

Vi 2 học sinh có không có quá một câu trả lời chung cho các các câu hỏi nên $S \leq C_{16}^{2} = 120$

Với mỗi câu hỏi $c$ có bốn phương án trả lời, gọi số thí sinh chọn phương án thứ $i$ là $a_{i}$ . Ta có $\sum_{1}^{4} a_{i} = 16$

Khi đó số cặp thí sinh ${h_{1}, h_{2}}$ mà có cùng câu trả lời cho câu hỏi $c$ là:
$C_{a_{1}}^{2} + C_{a_{2}}^{2} + C_{a_{3}}^{2} + C_{a_{4}}^{2} \geq \frac{16 (16 - 4)}{2.4} = 24$
Ta có: $S \geq 24 n$ .
Suy ra $24 n \leq 120$ hay $n \leq 5$ .

Bài 25.

Một CLB có $n$ thành viên và họ đã tham gia vào 12 buổi chuyên đề, mỗi buổi có 24 thành viên tham gia. Biết rằng hai thành viên bất kỳ tham gia chung không quá một buổi.

a) Tìm giá trị nhỏ nhất của $n$ ;

b) Câu hỏi tương tự nếu có 10 buổi chuyên đề và mỗi buổi có 7 thành viên tham gia.

Lời giải

a) Trước hết ta chuyển đổi giả thiết của bài toán “hai thành viên bất kỳ tham gia chung không quá một buổi” thành “hai buổi bất kì có không quá một thành viên chung”.

Ta đánh số các thành viên từ 1 đến $n .$ Gọi $a_{i}$ số buổi chuyên đề mà thành viên thứ $i$ tham gia thì $\sum_{i = 1}^{n} a_{i} = 12.24 = 288$

Gọi $T$ là số bộ $(a, B, C)$ mà thành viên $a$ tham gia vào cả 2 buổi chuyên đề $B, C$ . Vi hai buổi bất kì có không quá một thành viên chung nên $T \leq C_{12}^{2} = 66$ . Ta có $T = \sum_{i = 1}^{n} C_{a_{i}}^{2} \geq \frac{288 (288 - n)}{2 n}$

Suy ra: $66 \geq \frac{288 (288 - n)}{2 n}$ . Dẫn đến $n \geq 198$ .

Ta thấy $⌊ \frac{288}{198} ⌋ = 1$ nên các số $a_{i}$ chỉ nhận giá trị bằng 1 hoặc 2 . Giả sử có $k$ số $a_{i}$ bằng 1 khi đó $T = k$ suy ra $k \leq 66$

Suy ra: $288 = 2 k + (n - k) = n + k \leq n + 66$ . Vậy $n = 222$ là giá trị nhỏ nhất.

Khi đó ta có 66 số $a_{i}$ bằng 2 và 156 số $a_{i}$ bằng $1 .$

b) $\sum_{i = 1}^{n} a_{i} = 10.7 = 70$

Gọi $T$ là số bộ $(a, B, C)$ mà thành viên $a$ tham gia vào cả 2 buổi chuyên đề $B, C$ . Vi hai buổi bất kì có không quá một thành viên chung nên $T \leq C_{10}^{2} = 45$ .

Ta có $T = \sum_{i = 1}^{n} C_{a_{i}}^{2} \geq \frac{70 (70 - n)}{2 n}$

Suy ra: $45 \geq \frac{70 (70 - n)}{2 n}$ . Dẫn dến $n \geq 31$

Ta thấy $⌊ \frac{70}{31} ⌋ = 2$ nên các số $a_{i}$ chỉ nhận giá trị bằng 2 hoặc $3 .$

Giả sử có $k$ số $a_{i}$ bằng 3 khi đó $T = n - k + 3 k = n + 2 k$ suy ra $n + 2 k \leq 45$ .

Suy ra: $70 = 3 k + 2 (n - k) = 2 n + k = \frac{3 n}{2} + \frac{n}{2} + k \leq \frac{3 n}{2} + \frac{45}{2}$ . Vậy $n \geq 32$ .

Vậy giá trị nhỏ nhất của $n$ là 32 . Khi đó ta có $k = 6$ số $a_{i}$ bằng 3 và 26 số $a_{i}$ bằng 2 .

Bài 26.

Trên mặt phẳng cho tập hợp $A$ gồm 66 điểm phân biệt và tập hợp $B$ gồm 16 đường thẳng phân biệt. Gọi $m$ là số bộ $(a, b)$ sao cho $a \in A, b \in$ $B$ , $a \in b$ . Chứng minh rằng $m \leq 159$ .

Lời giải

Để $m$ đạt giá trị lớn nhất thì tất cả điểm của $A$ phải thuộc vào các đường thẳng của $B$ . Ta đặt tên các điểm là $A_{1}, \dots, A_{66} .$ Gọi số đường thẳng trong tập $B$ đi qua điểm $A_{i}$ là $a_{i}$ . Ta có $\sum_{i = 1}^{16} = m$ .

Gọi $T$ là số bộ $(X, d_{i}, d_{j})$ mà $X \in A$ là giao điểm của $d_{i}$ và $d_{j}$ và $d_{i}, d_{j} \in B$ . Rõ ràng $T \leq C_{16}^{2} = 8.15 = 120$
Mặt khác $T = \sum_{i = 1}^{66} C_{a_{i}}^{2} \geq \frac{m (m - 66)}{2.66}$ .
Ta có: $120 \geq \frac{m (m - 66)}{2.66}$ . Suy ra $m \leq 163$ .
Ta có $⌊ \frac{m}{66} ⌋ \leq 2$ nên ta dự đoán giá trị nhỏ nhất của $m$ ra khi $a_{i}$ nhận các giá trị là 2 hoặc $3 .$
Giả sử có $k$ giá trị $a_{i}$ bằng 3 thì $m = 3 k + 2 (66 - k) = 132 + k$ .
Và $T = 3 k + (66 - k) = 66 + 2 k = 2 (k + 132) - 198 = 2 m - 198$ .
Suy ra: $2 m - 198 \leq 120$ nên $m \leq 159$ .
Đẳng thức xảy ra khi có 27 số $a_{i}$ nhận giá trị bằng 3 và 39 số $a_{i}$ nhận giá trị bằng 2 .

Nhận xét $2.5$ . Bài toán này thực tế giống bài toán trên vì có một tính chất mà người giải bài toán phải tự nhận thấy là “hai đường thẳng phân biệt có không quá một điểm chung”.

Bài 26.

Lời giải

Bài 27. (IMO Shortlist 1995)

Một cuộc họp có $12 k$ người và mỗi người bắt tay với đúng $3 k + 6$ người còn lại. Biết rằng với mọi cách chọn cặp hai người, số người bắt tay với cả hai là như nhau. Tính số người trong cuộc họp.

Lời giải

Gọi $S$ là số bộ $(a, b, c)$ mà $a$ bắt tay với cả $b, c$ .

Nếu ta đếm theo $a$ thì $S = 12 k C_{3 k + 6}^{2}$ . Với 2 người bất kì, thì số người bắt tay với cả 2 người không đổi, ta đặt bằng $m$ .

Nếu ta đếm theo $(b, c)$ thì $S = m C_{12 k}^{2}$ .

Suy ra $m = \frac{3 (k + 2) (3 k + 5)}{12 k - 1} = 3 \frac{3 k^{2} + 11 k + 10}{12 k - 1} \in Z$ .

Giải phương trình nghiệm nguyên ta được $k = 3$ và $m = 6$ .

Vậy cuộc họp có 36 người.

Bài 28.

Cho số nguyên tố $p$ . Trên bàn cờ hình vuông có cạnh $p^{2} + p + 1$ , tìm số lớn nhất các ô có thể tô màu sao cho không tồn tại hình chữ nhật có 4 đỉnh cùng màu và các cạnh song song với các cạnh của hình chữ nhật.

Lời giải

Giả sử ta tô màu $n$ ô.

Gọi $S$ là số bộ $(c_{i}, c_{j}, h_{k})$ trong đó các cột $c_{i}$ và $c_{j}$ và giao với hàng $h_{k}$ tại hai ô được tô màu.

Để không xuất hiện hình chữ nhật nào có bốn đỉnh được tô màu thì với mỗi hai cột $c_{i}$ và $c_{j}$ thì có nhiều nhất một hàng $h_{k}$ nên $S \leq C_{p^{2} + p + 1}^{2}$ .

Với mỗi hàng, ta giả sử số ô được tô màu trên hàng đó là $a_{i}$ thì

$\sum_{i = 1}^{p^{2} + p + a} a_{i} = n$

Khi đó $S = \sum_{i = 1}^{p^{2} + p + 1} C_{a_{i}}^{2} \geq \frac{n (n - p^{2} - p - 1)}{2 (p^{2} + p + 1)}$

Suy ra $C_{p^{2} + p + 1}^{2} \geq \frac{n (n - p^{2} - p - 1)}{2 (p^{2} + p + 1)}$

Từ đó ta thu được $n \leq (p + 1) (p^{2} + p + 1)$ .

Đẳng thức xảy ra khi mỗi hàng có $p + 1$ ô được tô màu và trên 2 cột bất kì chỉ có 2 ô nằm trên cùng một hàng được tô màu.

Việc chỉ ra một cách một cách tô màu thỏa mãn đẳng thức xin dành lại cho người đọc chuyên đề này.

3/ Ma trận liên thuộc

Bài 29. (Iran 1999)

Giả sử $C_{1}, C_{2}, \dots, C_{n} (n \geq 2)$ là các đường tròn bán kính 1 . Không có 2 đường tròn nào tiếp xúc. Bất kì một đường tròn nào cũng cắt ít nhất một đường tròn khác. Giả sử $S$ là tập hợp các điểm thuộc ít nhất 2 đường tròn (tập các giao điểm). Chứng minh rằng $| S | \geq n$ .

Lời giải

Gọi tập các đường tròn là $T$ Giả sử $| S | = s$

Với mỗi cặp $(d, C_{i})$ mà $d \in S$ và đường tròn $C_{i}$ đi qua $d$ .

Ta gọi $x (d, C_{i})$ là số đường tròn đi qua điểm $d$ .

Và $y (d, C_{i})$ là số điểm mà đường tròn $C_{i}$ đi qua.

Với điểm $d$ giả sử có một đường tròn $C_{j}$ nữa đi qua điểm $d$ thì đường tròn $C_{j}$ và $C_{i}$ cắt nhau tại một điểm $d^{'}$ nữa khác $d .$

Suy ra $x (d, C_{i}) \leq y (d, C_{j})$ .

Vì vậy ta có: $s = \sum_{\binom{d \in S, C \in T}{d \in C}} \frac{1}{x (d, C_{i})} \geq \sum_{d \in S, C \in T, C C} \frac{1}{y (d, C_{i})} = n$

Bài 30.

Cho $S_{1}, S_{2}, \dots, S_{m}$ là các tập con phân biệt của tập $1, 2, \dots, n$ sao cho $| S_{i} \cap S_{j} | = 1$ với mọi $i \neq j$ . Chứng minh rằng $m \leq n$ .

Lời giải

Ta phản chứng giả sử $m > n$ .

Ta thấy các tập $S_{i}$ đều phải khác rỗng và ta chỉ cần xét với $m \geq 2$ . Lời giải này sẽ được chúng tôi trình bày thông qua Ma trận liên thuộc. Trước hết ta lập một bảng ô vuông gồm $m$ dòng, dòng thứ $i$ sẽ ứng với tập $S_{i}$ và $n$ cột, cột thứ $j$ sẽ ứng với phần tử $j$ trong tập ${1, 2, \dots, n}$ . Ô ở vị trí giao của cột thứ $j$ và dòng thứ $i$ sẽ được điền vào giá trị $a_{i j}$ . Trong đó

$a_{i j} = {\begin{cases} 1 nếu j \in S_{i} \\ 0 nếu j \notin S_{i} \end{cases}$

Bây giờ ta xét trường hợp $a_{i j} = 0$ . Nếu trên cột $j$ có một số 1 giả sử là $a_{k j} = 1$ thì $| S_{k} \cap S_{i} | = 1$ nên trên dòng $i$ cũng có một số 1 . Và ta thấy rằng quy tắc này là một đơn ánh. Do đó, ta gọi $R_{i}$ là tổng các số trên dòng thứ $i$ và $C_{j}$ là tổng các số trên cột thứ $j$ thì $C_{j} < R_{i}$ .

Suy ra $m - C_{j} > n - R_{i}$ và $\frac{C_{j}}{m - C_{j}} < \frac{R_{i}}{n - R_{i}}$ .

Gọi $M$ là tổng các số trên bảng. Thì

\begin{gathered}

M=\sum_{j=1}^{n} C_{j}=\sum_{j=1}^{n}\left(m-C_{j}\right) \frac{C_{j}}{m-C_{j}}=\sum_{j=1}^{n}\left(\sum_{i=1}^{m}\left(1-a_{i j}\right)\right) \frac{C_{j}}{m-C_{j}}= \

=\sum_{j=1}^{n} \sum_{i=1}^{m} \frac{\left(1-a_{i j}\right) C_{j}}{m-C_{j}}<\sum_{j=1}^{n} \sum_{i=1}^{m} \frac{\left(1-a_{i j}\right) R_{i}}{n-R_{i}}=\sum_{i=1}^{m} \frac{R_{i}}{n-R_{i}}\left(\sum_{j=1}^{n}\left(1-a_{i j}\right)\right) \

=\sum_{i=1}^{m} \frac{R_{i}}{n-R_{i}}\left(n-R_{i}\right)=\sum_{i=1}^{m} R_{i}=M

\end{gathered}

Vô lý nên $m \leq n$

4/ Lựa chọn giữa đếm bằng hai cách và nguyên lý Dirichlet

Bài 31. (Chọn ĐT Lương Thế Vinh, Đồng Nai)

Trong một thư viện người ta quan sát thấy được:

i) Mỗi ngày có 5 người đọc sách.

ii) Hai ngày bất kì thì số người đọc sách là $9 .$

Hãy tính xem trong 1 tháng có bao nhiêu người đến đọc sách. Biết tháng đó có 30 ngày.

Lời giải

Lời giải. Giả sử có $n$ người đến đọc sách. Gọi tập hợp những người tham gia đọc sách ngày thứ $i$ là $A_{i}$ .

Giả sử $A_{1} = {b_{1}, \dots, b_{5}}$ . Mỗi phần tử của $A_{1}$ này phải thuộc vào các tập từ $A_{2}, \dots, A_{30} .$ Gọi $b_{1}$ là người tham gia nhiều ngày đọc sách nhất thì theo nguyên lý Drichlet thì $b_{1} \geq 6$
Giả sử $b_{1}$ tham gia đọc sách vào cách ngày $A_{i_{1}}, \dots, A_{i_{m}}$ với $m \geq 6$ Giả $A_{k}$ không chứa $b_{1} .$ Do $| B | = 5$ nên tồn tại hai tập $A_{i}$ và $A_{j}$ mà $A_{i_{j}} \cap B =$ $A_{i_{h}} \cap B .$ Mặt khác $| A_{i_{j}} \cap A_{i_{h}} | = 1$ nên $A_{i_{j}} \cap A_{i_{h}} = a_{1}$ . Vô lý.
Suy ra $a_{1} \in A_{k} \forall 1 \leq k \leq 30$
Vậy số người tham gia đọc sách là $n = 30.4 + 1 = 121$ .

Bài 32. (Chọn đội tuyển Việt Nam 2014)

Trong một kỳ thi có 100 thí sinh và 24 vị giám khảo. Mỗi thí sinh được hỏi bởi đúng 10 giám khảo. Chứng minh rằng có 7 giám khảo mà mỗi thí sinh đều được hỏi bởi ít nhất một trong số họ.

Lời giải

Ta chứng minh bằng phản chứng. Giả sử với 7 giám khảo bất kỳ luôn tồn tại một thí sinh không được hỏi bởi cả 7 giám khảo đó. Gọi $S$ là số bộ $({a_{1}, \dots, a_{7}}, h)$ mà $h$ không được hỏi bởi cả 7 giám thị $a_{1}, \dots, a_{7}$ .

Ta có $S \geq C_{24}^{7}$ .

Với mỗi thí sinh thì có 14 giám khảo không hỏi thí sinh đó. Nên $S = 100 C_{14}^{7}$ . Suy ra $C_{24}^{7} \geq 100 C_{14}^{7}$ . Điều này vô lý.

Tất nhiên bài tập này có thể giải bằng cách sử dụng nguyên lý Drichlet.

Bài tập tự luyện

Bài tập 33 (IMO 2001). Hai mươi mốt cô gái và 21 chàng trai đã tham gia vào một cuộc thi toán học. Cho biết rằng

i) mỗi thí sinh giải quyết nhiều nhất là sáu bài toán, và

ii) với mỗi cặp của một cô gái và một chàng trai, có ít nhất một bài đã được giải quyết bởi cả cô gái và chàng trai.

Chứng minh rằng có một bài được giải bởi ít nhất là ba cô gái và ít nhất là ba chàng trai.

Bài tập 34 (IMO 2005). Trong một cuộc thi toán học có 6 bài toán được đưa ra cho các thí sinh. Mỗi cặp bài tập được giải bởi nhiều hơn $\frac{2}{5}$ số thí sinh. Không có thí sinh nào giải được cả 6 bài. Chứng minh rằng có ít nhất 2 thí sinh mà mỗi người giải được đúng 5 bài.

Bài tập 35 (IMO 1987). Cho $p_{n} (k)$ là số hoán vị của tập $1, 2, \dots, n (n \geq 1)$ có đúng $k$ điể̉ cố định. Chứng minh rằng

$\sum_{k = 1}^{n} k \cdot p_{n} (k) = n!$

Bài tập 36. Cho $S$ là một tập với $| S | = n$ . Giả $S_{1}, \dots, S_{m}$ là các tập con của $S$ sao cho $S_{i} ⊄ S_{j} \forall i \neq j$ . Chứng minh rằng $m \leq C_{n}^{[\frac{n}{2}]}$

Bài tập 37. Cho các tập hợp $S_{1}, \dots, S_{m}$ , mỗi tập có 3 phần tử. Và $S = S_{1} \cup$ $S_{2} \cup \dots \cup S_{m}$ . Thỏa mãn:

i) $| S_{i} \cup S_{j} | = 1 \forall i \neq j;$

ii) $\forall x, y \in S, x \neq y$ thì tồn tại một tập $S_{i}$ mà $x, y \in S_{i}$ .

Chứng minh rằng: $| S | = 7$ và họ $S_{1}, \dots, S_{m}$ tồn tại.

Bài tập 38 (China TST 1990). Cho 7 điểm trên mặt phẳng và ta vẽ các đường tròn qua đúng 4 điểm nào đó trong số chúng. Tính số đường tròn lớn nhất có thể có.

Các bài toán tổ hợp trong kì thi Junior Bankan – P1

Leave a reply

Lê Phúc Lữ – Phạm Khánh Vĩnh

(Bài viết trích từ Tập san Star Education – Số 5)

Bài 1. (JBMO 1998)
Hỏi có tồn tại hay không $16$ số có ba chữ số tạo thành từ ba chữ số phân biệt cho trước mà không có hai số nào có cùng số dư khi chia cho $16$ ?

Lời giải

Câu trả lời là phủ định.
Giả sử tồn tại các số thỏa mãn đề bài thì vì chúng có số dư đôi một khác nhau nên sẽ có đầy đủ các số dư $0, 1, 2, 3, \dots, 15$ . Điều này có nghĩa là trong đó, có $8$ số chẵn và $8$ số lẻ. Suy ra, ba chữ số $a, b, c$ để tạo thành các số đã cho không thể có cùng tính chẵn lẻ. Ta có hai trường hợp:

Trong các số $a, b, c$ , có hai số chẵn là $a, b$ và số $c$ lẻ. Ta có tất cả $9$ số lẻ tạo thành từ các chữ số này là:
$a a c, a b c, a c c, b a c, b b c, b c c, c a c, c b c, c c c$ .
Gọi $a_{1}, a_{2}, \dots, a_{9}$ là số có hai chữ số tạo thành bằng cách xóa đi chữ số cuối từ dãy trên.
Rõ ràng số $\overset{―}{a_{i} k}$ và $\overset{―}{a_{j} k}$ với $i \neq j$ khác số dư với nhau theo modulo $16$ nếu như hiệu của chúng không chia hết cho $16$ , suy ra $a_{i} - a_{j}$ không chia hết cho $8.$ Tuy nhiên, ta lại có đến $9$ số nên điều này không thể xảy theo nguyên lý chuồng bồ câu.
Trong các số $a, b, c$ , có hai số lẻ là $a, b$ và số $c$ chẵn: cũng dẫn đến mâu thuẫn tương tự.

Vậy không tồn tại các số thỏa mãn đề bài.

Bài 2: (JBMO 2000)

Trong một giải thi đấu tennis, số lượng nam gấp đôi số nữ. Mỗi cặp vận động viên thi đấu với nhau đúng một lần và không có trận hòa, chỉ có thắng – thua. Tỷ số giữa trận thắng của nữ và của nam là $\frac{7}{5}$ . Hỏi có bao nhiêu vận động viên trong giải thi đấu?

Lời giải

Gọi số nam là $2 n$ , số nữ là $n$ và tổng số vận động viên là $3 n .$ Tổng số trận đấu là

$\frac{3 n (3 n - 1)}{2} .$ \medskip

Theo giả thiết thì số trận thắng bởi nam là $\frac{5}{12} \cdot \frac{3 n (3 n - 1)}{2} = \frac{5 n (3 n - 1)}{8} .$

Số trận đấu giữa các nam là $\frac{2 n (2 n - 1)}{2} = n (2 n - 1)$ và rõ ràng số trận này không vượt quá số trận thắng của các nam.

Suy ra $\frac{5 n (3 n - 1)}{8} \geq n (2 n - 1) \Leftrightarrow n \leq 3.$ Mặt khác, $5 n (3 n - 1)$ phải chia hết cho $8$ nên $n = 3.$ Do đó, số vận động viên của giải đấu là $9.$

Bài 3: (JBMO 2006)

Xét bảng ô vuông kích thước $2 n \times 2 n$ với $n$ nguyên dương. Người ta xóa đi một số ô của bảng theo quy tắc sau đây:

Nếu $1 \leq i \leq n$ thì ở dòng thứ $i$ , xóa $2 (i - 1)$ ô ở giữa.
Nếu $n + 1 \leq i \leq 2 n$ thì ở dòng thứ $i,$ xóa đi $2 (2 n - i)$ ô ở giữa.

Hỏi có thể phủ được bảng bởi tối đa bao nhiêu hình chữ nhật kích thước $2 \times 1$ và $1 \times 2$ (không nhất thiết phải phủ kín toàn bộ) sao cho không có hai hình chữ nhật nào chồng lên nhau?

Lời giải

Với mọi bảng kích thước $2 n \times 2 n,$ tổng số ô bị xóa đi là $2 \times 2 \times (1 + 2 + 3 + \dots + n - 1) = 2 n (n - 1) .$

Bảng sẽ còn lại ${(2 n)}^{2} - 2 n (n - 1) = 2 n (n + 1)$ ô, tức là phủ được tối đa $n (n + 1)$ ô vuông.

Với $n = 1, 2, 3, 4,$ ta có thể kiểm tra trực tiếp được rằng kết quả lần lượt sẽ là $2, 6, 12, 20$ bởi khi đó ta có thể phủ kín toàn bộ bảng. Còn với $n \geq 4$ , ta xét hai trường hợp:

Nếu $n$ lẻ, khi đó ta chia bảng $2 n \times 2 n$ đã cho thành $4$ hình vuông nhỏ thì rõ ràng, mỗi hình sẽ có $\frac{n (n + 1)}{2}$ ô còn trống. Tiếp theo, ta tô màu theo dạng bàn cờ cho bảng này (ô ở góc thì tô đen), ta sẽ có tất cả $\frac{{(n + 1)}^{2}}{4}$ ô đen và $\frac{n^{2} - 1}{4}$ ô trắng. Rõ ràng mỗi hình chữ nhật khi đặt lên bảng sẽ chứa một ô đen và một ô trắng nên số cặp ô trắng – đen tối đa trong hình vuông con là $\frac{n^{2} - 1}{4}$ , và tương ứng sẽ có tối đa $4 \cdot \frac{n^{2} - 1}{4} = n^{2} - 1$ hình chữ nhật $1 \times 2, 2 \times 1$ phủ được trên bảng.

Ngoài ra, giữa các hình vuông con cạnh nhau, ta còn có hai ô màu đen cạnh nhau nên ta có thể lát thêm vào đó tổng cộng $4$ hình chữ nhật nữa, tổng cộng là $n^{2} - 1 + 4 = n^{2} + 3$ .

Nếu $n$ chẵn, bằng cách tương tự trên, ta phủ được hình bởi tối đa $n^{2} + 4$ ô.

Tóm lại,

Với $n = 1, 2, 3, 4$ , đáp số lần lượt là $2, 6, 12, 20.$
Với $n > 4$ và $n$ lẻ thì đáp số là $n^{2} + 3.$
Với $n > 4$ và $n$ chẵn thì đáp số là $n^{2} + 4.$

Bài 4: (JBMO 2008)

Một bảng $4 \times 4$ được chia thành $16$ ô vuông con và tất cả đều được tô màu trắng. Hai ô vuông được gọi là kề nhau nếu chúng có chung một cạnh. Một thao tác hợp lệ bao gồm việc chọn một ô vuông và đổi màu tất cả các ô kề với nó (kể cả nó): trắng sang đen, đen sang trắng. Sau $n$ thao tác, tất cả ô vuông của bảng chuyển sang màu đen. Tìm tất cả các giá trị có thể có của $n .$

Lời giải

Ta thấy mỗi lần đổi màu không quá $5$ ô nên số lần đổi màu phải ít nhất là $4.$ Hơn nữa, ta cũng có thể đổi màu tất cả sang đen như hình bên dưới, các ô được đánh dấu là các ô được chọn trong các thao tác.

Mặt khác, với $n$ chẵn lớn hơn $4$ , ta có thể chọn một trong các điểm trên hai lần và khi đó, màu của chúng sẽ đổi từ trắng sang đen, đen sang trắng, tức là không bị ảnh hưởng. Điều này có nghĩa là ta cũng có thể chuyển tất cả các ô sang màu đen như trường hợp $n = 4.$ \medskip

Cuối cùng, ta sẽ chứng minh rằng $n$ lẻ không thỏa mãn đề bài.

Tô màu xanh các ô vuông như hình vẽ. Ta thấy rằng ở mỗi lần thao tác thì có số lẻ ô xanh bị thay đổi ( $1$ hoặc $3$ ) nên sau mỗi lần thao tác, số lượng ô trắng – đen trong vùng màu xanh bị thay đổi một số đồng dư $2$ modulo $4.$

Ban đầu chênh lệch đó là $10$ và nếu muốn đổi tất cả sang màu đen thì chênh lệch đó là $- 10$ ; tức là thay đổi $- 20$ , chia hết cho $4$ . Điều này không thể xảy ra nên $n$ lẻ không thỏa mãn đề bài.

Vậy các giá trị $n$ cần tìm là $n$ chẵn và $n \geq 4.$

Bài 5: (JBMO 2008)

Lời giải

Cuối cùng, ta sẽ chứng minh rằng $n$ lẻ không thỏa mãn đề bài.

Vậy các giá trị $n$ cần tìm là $n$ chẵn và $n \geq 4.$

Bài 6:

(JBMO 2010)

Một hình chữ nhật $9 \times 7$ được lát bởi hai loại gạch như hình bên dưới: chữ $L$ và hình vuông.

Tìm tất cả các giá trị có thể có của số lượng các viên gạch hình vuông đã được dùng.

Lời giải

Câu trả lời là $0$ hoặc $3.$

Gọi $x$ là số viên gạch chữ $L$ và $y$ là số viên gạch hình vuông $2 \times 2.$ Đánh dấu chéo $20$ hình vuông của hình chữ nhật như sơ đồ bên dưới.

Rõ ràng mỗi viên gạch sẽ chứa không quá một dấu chéo. Suy ra $x + y \geq 20.$

Ngoài ra ta cũng có $3 x + 4 y = 63.$

Từ đó suy ra $y \leq 3$ và $y$ chia hết cho $3$ , dựa theo điều kiện thứ hai.

Do đó $y = 0$ hoặc $y = 3.$ Dưới đây là các cách lát thỏa mãn điều kiện đó.

Bài 7: (JBMO 2013)

Cho $n$ là một số nguyên dương. Có hai người chơi là Alice và Bob chơi một trò chơi như sau:

Alice chọn $n$ số thực, không nhất thiết phân biệt.
Alice viết tất cả các tổng theo cặp của tất cả các số lên giấy và đưa nó cho Bob (rõ ràng có tất cả $\frac{n (n - 1)}{2}$ cặp và không nhất thiết phân biệt).
Bob sẽ thắng nếu như có thể tìm lại được $n$ số ban đầu được chọn bởi Alice.

Hỏi Bob có thể có cách chắc chắn thắng hay không với

$n = 5 ?$
$n = 6 ?$
$n = 8 ?$

Lời giải

1) Câu trả lời là khẳng định.

Giả sử các số Alice đã chọn là $a \leq b \leq c \leq d \leq e$ . Rõ ràng mỗi số xuất hiện trong các tổng đúng $4$ lần nên bằng cách cộng tất cả $10$ tổng và chia hết quả cho $4$ , Bod sẽ thu được

$a + b + c + d + e .$

Trừ đi tổng lớn nhất và nhỏ nhất, Bob sẽ thu được số lớn thứ ba là $c .$ Tiếp tục trừ $c$ vào tổng lớn thứ nhì, chính là $c + e$ thì Bob thu được $e .$ Trừ $e$ vào tổng lớn nhất, Bob thu được $d$ . Bằng cách tương tự, Bob sẽ tìm ra được các giá trị $a, b .$ \medskip

2) Câu trả lời là khẳng định. Giả sử các số Alice đã chọn là $a \leq b \leq c \leq d \leq e \leq f .$ Tương tự trên, ta cũng tính được tổng $S$ các số của bộ. Trừ $S$ cho tổng lớn nhất và nhỏ nhất, ta thu được tổng $c + d .$ \medskip

Trừ $S$ cho tổng lớn nhì và tổng nhỏ nhất, ta được $c + e .$ Trừ $S$ cho tổng lớn nhất và tổng nhỏ nhì, ta được $b + d .$

Từ đây suy ra $a + c = S - (b + d) - (e + f)$ , trong đó ta biết $e + f$ vì đó là tổng lớn nhất.

Lúc bấy giờ, Bob đã tìm được ba tổng $a + b, a + c, b + c$ nên sẽ tính được $T = a + b + c$ và dễ dàng tìm được $a, b, c .$ Tương tự, Bob có thể tìm được $d, e, f .$ \medskip

3) Câu trả lời là phủ định.

Ta thấy rằng có hai bộ tám số là $1, 5, 7, 9, 12, 14, 16, 20$ và $2, 4, 6, 10, 11, 15, 17, 19$ đều cho cùng $28$ tổng theo đôi một giống nhau nên chắc chắn rằng Bob không thể biết được bộ mà Alice đã chọn.

Bài 8: (JBMO 2014)

Với mỗi số nguyên dương $n$ , hai người $A, B$ chơi một trò chơi như sau: Cho một đống có $s$ viên sỏi và hai người chơi thay phiên nhau chơi, $A$ đi trước. Ở mỗi lượt, người chơi được bốc hoặc $1$ viên sỏi, hoặc một số $p$ nguyên tố các viên sỏi, hoặc một bội của $n$ các viên sỏi. Người bốc được viên cuối cùng là chiến thắng. Giả sử hai người đều chơi với chiến thuật tối ưu, hỏi có bao nhiêu giá trị $s$ để người $B$ có chiến thuật thắng?

Lời giải

Ta gọi các giá trị $s$ để cho người $A$ có chiến thuật thắng là vị trí thắng và các vị trí còn lại là vị trí thua. Ta cần tìm số lượng vị trí thua.

Giả sử có $k$ vị trí thua thuộc tập hợp $X = {s_{1}, s_{2}, s_{3}, \dots, s_{k}} .$

Trước hết, ta thấy rằng mỗi bội của $n$ là vị trí thắng (vì người $A$ có thể lấy tất cả các viên sỏi ở ngay lần đi đầu tiên). Khi đó, nếu có $s_{i} \equiv s_{j} (mod n)$ và $s_{i} > s_{j}$ thì ở lượt đi đầu tiên, $A$ bốc $s_{i} - s_{j}$ viên sỏi (vì số này chia hết cho $n$ ). Nhưng lúc đó, còn lại $s_{j}$ viên sỏi và đây là vị trí thua của $B$ nên sẽ là vị trí thắng của $A$ , mâu thuẫn.

Do đó, tất cả các số trong $X$ đều không đồng dư với nhau theo modulo $n$ hay $k = | X | \leq n - 1.$ \medskip

Ta sẽ chứng minh rằng $k = n - 1.$ Thật vậy,

Để có được điều đó, ta sẽ chỉ ra rằng ở mỗi lớp thặng dư khác $0$ của $n$ , luôn có một vị trí thua bằng phản chứng. Giả sử rằng tồn tại $r \in {1, 2, 3, \dots, n - 1}$ sao cho $m n + r$ là vị trí thắng với mỗi số nguyên dương $m .$ Gọi $u$ là vị trị thua lớn nhất (nếu $k > 0$ ) hoặc $0$ (nếu $k = 0$ ).

Đặt $s$ là bội chung nhỏ nhất của tất cả các số nguyên dương từ $2$ đến $u + n + 1.$ Khi đó, tất cả các số $s + 2, s + 3, \dots, s + u + n + 1$ đều là hợp số. \medskip

Xét số nguyên dương $m^{'}$ thỏa mãn

$s + u + 2 \leq m^{'} n + r \leq s + u + n + 1$ .

Để $m^{'} n + r$ là vị trí thắng thì phải có số tự nhiên $p$ là $1$ , là số nguyên tố hoặc là bội của $n$ sao cho hiệu $m^{'} n + r - p$ sẽ là vị trí thua, là $0$ hoặc là một số nhỏ hơn hoặc bằng $u .$ Chú ý rằng

$s + 2 \leq m^{'} n + r - u \leq p \leq m^{'} n + r \leq s + u + n + 1$

nên $p$ phải là hợp số, chứng tỏ $p$ chỉ có thể là bội của $n$ (theo giả thiết của đề bài). \medskip

Đặt $p = q n$ thì $m^{'} n + r - q = (m^{'} - q) n + r$ cũng sẽ là một vị trí thắng khác; tuy nhiên, theo nguyên lý trò chơi thì không thể đi từ vị trí thằng này đến vị trí thắng khác được. Điều mâu thuẫn này cho thấy không thể xảy ra trường hợp toàn bộ các số dạng $m n + r$ là vị trí thắng. \medskip

Từ đây ta suy ra rằng có ít nhất $n - 1$ vị trí thua nên từ các điều trên, ta thấy có đúng $n - 1$ vị trí thua hay có $n - 1$ vị trí mà người $B$ có chiến lược để thắng.

Bài 9: (JBMO 2015)

Một khối chữ $L$ bao gồm ba khối vuông ghép như một trong các hình bên dưới:

Cho trước một bảng $5 \times 5$ bao gồm $25$ ô vuông đơn vị, một số nguyên dương $k \leq 25$ và một số lượng tùy ý các khối chữ $L$ nêu trên. Hai người chơi $A, B$ cùng tham gia một trò chơi như sau: bắt đầu bởi $A$ , hai người sẽ lần lượt đánh dấu các ô vuông của bảng cho đến khi nào tổng số ô được đánh dấu bởi họ là $k .$ \medskip

Ta gọi một cách đặt các khối chữ $L$ trên các ô vuông đơn vị còn lại chưa được đánh dấu là tốt nếu như nó không bị chồng lên nhau, đồng thời mỗi khối đặt lên đúng ba ô vuông như một trong các hình ở trên. $B$ sẽ thắng nếu như với mọi cách đặt tốt ở trên, luôn luôn tồn tại ít nhất ba ô vuông đơn vị chưa được đánh dấu trên bảng. \medskip

Xác định giá trị $k$ nhỏ nhất (nếu có tồn tại) để $B$ có chiến lược thắng.

Lời giải

Ta sẽ chứng minh rằng $A$ sẽ thắng nếu $k = 1, 2, 3$ và $B$ thắng nếu $k = 4.$ Suy ra giá trị nhỏ nhất của $k$ là $4.$ \medskip

1) Nếu $k = 1$ thì người chơi $A$ sẽ đánh dấu ô ở góc trên bên trái và đặt các khối như bên dưới

Khi đó, rõ ràng $A$ thắng. \medskip

2) Nếu $k = 2$ thì vẫn tương tự trên, $A$ đánh dấu vào ô ở góc trên bên trái. Khi đó, cho dù $B$ đánh dấu ô nào đi nữa thì $A$ cũng sẽ có cách đặt tương tự như trên, thiếu đi nhiều nhất là $2$ ô thuộc cùng khối vuông chữ $L$ với ô mà $B$ chọn. Điều này chứng tỏ $A$ vẫn thắng. \medskip

3) Nếu $k = 3$ thì cũng tương tự, ở lượt sau, $A$ đánh dấu vào ô cùng khối chữ $L$ với ô mà $B$ đã đánh dấu. Khi đó, $A$ vẫn thắng. \medskip

4) Với $k = 4$ , ta sẽ chứng minh rằng $B$ sẽ luôn có chiến lược thắng cho dù $A$ đi thế nào đi nữa. Rõ ràng còn lại $21$ ô nên $A$ phải chọn cách đánh dấu sao cho có thể đặt được toàn bộ $7$ khối vuông chữ $L$ (vì nếu không thì sẽ còn lại ít nhất $3$ ô chưa được đặt). \medskip

Giả sử trong lượt đầu tiên, $A$ không chọn ô nào trong hàng cuối (vì nếu có thì ta xoay ngược bảng lại và lập luận tiếp một cách tương tự). Khi đó, $B$ sẽ chọn ô số $1$ như bên dưới.

Nếu trong lượt tiếp theo, $A$ không chọn ô nào trong các ô $2, 3, 4$ thì $B$ chọn ô số $3.$ Khi đó, rõ ràng ô số $2$ sẽ không thể đặt lên bởi bất cứ khối chữ $L$ nào và $B$ chiến thắng.
Nếu trong lượt tiếp theo, $A$ chọn ô số $2$ thì $B$ chọn ô số $5$ , dẫn đến ô số $3$ không thể đặt lên bởi khối $L$ nào.
Nếu trong lượt tiếp theo, $A$ chọn một trong hai ô $3$ hoặc $4$ thì $B$ chọn ô còn lại, kết quả tương tự trên, ô số $2$ cũng sẽ không thể tiếp cận.

Vậy nói tóm lại, $k = 4$ là giá trị nhỏ nhất cần phải tìm.

Bài 10: (JBMO 2016)

Một bảng kích thước $5 \times 5$ được gọi là “tốt” nếu như mỗi ô của nó có chứa một đúng bốn giá trị phân biệt, và mỗi giá trị xuất hiện đúng một lần trong tất cả các bảng con $2 \times 2$ của bảng đã cho. Tổng tất cả các số có trên bảng được gọi là “giá” của bảng. Với mỗi bộ bốn số thực, ta có thể xây dựng tất cả các bảng tốt và tính giá của nó. Tính số giá phân biệt lớn nhất có thể có.

Lời giải

Ta sẽ chứng minh rằng số giá phân biệt lớn nhất là $60.$ Ta có nhận xét sau: \medskip

Nhận xét: Trong mỗi bảng tốt, mỗi hàng chứa đúng hai số trong các số hoặc mỗi cột chứa đúng hai số trong các số. \medskip

Thật vậy, ta thấy mỗi hàng của bảng đều chứa ít nhất hai số (vì nếu chứa toàn bộ là một số thì mâu thuẫn với giả thiết). Khi đó, nếu toàn bộ các hàng đều chứa hai số thì nhận xét đúng. \medskip

Giả sử ngược lại là có hàng $R$ chứa ít nhất ba số trong bốn số của bảng là $x, y, z, t$ . Khi đó, các số đó phải có nằm ở vị trí liên tiếp nào đó trên hàng, giả sử là $x, y, z$ liên tiếp. Theo giả thiết thì trong mỗi bảng $2 \times 2$ , ta đều có đủ bốn giá trị nên trong hàng phía trên và phía dưới của $R$ phải chứa $z, t, x$ theo đúng thứ tự đó, và tương tự là $x, y, z$ . Ta có bảng như bên dưới

* & x & y & z & * \

* & z & t & x & * \

* & x & y & z & * \

* & z & t & x & * \

* & x & y & z & * \

Điền thêm các ô còn lại, dễ thấy rằng các cột đều chứa đúng hai số. Nhận xét được chứng minh. \medskip

Không mất tính tổng quát, ta có thể giả sử mỗi hàng của bảng đều có đúng hai số (nếu không thì có thể xoay bảng lại). Nếu không xét hàng đầu tiên và cột đầu tiên, ta sẽ có bảng $4 \times 4$ mà trong đó, mỗi số trong $x, y, z, t$ đều xuất hiện $4$ lần nên tổng các số trong bảng này là $4 (x + y + z + t) .$

Do đó, ta chỉ cần tính xem có bao nhiêu cách khác nhau để đặt các số lên hàng đầu tiên $R_{1}$ và cột đầu tiên $C_{1} .$ Gọi $a, b, c, d$ là số lần xuất hiện của các số $x, y, z, t$ thì khi đó, tổng tất cả các số của bảng sẽ là

$4 (x + y + z + t) + x a + y b + z c + t d .$

Nếu hàng $1 - 3 - 5$ chứa các số $x, y$ với $x$ ở vị trí đầu tiên của hàng $1$ thì các hàng $2 - 4$ sẽ chứa các số $z, t$ (theo giả sử ở trên). Khi đó, ta có

$a + b = 7$ và $a \geq 3, b \geq 2$ ,

$c + d = 2$ và $c \geq d .$ \medskip

Khi đó $(a, b) = (5, 2), (4, 3)$ tương ứng với $(c, d) = (2, 0), (1, 1) .$ Suy ra $(a, b, c, d)$ sẽ nhận các bộ là $(5, 2, 2, 0), (5, 2, 1, 1), (4, 3, 2, 0), (4, 3, 1, 1) .$

Tổng số hoán vị của các bộ là $\frac{4!}{2!} + \frac{4!}{2!} + 4! + \frac{4!}{2!} = 60.$

Bằng cách chọn $x = 10^{3}, y = 10^{2}, z = 10, t = 1$ thì dễ thấy rằng các tổng tương ứng với mỗi hoán vị của bộ số trên đều phân biệt, nghĩa là giá của các bảng đều phân biệt. Vậy số lượng giá tối đa là $60.$

Dưới đây là một số bài toán để bạn đọc tự rèn luyện thêm:

Bài 11. (JBMO 2019) Cho bảng ô vuông $5 \times 100$ được chia thành $500$ ô vuông con đơn vị, trong đó có $n$ được tô đen và còn lại tô trắng. Hai ô vuông kề nhau nếu chúng có cạnh chung. Biết rằng mỗi ô vuông đơn vị sẽ có tối đa hai ô vuông đen kề với nó. Tìm giá trị lớn nhất của $n .$

Bài 12. (JBMO 2020) Alice và Bob chơi một trò chơi như sau: Alice chọn một tập hợp $A = 1, 2, \dots, n$ với $n \geq 2.$ Sau đó, bắt đầu bằng Bob, họ sẽ thay phiên chọn một số trong tập $A$ sao cho: đầu tiên Bob chọn bất kỳ số nào, sau đó, các số được chọn phải khác các số đã chọn và hơn kém đúng $1$ đơn vị so với số nào đó đã chọn. Trò chơi kết thúc khi tất cả các số trong $A$ đã được chọn. Alice thắng nếu tổng các số bạn ấy chọn được là hợp số. Ngược lại thì Bob thắng. Hỏi ai là người có chiến lược thắng?

Chỉnh hợp – Hoán vị – Tổ hợp

Chỉnh hợp

Mỗi cách sắp xếp $k$ phần tử (phân biệt) vào $n$ vị trí phân biệt ( $n \geq k$ ) được gọi là một chỉnh hợp chập $k$ của $n$ .

Tính chất. Số chỉnh hợp chập $k$ của $n$ là $A_{n}^{k} = \frac{(n!)}{(n - k)!}$

Hoán vị.

Mỗi chỉnh hợp chập $n$ của $n$ được gọi là một hoán vị, hay mỗi cách sắp xếp $n$ phần tử vào $n$ vị trí được gọi là một hoán vị của $n$ phần tử. Số hoán vị của $n$ phần tử là $P_{n} = n!$ .

Định nghĩa khác. Cho tập $A = 1, 2, \dots, n$ . Mỗi song ánh từ $A$ vào $A$ được gọi là một hoán vị.

Ví dụ 1. Có 8 bạn nam và 2 bạn nữ được xếp thành một hàng dài. Hỏi có bao nhiêu cách xếp thỏa:

a) Xếp bất kì.
b) 8 bạn nam kề nhau,2 bạn nữ kề nhau.
c) Các bạn nam giữa hai bạn nữ.

Ví dụ 2. Có 8 bạn nam và 4 bạn nữ. Có bao nhiêu cách sắp xếp các bạn này thành một hàng sao cho không có hai bạn nữ nào đứng kề nhau.

Ví dụ 3. Cho tập $A = 0, 1, 2, 3, 4, 5$ . Từ $A$ có thể lập được bao nhiêu số

a) Là số chẵn có 4 chữ số khác nhau.
b) Là số lẻ có 5 chữ số khác nhau và chia hết cho 3.

Tổ hợp. Cho tập hợp $A$ có $n$ phần tử. Một tập hợp con có $k$ phần tử của $A$ được gọi là một tổ hợp chập $k$ của $n$ phần tử.

Tính chất. Số tổ hợp có chập $k$ của $n$ là: [C_n^k = \dfrac{A_n^k}{k!} = \dfrac{n!}{(n-k)! k!}]

Ví dụ 4. Đội văn nghệ của trường gồm 4 bạn học sinh lớp 10, 5 học sinh lớp 11, 4 học sinh lớp 12.

a) Có bao nhiêu cách chọn ra hai bạn hát song ca?
b) Có bao nhiêu cách chọn ra 3 bạn hát tam ca mà mỗi khối có một học sinh?
c) Có bao nhiêu cách chọn ra một đội múa gồm 5 bạn trong đó có ít nhất 2 học sinh lớp 11.

Ví dụ 5. Cho tập $A = 1, 2, 3, 4, 5, B = a, b, c, d, e,$ , $C = x, y, z$ .

a) Có bao nhiêu song ánh từ $A$ vào $B$ .
b) Có bao nhiêu ánh xạ từ $A$ vào $C$ ? Có bao nhiêu đơn ánh từ $C$ vào $A$ .
c) Có bao nhiêu đơn ánh từ $C$ và $A$ sao cho $f (x) + f (y) + f (z)$ là số chẵn.

Bài tập rèn luyện

Bài 1. Cho tập $A = 0, 1, 2, 3, 4, 5, 6, a, b, c, d$

a) Có bao nhiêu hoán vị của $A$ .
b) Có bao nhiêu hoán vị của $A$ mà các chữ số đứng kề nhau.
c) Có bao nhiêu hoán vị của $A$ mà không có chữ cái nào đứng kề nhau?

Bài 2. Cho tập $A = 0, 1, 2, 3, 4, 5, 6$

a)Từ A có thể lập được bao nhiêu số có 5 chữ số khác nhau.
b) Có bao nhiêu hoán vị của A mà hai chữ số lẻ không đứng kề nhau.
c) Từ A có thể lập được bao nhiêu số có 4 chữ số mà chữ số đứng sau lớn hơn chữ số đứng liền trước.
d) Từ A có thể lập được bao nhiêu số có 3 chữ số chia hết cho 3.

Bài 3. Xếp $m$ bạn nam và $n$ bạn nữ thành 1 hàng, với $m, n \in N$ . Hỏi có bao nhiêu cách xếp nếu:

a) Xếp tùy ý;
b) Không có bạn nam nào đứng cạnh nhau $(m \leq n + 1);$
c) $n$ bạn nữ đứng liền kề nhau;
d) Một bạn nam A và một bạn nữ B đứng cạnh nhau.

Bài 4. Tính: $1 \cdot 1! + 2 \cdot 2! + 3 \cdot 3! + \cdot \cdot \cdot + n \cdot n!, n \in N .$

Bài 5. Tính: $\frac{1}{(1 + 1)!} + \frac{2}{(2 + 1)!} + \cdot \cdot \cdot + \frac{n}{(n + 1)!}$ với $n \in N .$

Bài 6. Cho $n, r \in N$ với $r \leq n .$ Chứng minh rằng:

a) $A_{n}^{r} = n A_{n - 1}^{r - 1};$
b) $A_{n}^{r} = (n - r + 1) A_{n}^{r - 1};$
c) $A_{n}^{r} = \frac{n}{n - r} A_{n}^{r - 1},$ với $r < n;$
d) $A_{n + 1}^{r} = A_{n}^{r} + r A_{n}^{r - 1};$
e) $A_{n + 1}^{r} = r! + r (A_{n}^{r - 1} + A_{n - 1}^{r - 1} + \dots + A_{r}^{r - 1}) .$

Bài 7. Một nhóm có 15 hóc sinh, trong đó có 5 bạn nữ. Hỏi có bao nhiêu cách chọn 9 học sinh sao cho có đúng 3 học sinh nữ:

a) để thành lập một hội đồng.
b) để thành lập một hội đồng với 9 vị trí khác nhau.

Bài 8. Có 10 cái ghế được xếp thành một hàng. 7 học sinh được xếp vào 7 cái ghế sao cho không có 2 học sinh nào ngồi chung một cái ghế. Hỏi có bao nhiêu cách xếp sao cho không có 2 cái ghế trống nào liền nhau.

Bài 9. Có 8 cái hộp được xếp thành hàng. Hỏi có bao nhiêu cách đặt 5 viên bi khác nhau vào các hộp nếu mỗi hộp chứa nhiều nhất 1 viên bi và không có hai hộp không chứa bi nào đứng cạnh nhau?

Bài 10. Xếp một nhóm có 20 học sinh, trong đó có 3 bạn nữ là: A, B, C và 4 bạn nam: X,Y,Z,T thành 2 hàng, mỗi hàng 10 học sinh. Hỏi có bao nhiêu cách xếp sao cho 3 bạn nữ luôn ở hàng trước, còn 4 bạn nam ở hàng phía sau.

Bài 11. Hỏi có bao nhiêu cách xếp 7 bạn nam và 2 bạn nữa thành một hàng sao cho các bạn gái cách nhau bởi đúng 3 bạn nam?

Bài 12. Tìm số $(m + n)$ -nhị phân là một dãy chữ số với $m$ số 0 và $n$ số 1 sao cho không có 2 số 1 nào đứng kề nhau, khi $n \leq m + 1.$

Bài 13. Lớp A có 10 bạn nữ và 15 bạn nam và lớp B có 4 nữ và 10 nam. Một hội đồng gồm 7 thành viên được chọn từ 2 lớp đó. Hỏi có bao nhiêu cách chọn các thành viên sao cho có đúng 4 bạn của lớp B và có đúng 5 bạn nam.

Bài 14. Trong mỗi trường hợp sau, tìm số tuyến đường ngắn nhất từ $O$ đến $P$ trong sơ đồ được cho dưới đây:
a) Tuyến đường phải đi qua $A$ .
b) Tuyến đường phải qua đoạn $A B$ .
c) Tuyến đường phải đi qua $A$ và $C$ .
d) Đoạn đường $A B$ bị đóng.

Bài 15. Tìm số cách chọn một nhóm gồm $2 k$ người từ $n$ cặp đôi, với $k, n \in N$ và $2 k \leq n,$ trong mỗi trường hợp sau đây:

a) Có $k$ cặp đôi trong nhóm đó.
b) Không có cặp đôi nào trong nhóm đó.
c) Có ít nhất một cặp đôi được chọn trong nhóm.

d) Có đúng 2 cặp đôi được chọn trong nhóm đó.

Bài 16. Cho một đa giác có 10 đỉnh.

a) Có bao nhiêu đường chéo.
b) Có bao nhiêu tam giác có 3 đỉnh là 3 đỉnh thuộc đa giác.
c) Có bao nhiêu tam giác có đúng 1 cạnh trùng với cạnh của đa giác.
d) Có bao nhiêu tam giác không có cạnh nào trùng với cạnh của đa giác.
e) Biết rằng không có 3 đường chéo nào đồng quy. Tìm số giao điểm của các đường chéo.

Bài 17. Cho đa giác đều có 100 cạnh. Hỏi có bao nhiêu hình chữ nhật tạo ra từ các đỉnh của đa giác trên.

Bài 18. Cho A là tập hợp các số nguyên dương từ 1 đến 100. Hỏi có bao nhiêu tập con có 3 phần tử của A thỏa:

a) Tổng các số chia hết cho 3
b) Tổng các số chia hết cho 4.

Bài 19. Chung kết cuộc thi tiếng hát học đường có 3 bạn vào chung kết, mỗi bạn hát 2 bài khác nhau. Hỏi có bao nhiêu cách sắp xếp chương trình sao cho không có ai hát liên tiếp.

Bài 20. Có bao nhiêu cách chọn ra 3 số từ tập $A = 1, 2, \dots, 100$ sao cho một số là trung bình cộng của hai số còn lại.

Các bài toán tổ hợp trên dãy số

CÁC BÀI TOÁN TỔ HỢP TRÊN DÃY SỐ

Thầy Lê Phúc Lữ

(Lớp Cao học Khoa học tự nhiên TP.HCM)

Trong bài viết nhỏ này, chúng ta sẽ cùng xét khía cạnh tổ hợp của dãy số nguyên; khi cần đếm số lượng dãy thỏa mãn một điều kiện cho trước nào đó. Các phương pháp thường gặp: truy hồi, xuống thang, cực hạn, phản chứng, …

1. Các bài toán chọn lọc

Bài tập 1.1: Tìm tất cả các bộ số nguyên dương $x_{1}, x_{2}, x_{3}, \dots, x_{2017}$ sao cho có thể đặt chúng lên vòng tròn theo thứ tự đó mà $6$ số liên tiếp bất kỳ đều có thể chia thành hai nhóm $3$ có tổng bằng nhau.

Giải

Dùng phương pháp xuống thang.

Ta có $x_{i} + x_{i + 1} + x_{i + 2} + x_{i + 3} + x_{i + 4} + x_{i + 5} \equiv 0 (\mod 2)$ với mọi $i = 1, 2, 3, \dots, 2017$ nên $x_{i} \equiv x_{i + 6}$ với mọi $i .$

Vì $(6, 2017) = 1$ nên suy ra tất cả các số có cùng tính chẵn lẻ. Ta xét phép biến đổi dãy số sau:

Nếu tất cả các số cùng chẵn thì thay bằng $y_{i} = \frac{x_{i}}{2}$ .
Nếu tất cả các số cùng lẻ thì thay bằng $y_{i} = \frac{x_{i} + 1}{2}$ .

Dễ thấy dãy mới cũng thỏa và tổng $S = \sum_{i = 1}^{2017} a_{i}$ sẽ giảm ngặt nếu có một số nào đó trong dãy khác $1$ ; suy ra quá trình biến đổi sẽ dừng lại khi tất cả đều là $1$ . Vì ta thu được một dãy toàn là $1$ nên dãy ban đầu có tất cả các số hạng bằng nhau.

Nhận xét: Bài toán trên có thể thay việc chia 2 nhóm thành $3, 4, 5, \dots$ nhóm và vẫn giải được bằng cách tương tự. Ta xét các bài tương tự sau:

Bài tập 1.2 (APMO 2017): Bộ năm số nguyên là tốt nếu có thể đặt chúng là $a, b, c, d, e$ để $a - b + c - d + e = 29.$ Tìm tất cả các bộ $2017$ số sao cho $5$ số liên tiếp bất kỳ trong chúng đều tốt.

Ở bài toán này, điểm khó là không biết các số đã cho có dương hay không; vì thể, đại lượng tổng ở trên không xét tiếp tục được.

Tuy nhiên, cách áp dụng vẫn tương tự như sau:

Trừ tất cả các số của bộ cho $29$ , ta thu được điều kiện tốt trở thành $a - b + c - d + e = 0.$
Tất cả các số đã cho cùng tính chẵn lẻ, và chính xác là cùng chẵn.
Xét đại lượng $S = \sum_{i = 1}^{2017} | \frac{a_{i}}{2} |$ thì thông qua phép chia 2, tổng này giảm ngặt. Từ đó suy ra tất cả các số này phải là $0$ và tất cả ban đầu phải là $29.$

Bài tập 1.3 (VMO 2014): Tìm tất cả các bộ số $2014$ số hữu tỷ không âm sao cho nếu bỏ đi bất kỳ số nào trong chúng thì các số còn lại có thể được chia thành $3$ nhóm rời nhau, mỗi nhóm có $671$ số sao cho tích các số trong mỗi nhóm là bằng nhau.

Bài này khó hơn vì: số hữu tỷ chứ không nguyên, tích chứ không phải tổng, … Ta lần lượt giải quyết điều đó như sau:

Quy đồng mẫu để đưa về số nguyên.
Xét số mũ của 1 ước nguyên tố để đưa về tổng.
Chú ý thêm trường hợp số 0 (nếu có 1 số thì phải có ít nhất 4 số).

Bài tập 1.4: Cho dãy số nguyên dương $(a_{n})$ thỏa mãn:

$i)$ Gồm các số phân biệt nhau.

$i i)$ Với mọi $n$ thì $a_{n} \geq n .$

$i i i)$ $a_{1} = 5, a_{2} = 4, a_{3} = 3$ .

a) Chứng minh rằng tồn tại $n > 2017$ sao cho $a_{n} \neq n + 1$ ?

b) Giả sử $a_{n} = n + 2$ với mọi $n > 2017$ , hỏi có tất cả bao nhiêu dãy số như thế?

Giải

a) Bài toán có thể giải quyết dễ dàng bằng phản chứng và Dirichlet. Thật vậy, nếu $a_{n} = n + 1$ với mọi $n > 2017$ thì các số hạng $a_{4} \to a_{2017}$ sẽ nhận các giá trị trong tập hợp $6 \to 2018$ . Khi đó, sẽ có hai số hạng bằng nhau, không thỏa.

b) Nếu đã có $a_{n} = n + 2$ với mọi $n > 2017$ thì các số hạng $a_{4} \to a_{2017}$ sẽ nhận các giá trị trong tập hợp $6 \to 2019.$ Nhận xét:

$a_{2017} \in {2017, 2018, 2019}$ nên có $3$ cách chọn.
$a_{2016} \in {2016, 2017, 2018, 2019}$ nhưng vì $a_{2017}$ đã lấy một số nên cũng còn $3$ cách chọn.
Tương tự, đến $a_{6}$ vẫn có $3$ cách chọn. Còn lại $a_{5}$ có $2$ cách chọn và $a_{4}$ có $1$ cách chọn.

Theo nguyên lý nhân, ta có $2 \cdot 3^{2012}$ dãy thỏa mãn.

Bài tập 1.5: Xét lục giác $A B C D E F$ có độ dài cạnh là $1$ được điền các số như hình vẽ

Một con ếch xuất phát từ $A$ và nhảy đến các đỉnh sao cho mỗi bước nhảy đều có độ dài nguyên. Hành trình của ếch là dãy các tên đỉnh mà ếch đã nhảy qua; và hai hành trình được coi là khác nhau nếu ở một lần thứ $k$ nào đó, đỉnh mà ếch nhảy đến ở hai hành trình là khác nhau.

Gọi $m$ là số hành trình ếch nhảy sao cho tổng các số mà nó nhảy qua là $2017$ . Chứng minh rằng $m$ không phải là số chính phương.

Giải

Ta thấy $A C E$ và $B D F$ là hai tam giác đều có cạnh là $\sqrt{3}$ nên mỗi lần, ếch sẽ nhảy từ tam giác đều này đến tam giác đều kia.

Chia nhóm:

$I = (A, C, E)$ tương ứng với các số $(0, 0, 1)$ .
$I I = (B, D, F)$ tương ứng với $(1, 1, 2)$ .

Ta thấy ${x + y | x \in I, y \in I I} = {1, 1, 1, 1, 2, 2, 2, 2, 3}$ chứng tỏ tổng các số trên hai bước nhảy liên tiếp của ếch sẽ nhận giá trị là $4$ số $1$ , $4$ số $2$ và $1$ số $3.$ Nếu gọi $s_{n}$ là số hành trình của ếch có tổng là $n$ thông qua chẵn bước thì

$s_{n} = 4 s_{n - 1} + 4 s_{n - 2} + s_{n - 3} .$

Một cách tương tự, gọi $t_{n}$ là số hành trình của ếch có tổng là $n$ thông qua lẻ bước thì công thức truy hồi vẫn thế (chỉ khác ở các số hạng đầu).

Vì vậy nên nếu gọi $u_{n} = s_{n} + t_{n}$ là số hành trình của ếch có tổng là $n$ thì

$u_{n} = 4 u_{n - 1} + 4 u_{n - 2} + u_{n - 3} với n \geq 3.$

Ta có $u_{0} = 1, u_{1} = 6, u_{2} = 28$ và từ công thức truy hồi thì $m = u_{2017} \equiv u_{1} \equiv 2 (\mod 4)$ nên $m$ không thể là số chính phương, ta có đpcm.

Nhận xét: Bài toán có thể giải bằng cách gọi $6$ dãy truy hồi $a_{n}, b_{n}, c_{n}, d_{n}, e_{n}, f_{n}$ chỉ số hành trình của ếch có tổng là $n$ và kết thúc tại $A, B, C, D, E, F$ . Tuy nhiên, cách tiếp cận đó khá phức tạp, đòi hỏi phải khai thác nhiều các liên hệ giữa các đường đi.

Một bài toán tương tự:

Bài tập 1.6 (Ả Rập TST 2017): Người ta đặt các số $1, 2, 3, 4$ trên vòng tròn theo thứ tự đó. Một con kiến xuất phát từ số $1$ và ở mỗi bước, nó sẽ bò qua số bên cạnh. Hỏi con kiến có bao nhiêu cách bò sao cho tổng tất cả các số mà nó bò qua (kể cả số ban đầu) bằng 21?

Tương tự bài trên, ta cũng tìm được hệ thức truy hồi là $s_{n} = s_{n - 3} + 2 s_{n - 5} + s_{n - 7}$ . Từ đó tính được $s_{21} = 167.$

Bài tập 1.7: Đếm số dãy số nguyên dương $(a_{1}, a_{2}, \dots, a_{12})$ thỏa mãn các điều kiện sau:

a) $1 \leq a_{1} \leq a_{2} \leq \dots \leq a_{12} \leq 2017$

b) $a_{i} \equiv i^{2} (mod 12)$ .

Giải

Theo giả thiết, ta có

$a_{1} \equiv a_{5} \equiv a_{7} \equiv a_{11} \equiv 1 (mod 12)$

$a_{2} \equiv a_{4} \equiv a_{8} \equiv a_{10} \equiv 4 (mod 12)$

$a_{3} \equiv a_{9} \equiv 9 (mod 12)$

$a_{6} \equiv a_{12} \equiv 0 (mod 12)$

Đặt $a_{i} = 12 b_{i} + r_{i}$ với $i = 1, 2, 3, \dots, 12$ và $r_{i}$ là số dư tương ứng đã chỉ ra ở trên.

Do tính không giảm của dãy nên ta phải có

$0 \leq b_{1} \leq b_{2} \leq b_{3} < b_{4} < b_{5} < b_{6} \leq b_{7} \leq b_{8} \leq b_{9} < b_{10} < b_{11} < b_{12} \leq 168.$

Từ đó suy ra

$0 \leq b_{1} < b_{2} + 1 < b_{3} + 2 < b_{4} + 2 < b_{5} + 2 < b_{6} + 2 \leq b_{7} + 3 \leq b_{8} + 4 \leq b_{9} + 5$

$< b_{10} + 5 < b_{11} + 5 < b_{12} + 5 \leq 173$

Do các số liệt kê ở trên đều phân biệt và thuộc $[0; 173]$ nên số cách chọn một bộ như thế là $C_{174}^{12}$ . Đó cũng chính là số dãy cần tìm.

Nhận xét: Điều kiện thứ hai có thể thay bằng một hàm số tùy ý theo $i$ chứ không nhất thiết phải là $i^{2}$ , cách giải vẫn tương tự như trên.

Bài tập 1.8: Hỏi có bao nhiêu hoán vị $a_{1}, a_{2}, \dots, a_{2017}$ của $2017$ số nguyên dương đầu tiên thỏa mãn đồng thời các điều kiện sau:

$i)$ $a_{i + 1} - a_{i} \leq 1$ với mọi $i = 1, 2, 3, \dots, 2016.$

$i i)$ Có đúng một chỉ số $i$ với $1 \leq i \leq 2017$ sao cho $a_{i} = i$ ?

Giải

Trước hết, ta sẽ chứng minh nhận xét rằng số hoán vị của $n$ số nguyên dương đầu tiên thỏa mãn điều kiện i), gọi là hoán vị đẹp, sẽ là $2^{n - 1}$ . Thật vậy,

Đầu tiên, ta đặt số $1$ vào hoán vị.
Số $2$ có thể xếp trước hoặc sau số $1$ , có $2$ cách.
Số $3$ có thể xếp vào đầu dãy hoặc ngay sau số $2$ đã xếp trước đó, có $2$ cách.
Số $4$ có thể xếp vào đầu dãy hoặc ngay sau số $3$ đã xếp trước đó, cũng có $2$ cách. Cứ như thế cho đến $n .$

Do đó, có tất cả $2^{n - 1}$ cách xếp, tương ứng vời $2^{n - 1}$ hoán vị.

Tiếp theo, giả sử ta có $a_{i} = i$ .

Khi đó $a_{i + 1} \leq a_{i} + 1 = i + 1$ , nhưng không thể có $a_{i + 1} = i + 1$ (do chỉ có 1 chỉ số thỏa mãn ii) nên $a_{i + 1} \leq i$ , mà $a_{i} = i$ nên $a_{i + 1} \leq i - 1$ . Tiếp theo, $a_{i + 2} \leq a_{i + 1} + 1 \leq i$ nên $a_{i + 2} \leq i - 1$ .

Do đó, các số từ $a_{i + 1}$ đến $a_{2017}$ nhận giá trị không vượt quá $i - 1$ .

Lập luận tương tự, các số từ $a_{1}$ đến $a_{i - 1}$ phải nhận giá trị không nhỏ hơn $i + 1.$

Do đó, hai đoạn hoán vị phía trước và phía sau $a_{i}$ phải có độ dài bằng nhau, tức là $a_{1009} = 1009$ là số ở giữa.

Rõ ràng các hoán vị phía trước và phía sau $1009$ đều phải là hoán vị đẹp và được sắp xếp độc lập với nhau.

Vậy số hoán vị cần tìm là ${(2^{1007})}^{2} = 2^{2014} .$

Nhận xét: Nếu đề đổi số $2017$ thành $2018$ thì sẽ tồn tại hai chỉ số $i$ như trên và chúng sẽ cách đều hai đầu $1$ và $2018$ . Khi đó, đoạn ở giữa cũng sẽ cố định, tức là có $i < j$ để

$a_{k} = k$ với mọi $k = i, i + 1, \dots, j$ và $i + j = 2019.$

Phần trước $i$ và phần sau $j$ sẽ đổi chỗ cho nhau với số cách xếp là ${(2^{i - 1})}^{2}$ .

Bài tập 1.9: Cho dãy các số nguyên dương $(u_{n})$ thỏa mãn điều kiện

$0 \leq u_{m + n} - u_{m} - u_{n} \leq 1$ với mọi $m, n \in Z^{+}$ .

Chứng minh rằng tồn tại $a \in R^{+}$ sao cho $- 1 \leq u_{n} - [a n] \leq 1$ với mọi $n = 1, 2, 3, \dots, 2017.$

Giải

Ta đưa điều cần chứng minh về

$\frac{u_{n}}{n} < a < \frac{u_{n} + 1}{n} .$

Đến đây, gọi

$m = min {\frac{u_{n} + 1}{n} | n = 1, 2, 3, \dots, 2017}$ và

$M = max {\frac{u_{n}}{n} | n = 1, 2, 3, \dots, 2017.}$

Cần chỉ ra $m > M$ rồi chọn số $a$ nằm giữa $(m, M)$ là xong. Gọi $p, q$ lần lượt là các chỉ số nhỏ nhất để có dấu bằng xảy ra ở các đánh giá trên. Khi đó

$u_{p} + 1 = p m$ và $u_{q} = M q .$

Ngoài ra, $u_{k} + 1 > k m, \forall k < p$ và $u_{k} < k q, \forall k < q .$

Nếu $p = q$ thì hiển nhiên đúng.
Nếu $p > q$ , ta đặt $p = q + k$ thì $k < p$ nên $u_{k} + 1 > k m$ , vì $u_{p} \geq u_{q} + u_{k}$ (theo giả thiết) nên $p m - 1 > M q + k m - 1 \Leftrightarrow m > M .$
Nếu $p < q$ thì cũng chứng minh tương tự với chú ý rằng $u_{q} \leq u_{p} + u_{k} + 1.$

Nhận xét: Nếu đề bài đổi giả thiết thành $0 \leq u_{m + n} - u_{m} - u_{n} \leq 2$ ,

ta sẽ cần đến hai số $a, b$ sao mới thỏa mãn được kết luận (vì khoảng chênh lệch của các số hạng rộng hơn một tí), cụ thể là tồn tại $a, b > 0$ để

$- 1 \leq u_{n} - [a n] - [b n] \leq 1.$

Ở bài toán trên, ta còn chứng minh được một kết quả mạnh hơn là tồn tại $a$ để $u_{n} = [a n]$ với mọi $n .$ Một bài toán tương tự trong đề trường Đông miền Trung:

Bài tập 1.10: Cho hàm số $f : R \to R$ thỏa mãn $| f (x + y) - f (x) - f (y) | \leq 1, \forall x, y \in R$ . Chứng minh rằng tồn tại hàm cộng tính $g : R \to R$ thỏa mãn $| f (x) - g (x) | \leq 1, \forall x .$

Đây có thể nói là một phiên bản trên $R$ của bài toán trên (thay vì xét trên $N$ ).

Tiếp theo, ta xét lớp các bài toán sử dụng một định lý thú vị trong dãy số, số học. Trước hết, ta xét định lý Beatty với nội dung như sau:

Cho hai số vô tỷ dương $α, β$ . Xét hai dãy số:

$[α], [2 α], [3 α], \dots$ tạo thành dãy $A .$
$[β], [2 β], [3 β], \dots$ tạo thành dãy $B .$

Khi đó $\frac{1}{α} + \frac{1}{β} = 1$ khi và chỉ khi $A, B$ là phân hoạch của $Z^{+}$ .

Chứng minh

Định lý này có thể chứng minh bằng cách sử dụng các BĐT về phần nguyên. Dưới đây là cách chứng minh cho chiều đảo:

Với mỗi số nguyên dương $k$ , gọi $m, n$ là các số nguyên dương thỏa mãn

$[m α] \leq k < [(m + 1) α] và [n β] \leq k < [(n + 1) β] .$

Đặt $A = {[i α], 1 \leq i \leq m}$ và $B = {[j β], 1 \leq j \leq n}$ thì $| A | = m, | B | = n$ và $A, B$ là phân hoạch của tập hợp ${1, 2, 3, \dots, k}$ theo định nghĩa của đề bài.

Do đó $m + n = k$ . Theo bất đẳng thức phần nguyên thì $m α - 1 < k < (m + 1) α$ nên $\frac{m}{k + 1} < \frac{1}{α} < \frac{m + 1}{k}$ .

Tương tự $\frac{n}{k + 1} < \frac{1}{β} < \frac{n + 1}{k} .$

Suy ra $\frac{m + n}{k + 1} < \frac{1}{α} + \frac{1}{β} < \frac{m + n + 2}{k} hay \frac{k}{k + 1} < \frac{1}{α} + \frac{1}{β} < \frac{k + 2}{k} .$

Cho $k \to + \infty$ , ta thu được $\frac{1}{α} + \frac{1}{β} = 1.$

Bài tập 1.11: Hai dung dịch $A, B$ có đặc điểm: số đo thể tích của $1$ kg $A$ bằng số đo khối lượng của $1$ lít $B .$ Ngoài ra, $p$ lít $A$ nặng bằng $q$ lít $B$ với $p, q$ nguyên tố khác nhau. Mỗi dung dịch được chia cho vào các bình nhỏ giống nhau, cùng chứa $1$ lít và vỏ nặng $1$ kg. Chứng minh rằng có đúng một cách ghép các bình cùng loại ( $A$ hoặc $B$ ) lại với nhau mà khối lượng của chúng thuộc khoảng $(2017; 2018) .$

Giải

Gọi $x, y$ lần lượt là khối lượng riêng của các dung dịch thì $\frac{1}{x} = 1 \cdot y, p x = q y$ nên $x = \sqrt{\frac{q}{p}}, y = \sqrt{\frac{p}{q}} .$

Khối lượng mỗi bình là $α = 1 + \sqrt{\frac{q}{p}}, β = 1 + \sqrt{\frac{p}{q}}$ . Dễ thấy $\frac{1}{α} + \frac{1}{β} = 1$ , thỏa mãn định lý Beatty.

Suy ra hai dãy $[m α], [n β]$ là phân hoạch của số nguyên dương nên ta có đpcm.

Bài tập 1.12 (APMO 2006): Với mỗi số nguyên dương $n$ , gọi $a_{n}, b_{n}$ lần lượt là số cách viết $10^{n}$ trong hệ nhị phân, ngũ phân. Chứng minh rằng $(a_{n}), (b_{n})$ là phân hoạch của $Z^{+} ∖ {1} .$

Giải

Để giải bài này, chú ý rằng: số chữ số của $M$ trong hệ $p$ phân là $[\log_{p} M] + 1$ .

Ngoài ra, $α = \log_{2} 10, β = \log_{5} 10$ thỏa mãn điều kiện của định lý Beatty.

Từ đó, ta có một nhận xét thú vị rằng: tổng số chữ số của $2^{n}$ và $5^{n}$ trong hệ thập phân là $n + 1.$

Bài tập 1.13 (VN TST 2000): Cho số nguyên dương $k$ . Dãy số $(u_{n})$ xác định bởi: $u_{1} = 1$ và $u_{n + 1}$ là số nguyên dương nhỏ nhất không thuộc tập hợp

${u_{1}, u_{2}, \dots, u_{n}, u_{1} + k, u_{2} + 2 k, \dots, u_{n} + n k} .$

Chứng minh rằng tồn tại $α$ vô tỷ dương sao cho $u_{n} = [n α]$ với mọi $n .$

Giải

Để giải bài toán này, ta xét đa thức $P (x) = x^{2} + (k - 2) x - k$ với $k$ là số nguyên dương đã cho thì $P (x)$ có hai nghiệm phân biệt trái dấu. Hơn nữa, $Δ_{P (x)} = {(k - 2)}^{2} + 4 k = k^{2} + 4$ , không thể là số chính phương với bất kì số k nguyên dương nào nên hai nghiệm này đều là số vô tỉ. Ta thấy $P (1) = 1 + (k - 2) - k = - 1 < 0, P (2) = 4 + 2 (k - 2) - k = k > 0$ nên nghiệm dương của phương trình $P (x) = 0$ thuộc khoảng $(1, 2)$ . Gọi nghiệm đó là $a .$

Đặt $b = a + k$ thì $a, b$ đều vô tỉ và $a b = a (a + k) = a^{2} + a k = 2 a + k = a + b$ nên $\frac{1}{a} + \frac{1}{b} = 1$ .

Xét $f (n) = [n a], g (n) = [n b] = f (n) + k n$ với $n$ là số nguyên dương.

Ta sẽ chứng minh rằng $x_{n} = f (n)$ bằng quy nạp. Thật vậy,

– Với $n = 1$ , khẳng định hiển nhiên đúng vì $1 < a < 2.$

– Giả sử $x_{n} = f (n)$ với mọi $n = 1, 2, 3, \dots, m$ . Ta sẽ chứng minh rằng $x_{m + 1} = f (x_{m + 1})$ .

Ta có $f (i) = x_{i}, g (i) = f (i) + i k = x_{i} + i k$ với mọi $i = 1, 2, 3, \dots, m$ nên ta có tập hợp

$H = {x_{1}, x_{2}, \dots, x_{m}, x_{1} + k, x_{2} + 2 k, \dots, x_{m} + m k}$

$= {f (1), f (2), \dots, f (m), g (1), g (2), \dots, g (m)}$

Rõ ràng $f (m + 1) \notin H$ và $g (n) > f (n)$ với mọi $n$ , $f (n)$ là hàm số đồng biến trên $N *$ nên ta thấy rằng $f (m + 1)$ chính là số tự nhiên nhỏ nhất không thuộc H. Theo định nghĩa dãy số $(x_{n})$ đã cho thì ta có $x_{m + 1} = f (m + 1)$ .

Do đó, khẳng định cũng đúng với $m + 1.$ Theo nguyên lí quy nạp, ta có đpcm. Vậy số tự nhiên cần tìm chính là $a$ là nghiệm dương của phương trình $x^{2} + (k - 2) x - k = 0$ .

Nhận xét: Đây là một kết quả có từ $1959$ . Ta có thể phân tích cách tiếp cận như sau:

Xuất phát từ việc $α = \sqrt{2}, β = \sqrt{2} + 2$ thỏa mãn điều kiện Beatty. Ta có hai dãy với công thức

$a_{n} = [n \sqrt{2}], b_{n} = a_{n} + 2 n$ là phân hoạch của $Z^{+}$ .

Từ đó, để giấu dãy $b_{n}$ đi, ta chỉ cần xét $a_{n} + 2 n$ .

Để ý $a_{1} = 1, a_{2} = 2, a_{3} = 4, b_{1} = 3, b_{2} = 6, b_{3} = 10$ nên $a_{4}$ có thể định nghĩa là số nguyên dương nhỏ nhất không thuộc ${a_{1}, a_{2}, a_{3}, a_{1} + 2, a_{2} + 4, a_{3} + 6}$ . Đó chính là cơ sở để có bài toán trên.

Bài tập 1.14 (Dãy Wythoff): Cho chuỗi $S_{1} = 1$ . Chuỗi $S_{n}$ được tạo thành từ chuỗi $S_{n - 1}$ bằng cách thay $1 \to 01$ và $0 \to 1.$ Các chuỗi $S_{1}, S_{2}, S_{3}, \dots$ được ghép liên tiếp lại với nhau thành một chuỗi vô hạn $L$ . Gọi $a_{n}$ là vị trí của số $1$ thứ $n$ trong chuỗi $L .$ Chứng minh rằng tồn tại $α$ vô tỷ dương sao cho $a_{n} = [n α], \forall n .$

Ở đây, ta có nhận xét rằng số $0$ thứ $n$ được sinh ra bởi số $1$ thứ $n$ nên nếu gọi $k_{n}$ là số các số $0$ đứng trước số $1$ thứ $n$ và $b_{n}$ là vị trí của số $0$ thứ $n,$ ta sẽ có $a_{n} = n + k_{n}$ và $b_{n} = 2 n + k_{n}$ nên $b_{n} = a_{n} + n$ .

Chú ý rằng $(a_{n}), (b_{n})$ chính là phân hoạch của $Z^{+}$ nên dễ dàng tìm được $α$ là nghiệm của $\frac{1}{α} + \frac{1}{α + 1} = 1$ hay $α$ chính là tỷ số vàng.

Bài tập 1.15: Cho $n$ là số nguyên dương, hỏi có bao nhiêu dãy số $a_{1}, a_{2}, \dots, a_{2 n}$ sao cho

$i)$ $a_{i} \in {- 1, 1}$ với $i = 1, 2, 3, \dots, 2 n .$

$i i)$ $| \sum_{i = 2 k + 1}^{2 l} a_{i} | \leq 2$ với $0 \leq k < l \leq n$ ?

Giải

Gọi $S$ là tập hợp các dãy thỏa mãn đề bài và đặt $| S | = s_{n}$ . Gọi $T$ là tập hợp tất cả các tổng các $a_{i}$ lấy từ chỉ số lẻ bất kỳ đến $2 n .$ Theo giả thiết thì $T \subset {\pm 2, \pm 1, 0}$ , tuy nhiên, tất cả các tổng trong $T$ đều có chẵn số hạng mà mỗi số hạng đều là $\pm 1$ nên tất cả phải đều chẵn. Suy ra $T \subset {\pm 2, 0}$ .

Nếu trong $T$ chứa cả $2$ lẫn $- 2$ thì giả sử $\sum_{k = 2 i + 1}^{2 n} a_{k} = 2$ và $\sum_{k = 2 j + 1}^{2 n} a_{k} = - 2$ với $i < j$ , khi đó

$4 = \sum_{k = 2 i + 1}^{2 n} a_{k} - \sum_{k = 2 j + 1}^{2 n} a_{k} = \sum_{k = 2 i + 1}^{2 j} a_{k},$ mâu thuẫn.

Ứng với $(a_{1}, a_{2}, \dots, a_{2 n}) \in S$ , ta có phân loại sau:

Tất cả các tổng trong $T$ đều là $0$ , đặt số lượng dãy có tính chất này là $a_{n}$ .
Trong $T$ có chứa số $2$ , đặt số lượng dãy có tính chất này là $b_{n}$ .
Trong $T$ có chứa số $- 2$ , đặt số lượng dãy có tính chất này là $c_{n}$ .

Từ đó, ta dễ dàng chứng minh được hệ thức truy hồi

$a_{n + 1} = 2 a_{n}$

$b_{n + 1} = a_{n} + 2 b_{n} + c_{n}$

$c_{n + 1} = a_{n} + b_{n} + 2 c_{n}$

Chú ý rằng $a_{n} = 2^{n}$ và $a_{n} + b_{n} + c_{n} = s_{n}$ . Cộng hai công thức cuối lại, ta có

$b_{n + 1} + c_{n + 1} = 2 a_{n} + 3 (b_{n} + c_{n}) \Leftrightarrow s_{n + 1} - 2^{n + 1} = 2^{n + 1} + 3 (s_{n} - 2^{n})$ hay

$s_{n + 1} = 3 s_{n} + 2^{n} \Leftrightarrow s_{n + 1} + 2^{n + 1} = 3 (s_{n} + 2^{n}) .$

Với $n = 1$ , ta có $4$ dãy là $(1, 1), (- 1, - 1), (- 1, 1), (1, - 1)$ nên $s_{1} = 4.$

Từ đẳng thức trên, ta có $s_{n} + 2^{n} = 3^{n - 1} (s_{1} + 2^{1}) = 2 \cdot 3^{n}$ nên $s_{n} = 2 \cdot 3^{n} - 2^{n}$ .

Nhận xét: Bài toán thoạt nhìn có vẻ quen thuộc nhưng thật không đơn giản. Điều kiện đề cho là giá trị tuyệt đối của tất cả các tổng con từ vị trí lẻ đến vị trí chẵn bất kỳ đều không vượt quá $2$ buộc ta phải có đánh giá thích hợp mới có thể truy hồi được.

2. Bài tập áp dụng

Bài 1 (TP.HCM 2018): Hỏi có bao nhiêu hoán vị $(a_{1}, a_{2}, \dots, a_{164})$ của $164$ số nguyên dương đầu tiên sao cho $a_{i} \neq i$ và $a_{i} \equiv i (mod 41)$ với mọi $i = 1, 2, \dots, 164 ?$

Bài 2: (Bài toán phát kẹo) Cô giáo có $10$ loại kẹo (mỗi loại có nhiều viên) và cần phát cho $30$ học sinh của lớp (một em nhận không quá $1$ viên/loại), giả sử rằng các em này có học lực đôi một khác nhau. Hỏi cô giáo có bao nhiêu cách phát kẹo, biết rằng nếu học sinh $A$ giỏi hơn $B$ thì $B$ có kẹo gì là $A$ có kẹo đó (tính cả trường hợp không em nào nhận được kẹo)?

Bài 3: (Bài toán con nhện) Một con nhện có $8$ cái chân, $8$ cặp vớ – giày khác nhau (vớ chỉ dùng chung với chiếc giày tương ứng). Con nhện có bao nhiêu thứ tự mang vớ và giày để sao cho trên cùng một chân, giày phải được mang vào sau vớ?

Phương pháp ánh xạ trong các bài toán tổ hợp

Bài viết dựa vào bài giảng của NCS. Vương Trung Dũng (trường PTNK-ĐHQG) trong lớp chuyên đề 10 toán tại Star Education.

Ánh xạ là một khái niệm khó và quan trọng trong toán học, có vai trò trong hầu hết các lĩnh vực toán học. Trong bài giảng này ta xét ứng dụng của ánh xạ trong các bài toán tổ hợp.

Ánh xạ và một số tính chất

Định nghĩa. Cho hai tập hợp $X$ và $Y$ khác rỗng. Một ánh xạ $f$ từ tập $X$ đến tập $Y$ là một quy tắc đặt tương ứng mỗi phần tử $x$ của $X$ với một và chỉ một phần tử $y$ của $Y$ , kí hiệu là $y = f (x)$ .

Kí hiệu $f : X ⟶ Y$ .

$f (x) = y$ .

Các khái niệm: Cho ánh xạ $f : X ⟶ Y$ .

$y = f (x)$ được gọi là ảnh của $x$ .
$f (X) = {f (x) | x \in X}$ tập ảnh của $f$ .
$y \in Y$ thì $f^{-} 1 (y) = {x \in X | f (x) = y}$ được gọi là tạo ảnh của $y$ .

Đơn ánh, toàn ánh, song ánh

Ánh xạ $f : X ⟶ Y$ được gọi là đơn ánh nếu với $a, b \in X$ mà $a \neq b$ thì $f (a) \neq f (b)$ . Nói một cách khác ánh xạ $f$ là một đơn ánh nếu và chỉ nếu với $a, b \in X$ mà $f (a) = f (b)$ thì suy ra $a = b .$
Ánh xạ $f : X ⟶ Y$ được gọi là toàn ánh nếu với mỗi phần tử $y \in Y$ đều tồn tại một phần tử $x \in X$ sao cho $f (x) = y$ . Như vậy $f$ là toàn ánh nếu và chỉ nếu $f (X) = Y$ .
Ánh xạ $f : X ⟶ Y$ được gọi là song ánh giữa $X$ và $Y$ nếu và chỉ nếu nó vừa là đơn ánh và vừa là toàn ánh. Như vậy $f$ là song ánh nếu với mỗi $y \in Y$ tồn tại duy nhất một phần tử $x \in X$ sao cho $y = f (x) .$

Ánh xạ và tập hợp

Cho $A = 1, 2, \dots, n$ . $X$ là tập khác rỗng. Nếu có một song ánh từ tập $X$ đến $A$ thì ta nói $X$ có $n$ phần tử và kí hiệu $| X | = n$ .

Nếu không tồn tại song ánh thì ta nói $X$ có vô hạn phần tử.

Nếu tồn tại một song ánh từ $X$ vào tập các số tự nhiên, ta nói $X$ có lực lượng đếm được, ngược lại thì ta nó $X$ có lực lượng không đếm được.
Các tập số tự nhiên, số nguyên và hữu tỷ là các tập có lực lượng đếm được.

Định lý Cho $A$ và $B$ là hai tập hợp hữu hạn.

Nếu có một đơn ánh $f : X ⟶ Y$ thì $| X | \leq | Y | .$
Nếu có một toàn ánh $f : X ⟶ Y$ thì $| X | \geq | Y | .$
Nếu có một song ánh $f : X ⟶ Y$ thì $| X | = | Y | .$

Ánh xạ và các bài toán đếm, đẳng thức tổ hợp.

Ví dụ 1. Cho tập $X_{n} = 1, 2, \dots, n$ , gọi $P (X_{n})$ là tập các tập con của $X_{n}$ , và $S_{n}$ là tập các dãy nhị phân có độ dài $n$ . Tìm một song ánh từ $P (X_{n})$ vào $S_{n}$ , suy ra số tập con của $X_{n}$ .

Gợi ý

Định nghĩa một ánh xạ $f : P (X_{n}) ⟶ S_{n}$ như sau:
Với mỗi $S \in P (X_{n})$ (tức là $S \subset X_{n}$ ) ta đặt $f (S) = y_{1} y_{2} \dots y_{n}$
trong đó
$y_{i} = {\begin{cases} 1, y_{i} \in S \\ 0, y_{i} \notin S . \end{cases}$
Ví dụ , nếu $X = {1; 2; 3; 4; 5}, S_{1} = {4}, S_{2} = {2; 3; 5}$ thì $f (S_{1}) = 00010, f (S_{2}) = 01101, f (\emptyset) = 00000, f (X) = 11111$ .
Dễ dàng kiểm tra đây là một song ánh từ $P (X)$ vào $Y$ .
Do đó theo nguyên lý song ánh ta có $| P (X) | = | Y | = 2^{n}$ .

Ví dụ 2. Hãy tính trung bình cộng của tất cả các số N gồm 2014 chữ số thỏa mãn N chia hết cho 9 và các chữ số của N được lập từ $X = 1, 2, \dots, 8$

Gợi ý

Gọi M là tập các số thỏa yêu cầu đề bài.

Ta xây dựng một ánh xạ đi từ M đến M như sau: Với mỗi $N = \overset{―}{a_{1} a_{2} \dots a_{2014}} \in M$ dặt $f (N) = \overset{―}{b_{1}, b_{2}, \dots, b_{2014}}$ với $b_{i} = 9 - a_{i}$ với mọi $i = 1, 2, \dots, 2014$ . Vì $N + f (N) = 99 \dots 9$ (2014 số 9) chia hết cho 9 và N chia hết cho 9 nên suy ra $f (N)$ cũng chia hết cho 9. Do đó $f$ là một ánh xạ đi từ M vào M. Hơn nữa dễ thấy $f$ là một song ánh. Từ đó suy ra $2 \sum_{N \in M} N = \sum_{N \in M} (N + f (N)) = | M | .99 \dots 9 .$ Vậy trung bình cộng của các số trong M là $99 \dots 9 : 2.$

Ví dụ 3. Cho tập S gồm tất cả các số nguyên dương trong đoạn $[1, 2, \dots, 2002]$ . Gọi T là tập hợp tất cả các tập con khác rỗng của S. Với mỗi X thuộc T ký hiệu m(X) là trung bình cộng các phần tử thuộc X. Tính $m = \frac{\sum_{X \in T} m (X)}{| T |} .$

Gợi ý

Xây dựng song ánh $f : T ⟶ T$ như sau: với mọi $X \in T$ đặt tương ứng $f (X) = {2003 - x : x \in X}$ .\
Khi đó $m (X) + m (f (X)) = 2003$ . Do đó $2 \sum m (X) = \sum (m (X) + m (f (X))) = | T | .2003 \Rightarrow m = \frac{\sum m (X)}{| T |} = \frac{2003}{2}$

Ví dụ 4. Cho $X = 1, 2, \dots, n$ . Có bao nhiêu tập con $k$ phần tử của X sao cho trong mỗi tập con không chứa 2 số nguyên liên tiếp.

Gợi ý

Gọi A là tập tất cả các tập con $k$ phần tử của X mà trong mỗi tập không chứa 2 số nguyên liên tiếp và B là tập tất cả các tập con của tập $Y = {1, 2, \dots, n - (k - 1)}$ . Ta xây dựng song ánh từ A đến B như sau: Lấy $S = {s_{1}, s_{2}, \dots, s_{k}} \in A$ (không mất tổng quát có thể giả sử $s_{1} < s_{2} < \dots < s_{k}$ ) đặt tương ứng với $f (S) = {s_{1}, s_{2} - 1, s_{3} - 2, \dots, s_{k} - (k - 1)}$ . Dễ chứng minh đây là một song ánh. Từ đó có $C_{n - k + 1}^{k}$ tập thoả yêu cầu đề bài.

Bài tập rèn luyện

Bài 1. Cho $X = 1, 2, . ., n$ . Một tập con $S = s_{1}, s_{2}, \dots, s_{k}$ của X ( $s_{1} < s_{2} < \dots < s_{k}$ ) được gọi là \textit{m- tách được} $(m \in N)$ nếu $s_{i} - s_{i - 1} \geq m; i = 1, 2, \dots, k$ . Có bao nhiêu tập con m- tách được gồm $k$ phần tử của X, trong đó $0 \leq k \leq n - (m - 1) (k - 1)$ .

Bài 2. Cho $X = 1, 2, \dots, n$ , với mỗi tập con khác rỗng $A_{i} = a_{1}, a_{2}, \dots, a_{i}$ (không mất tổng quát giả sử $a_{1} > a_{2} > \dots > a_{i}$ ) ta định nghĩa \textit{tổng hỗn tạp} của $A_{i}$ là số $m (A_{i}) = a_{1} - a_{2} + a_{3} - \dots \pm a_{i}$ . Tính $\sum_{A_{i} \subset X} m (A_{i})$ .

Bài 3. Cho số nguyên dương $n$ và $d$ là một ước dương của $n$ . Gọi S là tập tất cả những bộ $(x_{1}, x_{2}, \dots, x_{n})$ nguyên dương thỏa $0 \leq x_{1} \leq x_{2} \leq \dots \leq x_{n} \leq n$ và $d | x_{1} + x_{2} + \dots + x_{n}$ . Chứng minh rằng có đúng một nửa các phần tử của S có tính chất $x_{n} = n$ .

Bài 4. Gọi $a_{n}$ là số các xâu nhị phân độ dài $n$ không chứa ba bit 0, 1, 0 liên tiếp. Gọi $b_{n}$ là số các xâu nhị phân độ dài $n$ chứa bốn bit 0, 0, 1, 1 hoặc 1, 1, 0, 0 liên tiếp. Chứng minh rằng $b_{n + 1} = 2 a_{n}$ với mọi số nguyên dương $n$ .

Bài 5. Cho các số tự nhiên $k, n, m$ thỏa điều kiện $1 < k \leq n, m > 1$ . Hỏi có bao nhiêu chỉnh hợp chập $k : (a_{1}, a_{2}, \dots, a_{k})$ của $n$ số tự nhiên đầu tiên mà mỗi chỉnh hợp đều thỏa mãn ít nhất một trong hai điều kiện sau:

i) Tồn tại $i, j \in 1, 2, \dots, k$ sao cho $i < j$ và $a_{i} > a_{j}$ .

ii) Tồn tại $i \in 1, 2, \dots, k$ sao cho $a_{i} - i$ không chia hết cho $m$ .

Bài 6. Cho các số nguyên dương $n, k, p$ với $k \geq 2$ và $k (p + 1) \leq n .$ Cho $n$ điểm phân biệt cùng nằm trên một đường tròn. Tô tất cả $n$ điểm đó bởi hai màu xanh, đỏ (mỗi điểm được tô bởi một màu) sao cho có đúng $k$ điểm được tô bởi màu xanh và trên mỗi cung tròn mà hai đầu mút là hai điểm màu xanh liên tiếp (tính theo chiều quay kim đồng hồ) đều có ít nhất $p$ điểm được tô màu đỏ. Hỏi có tất cả bao nhiêu cách tô khác nhau?

Bài 7. Gọi $a_{n}$ là số các xâu nhị phân độ dài $n$ không chứa ba bit 0, 1, 0 liên tiếp. Gọi $b_{n}$ là số các xâu nhị phân độ dài $n$ chứa bốn bit 0, 0, 1, 1 hoặc 1, 1, 0, 0 liên tiếp. Chứng minh rằng $b_{n + 1} = 2 a_{n}$ với mọi số nguyên dương $n$ .

Bài 8. Trong một hội nghị có $n$ nhà toán học. Biết rằng nếu hai nhà toán học nào đó quen nhau thì họ không quen chung thêm một người nào nữa, còn nếu hai nhà toán học này không quen nhau thì họ quen chung với đúng hai nhà toán học khác nữa. Chứng minh rằng $8 n - 7$ là số chính phương.

Bài 9. Trong một trại hè toán học có 40 học sinh. Biết rằng cứ 19 học sinh bất kỳ thì đều viết thư hỏi bài một học sinh khác (Nếu học sinh A viết thư hỏi bài học sinh B thì không nhất thiết học sinh B phải viết thư hỏi bài học sinh A và dĩ nhiên A cũng không viết thư hỏi chính mình). Chứng minh rằng trong trại hè này tồn tại một tập $T_{0}$ gồm 20 học sinh sao cho với mỗi $P \in T_{0}$ thì 19 người còn lại không đồng thời viết thư hỏi bài P.

Bài 10. Gọi M là số số nguyên dương trong hệ thập phân có $2 n$ chữ số trong đó có $n$ chữ số 1 và $n$ chữ số 2. Gọi N là số số nguyên dương có $n$ chữ số trong hệ thập phân trong đó chỉ có các chữ số 1, 2, 3, 4 và số chữ số 1 bằng số chữ số 2. Chứng minh $| M | = | N | .$

(Hết phần 1)

Nguyên lý Đirichlet và áp dụng

Leave a reply

Nguyên lý Dirichlet hay còn được gọi là nguyên lý chuồng thỏ được phát biểu dưới dạng sau:”Có $n + 1$ con thỏ được nhốt vào $n$ cái chuồng thì có một chuồng chứa ít nhất hai con thỏ“. Với nội dung khá đơn giản tuy nhiên nguyên lý này giúp giải được khá nhiều bài toán trong nhiều phân môn: đại số, số học, hình học, tổ hợp. Trong bài viết nhỏ này trình bày một vài ví dụ áp dụng nguyên lý Dirichlet giúp các bạn định hướng tốt hơn trong việc giải các bài toán.

1. Các ví dụ

a) Nguyên lý Dirichlet trong các bài toán đại số và số học

Nguyên lý Dirichlet có thể được phát biểu như sau: Có $n + 1$ số tự nhiên lớn hơn $k$ và nhỏ hơn $k + n + 1$ , thì sẽ có 2 số bằng nhau.

Trong phát biểu trên ta xem $n + 1$ số tự nhiên là $n + 1$ con thỏ, các số tự nhiên lớn hơn $k$ , nhỏ hơn $k + n + 1$ gồm $k + 1, k + 2, \dots, k + n$ là $n$ cái chuồng. Khi đó chắc chắn có 2 con thỏ cùng một chuồng, hay sẽ có hai số bằng nhau.

Việc phát hiện đối tượng nào là thỏ, đối tượng nào là chuồng là một việc có ý nghĩa quan trọng, hoặc đôi khi ta phải xây dựng chuồng, thỏ, từ đó giải quyết vấn đề. Ta xét các ví dụ sau:

Ví dụ 1: Cho 676 số tự nhiên phân biệt không lớn hơn 2016. Chứng minh rằng chọn được hai số $a, b$ thỏa $| a - b | \in {3, 6}$ .

Giải

Gọi $676$ số đó là $a_{1}, a_{2}, \dots, a_{676}$ .

Xét $676 \times 3 = 2028$ gồm $676$ số $a_{1}, a_{2}, \dots, a_{676}$ ; (nhóm 1), $676$ số $a_{1} + 3, a_{2} + 3, \dots, a_{676} + 3$ (nhóm 2), $676$ số $a_{1} + 6, a_{2} + 6, \dots, a_{676} + 6$ (nhóm 3).

$2028$ số này là các số tự nhiên không vượt quá $2022$ nên theo nguyên lý Dirichlet tồn tại $2$ số bằng nhau. Mà hai số cùng một nhóm không thể bằng nhau nên xảy ra $3$ trường hợp: $a_{i} = a_{j} + 3$ , $a_{i} = a_{j} + 6$ hoặc $a_{i} + 3 = a_{j} + 6$ , trong cả ba trường hợp ta đều có $| a_{i} - a_{j} | \in {3, 6}$ .

Ví dụ 2: Cho tập $A = 1, 2, 3, \dots, 9$ . Lấy $S$ gồm các phần tử thuộc $A$ sao cho tổng hai số bất kì thuộc $S$ là các số phân biệt. Hỏi tập $S$ có số phần tử nhiều nhất là bao nhiêu? Tại sao?

Giải

Nếu tập $S$ có $7$ phần tử trở lên thì sẽ có không ít hơn $21$ tổng. Mà các tổng hai số chỉ nhận các giá trị từ $3$ đến $17$ nên theo nguyên lý dirichlet thì sẽ có hai tổng bằng nhau.

Do đó số phần tử của $S$ không lớn hơn $6$ .

Xét $S$ có $6$ phần tử, khi đó có đúng $15$ tổng nhận các giá trị $3, 14, \dots, 17$ nên mỗi tổng hai số nhận đúng một giá trị. Để có tổng bằng $3$ , $17$ thì tồn tại $4$ số $1, 2$ và $8, 9$ . Khi đó $1 + 9 = 2 + 8$ (vô lý). Vậy tập không thể có $6$ phần tử.

Nếu tập có $5$ phần tử, ta thấy $S = {1, 2, 5, 7, 9}$ thỏa đề bài.

Vậy số phần tử lớn nhất của một tập con thỏa đề bài là $5$ .

Ví dụ 3: Cho $1010$ số nguyên dương $a_{1} < a_{2} < \dots < a_{1010} \leq 2017$ . Chứng minh rằng có $2$ số $a_{i}, a_{k}$ sao cho $a_{i} + a_{1} = a_{k}$ .

Giải

Xét $2019$ số gồm $1010$ số đã cho (nhóm 1) và $1009$ số $a_{2} - a_{1}, a_{3} - a_{1}, \dots, a_{1010} - a_{1}$ (nhóm 2) nhận giá trị nguyên từ $1$ đến $2017$ , theo nguyên lý dirichlet thì có hai số bằng nhau, hơn nữa các số nhóm 1 khác nhau, các số nhóm 2 khác nhau nên một số thuộc nhóm 1 bằng một số thuộc nhóm 2, do đó tồn tại $i, k$ sao cho $a_{k} - a_{1} = a_{i}$ hay $a_{i} + a_{1} = a_{k}$ .

Nguyên lý áp dụng trong các bài toán số học được phát biểu dưới dạng sau: “Cho $n + 1$ số nguyên, khi đó có 2 số có hiệu chia hết cho $n$ “.

Ví dụ 4: Chứng minh rằng trong $11$ số chính phương thì có $2$ số có hiệu chia hết cho $20$ .

Giải

Theo nguyên lý đirichlet thì trong $11$ số có hai số có hiệu chia hết cho $10$ , gọi $2$ số đó là $a, b$ . Ta có $a = x^{2}, b = y^{2}$ và $a - b = (x - y) (x + y)$ chia hết cho $10$ nên $x, y$ cùng tính chẵn lẻ, do đó $(x - y) (x + y)$ chia hết cho $4$ . Vậy $a - b$ chia hết cho $4$ và chia hết cho $10$ nên chia hết cho $20$ .

Ví dụ 5: Cho $5$ số nguyên dương và mỗi số chỉ có ước nguyên tố là $2$ và $3$ . Chứng minh rằng có $2$ số mà tích là một số chính phương.

Giải

$5$ số có dạng $2^{a} \cdot 3^{b}$ với $a, b$ là các số tự nhiên.

Xét tính chẵn lẻ của các cặp số $(a; b)$ ta chỉ có $4$ trường hợp là (chẵn; chẵn), (chẵn;lẻ), (lẻ; chẵn) và (lẻ; lẻ).

Khi đó với $5$ cặp số thì theo nguyên lý dirichlet có $2$ cặp $(a_{1}; b_{1})$ và $(a_{2}; b_{2})$ sao cho $a_{1}, a_{2}$ cùng tính chẵn lẻ và $b_{1}, b_{2}$ cùng tính chẵn lẻ.

Khi đó $a_{1} + a_{2}, b_{1} + b_{2}$ là chẵn, suy ra $2^{a_{1}} 3^{b_{1}} \cdot 2^{a_{2}} 3^{b_{2}} = 2^{a_{1} + a_{2}} \cdot 3^{b_{1} + b_{2}}$ là số chính phương.

Ví dụ 6: Xét $20$ số tự nhiên $1, 2, . . ., 20$ . Hãy tìm số nguyên dương $k$ nhỏ nhất sao cho với mỗi cách lấy $k$ số phân biệt từ $20$ số trên đều lấy được hai số $a, b$ sao cho $a + b$ là một số nguyên tố.

Giải

Xét $10$ số chẵn thì tổng hai số bất kì đều là hợp số, do đó đó $k \geq 11$ .

Ta chứng minh $k = 11$ .

Xét $10$ cặp số $(1; 2), (3; 20), (4; 19), \dots, (11; 12)$ , mỗi cặp số có tổng là số nguyên tố, khi đó với $11$ số thì theo nguyên lý dirichlet có $2$ số cùng một cặp, khi đó tổng của chúng là một số nguyên tố.

b) Nguyên lý Dirichlet trong các bài toán hình học

Ví dụ 7: Có $33$ điểm trong hình vuông $4 \times 4$ . Chứng minh rằng có $3$ điểm tạo thành tam giác có diện tích không lớn hơn $\frac{1}{2}$ .

Giải

Chia hình vuông thành $16$ hình vuông như hình vẽ, khi đó theo nguyên lý dirichlet thì có $3$ điểm cùng thuộc một hình vuông $1 \times 1$ .

Ta cần chứng minh tam giác có $3$ đỉnh nằm trong hoặc trên cạnh hình vuông $1$ thì diện tích không quá $\frac{1}{2}$ .

Xét tam giác $E F G$ , đường thẳng qua $E$ song song với cạnh hình vuông cắt $F G$ tại $I$ .

Khi đó $S_{E F G} = S_{E F I} + S_{E G I} = \frac{1}{2} F M \cdot E I + \frac{1}{2} G K \cdot E I = \frac{E I}{2} (F M + G K) \leq \frac{1}{2}$ .

Ví dụ 8: Cho một tập $S$ gồm $25$ điểm sao cho với ba điểm bất kì thuộc $S$ thì có $2$ điểm khoảng cách nhỏ hơn $1$ . Chứng minh rằng tồn tại một hình tròn bán kính $1$ chứa ít nhất $13$ điểm thuộc $S$ .

Giải

Xét $2$ điểm $A$ và $B$ sao cho $A B$ có độ dài lớn nhất. Khi đó xét $2$ hình tròn $(A; 1), (B; 1)$ nếu chứa hết $25$ điểm thì sẽ có $13$ điểm cùng thuộc một hình tròn, ta có điều cần chứng minh.

Nếu có $1$ điểm $C$ không thuộc $2$ hình tròn trên thì trong $3$ điểm $A, B, C$ không có $2$ điểm nào khoảng cách nhỏ hơn $1$ (vô lý).

Ví dụ 9: Cho đa giác đều có $14$ đỉnh. Chứng minh rằng từ $6$ đỉnh bất kì có thể chọn được $4$ đỉnh tạo thành một hình thang cân.

Giải

Do tính chất đối xứng của tứ giác đều nên với hai đỉnh bất kì thì độ dài nối hai đỉnh đó có thể nhận $1$ trong $7$ giá trị.

Với $6$ đỉnh ta có $15$ đoạn thẳng nhận bảy giá trị độ dài khác nhau, theo nguyên lý dirichlet thì có $3$ đoạn có đoạn thẳng bằng nhau.

TH1: Nếu $3$ đoạn bằng nhau đó cùng chung một đỉnh, ví dụ $A B = A C = A D$ , suy ra $B, C, D$ thuộc đường tròn tâm A (vô lý).

TH2: Có $2$ đoạn bằng nhau không chung một đỉnh, giả sử $A B = C D$ . Ta có $A B C D$ nội tiếp và $A B = C D$ nên $4$ đỉnh $A, B, C, D$ tạo thành hình thang cân. (điều cần chứng minh).

2. Bài tập

Bài 1: Cho $100$ số tự nhiên. Chứng minh rằng tồn tại một số hoặc mộ số các số có tổng chia hết cho $100$ .

Bài 2: Chứng minh rằng tồn tại số tự nhiên chỉ toàn các chữ số $1$ và chia hết cho $2017$ .

Bài 3: Cho bảng ô vuông $5 \times 5$ , người ta điền vào các ô vuông các số $- 1, 0, 1$ . Xét tổng các số ở các dòng, cột và đường chéo, chứng minh rằng trong các tổng này có hai tổng bằng nhau.

Bài 4: Cho $5$ số nguyên dương đôi một phân biệt sao cho trong các số ấy thì chỉ có ước nguyên tố là $2$ và $3$ . Chứng minh rằng có hai số mà tích của chúng là một số chính phương.

Bài 5: Có $20$ số nguyên dương phân biệt không lớn hơn $70$ . Xét tất cả các hiệu của $2$ số, chứng minh rằng trong các hiệu đó có $4$ số bằng nhau.

Bài 6: Xét $20$ số tự nhiên $1, 2, \dots, 20$ . Hãy tìm số nguyên dương $k$ nhỏ nhất sao cho với mỗi cách lấy $k$ số phân biệt từ $20$ số trên đều lấy được hai số $a, b$ sao cho $a + b$ là một số nguyên tố.

Bài 7:

a) Tô các cạnh của một lục giác bằng $2$ màu xanh đỏ. Chứng minh rằng tồn tại một tam giác được tô cùng một màu.

b) Tô các cạnh của một đa giác $17$ cạnh bằng $3$ màu. Chứng minh rằng tồn tại một tam giác được tô cùng một màu.

Bài 8: Trên đường tròn cho $16$ điểm tô bởi một trong ba mày: Xanh, Đỏ, Vàng. Các dây cung nối $2$ điểm trong $16$ điểm trên được tô bởi hai màu trắng, đen. Chứng minh ta luôn có $3$ điểm trong $16$ điểm trên tô cùng màu và $3$ cạnh của nó cũng được tô cùng màu.

Bài 9: Chứng minh rằng trong $52$ số tự nhiên bất kì luôn tìm được $2$ số mà tổng hoặc hiệu của chúng chia hết cho $100$ .

Bài 10: Từ các số $1, 2, \dots, 2 n$ lấy ra $n + 1$ số. Chứng minh rằng:

a) Có $2$ số nguyên tố cùng nhau.

b) Có $2$ số mà số này chia hết cho số kia.

Bài 11: Có $81$ số gồm $9$ chữ số $1, 9$ chữ số $2, \dots, 9$ chữ số $9$ . Xếp $81$ số này thành một dãy, có tồn tại hay không một cách xếp sao cho giữa hai chữ số $k$ có đúng $k$ số với $k = 1, 2, \dots, 9$ .

Bài 12: Có $51$ điểm trong một hình vuông có cạnh bằng $1$ . Chứng minh rằng tồn tại $3$ điểm có thể chứa trong một hình tròn bán kính $\frac{1}{7}$ .

Bài 13: Cho đa giá có $2018$ cạnh, chứng minh rằng có một đường chéo không song song với bất kì cạnh nào.

Bài 14: Mỗi đỉnh của một đa giác đều $7$ cạnh được tô màu đỏ hoặc xanh. Chứng minh rằng có $3$ đỉnh tạo thành một tam giác cân và được tô cùng một màu.

Bài 15: Có $9$ đường thẳng trong đó mỗi đường thẳng chia hình vuông ra làm $2$ phần tỉ lệ diện tích là $2 : 3$ . Chứng minh rằng có $3$ đường thẳng đồng quy.

Bài 16: (PTNK 2011) Cho hình chữ nhật $3 \times 4$ .

a) Có $7$ điểm trong hình chữ nhật. Chứng minh có $2$ điểm khoảng cách không lớn hơn $\sqrt{5}$ .

b) Có $6$ điểm trong hình chữ nhật. Chứng minh có $2$ điểm khoảng cách không lớn hơn $\sqrt{5}$ .

Giải bài toán bằng đại lượng cực biên-Phần 1

Leave a reply

Tương đương với nguyên lý qui nạp là nguyên lý cực hạn, trong dó cụ thể bằng một số tính chất sau:

Tính chất (tiên đề)

Một tập con hữu hạn khác rỗng của tập số thực luôn tồn tại phần tử nhỏ nhất và phần tử lớn nhất.
Mọi tập con khác rỗng của $R$ bị chặn trên đều tồn tại chặn trên nhỏ nhất.
Mọi tập con khác rỗng của $R$ bị chặn dưới đều tồn tại chặn dưới lớn nhất.

Trong nhiều bài toán, việc chọn đối tượng cực hạn (lớn nhất hoặc nhỏ nhất) giúp ta thuận lợi trong suy luận. \
Cũng như quy nạp, cực hạn cũng có nhiều ứng dụng rộng rãi trong các việc giải quyết các bài toán tổ hợp.
Ví dụ 1. Tìm $n$ lớn nhất sao cho tồn tại $n$ điểm mà 3 điểm bất kì đều tạo thành tam giác vuông.

Lời giải

Ta thấy

n = 3, n = 4

đều tồn tại. Ta chứng minh

n \geq 5

thì không tồn tại. \
Giả sử ngược lại, tồn tại 5 điểm, sao cho 3 điểm bất kì đều tạo thành tam giác vuông. Khi đó ta chọn hai điểm sao cho có độ dài lớn nhất. Khi đó các điểm còn lại đều nằm trên đường tròn đường kính là đoạn thẳng này. Khi đó 3 điểm thuộc 2 nửa đường tròn, khi đó có ít nhất 2 điểm cùng thuộc một nửa, từ đó tồn tại một tam giác khác vuông có đỉnh là 2 điểm này cùng một điểm thuộc đường kính. Do đó không thỏa đề bài.

Bài toán này có nhiều các để tiếp cận, việc tìm ra $n = 5$ không có gì khó, khi chứng minh $n = 5$ không thỏa cũng có nhiều cách suy luận, tuy vậy việc chọn đoạn thẳng có độ dài lớn nhất giúp ta dễ dàng suy ra mâu thuẫn.
Ví dụ 2. Trên một mặt bàn đặt một số các đồng xu với kích cỡ không giống nhau đôi một (các đồng xu không được đè lên nhau và phải nằm sấp hoặc ngửa trên bàn). Chứng minh rằng dù ta đặt như thế nào đi nữa, cũng luôn tồn tại một đồng xu chỉ tiếp xúc được với nhiều nhất 5 đồng xu khác.

Lời giải

Chọn đồng xu có bán kính nhỏ nhất, thì đồng xu này chỉ tiếp xúc không quá 5 đồng xu khác. Giả sử nó có thể tiếp xúc với 6 đồng xu khác. Khi đó

A

là tâm đường tròn, tâm các đường tròn còn lại là

A_{1}, \dots, A_{6}

. Khi đó tồn tại

A_{i} A_{i + 1} \leq 60^{\circ}

, suy ra

A_{i} A_{i + 1} < A A_{i}

vô lý, vì bán kính của

(A)

là nhỏ nhất.

Ví dụ 3. Cho $n$ điểm trong mặt phẳng biết rằng cứ 3 điểm bất kì tạo thành một tam giác có diện tích không lớn hơn 1. Chứng minh rằng $n$ điểm thuộc một hình tam giác có diện tích không lớn hơn 4.

Lời giải

Gọi

A, B, C

là 3 điểm tạo thành tam giác sao cho

A B C

có diện tích lớn nhất. Từ

A, B, C

vẽ các đường song song với các cạnh đối diện, các đường thẳng cắt nhau tại

A^{'}, B^{'}, C^{'}

ta chứng minh các điểm thuộc cạnh hoặc miền trong tam giác

A^{'} B^{'} C^{'}

Thật vậy, nếu có điểm nào nằm ngoài tam giác $A^{'} B^{'} C^{'}$ thì điểm đó kết hợp với hai trong 3 điểm $A, B, C$ sẽ có diện tích lớn hơn diện tích tam giác $A B C$ , vô lý.
Do $S_{A^{'} B^{'} C^{'}} = 4 S_{A B C} \leq 4$ .

Ví dụ 4. (Sylvester) Trong mặt phẳng cho $n$ điểm phân biệt, sao cho mỗi đường thẳng đi qua hai điểm thì đi qua ít nhất một điểm khác. Chứng minh rằng $n$ điểm này cùng thuộc một đường thẳng.

Lời giải

Giả sử không phải tất cả các điểm cùng thuộc một đường thẳng. Khi đó ta xét khoảng cách từ một điểm đến đường thẳng qua ít nhất 3 điểm, trong các khoảng cách này có khoảng cách nhỏ nhất. Giả sử

P

là điểm có khoảng cách từ

P

đến

d

là nhỏ nhất, với

d

là đường thẳng qua các điểm

A, B, C

theo thứ tự. \
Gọi

H

là hình chiếu của

P

trên

d

D, E

là hình chiếu của

A, B

trên

B

trên

P A, P C

. Nếu

H

thuộc tia

B A

thì

B E < P H

, nếu

H

thuộc đoạn

B C

thì

B D < P H

. Mâu thuẫn với

P H

là nhỏ nhất. \
Vậy tất cả các điểm cùng thuộc một đường thẳng.

Trên đây là một định lý kinh điển với lời giải cực hạn cũng đi vào các sách giáo khoa về tổ hợp, việc chọn khoảng cách nhỏ nhất đó là một ý tưởng khá độc đáo, giúp giải quyết bài toán rất nhanh.

Việc chọn đối tượng cực hạn phụ thuộc vào bài toán và hướng đi kế tiếp, có được điều này cần rèn luyện thêm trong việc giải toán.

Ví dụ 5. Cho 3 trường, mỗi trường có $n$ học sinh, biết rằng cứ mỗi học sinh thì quen ít nhất $n + 1$ học sinh của hai trường khác. Chứng minh rằng có thể chọn được từ mỗi trường một bạn sao cho 3 bạn này đôi một quen nhau.

Lời giải

Giả sử 3 trường là

X, Y, Z

. Tồn tại một người có số người quen ở cùng một trường khác là nhiều nhất, giả sử

A

thuộc

X

có số người quen ở trường

Y

nhiều nhất là

k

. Khi đó số người quen của

A

ở

Z

ít nhất là

n + 1 - k

. Nếu nhóm người quen

A

ở

Z

quen với số người quen

A

ở

X

có hai người quen nhau thì ta có điều chứng minh.\
Ngược lại xét người quen

A

ở

Z

, đặt là

B

quen số người ở

Y

tối đa là

n - k

, khi đó

B

quen ở

X

ít nhất là

n + 1 - (n - k) = k + 1

, mâu thuẫn với cách chọn

A

. (Mâu thuẫn).

Ví dụ 6. Một bữa tiệc có 10 học sinh tham gia, biết rằng mỗi học sinh quen với ít nhất là 5 người. Chứng minh rằng có thể sắp xếp 10 học sinh ngồi vào một bàn tròn sao cho hai người kế nhau thì quen nhau.

Lời giải

Giả sử chuỗi người quen dài nhất có độ dài là

k

A_{1} A_{2} \dots A_{k}

, ta thấy các người còn lại không ai quen

A_{1}, A_{k}

nên suy ra

k \geq 6

. \
Nếu

k = 6

, suy ra

A_{1}

và

A_{6}

quen nhau, khi đó trong các người còn lại

A_{7}

quen một trong cái người giả sử là

A_{i}

, khi đó ta có chuỗi

A_{7} A_{i} A_{i - 1} A_{1} A_{6} A_{i + 1}

có độ dài hơn 6, vô lý.\
Nếu

k = 7

, khi đó

A_{1}

quen từ

A_{2}

đến

A_{6}

và

A_{7}

quen

A_{2}

tới

A_{6}

, khi đó có một vòng

A_{2} A_{7} A_{6} A_{5} A_{4} A_{3} A_{1} A_{2}

. Khi đó sẽ có một người trong nhóm còn lại thì ta sẽ có chuỗi dài hơn, mâu thuẫn.\
Nếu

k = 8, 9

xét tương tự, ta sẽ có

k = 10

. Giả sử có chuỗi

A_{1} \dots A_{10}

. Khi đó tồn tại

k > i

sao cho

A_{1}

quen

A_{k}

và

A_{10}

quen

A_{i}

, khi đó có cách xếp thỏa đề bài là

A_{1} A_{k} \cdot A_{i} A_{10} A_{9} \dots A_{k}

Ví dụ 7. Một bảng $2 n \times 2 n$ ô, người ta đánh dấu bất kì $3 n$ ô trong bảng. Chứng minh rằng tồn tại $n$ dòng và $n$ cột sao cho $3 n$ ô được đánh dấu thuộc $n$ dòng và $n$ cột này.

Lời giải

Chọn

n

dòng sao cho số ô được tô là lớn nhất, ta chứng minh rằng số ô được tô trong

n

dòng này là không ít hơn

2 n

ô. \
Thực vậy giả sử số ô được tô là ít hơn

2 n

, khi đó

n

dòng còn lại có nhiều hơn

n

ô được tô, nên có ít nhất một một dòng có 2 ô được tô. Do đó

n

dòng đã chọn, mỗi dòng ít nhất 2 ô được tô nên tổng số ô hơn hoặc bằng

2 n

(mâu thuẫn).\
Vậy ta chỉ cần chọn

n

cột chứa các ô được tô màu nhưng chưa được chọn trong

n

dòng trên thì sẽ có điều cần chứng minh.

Bài tập rèn luyện
Bài 1. Có $(2 n + 1)$ người đứng trên cùng một mặt phẳng, khoảng cách giữa họ không giống nhau. Sau đó mỗi người bắn người gần họ nhất. Chứng minh rằng:

a) Có ít nhất một người còn sống.
b) Không ai bị bắn quá năm viên đạn.
c) Các đường đạn không cắt nhau.

Bài 2. Một hành tinh có 20 quốc gia. Trong ba nước bất kỳ, luôn có hai nước không thiết lập quan hệ ngoại giao với nhau. Chứng minh rằng, hành tình này có tối đa 200 đại sứ quán.
Bài 3. Với $2 n + 3$ điểm trong mặt phẳng, ba điểm bất kỳ không thẳng hàng và bốn điểm bất kỳ không cùng nằm trên một đường tròn. Chứng minh rằng ta có thể chọn ba điểm và vẽ được một đường tròn qua ba điểm đó. Trong $2 n$ còn lại, có $n$ điểm nằm trong đường tròn và $n$ điểm nằm ngoài đường tròn.
Bài 4. Điền các số từ 1 đến $n^{2}$ vào bảng vuông $n \times n$ . Chứng minh rằng có hai ô kề nhau (kề cạnh hoặc kề đỉnh) mà hiệu của chúng không nhỏ hơn $n + 1$ .
Bài 5. Có $N (N \geq 3)$ chơi tenis vòng tròn một lượt. Cuối giải người ta thấy rằng không có ai thắng tất cả các trận thi đấu. Chứng minh rằng có thể tìm được 3 người A, B, C sao cho A thắng B, B thắng C và C thắng A.
Bài 6. Cho $a, b$ là hai số tự nhiên nguyên tố cùng nhau.
Gọi $d = (a, b)$ . Khi đó tồn tại các số nguyên $x, y$ sao cho $x a + y b = d$

Tổ hợp lặp và bài toán chia kẹo Euler

Leave a reply

Trong các bài toán đếm ta gặp bài toán sau: Một người vào cửa hang mua dụng cụ học tập để làm thành một món quà gồm viết, sách và tập, người đó chỉ mua tổng cộng 5 món đồ. Biết rằng trong cửa hàng có 5 cây viết giống nhau, 6 sách giống nhau và 10 cuốn tập giống nhau, hỏi có bao nhiêu cách chọn viết, sách tập để làm quà?

Ta thấy rằng số lượng các viết sách và tập đều lớn hơn số cần mua, do đó bài toán chỉ quay lại việc đếm là có bao nhiêu bộ sách viết tập mà tổng số là 5 cái, trong đó mỗi cái có hoặc không có.

Có ba đối tượng là viết, sách và tập, tạ kí hiệu là $A = {V, S, T}$ . Một món quà gồm 5 cái, do đó quà có thể là $X = {V, V, V, S, T}$ , gồm 3 cây viết và 1 sách, 1 tập, hoặc là tập $Y = {V, V, S, T, T}$ , ta thấy các đối tượng $V, T$ là lập lại. Khi đó ta nói tổ hợp $X, Y$ là tổ hợp lặp.

Để định nghĩa rõ hơn ta có định nghĩa sau:

Định nghĩa. Cho tập $A = {a_{1}, a_{2}, \dots, a_{k}}$ . Một ánh xạ từ $p : A \mapsto N$ , khi đó $P$ được gọi là một multiset của A.

Ví dụ 1. Cho $A = {a, b, c}$ . Ánh xạ $p : A \mapsto N$ như sau: $p (a) = 2, p (b) = 1, p (c) = 1$ . Khi đó ta có thể kí hiệu $p$ là $(a a b c)$ , hay $(b a a c)$ ,.., không tính đến thứ tự của các phần tử $a, b, c$ .

Đặt $n = p (a_{1}) + p (a_{2}) + \dots + p (a_{k})$ , bài toán đặt ra là có bao nhiêu ánh xạ $p : A \mapsto N$ mà $n = p (a_{1}) + p (a_{2}) + \dots + p (a_{k})$ .

Tiếp theo ví dụ trên, nếu $p (a) + p (b) + p (c) = 2$ thì có các multiset sau: $(a b), (a c), (b c), (a a), (b b), (c c)$ , 6 multiset.

Tính chất. Cho tập $A = {a_{1}, a_{2}, \dots, a_{k}}$ , số ánh xạ $p : A \mapsto N$ thỏa $p (a_{1}) + \dots + p (a_{k}) = n$ là $C_{n + k - 1}^{n}$

Chứng minh

Mỗi ánh xạ $p$ ta cho tương ứng với một dãy nhị phân độ dài $n + k - 1$ , trong đó $p (a_{1})$ chữ số đầu là 0, tiếp theo là số 1, rồi $p (a_{2})$ chữ số $0$ ,…cuối cùng là $p (a_{k})$ chữ số $0$ . Ví dụ bộ $V V S T T$ ứng với dãy $0010100$ .

Rõ ràng đây là tương ứng 1 – 1, do đó số ánh xạ $p$ bằng số dãy nhị phân, do đó ta chỉ cần đếm số dãy nhị phân.

Ta thấy dãy có $n + k - 1$ chữ số trong đó có $k - 1$ chữ số $1$ , do đó số dãy nhị phân chỉ là số cách chọn vị trí cho $k - 1$ chữ số $1$ nên số dãy nhị phân là $C_{n + k - 1}^{k - 1}$ .

Do đó số ánh xạ $p$ là $C_{n + k - 1}^{k - 1}$

Trở lại bài toán trên, ta thấy số món quà có 5 cái là một tổ hợp lặp chập 5 của sách, viết, tập, do đó số món quà có thể là $C_{5 + 2 - 1}^{2} = C_{6}^{2} = 15$ .

(Chú ý trong bài toán trên, đảm bảo số mỗi loại sản phẩm có không ít hơn 5 cái).

Bài toán 1. (Chia kẹo Euler). Cho $n$ viên kẹo giống nhau đem chia cho $k$ người, hỏi có bao nhiều cách chia.

Giải

Ta gọi $k$ người là $a_{1}, a_{2}, \dots a_{k}$ , với mỗi cách chia kẹo là một multiset của $A$ mà $p (a_{1}) + p (a_{2}) + \dots + p (a_{k}) = n$ .

Do đó số cách chia kẹo là $C_{n + k - 1}^{n}$ .

Bài toán 2. Giải bài toán trên với cách chia sao cho mỗi người có ít nhất một viên.

Giải

Trước hết phát cho mỗi người một viên, thì còn $n - k$ viên kẹo, tiếp tục áp dụng bài toán trên với $n - k$ . Khi đó số cách chia là

$C_{n - 1}^{k - 1}$

Ta có thể giải bài toán trên mà không cần sử dụng bài toán 1 bằng cách xây dựng dãy nhị phân thỏa: $a_{1}$ chữ số đầu là 0, tiếp theo là số 1, tiếp là $a_{2}$ chữ số 0, …., cuối cùng là $a_{k}$ chữ số 0. Dãy này có $k - 1$ chữ số 1 đứng giữa $n$ chữ số 0 và không có hai chữ số $1$ nào đứng kề nhau. Khi đó số dãy nhị phân là: $C_{n - 1}^{k - 1}$ .

Phần kế tiếp ta cùng tìm hiểu và giải một số bài toán có thể đưa về bài toán tổ hợp lặp hay bài toán chia kẹo Euler. Các bạn chờ nhé.

Bài toán 1 và 2 có thể phát biểu dưới dạng sau.

Bài toán 3. Cho phương trình $x_{1} + x_{2} + \dots + x_{k} = n$ trong đó $k, n$ là các số nguyên dương.

a. Tìm số nghiệm tự nhiên của phương trình.

b. Tìm số nghiệm nguyên dương của phương trình.

Như bài toán trên ta đã biết, số nghiệm tự nhiên của phương trình là $C_{n + k - 1}^{k - 1}$ .

Số nghiệm nguyên dương của phương trình là $C_{n - 1}^{k - 1}$ .

(Phần 2)

Trong phần trước ta đã biết, số nghiệm nguyên không âm của phương trình $x_{1} + x_{2} + \dots + x_{k} = n$ là $C_{n + k - 1}^{k - 1}$ , và số nghiệm nguyên dương là $C_{n - 1}^{k - 1}$ .

Từ bài toán này ta có thể giải các bài toán sau:

Ví dụ 1. Tìm số nghiệm nguyên của phương trình $x_{1} + x_{2} + x_{3} + x_{4} + x_{5} = 30$ nếu:

a) $x_{i} \geq 2 \forall i = \overset{―}{1, 5}$ .

b) $3 < x_{1}, x_{2}$ và $x_{3}, x_{4}, x_{5} > 5$ .

c) $x_{1}, x_{2}, x_{3}, x_{4} \geq 4$ và $0 < x_{5} < 3$ .

Giải

a) $x_{1} + x_{2} + x_{3} + x_{4} + x_{5} = 30$ , $x_{i} \geq 2 \forall i = \overset{―}{1, 5}$ . (1). Ta đi tìm số nghiệm của hệ (1).

Để đưa về bài toán gốc, ta đặt ẩn phụ như sau: $y_{i} = x_{i} - 1 \geq 1$ với mọi $i = \overset{―}{1, 5}$ .

Khi đó ta có $y_{1} + 1 + y_{2} + 1 + y_{3} + 1 + y_{4} + 1 + y_{5} + 1 = 30 \Leftrightarrow y_{1} + y_{2} + y_{3} + y_{4} + y_{5} = 25$ với $y_{i} \geq 1$ . (2)

Một bộ nghiệm của (2) cho tương ứng một bộ nghiệm thỏa (1), mà số nghiệm của $(2)$ là $C_{24}^{4}$ (Theo bài toán chia kẹo Euler), do đó số nghiệm của (1) là $C_{24}^{4}$ .

b) Tương tự câu a, đặt $y_{1} = x_{1} - 3, y_{2} = x_{2} - 3, y_{3} = x_{3} - 5, y_{4} = x_{4} - 5, y_{5} = x_{5} - 5$ , từ (1) ta có phương trình $y_{1} + y_{2} + y_{3} + y_{4} + y_{5} = 9$ và $y_{i} \geq 1$ . Số nghiệm là $C_{8}^{4}$ .

c) Xét $x_{5} = 1, 2$ và đặt ẩn phụ $y_{i} = x_{i} - 3$ ta có đáp số là: $C_{16}^{3} + C_{15}^{3}$ .

Ví dụ 2. Có bao nhiêu bộ $(x_{1}, x_{2}, . . ., x_{10})$ các số nguyên dương thỏa $x_{1} + x_{2} + \dots x_{10} < 2020$ .

Giải

Đặt $x_{11} = 2020 - (x_{1} + x_{2} + \dots + x_{10})$ thì $x_{11} \geq 1$ .

Khi đó ta có phương trình $x_{1} + \dots + x_{11} = 2020$ và $x_{i} \geq 1$ .

Do đó số nghiệm là $C_{2019}^{10}$ .

Ví dụ 3. Có bao nhiêu bộ $(x_{1}, x_{2}, . . ., x_{10})$ các số tự nhiên thỏa $x_{1} \leq x_{2} \leq x_{3} \leq \dots \leq x_{10} \leq 2020$ .

Giải

Đặt $y_{1} = x_{1}, y_{2} = x_{2} - x_{1} \geq 0$ , $y_{2} = x_{3} - x_{2} \geq 0$ , …, $y_{11} = 2020 - x_{10} \geq 0$ .

Khi đó $y_{1} + y_{2} + \dots + y_{11} = 2020$ với $y_{i} \geq 0$ . (2)

Với một bộ nghiệm của (2) sẽ tương ứng duy nhất một bộ $(x_{1}, x_{2}, \dots, x_{10})$ thỏa đề bài.

Số nghiệm của (2) là $C_{2030}^{10}$ , đó cũng chính là số bộ $(x_{1}, x_{2}, \dots, x_{10})$ thỏa đề bài.

Ví dụ 4. (VMO 2012) Cho một nhóm gồm 5 cô gái, kí hiệu là $G_{1}, G_{2}, G_{3}, G_{4}, G_{5}$ và 12 chàng trai. Có 17 chiếc ghế được xếp thành một hàng ngang. Người ta xếp nhóm người đã cho vào các chiếc ghế sao đó sao cho các điều kiện sau được đồng thời thỏa mãn :
1) Mỗi chiếc ghế có đúng một người ngồi;
2) Thứ tự ngồi của các cô gái, xét từ trái qua phải, là $G_{1}, G_{2}, G_{3}, G_{4}, G_{5}$ ;
3) Giữa $G_{1}$ và $G_{2}$ có ít nhất 3 chàng trai;
4) Giữa $G_{4}$ và $G_{5}$ có ít nhất 1 chàng trai và nhiều nhất 4 chàng trai.
Hỏi có tất cả bao nhiêu cách xếp như vậy?

Giải

Đánh số thứ tự các ghế từ trái sang phải là $1, 2, \dots, 17$ .

Gọi $x_{1}$ là số chàng trai được xếp bên trái $G_{1}, x_{2}$ là số chàng trai ở giũa $G_{1}$ và $G_{2}, x_{3}$ là số chàng trai ở giữa $G_{2}$ và $G_{3}, x_{4}$ là số chàng trai ở giữa $G_{3}$ và $G_{4}, x_{5}$ là số chàng trai ở giữa $G_{4}$ và $G_{5}, x_{6}$ là số chàng trai được xếp ở bên phải $G_{5}$ . Khi đó bộ số $(x_{1}, x_{2}, \dots, x_{6})$ hoàn toàn xác định vị trí các cô gái và ta có:
1) $x_{1} + x_{2} + \dots + x_{6} = 12$
2) $3 \leq x_{2}$ .
3) $1 \leq x_{5} \leq 4$
Đổi biến $y_{2} = x_{2} - 3$ và $y_{5} = x_{5} - 1$ ta được $x_{1} + y_{2} + x_{3} + x_{4} + y_{5} + x_{6} = 8$ với các $\hat{ẩn}$ không âm và có thêm điều kiện $y_{5} \leq 3$ . Tiếp theo, sử dụng bài toán chia kẹo của Euler ở dạng $x_{1} + y_{2} + x_{3} + x_{4} + x_{6} = 8 - y_{5}$ ta được đáp số (phần phân ghế cho các cô gái) là $C_{12}^{4} + C_{11}^{4} + C_{10}^{4} + C_{9}^{4} = 1161$ .
Vì còn có 12 chàng trai có thể hoán đổi vị trí ở 12 chiếc ghế dành cho họ nên số cách xếp thỏa mãn yêu cầu bài toán là $1161 \cdot 12!$

Ví dụ 5. Có bao nhiêu bộ số nguyên dương $(a, b, c, d)$ thỏa $d = m a x {a, b, c, d}, d \leq 2015$ và

$(a d + b c) (b d + a c) (c d + a b) = (d - a)^{2} (d - b)^{2} (d - c)^{2}$ .

Giải

Trước hết ta chứng minh $d = a + b + c$ bằng phản chứng.
Khi dó $3 \leq d \leq 2015$ , với mỗi $d$ thì số bộ $(a, b, c)$ là $C_{d - 1}^{2}$ .
Do đó số bộ thỏa đề bài là $C_{2}^{2} + C_{3}^{2} + \dots + C_{2014}^{2}$ .

Trên đây là một số bài toán liên quan đến bài toán chia kẹo Euler, các bạn hãy đọc và tìm hiểu thêm trong các tài liệu khác.

Bài tập rèn luyện.

Bài 1. Tìm số nghiệm nguyên dương của phương trình: $x_{1} + x_{2} + . . . + x_{5} = 100$
Bài 2. Tìm số nghiệm không âm của phương trình $x_{1} + x_{2} + x_{3} + x_{4} = 20$ .
Bài 3. Có bao nhiêu số tự nhiên có 3 chữ số mà tổng các chữ số bằng 11 ?
Bài 4. Tìm số nghiệm nguyên của phương trình $x_{1} + x_{2} + x_{3} + x_{4} = 30$ nếu:
a) $x_{i} \geq 0 \forall i$ .
b) $2 \leq x_{1} \leq 7$ , $x_{i} \geq 0, i = 2, 3, 4$ .
c) $x_{1} \geq - 3, x_{2} \geq - 1, x_{3}, x_{4} \geq 1$ .
Bài 5. Tìm số nghiệm nguyên dương của phương trình $4 x_{1} + x_{2} + x_{3} + x_{4} = 15$ .
Bài 6. Có 4 viên bi vàng và 10 viên bi xanh. Hỏi có bao nhiêu cách sắp xếp các viên bi thỏa:
a) Không có bi vàng nào kề nhau.
b) Giữa hai bi vàng có ít nhất 2 bi xanh.

Bài 7. Để bảo vệ máy tính của minh khỏi su tấn công của hacker, một lâp trinh viên muốn thiết lập một mât khẩu cho máy tính của mình. Mât khẩu này bao gồm tất cả các chữ cái trong bảng chữ cái tiêng Anh, mỗi chữ cái một lần xuất hiện và các chữ nguyên âm không đứng cạnh nhau. Hỏi lâp trình viên đó có bao nhiêu cách cài đăt mât khẩu?

Bài 8. Bốn anh em An, Bình, Cừng, Danh rất thích ăn keo. Nhân dip Tết, me của các câu đực thửng rất nhiều quà, trong đó có một phần quà là một bịch keo bao gồm 125 viên keo. Vì quá thich ăn kẹo nên bốn anh em đã xin mẹ thêm một vài bịch keo khác giống nhu vậy nữa, nhưng me nhất quyết không cho vì sơ ăn nhiều keo sẽ bi sâu răng, do đó mẹ chỉ cho các câu ăn số kẹo trong bịch kia thôi. Thế là họ ngay lâp tức chia nhau số keo nói trên. Hỏi họ có tông công bao nhiêu cách chia keo ? (cho rằng 125 viên keo là giống hệt nhau, và anh em họ có quyền không ăn môt số viên keo trong số 125 viên keo ban đầu, đồng thời cũng có thể xảy ra trường họ có một nguròi không durọc chia viên keo nào).

Tài liệu tham khảo.

Jiri-herman-radan-kucera-jaromir-simsa, Counting-and-configurations-problems-in-combinatorics-arithmetic-and-geometry
Chuyên đề toán học 11 - Tập san của học sinh Trường Phổ thông Năng khiếu.

Toán Việt

Chia sẻ và học hỏi

Category Archives: Tổ hợp

Phương pháp chứng minh phản chứng (P2)

Phương pháp ánh xạ trong các bài toán tổ hợp

Đếm bằng 2 cách

Các bài toán tổ hợp trong kì thi Junior Bankan – P1

Chỉnh hợp – Hoán vị – Tổ hợp

Các bài toán tổ hợp trên dãy số

Phương pháp ánh xạ trong các bài toán tổ hợp

Nguyên lý Đirichlet và áp dụng

Giải bài toán bằng đại lượng cực biên-Phần 1

Tổ hợp lặp và bài toán chia kẹo Euler