복면산

3. 규칙

• 각 문자는 0부터 9까지의 서로 다른 숫자를 나타낸다. (같은 문자는 같은 숫자, 다른 문자는 다른 숫자를 사용)^[1]
• 가장 왼쪽에 있는 문자(최상위 숫자)는 0이 될 수 없다.^[2]
• * 한 자리 수의 경우에도 최상위 숫자로 간주하여 0을 사용하지 않는 것이 일반적이지만, 한 자리 수의 경우에는 0을 허용하는 경우도 있다.
• 문제에 제시된 숫자를 문자에 대입할 수도 있다.^[3]

4. 유형

암호 셈에는 알파벳 셈, 숫자 셈, 뼈대 나눗셈 등의 유형이 있다.

• 알파벳 셈은 문자들을 숫자로 대체하여 유효한 산술 계산을 만드는 방식이다.
• 숫자 셈은 숫자가 다른 숫자를 나타내는 암호 셈이다.
• 뼈대 나눗셈은 대부분의 숫자가 기호로 대체된 나눗셈 문제로, 리처드 파인만의 뼈대 나눗셈 퍼즐이 잘 알려져 있다.^[5]

4. 1. 알파벳 셈 (Alphametic)

• SEND + MORE = MONEY

• FORTY + TEN + TEN = SIXTY

• 바나나 + 바나나 = 시나몬

• 물 × 물 = 음료수

• ----

• ----

• ---

4. 2. 숫자 셈

4. 3. 뼈대 나눗셈 (Skeleton Division)

4. 4. 수사 복면산 (Doubly True Alphametic)

• third + third + third + seven = eight

4. 5. 복합 복면산

4. 6. Word Arithmetic

4. 7. 기하 무늬 복면산

4. 8. 초고층 복면산

• 에 × 5000 + 센 × 4 + 니센 × 8 = 산만

4. 9. 연립 복면산

위의 식만으로는 7개의 해(b=0을 인정하면 8개)가 존재하고, 아래의 식만으로는 3개의 해가 존재하지만, (위의 식의 b)=(아래의 식의 b), (위의 식의 c)=(아래의 식의 c)이므로 해가 하나로 결정된다.

5. 풀이 방법

복면산의 풀이 방법은 문제에 따라 다양하지만, 일반적으로 다음과 같은 방법들을 사용한다.

• 손으로 복면산을 푸는 것은 추론과 가능한 경우를 철저하게 검토하는 방식으로 이루어진다. 예를 들어, SEND+MORE=MONEY 문제는 다음과 같이 풀 수 있다.

• TO+GO=OUT의 경우

모듈러 산술을 사용하면 도움이 될 수 있다. 예를 들어, mod-10 산술을 사용하면 덧셈 문제의 열을 연립 방정식으로 처리할 수 있으며, mod-2 산술을 사용하면 변수의 패리티를 기반으로 추론할 수 있다.

컴퓨터 과학에서 복면산은 무차별 대입 방법과 ''n''개의 가능성에서 ''m''개의 선택에 대한 모든 순열을 생성하는 알고리즘을 설명하는 좋은 예시를 제공한다. 또한 알고리즘 설계의 백트래킹 패러다임에 대한 좋은 예시를 제공한다.

• "바나나 + 바나나 = 시나몬"을 예시 문제로 사용할 때, 다음과 같은 풀이 방식이 있다.

6. 제작 방법

복면산 제작에는 정해진 방법은 없지만, 일반적으로 다음과 같은 단계를 따른다.

1. 테마를 정하고 단어 후보를 제시한다.

2. 후보를 조합하여 식을 만든다.

3. 검산한다.

4. 해가 1개라면 완성.

5. 해가 여러 개 있거나 존재하지 않는 경우, 2번으로 돌아가 새로운 조합을 생각한다.

예를 들어, 유럽을 테마로 한 복면산을 생각해 보자.

먼저 "영국+스위스=유럽"이라는 식을 생각하면, 이것에는 해가 2개 있다. 다음에 조사를 붙여서 "영국과+스위스=유럽"이라는 식을 생각하면, 이것은 해가 3개 있다. 다음에 영국을 이탈리아로 바꿔 "이탈리아+스위스=유럽"이라는 식을 생각하면 이것은 해가 1개이다. 이것으로 하나의 문제가 완성된다.

위의 절차에서 "검산한다"라고 썼지만, 실제로는 보기만 해도 해가 없거나 여러 개가 있다는 것을 알 수 있는 경우도 많다.

다음은 대표적인 예를 나타낸다.

• 문자 수 과다: 숫자는 10종류밖에 없으므로 11종류 이상의 문자를 사용한 문제에는 해가 없다.
• 자릿수 부족: 합의 자릿수가 다른 것보다 2자릿수 이상 (항의 수가 많은(12 이상) 경우에는 예외) 크면 올림을 고려하더라도 최고위가 0이 된다. 이것은 규칙으로 인정되지 않는다.
• 예를 들어 "one+two=three"라는 문제는 3자리 + 3자리이므로 합은 최대 4자리가 된다.
• 뜨기: 전체에서 한 번만 사용된 문자가 같은 자리에 있으면, 그 두 문자가 교환 가능하게 되어 여러 개의 해가 발생한다. 이것을 "뜨기"라고 한다.
• 예를 들어 "カナダ+ロシア=アメリカ(캐나다+러시아=아메리카)"라는 문제는 십의 자리 "ナ(나)"와 "シ(시)"가 교환 가능하다. 백의 자리는 "カ(카)", 일의 자리는 "ア(아)"가 각각 합에서도 사용되고 있으므로 문제 없다.
• 미국 등에서는 뜨기가 있는 경우 작은 숫자를 위의 문자에 대입한다는 규칙이 있어서, 여러 개의 해의 요인이 되지 않는다.

7. 기타

임의의 기저로 일반화되었을 때, 암호 산술이 해를 가지는지 결정하는 문제는 NP-완전이다.^[6] 10진법에서는 문자에 숫자를 할당하는 가능한 경우의 수가 10!개밖에 없으며, 이는 선형 시간 내에 퍼즐에 대해 확인할 수 있기 때문에 일반화는 경도 결과를 위해 필요하다.

알파메틱스는 스도쿠와 카쿠로와 같은 다른 숫자 퍼즐과 결합하여 암호 스도쿠 및 카쿠로를 만들 수 있다. 컴퓨터를 이용하여 복면산을 생성하는 프로그램이 존재한다. 가장 일반적인 것은 단어군을 데이터로 전달하면 그 단어를 조합하여 문제를 만드는 것이다.

단어 조합이 제한되는 수사 복면산에서는 컴퓨터를 이용한 탐색이 일반적이다.

10진법이라면 각 문자에 0~9의 숫자를 할당하고, 식이 성립하는지 확인하면 되므로, 10!가지 방법을 확인하는 것으로 풀 수 있다. 일반적으로 r진법이라면 r!가지 확인을 함으로써 컴퓨터로 쉽게 풀 수 있다. 그러나 "어떤 진법인가"도 입력의 일부가 되는 문제에 대해서는 두 숫자의 덧셈에 관한 문제가 NP 완전임이 증명되었으며,^[23] 매우 어려운 부류에 속하는 문제로 여겨진다.

8. 복면산의 예 (한국어)

이밖에도 어떤 숫자라도 가능하다는 뜻으로 문자 대신 빈 칸이나 * 기호를 사용한 문제도 있다. 이런 종류는 특별히 충식산(蟲食算, 벌레 먹은 셈)이라 부르기도 한다.

참조

_[1] 간행물 Strand Magazine 1924-07
_[2] 뉴스 No. 109 Mathematical puzzle https://archive.org/[...] 1864-12
_[3] 서적 Mathematical Recreations 1953
_[4] 뉴스 Globe and Mail Toronto 1955-10-27
_[5] 서적 Perfectly Reasonable Deviations from the Beaten Track: The Letters of Richard P. Feynman https://books.google[...] Basic Books 2008-08
_[6] 논문 On the NP-completeness of cryptarithms http://www.ics.uci.e[...]
_[7] 웹사이트 Crux Mathematicorum https://cms.math.ca/[...] 2016-12-14
_[8] 간행물 1946
_[9] 간행물 1976
_[10] 간행물 1985
_[11] 간행물 1985
_[12] 간행물 1985
_[13] 간행물 1985
_[14] 간행물 1985
_[15] 간행물 1988
_[16] 간행물 1985
_[17] 간행물 1988
_[18] 간행물 1985
_[19] 간행물 1985
_[20] 간행물 1985
_[21] 간행물 1977
_[22] 문서 虫食い算の歴史
_[23] 논문 On the NP-completeness of cryptarithms
_[24] 문서 研究社 リーダーズ英和辞典/リーダーズ・プラス 第2版 → cryptarithm