Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Square-headed Architect Riddle

  1. Aug 19, 2011 #1
    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.


    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. jcsd
  3. Aug 20, 2011 #2

    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
  4. Aug 20, 2011 #3


    User Avatar
    Gold Member

    If the rooms do not need square corners then there are infinite possibilities for n=2,,4 due to symmetry.
  5. Aug 20, 2011 #4
    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.

    Please introduce this constraint in your designs.
  6. Aug 20, 2011 #5

    I like Serena

    User Avatar
    Homework Helper

    Aww, and I had all these rooms with interesting shapes (that actually had square corners).
    I guess they don't count now? :grumpy:
  7. Aug 20, 2011 #6
    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!
  8. Aug 22, 2011 #7

    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
  9. Aug 24, 2011 #8

    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.


    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!
  10. Aug 26, 2011 #9
    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
  11. Sep 3, 2011 #10
    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!!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook