본문바로가기
폴리매스 문제
아직 아무도 답을 모르는 문제에 도전하세요!
[대한수학회] 대64. 그래프 게임 문제
수학동아 2022.04.01 09:04 조회 980

대한수학회 64번

 

 

그래프 게임 문제

 

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

 

 

 

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

 

 

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

 

 

 

 

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

 

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

 

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

 

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

 

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

 

이 게임을 (G,n)-게임이라 하자.

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

 

 

 

 

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

 

1Round에서 갑이 를 선택하고, 을이 I=\left \{ v_{1}, v_{4} \right \}를 선택하면

v_{1}, v_{4}는 파란색으로 색칠되고, 에서 돌이 하나씩 제거되어 v_{2}와 v_{3}에는 두개의 돌이 남는다.

 

2Round에서 갑이 S=\left \{v_{2}, v_{3}, v_{5} \right \}를 선택하고, 을이 를 선택하면, v_{2}, v_{5}는 파란색으로 색칠되고

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

 

3Round에서 갑이 S=\left \{v_{3}, v_{6} \right \}을 선택하면, 을은 I=\left \{ v_{3}, v_{6} \right \}을 선택할 수 있고, 이때 v_{3}와 v_{6}도 파란색으로 색칠되어 을이 승리하게 된다.

 

 

 

 

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

 

 

 

 

 

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

 

 

 

문제 2. 그래프 G에 대하여 \bigtriangleup (G)를 G의 최대 차수라고 하자. (G,    riangle (G)+1)-게임은 을이 항상 이길 수 있음을 보여라.

 

 

 

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

 

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

 

예를 들어, 적어도 하나의 변을 갖는 수형도 F에 대하여 d(F)=1이다. 이 때, (G, d(g)+1)게임은 을이 항상 이길 수 있음을 증명하여라. 

 

 

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

 

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

 

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

 

 

 

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

 

 

 

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

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

 

 

 

끝.

 

 

 

  •  
    다시 도전
    pure math Lv.6 2022.04.01 10:11 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수2
    •  
      김준수 Lv.2 2022.04.06 01:18 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      pure math Lv.6 2022.04.06 17:46

      넵!수정하겠습니다!

      좋아요0
  •  
    다시 도전
    pure math Lv.6 2022.04.01 10:26

    1.

    임의의 한 점 v에 대해서 S의 부분집합 중 독립그래프이면서 v를 포함하는 집합을 2개를 넘어가지 않도록 갑이 만들 수 있으므로 갑이 승리한다.

    (만일 첫번째에서 선택을 받지 못해 돌이 하나가 없어졌다 하더라도 결국엔 나중에 을은 그 꼭짓점을 포함하는 그래프를 만들어야 되며, 모든 그래프의 부분집합 중 독립그래프는 존재하므로, 또한 점도 독립집합이므로 그 꼭짓점을 파란색으로 만들 수 있고, 모든 임의의 꼭짓점에 대해서도 이렇게 할 수 있으므로 가능하다.)

    댓글 작성하기 좋아요1 댓글수0
  •  
    pure math Lv.6 2022.04.01 10:28

    2번과 3번에서 을이 아니라 갑이 이길 수 있다는 것 아닌가요?

    댓글 작성하기 좋아요1 댓글수2
    •  
      asdf3 Lv.4 2022.04.01 16:24

      그런데 2번에서 갑이 항상 이길수는 없지 않나요?

      좋아요0
    •  
      pure math Lv.6 2022.04.01 16:51

      네 뭐 암튼.. 문제가 헷갈리네요

      좋아요0
  •  
    asdf3 Lv.4 2022.04.01 17:09

    문제 2번은 채색수와 관련있을 것 같아요!

    댓글 작성하기 좋아요0 댓글수0
  •  
    RedoC Lv.5 2022.04.01 17:36

    저만 지문에 있는 수식 중 일부가 깨져서 보이나요?

    OS는 macOS 12.0.1입니다.

    댓글 작성하기 좋아요0 댓글수1
    •  
      asdf3 Lv.4 2022.04.01 17:56

      저도 (H,3) 예시 설명하는 부분이 깨져서 보여요.

       

      좋아요0
  •  
    asdf3 Lv.4 2022.04.01 18:23

    문제 2: 일단 X(G)<=\Delta(G)+1=n 이므로 그래프 G를 서로 다른 n개의 색으로 칠할 수 있습니다.(x(G)는 그래프 G의 채색수)

    을은 (갑이 구성한 집합 S의 원소 수)/n 이상의 점을 파란색으로 칠할 수 있습니다.

     

    댓글 작성하기 좋아요0 댓글수0
  •  
    부분해결
    RedoC Lv.5 2022.04.01 22:18 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수2
    •  
      RedoC Lv.5 2022.04.01 22:21 비밀댓글
      비밀 댓글이 등록 되었습니다!
    •  
      김준수 Lv.2 2022.04.06 01:28

      깔끔하게 잘 해결했습니다. 문제의 의도대로 잘 푼 것 같네요!

       

       

      좋아요0
  •  
    RedoC Lv.5 2022.04.01 22:27
    확인요청중

    2.

    댓글 작성하기 좋아요1 댓글수0
  •  
    RedoC Lv.5 2022.04.02 11:33

    승리수가 뭔가요?

     

    댓글 작성하기 좋아요0 댓글수2
    •  
      RedoC Lv.5 2022.04.02 19:35

      @에프매스

      좋아요0
    •  
      유지연_매니저 Lv.15 2022.04.05 13:17

      승리수 관련 부분을 추가했어요!

      좋아요1
  •  
    부분해결
    asdf3 Lv.4 2022.04.03 00:24

    댓글 작성하기 좋아요0 댓글수1
    •  
      김준수 Lv.2 2022.04.06 01:36

      잘 해결했습니다! 수고했어요 

      좋아요0
  •  
    A math Lv.7 2022.04.06 18:02 비밀댓글
    확인요청중
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수2
    •  
      A math Lv.7 2022.04.06 18:10

      2번을 보니 풀이가 틀린 것 같네. 뭔가 잘못 이해한 건가

      좋아요0
    •  
      A math Lv.7 2022.04.06 18:11

      아. 조건 하나 빼먹었다. 

      좋아요0
  •  
    A math Lv.7 2022.04.07 08:50

    문제 3의 d(G)가 최대 차수와 다른 점이 있나요

    댓글 작성하기 좋아요0 댓글수2
    •  
      강지원 멘토 Lv.3 2022.05.12 00:01

      아마 '가장 큰 음이 아닌 정수 d'가 아니라 '가장 작은 음이 아닌 정수 d'로 의도하신 게 아닌가 싶네요. 'G'의 모든 점은 차수가 d 이하다'가 아니라 'G'에 차수가 d 이하인 꼭짓점이 존재한다'기 때문에 최대 차수보다 낮은 값도 가능할 수 있습니다.

      좋아요0
    •  
      A math Lv.7 2022.05.12 07:04

      좋아요0
  • 폴리매스 문제는 과학기술진흥기금 및 복권기금의 재원으로 운영되고, 과학기술정보통신부와 한국과학창의재단의 지원을 받아 수행된 성과물로 우리나라의 과학기술 발전과 사회적 가치 증진에 기여하고 있습니다.

  • ☎문의 02-6749-3911