A certain town is composed of n
couples. At least one
husband is
cheating on his wife. Now, each wife knows which husbands cheat, and which don't, except she does not know if her own husband is cheating on her or not.
One day, the mayor of the town declares to the wives: "there is at least one husband here who is cheating on his wife. If you know that your husband is cheating on you, bring him to the public square the next day."
The problem is: if there are k cheating husbands, how long till all the husbands are reported? Prove it.