›
›
›

Tài liệu ôn thi học sinh giỏi Toán Lớp 11 - Chuyên đề: Toán rời rạc (Phần 1) - Ngô Tùng Hiếu

docx 21 trang nhungbui22 11/08/2022 2800
Download
Bạn đang xem 20 trang mẫu của tài liệu "Tài liệu ôn thi học sinh giỏi Toán Lớp 11 - Chuyên đề: Toán rời rạc (Phần 1) - Ngô Tùng Hiếu", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • docxtai_lieu_on_thi_hoc_sinh_gioi_toan_lop_11_chuyen_de_toan_roi.docx

Nội dung text: Tài liệu ôn thi học sinh giỏi Toán Lớp 11 - Chuyên đề: Toán rời rạc (Phần 1) - Ngô Tùng Hiếu

  1. Bài 1. Gọi f n là số cách chọn các dấu cộng,trừ đặt giữa biểu thức: En 1 2 n sao cho En 0 .Chứng minh rằng: a) f n 0 khi n 1,2(mod 4) n n 2 1 b) Khi n  0,3(mod 4) ta có f (n) 2n 2 2 2 Hướng dẫn giải a) Giả sử tồn tại một cách đặt dấu +,- với n 1,2(mod 4) để En 0. n(n 1) Khi đó 1 2 n là số chẵn,vì vậy  0(mod 2) n  0,3(mod 4) ,trái với n 1,2(mod 4) 2 .Vậy giả sử là sai,ta có điều cần chứng minh. 1 n b)Ta chứng minh : f (n) 2n 2 2 ,thật vậy: Chia tất cả các biểu thức thành 2n 1 cặp theo dạng: (1 2a 3a na ;-1 2a 3a na ) với a bằng 1 hoặc 1 2 3 n 2 3 n i Nếu f (n) 2n 1 thì theo nguyên lý Dirichlet tồn tại 2 biểu thức cùng nằm trong một cặp như trên,hiệu của chúng bằng 2 .Do đó chúng không thể cùng bằng 0 được (mâu thuẫn !) 1 n Do đó f (n) 2n 1 2n 2n 1 2n 2 2 (1) n 2 Ta chứng minh f (n) 2 Xét biểu thức En ,gọi An là tập hợp các số xuất hiện trong En với dấu ở trước n n 1 Nếu E 0 thì tổng các phần tử của A là .Ta định nghĩa A như sau: n n 4 n 4 Nếu 1 A thì A A \{1}{n 2,n 4} ; n n 4 n Nếu 1 A thì chọn A A {1,n 1,n 3} n n 4 n
  2. Nếu 2 A thì chọn A A \{2}{n 3,n 4} n n 4 n Nếu 2 A ta chọn A A {2,n 1,n 2} n n 4 n Như vậy với mỗi cách chọn An ta có thể xây dựng ít nhất 4 tập An 4 Giả sử cho trước tập An 4 .Ta thấy tập An 4 được xây dựng từ tập An và thêm đúng một cặp trong tập n 1;n 2;n 3;n 4 và An chứa đúng một cặp như thế. Do đó ta có thể chỉ ra 6 trường hợp khi xây dựng An 4 từ đó xác định được An là duy nhất.Do đó ánh xạ từ An vào An 4 là đơn ánh. Mặt khác với mỗi An xác định được duy nhất một En ,với mỗi En cũng xác định được duy nhất An Do đó f (n 4) 4 f (n).Ta có f 3 f 4 2 . 4k 3 2 Suy ra: f (4k 3) f (4k 1 4) 4 f (4k 1) 42 f (4k 5) 4k f (3) 2 4k 2 f (4k) 4 f (4k 4) 42 f (4k 8) 4k 1 f (4) 2.4k 1 2 n 2 Vì vậy: f (n) (2) 2 Bài 2. Giả sử a1,a2 , ,an là các số thực cho trước. Chứng minh luôn có một số thực x sao cho tất cả các số a1 x,a2 x, ,an x đều là số vô tỷ. Hướng dẫn giải Giả sử t là số vô tỉ bất kì. Ta sẽ chứng minh trong các số t,2t, , n 1 t sẽ có một số thỏa mãn. Giả thiết phản chứng là không có số nào trong các số trên thỏa mãn. Lập bảng n 1 xn như sau: t a1 t a2  t an 2t a 2t a  2t a 1 2 n     n 1 t a1 n 1 t a2  n 1 t an
  3. Có n 1 hàng và n cột. Theo giả thiết phản chứng thì trong mỗi hàng có ít nhất một số hữu tỉ nên có ít nhất n 1 số hữu tỉ trong bảng. Vì có n cột nên có một cột chứa hai số hữu tỉ. Khi đó hiệu của chúng là số hữu tỉ. Vô lí. Bài 3. Trên mặt phẳng có 25 điểm, không có 3 điểm nào trong chúng thẳng hàng. Tìm số màu k nhỏ nhất sao cho ta có thể tô màu tất cả các đoạn thẳng nối hai điểm trong mặt phẳng bởi k màu ( mỗi đoạn thẳng được tô đúng một màu) và các cạnh của một tam giác bất kì tạo bởi 2 điểm trong chúng được tô bởi đúng hai màu. Hướng dẫn giải Dùng định lí Ramsey chứng minh được: Tô màu các cạnh của đồ thị K17 ( đồ thị đầy đủ 17 đỉnh) bằng 3 màu một cách tùy ý thì luôn có một K3 có ba cạnh cùng màu. ( trong các cuốn sách về đồ thị đều trình bày chứng minh, học sinh phải chứng minh lại). Khi đó k 4. Ta đi chứng minh: bằng 4 màu ta có thể tô được các cạnh của K25 thỏa mãn bài ra. Thật vậy, chia 25 điểm thành 5 tập hợp 5 điểm A1,A5 . Trong mỗi Ai lấy các đỉnh trên một ngũ giác đều. Cạnh của ngũ giác con này tô màu 1 và các đường chéo của nó tô màu 2. Sau đó mỗi tập hợp Ai coi là đỉnh một ngũ giác và thực hiện việc tô màu nối các đoạn thẳng của các nhóm Ai , Aj cũng theo cách tương tự với 2 màu còn lại. Ta đi chứng minh cách tô màu này thỏa mãn bài toán Thật vậy : lấy 3 điểm A, B, C tùy ý. Ta xét các trường hợp sau: TH1: A, B, C thuộc một tập 푖 nạo đó. Dễ dàng kiểm tra các cạnh được tô bởi 2 màu. TH2: A, B, C thuộc hai tập hợp khác nhau. Giả sử A, B thuộc cùng một tập, C thuộc tập hợp khác. Khi đó hai cạnh CA, CB được tô cùng màu và cạnh AB được tô khác màu. TH3:A, B, C thuộc ba tập hợp khác nhau. Khi đó trường hợp này giống trượng hợp1. Vậy k nhỏ nhất bằng 4. Bài 4. Cho T là tập hợp gồm vô hạn các số nguyên dương. Trên mặt phẳng (P) cho B là một họ các hình ii T tròn không tính biên của mỗi hình tròn. Chứng minh rằng nếu hình vuông M trên mặt phẳng (P) được phủ kín m bởi họ B thì tồn tại các số nguyên dương t ,t , ,t T sao cho M  B . ii T 1 2 m  ti i 1 Hướng dẫn giải Giả sử hình vuông M không thể phủ bởi hữu hạn các hình Bi . Không mất tính tổng quát ta giả sử hình vuông M là hình vuông ABCD trong đó A 0;0 , B 0;1 ,C 1;1 , D 1;0 . Chia hình vuông M thành 4 hình vuông bằng nhau bởi hai đường thẳng đi qua tâm của M và vuông góc với các cạnh. Trong 4 hình vuông bằng nhau đó có ít nhất một hình vuông M1 sao cho M1 không thể phủ bởi một số hữu hạn các hình Bi . Độ dài cạnh của hình 1 vuông M là . Ta lại chia hình vuông M thành 4 hình vuông bằng nhau bởi hai đường thẳng đi qua tâm 1 2 1 của M1 và vuông góc với các cạnh. Trong 4 hình vuông bằng nhau đó có ít nhất một hình vuông M 2 sao cho
  4. 1 M không thể phủ bởi một số hữu hạn các hình B . Độ dài cạnh của hình vuông M là . Tiếp tục như vậy 2 i 2 22 ta được một dãy các hình vuông M n có các tính chất sau: (i) M  M1  M 2   M n  1 (ii) M là hình vuông có độ dài cạnh là n 2n (iii) Không thể phủ mỗi hình vuông M n bởi một số hữu hạn các hình Bi . Từ tính chất (i) thì tồn tại điểm M 0 M n với mọi số nguyên dương n. Do M 0 M i0 T sao cho 2 M B . Do giả thiết của B và hình vuông M có đường chéo 0 khi n nên M  B với n 0 i0 i0 n 2n n i0 đủ lớn, điều này mâu thuẫn với (iii). Vậy điều giả sử là sai và do đó tồn tại các số nguyên dương m t ,t , ,t T sao cho M  B 1 2 m  ti i 1 Bài 5. Cho 100 số tự nhiên không lớn hơn 100 có tổng bằng 200. Chứng minh rằng từ các số đó có thể chọn được một số số có tổng bằng 100 Hướng dẫn giải Nếu tất cả các số bằng nhau thì tất cả các số là 2. Khi đó ta lấy 50 số 2 sẽ có tổng là 100. Giả sử a1 a2 ta xét 100 số có dạng 0 a1,a2 ,a1 a2 ,a1 a2 a3 , ,a1 a2 a99 200 Nếu có một số chia hết cho 100 thì số đó bằng 100 vì số đó bé hơn 200. Nếu không có số nào chia hết cho 100 thì trong 100 số phải có hai số đồng dư trong phép chia cho 100 (vì các số dư nhận giá trị từ 1 đến 99) suy ra hiệu của chúng chia hết cho 100 và hiệu hai số đó chính là tổng cần tìm Bài 6. Cho các số nguyên a1,a2 , ,a2015 với 0 ai 100, i 1;2015. Với mỗi cặp ai ;ai 1 ta cộng thêm 1 vào cả hai số và mỗi cặp đó không được xuất hiện quá k lần. Tìm k nhỏ nhất sao cho hữu hạn lần thực hiện thao tác trên ta được mọi số bằng nhau. Hướng dẫn giải a1 a3  a2015 100 Ta xét trường hợp các số cạnh nhau cách nhau xa nhất a2 a4  a2014 0 Đặt S a2 a3 a3 a4  a2014 a2015 lúc đầu tiên chưa tác động thì S 1001007 Sau hữu hạn lần tác động tất cả các số bằng nhau do đó khi đó S 0 . Ta nhận xét rằng Tác động lên các cặp a2 ,a3 , a2 ,a3 , , a2014 ,a2015 Thì S không đổi
  5. Tác động lên cặp a1,a2 Thì S tăng lên một đơn vị Tác động lên cặp a2015 ,a1 Thì S giảm 1 đơn vị Bộ a1,a2 bị tác động lớn hơn hoặc bằng 100.1007 lần thì k 100.1007 . Ta sẽ chứng minh k 100.1007 là giá trị nhỏ nhất thoả mãn. Tác động cặp ai 1,ai số lần là ai 1 ai 3  Tác động cặp ai ,ai 1 số lần là ai 2 ai 4  Sau các lần tác động như vậycác số bằng nhau và bằng a1 a2 a2014 a2015.nên số lần tác động 100.1007 suy ra điều phải chứng minh. Bài 7. Chứng minh rằng với mọi số nguyên dương n lớn hơn 1 ta có thể loại bỏ hai số thuộc tập hợp Sn 1,2, ,n sao cho tổng các số còn lại là số chính phương. Hướng dẫn giải Xét tập Sn 1,2, ,n loại đi hai số thuộc Sn và gọi S là tổng các số còn lại thì n n 1 n n 1 n2 3n 2 n2 n 6 n 1 n S 1 2 S 2 2 2 2 n n 1 n n 1 Hơn thế nữa với mọi a n 1 n ; 1 2 thì luôn tồn tại cách xóa đi hai số từ Sn để 2 2 S a . n2 3n 2 n2 n 6 Cuối cùng chỉ cần chứng minh trong đoạn ; có ít nhất một số chính phương 1,0 2 2 Phản chứng: Thật vậy giả sử không tồn tại số chính phương nào thuộc đoạn nói trên nghĩa là với mọi m N* 2 2 n 3n 2 n n 6 2 ta có : m2 m 1 2 2 n2 3n 2 n2 n 6 n2 n 6 n2 3n 2 m m 1 1 2 2 2 2 2n2 14n 21 0 ( Bất đẳng thức này sai với n 5 ) Cuối cùng ta cần kiểm tra với n 4 n 3 xét tập S3 1,2,3 ta loại bỏ hai số 2 và 3 n 4 xét tập S4 1,2,3,4 ta loại bỏ hai số 2 và 4
  6. 1 Bài 8. Cho hình vuông có cạnh 6cm và 2014 đường tròn bán kính cm. Đặt tất cả các đường tròn vào trong 38 hình vuông. Chứng minh rằng tồn tại một đường thẳng cắt 18 đường tròn đã cho. Hướng dẫn giải Chia hình vuông bởi 117 đường thẳng song song cách đều nhau và song song với một cạnh của hình vuông, 6 cách nhau một khoảng cm. Khi đó hình vuông được chia thành 118 dải hình chữ nhật có chiều rộng bằng 118 6 cm, chiều dài bằng chiều dài hình vuông. 118 1 1 6 Hình tròn có đường kính cm, > nên mỗi đường tròn đều bị cắt bởi ít nhất một đường thẳng trên. 19 19 118 Vì 2014 = 118 . 17 + 8 nên theo nguyên lí Dirichlet tồn tại một đường thẳng cắt 18 đường tròn Bài 9. Cho m,n 3là hai số nguyên dương. Trong bảng kích thước m n có dán k ngôi sao (mỗi ô có nhiều nhất là một ngôi sao). Ta thực hiện một công việc là nếu có một hình 2 3 hoặc 3 2 mà có 5 ngôi sao thì ta sẽ dán thêm một ngôi sao vào ô còn lại. Tìm giá trị nhỏ nhất của k sao cho ban đầu trong bảng có k ngôi sao thì sau hữu hạn bước thực hiện việc dán thêm sao như trên thì mọi ô trong bảng đều có ngôi sao. Hướng dẫn giải Sau mỗi một lần thực hiện thuật toán thì ít nhất một hình 2 2với 4 ngôi sao được hình thành. Nếu ban đầu không có hình 2 2 nào với 4 ngôi sao thì sau bước thực hiện sẽ có ít nhất hai hình 2 2 với đầy đủ 4 ngôi sao được hình thành. Do đó sau mn-k bước thực hiện sẽ có ít nhất mn-k+1 hình 2 2 với 4 ngôi sao được hình thành hoặc ít nhất có 1 hình 2 2 với 4 ngôi sao đã có ban đầu và mn-k hình 2 2 có đủ 4 sao được hình thành. Mặt khác, tồn tại đúng (m-1)(n-1) hình 2 2 ở trong bảng, do đó m 1 n 1 mn k 1 Từ đó k m n . Hình vẽ sau đây chỉ ra một ví dụ k= m+n * *
  7. Bài 10. Cho số nguyên n 2 . Chứng minh rằng trong mọi họ gồm ít nhất 2n 1 1 tập hợp con không rỗng phân biệt của tập 1,2, ,n đều tìm được ba tập hợp mà một trong chúng là hợp của hai tập còn lại. Hướng dẫn giải Với n=2 ,ta có {1;2}={1}U{2}. Với n>=2, giả sử có 2n+1 tập con không rỗng của tập {1,2, ,n+1} Nếu ít nhất trong 2n-1+1 tập hợp trong chúng không chứa n+1, theo giả thiết quy nạp ta có đpcm. Nếu ít nhất 2n-1+2 tập hợp chứa n+1 thì bỏ n+1 ra khỏi các tập hợp này và ta áp dụng giả thiết quy nạp Nếu có đúng 2n-1 tập con không chứa n+1 thì có đúng 2 n-1 tập con chứa n+1 (có nhiều hơn 1 phần tử) và tập {n+1} Loại bỏ n+1 trong những tập con này ta được 2n tập con khác rỗng của tập {1,2, ,n}, và do đó trong chúng phải có hai tập trùng nhau, gọi đó là A. Do vậy AU{n+1}=B  1,2, ,n 1(đpcm) Bài 11. Một khu rừng có dạng hình vuông với chiều dài là 1km. Trong khu rừng có 4000 cây thông, cây to nhất có đường kính 0,5 m. Chứng minh rằng trong khu rừng đó có ít nhât 560 mảnh đất , diện tích mỗi mảnh 200m2 không có cây thông nào. Hướng dẫn giải Vì 1km = 1000m = 48.20 + 47.0,6 + 2 . 5,9 1000m = 95.10 + 94.0,52 + 2.0,56 Chia một cạnh hình vuông thành 48 đoạn, mỗi đoạn dài 20m , khoảng cách giữa các đoạn là 0,6m, ở hai đầu là hai đoạn mỗi đoạn dài 5,9m. Chia cạnh còn lại thành 95 đoạn, mỗi đoạn dài 10m, khoảng cách giữa các đoạn là 0,52m, ở hai đầu là hai đoạn mỗi đoạn dài 0,56m. Như vậy có tất cả 48.95 = 4560 mảnh có diện tích 200m2. Vì chỉ có 4000 cây và do đường kính của cây không quá 0,5m nên còn ít nhất 560 mảnh (mỗi mảnh có diện tích 200m2 Bài 12. Có 1650 học sinh được sắp xếp thành 22 hàng và 75 cột. Biết rằng với hai cột bất kì, số cặp học sinh cùng hàng và cùng giới tính không vượt quá 11. Chứng minh rằng số học sinh nam không vượt quá 920 người. Hướng dẫn giải Gọi ai là số học sinh nam trong hàng thứ i, suy ra số học sinh nữ trong hàng i là 75 ai . Số cặp học sinh cùng giới tính trong hàng thứ i là: C 2 C 2 ai 75 ai Do đó, từ điều kiện của bài toán ta có: 22 22 22 C 2 C 2 11C 2 a2 75a 30525 2a 75 2 1650  ai 75 ai 75  i i  i i 1 i 1 i 1 Cùng với BĐT Cauchy-Schwart ta được:
  8. 22 2 22 2  2ai 75 22 2ai 75 36300 i 1 i 1 22 22 191 1650 Suy ra  2ai 75 191  ai 921. i 1 i 1 2 Bài toán được chứng minh hoàn toàn. Bài 13. Cho n là số nguyên dương. Cho 2n điểm trên phân biệt trên một đường tròn được gán giá trị bởi các số 1,2, ,2n (2 điểm khác nhau được gán giá trị khác nhau) theo một cách nào đó. Mỗi dây cung được nối 2 điểm trong các điểm trên và được gán giá trị bằng độ chênh lệch dương giữa 2 đầu mút. Chứng minh rằng ta có thể chọn được n dây cung đôi một không cắt nhau sao cho tổng giá trị của các dây cung bằng n2 Hướng dẫn giải Bổ đề:Trên một được tròn có 2n điểm phân biệt. Người ta tô màu 2n điểm này bằng 1 trong 2 màu màu xanh đỏ sao cho có đúng n điểm được tô màu xanh và đúng n điểm được tô màu đỏ. 2 điểm khác màu nhau bất kì được nối bởi 1 dây cung. Khi đó với mỗi cách tô màu luôn tồn tại n dây cung mà không có 2 dây cung nào cắt nhau. Chứng minh: Ta sẽ chứng minh bổ đề trên bằng quy nạp Dễ thấy bổ đề đúng với n=1 Giả sử bổ đề đúng với mọi n=m Xét n=m+1: Do các điểm chỉ được tô bởi 1 trong 2 màu nên phải tồn tại 2 điểm kề nhau mà chúng được tô khác màu. Ta chọn dây cung có 2 đầu mút là 2 điểm này. Theo giả thiết quy nạp tồn tại cách chọn m cung trong số các dây cung có đầu mút là các điểm trong 2m điểm còn lại mà không có 2 dây cung nào cắt nhau. Rõ ràng không có dây cung nào trong m dây cung này cắt dây cung vừa chọn phía trên. Như vậy tồn tại cách chọn m+1 dây cung mà không có 2 dây cung nào cắt nhau, Bổ đề được chứng minh Trở lại bài toán: Ta tô các điểm có giá trị là 1,2, ,n bằng màu đỏ, các điểm n+1, ,2n bằng màu xanh. Khi đó theo bổ đề tồn tại cách chọn n dây cung mà mỗi dây cung có 2 đầu mút được tô bởi 2 màu khác nhau và chúng đôi một không cắt nhau. Tổng giá trị của các dây cung sẽ bằng: (n + 1) + (n + 2) + + 2n ― 1 ― 2 ― ― n = n2 (ĐPCM) Bài 14. Cho số nguyên dương n 3 . Chứng minh rằng tập hợp X 1; 2; 3; ; n2 n có thể chia thành hai tập con không giao nhau sao cho không tập nào trong chúng chứa n phần tử a1,a2 , ,an với a1 a2 an a a và a k 1 k 1 với mọi k 2; 3; , n 1. k 2 Hướng dẫn giải
  9. 2 2 2 2 2 2 Đặt Sk k k 1; k k 2; ;k ; Tk k 1; k 2; ;k k n 1 n 1 S  Sk ; T  Tk . Ta chứng minh S, T là các tập con cần tìm của X k 1 k 1 Dễ dàng thấy S T  và S T X a a Ta chứng minh phản chứng. Giả sử S gồm các phần tử a ,a , ,a với a a a và a k 1 k 1 1 2 n 1 2 n k 2 với mọi k 2; 3; , n 1. Khi đó ta có ak ak 1 ak 1 ak , với mọi k 2; 3; , n 1 (1) Nếu a1 Si ., ta có i n 1 do Sn 1 n . Suy ra tồn tại ít nhất n Si n i phần tử thuộc a1; a2 ; ; an Si 1  Si 2   Sn 1 . Áp dụng nguyên lý Dirichlet, tồn tại ít nhất một tập S j , i j n chứa ít nhất 2 phần tử trong số các phần tử a1,a2 , ,an . Tức là tồn tại ak sao cho ak , ak 1 S j và ak 1 S1  S2   S j 1 . Khi đó ta có ak 1 ak S j 1 j 1; ak ak 1 Tj 1 1 j Suy ra ak 1 ak ak ak 1 . Điều này, mâu thuẫn với (1) a a Vậy S không chứa các phần tử a ,a , ,a với a a a và a k 1 k 1 với mọi k 2; 3; , n 1. 1 2 n 1 2 n k 2 Chứng minh tương tự ta cũng có tập T không chứa các phần tử a1,a2 , ,an với a1 a2 an và a a a k 1 k 1 với mọi k 2; 3; , n 1. k 2 Vậy S, T là các tập con cần tìm của X . Bài 15. Chứng minh rằng không thể chia các số từ 1 đến 15 thành hai tập A và B sao cho | A | 2, | B | 13 mà tổng các số ở B bằng tích các số ở A . (| A| là số phần tử của tập hợp A ). Hướng dẫn giải A Bài 16. Cho đa giác đều A1 A2 A2n , ( n 2 , n nguyên) nội tiếp đường tròn (O). Biết rằng số tam giác có các đỉnh là 3 trong 2n điểm A1, A2 , , A2n nhiều gấp 20 lần số hình chữ nhật có các đỉnh là 4 trong 2n điểm A1, A2 , , A2n . Tìm n. Hướng dẫn giải A
  10. Bài 17. Cho một bảng ô vuông có 100 100 ô vuông , mỗi ô đều điền một dấu + . Ta thực hiện phép biến đổi như sau: đổi dấu toàn bộ một hàng hoặc một cột của bảng ( dấu + thành dấu - , dấu - thành dấu +). Hỏi sau một số lần thực hiện phép biến đổi như trên thì bảng có thể có đúng 98 dấu - được không? Hướng dẫn giải Giả sử sau một số lần biến đổi bảng có đúng 98 dấu - Gọi xi là số lần đổi dấu ở hàng thứ i ( i = 1, 2 ,100 , tính từ trên xuống) Gọi yj là số lần đổi dấu ở cột thứ j ( j = 1, 2 ,100 , tính từ trái sang phải) Gọi m là các số lẻ trong các số x1; x2 ; ; x100 và n là các số lẻ trong các số y1; y2 ; ; y100 . Ta có m , n 0,1,2 100Ta có số lượng các dấu - trên bảng là m(100-n) + n( 100-m) = 100m +100n - 2mm Bảng có đúng 98 dấu - nên ta có 100m +100n - 2mm = 98 m 50 (n 50) 502 72 m 50 n 50 43.57 (*) m 50 n 50 57 mà 57 là số nguyên tố nên m-50  57 hoặc n-50  57 Ta có m-50 , n-50 50; 49; ;49;50 nên m-50 = 0 hoặc n-50 = 0 mâu thuẫn với (*). Vậy bảng không thể có đúng 98 dấu - . Bài 18. Với mỗi số nguyên dương m, kí hiệu C(m) là số nguyên dương k lớn nhất sao cho luôn tồn tại một tâp S gồm m số nguyên dương để mỗi số nguyên chạy từ 1 đến k hoặc thuộc S hoặc là tổng hai phần tử thuộc S m(m 6) m(m 3) (hai phần tử này không nhất thiết phân biệt). Chứng minh: C(m) . 4 2 Hướng dẫn giải Trước tiên ta tính thử một vài giá trị ban đầu của C(m) để cảm nhận bài toán. Dễ thấy: C(1)=2; C(2)=4; C(3)=8 Nhận xét: Việc tính C(m) quy về việc đếm số phần tử của tập A xác định bởi: A S  (S S) ; S S x y | x, y S m(m 3) C(m) +) (2 điểm) Chứng minh: 2 2 | S | (| S | 3) m(m 3) | A | | S | | S S | | S | | S | C|S| 2 2 Chú ý : Để đánh giá số phần tử của tập S+S ta chia hai trường hợp x trùng y và x khác y. Rõ ràng {1;2;3; ;k} là một tập con của A nên ta được đpcm.
  11. m(m 6) C(m) +) (2 điểm) Chứng minh: 4 Ta sẽ chỉ ra một tập B sao cho với mọi số nguyên chạy từ 1 đến m(m+6)/4 hoặc thuộc B hoặc là tổng hai số (không nhất thiết phân biệt) thuộc S(m). Khi đó C(m)>=m(m+6)/4. Xét hai trường hợp sau: TH1: m = 2n. (1 điểm) Xét tập B(m) = {1; 2; 3; ; n; 2n+1; 3n+2; ; (n+1)n+n} gồm m phần tử và dễ thấy tập B  (B B) chứa dãy số liên tiếp từ 1 đến (n+1)n + 2n và rõ ràng (n+1)n + 2n = 2n(2n+6)/4 TH2: m = 2n+1(1 điểm) B  (B B) Khi đó ta xây dựng tập B(m)={1;2;3; ; n+1;2n+3;3n+5; ;(n+1)n+2n+1}gồm m phần tử và tập chứa dãy số liên tiếp từ 1 đến (n+1)n+3n+2 và rõ ràng (n+1)n+3n+2 > (2n+1)(2n+7)/4 Từ hai TH trên ta được đpcm. Bài 19. Cho các tập hợp các số nguyên liên tiếp như sau:{1},{2,3},{4,5,6}, {7,8,9,10}, , trong đó mỗi tập hợp chứa nhiều hơn tập hợp ngay trước nó 1 phần tử, và phần tử đầu tiên của mỗi tập hợp lớn hơn phần tử cuối cùng của tập hợp ngay trước nó 1 đơn vị. Gọi Sn là tổng của các phần tử trong tập hợp thứ n. Tính S999. Hướng dẫn giải Ta thấy tập hợp thứ n chứa n số nguyên liên tiếp mà số cuối cùng là n n 1 1 2 3 4 n . 2 n n 1 Khi đó Sn là tổng của n số hạng trong một cấp số cộng có số hạng đầu u , công sai d 1 1 2 (coi số hạng cuối cùng trong tập hợp thứ n là số hạng đầu của cấp số cộng này) 1 1 2 Ta có Sn n 2u1 n 1 d n n 1 . 2 2 1 2 Vậy S999 .999 999 1 498501999 . 2 Bài 20. Có 푛 học sinh (푛 ≥ 2) đứng thành hàng dọc, cứ mỗi lần thầy giáo thổi còi thì có đúng 2 học sinh đổi chỗ cho nhau. Hỏi sau 2015 lần thầy giáo thổi còi, ta có thể thấy tất cả các học sinh đều đứng trở lại đúng vị trí ban đầu của mình hay không ? Hướng dẫn giải Đánh số từ 1 đến n cho các bạn học sinh trong hàng dọc lúc đầu. Ký hiệu 푃푛 là tập các hoán vị của {1,2, ,푛}.
  12. Gọi = ( (1), (2), , (푛)) là một hoán vị của {1,2, ,푛}. Cặp ( (푖), (푗)) của gọi là 1 nghịch thế của nếu 푖 (푗). Xét ánh xạ 푖: 푃푛→푃푛 mà 푖( ) thu được từ bằng cách đổi chỗ hai vị trí kề nhau ( (푖), (푖 + 1)) và giữ nguyên các vị trí còn lại. ∗ Cho 푖, 푗 ∈ ℕ , 푖 < 푗 ≤ 푛. Xét ánh xạ 푖푗: 푃푛→푃푛 푖푗 = 푗―1표 푗―2표 푗―3표 표 푖+2표 푖+1표 푖표 표 푗―3표 푗―2표 푗―1 (1) Là hợp thành của 2(푗 ― 푖) ―1 ánh xạ. Dễ thấy 푖푗( ) thu được từ bằng cách đổi vị trí của ( (푖), (푗)) và giữ nguyên các vị trí còn lại . Gọi ( ) là số nghịch thế của hoán vị . ( ) ― 1 푛ế ( (푖); (푖 + 1)) 푙à 푛 ℎị ℎ 푡ℎế Ta có ( 푖( )) = ( ) + 1 푛ế ( (푖); (푖 + 1)) ℎô푛 푙à 푛 ℎị ℎ 푡ℎế Do vậy ( 푖( )) ≡ ( ) +1 ( 표 2) (2). Từ (1) và (2) suy ra 푖푗 ( ) ≡ ( ) +1 (mod2) (3). Giả sử là thứ tự của 푛 học sinh sau lần thổi còi thứ k của thầy giáo. Ta có ∈ 푃푛 và +1 = 푖푗 ( ) với 1 ≤ 푖 < 푗 ≤ 푛 nào đó. Theo (3) ta có ( +1) ≡ ( ) +1 (mod2). Do đó ( ) ≡ ( 0) + ≡ ( 표 2)(vì ( 0) = 0). Nếu k lẻ thì ( ) ≢ 0( 표 2) do đó ≠ 0. Vậy sau 2015 lần thổi còi, tất cả các học sinh không thể đứng trở lại đúng vị trí ban đầu của mình. Bài 21. Lấy ngẫu nhiên 498 số nguyên dương không vượt quá 1000. Chứng minh rằng trong đó có 2 số có tổng chia hết cho 111 Hướng dẫn giải Xét tập S={1,2, ,1000} ta phân hoạch S như sau: A={1000}, B={111;222; ;999} Và chia tập T=S\(AUB) thành các tập con có 2 phần tử mà tổng bằng 999 như sau: T1={1;998}, T2={2;997}, T3={3;996}, , T495={499;500}. Như vậy S được chia thành 497 tập con, vậy 498 số được chọn ngẫu nhiên phải có 2 số rơi vào cùng một tập hợp. Hai số đó hoặc cùng chia hết cho 111 hoặc có tổng bằng 999 nên tổng của chúng chia hết cho 111 Bài 22. Trong mỗi ô của một bàn cờ ta viết một số nguyên dương. Hiệu giữa hai số nằm trong hai ô kề nhau bất kì (có chung cạnh) là số bé hơn hoặc bằng n. Chứng minh rằng có ít nhất 1007 ô vuông chứa cùng một số. Hướng dẫn giải Ta xét bài toán tổng quát: Trong mỗi ô của một bàn cờ n2 n2 ta viết một số nguyên dương. Hiệu giữa hai n số nằm trong hai ô kề nhau bất kì (có chung cạnh) là số bé hơn hoặc bằng n. Chứng minh rằng có ít nhất 2 + 1 ô vuông chøa cùng một số. Giải:
  13. Trên bàn cờ ta gọi a là số bé nhất và b là số lớn nhất. Chúng nằm cách nhau nhiều nhất là n2 – 1 ô vuông theo chiều ngang và n2 – 1 ô vuông theo chiều thẳng đứng. Do đó tồn tại một đường đi từ ô này đến ô kia gồm không quá 2n2 – 2 ô vuông Hiệu giữa hai số nằm trong hai ô kề nhau bất kì (có chung cạnh) là số bé hơn hoặc bằng n, nên ta có: b – a 2(n2 - 1)n Mặt khác tất cả các số nguyên dương nằm trên bàn cờ đều nằm giữa a và b nên nhiều lắm là có 2(n2 - 1)n số khác nhau n n n Từ đó vì n4 > (2(n2 - 1)n + 1) nên phải có nhiều hơn ô vuông chứa cùng một số. Hay có ít nhất + 2 2 2 1 ô vuông chưa cùng một số. Cho ta thu được bài toán đã cho. Bài 23. Các số nguyên được viết vào 441 ô của bảng vuông 21 21. Mỗi hàng và mỗi cột có nhiều nhất 6 giá trị khác nhau. Chứng minh rằng tồn tại một số nguyên có mặt ở ít nhất 3 cột và ít nhất 3 hàng. Hướng dẫn giải Giả sử các giá trị được ghi vào bảng là 1,2, ,n . Gọi ai là số cột khác nhau mà i i 1,n có mặt và bi là số hàng khác nhau mà i có mặt. Gọi Ti là số ô được đánh số i , ta có Ti Ti aibi 441 Ti  aibi . Mỗi cột và mỗi hàng có không quá 6 giá trị khác nhau, nên  ai 6.21,bi 6.21. Giả sử với mọi i , ta có ai 2,bi 2 . Khi đó: ai 2 bi 2 1  aibi 2 ai 2bi 3n 21.24 3n Vậy n 21. Mặt khác nếu đặt A i | ai 2,bi 3, B i | bi 2,ai 3 thì với mỗi cột có 21 ô và mỗi hàng có không quá 6 giá trị khác nhau nên tồn tại giá trị xuất hiện ở 4 hàng, giá trị này thuộc A nên xuất hiện nhiều 21 2 1 nhất là ở hai cột. Do có tất cả 21 cột nên số giá trị như thế không ít hơn 11 A 11. 2 Tương tự B 11, nên n A B 22 . Mâu thuẫn nhận được suy ra điều phải chứng minh. Bài 24. Cho số n tự nhiên lớn hơn 2. Ta đánh số mỗi cạnh, đường chéo của n- giác A1 A2 An bởi một số nguyên dương nhỏ hơn hoặc bằng r (nguyên dương) sao cho: i) Mọi số nguyên dương từ 1 đến r đều được đánh số. ii) Với mỗi tam giác Ai Aj Ak đều có 2 cạnh được đánh số bởi cùng 1 số và cạnh còn lại đánh bởi số nhỏ hơn.
  14. a) Xác định số nguyên dương r lớn nhất mà điều đó có thể thực hiện được. b) Khi r lớn nhất, có bao nhiêu cách đánh số thỏa mãn Hướng dẫn giải a. Xét một đỉnh V mà từ đó có k 2 cạnh đánh số bởi r, đỉnh như thế phải tồn tại vì tồn tại một tam giác có 2 cạnh đánh số r. Gọi A là tập các đỉnh từ V được đánh số r thì | A | k và B là tập các đỉnh còn lại ( gồm cả V) thì | B | n k . Khi đó + Mọi cạnh nối từ một điểm thuộc A đến một điểm thuộc B đều được đánh số bởi r, vì nếu giả sử có X thuộc A, Y thuôc B mà |XY| < r thì Y  V và do đó | XV | r,|YV | r , do điều kiện ii) nên | XY | r . Mâu thuẫn + Mọi cạnh nối 2 điểm trong A đều đánh số nhỏ hơn r, vì nếu X ,Y A thì | XV | |YV | r nên |XY| < r + Mọi cạnh nối 2 điểm trong B đều đánh số nhỏ hơn r, vì nếu X ,Y B mà | XY | r thì hoặc | XV | r hoặc |YV | r . Mâu thuẫn. Chứng minh bằng quy nạp rằng giá trị lớn nhất của r là n-1 Giả sử với mọi đa giác i n cạnh, số số được dung nhiều nhất là k-1 Xét đa giác n+1 đỉnh, giả sử V,A,B là đỉnh và các tập được nói đến ở trên, Ta có r | A | 1 | B | 1 1 k 1 (n 1 k 1) 1 n . Điều phải chứng minh. b. 2,0 Nhận xét: Nếu đa giác có n cạnh và tập A có k phần tử thì tập A có nhiều nhất k-1 số được dung và tập B có nhiều nhất n-k-1 số được dung. Vậy để đánh số từ 1 đến n-1 cho các đoạn tạo được từ đa giác, ta phải chọn k-1 số trong các số{1 ,2,,n 2} để đánh số cho các đoạn tạo được từ các điểm trong tập A và n k 1 số còn lại trong tập đó để đánh số cho các đoạn tạo được từ các điểm thuộc tập B k Mặt khác, số cách chọn 2 tập A,B sao cho | A | k,| B | n k là Cn Từ đó ta có hệ thức truy hồi sau ( với f(n) là số cách đánh số trong trường hợp đa giác có n cạnh): n 1 k k 1 2 f (n) C Cn 2 f (k) f (n k) k 1 n n 1 f (k) f (n k) n!(n 2)! . k 1 k!(k 1)! (n k)!(n k 1)! k k 1 ( Có 2f(n) là vì theo cách đếm như vậy, mỗi sốCn .Cn 2 f (k) f (n k) được tính 2 lần )
  15. n 1 Đặt f (x) x!(x 1)!g(x) ta có: 2(n 1)g(n)  g(k)g(n k). k 1 n!(n 1)! Chứng minh kết quả đó bằng quy nạp f (n) 2n 1 Bài 25. Cho các số nguyên dương m,n; một bảng hình vuông kích thước n n được gọi là bảng “ m hoàn thiện” nếu tất cả các ô của nó được điền bởi các số nguyên không âm (không nhất thiết phân biệt) sao cho tổng các số trên mỗi hàng và mỗi cột đều bằng m. Hỏi có tất cả bao nhiêu cách lập bảng “2015-hoàn thiện” kích thước 3x3 sao cho số nhỏ nhất trong các số ở các ô trên đường chéo chính nằm ở vị trí tâm của bảng? (Ô ở đường chéo chính của bảng là ô ở vị trí giao của dòng có số thứ tự tính từ trên xuống và cột có số thứ tự tính từ trái sang bằng nhau; ô ở tâm bảng 3x3 là ô ở dòng thứ 2 và cột thứ 2). Hướng dẫn giải Ta giải bài toán trong trường hợp lập bảng “ m hoàn thiện” kích thước 3x3. Gọi x, y, z,t lần lượt là các số điền được ở đường chéo chính và ô ở vị trí dòng 1 cột 2 , khi đó các số còn lại ở các ô được xác định duy nhất như hình bên dưới x t m x t m z x y t y x t z y t z m y t z Vì các số được điền là không âm và y là số nhỏ nhất trong các số ở đường chéo chính nên các điều kiện sau phải thỏa x, y, z,t 0; x t m; x t z; z y t m; x y t m z; y min x, y, z Các điều kiện trên có thể rút gọn lại thành 0 y min x, y, z; x t m; z y t * Khi đó 0 y 2y t z x y t z x t m . Ta thấy rằng bộ bốn số không âm y;2y t z; x y t z; x t sắp theo thứ tự tăng dần xác định duy nhất bộ các số x, y, z,t thỏa mãn * và tương ứng với một cách lập bảng “m hoàn thiện”. Do vậy, số cách lập được là m 4 . 4 2019 Áp dụng với m 2015, ta được kết quả là . 4
  16. Bài 26. Cho m,n,k là các số nguyên dương thoả mãn m 1 và 1 k n k 1 m . Xét tập hợp S 1,2, ,n . Gọi X là tập hợp tất cả các tập con A của S thoả mãn đồng thời hai tính chất sau: (i) A k ; (ii) ai a j m,ai ,a j A,i j;i, j 1,k . Hãy xác định số phần tử của tập hợp X . Hướng dẫn giải Giả sử A X , A a1,a2 , ,ak  với 1 a1 a2 ak n;ai a j m,1 j i k . Đặt b1 a1,b2 a2 m, ,bi ai i 1 m, ,bk ak k 1 m . Vì 1 a1 a2 ak n;ai a j m,1 j i k nên 1 b1 b2 bk n k 1 m Suy ra tập B b1,b2 , ,bk  là một tập con có k phần tử của tập 1,2, ,n k 1 m. Gọi Y là tập tất cả các tập con có k phần tử của tập hợp 1,2, ,n k 1 m. Khi đó ánh xạ f : X Y A B Khi đó f là một song ánh. Thật vậy ● f là đơn ánh: Vì với A1, A2 X , A1 A2 B1, B2 Y, B1 B2 f A1 f A2 ● f là toàn ánh: Giả sử B b1,b2 , ,bk  Y . Đặt A b1,b2 m, ,bk k 1 m a1,a2 , ,ak  . Ta có ai 1 ai bi 1 im bi i 1 m m 1 nên A X và f A B . k Vì vậy ta có X Y Cn k 1 m . Bài 27. Hội khỏe Phù Đổng năm 2014 có tổ chức thi đấu 4 môn thể thao chạy 100m, nhẩy xa, nhẩy cao, bắn cung và quy định điều kiện cho mỗi đội tham gia như sau: • Mỗi vận động viên của một đội chỉ thi đấu duy nhất một môn thể thao. • Mỗi đội có thể lựa chọn số vận động viên cho mỗi môn tùy ý (nhưng tổng số vận động viên đúng bằng 20). Tại lễ khai mạc, mỗi đội xếp thành một hàng dọc, các vận động viên chạy 100m cầm cờ đỏ đứng đầu, tiếp theo đến vận động viên nhảy xa cầm cờ vàng rồi đến vận động viên nhảy cao cầm cờ xanh và cuối cùng là vận động viên bắn cung cầm cờ tím. Giả sử số đội tham dự là đủ lớn, hỏi có thể có tối đa bao nhiêu loại hàng dọc (phân biệt theo độ dài mỗi màu của hàng). Hướng dẫn giải
  17. 0 a,b,c,d 20 Ta thấy mỗi hàng sẽ tương ứng với một bộ 4 số (a, b, c, d) với để chỉ số lượng vận động a b c d 20 viên thi đấu mỗi môn chạy 100m, nhẩy xa, nhẩy cao, bắn cung tương ứng. Với mỗi bộ 4 số như thế ta đặt 23  tương ứng với dãy nhị phân 1 101 101 101 1. Dễ thấy tương ứng đó là một song ánh và có 3 dãy nhị C 23 a b c d phân khác nhau do đó có tối đa 3 1771 loại hàng dọc khác nhau. C 23 Bài 28. Có 2n cái đèn L , L , , L được treo thành một hàng theo thứ tự đó, mỗi một đèn có thể ở một trong 1 2 2n hai trạng thái là tắt hoặc bật. Mỗi giây ta đồng thời thay đổi trạng thái của các đèn như sau: nếu đèn L i và các đèn kề nó (chỉ có một đèn kề với L và L , có hai đèn kề với các đèn còn lại) là cùng trạng thái thì L chuyển 1 2n i sang trạng thái tắt, ngược lại Li chuyển sang trạng thái bật. Ban đầu tất cả các đèn đều tắt trừ đèn bên trái cùng là bật. Chứng minh rằng sau một số hữu hạn lần thay đổi trạng thái cuối cùng tất cả các đèn đều tắt Hướng dẫn giải Kí hiệu các đèn từ trái qua phải là L , L , , L . Giả sử ban đầu L bật, các đèn khác đều tắt. Ta chứng minh 1 2 2n 1 rằng: Sau 2n 1 lần thay đổi trạng thái tất cả các đèn đều bật và sau 2n lần thay đổi trạng thái tất cả các đèn đều tắt. Với n = 1 dễ thấy mệnh đề đúng. Giả sử mệnh đề đúng với n = k. Ta chứng minh mệnh đề đúng với n = k + 1. Thật vậy: Sau 2k 1 lần thay đổi trạng thái tất cả các đèn L , L , , L đều bật và tất cả các đèn 1 2 2k L , L , , L đều tắt. 2k 1 2k 2 2k 1 Sau lần thứ 2k hai đèn L , L đều bật và các đèn còn lại đều tắt. 2k 2k 1 Do đó sau 2k 1 đổi tiếp theo tất cả các đèn đều bật suy ra sau 2k 1 1lần thay đổi trạng thái tất cả các đèn đều bật và sau 2k 1 lần thay đổi trạng thái tất cả các đèn đều tắt. Bài 29. Mỗi điểm trong mặt phẳng được tô bằng một trong hai màu xanh hoặc đỏ. Chứng minh rằng luôn tồn tại một tam giác mà ba đỉnh và trọng tâm cùng màu. Hướng dẫn giải Lấy 5 điểm tùy ý sao cho không có 3 điểm nào thẳng hàng trong mặt phẳng. Khi đó vì chỉ dùng hai màu để tô các điểm nên theo nguyên lý Dirichlet phải tồn tại ba điểm trong số đó cùng màu. Giả sử đó là 3 điểm A, B, C màu đỏ. Gọi G là trọng tâm tam giác ABC. Nếu G có màu đỏ thì ta được tam giác có 3 đỉnh và trọng tâm màu đỏ. Nếu G có màu xanh. Kéo dài GA, GB, GC các đoạn AA', BB', CC' sao cho AA'=3GA, BB'=3GB, CC'=3GC. Gọi M, N, P tương ứng trung điểm BC, CA, AB thì AA'=3GA=6GM, suy ra AA'=2AM. Tương tự BB'=2BN, CC'=2CP. Do đó tam giác A'BC, B'CA, C'AB tương ứng nhận A, B, C làm trọng tâm. Mặt khác ta cũng có tam giác ABC, A'B'C' có cùng trọng tâm G. Có hai trường hợp có thể xảy ra a) Nếu A', B', C' có cùng màu xanh, khi đó tam giác A'B'C' và trọng tâm G có màu xanh.
  18. b) Nếu ít nhất một trong các điểm A', B', C' màu đỏ. Không giảm tổng quát, giả sử A' đỏ. Khi đó tam giác A'BC và trọng tâm A có màu đỏ. Bài 30. Cho một sự bố trí vòng tròn quanh ba cạnh của một tam giác, một vòng ở mỗi góc, hai vòng ở mỗi cạnh, mỗi số từ 1 đến 9 được viết vào một trong những vòng tròn này sao cho. i. Tổng của 4 số ở mỗi cạnh là bằng nhau. ii. Tổng của bình phương của 4 số trên mỗi cạnh của tam giác là bằng nhau. Tìm tất cả các cách thỏa mãn yêu cầu này. Hướng dẫn giải Lấy bất kỳ một sự bố trí các con số, gọi x, y, z là số ở trong góc và S1, S2 lần lượt là tổng của bốn số, tổng của bình phương bốn số trên một cạnh bất kỳ. Do điều kiện đã cho ta có: 9 3S1 x y z  k x y z 45 (1) k 1 9 2 2 2 2 2 2 2 3S2 x y z  k x y z 285 (2) - Từ k 1 đẳng thức (2) ta suy ra x, y, z hoặc tất cả chia hết cho 3 hoặc không có số nào chia hết cho 3. Bởi nguyên lý Pigeouhole có hai số là đồng dư mod3. Lấy phương trình (1) theo mod3 ta cũng suy ra 3| (x y z) . Do đó x  y  z(mod3) . Nếu (x, y, z) (3,6,9) hay (1,4,7) thì S2 137 hoặc 17. Nếu S2 137 thì S2 1(mod3) suy ra chỉ có một số trên 3 cạnh là lẻ. Điều này không thể vì 5 3 số lẻ được viết trong mỗi khe. Vì thế (x, y, z) (2,5,8) và S2 126 . Vì 92 82 126 nên 9 không thể nằm cùng cạnh với 8, tức nó nằm trên cạnh chứa 2 hoặc 5. - Vì min 72 92 ;72 52 82 126 , nên số 7 phải nằm trên cạnh chứa số 2 hoặc 8. Như vậy 4 lần các số trên 3 cạnh phải là (2,4,9,5); (5,1,6,8); (8,7,3,2) để cho tổng bình phương các số trên mỗi cạnh bằng 126. Cuối cùng ta thử lại các bộ số trên đều thỏa mãn. Bài 31. Cho số nguyên n 1. Tìm số lớn nhất các cặp gồm 2 phần tử phân biệt của tập 1;2; ;n sao cho tổng của các cặp khác nhau là các số nguyên khác nhau và không vượt quá n . Hướng dẫn giải Giả sử có k cặp thỏa mãn đề bài. Gọi S là tổng của k cặp đó, thì S 1 2 2k k(2k 1) k(k 1) Dễ thấy S n (n 1) (n k 1) nk . 2 Do đó,
  19. k(k 1) 2n 1 k(2k 1) nk k 2 5 2n 1 Bây giờ ta xây dựng cặp thỏa mãn đề bài như sau 5 2n 1 Trường hợp 1: Số n có dạng 5k 1 hoặc 5k 2. Khi ấy, 2k . Ta xét các cặp sau 5 (4k 1;k), (4k;k 1), (3k 2;1), (3k;2k), (3k 1;2k 1), (2k 1;k 1) Rõ ràng dãy trên có 2k cặp thỏa mãn đề bài. 2n 1 Trường hợp 2: Số n có dạng 5k 3 hoặc 5k 4 hoặc 5k 5 . Khi ấy, 2k 1. Ta xét các cặp sau 5 (4k 2;k 1), (4k 1;k), ,(3k 2;1),(3k 1;2k 1),(3k;2k), ,(2k 1;k 1) Dãy trên có 2k 1 thỏa mãn đề bài. 2n 1 Vậy số lớn nhất các cặp thỏa mãn đề bài là 5 Bài 32. Sắp xếp chín học sinh lớp 11 (hoặc giới Nam hoặc giới Nữ) đứng cách đều nhau trên một đường tròn. Chứng minh rằng tồn tại sáu học sinh cùng giới đứng tại sáu đỉnh của hai tam giác bằng nhau. Hướng dẫn giải Gọi 9 học sinh là H1, H2, H9 đứng tại chín đỉnh của đa giác đều chín cạnh. Vì có 9 học sinh đứng tại 9 đỉnh nên có ít nhất 5 đỉnh có học sinh cùng giới (hoặc là Nam hoặc là Nữ). Để cho tiện, ta giả sử 5 đỉnh này có 5 học sinh Nam đứng (tương tự nếu là 5 học sinh Nữ). 3 Gọi một tam giác có 3 đỉnh mà 3 học sinh Nam đứng là tam giác Nam, như vậy có ít nhất C5 10 tam giác Nam. Bây giờ ta sẽ chứng minh có hai tam giác Nam bằng nhau: Chín đỉnh của đa giác chia đường tròn ngoại tiếp nó thành 9 cung bằng nhau Hi Hi 1, i =1,8 và cung H9 H1; , ta gọi mỗi cung này là một “mảnh”. Không mất tính tổng quát, gọi Hi H j Hk là tam giác có Hi H j H j Hk Hk Hi . Hơn nữa số hij là số mảnh của cung Hij không chứa điểm Hk (i j k i ); tương tự ta định nghĩa như thế cho số hjk , hki .
  20. Tương ứng với mỗi tam giác Hi H j Hk với một bộ ba (hij; hjk ; hki ) . Ta nhận thấy rằng: 1 hij hjk hki 7 và hij + hjk + hki 9 . Chẳng hạn với tam giác với 3 đỉnh H1, H3 , H7 ta gọi là tam giác H3H1H7 tương ứng với một bộ ba (2;3;4) theo thứ tự đó. Như vậy, các tam giác bằng nhau ứng với cùng một bộ ba số như định nghĩa, trong khi các tam giác không bằng nhau ứng với các bộ ba khác nhau. Từ đó, ta xây dựng một song ánh giữa các lớp tam giác bằng nhau với tập hợp các bộ ba số nguyên dương có thứ tự (a, b, c) với a b c; a+b+c = 9 . Có tất thảy bẩy bộ ba số thỏa mãn là: (1,1,7), (1,2,6), (1,3,5), (1,4,4), (2,2,5), (2,3,4) và (3,3,3). Tức là có 7 lớp tam giác bằng nhau. Vì có ít nhất 10 tam giác Nam (Ba đỉnh tam giác là 3 học sinh Nam), nên có một lớp có ít nhất hai tam giác Nam; do đó có ít nhất sáu học sinh cùng giới, đứng tại sáu đỉnh của hai tam giác bằng nhau. Bài 33. Một quân cờ di chuyển trên bàn cờ 2016 2016 theo một trong ba cách: đi lên một ô, sang bên phải một ô, đi xuống về bên trái một ô. Hỏi quân cờ có thể đi qua tất cả các ô, mỗi ô đúng một lần và quay lại ô kề bên phải ô xuất phát được không? Hướng dẫn giải Sau mỗi bước, tổng thứ tự của hàng và cột chứa quân cờ hoặc giảm đi 2 hoặc tăng lên 1. Như vậy, khi xét theo modulo 3 thì tổng này tăng 1 mỗi bước. Do có 20162 1 bước, nếu kết thúc ở ô kề bên phải ô xuất phát thì tổng này tăng 1 đơn vị. Do đó, 20162 2 chia hết cho 3, mâu thuẫn. Vậy quân cờ không thể đi qua tất cả các ô, mỗi ô đúng một lần và quay lại ô kề bên phải ô xuất phát. Bài 34. Trên mặt phẳng, kẻ vô hạn các ô vuông (dạng bàn cờ) và mỗi ô vuông được điền một trong hai số 0 hoặc 1 sao cho bất cứ hình chữ nhật nào có kích thước 2x3 thì có đúng hai ô điền số 1. Xét một hình chữ nhật bất kì có kích thước 2016x2017. Tính tổng các số có trong các ô của nó. Hướng dẫn giải Nhận xét : Mọi hình chữ nhật có kích thước 1x3 đều chứa đúng một ô có số 1. Thật vậy, giả sử tồn tại hình chữ nhật có kích thước 1x3 có số ô có số 1 khác 1. Không mất tính tổng quát ta giả sử đó là hình chữ nhật AKHD kích thước 1x3 có đúng hai ô điền số 1 (nếu không thì không có ô nào chứa số 1 nhưng không thể là ba ô điền số 1 vì trong mọi hình chữ nhật có kich thước 2x3 có đúng 2 ô điền số 1).
  21. Có thể cho coi hai ô chứa số 1 của AKHD là ô 7 và ô 8 (Nếu ở các ô khác thì lập luận tương tự). Xét hình chữ nhật BFNA có kích thước 2x3 nó có đúng hai ô chứa số 1 các ô 1,2,4,5 là các ô điền số 0. Xét hình chữ nhật BCHK, từ giả thiết và do các ô 1,2,4,5 đều điền số 0 nên các ô 3,6 phải điền số 1. Xét hình chữ nhật ECDM kích thước 2x3, ta thấy do ô 3,6,8 điền số 1 nên dẫn đến mâu thuẫn. Trường hợp AKHD không có ô nào điền số 1, lập luận tương tự ta cũng dẫn đến mâu thuẫn. Vậy giả thiết phản chứng là sai hay ta có điều phải chứng minh Vì 2016=3x672 nên hình chữ nhật kich thước 2016x2017 chia thành 672x2017 hình chữ nhật có kích thước 1x3. Vậy tổng các số điền trong ô của hình chữ nhật này là: 672.2017=1355424. Bài 35. Trong một cuộc hội nghị, mỗi đại biểu bắt tay ít nhất 6 đại biểu khác. Người ta đếm được tất cả 97 lần bắt tay. Hỏi hội nghị đó có tối đa bao nhiêu đại biểu. Hướng dẫn giải Gọi n là số đại biểu. Ta xây dựng đồ thị G với đỉnh là các đại biểu, còn hai đỉnh bất kỳ được nối với nhau bằng cạnh khi và chỉ khi hai đại biểu tương ứng của hai đỉnh đó bắt tay với nhau. Khi đó đồ thị G có 97 cạnh. Theo bổ đề bắt tay, trong một đồ thị, tổng số bậc của các đỉnh bằng hai lần số cạnh, do đó 97x2 6n n 32 . Vậy hội nghị có tối đa 32 đại biểu.