IMO2021/6

Trong bài này tôi giới thiệu hai lời giải cho bài 6 trong đề thi IMO 2021, lời giải thứ hai có dùng bổ đề Siegel mà tôi đã giới thiệu cách đây rất lâu ở đường dẫn https://nttuan.org/2007/10/21/siegel/. Các bạn có thể tìm các bài toán khác trong đề IMO 2021 ở đây https://nttuan.org/2021/07/25/imo2021/

Bài toán (IMO2021/6). Cho số nguyên $m\ge 2,$ $A$ là một tập hữu hạn các số nguyên và $B_1,$ $B_2,$ …, $B_m$ là các tập con của $A$ . Giả sử rằng với mỗi $k=1,2,...,m$ , tổng các phần tử của $B_k$ là $m^k$ . Chứng minh rằng $A$ có ít nhất $\frac{m}{2}$ phần tử.

Lời giải 1. Đặt $k=|A|$ và giả sử $A = \{a_1,a_2,\ldots,a_k\}$ . Từ giả thiết, với mỗi $i\in [m]$ , ta có $\displaystyle m^i = \sum_{j=1}^{k}b_{i,j}a_{j}\quad (1)$ với các $b_{i,j} \in \{0;1\}$ . Với mỗi $0 \le x \le m^{m}-1$ , biểu diễn $mx$ theo cơ số $m$ và kết hợp với $(1)$ ta được $\displaystyle mx = \sum_{j=1}^{k}c_{j}a_{j},$ trong đó các $c_j$ là số nguyên thỏa mãn $0 \le c_j \le (m-1)m,\quad\forall j\in [k]$ . Vế trái của đẳng thức này nhận đúng $m^{m}$ giá trị, do đó $\displaystyle m^{m} \le [m(m-1)+1]^{k} < m^{2k},$ suy ra $|A|=k>m/2$ . $\Box$

Lời giải 2. Giả sử $|A| =k<m/2.$ Với mỗi $i\in [m],$ gọi $v_i=(v_{j,i})$ là phần tử của tập tích $\{ 0; 1 \}^k$ sao cho $v_{j,i} = 1$ nếu và chỉ nếu phần tử nhỏ nhất thứ $j$ của $A$ thuộc $B_i$ . Khi đó với mỗi $i\in [m]$ , tổng các phần tử của $B_i$ bằng tích vô hướng của $v_i$ và $a$ , với $a$ là bộ các phần tử của $A$ xếp theo thứ tự tăng. Theo bổ đề Siegel, tồn tại các số nguyên $a_i$ không đồng thời bằng không sao cho $a_1v_{j,1} +\cdots + a_m v_{j,m} = 0,\quad\forall j\in [k]\quad (2)$ và $|a_i| < m$ với mọi $i\in [m]$ . Từ $(2)$ ta có $a_1 m + a_2 m^2 +\cdots +a_m m^m = 0,$ điều này không thể xảy ra do tính chất của các $a_i$ . $\Box$