# ===Open Problem #5===

Welcome to Open Problem #5! This is a problem I've picked, but I'd like Open Problem #6 to come from our suggestion thread which has been quiet lately. Please make some suggestions if you can!

Using copies of the polynomio above, you can use repeated copies to form a rectangle (with rotations and reflections allowed).

Using just copies of the polyomino below, is it possible to form them into a rectangle?

The answer incidentally is thought to be "no", but nobody has proven it yet.

This problem of the week from a month ago gives something a flavor of the type of proof needed.

Typically, you figure out some value ("pointiness = 0" or the like) that all rectangles share. Then you find that adding a polynomio increases or decreases that value by some set amount, such that the target value is never reached.

This problem hasn't gotten a lot of attention, so it's a possible things are that simple. You may decide a different strategy altogether, though. Good luck!

Quick updates: Open Problem #2 has the paper done, I'm still looking into the possibility of publishing in a journal.

I will be soon contacting the Online Encyclopedia of Integer Sequences about Open Problem #4, which while not finding any "new" sequences found out information about existing ones and made connections between previously unrelated ones.

Note by Jason Dyer
3 months, 1 week ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

I looked at the possible edges of the rectangle, starting wit labeling the eight possible orientations:

Polyomino labels A - H

And then considered the sequence of orientations that could fill the edge:

Empty edge L - R

Just using L and R to mark the start and end. The list of what orientations can follow each other in sequence without holes is: L -> ABFH A -> ABCDEFGHR B -> ABCEFGHR C -> B D -> AB E -> ABFHR F -> AB G -> ABFHR H -> AB A lot of these combinations leave squares that cannot be filled with other polyominos, though:

Blocked Squares

Since AG and BG do not fit, by symmetry, HB and HA don't work, so G and H are eliminated. This also means that LB and AR don't fit, since the first and last polyomino in one edge are part of the next edge. Also by symmetry BB and EB are not possible. This leaves: L->AF / A->CDE / B->ACEFR / C->B / D->AB / E->AFR / F->AB Which can be summarized in a graph:

Edge graph

This graph generates a language that codes the flat edges that can be filled with the polyomino. It can be seen that this language is closed under concatenation, so edges of any multiple can be made.

I only looked at sub sequences of length two to see if there were any squares that couldn't be filled deeper in the rectangle. The next step could be to use this to expand to length three sub strings, eliminating any that don't work, thereby getting a more precise language for the edge. Then length four, five, etc. This might lead to a contradiction, or to an edge that works. I will start working on the length three sub strings.

edit: sorry, those pictures are a lot bigger than I expected

- 2 months, 3 weeks ago

I like bigger. Easy to read.

- 2 months, 3 weeks ago

I have been doing some brute force searching by computer program. I not ready to give precise results but you may be interested in a flavour of what I am getting. The computer program is in java and at each stage tries to fit a piece on the next unoccupied square chosen as the left most column with unoccupied squars and then the square the bottom edge in that column. The pieces are tried in order and the prog first checks that the piece does not overlap an edge or previously place piece. If this check is satisfied, the prog then checks that the boundary does not leave one of a number of known "bays" that are known to be impossible to fill. If this check is satisfied the piece is placed on the board and we go onto the next iteration. If either check fails we try another piece or backtrack as appropriate. Obviously such an approach will not prove impossibility, and because of the exponential nature of the problem cannot work on large rectangles. Let the rectangle be of size X x Y where X is number of squares left to right, and Y up and down. Let X be large and as in my prog, tile the rectangle from the left, filling all the squares on left as we go. Then it is noticeable that even for reasonable large Y say up to around 100 then the number of columns that can be fully tiled from the left is never more than about six or so.
Consistent with this, the same way that others have noticed that bay on the bottom of say 1 deep by 4 wide is not tileable, there are many other bays that are not tileable, for example bays which are 4 or 5 squares deep are not tileable for a couple of dozen different widths. [I mean that a bay is tileable if it is possible to cover all its squares even if the tiles that do so reach over its boundary into the main area of the rectangle] In general the deeper the bay the wide it can be and still not tileable. A proper census of these impossible bays/boundary would speed up the search.

- 2 months ago

To fill in the corner of a rectangle with the given polynomio, the flat side of each polynomio must go up against the side of the rectangle (or there will be a gap). There are six ways to do this, as shown below.

When a 3-square-end meets another 3-square-end in the corner, then a 2 x 3 rectangular gap is formed that cannot be filled by any orientation of the polynomio (see the first two diagrams in the above picture). When a 3-square-end meets a 1-square-end in the corner, with the 3-square-end directly in the corner, then a 1 x 2 rectangular gap is formed that cannot be filled by any orientation of the polynomio (see the third diagram in the above picture). When a 3-square-end meets a 1-square-end in the corner, with the 1-square-end directly in the corner (see the fourth diagram in the above picture), then a 1 x 2 rectangular gap is formed near the corner that can only be filled by a certain orientation of a third polynomio (light blue), and this forms a 1 x 2 rectangular gap that cannot be filled by any combination of polynomios. This leaves only 2 possible ways to fill a corner - both when a 1-square-end meets another 1-square-end.

Therefore, if a rectangle does exist, the 1-square-end of one polynomio must meet another 1-square-end of another polynomio in all 4 of its corners.

(I was hoping to limit this further to either find a possible rectangle or prove that one does not exist, but unfortunately I was unable to get any further than this. Hopefully someone can use my work towards a complete solution.)

- 2 months, 3 weeks ago

Here are a lot of the "edge cases":

By "edge case", I mean that these are the patterns that can be used on the edge of the rectangle, or in this case, the left edge (I've excluded the patterns that create completely enclosed holes). Of those edge cases, I'm pretty sure only 6 work, but I'm not too sure. Obviously, the second cases in the first and second row don't work, as they create holes that can't be filled by the shape. As far as I can tell, the only case in the third row that works is the third case, but I'm not too sure. I'm pretty sure that all 3 of the cases in the last row work.

- 2 months, 3 weeks ago

From my experimenting I would agree with all of your assessments.

- 2 months, 3 weeks ago

Also, as a thought, if we can split the polyomino into two or more separate polyominoes, then if we can't construct a rectangle using those two (possibly because of infinite loops), then it definitely isn't possible with the original polyomino.

Perhaps these two?

EDIT:

Nevermind. I mean, this DOES make for a cool pattern, I guess...

- 2 months, 3 weeks ago

That's certainly worth a try, especially since the s-shape alone can't fill a rectangle.

- 2 months, 3 weeks ago

Actually, I just had a thought - what if we try making a rectangle with the two pieces I cut the polyomino into, but this time, there has to be the same number of both pieces? This might actually be a hader problem, but if it turns out to be easy, and it ends up being impossible, then that's a possible solution.

- 2 months, 3 weeks ago

I tries messing around with the s one myself last night and came to that conclusion.

- 2 months, 3 weeks ago

So the edge must be some 10x+(9+a). I put in the a since we need it to be some (1+10b) so the edge is divisible by 10. So if the the 7 edge- 3 edge sequence cannot have a 1 edge in between (which would be a vertically flipped polymino), the rectangle cannot be constructed.

- 2 months, 3 weeks ago

The area must be divisible by 10, but not necessarily the edge - one edge could be divisible by 5 and the other could be divisible by 2.

- 2 months, 3 weeks ago

Agreed. But proving that one cannot put a 1-edge between a 7-edge and 3-edge will also disprove for divisibility by 2 since the edge would be 2(10x)+9, which is not divisible by 2.

- 2 months, 3 weeks ago

Sorry. The 9 is an 8. So it would no disprove by 2.

- 2 months, 3 weeks ago

The 9 is from the extra 7-edge we always need to complete the 7-edge-3-edge sequence plus the two 1-edge at the corners.

- 2 months, 3 weeks ago

Assuming it can form a rectangle of dimensions axb, then axb must be divisible by 10 and both a and b can be expressed as the sum of any combination of 7, 3, and 1. Just an observation that may help :)

- 3 months ago

If you have a 3 at the edge, it has to be followed by a 7. These can be grouped together into a group of 10. Since adding 10 does not change the remainder by 2 or by 5, the remaining modular analysis would boil down to 7s and 1s; that on all four sides of the hypothetical rectangle.

- 3 months ago

We could prove that this scenario is impossible.

- 3 months ago

My idea was to try to construct, and continue until one of three things happens:

1. The rectangle is constructed, which would proof it's possible
2. A contradiction is reached, which would proof it's not possible
3. An infinite loop is reached, which would proof it's not possible

The furthest I was able to get was this. Assuming I didn't make any mistakes, it looks like the first two columns form an infinite loop, but I don't have a proof.

- 3 months ago

Do you have a proof that yours is the only valid configuration for the corner?

- 2 months, 4 weeks ago

I suppose I could write a proof, but it would be a pretty long and messy proof, because it would include lots of cases and cases within cases. I started writing a bit, and just the first three polyomino already took 7 pages.

What I have so far: https://docs.google.com/document/d/10j13AQu4oOi6zBNfaX90hxJ_8nawAw7lGpEP9VhtOIc/edit?usp=sharing

- 2 months, 4 weeks ago

Could you please tell me how you are working with the polyminos in your computer or whatever. I'd like to do that and post something.

- 2 months, 4 weeks ago

Make square cells in Excel. Color them in to make the shapes.

- 2 months, 4 weeks ago

Thanks!

- 2 months, 4 weeks ago

Before we tackle this particular problem, I think it would be advantageous to take a look into what type of polynomio make rectangles and which don't. I'm guessing some sort of pattern will emerge that will help us on our way.

- 3 months ago

Sounds good! Do you want to try some?

Staff - 3 months ago

Maybe cutting up the polynomial into smaller polyominoes then seeing which are impossible would be useful.

- 2 months, 3 weeks ago

I wanna try!!!!!

- 3 months ago

Here's a suggestion.

Go to the main Open Problems Group feed.

Click "Post Problem" and write up a problem you know the answer to (doing it this way will make it easier to post pictures, too). You could ask a single polynomio or a set and ask "how many of these can we make into rectangles?"

If we can get enough like this, we can start gathering on a wiki.

Staff - 3 months ago

Thanks!!!!

- 3 months ago

Just a question: if you can construct a rectangle with some polyomino, is it necessarily true that the figure is rotationally symmetric?

- 2 months, 1 week ago

@Daniel: Could you say what makes you think it must be rotationally symmetric? My intuition is that this is not true in general. If the polyomino is an ordinary domino [ = two squares ] then non-rotationally symmetric tilings certainly exist.

- 2 months, 1 week ago

Observation. Look at the example polyomino above: if you rotate it by 180°, you get the same arrangement. If you rotate by 90°, you get the same cornner arrangments. I haven't really tried to find one that is not like that. I'll get to it.

- 2 months, 1 week ago

I think the answer is yes, but I just want to be sure.

- 2 months, 1 week ago

Because if so, we could determine all the corners of the assumed rectangle by setting only one of them from David Vreken's list of possible corners.

- 2 months, 1 week ago

Following on from comments from Daniel Stone and Loius Ullman, note that the number of tiles must be even and therefore the total area is divisible by 20 and the sides of the rectangle must have factors of two at least twice and five at least once. To see that the number of tiles is even, note that if the squares are coloured alternately back and white as on a chess board each tile covers two more white squares than black squares or vice versa. Since the total number of squares in the rectangle is even ( the area is a multiple of 10 (the area of the tile), there are the same number of black squares as white in the rectangle. Hence to cover the rectangle there must be the same number of tiles with more black squares as there are tiles with more white squares: that is the tiles come in pairs.

- 2 months, 1 week ago

I took each connection in Scott Reynolds' comment and saw that the space between each polyomino in the second row in from the edge was either 0,1,2. Here's the list (it uses the same lettering as Scott's comment): 0: A->D ; B->C ; B->E ; C->B ; D->A ; E->F ; F->A 1: B->F ; E->A 2: A->E ; A->C ; B->A ; D->B ; F->B

This means you can't lay the polyominoes so that they inter-lock with the next row down, like here (the purple bit is an arbitrary tiling, and the bottom of it is an edge):

This picture is impossible, regardless of how we fill in the purple part.

This means that the rectangle might look something like this close to one of the edges:

- 2 months, 2 weeks ago

Picture Trick: If you go to a completely different problem that you solved correctly, click on the "discuss solutions" button, and write your comment in the "Add your Solutions" box, you can add pictures (and preview equations). But then instead of posting it there, copy your work and paste it in the discussion you want to comment in and post it there.

- 2 months, 2 weeks ago

I wonder if it is possible to merge David's insight which limits the number of states each corners can be put in, with Scott's insight which seeks to formalizes the pattern that any valid string of blocks should follow, to figure out if there can exist any string of block at the edge such that the string starts with one of the possible corner block and also ends with one of the corner blocks.

- 2 months, 3 weeks ago

Since the polyomino has an area of 10, the area of a rectangle that can be filled with the polynomial will have an area which is a multiple of 10. In order for this to be possible, the lengths of the rectangle must be multiples of certain numbers - if one of the side lengths was 10, then the area will always be a multiple of 10. If one of the side lengths was a multiple of 2 and the other was a multiple of 5, then the area will always be a multiple of 10. If the side lengths of a rectangle don't meet either of these conditions, then it cannot be filled with the polyomino.

(...did I seriously type "polynomial" instead of "polyomino"?)

- 2 months, 3 weeks ago

Agreed. But we need some casework to show that certain combinations of polyminos to fill the edges are not possible. Then, if the combinations necessary to reach an area divisible by 10 are proven impossible, the answer would be no.

- 2 months, 3 weeks ago

There is no side of two blocks which is always required

- 2 months, 1 week ago

What do you mean by this?

- 2 months, 1 week ago

Could you please explain yourself a little better?

- 2 months, 1 week ago

Since we already know that the area 4 S/Z polyomino can't be used to construct a rectangle, what if we assumed that a axb rectangle made of S/Z polyominoes existed, then proved by contradiction that it couldn't exist? If it works, we may be able to do the same to the area 10 polynomial we're using.

- 2 months, 3 weeks ago