Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2022 USAMO Problems/Problem 6"

(→‎Problem)
(→‎Solution 1)
 
(6 intermediate revisions by 5 users not shown)
Line 3: Line 3:
  
 
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?
 
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?
−
Solution 1
 
  
−
To answer this question, we need to consider how friendships on Mathbook are formed. If two users have at least two friends in common, then they will be able to become friends with each other. This means that the minimum number of friendships that must already exist in order for every user to eventually become friends with every other user is the smallest number of friendships that guarantees that each pair of users has at least two friends in common.
+
==Solution 1==
−
 
+
No Solution Here Yet!
−
One way to guarantee that each pair of users has at least two friends in common is to create a complete graph, where each user is friends with every other user. In this case, each pair of users has exactly <math>2022 - 2 = 2020</math> friends in common. However, this is not the minimum number of friendships required, since some pairs of users may have more than two friends in common without forming a complete graph.
 
−
 
 
−
To find the minimum number of friendships required, we can use the fact that a friendship between two users implies that they share all of their mutual friends. In other words, if two users are friends, then they must have at least two friends in common. This means that if we want to guarantee that each pair of users has at least two friends in common, we can do so by ensuring that each user has at least two friends.
 
−
 
 
−
Therefore, the minimum number of friendships that must already exist in order for every user to eventually become friends with every other user is <math>2 \cdot 2022 = \boxed{4044}</math>.
 
  
 
==See also==
 
==See also==
 
{{USAMO newbox|year=2022|num-b=5|after=Last Problem}}
 
{{USAMO newbox|year=2022|num-b=5|after=Last Problem}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 17:01, 13 November 2023

Problem

There are $2022$ 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?

Solution 1

No Solution Here Yet!

See also

2022 USAMO (Problems • Resources)
Preceded by
Problem 5 		Followed by
Last Problem
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2022_USAMO_Problems/Problem_6&oldid=203013"