Browse · MathNet
PrintJapan Mathematical Olympiad Initial Round
Japan counting and probability
Problem
Suppose we assign one of positive integers satisfying to each of the 8 vertices of a regular octagon. How many ways of assigning these numbers are there, which satisfy the following 2 conditions?: assigned numbers are all distinct. any pair of numbers assigned to adjacent vertices are relatively prime. Regard two assignments of 8 numbers to be distinct if one is obtained from the other by rotation or flipping of the octagon.
Solution
576 ways Since pair of even integers are not relatively prime, any pair of adjacent vertices cannot both be occupied by even numbers. Hence even and odd numbers must be assigned to vertices alternately. So, the assignment of numbers must be carried out as in the figures 1 or 2 below.
figure 1 figure 2
There are ways of assigning even numbers 2, 4, 6, 8 to the vertices marked even in the figure 1, and the same is true for the vertices in figure 2, and all these assignments have to be considered distinct. Therefore, there are 48 ways of assigning the even numbers to the vertices of the octagon to satisfy the requirement of the problem.
Now, after we decide on the assignments of even numbers, we have to consider the ways of assigning odd numbers to the vertices marked odd in figures 1 and 2 in such a way to satisfy the requirements of the problem. Since 3 and 6 are not relatively prime, 3 has to be assigned to a vertex not adjacent to a vertex which has 6 as the assigned number, and therefore, there are exactly 2 vertices to which the number 6 can be assigned. On the other hand, all the even-odd pairs of numbers in between 1 through 8 except the pair (3, 6) are relatively prime, remaining odd numbers 1, 5, 7 can be assigned to the remaining vertices marked odd in any order,
which means that there are ways of assigning these numbers. Therefore, there are altogether ways of assigning the numbers 1, 2, ..., 8 to the vertices of the octagon in such a way to satisfy the conditions of the problem.
figure 1 figure 2
There are ways of assigning even numbers 2, 4, 6, 8 to the vertices marked even in the figure 1, and the same is true for the vertices in figure 2, and all these assignments have to be considered distinct. Therefore, there are 48 ways of assigning the even numbers to the vertices of the octagon to satisfy the requirement of the problem.
Now, after we decide on the assignments of even numbers, we have to consider the ways of assigning odd numbers to the vertices marked odd in figures 1 and 2 in such a way to satisfy the requirements of the problem. Since 3 and 6 are not relatively prime, 3 has to be assigned to a vertex not adjacent to a vertex which has 6 as the assigned number, and therefore, there are exactly 2 vertices to which the number 6 can be assigned. On the other hand, all the even-odd pairs of numbers in between 1 through 8 except the pair (3, 6) are relatively prime, remaining odd numbers 1, 5, 7 can be assigned to the remaining vertices marked odd in any order,
which means that there are ways of assigning these numbers. Therefore, there are altogether ways of assigning the numbers 1, 2, ..., 8 to the vertices of the octagon in such a way to satisfy the conditions of the problem.
Final answer
576
Techniques
Enumeration with symmetryColoring schemes, extremal argumentsGreatest common divisors (gcd)