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

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

댓글 43

  • 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

    좋아요1 댓글수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 댓글수2
    • algebra 2019.01.11 00:52:39

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

      좋아요0
    • code 2019.01.26 23:02:18

      어떻게 이겨야 할지 설명만 있고 증명이 없네요.

      확실한 증명을 해주셔야 그 의견이 해답인지 아닌지를 사람들과 함께 소통할수 있습니다.

      좋아요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개 있을때만 적용되는 풀이인가요?

      좋아요0