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

Problems

폴리매스 문제 보기

문제

[국가수리과학연구소] 국9.5. 제설기의 마법 (9월 추가문제)

2017.09.15

같이 풀어볼까?

네이버밴드 구글플러스

★9월 문제가 일찍 풀려 새 문제를 만들었습니다. 이 추가 문제는 조금 깁니다.★

 

<9월 추가 문제>

어떤 마을에는 그림처럼 일렬로 집들이 나열되어 있다. 집이 충분히 많아서, 집들이 마치 수직선에서 정수가 위치한 지점들처럼 양쪽 끝으로 충분히 길게 나열되어 있다고 가정해도 된다.


어느 날 밤, 이 마을에 갑자기 눈이 산더미처럼 내렸다. 내린 눈의 양은 유한하다.

아침에 일어나 하염없이 쌓인 눈을 본 주민들은 많이 당황했다. 다행히도, 각 집에는 제설기가 하나씩 구비되어 있다. 주민들은 각자 가지고 있는 제설기를 꺼내 자기 집에 쌓여있는 눈을 치우기로 마음먹었다. 제설기는 다음과 같이 작동한다.
 

    1. 제설기 탱크에 눈 x리터를 넣는다. 숫자 x는 각 집에 있는 제설기마다 할당된 값으로, 각 집마다 다를 수 있다.
    2. 분사 버튼을 누르면 집에 있는 눈 x리터가 주변 집들로 분사된다 (!)
    3. 분사하는 도중에는 제설기를 건드릴 수 없다. 이를테면 제설기 탱크에 눈을 추가로 넣거나, 아니면 눈을 분사하는 과정을 취소할 수 없다.
    4. 분사가 다 끝나면 탱크 통이 비게 되고, 그러면 다시 탱크에 눈을 넣어 분사 작업을 할 수 있다.


 다음과 같은 조건이 있다.
 

    5. 분사기가 각 위치마다 분사하는 눈의 양은 일정하다. 이를테면, 가운데 있는 집의 제설기가 총 3L의 눈을 1L는 왼쪽으로 두 칸, 1L는 왼쪽으로 한 칸, 1L는 오른쪽으로 한 칸씩 보낸다고 하자.
  그러면 이 제설기는 매번 돌아갈 때마다 무조건 똑같은 양의 눈 3L를 1L를 왼쪽으로 두 칸, 1L를 왼쪽으로 한 칸, 1L를 오른쪽으로 한 칸씩 보낸다.

    6. 분사기를 쓸 때마다 바뀔 수 있는 것은, 분사기가 탱크를 얼마나 빨리 비우냐는 것이다. 이를테면 첫 번째 분사에서는 총 3L의 눈을 분사하는 데 1분이 걸렸다 해도, 두 번째 분사에서는 3분이 걸릴 수 있다.
마찬가지로, 분사기가 눈을 각 위치마다 뿌리는 속도도 다를 수 있고, 시간에 따라 변할 수 있다. 예를 들어, 첫 번째로 분사했을 때는 왼쪽으로 눈을 빠르게 분사하지만, 오른쪽으로는 눈을 천천히 분사할 수 있다. 하지만 두 번째로 분사했을 때는 속도가 바뀌어서 왼쪽으로는 눈을 천천히 분사하지만, 오른쪽으로는 눈을 빠르게 분사할 수도 있다.

    7. 마지막으로, 각 집에 있는 분사기는 무조건 양쪽 방향으로 눈을 뿌린다. 다시 말하면, 한쪽 방향으로만 눈을 뿌리는 분사기는 없다.


눈이 너무 많이 쌓여 있어서, 아무리 분사기를 돌려도 서로에게 눈을 넘겨버리는 꼴이 되어버린 상황! 마을 주민들은 분사기를 계속 써야 할지, 아니면 외부 업체에 신고를 해서 며칠을 기다리더라도 제설 작업을 맡겨야 할 지에 대해 열띤 토론을 펼쳤다.

그런데 어떤 물리학자가 갑자기 강단 앞에 서더니 다음과 같이 말을 하기 시작했다.

 

괜찮습니다, 여러분! 여러분들이 가진 제설기로 제설을 할 수 없을 때까지 작업을 하시다 보면, 언젠가 쌓인 눈더미가 양쪽으로 충분히 얕게 퍼지게 될 것입니다. 각자 제설기를 쓸 수 없을 때까지 최대한 그 자리에서 제설을 하셨을 때, 최종적으로 남을 눈의 양이 얼마나 될지를 제가 알려드리겠습니다. 


그러고는 이 물리학자는 각 집마다 최종적으로 남게 될 눈의 양을 계산해서 각 집마다 알려주었다. 수학을 공부하는 평범한 대학원생 B모군은 물리학자의 말을 듣고 무척 의아했다. 눈의 양이 많아서 아무리 제설기를 돌려도 눈더미가 평평하게 퍼질 거란 사실이 당연하지 않거니와, 눈을 치우는 방법의 수가 수도 없이 많을 텐데도 불구하고 물리학자는 제설 작업의 최종 결과가 항상 일정하다고 주장했기 때문이다.

신기하게도 주민들이 각자 자기 집에서 제설기를 열심히 돌리자 눈더미가 얕게 퍼졌고, 각 집마다 남은 눈의 양도 물리학자가 말한 대로 되었다. 대학원생 B모군은 여기에 흥미로운 수학적인 성질이 있을 거라곤 생각했지만, 너무 게으른 나머지 집에 들어가서 마저 보던 만화영화를 봤다.


질문: 과연 물리학자의 말은 맞았을까? 만약 그렇다면, 게으른 B모군과 달리 당신은 물리학자의 주장을 증명할 수 있을까?

 

참고 노트 

여기서 눈을 제설하는 과정이 순차적이지 않을 때를 고려해야 함을 명시한다. 구체적인 예시를 들자면, 위치 1에 있는 사람이 눈을 1분동안 제설했을 때 위치 -1에 있는 사람이 제설기를 켜서, 위치 1에 있는 제설기가 2분이 지난 뒤 제설을 마치면 위치 -1에 있는 제설기가 남은 1분동안 추가적으로 눈을 뿌릴 수 있는 것이다(그리고 이 제설기가 돌아가는 동안 또 다른 제설기가 돌아가기 시작할 수도 있다).
위 예시처럼 순차적으로 눈을 제설한다고 가정했을 때(즉, 모든 제설기들이 다 돌아간 뒤에 새로 제설기를 돌리는 경우만 가정했을 때)의 풀이는 부분 풀이로 인정하되, 이렇게 제설기가 시간차로 교차해서 돌아가는 모든 경우를 고려해야 최종 풀이로 인정된다.

 

<알립니다>

문제를 낸 백진언 국가수리과학연구소 연구원으로부터 

'shine 님이 문제를 부분해결 했다'는 소식이 왔습니다. 

제설기가 시간차로 교차해서 돌아가는 경우에 대해서도

풀어야 완벽한 해결입니다! 

댓글 28

  • 제네릭 2017.09.16 14:08:44

    제가 조건을 이해한게 맞다면,

    각 집에 있는 제설기의 눈 양은 다르며, 또한 그 제설기들이 옆으로 분사하는 눈의 양도 또한 조건에 따라서 각각 다르다.

     

    예를 들어서 3채의 집이 있다고 한다면

    왼쪽 집 제설기는 3L의 눈을 담을수 있고 오른쪽으로 2L, 왼쪽으로 1L,

    가운데 집 제설기는 7L의 눈을 담을 수 있고, 오른쪽으로 4L, 왼쪽으로 3L

    오른쪽 집 제설기는 4L의 눈을 담을 수 있고, 오른쪽으로 3L, 왼쪽으로 1L

    이 가능하다.

    이렇게 된다는 의미인가요?

     

    또한 시간에 따라 변한다는 것이, 속도랑 분사 방향이 바뀐다는 점 이외에는 무슨 특별한 규칙 같은 건 없나요? 풀이자가 임의로 규정해서 풀어도 되는건지 궁금합니다.

     

    ※ 제설기를 돌릴 수 없는 조건은 언제인가요?

    눈이 완전히 없을 때인가요, 제설기 탱크 용량 X보다 작을 때인가요?

     

    좋아요0 댓글수1
    • 수돌이 2017.09.16 20:02:47

      예를 들어서 3채의 집이 있다고 한다면

      왼쪽 집 제설기.......[생략]..........으로 1L

      이 가능하다. 이렇게 된다는 의미인가요?

      네. 그렇습니다.

       

      또한 시간에 따라 변한다는 것이, 속도랑 분사 방향이 바뀐다는 점 이외에는 무슨 특별한 규칙 같은 건 없나요? 풀이자가 임의로 규정해서 풀어도 되는건지 궁금합니다.

      분사 방향은 바뀌지 않고, 제설기가 분사하는 칸마다 속도가 바뀝니다. (분사하는 총량은 바뀌지 않습니다.)

      풀이자가 임의로 규정해서 풀 수 없습니다. 모든 바뀌는 경우에 대해서 문제를 풀어야 합니다.

       

      제설기를 돌릴 수 없는 조건은 언제인가요?

      제설기 탱크 용량 X보다 작을 때입니다.

      모든 집이 제설기 탱크 용량보다 눈이 적게 있을 때, 각 집에 있는 눈의 양을 항상 맞출 수 있다는 것을 증명하면 됩니다.

      좋아요0
  • shine 2017.09.18 16:44:03

    분사기가 각 위치에 뿌리는 눈의 양은 모두 자연수이겠지요?

    좋아요0 댓글수1
    • 구머 2017.09.18 17:31:51

      아닐 듯 한데요...

       

      좋아요0
  • 구머 2017.09.18 17:38:30

    근데 궁금한게 있는데.. 여기서 '시간'의 개념이 큰 의미가 있나요?

     

    좋아요0 댓글수3
    • 제네릭 2017.09.18 21:16:40

      아무래도 '분사 방향과 속도'가 달라진다는 것 때문에 고려는 해야할 것 같네요.

      이 분사 방향과 속도라는게 일정한 규칙이 아니라 난수처럼 매 분사시마다 마구잡이로 설정되는 거라면 더 골머리 아프겠지만요.

      좋아요0
    • 구머 2017.09.18 23:16:18

      그런데 결국 어떤 위치에 분사되는 눈 양은 일정한 거 아닌가요...?

       

      좋아요0
    • 제네릭 2017.09.21 07:34:53

      분사하는 양은 당연히 일정합니다.

      하지만, 여러 제설기들이 순차적으로 작동하지 않을 때는 한 제설기가 다른 쪽으로 눈을 분사한다고 할 때, 다른 제설기의 영향을 받을수 있으니 꼭 고려해야할 것 같습니다.

      좋아요0
  • 제네릭 2017.09.18 21:18:00

    만약에 x가 자연수라고 하면 쌓기나무(...) 같은걸 옮기면서 해볼수는 있을것 같고 (너무 유치한것 같네요 ㅇㅅㅇ;;)

    x가 실수라면 좀 복잡해질 것 같습니다.

     

    다음은 x가 자연수고, 동시에 일어나는 경우만 가정했을때 생각해볼 수 있는 단순한 예 중 하나가 될 것 같습니다(색깔은 무시하셔도 됩니다).

    각 쌓기나무는 왼쪽으로 1개, 오른쪽으로 1개씩 옮기고, 1번째에는 2개, 2번째에는 4개, 3번째에는 3개의 쌓기나무 블럭을 두었습니다. 시간에 따른 속력 변화는 고려하지 않았습니다.

    좋아요0 댓글수0
  • 제네릭 2017.09.21 07:44:37

    이런 다이어그램을 그려서 생각해볼 수 있을 것 같습니다.

    또 궁금한 점이 생겼는데, x리터만큼(여기서 x는 자연수라 가정합시다)의 눈을 n분동안 분사할 때,

    반드시 1분이 지날때마다 x/n분만큼의 눈이 주변으로 분사되나요?

     

    좋아요0 댓글수2
    • shine 2017.09.21 16:42:49

      아니요. 시간에 따라 눈을 뿌리는 속도가 달라질 수 있다고 되어 있습니다.

      좋아요0
    • 제네릭 2017.09.22 00:02:35

      그렇군요. 제가 문제를 잘 읽어보지 못했습니다.

      좋아요0
  • 김채현 2017.09.23 16:52:24

    저는 제설기가 언제나 양쪽 방향으로 눈을 뿌리며, 마을의 길이가 유한하다는 점에 착안하여 접근해 보았습니다.

    먼저 마을에는 눈이 두껍게 쌓였기 때문에, 대부분의 집들에는 제설기를 가동할 수 있을 정도의 눈이 있다고 볼 수 있습니다. 

    그리고 제설 작업이 끝나는 시점은 모든 집에 쌓인 눈의 양이 제설기의 용량보다 작아지는 시점입니다. 

    따라서 눈의 총량이 줄어들어야 하는데, 눈의 총량이 줄어들 수 있는 방법은, 오직 마을 양 끝으로 빠져나가는 것뿐입니다.

    마을 안에서 집끼리 뿌리는 눈은 총량의 감소에 기여하지 않지만, 마을 밖으로 뿌린 눈은 돌아오지 않기 때문에 

    결국은 마을 바깥으로 눈이 충분히 뿌려져야 제설 작업이 끝나는 것입니다.

     

    그리고 마을 바깥으로 눈이 충분히 뿌려질 수 있는가를 증명하려면 제설기의 성질에 주목해야 합니다.

    제설기는 무작위의 용량과 속도로 눈을 뿌리지만, 언제나 양쪽으로 뿌립니다.

    두 개의 집이 있을 때부터 생각해 봅시다.

    두 집은 분명히 눈을 서로 주고받을 수도 있지만, 결국 두 집의 눈은 양쪽으로 계속해서 빠져나가게 되어 있습니다. 

    왼쪽 집의 제설기는 오른쪽 집으로도 눈을 뿌리지만 왼쪽으로도 눈을 뿌릴 수밖에 없고, 오른쪽 집도 마찬가지입니다.

    따라서 두 집에 있는 눈의 총량은 계속 줄어들 수밖에 없습니다. 

    이는 집의 개수가 두 개가 아니라 여러 개라도 상관이 없습니다.

    이동하는 눈의 시점에서 추적해 보면, 눈은 언제나 양쪽으로 나뉘어 뿌려지기 때문에 마을 내부의 있던 눈의 일부는

    계속해서 오른쪽으로 이동해 버려지거나, 계속해서 왼쪽으로 이동해 버려집니다.

    따라서 눈의 총량은 천천히라도 분명히 감소할 수밖에 없고, 무한한 시간이 주어졌을 때(제설기가 계속 작동한다면)

    마을 내 눈의 총량은 0에 수렴하게 됩니다. 그런데 눈의 양의 목표치는 각자 집에 있는 제설기의 용량 미만으로

    양수이기 때문에 유한한 시간 내에 이를 달성할 수 있는 것입니다.

     

     

    조금 논리적인 관점으로 접근해서 풀어 보았는데, 위와 같은 방법이라면 제설이 가능하다는 것은 증명이 됩니다.

    하지만 제설기가 눈을 뿌리는 속도가 일정하지 않은데, 어떻게 물리학자가 남을 눈의 양을 예측한 것인지는 모르겠습니다.

    좋아요0 댓글수3
    • shine 2017.09.23 18:24:57

      집이 충분히 많아서, 집들이 마치 수직선에서 정수가 위치한 지점들처럼 양쪽 끝으로 충분히 길게 나열되어 있다고 가정해도 된다.

      라는 구문 때문에 마을의 길이가 유한하다고는 할 수 없습니다.

      좋아요0
    • 김채현 2017.09.23 18:34:33

      마을의 길이가 유한하지 않고 무한하며, 마을 전체에 눈이 두껍게 쌓여 있다면 처음부터 불가능하다는 것을 알 수 있지 않나요?

      '충분히 길다'라는 표현이 '무한하다'라는 것인지가 관건이네요. 하지만 만약 마을의 길이가 무한하다면 눈의 양도 무한할 것이고, 문제 해결이 불가능하다고 봅니다.

      좋아요0
    • 누군가 2017.09.23 18:36:16

      집은 무한하지만 눈이 있는 집은 유한하기 때문에 김채현님 글에서 눈의 총량을 눈을 가지고 있는 집들이 가지고 있는 눈의 평균으로 바꾸면 괜찮지 않을까요?

      눈을 가진 집만 마을에 포함된다고 하면 마을이 점점 커지는거죠. 제설기를 작동할 수 있을 때 마을의 크기가계속 커지다보면 언젠가는 제설기를 작동할 수 없는 때가 오겠죠

      좋아요0
  • c언어 2017.09.23 17:25:52

    저번 문제인 조약돌 옮기기의 확장이라고 볼 수도 있으니까 조약돌은 옮기는 것과 비슷하게 접근한다면 유한번 안에 끝난다는 것과 마지막 모양이 일정하다는 것이 증명되지 않을까요?

    좋아요0 댓글수1
    • 구머 2017.09.24 14:08:23

      아니면 그냥 연립방정식을 푸는 느낌으로 접근해도 좋을 듯 합니다..

       

      좋아요0
  • shine 2017.09.29 18:46:41

    정의: 임의로 집을 하나 잡아 집 0이라 하자.

    자연수 i에 대해, 집 0에서 왼쪽으로 i칸 위치에 있는 집을 집 -i,

    집 0에서 오른쪽으로 i칸 위치에 있는 집을 집 i라 하자.

     

    모든 자연수 n에 대하여, 다음이 성립함을 보이자.

    [n번의 제설을 하는 모든 제설과정 A_{n}에 대해,

    'A_{n}제설 시작 순서'로 순차적 제설이 가능하고, 모든 제설이 끝난 후의 결과 또한 A_{n}와 동일하다.]

     

    수학적 귀납법을 사용하자.

    i) n=1일때 

     자명하다.

    ii) n=k일때 [ ]가 성립하면, n=k+1일때도 성립함을 보이자.

    A_{k+1}에서 k+1번째 제설을 하기 직전의 상태를 P라 하고, P에서 각 집 i에 쌓인 눈의 양(제설기 안에 들어있는 눈은 무시)을 p_{i}라 하자.

    A_{k+1}에서 k+1번째 제설을 하지 않았을 때(즉 처음 k번의 제설만 했을 때) 이르는 최종 상태를 Q라 하고, Q에서 각 집 i에 쌓일 눈의 양을 q_{i}라 하자.

    n=k일때 [ ]가 성립하므로, A_{k+1}의 처음 k번의 제설 시작 순서대로 순차적 제설이 가능하고, 최종 상태 역시 Q와 같다.

    이때, P에서 Q 상태가 될 때까지 제설이 한번도 시작되지 않는다. 그러니 각 집에 쌓인(제설기 안의 것 제외할 때) 눈의 양이 감소하지 않는다.

    즉 모든 i에 대해 p_i\leq q_i 이다.

    따라서 P 상태에서 제설기를 가동할 수 있는 집은 Q 상태에서 제설기를 가동할 수 있는 집에 포함된다.

    그러니 A_{k+1} (P 상태에서 제설기를 가동)의 제설 시작 순서로 순차적 제설(Q 상태에서 제설기를 가동)이 가능하다.

     

    d_i=q_i-p_i 라고 하자.

    A_{k+1}의 마지막 제설이 각 집 i에 주는(제설한 집에 한해서 뺏는) 눈의 양을 e_i라 하자.

    d_i,e_i의 값은 k+1번째 제설을 언제 했는지에 관계없이 일정하므로 A_{k+1}과 순차적 시행의 최종 상태에서 각 집의 눈의 양은

    p_i+d_i+e_i로 같아진다.

     

     

    따라서 수학적 귀납법에 의해 모든 자연수 n에 대하여 []가 성립한다.

    그러므로 순차적으로 제설하는 경우에서만 최종상태가 항상 존재함을 보이면 그것이 순차적이지 않은 제설에서도 성립한다.

    좋아요0 댓글수5
    • shine 2017.09.29 18:47:51

      풀이 작성중이라 비밀댓글 처리하였습니다.

      좋아요0
    • shine 2017.10.15 16:19:58

      풀이가 완성되었습니다.

      좋아요0
    • 구머 2017.10.15 18:15:59

      아..그럼 아직 해결 안된건가요?

      좋아요0
    • shine 2017.10.15 21:30:14

      이제 이걸 조약돌 옮기기의 제 (3)번 문제 풀이와 연계하면...!

      좋아요0
    • 구머 2017.10.15 22:28:00

      두...둥!

      좋아요0
  • shine 2017.10.16 13:21:38

    일단 가져왔습니다.

    /resources/comment/2017/10/1d424c920654b01afb61ad65cb7af082.jpg

    /resources/comment/2017/10/9ec48945cb9397420eb08555ab972377.jpg

    좋아요0 댓글수0
  • shine 2017.10.16 13:23:23

    여기서 유한한 과정이라는 걸 증명하거나, 유한한 과정이라는 조건 없이 풀이를 만들 수 있다면 해결되겠네요.

    좋아요0 댓글수0
  • shine 2017.10.23 13:12:23

    풀이에서 유한한 과정(최종상태의 존재 여부)이라는 것이 쓰이는 부분은 두번째 페이지의 1~2줄

    "따라서 시행을 더 할 수 없는 최종상태 P가 되기까지

    q_1 에서의 시행이 적어도 한번 있어야 한다."

    입니다.

     

    그런데 문제에서

    각자 제설기를 쓸 수 없을 때까지 최대한 그 자리에서 제설을 하셨을 때

    라는 부분이 있으니 최종상태의 존재여부를 쓰지 않고도 q_1 에서의 시행이 적어도 한번 있어야 한다는 것이 보여지네요.

     

    그러니 제설 순서에 관계없이 제설 작업의 결과가 항상 일정합니다.

     

    좋아요1 댓글수0
  • shine 2017.10.23 13:20:08

    그리고 X가 자연수인지 여부를 물었던 것은 예를 들어 집의 수가 무한했을때,

    i에서의 X를 \left ( \frac{1}{2} \right )^ {\left | i \right |}로 설정하고 눈의 총량이 3보다 크다면

    영원히 제설이 계속되기 때문입니다.

     

    X의 제한 조건, 집의 수의 무한한지의 여부 등이 정확히 되어야 최종 상태가 존재하는지의 여부를 따질 수 있을 것 같습니다.

    좋아요0 댓글수0