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 "1995 USAMO Problems/Problem 5"
(→‎Solution)
 
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
−
{{solution}}
 
−
 
 
Consider the graph with two people joined if they are friends.
 
Consider the graph with two people joined if they are friends.
  
Line 14: Line 12:
 
<cmath> \sum_{X \in G} D(X)^2 \geq \frac{(\sum_{X \in G} D(X))^2}{n}=\frac{(2q)^2}{n}=4q^2/n. </cmath>
 
<cmath> \sum_{X \in G} D(X)^2 \geq \frac{(\sum_{X \in G} D(X))^2}{n}=\frac{(2q)^2}{n}=4q^2/n. </cmath>
 
(That's Cauchy.) Since we are summing over <math>n</math> vertices, one of the summands is at least <math>4q^2/n^2</math> by pigeonhole, which is what we wanted to prove.
 
(That's Cauchy.) Since we are summing over <math>n</math> vertices, one of the summands is at least <math>4q^2/n^2</math> by pigeonhole, which is what we wanted to prove.
 +
 +
{{alternate solutions}}
 +
 
==See Also==
 
==See Also==
 
{{USAMO box|year=1995|num-b=4|after=Last Problem}}
 
{{USAMO box|year=1995|num-b=4|after=Last Problem}}
 
{{MAA Notice}}
 
{{MAA Notice}}
 
[[Category:Olympiad Combinatorics Problems]]
 
[[Category:Olympiad Combinatorics Problems]]

Latest revision as of 20:56, 12 November 2023

Problem

Suppose that in a certain society, each pair of persons can be classified as either amicable or hostile. We shall say that each member of an amicable pair is a friend of the other, and each member of a hostile pair is a foe of the other. Suppose that the society has $\, n \,$ persons and $\, q \,$ amicable pairs, and that for every set of three persons, at least one pair is hostile. Prove that there is at least one member of the society whose foes include $\, q(1 - 4q/n^2) \,$ or fewer amicable pairs.

Solution

Consider the graph with two people joined if they are friends.

For each person $X$, let $A(X)$ be the set of its friends and $B(X)$ the set of its foes. Note that any edge goes either: from $X$ to $A(X)$ (type 1), from $A(X)$ to $B(X)$ (type 2) or from a point of $B(X)$ to another (type 3), but there's no edge joining two points of $A(X)$ (since they would form a triangle with $X$). Let the number of type 1, type 2, type 3 edges of $X$ be $x_1, x_2, x_3$ respectively, so that $x_1$ is the degree of $X$ and we want to show that for some $X$, we have $x_3 \leq q(1-4q/n^2)$.

Since each edge is of one of those types, we have $x_1+x_2+x_3=q$. Thus \[x_3 \leq q(1-4q/n^2) \Longleftrightarrow \\ x_3 \leq q-4q^2/n^2 \Longleftrightarrow \\ q-x_1-x_2 \leq q-4q^2/n^2 \Longleftrightarrow \\ x_1+x_2 \geq 4q^2/n^2.\] That is, what we want is equivalent to proving that for some vertex $X$, the set of edges touching either $X$ or a vertex joined to $X$ is at least $4q^2/n^2$. Obviously now we'll sum $x_1+x_2$ over all vertices $X$. In the resulting sum, an edge joining $X, Y$ is counted once for each edge that $X, Y$ have, that is, it is counted $D(X)+D(Y)$ times, where $D(X)=x_1$ is the degree of $X$. Thus each vertex $X$ contributes to the overall sum with $D(X)$ for each edge it has, and since it has $D(X)$ edges, it contributes with $D(X)^2$. Thus the considered sum is equal to \[\sum_{X \in G} D(X)^2 \geq \frac{(\sum_{X \in G} D(X))^2}{n}=\frac{(2q)^2}{n}=4q^2/n.\] (That's Cauchy.) Since we are summing over $n$ vertices, one of the summands is at least $4q^2/n^2$ by pigeonhole, which is what we wanted to prove.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See Also

1995 USAMO (Problems • Resources)
Preceded by
Problem 4 		Followed by
Last Problem
1 • 2 • 3 • 4 • 5
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=1995_USAMO_Problems/Problem_5&oldid=202843"