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'm trying to find a partition of natural number N whereby

  1. we can generate a partition for all natural numbers less than N from the partition elements.
  2. The number of elements in the partition should be as small as possible.

For example, if N is 8, I believe the partition is {1,2,4,1} since I can form a partition for all natural numbers less than 8 from the elements like the below.

1 = 1, 2 = 2, 3 = 1+2, 4 = 4, 5 = 1+4, 6 = 2+4, 7 = 1+2+4

I simply put the power of 2s (ex {1,2,4}) until the sum of them are less than or equal to N. Then, put the remainder(ex {1}) to make sum of all elements equal to N. I'd like to know if this method is the right approach to get a partition with the smallest number of elements. Is there any theorem related to it? It would be great if anyone can help me to prove whether my method is right or wrong. Thanks!

share|improve this question

1 Answer 1

up vote 4 down vote accepted

This does yield the smallest size partition (though there might be other partitions of this size that do the job - but yours definitely works). Notice that the size of your partition is $\lceil \log_2(N+1) \rceil$ (as you can check); we can show that no smaller partition will work.

Suppose that you have a partition with $k<\lceil \log_2(N+1) \rceil$ parts, so that $k < \log_2(N+1)$ in particular. The number of subsets of your partition is $2^k$, so even if they all had different sums, the total number of sums that can be achieved (as a sum of a subpartition) is at most $2^k < 2^{\log_2(N+1)} = N+1$; in other words, the total number of sums that could be achieved is at most $N$. But the two sums $0$ and $N$ are definitely achieved, so there must be some natural number between $1$ and $N-1$ that can't be achieved.

share|improve this answer

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.