2.[Đưa đến mâu thuẫn]Từ điều giả sử trên và từ giả thuyết của bài toán, ta suy ra điều mâu thuẫn với giả thiết hay với các kiến thức đã học.
3.[Khẳng định kết luận]Vậy kết luận của bài toán là đúng
*Ưu điểm của phương pháp này là tạo thêm được giả thiết mới [giả thiết phản chứng]vào các giả thiết của bài toán.Chẳng hạn để cm $A\geq B$ bằng phương pháp phản chứng,ta được sử dụng giả thiết phản chứng $A1$ thoả mãn $2^{n}+1$ là số nguyên tố.Chứng minh rằng $n=2^{k}$với $k$ là số nguyên dương
Lời giải:
Giả sử $n$ không là 1 luỹ thừa của 2 khi đó $n$ được biểu diễn dưới dạng $n=2^{k}t[t\epsilon N*]$ với $t$ lẻ
Ta có $2^{n}+1=2^{2^{k}t}+1=[2^{2^{k}}]^{t}+1$
Đặt $a=2^{2^{k}}\Rightarrow 2^{n}+1=a^{t}+1$
Do $t$ lẻ nên $a^{t}+1\vdots [a+1]$
Mà $1< a+1< a^{t}+1\Rightarrow$ $a^{t}+1$ là hợp số [hay $2^{n}+1$ là hợp số trái với gt]
Vậy ta có đpcm
2.Sử dụng nguyên tắc cực hạn
a]Lý thuyết
*]Nguyên tắc:Trong một tập hợp hữu hạn khác rỗng các số thực luôn tồn tại một số bé nhất và một số lớn nhất.Ngoài ra còn có thể sắp xếp chúng theo một trật tự tăng dần hoặc giảm dần.
VD:Nếu $A$ là $1$ tập con khác rỗng của tập hợp số tự nhiên thì $A$ luôn có phần tử nhỏ nhất.
*]Hệ quả
+Nếu $n$ số có tổng bằng $S$ thì luôn tồn tại $1$ số lớn hơn hoặc bằng $\frac{S}{n}$ và một số bé hơn hoặc bằng $\frac{S}{n}$
+Cho $n$ đoạn thẳng trên mặt phẳng,khi đó luôn tồn tại $1$ đoạn có độ dài lớn nhất và $1$ đoạn có độ dài nhỏ nhất
b]Ví dụ:
Cho $n$ số thực $a_{1};a_{2};...;a_{n}$ có tính chất:Tổng của $n-1$ số bất kì lớn hơn số còn lại.Chứng minh rằng trong $n$ số này có ít nhất $3$ số dương
Lời giải:
Theo nguyên tắc cực hạn ta có thể giả sử $a_{1}\leq a_{2}\leq ...\leq a_{n-1}\leq a_{n}$
Ta có $a_{1}+a_{2}+...+a_{n-1}> a_{n};a_{n-1}\leq a_{n}\Rightarrow a_{n}-a_{n-1}\geq 0\Rightarrow a_{1}+a_{2}+...+a_{n-2}> a_{n}-a_{n-1}\geq 0$
$\rightarrow a_{n-2}> 0\rightarrow a_{n}\geq a_{n-1}\geq a_{n-2}> 0$
Ta có đpcm
3.Sử dụng tính chất bất biến:
a]Định nghĩa:
Một tính chất P của một vật A trong phạm trù C gọi là bất biến nếu như mọi vật đẳng cấu với nó đều có tính chất P.
Chú ý:Để giải các bài toán bằng nguyên lý bất biến thì việc quan trọng nhất chính là phát hiện ra các yếu tố bất biến, sau đó là việc sử dụng các yếu tố đó vào trong bài toán một cách thích hợp. Trong mỗi bài toán sau khi giải xong chúng tôi đều phân tích những bất biến nằm trong bài toán. Đó chính là chìa khóa để tìm lời giải cho bài toán.
b]Ví dụ:
Một bàn cờ quốc tế $8\times 8$.Hỏi rằng quân mã có thể đi nước đầu tiên từ ô dưới cùng bên trái và kết thúc ở ô trên cùng bên phải không ? Với điều kiện nó phải đi qua tất cả các ô trên bàn cờ và mỗi ô chỉ đi qua đúng một lần.
Lời giải:
Do bàn cờ có $64$ ô nên con mã sẽ phải đi $63$ nước mới có thể đến ô cuối cùng.Giả sử ô con mã đang đứng là ô màu đen thì nước tiếp theo con mã sẽ đi ô trắng và nước sau nữa sẽ đi ô đen
vì $63$ là số lẻ nên đến nước thứ $63$ nó sẽ đứng ở ô màu trắng [vô lí vì ô con mã đứng ban đầu cùng màu với ô trên cùng bên phải]Do đó quân mã không thể đi nước đầu tiên từ ô dưới cùng bên trái và kết thúc ở ô trên cùng bên phải được,ta đã có đpcm.
4.Nguyên lí Dirichlet:
a]Lý thuyết:
*]Nguyên lí Dirichlet cơ bản:
Nếu nhốt $n+1$ con thỏ vào $n$ chuồng thì bao giờ cũng có $1$ chuồng chứa ít nhất $2$ con thỏ
*]Nguyên lí Dirichlet tổng quát:
Nếu có $N$ đồ vật được đặt trong $k$ hộp thì sẽ tồn tại $1$ hộp có $\left [ \frac{N}{k} \right ]$ đồ vật.
Chứng minh:Ta sẽ cm bằng phương pháp phản chứng
Giả sử mọi hộp đều chứa ít hơn $\left [ \frac{N}{k} \right ]$ đồ vật,khi đó tổng số đồ vật là $k[\left [ \frac{N}{k} \right ]-1]< k.\left [ \frac{N}{k} \right ]=N\rightarrow$ mâu thuẫn với giả thiết là có $N$ đồ vật được sắp xếp.
*]Nguyên lí Dirichlet mở rộng:
Nếu nhốt $n$ con thỏ vào $m\geq 2$ cái chuồng thì tồn tại $1$ chuồng chứa ít nhất $\left [ \frac{n+m-1}{m} \right ]$ con thỏ
Chứng minh:Ta cũng sẽ cm bằng phản chứng
Giả sử mọi chuồng đều chứa ít hơn $\left [ \frac{n+m-1}{m} \right ]$ con thỏ thì $\left [ \frac{n+m-1}{m} \right ]=\left [ \frac{n-1}{m}+1 \right ]=\left [ \frac{n-1}{m} \right ]+1$ con thỏ trong mỗi chuồng đều bé hơn hoặc bằng $\left [ \frac{n-1}{m} \right ]$ con.Từ đó suy ra $m\left [ \frac{n-1}{m} \right ]\leq n-1$ [con] [vô lí vì có $n$ chuồng thỏ].Vậy điều giả sử là sai,ta có đpcm
*]Nguyên lí Dirichlet dạng tập hợp
Cho $A$ và $B$ là $2$ tập hợp khác rỗng có số phần tử hữu hạn,mà số lượng phần tử của $A$ lớn hơn số lượng phần tử của $B$.Nếu với $1$ quy tắc nào đó,mỗi phần tử của $A$ cho tương ứng với $1$ phần tử của $B$,thì tồn tại ít nhất $2$ phần tử khác nhau của $A$ mà chúng tương ứng với $1$ phần tử của $B$.
*]Nguyên lí Dirichlet dạng tập hợp mở rộng:
Giả sử $A;B$ là $2$ tập hợp có hữu hạn các phần tử và $S[A];S[B]$ tương ứng kí hiệu là các số lượng phần tử của $A$ và $B$.Giả sử có $1$ số tự nhiên $k$ nào đó mà $S[A]>k.S[B]$ và ta có quy tắc cho tương ứng mỗi phần tử của $A$ mà chúng tương ứng với $1$ phần tử của $B$.
Chú ý:Khi $k=1$ ta có nguyên lí Dirichlet
*]Nguyên lí Dirichlet cho diện tích
Nếu $K$ là $1$ hình phẳng còn $K_{1};K_{2};...;K_{n}$ là các hình phẳng sao cho $K_{i}\subseteq K$ với $i=\overline{1;n}$ và $S_{K}< S_{K_{1}}+S_{K_{2}}+...+S_{K_{n}}$ [kí hiệu $S$ là diện tích] thì tồn tại ít nhất $2$ hình phẳng $H_{i};H_{j}$$[1\leq i\leq j\leq n]$ sao cho $H_{i};H_{j}$ không có điểm chung.
Chú ý :Ta nói $P$ là điểm trong của tập hợp $A$ trên mặt phẳng nếu như tồn tại hình tròn tâm $P$ bán kính đủ bé sao cho hình tròn này nằm trọn trong $A$
Tương tự như nguyên lí Dirichlet cho diện tích ta cũng có các nguyên lí Dirichlet cho độ dài đoạn thẳng,thể tích các vật thể.
*]Nguyên lí Dirichlet vô hạn
Nếu chia $1$ tập hợp vô hạn các quả táo vào hữu hạn ngăn kéo thì phải có ít nhất $1$ ngăn kéo chứa vô hạn các quả táo.
b]Phương pháp ứng dụng
Nguyên lí Dirichlet tưởng chừng như đơn giản như vậy, nhưng nó là một công cụ hết sức có hiệu quả dùng để chứng mình nhiều kết quả hết sức sâu sắc của toán học. Nguyên lí Dirichlet cũng được áp dụng cho các bài toán của hình học, điều đó được thể hiện qua hệ thống bài tập sau
Để sử dụng nguyên lý Dirichlet ta phải làm xuất hiện tình huống nhốt “thỏ” vào “chuồng” và thoả mãn các điều kiện
+ Số ‘thỏ” phải hiều hơn số chuồn
+ “Thỏ” phải được nhốt hết vào các “chuồng”, nhưng không bắt buộc chuồng nào cũng phải có thỏ
Thường phương pháp Dirichlet được áp dụng kèm theo phương pháp phản chứng. Ngoài ra nó còn có thể áp dụng với các phép biến hình.
5.Sử dụng một số bổ đề hình học:
- Bổ đề về đa giác bao:Cho $n$ điểm không cùng thuộc một đường thẳng.Tồn tại một đa giác lồi $m$ cạnh $[m \leq n]$ có đỉnh là $m$ trong $n$ điểm đã cho sao cho các điểm còn lại không nằm ngoài đa giác.
- Bổ đề về góc bao:Cho $n$ điểm không cùng thuộc một đường thẳng.Tồn tại một góc bẹt có đỉnh là một trong $n$ điểm đã cho sao cho các điểm còn lại không thuộc miền ngoài góc đó.
- Bổ đề về hình bình hành phủ đa giác:Cho một đa giác lồi.Tồn tại một hình bình hành có diện tích không quá hai lần diện tích đa giác sao cho các đỉnh của đa giác nằm trong hoặc trên biên của hình bình hành
Chứng minh:
- Bổ đề về đa giác bao:VMF tổ hợp.bmp 717.7K 932 Số lần tải
Vì số điểm đã cho $n$ là hữu hạn nên tồn tại một đường tròn có bán kính đủ lớn chứa tất cả $n$ điểm.Gọi $xy$ là đường thẳng nằm ngang không giao với đường tròn.Gọi $A_{1}$ là điểm gần $xy$ nhất [nếu có nhiều điểm thì chọn $A_{1}$ là điểm cuối cùng bên phải].Qua $A_{1}$ kẻ đường thẳng $d$ song song vs $xy$
Quay đường thẳng $d$ quanh $A_{1}$ ngược chiều kim đồng hồ cho đến khi gặp một điểm đã cho,ta được đường thẳng $d_{1}$,gọi điểm vừa gặp là $A_{2}$[nếu có nhiều điểm thuộc $d_{1}$ thì chọn $A_{2}$ là điểm xa $A_{1}$ nhất]
Cũng tương tự vs cách làm trên ta được các đường thẳng $d_{2}$;$d_{3}$;... cho đến khi được đường thẳng qua $A_{1}$ gọi là $d_{m}$ ta nhận được đa giác lồi $A_{1}$$A_{2}$...$A_{m}$ thoả mãn đề bài.
Chú ý: Ta gọi đa giác lồi tạo thành theo cách trên là đa giác bao $n$ điểm đã cho
- Bổ đề về góc bao: Chứng minh tương tự như bổ đề về đa giác bao
Chú ý: Ta gọi góc tạo thành theo cách trên là góc bao $n$ điểm đã cho
- Bổ đề về hình bình hành phủ đa giác:VMF tổ.bmp 604.55K 610 Số lần tải
Gọi $a$ là đường thẳng chứa cạnh $AB$ của đa giác.Gọi $C$ là đỉnh của đa giác cách xa $AC$ nhất .Qua $C$ kẻ đường thẳng $b$ song song vs $AB$
Gọi $D,E$ là các đỉnh của đa giác cách xa $AC$ nhất về hai phía của $AC$.Qua $D$ kẻ đường thẳng $c$ song song với $AC$.Qua $E$ kẻ đường thẳng $d$ song song vs $AC$
Gọi $MNPQ$ là hình bình hành tạo bởi các đường thẳng $a,b,c,d$,các đỉnh của đa giác nằm trong hoặc trên biên của hình bình hành
Hiển nhiên $S_{ACD}+S_{ACE}\leq$ diện tích đa giác mà $S_{ACD}+S_{ACE}=\frac{1}{2}S_{MNPQ}$ nên $2S_{MNPQ}\leq$ diện tích đa giác
6.Phương pháp Graph
a]Một số khái niệm cơ bản
Định nghĩa:Một graph G là một tập hợp hữu hạn các điểm [gọi là đỉnh của graph] cùng với tập hợp các đoạn đường cong hay thẳng [gọi là các cạnh của graph] có các đầu mút tại các đỉnh của graph.
Trong Graph có
- Đỉnh:Là các cạnh $A,B,C$
- Cung:Có 2 loại cung định hướng và cung không định hướng
- Cạnh:Nối hai điểm $A$ và $B$
- Khuyên:Hai đầu mút của cạnh trùng nhau
- Hành trình [đường đi] là những dây cung liên tiếp trong đó điểm cuối của cung trước trùng với điểm đầu của cung sau.
- Bậc của đỉnh:Mỗi đỉnh của graph được gọi là đỉnh bậc $n$ nếu nó là đầu mút của $n$ cạnh
- Độ dài hành trình là tổng số các cung trong hành trình
- Hành trình sơ giản:Là hành trình không có đỉnh nào lặp lại hai lần
- Chu tuyến:là hành trình hữu hạn,trong đó đỉnh đầu tiên trùng với đỉnh cuối cùng
Các loại Graph:
- Graph không định hướng:gồm những cung không hướng
- Graph định hướng:gồm những cung định hướng
- Graph liên thông:bất kì hai đỉnh nào cũng nối được một cung
- Cây là graph liên thông nhưng không phải là
- Rưng:Là graph liên thông mà mỗi thành phần liên thông là một cây
Chú ý:
- Trong mọi graph G tổng tất cả các bậc của các đỉnh là một số chẵn,bằng hai lần tất cả các cạnh của G
- Số đỉnh bậc lẻ của mọi graph là một số chẵn
- Trong mọi graph có $n$ đỉnh $[n \geq 2]$ bao giờ cũng có ít nhất hai đỉnh có cùng bậc
- Một graph là đầy đủ khi và chỉ khi mỗi cặp đỉnh của nó được nối với một cạnh
- Graph bù của một Graph G là Graph $\overline{G}$ có cùng đỉnh với G và có các cạnh là những cạnh mà ta phải bổ sung vào G để được một graph đầy đủ
- Nếu một Graph G với $n$ đỉnh $[n>2]$ có đúng hai đỉnh cùng bậc thì G phải có đúng một đỉnh bậc $O$ hoặc đúng một đỉnh bậc $n-1$
b]Ví dụ:
Bài toán:Cho $6$ điểm trong mặt phẳng sao cho bất kì ba điểm nào cũng là đỉnh của một tam giác có các cạnh độ dài khác nhau.Chứng minh cạnh nhỏ nhất của tam giác này là cạnh lớn nhất của tam giác khác
[Vô địch Toán Ba Lan 1976]
Lời giải:
Tô các cạnh của tam giác bằng hai màu đỏ hoặc xanh với cách tô sau:Tô đỏ cạnh nhỏ nhất ,hai cạnh còn lại có thể tô màu đỏ hoặc xanh.Ta được Graph G đầy đủ có $6$ đỉnh các cạnh còn lại đều được tô xanh hoặc đỏ mà mọi tam giác đều có một cạnh đỏ.
Từ điểm $A$ trong $6$ điểm đã cho nối với $5$ đỉnh còn lại được $5$ cạnh ,trong $5$ cạnh này có ít nhất $3$ cạnh cùng màu,giả sử đó là $AB,AC,AD$