Category Archives: Tổ hợp

Phương pháp chứng minh phản chứng (P2)

Bài 1. 

Cho tập B=1,2,3,,16. Người ta ghi các số của tập B thành một vòng tròn (mỗi số ghi một lần). Hỏi có cách ghi để tổng thỏa:

a/ Tổng của hai số kế nhau bất kì lớn hơn hoặc bằng 17 được không? Tại sao?

b/ Tổng của ba số kế nhau bất kì lớn hơn 24 được không? Tại sao?

Lời giải

a/ Giả sử tồn tại cách ghi thỏa mãn. Khi đó, gọi 2 số kề với 1 là a và b.

Theo giả thiết, ta có:

{1+a171+b17{a16b16 Mâu thuẫn.

Vậy không tồn tại cách ghi thỏa mãn.

b/ Giả sử tồn tại cách ghi thỏa mãn.

Khi đó, ta tách số 16 ra và chia 15 số còn lại thành 5 bộ 3 số kề nhau. Và tổng của 16 số này phải lớn hơn hoặc bằng: 16+525=141

1+2+3+16=136 Mâu thuẫn

Vậy không tồn tại cách ghi thỏa mãn.

Bài 2. 

Có tồn tại hay không một cách điền các số 0,1,2,3,,9 vào các đỉnh của một đa giác 10 đỉnh sao cho hiệu hai số ở hai đỉnh kề nhau chỉ có thể nhận một trong các giá trị sau: 5,4,3,3,4,5.

Lời giải

Giả sử có cách xếp thỏa mãn.

Xét các số 0,1,2,8,9 không thể đứng kề nhau và có đúng 10 số nên 5 số còn lại phải đứng xen kẽ với 5 số 0,1,2,8,9.

Xét số 7:

Khi đó hai số kề số 7 phải thuộc tập hợp {0,1,2,8,9}

Mà theo giả thiết 2 đỉnh kề nhau bất kì nhận một trong các giá trị – 3, – 4, – 5, 3, 4 hoặc 5 nên 2 số kề nhau với 7 đều bằng 2 Mâu thuẫn.

Vậy không có cách xếp nào thỏa mãn.

Bài 3. 

Trong mặt phẳng tọa độ thì một điểm mà hoành độ và tung độ đều là các số nguyên được gọi là điểm nguyên. Chứng minh rằng không tồn tại tam giác đều nào mà các đỉnh đều là điểm nguyên.

Lời giải

Giả sử tồn tại tam giác đều có các đỉnh là các điểm nguyên.

Xét hình chữ nhật có các đỉnh là các điểm nguyên, sao cho đỉnh của tam giác đều thuộc cạnh của hình chữ nhật. Khi đó dễ dàng suy ra diện tích tam giác đều là số hữu tỷ.

Ta có diện tích tam giác đều S=a234 với a2=x2+y2 là số nguyên, 3 là số vô tỷ

Do đó, S là số vô tỉ Mâu thuẫn đpcm.

Bài 4. 

Điền các số 1,2,3,…,121 vào một bảng ô vuông kích thước 11×11 sao cho mỗi ô chứa một số. Tồn tại hay không một cách điền sao cho hai số tự nhiên liên tiếp sẽ được điền vào hai ô có chung một cạnh và các tất cả các số chính phương thì nằm trong cùng một cột?

Lời giải

Giả sử tồn tại một cách điền số vào các ô thỏa yêu cầu đặt ra.

Khi đó bảng ô vuông được chia thành hai phần ngăn cách nhau bởi cột điền các số chính phương. Một phần chứa 11n ô vuông 1×1, và phần còn lại chứa 11011n ô vuông 1×1 , với 0n5.

Nhận thấy rằng các số tự nhiên nằm giữa hai số chính phương liên tiếp a2(a+1)2 sẽ cùng nằm về một phần và các số tự nhiên nằm giữa (a+1)2(a+2)2 sẽ nằm ở phần còn lại.

Ta có số lượng các số tự nhiên nằm giữa 1 và 4, 4 và 9, 9 và 16,…,100 và 121 lần lượt là 2,4,6,8,,20.

Do đó một phần sẽ chứa 2+6+10+14+18=50 số, phần còn lại chứa 4+8+12+16+20=60 số.

Cả 50 và 60 đều không chia hết cho 11 Mâu thuẫn.

Vậy không tồn tại cách điền số thỏa yêu cầu đề bài.

Bài 5. 

Mỗi phần tử của bảng vuông 25×25 hoặc là +1 hoặc 1. Gọi ai là tích của tất cả các phần tử của hàng thứ ibj là tích của tất cả các phần tử của cột thứ j. Chứng minh rằng a1+b1++a25+b250

Lời giải

Giả sử a1+b1++a25+b25=0.

Vì mỗi ô vuông chứa -1 hoặc 1 nên ai,bi{1,1}

Do đó trong 50 tích ai,bi(i=1,25) sẽ có 25 tích có giá trị -1 và 25 tích có giá 1.

Khi thay thế một phần tử -1 trong bảng bằng 1 thì số các tích ngang dọc có giá trị -1 sẽ tăng 2 hoặc giảm 2 hoặc không thay đổi. Như vậy số các tích ai,bi có giá trị -1 luôn là số lẻ (1)

Ta sẽ tiếp tục thay thế các phần tử -1 trong bảng bằng 1 cho đến khi tất cả các phần tử trong bảng đều bằng 1 thì khi đó số các tích ngang dọc ai,bi có giá trị -1 là 0 Mâu thuẫn với (1) đpcm.

Phương pháp ánh xạ trong các bài toán tổ hợp

Thầy Nguyễn Tăng Vũ

1/ Lý thuyết:

Cho AB là hai tập hợp hữu hạn.

  • Nếu có một đơn ánh f:XY thì |X||Y|.
  • Nếu có một toàn ánh f:XY thì |X||Y|.
  • Nếu có một song ánh f:XY thì |X|=|Y|.

2/ Bài tập:

Bài 1. 

Cho X=1,2,..,n. Một tập con S=s1,s2,,sk của X (s1<s2<<sk) được gọi là \textit{m- tách được} (mN) nếu sisi1m;i=1,2,,k. Có bao nhiêu tập con m- tách được gồm k phần tử của X, trong đó 0kn(m1)(k1).

Lời giải

Gọi A là tập tất cả các tập con m- tách được gồm k phần tử của X và B là tập tất cả các tập con gồm k phần tử của tập Y={1,2,,n(k1)(m1)}.

Ta xây dựng song ánh từ A đến B như sau: Với S={s1,s2,,sk}A (s1<s2<<sk) lấy tương ứng f(S)={s1,s2(m1),s32(m1),,sk(k1)(m1)}. Dễ chứng minh đây là một song ánh. Từ đó có Cn(k1)(m1)k tập thoả yêu cầu đề bài.

Bài 2. 

Cho X=1,2,,n, với mỗi tập con khác rỗng Ai=a1,a2,,ai (không mất tổng quát giả sử a1>a2>>ai) ta định nghĩa tổng hỗn tạp của Ai là số m(Ai)=a1a2+a3±ai. Tính AiXm(Ai).

Lời giải

Gọi B là tập tất cả các tập con không chứa phần tử n của X và C là tập tất cả các tập con có chứa phần tử n của X.

Ta xây dựng song ánh từ B đến C như sau: Với S={s1,s2,,sk}B (s1<s2<<sk<n) lấy tương ứng f(S)={s1,s2,,sk,n}, nhận thấy f(S)C. Dễ chứng minh đây là một song ánh.

Ta có: |B|=|C|=2n1;BC=;BC=X

m(S)+m(f(S))=n

Do đó: AiXm(Ai)=BiBm(Bi)+CiCm(Ci)=n2n1

Bài 3. 

Cho X=1,2,,n. Một tập con A của X được gọi là tập béo nếu mỗi phần tử của A đều không nhỏ hơn số phần tử của nó. Tập rỗng cũng là một tập béo. Đặt an là số các tập béo của X mà trong mỗi tập không chứa hai số liên tiếp, bn là số các tập con của X mà hai phần tử bất kỳ hơn kém nhau ít nhất 3 đơn vị. Chứng minh an=bn.

Lời giải

Gọi A là họ các tập béo thỏa yêu cầu đề bài, B là họ các các tập con của X có tính chất hai phần tử bất kỳ hơn kém nhau 3 đơn vị. Ta thiết lập một ánh xạ f đi từ A đến B như sau: giả sử x={a1,a2,,ak}A, ta có thể giả sử ka1<a2<a3<<akn. Đặt b1=a1k+1,b2=a2k+2,,bk=ak. Khi đó ai+1ai+2,i=1,2,,k1.

Suy ra ai+1ai2 do đó bi+1bi3b11,bkn. Định nghĩa f(x)=y={b1,b2,,bk}, suy ra yB. Vậy f là một ánh xạ, hơn nữa dễ thấy f là một song ánh do đó ta có điều cần chứng minh.

Bài 4. 

Cho số nguyên dương nd là một ước dương của n. Gọi S là tập tất cả những bộ (x1,x2,,xn) nguyên dương thỏa 0x1x2xnnd|x1+x2++xn. Chứng minh rằng có đúng một nửa các phần tử của S có tính chất xn=n.

Lời giải

(x1,x2,,xn1,xn)Sxnn ta cho tương ứng với bộ (x1+1,x2+2,,xn1+1,xn+1), với (x1,x2,,xn1,n)S ta cho tương ứng với bộ (0,x1,,xn1). \

Dễ chứng minh f là một song ánh, f hoán vị S và f(S)=S. Vì tổng tất cả các phần tử của các bộ trong S và f(S) là như nhau trong khi tương ứng thứ nhất tăng tăng tổng này lên n đơn vị, tương ứng thứ hai giảm tổng này đi n đơn vị nên số lần xuất hiện của hai tương ứng này là như nhau. Từ đó suy ra điều cần chứng minh

Bài 5. 

Gọi an là số các xâu nhị phân độ dài n không chứa ba bit 0, 1, 0 liên tiếp. Gọi bn là số các xâu nhị phân độ dài n chứa bốn bit 0, 0, 1, 1 hoặc 1, 1, 0, 0 liên tiếp. Chứng minh rằng bn+1=2an với mọi số nguyên dương n.

Lời giải

Gọi An,Bn lần lượt là tập các xâu nhị phân độ dài n thỏa điều kiện thứ nhất và thứ hai. Với mỗi xâu nhị phân (x1,x2,,xn) ta cho tương ứng với một xâu nhị phân (y0,y1,,yn) xác định bởi y0=0yi=x1+x2++xi mod 2,i=1,2,,n.   ()

Khi đó xi=yi+yi1 mod 2,i=1,2,,n.

Dễ thấy (*) là một song ánh giữa tập tất cả các xâu nhị phân độ dài n và tập tất cả các xâu nhị phân độ dài n+1 trong đó có bit đầu tiên là 0. Hơn nữa xâu nhị phân (x1,x2,,xn) có 3 bit 0,1,0 liên tiếp theo thứ tự này khi và chỉ khi xâu nhị phân tương ứng (y0,y1,,yn) có 4 bit liên tiếp theo thứ tự là 0,0,1,1 hoặc 1,1,0,0. Nói cách khác một xâu nhị phân thuộc An sẽ tương ứng với một xâu nhị phân thuộc Bn+1 và bắt đầu bằng bit 0. Vì số xâu nhị phân thuộc vào Bn+1 bắt đầu bằng bit 0 đúng bằng một nửa số xâu nhị phân thuộc vào Bn+1 do đó ta có bn+1=2an (điều phải chứng minh).

 

Đếm bằng 2 cách

NGUYỄN QUANG TÂN

1/ Bài tập đếm số cặp

Bài 1. 

Trong một ủy ban, mỗi thành viên thuộc đúng 3 tiểu ban, mỗi tiểu ban có đúng 3 thành viên. Chứng minh rằng số thành viên của ủy ban bằng số tiểu ban.

Lời giải

Gọi số thành viên là n và số tiểu ban là m.

Gọi T là số cặp (a,B) trong đó thành viên a thuộc tiểu B. Vì mỗi thành viên thuộc 3 tiểu ban nên: T=3n;

Vi mỗi tiểu ban có đúng 3 thành viên nên T=3m;

Vậy 3m=3n nên m=n

Bài 2. 

Trong trường học có một số câu lạc bộ. Biết rằng mỗi câu lạc bộ có đúng 30 học sinh. Vâ mỗi học sinh tham gia đúng 3 câu lạc bộ. Biết rằng tổng số câu lạc bộ và số học sinh bằng 440 . Tìm số học sinh của trường.

Lời giải

Ta đếm số cặp (a,B) mà học sinh a thuộc câu lạc bộ B. Gọi m là số câu lạc bộ và n là số học sinh.

Ta có hệ 30m=3nm+n=440. Ta được m=40n=400.

Bài 3. (IMC 2002)

Có 200 thí sinh tham gia một cuộc thi toán học. Các thí sinh phải giải 6 bài toán. Biết mỗi bài được giải đúng bởi ít nhất 120 thí sinh. Chứng minh rằng có hai thí sinh mà mỗi bài tập được giải bởi ít nhất một trong hai thí sinh.

Lời giải

Ta dùng phản chứng: Với mỗi cặp thí sinh bất kì đều có ít nhất 1 bài không giải được bởi cả hai thí sinh.

Gọi T là số bộ ({t1,t2};B) thỏa mãn thí sinht1,t2 cùng không giải được bài tập B.

Ta biết rằng mỗi bài được giải bởi ít nhất 120 thí sinh, vậy số thí sinh không giải được một bài nhỏ hơn hoặc bằng 80.

Nên T6C802=18960

Mặt khác hai thí sinh bất kì có ít nhất một bài cùng không giải được nên TC2002=19900. Mâu thuẫn.

Vậy điều phản chứng là sai. Bài toán được chứng minh.

Bài 4. (Chọn đội tuyển thi Quốc Gia Khối chuyên ĐHSP 2013)

Cơ sở dữ liệu tạp chí của thư viện Quốc Gia có đúng 2016 loại khác nhau. Thư viện này cho phép 2013 thư viện địa phương kết nối để có thể khai thác cơ sở dữ liệu tạp chí của nó. Biết mỗi thư viện địa phương được phép khai thác ít nhất 1008 loại tạp chí khác nhau và 2 thư viện địa phương bất kì có tối đa 504 loại tạp chí mà cả 2 thư viện địa phương đó cùng đc phép khai thác. Chứng minh rằng không có quá 1 loại tạp chí trong cơ sở dữ liệu của thư viện Quốc Gia mà cả 2013 thư viện địa phương đều không thể khai thác được.

Lời giải

Giả sử có 2 tạp chí mà không thư viện địa phương nào cùng khai thác. Như vậy tập hợp các tạp chí mà các thư viện cùng khai thác là X= {1,,2014}. Gọi T là số bộ ({T1,T2},t) mà hai thư viện T1,T2 cùng khai thác tạp chí t.

Vì mỗi thư viện khai thác chung tối đa 504 tạp chí nên: T504C20132.

Giả sử số thư viện cùng khai thác tạp chí thứ iai thi i=12013ai2013.1008.

Ta có: T=i=12014Cai22003.1008(2003.10082014)2.2014

Suy ra: 504C201322003.1008(2003.10082014)2.2014. Điều này vô lý.

Bài 5. (Chọn đội tuyển HSG QG tỉnh Đồng Tháp năm học 2013)

CLB du khảo có n thành viên. Năm ngoái CLB đã tổ chức được 6 chuyến du khảo, mỗi chuyến có 5 thành viên tham dự. Một thành viên CLB nhận xét rằng hai chuyến du khảo bất kỳ có không quá hai thành viên chung. Hỏi CLB đó có ít nhất bao nhiêu thành viên?

Lời giải

Giả sử câu lạc bộ đó có n thành viên. Tập hợp các học sinh tham gia chuyến du khảo thứ iAi. Ta có:

i) |Ai|=5;

ii) |AiAj|2

Giả sử thành viên thứ i tham gia ai chuyến du khảo ta có i=16ai=30.

Gọi T là số bộ (Ai,Aj,k) trong đó thành viên k tham gia cả hai chuyến du khảo AiAj

$$

T=\sum_{i=1}^{n} C_{a_{i}}^{2} \geq \frac{15(30-n)}{n}

$$

Vì hai chuyến du khảo bất kì có không quá 2 thành viên chung nên: T2C62=30

Suy ra: 15(30n)n30n10

2/ Bài tập đếm số bộ ba

Bài 6.

Trong một trương học có m lớp với m10, tổng số học sinh là n. Với n465, các lớp được đánh số từ 1 tới m, biết rằng mỗi học sinh ở lớp i quen j học sinh ở lớp thứ j. Tìm giá trị lớn nhất của n.

Lời giải

Giả sử lớp thứ iki học sinh. Từ quan hệ quen biết ta có: kij=kji nên kii=t với mọi i.

Vi k1++km=n465 nên t(1++m)465m10 nên t10.112=55

Suy ra 55t465 nên n8. Vậy n lớn nhất bằng 8 .

Bài 7. (Hong Kong TST 2003)

Có 15 học sinh tham gia một khóa học. Biết rằng mỗi ngày, có 3 học sinh phải trực vệ sinh cho lớp và sau khi kết thúc khóa học thì cứ 2 học sinh bất kì đều tham gia trực chung đúng 1 lần. Tính số ngày khóa học diễn ra.

Lời giải

Giả sử khóa học có m ngày. Ta gọi S là số bộ (x,y,z) trong đó hai học sinhx,y cùng tham gia trực nhật vào ngày thứ z của khóa học.

Vì 2 học sinh bất kỳ đều tham gia trực nhật chung đúng một lần nên S= C152=105. Mặt khác mỗi ngày có 3 học sinh tham gia trực nhật nên S= mC32=3m

Vậy m=1053=35.

Bài 8. (IMO 1989)

Cho nk là các số nguyên dương mà tồn tại một tập Tn điểm trong mặt phẳng sao cho

i) Không có 3 điểm nào thẳng hàng;

ii) PT có ít nhất k điểm thuộc T mà cách đều P.

Chứng minh rằng k12+2n

Lời giải

Gọi S là số các bộ 3 điểm ({A,B},C)A,B cách đều C.

Trước hết ta đếm theo {A,B} : Với mỗi cạ̣p điểm {A,B} thì các điểm cách đều AB nằm trên trung trực của đoạn AB. Mà không có 3 điểm nào thẳng hàng trong T nên ta có chỉ có tối đa 2 điểm C. Vậy S2Cn2.

Ta đếm theo C : Với mỗi điểm C có ít nhất k điểm trong T cách đều C nên số cặp {A,B} ít nhất là Ck2. Do đó SnCk2.

Suy ra 2Cn2nCk2. Từ đó ta có: k12+2n

Bài 9.

Cho X là một tập hữu hạn với |X|=nA1,A2,,Am là các tập con của X có đúng 3 phần tử thỏa mãn |AiAj|1ij. Chứng minh rằng tồn tại một tập con AX với ít nhất [2n] phần tử mà không chứa bất kì tập Ai(1im) nào.

Lời giải

Giả sử AX là một tập con với số phần tử lớn nhất là k mà không chứa bất kì tập Ai(1im) nào.

Gọi S là số bộ ({a,b},c) thỏa mãn cA{a,b} là tập con của một trong một tập A1,,Am.

Ta đếm theo c : Với mỗi cA do tính cực đại của A thì sẽ tồn tại Ai A{c} khi đó chọn {a,b}=Ai{c}.

Do vậy Snk.

Ta đếm theo {a,b}: Do |AiAj|1ij nên với mỗi {a,b}A tồn tại nhiều nhất một Aj{a,b}, khi đó ta chọn c=Aj{a,b}. Do đó SCk2.

Suy ra nkCk2 hay k2+k2n nên k12+121+8n

Từ đó ta có: k2n.

Bài 10. (APMO 2006) 

Trong một rạp xiếc, có n chú hề được trang điểm bằng một số trong tổng cộng 12 màu sơn. Biết rằng mỗi chú hề phải sử dụng ít nhất 5 màu. Ngoài ra, mỗi màu được sử dụng bởi không quá 20 chú hề. Chứng minh rằng n48

Lời giải

Gọi số chú hề sử dụng màu sơn thứ iai20. Ta có T=i=112ai 5n. Gọi S là số bộ (x,y,m) trong đó hai chú hề x,y cùng sử dụng màu sơn thứ m

Ta có S=i=112Cai2T(T12)2.125n(5n12)24

Vì mỗi màu sơn được sử dụng bởi không quá 20 chú hề, S12C202=2280. Ta có phương trình 5n(5n12)242280n48

Bài 11. (China MO 1996)

Có 8 ca sĩ tham gia một chương trình văn nghệ với tổng cộng m buổi hòa nhạc. Trong mỗi buổi hòa nhạc, có 4 ca sĩ tham gia và số lần tham gia của mỗi cặp ca sĩ là như nhau và bằng n.
Tìm giá trị nhỏ nhất của m.

Lời giải

Ta gọi S là số bộ (A,b,c) trong đó ca sĩ b,c cùng tham gia buổi hòa nhạc A.

Vi hai ca sĩ bất kì cùng tham gia biểu diễn n buổi nên S=nC82.

Mặt khác có m buổi biểu diễn và mỗi buổi có đúng 4 ca sĩ tham gia nên S=mC42

Do vậy nC82=mC42 hay 14n=3m. Suy ra 14m nên m14. Giá trị nhỏ nhất của m là 14 .

Dưới đây là một sách sắp xếp như vậy

Không có mô tả.

Bài 12. (VMO 2005)

Cho bát giác lồi A1A2A8 mà không có ba đường chéo nào đồng quy. Giao của hai đường chéo tùy ý được gọi là một “nút”. Xét tất cả các tứ giác lồi được tạo thành bởi bốn đỉnh của bát giác đã cho và các tứ giác đó được gọi là “tứ giác con”. Hãy xác định số nguyên dương n nhỏ nhất sao cho có thể tô màu n nút để với mọi iki,k1,2,,8 thì các số s(i,k) bằng nhau, trong đó s(i,k) ký hiệu số tứ giác con nhận Ai,Ak làm đỉnh và giao của hai đường chéo là một nút được tô màu.

Lời giải

Bài toán này chính là bài toán China MO 1996. Thật vậy nếu ta coi các đỉnh của đa giác là các ca sĩ. Mỗi một nút được tô màu là là một buổi biểu diễn. Khi đó số s(i,k) chính là số buổi biểu diễn mà ca sĩ Ai,Ak cùng tham gia.

Bài 13. (Chọn đội tuyển PTNK 2014)

Cho tập hợp X=1,2,3,,19 và xét một họ Ω gồm k tập con có 7 phần tử của X. Một tập hợp AX được gọi là “tập mẹ” của họ Ω nếu như A có 8 phần tử và tồn tại một tập hợp BΩ sao cho BA. Gọi d là số tất cả các tập mẹ của Ω. Chứng minh rằng d32k.

Lời giải

Gọi S là số bộ (B,A) sao cho B thuộc họ ΩA là mẹ của B.

Vì một tập B thì có 7 phần tử, vậy A muốn là mẹ của B thì A phải bổ sung thêm một trong 12 phần tử còn lại. Tức là mỗi tập B sẽ có 12 tập mẹ. S=k.12 Mỗi tập A có 8 tập con có 7 phần tử nên mỗi tập mẹ A có nhiều nhất 8 tập conB. Ta có S8d

Suy ra: 12k8d. Vậy d32k

Bài 14. (Russia 1996)

Ở một thành phố nọ, có 1600 đại biểu tham gia vào 16000 ủy ban và mỗi ủy ban có đúng 80 người tham gia. Chứng minh rằng có 2 ủy ban nào đó có ít nhất 4 đại biểu tham gia chung.

Lời giải

Gọi ai là số ủy ban mà đại biểu thứ i tham gia. Ta gọi T là số bộ (x,Y) mà đại biểu x tham gia ủy ban Y.

Trước hết ta đếm theo Y thì T=16000.80.

Bây giờ ta đếm theo x thì T=i=11600ai.

Suy ra i=11600ai=16000.80

Ta chứng minh bằng phản chứng, giả sử 2 ủy ban bất kì có không quá 3 đại biểu chung.

Ta gọi S là số bộ (x,V,U) trong đó đại biểu x cùng tham gia cả 2 ủy ban UV. Ta có S3C160002

Bây giờ ta đếm theo x thì S=i=11600Cai2T(T1600)2.1600.

Từ đó ta rút ra điều vô lý.

Bài 15. (Bulgari MO 2006)

Một quốc gia có 16 thành phố và có 36 tuyến bay nối giữa chúng (chuyến bay ở đây là hai chiều). Chứng minh rằng ta có thể tổ chức một chuyến bay vòng quanh giữa 4 thành phố nào đó.

Lời giải

Ta chứng minh bằng phản chứng. Giả sử với 2 sân bay A,B bất kì có không quá một thành phố C có thể bay đến cả AB.

Gọi T là số bộ (A,B,C) mà cả A,B cùng bay được đến C. Ta có TC162=120

Giả sử thành phố thứ i có thể bay đến được ai thành phố khác. Thì i=116ai= 72.

Khi đó: i=116Cai272(7216)2.16>120. Vô lý.

Bài 16. (Chọn đội tuyển Bình Thuận)

Trong một hội nghị có 155 đại biểu tham dự và có 2015 cặp đại biểu quen biết nhau. Chứng minh rằng có thể chọn ra 4 đại biểu để xếp lên một bàn tròn sao cho hai đại biểu ngồi cạnh nhau thì có quen biết nhau.

Lời giải

Bài này cách giải hoàn toán giống bài Bulgari MO 2006.

Bài 17. 

Trong một trường có 1001 học sinh tham gia vào một số câu lạc bộ, các câu lạc bộ hợp với nhau để tổ chức m hoạt động xã hội (một hoạt động có thể được tổ chức bởi một hoặc nhiều câu lạc bộ). Biết rằng
i) Mỗi câu lạc bộ đều có lẻ thành viên và nếu câu lạc bộ có k thành viên thì nó tổ chức k12 hoạt động xã hội;
ii) Với mỗi học sinh bất kì và một hoạt động bất kì thì có đúng một câu lạc bộ vừa tổ chức hoạt động xã hội đó và nhận học sinh đó là thành viên;
iii) Hai học sinh bất kì tham gia đúng một câu lạc bộ;

Tìm m.

Lời giải

Gọi S là số bộ (t,C,H) mà học sinh t tham gia câu lạc bộ C và câu lạc bộ C tổ chức hoạt động H. Vì với mỗi cặp tH chỉ tồn tại duy nhất một C nên S=1001 m

Nếu một câu lạc bộ có k thành viên thì nó tổ chức k12. Giả sử có n câu lạc bộ và câu lạc bộ thứ iki thành viên thì S=i=1nkiki12.
Suy ra i=1nki2ki2=1001 m.
Gọi T là số bộ (a,b,C) là hai học sinh a,b cùng tham gia câu lạc bộ C. Vi hai học sinh bất kì chỉ tham gia đúng một câu lạc bộ nên T=C10012.
Mặt khác câu lạc bộ thứ iki thành viên nên T=i=1nCki2.
Suy ra i=1nki2ki2=C10012
Vậy 10001m=C100012 nên m=500.

Bài 18. 

Một trường có n học sinh và m câu lạc bộ. Mỗi câu lạc bộ có ít nhất 2 thành viên. Nếu 2 câu lạc bộ có nhiều hơn một thành viên chung thì sô thành viên của 2 câu lạc bộ khác nhau.

a) Gọi ai là số câu lạc bộ có i thành viên. Chứng minh aiCn2Ci2;

b) Chứng minh mn1;

Lời giải

a) Ta gọi S là số bộ (x,y,C) mà hai học sinh x,y cùng tham gia CLB C có i thành viên. Trước hết ta đếm theo xy. Vi 2 câu lạc bộ có cùng hai thànhviên x,y chung thì số thành viên của 2 câu lạc bộ khác nhau nên có nhiều nhất một câu lạc bộ có i thành viên và chứa x,y.
Suy ra SCn2
Bây giờ ta đếm theo C, số câu lạc bộ có i thành viên là ai nên số cách chọn Cai. Với mỗi câu lạc bộ có i thành viên số số cách chọn x,yCi2 nên S=aiCi2 suy ra aiCi2Cn2
Vậy aiCn2Ci2.
b) Ta có
m=i=2naii=2nCn2Ci2=i=2nn(n1)i(i1)=n(n1)i=2n(1i11i)=n(n1)(11n)=(n1)2

Bài 19.

Cho 6 điểm nằm trong mặt phẳng và không có ba điểm nào thẳng hàng. Mỗi cạnh nối hai điểm được tô bởi hai màu xanh / đỏ. Hỏi có ít nhất bao nhiêu tam giác được tô cùng màu?

Lời giải

Gọi S là số bộ (A,B,C) sao cho cạnh AB,AC được tô cùng màu.

Giả sử số tam giác được tô cùng màu là n thì số tam giác được tô không cùng màu là C63n=20n

Với mỗi tam giác cùng màu số bộ (A,B,C)3.

Với mỗi tam giác không được tô cùng màu thì số bộ (A,B,C) là 1 . Vậy S=3n+20n=20+2n.

Với mỗi đỉnh C là gọi a1 là số cạnh màu đỏ nhận C làm đầu mút và a2 là số cạnh màu xanh nhận C làm đầu mút. Ta có a1+a2=5.

Ca12+Ca22C32+C22=4 nên S6.4=24.

Suy ra 20+2n24 nên n2.

Bài 20. (Ukraina TST 2013)

Cho đa giác lồi có 17 đỉnh A1A2A3A17 và với hai đỉnh Ai,Aj bất kỳ trong số các đỉnh của đa giác, ta định hướng cho đoạn thẳng nối chúng để có vectơ: AiAj hoặc AjAi. Sau khi thực hiện với mọi cặp đỉnh, gọi S là số tam giác có tổng các vectơ đặt trên 3 cạnh là 0. Tim GTNN và GTLN của S.

Lời giải

Gọi số tam giác có tổng các vector trên 3 cạnh bằng 0n.
Ta gọi S là số bộ 3 diểm (A,B,C) trong 17 đỉnh mà có hai vector AC,BC hoặc CA,CB tức là với với các vector đặt trên hai cạnh AC,BC thì C cùng là điểm đầu hoặc cùng là điểm cuối.

Với mỗi tam giác mà tổng các vector đặt trên các cạnh bằng 0 thì số bộ như trên bằng 0 .

Với mỗi tam giác mà tổng các vector đặt trên các cạnh khác 0 thì số bộ như trên bằng 2 .

Vậy S=2(C173n)=13602n

Với mỗi điểm Ai ta gọi di là số vector nhận Ai là điểm đầu và ci là số vector nhận Ai là điểm cuối.

Ta có di+ci=16Cci2+Cdi216(162)2.2=56.

Nên S56.17=952

Suy ra 13602n952n204

Bài 21. (China MO 2007).

Trong một trường THPT, có 2007 học sinh nam và 2007 học sinh nữ. Mỗi học sinh tham gia không quá 100 CLB ở trường. Biết rằng hai học sinh bất kỳ khác giới tính đều có tham gia ít nhất 1 CLB chung nào đó. Chứng minh rằng có 1 CLB mà có ít nhất 11 thành viên nam và 11 thành viên nữ.

Lời giải

Ta chứng minh bằng phản chứng, giả sử mỗi câu lạc bộ đều có nhiều nhất 10 học sinh nam hoặc nhiều nhất 10 học sinh nữ. Gọi S là số bộ (A,B,C) mà học sinh nam A và học sinh nữ B tham gia câu lạc bộ C.

Vì mỗi học sinh nam và học sinh nữ bất kì tham gia ít nhất một câu lạc bộ nên S20072

Ta chia các câu lạc bộ thành 2 trường hợp.

TH1: Câu lạc bộ có không quá 10 nam. Số học sinh nữ là 2007 và mỗi học sinh tham gia không quá một câu lạc bộ nên số cặp (B,C) trong trường hợp này không vượt quá: 2007.100 vì thế số bộ (A,B,C) không vượt quá 10.2007.100.

TH2: Câu lạc bộ có không quá 10 nữ. Số bộ (A,B,C) trong trường hợp này không quá 2007.10.100.

Suy ra: S2.2007.10.100=2000.2007

Vi vậy 200722000.2007. Vô lý.

Bài 22. (Trường Xuân 2013)

Cô giáo có tất cả X viên kẹo gồm 11 loại kẹo khác nhau. Cô chia cho các học sinh của mình mỗi người một số viên kẹo và không có học sinh nào nhận nhiều hơn một viên kẹo ở cùng một loại kẹo. Cô yêu cầu hai học sinh khác nhau bất kì so sánh các viên kẹo mình nhận được và viết số loại kẹo mà cả hai cùng có lên bảng. Biết rằng mỗi cặp bất kì đều được lên bảng đúng một lần. Gọi tổng các số được viết lên bảng là M. Xác định giá trị nhỏ nhất của M.

a) Khi X=2013

b) Khi X=2017

Lời giải

Ta đánh số các loại kẹo từ 1 đến 11 giả sử số viên kẹo loại iai. Ta có i=111ai=X. Ta thấy M=i=111Cai2

a) Khi X=2013 ta có 112013

Ta thấy M2013(201311)2.11=183183 Đẳng thức xảy ra khi ai=201311=183

b) Khi X=2017 ta có 2017=11.183+4 nên

M7C1832+4C1842=183915

Bài 23. (IMO 1998)

Trong một cuộc thi có a thí sinh và b giám khảo, trong đó b3 là một số nguyên lẻ. Mỗi giám khảo đánh giá một thí sinh là “đạt” hoặc “trượt”. Giả sử k là một số sao cho, với 2 giám khảo bất kì, đánh giá của họ là như nhau với nhiều nhất k thí sinh. Chứng minh rằng

kab12b

Lời giải

Gọi T là số bộ ({g1,g2},s) trong đó giám khảo g1g2 có cùng đánh giá với thí sinh s.

Vi hai giám khảo bất kì có cùng đánh giá với nhiều nhất k thí sinh nên TkCb2

Với một thí sinh s bất kì, giả sử có p giám khảo đánh giá “đạt” và q giám khảo đánh giá “trượt”. Ta có p+q=b và số cặp giám khảo có cùng đánh giá với s là:

Cp2+Cq2=p2+q2pq2(b1)24+(b+1)24b2=(b1)24

Bài 24. (China TST 1992)

Có 16 học sinh tham gia một cuộc thi có n câu hỏi và mỗi câu hỏi có 4 lựa chọn. Biết rằng 2 học sinh bất kì có không quá 1 câu trả lời chung cho tất cả các câu hỏi. Tìm giá trị lớn nhất của n.

Lời giải

Gọi S là số bộ ({h1,h2},c) mà 2 học sinh h1h2 có cùng câu trả lời với câu hỏi c.

Vi 2 học sinh có không có quá một câu trả lời chung cho các các câu hỏi nên SC162=120

Với mỗi câu hỏi c có bốn phương án trả lời, gọi số thí sinh chọn phương án thứ iai. Ta có 14ai=16

Khi đó số cặp thí sinh {h1,h2} mà có cùng câu trả lời cho câu hỏi c là:
Ca12+Ca22+Ca32+Ca4216(164)2.4=24
Ta có: S24n.
Suy ra 24n120 hay n5.

Bài 25.

Một CLB có n thành viên và họ đã tham gia vào 12 buổi chuyên đề, mỗi buổi có 24 thành viên tham gia. Biết rằng hai thành viên bất kỳ tham gia chung không quá một buổi.

a) Tìm giá trị nhỏ nhất của n;

b) Câu hỏi tương tự nếu có 10 buổi chuyên đề và mỗi buổi có 7 thành viên tham gia.

Lời giải

a) Trước hết ta chuyển đổi giả thiết của bài toán “hai thành viên bất kỳ tham gia chung không quá một buổi” thành “hai buổi bất kì có không quá một thành viên chung”.

Ta đánh số các thành viên từ 1 đến n. Gọi ai số buổi chuyên đề mà thành viên thứ i tham gia thì i=1nai=12.24=288

Gọi T là số bộ (a,B,C) mà thành viên a tham gia vào cả 2 buổi chuyên đề B,C. Vi hai buổi bất kì có không quá một thành viên chung nên TC122=66. Ta có T=i=1nCai2288(288n)2n

Suy ra: 66288(288n)2n. Dẫn đến n198.

Ta thấy 288198=1 nên các số ai chỉ nhận giá trị bằng 1 hoặc 2 . Giả sử có k số ai bằng 1 khi đó T=k suy ra k66

Suy ra: 288=2k+(nk)=n+kn+66. Vậy n=222 là giá trị nhỏ nhất.

Khi đó ta có 66 số ai bằng 2 và 156 số ai bằng 1.

b) i=1nai=10.7=70

Gọi T là số bộ (a,B,C) mà thành viên a tham gia vào cả 2 buổi chuyên đề B,C. Vi hai buổi bất kì có không quá một thành viên chung nên TC102=45.

Ta có T=i=1nCai270(70n)2n

Suy ra: 4570(70n)2n. Dẫn dến n31

Ta thấy 7031=2 nên các số ai chỉ nhận giá trị bằng 2 hoặc 3.

Giả sử có k số ai bằng 3 khi đó T=nk+3k=n+2k suy ra n+2k45.

Suy ra: 70=3k+2(nk)=2n+k=3n2+n2+k3n2+452. Vậy n32.

Vậy giá trị nhỏ nhất của n là 32 . Khi đó ta có k=6 số ai bằng 3 và 26 số ai bằng 2 .

Bài 26.

Trên mặt phẳng cho tập hợp A gồm 66 điểm phân biệt và tập hợp B gồm 16 đường thẳng phân biệt. Gọi m là số bộ (a,b) sao cho aA,b B, ab. Chứng minh rằng m159.

Lời giải

Để m đạt giá trị lớn nhất thì tất cả điểm của A phải thuộc vào các đường thẳng của B. Ta đặt tên các điểm là A1,,A66. Gọi số đường thẳng trong tập B đi qua điểm Aiai. Ta có i=116=m.

Gọi T là số bộ (X,di,dj)XA là giao điểm của didjdi,djB. Rõ ràng TC162=8.15=120
Mặt khác T=i=166Cai2m(m66)2.66.
Ta có: 120m(m66)2.66. Suy ra m163.
Ta có m662 nên ta dự đoán giá trị nhỏ nhất của m ra khi ai nhận các giá trị là 2 hoặc 3.
Giả sử có k giá trị ai bằng 3 thì m=3k+2(66k)=132+k.
T=3k+(66k)=66+2k=2(k+132)198=2m198.
Suy ra: 2m198120 nên m159.
Đẳng thức xảy ra khi có 27 số ai nhận giá trị bằng 3 và 39 số ai nhận giá trị bằng 2 .

Nhận xét 2.5. Bài toán này thực tế giống bài toán trên vì có một tính chất mà người giải bài toán phải tự nhận thấy là “hai đường thẳng phân biệt có không quá một điểm chung”.

Bài 26.

Trên mặt phẳng cho tập hợp A gồm 66 điểm phân biệt và tập hợp B gồm 16 đường thẳng phân biệt. Gọi m là số bộ (a,b) sao cho aA,b B, ab. Chứng minh rằng m159.

Lời giải

Để m đạt giá trị lớn nhất thì tất cả điểm của A phải thuộc vào các đường thẳng của B. Ta đặt tên các điểm là A1,,A66. Gọi số đường thẳng trong tập B đi qua điểm Aiai. Ta có i=116=m.

Gọi T là số bộ (X,di,dj)XA là giao điểm của didjdi,djB. Rõ ràng TC162=8.15=120
Mặt khác T=i=166Cai2m(m66)2.66.
Ta có: 120m(m66)2.66. Suy ra m163.
Ta có m662 nên ta dự đoán giá trị nhỏ nhất của m ra khi ai nhận các giá trị là 2 hoặc 3.
Giả sử có k giá trị ai bằng 3 thì m=3k+2(66k)=132+k.
T=3k+(66k)=66+2k=2(k+132)198=2m198.
Suy ra: 2m198120 nên m159.
Đẳng thức xảy ra khi có 27 số ai nhận giá trị bằng 3 và 39 số ai nhận giá trị bằng 2 .

Bài 27. (IMO Shortlist 1995)

Một cuộc họp có 12k người và mỗi người bắt tay với đúng 3k+6 người còn lại. Biết rằng với mọi cách chọn cặp hai người, số người bắt tay với cả hai là như nhau. Tính số người trong cuộc họp.

Lời giải

Gọi S là số bộ (a,b,c)a bắt tay với cả b,c.

Nếu ta đếm theo a thì S=12kC3k+62. Với 2 người bất kì, thì số người bắt tay với cả 2 người không đổi, ta đặt bằng m.

Nếu ta đếm theo (b,c) thì S=mC12k2.

Suy ra m=3(k+2)(3k+5)12k1=33k2+11k+1012k1Z.

Giải phương trình nghiệm nguyên ta được k=3m=6.

Vậy cuộc họp có 36 người.

Bài 28.

Cho số nguyên tố p. Trên bàn cờ hình vuông có cạnh p2+p+1, tìm số lớn nhất các ô có thể tô màu sao cho không tồn tại hình chữ nhật có 4 đỉnh cùng màu và các cạnh song song với các cạnh của hình chữ nhật.

Lời giải

Giả sử ta tô màu n ô.

Gọi S là số bộ (ci,cj,hk) trong đó các cột cicj và giao với hàng hk tại hai ô được tô màu.

Để không xuất hiện hình chữ nhật nào có bốn đỉnh được tô màu thì với mỗi hai cột cicj thì có nhiều nhất một hàng hk nên SCp2+p+12.

Với mỗi hàng, ta giả sử số ô được tô màu trên hàng đó là ai thì

i=1p2+p+aai=n

Khi đó S=i=1p2+p+1Cai2n(np2p1)2(p2+p+1)

Suy ra Cp2+p+12n(np2p1)2(p2+p+1)

Từ đó ta thu được n(p+1)(p2+p+1).

Đẳng thức xảy ra khi mỗi hàng có p+1 ô được tô màu và trên 2 cột bất kì chỉ có 2 ô nằm trên cùng một hàng được tô màu.

Việc chỉ ra một cách một cách tô màu thỏa mãn đẳng thức xin dành lại cho người đọc chuyên đề này.

3/ Ma trận liên thuộc

Bài 29. (Iran 1999)

Giả sử C1,C2,,Cn(n2) là các đường tròn bán kính 1 . Không có 2 đường tròn nào tiếp xúc. Bất kì một đường tròn nào cũng cắt ít nhất một đường tròn khác. Giả sử S là tập hợp các điểm thuộc ít nhất 2 đường tròn (tập các giao điểm). Chứng minh rằng |S|n.

Lời giải

Gọi tập các đường tròn là T Giả sử |S|=s

Với mỗi cặp (d,Ci)dS và đường tròn Ci đi qua d.

Ta gọi x(d,Ci) là số đường tròn đi qua điểm d.

y(d,Ci) là số điểm mà đường tròn Ci đi qua.

Với điểm d giả sử có một đường tròn Cj nữa đi qua điểm d thì đường tròn CjCi cắt nhau tại một điểm d nữa khác d.

Suy ra x(d,Ci)y(d,Cj).

Vì vậy ta có: s=dS,CTdC1x(d,Ci)dS,CT,CC1y(d,Ci)=n

Bài 30.

Cho S1,S2,,Sm là các tập con phân biệt của tập 1,2,,n sao cho |SiSj|=1 với mọi ij. Chứng minh rằng mn.

Lời giải

Ta phản chứng giả sử m>n.

Ta thấy các tập Si đều phải khác rỗng và ta chỉ cần xét với m2. Lời giải này sẽ được chúng tôi trình bày thông qua Ma trận liên thuộc. Trước hết ta lập một bảng ô vuông gồm m dòng, dòng thứ i sẽ ứng với tập Sin cột, cột thứ j sẽ ứng với phần tử j trong tập {1,2,,n}. Ô ở vị trí giao của cột thứ j và dòng thứ i sẽ được điền vào giá trị aij. Trong đó

aij={1 nếu jSi0 nếu jSi

Bây giờ ta xét trường hợp aij=0. Nếu trên cột j có một số 1 giả sử là akj=1 thì |SkSi|=1 nên trên dòng i cũng có một số 1 . Và ta thấy rằng quy tắc này là một đơn ánh. Do đó, ta gọi Ri là tổng các số trên dòng thứ iCj là tổng các số trên cột thứ j thì Cj<Ri.

Suy ra mCj>nRiCjmCj<RinRi.

Gọi M là tổng các số trên bảng. Thì

$$

\begin{gathered}

M=\sum_{j=1}^{n} C_{j}=\sum_{j=1}^{n}\left(m-C_{j}\right) \frac{C_{j}}{m-C_{j}}=\sum_{j=1}^{n}\left(\sum_{i=1}^{m}\left(1-a_{i j}\right)\right) \frac{C_{j}}{m-C_{j}}= \

=\sum_{j=1}^{n} \sum_{i=1}^{m} \frac{\left(1-a_{i j}\right) C_{j}}{m-C_{j}}<\sum_{j=1}^{n} \sum_{i=1}^{m} \frac{\left(1-a_{i j}\right) R_{i}}{n-R_{i}}=\sum_{i=1}^{m} \frac{R_{i}}{n-R_{i}}\left(\sum_{j=1}^{n}\left(1-a_{i j}\right)\right) \

=\sum_{i=1}^{m} \frac{R_{i}}{n-R_{i}}\left(n-R_{i}\right)=\sum_{i=1}^{m} R_{i}=M

\end{gathered}

$$

Vô lý nên mn

4/ Lựa chọn giữa đếm bằng hai cách và nguyên lý Dirichlet

Bài 31. (Chọn ĐT Lương Thế Vinh, Đồng Nai)

Trong một thư viện người ta quan sát thấy được:

i) Mỗi ngày có 5 người đọc sách.

ii) Hai ngày bất kì thì số người đọc sách là 9.

Hãy tính xem trong 1 tháng có bao nhiêu người đến đọc sách. Biết tháng đó có 30 ngày.

Lời giải

Lời giải. Giả sử có n người đến đọc sách. Gọi tập hợp những người tham gia đọc sách ngày thứ iAi.

Giả sử A1={b1,,b5}. Mỗi phần tử của A1 này phải thuộc vào các tập từ A2,,A30. Gọi b1 là người tham gia nhiều ngày đọc sách nhất thì theo nguyên lý Drichlet thì b16
Giả sử b1 tham gia đọc sách vào cách ngày Ai1,,Aim với m6 Giả Ak không chứa b1. Do |B|=5 nên tồn tại hai tập AiAjAijB= AihB. Mặt khác |AijAih|=1 nên AijAih=a1. Vô lý.
Suy ra a1Ak1k30
Vậy số người tham gia đọc sách là n=30.4+1=121.

Bài 32. (Chọn đội tuyển Việt Nam 2014)

Trong một kỳ thi có 100 thí sinh và 24 vị giám khảo. Mỗi thí sinh được hỏi bởi đúng 10 giám khảo. Chứng minh rằng có 7 giám khảo mà mỗi thí sinh đều được hỏi bởi ít nhất một trong số họ.

Lời giải

Ta chứng minh bằng phản chứng. Giả sử với 7 giám khảo bất kỳ luôn tồn tại một thí sinh không được hỏi bởi cả 7 giám khảo đó. Gọi S là số bộ ({a1,,a7},h)h không được hỏi bởi cả 7 giám thị a1,,a7.

Ta có SC247.

Với mỗi thí sinh thì có 14 giám khảo không hỏi thí sinh đó. Nên S=100C147. Suy ra C247100C147. Điều này vô lý.

Tất nhiên bài tập này có thể giải bằng cách sử dụng nguyên lý Drichlet.

Bài tập tự luyện

Bài tập 33 (IMO 2001). Hai mươi mốt cô gái và 21 chàng trai đã tham gia vào một cuộc thi toán học. Cho biết rằng

i) mỗi thí sinh giải quyết nhiều nhất là sáu bài toán, và

ii) với mỗi cặp của một cô gái và một chàng trai, có ít nhất một bài đã được giải quyết bởi cả cô gái và chàng trai.

Chứng minh rằng có một bài được giải bởi ít nhất là ba cô gái và ít nhất là ba chàng trai.

Bài tập 34 (IMO 2005). Trong một cuộc thi toán học có 6 bài toán được đưa ra cho các thí sinh. Mỗi cặp bài tập được giải bởi nhiều hơn 25 số thí sinh. Không có thí sinh nào giải được cả 6 bài. Chứng minh rằng có ít nhất 2 thí sinh mà mỗi người giải được đúng 5 bài.

Bài tập 35 (IMO 1987). Cho pn(k) là số hoán vị của tập 1,2,,n(n1) có đúng k điể̉ cố định. Chứng minh rằng

k=1nkpn(k)=n!

Bài tập 36. Cho S là một tập với |S|=n. Giả S1,,Sm là các tập con của S sao cho SiSjij. Chứng minh rằng mCn[n2]

Bài tập 37. Cho các tập hợp S1,,Sm, mỗi tập có 3 phần tử. Và S=S1 S2Sm. Thỏa mãn:

i) |SiSj|=1ij;

ii) x,yS,xy thì tồn tại một tập Six,ySi.

Chứng minh rằng: |S|=7 và họ S1,,Sm tồn tại.

Bài tập 38 (China TST 1990). Cho 7 điểm trên mặt phẳng và ta vẽ các đường tròn qua đúng 4 điểm nào đó trong số chúng. Tính số đường tròn lớn nhất có thể có.

Các bài toán tổ hợp trong kì thi Junior Bankan – P1

Lê Phúc Lữ – Phạm Khánh Vĩnh

(Bài viết trích từ Tập san Star Education – Số 5)

Bài 1. (JBMO 1998)
Hỏi có tồn tại hay không 16 số có ba chữ số tạo thành từ ba chữ số phân biệt cho trước mà không có hai số nào có cùng số dư khi chia cho 16?

Lời giải

Câu trả lời là phủ định.
Giả sử tồn tại các số thỏa mãn đề bài thì vì chúng có số dư đôi một khác nhau nên sẽ có đầy đủ các số dư 0,1,2,3,,15. Điều này có nghĩa là trong đó, có 8 số chẵn và 8 số lẻ. Suy ra, ba chữ số a,b,c để tạo thành các số đã cho không thể có cùng tính chẵn lẻ. Ta có hai trường hợp:

  • Trong các số a,b,c, có hai số chẵn là a,b và số c lẻ. Ta có tất cả 9 số lẻ tạo thành từ các chữ số này là:
    aac,abc,acc,bac,bbc,bcc,cac,cbc,ccc.
    Gọi a1,a2,,a9 là số có hai chữ số tạo thành bằng cách xóa đi chữ số cuối từ dãy trên.
    Rõ ràng số aikajk với ij khác số dư với nhau theo modulo 16 nếu như hiệu của chúng không chia hết cho 16, suy ra aiaj không chia hết cho 8. Tuy nhiên, ta lại có đến 9 số nên điều này không thể xảy theo nguyên lý chuồng bồ câu.
  • Trong các số a,b,c, có hai số lẻ là a,b và số c chẵn: cũng dẫn đến mâu thuẫn tương tự.

Vậy không tồn tại các số thỏa mãn đề bài.

Bài 2: (JBMO 2000)

Trong một giải thi đấu tennis, số lượng nam gấp đôi số nữ. Mỗi cặp vận động viên thi đấu với nhau đúng một lần và không có trận hòa, chỉ có thắng – thua. Tỷ số giữa trận thắng của nữ và của nam là 75. Hỏi có bao nhiêu vận động viên trong giải thi đấu?

 

Lời giải

Gọi số nam là 2n, số nữ là n và tổng số vận động viên là 3n. Tổng số trận đấu là

3n(3n1)2. \medskip

 

Theo giả thiết thì số trận thắng bởi nam là 5123n(3n1)2=5n(3n1)8.

Số trận đấu giữa các nam là 2n(2n1)2=n(2n1) và rõ ràng số trận này không vượt quá số trận thắng của các nam.

Suy ra 5n(3n1)8n(2n1)n3. Mặt khác, 5n(3n1) phải chia hết cho 8 nên n=3. Do đó, số vận động viên của giải đấu là 9.

Bài 3: (JBMO 2006)

Xét bảng ô vuông kích thước 2n×2n với n nguyên dương. Người ta xóa đi một số ô của bảng theo quy tắc sau đây:

 

  •  Nếu 1in thì ở dòng thứ i, xóa 2(i1) ô ở giữa.
  •  Nếu n+1i2n thì ở dòng thứ i, xóa đi 2(2ni) ô ở giữa.

Hỏi có thể phủ được bảng bởi tối đa bao nhiêu hình chữ nhật kích thước 2×11×2 (không nhất thiết phải phủ kín toàn bộ) sao cho không có hai hình chữ nhật nào chồng lên nhau?

 

Lời giải

Với mọi bảng kích thước 2n×2n, tổng số ô bị xóa đi là 2×2×(1+2+3++n1)=2n(n1).

Bảng sẽ còn lại (2n)22n(n1)=2n(n+1) ô, tức là phủ được tối đa n(n+1) ô vuông.

Không có mô tả.

 

Với n=1,2,3,4, ta có thể kiểm tra trực tiếp được rằng kết quả lần lượt sẽ là 2,6,12,20 bởi khi đó ta có thể phủ kín toàn bộ bảng. Còn với n4, ta xét hai trường hợp:

 

  • Nếu n lẻ, khi đó ta chia bảng 2n×2n đã cho thành 4 hình vuông nhỏ thì rõ ràng, mỗi hình sẽ có n(n+1)2 ô còn trống. Tiếp theo, ta tô màu theo dạng bàn cờ cho bảng này (ô ở góc thì tô đen), ta sẽ có tất cả (n+1)24 ô đen và n214 ô trắng. Rõ ràng mỗi hình chữ nhật khi đặt lên bảng sẽ chứa một ô đen và một ô trắng nên số cặp ô trắng – đen tối đa trong hình vuông con là n214, và tương ứng sẽ có tối đa 4n214=n21 hình chữ nhật 1×2,2×1 phủ được trên bảng.

Ngoài ra, giữa các hình vuông con cạnh nhau, ta còn có hai ô màu đen cạnh nhau nên ta có thể lát thêm vào đó tổng cộng 4 hình chữ nhật nữa, tổng cộng là n21+4=n2+3.

  •  Nếu n chẵn, bằng cách tương tự trên, ta phủ được hình bởi tối đa n2+4 ô.

Tóm lại,

  •  Với n=1,2,3,4, đáp số lần lượt là 2,6,12,20.
  •  Với n>4n lẻ thì đáp số là n2+3.
  •  Với n>4n chẵn thì đáp số là n2+4.

Bài 4: (JBMO 2008)

Một bảng 4×4 được chia thành 16 ô vuông con và tất cả đều được tô màu trắng. Hai ô vuông được gọi là kề nhau nếu chúng có chung một cạnh. Một thao tác hợp lệ bao gồm việc chọn một ô vuông và đổi màu tất cả các ô kề với nó (kể cả nó): trắng sang đen, đen sang trắng. Sau n thao tác, tất cả ô vuông của bảng chuyển sang màu đen. Tìm tất cả các giá trị có thể có của n.

 

Lời giải

Ta thấy mỗi lần đổi màu không quá 5 ô nên số lần đổi màu phải ít nhất là 4.Hơn nữa, ta cũng có thể đổi màu tất cả sang đen như hình bên dưới, các ô được đánh dấu là các ô được chọn trong các thao tác.

Không có mô tả.

Mặt khác, với n chẵn lớn hơn 4, ta có thể chọn một trong các điểm trên hai lần và khi đó, màu của chúng sẽ đổi từ trắng sang đen, đen sang trắng, tức là không bị ảnh hưởng. Điều này có nghĩa là ta cũng có thể chuyển tất cả các ô sang màu đen như trường hợp n=4. \medskip

Cuối cùng, ta sẽ chứng minh rằng n lẻ không thỏa mãn đề bài.

Không có mô tả.

Tô màu xanh các ô vuông như hình vẽ. Ta thấy rằng ở mỗi lần thao tác thì có số lẻ ô xanh bị thay đổi (1 hoặc 3) nên sau mỗi lần thao tác, số lượng ô trắng – đen trong vùng màu xanh bị thay đổi một số đồng dư 2 modulo 4.

Ban đầu chênh lệch đó là 10 và nếu muốn đổi tất cả sang màu đen thì chênh lệch đó là 10; tức là thay đổi 20, chia hết cho 4. Điều này không thể xảy ra nên n lẻ không thỏa mãn đề bài.

Vậy các giá trị n cần tìm là n chẵn và n4.

Bài 5: (JBMO 2008)

Một bảng 4×4 được chia thành 16 ô vuông con và tất cả đều được tô màu trắng. Hai ô vuông được gọi là kề nhau nếu chúng có chung một cạnh. Một thao tác hợp lệ bao gồm việc chọn một ô vuông và đổi màu tất cả các ô kề với nó (kể cả nó): trắng sang đen, đen sang trắng. Sau n thao tác, tất cả ô vuông của bảng chuyển sang màu đen. Tìm tất cả các giá trị có thể có của n.

 

Lời giải

Ta thấy mỗi lần đổi màu không quá 5 ô nên số lần đổi màu phải ít nhất là 4.Hơn nữa, ta cũng có thể đổi màu tất cả sang đen như hình bên dưới, các ô được đánh dấu là các ô được chọn trong các thao tác.

Mặt khác, với n chẵn lớn hơn 4, ta có thể chọn một trong các điểm trên hai lần và khi đó, màu của chúng sẽ đổi từ trắng sang đen, đen sang trắng, tức là không bị ảnh hưởng. Điều này có nghĩa là ta cũng có thể chuyển tất cả các ô sang màu đen như trường hợp n=4. \medskip

Cuối cùng, ta sẽ chứng minh rằng n lẻ không thỏa mãn đề bài.

Tô màu xanh các ô vuông như hình vẽ. Ta thấy rằng ở mỗi lần thao tác thì có số lẻ ô xanh bị thay đổi (1 hoặc 3) nên sau mỗi lần thao tác, số lượng ô trắng – đen trong vùng màu xanh bị thay đổi một số đồng dư 2 modulo 4.

Ban đầu chênh lệch đó là 10 và nếu muốn đổi tất cả sang màu đen thì chênh lệch đó là 10; tức là thay đổi 20, chia hết cho 4. Điều này không thể xảy ra nên n lẻ không thỏa mãn đề bài.

Vậy các giá trị n cần tìm là n chẵn và n4.

Bài 6:

(JBMO 2010)

Một hình chữ nhật 9×7 được lát bởi hai loại gạch như hình bên dưới: chữ L và hình vuông.

 

Không có mô tả.

 

Tìm tất cả các giá trị có thể có của số lượng các viên gạch hình vuông đã được dùng.

 

Lời giải

Câu trả lời là 0 hoặc 3.

Gọi x là số viên gạch chữ Ly là số viên gạch hình vuông 2×2. Đánh dấu chéo 20 hình vuông của hình chữ nhật như sơ đồ bên dưới.

Không có mô tả.

Rõ ràng mỗi viên gạch sẽ chứa không quá một dấu chéo. Suy ra x+y20.

Ngoài ra ta cũng có 3x+4y=63.

Từ đó suy ra y3y chia hết cho 3, dựa theo điều kiện thứ hai.

Do đó y=0 hoặc y=3. Dưới đây là các cách lát thỏa mãn điều kiện đó.

Không có mô tả.

Bài 7: (JBMO 2013)

Cho n là một số nguyên dương. Có hai người chơi là Alice và Bob chơi một trò chơi như sau:

 

  •  Alice chọn n số thực, không nhất thiết phân biệt.
  •  Alice viết tất cả các tổng theo cặp của tất cả các số lên giấy và đưa nó cho Bob (rõ ràng có tất cả n(n1)2 cặp và không nhất thiết phân biệt).
  •  Bob sẽ thắng nếu như có thể tìm lại được n số ban đầu được chọn bởi Alice.

Hỏi Bob có thể có cách chắc chắn thắng hay không với

 

  •  n=5?
  •  n=6?
  •  n=8?

 

 

Lời giải

1) Câu trả lời là khẳng định.

 

Giả sử các số Alice đã chọn là abcde. Rõ ràng mỗi số xuất hiện trong các tổng đúng 4 lần nên bằng cách cộng tất cả 10 tổng và chia hết quả cho 4, Bod sẽ thu được

a+b+c+d+e.

Trừ đi tổng lớn nhất và nhỏ nhất, Bob sẽ thu được số lớn thứ ba là c. Tiếp tục trừ c vào tổng lớn thứ nhì, chính là c+e thì Bob thu được e. Trừ e vào tổng lớn nhất, Bob thu được d. Bằng cách tương tự, Bob sẽ tìm ra được các giá trị a,b. \medskip

 

2) Câu trả lời là khẳng định. Giả sử các số Alice đã chọn là abcdef. Tương tự trên, ta cũng tính được tổng S các số của bộ. Trừ S cho tổng lớn nhất và nhỏ nhất, ta thu được tổng c+d. \medskip

 

Trừ S cho tổng lớn nhì và tổng nhỏ nhất, ta được c+e. Trừ S cho tổng lớn nhất và tổng nhỏ nhì, ta được b+d.

Từ đây suy ra a+c=S(b+d)(e+f), trong đó ta biết e+f vì đó là tổng lớn nhất.

Lúc bấy giờ, Bob đã tìm được ba tổng a+b,a+c,b+c nên sẽ tính được T=a+b+c và dễ dàng tìm được a,b,c. Tương tự, Bob có thể tìm được d,e,f. \medskip

 

3) Câu trả lời là phủ định.

Ta thấy rằng có hai bộ tám số là 1,5,7,9,12,14,16,202,4,6,10,11,15,17,19 đều cho cùng 28 tổng theo đôi một giống nhau nên chắc chắn rằng Bob không thể biết được bộ mà Alice đã chọn.

 

Bài 8: (JBMO 2014)

Với mỗi số nguyên dương n, hai người A,B chơi một trò chơi như sau: Cho một đống có s viên sỏi và hai người chơi thay phiên nhau chơi, A đi trước. Ở mỗi lượt, người chơi được bốc hoặc 1 viên sỏi, hoặc một số p nguyên tố các viên sỏi, hoặc một bội của n các viên sỏi. Người bốc được viên cuối cùng là chiến thắng. Giả sử hai người đều chơi với chiến thuật tối ưu, hỏi có bao nhiêu giá trị s để người B có chiến thuật thắng?

 

Lời giải

Ta gọi các giá trị s để cho người A có chiến thuật thắng là vị trí thắng và các vị trí còn lại là vị trí thua. Ta cần tìm số lượng vị trí thua.

Giả sử có k vị trí thua thuộc tập hợp X={s1,s2,s3,,sk}.

Trước hết, ta thấy rằng mỗi bội của n là vị trí thắng (vì người A có thể lấy tất cả các viên sỏi ở ngay lần đi đầu tiên). Khi đó, nếu có sisj(modn)si>sj thì ở lượt đi đầu tiên, A bốc sisj viên sỏi (vì số này chia hết cho n). Nhưng lúc đó, còn lại sj viên sỏi và đây là vị trí thua của B nên sẽ là vị trí thắng của A, mâu thuẫn.

Do đó, tất cả các số trong X đều không đồng dư với nhau theo modulo n hay k=|X|n1. \medskip

 

Ta sẽ chứng minh rằng k=n1. Thật vậy,

Để có được điều đó, ta sẽ chỉ ra rằng ở mỗi lớp thặng dư khác 0 của n, luôn có một vị trí thua bằng phản chứng. Giả sử rằng tồn tại r{1,2,3,,n1} sao cho mn+r là vị trí thắng với mỗi số nguyên dương m. Gọi u là vị trị thua lớn nhất (nếu k>0) hoặc 0 (nếu k=0).

Đặt s là bội chung nhỏ nhất của tất cả các số nguyên dương từ 2 đến u+n+1. Khi đó, tất cả các số s+2,s+3,,s+u+n+1 đều là hợp số. \medskip

 

Xét số nguyên dương m thỏa mãn

s+u+2mn+rs+u+n+1.

Để mn+r là vị trí thắng thì phải có số tự nhiên p1, là số nguyên tố hoặc là bội của n sao cho hiệu mn+rp sẽ là vị trí thua, là 0 hoặc là một số nhỏ hơn hoặc bằng u. Chú ý rằng

s+2mn+rupmn+rs+u+n+1

nên p phải là hợp số, chứng tỏ p chỉ có thể là bội của n (theo giả thiết của đề bài). \medskip

 

Đặt p=qn thì mn+rq=(mq)n+r cũng sẽ là một vị trí thắng khác; tuy nhiên, theo nguyên lý trò chơi thì không thể đi từ vị trí thằng này đến vị trí thắng khác được. Điều mâu thuẫn này cho thấy không thể xảy ra trường hợp toàn bộ các số dạng mn+r là vị trí thắng. \medskip

 

Từ đây ta suy ra rằng có ít nhất n1 vị trí thua nên từ các điều trên, ta thấy có đúng n1 vị trí thua hay có n1 vị trí mà người B có chiến lược để thắng.

Bài 9: (JBMO 2015)

Một khối chữ L bao gồm ba khối vuông ghép như một trong các hình bên dưới:

 

 

Cho trước một bảng 5×5 bao gồm 25 ô vuông đơn vị, một số nguyên dương k25 và một số lượng tùy ý các khối chữ L nêu trên. Hai người chơi A,B cùng tham gia một trò chơi như sau: bắt đầu bởi A, hai người sẽ lần lượt đánh dấu các ô vuông của bảng cho đến khi nào tổng số ô được đánh dấu bởi họ là k. \medskip

 

Ta gọi một cách đặt các khối chữ L trên các ô vuông đơn vị còn lại chưa được đánh dấu là tốt nếu như nó không bị chồng lên nhau, đồng thời mỗi khối đặt lên đúng ba ô vuông như một trong các hình ở trên. B sẽ thắng nếu như với mọi cách đặt tốt ở trên, luôn luôn tồn tại ít nhất ba ô vuông đơn vị chưa được đánh dấu trên bảng. \medskip

 

Xác định giá trị k nhỏ nhất (nếu có tồn tại) để B có chiến lược thắng.

 

Lời giải

Ta sẽ chứng minh rằng A sẽ thắng nếu k=1,2,3B thắng nếu k=4. Suy ra giá trị nhỏ nhất của k4. \medskip

 

1) Nếu k=1 thì người chơi A sẽ đánh dấu ô ở góc trên bên trái và đặt các khối như bên dưới

 

Không có mô tả.

 

Khi đó, rõ ràng A thắng. \medskip

 

2) Nếu k=2 thì vẫn tương tự trên, A đánh dấu vào ô ở góc trên bên trái. Khi đó, cho dù B đánh dấu ô nào đi nữa thì A cũng sẽ có cách đặt tương tự như trên, thiếu đi nhiều nhất là 2 ô thuộc cùng khối vuông chữ L với ô mà B chọn. Điều này chứng tỏ A vẫn thắng. \medskip

 

3) Nếu k=3 thì cũng tương tự, ở lượt sau, A đánh dấu vào ô cùng khối chữ L với ô mà B đã đánh dấu. Khi đó, A vẫn thắng. \medskip

 

4) Với k=4, ta sẽ chứng minh rằng B sẽ luôn có chiến lược thắng cho dù A đi thế nào đi nữa. Rõ ràng còn lại 21 ô nên A phải chọn cách đánh dấu sao cho có thể đặt được toàn bộ 7 khối vuông chữ L (vì nếu không thì sẽ còn lại ít nhất 3 ô chưa được đặt). \medskip

 

Giả sử trong lượt đầu tiên, A không chọn ô nào trong hàng cuối (vì nếu có thì ta xoay ngược bảng lại và lập luận tiếp một cách tương tự). Khi đó, B sẽ chọn ô số 1 như bên dưới.

Không có mô tả.

 

  •  Nếu trong lượt tiếp theo, A không chọn ô nào trong các ô 2,3,4 thì B chọn ô số 3. Khi đó, rõ ràng ô số 2 sẽ không thể đặt lên bởi bất cứ khối chữ L nào và B chiến thắng.
  •  Nếu trong lượt tiếp theo, A chọn ô số 2 thì B chọn ô số 5, dẫn đến ô số 3 không thể đặt lên bởi khối L nào.
  •  Nếu trong lượt tiếp theo, A chọn một trong hai ô 3 hoặc 4 thì B chọn ô còn lại, kết quả tương tự trên, ô số 2 cũng sẽ không thể tiếp cận.

Vậy nói tóm lại, k=4 là giá trị nhỏ nhất cần phải tìm.

Bài 10: (JBMO 2016)

Một bảng kích thước 5×5 được gọi là “tốt” nếu như mỗi ô của nó có chứa một đúng bốn giá trị phân biệt, và mỗi giá trị xuất hiện đúng một lần trong tất cả các bảng con 2×2 của bảng đã cho. Tổng tất cả các số có trên bảng được gọi là “giá” của bảng. Với mỗi bộ bốn số thực, ta có thể xây dựng tất cả các bảng tốt và tính giá của nó. Tính số giá phân biệt lớn nhất có thể có.

 

Lời giải

Ta sẽ chứng minh rằng số giá phân biệt lớn nhất là 60. Ta có nhận xét sau: \medskip

 

Nhận xét:  Trong mỗi bảng tốt, mỗi hàng chứa đúng hai số trong các số hoặc mỗi cột chứa đúng hai số trong các số. \medskip

 

Thật vậy, ta thấy mỗi hàng của bảng đều chứa ít nhất hai số (vì nếu chứa toàn bộ là một số thì mâu thuẫn với giả thiết). Khi đó, nếu toàn bộ các hàng đều chứa hai số thì nhận xét đúng. \medskip

 

Giả sử ngược lại là có hàng R chứa ít nhất ba số trong bốn số của bảng là x,y,z,t. Khi đó, các số đó phải có nằm ở vị trí liên tiếp nào đó trên hàng, giả sử là x,y,z liên tiếp. Theo giả thiết thì trong mỗi bảng 2×2, ta đều có đủ bốn giá trị nên trong hàng phía trên và phía dưới của R phải chứa z,t,x theo đúng thứ tự đó, và tương tự là x,y,z. Ta có bảng như bên dưới

 

* & x & y & z & * \

* & z & t & x & * \

* & x & y & z & * \

* & z & t & x & * \

* & x & y & z & * \

 

Điền thêm các ô còn lại, dễ thấy rằng các cột đều chứa đúng hai số. Nhận xét được chứng minh. \medskip

 

Không mất tính tổng quát, ta có thể giả sử mỗi hàng của bảng đều có đúng hai số (nếu không thì có thể xoay bảng lại). Nếu không xét hàng đầu tiên và cột đầu tiên, ta sẽ có bảng 4×4 mà trong đó, mỗi số trong x,y,z,t đều xuất hiện 4 lần nên tổng các số trong bảng này là 4(x+y+z+t).

Do đó, ta chỉ cần tính xem có bao nhiêu cách khác nhau để đặt các số lên hàng đầu tiên R1 và cột đầu tiên C1. Gọi a,b,c,d là số lần xuất hiện của các số x,y,z,t thì khi đó, tổng tất cả các số của bảng sẽ là

4(x+y+z+t)+xa+yb+zc+td.

Nếu hàng 135 chứa các số x,y với x ở vị trí đầu tiên của hàng 1 thì các hàng 24 sẽ chứa các số z,t (theo giả sử ở trên). Khi đó, ta có

a+b=7a3,b2,

c+d=2cd. \medskip

 

Khi đó (a,b)=(5,2),(4,3) tương ứng với (c,d)=(2,0),(1,1). Suy ra (a,b,c,d) sẽ nhận các bộ là (5,2,2,0),(5,2,1,1),(4,3,2,0),(4,3,1,1).

Tổng số hoán vị của các bộ là 4!2!+4!2!+4!+4!2!=60.

Bằng cách chọn x=103,y=102,z=10,t=1 thì dễ thấy rằng các tổng tương ứng với mỗi hoán vị của bộ số trên đều phân biệt, nghĩa là giá của các bảng đều phân biệt. Vậy số lượng giá tối đa là 60.

Dưới đây là một số bài toán để bạn đọc tự rèn luyện thêm:

Bài 11. (JBMO 2019) Cho bảng ô vuông 5×100 được chia thành 500 ô vuông con đơn vị, trong đó có n được tô đen và còn lại tô trắng. Hai ô vuông kề nhau nếu chúng có cạnh chung. Biết rằng mỗi ô vuông đơn vị sẽ có tối đa hai ô vuông đen kề với nó. Tìm giá trị lớn nhất của n.

Bài 12. (JBMO 2020) Alice và Bob chơi một trò chơi như sau: Alice chọn một tập hợp A=1,2,,n với n2. Sau đó, bắt đầu bằng Bob, họ sẽ thay phiên chọn một số trong tập A sao cho: đầu tiên Bob chọn bất kỳ số nào, sau đó, các số được chọn phải khác các số đã chọn và hơn kém đúng 1 đơn vị so với số nào đó đã chọn. Trò chơi kết thúc khi tất cả các số trong A đã được chọn. Alice thắng nếu tổng các số bạn ấy chọn được là hợp số. Ngược lại thì Bob thắng. Hỏi ai là người có chiến lược thắng?

Chỉnh hợp – Hoán vị – Tổ hợp

Chỉnh hợp

Mỗi cách sắp xếp k phần tử (phân biệt) vào n vị trí phân biệt (nk) được gọi là một chỉnh hợp chập k của n.

Tính chất. Số chỉnh hợp chập k của nAnk=(n!)(nk)!

Hoán vị. 

Mỗi chỉnh hợp chập n của n được gọi là một hoán vị, hay mỗi cách sắp xếp n phần tử vào n vị trí được gọi là một hoán vị của n phần tử. Số hoán vị của n phần tử là Pn=n!.


Định nghĩa khác. Cho tập A=1,2,,n. Mỗi song ánh từ A vào A được gọi là một hoán vị.

Ví dụ 1. Có 8 bạn nam và 2 bạn nữ được xếp thành một hàng dài. Hỏi có bao nhiêu cách xếp thỏa:

a) Xếp bất kì.
b) 8 bạn nam kề nhau,2 bạn nữ kề nhau.
c) Các bạn nam giữa hai bạn nữ.

Ví dụ 2. Có 8 bạn nam và 4 bạn nữ. Có bao nhiêu cách sắp xếp các bạn này thành một hàng sao cho không có hai bạn nữ nào đứng kề nhau.

Ví dụ 3.  Cho tập A=0,1,2,3,4,5. Từ A có thể lập được bao nhiêu số

a) Là số chẵn có 4 chữ số khác nhau.
b) Là số lẻ có 5 chữ số khác nhau và chia hết cho 3.

 

Tổ hợp. Cho tập hợp An phần tử. Một tập hợp con có k phần tử của A được gọi là một tổ hợp chập k của n phần tử.

Tính chất. Số tổ hợp có chập k của n là: [C_n^k = \dfrac{A_n^k}{k!} = \dfrac{n!}{(n-k)! k!}]

Ví dụ 4. Đội văn nghệ của trường gồm 4 bạn học sinh lớp 10, 5 học sinh lớp 11, 4 học sinh lớp 12.

a) Có bao nhiêu cách chọn ra hai bạn hát song ca?
b) Có bao nhiêu cách chọn ra 3 bạn hát tam ca mà mỗi khối có một học sinh?
c) Có bao nhiêu cách chọn ra một đội múa gồm 5 bạn trong đó có ít nhất 2 học sinh lớp 11.

Ví dụ 5. Cho tập A=1,2,3,4,5,B=a,b,c,d,e,, C=x,y,z.

a) Có bao nhiêu song ánh từ A vào B.
b) Có bao nhiêu ánh xạ từ A vào C? Có bao nhiêu đơn ánh từ C vào A.
c) Có bao nhiêu đơn ánh từ CA sao cho f(x)+f(y)+f(z) là số chẵn.

Bài tập rèn luyện

Bài 1. Cho tập A=0,1,2,3,4,5,6,a,b,c,d

a) Có bao nhiêu hoán vị của A.
b) Có bao nhiêu hoán vị của A mà các chữ số đứng kề nhau.
c) Có bao nhiêu hoán vị của A mà không có chữ cái nào đứng kề nhau?

Bài 2. Cho tập A=0,1,2,3,4,5,6

a)Từ A có thể lập được bao nhiêu số có 5 chữ số khác nhau.
b) Có bao nhiêu hoán vị của A mà hai chữ số lẻ không đứng kề nhau.
c) Từ A có thể lập được bao nhiêu số có 4 chữ số mà chữ số đứng sau lớn hơn chữ số đứng liền trước.
d) Từ A có thể lập được bao nhiêu số có 3 chữ số chia hết cho 3.

Bài 3. Xếp m bạn nam và n bạn nữ thành 1 hàng, với m,nN. Hỏi có bao nhiêu cách xếp nếu:

a) Xếp tùy ý;
b) Không có bạn nam nào đứng cạnh nhau (mn+1);
c) n bạn nữ đứng liền kề nhau;
d) Một bạn nam A và một bạn nữ B đứng cạnh nhau.

Bài 4. Tính: 11!+22!+33!++nn!,nN.

Bài 5. Tính: 1(1+1)!+2(2+1)!++n(n+1)! với nN.

Bài 6. Cho n,rN với rn. Chứng minh rằng:

a) Anr=nAn1r1;
b) Anr=(nr+1)Anr1;
c) Anr=nnrAnr1, với r<n;
d) An+1r=Anr+rAnr1;
e) An+1r=r!+r(Anr1+An1r1++Arr1).

Bài 7. Một nhóm có 15 hóc sinh, trong đó có 5 bạn nữ. Hỏi có bao nhiêu cách chọn 9 học sinh sao cho có đúng 3 học sinh nữ:

a) để thành lập một hội đồng.
b) để thành lập một hội đồng với 9 vị trí khác nhau.

Bài 8. Có 10 cái ghế được xếp thành một hàng. 7 học sinh được xếp vào 7 cái ghế sao cho không có 2 học sinh nào ngồi chung một cái ghế. Hỏi có bao nhiêu cách xếp sao cho không có 2 cái ghế trống nào liền nhau.

Bài 9. Có 8 cái hộp được xếp thành hàng. Hỏi có bao nhiêu cách đặt 5 viên bi khác nhau vào các hộp nếu mỗi hộp chứa nhiều nhất 1 viên bi và không có hai hộp không chứa bi nào đứng cạnh nhau?

Bài 10. Xếp một nhóm có 20 học sinh, trong đó có 3 bạn nữ là: A, B, C và 4 bạn nam: X,Y,Z,T thành 2 hàng, mỗi hàng 10 học sinh. Hỏi có bao nhiêu cách xếp sao cho 3 bạn nữ luôn ở hàng trước, còn 4 bạn nam ở hàng phía sau.

Bài 11. Hỏi có bao nhiêu cách xếp 7 bạn nam và 2 bạn nữa thành một hàng sao cho các bạn gái cách nhau bởi đúng 3 bạn nam?

Bài 12. Tìm số (m+n)-nhị phân là một dãy chữ số với m số 0 và n số 1 sao cho không có 2 số 1 nào đứng kề nhau, khi nm+1.

Bài 13. Lớp A có 10 bạn nữ và 15 bạn nam và lớp B có 4 nữ và 10 nam. Một hội đồng gồm 7 thành viên được chọn từ 2 lớp đó. Hỏi có bao nhiêu cách chọn các thành viên sao cho có đúng 4 bạn của lớp B và có đúng 5 bạn nam.

Bài 14. Trong mỗi trường hợp sau, tìm số tuyến đường ngắn nhất từ O đến P trong sơ đồ được cho dưới đây:
a) Tuyến đường phải đi qua A.
b) Tuyến đường phải qua đoạn AB.
c) Tuyến đường phải đi qua AC.
d) Đoạn đường AB bị đóng.

Bài 15. Tìm số cách chọn một nhóm gồm 2k người từ n cặp đôi, với k,nN2kn, trong mỗi trường hợp sau đây:

a) Có k cặp đôi trong nhóm đó.
b) Không có cặp đôi nào trong nhóm đó.
c) Có ít nhất một cặp đôi được chọn trong nhóm.

d) Có đúng 2 cặp đôi được chọn trong nhóm đó.

Bài 16. Cho một đa giác có 10 đỉnh.

a) Có bao nhiêu đường chéo.
b) Có bao nhiêu tam giác có 3 đỉnh là 3 đỉnh thuộc đa giác.
c) Có bao nhiêu tam giác có đúng 1 cạnh trùng với cạnh của đa giác.
d) Có bao nhiêu tam giác không có cạnh nào trùng với cạnh của đa giác.
e) Biết rằng không có 3 đường chéo nào đồng quy. Tìm số giao điểm của các đường chéo.

Bài 17. Cho đa giác đều có 100 cạnh. Hỏi có bao nhiêu hình chữ nhật tạo ra từ các đỉnh của đa giác trên.

Bài 18. Cho A là tập hợp các số nguyên dương từ 1 đến 100. Hỏi có bao nhiêu tập con có 3 phần tử của A thỏa:

a) Tổng các số chia hết cho 3
b) Tổng các số chia hết cho 4.

Bài 19. Chung kết cuộc thi tiếng hát học đường có 3 bạn vào chung kết, mỗi bạn hát 2 bài khác nhau. Hỏi có bao nhiêu cách sắp xếp chương trình sao cho không có ai hát liên tiếp.

Bài 20. Có bao nhiêu cách chọn ra 3 số từ tập A=1,2,,100 sao cho một số là trung bình cộng của hai số còn lại.

Các bài toán tổ hợp trên dãy số

CÁC BÀI TOÁN TỔ HỢP TRÊN DÃY SỐ

Thầy Lê Phúc Lữ 

(Lớp Cao học Khoa học tự nhiên TP.HCM)

Trong bài viết nhỏ này, chúng ta sẽ cùng xét khía cạnh tổ hợp của dãy số nguyên; khi cần đếm số lượng dãy thỏa mãn một điều kiện cho trước nào đó. Các phương pháp thường gặp: truy hồi, xuống thang, cực hạn, phản chứng, …

1. Các bài toán chọn lọc

Bài tập 1.1: Tìm tất cả các bộ số nguyên dương x1, x2, x3, , x2017 sao cho có thể đặt chúng lên vòng tròn theo thứ tự đó mà 6 số liên tiếp bất kỳ đều có thể chia thành hai nhóm 3 có tổng bằng nhau.

Giải

Dùng phương pháp xuống thang.

Ta có xi+xi+1+xi+2+xi+3+xi+4+xi+50(mod2) với mọi i=1,2,3,,2017 nên xixi+6 với mọi i.

(6,2017)=1 nên suy ra tất cả các số có cùng tính chẵn lẻ. Ta xét phép biến đổi dãy số sau:

  • Nếu tất cả các số cùng chẵn thì thay bằng yi=xi2.
  • Nếu tất cả các số cùng lẻ thì thay bằng yi=xi+12.

Dễ thấy dãy mới cũng thỏa và tổng S=i=12017ai sẽ giảm ngặt nếu có một số nào đó trong dãy khác 1; suy ra quá trình biến đổi sẽ dừng lại khi tất cả đều là 1. Vì ta thu được một dãy toàn là 1 nên dãy ban đầu có tất cả các số hạng bằng nhau.

Nhận xét: Bài toán trên có thể thay việc chia 2 nhóm thành 3,4,5, nhóm và vẫn giải được bằng cách tương tự. Ta xét các bài tương tự sau:

Bài tập 1.2 (APMO 2017): Bộ năm số nguyên là tốt nếu có thể đặt chúng là a,b,c,d,e để ab+cd+e=29. Tìm tất cả các bộ 2017 số sao cho 5 số liên tiếp bất kỳ trong chúng đều tốt.

Ở bài toán này, điểm khó là không biết các số đã cho có dương hay không; vì thể, đại lượng tổng ở trên không xét tiếp tục được.

Tuy nhiên, cách áp dụng vẫn tương tự như sau:

  • Trừ tất cả các số của bộ cho 29, ta thu được điều kiện tốt trở thành ab+cd+e=0.
  • Tất cả các số đã cho cùng tính chẵn lẻ, và chính xác là cùng chẵn.
  • Xét đại lượng S=i=12017|ai2| thì thông qua phép chia 2, tổng này giảm ngặt. Từ đó suy ra tất cả các số này phải là 0 và tất cả ban đầu phải là 29.

Bài tập 1.3 (VMO 2014): Tìm tất cả các bộ số 2014 số hữu tỷ không âm sao cho nếu bỏ đi bất kỳ số nào trong chúng thì các số còn lại có thể được chia thành 3 nhóm rời nhau, mỗi nhóm có 671 số sao cho tích các số trong mỗi nhóm là bằng nhau.

Bài này khó hơn vì: số hữu tỷ chứ không nguyên, tích chứ không phải tổng, … Ta lần lượt giải quyết điều đó như sau:

  • Quy đồng mẫu để đưa về số nguyên.
  • Xét số mũ của 1 ước nguyên tố để đưa về tổng.
  • Chú ý thêm trường hợp số 0 (nếu có 1 số thì phải có ít nhất 4 số).

Bài tập 1.4: Cho dãy số nguyên dương (an) thỏa mãn:

i) Gồm các số phân biệt nhau.

ii) Với mọi n thì ann.

iii) a1=5, a2=4, a3=3.

a) Chứng minh rằng tồn tại n>2017 sao cho ann+1?

b) Giả sử an=n+2 với mọi n>2017, hỏi có tất cả bao nhiêu dãy số như thế?

Giải

a) Bài toán có thể giải quyết dễ dàng bằng phản chứng và Dirichlet. Thật vậy, nếu an=n+1 với mọi n>2017 thì các số hạng a4a2017 sẽ nhận các giá trị trong tập hợp 62018. Khi đó, sẽ có hai số hạng bằng nhau, không thỏa.

b) Nếu đã có an=n+2 với mọi n>2017 thì các số hạng a4a2017 sẽ nhận các giá trị trong tập hợp 62019. Nhận xét:

  • a2017{2017,2018,2019} nên có 3 cách chọn.
  • a2016{2016,2017,2018,2019} nhưng vì a2017 đã lấy một số nên cũng còn 3 cách chọn.
  • Tương tự, đến a6 vẫn có 3 cách chọn. Còn lại a52 cách chọn và a41 cách chọn.

Theo nguyên lý nhân, ta có 232012 dãy thỏa mãn.

Bài tập 1.5: Xét lục giác ABCDEF có độ dài cạnh là 1 được điền các số như hình vẽ

Một con ếch xuất phát từ A và nhảy đến các đỉnh sao cho mỗi bước nhảy đều có độ dài nguyên. Hành trình của ếch là dãy các tên đỉnh mà ếch đã nhảy qua; và hai hành trình được coi là khác nhau nếu ở một lần thứ k nào đó, đỉnh mà ếch nhảy đến ở hai hành trình là khác nhau.

Gọi m là số hành trình ếch nhảy sao cho tổng các số mà nó nhảy qua là 2017. Chứng minh rằng m không phải là số chính phương.

Giải

Ta thấy ACEBDF là hai tam giác đều có cạnh là 3 nên mỗi lần, ếch sẽ nhảy từ tam giác đều này đến tam giác đều kia.

Chia nhóm:

  • I=(A,C,E) tương ứng với các số (0,0,1).
  • II=(B,D,F) tương ứng với (1,1,2).

Ta thấy {x+y|xI,yII}={1,1,1,1,2,2,2,2,3} chứng tỏ tổng các số trên hai bước nhảy liên tiếp của ếch sẽ nhận giá trị là 4 số 1, 4 số 21 số 3. Nếu gọi sn là số hành trình của ếch có tổng là n thông qua chẵn bước thì

sn=4sn1+4sn2+sn3.

Một cách tương tự, gọi tn là số hành trình của ếch có tổng là n thông qua lẻ bước thì công thức truy hồi vẫn thế (chỉ khác ở các số hạng đầu).

Vì vậy nên nếu gọi un=sn+tn là số hành trình của ếch có tổng là n thì

un=4un1+4un2+un3 với n3.

Ta có u0=1,u1=6,u2=28 và từ công thức truy hồi thì m=u2017u12(mod4) nên m không thể là số chính phương, ta có đpcm.

Nhận xét: Bài toán có thể giải bằng cách gọi 6 dãy truy hồi an, bn, cn, dn, en, fn chỉ số hành trình của ếch có tổng là n và kết thúc tại A,B,C,D,E,F. Tuy nhiên, cách tiếp cận đó khá phức tạp, đòi hỏi phải khai thác nhiều các liên hệ giữa các đường đi.

Một bài toán tương tự:

Bài tập 1.6 (Ả Rập TST 2017): Người ta đặt các số 1,2,3,4 trên vòng tròn theo thứ tự đó. Một con kiến xuất phát từ số 1 và ở mỗi bước, nó sẽ bò qua số bên cạnh. Hỏi con kiến có bao nhiêu cách bò sao cho tổng tất cả các số mà nó bò qua (kể cả số ban đầu) bằng 21?

Tương tự bài trên, ta cũng tìm được hệ thức truy hồi là sn=sn3+2sn5+sn7. Từ đó tính được s21=167.

Bài tập 1.7: Đếm số dãy số nguyên dương (a1, a2, , a12) thỏa mãn các điều kiện sau:

a) 1a1a2a122017

b) aii2(mod12).

Giải

Theo giả thiết, ta có

a1a5a7a111 (mod12)

a2a4a8a104 (mod12)

a3a99 (mod12)

a6a120 (mod12)

Đặt ai=12bi+ri với i=1,2,3,,12ri là số dư tương ứng đã chỉ ra ở trên.

Do tính không giảm của dãy nên ta phải có

0b1b2b3<b4<b5<b6b7b8b9<b10<b11<b12168.

Từ đó suy ra

0b1<b2+1<b3+2<b4+2<b5+2<b6+2b7+3b8+4b9+5

<b10+5<b11+5<b12+5173

Do các số liệt kê ở trên đều phân biệt và thuộc [0;173] nên số cách chọn một bộ như thế là C17412. Đó cũng chính là số dãy cần tìm.

Nhận xét: Điều kiện thứ hai có thể thay bằng một hàm số tùy ý theo i chứ không nhất thiết phải là i2, cách giải vẫn tương tự như trên.

Bài tập 1.8: Hỏi có bao nhiêu hoán vị a1, a2, , a2017 của 2017 số nguyên dương đầu tiên thỏa mãn đồng thời các điều kiện sau:

i) ai+1ai1 với mọi i=1,2,3,,2016.

ii) Có đúng một chỉ số i với 1i2017 sao cho ai=i?

Giải

Trước hết, ta sẽ chứng minh nhận xét rằng số hoán vị của n số nguyên dương đầu tiên thỏa mãn điều kiện i), gọi là hoán vị đẹp, sẽ là 2n1. Thật vậy,

  • Đầu tiên, ta đặt số 1 vào hoán vị.
  • Số 2 có thể xếp trước hoặc sau số 1, có 2 cách.
  • Số 3 có thể xếp vào đầu dãy hoặc ngay sau số 2 đã xếp trước đó, có 2 cách.
  • Số 4 có thể xếp vào đầu dãy hoặc ngay sau số 3 đã xếp trước đó, cũng có 2 cách. Cứ như thế cho đến n.

Do đó, có tất cả 2n1 cách xếp, tương ứng vời 2n1 hoán vị.

Tiếp theo, giả sử ta có ai=i.

Khi đó ai+1ai+1=i+1, nhưng không thể có ai+1=i+1 (do chỉ có 1 chỉ số thỏa mãn ii) nên ai+1i, mà ai=i nên ai+1i1. Tiếp theo, ai+2ai+1+1i nên ai+2i1.

Do đó, các số từ ai+1 đến a2017 nhận giá trị không vượt quá i1.

Lập luận tương tự, các số từ a1 đến ai1 phải nhận giá trị không nhỏ hơn i+1.

Do đó, hai đoạn hoán vị phía trước và phía sau ai phải có độ dài bằng nhau, tức là a1009=1009 là số ở giữa.

Rõ ràng các hoán vị phía trước và phía sau 1009 đều phải là hoán vị đẹp và được sắp xếp độc lập với nhau.

Vậy số hoán vị cần tìm là (21007)2=22014.

Nhận xét: Nếu đề đổi số 2017 thành 2018 thì sẽ tồn tại hai chỉ số i như trên và chúng sẽ cách đều hai đầu 12018. Khi đó, đoạn ở giữa cũng sẽ cố định, tức là có i<j để

ak=k với mọi k=i,i+1,,ji+j=2019.

Phần trước i và phần sau j sẽ đổi chỗ cho nhau với số cách xếp là (2i1)2.

Bài tập 1.9: Cho dãy các số nguyên dương (un) thỏa mãn điều kiện

0um+numun1 với mọi m,nZ+.

Chứng minh rằng tồn tại aR+ sao cho 1un[an]1 với mọi n=1,2,3,,2017.

Giải

Ta đưa điều cần chứng minh về

unn<a<un+1n.

Đến đây, gọi

m=min{un+1n|n=1,2,3,,2017}

M=max{unn|n=1,2,3,,2017.}

Cần chỉ ra m>M rồi chọn số a nằm giữa (m,M) là xong. Gọi p,q lần lượt là các chỉ số nhỏ nhất để có dấu bằng xảy ra ở các đánh giá trên. Khi đó

up+1=pmuq=Mq.

Ngoài ra, uk+1>km,k<puk<kq,k<q.

  • Nếu p=q thì hiển nhiên đúng.
  • Nếu p>q, ta đặt p=q+k thì k<p nên uk+1>km, vì upuq+uk (theo giả thiết) nên pm1>Mq+km1m>M.
  • Nếu p<q thì cũng chứng minh tương tự với chú ý rằng uqup+uk+1.

Nhận xét: Nếu đề bài đổi giả thiết thành 0um+numun2,

ta sẽ cần đến hai số a,b sao mới thỏa mãn được kết luận (vì khoảng chênh lệch của các số hạng rộng hơn một tí), cụ thể là tồn tại a,b>0 để

1un[an][bn]1.

Ở bài toán trên, ta còn chứng minh được một kết quả mạnh hơn là tồn tại a để un=[an] với mọi n. Một bài toán tương tự trong đề trường Đông miền Trung:

Bài tập 1.10: Cho hàm số f:RR thỏa mãn |f(x+y)f(x)f(y)|1,x,yR. Chứng minh rằng tồn tại hàm cộng tính g:RR thỏa mãn |f(x)g(x)|1,x.

Đây có thể nói là một phiên bản trên R của bài toán trên (thay vì xét trên N).

Tiếp theo, ta xét lớp các bài toán sử dụng một định lý thú vị trong dãy số, số học. Trước hết, ta xét định lý Beatty với nội dung như sau:

Cho hai số vô tỷ dương α,β. Xét hai dãy số:

  • [α],[2α],[3α], tạo thành dãy A.
  • [β],[2β],[3β], tạo thành dãy B.

Khi đó 1α+1β=1 khi và chỉ khi A,B là phân hoạch của Z+.

Chứng minh

Định lý này có thể chứng minh bằng cách sử dụng các BĐT về phần nguyên. Dưới đây là cách chứng minh cho chiều đảo:

Với mỗi số nguyên dương k, gọi m,n là các số nguyên dương thỏa mãn

[mα]k<[(m+1)α] và [nβ]k<[(n+1)β].

Đặt A={[iα],1im}B={[jβ],1jn} thì |A|=m,|B|=nA,B là phân hoạch của tập hợp {1,2,3,,k} theo định nghĩa của đề bài.

Do đó m+n=k. Theo bất đẳng thức phần nguyên thì mα1<k<(m+1)α nên mk+1<1α<m+1k.

Tương tự nk+1<1β<n+1k.

Suy ra m+nk+1<1α+1β<m+n+2k hay kk+1<1α+1β<k+2k.

Cho k+, ta thu được 1α+1β=1.

Bài tập 1.11: Hai dung dịch A,B có đặc điểm: số đo thể tích của 1 kg A bằng số đo khối lượng của 1 lít B. Ngoài ra, p lít A nặng bằng q lít B với p,q nguyên tố khác nhau. Mỗi dung dịch được chia cho vào các bình nhỏ giống nhau, cùng chứa 1 lít và vỏ nặng 1 kg. Chứng minh rằng có đúng một cách ghép các bình cùng loại (A hoặc B) lại với nhau mà khối lượng của chúng thuộc khoảng (2017;2018).

Giải

Gọi x,y lần lượt là khối lượng riêng của các dung dịch thì 1x=1y,px=qy nên x=qp,y=pq.

Khối lượng mỗi bình là α=1+qp,β=1+pq. Dễ thấy 1α+1β=1, thỏa mãn định lý Beatty.

Suy ra hai dãy [mα],[nβ] là phân hoạch của số nguyên dương nên ta có đpcm.

Bài tập 1.12 (APMO 2006): Với mỗi số nguyên dương n, gọi an, bn lần lượt là số cách viết 10n trong hệ nhị phân, ngũ phân. Chứng minh rằng (an),(bn) là phân hoạch của Z+{1}.

Giải

Để giải bài này, chú ý rằng: số chữ số của M trong hệ p phân là [logpM]+1.

Ngoài ra, α=log210,β=log510 thỏa mãn điều kiện của định lý Beatty.

Từ đó, ta có một nhận xét thú vị rằng: tổng số chữ số của 2n5n trong hệ thập phân là n+1.

Bài tập 1.13 (VN TST 2000): Cho số nguyên dương k. Dãy số (un) xác định bởi: u1=1un+1 là số nguyên dương nhỏ nhất không thuộc tập hợp

{u1, u2, , un, u1+k, u2+2k, , un+nk}.

Chứng minh rằng tồn tại α vô tỷ dương sao cho un=[nα] với mọi n.

Giải

Để giải bài toán này, ta xét đa thức P(x)=x2+(k2)xk với k là số nguyên dương đã cho thì P(x) có hai nghiệm phân biệt trái dấu. Hơn nữa, ΔP(x)=(k2)2+4k=k2+4, không thể là số chính phương với bất kì số k nguyên dương nào nên hai nghiệm này đều là số vô tỉ. Ta thấy P(1)=1+(k2)k=1<0,P(2)=4+2(k2)k=k>0 nên nghiệm dương của phương trình P(x)=0 thuộc khoảng (1,2). Gọi nghiệm đó là a.

Đặt b=a+k thì a,b đều vô tỉ và ab=a(a+k)=a2+ak=2a+k=a+b nên 1a+1b=1.

Xét f(n)=[na],g(n)=[nb]=f(n)+kn với n là số nguyên dương.

Ta sẽ chứng minh rằng xn=f(n) bằng quy nạp. Thật vậy,

– Với n=1, khẳng định hiển nhiên đúng vì 1<a<2.

– Giả sử xn=f(n) với mọi n=1,2,3,,m. Ta sẽ chứng minh rằng xm+1=f(xm+1).

Ta có f(i)=xi,g(i)=f(i)+ik=xi+ik với mọi i=1,2,3,,m nên ta có tập hợp

H={x1,x2,,xm,x1+k,x2+2k,,xm+mk}

={f(1),f(2),,f(m),g(1),g(2),,g(m)}

Rõ ràng f(m+1)Hg(n)>f(n) với mọi n, f(n) là hàm số đồng biến trên N nên ta thấy rằng f(m+1) chính là số tự nhiên nhỏ nhất không thuộc H. Theo định nghĩa dãy số (xn) đã cho thì ta có xm+1=f(m+1).

Do đó, khẳng định cũng đúng với m+1. Theo nguyên lí quy nạp, ta có đpcm. Vậy số tự nhiên cần tìm chính là a là nghiệm dương của phương trình x2+(k2)xk=0.

Nhận xét: Đây là một kết quả có từ 1959. Ta có thể phân tích cách tiếp cận như sau:

Xuất phát từ việc α=2,β=2+2 thỏa mãn điều kiện Beatty. Ta có hai dãy với công thức

an=[n2], bn=an+2n là phân hoạch của Z+.

Từ đó, để giấu dãy bn đi, ta chỉ cần xét an+2n.

Để ý a1=1, a2=2, a3=4, b1=3, b2=6, b3=10 nên a4 có thể định nghĩa là số nguyên dương nhỏ nhất không thuộc {a1, a2, a3, a1+2, a2+4, a3+6}. Đó chính là cơ sở để có bài toán trên.

Bài tập 1.14 (Dãy Wythoff): Cho chuỗi S1=1. Chuỗi Sn được tạo thành từ chuỗi Sn1 bằng cách thay 10101. Các chuỗi S1, S2, S3,  được ghép liên tiếp lại với nhau thành một chuỗi vô hạn L. Gọi an là vị trí của số 1 thứ n trong chuỗi L. Chứng minh rằng tồn tại α vô tỷ dương sao cho an=[nα],n.

Ở đây, ta có nhận xét rằng số 0 thứ n được sinh ra bởi số 1 thứ n nên nếu gọi kn là số các số 0 đứng trước số 1 thứ nbn là vị trí của số 0 thứ n, ta sẽ có an=n+knbn=2n+kn nên bn=an+n.

Chú ý rằng (an), (bn) chính là phân hoạch của Z+ nên dễ dàng tìm được α là nghiệm của 1α+1α+1=1 hay α chính là tỷ số vàng.

Bài tập 1.15: Cho n là số nguyên dương, hỏi có bao nhiêu dãy số a1, a2, , a2n sao cho

i) ai{1,1} với i=1,2,3,,2n.

ii) |i=2k+12lai|2 với 0k<ln?

Giải

Gọi S là tập hợp các dãy thỏa mãn đề bài và đặt |S|=sn. Gọi T là tập hợp tất cả các tổng các ai lấy từ chỉ số lẻ bất kỳ đến 2n. Theo giả thiết thì T{±2,±1,0}, tuy nhiên, tất cả các tổng trong T đều có chẵn số hạng mà mỗi số hạng đều là ±1 nên tất cả phải đều chẵn. Suy ra T{±2,0}.

Nếu trong T chứa cả 2 lẫn 2 thì giả sử k=2i+12nak=2k=2j+12nak=2 với i<j , khi đó

4=k=2i+12nakk=2j+12nak=k=2i+12jak, mâu thuẫn.

Ứng với (a1,a2,,a2n)S, ta có phân loại sau:

  • Tất cả các tổng trong T đều là 0, đặt số lượng dãy có tính chất này là an.
  • Trong T có chứa số 2, đặt số lượng dãy có tính chất này là bn.
  • Trong T có chứa số 2, đặt số lượng dãy có tính chất này là cn.

Từ đó, ta dễ dàng chứng minh được hệ thức truy hồi

an+1=2an

bn+1=an+2bn+cn

cn+1=an+bn+2cn

Chú ý rằng an=2nan+bn+cn=sn. Cộng hai công thức cuối lại, ta có

bn+1+cn+1=2an+3(bn+cn)sn+12n+1=2n+1+3(sn2n) hay

sn+1=3sn+2nsn+1+2n+1=3(sn+2n).

Với n=1, ta có 4 dãy là (1,1),(1,1),(1,1),(1,1) nên s1=4.

Từ đẳng thức trên, ta có sn+2n=3n1(s1+21)=23n nên sn=23n2n.

Nhận xét: Bài toán thoạt nhìn có vẻ quen thuộc nhưng thật không đơn giản. Điều kiện đề cho là giá trị tuyệt đối của tất cả các tổng con từ vị trí lẻ đến vị trí chẵn bất kỳ đều không vượt quá 2 buộc ta phải có đánh giá thích hợp mới có thể truy hồi được.

2. Bài tập áp dụng

Bài 1 (TP.HCM 2018): Hỏi có bao nhiêu hoán vị (a1, a2, , a164) của 164 số nguyên dương đầu tiên sao cho aiiaii (mod41) với mọi i=1,2,,164?

Bài 2: (Bài toán phát kẹo) Cô giáo có 10 loại kẹo (mỗi loại có nhiều viên) và cần phát cho 30 học sinh của lớp (một em nhận không quá 1 viên/loại), giả sử rằng các em này có học lực đôi một khác nhau. Hỏi cô giáo có bao nhiêu cách phát kẹo, biết rằng nếu học sinh A giỏi hơn B thì B có kẹo gì là A có kẹo đó (tính cả trường hợp không em nào nhận được kẹo)?

Bài 3: (Bài toán con nhện) Một con nhện có 8 cái chân, 8 cặp vớ – giày khác nhau (vớ chỉ dùng chung với chiếc giày tương ứng). Con nhện có bao nhiêu thứ tự mang vớ và giày để sao cho trên cùng một chân, giày phải được mang vào sau vớ?

Phương pháp ánh xạ trong các bài toán tổ hợp

Bài viết dựa vào bài giảng của NCS. Vương Trung Dũng (trường PTNK-ĐHQG) trong lớp chuyên đề 10 toán tại Star Education.

 

Ánh xạ là một khái niệm khó và quan trọng trong toán học, có vai trò trong hầu hết các lĩnh vực toán học. Trong bài giảng này ta xét ứng dụng của ánh xạ trong các bài toán tổ hợp.

Ánh xạ và một số tính chất

Định nghĩa. Cho hai tập hợp XY khác rỗng. Một ánh xạ f từ tập X đến tập Y là một quy tắc đặt tương ứng mỗi phần tử x của X với một và chỉ một phần tử y của Y, kí hiệu là y=f(x).

Kí hiệu f:XY.

f(x)=y.

Các khái niệm: Cho ánh xạ f:XY.

  • y=f(x) được gọi là ảnh của x.
  • f(X)={f(x)|xX} tập ảnh của f.
  • yY thì f1(y)={xX|f(x)=y} được gọi là tạo ảnh của y.

Đơn ánh, toàn ánh, song ánh

  1. Ánh xạ f:XY được gọi là đơn ánh nếu với a,bXab thì f(a)f(b). Nói một cách khác ánh xạ f là một đơn ánh nếu và chỉ nếu với a,bXf(a)=f(b) thì suy ra a=b.
  2. Ánh xạ f:XY được gọi là toàn ánh nếu với mỗi phần tử yY đều tồn tại một phần tử xX sao cho f(x)=y. Như vậy f là toàn ánh nếu và chỉ nếu f(X)=Y.
  3. Ánh xạ f:XY được gọi là song ánh giữa XY nếu và chỉ nếu nó vừa là đơn ánh và vừa là toàn ánh. Như vậy f là song ánh nếu với mỗi yY tồn tại duy nhất một phần tử xX sao cho y=f(x).

Ánh xạ và tập hợp

Cho A=1,2,,n. X là tập khác rỗng. Nếu có một song ánh từ tập X đến A thì ta nói Xn phần tử và kí hiệu |X|=n.

Nếu không tồn tại song ánh thì ta nói X có vô hạn phần tử.

  • Nếu tồn tại một song ánh từ X vào tập các số tự nhiên, ta nói X có lực lượng đếm được, ngược lại thì ta nó X có lực lượng không đếm được.
  • Các tập số tự nhiên, số nguyên và hữu tỷ là các tập có lực lượng đếm được.

Định lý Cho AB là hai tập hợp hữu hạn.

  • Nếu có một đơn ánh f:XY thì |X||Y|.
  • Nếu có một toàn ánh f:XY thì |X||Y|.
  • Nếu có một song ánh f:XY thì |X|=|Y|.

Ánh xạ và các bài toán đếm, đẳng thức tổ hợp.

Ví dụ 1. Cho tập Xn=1,2,,n, gọi P(Xn) là tập các tập con của Xn, và Sn là tập các dãy nhị phân có độ dài n. Tìm một song ánh từ P(Xn) vào Sn, suy ra số tập con của Xn.

Gợi ý

Định nghĩa một ánh xạ f:P(Xn)Sn như sau:
Với mỗi SP(Xn) (tức là SXn) ta đặt f(S)=y1y2yn
trong đó
yi={1,yiS0,yiS.
Ví dụ , nếu X={1;2;3;4;5},S1={4},S2={2;3;5} thì f(S1)=00010,f(S2)=01101,f()=00000,f(X)=11111 .
Dễ dàng kiểm tra đây là một song ánh từ P(X) vào Y.
Do đó theo nguyên lý song ánh ta có |P(X)|=|Y|=2n.

Ví dụ 2. Hãy tính trung bình cộng của tất cả các số N gồm 2014 chữ số thỏa mãn N chia hết cho 9 và các chữ số của N được lập từ X=1,2,,8

Gợi ý

Gọi M là tập các số thỏa yêu cầu đề bài.

Ta xây dựng một ánh xạ đi từ M đến M như sau: Với mỗi N=a1a2a2014M dặt f(N)=b1,b2,,b2014 với bi=9ai với mọi i=1,2,,2014. Vì N+f(N)=999 (2014 số 9) chia hết cho 9 và N chia hết cho 9 nên suy ra f(N) cũng chia hết cho 9. Do đó f là một ánh xạ đi từ M vào M. Hơn nữa dễ thấy f là một song ánh. Từ đó suy ra 2NMN=NM(N+f(N))=|M|.999. Vậy trung bình cộng của các số trong M là 999:2.

Ví dụ 3. Cho tập S gồm tất cả các số nguyên dương trong đoạn [1,2,,2002]. Gọi T là tập hợp tất cả các tập con khác rỗng của S. Với mỗi X thuộc T ký hiệu m(X) là trung bình cộng các phần tử thuộc X. Tính m=XTm(X)|T|.

Gợi ý

Xây dựng song ánh f:TT như sau: với mọi XT đặt tương ứng f(X)={2003x:xX}.\
Khi đó m(X)+m(f(X))=2003. Do đó 2m(X)=(m(X)+m(f(X)))=|T|.2003m=m(X)|T|=20032

Ví dụ 4.  Cho X=1,2,,n. Có bao nhiêu tập con k phần tử của X sao cho trong mỗi tập con không chứa 2 số nguyên liên tiếp.

Gợi ý

Gọi A là tập tất cả các tập con k phần tử của X mà trong mỗi tập không chứa 2 số nguyên liên tiếp và B là tập tất cả các tập con của tập Y={1,2,,n(k1)}. Ta xây dựng song ánh từ A đến B như sau: Lấy S={s1,s2,,sk}A (không mất tổng quát có thể giả sử s1<s2<<sk) đặt tương ứng với f(S)={s1,s21,s32,,sk(k1)}. Dễ chứng minh đây là một song ánh. Từ đó có Cnk+1k tập thoả yêu cầu đề bài.

Bài tập rèn luyện 

Bài 1. Cho X=1,2,..,n. Một tập con S=s1,s2,,sk của X (s1<s2<<sk) được gọi là \textit{m- tách được} (mN) nếu sisi1m;i=1,2,,k. Có bao nhiêu tập con m- tách được gồm k phần tử của X, trong đó 0kn(m1)(k1).

Bài 2. Cho X=1,2,,n, với mỗi tập con khác rỗng Ai=a1,a2,,ai (không mất tổng quát giả sử a1>a2>>ai) ta định nghĩa \textit{tổng hỗn tạp} của Ai là số m(Ai)=a1a2+a3±ai. Tính AiXm(Ai).

Bài 3. Cho số nguyên dương nd là một ước dương của n. Gọi S là tập tất cả những bộ (x1,x2,,xn) nguyên dương thỏa 0x1x2xnnd|x1+x2++xn. Chứng minh rằng có đúng một nửa các phần tử của S có tính chất xn=n.

Bài 4. Gọi an là số các xâu nhị phân độ dài n không chứa ba bit 0, 1, 0 liên tiếp. Gọi bn là số các xâu nhị phân độ dài n chứa bốn bit 0, 0, 1, 1 hoặc 1, 1, 0, 0 liên tiếp. Chứng minh rằng bn+1=2an với mọi số nguyên dương n.

Bài 5. Cho các số tự nhiên k,n,m thỏa điều kiện 1<kn,m>1. Hỏi có bao nhiêu chỉnh hợp chập k:(a1,a2,,ak) của n số tự nhiên đầu tiên mà mỗi chỉnh hợp đều thỏa mãn ít nhất một trong hai điều kiện sau:

i) Tồn tại i,j1,2,,k sao cho i<jai>aj.

ii) Tồn tại i1,2,,k sao cho aii không chia hết cho m.

Bài 6. Cho các số nguyên dương n,k,p với k2k(p+1)n. Cho n điểm phân biệt cùng nằm trên một đường tròn. Tô tất cả n điểm đó bởi hai màu xanh, đỏ (mỗi điểm được tô bởi một màu) sao cho có đúng k điểm được tô bởi màu xanh và trên mỗi cung tròn mà hai đầu mút là hai điểm màu xanh liên tiếp (tính theo chiều quay kim đồng hồ) đều có ít nhất p điểm được tô màu đỏ. Hỏi có tất cả bao nhiêu cách tô khác nhau?

Bài 7. Gọi an là số các xâu nhị phân độ dài n không chứa ba bit 0, 1, 0 liên tiếp. Gọi bn là số các xâu nhị phân độ dài n chứa bốn bit 0, 0, 1, 1 hoặc 1, 1, 0, 0 liên tiếp. Chứng minh rằng bn+1=2an với mọi số nguyên dương n.

Bài 8. Trong một hội nghị có n nhà toán học. Biết rằng nếu hai nhà toán học nào đó quen nhau thì họ không quen chung thêm một người nào nữa, còn nếu hai nhà toán học này không quen nhau thì họ quen chung với đúng hai nhà toán học khác nữa. Chứng minh rằng 8n7 là số chính phương.

Bài 9. Trong một trại hè toán học có 40 học sinh. Biết rằng cứ 19 học sinh bất kỳ thì đều viết thư hỏi bài một học sinh khác (Nếu học sinh A viết thư hỏi bài học sinh B thì không nhất thiết học sinh B phải viết thư hỏi bài học sinh A và dĩ nhiên A cũng không viết thư hỏi chính mình). Chứng minh rằng trong trại hè này tồn tại một tập T0 gồm 20 học sinh sao cho với mỗi PT0 thì 19 người còn lại không đồng thời viết thư hỏi bài P.

Bài 10. Gọi M là số số nguyên dương trong hệ thập phân có 2n chữ số trong đó có n chữ số 1 và n chữ số 2. Gọi N là số số nguyên dương có n chữ số trong hệ thập phân trong đó chỉ có các chữ số 1, 2, 3, 4 và số chữ số 1 bằng số chữ số 2. Chứng minh |M|=|N|.

(Hết phần 1)

Nguyên lý Đirichlet và áp dụng

Nguyên lý Dirichlet hay còn được gọi là nguyên lý chuồng thỏ được phát biểu dưới dạng sau:”n+1 con thỏ được nhốt vào n cái chuồng thì có một chuồng chứa ít nhất hai con thỏ“. Với nội dung khá đơn giản tuy nhiên nguyên lý này giúp giải được khá nhiều bài toán trong nhiều phân môn: đại số, số học, hình học, tổ hợp. Trong bài viết nhỏ này trình bày một vài ví dụ áp dụng nguyên lý Dirichlet giúp các bạn định hướng tốt hơn trong việc giải các bài toán.

1. Các ví dụ

a) Nguyên lý Dirichlet trong các bài toán đại số và số học

Nguyên lý Dirichlet có thể được phát biểu như sau: n+1 số tự nhiên lớn hơn k và nhỏ hơn k+n+1, thì sẽ có 2 số bằng nhau.

Trong phát biểu trên ta xem n+1 số tự nhiên là n+1 con thỏ, các số tự nhiên lớn hơn k, nhỏ hơn k+n+1 gồm k+1,k+2,,k+nn cái chuồng. Khi đó chắc chắn có 2 con thỏ cùng một chuồng, hay sẽ có hai số bằng nhau.

Việc phát hiện đối tượng nào là thỏ, đối tượng nào là chuồng là một việc có ý nghĩa quan trọng, hoặc đôi khi ta phải xây dựng chuồng, thỏ, từ đó giải quyết vấn đề. Ta xét các ví dụ sau:

Ví dụ 1: Cho 676 số tự nhiên phân biệt không lớn hơn 2016. Chứng minh rằng chọn được hai số a,b thỏa |ab|{3,6}.

Giải

Gọi 676 số đó là a1,a2,,a676.

Xét 676×3=2028 gồm 676 số a1,a2,,a676; (nhóm 1), 676 số a1+3,a2+3,,a676+3 (nhóm 2), 676 số a1+6,a2+6,,a676+6 (nhóm 3).

2028 số này là các số tự nhiên không vượt quá 2022 nên theo nguyên lý Dirichlet tồn tại 2 số bằng nhau. Mà hai số cùng một nhóm không thể bằng nhau nên xảy ra 3 trường hợp: ai=aj+3, ai=aj+6 hoặc ai+3=aj+6, trong cả ba trường hợp ta đều có |aiaj|{3,6}.

Ví dụ 2: Cho tập A=1,2,3,,9. Lấy S gồm các phần tử thuộc A sao cho tổng hai số bất kì thuộc S là các số phân biệt. Hỏi tập S có số phần tử nhiều nhất là bao nhiêu? Tại sao?

Giải

Nếu tập S7 phần tử trở lên thì sẽ có không ít hơn 21 tổng. Mà các tổng hai số chỉ nhận các giá trị từ 3 đến 17 nên theo nguyên lý dirichlet thì sẽ có hai tổng bằng nhau.

Do đó số phần tử của S không lớn hơn 6.

Xét S6 phần tử, khi đó có đúng 15 tổng nhận các giá trị 3,14,,17 nên mỗi tổng hai số nhận đúng một giá trị. Để có tổng bằng 3, 17 thì tồn tại 4 số 1,28,9. Khi đó 1+9=2+8 (vô lý). Vậy tập không thể có 6 phần tử.

Nếu tập có 5 phần tử, ta thấy S={1,2,5,7,9} thỏa đề bài.

Vậy số phần tử lớn nhất của một tập con thỏa đề bài là 5.

Ví dụ 3: Cho 1010 số nguyên dương a1<a2<<a10102017. Chứng minh rằng có 2 số ai,ak sao cho ai+a1=ak.

Giải

Xét 2019 số gồm 1010 số đã cho (nhóm 1) và 1009 số a2a1,a3a1,,a1010a1 (nhóm 2) nhận giá trị nguyên từ 1 đến 2017, theo nguyên lý dirichlet thì có hai số bằng nhau, hơn nữa các số nhóm 1 khác nhau, các số nhóm 2 khác nhau nên một số thuộc nhóm 1 bằng một số thuộc nhóm 2, do đó tồn tại i,k sao cho aka1=ai hay ai+a1=ak.

Nguyên lý áp dụng trong các bài toán số học được phát biểu dưới dạng sau: “Cho n+1 số nguyên, khi đó có 2 số có hiệu chia hết cho n“.

Ví dụ 4: Chứng minh rằng trong 11 số chính phương thì có 2 số có hiệu chia hết cho 20.

Giải

Theo nguyên lý đirichlet thì trong 11 số có hai số có hiệu chia hết cho 10, gọi 2 số đó là a,b. Ta có a=x2,b=y2ab=(xy)(x+y) chia hết cho 10 nên x,y cùng tính chẵn lẻ, do đó (xy)(x+y) chia hết cho 4. Vậy ab chia hết cho 4 và chia hết cho 10 nên chia hết cho 20.

Ví dụ 5: Cho 5 số nguyên dương và mỗi số chỉ có ước nguyên tố là 23. Chứng minh rằng có 2 số mà tích là một số chính phương.

Giải

5 số có dạng 2a3b với a,b là các số tự nhiên.

Xét tính chẵn lẻ của các cặp số (a;b) ta chỉ có 4 trường hợp là (chẵn; chẵn), (chẵn;lẻ), (lẻ; chẵn) và (lẻ; lẻ).

Khi đó với 5 cặp số thì theo nguyên lý dirichlet có 2 cặp (a1;b1)(a2;b2) sao cho a1,a2 cùng tính chẵn lẻ và b1,b2 cùng tính chẵn lẻ.

Khi đó a1+a2,b1+b2 là chẵn, suy ra 2a13b12a23b2=2a1+a23b1+b2 là số chính phương.

Ví dụ 6: Xét 20 số tự nhiên 1,2,...,20. Hãy tìm số nguyên dương k nhỏ nhất sao cho với mỗi cách lấy k số phân biệt từ 20 số trên đều lấy được hai số a,b sao cho a+b là một số nguyên tố.

Giải

Xét 10 số chẵn thì tổng hai số bất kì đều là hợp số, do đó đó k11.

Ta chứng minh k=11.

Xét 10 cặp số (1;2),(3;20),(4;19),,(11;12), mỗi cặp số có tổng là số nguyên tố, khi đó với 11 số thì theo nguyên lý dirichlet có 2 số cùng một cặp, khi đó tổng của chúng là một số nguyên tố.

b) Nguyên lý Dirichlet trong các bài toán hình học

Ví dụ 7: 33 điểm trong hình vuông 4×4. Chứng minh rằng có 3 điểm tạo thành tam giác có diện tích không lớn hơn 12.

Giải

 

Chia hình vuông thành 16 hình vuông như hình vẽ, khi đó theo nguyên lý dirichlet thì có 3 điểm cùng thuộc một hình vuông 1×1.

Ta cần chứng minh tam giác có 3 đỉnh nằm trong hoặc trên cạnh hình vuông 1 thì diện tích không quá 12.

 

 

Xét tam giác EFG, đường thẳng qua E song song với cạnh hình vuông cắt FG tại I.

Khi đó SEFG=SEFI+SEGI=12FMEI+12GKEI=EI2(FM+GK)12.

Ví dụ 8: Cho một tập S gồm 25 điểm sao cho với ba điểm bất kì thuộc S thì có 2 điểm khoảng cách nhỏ hơn 1. Chứng minh rằng tồn tại một hình tròn bán kính 1 chứa ít nhất 13 điểm thuộc S.

Giải

Xét 2 điểm AB sao cho AB có độ dài lớn nhất. Khi đó xét 2 hình tròn (A;1),(B;1) nếu chứa hết 25 điểm thì sẽ có 13 điểm cùng thuộc một hình tròn, ta có điều cần chứng minh.

Nếu có 1 điểm C không thuộc 2 hình tròn trên thì trong 3 điểm A,B,C không có 2 điểm nào khoảng cách nhỏ hơn 1 (vô lý).

Ví dụ 9: Cho đa giác đều có 14 đỉnh. Chứng minh rằng từ 6 đỉnh bất kì có thể chọn được 4 đỉnh tạo thành một hình thang cân.

Giải

 

Do tính chất đối xứng của tứ giác đều nên với hai đỉnh bất kì thì độ dài nối hai đỉnh đó có thể nhận 1 trong 7 giá trị.

Với 6 đỉnh ta có 15 đoạn thẳng nhận bảy giá trị độ dài khác nhau, theo nguyên lý dirichlet thì có 3 đoạn có đoạn thẳng bằng nhau.

TH1: Nếu 3 đoạn bằng nhau đó cùng chung một đỉnh, ví dụ AB=AC=AD, suy ra B,C,D thuộc đường tròn tâm A (vô lý).

TH2:2 đoạn bằng nhau không chung một đỉnh, giả sử AB=CD. Ta có ABCD nội tiếp và AB=CD nên 4 đỉnh A,B,C,D tạo thành hình thang cân. (điều cần chứng minh).

2. Bài tập

Bài 1: Cho 100 số tự nhiên. Chứng minh rằng tồn tại một số hoặc mộ số các số có tổng chia hết cho 100.

Bài 2: Chứng minh rằng tồn tại số tự nhiên chỉ toàn các chữ số 1 và chia hết cho 2017.

Bài 3: Cho bảng ô vuông 5×5, người ta điền vào các ô vuông các số 1,0,1. Xét tổng các số ở các dòng, cột và đường chéo, chứng minh rằng trong các tổng này có hai tổng bằng nhau.

Bài 4: Cho 5 số nguyên dương đôi một phân biệt sao cho trong các số ấy thì chỉ có ước nguyên tố là 23. Chứng minh rằng có hai số mà tích của chúng là một số chính phương.

Bài 5:20 số nguyên dương phân biệt không lớn hơn 70. Xét tất cả các hiệu của 2 số, chứng minh rằng trong các hiệu đó có 4 số bằng nhau.

Bài 6: Xét 20 số tự nhiên 1,2,,20. Hãy tìm số nguyên dương k nhỏ nhất sao cho với mỗi cách lấy k số phân biệt từ 20 số trên đều lấy được hai số a,b sao cho a+b là một số nguyên tố.

Bài 7:

a) Tô các cạnh của một lục giác bằng 2 màu xanh đỏ. Chứng minh rằng tồn tại một tam giác được tô cùng một màu.

b) Tô các cạnh của một đa giác 17 cạnh bằng 3 màu. Chứng minh rằng tồn tại một tam giác được tô cùng một màu.

Bài 8: Trên đường tròn cho 16 điểm tô bởi một trong ba mày: Xanh, Đỏ, Vàng. Các dây cung nối 2 điểm trong 16 điểm trên được tô bởi hai màu trắng, đen. Chứng minh ta luôn có 3 điểm trong 16 điểm trên tô cùng màu và 3 cạnh của nó cũng được tô cùng màu.

Bài 9: Chứng minh rằng trong 52 số tự nhiên bất kì luôn tìm được 2 số mà tổng hoặc hiệu của chúng chia hết cho 100.

Bài 10: Từ các số 1,2,,2n lấy ra n+1 số. Chứng minh rằng:

a) Có 2 số nguyên tố cùng nhau.

b) Có 2 số mà số này chia hết cho số kia.

Bài 11:81 số gồm 9 chữ số 1,9 chữ số 2,,9 chữ số 9. Xếp 81 số này thành một dãy, có tồn tại hay không một cách xếp sao cho giữa hai chữ số k có đúng k số với k=1,2,,9.

Bài 12:51 điểm trong một hình vuông có cạnh bằng 1. Chứng minh rằng tồn tại 3 điểm có thể chứa trong một hình tròn bán kính 17.

Bài 13: Cho đa giá có 2018 cạnh, chứng minh rằng có một đường chéo không song song với bất kì cạnh nào.

Bài 14: Mỗi đỉnh của một đa giác đều 7 cạnh được tô màu đỏ hoặc xanh. Chứng minh rằng có 3 đỉnh tạo thành một tam giác cân và được tô cùng một màu.

Bài 15:9 đường thẳng trong đó mỗi đường thẳng chia hình vuông ra làm 2 phần tỉ lệ diện tích là 2:3. Chứng minh rằng có 3 đường thẳng đồng quy.

Bài 16: (PTNK 2011) Cho hình chữ nhật 3×4.

a) Có 7 điểm trong hình chữ nhật. Chứng minh có 2 điểm khoảng cách không lớn hơn 5.

b) Có 6 điểm trong hình chữ nhật. Chứng minh có 2 điểm khoảng cách không lớn hơn 5.

Giải bài toán bằng đại lượng cực biên-Phần 1

Tương đương với nguyên lý qui nạp là nguyên lý cực hạn, trong dó cụ thể bằng một số tính chất sau:

Tính chất (tiên đề)

  •  Một tập con hữu hạn khác rỗng của tập số thực luôn tồn tại phần tử nhỏ nhất và phần tử lớn nhất.
  • Mọi tập con khác rỗng của R bị chặn trên đều tồn tại chặn trên nhỏ nhất.
  • Mọi tập con khác rỗng của R bị chặn dưới đều tồn tại chặn dưới lớn nhất.

Trong nhiều bài toán, việc chọn đối tượng cực hạn (lớn nhất hoặc nhỏ nhất) giúp ta thuận lợi trong suy luận. \
Cũng như quy nạp, cực hạn cũng có nhiều ứng dụng rộng rãi trong các việc giải quyết các bài toán tổ hợp.
Ví dụ 1. Tìm n lớn nhất sao cho tồn tại n điểm mà 3 điểm bất kì đều tạo thành tam giác vuông.

Lời giải
  Ta thấy n=3,n=4 đều tồn tại. Ta chứng minh n5 thì không tồn tại. \
Giả sử ngược lại, tồn tại 5 điểm, sao cho 3 điểm bất kì đều tạo thành tam giác vuông. Khi đó ta chọn hai điểm sao cho có độ dài lớn nhất. Khi đó các điểm còn lại đều nằm trên đường tròn đường kính là đoạn thẳng này. Khi đó 3 điểm thuộc 2 nửa đường tròn, khi đó có ít nhất 2 điểm cùng thuộc một nửa, từ đó tồn tại một tam giác khác vuông có đỉnh là 2 điểm này cùng một điểm thuộc đường kính. Do đó không thỏa đề bài.

Bài toán này có nhiều các để tiếp cận, việc tìm ra n=5 không có gì khó, khi chứng minh n=5 không thỏa cũng có nhiều cách suy luận, tuy vậy việc chọn đoạn thẳng có độ dài lớn nhất giúp ta dễ dàng suy ra mâu thuẫn.
Ví dụ 2. Trên một mặt bàn đặt một số các đồng xu với kích cỡ không giống nhau đôi một (các đồng xu không được đè lên nhau và phải nằm sấp hoặc ngửa trên bàn). Chứng minh rằng dù ta đặt như thế nào đi nữa, cũng luôn tồn tại một đồng xu chỉ tiếp xúc được với nhiều nhất 5 đồng xu khác.

Lời giải
  Chọn đồng xu có bán kính nhỏ nhất, thì đồng xu này chỉ tiếp xúc không quá 5 đồng xu khác. Giả sử nó có thể tiếp xúc với 6 đồng xu khác. Khi đó A là tâm đường tròn, tâm các đường tròn còn lại là A1,,A6. Khi đó tồn tại AiAi+160, suy ra AiAi+1<AAi vô lý, vì bán kính của (A) là nhỏ nhất.

Ví dụ 3. Cho n điểm trong mặt phẳng biết rằng cứ 3 điểm bất kì tạo thành một tam giác có diện tích không lớn hơn 1. Chứng minh rằng n điểm thuộc một hình tam giác có diện tích không lớn hơn 4.

Lời giải
  Gọi A,B,C là 3 điểm tạo thành tam giác sao cho ABC có diện tích lớn nhất. Từ A,B,C vẽ các đường song song với các cạnh đối diện, các đường thẳng cắt nhau tại A,B,C ta chứng minh các điểm thuộc cạnh hoặc miền trong tam giác ABC.

Thật vậy, nếu có điểm nào nằm ngoài tam giác ABC thì điểm đó kết hợp với hai trong 3 điểm A,B,C sẽ có diện tích lớn hơn diện tích tam giác ABC, vô lý.
Do SABC=4SABC4.

Ví dụ 4. (Sylvester) Trong mặt phẳng cho n điểm phân biệt, sao cho mỗi đường thẳng đi qua hai điểm thì đi qua ít nhất một điểm khác. Chứng minh rằng n điểm này cùng thuộc một đường thẳng.

Lời giải
Giả sử không phải tất cả các điểm cùng thuộc một đường thẳng. Khi đó ta xét khoảng cách từ một điểm đến đường thẳng qua ít nhất 3 điểm, trong các khoảng cách này có khoảng cách nhỏ nhất. Giả sử P là điểm có khoảng cách từ P đến d là nhỏ nhất, với d là đường thẳng qua các điểm A,B,C theo thứ tự. \
Gọi H là hình chiếu của P trên d, D,E là hình chiếu của A,B trên B trên PA,PC. Nếu H thuộc tia BA thì BE<PH, nếu H thuộc đoạn BC thì BD<PH. Mâu thuẫn với PH là nhỏ nhất. \
Vậy tất cả các điểm cùng thuộc một đường thẳng.
Trên đây là một định lý kinh điển với lời giải cực hạn cũng đi vào các sách giáo khoa về tổ hợp, việc chọn khoảng cách nhỏ nhất đó là một ý tưởng khá độc đáo, giúp giải quyết bài toán rất nhanh.

Việc chọn đối tượng cực hạn phụ thuộc vào bài toán và hướng đi kế tiếp, có được điều này cần rèn luyện thêm trong việc giải toán.

Ví dụ 5. Cho 3 trường, mỗi trường có n học sinh, biết rằng cứ mỗi học sinh thì quen ít nhất n+1 học sinh của hai trường khác. Chứng minh rằng có thể chọn được từ mỗi trường một bạn sao cho 3 bạn này đôi một quen nhau.

Lời giải
Giả sử 3 trường là X,Y,Z. Tồn tại một người có số người quen ở cùng một trường khác là nhiều nhất, giả sử A thuộc X có số người quen ở trường Y nhiều nhất là k. Khi đó số người quen của AZ ít nhất là n+1k. Nếu nhóm người quen AZ quen với số người quen AX có hai người quen nhau thì ta có điều chứng minh.\
Ngược lại xét người quen AZ, đặt là B quen số người ở Y tối đa là nk, khi đó B quen ở X ít nhất là n+1(nk)=k+1, mâu thuẫn với cách chọn A. (Mâu thuẫn).

Ví dụ 6. Một bữa tiệc có 10 học sinh tham gia, biết rằng mỗi học sinh quen với ít nhất là 5 người. Chứng minh rằng có thể sắp xếp 10 học sinh ngồi vào một bàn tròn sao cho hai người kế nhau thì quen nhau.

Lời giải
Giả sử chuỗi người quen dài nhất có độ dài là k, A1A2Ak, ta thấy các người còn lại không ai quen A1,Ak nên suy ra k6. \
Nếu k=6, suy ra A1A6 quen nhau, khi đó trong các người còn lại A7 quen một trong cái người giả sử là Ai, khi đó ta có chuỗi A7AiAi1A1A6Ai+1 có độ dài hơn 6, vô lý.\
Nếu k=7, khi đó A1 quen từ A2 đến A6A7 quen A2 tới A6, khi đó có một vòng A2A7A6A5A4A3A1A2. Khi đó sẽ có một người trong nhóm còn lại thì ta sẽ có chuỗi dài hơn, mâu thuẫn.\
Nếu k=8,9 xét tương tự, ta sẽ có k=10. Giả sử có chuỗi A1A10. Khi đó tồn tại k>i sao cho A1 quen AkA10 quen Ai, khi đó có cách xếp thỏa đề bài là A1AkAiA10A9Ak.

Ví dụ 7. Một bảng 2n×2n ô, người ta đánh dấu bất kì 3n ô trong bảng. Chứng minh rằng tồn tại n dòng và n cột sao cho 3n ô được đánh dấu thuộc n dòng và n cột này.

Lời giải
Chọn n dòng sao cho số ô được tô là lớn nhất, ta chứng minh rằng số ô được tô trong n dòng này là không ít hơn 2n ô. \
Thực vậy giả sử số ô được tô là ít hơn 2n, khi đó n dòng còn lại có nhiều hơn n ô được tô, nên có ít nhất một một dòng có 2 ô được tô. Do đó n dòng đã chọn, mỗi dòng ít nhất 2 ô được tô nên tổng số ô hơn hoặc bằng 2n (mâu thuẫn).\
Vậy ta chỉ cần chọn n cột chứa các ô được tô màu nhưng chưa được chọn trong n dòng trên thì sẽ có điều cần chứng minh.

Bài tập rèn luyện
Bài 1.(2n+1) người đứng trên cùng một mặt phẳng, khoảng cách giữa họ không giống nhau. Sau đó mỗi người bắn người gần họ nhất. Chứng minh rằng:

a) Có ít nhất một người còn sống.
b) Không ai bị bắn quá năm viên đạn.
c) Các đường đạn không cắt nhau.

Bài 2. Một hành tinh có 20 quốc gia. Trong ba nước bất kỳ, luôn có hai nước không thiết lập quan hệ ngoại giao với nhau. Chứng minh rằng, hành tình này có tối đa 200 đại sứ quán.
Bài 3. Với 2n+3 điểm trong mặt phẳng, ba điểm bất kỳ không thẳng hàng và bốn điểm bất kỳ không cùng nằm trên một đường tròn. Chứng minh rằng ta có thể chọn ba điểm và vẽ được một đường tròn qua ba điểm đó. Trong 2n còn lại, có n điểm nằm trong đường tròn và n điểm nằm ngoài đường tròn.
Bài 4.  Điền các số từ 1 đến n2 vào bảng vuông n×n. Chứng minh rằng có hai ô kề nhau (kề cạnh hoặc kề đỉnh) mà hiệu của chúng không nhỏ hơn n+1.
Bài 5.  Có N(N3) chơi tenis vòng tròn một lượt. Cuối giải người ta thấy rằng không có ai thắng tất cả các trận thi đấu. Chứng minh rằng có thể tìm được 3 người A, B, C sao cho A thắng B, B thắng C và C thắng A.
Bài 6.  Cho a,b là hai số tự nhiên nguyên tố cùng nhau.
Gọi d=(a,b). Khi đó tồn tại các số nguyên x,y sao cho xa+yb=d

 

Tổ hợp lặp và bài toán chia kẹo Euler

Trong các bài toán đếm ta gặp bài toán sau: Một người vào cửa hang mua dụng cụ học tập để làm thành một món quà gồm viết, sách và tập, người đó chỉ mua tổng cộng 5 món đồ. Biết rằng trong cửa hàng có 5 cây viết giống nhau, 6 sách giống nhau và 10 cuốn tập giống nhau, hỏi có bao nhiêu cách chọn viết, sách tập để làm quà?

Ta thấy rằng số lượng các viết sách và tập đều lớn hơn số cần mua, do đó bài toán chỉ quay lại việc đếm là có bao nhiêu bộ sách viết tập mà tổng số là 5 cái, trong đó mỗi cái có hoặc không có.

Có ba đối tượng là viết, sách và tập, tạ kí hiệu là A={V,S,T}. Một món quà gồm 5 cái, do đó quà có thể là X={V,V,V,S,T}, gồm 3 cây viết và 1 sách, 1 tập, hoặc là tập Y={V,V,S,T,T}, ta thấy các đối tượng V,T là lập lại. Khi đó ta nói tổ hợp X,Y là tổ hợp lặp.

Để định nghĩa rõ hơn ta có định nghĩa sau:

Định nghĩa.  Cho tập A={a1,a2,,ak}. Một ánh xạ từ p:AN, khi đó P được gọi là một multiset của A.

Ví dụ 1. Cho A={a,b,c}. Ánh xạ p:AN như sau: p(a)=2,p(b)=1,p(c)=1. Khi đó ta có thể kí hiệu p(aabc), hay (baac),.., không tính đến thứ tự của các phần tử a,b,c.

Đặt n=p(a1)+p(a2)++p(ak), bài toán đặt ra là có bao nhiêu ánh xạ p:ANn=p(a1)+p(a2)++p(ak).

Tiếp theo ví dụ trên, nếu p(a)+p(b)+p(c)=2 thì có các multiset sau: (ab),(ac),(bc),(aa),(bb),(cc), 6 multiset.

Tính chất. Cho tập A={a1,a2,,ak}, số ánh xạ p:AN thỏa p(a1)++p(ak)=nCn+k1n

Chứng minh

Mỗi ánh xạ p ta cho tương ứng với một dãy nhị phân độ dài n+k1, trong đó p(a1) chữ số đầu là 0, tiếp theo là số 1, rồi p(a2) chữ số 0,…cuối cùng là p(ak) chữ số 0. Ví dụ bộ VVSTT ứng với dãy 0010100.

Rõ ràng đây là tương ứng 1 – 1, do đó số ánh xạ p bằng số dãy nhị phân, do đó ta chỉ cần đếm số dãy nhị phân.

Ta thấy dãy có n+k1 chữ số trong đó có k1 chữ số 1, do đó số dãy nhị phân chỉ là số cách chọn vị trí cho k1 chữ số 1 nên số dãy nhị phân là Cn+k1k1.

Do đó số ánh xạ pCn+k1k1

Trở lại bài toán trên, ta thấy số món quà có 5 cái là một tổ hợp lặp chập 5 của sách, viết, tập, do đó số món quà có thể là C5+212=C62=15.

(Chú ý trong bài toán trên, đảm bảo số mỗi loại sản phẩm có không ít hơn 5 cái).

Bài toán 1. (Chia kẹo Euler). Cho n viên kẹo giống nhau đem chia cho k người, hỏi có bao nhiều cách chia.

Giải

Ta gọi k người là a1,a2,ak, với mỗi cách chia kẹo là một multiset của Ap(a1)+p(a2)++p(ak)=n.

Do đó số cách chia kẹo là Cn+k1n.

Bài toán 2. Giải bài toán trên với cách chia sao cho mỗi người có ít nhất một viên.

Giải

Trước hết phát cho mỗi người một viên, thì còn nk viên kẹo, tiếp tục áp dụng bài toán trên với nk. Khi đó số cách chia là

Cn1k1

Ta có thể giải bài toán trên mà không cần sử dụng bài toán 1 bằng cách xây dựng dãy nhị phân thỏa: a1 chữ số đầu là 0, tiếp theo là số 1, tiếp là a2 chữ số 0, …., cuối cùng là ak chữ số 0. Dãy này có k1 chữ số 1 đứng giữa n chữ số 0 và không có hai chữ số 1 nào đứng kề nhau. Khi đó số dãy nhị phân là: Cn1k1.

Phần kế tiếp ta cùng tìm hiểu và giải một số bài toán có thể đưa về bài toán tổ hợp lặp hay bài toán chia kẹo Euler. Các bạn chờ nhé.

Bài toán 1 và 2 có thể phát biểu dưới dạng sau.

Bài toán 3. Cho phương trình x1+x2++xk=n trong đó k,n là các số nguyên dương.

a. Tìm số nghiệm tự nhiên của phương trình.

b. Tìm số nghiệm nguyên dương của phương trình.

Như bài toán trên ta đã biết, số nghiệm tự nhiên của phương trình là  Cn+k1k1.

Số nghiệm nguyên dương của phương trình là Cn1k1.

(Phần 2)

Trong phần trước ta đã biết, số nghiệm nguyên không âm của phương trình x1+x2++xk=nCn+k1k1, và số nghiệm nguyên dương là Cn1k1.

Từ bài toán này ta có thể giải các bài toán sau:

Ví dụ 1. Tìm số nghiệm nguyên của phương trình x1+x2+x3+x4+x5=30 nếu:

a) xi2i=1,5.

b) 3<x1,x2x3,x4,x5>5.

c) x1,x2,x3,x440<x5<3.

Giải

a) x1+x2+x3+x4+x5=30, xi2i=1,5. (1). Ta đi tìm số nghiệm của hệ (1).

Để đưa về bài toán gốc, ta đặt ẩn phụ như sau: yi=xi11 với mọi i=1,5.

Khi đó ta có y1+1+y2+1+y3+1+y4+1+y5+1=30y1+y2+y3+y4+y5=25 với yi1. (2)

Một bộ nghiệm của (2) cho tương ứng một bộ nghiệm thỏa (1), mà số nghiệm của (2)C244 (Theo bài toán chia kẹo Euler), do đó số nghiệm của (1) là C244.

b) Tương tự câu a, đặt y1=x13,y2=x23,y3=x35,y4=x45,y5=x55, từ (1) ta có phương trình y1+y2+y3+y4+y5=9yi1. Số nghiệm là C84.

c) Xét x5=1,2 và đặt ẩn phụ yi=xi3 ta có đáp số là: C163+C153.

Ví dụ 2. Có bao nhiêu bộ (x1,x2,...,x10) các số nguyên dương thỏa x1+x2+x10<2020.

Giải

Đặt x11=2020(x1+x2++x10) thì x111.

Khi đó ta có phương trình x1++x11=2020xi1.

Do đó số nghiệm là C201910.

Ví dụ 3.  Có bao nhiêu bộ (x1,x2,...,x10) các số tự nhiên thỏa x1x2x3x102020.

Giải

Đặt y1=x1,y2=x2x10, y2=x3x20, …, y11=2020x100.

Khi đó y1+y2++y11=2020 với yi0. (2)

Với một bộ nghiệm của (2) sẽ tương ứng duy nhất một bộ (x1,x2,,x10)  thỏa đề bài.

Số nghiệm của (2) là C203010, đó cũng chính là số bộ (x1,x2,,x10) thỏa đề bài.

Ví dụ 4. (VMO 2012) Cho một nhóm gồm 5 cô gái, kí hiệu là G1,G2,G3,G4,G5 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à G1,G2,G3,G4,G5 ;
3) Giữa G1G2 có ít nhất 3 chàng trai;
4) Giữa G4G5 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?

Giải

Đánh số thứ tự các ghế từ trái sang phải là 1,2,,17.

Gọi x1 là số chàng trai được xếp bên trái G1,x2 là số chàng trai ở giũa G1G2,x3 là số chàng trai ở giữa G2G3,x4 là số chàng trai ở giữa G3G4,x5 là số chàng trai ở giữa G4G5,x6 là số chàng trai được xếp ở bên phải G5. Khi đó bộ số (x1,x2,,x6) hoàn toàn xác định vị trí các cô gái và ta có:
1) x1+x2++x6=12
2) 3x2.
3) 1x54
Đổi biến y2=x23y5=x51 ta được x1+y2+x3+x4+y5+x6=8 với các ẩn^ không âm và có thêm điều kiện y53. Tiếp theo, sử dụng bài toán chia kẹo của Euler ở dạng x1+y2+x3+x4+x6=8y5 ta được đáp số (phần phân ghế cho các cô gái) là C124+C114+C104+C94=1161.
Vì còn có 12 chàng trai có thể hoán đổi vị trí ở 12 chiếc ghế dành cho họ nên số cách xếp thỏa mãn yêu cầu bài toán là 116112!

Ví dụ 5. Có bao nhiêu bộ số nguyên dương (a,b,c,d) thỏa d=max{a,b,c,d},d2015

(ad+bc)(bd+ac)(cd+ab)=(da)2(db)2(dc)2.

Giải
  • Trước hết ta chứng minh d=a+b+c bằng phản chứng.
  • Khi dó 3d2015, với mỗi d thì số bộ (a,b,c)Cd12.
  • Do đó số bộ thỏa đề bài là C22+C32++C20142.

Trên đây là một số bài toán liên quan đến bài toán chia kẹo Euler, các bạn hãy đọc và tìm hiểu thêm trong các tài liệu khác.

Bài tập rèn luyện.

Bài 1. Tìm số nghiệm nguyên dương của phương trình: x1+x2+...+x5=100
Bài 2. Tìm số nghiệm không âm của phương trình x1+x2+x3+x4=20.
Bài 3. Có bao nhiêu số tự nhiên có 3 chữ số mà tổng các chữ số bằng 11 ?
Bài 4. Tìm số nghiệm nguyên của phương trình x1+x2+x3+x4=30 nếu:
a) xi0i.
b) 2x17, xi0,i=2,3,4.
c) x13,x21,x3,x41.
Bài 5. Tìm số nghiệm nguyên dương của phương trình 4x1+x2+x3+x4=15.
Bài 6. Có 4 viên bi vàng và 10 viên bi xanh. Hỏi có bao nhiêu cách sắp xếp các viên bi thỏa:
a) Không có bi vàng nào kề nhau.
b) Giữa hai bi vàng có ít nhất 2 bi xanh.

Bài 7. Để bảo vệ máy tính của minh khỏi su tấn công của hacker, một lâp trinh viên muốn thiết lập một mât khẩu cho máy tính của mình. Mât khẩu này bao gồm tất cả các chữ cái trong bảng chữ cái tiêng Anh, mỗi chữ cái một lần xuất hiện và các chữ nguyên âm không đứng cạnh nhau. Hỏi lâp trình viên đó có bao nhiêu cách cài đăt mât khẩu?

Bài 8. Bốn anh em An, Bình, Cừng, Danh rất thích ăn keo. Nhân dip Tết, me của các câu đực thửng rất nhiều quà, trong đó có một phần quà là một bịch keo bao gồm 125 viên keo. Vì quá thich ăn kẹo nên bốn anh em đã xin mẹ thêm một vài bịch keo khác giống nhu vậy nữa, nhưng me nhất quyết không cho vì sơ ăn nhiều keo sẽ bi sâu răng, do đó mẹ chỉ cho các câu ăn số kẹo trong bịch kia thôi. Thế là họ ngay lâp tức chia nhau số keo nói trên. Hỏi họ có tông công bao nhiêu cách chia keo ? (cho rằng 125 viên keo là giống hệt nhau, và anh em họ có quyền không ăn môt số viên keo trong số 125 viên keo ban đầu, đồng thời cũng có thể xảy ra trường họ có một nguròi không durọc chia viên keo nào).

Tài liệu tham khảo. 

  1. Jiri-herman-radan-kucera-jaromir-simsa, Counting-and-configurations-problems-in-combinatorics-arithmetic-and-geometry
  2. Chuyên đề toán học 11 - Tập san của học sinh Trường Phổ thông Năng khiếu.