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

📖 풀이:
핵심 아이디어: 완전순열(교란순열, derangement)을 포함배제로 센다. $D_n=n!\sum_{k=0}^{n}\dfrac{(-1)^k}{k!}$. $n=4$이면 $D_4=24\left(1-1+\tfrac12-\tfrac16+\tfrac1{24}\right)=24\cdot\tfrac{9}{24}=9$. 점화식 $D_n=(n-1)(D_{n-1}+D_{n-2})$로도 $D_4=3(2+1)\cdot\dots=9$.

📖 풀이:
핵심 아이디어: 거듭제곱을 차례로 계산하며 처음으로 $1$이 되는 지수를 찾는다. $3^1\equiv3,\ 3^2\equiv2,\ 3^3\equiv6,\ 3^4\equiv4,\ 3^5\equiv5,\ 3^6\equiv1\pmod7$. 따라서 위수는 $6$. 위수는 페르마 소정리의 $p-1=6$을 나누어야 하는데($k\mid 6$), $6$ 자신이 위수이므로 $3$은 $\bmod 7$의 원시근이다.

📖 풀이:
핵심 아이디어: 연결그래프에서 오일러 회로 존재 $\iff$ 모든 정점의 차수가 짝수. 차수를 세면 $\deg A=2,\ \deg B=2,\ \deg C=4,\ \deg D=2,\ \deg E=2$로 모두 짝수이고 그래프는 연결되어 있다. 따라서 오일러 회로가 존재한다(예: $A\to B\to C\to D\to E\to C\to A$).

📖 풀이:
핵심 아이디어: 베이즈 정리. $P(\text{병}\mid +)=\dfrac{P(+\mid\text{병})P(\text{병})}{P(+\mid\text{병})P(\text{병})+P(+\mid\text{무병})P(\text{무병})}$. 분자 $=0.99\times0.01=0.0099$, 거짓양성 $=0.05\times0.99=0.0495$. 따라서 $\dfrac{0.0099}{0.0099+0.0495}=\dfrac{0.0099}{0.0594}\approx0.167$, 즉 약 $17\%$.

📖 풀이:
핵심 아이디어: 비제차 점화식을 평행이동으로 등비수열로 만든다. $a_n+1=2(a_{n-1}+1)$이므로 $b_n=a_n+1$은 $b_1=2$인 공비 $2$ 등비수열. $b_n=2^n$이므로 $a_n=2^n-1$. 따라서 $a_{10}=2^{10}-1=1023$. (하노이 탑에서 원반 $n$개를 옮기는 최소 횟수와 같은 식이다.)

📖 풀이:
핵심 아이디어: 불변량을 찾는다. $a+b+ab=(a+1)(b+1)-1$이므로, 각 수에 $1$을 더한 값들의 '곱'에서 마지막에 $1$을 빼면 결과가 된다. 즉 $\prod(x_i+1)$이 (마지막 $+1$까지 포함해) 보존된다. 처음 값 $1,\dots,5$에 대해 $(1+1)(2+1)(3+1)(4+1)(5+1)=2\cdot3\cdot4\cdot5\cdot6=720$. 남는 수는 $720-1=719$이며 연산 순서와 무관하다.

📖 풀이:
핵심 아이디어: P-포지션(이전 플레이어 승, 즉 둘 차례를 받은 사람이 지는 위치)은 돌 개수가 $4$의 배수일 때다. 증명: $0$은 P-포지션. $4$의 배수에서 $1$ - 3개를 가져가면 상대에게 $4$의 배수가 아닌 수가 가고, 상대는 항상 다시 $4$의 배수로 만들 수 있다. $2024=4\times506$이므로 시작이 P-포지션이라 선공이 진다. 즉 후공이 이긴다.

📖 풀이:
핵심 아이디어: 곱셈형 코시 함수방정식. $f(x+y)=f(x)f(y)$에 정수 인수를 넣으면 $f(n)=f(1)^n$이다. 실제로 $f(2)=f(1)^2,\ f(3)=f(1)^3,\ f(4)=f(1)^4$. 따라서 $f(4)=3^4=81$. (연속성이나 양수 조건을 가정하면 전체 해는 $f(x)=3^x$로 유일하게 결정된다.)

📖 풀이:
핵심 아이디어: 이것은 벨 수 $B_4$다. 분할의 크기별로 센다. 한 덩어리 $\{1234\}$: $1$가지. $3{+}1$: $\binom41=4$. $2{+}2$: $\frac12\binom42=3$. $2{+}1{+}1$: $\binom42=6$. $1{+}1{+}1{+}1$: $1$. 합 $1+4+3+6+1=15$. 점화식 $B_{n+1}=\sum_k\binom nk B_k$로도 $B_4=15$ ($B_0{=}1,B_1{=}1,B_2{=}2,B_3{=}5$).

📖 풀이:
핵심 아이디어: '사이먼의 좋아하는 인수분해'로 곱 형태를 만든다. 양변에 $4xy$를 곱하면 $4y+4x=xy$, 즉 $xy-4x-4y=0$, 양변에 $16$을 더하면 $(x-4)(y-4)=16$. $x,y>0$이려면 $x-4>0$(음수면 $1/x+1/y<1/4$ 불가). $16$의 양의 약수는 $1,2,4,8,16$의 $5$개이고, 각 약수쌍 $(x-4,y-4)\in\{(1,16),(2,8),(4,4),(8,2),(16,1)\}$이 순서쌍을 준다. 따라서 $5$개.

📖 풀이:
핵심 아이디어: 코시-슈바르츠(또는 제곱평균-산술평균). $(1^2+1^2+1^2)(a^2+b^2+c^2)\ge(a+b+c)^2$이므로 $3(a^2+b^2+c^2)\ge9$, 즉 $a^2+b^2+c^2\ge3$. 등호는 $a=b=c=1$일 때 성립한다. 따라서 최솟값은 $3$. (변수가 같을 때 제곱합이 최소가 되는 것은 '분산이 0'일 때라는 직관과 일치.)

📖 풀이:
핵심 아이디어: 크기에 대한 강귀납법. $2^n\times2^n$ 판에서 한 칸을 제거하면 항상 L-트로미노로 덮을 수 있음을 보인다. 판을 네 개의 $2^{n-1}\times2^{n-1}$ 사분면으로 나누면 제거된 칸은 한 사분면에만 있다. 중앙에 L-트로미노 하나를 두어 나머지 세 사분면의 중심 한 칸씩을 '가짜로 제거'된 것처럼 만들면, 네 사분면 모두 '한 칸 제거된 $2^{n-1}$ 판'이 되어 귀납가정으로 덮인다. $8\times8$은 $n=3$이라 항상 가능. 칸 수가 $63=3\times21$이므로 트로미노는 $21$개.

📖 풀이:
핵심 아이디어: 조건부 확률에서 표본공간을 올바르게 줄이는 것이 관건. 두 자녀의 출생 순서를 고려한 표본공간은 $\{BB,BG,GB,GG\}$로 각각 확률 $\tfrac14$. '적어도 한 명 아들' 조건은 $GG$를 제외해 $\{BB,BG,GB\}$만 남기고, 이 셋은 같은 확률이다. 이 중 둘 다 아들($BB$)은 하나뿐이므로 확률은 $\dfrac13$. 직관적인 $\tfrac12$은 $BG$와 $GB$를 합쳐버리는 오류에서 나온다.

📖 풀이:
핵심: $x^2-y^2=(x-y)(x+y)$ 로 인수분해하고 두 인수의 패리티를 따진다. $d=x-y,\ e=x+y$ 라 하면 $de=96,\ d<e$ 이고 $d,e$ 는 항상 같은 패리티여야 한다. $96$ 이 짝수이므로 둘 다 홀수일 수 없고 따라서 둘 다 짝수다. $96$ 의 짝수$\times$짝수 분해 $(d,e)$: $(2,48),(4,24),(6,16),(8,12)$. 각각 $x=\frac{d+e}{2},\ y=\frac{e-d}{2}$ 로 $(25,23),(14,10),(11,5),(10,2)$ 의 4개.

📖 풀이:
핵심(귀납 한 줄): $2^n\times 2^n$ 을 네 개의 $2^{n-1}\times 2^{n-1}$ 로 나누고, 중앙에 L-트로미노 하나를 놓아 네 사분면이 각각 '한 칸 제거된 상태'가 되게 만들면 귀납가설로 모두 덮인다. 칸 수는 $8\times 8 - 1 = 63$ 이고 트로미노가 3칸을 덮으므로 개수는 $63/3 = 21$. (일반적으로 $\frac{4^n-1}{3}$ 개.)

📖 풀이:
핵심: 전구 $n$ 은 $n$ 의 약수의 개수만큼 토글된다. 약수는 보통 쌍 $(d, n/d)$ 로 짝지어지므로 개수가 짝수여서 다시 꺼지지만, $n$ 이 완전제곱수일 때만 $\sqrt n$ 이 짝을 못 이뤄 약수 개수가 홀수가 되어 최종적으로 켜진다. $1$ - $100$ 의 완전제곱수는 $1,4,9,\dots,100$ 의 $10$ 개.

📖 풀이:
핵심: 중국인 나머지정리(CRT). $x\equiv 2 \pmod 3$ 과 $x\equiv 2\pmod 7$ 에서 $x\equiv 2 \pmod{21}$ 이므로 $x\in\{2,23,44,65,\dots\}$. 이 중 $x\equiv 3 \pmod 5$ 를 만족하는 것은 $23$ ($23=4\cdot 5+3$). $3,5,7$ 이 서로소이므로 해는 $\pmod{105}$ 로 유일하며 최소 양수는 $23$.

📖 풀이:
핵심: $x \to 1-x$ 치환으로 식을 하나 더 만들어 연립한다. 원식 (1): $f(x)+2f(1-x)=x^2$. $x$ 대신 $1-x$: (2) $f(1-x)+2f(x)=(1-x)^2$. (2)$\times 2 -$(1): $3f(x) = 2(1-x)^2 - x^2$, 즉 $f(x)=\dfrac{x^2-4x+2}{3}$. 따라서 $f(2)=\dfrac{4-8+2}{3}=-\dfrac{2}{3}$.

📖 풀이:
핵심: 포함배제(inclusion-exclusion). 배수 개수 $\lfloor 1000/2\rfloor=500,\ \lfloor1000/3\rfloor=333,\ \lfloor1000/5\rfloor=200$; 두 개씩 $\lfloor1000/6\rfloor=166,\ \lfloor1000/10\rfloor=100,\ \lfloor1000/15\rfloor=66$; 셋 모두 $\lfloor1000/30\rfloor=33$. 적어도 하나로 나뉘는 수 $=500+333+200-(166+100+66)+33 = 734$. 따라서 답은 $1000-734=266$.

📖 풀이:
핵심: 합이 $11$ 인 쌍으로 비둘기집을 만든다. $\{1,10\},\{2,9\},\{3,8\},\{4,7\},\{5,6\}$ 의 5개 집(쌍)으로 $1$ - $10$ 이 모두 분할된다. $6$ 개를 뽑으면 비둘기집 원리에 의해 같은 쌍에서 두 수가 나와 합 $11$ 이 보장된다. 반면 각 쌍에서 하나씩만 고른 $5$ 개(예: $1,2,3,4,5$)는 합 $11$ 이 없으므로 $5$ 로는 불충분. 따라서 최솟값은 $6$.

📖 풀이:
핵심: 점화식 $a_n=2a_{n-1}+1$ 의 양변에 $1$ 을 더하면 $a_n+1 = 2(a_{n-1}+1)$ 로 등비꼴이 된다. $a_1+1=2$ 이므로 $a_n+1 = 2^n$, 즉 $a_n = 2^n - 1$. 따라서 $a_{10}=2^{10}-1 = 1023$.

📖 풀이:
핵심: 차수의 홀짝을 센다. 각 정점 차수는 $V_1:3,\ V_2:2,\ V_3:3,\ V_4:2,\ V_5:2$. 그래프는 연결되어 있고 홀수 차수 정점이 정확히 $2$ 개($V_1,V_3$)다. 오일러 회로는 '모든 차수가 짝수'일 때만, 오일러 경로는 '홀수 차수 정점이 0 또는 2개'일 때 존재한다. 따라서 회로는 없고 경로는 ($V_1$ 또는 $V_3$ 에서 시작해) 존재한다.

📖 풀이:
핵심: 영국 국기 정리(British Flag Theorem) - 직사각형의 임의의 점 $P$ 에 대해 마주 보는 두 꼭짓점까지 거리 제곱의 합이 같다: $PA^2+PC^2 = PB^2+PD^2$. 따라서 $PD^2 = PA^2+PC^2-PB^2 = 9+25-16 = 18$, $PD = \sqrt{18} = 3\sqrt{2}$. (좌표를 잡고 $P=(x,y)$ 로 직접 전개해도 같은 항등식이 나온다.)

📖 풀이:
핵심: 베이즈 정리. $P(\text{병}\mid +) = \dfrac{P(+\mid\text{병})P(\text{병})}{P(+)}$. 분자 $=0.99\times 0.001 = 0.00099$. 양성 전체 확률 $P(+) = 0.00099 + 0.05\times 0.999 = 0.00099+0.04995 = 0.05094$. 따라서 $\dfrac{0.00099}{0.05094}\approx 0.0194 \approx 1.9\%$. 검사 정확도가 높아도 유병률이 낮으면 양성의 대부분이 위양성이라는 '기저율 무시' 직관 함정.

📖 풀이:
핵심(불변량): 한 번의 작업에서 칠판 수의 합은 $(a+b)$ 가 사라지고 $(a+b-1)$ 이 생기므로 정확히 $1$ 만큼 줄고, 수의 개수도 $1$ 씩 준다. 처음 합은 $1+2+\cdots+2024 = \dfrac{2024\cdot 2025}{2} = 2049300$. 수를 $2024$ 개에서 $1$ 개로 줄이려면 작업을 $2023$ 번 하므로 합은 $2023$ 만큼 줄어 $2049300 - 2023 = 2047277$. 어떤 순서로 작업해도 결과는 같다.