7
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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"

$\endgroup$
  • 1
    $\begingroup$ What about $K = 7$? $\endgroup$ – Improve Mar 6 '16 at 16:47
  • 4
    $\begingroup$ 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. $\endgroup$ – f'' Mar 6 '16 at 17:06
  • $\begingroup$ 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. $\endgroup$ – Zerris Mar 6 '16 at 19:52
3
$\begingroup$

$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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.