2017 제9회 베네룩스수학올림피아드 2번문제

정수 $n\ge2 $이 있다. 총 $n$개의 섬으로 구성된 어떤 나라에서 엘리스와 밥이 아래와 같은 게임을 한다. 이 섬 중 정확히 두 섬만 공장을 가지고 있다. 처음에 이 나라에는 다리가 하나도 없다. 엘리스와 밥은 돌아가면서 각자 자기 차례가 되면 서로 다른 두 섬 $I_1$, $I_2$를 골라 그 사이에 다리를 놓는데, 아래 두 조건을 반드시 만족시켜야 한다.

  • 기존에 $I_1$과 $I_2$ 사이에는 다리가 없었다.
  • $I_1$과 $I_2$ 중 적어도 하나의 섬에서는 다리를 여러 번 지나서 공장이 있는 섬으로 이동할 수 있다 (혹은 그 섬에 공장이 있다). (즉, 다리를 짓기 위해서는 공장으로 이동할 수 있는 길이 있어야 한다.)

한 공장에서 다른 공장으로 이동할 수 있도록 다리가 연결되는 순간 마지막 다리를 놓은 사람이 진다. 엘리스가 먼저 시작하는 경우 각 $n\ge2$에 대하여 누가 필승 전략을 가지고 있는지 결정하라. (단, 다리가 다른 다리 위로 지나가도록 건설할 수 있다.)

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