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

Problems

폴리매스 문제 보기

문제

[국가수리과학연구소] 국28. 은 동전을 사수하라!

2019.03.29

같이 풀어볼까?

네이버밴드 구글플러스

 

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

 

 

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

 

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

 

 

[문제]

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

 

댓글 25

  • Simon 2019.04.01 16:26:13 비밀댓글
    비밀댓글 입니다.
    댓글수2
    • 아인수타인 2019.04.02 20:36:37

      Simon님 설마 벌써 푼 건가요?

      좋아요1
    • sincostan 2019.04.02 23:08:09

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

      좋아요0
  • muse 2019.04.01 17:27:00

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

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

    좋아요0 댓글수2
    • 수학장 2019.04.01 18:03:19

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

      좋아요1
    • muse 2019.04.01 19:58:41

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

      좋아요0
  • c언어 2019.04.02 01:39:26

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

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

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

    좋아요0 댓글수0
  • sincostan 2019.04.02 23:10:42

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

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

    좋아요0 댓글수1
    • 김우현 기자 2019.04.03 09:28:28

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

      좋아요1
  • 김우현 기자 2019.04.03 11:33:51

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

    좋아요0 댓글수0
  • 오지원 2019.04.09 18:47:29

    음... 어렵네요오

    좋아요0 댓글수1
    • 오지원 2019.04.09 18:54:23

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

      좋아요0
  • 우리집고양이 2019.04.11 20:11:55

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

    좋아요0 댓글수4
    • code 2019.04.11 22:50:48

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

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

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

      좋아요0
    • 우리집고양이 2019.04.12 17:56:00

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

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

      좋아요0
    • 출제자(국) 2019.05.04 15:00:36

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

      ㅁCSㅁㅁC

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

      좋아요0
    • 우리집고양이 2019.05.06 10:57:16

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

      좋아요0
  • code 2019.05.03 10:07:06

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

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

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

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

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

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

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

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

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

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

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

    좋아요0 댓글수1
    • 출제자(국) 2019.05.04 15:03:52

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

      좋아요0
  • 동덕 2019.05.03 11:24:48

    좋아요0 댓글수0
  • 동덕 2019.05.03 11:26:30

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

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

    좋아요1 댓글수1
    • 아인수타인 2019.05.04 00:50:40

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

      좋아요0
  • Fermat314 2019.05.04 15:48:29

    글을 쓰기에 앞서 현재 문제를 간단하게 수로 표현하겠습니다. 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
  • 이방인 2019.05.07 01:59:36

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

    처음 하는 사람의 필승 전략

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

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

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

     

    동전 배치 조건은

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

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

     

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

     

     

     

    좋아요2 댓글수1
    • Undefined 2019.05.31 19:15:28

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

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

      좋아요1