2
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ This is a fun problem. There's a good Numberphile youtube video about the version with rectangles of ratio 1:2. It explains a solution method that also applies here so don't watch it if you want to have a go at solving it unspoiled. $\endgroup$ May 17, 2022 at 7:52
  • 1
    $\begingroup$ Inspired by that video. $\endgroup$ May 17, 2022 at 7:53
  • 2
    $\begingroup$ Please don't edit a question so that it renders the already given answers incorrect, incomplete or irrelevant. If you want to ask about general case, either do it in a new question and link back to this one, or frame it as a bonus part of the original question so that the existing answers still make sense. $\endgroup$ May 19, 2022 at 7:50
  • $\begingroup$ That doesn't give you a ticket to get around the rules. See meta.stackexchange.com/a/86998/1017231 $\endgroup$
    – bobble
    May 19, 2022 at 13:44

2 Answers 2

5
$\begingroup$

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

1

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

$\endgroup$
11
  • 1
    $\begingroup$ 1 and 2 must be evil. 6 isn't. and 11 isn't either. Try to construct them. I think 4 and 5 are evil, correct me if you find a construct $\endgroup$ May 17, 2022 at 14:45
  • $\begingroup$ @NumberBasher Yeah but proving "almost all" satisfies me so :) $\endgroup$
    – xd y
    May 17, 2022 at 14:47
  • $\begingroup$ I don't really understand this $\endgroup$ May 17, 2022 at 14:50
  • 2
    $\begingroup$ rot13(Pbafgehpgvba sbe 11: gjb gvyrf jvgu gur ybatre fvqr yratgu rdhny gb gur fvqr yratgu bs gur fdhner, gura avar fznyyre gvyrf jvgu gur ybatre fvqr yratgu rdhny gb n guveq bs gur fvqr yratgu bs gur fdhner) $\endgroup$
    – Jerry Dean
    May 17, 2022 at 15:00
  • 2
    $\begingroup$ The n=6 case can be made by using the bottom half of your n=9 case twice. I'm pretty sure the remaining cases are evil, but don't know how to prove it. $\endgroup$ May 17, 2022 at 15:32
2
$\begingroup$

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.

enter image description here

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.

enter image description here

$\endgroup$
8
  • $\begingroup$ > Clearly, at least one of H,V must span the square. $\endgroup$ May 18, 2022 at 0:18
  • $\begingroup$ Why? IHATE15CHAR $\endgroup$ May 18, 2022 at 0:18
  • 2
    $\begingroup$ @NumberBasher It is quite intuitive, really: For example, if H doesn't span there must be a horizontal line that is not touched by any horizontal tile. It must therefore be entirely covered by vertical tiles. $\endgroup$
    – loopy walt
    May 18, 2022 at 0:35
  • $\begingroup$ OK, understand now $\endgroup$ May 18, 2022 at 0:41
  • 2
    $\begingroup$ @JerryDean I do not see any counter examples and if there were there obviously couldn't be proof. Are you sure you have read the definitions carefully? $\endgroup$
    – loopy walt
    May 18, 2022 at 2:36

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.