Problems & Puzzles:
Rectangling the square-II.
Let's continue rectangling the square using rectangles of
unequal prime sides as we did in Puzzle 609.
In puzzle 609 we accepted imperfect & compound dissection.
In this new puzzle we will increase the requirements asking
for perfect & simple dissections and will maintain the condition of using
inner rectangles of unequal prime sides.
First let's show a SPRR-UPS (
& perfect rectangled rectangle, using unequal prime sides for each inner
rectangle) that I produced during this week:
This is a 10x15
SPRR-UPS, which means a 10x15 Simple (no two or more
produce another inner rectangle) perfect (all the inner rectangles are
distinct) Rectangle Rectangled using Unequal Prime Sides.
Q1. Is this the smallest SPRR-UPS?
Q2. Can you produce a SPSR-UPS
(Simple Perfect Square
Contributions came from Giovanni Resta, Jan van Delden &
Q1: yes, your solution is the smallest one
[Is minimal in the sense of using 5 rectangles, but is not the minimal in
the sense of the area of the rectangle overall. See belo solutions by Jan
& Hakan, CR]
Q2: the smallest square is 18x18.
I discovered that I actually attacked this problem
during the Christmas holidays of 2006. It took me quite a while to
understand my old outputs.
All the sides up to 32 are possible, apart from 19 and 23.
[New question: Can you get the SPSR-UPS for
19 & 23?]
For sides from 18 to 25 I have explored all the possibilities.
There are tilings with:
S : Tiles
18 : 7, 8
20 ; 9, 11
21 : 9, 11, 13
22 : 11, 12, 14
24 : 7, 8, 10, 11, 12, 13, 14, 15
25 : 9, 12, 13, 14, 15
Here are two examples: 18x18 & 27x27
Any special approach for your solutions to Q2?
Actually no, I do not exploit the fact that the numbers involved are
primes. I have written a general little recursive program to pack a
subset of a given set of rectangles into a larger one. The program is
simple and not very clever.
Given a goal rectangle of size R x C (rows x columns),
I recursively try to fill it from the bottom to the top, without leaving
holes. Given this property, the goal area can be represented by an array
of C integers, one for each column, that tells me how many cells from
the bottom are already filled.
For example (assuming O=empty and X=fill), the half filled board:
is represented by the numbers 4,4,2,2,1,5.
At each recursive step, I detect the narrower "well" in the current
board and I continue the filling from the bottom-left corner of it.
Clearly, other heuristics are possible.
2) Has some meaning that the only two unsolved cases in the
are prime numbers (19 & 23)?
I really do not know. However, 29 and 31 are solvable.
3) Where you solving a published/posted puzzle in 2006 from
there, or it was an idea from your own?
Few years ago I was playing with my programs for packing rectangles
and I explored several possibilities, some of them involving primes.
Jan wrote a short and a long contribution. The following is a copy of
his short one explanation:
The only 5-configuration
necessarily looks like (prove omitted):
The rectangle with the smallest
area (if no dissection exists with 6 tiles, prove omitted) 7x16:
It has area 112.
An infinite number of
rectangles/squares exist of the following 7-configuration:
Conditions for this
configuration to have a solution can be easily derived.
For this configuration the above assignment of sidelengths, with p,r,s>2
is the only possibility.
If we choose p=3 and r=s we get
a square with sides s+7, area (s+7)^2.
There is a square of this type for every value s, the lesser of a twin
The square 18x18 with the
The square [p,r,s]=[3,659,659]
has side 666, a real monster.
The rectangle with the smallest area of this type, [p,r,s]=[11,17,3],
with sides 10,32 area 320.
I found 7x16 SPRR-UPS.
the same reported by Jan above, area 112]
request, Giovanni Resta sent his solutions for 19x19 & 23x23 squares
relaxing the UPS condition to accept both rectangles & squares inside
the squares. Here are his drawings:
and this is the minimal square gotten with this relaxed
condition, using rectangles &squares.