Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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<N_k<(k+1)s_1$. 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.

share|improve this answer
    
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. –  042 Nov 4 '12 at 12:43
    
@042: let me read your updated version first. –  23rd Nov 4 '12 at 12:46
    
OK, that comment was related to your original answer, now I am trying out to understand the new answer. –  042 Nov 4 '12 at 12:48
    
... it has the same problem –  042 Nov 4 '12 at 12:49
    
@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. –  23rd Nov 4 '12 at 12:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.