## Teaser 2836: Squaring up

**From The Sunday Times, 29th January 2017** [link]

Alice had a large collection of one centimetre square tiles. She used them to make a set of some larger squares of different sizes, all with sides of less than a metre. When I saw these squares I removed one corner tile from each. Then, for each mutilated shape, Alice moved the minimum number of tiles to transform it into a rectangle. Overall she moved two hundred tiles. This resulted in a set of rectangles all of whose sides were a prime number of centimetres long.

What (in increasing order) were the lengths of the sides of her original squares?

[teaser2836]

## Jim Randell 11:51 am

on9 October 2019 Permalink |If Alice has made a square of side

n(son < 100), then she has usedn²tiles.The setter removes one corner tile from the square, leaving

(n² – 1)tiles.Alice can then take the remaining

(n – 1)tiles from the same row (or column) as the removed tile, to produce a rectangle with dimensionsn × (n – 1), and the removed(n – 1)tiles can be added back to form an additional column (or row) of a rectangle with dimensions(n + 1) × (n – 1).We require both these dimensions to be prime, so we are looking for twin primes of the form

(n – 1)and(n + 1).We need to find a set of primes that sum to 200, where each is the lower of a pair of twin primes.

This Python program runs in 85ms.

Run:[ @repl.it ]Solution:The lengths of the sides of the original squares were: 30, 42, 60, 72.Examining all subsets could be a costly approach if the parent set is large. In this case there are only 8 candidate primes, so there are at most 255 (non-empty) subsets to consider.

So here is an alternative program, although on a small problem like this there isn’t much difference in execution time.

LikeLike