This riddle was given to my son during an online math course: There are 42 tiles in a line. How many tiles can be marked so that no marked tile is located exactly between two other marked tiles? Honestly, I’m not sure how to tackle this puzzle without the assistance of a computer. When it comes to coding, this can be achieved with a brute-force algorithm. Every tile is a potential candidate, so we build a list of the marked tiles iteratively. We start with tile #1 and add other tiles to the list only if the new tile number doesn’t break the rule. Notice that tile ‘a’ is ‘exactly in the middle’ of tile ‘b’ and tile ‘c’ if ‘a’ is the average of ‘b’ and ‘c’.

It’s Python time

answer = []                           # list of marked tiles
for i in range(1,43):                 # go over tiles #1 to #42 (candidates)
    for x in answer:                  # go over the tiles already marked
        if (x+i)/2 in answer:         # if the average between the candidate and a marked tile is also a marked tile...
            break                     # ...break and go to the next candidate
    else:
        answer.append(i)              # if the internal loop wasn't broken the new candidate can be added to the list
print(answer, len(answer), "Numbers")

Output

[1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 32, 37, 38, 40, 41] 16 Numbers

This code leverages a useful syntax feature of Python – the ‘else’ keyword in a for loop. The ‘else’ block is executed only if the loop completes without encountering a ‘break’ statement. In this program, the code breaks out of the internal for loop if it realizes that a candidate ‘i’ cannot be marked because there is a marked tile located in the middle between candidate ‘i’ and another marked tile ‘x’.

For those who prefer concise coding, the second loop can be replaced with the ‘any’ keyword in conjunction with list comprehension. While it may initially seem less readable, once you understand the code above, the new code makes sense.

answer = []
for i in range(1,43):
    if all([(x+i)/2 not in answer for x in answer]):
        answer.append(i)
print(answer, len(answer), "Numbers")

Let’s break down the if statement. First, there’s a list comprehension that generates a list of True/False boolean values. For each already marked tile, we check if the average between the candidate and this marked tile is not a marked tile (which is good!). If the list consists entirely of True values, we can safely mark the new candidate.