Đề cương ôn thi môn Toán Lớp 9 - Chuyên đề 18: Nguyên lí và áp dụng - Trần Kim Oanh

Nội dung text: Đề cương ôn thi môn Toán Lớp 9 - Chuyên đề 18: Nguyên lí và áp dụng - Trần Kim Oanh

1. GIÁO VIÊN: TRẦN KIM OANH CHUYÊN ĐỀ: NGUYÊN LÍ VÀ ÁP DỤNG 1. Nguyên lí Dirichlet. 1.1. Nội dung Nguyên lí Dirichlet - còn gọi là nguyên lí chim bồ câu (The Pigeonhole Principle) hoặc nguyên lý những cái lồng nhốt thỏ hoặc nguyên lí sắp xếp đồ vật vào ngăn kéo (The Drawer Principle) - đưa ra một nguyên tắc về phân chia phần tử các lớp. Nguyên lý Dirichlet cơ bản: Nếu nhốt n 1 con thỏ vào n cái chuồng thì bao giờ cũng có một chuồng chứa ít nhất hai con thỏ. Nguyên lý Dirichlet tổng quát: Nếu có N đồ vật được đặt vào trong k hộp thì sẽ tồn tại một hộp N chứa ít nhất đồ vật. (Ở đây x là số nguyên nhỏ nhất có giá trị nhỏ hơn hoặc bằng x) k Nguyên lí Dirichlet mở rộng: Nếu nhốt n con thỏ vào m 2 cái chuồng thì tồn tại một chuồng n m 1 có ít nhất con thỏ. m Nguyên lí Dirichlet dạng tập hợp: Cho A và B là hai tập hợp khác rỗng có số phần tử hữu hạn, mà số lượng phần tử của A lớn hơn số lượng phần tử của B. Nếu với một quy tắc nào đó, mỗi phần tử của A cho tương ứng với một phần tử của B, thì tồn tại ít nhất hai phần tử khác nhau của A mà chúng tương ứng với một phần tử của B. 1.2. Phương pháp ứng dụng. Nguyên lí Dirichlet tưởng chừng như đơn giản như vậy, nhưng nó là một công cụ hết sức có hiệu quả dùng để chứng mình nhiều kết quả hết sức sâu sắc của toán học. Nguyên lí Dirichlet cũng được áp dụng cho các bài toán của hình học, điều đó được thể hiện qua hệ thống bài tập sau: Để sử dụng nguyên lý Dirichlet ta phải làm xuất hiện tình huống nhốt “thỏ” vào “chuồng” và thoả mãn các điều kiện: + Số ‘thỏ” phải nhiều hơn số chuồng. + “Thỏ” phải được nhốt hết vào các “chuồng”, nhưng không bắt buộc chuồng nào cũng phải có thỏ. Thường thì phương pháp Dirichlet được áp dụng kèm theo phương pháp phản chứng. Ngoài ra nó còn có thể áp dụng với các nguyên lý khác. 1.3. Một số ví dụ minh họa. Ví dụ 1. Cho bảng ô vuông kích thước 10.10 gồm 100 ô vuông đơn vị. Điền vào mỗi ô vuông của bảng này một số nguyên dương không vượt quá 10 sao cho hai số ở hai ô vuông chung cạnh hoặc chung đỉnh nguyên tố cùng nhau. Chứng minh rằng trong bảng ô vuông đã cho có một số xuất hiện ít nhất 17 lần. Lời giải Xét hình vuông cạnh 2x2 , do hình vuông này có mỗi hình vuông nhỏ luôn chung cạnh hoặc chung đỉnh nên tồn tại nhiều nhất 1 số chẵn, nhiều nhất 1 số chia hết cho 3 do đó có ít nhất 2 số lẻ không chia hết cho 3. Bảng 10x10 được chia thành 25 hình vuông có cạnh 2x2 nên có ít nhất 50 số lẻ không chia hết cho 3. Từ 1 đến 0 có 3 số lẻ không chia hết cho 3 là 1, 5, 7. Áp dụng nguyên 50 lí Dirichlet ta được một trong ba số trên xuất hiện ít nhất 1 17 lần 3 Ví dụ 2. Cho tập hợp X 1; 2; 3; ; 2024. Chứng minh rằng trong 90 số khác nhau bất kỳ 1 được lấy ra từ tập X luôn tồn tại hai số x và y sao cho x y . 2 Lời giải Chia 2012 số thành 44 đoạn gồm . 1; 2; 3; ; 2012 1; 3 , 4; 8 , , 1936; 2012 2 Các đoạn trên có dạng tổng quát là k2 ; k 1 1 .
2. GIÁO VIÊN: TRẦN KIM OANH Như vậy 90 số thuộc tập hợp X nằm trong 44 đoạn trên. Theo nguyên lí Dirichlet thì tồn tại ba số trong 90 số trên nằm trong cùng một đoạn. Không mất tính tổng quát ta giả sử hai số đó là x, y, z và 2 chúng nằm trong đoạn k2 ; k 1 1 . 2 2 Chia đoạn k2 ; k 1 1 thành hai đoạn là k2 ; k2 k và k2 k; k 1 1 Khi đó theo nguyên lí Dirichlet tồn tại hai số nằm trên cùng một đoạn. Giả sử hai số đó là x và y. Khi đó Nếu x và y nằm trên đoạn k2 ; k2 k thì ta được 1 1 1 x y k2 k k2 k2 k k2 k k 4 2 2 2 Nếu x và y nằm trên đoạn k2 k; k 1 1 thì ta được 2 2 2 k 1 1 k k k 1 x y k 1 1 k2 k . 2 k 1 1 k2 k 2k 2 Từ đó ta có điều phải chứng minh. Ví dụ 3. Cho A là tập hợp gồm 6 phần tử bất kỳ của tập hợp 0;1; 2; ;14. Chứng minh rằng tồn tại hai tập hợp con B1 ,B2 của tập hợp A( B1 ,B2 khác nhau và khác rỗng ) sao cho tổng tất cả các phần tử của tập hợp B1 bằng tổng tất cả các phần tử của tập hợp B2 . Lời giải Do A là tập hợp có 6 phần tử nên số tập hợp con khác rỗng và khác A của tập hợp A là 26 2 62 . Xét tập hợp X là tập hợp con bất kì trong 62 tập hợp con trên và S X là tổng các phần tưt của X. Tập hợp X có nhiều nhất 5 phần tử thuộc tập hợp 0;1; 2; ;14 nên ta có 0 S X 10 11 12 13 14 60 . Như vậy với 62 tập hợp con của A như trên thì tồng tại 62 tổng không vượt quả 60. Theo nguyên lý Dirichlet thì tồn tại hai tổng có giả trị bằng nhau. Điều đó chứng tỏ tồn tại hai tập hợp con B1 ,B2 của tập hợp A có tổng các phần tử của chúng bằng nhau. Ví dụ 4. Trong hình vuông cạnh bằng 1 ta đặt 51 điểm phân biệt bất kì. Chứng minh rằng có ít nhất 1 3 trong số 51 điểm đó nằm trong một hình tròn bán kính . 7 Lời giải 1 Chia hình vuông đã cho thành 25 hình vuông con bằng nhau có cạnh bằng . Theo nguyên lý 5 Dirichlet thì tồn tại ít nhất một hình vuông nhỏ chứa ít nhất ba điểm trong số 51 điểm đó. Ta kí hiệu 2 hình vuông đó là C. Khi đó hình vuông nhỏ C có đường chéo là . Đường tròn ngoại tiếp hình 5 1 2 1 1 vuông nhỏ C có bán kính . . Vậy ba điểm nói trên nằm trong hình tròn đồng tâm 2 5 5 2 7 1 với đường tròn ngoại tiếp hình vuông nhỏ đó có bán kính . 7
3. GIÁO VIÊN: TRẦN KIM OANH Tổng quát hóa bài toán: Dựa vào bài giải bài toán trên ta có thể tổng quát hóa bài toán trên với a là kích thước của cạnh hình vuông, m là số điểm đặt bất kì, phân biệt. Chứng minh rằng có ít nhất n a2 trong số m điểm đó nằm trong một hình trong bán kính . (Trong đó kí hiệu [a] là phần m 2. n 1 nguyên của a). Lời giải m a2 Chia hình vuông đã cho thành hình vuông con bằng nhau có cạnh bằng . Theo n 1 m n 1 nguyên lí Dirichlet thì tồn tại ít nhất một hình vuông nhỏ có chứa ít nhất n điểm trong số m điểm đó. Ta kí hiệu đó là hình vuông C. Đường tròn ngoại tiếp C có bán kính a2 a2 . Vậy n điểm trên nằm trong hình tròn đồng tâm với đường tròn C có m m 2. 2. n 1 n 1 a2 bán kính . m 2. n 1 Ví dụ 5. Trong mặt phẳng cho n đường thẳng sao cho đôi một không song song với nhau. Chứng 1800 minh rằng tồn tại góc giữa hai đường thẳng nào đó không lớn hơn . n Lời giải Cho điểm O tùy ý trong mặt phẳng. Qua O vẽ n đường thẳng d1 ;d2 ;d3 ; ;dn lần lượt song song với n đường thẳng đã cho (ta luôn làm được điều này do n điểm đã cho đôi một không song song với nhau) Gọi i là góc tạo bởi hai đường thẳng di và di 1 . 0 0 Khi đó ta có 2 1 2 3 n 360 nên ta được 1 2 3 n 180 . 1800 Từ đó theo nguyên lí Dirichlet tồn tại một góc . Từ đó suy ra điều phải chứng minh. j n BÀI TẬP TỰ LUYỆN Bài 1. Có 15 đội bóng tham dự giải vô địch quốc gia theo thể thức đấu vòng tròn một lượt. Chứng minh rằng tại bất kì thời điểm nào của giải ta luôn tìm được 2 đội có cùng số trận đấu bằng nhau tại thời điểm đó(có thể là 0 trận). Bài 2. Một bà mẹ chiều con nên ngày nào cũng cho con ăn ít nhất một chiếc kẹo. Để hạn chế, mỗi tuần bà cho con không ăn quá 12 chiếc kẹo. Chứng minh rằng trong một số ngày liên tiếp nào đó bà mẹ đã cho con tổng số 20 chiếc kẹo. Bài 3. Chứng minh rằng trong 2001 người bất kỳ, luôn có ít nhất hai người có số người quen bằng nhau(số người quen chỉ tính trong nhóm) Bài 4. Trong một thời gian nọ của một lớp học Toán có một nhóm gồm 5 học sinh mà cứ mỗi người trong nhóm này thì rơi vào trong trạng thái ngủ gục trong lớp đúng 2 lần. Với mỗi cặp học sinh, đều có cả hai cùng ngủ gục một lần. Chứng minh rằng tại một thời điểm nào đó có ba học sinh trong nhóm đó đồng thời ngủ gục . Bài 5. Có 5 người đấu cờ với nhau. Hãy xác định kết quả của tất cả các trận đấu nếu biết rằng mỗi người chơi một lần với 4 người kia và số điểm của mỗi người nhận được đều khác nhau. Ngoài ra: a) Người xếp thứ nhất không hoà trận nào. b) Người xếp thứ nhì không thua trận nào.
4. GIÁO VIÊN: TRẦN KIM OANH c) Người xếp thứ tư không thắng trận nào. Bài 6. Các học sinh được phát bài kiểm tra với mỗi môn một bài và trong n( n 3 ) môn học. Biết rằng với một môn học bất kỳ có đúng 3 học sinh đạt điểm tối ưu, còn với hai môn tuỳ ý thì có đúng 1 học sinh đạt điểm tối ưu cho mỗi môn trong cả hai môn đó. Hãy xác định số n bé nhất sao cho từ các điều kiện trên có thể suy ra rằng có đúng 1 học sinh đạt điểm tối ưu cho mỗi môn trong cả n môn học. Bài 7. Cho m máy tính và n máy in m n mỗi sợi dây cáp chỉ nối được một máy tính và một máy in. Tại một thời điểm bất kỳ mỗi máy tính chỉ có thể điều khiển được một máy in và người lại mỗi máy in chỉ in được cho một máy tính. Hỏi phải dùng ít nhất là bao nhiêu sợi dây cáp để n máy tính bất kỳ có thể đồng thời in được? Bài 7. Kì thi tuyển sinh vào trường THPT chuyên Long An năm nay có 529 học sinh đến từ 16 địa phương khác nhau tham dự. Giả sử điểm bài thi môn Toán của mỗi học sinh đều là số nguyên lớn hơn 4 và bé hơn hoặc bằng 10. Chứng minh rằng luôn tìm được 6 học sinh có điểm môn Toán giống nhau và cùng đến từ một địa phương. Bài 8. Xét 20 số nguyên dương đầu tiên 1, 2, 3, , 20. Hãy tìm số nguyên dương k nhỏ nhất có tính chất: Với mỗi cách lấy ra k số phân biệt từ 20 số trên, đều lấy được hai số phân biệt a và b sao cho a b là một số nguyên tố. Bài 9. Cho tập hợp X 1; 2; 3; ; 2024. Chứng minh rằng trong 45 số khác nhau bất kỳ được lấy ra từ tập X luôn tồn tại hai số x, y sao cho x y 1. Bài 10. Chứng minh rằng tồn tại số nguyên dương n thỏa mãn 13579n 1 chia hết cho 313579 . Bài 11. Trong một cái bát hình vuông cạnh 18 cm có 128 hạt vừng. Chứng minh rằng tồn tại hai hạt vừng có khoảng cách tới nhau nhỏ hơn 2 cm. Bài 12. Bên trong tam giác đều ABC cạnh 1 đặt 5 điểm. Chứng minh rằng tồn tại 2 điểm có khoảng cách nhỏ hơn 0,5. Bài 13. Cho hình tròn có bán kính n, ở đây n là số nguyên dương. Trong hình tròn có 4n đoạn thẳng đều có độ dài bẳng 1. Cho trước một đường thẳng d. Chứng minh rằng tồn tại đường thẳng d’ hoặc song song với d, hoặc là vuông góc với d sao cho d’ cắt ít nhất hai đoạn thẳng đã cho. Bài 14. Cho một bảng có kích thước 2n 2n ô vuông. Người ta đánh dấu vào 3n ô bất kì của bảng. Chứng minh rằng có thể chọn ra n hàng và n cột của bảng sao cho các ô được đánh dấu đều nằm trên n hàng và n cột này. Bài 15. Chứng minh rằng trong mọi đa giác lồi với số cạnh chẵn, tồn tại đường chéo không song song với một cạnh nào của đa giác. Bài 16. Một hình lập phương có cạnh bằng 15 chứa 11000 điểm. Chứng minh rằng có một hình cầu bán kính 1 chứa ít nhất 6 điểm trong số 11000 điểm đã cho. Bài 17. Giả sử 1 bàn cờ hình chữ nhật có 3x7 ô vuông được sơn đen hoặc trắng. Chứng minh rằng với cách sơn màu bất kì, trong bàn cờ luôn tồn tại hình chữ nhật gồm các ô ở 4 góc là các ô cùng màu. Bài 18. Trong một tờ giấy hình vuông bằng giấy có cạnh bằng 12 cm có 31 lỗ kim châm. Chứng minh rằng ta vẫn có thể cắt từ tờ giấy này ra một hình tròn có bán kính 1 cm mà không chứa một lỗ kim châm nào. Bài 19. Cho hình tròn (C) có diện tích bằng 8, đặt 17 điểm phân biệt bất kì. Chứng minh rằng bao giờ cũng tìm được ít nhất ba điểm tạo thành một tam giác có diện tích bé hơn 1. Bài 20. Trong hình vuông cạnh bằng 15 đặt 20 hình vuông nhỏ cạnh bằng 1 và từng đôi một không cắt nhau. Chứng minh rằng trong hình vuông lớn có thể đặt một hình tròn bán kính 1 sao cho nó không cắt hình vuông nào. 2. NGUYÊN LÝ CỰC HẠN 2.1. Nguyên lý cực hạn Nguyên lí cực hạn được phát biểu đơn giản như sau: Nguyên lí 1: Trong một tập hữu hạn và khác rỗng các số thực luôn luôn có thể chọn được số bé nhất và số lớn nhất.
5. GIÁO VIÊN: TRẦN KIM OANH Nguyên lí 2: Trong một tập khác rỗng các số tự nhiên luôn luôn có thể chọn được số bé nhất. Sử dụng nguyên lí cực hạn là một phương pháp được vận dụng cho nhiều lớp bài toán khác, đặc biệt nó có ích khi giải các bài toán tổ hợp. Trong quá trình tìm kiếm lời giải nhiều bài toán, sẽ rất có lợi nếu chúng ta xem xét các phần tử biên, phần tử giới hạn nào đó, tức là phần tử mà tại đó mỗi đại lượng hình học cá thể nhận giá trị lớn nhất hoặc giá trị nhỏ nhất, chẳng hạn như cạnh lớn nhất, cạnh nhỏ nhất của một tam giác, góc lớn nhất hoặc góc nhỏ nhất của một đa giác . Những tính chất của các phần từ biên, phần tử giới hạn nhiều khi giúp chúng ta tìm kiếm được lời giải thu gọn của bài toán. Nguyên lí cực hạn thường được sử dụng kết hợp với các phương pháp khác, đặc biệt là phương pháp phản chứng, được vận dụng trong trong trường hợp tập các giá trị cần khảo sát chỉ tập hợp hữu hạn( nguyên lí 1) hoặc có thể có vô hạn nhưng tồn tại một phần tử lớn nhất hoặc nhỏ nhất (nguyên lí 2). Khi vận dụng nguyên lí này, ta phải tiến hành các bước sau: Bước 1. Chứng minh rằng trong tất cả các giá trị cần khảo sát luôn tồn tại giá trị lớn nhất hoặc giá trị nhỏ nhất. Bước 2. Xét bài toán trong trường hợp riêng khi nó nhận giá trị này (nhỏ nhất hoặc lớn nhất) Bước 3. Chỉ ra một mâu thuẫn, chỉ ra một giá trị còn nhỏ hơn (hay lớn hơn) giá trị ta đang khảo sát . Theo nguyên lí của phương pháp phản chứng, ta sẽ suy ra điều phải chứng minh. 2.2. Một số ví dụ minh họa Ví dụ 1. Chứng minh rằng bốn hình tròn đường kính là bốn cạnh của một tự giác lồi thì phủ kín miền tứ giác ABCD. Lời giải Lấy M là một điểm tùy ý của tứ giác lồi ABCD. Có hai B khả năng xảy ra: Nếu M nằm trên biên của đa giác (tức M nằm trên một cạnh của tứ giác ABCD). Khi đó M nằm trong hình C tròn có đường kính là cạnh ấy. Trong trường hợp này kết luận của bài toán hiển nhiên đúng. M Nếu M nằm bên trong tứ giác lồi ABCD . A Khi đó ta có A· MB B· MC C· MD D· MA 3600 Theo nguyên lí cực hạn thì trong các góc D A· MB,B· MC,C· MD,D· MA luôn tồn tại một góc có số đo lớn nhất. Giả sử MaxB· MC A· MB,B· MC,C· MD,D· MA . Khi đó B· MC 900 Từ đó suy ra M nằm trong (hoặc cùng lắm là nằm trên) đường tròn đường kính BC. Vậy dĩ nhiên M bị phủ bởi đường tròn này. Như thế do M là điểm tùy ý của tứ giác ABCD, ta suy ra bốn hình tròn nói trên phủ kín tứ giác lồi đã cho. Vậy ta có điều phải chứng minh. Ví dụ 2. Cho 2011 đường thẳng phân biệt, trong đó ba đường thẳng bất kì trong số chúng thì đồng quy. Chứng minh rằng cả 2011 đường thẳng đã cho đồng quy tại một điểm. Lời giải A K P l B Q C D Ta sẽ đi giải quyết bài toán bằng phương pháp phản chứng: Giả sử ngược lại các đường thẳng đã cho không đi qua một điểm. Ta xét các giao điểm tạo nên bởi 2011 đường thẳng đã cho. Xét tất cả các khoảng cách khác 0 hạ từ các giao điểm này tới các đường thẳng đã cho. Giả sử A là một giao điểm trong số đó và gọi AQ là khoảng cách nhỏ nhất trong số đó vẽ từ A đến  đường
6. GIÁO VIÊN: TRẦN KIM OANH thẳng  trong số 2011 đường thẳng. Qua A theo giải thiết, phải có ít nhất là 3 đường thẳng, và 3 đường thẳng này cả  lần lượt tại B, C và D. Vẽ AQ vuông góc với  , thì hai trong ba điểm B, C, D phải nằm cùng một phía của điểm Q, chẳng hạn là C và D. Không mất tính tổng quát, giả sử QC QD . Vẽ CP vuông góc với AD và QK vuông góc với AD. Suy ra CP QK AQ . Điều này là vô lý vì trái với giả thiết giả sử AQ là khoảng cách bé nhất. Điều vô lí trên chứng tỏ rằng 2011 đường thẳng đã cho đồng quy tại một điểm. Ví dụ 3. Một nước có 80 sân bay mà khoảng cách giữa hai sân bay nào cũng khác nhau. Mỗi máy bay cất cánh từ một sân bay và bay đến sân bay nào gần nhất. Chứng minh rằng trên bất kỳ sân bay nào cũng không thể có quá 5 máy bay đến. Lời giải Từ giả thiết suy ra nếu các máy bay từ các sân bay M và N đến sân bay O thì khoảng cách MN là lớn nhất trong các cạnh của tam giác MON, do đó ta được M· ON 600 . Giả sử rằng các máy bay bay từ các sân bay M1 ;M2 ;M3 ;M4 ; ;Mn đến sân bay O thì một trong 3600 các góc M· ON không lớn hơn với i, j,n 1;2;3;4;5; ;80 vì tổng các góc đã cho bằng i j n 3600 . 3600 Như vậy ta có 600 do đó n 6 . Suy ra điều phải chứng minh. n Ví dụ 4. Trên mặt phẳng cho 2 2000 điểm, trong đó không có bất kỳ 3 điểm nào thẳng hàng. Người ta tô 2011 điểm bẳng màu đỏ và tô 2011 điểm còn lại bằng màu xanh. Chứng minh rằng bao giờ cũng tồn tại một cách nối tất cả các điểm màu đỏ với tất cả các điểm màu xanh bởi 2011 đoạn thẳng không có điểm nào chung. Lời giải Ta nhận thấy rằng luôn tồn tại cách nối 2011 cặp điểm với Y nhau bằng 2011 đoạn thẳng và vì có 2011 cặp điểm nên số A cách nối là hữu hạn và nếu dùng tổ hợp thì ta có thể tính được con số chính xác các cách nối. Và hiển nhiên là trong hữu hạn cách nối đó ta luôn tìm ra được một cách nối có tổng độ dài các đoạn thẳng là ngắn nhất. Ta chứng minh cách nối đó là cách mà chúng ta cần tìm. X B Thật vậy, giả sử ngược lại ta có hai đoạn thẳng AX và BY mà cắt nhau tại điểm O (giả sử A và B tô màu đỏ, còn X và Y tô màu xanh). Khi đó, nếu ta thay đoạn thẳng AX và BY bằng hai đoạn AY và BX, các đoạn còn lại giữ nguyên thì ta có cách nối này có tính chất: AY BX AO OY BO OX AO OX BO OY Từ đó ta được AY BX AX BY . Như vậy, việc thay hai đoạn thẳng AX và BY bằng hai đoạn thẳng AY và BX , ta nhận được một cách nối mới có tổng độ dài đoạn thẳng là nhỏ hơn. Điều này vô lý vì trái với giả thiết là đã chọn cách nối có tổng các độ dài là bé nhất. Điều đó chứng tỏ cách nối có tổng độ dài các đoạn thẳng là ngắn nhất là không có điểm chung. Ví dụ 5. Bên trong một hình vuông cạnh 1 cho n điểm sao cho không có ba điểm thẳng hàng. Chứng minh rằng tồn tại môt tam giác có đỉnh tại các điểm đã cho và diện tích S của nó thỏa mãn 1 bất đẳng thức S n 2 Lời giải
7. GIÁO VIÊN: TRẦN KIM OANH Xét bao lồi của n điểm nằm bên trong hình vuông. Vì không A2 A 3 có ba điểm nào thẳng hàng, nên bao lồi là đa giác lồi có k đỉnh k n , ngoài ra các điểm đã cho hoặc là đỉnh của đa giác lồi, hoặc nằm hẳn bên trong đa giác lồi. Chỉ có hai khả A1 năng xảy ra Nếu k n , khi đó số đường chéo xuất phát từ A1 của đa giác bao lồi tạo thành cùng các cạnh của đa giác n 2 tam giác. Gọi S là diện tích tam giác nhỏ nhất trong n 2 tam An giác ấy Vì tổng các diện tích của n 2 tam giác nhỏ hơn 1(chú ý 1 là diện tích hình vuông chứa chọn 1 n 2 tam giác này). Từ đó suy ra S . n 2 Nếu k n , khi đó bên trong đa giác bao lồi A1A2 Ak có n k điểm Ak 1 ,Ak 2 , ,An . Nối Ak 1 với các đỉnh A1 ; A2 ; ; Ak . Khi đó có k tam giác Ak 1A1A2 ; Ak 1A2A3 ; ; Ak 1AkA1 Vì không có ba điểm nào thẳng hàng, nên các điểm A2 A3 Ak 2 , ,An phải nằm hẳn trong k tam giác nói trên. Giả sử Ak 2 nằm hẳn trong tam giác nào đó. Nối Ak 2 với ba đỉnh của tam giác này thì từ một tam giác sẽ có ba A1 Ak+1 tam giác mới . Sau mỗi lần làm số tam giác tăng lên 2. Như vậy ta đi đến k 2 n k – 1 2n – k – 2 n – 2 n – k tam giác A k mà bên trong mỗi tam giác này không có điểm nào thuộc n điểm đã cho. Gọi S là diện tích bé nhất trong các tam giác trên, thế thì 1 1 S n – 2 n – k n 2 1 Bất đẳng thức S được chứng minh. n 2 Nhận xét: Ta có một số bài toán tương tự. Bài toán 1. Cho n điểm nằm trong tam giác ABC có diện tích là 1cm2 . Chứng minh rằng từ n điểm 1 đó cùng với 3 điểm A, B, C luôn tồn tại một tam giác có diện tích không lớn hơn cm2 . 3 2(n 1) Bài toán 2. Cho n điểm nằm trong đa giác lồi m đỉnh có diện tích là 1cm2 . Chứng minh rằng từ n điểm đó cùng với m đỉnh của đa giác, luôn tồn tại một tam giác có diện tích không lớn hơn 1 cm2 . m 2(n 1) Ví dụ 6. Cho p là số nguyên tố lớn hơn 3 và n là số tự nhiên khác 0. Chứng minh rằng pn không thể là tổng của hai lập phương của hai số nguyên dương khác nhau. Lời giải Giả sử n là số nguyên dương nhỏ nhất sao cho pn là tổng của hai lập phương của hai số nguyên dương khác nhau. Tức là ta có pn a3 b3 với a,b Z . Khi đó ta được pn a b a2 ab b2 . a b pk Do p là số nguyên tố nên từ pn a b a2 ab b2 ta được . 2 2 n k a ab b p
8. GIÁO VIÊN: TRẦN KIM OANH Dễ thấy a b 2 nên k 0 . Lại thấy a2 ab b2 ab 1 , do đó ta được n k 0 hay n k . 2 Lại có 3ab a b a2 ab b2 p2k pn k , do đó ta được 3ab chia hết cho p. Do p là số nguyên tố nên a chia hết cho p hoặc b chia hết cho p. Mà ta lại có a b pk nên ta được a và b cùng chia hết cho p. * n 3 3 n 3 3 3 Đặt a a1p; b b1p với a1 ; b1 N , khi đó từ p a b ta được p a1 b1 , điều này trái với giải sử n là số tự nhiên bé nhất thỏa mãn yêu cầu bài toán. Vậy không thỏa mãn số tự nhiên n thỏa mãn yêu cầu bài toán. 2.3. BÀI TẬP Bài 1. Chứng minh rằng nếu tất cả các cạnh của một tam giác đều nhỏ hơn 1 thì diện tích tam giác 3 nhỏ hơn . 4 Bài 2. Trên mặt phẳng đã cho 2011 điểm, khoảng cách giữa chúng đôi một khác nhau. Nối mỗi điểm trong số 2011 điểm này với điểm gần nhất. Chứng minh rằng với mỗi cách nối đó không thể nhận được một đường gấp khúc khép kín. Bài 3. Trên mặt phẳng cho 2011 điểm thỏa mãn ba điểm bất kì trong số chúng đều thẳng hàng. Chứng minh rằng 2011 điểm đã cho là thẳng hàng. Bài 4. Trên mặt phẳng có 2011 điểm bất kỳ, ít nhất ba điểm không thẳng hàng. Chứng minh rằng luôn vẽ được một đường tròn qua ba trong số 2011 điểm đã cho mà 2008 điểm còn lại không nằm ngoài đường tròn. Bài 5. Trên mặt phẳng cho m n điểm phân biệt(m, n là các số nguyên dương). Chứng minh rằng tồn tại một đường tròn không đi qua điểm nào trong các điểm trên và chứa đúng n điểm trong m n điểm đã cho. Bài 6. Trong một bảng ô vuông 10x10 người ta viết 100 số nguyên từ 1 đến 100. Mỗi hàng ta chọn ra số lớn thứ ba trong 10 số của hàng. Chứng minh rằng tổng của 10 số được chọn không nhỏ hơn tổng của 10 số trong bất cứ một hàng nào của bảng số. Bài 7. a) Trên một mạng lưới ô vuông vô hạn trên một mặt phẳng, đặt vào mỗi ô vuông một số tự nhiên sao cho số trong mỗi ô bằng trung bình cộng của bốn số trong các ô vuông có cạnh kề với ô đó. Chứng minh tất cả các số bằng nhau. b) Nếu số trong mỗi ô bằng trung bình cộng của bốn số trong các ô vuông bốn góc. Ta có thể đặt được tối đa bao nhiêu giá trị của các số? Bài 8. Bảy người câu được 100 con cá. Biết rằng không có hai người nào câu được số cá như nhau. Chứng minh rằng có ba người câu được tổng cộng không ít hơn 50 con cá. Bài 9. Đặt các số nguyên 1; 2; 3; ; n2 vào một bàn cờ n.n n 2 một cách ngẫu nhiên, mỗi số đúng một lần, mỗi ô một số. Chứng minh rằng tồn tại hai ô vuông kề nhau(chung cạnh hoặc chung đỉnh) mà có giá trị khác nhau ít nhất n 1 . Bài 10. Cho trước một bảng m.n các số thực. Một phép biến đổi bảng là một lần ta đổi dấu của tất cả các số trong một hàng hay một cột nào đó của bảng. Chứng minh rằng ta luôn có thể thực hiện được một dãy hữu hạn các phép biến đổi bảng để kết quả thu được là một bảng với tổng các số trong một dòng, một cột bất kì đều không âm. Bài 11. Trong một buổi tiệc với một số lượng người tham gia nhất định, xét quan hệ “bạn bè” theo nghĩa: “Nếu A là bạn của B thì B cũng là bạn của A”. Chứng minh rằng người trong buổi tiệc luôn có thể chia làm hai nhóm để đưa vào trong hai phòng khác nhau sao cho: Với mỗi người trong một phòng bất kì, ít nhất một nửa số bạn của người đó ở phòng còn lại. Bài 12. Trong các ô của bảng vuông kích thước n.n ô vuông, người ta viết các số sao cho tổng của các số có mặt trong các ô của một “chữ thập” (tức là hình gồm một hàng và một cột) bất kỳ không nhỏ hơn a. Tính giá trị nhỏ nhất của tổng các ô trong bảng. Bài 13. Lấy 2011 điểm thuộc miền trong của tứ giác để cùng với 4 đỉnh ta được 2015 điểm, trong đó không có ba điểm nào thẳng hàng. Biết diện tích của tứ giác ban đầu là 1cm 2. Chứng minh rằng 1 tồn tại một tam giác có 3 đỉnh lấy từ 2015 điểm đã cho có diện tích không vượt quá cm2. 4024
9. GIÁO VIÊN: TRẦN KIM OANH Bài 14. Trong mặt phẳng cho tập hợp P gồm hữu hạn điểm bất kỳ không cùng nằm trên một đường thẳng. Xét tất cả các đường thẳng đi qua hai điểm bất kỳ của P. Chứng minh luôn có ít nhất một đường thẳng chỉ đi qua hai điểm của P. Bài 15. Trên mặt phẳng kẻ 2016 đường thẳng sao cho không có ba đường nào đồng quy. Tam giác tao bởi ba đường thẳng trong các đường thẳng trên được gọi là tam giác xanh nếu nó không bị đường thẳng cào trong số các đường thẳng còn lại cắt. Gọi k là số tam giác xanh có thể có được từ các đường thẳng trên. a) Chứng minh rằng số tam giác xanh không ít hơn 672. b) Chứng minh rằng số tam giác xanh không ít hơn 1344. Bài 16. Chứng minh rằng nếu a, b là các số nguyên dương nguyên tố cùng nhau thì tồn tại các số nguyên x, y sao cho ax by 1. Bài 17. Trên một vòng tròn người ta xếp ít nhất bốn số thực không âm có tổng bằng 1. Chứng minh 1 rằng tổng của tất cả các tích hai số kề nhau không lớn hơn . 4 Bài 18. Cho n là một số nguyên dương và các số nguyên dương a1 ;a2 ;a3 ; ;an có tổng bằng 2n 1 . Chứng minh rằng tồn tại một số số trong các số nguyên dương trên có tổng bằng n. Bài 19. Cho 5 số nguyên phân biệt sao cho tổng ba số bất kì trong chúng luôn lớn hơn tổng hai số còn lại. Tìm giá trị nhỏ nhất của tích năm số nguyên đó. 3. Nguyên lý bất biến 3.1. Giới thiệu phương pháp đại lượng bất biến Cho a, b, c là những số thực ta xét tổng S a b c . Nếu ta đổi chỗ a cho b, b cho c, c cho a, thì tổng S luôn luôn chỉ là một (không đổi). Tổng này không thay đổi đối với thứ tự phép cộng. Dù a, b, c có thay đổi thứ tự như thế nào chăng nữa S vẫn không thay đổi, nghĩa là S bất biến đối với việc thay đổi các biến khác. Trong thực tế cũng như trong toán học, rất nhiều vấn đề liên quan đến một số đối tượng nghiên cứu lại bất biến đối với sự thay đổi của nhiều đối tượng khác. 3.2. Giải toán bằng đại lượng bất biến Để giải toán được bằng đại lượng bất biến ta thực hiện theo các bước sau: + Bước 1: Ta phải phát hiện ra những đại lượng bất biến trong bài toán. Bước này tương đối khó nếu ta không luyện tập thường xuyên. + Bước 2: Xử lý tiếp đại lượng bất biến để tìm ra các điểm mâu thuẫn. 3.3. Một số ví dụ minh họa Ví dụ 1. Mỗi lần cho phép thay thế cặp số (a, b) thuộc tập hợp M cho dưới đây bằng cặp số (a + c, b + d) trong đó cặp số (c, d) cũng thuộc M. Hỏi sau một số hữu hạn lần thay thế ta có thể nhận được tập hợp các cặp số như trong tập hợp M1 hay không? M (16, 2), (4, 32), (6, 62), (78, 8) M1 (2018,702), (844, 2104), (1056, 2176), (2240, 912) Lời giải Ta thấy hai số trong cùng một cặp số của tập hợp M đều có cùng số dư khi chia cho 7. Do đó với hai cặp số a; b , c; d thuộc tập hợp M, ta có
10. GIÁO VIÊN: TRẦN KIM OANH a 7m r; b 7n r và c 7i q; d 7k q Với m, n, i, k, r, q N và 0 r, q 7 . Khi đó ta được a c 7 m i r q; b d 7 n k r q Suy ra a c; b d có cùng số dư khi chia cho 7. Như vậy sau một số hữu hạn lần thay đổi, tập hợp gồm các cặp số như vậy vẫn giữ nguyên tính chất hai số trong cùng một cặp số có cùng số dư khi chia cho 7. Trong khi đó ở tập hợp M1 có chứa cặp số 2240; 912 có 22407 và 912 chia 7 dư 2. Như vậy sau một số hữu hạn lần thay thế ta không thể nhận được tập hợp các cặp số như trong tập hợp M1 1 Ví dụ 2. Trên bảng đen viết ba số 2; 2; . Ta bắt đầu thực hiện trò chơi như sau: Mỗi lần chơi 2 ta xoá hai số nào đó trong ba số trên bảng, giả sử là a và b rồi viết vào 2 vị trí vừa xoá hai số mới a b a b và đồng thời giữ nguyên số còn lại. Như vậy sau mỗi lần chơi trên bảng luôn có ba số. 2 2 Chứng minh rằng dù ta có chơi bao nhiêu lần đi chăng nữa thì trên bảng không đồng thời có ba số 1 ; 2; 1 2 . 2 2 Lời giải a b a b Giả sử ba số trên bảng là a,b,c , khi thay a,b bằng x và y . 2 2 2 2 a b a b a2 2ab b2 a2 2ab b2 Khi đó ta có x2 y2 a2 b2 . 2 2 2 a b a b Như vậy sau khi xoá 2 số a,b thay bởi hai số mới và thì tổng bình phương hai số 2 2 1 13 mới không đổi. Do đó tổng bình phương của ba số trên bảng không đổi và bằng 2 4 . 2 2 1 1 13 Mặt khác tổng bình phương ba số ; 2; 1 2 là 2 3 2 2 . Vậy không thể 2 2 8 2 1 đồng thời trên bảng ba số ; 2; 1 2 2 2
11. GIÁO VIÊN: TRẦN KIM OANH Ví dụ 3. Trên bảng cho 2014 số tự nhiên từ 1 đến 2014. Thực hiện liên tiếp phép biến đổi sau: Mỗi 1 lần xoá đi hai số bất kỳ a, b có trên bảng rồi viết thêm số a b ab vào bảng. Khi trên bảng chỉ 2 còn lại đúng một số thì dừng lại. Tìm số còn lại đó. Lời giải Trong quá trình biến đổi, giả sử trên bảng có dãy số a1 ; a2 ; ; an Ta xét biểu thức sau: P a1 2 a2 2 an 2 . Ta chứng minh su mỗi lần xóa thì giá trị biểu thức P giảm đi hai lần. Giả sử ta xóa đi hai số a và b khi đó tích P mất đi thừa số a 2 b 2 nhưng khi thay bằng 1 1 a 2 b 2 a b ab thì tích P có thêm thừa số a b ab 2 giảm đi một nửa nên P 2 2 2 giảm đi một nửa. Khi xóa đi hai số và thay bằng một số nên sau mỗi lần xóa trên bảng giảm đi một số. Mà trên bảng có 2014 số nên sau 2013 lần xóa thì P giảm đi 22013 lần. Khi đó ta có giá trị P 1 2 2 2 2014 2 0 Giả sử số còn lại trên bảng là x khi đó ta có P x 2 0 x 2 Vậy số cuối cùng trên bảng là 2. 1 2 2014 2015 Ví dụ 4. Trên bảng viết các số , , , , . Mỗi lần biến đổi, xóa đi hai số a, b 2015 2015 2015 2016 bất kỳ và thay bằng số a b 5ab. Hỏi sau 2014 lần thực hiện phép biến đổi trên bảng còn lại số nào? Lời giải 403 1 Trong dãy số trên có số . 2015 5 Nếu xóa hai số a và b bất kì và thay bằng số mới là c a b 5ab , như vậy sau mỗi lần xóa day trên giảm đi một số. Như vậy sau 2014 lần xóa trên bảng còn lại một số. 1 1 1 1 Đến một lúc nào đó ta sẽ xóa và một số b thì ta thay bằng c b 5. b 5 5 5 5 1 1 1 Như vậy cứ xóa số thì lại xuất hiện số . Vậy số cuối cùng còn lại là 5 5 5
12. GIÁO VIÊN: TRẦN KIM OANH 1 1 1 1 Ví dụ 5. Người ta viết lên bảng dãy số ; ; ; ; . Mỗi lần xóa đi hai số bất kì x, y trên bảng 1 2 3 2016 thì lại viết thêm số x y xy . Sau một số lần thực hiện như vậy thì trên bảng còn lại một số. Tìm số còn lại đó. Lời giải 1 1 1 1 Thực hiện cộng mỗi số trên bảng với 1 ta được dãy số 1; 1; 1; ; 1. 1 2 3 2016 Đặt x y xy m , khi đó ta được m 1 x 1 y 1 Như vậy sau mối lần xóa đi hai số x 1 và y 1 của dãy thì lại thay bởi số x 1 y 1 . Do đó lúc đấu ta có dãy số x; y;a; b;c; và sau khi xóa đi hai số x và y ta được dãy số m;a; b;c; . Chú ý rằng x 1 y 1 a 1 b 1 c 1 m 1 a 1 b 1 c 1 Như vậy sau mỗi lần xóa thì tích trên không thay đổi. Gọi k là số cuối cùng trên bảng sau khi xóa thì ta được 1 1 1 1 k 1 1 1 1 1 2017 1 2 3 2016 Do đó ta được k 2016 hay số cuối cùng còn lại trên bảng là 2016. Nhận xét: Ta phát hiện ra tình chất bất biến nhờ đẳng thức xy x y 1 x 1 y 1 . Như vậy nếu giữ nguyên đẳng thức này và thay đổi dãy số trên thì ta tìm được bài toán mới hoặc thay đổi đẳng thức trên ta cũng được bài toán mới. Người ta viết lên bảng dãy số 1; 2; 3; ; 2016 . Mỗi lần xóa đi hai số bất kì x, y trên bảng thì lại viết thêm số x y xy . Sau một số lần thực hiện như vậy thì trên bảng còn lại một số. Tìm số còn lại đó. 1007 1007 1007 1007 Người ta viết lên bảng dãy số ; ; ; ; . Mỗi lần xóa đi hai số bất kì x, y trên 1 2 3 2013 bảng thì lại viết thêm số 2xy x y 1. Sau một số lần thực hiện như vậy thì trên bảng còn lại một số. Tìm số còn lại đó. Nếu số cốc lúc đầu là 1998 chiếc ở trạng thái ngửa, ta thực hiện các bước đi như sau: Đánh số thứ tự 1998 cốc ở trạng thái ngửa là 1, 2, 3, , 1998. Bước thứ nhất ta chuyển 100 cốc đầu tiên về trạng thái úp, thức hiện như vậy sau cho đến khi 1800 cốc đầu tiên được chuyên sang trạng thái úp. Tiếp theo ta chuyển trạng thái các cốc số 1801, 1803, 1804, ,1901 về trạng thái úp(cốc số 1802 để nguyên trạng thái ngửa). Sau đó ta đảo các cốc số 1802, 1803, 1804, ,1901 về trang thái ngược lại(cốc số 1801 để nguyên trạng thái úp). Như vậy sau hai bước đi trên chỉ có hai cốc 1801 và 1802
13. GIÁO VIÊN: TRẦN KIM OANH chuyển sang trạng thái úp vòn các cốc còn lại vẫn ở trạng thái ngửa. Thực hiện như vậy cho đến khi còn lại 100 cốc ở trạng thái ngửa cuối cùng thì ta thực hiện một lần nữa. Khi đó tất cả 1998 cốc ở trạng thái ngửa được chuyển sang trạng thái úp. 3.4. BÀI TẬP Bài 1. Trên bảng ghi một số nguyên dương có hai chữ số trở lên. Người ta thiết lập số mới bằng cách xóa đi chữ số hàng đơn vị của số đã cho, sau đó cộng vào số còn lại 7 lần số vừa bị xóa. Ban đầu trên bảng ghi số 6100. Hỏi sau một số bước thực hiện như trên ta có thể thu được 1006 hay không ? Tại sao ? Bài 2. Giả sử rằng n là một số lẻ. Đầu tiên ta viết các số từ 1 tới 2n trên một bảng đen. Sau đó ta chọn ra hai số bất kì a, b và xoá chúng, rồi thay thế chúng bởi a b . Chứng minh rằng số còn lại cuối cùng là một số lẻ Bài 3. Người ta viết trên bảng dãy các số tự nhiên liên tiếp từ 1 đến 100. Thực hiện trò chơi như sau: Tiến hành xóa hai số a, b bất kì trong dãy số trên và viết lại một số là a3 b3 . Thực hiện trò chơi như trên cho đến khi trên bảng còn lại một số. Hỏi số còn lại trên bảng có thể là 9876543212016 không. Bài 4. Có 2010 viên sỏi. Hai người chơi thay phiên nhau bốc sỏi, mỗi lượt đi người chơi được quền bốc một số lượng viên sỏi là luỹ thừa với số mũ tự nhiên bất kì của 2(1, 2, 4, ). Ai bốc được viên sỏi cuối cùng là thắng cuộc. Giả sử cả hai người chơi đều là người thông minh. Hỏi ai là người thắng cuộc? Bài 5. Trong một hộp có 2010 viên sỏi. Có hai người tham gia trò chơi, mỗi người lần lượt phải bốc ít nhất là 11 viên sỏi và nhiều nhất là 20 viên sỏi. Người nào bốc viên sỏi cuối cùng sẽ thua cuộc. Hãy tìm thuật chơi để đảm bảo người bốc đầu tiên luôn là người thắng cuộc. 1 1 1 1 Bài 6. Trên bảng có ghi 2013 số ; ; ; ; . Mỗi lần xóa đi hai số bất kì trên bảng thì ta thay 1 2 3 2013 xy bằng số z và giữ nguyên các số còn lại. Sau 2012 lần thực hiện thì trên bảng còn lại một x y 1 số. Tìm số còn lại đó. Bài 7. Cho một hình tròn được cia thành 10 ô hình quạt. Trêm mỗi ô hình quạt ta đặt một hòn bi. Thực hiện trò chơi như sau: Mỗi lần lấy ở hai ô bất kì mỗi ô một hòn bi và chuyển sang ô liền kề theo chiều ngược nhau. Hỏi sau một số lần thực hiện trò chơi có thể chuyển tất cỏ các viên bi về cùng một ô được không. Bài 8. Cho một bảng ô vuông chứa số như hình 4a. Ta thực hiện một thuật toán T như sau: Chọn ra 2 số bất kì nằm ở hai ô vuông cạnh nhau và cộng 2 số đó với một số nguyên nào đó. Hỏi rằng sau một số lần thực hiện thuật toán T thì bảng hình vuông chứa các số như hình 4a có thể thành bảng hình vuông như hình 4b hay không ?
14. GIÁO VIÊN: TRẦN KIM OANH 1 2 3 7 8 9 4 5 6 6 2 4 7 8 9 3 5 1 Hình a Hình b Bài 9. Cho một bàn cờ quốc tế 8.8 . Hỏi rằng quân mã có thể đi nước đầu tiên từ ô dưới cùng bên trái và kết thúc ở ô trên cùng bên phải hay không. Với điều kiện nó phải đi qua tất cả các ô trên bàn cờ và mỗi ô chỉ đi qua đúng một lần Bài 10. Mỗi số trong các số a1 ;a2 ;a3 ; ;an nhận một trong hai giá trị là 1 hoặc 1. Biết rằng S a1.a2 .a3 .a4 a2 .a3 .a4 .a5  an .a1.a2 .a3 0 . Chứng minh rằng n chia hết cho 4 Bài 11. Trên mặt phẳng cho 2011 điểm sao cho không có 3 điểm nào thẳng hàng. Xét tất cả các đoạn thẳng nối các cặp điểm trong 2011 điểm này. Vẽ đường thẳng d không đi qua điểm nào trong số 2011 điểm nói trên. Chứng minh rằng nếu đường thẳng d cắt một số đoạn thẳng xét ở trên thì số đoạn thẳng bị đường thẳng d cắt là một số chẵn. Bài 12. Cho trước số nguyên dương n lẻ. Tại mỗi ô vuông của bàn cờ kích thước n x n người ta viết một số 1 hoặc 1. Gọi ak là tích của tất cả những số ghi trên hàng thứ k (tính từ trên xuống) và bk là tích của tất cả những số ghi trên cột thứ k (tính từ trái sang). Chứng minh rằng với mọi cách điền số như trên, đều có: a1 a2  an b1 b2  bn 0 . Bài 13. Ta định nghĩa viên gạch hình móc câu là hình gồm 6 ô vuông đơn vị như hình vẽ dưới đây hoặc hình nhận được do lật hình đó(sanh trái, sang phải, ) hoặc hình nhận được do xoay hình đó đi một góc. Xác định các hình chữ nhật kích thức m.n với m, n là các số nguyên dương sao cho có thể lát được bằng các viên gạnh hình móc câu. Bài 14. Cho các bảng ô vuông 6x6 dưới đây: Bảng 1 Bảng 2 Bảng 3
15. GIÁO VIÊN: TRẦN KIM OANH Thực hiện thao tác biến đổi như sau: Mỗi bước biến đổi cho phép đảo ngược dấu tất cả các ô trên cùng một hàng hoặc một cột hoặc một đường chéo hoặc dọc theo một đường bất kì song song với một trong hai đường chéo. Hỏi sau một số bước biến đổi có thể đưa một trong các bảng trên về bảng không có dấu trừ được không.