Here is my solution: One has to show that all subsets of the new set are good. From the condition we already know that all the subsets without Bob are good. Now one hast to prove that all the subsets with Bob are good. In order to show that look at a good distribution of people of a set without Bob. If there are acquiantances of him in every room then he needs a new room. If there is a room without an acquiantance of him he goes into this room. Obviously the distribution in both cases is good. A bit to easy in comparison to the others I think...

Max(i) wrote: If there are acquiantances of him in every room then he needs a new room. Room only with Bob is very bad. Because it's possible that Bob has acquiantance in any room, but now we cann't choose a person from each room and Bob so that all choosen persons are acquainted with each other. (because people that acquainted with Bob may be not acquainted with each other). My solution is here: It is obvious that good group is graph such that chromatic number of this graph is equate size of maximal clique. Obvious that all group without Bob is good, and all group with Bob, but without Alice is good too. (because we can exchange Bob with Alice and get a similar group withot Bob). So we need to look at groups with Bob and Alice. Lets $ G$ will be some of those groups. And let $ k$ be a size of maximal clique in group $ G$ without Bob. If in $ G$ size of maximal clique is bigger than $ k$, then we can paint $ G$ without Bob in $ k$ colours, and paint Bob in new colour. In that way we will get not more than $ k + 1$ colours in $ G$ and size of maximal clique in $ G$ at least $ k + 1$. So that's ok. If in $ G$ size of maximal clique is again $ k$, then there is no maximal clique with Alice in graph $ G$ without Bob. (else this clique with Bob will have size $ k + 1$). So we can paint $ G$ without Bob in $ k$ colours and then look at Alice colour. Let it be $ green$. There are $ green$ man in every clique with size $ k$. (because people in this clique have different colours and so there are all $ k$ colours in every maximal clique). Lets take all $ green$ people except Alice and turn they all out for some time. In our new graph $ G$ without Bob and those $ green$ people size of maximal clique lesser than $ k$. (Because in every maximal clique we turn out at least one man). So we can colour $ G$ without Bob and $ green$ people in $ k - 1$ colours. Then we paint Bob and all $ green$ people in new colour and add them to our graph. Nobody from $ green$ people isn't acquainted with Bob and with each other (because in $ G$ without Bob they all and Alice have one colour). So this painting of $ G$ in $ k$ colours is correct. So again size of maximal clique is equate chromatic number.

I have a question! Can Bob know anyone who is not acquianted with Alice?

limsk1 wrote: I have a question! Can Bob know anyone who is not acquianted with Alice? I think he can...

limsk1 wrote: I have a question! Can Bob know anyone who is not acquianted with Alice? NO! He can't.

I'm quite impressed that high schoolers were asked to (and probably did) solve this problem! I like Akella's solution, and I'd like to restate it here in case anyone doesn't have the specific knowledge to follow it: A clique is a group of people who are pairwise connected (all mutual acquaintances). The chromatic number of a graph (group of people) is the fewest number of colors required to color each person so that no two people who are acquainted have the same color. A maximum clique (not to be confused with maximal clique -- any clique which is not a subset of any other clique) is a clique of maximum cardinality (of which there could be more than one). A crucial point is that the chromatic number of any graph must be at least as large as its maximum clique (because any clique requires that each member is colored differently). From the problem statement, we can see that the chromatic number of a good group is not larger than the the cardinality of its maximum clique: if the maximum clique (call it C) has cardinality k, then each clique member requires his own room (with corresponding color), and if anyone required a color beyond that, he'd need a new room, but wouldn't be part of the maximum clique (as required by the problem statement). This also means that every maximum clique uses the same k colors as C. So, now we look at various cases for subsets G of the new party: * Bob is not in G: then G is good by assumption. * Bob is in G but Alice is not: Bob can take the spot Alice would have had by assumption. * Bob and Alice are both in G: Remove Bob for a moment and consider a good rooming scheme. Let Alice's room be green. If Alice is part of a maximum clique, then Bob can be placed in his own room. So suppose not. Then we can temporarily remove all the other green people from the graph, and the leftover people can be placed into k-1 rooms (because a green person is required to form a clique of size k). Now add back the green people + Bob into their own room. The maximal clique is again size k, meaning that it contains someone from the green room, so the scheme is again good.

Note that this follows easily from the strong perfect graph theorem. https://en.wikipedia.org/wiki/Strong_perfect_graph_theorem Assume after adding Bob there is a (hole/antihole) of odd length. Then if this (hole/antihole) lacks Alice, it existed before as we can replace Bob with Alice. Else it contains Alice. If Bob and Alice are not adjacent, then if Bob has two neighbors C and S, then Alice knows C and S and so this can be used to make an odd (hole/antihole). If Bob and Alice are adjacent in the cycle, then say Bob neighbors R while Alice neighbors T. Then Bob knows T and Alice knows R, contradicting the fact that the induced graph is a hole. Note that the letters stand for the surnames of the people who proved the strong perfect graph theorem.