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!

If you're new here, you should start by reading some general information about this group.

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.

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestI 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

Log in to reply

I like bigger. Easy to read.

Log in to reply

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

Log in to reply

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.Log in to reply

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

Log in to reply

EDIT:

Nevermind. I mean, this DOES make for a cool pattern, I guess...Log in to reply

Log in to reply

Log in to reply

Log in to reply

So the edge must be some 10x+(9+a). I put in the

asince 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.Log in to reply

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.

Log in to reply

Log in to reply

Log in to reply

Log in to reply

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 :)

Log in to reply

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.

Log in to reply

We could prove that this scenario is impossible.

Log in to reply

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

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.

Log in to reply

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

Log in to reply

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

Log in to reply

Log in to reply

Log in to reply

Log in to reply

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.

Log in to reply

Sounds good! Do you want to try some?

Log in to reply

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

Log in to reply

I wanna try!!!!!

Log in to reply

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?"

Answer your own question.

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

Log in to reply

Log in to reply

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"?)

Log in to reply

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.

Log in to reply

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.

Log in to reply

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.

Log in to reply