MathDB
An inequality at a graph

Source: Korea National 2012 Problem 2

August 19, 2012
inequalitiescombinatorics proposedcombinatorics

Problem Statement

There are nn students A1,A2,⋯ ,An A_1 , A_2 , \cdots , A_n and some of them shaked hands with each other. (Ai A_i and Aj A_j can shake hands more than one time.) Let the student Ai A_i shaked hands di d_i times. Suppose d1+d2+⋯+dn>0 d_1 + d_2 + \cdots + d_n > 0 . Prove that there exist 1≤i<j≤n 1 \le i < j \le n satisfying the following conditions: (a) Two students Ai A_i and Aj A_j shaked hands each other. (b) (d1+d2+⋯+dn)2n2≤didj \frac{(d_1 + d_2 + \cdots + d_n ) ^2 }{n^2 } \le d_i d_j
Back to ProblemsView on AoPS