GSM 네트워크의 가장 중요한 부분은 BTS(Base Transceiver Station)이라 불리는 곳이다. 이 송수신기들은 cell(이 용어는 cellular phone이라는 이름을 만들었다) 이라 불리는 영역을 형성하여 모든 전화기는 BTS에 가장 강력한 신호로 연결된다.(약간 간략화된 관점) 물론, BTS들은 그들이 제대로 동작하는지 주기적으로 점검하고 그를 위한 기술자들이 필요하다.
ACM 기술자들은 최근에 흥미로운 문제에 봉착했다. 방문하기로 한 BTS들의 집합이 주어지면, 그들은 모든 지점을 방문하고 중앙 회사 빌딩으로 돌아오기 위한 최소 경로를 찾아야 할 필요성을 느꼈다. 프로그래머들은 이 문제를 몇 달 동안 연구했지만 성과가 없었다. 그들은 충분히 빠른 솔루션을 찾는 데 실패했다. 긴 시간이 지난 뒤, 한 프로그래머가 이 문제를 학회 논문에서 찾아냈다. 불행하게도 그가 찾은 것은 “Travelling Salesman Problem”이라 불리는 문제로 굉장히 풀기 어렵다고 한다. 만약 방문하기로 한 BTS가 N 개 있다면, 우리는 어떤 순서로든지 BTS들을 방문할 수 있기에 N! 개의 조사할 가능성이 생기게 된다. 1.2.3.4....N. 이 숫자를 표현하는 함수는 팩토리얼이라 불리고 1,2,3,…,N까지의 곱으로 계산된다. 이 숫자는 상대적으로 작은 N에 대해서도 아주 큰 값이다.
프로그래머들은 이 문제를 해결할 가능성이 없다는 것을 깨달았다. 그러나 그들은 이미 정부로부터 연구비를 받았기에 연구를 계속해서 조금의 성과라도 내야만 했다. 그래서 그들은 팩토리얼 함수의 행동에 대한 연구를 시작했다. 그들은 함수 Z를 정의했다. 어떤 양의 정수 N에 대해서도, Z(N)은 N!의 십진수 형식의 0의 개수를 나타낸다. 그들은 이 함수가 절대 감소하지 않는다는 것을 알아냈다. N1 < N2인 숫자가 있다면 항상 Z(N1) <= Z(N2)이다. 왜냐하면 양의 정수를 곱해서는 따라오는 0을 ‘잃어버릴’ 수 없기 때문이다. 결국 우리는 새로운 0을 얻고 또 얻을 수밖에 없다. 함수 Z는 굉장히 흥미로웠고, 우리는 이 값을 효율적으로 계산하는 프로그램을 필요로 하게 되었다.
입력 6 3 60 100 1024 23456 8735373 출력 0 14 24 253 5861 2183837
출처: Central Europe 2000 번역: halfleaf