Bài Toán Chia Kẹo Của Euler (1) - 123doc

hay tuyệt vời.......................... khoogn có chỗ nào để chê được... quá hay... quá tuyệt.... hay nhất................................................................................................................................................................

Bài toán chia kẹo của Euler

I.Giới thiệu:

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.Bà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 :

x1+ x2+…+ xn=m (n, m ∈ 𝑁∗).”

Giải:

Với mỗi bộ x1, x2,…, xn thỏa mãn x1+ x2+…+ xn = m tương ứng 1-1 với bộ

11 .1

⏟ 0

x 1

11 … 1⏟ 0

x 2

.0 11 .1⏟

x n

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𝑛−1 .

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

(n, m ∈ 𝑁∗)

Giải:

Đặt yi=xi-1 (Với i=1, 𝑛̅̅̅̅̅) ta có:

y1+ y2 +…+ yn= x1+ x2+…+ 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𝑛−1

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

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

Giải:

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

y1+ y2 +…+ yn= x1+ x2+…+ xn- a1+a2+…+an = m-S

 Nếu m < S Phương trình vô nghiệm

 Nếu m = S Phương trình có 1 nghiệm

 Nếu m > S Phương trình có 𝐶𝑚+𝑛−𝑆−1𝑛−1 nghiệm

III.Một bài toán nâng cao:

Bài toán tổng quát:Tìm số nghiệm của phương trình: x1+ x2+…+ xn=m với x1≤x2 ≤ … ≤ xn

Trước tiên để giải bài toán tổng quát này ta sẽ làm với những bài toán nhỏ hơn:

Bài toán 1:Tìm số nghiệm của phương trình: x + y = m với x ≤ y

Giải:Đây là lời giải của thầy Nguyễn Vũ Lương (Trường THPT Chuyên KHTN):

Vì x≤y nên từ phương trình suy ra x ≤ [𝑛

2]:

 Nếu n chia hết cho 2 thì x có thể nhận 𝑛

2 + 1=[𝑛

2] +1 giá trị 0,1,2,…, [𝑛

2] và y tính được theo x (vì y=n-x) suy ra ta có [𝑛

2] +1 bộ (x,y) nguyên không âm thỏa mãn x+y=n và x≤ y

 Nếu n không chia hết cho 2 suy ra x ≤ [𝑛

2] và x có thể nhận [𝑛

2] +1 giá trị

và có [𝑛

Bài toán 2: Tìm số nghiệm không âm của phương trình: x+y+z=n thỏa mãn điều kiện x ≤ y ≤ z

Giải: Đây là lời giải của thầy Nguyễn Vũ Lương (Trường THPT Chuyên KHTN):

 Kí hiệu r1xyz là nghiệm số của phương trình thỏa mãn x < y < z Tương tự có r1xzy ,r1yzx ,r1yxz ,r1zxy ,r1zyx

Do vai trò của x,y,z hoàn toàn bình đẳng trong phương trình: x+y+x=n

Ta có: r1xyz = r1xzy = r1yzx = r1yxz = r1zxy = r1zyx=r1

 Kí hiệu r2xyz là nghiệm số của phương trình thỏa mãn x=y<z Tương tự có r2yzx ,r3zxy

Ta có: r2xyz = r2yzx = r1zxy = r2

 Kí hiệu r3xyz là nghiệm số của phương trình thỏa mãn x<y=z Tương tự có r3yzx ,r3zxy

Ta có: r3xyz = r3yzx = r3zxy = r3

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

Tất cả các bộ số nguyên không âm (x,y,z) thỏa mãn x+y+z=n bằng

𝐶𝑛−12 = (𝑛+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ó: 6r1 + 3r2 + 3r3 + r4 = (𝑛+2)(𝑛+1)

Ta có : r2 + r3 + r4 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<z, x=y=z

Phương trình 2u+v=n <=> 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] +1

hay r2 + r3 + r4 = [𝑛

2] +1

Xét:

 Nếu n chia hết cho 3 => r4 = 1

 Nếu n không chia hết cho 3 => r4 = 0 hay r4 = [𝑛

3] − [𝑛−1

3 ]

Vì x y z bao gồm x<y<z hoặc x=y<z hoặc x<y=z hoặc x=y=z

Vậy số nghiệm thỏa mãn yêu cầu của bài toán là: d = r1 + r2 + r3 + r4

Từ những dữ liệu trên ta có:

d = 1

= (𝑛+2)(𝑛+1)

6𝑟4 = (𝑛+2)(𝑛+1)

3𝑟4 = (𝑛+2)(𝑛+1)

2([𝑛

3([𝑛

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:

x1+ x2+x3+ x4 = n với x1≤x2≤x3≤x4

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

x1+ x2+x3+ x4= n => v(𝜑) =𝐶𝑛+33 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 ]

2] ([𝑛

= ([𝑛

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

2𝐶42 = 3 (𝜑)

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

* Nếu n chẵn, phương trình có 𝑛

2 + 1 nghiệm

=> v(𝜑) = ([𝑛

2 ])

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

=> v(𝜑) =[𝑛

3] + 1

 Nếu 𝜑 ∈ 𝜙: v(𝜑) là số nghiệm của phương trình 4x=n và 4!

4 = 6 (𝜑)

=> v(𝜑)= [𝑛

4 ] Tổng số các 𝜑 là 1+6+3+8+6=24

Theo bổ đề Burnside số nghiệm của phương trình ban đầu là:

1

24 (𝐶𝑛+33 +6([𝑛

2 ] + 1) ([𝑛+1

2 ] + 1) + 3([𝑛

2 ] + 1)([𝑛

2 ] − [𝑛−1

2 ])+8([𝑛

3 ] + 1) + 6([𝑛

4 ] − [𝑛−1

4 ]))

Quay lại bài toán tổng quát: Tìm số nghiệm của phương trình:

x1+ x2+…+ xn=m thỏa mãn : x1≤x2 ≤ … ≤ xn

Giải:

Có thể áp dụng bổ đề Burnside hoặc dung phương thức đệ quy như sau:

Giả sử Mm,n là tập hợp các kết quả của phương trình và P (m,n) số tập thỏa mãn của các yếu tố của phương trình Chúng ta dễ dàng thấy rằng:

P (0, n) = 1 với mọi k, P (m, n) = P (m, m) cho tất cả các k ≥ n

Do đó, ta giả định thêm rằng m cố định, chúng ta có 1< n  m Ta chia nhỏ các tập Mm,n vào thành các tập Ti (i = 0,1, , n-1), nên Ti chứa chính xác những kết quả của bài toán trong đó N0 thoả mãn điều kiện:

0=x1=x2=…=xi<xi+1<xi+2<…<xn

Ta có (x1,x2,…,xn) → (xi+1-1,xi+2-1,…,xn-1), định nghĩa một song ánh từ Ti đến Mm-n+i,n-i từ 0≤ xi+1-1≤ xi+2-1≤ …≤ xn-1,

(xi+1-1)+(xi+2-1)+…+(xn-1)=m-n+i, và ánh xạ:

(y1,y2,…,yn-i) → (0,0,…,0, y1+1,y2+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.Một số bài toán áp dụng:

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 t1=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

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=1000 (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

x1+ x2+…+ 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 a1=x-1 ≥ 0 , a2=y-x ≥ 0, a3=z-y ≥ 0, a4=t-z ≥ 0, a5=1000-t ≥ 0 Ta có:

a1 + a2 + a3 + a4 + a5 = 999

Đáp số: : 𝐶10034

Giải:

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

y1+y2+y3+y4=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 y1+y2+y3+y4=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

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

Giải:

Vì |xi| ≤ 5 => -5 ≤ xi ≤ 5 Đặt yi = xi + 5 (∀𝑖 = 1,4̅̅̅̅)

=> y1+y2+y3+y4=34 với 0≤xi≤10 (∀𝑖 = 1,4̅̅̅̅)

Làm tương tự bài 4 ta có kết quả là:540 nghiệm

hiệu của 2 số bất kì trong 5 số đó không nhỏ hơn 2?

Giải:

Theo bài toán ta sẽ có 5 số thỏa mãn đề bài sẽ không có 2 số nào liên tiếp, suy ra 5

số này chia chuỗi 13 số còn lại thành 6 chuỗi con trong đó mỗi chuỗi đều có ít nhất

1 phần tử Gọi số phần tử trong chuỗi là a1,a2, ,a6 bài toán tương đương với việc tìm số nghiệm nguyên dương của phương trình a1+a2+ +a6=13 Kết quả bài toán là

792

14?

Giải:

Gọi số phải tìm có dạng 𝑎𝑏𝑐𝑑̅̅̅̅̅̅̅ sao cho 0≤a, b, c, d≤9.Theo bài ra ta có:

a+b+c+d=14

Tương tự bài 4, số các số nguyên dương phải tìm là 456

xếp 8 viên bi đó vào các hộp sao cho tổng số bi trong hộp 1,2,3 là chẵn?

Giải:

Gọi số bi trong các hộp lần lượt là a1,…, a12

Đặt a1+a2+a3=x => x chẵn

 Nếu x=0 => có a4+…+a12=8

Số nghiệm (a4,…,a12) là 𝐶167 Số nghiệm (a1,a2,a3) là 1

 Nếu x=2 => a4+…+a12=6

Số nghiệm (a4,…,a12) là 𝐶145 Số nghiệm (a1,a2,a3) là 𝐶41

 Nếu x=4 => a4+…+a12=4

Số nghiệm (a4,…,a12) là 𝐶123 Số nghiệm (a1,a2,a3) là 𝐶63

 Nếu x=6 => a4+…+a12=2

Số nghiệm (a4,…,a12) là 𝐶101 Số nghiệm (a1,a2,a3) là 𝐶85

 Nếu x=8 => a4+…+a12=0

Số nghiệm (a4,…,a12) là 1 Số nghiệm (a1,a2,a3) 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.4: Combinatorial Problems on

Mathematical Competitions – Yao Zhang

 Problem-Solving Methods in Combinatorics – Pablo Soberón Bravo

 Xung quanh bài toán chia kẹo-www.vietmaths.com