7
$\begingroup$

Can you paint every number from 1 to 23 with three colours, such that there are no distinct numbers $𝑎,𝑏,𝑐$ of the same colour with $𝑎+𝑏=𝑐$? For example, you cannot have 2, 3 and 5 of the same colour since 2+3=5. You may need to use a computer to solve this.

Here is a similar puzzle for numbers 1 to 8 painted with two colours: Paint numbers from 1 to 8 with two colours

Good luck!

$\endgroup$
  • $\begingroup$ This is a job for... S̶u̶p̶e̶r̶m̶a̶n̶ SAT solvers! $\endgroup$ – Mario Carneiro Oct 20 at 6:56
6
$\begingroup$

I have found that solution (thanks Python !) :

Red : 1, 2, 4, 8, 11, 16, 22
Green : 3, 5, 6, 7, 19, 21, 23
Blue : 9, 10, 12, 13, 14, 15, 17, 18, 20

Here is my code if you're curious !

 # Tells for each color if it is available for this number
 def getColorsAvailabilities(n):
     av = [True] * 3
     for i in range(1, (n+1) // 2): # Only iterate up to half the number
         if (colors[i] == colors[n-i]):
             # If i and (n-i) have same color, n cannot be of that color
             av[colors[i]] = False
     return av
 
 # Main recursive function
 def test(n):
     if (n >= 24):
         return True
     colorsAvailabilities = getColorsAvailabilities(n)
     # Try each available color, in order
     for color in range(3):
         if colorsAvailabilities[color]:
             colors[n] = color
             if test(n+1):
                 return True  # Stop when we found a solution
     # If every available color results in a failure, backtrack
     return False
 
 # First try : 1 and 2 have same colors
 colors = [-1] * 24
 colors[1] = 0
 colors[2] = 0
 print(test(3)) # It works !
 print(colors) # My solution (with Red = 0, Green = 1, Blue = 2)
 # Second try : 1 and 2 have different colors
 colors = [-1] * 24
 colors[1] = 0
 colors[2] = 1
 print(test(3)) # Doesn't work (stops at 22)
 print(colors)
 

$\endgroup$
  • 3
    $\begingroup$ I saw someone else answer in the while I was editing my own answer, but since I have added my code, it is not a total duplicate, so here you go ^^ $\endgroup$ – Thomas Bécavin Oct 18 at 13:39
9
$\begingroup$

I used a computer, and found the following solution:

First group: $1,2,4,8,11,22$
Second group: $3,5,6,7,19,21,23$
Third group: $9,10,12,13,14,15,16,17,18,20$

You can move $16$ or $17$ to the first group, but not both. Those are the only three solutions according to my program, other than permuting the groups. Note that $24$ cannot be added to any group.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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