The cheating husband problem

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.

If there is one cheating husband, his wife knows that no one else's husband is cheating, so hers must be because there is at least one cheating husband. She brings him to the public square on day one.

If there are two cheating husbands, each wife sees the other cheated-on wife not bring her husband to the public square on day one, and therefore concludes that her own husband is cheating. (The other wife would only bring her husband to the public square if she knew that no other husbands were cheating. Because she doesn't bring him, at least one other husband must be cheating. Because the only unknown value for the first wife is her own husband, she concludes that he must be cheating.) Both wives bring their husbands to the public square on day two.

If there are three cheating husbands, each wife sees the other cheated-on wives not bring her husband to the public square on day one, or day two. Therefore, she concludes that her own husband is cheating. (The other wives must know someone else is cheating, and that someone else must be her husband.) All three bring their husbands to the public town on day three.

Thus, given k cheating husbands, they will all be brought to town on day k. Assuming, of course, that the wives are inclined toward reasoning things out rather than beating their husbands with a frying pan until they 'fess up.