|
|
| (One intermediate revision by one other user not shown) |
| Line 1: |
Line 1: |
| − | Let us start with arbitrarily breaking up the group of students into 2 groups, one in each room. Let the size of the largest clique in one room (room A) be n and the size of the largest clique in the other room (room B) be m. We consider the case where m>n. Let us take one student from room B to room A. This can do one of three things, it can decrease the difference between the size of the largest clique in room B and the size of the largest clique in room A by a factor of 0,1 or 2. We repeatedly perform this operation until for some k the largest clique in room A has size k, and the largest clique in room B has size k+1.
| + | ''Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please [{{fullurl:{{FULLPAGENAME}}|action=edit}} add it] to this page.''<noinclude> |
| | | | |
| − |
| + | This template is to be placed on problem pages, to encourage users to post alternate solutions.</noinclude> |
| − | We consider two cases. Case 1- Let the number of k+1 cliques in B be 1. This case has two subcases. If the number of k cliques in room B has size 1 then since the largest clique cannot be of size 2k+1, we can send one member of the k+1 clique in room B to room A without disturbing the size of the sole k clique in room A. This gives us the largest size of cliques in each room to be k. Second subcase- If the number of k cliques in in room A is more than one. Given any k clique in A there is a member of that clique such that it is not friends with all of the members of the k+1 clique in B, or else the largest clique overall would have size 2k+1. If such a member named "a" is contained in all of the k cliques in A then there is a member named "b" of the k+1 clique in B who is not friends with a, and we send b to room A which gives us the size of the largest clique in both rooms as k. If such a member "a" is not contained in all of the k cliques, then we send it to room B thereby decreasing the number of k cliques in room A by 1. This process continues until either we have 2 k+1-cliques in room A, which will be the next case, or we have 1 k-clique in room A and 1 k+1-clique in room B which is the previous case.
| |
| − | | |
| − | Case 2- The number of k+1 cliques in B is 2. Let the 2 cliques be C,D. If there is a student "a" in C\D or D\C such that sending a over to the other room increases the size of the largest clique in room A by 1, then we do so and finish our job. In the other case we assume this is not possible. Now there is an "a" in C\D and a "b" in D\C such that a and b are not friends, otherwise the cliques C, D would be the same. We send a,b to the other room. This finished our job since sending a,b to the other room does not increase the size of any k clique in room A by assumption and since a,b are not friends it does not increase the size of a k-1 clique by 2.
| |
| − | | |
| − | Case 3- The number of k+1 cliques in B is more than 2. Let C be the intersection of all these k+1 cliques. Now consider a k+1 clique E. If there is an "a" in E\C such that sending "a" to room A increases the size of a k clique by 1 then we send "a" to room A to finish the job, since removing "a" does not affect the size of all of the k+1-cliques in B. If not then we still send "a" to room A decreasing the number of k+1 cliques in room B by 1. We continue this process until either we finish the job or the number of k+1 cliques in room B is 2, in which case we are in case 2.
| |
Latest revision as of 22:05, 24 June 2010
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
This template is to be placed on problem pages, to encourage users to post alternate solutions.
