MathDB
High school combinatorics

Source: Korea National Olympiad P3

November 24, 2020
combinatoricsgraph

Problem Statement

There are n boys and m girls at Daehan Mathematical High School. Let d(B)d(B) a number of girls who know Boy BB each other, and let d(G)d(G) a number of boys who know Girl GG each other. Each girl knows at least one boy each other. Prove that there exist Boy BB and Girl GG who knows each other in condition that d(B)d(G)≥mn\frac{d(B)}{d(G)}\ge\frac{m}{n}.
Back to ProblemsView on AoPS