First round – City competition

$$4(2^{m-1}+1)(2^m+1)(2^{2m-1}+2^m+1)=(p-1)(p+1).$$ Since $p$ is odd, the right-hand side is the product of two consecutive even numbers, so it is divisible by 8. The left-hand side is not divisible by 8, unless $m=1$. It follows that the only solution is $(p,m,n)=(11,1,3)$. 3.3. Let $G$ be the set of all cities in the country. We call a pair $(A,Z)$, where $A$ and $Z$ are disjoint subsets of $G$ good if all cities in the set $A$ can be visited using only bus such that no city is visited twice and all cities in the set $Z$ can be visited using only train such that no city is visited twice. Let $(A,Z)$ be a good pair such that the set $A\cup Z$ has the maximum number of elements. If we prove $A\cup Z=G$, the statement of the problem holds. Let us assume the opposite, i.e. there is a city $g$ which isn't from $A$ nor $Z$. Without loss of generality we can assume that $A$ and $Z$ are non-empty, because otherwise we can transfer any city from a non-empty set to an empty one. Let $n$ be the number of cities in the set $A$, and $m$ the number of cities in the set $Z$. Let us arrange the cities from $A$ in the series $a_1,\dots ,a_n$ such that every two consecutive cities in that series are connected by a direct bus line. Also, let us arrange the cities from $Z$ in the series $z_1,\dots ,z_m$ such that every two consecutive cities in that series are connected by a direct train line. Since we assumed that the pair $(A,Z)$ is maximum, the cities $g$ and $a_1$ have to be connected by train (otherwise the pair $(A\cup \{g\},Z)$ would be a good pair whose union would have more elements than $A\cup Z$), and $g$ and $z_1$ have to be connected by bus (otherwise the pair $(A,Z\cup \{g\})$ would be a good pair whose union would have more elements than $A\cup Z$). The cities $a_1$ and $z_1$ have to be connected by bus or by train. --- ## Croatia2016_booklet — Page 19