[12월의 퍼즐] 수를 굽는 마법의 오븐

매월 정답자 한 분을 선정하여 고등과학원에서 소정의 상품을 드릴 예정입니다
퍼즐 참여는 12월 27일까지 가능하며 다음달 초 해설과 함께 정답자가 공개됩니다
(답안과 함께 이름, 연락처를 남겨주셔야 정답자 선정 연락이 가능합니다!)

코로나19로 힘든 한 해였으니, 이번 호는 정답자를 여러 명 선정할 계획입니다. 본문의 네 가지 문제에 대해 정답자를 각각 한 명씩, 최대 네 명을 선정하여 소정의 상품을 보내드릴 예정이니 답안에 이름과 연락처를 꼭 남겨주시기 바랍니다.

***

코로나19로 힘들었던 2020년이 끝나가고 있다. 연말을 기념하며 새해에는 온 세상이 정상이 되기를 기원하면서 마법의 오븐으로 쿠키를 구워 보자.

사칙연산 기호와 제곱근 기호가 적힌 버튼이 붙어 있는 작은 오븐이 있다. 여기에 숫자를 배열하여 구우면 계산 결과가 새로운 쿠키로 만들어져 나온다. 사칙연산이나 제곱근 기호는 쿠키를 구울 때마다 한 번씩만 쓸 수 있다. 단, 계산 결과가 자연수가 아니거나, 넣은 숫자보다 더 많은 숫자가 나오는 계산이라면 오븐이 작동하지 않는다.

처음에 세 숫자 1, 2, 3이 주어져 있다. 이 쿠키로 4를 만들려면, 오븐에 1과 3을 넣고 \(+\) 버튼을 누른 다음 구우면 된다. 그러면 1과 3이 합쳐져 4라는 쿠키가 만들어진다.

5는 2와 3의 합으로 만들 수 있다. 6은 \(1+2+3\)이지만, 이렇게 만들려면 먼저 \(1+2\)로 3을 만들고, 다시 \(3+3\)으로 6을 만들어야 해서 오븐을 두 번 써야 한다. 이것보다는 \(2 \times 3\)으로 만들면 오븐을 한 번만 써도 된다.

7은 6을 만든 다음 \(1+6\)으로 만들 수 있다. 오븐은 두 번 사용하게 된다.

8은 어떨까? 사칙연산으로는 8을 만들기가 어려운데, 이 경우는 오븐에 2와 3을 지수 모양으로 배열하여 구우면 된다. 이것도 오븐을 한 번 사용한 것이다. \(2^{31}\)을 만들면 8을 비롯하여 여러 숫자를 만들 수 있지만, 오븐에 넣을 때보다 더 많은 숫자를 만드는 수식은 구워지지 않는다. 따라서 오븐을 아무리 많이 써도 네 자리 수는 만들 수 없다.

9는 \(3^2\)으로 만들 수 있다. 여기에 1을 더하면 10이 된다.

11은 어떻게 만들 수 있을까? 먼저 \(3-2\)로 1을 만든 다음, 원래 있던 1과 새로 만든 1을 접시에 나란히 담으면 된다. 오븐은 한 번만 사용했다.

12는 오븐을 쓰지 않고, 그냥 1과 2를 접시에 담기만 하면 된다. 13도 마찬가지.

14는 어떻게 만들 수 있을까? 먼저 오븐에 13과 2를 배열하여 \(13^2 = 169\)를 만든다. 여기서 \(6-1\)로 5를 만들고, 다시 \(5+9\)로 14를 만들면 오븐을 세 번 쓰게 되지만, 169를 재배열하여 196을 오븐에 넣고 제곱근을 적용하면 오븐을 두 번만 쓰고 14를 만들 수 있다. 169를 이용하면 오븐을 한 번만 써서 16, 19, 61, 66, 69, 91, 96, 99를 만들 수 있다.

이런 식으로 숫자 1, 2, 3에서 시작하여 다양한 수를 만들어 보자. 조건을 정리하면 다음과 같다.

모든 조작은 1, 2, 3에서 시작한다.
오븐에 수를 배열하면 계산 결과가 새로운 쿠키로 만들어진다.
연산은 한 번에 하나만 사용할 수 있다. 지수 모양으로 배열하는 것도 연산 하나로 생각한다.
6을 뒤집어 9로 사용하거나, 9를 뒤집어 6으로 사용할 수 있다.
계산 결과가 자연수가 아닌 수식은 처리되지 않는다.
숫자 개수가 더 많아지는 수식은 처리되지 않는다.
접시에 옮겨 담아 다른 수를 만드는 것은 오븐 조작 횟수에 포함하지 않는다.

이제 몇 가지 문제를 풀어 보자.

문제1 숫자 1, 2, 3으로 시작하여 오븐으로 구워낼 수 있는 가장 큰 수는 무엇일까? 숫자의 개수가 늘지 않으므로 999보다 크지 않다는 것은 분명하다.

문제2 숫자 1, 2, 3으로 시작하여 오븐으로 구워낼 수 없는 가장 작은 수는 무엇일까? 앞서 살펴본 예에서 14까지는 만들어 보았다.

문제3 오븐을 가장 많이 써야 하는 수는 무엇일까? 당연히 이 질문은 오븐을 최소한으로 사용한다는 전제 조건 아래 생각한다.

문제4 새로운 수를 만들어낼 때마다 쿠키를 먹어 치우는 대신 접시에 담아 사진만 찍고 재활용한다고 생각하자. 1, 2, 3에서 시작하여 연속적으로 만들어낼 수 있는 수는 최대 몇 개나 가능할까? 우선, 한 자리수인 1, 2, 3과 12, 13, 21, 23, 31, 32, 123, 132, 213, 231, 312, 321은 오븐을 쓰지 않고 만들 수 있다. 이어서 \(2+3=5\)를 만들면, 15와 51은 오븐을 쓰지 않고 추가로 만들 수 있고, 오븐을 한 번 더 쓰면 \(1+5=6\)을 만들 수 있고, 이걸 뒤집어 9를 만들 수도 있지만, 6 이외에 남는 숫자가 없으므로 여기서 정지한다. 그러면 모두 20개의 수를 만들 수 있다.

* 네 가지 문제 전체 혹은 일부에 관해 답변을 제출해주시면 됩니다.
문제별로 정답자를 선정할 예정입니다.