Divisible to the right in circle

123 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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.