[Toán 9] Chuyên đề nhỏ:tổ hợp;suy luận logic, nguyên lý điricle THCS

[hermes_legend]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Chuyên đề: Tổ hợp, suy luận​

Trong mỗi đề thi hsg cấp quận,huyện, cấp thành phố hay cấp tỉnh đều dễ dàng nhận thấy có bài toán về vấn đề nêu trên. Thường trong đề sẽ có 1 bài và chiếm từ 2-4 điểm (tương đối). Đã có 1 số topic về tổ hợp và 1 số bài toán rời rạc được post ra nhưng tớ mạm phép lập lại CĐ nhỏ này. Tớ học không tốt phần này lắm, mong nhận được sự ủng hộ của mọi người trên tinh thần cùng giúp nhau học tập.

Về Đirichlê thì cũng sẽ được lồng vào, topic bàn về tất cả các vấn đề liên quan đến.

Các phương pháp thường dùng (chỉ mang tính chất lý thuyết) về bài tập thì chắc phải thông minh và được làm quen nhiều.
I.Phương pháp phản chứng: cách làm phương pháp thì ai cũng đã rõ.

II.Dùng nguyên lý đi ric lê: (Cái này thì ai cũng đã được làm quen).

III.Nguyên tắc cực hạncái này mới, khái niệm về nó thì có thể search goole;
VD:TRong mặt phẳng cho n điểm ([TEX]n \geq 3[/TEX]. Biết rằng mỗi đường thẳng đi qua 2 diểm bất kì thì đi qua 1 diểm thứ 3 khác, CM: n điểm đã cho thẳng hàng,

Bài giải​

Giả sử: n điểm đã cho không thẳng hàng
Xét [TEX]A_1[/TEX] và các đường thẳng đi qua 2 điểm trong các điểm còn lại không qua [TEX]A_i [/TEX](i: 1->n)
Xét các khoảng cách từ A đến các đường thẳng đi qua 2 trong các điểm còn lại và không đi qua [TEX]A_i[/TEX]. Các khoảng cách hữu hạn nên tồn tại 1 khoảng cách nhỏ nhất từ A-> đoạn nào đó nhỏ nhất.
Giả sử kc từ A->BC nhỏ nhất. => AH min (H là hình chiếu trên BC)
Vì BC còn đi qua 1 điểm khác nữa, giả sử D. Không mất tính TQ: giả sử CD nằm cùng phía với H và C nằm giữa D,H ( chưa biết vẽ hình ntn).
Kẻ đường thẳng ÀD. CK vuông góc AD(K thuộc AD; CI vuông góc BC (I thuộc AD).
Thấy CK<CI<AH=> cK<AH=> AH chưa phải kc nhỏ nhất.
=> giả sử sai.=> n điểm thẳng hàng.

IV.Dùng quy nạp và tô màu.

Và bây giờ là bài tập:
Rất dễ nhưng là cái nên để bắt đầu:
Bài 1: Cho hình vuông và 13 đường thẳng, mỗi đường chia hv thành 2 tứ giác có S=2/3. CMR: 13 đường thẳng có 4 đường đồng quy.
Bài 2: Trên mặt phẳng có 25 điểm sao cho từ 3 điểm bất kì trong số chúng tìm được 2 điểm có khoảng cách <1. CMR: tồn tại 1 hình tròn bán kính 1 chứa không ít hơn 13 điểm.

Bài tập các bạn cứ post lên nhưng chú ý là phải cố giải được các bài và không spam quá mức.
Thanks.​

&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-&gt;-

 

[minhtuyb]

Rất mong topic phát triển, póc tem bài 2 )
Lấy điểm A bất kì trong 25 điểm đã cho là tâm, kẻ đường tròn [tex](O_1;1)[/tex]. Nếu [tex](O_1;1)[/tex] chứa 25 điểm đã cho thì ta có đ.p.c.m.
-Giả sử tồn tại điểm B không thuộc O tức AB > 1. Lấy điểm B là tâm, kẻ đường tròn [tex](O_2;1)[/tex]. Không có điểm nào nằm ngoài miền của O1 và O2 .
Thật vậy, giả sử tồn tại C nằm ngoài O1 và O2 thì ta có [tex]AB>1;BC>1;AC>1[/tex], vô lý vì trong 3 điểm A,B,C phải có 2 điểm có khoảng cách <1. Vậy 25 điểm nằm trong 2 đường tròn nên theo nguyên lý Dirichlet trong 1 đường tròn có ít nhất 13 điểm đã cho

 

[cs_dac_nhiem_vn]

Chúc topic này phát triển / tớ lột nhãn bài 1

cho hình vuông ABCD :
M thuộc AB sao cho AM=2/3 AB
N thuộc CD sao cho CN=1/3 CD
trung điểm của MN là K
bạn có thể vẽ hơn 1001 đường thẳng đi qua K chia hv thành 2 tứ giác có S=2/3
lưu ý các đườg qua K ko đc cắt BC trong giới hạn hình vuông
khi đấy nó sẽ chia hv ra làm 2 hình thang vuông có S 2/3 và 1/3
mà chỉ có điểm đồng quy là K. ở đây là K gần BC
còn 3 trường hợp tương tự vs K gần AB AD CD
vậy ta có 4 điểm đông quy
còn 13 đường thẳng ấy chỉ là số rất ít
lưu ý các đườg qua K ko đc cắt

 

[minhtuyb]

Tiếp :
Bài 3: Giả sử trong một nhóm 6 người mà mỗi cặp bất kì, hoặc là bạn của nhau, hoặc là thù của nhau. Chứng tỏ rằng trong nhóm người trên, tồn tại 3 người hoặc là bạn của nhau, hoặc là thù của nhau:
Bài 4: Trong một bảng vuông 5*5 ô vuông , người ta viết vào mỗi ô vuông một trong các số -1,1,hoặc 0.chứng minh rằng trong các tổng của 5 số theo mỗi cột , mỗi hàng hay mỗi đường chéo có ít nhất 2 tổng bằng nhau
Bài 5: Trong một lớp chuyên toán có 38 học sinh. Trong một kỳ kiểm tra chất lượng môn toán chỉ có một em đạt điểm tối đa là 10, và một em đạt điểm 4, các em khác đạt từ điểm 5 trở lên. Chứng minh rằng trong lớp ít nhất cũng có 8 em có điểm số như nhau, biết rằng điểm số các em đều là các số nguyên.

 

[hermes_legend]

Tiếp :
Bài 3: Giả sử trong một nhóm 6 người mà mỗi cặp bất kì, hoặc là bạn của nhau, hoặc là thù của nhau. Chứng tỏ rằng trong nhóm người trên, tồn tại 3 người hoặc là bạn của nhau, hoặc là thù của nhau:

Bài 3
Xét người A quan hệ với 5 người còn lại thì A là bạn hoặc thù với tối thiểu 3 bạn;
Giá sử A là bạn với B,C,D.
Nếu 2 trong 3 người B,C,D là bạn thì họ tạo với A thành 3 người là bạn của nhau.
Ngược lại, nếu cả 3 người B,C,D đôi 1 "ức chế" nhau thì họ tạo với nhau thành bộ 3 người thù địch.
=> Bài toán được CM.

Bài 5:Bỏ qua 1 em đạt 10 và 1 em đạt 4 thì còn lại 36 em.
Có 36 em mà có 5 khả năng điểm từ 5->9 nên tồn tại ít nhất (36/5)+1=8 em cùng sở hữu 1 loại điểm số.
=> đpcm
@:rửa bát xong đi học cái đã; chiều post tiếp bài nhé.@-)

 

[cs_dac_nhiem_vn]

tiếp nè!!

1) Một trường học có 1000 hs gồm 23 lớp. C/m : ít nhất 1 lớp có từ 44 hs trở lên.
2) Một lớp học có 50 hs . C/m: có ít nhất 5 hs có cùng tháng sinh giống nhau.

 

[minhtuyb]

1) Một trường học có 1000 hs gồm 23 lớp. C/m : ít nhất 1 lớp có từ 44 hs trở lên.
2) Một lớp học có 50 hs . C/m: có ít nhất 5 hs có cùng tháng sinh giống nhau.

Chậc, bài hơi dễ :
1) Có: [TEX]1000=43.23+11[/TEX] nên theo nguyên lí đi dép lê, có ít nhất một lớp có 43+1=44 hs trở lên
2) Có 50 học sinh, số tháng sinh có thể xảy ra 12 trường hợp. Vì [TEX]50=12.4+2[/TEX] nên theo nguyên lí đi dép lê, có ít nhất 5 hs có số tháng sinh giống nhau
Chém bài mình nào ;

 

[hermes_legend]

2 bài trung bình:
Bài 8) Trong 1 căn phòng có 10 người. Biết rằng giữa 3 người bất kì đều có 2 người quen nhau. CMR có thể tìm ra 4 người mà 2 người bất kì trong số đó đều quen nhau.

Bài 9: 9 nhà khoa học gặp nhau ở hội nghị quốc tế và họ nhận ra rằng giữa 3 người bất kì trong số họ có ít nhất 2 người nói cùng 1 thứ tiếng. Ngoài ra mỗi nhà klhoa học có thể nói không nhiều hơn 3 thứ tiếng.
CMR: có ít nhất 3 nhà khoa học nói cùng 1 thứ tiếng.

&gt;-&gt;-&gt;-

 

[cs_dac_nhiem_vn]

Bài 4 :giải thế này

Bài 4: Trong một bảng vuông 5*5 ô vuông , người ta viết vào mỗi ô vuông một trong các số -1,1,hoặc 0.chứng minh rằng trong các tổng của 5 số theo mỗi cột , mỗi hàng hay mỗi đường chéo có ít nhất 2 tổng bằng nhau
GIẢI
Dễ thấy:Có tất cả 12 tổng của 5 số( 5 hàng ngang + 5 hàng dọc+2 đường chéo),trong khi kết quả của tổng này chỉ có 11 kết quả( -5 ;-4 ;-3 ;-2 ;-1;0 ; 1 ;2 ;3 ;4 ;5)
( Tổng của năm ô bất kỳ trong hình vuông này cũng chỉ nằm trong 11 kết quả này)
Vậy có ít nhất một kết quả là chung của hai tổng trên

 

[cs_dac_nhiem_vn]

bài 9 nè

Giả sử 9 nhà khoa học là A, B, C, D, E, F, G, H ,I
+ Trong 3 người A,B,C có ít nhất 2 người nói chung thứ tiếng, ví dụ là A và B
+ Trong 3 người D,E,F............................................................., ví dụ là D và E
+ Trong 3 người G,A,D ........................................… .................xét 3 trường hợp :
1) G và A nói chung thứ tiếng ---> G, A, B nói chung thứ tiếng
2) G và D .................................----> G, D, E ...........
3) A và D .................................---> A, B, D, E ........
Như vậy trong mọi trường hợp , ta đều tìm được ít nhất 3 người nói chung thứ tiếng.

 

[cs_dac_nhiem_vn]

tiếp nè!!

Bài 10:Trên bàn cờ 10x10, ng` ta viết các số từ 1 đến 100. Mỗi hàng chọn ra số lớn thứ 3. Cmr tồn tại 1 hàng có tổng các số trong hàng đó < tổng các chữ số lớn T3 đc chọn

@minhtuyb:Đánh số thứ tự bài nha bạn

 

[hermes_legend]

Giả sử 9 nhà khoa học là A, B, C, D, E, F, G, H ,I
+ Trong 3 người A,B,C có ít nhất 2 người nói chung thứ tiếng, ví dụ là A và B
+ Trong 3 người D,E,F............................................................., ví dụ là D và E
+ Trong 3 người G,A,D ........................................… .................xét 3 trường hợp :
1) G và A nói chung thứ tiếng ---> G, A, B nói chung thứ tiếng
2) G và D .................................----> G, D, E ...........
3) A và D .................................---> A, B, D, E ........
Như vậy trong mọi trường hợp , ta đều tìm được ít nhất 3 người nói chung thứ tiếng.

@:chưa chính xác lắm nhưng vẫn dành tặng 1 thaks cho công sức tìm tòi lời giải.

Còn bài 8 vs bài 10 ai giải nốt đi.

Bài 11Dễ) có 10 đội bóng thi đấu với nhau; mỗi đội phải đấu 1 trận với đội khác. CMR vào bất kì lúc nào của giải cũng có 2 đội đã đấu số trận như nhau

 

[minhtuyb]

@:chưa chính xác lắm nhưng vẫn dành tặng 1 thaks cho công sức tìm tòi lời giải.

Còn bài 8 vs bài 10 ai giải nốt đi.

Bài 11Dễ) có 10 đội bóng thi đấu với nhau; mỗi đội phải đấu 1 trận với đội khác. CMR vào bất kì lúc nào của giải cũng có 2 đội đã đấu số trận như nhau

Bài 11:Rõ ràng nếu trong 10 đội bóng có 1 đội chưa đấu một trận nào thì trong các đội còn lại không có đội nào đã thi đấu 9 trận như vậy 10 đội chỉ có số trận đấu hoặc từ 0 đến 8 hoặc từ 1 đến 9. Vậy theo nguyên lý Đirichlê phải có ít nhất 2 đội có số trận đấu như nhau.

Chú ý:Các bạn cố gắng trích dẫn đề bài trước bài giải của mình để tiện theo dõi

 

[hermes_legend]

Hơi ít thành viên tham gia, toàn tự post câu hỏi thế này thì chả thu được kiến thức là mấy, mọi người tích cực ra thêm 1 số đề hay và đa dạng, cố gắng giải hết các bài ở mức trung bình và mức dễ.

Bài 12) (Đề thi thành phố)
Cho đa giác đều 91 đỉnh. Mỗi đỉnh được tô bởi màu đỏ hoặc màu xanh, CMR: luôn tìm được 3 đỉnh trong 91 đỉnh của đa giác thoả:
-3 đỉnh cùng màu và là 3 đỉnh của 1 tam giác cân có ít nhất 1 góc nhỏ hơn 60 độ.

Cố lên nào

 

[cs_dac_nhiem_vn]

Có ai giải bài 10 ko tớ giải luôn cho !!!!!!!!!!!!!!!

 

[minhtuyb]

Bài 10:Trên bàn cờ 10x10, ng` ta viết các số từ 1 đến 100. Mỗi hàng chọn ra số lớn thứ 3. Cmr tồn tại 1 hàng có tổng các số trong hàng đó < tổng các chữ số lớn T3 đc chọn

@minhtuyb:Đánh số thứ tự bài nha bạn

"Bài này phân tích ra khá là thú vị đó? dễ hay khó tùy bạn nhận xét :
-Vì chỉ có 10 hàng(ngang hay dọc cũng thế cũng làm một cách này hết) việc ta sắp xếp thế nào không quan trọng vì tính độc lâp của biến -tính ngẫu nhiên của sác xuất - nên ta gọi và lần lượt sắp xếp lại lần lượt các số hang và các hàng theo thứ tự là trong 1 hàng xn.1>xn.2>xn.3>.....>xn.10 từ lớn đến bé ; n là chỉ số hàng cũng từ 1 đến 10 .các số lớn thứ 3 là : x1.3 < x2.3 < x3.3 ;.... < x10.3
ĐẶT A=X1.3+X23+X3.3+...+X10.3
( VÌ khi đã viết xong 100 số vào các ô thì ta sắp xếp đổi chỗ các hàng các vị trí khác cho nhau thế nào theo cách của ta trừ số lớn thứ 3 thì cũng không thay đổi đến tổng: A
Bây giờ ta xét đén tổng A sẽ nhận giá trị nhỏ nhất là bao nhiêu : Amin=
vì x1.3 phải lớn hơn 7 số khác nên
- . X1.3 >;=8 . còn X2.3 phải lớn hơn X1.3 và 7 số trong hàng 2 của mình nên :
- .X2.3 >;=8+8=16 .cứ như vậy ta có các Xn.3 min lập thành một cấp số cộng mà
ta sẽ tính được Amin=8*(1+2+3+...+9+10)=440....
_ Với Amin =44o thi tông cuả 10 số hàng thư 1 max =1+2+3+4+5+6+7+8+99+100=235
Ngay tổng của 10 số hàng thứ 2 max cũng chỉ =295
Ngay tổng của 10 số hàng thứ 3 max cũng chỉ =363
Ngay tổng của 10 số hàng thứ 4 max cũng chỉ =427 vậy nhỏ hơn Amin có tới 4 hàng?
Nếu ngẫu nhiên tổng 10 số lớn thứ 3 không phải là Amin ta thấy nếu chỉ cần thay một số Xn.3 bất kỳ > Xn.3 đã chọn thì phải thế ngay chinh số Xn.3 đó vào một vị trí tương ứng- làm cho tổng của 10 số ở hàng đó giảm xuống. vậy thì chắc chắn ta luôn tìm được không ít hơn 1 hàng có tổng < tổng 10 số lớn thứ 3 đc chọn?- ĐPCM đã xong"

Cái này copy nguyên văn từ "Luong-YH answer"
Bạn cs_dac_nhiem_vn đưa ra đáp án đi để mọi người so sánh

 

[cs_dac_nhiem_vn]

Bài 13 Trong mặt phẳng cho 19 điểm phân biệt trong đó ko có 3 điểm nào thẳng hàng và nằm trong hình chữ nhật có kích thước ­­­­2.3. CMR trong 19 điểm đã cho có 3 điểm nằm trong hình tròn bán kính 3/4 và tạo thành 1 tam giác có ít nhất 1 góc ko vượt quá 45 độ.
Bài 14 Cho tam giác ABC vuông tại A nội tiếp đ­uong tròn tam O. M là một điểm tùy ý thuộc đường tròn khác A,B,C. Goi I là trung điểm của AM và H là hình chiếu cua I trên MC .Tìm vị trí của M sao cho tam giác AHC có S Max.
Bai 15 Cho 53 số nguyên dương phân biệt có tổng ko > 2004. CM rằng luôn tìm được 6 số trong 53 số đã cho thỏa mãn 6 số này chia được thành 3 cặp số mà mỗi cặp đều có tổng là 53.

 

[cs_dac_nhiem_vn]

bài 12 >>>>>>

Giả sử đó là đa giác đều 91 đỉnh là A1A2A3...A91. Chú ý 91 là số lẻ, và chỉ có 2 màu xanh hoặc đỏ nên mọi cách tô màu các đỉnh ta đều suy ra tồn tại 2 đỉnh liền kề nhau có chung một màu, không mất tổng quát ta giả sử 2 đỉnh A1 và A2 màu xanh. Nếu A3 hoặc A47 hoặc A91 là màu xanh thì ta có tam giác cân có 3 đỉnh màu xanh ngay. Nếu trái lại thì ta có ngay tam giác cân A3A47A91 có 3 đỉnh tô màu đỏ.

Như vậy ta đã chứng minh được luôn tồn tại 1 tam giác có 3 đỉnh thuộc các đỉnh của đa giác 91 cạnh và được tô bởi cùng 1 màu (để lý luận chặt chẽ hơn chúng ta cần sử dụng nguyên lý Dirichlet).

Xét đường tròn ngoại tiếp đa giác đều 91 cạnh, số đo cung bị chắn bởi 1 cạnh có số đo bằng pi/91. Bây giờ xét các cung bị chắn bởi các cạnh của đa giác thì số đo góc nội tiếp bằng 1/2 số đo cung bị chắn. Mỗi góc của tam giác cân (mà ta vừa chứng minh tồn tại ở trên) bằng bội số của pi/(2.91) nên không thể bằng pi/3 được, nghĩa là tam giác cân đó không thể là tam giác đều được.

Mà 1 tam giác không đều luôn luôn tồn tại 1 góc nhỏ hơn 60 độ . Bài toán đã giải xong

 

[hermes_legend]

Phủ đầu 4 bài cho nó ác; mọi người cứ làm dần đê
1.Tồn tại hay không 2012 điểm trên mặt phẳng sao cho bất kì 3 điểm nào trong chúng cũng là đỉnh của 1 tam giác tù. (đề vòng loại team-concet)

2.Bên trong hình vuông cạnh 100 đặt 63 đồng xu hình tròn có BK là 1. CMR có thể đặt 1 tấm bìa hình vuông cạnh 10 nằm trong hình vuông mà không chờm lên đồng xu nào.

3.1 cái bánh trưng hình vuông có kích thước 6x6. Có thể dùng 9 miếng thịt hình chữ nhật kích thước 1x4 để phủ bề mặt cái bánh hay không? (Pots được hình lên thì tốt)
@: tức là cái bánh trưng được chia thành 36 hình vuông nhỏ bằng nhau có tỉ lệ cạnh-cạnh=6x6. Miếng thịt thì tương tự.
Sửa đề cho khỏi copy đâu!!

4.(Đề thi IMO hay sao không nhớ)
Có 41 thành phố được nối với nhau bởi các đường chỉ đi được 1 chiều. Biết rằng từ mỗi TP có đúng 16 đường đến các TP khác và có đúng 16 đường đến các TP khác và có đúng 16 đường từ thành phố khác đến nó. Giữa 2 TP bất kì không có quá 1 con đường của mạng đường nói trên. CMR từ 1TP bất kì A đều có thể đi đến TP bất kì B mà chỉ đi qua nhiều nhất 2 thành phố trung gian.

OK. Các bài toán 1,2,3 đều khá thú vị, bài 4 có khó hơn. Vận dụng những gì mình có để giải quyết chúng nhé.
&gt;-

 

[minhtuyb]

Bài 1: Copy có bản quyền )

He he đề mềm hơn thật
-Vẽ nửa đường tròn đường kính AB.
-Trên nửa đường tròn đó lấy 2012 điểm [TEX]A_1,A_2,A_3,...,A_2011[/TEX]. Rõ ràng trong 2012 điểm đó không có 3 điểm nào thẳng hàng, nên với bất kì 3 điểm [TEX]A_i;A_j;A_k(i,j,k\in N*;i,j,k\leq 2011;i,j,k[/TEX]đôi một khác nhau) đều tạo thành một tam giác
-Trong tam giác [TEX]A_iA_jA_k[/TEX] chắc chắn có một góc tù (góc nội tiếp chắn cung lớn hơn nửa đường tròn)
-Vậy luôn luôn tồn tại 2012 điểm trên mặt phẳng thỏa mãn đề bài <DPCM> >->->-

Đã sửa "2011"-->"2012"