A mother has twelve children, each born in a different month. They want to go to the beach. She says she’ll take them if they can win a game. She puts the name of each child on a card and tells them she will place the cards face-down in a row on a table in the next room.
She’ll randomly call one child in. The child can turn over cards one at a time, up to half the cards, looking for his or her own name.
If that child finds his or her own name, he or she will be sent outside to play, and won’t be able to communicate with the children still waiting to take a turn. The mother will turn all the cards back face-down, keeping them in the same order, and will randomly call in another child and repeat the process. In order for the children to win the game and go to the beach, all the children must be successful in finding their own names. If any child fails, the game is over, and there will be no trip to the beach! The children can consult each other before their mother starts the game, but those who have already taken a turn cannot contact the others or leave any clues for them.
The children talk among themselves and devise a strategy that all the children will be able to follow perfectly. The game begins, and the first child is called into the room where the game is taking place. A few minutes later, he comes back into the room with the other children, grinning widely. “Pack your swimsuits and your towels!” he says. “We’re going to the beach!”
The child is correct, and knows for certain that the inevitable outcome of the game is that the children will win. How many cards did he turn over before he found his name?
puzzle by Harvey Lerman
permutations n Combinations