Maths Olympiad Prep

Library / /4 of 144

Combinatorics Difficulty 7.3 National olympiad, round 2 Find the answer

Among a group of 120 people, some pairs are friends. A weak quartet is a set of four people containing exactly one pair of friends. What is the maximum possible number of weak quartets ?

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

Solution

Given a group of 120 people, where some pairs are friends, we need to determine the maximum possible number of weak quartets. A weak quartet is defined as a set of four people containing exactly one pair of friends.

To solve this, we need to analyze the structure of weak quartets:

1. Count the total number of quartets:
The total number of ways to choose 4 people out of 120 is given by the combination formula:
(1204)=120×119×118×1174×3×2×1=2550240. \binom{120}{4} = \frac{120 \times 119 \times 118 \times 117}{4 \times 3 \times 2 \times 1} = 2550240.

2. Count the number of quartets that could be considered as weak quartets:
First, select a pair of friends, and then choose the other two people from the 118 remaining people. If f f is the number of pairs of friends, then:
Number of ways to form a weak quartet involving a specific pair of friends=f×(1182). \text{Number of ways to form a weak quartet involving a specific pair of friends} = f \times \binom{118}{2}.

3. Maximize the number of weak quartets:
To maximize the number of weak quartets, assume the maximum possible number of friendship pairs. According to the combinatorial principle, the maximum number of friendship pairs among 120 people occurs when every possible pair of persons is friends:
f=(1202)=120×1192=7140. f = \binom{120}{2} = \frac{120 \times 119}{2} = 7140.

4. Thus, the maximum possible number of weak quartets is:
7140×(1182)=7140×118×1172=7140×6903=4769280. 7140 \times \binom{118}{2} = 7140 \times \frac{118 \times 117}{2} = 7140 \times 6903 = 4769280.

Therefore, the maximum possible number of weak quartets is:
4769280. \boxed{4769280}.

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.