Let $n\ge 2$ be a positive integer. Find whether there exist $n$ pairwise nonintersecting nonempty subsets of $\{1, 2, 3, \ldots \}$ such that each positive integer can be expressed in a unique way as a sum of at most $n$ integers, all from different subsets.
Problem
Source: Baltic Way 2001
Tags: arithmetic sequence, combinatorics proposed, combinatorics
17.11.2010 23:20
WakeUp wrote: Let $n\ge 2$ be a positive integer. Find whether there exist $n$ pairwise nonintersecting nonempty subsets of $\{1, 2, 3, \ldots \}$ such that each positive integer can be expressed in a unique way as a sum of at most $n$ integers, all from different subsets. At most n integers? So I could pick for example the congruence classes mod n and put every odd integer $2n+1=n+(n+1)$ and every even integer$2n+2=n+(n+2)$ for $n>0$ and forget about 1 and 2, wich can't be put as a sum of positive integers (I assume a sum has two summands)? Since $n\geq 2$ and $n$,$n+1$ and $n+2$ are different mod n for $n>2$, and for $n=2$ it is easy Perhaps you mean exactly n integers? Please clarify...
18.11.2010 01:02
jestrada wrote: WakeUp wrote: Let $n\ge 2$ be a positive integer. Find whether there exist $n$ pairwise nonintersecting nonempty subsets of $\{1, 2, 3, \ldots \}$ such that each positive integer can be expressed in a unique way as a sum of at most $n$ integers, all from different subsets. At most n integers? So I could pick for example the congruence classes mod n and put every odd integer $2n+1=n+(n+1)$ and every even integer$2n+2=n+(n+2)$ for $n>0$ and forget about 1 and 2, wich can't be put as a sum of positive integers (I assume a sum has two summands)? Since $n\geq 2$ and $n$,$n+1$ and $n+2$ are different mod n for $n>2$, and for $n=2$ it is easy Perhaps you mean exactly n integers? Please clarify... I don't understand what you mean. Anyway, it says "can be expressed in a unique way" I would suggest the following: take $S_i=\{2^{i-1}\}$ for $i=1,...,n-1$ and $S_n=\{k2^{n-1},k=0,1,...\}$. e.g. for $n=4$ $\{1\}$ $\{2\}$ $\{4\}$ $\{8,16,24,32,...\}$ Now an interesting question would be if there are solutions with more than one of the sets infinite. It should be possible to show that a suitable infinite set must contain an arithmetic progression (and then of course the sums wouldn't be always in a unique way, so the answer would be no). but maybe not that easy.
13.11.2011 07:41
the following example satisfies the conditions: $n$ is in the jth class,if and only if $n=\sum 2^{a_i}$(binary representation),where all $a_i\equiv j(modn)$.
13.11.2011 19:20
Very nice construction! Those classes are not only infinite, but self-similar and they don't even contain arithmetic progressions of length $3$.