The Old Miss Gruppe

Question

Miss Gruppe is growing too old for her house - there are far too many rooms and it sometimes takes her days to find her way between the pantry and the kitchen! In honor of her accomplishments in the field of mathematics, the townsfolk have decided to design her a brand new house, to suit her better in her old age.

In particular, they've come up with the following idea: The house will be organized into various rooms connected to each other by doors (as tends to be the case in houses). A room may have any number of doors, but it will always have one labeled as A and one labeled as B (with the labels facing inwards). Then, it will be easy to give instructions to get around the house - for instance:

To get from the pantry to the kitchen, go through door A. From that room, go through door B. Finally, using door A brings you to your destination.

They design the house so that it is possible to get from any room to any other by such a sequence of moves. One may note that instructions like:

To get from the bathroom to the dining room, use door A and from that room, use the next door labelled A.

make sense, as the door labelled A inside the bathroom is likely different from the door labelled A in the room into which the former door leads (i.e. the door labelled A in the bathroom might be unlabeled on the other side or labelled B on the other side).

However, they understand that Miss Gruppe is somewhat absent-minded and often wanders - though she can remember the instructions all right, sometimes she'll deviate from the path. But, as a matter of superstition, when she deviates, it will always be by repeating some sequence of moves through doors exactly $3$ times - so she might go through door A, then through the next door A, and then through the next door A or she might alternate "Use door A, use door B" exactly thrice. Thus, they have decided to design the house with the following additional property:

From any room, if you choose some sequence of door labels to go through and repeat it thrice, you will end up in the same room as you started.

The townspeople love Miss Gruppe very much and want to build her a house with as many rooms as possible subject to the above conditions. Miss Gruppe, who is still an avid climbed of stairs, is fine with the house having overpasses and tunnels and generally not fitting into a plane. How many rooms can such a house have?

---

Simple Example of such a house:

A simple design for such a house with $3$ rooms would be as follows, where the character * represents a door and a letter in an adjacent square represents a label.

+---+---+
|   |   |
|   |   |
|  A*B  |
|   |   |
|   | A |
|   +-*-+
|   | B |
|   |   |
|  B*A  |
|   |   |
|   |   |
+---+---+

Where one can, for instance, get from the long room to the bottom left room either by following door A twice or by following B once - but it is easy to see that following either door three times leads you back to your original location, and easy to see that sequences like "Follow A then A then B" lead one back to their original location when followed thrice.

Answer 1

Each finite sequence of letters from the set $\{A,B\}$ gives instructions for moving from one room to another, and so determines a permutation of the rooms in the house. Let $G$ denote the collection of all permutations arising this way, which is a group. The information we are given means that:

1. $G$ acts transitively on the rooms in the house,
2. $G$ is generated by the elements $A$ and $B$, and
3. every element of $G$ has order dividing $3$.

Condition 1 says that the number of rooms is bounded by the size of $G$. The largest group satisfying Conditions 2 and 3 is called the Burnside group $B(2,3)$, which has order $27$ (see here).

Below is an image of the Burnside group, which can also be interpretted as the largest house satisfying the desired conditions. This house has $27$ rooms. The black squares represent rooms. A yellow edge pointing from one room to another indicates door A leads from the first room to the second. Similarly, blue edges represent doors labelled B.

This image was created by William E. Skeith III, and come from here.