[Problem] Intresting problems

100 Married Couples

Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announces that at least one husband has been unfaithful. What happens?

Answer it is here.

Solution 1:

1st Night: If only one has cheated.

There is only one wife who has list of cheated husband count as zero and she kills her husband. One husband is killed.

2nd Night: If no killing happens 1st night.

The wifes with count of cheated husband as one, will kill their husbands. Two husbands are killed.

3rd Night: If no killing happens 2nd night.

The wifes with count of cheated husband as two, will kill their husbands. Three husbands are killed.

nth Night: If no killing happens (n-1)th night.

The wifes with count of cheated husband as (n-1), will kill their husbands. n husbands are killed.

Solution 2:

Nothing happens.

If every husband cheats and every wife knows when another woman's husband cheats, then every wife is already aware of cheating in the village. The queen has introduced no new data.

Furthermore, if each wife is aware of 99 instances of cheating and we assume she isn't stupid, she can probably surmise through induction that all 100 husbands have cheated. If word gets out, it will be a bloodbath. The entire community will be destroyed. The only solution is to never, ever seek out any information that would prove that her own husband is unfaithful. If everyone keeps quiet, the burden of proof rests with the queen alone.

Essentially, it's a classic "garbage in, garbage out" problem. The wives subvert the data-collection process, and the algorithm fails for lack of input validation.

12 coin problem

you have 12 coins. one of them is counterfeit. all the good coins weigh the same, while the counterfeit one weights either more or less than a good coin. your task is to find the counterfeit coin using a balance-scale in 3 weighs. moreover, you want to say whether the coin weighs more or less
than is should and, and this is the real kicker, your weighs must be non-adaptive. that is, your choice of what to put on the balance for your second weigh cannot depend on the outcome of the first weigh and your decision about what to weigh for round 3 cannot depend on what happened on either your first or second weigh. for example, you can't say something like "take coin #1 and coin #2 and weigh them. if they balance, then take coins 3,4,5 and weight them against 6,7,8...if 1 and 2 don't balance, then weigh #1 vs #12..." you
have to say something like:

round #1: do this
round #2: do this
round #3: do this
if the results are left tilt, balanced, and left tilt, respectively, then coin #11 is heavier than it should be.

Answer it is here.