2011-07-07

A Simple Board Game

Bengt is in the mood for designing a game. But his imagination is not at its best. He was up late last night, and... well, never mind that. He's making a rather simple board game, one of those where you roll a die and walk along a path. As soon as you reach (or pass) the finish line, you win.
The game is played with a special k-sided die. Just to be completely clear, the die shows each integer from 1 to k inclusively, with equal probability. At the start of the game, you also get a few cards which do various things, but apart from that nothing much happens in the game. There's supposed to be several types of cards, but so far Bengt has only come up with one type. This card can be played right after you've rolled the die, and lets you double the number of steps. Thus, obviously, it should be played when you've rolled a rather high number. Bengt calls this card "the doubling card". He really is unimaginative today.

  1. Imagine you are n steps from the finish line, and you want to reach it in as few turns as possible. You have one doubling card. You roll the die. What is the minimum value on the die roll for which it is a good idea to use the card?
  2. What if you have c cards?
  3. If there are other players involved, and your goal is not to win as soon as possible but to beat the other players, does that affect the optimal strategy at all? If so, how?