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

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.

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

 

5.

매번 무조건 k개의 돌 무더기를 골라 각 무더기에서 돌을 적어도 1개 이상 가져가야 한다고 하자. 서은이가 게임을 이길 조건은 무엇일까? 단, 이 문제의 경우에는 돌을 가져가지 못하는 사람이 진다고 하자. 즉, k개 미만의 돌 무더기를 받은 사람이 진다.

 

※알립니다.

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

 

※문제를 수정합니다.

소문제 4번: 문제 끝에 조건을 추가합니다.

단, 여기서 한 무더기의 돌을 다 가져가는 건 그 더미의 돌 개수를 0으로 만드는 것으로 간주한다. 즉, 0개의 돌 무더기를 포함해 모든 더미들이 오름차순을 이뤄야 한다.

 

소문제 5번: 아래 조건을 변경합니다.

이 때 처음으로 모든 돌을 다 없애는 사람이 이긴다. 즉, 마지막 돌을 가져가는 사람이 이긴다가 아닌 돌을 가져가지 못하는 사람이 진다는 조건으로 풀어주세요.

즉, k개 미만의 돌 무더기를 받은 사람이 지는 것입니다.

 

혼란을 드려 죄송합니다crying

댓글 58

  • 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'를 쓰지는 않네요.

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

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

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

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

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

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

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

    좋아요0 댓글수7
    • 구머 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는 임의로 서은이가 정하는 게 아닙니다.

      좋아요1
    • 222 2019.06.02 14:30:30

      오!

      좋아요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\geq 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 댓글수1
    • 김우현 기자 2019.01.25 14:06:37

      지적해줘서 고마워요, 수학자 친구!

      연구원님과 상의해 문제를 일부 수정했습니다!!surprise

      좋아요0
  • 수학자 2019.01.27 23:57:04

    2번 문제 풀이입니다.

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

    결론부터 말하자면, 이 말이 맞습니다. 정확히 말해, 각 무더기의 돌의 개수를 mod (k+1)로 봤을 때 값들을 NIM-sum 해서 0이면 '먼저하는 지는 모양'입니다.

     

    원래 NIM 게임에 대한 증명에서 추가/수정되는 부분만 써 보면 다음과 같습니다.

     

    1. 만약 모든 돌무더기의 돌 개수가 k+1의 배수라면(모든 무더기가 mod (k+1)로 0이라면), 이는 먼저하면 지는 모양입니다. 어떻게 가져가더라도 그 무더기는 k+1의 배수가 아니게 되며, 상대는 가져간 곳이 k+1의 배수가 되도록 다시 가져갈 수 있습니다.

     

    2. NIM-sum이 0인 상태에서는 어떻게 돌을 가져가도 NIM-sum이 0이 아닌 상태가 되는 것은 똑같지만, 나머지를 따지기 때문에 값이 증가해버릴 수도 있습니다. 예를 들면, k=3일 때, (5 2 3)에서 (3 2 3)으로 가져가면, 나머지는 (1 2 3)에서 (3 2 3)으로 증가한 형태가 됩니다. 하지만 이런 경우, 그 무더기에서 ( k+1 - [상대가 가져간 개수] ) 만큼을 다시 가져가면, k+1로 나눈 나머지가 다시 원래 상태로 돌아가면서 NIM-sum이 0인 상태를 상대에게 줄 수 있습니다. 이 만큼 가져가는 것은 항상 가능한데, 그 이유는, 상대와 나의 한 번씩의 시행 동안 그 무더기에서 가져가는 돌은 정확히 k+1개이며, 나머지가 증가하기 위해서는 원래 나머지를 r이라 했을 때 (k+1)*t+r\geq r+\alpha에서 t>0, t\geq 1이 나옵니다. 즉 그 무더기에 최소 k+1개의 돌이 있었으므로 이 시행이 가능합니다.

     

    3. 나머지가 증가하지 않았다면, 원래 NIM 게임에서 가져갔던 대로 가져가면 됩니다. 이 때 k개보다 많이 가져가게 될 일은 없습니다. NIM-sum의 대상인 (k+1)로 나눈 나머지들이 모두 k 이하이기 때문에, 원래 NIM 게임에서의 방법대로 하면 k 이하의 수를 더 작게 만드는 것이므로, 가져가게 되는 돌의 수는 최대 k개가 되어 게임의 조건을 만족시키며 가져갈 수 있습니다.

    좋아요0 댓글수1
    • 김우현 기자 2019.01.29 15:16:06

      잘 풀었어요, 수학자 친구!

      백진언 연구원이 검토한 결과 정답이라고 합니다.laugh

      좋아요0
  • 수학자 2019.01.28 00:14:57

    4번도 조금 애매한 부분이 있네요. 무더기 하나에 있는 돌을 아예 다 가져가버리면 오름차순 조건에서 그 무더기를 무시하는 것인지, 아니면 그 무더기 역시 "돌이 0개 있는 무더기"로 간주하여 오름차순 조건을 따지는지를 명확히 해야 할 것 같아요.

    ex) 1 2 3 -> 1 0 3의 경우 전자에서는 가능, 후자에서는 불가능

    두 경우 모두 풀어보는 것도 재밌을 것 같네요.

    좋아요0 댓글수1
    • 김우현 기자 2019.01.29 15:18:38

      수학자 친구의 말이 일리가 있다는 연구원님의 의견! 4번 문제가 명확해지도록 "단 여기서 한 무더기의 돌을 다 가져가는 건 그 더미의 돌 개수를 0으로 하는 것으로 간주한다. 즉, 0개의 돌 무더기를 포함해 모든 더미들이 오름차순을 이뤄야 한다는 것이다"라는 문장을 추가하도록 하겠습니다.

      추가로 연구원님께서 두 가지 경우 모두 풀어보면 재밌을 것 같다는 의견도 전했습니다.smiley

      좋아요0
  • 볼드모트 2019.01.29 18:36:45

    3번 문제는 k의 범위에 따라 2가지로 나눌 수 있을 것 같습니다.

    i) N<k 또는 N=k 라면 서은이가 첫 번 째에 다 가져가면 됩니다

    ii) N>k 라면 N-(k+1)n 개의 무더기의 돌을 모두 가져갑니다. (단, n은 (k+1)n<N 을 만족하는 최대의 정수)

              이후 동수가 k' 개의 무더기를 비울 때마다 (k' 는 k'<k 또는 k'=k 를 만족하는 임의의 자연수)  서은이는 k+1-k' 개의 무더기를 비우면

              서은이의 차례가 끝나면 항상 (k+1)m 개의 무더기가 남으므로 m이 0이 될 때까지 진행하면 됩니다.

    3번 문제에 댓글이 별로 없길래 하나 올려봤습니다 ㅎㅎ

    좋아요0 댓글수2
    • 수학자 2019.01.29 23:17:43

      동수가 0개의 무더기를 비우는 경우가 문제가 될 수 있겠네요. "하나 이상의 무더기를 비울 수 밖에 없게 만드는 것"이 문제 해결의 포인트가 될 것 같아요.

      k=2이고 무더기의 수가 3개인 경우를 생각해봅시다. 하나 이상의 무더기를 비울 수 밖에 없는 상황은, 각 무더기에 돌이 하나씩 있는 상황 (1 1 1)입니다. 그리고 이 상황을 만들 수 있는 조건은 이전 상태가 (1 m n) 꼴인 것입니다. 즉, 돌이 하나인 무더기가 최소 하나 있는 상황입니다. 그러면 다시, 어떻게 하더라도 돌이 하나인 무더기가 생기게 되는 상황을 생각해보면, 각 무더기에 돌이 2개씩 있는 상황 (2 2 2)입니다. 계속해 나가면, 서은이가 첫 번째 시행에서 세 무더기의 돌의 개수를 같게 만드는 것이 전략이라는 것을 알 수 있습니다. 이런 식으로 무더기의 수가 임의의 자연수일 때로 확장해봐야 할 듯 하네요.

      + 이 포인트가 3번뿐만 아니라 5번에도 적용될 수 있을 듯 합니다.

      좋아요0
    • 볼드모트 2019.01.30 09:40:18

      (k+1)개의 무더기 중에서 돌의 개수가 최소인 무더기의 돌 수에 맞추어서 k개의 무더기에서 돌을 제거하면 모든 무더기의 돌 수가 같게 만들 수 있을 것 같네요

      ex) (3,5,7) -> (3,3,3,)       <- 이렇게 하면 동수가 0개의 무더기를 비워도 무조건 1개의 돌은 가져가야 하기 때문에 서은이의 전략이 통할 수 있습니다.

      좋아요0
  • code 2019.02.11 16:28:48

    3번 문제 풀이입니다.

    돌무더기 갯수를 N이라 할때,

    N<=k 라면, 서은이가 이깁니다.

    N>k 인경우중에,

    N은 k+1의 배수라고 합시다.

    이때 동수가 무조건 돌무더기 하나를 비워야하는 상황이면,

    다시말해 모든 돌무더기의 돌의갯수가 1이라면 서은이가 이기게됩니다.

    즉 이경우 모든 돌무더기의 돌의 갯수가 1이 되도록 만들면 이기게됩니다.

    만약에 모든 돌무더기의 돌의 갯수에서 1을 뺀다고 가정하면,

    이를 모두 가져가는 사람이 이기는것이므로,

    각 돌무더기에서 돌을 하나씩 뺀값의 NIM-SUM 값이 0이 아니면 서은이가 이기게됩니다.

    N이 k+1의 배수가 아닐 경우,

    N이 k+1의 배수가 되게하는 방법은 반드시 있으므로

    그 방법으로 가져갔을 때 각 돌무더기에서 돌을 하나씩 뺀값의 NIM-SUM 값이 0이 되면

    서은이가 이기게 됩니다.

    어느 방법으로도 각 돌무더기에서 돌을 하나씩 뺀값의 NIM-SUM 값이 0이 아니게 된다면,

    동수가 이기게됩니다.

    N을 k+1의 배수가되도록 하는 수를 두지 않는다고 하더라도,

    반드시 한개는 가져가야 하므로,

    동수는 각 돌무더기에서 돌을 하나씩 뺀값의 NIM-SUM 값이 0되도록 할 수 있게 됩니다.

    좋아요0 댓글수4
    • code 2019.02.11 16:44:37

      만약에 서은이가 돌무더기 하나를 통째로 가져가면,

      동수도 서은이와 같은 처지이므로,

      돌무더기 하나를 통째로 가져가야하고,

      이것이 반복되므로,

      N을 k+1의 배수로 만들기 위해 가져가야 하는 돌무더기 갯수가 홀수라면 동수가,

      짝수라면 서은이가 이기게되네요.

      (N이 k+1의 배수가 아니고 각 돌무더기 에서 하나씩을 뺀 NIM-SUM값을 0으로 만들 수 없을때의 경우입니다.)

      좋아요0
    • 수학자 2019.02.11 22:07:26

      NIM-SUM 값이 0인 상태에서 0인 상태로 갈 수 있을 것 같아요. 이를테면 (3,5,6)->(3,1,2)처럼 말이죠. 여러 무더기에서 돌을 가져갈 수 있기 때문에, 모든 돌무더기의 돌의 갯수에서 1을 빼면, 다시 재귀적으로 원래 게임의 승리 조건을 따져봐야 할 것 같네요.

      좋아요0
    • code 2019.02.14 09:48:32

      저도 뒤늦게 깨달았습니다..

      좋아요0
    • code 2019.02.14 09:50:15

      계속 반복된다고는 하지만,

      돌무더기가 끝없이 있는것이 아니기 때문에 위 방법으로 하나씩 없애가면서 하면 뭔가 풀리지 않을까요?

      좋아요0
  • kevin0610 2019.02.17 22:17:24

    소문제 4

    우선 세 무더기의 돌의 숫자를 x, y, z라고 칭한다.(이때 x<y<z이다.) x, y, z 세 수를 모두 2의 N승꼴들의 합으로 만든다. {ex)5=2의 2승+ 2의 0승} 그 후, 각 무더기들의 합을 나타낸 숫자들을 원소로 하여, 집합을 만든다. 그 후, 원소를 내림차순으로 나열한다.(이 1,2,3번 알고리즘은 y-x값보다 z-y의 값이 더 클때라고 가정하고 정한 순번이다. 만약 z-y의 값보다 y-x의 값이 더 클 경우 2,3,1의 순서로 진행한다.

    1.x와 y를 비교하여 동일한 원소가 있는 경우 x와 y에 한하여 같은 원소를 소거한다.(x와 y의 같은 원소가 모두 소거될때까지 반복한다.)

    2.x와 z를 비교하여 동일한 원소가 있는 경우 x와 z에 한하여 같은 원소를 소거한다.(x와 z의 같은 원소가 모두 소거될때까지 반복한다.)

    3.y와 z를 비교하여 동일한 원소가 있는 경우 y와 z에 한하여 같은 원소를 소거한다.(x와 y의 같은 원소가 모두 소거될때까지 반복한다.)

    정리하기 위하여 x=3, y=6, z=28이라고 가정하고 예시를 들어본다. x=2의 1승+2의 0승, y=2의 2승+2의 1승, z=2의 4승+2의 3승+2의 2승이다. 이때, x의 원소를 {2의 1승, 2의0승},y의 원소를 {2의 2승, 2의 1승}, z의 원소를 {2의 4승, 2의 3승, 2의 2승}이다.

    이때, 1단계를 적용하여, x와 y에서 겹치는 2의 1승을 두 집합에서 모두 소거한다. 더 이상 겹치는 원소가 없기 때문에 2단계로 넘어간다. 2단계에서는 x와 z가 겹치는 원소가 없기 때문에 생략한다. 3단계에서는 y와 z에서 겹치는 2의 2승을 소거한다. 지금까지의 상황으로 정리하면, x의 원소는 {2의 0승}, y의 원소는 모두 소거되었고, z의 원소는 {2의 4승, 2의 3승}이다.

    이 이후에 만약 남은 2의 N승 꼴이 2개 이상일 경우 다음의 부가적인 단계에 도입하여야 한다.

    4.가장 큰 2의 N승을 2의 L승이라고 할때 2의 L승을 2의 (L-1)승 +2의 (L-1)승으로 바꾸고 다시 위의 단계를 진행한다. (4단계는 2의 N승 꼴의 형태의 숫자가 하나뿐일 때까지 진행한다.

    다시 한번 아까의 상황으로 예를 들자면 2의 L승은 2의 4승이다. 그러니 2의 4승을 2의 3승+2의 3승으로 바꾸고 이를 다시 {2의 3승, 2의 3승}으로 만드는 것이다. 이러한 방식을 계속하다보면 z에만 2의 0승이 23개 주어지게 된다. 이것은 1,2,3,4,번 과정을 반복하고 남은 숫자가 23이라는 것이다. 그러면 마지막 부가적인 단계를 진행하게 된다. (남은 숫자를 F라고 가정한다.)

    5-1. 만약 z-F가 y 이상일 경우에는 그냥 z무더기에서 F개를 가져가면 된다.

    5-2. 만약 z-F가 y보다 작을 경우에는 y에서 y-z+f-1의 값만큼 가져가면 된다.

    5-3. y-z+F-1이 0인 경우 z에서 z-y-x의 값만큼 가져가면 된다.

    마지막으로 예시를 들자면 28-23이 6보다 작으므로 5-3에 해당한다. 그러므로 6-28+23-1의 값이 0이니 28-6-3-의 값인 19개를 z에서 가져오면 된다.

    좋아요0 댓글수1
    • 출제자(국) 2019.04.22 17:28:28

      kevin0610 친구의 풀이는 돌 무더기가 3개 있을때만 적용되는 풀이인가요?

      좋아요1
  • code 2019.05.08 17:05:39

    문제 3번:

    각 돌무더기마다 돌이 한개이고 돌무더기가 k+1개라면 당연히 먼저 패배한다.--ㄱ

    뿐만아니라 k+1의 배수더라도 선이 1개를 가져가면 후 k개, 2개면 k-1개 이런식으로 k+1의 배수로 선에게 넘기기 때문에 선이 패배한다. --ㄴ

    ㄱ의 상태를 상대방에게 주면 이기기 때문에 다음과 같은 경우는 선이 승리한다.

    '1이상의 수' 1개

    ----k개----  -1개-                 //k개의 돌무더기에서 맨 밑줄을 제외하면 승리한다.
    각 줄마다의 돌갯수를 a1 a2 a3 ........ an 이라고 하자

    1 3 2 1 일때 a1=4 a2=2 a3=1 이며 뒤의 값은 0이다.

    a2 =0 이라 가정하자.

    이때에는 ㄴ과 마찬가지로 먼저하는 사람에게 돌무더기가 k+1의 배수이면 패배,

    아니면 승리한다.

    이는 즉슨 a2 가 0이 되었을 때 그 차례의 사람에게 k+1의 배수개의 돌무더기인지가 중요함을 의미한다.

    (NIM-SUM은 필요없다.)

    a2 = k 가 되었을때 a1 의 값을 무시하더라도 a2 위를 몰수하고,

    a1을 k+1의 배수로 맞추면 되기에 이 상황에서는 선이 승리한다.

    이는 k보다 작은 값(단 1이상)에서도 성립하기때문에,

    상대방에게 a2=(k+1)b가 되도록 넘기면 승리한다(a3=0)

    a3 a4 a5 a6 ...... 도 동일하다.

    k+1의 배수가 아닌경우, 어떤 경우에도 k+1의 배수가 되도록 할수 있고

    k+1의 배수인 경우 어떻게해도 k+1의 배수가 되지 못하므로,

    a1 a2 a3 ........ an값이 전부 k+1의 배수라면 선이 패,

    그렇지 않으면 선이 이긴다.

    좋아요0 댓글수6
    • 출제자(국) 2019.05.09 22:55:59

      code님! 

      '1이상의 수' 1개
      ----k개----  -1개-                 //k개의 돌무더기에서 맨 밑줄을 제외하면 승리한다.

      가 어떤 상태인지 각 줄마다의 돌 갯수를 알려줄 수 있나요? '----k개----  -1개-'가 k개의 돌 1개 무더기들인지, 아니면 돌 k개의 무더기 하나랑 돌 1개의 무더기 하나인지 잘 모르겠어요.

      그리고 '1 3 2 1 일때 a1=4 a2=2 a3=1 이며 뒤의 값은 0이다' 도 설명해주시면 좋을 거 같아요. 1 3 2 1이라는 수열이 각 줄의 돌 갯수를 나타낸 것인가요?

      이외에도 궁금한 것이 많은데, 전반적으로 풀이를 더욱 명료하게 써주시면 이해하기가 더 쉬울 거 같아요!

      좋아요0
    • code 2019.05.09 23:03:25

      각 돌무더기마다의 돌갯수는 1이상의 수들(단 모든 돌무더기의 돌갯수가 1은 아님), 단 1줄만 1인경우이고요.

      두번째는 돌무더기의 돌들을 줄로 세웠을 때

      (예시: 돌무더기 갯수가 1, 2, 1 이라면 

          돌

      돌 돌 돌           다음과 같이 표시함)

      각 세로줄마다의 돌개수를 밑에서부터 a1값이라고 하는것입니다(예시에서는 a1=3, a2=1 이겠네요)

            

      좋아요0
    • 출제자(국) 2019.05.10 00:14:47

      k=1이고 각 줄마다의 돌 개수가 순서대로 1, 2, 3이면 a1=1, a2=2, a3=3이 되어 ai들 중 어떤 수(a1, a3)는 2의 배수가 아니지만, 문제 1번의 답에 따르면 이 상태는 선이 패해요. 이 경우는 풀이에서 어떻게 설명이 되나요?

      좋아요0
    • code 2019.05.10 17:28:22

      k=1인경우는 제외이고, 다음 경우에는 

      a1=3, a2=2, a3=1 입니다.

      1인경우를 제외하는 이유는 저 풀이는 NIM-SUM=0이더라도 다시 0으로 돌려보낼 수 있다는 가정하에 쓴 것으로

      돌무더기 2개부터는 가능하지만 1개인 경우는 불가능하기에 위 풀이에는 적용되지 않음이 당연합니다.

      좋아요0
    • 출제자(국) 2019.05.10 21:52:52

      설명 감사합니다! 위 예시에서 a1 a2 a3의 값을 제가 순서를 잘못해서 역순으로 적었네요;; blush 실수 미안해요 ㅎㅎ k=1일 때 풀이가 왜 적용이 안 되는지 설명해준것도 풀이의 의도를 이해하는 데 도움이 됐어요. 그러면 k=2일 땐 풀이가 적용이 되는거죠? k=2이고 돌 무더기 각각의 돌 개수가 순서대로 1개, 1개, 2개, 2개, 3개일 때 (이때 a1=5, a2=3, a3=1 맞나요?) 선이 패하는 것 같은데, 이 예시를 확인해줄 수 있어요?

      좋아요0
    • code 2019.05.10 22:26:45

      아... 제 풀이에 오점이 있네요. 제 전략대로라면 a1=3, a2=3, a3=0 이 되도록 만들어야 하는데 다음의 경우는 그러지 못하네요.

      좋아요1
  • code 2019.05.10 22:46:06

    ***증명이 아닌 추측***(나중에 증명을 더 자세히 하겠습니다.)

    이어서 조건을 더 붙이겠습니다.

    선이 승리하기위해서는 (k+1)의 배수가 아니여야하며 (k+1)의 배수로 만들 수 있어야 한다.

    출제자 분께서 드신 반례의 경우 원래 k+1의배수였다면 만들 수가 없습니다.

    따라서 나온 가설

    '초기 상태만 (k+1)의 배수로 만들 수 있으면 그 이후는 모두 (k+1)의배수로 만들 수 있다.'

     

    좋아요0 댓글수2
    • code 2019.05.11 16:57:57

      이 추측이 맞다면 다음과 같은 조건만 추가되면 됩니다

      am 을 k+1의 배수로 만들기위해 가져와야 할 돌갯수가 p, am-1 밑부터 k+1의 배수로 만들기위해 가져와야 할 돌갯수가 가장많은것을 q 

      am+1이상부터 k+1의 배수로 만들기위해 가져와야 할 돌갯수가 가장 많은것을 i, 전체 돌무더기 개수가 n이라면

      n-am-q+p>=0 ,k>=q+i-p 이면 선이 k+1의 배수로 만들수 있는 경우,

      그렇지 않으면 (a1 a2 a3....)이 k+1의배수가 아니더라도 선이 이길 수 없다.

      *설명

      돌무더기 하나씩을 기준으로 am칸에 돌이 존재할 수도, 안 할수도있다. 다시말해 m=2일때 돌무더기마다 2이상이면 존재, 2미만이면 비존재이다.

      만약에 존재하지않는다면 am+1칸부터는 당연히 존재하지않는다.

      문제로 돌아와서 p값이 0이라고 해보자.

      이때 q값이 1이라면 돌무더기중 am 칸에 돌이 존재하는 돌무더기중에 하나를 선택하여 가져와야한다.

      이제 선택할수 있는 돌무더기는 k-1이다.

      즉 am-1부터는 그 돌무더기에서 가져올 수가 없다(위 풀이에의하면 돌은 무조건 위의 것부터 가져와야하기 때문).

      그런데 am-1이하로 가져와야할 돌갯수가 k-1이 넘는다면,

      그것을 다 가져갈 수가 없다.

      n-am-q+p>=0 라는 식도 이와 유사한 방법으로 설명가능하다(만약에 증명이 필요하다면 서술하겠습니다.)

      좋아요0
    • 출제자(국) 2019.05.11 21:54:01

      code님. 먼저 문제에 열정적으로 참여해주셔서 정말 감사드립니다! 다만 code님이 현재 생각하시는 방향으로 시간을 너무 많이 쏟으시면 나중에 혹시라도 지치실까봐 조심스럽게 댓글을 달아요. 지금 생각하시는 방향도 문제를 접근하는 데 도움이 되지만, 어떤 전략이 통하지 않는 예외사항을 계속 전략에 추가시키는 방향으로 접근하면 계속해서 새로운 (더욱 복잡한) 예외 사항이 생길 수도 있어요. 다양한 시도를 해서 문제에 대한 이해를 키우는 것도 좋지만, 최종 전략을 세울 때는 문제 전체를 볼 수 있는 새로운 전략/풀이 방법을 생각하는 것도 좋을 것 같아요. 생각이 막히면 충분히 쉬어두는 것도 방법이구요! 문제에 열정을 가지신 만큼 꼭 해결하실 수 있길 바래요. 화이팅!!

      좋아요0
  • 출제자(국) 2019.05.11 21:59:03

    3번에 대한 힌트를 하나 드리자면, k=1일 때는 3번 문제가 1번 문제와 같아지기 때문에 일반적인 경우에도 3번 문제가 1번 문제의 자연스러운 확장으로 풀려요.

    좋아요0 댓글수0
  • code 2019.05.21 17:01:48

    문제 3번 풀이입니다.

    k개의 돌무더기를 선택하여 가져갈 수 있다고 했을 때,

    k+1진법을 이용하여 NIM-SUM값을 적용시키면 됩니다.

    예를 들어 문제 1번의 경우는 k=1이고 2진법을 이용하여 해결할 수 있었습니다.

    1번을 조금만 더 자세히 설명하도록 하겠습니다.

    모든 돌무더기에 돌이 하나 있다고 가졍합시다.

    이때 돌무더기 하나하나 마다 1이라는 숫자를 부여받습니다(NIM-SUM에 관여하는)

    돌무더기 갯수가 짝수이면 NIM-SUM=0, 홀수이면 1이기때문에

    홀수일 때 선이 승리합니다.

    k=2로 확장하보겠습니다.

    위와 똑같은 조건하에 선이 이기는 방법은 돌무더기를 k+1의 배수로 만드는 것입니다.

    즉 3의배수이면 후가 아니면 선이 승리합니다.

    3진법으로 바꿔 생각할시 3의 배수는 0, 그렇지않으면 1또는2 입니다.

     

    이제부터는 NIM-SUM값에 그대로 적용시키면 됩니다.

    NIM-SUM값이 0이 아닌경우, 선택가능 돌무더기가 k개이므로 어떤경우에도 0으로 만들수 있고 (k+1진법 기준)

    0인경우 어떻게 행동해도 0이 아닌 값이 됩니다.

    **  진법 계산  **

    각 자릿수 마다 따로 더해준다.

    단 k+1개가 넘으면 넘지않을때까지 k+1 배수를 빼준다.

    올림은 하지않는다.

     

     

    좋아요0 댓글수2
    • 출제자(국) 2019.05.22 10:35:21

      code님! k=2일 때 돌 무더기들이 순서대로 돌이 1개, 1개, 2개, 2개 씩 있으면 (k+1)진법 NIM-SUM은 0이지만, 돌이 두개인 무더기들에서 각각 1개, 2개의 돌을 빼 순서대로 돌이 1개, 1개, 1개, 0개 가 되게 할 수 있어요 (이때도 (k+1)진법 NIM-SUM은 0). 최종 풀이를 낼 때는 논리의 각 부분을 엄밀하게 증명하고 확인한 뒤에 세부적인 증명도 풀이에 명시적으로 써주는 걸 부탁드려요. 이렇게 하면 본인이 풀이를 더 잘 이해할 수 있어서 실수도 방지할 수 있고, 풀이를 읽는 사람도 계속 반례를 생각하거나 논리의 허점을 설득할 필요가 없이 더욱 납득하면서 풀이를 읽을 수 있어요. 아이디어가 발전되는 게 풀이에 점점 가까워지는 것 같으니까 조금만 더 힘내면 풀 수 있을 것 같아요! ㅎㅎ 다만 최종 답안을 올릴 때는 반례는 없는지, 설명을 명확하게 했는지 한번만 더 확인해주길 부탁해요!

      좋아요0
    • 출제자(국) 2019.05.22 13:49:02

      됴쑨 님처럼 예시를 들어가면서 설명해주시면 아이디어 이해에 도움이 많이 되구요, 수학자 님처럼 논리의 흐름을 구체적으로 연결되게 써주시면 논리에 틈이 없다는 게 설득이 더 잘 돼요. 풀이를 쓰실 때 참고하시면 도움이 될 거 같아요! 이를테면 'NIM-SUM이 0이 아닌 경우 0으로 만들 수 있다', 'NIM-SUM이 0인 경우 어떻게 해도 0이 아닌 값이 된다' 같은 부분들이 있으면 각각 따로 항목을 만들어서 엄밀하게 증명할 수 있겠죠?

      좋아요0
  • 수학자 2019.07.18 23:45:52

    3번 풀이입니다. 푼 건 좀 오래 전에 풀긴 했는데, 그래도 나름 관심 가지고 문제 푸는 사람들이 있을까 싶어서 조금 기다렸습니다.

    NIM 게임 재밌지 않나요?(저만 그런가요...ㅠㅠ)

     

    다음 [조건]을 만족하는 상태만이 서은이가 지는 상태이다.

    [조건] 각 무더기의 돌의 수를 2진법으로 나타낸 뒤 자릿수별로 1의 개수를 셌을 때, 모두 k+1의 배수이다.

    예를 들면, 무더기가 {3, 3, 4, 5, 6}, k=2인 경우, 2진법 표현이 {011, 011, 100, 101, 110}이므로 자릿수별로 1의 개수는 4의 자리는 3개, 2의 자리는 3개, 1의 자리는 3개이므로 [조건]을 만족합니다.

    오리지널 NIM 게임에서와 비교하자면, XOR은 1의 개수가 2의 배수인가 아닌가를 다루는 것이라 생각할 수 있습니다. 이 2가 k+1로 확장된 것이라 할 수 있죠.

     

    증명: 다음 세 가지가 참임을 보이면 된다.

    Claim 1. 더 이상 시행을 할 수 없는 상태는 돌이 없는 상태이고, 이 때 [조건]을 만족한다.

    Claim 2. [조건]을 만족하는 상태에서 한 번 시행을 하면 절대 [조건]을 만족할 수 없다.

    Claim 3. [조건]을 만족하지 않는 상태에서는 언제나 [조건]을 만족하는 상태로 갈 수 있다.

     

    Claim 1의 증명: 돌이 없는 상태(모든 무더기의 돌의 수가 0인 상태)는 각 자릿수별로 1의 개수가 0개이므로 [조건]을 만족한다.

     

    Claim 2의 증명: 돌을 가져갔을 때, 그 무더기의 돌의 수의 2진법 표현이 바뀌는 가장 높은 자리를 생각한다. 그 자리는 무조건 값이 1에서 0으로 바뀌었어야 한다. 그러면 최대 k개의 무더기 각각에 대해 가장 높은 자리들이 나오는데, 이들 중 가장 높은 자리를 따지면, 그 자리는 최소 1개, 최대 k개가 1에서 0으로 바뀌었다. 그러므로 그 자릿수의 1의 개수를 k+1로 나눈 나머지는 0이 될 수 없다.

     

    Claim 3의 증명: 가져가는 돌 무더기를 다음과 같이 정하면 된다.

    가져가는 돌 무더기의 집합을 A라 한다. 처음에 A=\varnothing이다.

    1) 자릿수별 1의 개수가 k+1의 배수가 아닌 가장 높은 자리를 찾는다. 그 자리의 1의 개수를 k+1로 나눈 나머지를 r이라 하자. 그러면 그 자리가 1인 무더기 중 r개를 골라서, 1을 0으로 바꾸고 A에 추가한다.

    2) 자리를 하나씩 낮은 자리로 내려가며, 조건을 만족시키도록 자릿수를 바꾼다. 이미 k+1의 배수인 경우 넘어간다. 그렇지 않은 경우 다음과 같이 한다. 현재 A의 원소의 개수를 a라 하고, 그 중에서 바꾸려는 자리가 0, 1인 것의 개수를 각각 x,y라 한다. 그리고 바꾸려는 자리의 1의 개수를 k+1로 나눈 나머지를 r이라 한다.

    (i) k-x = y+(k-a) \ge r인 경우, 1 r개를 0으로 바꾼다. y \ge r인 경우 A에 있는 1인 것 y개 중 r개를 0으로 바꾸면 된다. 그렇지 않은 경우 A에 있는 1인 것 y개를 모두 0으로 바꾸고, 나머지 중에서 1인 것 r-y개를 A에 추가하면서 0으로 바꾸면 된다. 1이 최소 r개 있기 때문에 이것은 가능하며, 또한 바뀐 A의 원소의 개수는a+(r-y)\le k이 된다.

    (ii) k-x < r인 경우, k+1-x \le r에서 k+1-r \le x이다. 그러므로 A에 있는 0인 것 x개 중 k+1-r개를 1로 바꾸면 된다.

    이렇게 하면, 최종적으로 A의 원소의 수는 k 이하이며, 바뀌는 값들은 처음에 A에 추가될 때 그 자리가 1에서 0으로 바뀌고, 이후 바뀌는 건 그보다 낮은 자리를 바꾸므로 수가 감소한다. 그러므로 이것이 valid한 시행이며, 이렇게 시행했을 때 모든 조건을 만족한다.

     

    예시) k=3, 무더기의 돌 수가 [2 4 5 5 7]인 경우

    \begin{matrix} 010\\ 100\\ 101\\ 101\\ 111 \end{matrix}

    4의 자리는 4개이므로 4의 배수. 2의 자리가 2개이므로 010, 111을 A에 추가하고 1을 0으로 바꾼다. 1의 자리는 3개인데, (ii)의 케이스에 해당하므로 010의 0을 1로 바꾼다. 최종 결과

    \begin{matrix} 001\\ 100\\ 101\\ 101\\ 101 \end{matrix}​​​​​​​

    좋아요0 댓글수0