Sparsely's blog

How to prove 2007D?
By Sparsely, history, 4 months ago, In English

Link to problem, it is not that hard to find the solution, but I can't quite understand why the operation done by the players can always be sorted into one of the three types of the following when the root is unknown:

  • The first player sets the root in the first turn;
  • The first player sets one of the leaves in the first turn, while the second player sets the root (That is only valid when at least 1 leaf is unknown);
  • The first player sets one of the other nodes in the first turn, while the second player sets the root (That is only valid when the number of available nodes that is neither the root nor the leaf odd).

What I don't understand is that why can't one player choose the root or something else midgame, and why the condition for the third thing exists?

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
4 months ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

I talk about the proof in my video.

Assume that the root is unknown, all the leaves are unknown, and there are no internal unknown vertices.

If you lock down the root immediately, the best you can get is $$$L/2$$$. This strategy means that you divide the leaves equally with your opponent, except maybe the last leaf. So, you're not getting any advantage.

Let's see if it's possible to create an advantage during the game. To create an advantage, during the game, you must arrive at a situation where the number of 1s is strictly greater than the number of 0s. And then you immediately lock down the root to be equal to 0.

However, your opponent is smart enough to see this strategy, and as soon as you create a disbalance b/w number of zeroes, and number of ones, your opponent will simply take that advantage for themselves by locking the root at that point (since they are well aware that after root has been locked, the remaining leaves are distributed equally, so why not take the advantage if you are offered).

Hence, no player will risk creating an advantage. Therefore, there are only 2 strategies :

  • Lock down the root immediately, take $$$L/2$$$ leaves for yourselves. However, the opponent might take the last leaf.
  • Set any leaf to 0. Your opponent will cancel it out by setting another leaf to 1. If the number of leaves is odd, then at the end, the root and 1 leaf will remain. Since it is your turn, no matter what you color, the opponent will get an extra leaf for themselves.

In both these strategies, opponent takes that extra leaf. Can we prevent it? Yes, if you let opponent start the game, then you can take that extra leaf. But how do you do that? By wasting your turn on a non-terminal ?, but your opponent is smart, they can just mirror your moves on non-terminal ?, therefore, if the number of non-terminal ? is odd, they won't be able to mirror your last move, hence, they start the game, and you gain an advantage of the last leaf.

Now, what if there was an advantage at the start of the game, i.e, count of 1 is strictly greater than count of 0? We went through so much trouble for getting an advantage of just 1 leaf, so if we're getting it without doing anything, we should take it, otherwise the opponent will.

Hence, if root is unknown, and there is an advantage, you should lock down the root immediately.

If root is unknown, and there is no advantage, it doesn't mean that you have to lock down the root immediately, just cancel out your opponent's moves.

→ Reply