MathDB

Another Turan-type problem

Source: Romanian TST 3 2008, Problem 4

June 7, 2008

inequalitiesinductiongraph theorycombinatorics proposedcombinatorics

Problem Statement

Let

n

be a nonzero positive integer. A set of persons is called a

n

-balanced set if in any subset of

3

persons there exists at least two which know each other and in each subset of

n

persons there are two which don't know each other. Prove that a

n

-balanced set has at most (n \minus{} 1)(n \plus{} 2)/2 persons.