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

📖 풀이:
핵심: 항등식 $\gcd(a,b)\cdot\lcm(a,b)=ab$. $6\cdot36=12\cdot b$ → $216=12b$ → $b=18$. 검산: $\gcd(12,18)=6$, $\lcm(12,18)=36$. 모두 성립.

📖 풀이:
핵심: 원에 내접하는 사각형 $ABPC$에 톨레미 정리 $PA\cdot BC = PB\cdot AC + PC\cdot AB$를 적용한다. 정삼각형이므로 $AB=BC=CA$이고 양변을 그 길이로 나누면 $PA=PB+PC=3+5=8$.

📖 풀이:
핵심: 코시 함수방정식은 유리수에서 반드시 $f(x)=cx$ 꼴이다. 먼저 $f(0)=0$, 정수 $n$에 대해 $f(n)=nf(1)$. 또 $f(1)=f\!\left(q\cdot\frac1q\right)=q\,f\!\left(\frac1q\right)$이므로 $f\!\left(\frac1q\right)=\frac{f(1)}{q}$, 따라서 $f\!\left(\frac{p}{q}\right)=\frac{p}{q}f(1)$. $c=f(1)=3$이므로 $f\!\left(\frac52\right)=3\cdot\frac52=\frac{15}{2}$.

📖 풀이:
핵심: 어떤 원소도 제자리에 있지 않은 순열(교란순열)의 수. 점화식 $D_n=(n-1)(D_{n-1}+D_{n-2})$, $D_1=0,\ D_2=1$. $D_3=2(1+0)=2$, $D_4=3(2+1)=9$, $D_5=4(9+2)=44$. 또는 포함배제로 $D_5=5!\left(1-1+\frac1{2!}-\frac1{3!}+\frac1{4!}-\frac1{5!}\right)=44$.

📖 풀이:
핵심: 윌슨 정리에서 $16!\equiv-1\pmod{17}$. 그런데 $16!=16\cdot15!$이고 $16\equiv-1\pmod{17}$이므로 $16!\equiv(-1)\cdot15!\pmod{17}$. 따라서 $-15!\equiv-1\pmod{17}$ → $15!\equiv1\pmod{17}$. 나머지는 $1$.

📖 풀이:
핵심: 님합(이진 XOR) $2\oplus3\oplus4$를 계산한다. $010\oplus011\oplus100=101=5\neq0$이므로 선공 필승. 이기려면 님합을 $0$으로 만들어야 한다. 각 더미를 $(\text{현재값})\oplus5$와 비교하면, $4\oplus5=1<4$이므로 $4$ 더미를 $1$개로 줄이면 된다(즉 $3$개 제거). 그러면 $(2,3,1)$, 님합 $2\oplus3\oplus1=0$이 되어 상대를 패배 위치로 몬다.

📖 풀이:
핵심: 코시-슈바르츠 $(x^2+y^2)(1^2+2^2)\ge(x\cdot1+y\cdot2)^2$. 우변은 $(x+2y)^2=16$이므로 $5(x^2+y^2)\ge16$ → $x^2+y^2\ge\frac{16}{5}$. 등호는 $\frac{x}{1}=\frac{y}{2}$일 때, 즉 $x=\frac45,\ y=\frac85$. 기하적으로는 $x^2+y^2$이 원점에서 직선까지 거리의 제곱이고, 그 거리는 $\frac{|{-4}|}{\sqrt{1^2+2^2}}=\frac{4}{\sqrt5}$, 제곱하면 $\frac{16}{5}$.

📖 풀이:
핵심: 질량점은 분점 비의 '역수'로 무게를 준다. $BD:DC=1:2$이므로 무게 $m_B:m_C=DC:BD=2:1$. $CE:EA=1:2$이므로 $m_C:m_A=EA:CE=2:1$. $C$를 공통으로 맞추려 $m_C=2$로 두면 $m_B=4,\ m_A=1$. $D$는 $B,C$의 평형점이라 $m_D=m_B+m_C=6$. 체바선 $AD$ 위에서 $P$는 $A$와 $D$의 평형점이므로 $AP:PD=m_D:m_A=6:1$.

📖 풀이:
핵심: 소수 $p$ 에 대해 윌슨 정리 $(p-1)! \equiv -1 \pmod{p}$ 가 성립한다. $p=13$ 이므로 $12! \equiv -1 \equiv 12 \pmod{13}$. 따라서 나머지는 $12$.

📖 풀이:
핵심: $x\equiv 2\pmod 3$ 와 $x\equiv 2\pmod 7$ 을 합치면 $x\equiv 2\pmod{21}$. 후보 $2,23,44,\dots$ 중 $x\equiv 3\pmod 5$ 를 만족하는 최소값을 찾는다. $2\equiv 2$, $23\equiv 3\pmod 5$ 이므로 $23$. 검산: $23=3\cdot7+2,\ 23=5\cdot4+3,\ 23=7\cdot3+2$ 모두 성립.

📖 풀이:
핵심: 산술-기하 평균 부등식에 의해 $x+\dfrac{9}{x}\ge 2\sqrt{x\cdot\dfrac{9}{x}}=2\sqrt{9}=6$. 등호는 $x=\dfrac{9}{x}$, 즉 $x=3$ 일 때 성립하므로 최솟값은 $6$.

📖 풀이:
핵심(베이즈 정리): $P(\text{병}\mid +)=\dfrac{P(+\mid \text{병})P(\text{병})}{P(+)}$. 분자 $=0.99\times 0.01=0.0099$. 분모 $P(+)=0.99\times 0.01+0.05\times 0.99=0.0099+0.0495=0.0594$. 따라서 $\dfrac{0.0099}{0.0594}=\dfrac{1}{6}\approx 16.7\%$. 검사 정확도가 높아도 유병률이 낮으면 양성의 대부분이 위양성임에 주의.

📖 풀이:
핵심 불변량: 두 색 개수의 차를 $3$ 으로 나눈 나머지는 보존된다. 한 번의 변환에서 두 색은 $1$ 씩 줄고 한 색은 $2$ 늘어, 임의의 두 색 개수 차는 $0$ 또는 $\pm 3$ 만큼만 변하므로 $\pmod 3$ 으로 불변이다. 처음 개수는 $13\equiv 1,\ 15\equiv 0,\ 17\equiv 2 \pmod 3$ 으로 셋이 모두 다르다. 모두 한 색이 되려면 나머지 두 색의 개수가 $0$ 으로 같아야 하니 그 두 색 개수 차가 $\equiv 0\pmod 3$ 이어야 하는데, 어떤 두 색도 $\pmod 3$ 이 같지 않으므로 불가능.

📖 풀이:
핵심: $(x-y)(x+y)=60$. $x,y$ 가 정수이려면 $x-y$ 와 $x+y$ 는 같은 홀짝성을 가져야 하는데, 곱 $60$ 이 짝수이므로 둘 다 짝수여야 한다. $x-y=2a,\ x+y=2b\ (a<b)$ 로 놓으면 $4ab=60$, 즉 $ab=15$. 가능한 $(a,b)=(1,15),(3,5)$ 두 가지뿐이고, 각각 $(x,y)=(16,14),(8,2)$ 로 모두 양의 정수다. 따라서 $2$ 쌍.

📖 풀이:
핵심: 전체 배치 $3^5$ 에서 비어 있는 상자가 생기는 경우를 포함배제로 뺀다. $3^5-\binom{3}{1}2^5+\binom{3}{2}1^5=243-3\cdot 32+3\cdot 1=243-96+3=150$. (이는 전사함수의 개수 $3!\,S(5,3)=6\cdot 25=150$ 과 일치한다.)

📖 풀이:
핵심: 연결그래프에서 오일러 경로는 홀수 차수 정점이 $0$ 개(회로) 또는 정확히 $2$ 개일 때만 존재하며, 후자에서는 그 두 정점이 경로의 양 끝이 된다. 차수는 $\deg A=3,\ \deg C=3$ 이고 $\deg B=\deg D=\deg E=2$. 홀수 차수 정점이 $A,C$ 둘뿐이므로 $A$ 와 $C$ 를 양 끝으로 하는 오일러 경로가 존재한다. 예: $A\to B\to C\to D\to E\to A\to C$ (간선 6개를 모두 한 번씩 사용).

📖 풀이:
핵심(비둘기집): 부분합 $S_0=0,\ S_k=a_1+\cdots+a_k\ (k=1,\dots,7)$ 의 $8$ 개 값을 $7$ 로 나눈 나머지를 본다. 나머지는 $\{0,1,\dots,6\}$ 의 $7$ 종류뿐이므로 비둘기집 원리에 의해 $S_p\equiv S_q\ (p<q)$ 인 두 값이 존재한다. 그러면 $S_q-S_p=a_{p+1}+\cdots+a_q$ 가 $7$ 의 배수다. 따라서 항상 참.

📖 풀이:
핵심: 위토프 게임의 패배 위치(P-포지션)는 $\big(\lfloor n\varphi\rfloor,\ \lfloor n\varphi^2\rfloor\big),\ \varphi=\tfrac{1+\sqrt 5}{2}$ 로 $(0,0),(1,2),(3,5),(4,7),(6,10),\dots$ 이다. $(5,8)$ 은 이 목록에 없으므로 선공이 이기는 위치다. 두 무더기에서 $1$ 개씩 가져가면 $(4,7)$ 이 되고 이는 P-포지션이므로, 이후 상대가 어떤 수를 두어도 다시 P-포지션으로 되돌릴 수 있어 선공이 승리한다.

📖 풀이:
핵심(톨레미 정리): 원에 내접하는 사각형에서 $AC\cdot BD=AB\cdot CD+BC\cdot DA$ 가 성립한다. 대입하면 $AC\cdot BD=3\cdot 5+4\cdot 6=15+24=39$.

📖 풀이:
핵심: 선형 점화식은 특성방정식의 근으로 일반항을 잡는다.\n특성방정식 $x^2 - 4x + 3 = 0$ 의 근은 $x=1,\ x=3$ 이므로 $a_n = A\cdot 1^n + B\cdot 3^n = A + B\cdot 3^n$.\n초기조건: $a_1 = A + 3B = 2$, $a_2 = A + 9B = 6$. 두 식을 빼면 $6B = 4$ 이지만 다시 정리하면 $A+3B=2,\ A+9B=6 \Rightarrow 6B=4$... 실제로 $9B-3B=6B$, $6-2=4$ 이므로 $B=\tfrac{2}{3}$, $A=0$. 따라서 $a_n = \tfrac{2}{3}\cdot 3^n = 2\cdot 3^{n-1}$.\n검산: $a_1=2,\ a_2=6,\ a_3=18$ 이고 $4\cdot 6 - 3\cdot 2 = 18$ ✓.

📖 풀이:
핵심: 코시 방정식 $f(x+y)=f(x)+f(y)$ 에서 정수·유리수 점은 $f(n)=n\,f(1)$ 로 강제된다.\n$y=x$ 를 반복하면 임의의 양의 정수 $n$ 에 대해 $f(nx) = n f(x)$. 특히 $f(3) = 3f(1) = 12$ 이므로 $f(1) = 4$.\n따라서 $f(7) = 7 f(1) = 7\cdot 4 = 28$.

📖 풀이:
핵심: 역수를 취하면 비선형 점화식이 등차수열로 선형화된다.\n양변의 역수를 취하면 $\dfrac{1}{a_{n+1}} = \dfrac{1+a_n}{a_n} = \dfrac{1}{a_n} + 1$.\n따라서 $\left\{\dfrac{1}{a_n}\right\}$ 은 공차 $1$ 인 등차수열이고 $\dfrac{1}{a_1}=1$ 이므로 $\dfrac{1}{a_n} = n$, 즉 $a_n = \dfrac{1}{n}$.\n그러므로 $a_{10} = \dfrac{1}{10}$.

📖 풀이:
핵심: $n$ 번째 직선은 앞선 $n-1$ 개와 모두 만나 $n$ 개의 조각으로 나뉘고, 각 조각이 영역을 하나씩 추가한다.\n영역 수를 $R_n$ 이라 하면 $R_0 = 1$, $R_n = R_{n-1} + n$.\n따라서 $R_n = 1 + (1+2+\cdots+n) = 1 + \dfrac{n(n+1)}{2}$.\n$n=10$ 이면 $R_{10} = 1 + \dfrac{10\cdot 11}{2} = 1 + 55 = 56$.

📖 풀이:
핵심: $k\cdot k! = (k+1)! - k!$ 라는 망원(telescoping) 항등식을 귀납적으로 활용한다.\n$(k+1)! - k! = k!\,(k+1-1) = k\cdot k!$ 이므로 $\displaystyle\sum_{k=1}^{n} k\cdot k! = \sum_{k=1}^{n}\big[(k+1)! - k!\big] = (n+1)! - 1!$.\n즉 합은 $(n+1)! - 1$. (귀납법으로도: $n=1$ 일 때 $1 = 2!-1$ 성립, 가정 후 $n\to n+1$ 에서 $(n+1)!-1 + (n+1)(n+1)! = (n+2)! - 1$ ✓.)\n$n=5$: $6! - 1 = 720 - 1 = 719$.

📖 풀이:
핵심: $x$ 와 $\tfrac1x$ 를 서로 바꾼 두 식을 연립하여 $f(x)$ 를 소거 없이 풀어낸다.\n주어진 식 $f(x) - 2f(1/x) = x \ \cdots(1)$.\n$x \to 1/x$ 대입: $f(1/x) - 2f(x) = \dfrac{1}{x} \ \cdots(2)$.\n$(1) + 2\times(2)$: $f(x) - 2f(1/x) + 2f(1/x) - 4f(x) = x + \dfrac{2}{x}$, 즉 $-3f(x) = x + \dfrac{2}{x}$.\n따라서 $f(x) = -\dfrac{1}{3}\!\left(x + \dfrac{2}{x}\right) = -\dfrac{x^2+2}{3x}$.\n$f(2) = -\dfrac{4+2}{6} = -1$.