Tuyển tập một số bài toán tổ hợp ôn thi HSG Toán

Tuyển tập

một số bài toán tổ hợp

Sưu tầm và Latex

Hướng tới kỳ thi VMO 2021

Phát hành tại blog lovetoan.wordpress.com

TẠP CHÍ VÀ TƯ LIỆU TOÁN HỌC

Lời giới thiệu

Tổhợp là một vấn đềkhó của toán sơ cấp nói chung cũng như trong các kì thi toán các cấp thì chủ đềnày luôn có một chỗđứng nhất định. Các bài toán tổhợp đôi khi không cần những biến đổi toán học phức tạp mà đòi hỏi tư duy nhạy bén của người làm bài, vì vậy việc luyện tập với nhiều bài toán sẽgiúp chúng ta luyện thêm kiến thức và kĩ năng xửlý các bài toán này. Với mong muốn tạo ra một tài liệu giúp các bạn học sinh ôn luyện chủđềkhó nhằn này, fanpage đã cốgắng tổng hợp nhiều bài đã sưu tầm được thành một tuyển tập nho nhỏgiúp các bạn luyện tập chuẩn bịcho các kì thi olympic toán sắp tới mà các bạn tham dự. Tài liệu là sựkết hợp của nhiều nguồn, nhiều tài liệu khác lại nhằm mang tới cho bạn đọc những bài toán thú vịnhất. Trong này sẽkhông đềcập tới các phương pháp như: đếm bằng hai cách, truy hồi, song ánh, hàm sinh,... Các bạn có thểtìm đọc chúng ởcác tài liệu khác. Hy vọng đây sẽlà công cụđắc lực của các bạn.

Mọi ý kiến đóng góp và thắc mắc vui lòng gửi vềđịa chỉ

Tạp chí và tư liệu toán học https://www.facebook.com/OlympiadMathematical

3

Chương 1

Lý thuyết vềtổhợp.

1.1 Các quy tắc tổhợp cơ bản.

Định nghĩa 1. Tập không rỗng A là tập hữu hạn nếu tồn tại sốnguyên dương n và một song ánh f : 1, 2, ..., n →A. Trong tập đó tập A bao gồm n phần tử, và chúng ta nói rằng A là một tập hợp n. Sốsốphần tửcủa tập hợp A được đặt bằng |A|. Tập rỗng ∅hữu hạn bởi định nghĩa và |∅| = 0. Một tập hợp được gọi là vô hạn nếu nó không hữu hạn. Một tập hợp con k của A là tập con của A bao gồm k phần tử.

Quy tắc song ánh. Hai tập hợp không rỗng A và B có cùng sốsốphần tửkhi và chỉkhi nếu tồn tại một song ánh f : A →B. Mặc dù quy tắc song ánh rất là hiển nhiên nhưng chúng ta đềra nó bởi những lý do sau. Đôi khi người ta nên xác định các biến với các tính chất đưa ra và nên suy ra tập A của tất cảcác biến như vậy. Nếu B là một tập hợp với sốphần tửk và tồn tại một song ánh f : A →B thì sẽcùng có sốphần tửk. Quy tắc nhân. ĐểA và B là hai tập hợp hữu hạn và f : A →B một hàm sốnhư là đối với mỗi phần tửb ∈B tồn tại chính xác k phần tửtừtập A mà có ảnh là B. Sau đó |A| = k. |B|. Chúng ta thường sửdụng quy tắc này đểphân biệt sốphần tửcủa các kết quảđược sắp xếp và không sắp xếp khi chúng ta chọn các phần tửtừcác tập đã cho. Quy tắc cộng. Nếu A là một tập hữu hạn và A = A1 ∪A2 ∪...... ∪An và Ai ∩Aj = ∅với tất cảI khác j, và

|A| = |A1| + |A2| + ..... + |An|

Chúng ta sửdụng quy tắc cộng khi xét câu hỏi tổhợp đểđếm sốphần tửcủa tập A. Đôi khi nó rất tựnhiên và dễdàng đểphân chia tập hợp A thành các tập con.(khối) đểxác địn sốlượng phần tử trong mỗi khối và đểtính được sốphần tửthu được. Quy tắc tích số. Cho A1, A2, ....An là các tập hợp hữu hạn mà lần lượt chứa k1, k2, ...., kn phần tử và tích Cartesian A1 × A2 × .... × An là 1 tập hợp chứa k1k2.....kn phần tửđó là

|A1 × A2 × .... × An| = |A1| . |A2| ...... |An| (1)

Đặc biệt, nếu A là tập hợp chứa m phần tửthì An là tập hợp chứa mn phần tửđó là |An| = |A|n. Chứng minh. Ta sẽchứng minh đẳng thức (1) bằng quy nạp. Với n = 1 thì đẳng thức (1) trởthành |A1| = k1 và luôn đúng. Cho đẳng thức (1) đúng với tập hợp chứa n −1 phần tử. Bây giờchúng ta hãy xét tập hợp chứa n phần tửnhư là |Ai| = ki với i ∈{1, 2, 3, ..., n} và An = {x1, x2, ..., xkn}. Theo giảthiết quy nạp ta có |A1.A2.....An−1| = k1.k2....kn−1 (2)

Với i ∈{k1, k2, ....., kn}, đặt

Si = {a1, a2, ....., an, xi|a1 ∈A1, a2 ∈A2, ....., an−1 ∈An−1} (3)

5