Can You Solve a High Schooler’s Favorite Puzzle?

This Week's Fiddler

Our strategy is to make a $\gcd(3,5)=15$ cm–sized square of one tile, allowing us to perfectly tile the outside on two sides with the other tile. In this case, we want to tile a 15 cm × 15 cm square with nine 5 cm × 5 cm tiles, and we can maintain the square's perfect square status by adding 3 cm × 3 cm tiles only to two of the larger square's sides. This makes for an 18 cm × 18 cm final square. Hence, our answer is 18 cm.

The Python code below confirms, using a recursive filling algorithm with backtracking, that $N=18$ is indeed the first size for which this works:

Code

import itertools


def tile35(board: list[list[int]]):
    N = len(board)
    has3 = False
    has5 = False
    for r, c in itertools.product(range(N), repeat=2):
        if board[r][c] == 0:
            break
        if board[r][c] == 3:
            has3 = True
        elif board[r][c] == 5:
            has5 = True
    else:
        return has3 and has5
    for k in (3, 5):
        if r + k > N or c + k > N:
            continue
        if any(board[r + dr][c + dc] for dr, dc in itertools.product(range(k), repeat=2)):
            continue
        for dr, dc in itertools.product(range(k), repeat=2):
            board[r + dr][c + dc] = k
        if tile35(board):
            return True
        for dr, dc in itertools.product(range(k), repeat=2):
            board[r + dr][c + dc] = 0
    return False


for n in itertools.count():
    board = [[0 for _ in range(n)] for _ in range(n)]
    if tile35(board):
        print('\n'.join(''.join(map(str, row)) for row in board))
        print('Answer:', n)
        print()
        break

Output

333333333333333333
333333333333333333
333333333333333333
333555555555555555
333555555555555555
333555555555555555
333555555555555555
333555555555555555
333555555555555555
333555555555555555
333555555555555555
333555555555555555
333555555555555555
333555555555555555
333555555555555555
333555555555555555
333555555555555555
333555555555555555
Answer: 18

One such tiling is shown below:

Answer: 18 cm

Extra Credit

We know that any $N\lt3$ is not possible. From there, we can consider "trivial solutions": solutions where the size is a multiple of an odd number 3 or greater. For example, a 6 cm × 6 cm board is tileable with only 3 cm × 3 cm tiles. Thus, the only answers possible are sizes which have no odd factors, i.e., powers of 2; this observation helps limit our search space tremendously. Note that for the lowest power of 2 that is fillable, any higher power of 2 will also be fillable because it is a multiple of the lower power of 2.

The Python code below recursively fills a board with tiles of various sizes, backtracking if a board is impossible to fill. We can try to fill boards of power-of-2 sizes until one of them succeeds; we can then conclude that the largest $N$ for which an $N$ cm × $N$ cm board is not tileable would be the power of 2 that preceded.

Code

import itertools


def tile_board(board: list[list[int]]):
    N = len(board)
    for r, c in itertools.product(range(N), repeat=2):
        if board[r][c] == 0:
            break
    else:
        return True
    for k in range(N - (N % 2 == 0), 2, -2):
        if r + k > N or c + k > N:
            continue
        if any(board[r + dr][c + dc] for dr, dc in itertools.product(range(k), repeat=2)):
            continue
        for dr, dc in itertools.product(range(k), repeat=2):
            board[r + dr][c + dc] = k
        if tile_board(board):
            return True
        for dr, dc in itertools.product(range(k), repeat=2):
            board[r + dr][c + dc] = 0
    return False


for p in itertools.count():
    board = [[0 for _ in range(2**p)] for _ in range(2**p)]
    if tile_board(board):
        print('\n'.join(' '.join(f'{x:02d}' for x in row) for row in board))
        print(f'{2**p} by {2**p}')
        print('Answer:', 2**(p - 1))
        break

Output

21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 11 11 11 11 11 11 11 11 11 11 11
21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 11 11 11 11 11 11 11 11 11 11 11
21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 11 11 11 11 11 11 11 11 11 11 11
21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 11 11 11 11 11 11 11 11 11 11 11
21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 11 11 11 11 11 11 11 11 11 11 11
21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 11 11 11 11 11 11 11 11 11 11 11
21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 11 11 11 11 11 11 11 11 11 11 11
21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 11 11 11 11 11 11 11 11 11 11 11
21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 11 11 11 11 11 11 11 11 11 11 11
21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 11 11 11 11 11 11 11 11 11 11 11
21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 11 11 11 11 11 11 11 11 11 11 11
21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 05 05 05 05 05 03 03 03 03 03 03
21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 05 05 05 05 05 03 03 03 03 03 03
21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 05 05 05 05 05 03 03 03 03 03 03
21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 05 05 05 05 05 03 03 03 03 03 03
21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 05 05 05 05 05 03 03 03 03 03 03
21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 05 05 05 05 05 03 03 03 03 03 03
21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 05 05 05 05 05 03 03 03 03 03 03
21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 05 05 05 05 05 03 03 03 03 03 03
21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 05 05 05 05 05 03 03 03 03 03 03
21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 05 05 05 05 05 03 03 03 03 03 03
11 11 11 11 11 11 11 11 11 11 11 05 05 05 05 05 05 05 05 05 05 05 05 05 05 05 03 03 03 03 03 03
11 11 11 11 11 11 11 11 11 11 11 05 05 05 05 05 05 05 05 05 05 05 05 05 05 05 03 03 03 03 03 03
11 11 11 11 11 11 11 11 11 11 11 05 05 05 05 05 05 05 05 05 05 05 05 05 05 05 03 03 03 03 03 03
11 11 11 11 11 11 11 11 11 11 11 05 05 05 05 05 05 05 05 05 05 05 05 05 05 05 03 03 03 03 03 03
11 11 11 11 11 11 11 11 11 11 11 05 05 05 05 05 05 05 05 05 05 05 05 05 05 05 03 03 03 03 03 03
11 11 11 11 11 11 11 11 11 11 11 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03
11 11 11 11 11 11 11 11 11 11 11 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03
11 11 11 11 11 11 11 11 11 11 11 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03
11 11 11 11 11 11 11 11 11 11 11 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03
11 11 11 11 11 11 11 11 11 11 11 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03
11 11 11 11 11 11 11 11 11 11 11 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03 03
32 by 32
Answer: 16

Here we find that we can successfully tile a 32 cm × 32 cm board, making 16 (the largest "untileable" power of 2) our answer.

There are actually thousands of tilings that work for a 32 cm × 32 cm board. One such tiling that I find rather elegant (due to its diagonal symmetry and its "greedy" use of maximally sized tiles) is:

Another interesting 32 × 32 solution I found (which greedily chooses minimally sized tiles and is notably assymmetric):

Answer: 16