Experimenting with Permutation Wordle

Each language version is independently generated for its own context, not a direct translation.

1. 게임은 무엇인가요? (비밀 번호 자물쇠)

상상해 보세요. 누군가 1 번부터 n 번까지 번호가 붙은 공들을 일렬로 나열해 두었습니다. 하지만 그 순서를 비밀로 하고 있습니다.
당신의 임무는 이 비밀 순서를 맞추는 것입니다.

한 번 시도할 때마다: 당신이 추측한 순서를 말하면, 주인은 "이 번호들은 제자리에 있어요"라고 알려줍니다. (예: "2 번은 맞았어요, 4 번도 맞았어요" 등)
목표: 모든 번호가 제자리에 오도록 최소한의 시도 만에 비밀 순서를 찾아내는 것입니다.

이 게임은 유명한 '워드들 (Wordle)' 게임의 숫자 버전이라고 생각하시면 됩니다.

2. 문제와 가설 (마법사의 제안)

이 게임에서 가장 효율적인 방법은 무엇일까요?
저자 (오로라 히블리) 는 Samuel Kutin 과 Lawren Smithline 이 제안한 **'순환 이동 (Cyclic Shift)'**이라는 전략을 연구했습니다.

순환 이동 전략의 비유:
당신이 추측한 번호 중 틀린 것들이 있다면, 그 틀린 번호들을 오른쪽으로 하나씩 밀어내세요. (마치 자석으로 자물쇠의 톱니를 하나씩 밀어서 새로운 조합을 만드는 것처럼요.)
- 예: 1 2 3 4 5라고 추측했는데 2 만 맞았다면, 틀린 1, 3, 4, 5 를 오른쪽으로 한 칸씩 밀어서 5 2 1 3 4로 바꿉니다.

이 두 사람은 **"이 '오른쪽 밀기' 전략이 모든 경우에서 가장 빠르고 좋은 전략이다"**라고 주장했습니다. 우리는 이 주장이 사실인지 확인하려고 합니다.

3. 연구 방법 (수학자 vs 실험실)

저자는 이 가설을 증명하기 위해 두 가지 방법을 썼습니다.

① 컴퓨터 실험 (실험실 테스트)

컴퓨터 (Maple 프로그램) 를 이용해 수많은 경우의 수를 시뮬레이션했습니다.

결과: 컴퓨터가 계산해 보니, 5 번, 6 번, 7 번까지의 짧은 게임에서는 '오른쪽 밀기' 전략이 정말로 가장 잘 작동했습니다. 다른 어떤 복잡한 방법보다도 빨리 정답을 찾았습니다.

② 수학적 증명 (이론적 분석)

컴퓨터는 무한히 계산할 수 없기 때문에, 수학적으로 엄밀하게 증명해야 합니다. 저자는 **'생성 함수 (Generating Function)'**라는 수학적 도구를 사용했습니다.

비유: 이 도구는 "이 전략을 쓰면 1 번 만에 맞는 경우는 몇 개, 2 번 만에 맞는 경우는 몇 개, 3 번 만에 맞는 경우는 몇 개일까?"를 **다항식 (방정식)**으로 나타내는 것입니다.
- $x^1$ 의 계수: 1 번 만에 맞는 경우의 수
- $x^2$ 의 계수: 2 번 만에 맞는 경우의 수
- $x^3$ 의 계수: 3 번 만에 맞는 경우의 수

4. 주요 발견 (3 번 시도까지의 승리)

이 논문은 특히 3 번의 시도 안에 끝나는 게임에 집중했습니다.

1 번과 2 번 시도: 어떤 전략을 쓰든 1 번이나 2 번 만에 맞추는 경우의 수는 거의 비슷했습니다. (모두가 똑같은 확률로 시작하기 때문입니다.)
3 번 시도 (핵심): 여기서 차이가 나타났습니다.
- '오른쪽 밀기 (Cyclic Shift)' 전략은 3 번 만에 정답을 맞출 수 있는 경우의 수 (계수) 가 가장 많았습니다.
- 다른 전략들 (예: 왼쪽으로 밀거나, 무작위로 섞는 등) 은 3 번 만에 맞추는 경우가 더 적었습니다.

결론: 3 번 시도 이내로 게임을 끝내야 한다면, '오른쪽 밀기' 전략이 압도적으로 최고라는 것을 수학적으로 증명했습니다.

5. 왜 다른 전략은 안 될까요? (비유: 자석의 방향)

논문의 마지막 부분에서는 왜 다른 전략들은 '오른쪽 밀기'보다 못 하는지 설명합니다.

오른쪽 밀기: 모든 톱니가 일정한 방향으로 움직이므로, 자물쇠의 내부 구조가 예측 가능하게 변합니다.
다른 전략들: 어떤 톱니는 오른쪽으로 가고, 어떤 톱니는 왼쪽으로 가거나 제자리에 멈추기도 합니다. 이렇게 하면 자물쇠 내부의 '틀린 조합'들이 서로 겹치거나, 다시 원래 상태로 돌아가는 **지루한 루프 (無限 고리)**에 빠질 위험이 생깁니다.
- 즉, '오른쪽 밀기'는 실수를 최대한 빨리 수정하고 새로운 정보를 얻지만, 다른 전략들은 같은 실수를 반복하거나 정보를 낭비할 가능성이 더 큽니다.

6. 요약 및 미래 (아직 해결되지 않은 미스터리)

이 논문의 성과: "비밀 번호 워들" 게임에서 3 번 시도 이내로 끝나는 경우, '오른쪽으로 밀기' 전략이 가장 최적임을 증명했습니다.
남은 과제: 하지만 게임이 4 번, 5 번 이상 걸리는 더 긴 경우에는 이 전략이 여전히 최선인지 아직 확실하지 않습니다. 수학적으로 더 복잡한 분석이 필요하며, 저자는 앞으로 이 부분을 더 연구할 계획입니다.

한 줄 요약

"비밀 번호를 맞출 때, 틀린 것들을 오른쪽으로 하나씩 밀어내는 단순한 방법이, 3 번 안에 끝내는 게임에서는 가장 똑똑하고 빠른 마법입니다."

Each language version is independently generated for its own context, not a direct translation.

논문 요약: 순열 워들 (Permutation Wordle) 과 순환 시프트 전략의 최적성 연구

1. 문제 정의 (Problem)

이 논문은 **순열 워들 (Permutation Wordle)**이라는 추측 게임의 최적 전략을 연구합니다.

게임 규칙: 게임 마스터는 $n$ 개의 객체 (1 부터 $n$ 까지) 를 비밀스럽게 순서대로 배열합니다 (비밀 순열). 플레이어는 $1 $부터$ n$까지의 순열을 추측합니다. 매 라운드마다 게임 마스터는 추측한 순열 중 **정확한 위치에 있는 원소의 개수 (또는 위치)**를 피드백으로 제공합니다. 게임은 모든 원소가 올바른 위치에 있을 때 종료됩니다.
목표: 비밀 순열을 최대한 적은 추측 횟수로 찾아내는 최적 전략을 찾는 것입니다.
Kutin-Smithline 추측: Samuel Kutin 과 Lawren Smithline 은 "잘못된 모든 원소를 한 칸씩 오른쪽으로 순환 이동 (Cyclic Shift) 시키는 전략"이 모든 전략 중 최적일 것이라고 추측했습니다. 즉, $r$ 번의 추측 내 성공 확률이 최대이거나, 평균 추측 횟수가 최소가 된다는 것입니다.

2. 연구 방법론 (Methodology)

저자는 이 추측을 검증하기 위해 다음과 같은 수학적 및 실험적 접근법을 사용했습니다.

전략의 형식화 (Formalization):
- 전략 $S$ 를 $S = [s_1, s_2, \dots, s_n]$ 으로 정의하며, $s_i$ 는 길이 $i$ 의 순열입니다.
- $r$ 번째 추측 ( $\gamma_r$ ) 에서 올바른 위치 집합 $J_r$ 은 고정하고, 틀린 위치 집합 $I_r$ 에 포함된 원소들을 전략 성분 $S[|I_r|]$ 에 따라 재배열하여 다음 추측 $\gamma_{r+1}$ 을 생성합니다.
- 순환 시프트 (Cyclic Shift, CS): $S[n] = [2, 3, \dots, n, 1]$ 로 정의됩니다. (오른쪽 시프트)
- 유도적 구성 (Inductive Construction): $n$ 보다 작은 길이의 부분 순열에 대해서는 이미 검증된 최적 전략 (보통 CS) 을 사용하고, $n$ 번째 단계에서만 특정 순열 $S[n]$ 을 적용하는 전략을 고려했습니다.
- 제약 조건: 무한 루프를 방지하고 계산을 단순화하기 위해 전략 성분은 **순환 순열 (Cyclic Permutations)**로 제한했습니다.
실험적 분석:
- Maple 소프트웨어를 사용하여 $n$ 이 작은 경우 ( $n \le 8$ ) 에 대해 모든 가능한 비밀 순열에 대한 게임 시뮬레이션을 수행했습니다.
- 각 전략의 평균 추측 횟수를 계산하고, Kutin-Smithline 추측을 검증했습니다.
생성 함수 (Generating Functions) 분석:
- 전략 $S$ 의 성능을 나타내는 생성 함수 $f_S(x) = \sum a_r x^r$ 를 정의했습니다. 여기서 $a_r$ 은 정확히 $r$ 번의 추측으로 비밀 순열을 맞출 수 있는 순열의 개수입니다.
- 최적성을 증명하기 위해 $x^1, x^2, x^3$ 의 계수 (즉, 1 회, 2 회, 3 회 추측으로 해결 가능한 경우의 수) 를 정량적으로 분석하고 비교했습니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

가. 실험적 검증 (Experimental Verification)

Maple 을 통해 $n \le 7$ (순환 전략) 및 $n \le 5$ (부정합 전략, deranged strategies) 에서 Kutin-Smithline 추측이 성립함을 확인했습니다.
유도적으로 구성된 전략에 대해서는 $n \le 8$ 까지 검증되었습니다.

나. 1 회 및 2 회 추측에서의 성능 (Linear and Quadratic Coefficients)

1 회 추측 ( $x^1$ ): 모든 전략에 대해 $a_1 = 1$ 입니다 (단, 첫 추측이 바로 정답인 경우).
2 회 추측 ( $x^2$ ): 모든 전략에 대해 $a_2 = A(n, 1)$ (오일러 수) 로 동일합니다. 이는 첫 추측 후 틀린 원소들의 집합 크기만 중요하고, 구체적인 순열의 순서는 2 회 추측 내 해결 가능성에는 영향을 주지 않기 때문입니다.

다. 3 회 추측에서의 성능 및 최적성 증명 (Cubic Coefficients - Main Result)
이 논문은 3 회 추측으로 게임이 종료되는 경우에 대해 순환 시프트 (CS) 가 유도적 전략 중 최적임을 수학적으로 증명했습니다.

생성 함수의 3 차 계수 비교:
- $a_3 = [x^3]f_S(x)$ 는 3 회 추측으로 해결 가능한 순열의 수입니다.
- 저자는 $a_3$ 을 $\rho_S(\pi) = i$ (첫 번째 올바른 원소가 $i$ 번째 추측에서 발견된 경우) 로 분류하여 분석했습니다.
- $\rho_S(\pi) = 1$ 과 $\rho_S(\pi) = 3$ 인 경우의 수는 모든 유도적 전략에서 동일함을 보였습니다.
- 따라서 $\rho_S(\pi) = 2$ 인 경우의 수가 전략 간 차이를 결정합니다.
주요 정리 (Theorems):
- Theorem 4.7: 순환 시프트 전략 (CS) 의 경우, 3 회 추측으로 해결 가능한 경우 중 첫 번째 정답이 2 번째 추측에서 나온 경우의 수는 $2^n - 2n - 2$입니다.
- Theorem 4.8: 임의의 유도적 전략 $S$ $S$ (CS 가 아닌 경우) 에 대해서는 해당 경우의 수가 CS 보다 엄격히 작음을 증명했습니다.
  - 이유: CS 가 아닌 전략은 특정 구조적 제약 (인접한 원소 쌍의 부재 등) 으로 인해 유효한 $J_2$ (2 번째 추측에서의 올바른 위치 집합) 의 조합이 CS 보다 적게 발생합니다.
- Theorem 4.9: 따라서 모든 유도적 전략 $S$ 에 대해 $[x^3]f_{CS}(x) > [x^3]f_S(x)$ 가 성립합니다. 즉, CS 는 3 회 추측 내 해결 가능한 순열의 수가 가장 많습니다.
최악의 경우 분석:
- 반대로, 왼쪽 순환 시프트 (CSL) 전략이 유도적 전략 중 가장 비효율적임을 보였습니다.
- CSL 의 3 차 계수는 $L_n - n - 1$ (Lucas 수 관련) 로 표현되며, 이는 다른 모든 유도적 전략보다 작습니다.

4. 의의 및 한계 (Significance & Limitations)

의의:
- Kutin-Smithline 의 추측을 3 회 추측 이내로 종료되는 게임에 대해 엄밀하게 증명했습니다.
- 생성 함수의 계수를 분석하여 전략의 미세한 성능 차이를 정량화하는 새로운 수학적 프레임워크를 제시했습니다.
- 순열 워들 게임에서 순환 이동 (Cyclic Shift) 전략이 왜 효율적인지에 대한 구조적 이유 (특히 2 번째 추측 단계에서의 정보 획득 효율성) 를 규명했습니다.
한계 및 향후 과제:
- 현재 결과는 3 회 추측 이내의 게임에 국한되어 있습니다. 4 회 이상 걸리는 게임에 대해서는 생성 함수의 고차 계수 분석이 복잡해지며, 실험적 관찰이 고차 항으로 확장되지 않을 수 있어 추가적인 정교한 접근이 필요합니다.
- 전략 성분을 순환 순열로 제한했습니다. 일반적인 부정합 (Derangement) 이나 임의의 순열을 허용할 경우 결과가 달라질 수 있습니다.
- 전략이 게임 중간에 동적으로 변경될 수 있다는 가정은 배제되었습니다.

결론

이 논문은 순열 워들 게임에서 "잘못된 원소를 오른쪽으로 한 칸씩 밀어내는 순환 시프트 전략"이 3 회 이내의 추측으로 게임을 종료하는 모든 경우에서 최적임을 수학적으로 증명했습니다. 이는 생성 함수의 계수 분석을 통해 전략의 성능을 정량화하고, 유도적 구성을 통해 최적성을 입증한 중요한 결과입니다.