99 Ninja missions and a single lantern From http://blog.liveramp.com/2014/01/30/the-case-of-ninety-nine-ninja/:

A team of 99 ninja are each sent out on individual missions by their master. Their master tells the ninja that one of them must come back to the fortress and tell him when all 99 missions are complete - if this ninja is wrong and any mission is incomplete, they will all be slain for incompetence. These ninja are strictly prohibited from seeing each other while outside their fortress, lest they be discovered - they may never meet in person, and may only communicate through a single lantern left in the darkest part of the forest, which they may either turn on or off. Each ninja can visit the lantern whenever he or she wants - there is no danger of accidentally overlapping with another ninja. What plan of communication should the ninja put in place so that at least one of them knows when to return to the fortress?


This is a variant of a classical problem. Before leaving, they choose one ninja who will report back to the master. Each ninja goes and completes his mission. When he is done, he returns to the lantern. If he finds the lantern off, he turns it on. If he finds it on, he leaves without doing anything. The only ninja who is allowed to turn off the lantern is the ninja chosen to report back to the master. You should be able to figure it out from here.
