1
$\begingroup$

I have come over the following problem in elementary number theory: suppose that a positive integer $k$ is given. Is it possible to find, for every such $k$, a nonnegative integer $N(k)$ and a set of nonnegative integers $S(k) = \{s_1,\ldots,s_k\}$ of cardinality $k$, such that $N(k) = s_1 + \ldots + s_k$ and such that this is a unique partition of $N(k)$ with parts taken from $S(k)$ (that is there is not any other partition of $N(k)$ with parts taken from $S(k)$)? For instance, for $k = 3$, one may choose $N(3)= 3004$ and $S(3) = \{1000,1001,1003\}$. However, one may not choose $N(3) = 3003$ and $S(3) = \{1000,1001,1002\}$, since $1001 + 1001 + 1001 = 3003$. Or, one cannot choose $N(2) = 3$ and $S(2) = \{1,2\}$, since $3 = 1 + 1 + 1$.

I suspect that this should be possible to do for general $k$, however I have failed to characterize $N(k)$ and $S(k)$ in general.

My apologies if this problem is trivial.

1 Answers 1

2

Given $k\ge 1$, a more or less trivial construction is as follows. Let $s_i=(k+1)!+i!$, $i=1,\dots,k$. Let $N(k)=\sum_{i=1}^k s_i$ and $S(k)=\{s_i:1\le i\le k\}$. Note that $\sum_{i=1}^k i!<(k+1)!$, so $(k-1)s_k. Now let $N(k)=a_1+a_2+\dots+a_n$ be a partition, where $a_i\in S(k)$, $1\le i\le n$. Then from $ns_1\le N(k)\le ns_k$ we can conclude $k=n$. Now let $M(k)=N(k)-k(k+1)!$ and $b_i=a_i-(k+1)!$. From $M(k)=\sum_{i=1}^k i!=\sum_{i=1}^k b_i$ and $b_i\in\{i!:1\le i\le k\}$, the uniqueness of partition is easy to see.

  • 0
    @042: That is because I edited the answer before noticing your update of the question. The problem is easy to fix. Give me a few minutes for editing.2012-11-04