d라이브러리

유명 패스트푸드 가게에서 아르바이트를 시작했습니다. ‘햄버거 세트를 시키면 각각 주문할 때보다 할인이 되고, 치킨 너겟인 맥너겟은 6개, 9개, 20개씩만 판매할 수 있다’. 점장님이 알려주신 방법을 속으로 다시한번 생각합니다. 드디어 첫 손님이…, 손님 세 명이 한꺼번에 우르르 들어옵니다.

“맥너겟 41개요”, “맥너겟 43개요”, “맥너겟 44개요”.

다행히도 모두 맥너겟을 주문하는 손님이네요. 어렵지 않게 처리할 수 있다고 생각한 순간, 교육하는 점장님의 한 마디가 등골을 서늘하게 만듭니다.

“손님 중에 ‘맥너겟 수’대로 주문 안 한 분이 계시네.”

재앙도 이런 재앙이 없습니다. 잘못된 주문이 있을 줄이야….

꿈에도 생각 못 했습니다. 하지만 첫 주문도 못 받고 해고당할 수는 없습니다! 점장님이 말해줬던 맥너겟 수를 안간힘을 다해 떠올려봅니다. 맥너겟 수를 찾기 위해 먼저 알아야 했던 게…. 프로…, 프로…, 프로베니우스의 수!

2원과 5원짜리 동전으로 만들 수 없는 금액은?

맥너겟 수를 알기 전에 동전 문제부터 알아야 합니다. 동전 문제는 독일 수학자 페르디난트 프로베니우스의 이름을 따서 프로베니우스 문제라고도 부릅니다. 맥너겟 수는 이 동전 문제의 한 예시고요.

동전 문제는 서로 다른 동전이 있을 때 이 동전으로 만들 수 없는 가장 큰 수를 찾는 문제입니다. 예를 들어 2원짜리 동전과 5원짜리 동전이 있다면, 두 동전의 조합으로 만들 수 없는 금액은 1원과 3원뿐 입니다. 그 외의 금액은 모두 만들 수 있지요. 이때 두 동전으로 만들 수 없는 가장 큰 수 3이 프로베니우스의 수이고, 이를 찾는 문제가 바로 프로베니우스 문제 또는 동전 문제입니다.

프로베니우스의 수는 서로소인 수 사이에서만 있습니다. 서로소가 무엇이냐고요? 어떤 수들의 공통 약수, 즉 공약수가 1뿐인 수들의 관계를 서로소라고 합니다.

1882년 영국 수학자 제임스 조세프 실베스터는 서로소 관계인 두 수가 있을 때 프로베니우스 수를 찾는 방법을 공식으로 만들었습니다. 서로소인 두 수 a와 b의 프로베니우스 수는 (a-1)(b-1)-1입니다. 위에서 언급한 두 수 2와 5를 공식에 넣어보면 1×4-1로, 3이 맞습니다.

43개는 주문 못하는 이유

동전 종류가 훨씬 더 많을 때는 어떨까요? 아쉽게도 이 경우에 대해서는 아직 공식으로 알려진 바가 없습니다. 동전의 액면가를 알고 있기만 하면 알고리즘을 만들 수 있긴 합니다. NP-하드 문제에 속하지만요.

NP 문제는 답이 될 수 있는 후보는 찾을 수 있지만 정확한 답을 찾을 수 없는 문제들입니다. 답을 정확히 구하려면 모든 경우의 수를 일일이 확인해 보는 방법밖에 없다는 뜻이지요. NP-하드 문제는 모든 NP 문제보다도 풀기 더 어려운 문제의 집합입니다. 세 종류 이상의 동전으로 프로베니우스의 수를 찾는 건 여간 어려운 일이 아니지요.

그러던 중 특별한 숫자 조합으로 맥너겟 수가 탄생했습니다. 수학교육자 앙리 피치오토가 아들과 맥도날드에서 저녁을 먹던 중에 발견했지요. 당시 영국 맥도날드에서는 맥너겟을 6개, 9개, 20개씩만 팔고 있었습니다. 이때 피치오토는 맥너겟 수를 떠올려 매장에 있던 냅킨에 바로 계산했고, 이 결과를 그가 쓴 대수학 책에 소개했습니다.

6, 9, 20은 공약수가 1뿐인 서로소이기 때문에, 충분히 큰 어떤 수는 이 세 수의 결합으로 나타낼 수 있습니다. 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, 43을 제외하고요. 나열한 수 이외의 모든 자연수는 맥너겟 상자 조합으로 만들 수 있다는 뜻이고, 이 수를 맥너겟 수라고 합니다. 그리고 맥너겟 수가 아닌 가장 큰 수 43이 바로 서로소인 세 수 6, 9, 20의 프로베니우스의 수이지요. 그러니 우리 매장에서 43개는 주문할 수 없어요!

“맥너겟 43개 주문한 손님, 43은 맥너겟 수가 아니라 구매하실 수 없습니다. 다시 말씀해 주세요~.”