Not Twice

Probability Level 2

Charlotte selected a subset out of the integers from 1 through 20 inclusive. None of the numbers in the subset is double another number in the subset.

What is the greatest number of integers she could have selected?

10 11 12 13 14 15

14 solutions

Marta Reece
May 19, 2018

The table on the left summarizes all the "times two" relationships.

The first line is $1$ "times two" is $2$ , then this "times two" is $4$ etc.

Similarly for all the other lines, each line starting with the lowest number not yet listed so that all numbers from 1 to 20 are included and none of them are repeated.

If a line contains only one number, that number should be included in the set.

If a line contains two numbers, either one may of them be included. We may as well pick the odd one, but that is just an arbitrary pick.

If a line contains three numbers, the first and last should be included. Neighbors in the same line are related "times two" and can't both be picked. (Including the middle one instead would result in fewer numbers as neither of the ends could be included.)

If a line contains five numbers, taking the first, middle, and last is the best option.

Following this procedure, only the red ones end up selected and there are $\boxed{14}$ of them.

Relating your solution to Calvin's comment below,

If a line contains an even number of numbers, than we can take either alternating sequence. This gives us all of the flexibility that there is.

A nice result is that the number of "maximal sets" for integers from 1 to n, is always a power of 2!

Chung Kevin - 3 years ago

"Charlotte selected a set of integers from 1 through 20."

This wording as it stands would seem to indicate that she took all the numbers from 1 to 20. While the text after that clarifies this, it would be preferable, in my opinion, to start with:

"Charlotte picked a subset out of integers from 1 to 20."

This way the situation is clear from the start.

Marta Reece - 3 years ago

Damn, I forgot to count 20.

Kunal Kantaria - 3 years ago

The question should have said exactly double.

Adam Polansky - 3 years ago

What other interpretation is there? As mathematicians, we do not say that "9 is double of 5".

Chung Kevin - 3 years ago

Can you explain to me how you can include 4 if it double 2?

Jim Allen - 3 years ago

By not including 2.

Marta Reece - 3 years ago

I see. Thank you.

Jim Allen - 3 years ago

I wrote a chess database progam once that would let me add a large number of games and toss them into a binary tree. The LEFT branch was NEXT and the RIGHT branch was ALTERNATIVE. The program would descend through the existing game tree until it encountered a move not already in the tree and add it. With a large number of games, lots of cells have both NEXT and ALTERNATIVE branches, making it nearly impossible to draw even small parts of the tree. The idea was to let me pick through a huge tree and look at only the lines I was interested in.

So my first take was to have each number add to a tree where LEFT is NOT-DOUBLE and RIGHT was DOUBLE. I generated exactly Ms Reece's solution. Because the odds add only to the leftmost node you can actually write this binary tree down!

Bill Weihmiller - 3 years ago

2 is double 1

edwin hoffman - 3 years ago

Which is why it is not selected. Only the red ones are the selected ones, the black ones are not.

Marta Reece - 3 years ago

Not sure If I understand any of the math. But I got the right answer by writing up a lua program to solve it. Took about 5 mins. Just hit execute and there it is, the working set of numbers and the number of integers used. http://tpcg.io/vrbuDu

KHJ Games - 3 years ago

I am non a native English person, so the word "double" have led me into delusion. I would be better to use "cannot be divided by 2", because of I was thinking, that the number could not be reused.

Grigoriy Yuschenko - 2 years, 9 months ago

Arjen Vreugdenhil
May 19, 2018

General solution for integers $1, \dots, N$ :

Consider the binary representation $N = \overline{\dots b_4 b_3 b_2 b_1 b_0}_2$ . Calculate the alternating digit sum $a_N$ as follows: $a_N = b_0 - b_1 + b_2 - b_3 + b_4 -+ \cdots.$

The maximum value required in this problem is then $m_N = \frac{2N + a_N}3.$

In the case $N = 20 = 10100_2$ we have $a_{20} = 0 - 0 + 1 - 0 + 1 = 2$ , and $m_{20} = \frac{2\cdot 20 + 2}3 = \boxed{14}.$

Challenge : Proving the general formula is not easy! Any takers?

That's surprising to have such a nice formula.

Marta's solution is how I approached it, but I don't know how to count the red numbers in the general case.

Chung Kevin - 3 years ago

Believe it or not, but my formula started with Marta's approach. Then I went to work counting the red numbers.

Hint: The red numbers are precisely those whose binary representation ends in an odd number of zeroes.

Arjen Vreugdenhil - 3 years ago

Proof by induction on the binary digits of $N$ :

Every positive integer $x$ may be written uniquely as $x = 2^io$ with $o$ odd and $i \geq 0$ . As in Marta's solution, we call a number "red" if $i$ is even and "black" if $i$ is odd. The solution to the problem is the number of red numbers in the given range $1, \dots, N$ .

Dividing a number by two changes its color, from red to black and from black to red.

Now suppose that $N = 2n + b_0$ , where $b_0 = 0$ or $1$ . To count $R_N$ , the red numbers between $1, \dots, N$ , we start with all the numbers and remove all the black numbers. But these black numbers are precisely double all red numbers in the range $1, \dots, n$ . Therefore we find the recursion relation $R_N = N - R_n.$

We are now ready to prove $R_N = \tfrac13(2N + a_N)$ by induction.

Base step : If $N = 0$ , then $R_N = a_N = 0$ . The equation is clearly satisfied.

Induction step : Let $N = 2n + b_0$ ; then $a_N = b_0 - a_n$ , and suppose that $R_n = \tfrac13(2n + a_n)$ . Then $\begin{aligned} R_N & = N - R_n \\ & = N - \tfrac13(2n + a_n) \\ & = N - \tfrac13(2n + b_0 - a_N) \\ & = N - \tfrac13N + \tfrac13 a_N \\ & = \tfrac13(2N + a_N) \end{aligned}$

Since all integers $N$ can be generated from $N = 0$ in a finite number of such steps, we have proven the statement for all integers $N$ . $\square$

Arjen Vreugdenhil - 3 years ago

That's very clever! The general equation I came up with was a little more complicated:

$m_N = \sum_{k=0}^{\lfloor \log_4 N \rfloor} \left \lfloor \frac{N + 4^k}{2 \cdot 4^k} \right \rfloor$

Each term $\left \lfloor \frac{N + 4^k}{2 \cdot 4^k} \right \rfloor$ gives the number of red numbers in the $(k + 1)^{\text{th}}$ red-numbered column in Marta's solution, and there are $\lfloor \log_4 N \rfloor + 1$ red-numbered columns.

David Vreken - 3 years ago

My initial solution took that direction. Then I realized that the sum was approximately $\sum_{k=0}^\infty \frac N{2\cdot 4^k} = \frac{2N}3.$ Then I investigated the differences between $2N$ and $3m_N$ , and realized that it was related to the binary digits.

What really helped me was sequences like $m_{10} = 6$ , $m_{20} = 14$ , $m_{40} = 26$ , $m_{80} = 54$ . In each case, $m_N$ is nearly two-thirds of $N$ ; but alternatingly the number is rounded op and down. But no such discrepancy arose with $m_3 = 2$ , $m_6 = 4$ , and so on. At first I thought multiples of 3 should always give $m_N = \tfrac23N$ , but that broke down with $m_{21} = 15$ , $m_{42} = 27$ , $m_{84} = 57$ , where $m_N = \tfrac23N \pm 1$ .

Arjen Vreugdenhil - 3 years ago

Little mistake: "As in Marta's solution, we call a number "black" if $i$ is even and "red" if $i$ is odd".

Marta colored her numbers in the opposite way. By the way, could you explain or at least give me a hint on how you came up with this formula in the first place?

Uros Stojkovic - 3 years ago

For your question: see may reply to David Vreken in this thread.

You are right about the colors. I will swap them.

Arjen Vreugdenhil - 3 years ago

Hi, Can you derive the same proof without induction ?

senthil kumar - 3 years ago

Proving the formula without induction may be more difficult... If you have a suggestion, I'd be happy to hear it!

Arjen Vreugdenhil - 3 years ago

@Arjen Vreugdenhil – I have difficulty understanding the part "suppose that Rn = 1/3(2n + an)". On what basis this is taken as an assumption ?

senthil kumar - 3 years ago

@Senthil Kumar – That's the formula which Arjen proves. To check if it's generally true, he supposes that it's true for some $n$ and then proves that it must be also true for $N = 2n + b_{0}$ .

Uros Stojkovic - 3 years ago

@Uros Stojkovic – I understand why it seems to be coming out of the blue. This is often the case with induction proofs: it's not always clear how the author "invented" an equation. Proving that it works is one thing; figuring out what works is different.

My inspiration for this formula came from calculating $R_n$ for the simplest case, $n = 2^k$ . In that case, $R_n = 2^k - 2^{k-1} + 2^{k-2} - + \cdots \pm 1 = \frac{2^{k+1}\pm 1}3 = \frac{2n\pm 1}3.$ This gave me the idea of writing $R_n = \frac{2n + a_n}3,\ \ \ \ a_n = 3R_n - 2n$ and seeing how $a_n$ behaves. I quickly discovered that when $N = 2n+b$ , $a_N = 3R_N - 2N = 3(N - R_n) - 2N = N - 3R_n = 2n + b - 3R_n = b - (3R_n - 2n) = b - a_n.$ Thinking about binary digits, this shows that $a_N = b_0 - a_n = b_0 - (b_1 - \cdots) = b_0 - b_1 + b_2 - + \cdots$ Thus I found a useful definition of $a_n$ and a valid equation for $R_n$ ; in a way, the proof by induction is "working backward", but as a proof it is more elegant.

Arjen Vreugdenhil - 3 years ago

@Arjen Vreugdenhil – Now everything makes sense! I see how you brought in binary digits and alternating sum - it's an upgrade of the simplest case! Awesome!

Btw I see you turned 41 recently, happy birthday!

Uros Stojkovic - 3 years ago

I don't get it. All these numbers confuses me?

Batuhan Gokmen - 3 years ago

Same here, lol

Kryogenik X - 3 years ago

Marta's solution is easier to understand. Generalizations are always more challenging and require more mathematics. It pays off when you work with bigger values. For instance, if the number $20$ were replaced by $2222$ , Marta's method would make you write down long lists, while I would immediately calculate $2222 = 1000\,1010\,1110_2 \\ a_{2222} = -1 + 1 - 1 - 1 - 1 - 1 = -4 \\ m_{2222} = \frac{2\cdot 2222-4}3 = 1480.$

Arjen Vreugdenhil - 3 years ago

What does the subscript 2 mean next to the binary representation N? I figured it was a mistake but you wrote it again in the example case next to 10100.

Yonatan Beer - 3 years ago

It indicates that the number is in binary notation.

Matt Shisler - 3 years ago

Also, this proof clearly works, but do you have a proof for why it does? How did you arrive at this formula in the first place?

Yonatan Beer - 3 years ago

First, I considered that for $N = 2^k$ , $m_N = 2^k - 2^{k-1} + 2^{k-2} - \cdots + 1 = \frac{2^{k+1} \pm 1}{3} = \frac{2N \pm 1}3.$ That gave me the idea of stipulation $m_N = \frac{2N + a_N}3$ and figuring a formula for $a_N$ . Now if $N = 2n + b$ then $a_N = 3m_N - 2N = 3(N - m_n) - 2N = N - 3m_n = 2n + b - 3m_n = b - (3m_n - 2n) = b - a_n.$

Arjen Vreugdenhil - 3 years ago

In the first step, why does 2^k-2^k-1+2^k-2...+2^k-k = (2^k+-1)/3. Why divide by three, how did we get 2^k+1, why are we doing this alternating pattern in the first place? I get that it's (all of the numbers)-(the even numbers)+(every fourth even number)-(every eighth even number) but if i'm wrong, what's the reason for the alternating negation? why are we doing +- 1 one line one but +aN on line two, and how did you replace 1 with aN?

Hate to bombard you with questions but you seem to be assuming that some things will lead you to your answer when i don't see why they would.

Yonatan Beer - 3 years ago

@Yonatan Beer – There is a well-known expression for a geometric series: $1 + x + x^2 + x^3 + x^4 + \cdots + x^n = \frac{x^{n+1} - 1}{x - 1}.$ Now let $x = -2$ and $n = k$ . This will give you $1 - 2 + 4 - 8 + - \cdots + (-2)^k = \frac{(-2)^{k+1} + 1}{(-2) - 1} = \frac{(-)^k 2^{k+1} - 1}3.$ Multiply by $(-)^k$ ; then $\pm 1 \mp 2 \pm \mp \cdot + 2^k = \frac{2^{k+1} \mp 1}3,$ as advertized.

When I had found $m_N = (2N \pm 1)/3$ for the specific case $N = 2^k$ , I thought it might be useful to write the general solution as $m_N = (2N + a_N)/3$ . This does not really solve anything; it merely creates a new problem, namely to find an equation for $a_N$ . I already knew that $a_N = (-1)^k$ for $N = 2^k$ , but what is it for other values of $N$ ? The recurrence relation $m_N = N - m_n$ was sufficient to derive the general equation for $a_n$ , thereby also solving the original problem.

Arjen Vreugdenhil - 3 years ago

Chandrashekar Giridharan
May 15, 2018

To maximise the number of integers picked, we first pick all the odd integers(since twice of no number will be equal to them). Thus we have already picked 10 odd integers.

From the remaining integers 2,4,6,8,10,12,14,16,18,20 we can’t choose 2,6,10,14,18 as they are twice the odd integers that we have already picked. From the remaining even integers, we can maximise the number of integers chosen by taking 4,12,16 and 20.

Thus, finally we have the maximum 14 chosen integers- 1,3,4,5,7,9,11,12,13,15,16,17,19,20

Click here for a similar problem

Be careful of the argument. While it is a good idea to 'try and pick the odd numbers", it might not be true that "every maximal sequence must contain all of the odd numbers". As such, this initial restriction might have been too strict, or that it doesn't fully explain what is really happening.

As an example, we could have used the set $\{ 1, 3, 4, 5, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 \}$ , which misses out 7 and 9. The idea here is to "grab a lot of the large numbers, IE we have numbers from 11 to 20, and clearly cannot use 10.". (Admittedly, this can seem like a really dumb move, but my point is to illustrate that the solution is dependent on the initial assumption, hence doesn't apply to all cases.) What other maximal sets are there?

Calvin Lin Staff - 3 years ago

Hmm..that’s correct sir....but I still can’t figure out how to prove rigorously that 14 numbers is the maximum that you can pick.

Chandrashekar Giridharan - 3 years ago

You're close. Think about how I could "miss out 7 and 9".

Here is an easier, and almost equivalent question.

Charlotte selected a set of integers from 1 through 20. None of the numbers in the set is one more than another number in the set.
What is the greatest number of integers she could have selected?

Calvin Lin Staff - 3 years ago

{1,2,3,5,7,8,9,11,12,13,15,17,19,20} is another subset with 14 elements. Here is a greedy algorithm to get there.

Start with including all odd numbers in the Solution set S. (since odd numbers themselves can not be twice of another number).

So S = {1,3,5,7,9,11,13,15,17,19}

Now iterate over remaining even numbers in order [2,4,6,8,10,12,14,16,18,20]

Add the even number to the set if it does not lead to removal of more numbers in S due to the constraints set in the problem.

Thus you only add {2,8,12,20}.

Of course this does not prove rigorously that 14 is the maximum.

If we iterate over the even numbers in the descending order, we get another solution

{1,3,4,5,7,9,11,12,13,15,16,17,19,20}

Question: Does every permutation converge to a Solution set of length 14.

Vishal Shekhar - 3 years ago

I don't understand how can you pick 4 12 16 and 20. Could you please explain? The problem clearly states: "None of the numbers in the subset is double another number in the subset". It does not differentiate between odd and even - it just says "another number".

The answer should be 10 and not 14. And for the general solution it is always a sequence of 1,3, 5, 7, 9, 11.... etc.

Why people do not read the problem and immediately jump to a solution which is incorrect?

Igor Korot - 3 years ago

Which number in the subset (given by Chandrashekar) is 4 double of?
Is 2 in the subset?

Calvin Lin Staff - 3 years ago

It would help if you had clear instruction. From the given info, 4, 10 and 20 should not be included. Nice try

William DeGan - 3 years ago

Can you elaborate on why 4, 10, and 20 should not be included?

Note that 10 is already not included in the final list (because 5 is in there).

Calvin Lin Staff - 3 years ago

Himank Kansal
May 21, 2018

My approach was simple. I was selected those numbers whose double is not there in the integer set, that is, from 11 to 20. Now I start searching for numbers whose double is not between 11 and 20. Therefore I cannot select any number from [6,10]. In 1 to 5, 1 3 4 5 can be chosen.

Final set will be : 1,3,4,5,11,12,13,14,15,16,17,18,19,20. 14 numbers in total.

And since that ends in 14, the highest possible option, the answer can't be higher.

D B - 3 years ago

Zico Quintina
May 20, 2018

Yet another option: we start by taking all numbers from 11 - 20; none of those ten is the double of another in that group. This eliminates the numbers 5 - 10 from being added to the set, but 1 - 5 still remain eligible. Of those five, the only problem is the 1 - 2 - 4 chain, and by removing 2, we can add all four others to our set, ending up with fourteen elements: {1, 3, 4, 5, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20).

Angie Giselle Morocho Alburqueque
May 21, 2018

1-3-4-5-7-9-11-12-13-15-16-17-19-20 - Total of numbers = 14

Rick Weber
May 21, 2018

First I did some guess and check in Excel. My first attempt gave me a set of 14 numbers, but that only provides the right answer.

What I came up with is an approach for eliminating numbers that ultimately rests on the logic of Marta's much more elegant answer... Write the numbers out in a line. Look at 10. It's double 5, and half 20. Eliminate 10 and we preserve both of those numbers. Now work down the line (descending in magnitude). 9 pairs with 18, scratch either one. 8 matches with 4 and 16, so sacrificing 8 saves two numbers. 7 and 14 are equivalent, scratch either one. 6 is between 3 and 12; sacrifice it to save them. 5 is safe because 10 is gone. 4 matches with 2 which matches with 1; drop 2. 3 is already safe, 2 is gone, and 1 is safe.

COUNTA(...) in Excel shows 14 numbers in my set. Good enough for now.

I'm not 100% sure the algorithm works in all cases, but what I think is interesting is how starting in the middle and working towards the smallest number narrows attention to the place in the ordered set where you can do the most good (in terms of making the set bigger). It's simple enough to see why it might work by looking at Marta's answer, but I like having a second perspective on it...

Hao Fu
May 20, 2018

According to the question，we know that we must give up two guys in 1，2，4，8，16 at least，which could prevent the "double group".

In a similar way，to make remaining numbers as many as possible，we must abandon 6 in 3，6，12，and 10 in 5，10，20，an unfortunate guy in 7 and 14，as well as the last one in 9 and 18.

And then we get the answer，to give up 6 guys in a minimum situation，14 is the correct one.

Siamul Karim Khan
May 26, 2018

We can form sets of multiples of 2 (less than 21) starting with each number from 1 to 20, not building for those numbers already included in a previous set formed. So, we have:

1 -> {1,2,4,8,16}

3 -> {3,6,12}

5 -> {5,10,20}

7 -> {7,14}

9 -> {9, 18}

11 -> {11}

13 -> {13}

15 -> {15}

17 -> {17}

19 -> {19}

Now, the max number of integers that can be selected from each set are the alternating entries starting from the first element which mathematically results in the ceiling value of the (cardinality of each set divided by 2). Now if we add these, the result is 14.

Ramadan Alshaqra
May 22, 2018

First, list out the numbers 1 through 20. Then, start at 1 and work your way up to 20, considering at each number carefully whether it was a double of a number already added to the set. This collection will not include any numbers which are doubles of others on the list.

Elîte Keryakos
May 27, 2018

Something to notice when picking the integers is patterns like 3,6,12 where we should select the extremes 3,12 because by selecting the 6, we will have to leave 3,12 so we're taking 1 integer (6) instead of selecting 2 (3,12). We will also select odd numbers > 10, since their double is >20.

The list will be: 1 3 4 5 11 12 13 14 15 16 17 18 19 20

Matthew Hellwig
May 25, 2018

For this, I simply started at 1 and used the rule to exclude or include all others as I counted to 20. 1, so 2 is not allowed, 3, then you can use 4 because you already excluded 2. Then 5, 6 is out because you used 3, and so on. Use the same method up to 20 and count how many numbers you have. 1, 3, 4, 5, 7, 9, 11, 12, 13, 15, 16, 17, 19, 20....14 numbers, and there's your answer.

You also know that all odd numbers will be used. So you just have to check at each even number if its half has already been used, then include or exclude accordingly.

A very simple solution for someone like myself who's forgotten all the fancy math they learned at school.

Cutie 479
May 22, 2018

It's easier to make a list of integers 1-20 one at a time. Just look at the previous numbers and see if you have the number that's half of any of the even numbers (all of the odd numbers work). These are the numbers I got: 1, 2, 3, (no 4 because 2 2=4) 5, (no 6 because 3 2=6) 7, 8 (8 because there is no 4), 9, (no 10 because there is a 5) 11, 12, (12 because there is no 6) 13, 15, 17, 19, 20 (20 because there is no 10), which makes 14 possible options.

Paweł Hordyniak
May 21, 2018

Is it cheating? Because after you count integers starting on 1 you get 14 - this is already largest possible choice from the answers so why bother checking anything else? :D

Because 2x2=4 so the first 14 integers can't all be included.

Rick Weber - 3 years ago

My interpretation of this solution:

For the numbers 1 - 20, when you start selecting numbers in order of lowest (starting on 1), and eliminating the doubles of only the selected numbers as you go, you end up with a list of 14 numbers.

1, 3, 4, 5, 7, 9, 11, 12, 13, 15, 16, 17, 19, 20.

Jonathan Quarrie - 3 years ago

Not Twice

14 solutions

0 pending reports