In the Paircity there are married couples numbered from to . On the New Year's eve, each man congratulated two women from couples whose numbers differ by one. It turned out that for any two men from couples whose numbers differ by one, there is a woman who received congratulations from both of them.
Prove that at least one man congratulated his wife.
Call a man *leftside* if he congratulated women from couples with numbers less than his own, otherwise call him *rightside*. Clearly, the man from the first couple is leftside and the man from the -th couple is rightside. Hence, there is a number , , such that the man from the -th couple is leftside while the man from the -th couple is leftside. The numbers of couples of these men differ by one, but they congratulated four different women — a contradiction to the problem condition. Consequently, at least one man congratulated his wife.