Bài giảng Đại số 10 - Tiết 1: Giới thiệu nguyên lí dirichlet

ị từ 2 đến 400 có hai tổng bằng nhau Þ đpcm. Tiết 5 BÀI TẬP Bài 1:Tại một cuộc họp, một nhà Toán học tuyên bố : “ Số các nhà Toán học tham gia tại đây là một số có hai chữ số, số náy bé hơn hai lần tích 2 chữ số của nó 9 đơn vị”. Hỏi có bao nhiêu nhà Toán học tham dự cuộc họp? Hướng dẫn: Gọi số đã cho là , ta có: 10x + y + 9 = 2xy Với x = 4, ta suy ra y = 7. Các khả năng khác của x đều không cho ta giá trị y chấp nhận được . Vậy có 47 nhà Toán học tham dự. Bài 2:A và B tiến hành một trò chơi với 2001 hạt đậu. A đi nước và luân phiên nhau. Một nước đi là một lần lấy khỏi đốn hạt đậu đi 1, 2 hay 3 hạt. Người nào đi nước cuối (hết đậu trong đống), ngưới ấy thắng. Vậy người nào có chiến thuật để chiến thắng và chiến thuật đó ra sao? Hướng dẫn: A luôn chiến thắng nếu A tiến hành như sau : Nước đi đầu tiên, A lấy 1 hạt , nước tiếp theo A sẽ lấy đi 4-x hạt, với x là số hạt B lấy ở nước đi trước đó. Thật vậy, sau khi A đi đầu tiên, còn lại 2000 hạt đậu. Tiếp theo, cứ sau mỗi lần B rồi A đi, đống đậu luôn còn lạisố hạt bằng một bội số của 4. Do vậy, cuối cùng sẽ còn lại 4 hạt. Bấy giờ đến B đi và A đi nước cuối thì sẽ còn 0 hạt: A thắng. Bài 3: 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ó 3 học sinh tronh nhóm đó đồng thời ngủ gục . Hướng dẫn: Giả sử ngược lại, rằng không hề có chuyện 3 học sinh đồng thời ngủ gục. Ta sẽ chứng minh điều này mâu thuẩn. Thật vậy, trong khoảng thời gian có hai người đồng thời ngủ gục, 3 người còn lại tỉnh táo. Theo đề bài, mỗi học sinh trong nhóm đều ngủ gục đúng hai lần nên một trong hai người(đang ngủ gục) sẽ có lúc lại ngủ gục với một trong 3 người còn lại. Như vậy, nhiều nhất sẽ có tất cả là 9 khoảng thời gian diễn ra ngủ gục từng cặp. Nhưng nhóm này có 5 học sinh, số cặp là , mà chỉ có nhiều lắm là 9 khoảng thời gian. Do vậy sẽ có ít nhất một cặp không đồng thời ngủ gục. Ta có điều mâu thuẫn. Bài 4: 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: Người xếp thứ nhất không hoà trận nào. Người xếp thứ nhì không thua trận nào. Người xếp thứ tư không thắng trận nào. Hướng dẫn: Theo điều kiện của bài ra ta thấy ngay người xếp thứ nhất thắng người xếp thứ ba, thứ tư, thứ năm và được tất cả 3 điễm. Còn người thứ nhì thắng người xếp thứ nhất. Người thứ nhì hoà trong các trận đấu với người xếp thứ ba, thứ tư, thứ năm và nhận 2,5 điểm. Những người còn lại chỉ nhận số điểm lớn nhất lần lượt là 2; 1; 5; 1. Ta chứng minh họ không thể nhận ít hơn. Thật vậy, vì có 5 người nên họ chơi tất cả 10 trận và nhận tất cả 10 điểm. Nhưng người xếp thứ nhất và thứ nhì đã nhận 5,5 điểm nên ba người còn lại nhận 4,5 điểm. Mặt khác: 2 + 1,5 +1 = 4,5 nên họ không thể nhận ít hơn. Như vậy, do người thứ tư không thắng trận nào nên anh ta hoàvới người xếp thứ ba và thứ năm. Còn lại người thứ ba thắng người thứ năm. Tiết 6 BÀI TẬP Bài 1:Trong một cuộc tranh giải vô địch quốc gia về bóng đá có 20 đội tham gia. Số nhỏ nhất các trận đấu là bao nhiêu để trong 3 đội bất kỳ luôn tìm được 2 đội đã chơi với nhau? Hướng dẫn: Ta chia 20 đội thành 2 nhóm, mỗi nhóm 10 đội và chỉ các đội trong cùng1 nhóm mới thi đấu với nhau. Rõ ràng cách sắp xếp này thoả mãn các điều kiện của bài toán và tất cả có 90 trận đấu. Ta chứng minh rằng nếu các điều kiện của bài toán thoả mãn thì số trận đấu sẽ ³ 90. Giả sử ngược lại, ta tìm đôi một A đấu số trận k £ 8. Ta ký hiệu các đội đã đấu với A là X. Các đội không đấu với A là Y: X= k, Y = 19 –k. Dĩ nhiên các đội trong Y sẽ đấu với nhau nếu không hai đội thuộc Y và A sẽ là 3 đội mà không có đội nào chơi với nhau. Giả sử trong X có P cặp không chơi với nhau. Do đó mỗi đội Y phải đấu với mỗi đội trong P cặp đó của X và mỗi đội trong X có mặt không quá (k -1) cặp trong số P cặp (X có tất cả k đội). Vì vậy giữa các đội của X và Y đấu số trận bé hơn hoặc bằng = . Mặt khác: do k £ 8 nên .P ³ P. Như vậy: nếu thay các trận của các đội trong X đấu với các đội trong Y bởi các trận đấu cần thiết sẽ giảm đi. Như vậy số trận đấu cần phải tiến hành là: Vậy số các trận đấu ít nhất cần phải tiến hành là 90 Bài 2:Các học sinh được phát bài kiểm tra, mỗi môn một bài, 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. Hướng dẫn: Giá trị nhỏ nhất của n là 8. Ta biểu thị mỗi học sinh bằng một điểm trong mặt phẳng sao cho không có ba điểm nào thẳng hàng. Nếu hai học sinh đạt điểm tối ưu ở một môn nào đó, ta nối hai điểm tương ứng lại với nhau. Khi đó, theo đề bài, mỗi môn học sẽ cho tương ứng duy nhất một tam giác vàbất cứ hai tam giác nào cũng có đúng một đỉnh chung. Chú ý rằng nếu như bốn tam giác có chung một đỉnh thì tất cả các tam giác đều có chung đỉnh đó, bởi vì nếu không thì tam giác thứ năm sẽ có chung đỉnh với mỗi một trong bốn tam giác đó. Như vậy tam giác thứ năm này sẽ có bốm đỉnh, điều này mâu thuẩn. Bây giờ, nếu n ³ 8 thì một tam giác sẽ có chung một đỉnh với mỗi một trong 7 tam giác còn lại. Theo nguyên lí Dirichlet , một trong các đỉnh của nó sẽ có chung đỉnh với ít nhất ba tam giác khác, tức là tồn tại 4 tam giác có chung một đỉnh. Cuối cùng ví dụ sau đây chứng tỏ rằng trường hợp n = 7 không thỏa mãn đề bài (do vậy n < 7). Trong bảng, ta dùng dấu chéo (´) để chỉ học sinh đạt điểm tối ưu ở môn học tương ứng . Họcsinh Môn học 1 2 3 4 5 6 7 I x x x II x x x III x x x IV x x x V x x x VI x x x VII x x x Bài 3: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 ? Hướng dẫn: Ta xét một cách nối thoả mãn đề bài như sau: Với n máy tính đầu tiên mỗi máy nối với một máy in; với (m-n) máy tính còn lại, mỗi máy nối với tất cả n máy in. Số dây cáp cần dùng trong cách nối này là: S = n + n(m–n) = n (m-n +1). Ta sẽ chứng minh rằng nếu số dây cáp S < n (m-n+1) thì không thoả mãn điều kiện đầu bài.Thật vậy, do S < n (m-n+1) nên có ít nhất một máy in x nào đó được nối với không quá (m-n) máy tính. Suy ra rằng có m máy tín mà trong số đó có máy nào nối với máy in x , nghĩa là máy tính đó không thể nào đồng thời in được. Tóm lại số sợi dây cáp ít nhất cần phải dùng là S= n(m-n+1) Bài 4: Có 5 học sinh A, B, C, D, E trải qua một kỳ thi và kết quả xếp hạng được đánh số từ 1 tới 5 Người ta dự đoán rằng kết quả cuộc thi sẽ xếp theo thứ tự A, B, C, D, E .Thế nhưng lại không có học sinh nào đạt kết quả vị trí như đã dự đoán và cũng không có hai học sinh nào đạt kết quả kề nhau (thứ tự gần nhau) như dự đoán . Ví dụ hai học sinh C vàD không đạt kết quả tương ứng là 1,2 hay2,3 hay3,4 hay 4,5 Một dự đoán khác cho rằng thứ tự xếp hạng là D, A, E, C, B . Kết quả sau khi thi, có đúng 2 học sinh đã đạt vị trí dự đoán và cũng đã có được hai cặp học sinh khác nhau xếp thứ tự kề nhau như đã dự đoán . Hãy xác định kết quả xếp hạng của 5 học sinh đó. Hướng dẫn: Ta bắt đầu tự dự đoán thứ hai. Theo dự đoán này, các cặp học sinh khác nhau chỉ có thể là DA và EC, DC và CB hay AE và CB. Cũng theo dự đoán đó, có đúng hai học sinh đã đạt vị trí như dự đùoán. Do vậy, thứ tự xếp hạng là một trong những khả năng sau: DABEC (1) DACBE (2) EDACB (3) AEDCB (4) Đến đây , ta xét kết hợp với dự đoán ban đầu. Kết quả (1) không thể xảy ra vì AB rơi đúng vị trí liên tiếp như dự đoán ban đầu . Kết quả (2) cũng không xảy ra bởi C xếp đúng vị trí như dự đoán ban đầu. Cũng vậy kết quả (4) không xảy ra vì nếu thế thì A lại xếp đúng vị trí của dự đoán ban đầu. Tóm lại: E, D, A, C, B xếp theo thứ tự tương ứng từ 1 đến 5, đó là kết quả sau kỳ thi. Hết Sự tương hỗ: Ví dụ:     Có 5 đấu thủ thi đấu cờ, mỗi người đấu một trận với mỗi đấu thủ khác. Chứng minh rằng trong suốt thời gian thi đấu, luôn tồn tại hai đấu thủ có số trận đã đấu bằng nhau. Bài giải:        Gọi 5 lồng 0, 1, 2, 3, 4 thứ tự chứa các đấu thủ đã đấu 0, 1, 2, 3, 4 trận. Cũng chú ý rằng hai lông 0 và 4 không thể cùng chứa người. Như vậy chỉ có 4 lồng, mà có 5 người, tồn tại 2 người trong cùng một lồng tức là tồn tại hai đấu thủ có số trận đấu bằng nhau.       Sự sắp xếp: Ví dụ 1:       Cho một bảng vuông 4 x 4. Trên 16 ô của bảng, ta đặt 16 số tự nhiên từ 1 đến 16. Chứng minh rằng tồn tại hai ô kề nhau (tức là hai ô có một cạnh chung ) sao cho hiệu các số ở hai ô đó lớn hơn hoặc bằng 3. Bài giải:        Chuyển từ một ô bất kì sang ô kề nó gọi là một bước. Xét hai ô ghi số 1 và số 16 chuyển từ ô ghi số 1 đến ô ghi số 16 chỉ cần không quá 6 bước chuyển (nhiều nhất là 3 bước theo hàng ngang, 3 bước theo hàng dọc). Tồn tại một bước chuyển có hiệu lớn hơn hoặc bằng 3. Thật vậy giả sử tất cả các bước chuyển đều nhỏ hơn hoặc bằng 2 thì từ số 1, qua không quá 6 bước chuyển tăng thêm không quá 12, không đạt được đến số 16.      Vậy tồn tại hai ô kề nhau có hiệu các số của hai ô đó lớn hơn hoặc bằng 3. Ví dụ 2:        Viết 16 số, mỗi số có giá trị bất kỳ là 1, 2, 3, 4. Ghép thành từng cặp 2 số được 8 cặp số. Chứng minh rằng tồn tại hai cặp số mà tồng các số trong hai cặp đó bằng nhau. Bài giải:         Tổng hai số của mỗi cặp trong 8 cặp số có giá trị nhỏ nhất là: 1 + 1 = 2, có giá trị lớn nhất là: 4 + 4 = 8. Như vậy 8 tổng đó nhận 7 giá tri: (2, 3, 4, 5, 6, 7, 8). Theo nguyên lý Dirichlet, tồn tại hai tổng bằng nhau, tức là tồn tại hai cặp có tổng bằng nhau.