Is it possible to place $1995$ different natural numbers along a circle so that for any two of these numbers, the ratio of the greatest to the least is a prime? I feel that my solution's wording and notation is awkward (and perhaps unnecessarily complicated), so please feel free to critique it:
HIDE: Click to reveal hidden text Suppose that we do have such a configuration $a_{1},a_{2},...a_{1995}$. WLOG, $a_{2}=p_{1}a_{1}$. Then \[\frac{a_{2}}{a_{3}}= p_{2}, \frac{1}{p_{2}}\] \[\frac{a_{3}}{a_{4}}= p_{3}, \frac{1}{p_{3}}\] \[... \] \[\frac{a_{1995}}{a_{1}}= p_{1995}, \frac{1}{p_{1995}}\] Multiplying these all together, \[\frac{a_{2}}{a_{1}}= \frac{\prod p_{k}}{\prod p_{j}}= p_{1}\] Where $\prod p_{k}$ is some product of the elements in a subset of $\{ p_{2},p_{3}, ...p_{1995}\}$. We clear denominators to get \[p_{1}\prod p_{j}= \prod p_{k}\] Now, by unique prime factorization, the set $\{ p_{j}\}\cup \{ p_{1}\}$ is equal to the set $\{ p_{k}\}$. However, since there are a total of $1995$ primes, this is impossible. We conclude that no such configuration exists.Problem
Source: Russia 95
Tags: ratio, number theory, prime factorization
_anant
17.12.2006 22:27
is your problem same as select any 1995 natural no.s in such a way so that if we take any 2 no.s then the ratio of the greatest to the least is a prime?Are you from russia ? Can you suggest me some good physics problems(by russian authors) books written / translated in english?Iam from india and cuurently using books by s.s.krotov and i.e. irodov
Phelpedo
17.12.2006 22:30
It's not quite the same: we can't select any two, we can only select adjacent ones.
theax
02.04.2011 22:06
can't you just say that consider three numbers, $a_1$, $a_2$, and $a_3$. Then $\frac{a_2}{a_1} =\, prime\, p$, so $a_2\,=\,a_1*p$ $\frac{a_3}{a_2} = \,prime\,q$, so $a_3\,=\,a_2*q$ $\Longrightarrow\,a_3\,=a_1*p*q$. Since $p$ and $q$ are primes, their product cannot be, so as long as you have n different natural numbers along a circle, where n >= 3, this problem is impossible. But I read somewhere that this problem is possible for all even n, though...
mavropnevma
02.04.2011 22:38
A more formal way is to take $\dfrac {a_{k+1}} {a_k} = p_k^{\varepsilon_k}$, where $a_k$ are $n$ distinct natural numbers around the circle, indexed by $0,1,\ldots,n-1$ in $\mathbb{Z}_n$ (so $a_n = a_0$), $p_k$ are primes, and $\varepsilon_k \in \{-1,+1\}$. Then $1 = \prod_{k=0}^{n-1} \dfrac {a_{k+1}} {a_k} = \prod_{k=0}^{n-1} p_k^{\varepsilon_k}$, therefore $\prod_{\varepsilon_k = -1} p_k = \prod_{\varepsilon_k = +1} p_k$. When $n$ is odd, this is impossible, since if we define by $\Omega(m)$ the number of the prime factors of $m$ (including multiplicities), we have $\Omega \left (\prod_{\varepsilon_k = -1} p_k\right ) = \left | \{k \mid \varepsilon_k = -1\} \right |$ and $\Omega \left (\prod_{\varepsilon_k = +1} p_k\right ) = \left | \{k \mid \varepsilon_k = +1\} \right |$, so $\left | \{k \mid \varepsilon_k = -1\} \right | = \left | \{k \mid \varepsilon_k = +1\} \right |$, but $\left | \{k \mid \varepsilon_k = -1\} \right | + \left | \{k \mid \varepsilon_k = +1\} \right | = n$. When $n$ is even, this is possible, with the easy example $a_{2k} = 1$, $a_{2k+1} = p$ prime.
parmenides51
26.08.2024 10:10
Is it possible to place $1995$ different natural numbers along a circle so that for any two of these numbers, the ratio of the greatest to the least is a prime?