Track / Stage 5 / 310 of 400 #910 of 2000

Problem 910

AIME late

Combinatorics Difficulty 5.7 Prove it

10. In a city at every square exactly three roads meet, one is called street, one is an avenue, and one is a crescent. Most roads connect squares but three roads go outside of the city. Prove that among the roads going out of the city one is a street, one is an avenue and one is a crescent.

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

10. Let $\mathrm{n}$ be the number of squares. Let us split each road in two halves in the middle. Then the total number of halves of each type is even.
Let $x \_1, x \_2$ and $x \_3$ be the number of streets, avenues and crescents leaving the city. Then we have $n+x \_1, n+x \_2, n+x \_3$ halves of each kind. These numbers are even, hence $x \_1, x \_2, x \_3$ have equal parity.
But $x \_1+x \_2+x \_3=3$ , thus they are all odd, and $\$ x \_1=x \_2=x \_3=1$.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.