Hacker News Reader

Comment by cbau | Hacker News Reader

This is a great explanation.

Is this problem useful for anything? I've seen multiple variations of these prisoner problems now, and I can never remember any being useful in other contexts.

View on HN

Well, first of all it's a puzzle so it's useful as something fun to think about. Math is kinda like science though, you never know exactly how or if a particular discovery will be useful. In this case maybe you could find some graph traversal scenario where this would be applicable. In the Wikipedia article under variants they mention

> If the number of team members and the fraction of boxes which are opened is fixed, the winning probability stays strictly larger than zero when more empty boxes are added

Replace boxes with nodes and now you have some math to determine graph traversals. Maybe a bit more math and you can expand it for multiple paths. I don't know though, I'm not a mathematician and I don't normally have to do more than DFS and BFS in coding interviews, but sure I can see some way that this might be useful.

Genetics for one. If a DNA primer-pair is looking for it's complement [0], then this strategy could be useful. Here the prisoners are the complementary primers and the DNA-sequence-to-be-matched-to is the cabinet. Shepherding proteins/histones could restrict in a nucleic bottleneck of some sort, such that only one primer gets to go at once without repeating [1]. Only when the primers are all set-up is the DNA 'free' to be transcribed or some such thing.

[0] For a sequence like ATGC, the primer is the opposite nucleotide, therefore the 'matching number' would be not ATGC as well, but TACG.

[1] Look, bio is weird, like, jumping genes are actually a thing. This set-up, though strange, is not as unreasonable as a lot of stuff that goes on.

It sounds like a parallelization algorithm. Spin up a hundred threads each whom does not need to communicate with anyone.

Reply on news.ycombinator.com