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

📖 풀이:
핵심: 한 사람 $P$ 에서 나머지 $5$명과의 관계를 두 색(아는/모르는)으로 보면, 비둘기집에 의해 같은 색이 $3$명 이상 있다. 그 색이 '아는 사이'라 하자(다른 경우도 대칭). 그 $3$명끼리 한 쌍이라도 '아는 사이'면 $P$ 와 함께 $3$명 친구 완성, 아무도 아니면 그 $3$명이 서로 모르는 $3$명. 어느 경우든 단색 삼각형이 생긴다. 즉 $R(3,3)=6$.

📖 풀이:
핵심(이중계산/위원장 논법): $n$ 명에서 위원회를 뽑고 그중 위원장 $1$ 명을 정하는 방법을 두 가지로 센다. (위원회 크기 $k$ 먼저) $\sum_k k\binom{n}{k}$, (위원장 먼저) 위원장 $n$ 가지 $\times$ 나머지 각자 포함여부 $2^{n-1}$. 따라서 $\sum_{k}k\binom{n}{k}=n\,2^{n-1}$. $n=10$ 이면 $10\cdot2^{9}=10\cdot512=5120$.

📖 풀이:
핵심: 볼록 $(n+2)$각형의 삼각분할 수는 카탈란 수 $C_n$. 육각형은 $n+2=6\Rightarrow n=4$. $C_n$ 은 점화 $C_{n}=\sum_{i=0}^{n-1}C_iC_{n-1-i}$ 또는 $C_n=\frac{1}{n+1}\binom{2n}{n}$ 로 $C_4=\frac{1}{5}\binom{8}{4}=\frac{70}{5}=14$.

📖 풀이:
윌슨 정리에 의해 $16! \equiv -1 \pmod{17}$. 한편 $16! = 16 \times 15!$ 이고 $16 \equiv -1 \pmod{17}$ 이므로 $-15! \equiv -1 \pmod{17}$, 즉 $15! \equiv 1 \pmod{17}$.

📖 풀이:
$36 = 2^2 \cdot 3^2$. 오일러 토션트 함수의 곱셈성과 $\varphi(p^k)=p^k-p^{k-1}$ 에 의해 $\varphi(36)=\varphi(4)\varphi(9)=(4-2)(9-3)=2\cdot 6=12$. 또는 $36\left(1-\tfrac12\right)\left(1-\tfrac13\right)=12$.

📖 풀이:
$x\equiv 2\pmod 3$ 와 $x\equiv 2\pmod 7$ 에서 $x\equiv 2\pmod{21}$. $x=21k+2$ 를 $x\equiv 3\pmod 5$ 에 대입하면 $21k+2\equiv k+2\equiv 3$, 즉 $k\equiv 1\pmod 5$. 최소 $k=1$ 에서 $x=23$. (중국인 나머지정리)

📖 풀이:
부분분수 분해 $\frac{1}{k(k+1)}=\frac1k-\frac{1}{k+1}$ 를 쓰면 합이 망원경(텔레스코핑)으로 소거되어 $\left(1-\frac12\right)+\cdots+\left(\frac1{99}-\frac1{100}\right)=1-\frac1{100}=\frac{99}{100}$.

📖 풀이:
$(0,0)\to(2,2)$ 경로는 오른쪽 2번, 위 2번을 배열하는 $\binom{4}{2}=6$ 가지. $(2,2)\to(4,4)$ 도 같은 이유로 $\binom{4}{2}=6$ 가지. 두 구간은 독립이므로 곱의 법칙에 의해 $6\times 6=36$.

📖 풀이:
핵심: 부분합과 비둘기집. 부분합 $S_0=0,\ S_k=a_1+\cdots+a_k\ (k=1,\dots,7)$ 의 $8$ 개 값을 $7$ 로 나눈 나머지를 본다. 나머지는 $0\sim 6$ 의 $7$ 종류뿐이므로 비둘기집 원리로 $S_i\equiv S_j\ (i<j)$ 인 두 값이 존재한다. 그러면 $S_j-S_i=a_{i+1}+\cdots+a_j$ 가 $7$ 의 배수다.

📖 풀이:
산술-기하 평균 부등식 $a+b\ge 2\sqrt{ab}$ 에서 $x+\frac4x\ge 2\sqrt{x\cdot\frac4x}=2\sqrt4=4$. 등호는 $x=\frac4x$, 즉 $x=2$ 에서 성립.

📖 풀이:
코시-슈바르츠 부등식 $(a+2b+2c)^2\le (1^2+2^2+2^2)(a^2+b^2+c^2)=9\cdot 1=9$ 이므로 $a+2b+2c\le 3$. 등호는 $(a,b,c)$ 가 $(1,2,2)$ 와 평행, 즉 $a=\frac13,\ b=c=\frac23$ 에서 성립.

📖 풀이:
$\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}$. 따라서 합은 $\le \frac{3\sqrt3}{2}$ 이고 등호는 정삼각형 $A=B=C=\frac{\pi}{3}$ 에서 성립.

📖 풀이:
핵심: $4$ 의 배수가 패배 위치(P-포지션). 한 번에 $1\sim3$ 개를 가져가므로 상대가 $k$ 개를 가져가면 나는 $4-k$ 개를 가져가 남은 돌 수를 항상 $4$ 의 배수로 유지할 수 있다. 시작값 $20$ 은 $4$ 의 배수라서 둘 차례인 선공이 진다. 즉 후공이 이 전략으로 승리한다. (그런디값 $g(n)=n\bmod 4$, $g(20)=0$ 이 패배 위치)

📖 풀이:
방멱(접선-할선) 정리: $PT^2=PA\cdot PB$. 여기서 $PB=PA+AB=2+6=8$ 이므로 $PT^2=2\cdot 8=16$, 따라서 $PT=4$.

📖 풀이:
$f(4)=f(2\cdot2)=2f(2)$, $f(8)=f(2\cdot4)=f(2)+f(4)=3f(2)=3$. (이 곱셈형 함수방정식의 연속해는 로그함수 $f(x)=\log_2 x$ 이며 실제로 $f(8)=\log_2 8=3$.)

📖 풀이:
불변량: 앞면 개수의 홀짝성. 한 번 조작할 때 앞면 개수는 $+2,\ 0,\ -2$ 중 하나만큼만 변하므로 홀짝성이 보존된다. 처음 앞면 개수는 $3$(홀수)이고 목표인 모두 뒷면은 앞면 $0$ 개(짝수)다. 홀짝이 다르므로 도달할 수 없다.

📖 풀이:
무한강하법(무한하강). 해가 존재한다면 $x$ 가 가장 작은 해를 택하자. $x^2=2y^2$ 에서 $x^2$ 이 짝수이므로 $x$ 는 짝수, $x=2m$. 대입하면 $4m^2=2y^2\Rightarrow y^2=2m^2$ 이라 $(y,m)$ 역시 해이고 $y<x$. 더 작은 해가 끝없이 나오는 모순. 따라서 양의 정수해는 없다.

📖 풀이:
근과 계수의 관계(비에트): $\alpha+\beta=7,\ \alpha\beta=11$. 따라서 $\alpha^2+\beta^2=(\alpha+\beta)^2-2\alpha\beta=49-22=27$.

📖 풀이:
베이즈 정리. $P(\text{병}\mid +)=\dfrac{P(+\mid\text{병})P(\text{병})}{P(+)}$. 분자 $=0.99\times0.01=0.0099$. 분모 $=0.0099+\underbrace{0.02\times0.99}_{\text{위양성}}=0.0099+0.0198=0.0297$. 따라서 $\dfrac{0.0099}{0.0297}=\dfrac13\approx33\%$.

📖 풀이:
핵심: 색칠 불변량. 흑백으로 칠하면 도미노 하나는 반드시 흑1·백1을 덮는다. 마주보는 두 모서리 칸은 같은 색(예: 둘 다 흑)이므로 제거 후 흑 30칸·백 32칸이 남는다. 도미노 31개는 흑31·백31을 요구하므로 색 개수가 맞지 않아 덮기가 불가능하다.

📖 풀이:
핵심: $a+b+ab=(a+1)(b+1)-1$. 따라서 칠판의 각 수에 1을 더한 값들의 곱은 연산 동안 변하지 않는다(불변량). 처음 그 곱은 $\prod_{k=1}^{n}(k+1)=(n+1)!$. 마지막에 남는 수를 $S$라 하면 $S+1=(n+1)!$이므로 $S=(n+1)!-1$. 순서와 무관하다.

📖 풀이:
핵심: $x\to\frac1x$ 대입 후 연립. 주어진 식 $f(x)+2f(1/x)=3x$ ...(1). $x$ 대신 $1/x$를 넣으면 $f(1/x)+2f(x)=3/x$, 즉 $2f(x)+f(1/x)=3/x$ ...(2). $(2)\times2-(1)$: $3f(x)=\frac6x-3x$, 따라서 $f(x)=\frac2x-x$. 그러므로 $f(2)=1-2=-1$.

📖 풀이:
핵심: 텔레스코핑. $k\cdot k!=(k+1)!-k!$. 따라서 $\sum_{k=1}^{n}k\cdot k!=\sum_{k=1}^{n}\big[(k+1)!-k!\big]=(n+1)!-1!=(n+1)!-1$. 중간 항이 모두 소거된다.

📖 풀이:
핵심: 각 수를 $2^a\cdot m$ ($m$은 홀수)로 쓰면 $m\in\{1,3,5,\dots,2n-1\}$로 $n$가지뿐이다. $n+1$개를 고르면 비둘기집 원리에 의해 같은 홀수 부분 $m$을 갖는 두 수 $2^a m,\ 2^b m$ ($a<b$)이 반드시 존재하고, 이때 작은 쪽이 큰 쪽을 나눈다.

📖 풀이:
핵심: 산술-기하 평균. $a+b+c\ge3\sqrt[3]{abc}$이고 $\frac1a+\frac1b+\frac1c\ge\dfrac{3}{\sqrt[3]{abc}}$. 두 식을 곱하면 $(a+b+c)\left(\frac1a+\frac1b+\frac1c\right)\ge9$. 등호는 $a=b=c$일 때 성립하므로 최솟값은 $9$.