# A list with many divisibilities

There is a list with $K$ distinct positive integers so that

• exactly 1 number in the list is divisible by $K$,
• exactly 2 numbers in the list are divisible by $K-1$,
• exactly 3 numbers in the list are divisible by $K-2$,
• ... ... ... ... ...
• exactly $K$ numbers in the list are divisible by $1$.

What's the largest possible value of $K$ under these circumstances?

-

## 2 Answers

The largest possible value is

K = 5

This can be shown by

Observing that K = 5 is possible (1, 2, 6, 12, 60 works)

Observing that for K = 6, we need five numbers divisible by 2 and four numbers divisible by 3. This means at minimum, three of our numbers must overlap and be divisible by 6, which is a failure because exactly one should be.

f" did a more eloquent job than me of extending this proof to all larger values of K:

"For K>5, only one number isn't divisible by 2 and two numbers aren't divisible by 3. That means at most three numbers aren't divisible by 6, but there need to be five that aren't." - f"

-
What about $K = 7$? – Improve Mar 6 at 16:47
For K>5, only one number isn't divisible by 2 and two numbers aren't divisible by 3. That means at most three numbers aren't divisible by 6, but there need to be five that aren't. – f'' Mar 6 at 17:06
Got dragged off to see a movie before I could extended my proof to all larger K. Yours is better written anyways, so I'm adding it instead. – Zerris Mar 6 at 19:52

$K-1$ of them are div. by 2 and $K-2$ are div. by 3, so at least $K-3$ must be multiples of both (div. by 6), which contradicts the info given in the question. That can only be avoided if $K<6$. A legit list is possible if $K=5$ - the numbers can be 1, 6, 12, 14 and 60 for example.

-