MathDB
n students shaking hands

Source: KJMO 2012 p4

May 4, 2019
combinatorics

Problem Statement

There are nn students A1,A2,...,AnA_1,A_2,...,A_n and some of them shaked hands with each other. (AiA_i and A−jA-j can shake hands more than one time.) Let the student AiA_i shaked hands did_i times. Suppose d1+d2+...+dn>0d_1 + d_2 +... + d_n > 0. Prove that there exist 1≤i<j≤n1 \le i < j \le n satisfying the following conditions: (a) Two students AiA_i and AjA_j shaked hands each other. (b) (d1+d2+...+dn)2n2≤didj\frac{(d_1 + d_2 +... + d_n)^2}{n^2}\le d_id_j
Back to ProblemsView on AoPS