양의 정수 $n$에 대하여, 총 $n$명의 학생이 있는 학교가 있다. 이 학교 학생들로 이루어진 집합 $X$에 대하여, $X$에 속한 임의의 서로 다른 두 학생이 서로 아는 사이이면 그 집합 $X$를 잘 짜인 집합이라 부르자. 잘 짜인 집합의 학생 수의 최댓값이 $k$이면, 이 학교에서 만들 수 있는 잘 짜인 집합의 개수는 $3^{(n+k)/3}$ 이하임을 보여라. 단, 공집합이나 학생 $1$명의 집합 역시 잘 짜인 집합이다.
GD Star Rating
loading...
loading...