Maths Olympiad Prep

Library / /29 of 53

Combinatorics Difficulty 6.3 National olympiad Prove it China

Eight persons join a party.

(1) If there exist three persons who know each other in any group of five, prove that we can find that four persons know each other.

(2) If there exist three persons in a group of six who know each other in a cyclical manner, can we find four persons who know each other in a cyclical manner?

Solution

(1) By means of graph theory, use 88 vertices to denote 88 persons. If two persons know each other, we connect them with an edge. With the given condition, there will be a triangle in every induced subgraph with five vertices, while every triangle in the graph belongs to different (832)=(52)=10\binom{8-3}{2} = \binom{5}{2} = 10 induced subgraphs with five vertices. We know that there are 3×(85)=3×56=1683 \times \binom{8}{5} = 3 \times 56 = 168 edges in total in these triangles, while every edge is computed ten times repeatedly.

Thus every vertex is incident with at least 2×1688×10>4\frac{2 \times 168}{8 \times 10} > 4 edges. So there exists one vertex AA that is incident with at least five edges.

Suppose the vertex AA is adjacent with five vertices BB, CC, DD, EE, FF. By the condition, there exists one triangle in five vertices. Without loss of generality, let BCD\triangle BCD denote the triangle. So there exists one edge between any two vertices in the four vertices AA, BB, CC, DD. So the corresponding four persons of the four vertices know each other.

(2) If there exist three persons (in a group of six) who know one another in a cyclical manner, there may not exist four persons who know each other.

For example, let 88 vertices denote 88 persons. If two persons know each other, we join them with an edge. Consider the regular octagon, we link up the 88 shortest diagonals, as desired.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.