Lets Make A Circle!

Number Theory Level 3

What is the greatest integer value of $n$ such that we can arrange 9 distinct positive integers in a circle satisfying

each integer is less than 160,
the sum of any two non-adjacent numbers is a multiple of $n$ , and
the product of any two adjacent numbers is not a multiple of $n$ ?

The answer is 18.

1 solution

Jason Ding
Aug 16, 2017

Let us change all the numbers to be the remainder when it is divided by $n$ . Let us set each of these numbers to be $a_1, a_2, ... , a_8, a_9$ , respectively. We can see that none of the numbers will be 0, since then that number times the number adjacent to it would be a multiple of n. Now let us look at $a_1$ . We know that $a_1+a_3=a_1+a_4=a_1+a_5=a_1+a_6=a_1+a_7=a_1+a_8=n$ . Subtracting $a_1$ we get $a_3=a_4=a_5=a_6=a_7=a_8=n-a_1$ . Now if we look at $a_3$ , we get that $a_1=a_5=a_6=a_7=a_8=a_9=n-a_3=n-n+a_1=a_1$ . Since $a_5=n-a_1=a_1$ , we get $n=2a_1$ . Therefor we can see that $a_1=a_2=a_3=a_4=a_5=a_6=a_7=a_8=a_9$ . Let us set these numbers equal to $b$ , so that $n=2b$ . Because of the rule that adjacent numbers can't be a multiple of n, we get that $2b$ is not a factor of $b^2$ . Therefor b is odd. Now changing the nine numbers back to its original form, since none of them are the same number, then the smallest we can get them to be is $b, 3b, 5b, ... 15b, 17b$ which is equivalent to $n/2, 3n/2, 5n/2, ... 15n/2, 17n/2$ . Therefor, since $n$ is even and $17n/2<160$ , we get the the largest $n$ can be is 18.

Note: Be careful with your equality sign. Since you're working in modular arithmetic, it would be better to use $\equiv$ (\equiv) instead of $=$ .

As an explicit example, From $a_5 \equiv n - a_1 \equiv a_1 \pmod{n}$ , what we have is $2a_1 \equiv 0 \pmod{n}$ . We cannot conclude that $n = 2a_1$ , or even that $n$ must be even. For example, we could have $n = 1$ , and there is no corresponding integer $b$ that we can use.

In light of this, can you work through the solution carefully? Rigor in a solution can be extremely demanding, and it gets better with practice.

Calvin Lin Staff - 3 years, 9 months ago

Would it not work even though I said that $a_1, a_2, ... ,a_9$ were the remainders of the original numbers when divided by n?

Jason Ding - 3 years, 9 months ago

Well, consider what happens in that case. When $n=1$ , then the remainders are all 0. Do we still have $n=2b$ ?

The error that you made was in claiming that $2a_1 \equiv 0 \pmod{n} \Rightarrow n = 2a_1$ . All that we know is $n \mid 2 a_1$ .

As another example, we could have $n = 3, a_1 =3, a_2 = 6, a_3 = 9, \ldots$ . Again, the remainders are all 0, and we do not have $n = 2b$ . Of course, this violates the other condition that "product of any two adjacent numbers is not a multiple of $n$ ". You have to use this condition somehow in the proof.

Calvin Lin Staff - 3 years, 9 months ago

Lets Make A Circle!

The answer is 18.

1 solution

0 pending reports