Posers and Puzzles

Posers and Puzzles

  1. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    04 Jan '03 22:29
    I have 500 coins, and four bags. In how many ways can I put these coins in bags so that all coins are in a bag, and some bag may be empty. (Only count essentially different combinations, order doesn't matter-200, 150, 100, 50 is the same as 50, 100, 150, 200.) The total number is very large, and the best way i can find to do it is very difficult and time-consuming. I would be very impressed if anyone gets it, and it would be cool if they got the same answer as i did (mine could be a bit off ...)
  2. Donationmwmiller
    RHP Member No.16
    Joined
    25 Feb '01
    Moves
    68438
    04 Jan '03 22:381 edit
    500,0,0,0.
    One bag with all the coins in it.
    I think this meets your description for all the coins in a bag.
  3. Joined
    01 Dec '01
    Moves
    14745
    04 Jan '03 23:36
    Originally posted by royalchicken
    I have 500 coins, and four bags. In how many ways can I put these coins in bags so that all coins are in a bag, and some bag may be empty. (Only count essentially different combinations, order doesn't matter-200, 150, 100, 50 is the same as 50, 100, 150, 200.) The total number is very large, and the best way i can find to do it is very difficult and ...[text shortened]... gets it, and it would be cool if they got the same answer as i did (mine could be a bit off ...)
    Assuming the coins are identical and not unique, then I could assume it's the combination of 500 in 5 (the empty bag):

    500!
    ---------
    5! x 495!

    or 496x497x498x499x500 : (2x3x4x5)
    =

    127 622 343 800. Or am I wrong (again)?

    Gil.
  4. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    05 Jan '03 02:13
    I may have expressed the question wrong. I am essentially looking for the total number of 4-tuples of nonnegative integers that add up to 500. I used two methods, which are essentially the same, but very tedious.
  5. Joined
    01 Dec '01
    Moves
    14745
    05 Jan '03 09:52
    Originally posted by sintubin
    Assuming the coins are identical and not unique, then I could assume it's the combination of 500 in 5 (the empty bag):

    500!
    ---------
    5! x 495!

    or 496x497x498x499x500 : (2x3x4x5)
    =

    127 622 343 800. Or am I wrong (again)?

    Gil.
    this was wrong anyway. The possibility of an empty bag could not be represented by a fith bag.

    It is much more complicated.
  6. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    05 Jan '03 16:42
    That's true. The answer is smaller than that by several orders of magnitude.
  7. DonationAcolyte
    Now With Added BA
    Loughborough
    Joined
    04 Jul '02
    Moves
    3790
    05 Jan '03 17:39
    I think I've got something, but it's ugly and I don't know how to tidy it up. Consider whether any two bags have the same number of coins in them. Exactly one of the following is true:

    a all bags have 125 coins.
    b 3 bags same, 1 different.
    c 2 pairs of bags.
    d A pair and two distinct.
    e All distinct.

    There is only 1 possibility for a.
    For b, 500/3 = 166 (rounded down), so there are 166 possibilites (+1 for 3 empty bags, -1 for case a)
    For c, the pair with the least coins could have between 0 and 124 each, so 125 possibilities.

    Now it gets ugly. Suppose we have a string of 500 0s and 2 1s. For every pair of 0s, put 1 coin in each of the first two bags until you reach the first 1. Then put a coin for every 0 into bag 3 until you reach the second 1, then put the remaining coins in bag 4. Now there are 251 choose 2 strings (=125*251) where both 1s occur in an odd position, so these are valid; and there are 251^2 strings where one is in an even and one in an odd position. In (251/2)(251+1) (=126*251) of these the odd one occurs first so these are also valid. This gives 251^2. However among these strings, 1 falls under case a; 2*166 fall under case b (3rd or 4th bag same as 1st two); and 2*125 fall under case c (larger pair could be 1&2 or 3&4). The order of the 3rd and 4th bags doesn't matter, so the remainder of the strings occur in equivalent pairs. This gives a total of [(251^2 - 1)/2 - 166 - 125] for case d, and a total of (251^2+1)/2 overall.

    Finally, most of the possibilities are in case e: this time we have a string with 500 0s and 3 1s, with the obvious interpretation. There are 503 choose 3 (=167*251*503) of these. However amongst these 1 falls under a, 4*166 under b, 6*125 under c and 12*[(251^2 - 1)/2 -166 -125] under d (consider possible orders of bags). The rest occur in equivalence classes of 24.

    So we have a grand total of {167*251*503 - 1 - 4*166 - 6*125 - 12*[(251^2 - 1)/2 - 166 -125]}/24 + (251^2 + 1)/2.

    I think this is [167*251*503 - 1 + 8*166 + 6*(251^2 + 128)]/24, but I've probably made some mistakes along the way, and don't really want to simplify this expression any more. My calculator says 894348; does this sound right?
    I'm sure you came up with a more elegant method than this!
  8. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    05 Jan '03 22:26
    Congratulations! You are exactly right. My METHOD was less elegant than that, although it involved proving a fairly groovy theorem. Let P(m, n) be the number of ways of dviding n into at most m addends. Thus we are looking for P(4, 500)-P(3, 500). I then proved that for real x such that |x|<1:

    [(1-x)(1-x^2)(1-x^3)...(1-x^m)]^-1 = 1 + P(m, 1)x + P(m, 2)x^2+ ...

    So all we are looking for are the 500th coefficients in the Maclaurin series expansion of (1-x)(1-x^2)(1-x^3)^-1, and the same times 1/(1-x^4). We can now do either of two things, namely:

    Take the 500th order derivative of each of these at 0, divide each by 500!, and subtract (by Taylor's theorem), or factor these functions and find their Maclaurin expansions by multiplication of the series of each of the factors. The first method is ridiculously tedious, but the second is only absurdly tedious, and yields 894348. I thought somehow that this would be settled when you weighed in on this one. 'Grats.
  9. Donation!~TONY~!
    1...c5!
    Your Kingside
    Joined
    28 Sep '01
    Moves
    40665
    13 Jan '03 23:18
    You guys are freakin nuts in here! Hehehe...Just kidding! Kudos for the answer!
  10. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    14 Jan '03 00:361 edit
    I know. You should come here more often 😉
  11. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    16 Apr '03 01:291 edit
    I saw this thread again yesterday, and had a few minutes. I figured, in view of the very fine and clear solution Acolyte produced, that I should try to solve this one in a way not involving large infinite series. So I found another interesting way.

    Let f(n,m) be the number of ways of representing n as the sum of at most m positive integers. Then it is fairly easy to prove that:

    f(n,m) = f(n-m,m) + f(n,m-1)

    Furthermore, if we want to find f(n,2), we can arrange the numbers in columns so that rows sum to n:

    0....n
    1....n-1
    ...
    n....0

    Clearly there is repetition here, so f(n,2) = [n/2] +1. Using the above recursion formula with this gives:

    f(500,4) = SUM([n=1 to 125] SUM([k=0 to 4n/3] [(4n-3k)/2] + [4n/3]))

    Adding these up gives 894348. 'Tis nice.
  12. Joined
    12 Apr '03
    Moves
    31
    16 Apr '03 19:16
    Good effort lad
  13. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    16 Apr '03 21:51
    Originally posted by waldorf
    Good effort lad
    Thank you. Approximately who are you? Can you prove the recursion formula...?
  14. Joined
    26 Mar '03
    Moves
    143
    20 Apr '03 18:37
    Originally posted by royalchicken
    Thank you. Approximately who are you? Can you prove the recursion formula...?
    Wat????????????
  15. Standard membergenius
    Wayward Soul
    Your Blackened Sky
    Joined
    12 Mar '02
    Moves
    15128
    20 Apr '03 20:52
    Originally posted by royalchicken
    Thank you. Approximately who are you? Can you prove the recursion formula...?
    erm-yeah-what's the recursion formula (i've heard of it before, but i ca't remeber what it is...😕)
Back to Top