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$

2 Answers 2

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$
3
  • 1
    $\begingroup$ What about $K = 7$? $\endgroup$
    – Improve
    Mar 6, 2016 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, 2016 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, 2016 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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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