Bottom Dollar

Source: +Plus Magazine

Problem: You're in a glitzy casino in Las Vegas. Having tried your hand at everything from Roulette to Black Jack, you've managed to lose most of your money and have only one dollar left.

What's worse, with all the champagne and everything, you've misbehaved and the management has made it very clear that you're not allowed any more games. But you need two dollars to get the bus back to the hotel.
Two shady-looking characters at the bar offer you a game: they have a pile of 15 stones. Each of you in turn is to take your choice of 1, 2, 3, 4 or 5 stones from the pile. The person who takes the last stone gets one dollar from the person who drew previously, and the third person neither wins nor loses.
You're to draw first. You're sure that both of the other players will play to their best personal advantage and won't make any mistakes. Should you agree to play the game?

Update(23/01/10):
Solution: Posted by Giridhar Addepalli (CSE, IITK alumnus and Yahoo! Sr. Software Engineer) in comments!!
Clarification: The two shady people do not form a group. They play to their best personal advantage.

Comments

  1. NG6:59 PM, January 20, 2010

    I THINK our man ( lets call him slim ) should not play.

    Solution:
    Slim clearly wont play if he has to pay his dollar. Also he wont play if he neither has to pay one nor gets one ( Afterall in time he wastes playing this , he could woo a pretty girl at counter to lend him a ride ) . So he plays only if he can win.

    Now our shady gentlemen know that if slim plays - he tries to win only (& is not interested in any draw for him ) So our gentlemen essentially form a team (lets call it shady ). So we have a match between slim & shady. Slim can take 1 to 5 coins at once , while shady can take 2 to 10 coins at once. ( they would also take 1 if only one coin was left ).

    So in maths , we have a finite , impartial nim with Slim having move set 1 to 5 & shady having move set 2 to 10 (& 1 if needed ). Every position of game is either winning or losing & by inductive way we can find which positions are winning for whom.

    As it happens 15 is not a winning position for Slim ( Whatever he chooses , he would get 6 in his next turn & then he would lose ).

    ReplyDelete
  2. Giridhar9:51 AM, January 21, 2010

    Let us call our guy A.
    He can win, i guess.

    L: looses
    W: Wins
    I: Indifferet. ( neither wins nor looses )
    S = Stones left.

    If S <=5 , we know it is a winning position.
    If S = 6, whatever we do next guy will win.
    If S = 7, we pick 1 stone, just to remain indifferent. In this case A remains indifferent,B will loose, C will win.
    If 8 <= S <= 12 ,we pick (S-7) stones. In all these cases, A wins, B remains indifferent, C looses.
    if S = 13 , A looses, B wins.
    if S = 14, A can remain indifferent by picking 1 stone, B looses, C wins.
    if S = 15, A wins by picking 1 stone.

    ReplyDelete
  3. ashishwrites8:44 AM, January 22, 2010

    here's another approach

    i assert that shady wil be able to offer slim 6 stones no matter what slim does in his first turn

    15 -> x -> y -> 6

    now for every value of x(slim's effort) between 10 and 14, there is a value of y (shady's effort) which can lead to 6 for slim's second turn in which case he loses

    so there's no way slim can win

    ReplyDelete
  4. NG6:01 PM, January 23, 2010

    Girdhar's solution & mine solution differ because of our assumptions about game.

    He has taken it to be a strict combinatorial game (more precisely a general k player impartial subtraction nim )

    I on other hand have made assumptions about "behaviour" of slim (he wont play if he is drawing ) & that of shady ( that they essentially form a team ).

    & I think ,both are right under the domain of respective assumptions.

    ReplyDelete
  5. Pratik Poddar11:42 PM, January 23, 2010

    @ashishwrites you also assumed that the two people would form a group and play "together"
    @ashishwrites ... @Nikhil.. I have already stated the assumption that: "both of the other players will play to their best personal advantage"

    So, Giridhar's solution is correct. :)

    You can see a more detailed solution here

    Thanx.

    ReplyDelete

Post a Comment

Popular posts from this blog

Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions.  In total, Siddhant scores 25 out of 34.  Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34. Note that a) Vaibhav scores more than Siddhant b) Siddhant score better than Vaibhav in both individual topics -  5/6 > 20/25 and 20/28 > 6/9 How is it possible? 
Read more

Buying Dimsums

Source: Alok Goyal (Stellaris VP, Ex-Helion VC) puzzle blog Problem: A fast food restaurant sells dimsums in boxes of 7 and 3. What’s the greatest number of dimsums a person cannot buy. Generalize it for p and q where p and q are relatively prime. I loved the puzzle. Hope you enjoy it too.
Read more

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially)
Read more