wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> balls in bags
        
(Message started by: inexorable on Jan 7^th, 2006, 11:47am)

Title: balls in bags
Post by inexorable on Jan 7^th, 2006, 11:47am

m identical balls are to be placed in n distinct bags. You are given that m>=kn, where k is a natural number >=1. In how many ways can the balls be placed in the bags if each bag must contain atleast k balls?

Title: Re: balls in bags
Post by towr on Jan 8^th, 2006, 7:46am

[hide]
choose(m, kn) * choose(m-kn+n-1, m-kn)

randomly pick the kn balls you have to put in the n bags
then distribute the rest randomly.
[/hide]

I'm not entirely convident though :-/

Title: Re: balls in bags
Post by Grimbal on Jan 8^th, 2006, 2:39pm

I'd say [hide] put k balls in each bag and count in how many ways you can arrange the m-kn remaining.
The ways to put m-kn balls in n bags is Choose((m-kn)+n,n).
[/hide]

Title: Re: balls in bags
Post by towr on Jan 8^th, 2006, 11:58pm

on 01/08/06 at 14:39:56, Grimbal wrote:

[hide]The ways to put m-kn balls in n bags is Choose((m-kn)+n,n).
[/hide]

I don't think so. n bags, means n-1 seperators.
And the number of ways to put 3 balls in one bag is 1, not 4.

And if you have to put two balls in two bags, one in each, you can do so in two ways. Put one in bag one first, or in bag two first, and then one in the other.

Title: Re: balls in bags
Post by Grimbal on Jan 9^th, 2006, 12:54am

Uh... well, yes, there must be a -1 somewhere.
[hide] Choose(m-kn+n-1,n-1) maybe? [/hide]

Title: Re: balls in bags
Post by towr on Jan 9^th, 2006, 11:24am

That solves half the problem.

If m=k*n, as an obvious case, you'd always get 1, while I'd say it's clearly not.
And I suppose it also discredits my first solution.

for k=1 if m=n, there are m! ways to fill the bags

Title: Re: balls in bags
Post by towr on Jan 9^th, 2006, 11:41am

[hide]m!/[k!^n * (m-n*k)!] * choose(m-kn+n-1, m-kn) [/hide]

Title: Re: balls in bags
Post by Grimbal on Jan 10^th, 2006, 12:28am

I'm not sure it is about the process of putting the balls. I think it is only about the end result. Or you could also consider cases where you put 2 balls at the same time, cases where you take out a ball you put in earlier, etc.

Title: Re: balls in bags
Post by towr on Jan 10^th, 2006, 5:55am

bah.. ambiguity..