I'd like to think about and even discuss this ultra-fascinating question — *without* knowing the answer (or hints) — with others in the same boat. So, would it be OK if anyone posting a spoiler about this adds the word SPOILER to the subject line? If that wouldn't screw up threading or anything too badly. —Dan
On May 19, 2017, at 1:36 PM, Cris Moore <moore@santafe.edu> wrote:
There is a variant where you have agreed to meet a friend in Vienna, at the Cafe Mozart. You arrive in the city, and find to your horror that there are N cafes called Cafe Mozart. Each day, you and your friend each go to one of these cafes at noon, hoping to see each other. How can you minimize the expected number of days before you meet?
This problem is fairly easy if you and your friend agree on your roles in advance. For instance, one of you can go to the same cafe every day, while the other goes through all N in random order, then the expected time is N/2.
It gets more interesting if you don’t have such a prior agreement, so that you and your friend have to follow the same randomized strategy. In that symmetric case, can you achieve an average less than N?
[Spoiler]