Chuyên đề Toán Olympic: Nguyên lý Dirichlet Nâng cao (AMO - ASMO - TIMO Level 3)

PHẦN I. LÝ THUYẾT & KỸ THUẬT XÂY DỰNG CHUỒNG NÂNG CAO (ADVANCED TECHNIQUES)

Trong các kỳ thi Olympic toán quốc tế (AMO, ASMO, TIMO, SEAMO), các bài toán Dirichlet không còn ở dạng nhận biết cơ bản (như phân loại ngày trong tuần, tháng sinh hay màu sắc viên bi thông thường). Điểm then chốt để giải quyết các bài toán phân hóa mạnh là kỹ thuật kiến tạo chuồng ẩn (Implicit Pigeonholes) và xác định đối tượng thỏ (Active Pigeons) thông qua các mô hình toán học trừu tượng.

1. Kỹ thuật phân hoạch đồng dư và tổng dồn (Modular Arithmetic & Prefix Sums)

- Nguyên lý số dư (Residue Partitioning):
Cho số nguyên dương $m \ge 2$. Mọi số nguyên $a$ khi chia cho $m$ đều có số dư $r \in \{0, 1, 2, \dots, m - 1\}$. Do đó có đúng $m$ lớp đồng dư modulo $m$.
- Nếu chọn $m + 1$ số nguyên bất kỳ, theo nguyên lý Dirichlet, luôn tồn tại ít nhất hai số $a, b$ có cùng số dư khi chia cho $m$. Khi đó: $(a - b) \ \vdots \ m$.
- Kỹ thuật tổng dồn (Prefix Sums Technique):
Cho dãy số nguyên $a_1, a_2, \dots, a_n$. Xét dãy các tổng dồn liên tiếp:

$$S_0 = 0, \quad S_1 = a_1, \quad S_2 = a_1 + a_2, \quad \dots, \quad S_n = a_1 + a_2 + \dots + a_n$$

Dãy trên gồm $n + 1$ giá trị tổng dồn. Khi chia các giá trị này cho $n$, theo nguyên lý Dirichlet, tồn tại ít nhất hai tổng $S_j$ và $S_i$ ($0 \le i < j \le n$) có cùng số dư.
Khi đó, tổng của một đoạn các phần tử liên tiếp là:

$$a_{i+1} + a_{i+2} + \dots + a_j = S_j - S_i \ \ \vdots \ \ n$$

2. Kỹ thuật nhân tử lẻ và ghép cặp số học (Odd Factorization & Pairing)

- Kỹ thuật phân tích nhân tử lẻ (Odd Part Representation):
Mọi số nguyên dương $x$ đều có thể biểu diễn duy nhất dưới dạng:

$$x = 2^k \cdot m$$

trong đó $k$ là số nguyên không âm ($k \ge 0$) và $m$ là một số nguyên dương lẻ ($m \in \{1, 3, 5, 7, \dots\}$). Số $m$ được gọi là phần lẻ (odd part) của $x$.
- Ứng dụng kinh điển: Khi xét tập hợp $S = \{1, 2, 3, \dots, 2n\}$, chỉ có đúng $n$ số lẻ $\{1, 3, 5, \dots, 2n - 1\}$. Nếu chọn ra $n + 1$ số bất kỳ từ $S$, chắc chắn có hai số có cùng phần lẻ $m$. Hai số đó sẽ có dạng $2^u \cdot m$ và $2^v \cdot m$, do đó số này chắc chắn là ước hoặc bội của số kia.
- Kỹ thuật ghép cặp đối xứng (Symmetric Pairing):
Chia tập hợp các phần tử thành các cặp rời nhau có tổng không đổi hoặc có mối liên hệ đặc biệt. Chọn số phần tử vượt quá số cặp sẽ kích hoạt nguyên lý Dirichlet.

3. Dirichlet trong hình học rời rạc và lưới ô vuông (Discrete Geometry & Grid Coloring)

- Nguyên lý bao điểm cực đại (Diameter / Bounding Box Principle):
- Nếu chia một hình phẳng diện tích $S$ thành $k$ phần nhỏ, khi đặt $k + 1$ điểm vào trong hình đó, luôn có ít nhất hai điểm cùng thuộc một phần nhỏ.
- Trong tam giác đều cạnh $a$, nếu chia thành $n^2$ tam giác đều nhỏ cạnh $\dfrac{a}{n}$, khoảng cách lớn nhất giữa hai điểm trong cùng một tam giác nhỏ là $\le \dfrac{a}{n}$.
- Kỹ thuật tô màu lưới ô vuông (Grid Coloring & Monochromatic Rectangles):
Xét một bảng ô vuông kích thước $m \times n$. Nếu mỗi ô được tô bởi một trong $c$ màu:
- Xem mỗi cột gồm $m$ ô là một cấu hình màu. Số cách tô màu một cột là $c^m$.
- Nếu $n > c^m$, luôn có hai cột được tô màu hoàn toàn giống nhau.
- Xét các cặp ô trong cùng một cột: Theo nguyên lý Dirichlet, nếu số ô trong một cột đủ lớn, sẽ có ít nhất hai ô cùng màu. Phân tích sự lặp lại vị trí của các cặp cùng màu này qua các cột sẽ dẫn đến sự tồn tại của hình chữ nhật đơn sắc (monochromatic rectangle) có 4 đỉnh cùng màu.

[Hình vẽ]

4. Nguyên lý Dirichlet tổng quát và Phương pháp cực hạn (Generalized Pigeonhole & Extremal Method)

- Dạng tổng quát (Generalized Form):
Nếu xếp $N$ đồ vật vào $k$ cái hộp thì:
- Tồn tại ít nhất một hộp chứa không ít hơn $\left\lceil \dfrac{N}{k} \right\rceil$ đồ vật (trong đó $\lceil x \rceil$ là phần nguyên trên, số nguyên nhỏ nhất $\ge x$).
- Tồn tại ít nhất một hộp chứa không nhiều hơn $\left\lfloor \dfrac{N}{k} \right\rfloor$ đồ vật.
- Phương pháp phản chứng kết hợp Cực hạn (Contradiction & Extremal Principle):
Giả sử điều cần chứng minh là sai. Khảo sát phần tử đạt giá trị cực đại (lớn nhất) hoặc cực tiểu (nhỏ nhất), từ đó chỉ ra sự mâu thuẫn về tổng số liên kết, điểm số thi đấu hoặc cấu trúc hình học.

PHẦN II. CÁC VÍ DỤ MINH HỌA (WORKED EXAMPLES - OLYMPIAD STANDARD)

Ví dụ 1 (AMO / Erdős Divisibility Theorem).
Người ta chọn ngẫu nhiên 51 số tự nhiên khác nhau từ tập hợp gồm 100 số tự nhiên đầu tiên $S = \{1, 2, 3, \dots, 100\}$. Chứng minh rằng trong các số được chọn, luôn tồn tại hai số phân biệt $a$ và $b$ sao cho số này là bội của số kia (tức là $a \ \vdots \ b$ hoặc $b \ \vdots \ a$).
(Fifty-one distinct natural numbers are chosen at random from the set of the first 100 natural numbers $S = \{1, 2, 3, \dots, 100\}$. Prove that among the chosen numbers, there always exist two numbers $a$ and $b$ such that one is divisible by the other).

Lời giải (Solution):
- Bước 1: Thiết lập cấu trúc phân tích phần lẻ.
Mọi số tự nhiên $x \in S$ đều được phân tích duy nhất thành tích của một lũy thừa của 2 và một số lẻ:

$$x = 2^k \cdot m, \quad \text{với } k \ge 0 \text{ và } m \in \{1, 3, 5, \dots, 99\}$$

- Bước 2: Xác định "Chuồng" và "Thỏ".
- "Chuồng": Các phần lẻ $m$. Vì từ 1 đến 100 có đúng 50 số lẻ $\{1, 3, 5, \dots, 99\}$, nên có tối đa 50 giá trị khả dĩ cho $m$. Ta tạo ra 50 chuồng tương ứng với 50 số lẻ này.
- "Thỏ": 51 số tự nhiên được chọn từ tập $S$.
- Bước 3: Vận dụng nguyên lý Dirichlet.
Vì có 51 số ("thỏ") nhưng chỉ có 50 giá trị phần lẻ ("chuồng"), theo nguyên lý Dirichlet, chắc chắn có ít nhất hai số được chọn có cùng phần lẻ $m$.
Gọi hai số đó là $a$ và $b$, với:

$$a = 2^u \cdot m \quad \text{và} \quad b = 2^v \cdot m \quad (u, v \in \mathbb{N}, \ u \ne v)$$

Không mất tính tổng quát, giả sử $u > v \ge 0$. Khi đó:

$$\dfrac{a}{b} = \dfrac{2^u \cdot m}{2^v \cdot m} = 2^{u - v}$$

Vì $u - v \ge 1$ nên $2^{u - v}$ là một số nguyên dương chẵn. Do đó $a$ chia hết cho $b$.
Bài toán được chứng minh hoàn toàn.

Ví dụ 2 (ASMO / Consecutive Days Problem - Prefix Sums).
Một học sinh chuyên Toán lên kế hoạch ôn luyện thi Olympic trong 30 ngày liên tiếp. Mỗi ngày bạn giải được ít nhất 1 bài toán, và tổng số bài toán bạn giải được trong cả 30 ngày không vượt quá 45 bài. Chứng minh rằng luôn tồn tại một giai đoạn gồm một số ngày liên tiếp mà trong giai đoạn đó bạn đã giải được đúng 14 bài toán.
(A student prepares for an Olympiad competition over 30 consecutive days. Each day, the student solves at least 1 problem, and the total number of problems solved over the 30 days does not exceed 45. Prove that there is a period of consecutive days during which the student solves exactly 14 problems).

Lời giải (Solution):
- Bước 1: Chuyển đổi bài toán sang mô hình dãy tổng dồn.
Gọi $a_i$ là số bài toán học sinh giải được trong ngày thứ $i$ ($1 \le i \le 30$).
Theo đề bài, ta có $a_i \ge 1$ với mọi $i$.
Xét dãy tổng dồn $S_n$ biểu thị tổng số bài toán giải được từ ngày 1 đến ngày $n$:

$$S_n = a_1 + a_2 + \dots + a_n \quad (1 \le n \le 30)$$

Vì mỗi ngày giải ít nhất 1 bài và tổng không quá 45 bài, nên dãy số $\{S_n\}$ là một dãy số nguyên dương tăng nghiêm ngặt:

$$1 \le S_1 < S_2 < S_3 < \dots < S_{30} \le 45$$

- Bước 2: Tạo thêm đối tượng để kích hoạt nguyên lý ghép cặp.
Cộng 14 vào mỗi số hạng của dãy trên, ta thu được dãy mới:

$$15 \le S_1 + 14 < S_2 + 14 < \dots < S_{30} + 14 \le 45 + 14 = 59$$

- Bước 3: Thiết lập "Thỏ" và "Chuồng".
Xét tập hợp gồm tất cả 60 số sau:

$$\mathcal{A} = \{S_1, S_2, \dots, S_{30}\} \cup \{S_1 + 14, S_2 + 14, \dots, S_{30} + 14\}$$

- Toàn bộ 60 số này đều là các số nguyên dương nằm trong đoạn từ 1 đến 59: $[1; 59]$.
- "Thỏ": 60 phần tử thuộc tập $\mathcal{A}$.
- "Chuồng": 59 giá trị nguyên từ 1 đến 59.
- Bước 4: Áp dụng nguyên lý Dirichlet.
Vì $60 > 59$, theo nguyên lý Dirichlet, trong 60 số trên phải tồn tại ít nhất hai số bằng nhau.
Mặt khác, các số trong nhóm $\{S_1, \dots, S_{30}\}$ đôi một phân biệt, và các số trong nhóm $\{S_1 + 14, \dots, S_{30} + 14\}$ cũng đôi một phân biệt.
Do đó, hai số bằng nhau buộc phải thuộc về hai nhóm khác nhau. Tức là tồn tại các chỉ số $j$ và $i$ ($1 \le i < j \le 30$) sao cho:

$$S_j = S_i + 14 \iff S_j - S_i = 14$$

Điều này có nghĩa là:

$$a_{i+1} + a_{i+2} + \dots + a_j = 14$$

Vậy từ ngày thứ $i + 1$ đến ngày thứ $j$, học sinh đó đã giải được đúng 14 bài toán.

Ví dụ 3 (TIMO Global Round / Monochromatic Rectangle on Grid).
Một bảng ô vuông kích thước $3 \times 7$ gồm 21 ô vuông đơn vị. Mỗi ô vuông được tô bằng một trong hai màu: Đỏ hoặc Xanh. Chứng minh rằng trên bảng luôn tìm được một hình chữ nhật có các cạnh song song với các cạnh của bảng sao cho cả 4 ô vuông ở 4 góc của nó đều có cùng một màu.
(A $3 \times 7$ grid consists of 21 unit squares. Each unit square is colored either Red or Blue. Prove that there always exists a rectangle with sides parallel to the grid lines whose four corner squares have the same color).

Lời giải (Solution):
- Bước 1: Khảo sát từng cột của bảng.
Bảng gồm 7 cột, mỗi cột chứa 3 ô vuông.
Mỗi ô chỉ có 2 cách tô màu (Đỏ hoặc Xanh).
Theo nguyên lý Dirichlet, trong 3 ô của một cột bất kỳ, có ít nhất $\left\lceil \dfrac{3}{2} \right\rceil = 2$ ô có cùng màu.
- Bước 2: Phân loại các cặp ô cùng màu trong mỗi cột.
Trong một cột có 3 vị trí ô (tạm gọi là ô 1, ô 2, ô 3 từ trên xuống). Số cách chọn ra 2 vị trí ô trong 3 vị trí là:

$$\binom{3}{2} = 3 \text{ cặp vị trí: } \{1, 2\}, \{2, 3\}, \{1, 3\}$$

Vì mỗi cặp vị trí có thể cùng màu Đỏ hoặc cùng màu Xanh, nên có tất cả:

$$3 \times 2 = 6 \text{ kiểu cấu hình cặp cùng màu trong một cột:}$$

1. Vị trí $\{1, 2\}$ cùng màu Đỏ.
2. Vị trí $\{2, 3\}$ cùng màu Đỏ.
3. Vị trí $\{1, 3\}$ cùng màu Đỏ.
4. Vị trí $\{1, 2\}$ cùng màu Xanh.
5. Vị trí $\{2, 3\}$ cùng màu Xanh.
6. Vị trí $\{1, 3\}$ cùng màu Xanh.
- Bước 3: Áp dụng nguyên lý Dirichlet trên toàn bảng.
- "Chuồng": 6 kiểu cấu hình cặp cùng màu.
- "Thỏ": 7 cột của bảng.
Vì có 7 cột mà chỉ có 6 kiểu cấu hình, theo nguyên lý Dirichlet, chắc chắn tồn tại ít nhất 2 cột có cùng một kiểu cấu hình cặp cùng màu.
Giả sử hai cột đó là cột $c_1$ và cột $c_2$, và chúng cùng có hai ô ở vị trí hàng $r_1$ và $r_2$ mang cùng màu (ví dụ cùng màu Đỏ).
Khi đó, 4 ô vuông tại giao điểm của hàng $r_1, r_2$ và cột $c_1, c_2$ lập thành một hình chữ nhật có 4 đỉnh cùng mang màu Đỏ.

Ví dụ 4 (SEAMO / Geometric Pigeonhole in Equilateral Triangle).
Bên trong một tam giác đều có độ dài cạnh bằng $1\text{ dm}$, người ta đặt ngẫu nhiên 10 điểm. Chứng minh rằng luôn tìm được ít nhất hai điểm có khoảng cách không vượt quá $\dfrac{1}{3}\text{ dm}$.
(Inside an equilateral triangle of side length $1\text{ dm}$, 10 points are placed arbitrarily. Prove that there are always at least two points whose distance is at most $\dfrac{1}{3}\text{ dm}$).

[Hình vẽ]

Lời giải (Solution):
- Bước 1: Phân hoạch tam giác đều ban đầu.
Chia mỗi cạnh của tam giác đều đã cho thành 3 đoạn thẳng bằng nhau, mỗi đoạn có độ dài bằng $\dfrac{1}{3}\text{ dm}$.
Qua các điểm chia, kẻ các đường thẳng song song với ba cạnh của tam giác.
Tam giác đều lớn ban đầu được phân hoạch thành:

$$3^2 = 9 \text{ tam giác đều nhỏ bằng nhau, mỗi tam giác có cạnh bằng } \dfrac{1}{3}\text{ dm.}$$

- Bước 2: Xác định "Chuồng" và "Thỏ".
- "Chuồng": 9 tam giác đều nhỏ cạnh $\dfrac{1}{3}\text{ dm}$.
- "Thỏ": 10 điểm đã cho.
- Bước 3: Đánh giá khoảng cách cực đại.
Theo nguyên lý Dirichlet, vì $10 > 9$, nên luôn có ít nhất hai điểm cùng thuộc về một tam giác đều nhỏ (kể cả trên biên).
Trong một tam giác đều có cạnh bằng $\dfrac{1}{3}\text{ dm}$, khoảng cách lớn nhất giữa hai điểm bất kỳ không thể vượt quá độ dài cạnh của tam giác đó, nghĩa là $d \le \dfrac{1}{3}\text{ dm}$.
Vậy luôn tìm được hai điểm có khoảng cách không vượt quá $\dfrac{1}{3}\text{ dm}$.

PHẦN III. BÀI TẬP LUYỆN TẬP TRÊN LỚP (CLASSROOM PRACTICE)

Bài 1 (AMO).
Cho 10 số nguyên tùy ý $a_1, a_2, \dots, a_{10}$. Chứng minh rằng luôn tồn tại một số hạng hoặc tổng của một số số hạng liên tiếp trong dãy chia hết cho 10.
(Given any 10 integers $a_1, a_2, \dots, a_{10}$. Prove that there is always either a single term or a sum of consecutive terms that is divisible by 10).

Bài 2 (ASMO).
Từ tập hợp 20 số tự nhiên đầu tiên $S = \{1, 2, 3, \dots, 20\}$, người ta chọn ra 11 số khác nhau. Chứng minh rằng trong 11 số được chọn:
a) Luôn tìm được hai số có tổng bằng 21.
b) Luôn tìm được hai số nguyên tố cùng nhau (tức là có ước chung lớn nhất bằng 1).
*(From the set of the first 20 natural numbers $S = \{1, 2, 3, \dots, 20\}$, 11 distinct numbers are chosen. Prove that among the 11 chosen numbers:
a) There are always two numbers whose sum is 21.
b) There are always two numbers that are coprime (their greatest common divisor is 1).*

Bài 3 (TIMO).
Người ta chọn 31 số tự nhiên khác nhau từ tập hợp $\{1, 2, 3, \dots, 60\}$. Chứng minh rằng trong các số được chọn, luôn tìm được hai số phân biệt sao cho số này là bội của số kia.
(Thirty-one distinct natural numbers are chosen from the set $\{1, 2, 3, \dots, 60\}$. Prove that among the chosen numbers, there always exist two numbers such that one is a multiple of the other).

Bài 4 (SEAMO).
Một kỳ thủ cờ vua tập luyện thi đấu trong 40 ngày liên tiếp. Biết rằng mỗi ngày anh ta chơi ít nhất 1 ván cờ, và trong cả 40 ngày anh ta chơi tổng cộng không quá 60 ván cờ. Chứng minh rằng luôn tồn tại một số ngày liên tiếp mà tổng số ván cờ anh ta đã chơi đúng bằng 20 ván.
(A chess player trains over 40 consecutive days. Given that he plays at least 1 game each day, and plays at most 60 games in total over the 40 days, prove that there is a period of consecutive days during which he played exactly 20 games).

Bài 5 (AMO).
Một bảng ô vuông kích thước $4 \times 19$ gồm 76 ô vuông đơn vị. Mỗi ô vuông được tô bằng một trong ba màu: Đỏ, Xanh hoặc Vàng. Chứng minh rằng trên bảng luôn tồn tại một hình chữ nhật có 4 ô ở 4 góc mang cùng một màu.
(A $4 \times 19$ grid consists of 76 unit squares. Each unit square is colored using one of three colors: Red, Blue, or Yellow. Prove that there always exists a rectangle whose four corner squares have the same color).

Bài 6 (ASMO).
Bên trong một hình vuông có độ dài cạnh bằng $2\text{ cm}$, người ta lấy ngẫu nhiên 9 điểm bất kỳ. Chứng minh rằng luôn tìm được 3 điểm trong số đó lập thành một tam giác có diện tích không vượt quá $\dfrac{1}{2}\text{ cm}^2$.
(Inside a square of side length $2\text{ cm}$, 9 points are chosen arbitrarily. Prove that there exist 3 points among them that form a triangle with area at most $\dfrac{1}{2}\text{ cm}^2$).

Bài 7 (TIMO).
Một giải bóng đá gồm 12 đội tham gia thi đấu vòng tròn một lượt (mỗi đội thi đấu với mọi đội khác đúng một trận). Biết rằng mỗi trận đấu đều có phân định thắng – thua rõ ràng (không có kết quả hòa). Chứng minh rằng khi kết thúc giải đấu, luôn tồn tại ít nhất hai đội có số trận thắng hoàn toàn bằng nhau.
(A football tournament consists of 12 teams playing in a single round-robin format (every team plays against every other team exactly once). Every match results in a win or a loss (no draws). Prove that at the end of the tournament, there are at least two teams with the exact same number of wins).

Bài 8 (SEAMO).
Một thùng kín đựng 15 quả bóng đỏ, 18 quả bóng xanh dương, 20 quả bóng vàng và 25 quả bóng xanh lá cây. Các quả bóng có kích thước và khối lượng giống hệt nhau. Không nhìn vào thùng, hỏi phải lấy ra ít nhất bao nhiêu quả bóng để chắc chắn rằng:
a) Có ít nhất 14 quả bóng cùng màu?
b) Có ít nhất 6 quả bóng của mỗi màu?
*(A closed box contains 15 red, 18 blue, 20 yellow, and 25 green balls. All balls are identical in shape and weight. Without looking into the box, what is the minimum number of balls one must draw to guarantee:
a) At least 14 balls of the same color?
b) At least 6 balls of each color?)*

Bài 9 (AMO).
Chứng minh rằng trong 6 số nguyên tùy ý bất kỳ, luôn tìm được hai số $x$ và $y$ sao cho hiệu các bình phương của chúng chia hết cho 10, tức là:

$$(x^2 - y^2) \ \vdots \ 10$$

(Prove that among any 6 arbitrary integers, there always exist two integers $x$ and $y$ such that the difference of their squares is divisible by 10, that is, $(x^2 - y^2) \ \vdots \ 10$).

Bài 10 (TIMO Global Round).
Người ta viết 10 số nguyên dương phân biệt xung quanh một vòng tròn. Biết rằng tổng của tất cả 10 số này bằng 55. Chứng minh rằng luôn tồn tại 3 số liên tiếp trên vòng tròn có tổng không nhỏ hơn 17.
(Ten distinct positive integers are written in a circle. The sum of all 10 integers is 55. Prove that there always exist 3 consecutive integers on the circle whose sum is at least 17).

PHẦN IV. BÀI TẬP VỀ NHÀ (HOMEWORK ASSIGNMENTS)

Bài 1 (HW 1).
Chọn ngẫu nhiên 51 số tự nhiên khác nhau từ tập hợp $\{1, 2, 3, \dots, 100\}$. Chứng minh rằng:
a) Luôn tìm được hai số có tổng bằng 101.
b) Luôn tìm được hai số có hiệu đúng bằng 50.
*(Fifty-one distinct natural numbers are chosen at random from the set $\{1, 2, 3, \dots, 100\}$. Prove that:
a) There are always two numbers whose sum is 101.
b) There are always two numbers whose difference is exactly 50).*

Bài 2 (HW 2).
Từ tập hợp các số $\{1, 2, 3, \dots, 30\}$, người ta chọn ra 16 số khác nhau. Chứng minh rằng trong các số được chọn, luôn tìm được hai số có tổng bằng 31 và hai số phân biệt sao cho số này chia hết cho số kia.
(From the set $\{1, 2, 3, \dots, 30\}$, 16 distinct numbers are chosen. Prove that among the chosen numbers, there are always two numbers whose sum is 31, and two distinct numbers such that one is divisible by the other).

Bài 3 (HW 3).
Một vận động viên điền kinh chạy bộ rèn luyện trong 21 ngày liên tiếp. Mỗi ngày anh ấy chạy ít nhất $1\text{ km}$, và tổng quãng đường chạy được trong 21 ngày là $30\text{ km}$. Chứng minh rằng luôn tồn tại một chuỗi các ngày liên tiếp mà trong đó anh ấy chạy được tổng cộng đúng $9\text{ km}$.
(An athlete trains by running over 21 consecutive days. Each day, he runs at least $1\text{ km}$, and the total distance run over the 21 days is $30\text{ km}$. Prove that there is a sequence of consecutive days during which he ran a total of exactly $9\text{ km}$).

Bài 4 (HW 4).
Bên trong một hình tròn có bán kính bằng $1\text{ dm}$, người ta lấy 7 điểm bất kỳ. Chứng minh rằng luôn tìm được ít nhất hai điểm có khoảng cách không vượt quá $1\text{ dm}$.
(Inside a circle of radius $1\text{ dm}$, 7 points are chosen arbitrarily. Prove that there are always at least two points whose distance is at most $1\text{ dm}$).

Bài 5 (HW 5).
Một bảng ô vuông kích thước $3 \times 11$ gồm 33 ô vuông. Mỗi ô vuông được tô bằng một trong ba màu: Xanh, Đỏ hoặc Vàng. Chứng minh rằng luôn tồn tại một hình chữ nhật có 4 ô góc cùng màu.
(A $3 \times 11$ grid contains 33 squares. Each square is colored using one of three colors: Blue, Red, or Yellow. Prove that there always exists a rectangle whose four corner squares have the same color).

Bài 6 (HW 6).
Trên mặt phẳng tọa độ $Oxy$, người ta chọn 5 điểm bất kỳ có tọa độ là các số nguyên $(x, y) \in \mathbb{Z}^2$. Chứng minh rằng luôn tìm được hai điểm trong số đó sao cho trung điểm của đoạn thẳng nối chúng cũng có tọa độ là các số nguyên.
(In the Cartesian plane $Oxy$, 5 points with integer coordinates $(x, y) \in \mathbb{Z}^2$ are chosen. Prove that there are always two points such that the midpoint of the line segment joining them also has integer coordinates).

Bài 7 (HW 7 - Ramsey Theorem $R(3,3)=6$).
Trong một căn phòng có 6 người. Biết rằng hai người bất kỳ hoặc là quen nhau, hoặc là không quen nhau (quan hệ quen biết là hai chiều). Chứng minh rằng luôn tìm được một nhóm gồm 3 người đôi một quen nhau hoặc một nhóm gồm 3 người đôi một không quen nhau.
(In a room of 6 people, any two people are either mutual acquaintances or mutual strangers. Prove that there always exist 3 people who are all mutual acquaintances or 3 people who are all mutual strangers).

Bài 8 (HW 8).
Một tủ quần áo trong phòng tối có chứa 30 chiếc tất đỏ, 24 chiếc tất xanh lá cây, 18 chiếc tất xanh dương và 12 chiếc tất đen. Các chiếc tất hoàn toàn giống nhau về kích cỡ và chất liệu. Cần lấy ra ít nhất bao nhiêu chiếc tất mà không nhìn để chắc chắn rằng:
a) Có được ít nhất 3 đôi tất thuộc 3 màu sắc khác nhau (mỗi đôi gồm 2 chiếc cùng màu)?
b) Có được ít nhất 10 chiếc tất cùng màu?
*(A wardrobe in a dark room contains 30 red socks, 24 green socks, 18 blue socks, and 12 black socks. All socks are identical in size and material. What is the minimum number of socks one must take out blindly to guarantee:
a) Having at least 3 pairs of socks of 3 different colors (each pair consisting of 2 socks of the same color)?
b) Having at least 10 socks of the same color?)*

--------- HẾT ---------