Couples in a Sauna

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Couples in a Sauna

G H J

Reveal topic tags

combinatorics unsolved

L

G H BBookmark kLocked kLocked NReply

Source: 2013 Baltic Way, Problem 8

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

418 posts

#1 h Dec 31, 2013, 12:14 AM • 2 Y

Y by Adventure10 and 1 other user

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

15142 posts

#2 h Dec 31, 2013, 1:01 AM • 7 Y

Y by FlakeLCR, hakN, Adventure10, Mango247, and 3 other users

That maximal $k$ is equal to $n-1$ . We can easily see this is true for $n=1$ (and as easy for $n=2$ ), and if $n$ couples all know each other, then they need $1$ room for the females and $n$ rooms for the males, so $k<n$ .
Assume by induction that $n-1$ couples can be accomodated by a sauna with $n$ rooms, and consider a sauna with $n+1$ rooms. Then for any $n$ couples, set one aside and accomodate the remaining $n-1$ couples in $n$ rooms, by the induction step. If actually less than $n$ rooms are used, there remain two rooms to accomodate the members of the leftover couple, so assume $n$ rooms are used. The only way the male of the leftover couple cannot share an already occupied room is if he knows (at least) one male in each of the $m$ rooms occupied by males. The only way the female of the leftover couple cannot share an already occupied room is if she does not know (at least) one female in each of the $f$ rooms occupied by females. But $m+f = n$ , while the number of couples known / not known by the leftover couple is only $n-1$ . This means the male or the female of the leftover couple should be able to share an already occupied room, and the other may use the empty $(n+1)$ -th room.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

15142 posts

#3 h Nov 17, 2014, 7:17 AM • 7 Y

Y by FlakeLCR, AlastorMoody, Adventure10, Mango247, and 3 other users

Re-used (or re-discovered) here http://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&t=607589&p=3655031#p3655031.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

578 posts

#4 h Nov 28, 2019, 4:26 PM • 2 Y

Y by alinazarboland, Adventure10

Here's an interesting algorithmic solution.

The answer is $\boxed{n-1}.$

To see that $n$ fails, simply let none of the couples know each other.

Now, let's show that $n-1$ works.

For a graph $G$ , we will let $f(G)$ denote the minimum number of sets that its vertices can be split into such that the induced subgraph of $G$ by each of the sets is complete.

Let $\overline{G}$ denote the complement of a graph $G.$

We claim that $f(G) + f(\overline{G}) \le |v(G)| + 1$ , for any graph $G.$ This would clearly imply the problem.

Set $f(G) = k,$ and let $|v(G)| = n.$

We will show that $f(\overline{G}) \le n+1-k$ , which would finish.

Let $A_1 \cup A_2 \cup \cdots \cup A_k$ be a partition of $v(\overline{G})$ so that the subgraph of $\overline{G}$ induced by $A_i$ is empty for all $1 \le i \le k.$

Define the value of a complete graph to be its number of vertices minus $1.$ We wish to show that $\overline{G}$ can be partitioned into some number of complete graphs with total value at least $k-1.$ This would finish.

Notice that there is always an edge between some vertex in $A_i$ and some vertex in $A_j$ , for each $1 \le i < j \le k.$ WLOG we can assume that there is exactly one edge connecting a vertex in $A_i$ and a vertex in $A_j$ , as else we can just remove one to make this problem strictly harder.

Create another graph on $k$ vertices which is initially complete. Associate to each vertex one of the sets $A_1, A_2, \cdots, A_k.$ Keep track of a list of complete graphs, which is initially just the entire graph. We will perform some steps, after which the sum of the values of the complete graphs is always $k-1.$

Now, we will perform the following $k$ steps in order. In the $i$ th step, we will "split" the vertex corresponding to $A_i$ into however many vertices are in $A_i.$ These vertices of our new graph correspond to the vertices in $A_i$ of the original graph $\overline{G}.$

For each complete graph in the list which contained the vertex $A_i$ (which is now split into different vertices), we can split it into smaller complete graphs with total value the same as its original total value. For instance, if there was a complete graph with vertex-set $A_1, a, b, c, d$ , and we split $A_1$ into vertices $v, w, x$ , then we consider the complete graphs on vertex-sets $\{v, a, b\},$ $\{w, c\}$ , and $\{x, d\}$ instead, where $a, b$ are connected to $v$ in the original graph $\overline{G}$ , etc.

After applying these $i$ steps, our graph is now identical to our original graph $\overline{G}$ , and we now have vertex-disjoint cliques with total value $k-1.$ This means there are at most $n-k+1$ of them, and so the problem is solved.

The answer is $\boxed{n-1}.$

$\square$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a