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

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?

Answer 1

Just a guess. I guess you need to find 4 distinct integers $a \gt b \gt c \gt d$ such that the difference between every 2 of them is a square. Then since you have just 3 colors, that would prove the statement. I just don't know yet how easy it is to find such 4 integers. Maybe one can construct something using certain Pythagorean triples, or some squares of numbers, and also the number 0.

But if this problem is about pigeon hole principle, that seems like the most obvious idea.

EDIT:

Yeah, this idea works here. Here are 4 such integers:

$697^2, 185^2, 153^2, 0^2$

The difference between any two of them is a square.
One can show more examples. But one example is enough for this problem.

Here are a few more examples:

$697^2, 185^2, 153^2, 0^2$
$697^2, 680^2, 672^2, 0^2$
$925^2, 533^2, 520^2, 0^2$
$925^2, 765^2, 756^2, 0^2$

Answer 2

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.