This is very hard problem because I heard that only one chinese solved this problem...

Quote: we suppose that competition contain: $ (G_{i})_{i\in \{1,2,...,g\}}=groups \ not\ clique$ $ (C_{i})_{i\in \{1,2,...,c\}}=cliques$ $ A_{n}=\{C_{i}|\ |C_{i}|=n\}$ and $ G=\{G_{i}\}$ we have $ max\{|C_{i}|\}=2k$ for some $ k$. $ R_{1}$ first room $ R_{2}$ second room $ I)$ if $ |A_{2k}|>1$ we put a clique of $ A_{2k}$ and $ G$ in $ R_{1}$ and the other cliques of $ A_{2k}$ in $ R_{2}$ the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room$ =2k$ $ II)$ if $ |A_{2k}|=1,\ A_{2k}=\{C_{h}\}$ $ 1)$ if $ m=max\{i\in N|\ A_{i}\neq\emptyset,i<2k \}>k$ here we put $ m$ competitors of $ C_{h}$ in $ R_{1}$ and the other elements ($ 2k-m<m$) of $ C_{h}$ in $ R_{2}$ we put $ G$ in $ R_{1}$ and the cliques of $ A_{m}$ in $ R_{2}$ we can put the rest of cliques in $ R_{2}$ for example. the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room$ =m$ $ 2)$ if $ m=max\{i\in N|\ A_{i}\neq\emptyset,i<2k \}\le k$ we put $ k$ competitors of $ C_{h}$ in $ R_{1}$ and $ k$ competitors of $ C_{h}$ in $ R_{2}$ and we put $ G$ in $ R_{1}$ and the other cliques in $ R_{2}$ the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room$ =k$ sorry for my bad english

aviateurpilot wrote: Quote: we suppose that competition contain: $ (G_{i})_{i\in \{1,2,...,g\}}=groups \ not\ clique$ $ (C_{i})_{i\in \{1,2,...,c\}}=cliques$ $ A_{n}=\{C_{i}|\ |C_{i}|=n\}$ and $ G=\{G_{i}\}$ we have $ max\{|C_{i}|\}=2k$ for some $ k$. $ R_{1}$ first room $ R_{2}$ second room $ I)$ if $ |A_{2k}|>1$ we put a clique of $ A_{2k}$ and $ G$ in $ R_{1}$ and the other cliques of $ A_{2k}$ in $ R_{2}$ the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room$ =2k$ I don't know if I misundertsand your idea or not, but you seems didn't consider if two cliques is overlap. e.g. {1,2,3,4} is a clique and {1,5,6,7} is another clique, you can't put 1 in both room anyway

I solved the problem. Here is my idea. For a subset $ A$ of graph $ G$, let $ f(A)$ be the size of largest clique in the induced graph by $ A$. For a partition of $ G$ to $ A,B$, define $ f(A,B)=f(A)-f(B)$. Suppose $ K_{n}$ is the largest clique of $ G$ and split it into two $ K_{n}$'s randomly and put one of the $ K_{n}$'s in set $ A$, and put the other $ K_{n}$ and other vertices in set $ B$. You see $ f(A,B)\geq0$, we can make some operations on the partition and to that at each step $ f$ reduces at most one, and $ f$ is non-positive at the end.

that is also my idea. I reduce it to the case when $ f(A,B)=1$ where each member is part of a $ f(A)$-clique an there exist no two members x,y and clique $ K$ so that the union of $ K$ with x and with y is a $ f(A)+1$ clique.

The following is an idea. Let $ \mathbb{S}_{n}=\left\{ \bold x\in[0,1]^{n}|\left< \bold x,\bold{1}\right> =1\right\}$ and $ f(G)=\max_{\bold x\in\mathbb{S}_{n}}f_{G}(\bold x)=\max_{\bold x\in\mathbb{S}_{n}}\left<A\bold x,\bold x\right>$, where $ A$ is the adjacency matrix of any graph $ G$ with $ |G|=n$. Clearly, $ f$ is an increasing function, so for $ H,G-H\subset G$, $ f(H)\leq f(G)$. It can be proven that if $ \omega (G)$ is the maximum clique number of $ G$, then $ f(G)=\frac{\omega(G)-1}{\omega(G)}$ (How?). We want to prove that there exists a subset $ H\subset G$ such that $ f(H)=f(G-H)$, i.e. $ \max_{\bold x\in \mathbb{S}_{|H|}}f_{H}(\bold x)=\max_{\bold x\in\mathbb{S}_{|G-H|}}f_{G-H}(\bold x)$. Hopefully, this is a correct approach.

actually Omid Hatami f can reduce also by 2 , and in my solution that's where I have to use that the maximum clique is of even size. Where do you use it?

I split a $ K_{2n}$ into two $ K_{n}$'s, and then I do the operations such that at each step $ f$ reduces by at most 1(you must prove that it is always possible, using the maximality of $ K_{2n}$). Obviously before the first step $ f\geq0$, and at the last step all of the the vertices in $ B$, which are not in $ K_{n}\subset B$ will be moved in $ A$, and at last step $ f\leq0$, and everything is proved. If the size of the maximum clique was odd then maybe at the first step and at the last step we had $ f\geq0$, and we could not prove anything. But for odd $ n$, we can prove that it's possible to split vertices in two parts that the size of the maximum clique in each side differ by at most 1.

Yes! that's also my proof (approximately) actually in showing that it can decrease by at most 1 I suppose the contrary (that it can't) and get either a bigger size of the maximal clique or that it has odd size (thus contradiction in both)

I think Omid Hatami has really good idea. But it is not clear (and no any proofs that it is possible) about operations that decreasing f. No lame, no game.

We can prove that by an algorithm. Note by max(Room n) the largest clique size in Room n, where n= 0 or 1 Lema 1. If we move one person from Room 1 to Room 2 then the largest size of a clique in Room 1 will decrease by 0 or 1, and in Room2 it will increase by 0 or 1. Lema 2. If in Room 1 the largest size of a clique is m and in Room 2 - n, then the maximum size of a clique of all persons is not greater than n+m. The algorithm: All persons are in Room 1. Move to Room 2 all except the largest clique. Move persons by one from Room1 to Room2 until max( Room 1 ) - max(Room 2) = 0 or 1 (this is possible to achieve due to Lema 1). If it is 0 then its done. So consider max( Room 1 ) = max(Room 2) + 1 . Move any person from Room 1 to Room2. If max(Room 2) do not increase it is done (in max(Room1) will decrease by 1 as there is only one clique of persons). So consider max(Room 2) + 1 = max(Room 1). Find a person in the largest clique of Room2 which is not friend with all persons from Room 1 and move that person to Room 1, and we get max (Room 1) = max(Room 2) q.e.d. (there exist such a person otherwise all people in the largest clique of Room2 are friends with all persons from the only clique in Room 1 and by concatenating both cliques we get an odd size and it is the largest - from Lema 2). I had a typo, now it is correct.

Quote: Find a person in the largest clique of Room2 which is not friend with all persons in Room 2 and move that person to Room 1, and we get max (Room 1) = max(Room 2) q.e.d. in this step if we have more then one largest clique in Room2, max(Room2) and max(Room1) don't change.

anonymous1173 wrote: Quote: Find a person in the largest clique of Room2 which is not friend with all persons in Room 2 and move that person to Room 1, and we get max (Room 1) = max(Room 2) q.e.d. in this step if we have more then one largest clique in Room2, max(Room2) and max(Room1) don't change. I can't finish this, but I pursued this approach a bit further -- here's a sketch. If there is more than one largest clique in Room 2, take a person in Room 2 who belongs to at least one but not all of the largest cliques, and move him to Room 1. If this increases the size of the largest clique in room 1, we're done, otherwise, repeat until we have a unique clique in Room 2, call it K. If we move any of the persons in K to room 1, we'll decrease max(Room 2) -- if we can do this without increasing max(Room 1), we're good. The problem is that everyone in K could be friends with all of a maximal clique in Room 1. Suppose a person x in K is friends with everyone in a maximal clique L in room 1 -- if there is only one such L satisfying this description for a given person x, we can do the following.. Then not everyone in L is friends with everyone in K, or we would have a maximal clique in our big graph of odd size, so take $ y \in L$ such that y is not friends in everyone in K, switch x to room 1, switch y to room 2, so that max(room 1) is unaffected and max(room 2) decreases by 1. The problem is that there might be more than one clique in room 1 containing only friends of x, and then we would have to move one person from each of those cliques to room 2 so as to keep from increasing max(room 1). At this point I get stuck because I don't see how to assure that max(room 2) will actually decrease if we have to move a bunch of people to room 2.

I think this is enough to finish the most annoying case (when Room 2 has several cliques of maximal size). Let $ A_{1}, A_{2}, ..., A_{n}$ be the distinct (but not disjoint) cliques of maximal size in Room 2. There must be a vertex in $ A_{1}$ which is not in all of the other cliques (proof: if each vertex of $ A_{1}$ were also in all of $ A_{2}, ..., A_{n}$ then, being of the same size, there would be no room in them for other vertices, so they would all be equal to $ A_{1}$, absurd because they are distinct). So we have a vertex $ V$ which is in $ A_{1}$ and possibly also in some other $ A_{i}$ but not in all cliques, so not in, for example, $ A_{l}$. Now, for each clique not containing $ V$ (in this case $ A_{l}$), take a vertex $ V_{l}$ in $ A_{l}$ not joined to $ V$ by an edge. Such a vertex exists because, if $ V$ were joined to all vertices of $ A_{l}$, $ V$ and $ A_{l}$ would form a larger-than-maximum clique. Possibly some of the vertices $ V_{l}, V_{m}$ chosen in this way will be the same; in that case, count it just once. Now we will have a set of vertices of the form $ V, V_{l}, V_{m}$. Move these to Room 1. This will reduce the max clique size in Room 2, because all their maximal cliques have lost vertices, but it will decrease only by $ 1$ (because $ A_{1}$ has lost only one vertex; clearly $ V_{l}, V_{m}$ can't belong to $ A_{1}$ because they are not joined to $ V$, which is in $ A_{1}$). If the max clique size in Room 1 doesn't increase, we're done. If it does, a new larger clique has arisen, containing some of the new vertices. Now, since $ V$ is not joined to the other $ V_{l}$, if the new clique contains $ V$ it only contains $ V$, and all the other $ V_{l}$ can be sent back to Room 2, where all sets to which $ V$ didn't belong will be repaired, and we will be done (since the new clique in Room 1 only contains $ V$ the max clique size in R1 cannot increase by more than 1). If the new clique doesn't contain $ V$, it can contain several of the $ V_{l}, V_{m}$ and the max clique size in R1 can increase by more than one. First bring back $ V$ to Room 2; $ A_{1}$ will be repaired. Now, if m-c-s in R1 has increased by only 1, we're done; otherwise, send back vertices $ V_{l}$ one by one to Room 2. M-c-s in R1 will decrease at most 1 in each step, while m-c-s in Room 2 will not increase (because $ A_{1}$ is already a maximal clique), so at some point we will win.

Severius wrote: I think this is enough to finish the most annoying case (when Room 2 has several cliques of maximal size). OK, but what about the case where Room 2 has only 1 clique of maximal size? That's the case that I'm having trouble with and am finding the most annoying (see my post above) -- am I missing something simple?

Sorry, I didn't read all the above posts in detail ; since what I saw looked similar to my solution I assumed it was the same, and therefore that the most annoying case was the one with several cliques. I will write a sketch of my solution from the beginning to make sure I'm not talking nonsense. First put all vertices in Room 1, and then move them one by one to Room 2. Let max clique size of a room=M(1) or M(2). Each step decreases M(1)-M(2) by at most 2. In the beginning M(1)=2n and M(2)=0, while if we move all vertices to Room 2 M(1)=0 and M(2)=2n, so at some point M(1)-M(2) changes signs; either it becomes $ 0$ at some point (then we're done) or it goes from $ 1$ to $ -1$. Take the situation when M(1)-M(2)=1. Let $ M(2)=k, M(1)=k+1$. If there are other vertices in R1 besides the k+1-clique, move them one by one to R2. It at some point M(2) increases we win. Otherwise all that will be left in R1 will be the clique. Now move one of the vertices in R1 to R2. Then $ M(1)=k$. If M(2) doesn't increase we win; if it increases and several k+1-cliques arise, that's the case we dealt with. Now for the case when only one k+1-clique is created. Let this clique be $ C$. Move a vertex $ C_{i}$ of $ C$ to R1. This will make $ M(2)=k$. So if M(1) doesn't increase, we are done. If it increases, try with another vertex $ C_{j}$. If every vertex of $ C$ creates a k+1-clique when moved to R1, that means every vertex of $ C$ is joined to every vertex of R1, but then in the original graph they made a 2k+1-clique. Then $ 2k+1 \leq 2n$ (the size of the largest clique), and since the LHS is odd and the RHS is even they are not equal so $ 2k+1<2n$. But this is absurd, because $ M(1)+M(2)=2k+1$, and always $ M(1)+M(2) \geq 2n$, since the 2n-clique would generate sub-cliques of sizes adding up to at least 2n.

anonymous1173 wrote: Quote: Find a person in the largest clique of Room2 which is not friend with all persons in Room 2 and move that person to Room 1, and we get max (Room 1) = max(Room 2) q.e.d. in this step if we have more then one largest clique in Room2, max(Room2) and max(Room1) don't change. We cannot have more than one clique with largest size in room 2 at this step, because we just added a person to Room 2 and max(Room 2) increased by one. So that person was added to the one of the largest cliques, and the resulting clique is the new largest and only one. (Note: if the max (Room 2) do not increase by one then the max () value in both rooms have the same value after this step.)

dido, I think what I did was similar to what you did. (I'm not at IMO, but decided to take day 1 today at home for practice. Maybe it's from the lack of a pressured environment, but I somehow got all three problems!) We let the rooms be $ A$ and $ B$. Let the largest clique have size $ 2k$, call the clique $ C$. Start with everyone in room $ A$. Keep moving people from clique $ C$ from room $ A$ to room $ B$. Keep doing this until the largest clique in $ A$ is the same size or $ 1$ bigger than the largest in $ B$. If they're the same size, you're done. So assume the largest clique in $ A$ is one bigger. Then the sizes are $ t+1$ and $ t$, where $ t \ge k$. Because there are $ 2k-t \le t$ members of $ C$ in room $ A$, every clique of size $ t+1$ in room $ A$ has a member who's not in $ C$. If there is a clique of size $ t+1$ in room $ A$ which does not contain all of the members of $ C$ in that room, then move a member of $ C$ who's not in that clique and you're done because both values in question are $ t+1$. If every clique of size $ t+1$ in room $ A$ has all of the members of $ C$ from that room, then you take one person who is not a member of $ C$ from each of these cliques of size $ t+1$ in room $ A$. We can't have $ x$ of these people and $ t-x+1$ members of $ C$ in room $ B$ form a clique, because then those $ t+1$ people and the $ 2k-t$ members of $ C$ in room $ A$ would form a clique of size $ 2k+1$. Therefore, after this move, the largest clique in room $ B$ is still $ t$, while now the largest clique in room $ A$ is of size $ t$ as well, and you're done.

dido wrote: We cannot have more than one clique with largest size in room 2 at this step, because we just added a person to Room 2 and max(Room 2) increased by one. So that person was added to the one of the largest cliques, and the resulting clique is the new largest and only one. (Note: if the max (Room 2) do not increase by one then the max () value in both rooms have the same value after this step.) You can. That particular person we moved can be a part of 2 different, but not disjoint, cliques of the largest size in room 2.

Finally! Valentin Vornicu wrote: In a mathematical competition some competitors are friends. Friendship is always mutual. Call a group of competitors a clique if each two of them are friends. (In particular, any group of fewer than two competitiors is a clique.) The number of members of a clique is called its size. Given that, in this competition, the largest size of a clique is even, prove that the competitors can be arranged into two rooms such that the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room. Author: Vasily Astakhov, Russia Call the rooms $A$ and $B$; suppose $A$ is initially empty while $B$ has all the competitors in it. Let $M$ be the maximum clique of the initial group. Suppose $|M|=2m$. Now, one-by-one pick elements from $M$ and put them in $A$. Let $\mathcal{C}(A), \mathcal{C}(B)$ denote the size of maximum cliques in these respective sets. Initially $\mathcal{C}(B)-\mathcal{C}(A)=2m$ and on each move this decreases by $1$ or $2$. Continue the process as long as it isn't negative; we either obtain $\mathcal{C}(A)+1=\mathcal{C}(B)$ or $\mathcal{C}(A)=\mathcal{C}(B)$. The latter yields a desirable partition so assume we have the former case. Let $\mathcal{C}(A)=k$, then $\mathcal{C}(B)=k+1$. Now let $M'$ be the remnants of former maximum clique $M$ in $B$. Claim. All $k+1$ cliques in $B$ contain $M'$. (Proof) If not; pick an element from $M'$ that doesn't destroy some $k+1$ clique in $B$ and put it in $A$ thus making $A$ a $k+1$ clique. $\blacksquare$ Let $S_1, \dots, S_j$ denote the set of $k+1$ cliques in $B$. Now onwards, we will not meddle with elements in $B$ aside from those in $S=\cup^{j}_{i=1} S_i$. Fix $S_1$ and one-by-one pick elements from $S$ not in $S_1$ and put them in $A$. If at any point $\mathcal{C}(A)$ becomes $k+1$ then we're done. So now we have deposited all elements of $S$ not in $S_1$ to $A$. The maximum clique in $A$ right now (say $T$) has size $k$. Note that all elements of $T$ share an edge with all elements of $M'$ and $|T|+|M'|=2m$ hence $T \cup M'$ is a maximum clique of the entire graph. Thus, if we pluck an element from $S_1$ and put it in $A$; it will not contribute to any maximum clique in $A$. By doing so, we've now made $\mathcal{C}(A)=\mathcal{C}(B)=k$ as desired. $\blacksquare$

After having read the solution in Pascal96's book a long time ago, I finally take the time to write it up now. Take the obvious graph interpretation $G$. We paint red any vertices in one of the maximal cliques $K$, which we assume has $2r$ vertices, and paint the remaining vertices green. We let $\alpha(\bullet)$ denote the clique number. Initially, let the two rooms $A = K$, $B = G-K$. Claim: We can move at most $r$ vertices of $A$ into $B$ to arrive at $\alpha(A) \le \alpha(B) \le \alpha(A)+1$. Proof. This is actually obvious by discrete continuity. We move one vertex at a time, noting $\alpha(A)$ decreases by one at each step, while $\alpha(B)$ increases by either zero or one at each step. We stop once $\alpha(B) \ge \alpha(A)$, which happens before we have moved $r$ vertices (since then we have $\alpha(B) \ge r = \alpha(A)$). The conclusion follows. $\blacksquare$ So let's consider the situation \[ \alpha(A) = k \ge r \qquad\text{and}\qquad \alpha(B) = k+1. \]At this point $A$ is a set of $k$ red vertices, while $B$ has the remaining $2r-k$ red vertices (and all the green ones). An example is shown below with $k=4$ and $2r = 6$. [asy][asy] size(10cm); pair K1 = 2*dir(45); pair K2 = 2*dir(135); pair K3 = 2*dir(225); pair K4 = 2*dir(315); label("$A$", (0,2), dir(90), red); label("$\alpha(A) = k$", (0,-2.5), dir(90), red); label("$k$ red vertices", (0,-2.5), dir(-90), red); pair K5 = (6,1); pair K6 = (6,-1); draw(K1--K5, palered); draw(K2--K5, palered); draw(K3--K5, palered); draw(K4--K5, palered); draw(K1--K6, palered); draw(K2--K6, palered); draw(K3--K6, palered); draw(K4--K6, palered); pair B1 = (4.8,1.3); pair B2 = (3.7,0); pair B3 = (4.8,-1.3); pair C1 = (7.2,1.3); pair C2 = (8.3,0); pair C3 = (7.2,-1.3); draw(K5--B1--K6, paleblue); draw(K5--B2--K6, paleblue); draw(K5--B3--K6, paleblue); draw(B1--B2--B3--cycle, paleblue); draw(K5--C1--K6, paleblue); draw(K5--C2--K6, paleblue); draw(K5--C3--K6, paleblue); draw(C1--C2--C3--cycle, paleblue); draw(K1--K2--K3--K4--cycle, red+1); draw(K1--K3, red+1); draw(K2--K4, red+1); draw(K5--K6, red+1); dot(K1, red); dot(K2, red); dot(K3, red); dot(K4, red); dot(K5, red); dot(K6, red); dot(B1, deepgreen); dot(B2, deepgreen); dot(B3, blue); dot(C1, deepgreen); dot(C2, deepgreen); dot(C3, blue); draw(circle(B3, 0.15), blue); draw(circle(C3, 0.15), blue); label("$B$", (6,2), dir(90), deepgreen); label("$\alpha(B) = k+1$", (6,-2.5), dir(90), deepgreen); label("$2r-k$ red vertices", (6,-2.5), dir(-90), deepgreen); draw((3,2.8)--(3,-2.8), black+1.5); [/asy][/asy] Now, if we can move any red vertex from $B$ back to $A$ without changing the clique number of $B$, we do so, and win. Otherwise, it must be the case that every $(k+1)$-clique in $B$ uses every red vertex in $B$. For each $(k+1)$-clique in $B$ (in arbitrary order), we do the following procedure. If all $k+1$ vertices are still green, pick one and re-color it blue. This is possible since $k+1 > 2r-k$. Otherwise, do nothing. Then we move all the blue vertices from $B$ to $A$, one at a time, in the same order we re-colored them. This forcibly decreases the clique number of $B$ to $k$, since the clique number is $k+1$ just before the last blue vertex is moved, and strictly less than $k+1$ (hence equal to $k$) immediately after that. Claim: After this, $\alpha(A) = k$ still holds. Proof. Assume not, and we have a $(k+1)$-clique which uses $b$ blue vertices and $(k+1)-b$ red vertices in $A$. Together with the $2r-k$ red vertices already in $B$ we then get a clique of size \[ b + \left( (k+1-b) \right) + \left( 2r-k \right) = 2r + 1 \]which is a contradiction. $\blacksquare$

v_Enhance wrote: After having read the solution in Pascal96's book a long time ago, I finally take the time to write it up now. Take the obvious graph interpretation $G$. We paint red any vertices in one of the maximal cliques $K$, which we assume has $2r$ vertices, and paint the remaining vertices green. We let $\alpha(\bullet)$ denote the clique number. Initially, let the two rooms $A = K$, $B = G-K$. Claim: We can move at most $r$ vertices of $A$ into $B$ to arrive at $\alpha(A) \le \alpha(B) \le \alpha(A)+1$. Proof. This is actually obvious by discrete continuity. We move one vertex at a time, noting $\alpha(A)$ decreases by one at each step, while $\alpha(B)$ increases by either zero or one at each step. We stop once $\alpha(B) \ge \alpha(A)$, which happens before we have moved $r$ vertices (since then we have $\alpha(B) \ge r = \alpha(A)$). The conclusion follows. $\blacksquare$ So let's consider the situation \[ \alpha(A) = k \ge r \qquad\text{and}\qquad \alpha(B) = k+1. \] At this point $A$ is a set of $k$ red vertices, while $B$ has the remaining $2r-k$ red vertices (and all the green ones). An example is shown below with $k=4$ and $2r = 6$. [asy][asy] size(10cm); pair K1 = 2*dir(45); pair K2 = 2*dir(135); pair K3 = 2*dir(225); pair K4 = 2*dir(315); label("$A$", (0,2), dir(90), red); label("$\alpha(A) = k$", (0,-2.5), dir(90), red); label("$k$ red vertices", (0,-2.5), dir(-90), red); pair K5 = (6,1); pair K6 = (6,-1); draw(K1--K5, palered); draw(K2--K5, palered); draw(K3--K5, palered); draw(K4--K5, palered); draw(K1--K6, palered); draw(K2--K6, palered); draw(K3--K6, palered); draw(K4--K6, palered); pair B1 = (4.8,1.3); pair B2 = (3.7,0); pair B3 = (4.8,-1.3); pair C1 = (7.2,1.3); pair C2 = (8.3,0); pair C3 = (7.2,-1.3); draw(K5--B1--K6, paleblue); draw(K5--B2--K6, paleblue); draw(K5--B3--K6, paleblue); draw(B1--B2--B3--cycle, paleblue); draw(K5--C1--K6, paleblue); draw(K5--C2--K6, paleblue); draw(K5--C3--K6, paleblue); draw(C1--C2--C3--cycle, paleblue); draw(K1--K2--K3--K4--cycle, red+1); draw(K1--K3, red+1); draw(K2--K4, red+1); draw(K5--K6, red+1); dot(K1, red); dot(K2, red); dot(K3, red); dot(K4, red); dot(K5, red); dot(K6, red); dot(B1, deepgreen); dot(B2, deepgreen); dot(B3, blue); dot(C1, deepgreen); dot(C2, deepgreen); dot(C3, blue); draw(circle(B3, 0.15), blue); draw(circle(C3, 0.15), blue); label("$B$", (6,2), dir(90), deepgreen); label("$\alpha(B) = k+1$", (6,-2.5), dir(90), deepgreen); label("$2r-k$ red vertices", (6,-2.5), dir(-90), deepgreen); draw((3,2.8)--(3,-2.8), black+1.5); [/asy][/asy] Now, if we can move any red vertex from $B$ back to $A$ without changing the clique number of $B$, we do so, and win. Otherwise, it must be the case that every $(k+1)$-clique in $B$ uses every red vertex in $B$. We pick a green vertex from each clique simultaneously (possibly with overlap), which is possible since $k+1 > 2r-k$, and re-color it blue. We move them all blue vertices to $A$, forcibly decreasing the clique number of $B$ to $k$. Claim: After this, $\alpha(A) = k$ still holds. Proof. Assume not, and we have a $(k+1)$-clique which uses $b$ blue vertices and $(k+1)-b$ red vertices in $A$. Together with the $2k-r$ red vertices already in $B$ we then get a clique of size \[ b + \left( (k+1-b) \right) + \left( 2k-r \right) = 3k+1 - r \ge 2r + 1 \]since $k \ge r$, contradiction. $\blacksquare$ Everything is OK, but can you explain me, why moving all blue vertices from $B$ to $A$ decreases the size of the largest clique in $B$ exactly by 1?

My mistake. I think I took too many blue vertices. I edited what I think should be a fix for it.

Let $ Q_{max}$ be a largest clique. At the beginning we deploy all students in the room $ R_1$ and then begin to move the competitors in $ Q_{max}$ one by one from $ R_1$ into the other room $ R_2$. Consider the last moment, the largest size of the cliques in $ R_1$ is greater than the size of the clique in $ R_2$. Denote by $ Q_1,Q_2$ the groups of students, $ Q_{max}$ is split into, and which currently are in $ R_1$ and $ R_2$ respectively. Clearly, $ Q_1\neq \emptyset$. So, suppose at this moment the maximal clique size in $ R_1$ is $ m_1$ and the size of the clique in $ R_2$ is $ m_2=|Q_2|, m_2<m_1$. Taking any $ q_1\in Q_1$ and moving it to $ R_2$ changes the situation, i.e. after that move we have $ m_2\geq m_1 $. In case of equality, we are done , so we assume that after moving any $ q_1\in Q_1$ into room $ R_2$ the clique in $ R_2$ has greater size than any clique in $ R_1$. It means $ m_1=m_2+1$ Denote by $ \mathcal{Q}$ the family of all cliques of size $ m_1$ in $ R_1$. Taking into account that after removing any $ q_1\in Q_1$ the max clique size in $ R_1$ drops down, it follows $ Q_1\subset Q$ for any $ Q\in \mathcal{Q}$. We also conclude $ Q_1\not\in \mathcal{Q}$, since otherwise $ |Q_1|=|Q_2|+1$, which is impossible because $ |Q_{max}|$ is even. Now, we start transferring students $ s_1,s_2,\dots,s_k$ not in $ Q_1$ that take part in some clique of $ \mathcal{Q}$ from room $ R_1$ to $ R_2$ till the moment we destroy all cliques in $ \mathcal{Q}$. At that moment, the max clique size in $ R_1$ decreases with $ 1$ and equals $ m_1-1$. We claim the max clique size in $ R_2$ is still intact and equals $ m_2=m_1-1$. Assume on the contrary, there exists a clique $ P_2$ in $ R_2$ with $ |P_2|>|Q_2|=m_2$. Note that all students of $ P_2\setminus Q_2$ are among $ s_1,s_2,\dots,s_k$ and thus they are friends with all students in $ Q_1$. Hence $ P_2\cup Q_1$ is a clique with size $ |P_2|+|Q_1|>|Q_2|+|Q_1|=|Q_{max}|$, a contradiction with the fact $ Q_{max}$ is a clique with maximal size. Remark: Here are more detailed comments on the motivation and grading of this problem.

v_Enhance wrote: Claim: After this, $\alpha(A) = k$ still holds. Proof. Assume not, and we have a $(k+1)$-clique which uses $b$ blue vertices and $(k+1)-b$ red vertices in $A$. Together with the $2k-r$ red vertices already in $B$ we then get a clique of size\[ b + \left( (k+1-b) \right) + \left( 2k-r \right) = 3k+1 - r \ge 2r + 1 \]since $k \ge r$, contradiction. $\blacksquare$ There are $2r-k$ red vertices in $B$, not $2k-r$ Can be fixed easily, though.

Ah, thanks, will fix.

Solution: We take the obvious graph interpretation, i.e., let a vertex denote competitor and let an edge denote friendship. Let the rooms be $A$ and $B$. Let $X$ denote a maximal clique and let it have $2x$ vertices. The idea here is to move competitors from one room to the other (pairwise). When we put the vertices of $X$ into $A$ and $B$ in that order, the size of the largest clique in $A$ would be $2x$ and in $B$ at most $2x$ (note the bound). Also let $A'$ denote a maximal clique of $A$. Assume that they don't have the same clique size (with $A$'s larger), as if they do than we would already have the desired result. As indicated above in this post, we'll move the vertices (competitors) from $A$ to $B$ one at a time. We continue this process whenever $A$ has the larger size of a maximal clique than $B$ (notice that the case when we don't continue the process is when $B$ has a larger size of a maximal clique than $A$, and from our "moving process," $B$ has a maximal clique of size $k$, $A$ has a maximal clique of size $k-1$). Consequently, we easily get that $k \geq x+1$ from $B$ and $k-1 \leq x-1$ from $A$, which is absurd, so thus $A$ has at least $x$ vertices of $X$. Denote by $B \cap X = X'$ (has at most $x$ vertices coming from $X$). Note we get a ton of friendships from $A'$ w.r.t $X'$, so obviously the union would be a clique. Let $y \in X'$ s.t $y$ is not a maximal clique of $B$. Then if we reverse our process (i.e., move $B$ back to $A$), then that would obviously increase the size of the maximal clique, and hence $A$ and $B$ both have maximal clique size $k$. This tells us that $X'$ belongs in every maximal clique of $B$. Now consider the set formed by removing the elements of $X'$ from a maximal clique of $B$, and move every vertex to $A$. From this, we can get that the size of the maximal clique of $A$, $A'$ is at most $k-1 \implies$ the original rooms $A$ and $B$ have the same maximal clique size $k-1$, as desired. $\square$

Valentin Vornicu wrote: In a mathematical competition some competitors are friends. Friendship is always mutual. Call a group of competitors a clique if each two of them are friends. (In particular, any group of fewer than two competitiors is a clique.) The number of members of a clique is called its size. Given that, in this competition, the largest size of a clique is even, prove that the competitors can be arranged into two rooms such that the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room. Author: Vasily Astakhov, Russia Consider a graph $G$ with $n$ vertices and an edge between any two vertices(competitors) if they are friends. Now consider two groups with one group having all the competitors and the other containing no competitors. For convinence,denote both the rooms by $R_1$ and $R_2$ and define $C(R_n)$ as the largest size of a clique in a particular room. By definition,at the starting we have $$\mathcal{C}(R_1)=2n \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \mathcal{C}(R_2)=0$$Continue the process as long as it isn't negative; we either obtain $\mathcal{C}(A)+1=\mathcal{C}(B)$ or $\mathcal{C}(A)=\mathcal{C}(B)$ Now suppose that the first case holds i.e $\mathcal{C}(A)+1=\mathcal{C}(B)=k+1$ and by default the largest clique is of $2m$ Move 1 person for the second room to the first.Then we have two cases:- $\;\;\; \bullet$ All people in the clique in room 2 know everyone in room 1:-Then move everyone to rome 1.There's a clique of size $2k+1$ in room 1 and this is the largest clique among the competitors since otherwise if someone knows all the people in the clique in room 1,then his count increases one of that in room 1 or 2,contradiction. $\;\;\; \bullet$ No one in the clique from room 2 know anyone in room 1:-Then simply transfer one of them;there is a clique of $k$ in both of them.$\blacksquare$

We will prove this statement by constructing such a division of the competitors into two rooms. Let the largest size of a clique be $k$. Since $k$ is even, we can divide the clique into two groups of $k/2$ competitors each. Let these two groups be called $A$ and $B$. Now consider any other clique in the competition. It must have a size less than or equal to $k$, since we have assumed that $k$ is the largest size of a clique. If the size of this clique is less than $k/2$, then it can be fully contained in either group $A$ or group $B$. If the size of this clique is $k/2$, then it must contain exactly one competitor from each group $A$ and $B$. Therefore, we can divide the competitors into two rooms such that the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room by putting group $A$ in one room and group $B$ in the other room. Notice that in the construction above we made use of the fact that the largest clique is even. This is important because if the largest clique were odd, we could not divide it into two groups of the same size, which would make the construction above impossible.

Call the rooms $A$ and $B$. Start with $A$ having one of the largest cliques, and $B$ having everyone else. Let the largest size of a clique of any set $S$ of competitors $m(S)$. Let the maximum in general be $2m$. Here, we see $A$ and $B$ as sets. Evidently, $m(A)\ge m(B)$. As long as $m(A)>m(B)$, take one member of $A$ and move them to $B$. This increases $m(B)$ by at most one and decreases $m(A)$ by exactly one. Thus, $m(A)-m(B)$ decreases by one or two at a time. Since we do this process until it is non-positive, at the end of the process it will be $0$ or $-1$. If it is $0$ we are done. Suppose it is $-1$. Let $X$ be the subset of $A$ that is part of one of the largest cliques of $A$, and $Y$ be the subset of $B$ that is part of one of the largest cliques of $B$. If for some $p\in Y$, $p$ is not friends with $x$ for some $x\in X$, then moving $p$ to $A$ will not change $m(A)$ but will decrease $m(B)$ by one. If for some $q\in B\setminus Y$, $q$ is friends with each of the competitors in $X$, then moving $q$ to $A$ will not change $m(B)$ but will increase $m(A)$ by one. Thus, if either of these conditions are true, we are done. Assume For each $p\in Y$, $p$ is friends with each $x\in X$. For each $q\in B\setminus Y$, $q$ is not friends for some $x\in X$. By the first condition, for any pair $(x,y)$ in $(X,Y)$, $x$ and $y$ are friends. Since $X$ and $Y$ are both cliques, $X\cup Y$ is also a clique. Since \[2m(X)<m(X)+m(Y)=m(X+Y) \le m\]so $m(X)\le m-1$. However, this means that we moved at least $m+1$ from $A$ to $B$ in our first process. Thus, $m(A)-m(B)\le -2$, contradiction.

I see that there's a lot of solutions posted! Here's my only hard combo problem solved lol in fact I think it might be unique, but my heuristic was really simple so probably not. Call the rooms A and B, with splitting them s.t. A has the largest clique and B has everyone else, with the maximum 2x size clique and y and z representing the size of their respective largest cliques. We move an arbitrary person from A to be continuously, meaning y decreases by 1 every time and z increases by at most 1, stopping when z-y=0 or 1. Now if it's 0 we're done, so suppose it's 1. Call a person who did not come from room A $different$ and someone who did but now in B $friendzoned.$ If there is a friendzoned person not in z, just move it, which increases y by 1 and we're done. If there are multiple largest cliques in B, we can just take any friendzoned person who would join the clique in A from B, and we would be done (since there'd be at least one clique that stays the same size, yet y would +1). If not, then every friendzoned person must be both in the unique largest clique z, with at least one different person (since if otherwise, both A and that largest clique only contain members that come from A, and because y was originally even we can evenly split), and we can take them and move them to A, which will subtract one from z but not add one to y since they were not a person from A, meaning they would not fit in/add to y as a clique member. $\blacksquare$

Solved with AdventuringHobbit and others. Have a left side and a right side; an LHS and RHS respectively, for short. Start with everything on the LHS. Let $C$ be a maximally sized clique. Move elements of $C$ one by one from the LHS to RHS, until all of them are on the RHS. Now, at each step of this process, the largest clique size on the LHS stays the same or decreases by one and that of the RHS increases by one. Thus, either eventually they must cross, and if they do then at that point we are done, or at some point the LHS has maximal clique size $k+1$ and the RHS has $k$ elements of $C$ and then after one step the maximal clique size for the LHS goes down to $k$ where the RHS goes up to $k+1$ elements of $C$. Now, observe that every maximally sized clique on the LHS before this step should contain $C\cap$LHS; otherwise we could take the element in $C$ on the LHS not in a maximally sized clique and move it to the RHS, thus increasing the maximal clique size of the RHS to $k+1$ but leaving that of the LHS at $k+1$ and finishing the problem. Now, every maximally sized clique on the LHS cannot only be $C\cap$LHS because then its size would add to $k+1$ to make the size of $C$, which would make that size $2k+1$, but that is odd, contradicting problem condition. Hence, moving all elements outside of $C$ that connect to every element of $C\cap$LHS to the RHS ensures that no more $k+1$-sized clique on the LHS can remain as it would have to contain all of $C\cap$LHS and then at least one of the elements which we just moved. This leaves the LHS with maximal clique size $k$, and we claim that the RHS remains at maximal clique size $k$ as well: we know that it was at $k$ before so now the maximal clique size will be at least $k$, and every element of the RHS connects to every element of $C\cap$LHS, meaning any clique on the RHS combined with $C\cap$LHS can have at most the size of $C$, which is the same as the size of the original $C\cap$RHS clique combined with $C\cap$LHS, so any new clique cannot have a larger size and thus has size at most $k$. This proves that the largest clique size on the RHS is at least $k$ and at most $k$, hence equal to $k$ and in particular equal to the largest clique size on the LHS, as desired.

First we can apply an algorithm, call it algorithm for which if we have two sets of vertices $A$ and $B$ and let the remaining vertices be in a set $C$, algorithm takes a vertice from $C$ and adds it to the set out of $A$ and $B$ with the smaller maximal clique or to a random one if they have the same maximal clique. Applying this algorithm until $C$ is empty will create a set $A$ with maximal clique of size $k$ and a set $B$ with maximal clique of size $k+1$. Now we remove every vertice that is not in the $k+1$ clique until set $A$ has a $k+1$ clique or such a move cannot be made again. Now we have $B$ is a $k+1$ clique. Now move a vertice from $B$ to $A$. If we do not get a $k+1$ clique in $A$ we are done. Now suppose we have a $k+1$ clique in $A$. Let $S$ be a set of vertices such that removing all vertices in that set from $A$ changes its maximal clique size to $k$ but removing some of those vertices but not all keeps the maximal clique size as $k+1$, thus we get that $S$ must be a clique as we have that moving all vertices in $S$ to $B$ increases the clique size of $B$ to $k+1$ but moving some of the vertices but not all keeps the clique size the same. Thus we get that in fact there is only one $k+1$ clique in $A$, as if there are multiple we get that the result about $S$ implies they are all one clique which implies the size of the maximal clique of $A$ is $>k+1$ which is not possible. Thus there is only one $k+1$ in $A$, if we move any vertice from this back to $B$ this must make $B$ a $k+1$ clique, which implies that when $B$ is added to $A$ the maximal clique in the graph has size $2n+1$ which is odd which is a contradicition.