Category Archives: Phương pháp chứng minh

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 $\mathbb{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 $\mathbb{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, \cdots, A_6$. Khi đó tồn tại $A_iA_{i+1} \leq 60^\circ$, suy ra $A_iA_{i+1} < AA_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 $ABC$ 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 $ABC$, vô lý.
Do $S_{A’B’C’} = 4S_{ABC} \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 $PA, PC$. Nếu $H$ thuộc tia $BA$ thì $BE < PH$, nếu $H$ thuộc đoạn $BC$ thì $BD < PH$. Mâu thuẫn với $PH$ 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_1A_2…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_7A_iA_{i-1}A_1A_6A_{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_2A_7A_6A_5A_4A_3A_1A_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\cdots 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_1A_k\cdot A_iA_{10}A_9…A_k$.

Ví dụ 7. Một bảng $2n \times 2n$ ô, người ta đánh dấu bất kì $3n$ ô trong bảng. Chứng minh rằng tồn tại $n$ dòng và $n$ cột sao cho $3n$ ô đượ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 $2n$ ô. \\
Thực vậy giả sử số ô được tô là ít hơn $2n$, 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 $2n$ (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ó $(2n + 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 $2n + 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 $2n$ 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 $$xa+yb=d$$

 

Phương pháp chứng minh quy nạp – Các dạng khác

Leave a reply

Trong bài này, chúng ta tiếp tục tìm hiểu thêm và phương pháp quy nạp. Ngoài dạng quy nạp như đã biết ta còn một số dạng quy nạp khác như: Quy nạp mạnh, quy nạp bước nhảy, quy nạp lùi.

Quy nạp mạnh được phát biểu như sau: Để chứng minh mệnh đề $P(n)$ đúng với mọi số tự nhiên $n$, ta thực hiện theo hai bước sau:

  • Chứng minh $P(n)$ đúng với $n=1$.
  • Giả sử $P(n)$ đúng với $1, 2, \cdots, n$. Chứng minh $P(n+1)$ đúng.

Ví dụ 1. Cho $x$ thỏa $x+\dfrac{1}{x}$ là số nguyên. Chứng minh rằng $x^n+\dfrac{1}{x^n}$ là số nguyên với mọi $n$.

Lời giải. 

  • Ta có $x + \dfrac{1}{x}$ là số nguyên  đúng (theo giả thiết).
  • Giả sử $x^k + \dfrac{1}{x^k}$ là số nguyên với mọi $k = \overline{1,n}$. Ta cần chứng minh $x^{n+1} + \dfrac{1}{x^{n+1}}$.
    • $(x^{n+1} + \dfrac{1}{x^{n+1}} = (x+\dfrac{1}{x})(x^n + \dfrac{1}{n})  – (x^{n-1}+\dfrac{1}{x^{n-1}})$.
    • Theo giả thiết quy nạp thì $x^{n+1} + \dfrac{1}{x^{n+1}}$ là số nguyên.
  • Vậy ta có $x^n + \dfrac{1}{x^n}$ là số nguyên với mọi $n$.

 

Dạng kế tiếp là Quy nạp bước nhảy  được phát biểu như sau: Chứng minh mệnh đề $P(n)$ đúng với mọi $n$, ta làm như sau:

  • Chứng minh $P(1), P(2), \cdots, P(k)$ đúng.
  • Giả sử $P(n)$ đúng. Ta chứng minh $P(n+k)$ đúng.

Ví dụ 2. Chứng minh rằng với mọi số tự nhiên $M$ tồn tại số tự nhiên $n$ và cách chọn các dấu $+$ hoặc $-$ sao cho

$M = \pm 1^2 \pm 2^2 \cdots \pm n^2$.

Lời giải.

  • Khi $M = 1, 2, 3, 4$ ta có $1 = 1^2$, $2 = -1^2-2^2-3^2+4^2$, $3 = -1^2+2^2$ và $4 = 1^2-2^2-3^2+4^2$.
  • Giả sử đúng với $M$, tức là tồn tại $n$ thỏa $M = \pm 1^2 \pm 2^2 \cdots \pm n^2$, khi đó $M + 4 = \pm 1^2 \pm 2^2 \cdots \pm n^2 +(n+1)^2-(n+2)^2-(n+3)^2 + (n+4)^2$.

Ví dụ 3.  Chứng minh rằng với mọi số tự nhiên $n$ thì phương trình $a^2 + b^2 = c^n$ luôn có nghiệm trong tập các số nguyên dương.

Lời giải. 

  • Rõ ràng nếu $n=1, 2$ thì phương trình luông có nghiệm nguyên dương.
  • Giả sử phương trình có nghiệm nguyên dương là $a, b, c$ với $n$ nào đó, tức là $a^2 + b^2 = c^n$.
    • Khi đó với $n+2$ thì xét $(ac), (bc), c$: $(ac)^2+(bc)^2 = c^2 (a^2+b^2) = c^{n+2}$.
    • $(ac, bc, c$ là nghiệm.
  • Vậy phương trình luôn có nghiệm với mọi $n$.

Dạng kế tiếp là Quy nạp lùi được phát biểu như sau:

  • Chứng minh $P(a_i)$ đúng với dãy $(a_i)$ là dãy con tăng thực sự của tập các số tự nhiên.
  • Giả sử $P(n)$ đúng, chứng minh $P(n-1)$ đúng.

Ví dụ 4. 

a) Hãy chỉ ra cách sắp 8 số nguyên dương đầu tiên 1, 2, …, 8 thành một dãy $a_1, a_2 ,…, a_8$ sao cho 2 số $a_i, a_j$ bất kì $(i < j)$ thì mọi số trong dãy nằm giữa $a_i$ và $a_j$ đều khác $\dfrac{a_i + a_j}{2}$.
b) Chứng minh rằng với $N$ số nguyên dương đầu tiên $1, 2, …, N$ luôn tìm được cách sắp thành dãy $a_1, a_2, …, a_N$ sao cho dãy thỏa mãn điều kiện như câu a).
Lời giải.

a) Một cách xếp thỏa đề bài là 26481537.\
b)

Bước 1.Ta chứng minh bằng quy nạp với $n = 2^k$ thì luôn tồn tại một cách xếp thỏa đề bài.

  • Nếu $k = 1$, hiển nhiên đúng.
    Giả sử luôn tồn tại một cách xếp thỏa đề bài với $n = 2^k$, cách xếp đó là $a_1, a_2, …, a_n$.
    Ta chứng minh tồn tại một cách xếp với $n = 2^{k+1}$.
    Thật vậy xét hoán vị $(2a_1, 2a_2,…, 2a_n, 2a_1-1, 2a_2-1, …, 2a_n-1)$ là một hoán vị của $1, 2, …, 2^{k+1}$. Ta chứng minh hoán vị trên thỏa đề bài.

    • Ta có nếu $a_i, a_j \in \{2a_1, 2a_2, …, 2a_n\}$ theo giả thiết quy nạp không có số nào nằm giữa $a_i, a_j$ bằng $\dfrac{1}{2}(a_i+a_j)$.
    • Nếu $a_i \in \{2a_1, …, 2a_n\}, a_j \in \{2a_1-1, 2a_2-1, …, 2a_n-1\}$ thì $\dfrac{1}{2}(a_i +a_j)$ không phải số nguyên.
    • Nếu $a_i, a_j \in \{2a_1-1, 2a_2-1, …, 2a_n-1\}$ theo giả thiết quy nạp thì cũng có số nào nằm giữa $a_i, a_j$ bằng $\dfrac{1}{2}(a_i + a_j)$.

Vậy bài toán đúng với $n = 2^k$.(1)
Bước 2. Nếu bài toán đúng với $n$, ta chứng minh bài toán đúng với $n-1$.

Xét các số $a_1, a_2, …, a_n$ là một hoán vị thỏa đề bài của $1,2,…,n$.

Khi đó nếu xóa bất kì số nào trong các số $a_1, …, a_n$ thì dãy còn lại vẫn thỏa điều kiện. (2)
Từ (1) và (2) ta có điều cần chứng minh.

Quy nạp lùi cũng là một trong những cách chứng minh bất đẳng thức Cauchy tổng quát: $\dfrac{a_1+a_2 + \cdots+a_n}{n} \geq \sqrt[n]{a_1a_2\cdots a_n}$.

Các bạn tự làm thử nhé.

Trên đây là một số dạng quy nạp thường gặp trong chứng minh toán. Tùy theo tình huống mà ta sử dụng cho phù hợp, các bạn cần làm thêm nhiều bài tập để rèn luyện.

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

Bài 1. Ta gọi tổng các số tự nhiên từ 1 đến n là số tam giác. Chứng minh rằng tồn tại vô hạn các số tam giác đồng thời là số chính phương.

Bài 2. (Chọn đội tuyển PTNK 2014)Tìm số nguyên dương $n$ lớn nhất thỏa mãn các điều kiện sau:

  • $n$ không chia hết cho 3;
  • Bảng vuông $n \times n$ ô không thể được phủ kín bằng 1 quân tetramino $1 \times 4$ và các quân trimino kích thước $1 \times 3$. Trong phép phủ các quân tetramino và trimino được phép quay dọc nhưng không được phép chườm lên nhau hoặc nằm ngoài ra bảng vuông.

Bài 3. Có $n$ số tự nhiên từ 1 đến $n$ được viết thành một dòng theo một thứ tự nào đó. Mỗi bước thực hiện biến đổi như sau: nếu số đầu tiên là $k$ thì $k$ số đầu tiên sẽ được viết theo thứ tự ngược lại. Chứng minh rằng sau hữu hạn bước thì số đầu tiên của dòng là số 1.

Bài 4. Trong cuộc họp có $2n$ ($n \geq 2$) người, một số người bắt tay nhau và người ta đếm được có $n^2+1$ cái bắt tay. Chứng minh rằng có $n$ bộ ba, mà mỗi bộ ba đôi một bắt tay nhau.

Bài 5. Chứng minh rằng với mọi số tự nhiên $n$ tồn tại các số nguyên $x, y, z$ phân biệt sao cho $x^2+y^2+z^2 = 14^n$.

Bài 6. Trong một giải đấu tennis có 10 người tham dự, hai đối thủ gặp nhau đúng một trận. Chứng minh rằng, sau khi kết thúc giải có thể sắp xếp các tay vợt thành một hàng mà người đứng trước thắng người đứng sau.

Phương pháp chứng minh quy nạp – P2

Leave a reply

Trong phần trước ta đã làm quen với phương pháp chứng minh quy nạp và áp dụng vào chứng minh một vài đẳng thức, bất đẳng thức hay các bài toán chia hết. Bài này tiếp tục là ứng dụng của quy nạp trong việc chứng minh các bài toán khác, trong cái đề thi học sinh giỏi hay tuyển sinh.

Ví dụ 1. Người ta lát nền nhà hình vuông kích thước $n \times n$ ô bằng các viên gạch như hình vẽ dưới sao cho còn chừa lại một ô không lát.
a) Hãy chỉ ra một cách lát như trên với nền nhà kích thước $4 \times 4$ và $8 \times 8$.
b) Hãy chứng minh rằng luôn tồn tại một cách lát nền nhà có kích thước $2^k \times 2^k$ (k nguyên dương) với ô trống còn lại nằm ở vị trí $(i,j)$ bất kì.

Lời giải

a) Các bạn tự làm.
b) Ta chứng minh bằng quy nạp.

  • Với $k = 2$ hiển nhiên đúng.
  • Giả sử với $k$ thì nền $2^k \times 2^k$ bỏ ô $(i;j)$ bất kì thì luôn phủ được. Ta chứng minh đúng với $k+1$.
    Với nền nhà $2^{k+1} \times 2^{k+1}$ ta chia thành 4 hình vuông $2^k \times 2^k$. Khi đó ô bỏ đi thuộc một trong 4 hình vuông đó, ta phủ được hình vuông này theo giả thiết quy nạp. Tiếp tục,theo giả thiết quy nạp, với 3 hình vuông còn lại, bỏ đi ô ở góc (hình vẽ) thì ta có thể phủ được. Khi đó 3 ô ở góc ta phủ tiếp bằng một viên gạch.
  • Với cách thực hiện đó thì ta có thể phủ được nền nhà $2^{k+1} \times 2^{k+1}$ khi bỏ ô bất kì.

Ví dụ 2. Trong cuộc họp có $2n$ ($n \geq 2$) người, một số người bắt tay nhau và người ta đếm được có $n^2+1$ cái bắt tay. Chứng minh rằng có 3 người đôi một bắt tay nhau.

Lời giải
  • Rõ ràng bài toán đúng khi $n=2$.
  • Giả sử bài toán đúng với $n$, ta chứng minh bài toán đúng với $n+1$. Xét hai người $A, B$ bắt tay.
    Nếu số bắt tay của $A$ và $B$ với $2n$ người còn lại không vượt quá $2n$ thì $n$ người kia có $n^2+1$ cái bắt tay, ta có điều cần chứng minh.
    Nếu số người bắt tay với $A, B$ là hơn $2n$ cái.
  • Do đó trong $2n$ người kia thì sẽ có ít nhất một người bắt tay với cả $A$ và $B$, ta có điều cần chứng minh.

Ví dụ 3.  a) Cho bốn số nguyên dương $a_1, a_2, a_3, a_4$ sao cho $1 \leq a_k \leq k$ với mọi $ k= 1,2, 3, 4$ và tổng $S = a_1 + a_2 + a_3 + a_4$ là một số chẵn. Chứng minh rằng có ít nhất một trong các số dạng $\pm a_1 \pm a_2 \pm a_3 \pm a_4$ có giá trị bằng 0.
b) Cho 1000 số nguyên dương $a_1, a_2,…, a_{1000}$ sao cho $1 \leq a_k \leq k$ với $k = 1, 2, …, 1000$ và tổng $S = a_1 + a_2 + …+a_{1000}$ là một số chẵn.\
Hỏi trong các số có dạng $\pm a_1 \pm a_2 … \pm a_{1000}$ có số nào bằng 0 hay không? Giải thích vì sao?

Lời giải

a) Ta có $4 \leq S \leq 10$ và $S$ chẵn, suy ra $S = 4, 6, 8, 10$. Xét các trường hợp sau:

  • $S = 4$, suy ra $a_1 = a_2 = a_3 = a_4 = 1$. Suy ra $- 1 – 1+ 1 + 1 = 0$.
  • $S = 6$ ta có $6 = 1 + 1 + 1 + 3 = 1 + 1 + 2 + 2$, suy ra có một cách thỏa đề bài.
  • $S = 8$ ta có $8 = 1 + 1 + 2 + 4 = 1 + 1 + 3 + 3 = 1 + 2 + 2 + 3 = 2 + 2 + 2 + 2$. Suy ra mỗi cách đều tồn tại một cách chọn dấu $ + , – $ thỏa đề bài.
  • $S = 10 = 1 + 2 + 3 + 4$. Suy ra có một cách thỏa đề bài.

a) Ta chứng minh bằng quy nạp mệnh đề sau: Cho $n$ các số nguyên dương thỏa $1 \leq a_k \leq k$ thỏa $S_n = a_1 + …+a_n$ chẵn. Khi đó tồn tại số có dạng $\pm a_1 \pm a_2 … \pm a_{n}$ bằng 0.

  • Khi $n = 2$ ta có $a_1 + a_2$ chẵn, suy ra $a_1 = a_2 = 1$. Suy ra $a_1 – a_2 = 0$.
  • Giả sử bài toán đúng với $k\leq n$. Ta chứng minh bài toán đúng với $n + 1$. Ta có $S_{n+1} = a_1 + …+a_{n} + a_{n+1}$ chẵn. Ta có $0\leq |a_{n} – a_{n+1}| \leq n$.
    • Nếu $a_n – a_{n+1} = 0$ ta áp dụng giả thiết quy nạp với $n-1$ số $a_1, …, a_{n-1}$ ta có điều cần chứng minh.
    • Nếu $a_n – a_{n+1} \neq 0$. Áp dụng giả thiết quy nạp với $n$ số $a_1, a_2, …, a_{n-1}, |a_n-a_{n+1}|$ ta thấy $a_1 + …+a_{n+1}$ chẵn nên $a_1 + …+a_{n-1} + |a_n – a_{n+1}|$ chẵn.
    • Suy ra tồn tại số có dạng $\pm a_1 \pm a_2 … \pm |a_{n}-a_{n+1}| = \pm a_1 \pm a_2 … \pm a_{n+1}$ bằng 0.

 

Ví dụ 4. (USAMO 2002) Cho tập S có 2002 phần tử, số tự nhiên $k$ thỏa $0 \leq k \leq 2^{2002}$ chứng minh rằng tồn tại cách tô màu các tập con của S bằng hai màu xanh và đỏ thỏa:
a)  Có đúng $k$ tập được tô màu đỏ.
b) Hợp của hai tập đỏ là một tập đỏ.
c) Hợp của hai tập xanh là một tập xanh.

Lời giải
  • Ta chứng minh bài toán đúng với tập $S$ có số phần tử $n$ bất kì bằng quy nạp.

    Rõ ràng bài toán đúng với $n=1$, $S=\{1\}$. Nếu $k=0$ tô màu xanh cả hai tập con. Nếu $k=1$ tô màu đỏ tập $S$, xanh tập rỗng. Nếu $k=2$ thì tô $S$ và rỗng đều màu đỏ.

  • Giả sử $S$ có $n$ phần tử thì với mọi $k$ đều tồn tại cách tô thỏa đề bài.
    Ta chứng minh bài toán đúng với $S$ có $n+1$ phần tử.
    Giả sử $S = \{1, 2, \cdots, n, n+1\}$, $0 \leq k \leq 2^{n+1}$.

    • Nếu $k \leq 2^n$.Theo giả thiết quy nạp các tập con của $\{1, 2, \cdots, n\}$ được tô thỏa đề bài và các tập con chứa $n+1$ ta tô màu xanh. Rõ ràng cách tô này thỏa đề bài.
    • Nếu $ 2^n < k \leq 2^{n+1}$. Thì ta chỉ cần đổi màu các tập tô như trường hợp trên, tập nào tô màu xanh thì đổi thì màu đỏ và ngược lại. Rõ ràng thỏa đề bài.

Trên đây là một vài ví dụ khá hay về áp dụng của Quy nạp, tất nhiên còn nhiều bài tập khác cũng hấp dẫn không kém, các bạn tự tìm hiểu nhé. Chúng ta sẽ trở lại trong bài viết sau về một số dạng quy nạp thường gặp.

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

Bài 1. Lúc đầu có $n$ lít nước để vào một số lu, mỗi lu chứa đúng một số nguyên dương lít nước, ta thực hiện cách đong nước như sau: nếu số nước ở lu $A$ nhỏ hơn hoặc bằng lu $B$ thì ta có thể cho hết nước của $B$ vào $A$ một lượng bằng lượng nước lu $A$ đang có.
a) Nếu có 3 lu nước chứa lần lượt $2, 3, 8$ thì có thể đưa về hai lu không? Tại sao?
b) Nếu $n=1024 $. Chứng minh rằng ta có thể đưa số nước hết về một lu. Giả sử lu này là lu lớn, chứa đủ số nước đã có.
Bài 2. Cho $n$ đội bóng, $n$ là số chẵn lớn hơn 2.  Mỗi một lượt, các đội chia cặp để đấu với nhau một trận. Chứng minh rằng sau hai lượt thì có thể tìm được $\dfrac{n}{2}$ đội mà không có hai đội nào đấu với nhau.

Bài 3. Cho $n = 2^k$, chứng minh rằng người ta có thể chọn $n$ số nguyên từ $2n-1$ số nguyên để tổng của chúng chia hết cho $n$.

Bài 4. Gọi $x_1, x_2$ là nghiệm của phương trình $x^2 + 2017 x – 1 = 0$. Đặt $S_n = x_1^2+x_2^n$. Chứng minh rằng $S_n$ và $S_{n+1}$ là nguyên tố cùng nhau với mọi $n$.

Phương pháp chứng minh quy nạp – P1

Leave a reply

Phương pháp chứng minh quy nạp là một trong những phương pháp chứng minh quan trọng trong toán học. Trong bài viết nhỏ này dành cho các bạn THCS chúng tôi xin trình bày một số dạng của phương pháp này trong việc chứng minh các bài toán ở các lĩnh vực như: Đại số, số học, tổ hợp. Hy vọng các em có thể nắm bắt vận dụng phù hợp trong các tình huống cụ thể.

Để chứng minh một mệnh đề $P(n)$ là đúng với mọi số nguyên dương $n$, ta thực hiện các bước sau:

  • Bước cơ sở:      Chứng minh $P(1)$ đúng.
  • Bước quy nạp: Giả sử $P(n)$ đúng với $n$ nào đó (giả thiết quy nạp), chứng minh $P(n+1)$ đúng.

Ví dụ 1. Chứng minh rằng với mọi số nguyên dương $n$ thì $1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$.

Lời giải. 

  • Khi $n=1$ rõ ràng : $1 = \dfrac{1(1+1)}{2}$.
  • Giả sử đẳng thức đúng với $n$, ta chứng minh đẳng thức đúng với $n+1$.
    • Thật vậy áp dụng giả thiết quy nạp ta có: $1+2+\cdots+n+n+1 = \dfrac{n(n+1)}{2} + n+1 = \dfrac{(n+1)(n+2)}{2}$.
  • Vậy đẳng thức đúng với mọi $n$.

Ví dụ 2. Chứng minh $n^3+11n$ chia hết cho 6 với mọi số tự nhiên $n$.

Lời giải. 

  • Khi $n = 0$ ta có $0^3+11\cdot 0 = 0$ chia hết cho 6.
  • Giả sử $n^3+11n$ chia hết cho 6, ta chứng minh $(n+1)^3+11(n+1$ chia hết cho 6.
    • Thật vậy $(n+1)^3 + 11(n+1) = n^3 + 11n + 3n(n+1)+12$.
    • Theo giả thiết quy nạp thì $n^3+11n$ chia hết cho 6, và $3n(n+1), 12$ cũng chia hết cho 6 nên $(n+1)^3+11n$ chia hết cho 6.
  • Vậy $n^3+11n$ chia hết cho 6 với mọi $n$.

Trong một số trường hợp ta cần chứng minh $P(n)$ đúng với mọi số tự nhiên $n \geq n_o$ nào đó, ta cũng làm tương tự, chỉ thay bước cơ sở thành: Chứng minh $P(n_o)$ đúng.

Ví dụ 3. Chứng minh rằng $2^n > n^2$ với mọi $n \geq 5$.

Lời giải. 

  • Khi $n = 5$ ta có $2^5 > 5^2 $( đúng)
  • Giả sử $2^n > n^2$ với $n> 5$. Ta cần chứng minh $2^{n+1} > (n+1)^2$.
    • Thật vậy áp dụng giả thiết quy nạp ta có $2^{n+1} = 2\cdot 2^n > 2n^2$.
    • Mà $2n^2 > (n+1)^2 \Leftrightarrow  n^2-2n+1 > 0$ (đúng với $n > 5$).
    • Do đó $2^{n+1} > (n+1)^2$.
  • Vậy $2^n > n^2$ với mọi $n \geq 5$.

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

Bài 1. Chứng minh các đẳng thức sau:

a) $1^2 + 2^2 + …+ n^2 = \dfrac{n(n+1)(2n+1)}{6}.$

b) $1^3 + 2^3 + …+n^3 = \dfrac{n^2(n+1)^2}{4}$.

c) $\dfrac{1}{1.2.3} + \dfrac{1}{2.3.4} + …+ \dfrac{1}{n(n+1)(n+2)} = \dfrac{n(n+3)}{4(n+1)(n+2)}$.

Bài 2.

a) Chứng minh rằng $n! > 3^n$ với mọi $n > 7$.

b) Chứng minh rằng với số thực $a > – 1$, thì với mọi số tự nhiên $n$ ta có $(1+a)^n \geq 1+ na$.

Bài 3. Chứng minh rằng với mọi số tự nhiên $n$ thì:

a) $5^{2n+1}+2^{n+4} + 2^{n+1}$ chia hết cho 23.

b) Với $ n $ là số tự nhiên chẵn, chứng minh rằng: $$ (20^n+16^n-3^n-1)\ \vdots \ 323. $$

Phương pháp chứng minh phản chứng – P1

Leave a reply

Ta dùng tương đương logic sau $A \Rightarrow B \Leftrightarrow \overline{B} \Rightarrow \overline{A}$ để thiết lập phương pháp chứng minh Phản chứng.

Để chứng minh mệnh đề $A \Rightarrow B$ đúng, ta có thể thực hiện các bước sau (Phương pháp phản chứng)

  • Giả sử mệnh đề $B$ sai.
  • Chứng minh $A$ sai, hoặc một điều vô lý.

Ví dụ 1. (Nguyên lý Dirichlet) Có $nk + 1$ viên bi, bỏ vào trong $k$ cái hộp. Chứng minh rằng có ít nhất một hộp có ít nhất là là $n+1$ viên bi.

Lời giải

Giả sử tất cả các hộp chỉ chứa số lượng bị không vượt quá $n$ viên, khi đó tổng số viên bi không vượt quá $k \cdot n$, mâu thuẫn với số bi là $kn + 1$.
Vậy phải có một hộp chứa nhiều hơn $n$ viên bi.

Ví dụ 2. Cho $n$ là số tự nhiên $n>3$. Chứng minh rằng $2^n+1$ không chia hết cho $2^m-1$ với mọi số tự nhiên $m$ sao cho $2 < m \leq n$.

Lời giải

Giả sử tồn tại $m,n$ sao cho $2^n+1$ chia hết cho $2^m-1$ với $2 < m < n$.
Ta có $2^{n-m}(2^m-1) \vdots 2^m-1$, suy ra $2^n -2^{n-m} \vdots 2^m-1$, mà $2^n+1 \vdots 2^m-1$ suy ra $2^{n-m} +1$ chia hết cho $2^m-1$.
Lý luận tương tự ta có $2^{n-km} + 1$ chia hết cho $2^m-1$.\\ Giả sử $n = km + q, 0\leq q <m$. Chọn $k$ như trên ta có $2^q +1$ chia hết cho $2^m-1$. Mà $q < m$ nên $2^q + 1 =2^m-1$,giải ra $q = 1, m=2$ (vô lý).

Ví dụ 3. Cho tập $B = {1, 2, 3, …, 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ử có cách ghi thỏa đề bài xét hai số đứng kề số 1, gọi là $a, b$ như sau $a1b$, khi đó $a+1 \geq 17, b+1 \geq 17$, suy ra $a = b= 16$ vô lí. Do đó không có cách ghi thỏa đề bài.
b) Giả sử có cách ghi thỏa đề bài: 3 số liên tiếp bất kì có tổng lớn hơn 24. Khi đó bỏ số 16 ra, còn lại 15 số chia làm 5 nhóm rời nhau thì tổng lớn hơn $24 \times 5 = 120$, trong khi đó $1 + 2 + \cdots + 15 = 120$ vô lí.

Ví dụ 4.  Có tồn tại hay không một cách điền các số $0,1, 2, 3, \cdots , 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ó một cách ghi thỏa đề bài. Khi đó
ta thấy rằng các số $0, 1, 2, 8, 9$ không thể đứng cạnh nhau đôi một. Hơn nữa có đúng 10 số, vậy các số còn lại sẽ đứng xen kẽ giữa các số này.
Khi đó xét số 7, ta thấy số 7 chỉ có thể đứng bên cạnh số 2 trong các số $\{0, 1, 2, 8, 9\}$, mâu thuẫn.
Vậy không tồn tại cách ghi thỏa đề bài.

Ví dụ 5.  Đ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 $11n$ ô vuông $1 \times 1$, và phần còn lại chứa $110-11n$ ô vuông $1 \times 1$ , với $0 \le n \le 5.$
  • Để ý 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à dó đó 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.
  • 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,…,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, 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.

Ví dụ 6.  Cho $F ={E_1, E_2, …, E_k }$ là một họ các tập con có $r$ phần tử của tập $X$. Nếu giao của $r+1$ tập bất kì của $F$ là khác rỗng, chứng minh rằng giao của tất cả các tập thuộc $F$ là khác rỗng.

Lời giải
  • Giả sử ngược lại, giao tất cả các tập thuộc $F$ bằng rỗng.
    Xét tập $E_1 = \{x_1, \cdots, x_r\}$.
  • Do giao tất cả các tập thuộc $F$ là rỗng, nên với $x_k$ tồn tại một tập $E_{i_k}$ mà $x \notin E_{i_k}, \forall k = \overline{1,r}$.
  • Khi đó xét giao của họ gồm $r+1$ tập $E_1, E_{i_1}, \cdot, E_{i_r}$ thì bằng rỗng, mâu thuẫn.
    Vậy giao của tất cả các tập thuộc $F$ là khác rỗng.

Ví dụ 7.  Cho $A$ và $B$ là các tập phân biệt và hợp của $A$ và $B$ là tập các số tự nhiên. Chứng minh rằng với mọi số tự nhiên $n$ tồn tại các số phân biệt $a,b > n$ sao cho ${a,b,a + b } \subset A$ hoặc ${a,b,a+b} \subset B$.

Lời giải
  • Nếu $A$ hoặc $B$ là tập hợp hữu hạn phần tử thì chỉ cần chọn $a, b$ lớn hơn phần tử lớn nhất của $A$ hoặc $B$ ta có điều cần chứng minh.
  • Nếu $A, B$ là tập vô hạn, giả sử tồn tại $n$ sao cho với mọi $a, b$ thì $a, b, a+b$ không cùng thuộc $A$ hoặc $B$. (1)
  • Ta chọn các số $x, y, z \in A$ sao cho $x < y < z$ và $z-y, y-x > n$.
  • Do (1) nên các số $y-x, z-y,z-x \in B$, suy ra $z-y+y-x = z-x \in A$ (mâu thuẫn).
    Vậy điều giả sử là sai, tức là ta có điều cần chứng minh.

Ví dụ 8.  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ỷ.
  • Mặt khác diện tích tam giác đều $S = \dfrac{a^2\sqrt{3}}{4}$ là số vô tỷ, vì $a$ là số nguyên, $\sqrt{3}$ là số vô tỷ.

Ví dụ 9.  Cho $A$ là tập con có 19 phần tử của tập ${1, 2, \cdots, 106}$ sao cho không có hai phần tử nào có hiệu bằng $6, 9, 12, 15, 18$. Chứng minh rằng có 2 phần tử thuộc $A$ có hiệu bằng 3.

Lời giải
  • Xét các phần tử thuộc $A$ theo mod 3 thì có ít nhất 7 phần tử có cùng 0, 1, 2 mod 3. Xét tập B có 7 hoặc nhiều hơn phần tử có cùng số dư khi chia cho 3. Khi đó hiệu 2 số bất kì là số chia hết cho 3.
  • Giả sử không có hai số có hiệu bằng 3, khi đó hiệu hai số sẽ từ 21 trở đi. Giả sử $a_1 < a_2 < a_3 < a_4 < a_5 < a_6 < a_7 \in B$. Ta có $a_2 – a_1 \geq 21, \cdots, a_7 – a_6 \geq 21$, suy ra $a_7 \geq 1 + 21\times 6 = 127$ mâu thuẫn.
  • Vậy có 2 số có hiệu bằng 3.

Ví dụ 10. Một hình vuông $n \times n$ ô được tô bởi hai màu đen trắng, sao cho trong 4 ô góc thì 3 ô được tô màu đen, 1 ô được tô màu trắng. Chứng minh rằng trong hình vuông có ô vuông $2 \times 2 $ mà có số ô màu đen là số lẻ.

Lời giải
  • Giả sử ngược lại, không có hình vuông $2 \times 2$ nào mà số ô đen là lẻ mà đều là số chẵn.
  • Lấy tổng các ô đen của các hình vuông $2\times 2$, khi đó ta được một số chẵn các ô đen.
  • Mặt khác, mỗi ô vuông trên cạnh (khác ô góc) được tính 2 lần (vì có 2 hình vuông $2 \times 2$ chứa nó, các ô vuông bên trong được tính 4 lần, các ô góc được tính 1 lần, do đó số ô đen là một số lẻ. Mâu thuẫn.
  • Vậy có ít nhất một hình vuông $2 \times 2$ ô đen là một số lẻ.

 

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

Bài 1. Giải các bài toán sau bằng phương pháp phản chứng
a) Chứng minh rằng $\sqrt{2}$ là một số vô tỷ.
b) Chứng minh rằng tổng của một số hữu tỷ và một số vô tỷ là số vô tỷ.
c) Chứng minh tích của một số hữu tỷ và một số vô tỷ là số vô tỷ.
d) Tổng, tích hai số vô tỷ có luôn là số vô tỷ không? Tại sao?
e) Cho 15 số thỏa mãn tổng của 8 số bất kì lớn nhơn tổng của 7 số còn lại. Chứng minh tất cả các số đã cho đều dương.
f) Từ 8 số nguyên dương không lớn hơn 20, chứng minh rằng có thể chọn ra 3 số $x, y, z$ là độ dài 3 cạnh của một tam giác.

Bài 2. Có thể chia tập $X = {1, 2, …, 17}$ thành hai tập rời nhau sao cho tích các phần tử thuộc tập này bằng tổng các phần tử thuộc tập kia?
Bài 3. Có tồn tại hay không cách chia tập hợp $X = {1, 2, …, 2017}$ thành các tập hợp sao cho trong mỗi tập đó thì phần tử lớn nhất bằng tổng các phần tử còn lại.

Bài 4. Một tập hợp có ít nhất 3 số nguyên dương phân biệt được gọi là \textbf{tập đều} nếu có ít nhất một số lẻ và khi bỏ đi một phần tử bất kì thì các số còn lại có thể chia thành hai tập hợp mà tổng các số trong hai tập hợp đó bằng nhau.
a) Chứng minh không có tập đều nào có 3 phần tử.
b) Chứng minh số phần tử của tập đều luôn là một số lẻ.
c) Có tồn tại hay không một tập đều có 5 phần tử? Tại sao?

Phương pháp chứng minh phản chứng (Lớp 10)

Leave a reply

Tính chất.  $A \Rightarrow B \Leftrightarrow \overline{B} \Rightarrow \overline{A}$ hoặc $A \Rightarrow B \Leftrightarrow \overline{B} \Rightarrow S$,  $S$ là mệnh đề hằng sai.

  • Phương pháp chứng minh phản chứng là một phương pháp chứng minh gián tiếp, để chứng  minh mệnh đề $A \Rightarrow B$ ta chứng minh mệnh đề tương đương với nó là $\overline{B} \Rightarrow \overline{A}$.
  • Điểm mạnh của phương pháp này là ta đã tạo thêm được giả thiết mới $\overline{B}$, để từ đó giúp ta suy luận tiếp để giải quyết được bài toán.
  • Tất nhiên việc viết lại mệnh đề $\overline{B}$ một cách chính xác là điều quan trọng, cái này chú ý một số quy tắt về mệnh đề.
  • Phương pháp này được sử dụng hầu hết trong các phân môn của toán là: đại số, số học, hình học, tổ hợp.

1. Các bài toán tổ hợp

Ví dụ 1. (Nguyên lý Dirichlet) Có $nk + 1$ viên bi, bỏ vào trong $k$ cái hộp. Chứng minh rằng có ít nhất một hộp có ít nhất là là $n+1$ viên bi.

Lời giải
  •  Giả sử tất cả các hộp chỉ chứa số lượng bị không vượt quá $n$ viên, khi đó tổng số viên bi không vượt quá $k \cdot n$, mâu thuẫn với số bi là $kn + 1$.
  • Vậy phải có một hộp chứa nhiều hơn $n$ viên bi.

 

Ví dụ 2. Có tồn tại hay không một cách điền các số $0,1, 2, 3, \cdots , 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ó một cách ghi thỏa đề bài.
  • Khi đó ta thấy rằng các số $0, 1, 2, 8, 9$ không thể đứng cạnh nhau đôi một. Hơn nữa có đúng 10 số, vậy các số còn lại sẽ đứng xen kẽ giữa các số này.
  • Khi đó xét số 7, ta thấy số 7 chỉ có thể đứng bên cạnh số 2 trong các số $\{ 0, 1, 2, 8, 9 \}$, mâu thuẫn.
    Vậy không tồn tại cách ghi thỏa đề bài.

Ví dụ 3.  Đ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 $11n$ ô vuông $1 \times 1$, và phần còn lại chứa $110-11n$ ô vuông $1 \times 1$ , với $0 \le n \le 5.$
  • Để ý 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à dó đó 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.
  • 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,…,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, 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.

Ví dụ 4. Cho $F ={E_1, E_2, …, E_k }$ là một họ các tập con có $r$ phần tử của tập $X$. Nếu giao của $r+1$ tập bất kì của $F$ là khác rỗng, chứng minh rằng giao của tất cả các tập thuộc $F$ là khác rỗng.

Lời giải
  • Giả sử ngược lại, giao tất cả các tập thuộc $F$ bằng rỗng.
  • Xét tập $E_1 = \{x_1, \cdots, x_r\}$. Do giao tất cả các tập thuộc $F$ là rỗng, nên với $x_k$ tồn tại một tập $E_{i_k}$ mà $x \notin E_{i_k}, \forall k = \overline{1,r}$.
  • Khi đó xét giao của họ gồm $r+1$ tập $E_1, E_{i_1}, \cdot, E_{i_r}$ thì bằng rỗng, mâu thuẫn.Vậy giao của tất cả các tập thuộc $F$ là khác rỗng.

Ví dụ 5.  Cho $A$ và $B$ là các tập phân biệt và hợp của $A$ và $B$ là tập các số tự nhiên. Chứng minh rằng với mọi số tự nhiên $n$ tồn tại các số  phân biệt $a,b > n$ sao cho ${a,b,a + b } \subset A$ hoặc ${a,b,a+b} \subset B$.

Lời giải
  • Nếu $A$ hoặc $B$ là tập hợp hữu hạn phần tử thì chỉ cần chọn $a, b$ lớn hơn phần tử lớn nhất của $A$ hoặc $B$ ta có điều cần chứng minh.
  • Nếu $A, B$ là tập vô hạn, giả sử tồn tại $n$ sao cho với mọi $a, b$ thì $a, b, a+b$ không cùng thuộc $A$ hoặc $B$. (1)
  • a chọn các số $x, y, z \in A$ sao cho $x < y < z$  và $z-y, y-x > n$.
  • Do (1) nên các số $y-x, z-y,z-x \in B$, suy ra $z-y+y-x = z-x \in A$ (mâu thuẫn).
    Vậy điều giả sử là sai, tức là ta có điều cần chứng minh.

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

Bài 1. 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.

Bài 2. Cho $S$ là tập vô hạn các phần tử và $P(S)$ là họ các tập con của $S$. Chứng minh rằng không tồn tại một song ánh từ $S$ và $P(S)$.

Bài 3. Cho $A$ là tập con có 19 phần tử của tập ${1, 2, \cdots, 106}$ sao cho không có hai phần tử nào có hiệu bằng $6, 9, 12, 15, 18$. Chứng minh rằng có 2 phần tử thuộc $A$ có hiệu bằng 3.

Bài 4. Một hình vuông $n \times n$ ô được tô bởi hai màu đen trắng, sao cho trong 4 ô góc thì 3 ô được tô màu đen, 1 ô được tô màu trắng. Chứng minh rằng trong hình vuông có ô vuông $2 \times 2 $ mà có số ô màu đen là số lẻ.

Bài 5.  Tập $S$ được gọi là một tập cân nếu lấy từ $S$ ra một phần tử bất kì thì các phần tử còn lại của $S$ có thể chia ra làm hai phần có tổng bằng nhau. Tìm số phần tử nhỏ nhất của một tập cân.

(còn nữa)

PHƯƠNG PHÁP ĐẾM BẰNG HAI CÁCH – Phần 1

Leave a reply

PHƯƠNG PHÁP ĐẾM BẰNG HAI CÁCH

(Dành cho học sinh lớp 10 chuyên toán)

Lời nói đầu
Đếm bằng hai cách là một phương pháp hay gặp trong đời sống, ví dụ bài toán sau: Một công ty nhập vào 3 xe hàng $ A, B, C $ gồm hai loại hàng $ I $ và $ II $. Trong đó xe $ A $ có 3 loại $ I $ và 2 loại $ II $, xe $ B $ có 4 loại $ I $ và 6 loại $ II $, xe $ C $ có 4 loại $ I $ và 6 loại $ II $. Tính số lượng hàng mà công ty nhâp vào. Đây là bài toán khá đơn giản, để giải bài toán ta có thể lập bảng và khi đó ta có thể tính bằng 2 cách như sau: Tính tổng số hàng trên mỗi xe rồi cộng lại; hoặc ta có thể tính tổng số hàng loại $ I $ trên 3 xe,tổng số hàng loại 2 trên 3 xe, rồi sau đó cộng lại.


Trên đây là một ví dụ của tính bằng hai cách, ta có thể tính tổng theo dòng hoặc có thể tính tổng theo cột. Tổng quát hơn ta có công thức đại số sau: $\sum_{i \in I,j \in J}a_{ij}=\sum_{j \in J}(\sum_{j \in J}a_{ij})=\sum_{j \in J}(\sum_{i \in J}a_{ij})$

Trong một số tình huống đề bài yêu cầu đếm số phần tử của một tập hợp mà không quan tâm ta đếm bằng cách nào, khi đó đếm bằng hai cách cho ta cùng một đáp số giống nhau, khi đó ta sẽ thiết lập được một đẳng thức tổ hợp. Một ví dụ đơn giản như đếm số tập con của tập có $ n $ phần tử, ta có thể đếm số tập có $ k $ phần tử với $ k = 0,1,…,n $, lấy tổng ta được $ C^0_n +C^1_n +….+C^n_n $. Nhưng nếu ta đếm bằng cách khác như sau: xét một tập hợp $ A $ bất kì, khi đó phần tử $ i $ có thể thuộc $ A $ hoặc $ i $ không thuộc $ A $, mỗi phần tử có 2 trường hợp, mà có $ n $ phần tử nên số tập $ A $ là $ 2^n $. Từ đó ta có đẳng thức $ C^0_n + C^1_n + …. + C^n_n = 2^n $. Đếm bằng hai cách cho ta một phương pháp để chứng minh đẳng thức liên quan tới hệ số khai triển nhị phân hay các đẳng thức tổ hợp.

Ngoài ra đếm bằng hai cách có thể áp dụng trong các bài toán bất đẳng thức, cực trị tổ hợp hay một số bài toán chứng minh sự tồn tại.

Để sử dụng phương pháp đếm bằng hai cách, đòi hỏi học sinh phải biết và vận dụng tốt các phép đếm cơ bản. Bài viết này được sử dụng để giảng dạy cho học sinh lớp 10 chuyên Toán, các em mới bước đầu làm quen với các bài toán tổ hợp nói chung và các bài toán đếm nói riêng nên ví dụ được nêu ra có độ khó không cao giúp các em làm quen với phương pháp này. Vì thời gian quá gấp rút nên không tránh khỏi sai sót, bạn đọc có thắc mắc xin liên hệ địa chỉ nguyentangvu@gmail.com,cảm ơn.

1. Chứng minh các đẳng thức tổ hợp
Ví dụ 1. Cho các số nguyên dương $ n $ và $ k $ với $ 0 < k \leq n $. Chứng minh các đẳng thức tổ hợp sau:

a) $ C_n^k=C^k_{n-1}+C^{k-1}_{n-1} $

b) $ \sum_{k \geq 0}C^{2k}_n=2^{n-1} $

Giải

a) Dễ thấy vế trái của đẳng thức là số cách chọn $ k $ phần tử từ  $ n $  phần

tử. Để chọn $ k $ phần tử từ $ n $ phần tử ta có thể làm như sau: Xét phần tử

$ a $, nếu $ a $ được chọn thì ta cần chọn thêm $ k−1 $ phần tử từ $ n−1 $

phần tử còn lại ta có $ C^{k−1}_{ n−1} $ cách. Nếu $ a $ không được chọn,

ta chọn $ k $ phần tử từ $ n−1 $ phần tử còn lại, ta có $ C^k_ {n−1} $. Do

đó số cách chọn trong hai trường hợp là $C^k_{n-1}+C^{k-1}_{n-1} $. Từ

đó ta có điều cần chứng minh.

b) Ta xét bài toán “đếm số cách chọn một số chẵn phần tử từ $ n $ phần tử”.Ta có thể đếm theo cách sau:

Cách 1: Ta có số cách chọn $ 2k $ phần tử từ $ n $ phần tử là $ C^{2k}_n $ . Khi

đó $ \sum_{k \geq 0}C^{2k}_n $ lần tổng số cách chọn một số chẵn phần tử từ

$ n $ phần tử.

Cách 2: Xét một phần tử $ a $, thì có hai khả năng $ a $ được chọn hoặc $ a $

không được chọn, ta có 2 trường hợp. Khi đó với $ n−1 $ phần tử đầu tiên, thì

số trường hợp là $ 2^{n−1} $. Tới phần tử thứ $ n $, nếu ta đã chọn được một

số chẵn phần tử thì ta không chọn, còn nếu ta đã chọn được một số lẻ phần

tử thì phần tử này sẽ được chọn, do đó số cách chọn là $ 2^{n−1} $.

Ví dụ 2. Cho các số nguyên dương $ n $ và $ k $ với $ 0 \leq k \leq n $. Chứng minh rằng:

a) $ kC^k_n=nC^{k-1}_{n-1} $

b) $ \sum_{k=0}^{n}kC^k_n=n2^{n-1} $

Giải
a) Xét bài toán “Một đội văn nghệ có n thành viên, có bao nhiêu cách chọn

$k$ người thể hiện một tiết mục hát tốp ca trong đó có một bạn hát sô lô”.

Cách 1: Chọn đội văn nghệ gồm $ k $ người từ $ n $ ta có số cách là $ C^k_n $,

từ $ k $ người này ta chọn một người hát sô lô có $ k $ cách. Khi đó số cách

chọn là $ kC^k_n $.(1)

Cách 2: Chọn người hát sô lô trước, có $ n $ cách, sau đó chọn $ k−1 $ người từ

$ n−1 $ người còn lại có $ C^{k−1}_{n−1} $ cách.

Vậy số cách chọn là $ nC^{k−1}_{n−1} $. (2)

Từ (1) và (2) ta có đẳng thức $ kC^k_n = nC^{k−1}_{n−1}. $

b) Xét bài toán “Từ $ n $ thành viên của đội văn nghệ, có bao nhiêu cách lập một nhóm hát trong đó có một nhóm trưởng?”. Làm tương tự như câu trên ta sẽ có đẳng thức cần chứng minh.

Ví dụ 3. Cho các số nguyên dương $ n $ và $ k $ với $ 0 \leq k \leq n $. Chứng minh rằng:
a) $ \sum_{m=k}^{n}C^k_m=C^{k+1}_{n+1} $

b) $ \sum_{m=k}^{n-k}C^k_mC^k_{n-m}=C^{2k+1}_{n+1} $

với $ 0 \leq k \leq\dfrac{n}{2} $.

Giải

a) Xét tập $ X = {1,2,…,n + 1} $. Khi đó ta đếm số tập con có $ k + 1 $ phần tử của $ X $.

Cách 1: Rõ ràng số tập con là $ C^{k+1}_{ n+1} $.

Cách 2: Ta chọn tập con sao cho phần tử lớn nhất là $ m $. Khi đó số tập con

có phần tử lớn nhất $ m $ là $ C^k_m $. Vì $ k \leq m \leq n $ nên ta có số tập

con là $ C^k_k + C^k_{k+1} + … + C^k_n $. Từ đó suy ra đẳng thức cần chứng

minh.

b) Xét bài toán “Đếm số tập con có $ 2k+1 $ phần tử của $ X $”.

Cách 1: Số tập con là $ C^{2k+1}_n $.

Cách 2: Ta xét phần tử thứ $ k + 1 $, giả sử đó là $ m $, khi đó ta chọn $ k $

phần tử nhỏ hơn $ m $ và $ k $ phần tử lớn hơn $ m $, số cách chọn là

$ C^k_mC^k_{n−m} $, vì $ k \leq m \leq n−k $ nên ta có số cách chọn là

$ \sum_{m=k}^{n-k} C^k_mC^k_{n-m}$.

Từ đó ta có đẳng thức cần chứng minh.

Bài tập

Bài 1 Cho $ 0 \leq k \leq m \leq n. $ Chứng minh các đẳng thức sau:

a) $ C^k_mC^m_n=C^k_nC^{m-k}_{n-k} $

b) $ \sum_{k \geq 0}k(C^k_n)^2=nC^{n-1}_{2n-1} $

c) $ \sum_{k \geq 0}C^k_nC^{m-k}_{n-k}=2^mC^m_n $

Bài 2. Chứng minh các đẳng thức sau:

a) $\sum_{i=0}^{k} C^i_n C^{k-i}_{n-i} = 2^kC^k_n$

b) $ kC^k_m C^0_p+(k-1)C^{k-1}_m C^1_p+…+C^1_mC^{k-1}_p$

$=\dfrac{m}{m+p}.k.C^k_{m+p} $

Ví dụ 4. Trong một hội nghị, mỗi thành viên tham gia đúng 3 cuộc họp và mỗi cuộc họp thì có đúng 6 thành viên tham gia. Chứng minh rằng số cuộc họp thì bằng nửa số thành viên tham gia hội nghị.

Giải
Gọi số thành viên là $ n $, số cuộc hộp là $ m $. Khi đó mỗi cuộc họp có 6 thành viên tham gia, nên tổng số lượt thành viên tham gia $ m $ cuộc họp là $ 6m $ (có lặp lại). Tương tự mỗi thành viên tham gia 3 cuộc họp mà có $ n $ thành viên nên số lượt thành viên tham gia là $ 3n $. Do đó $ 3n = 6m $ hay $ n = 2m $.
Trong bài toán trên ta có thể làm như sau: giả sử có $ m $ cuộc họp là $ 1,2,…,m $ và $ n $ thành viên là $ 1,2,3,…,n $. Xét bảng vuông $ m \times n $ gồm $ m $ dòng và $ n $ cột trên đó ghi các số dòng thứ $ i $ cột $ j $ là $ aij $ thỏa $ aij = 1 $ nếu người $ j $ tham gia cuộc họp thứ $ i $ và $ a{ij} = 0 $ trong trường hợp ngược lại. Ta được bảng sau:


Dựa vào trên, ta thấy mỗi dòng có 6 số 1 và mỗi cột có 3 số 1. Khi đó ta có $ 6m = 3n $ hay $ n = 2m $.
Bảng trên được gọi là một ma trận nhị phân, dùng để biểu diễn các mối quan hệ hai ngôi như phần tử thuộc tập hợp, quen nhau, đồ thị… và là mô hình biểu diễn rất hữu dụng trong các bài toán tổ hợp. Trong mỗi bảng nhị phân trên, nếu gọi $ r_i $ là số số 1 ở dòng thứ $ i $ và $ c_j $ là số số 1 ở cột thứ $ j $, ta có :
$ \sum_{i=1}^{m}r_i=\sum_{j=1}^{n}cj $

Ví dụ 5 (HK 1994) Trong một trường học có $ m $ giáo viên và $ n $ học sinh thỏa điều kiện sau:
i) Mỗi giáo viên dạy đúng p học sinh.
ii) Với hai học sinh phân biệt thì có đúng $ q $ giáo viên dạy họ.
Chứng minh rằng $ \dfrac{m}{q}=\dfrac{n(n-1)}{p(p-1)} $

Giải
Lập bảng gồm $ m $ dòng và $ n $ cột trong đó $ aij = 1 $ nếu giáo viên $ i $ dạy học sinh $ j $, và bằng $ 0 $ nếu ngược lại. Khi đó từ (i) thì mỗi dòng có đúng $ p $ số $ 1 $. Ta đếm các cặp số $ (1;1) $ trên cùng một dòng. Nếu đếm theo dòng thì mỗi dòng có $ C^2_p $ cặp, có $ m $ dòng nên số cặp là $ mC^2_p $. (1)
Nếu đếm theo cột, do điều kiện (ii) nên với hai cột bất kì thì có đúng $ q $ cặp. Do đó số cặp là $ qC^2_n $ (2). Từ (1) và (2) ta có $ mC^2_p=qC^2_n $ hay $ \dfrac{m}{q} =\dfrac{n(n-1)}{p(p-1)}$.

Trên đây là một kĩ thuật đếm theo cặp $ (1;1) $ cùng một dòng hoặc cùng một cột. Ta có mệnh đề sau:

Định lý 1. Nếu trong một bảng nhị phân $ m \times n, $ mỗi dòng có $ k $ số 1, hai cột bất kỳ có đúng $ p $ cặp $ (1;1) $ cùng một dòng.

Khi đó ta có $ pC^2_n=kC^2_m. $

Bài tập
Bài 1. Cho tập $ X = {1,2,…,8} $ và các tập $ A1,A2,…,A6 $ là các tập con của $ X $ sao cho mỗi tập $ Ai $ có $ 4 $ phần tử và mỗi phần tử của $ S $ thuộc $ m $ tập $ Ai $. Tìm $ m $.

Bài 2. Trong một vòng thi toán chung kết tại trường PNTK, các thí sinh phải giải 9 bài toán. Biết rằng mỗi thí sinh giải được đúng 6 bài, và với hai thí sinh bất kì thì giải đúng chung 3 bài. Tìm số thí sinh dự thi.
Bài 3. Gọi $ p(n,k) $ là số hoán vị của $ {1,2,…,n} $ có $ k $ điểm bất động. Chứng minh rằng:
$ \sum_{k=1}^{n}kp(n,k)=n! $

2. Chứng minh các bài toán bất đẳng thức và cực trị tổ hợp

Ví dụ 6. (Iran 2011) Cho $ n $ điểm trên mặt phẳng sao cho không có 3 điểm nào thẳng hàng. Chứng minh rằng số tam giác có diện tích bằng 1 có các đỉnh thuộc $ n $ điểm trên không vượt quá $ \dfrac{2}{3}(n^2-n) $.

Giải
Bài toán này ta đi tính số cặp (cạnh;tam giác). Với đoạn thẳng $ AB $, khi đó nếu điểm $ C $ thỏa $ S_{ABC} = 1 $ thì khoảng cách từ $ C $ đến $ AB $ bằng $ \dfrac{2}{AB} $ , vì không có 3 điểm nào thẳng hàng nên chỉ có nhiều nhất 4 điểm thỏa. Vậy với 1 đoạn ta sẽ có nhiều nhất 4 tam giác có diện tích 1 nhận đoạn thẳng đó làm đỉnh. Suy ra tổng số cặp nhiều nhất là $ 4C^2_n $.
Mặt khác nếu gọi số tam giác là $ m $ thì tổng số cặp là $ 3m $.
Từ đó ta có: $ 3m \leq 4C^2_n $ hay $ m \leq \dfrac{2}{3}(n^2-n) $.

Ví dụ 7.(USA TST 2005) Cho $ n > 1 $. Với số nguyên dương $ m $. Đặt $ X_m = {1,2,…,mn} $. Xét họ $ T $ gồm $ 2n $ tập hợp thỏa các điều kiện sau:
i) Mỗi phần tử của $ T$ là một tập con có $ m $ phần tử của $ X_m. $
ii) Mỗi cặp thuộc $ T $ có nhiều nhất một phần tử chung.
iii) Mỗi phần tử thuộc $ X_m $ thuộc đúng hai tập của $ T. $
Tìm giá trị lớn nhất của $ m $ theo $ n. $

Giải

Xét bảng vuông sao cho gồm $ 2n $ dòng và $ mn $ cột sao cho $ a_{ij} =1$ nếu số $ j $ thuộc $ a_i $ và bằng $ 0 $ trong trường hợp ngược lại.
Ta xét bài toán đếm số cặp $ (1;1) $ cùng một cột. Do (i) nên ta có số cặp nhiều nhất là $ C^2_{2n} $.
Do (ii) nên ta có số cặp là $ mn $.
Do đó $ mn \geq C^2_ {2n} $, suy ra $ m \geq 2n−1 $. Nếu $ m = 2n−1 $, ta xét mô hình sau. Cho $ 2n $ đường thẳng không có 3 đường nào đồng quy và không có hai đường nào song song. Khi Xm là tập các giao điểm và $ T $ là họ gồm các điểm thuộc một đường thẳng. Rõ ràng đây là mô hình thỏa đề bài. Bảng sau cho ví dụ $ n=2, m=3 $.

Ví dụ 8. (IMO 1998, P2) Trong một cuộc thi có $ a $ thí sinh và $ b $ giám khảo, với $ b $ là số lẻ lớn hơn 3. Mội giám khảo có thể đánh giá thí sinh rớt hay đậu.Giả sử với hai giám khảo bất kì thì quyết định giống nhau nhiều nhất là $ k $ thí sinh. Chứng minh rằng $ \dfrac{k}{a} \geq \dfrac{b-1}{2b} $
Giải
Cũng như ví dụ trên, ta thấy việc biểu diễn các mối quan hệ bằng bảng nhị phân rất thuận lợi trong việc trình bày lời giải. Trong bài này ta cũng có thể lập bảng $ b \times a $ theo quy tắc sau: dòng i cột j bằng 1 nếu giám khảo i cho thí sinh j đậu. Ta sẽ đếm số cặp $ (0;0) $ và $ (1;1) $ cùng một cột bằng hai cách.
Cách 1 ta đếm theo dòng: Vì với hai vị giáo bất kì có nhiều nhất $ k $ kết luận giống nhau nên với hai dòng bất kì có $ k $ cặp, do đó số cặp nhiều nhất là $ kC^2_b $.
Cách 2 ta đếm theo cột: Trong mỗi cột số cặp là $ C^2_m+C^2_n $ cặp, trong đó $ m $ là số các số $ 0 $ và $ n $ là số các số $ 1, $ ta có $ m+n=b=2t+1, $ suy ra $ n=2t+1-m. $
Khi đó $ C^2_m+C^2_n=\dfrac{m(m-1)+(21-m)(2t-m-1)}{2}=\dfrac{(2t-m)^2+m^2}{2} \geq t^2=\dfrac{(b-1)^2}{4}. $
Từ đó ta có $ kC^2_b \geq \dfrac{a(b-1)^2}{4} $, suy ra $ \dfrac{k}{a} \geq \dfrac{b-1}{2b.} $

Ví dụ 9. Cho $ n $ điểm trong mặt phẳng. Chứng minh rằng số cặp điểm có

khoảng cách bằng 1 không quá $ \dfrac{n}{4}+\dfrac{\sqrt{2n^3}}{2}. $

Giải

Gọi $ d_i $ là số đoạn thẳng có độ dài 1 mà có đỉnh là $ A_i $. Đặt khi

đó số cặp điểm là $ k = \dfrac{1}{2} (d_1 + d_2 + … + d_n) $. Ta đếm số cặp

$ (A,B) $ mà khoảng cách từ $ A,B $ đến $ A_i $ bằng 1. Số cặp là $ C^2 _{di} $,

suy ra tổng số cặp là $ \sum_{i=1}^{n}C^2_{d_i} $. Ta biết rằng hai điểm $ C,D $

thì có chung nhiều nhất một cặp $ (A,B) $ nên số cặp không vượt quá

$ 2C^2_n $. Do đó: $ \sum_{i=1}^{n}C^2_{d_i} \leq n(n-1) $

hay $ \dfrac{2k(2k-n)}{2n} \leq n(n-1) \Leftrightarrow 2k^2-nk-n^2(n-1) \leq 0 $

Do đó $ k \leq \dfrac{n}{4}+\dfrac{\sqrt{2n^3}}{2} $

3 Các bài toán tồn tại
Ví dụ 10. Cho 133 số nguyên dương, có ít nhất 799 cặp số là nguyên tố cùng nhau. Chứng minh rằng tồn tại 4 số nguyên dương phân biệt $ a,b,c,d $ sao cho $ a $ và $ b; b $ và $ c, c $ và $ d; d $ và $ a $ nguyên tố cùng nhau.

Giải

Mỗi số được đại diện bởi một điểm, hai số nào nguyên tố cùng nhau thì hai điểm tương ứng được nối nhau bởi một đoạn. Ta cần chứng minh có 4 đoạn $ AB,BC,CD,DA $. Ta cần chứng minh rằng có hai điểm $ B $ và $ D $ cùng nối với hai điểm $ A $ và $ C $.
Gọi $ d_i $ là số cạnh có đỉnh là $ A_i $. Khi đó ta có

$ d_1 + d_2 + … + d_{133} = 2 \times 799 $. Nếu hai đỉnh $ Y, Z $ cùng nối với đỉnh $ X $ thì ta sẽ xem $ (Y;Z) $ là một cặp. Ta sẽ tính số cặp này. Rõ ràng, tổng số cặp là
$ \sum_{i=1}^{133} C^2_{d_i}$

$=\dfrac{1}{2}\left(\sum_{i=1}^{133}d^2_i-\sum_{i=1}^{133}d_i \right) $

Ta có

$ \sum_{i=1}^{133}d^2_i \geq \dfrac{1}{133} \left(\sum_{i=1}^{133}d_i \right)^2 $

Do đó

$ \sum_{i=1}^{133}C^2_{d_i} \geq \dfrac{1}{2}(\dfrac{1}{133}(\sum_{i=1}^{133}d_i)^2)$

$-\sum_{i=1}^{133}d_i ]>C^2_{133} $
Nhưng $ 133 $ điểm thì có $ C^2_{133} $ cặp, nên sẽ có một cặp nào đó được tính hai lần, tức là tồn tại cặp $ (A,C) $ cùng được nối với $ B$ và $ D $. Tức là ta có 4 đoạn $ AB, BC,CD,DA. $

Ví dụ 11.  Cho tập $ X $ có $ n $ phần tử, gọi $ A_1,A_2,…,A_m $ là một họ các tập con của $ X $, sao cho $ |Ai| = 3 $ và $ |A_i \cap A_j| \leq 1 $ với $ i \neq j $. Chứng minh rằng tồn tại một tập con $ A $ của $ X $ có ít nhất $ [\sqrt{2n}] $ phần tử và không chứa bất kì tập $ A_i $ nào.

Giải
 

Ta xét tập tất cả các tập con của $ X $ mà không chứa bất kỳ tập $ A_i $ nào, khi đó dễ thấy tập này là khác rỗng (xét tập có 2 phần tử là thỏa) và hữu hạn, nên tồn tại một tập $ M $ có nhiều phần tử nhất. Đặt $ |M|=k $. Khi đó, do $ M $ có số phần tử lớn nhất nên mọi tập có số phần tử lớn hơn $ M $ đều chứa một tập $ A_i. $ Xét tập $ M’=X \setminus M= \{a_1,a_2,…,a_{n-k}\} $. Khi đó $ M \cup \{a_i\} $ có $ k+1 $ phần tử, nên theo cách xác định $ M $ thì sẽ tồn tại $ A_i \subset M’,$ do $ A_i \nsubseteq M $ nên $ A_i=\{a_i,x,y\} $ trong đó $ x,y \in M. $
Hơn nữa hai tập giao nhau có không quá một phần tử nên với mỗi $ a_i $ có nhiều nhất một cặp $ (x,y) \in A_i$. Ta đếm số cặp $ (x,y) $ theo hai cách:\\
Số cặp $ (x,y) \in X $ là $ C_k^2. $
Vì $ i=1,2,…,n-k $ nên có $ n-k $ cặp. Vậy ta có:
$ n-k \leq C^2_k \Leftrightarrow k^2+k \geq 2n $
Mà $ k \leq \sqrt{k^2+k} \leq k+1, $ suy ra $ k \geq [\sqrt{2n}] $. Ta có điều cần chứng minh.

Bài tập rèn luyện
Bài 1.  Cho 7 tập $ A1,A2,…,A7 $ là các tập con của $ X = {1,2,3,4,5,6,7} $, sao cho mội cặp phần tử thuộc $ X $ thuộc đúng một tập con, và $ |Ai|\geq 3 $ với mọi $ i $. Chứng minh rằng $ |A_i \cap Aj| = 1 $ với mọi $ i,j. $

Bài 2. Cho 16 bạn học sinh làm một bài kiểm tra trắc nghiệm, trong đó mỗi câu hỏi có 4 lựa chọn. Sau bài kiểm tra, ta thấy rằng với hai học sinh bất kì có nhiều nhất một câu trả lời giống nhau. Hỏi bài kiểm tra có nhiều nhất bao nhiêu câu hỏi?

Bài 3. Một hội nghị có n thành viên tham gia, hội nghị đã tổ chứng $ n + 1 $ cuộc họp, trong đó mỗi cuộc họp có đúng 3 người và không có cuộc họp nào có thành viên giống nhau. Chứng minh rằng có hai cuộc họp mà có chung đúng một thành viên.

Bài 4.  (China 1996) Trong một hội nghị có 8 người tham gia, hội nghị tổ chức $ m $ cuộc họp, mỗi cuộc họp có đúng 4 người tham gia. Hơn nữa hai người bất kì thì cùng tham gia một số cuộc họp như nhau. Tìm giá trị nhỏ nhất của $ m $.
Bài 5.  Cho $ A1,A2,…,Ak $ là các tập con của $ S = {1,2,…,10} $ sao cho:
i) $ |A_i| = 5,i = 1,2,…,k. $
ii) $ |A_i \cap A_j| \leq 2, 1 \leq i < j \leq k. $ Tìm giá trị lớn nhất của $ k $.

Bài 6. (IMO 2001) Có 21 bạn nam và 21 bạn nữ tham dự một kì thi học sinh giỏi toán. Biết rằng:
a) Mỗi bạn giải được nhiều nhất sáu bài.
b) Mỗi cặp một nam và một nữ thì có ít nhất một bài toán được giải bởi hai người đó.
Chứng minh rằng có môt bài toán mà giải được bởi ít nhất 3 nam và 3 nữ.

Bài 7.  (USAMO 2001) Có 8 hộp, mỗi hộp chứa 6 viên bi. Mỗi viên bi được tô màu sao cho:
i) Mội hộp chứa các viên bi khác màu.
ii) Không có hai màu nào cùng xuất hiện nhiều hơn trong một hộp.
Tìm số màu ít nhất cần dùng.

Bài 8.  (IMO 1989) Cho $ n $ và $ k $ là các số nguyên dương và $ S $ là tập $ n $ điểm trong mặt phẳng sao cho:
i) Không có 3 điểm nào thẳng hàng,
ii) Với điểm $ P $ bất kì thuộc $ S $ thì có ít nhất $ k $ điểm của $ S $ cách đều $ P $.
Chứng minh rằng: $ k<\dfrac{1}{2}+\sqrt{2n} $

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

Bài 10. Trong một hội nghị có 35 người tham gia. Biết rằng có 111 cặp đôi một quen nhau. Chứng minh rằng có thể chọn ra 4 thành viên xếp ngồi vào một bàn tròn sao cho hai người ngồi gần nhau thì quen nhau.