도쿄대 2021-2(문과)

 

 

 

5 이상의 자연수 N이 있다. 1 부터 2N 까지의 자연수 중 1을 포함하여 서로 다른 N개의 수를 골라 집합 S를 만들자. 

각 조건을 만족하는 집합 S의 경우의 수를 구하여라.

 

1) S는 연속하는 2개의 자연수 쌍을 갖지 않는다.

2) S는 연속하는 N-2 개의 자연수 쌍을 적어도 하나 포함한다.

 

---

생각해보기) 경우의 수 문제이지만 전체 개수가 미지수인 경우이다.

처음부터 일반적인 case를 생각하기가 쉽지 않으므로, 작은 N에 대한 special case를 먼저 생각해보자.

가장 작은 N=5 인 경우를 생각해보면,

 

OXOOOXOX

OXOXOOOX

OOOXOXOX

OOOXOOX

OOXOOOX

 

위와 같이 5가지 case 를 생각할 수 있고, 각 case마다 X를 적절하게 넣는 경우의 수만 생각하면 되는 것이다.

N이 커져도 새로운 case가 추가 되는 것은 아니기 때문에, 자연스럽게 일반화를 할 수 있다.

 

 

풀이)