- 01 Jul '05 21:09A box contains 1000 balls, numbered from 1 to 1000. You randomly pick out balls from this box. If one of the numbers that you have picked happens to be 2 or 3 times the value of another picked number, you are entitled to a prize. To guarantee a prize, at least how many balls do you need to pick?
- 01 Jul '05 21:21

If the first is 1000 then the second 999, 998 etc, then you could in theory go sequentially all the way down to 500 before the criteria was matched. That means you would need to pick 501 balls out.*Originally posted by THUDandBLUNDER***A box contains 1000 balls, numbered from 1 to 1000. You randomly pick out balls from this box. If one of the numbers that you have picked happens to be 2 or 3 times the value of another picked number, you are entitled to a prize. To guarantee a prize, at least how many balls do you need to pick?** - 01 Jul '05 22:05 / 5 edits

that's not everything, because you can pick after those 500 balls, you can pick number 1-166, match the criteria...*Originally posted by jimslyp69***If the first is 1000 then the second 999, 998 etc, then you could in theory go sequentially all the way down to 500 before the criteria was matched. That means you would need to pick 501 balls out.**

EDIT

if you pick out all balls from 501-1000, you picked 500 balls.

If you pick every number under the 166 (501/3-1) which isn't a devision by 2 or 3... you got all balls I think.

That's around 550-600 balls...

EDIT:

you can pick then 84-166, 14-27, 3-4, that's 500+83+14+2+1 (last ball, which guarantees it) balls, so that's.... 600 balls exactly!

I like such puzzles, you need some math, and some logic thinking, I like it both - 01 Jul '05 22:16

Never thought of that. Well pointed out. Personally I think it's a load of balls.*Originally posted by Florrat***that's not everything, because you can pick after those 500 balls, you can pick number 1-166, match the criteria...**

EDIT

if you pick out all balls from 501-1000, you picked 500 balls.

If you pick every number under the 166 (501/3-1) which isn't a devision by 2 or 3... you got all balls I think.

That's around 550-600 balls... - 02 Jul '05 04:11 / 1 editWhat if the number of balls in the box is n, numbered 1 to n - how many balls do you have to pick to ensure that at least one of them is at least exactly 2 or 3 times another?

What are the odds, if you take out 1/2(n) balls that you don't have at least one ball that is exactly 2 or 3 times another? - 02 Jul '05 11:35

I think you can't make exactly rules for it, because you can't pick a half ball, so this time it was exactly 60% (0.6n)*Originally posted by The Plumber***What if the number of balls in the box is n, numbered 1 to n - how many balls do you have to pick to ensure that at least one of them is at least exactly 2 or 3 times another?**

What are the odds, if you take out 1/2(n) balls that you don't have at least one ball that is exactly 2 or 3 times another?

but if you have 2 balls you must pick n balls (2),

3 balls 2/3n

4 balls 3/4n = 0.75n

5 balls 4/5n = 0.8n

6 balls 5/6n

7 balls 6/7n

8 balls 6/8n = 0.625n

9 balls 7/9n = 2/3n

10 balls 7/10n = 0.6n

11 balls 8/11n

12 balls 9/12n = 2/3n

n= 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 if n is this

pick - 2 2 3 4 5 6 6 7 7 8 9 9 10 10 11 the balls you must pick

+ 0 1 1 1 1 0 1 0 1 1 0 1 0 1 the increasment if n increases with one, the balls you must pick increases with

after this 11010 will repeat I believe, I can't see a better way to solve this, and I can't finish this too. - 02 Jul '05 16:41Let's see... For the worst case scenario we can start by calculating all numbers that are not divisible by 2 or 3 (lower bound). The sieve:

Let n>=3 is the total number of balls. Then by "n2" we denote the number of numbers divisible by 2; by "n3" the number of numbers divisible by 3; and by "n6" the number of numbers divisible by 6.

m - Number of numbers from 1 to n not divisible by 2 or 3:

m = n + [n/6] - [n/2] - [n/3]; where [ ] denotes the floor function or the integer part; That are balls which give us no chance of fulfilling the condition.

So we have that if T is the maximum number of balls that can be taken before the condition is fulfilled m<=T;

I'll give it some more thought.

- 03 Jul '05 08:07 / 1 editI think I finally got it:

let n be the number of balls and M signify the maximum number of balls one can take**before**fulfilling the condition;

Now I will lay down my reasoning:

In order to get the maximum number of balls we need to remove all balls divisible by odd powers of 2 and 3. The ratio of any pair of the balls that are still left would be greater or different from 2 or 3, .

So**M = n + [n/6] - [n/2] - [n/3] - [n/6^2] + [n/2^2] + [n/3^2] + [n/6^3] - [n/2^3] - [n/3^3] - [n/6^4] + [n/3^4] + [n/2^4] + ...**

So basically we "unremove" the even powers and remove the "odd" what we are left with are purely even powers; those divisible by the resepective power of 6 is added/subtracted because it is counted twice (once in the respective power of 3 and one more time in the respective power of 2)