# Relatively prime numbers

Can you fill in the circles with numbers such that:

• Each pair of circles connected by one line contains relatively prime numbers
• Each pair of circles connected by two lines do not contain relatively prime numbers
• You use one of every element from this set: $$\lbrace 20,21,22,23,24,25,27,28,30,32,33,35 \rbrace$$.

A Relatively Prime Number Set is a collection of integers in which each pair of numbers is coprime, meaning they share no common factors other than 1 (e.g. $$\lbrace9, 3, 1\rbrace$$, $$\lbrace10, 5, 2, 1\rbrace$$, etc.).

Source is from https://brainly.com/question/40900166

• I'm not exactly sure what you mean with the example sets there. $\{9,3,1\}$ is not a set of pairwise co-prime numbers, since the gcd of $9$ and $3$ is $3 \neq 1$. On the other hand, if you meant just that the gcd of all numbers in the set is $1$, then that's trivially true for any set that contains $1$ itself. But do we even care about multi-number sets of co-primes for the puzzle, if it's enough for each pair (connected by one line) to be individually co-prime? Commented Nov 28, 2023 at 15:15
• Me too, somebody decided to edit my question for some reason Commented Nov 28, 2023 at 16:07
• This is too late but this problem was cheating on USAMTS round 2. Discussion is allowed now. Commented Nov 29, 2023 at 15:51
• oh, i did not nkow this Commented Dec 3, 2023 at 20:15

## 1 Answer

23 is prime, so all its cell's connections must be single lines. There is only one such cell. Then, 30 has a common factor with every remaining number. It must be in a cell that has a double line connection to each adjacent cell (except possibly the 23 cell). There is only one such cell. Then, consider triangles of single line connections (which I've colored in red). Such a triangle must have at least one number that is not a multiple of 2 or 3 (otherwise there would be two multiples of 2 or two multiples of 3 which would need a double line connection). Only 3 such numbers exist: 23, 25, and 35. Since there are only three, each triangle must have only one of these numbers. The other two numbers in each triangle, then, must be one multiple of 2 and one multiple of 3. Thus, a number that is a multiple of 2 and 3 can't be on one of the triangles. Only one remaining cell is not on a triangle. It must contain 24.

Consider the cells connected to 24 by single lines. They can't be multiples of 2 or 3, so they are 25 and 35. There is another cell adjacent to both of these. It has a single connection to one and a double connection to the other. Anything that has a common factor with 25 would also have a common factor with 35, but the reverse is not true because 35 is also divisible by 7. Thus, the double connection must be to the 35 cell (which gives us the 25 cell by process of elimination). We know the cell connected to 25 and 35 is divisible by 7, so either 21 or 28.

The remaining cells can be divided into a group of 5 on the left joined in a single-line connection chain, and a pair in the upper right joined by another single-line connection (shown below in blue). Given that the remaining odd numbers are all multiples of 3, in each chain, even-odd parity must alternate. Because we have more even numbers remaining, we know the chain on the left must be even-odd-even-odd-even. Thus, the that cell we previously concluded was a multiple of 7 must be 21 by parity.

28 can't have a single-line connection to 35 or 21. There is only one such cell. 20 can't have a single-line connection to 35 or 25. There is only one such cell. Then consider the top-middle cell. It is connected on the left to a multiple of 2 (but not 3) and a multiple of 3 (but not 2) by double-line connections. Since those connections can't both be realized by the same factor, and we don't have a multiple of 6 remaining, the only factor we have to work with among the remaining numbers is 11. Thus, this cell and the cell to its lower-left are 22 and 33.

We know which of 22 and 33 is which by the previous parity argument. The remaining two numbers can then also be filled in by parity, completing the arrangement.