Maths Olympiad Prep

Library / /25 of 30

Combinatorics Difficulty 6.4 National olympiad Find the answer

At a conference there are nn mathematicians. Each of them knows exactly kk fellow mathematicians. Find the smallest value of kk such that there are at least three mathematicians that are acquainted each with the other two.

Rewording of the last line for clarification:
Find the smallest value of kk such that there (always) exists 33 mathematicians X,Y,ZX,Y,Z such that XX and YY know each other, XX and ZZ know each other and YY and ZZ know each other.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let n n be the number of mathematicians at the conference. We are tasked with finding the smallest value of k k such that there are at least three mathematicians, say X,Y, X, Y, and Z Z , who are all acquainted with each other (i.e., each knows the other two).

We can model this problem using graph theory, where each mathematician is represented by a vertex, and an edge exists between two vertices if the corresponding mathematicians know each other. Our goal is to find the smallest k k such that any graph with n n vertices, each with degree k k , must contain a triangle (a cycle of three vertices).

To approach this problem, consider the following:

1. The total number of acquaintances (edges) in the graph is nk2 \frac{nk}{2} , since each of the n n vertices has degree k k .

2. The problem is equivalent to finding the smallest k k such that every subgraph G G of n n vertices and nk2 \frac{nk}{2} edges contains at least one triangle.

Let's consider a complete bipartite graph Kn2,n2 K_{\lfloor \frac{n}{2} \rfloor, \lceil \frac{n}{2} \rceil} . This graph divides the n n vertices into two sets of sizes n2 \lfloor \frac{n}{2} \rfloor and n2 \lceil \frac{n}{2} \rceil , and every vertex in one set is connected to every vertex in the other set, with no edges within the same set. The degree of each vertex in this graph is n2 \lfloor \frac{n}{2} \rfloor . Such a graph contains no triangles as there are no edges within the same set.

If kn2 k \leq \lfloor \frac{n}{2} \rfloor , it's possible to arrange the acquaintance relations as in a complete bipartite graph, avoiding triangles. To ensure a triangle always exists, we need at least k>n2 k > \lfloor \frac{n}{2} \rfloor .

Thus, adding one more acquaintance to each mathematician ensures that at least one triangle must form due to the increase in connectivity. Therefore, the smallest k k for which a triangle always exists is:

k=n2+1. k = \left\lfloor \frac{n}{2} \right\rfloor + 1.

Thus, the required smallest value of k k is:

n2+1. \boxed{\left\lfloor \frac{n}{2} \right\rfloor + 1}.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.