Problem

Source: 2013 Baltic Way, Problem 8

Tags: induction, combinatorics unsolved, combinatorics



There are n rooms in a sauna, each has unlimited capacity. No room may be attended by a female and a male simultaneously. Moreover, males want to share a room only with males that they don't know and females want to share a room only with females that they know. Find the biggest number k such that any k couples can visit the sauna at the same time, given that two males know each other if and only if their wives know each other.