Credit for this problem goes to Dennis Shasha, TED-Ed. Thanks!

Cursed Temple

You, and a group of 8 friends, are exploring a temple. You enter the temple through a tunnel, and come across a large central room. At the center of the room stands an alter, on which there is a green skull. There are also five tunnels leading outwards from this room, including the one that you just came from.

After a few hours of exploration, you find yourself back at the central room. Suddently, the walls begin to shake and the green skull on the alter lets out two puffs of cursed smoke. Then, a ghost appears stating that, in exactly one hour the temple will collapse. The ghost also states that two people have been affected by the cursed smoke, affecting their truth-telling abilities. For the next hour, they may not always tell the truth (but still might).

You know that you aren’t cursed. You know that one of the tunnels leading out from this room leads to the exit, however you’ve forgotten which one! Luckily, you do remember the tunnel that you just came from, which clearly does not lead to the exit. You also know, somehow, that exploring each tunnel takes 20 minutes.

How can you split up you and your eight friends into search parties such that you maximize your chances of getting out before the temple collapses?

Solution