Museum Design Puzzle - Help out the square-headed architect

Fausto Morales · 2011-08-19 23:10: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)

bobbym · 2011-08-19 23:50:15

Hi Fausto Morales;

Welcome to the forum.

2,3,4 are obviously open problems.

Where or what are the simple solutions?

Fausto Morales · 2011-08-20 00:16:25

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)

bobbym · 2011-08-20 00:43:57

Hi;

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

http://www.artofproblemsolving.com/Reso … minoes.pdf

Fausto Morales · 2011-08-20 01:00:04

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)

bobbym · 2011-08-20 01:14:09

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.

Fausto Morales · 2011-08-20 01:22:26

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)

bobbym · 2011-08-20 01:35:33

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

Fausto Morales · 2011-08-20 04:40:51

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)

Fausto Morales · 2011-08-20 20:52:59

You can find

the 26 symmetric museum designs that we have found so far.

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

Fausto Morales · 2011-08-25 19:43:38

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)

namealreadychosen · 2011-08-29 19:58:55

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

Fausto Morales · 2011-08-29 20:40:46

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)

namealreadychosen · 2011-08-30 18:42:53

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.

GWMorris · 2011-09-04 00:37:34

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

Fausto Morales · 2011-09-04 22:23:34

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

Math Is Fun Forum

#1 2011-08-19 23:10:11

Museum Design Puzzle - Help out the square-headed architect

#2 2011-08-19 23:50:15

Re: Museum Design Puzzle - Help out the square-headed architect

#3 2011-08-20 00:16:25

Re: Museum Design Puzzle - Help out the square-headed architect

#4 2011-08-20 00:43:57

Re: Museum Design Puzzle - Help out the square-headed architect

#5 2011-08-20 01:00:04

Re: Museum Design Puzzle - Help out the square-headed architect

#6 2011-08-20 01:14:09

Re: Museum Design Puzzle - Help out the square-headed architect

#7 2011-08-20 01:22:26

Re: Museum Design Puzzle - Help out the square-headed architect

#8 2011-08-20 01:35:33

Re: Museum Design Puzzle - Help out the square-headed architect

#9 2011-08-20 04:40:51

Re: Museum Design Puzzle - Help out the square-headed architect

#10 2011-08-20 20:52:59

Re: Museum Design Puzzle - Help out the square-headed architect

#11 2011-08-25 19:43:38

Re: Museum Design Puzzle - Help out the square-headed architect

#12 2011-08-29 19:58:55

Re: Museum Design Puzzle - Help out the square-headed architect

#13 2011-08-29 20:40:46

Re: Museum Design Puzzle - Help out the square-headed architect

#14 2011-08-30 18:42:53

Re: Museum Design Puzzle - Help out the square-headed architect

#15 2011-09-04 00:37:34

Re: Museum Design Puzzle - Help out the square-headed architect

#16 2011-09-04 22:23:34

Re: Museum Design Puzzle - Help out the square-headed architect

Board footer