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

📖 풀이:
핵심: 볼록 $(n+2)$각형의 삼각분할 수는 카탈란 수 $C_n=\frac{1}{n+1}\binom{2n}{n}$. 육각형은 $n=4$ 이므로 $C_4=\frac{1}{5}\binom{8}{4}=\frac{70}{5}=14$.

📖 풀이:
핵심: 끝의 0 개수는 $100!$ 의 소인수분해에서 5의 지수와 같다(2의 지수가 더 크므로). 르장드르 공식으로 $\sum_{k\ge1}\lfloor 100/5^k\rfloor=\lfloor100/5\rfloor+\lfloor100/25\rfloor=20+4=24$.

📖 풀이:
핵심: 거듭제곱을 차례로 계산한다. $2^4\equiv5,\ 2^5\equiv10\equiv-1\pmod{11}$ 이므로 $2^{10}\equiv1$. 위수는 $\varphi(11)=10$ 의 약수여야 하는데 $2^1,2^2,2^5$ 모두 1이 아니므로 위수는 10. 즉 2는 11의 원시근.

📖 풀이:
핵심: $\sin$ 은 구간 $(0,\pi)$ 에서 오목함수이므로 젠센 부등식에 의해 $\frac{\sin A+\sin B+\sin C}{3}\le\sin\frac{A+B+C}{3}=\sin\frac{\pi}{3}=\frac{\sqrt3}{2}$. 따라서 합의 최댓값은 $\frac{3\sqrt3}{2}$ 이고 정삼각형에서 달성된다.

📖 풀이:
핵심: 재배열 부등식에 의해 같은 순서(증가-증가)로 곱해 더하면 최대, 역순(증가-감소)으로 짝지으면 최소가 된다. 역순 배열은 $1\cdot4+2\cdot3+3\cdot2+4\cdot1=4+6+6+4=20$.

📖 풀이:
핵심: 비에트(근과 계수의 관계)로 $\alpha+\beta+\gamma=6,\ \alpha\beta+\beta\gamma+\gamma\alpha=11$. 따라서 $\sum\alpha^2=(\sum\alpha)^2-2\sum\alpha\beta=36-22=14$. (실제 근은 1, 2, 3)

📖 풀이:
핵심: 단위근 여과(roots of unity filter). $\omega=e^{2\pi i/3}$ 일 때 $\sum_{k\equiv0\,(\mathrm{mod}\,3)}\binom{n}{k}=\frac{1}{3}\big((1+1)^n+(1+\omega)^n+(1+\omega^2)^n\big)$. $n=6$ 이면 $1+\omega=-\omega^2$ 이라 $(1+\omega)^6=\omega^{12}=1$, 마찬가지로 $(1+\omega^2)^6=1$. 따라서 $\frac{64+1+1}{3}=22$. (직접 계산: $1+20+1=22$)

📖 풀이:
핵심: 픽의 정리 $A=I+\dfrac{B}{2}-1$. 대입하면 $A=6+\dfrac{8}{2}-1=6+4-1=9$.

📖 풀이:
핵심: 램지 수 $R(3,3)=6$. 6명을 정점으로, 친구 관계를 간선 색으로 두면 한 사람의 5개 관계 중 같은 색이 최소 3개(비둘기집)이고, 이로부터 단색 삼각형이 강제된다. 5명일 때는 정오각형 모양의 반례가 있어 보장되지 않는다.

📖 풀이:
핵심: 무한강하법. $a^2=2b^2$ 이면 $a$ 는 짝수이므로 $a=2a_1$. 대입하면 $4a_1^2=2b^2$, 즉 $b^2=2a_1^2$ 이라 $b$ 도 짝수 $b=2b_1$, 다시 $a_1^2=2b_1^2$ 로 같은 형태가 더 작은 양의 정수에서 반복된다. 양의 정수는 무한히 작아질 수 없으므로 모순, 해는 존재하지 않는다(이는 $\sqrt2$ 가 무리수임과 동치).

📖 풀이:
핵심: 악수 보조정리에 의해 모든 정점의 차수 합은 간선 수의 2배, 즉 반드시 짝수여야 한다. ③의 합은 $5+3+2+2+2+1=15$ 로 홀수이므로 어떤 그래프로도 실현 불가능하다. (나머지는 합이 짝수이고 에르되시-갈라이 조건도 만족한다.)

📖 풀이:
핵심: 집합의 분할 수는 벨 수 $B_4$. 부분 개수별 제2종 스털링 수의 합으로 $S(4,1)+S(4,2)+S(4,3)+S(4,4)=1+7+6+1=15$.

📖 풀이:
핵심: 생성함수 $(1+x+x^2+x^3+x^4)^3=\left(\frac{1-x^5}{1-x}\right)^3$ 에서 $x^{10}$ 의 계수를 구한다. $(1-x^5)^3=1-3x^5+3x^{10}-\cdots$ 와 $(1-x)^{-3}=\sum_k\binom{k+2}{2}x^k$ 를 곱하면 계수는 $\binom{12}{2}-3\binom{7}{2}+3\binom{2}{2}=66-63+3=6$.

📖 풀이:
핵심: 님 게임은 모든 더미 크기의 이진 XOR(님-합)이 0이면 후공 필승이다. $2\oplus4\oplus6 = 010\oplus100\oplus110 = 000$ 이므로 님-합이 0. 선공은 어떤 수를 두어도 님-합을 0이 아닌 상태로 만들어 후공에게 넘기게 되고, 후공은 다시 0으로 되돌릴 수 있어 결국 선공이 진다.

📖 풀이:
핵심: 교란순열(derangement) 수 $D_n=n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}$. $D_4=24\left(1-1+\frac12-\frac16+\frac1{24}\right)=24\cdot\frac{9}{24}=9$. 포함배제로도 같은 값을 얻는다.

📖 풀이:
핵심: 관계식에서 $f(2^n)=n\,f(2)$ 임을 귀납적으로 얻는다($f(2^2)=2f(2)$ 등). $32=2^5$ 이므로 $f(32)=5f(2)=5$. 이 성질은 로그함수 $f(x)=\log_2 x$ 의 특징이다.

📖 풀이:
핵심: 기댓값의 선형성. 사람 $i$ 가 자기 모자를 받으면 1, 아니면 0인 지시확률변수를 $X_i$ 라 하면 $P(X_i=1)=\frac1n$ 이므로 $E[X_i]=\frac1n$. 따라서 $E\!\left[\sum_{i=1}^n X_i\right]=n\cdot\frac1n=1$ 로 $n$ 과 무관하다(변수들의 독립성도 필요 없다).

📖 풀이:
핵심: 같은 나머지를 묶고 중국인 나머지정리(CRT)로 결합. $x \equiv 2 \pmod 3$과 $x \equiv 2 \pmod 7$은 함께 $x \equiv 2 \pmod{21}$. 따라서 $x = 2 + 21k$. 이를 $x \equiv 3 \pmod 5$에 대입하면 $2 + 21k \equiv 3 \pmod 5$, 즉 $k \equiv 1 \pmod 5$ (∵ $21 \equiv 1$). 최소 $k=1$이면 $x = 23$. 검산: $23 = 7\cdot3+2$, $4\cdot5+3$, $3\cdot7+2$ 모두 성립. 전체 해는 $x \equiv 23 \pmod{105}$.

📖 풀이:
핵심: 볼록 $(n+2)$각형의 삼각분할 수는 카탈란 수 $C_n$. 육각형은 $n+2=6$이므로 $n=4$, $C_4 = \frac{1}{5}\binom{8}{4} = \frac{70}{5} = 14$. (점화 $C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k}$로도 $C_0{=}1, C_1{=}1, C_2{=}2, C_3{=}5, C_4{=}14$.)

📖 풀이:
핵심: 오일러 판정은 '홀수 차수 정점의 개수'로 결정. 오일러 회로 ⇔ 모든 정점 차수 짝수, 오일러 경로 ⇔ 홀수 차수 정점이 정확히 0개 또는 2개. $K_4$는 모든 정점의 차수가 3(홀수)이라 홀수 차수 정점이 4개. 따라서 둘 다 불가능.

📖 풀이:
핵심: 전체 합의 홀짝성이 불변량. $|a-b| \equiv a+b \pmod 2$이므로 두 수를 차로 바꿔도 칠판 위 모든 수의 합의 홀짝성은 변하지 않는다. 처음 합은 $1+2+\cdots+20 = 210$(짝수). 따라서 마지막 한 수도 짝수.

📖 풀이:
핵심: 누적합을 mod 7로 보고 비둘기집. $S_0 = 0,\ S_k = a_1 + \cdots + a_k\ (k=1,\dots,7)$로 총 $8$개의 부분합을 둔다. 이들을 7로 나눈 나머지는 $0,1,\dots,6$의 7가지뿐이므로, 8개 중 적어도 두 개 $S_i, S_j\ (i<j)$의 나머지가 같다. 그러면 $S_j - S_i = a_{i+1} + \cdots + a_j \equiv 0 \pmod 7$, 즉 연속한 항들의 합이 7의 배수. 비둘기 8마리, 둥지 7개.

📖 풀이:
핵심: 코시-슈바르츠의 엥겔 형태(Titu 보조정리) $\dfrac{a^2}{p} + \dfrac{b^2}{q} \ge \dfrac{(a+b)^2}{p+q}$. 여기서 $\dfrac{2^2}{x} + \dfrac{3^2}{y} \ge \dfrac{(2+3)^2}{x+y} = \dfrac{25}{10} = \dfrac{5}{2}$. 등호는 $\dfrac{2}{x} = \dfrac{3}{y}$, 즉 $x=4, y=6$일 때 성립하며 실제로 $\dfrac{4}{4} + \dfrac{9}{6} = 1 + 1.5 = 2.5$.

📖 풀이:
핵심: 일의 자리(mod 10)의 거듭제곱 주기. $7^1=7,\ 7^2=49,\ 7^3=343,\ 7^4=2401$로 일의 자리가 $7,9,3,1$이 주기 4로 반복. $2026 = 4\cdot506 + 2$이므로 주기에서 두 번째인 $9$.

📖 풀이:
핵심: mod 3 분석 + 무한강하법. 제곱수는 $\bmod 3$으로 $0$ 또는 $1$. $x^2 + y^2 \equiv 0 \pmod 3$이 되려면 $x^2 \equiv y^2 \equiv 0$, 즉 $3 \mid x,\ 3 \mid y$. $x = 3x',\ y = 3y'$를 대입하면 $9x'^2 + 9y'^2 = 3z^2 \Rightarrow z^2 = 3(x'^2 + y'^2)$이므로 $3 \mid z$, $z = 3z'$. 그러면 $x'^2 + y'^2 = 3z'^2$로 같은 형태의 더 작은 해가 나온다. 0이 아닌 해가 있다면 무한히 작아지는 양의 정수열을 얻어 모순(무한강하). 따라서 자명해뿐.