Tag Archives: cucbien

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

Leave a reply

(Bài viết dành cho các em học sinh lớp 8, 9, 10)

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.

Nhận xét. Đây là một bài toán cực trị dạng tìm số nhỏ nhất, lớn nhất của n để thỏa điều kiện nào đó. Những kiểu bài tập này thường ta cứ xét các trường hợp nhỏ và cố gắng xây dựng cấu hình thỏa, đối với bài này cấu hình rất dễ tìm, với trường hợp $ n = 5$, để chứng minh không tồn tại, ta sử dụng cực biên, kết hợp với phản chứng để cho lời giải trọn vẹn, chọn độ dài lớn nhất giúp mình gôm hết các điểm vào thành một đường tròn, từ đó giúp giải được bài toá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. Đồng xu càng to thì nhiều đồng xu có thể tiếp xúc với nó, còn ngược lại thì càng nhỏ, do đó để càng ít đường tròn tiếp xúc nó, ta chọn đồng xu nhỏ nhất.

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.

Việc chọn phần tử lớn nhất, nhỏ nhất thể hiện ưu thế của của các phần tử đó so với các đối tượng khác, đó chưa chắc là cái thỏa, nhưng cũng cũng có ưu thế hơn, giống khi xét tuyển, các thí sinh có điểm trung bình cao chưa chắc là giỏi nhất, nhưng là những người có ưu thế hơn điểm thấp, khi chọn trong nhóm đó sẽ tìm được nhiều người giỏi hơn là chọn trong nhóm thấp điểm, do đó vượt trội một khía cạnh nào tính ra là một lợi thế để so sánh.

Ta tiếp tục với việc chứng minh các bài toán về tồn tại các đối tượng thỏa yêu cầu nào đó.

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

Ví dụ 7. 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$.

Bài tập Bài tập nguyên lý cực biên

Tài liệu tham khảo. 

  1. Problems – Solving Stretagies – Arthur Hegel
  2. Giải bài toàn bằng đại lượng cực biên – Nguyễn Hữu Điển

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

Leave a reply

(Bài viết dành cho học sinh lớp 8,9 và đầu lớp 10)

Có một câu chuyện thú vị thường thấy là trong lớp học những người nào ngồi bàn đầu hay bàn cuối thì thường hay bị gọi lên bảng trả bài hơn là những người khác, vì sao như vậy? Thực sự vì hai vị trí đó là vị trí đầu và cuối, tức là vị trí biên, vị trí “đặc biệt” hơn các vị trí khác, nên dễ được chú ý hơn.

Hoặc có một bài toán đơn giản sau: Tam giác $ABC$, $M$ thuộc cạnh $BC$, với vị trí nào của $M$ thì $AM$ đạt giá trị lớn nhất? (nhỏ nhất?). Dễ nhận ra rằng $AM \leq AB$ hoặc $AM \leq AC$, do đó $AM$ lớn nhất chỉ khi $M$ là một trong hai vị trí $B$ hoặc $C$, đó chính là vị trí biên của đoạn thẳng.

Do đó các vị trí biên của một tập hợp $X$ nào đó luôn có những đặc điểm mà vị trí khác không có được, kiểu nếu lệch ra một tí thì “bay màu” khỏi $X$.

Nguyên lý cực biên cũng như nguyên lý quy nạp, đó là một trong các nguyên lý quan trọng để chứng minh các định lý hay các bài toán. Xuất phát tự quan hệ thứ tự trong tập các số thực, và tiên đề xây dựng số tự nhiên, ta có các tính chất sau

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

Nguyên lý cực biên xuất hiện nhiều trong các chứng minh, trong bài viết nhỏ này tôi chỉ giới thiệu một số bài toán cơ bản thường gặp để giúp các em học sinh nắm được kĩ thuật chứng minh này, từ đó vận dụng để làm các bài toán khó hơn.

Việc sử dụng nguyên lí cực hạn có cái quan trọng nhất là mình sử dụng đặc điểm đặc biệt của đại lượng cực biên, xem như một giả thiết mới để khai thác, kết hợp với các kĩ thuật sắp xếp, phản chứng để giải quyết bài toán.

Ta xét vài ví dụ sau

Bài 1. Cho số thực $x$ chứng minh rằng tồn tại duy nhất số nguyên $n$ sao cho $n\leq x < n+1$. ($n$ được gọi là phần nguyên của $x$, kí hiệu là $[x]$.

Lời giải. 

Nhận xét: rõ ràng $n$ là số nguyên mà nhỏ hơn và “gần” $x$ nhất, tức là nếu $n$ tăng thêm một đơn vị thì nó sẽ vượt qua $x$. Từ ý đó ta có thể giải như sau:

Đặt $A = \{n \in \mathbb{Z}, n \leq x \}$, ta thấy $A$ là tập con khác rỗng của $\mathbb{Z}$, bị chặn trên bởi $x$ nên tồn tại phần tử lớn nhất, đặt là $n_\circ$. Ta chứng minh $n_\circ \leq x < n_\circ+1$.

Rõ ràng $n_\circ \in A$ nên $n_\circ \leq x$.

Giả sử $n_\circ + 1 \leq x$ thì $n_\circ \in A$ và $n_\circ + 1  > n_\circ $ vô lí vì $n_\circ$ là phần tử lớn nhất của $A$. Do đó $n_\circ +1 > x$

Từ đó ta có $n_\circ \leq x < n_\circ + 1$.

Bước kế tiếp là chứng minh duy nhất,giả sử tồn tại $n’$ nguyên thỏa $n’\leq x < n’+1$. \

Nếu $n’ > n_\circ$ thì $n’ \geq n_\circ+1 > x$, vô lí, tương tự với $n_\circ > n’$.

Do đó $n’ = n_\circ$.

Bài 2. Cho hai số nguyên dương $a, b$. Chứng minh rằng tồn tại duy nhất cặp số $q, r$ sao cho $0 \leq r \leq b-1$ và $$a = bq + r$$

Lời giải. Do $0 \leq r \leq b-1$ nên mình thấy rằng, $q$ trong đẳng thức trên là số lớn nhất để hiệu $a-bq$ không không âm.

Đặt $A = \{a-bq \leq 0, q\in \mathbb{N} \}$.

Rõ ràng $A$ khác rỗng vì $a-b \cdot 0 > 0$, và là tập con của tập các số tự nhiên. Khi đó $A$ có phần tử nhỏ nhất, đặt là $r$, ta có $q$ để $r = a-bq$. Ta chứng minh $0 \leq r \leq b-1$.

Rõ ràng $r \in A$ nên $r \geq 0$.

Ở ý còn lại, ta giả sử $r \geq b$, khi đó $r-b = a-bq-b = a-b(q+1) \geq 0$ và $r-b < r$, do đó $r-b$ thuộc $A$ và nhỏ hơn $r$,  mâu thuẫn với $r$ là số nhỏ nhất thuộc $A$.

Giả sử tồn tại cặp $q’, r’$ thỏa đề bài. Khi đó $a = bq+r = bq’+r’$

suy ra $r-r’ = b(q’-q)$ chia hết cho $b$ mà $|r-r’| \leq b-1$, do đó $r-r’=0$, và $q-q’=0$. Ta có điều cần chứng minh.

Ví dụ 3. Cho $a, b$ là hai số nguyên dương, gọi $d$ là ước chung lớn nhất của $a$ và $b$. Chứng minh rằng tồn tại các số nguyên $x, y$ thỏa $$d = x\cdot a + y \cdot b$$

Lời giải. Ý tưởng tương tự như bài trên, xét tập các tổ hợp tuyến tính dương của $a, b$ có dạng $xa + yb$,

Đặt T = ${xa + yb| x,y \in Z, xa +yb >0}$. Rõ ràng $T$ khác rỗng và là tập con của tập các số tự nhiên nên có phần tử nhỏ nhất, đặt là $e$.
Khi đó T có phần tử nhỏ nhất, ta đặt $e = xa + yb$.
Giả sử $a = ek +r$, với $ 0 \leq r < e$ , suy ra $r = a – ek = a – (xa +yb).k = a(1 – xk) + b. yk$.

  • Nếu $r >0$ thì $r \leq e$ mâu thuẫn vì $e$ là phần tử nhỏ nhất của $T$.
  • Vậy $r =0$ suy ra $e|a$. Chứng minh tương tự ta có $e|b$ do đó $e|d$.
  • Mặt khác $d|a, d|b$ suy ra $d|(xa + yb)$ hay $d|e$. Từ đó ta có $d = e$.

Ví dụ 4. Chứng minh rằng $\sqrt{2}$ là số vô tỉ.

Lời giải. Việc chứng minh $\sqrt{2}$ là số vô tỉ có nhiều cách, nhìn chung đều sử dụng phản chứng, và tính chất số học, lần này ta trình bày với phản chứng kết hợp với đại lượng cực biên.

Giả sử $\sqrt{2}$ không là số vô tỉ, tức là $\sqrt{2} = \dfrac{a}{b}$ trong đó $a, b$ là các số nguyên dương, suy ra $b\sqrt{2} = a$ là số nguyên dương.

Đặt $A = \{n| n, n\sqrt{2} \in \mathbb{N}\}$. Rõ ràng, $A$ khác rỗng là con của tập các số nguyên dương, nên có phần tử nhỏ nhất, đặt là $k$.

Ta có $k, k\sqrt{2}$ nguyên dương, suy ra $k(\sqrt{2}-1)$ nguyên dương.

Và $k(\sqrt{2}-1)\sqrt{2} = 2k – k\sqrt{2}$ cũng nguyên dương.

Do đó $k(\sqrt{2}-1)$ thuộc $A$ và $0 < k(\sqrt{2}-1) < k$ vô lí vì $k$ là nhỏ nhất.

Ví dụ 5. Chứng minh rằng không tồn tại các số nguyên dương $x, y, z, t$ sao cho $$x^2+y^2=3(z^2+t^2)$$

Lời giải. Giả sử tồn tại bộ 3 số nguyên dương thỏa đề bài, ta chọn bộ thỏa $x^2+y^2$ nhỏ nhất. Khi đó $x^2+y^2$ chia hết cho 3, suy ra $x, y$ đều chia hết cho $3$, khi đó $x= 3x’, y=3y’$, suy ra $z^2+t^2 = 3(x’^2+y’^2)$, thì bộ $(z,t,x’,y’)$ cũng thỏa đề bài, nhưng $z^2 +t^2 < x^2+y^2$. Mâu thuẫn.

Do đó phương trình không có nghiệm trong tập các số nguyên dương.

(Hết phần 1)

Tài liệu tham khảo. 

[1] Giải toán bằng phương pháp Đại lượng cực biên – Nguyễn Hữu Điển

[2] Problems Solving Strategies –