Đếm Bằng Hai Cách Trong Các Bài Toán Tổ Hợp - Lê Phúc Lữ - 123doc

Có thể bạn quan tâm

Đếm bằng hai cách trong các bài toán Tổ hợp - Lê Phúc Lữ

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (214.66 KB, 5 trang )

(1)<div class='page_container' data-page=1>

PHẦN 5. ĐẾM BẰNG HAI CÁCH TRONG GIẢI TOÁN TỔ HỢP

Ta biết rằng nếu một đại lượng S được đếm theo hai cách thì hai kết quả thu được phải giống nhau. Ngoài ra, nếu đếm theo cách thứ nhất được S a, còn theo cách thứ hai được Sb, thì ta sẽ có ab. Từ ý tưởng cơ bản này, ta có thể giải quyết nhiều bài toán tổ hợp liên quan đến số mối liên hệ giữa hai đối tượng nào đó (chẳng hạn học sinh – giáo viên, học sinh - CLB, …), một dạng toán khá phổ biến trong tổ hợp.

Bài 5.1.(chọn đội tuyển PTNK TPHCM) Một trường phổ thông có n học sinh. Các học sinh

tham gia vào tổng cộng m câu lạc bộ A A1, 2,,Am.

a) Chứng minh rằng nếu mỗi câu lạc bộ có 4 học sinh và hai học sinh bất kỳ tham gia chung nhiều nhất một câu lạc bộ thì ( 1).

12n n

m 

b) Giả sử tồn tại k0 sao cho hai câu lạc bộ bất kỳ có chung nhau k thành viên và tồn tại một câu lạc bộ At có k thành viên. Chứng minh rằng mn.

Lời giải.

a) Gọi S là số bộ ({ , }, )A B C mà trong đó học sinh A B, cùng tham gia vào CLB C.  Cách 1. Chọn CLB trước, có m cách, chọn cặp học sinh cùng tham gia vào đó có 2

4 6

C 

cách nên S6 .m

 Cách 2. Chọn cặp học sinh trước, có 2n

C cách, chọn CLB mà hai học sinh đó cùng tham gia, có khơng q 1 cách nên 2

nSC . Từ đó suy ra 6 2 ( 1).

12n

n n

mC  m 

b) Xét CLB X nào đó có k thành viên. Xét m1 CLB cịn lại thì theo giả thiết, rõ ràng các CLB này đều có chứa k thành viên trên của CLB X. Từ đó suy ra m1 CLB cịn lại đơi một khơng có thành viên chung.

Xét nk học sinh cịn lại của trường thì rõ ràng một học sinh thuộc tối đa một CLB (trong số các CLB còn lại), suy ra số CLB cịn lại khơng vượt q nk nên suy ra m   n k 1 n.

Bài 5.2. (Lào Cai) Trên mặt phẳng cho tập A gồm n điểm phân biệt với *

n và tập B gồm 14 đường thẳng phân biệt. Biết mỗi đường thẳng của tập B đi qua đúng 14 điểm của tập A. a) Gọi tất cả các điểm của tập A là P P1, 2,,Pn. Với mỗi điểm Pi giả sử có đúng ai đường thẳng của tập B đi qua Pi. Chứng minh rằng

196n

ii

a



</div>(2)<div class='page_container' data-page=2>

a) Ta gọi S số bộ ( , )P l thỏa mãn PA và lB và l đi qua A.Đếm theo P ta có 1niiS a



. Đếm theo l ta có 2

14 196S   nên

1196niia



b) Gọi T là số bộ ( , , )P l l1 2 thỏa mãn PA và l l1, 2B và P là giao điểm của l1 và l2. Vì 2 đường thẳng có nhiều nhất một giao điểm chung. Đếm theo l l1, 2 ta có 2

14T C . Đếm theo P ta có

1 i 1 2n ni iai ia aT C 









. Ta đánh giá tiếp như sau: 22 21 11196 196.

2 2 2 2 2

n n

i i

n

i

i i i

ia aa an n        



Suy ra 2214196 196

2n  2 C nên giải ra được n102.

Nhận xét. Thực ra đoạn đánh giá 2

1niia



ở trên chưa thật sự chặt nên đánh giá n102 còn chưa chặt. Ta làm mạnh hơn BĐT này như sau:

(ai1)(ai2)0 nên 2

3 2

i i

a  a  và 2

1 1

3 2 3 196 2

n ni ii i

a a n n

 

    



. Từ đó ta có

214

3 196 2 196

105.

2 2

n

C     n

Bài 5.3. (chọn đội tuyển chuyên ĐH Vinh) Có 16 học sinh tham gia làm một bài thi trắc nghiệm.

Đề thi chung cho tất cả học sinh và có n câu hỏi, mỗi câu hỏi có 4 phương án trả lời. Sau khi thi xong, thầy giáo nhận thấy với mỗi câu hỏi, mỗi học sinh chọn đúng 1 phương án trả lời và hai học sinh bất kì có nhiều nhất 1 câu hỏi có phương án trả lời giống nhau.

a) Với n2, hãy chỉ ra một ví dụ về phương án trả lời các câu hỏi của 16 học sinh. b) Chứng minh rằng n5.

Lời giải. a) Đánh số các học sinh là 1, 2, . . ., 16 và gọi các phương án trả lời các câu hỏi là A,

</div>(3)<div class='page_container' data-page=3>

Câu 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 A B C D A A A B B B C C C D D D 2 A B C D B C D A C D A B D A B C b) Xét bảng tương tự như câu a) với n câu hỏi.

Ta đếm số lần chọn phương án trả lời câu hỏi giống nhau của các cặp học sinh, kí hiệu là N. Đếm theo cột, vì hai học sinh bất kỳ có tối đa một câu hỏi chọn chung phương án trả lời nên

N không vượt quá số cặp học sinh, hay 2

16 120.

NC 

Đếm theo hàng, xét câu hỏi 1, gọi a b c d, , , lần lượt là số học sinh trả lời phương án A B C D, , , .Khi đó a   b c d 16 và 2 2 2 2

24( a b c d).N  C C C CTheo BĐT AM-GM thì

( 1) ( 1) ( 1) ( 1) ( )

24.

2 2 2 2 8 2

a a b b c c d d a b c d a b c d

N                 

Từ các đánh giá trên, ta có ngay 24n120 hay n5, đpcm.

Bài 5.4. (Hải Phịng) Trong một phịng họp có n người. Mỗi người quen nhau hoặc không

quen nhau. Biết rằng:

 Một người quen đúng 30 người khác.

 Một cặp quen nhau thì có đúng 19 người khác quen với cả hai người đó.

 Một cặp khơng quen nhau thì có đúng 20 người khác quen với cả hai người đó. Tìm tất cả các giá trị có thể có của n.

Lời giải.

Để tìm n, ta thực hiện đếm bằng hai cách số lượng S gồm các bộ có thứ tự ( , , )A B C mà C quen cả A, B nhưng A, B lại không quen nhau.

* Cách 1.

</div>(4)<div class='page_container' data-page=4>

nên sẽ có 30 1 19  10 người quen C mà không quen A, đặt người đó là B. Suy ra S 300 .nDo đó, ta có 20 (n n31)300nn46.

Bài 5.5. (Cần Thơ) Trong một trung tâm văn hóa tỉnh, có 501 học sinh tổ chức các CLB (một

học sinh có thể tham gia nhiều CLB). Các CLB phối hợp với nhau để tổ chức các hoạt động xã hội. Biết rằng có k hoạt động xã hội thỏa mãn các điều kiện:

- Mỗi cặp học sinh thuộc đúng 1 CLB.

- Với mỗi học sinh và mỗi hoạt động xã hội, học sinh này thuộc đúng 1 CLB trong hoạt động xã hội tương ứng.

- Mỗi CLB có một số lẻ thành viên và nếu số thành viên là 2m1 thì số hoạt động xã hội là m.Tính tất cả các giá trị có thể có của k.

Lời giải. Trước hết, ta đếm số bộ S có dạng ( , , )A B C với A tham gia vào CLB B nằm trong

hoạt động xã hội C.

- Đếm theo hoạt động xã hội và học sinh, ta có S501k.

- Đếm theo CLB và hoạt động xã hội. Gọi t là số CLB và a a1, 2,...,at là số thành viên của từng CLB đó. Ta biết rằng CLB có ai thành viên thì thuộc về đúng

ia

hoạt động xã hội. Thêm nữa, theo điều kiện thứ 2 thì ta có

( 1)2





ti ii

a a

S .

Do đó, ta có đẳng thức

( 1)501

2t

i ii

a ak









Ta xét thêm một bước đếm bằng hai cách nữa với số bộ T có dạng ( , , )D E F mà học sinh ,

D E thuộc về CLB F.

- Đếm theo CLB, ta có 21

.it

ai

T C





- Đếm theo học sinh, ta có 2

501.T C

Do đó 1

501.

2 2

tii

a

         

</div>(5)<div class='page_container' data-page=5>

501501

2k  

 

hay k 250.

Bài 5.6. (Bến Tre) Sắp xếp 1650 học sinh (cả nam và nữ) thành 22 hàng ngang và 75 hàng

dọc. Biết rằng với hai hàng dọc bất kì, số lần xảy ra hai học sinh trong cùng hàng ngang có cùng giới tính không vượt quá 11. Chứng minh rằng số học sinh nam không vượt quá 928.

Lời giải.

Gọi R R1, 2,,R75 là tập hợp các học sinh theo các hàng và C C1, 2,,C22 là tập hợp học sinh theo các cột. Theo giả thiết thì CiCj 11, i j.

Do đó, 2

11 11 75 37.i j

i j

T C C C







     

Ta sẽ tính T theo cách khác. Trên hàng thứ k gọi x yk, k lần lượt là số nam, nữ thì số cặp học sinh cùng giới tính trên mỗi hàng sẽ là





2 2 2 2

22 22 22 22

2 2 2

1 1 1 1

( ) (75 ) 75

( 75 75 37)

2 2

k k

k k k k k k

x y k k

k k k k

x y x y x x

T C C x x

   

     





 











   .

Gọi a là tổng số nam thì 22

1kk

a x





và từ đánh giá a928 của đề bài, ta ước lượng rằng {42, 43}

k

x  nên (xk42)(xk43)0,xk nên 2

85 42 43k k

x  x   . Suy ra 22

(10 k 75 37 42 43) 10 22 75 37 22 43 42.k

T x a







          

Vậy nên 10a22 43 42 11 75 37     a920. Ta được đánh giá chặt hơn kết quả của đề.

Nhận xét. Bài toán này rất thú vị liên quan đến kỹ thuật đếm bằng hai cách, tuy nhiên trong

điều kiện khơng dùng máy tính, nên đưa các số nhỏ hơn để dễ xử lý. Nếu ta thay ước lượng trên thành (xk41)(xk 42)0 thì có a919.

Một bài toán khác cũng từ kỳ thi chọn đội tuyển Bến Tre.

Bài 5.7. (Bến Tre) Cho n k, là các số nguyên dương. Xét S là tập hợp n điểm trên mặt phẳng

sao cho 3 điểm bất kỳ không thẳng hàng và mỗi điểm P tùy ý thì có ít nhất k điểm phân biệt cách P một khoảng bằng nhau. Chứng minh rằng 1 2

2 

k n.

Gợi ý. Ta đếm số bộ ({ , }, )A B C trong đó CACB. Chú ý rằng từ giả thiết, ta thấy rằng ứng

với một C, có ít nhất 2k

</div>

Từ khóa » Nguyên Lý đếm Bằng Hai Cách

Đếm Bằng Hai Cách Trong Các Bài Toán Tổ Hợp - Lê Phúc Lữ - 123doc

<sub></sub>



<sub></sub>

<sub></sub>













<sub></sub>

<sub></sub>

<sub></sub>

<sub></sub>





<sub></sub>

<sub></sub>

<sub></sub>

<sub></sub>

<sub></sub>

<sub></sub>

PHƯƠNG PHÁP ĐẾM BẰNG HAI CÁCH – Phần 1 - Toán Việt

Đếm Bằng Hai Cách Trong Các Bài Toán Tổ Hợp - Lê Phúc Lữ

Đếm Bằng 2 Cách - Trường THPT Chuyên Lào Cai

Giải Toán Tổ Hợp Bằng Phương Pháp 'đếm Bằng Hai Cách'

BD HSG - PM Tổ Hợp - Bài 11: Đếm Bằng Hai Cách Cơ Bản - YouTube

Bài: Đếm Bằng Hai Cách Cơ Bản

Chuyên Đề Đếm Bằng Hai Cách - Huy | PDF - Scribd

Kỹ Thuật đếm Bằng Hai Cách Chứng Minh đẳng Thức Tổ Hợp - 123doc

Chu De 1 - Dem Bang Hai Cach

() - Đếm Bằng Hai Cách Trong Giải Toán Tổ Hợp

Các Phương Pháp đếm Nâng Cao - SlideShare

TOÁN RỜI RẠC - CHƯƠNG II BÀI TOÁN ĐẾM

[PDF] PHƯƠNG PHÁP XÂY DỰNG CẤU HÌNH TRONG GIẢI TOÁN TỔ HỢP

Liên Hệ