🧠 고등/올림피아드 사고력

📖 풀이:
핵심: 완전매칭은 $A_1, A_2, A_3$ 을 $B_1, B_2, B_3$ 와 일대일로 짝짓는 방법. 즉 $\{B_1, B_2, B_3\}$ 의 순열 수와 같다. 따라서 $3! = 6$.

📖 풀이:
핵심: 카탈란 수 $C_n = \dfrac{1}{n+1}\binom{2n}{n}$. $n = 4$ 일 때 $C_4 = \dfrac{1}{5}\binom{8}{4} = \dfrac{70}{5} = 14$. 또는 격자경로 ($x$ 축 위에서 $(0,0) \to (4,4)$ 인 단조 경로 중 대각선 아래로 내려가지 않는 것) 해석으로도 같은 값.

📖 풀이:
핵심: 지수 $p = 11$ 이 소수라도 $M_p$ 가 소수임은 보장되지 않는다. $2047 \div 23 = 89$ 이고 $23, 89$ 모두 소수. 즉 $2047 = 23 \cdot 89$. 메르센 소수는 $M_2, M_3, M_5, M_7, M_{13}, \ldots$ 등이며 $M_{11}$ 은 첫 반례.

📖 풀이:
핵심: 첫 시행 앞면이라는 조건 하에 동전 A 일 확률 $P(A \mid H) = \dfrac{P(H \mid A) P(A)}{P(H)} = \dfrac{1 \cdot \tfrac12}{\tfrac12 \cdot 1 + \tfrac12 \cdot \tfrac12} = \dfrac{1/2}{3/4} = \dfrac{2}{3}$. 따라서 두 번째도 앞면일 확률은 $\dfrac{2}{3} \cdot 1 + \dfrac{1}{3} \cdot \dfrac{1}{2} = \dfrac{4 + 1}{6} = \dfrac{5}{6}$.

📖 풀이:
핵심: 어떤 원소도 자기 자리에 있지 않은 순열을 착란순열(derangement) 이라 한다. 포함배제로 $D_n = n! \sum_{k=0}^{n} \dfrac{(-1)^k}{k!}$. $D_4 = 4!\left(1 - 1 + \tfrac12 - \tfrac16 + \tfrac1{24}\right) = 24 \cdot \tfrac{9}{24} = 9$. 전체 순열 $4! = 24$ 이므로 확률 $= \dfrac{9}{24} = \dfrac{3}{8}$.

📖 풀이:
핵심: 코시-슈바르츠 부등식의 엥겔(Engel) 형: $(a + b + c)\left(\dfrac{1}{a} + \dfrac{1}{b} + \dfrac{1}{c}\right) \geq (1 + 1 + 1)^2 = 9$. 따라서 $\dfrac{1}{a} + \dfrac{1}{b} + \dfrac{1}{c} \geq \dfrac{9}{a+b+c} = \dfrac{9}{6} = \dfrac{3}{2}$. 등호는 $a = b = c = 2$ 일 때 성립.

📖 풀이:
핵심 아이디어: $k \cdot k! = (k+1)! - k!$. 망원합(telescoping)으로 $\sum_{k=1}^{n} k \cdot k! = \sum_{k=1}^{n} \big((k+1)! - k!\big) = (n+1)! - 1!$.

귀납 단계: $n=1$이면 $1 \cdot 1! = 1 = 2! - 1$. $n$에서 성립한다고 가정하면 $n+1$항을 더했을 때 $((n+1)! - 1) + (n+1)(n+1)! = (n+2)(n+1)! - 1 = (n+2)! - 1$.

따라서 $n=6$의 값은 $7! - 1 = 5040 - 1 = 5039$.

📖 풀이:
핵심 아이디어: $7$의 거듭제곱의 일의 자리는 주기 $4$로 순환한다.

계산: $7^1 \equiv 7$, $7^2 \equiv 49 \equiv 9$, $7^3 \equiv 7 \cdot 9 = 63 \equiv 3$, $7^4 \equiv 7 \cdot 3 = 21 \equiv 1 \pmod{10}$. 이후 다시 $7, 9, 3, 1$ 반복.

지수 축약: $2026 = 4 \cdot 506 + 2$이므로 $7^{2026} \equiv 7^2 \equiv 9 \pmod{10}$.

📖 풀이:
핵심 아이디어: 사물함 $n$이 토글되는 횟수는 $n$의 양의 약수의 개수 $d(n)$이다. 처음에 닫혀 있었으므로 마지막에 열려 있을 조건은 $d(n)$이 홀수.

약수의 개수가 홀수인 자연수의 특징: 약수는 보통 쌍 $(d, n/d)$로 짝지어지지만, $d = n/d$ 즉 $n$이 완전제곱수일 때만 짝이 안 맞아 홀수 개가 된다.

$1$ 이상 $100$ 이하의 완전제곱수: $1, 4, 9, 16, 25, 36, 49, 64, 81, 100$의 $10$개.

📖 풀이:
핵심 아이디어: 진다는 패배 위치(P-position)를 역추적한다.

돌이 $1$개 남으면 가져갈 수밖에 없고 그 사람이 패. 즉 $n=1$은 P(이동할 차례인 자가 짐).

$n=2$: $1$개 가져가 $n=1$을 상대에게 넘기면 승. W.
$n=3$: $2$개 가져가 $n=1$ 넘기면 승. W.
$n=4$: $1$ 또는 $2$ 어느 쪽이나 $n=2$ 또는 $n=3$(둘 다 W)이 상대에게. P.

패턴: P-position은 $n \equiv 1 \pmod{3}$, 즉 $1, 4, 7, 10, 13, 16, 19, 22, \ldots$

$21 = 3 \cdot 7$이므로 W. 첫 수로 $2$개를 가져가면 $19 \equiv 1 \pmod{3}$를 상대에게 남겨 패배 위치로 만든다.

📖 풀이:
핵심 아이디어(강귀납법): 절단 한 번은 항상 \textbf{조각의 개수를 정확히 1 증가}시킨다.

증명: $n$개 조각 짜리 초콜릿을 분리하는 데 필요한 횟수를 $f(n)$이라 하자. $f(1)=0$. $n \geq 2$일 때, 첫 절단으로 크기 $a$, $b$ ($a+b=n$, $a, b \geq 1$) 두 조각이 생기고 각각 $f(a)$, $f(b)$회의 절단이 필요. 강귀납 가정에서 $f(a)=a-1, f(b)=b-1$이라 가정하면 $f(n) = 1 + (a-1) + (b-1) = n - 1$.

초기 1조각, 매 절단마다 +1이므로 $n$조각 도달엔 항상 $n-1$회. 따라서 최소·최대 모두 $n-1$.

$n=2026 \Rightarrow 2025$회.

📖 풀이:
핵심 아이디어: $30 = 2 \cdot 3 \cdot 5$로 소인수 분해하여 각 소수로의 가분성을 따로 보인다.

인수분해: $n^5 - n = n(n^4 - 1) = n(n^2-1)(n^2+1) = (n-1)\,n\,(n+1)(n^2+1)$.

- $2$의 배수: $(n-1)\,n\,(n+1)$ 중 연속 정수에 항상 짝수.
- $3$의 배수: $n-1, n, n+1$ 중 하나는 $3$의 배수.
- $5$의 배수: 페르마 소정리에서 $n^5 \equiv n \pmod 5$, 즉 $5 \mid n^5 - n$.

$2, 3, 5$가 서로소이므로 $30 \mid n^5 - n$.

$n=7$ 계산: $7^5 = 16807$, $7^5 - 7 = 16800$, $16800 / 30 = 560$.

📖 풀이:
핵심 아이디어: 연결 평면 그래프에 대해 오일러 공식이 성립한다.

오일러 공식: $V - E + F = 2$.

대입: $F = 2 - V + E = 2 - 8 + 15 = 9$.

참고 부등식 검증: 단순 평면 그래프는 $V \geq 3$에서 $E \leq 3V - 6$를 만족해야 한다. $3 \cdot 8 - 6 = 18 \geq 15$이므로 그릴 수 있는 평면 그래프이다.

📖 풀이:
핵심 아이디어: 베이즈 정리(또는 표본 공간 재구성).

표본 공간: 6개의 공에 라벨을 붙인다. 상자 A: $W_1, W_2$ (둘 다 흰), 상자 B: $W_3$(흰), $B_1$(검), 상자 C: $B_2, B_3$.

조건 \textquoteleft 꺼낸 공이 흰색\textquoteright 에 해당하는 공: $W_1, W_2, W_3$ (각 상자 선택 확률 $1/3$, 그 안에서 공 선택은 $1/2$로 균등하므로 세 공의 확률은 모두 같음).

그중 다른 공도 흰색인 경우: $W_1, W_2$ (상자 A에 있을 때, 2개).

구하는 확률 $= \dfrac{2}{3}$.

Bayes 공식 검증: $P(A \mid W) = \dfrac{P(W \mid A) P(A)}{P(W)} = \dfrac{1 \cdot \tfrac{1}{3}}{1 \cdot \tfrac{1}{3} + \tfrac{1}{2} \cdot \tfrac{1}{3} + 0 \cdot \tfrac{1}{3}} = \dfrac{1/3}{1/2} = \dfrac{2}{3}$.

📖 풀이:
핵심 아이디어: 위토프 게임의 \textbf{차가운 위치}(P-position, 이동할 차례인 사람이 짐)는 황금비 $\varphi = \dfrac{1+\sqrt{5}}{2}$를 이용한 \textquoteleft Beatty 수열\textquoteright 로 주어진다.

P-position: $\big(\lfloor k\varphi \rfloor,\, \lfloor k\varphi^2 \rfloor\big)$, $k = 0, 1, 2, \ldots$
- $k=0$: $(0,0)$
- $k=1$: $(1,2)$
- $k=2$: $(3,5)$
- $k=3$: $(4,7)$
- $k=4$: $(6,10)$
- $k=5$: $(8,13)$

$(5, 8)$은 위 목록에 없으므로 W(이동자 승리). P-position에 도달하는 수를 찾자.

- 둘째 무더기에서 $5$ 가져가 $(5, 3)$: 정렬하면 $(3, 5)$로 P. ✓
- 양쪽에서 $1$씩 가져가 $(4, 7)$: P. ✓ (이 선택지는 보기에 없음)

따라서 답은 ②.

📖 풀이:
핵심 아이디어: 큰 $n$에서 $n!$이 $12$를 나누는 점을 이용해 합을 절단한다.

$4! = 24 = 12 \cdot 2$이므로 $12 \mid 4!$. $n \geq 4$이면 $n!$은 $4!$을 인수로 가져 $12 \mid n!$, 따라서 $n! \equiv 0 \pmod{12}$.

그러므로 $S \equiv 1! + 2! + 3! \pmod{12}$.

계산: $1! + 2! + 3! = 1 + 2 + 6 = 9$.

결론: $S \equiv 9 \pmod{12}$.

📖 풀이:
핵심 아이디어: 원에 내접하는 사각형에 대해 \textbf{톨레미(Ptolemy) 정리}.

톨레미 정리: 원에 내접하는 사각형 $ABCD$에서 $$AC \cdot BD = AB \cdot CD + BC \cdot DA.$$

증명 스케치: 대각선 $BD$ 위의 점 $K$를 $\angle BAK = \angle CAD$가 되도록 잡으면 $\triangle ABK \sim \triangle ACD$, $\triangle AKD \sim \triangle ABC$가 되고 (원주각 일치), 각 닮음에서 $BK \cdot AC = AB \cdot CD$, $KD \cdot AC = AD \cdot BC$. 두 식을 더하면 좌변이 $(BK+KD) \cdot AC = BD \cdot AC$.

대입: $AC \cdot BD = 3 \cdot 5 + 4 \cdot 6 = 15 + 24 = 39$.

📖 풀이:
핵심 아이디어: 정삼각형 분할 + 비둘기집 원리. 세 변의 중점을 연결하면 한 변 $\frac{1}{2}$ 인 작은 정삼각형 $4$개로 분할된다. 점 $5$개를 영역 $4$개에 배치하므로 비둘기집 원리에 의해 어느 한 작은 정삼각형에 적어도 $2$개의 점이 들어간다. 한 변 $\frac{1}{2}$인 정삼각형 내부 두 점 사이의 최대 거리는 그 변의 길이 $\frac{1}{2}$이다. 따라서 거리가 $\frac{1}{2}$ 이하인 두 점이 반드시 존재한다.

📖 풀이:
핵심: 포함배제 원리. $A_k$를 '$k$의 배수인 수의 집합'이라 하면 $|A_2|=50,\ |A_3|=33,\ |A_5|=20,\ |A_6|=16,\ |A_{10}|=10,\ |A_{15}|=6,\ |A_{30}|=3.$ $|A_2 \cup A_3 \cup A_5| = 50+33+20-16-10-6+3 = 74.$ 따라서 어느 것으로도 나누어떨어지지 않는 수의 개수 $= 100 - 74 = 26.$

📖 풀이:
핵심 아이디어: 적절한 치환으로 코시형 함수방정식으로 환원. $g(x) = f(x) - \frac{x^2}{2}$로 놓으면 $g(x+y) = f(x+y) - \frac{(x+y)^2}{2} = f(x)+f(y)+xy - \frac{x^2+2xy+y^2}{2} = g(x) + g(y).$ $f$가 다항함수이므로 $g$도 다항이며 코시방정식의 다항해는 $g(x) = cx$. $f(1) = \frac{1}{2} + c = 1$ 에서 $c = \frac{1}{2}.$ 따라서 $f(x) = \frac{x(x+1)}{2}$ 이고 $f(10) = \frac{10 \cdot 11}{2} = 55.$

📖 풀이:
핵심: 유한 잉여계에서 제곱표 작성. $x = 0,1,2,3,4,5,6$ 에 대해 $x^2 \pmod 7$ 은 차례로 $0, 1, 4, 2, 2, 4, 1.$ $x^2 \equiv 2 \pmod 7$ 인 해는 $x = 3$ 과 $x = 4$ 의 두 개. 합 $= 3 + 4 = 7.$ 일반적으로 $x_0$ 가 해이면 $-x_0 \equiv p - x_0$ 도 해이므로 해의 합은 $\equiv 0 \pmod p$ 임에 주목.

📖 풀이:
핵심 아이디어: 색칠 불변량. 체스판을 흑백으로 칠하면 두 대각 모서리는 동색(예: 둘 다 흰색). 따라서 남은 칸의 색 구성은 흰 $30$, 검 $32$. 한편 $1 \times 2$ 도미노는 인접한 두 칸을 덮으므로 항상 흰 $1$, 검 $1$ 을 덮는다. $31$ 개의 도미노로 모두 덮으려면 흰 $31$ + 검 $31$ 이 필요. 모순. 따라서 불가능.

📖 풀이:
핵심: '수들의 합의 패리티'가 불변. $|a-b|$ 와 $a+b$ 는 같은 패리티를 가지므로 ($\because |a-b| = a+b - 2\min(a,b)$), 한 번의 조작 후 칠판 위 수들의 합 $S$ 의 패리티는 바뀌지 않는다. 초기 합 $S_0 = 1+2+\cdots+100 = \frac{100 \cdot 101}{2} = 5050$ 으로 짝수. 따라서 마지막 남은 한 수도 짝수.

📖 풀이:
핵심: 본질적 표현 찾기 + 부호/순서 대칭. $2025 = 3^4 \cdot 5^2 = 45^2$. 본질적 분해: $2025 = 0^2 + 45^2 = 27^2 + 36^2$ ($27^2 + 36^2 = 729 + 1296 = 2025$). 다른 분해는 $0 \leq a \leq b$ 의 범위에서 $b$ 를 $45$ 이하로 차례 검증하여 없음을 확인. 이제 부호와 순서: $(0, \pm 45), (\pm 45, 0)$ → $4$개. $(\pm 27, \pm 36), (\pm 36, \pm 27)$ → $8$개. 총 $12$개. (페르마 두 제곱수 정리 $r_2(n)=4(d_1(n)-d_3(n))$ 로도 $4(9-6)=12$.)

📖 풀이:
핵심 아이디어: '도달 거리'가 고정되어 패리티가 결정됨. 종착 칸은 $(8,8)$ 로, 여기 도달한 다음 사람은 움직일 수 없어 진다. 즉 $(8,8)$ 에 도착하는 사람이 이긴다. $(1,1) \to (8,8)$ 까지는 오른쪽 $7$ 번 + 위 $7$ 번 = 총 $14$ 번의 이동이 강제된다 (어떤 경로든 합이 일정). 첫 번째 사람은 $1, 3, \ldots, 13$ 번째 이동 ($7$ 번), 두 번째 사람은 $2, 4, \ldots, 14$ 번째 이동 ($7$ 번). 따라서 $14$ 번째 (마지막) 이동은 항상 두 번째 사람이 두며 $(8,8)$ 에 도달. 결과: 두 번째 사람이 항상 필승.