Tài liệu Bài tập và hướng dẫn giải bài tập toán thi học sinh giỏi

Tổ hợp 1. Lý thuyết cơ bản Các bài toán về tổ hợp cũng rất đa dạng về nội dung, hình thức và phương pháp giải. Bài toán tổ hợp có thể ẩn chứa đường sau các bản chất đại số, số học, hình học … và để giải chúng ta cũng cần vận dụng những kiến thức tổng hợp. Có thể chia các bài toán tổ hợp thành các loại chính sau + Bài toán đếm số phần tử của một tập hợp + Các bài toán về đồ thị, tô màu + Các bài toán trên lưới nguyên, trên bảng vuông + Các bài toán bất biến, đơn biến + Các bài toán trò chơi + Các bài toán hình học tổ hợp + Và một số loại toán khác Để giải bài toán đếm, ta sử dụng các kiến thức cơ bản và nâng cao đã được học, đó là các quy tắc đếm: quy tắc cộng, quy tắc nhân, quy tắc trừ, nguyên lý bù trừ, các số tổ hợp, chỉnh hợp, hoán vị. Ngoài ra, sử dụng các phương pháp đếm nâng cao như Phương pháp song ánh, Phương pháp quan hệ đệ quy, Phương pháp đồ thị, Phương pháp hàm sinh. Định lý. (Đường đi trên lưới nguyên) Số đường đi ngắn nhất trên lưới nguyên từ điểm A(0, 0) đến điểm B(m, n) bằng C mm n . Định lý. (Bài toán chia kẹo Euler) Số nghiệm nguyên không âm của phương trình x1 + x2 + … + xn = k n 1 là C k  n 1 . Định lý. (Nguyên lý bao hàm và loại trừ) Với A1, A2, …, An là các tập hợp bất kỳ, ta có n | Ai | i 1 n  | Ai |  i 1  | Ai  A j |  1 i  j  n n  | Ai  A j  Ak | ...  (1) n 1 | Ai | 1 i  j  k  n Các trường hợp đặc biệt 1) |A  B| = |A| + |B| - |A  B| 2) |A  B  C| = |A| + |B| +|C| - (|A B| + |BC| + |CA|) + |A B C| Mệnh đề. (Nguyên lý của phương pháp song ánh) Hai tập hợp A và B có cùng số phần tử khi và chỉ khi tồn tại một song ánh từ A vào B. i 1 Để giải các bài toán về đồ thị, ta sử dụng các kiến thức cơ bản liên quan đến đồ thị như đỉnh, cạnh, bậc của đỉnh, bổ đề bắt tay, chu trình, đường đi, tính liên thông, cây khung, đồ thị hai phe, các phép thêm đỉnh, bớt đỉnh … Định lý. (Bổ đề bắt tay) Với đồ thị đơn vô hướng G = (X, E) ta có  d ( x)  2 | E | x X Định lý. (Ore) Cho G là đồ thị đơn vô hướng bậc n. Nếu với hai đỉnh không kề nhau u, v bất kỳ ta có d(u) + d(v)  n thì G là đồ thị Hamilton. Định lý. (Euler) Với một đa diện lồi bất kỳ ta luôn có M–C+Đ=2 Trong đó M là số mặt, C là số cạnh và Đ là số đỉnh. Định lý (Redei) Một tournament bất kỳ đều có một đường đi Hamilton. Nhiều bài toán trò chơi hay biến đổi trạng thái được giải quyết một cách khá hiệu quả nhờ khái niệm bất biến, đơn biến. Định nghĩa. Cho tập hợp  (tập hợp các trạng thái) và tập hợp T (tập hợp các phép biến đổi) các ánh xạ từ   . Hàm số f:   R được gọi là bất biến đối với cặp (, T) nếu ta có f(t()) = f() với mọi  thuộc  và với mọi t thuộc T. Nguyên lý bất biến. Nếu f là một bất biến của (, T) và f(’)  f() thì ’ không thể thu được từ  thông quan các phép biến đổi T. Nguyên lý Dirichlet, nguyên lý cực hạn, phép quy nạp toán học cũng là những công cụ thường được sử dụng trong phép giải các bài toán tổ hợp. Mệnh đề. (cơ sở của nguyên lý cực hạn) a) Nếu A là một tập con hữu hạn bất kỳ của R thì A có phần tử lớn nhất và phần tử nhỏ nhất. b) Nếu A là một tập con bất kỳ của N thì A có phần tử nhỏ nhất. Định lý. (Định lý Pick về diện tích đa giác trên lưới nguyên) Cho P là một đa giác có đỉnh là các điểm nguyên trên mặt phẳng, khi đó diện tích của P có thể tính bởi công thức S(P) = I + B/2 – 1 Trong đó B là số điểm nguyên nằm trên chu vi của đa giác, I là số điểm nguyên nằm bên trong đa giác. 2. Một số bài tập có lời giải Bài toán 1. (PTNK 2009) Cho số nguyên dương n. Có bao nhiêu số chia hết cho 3, có n chữ số và các chữ số đều thuộc {3, 4, 5, 6}? Lời giải. Gọi an là số các số có n chữ số lập từ {3, 4, 5, 6} và chia hết cho 3, còn b n là số các số có n chữ số lập từ {3, 4, 5, 6} và không chia hết cho 3. Khi đó ta có an = 2an-1 + bn-1 (1) bn = 2an-1 + 3bn-1 (2) (Giải thích rõ!) Từ (1) suy ra bn-1 = an – 2an-1, thay n  n+1 thì được bn = an+1 – 2an. Thay vào (2), ta được an+1 – 2an = 2an-1 + 3(an – 2an-1)  an+1 – 5an + 4an-1 = 0. Giải phương trình sai phân này, với chú ý rằng a1 = 2, a2 = 6, ta tìm được an  4n  2 . 3 Nhận xét. 1. Nếu thay {3, 4, 5, 6} bằng {1, 2, 3, 4, 5, 6} thì bài toán có thể giải trực tiếp, sử dụng nguyên lý nhân và đáp số là 2.6 n-1. Lưu ý lý luận sẽ thay đổi chút ít nếu thay {3, 4, 5, 6} bằng {2, 3, 4, 5, 6}. 2. Nếu học sinh chưa được học về phương trình sai phân thì cần bổ sung phần kiến thức này, giảng ngắn gọn về cách chuyển phương trình sai phân về bài toán cấp số nhân. Bài toán 2. Cho X = {1, 2, …, n}. Tìm số tất cả các cặp sắp thứ tự (A, B) với A, B là các tập con của X sao cho A không phải là tập con của B và B cũng không phải là tập con của A. Lời giải. Có 2n tập con của E. Từ đó số các tập sắp thứ tự (A, B) các tập con của E là 2n x 2n = 4n. Ta đếm số các bộ (A, B) mà A  B hoặc B  A. Ta có |{(A, B)| A  B hoặc B  A }| = |{(A, B)| A  B}| + | (A, B)| B  A } - |{(A, B)| A  B và B  A}|. Rõ ràng |{(A, B)| A  B và B  A}| = |{(A, B)| A = B}| = 2n. Để tính |{(A, B)| A  B}| ta lý luận như sau: Nếu |B| = k (k=0, 1, …, n) thì có C nk cách chọn B. Sau khi B được chọn, sẽ có 2k cách chọn A. Từ đó n | {( A, B ) | A  B} |  C nk 2 k  3 n. k 0 Từ đó đáp số của bài toán là 4n – 2.3n + 2n. Bài toán 3. (IMOSL 2007) Với số nguyên dương n > 1 xét S = {1, 2, 3, …, n}. Tô các số của S bằng 2 màu, u số màu đỏ và v số màu xanh. Hãy tìm số các bộ (x, y, z) thuộc S3 sao cho a) x, y, z được tô cùng màu; b) x + y + z chia hết cho n. Lời giải. Cách 1. Gọi R là tập các số được tô màu đỏ và B là tập các số được tô màu xanh. Nếu x, y, đã được chọn thì có duy nhất một cách chọn z = z x,y sao cho x + y + z chia hết cho n. Suy ra có n2 bộ (x, y, z) với x + y + z chia hết cho n. Ta đi đếm các bộ (x, y, z) với x + y + z chia hết cho n nhưng trong 3 số x, y, z xuất hiện cả hai màu. Nếu (x, y, z) là một bộ hai màu thì sẽ có hoặc hai số màu đỏ, một số màu xanh hoặc ngược lại. Trong cả hai trường hợp, sẽ có đúng một trong các cặp (x, y), (y, z) và (z, x) thuộc tập hợp R x B. Ta cho tương ứng cặp này với bộ (x, y, z). Ngược lại, với bộ (x, y) bất kỳ thuộc R x B và ký hiệu z = z x,y. Vì x  y nên các bộ (x, y, z), (y, z, x) và (z, x, y) khác nhau và đều tương ứng với (x, y). Mặt khác, nếu (x, y) được cho tương ứng với 1 bộ ba nào đó thì bộ ba này chính là một trong các bộ ba nói trên. Như vậy mỗi một cặp thuộc R x B được cho tương ứng đúng 3 lần. Từ đó suy ra số bộ hai màu bằng 3.u.v và đáp số của bài toán là n2 – 3uv = (u+v) 2 – 3uv = u2 – uv + v2. Cách 2. Giả sử R = {a1, a2, …, au}, B = {b1, b2, …, bv} tương ứng là tập hợp các số được tô màu đỏ và màu xanh thì R  B = S. x a , Q ( x)   x b và xét đa thức H(x) = P3(x) + Q3(x). Để ý Đặt P( x)   aR bB rằng P 3 ( x)  x ( a ,b , x )R a b c , Q 3 ( x)  3 x ( a ,b , x )B a bc , 3 Nên số các bộ (x, y, z) thuộc S3 sao cho x, y, z cùng màu và x + y + z chia hết cho n chính là tổng các hệ số của xn, x2n, x3n trong H(x). Mặt khác, H(x) = P3(x) + Q3(x) = (P2(x) – P(x)Q(x) + Q2(x))(P(x) + Q(x)) = (P2(x) – P(x)Q(x) + Q2(x))(x + x2 + …+ xn) Giả sử G(x) = P2(x) – P(x)Q(x) + Q2(x) = a0 + a1x + … + amxm Chú ý rằng với mọi số tự nhiên k, tồn tại suy nhất i thuộc (1, 2, …, n) sao cho k+i chia hết cho n. Do đó tổng các hệ số của x n, x2n, x3n trong H(x) đúng bằng tổng các hệ số của G(x) và như vậy bằng G(1) = u2 – uv + v2. Vậy đáp số của bài toán là u2 – uv + v2. Bài toán 4. Tại một hội nghị có 100 đại biểu. Trong số đó có 15 người Pháp, mỗi người quen với ít nhất 70 đại biểu và 85 người Đức, mỗi người quen với không quá 10 đại biểu. Họ được phân vào 21 phòng. Chứng minh rằng có một phòng nào đó không chứa một cặp nào quen nhau. Lời giải. Mỗi một người Pháp phải quen với ít nhất 70 – 14 = 56 người Đức. Suy ra số cặp (Pháp, Đức) quen nhau ít nhất là 15 x 56 = 840. Gọi n là số người Đức quen  9 đại biểu người Pháp (gọi là Đ1) thì ta có: 840  (85-n).10 + n.9. Suy ra n  10. Những người Đức còn lại (Đ 2) đều quen 10 đại biểu người Pháp, do đó không thể quen với người Đức nữa. Vì có 21 phòng và chỉ có 15 người Pháp nên có ít nhất 6 phòng chỉ có toàn người Đức. Vì chỉ có nhiều nhất 10 người Đức có thể quen nhau nên theo nguyên lý Dirichlet, trong 6 phòng này sẽ có ít nhất một phòng chỉ có nhiều nhất 1 người Đức thuộc Đ1. Phòng này chính là phòng cần tìm. Bài toán 5. Trong một buổi gặp mặt có 259 người tham gia. Những người quen nhau bắt tay nhau. Biết rằng nếu A bắt tay B thì một trong hai người A và B bắt tay không quá 8 lần. Hỏi có nhiều nhất bao nhiêu cái bắt tay? Lời giải: Ta chia tập hợp 259 người ra thành hai tập con, L và N. L gồm những người bắt tay quá 8 lần và N gồm những người bắt tay không quá 8 lần. Theo điều kiện đề bài thì những người trong L không bắt tay nhau. Ta xét các trường hợp sau: 1) Nếu |L|  8 thì |N|  251. Vì mỗi một người thuộc N bắt tay không quá 8 lần nên số cái bắt tay không quá 8 x 251 = 2008. 2) Nếu |L| = k < 8. Vì những người thuộc L không bắt tay nhau nên mỗi người thuộc L bắt tay không quá 259 – k cái. Có 259 – k người thuộc N và họ bắt tay không quá 8 cái, suy ra số cái bắt tay sẽ không quá [k(259 – k) + (259 – k) x 8]/2 = (259 – k)(8+k)/2 < 259.15/2 < 2008. Vậy số cái bắt tay không lớn hơn 2008. Mặt khác, ta thấy rằng có thể chỉ ra được cách bắt tay thoả mãn yêu cầu bài toán và có đúng 2008 cái bắt tay: Chọn L và N sao cho |L| = 8 và |N| = 251. Cho những người thuộc L bắt tay với tất cả những người thuộc N thì ta được tập hợp thoả mãn các yêu cầu. Vậy 2008 là số bắt tay nhiều nhất có thể có. Bài toán 6. Chứng minh rằng trong một nhóm có 17 người, trong đó mỗi người có đúng 4 người quen, tìm được 2 người không quen nhau và không có người quen chung. Lời giải. Ta chuyển sang ngôn ngữ đồ thị, mỗi người tương ứng với 1 đỉnh và hai người quen nhau được nối bằng 1 cạnh. Giả sử ngược lại với khẳng định bài toán, mọi đỉnh X đều được nối với 1 trong 16 đỉnh còn lại, hoặc là trực tiếp, hoặc là qua một đỉnh thứ 3. Vì X được nối với đúng 4 đỉnh và mỗi một đỉnh này được nối với đúng 3 đỉnh khác, trong đồ thị sẽ không còn đỉnh nào khác và tất cả các đỉnh đã nhắc đến đều khác nhau. Ngoài ra các cạnh còn lại của đồ thị có số lượng là 17.4/2 – 16 = 18 chỉ có thể nối các đỉnh ngoài. Mỗi một trong 18 cạnh này cho chúng ta một chu trình độ dài 5 đi qua X. Vì X là một đỉnh bất kỳ, qua mỗi một trong 16 đỉnh còn lại cũng có đúng 18 chu trình như vậy. Mỗi một chu trình đi qua đúng 5 đỉnh, suy ra số chu trình bằng 18.17/5, mâu thuẫn. Như vậy khẳng định bài toán được chứng minh. Bài toán 7. (Thanh Hoá 2009) Cho A là một tập hợp gồm 8 phần tử. Tìm số lớn nhất các tập con gồm 3 phần tử của A sao cho giao của 2 tập bất kì trong các tập con này không phải là một tập hợp gồm 2 phần tử. Lời giải. Giả sử ta tìm được n tập hợp con thoả mãn yêu cầu đề bài. Ta chứng minh rằng một phần tử a bất kỳ thuộc A thuộc không quá 3 tập hợp trong số n tập hợp con nói trên. Thật vậy, giả sử có 4 tập hợp chứa a là {a, a 1, a2}, {a, a3, a4}, {a, a5, a6}, {a, a7, a8} thì do ai đều khác a nên phải tồn tại i  j sao cho ai = aj. Không mất tính tổng quát có thể giả sử i = 1. Nếu j = 2 thì {a, a 1, a2} chỉ có 2 phần tử. Mâu thuẫn. Nếu j > 2, chẳng hạn j = 3 thì {a, a 1, a2}  {a, a3, a4} = {a, a1}, mâu thuẫn! Như vậy mỗi một phần tử thuộc không quá 3 tập hợp. Suy ra số lần xuất hiện của tất cả các phần tử của A trong các tập con được chọn không quá 3 x 8 = 24 lần. Vì mỗi một tập con có 3 phần tử nên số tập con không quá 24/3 = 8. Suy ra n  8. Ta chứng minh 8 là số lớn nhất bằng cách chỉ ra 8 tập con như vậy. Điều này có thể làm được khá dễ dàng thông qua bảng sau 1 2 3 4 5 6 7 8 1 X X X 2 X 3 X 4 5 X X 6 7 X X X X X X X X X 8 X X X X X X X X Bài toán 8. (Nghệ An 2009) Gọi S là tập hợp các số nguyên dương đồng thời thoả mãn 2 điều kiện sau: 1.Tồn tại 2 phần tử x, y  S sao cho (x, y) = 1 2.Với bất kỳ a, b  S thì a + b  S Gọi T là tập hợp tất cả các số nguyên dương không thuộc S. Chứng minh rằng số s (T ) , trong đó s(T) là tổng các phần tử của T là hữu hạn và không nhỏ hơn phần tử của tập T (nếu T =  thì s(T) = 0). Bài toán 9. (Thái Lan 2007) 229 học sinh nam và 271 học sinh nữ được chia thành 10 nhóm, mỗi nhóm 50 học sinh được đánh số từ 1 đến 50. Người ta muốn chọn ra một nhóm 4 học sinh, trong đó số học sinh nữ được chọn là lẻ và thoả mãn điều kiện sau đây: 4 người này được chọn từ 2 nhóm và có 2 cặp học sinh có cùng số thứ tự. Chứng minh rằng số cách chọn các nhóm như vậy là một số lẻ. Lời giải. Gọi tập hợp gồm 4 học sinh lấy từ hai nhóm với hai học sinh có cùng số thứ tự là một đội. Giả sử S = { | là một đội}, O = {  S|  có số lẻ học sinh nữ} và E = {  S|  có số chẵn học sinh nữ}. Ta cần chứng minh rằng |O| là lẻ. g ( ) , trong đó g() là số học sinh nữ Với mỗi A  S, ta định nghĩa f ( A)   A của . Vì O  E =  và O  E = S, f(S) = f(O) + f(E). Vì f(E) chẵn, f(S)  f(O) (mod 2). f(S) có thể tìm được bằng cách xét rằng mỗi một học sinh nữ có thể bắt cặp với một học sinh khác trong nhóm bởi 50 – 1 cách, sau đó tìm 2 học sinh khác ở nhóm khác bởi 10 – 1 cách. Suy ra, học sinh nữ này là thành viên của 49.9 đội. Có nghĩa là mỗi một học sinh nữ được tính 49.9 lần trong f(S). Vì ta có 271 học sinh nữ, f(S) = 49.9.271  1 (mod 2). Vì mỗi   O chứa một số số lẻ các học sinh nữ, như thế f(O)  |O| (mod 2). Suy ra |O|  f(O)  f(S)  1 (mod 2) và như vậy số cách chọn những đội như vậy là một số lẻ. Bài toán 10. Có 20 người xếp thành một vòng tròn. Hỏi có bao nhiêu cách chọn ra 5 người sao cho không có hai người kề nhau được chọn. Lời giải. Ta giải các bài toán tổng quát sau Bài toán 10.1. Có n người xếp thành một hàng dọc. Có bao nhiêu cách chọn ra k người, sao cho không có hai người kề nhau được chọn? Cách 1. (Phương pháp song ánh) Đặt En = {1, 2, …, n}. Gọi u1< u2 < …< uk là số thứ tự của những người được chọn thì ta có u i+1 – ui  2 với mọi i=1, …, k-1. Đặt A = {(u1, u2, …, uk)  Ekn | ui+1 – ui  2 với mọi i=1, …, k-1}. Xét ánh xạ f: A  B, trong đó B = {(v1, v2, …, vk)  Ekn-k+1| v1 < v2 < …< vk} xác định như sau f(u1, u2, …, uk) = (v1, v2, …, vk) với vi = ui – (i-1). Ta kiểm tra (v1, v2, …, vk)  B : 1) Rõ ràng vi+1 – vi = (ui+1 – i) – (ui – (i-1)) = ui+1 – ui – 1  1 2) v1 = u1  1, vk = uk – (k -1)  n – k + 1. Ta kiểm tra f là một song ánh. Nếu (u 1, u2, …, uk)  (u1’, u2’, …, uk’) thì rõ ràng ảnh của chúng khác nhau. Suy ra f là một đơn ánh. Ngược lại, với (v 1, v2, …, vk) thuộc B, ta chọn ui = vi + i-1 thì (u 1, u2, …, uk) thuộc A và f(u1, …, uk) = (v1, v2, …, vk). Suy ra f là toàn ánh. Vậy |A| = |B|. Mà |B| thì rõ ràng là bằng số các tập con k phần tử của E n-k+1, do đó bằng C nk k 1 . Cách 2. (Sử dụng bài toán chia kẹo của Euler). Giả sử ta chọn được k người. Gọi x1 là số người tính từng người đầu tiên đến trước người thứ nhất được chọn, x 2 là số người nằm giữa người thứ nhất và người thứ hai, …, x k là số người nằm giữa người thứ k-1 và người thứ k và xk+1 là số người nằm sau người thứ k đến cuối. Khi đó ta có x1 + x2 + … + xk+1 = n – k (1) và x1, xk+1 là các số nguyên không âm, còn x2, …, xk là các số nguyên  1. Ngược lại, nếu (x1, …, xk+1) là một nghiệm của (1) với x1, xk+1  0, x2, …, xk  1 thì ta cho tương ứng với cách chọn người thứ 1+x 1, 2+x1+x2, …, k+x1+…+xk thì rõ ràng do (i + x1 + …+ xi) – (i-1 + x1 + …+xi-1) = 1 + xi  2 nên không có 2 người liên tiếp được chọn. Để hoàn tất lời giải bài toán, ta đặt y 1 = x1, yk+1 = xk+1 và yi = xi – 1 với i=2, …, k thì được y1 + y2 + … + yk+1 = n – 2k + 1 (2) với yi là các số nguyên không âm. Theo kết quả của định lý chia kẹo của Euler, ta có số nghiệm của (2) bằng C nk k 1 . Đó cũng chính là kết quả của bài toán ban đầu của chúng ta. Bài toán 10.2. Có n người xếp thành một vòng tròn. Có bao nhiêu cách chọn ra k người, sao cho không có hai người kề nhau được chọn? Bài toán này có thể giải bằng kết quả của bài toán trên và phương pháp « cắt đường tròn ». Giả sử n người đó được đánh số 1, 2, …, n. Ta xét các trường hợp sau : 1) Người số 1 được chọn. Khi đó người số 2 và số n không được chọn. Như vậy ta phải chọn thêm k-1 người từ 3 đến n-1 sao cho không có hai người kề nhau được chọn. Vì n-1 không kề 3 nên có thể coi đây là n-3 người xếp theo một hàng dọc. Theo kết quả của bài toán trên, số cách chọn bằng C nkk11 . 2) Người số 1 không được chọn. Khi đó ta cần chọn k người từ số 2 đến n sao cho không có 2 người kề nhau được chọn. Vì 2 và n không kề nhau nên có thể coi đây là n-1 người xếp theo một hàng dọc. Theo kết quả của bài toán trên, số cách chọn bằng C nk k . Vậy đáp số của bài toán là C nkk11  C nk k  ( n  k  1)! ( n  k )! ( n  k  1)! n   (k  n  k )  C nkk11 ( k  1)! ( n  2k )! k!( n  2k )! k!( n  2k )! k 3. Bài tập tự giải Bài 1. Hình vuông được chia thành 16 hình vuông con bằng nhau, thu được tập hợp gồm 25 đỉnh. Hỏi cần phải bỏ đi ít nhất bao nhiêu đỉnh của tập hợp này để không có 4 đỉnh nào của tập hợp còn lại là đỉnh của một hình vuông với các cạnh song song với cạnh của hình vuông ban đầu? Bài 2. (Nghệ An 2009) Cho n là số nguyên dương lớn hơn hay bằng 2. Kí hiệu A = {1, 2, …, n}. Tập con B của tập A được gọi là 1 tập "tốt" nếu B khác rỗng và trung bình cộng của các phần tử của B là 1 số nguyên. Gọi T n là số các tập tốt của tập A. Chứng minh rằng Tn – n là 1 số chẵn. Bài 3. (Vũng Tàu 2009) Trên bàn cờ vua kích thước 8x8 được chia thành 64 ô vuông đơn vị, người ta bỏ đi một ô vuông đơn vị nào đó ở vị trí hàng thứ m và cột thứ n. Gọi S(m;n) là số hình chữ nhật được tạo bởi một hay nhiều ô vuông đơn vị của bàn cờ sao cho không có ô nào trùng với vị trí của ô bị xóa bỏ ban đầu. Tìm giá trị nhỏ nhất và giá trị lớn nhất của S(m;n). Bài 4. Ba nhóm đường thẳng song song chia mặt phẳng thành N miền. Hỏi số đường thẳng của cả 3 nhóm ít nhất là bao nhiêu để N > 1981. Bài 5. (Nghệ An 2009) Cho 9 điểm nguyên trên mặt phẳng tọa độ, không có 3 điểm thẳng hàng. Chứng minh ta luôn chọn được 3 điểm thỏa mãn diện tích của tam giác tạo bởi chúng là số chẵn. Bài 6. (Nga 2007, Bắc Ninh 2009) Trong bảng hình vuông gồm 10 x 10 ô vuông (10 hàng, 10 cột), người ta viết vào các ô vuông các số tự nhiên từ 1 đến 100 theo cách như sau: ở hàng thứ nhất, từ trái sang phải, viết các số từ 1 đến 10; ở hàng thứ hai, từ trái sang phải, viết các số từ 11 đến 20; cứ như vậy cho đến hết hàng thứ 10. Sau đó cắt bảng hình vuông thành những hình chữ nhật cỡ 1 x 2 hoặc 2 x 1. Tính tích số của hai số trong mỗi hình chữ nhật rồi cộng 50 tích lại. Cần phải cắt hình vuông như thế nào để tổng tìm được nhỏ nhất ? Bài 7. (Nhật Bản 2007) Ta có 15 tấm thẻ được đánh số 1, 2, …, 15. Có bao nhiêu cách chọn ra một số (ít nhất 1) tấm thẻ sao cho tất cả các số viết trên các tấm thẻ này đều lớn hơn hoặc bằng số tấm thẻ được chọn. Bài 8. Trên một đường thẳng nằm ngang, cho 2005 điểm được đánh dấu trắng hoặc đen. Với mỗi điểm, xác định tổng tất cả các điểm trắng bên phải và điểm đen bên trái của nó. Biết rằng, trong 2005 tổng trên có đúng một số xuất hiện số lẻ lần. Hãy tìm tất cả các giá trị có thể có của số này. Bài 9. (Định lý Mantel – Turan) Chứng minh rằng đồ thị đơn bậc n không chứa tam giác có không quá n2     4  đỉnh. Bài 10. Cho E = {1, 2, …, n}. Tìm số tất cả các bộ ba tập con (A, B, C) thoả mãn đồng thời các điều kiện a) A  B  C = E ; b) A  B  , B  C  . Bài 11. (Bài toán về vé hạnh phúc) Vé xe buýt có dạng abcdef trong đó a, b, c, d, e, f là các chữ số thuộc E = {0, 1, 2, …, 9}. Vé abcdef được gọi là vé hạnh phúc nếu như a + b + c = d + e + f. Hãy tìm số vé hạnh phúc trong các vé từ 000000 đến 999999 theo sơ đồ sau: a) Chứng minh rằng số nghiệm của phương trình a+b+c=d+e+f (a, b, c, d, e, f)  E6 (1) bằng số nghiệm của phương trình a + b + c + d + e + f = 27 (a, b, c, d, e, f)  E6 (2) b) Chứng minh rằng số nghiệm của phương trình (2) bằng số nghiệm của phương trình a + b + c + d + e + f = 27 (a, b, c, d, e, f)  N6 trừ đi số phần tử của N = Na  Nb  Nc  Nd  Ne  Nf, trong đó Na = { (a, b, c, d, e, f)  N6, a + b + c + d + e + f = 27, a  10} (Nb, Nc, Nd, Ne, Nf định nghĩa tương tự). 4. Đáp số, hướng dẫn, lời giải