Let $S$ denote the set of rational numbers in the interval $(0,1)$. Determine, with proof, if there exists a subset $T$ of $S$ such that every element in $S$ can be uniquely written as the sum of finitely many distinct elements in $T$.
Problem
Source: MOP 2006 Homework - Black Group
Tags: induction, algebra solved, algebra
27.04.2014 23:42
i think \[T=\{\frac{r}{p^k} : p \text{ prime },k \in \Bbb{Z}_+, r \in \{0,1,...,p-1\} \}\] works. The proof should be just like the partial fraction decomposition.
28.04.2014 08:10
It says "uniquely". You have $\frac{1}{3}=\frac{1}{9}+\frac{2}{9}$.
25.06.2014 12:29
The answer is no. Proof. Assume the opposite, such subset $T$ exists. Lemma 1 If $x, y \in T$ and $x<y$, then $x \le \frac y 2$. Proof. Assume that $\frac y 2 < x$. Let $z=y-x$. Then $z <\frac y 2 < x$. $z$ can be written as the sum $z=t_1+\dots+t_n$ of distinct elements from $T$ ($n$ may equal to $1$ if $z \in T$). Clearly, all $t_i$ are less then $x$. So $y=t_1+\dots+t_n+x$ is another representation of $y$, different from $y=y$, that is not allowed. Lemma 2 If $x \in T$, then there are no numbers from $T$ in the interval $\left(\frac x 2, 2x \right)$ except $x$. Proof. Directly from lemma 1. Lemma 3 $T$ is in fact the infinite sequence $t_1, t_2, t_3, \dots$ where $t_n \le \frac {t_{n-1}} 2$. Proof. Write $T$ as $T=\bigcup_{n=1}^{\infty} T_n$ where $T_n=T \bigcap \left[\frac 1 {2^n}, \frac 1 {2^{n-1}}\right)$. Lemma 2 implies that each $T_n$ cannot contain more than one element. So, writing out elements of those $T_n$ that are not empty in corresponding order and applying lemma 1, we obtain the required sequence and inequality. Clearly, the sequence is infinite, or elements in $S$ less than the last element of the sequence cannot be written as a sum of elements from $T$. Now consider two cases. Case 1. $t_n = \frac {t_{n-1}} 2$ for all $n$. We have digits of ordinary binary system multiplied by $t_1$. So the number $\frac {t_1} 3$ cannot be written as a finite sum of elements in $T$. Case 2. $t_n < \frac {t_{n-1}} 2$ for some $n$. Let $r$ be a rational number from $(2t_n,t_{n-1})$. Assume that \begin{eqnarray} r=t_{i_1}+t_{i_2}+\dots+t_{i_m} \end{eqnarray} where $i_1>i_2>\dots>i_m$ and, therefore, $t_{i_{k-1}} \le \frac {t_{i_k}} 2$ for every $k=2,\dots, m$. It is easy to prove by induction that the sum of first $k$ terms in RHS of $(1)$ is less than $2t_{i_k}$. Therefore, the whole sum $(1)$ is less than $2t_{i_m}$. But $r<t_{n-1}$, so $t_{i_m} \le t_n$ and $2t_{i_m} \le 2t_n<r$ that contradicts $(1)$. $\blacksquare$