Ôn thi học sinh giỏi môn Toán Lớp 8 - Dạng 13: Toán rời rạc (Có lời giải)

Nội dung text: Ôn thi học sinh giỏi môn Toán Lớp 8 - Dạng 13: Toán rời rạc (Có lời giải)

1. DẠNG 13: TOÁN RỜI RẠC A.Bài toán Bài 1: Cho n là số tự nhiên lẻ. Chứng minh n3 n chia hết cho 24 Bài 2: Hình vuông có 3x3 ô (như hình bên ), chứa 9 số mà tổng các số ở mỗi hàng, mỗi cột, mỗi đường chéo bằng nhau được gọi là hình vuông kỳ diệu . Chứng minh rằng số ở tâm (x) của một hình vuông kỳ diệu bằng trung bình cộng của hai số còn lại cùng hàng, hoặc cùng cột , hoặc cùng đường chéo. X Bài 3: Trong bảng ô vuông kích thước 8x8 gồm 64 ô vuông đơn vị, người ta đánh dấu 13 ô bất kỳ. Chứng minh rằng với mọi cách đánh dấu luôn có ít nhất 4 ô được đánh dấu không có điểm chung (hai ô có điểm chung là hai ô có chung đỉnh hoặc chung cạnh). Bài 4: Một giải bóng chuyền có 9 đội bóng tham gia thi đấu vòng tròn 1 lượt (hai đội bất kỳ chỉ thi đấu với nhau 1 trận). Biết đội thứ nhất thắng a1 trận và thua b1 trận, đội thứ 2 thắng a2 trận và thua b2 trận, ., đội thứ 9 thắng a9 trận và thua b9 trận. 2 2 2 2 2 2 2 2 Chứng minh rằng a1 a2 a3 a9 b1 b2 b3 b9 Bài 5: Làm thế nào để đem được 6 lít nước từ sông về nếu trong tay chỉ có 2 cái can, một can có dung tích 4 lít, một can có dung tích 9 lít và không can nào có vạch chia dung tích ? Bài 6: Trong một đề thi có 3 bài toán A,B,C.Có 25 học sinh mỗi người đều đã giải được ít nhất một trong 3 bài đó. Biết rằng: - Trong số thí sinh không giải được bài A thì số thì sinh đã giải được bài B nhiều gấp hai lần số thí sinh đã giải được bài C - Số thí sinh chỉ giải được bài A nhiều hơn số thí sinh giải được bài A và thêm bài khác là 1 người - Số thí sinh chỉ giải được bài A bằng số thí sinh chỉ giải được bài B cộng với số thí sinh chỉ giải được bài C. Hỏi có bao nhiêu thí sinh chỉ giải được bài B? Bài 7: Trong lớp học bạn An khi đã hoàn thành bài tập mà giáo viên giao cho thì đã giết thời gian bằng cách liệt kê ra một bảng các số nguyên. Bận ấy bắt đầu ghi ra một số nguyên nào đó; để có số tiếp theo, An đã cộng hoặc nhân các chữ số của số đứng liền trước. Cứ tiếp tục như thế, và rồi nhận ra rằng các số mình ghi đều là số lẻ. Hỏi có bao nhiêu số đầu tiên An có thể chọn, biết rằng nó không quá 6 chữ số. Bài 8: Cho hình vuông ABCD và 9 đường thẳng cùng có tính chất là mỗi đường thẳng chia hình 2 vuông ABCD thành hai tứ giác có tỉ số diện tích bằng .Chứng minh rằng có ít nhất 3 đường 3 thẳng trong số đó cùng đi qua một điểm.
2. Bài 9: Cho hình vuông ABCD có 13 đường thẳng bất kỳ có cùng tính chất là mỗi đường thẳng chia 2 hình vuông thành hai tứ giác có tỉ số diện tích là .Chứng minh rằng có ít nhất 4 đường thẳng trong 5 13 đường thẳng đó cùng đi qua một điểm. Bài 10: Cho đa giác đều gồm 1999 cạnh. Người ta sơn các đỉnh của đa giác bằng hai màu xanh và đỏ. Chứng minh rằng tồn tại ba đỉnh được sơn cùng một màu tạo thành một tam giác cân. B.Lời giải Bài 1: Cho n là số tự nhiên lẻ. Chứng minh n3 n chia hết cho 24 Lời giải Ta có: n3 n n n 1 n 1 Vì n 1;n;n 1 là ba số tự nhiên liên tiếp nên có một trong ba số đó chia hết cho 3. Do đó n3 n M8 (2) Vì 3 và 8 là hai số nguyên tố cùng nhau nên kết hợp với 1 ; 2 a b c 3 d e f suy ra n n M24 dpcm g h i Bài 2: Hình vuông có 3x3 ô (như hình bên ), chứa 9 số mà tổng các số ở mỗi hàng, mỗi cột, mỗi đường chéo bằng nhau được gọi là hình vuông kỳ diệu . Chứng minh rằng số ở tâm (x) của một hình vuông kỳ diệu bằng trung bình cộng của hai số còn lại cùng hàng, hoặc cùng cột , hoặc cùng đường chéo. X a b c d e f Lời giải g h i Giả sử hình vuông kỳ diệu điền các số a,b,c,d,e,f,g,h,i như hình vẽ Đặt S = a + b +c + d + e + f + g + h + i 푆 Suy ra d + e + f = b + e + h = a + e + i = c + e + g =3 (1) 4푆 Suy ra (d + e + f ) + (b + e + h) + (a + e + i) + (c + e + g)= 3 4푆 푆 S + 3e= 3 푒 = 9 (2) 2S Từ (1) và (2) suy ra: d + f = b + h = a + i = c + g = 9 = 2e (đpcm) Bài 3:
3. Trong bảng ô vuông kích thước 8x8 gồm 64 ô vuông đơn vị, người ta đánh dấu 13 ô bất kỳ. Chứng minh rằng với mọi cách đánh dấu luôn có ít nhất 4 ô được đánh dấu không có điểm chung (hai ô có điểm chung là hai ô có chung đỉnh hoặc chung cạnh). Lời giải Chi 64 ô vuông của bảng 8x8 thành 4 loại như hình vẽ (các ô cùng loại được đánh số giống nhau). Khi đó theo cách chia này rõ ràng các ô trong cùng loại sẽ không có điểm chung. Khi đánh dấu 13 điểm bất kỳ, thì 13 điểm này sẽ thuộc 4 loại ô vừa chia. Vì 13 = 4.3 + 1 nên theo nguyên lý Dirichle sẽ tồn tại ít nhất 4 ô thuộc cùng một loại, khi đó 4 ô này sẽ không có điểm chung. Suy ra đpcm. 2 1 2 1 2 1 2 3 4 3 4 3 4 3 4 1 2 1 2 1 2 1 2 3 4 3 4 3 4 3 4 1 2 1 2 1 2 1 2 3 4 3 4 3 4 3 4 1 2 1 2 1 2 1 2 3 4 3 4 3 4 3 4 Bài 4: Một giải bóng chuyền có 9 đội bóng tham gia thi đấu vòng tròn 1 lượt (hai đội bất kỳ chỉ thi đấu với nhau 1 trận). Biết đội thứ nhất thắng a1 trận và thua b1 trận, đội thứ 2 thắng a2 trận và thua b2 trận, ., đội thứ 9 thắng a9 trận và thua b9 trận. 2 2 2 2 2 2 2 2 Chứng minh rằng a1 a2 a3 a9 b1 b2 b3 b9 Lời giải Mỗi đội bóng thi đấu với 8 đội bóng khác và hai đội bất kỳ chỉ gặp nhau 1 trận nên mỗi đôi sẽ thi đấu 8 trận ai bi 8 (với i = 1;2;3; ;8) Đẳng thức cần chứng minh tương đương với: a 2 a 2 a 2 a 2 8 a 2 8 a 2 8 a 2 8 a 2 1 2 3 9 1 2 3 9 16 a1 a2 a3 a9 576 (1) Mặt khác, tổng số trận thắng của các đôi bằng tổng số trận đấu nên : 9.8 a a a a 36 (2) 1 2 3 9 2 Từ (1) và (2) suy ra đpcm. Bài 5: Làm thế nào để đem được 6 lít nước từ sông về nếu trong tay chỉ có 2 cái can, một can có dung tích 4 lít, một can có dung tích 9 lít và không can nào có vạch chia dung tích ? Lời giải
4. Ký hiệu a;b là trạng thái can 4 lít có a lít với 0 a 4 và can 9 lít có b lít với 0 b 9 . Khi đó việc lấy được 6 lít nước từ sông được diễn tả qua các trạng thái sau: 0;0 0;9 4;5 0;5 4;1 0;1 1;9 4;6 Bài 6: Trong một đề thi có 3 bài toán A,B,C.Có 25 học sinh mỗi người đều đã giải được ít nhất một trong 3 bài đó. Biết rằng: - Trong số thí sinh không giải được bài A thì số thì sinh đã giải được bài B nhiều gấp hai lần số thí sinh đã giải được bài C - Số thí sinh chỉ giải được bài A nhiều hơn số thí sinh giải được bài A và thêm bài khác là 1 người - Số thí sinh chỉ giải được bài A bằng số thí sinh chỉ giải được bài B cộng với số thí sinh chỉ giải được bài C. Hỏi có bao nhiêu thí sinh chỉ giải được bài B? Lời giải Gọi a là số học sinh chỉ giải được bài A, b là số thí sinh chỉ giải được bài B, c là số thí sinh chỉ giải được bài C, d là số thí sinh giải được 2 bài B và C nhưng không giải được bài A. Khi đó số thí sinh giải được bài A và thêm ít nhất một trong hai bài B và C là : 25 a b c d Theo bài ra ta có: b d 2 c d a 1 25 a b c d và a b c 4b c 26 b 6 Từ các đẳng thức trên ta có: d b 2c 0 c 2 Bài 7: Trong lớp học bạn An khi đã hoàn thành bài tập mà giáo viên giao cho thì đã giết thời gian bằng cách liệt kê ra một bảng các số nguyên. Bận ấy bắt đầu ghi ra một số nguyên nào đó; để có số tiếp theo, An đã cộng hoặc nhân các chữ số của số đứng liền trước. Cứ tiếp tục như thế, và rồi nhận ra rằng các số mình ghi đều là số lẻ. Hỏi có bao nhiêu số đầu tiên An có thể chọn, biết rằng nó không quá 6 chữ số. Lời giải Ta gọi số đầu tiên thỏa mãn đề bài là số chấp nhận được. Các chữ số của số chấp nhận đều phải là số lẻ, vì nếu không tích của chúng sẽ chẵn Như vậy có 5 số chấp nhận được có 1 chữ số Không thể có số chấp nhận được gồm 2 chữ số vì thế thì tổng hoặc tích các chữ số của chúng sẽ là số chẵn. Tương tự như vậy số chấp nhận được cũng không thể có 4 hoặc 6 chữ số. Ta xét các số chấp nhận được gồm ba chữ số (tổng và tích các chữ số của các số chấp nhận được gồm ba chữ số này phải là số lẻ, và chúng không thể có hai chữ số, nên và tổng và tích các chữ số không thể vượt quá 9. Như vậy số chấp nhận được gồm 3 chữ số có thể:
5. Hoặc là gồm 3 chữ số 1, Hoặc là gồm hai chữ số 1, số còn lại là 1 trong 3 chữ số 3,5,7 Hoặc gồm 1 chữ số 1 và 2 chữ số 3 Do đó có 1 9 3 13 số chấp nhận được có 3 chữ số. Tương tự như thế , ta tính được số chấp nhận được gồm 5 chữ số. Tổng các chữ số không vượt quá 45 và là số chấp nhận được nên tích không vượt quá 9, khả năng xảy ra là : Hoặc gồm 5 chữ số 1 Hoặc gồm 4 chữ số 1 và một chữ số 3 Hoặc gồm 4 chữ số 1 và một chữ số 5 Hoặc gồm ba chữ số 1 và hai chữ số 3 Do đó số các số chấp nhận được gồm 5 chữ số: 1 5 5 10 21 số Vậy số các số thỏa mãn đề bài là: 5 13 21 39 số Bài 8: Cho hình vuông ABCD và 9 đường thẳng cùng có tính chất là mỗi đường thẳng chia hình 2 vuông ABCD thành hai tứ giác có tỉ số diện tích bằng .Chứng minh rằng có ít nhất 3 đường 3 thẳng trong số đó cùng đi qua một điểm. Lời giải Các đường thẳng đã cho không thể cắt các cạnh kề nhau của hình vuông, bởi vì nếu thế chúng chia hình vuông thành một tam giác và ngũ giác (chứ không phải chia hình vuông thành hai tứ giác) Do đó, mỗi đường thẳng (trong số chín đường thẳng) đều cắt hai cạnh đối của hình vuông và không đi qua một đỉnh nào của hình vuông cả. Giả sử một đường thẳng cắt hai cạnh đối BC và AD tại các điểm M và N
6. A N D F E J B M C Bài 9: Cho hình vuông ABCD có 13 đường thẳng bất kỳ có cùng tính chất là mỗi đường thẳng chia 2 hình vuông thành hai tứ giác có tỉ số diện tích là .Chứng minh rằng có ít nhất 4 đường thẳng trong 5 13 đường thẳng đó cùng đi qua một điểm. Lời giải A E B M H F P N Q D G C Đường thẳng chia hình vuông thành hai tứ giác nên đường thẳng phải cắt hai cạnh đối của hình vuông và không đi qua đỉnh hình vuông. E,F,G,H là trung điểm AB,BC,CD,DA
7. Xét một đường thẳng chia hình vuông thành hai tứ giác, cắt HF tại N NF Nên tỉ số diện tích hai tứ giác tạo thành bằng . NH 2 NH 2 Nếu tỉ số diện tích hai tứ giác tạo thành là .Như vậy N cố định và có 4 điểm vai trò 5 NF 5 như điểm N là M, N, P,Q như hình vẽ Có 13 đường thẳng mỗi đường phải đi qua 1 trong 4 điểm phân biệt M , N,P,Q 13 3.4 1Theo nguyên tắc Dirichle sẽ tồn tại ít nhất 4 đường thẳng cùng đi qua một điểm trong 4 điểm M,N,P,Q. Bài 10: Cho đa giác đều gồm 1999 cạnh. Người ta sơn các đỉnh của đa giác bằng hai màu xanh và đỏ. Chứng minh rằng tồn tại ba đỉnh được sơn cùng một màu tạo thành một tam giác cân. Lời giải Ta có đa giác 1999 cạnh nên có 1999 đỉnh. Do đó phải tồn tại 2 đỉnh kề nhau là P và Q được sơn bởi cùng một màu – màu đỏ (Theo nguyên lý Dirichle) Vì đa giác đã cho là đa giác đều có số đỉnh lẻ, nên phải tồn tại một đỉnh nào đó nằm trên đường trung trực của đoạn thẳng PQ.Giả sử đỉnh đó là A. Nếu A tô màu đỏ thì ta có tam giác APQ là tam giác cân có 3 đỉnh A,P,Q được tô cùng màu đỏ. Nếu A tô màu xanh, lúc đó gọi B và C là các đỉnh khác của đa giác kề với P và Q. Nếu cả hai đỉnh B và C được tô màu xanh thì tam giác ABC cân và có 3 đỉnh cùng tô màu xanh. Nếu ngược lại, một trong hai đỉnh B và C mà tô màu đỏ thì tam giác BPQ hoặc tam giác CPQ là tam giác cân có 3 đỉnh được tô màu đỏ .