There are 1000 natural numbers a1, a2,...., a1000. Prove that of the numbers 3a1, 3a2,...., 3a1000, there must be 56 of them which have the same remainder when divided by 19.
(Hint: this is not a misprint. If the best you can do is prove the statement with 56 replaced by 53, then you're missing something.)