Problem

Source: KJMO 2017 p8

Tags: combinatorics, graph theory



For a positive integer $n$, there is a school with $n$ people. For a set $X$ of students in this school, if any two students in $X$ know each other, we call $X$ well-formed. If the maximum number of students in a well-formed set is $k$, show that the maximum number of well-formed sets is not greater than $3^{(n+k)/3}$. Here, an empty set and a set with one student is regarded as well-formed as well.