I found a question in 1001 Problems in Classical Number Theory by Jean-Marie De Koninck et. al.(1) that seems to be in error. Question #30 reads:
(30) Given 51 arbitrary positive integers, show that one can always find two of them whose difference is 50.
This seems obviously false, because, for example, the sequence { 100, 200, 300, ..., 5100 } will never contain two numbers that differ by 50.
The solution given in the text seems to hint at their actual intent:
(30) There are exactly 50 possible remainders when we divide the numbers by 50, and these remainders are the numbers: 0, 1, 2, ..., 49. Since we have 51 integers and only 50 possible remainders, it follows that using the Pigenhole Principle, there are at least two numbers amongst these 51 integers having the same remainder. Then, the difference of these two integers has 0 as a remainder and is therefore divisible by 50.
My question is simply: is the textbook question invalid/wrong? (i.e., am I correct in believing there is no such sequence?) If the question is valid, can you provide an example of a valid sequence that satisfies the question? If I'm right and the question is invalid, confirmation will suffice, although any additional evidence or explanation would be appreciated.
If I may indulge in brief speculation, I would guess that, based on their solution, the authors probably intended the question to read:
... one can always find two of them whose difference is divisible by 50.
But I'd be most grateful for someone else's interpretation of the question and the solution.
(1). ISBN 978-0-8218-4229-9
Answer
community wiki post so the question can be closed
You are correct. The authors intended to state that in any set of $51$ positive integers, there must be two whose difference is divisible by $50$.
No comments:
Post a Comment