A princess is living in a palace which has 17 bedrooms, arranged in a line. There is a door between every two neighboring bedrooms and also a hallway which connects them all. Every night the princess moves through the inner doors from one bedroom to another. Every morning for 30 consecutive days you are allowed to go to the hallway and knock on one of the 17 doors. If the princess is inside, you will marry her. What your strategy would be?
You knock on doors: 2, 3,…, 15, 16, 16, 15,…, 3, 2. This makes exactly 30 days. If during the first 15 days you don’t find the princess, this means that every time you were knocking on an even door, she was in an odd room, and vice versa. Now it is easy to see that in the next 15 days you can’t miss her.