In a monastery, there is a special rite to elect new novices. All candidates (we're talking of a huge number, so let's assume an infinite amount) gather together in one hall that gets locked, so that nobody can get in or out. There is no communication with the outside at all.
Now the magic starts and the elder monks perform a spell somewhere outside this room, which makes a symbol appear on the forehead of each candidate that will become a novice. No one can see his own forehead, and there are no mirroring surfaces in the hall. Talking or giving signs is strictly prohibited!
So after this has happened, the candidates have the following task:
Every full hour the door will be opened. Then there are two possible options. Either ALL novices with the symbol on their forehead leave the room together, or nobody leaves the room at all. They have to finish the rite in as little time as possible, but without breaking any rules, which would have bad (very bad, I assure you) consequences for the candidates...

So now your task is: There is a random number n between 1 (inclusively) and the amount of candidates (almost infinite) of newly elected novices that have the sign appear on their forehead. How many hours h will the rite take at least, depending on the value of n? Or the other way round: When the novices leave the room after h hours, how many novices got elected?

This should be a pretty easy question. Any ideas?

  • $\begingroup$ I think this is the same problem as this $\endgroup$
    – Trenin
    Jan 27, 2015 at 13:01
  • $\begingroup$ Pretty much. Only the knowledge given by the oracle is presumed by everyone here. Not a bad phrasing, though. $\endgroup$
    – dmg
    Jan 27, 2015 at 13:03
  • $\begingroup$ Okay, I have to admit the solution strategy is quite the same. It is only wrapped in slightly different words and, as I think, easier to understand conditions. Sorry for double-posting, I did not find that one... $\endgroup$ Jan 27, 2015 at 13:07


Browse other questions tagged or ask your own question.