2016 미국수학올림피아드 6번문제

양의 정수 $n$과 $k$가 $n\ge k\ge2$를 만족시키도록 주어져 있다. 당신은 마법사와 아래와 같은 게임을 한다.

마법사는 $2n$개의 카드를 가지고 있다. 각각의 $i=1,2,\ldots,n$에 대해, $i$라고 표시된 카드가 두 장 있다. 처음에 마법사는 모든 카드를 수가 적힌 면이 보이지 않도록 뒤집어서 한 줄로 늘어놓는데, 그 순서가 어떤 것인지 알 수 없다.

당신은 다음과 같은 시행을 여러번 할 수 있다: 당신이 카드 $k$개를 아무렇게나 가리키면, 마법사는 그 가리킨 카드를 모두 뒤집는다. 만일 그 카드 중 어느 두 장이라도 같은 것이 있다면 게임이 끝나고 당신이 이긴다. 같은 것이 없다면 당신이 잠깐 눈을 감은 동안 마법사는 그 카드를 다시 뒤집은 후 아무렇게나 다시 섞어서 한 줄로 늘어놓는다. 그후 다시 당신 차례가 된다.

만일 최대 $m$번의 시행만으로 항상 이 게임에서 마법사가 어떻게 하더라도 당신이 이길 수 있는 전략이 있다면 이 게임을 이길 수 있는 게임이라고 하자.

어떤 $n$과 $k$ 값에 대하여 이 게임이 이길 수 있는 게임이 되는가?

GD Star Rating
loading...
이 글은 조합 카테고리에 분류되었고 mo님에 의해 작성되었습니다. 고유주소 북마크.