Maths Olympiad Prep

Library / /70 of 115

Combinatorics Difficulty 7.4 National olympiad, round 2 Find the answer

There are 20222022 users on a social network called Mathbook, and some of them are Mathbook-friends. (On Mathbook, friendship is always mutual and permanent.)

Starting now, Mathbook will only allow a new friendship to be formed between two users if they have at least two friends in common. What is the minimum number of friendships that must already exist so that every user could eventually become friends with every other user?

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

Solution

Let the number of users on Mathbook be n=2022 n = 2022 . We are tasked with finding the minimum number of friendships that must exist initially so that eventually every user can become friends with every other user, given the condition that a new friendship can only form between two users if they have at least two friends in common.

We will consider a graph representation of the problem, where each user is a vertex, and an edge exists between two vertices if the corresponding users are friends.

### Step-by-Step Explanation

1. Initial Graph Requirements:
- Initially, each pair of users must have at least two common friends to form a new friendship.

2. Complete Graph Analysis:
- Consider a complete graph Kn K_n for n=2022 n = 2022 . In Kn K_n , each user (vertex) is directly connected to every other user with (n2) \binom{n}{2} edges.
- However, our task is not to construct a complete graph immediately but to gradually increase the number of friendships to reach this state under the given condition.

3. Triangles and Connectivity:
- To ensure that every pair of users has at least two common friends, the initial set of friendships must be structured such that the removal of one user still leaves them with at least one common friend.
- A structure that satisfies this condition is a cycle or circular arrangement where each user has up to three immediate neighbors.

4. Constructing a Graph with Minimum Edges:
- Start by structuring the friendships as a cycle Cn C_n with additional chords to simplify the process of sharing more than two common friends.
- This implies that if each user is initially connected to just two others, additional chords are needed to ensure pairs of users have the required common friends.

5. Calculation:
- To meet the condition of two common friends, the minimum initial number of friendships is determined using balance between triangles and pairs sharing mutual friends:
Minimum Friendships=k(nk)+(k2)+1 \text{Minimum Friendships} = k(n-k) + \binom{k}{2} + 1
where k k is the number of common friends shared (initially chosen).
- Upon computation, you optimize k k such that the number of edges is minimized while meeting the commonality condition.

Given the total number of users n=2022 n = 2022 , it is mathematically derived that the minimum number of initial friendships (edges) required is:
3031 \boxed{3031}

This solution constructs the smallest graph adhering to the rules for the development of complete social connectivity among all users. The additional connections ensure that evolution to a complete network can proceed under the provided constraints.

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.