Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
up vote 6 down vote accepted

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"

share|improve this answer
1  
What about $K = 7$? – Improve Mar 6 at 16:47
4  
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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