Maths Olympiad Prep

Library / /30 of 53

Combinatorics Difficulty 6.8 National olympiad Prove it Vietnam

Given a regular 103-sided polygon with 79 vertices are colored red and the remaining vertices are colored blue. Denote AA to be the number of pairs of adjacent red vertices and BB to be the number of pairs of adjacent blue vertices.

a) Find all possible values of (A,B)(A, B).

b) Determine the number of pairwise non-similar colorings of the polygon satisfying B=14B = 14. Note that two ways of colorings are considered similar if one of them can be obtained from another with a rotation at the circumcircle of the polygon.

Solution

a) Clearly, there are 24 blue vertices. If all red vertices form a single block then A=78A = 78, if they form two blocks then A=77A = 77, and similarly, if they form kk blocks then A=79kA = 79 - k.

Besides, the number of red blocks is equal to the number of blue blocks, hence B=24kB = 24 - k. This implies that all possible values of (A,B)(A, B) are (79k,24k)(79 - k, 24 - k) for k=1,2,,24k = 1, 2, \dots, 24.

b) In order to have B=14B = 14 we need k=10k = 10, i.e. blue vertices form 10 blocks (and red vertices also form 10 blocks). Starting from a certain blue block, we label all blue blocks clockwise from 1 to 10. Let the numbers of vertices in blue blocks be x1,x2,,x10x_1, x_2, \dots, x_{10}, respectively.

Let yi=x1++xiy_i = x_1 + \dots + x_i then 1y1<y2<<y9<y10=241 \le y_1 < y_2 < \dots < y_9 < y_{10} = 24. Hence, there are (239)\binom{23}{9} possible ways to choose such y1,,y10y_1, \dots, y_{10}. In other words, 24 blue vertices can form 10 blocks in (239)\binom{23}{9} possible ways. Similarly, red vertices can form 10 blocks in (789)\binom{78}{9} ways.

Hence, there are (239)(789)\binom{23}{9}\binom{78}{9} possible ways to arrange 10 blue blocks and 10 red blocks alternating. Note that such arrangements are distinct by the rotation because 79 is a prime number. However, there are 10 ways to choose the starting block, hence the number of pairwise non-similar colorings is (239)(789)10\frac{\binom{23}{9}\binom{78}{9}}{10}.

\square

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 and solution reproduced as published; topic and difficulty added by this site.