1

Is it possible to place $1995$ different natural numbers on along a circle such that for any two of these numbers, the ratio of the greatest to the least is a prime?

I'm confused about what does it mean for a natural number to be "along" a circle? As far as I know the circle of radius $r$ centered at $(h,k)$ is characterized by $(x-h)^2+(y-k)^2=r^2$ and the points have too coordinates always that is they're tuples. How does one assign a single natural number to a spot on a cirlce in the plane?

Walker
  • 1,404
  • a point is on the circle if it is on the boundary. You're overcompicating it. Just try a few like the vertices of a hexagon. The only relevant thing is the numbers are in a row and you think of the last one as adjacent to the first one. [and the first adjacent to secnd, etc..] – coffeemath Sep 27 '22 at 20:00
  • Important question: Can the numbers be any positive integers at all, or must they be just those from 1 to 1995? I'd think any at all to make the question interesting. – coffeemath Sep 27 '22 at 20:05
  • Almost certainly any at all, @coffeemath It's certainly possible to answer for arbitrary integers. – Thomas Andrews Sep 27 '22 at 20:07
  • 1
    Hint: Write the number of prime divisors for each number (counting repetitions) around the circle. – Thomas Andrews Sep 27 '22 at 20:11
  • @coffeemath the problem I have with this is that the points are tuples of the form $(x,y)$ not single natural numbers. – Walker Sep 27 '22 at 21:14
  • 1
    @SleepWalker NO they are not tuples. The numbers mentioned are "1995 natural numbers". Each one is a single number, like 1048. None of them have two coordinates. Your attempt to use (x,y) coordinates is totally irrelevant to the problem. Suppose there are only 6 numbers. I could put them going counterclockwise around the circle as 23, 45, 18, 21, 29, 62 where the 62 is next to the beginning 23 in the circular arrangement. It does not help your problem one bit to give (x,y) coordinates to these six natural numbers. – coffeemath Sep 27 '22 at 21:33
  • It feels very odd that I'm dealing with geometric object in the plane and considering single numbers placed on it. @coffeemath – Walker Sep 27 '22 at 21:43
  • @SleepWalker Have you had a course in intro group theory? If so the circle idea is unnecessary, it can be replaced by the concept of a cyclical permutation. – coffeemath Sep 27 '22 at 22:27
  • @SleepWalker You are not dealing with a geometric object in the plane. Say you are solving some cubic equation; do you need to draw a figure of cube in the process? No. Same thing here. – Ivan Neretin Sep 27 '22 at 22:40
  • Think about it like $1995$ people are sitting at a round table – TheBestMagician Sep 28 '22 at 00:29

1 Answers1

3

There's really no geometry at play here, 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.

TheBestMagician
  • 2,864
  • 2
    On the other hand, any even number of numbers should be achievable, for example by starting with $1,2,4,8,\ldots,2^n$, then going up to $2^n \cdot 3$, then down to $\ldots, 12, 6, 3$, then back to 1. – Daniel Schepler Sep 28 '22 at 16:49