8
$\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$
1
  • $\begingroup$ This is a job for... S̶u̶p̶e̶r̶m̶a̶n̶ SAT solvers! $\endgroup$ Oct 20, 2019 at 6:56

2 Answers 2

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$
1
  • 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$ Oct 18, 2019 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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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