Affixing squares

All pairs $(l,w)$ with $\gcd(l,w) = 1$ are possible, and only those. A simple algorithm can print the result $\boxed{6087}$ , such as this:

1
2
3
4

from fractions import gcd
print(sum((gcd(l, w) == 1) for l in range(1, 101) for w in range(1, 101)))
# count the number of (l, w) with 1 <= l,w < 101 where gcd(l, w) = 1
# prints 6087

It remains to show that the above claim is correct.

Observe that it doesn't matter whether you put a square on the left side or on the right side; likewise, it doesn't matter whether you put a square on the top side or on the bottom side. So we can just say whether we extend the rectangle horizontally or vertically.

Moreover, given a rectangle $l \times w$ ( $l$ units horizontally, $w$ units vertically), we can always determine the last move. If $l > w$ , then the last move must have been affixing $w \times w$ horizontally on a $(l-w) \times w$ rectangle; the other possibility is impossible as there's no rectangle left. If $l < w$ , the last move was vertical. If $l = w$ , then there's no last move.

Now observe that this is exactly the Euclidean algorithm! Whichever number is smaller, subtract it from the larger one. Repeat until both numbers are equal, which gives the GCD.

Thus, if $l \times w$ can be generated from $1 \times 1$ , it must be that $\gcd(l,w) = 1$ . Likewise, every pair with GCD $1$ can be generated by just reversing the sequence of steps generated by the Euclidean algorithm. For example, for the picture,

$\begin{aligned} \gcd(17, 5) &= \gcd(12, 5) \\ &= \gcd(7, 5) \\ &= \gcd(2, 5) \\ &= \gcd(2, 3) \\ &= \gcd(2, 1) \\ &= \gcd(1, 1) \end{aligned}$

Reversing the sequence above, from $1 \times 1$ we extend horizontally to $2 \times 1$ , then vertically twice to $2 \times 5$ , then horizontally three times to $17 \times 5$ . This shows the correctness of the claim.

Python 3.3:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def children(dimensions):
    w, l = dimensions
    if w + l <= 100:
        # add a square to the right
        yield w + l, l
        # add a square to the top
        yield w, w + l
# do a breadth first search for all valid dimensions
found = set((0,0))
frontier = {0:[(1, 1)]}
current_level = 0
while frontier[current_level]:
    current_level += 1
    frontier[current_level] = set()
    for node in frontier[current_level-1]:
        for child in children(node):
            found.add(child)
            frontier[current_level].add(child)
    del frontier[current_level-1]
print ("Answer:", len(found))