wu :: forums - Print Page


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

        riddles >> putnam exam (pure math) >> Card throwing probability
        
(Message started by: Aryabhatta on Dec 29^th, 2005, 2:43pm)

Title: Card throwing probability
Post by Aryabhatta on Dec 29^th, 2005, 2:43pm

Not sure if this has been asked before...

Anyway, here goes:

p is an odd prime number. You have 2 decks of p cards each, each deck having cards numbered 1 to p, the numbers being written on the front face of the cards. You throw the cards up and they randomly fall to the floor. You now sum up the numbers on the cards which have fallen face up.

What is the probability that this sum is divisible by p?

Title: Re: Card throwing probability
Post by Aryabhatta on Jan 3^rd, 2006, 10:10pm

What is wrong with this one? too easy/hard... seen it before?

Title: Re: Card throwing probability
Post by Barukh on Jan 3^rd, 2006, 10:47pm

I would say not too easy, and not seen this before. ;D

Title: Re: Card throwing probability
Post by SMQ on Jan 4^th, 2006, 6:04am

Well, since I'm more of an experimentalist than an analyst, I thought I'd investicate a few small cases:

p = 3: 24 / 2⁶ ~ 1 / 2.66667
p = 5: 208 / 2¹⁰ ~ 1 / 4.92308
p = 7: 2344 / 2¹⁴ ~ 1 / 6.98976
p = 11: 381304 / 2²² ~ 1 / 10.9999
p = 13: 5162224 / 2²⁶ ~ 1 / 13.0000

That should give you analytical types something to work with. ;)

--SMQ

Title: Re: Card throwing probability
Post by Eigenray on Jan 4^th, 2006, 8:00pm

Nice problem!

We need to count the number of subsets whose sum is divisible by p. Hint: I expected this to be roughly [hide]4^p/p[/hide]. Of course it can't be exactly, but it's reasonable to assume that the solution will include a combinatorial proof that [hide](4^p-4)/p[/hide] is an integer. I only know the one, so...

[hideb]Clearly there is 1 subset with 0 cards, and 1 with 2p cards.

Now consider taking any subset of k cards, and adding 1 to each card (mod p), increasing the sum by k. If we do this p times, and k is relatively prime to p, then we get a cycle of p subsets, exactly one of which will have sum 0 mod p. This partitions the subsets of size other than 0, p, or 2p, of which there are 2^2p-1-(^2pC_pp)-1, and we count exactly 1/p-th of them.

Now consider a subset of size p. If it is not all from a single deck, then we can similarly cycle just the cards from the second deck, changing the sum by a number relatively prime to p each time. Thus we count exactly 1/p-th of these (^2pC_p)-2 possibilities, together with 2 ways of taking all p cards from a single deck.

Altogether, we have
2 + [ 2^2p - 2 - (^2pC_p) ]/p + [ (^2pC_p) - 2 ]/p + 2 = [ 4^p + 4(p-1) ]/p.[/hideb]

Title: Re: Card throwing probability
Post by Aryabhatta on Jan 4^th, 2006, 10:32pm

Excellent! Well done Eigenray.

Title: Re: Card throwing probability
Post by Aryabhatta on Jan 5^th, 2006, 4:37pm

here is another solution which uses generating functions...

Let P(z) = ( (1+z)(1+z²)...(1+z^p) )²

We are looking for sum of coefficients of z^kp where k starts at 0 and goes on...

Set Q(z) = P(z) + P(wz) + P(w²)+... + P(w^p-1z)

where w is a p^th root of unity.

We see that we are looking for Q(1)/p.

It is easy to see that P(w^m) = 4 for 0 < m < p (Consider H(z) = z^p -1 = (z-w)(z-w²)...(z-w^p) and set z = -1)