Chuyên đề bồi dưỡng HSG môn Toán Lớp 11 - Chuyên đề: Toán rời rạc - Phần 1

Nội dung text: Chuyên đề bồi dưỡng HSG môn Toán Lớp 11 - Chuyên đề: Toán rời rạc - Phần 1

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 1
2. Nếu 1 A thì chọn A A {1,n 1,n 3} n n 4 n 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: 2
3. t a1 t a2  t an 2t a1 2t a2  2t an     n 1 t a1 n 1 t a2  n 1 t an 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 ii T hình 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 m phủ kín 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 3
4. 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 1 của hình 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 1 2 1 qua tâm 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 1 M sao cho 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à . 2 2 i 2 22 Tiếp tục như vậy 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 4
5. Đặ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 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 5
6. 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 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 6
7. Từ đó k m n . Hình vẽ sau đây chỉ ra một ví dụ k= m+n ****** ** * * 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 7
8. 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: 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. 8
9. 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 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) 9
10. 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 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 (*). 10