Polyomino rectangle tiling

Probability Level 1

This question is part of the Brilliant.org Open Problems Group where we try to solve problems nobody knows the answer to. You can join in the discussion here.

Multiple copies of a polyomino can sometimes be used to form a rectangle.

Using multiple copies, which of the polyominoes below can be formed into a rectangle?

Note: You can only use copies of the designated type, and while rotation and reflection are allowed, overlapping is not.

Only A Only B Both A and B Neither A nor B

Jason Dyer by Jason Dyer

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

It's impossible to form a rectangle with polyomino A.

To show why, let's try to form a rectangle starting from the top-left corner. There are two ways to do it (the X represents the top-left of the rectangle):

Let's first look at the first way. There's a hole in the top-right, which needs to be filled up. There is only one way to do it.

But now there's a new hole in the top-right and there is again only one way to fill it. After that there's again a hole in the top-right, and it will keep going on like that forever.

The second way won't work for the same reason, except then the hole will always be in the bottom-left. So it's impossible to construct a rectangle with polyomino A.

It's possible to form a rectangle with polyomino B as shown below.

Therefore the answer is 'Only B'.

138 Helpful 0 Interesting 0 Brilliant 0 Confused

I thought of it the same way, very good solution

Stephen Mellor - 3 years, 1 month ago

Is there a more "rigorous" way to prove that A cannot form a rectangle?

Shubhamkar Ayare - 3 years, 1 month ago

Log in to reply

Probably. I can't come up with something though.

Stefan van der Waal - 3 years, 1 month ago

Let's assume that we can indeed fill a rectangle with finite side lengths using only polymino A.

There is only one way to fill the top-left corner of the rectangle if we ignore the other symmetrical approach.

This forces us to fill the square three squares to the right of the corner square using polymino A and this continues forever.

However, this contradicts the fact that the side lengths of the rectangle are finite.

Jesse Nieminen - 3 years, 1 month ago

Small side note: I think it should be "polyomino", not "polynomial" in this context.

Victor Dumbrava - 3 years, 1 month ago

My son provide me more complex solution for case B https://imgur.com/QvMovCt

Igor L - 3 years, 1 month ago

Good solution - I recognised the rectangle above as a possible for shape B almost immediately. I visualized various assemblages of shape A, and none were rectangular, and given that this is a Basic level problem of the week I considered that sufficient to plump for "Only B" as my answer. Being right makes this what I call my brilliant.org Pi day (as well as the usual approximation this involves some chicanery with the placement of the decimal poiint!).

Thomas Sutcliffe - 3 years, 1 month ago

That is not the only way to fill the hole, but no matter how you combine the A, there is always a different side hole need to fill, so we cannot use the polyomino A to fill hole for each other.

Josei cckk - 3 years, 1 month ago

Log in to reply

Nope, now we are discussing about the top left polynomial, hence there is only one way to fill it and other ways to fill breaks the setting "top left polynomial".

Ong Zi Qian - 2 years, 11 months ago
Aatmoshru Goswami
Apr 16, 2018

Make it into a chessboard solution. Say that the top left corner of A is black, then, the bottom left must also be black, and so on until we get that there would be four of either black or white and 2 of the other, this means that it is impossible to do A, since, an odd-aread rectangle would only have 1 more than the other and an even aread would have them equal, hence, A is impossible. Now, B can have 3 blacks and 3 whites, but, hold your horses, this doesn't necessarily mean that it automatically allowed, you need to try and check this to see if it works, and I just guessed that B was allowed, and, I was right, check the illustration of the solution by Stefan van der Waal to see how it fits.

8 Helpful 0 Interesting 0 Brilliant 0 Confused

Moderator note:

This solution doesn't work, because there are two possible colorings:

4 black, 2 white

4 white, 2 black

meaning that a mixture of the two types can lead to an equal number of black and white squares.

Your logic for this wrong. It is possible for the half the pieces to have more blacks than white and the other half to have more blacks than white.

Shubham Bhargava - 3 years, 1 month ago

I was thinking this was the solution, until I saw that reflection was allowed.

J E - 3 years, 1 month ago
Alfonso Abraham
Apr 21, 2018

The only way you can form a rectangle is by using b and going in a 90 degree angle 3 times A will always have a gap

3 Helpful 0 Interesting 0 Brilliant 0 Confused

There are more complicated rectangles you can make from B than just the one using four copies each rotated differently. (I agree that A will always have gaps.)

Adam Zydney - 3 years, 1 month ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...