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

📖 풀이:
핵심: P-위치(차례인 사람이 지는 위치) 분류. $n=0$은 L. 어떤 위치에서 $-1,-3,-4$ 중 하나로 L에 보낼 수 있으면 W, 모든 이동이 W로만 가면 L. 계산하면 L은 $n \equiv 0$ 또는 $2 \pmod 7$. (예: $0,2,7,9,14,16,\dots$) $2026 = 7\cdot289 + 3$이므로 $2026 \equiv 3$, 즉 L이 아니라 W. 선공이 적절히 가져가 상대를 L 위치로 보낼 수 있어 선공 승.

📖 풀이:
핵심: 픽의 정리 $A = I + \dfrac{B}{2} - 1$. 대입하면 $A = 10 + \dfrac{12}{2} - 1 = 10 + 6 - 1 = 15$. 격자점 다각형의 넓이를 내부점과 경계점 개수만으로 정확히 준다.

📖 풀이:
핵심: 우변의 $2xy$ 항을 보고 이차형 $f(x) = x^2 + cx$를 시도(치환). 그러면 $f(x+y) = (x+y)^2 + c(x+y) = x^2 + 2xy + y^2 + cx + cy = f(x) + f(y) + 2xy$로 항등식이 성립. $f(1) = 1 + c = 3 \Rightarrow c = 2$, 즉 $f(x) = x^2 + 2x$. 따라서 $f(4) = 16 + 8 = 24$. (또는 $g(x)=f(x)-x^2$로 두면 $g$가 코시 가법함수가 되어 $g(x)=cx$.)

📖 풀이:
핵심: '카드'가 아니라 '빨간 면'을 세는 조건부확률(베르트랑 상자). 빨간 면은 모두 3개: RR 카드의 두 면, RB 카드의 한 면. 보인 빨간 면이 이 셋 중 무엇이든 동등하게 가능하므로, 그 면이 RR 카드일 확률은 $\dfrac{2}{3}$. 직관적으로 '$1/2$'로 답하기 쉽지만, RR 카드는 빨간 면을 보일 기회가 두 배라 갱신이 필요하다.

📖 풀이:
핵심: 교란순열(완전순열) 수 $D_n$을 포함배제로. $D_n = n!\sum_{k=0}^{n}\dfrac{(-1)^k}{k!}$. $D_4 = 24\left(1 - 1 + \tfrac{1}{2} - \tfrac{1}{6} + \tfrac{1}{24}\right) = 24\cdot\tfrac{9}{24} = 9$. 전체 경우는 $4! = 24$이므로 확률 $\dfrac{9}{24} = \dfrac{3}{8}$.

📖 풀이:
핵심: 끝의 $0$ 개수는 $10 = 2\times5$에서 더 부족한 소인수 $5$의 지수와 같다(2는 항상 더 많다). 르장드르 공식으로 $100!$ 속 $5$의 지수 $= \left\lfloor\dfrac{100}{5}\right\rfloor + \left\lfloor\dfrac{100}{25}\right\rfloor = 20 + 4 = 24$. ($125 > 100$이라 거기서 멈춤.)

📖 풀이:
핵심: 칸의 색이 이동마다 반전되는 패리티 불변량. 나이트가 한 번 움직이면 색이 흑↔백으로 바뀐다. 출발 칸과 도착 칸이 같으면 색도 같으므로, 색이 짝수 번 바뀌어야 한다. 즉 닫힌 경로의 이동 횟수는 항상 짝수.

📖 풀이:
핵심 아이디어: 악수의 총 횟수를 두 번 센다(이중계산). 각 악수는 두 사람의 악수 횟수에 각각 1씩 기여하므로, 모든 사람의 악수 횟수의 합 $= 2\times(\text{악수의 수})$ 로 짝수다. 이 합을 \"짝수 번 악수한 사람들의 합\"과 \"홀수 번 악수한 사람들의 합\"으로 나누면, 앞부분은 짝수이므로 뒷부분도 짝수여야 한다. 홀수들의 합이 짝수이려면 그 항의 개수가 짝수여야 하므로, 홀수 번 악수한 사람의 수는 항상 짝수다(악수 보조정리).

📖 풀이:
핵심: 전체 경로에서 금지점을 지나는 경로를 뺀다(여사건·이중계산). 전체 경로 수는 $\binom{8}{4}=70$. 점 $(2,2)$ 를 지나는 경로는 $(0,0)\to(2,2)$ 가 $\binom{4}{2}=6$ 가지, $(2,2)\to(4,4)$ 가 $\binom{4}{2}=6$ 가지이므로 $6\times 6=36$. 따라서 $(2,2)$ 를 피하는 경로는 $70-36=34$.

📖 풀이:
핵심: 비둘기집 원리. 공집합이 아닌 부분집합은 $2^{10}-1=1023$ 개. 어떤 부분집합의 합도 가장 큰 $10$ 개 $91+92+\cdots+100=955$ 를 넘지 못하므로, 가능한 합은 많아야 $955$ 가지(비둘기 구멍). 부분집합($1023$ 마리) 이 합의 가짓수($\le 955$)보다 많으므로, 합이 같은 두 부분집합이 존재한다. 겹치는 공통 원소를 제거하면 서로소이면서 합이 같은 두 부분집합도 얻는다.

📖 풀이:
핵심: 보존되는 곱(불변량)을 찾는다. $1+(a+b+ab)=(1+a)(1+b)$ 이므로, 칠판의 모든 수 $x_i$ 에 대해 $\prod(1+x_i)$ 는 연산을 해도 변하지 않는다. 처음 값은 $(1+1)(1+2)(1+3)(1+4)(1+5)=2\cdot3\cdot4\cdot5\cdot6=720$. 마지막 한 수 $N$ 에 대해 $1+N=720$ 이므로 $N=719$. 어떤 순서로 지워도 답은 같다.

📖 풀이:
핵심: 모듈러 분석으로 경우를 한정한다. $(1,1):3-2=1$, $(2,3):9-8=1$ 은 해다. $y\ge2$ 이면 $3^x\equiv1\pmod4$ 이므로 $x$ 는 짝수, $x=2k$. 그러면 $2^y=3^{2k}-1=(3^k-1)(3^k+1)$. 두 인수는 차가 $2$ 이면서 모두 $2$ 의 거듭제곱이어야 하므로 $\{2,4\}$, 즉 $3^k=3\Rightarrow k=1,\;x=2,\;y=3$. $y=1$ 이면 $3^x=3\Rightarrow x=1$. 따라서 해는 $(1,1),(2,3)$ 두 개뿐이다.

📖 풀이:
핵심: 마지막 글자로 경우를 나눠 점화식을 세운다. 길이 $n$ 인 조건 만족 문자열 수를 $a_n$ 이라 하면, 끝이 $0$ 이면 앞 $n-1$ 자리는 자유($a_{n-1}$), 끝이 $1$ 이면 그 앞은 반드시 $0$ 이고 그 앞 $n-2$ 자리는 자유($a_{n-2}$). 따라서 $a_n=a_{n-1}+a_{n-2}$ (피보나치형), $a_1=2,a_2=3$. 차례로 $2,3,5,8,13,21,34,55,89,144$ 이므로 $a_{10}=144$.

📖 풀이:
핵심: 오일러 정리. 연결 그래프에서 모든 정점의 차수가 짝수이면 오일러 회로(출발점=도착점)가 존재한다. 차수를 세면 $\deg(V_1)=4$, $\deg(V_2)=\deg(V_3)=\deg(V_4)=\deg(V_5)=2$ 로 모두 짝수이고 그래프는 연결되어 있다. 따라서 홀수 차수 정점이 $0$ 개이므로 오일러 회로가 존재한다(예: $V_1V_2V_3V_1V_4V_5V_1$).

📖 풀이:
핵심: 코시-슈바르츠(또는 제곱평균-산술평균). $(1^2+1^2+1^2)(a^2+b^2+c^2)\ge(a+b+c)^2$ 이므로 $a^2+b^2+c^2\ge\dfrac{(a+b+c)^2}{3}=\dfrac{144}{3}=48$. 등호는 $a=b=c=4$ 일 때 성립하므로 최솟값은 $48$.

📖 풀이:
핵심: 귀납으로 일반항을 구한다. $f(n+1)=f(n)f(1)=3f(n)$ 이고 $f(1)=3$ 이므로 $f(n)=3^n$. 따라서 $f(4)=3^4=81$ (또는 $f(2)=9,\;f(4)=f(2)f(2)=81$).

📖 풀이:
핵심: 베이즈 정리. $P(\text{환자}\mid\text{양성})=\dfrac{P(\text{양성}\mid\text{환자})P(\text{환자})}{P(\text{양성})}$. 분자 $=0.99\times0.01=0.0099$. 분모 $=0.0099+\underbrace{0.05\times0.99}_{0.0495}=0.0594$. 따라서 $\dfrac{0.0099}{0.0594}\approx0.167\approx17\%$. 검사 정확도가 높아도 기저 발병률이 낮으면 거짓양성이 압도해 사후확률이 작다.

📖 풀이:
핵심: 이 게임은 위토프(Wythoff) 게임이다. P-위치(둘 차례에 둔 사람이 지는, 즉 후공 필승)는 $\big(\lfloor n\varphi\rfloor,\lfloor n\varphi^2\rfloor\big)$, $\varphi=\tfrac{1+\sqrt5}{2}$ 로 $(0,0),(1,2),(3,5),(4,7),(6,10),\dots$ 이다. $(1,2),(3,5),(4,7)$ 은 모두 P-위치. 그러나 $(2,4)$ 에서는 큰 무더기에서 $3$ 개를 빼 $(2,1)=(1,2)$ 로 갈 수 있어 상대를 P-위치에 빠뜨릴 수 있으므로 $(2,4)$ 는 N-위치(선공 필승)다. (두 무더기에서 $1$ 씩 빼면 $(1,3)$ 이 되어 P-위치가 아니다.) 따라서 P-위치가 아닌 것은 $(2,4)$.

📖 풀이:
핵심: 끝의 $0$ 의 개수 $=$ $10=2\cdot5$ 의 지수 $=\min(v_2,v_5)$ 인데 $2$ 가 $5$ 보다 훨씬 많으므로 $v_5(100!)$ 만 세면 된다(르장드르 공식). $v_5(100!)=\left\lfloor\dfrac{100}{5}\right\rfloor+\left\lfloor\dfrac{100}{25}\right\rfloor=20+4=24$. ($125>100$ 이므로 다음 항은 $0$.)

📖 풀이:
핵심: 비에트 점프(Vieta jumping). $(1,1)$ 은 $1+1+1=3=3\cdot1$ 로 해. $y$ 를 고정하면 $x^2-3yx+(y^2+1)=0$ 이고 근과 계수 관계로 다른 근은 $x'=3y-x=\dfrac{y^2+1}{x}$ (정수). 이로써 $(1,1)\to(1,2)\to(2,5)\to(5,13)\to\cdots$ 가 모두 해다($(1,2):1+4+1=6=3\cdot2$, $(2,5):4+25+1=30=3\cdot10$). 한편 $(3,7)$ 은 $9+49+1=59\ne 3\cdot21=63$ 이므로 해가 아니다.

📖 풀이:
핵심: 처음 선택이 맞을 확률은 $\frac13$, 틀릴 확률은 $\frac23$. 처음에 틀렸을 때(확률 $\frac23$) 사회자가 나머지 염소 문을 제거하므로 '바꾸기'는 반드시 자동차로 이어진다. 처음에 맞았을 때(확률 $\frac13$)만 바꾸기가 실패한다. 따라서 바꾸기 당첨 확률은 $\frac23$, 유지의 $\frac13$의 두 배다. 사회자가 정보를 가지고 행동했다는 점이 직관과 어긋나는 부분이다.

📖 풀이:
핵심: 세제곱의 합은 '처음 $n$개 자연수 합의 제곱'과 같다. $\sum_{k=1}^{10}k = \frac{10\cdot 11}{2}=55$ 이므로 $\sum_{k=1}^{10}k^3 = 55^2 = 3025$. (귀납 단계: $\left(\frac{n(n+1)}{2}\right)^2+(n+1)^3 = \left(\frac{(n+1)(n+2)}{2}\right)^2$ 가 전개로 확인된다.)

📖 풀이:
핵심: 양팔 저울 한 번은 (왼>오, 왼<오, 균형) 3가지 정보를 주므로 한 번에 후보를 $\frac13$로 줄일 수 있다. 9개를 3-3-3으로 나눠 두 묶음을 올린다. 균형이면 무거운 동전은 남은 3개 중에, 기울면 내려간 쪽 3개 중에 있다. 그 3개를 다시 1-1-1로 비교하면 두 번째 측정에서 확정. $3^2=9$ 이므로 2번이 한계이자 충분.

📖 풀이:
핵심: 세 조각이 삼각형을 이루려면 어떤 조각도 $\frac12$ 를 넘지 않아야 한다. 두 절단점을 $(x,y)$ 로 보면 표본공간은 넓이 $1$ 인 단위정사각형이고, 세 조각의 길이는 $\min(x,y),\ |x-y|,\ 1-\max(x,y)$ 이다. '가장 긴 조각이 $\frac12$ 초과'인 사건은 서로 배타적인 세 경우로 갈라진다.
- $\min(x,y)>\frac12$ ($x,y$ 가 모두 $>\frac12$): 넓이 $\frac12\cdot\frac12=\frac14$.
- $1-\max(x,y)>\frac12$ ($x,y$ 가 모두 $<\frac12$): 넓이 $\frac14$.
- $|x-y|>\frac12$ ($x-y>\frac12$ 와 $y-x>\frac12$, 두 모서리 삼각형): 각 $\frac18$, 합 $\frac14$.
세 사건은 동시에 일어날 수 없으므로 삼각형이 안 되는 넓이는 $\frac14+\frac14+\frac14=\frac34$. 따라서 삼각형이 되는 확률은 $1-\frac34=\frac14$.
그림은 대칭성을 이용해 $y>x$ 인 절반(넓이 $\frac12$)만 나타낸 것으로, 그 안에서 삼각형 조건 $x<\frac12,\ y>\frac12,\ y-x<\frac12$ 을 만족하는 음영 삼각형(꼭짓점 $(0,\frac12),(\frac12,\frac12),(\frac12,1)$)의 넓이는 $\frac18$ 이고 이는 그 절반 영역의 $\frac14$ 이다. 대칭인 $y<x$ 쪽도 같으므로 전체 확률은 $\frac14$ 로 일치한다(그림의 ¼ 은 $y>x$ 영역 대비 비율).

📖 풀이:
핵심: $8y\equiv 0\pmod 5 \Rightarrow 3y\equiv 0\pmod5 \Rightarrow y\equiv 0\pmod5$. 따라서 $y\in\{0,5,10\}$ (그 이상은 $8y>100$). 각각 $x=20,\ 12,\ 4$ 로 모두 음이 아닌 정수. 그러므로 해는 $(20,0),(12,5),(4,10)$ 의 3개.