폴리매스

대한수학회 64번

그래프 게임 문제

문제 출제자 : 김린기 인하대학교 수학과 교수

* 2022. 04. 05. 수식 깨짐 부분, 문제3에 승리수 부분 수정사항이 있습니다.

==================================================================================

주어진 그래프 와 자연수  에 대하여, 갑과 을은 다음과 같은 게임을 한다.

게임 시작 전에 그래프  의 모든 꼭짓점은 빨간색으로 색칠되어 있고, 각 꼭짓점에는 개의 돌이 놓여있다. 게임이 끝나기 전까지 매 라운드마다 갑과 을은 다음의 시행을 한다.

갑: 의 빨간색 꼭짓점들로 구성된 집합 를 선택한다.

을: 독립 집합 를 선택하여 의 모든 꼭짓점을 파란색으로 색칠하고, 의 각 꼭짓점에서 돌을 하나씩 제거한다. (그래프의 꼭짓점의 집합 에 대하여, 의 임의의 두 꼭짓점이 서로 연결되어 있지 않으면 를 독집 집합이라 한다.)

각 라운드가 끝났을 때, 만약 돌이 남아 있지 않은 빨간색 꼭짓점이 생기면 갑의 승리로 게임이 끝나고, 모든 꼭짓점이 파란색으로 색칠되면 을의 승리로 게임이 끝난다.

이 게임을 -게임이라 하자.

예를 들어, 그래프 가 아래와 같이 주어졌을 때, -게임은 다음과 같이 진행된다.

게임 시작 전에 의 꼭짓점은 빨간색으로 색칠되어 있고, 각 꼭짓점에는 3개의 돌이 놓여있다.

1Round에서 갑이 를 선택하고, 을이 를 선택하면

는 파란색으로 색칠되고, 에서 돌이 하나씩 제거되어 와 에는 두개의 돌이 남는다.

2Round에서 갑이 를 선택하고, 을이 를 선택하면, 는 파란색으로 색칠되고

에서 하나의 돌이 제거되어 한 개의 돌만 남는다.

3Round에서 갑이 을 선택하면, 을은 을 선택할 수 있고, 이때 와 도 파란색으로 색칠되어 을이 승리하게 된다.

값과 을은 항상 최선의 전략으로 게임을 한다고 한다. 

문제 1. 위에서 정의된 그래프 에 대하여, -게임은 갑이 이길 수 있을까?

문제 2. 그래프 에 대하여 를 의 최대 차수라고 하자. -게임은 을이 항상 이길 수 있음을 보여라.

문제 3. 그래프 에 대하여 를 다음을 만족하는 가장 큰 음이 아닌 정수 로 정의하자.

  조건 : 의 임의의 부분 그래프 에 대하여 에는 차수가  이하인 꼭짓점이 존재한다.

예를 들어, 적어도 하나의 변을 갖는 수형도 에 대하여 이다. 이 때, 게임은 을이 항상 이길 수 있음을 증명하여라. 

그래프 에 대하여, 다음을 만족하는 가장 작은 자연수 을 승리수라고 하자.

조건 : 게임에서 을이 항상 이길 수 있다.

문제 3에 의하여 의 승리수는 이하임을 알 수 있다.

문제 4. 순환 그래프의 승리수를 각각 구하여라.

문제 5. 임의의 그래프 에 대하여, 의 승리수는 의 강한 채색수보다 크거나 같음을 증명하여라.

(강한 채색수의 정의는 대한수학회 56번 문제 참고)

끝.