A nonempty set $ A$ of real numbers is called a $ B_3$-set if the conditions $ a_1, a_2, a_3, a_4, a_5, a_6 \in A$ and $ a_1 + a_2 + a_3 = a_4 + a_5 + a_6$ imply that the sequences $ (a_1, a_2, a_3)$ and $ (a_4, a_5, a_6)$ are identical up to a permutation. Let $A = \{a_0 = 0 < a_1 < a_2 < \cdots \}$, $B = \{b_0 = 0 < b_1 < b_2 < \cdots \}$ be infinite sequences of real numbers with $ D(A) = D(B),$ where, for a set $ X$ of real numbers, $ D(X)$ denotes the difference set $ \{|x-y|\mid x, y \in X \}.$ Prove that if $ A$ is a $ B_3$-set, then $ A = B.$
Problem
Source: IMO Shortlist 2000, A6
Tags: algebra, number theory, Combinatorial Number Theory, Sequence, IMO Shortlist
Zhero
21.08.2010 00:10
Because $D(B) = D(A)$, we can find functions $f$ and $g$ such that $b(m) - b(i) = a(f(m,i)) - a(g(m,i))$ for all $m, i$ with $0 \leq i \leq m-1$ and $f(m,i) > g(m,i)$. We shall show that $a(f(m,i)) - b(m)$ is constant.
Let $m_1 ,i_1, m_2, i_2$ be any nonnegative integers with $m_1 \geq i_1 + 1$ and $m_2 \geq i_2 + 1$. For any $k > i_1$, we have that $(b(k) - b(i_1)) - (b(m_1) - b(i_1)) = a(p) - a(q)$ for some integers $p > q$. Let $s_k$ be a sequence of positive integers such that $b(k) - b(i_1) = a(s_k) - a(u)$ for some $u < s_k$. We also have $b(m_1) - b(i_1) = a(f(m_1,i)) - a(g(m_1,i))$.
Substituting these, we get that
$a(s_k) + a(g(m_1,i)) + a(q) = a(p) + a(f(m_1,i_1)) + a(u).$
If we take $k$ to be sufficiently large, we can force $s_k$ to grow sufficiently large as well (or else $b(k) - b(i_1)$ will be unbounded, while $a(s_k) - a(u)$ will be bounded, since $u < s_k$.) Hence, for sufficiently large $k$, $s_k > f(m_1, i_1)$. $s_k > u$, so since $A$ is $B_3$, we must have $s_k = p$. It follows that $f(m_1, i_1) = q$ and $u = g(m_1, i)$. Hence, we have $b(k) = a(s_k) + (b(m_1) - a(f(m_1, i_1))$ for all sufficiently large $k$. In a similar way, we can find a sequence $t_1, t_2, \ldots$, such that for all sufficiently large $k$, $b(k) = a(t_k) + (b(m_2) - a(f(m_2, i_2)))$. Subtracting, we see that $a(t_k) - a(s_k) = a(t_{k+1}) - a(s_{k+1})$ for all sufficiently large $k$.
Rearrange that to get $a(t_k) + a(s_{k+1}) + a(0) = a(0) + a(s_k) + a(s_{k+1})$. $s_k \neq s_{k+1}, 0$, so $s_k = t_k$. Hence, $0 = a(t_k) - a(s_k) = (b(m_1) - a(f(m_1, i_1))) - (b(m_2) - a(f(m_2, i_2)))$, so our claim is proven.
For $x > 0$, let $h(x) = f(x,0)$. Since $a(f(m,i)) - b(m)$ is constant and $a$ is increasing, $f(m,i)$ is independent of $i$, so $f(m,i) = h(m)$ for all $m \geq i \geq 0$. Because $a$ and $b$ are increasing functions, $h$ must be increasing as well in order for $a(h(m)) - b(m)$ to remain constant.
For any $n > 0$, we have $a(n) - a(0) = b(x) - b(y)$ for some integers $x,y$. We also have $b(x) - b(y) = a(h(x)) - a(g(x,y))$, so $a(g(x,y)) + a(n) = a(h(x)) + a(0)$. $n \neq 0$, so $h(x) = n$, so $h$ is surjective over the positive integers. Since $h$ is increasing and surjective over the positive integers, we must have $h(n) = n$ for all positive integers $n$, so $a(n) - b(n)$ is constant when $n \geq 1$.
It follows easily that $a(m) - a(n) = b(m) - b(n)$ whenever $m > n \geq 0$. For any $n \geq 0$, we have $a(n) - a(0) = b(x) - b(y) = a(x) - a(y)$ for some $x > y \geq 0$. $a(x) + a(0) + a(0) = a(n) + a(y) + a(0)$. $y \neq x$, so $y=0$ and $x = n$, whence $a(n) = b(n)$ for all $n$, as desired.
mathaddiction
01.10.2020 14:56
CLAIM 1. If $a_i+a_j=a_k+a_l$ then $\{i,j\}=\{k,l\}$ Proof. Otherwise take $p\neq i,j,k,l$ then $a_p+a_i+a_j=a_p+a_k+a_l$, but $\{p,i,j\}\neq \{p,k,l\}$, contradiction. $\blacksquare$ Hence each pair of integer $(i,j)$ with $i>j\geq 0$ unique determine an element in $D(A)$. $\noindent\rule{15cm}{0.2pt}$ Now for some $i>j>0$ let \begin{align*} b_j&=a_{x_1}-a_{x_2}\\ b_i-b_j&=a_{x_3}-a_{x_4}\\ b_i&=a_{x_5}-a_{x_6}\\ \end{align*}Then $a_{x_1}+a_{x_3}+a_{x_6}=a_{x_2}+a_{x_4}+a_{x_5}$ Now $x_1\neq x_2$. If $x_1=x_4$ then $a_{x_3}+a_{x_6}=a_{x_2}+a_{x_5}$. From CLAIM 1 we have $\{x_3,x_6\}=\{x_2,x_5\}$. Since $x_5\neq x_6$, we have $x_5=x_3$ and $x_2=x_6$. Hence \begin{align*} b_j&=a_x-a_y\\ b_i-b_j&=a_z-a_x \qquad(1)\\ b_j&=a_z-a_y\\ \end{align*}for some $z>x>y$. Similarly if $x_1=x_5$ we have \begin{align*} b_j&=a_x-a_y\\ b_i-b_j&=a_y-a_z \qquad (2)\\ b_i&=a_x-a_z\\ \end{align*}for some $x>y>z$. $\noindent\rule{15cm}{0.2pt}$ Now if $(i,j)$ satisfies $(1)$ we will call it good and bad if it satisfies $(2)$. CLAIM 2. $(i,1)$ is good for all $i>1$. Proof. Let $b_i=a_x-a_y$ for some $x,y$. Firstly if there exists $j,k$ such that $(j,1)$ is good while $(k,1)$ is bad, then $b_j=a_p-a_y$ for some $p$ while $b_k=a_x-a_q$ for some $q$. Now from $(1),(2)$ that $q\neq y$ and $p\neq x$, hence $(j,k)$ is neither good or bad, contradiction. Now if all $i>1$ is bad then $b_j=a_x-a_z<a_x$, hence $B$ is bounded, contradiction. $\blacksquare$ $\noindent\rule{15cm}{0.4pt}$ Now for all $i.1$ let $b_i=a_{f(i)}-a_y$. Now we can compute all the elements in $D(B)$, indeed we have $$b_i-b_j=a_{f(i)}-a_{f(j)}$$where $f(1)=x$ and $f(0)=y$. Since $f$ is strictly increasing, and that it is surjective, we must have $f(i)=i$, hence $a_i=b_i$ as desired.