Myrtle the Matchmaker is widely known for her professional skills in the town of Harmony. Besides her personal charm, she has an uncanny sense for which pairs of people, especially shy people, will come to love one another and for how to make those people think it was their idea. Her technique is simple: if she knows Bob and Alice are well suited to one another but haven't been introduced, she might ask Bill and Mary to invite them to Bill and Mary's upcoming wedding. At the wedding, Bob and Alice often recognize their destinies and soon get hitched.
Myrtle likes to space out the weddings, however, so she tries to control who will get married to whom. She also likes to work with 16 people at a time--that is, eight pairs of people who will all eventually marry. Because 16 names can get confusing, she numbers the people:
1, 1, 2, 2, ..., 8, 8.
Here she wants 1 to marry 1, 2 to marry 2, and so on in that order.
Responding to recent market demands for quick marriages with a geometrical theme, Myrtle has arrived at what she calls a "marriage train." She has constructed 16 rooms in a line from west to east. She puts one person in each room and allows each to talk through a window with his or her neighbor to the west and to the east. If two think they are meant for one another, they open the door between them, get engaged and leave. Suppose two people get engaged. Call the western-most one W and the eastern-most one E. After they leave, all the people in rooms to the west of W move east one room and all the people in the rooms to the east of E move west one room. At this point, new marriage possibilities open up.
How would you arrange the people so Myrtle achieves her ordering objective?
This is in fact quite easy. Arrange them this way:
8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8
Here is what will happen. The western-most 1 will get engaged to the eastern-most 1.
Then the 2 to the west of the western 1 will move into western 1's room and the eastern 2 will move into the eastern 1's room. That will yield this configuration:
8 7 6 5 4 3 2 2 3 4 5 6 7 8
The 2s will then get engaged. Then the western 3 will move into what was once western 1's room and so on.
This system worked well, but demands for speedier matchmaking continued to grow. In response, Myrtle designed a four-by-four square grid of rooms. She laid them out so that the rows are west-east and the columns are north-south. The protocol for introductions, conversation and movement is also a little more complicated. First, each person meets his or her neighbors to the north, south, east and west. If, as a result, two neighboring west-east people (call them W and E) get engaged, they leave. Then W's western neighbor has a chance to meet E's eastern neighbor. Furthermore, W's northern neighbor will meet W's southern neighbor. Similarly, E's northern neighbor will meet E's southern neighbor.
The arrangement is similar if two neighboring north-south neighbors N and S get engaged: N's northern neighbor will meet S's southern neighbor, N's western neighbor will meet N's eastern neighbor, and S's western neighbor will meet S's eastern neighbor.
In all the scenarios above, a meeting can still take place even if a neighbor is missing provide the neighbor's neighbor in the same direction is present. For example if N has an eastern neighbor but no western neighbor (because that person is already engaged), then N will introduce N's neighbor who is two doors to the west to N's eastern neighbor.
Of course it would be very easy for Myrtle to arrange the people so everyone gets engaged right away. Here is just one configuration
1 1 2 2
3 3 4 4
5 6 7 8
5 6 7 8
It's also possible for Myrtle to arrange for many to get engaged in a first round and the rest to get engaged in a second round:
5 1 1 5
6 2 2 6
7 3 3 7
8 4 4 8