PROJECT EULER · #0644
Squares on the Line
Sam and Tom are trying a game of (partially) covering a given line segment of length
As illustrated below, the squares may be positioned in two different ways, either "straight" by placing the midpoints of two opposite sides on the line segment, or "diagonal" by placing two opposite corners on the line segment. Newly placed squares may touch other squares, but are not allowed to overlap any other square laid down before.
The player who is able to place the last unit square onto the line segment wins.
With Sam starting each game by placing the first square, they quickly realise that Sam can easily win every time by placing the first square in the middle of the line segment, making the game boring.
Therefore they decide to randomise Sam's first move, by first tossing a fair coin to determine whether the square will be placed straight or diagonal onto the line segment and then choosing the actual position on the line segment randomly with all possible positions being equally likely. Sam's gain of the game is defined to be 0 if he loses the game and
For example, if
Choosing
Being interested in the optimal value of
You are given
Find
Write-up coming later
The complete problem is available here. An approach, code, and answer will be added later.