HMMT November 2014 E5

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.)