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

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

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

]]>]]>

Good luck!

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

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

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

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

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

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

Welcome to the forum.

2,3,4 are obviously open problems.

Where or what are the simple solutions?

]]>