How many numbers can you create?

Number Theory Level 4

The majestic Calvin Set is denoted as $C$ where

$C = \{0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024\}$

Lin takes at least two elements of $C$ and adds them.

How many numbers can Lin create?

The answer is 2047.

3 solutions

Alan Yan
Aug 26, 2015

Hmmmmmmm....... I wonder if there is something I could do to the set so I don't need to add every combination and count the number of sums.....

Wait! All of the elements are powers of two! Let me try to put it in binary.

$\{ 0_2, 1_2, 10_2, 100_2, 1000_2, ..., 100000000_2, 1000000000_2, 10000000000_2\}$

From here it is easy to see that I can create every number less than

$100000000000_2 = 2048$ by adding the elements corresponding to the base 2 representation.

Therefore there are $\boxed{2047}$ numbers.

The key was that you included $0$ in $C$ even though it is not actually a power of $2$ itself. This preserved all the powers of $2$ as being part of the solution set, for otherwise if $0$ were not present then the elements of $C' = C - \{0\}$ themselves could not be be expressed as a sum of two or more elements of $C'.$

Brian Charlesworth - 5 years, 9 months ago

عبدالرحمن زكريا
Sep 2, 2015

answer is very simple if you considered it as a binary system so you can create any number between 0 up to 1024 x 2 with this set of numbers

every number in the set is less than the sum of the previous numbers by 1.

so the answer is 1024 x 2 - 1 = 2047

A short video about binary system

Mauli Kundlia
Aug 26, 2015

(2^11) - 1 There is a total of 12 numbers, however one of them is 0. Adding zero will not change the answer therefore we exclude it. However, when we take 0 and another number, we get the number itself. Therefore the problem can be reduced to finding, the sum of, the number of ways of selecting 1 number, 2 numbers, 3 numbers......,11 numbers out of 11 numbers provided to us to get distinct sums of these numbers. 11C1 + 11C2 + ...........+11C11 = (2^11)-1 = 2047

You still haven't proven that all of these sums are distinct. With a slight change to the problem, this method could lead to an incorrect answer.

Alan Yan - 5 years, 9 months ago

Of course that would be a problem if we had just any sequence, but the numbers given here are all in the powers of 2, as you can see just by observation, no number in the entire sequence can be obtained by the sum of all the smaller numbers before it, and you are not allowed to repeat any number. This will give us distinct sums. Lets take an example, had the numbers been 1,2,3,4, 1+2+3 = 6, and also 2+4 = 6, this is because, the sum of 1 and 3 can be replaced by the number 4, which is not a case in the given sequence. Another case is that 2+3=5, also 1+4=5, however that is because, the sum of two small numbers 2 and 3 exceeds 4, therefore there was a probability of another number existing which when added to 4 gives the same number, but it is not the case in the given sequence.

Mauli Kundlia - 5 years, 9 months ago

Good, now you just need to add it to your proof ;)

Alan Yan - 5 years, 9 months ago

@Alan Yan – Lets just leave it at that :P I am too tired to edit the comment. By the way, glad you pointed it out. :)

Mauli Kundlia - 5 years, 9 months ago

How many numbers can you create?

The answer is 2047.

3 solutions

0 pending reports