Colour the positive integers without making a blue equation

Question

This puzzle is related to How do we find the numbers? but has a slightly more striking solution in my opinion. It is also based on one of my MathsSE answers.

What is the least number of colours you need to colour the positive integers such that there are no three not necessarily distinct same-coloured numbers $(x,y,z)$ satisfying $x+y=3z$?

---

The sufficiency of four colours has been proven. It remains to show that three is insufficient – and this can be done the usual way of trying to colour the first several integers and arriving at some kind of contradiction.

Answer 1

The answer is

4

Sufficiency:

Consider the colouring

Given a number represent it in base 3. Count trailing zeros, multiply the parity by two and add the least significant nonzero digit. The resulting number (1-4) is the colour.

Indeed if x and y are the same colour it is readily verified that z must have exactly one fewer trailing zero than the smaller number of trailing zeros between x and y.

Note that this is not the only way. For an alternative and arguably slightly simpler construction see comment by @EdwardH

Necessity:

Warmup: by-hand proof of a weaker bound to illustrate the technique.

Choosing x = z we see that pairs a,b=2a must have different colours and equating x and y that pairs 3a=2b must have different colours. Using all permutations of these two we see that 6 must be coloured differently to 3,4,9 and 12. But using x=3,y=9,z=4 we see that in addition to the colour of 6 at least two more are required.

Full proof: Computer generated, human readable.

Shown are 7 macro columns each consisting of four micro columns. The micro columns are the three colours plus annotation. Each row corresponds to painting one more number (top-to-bottom).

Annotations:

• f=forced: this number could only be given the given colour.

• w=wlog: at least two colours weren't used yet; pick one without loss of generality

• b=branch: for this number at least two colours are still possible; the other branches are traced in new macro columns

• c=contradiction: for this number no colour is available anymore.

As all branches end with contradictions three colours are not sufficient.

    18|  |   w
    24|  |   b                            |24|   w
     6|  |   b                | 6|   w    |  |12 f
      | 8|   w                |  |12 f    |  |36 f
      |  |12 f                |  | 9 f  16|  |   f
      |  | 4 f                |27|   f    | 8|   f
      |  |16 f                |  |54 f   6|  |   b                | 6|   b
      |36|   f                |36|   f    |  | 4 f                |  | 9 f
      |  |54 f                |  |14 f    | 2|   f                |27|   f
      |27|   f                |30|   f    |  | 3 f              54|  |   f
    81|  |   f              15|  |   f    | 9|   f                |30|   b    |  |30 b
      |30|   b    |  |30 b  21|21|21 c    |32|   f              15|  |   f  45|  |   f
    20|  |   f    |14|   f    |  |        |  |48 f                |  |10 f    |  | 3 f
    22|  |   f    |  |10 f    |  |      72|  |   f                |  |11 f   4|  |   f
      |32|   f  15|  |   f    |  |        |30|   b    |  |30 b  17|  |   f  11|  |   f
      |44|   f    |  | 7 f    |  |      13|  |   f  11|  |   f  19|  |   f    | 5|   f
      |  |46 f    | 9|   f    |  |        | 5|   f  22|22|22 c  20|  |   f   7|  |   f
      |  |48 f    |11|   f    |  |      20|  |   f    |  |        |23|   f    |  |10 f
      |34|   f    |  |13 f    |  |        |  |10 f    |  |        |25|   f  17|17|17 c
      |  |14 f    |  |21 f    |  |        |  |11 f    |  |        |26|   f    |  |
      |10|   f  33|33|33 c    |  |      19|19|19 c    |  |        |  |13 f    |  |
    21|  |   f    |  |        |  |        |  |        |  |       3| 3| 3 c    |  |
      |  |15 f    |  |        |  |        |  |        |  |        |  |        |  |
      | 9|   f    |  |        |  |        |  |        |  |        |  |        |  |
      |  |13 f    |  |        |  |        |  |        |  |        |  |        |  |
    26|  |   f    |  |        |  |        |  |        |  |        |  |        |  |
    72|72|72 c    |  |        |  |        |  |        |  |        |  |        |  |
 

Answer 2

How many?

4 is enough.

Why (smaller cases)?

There are two trivial cases about $x+y=3z$:

$x+2x=3x$
$3x+3x=3*2x$

They mean that $x$ and $2x$ must be of different colors. Same for $2x$ and $3x$.
............................................................................
If we have 2 colors, $3x$ and $4x$ must have the same color as $x$. We get this:

$1, 3, 4, 9, 12$: red
$2, 6, 8, 18$: blue

However, $3+9=3*4$, so it's impossible.
............................................................................
If we have 3 colors, 1 is red and 2 is blue. 3 and 4 can be any color, but (at least) two of the four must be of the same color.

- If 1 and 3 have the same color, the same relationship goes for any $x$ and $3x$.

$1, 3, 9$: red
$2, 6, 18$: blue

But then 4 can't be red like in the previous case (blue or yellow), and 8 can't be blue in the expanded equation (red or yellow). 4 can't be blue either, so it must be yellow. Because of that, 8 can't be yellow, so it's red. Also, the relationship between 3 and 8 is the same as 6 and 16 blue, making 16 also blue. Then again, $1+8=3*3$ means this option is impossible.

- If 1 and 4 have the same color, the same relationship goes for any $x$ and $4x$.

$1,4$: red
$2,8$: blue

No $x$ and $3x$ can have the same color, so 3 isn't red (blue or yellow) and 6 isn't blue (red or yellow). 6 isn't red either, so it must be yellow. For this reason, 3 can't be yellow either, making it blue:

$1,4$: red
$2,3,8,12$: blue
$6$: yellow

5 and 7 must not be blue because $12+3=3*5$ and $7+2=3*3$ (red or yellow). They can't both be red at the same time either, because $7+5=3*4$. 9 isn't blue because 3 is, and isn't yellow because 6 is, so it's red. 3 being blue creates a contradiction where 2 and 3 are both blue though.

- If 3 and 4 have the same color different from both 1 and 2:

$1$: red
$2$: blue
$3,4$: yellow

5 can't be yellow because $4+5=3*3$ (red or blue). 6 can't be blue (red or yellow). 8 can only be red, so as is 6. 9 and 12 can only be blue. If 12 is blue, so is 15, but $12+15=3*9$ creates a contradiction.

The working case:

Paint any $3k+1$ number red, and any $3k+2$ number blue. Then among the multiples of 3, paint any $3(3k+1)$ yellow and any $3(3k+2)$ green. Then go back to red-blue on the next turn. Rinse and repeat.