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
    I am afraid that this does not work, since $N(k) = \underbrace{1+\ldots+1}_{N(k)}$. I am sorry, I have not sufficiently emphasized that the partition has to be unique not only among all $k$-partitions, but among all partitions (and I admit that the name of the question may be misleading as well). I have edited the question.2012-11-04
  • 0
    @042: let me read your updated version first.2012-11-04
  • 0
    OK, that comment was related to your original answer, now I am trying out to understand the new answer.2012-11-04
  • 0
    ... it has the same problem2012-11-04
  • 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