7
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

solution

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);
        }
    }
}
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – theonetruepath Jan 11 '18 at 22:49
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – theonetruepath Jan 10 '18 at 2:24
  • $\begingroup$ 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. $\endgroup$ – thugsinuggs Jan 10 '18 at 18:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.