Giải bài toán bằng cách lập phương trình chia kẹo năm 2024

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ó.

   Nội dung chính Show

   • II. BÀI TẬP VẬN DỤNG​
   • IIài toán mở đầu:
   • IVột số bài toán áp dụng:
   • Tài liệu

   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 :

   o o o o o o o o o o Thầy xếp 4 chiếu que vào:
   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]
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]
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] "

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.

Bài toán chia kẹo là một trong những bài toán tổ hợp hay và thú vị. Nên được ứng dụng nhiều trong các bài tập. Sau đây tôi sẽ trình bày về bài toán này.

IIài toán mở đầu:

Bài toán mở đầu: Có m chiếc kẹo giống nhau chia cho n em bé. Hỏi có bao

nhiêu cách chia? Đây cũng chính là bài toán: “Tìm số nghiệm không âm của phương trình : x 1 + x 2 +...+ xn=m (n, m ∈ 𝑁∗).”

Giải:

Với mỗi bộ x 1 , x 2 ,..., xn thỏa mãn x 1 + x 2 +...+ xn = m tương ứng 1-1 với bộ 11. .1⏟ 0 x 1

11 ... 1⏟ 0

x 2

. .0 11. .1⏟

xn

gồm m số 1 và n-1 số 0 (Đây là kĩ thuật song ánh). Để có

một bộ số chúng ta cần chọn n-1 vị trí trong m+n-1 vị trí để đặt chữ số 0 và còn lại đặt chữ số 1.

Suy ra số cách chia kẹo là: d =𝐶𝑚+𝑛−1𝑛− .

Bài toán 1: Tìm số nghiệm nguyên dương của phương trình: x 1 + x 2 +...+ xn = m

(n, m ∈ 𝑁∗).

Giải:

Đặt yi=xi-1 (Với i=1, 𝑛̅̅̅̅̅ ) ta có: y 1 + y 2 +...+ yn= x 1 + x 2 +...+ xn-n = m-n.

 Nếu m < n phương trình vô nghiệm.  Nếu m ≥ n, quay trở lại bài toán ban đầu số nghiêm của phương trình trên

chính là số nghiệm của phương trình là: d= 𝐶𝑚−1𝑛− .

Có thể tổng quát dạng toán này như sau: Cho n số tự nhiên, a 1 ,a 2 ,...,anìm

số nghiệm tự nhiên của phương trình:x 1 + x 2 +...+ xn=m thỏa mãn xi ≥ ai (∀i= 1, 𝑛̅̅̅̅̅ ).

Giải:

Đặt yi=xi- ai (∀ i=1, 𝑛̅̅̅̅̅ ) và S = a 1 +a 2 +...+an nên ta có:

 Kí hiệu r2xyz là nghiệm số của phương trình thỏa mãn x=y

𝐶𝑛−1 2 = (𝑛+2)(𝑛+1) 2 mỗi bộ số sẽ thuộc một trong những trường hợp trên nên ta

có: 6r 1 + 3r 2 + 3r 3 + r 4 = (𝑛+2)(𝑛+1) 2.

Ta có : r 2 + r 3 + r 4 chính là số nghiệm của phương trình 2u+v=n (vì từ phương trình x+y+z=n ta có thể cho 2 số hạng x=y hoặc y=z hoặc z=x và tất nhiên bao gồm cả trường hợp x=y=z). Giả sử x=y sẽ bao gồm x=y>z, x=y u+(u+v)=n. Đặt t=u+v ≥ u thu được u+t=n với u ≤ t.

Theo như bài toán 1 số nghiệm của phương trình này là [𝑛 2 ] +

hay r 2 + r 3 + r 4 = [𝑛 2 ] +1.

Xét:  Nếu n chia hết cho 3 => r 4 = 1.

 Nếu n không chia hết cho 3 => r 4 = 0 hay r 4 = [𝑛 3 ] − [𝑛−1 3 ]..

Vì x  y  z bao gồm x

d = 16 [(𝑛+2)(𝑛+1) 2 − 3𝑟 2 − 3𝑟 3 − 𝑟 4 ] + r 2 + r 3 + r 4.

\= (𝑛+2)(𝑛+1) 12 + 12 (𝑟 2 − 𝑟 3 ) + 56 𝑟 4

\= (𝑛+2)(𝑛+1) 12 + 12 (𝑟 2 + 𝑟 3 + 𝑟 4 ) + 13 𝑟 4

\= (𝑛+2)(𝑛+1) 12 + 12 ([𝑛 2 ] +1) + 13 ([𝑛 3 ] − [𝑛 2 ])

Bài toán 3: Tìm số nghiệm nguyên không âm của phương trình thỏa mãn:

x 1 + x 2 +x 3 + x 4 = n với x 1 ≤x 2 ≤x 3 ≤x 4.

Giải: Lời giải của Nguyễn Long Nhật và Nguyễn Hùng Quang (Trường Chuyên

KHTN):

Bổ đề Burnside: “ Nếu 𝜙 là các tập thuộc tập X. Với mỗi 𝜑 thuộc 𝜙 với 𝑋𝜑 biểu thị các phần tử trong tập X được xác định bởi 𝜑.Bổ đề Burnside xác định số quỹ đạo khác nhau của bài toán, biểu thị |X/ 𝜙 |: |𝑋/𝜙| = |𝜙| 1 ∑ 𝜑∈𝜙 𝑣(𝜑)(trong đó 𝑣(𝜑) là số phần tử của từng tập.”  Nếu 𝜑= id : v(𝜑) là số nghiệm của phương trình

x 1 + x 2 +x 3 + x 4 = n => v(𝜑) =𝐶𝑛+3 3 và có 1(𝜑).

 Nếu 𝜑 ∈ 𝜙: v(𝜑) là số nghiệm của phương trình 2x+y+z=n và 𝐶 42 = 6 (𝜑).

Ta có x ∈{ 0;1;...;[𝑛 2 ] } và phương trình có n-2x+1 với mỗi x.

\=> v(𝜑) = ∑ [ (𝑛 − 2𝑥 + 1) =

𝑛 2 ]

𝑥=0 ([

𝑛

2 ] + 1)(𝑛 + 1) − [

𝑛

2 ] ([

𝑛

2 ] + 1)

\= ([𝑛 2 ] + 1)([𝑛+1 2 ]+1).

 Nếu 𝜑 ∈ 𝜙: v(𝜑) là số nghiệm của phương trình 2x+2y=n và 12 𝐶 42 = 3 (𝜑).

• Nếu n lẻ, phương trình vô nghiệm.

(y 1 ,y 2 ,...,yn-i) → (0,0,...,0, y 1 +1,y 2 +1,...,yn-i+1). Có nghĩa là | Ti | = | Mm-n+i,n-i |, và do đó có thể viết: P (m, n) = P (m-1,1) + P (m-2,2) + ... + P (m-n, n) (1< n ≤ m) và với phương trình cụ thể ta có thể tính được kết quả cụ thể.

IVột số bài toán áp dụng:

Bài 1: Tìm số nghiệm không âm của phương trình: x+y+z+t=1000 với

t ≤ 499.

Giải:

Số nghiệm thỏa mãn x+y+z+t =1000 là 𝐶 10033 được chia ra như sau:

 Thỏa mãn yêu cầu đề bài t ≤ 499.  Không thỏa mãn yêu cầu đề bài t ≥ 500.

Xét t ≥ 500 ta có: x+y+z+(t-500) = 500

Đặt t 1 =t-500 ta thu được số nghiệm trong trường hợp này là 𝐶 5033.

Vậy đáp số của bài toán là: d = 𝐶 10033 - 𝐶 5033. Đây là phương pháp bù trừ rất hay sử dụng trong các bài toán tổ hợp không chỉ trong bài toán chia kẹo này một số bài toán sau cũng sử dụng phương pháp này.

Bài 2: Tìm số nghiệm không âm của bất phương trình: x+y+z+t ≤ 1000.

Giải:

Đặt u=1000-(x+y+z+t) ≥ 0 ta thu được bài toán tương đương x+y+z+t+u= (với x,y,z,u là những số nguyên không âm)

Đáp số của bài toán là: d= 𝐶 10044

Tổng quát: Số nghiệm nguyên không âm của bất phương trình

x 1 + x 2 +...+ xn ≤ m là 𝐶𝑚+𝑛𝑚 .

Bài 3: Tìm số bộ số nguyên không âm (x,y,z,t) thỏa mãn :

1 ≤ x ≤ y ≤ z ≤ t ≤ 1000.

Giải:

Đặt a 1 =x-1 ≥ 0 , a 2 =y-x ≥ 0, a 3 =z-y ≥ 0, a 4 =t-z ≥ 0, a 5 =1000-t ≥ 0. Ta có: a 1 + a 2 + a 3 + a 4 + a 5 = 999.

Đáp số: : 𝐶 10034

Bài 4: Tìm số nghiệm của phương trình sau: x 1 +x 2 +x 3 +x 4 =30 (5≤xi≤ 10 ∀𝑖 = 1,4̅̅̅̅ )

Giải:

Đặt yi=xi-5 ∀𝑖 = 1,4̅̅̅̅ .Từ giả thiết suy ra 0≤yi≤5. Ta có phương trình:

y 1 +y 2 +y 3 +y 4 =10 ( ∀𝑖 = 1,4̅̅̅̅ ).

Gọi X là tập hợp các nghiệm nguyên không âm của phương trình. Khi đó |X|=𝐶 133.

Gọi A,B,C,D lần lượt là các tập hợp thỏa mãn y 1 +y 2 +y 3 +y 4 =10 và 5≤yi. Theo bài 1 ta có: |𝐴| = |𝐵| = |𝐶| = 𝐷| = 𝐶 73. |𝐴 ∩ 𝐵| = |𝐴 ∩ 𝐶| = |𝐴 ∩ 𝐷| = |𝐵 ∩ 𝐶| = |𝐵 ∩ 𝐷| = |𝐶 ∩ 𝐷| = 0. |𝐴 ∩ 𝐵 ∩ 𝐶| = |𝐴 ∩ 𝐶 ∩ 𝐷| = |𝐵 ∩ 𝐶 ∩ 𝐷| = |𝐴 ∩ 𝐵 ∩ 𝐷| = 0. |𝐴 ∩ 𝐵 ∩ 𝐶 ∩ 𝐷| = 0. Áp dụng nguyên lí bù trừ ta có số nghiệm bằng: |𝑋| − (|𝐴| + |𝐵| + |𝐶| + |𝐷| − |𝐴 ∩ 𝐵| − |𝐴 ∩ 𝐶| − |𝐴 ∩ 𝐷| − |𝐵 ∩ 𝐶| − |𝐵 ∩ 𝐷| − |𝐶 ∩ 𝐷| + |𝐴 ∩ 𝐵 ∩ 𝐶| + |𝐴 ∩ 𝐶 ∩ 𝐷| + |𝐵 ∩ 𝐶 ∩ 𝐷| + |𝐴 ∩ 𝐵 ∩ 𝐷| − |𝐴 ∩ 𝐵 ∩ 𝐶 ∩ 𝐷|).

Vậy đáp số là: 𝐶 133 − 4𝐶 73 = 146.

Bài 5: Tìm số nghiệm của phương trình sau: x 1 +x 2 +x 3 +x 4 =14 và |xi|≤ 5

( ∀𝑖 = 1,4̅̅̅̅ ).

Giải:

Số nghiệm (a 4 ,...,a 12 ) là 𝐶 123. Số nghiệm (a 1 ,a 2 ,a 3 ) là 𝐶 63.  Nếu x=6 => a 4 +...+a 12 = Số nghiệm (a 4 ,...,a 12 ) là 𝐶 101. Số nghiệm (a 1 ,a 2 ,a 3 ) là 𝐶 85.  Nếu x=8 => a 4 +...+a 12 = Số nghiệm (a 4 ,...,a 12 ) là 1. Số nghiệm (a 1 ,a 2 ,a 3 ) là 𝐶 107. Vậy số cách xếp bóng vào hộp là 24528 cách.

Tài liệu

 Counting and Configuration – Jiri Herman, Radan Kucera, Jaromir Simsa.  Mathematical Olympiad Series, Vol: Combinatorial Problems on Mathematical Competitions – Yao Zhang.  Problem-Solving Methods in Combinatorics – Pablo Soberón Bravo.  Xung quanh bài toán chia kẹvietmaths