wu :: forums - Print Page


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

        riddles >> hard >> Name the cards
        
(Message started by: puzdispenser on May 20^th, 2005, 12:04pm)

Title: Name the cards
Post by puzdispenser on May 20^th, 2005, 12:04pm

I'm going to shuffle a deck of cards and deal them out face up in four rows of thirteen. Your task is to turn some of the cards face down so that your partner, using a pre-discussed strategy, can correctly identify every face down card.
What's the best practical strategy and how many cards on average could your partner call? (I have a simple one in mind, but I'm betting someone here is capable of doing much better)
What would be the theoretical limit if you could use computer power to fully exploit information encoded in patterns and subsets? (Maybe this is difficult enough that you should solve it with a smaller n, like a random arrangement of the numbers 1 to 10. Or maybe the whole thing will be easy for you masterminds).

Title: Re: Name the cards
Post by Deedlit on May 21^st, 2005, 1:59am

From the phrasing of your question, there seem to be two parameters: how may cards you flip over and how many cards (or percentage) your partner can guess correctly. For both numbers we can talk about expected value or bounds.

I will address the subcase in which your partner has to guess all the cards correctly. In that case, your partner needs to see a different configuration of cards for every possible ordering. There are 52! possible orderings; a "perfect" strategy will assign orderings to all configurations with no cards revealed, 1 card revealed, etc., until we have enough configurations for all orderings. The number of configurations with n cards revealed is P(52, n) C(52, n) = (52!)² /([ (52-n)!]² n!). So the largest n we need will be at least 37, and the expected number of cards we need to reveal will be at least some number between 36 and 37 (the calculation isn't too hard, but I'm too lazy at the moment). While I'm not sure we will be able to achieve a "perfect" strategy for 52 cards (although it seems quite simple for small n), it seems intuitively clear that we should be able to get quite close to perfect, enough to keep the expected value under 37 at any rate.