어떤 나라에 $n$개의 도시 $1,2,\ldots,n$가 있다고 하자. 두 도시를 잇는 고속도로를 정확히 $n-1$개를 건설해서 모든 도시가 다른 도시에서 도로를 여러개 이용해서 도달가능하게 만들고자 한다. 그런데 두 도시의 수 차이가 정확히 $1$이면 그 사이 도로를 건설하는 것은 금지되어 있으며, 도시 $1$과 도시 $n$ 사이에도 도로 건설이 금지되어 있다고 한다. 이렇게 도로를 건설하는 방법의 수를 $T_n$이라 하자.
(a) $n$이 홀수이면 $T_n$이 $n$의 배수가 됨을 증명하라.
(b) $n$이 짝수이면 $T_n$은 $n/2$의 배수가 됨을 증명하라.
(2013년 6월 25일, 4시간 반동안 3문제, 출처)