Come play IF you Dare

1. Jan 10, 2005

121212

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 :)

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. Jan 10, 2005

Galileo

I think the answer to the first is:

$$\frac{(4+N)!}{5!(N-1)!}$$

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
3. Jan 10, 2005

121212

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
4. Jan 10, 2005

vincentchan

galileo did it WRONG
here is the solution for the first problem:
$$\Sigma_{k=5,500} \Sigma_{i=o,k} (-1)^i \left( \begin{array}{cc}k\\i\end{array} \right) (k-i)^5$$
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
5. Jan 10, 2005

vincentchan

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......

6. Jan 10, 2005

Galileo

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

$$\bullet \vert \bullet \vert \vert \bullet \bullet \vert \vert \vert \bullet$$
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:

$$\frac{(5+6)!}{5!6!}$$

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:

$$\frac{(k+N-1)!}{k!(N-1)!}$$

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
7. Jan 10, 2005

vincentchan

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

8. Jan 10, 2005

HallsofIvy

9. Jan 10, 2005

121212

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 :)

from lowest to highest coin used
yah yah this is a hard one ;) :P

10. Jan 10, 2005

chroot

Staff Emeritus
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

11. Jan 10, 2005

121212

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

12. Jan 10, 2005

vincentchan

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......

13. Jan 10, 2005

121212

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 ...

14. Jan 10, 2005

NateTG

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.

15. Jan 11, 2005

121212

ok ill do that then ;) thanks anyway :D
greetz

16. Jul 25, 2005

lazyidiot

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
17. Jul 25, 2005

NateTG

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?

18. Jul 25, 2005

NateTG

Hmm, it seems to matter whether negative denominations are allowed.