Competition problem — Combinatorics

Library / /24 of 41

Combinatorics Difficulty 5.6 AIME, harder Prove it Romania

The vertices of a prism are colored using two colors, so that each lateral edge has its vertices differently colored. Consider all the segments that join vertices of the prism and are not lateral edges. Prove that the number of such segments with endpoints differently colored is equal to the number of such segments with endpoints of the same color.

Solution

Denote $a$ the number of the vertices of the upper base which have the first color and $b = n - a$ the number of the vertices of the upper base which have the second color. Then the lower base has $b$ points with the first color and $a$ points with the second color.
The number of segments with endpoints differently colored and on different bases is $a^2 + b^2 - n$ .
The number of segments with endpoints differently colored and on the same base is $2ab$ .
So, the total number of segments with endpoints differently colored is $(a + b)^2 - n = n^2 - n$ , which is exactly half of the number of all the segments.

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.