4
$\begingroup$

Good Rectangles and Evil Numbers - Integrated

Original: Good Rectangles and Evil Numbers

Good Rectangle

We define a good rectangle with base $ x $ as a rectangle in which $ \frac lw = x $ where $ l $ is the length of the rectangle and $ w $ is the width of the rectangle.

Tiling

This is simply to clarify. There should be no problem if you ignore this section, but I would like the question to be robust.

We define a tiling of a group of shapes onto another shape as a way to place the group of shapes such that:

  • The shapes do not overlap

  • The group of shapes covers the entire target shape

  • The target shape covers the entire group of shape

(The latter two combined is equivalent such that the union of all shapes in the group is congruent to the target shape)

Good Numbers

We define a positive integer as a good number in base $ x $ if it is possible to tile that many good rectangles of base $ x $ (not necessarily of the same size) onto a square of any side length.

Evil Numbers

We define an evil number as a positive integer that is not a good number in that base.

Your Challenge

What are the evil numbers for any base?

Disclaimer

I do not know the entire answer.

But from the same logic as the original question:

Evil number $ n $ in base $ x $ must satisfy that $ n < x $ or $ n = x + 1 $ or $ n = x + 2 $ or $ n = x + 5 $. The essential part of the question is which numbers that satisfy one of the above equations but is not evil (for instance, $ n = 8 $ where $ x = 3 $ , as in the original challenge).

We appreciate answers that:

  • Tells ideas

  • Gives partial answers

But make sure you:

  • Give examples

  • Use spoilers

$\endgroup$

2 Answers 2

3
+50
$\begingroup$

This is a partial answer that just fills out the general theory a bit, and proves some more numbers to be good.

Assumptions

  • I assume the aspect ratio $x$ is rational.

I have not been able to prove that an irrational $x$ fails. It is a known theorem that if you have rectangles with one rational and one irrational side length, then they cannot tile a larger rectangle with two rational sides. I don't think that theorem can be applied here since there can be irrational scaling factors so that some of our tiles can have two irrational sides.

  • $x=\frac{l}w$ where the fraction is in lowest terms, i.e. $l$ and $w$ are positive integers with no common factor.

Next I will try to determine the smallest good number, and for that I will use a further assumption.

  • I assume that in a solution all side lengths are rationals.

If all side lengths are rationals, then we can scale up everything by the lowest common denominator of those rationals to make all the side lengths integers. I have not been able to eliminate the possibility of having irrational side lengths within the tiling, but I strongly believe it to be impossible.

Finding the smallest good number $m$

For any particular choice of $x$, let $m$ denote the smallest good number. It is obvious that you can put equal-sized $l\times w$ rectangles into a $w\times l$ grid arrangement to form a square. If $w=1$ then this is the best you can do (so $m=l$), but things get interesting when $w>1$. You can replace any $k\times k$ set of smaller rectangles by a single larger rectangle tile. For example, for the $2\times3$ rectangle $m=3$ because two normal-sized tiles and one double-sized tile form a square. Clustering the $w\times l$ grid arrangement in this way is equivalent to tiling a $w\times l$ rectangle by integer squares. This has been studied, and can be found in the OEIS as A113881. Note that it is possible that in certain cases $m$ is smaller than this, because it is not necessarily the case that all minimal solutions arise like this with all the rectangle tiles oriented the same way.

Potentially evil numbers

As shown in answers to the previous question, one solution can generate other solutions with more tiles.

Replacing any tile by four half-sized tiles increases the number of tiles by $3$.
Surrounding any solution with a layer consisting of four rectangles increases the number of tiles by $4$.
Note: the second method only works when the tile is rectangular, not when it is square.

So starting at the base case with $m$ tiles we can generate solutions for

$m$, $m+3$, $m+6$, $m+9$, ...
$m+4$, $m+7$, $m+10$, $m+13$, ...
$m+8$, $m+11$, $m+14$, $m+17$, ...

This leaves only the cases

$m+1$, $m+2$, $m+5$

as potentially evil numbers that remain to be checked in general. This was already known, and alluded to in the question. However, the last case can be eliminated. I had already found tilings for several rectangle shapes (see previous edit of this answer), until it dawned on me that they can all be solved in the same way:

You can replace any tile by a $3\times3$ array of smaller tiles. This adds $8$ tiles. Then merge together $2\times2$ of them into a larger tile, which reduces the number of tiles by $3$. The net gain is $5$ tiles.
For example, with the $1\times4$ tile $9$ is good as shown here:
Nine_1x4_tiles_making_a_square
This leaves only $m+1$ and $m+2$ as potentially evil numbers.

As Penguino points out in his answer, the square case $w=l=1$ needs special treatment. Here is a different proof for this case.

Using $(k+1)^2 = 1\cdot k^2 + (2k+1)\cdot 1^2$ you get tilings with $2k+2$ tiles for any $k>0$.
Using $(2k+2)^2 = 4\cdot k^2 + (2k+1)\cdot 2^2$ you get tilings with $2k+5$ tiles for any $k>0$.
As $1$ is obviously a good number, this leaves only $2$, $3$, $5$ as potentially evil numbers.

The corners of the final square must each be covered by a different tile, so it follows immediately that $2$ and $3$ are evil. Proving $5$ is evil is trickier. The fifth tile is not in a corner, so can touch at most one side of the target square. The other three sides of the target square must be covered by the tiles in the corners, and you find that whatever their side lengths are, the total area leaves no room for a fifth tile.

Here is a list of potentially evil numbers for various rectangle sizes:

$1\times1$: $2$, $3$, $5$; proven evil
$1\times2$: ($1$), $3$, $4$; proven evil in Numberphile video
$1\times3$: ($1$, $2$), $4$, $5$; proven evil in original question
$1\times4$: ($1$, $2$, $3$), $5$, $6$
$1\times5$: ($1$, $2$, $3$, $4$), $6$, $7$
$1\times6$: ($1$, $2$, $3$, $4$, $5$), $7$, $8$

$2\times3$: $m=3$: ($1$, $2$), $4$, $5$
$2\times5$: $m=4$: ($1$, $2$, $3$), $5$, $6$
$3\times4$: $m=4$: ($1$, $2$, $3$), $5$, but $6$ is good (see below)
$3\times5$: $m=4$: ($1$, $2$, $3$), $5$, $6$
$3\times7$: $m=5$: ($1$, $2$, $3$, $4$), $6$, but $7$ is good (see below)

It is of course much more difficult to prove a number to be evil than it is to prove a number to be good. In the latter case a single tiling is proof, while in the former you have to prove that no such tiling can exist.

Here is proof that $6$ is good for $3\times4$ tiles:

Six_3x4_tiles_making_square

and that $7$ is good for $3\times7$ tiles:

Seven_3x7_tiles_making_square

The above two tilings are related, and can be generalised to all $3\times(3k+1)$ rectangles by adding orange rectangles at the top as $k$ increases. I found similar general tilings in some other cases, which are also tilings arising from clustering together tiles from a $l\times w$ arrangement of rectangles. Below is a list, but note that I have not proved that these values of $m$ are correct, nor proved that the numbers labeled as evil really are.

$1\times k$: $m=k$; $m+1$ evil, $m+2$ evil

$2\times (2k+1)$: $m=k+2$; $m+1$ evil, $m+2$ evil

$3\times (3k+1)$: $m=k+3$; $m+1$ evil, $m+2$ good
$3\times (3k+2)$: $m=k+3$; $m+1$ evil, $m+2$ evil

$4\times (4k+1)$: $m=k+4$; $m+1$ good, $m+2$ evil
$4\times (4k+3)$: $m=k+4$; $m+1$ evil, $m+2$ good

$5\times (5k+1)$: $m=k+4$; $m+1$ good, $m+2$ evil
$5\times (5k+2)$: $m=k+4$; $m+1$ evil, $m+2$ evil
$5\times (5k+3)$: $m=k+4$; $m+1$ evil, $m+2$ evil
$5\times (5k+4)$: $m=k+5$; $m+1$ good, $m+2$ evil

$6\times (6k+1)$: $m=k+4$; $m+1$ evil, $m+2$ good
$6\times (6k+5)$: $m=k+5$; $m+1$ good, $m+2$ good

$\endgroup$
1
$\begingroup$

Partial answer...

For x=1, the evil numbers are

n = {2,3,5}

See visual 'proof' below. But this seems to go against the spoiler in your post that follows the statement "But from the same logic as the original question:, as the largest evil number for x=1 does not fit into any of the categories described in your spoiler. That is to say.

for x=1, n=5 is not of the form n < x, or n = x + 1, pr n = x + 2 or n = x + 5 as you suggest

Unless I am missing something...

enter image description here

$\endgroup$
1
  • 1
    $\begingroup$ This is correct: the "pinwheel" construction used to get n+4 from n doesn't work with squares $\endgroup$ Jun 1, 2022 at 12:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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