1. Joined
    29 Feb '04
    Moves
    22
    01 Jul '05 21:09
    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?
  2. In your face
    Joined
    21 Aug '04
    Moves
    55993
    01 Jul '05 21:21
    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?
    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. 😀
  3. Joined
    24 May '05
    Moves
    1958
    01 Jul '05 22:055 edits
    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. 😀
    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...

    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 😀😛
  4. In your face
    Joined
    21 Aug '04
    Moves
    55993
    01 Jul '05 22:16
    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...
    Never thought of that. Well pointed out. Personally I think it's a load of balls. 😛
  5. Standard memberThe Plumber
    Leak-Proof
    under the sink
    Joined
    08 Aug '04
    Moves
    12493
    02 Jul '05 04:111 edit
    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?
  6. Joined
    24 May '05
    Moves
    1958
    02 Jul '05 11:35
    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?
    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)
    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.
  7. Joined
    30 Oct '04
    Moves
    7813
    02 Jul '05 16:41
    Let'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.

  8. Joined
    30 Oct '04
    Moves
    7813
    03 Jul '05 08:071 edit
    I 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)
Back to Top

Cookies help us deliver our Services. By using our Services or clicking I agree, you agree to our use of cookies. Learn More.I Agree