Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Come play IF you Dare

  1. Jan 10, 2005 #1
    Come play IF you Dare!!!

    hey i made a little game i need to know if its you guys can calculate it
    atleast try ;) :
    Code (Text):
    You have 5 balls that you have to divide (put the balls in the cups) between a number of cups in all possible ways.

    1 cup:
    ---
    |5|
    ---
    1 possibility
    Total: 1 possibility

    2 cups:
    -----
    |1|4|
    -----
    |2|3|
    -----
    |3|2|
    -----
    |4|1|
    -----
    |5|0|
    -----
    |0|5|
    -----
    6 possibilities
    Total: 7 possibilities

    3 cups:
    21 possibilities
    Total: 28 possibilities

    Continue until you have 500 cups. The total of possibilities from 1 to 500 is the answer.
     
    --------------------------------------------------------------------------
    and another one by my friend ! :
    Code (Text):
     N = number of Queens.

    You have to put N Queens onto a chess board of N * N squares, so that the Queens don't threaten each other. (horizontally, vertically, diagonally)
    How many possible setups are there?

    Thus:
    How can I put 4 Queens onto a 4*4 board
    How can I put 5 Queens onto a 5*5 board
    etc...

    Calculate all setups for 4 to 10 Queens, take the sum of the results - the sum is the answer
    -------------------------------------------------------------------------
    And another one !
    -------------------------------------------------------------------------
    Code (Text):
     If you want to buy something for less than 100 Euro you can pay with different 'units' (coins and bills).
    At the moment the 6 best existing units to use are: 1, 2, 5, 10, 20 and 50.

    If you want to buy something (that is less than 100 Euro) you have to use some of those units to pay for it.

    Now let's go shopping with these 6 units :)
    You are going to search for products that are 1 euro untill 99 euro, and you are going to buy one of each. Each time you buy something you choose as less units as possible (you have an infinite amount of units).

    Let's see how many units we need if we use the units 1, 2, 5, 10, 20 and 50:

    1 EURO -> only 1 unit: 1
    2 EURO -> 1 unit : 2
    3 EURO -> 2 units : 1 + 2
    ..
    ..
    ..
    98 EURO -> 6 units : 1 + 2 + 5 + 20 + 20 + 50
    99 EURO -> 6 units : 2 + 2 + 5 + 20 + 20 + 50

    Now we will take the average of the needed units between 1 and 99, which is 3.4 units.
    That's quite alright, but we can do better...

    Your job is to find the lowest average with 6 different (integer) units.
    Maybe a 3 euro coin is a good idea? And what about a 22 euro bill? Try it out :)

    Enter your answer below like this => 1:2:5:10:20:50 (example).
    from lowest to highest coin used
    i am gonna try to put these on a site and many more > maybe it needs a little programming to ge tthe correct answers

    greetz lassie
     
    Last edited: Jan 10, 2005
  2. jcsd
  3. Jan 10, 2005 #2

    Galileo

    User Avatar
    Science Advisor
    Homework Helper

    I think the answer to the first is:

    [tex]\frac{(4+N)!}{5!(N-1)!}[/tex]

    where N is the number of cups. That is the number of ways to distribute 5 balls over N cups.
    So for 500 cups, there are 265,661,562,600 ways.
    You shouldn't add up the number of ways for one cup plus the number of ways for 2 cups and so forth.
     
    Last edited: Jan 10, 2005
  4. Jan 10, 2005 #3
    maybe u need to programe something then if you cant calculate it ;)
    but keep ya head up and you have something to do also

    good luck

    (use excel)
     
    Last edited: Jan 10, 2005
  5. Jan 10, 2005 #4
    galileo did it WRONG
    here is the solution for the first problem:
    [tex]\Sigma_{k=5,500} \Sigma_{i=o,k} (-1)^i \left( \begin{array}{cc}k\\i\end{array} \right) (k-i)^5 [/tex]
    If you have learned combinatorics, the idea is simple. this has no different with putting n indistinguishable balls into k indistinguishable cells which allowed cells empty, sum k up from 5 to 500 and let n be 5, that's it...... i am not sure could this be simplify...

    edit: is from 1 to 500 instead of 5 to 500
     
    Last edited: Jan 10, 2005
  6. Jan 10, 2005 #5
    the second answer is 1224: 2+10+4+40+92+352+724
    don't say my answer is wrong if you can't find the answer......
     
  7. Jan 10, 2005 #6

    Galileo

    User Avatar
    Science Advisor
    Homework Helper

    I didn't assume the cups were indistinguishable.
    Assume they are distinguishable.
    Let's take 7 cups for simplicity. Then consider the following drawing:

    [tex]\bullet \vert \bullet \vert \vert \bullet \bullet \vert \vert \vert \bullet[/tex]
    The 5 dots depict the 5 balls and the 6 vertical bars distinguish 7 area's which represent the 7 cups. So in this particular arrangement we have 1 ball in the first cup, 1 on the second, cup 3 is empty, there are 2 in the 4th cup, cups 5 and 6 are emtpy and there is one in the 7th cup.

    It's clear that any order of the 5 dots and 7 lines gives a way to put the 5 balls in the 7 cups. Since there are 5+6 symbols, there are (5+6)!=11! ways to arrange them.
    But permutation of the dots do not give a different arrangement and neither does a permutation of the lines. So the number is:

    [tex]\frac{(5+6)!}{5!6!}[/tex]

    In general, you can do this for k balls and N cups. You'll have k dots and N-1 bars. So the number of arrangements here is:

    [tex]\frac{(k+N-1)!}{k!(N-1)!}[/tex]

    The same problem arises in statistical mechanics, when considering the number of ways to put k bosons in N 'energy states'.

    Note that I didn't consider the cups indistinguishable. That is, have 5 balls in the first cup is different from having 5 balls in the second cup.

    BTW: 121212 didn't consider the cups indistinguishable either.
     
    Last edited: Jan 10, 2005
  8. Jan 10, 2005 #7
    oh, yeah, you are right, the question said the cups are distinguishable, because the title of the post, i assume this is a very hard problem and didn't read it carefully, and your answer is probably right... and isn't that his question itself is ADD UP ALL THE possibility.... if not.....why did he say we need writing a computer program.... this indeed is an easy problem
     
  9. Jan 10, 2005 #8

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    In what class was this given as homework?
     
  10. Jan 10, 2005 #9
    wow didnt though u would get so far
    btw you answer was correct on the chess game :p

    i go to sleep now
    in that time i got another one for you guys thats also very hard !!1 grrr
    --------------------------------------------------------------------------
    Code (Text):

    If you want to buy something for less than 100 Euro you can pay with different 'units' (coins and bills).
    At the moment the 6 best existing units to use are: 1, 2, 5, 10, 20 and 50.

    If you want to buy something (that is less than 100 Euro) you have to use some of those units to pay for it.

    Now let's go shopping with these 6 units :)
    You are going to search for products that are 1 euro untill 99 euro, and you are going to buy one of each. Each time you buy something you choose as less units as possible (you have an infinite amount of units).

    Let's see how many units we need if we use the units 1, 2, 5, 10, 20 and 50:

    1 EURO -> only 1 unit: 1
    2 EURO -> 1 unit : 2
    3 EURO -> 2 units : 1 + 2
    ..
    ..
    ..
    98 EURO -> 6 units : 1 + 2 + 5 + 20 + 20 + 50
    99 EURO -> 6 units : 2 + 2 + 5 + 20 + 20 + 50

    Now we will take the average of the needed units between 1 and 99, which is 3.4 units.
    That's quite alright, but we can do better...

    Your job is to find the lowest average with 6 different (integer) units.
    Maybe a 3 euro coin is a good idea? And what about a 22 euro bill? Try it out :)

    Enter your answer below like this => 1:2:5:10:20:50 (example).
    from lowest to highest coin used
    yah yah this is a hard one ;) :P
     
  11. Jan 10, 2005 #10

    chroot

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Participants:

    Please do not hand out answers to homework problems. You should emphasize technique and methodology, but always leave at least some of the work to the student. Generally, the student must show some of his/her work, up to the point where he/she becomes stuck, before anyone should provide help.

    121212:

    Please do not attempt to use this site as a way out of your homework. Labelling your homework assignments as "games made by a friend" is ridiculous. If you do not at least make an attempt to do your homework before posting it here, we will not help you.

    - Warren
     
  12. Jan 10, 2005 #11
    this is not really ment as homework cause a friend of a friend made these
    and it is a game to relax but also homework cause u have to do it with your learned maths , and you "Learn" stuff
    ----edit----
    (lol i dont want a teacher that gives me this kinda homework whaha :P)

    greetz lassie
     
  13. Jan 10, 2005 #12
    okay, then do you have the answer and do you know how to solve it, if yes, please don't post it here, if no, we won't give you the solution......
     
  14. Jan 10, 2005 #13
    if i didnt solve it would i post it as a game then ?
    i just programmed in vb and perl
    and i though that maths forum ""grand masters "" would like to solve this game ....
    sorry if my attempt on harmony and fun in life is disaccepted here ...
     
  15. Jan 10, 2005 #14

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    No, talking about this stuff is fine, but it's not appropriate for the homework section. If you had posted it in, for example, the brain teasers section, nobody would be complaining.
     
  16. Jan 11, 2005 #15
    ok ill do that then ;) thanks anyway :D
    greetz
     
  17. Jul 25, 2005 #16
    All the 3 above questions are programming challenges of net-force.nl ... your friend must be trying to solve them without taking any pain ;)

    Ive solved first 2 questions a long time before .. to solve the 3rd one, one must brute-force the possible set of answers, and Ive nt done that. So, If any one can solve that .. gimme a buzz.
     
    Last edited: Jul 25, 2005
  18. Jul 25, 2005 #17

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    There's the question of how to prove that the answer is optimal without brute force. Perhaps looking at that first will provide some insight?
     
  19. Jul 25, 2005 #18

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    Hmm, it seems to matter whether negative denominations are allowed.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?