주메뉴바로가기.. 본문바로가기

Problems

폴리매스 문제 보기

문제

[국가수리과학연구소] 국25. 심심할 땐 NIM과 함께!

2019.01.02

같이 풀어볼까?

네이버밴드 구글플러스

 

국가수리과학연구소의 25번째 문제입니다.

 

서은이와 동수는 바둑돌로 NIM 게임을 하기로 했다. NIM 게임은 여러 개의 돌 무더기에서 돌을 번갈아가며 가져가는 게임이다. 편의상 서은이가 먼저 돌을 가져간다고 하자. NIM 게임의 규칙은 다음과 같다.

 
①먼저 돌 무더기를 몇 개 준비한다 (예: 각각 돌 3개, 5개, 7개가 있는 돌 무더기 총 3개).

②다음 서로 번갈아가며 한 번씩 돌을 가져간다. 매 턴마다 돌을 가져가는 사람은 무더기들 중 하나를 골라 그 무더기에서 원하는 만큼 돌을 가져간다. 적어도 1개 이상의 돌을 가져가야 하고, 고른 무더기의 돌을 전부 가져갈 수도 있다. 하지만 두 개 이상의 무더기에서 돌을 1개 이상씩 가져갈 수는 없다.

③이 때 처음으로 모든 돌을 다 없애는 사람이 이긴다. 즉, 마지막 돌을 가져가는 사람이 이긴다.

 

 

[문제]

 

1.

서은이와 동수가 최선을 다해 NIM 게임을 할 때, 서은이가 게임을 이길 조건은 무엇일까? 이 조건을 처음 돌 무더기들의 돌 개수와 연관지어 설명해보자.
(이미 알려진 답을 참고해 답을 작성해도 수학적인 이유를 잘 설명하기만 하면 정답으로 인정한다. 단, 참고한 자료의 출처를 명확히 밝히고 다른 사람들도 이해하기 쉽게 쓰기를 권장한다.) 

 

2.

규칙을 바꿔보자. NIM 게임 규칙에서 서은이와 동수가 돌을 많아야 k개 이하로만 가져갈 수 있다고 하자. (k는 고정된 양의 정수). 서은이가 게임을 이길 조건은 무엇일까?

 

3.

돌을 가져갈 때 매번 최대 k개 돌 무더기를 골라 각 무더기에서 원하는 만큼 돌을 가져갈 수 있다고 하자. k개 미만의 돌 무더기에서 가져가는 것도 허용하지만, 적어도 1개 이상의 돌을 가져가야 한다. 이때 서은이가 게임을 이길 조건은 무엇일까?

 

4.

돌 무더기를 왼쪽부터 돌 개수가 적은 순서(오름차순)대로 나열했다고 하자. 즉, 인접한 두 돌 무더기에서 오른쪽 돌 무더기의 돌 개수는 적어도 왼쪽의 돌 무더기만큼 있다. 돌을 가져간 뒤에도 돌 무더기들의 돌 개수가 항상 오름차순이 유지돼야 한다면, 서은이가 게임을 이길 조건은 무엇일까?

 

5.

매번 무조건 k개의 돌 무더기를 골라 각 무더기에서 돌을 적어도 1개 이상 가져가야 한다고 하자. 서은이가 게임을 이길 조건은 무엇일까?

 

※알립니다.

algebra, 됴쑨 친구가 소문제 1번을 해결했어요!

댓글 27

  • ln -1=pi*i 2019.01.02 20:13:36

    1번 문제는 언제든 서은이가 이길 수 있습니다. 동수가 돌 몇 개를 남기면 처음에는 나머지를 다 가져가고 두 번째도 그러면 마지막 무더기에 돌을 1개만 남기면 됩니다. 두 번째 무더기를 다 가져가면 서은이는 마지막 무더기를 다 가져가면 이깁니다. 하지만 서은이의 차례에 1개짜리 무더기가 2개가 생기면 지게된다.

    동수가 첫 번째 무더기를 다 가져가면 서은이는 두 번째 무더기의 돌을 2개만 남기고 가져가면 된다. 동수가 남은 2개를 다 가져가면 이기고, 동수가 세 번째 무더기를 다 가져가도 이긴다. 그리고 남은 2개 중 1개만 가져가면 마지막 무더기에 1개만 남기고 가져가면 이긴다. 또, 동수가 마지막 무더기에서 몇 개의 돌만 남기면 자유롭게 진행하되 서은이의 차례에 1개짜리 무더기가 2개가 생기지 않게 해야 이길 수 있다.

    즉 처음 돌 무더기의 개수와는 상관없이 서은이의 차례에 1개짜리 돌무더기가 2개가 아니면 이길 수 있다.

    좋아요0 댓글수5
    • 수학장 2019.01.03 22:45:46

      반례 : 돌 3개짜리 돌 무더기가 4개인 경우

      절대 이길 수 없다.

      서은이가 뭘 가져가든 동수가 똑같이 가져가면 된다.

      일반적으로, 돌의 개수가 같은 돌무더기가 짝수 개씩 있으면, 서은이가 돌을 가져갈 때 마다 동수가 계속 돌의 개수가 같은 돌무더기에서 똑같은 양을 가져가면 서은이는 절대 이길 수 없다.

      좋아요0
    • 디듀우 2019.01.04 07:38:05

      1번 문제에서는 각 돌 개수가 같은 돌무더기가 짝수 개씩 있고 개수 상관없이 돌무더기가 하나 더 있으면 됩니다. 그 이유는 일단 서은이가 나머지 돌무더기를 모두 가져가고, 그러면 남은 돌무더기에 대해 수학장님의 풀이대로 하면 동수가 절대 이길 수 없습니다. 더 포괄적인 경우도 있을 것 같긴 합니다.

      좋아요0
    • ln -1=pi*i 2019.01.05 15:21:40

      결국 이것도 마지막에 나온서은이의 차례에 1개짜리 돌무더기가 2개가 되는 것 아닌가요?

      좋아요0
    • 디듀우 2019.01.05 16:41:11

      예를 들어 3개짜리 돌무더기 1개, 5개짜리 돌무더기 4개, 7개짜리 돌무더기 2개로 NIM게임을 한다고 하면 서은이가 먼저 3개짜리 돌무더기를 없애고 동수가 가져가는 만큼 같은 개수가 남은 돌무더기에서 똑같이 가져간다는 것입니다.

      좋아요0
    • 신월초 송수진 2019.01.09 10:26:16

      반례: 돌의 개수가 같은 돌 무더기가 짝수 개 있을 때

      좋아요0
  • algebra 2019.01.05 03:19:57

    영문 위키백과에서 찾아보니까 각 돌 무더기의 돌 수의 NIM-sum이 0이 되게 할 수 있다면 반드시 이길 수 있다고 합니다. 즉, 만약 서은이가 처음 시작한다면 NIM-sum이 0이 아닌 경우에, 두 번째 순서일 때는 NIM-sum이 0인 경우에 반드시 이긴다는 겁니다.

     

    여기서 NIM-sum이란 여러 수들을 이진수로 바꾼 뒤 XOR을 적용했을 때 나온 값을 다시 십진수로 바꾼 값으로, 기호는 \tiny \bigoplus을 사용합니다. (XOR은 입력값이 다를 때 '참'을 출력하는 논리적 연산입니다. 쉽게 말해 0 XOR 0=0, 0 XOR 1=1, 1 XOR 0=1, 1 XOR 1=0입니다. 집합으로 말하자면 두 집합의 합집합에서 교집합을 뺀 것이라고 볼 수 있습니다.) 예를 들어서, 3\tiny \bigoplus6\tiny \bigoplus7을 계산하고 싶다면 3=11(2)(혹은 011(2)), 6=110(2), 7=111(2)이고, 0 XOR 1 XOR 1=0, 1 XOR 1 XOR 1=1, 1 XOR 0 XOR 1=0이며, 결과적으로 010(2)=2이므로 3\tiny \bigoplus6\tiny \bigoplus7=2입니다.

     

    증명도 이해해보려 했지만...제가 영어도 못하고 컴퓨터과학도 하나도 몰라서...(주륵)

    다른 분들은 이해하실 거라 믿으며 위키백과 링크를 남깁니다! 저도 노력해볼게요^^

     

    http://en.wikipedia.org/wiki/Nim

    http://en.wikipedia.org/wiki/Exclusive_or

    좋아요0 댓글수2
    • 됴쑨 2019.01.05 22:02:11

      이건 제가 정리를 해드릴게요

       

      ◇ 승리 판별법
      모든 더미들의 NIM-sum을 구해서 이 값이 0이라면 나중에 시작하는 사람이 이기고, NIM-sum이 0이 아니라면 먼저 시작하는 사람이 이깁니다.

       

      ◇ 이진법이란?
      이 문단은 생략하겠습니다. 모르는 분이 있으면 다른분이 설명해주세요.

       

      ◇ XOR이란?
      0 또는 1의 값만 가질수 있는 하나의 수를 비트라고 하는데, XOR은 비트를 가지고 하는 연산입니다. "exclusive OR"의 약자인데 어원에 관한 추가설명은 하지 않겠습니다. 기호는 ⊕인데, 이 기호대신 그냥 XOR을 쓰겠습니다.
      0 XOR 0 = 0
      0 XOR 1 = 1
      1 XOR 0 = 1
      1 XOR 1 = 0 을 만족합니다.
      XOR은 결합법칙과 교환법칙이 성립합니다. (증명 생략) 즉,
      (a XOR b) XOR c = a XOR (b XOR c)와
      a XOR b = b XOR a를 만족하기 때문에 XOR 연산을 여러번 하고싶을땐 괄호 안쓰고 하고싶은 순서대로 해도 됩니다.
      예시) 0 XOR 1 XOR 1 XOR 0 XOR 1 = 1 처럼 구할 수 있습니다.
      이 값을 빨리 구하려면 홀짝을 생각하시면 편합니다. 1의 개수를 세서 홀수개면 1, 짝수개면 0이 나옵니다.

       

      ◇ bitwise-XOR이란?
      비트 여러개짜리 문자열로도 XOR을 할 수 있습니다. 여기서 사용되는 수들은 전부 이진법입니다. "비트의 문자열"과 "이진법의 수"는 아주 비슷해서 구분하지 않고 써도 괜찮습니다.
      10010 XOR 11011을 구하고 싶다면 비트단위로(bitwise) XOR을 계산하게 되고 결과는 01001이 됩니다. 직접 확인해봅시다.
      판별법에서 나온 NIM-sum이란 각 더미당 돌의 개수를 이진법으로 나타낸 후 모두 bitwise-XOR을 계산해서 나오는 값을 말합니다. 
      예) 세 무더기에 돌이 3개, 5개, 7개 있을 경우 각각 이진법으로 고치면 11, 101, 111이 되고 이들의 NIM-sum은 (011 XOR 101) XOR 111 = 001이 됩니다. 따라서 이 게임은 먼저 해서 이길수 있습니다.

       

      ◇ 판별법은 왜 성립하는가?
      돌이 하나도 없는 상태는 NIM-sum이 0이고,
      NIM-sum이 0인 상태에서는 어떻게 행동해도 NIM-sum이 0이 아닌 값이 되고,
      NIM-sum이 0이 아닌 상태에서는 NIM-sum을 0으로 만드는 방법이 반드시 존재하기 때문입니다.
      게임을 할땐 항상 자기 차례에서 NIM-sum을 0으로 만들어서 상대에게 주면 됩니다.


      (계속)

      좋아요0
    • 됴쑨 2019.01.05 22:32:46

      (이어서)


      ◇ NIM-sum을 0으로 만드는 법
      NIM-sum을 비트 문자열로 구해서 1이 있는 가장 높은 자리(가장 왼쪽 자리 또는 most significant bit)가 어디인지 찾고, 돌 개수의 이진법 표현 중 그 찾은 자리가 1인 무더기 중에서 아무 무더기나 골라서 정확히 NIM-sum만큼의 '비트 변화'를 주면 됩니다. 다른말로 하면, (그 무더기의 돌의 개수) XOR (NIM-sum)을 계산해서 나온 값만큼 남도록 돌을 가져가면 됩니다.
      예시)
      세 무더기에 돌이 3개, 5개, 7개가 있다면 이진법으로 고치면 011, 101, 111이고
      NIM-sum은 001입니다. (앞자리에는 원하는만큼 0을 붙이고 뗄 수 있습니다.)
      돌 개수의 일의자리가 1인 무더기(셋 다 해당됨)에서 아무 무더기나 고릅시다. 5개짜리 무더기를 골랐다고 하면 XOR값에 001만큼의 변화를 주면 됩니다. 여기선 하나를 가져가면 되겠네요.

       

      ◇ 보조정리 1. NIM-sum이 0인 상태에서 어떻게 돌을 가져가도 NIM-sum이 0이 아닌 상태가 된다.
      XOR은 임의의 비트 문자열에 대해서 A XOR A = 0, 0 XOR A = A를 만족합니다. 또 A XOR B = 0이면 A=B입니다.
      돌 세 무더기에 각각 A, B, C개가 있다고 하고 A XOR B XOR C = 0이라고 합시다. C개짜리 무더기에서 돌을 가져가서 D개가 되었다고 하면 새로운 NIM-sum의 값은
      A XOR B XOR D
      = (A XOR B XOR C) XOR C XOR D
      = C XOR D입니다. 그런데 C와 D는 다른 값이므로 이 NIM-sum은 0이 될수 없습니다.


      ◇ 보조정리 2. NIM-sum이 0이 아닌 상태에서는 NIM-sum을 0으로 만드는 방법이 반드시 존재한다.
      위에 "0으로 만드는 방법" 항목에서 NIM-sum을 계산하고 1이 있는 가장 높은 자리가 p번째 자리라고 합시다. (값으로 치면 2^(p-1)의 자리) NIM-sum을 계산하려면 자리별로 계산하기 때문에 돌무더기 중에서 p번째 자리가 1값이 나오는 무더기가 홀수개가 있어야 합니다. 따라서 그런 무더기가 반드시 하나는 존재합니다.
      NIM-sum 값을 n, 그 무더기의 돌의 개수를 m이라고 합시다. 이제 m에 n만큼의 '변화'를 줄 수 있는지를 밝혀야 합니다. 이는 m개짜리 무더기에서 돌 몇개를 가져가서 (m XOR n)개로 만들수 있는가와 동치이고, m > (m XOR n)인가와 동치입니다. (여기서 부등호는 이진법의 수 크기비교를 의미합니다)
      여기서 n은 p자리의 수이고 m은 p자리 이상의 수입니다.
      예시) n=0000010011, m=1110011010, p=5
      m XOR n을 계산하면 p번째보다 높은 자리는 m의 자리와 같고, p번째자리는 0이고(왜냐면 m과 n에서 둘다 1이므로), p번째보다 낮은 자리는 어떻게든 나옵니다.
      예시) m XOR n = 1110001001
      그러면 이 값을 m과 크기비교하면 p번째자리에서 크기가 갈리게 됩니다. m > (m XOR n) 이 성립하게 되죠. 따라서 m개짜리에서 돌을 가져가서 (m XOR n)개로 만들 수 있습니다.

       

      아는대로 끄집어내서 길어진것 같네요. 요약이 필요할지도 모르겠습니다. 더 엄밀한 증명이 필요하다면 다른분께 넘깁니다.

      아 저는

      https://librewiki.net/wiki/필승_전략_게임

      여기를 참고했습니다

       

       

       

      좋아요0
  • 인천 오일러 2019.01.05 22:28:16

     algebra 님과 됴쑨 님의 자료를 보면 2번 문제는 각 더미의 수를 k진법으로 표현해 각 자릿수별 합을 법 k로 표현한 값을 NIM-sum으로 정의하고  NIM-sum을 구해 0이 안 되면 이길 수 있을 것 같네요. 아니면 다르게 일반화하거나요. 됴쑨님께서 말씀하신 것 처럼 돌이 하나도 없으면 NIM-sum이 0이고, NIM-sum이 0인 상태에서는 어떻게 행동해도 NIM-sum이 0이 아닌 값이 됩니다.
    NIM-sum이 0이 아닌 상태에서는 NIM-sum을 0으로 만드는 방법의 규칙성을 알아내야 할 것 같습니다. 자기 차례에서 NIM-sum을 0으로 만들어서 상대에게 주면 됩니다. 돌이 하나도 없는 상태를 자신이 만들도록 하는겁니다.

    좋아요0 댓글수3
    • 됴쑨 2019.01.05 22:39:15

      저는 k진법보다는 단순히 k로 나눌때 몫과 나머지를 사용해야 되지 않을까하고 생각해봤습니다. 최대 k개만 가져갈수 있기때문에 k진법으로 나타냈을때 k^2의 자리 이상은 건드릴수 없으니까요.

      그리고 XOR 대신 '다 더하고 mod k' 연산을 도입해야 될것 같습니다. XOR은 결국 '다 더하고 mod 2' 연산이거든요.

      좋아요0
    • 인천 오일러 2019.01.05 22:44:13

       됴쑨님 말씀이 맞는 것 같습니다. 방금 생각났는데 논리연산을 3진법 이상에서 사용하면 이상하네요. 수정하겠습니다.

      좋아요0
    • 됴쑨 2019.01.08 14:38:55

      2번에서 만약 돌무더기가 하나라면 남은개수가 k+1의 배수가 되도록 계속 만들어서 상대에게 '먼저하면 지는 모양'을 주면 됩니다.

      돌무더기가 여러개이면서 각 무더기에 돌이 k개 이하라면 1번의 NIM-sum을 쓰면 됩니다.

      그러면 돌무더기가 여러개이면서 개수도 제각각인 경우라면 k+1개 가져가서 NIM-sum이 0이 된다면 그게 '먼저하면 지는 모양' 아닐까요?

      이렇게 생각해보니 '다 더해서 mod k'를 쓰지는 않네요.

      좋아요0
  • 김우현 기자 2019.01.07 15:11:15

    algebra 친구가 잘 요약해줬고, 됴쑨 친구가 자세히 설명해줬네요. 

    소문제 1번은 두 친구가 맞힌 걸로 하겠습니다!smiley

    좋아요0 댓글수1
    • shaina왕눈이 2019.01.11 17:54:55

      주니어 폴리매스 엘레베이터 문제 잠깐 봐주실 수 있나요

      좋아요0
  • 송수진 2019.01.08 21:26:59

    5번  문제는 서은이가  돌을  1번째 차례에 전부 다 가져가면 된다.

    좋아요0 댓글수6
    • 구머 2019.01.08 21:36:32

      와우

      좋아요0
    • 수학장 2019.01.09 10:20:46

      ㅋㅋㅋㅋㅋㅋ

      좋아요0
    • 인천 오일러 2019.01.09 10:22:54

      이거를 이렇게?

      좋아요0
    • 여백 패르마 2019.01.09 11:00:54

      ㅋㅋㅋㅋ k가 전체 돌무더기 개수이면 되겠네욬ㅋㅋ

      좋아요0
    • 아인수타인 2019.01.10 19:23:36

      ㅋㅋㅋ어떻게 그런 생각을ㅋㅋ

      좋아요0
    • 수학장 2019.01.10 20:31:18

      근데 k는 정해져 있는 상수입니다. 한 번 k를 정했으면 k보다 많이 또는 적게 가져갈 수 없죠. k는 임의로 서은이가 정하는 게 아닙니다.

      좋아요0
  • 송수진 2019.01.09 08:16:56

    4번 문제에서는 서은이가 항상 왼쪽 끝에 있는 돌 무더기에서 1개를 남기고 다 가져간다. 2번째 무더기는 2개,n번째 무더기에서는 n개를 남긴다 .그런 다음 1번째 무더기에서 돌을 다 가져가고 2번째 무더기에서도 다가져간다. 무더기에 개수를 A라고 하면 A-3번째 무더기에서 돌 1개를 남긴다. A번째 무더기에서는 3개를 남긴다.A-2번째 무더기에서는 2개.

    동수가 1번째 무더기에서  돌 1개를 가져갇다. 서은이는 2번 무더기에 있는 돌을 전부 다 가져간다. 동수가 무엇을 하든 서은이가 이긴다.

    좋아요1 댓글수1
    • algebra 2019.01.11 00:52:39

      그런데 서은이랑 동수가 번갈아 가면서 돌을 가져가니까 서은이 n번째 무더기에서 돌 n개를 남기고 가져가는 동안 동수가 더 가져가서 돌의 개수에 변화가 생길 수도 있지 않을까요? 그로 인해 서은이의 계획이 틀어질 수 있을 것 같습니다만...

      좋아요0
  • 신월초 송수진 2019.01.10 22:51:04

    5번 문제는 2k> N(N은 돌무더기 개수) 일 때 서은이가 항상 이긴다.왜냐하면 서은이가 1개를 남기고 다 가져가면 동수가 무엇을 하든 돌무더기가 k개보다 적기 떄문이다. 

    좋아요0 댓글수1
    • 신월초 송수진 2019.01.10 22:57:02

      2k< N 일떄일때 생각해 보는 것이 좋을 것 같습니다.

       

      좋아요0
  • 수학자 2019.01.17 15:52:40

    일단 5번 문제는 "돌을 더 이상 가져갈 수 없는 쪽이 진다"고 설명하는 게 정확하겠네요. 무더기가 k-1개 이하면 돌을 가져갈 방법이 없으니깐요.

    좋아요0 댓글수0