MathDB
Double Counting on a simple Graph

Source: Korea National Olympiad 2009 Problem 4

September 9, 2012
combinatorics proposedcombinatorics

Problem Statement

There are n(≥3)n ( \ge 3) students in a class. Some students are friends each other, and friendship is always mutual. There are s(≥1) s ( \ge 1 ) couples of two students who are friends, and t(≥1) t ( \ge 1 ) triples of three students who are each friends. For two students x,y x, y define d(x,y) d(x,y) be the number of students who are both friends with x x and y y . Prove that there exist three students u,v,w u, v, w who are each friends and satisfying d(u,v)+d(v,w)+d(w,u)≥9ts. d(u,v) + d(v,w) + d(w,u) \ge \frac{9t}{s} .
Back to ProblemsView on AoPS