1. Aug 19, 2011

### FaustoMorales

This puzzle is about a square-headed architect who is designing 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 additional constraints:

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.

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?

Last edited: Aug 19, 2011
2. Aug 20, 2011

### FaustoMorales

HINT:

Here is a technique that may help produce new solutions:

1. For each value of n that you choose to investigate, construct or look up 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: Aug 20, 2011
3. Aug 20, 2011

### 256bits

If the rooms do not need square corners then there are infinite possibilities for n=2,,4 due to symmetry.

4. Aug 20, 2011

### FaustoMorales

You are right. The statement did not clarify -but should have- that the idea is to use shapes for the rooms made up by joining n 1x1 squares side by side (a.k.a. n-polyominoes). That was the purpose of stating that the side length of the complex is an integer.

5. Aug 20, 2011

### I like Serena

Aww, and I had all these rooms with interesting shapes (that actually had square corners).
I guess they don't count now? :grumpy:

6. Aug 20, 2011

### FaustoMorales

Sorry about that... On the brighter side, you'll see how many interesting shapes you'll be able to make when you find larger n solutions!

7. Aug 22, 2011

### FaustoMorales

SPECIAL PROJECT:

Our square-headed architect would definitely prefer museum designs with some sort of symmetry, in addition to the rest of requirements (splitting the nxn square into n-polyominoes, all with the same perimeter and the same number of neighboring rooms), so we are also putting together a special collection to that effect.

This collection contains 15 symmetric designs so far:

n=1: The trivial design
n=2: 1 mirror-symmetric design
n=4: 2 mirror-symmetric designs and 2 designs with 90º rotation symmetry
n=6: 2 mirror-symmetric designs
n=8: 3 mirror-symmetric designs
n=9: 4 designs with 180º rotation symmetry

Use your cleverness and the hint on graphs from a previous post to find these designs and many others that will extend this very special collection.

Good luck!

Last edited: Aug 22, 2011
8. Aug 24, 2011

### FaustoMorales

UPDATE ON THE SPECIAL PROJECT

The collection keeps growing and already contains 23 symmetric designs.

n=1: The trivial design
n=2: 1 mirror-symmetric design
n=4: 2 mirror-symmetric designs and 2 designs with 90º rotation symmetry
n=6: 2 mirror-symmetric designs
n=8: 3 mirror-symmetric designs
n=9: 12 designs with 180º rotation symmetry

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!

9. Aug 26, 2011

### FaustoMorales

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

Good luck!

Last edited: Aug 26, 2011
10. Sep 3, 2011

### FaustoMorales

We extend the deadline for solutions until September 22.

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

Grids (how to) that has square elements -- post that will require a Cayley table? Feb 18, 2016
News I-Squared Act Bill Sep 2, 2015
3d head reconstruct Jan 5, 2015
Is the white region a square or rectangle? Aug 11, 2012