Maths Olympiad Prep

Library / /45 of 71

Combinatorics Difficulty 5.2 AIME, harder Prove it United States

Problem:

In how many ways can you fill a 3×33 \times 3 table with the numbers 11 through 99 (each used once) such that all pairs of adjacent numbers (sharing one side) are relatively prime?

Solution

Solution:

2016

The numbers can be separated into four sets. Numbers in the set A={1,5,7}A=\{1,5,7\} can be placed next to anything. The next two sets are B={2,4,8}B=\{2,4,8\} and C={3,9}C=\{3,9\}. The number 66, which forms the final set DD, can only be placed next to elements of AA. The elements of each group can be interchanged without violating the condition, so without loss of generality, we can pretend we have three 11's, three 22's, two 33's, and one 66, as long as we multiply our answer by 3!3!2!3!3!2! at the end. The available arrangements are, grouped by the position of the 66, are:

When 66 is in contact with three numbers:

123
612
123

When 66 is in contact with two numbers:
612
1236 1 2 <br> 1 1 3 <br> 2 3 123

The next two can be flipped diagonally to create different arrangements:
612
1236 12
123
132312

Those seven arrangements can be rotated 9090, 180180, and 270270 degrees about the center to generate a total of 2828 arrangements. 283!3!2!=201628 \cdot 3!3!2! = 2016.

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.