-2

My problem is such:

On a circle there are $9$ distinct positive integers aranced in such a way that the product of two non-adjacent numbers in the circle is a multiple of $n$ and the product of any two adjacent numbers in the circle is not a multiple of $n$. Here, $n$ is a fixed positive integer. What is the smallest possible value for $n$?

I have found a solution if someone is willing to compare answers with mine. My answer came out to be 485100. Can someone please verify this?

Alex Ravsky
  • 90,434
Rick Shawn
  • 29
  • 1
    Where did this problem come from? – user7530 Dec 22 '14 at 20:18
  • 2
    @user7530 You probably saw the problem on Meta. It's from the ongoing Round 3 of USAMTS. To everyone: Please don't answer this question until the contest is over. – epimorphic Dec 23 '14 at 04:40
  • 1
    This was a problem asked during an open mathematical competition for the purposes of gaining an unnatural and unfair advantage. It had been locked and hidden. Although it is now unlocked, since the competition has passed, this is abusive and bad; and I downvoted. It is unfortunate, as the question is pleasant and the answer good. – davidlowryduda Jan 20 '15 at 07:29

1 Answers1

0

Denote the integers $n_1, \dots, n_9$.

For each $i = 1, \dots, 9$, the product $n_i n_{i+1}$ is not a multiple of $n$ (where the indices should be read modulo nine, i.e., $n_{10} = n_1$). Therefor, there exists a prime $p_i$ such that $p_i$ divides $n$ but $p_i$ does not divide $n_i$ or $n_{i+1}$.

If $p_i$ does not divide $n_j$ for some $j \neq i, i+1$, then neither $n_jn_i$ nor $n_jn_{i+1}$ is a multiple of $n$. Since $n_j$ is non adjacent to either $n_i$ or $n_{i+1}$, this is a contradiction. Hence, $n_i$ and $n_{i+1}$ are the only two integers not divisible by $p_i$.

Since there are nine pairs of adjacent integers, $n$ must have at least nine prime factors $p_1, \dots, p_9$.

On the other hand, $$n_i = p_1 \cdots \hat p_{i-1} \hat p_i \cdots p_9,$$ solves the problem with $$n = p_1 \cdots p_9.$$

The smallest such integer is $$n = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 23 = 223 092 870$$

Raclette
  • 613