Chuyên đề 20: TỔ HỢP VÀ RỜI RẠC
1. KIẾN THỨC TRỌNG TÂM
Tổ hợp và xác suất CX
Số hoán vị của tập A có n phần tử:
Số chỉnh hợp n chập k:
Số tổ hợp n chập k:
Xác suất:
Xác suất có điều kiện:
Nhị thức Newton:
Cho n tập là n tập hợp hữu hạn thì số phần tử:


Cho ánh xạ f từ tập hữu hạn X có n phần tử vào tập hữu hạn Y có m phần tử.
Số ánh xạ f từ X và Y là.
Số đơn ánh f từ X vào Y làvới
Số toàn ánh f từ X vào Y là khi
Số song ánh f từ X và Y là khi
Nguyên tắc Dirichlê
Nếu nhốt con thỏ vào k chuồng (k nguyên dương) thì tồn tại một chuồng chứa ít nhất 2 con. Nếu nhốt con thỏ vào k chuồng (k nguyên dương) thì tồn tại một chuồng chứa ít nhất 3 con.
Nếu nhốtcon thỏ vào k chuồng (k, n nguyên dương) thì tồn tại một chuồng chứa ít nhất con. Nguyên tắc cực hạn
Tồn tại độ đo lớn nhất và độ đo nhỏ nhất hay đại lượng lớn nhất và đại lượng nhỏ nhất của tập hữu hạn khác rỗng các độ đo hay các đại lượng.
Bất biến và đơn biến
Đại lượng bất biến, tính chất bất biến là những đại lượng hay tính chất không thay đổi trong quá trình thực hiện các phép biến đổi nào đó.
Đại lượng đơn biến, tính chất đơn biến là những đại lượng hay tính chất thay đổi một chiều, hoặc tăng thêm hoặc giảm đi trong quá trình thực hiện các phép biến đổi nào đó.
Đồ thị
Bổ đề bắt tay: Cho đồ thị thì tổng bậc các đỉnh củạ đồ thị là số chẵn và

Định lý Tocran: Nếu đồ thị G có n đỉnh và số tam giác của G là thì
số cạnh:
2. CÁC BÀI TOÁN
Bài toán 20 .1 : Tính:

Hướng dẫn giải
Xét hàm số thì:




Do đó:

Bài toán 20. 2: Tìm tất cả các cặp số tự nhiên dương n và k thoả:
Hướng dẫn giải
Ta có:


Vì nên (1)
Mà nên (1) xả ra
Do đó
Thử lại Tóm lại
Bài toán 20. 3: Chứng minh rằng:

Hướng dẫn giải
Với ta đặt trong đó tổng được lấy từ
cho đến hết những số hạng khác 0.
Ta có:
Ta có , suy ra (1)
Ta có , từ đó

Từ (1) ta có nếu .Do
nên ta được:

Suy ra điều phải chứng minh.
Bài toán 20. 4: Cho các số nguyên dương m và n sao cho.
Chứng minh rằng:
Hướng dẫn giải
Ta có:
Ngoài ra và

Do đó, các bất đẳng thức cần chứng minh tương đương với

Ta có:

vì i là số nguyên nằm giữa 1 và n. Suy ra:

do đó ta được:
Vậy các bất đẳng thức đã cho là đúng.
Bài toán 20. 5: Cho n nguyên dươngvà
Chứng minh:
Hướng dẫn giải
Ta có: và khai triển nhị thức



Bài toán 20. 6: Hỏi từ các chữ số 1, 2, 3, 4, 5 ta có thể lập được tất cả bao nhiêu số có 15 chữ số mà trong mỗi số mỗi chữ số đều có mặt đúng 3 lần và không có chữ số nào chiếm 3 vị trí liên tiếp trong số?
Hướng dẫn giải
Gọi X là tập gồm tất cả các số thoả mãn yêu cầu đề bài.
A là tập gồm tất cả các số có 15 chữ số được lập nên bởi các chữ số 1, 2, 3, 4, 5 mà mỗi chữ số đều có mặt đúng 3 lần trong số.
Khi đó: Với là tập gồm tất cả các số thuộc A mà chữ số i
chiếm đúng 3 vị trí liên tiếp
Xét ta chứng minh được và
Áp dụng công thức:

Bài toán 20. 7: Cho các số nguyên dương k và n với. Hỏi tất cả có bao nhiêu chỉnh hợp chập của n số nguyên dương đầu tiên, mà mỗi chỉnh hợp thoả mãn ít nhất một trong hai điều kiện sau:
1) Tồn tại sao cho s < t và >
2) Tồn tại sao cho không chia hết cho 2.
Hướng dẫn giải
Gọi A là tập hợp tất cả chỉnh hợp chập k của n số nguyên dương đầu tiên và A1 là tập hợp tất cả chỉnh hợp thoả mãn yêu cầu của bài ra.
Nếu kí hiệu chỉnh hợp và
thì rõ ràngvà . Suy ra:
Bây giờ ta xét . Với mỗi ta đều có với mọi
và với mọi
Ta chứng minh: từ đó ta có:
Bài toán 20. 8: Trong mặt phẳng cho 100 điểm phân biệt sao cho không có 3 điểm nào thẳng hàng.Chứng minh rằng trong số các tam giác được tạo thành từ 100 điểm đó, có không quá 70% các tam giác nhọn.
Hướng dẫn giải
Từ 4 điểm phân biệt không có 3 điểm nào thẳng hàng, nhiều lắm là có 3 tam giác nhọn. Từ kết quả này, suy ra với 5 điểm phân biệt không có 3 điểm nào thẳng hàng, ta nhận được 10 tam giác và có không quá 7 tam giác nhọn.
Với 10 điểm phân biệt không có 3 điểm nào thẳng hàng, số cực đại các tam giác nhọn tạo thành là: số các tập con 4 điểm nhân cho 3 rồi chia cho số các tập con 4 điểm chứa 3 điểm cho trước. Trong khi đó, số tất cả các tam giác tạo thành cũng có biểu thức tương tự như í trên nhưng thay vì nhân 3 ta nhân cho 4. Do vậy số các tam giác nhọn chiếm không quá 3/4 số tất cả các tam giác (đối với 10 điểm).
Lí luận tương tự, ta xét 100 điểm phân biệt sao cho không có 3 điểm nào thẳng hàng, số cực đại các tam giác nhọn tạo thành là: số các tập con 5 điểm nhân cho 7 rồi chia cho số các tập con 5 điểm chứa 3 điểm cho trước.
Trong khi đó, số tất cả các tam giác tạo thành cũng có biểu thức tương tự như trên nhưng thay vì nhân 7 ta nhân cho 10. Do vậy số các tam giác nhọn chiếm không quá 7/10 số tất cả các tam giác tạo thành, điều phải chứng minh.
Bài toán 20. 9: Có một trò chơi xổ số như sau: Từ 90 số Ban tổ chức chọn ngẫu nhiên 5 số. Người chơi được quyền đặt tiền cho một số bất kì hay cho một nhóm số. Nếu tất cả các số người chơi viết nằm trong 5 số của Ban tổ chức thì người chơi thắng số tiền bằng 15 lần số tiền đặt nếu người chơi viết một số; bằng 270 lần nếu người chơi viết hai số; bằng 5500 lần nếu người chơi viết ba số; bằng 75000 lần nếu người chơi viết bốn số; bằng 1000000 lần nếu anh ta viết năm số. Tìm số lần thắng trung bình của người chơi khi viết một số, hai số, .... năm số.Giả sử có 100000 người đặt tiền viết ba số. Tìm xác suất sao cho có hơn 10 người thắng trong số họ.
Hướng dẫn giải
Nếu người chơi viết k số, thì xác suất pk sao cho tất cả các số anh ta viết nằm trong năm số của Ban tổ chức, bằng:

Kí hiệu là số lần thắng trung bình của người chơi khi viết k số và đặt a đồng, ta có:
Vì tất cả, nên rõ ràng là trò chơi xổ số này không có lợi cho người chơi dù viết mấy số. Xác suất sao cho có hơn 10 người thắng trong số những người viết 3 số bằng
Bài toán 20. 10: Hai đấu thủ A và B thi đấu trong một giải cờ vua. Người thắng một ván được một điểm và không có ván hoà. Xác suất thắng một ván của đấu thủ A là và của là p. Ai hơn đối thủ hai điểm thì thắng giải.
Tính xác suất thắng giải của mỗi đấu thủ.
Hướng dẫn giải
Giả sử. Kí hiệu là xác suất thắng giải của A sau n ván; và là các biến số tương ứng A và B thắng ván đầu tiên. Khi đó:

(*)
Trong đó là xác suất A thắng giải sau n – 1 ván còn lại, khi A đã thắng ván đầu tiên; là xác suất A thắng giải sau n – 1 ván còn lại, khi B đã thắng ván đầu tiên.
Xét . Để A thắng giải sau n – 1 ván còn lại, khi A đã thắng ván đầu, thì B phải thắng ván thứ hai, nghĩa là:
Tương tự:
Từ đó và (*) ta có , và suy ra

Khi ta có . Vì không có ván hoà nên , do đó xác suất thắng giải của A là:
Bài toán 20. 11: Tìm tất cả các số nguyên dương n có tính chất sau: Có thể chia tập hợp 6 số thành hai tập hợp, sao cho tích tất cả các số của tập hợp này bằng tích tất cả các số của tập hợp kia.
Hựớng dẫn giải
Ta hãy để ý rằng trong 5 số nguyên liên tiếp phải có một số chia hết cho 5.
Vì vậy nếu tập hợp 6 số có tính chất đã nêu trong đầu bài, thì trong tập hợp ấy phải có đúng hai số chia hết cho 5, dĩ nhiên đó phải là các số n và , còn các số không chia hết cho 5.
Mặt khác, nếu trong 6 số của tập hợp trên chia hết cho một số nguyên tố, thì 5 số còn lại sẽ không chia hết cho p, và tập hợp không có tính chất đòi hỏi. Từ đây đặc biệt suy ra rằng các số và chỉ chứa các thừa số nguyên tố 2 và 3, tức là:

Trong đó là những số nguyên không âm.
Nếu (và do đó ) chia hết cho 3, thì và không chia hết cho 3, vậy và nhưng như thế thì và là hai số nguyên liên tiếp mà lại là hai số chẵn, điều này vô lí.
Lập luận tương tự, ta thấy rằng nếu chia hết cho 3, hoặc nếu chia hết cho 3, thì ta vẫn gặp mâu thuẫn. Chứng tỏ không có số nguyên dương n nào thoả mãn điều kiện bài toán.
Bài toán 20. 12: Tìm tất cả các số nguyên dương k sao cho có thể phân chia tập hợp thành hai tập con A, B thoả mãn điều kiện: Tổng của tất cả các phần tử thuộc A bằng tổng của tất cả các phần tử thuộc B
Hướng dẫn giải
Ta quy ước: tập số M được gọi là có tính chất T nếu M có thể được chia thành hai tập con rời nhau sao cho tổng của tất cả các phần tử của tập con này bằng tổng của tất cà các phần tử cùa tập con kia.
Theo bài ra, ta cần tìm tất cả các số nguyên dương k để tập X có tính chất T. Dễ thấy nếu X có tính chất T thì tổng của tất cả các phần tử của X sẽ là một số chẵn. Mà tổng này bằng nên
Suy ra, k cần có dạng hoặc với. Xét:
Trường hợp 1 :. Khi đó, số phần tử cùa X sẽ là Do đó, ta có thể chia tập X thành tập con rời nhau sao cho mỗi tập con đều gồm 4 số tự nhiên liên tiếp. Dễ thấy, tập gồm 4 số tự nhiên liên tiếp là tập có tính chất T. Từ đó suy ra tập X có tính chất T.
Trường hợp 2: . Khi đó, tập X sẽ có phần tử. Do đó, nếu X được chia thành hai tập con rời nhau A, B thì một trong hai tập con đó, không mất tổng quát giả sử là A, phải có không ít hơn 2t + 1 phần tử. Như vậy, tập B sẽ có không quá 2t phần tử. Suy ra, nếu kí hiệu a, b tương ứng là tổng của tất cả các phần tử của A, B thì:

Với giả thiết ta có:

nên
Với ta có
Với:

Hiển nhiên A, B rời nhau, và bằng tính toán trực tiếp dễ thấy . Như vậy với tập X có tính chất T.
Với ta có: với và
Theo phần trên, tập có tính chất t. Hơn nữa, do tập có , phần tử nên, vận dụng những lập luận đã trình bày khi xét trường hợp 1, ta sẽ được tập có tính chất T. Từ đó suy ra tập X cũng có tính chất T.
Vậy, tóm lại, tất cả các số nguyên dương k cần tìm là tất cả các số có dạng
và
Bài toán 20. 13: Cho tập hợp số Hãy tìm số m nhỏ nhất sao cho mỗi tập con chứa m phần tử của tập M đều tồn tại ít nhất hai số a, b thoả số này là bội của số kia
Hướng dẫn giải
Ta có có phần tử và không có phần tử nào là bội của ít nhất 1 phần tử khác thuộc C.
Suy ra: phần tử. Ta chứng minh:
Xét 1 tập con P bất kì chứa phần tử của M. Với mỗi đặt
và q là số lẻ, vì nên mà từ 1 đến n
có. số lẻ khác nhau nên trong biểu diễn các phần tử , phải có ít nhất 2 số q lẻ bằng nhau suy ra tồn tại ít nhất 2 số sao cho: Tức là trong 2 số a, b phải có 1 số là bội của số kia.
Bài toán 20.14: Cho n là một số nguyên dương.
Xét như là một tập hợp gồm điểm trong không gian 3 chiều. Hãy xác định số nhỏ nhất có thể các mặt phẳng mà hợp của chúng chứa tất cả các điểm của s nhưng không chứa điểm (0,0,0).
Hướng dẫn giải
Ta thấy 3n mặt phẳng và chứa tất cả các điểm của S và không chứa điểm (0,0,0). Như vậy số mặt phẳng cần tìm không vượt quá 3n.
Để chứng tỏ số mặt phẳng cần tìm đúng bằng 3n, ta chứng minh bỗ đề sau:
Bổ đề: Xét đa thức k biến . Nếu P triệt tiêu tại các điểm của tập hợp
và không triệt tiêu tại điểm (0,0,...,0) thì p có bậc không nhỏ hơn kn.
Chứng minh. Ta chứng minh kết quả bổ đề bằng quy nạp theo k. Dễ thấy kết luận của bổ đề đúng với . Giả sử kết luận bổ đề đúng cho , ta chứng minh kết luận của bổ đề cũng đúng cho k.
Thực vậy, nếu đa thức k biến thoả mãn điều kiện của bỗ đề (trong đó X là biến thứ k), thì ta thực hiện phép chia cho đa thức để được thương là và đa thức dư . Viết lại dạng chính tắc theo luỹ thừa của x ta có: (*)
Ta sẽ chứng minh là đa thức biến thoả mãn điều kiện của bổ đề.
a) là đa thức của x với bậc không vượt quá n và triệt tiêu tại các điểm . Do
cho nên T(0) là đa thức bậc n của x, suy ra hệ số của bậc cao nhất trong khai triển (*) là
b) Với một bộ thoả ta có triệt tiêu tại n+1 điểm . Vì bậc của không vượt quá n, cho nên là đa thức đồng nhất 0, do đó tất cả hệ số của nó trong khai triển (*) bằng 0 và đặc biệt là
Như vậy, là đa thức có bậc không nhỏ hơn (k – 1)n theo giả thiết quy nạp, cho nên là đa thức có bậc không nhỏ hơn kn.
Do đó . Bổ đề đựợc chứng minh.
Bây giờ giả sử N mặt phẳng chứa tất cả các điểm của S nhưng không chứa điểm (0,0,...,0). Khi đó xét

Đa thức này có bậc là N và P(x, y,z) thoả mãn các giả thiết của bổ đề, nên ta có là điều phải chứng minh.
Bài toán 20. 15: Xét hoán vị cua các số 0, 1, 2,...,n, ta tác động một phép biến đổi lên hoán vị này nếu tìm được i, j sao cho và . Hoán vị mới tạo thành nhận được bằng cách đổi chỗ hai phần tử Si và Sj.
Hỏi với số n nào thì xuất phát từ hoán vị ta có thể nhận được hoán vị bằng cách lập lại nhiều lần phép biến đổi đó?
Hướng dẫn giải
Thử trực tiếp, ta thấy rằng có thể thực hiện yêu cầu của bài toán trong trường hợp
, nhưng không thực hiện được khi . Từ đó, ta dự đoán rằng các số dạng và số sẽ thoả mãn điều kiện bài toán.
Ta để ý nếu , thì sau lần biến đỗi ta sẽ có và không thể làm tiếp được. Vậy với n chẵn, ta không thực hiện được .
Nếu ta có thể làm như sau:
(bắt đầu)
(sau 7 lần biến đổi)
(sau; 8 lần biến đổi)
(sau 8 lần biến đổi)
(sau 8 lần biến đổi)
Tổng quát, ta giả sử . Gọi là hoán vị đầu tiên và là hoán vị có dạng:


ở đây R là kí hiệu cho số và dấu phẩy ngăn cách biểu thị rằng, sau hoán vị ban đầu, tăng lên R số hạng. Nếu khởi đầu từ , thì số 0 được chuyển đổi thành công với , rồi với ,
tiếp tục với . Điều này sẽ cho ta . Dễ dàng kiểm tra được
dẫn đến và sau đó đến pm là vị trí kết thúc. Như thế, có thể thực hiện được theo yêu cầu đề bài cho trường hợp .
Tiếp theo, giả sử n lẻ nhưng không có dạng . Lúc đó, ta có thể viết (lấy là luỹ thừa cao nhất của 2 sao cho nó chia hết ).
Ta có thể định nghĩa như trên. Ta có thể đạt đến như trên:


với . Khi đó, 0 được chuyển với , và đặt nó ngay bên phải của , nên không thể tiếp tục được xa hơn, điều này có nghĩa không thể thực hiện được để thoả mãn điều kiện bài toán cho
Bài toán 20.16: Cho S là tập hợp . Ta gọi là số các hoán n vị của S có đúng k điểm cố định. Chứng minh rằng:
Hướng dẫn giải
Ta có: nếu
Để ý:
Từ đó suy ra:

Bài toán 20. 17: Chứng minh rằng tập hợp có thể được viết thành hợp của các tập rời nhau sao cho mọi , đều có chứa 17 phần tử và tổng giá trị của các phần tử những Aị đều bằng nhau.
Hướng dẫn giải
Trước hết, ta xây dựng 117 tập hợp gồm 3 số sao cho tổng của 3 số đó trong mỗi tập đều bằng 0 và chúng rời nhau từng đôi một như sau: Từ tập , ta tạo thành tập , tập hợp này có được bằng cách lấy từng số hạng của tập hợp đã cho trừ đi 995.
Khi đó, ta tạo 116 tập hợp gồm 3 số nói trên là:



…………………………………………

Ngoài ra, ta đặt
Tất cả 117 tập hợp trên đều rời nhau từng đôi một, Thật vậy, trong mỗi tập, do các phần tử thứ hai đều chẵn nên các phần tử thứ hai của các tập hợp không thể trùng với các phần tử thứ nhất hoặc thứ ba của những tập hợp này, tất cả các phần tử thứ nhất của những tập hợp này có giá trị tuyệt đối lớn hơn tất cả phần tử thứ ba, thành thử các tập hợp rời nhau từng đôi một.
Ngoài ra, nếu số x nào đó là phần tử của một trong các tập hợp thì số (-x) cũng là phần tử của một trong các tập hợp . Để ý rằng 14.117 phần tử của tập hợp M, không thuộc về một trong các tập hợp , được chia thành 7.117 cặp số với dấu đối nhau. Bằng cách tuỳ ý ta thêm 7 cặp số phân biệt vào tập hợp đã chọn ở trên, ta sẽ chia được tập hợp M thành 117 tập hợp con từng cặp không giao nhau.
Cuối cùng để thoả mãn yêu cầu của bài toán, ta chỉ cần xây dựng 117 tập Ai bằng cách cộng 995 vào từng phần tử của các tập tương ứng.
Bài toán 20. 18: Trong một kì thi học sinh giỏi toán có một số thí sinh là bạn bè của nhau. Quan hệ bạn bè là quan hệ hai chiều. Gọi một nhóm các thí sinh là nhóm bạn bè nếu như hai người bất kì trong nhóm này là bạn bè của nhau. (Mỗi nhóm tuỳ ý ít hơn hai thí sinh cũng vẫn được coi là một nhóm bạn bè), số lượng các thí sinh của một nhóm bạn bè được gọi là cỡ của nó.
Cho biết rằng, trong kì thi này, cỡ của một nhóm bạn bè có nhiều người nhất là một số chẵn. Chứng minh rằng có thể xếp tất cả các thí sinh vào hai phòng sao cho cỡ của nhóm bạn bè có nhiều người nhất trong phòng này cũng bằng cỡ của nhóm bạn bè có nhiều người nhất trong phòng kia
Hướng dẫn giải
Ta gọi cỡ của một tập hợp A, kí hiệu là c(A), là cỡ của nhóm bạn bè đông người nhất trong A. Gọi M là nhóm bạn bè đông người nhất trong tập hợp G tất cả các thí sinh, như vậy là số chẵn. Ta chỉ ra một cách phân hoạch G thành hai tập hợp có cùng cỡ như sau:
Trước hết A là một tập hợp m thí sinh của M và. Như vậy Chừng nào ta chuyển một thí sinh của M từ B sang A. Mỗi lần như vậy cỡ của B giảm không quá 1 và cỡ của A tăng đúng 1.
Do đó, ta có thể thực hiện được việc điều chỉnh này cho tới khi hoặc . Trong trường hợp ta thực hiện tiếp việc điều chỉnh mới bằng cách xét tất cả nhóm bạn bè gồm c(B) người trong B. Nếu tồn tại và sao cho thì tập hợp và là hai tập hợp có cùng cỡ . Nếu với mọi và thì luôn khác tập rỗng vì có ít nhất phần tử còn chỉ có nhiều nhất m phần tử. Xuất phát từ ta chọn một phần tử của vào C, với là nhóm bạn bè nào đó có c(B) người trong tập hợp . Quá trình kết thúc khi thu được một tập hợp c sao cho .
Ta chứng minh . Thật vậy, xét một nhóm bạn bè Q tuỳ ý trong
. Do mỗi phần tử của c là bạn bè của mọi phần tử cho nên là một nhóm bạn bè trong G và do đó:
.
Vậy và là phân hoạch của G thành hai tập hợp có cùng cỡ (đpcm).
Bài toán 20. 19: Trong kỳ thi Olympic có 17 học sinh thi Toán được mang số ký danh trong khoảng từ 1 đến 1000. Chứng tỏ rằng có thể chọn ra 9 học sinh thi Toán có tổng các số ký danh được mang chia hết cho 9.
Hướng dẫn giải
Xét 5 số tự nhiên tuỳ ý, khi chia cho 3 có thể xảy ra: Có 3 số dư giống nhau Tổng 3 số tương ứng chia hết cho 3. Trái lại, sẽ có 3 số dư đôi một khác nhau Tổng 3 số tương ứng chia hết cho 3.
Vậy trong 5 số tự nhiên bất kì, tồn tại 3 số có tổng chia hết cho 3.
Xét 17 số tự nhiên tuỳ ý: Chia chúng thành 3 tập, có lần lượt 5, 5, 7 phần tử. Trong mỗi tập, chọn được 3 số có tổng lần lượt là: còn lại:
số, trong 8 số này, chọn tiếp 3 số có tổng là , còn lại 5 số, chọn tiếp 3 số có tổng là .
Trong 5 số có 3 số có tổng chia hết cho 3. 9 học sinh tương ứng có tổng các số kí danh là:

Bài toán 20. 20: Cho 75 điểm trong hình lập phương có cạnh 1. Chứng minh rằng tồn tại một tam giác có 3 đỉnh trong số các điểm đó có diện tích không quá
Hướng dẫn giải
Trước hết ta chứng minh bổ đề sau:
Bổ đề: Trong hình lập phương cạnh a có 3 điểm, khi đó diện tích tam giác có 3
đỉnh tại các điểm đó không lớn hơn
Chứng minh: Dựa vào nhận xét đơn giản sau: trong không gian cho 5 điểm B, C, M, A, N trong đó M, A, N theo thứ tự nằm trên một đường thẳng, khi đó:

Ta suy ra diện tích tam giác ABC không lớn hơn diện tích tam giác có đỉnh là đỉnh của hình lập phương. So sánh diện tích các tam giác này, ta thấy tam giác có cạnh là các đường chéo của các mặt bên có diện tích lớn nhất.
Diện tích đó bằng . Và như vậy bổ đề được chứng minh.
Quay lại bài toán, ta chia hình lập phương thành 27 hình lập phương nhỏ cạnh 1/3. Vì nên theo nguyên lý Dirichlet, tồn tại 3 điểm trong số 75 điểm đã cho nằm trong 1 hình lập phương nhỏ nào đó. Diện tích tam giác có đỉnh tại ba điểm này có diện tích không lớn hơn (đpcm).
Bài toán 20. 21: Có 1991 học sinh đứng thành vòng tròn và quay mặt vào giữa để chơi trò đếm số như dưới đây. Mỗi học sinh đếm một số lần lượt theo chiều kim đồng hồ, bắt đầu từ học sinh A nào đó. Các số đếm được là 1, 2, 3 và cứ lặp lại theo thứ tự như thế. Nếu học sinh nào đến số 2 hoặc số 3 thì phải rời ngay khỏi vị trí ở vòng tròn. Học sinh còn lại cuối cùng sẽ được thưởng. Hỏi học sinh muốn nhận phần thưởng thì lúc bắt đầu chơi phải chọn vị trí thứ bao nhiêu theo chiều kim đồng hồ kể từ học sinh A đếm số 1 lần đầu tiên?
Hướng dẫn giải
Xét 2 trường hợp:
1) Trường hợp có học sinh đứng thành vòng tròn Nếu chia học sinh thành từng nhóm 3 người theo số đếm 1,2,3 thì có nhóm. Sau 1 vòng đếm thì số học sinh ra khỏi vòng là và còn lại học sinh. Chú ý rằng học sinh B đếm số 1 đầu tiên trong vòng đầu sẽ lại đếm số 1 đầu tiên ở mỗi vòng nên sẽ ở lại đến cuối cùng và sẽ được nhận thưởng.
2) Trường hợp có 1991 học sinh
Ta có: . Ta đưa về trường hợp 1 bằng cách tính xem đến khi nào còn lại học sinh thì học sinh B đếm số 1 đầu tiên trong 729 người sẽ được thưởng.
Như vậy: cần có học sinh rời khỏi vị trí có nhóm 3 người, do đó cần có học sinh đứng trước học sinh B đếm số 1 đầu tiên trong 729 người còn lại.
Vậy nếu chọn số 1 đầu tiên trong số 1991 người thì học sinh B đứng ở vị trí thứ 1894 sẽ là người đếm sổ 1 đầu tiên trong 729 người, do đó sẽ còn lại đến cuối cùng và được thưởng.
Bài toán 20. 22: Tại đỉnh của đa giác người ta đặt n viên bi. Thực hiện việc chuyển chỗ các viên bi theo cách sau: mỗi lần lấy một viên bi ở A, rồi đặt vào một đỉnh kề và đồng thời lấy một viên bi ở rồi đặt nó vào một đỉnh kề với (có thể i = j).
Hãy tìm tất cả giá trị của n sao một số hữu hạn lần thực hiện việc chuyển bi nói trên một cách thích hợp thì ở mỗi đỉnh đều có một viên bi.
Hướng dẫn giải
Ta thấy (k là số tự nhiên > 2) thoả mãn bài ra.
Vậy ta xét với k tự nhiên . Ta tô các đỉnh với hai màu xanh, đỏ sao cho đỉnh được tô màu đỏ; với mỗi đỉnh có màu khác với màu của đỉnh kề với nó.
Ta nhận thấy rằng: trong mỗi lần chuyển bi, mỗi bi đều được chuyển từ đỉnh có màu này sang đỉnh có màu kia. Vì thế, sau mỗi lần chuyển bi, tổng số bi có tại tất cả các đỉnh được tô màu xanh không thay đổi tính chẵn, lẻ. Suy ra có thể xếp được vào mỗi đỉnh một bi chỉ khi hay . Ngược lại, với , thực hiện việc chuyển bi theo cách sau đây chẳng hạn: Lần lượt, với mỗi ở bước thứ 1 ta làm như sau: Lấy 2 bi ở , chuyển chúng qua các đỉnh tới đỉnh thì dừng lại. Sau bước thứ , tại đỉnh sẽ có 1 bi, tại mỗi đỉnh đều có 2 bi, còn tại các đỉnh đều không có bi. Sau đó lần lượt với mỗi ở bước thứ k ta làm như sau: Lấy 1 bi ở chuyển sang , đồng thời lấy 1 bi ở chuyển sang (quy ước coi là )- Sau bước thứ , tại mỗi điểm sẽ có 1 bi. Vậy tất cả giá trị phải tìm là
Bài toán 20. 23: Từ bảng


Hãy chọn n số sao cho không có hai số nào đứng trong cùng một dòng và không có 2 số nào nằm trong cùng một cột của bảng. Tính tổng n sổ đã chọn.
Hướng dẫn giải
Kí hiệu là số ở hàng thứ i, cọt thứ j và để ý đến cấu tạo của bảng thì ta có: Muốn có n số thoả mãn đầu bài, ta chỉ việc lấy n số sau:
trong đó là số thứ tự chỉ cột và nếu .
Như vậy nếu hoán vị các cho nhau, ta được tất cả n! cách chọn Muốn có cách chọn khác ta chỉ việc hoán vị và cho nhau mà phép hoán vị không làm thay đổi tổng của hai số đã cho, nên mọi cách chọn đều có chung một tổng. Gọi tổng của n chữ số đó là S ta có:


Mà
Nên
Bài toán 20. 24: Tồn tại hay không một cách xếp 100 số nguyên: vào trong một lưới vuông gồm 10 hàng 10 cột (mỗi ô vuông một số) sao cho nếu a và b là hai số đứng kề nhau trên một hàng hoặc trên một cột thì ít nhất một trong hai phương trình có nghiệm nguyên?
Hướng dẫn giải
Đặt Giả sử nguyên tố. Khi đó:
Nếu phương trình có nghiệm nguyên, thì theo định lý Vi-ét, cả hai nghiệm của nó đều nguyên và dương; hơn nữa, do p là số nguyên tố,

Nếu phương trình có nghiệm nguyên. Cả hai nghiệm của phương trình này cũng nguyên dương và , nên


Suy ra:
Nhưng do
nếu p thỏa: thì chỉ còn khả năng
Từ hai trường hợp trên, ta thấy: nếu tồn tại một cách xếp 100 số của S vào trong một lưới vuông gồm 10 hàng 10 cột sao cho yêu cầu của bài toán được thỏa mãn, thì mỗi số nguyên tố p thỏa (1) của s có tối đa 2 số đứng kề với nó, là ; vậy, chỉ có thể xếp p vào một trong 4 ô vuông ở góc của lưới vuông đó.
Nhưng S có nhiều hơn 4 số nguyên tổ thỏa nên ta không thể xếp hết chúng vào lưới vuông.
Mâu thuẫn đó chứng tỏ rằng: không thể tồn tại một cách xếp thỏa yêu cầu bài toán.
Bài toán 20. 26: Một bảng vuông gồm ô với mỗi ô có chứa một hoặc không hòn đá. Tìm số bé nhất các hòn đá để cho khi chọn một ô trống bất kì, tổng số các hòn đá trong hàng và cột tương ứng với ô trống này ít nhất là 1999.
Hướng dẫn giải
Ta hãy xếp các hòn đá len bảng vuông sao cho ở bốn góc đều có bốn hòn đá, và sắp xếp toàn bảng như hình bàn cờ(ô đen có một hòn, ô trắng không có – có dạng như hình 5x5 bên cạnh).
Dễ thấy cách sắp xếp này thoả mãn điều kiện đề bài.
Tổng số các hòn đá được dùng trong cách sắp xếp này là:
(hòn đá) Ta sẽ chứng minh rằng 1998001 là số bé nhất cần tìm.
Giả sử các điều kiện của bài toán được thoả mãn, trong đó, k là số bé nhất các hòn đá trong một hàng hay cột bất kì.
Không mất tính tổng quát, có thể giả sử rằng có một cột nào đó chứa k hòn đá. Trong cột này, tương ứng với mỗi một trong k hòn đá, hàng có chứa hòn đá đó phải chứa ít nhất k hòn đá, do giả thiết k là số bé nhất các hòn đá trong một hàng hay cột bất kì. Với ô trống của cột này, tương ứng với một ô trống, để thoả mãn điều kiện đã nêu, hàng chứa ô trống phải chứa ít nhất hòn đá. Vậy tổng số các hòn đá ít nhất phải là:

Tóm lại, số cần tìm là 1998001.
Bài toán 20. 26: Một khối bằng gạch có dạng hình của một tam cấp gồm ba bậc có bề rộng là 2 được làm từ 12 khối hình lập phương đơn vị. Hãy xác định số nguyên n sao cho ta có thể dựng một khối lập phương cạnh n từ các khối bằng gạch (dạng tam cấp) ấy.
Hưởng dẫn giải
Thể tích trọn viên gạch (dạng tam cấp) bằng 12, nên điều kiện ắt có là cạnh của hình lập phương phải là bội của 6. Hai viên gạch có thể gắn với nhau dễ dàng để tạo thành một hình hộp chữ nhật kích thước , và hình hộp chữ nhật này có thể xếp thành hàng để tạo thành một hình lập phương cạnh 1 hay thành một hình lập phương bất kì có cạnh là bội của 12.
Đảo lại, ta sẽ chứng minh rằng: Một hình lập phương cạnh chỉ có thể tạo thành theo điều kiện bài toán nếu chẵn.
Thật vậy, giả sử một hình lập phương như thế được tạo xong, thế thì ta đã sử dụng
viên gạch (dạng tam cấp). Ta chuyển hình lập phương này vào trong góc phần tám của hệ trục toạ độ trong không gian với một đỉnh của hình lập phương nằm tại gốc Tô màu mỗi cạnh của hình lập phương đơn vị

bằng một trong tám màu, tuỳ theo tính chẵn lẻ của bộ ba. Trong mỗi viên gạch, tất cả tám màu đều có sáu trong tám mày ấy
xuất hiện chỉ trong một hình lập phương đơn vị, và mỗi một trong hai màu còn lại có mặt trong ba hình lập phương đơn vị.
Ta chọn một trong tám màu và gọi p là số viên gạch mà trong đó màu này xuất hiện ba lần. Trong hình lập phương có m viên gạch, màu này xuất hiện cả thảy
lần.
Mặt khác, tám màu được phân phối đều trong hình lập phương cạnh , cho nên mỗi màu xuất hiện đúng lần. Suy ra rằng và thế là . Như vậy m là bội của 4 và phải là số chẵn.
Bài toán 20. 27: Tại một cuộc khiêu vũ, một nhóm S gồm 1994 học sinh đứng thành một vòng tròn lớn. Mỗi học sinh sẽ vỗ vào tay một trong hai học sinh kề hai bên một số lần. Với mọi học sinh x, ta gọi f(x) là tổng tất cả các số lần mà X vỗ vào tay những người bạn đứng kề. Chẳng hạn, ta giả sử có 3 học sinh A, B và C, A vỗ vào tay B hai lần, B vỗ vào tay C ba lần và C vỗ vào tay A năm lần. Như thế, ta có:

a) Chứng minh là số nguyên
b) Tìm một số ví dụ chứng tỏ: là số nguyên,
Hướng dẫn giải
a) Để ý rằng hai lần tổng số các lần vỗ vào tay là một số chẵn, và bằng f(x) số này và bằng không thể bằng số lẻ:
b) Cho . Với một nhóm sn gồm học sinh, biểu đồ sau đây cho ta ví dụ chứng tỏ. là số nguyên,





Mỗi vòng tròn trên biểu đồ biểu diễn một học sinh x và con số trong vòng tròn biểu diễn f(x). số nằm trên các cung tròn thì biểu diễn số lần 2 học sinh kề nhau vỗ vào tay nhau. Chọn , ta có được ví dụ thoả mãn bài toán.
Bài toán 20. 28: Cho là một số nguyên. Một con đường từ tới trong mặt phẳng xOy được định nghĩa là một chuỗi các di chuyển liên tiếp của đơn vị sang phải (di chuyển này được kí hiệu bởi E) hay lên trên (di chuyển này được kí hiệu bởi N), mọi di chuyển được thực hiện trong nửa mặt phẳng . Một bước nhảy trên con đường là sự kết hợp của hai di chuyển liên tiếp có dạng EN. Chứng minh rằng số các con đường từ đến mà chứa đúng s bước nhảy là bằng

Hướng dẫn giải
Một con đường với s bước nhảy từ đến được gọi là một con đường kiểu. Cho là số con đường kiểu và đặt
Ta sẽ chứng minh bằng quy nạp theo n rằng với . Dễ dàng thấy rằng:

Cho và giả sử rằng với . Rõ ràng là . Ta sẽ chứng minh rằng với
Ta nói một con đường kiểu và một con đường kiểu là liên đới với nhau nếu con đường sau thu được từ con đường trước bằng cách hoặc nhét thêm vào con đường thứ nhất một cặp EN giữa hai di chuyển liên tiếp có dạng (E, E), (N, N) hay (N, E), hoặc thêm vào một cặp EN ở cuối con đường. Ta cũng nói rằng con đường kiểu và con đường kiểu là liên đới nếu con đường dài hơn có được từ con đường ngắn hơn bằng cách thêm một cặp EN vào giữa (E, N).
Mỗi con đường kiểu liên đới với con đường kiểu khác; mỗi con đường kiểu liên đới với con đường kiểu khác; mỗi con đường kiểu liên đới với đúng con đường kiểu hay. Vì thế số các cặp liên đới là:

Dễ dàng kiểm chứng được rằng:
và khi đó

Chú ý: Nếu , số các con đường từ đến có s bước nhảy sẽ được cho bởi . Điều này được chứng minh bằng quy nạp theo m:
Bài toán 20. 29: Có 18 người tham gia một cuộc thi đấu gồm 17 vòng đấu.
Mỗi vòng có 9 trận thi đấu và trong mỗi vòng, mỗi đấu thủ tham gia một trận. Mỗi người đều thi đấu với người khác đúng một trận trong suốt cuộc thi đấu. Tìm số n lớn nhất sao cho nếu có xếp lại cuộc thi đấu (theo nguyên tắc trên) ta vẫn có thể tìm được 4 người trong số 18 người tham gia, mà họ chỉ chơi đúng một trận vào lúc kết thúc vòng đấu thứ n.
Hướng dẫn giải
Câu trả lời là n = 7 Đầu tiên, ta chứng minh không thoả mãn Thật vậy, khi
ta chỉ ra một sự sắp xếp để không thoả mãn như sau: Gọi A là tập con của một tập gồm 9 cầu thủ và B phần bù của A trong tập 9 cầu thủ đó. Lúc đó, ở 8 vòng thi đấu đầu tiên, ta có thể sắp xếp sao cho mỗi phần tử của B thi đấu với mọi phần tử khác của B. Ta chỉ cần chỉ ra rằng có một cuộc đấu gồm vòng trong số 2N đấu thủ sao cho có N trận đấu ở mỗi vòng và mỗi người đều thi đấu với người khác đúng một trận trong suốt cuộc thi đấu đó. Ta đánh số các đấu thủ là . Đánh số các vòng đấu là . Giả sử hai đấu thủ khác nhau i, j (không phải X) thi đấu ở vòng . Cho i và X đấu nhau ở vòng
. Dễ dàng kiểm tra rằng cách sắp xếp như vậy thoả mãn yêu cầu.
Bây giờ ta xét trường hợp . Gọi S là tập hợp lớn nhất gồm các cầu thủ mà không có hai người nào trong đó đấu với nhau, gọi S là tập hợp các đấu thủ còn lại. Chọn A trong S là một người đã chơi với vài đấu thủ trong S. Giả sử , ta có . Ta sẽ chứng minh rằng A đã chơi nhiều nhất là với phần tử của S. Giả sử điều ngược lại xảy ra. Mỗi đấu thủ đã chơi 7 trận, do tất cả các phần tử của s đều có chơi với các phần tử của S nên đã có 7m trận diễn ra giữa các phần tử của S và các phần tử của S. Nếu mọi phần tử của S đã chơi với hay nhiều hơn các phần tử của S thì có ít nhất trận diễn ra giữa các phần tử của S và các phần tử của S, suy ra , , do đó
hoặc . Rõ ràng không thể có (vì chắc chắn có hai đấu thủ không chơi với nhau). Còn nếu thì do A chỉ chơi có 7 trận nên anh ta đã chơi ít hơn phần tử của S.
Vì vậy, ta có thề tìm được B và C thuộc S sao cho A không chơi với B hay C. Vì A không thuộc S và S lớn nhất như đã nói trên nên phải có D thuộc S là người đã chơi với A. Như thế A, B, C, D là 4 người cần tìm mà trong số họ chỉ chơi có một trận (A với D).
Bài toán 20. 30: một cuộc họp có 12k người, mỗi người trao đổi lời chào với đúng
người khác. Với hai người bất kì nào đó, số người trao đổi lời chào với cả hai người này là giống nhau.
Hỏi có bao nhiêu người tham dự cuộc họp?
Hướng dẫn giải
Với hai người bất kì, ta gọi n là số cố định những người khác có trao đỗi lời chào với cả hai. Xét một người đặc biệt a. Gọi B là tập hợp những người có trao đồi lời chào với a, và C là tập hợp những người không trao đổi lời chào với a. Thế thì có người trong B và người trong C. Với một người b bất kì trong B, thì người có trao đổi lời chào với a và b phải thuộc B. Như thế b đã trao đổi lời chào với n người trong B, và như thế với người trong C.
Với một người c bất kì trong C, người trao đồi lời chào với a và c cũng phải thuộc B. Do đó c đã trao đổi lời chào với n người trong B. Tổng số lời chào được trao đổi giữa B và C được cho bởi:

Suy ra với m nguyên dương và
Nếu thì và 4m sẽ không phải là một số nguyên.
Với , chỉ có làm cho số nhận giá trị nguyên. Vậy có tất cả 36 người tại cuộc họp.
Bài toán 20. 31: Trong mặt phẳng cho n đường thẳng đôi một cắt nhau nhưng không cùng đi qua một điểm. Chứng minh rằng tồn tại ít nhất một điểm là giao của hai và chỉ hai trong số n đường thẳng đó
Hướng dẫn giải


Gọi là n đường thẳng đã cho. Kí hiệu giao của hai đường thẳng là. Xét các khoảng cách từ điểm tới đường thẳng không đi qua nó. Vì số các khoảng cách đó là hữu hạn nên phải tìm được 3 đường thẳng (chẳng hạn ) sao cho khoảng cách từ điểm tới đường thẳng là ngắn nhất (hoặc một trong những khoảng cách ngắn nhất).
Ta chứng minh rằng không còn một đường thẳng thứ ba nào (khác ) lại đi qua điểm . Trước hết ta nhận thấy rằng nếu qọi H là chân đường vuông góc hạ từ tới thì H phải thuộc đoạn thẳng nối và .
Thật vậy nếu H nằm ngoài đoạn thẳng đó và gần H hơn thì rõ ràng khoảng cách từ tới còn nhỏ hơn .
Bây giờ giả sử rằng qua còn có đường thẳng . Khi đó phải cắt a, tại một điểm , điểm này phải nằm trên một trong hai tia có gốc H của đường thẳng . Giả sử nó nằm trên tia chứa điểm thì rõ ràng khoảng cách từ tới nhỏ hơn. Vô lý!.
Bài toán 20. 32: Cho một đa giác đều 2007 đỉnh. Tìm số nguyên dương k nhỏ nhất thoả mãn tính chất: Trong mỗi cách chọn k đỉnh của đa giác luôn tồn tại 4 đỉnh tạo thành một tứ giác lồi mà 3 trong số 4 cạnh của nó là 3 cạnh của đa giác đã cho.
Hướng dẫn giải
Gọi các đỉnh của đa giác đều đã cho là
Chú ý rằng tứ giác (tạo nên từ 4 trong số các đỉnh của đa giác) có 3 cạnh là 3 cạnh của đa giác khi và chỉ khi 4 đỉnh của tứ giác đó là 4 đỉnh liên tiếp của đa giác.
Gọi A là tập các đỉnh:
(bỏ đi các đỉnh và ). Hiển nhiên và trong A không chứa 4 đỉnh liên tiếp nào của đa giác. Dễ thấy, mọi tập con của A đều không chứa 4 đỉnh liên tiếp của đa giác. Vậy . Ta sẽ chứng minh mọi cách chọn 1506 đỉnh tuỳ ý của đa giác thì sẽ tồn tại 4 đỉnh liên tiếp của đa giác trong 1506 đỉnh đó. Thật vậy, giả sử T là một tập gồm 1506 đỉnh tuỳ ý của đa giác. Phân hoạch tập các đỉnh của đa giác thành các tập hợp.


Giả sử T không chứa 4 đỉnh liên tiếp của đa giác. Lúc đó với mỗi, tập không thuộc T, tức là mỗi tập đó sẽ có ít nhất một đỉnh không thuộc T. Khi đó . Do nên và mỗi tập ó đúng 3 phần tử thuộc T.
Ta có suy ra


Khi đó 4 đỉnh liên tiếp thuộc T, mâu thuẫn Vậy
Có thể giải ngắn gọn hơn bằng cách xét điểm còn lại chia đường tròn ngoại tiếp đa giác đều đã cho không quá 501 cung, và phải có một cung trong chúng chứa không ít hơn đỉnh liên tiếp.
Bài toán 20. 33: Có bao nhiêu cách tô màu đỏ cho 16 khối lập phương đơn vị của khối lập phương , sao cho mỗi khối (và mỗi khối hay
) có chứa đúng một khối lập phương đơn vị màu đỏ?
Hướng dẫn giải
Mấu chốt của vấn đề là chứng tỏ tồn tại một song ánh giữa tập các sắp xếp chấp nhận được (tức là thoả mãn yêu cầu đề bài) và tập các hình vuông Latin (Một hình vuông ô được gọi là một hình vuông Latin nếu nó chứa n phần tử
và mỗi hàng hoặc mỗi cột đều có chứa đựng n phần tử này).
Ở mặt đỉnh của khối lập phương, ta viết các sổ 1, 2, 3 hoặc 4 lên mỗi hình vuông (của mặt đỉnh này) tuỳ theo khoảng cách đến khối đơn vị có màu đỏ tính từ trên xuống. Chú ý rằng dưới mỗi hình vuông (trên mặt đỉnh) chắc chắn có ít nhất một khối đơn vị màu đỏ. Có 16 hình vuông, và chỉ có 16 khối đơn vị đó, do đó chắc chắn trong mỗi cột có đúng một khối đơn vị đỏ. Bây giờ, phải có một số 1 trong mỗi hàng của mỗi hình vuông, vì nếu không thì sẽ không có khối đơn vị đỏ nào trong khối cột tương ứng. Tương tự như thế, phải có các số 2, 3 và 4. Như vậy, mỗi hàng phải là một hoán vị của 1, 2, 3, 4. Lí luận tương tự cho mỗi cột. Do đó, hình vuông (trên mặt đỉnh) phải là hình vuông Latin. Đảo lại, một hình vuông Latin cũng tương ứng với một sắp xếp chấp thuận được.
Như thế, việc còn lại là tính xem có bao nhiêu hình vuông Latin như thế. Dễ thấy có đúng 4 hình vuông theo mẫu như hình bên trái, đó là:


Đến đây, có thể tiếp tục lí luận dựa trên các hoán vị để chứng tỏ có tất cả khả năng sắp xếp một hình vuông Latin.
Bài toán 20. 34: Cho tam giác ABC. Nếu ta sơn các điểm của mặt phẳng bằng hai màu xanh và đỏ, hãy chứng minh rằng hoặc là tồn tại hai điểm màu đỏ có khoảng cách bằng một đơn vị, hoặc là tồn tại ba điểm màu xanh tạo thành một tam giác bằng tam giác ABC.
Hướng dẫn giải
Ta sẽ gọi một đa giác là đa giác xanh (tương ứng, đỏ) nếu nó có tất cả các đỉnh cùng màu xanh (tương ứng, đỏ) ta cũng gọi một đoạn thẳng là đoạn thẳng xanh (tương ứng, đỏ) nếu đoạn thẳng đó có hai điểm đầu mút cùng màu xanh (tương ứng, đỏ).
Giả sử ngược lại rằng không tồn tại hai điểm màu đỏ có khoảng cách bằng một đơn vị và cũng không tồn tại ba điểm màu xanh tạo thành một tam giác bằng tam giác ABC (*) Kí hiệu a, b, c là ba cạnh của tam giác ABC, không mất tính tổng quát, ta giả sử rằng: .
Đầu tiên ta sẽ chứng minh rằng không có đoạn thẳng đỏ nào có độ dài a cả.
Thật vậy, giả sử XY là một đoạn thẳng đỏ có độ dài a, khi đó, các đường tròn đơn vị nhận X, Y làm tâm sẽ hoàn toàn màu xanh. Gọi Z là điểm sao cho (viết theo các đỉnh tương ứng). Khi đó, đường tròn đơn vị tâm z phải có toàn màu đỏ, vì nếu không thì z màu xanh và tam giác XYZ là tam giác xanh bằng , mâu thuẫn với giả thiết (*). Trên đường tròn đơn vị này chắc chắn có hai điểm màu đỏ có khoảng cách bằng một đơn vị, vô lí.
Bây giờ, toàn mặt phẳng không thể màu xanh, nên có một điểm nào đó màu đỏ mà ta gọi là R. Đường tròn (T) có tâm R và bán kính a phải toàn màu xanh. Khi đó, lấy hai điểm D và E trên (T) sao cho . Vì nên ta có thể dựng điểm F nằm ngoài (T) sao cho (viết theo các đỉnh tương ứng), điểm F phải có màu đỏ. Như vậy, nếu ta quay DE quanh R, thì điểm F sẽ vạch nên một đường tròn bán kính lớn hơn a và có toàn màu đỏ, trên đường tròn này ta có thể tìm được hai điểm màu đỏ có khoảng cách a, mâu thuẫn với chứng minh trên. Như vậy, giả thiết (*) là sai và ta có điều phải chứng minh.
Bài toán 20. 35: Tìm số nguyên dương n bé nhất thoả mãn tính chất sau: Với n điểm đôi một phân biệt, thẳng hàng và thì mọi cách tô màu n điểm đó bằng đúng 2 màu khác nhau đều tồn tại 3 điểm (với
) được tô cùng một màu.
Hướng dẫn giải
Giả sử ta dùng 2 màu là xanh kí hiệu là (X) và đỏ kí hiệu là (Đ)
Bổ đề: Với n điểm đã cho cùa đề bài, nếu ta đặt chúng trên một trục toạ độ xOx sao cho điểm có toạ độ bằng k. Vậy: 3 điểm được tô cùng một màu khi và chỉ khi toạ độ của 3 điểm trên theo thứ tự lập thành một cấp số cộng.
a) Ta chứng minh: Với (và từ đó ) thì tồn tại cách tô màu 8 điểm
sao cho không có 3 điểm nào được tô cùng màu.
Thật vậy: Ta chỉ việc tô các điểm cùng màu (X) và tô các điểm
cùng màu (Đ) đpcm.
b) Ta phải chứng minh: Với n = 9 thì mọi cách tô màu 9 điểm: bằng đúng 2 màu khác nhau đều tồn tại 3 điểm (với) được tô cùng một màu. Thật vậy, Giả sử trái lại rằng: tồn tại cách tô màu 9 điểm trên sao cho mọi bộ 3 điểm (với ) đều bị tô khác nhau. Khi đó, vận dụng Bồ đề trên, ta suy ra rằng: với mỗi chỉ số thì các điểm và phải được tô khác màu (vì: nếu điểm và được tô cùng màu chẳng hạn là màu (X) thì ta cổ thể tô cậc điểm cùng màu (Đ), điều này lại trái với điều giả sử trên). Không mất tính tổng quát ta có thể giả sử tô màu (Đ) màu (Đ) và do đó cùng màu (Đ). Vì 3, 4, 5 là cấp số cộng màu (X) và do đó cũng màu (X). Vì 4, 6, 8 là cấp số cộng
màu (Đ). Vì 7, 8, 9 là cấp số cộng => màu (X). Vì 1, 3, 5 là cấp số cộng màu (X). Vì 2, 5, 8 là cấp số cộng màu (X). Vậy 3 điểm lại cùng màu (X), trái với điều giả sử trên.
Vậy số n phải tìm là n = 9.
Bài toán 20. 36: Cho G tà một đồ thị liên thông gồm k cạnh. Chứng minh rằng có thể đánh số các cạnh bằng tất cả các số sao cho tại mỗi đỉnh thuộc về ít nhất hai cạnh của đồ thị, ta đều có ước số chung lớn nhất của các số nguyên viết trên các cạnh của đỉnh này bằng 1.
Hướng dẫn giải
Ta bắt đầu tại một đỉnh nào đó.
Hãy tưởng tượng rằng ta đang đi dọc theo các cạnh phân biệt của đồ thị, vừa đi vừa đánh số chúng như ta đang đếm: cho đến khi ta không thể đi xa hơn được nữa vì nếu muốn đi thêm phải dừng lại một cạnh đã đi qua.
Nếu có những cạnh không được đánh số thì một trong những cạnh này phải có một đỉnh ta đã đi qua, vì G liên thông. Hãy khởi đầu từ đỉnh này, ta tiếp tục đi dọc theo các cạnh chưa dùng tới, đánh số lại nơi ta đi qua, và tiếp tục như thế cho đến khi một lần nữa ta không thể đi xa hơn. Quá trình này được lặp lại cho đến lúc tất cả các cạnh đều được đánh số.
Bây giờ, ta sẽ chứng minh rằng việc đánh số như trên thoả mãn điều kiện ở đề bài: tại mỗi đỉnh thuộc về ít nhất hai cạnh của đồ thị, ta đều có ước số chung lớn nhất của các số nguyên viết trên các cạnh của đỉnh này bằng 1.
Thật vậy, gọi V là một đỉnh như thế (v thuộc về ít nhất hai cạnh của đồ thị).
Nếu , tức V là đỉnh xuất phát, thì một trong các cạnh chứa đỉnh V đã được đánh số 1, do đó hiển nhiên ta có ước số chung lớn nhất của các số nguyên viết trên các cạnh của đỉnh V này bằng 1. Nếu , giả sử lần đầu tiên ta đánh số V trên đường đi là vào lúc cuối của cạnh được đánh số r.
Vào lúc đó, có nhiều hơn 1 cạnh chưa sử dụng tại đỉnh V, một trong những cạnh này được đánh số . Do đó, ước số chung lớn nhất của các số nguyên viết trên các cạnh của đỉnh V này bằng 1, vì các cạnh này có chứa r và . Suy ra điều phải chứng minh.
Bài toán 20. 37: Cho G là một đồ thị đơn (G không chứa khuyên và không có hai cạnh khác nhau nào nối cùng một cặp đỉnh), có hữu hạn đỉnh. Mỗi đỉnh của G sẽ được tô chỉ một trong hai màu đen hoặc trắng. Giả sử ban đầu tấu cả các đỉnh của G đều có màu đen. Ta được phép thực hiện nhiều lần thao tác: chọn một đỉnh P tùy ý của G rồi đổi màu của P và của mọi đỉnh kề với P (hai đỉnh được gọi là kề nhau nếu chúng được nối với nhau bởi một cạnh).
Hỏi: sau một số hữu hạn lần thực hiện các thao tác như vậy, ta có thể đổi màu của tất cả các đỉnh của G sang trắng hết được hay không?
Hướng dẫn giải
Giả sử . Ta sẽ chứng minh bằng quy nạp theo rằng: sau một số hữu hạn lần thực hiện (các) thao tác như đề toán cho phép, ta có thể đỗi màu của tất cả các đỉnh của đồ thị đã cho sang trắng.
Đpcm rõ ràng là đúng khi .
Giả sử và đpcm đã đủng cho mọi đồ thị với số đỉnh là
Xét một đồ thị với mỗi đỉnh đang được tô đen. Gọi là thao tác “cơ sở”: đổi màu của và của mọi đỉnh kề với trong G.
Ta sẽ chứng minh rằng tồn tại một dãy g gồm một số hữu hạn các thao tác cơ sở mà “hợp thành” của chúng đổi được màu pủa mọi đỉnh của G. (1)
Xét các đồ thị với tập đỉnh tập cạnh của thu được từ tập cạnh E của G bằng cách bỏ đi các cạnh có một trong hai đầu mút là . Theo giả thiết quy nạp, với mỗi, tồn tại một dãy hữu hạn các thao tác cơ sở trong Gị mà hợp thành của chúng đổi được màu của mọi đỉnh của suy ra: tồn tại một dãy gồm một số hữu hạn các thao tác cơ sở trong chính G (như đã vừa được giới thiệu ở trên) mà hợp thành của chúng đổi được màu của tất cả các đỉnh của G, “không kể” đỉnh . Nếu một trong n dãy có hợp thành (của các thao tác “thành phần” trong nó) đỗi được màu của cả đỉnh ( thì chỉ cần lấy đó ta có ngay (1).
Giả sử: mọi dãy đều có hợp thành không đổi được màu của
đỉnh (2)
Xét hai trường hợp :
Với n chẵn: lấy: nghĩa là, g là dãy gồm tất cả các thao tác thành phần liên tiếp trong gr ròi các thao tác thành phần liên tiếp trong, .... cuối cùng là các thao tác thảnh phần liên tiếp trong . Do (2) và do lẻ, dễ thấy g thỏa (1).
Với n lẻ: trong trường hợp này, từ Bổ đề Bắt tay suy ra G có ít nhất một đỉnh bậc chẵn; không mất tính tổng quát, giả sử đó là đỉnh và tất cả các đỉnh kề với đỉnh gồm các đỉnh . Lấy ; do (2), dễ thấy g thỏa (1).
Vậy (1) luôn đúng. Theo nguyên lý quy nạp đpcm đúng cho mọi n.
Bài toán 20. 38: Cho 21 điểm nằm trên đường tròn. Chứng minh rằng có ít nhất 100 cung được xác định bởi các cặp điểm trong các điểm đã cho được nhìn từ tầm dưới một góc không vượt quá 120°.
Hướng dẫn giải
Bổ đề: Cho graph G và A, B, c là 3 đỉnh của G sao cho 2 trong số 3 đỉnh đều được nối với nhau bởi 1 cạnh thì tập hợp gồm 3 đỉnh A, B, c và 3 cạnh AB, AC, BC là một tam giác của G. số tam giác của graph G được kí hiệu là t(G).
Khi đó ta có Định lí Turan : Nếu graph G có n đỉnh và thì số cạnh
của graph
Chứng minh: Gọi A là đỉnh của G có bậc lớn nhất, là k. Gọi là các đỉnh được nối với A. G là graph nhận được từ G bằng cách bỏ A và các cạnh xuất phát từ A. Khi đó số cạnh của số cạnh của G.
Rõ ràng rằng không có cạnh nào nối và , bởi vì ngược lại ta có tam giác tạo thành, trong G chỉ đếm được tất cả các cạnh nối từ các đỉnh của G (trừ ) vì bậc cao nhất của các đỉnh là k nên số cạnh của
. Do đó số cạnh của (đpcm).
Áp dụng vào bài : Từ 21 điểm ta có tất cả cung. Đếm tất cả các cung không vượt quá 180° và đầu mút là 2 trong số 21 điểm đã cho. Nối 2 điểm nào đó bởi 1 cạnh, xác định cung có số đo > 120°. Xét tất cả các cạnh trên tạo thành 1 graph G (có các đỉnh từ 21 điểm đã cho). Không có tam giác nào trong G (nếu ngược lại sẽ có 1 tam giác có tổng lớn hơn 180°) theo định lý Turan có không nhiều hơn cạnh nên phải có ít hơn cung không vượt quá 120°.
Bài toán 20. 39: Cho trước một số số tự nhiên được viết trên một đường thẳng. Ta thực hiện các bước điền số trên đường thẳng như sau: tại mỗi bước, xác định tất cả các cặp số kề nhau hiện có trên đường thẳng theo thứ tự từ trái qua phải, sau đó điền vào giữa mỗi cặp một số bằng tổng của hai số thuộc cặp đó. Hỏi sau 2013 bước, số 2013 xuất hiện bao nhiêu lần trên đường thẳng trong các trường hợp sau:
a) Các số cho trước là 1 và 1000?
b) Các số cho trước là và xếp theo thứ tự tăng dần từ trái qua phải?
Hướng dẫn giải
a) Ta chứng minh có đúng hai số 2013 trong dãy nhận được sau 2013 lần thực hiện. Chú ý ta chỉ quan tâm đến số lần xuất hiện của 2013 nên khi có 2 số đứng kề nhau mà tổng các số đều lớn hơn 2013 hoặc các số đã xuất hiện từ trước đó rồi thì ta không cần liệt kê nữa.
Dãy ban đầu 1,1000
Sau bước 1 1,1001,1000
Sau bước 2 1,1002,1001,2001,1000

onthicaptoc.com Tài liệu bồi dưỡng học sinh giỏi Chuyên đề 20 TỔ HỢP VÀ RỜI RẠC Lê Hoành Phò File word