Processing math: 100%

Problem #79

Strings

Laertes and Roxane play a game together by first drawing a string of Ls and Rs into the sand, and then taking turns removing any one of their respective letters (L for Laertes and R for Roxane) along with the substring to its right. The first player unable to make a move loses the game.

Consider the game played with the string L. If Laertes goes first, he removes the only L and passes to Roxane, who immediately loses, having no valid move. If Roxane goes first, she immediately loses again. So we see that Laertes always has at least one move's worth of an advantage over Roxane. We shall abbreviate this by saying the value of the string L is +1, from Laertes' point of view. Similarly, the string R has value -1. A game played with the two separate strings, L and R (denoted by L+R) can be shown to have the property that the first player to play loses the game. We shall call the value of such a string 0, and denote this as L+R=0.

Convince yourselves that LR = 0.5 (try playing the game with LR+LR+R). What is the value of LRL?

Contributed by Project Gauss

Solved by 104 users

Log in to submit answers.

Is something wrong?

Maintaining a collection of high quality questions is our top priority. If, however, you do find an error, report the problem and we'll make sure it is reviewed soon.