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.
Problem
Source: 2013 Baltic Way, Problem 8
Tags: induction, combinatorics unsolved, combinatorics
31.12.2013 03:01
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.
17.11.2014 09:17
Re-used (or re-discovered) here http://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&t=607589&p=3655031#p3655031.
28.11.2019 19:26
Here's an interesting algorithmic solution. The answer is 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 ¯G denote the complement of a graph G. We claim that f(G)+f(¯G)≤|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(¯G)≤n+1−k, which would finish. Let A1∪A2∪⋯∪Ak be a partition of v(¯G) so that the subgraph of ¯G induced by Ai is empty for all 1≤i≤k. Define the value of a complete graph to be its number of vertices minus 1. We wish to show that ¯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 Ai and some vertex in Aj, for each 1≤i<j≤k. WLOG we can assume that there is exactly one edge connecting a vertex in Ai and a vertex in Aj, 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 A1,A2,⋯,Ak. 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 ith step, we will "split" the vertex corresponding to Ai into however many vertices are in Ai. These vertices of our new graph correspond to the vertices in Ai of the original graph ¯G. For each complete graph in the list which contained the vertex Ai (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 A1,a,b,c,d, and we split A1 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 ¯G, etc. After applying these i steps, our graph is now identical to our original graph ¯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 n−1. ◻