[문제] 특별한 10자리 숫자

어제 문제적 남자 (73회) 를 보던 중 아래와 같은 문제가 마지막으로 나왔다.

$0$부터 $9$까지 $10$개의 숫자를 단 한번씩만 사용하여 다음의 규칙을 만족하는 $10$자리의 숫자를 만들어라: 모든 $1 \leq n \leq 10$에 대하여, 이 숫자의 앞에서부터 $n$자리 까지가 $n$으로 나누어 떨어진다.

예를 들어 $10$자리 숫자 $1234567890$의 경우, 앞에서 부터 $1$자리 까지인 $1$은 당연히 $1$로 나누어 떨어지고, 앞에서 부터 $2$자리 까지인 $12$는 $2$로 나누어 떨어진다. 앞에서 부터 $3$자리 까지인 $123$ 또한 $3$으로 나누어 떨어지지만 앞에서 부터 $4$자리 까지인 $1234$는 $4$로 나누어 떨어지지 않는다. 따라서 $1234567890$은 주어진 조건을 만족하지 못한다.

이 문제는 유명한 고전 수학 퍼즐 중의 하나로 2016년 3월 14일 (pi 데이)를 기념하기 위하여, 피자헛이 수학자 John Conway의 자문을 받아서 출제한 3개의 수학 퍼즐 중 첫번째 문제라고 한다. 참고로 이 문제를 맞춘 사람은 3.14년간 피자를 무료로 먹을 수 있는 쿠폰^[각주:1]을 주었다고 한다.

또한 이 문제의 조건을 만족하는 숫자를 지칭하는 특별한 이름이 있는데 이는 다음과 같다. 우선 $n$자리의 숫자가 주어졌다고 하자. 만약 임의의 $1 \leq n \leq 10$에 대하여, 이 숫자의 앞에서부터 $n$자리 까지가 $n$으로 나누어 떨어지면, 이 숫자를 polydivisible number^[각주:2]라고 한다. 또한 주어진 숫자에 $0$ 부터 $9$까지의 모든 숫자가 적어도 한번씩 쓰여졌으면, 이 수를 pandigital number^[각주:3]라고 한다. 따라서 이러한 수학 용어들을 이용하여 위 문제를 다음과 같이 다시 쓸 수 있다.

$10$자리의 polydivisible pandigital number를 찾아라.

1. 약 $1,600 정도라고 한다. [본문으로]
2. 적당한 한글용어가 존재하지는 않지만 직역하자면 "복합적으로 나누어떨어지는 수" 정도가 될 것 같다. [본문으로]
3. 마찬가지로 적당한 수학용어가 존재하지 않는다. 굳이 번역하자면 "범디지털수" 정도가 된다. [본문으로]