Trouble With Editorial

Problems and Contests
#1

So I’ve solved this problem, but I’m having some trouble understanding how a win is guaranteed is k^2 \geq n.
I understand that the proof in the official editorial follows a greedy strategy in which they always cut off the node that leads to the earliest fork, but this part is really confusing:

image
image1000×330 64.9 KB

If someone could explain this to me, that would be really helpful.

#2

Bump.

#3

(Hopefully simpler version? Didn’t read the whole editorial)

Let r be the number of rounds of the game that have occurred so far. Define

  • t_r to be the number of nodes that Daniel thinks Stjepan can move to next (if t_r=0, then the game ends. t_0 is the number of neighbors of node 1)
  • n_r to be the sum of the subtree sizes of these t_r nodes (with n_0=N-1).

Suppose Daniel marks the node out of the t_r with the maximum subtree size. It’s easy to show that using this strategy,

n_{r+1}\le n_r-n_r/t_r-(t_r-1)\le n_r-2\sqrt n_r+1.

So if n_r\le (k-r)^2, then n_{r+1}\le (k-r-1)^2. By induction it follows that n_k\le 0.

#4

So if n_r \leq (k-r)^2,

Where does this come from?

#5

The goal is to show that if n_0\le k^2 then the game finishes within k rounds.

#6

I see.
Also, what’s the intuition for the giant chain inequality in the middle of the proof?

#7

Consider a star-like tree with N=401 and 20 branches of length 20. You can check that n_r=(20-r)^2 for this graph, and that the game ends in 20 marks by Daniel and 19 moves by Stjepan.