3

Numbers $1,2,\dots,300$ are placed in a circle in some order. At most how many numbers can be divisible by the number to its right?

One way (probably optimal) is to place numbers so that $m$ is followed by $2m$ whenever possible. So the numbers are $1,2,4,8,...,256,3,6,12,...,192$ etc.

The numbers that are divisible by the number to their right are those $\leq 150$, so there are $150$ of them.

pi66
  • 7,164
  • Except that the odd numbers are also not divisible by their numbers on their right ($3$ is not divisible by $256$, $5$ is not divisible by $192$ and so on), and there are $75$ of those below $150$. So for your distribution there are only $75$ numbers that are divisible by the number on their right. – Arthur Jul 18 '16 at 17:32
  • I think you mean divisible by the number to its left. – Asinomás Jul 18 '16 at 17:37
  • 1
    @CarryonSmiling That depends on whether you mean our left or the number's left, and whether he is recounting them clockwise or anti-clockwise (i.e. which way is the number facing?), and so on. I'd just let it slide, as long as it's consistent. – Arthur Jul 18 '16 at 17:39
  • @arthur, But I think that in his arrangement the only numbers that are not divisible by their "right" neighbour are the odd ones. – Asinomás Jul 18 '16 at 17:40
  • 2
    @CarryonSmiling Ahh, yes, of course. any even number greater than $150$ is still happy because their half is to their 'right'. So all in all still $150$ happy numbers. – Arthur Jul 18 '16 at 17:44

1 Answers1

4

Call a number happy if it divides the number to its right and excited if it is divisible by the number to its left.

Notice that the number of happy numbers is equal to the number of excited numbers (since a number is happy if and only if the number to its right is excited).

Therefore we want to maximize the number of happy numbers.

Notice there are at most $150$ happy numbers since $151,152\dots 300$ can never be happy.

Your arrangement provides $150$ happy numbers, so we are done.

Asinomás
  • 105,651