Also in the spirit of the holiday season, I present a new math problem relating to Christmas gift-giving. This doesn't have anything to do with gaming, but it's still too good to pass up.
Bonus Problem: Divvying Up the Loot, Modern-Day Edition
The "white elephant gift exchange" protocol, featured in an episode of NBC's "The Office", is a procedure used for distributing Christmas gifts at large gatherings. In the protocol, each of the N participants brings a gift, for a total of N gifts, which are all placed into a central pile. The participants are numbered from 1 to N. The protocol consists of N rounds.
In the I'th round of the protocol, the following steps take place:
1. Player I selects a gift and places it in front of him. He can select a gift either from the central pile or any of the gifts in front of other players.
2. If he selects a gift from the central pile, the round ends. If he selects a gift from another player, then that player (who just had his gift taken) now has the option of choosing a gift, again either from the central pile or from another player. If he takes a gift from another player, then that player also has the option of choosing a gift as described. This process continues until someone chooses a gift from the central pile, at which point the round ends.
3. Once a gift has been selected, it cannot be selected again until the beginning of the next round.
After all N rounds have been completed, each player gets to keep the gift that is in front of them.
Is it possible that after this protocol is completed, there will be two people (A and B) who each prefer the gift that the other one ended up with to the one he ended up with? (Assume that each participant has a strict preference ordering over the available gifts, and that each time a participant makes a selection, that he chooses the gift he most prefers out of those that are available for selection.)