Armadillo and Badger are playing a game. Armadillo chooses a nonempty tree (a simple acyclic graph) and places apples at some of its vertices (there may be several apples on a single vertex). First, Badger picks a vertex $v_0$ and eats all its apples. Next, Armadillo and Badger take turns alternatingly, with Armadillo starting. On the $i$-th turn the animal whose turn it is picks a vertex $v_i$ adjacent to $v_{i-1}$ that hasn't been picked before and eats all its apples. The game ends when there is no such vertex $v_i$. Armadillo's goal is to have eaten more apples than Badger once the game ends. Can she fulfill her wish?
Problem
Source: 2023 Israel Olympic Revenge P1
Tags: olympic revenge, combinatorics, graph theory
25.06.2023 00:32
Armadillo cannot win, i.e. Badger can always start at a vertex $v_0$ and eat as many apples as Armadillo. Suppose there are $a_i\geq 0$ apples at vertex $i$. Let the payoff be $a_{v_0}-a_{v_1}+a_{v_2}-\ldots$, then Badger's aim is to maximise the payoff, while Armadillo's aim is to minimise it. Badger wins if the payoff is $\geq 0$. We first show when the tree is a path, with vertices $1,2,\ldots,n$. Let $x=a_1-a_2+a_3-\ldots$. If $x\geq 0$, then Badger will just pick $v_0=1$. Otherwise, $x<0$, so $a_2+a_4+a_6+\ldots>a_1+a_3+\ldots$. Let $k$ be the smallest even integer such that $a_2+a_4+\ldots+a_k> a_1+a_3+\ldots+a_{k-1}$. Such an integer exists, since $k$ being the largest even integer at most $n$ works. Badger picks $v_0=k$. If Armadillo picks $v_1=k-1$, then the payoff is $a_2+a_4+\ldots+a_k-(a_1+a_3+\ldots+a_{k-1})>0$. Otherwise, Armadillo picks $v_1=k+1$. By minimality of $k$, $a_2+a_4+\ldots+a_{k-2}\leq a_1+a_3+\ldots+a_{k-3}$, thus $a_k+a_{k+2}+\ldots-(a_{k-1}+a_{k+1}+\ldots)\geq x>0$. Hence the payoff is $a_k+a_{k+2}+\ldots-(a_{k+1}+a_{k+3}+\ldots)\geq a_k+a_{k+2}+\ldots-(a_{k-1}+a_{k+1}+\ldots)>0$, so Badger wins. Now suppose we have a general tree. First, we add a small random real number to each $a_i$, so that the $a_i$'s are now $\mathbb{Q}$-linearly independent. This is to break ties, and ensure that the payoff of different paths are distinct. Let $u_0$ be any leaf vertex. Suppose Armadillo and Badger plays optimally, with Badger starting at $u_0$. This game ends in some leaf vertex $u_1$. We call a path taken by the players if played optimally an optimal path. Now suppose Badger starts at $u_1$, and they both play optimally. This game ends in some leaf vertex $u_2$. Repeating, if Badger starts at leaf $u_k$, the game ends at leaf $u_{k+1}$. This gives a sequence of leaf nodes $u_1,u_2,\ldots$. Since the tree is finite, some leaf node must repeat, and hence this sequence is eventually periodic. So, for a suitable leaf node $u_1$, we may assume that we have a sequence $u_1,u_2,\ldots,u_k$ of distinct leaf nodes, for some $k$, and $u_{k+1}=u_1$. Claim: $k=2$. Proof: Suppose $k>2$, then the (unique) path from $u_2$ to $u_3$ breaks away from the path from $u_2$ to $u_1$ at some non-leaf vertex $w$. Suppose 2nd vertices of the paths from $v$ to $u_1,u_2,u_3$ are $w_1,w_2,w_3$. Suppose Badger starts from $w$ and Armadillo goes to $w_i$, then let the payoff be $p_i$. Note that the optimal path from $u_1$ to $u_2$ goes through $w$ and $w_2$ next, rather than $w_3$. Thus $p_2>p_3$. Also, the optimal path from $u_2$ to $u_3$ goes through $w$ and $w_3$ next, rather than $w_1$, so $p_3>p_1$. Hence $p_2,p_3>p_1$. This means that for any optimal path from $u_i$ to $u_{i+1}$ passing through $w$, on the turn at $w$, the player would prefer to pick $w_2$ or $w_3$ next (one of which is available), as opposed to $w_1$. Hence we can never return to $u_1$ along these optimal paths, a contradiction. $\square$ Let $P$ be the path from $u_1$ to $u_2$. We claim that if Badger starts at a vertex on $P$ and they play optimally, they do not leave $P$. If they do, from some vertex $w\in P$, then $w$ is not a leaf node. Let the 2 neighbours of $w$ in $P$ be $w_1,w_2$, closer to $u_1,u_2$ respectively. One of $w_1,w_2$ is available when at $w$, say $w_1$ is available. Then going to $w_1$ is optimal, since the optimal path from $u_2$ to $u_1$ goes from $w$ to $w_1$. Thus both players never leave $P$. Now if Badger starts at a vertex in $P$, the game is equivalent to the game on the path $P$, which we have already proven that Badger wins.
17.12.2023 17:19
NICE COMBI PROBLEM,quite hard for me. My solution:induct on the number of vertices.Only need to divide it into two cases: case1.the tree has a fork.Then apply the induction hypothesis.Need some careful discussion. case2.the tree is just one path.