108 bài tập toán tổ hợp cho tất cả mọi người: Từ cơ bản đến nâng cao

Ghi nhớ

Thông tin tác giả & Bản quyền tài liệu

• Tác giả / Chủ biên: TS. Nguyễn Văn Lợi và Nhóm Sigma-Maths (ThS. Hoàng Văn Tựu, Ngô Thị Nhã, Lợi Center)
• Mục đích: Bồi dưỡng học sinh khá giỏi THCS & THPT, rèn luyện tư duy logic, tổ hợp và phương pháp giải toán sáng tạo.

Mục lục

1. Kiến thức căn bản
2. Các bài toán đếm (Bài 1 – 20)
3. Biểu đồ Ven - Logic (Bài 21 – 30)
4. Nguyên lý Dirichlet (Bài 31 – 40)
5. Các bài toán trên bàn cờ (Bài 41 – 50)
6. Tổ hợp - Hình học (Bài 51 – 60)
7. Trò chơi – Games (Bài 61 – 70)
8. Qui nạp (Bài 71 – 80)
9. Mini Combinatorics (Bài 81 – 108)

1. Kiến thức căn bản

1. Hoán vị không lặp

• Định nghĩa: $n$ phần tử khác nhau của một tập hợp được xếp thành hàng được gọi là hoán vị không lặp (hoán vị) của $n$ phần tử.
• Định lý: Số các hoán vị không lặp lại của $n$ phần tử ký hiệu là $P_n$:$$P_n = 1 \cdot 2 \cdot 3 \dots n = n! \quad (0! = 1)$$

2. Hoán vị lặp

• Định nghĩa: Nếu một tập gồm $n$ phần tử sao cho giữa chúng có $k_1, k_2, \dots, k_r$ ($k_1 + k_2 + \dots + k_r \le n$) nhóm các phần tử bằng nhau. Khi đó một sắp xếp $n$ phần tử này vào một hàng được gọi là hoán vị lặp của bộ $n$ phần tử này.
• Định lý: Ký hiệu số hoán vị lặp của nhóm $n$ phần tử này là $P_n(k_1, k_2, \dots, k_r)$. Khi đó:$$P_n(k_1, k_2, \dots, k_r) = \frac{n!}{k_1! \, k_2! \dots k_r!}$$

3. Chỉnh hợp không lặp

• Định nghĩa: Nếu cho trước $n$ phần tử khác nhau, từ đó chọn ra $k$ phần tử, và sắp xếp $k$ phần tử này thành hàng thì ta nhận được chỉnh hợp không lặp bậc $k$ của $n$ phần tử.
• Định lý: Ký hiệu số các chỉnh hợp không lặp bậc $k$ của $n$ phần tử là $V_n^k$ (hoặc $A_n^k$), khi đó:$$V_n^k = A_n^k = \frac{n!}{(n - k)!}$$

4. Chỉnh hợp lặp

• Định nghĩa: Nếu cho trước $n$ phần tử, từ đó chọn ra $k$ phần tử sao cho mỗi phần tử có thể chọn nhiều lần, và sắp xếp $k$ phần tử được chọn này thành hàng thì ta nhận được chỉnh hợp lặp bậc $k$ của $n$ phần tử.
• Định lý: Ký hiệu số các chỉnh hợp lặp bậc $k$ của $n$ phần tử là $W_n^k$, khi đó:$$W_n^k = n^k$$

5. Tổ hợp không lặp

• Định nghĩa: Nếu cho trước $n$ phần tử khác nhau, từ đó chọn ra $k$ phần tử sao cho mỗi phần tử chỉ được chọn một lần (không quan tâm đến thứ tự xếp hạng các phần tử), thì ta nhận được tổ hợp không lặp bậc $k$ của $n$ phần tử.
• Định lý: Ký hiệu số các tổ hợp không lặp bậc $k$ của $n$ phần tử là $C_n^k$, khi đó:$$C_n^k = \frac{n!}{k!(n - k)!}$$

6. Tổ hợp lặp

• Định nghĩa: Nếu cho trước $n$ phần tử khác nhau, từ đó chọn ra $k$ phần tử sao cho mỗi phần tử có thể được chọn nhiều lần (không quan tâm đến thứ tự xếp hạng các phần tử), thì ta nhận được tổ hợp lặp bậc $k$ của $n$ phần tử.
• Định lý: Ký hiệu số các tổ hợp lặp bậc $k$ của $n$ phần tử là $D_n^k$, khi đó:$$D_n^k = \frac{(n + k - 1)!}{k!(n - 1)!} = C_{n + k - 1}^k$$

Các nguyên lý cơ bản

Cho $X$ là một tập hữu hạn. $A, B$ là các tập con của $X$.

• Nguyên lý bù trừ: $|X \setminus A| = |X| - |A|$
• Nguyên lý cộng: Nếu $A$ và $B$ là hai tập không giao nhau ($A \cap B = \emptyset$) thì:$$|A \cup B| = |A| + |B|$$
• Nguyên lý nhân: $|A \times B| = |A| \cdot |B|$
• Nguyên lý thêm bớt:$$|A \cup B| = |A| + |B| - |A \cap B|$$

2. Các bài toán đếm

Bài 1. Từ năm chữ số 1, 2, 3, 4, 5 mỗi chữ số sử dụng một lần viết tất cả các số có 5 chữ số.

• a) Nếu để các số theo thứ tự tăng dần, thì số nào đứng thứ 100?
• b) Số 42531 đứng thứ tự bao nhiêu?
• c) Tính tổng tất cả các số này.

Bài 2. Việc nào có khả năng xảy ra lớn hơn giữa: Tung xúc xắc được số 6, hay tung hai lần liên tiếp được cùng một số?

Bài 3. 10 học sinh rút thăm để nhận 4 quyển sách, mỗi học sinh không được nhiều quá 1 quyển. Hỏi có bao nhiêu cách có thể xảy ra?

Bài 4. Có bao nhiêu số có 4 chữ số mà giữa các chữ số có chữ số 0?

Bài 5. Tôi nghĩ một số nguyên $x$ với $0 < x < 17$. Hỏi cần ít nhất bao nhiêu câu hỏi mà chỉ được phép trả lời đúng - sai để người ta xác định được tôi nghĩ đến số nào?

Bài 6. Có bao nhiêu cách điền các số $1, 2, \dots, 8$ vào giữa các dấu quan hệ:

Bài 7. Tôi nghĩ hai số giữa 1 và 10. Hỏi phải cần bao nhiêu câu hỏi (dạng đúng - sai) để bạn có thể biết hai số tôi nghĩ là gì?

Bài 8. Trên bàn cờ $8 \times 8$ có bao nhiêu hình chữ nhật?

Bài 9. Trên giá có 10 quyển sách. Có bao nhiêu cách để lấy xuống 3 quyển sách không có hai quyển nào đứng cạnh nhau?

Bài 10. Có bao nhiêu số có ba chữ số sao cho chữ số ở giữa lớn hơn chữ số đứng đầu và đứng cuối?

Bài 11. Có bao nhiêu số $abc$ (ba chữ số) sao cho $b < a + c$, $c < b + a$, $a < b + c$?

Bài 12. Có bao nhiêu cách đi lên một cầu thang 8 bậc sao cho mỗi lần chỉ được bước 1 hoặc 2 bậc?

Bài 13. Có bao nhiêu cách phủ bàn cờ $2 \times 8$ bằng các quân domino $1 \times 2$?

Bài 14. Có bao nhiêu số có 5 chữ số sao cho các chữ số cạnh nhau luôn là các số liên tiếp nhau?

Bài 15. Có bao nhiêu cách để viết số 8 thành tổng của các số nguyên dương (kể cả 1 số) nếu trật tự của các số hạng là:

• a) Tính đến
• b) Không tính đến

Bài 16. Có bao nhiêu số có 3 chữ số và tổng các chữ số bằng 8?

Bài 17. Có bao nhiêu cách đi từ $A$ đến $B$ trong các hình sau, biết rằng chỉ có thể đi từ trái sang phải và đi lên:

Bài 18. Có bao nhiêu vị trí tương đối có thể của 5 bong bóng xà phòng, biết rằng một bong bóng có thể chứa toàn phần 1 hay nhiều bong bóng khác. Các bong bóng không thể phân biệt nhau, kích thước co dãn thay đổi tùy thích, chỉ chứa hay không chứa nhau, không cắt nhau (một ví dụ cho trường hợp 3 bong bóng thì có 4 trường hợp):

Bài 19. Ta xuất phát từ điểm $(1, 4)$ trên mặt phẳng tọa độ. Mỗi bước phải tăng một số nào đó thêm ít nhất 1 đơn vị. Sau một số bước thì ta đến điểm $(5, 6)$. Có bao nhiêu cách có thể?

Bài 20. Một bài toán nhiều cách phát biểu!

• a) Có 10 điểm bất kỳ. Hỏi có nhiều nhất bao nhiêu đường thẳng đi qua ít nhất 2 điểm của tập hợp này?
• b) Mười người tham gia một giải cờ. Cứ hai người gặp nhau không quá một lần. Hỏi nhiều nhất có bao nhiêu trận đấu?
• c) Trong các số từ 1 đến 10. Có bao nhiêu cách chọn ra 2 số khác nhau?

3. Biểu đồ Ven - Logic

Bài 21.

• a) Trong một viện khoa học có 67 người. Có 35 người biết tiếng Đức, tiếng Anh có 47 người biết, trong số biết tiếng Anh có 23 người biết cả tiếng Đức. Hỏi trong viện có bao nhiêu người không biết cả tiếng Đức lẫn tiếng Anh?
• b) (Tiếp tục câu a) Giả sử rằng có 20 người biết tiếng Pháp, vừa Pháp và Anh là 12 người, vừa Đức và Pháp là 11 người, cả ba thứ tiếng có 5 người biết. Vậy có bao nhiêu người không biết ngoại ngữ nào nêu trên?

Bài 22. Trên hòn đảo Hoa quả có hai bộ lạc. Bộ lạc Quýt thì mọi người đều thích quýt còn bộ lạc kia $90\%$ không thích quýt. Biết rằng $46\%$ tổng toàn bộ dân số thích quýt. Hỏi trên đảo bộ lạc Quýt chiếm bao nhiêu $\%$?

Bài 23. Trong lớp điểm 10 về toán có 12 bạn, về văn 16 bạn, và 8 bạn không có điểm 10 nào kể cả hai môn. Hỏi lớp có bao nhiêu học sinh, nếu số bạn được 10 cả văn và toán là 6 bạn?

Bài 24. Trong một lớp học nhạc, số học sinh học violon gấp hai lần so với số học sinh học Piano. Có 5 bạn học cả hai nhạc cụ. Cả lớp có 22 học sinh, mỗi người ít nhất học một nhạc cụ. Hỏi có bao nhiêu người học Violon và bao nhiêu người học piano?

Bài 25. Một lớp có 38 học sinh. Mỗi người đều chơi một trong các môn thể thao nào đó sau đây: Điền kinh, Bóng chuyền và bơi lội. 19 người tham gia điền kinh, 21 người chơi bóng chuyền, 12 người bơi lội. Có 7 người vừa tham gia điền kinh vừa bơi lội, 6 người tham gia cả điền kinh và bóng chuyền, ba người chơi vừa bóng chuyền vừa bơi. Hỏi có bao nhiêu người tham gia cả ba môn thể thao?

Bài 26. Một hội bạn bè tổ chức 3 cuộc đi du lịch. Mỗi đợt có 15 bạn tham gia. Giữa những người đi du lịch lần đầu có 7 người tham gia lần hai và 8 người tham gia lần ba. Giữa những người tham gia đợt hai có 5 người đi tiếp đợt ba. Có 4 người tham gia cả 3 đợt. Hỏi có bao nhiêu người tham gia ít nhất một lần đi du lịch?

Bài 27. Một trường học tổ chức ba đợt đi du lịch. Đợt đầu 320 học sinh tham gia, đợt thứ hai 280 học sinh tham gia, đợt thứ ba 350 học sinh tham gia. Có 60 học sinh tham gia cả ba lần, 130 học sinh tham gia ít nhất hai lần. Hỏi có bao nhiêu học sinh tham gia ít nhất một lần?

Bài 28. Một cuộc thi chung kết giải toán có 30 học sinh tham gia. Các thí sinh phải giải 3 bài toán. Bài thứ nhất có 19 bạn, bài thứ 2 có 15 bạn, bài thứ ba có 18 bạn giải được. Bài thứ nhất và thứ hai có 7 bạn, bài thứ nhất và thứ ba có 9 bạn, bài thứ hai và thứ ba có 10 bạn giải được. Cả ba bài có 3 bạn giải được. Hỏi có bao nhiêu bạn không giải được bài nào?

Bài 29. Lớp 12D có 32 học sinh. Lớp trưởng phải làm thống kê về học ngoại ngữ của lớp. Trong bản thống kê có các câu hỏi sau:

• i. Lớp có bao nhiêu học sinh?
• ii. Bao nhiêu học sinh có bằng B về tiếng Anh?
• iii. Bao nhiêu học sinh có bằng B về tiếng Pháp?
• iv. Bao nhiêu học sinh có bằng B về tiếng Đức?
• v. Bao nhiêu học sinh có bằng B về ít nhất một trong ba ngoại ngữ trên?
• vi. Bao nhiêu học sinh có bằng B về đúng hai trong ba ngoại ngữ trên?
• vii. Bao nhiêu học sinh có bằng B về đúng một trong ba ngoại ngữ trên?
• viii. Bao nhiêu học sinh không có bằng B từ một trong ba ngoại ngữ trên?

Theo lớp trưởng Câu hỏi thứ 8 là không cần thiết.

• a) Hãy xác định các giá trị của các câu hỏi còn lại nếu biết rằng các câu trả lời lần lượt cho 6 câu hỏi đầu là: $32, 20, 15, 6, 2, 9$.
• b) Kí hiệu câu trả lời thứ $y$ là $x_y$. Hãy biểu diễn $x_7$ và $x_8$ theo giá trị của $x_1, x_2, x_3, x_4, x_5, x_6$.

Bài 30. Từ 1 đến 1200 có bao nhiêu số nguyên dương biết rằng các số đó:

• a) Không chia hết cho 2
• b) Không chia hết cho 3
• c) Không chia hết cho cả 2 và 3.

4. Nguyên lý Dirichlet

Bài 31. Có 70 viên bi, trong đó 20 đỏ, 20 xanh, 20 vàng và trong mười viên còn lại có vài viên đen, số còn lại là màu trắng. Hỏi phải lấy ra ít nhất bao nhiêu viên bi để chắc chắn trong số lấy ra có 10 viên bi cùng màu?

Bài 32. Có 80 viên bi, trong đó 35 đỏ, 25 xanh, 15 vàng, 5 đen. Phải lấy ra ít nhất bao nhiêu viên bi để chắc chắn trong đó có:

• a) Màu đỏ
• b) Đỏ hoặc đen
• c) Đỏ và đen
• d) Hai màu khác nhau
• e) Từ một màu nào đó có ít nhất 3 viên bi?

Bài 33. Có $G$ viên bi, trong đó có: $D$ viên đỏ, $X$ viên xanh, $V$ viên vàng và $B$ viên đen.

• a) Biết rằng phải lấy ra ít nhất 5 viên để chắc chắn giữa chúng có màu đỏ. Hãy xác định giá trị của $B$ và $G$ nếu biết rằng $X = 1, V = 2$ và $D = 3$.
• b) Biết rằng phải lấy ra ít nhất 10 viên để chắc chắn giữa chúng có màu đỏ và đen. Hãy xác định giá trị của $V$ và $G$ nếu biết rằng $D = 2, B = 3$ và $X = 4$.

Bài 34. Trong một thùng có 4 loại táo. Số táo mỗi loại như nhau. Tổng cộng có 100 quả. Hỏi phải lấy ra ít nhất bao nhiêu quả để trong đó có một loại nào đó có 10 quả?

Bài 35. Trong một cái hộp có các đôi tất cùng cỡ: 5 đôi màu trắng, 10 đôi đen và 15 đôi màu nâu. Hỏi phải lấy ra ít nhất bao nhiêu chiếc tất có thể có một đôi (không phân biệt trái - phải)?

Bài 36. Có đúng là nếu trong một lớp có 37 học sinh thì có 4 học sinh có ngày sinh cùng một tháng?

Bài 37. Một thành phố cần có bao nhiêu dân số để tồn tại hai người có hàm răng giống nhau? (cùng vị trí còn hay mất – mỗi người có thể có không quá 36 cái răng).

Bài 38. Tổng của 50 số nguyên dương đôi một khác nhau bằng 2496. Chứng minh rằng giữa chúng có ít nhất 2 số chẵn?

Bài 39. Chứng minh rằng giữa 7 số chính phương luôn tồn tại hai số có hiệu chia hết cho 10.

Bài 40. Có thể cho nhiều nhất bao nhiêu số nguyên dương sao cho tổng hoặc hiệu của bất kì hai số nào trong chúng đều không chia hết cho 7?

5. Các bài toán trên bàn cờ

Bài 41. Có bao nhiêu cách đặt một quân cờ lên bàn cờ?

Bài 42. Có bao nhiêu cách đặt 2 quân xe lên bàn cờ sao cho chúng không ăn lẫn nhau?

Bài 43. Có thể đặt nhiều nhất bao nhiêu con xe lên bàn cờ sao cho chúng không ăn lẫn nhau?

Bài 44. Tám quân xe có bao nhiêu cách đặt lên bàn cờ sao cho không có hai quân nào có thể ăn lẫn nhau?

Bài 45. Nhiều nhất bao nhiêu quân:

• a) Mã
• b) Tượng
• c) Quân hậu

Có thể đặt lên bàn cờ sao cho chúng không thể ăn nhau?

Bài 46. Hãy xếp lên bàn cờ càng ít càng tốt quân:

• a) Quân vua
• b) Quân hậu

Sao cho nếu chỉ cần thêm một quân thì sẽ có những quân ăn nhau?

Bài 47. Trên bàn cờ ở các ô a1, b2, c3, d4 mỗi ô có một quân cờ đang đứng. Hãy cắt bàn cờ thành bốn phần trùng khít lên nhau sao cho mỗi hình có một quân cờ.

Bài 48.

• a) Đặt một con cánh cam lên một ô nào đó của bàn cờ. Con cánh cam có thể đi bằng cách dịch chuyển sang các ô chung cạnh với ô nó đang đứng sao cho ở mỗi ô đi qua và đi đúng một lần để cuối cùng quay lại ô xuất phát đầu tiên (duy nhất ô xuất phát có mặt 2 lần).
• b) Suy luận bài toán với bàn cờ kích thước $k \times n$?
• c) Suy luận bài toán trong không gian với hình hộp chữ nhật được ghép từ những hình lập phương có cạnh đơn vị (hai hình lập phương gọi là cạnh nhau nếu có mặt chung).

Bài 49. Một con mã xuất phát từ ô b2. Phải cần ít nhất bao nhiêu bước để nó đến được ô e8?

Bài 50. Một con mã xuất phát từ ô b2. Nó có thể đến ô cuối cùng là e7 không nếu phải đi qua tất cả các ô?

6. Tổ hợp - Hình học

Bài 51. Trên mặt phẳng $n$ điểm có thể xác định nhiều nhất bao nhiêu đường thẳng nối các đỉnh với nhau? Làm với các trường hợp $n = 5, 6, 10, k$.

Bài 52. 7 điểm trên mặt phẳng cần phải sắp xếp thế nào để chúng tạo được 9 đường thẳng?

Bài 53. Hãy lấy 7 điểm trên mặt phẳng sao cho khi nối chúng đôi một với nhau ta được 14 đường thẳng phân biệt.

Bài 54. 4 đường tròn và 3 đường thẳng cắt nhau nhiều nhất tại bao nhiêu điểm?

Bài 55. Cho trước một vài điểm trên mặt phẳng. Nối bất kì 2 điểm với nhau bằng các đường thẳng, ta nhận được 153 đường thẳng khác nhau. Hỏi ít nhất phải cần bao nhiêu điểm?

Bài 56. Một $n$-giác lồi có bao nhiêu đường chéo?

Bài 57. Một đa giác lồi có 189 đường chéo. Đa giác đó có bao nhiêu đỉnh?

Bài 58. Cho 5 điểm trên mặt phẳng. Qua ba điểm bất kì ta vẽ một vòng tròn, hỏi sẽ nhận được bao nhiêu vòng tròn khác nhau? Cho tất cả các trường hợp có thể?

Bài 59. Hãy xếp càng nhiều điểm trên mặt phẳng sao cho bất cứ 3 điểm nào giữa chúng đều là đỉnh của một tam giác cân!

Bài 60. Chu vi của hai hình lục giác cắt nhau nhiều nhất tại bao nhiêu điểm?

7. Trò chơi – Games

Bài 61. Trên lưới ô vuông $m \times n$ có hai người chơi. Mỗi lần mỗi người có thể gạch một ô trống, hoặc gạch hai ô cạnh nhau còn trống. Người nào gạch ô cuối cùng người đó thắng. Người nào có thể có chiến lược để luôn chiến thắng? Người bước đầu tiên hay người bước sau? Hãy giải bài toán trong các trường hợp:

• a) Lưới ô vuông $1 \times 9$
• b) Lưới ô vuông $1 \times 10$
• c) Lưới ô vuông $5 \times 5$

Bài 62. Người ta đặt lên bàn cờ ($8 \times 8$) một con tướng ông. Hai người thay nhau đi. Mỗi người một lần đi có thể bước chỉ về phía trái, bước xuống hoặc bước theo đường chéo về phía trái và đi xuống. Người thắng là người đi đến góc dưới cùng bên trái đầu tiên. Ai có chiến lược luôn luôn thắng? Nên chơi thế nào?

Bài 63. Hai người chơi. Người thứ nhất nói số 1, người thứ 2 nói số 2, sau đó hai người thay đổi nhau nói một số lớn hơn số vừa được nói trước đó ít nhất 1 đơn vị nhưng không vượt quá 2 lần số đó. Người thắng là người nói số 100 trước nhất. Có chiến lược để ai đó luôn thắng trận không?

Bài 64. Có ba nắm sỏi nhỏ, trong chúng có 1, 2, 3 viên sỏi. Hai người thay nhau bốc sỏi, nhưng mỗi lần chỉ được bốc từ một nắm. Người bốc viên sỏi cuối cùng là người thắng trận. Có chiến lược để ai đó luôn thắng trận không?

Bài 65. Có 10 đồng tiền kim loại được xếp thành vòng tròn và mặt số quay lên trên. Hai người chơi lật mặt các đồng tiền từ số chuyển sang chữ. Mỗi lần đi người đến lượt được lật một hoặc hai đồng đứng cạnh nhau. Người thắng là người lật cuối cùng. Ai là người có chiến thuật thắng trận? Và nên chơi như thế nào?

Bài 66. Người ta đặt một con xe lên bàn cờ $5 \times 7$. Hai người chơi. Họ có thể di chuyển quân xe sang trái hoặc đi xuống (số ô tùy thích). Người thắng trận là người dồn được con xe vào góc trái phía dưới. Ai có chiến thuật thắng trận? Nên chơi thế nào?

Bài 67. Người ta đặt một con tướng bàn lên bàn cờ $5 \times 7$. Hai người chơi. Họ có thể di chuyển quân cờ sang trái hoặc đi xuống hoặc đi theo đường chéo (số ô tùy thích). Người thắng trận là người dồn được con cờ vào góc trái phía dưới. Ai có chiến thuật thắng trận? Nên chơi thế nào?

Bài 68. Trên bàn có 40 que diêm, hai người chơi mỗi lần có thể lấy từ 2, 3, 4, 5 que. Người lấy cuối cùng thắng cuộc. Ai có chiến thuật thắng trận? Nên chơi thế nào?

Bài 69. Hai người chơi thay đổi nhau mỗi người nói một số nguyên. Người bắt đầu nói số 1, người tiếp theo sau đó phải nói số lớn hơn số vừa được nói trước đó ít nhất 1 đơn vị nhưng không được lớn hơn tổng của số vừa nói và tổng các chữ số của số này. Người thắng trận là người nói số 100. Ai có chiến lược để chiến thắng?

Bài 70. Hai người chơi xếp đồng tiền 1 USD lên một cái bàn hình chữ nhật. Các đồng tiền không được đè lên nhau. Người xếp cuối cùng là người thắng trận. Có nên nhận vai trò bắt đầu không? Bạn sẽ chơi thế nào?

8. Qui nạp

Bài 71. Ở trung tâm "Tinh Tướng" trong buổi tổng kết niên học người ta nhận thấy rằng thông thường buổi học đầu năm chưa thể dạy được, vì thế nhiều người đề nghị bỏ buổi học đầu năm cho tiết kiệm. Hỏi việc gì sẽ xảy ra?

Bài 72. Châu chấu – Nhà vô địch hồi tưởng lại những ngày đầu khởi nghiệp: "Trong buổi luyện tập đầu tiên tôi đã nhảy qua 10 cm. Tôi nghiệm thấy rằng, nếu đã nhảy qua được $x\text{ cm}$, thì với sự tập trung tốt hơn, tập trung sức cao hơn tôi cũng nhảy qua được độ cao $(x + 1)\text{ cm}$." Trên cơ sở này bạn suy ra điều gì?

Bài 73.

• a) Có thể cắt một hình vuông thành 10 hình vuông nhỏ? Các hình vuông có thể có kích thước khác nhau.
• b) Có thể cắt một hình vuông thành 1234567 hình vuông nhỏ?

Bài 74. Có thể cắt một hình tam giác thành $n$ ($n > 5$) hình tam giác con đồng dạng với hình tam giác ban đầu?

Bài 75. Những giá trị lũy thừa nào của 10 có thể phân tích được thành tổng của hai số chính phương?

Bài 76. Các đường thẳng chia mặt phẳng thành các miền khác nhau. Có thể dùng hai màu sơn các miền này sao cho cứ hai miền có chung cạnh (biên giới) thì có màu khác nhau?

Bài 77. Sau giải bóng bàn đấu vòng tròn, người ta muốn sắp xếp các tuyển thủ thành hàng dọc theo qui tắc: Người đứng sau luôn thua người đứng trực tiếp trước họ, tất nhiên ngoại trừ người đứng đầu tiên. Hỏi có thể luôn luôn thực hiện được việc này?

Bài 78. Các số $1, 2, 3, \dots, n$ được sắp xếp theo một thứ tự nào đó. Hai số trong dãy có tình trạng "ngược" nhau nếu số lớn đứng trước số bé.

• a) Chứng minh rằng với $n = 7$ tồn tại một sắp xếp của các số mà mỗi số có tình trạng ngược với 2 số khác.
• b) Với $n$ bằng bao nhiêu thì tồn tại một sắp xếp của các số mà mỗi số có tình trạng ngược với 3 số khác?

Bài 79. Một tập hợp $n$ phần tử. Hỏi có bao nhiêu tập con?

Bài 80. Chứng minh rằng với mọi $n$ một tập có $n$ phần tử thì số tập con có số chẵn phần tử bằng số tập con có số lẻ phần tử.

9. Mini Combinatorics

Bài 81. Có bao nhiêu số có 2 chữ số mà chữ số thứ 2 (hàng đơn vị) là số lẻ?

Bài 82. Có bao nhiêu số có 2 chữ số, mà trong các chữ số của nó có ít nhất một số lẻ?

Bài 83. Có bao nhiêu số có 3 chữ số mà trong các chữ số của nó có số 0?

Bài 84. Có bao nhiêu số có 4 chữ số mà giữa các chữ số của nó có chữ số trùng lặp (ví dụ: 2231, 1244, 3559)?

Bài 85. Giữa các số có 3 chữ số, các số mà các chữ số của nó đều lẻ nhiều hơn hay ít hơn các số mà các chữ số đều chẵn? Tại sao?

Bài 86. Có bao nhiêu số có ba chữ số mà số các chữ số lẻ của chúng là số lẻ?

Bài 87. Có bao nhiêu số có 5 chữ số mà đọc ngược (từ phải sang trái) ta được chính số đó (đối xứng)?

Bài 88. Có bao nhiêu số có ba chữ số mà tổng các chữ số bằng 6?

Bài 89. Có bao nhiêu số có 3 chữ số, mà tổng các chữ số của nó nhỏ hơn 4?

Bài 90. Có bao nhiêu số nhỏ hơn 2016, chia hết cho 3 và không chứa các chữ số của số 2016?

Bài 91. Có bao nhiêu cách chọn ra 3 số khác nhau nhỏ hơn 30 và tổng của chúng là số chẵn?

Bài 92. Một hình vuông mỗi cạnh được chia thành 7 phần bằng nhau. Có bao nhiêu tam giác mà các đỉnh là các điểm chia các cạnh nói trên (không tính các đỉnh của hình vuông)?

Bài 93. Cho 6 điểm trên mặt phẳng, không có 3 điểm nào thẳng hàng. Từ các điểm này có bao nhiêu tứ giác có thể chọn?

Bài 94. Một con châu chấu nhảy nhót trên đường thẳng số. Mỗi bước nhảy của nó có chiều dài một đơn vị. Nó muốn nhảy từ điểm 0 đến điểm 5 bằng 9 bước. Hỏi có bao nhiêu cách?

Bài 95. 5 bạn nữ và 3 bạn nam chia thành 2 đội chơi bóng rổ. Hỏi có bao nhiêu cách nếu đội nào cũng có ít nhất một bạn nam?

Bài 96. Từ 7 người đàn ông và 4 người đàn bà phải chọn ra một đội 6 người trong đó có ít nhất 2 người đàn bà. Hỏi có bao nhiêu cách?

Bài 97. Có bao nhiêu bộ số $\{a, b, c\}$ sao cho $a \cdot b \cdot c = 2310$?

Bài 98. Trong phòng có 10 ngọn đèn. Mỗi cái đều có thể tắt sáng độc lập. Hỏi có bao nhiêu cách thắp sáng sao cho ít nhất có một ngọn trong trạng thái sáng?

Bài 99. Có bao nhiêu cách đi lên một cầu thang 9 bậc mà mỗi lần bước có thể bước 1 hoặc 2 bậc thang?

Bài 100. Có bao nhiêu số có 10 chữ số mà chỉ chứa chữ số 2 và 5 sao cho các chữ số 2 không có hai số nào đứng cạnh nhau?

Bài 101. Tính tổng của các số có 3 chữ số được tạo thành từ các chữ số 5, 6, 7 sao cho trong mỗi số mỗi chữ số chỉ có mặt một lần.

Bài 102. Tính tổng của các số có 4 chữ số được cấu tạo từ các số 1, 2, 3, 4 (trong mỗi số các chữ số có thể giống nhau).

Bài 103. Tính tổng các số có 3 chữ số mà các chữ số của nó là số chẵn.

Bài 104. Một khối lập phương cạnh 10 cm được sơn các mặt màu đen, sau đó được cắt thành các khối lập phương con kích thước 1 cm. Hỏi có bao nhiêu khối lập phương con có ít nhất một mặt màu đen?

Bài 105. Người ta tung con xúc xắc 5 lần. Hỏi có bao nhiêu kết quả khác nhau có thể nhận được?

Bài 106. Người ta tung con xúc xắc 3 lần. Hỏi có bao nhiêu kết quả khác nhau có chứa con số 6?

Bài 107. Ba người có 3 đôi giày giống hệt nhau cùng tham gia một bữa tiệc, và họ cần bỏ lại giày ngoài cửa trước khi tham gia bữa tiệc. Sau bữa tiệc, mỗi người sẽ lấy 1 chiếc giày trái và 1 chiếc giày phải. Biết rằng mỗi người đều lấy 1 chiếc đúng là giày của mình và 1 chiếc là giày của người khác. Hỏi có bao nhiêu khả năng như vậy?

Bài 108. Cánh Cam làm toán mãi, nên muốn đi dạo quanh biệt thự thủy tinh của mình. Lối đi đều là các đoạn thẳng nối các chốt. Trước khi đi cánh cam muốn vẽ một sơ đồ đi dạo sao cho mỗi chốt chỉ phải đi qua một lần.

• Liệu cánh cam có làm được không? Hãy giúp cánh cam!

Mẹo hay

Lời khuyên học tập Các bài toán tổ hợp đòi hỏi tư duy phân loại, chia trường hợp logic và phát hiện tính đối xứng hoặc bất biến. Để đạt hiệu quả cao nhất, học sinh nên vẽ hình minh họa, thử nghiệm với các trường hợp nhỏ ($n = 1, 2, 3, 4$) trước khi tổng quát hóa công thức. Chúc các em luôn tìm thấy niềm hứng khởi khi chinh phục thế giới Toán tổ hợp!