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$ .