3

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?

vitamin d
  • 5,783
  • Here's a conjecture: starting coloring at $1$ (let it be black), then $2$ is arbitrarily one of the other two colors and it doesn't matter which for symmetry reasons, call it red. Then $3$ cannot be red, so it is either black or the third color (say, blue). I believe you cannot color past $25$ without reaching a contradiction. This makes some sense since at some point you'll have too many squares for differences and $25=5^2$. – Cameron Williams Mar 21 '21 at 14:12
  • To cast this in pigeonhole language, maybe my conjecture is that any sequence of $26$ consecutive positive integers cannot be $3$-colored by your rules. – Cameron Williams Mar 21 '21 at 14:15
  • 1
    In fact, by brute-force search, $28$ is the maximum number of consecutive integers that can be $3$-colored with the specified restrictions. – quasi Mar 21 '21 at 16:04
  • 1
    For an example with $28$ consecutive integers, here's a $3$-coloring that qualifies: $$ \begin{array}{|c|c|} \hline \text{color}&\text{positions}\ \hline 1& ;; 1, 4, 6, 9, 12, 14, 19, 24, 27 ;;;\ \hline 2& ;; 2, 5, 7, 10, 15, 17, 20, 22, 25, 28 ;;;\ \hline 3& ;; 3, 8, 11, 13, 16, 18, 21, 23, 26 ;;;\ \hline \end{array} $$ – quasi Mar 21 '21 at 18:33
  • Nice find @quasi! At least I was close . The cutoff being $28$ is certainly odd though. Maybe it's just in case your seeding is just right, forcing an extra $3$ for the number of colors. – Cameron Williams Mar 21 '21 at 19:29

2 Answers2

3

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$

peter.petrov
  • 12,568
  • Have you found an infinite family of examples? (just curious) – lulu Mar 21 '21 at 13:37
  • @lulu No, I just found a few examples of such tuples of 4 integers. – peter.petrov Mar 21 '21 at 13:38
  • Nice! After playing around with this problem brute force, I think you can even reach a contradiction with numbers on the order of 20. I've only traversed a few of the sequences though but it's held so far. There aren't too many options once you fix the colors for $1$ and $2$. – Cameron Williams Mar 21 '21 at 13:44
  • @CameronWilliams Not sure I follow. Could you elaborate a bit? I did use brute force but still... I required my 4 numbers to be 3 perfect squares and the number 0. Then I looked for all tuples which are of this kind and are below 1000 and these seem to be all the examples in this range. I guess if the requirements are relaxed one can find maybe even more examples. – peter.petrov Mar 21 '21 at 13:46
  • Oh sorry I meant just straight up coloring sequences. My bad. Your examples are great but I think you run into a contradiction for much smaller numbers. Proving that seems non trivial though. – Cameron Williams Mar 21 '21 at 13:56
  • After exploring some more, I think a tight upper bound is $25$, after which point I've hit contradictions. See my comments on the post itself. – Cameron Williams Mar 21 '21 at 14:18
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.

MarkP
  • 21