🔢 mathematics

Partitioning set $[n] = \{1, \dots, n\}$ into subsets of size at most $m$ such that all sums are powers of $m$

이 논문은 집합 $\{1, \dots, n\}$ 을 합이 $m$ 의 거듭제곱이 되는 크기 최대 $m$ 인 부분집합들로 분할하는 분할의 존재성과 유일성을 조사하며, $m > 3$ 일 때 그러한 분할이 무수히 많은 $n$ 에 대해 존재하지 않는 반면, $m = 3$ 일 때는 (잠재적 반례에 대한 특정 제약 조건 하에) 모든 $n$ 에 대해 존재할 가능성이 높다는 것을 증명하고, 다양한 $n$ 값에 대한 그러한 분할의 개수에 대한 정확한 수를 확립한다.

원저자: Vladimir Gurvich, Mariya Naumova

게시일 2026-07-17

📖 5 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Vladimir Gurvich, Mariya Naumova

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신이 정확히 $n$ 개의 고유한 벽돌(1부터 $n$ 까지 번호가 매겨진)을 사용하여 도시를 건설해야 하는 숙련된 건축가라고 상상해 보십시오. 당신의 목표는 단순히 벽돌을 쌓는 것이 아닙니다. 당신은 벽돌들을 '이웃(부분 집합)'으로 그룹화해야 하며, 여기에는 두 가지 엄격한 규칙이 적용됩니다. 첫째, 어떤 이웃도 너무 붐벼서는 안 됩니다. 즉, 한 이웃은 최대 $m$ 개의 벽돌을 가질 수 있습니다. 둘째, 각 이웃에 담긴 벽돌의 총 "무게"는 특정 마법의 숫자 $m$ 의 완전승수(예: $m^0=1, m^1=m, m^2$ 등)여야 합니다. 이 퍼즐은 조합론(combinatorics)의 세계에 속해 있으며, 조합론은 숫자들이 어떻게 배열되고, 세어지고, 그룹화되는지를 연구하는 수학의 한 분야입니다. 이것은 격자의 크기에 따라 규칙이 변하는 거대한 무한 스도쿠를 푸는 것과 같습니다. 수학자들은 숫자를 어떻게 분해하고 다시 조립할 수 있는지 이해하는 것이 마치 원자의 결합을 이해하는 것이 새로운 재료를 만드는 데 도움이 되는 것과 같이, 수학의 구조에 대한 깊은 비밀을 드러낸다는 점 때문에 이 문제를 중요하게 여깁니다.

이제 당신이 읽게 될 논문은 이 퍼즐의 매우 까다롭고 구체적인 버전을 다룹니다. 저자들인 블라디미르 구르비치(Vladimir Gurvich)와 마리야 나우모바(Mariya Naumova)는 마법의 숫자 $m$ 을 3으로 설정했습니다. 이는 그들이 1부터 $n$ 까지의 숫자를 크기가 1, 2, 또는 3인 그룹으로 나누되, 각 그룹의 합이 3의 거듭제곱(1, 3, 9, 27 등)이 되도록 하려는 시도를 의미합니다. 그들은 이미 $m=2$ 일 때, 모든 $n$ 에 대해 항상 정확히 한 가지 방법이 존재한다는 것을 알고 있었습니다. 또한 $m$ 이 3보다 클 경우, 무수히 많은 $n$ 값에 대해 이 퍼즐은 불가능하다는 것도 알고 있었습니다. 하지만 $m=3$ 인 경우, 답은 미스터리였습니다. 저자들은 모든 $n$ 에 대해 솔루션이 존재한다는 강력한 추측(conjecture)을 하고 있습니다.

이를 테스트하기 위해 그들은 단순히 추측만 한 것이 아니라, 수학적 안전망을 구축했습니다. 만약 어떤 $n$ 에 대해 솔루션이 존재하지 않는다면, 그 "나쁜" 숫자 $n$ 은 매우 특정한, 기묘한 형태를 띠어야 한다는 것을 그들은 증명했습니다. 그 숫자는 반드시 $n = 3t + 3k + 2$ 의 형태여야 하며, 다른 특정 패턴들을 피해야 합니다. 이것은 마치 탐정이 "만약 범죄가 발생했다면, 용의자는 빨간 모자를 쓰고, 다리를 절며, 왼손잡이여야 한다"라고 말하는 것과 같습니다. 만약 어떤 용의자가 그 설명에 부합하지 않는다면, 당신은 그가 범인이 아님을 알 수 있습니다. 저자들은 이러한 논리를 사용하여 거대한 숫자 덩어리들을 배제했습니다. 또한 그들은 컴퓨터 시뮬레이션을 실행하여 844까지의 모든 숫자를 확인했으며, 모든 경우에서 솔루션을 찾아냈습니다. 그들은 또한 하나의 숫자가 두 번 사용될 수 있는 "준분할(quasi-partition)"이라는 약간 더 느슨한 버전의 퍼즐을 탐구했고, 거기에서도 솔루션이 존재함을 증명했습니다. 비록 그들이 아직 모든 $n$ 에 대해 이 퍼즐이 풀린다는 것을 완전히 증명하지는 못했지만, 반례를 찾기 위한 범위를 매우 작고 특정한 리스트로 좁혀 놓았으며, 그 외의 거의 모든 숫자에 대해서는 솔루션이 가능할 뿐만 아니라 종종 유일하다는 점을 확신하고 있습니다.

위대한 숫자 그룹화 게임

당신에게 1부터 큰 숫자 $n$ 까지 번호가 매겨진 타일 주머니가 있다고 상상해 보십시오. 당신의 임무는 이 타일들을 더미로 분류하는 것입니다. 하지만 규칙이 있습니다!

크기 규칙: 각 더미는 최대 3개의 타일을 가질 수 있습니다.
합계 규칙: 각 더mi에 담긴 숫자의 합은 "3의 거듭제곱"이어야 합니다. 즉, 합은 1, 3, 9, 27, 81 등과 같아야 합니다.

이것이 바로 "3-good partition" 문제입니다. 저자들은 "2-good" 분할(더미에 최대 2개의 타일이 있고 합이 2의 거듭제곱인 경우)에 대한 답을 오랫동안 알고 있었습니다. 2-good의 경우, 항상 정확히 한 가지 방법이 존재한다는 것이 밝혀졌습니다. 하지만 3의 경우는 규칙이 훨씬 복잡해집니다. 저자들은 답이 "항상 가능하다"라고 추측하지만, 이를 증명하는 과정은 험난했습니다.

"결정적인" 용의자들

직접 모든 숫자에 대해 증명하는 대신(그것은 어렵습니다), 저자들은 "나쁜 놈들"—즉, 실패하는 숫자들—을 찾는 데 집중하기로 했습니다. 그들은 만약 어떤 숫자 $n$ 에서 그룹을 만들 수 없다면, 그 숫자는 "결정적인(critical)" 숫자여야 한다고 추론했습니다.

그들은 만약 그러한 결정적인 숫자가 존재한다면, 그것은 아무 숫자나 될 수 없음을 증명했습니다. 그 숫자는 반드시 특정한 변장을 하고 있어야 합니다. 반드시 다음과 같은 형태여야 합니다:
$n = 3t + 3k + 2$
그리고 $k$ 가 $t$ 에 비해 얼마나 큰지에 대한 추가적인 조건을 만족해야 합니다.

이것은 마치 클럽 입구의 보안 요원과 같습니다. 보안 요원이 말합니다. "티켓 없이 몰래 들어오려면, 반드시 초록색 모자를 쓰고 파란색 가방을 들고 있어야 합니다." 만약 당신이 빨간 모자를 쓴 사람을 본다면, 당신은 그가 잠입하려는 침입자가 아님을 확실히 알 수 있습니다. 저자들은 이 "초록색 모자" 설명에 부합하지 않는 모든 숫자는 안전하다는 것을 증명함으로써, 이 숫자들이 안전하게 그룹화될 수 있음을 보여주었습니다. 즉, 이 과정을 통해 방대한 양의 가능성을 제거했습니다.

컴퓨터 검증

이러한 영리한 수학적 논리에도 불구하고, 여전히 "초록색 모자" 설명을 충족하는 숫자들이 남아 있었습니다. 확실히 하기 위해, 저자들은 컴퓨터 프로그래머인 드미트리 리빈(Dmitry Rybin)의 도움을 받아 844까지의 모든 숫자를 확인하는 프로그램을 작성했습니다.

결과: 1부터 844까지의 모든 숫자에 대해, 그들은 타일을 완벽하게 그룹화하는 방법을 찾아냈습니다.
결론: 컴퓨터는 단 하나의 "나쁜" 숫자도 찾아내지 못했습니다. 이는 이 퍼즐이 모든 숫자에 대해 해결 가능하다는 그들의 추측을 강력하게 뒷받연합니다.

"준분할(Quasi-Partitions)"의 반전

저자들은 약간 다른 게임도 시도했습니다. 만약 하나의 숫자를 두 번 사용할 수 있다면 어떨까요? 그들은 이를 "준분할"이라고 부릅니다. 숫자 3이 하나 더 있어서, 이를 두 개의 서로 다른 더미에 사용할 수 있다고 상상해 보십시오.
그들은 특정 범위의 숫자들에 대해 이 버전의 퍼즐을 항상 해결할 수 있음을 증명했으며, 이때 숫자 3(구체적으로 $3^t$ )이 두 번 사용됩니다. 이는 더 어려운 원래의 문제를 이해하기 위한 유용한 디딤돌이 되었습니다.

얼마나 많은 방법이 있는가?

이 논문에서 가장 흥고한 부분 중 하나는 숫자를 그룹화하는 다양한 방법의 수를 세는 것입니다.

어떤 숫자들(1, 2, 3, 4 및 기타 많은 숫자들)의 경우, 정확히 한 가지 방법만이 존재합니다. 이는 마치 열쇠가 하나뿐인 자물쇠와 같습니다.
숫자 13과 $3t - 3$ 과 같은 숫자들의 경우, 정확히 두 가지 방법이 존재합니다.
거의 모든 다른 숫자에 대해서는, 그들은 두 가지 이상의 방법이 있을 것이라고 추측합니다.

그들은 또한 만약 어떤 세 숫자(삼중항)가 솔루션에 포함되어 있는지 안다면, 전체 퍼즐을 파악할 수 있다는 특별한 규칙(Proposition 2)을 찾아냈습니다. 이것은 마치 "방 안에 있는 세 명의 베스트 프렌드가 누구인지 안다면, 그 방의 전체적인 사회적 역학 관계를 알 수 있다"는 것과 같습니다.

핵심 요약

저자들이 아직 우주의 모든 숫자에 대해 이 퍼즐을 해결한 것은 아닙니다. 수학적으로 아직 완전히 해소되지 않은 까다로운 숫자들(예: 35, 38, 89, 101)이 여전히 존재합니다. 그러나 그들은 만약 솔루션이 존재하지 않는다면, 그 숫자는 이처럼 매우 구체적이고 희귀한 숫자 중 하나여야 함을 보여주었습니다.

그들은 "3-good partition"이 모든 숫자 $n$ 에 대해 존재한다는 확신을 가지고 있습니다. 그들은 쉬운 실패 사례들을 배제했고, 컴퓨터를 통해 처음 844개의 숫자를 확인했으며, 이 퍼즐이 항상 솔루션을 가진다는 것을 발견했습니다. 이제 미스터리는 우리가 숫자를 그룹화할 수 있느냐 없느냐가 아니라, 정말 큰 숫자들에 대해 얼마나 많은 방법이 있느냐 하는 것입니다. 모든 숫자에 대해 이를 증명하기 위한 여정은 계속되고 있지만, 그 길은 이제 훨씬 더 명확해졌습니다.

기술 요약: 모든 합이 m의 거듭제곱이 되도록 [n]을 크기가 최대 m인 부분집합들로 분할하는 것에 대하여

문제 정의
본 논문은 자연수의 첫 $n$ 개 집합인 $[n] = \{1, \dots, n\}$ 에 대해 정의된 조합론적 분할 문제를 다룬다. 정수 $m > 1$ 과 $n > 0$ 이 주어졌을 때, $[n]$ 의 부분집합이 $m$ -good하다는 것은 그 원소의 개수가 $m$ 이하이고, 원소들의 합이 $m$ 의 거듭제곱(즉, 어떤 정수 $t \ge 0$ 에 대하여 $m^t$ )인 경우를 말한다. $[n]$ 의 분할이 $m$ -good하다는 것은 분할된 모든 부분집합이 $m$ -good한 집합임을 의미한다.

저자들은 이러한 분할의 존재성과 유일성을 조사한다:

$m=2$ 인 경우, 모든 $n$ 에 대하여 유일한 2-good 분할이 존재한다.
$m > 3$ 인 경우, $m$ -good 분할이 존재하지 않는 $n$ 이 무수히 많이 존재한다 (구체적으로 $n = 2(m^t + 1)$ 인 경우).
$m=3$ 인 경우가 주요 연구 대상이며, 모든 $n$ 에 대해 3-good 분할이 존재하는지는 즉각적으로 명확하지 않으며 추측의 대상으로 남아 있다.

방법론
저자들은 구성적 증명, 재귀적 축소, 그리고 계산적 검증을 결합하여 사용한다.

축소 기법 (Reduction Techniques): 핵심 방법론은 더 작은 집합 $[n']$ 의 기지 분할에 특정 부분집합들을 추가하여 $[n]$ 의 분할을 구성하는 "축소"이다. 저자들은 다양한 형태의 $n$ (예: $n = 3t + 3k$ , $n = 3t + 3k + 1$ )에 대한 특정 축소 공식을 정의하여, 작은 $n'$ 에 대한 분할을 바탕으로 $n$ 에 대한 3-good 분할을 구성할 수 있게 한다.
대칭 구간 (Symmetric Intervals): 저자들은 축소를 용이하게 하기 위해 대칭 정수 구간 $[-\ell; \ell]$ 의 분할을 활용한다. 보조정리 1은 이러한 구간이 ( $\ell \equiv 0, 1 \pmod 3$ 일 때) 0을 합으로 하는 삼중항(triplets)을 사용하여 3-good 분할을 가짐을 보여준다.
준분할 (Quasi-Partitions): 표준적인 분할을 구성하기 어려운 경우를 처리하기 위해, 저자들은 3-good 준분할을 도입한다. 이는 $[n]$ 의 모든 수를 정확히 한 번씩 포함하되, 단 하나의 특정 숫자(구체적으로 $3^t$ )만 두 번 포함하는 부분집합들의 가족이다.
재귀 알고리즘 (Recursive Algorithms): 유일성 증명을 위해, 저자들은 가장 큰 자유수 $i$ 의 배치를 결정하는 재귀 알고리즘(Oleg Polubasoff의 것에 기인함)을 활용한다. 만약 $i$ 가 3의 거듭제곱이면 반드시 단일 원소여야 하며, 그렇지 않으면 $3^{j-1} < i < 3^j$ 를 만족하는 $3^j - i$ 와 쌍을 이루어야 한다.

주요 기여 및 결과

존재성 추측 (Conjecture 1): 저자들은 모든 양의 정수 $n$ 에 대해 3-good 분할이 존재한다는 것을 추측한다.
최소 반례의 특징 규명 (Theorem 1): 반례가 존재한다고 가정할 때, 최소 반례 $n$ $n$ 은 다음과 같은 엄격한 조건을 만족해야 함을 증명한다:
- $n = 3^t + 3k + 2$ ( $t > 0$ ).
- $0 \le k < \frac{3^{t-1}-1}{2}$ .
- $k \neq \frac{3^\ell-1}{2}$ (모든 비음수 정수 $\ell < t$ 에 대하여).
- 동치 조건으로, $n \equiv 2 \pmod 3$ , $3k+2 < \frac{3^{t+1}+1}{2}$ , 그리고 $3k+2 \neq \frac{3^{\ell+1}+1}{2}$ 이다.
- 이는 잠재적 반례에 대한 탐색 공간을 크게 좁혀준다.
준분할의 존재성 (Theorem 2): Theorem 1의 조건을 만족하는 모든 $n$ (즉, 잠재적 반례의 형태를 가진 $n$ )에 대하여, 숫자 $3^t$ 가 두 번 포함되는 3-good 준분할이 존재함을 증명한다. 이는 표준 분할이 실패할 수 있는 가장 어려운 경우에서도 장애물이 매우 최소화되어 있음을 시사한다.
유일성 결과 (Theorem 3): 저자들은 특정 범위의 $n$ $n$ 에 대해 3-good 분할의 유일성을 확립한다:
- $n \in \{1, 2, 3, 4\}$ 및 $n$ 이 $3^t - 4, 3^t - 2, 3^t - 1, 3^t, 3^t + 1, 3^t + 2, 3^t + 3, 3^t + 5$ 의 형태인 경우 ( $t \ge 2$ 에 대하여) 유일한 분할이 존재한다.
- $n = 3^t - 3$ 과 $n = 13$ 에 대해서는 정확히 두 개의 3-good 분할이 존재한다.
- 저자들은 (13을 제외한) 다른 모든 $n$ 에 대해 3-good 분할의 개수가 2보다 많을 것이라고 추측한다.
계산적 검증: Dmitry Rybin이 작성한 코드를 사용하여, $n \le 844$ 인 모든 $n$ 에 대해 추측들을 검증하였다.

의의 및 주장
본 논문은 모든 $n$ 에 대한 3-good 분할의 존재성에 관한 최초의 엄밀한 부분적 결과를 제공한다고 주장한다. 잠재적인 최소 반례의 형태를 규명함으로써, 저자들은 문제의 공간을 크게 제한하였다. 준분할의 도입은 중요한 중간 단계 역할을 하며, 표준 분할이 실패할 수 있는 가장 어려운 경우에서도 해결책에 매우 근접한 구조가 존재함을 보여준다.

저자들은 (Oleg Polubasoff가 제안한) 일반화된 축소 방법들이 증명 가능한 범위를 확장하지만, 이 방법들이 Conjecture 1을 모든 $n$ 에 대해 완전히 증명하기에 충분한지는 여전히 미해결 과제로 남아 있음을 인정한다. 본 논문은 일반적인 존재성 문제를 해결했다고 주장하는 것이 아니라, 구조적 틀을 제공하고 추측을 뒷받침하는 강력한 근거를 제시하는 데 목적이 있다.