CMIMC 2017 Power Problem 11

Suppose you play with a deterministic algorithm. Prove that there exists some configuration by the first player for which you require at least 3 k+1 guesses.