Good Rectangles and Evil Numbers

Question

Rectangles and Squares

Good Rectangle

We define a good rectangle as a rectangle in which $ \frac lw = 3 $ 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 if it is possible to tile that many good rectangles (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.

Your Challenge

What are the evil numbers?

Hint

This is important, ripped enormous cursing umbrella resting seriously in outer nitrogen.

Answer 1

Firstly, 3 is apparently good. Then, with the following shape, it concludes that if both $n_1$ and $n_2$ are good, $(n_1+n_2+2k)$ is good with any positive integer $k$.

First you stack $k$ strips of the same shape to form a rectangle, then stack other $k$ strips in the same way but transpose the rectangle. Then their remains two square "holes", which could be filled with any two good numbers of strips. For example, for $k=5, n_1=3, n_2=8$, the following tiling is constructed.

Then by taking $n_1=n_2=3$ we know $(6+2k)$ or all even integers from 8 are good. By taking $n_1=3, n_2=8$, we know all odd ingeters from 13 are good. Then the possibly bad number remaining are $\{1,2,4,5,6,7,9,11\}$. I successfully construct a square with $n=9$ as follows (and $7$ after watching the video mentioned in the comment of the question) (and $11$ by Jerry Dean) (and $6$ by Jaap Scherphuis and my solver as Jaap Scherphuis described).

So it is proved that only the following set might be evil

$\{1,2,4,5\}$

I wrote an MIQCP model and solved with gurobi for the remaining numbers, proving they are truly unfeasible and so evil.

(My model can only describe horizontally or vertically placed strips with any size, and I think that is sufficient.)

Also, the solver gives out some really random solutions like for $7$

and for $8$

I didn't think I would use mip in this problem..

For the generalized problem:

The same construction could be utilized, so $\{n_1, n_2\} \Rightarrow n_1+n_2+2k$ for all positive integer $k$. And $x$ is good in base $x$. So all even numbers from $2(x+1)$ are good. And for odd $x$'s, all odd numbers from $(3x+4)$ are good. To find odd number solution for even $x$'s, imagine we have a $x\times x$ grid, and we put a single rectangle on the first row, a $(x-1)\times(x-1)$ square and (x-1) small $1\times 1$ squares. Every square are made of $x$ rectangels. That is a construction with $(1+x^2)$ rectangles. With that being $n_1$ and $x=n_2$, we know that any odd numbers from $(x^2+x+3)$ are good. It is a bad bound but still it completes "almost all" numbers. Now it is proved that for any base $x$, any large enough number is good...

Answer 2

The evil numbers are

1,2,4,5

as already stated by @xd y . What this post adds is a simple non computer aided proof:

a) these are really bad:

Given a tile t and an x offset we say t covers x if there is a y offset such that x,y is in t. And the same with x and y interchanged.

Given a tiling T consider the subsets H and V of horizontal and vertical tile. We say H spans the square S if each y-offset in S is covered by a horizontal tile and, similarly, V spans S if each x-offset is covered by a vertical tile.

Clearly, at least one of H,V must span the square. WLOG H. As any horizontal tile can be at most 1/3 the height of S at least 3 tiles are required to span. Therefore 1 and 2 must be evil. If all tiles in H have maximal height then n=3. Any other solution must have at least four horizontal tiles two of which are not maximal size. Also, they can be chosen such that each of these four covers a y* not covered by any other. This proves 4 is evil. And for 5 not to be evil let Y1,Y2,... be the horizontal line segments in S corresponding to the y*'s of the non maximal tiles h1,h2,... The intersections hi & Yi and t5 & Yi must 1D-tile Yi where t5 is the last tile. As the intersection with t5 will always have the same width and offset, the same must hold for h1,h2,... This leaves the following cases: a tower of 2,3 or 4 same non full size horizontals next to a single vertical on top of a tower of 2,1 or 0 full size horizontals. For neither of those the numbers work out.

b) all others are good:

3 is obviously good.

i. with n also n+3 is good because

starting from a n-tiling of a square we can always chose one tile and cut it in four.

ii. with n also n+4 is good because

starting from a n-tiling of a square we can always surround it by a swirl of four tiles, see figure.

iii. with n also n+5 is good because

starting from a n-tiling of a square we can always form a larger square as shown in the figure.