techInterview Discussion

There is a group of devotees for a saint and they attend a meeting everyday. The saint makes a mark on heads of few devotees and says that if they found that their head has a marking, they shud not come for the next day's meeting. Each devotee can see others head, but not his own. They cannot communicate with each other. All the devotees attend the meeting for 5 days, on the 6th day, people having the markings over their head do not attend the meeting, while the other continue. How many markings did the saint make?

Make all asumptions needed for this kind of puzzles.

The saint made 5 marks.

If you assume that the saint made at least one mark then you can prove the following statement using mathematical induction:

"If the saint made n marks then n disciples will fail to attend the meeting on the (n + 1)st day."

Yes.

Sajid,

Can you please explain your answer in some details.
Thanks.

Asrarahmed

Sure ...

We will prove the following statement using mathematical induction, under the assumption that the saint made at least one mark:

"If the saint made n marks then n disciples will fail to attend the meeting on the (n + 1)st day."

(a) Suppose n = 1.

Everyone will attend the meeting on the first day.

The disciple with the mark on his head will notice that nobody else has a mark on his head.

And since he knows that the saint made at least one mark, he will conclude that he is the one with the mark on his head.

He will therefore not attend the meeting on the second day.

Therefore, we have proved the statement is true for n = 1.

Now, we need to prove that if the statement is true for n = k then it must be true for n = k + 1.

(b) Suppose the statement is true for n = k.

Now consider the case when n = k + 1.

Everyone will attend the meeting on the first day.

Each disciple with a mark on his head will see k other disciples with marks on their heads.

Any such disciple will reason that there are 2 possibilities:

1. He isn't marked and there are k marked disciples.

2. He is marked and there are k + 1 marked disciples.

If possibility 1 is true then on the kth day, k disciples will not attend the meeting (under the inductive hypothesis).

But on the kth day, all the disciples attend the meeting (because possibility 1 is not true).

Any such disciple therefore concludes that possibility 2 is true and does not attend the meeting on the (k + 1)st day.

The truth of our general statement follows from (a) and (b) via mathematical induction.

Sajid,

Thank you so much for the explanation.

Sajid, I had a doubt.

In the induction proof you wrote
"Suppose n = 1.
Everyone will attend the meeting on the first day.
The disciple with the mark on his head will notice that nobody else has a mark on his head."

Won't every person be in this position? I mean every  person would see that theres no mark on any other persons head, and hence "will"(i think) assume that he is the one whose head has a mark.

Please can you clarify?

Z-
Everyone else would see mark on 1 person's head .. think carefully.