When can you be certain you've got this one, drawing from 1-1000?

[leealdtes]

The problem:
There are cards, labeled 1-1000.
They're drawn one at a time without replacement.
How many draws must there be to be certain one has been drawn that's twice another that was selected?

So far, I figured half the numbers could be double another number (because the cards 501-1000 don't have any cards labeled with a number that is double, like 1002 or 2000 and so on).

But, after that, I'm lost.

The best I did was using a calculator to get that the summation of all 1/(1000-x), with x from 1 to 632, but 632 was the wrong answer. The correct answer is given as 667.

 

[tkhunny]

More of a pidgeon hole thing than a probability. The words "be certain" are most important. I've never been all that clear that counting things ALWAYS belongs in "Statistics". Nevertheless...

Perhaps working from the top would help?

You can pick 501-1000 and never meet the 2x criterion. There's 500, but we need more.
After that, you must NOT EVER pick 251-500.
You can then pick...{what?}
After that, you must NOT EVER pick...{what?}
Continue in this way.

 

[leealdtes]

So, I can't pick the top 500. Or, to not get a card that is twice another selected, I can't pick any even cards. There are 500 even cards. But, why must I not pick another 249 cards (cards 251-500) if 667-500=167?

Somehow, according to the answer key, I can only be certain I did pick a card twice another after 667 draws. But, I don't know how to get that figure.

Sorry, I'm still so lost.

 

[tkhunny]

No, you MUST pick the top 500. That's the largest patch where you will not ever find a double.

After that:
You can't pick 500, because you already have 1000 and you will hit a double.
You can't pick 317, because you already have 634 and you will hit a double.

You did not continue...

Roughly
Pick 500
Avoid 250
Pick 125
Avoid 62.5
Pick 31.25
Avoid something
Pick Something
Avoid something
CONTINUE in this way... Don't stop until you're done.

2^10 = 1024, so you can't go through too many cycles.
Work out the details of those fractions.

 

[leealdtes]

It's true one might go on forever into very, very small decimal numbers in saying "avoid this, pick half"... I could/did use a calculator I have to enter 1000/2, which equals 500, then hit /2 again and again (which uses the previous answer logged) to get smaller and smaller decimal numbers.
I was counting by brute force at first until I tried to automate this calculation on my calculator with the sum of all 1000/2^x, with x=1 to 35. So, maybe the calculator just rounded at that point? The sum was equal to 1000. Anything less than 35 wouldn't reach 1000. Anything at 35 or greater than 35 was 1000.

Which is great, but all besides the point because why take the sum? Like you said, can't go past 2^10, which equals 1024.

But, what is the 35 representing, I wonder? It's just weird how if I add that to 632 I get 667?

Back to thinking about the goal, which is to pull only cards not double some other one:
After the top 500, with so many possible doubles...that is, to avoid 500, 498, 496, 494, etc. being a double, one mustn't pick all the numbers half that, and one mustn't pick any other halves possible after that to avoid those being doubles if those were picked instead...

Halving over and over just before 2^10 hits 1024, leaves one with 2^9 max to use in the denominator.
1000/2, 500/2, 250/2, 125/2, 125/4, 125/8, 125/16, 125/32, 125/64
Or:
1000/2^1, 1000/2^2, 1000/2^3, 1000/2^4, 1000/2^5, 1000/2^6, 1000/2^7, 1000/2^8, 1000/2^9

I don't see how we get to 667 yet.

Maybe if the problem was smaller, so I could envision it? Say, the numbers 1-30. With the same goal:

Of the full set of cards 1-30...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

...the top half 15 cards won't draw a double...

16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

...but, of the bottom half...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

...there's about half within it that would make (some of the other half)...

1 2 3 4 5 6 7

...and another half that would do the same...

1 2 3

...and another...

1

The sum of all 30/2^x is 30 when x=1 to 33. But, you can't draw more than 30 cards. So, this method must be wrong. Would I be certain after 15+4 cards draws, using the number of times I halved the original set? But, then, that doesn't work for cards 1-1000. Or is it 26, using the cards that could be doubles within half selections? But, then, how do I get 500 + 167 card draws from the original set? Where did 167 come from? Or, 667?

 

[Dr.Peterson]

It's true one might go on forever into very, very small decimal numbers in saying "avoid this, pick half"... I could/did use a calculator I have to enter 1000/2, which equals 500, then hit /2 again and again (which uses the previous answer logged) to get smaller and smaller decimal numbers.
I was counting by brute force at first until I tried to automate this calculation on my calculator with the sum of all 1000/2^x, with x=1 to 35. So, maybe the calculator just rounded at that point? The sum was equal to 1000. Anything less than 35 wouldn't reach 1000. Anything at 35 or greater than 35 was 1000.

Which is great, but all besides the point because why take the sum? Like you said, can't go past 2^10, which equals 1024.

But, what is the 35 representing, I wonder? It's just weird how if I add that to 632 I get 667?

I'm not sure what that 35 is. But in your calculation, it is necessary to round, not just to add 1000/2^x. Also, you want to add only every other one of those numbers

To avoid any doubles, of the 1000, you:

• take 1000/2 = 500 numbers [namely 501 to 1000],
• skip 500/2 = 250 [251 to 500],
• take 250/2 = 125 [126 to 250],
• skip ceil(125/2) = 63 [63 to 125], -- here "ceil" means "round up"
• take floor(63/2) = 31 [32 to 62], -- here "floor" means "round down"
• skip ceil(31/2) = 16 [16 to 31],
• take floor(16/2) = 8 [8 to 15],
• skip ceil(8/2) = 4 [4 to 7],
• take floor(4/2) = 2 [2 to 3],
• skip ceil(2/2) = 1 [1], and there are no more.

So the total number taken is 500+125+31+8+2 = 666. The next one you take has to be half or twice of one that was picked, so the answer is 667.

What's interesting to me is that 666 is floor(1000/3). So what I'm curious about is whether there is a way to get 3 into the explanation. There may be a binary division by 3 hidden in here, for example.

 

[tkhunny]

"Work out the details of those fractions." -- You didn't do that. :-(
Dr. Peterson has done it for you.

 

[leealdtes]

Sorry, tkhunny. :'(
I see what Dr. Peterson did. Thank you both for your patience and explanations! They are very much appreciated.

To try it out on my smaller problem...
Of the numbers 1-30:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Take the 15 w/no doubles (30/2):
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Skip Cof (15/2) 7.5, which is 8
& take 4:
4 5 6 7
Skip (4/2) 2
& take 1:
1

Have/drawn: 1 4 5 6 7 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Left over still in deck: 2 3 8 9 10 11 12 13 14 15
So, max., there are 20 cards you could pull w/o drawing a double. So, you'd be sure you'd drawn one in 21 draws.