TITLE: Each integer has one of three colors. Prove that there exists two distinct integers of the same color with the difference between them being a square.
QUESTION [3 upvotes]: Each integer has one of three colors. Prove that there exists two distinct integers of the same color with the difference between them being a square.

Pretty sure this can be proved using the pigeon hole principle, but I don't know how to prove it?

REPLY [1 votes]: Consider the numbers: 0, 9, 16, 25. Numbers 0 and 25 must have different colors (say, red and green), and since 9 and 16 are each a perfect square distance from both 0 and 25, both 9 and 16 cannot be red nor green and so must have the same third color. From this we can conclude that any two numbers that differ by 7 (as in 9 and 16) must have the same color. Finally by looking at a sequence of numbers that differ by 7, all of which must have the same color, we eventually find a pair that differ by 49, leading to a contradiction.
{"set_name": "stack_exchange", "score": 3, "question_id": 4070656}