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

Problems

폴리매스 문제 보기

문제

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

2019.03.29

같이 풀어볼까?

네이버밴드 구글플러스

 

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

 

 

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

 

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

 

 

[문제]

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

 

댓글 15

  • 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

      좋아요0
  • 김우현 기자 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 댓글수2
    • code 2019.04.11 22:50:48

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

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

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

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

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

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

      좋아요0