Slowing down and a riddle

Lately I am more busy due to research and postdoc applications. Therefore, I have decided to slow down the blogging for the next 2.5 months. I will definitely keep posting, but at a slower pace and probably not long and technical posts.

To have something more interesting in this post, here is a nice combinatorial riddle that I heard a few days ago. There are 100 boxes, each containing a unique number between 1 and 100 (that is, we can think of the boxes as a permutation of the numbers 1–100). Alice looks at the boxes, chooses a number $x$, and tells Bob to find the box that contains $x$. Bob has to find $x$ by opening at most 50 of the boxes. Assuming that Alice wants Bob to fail, she can pick an arbitrary number $x$, and then Bob has no strategy that will guarantee his success (or even a probability larger than 0.5 for success). To make this more interesting, assume that before Alice arrives, Bob’s friend Charlie can look at all the boxes, and switch between the locations two numbers.

That is, the chain of events is as follows. First, Bob and Charlie can devise a strategy. Then, Charlie looks at all of the boxes, and is allowed to switch the locations of two numbers. Then, Alice looks at all of the boxes, and chooses a number $x$. Finally, Bob needs to find $x$ by opening at most 50 boxes. How can this be done?