-
Thông tin
-
Quiz
Tổ hợp lặp và bài toán chia kẹo Euler - Tài liệu tổng hợp
Ta biết rằng, một bộ gồm k phần tử lấy ra từ n phần tử phân biệt thỏa mãn 2 điều kiện: - Không tính thứ tự. - Một phần tử có thể được chọn nhiều hơn một lần. Chính là một tổ hợp lặp chập k của n phần tử (còn gọi là multiset, vì nó cho phép một số xuất hiện nhiều lần). Để xác định số tổ hợp lặp này, ta có thể nhận xét rằng: hai tổ hợp khác nhau khi có một số lượng một phần tử nào đó trong n phần tử của chúng là khác nhau. Tài liệu được sưu tầm giúp bạn tham khảo, ôn tập và đạt kết quả cao trong kì thi sắp tới. Mời bạn đọc đón xem !
Tài liệu Tổng hợp 1.9 K tài liệu
Tài liệu khác 2 K tài liệu
Tổ hợp lặp và bài toán chia kẹo Euler - Tài liệu tổng hợp
Ta biết rằng, một bộ gồm k phần tử lấy ra từ n phần tử phân biệt thỏa mãn 2 điều kiện: - Không tính thứ tự. - Một phần tử có thể được chọn nhiều hơn một lần. Chính là một tổ hợp lặp chập k của n phần tử (còn gọi là multiset, vì nó cho phép một số xuất hiện nhiều lần). Để xác định số tổ hợp lặp này, ta có thể nhận xét rằng: hai tổ hợp khác nhau khi có một số lượng một phần tử nào đó trong n phần tử của chúng là khác nhau. Tài liệu được sưu tầm giúp bạn tham khảo, ôn tập và đạt kết quả cao trong kì thi sắp tới. Mời bạn đọc đón xem !
Môn: Tài liệu Tổng hợp 1.9 K tài liệu
Trường: Tài liệu khác 2 K tài liệu
Thông tin:
Tác giả:
Preview text:
TỔ HỢP LẶP VÀ BÀI TOÁN CHIA KẸO EULER
Trần Anh Hào – 0878811605
I) Tóm tắt lý thuyết.
Ta biết rằng, một bộ gồm k phần tử lấy ra từ n phần tử phân biệt thỏa mãn 2 điều kiện:
- Không tính thứ tự.
- Một phần tử có thể được chọn nhiều hơn một lần.
Chính là một tổ hợp lặp chập k của n phần tử (còn gọi là multiset, vì nó cho phép một số xuất hiện nhiều lần).
Để xác định số tổ hợp lặp này, ta có thể nhận xét rằng: hai tổ hợp khác nhau khi có một số lượng một phần tử
nào đó trong n phần tử của chúng là khác nhau.
Gọi x , x ,..., x lần lượt là số lần mà phần tử thứ 1, 2,..., n được chọn. Ta có hệ điều kiện 1 2 n
x , x ,..., x 1 2 n .
x x ... x k 1 2 n
Ta thấy rằng số nghiệm của phương trình này cũng chính là số cách chia k viên kẹo cho n em bé mà mỗi em
có thể không nhất thiết có kẹo. Đây là bài toán chia kẹo Euler nổi tiếng hay còn được biết đến với tên gọi là bài
“stars and bars” hoặc “balls and urns”. Nguyên nhân của tên gọi này là vì để đếm số nghiệm ở trên, người ta thực hiện như sau:
Trước hết, ta đếm số cách chia thành các phần có số lượng phần tử dương:
Xếp k ngôi sao lên một đường thẳng *****************
Giữa các ngôi sao có đúng k 1 khoảng trống, ta tìm cách đặt các thanh chắn vào giữa chúng để chia các ngôi
sao thành n phần, chẳng hạn **** | **** | ******** | * k 1
Chọn n 1 khoảng trống trong k 1 khoảng trống, có . n 1
Trở về bài toán đếm số nghiệm không âm, ta chỉ cần mượn thêm n ngôi sao nữa rồi cho trước mỗi phần 1 ngôi
sao, khi đó, ta lại đưa về đếm số cách chia thành các phần có số lượng phần tử dương và tổng phần tử là n k.
n k 1 Kết quả là . n 1
Tóm lại, ta có các công thức quan trọng là:
n k 1
n k 1
- Số tổ hợp lặp chập k của n phần tử là hay . n 1 k 1 k n 1
- Số nghiệm dương của phương trình x n
với 1 k n là . i k 1 i 1 k
n k 1
- Số nghiệm không âm của phương trình x n là . i k 1 i 1
II) Các bài toán áp dụng.
Lập luận dạng trên cũng như kết quả đã nêu có khá nhiều ứng dụng trong các bài toán đếm tổ hợp. Dưới đây,
ta sẽ cùng tìm hiểu một số ứng dụng như thế. Mở đầu bằng một số bài toán đơn giản, áp dụng trực tiếp công
thức nghiệm của phương trình chia kẹo Euler. Bài 1.
Tính số nghiệm tự nhiên của các phương trình, bất phương trình sau
a) x x x x 3 với x , i 1, 4 . 1 2 3 4 i
b) x x x x x 2016 với x 5, x 4, x 3, x 2, x 1. 1 2 3 4 5 1 2 3 4 5
c) x x x x x x 100 với x 5,i 1, 6 . 1 2 3 4 5 6 i
d) x x x 1000 với x 3. 1 2 3 1
e) x x x x x 2016 với x không chia hết cho 3, i 1, 5 . 1 2 3 4 5 i
f) x x x x 50 . 1 2 3 4
g) 100 x x x x x x 200 . 1 2 3 4 5 6
h) (x x x )( y y y y ) 2017 . 1 2 3 1 2 3 4 Lời giải. 3 4 1 6 a) Số nghiệm là . 4 1 3
b) Đặt y x 5, y x 4, y x 3, y x 2, y x 1 thì 1 1 2 2 3 3 4 4 5 5
y y y y y 2001. 1 2 3 4 5 2001 5 1 2005 Số nghiệm là . 5 1 4
c) Đặt x 5y ,i 1, 6 thì i i
y y y y y y 20 . 1 2 3 4 5 6 20 6 1 25 Số nghiệm là . 6 1 5 2 1000 3 1 1002
d) Số nghiệm không âm của phương trình x x x 1000 là . 1 2 3 3 1 2 901
Nếu x 101 thì đặt y x 101, đưa về phương trình y x x 899 , số nghiệm là . 1 1 1 1 2 3 2 1002 901
Do đó, số nghiệm của phương trình cần tìm là . 2 2
e) Đặt x 3y r với i 1, 5 và 1 r 2,i 1,5 . i i i i
r r r r r 0 (mod 3) Vì 2016 0(mod 3) nên 1 2 3 4 5
r r r r r 6 hoặc 9 . 1 2 3 4 5
5 r r r r r 10 1 2 3 4 5 Ta xét hai trường hợp: 5
- Nếu r r r r r 6 thì có 4 số 1 và 1 số 2 , chọn 4 số trong 5 số, có cách chọn. Ngoài ra, ta 1 2 3 4 5 4 cũng có
3( y y y y y ) 2010 y y y y y 670 . 1 2 3 4 5 1 2 3 4 5 670 5 1 674
Số nghiệm của phương trình trên là . 5 1 4 5 674
Trường hợp này có tổng cộng nghiệm. 4 4 5
- Nếu r r r r r 9 thì có 4 số 2 và 1 số 1 nên tương tự, ta cũng có
cách chọn. Ngoài ra, ta cũng 1 2 3 4 5 4 có
3( y y y y y ) 2007 y y y y y 669 . 1 2 3 4 5 1 2 3 4 5 669 5 1 673
Số nghiệm của phương trình trên là . 5 1 4
5 674 5 673
Vậy số nghiệm của phương trình ban đầu là . 4 4 4 4
f) Xét phương trình x x x x a 50 trong đó a là số tự nhiên thì rõ ràng số nghiệm của phương trình 1 2 3 4
này bằng với số nghiệm của bất phương trình ban đầu. 3 50 5 1 54
Do đó, số nghiệm cần tìm là . 5 1 4 206
g) Tương tự bài trên, số nghiệm của bất phương trình x x x x x x 200 là . Ngoài ra, số 1 2 3 4 5 6 6 105
nghiệm của bất phương trình x x x x x x 99 là . 1 2 3 4 5 6 6 206 105
Vậy số nghiệm của bất phương trình đã cho là . 6 6
h) Do 2017 là số nguyên tố nên ta chỉ có 2 cách trường hợp:
1 3 1 2017 4 1 3 2020
- Nếu x x x 1, y y y y 2017 : có . 1 2 3 1 2 3 4 3 1 4 1 2 3
2017 3 1 1 4 1 2019 4
- Nếu x x x 2017, y y y y 1: có . 1 2 3 1 2 3 4 3 1 4 1 2 3
3 2020 2019 4
Vậy số nghiệm của phương trình là . 2 3 2 3
Bài 2. (bài toán về tổ hợp lặp)
a) Hỏi có bao nhiêu số tự nhiên có 7 chữ số a a a a a a a mà a a a a a a a ? 1 2 3 4 5 6 7 1 2 3 4 5 6 7
b) (Uzbekistan, 2012) Gọi S là tập hợp các số tự nhiên có 6 chữ số mà trong biểu diễn thập của nó có chữ số 7.
Biết rằng nếu x S thì số y tạo thành bằng cách hoán đổi các chữ số của x sẽ không thuộc S. Tính giá trị lớn nhất của S . Lời giải. 10 7 1 16
a) Ta thấy rằng số các số cần tìm chính là tổ hợp lặp chập 7 của 10 chữ số và là . Tuy nhiên, 7 7
phải trừ ra trường hợp toàn bộ là số 0 nên đáp số là 16 111439. 7
b) Với tính chất của tập hợp S, không mất tính tổng quát, ta có thể giả sử rằng tất cả các số thuộc tập hợp S đều
bắt đầu bằng số 7. Khi đó, 5 số còn lại là một tổ hợp có tính lặp của tập hợp 0,1, 2,...,
9 và để đạt được giá trị
lớn nhất, ta sẽ chọn hết các tổ hợp lặp đó. 10 5 1
Vậy kết quả cần tìm là 2002 số. 5 4
Bài 3. (bài toán về multiset)
a) Với k là số nguyên dương, xét a , a ,..., a là các số thực phân biệt. Đặt A (a , n ) 1 i k là một i i 1 2 k
multiset với cặp (a , n ) cho biết số a xuất hiện n lần trong đó. i i i i
Hỏi có bao nhiêu multiset B là tập con của A , trong đó mỗi phần tử của B cũng là của A và số lần xuất hiện
của nó trong B không nhiều hơn trong A ?
b) Cho A 1,2, 3,...,n . Chứng minh rằng tổng số các multiset có các phần tử lấy từ A và có số phần tử
không vượt quá n thì chia hết cho n 1. Lời giải.
a) Ta thấy multiset B có dạng B (a , m ) 1 i k với 0 m n ,i 1, k . i i i i
Như thế, có n 1 cách chọn m và mỗi cách chọn như thế cho ta tập hợp B khác nhau nên số tập con cần tìm i i là
(n 1)(n 1)...(n 1) . 1 2 k
b) Gọi x , x ,..., x là số lần xuất hiện của 1, 2,..., n trong multiset đã nêu thì 1 2 n
x x ... x . n 1 2 n
Xét phương trình tương ứng là
x x x ... x n , 0 1 2 n
trong đó x chỉ chênh lệch của tổng x x ... x và . n 0 1 2 n
n 1 n 1 2n
Số nghiệm của phương trình này là . n 11 n 2n
Ta cần chứng minh rằng n 1 . Ta có n 1 2n (2n)!
(2n)!(n 1 n) (2n)! (2n)!
2n 2n . n 1 n
(n 1)n!n!
(n 1)n!n! n!n!
(n 1)!(n 1)! n n 1
Đẳng thức cuối cho ta đpcm. Bài 4.
a) Robinson Crusoe lạc trên đảo hoang hơn 28 năm. Trong chừng ấy quãng thời gian, mỗi năm, ông ta tìm một
cái cây nào đó rồi khắc lên thân nó một hình đa giác lồi thật lớn và ngồi ngắm nghía. Biết rằng tổng tất cả các
góc của các đa giác lồi ấy vừa đúng 1687 , năm mà ông ấy được cứu thoát, đưa trở về thế giới loài người. Bạn 5
hãy cho biết có bao nhiêu cách ông khắc các đa giác lên cây thỏa mãn yêu cầu trên, biết rằng trong 10 năm đầu
tiên, mỗi năm, ông ấy khắc lên cây một đa giác có ít nhất 100 cạnh.
b) Có bao nhiêu xâu nhị phân có độ dài 20 sao cho sau mỗi số 0 , có ít nhất 3 số 1? Lời giải.
Đa giác có n cạnh thì có tổng các góc trong là (n 2) . Do đó, ta cần đếm số nghiệm của phương trình sau 28
(x 2) 1687 , x i i i 1 .
x 100,i 1,10, x 3,i 11,28 i i 28 28 Ta có
(x 2) 1687 x 1743 . i i i 1 i 1
Đặt x y 100,i 1,10 và x y 3,i 11, 28 , ta có phương trình i i i i 10 28 28 y 10 100
y 183 1743 y 689 . i i i i 1 i 1 1 i 1 689 28 1 716
Vậy số nghiệm nguyên không âm của phương trình là . 28 1 27
b) Ta thấy nếu có x số 0 trong xâu thì có thêm ít nhất 3x số 1. Ngoài ra, ta phải có
x 3x 20 x 5 .
Giả sử có k số 0 thì đặt a , a ,..., a lần lượt là số các số 1 nằm trước số 0 thứ nhất, giữa số 0 thứ nhất và thứ 0 1 k
hai, …, sau số 0 cuối cùng. Ta phải có a a ... a 20 k và a , a ,..., a 3 . 0 1 k 1 2 k
Đặt b a 3,i 1, k thì ta đưa về a b ... b 20 4k . i i 0 1 k
20 4k k 20 3k
Số nghiệm của phương trình này là .
Do đó, số xâu nhị phân cần tìm là k k
17 14 11 8 5 344 . 1 2 3 4 5
Bài 5. (Ấn Độ, 2012) Cho tam giác ABC và điểm P gọi là tốt nếu tìm được 27 tia chung gốc P cắt tam giác
thành 27 tam giác con có diện tích bằng nhau. Đếm số điểm tốt. Lời giải.
Trước hết ta thấy rằng P , A P ,
B PC phải là 3 trong 27 tia nêu trong đề bài (nếu không thì sẽ có một phần trong
các phần của tam giác ABC . Giả sử S
27 thì diện tích mỗi tam giác nhỏ đều bằng 1. ABC 6 Đặt S x, S y, S
z thì rõ ràng, các tam giác PBC, PC ,
A PAB đều phải chứa trong đó một số PBC PCA PAB
nguyên các tam giác có diện tích bằng 1 nên ta có x, y,
z và x y z 27 (*) . A z P y x B C
Chú ý rằng với mỗi P nằm trong tam giác thì PA S PB S PC S
0 và ngược lại với mỗi bộ PBC PCA PAB (S , S , S
) như thế thì tồn tại duy nhất P thỏa mãn. PBC PCA PAB 27 1 26
Do đó, số điểm cần tìm chính là số nghiệm của phương trình (*) và là 325. 3 1 2
Bài 6. (Đề kiểm tra Trường Đông 2014) Cho n 2 là một số nguyên dương. Xét tập hợp các đường đi ngắn
nhất trên lưới nguyên từ điểm (0
A ;0) đến điểm B( ;
n n) (độ dài đường đi là số lượng các bước đi). Một đường
đi như thế sẽ tương ứng với một dãy gồm n lệnh T (lên trên) và n lệnh P (sang phải). Trong dãy đó, một cặp
lệnh (T , P) kề nhau được gọi là một bước chuyển (lưu ý, cặp ( ,
P T ) không được gọi là bước chuyển).
Ví dụ dãy PTTPTPPT có 2 bước chuyển. Hãy tìm số các đường đi từ A đến B sao cho có đúng: a) 1 bước chuyển. b) 2 bước chuyển. Lời giải.
a) Ta phát biểu lại bài toán là: Cho xâu nhị phân có độ dài 2n với n số 0 và n số 1. Xác định số xâu nhị phân
thỏa mãn: cặp 10 chỉ xuất hiện đúng một lần.
Gọi A là các xâu nhị phân chứa toàn số 1, B là các xâu nhị phân chứa toàn số 0. Rõ ràng chỉ có các xâu dạng
sau thỏa mãn đề bài: AB, AB , A BA , B BABA . Dạng 1 có 1 xâu. n 1 Dạng 2 có n 1
xâu (ta đếm số nghiệm nguyên dương của x y n ). 2 1
Dạng 3 có n 1 xâu. Dạng 4 có 2
(n 1) xâu (ta đếm số nghiệm nguyên dương của cặp phương trình x y n rồi nhân lại vì
BA phía trước xây dựng độc lập với BA phía sau). 7 Vậy tổng cộng có 2 2
(n 1) 2(n 1) 1 n .
b) Tương tự trên, ta có các dạng ABAB, ABAB ,
A BABAB, BABABA . Dạng 1 có 2 (n 1) xâu. 2
n 1 n 1
(n 1) (n 1) Dạng 2 có xâu. 3 1 2 1 2 2
(n 1) (n 2) Dạng 3 có xâu. 2 2 2
n 1 n 1
(n 1) (n 2) Dạng 4 có xâu. 3 1 3 1 4
Vậy số đường đi tổng cộng thỏa mãn là 2 2 2 2 2 2
(n 1) (n 2)
(n 1) (n 2) (n 1) (n 1) n 2 2 (n 1) 2
(n 2) 4 (n 2) 4 . 4 2 4 4
Với các bài toán trên, ta thấy các trường hợp áp dụng bài toán chia kẹo Euler khá phong phú. Vấn đề có thể
được phát biểu dưới nhiều hình thức khác nhau, thậm chí còn có thể tiếp cận theo hướng khác. Trong phần tiếp
theo, ta xét một số bài toán khá quen thuộc của việc ứng dụng chia kẹo Euler vào việc chọn lựa các phần tử với
ràng buộc “không đứng cạnh nhau”. Ý tưởng quan trọng mấu chốt là gọi ra các khoảng cách giữa các phần tử. Bài 7.
a) Có bao nhiêu cách chọn từ 2016 số nguyên dương đầu tiên ra 10 số a , a ,..., a sao cho a a 1 với mọi 1 2 10 i j i j ?
b) Trên một bờ hồ, người ta muốn trồng các cây: hồng, cúc, lan, cau và tre. Biết rằng chu vi bờ hồ là 100m và
khoảng cách giữa các cây là các số nguyên dương. Giả sử kích thước của các gốc cây là không đáng kể. Hỏi có
bao nhiêu cách sắp xếp các cây này trên bờ hồ? Lời giải.
a) Không mất tính tổng quát, giả sử a a ... a thì khi đó, ta có thể đưa giả thiết đã cho về 1 2 10 a
a 2 với i 1,9 . i 1 i 8
Như thế, các số a này không đứng cạnh nhau. Gọi x là số các số trước a , x là các số sau a , còn lại x là i 1 1 11 10 i
số các số nằm giữa a và a . k 1 k 1 a1 a a 2016 10 2 a3 x x x1 x 3 11 2
Theo giả thiết, ta phải có x 0, x 0 và x 1 với i 2,10 . 1 11 i
Ngoài ra, x x ... x 2006. 1 2 11
Đặt y x 1 0,i 2,10 thì ta đưa về phương trình i i
x y ... y x 1997. 1 2 10 11 1997 111 2007
Số nghiệm của phương trình là . 111 10
Dễ thấy rằng một bộ nghiệm này cho ta một cách chọn ra một bộ 10 số thỏa mãn đề bài. Do đó, số các bộ cần 2007 tìm là . 10
b) Xét 5 vị trí trên bờ hồ để trồng các cây và gọi a, , b ,
c d , e lần lượt là khoảng cách giữa cây 1 và 2, 2 và 3, 3 và 4, 4 và 5, 5 và 1. Ta có
a b c d e 100 và a, ,
b c, d , e 0 . 100 5 1 104
Số nghiệm của phương trình này là . 5 1 4
Hoán vị vòng 5 cây trong 5 vị trí, ta có 4! cách. 104
Vậy số cách sắp xếp cần tìm là 4! . 4
Nhận xét. Một cách tương tự, ta có thể giải bài toán tổng quát là: Số cách chọn ra k số từ n số nguyên dương
n k 1
đầu tiên sao cho không có hai số nào đứng cạnh nhau là . k
Bài 8. (Việt Nam, 2012) Cho một nhóm gồm 5 cô gái, kí hiệu là G , G , G , G , G và 12 chàng trai. Có 17 1 2 3 4 5
chiếc ghế được xếp thành một hàng ngang. Người ta xếp nhóm người đã cho ngồi vào các chiếc ghế đó sao cho
các điều kiện sau được đồng thời thỏa mãn:
1/ Mỗi 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à G , G , G , G , G ; 1 2 3 4 5 9
3/ Giữa G , G có ít nhất 3 chàng trai; 1 2
4/ Giữa G , G có ít nhất 1 chàng trai và nhiều nhất 4 chàng trai. 4 5
Hỏi có tất cả bao nhiêu cách xếp như vậy? (Hai cách xếp được coi là khác nhau nếu tồn tại một chiếc ghế mà
người ngồi ở chiếc ghế đó trong hai cách xếp là khác nhau.) Lời giải.
Gọi a , a , a , a , a , a là số lượng chàng trai ngồi trước cô gái G , giữa cô gái G , G , giữa cô gái G , G , giữa 1 2 3 4 5 6 1 1 2 2 3
cô gái G , G , giữa cô gái G , G và sau cô gái G . 3 4 4 5 5
Ta có hệ điều kiện sau với các số tự nhiên a , a , a , a , a , a : 1 2 3 4 5 6
a a a a a a 12 1 2 3 4 5 6 .
a 3,1 a 4 2 5
Ta thấy a 1, 2,3, 4 và do a 3 nên có thể đặt b a 3 0 , ta đưa về 5 2 2
a b a a a 9 a . 1 3 4 6 5
9 a 5 1 13 a
Từ đây ta tính được số nghiệm của phương trình là 5 5 . 5 1 4
12 11 10 9
Với a 1, 2,3, 4 thì số nghiệm sẽ là 1161 . 5 4 4 4 4
Do nữ cố định nhưng các bạn nam có thể thay đổi vị trí nên đáp số của bài toán là 12! 1161 .
Tiếp theo, chúng ta xét một số bài toán cần phải đếm gián tiếp, kết hợp với nguyên lý bù trừ, khi các ràng buộc
về nghiệm có dạng “không lớn hơn một số” thay vì “không nhỏ hơn một số”. Bài 9.
a) Có bao nhiêu số nguyên dương nhỏ hơn 6
10 mà tổng các chữ số bằng 23 ?
b) Tìm số cách chọn ra 4 số nguyên phân biệt từ 24 số nguyên dương đầu tiên sao cho trong lựa chọn đó,
không có hai số cùng số dư khi chia cho 3 liên tiếp. Lời giải.
a) Số cần tìm có dạng a a a a a a với 1 2 3 4 5 6
a a a a a a 23 (*) và 0 a 9,i 1, 6 . 1 2 3 4 5 6 i
Gọi A , i 1, 6 là tập hợp các nghiệm không âm của (*) nhưng a 10. i i 10 23 6 1 28
Trước hết, ta thấy số nghiệm của (*) là . 6 1 5 6
Ta sẽ tính A với chú ý rằng A A A 0 với 1 i j k 6 vì tổng các số là 23. i i j k i 1
Tính A : đặt a a 10 0 thì a a a a a a 13 , phương trình này có số nghiệm là 1 1 1 1 2 3 4 5 6 13 6 1 18
. Tương tự với A ,i 2, 6. 6 1 5 i
Tính A A : đặt a a 10 0, a a 10 0 thì a a a a a a 3 , phương trình này có số 1 2 1 1 2 2 1 2 3 4 5 6 3 6 1 8 nghiệm là
. Tương tự với A A mà 1 i j 6 khác. 6 1 5 i j 6 6 18 6 8 Do đó A A
A A 6 . i i i j i i i j 5 2 5 1 1 1 6
Vậy số lượng các số cần tìm là
28 6 8
18 6 8 6
47712. 5 2 5 5 2 5
b) Gọi x , x ,..., x lần lượt là số các số nằm trước số thứ nhất được chọn, giữa số thứ nhất và số thứ hai, …, sau 1 2 5
x x ... x 20 1 2 5 số thứ tư. Ta có .
x 0, x 0, x 2, i 2, 4 1 5 i 24
Số nghiệm tự nhiên của phương trình ban đầu và không có điều kiện ràng buộc là . 4 24 Gọi , A ,
B C lần lượt là các cách chọn mà x 2, x 2, x 2 thì ta cần tính
A B C . 2 3 4 4 20 2 4 1 21 Ta có A
và tương tự với B,C. 4 1 3 20 4 3 1 18 A B
và tương tự với B C,C A . 3 1 2 20 6 2 1 15
A B C . 2 1 1 24 21 18 15
Do đó số cách chọn cần tìm là 3 3 7080. 4 3 2 1 11 Bài 10.
a) Trong không gian Oxyz, gọi S là tập hợp các điểm nguyên nằm phía trong hoặc ở trên đỉnh, cạnh và mặt của
hình lập phương cạnh 999 , trong đó các cạnh song song hoặc vuông góc với trục tọa độ, một đỉnh là (0;0; 0) và
một đỉnh đối với nó là (999;999;999). Hỏi mặt phẳng x y z 2016 đi qua bao nhiêu điểm trong tập hợp S ? b) Cho ,
m n là các số nguyên dương. Xét 2n quả táo, 2n quả đào, 2n quả cam, 3m quả xoài, 3m quả nho và
các quả cùng loại thì giống nhau. Gọi s là số cách chia số quả táo, đào, cam cho 2 người mà mỗi người nhận n
được 3n quả; t là số cách chia số quả xoài, nho cho 1 người và sử dụng ít hơn 3m quả. Chứng minh rằng m
s t với mọi , n m nguyên dương. n m Lời giải.
a) Rõ ràng các điểm thuộc S có dạng (x, y, z) x, y, z [0;999]
. Ta cần đếm số nghiệm nguyên không âm của phương trình sau
x y z 2016 thỏa mãn 0 , x y, z 999.
Tương tự các bài toán chia kẹo Euler có ràng buộc ở trên, dùng nguyên lý bù trừ, ta có kết quả là 2018 1018 18 3 3 482653. 2 2 2
b) Với cách chia táo – đào – cam, ta cần xét phương trình
x y z 3n với 0 x, y, z 2 . n
Tương tự trên, ta đếm được 3n 2 n 1
(3n 2)(3n 1) 3n(n 1) 2 s 3
3n 3n 1. n 2 2 2 2
Tiếp theo, để đếm t , ta chỉ cần đếm số nghiệm của x y 3m 1 với 0 x, y 3m . m
3m 1 3 1 3m(3m 1)
Tương tự, ta có số cách chia là t . m 3 1 2
Dễ thấy rằng với mọi n thì s không chia hết cho 3, còn t chia hết cho 3 nên s t với mọi số nguyên n m n m dương , m . n
Tiếp theo là một bài toán khá “kinh điển” về chủ đề này, bài toán “vé hạnh phúc”. Một vé hạnh phúc có 6 chữ
số và tổng của nhóm 3 số đầu bằng tổng của nhóm 3 số cuối. Mục tiêu là cần đếm số vé hạnh phúc. Ở bài này,
trước khi đưa về chia kẹo Euler, ta cần thực hiện một song ánh.
Bài 11. Vé xe buýt có dạng abcdef với a, , b c, d, ,
e f 0,1, 2,...,
9 . Một vé như trên thỏa mãn điều kiện
a b c d e f được gọi là “vé hạnh phúc”. 12
a) Chứng minh rằng số nghiệm của phương trình a b c d e f bằng số nghiệm của phương trình
a b c d e f 27 với 0 a, , b c, d , , e f 9 .
b) Tính số vé hạnh phúc. Lời giải. a) Gọi ,
A B lần lượt là số nghiệm của phương trình a b c d e f và phương trình a b c d e f . Ta thấy rằng
a b c d e f 27 a b c (9 d ) (9 e) (9 f ) .
Nếu đặt d 9 d, e 9 ,
e f 9 f thì ta được
a b c d e f .
Do đó, một bộ nghiệm của phương trình a b c d e f 27 sinh ra một bộ nghiệm của phương trình
a b c d e f nên A B .
Chứng minh tương tự, ta có B A nên A B .
b) Để đếm số nghiệm của phương trình
a b c d e f 27 (*) với 0 a, , b c, d , , e f 9 .
Gọi A , A , A , A , A , A lần lượt là tập hợp nghiệm của phương trình (*) nhưng có các điều kiện 1 2 3 4 5 6
a 10, b 10, c 10, d 10, e 10, f 10. 27 6 1 32 32 Số nghiệm của (*) là nên ta cần tính
A A ... A . 6 1 5 1 2 6 5 22
Xét A : đặt a a 10 0 thì ta có a b c d e f 17 và dễ thấy A . 1 1 5 22
Tương tự, ta cũng có A A A A A . 2 3 4 5 6 5
Xét A A : đặt a a 10 0,
b b 10 0 thì ta có a
b c d e f 7 và dễ thấy 1 2 12 A A . 1 2 5
Ngoài ra, ta thấy rằng A A A 0 với mọi 1 i j k 6 nên i j k 6 6 22 12
A A ... A A
A A 6 15 . 1 2 6 i 2 i j i
i j 5 5 1 1 6 13 32 22 12
Vậy số các số may mắn là 6 15 55252 . 5 5 5
Như trong đầu bài đã giới thiệu, chia kẹo Euler còn có tên gọi là bài toán “balls and urns”. Nó xuất phát từ bài
toán đếm số vòng cổ necklace tạo ra bằng cách xâu nhiều viên hạt xanh và đỏ. Khi đó, các viên cùng màu sẽ
tạo thành các vùng và số vị trí chuyển tiếp cũng bằng chính là số vùng đó. Trong phần còn lại, ta xét một
trường hợp như thế.
Bài 12. (Việt Nam, 2014) Cho đa giác đều có 103 cạnh. Tô màu đỏ 79 đỉnh của đa giác và tô màu xanh các
đỉnh còn lại. Gọi A là số cặp đỉnh đỏ kề nhau và B là số cặp đỉnh xanh kề nhau.
a) Tìm tất cả các giá trị có thể nhận được của cặp ( , A B).
b) Xác định số cách tô màu các đỉnh của đa giác để B 14. Biết rằng hai cách tô màu được xem là như nhau
nếu chúng có thể nhận được nhau qua một phép quay quanh tâm của đường tròn ngoại tiếp đa giác. Lời giải.
a) Gọi k là số dãy gồm các đỉnh liên tiếp được tô xanh và bị chặn hai đầu bởi đỉnh màu đỏ và h là số dãy gồm
các đỉnh liên tiếp được tô đỏ và bị chặn hai đầu bởi đỉnh màu xanh. Dễ thấy giữa 2 dãy đỏ là 1 dãy xanh và giữa
2 dãy xanh là 1 dãy đỏ nên h k.
Gọi a , a ,..., a là số lượng các đỉnh trong các dãy xanh; b , b ,..., b là số lượng đỉnh trong các dãy đỏ thì 1 2 k 1 2 k k k a 24, b 79 i . i i 1 i 1
Ngoài ra, rõ ràng nếu một dãy cùng màu có số lượng t thì có t 1 cặp đỉnh liên tiếp cùng màu. k Suy ra A
(a 1) 79 k
và tương tự B 24 k . i i 1 Do đó, các cặp ( ,
A B) sẽ có dạng (79 k, 24 k) với 0 k 24. Có tổng cộng 25 cặp như thế.
b) Do B 14 nên theo đẳng thức đã xây dựng ở trên thì 14 24 k k 10 . Như thế, có tổng cộng 10 dãy xanh và 10 dãy đỏ. 10 10 23 78
Số nghiệm nguyên dương của các phương trình sau a 24, b 79 , . i lần lượt là i 9 9 i 1 i 1
Do xếp trên một vòng tròn nên chỉ xét vị trí tương đối của nhóm với nhau chứ không xét vị trí cố định của từng nhóm. 1 23 78
Vậy số cách tô cần tìm là . 10 9 9
Bài 13. (AIME 1986) Cho xâu nhị phân: 001101001111011 có 4 cặp 01 , 3 cặp 10 , 5 cặp 11 và 2 cặp 00
đứng cạnh nhau. Hỏi có tất cả bao nhiêu xâu nhị phân cùng tính chất như thế? 14 Lời giải.
Tương tự bài toán trên, ta thấy rằng các xâu nhị phân thỏa mãn đề bài phải có dạng XYXYXYXY
trong đó X là một dãy các số 0 liên tiếp và Y là một dãy các số 1 liên tiếp. Như thế, có tổng cộng 4 dãy 0 và 4 dãy 1.
Rõ ràng trong một dãy có độ dài là k thì số lượng cặp giống nhau là k 1.
Gọi x, y, z, t là độ dài của 4 dãy 0 thì theo giả thiết, ta phải có
x 1 y 1 z 1 t 1 2 x y z t 6. 6 1 5
Số nghiệm nguyên dương của phương trình trên là 10. 4 1 3 Lại gọi , m ,
n p, q là độ dài của 4 dãy 1 thì m 1 n 1 p 1 q 1 5 m n p q 9. 9 1 8
Số nghiệm nguyên dương của phương trình này là 56. 4 1 3
Do hai dãy này chọn độc lập với nhau nên số xâu thỏa mãn là 10 56 560 xâu.
Nhận xét. Ta có thể bài toán tổng quát: Hỏi với các số tự nhiên a, , b ,
c d nào thì tồn tại một xâu nhị phân có độ
dài dương và có a cặp 01, b cặp 10, c cặp 11 và d cặp 00 đứng cạnh nhau?
Ta thấy rằng nếu xếp các số này lên vòng tròn thì các số 0 và 1 sẽ được tạo thành các nhóm rời nhau. Rõ ràng số
lượng nhóm 0 bằng số lượng nhóm 1. Do đó, nếu cắt xâu tại ranh giới giữa hai nhóm thì số lượng một trong hai
bộ 01 hoặc 10 sẽ giảm đi 1 đơn vị so với bộ kia.
Còn nếu cắt tại vị trí giữa các nhóm (trường hợp số lượng số trong nhóm lớn hơn 1) thì không làm thay đổi số lượng bộ 01 hoặc 10.
Trước hết, ta luôn có a b 1. Ngoài ra, dễ thấy rằng nếu c 0, d 0 thì phải tồn tại ranh giới giữa hai bộ nên
lúc đó, ta phải có hoặc a 0 hoặc b 0.
Từ đây ta thấy điều kiện của các số a, , b , c d là:
(1) Nếu cd 0 thì a b 0 .
(2) Nếu cd 0 thì a b 1 và a,b không đồng thời bằng 0.
Đặt k maxa,
b thì rõ ràng có tổng cộng k nhóm theo nhận xét ban đầu. Giả sử k 1 .
Gọi x , x , x ,..., x là số lượng số 1 có trong từng nhóm thì rõ ràng 1 2 3 k
x x x ... x c k . 1 2 3 k 15
c k 1
Số nghiệm dương của phương trình này là . k 1
d k 1
Tương tự số cách sắp xếp các số 0 là . k 1
c k 1 d k 1
Vậy số các xâu nhị phân thỏa mãn là
với k maxa,
b với k 1 ; trong trường hợp k 1 k 1
k 0 thì dễ thấy có 1 xâu thỏa mãn đề bài.
III) Một số bài tập rèn luyện. 3(n 1) 2 3n 1
Bài 1. Chứng minh số nghiệm nguyên của x y z
với 0 x, y, z n là . 2 4
Gợi ý. Ta có thể chia trường hợp n chẵn, lẻ để đếm cho thuận tiện. 9 10 11 99
Bài 2. Rút gọn tổng sau bằng bài toán chia kẹo Euler: A ... . 9 9 9 9 k k 11
Gợi ý. Ta thấy có thể viết thành
, đây chính là số nghiệm dương của phương trình 9 10 1
x x ... x k 1 . 1 2 10
Do đó, A chính là số nghiệm nguyên dương của bất phương trình 10 x x ... x 100. Đây là bài toán đã 1 2 10
giải quyết ở bài 1 của phần trước.
Bài 3. Có một dãy gồm 100 quyển vở đặt trên bàn và Tuấn được cô giáo thưởng 12 quyển vở trong số đó. Tuấn
rất ghét số 6 nên bạn ấy muốn chọn các quyển vở sao cho không có 2 quyển liên tiếp nào có thứ tự chênh lệch
nhau một lượng chia hết cho 6 . Biết rằng Tuấn đã chọn ra hai quyển vở ở hai đầu của dãy. Hỏi Tuấn có tổng
cộng bao nhiêu cách chọn ra thêm 10 quyển vở nữa theo ràng buộc trên?
Gợi ý. Gọi x , x ,..., x là số vở nằm giữa các quyển vở mà bạn Tuấn đã chọn. Ta có 1 2 9
x x ... x 88 và x 1 không chia hết cho 6 với i 1, 9. 1 2 9 i
Đến đây, ta gọi các số dư của biến và đếm dễ dàng.
Bài 4. Có bao nhiêu cách chọn ra trong 40 bạn học sinh xếp thành vòng tròn ra 7 bạn sao cho có ít nhất 2 bạn
học sinh đứng cạnh nhau? 16
Gợi ý. Ta xét trường hợp ngược lại: chọn ra 7 bạn sao cho không có 2 học sinh nào đứng cạnh nhau. Tương tự
trên, ta gọi a , a ,..., a là số học sinh giữa bạn thứ nhất và bạn thứ hai, giữa bạn thứ hai và bạn thứ ba, …, giữa 1 2 7
bạn thứ bảy và bạn thứ nhất. Ta có
a a a ... a 33 với a 1,i 1, 7 . 1 2 3 7 i 33 1 32 32
Số nghiệm của phương trình này là
và đáp số là 40 cách chọn. 7 1 6 6
Bài 5. Có bao nhiêu cách tô màu 12 ô vuông của bảng ô vuông 6 4 sao cho trên mỗi hàng có đúng 2 ô được
tô và trên mỗi cột có đúng 4 ô được tô? 4
Gợi ý. Xét một dòng tùy ý, do cần tô 2 ô của ô thuộc dòng này nên có 6
cách chọn ra 2 ô để tô. Gọi 2 a, , b , c d, ,
e f là số lần mà cặp cột 1 2;3 4;1 4; 2 3;1 3; 2 4 được chọn để tô.
Do mỗi cột có đúng 3 ô được tô màu nên ta phải có điều kiện
a c e a d f b d e b c f 3 .
Giải quyết hệ điều kiện này, ta có tổng cộng 720 60 1080 1860 cách tô.
Bài 6. Có 10 cái hộp khác nhau được đánh số từ 1 đến 10 và 10 viên bi giống nhau (mỗi hộp không nhất thiết
có bi). Hỏi có bao nhiêu cách sắp xếp 10 viên bi vào 10 hộp sao cho tổng số viên bi trong các hộp số 1, 2,3 là
số chẵn, còn tổng các viên bi trong các hộp 8, 9,10 là lẻ?
Gợi ý. Ta thấy rằng số cách chia cần tìm cũng bằng số cách chia mà: tổng số viên bi trong các hộp số 1, 2, 3 là 1
số lẻ, còn tổng các viên bi trong các hộp 8, 9,10 là số chẵn. Do đó, số cách chia bi thỏa mãn bằng số cách 2
chia bi mà tổng số bi ở các hộp 4, 5, 6, 7 là số lẻ. Đặt tổng đó là .
a Ta có a 1,3,5, 7, 9 .
4 11 9 6 1 4 14
Nếu a 1 thì dùng công thức chia kẹo Euler, ta có . 4 1 6 1 3 5 1
3 a 15 a
Tương tự với a 3, 5, 7,9 . Vậy đáp số của bài toán là 23000 . 2 a 3 5 1,3,5,7, 9
Bài 7. (AIME 2011) Ed có 5 quả cầu màu xanh giống nhau và một số rất lớn quả cầu màu đỏ giống nhau. Anh
ấy muốn xếp các quả cầu thành một dãy và với mỗi dãy, đặt a là số quả cầu mà bên trái nó là một quả cầu cùng
màu với nó, b là số quả cầu mà bên phải nó là một quả cầu khác màu với nó. Gọi m là số lớn nhất các quả cầu
màu đỏ có thể dùng sao cho tồn tại cách xếp m 5 quả cầu thành một dãy mà a b . Xác định m và số cách
xếp chúng để có a . b 15
Gợi ý. Ta chứng minh được m nhận giá trị lớn nhất là 16 và khi đó số cách xếp là . 5 17
Bài 8. (Tây Ban Nha, 2012) Cho x và n là những số nguyên dương sao cho 1 x n . Người ta có x 1 cái
hộp phân biệt và n x quả bóng giống nhau. Gọi f ,
n x là số cách phân phối n x quả bóng vào x 1 hộp.
Với p là một số nguyên tố cho trước, hãy tìm số nguyên n lớn hơn 1 sao cho số nguyên tố p là ước của f ,
n x với mọi x 1, 2,..., n 1 . n
Gợi ý. Ta dễ dàng tính được f ( ,
n x) và bằng công thức Legendre để tính số mũ của số nguyên tố p x
trong n!, ta tìm được k
n p với k nguyên dương là các số cần tìm. 18
TÀI LIỆU THAM KHẢO.
[1] https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)
[2] https://en.wikipedia.org/wiki/Urn_problem
[3] https://en.wikipedia.org/wiki/Multiset
[4] Diễn đàn http://artofproblemsolving.com.
[5] Trần Nam Dũng, Các phương pháp đếm nâng cao.
[6] Trần Quốc Luật, Đề thi và đáp án chọn đội tuyển Hà Tĩnh 2015.
[7] IMO Booklets các nước năm 2012. 19