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.