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.

IMO1986/3

The Pentagon Problem

Một bài viết rất công phu về IMO1986/3.

Trên mỗi đỉnh của một ngũ giác đều có viết một số nguyên, sao cho tổng của chúng là dương. Nếu ba đỉnh liên tiếp được viết lần lượt các số $x$ , $y$ , $z$ , với $y<0$ , thì phép toán sau được phép thực hiện: $x$ , $y$ , $z$ lần lượt được thay bởi $x+y$ , $-y$ , $z+y$ . Thao tác như vậy được thực hiện lặp đi lặp lại miễn là có ít nhất một trong năm số âm. Xác định xem quy trình này có nhất thiết phải kết thúc sau một số hữu hạn bước hay không.

IMO2011/6: Miquel circles and Steiner line

Sau khi giải xong bài IMO2023/6 ([1]) tôi vào topic thảo luận về bài toán đó trên AoPS ([2]) để tham khảo các lời giải khác. Tôi thấy parmenides51 bình luận rằng trong lịch sử IMO thì bài này là bài khó thứ nhì trong các bài hình học, bài khó nhất là bài IMO2011/6. Do tò mò tôi vào trang chủ của IMO ([3]) xem bài toán đó thế nào? Dưới đây là đề bài:

IMO2011/6. Cho tam giác nhọn $ABC$ với đường tròn ngoại tiếp $\Gamma$ . Giả sử $l$ là một tiếp tuyến nào đó của $\Gamma$ . Gọi $l_a$ , $l_b$ , và $l_c$ là những đường thẳng nhận được từ $l$ bằng cách lấy đối xứng qua $BC$ , $CA$ , và $AB$ , tương ứng. Chứng minh rằng đường tròn ngoại tiếp của tam giác tạo bởi ba đường thẳng $l_a$ , $l_b$ , và $l_c$ tiếp xúc với $\Gamma$ .

Trong điều kiện phòng thi thì thống kê chứng tỏ đây là bài hình học khó nhất trong lịch sử IMO! Ảnh sau tôi lấy từ [3], chỉ có $4$ thí sinh làm được bài toán này. Một bài toán rất rất khó!

Chỉ có 4 thí sinh làm được bài IMO2011/6.

Tôi thích bài IMO2023/6 bởi nó khá lạ so với các bài toán hình thường làm, bài IMO2011/6 này hấp dẫn tôi bởi sự giản dị. Không thể tin được là có kết quả này! Tôi quyết định lập một topic trên blog của tôi để làm việc với bài toán mỗi khi có thời gian (công việc chính của tôi là dạy đại số và số học cho các học sinh Chuyên toán bậc THPT), nó có thể lấy của tôi vài ngày hay nhiều tuần. Khi tôi đang gõ dòng này thì topic đang ở trạng thái ĐỢI, giải được bài toán tôi sẽ bấm nút CÔNG BỐ. Ở mỗi thời điểm, có được kết quả mới nào tôi sẽ sửa vào đây. Lời giải được viết theo hình vẽ trong bài, các trường hợp khác được bỏ qua.

Continue reading →

IMO2023/6: Coaxal circles

Trong bài này chúng tôi sẽ giới thiệu một lời giải của bài 6 trong kỳ thi Olympic Toán quốc tế năm 2023 (IMO 2023). Đề thi đã có ở đây https://nttuan.org/2023/07/08/imo2023-problems/

Chúng tôi trình bày lời giải theo hình vẽ tương ứng, các tình huống khác được bỏ qua. Đầu tiên ta phải hiểu thêm về đẳng thức giữa các góc trong đề bài, bởi vì ta không thể vẽ các điểm $A_1$ , $B_1$ và $C_1$ một cách tùy tiện và hy vọng giải được bài toán. Gọi $O$ là tâm của tam giác đều $ABC$ . Từ giả thiết ta có $\sum (180^{\circ}-2\widehat{A_1BC})=480^{\circ},$ suy ra $\widehat{A_1CB}+\widehat{B_1CA}=\widehat{B_2AA_1}.\quad (*)$ Đến đây ta ký hiệu $W$ là ảnh của $B_1$ qua phép quay tâm $C$ góc $+60^{\circ},$ cùng phép quay biến $A$ thành $B$ .

Khi đó $W$ thuộc tia $AA_1$ và $(*)$ được viết lại dưới dạng $\widehat{B_2CW}=\widehat{B_2AW}.$ Do đó bốn điểm $B_2$ , $A$ , $C$ , và $W$ cùng nằm trên một đường tròn. Đường tròn này có tâm là $B_1$ vì $CB_1=CW=B_1W=B_1A.$
Như vậy ta đã chứng minh được kết quả sau:

$(\alpha)$ : $B_1$ là tâm của $(CAB_2)$ , $C_1$ là tâm của $(ABC_2)$ , và $A_1$ là tâm của $(BCA_2)$ .

Tiếp theo, ta sẽ tìm hai điểm khác nhau có cùng phương tích đối với cả ba đường tròn ngoại tiếp các tam giác $AA_1A_2, BB_1B_2$ và $CC_1C_2$ . Làm được điều này là ta giải được bài toán. Mới đầu chúng tôi định giải nghĩa một cách hình học hai giao điểm của ba đường tròn, hay là chứng minh tâm của ba đường tròn thẳng hàng. Nhưng không thành công!

$(\beta)$ : Ba đường thẳng $A_1A_2$ , $B_1B_2$ , và $C_1C_2$ đồng quy. Nếu ký hiệu $T_1$ là điểm thuộc cả ba đường thẳng, thì $T_1$ có cùng phương tích đối với $(AA_1A_2)$ , $(BB_1B_2)$ , và $(CC_1C_2)$ .

Theo $(\alpha)$ , các tam giác $C_1C_2A$ và $B_1B_2A$ là các tam giác cân, suy ra
$\widehat{B_1B_2C_1}=\widehat{B_2AC_2}=\widehat{B_1C_2C_1}.$ Do đó tứ giác $B_1C_1B_2C_2$ là một tứ giác nội tiếp, tương tự ta cũng có hai tứ giác nội tiếp khác. Theo định lí về tâm đẳng phương của ba đường tròn ta có $(\beta)$ .

$(\gamma)$ : $\widehat{BAB_2}+\widehat{BB_1B_2}=\widehat{CAC_2}+\widehat{CC_1C_2}.$

Gọi $Z$ là giao điểm của $BB_1$ với $CB_2$ , và $Y$ là giao điểm của $BC_2$ với $CC_1$ . Ta có $\widehat{B_1ZC}=\widehat{A_1CB}+30^{\circ}=30^{\circ}-\widehat{BAC_1}-\widehat{B_1AC}+30^{\circ}=\widehat{B_2AB_1},$ nên tứ giác $AB_2ZB_1$ là một tứ giác nội tiếp. Chứng minh tương tự ta cũng có tứ giác $AC_1YC_2$ nội tiếp. Từ hai tứ giác nội tiếp này ta thấy vế trái và vế phải trong $(\gamma)$ lần lượt bằng $\widehat{BAZ}$ và $\widehat{CAY},$ chỉ việc để ý thêm rằng $Y$ và $Z$ đối xứng với nhau qua $AO$ là ta có $(\gamma)$ .