본문으로 바로 이동 / Skip to content
MathIsland
한EN
전체 목차/100개의 문

n² · 100개의 문

100개의 문

복도에 닫힌 문 100개가 있습니다. 1번 사람은 모든 문을, 2번 사람은 2의 배수 문을, 3번 사람은 3의 배수 문을 여닫아요. 100번 사람까지 지나가면, 어떤 문이 열려 있을까요?

100명이 차례로 지나간 뒤, 열려 있는 문은 몇 개일까

먼저 직접 생각해 보세요

먼저 결과를 예상해 보세요. 값을 하나씩 바꾸면서 예상과 무엇이 다른지 살펴봅시다.

문 100개가 전부 닫혀 있습니다. 버튼을 눌러 사람을 한 명씩 보내 보세요.

아직 아무도 지나가지 않았어요.지금 열린 문 0개
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
열림 닫힘 방금 여닫은 문

생각을 정리한 뒤 해설 읽기

문의 운명은 몇 번 만져졌는가로 갈린다.

이 질문이 왜 필요할까요?

100개의 문 문제는 '로커 문제'라는 이름으로도 불리는 수학 퍼즐의 고전입니다. 규칙은 초등학생도 아는 배수뿐인데, 결과는 아무도 바로 못 맞혀요.

이 문제의 진짜 얼굴은 여닫기가 아니라 세기입니다. 문 n을 만지는 사람은 n의 약수 번호를 가진 사람들뿐이에요. 그래서 문의 운명은 약수 개수의 홀짝으로 번역됩니다.

결과보다 번역이 남는 문제예요. '움직임의 문제'를 '개수의 문제'로 바꾸는 순간 답이 저절로 나옵니다. 복잡한 과정을 구조 하나로 압축하는 이 감각이 수학적 사고의 핵심이에요.

같은 생각을 다른 말로 읽어 봅시다

문을 여닫는 회차를 세는 일은 그 문 번호의 약수를 세는 일입니다. 최종 상태를 알려면 모든 행동을 따라가기보다 여닫은 횟수가 짝수인지 홀수인지 보면 됩니다.

예를 하나 더 따라가 봅시다

12번 문은 1, 2, 3, 4, 6, 12회차에 바뀝니다. 약수는 1과 12, 2와 6, 3과 4처럼 짝을 이룹니다. 반면 제곱수에서는 가운데 약수가 자기 자신과 짝이 됩니다.

문을 잊고, 만지는 사람을 세라.

문 n 앞에 서는 사람은 n을 나눠떨어뜨리는 번호의 사람들, 즉 n의 약수들입니다. 100명의 행진이라는 복잡한 과정이 '약수 개수'라는 정적인 구조로 압축돼요.

짝수 번은 원위치, 홀수 번만 흔적을 남긴다.

열고 닫으면 없던 일이 됩니다. 만진 횟수가 짝수면 문은 처음 그대로예요. 홀수 번 만져진 문, 즉 약수가 홀수 개인 문만 열린 채 남습니다. 그게 바로 제곱수예요.

이제 정의와 조건을 함께 읽습니다

여기서 지킬 조건

처음에는 모두 닫혀 있고, 매 회차 해당 번호의 배수인 문만 한 번씩 바꾼다는 규칙을 사용합니다.

실험에서 본 것을 수식의 언어로 옮겨 봅시다. 열쇠는 '문 n을 만지는 사람 = n의 약수'라는 번역 하나입니다.

공식 해부 — 여닫기 문제가 약수 세기 문제로 번역된다

⇢ 의

번역 (만지는 사람 세기)

k번 사람이 문 n을 만지는 조건은 'n이 k의 배수', 곧 'k가 n의 약수'입니다. 움직임이 개수로 바뀌는 순간이에요.

약수의 짝짓기

약수 d를 찾으면 n÷d도 약수입니다. 약수는 이렇게 둘씩 짝을 이뤄요. 그래서 약수 개수는 보통 짝수입니다.

짝 없는 하나

제곱수에서는 √n이 자기 자신과 짝이 됩니다(4×4=16). 짝 없는 약수 하나 때문에 개수가 홀수가 되고, 그 문만 열린 채 남아요.

여기서 한 번 더 구분해 볼까요?

많은 사람이 만지는 문일수록 열려 있을 것이다.

몇 번 만졌는지는 중요하지 않습니다. 홀수 번인지 짝수 번인지만 중요해요. 닫힌 문은 짝수 번 만지면 도로 닫히고, 홀수 번 만져야 열린 채 남습니다.

약수는 언제나 둘씩 짝을 이룬다.

거의 그렇습니다. 12의 약수는 1×12, 2×6, 3×4로 짝이 맞아요. 하지만 16은 4×4에서 4가 자기 자신과 짝이 됩니다. 제곱수만 이렇게 짝 없는 약수를 하나 갖고, 그래서 약수 개수가 홀수가 돼요.

다른 질문에서는 어떻게 쓰일까요?

면접과 알고리즘 수업의 고전

로커 문제라는 이름으로 코딩 면접과 알고리즘 수업에 단골로 등장합니다. 시뮬레이션 없이 구조로 답하는 사람을 가려내는 문제예요.

패리티 비트 — 홀짝이 오류를 잡는다

컴퓨터 통신은 데이터에 홀짝 검사 비트 하나를 붙여 전송 오류를 잡아냅니다. '횟수는 잊고 홀짝만 본다'는 오늘의 사고가 그대로 쓰여요.

약수 개수의 공식

n을 소인수분해하면 약수 개수를 곱셈으로 셀 수 있습니다. 12 = 2²×3이면 (2+1)×(1+1) = 6개. 문 하나하나 세지 않고 구조로 세는 법이에요.

전등 스위치 퍼즐들

여러 사람이 스위치를 번갈아 누르는 퍼즐은 대부분 홀짝 논증 하나로 풀립니다. 과정이 아무리 길어도 남는 것은 홀짝뿐이에요.

이번에는 내 말로 설명해 보세요

내 말로 설명해 보기

문 번호의 약수와 그 문을 건드리는 회차를 연결해 보세요.

생각한 뒤 설명 확인하기

k회차에 n번 문을 건드린다는 것은 n이 k의 배수라는 뜻입니다. 곧 k가 n의 약수라는 말과 같습니다.

계산과 개념을 문제로 확인하기 (4)

문제 완료 0 / 4

1. 문 n을 만지는 사람 수는 무엇과 같을까요?

2. 100번 사람까지 다 지나간 뒤, 문 49는 어떻게 되어 있을까요?

3. 문이 1,000개, 사람이 1,000명이라면 마지막에 열려 있는 문은 몇 개일까요?

개

4. 제곱수만 약수 개수가 홀수인 이유는 무엇일까요?

다음에는 어떤 질문을 해볼까요?

이전 개념

2ⁿ−1

하노이 탑

앞 문제가 '쪼개기'였다면, 이번 문제는 '번역하기' — 문제해결의 두 번째 무기다.

← 하노이 탑 실험실

다음 개념으로 연결

gcd

약수와 배수

문의 운명을 가른 약수를 정면으로 배우는 실험실 — 나눠떨어짐의 리듬이 이어진다.

약수와 배수 실험실로 이동 →

관련 실험실

p

소수

소인수분해가 약수 개수의 공식을 만든다 — 문을 세지 않고 세는 법.

소수 실험실로 이동 →

관련 실험실

√

제곱근

짝 없는 약수 √n의 정체 — 제곱수와 제곱근의 관계가 여기 있다.

제곱근 실험실로 이동 →