Prison Switcharoo

Puzzles during the interview -- show others how smart you are by giving clever puzzles. Watch them struggle, make them feel bad for not figuring it out under pressure. Also accept lots of people who can google puzzle answers, or just are really good at solving puzzles. Which, works great if they are running a plumbing company and have to figure out good shapes for your manhole covers, a prison, or are just evil and like to shrink people and throw them into blenders.

Since there's a password article on the front page too...

This problem is very clever, and there is a very clever way to solve this, assuming everyone plays nice. However, that solution assumes perfect collusion. These are prisoners we're talking about, so at least in some cases, we have to assume there may be bad actors involved. I mean this is a cute problem assuming the following:

1. All the prisoners have perfect memory (for this problem)

2. All the prisoners actually want to live.

3. The warden is telling the truth

4. The guards are all honest.

These are all the type of assumption that gets websites hacked. So what is the attack surface here?

* One of the prisoners decides this is a fun way to suicide

* One of the prisoners is in gang A, and one is in gang B. They value gang honor above their own life, and need to take out the other.

* A guard has decided that this is a great way to off some "scum"

* A prisoner forgets the algorithm, or hits the wrong switch, or other form of human error.

* As if_by_whisky points out: someone dies before the full run.

* The warden just wants to mess with people before feeding them to alligators, and just states "wrong" whenever someone declares all have visited.

* A prisoner can't handle the stakes, and cracks and makes the declaration early.

* The leader messes up the count.

There are probably a lot more.

Further, the warden is making assumptions that we can't be sure are true. Prisons are notorious for being bad at doing the actual security thing. Are there ways for prisoners to collude and do extra error checking on their end? Can a guard be bribed to help share state? Is there a way to get other prisoners involved in message passing, even if they manage to prevent direct collusion between the selected 23?

I don't know a way around all of these. In fact I'm pretty sure there a some combinations where everyone is just fucked. But, what can be done to add robustness to this problem? It seems pretty silly for prisoners (likely malicious actors as a generalization) will follow the rules and stay within the constraints the warden sets out.

I ask, because I've solved plenty of things in a nice elegant way, that were trivially broken by not assuming everything will play nicely in the environment. Similarly I've broken plenty of "awesome solutions" by asking questions about assumptions. The difference between the algorithmic solution and the real world is sometimes surprisingly large. Just some food for thought :)

I'm a bit sleepy, but I can't get this to work. For 3 prisoners, what if the sequence is (P1 T P1 T P1 T P1 T P2 P2 P2 P2)? Where T is the tally keeper. They've all gone the same number of times (given enough time), but the tally keeper would declare that they had all flipped a switch before P2 had gone in at all. Thus, alligators.

Did I miss something?

The solution could take years, even decades to solve - all depending on how often the warden brings in a prisoner. I'd rather wait out my prison term, hope to be released early for good behavior.

Each person will only toggle A to the 'on' state twice.