Let $t(A)$ denote the sum of elements of a nonempty set $A$ of integers, and define $t(\emptyset)=0$. Find a set $X$ of positive integers such that for every integers $k$ there is a unique ordered pair of disjoint subsets $(A_{k},B_{k})$ of $X$ such that $t(A_{k})-t(B_{k}) = k$.
Problem
Source: Turkish Mathematical Olympiad 2nd Round 1995
Tags: induction, combinatorics unsolved, combinatorics
02.10.2006 05:44
The set $X$ is the set of the powers of $3$. Let's prove by induction that this set satisfies the conditions required. I'll let the base of induction to the end of the proof. Suppose that we have done for each positive integer less than or equal to $\frac{3^{m}-1}{2}$ for some $m$ positive integer. Let $k$ be a positive integer such that $\frac{3^{m}-1}{2}< k \leq 3^{m}$. If $l =3^{m}-k$ then there exists $(A_{l}, B_{l})$ such that $t(A_{l})-t(B_{l}) = l$, for $l \leq \frac{3^{m}-1}{2}$. Then let $A_{k}= (B_{l})U(3^{m})$ and $B_{k}= A_{l}$. So $t(A_{k})-t(B_{k}) = k$. Suppose that there exist others sets $C_{k}$ and $D_{k}$ such that $t(C_{k})-t(D_{k}) = k$. Then now it's suficient to prove that $3^{m}$ belongs to $C_{k}$. But $t(C_{k}) \geq k > \frac{3^{m}-1}{2}> 3^{m-1}$, so there will exist a power of $3$ greater than $3^{m}$ on $C_{k}$. It's easy to see that $t(D_{k}) \leq \frac{3^{m}-1}{2}$, so $k \geq 3^{m+1}-\frac{3^{m}-1}{2}> 3^{m}$, contradiction. Then $3^{m}$ belongs to $C_{k}$, and $t(D_{k})-t(C_{k}-3^{m}) = 3^{m}-k = l$ which implies $A_{l}= B_{k}$ and $B_{l}= C_{k}-3^{m}$. So $A_{k}= C_{k}$ and $B_{k}= D_{k}$. So to each positive integer less than or equal to $3^{m}$ we have done. But if $n$ is such that $3^{m}< n \leq 3^{m}+\frac{3^{m}-1}{2}= \frac{3^{m+1}-1}{2}$, then call $l = n-3^{m}$, and by the uniqueness of $A_{l}$ and $B_{l}$ we may find unique $A_{n}$ and $B_{n}$, following the same steps of the last proof. And the induction is done. Base of induction: For $k = 1$, $A_{1}= [1]$ and $B_{1}= [0]$. For $A_{2}= [3]$ and $B_{2}= [1]$. PS: I know that I didn't complete this proof, but with a little bit of comprehension you would understand that I would repeat the first proof.
06.02.2018 15:49
If for finding only one set $X$, the set of powers of 3 clearly works (just consider digits of $k$ in base 3). The more challenging question is to find all such set $X$.