Competition problem — Combinatorics

Library / /29 of 56

Combinatorics Difficulty 5.7 AIME, harder Prove it Singapore

Consider a polygon with $m+n$ sides where $m, n$ are positive integers. Colour $m$ of its vertices red and the remaining $n$ vertices blue. A side is given the number $2$ if both its end vertices are red, the number $\frac{1}{2}$ if both its end vertices are blue and the number $1$ otherwise. Let the product of these numbers be $P$ . Find the largest possible value of $P$ .

Solution

We first show that if two adjacent vertices have different colours, then swapping the colours of these vertices leaves $P$ unchanged. To see this, we only need to consider the four possible cases:

$RRBR$ , $BRBB$ , $RRBB$ , $BRBR$

which change to $RBRR$ , $BBRB$ , $RBRB$ , $BBRP$ .

The value of $P$ remains unchanged in each case. Thus by swapping the colours of adjacent vertices repeatedly, we get to the case where vertices of the same colour form one block. We now have $m-1$ edges whose end vertices are red and $n-1$ edges whose end vertices are blue. The value of $P$ is $2^{m-n}$ , a constant.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.