9
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Lemma: Vs jr arrq a pbybef sbe gur fnzr guvat rkprcg k + l = m (a >= 3 cre "Ubj qb jr svaq gur ahzoref"), gura jr arrq ng zbfg a+1 pbybef sbe guvf (znc gur cerivbhf fbyhgvba gb gur zhygvcyrf bs 3, gura nqq bar zber pbybe sbe nyy gur bgure ahzoref). $\endgroup$
    – Ed Murphy
    Feb 19, 2023 at 16:38

2 Answers 2

7
$\begingroup$

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    |  |        |  |        |  |        |  |        |  |        |  |
 

$\endgroup$
3
  • $\begingroup$ Sufficiency: rot13(pbybevat onfrq ba gur yrnfg fvtavsvpnag abamreb qvtvg va onfr svir) should also work. $\endgroup$
    – Edward H
    Feb 20, 2023 at 2:04
  • $\begingroup$ @EdwardH I checked that with a small script and it does work. At least up to 10000. $\endgroup$
    – Florian F
    Feb 24, 2023 at 12:42
  • 1
    $\begingroup$ @FlorianF No need for a script, it is easily proven mathematically: Given a monochromatic equation divide through by five as often a possible. Then take residues mod 5. Let k be the colour. Then each number will now either be k or 0 mod 5. Because of our dividing through at least one will be k. If we rewrite the equation as x+y+2z=0 mod 5 then substituting leaves k or 2k or 3k or 4k on the l.h.s. none of which is zero mod 5. $\endgroup$
    – loopy walt
    Feb 24, 2023 at 14:57
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Found out the hard way that the hr tag doesn't play nice with spoilers. $\endgroup$
    – Nautilus
    Feb 26, 2023 at 21:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.