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

Question

(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.

Answer 1

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;
            }
        }
        placed.addFirst(new Rectangle(recWidth, recHeight, x, y));
        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);
        }
    }
}

Answer 2

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.