Toán 11 [Ôn thi HSG] Phương pháp chia kẹo Euler trong tổ hợp

2712-0-3

Cựu TMod Toán
Thành viên
5 Tháng bảy 2021
1,068
1,741
206
Bắc Ninh
THPT đợi thi
[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.

Xin chào mọi người, đến với bài viết số 3 của mình, là một bài học luận nâng cao nên mong rằng các bạn sẽ theo dõi nhé. Các bài được đề cập cũng không quá khó đủ để các bạn suy nghĩ, chúc các bạn thành công với chủ đề này. :Tuzki8. Do hơi tấu hài nên mình "lỡ tay" thêm vài cái icon khùm khùm nên mong các bạn bỏ qua nha ^^.

CHIA KẸO EULER TRONG TỔ HỢP ĐẾM


I. LÝ THUYẾT

1) Bài toán đặt ra: "Thầy giáo có m cái kẹo chia cho n em học sinh sao cho mỗi em được ít nhất một cái kẹo [imath]m\geq n[/imath]. Hỏi có bao nhiêu cách chia hết kẹo cho các em?"
*Nhận xét: Bước đầu tìm hiểu, ta thấy bài toán cũng khá là tự nhiên, với các trường hợp số nhỏ thì ta có thể sử dụng đếm "chay" kết hợp quy tắc cộng , nhân để tính được. Nhưng khi bắt gặp với [imath]m,n[/imath] lớn thì điều này gần như quá khó.

Khi này, mình sẽ mang tới cho các bạn một cách giải vừa dễ hiểu cũng vô cùng dễ hiểu (do nhà toán học từ nhiều thế kỉ trước nghĩ ra) như sau:


*Hướng xử lý: Thầy giáo dải m chiếc kẹo lên mặt bàn lần lượt, rồi sử dụng [imath]n-1[/imath] chiếc que để chia m chiếc kẹo thành [imath]n[/imath] phần. Rồi tương ứng phát mỗi phần cho các em học sinh theo đúng thứ tự. Yêu cầu là thầy giáo không được xếp 2 chiếc que mà đặt cạnh nhau, giữa chúng không có kẹo.

Ví dụ: Cho 10 chiếc kẹo, chia cho 5 em, thầy có thể xếp như sau:
Thầy xếp 10 chiếc kẹo ra : :Tuzki33 o o o o o o o o o o
Thầy xếp 4 chiếu que vào: :Tuzki34 o | o o | o o | o | o o o o

Khi đó, ta có thể hiểu: Em học sinh thứ nhất có 1 cái, thứ 2 có 2 cái, thứ 3 có 2 cái, thứ 4 có 1 và thứ 5 có 4 cái.


Thì khi này, bài toán trở về tính số cách xếp [imath]n-1[/imath] que vào [imath]m-1[/imath] chỗ trống (tạo bởi [imath]m[/imath] chiếc kẹo) sao cho k có 2 que cùng chỗ. Đáp án chính là: [imath]\mathrm C^{n-1}_{m-1}[/imath]
:Tuzki35
2) Bài toán mở rộng: "Vậy nếu hôm đó, thầy phạt 1 số em học sinh nên không phát kẹo, thì sẽ có bao nhiêu cách chia kẹo cho [imath]n[/imath] em học sinh ? "
*Hướng xử lý: Thầy chạy ra ngoài quán bánh kẹo, mua thêm [imath]n[/imath] cái kẹo để phát cho mỗi em mỗi cái trước. Sau đó thầy chia và cuối giờ thầy sẽ thu của mỗi em 1 cái là được.
Nghĩa là, bài toán lúc này trở thành giống bài toán ban đầu, chỉ thay [imath]m[/imath] chiếc kẹo thành [imath]m+n[/imath] chiếc.
Vậy đáp án của bài toán chính là:[imath] \mathrm C^{n-1}_{m+n-1}[/imath]
:Tonton22
3) Bài toán phát biểu dưới dạng số học
Bài toán 1: "Cho n số nguyên dương [imath]x_1,x_2 , \cdots x_n[/imath] sao cho [imath]x_1+x_2 + \cdots x_n = m[/imath] . Khi đó số bộ [imath](x_1,x_2,\cdots x_n)[/imath] thỏa mãn là: [imath]\mathrm C^{n-1}_{m-1}[/imath] "
Bài toán 2: "Cho n số nguyên không âm [imath]x_1,x_2 , \cdots x_n[/imath] sao cho [imath]x_1+x_2 + \cdots x_n = m[/imath] . Khi đó số bộ [imath](x_1,x_2,\cdots x_n)[/imath] thỏa mãn là: [imath]\mathrm C^{n-1}_{m+n-1}[/imath] "
:Tonton8

II. BÀI TẬP VẬN DỤNG

Lưu ý: Những cách giải chay thông thường, mình sẽ không đề cập đến ở bài viết này, các bạn có thể thử làm những cách thông thường để so sánh kết quả và tốc độ với phương pháp này nhé ^^.
Ngoài ra, trong các bài giải còn kết hợp với đếm phần bù, và công thức giao các tập hợp, khá hữu ích trong phương pháp này.



Bài 1: Cô Thảo ra chợ mua hoa quả, ở quán cô Xuân bán: cam, quýt, dứa, thanh long, xoài. Cô Thảo dự định mua 30 quả, hỏi có bao nhiêu cách để mua sao cho mỗi loại trên đều cho ít nhất 1 quả ? Coi số hoa quả cô Xuân bán mỗi loại đều đủ cho cô Thảo mua.
Ta thấy 30 quả chia vào 5 loại: cam, quýt, dứa, thanh long, xoài mà mỗi loại quả ít nhất 1 quả, nên có số cách mua là:
[imath]C^{5-1}_{30-1} = C^4_{29}=23751[/imath]

Bài 2: Hoàng đi lấy bi đem bắn, có 4 màu: xanh, đỏ , tím, vàng. Để phù hợp với cách chơi, yêu cầu số bi xanh và đỏ phải ít nhất 5 viên, bi tím ít nhất 3 viên và bi vàng bất kì. Tổng số bi Hoàng đem đi không quá 25 viên. Vậy Hoàng có bao nhiêu cách chọn bi ? (Coi như số bi các màu của Hoàng là vô hạn)
Gọi số bi xanh, đỏ , tím , vàng lần lượt là [imath]x,y,z,t \in \mathbb{N}[/imath] thỏa mãn [imath]x,y \geq 5 , z \geq 3, t \geq 0[/imath] và [imath]x+y+z+t \leq 25[/imath] (1)
Bình luận: Vì ta thấy ở bất phương trình trên không phải lúc nào cũng là dấu bằng, và còn điều kiện phức tạp của các biến nên ta sẽ đưa nó về dạng đơn giản.
Khi đó, [imath]x+y+z+t = 25 - w[/imath] với [imath]w \geq 0 , w \in \mathbb{N} \Rightarrow (x-5)+(y-5) + (z-3) + t + w =12[/imath] (2)
Vậy số cách chọn [imath](x,y,z,t)[/imath] thỏa mãn bất phương trình (1) chính bằng số cách chọn bộ nghiệm tự nhiên [imath](x-5),(y-5),(z-3),t,w)[/imath] thỏa mãn phương trình (2). Số cách đó chính bằng:
[imath]C^{5-1}_{12+5-1}=C^4_{16}=1820[/imath]

Bài 3: Vé xe buýt dạng abcde (1 số có 6 chữ số) được gọi là vé xe may mắn nếu [imath]a+b+c=d+e+f[/imath]. Hỏi có tất cả bao nhiêu vé xe may mắn như thế?
Ta sẽ biến đổi điều kiện đề bài thành tổng các số hạng nhé!!

Ta có: [imath]a+b+c=d+e+f \Leftrightarrow a+b+c+ (9-d) + (9-e) + (9-f) = 27[/imath]
Đặt [imath]9-d=x;9-e=y;9-f=z \Rightarrow a+b+c+x+y+z=27[/imath] (1) thỏa mãn [imath]a,b,c,x,y,z \in \mathbb{N}; a,b,c,x,y,z \leq 9[/imath]
Khi này, số vé may mắn chính bằng số bộ [imath](a,b,c,x,y,z)[/imath] thỏa mãn (1).

Xét trường hợp a,b,c,x,y,z là số tự nhiên , thỏa mãn (1) thì số bộ tìm được là: [imath]C^{6-1}_{27+6-1}=201376[/imath]

Xét trường hợp vi phạm, khi này tồn tại ít nhất 1 số trong 6 số [imath]a,b,c,x,y,z \geq 10[/imath] .
Đặt [imath]A_1,A_2,A_3 ,A_4,A_5,A_6[/imath] là tập hợp các cách sao cho lần lượt [imath]a,b,c,x,y,z \geq 10[/imath]
Khi đó, cách tính số trường hợp vi phạm là: [imath]|A_1\cup A_2 \cup \cdots \cup A_6| = |A_1| + |A_2| +\cdots |A_6| - (|A_1 \cap A_2| + |A_1 \cap A_3| + \cdots |A_5 \cap A_6| )[/imath]
Cụ thể, chỗ này không cần liệt kê tiếp vì trường hợp giao của 3 tập trở lên, nghĩa là tồn tại ít nhất 3 số [imath]\geq 10[/imath] Mà tổng 6 số là 27 nên điều đó không thể xảy ra.
Mà vai trò các tập trên đều như nhau nên ta rút gọn công thức trên thành:
[math]S=|A_1\cup A_2 \cup \cdots \cup A_6| = C^1_6|A_1| - C^2_6 |A_1 \cap A_2| =6|A_1| - 15 |A_1 \cap A_2|[/math]*Đếm [imath]|A_1|[/imath], khi này [imath]a\geq 10[/imath] Nên phương trình (1) tương đương với: [imath](a-10) +b+c+x+y+z=17[/imath]
Có số cách chọn bộ là: [imath]C^{6-1}_{17+6-1}=26334[/imath]
*Đếm [imath]|A_1\cap A_2|[/imath], khi này [imath]a,b\geq 10[/imath] Nên phương trình (1) tương đương với: [imath](a-10) +(b-10)+c+x+y+z=7[/imath]
Có số cách chọn bộ là: [imath]C^{6-1}_{7+6-1}=792[/imath]
Từ đó suy ra số trường hợp vi phạm là : [imath]S = 6.26334 - 15.792=136124[/imath]
Vậy số vé xe may mắn là: [imath]201376-136124=55252[/imath]

Các bạn có thể thử sức với 2 bài toán thi HSGQG này, sử dụng chính chia kẹo Euler để có ngay 6 điểm, không quá khó.

Bài 4: (VMO 2012) Cho một nhóm gồm 5 cô gái, kí hiệu là [imath]G_1,G_2,G_3,G_4,G_5[/imath] và 12 chàng trai. Có 17 chiếc ghế được xếp thành một hàng ngang. Người ta xếp nhóm người đã cho vào các chiếc ghế sao đó sao cho các điều kiện sau được đồng thời thỏa mãn :
1) Mỗi chiếc ghế có đúng một người ngồi;
2) Thứ tự ngồi của các cô gái, xét từ trái qua phải, là [imath]G_1,G_2,G_3,G_4,G_5[/imath]
3) Giữa [imath]G_1[/imath] và [imath]G_2[/imath] có ít nhất 3 chàng trai;
4) Giữa [imath]G_4[/imath] và [imath]G_5[/imath]có ít nhất 1 chàng trai và nhiều nhất 4 chàng trai.
Hỏi có tất cả bao nhiêu cách xếp như vậy?

Bài 5: (VMO 2022) Gieo 4 con súc sắc cân đối, đồng chất. Kí hiệu [imath]x_i (1\leq x_i \leq 6)[/imath]là số chấm xuất hiện trên mặt xuất hiện của con súc sắc thứ $i.
a) Tính các bộ [imath](x_1,x_2,x_3,x_4)[/imath] có thể có.
b) Tính xác xuất để có một số trong [imath]x_1,x_2,x_3,x_4[/imath] bằng tổng của ba số còn lại.
c) Tính xác xuất để có thể chia [imath]x_1,x_2,x_3,x_4[/imath] thành hai nhóm có tổng bằng nhau.

Các bạn hãy tích cực đưa ra hướng làm, lời giải của riêng mình cho 2 bài toán trên nhé, một lúc cần thiết mình sẽ cung cấp lời giải chính xác cho 2 câu trên. Cảm ơn các bạn đã tham khảo bài viết này, Ngoài ra còn có nhiều bài toán khó về chủ đề này, bạn có thể tham khảo thêm tài liệu trên mạng nhé!!.

Chúc các bạn một tuần mới tốt lành! Giờ là 4h30 s

:MIM7:Rabbit39:Tonton24:Tuzki45
 
Top Bottom