You are not logged in.

- Topics: Active | Unanswered

**Fausto Morales****Member**- Registered: 2011-08-19
- Posts: 11

This puzzle features a truly square-headed architect who wants to design a museum in the shape of an nxnxh square box, where n is an integer denoting the side length and h is the height of the building.

Building design is subject to the following requirements:

1. For any n chosen there will be exactly n rooms.

2. All rooms will have the same area n, in order to be able to hold similar crowd sizes.

3. All rooms will have the same perimeter so that they all have equal total wall areas.

4. All rooms will have the same number of neighboring rooms so as to be equivalent for the purpose of moving around the building.

5. All room designs will be the product of joining 1x1 squares side by side (that is, each room will be a polyomino).

Note: Two rooms are neighbors if they share at least a part of a wall, not just a corner.

QUESTIONS:

1. Simple solutions can be found for n=1, 2, 3 and 4. Can you check this?

2. No solutions are known for n=5. Are there any?

3. Two solutions are known for n=6. Can you find them? Are there more?

4. Are there solutions for n>6? Can we help the architect find interesting (i.e., large n) designs?

SPECIAL PROJECT

Our square-headed architect definitely prefers symmetric designs, so we are putting together a special collection of symmetric museum designs that meet all 5 requirements above.

Share your cleverness and make your contribution to extend our special collection! - Updates will be posted as we find new designs.

*Last edited by Fausto Morales (2011-08-21 03:35:54)*

Offline

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606

Hi Fausto Morales;

Welcome to the forum.

2,3,4 are obviously open problems.

Where or what are the simple solutions?

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.**** Always satisfy the Prime Directive of getting the right answer above all else.**

Offline

**Fausto Morales****Member**- Registered: 2011-08-19
- Posts: 11

Hi!

Here are solutions for n = 2, 3 and 4, looking at the building from above and so that all copies of the same letter denote 1x1 cells of the polyomino assigned to a specific room:

n=2:

AA

BB

n=3

AAB

ABB

CCC

n=4

AABB

AABB

CCDD

CCDD

or

AAAB

CABB

CCDB

CDDD

or

AAAB

CCAB

CDBB

CDDD

*Last edited by Fausto Morales (2011-08-20 00:32:08)*

Offline

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606

Hi;

Okay, thanks! Just the condition of the problem that they be polyminoes might make this problem intractable.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.**** Always satisfy the Prime Directive of getting the right answer above all else.**

Offline

**Fausto Morales****Member**- Registered: 2011-08-19
- Posts: 11

Hi,

Thanks for the link - very informative. The article states the intractability of polyomino counting under various criteria as n becomes large. By contrast, in the museum design problem we just want to find any new designs, if they exist. What the paper does imply is that finding ALL existing designs for a given n is a task that quickly gets computationally heavier as n grows (it would be one of those "NP-hard" problems).

Having understood that, my guess is that solutions for n > 6 will be found, quite probably in this forum.

A larger conjecture: I believe that solutions must exist for an infinite number of values of n.

*Last edited by Fausto Morales (2011-08-20 01:16:20)*

Offline

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606

Hi;

I admire your optimism. The fact that no five has been found, even by computer is not encouraging. If there was one number that failed there could be others.

I have to read up on polyminoes.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.**** Always satisfy the Prime Directive of getting the right answer above all else.**

Offline

**Fausto Morales****Member**- Registered: 2011-08-19
- Posts: 11

Absolutely, I also expect some other values of n to fail besides n=5 (If indeed n=5 turns out to fail - I haven't checked this by computer nor have I been able to prove that it fails.) However, n=6 works and I expect infinitely many other values of n to work out too.

*Last edited by Fausto Morales (2011-08-20 03:52:13)*

Offline

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 109,606

Okay, if I get anything meaningful I will post it.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.**** Always satisfy the Prime Directive of getting the right answer above all else.**

Offline

**Fausto Morales****Member**- Registered: 2011-08-19
- Posts: 11

HINT:

Here is a technique that may help produce solutions for n > 6:

1. For each value of n that you choose to investigate, construct or look up connected regular graphs on n vertices with degree > 2 that can be drawn without crossings between edges (i.e., with edges meeting only at vertices).

2. For each such graph, take the vertices to represent n-polyominoes with the same perimeter and take the edges between vertices to mean that the corresponding n-polyominoes are neighbors.

3.Try to produce a design with n-polyominoes in an nxn square consistently with the connectivity conditions specified by the graph.

Repeat this procedure for any regular graph on n vertices of the type specified that looks promising.

UPDATE 1:

I decided to follow my own hint and came up with several solutions for n = 8, two of them with mirror symmetry. Can you find these? Is it possible to find designs for n > 8?

UPDATE 2:

The situation is much less promising for n = 5 and n = 7, since there are no graphs of the type specified by the hint (a.k.a. connected regular planar graphs) with degree > 2.

Can we actually prove that the only connected regular planar graphs of each size (the pentagon graph and the heptagon graph, respectively) are incompatible with any possible solutions to the design? This shouldn't be hard.

n=9 holds better chances, since there is a connected regular planar graph with degree 4 that might do the trick.

*Last edited by Fausto Morales (2011-08-20 13:00:52)*

Offline

**Fausto Morales****Member**- Registered: 2011-08-19
- Posts: 11

You can find

theWhat is amazing to me is that such a set of **basic, uniform, regular** design conditions - **symmetrically** splitting an nxn **square** into n polygons made of 1x1 **squares**, **all** polygons having the **same** area, perimeter and number of neighbors - appears to **impose** the presence of some fairly **irregular**, zigzagging shapes already for n=8. If this is any indication, designs will get increasingly interesting and original as n grows.

P.S.: This impression is further supported by the symmetric designs for n=9 that I've just found - as you can see at the "here" link, these also have a few really twisted rooms. Is this going to be the fun trend as n grows?

The next big challenge ahead is to go for the **n=10** record.

**HINTS:**

1. Build connected, planar (no crossings between edges), 4-regular graphs and study their suitability to represent connections of 10-polyominoes of the same perimeter symmetrically placed within a 10x10 square. Keep in mind that the same graph may have several potentially useful planar embeddings (i.e. "presentantions" on the plane).

2. A trick to get you started with the graphs:

a. Put 4 vertices in a square configuration and join them with edges to form a square.

b. Similarly, use 6 more vertices to place a hexagon within the square.

c. Draw 2 more edges between vertices of the hexagon (you have some choices here).

d. Complete the graph by connecting some vertices of the square with some vertices of the hexagon, so that when you are done each vertex is connected to 4 others and there are no crossings between edges.

e. See if you can use your graph to help you produce a correct partition of the 10x10 square into 10-polyominoes. If not, repeat steps (c) and (d) and try again.

Have lots of fun!

*Last edited by Fausto Morales (2011-08-24 23:43:34)*

Offline

**Fausto Morales****Member**- Registered: 2011-08-19
- Posts: 11

Oh, in case you were wondering: at least 1 solution exists to the 10x10 design. I will add it to the collection on September 22, unless someone can find it first...:)

Good luck!

*Last edited by Fausto Morales (2011-09-02 19:20:03)*

Offline

**namealreadychosen****Member**- Registered: 2011-07-23
- Posts: 16

*Last edited by namealreadychosen (2011-08-29 20:00:22)*

Offline

**Fausto Morales****Member**- Registered: 2011-08-19
- Posts: 11

1. Seems that a row is missing in your 10x10 design. Couldn't fill in the gap with equal perimeters and symmetry simultaneously. Please re-post.

2. For the 5x5 design: I can't follow the logic behind the following statement towards the end of your proof: "The two neighbours of any room must touch...". They could just touch at a corner and they wouldn't be considered neighbors, in which case the rest of the argument wouldn't follow.

*Last edited by Fausto Morales (2011-08-29 20:53:31)*

Offline

**namealreadychosen****Member**- Registered: 2011-07-23
- Posts: 16

1. Sorry, the10x10 was wrong.

2. If 2 rooms only touch by the corners, the room which contains the square between those 2 corners will be already have 2 neighbours, and more neighbours will have to touch the rest of that room.

Offline

**GWMorris****Member**- Registered: 2011-09-03
- Posts: 4

Yeah, that 9x10 10x10 square REALLY threw me off for a minute! It took a second to realize we were missing a few spots there..

Offline

**Fausto Morales****Member**- Registered: 2011-08-19
- Posts: 11

Hints for the 2 symmetric solutions known so far to the 10x10 design:

1. Each corner of the 10x10 square belongs to a different room.

2. Each 1x1 cell of the central 2x2 square belongs to a different room.

Can you find them both?

Good luck!!

Offline