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

📖 풀이:
핵심: 페르마 소정리 $a^{p-1} \equiv 1 \pmod p$ ($p$ 소수, $\gcd(a,p)=1$). 따라서 $3^6 \equiv 1 \pmod 7$. 지수 분해: $100 = 6 \cdot 16 + 4$이므로 $3^{100} = (3^6)^{16} \cdot 3^4 \equiv 1 \cdot 81 \equiv 81 - 11\cdot 7 = 4 \pmod 7$.

📖 풀이:
이중계산(double counting): (학생, 동아리) 가입 쌍 $(s,c)$의 개수 $N$을 두 가지 방식으로 센다. (1) 학생 기준: $N = 10 \times 3 = 30$. (2) 동아리 기준: $N = k \times 5$ ($k$ = 동아리 수). 두 식이 같으므로 $5k = 30$, $k=6$.

📖 풀이:
베이즈 정리: $P(D|+) = \dfrac{P(+|D)P(D)}{P(+|D)P(D) + P(+|\bar D)P(\bar D)}$. 대입하면 $\dfrac{0.99 \times 0.01}{0.99 \times 0.01 + 0.01 \times 0.99} = \dfrac{1}{2}$. 직관: 분모 두 항이 정확히 같아진다(유병률 $\times$ 민감도 $=$ 정상비율 $\times$ 위양성률).

📖 풀이:
오일러 정리: 연결 그래프에서 오일러 회로 $\iff$ 모든 정점의 차수가 짝수. 본 그래프의 차수는 $(2,2,4,2,2)$로 모두 짝수이고 연결되어 있으므로 회로 존재. 예: $V_1 \to V_2 \to V_3 \to V_4 \to V_5 \to V_3 \to V_1$.

📖 풀이:
두 구간으로 분할. $(0,0) \to (2,3)$ 경로 수: 오른쪽 2번 + 위 3번 = $\binom{5}{2} = 10$. $(2,3) \to (5,5)$ 경로 수: 오른쪽 3번 + 위 2번 = $\binom{5}{2} = 10$. 곱의 법칙으로 총 $10 \times 10 = 100$.

📖 풀이:
기하확률: 확률 = (조건 영역 넓이) / (전체 넓이). 조건은 $Y > X + \frac{1}{2}$ 또는 $Y < X - \frac{1}{2}$. 각 영역은 직각이등변삼각형으로 다리 길이 $\frac{1}{2}$, 넓이 $\frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{8}$. 두 영역의 합 $= \frac{1}{4}$.

📖 풀이:
하한: 피터슨 그래프에 5각형(홀수 사이클)이 포함되어 있으므로 $\chi \geq 3$ (2색으로는 홀수 사이클 불가). 상한: 실제 3색 칠하기 존재. 예) 외부 5각형을 $1,2,1,2,3$으로, 내부는 충돌을 피해 $2,3,3,1,2$ 등으로 배정. 따라서 $\chi = 3$.

📖 풀이:
불변량 논증: 체스판을 흑백 교대 색칠. 좌상·우하 모서리는 같은 색(예: 둘 다 흰색). 제거 후 남은 칸은 흰색 $30$개, 검은색 $32$개. 도미노 하나는 반드시 흰 1칸 + 검은 1칸을 덮으므로 도미노 $31$개는 흰 $31$, 검 $31$을 덮어야 함. 색깔 수가 불일치($30 \neq 31$)하므로 불가능.

📖 풀이:
$65 = 5 \times 13$이고 두 소인수 모두 $4k+1$형. 원시 피타고라스 트리플과 그 배수 모두 고려: (i) $3$-$4$-$5$ 배 $13$: $(39, 52, 65)$. (ii) $5$-$12$-$13$ 배 $5$: $(25, 60, 65)$. (iii) 원시 트리플 1: $(16, 63, 65)$ ($16^2 + 63^2 = 256 + 3969 = 4225$). (iv) 원시 트리플 2: $(33, 56, 65)$ ($33^2 + 56^2 = 1089 + 3136 = 4225$). 총 $4$쌍.

📖 풀이:
포함배제 원리. $A_k = \{n \leq 1000 : k \mid n\}$이라 두면 $|A_2|=500$, $|A_3|=333$, $|A_5|=200$, $|A_6|=166$, $|A_{10}|=100$, $|A_{15}|=66$, $|A_{30}|=33$. $|A_2 \cup A_3 \cup A_5| = 500+333+200 - 166-100-66 + 33 = 734$. 따라서 답 $= 1000 - 734 = 266$. 검산: $1000 \times \frac{1}{2}\cdot\frac{2}{3}\cdot\frac{4}{5} = \frac{4}{15} \times 1000 \approx 266.67$.

📖 풀이:
Sprague-Grundy 이론: Nim의 승패는 모든 더미 크기의 이진 XOR(nim-sum)으로 결정된다. XOR $= 0$이면 현재 둘 차례인 사람이 짐(P-position), 아니면 이김. 계산: $2 \oplus 4 \oplus 7 = 010 \oplus 100 \oplus 111 = 001 = 1 \neq 0$, 따라서 첫 플레이어 승. 이기는 수는 nim-sum을 $0$으로 만드는 것인데, 각 더미를 $p \to p \oplus 1$로 바꿔 보면 $2 \to 3$, $4 \to 5$는 오히려 커져 불가능하고 오직 $7 \oplus 1 = 6 < 7$인 $7$ 더미만 줄일 수 있다. $7 \to 6$($1$개 제거)하면 $2 \oplus 4 \oplus 6 = 010 \oplus 100 \oplus 110 = 000$이 되어, 이것이 유일한 승리 첫수다.

📖 풀이:
한 줄 요약: 윌슨 정리로 바로 결정된다.

윌슨 정리: 소수 $p$ 에 대해 $(p-1)! \equiv -1 \pmod{p}$.
$11$ 은 소수이므로 $10! \equiv -1 \equiv 10 \pmod{11}$.

검증: 작은 케이스 $p=5$ 의 경우 $4! = 24 \equiv -1 \pmod 5$ 임을 확인하면 같은 원리이다.

📖 풀이:
한 줄 요약: $5$ 로 나눈 나머지의 종류는 $5$ 가지이므로 비둘기집 원리를 쓴다.

정수를 $5$ 로 나눈 나머지는 $\{0,1,2,3,4\}$ 의 $5$ 가지이다.
- $n = 5$ 이면 모든 나머지가 다를 수 있다 (예: $0,1,2,3,4$ 자체) — 차가 $5$ 의 배수인 쌍이 보장되지 않는다.
- $n = 6$ 이면 비둘기집 원리에 의해 적어도 두 수가 같은 나머지를 가진다. 같은 나머지인 두 수의 차는 $5$ 의 배수.

따라서 답은 $6$.

📖 풀이:
한 줄 요약: 중국인 나머지정리(CRT)로 두 식씩 결합한다.

1단계 ($x \equiv 2 \pmod 3, x \equiv 3 \pmod 5$): $x = 5k+3$ 로 놓으면 $5k+3 \equiv 2 \pmod 3 \Rightarrow 2k \equiv -1 \equiv 2 \pmod 3 \Rightarrow k \equiv 1 \pmod 3$. 즉 $x \equiv 8 \pmod{15}$.

2단계 ($x \equiv 8 \pmod{15}, x \equiv 2 \pmod 7$): $x = 15m + 8$ 로 놓으면 $15m + 8 \equiv 2 \pmod 7 \Rightarrow m + 1 \equiv 2 \pmod 7 \Rightarrow m \equiv 1 \pmod 7$. 즉 $x = 105n + 23$.

최소 양의 정수: $x = 23$. 검증: $23 = 3\cdot 7+2$, $23 = 5\cdot 4+3$, $23 = 7\cdot 3+2$. 모두 성립.

📖 풀이:
한 줄 요약: 통분 후 AM-GM 으로 $xy$ 의 최댓값을 구한다.

$\dfrac{1}{x} + \dfrac{1}{y} = \dfrac{x+y}{xy} = \dfrac{10}{xy}$.

AM-GM: $\sqrt{xy} \le \dfrac{x+y}{2} = 5 \Rightarrow xy \le 25$. 등호는 $x = y = 5$ 에서.

따라서 $\dfrac{1}{x} + \dfrac{1}{y} \ge \dfrac{10}{25} = \dfrac{2}{5}$. 최솟값은 $\dfrac{2}{5}$.

📖 풀이:
한 줄 요약: $\binom{5}{3}=10$ 부분집합에서 사이클을 포함하는 것을 제외한다.

신장트리는 $4-1 = 3$ 개의 간선으로 이루어진다. 전체 간선 $5$ 개 중 $3$ 개 고르기: $\binom{5}{3} = 10$.

이 중 사이클을 형성하는 부분집합:
- $\{V_1V_2, V_2V_3, V_1V_3\}$: 삼각형
- $\{V_1V_3, V_3V_4, V_4V_1\}$: 삼각형

사각형 $V_1V_2V_3V_4V_1$ 자체는 $4$ 개 간선이므로 $3$ 개 부분집합으로 사이클을 만들 수 없다.

사이클이 있는 경우 $2$ 가지 제외 $\Rightarrow 10 - 2 = 8$.

참고: 키르히호프 행렬-트리 정리로도 확인 가능하다.

📖 풀이:
한 줄 요약: $y$ 범위와 합동조건을 결합한다.

$x = \dfrac{100 - 7y}{3} \ge 0$ 이므로 $y \le 14$. 또한 $100 - 7y \equiv 0 \pmod 3 \Rightarrow 1 - y \equiv 0 \pmod 3 \Rightarrow y \equiv 1 \pmod 3$.

조건 $0 \le y \le 14, y \equiv 1 \pmod 3$ 을 만족하는 $y$ 는 $\{1, 4, 7, 10, 13\}$ 의 $5$ 개.

각각의 $x$: $(31, 1), (24, 4), (17, 7), (10, 10), (3, 13)$. 모두 비음정수. ∴ 해는 $5$ 개.

📖 풀이:
한 줄 요약: 코너 분석으로 모든 $3\times 3$ 동작이 홀수 번 사용되어야 하지만, 중간 셀이 모순을 일으킨다.

$3 \times 3$ 부분격자의 좌상단을 $(i, j)$ ($1 \le i, j \le 3$) 라 하고 이를 $A_{i,j}$ 라 한다. 총 $9$ 개의 가능한 동작. 동작 $A_{i,j}$ 를 $a_{i,j} \in \{0,1\}$ 번 (GF(2)) 적용한다고 보자.

셀 $(1,1)$ 은 오직 $A_{1,1}$ 에만 속한다. 모든 동전이 뒤집히려면 $a_{1,1} \equiv 1 \pmod 2$. 마찬가지로 모든 모서리 분석으로 $a_{1,1}, a_{1,3}, a_{3,1}, a_{3,3}$ 모두 $\equiv 1$.

셀 $(1,3)$ 은 $A_{1,1}, A_{1,2}, A_{1,3}$ 에 속한다. 양 끝이 $1$ 이므로 $a_{1,2} \equiv 1$. 같은 식으로 $a_{2,1}, a_{2,3}, a_{3,2} \equiv 1$.

셀 $(3,3)$ 은 모든 $9$ 개 부분격자에 속한다. 위에서 $8$ 개가 $1$ 이므로 $a_{2,2} \equiv 1$ 이어야 한다.

그러나 셀 $(2,2)$ 는 $A_{1,1}, A_{1,2}, A_{2,1}, A_{2,2}$ 의 $4$ 개에만 속하며, 각각 $1$ 이므로 뒤집힌 횟수 $\equiv 4 \equiv 0 \pmod 2$. 이는 "뒤집힘"이 아니므로 모순. ∴ 불가능.

📖 풀이:
한 줄 요약: 누적합과 비둘기집의 고전적 결합.

누적합을 $S_0 = 0, S_k = a_1 + a_2 + \cdots + a_k$ ($k = 1, \dots, n$) 로 정의하면 총 $n+1$ 개의 값.

$n$ 으로 나눈 나머지는 $\{0, 1, \dots, n-1\}$ 의 $n$ 가지. 비둘기집 원리로 $0 \le i < j \le n$ 인 $S_i \equiv S_j \pmod n$ 이 존재.

그러면 $a_{i+1} + a_{i+2} + \cdots + a_j = S_j - S_i \equiv 0 \pmod n$ 이며, 이는 비공집합 연속 부분합 (또한 부분집합).

특히 $i = 0$ 이면 시작부터의 누적합 자체가 $n$ 의 배수이다.

📖 풀이:
한 줄 요약: 카탈란 수의 닫힌 형식을 적용한다.

카탈란 수: $C_n = \dfrac{1}{n+1} \binom{2n}{n}$.

$C_5 = \dfrac{1}{6} \binom{10}{5} = \dfrac{252}{6} = 42$.

반사 원리 (Andre's reflection) 의 증명: 전체 길이 $2n$ 의 $\pm 1$ 수열 중 $0$ 에서 끝나는 것은 $\binom{2n}{n}$. "나쁜" 수열 (어느 시점에 $-1$ 도달) 은 첫 $-1$ 시점에서 반사하면 $\binom{2n}{n-1}$ 와 일대일 대응. 따라서 좋은 수열 수 = $\binom{2n}{n} - \binom{2n}{n-1} = \dfrac{1}{n+1}\binom{2n}{n}$.

📖 풀이:
한 줄 요약: $g(x) = f(x) - x^2$ 로 치환하면 코시 함수방정식이 된다.

$g(x) := f(x) - x^2$ 로 놓자. 그러면
$g(x+y) = f(x+y) - (x+y)^2 = (f(x) + f(y) + 2xy) - (x^2 + 2xy + y^2) = (f(x) - x^2) + (f(y) - y^2) = g(x) + g(y)$.

따라서 $g$ 는 가법함수. 양의 정수에 대해 귀납으로 $g(n) = n \cdot g(1) = n(f(1) - 1) = 2n$. 즉 $f(n) = n^2 + 2n$.

검증 (귀납): $f(1) = 1 + 2 = 3$. $f(n+1) = f(n) + f(1) + 2n = (n^2 + 2n) + 3 + 2n = (n+1)^2 + 2(n+1)$. ✓

$\therefore f(10) = 100 + 20 = 120$.

📖 풀이:
한 줄 요약: 멱점 정리 $PT^2 = PA \cdot PB$ 직접 적용.

점 $P$ 의 원 $O$ 에 대한 멱(power)은 $\mathrm{pow}(P) = PA \cdot PB = PT^2$ (접선의 제곱) 으로 정의되며 두 표현은 같다.

증명 스케치: 삼각형 $PTA$ 와 $PBT$ 는 닮음 (접선-현 사이 각 = 원주각). 즉 $\angle PTA = \angle PBT$ (접현각 정리), $\angle P$ 공통. AA 닮음으로 $\dfrac{PT}{PB} = \dfrac{PA}{PT}$, 즉 $PT^2 = PA \cdot PB$.

대입: $PT^2 = 4 \cdot 9 = 36$. $\therefore PT = 6$.

📖 풀이:
한 줄 요약: 예각 $\Leftrightarrow$ 세 호의 길이가 모두 반원 미만.

핵심 관찰: 삼각형 $ABC$ 가 예각 $\Leftrightarrow$ 원의 중심 $O$ 가 삼각형 내부 $\Leftrightarrow$ $A, B, C$ 가 나누는 세 호 모두 길이가 원주의 절반 미만 (반원 미만).

계산: 원주를 $1$ 로 정규화하고 $A = 0$ 으로 고정. $B, C$ 의 위치를 $X, Y$ 라 하면 $(X, Y)$ 는 $[0,1]^2$ 균일분포.

세 호의 길이를 $u, v - u, 1 - v$ (단, $u = \min(X, Y), v = \max(X, Y)$) 로 쓰면 모두 $< 1/2$ 인 영역:
$u < 1/2,\ v - u < 1/2,\ 1 - v < 1/2$ 즉 $1/2 < v$ 와 $v - 1/2 < u < 1/2$.

순서통계량의 결합밀도 (순서 있는 경우) 는 $2$.
$P = \displaystyle \int_{1/2}^{1} \int_{v - 1/2}^{1/2} 2 \, du \, dv = \int_{1/2}^{1} 2(1 - v) \, dv = 2 \cdot \left[ v - \dfrac{v^2}{2} \right]_{1/2}^{1} = 2 \cdot \dfrac{1}{8} = \dfrac{1}{4}$.

$\therefore P(\text{예각}) = \dfrac{1}{4}$.

📖 풀이:
핵심 아이디어: 일계 비제차 점화식 $a_{n+1} = 3a_n - 2$를 $a_{n+1} - 1 = 3(a_n - 1)$ 형태로 변형한다.

[단계 1] 고정점 찾기: $L = 3L - 2 \Rightarrow L = 1$.
[단계 2] 치환 $b_n = a_n - 1$. 그러면 $b_{n+1} = 3b_n$, $b_1 = 1$.
[단계 3] 등비수열이므로 $b_n = 3^{n-1}$, 즉 $a_n = 3^{n-1} + 1$.
[단계 4] $a_5 = 3^4 + 1 = 81 + 1 = 82$.

검산: $a_1=2, a_2=4, a_3=10, a_4=28, a_5=82$. ✓

📖 풀이:
핵심 아이디어: "부분 = 전체 - 앞부분" 으로 분해.

[단계 1] $1 + 3 + \cdots + 99$는 처음 50개의 홀수 합. 공식에 의해 $50^2 = 2500$.
[단계 2] $1 + 3 + \cdots + 49$는 처음 25개의 홀수 합. $25^2 = 625$.
[단계 3] 따라서 $51 + 53 + \cdots + 99 = 2500 - 625 = 1875$.

(귀납법 증명) $n=1$일 때 $1 = 1^2$. $n=k$ 가정 시 $1+\cdots+(2k-1)=k^2$이면, $n=k+1$일 때 $k^2 + (2k+1) = (k+1)^2$. ∎