지난 31년간 $n$($\ge 7$)명의 테니스 선수들이 서로 경기를 한 결과를 분석하였더니, 임의의 두 선수 $X$, $Y$를 뽑더라도 그 두 선수를 모두 이긴 적이 있는 다른 선수가 있었다는 사실을 발견하였다. 만일 어떤 정수 $k$에 대하여 $ 2(2^{(2^k)}-1)\ge n$이면 다음 조건을 만족하는 서로 다른 테니스 선수들 $A_1$, $A_2$, $\ldots$, $A_\ell$이 존재함을 보여라.
$2\le \ell\le 2k$이며 모든 $1\le i<\ell$에 대하여 $A_i$는 $A_{i+1}$을 이긴 적이 있고
$A_\ell$은 $A_1$을 이긴 적이 있다.
(단, 어떤 두 선수 $A$, $B$는 서로 경기를 한 적이 없을 수도 있고 있을 수도 있다.)
한 변의 길이가 1인 정이십면체의 각 면에 개미가 한 마리씩 살고 있다. 개미는 각 면의 모서리를 따라 반시계방향으로 돌아야 하며 어느 순간에도 속력이 1 이상이어야 한다. 꼭짓점이 아닌 점에서 두 개미가 만나는 것은 금지되어 있다. 다섯 마리의 개미가 한 꼭짓점에서 동시에 만나는 것을 충돌이라고 한다. 충돌이 일어나지 않도록 개미들이 움직이는 전략이 존재하는가?
민정과 성빈이 무한히 넓은 바둑판에서 다음 규칙에 따라 한번씩 번갈아 시행을 하는 게임을 한다.
처음에 민정부터 시작하며, 각 시행은 두 이웃한 교차점을 잇는 선분 중 아직 방향이 정해지지 않은 것 하나를 골라서 화살표 표시를 하여 방향을 정하는 것이다. 어느 순간에 방향이 정해진 선분들로 이루어진 유향폐곡선(한 점에서 출발하여 방향이 정해진 선분들의 화살표 방향을 따라 이동하면 시작점으로 되돌아올 수 있는 폐곡선)이 만들어지면 성빈이 이긴다. 성빈이 항상 이길 수 있는 전략이 존재하는가?
양의 정수 $n$에 대하여 한 원 위에 서로 다른 $2n$개의 고정된 점이 있다. 이 점들을 다음 세 조건을 모두 만족하도록 $n$개의 화살표선(유향선분)으로 연결하는 방법의 수를 구하라.
정수 $1$, $2$, $\ldots$, $2008$이 정확히 한 번씩 수열 $a_1$, $a_2$, $\ldots$, $a_{2008}$에 나타나며 모든 $2\le i\le 2008$에 대하여 $i\in\{1,2,\ldots,a_i\}$이 될 수열 $a_1$, $a_2$, $\ldots$, $a_{2008}$의 수는 몇 개인가?
정수 $k\in \{0,1,2,3\}$와 양의 정수 $n$에 대하여 \[ x_1+\cdots+x_n\equiv k\pmod 4\]이면서 $i=1,\ldots,n$에 대하여 $x_i\in\{-1,0,1\}$인 수열 $x_1,x_2,\ldots,x_n$의 수를 $f_k(n)$이라 하자.
(a) 모든 양의 정수 $n$에 대하여 $f_1(n)=f_3(n)$임을 보여라.
(b) 모든 양의 정수 $n$에 대하여 \[f_0(n)=\frac{3^n+2+(-1)^n}{4}\]임을 보여라