Track / Stage 8 / 22 of 180 #1722 of 2000

Problem 1722

IMO Shortlist mid-range; USAMO P2/P5

Combinatorics Difficulty 8.1 Prove it Baltic Way shortlist · Baltic Way

Let $b_i$ , $c_i$ , $0 \le i \le 100$ be two sequences of positive integers with two exceptions: $c_0 = 0$ , $b_{100} = 0$ . Several villages are connected by roads, each road connects two villages which are called neighbours and has length $1$ km. Roads do not intersect each other, but can pass over/under each other. The distance between two villages $X$ and $Y$ is the length of the shortest path between them. In this country the maximal distance between two villages equals $100$ km and for every pair of villages $(X,Y)$ (the case $X = Y$ is allowed) the following condition holds: if distance between $X$ and $Y$ is $k$ km, then there are exactly $b_k$ ( $c_k$ , respectively) neighbours of $Y$ that are $1$ km further from (closer to, respectively) $X$ than $Y$ . Show that the number
$\frac{b_0 b_1 \dots b_{99}}{c_1 c_2 \dots c_{100}}$
is an integer.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

Let $z$ be an arbitrary village, $S_i(z)$ be the set of villages at distance $i$ from $z$ , and $k_i$ be the number of elements in $S_i(z)$ . Then the sequence $k_i$ does not depend on $z$ !
We prove this statement by induction on $i$ . We will show also that $k_{i+1} = k_i \cdot \frac{b_i}{c_i}$ . Clearly, $k_0 = 1$ . This is the base of induction. To prove the step of induction we count roads between $S_i(z)$ and $S_{i+1}(z)$ in two ways: we can choose the village $x$ in $S_i(z)$ and the road to $S_{i+1}(z)$ by $k_i b_i$ ways; from the other hand we can choose the village $x$ in $S_{i+1}(z)$ and the road to $S_i(z)$ by $k_{i+1} c_{i+1}$ ways. Therefore $k_{i+1} c_i = k_i b_i$ .
The problem statement follows immediately from this formula.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.