$ n$ people decide to play a game. There are $ n-1$ ropes and each of its two ends are in hand of one of the players, in such a way that ropes and players form a tree. (Each person can hold more than rope end.) At each step a player gives one of the rope ends he is holding to another player. The goal is to make a path of length $ n-1$ at the end. But the game regulations change before game starts. Everybody has to give one of his rope ends only two one of his neighbors. Let $ a$ and $ b$ be minimum steps for reaching to goal in these two games. Prove that $ a=b$ if and only if by removing all players with one rope end (leaves of the tree) the remaining people are on a path. (the remaining graph is a path.)
Problem
Source: Iranian National Olympiad (3rd Round) 2008
Tags: combinatorics proposed, combinatorics
pellomania
26.02.2014 11:39
Does anyone have a solution for this problem?
Pathological
13.11.2019 01:43
Here's a clearer reformulation of the problem statement.
On a tree, we define an operation as the following three-step operation. First, select a vertex $v.$ Next, pick a neighbor $w$ of $v$ and remove edge $vw.$ Finally, pick a vertex $t \neq w$ which isn't a neighbor of $v$, and add the edge $vt.$
Define a special operation as an operation above where $w, t$ are connected.
Define the tastiness of a tree to be the minimum number of operations we can do to reduce it to a path, and the uniqueness to be the minimum number of special operations we can do to reduce to a path. Show that a tree has equal tastiness and uniqueness if and only if the subgraph induced by its non-leaf vertices is a path.
The "if" direction is quite easy to check, the tastiness and the uniqueness are both equal to the number of leaves minus two. Let's now deal with the "only if" direction. Suppose that we have a tree where the subgraph induced by the non-leaves is not a path. Firstly, note that the tastiness of this graph is still the number of leaves minus two, because whenever there are more than two leaves we can remove an edge connecting to some vertex of degree $>2$ and attach it to a leaf. Let's now show that the uniqueness of this graph is strictly greater than the number of leaves minus two. The first observation is that any special operation can decrease the number of leaves of the tree by at most one. Right off the bat, this implies that the uniqueness is at least the number of leaves minus two. Here, equality can only be achieved if the number of leaves decreases every time. We know that there is a vertex $v$ with degree $\ge 3$ in the "defoliated" tree (leaves removed). Clearly, a special operation must result in the "defoliated degree" of $v$ decreasing (number of non-leaf neighbors), as this number is eventually $\le 2.$ This means that some edge was removed and attached to a non-leaf. The number of leaves does not decrease during this special operation, and so we know equality cannot be achieved. From the previous discussion, the "only if" direction is proven, and so the problem is solved. $\square$
everythingpi3141592
12.11.2023 18:11
Assume that we have $m$ leaves. We want $2$ leaves, which if we achieve then by handshake lemma we are done. Note that the number of leaves decreases by atmost $1$ in every turn, and infact if it is the first game we can make it decrease by $1$ every turn. However, if a vertex is connected to $3$ or more non-leaves then we cannot necessarily force this.