The Halloween Captain
Smash Master
QFT - kinda. I still think the mayor was only allowed to talk about his own wife though, and then there would be the men whose wives cheat on them who would respond 38, but that is correct, a person who can't find someone who will say there are forty cheating wives shoots his wife at midnight.If the men are perfect logicians, then one who doesn't have a cheating wife or have no wife at all will know of 40 other wives that cheat. Men who have cheating wives will know of 39 women that cheat. A husband cannot be told about his own wife, but he can ask a man without a wife the general question of, "how many women in town are cheating?" (the mayor was allowed to say 1 wife cheats, so I assume this is ok) The answer would be 40. Therefore a man who has 40 by his count as well knows his wife is clear. Any man whose count was 39 shoots his wife in the square at midnight.
EDIT: Hylian's explanation is actually much stronger, better, and requires less communication.