MathDB
Dividing into cliques and independent sets

Source: Japan Olympiad Finals 2014 #3

May 17, 2014
inductionceiling functioninequalitiesalgorithmcombinatorics proposedcombinatorics

Problem Statement

In a school, there are nn students and some of them are friends each other. (Friendship is mutual.) Define a,b a, b the minimum value which satisfies the following conditions: (1) We can divide students into a a teams such that two students in the same team are always friends. (2) We can divide students into b b teams such that two students in the same team are never friends. Find the maximum value of N=a+b N = a+b in terms of nn.
Back to ProblemsView on AoPS