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

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

ReplyDeleteSolution:

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

Let us call our guy A.

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

here's another approach

ReplyDeletei 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

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

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

@ashishwrites you also assumed that the two people would form a group and play "together"

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