There were finitely many persons at a party among whom some were friends. Among any $4$ of them there were either $3$ who were all friends among each other or $3$ who weren't friend with each other. Prove that you can separate all the people at the party in two groups in such a way that in the first group everyone is friends with each other and that all the people in the second group are not friends to anyone else in second group. (Friendship is a mutual relation).
Problem
Source:
Tags: induction, group theory, abstract algebra, graph theory, combinatorics
13.04.2011 15:24
We connect points of $G$ red lines for all friends, others blue lines. Let $R$ is the maximum red complete subgraph of $G$. We can suppose $G$ is not blue complete graph, so $\left| R \right| \geqslant 2$. If $G\backslash R$ is blue complete graph, we done. Suppose there are ${v_1},{v_2} \in G\backslash R$, and ${v_1}{v_2}$ is red. For the maximum of $R$, ${v_1}$ must connected a ${u_1} \in R$ with blue line. If ${u_1}{v_2}$ is blue, for any ${u_1} \ne u \in R$, $\Delta u{v_1}{v_2}$ must be red triangle. So $R \cup \left\{ {{v_1},{v_2}} \right\}\backslash \left\{ {{u_1}} \right\}$ is red complete graph, contradiction. If ${u_1}{v_2}$ is red, one of $\Delta u{v_1}{v_2},\Delta {u_1}u{v_2}$ must be red triangle. So ${v_2}u$ is red line, $R \cup \left\{ {{v_2}} \right\}$ is red complete graph, contradiction.
Attachments:
25.04.2014 02:08
Define people at a party as points.Let $n$ be the number of the points.Let them be connected by red line if they know each other and by blue line otherwise.Define $AB=CD$ if $AB$ and $CD$ are the same color.Also define a triangle as a "right" triangle if all his lines are the same color.Let's prove it by induction: 1.Step:n=4: By the condition of the problem among these $4$ there exist $3$ point forming a "right" triangle.It is obvious that, if we put the 3 point that form a "right" triangle in one and the fourth point in the other room,we divided them into 2 rooms as demanded. 2.Step:Suppose that for any $n$ that acomplish given condition it is possible to divide them in 2 rooms as demanded. 3.Step:Prove that if it is possible for $n$ it is possible or $n+1$: Divide $n$ out of $n+1$ into 2 rooms.Let room $C$ be the room where everyone know each other and let the other room be $P$.Let the n+1-th point that is not put into any of the rooms be called $T$.Now,if $T$ knows everyone from the room $C$ it can be put into that room and the problem is solved.So let's suppose there is one point he doesn't know.Let that point be $A(1)$.Also,if it doesn't know anyone from the room $P$ it can be put in that room and the problem is solved.So let's suppose there is one point he knows.Let that point be $B(1)$.$WLOG$ because of simetry suppose that $A(1)$ doesn't know $B(1)$.Let $A(i)$;$i$ not equal to $1$; be any point from room $C$.In quadriletal $A(1)TB(1)A(i)$ there must be one right triangle.It is trivial that $A(1)$ doesn't build any right triangle in that quadriletal so $B(1)TA(i)$ must be a right triangle.As $B(1)T$ is blue both $TA(i)$ and $B(1)A(i)$ are blue so that means that $B(1)$ and $T$ know everybody except $A(1)$ from the room $C$.Now let $B(i)$;i not equal to 1,be any point from room $P$.In quadriletal $B(i)B(1)TA(1)$ also must be a right triangle.It is obvious that only triangles $TA(1)B(i)$ and $A(1)B(1)B(i)$ can be right.One of them must be a blue triangle.Notice that $A(1)B(i)$ is their mutual line so that line must be blue.That means that A(1) doesn't know anyone from room $P$. $A(1)$doesn't know anyone from $P$ and $B(1)$ knows everyone from $C$ except $A(1)$.That means we can swap $A(1)$ and $B(1)$ and the room conditions would still be satisfied.Then $T$ would know everyone from room $C$ so we can put $T$ in $C$.Beause of the above all problem conditions are satisfied so the proof is finished.I hope this helps:).
26.04.2014 16:38
From what year this problem is?, because actually this problem was used in the Mexican Olympiad on 2009. A PDF here confirms it. (Is in Spanish). http://ommbc.org/archivos_pdf/nacionales/OMM_23.pdf On question 6.
29.04.2014 18:02
From 2011.
13.10.2014 21:48
Pick the maximal subgroup such that no one knows one other.All other guys,cause of the maximality of the group must have at least one friend from this group.So,if we have two guys that know the same guy from the group and don't know each other,then we can add them to the group and remove their common friend,so contradiction cause the maximality,also otherwise everyone knows every other guy from the group,so we are finished.