Mathematical puzzle with a connection to blindfold solving

[bubbagrub]

I came across a mathematical puzzle today that has a very non-obvious solution:

https://en.wikipedia.org/wiki/100_prisoners_problem

Interestingly, if I'm understanding it correctly, the solution depends on the fact that permutations of numbers tend to have cycles in the sense that we mean when memorizing for blindfold solving. So the frustrating case for BLD solvers where you have a lot of cycles is the good case for this logic puzzle where your prisoners can survive.

Maybe this is something someone here has come across before, but I had not, so I thought I'd post it in case it's of interest to others.

 

[PenguinsDontFly]

bam and bam

I saw this a while ago but never thought about how it relates to bld.

 

[Matt11111]

bam and bam

I saw this a while ago but never thought about how it relates to bld.

Same. I watched the video and... Hi RedKB.

 

[PenguinsDontFly]

Same. I watched the video and... Hi RedKB.

whaaa?

 

[Matt11111]

whaaa?

RedKB left a comment about blind solving on the video

 

[kinch2002]

Interesting application of cycles. Never really looked into the actual formulas required to analyse probabilities of cycle lengths before. I think I've seen some probabilities surrounding bld cycle lengths on this forum somewhere though...

 

[Lucas Garron]

Interestingly, if I'm understanding it correctly, the solution depends on the fact that permutations of numbers tend to have cycles in the sense that we mean when memorizing for blindfold solving.

Well, any permutation of numbers will have cycles. The critical part of the puzzles is that if your set is pretty large (say, 100) and your permutation is (uniformly) random, then it becomes very unlikely for any single cycle to be large (say, more than half the number of items).

When you pick a starting place, the chance that the cycle ends (i.e. repeats) is only 1/100. The chance that the cycle ends after he second piece is 1/99, and so on.
By the time you have only a few pieces left, there's a good chance the cycle will terminate.

In between (around the 1/50 mark), the chance is moderate. The prisoner problem exploits that fact.

I don't actually know off-hand the average number of cycles a random permutation will have. Maybe someone else will chime in.