vineri, 6 noiembrie 2009

[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.

Un comentariu:

  1. se face prin inductie matematica

    fie k=100 barbatii care inseala

    luam k= 2

    si avem barbatA si barbatB care inseala

    inseamna ca sotieA stie ca barbatB inseala si sotieB stie de barbatA

    acu sotia A gandeste asa ...

    daca sotie B ar sti ca si sotB ar insela atunci l-ar fi omorat

    pentru ca ar fi avut dovada

    cum nu era mort

    inseamna ca in momentul asta sotie A stie ca sotie B stie de un alt adulter sotA si sotie A deduce ca si A a inselat

    deci il omoara pe A

    si mai departe va sti si B si asta il omoara pe B

    se presupune ca e valabil pentru k = 99

    si se demonstreaza pentru k + 1

    foarte simplu

    in locul lui A consideri Grupul k si pentru B acel + 1

    cum din inductia matematica stii ca grupul k mor toti

    rezulta ca va muri si al k+1 lea