BÀI TẬP VỀ NGUYÊN LÝ DIRICHLET_1

Tham khảo bài viết bài tập về nguyên lý dirichlet_1, tài liệu phổ thông, ôn thi đh-cđ phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
BÀI TẬP VỀ NGUYÊN LÝ DIRICHLET_1 BÀI TẬP TỔ HỢPBài 1: CMR: tồn tại một số tự nhiên xBài 7: 8 đội tham gia giải vô dịch bóng đá trong đó hai đội bất kì phảigặp nhau đúng 1 lần biết đến cuối giải có trận nào hòa . Cm trong 8 độitrên luôn tìm được 4 đội ABC thỏa mãn A thắng B,C,D ; B thắng C,D ;C thắng D .Bài 8: Cho bảng vuông kích thước nxn trong mỗi ô vuông khích thước1x1 ta ghi 1 trong các số 0,1,2 . CM k0 tìm được bảng vuông nào màtổng các số trên 1 cột , 1 hàng hoặc 1 đường chéo là các số khác nhau .Bài 9: Cho 9 đường thẳng song song nằm ngang và 9 đường thẳng songsong nằm dọc. Người ta đánh dấu các giao điểm của chúng hoặc bằngmàu xanh hoặc bằng màu đỏ. Chứng minh rằng tồn tại hai đường nằmngang và hai đường nằm dọc mà giao điểm của chúng được đánh dấucùng màu.Trả lời ≥ 1 vì nếu xét x = 0 thì quá tầm thường.Bài 1: Tất nhiên ta xétTa xét 16 số (25 − 1) với k = 1, 2, ..., 16. Ta phải cmr với một k nàođó số 25 − 1 chia hết cho 17. Ta cm bằng phản chứng. Giả sử với mọi1≤ ≤ 16 số (25 − 1) không chia hết cho 17. => trong 16 số trênkhông có 2 số nào cho cùng số dư khi chia cho 17. Thật thế nếu với1 ≤ < ≤ 16 có (25 − 1) = 17 + và (25 − 1) = 17 + – ⇒ 17( − ) = (25 − 1) − (25 − 1) = 25 (25 − 1)⇒ (25 − 1) chia hết cho 17 với n = j - i và 1 < ≤ 16 − 1 = 15trái với giả thiết là với ∀ ∈ [1,16] số (25 − 1) không chia hết cho 17Vậy trong 16 số đang xét không có 2 số nào cho cùng số dư khi chia cho17 và từ giả thiết không có số nào cho số dư 0 khi chia cho 17. Theonguyên lý Dirichlet (16 số dư khác nhau được xếp vào 16 ngăn kéo dưkhác nhau từ 1 đển 16) thì với n nào đó mà 1 tất cả các ô = -1, max khi tất cả các ô = 1)Có 12 tổng và 11 giá trị khác nhau để lấy (-5, ..., 0, ..., 5) vậy theonguyên lý Dirichlet phải có ít nhất 2 tổng có cùng giá trị (dpcm)Bài 4:Ta xét 6 điểm trong đường tròn. Ta cmr khoảng cách giữa 2 điểmnào đó = cạnh của ngũ giác > bánkính = 1 (Ta xét cạnh P1P2. Trong tg OP1P2 cạnh P1P2 đối điện với góc720 nên lớn hơn OP1 và OP2 là những cạnh đối diện với góc 540)Bài 5: Lấy điểm P1 là tâm kẻ đường tròn C1 với bán kính bằng 1. Nếu C1chứa 25 điểm đã cho thì ta có dpcm. Giả sử P2 không thuộc C1 tức P1P2> 1. Lấy điểm P2 là tâm kẻ đường tròn C2 với bán kính bằng 1. Ngoài C1và C2 không còn điểm nào đã cho Thật thế nếu P3 nằm ngoài C1 và C2thì ta có P1P2 > 1, P1P3 > 1, P2P3 > 1, vô lý vì trong tg P1P2P3 phải có 1cạnh nhỏ hơn 1; 25 điểm nằm trong 2 đường tròn nên theo nguyên lýDirichlet trong 1 đường tròn có ít nhất 13 điểm đã choBài 6: CM trong 1005 số tùy ý chọn được ít nhát 2 số mà số này là bộisố kia hay CM trong 1005 số tùy ý chọn được có ít nhất 2 số mà sốnày là bội số kia?Nếu ta chọn 1005 số: A = (1005, 1006, ..., 2009) thì trong A không có số ≥ 2010 (tức 2*1005)nào là bội của số kia vì bội của mỗi số trongnên các bội đó không nằm trong dãy, và do đó không thể có trong A.Bài 7;Ta xét biết đến cuối giải KHÔNG có trận nào hòa.Có tất cả 28 trận đấu (bằng 2C8, hoặc ai chưa học tổ hợp thì bằng 7 + 6+ 5 + 4 + 3 + 2 + 1: đội đầu đá với 7 đội còn lại, 1 trong 7 đội đó đấu với6 đội còn lại ...)Theo nguyên lý Dirichlet phải có ít nhất 1 đội, ta gọi đó là đội A, có sốtrân thắng ít nhất là 4. Gọi 4 đội thua A là B, C, D, E. 4 đội này có vớinhau 6 trận đá, vậy theo nguyên lý Dirichlet phải có ít nhất 1 đội, ta gọiđó là đội B, có số trân thắng ít nhất là 2. Gọi 2 đội thua B là C và D. Dokhông có trận hoà nên ta gọi đội thắng trong trân C-D là C. A, B, C, D làcác đội cần tìm.Bài 8: CM k0 tìm được bảng vuông nào mà tổng các số trên 1 cột , 1hàng hoặc 1 đường chéo là các số khác nhau có nghĩa là các tổng nàykhông thể khác nhau từng đôi một?Ta có tổng cộng tất cả (2n + 2) hàng, cột và đường chéo (n hàng, n cột, 2đường chéo). Các tổng là những số thỏa mãn 0 Chiếu tất cả các cặp ô vuông lên 1 hàng ngang nào đó. Do không có 1hình chữ nhật nào có cả 4 ô vuông xanh, nên các hình chiếu là đôi một . = 36hình chiếu, nênkhác nhau. Nhưng do chỉ có tối đa ( )∑ ≤ 36 ⇔ ∑ ≤ 72 + ≤ 9∑Theo BĐT Cauchy-Schwarz, ≤ 9( + 72) , và đến đây dễ dàng giải ra S 41Vậy điều giả sử là sai và ta có đpcm./.