Is it possible to place 1995 different natural numbers
along a circle so that for any two these numbers, the ratio of the greatest
to the least is a prime?
After searching on MSE,I saw this writen by TheBestMagicianwhich I don't understand.
just think of it like 1995
people sitting around a table. For the actual problem, there is a relatively neat trick. Prime factorize each number, then add up all the exponents. If the result is even, color the number red. Otherwise, color it blue. Then note that red people are adjacent to blue people and vice versa. However, because there are an odd number of people, such a coloring is impossible.
Why this make sense?Isn't 8/2=4,which 4 is not prime?
On the other hand, any even number of numbers should be achievable, for example by starting with 1,2,4,8,ā¦,2n
, then going up to 2nā 3
, then down to ā¦,12,6,3
, then back to 1. ā
Daniel Schepler
My question:
- Why adjacent numbers along a circle must have opposite parity?
- What is the connection between 1995 people sitting around a table and the italic question?
Any help ? Thanks:)
Best Answer
To give a bit more of an explanation:
Consider the numbers $a$ and $b$ with prime factorisations $a = p_0^{a_0} p_1^{a_1} \ldots p_n^{a_n}$ and $b = p_0^{b_0} p_1^{b_1} \ldots p_n^{b_n}$ (assume that we use a set of primes that covers both numbers, so it's possible for some of the $a_i$ and $b_i$ to be zero). If their ratio $\frac{a}{b}$ is prime, then that means that $a_i = b_i$ for almost every $i$, except for one case where $a_i = b_i + 1$. Then that means if we consider the sums $a_0 + a_1 + \ldots + a_n$ and $b_0 + b_1 + \ldots + b_n$, they differ by 1. This also means that if $b$ is odd then $a$ is even, and vice versa. (And notice that the zero exponents don't affect this, so we can include or exclude them as we please.)
For example, if we look at $a = 10800$ and $b = 3600$, notice that $a = 2^4 3^3 5^2$ and $b = 2^4 3^2 5^2$, so $\frac{a}{b} = 3$ is prime, and $4 + 3 + 2 = 9$ while $4 + 2 + 2 = 8$ if we look at the sums of the exponents.
Now looking at the given problem, let us assume that it is possible to arrange 1995 numbers in a circle such that every adjacent pair has a prime ratio between them. From what we've shown above, that means that if one of the numbers has an even sum of exponents of its prime factors, it must be located between two numbers with an odd sum of exponents. To use TheBestMagician's notation, a number that gets coloured red will be placed between numbers that are coloured blue and vice versa.
But that's a problem. Let's label the numbers $n_1, n_2, \ldots, n_{1995}$ going clockwise around the circle from some point. If $n_1$ is red, then $n_2$ must be blue, then $n_3$ is red, and so on. Going all the way around, we'll get to $n_{1995}$ which will be red - but then it's next to $n_1$, which is also red, which isn't allowed. If $n_1$ is blue instead, we get the same problem - we're forced to put two numbers with the same "colour" together, meaning that the sum of their prime exponents has the same parity, meaning that their ratio is not a prime number.
So we reached a contradiction, which breaks the assumption we made that such an arrangement is possible, and hence no such arrangement exists, and in fact this is always true whenever there are an odd number of numbers being placed.
If we're placing an even number of numbers around the circle - say, 1996 - then it is possible as long as we choose our numbers carefully. Essentially we note that as we go clockwise we will either multiply by or divide by a prime number, and to ensure that we can loop back to the start we need to make sure that every number we multiply by gets divided back out at some point (e.g. if $n_2 = 7 n_1$, then further around the circle we will have $n_{i+1} = \frac{1}{7} n_i$).