MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN TỔ HỢP THCS
Trong chương trình Toán THCS chúng ta đã không còn xa lạ với các bài toán bất đẳng thức,phương trình nghiệm nguyên,phương trình vô tỉ…. rất hay và khó.Tuy vậy đa số chúng ta lại quên mất một dạng toán có tính thực tiễn hơn cả-Toán Tổ Hợp.Có thể nói trong đề thi chuyên Toán tại các trường THPT chuyên hiện nay,Toán Tổ Hợp đang xuất hiện với tần suất lớn.Do đó mình lập topic này không có ý gì khác ngoài giúp mình và các bạn bước đầu…biết làm Toán Tổ Hợp.
Bạn đang xem: MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN TỔ HỢP THCS
Chúng ta bắt đầu vào vấn đề chính
1)Phương pháp phản chứng
a)Lý thuyết:
1.(Phủ định kết luận)Giả sử có điều trái với kết luận của bài toán.
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 $Ageq B$ bằng phương pháp phản chứng,ta được sử dụng giả thiết phản chứng $A<B$ để chỉ ra điều vô lí.
b)Ví dụ:
Cho số nguyên dương $n>1$ 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(tepsilon 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}+1vdots (a+1)$
Mà $1< a+1< a^{t}+1Rightarrow$ $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 0Rightarrow a_{1}+a_{2}+…+a_{n-2}> a_{n}-a_{n-1}geq 0$
Xem thêm : Phương pháp giâm cành đơn giản tại nhà
$rightarrow a_{n-2}> 0rightarrow 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.
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 ]=Nrightarrow$ 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 $mgeq 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 $mleft [ 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}$$(1leq ileq jleq 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
Xem thêm : Phương pháp tính giá thành sản phẩm theo phương pháp tỷ lệ
+ 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 930 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 609 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$
- Nếu $AB,AC,AD$ cùng màu đỏ mà $Delta DBC$ có một cạnh màu đỏ giả sử là $BC$.Khi đó $Delta ABC$ có các cạnh tô đỏ
- Nếu $AB,AC,AD$ cùng màu xanh thì rõ ràng $BC,BD,DC$ đỏ tức là ta có $Delta DBC$ có các cạnh tô đỏ
Vậy tồn tại một tam giác mà mọi cạnh của nó đều tô đỏ.Ta có đpcm
Mình sẽ post những bài đơn giản trước rồi các bài khác sẽ tính sau
Bài 1.Độ dài 3 cạnh của tam giác $ABC$ là 3 số nguyên tố.Chứng minh rằng diện tích của tam giác $ABC$ không thể là số nguyên
Bài 2.Cho các số nguyên $a,b,c$ thoả mãn $a^{2}+b^{2}=c^{2}$.Chứng minh rằng $abc$ chia hết cho $6$
Bài viết đã được chỉnh sửa nội dung bởi votruc: 17-08-2015 – 14:28
Nguồn: https://ppe.edu.vn
Danh mục: Tips
