# Dissect a square into 3:2 non-congruent integer-sided rectangles

(Similar to the recent 3:1 rectangle question)

Tile a square completely with rectangles which have aspect ratio 3:2, integral side lengths and all different sizes. In other words selected from 2x3, 4x6, 6x9 etc. Usual tiling rules apply: No gaps, no overlaps.

1. Find the smallest area tiling.
2. Find the tiling with with the fewest rectangles.

I have no way of proving that my answer to (1) is an answer to (2), so you could supply that proof in lieu of a tiling with fewer rectangles. Without such a proof, (2) is open ended - you could conceivably have a square one million units on a side tiled with just a handful of rectangles.

I've tagged this computer-puzzle, but I would not be surprised if it could be found by hand with a healthy dose of logic. So I also tagged it logical-deduction, but I would guess part (1) is easier with computer for most people. Part (2) requires a logical proof in order to not be open ended.

I found this by computer, a brief Google search didn't turn up any existing work in the area but it could still be a known problem.

My primitive and awfully slow program found this solution for part 1 of the question:

Size: 120; Rectangles: 10

The code:

package puzzle;

import java.util.ArrayDeque;
import java.util.BitSet;
import java.util.Deque;

public class Dissector {
private static class Rectangle {
public final int width;
public final int height;
public final int x;
public final int y;

public Rectangle(int width, int height, int x, int y) {
super();
this.width = width;
this.height = height;
this.x = x;
this.y = y;
}

public boolean overlap(int width, int height, int x, int y) {
return this.x < x + width && x < this.x + this.width  &&
this.y < y + height && y < this.y + this.height;
}

@Override
public String toString() {
return width + "x" + height + "+" + x + "+" + y;
}
}

private final int width;
private final int height;
private final int factorWidth;
private final int factorHeight;

private int areaLeft;
private final BitSet notPlaced = new BitSet();
private final Deque<Rectangle> placed = new ArrayDeque<>();

public Dissector(int width, int height, int factorWidth, int factorHeight) {
this.width = width;
this.height = height;
this.factorWidth = factorWidth;
this.factorHeight = factorHeight;
this.areaLeft = width * height;
for (int i = Math.max(width, height) / Math.max(factorWidth, factorHeight); i > 0; -- i) {
notPlaced.set(i);
}
}

private boolean place(int recId, boolean rotated, int x, int y) {
int recWidth = (rotated ? factorHeight : factorWidth) * recId;
int recHeight = (rotated ? factorWidth : factorHeight) * recId;
if (x + recWidth > width || y + recHeight > height) {
return false;
}
for (Rectangle r : placed) {
if (r.overlap(recWidth, recHeight, x, y)) {
return false;
}
}
return true;
}

public void dissect(int startX, int startY) {
if (areaLeft == 0) {
System.out.println(placed);
} else {
int x = startX;
int y = startY;
boolean moved = true;
while (moved && y < height) {
moved = false;
for (Rectangle r : placed) {
if (x >= r.x && x < r.x + r.width && y >= r.y && y < r.y + r.height) {
x = r.x + r.width;
if (x >= width) {
x = 0;
++ y;
}
moved = true;
break;
}
}
}

if (y < height) {
int recId = notPlaced.length();
while ((recId = notPlaced.previousSetBit(recId - 1)) > 0) {
notPlaced.clear(recId);
areaLeft -= recId * recId * factorWidth * factorHeight;
if (areaLeft >= 0) {
if (place(recId, false, x, y)) {
dissect(x, y);
placed.removeFirst();
}
if ((x > 0 || y > 0) && place(recId, true, x, y)) {
dissect(x, y);
placed.removeFirst();
}
}
notPlaced.set(recId);
areaLeft += recId * recId * factorWidth * factorHeight;
}
}
}
}

public static void main(String[] args) {
for (int size = 6; size < 200; size += 6) {
System.out.println("size: " + size);
Dissector splitter = new Dissector(size, size, 3, 2);
splitter.dissect(0, 0);
}
}
}

• Yup that's it. Can't be that slow or it would still be running. I'll give a while for someone to try and get part 2, then I'll mark as answer. – theonetruepath Jan 11 '18 at 22:49

2 pieces of info I've thought of that help constrain a solution, but I really haven't made much headway yet. My gut reaction is this may not be possible, but I'm not 100% certain of that. Don't consider this a full answer, but a possible stepping stone to the answer.

The ending square size, N x N, will have the form N=6k, for integer k. This comes from the fact that we know every tile's area is
$$2a\times3a=6a^2$$
Then the overall area of our square is $$N^2=\sum_{i=1}^j 6a_i^2=6\sum_{i=1}^j a_i^2$$
From here we know that we have a set of square numbers that give a sum of 6 times another square.

Based on 10 seconds of google searching, it appears that Lagrange's 4 color identity says this is possible for each multiple of 6, but not necessarily with 4 unique numbers. Example The first set of 4 tiles 4x6, 12x18, 14x21, 16x24 I found could form a 30x30 square, but does not tile nicely.

• Yes we only need consider squares with sides which are 6a. But if you are considering sets of rectangles with only four members you will not get very far. I think it's easy to see that they would require a pair of equal widths and a pair of equal heights. In other words you would have to dissect the square with one vertical and one horizontal line. Here my logic founders, but I think this precludes four different same-aspect-ratio-different-size rectangles. I don't know what the minimum number of rectangles is in general (it's probably known) but it's definitely higher than four. – theonetruepath Jan 10 '18 at 2:24
• Based on a small amount of algebra, 3 or 4 doesn't seem likely to be possible. The identity above gives a starting point to say that we have a way to construct sets of rectangles that give the correct area, but we'll need more rectangles to make that work. – thugsinuggs Jan 10 '18 at 18:17