Microsoft Interview Question
Software Engineer / Developersi agree - here is a simpler explanation.
if there has not been a dunking on a previous night then every man who sees k crowns dunks their wife on the (k+1)th night.
proof: fix c>=1. The n-c men without crowns all see c crowns and the c men with crowns all see c-1 crowns. This second group all dunk on the cth night, so the first group never dunk.
-------------------
I don't know if this is permitted under the rules, but it can be done on the first night if one person can reveal one bit of information: for man i, let P_i be the parity of the crowns seen by i. Choose some guy A, who writes P_A into the sand. Then person i has a crown iff P_i + P_A = 1 mod 2, so each man can dunk their wives correctly on the 1st night.
It just takes 1 midnight to remove all crowns. For any two men A and B, A is allowed to ask B such a question: how may crowns does the genie put on the men according to your observation ? If B's answer is equal to what A himself observed, then A know eithor both A and B have a crown or none have; Otherwise, only one of them has a crown. So, A could find out if he has a crown because A also could observe if B has or not, although B is not allowed to directly tell A if A has or not. B could also ask A or anybody else the same question, and so on. Therefore, after the genie put crowns on the men by the midnight, the men could find out everything at once.
by Jimmy
This solution is based on the assumption that the men know that there is atleast some one whose wife has cheated that is the value of c>0 but doesnt know the exact value of c. Also all can see whether a wife is dunked at midnight or not.
- Sudharsan February 14, 2006Lets consider the cases,
If c=1,
Then the person who has a crown on his head knows that there is atleast one such man whose wife has cheated. And moreover as he doesnt see any other with a crown, he will conclude that he is the 'one' and dunk his wife the 1st midnight.
if c=2,
Lets look at one of the 2 mens point of view. He knows that there is atleast one wife has cheated and he also sees a crown on another's head. He will assume that the other is going to dunk his wife on the 1st midnight. This is what the other person will also be thinking. Hence both of them will wait for the other to dunk their wives. However as this doesnt happen they will come to realize there is one other's whose wife has cheated and the other one is none but himself. Hence both will dunk their wives the 2nd midnight.
if c=3,
The man with the crown sees 2 others with crown and waits for 2 days without seeing any one dunking their wives and hence concludes his wife also cheated on him and hence he (along with the other 2) dunks his wife on the 3rd midnight.
generally,
similarly for any c all the men whose wife has cheated on them dunk their wifes on the cth midnight.
-Sudharsan