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$

Erdos–Ginzburg–Ziv theorem

Định lí Erdos–Ginzburg–Ziv. Cho số nguyên dương $n.$ Khi đó trong mỗi $2n-1$ số nguyên, tồn tại $n$ số có tổng chia hết cho $n.$

Chứng minh. Trước tiên ta thấy khẳng định đúng với $n=1,$ và nếu khẳng định đúng với $x>1$ và $y>1$ thì nó cũng đúng với $xy.$ Thật vậy, giả sử $a_1,a_2,\ldots,a_{2xy-1}$ là các số nguyên bất kỳ. Trước tiên, vì $2xy-1>2y-1$ nên trong các số đã cho ta có thể chọn $y$ số $a_{1j}$ sao cho $\displaystyle a_{11}+a_{12}+\cdots +a_{1y}\equiv 0\pmod{y},$ sau bước này ta còn $2xy-1-y=(2x-1)y-1>2y-1$ số. Trong $(2x-1)y-1$ số đó ta chọn $y$ số $a_{2j}$ sao cho

$a_{21}+a_{22}+\cdots+a_{2y}\equiv 0\pmod{y},$ sau bước này ta còn $(2x-2)y-1$ số. Tiếp tục làm như vậy cuối cùng ta được $(2x-1)y$ số $a_{ij}$ thỏa mãn

$a_{i1}+a_{i2}+\cdots+a_{iy}\equiv 0\pmod{y},\quad \forall i=\overline{1,2x-1}.$ Vì khẳng định đúng với $n=x$ nên trong $2x-1$ số nguyên $\displaystyle\frac{1}{y}(a_{i1}+a_{i2}+\cdots+a_{iy}),$ tồn tại $x$ số, chẳng hạn $\displaystyle\frac{1}{y}(a_{i1}+a_{i2}+\cdots+a_{iy})$ với $i=1,$ $2,\ldots,$ $x$ , có tổng chia hết cho $x.$ Khi đó $xy$ số $a_{ij}$ với $(i,j)\in [x]\times [y]$ có tổng chia hết cho $xy,$ suy ra khẳng định đúng với $xy.$

Vậy ta chỉ cần chứng minh nó đúng với các số nguyên tố. Giả sử $n=p$ là một số nguyên tố và $a_0,$ $a_1,\ldots,$ $a_{2p-2}$ là các số nguyên bất kỳ. Ta cần chỉ ra có $p$ số trong các số đã cho có tổng chia hết cho $p.$ Với mỗi số nguyên $\alpha,$ ký hiệu $(\alpha)_p$ là số dư khi chia $\alpha$ cho $p.$ Không mất tính tổng quát, giả sử $\{(a_i)_p\}$ là một dãy không giảm. Nếu tồn tại $i\in [p-1]$ sao cho $(a_i)_p=(a_{i+p-1})_p$ thì

$(a_i)_p=(a_{i+1})_p=\cdots =(a_{i+p-1})_p\Rightarrow \sum_{j=i}^{i+p-1}a_j\equiv 0\pmod{p},$ nếu không, xét $p-1$ tập $A_i=\{a_i,a_{i+p-1}\}$ và dùng hệ quả trong [1] ta có

$\mid A_1+A_2+\cdots+A_{p-1}\mid \geq \min (p,(p-1)\times 2-(p-1)+1)=p,$ suy ra với mỗi $i\in [p-1],$ tồn tại $b_i\in A_i$ để

$b_1+b_2+\cdots+b_{p-1}\equiv -a_0\pmod{p}\Rightarrow b_1+b_2+\cdots+b_{p-1}+a_0\equiv 0\pmod{p}.$ $\Box$

Tài liệu tham khảo

[1] https://nttuan.org/2014/09/29/cauchy-davenport/

IMO Shortlist 2022: Combinatorics

Trong bài này tôi sẽ dịch phần Tổ hợp trong cuốn IMO Shortlist 2022. Các năm trước bạn có thể tìm ở đường dẫn https://nttuan.org/2023/07/02/isl/.

Phần Hình của năm 2022 tôi đã dịch ở đây

IMO Shortlist 2022: Geometry

C1. Một $\pm 1$ -dãy là một dãy gồm $2022$ số $a_1, \ldots, a_{2022},$ mỗi số bằng $+1$ hoặc $-1$ . Tìm số $C$ lớn nhất sao cho, đối với bất kỳ dãy $\pm 1$ nào, tồn tại một số nguyên $k$ và các chỉ số $1 \le t_1 < \ldots < t_k \le 2022$ để $t_{i+1} - t_i \le 2$ với mọi $i$ , và $\displaystyle \left| \sum_{i=1}^{k} a_{t_i} \right| \ge C.$

C2. Ngân hàng Oslo phát hành hai loại tiền xu: nhôm (ký hiệu là $A$ ) và đồng (ký hiệu là $B$ ). Alpha có $n$ đồng xu nhôm và $n$ đồng xu đồng được sắp xếp thành một hàng theo thứ tự ban đầu tùy ý. Một chuỗi là bất kỳ dãy con nào các đồng xu liên tiếp có cùng loại. Cho một số nguyên dương cố định $k \leq 2n$ , Beta lặp đi lặp lại thao tác sau: anh ta xác định chuỗi dài nhất chứa đồng xu thứ $k$ từ bên trái và di chuyển tất cả đồng xu trong chuỗi đó sang đầu bên trái của hàng. Ví dụ: nếu $n=4$ và $k=4$ , quá trình bắt đầu từ $AABBBABA$ sẽ là

$AABBBABA \to BBBAAABA \to AAABBBBA \to BBBBAAAA \to ...$

Tìm tất cả các cặp $(n,k)$ với $1 \leq k \leq 2n$ sao cho với mỗi cách xếp các đồng xu lúc đầu, tại một thời điểm nào đó trong quá trình, $n$ đồng xu ngoài cùng bên trái có cùng loại.

C3. Trong mỗi ô vuông của một khu vườn có dạng bảng ô vuông cỡ $2022 \times 2022$ , ban đầu có một cái cây cao $0$ . Một người làm vườn và một thợ đốn gỗ thay phiên nhau chơi trò chơi sau, người làm vườn sẽ chơi ở lượt đầu tiên:

(1) Người làm vườn chọn một ô vuông trong vườn. Sau đó mỗi cây trên ô vuông đó và tất cả các ô vuông xung quanh trở thành cao hơn một đơn vị.

(2) Người thợ đốn gõ chọn bốn ô vuông khác nhau trong vườn. Sau đó mỗi cây có chiều cao dương trên các ô vuông đó sẽ trở thành thấp hơn một đơn vị.

Ta nói rằng một cái cây là hùng vĩ nếu chiều cao của nó ít nhất là $10^6$ . Tìm số $K$ lớn nhất sao cho người làm vườn có thể đảm bảo cuối cùng sẽ có $K$ cây hùng vĩ trong vườn, bất kể người thợ đốn gỗ chơi như thế nào.

C4. Cho một số nguyên $n > 3$ . Giả sử rằng $n$ đứa bé được sắp xếp thành một vòng tròn và $n$ đồng xu được phân phát cho chúng (một số bé có thể không có đồng xu nào). Ở mỗi bước, bé có ít nhất $2$ đồng xu có thể đưa $1$ đồng xu cho mỗi bé ngay bên phải và bên trái của mình. Hãy tìm tất cả các cách phân phát các đồng xu ban đầu sao cho sau một số hữu hạn bước, mỗi bé có đúng một đồng xu.

C5. Cho $m,n \geqslant 2$ là các số nguyên, $X$ là một tập hợp có $n$ phần tử, và $X_1$ , $X_2$ , $\ldots$ , $X_m$ là các tập hợp con khác rỗng phân biệt của $X$ . Một hàm $f \colon X \to \{1,2,\ldots,n+1\}$ được gọi là tốt nếu tồn tại một chỉ số $k$ sao cho $\displaystyle\sum_{x \in X_k} f(x )>\sum_{x \in X_i} f(x), \quad \forall i \ne k.$ Chứng minh rằng số hàm tốt ít nhất là $n^n$ .

C6. Cho $n$ là một số nguyên dương. Chúng ta bắt đầu với $n$ đống sỏi, mỗi đống ban đầu chỉ chứa một viên sỏi. Người ta có thể thực hiện các bước di chuyển theo hình thức sau: chọn hai đống, lấy một số viên sỏi bằng nhau từ mỗi đống và tạo thành một đống mới từ những viên sỏi này. Tìm, theo $n$ , số nhỏ nhất các đống sỏi khác rỗng mà một người có thể thu được bằng cách thực hiện một dãy hữu hạn các bước di chuyển có dạng này.

C7. Lucy bắt đầu bằng cách viết $s$ bộ $2022$ số nguyên lên bảng đen. Sau khi làm điều đó, cô ấy có thể lấy hai bộ bất kỳ (không nhất thiết phải khác nhau) $\mathbf{v}=(v_1,\ldots,v_{2022})$ và $\mathbf{w}=(w_1,\ldots,w_{ 2022})$ mà cô ấy đã viết và áp dụng một trong các thao tác sau để lấy bộ mới:

$\mathbf{v}+\mathbf{w}=(v_1+w_1,\ldots,v_{2022}+w_{2022})$

$\mathbf{v} \lor \mathbf{w}=(\max(v_1,w_1),\ldots,\max(v_{2022},w_{2022}))$

rồi viết bộ này lên bảng. Sau hữu hạn bước, theo cách này, Lucy có thể viết bất kỳ bộ $2022$ số nguyên nào lên bảng. Số $s$ nhỏ nhất có thể là bao nhiêu?

C8. Cho $n$ là một số nguyên dương. Hình vuông Bắc Âu là một bảng ô vuông $n \times n$ chứa tất cả các số nguyên từ $1$ đến $n^2$ sao cho mỗi ô chứa đúng một số. Hai ô khác nhau được gọi là kề nếu chúng có chung một cạnh. Mỗi ô chỉ kề với các ô chứa số lớn hơn được gọi là thung lũng. Đường lên dốc là một dãy gồm một hoặc nhiều ô sao cho các điều kiện sau được thỏa mãn đồng thời:

(i) ô đầu tiên trong dãy là một thung lũng,

(ii) mỗi ô tiếp theo trong dãy kề với ô trước đó,

(iii) các số trên các ô trong dãy lập thành một dãy tăng theo thứ tự.

Tìm, theo $n$ , số nhỏ nhất đường lên dốc có thể có trong một hình vuông Bắc Âu.

C9. Xét các song ánh $f:\mathbb N\times \mathbb N \to \mathbb N$ có tính chất: mỗi khi $f(x_1,y_1) > f(x_2, y_2)$ , thì $f(x_1+1, y_1) > f(x_2 + 1, y_2)$ và $f(x_1, y_1+1) > f(x_2, y_2+1)$ . Gọi $k$ là số cặp số nguyên $(x,y)$ sao cho $0\le x,y<100$ và $f(x,y)$ is số nguyên lẻ. Tìm giá trị lớn nhất và giá trị nhỏ nhất của $k$ .

IMO Shortlist 2022: Geometry

Trong bài này tôi sẽ dịch phần Hình học trong cuốn IMO Shortlist 2022. Các năm trước bạn có thể tìm ở đường dẫn https://nttuan.org/2023/07/02/isl/

—

G1. Cho ngũ giác lồi $ABCDE$ với $BC=DE.$ Giả sử có một điểm $T$ nằm trong $ABCDE$ sao cho $TB=TD,$ $TC=TE,$ và $\angle ABT = \angle TEA$ . Đường thẳng $AB$ cắt các đường thẳng $CD$ và $CT$ lần lượt tại $P$ và $Q.$ Giả sử $P,$ $B,$ $A,$ và $Q$ thẳng hàng theo thứ tự đó. Đường thẳng $AE$ cắt các đường thẳng $CD$ và $DT$ lần lượt tại $R$ và $S.$ Giả sử $R,$ $E,$ $A,$ và $S$ thẳng hàng theo thứ tự đó. Chứng minh rằng các điểm $P,$ $S,$ $Q,$ và $R$ cùng nằm trên một đường tròn.

G2. Trong tam giác nhọn $ABC$ , điểm $F$ là chân đường cao kẻ từ $A$ , $P$ là một điểm trên đoạn $AF$ . Các đường thẳng qua $P$ song song với $AC$ và $AB$ lần lượt cắt $BC$ tại $D$ và $E$ . Các điểm $X \ne A$ và $Y \ne A$ lần lượt nằm trên $(ABD)$ và $(ACE)$ sao cho $DA = DX$ và $EA = EY$ . Chứng minh rằng các điểm $B, C, X,$ và $Y$ cùng nằm trên một đường tròn.

G3. Cho $ABCD$ là một tứ giác nội tiếp. Giả sử các điểm $Q$ , $A$ , $B$ , và $P$ thẳng hàng theo thứ tự này sao cho đường thẳng $AC$ là tiếp tuyến của $(ADQ)$ , và đường thẳng $BD$ là tiếp tuyến của $(BCP)$ . Gọi $M$ và $N$ lần lượt là trung điểm của các đoạn thẳng $BC$ và $AD$ . Chứng minh ba đường thẳng sau đồng quy: đường thẳng $CD$ , tiếp tuyến của $(ANQ)$ tại $A$ , và tiếp tuyến của $(BMP)$ tại $B$ .

G4. Cho $ABC$ là một tam giác nhọn có $AC > AB$ , gọi $O$ là tâm đường tròn ngoại tiếp của nó và $D$ là một điểm trên đoạn $BC$ . Đường thẳng qua $D$ vuông góc với $BC$ lần lượt cắt các đường thẳng $AO, AC,$ và $AB$ tại $W, X,$ và $Y$ . Các đường tròn ngoại tiếp của các tam giác $AXY$ và $ABC$ cắt lại nhau tại $Z \ne A$ . Chứng minh rằng nếu $W \ne D$ và $OW = OD,$ thì $DZ$ là tiếp tuyến của $(AXY)$ .

G5. Cho $ABC$ là một tam giác và $\ell_1,\ell_2$ là hai đường thẳng song song. Giả sử với mỗi $i,$ $\ell_i$ lần lượt cắt các đường thẳng $BC$ , $CA$ , $AB$ tại $X_i,Y_i,Z_i$ . Với mỗi $i$ , gọi $\Delta_i$ là tam giác được tạo bởi đường thẳng đi qua $X_i$ và vuông góc với $BC$ , đường thẳng đi qua $Y_i$ và vuông góc với $CA$ , và đường thẳng đi qua $Z_i$ và vuông góc với $AB$ . Chứng minh rằng các đường tròn ngoại tiếp các tam giác $\Delta_1$ và $\Delta_2$ tiếp xúc với nhau.

G6. Cho $ABC$ là một tam giác nhọn có đường cao ${AH}$ và $P$ là một điểm thay đổi sao cho các đường phân giác $k$ và $\ell$ lần lượt của $\angle PBC$ và $\angle PCB$ gặp nhau trên ${AH}$ . Cho $k$ gặp ${AC}$ tại $E$ , $\ell$ gặp ${AB}$ tại $F$ và ${EF}$ gặp ${AH}$ tại $Q$ . Chứng minh rằng khi $P$ thay đổi, đường thẳng $PQ$ luôn đi qua một điểm cố định.

G7. Hai tam giác $ABC, A^{\prime}B^{\prime}C^{\prime}$ có cùng trực tâm $H$ và cùng đường tròn ngoại tiếp có tâm $O$ . Gọi $PQR$ là tam giác tạo bởi $AA^{\prime}$ , $BB^{\prime}$ và $CC^{\prime}$ , chứng minh rằng tâm đường tròn ngoại tiếp của tam giác $PQR$ nằm trên $OH$ .

G8. Cho $AA^{\prime}BCC^{\prime}B^{\prime}$ là một lục giác lồi nội tiếp sao cho $AC$ là tiếp tuyến của đường tròn nội tiếp tam giác $A^{\prime}B^{\prime}C^{\prime}$ và $A^{\prime}C^{\prime}$ là tiếp tuyến của đường tròn nội tiếp tam giác $ABC$ . Cho các đường thẳng $AB$ và $A^{\prime}B^{\prime}$ cắt nhau tại $X$ , các đường thẳng $BC$ và $B^{\prime}C^{\prime}$ cắt nhau tại $Y$ . Chứng minh rằng nếu $XBYB^{\prime}$ là một tứ giác lồi thì nó có đường tròn nội tiếp.