Chuỗi bài toán về 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 (208.85 KB, 4 trang )

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

CHUỖI BÀI TOÁN VỀ TỔ HỢP

(có bài tập và gợi ý)

Bài 1.

Cho n là số nguyên dương và p q r, , là các số nguyên tố phân biệt. Tìm số các hàm số f n( )

thỏa mãn: f : 1, 2,3,..., 2



n







p q r, ,



và f(1) (2) (3)... (2 )f f f n là số chính phương. 
Gợi ý. Tích đã cho là số chính phương khi số mũ của p q r, , trong đó đều chẵn.

Hơn thế nữa, tích này là sự đóng góp của tất cả các giá trị của hàm f từ 1, 2,3,..., 2n nên nó bị

ảnh hưởng bởi số hạng cuối cùng.

Ta gọi a b c dn, n, n, n là số các hàm f : 1, 2, 3,...,



n







p q r, ,



sao cho trong tích f(1) (2)... ( )f f n ,
số mũ của p q r, , lần lượt là:

 3 chẵn.

 2 chẵn, 1 lẻ.

 1 chẵn, 2 lẻ.

 3 lẻ.

Tìm quan hệ giữa a b c dn, n, n, n, ta suy ra được công thức truy hồi của an là: an4 10an29an.

Bài 2.

1) Tìm số hốn vị ( ,a a1 2,...,a2015) của



1, 2,3,..., 2015



sao cho ai1ai 1 với i1, 2,..., 2014.

2) Bổ sung điều kiện: tồn tại duy nhất một chỉ số i mà ai i. 
Gợi ý.

1) Xây dựng cơng thức truy hồi đếm số hốn vị là sn. Xét vị trí i mà ai n thì dễ dàng chứng

minh được ai1 n 1,ai2  n 2,... dẫn đến công thức truy hồi sn  1 s1s2...sn1.
Giải ra ta được s2015 22014.

2) Trước hết, chứng minh chỉ số i thỏa mãn ai i là i1008. Từ đó suy ra số hốn vị là 22012.

Nhận xét. Rút kinh nghiệm về đếm bằng truy hồi.

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

Cho bảng ô vuông 4 4 , mỗi ô vuông con được tô bởi 1 trong 2015 màu. Tính số cách tơ màu 
thỏa mãn: khơng có bảng con 3 3 nào có tất cả các ô vuông cùng màu.

Gợi ý. Sử dụng nguyên lý bù trừ, gọi A B C D, , , là tập hợp các cách tô mà các bảng con ở góc
trên-trái, trên-phải, dưới-trái, dưới-phải được tơ cùng màu.

Ta cần đếm 201516 ABCD .

Bài 4.

Có 25 con lạc đà xếp thành một hàng ngang và con đứng đầu tên là Alice. Ông bà chủ muốn 
tặng quà cho chúng theo các cách như sau:

- Ông chủ có các quả bóng với 7 loại màu (bóng cùng màu thì giống nhau) và ơng tặng cho

các con lạc đà sao cho 2 con đứng cạnh nhau thì phải khác màu bóng và tất cả quả bóng đều 
phải được sử dụng. Gọi A là số cách tặng của ơng chủ.

- Bà chủ có các vòng đeo cổ với 7 loại màu (vòng cùng màu thì giống nhau) và bà tặng riêng 
chiếc vịng cổ màu đỏ DUY NHẤT cho Alice, các vòng còn lại tặng cho các con lạc đà sao cho 
tất cả màu đều phải được sử dụng. Gọi B là số cách tặng của bà chủ.

Giả sử số quả bóng và số vịng đeo cổ của mỗi loại màu có đầy đủ để tặng. 
Tính tỉ số A

B.

Gợi ý. Vẫn sử dụng bù trừ, ta có A7 .B

Nhận xét. Rút kinh nghiệm về đếm bằng nguyên lý bù trừ.

Bài 5.Trong mặt phẳng, cho n điểm và người ta vẽ m đường thẳng phân biệt qua các điểm 
này sao cho:

(1) Mỗi đường thẳng đi qua 4 điểm.

(2) Hai điểm tùy ý đều tồn tại một đường thẳng đi qua. 
Tính các giá trị có thể có của m n, .

Gợi ý.

Ta đếm số bộ ( , , )A B C mà điểm A B, thuộc về đường thẳng C.

Sử dụng đếm bằng 2 cách, có ( 1)

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

Cố gắng tìm thêm một quan hệ nữa: 1 4( 4)

n
m   .

Từ đây dễ dàng tìm được cặp ( , ).m n

Bài 6.Trong một trường học, có n (với n2) học sinh tham gia vào k CLB. Biết rằng: 
- Mỗi CLB có ít nhất 2 học sinh.

- Nếu 2 CLB có chung nhau ít nhất 2 thành viên thì có số lượng thành viên khác nhau. 
Chứng minh rằng k(n1)2.

Gợi ý.

Ta đếm số lượng Si gồm các bộ ( , , )A B C mà học sinh A B, tham gia vào CLB C có số lượng

thành viên là i. Gọi ki là số lượng CLB có số thành viên là i.
Đếm theo học sinh, có Si Cn21.

Đếm theo CLB, có Si k Ci i2. Suy ra

2
2 2

2
n
i i n i

i

C
k C C k

C

   .

Từ đây dễ dàng chứng minh được kk2k3...kn (n1)2.

Nhận xét. Rút kinh nghiệm về đếm bằng hai cách.

Bài 7.Trong một kỳ thi có 200 thí sinh, phải giải 6 bài thi. Mỗi bài tốn có ít nhất 120 thí sinh 
giải được. Chứng minh rằng có 2 thí sinh mà mỗi bài toán trong 6 bài đều giải được bởi 1 
trong 2 thí sinh này.

Gợi ý.

Cách 1. Dùng đếm bằng 2 cách.
Cách 2. Tham lam.

Bài 8.

1) Trong một kỳ thi có 100 thí sinh và 24 giám khảo, mỗi thí sinh thích 10 giám khảo trong số

các giám khảo này. Chứng minh rằng có thể chọn ra 7 giám khảo mà mỗi thí sinh trong 6 thí 
sinh đều thích ít nhất 1 trong 7 giám khảo này.

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

18
Gợi ý.

1) Có thể đếm bằng 2 cách.
2) Chỉ có thể dùng tham lam.

Nhận xét. Rút kinh nghiệm về thuật tốn tham lam.

Bài 9.

Một tập hợp có n1 phần tử được gọi là “đẹp” nếu như bỏ đi 1 phần tử tùy ý thì có thể chia 
các phần tử cịn lại thành 2 phần có tổng bằng nhau.

a) Chứng minh rằng n lẻ. 
b) Tìm GTNN của n.

Gợi ý.

Trước hết chứng minh rằng các phần tử của tập hợp này có cùng tính chẵn lẻ. Nếu chúng cùng
chẵn thì chia nhiều lần cho 2 để được tập hợp mới có các phần tử cùng lẻ. Từ đây dễ dàng suy ra

n lẻ.

Để tìm GTNN, ta chỉ ra rằng n3,n5 khơng thỏa. Với n7, ta có S 



1,3, 5, 7, 9,11,13



Bài 10.

Tìm tất cả các số nguyên dương k sao cho tồn tại 6 số nguyên dương đôi một khác nhau mà 
tổng của chúng chia hết cho tổng của k số tùy ý trong 6 số đó.

Gợi ý. Dễ thấy k 1,k6 thỏa mãn. Ta sẽ chứng minh k2 không thỏa bằng cách chứng

minh đại diện cho trường hợp k2.

Xét các số thỏa mãn là a1a2a3a4 a5 a6 thì phải có a5a6|a1a2a3a4. Kết quả

của phép chia này chỉ có thể là 1. Tương tự với tổng a4a6, dễ dàng chỉ ra được mâu thuẫn.

</div>