Olympiad Maths Prep

Track / Stage 5 / 379 of 400 #979 of 2000

Problem 979

AIME late
Number theory Difficulty 5.9 Prove it

7. (美国数学奥林匹克)确定(并证明)是否有整数集的子集 XX 具有下面的性质: 对任意整数 nn, 恰有一组 a,bXa, b \in X, 使 a+2b=na+2 b=n.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

7. 解 这样的存在. 首先令 X2={0,1}X_{2}=\{0,1\}. 假设已有 Xk={a1,a2,,ak}X_{k}=\left\{a_{1}, a_{2}, \cdots, a_{k}\right\}, 使得 ai+2aja_{i}+2 a_{j} (1i,jk)(1 \leqslant i, j \leqslant k) 互不相同.
Sk={ai+2aj(1i,jk)}S_{k}=\left\{a_{i}+2 a_{j}(1 \leqslant i, j \leqslant k)\right\}. 对任一不属于 SkS_{k} 的整数 nn, 取正整数 ak+1a_{k+1},
又令 ak+2=2ak+1+na_{k+2}=2 a_{k+1}+n.
只要 ak+1a_{k+1} 充分大, 对 1i,j,s,tk1 \leqslant i, j, s, t \leqslant k, 有
3ak+1>as+2ak+1>ak+1+2ai>nak+2+2aj>ak+1+2ak+2>at+2ak+2>3ak+2 3 a_{k+1}>a_{s}+2 a_{k+1}>a_{k+1}+2 a_{i}>n a_{k+2}+2 a_{j}>a_{k+1}+2 a_{k+2}>a_{t}+2 a_{k+2}>3 a_{k+2} \text {, }

而且 ak+1+2aia_{k+1}+2 a_{i} 大于 SkS_{k} 中一切正数, ak+2+2aja_{k+2}+2 a_{j} 小于 SkS_{k} 中一切负数.
于是, 对 Xk+2={ak+1,ak+2}XkX_{k+2}=\left\{a_{k+1}, a_{k+2}\right\} \cup X_{k} 中任二数 ab,(a+2b)a 、 b,(a+2 b) 互不相同.
X=X2X4X2kX2k+2X=X_{2} \cup X_{4} \cup \cdots \cup X_{2 k} \cup X_{2 k+2} \cup \cdots
XX 满足要求.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.