New Proof Settles Decades-Old Bet About Connected Networks

69% looks surprising like the answer to this puzzle:

> The numbers 1–n are randomly placed into n boxes in a line. There are n people who are each able to look into half the boxes. While they are allowed to coordinate who looks into which boxes beforehand, they are taken out one at a time to choose which half of the boxes they will peek at. The goal is for the first person to find the number one, the second person to find the number two, and so on. If any of them fail to find their number, the whole group loses. What is the probability they lose if they use the optimal strategy?

I wonder if there's a connection to regular graphs here.

So you alternate so that you're always looking at as many new boxes as possible? Or are the people allowed to communicate?

The quanta article talks about the connections to regular graphs.

> 69% looks surprising like the answer to this puzzle:

Haven't read the paper, but wonder if this is the same ln(2) that comes up as the constant in rate monotonic scheduling.

Does that puzzle have a name, or a place to read more about it?

Problem 7 here: https://mathcontest.unm.edu/PastContests/2016-2017/2016-2017...

Or a Veritasium video here: https://www.youtube.com/watch?v=iSNsgj1OCLA

If you'll take a followup question: what is the best that can be achieved if you must decide which boxes to open before seeing what's inside any of them?

(That was how I understood the original description, and I was having a really hard time imagining a strategy other than "make sure there is an assignment of numbers to boxes that can satisfy the plan".)