2014 HMMT November General Round Problem 5

Mark and William are playing a game with a stored value. On his turn, a player may either multiply the stored value by 2 and add 1 or he may multiply the stored value by 4 and add 3. The first player to make the stored value exceed 2^{100} wins. The stored value starts at 1 and Mark goes first. Assuming both players play optimally, what is the maximum number of times that William can make a move?

(By optimal play, we mean that on any turn the player selects the move which leads to the best possible outcome given that the opponent is also playing optimally. If both moves lead to the same outcome, the player selects one of them arbitrarily.)

Answers are checked by value, so any equivalent form is accepted: 1/2, \frac{1}{2} and 0.5 all count as the same answer.

Full credit goes to HMMT for authoring these problems. This problem is from the November 2014 contest; the official solution is available on the HMMT archive. HMMT is not affiliated with or endorsing TopsOJ in any way.