←back to thread

New Proof Settles Decades-Old Bet About Connected Networks

(www.quantamagazine.org)
93 points rbanffy | 1 comments | 20 Apr 25 17:48 UTC | HN request time: 0.246s | source
Show context
programjames ◴[21 Apr 25 00:28 UTC] No.43747600[source]▶
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.

replies(4): >>43747678 #>>43748061 #>>43748084 #>>43748417 #
thaumasiotes ◴[21 Apr 25 04:03 UTC] No.43748417[source]▶
Does that puzzle have a name, or a place to read more about it?
replies(1): >>43748571 #
programjames ◴[21 Apr 25 04:47 UTC] No.43748571[source]▶
Problem 7 here: https://mathcontest.unm.edu/PastContests/2016-2017/2016-2017...

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

replies(1): >>43749117 #
1. thaumasiotes ◴[21 Apr 25 07:03 UTC] No.43749117[source]▶
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".)