Two concentric circles are divided by $n$ radii into $2n$ parts. Two parts are called neighbors (of each other) if they share either a common side or a common arc. Initially, there are $4n + 1$ frogs inside the parts. At each second, if there are three or more frogs inside one part, then three of the frogs in the part will jump to its neighbors, with one to each neighbor. Prove that in a finite amount of time, for any part either there are frogs in the part or there are frogs in each of its neighbors
Problem
Source:
Tags: combinatorics unsolved, combinatorics
22.02.2013 19:32
sahadian wrote: Two concentric circles are divided by $n$ radii into $2n$ parts. Two parts are called neighbors (of each other) if they share either a common side or a common arc. Initially, there are $4n + 1$ frogs inside the parts. At each second, if there are three or more frogs inside one part, then three of the frogs in the part will jump to its neighbors, with one to each neighbor. Prove that in a finite amount of time, for any part either there are frogs in the part or there are frogs in each of its neighbors In solving this problem we need to assume that $n\ge 3$. The problem statement implicitly assumes that each part has exactly $3$ neighbors--and the problem statement only makes sense if each part has exactly $3$ neighbors--and this is true only for $n\ge 3$. If this result were NOT true, then at all points in time there must exist a part with no frogs and with a neighbor with no frogs. That is, there must exist a pair of neighbors with no frogs. However, it is easy to see that once a pair of neighbors gain frogs, there will be one or more frogs there forever, as the allowed transitions can never cause a pair of neighbors with frogs to change to not have frogs. Thus for the result to NOT be true, there would need to be a specific pair of neighbors--call them $p_{1}$ and $p_{2}$--which never have frogs in them. We can then divide the set of parts into two disjoint groups. $A$ is the set of parts such that, for any given point in time, there will be some future point in time where $A$ has $3$ or more frogs. $B$ is the set of parts such that there exists a point in time such that after that point, $B$ always has $2$ or fewer frogs. Because there are $4n+1$ frogs but only $2n$ parts, it is easy to see $A$ must be nonempty. And if the result is NOT true, then $B$ is nonempty too--$p_{1}\in B$ and $p_{2}\in B$. Since the elements of $B$ always have $2$ or fewer frogs (after some initial interval), it is easy to see that the number of frogs in $B$ can only increase or stay the same. Hence each element of $B$ eventually ends up having a fixed number of frogs ($2$ or fewer) that never changes. Since $A$ and $B$ are both nonempty, there must be two parts that are neighbors with one in $A$ and one in $B$--let us refer to these neighbor parts as $a_{0}\in A$ and $b_{0}\in B$. After the number of frogs in $b_{0}$ becomes fixed, there must be some point where $a_{0}$ has $3$ or more frogs. This will result in a frog jumping to $b_{0}$ and increasing the number of frogs in $b_{0}$, which is a contradiction. Hence the assumption that the result doesn't hold must be false and we are done.