Interview Questions II

A friend visited last weekend and after several beers challenged me to a numbers game. I liked it and thought it would make a good post – apparently he read it in a book of interview questions so there’s a good excuse for me to put it on here! The variant of the game we played went as follows, although there is some scope for changing the various numbers.

The first player says any number between 1 and 10. The second player then follows with a larger number, but it can be no more than 10 larger. So, if player one had said 4, player two could say any number between 5 and 15. Play continues in turn until someone gets to exactly 50, at which point they are the winner and play finishes.

There is actually a simple rule to play by to ensure victory, but the best way to proceed is to play a few games with someone first to get the feel of play. The solution is below, along with the rest of this post.

.

.

.

.

Solution: The winner is the first person to say 50. But, after playing a few times you’ll rapidly notice that another good number to arrive at is 39. If I say 39, the other player has to say a number between 40 and 49, any of which allow me to say 50 on the next move and win; so 39 is a winning number as well. But of course, I can ensure that I am the person who says 39 if I am also the player who says 28, by the same logic. I can ensure that I say 28 if I also say 17, and 6. So, if I can be the player that says 6, I can be certain of victory – and since this is possible on the first move, I can always win if I go first. Is this always the case? Have a think about the case where the victor is the first person to say 55, instead of 50!

This backwards-propagation of the result is a lot like option pricing (the link seems slightly tenuous, but they ‘feel’ rather similar to me). With an option, we know what the payoff will look like as a function of spot at expiry, but we don’t know what it looks like before then – the whole challenge is to propagate the final payoff backwards in whatever model we are using to the current date, which can be done using backwards pdes or expectations.

As an extra, if you are interested in a slightly more complicated variant, try the following game (again for two people). Arrange 15 matchsticks in rows to form a pyramid as follows:

I
I I
I I I
I I I I
I I I I I

On each turn, remove some matchsticks from a single row. You can remove as few or as many as you like, but they have to come from the same row. The winner is the person who removes the last match/matches.

[The game has been thoroughly solved, it’s called Nimh and a quick internet search should tell you everything you need to know, but I strongly recommend having a play with a friend first to try and get a feel for how it works!]