본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[폴리매스 문제] 국28. 은 동전을 사수하라!
수학동아 2019.03.29

 

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

 

 

위 그림처럼 모눈종이 한 줄 위에 1개 이상의 동전이 있다. 동전들 중 1개만 은으로 만든 동전이고 나머지는 동으로 만들었다.  두 사람이 번갈아가며 아래 규칙 중 하나의 동작을 한다.

 

①맨 왼쪽 동전을 가져간다. ②한 동전을 다른 동전을 넘지 않고 왼쪽으로 원하는 칸만큼 옮길 수 있다. 이때 반드시 한 칸 이상 옮겨야 한다.

 

 

[문제]

은으로 만든 동전을 가져간 사람이 게임에서 이길 때 처음 하는 사람이 이길 수 있는 동전 배치 조건은 무엇일까? 단, 두 사람이 최선을 다해 플레이 한다. 

 

  •  
    Simon Lv.2 2019.04.01 비밀댓글
    비밀 댓글이 등록 되었습니다.
    댓글 작성하기 댓글수2
    •  
      아인수타인 Lv.6 2019.04.02

      Simon님 설마 벌써 푼 건가요?

      좋아요1
    •  
      sincostan Lv.5 2019.04.02

      이렇게 빨리 풀리 없을 것 같은데...

      좋아요0
  •  
    muse Lv.1 2019.04.01

    이 문제에서는 "끝나지 않는 배치"가 있을 것 같습니다.

    단순히 동 동전 하나가 왼쪽에 있고 은 동전이 오른쪽에 있다면, 게임은 절대로 끝나지 않겠죠.

    댓글 작성하기 좋아요0 댓글수2
    •  
      수학장 Lv.3 2019.04.01

      모눈종이는 왼쪽으로는 길이가 무한하지 않습니다. 따라서 항상 끝이 납니다. 오른쪽으로의 길이는 유한하든 무한하든 따질 가치가 없고요.

      좋아요1
    •  
      muse Lv.1 2019.04.01

      그렇네요. 그럼 항상 끝이 나겠군요.

      좋아요0
  •  
    c언어 Lv.2 2019.04.02

    시간이 많이 없어서 제대로 증명하거나 하지는 않았지만 다른사람에게 힌트가 되기를 빌며 적어보도록 하겠습니다.                                                                 

    먼저 이게임과 님게임이 비슷하다고 생각해 보았습니다. 님게임의 경우 게임을 설계하기 위해서 한 턴동안 남이 가져간 돌과 내가 가져간 돌의 수의합이 일정하도록 게임을 진행합니다. 이 문제에서도 게임을 설계하기 위한  '키'를 설정해야  한다고 생각했습니다. 그리고 전 그 키로 움직이는 돌의 칸 수의 합이 짝수나 홀수가 되어야  한다고 생각했습니다( 이부분은 게산해보면서 홀순지 짝순지 알아보아야 겠지만 짝수로 예상) 그리고, 님게임에서 돌의 갯수는 여기서 돌이 움직일 수 있는 최대 갯수로 보았습니다. 맨 왼쪽에서 돌n 개가 각각 a_1 . . . a_n의 위치해 있다고 한다면 모두 한칸씩 움직이고 더이상 움직일 수 없을때 제거되는 횟수까지 친다면 총 a_1 + ... + a_n가 되겠죠. 여기서 돌이 n 칸 움직인다면  a_1 + ... + a_n개의 돌에서 n 개의 돌을 가져간다고 비유한다고 할수 있겠습니다. 돌이 제거되는 경우는 제거되는 위치를 고려해서 몇번 움직일수 있었는지 본다면 이 경우도 몇개의 돌을 가져갔다고 비유할 수도 있을 겁니다. 이렇게 님게임과 비교를 해보며, 이 문제는  돌의 움직임에도 제한이 있으니 이도 생각하면서 풀면 될것 같습니다.                                               

    막 쓴글이라 오타, 잘못 생각한 부분이  있을 수도 있으니 내 생각과 뭔가 다른것 같다? 하면 바로 질문해 주시면 감사할 것 같습니다.

    댓글 작성하기 좋아요0 댓글수0
  •  
    sincostan Lv.5 2019.04.02

    조건 2에서 한 동전이 다른 동전을 넘지 않고 라는

    이야기가 서로 겹쳐지면 안 되는 거죠?

    댓글 작성하기 좋아요0 댓글수1
    •  
      김우현 기자 Lv.4 2019.04.03

      네! 최대로 움직여봤자 왼쪽에 보이는 동전 바로 오른쪽 칸까지만 움직일 수 있습니다.smiley

      좋아요1
  •  
    김우현 기자 Lv.4 2019.04.03

    ★백진언 연구원이 개인 사정 때문에 이번 달 말에 피드백을 줄 수 있다고 합니다. 연구원이 올 때까지 친구들끼리 열심히 상의해보자고요!smiley

    댓글 작성하기 좋아요0 댓글수0
  •  
    오지원 Lv.1 2019.04.09

    음... 어렵네요오

    댓글 작성하기 좋아요0 댓글수1
    •  
      오지원 Lv.1 2019.04.09

      제가 아는 남자애는 잘하던데 열심히 풀어야겠네요~

      좋아요0
  •  
    우리집고양이 Lv.1 2019.04.11

    어차피 동전을 미는 건 턴을 돌리는 거죠, 동전1 빈 칸 동전2가 있고 내 턴일 때 동전 2를 잡아야 한다면 빈 칸을 끝까지 밀고 잡아서는 안 된다면 동전 1을 가져갈 것이므로 빈 칸은 몇칸이든 의미가 없습니다. 따라서 빈칸을 한칸으로 통일하고, 동전을 A, 빈 칸을 B라고 한 뒤 은화 앞으로 적당한 A와 B의 나열이 있는 것을 생각합시다. A는 무조건 시행되는 턴이고, B는 B 왼쪽의 A를 잡은 플레이어가 선택할 수 있네요. 은화로부터 시작해서 오른쪽에서 왼쪽으로 턴 순서를 부여할게요.  은화가 0번이니까 최선의 플레이에서 짝수 번째 턴에서 시작하는 사람이 승리합니다. 따라서 시행 여부가 마음대로인 B는 그 앞의 A가 짝수 번째 턴을 부여받게 합니다. 즉 B 오른쪽의 A의 턴 순서가 짝수라면 B는 사용되고(B도 턴 순서를 부여받고) 홀수라면 턴 순서를 부여받지 않습니다. 동전이 배열되어 있을 때 중간에 동전이 없는 모든 빈칸을 B로 치환하고 상기한 한가지의 규칙만 지켜서 은동전으로부터 턴 순서를 부여했을 때, 짝수 동전(혹은 빈칸)에서 시작하는 사람이 승리합니다.

    댓글 작성하기 좋아요0 댓글수4
    •  
      code Lv.1 2019.04.11

      '따라서 빈칸을 한칸으로 통일하고' 라는 가정이 조금 이상한 면이 있는 것 같아 말씀드립니다.

      빈칸이 두칸이라고 하면 그 빈칸을 아예 없애 버리는 것이 아닌 한칸만 움직이는 것도 가능합니다(문제상황이 그러합니다.).

      즉 저렇게 가정한다면 아예 다른 문제가 되어 버리죠.

      좋아요0
    •  
      우리집고양이 Lv.1 2019.04.12

      ' 내 턴일 때 동전 2를 잡아야 한다면 빈 칸을 끝까지 밀고 잡아서는 안 된다면 동전 1을 가져갈 것이므로 빈 칸은 몇칸이든 의미가 없습니다. '

      라고 써두었는데 부족함이 있었던 것 같네요. 빈 칸은 홀짝을 결정하는 기회이므로 몇 칸이 있든 전부 밀어버리거나 동전을 가져와서 자신에게 유리한 쪽으로 결정해야지 그 기회를 상대에게 넘겨주어서는 안됩니다. 빈 칸이 두칸 이상 있을 때 한 칸만 움직이는 것은 최선의 선택이 아닙니다.

      좋아요0
    •  
      출제자(국) Lv.1 2019.05.04

      '우리집고양이'님! 'C'를 그냥 동전, 'S'를 은 동전, 'ㅁ'를 빈칸이라고 할 때 아래 상황에서 첫 플레이어의 필승전략은 맨 오른쪽 동전을 한 칸만 미는 거에요:

      ㅁCSㅁㅁC

      빈 칸이 두 칸 이상 있을 때 한칸만 움직이는 것도 최선의 선택이 될 수 있습니다

      좋아요0
    •  
      우리집고양이 Lv.1 2019.05.06

      문제를 잘못 이해했네요. 감사합니다.

      좋아요0
  •  
    code Lv.1 2019.05.03

    님게임과 유사한것같네요.

    기본적으로 2번시행없이 1번시행으로만 진행한다면

    은동전 앞의 동전의 갯수를 p라고 했을때

    p가 홀수일때에는 나중에하는 사람이,

    짝수일때에는 먼저하는 사람이 이깁니다.

    2번시행을 포함해보도록 하겠습니다.

    님게임에 비유해, 앞으로 땡길 수 있는 칸 수를 돌의 갯수, 동전의 갯수를 돌무더기의 갯수로 봅니다.

    님게임의 경우, 이때 NIM-SUM값이 0이면 나중에하는 사람이, 0이아니면 처음에하는 사람이 이깁니다(타 문제에서 증명되었으므로 생략).

    님게임을 이긴다는것은 돌을 전부가져가는것으로 이 게임에서는 더 이상 2번시행을 할 수 없는것과 동일합니다.

    즉 NIM-SUM값이 0이면 처음한사람에게 돌아가고, 0이아니면 나중에한사람에게 선이 주어집니다.

    종합하면, p값이 짝수이고 NIM-SUM이 0이거나 p값이 홀수이고 NIM-SUM이 0이 아니면 먼저하는 사람이 이깁니다.

    댓글 작성하기 좋아요0 댓글수1
    •  
      출제자(국) Lv.1 2019.05.04

      code님! 중간의 동전을 앞으로 당겨오면 바로 오른쪽에 있는 동전이 당겨질 수 있는 칸 수가 늘어나서, 상황이 NIM과 달라지게 됩니다. 이를테면 'CㅁSㅁCㅁC'의 배치는 나중에 하는 사람이 이겨요

      좋아요0
  •  
    동덕 Lv.1 2019.05.03

    댓글 작성하기 좋아요0 댓글수0
  •  
    동덕 Lv.1 2019.05.03

    위의 것처럼 하면 맨 처음하는 사람이  동으로 만든 동전을 가져갈 것이고 그러면 두번째로 하는 사람은 선택의 여지가 없으므로 남은 은 동전을 왼쪽으로 한 칸 움직이고 그 다음 가져가면 됩니다.

    물론 조건을 구하는 것이기에 별 다른건 도움이 안되지만, 그래도 아이디어를 도출하는데는 도움이 될 듯 합니다.

    댓글 작성하기 좋아요1 댓글수1
    •  
      아인수타인 Lv.6 2019.05.04

      '맨 왼쪽 칸'에 있는 걸 가져오는 게 아니라 그 동전들 중 맨 왼쪽에 있는 동전을 가져오는 것입니다. 그래서 위 경우는 두 번째 한 사람이 이깁니다.

      좋아요0
  •  
    Fermat314 Lv.2 2019.05.04

    글을 쓰기에 앞서 현재 문제를 간단하게 수로 표현하겠습니다. 0은 빈칸, 1은 동 동전, 2는 은 동전입니다. 예를 들어 0101102101 등의 형식으로 모든 배치를 표현할 수 있습니다. 물론 여기서 2는 반드시 한 번 있어야 하고, 맨 뒷자리는 1 또는 2입니다.(0은 의미가 없기 때문)

     

     

    현재까지 나온 아이디어를 보면 NIM 게임으로 보고 풀자는 아이디어가 있었는데요, 이것도 하나의 방법이 될 수는 있지만 제 개인적인 생각으로는 좀 복잡해질 것 같습니다.

     

    C언어 님이 제안하신 방법에서의 허점은 A1+A2+•••+An이 같더라도 결과는 다르게 나올 수 있다는 것이고(예를 들어 1002와 012는 값이 5로 같지만 012는 나중에 한 사람이, 1002는 먼저 한 사람이 이깁니다.), code님이 제안하신 방법에서의 허점은 p뿐만 아니라 2 뒤에 있는 배치도 결과에 영향을 준다는 점입니다. 각각 보완할 수는 있긴 한데, 제 생각에는 현재 문제를 NIM게임으로 변환시키면 다음과 같아질 것 같습니다.

     

    (NIM 게임 변환 시 - 모든 동전을 돌 무더기로 표현하되, 은 동전으로 표현되는 돌 무더기에 집중해야 합니다. 각각의 동전을 옮길 수 있는 칸의 수가 각 돌 무더기에 있는 돌의 개수가 되고, 이에 따라 임의의 돌 무더기에 있는 돌의 개수가 k개 줄어들면 그 무더기의 오른쪽에 있는 돌 무더기의 돌 개수는 k개 늘어납니다. 그리고 돌 무더기의 돌 개수가 0개가 되더라도 돌 무더기는 없어지지 않습니다. 맨 왼쪽의 돌 무더기를 없애는 시행을 할 수 있고, 은 동전이 있는 돌 무더기가 맨 왼쪽에 오도록 하는 사람이 패배합니다.)

     

    보시면 알겠지만 현재 게임 방법과 큰 차이가 없기 때문에, NIM게임으로 접근해도 풀이에 별로 도움이 되지 않을 수 있습니다.

     

     

    저는 위에서 말씀드린 대로 숫자로 표현한 뒤 생각해 보았는데요, 은 동전 앞의 돌의 개수와 은 동전 뒤의 돌의 개수를 기준으로 돌 사이에 빈칸을 넣어보고 있습니다. 아래는 1이 2개일 때까지 제가 알아본 결과입니다. '선'이 먼저 하는 사람이 승리, '후'가 나중에 하는 사람이 승리하는 배치입니다.

     

     

    [1이 0개]

    2 선 / 02 선 / 002 선 •••

     

    [1이 1개]

    (1) 12의 형식

    12 후 / 102 선 / 1002 선 •••

    012 후 / 0102 선 / 01002 선 •••

    0012 후 / 00102 선 / 001002 선 •••

    ••• 후 / ••• 선 / ••• 선 / •••

    (2) 21의 형식

    항상 '선'이 승리

     

    [1이 2개]

    (1) 112의 형식

    112 선 / 1102 후 / 11002 선 / 110002 선 •••

    1012 선 / 10102 후 / 101002 선 / 1010002 선 •••

    10012 선 / 100102 후 / 1001002 선 / 10010002 선 •••

    ••• 선 / ••• 후 / ••• 선 / ••• 선 / •••

    0112 선 / 01102 선 / 011002 후 / 0110002 선 / 01100002 선 •••

    01012 선 / 010102 선 / 0101002 후 / 01010002 선 / 010100002 선 •••

    010012 선 / 0100102 선 / 01001002 후 / 010010002 선 / 0100100002 선 •••

    ••• 선 / ••• 선 / ••• 후 / ••• 선 / ••• 선 / •••

    a1b1c2(a, b, c는 빈칸)로 표현될 때 c=a+1인 경우에만 '후' 승리

    (2) 121의 형식

    121 후 / 1201 선 / 12001 선 / •••

    1021 후 / 10201 선 / 102001 선 / •••

    10021 후 / 100201 선 / 1002001 선 / •••

    ••• 후 / ••• 선 / ••• 선 / •••

    0121 선 / 01201 후 / 012001 선 / 0120001 선 / •••

    01021 선 / 010201 후 / 0102001 선 / 01020001 선 / •••

    010021 선 / 0100201 후 / 01002001 선 / 010020001 선 / •••

    ••• 선 / ••• 후 / ••• 선 / ••• 선 / •••

    00121 선 / 001201 선 / 0012001 후 / 00120001 선 / 001200001 선 / •••

    001021 선 / 0010201 선 / 00102001 후 / 001020001 선 / 0010200001 선 / •••

    0010021 선 / 00100201 선 / 001002001 후 / 0010020001 선 / 00100200001 선 / •••

    ••• 선 / ••• 선 / ••• 후 / ••• 선 / ••• 선 / •••

    a1b2c1로 표현될 때 a=c인 경우에만 '후' 승리

    (3) 211의 형식

    항상 '선'이 승리

     

     

     

    위의 결과에서 보듯, 가로줄로 표현되는 배치에서는 후가 딱 한 번 승리하고 그 이후부터는 선이 승리하며, '00100201(선), 001002001(후), 0010020001(선)'의 경우처럼 빈칸의 유무뿐만 아니라 빈칸의 개수도 결과에 영향을 미칩니다.

    1의 개수를 늘려가며 규칙을 찾아야겠는데, 이대로만 된다면 문제 해결은 시간 문제겠네요.

     

    아 그리고 칸의 총 개수를 기준으로도 해봤는데, 이건 일반화가 어려워서 동전의 개수로 하는 게 좀 더 편한 것 같습니다.

    댓글 작성하기 좋아요0 댓글수0
  •  
    이방인 Lv.1 2019.05.07

    배스킨라빈스 31 게임의 필승 전략처럼 상대의 동작에 따라 수칙을 세우면 될 것 같아요.

    처음 하는 사람의 필승 전략

    가장 첫번째 동작으로 맨 왼쪽 동전을 가져간다. 다음부터는 상대의 동작에 따라 대응을 달리한다.

    1. 상대가 동전을 가져가면 자신도 동전을 가져간다.

    2. 상대가 n번째 동전을 왼쪽으로 옮긴다면, 자신은 n+1번째 동전을 n번째 동전의 바로 오른쪽으로 옮긴다.

     

    동전 배치 조건은

    1. 은으로 만든 동전은 홀수 번째에 위치한다.

    2. 2k번째 동전과 2k+1번째 동전은 항상 이웃한다.(k는 자연수) 예로 2, 3번째 동전은 항상 이웃하며 16,17번째 동전도 항상 이웃한다.

     

    배치와 전략이 다음과 같을 경우 처음 하는 사람은 이기게 됩니다. 왜냐하면, 이 배치에서는 상대방은 항상 짝수 번째 동전만을 조작하고 자신은 항상 홀수 번째 동전만을 조작하기 때문입니다.

     

     

     

    댓글 작성하기 좋아요2 댓글수1
    •  
      Undefined Lv.1 2019.05.31

      동전이 홀수개라는 조건이 추가되어야 합니다.

      마지막 동전을 움직일 여부를 고려해야 하기 때문입니다.

      좋아요1
  •  
    으아아아 Lv.2 2019.10.01

    은 동전을 맨 왼쪽에 둔다!<퍽

    댓글 작성하기 좋아요0 댓글수0
  •  
    은총알 Lv.6 2019.10.10
    확인요청중

    맨 왼쪽부터 동,동,은 동전을 놓으면 될 것 같습니다! 그러면 맨 처음에는 가장 왼쪽에 있는 동 동전을 가져가고, 나중에 하는 사람은 남아있는 동 동전을 가져가거나 동 동전을 왼쪽으로 한 칸 옮길 수밖에 없습니다! 남아있는 동 동전을 가져가는 경우에는 바로 은 동전을 가져가면 되고, 동 동전을 왼쪽으로 한 칸 옮기는 경우에는 은 동전을 왼쪽으로 한 칸 옮깁니다. 그러면 다음 차례에 상대방이 동 동전을 가져갈 수밖에 없기 때문에 그 다음에 제가 은 동전을 가져가면 됩니다!

    댓글 작성하기 좋아요0 댓글수1
    •  
      은총알 Lv.6 2019.10.10

      아 지금 보니 배치의 조건이군요 확인요청중이라 수정 삭제를 못하네요 죄송합니다. 한번 아이디어 올려봤어요

      좋아요0
  •  
    무한대의끝을본남자 Lv.5 2019.10.20
    확인요청중

    처음하는사람을 A라가정하자, 나중하는사람을 B라고 가정하자

    은으로 된 동전과의거리에 관련이있다 1번째 동전부터 n번째 은전까지의거리는 0,a이므로,

    거리는 n이다   1번동작은 홀짝성의의해 A는 홀수번째 동전을 가질수있다

    그리고 2번째 사람이 옮길때도 생각해야한다. 옮긴다는것은 빈칸이있을때, 턴을 포기한다는 뜻으로 해석이가능하다

    턴을포기하면 홀짝성의의해 짝, 홀이 바꿔진다

    턴을포기한다는것은 수학적으로 턴-1이기때문에 홀-1 = 짝  짝-1 = 홀이되므로 바뀌어지는것이다

    따라서 2번동작은 '패스' 1번은 '추출'로 해석할수있다

    빈공간이없을때, 턴포기는 이용할수없다

    그러나 한사람이 추출을하면, 왼쪽빈공간이 생기므로 턴포기할수있다

    1번주자가 추출만을할수있다. 홀짝, 2번주자의선택권은 추출과 포기 이다 추출할때는 홀짝

    포기할때는 짝홀 동전을 홀수에있을때, 이도 홀짝성의의해 홀짝, 짝홀이 바뀌려면, n/2가 짝수가되지않는다. n/2는 홀짝이아니므로A가승리하게된다

    댓글 작성하기 좋아요0 댓글수0