Browse · MathNet
PrintVMO
Vietnam counting and probability
Problem
Given a regular 103-sided polygon with 79 vertices are colored red and the remaining vertices are colored blue. Denote to be the number of pairs of adjacent red vertices and to be the number of pairs of adjacent blue vertices.
a) Find all possible values of .
b) Determine the number of pairwise non-similar colorings of the polygon satisfying . 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.
a) Find all possible values of .
b) Determine the number of pairwise non-similar colorings of the polygon satisfying . 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 , if they form two blocks then , and similarly, if they form blocks then .
Besides, the number of red blocks is equal to the number of blue blocks, hence . This implies that all possible values of are for .
b) In order to have we need , 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 , respectively.
Let then . Hence, there are possible ways to choose such . In other words, 24 blue vertices can form 10 blocks in possible ways. Similarly, red vertices can form 10 blocks in ways.
Hence, there are 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 .
Besides, the number of red blocks is equal to the number of blue blocks, hence . This implies that all possible values of are for .
b) In order to have we need , 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 , respectively.
Let then . Hence, there are possible ways to choose such . In other words, 24 blue vertices can form 10 blocks in possible ways. Similarly, red vertices can form 10 blocks in ways.
Hence, there are 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 .
Final answer
a) All pairs (A, B) are (79 − k, 24 − k) for k = 1, 2, …, 24. b) The number of pairwise non-similar colorings with B = 14 is (C(23, 9) · C(78, 9)) / 10.
Techniques
Enumeration with symmetryColoring schemes, extremal argumentsCatalan numbers, partitionsRecursion, bijection