3
$\begingroup$

The series which forms the basis of all the other series is:- $1,2,4,8,16,18$. Some other combinations are:- $1,2,3,7,14,22 ; 1,2,4,7,15,20 ; 1,2,4,8,13,21$. However, I obtained the basic combination by the following method:-

Step 1:- You definitely need "1".

Step 2:- You need two and also 3. So, the next numbers is 2.

Step 3:- Now you have $1,24$. So, the next numbers is 4.

Step 4:- Now you have $1,2,4$. So, the next numbers is 8

Step 5:- Now you have $1,2,4,8$. So, the next numbers is 16

Step 6:- Now you have $1,2,4,8,16$. So, the next numbers is 18 So the series is $1,2,4,8,16,18$.

My Question:- I don't know how to prove that there are more ( or exactly these many ) rigorously ( and why ). Any help would be appreciated.

$\endgroup$
1
  • $\begingroup$ How exactly do we "obtain any number between 1 and 49?" Is it by adding together various elements of our set? If so, then your question is probably related to this concept: en.wikipedia.org/wiki/Golomb_ruler $\endgroup$
    – Ryan
    Dec 17, 2012 at 2:17

1 Answer 1

Reset to default
2
$\begingroup$

In step 3, you could also select $3$, as you have in one of your examples. Your approach shows that with $n$ numbers we can add up to $2^n-1$ and to do so we want to select the powers of $2$. When the upper limit is not one less than a power of $2$ you have more flexibility. As you have seen, you can lower the top one from $32$ to $18$ and still reach $49$. There are certainly other possibilities: One of them is $1,2,4,8,12,22$

Basically your constraints are: the six numbers must sum to at least $49,$ each one must be less than or equal to one more than the sum of the previous numbers. A little thought and an inductive proof should convince you these are the only constraints. I don't know how to count the number of possibilities easily.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .