Tổ hợp & Số học

Khẳng định. Mọi $a_k$ trong $S$ đều có $a_k \equiv a_1 \pmod{4}$.

Chứng minh bằng quy nạp theo $k$.

Cơ sở $k = 1$: hiển nhiên.

Bước quy nạp: Giả sử $a_l \equiv a_1 \pmod{4}$ cho mọi $l < k$. Theo điều kiện (ii), $a_k = a_i + 4 a_j$ với $i, j < k$. Do đó $a_k \equiv a_i \equiv a_1 \pmod{4}$. $\blacksquare$

Bước 1. Vì mọi $a_k$ chia hết cho $4$, đặt $a_k = 4 b_k$. Khi đó $b_1 < b_2 < \ldots < b_n = 500$ và $b_k = b_i + 4 b_j$ — cùng dạng quy luật.

Bước 2. Áp dụng bổ đề mod 4 cho $(b_k)$: $b_k \equiv b_1 \pmod 4$ với mọi $k$. Mà $b_n = 500 \equiv 0 \pmod 4$, nên mọi $b_k$ chia hết cho $4$.

Đặt $b_k = 4 c_k$ thì $c_1 < c_2 < \ldots < c_n = 125$ và $c_k = c_i + 4 c_j$.

Bước 3. Áp dụng bổ đề lần ba cho $(c_k)$: $c_k \equiv c_1 \pmod 4$ với mọi $k$. Mà $c_n = 125 \equiv 1 \pmod 4$, nên $c_1 \equiv 1 \pmod 4$, và mọi $c_k \equiv 1 \pmod 4$.

Xét $c_k = 4 k - 3$ với $k = 1,\,2,\,\ldots,\,32$ (tức $1,\,5,\,9,\,\ldots,\,125$).

Kiểm tra điều kiện (ii): với $k \ge 2$, chọn $i = k - 1$, $j = 1$. Khi đó $$c_i + 4 c_j = (4(k-1) - 3) + 4 \cdot 1 = 4k - 3 = c_k. ✓$$

Quay ngược về $a$: $a_k = 16\, c_k = 16(4k - 3)$. Cụ thể $a_1 = 16,\ a_2 = 80,\ a_3 = 144,\ \ldots,\ a_{32} = 16 \cdot 125 = 2000.$

Tất cả điều kiện (i), (ii) đều thỏa: $a_k = a_{k-1} + 4 a_1 = 16(4k - 7) + 16 \cdot 4 = 16(4k - 3) = a_k$. ✓