Nếu nhốt n + 1 con thỏ vào n cái chuồng thì bao giờ cũng có ít nhất một chuồng chứa ít nhất hai con thỏ.
Nếu nhốt n con thỏ vào m chuồng (m ≥ 2) thì tồn tại ít nhất một chuồng có ít nhất $\left[ \frac{n+m-1}{m} \right]$ con thỏ.
Trong một tập hợ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.
Trong một tập hợp khác rỗng các số tự nhiên luôn luôn có thể chọn được số bé nhất.
Bài toán 1: [Đề thi Olympic lớp 6 quận Hoàng Mai – Hà Nội 2011 – 2012]
Cho 14 số tự nhiên có 3 chữ số. Chứng tỏ rằng trong 14 số đó tồn tại 2 số mà khi viết chúng liên tiếp nhau ta được một số có 6 chữ số chia hết cho 13.
Lời giải:
Để giải bài này chúng ta sử dụng kết hợp phương pháp Diriclet và phân tích cấu tạo số. Cụ thể như sau:
Lấy 14 số tự nhiên chia cho 13 ta thu được 14 số dư, các số này nhận giá trị từ 0 → 12 nên chắc chắn phải có ít nhất 2 số dư giống nhau. Nghĩa là trong 14 số đã cho luôn tồn tại ít 2 số mà hiệu giữa chúng chia hết cho 13.
Đặt 2 số đó là $\overline{abc}$ và $\overline{def}$(giả sử $\overline{abc}$ ≥ $\overline{def}$). Khi đó $\overline{abcdef}$= 1000$\overline{abc}$+ $\overline{def}$= 1001$\overline{abc}$– ($\overline{abc}$– $\overline{def}$)
Vì 1001 ⁝ 13 và $\overline{abc}$– $\overline{def}$ ⁝ 13 ⇒ $\overline{abcdef}$⁝ 13. Bài toán được chứng minh!
Bài toán 2: [Đề thi Olympic lớp 6 quận Hoàng Mai – Hà Nội năm 2018 – 2019]
Viết 6 số tự nhiên bất kì vào 6 mặt của 1 con súc sắc. Chứng minh rằng khi ta gieo con súc sắc xuống mặt bàn thì trong 5 mặt nhìn thấy(khi súc sắc đã đứng yên) bao giờ cũng tìm được 1 hay nhiều mặt có tổng các số trên đó chia hết cho 5.
Lời giải:
Để giải bài toán này, ta kí hiệu số trên 5 mặt nhìn thấy được của con súc sắc là $a_{1}, a_{2}, …, a_{5}$.
Xét dãy 5 số sau: $s_{1} = a_{1}$, $s_{2} = a_{1}+a_{2}$, …, $s_{5} = a_{1}+a_{2}+...+a_{5}$.
Nếu ít nhất 1 trong các $s_{i}$ chia hết cho 5 thì bài toán được chứng minh.
Nếu không có số nào như vậy, ta lấy các $s_{i}$ đem chi cho 5 sẽ thu được 5 số dư. Các số dư này nhận các giá trị từ 1 → 4. Theo nguyên tắc Diriclet phải tồn tại 2 số dư giống nhau, giả sử $d_{i}=d_{i}$ (i < j).
Khi đó $s_{j}-s_{i}$ ⁝ 5 ⇒ $a_{i+1}+a_{i+2}+...+a_{j}$ ⁝ 5.
Đến đây bài toán được chứng minh hoàn toàn!
Bài toán 3:
a. Chứng minh rằng tồn tại số có dạng 202220222022…2022 mà số đó chia hết cho 2023.
b. Cho p là số nguyên tố lớn hơn 5. Chứng minh rằng tồn tại số tự nhiên được viết chỉ bao gồm các chữ số 1 chia hết cho p.
Lời giải:
a. Đây là bài tập khá đơn giản, ta xét dãy số gồm 2024 số như sau: 2022, 20222022, 202220222022, …, 2022…2022(gồm 2024 số 2022 viết liên tiếp).
Ta lấy 2024 số này đem chia cho 2023 ta thu được 2024 số dư, các số dư này chỉ có thể nhận 2023 giá trị từ 0 → 2022. Theo nguyên tắc Diriclet, phải tồn tại 2 số khi chia cho 2023 có cùng số dư.
Giả sử đó là $a_{i}$ = 2022…2022(gồm i số 2022 viết liên tiếp) và là $a_{j}$ = 2022…2022(gồm j số 2022 viết liên tiếp) với i > j.
Khi đó $a_{i} – a_{j}$ sẽ chia hết cho 2023.
Ta có $a_{i} – a_{j}$ = A.$10^{4j}$ trong đó A = 2022…2022(gồm i – j số 2022 viết liên tiếp). Vì (2023;$10^{4j}$) = 1 suy ra A ⁝ 2023.
Nghĩa là luôn tồn tại số có dạng 2022…2022 chia hết cho 2023.
Bài toán được chứng minh.
b. Với suy nghĩ tương tự, các bạn có thể tự làm được phần này!
Bài toán 4: [Đề thi HSG toán cấp II toàn quốc 1983]
Chứng minh rằng trong các số nguyên dương thế nào cũng có số k sao cho $1983^k - 1$ cho hết cho $10^5$
Lời giải:
Chúng ta chọn $10^5+1$ số: $1983^1 - 1$; $1983^2 - 1$; $1983^3 - 1$;...
Ta đem chia chúng cho $10^5$ ta thu được $10^5+1$ số dư, các số dư này chỉ có thể nhận các giá trị từ 0 → $10^5-1$ nên theo nguyên tắc Dirichlet phải tồn tại 2 số dư giống nhau tương ứng với 2 số bị chia ban đầu là $1983^i - 1$ và $1983^j - 1$(i > j).
Khi đó $(1983^i - 1) - (1983^j - 1) $ ⁝ $10^5$ hay $1983^j(1983^{i-j}-1)$ ⁝ $10^5$.
Vì (1983; 10) = 1 suy ra $1983^{i-j}-1$ ⁝ $10^5$. Nghĩa là khi đó k = $i-j$ chính là số thỏa mãn yêu cầu bài ra. Tổng quát bài toán, các bạn có thể tìm hiểu trong phần bài tập.
Bài toán 5: [Đề thi Olympic lớp 7 quận Hoàng Mai – Hà Nội 2012 – 2013]
Trong một nhóm học sinh có 6 bạn. Người ta nhận thấy cứ 3 bạn học sinh bất kỳ thì có 2 bạn quen nhau. Chứng minh rằng trong nhóm học sinh đó luôn tìm được 3 bạn học sinh đôi một quen nhau.
Lời giải:
Ta kí hiệu 6 học sinh tương ứng 6 điểm A1, A2, A3, A4, A5, A6 trong mặt phẳng. Hai học sinh quen nhau thì 2 điểm tương ứng được nối với nhau bởi nét liền, ngược lại được nối với nhau bởi nét đứt.
Xét 1 điểm chẳng hạn A1 khi đó A1A2, A1A3, A1A4, A1A5, A1A6 sẽ là các đoạn thẳng nối với nhau bởi 2 loại nét nói trên. Theo nguyên tắc Dirichlet thì phải tồn tại ít nhất 3 đoạn cùng loại, chẳng hạn đó là A1A2, A1A3, A1A4. Khi đó sẽ xảy ra các trường hợp:
– Nếu A1A2, A1A3, A1A4 là các nét liền: theo bài ra thì với 1 tam giác bất kỳ phải tồn tại 2 cạnh được nối với nhau bởi nét liền ⇒ Trong 3 cạnh của tam giác A2A3A4 phải có ít nhất 1 cạnh liền nét, giả sử đó là A2A3 ⇒ 3 bạn quen nhau đôi một trong trường hợp này là A1, A2 và A3.
– Nếu A1A2, A1A3, A1A4 là các nét đứt, suy ra 3 cạnh của tam giác A2A3A4 đều phải là các cạnh liền nét, nghĩa là 3 bạn quen nhau đôi một trong trường hợp này là A2, A3 và A4.
Bài toán được chứng minh.
Bài toán 6: [Đề thi toán quốc tế(IMO) lần thứ 6 tại Liên Xô – năm 1964]
Có 17 người liên lạc với nhau qua email, mỗi người đều viết thư cho những người còn lại. Trong các vấn đề của họ có 3 chủ đề được đưa ra thảo luận. Mỗi cặp chỉ thảo luận với nhau đúng một vấn đề. Chứng minh rằng có ít nhất 3 người mà họ cùng thảo luận với nhau một vấn đề.
Lời giải:
Để đơn giản ta qui về bài toán tô màu như sau:
“Trong mặt phẳng cho 17 điểm phân biệt, đoạn thẳng nối 2 điểm bất kỳ được tô bởi một trong 3 màu xanh, đỏ hoặc vàng. Chứng minh rằng tồn tại ít nhất 1 tam giác có đỉnh là 3 trong 17 điểm đã cho mà 3 cạnh cùng màu”.
Tương tự ví dụ trên, kí hiệu 17 điểm đã cho là A1, A2, A3, A4, A5, A6, A7, …, A16, A17. Nối A1 với các điểm còn lại được 16 đoạn thẳng. Vì chỉ có 3 màu tô nên theo nguyên tắc Dirichlet phải tồn tại ít nhất [(17 + 3 - 1)/2] = 6 đoạn cùng màu.
Không làm giảm tính tổng quát ta có thể giả sử đó là các đoạn A1A2, A1A3, A1A4, A1A5, A1A6, A1A7 cùng được tô màu đỏ. Khi đó nếu tồn tại đoạn thẳng nối 2 trong 6 điểm A2, A3, A4, A5, A6, A7 được tô màu đỏ. Bài toán được chứng minh.
Nếu không có đoạn nào như vậy nghĩa là các đoạn thẳng nối 2 trong 6 điểm A2, A3, A4, A5, A6, A7 được tô màu xanh hoặc vàng thì chúng ta lại quy về bài toán 6 điểm như trên.
Nói tóm lại, trong mọi trường hợp luôn tồn tại ít nhất 1 tam giác có đỉnh là 3 trong 17 điểm đã cho mà 3 cạnh cùng màu! Đồng nghĩa với có ít nhất 3 người mà họ cùng thảo luận với nhau một vấn đề. Bài toán được chứng minh.
Bài toán 7: [Đề thi Olympic lớp 7 quận Hoàng Mai – Hà Nội 2018 – 2019]
Trong mỗi ô bàn cờ kích thước 5x5 có một con kiến. Vào một thời điểm nào đó, tất cả các con kiến đều bò sang ô bên cạnh(ngang hoặc dọc ). Có thể khẳng định rằng sau khi các con kiến di chuyển sẽ luôn có ít nhất một ô trong bàn cờ không có con kiến nào trong đó không ?
Lời giải:
Ta tô màu các ô cờ bởi 2 màu đen và trắng như hình vẽ. Tổng cộng có 13 ô đen và 12 ô trắng.
Tại một thời điểm nào đó tất cả các con kiến đều bò sang ô bên cạnh nghĩa là các con ở ô trắng sẽ bò sang các ô đen và ngược lại.
Vì số con kiến ở ô đen nhiều hơn ô trắng (13 > 12) nên theo nguyên tắc Dirichlet thì sau khi bò đi sẽ có ít nhất 1 ô chứa 2 con kiến, đồng nghĩa với tồn tại ít nhất 1 ô không có con kiến nào. Khẳng định bài toán là đúng và kết quả tương tự với bàn cờ kích thước n.n với n là số nguyên dương lẻ(≥ 3).
Bài toán 8: [Đề thi HSG lớp 7 quận Hoàng Mai – Hà Nội 2013 – 2014]
Cho C là một tập hợp gồm 678 số nguyên dương đôi một khác nhau và không lớn hơn 2015. Chứng minh rằng trong tập C ta luôn tìm được 2 phần tử x; y sao cho (x – y) ∈ {5;10;15}
Lời giải:
Kí hiệu 678 số dương đó là a1, a2, …, a678. Ta xét các tập hợp sau:
M = { a1, a2, a3, …, a678}
N = { a1 + 5; a2 + 5, a3 + 5,…, a678 + 5}
P = { a1 + 15; a2 + 15, a3 + 15,…, a678 + 15}
Nhận thấy tổng các tập M, N, P có 678.3 = 2034 phẩn tử, mỗi phần tử nhận các giá trị từ 1 đến 2030. Theo nguyên tắc Dirichlet phải tồn tại ít nhất 2 phần tử cùng giá trị, 2 phần tử này không thể cùng nằm trong M, hoặc N hoặc P vì gtheo giả thiết a1, a2, …, a678 là các số đôi một khác nhau.
Xảy ra các trường hợp:
– Hai phần tử đó thuộc M và N chẳng hạn ai = aj + 5 (i≠j) ⇒ ai – aj = 5.
– Hai phần tử đó thuộc M và P chẳng hạn ai = aj + 15 (i≠j) ⇒ ai – aj = 15.
– Hai phần tử đó thuộc P và N chẳng hạn ai + 15 = aj + 5 (i≠j) ⇒ aj – ai = 10.
Bài toán được chứng minh.
BÀI TẬP TỰ GIẢI
Bài 1.1[7-8]. [Đề thi toán vô địch Bungaria lớp 8 – năm 1999]
Ba đống sỏi có 51, 49 và 5 viên. Mỗi lần chơi ta thực hiện một trong hai thao tác như sau. Một là dồn hai đống tùy ý thành một đống hoặc là chọn đống có số chẵn viên sỏi để chia thành hai đống bằng nhau.
Hỏi có thể thực hiện một dãy các nước đi như thế để chia ba đống sỏi thành 105 đống mà mỗi đống chỉ có một viên sỏi hay không?
Bài 1.2[6–7]. Trong một bảng kẻ ô vuông 9×9 người ta viết các số khác nhau từ 1 đến 81. Chứng minh rằng dù viết như thế nào thì cũng luôn tìm được 2 ô cạnh nhau (2 ô chung cạnh) mà hiệu của 2 số trong ô đó không bé hơn 6.
Bài 1.3[7–8]. [Đề thi Olympic lớp 9 quận Cầu Giấy – Hà Nội 2022 – 2023]
Trên một hòn đảo phép thuật có 2021 con tắc kè xanh, 2022 con tắc kè đỏ và 2023 con tắc kè vàng. Khi 2 con tắc kè khác màu gặp nhau thì cả hai cùng biến màu thành màu còn lại. Hỏi có khi nào tất cả các con tắc kè cùng màu không?
Bài 1.4[6–7]. [Đề thi Chọn đội tuyển Hồng Kông tham gia IMO - Vòng 1, năm 2000]
Có 1999 tách uống trà đặt trên bàn. Lúc đầu tất cả đều được đặt ngửa. Mỗi một nước đi, ta làm cho đúng 100 tách trong số chúng lật ngược lại. Sau một số nước đi, có thể làm cho tất cả chúng đều úp xuống được không? Tại sao?
Trả lời hai câu hỏi này trong trường hợp chỉ có 1998 tách.
Bài 1.5[6–7]. [Đề thi HSG lớp 7 quận Hoàng Mai – Hà Nội 2008 – 2009]
Một nhóm có 45 học sinh có số tuổi khác nhau và tổng số tuổi là 600 tuổi. Hỏi có thể tìm được 25 học sinh có tổng số tuổi lớn hơn 300 được không?
Bài 1.6[6–7]. [Đề thi Olympic lớp 6 quận Hoàng Mai – Hà Nội 2016– 2017]
Trong một cuộc thi chung kết học sinh giỏi gồm 5 học sinh. Ban giám khảo nhận thấy cứ 3 học sinh bất kỳ thì có hai người quen nhau và 2 người không quen nhau. Chứng tỏ rằng trong 5 học sinh đó có 1 bạn quen đúng 2 bạn trong nhóm.
Bài 1.7[7–8]. Ở Vương quốc “Sắc màu kỳ ảo” có 45 hiệp sĩ: 13 hiệp sĩ tóc đỏ, 15 hiệp sĩ tóc vàng, 17 hiệp sĩ tóc xanh. Khi hai hiệp sĩ có màu tóc khác nhau gặp nhau, tóc của họ sẽ lập tức đổi sang màu thứ ba. Hỏi có thể có một lúc nào đó, tất cả các hiệp sĩ đều có màu tóc giống nhau.
Bài 1.8[7–8]. Trong hộp kín có 2023 viên bi. Hai bạn An và Hòa lần lượt mỗi lần bốc ra từ 1 đến 9 viên bi khi đến lượt chơi của mình. Bạn nào bốc được những viên bi cuối cùng sẽ là người thắng cuộc. Nếu An là người thực hiện lượt chơi đầu tiên, hãy chỉ ra cách chơi để An luôn là người thắng cuộc?
Bài 1.9[7–8]. Từ 2022 số nguyên dương đầu tiên 1, 2, 3, …, 2022 số nguyên dương đầu tiên, người ta chọn ra n số phân biệt sao cho sao cho cứ 2 số bất kỳ trong đó được chọn ra thì hiệu 2 số không là ước của tổng 2 số đó. Chứng minh rằng n ≤ 674.
Hi vọng những bài toán cơ bản mở đầu này sẽ giúp các bạn hiểu cách xây dựng cấu trúc cấu trúc dữ liệu(thỏ và chuồng) để có thể áp dụng được nguyên tắc dirichlet. Chúng ta sẽ gặp lại nhau trong các phần sau với cùng chủ đề...
(còn tiếp)