===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!

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.

Note by Jason Dyer
2 weeks, 1 day ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 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} \)

Comments

Sort by:

Top Newest

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

Polyomino labels A - H

Polyomino labels A - H

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

Empty edge L - R

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

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

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

Scott Reynolds - 3 days, 11 hours ago

Log in to reply

I like bigger. Easy to read.

Mike Harding - 3 days, 10 hours ago

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

David Vreken - 4 days, 15 hours ago

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.

Louis Ullman - 4 days, 11 hours ago

Log in to reply

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

David Vreken - 4 days, 10 hours ago

Log in to reply

@David Vreken 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...

Louis Ullman - 4 days, 9 hours ago

Log in to reply

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

David Vreken - 4 days, 9 hours ago

Log in to reply

@David Vreken 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.

Louis Ullman - 4 days, 7 hours ago

Log in to reply

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

Mike Harding - 4 days, 8 hours ago

Log in to reply

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.

Daniel Stone - 4 days, 15 hours ago

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.

David Vreken - 4 days, 14 hours ago

Log in to reply

@David Vreken 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.

Daniel Stone - 4 days, 14 hours ago

Log in to reply

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

Daniel Stone - 4 days, 13 hours ago

Log in to reply

@Daniel Stone 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.

Daniel Stone - 4 days, 13 hours ago

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

Daniel Stone - 1 week, 3 days ago

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.

Joonas Jürgen Kisel - 1 week, 1 day ago

Log in to reply

We could prove that this scenario is impossible.

Daniel Stone - 1 week, 3 days ago

Log in to reply

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.

Stefan van der Waal - 1 week, 5 days ago

Log in to reply

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

Raizel Davis - 5 days, 19 hours ago

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

Stefan van der Waal - 5 days, 15 hours ago

Log in to reply

@Stefan van der Waal 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.

Daniel Stone - 5 days, 14 hours ago

Log in to reply

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

Raizel Davis - 5 days, 14 hours ago

Log in to reply

@Raizel Davis Thanks!

Daniel Stone - 5 days, 13 hours ago

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.

Mike Harding - 1 week, 6 days ago

Log in to reply

Sounds good! Do you want to try some?

Jason Dyer Staff - 1 week, 5 days ago

Log in to reply

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

Louis Ullman - 4 days, 15 hours ago

Log in to reply

I wanna try!!!!!

Erica Phillips - 1 week, 5 days ago

Log in to reply

@Erica Phillips 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?"

Answer your own question.

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

Jason Dyer Staff - 1 week, 5 days ago

Log in to reply

@Jason Dyer Thanks!!!!

Erica Phillips - 1 week, 5 days ago

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

Louis Ullman - 4 days, 17 hours ago

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.

Daniel Stone - 4 days, 17 hours ago

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.

김 재형 - 1 day, 9 hours ago

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.

Louis Ullman - 2 days, 22 hours ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...