Chessboard comeback

Trưa nay tôi được hỏi câu V trong đề thi tuyển sinh vào lớp 10 Chuyên toán năm học 2024-2025 của Hà Nội. Trong bài này tôi sẽ phát biểu bài toán tổng quát và giới thiệu một lời giải của bài toán đó.

Bài toán. Cho một số nguyên $n$ lớn hơn $1$ và một bảng ô vuông cỡ $n\times n$ . Ban đầu một số ô vuông của bảng được tô màu đỏ. Sau đó mỗi giây, các ô vuông có chung cạnh với ít nhất hai ô đỏ sẽ được tô đỏ. Hỏi ban đầu cần tô ít nhất bao nhiêu ô vuông để sau một thời gian, tất cả các ô của bảng đều được tô đỏ?

Lời giải. Cần tô màu ít nhất $n$ ô để sau một thời gian, tất cả các ô của bảng đều được tô đỏ.

Mỗi ô vuông con được xem là có cạnh $1$ . Gọi $k$ là số ô được tô đỏ ban đầu, và ở mỗi thời điểm gọi $S$ là tổng chu vi của các vùng được tô đỏ. Ta thấy ban đầu $S\leq 4k$ và nếu tất cả các ô của bảng mang màu đỏ thì $S=4n$ . Để ý rằng sau mỗi giây $S$ không tăng. Vì thế, nếu sau một thời gian các ô đều mang màu đỏ thì $4k\geq 4n$ , suy ra $k\geq n$ .

Bây giờ nếu lúc đầu tô $n$ ô dọc theo một đường chéo chính của bảng thì sau một thời gian, tất cả các ô của bảng đều được tô đỏ. $\Box$

Vietnam TST 2023/6

Trong bài này tôi giới thiệu một lời giải của bài 6 trong đề thi chọn đội tuyển IMO 2023. Đây là lời giải của tác giả bài toán, không phải lời giải của tôi. Nếu có chỗ sai trong lời giải dưới đây thì đó là lỗi của tôi.

Với mỗi số nguyên dương $m$ , ký hiệu $[m]$ là tập gồm $m$ số nguyên dương đầu tiên.

Bài toán (Vietnam TST 2023/6). Cho số nguyên $n>2$ . Xác định số $k_n$ lớn nhất sao cho với mỗi họ $k_n$ tập con có $3$ phần tử của $[n]$ , luôn tô màu được các phần tử của $[n]$ bởi hai màu để không có tập con nào trong họ có ba phần tử cùng màu.

Lời giải. Với $n=3$ và $n=4$ thì $k_n=C_n^3$ , bởi vì ta có thể tô $2$ phần tử của $[n]$ xanh và $n-2 \leq 2$ phần tử còn lại màu đỏ và không có tập con ba phần tử cùng màu nào cả.

Với $n \geq 5$ thì $k_n \leq 9$ , bởi vì với $10$ tập con có $3$ phần tử của $[5]$ thì với mọi cách tô màu các phần tử $[5]$ bởi $2$ màu luôn có $3$ phần tử cùng màu. Với $n=5$ thì $k_5=9$ , vì với $9$ tập con $3$ phần tử tùy ý luôn có $1$ tập con $3$ phần tử không được chọn, ta có thể tô màu $3$ phần tử này màu xanh và $2$ phần tử còn lại màu đỏ, cách tô màu này thỏa mãn bài toán. Với $n=6$ , ta cũng có $k_6=9$ , vì ta có thể chia $20$ tập con $3$ phần tử của $[6]$ thành $10$ cặp, mỗi cặp là $2$ tập con bù nhau. Với $9$ tập con $3$ phần tử tùy ý của $[6]$ , luôn có $1$ cặp $(A, B)$ mà $A,$ $B$ không được chọn, ta tô $3$ phần tử của $A$ xanh, $3$ phần tử của $B$ đỏ và cách tô màu này thỏa mãn bài toán.

Mệnh đề 1. Với $n\geq 7$ thì $k_n \leq 6$ .

Chứng minh. Tồn tại $7$ tập con có $3$ phần tử của $[7]$ đôi một chung nhau không quá $1$ phần tử. Thật vậy, biểu diễn $1$ , $2, \ldots$ , $7$ là $7$ đỉnh một $7-$ giác đều. Chọn $B_1=\{1,2,4\}$ và $B_i$ là ảnh của $B_1$ quanh tâm đa giác với góc $\frac{2 \pi}{7} \times(i-1)$ . Rõ ràng các $B_i$ (như một tam giác) đôi một không có cạnh chung.

Giả sử tô màu được các phần tử của $[7]$ bởi $2$ màu sao cho không có $B_i$ nào có các phần tử cùng màu. Khi đó mỗi $B_i$ có đúng $2$ cạnh mà $2$ đỉnh của chúng khác màu. Suy ra ta có một đồ thị lưỡng phân $G[X,Y]$ , với $X$ là tập các phần tử xanh và $Y$ là tập các phần tử đỏ, có $14$ cạnh. Điều này không thể xảy ra vì $\mid X\mid +\mid Y\mid =7$ . $\Box$

Mệnh đề 2. Với $n \geq 5$ thì $k_n \geq 6$ .

Chứng minh. Ta chứng minh bằng qui nạp theo $n$ . Theo phần trình bày ở trên thì mệnh đề đúng với $n=5$ và $n=6$ . Với $n \geq 7$ , ta xét một họ gồm $6$ tập con có $3$ phần tử của $[n]$ . Tồn tại hai phần tử $a$ và $b$ của $[n]$ sao cho chúng không cùng thuộc một tập của họ này, vì $C_7^2=21>6 \times C_3^2=18$ . Bỏ $a$ , $b$ và thêm $c$ vào $[n]$ , ta có một cách tô màu thỏa mãn bài toán theo giả thiết quy nạp. Bỏ $c$ và cho lại $a, b$ về tập $[n]$ , sau đó tô màu $a$ và $b$ bởi màu của $c$ , ta có cách tô màu thỏa mãn bài toán. $\Box$

Từ mệnh đề 1 và mệnh đề 2, ta có $k_n=6$ khi $n \geq 7$ . $\Box$

Hanoi mathematical olympiad

Trong bài này tôi sẽ giới thiệu một số đề thi chọn HSG lớp 12 của Hà Nội. Mỗi năm có khoảng 500 học sinh tham gia kỳ thi này, khoảng 100 học sinh có điểm cao nhất sẽ tham gia kỳ thi chọn đội tuyển của Hà Nội dự thi chọn HSG QG (VMO).

Đề thi chọn đội tuyển Hà Nội các bạn có thể xem ở https://nttuan.org/2023/06/23/hanoitst/ .

HSG 12 Ha Noi – Nam hoc 2013 2014 Download

HSG 12 Ha Noi – Nam hoc 2014 2015 Download

HSG 12 Ha Noi – Nam hoc 2015 2016 Download

HSG 12 Ha Noi – Nam hoc 2016 2017 Download

Continue reading →