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

📖 풀이:
핵심 아이디어: 표본공간을 출생 순서를 포함해 나열한 뒤 조건부 확률 정의를 적용.

[단계 1] 표본공간: $\{BB, BG, GB, GG\}$, 각 확률 $1/4$.
[단계 2] 사건 $A$ = "적어도 한 명 남아" $= \{BB, BG, GB\}$, $P(A) = 3/4$.
[단계 3] 사건 $B$ = "둘 다 남아" $= \{BB\}$, $P(A \cap B) = 1/4$.
[단계 4] $P(B \mid A) = \dfrac{P(A \cap B)}{P(A)} = \dfrac{1/4}{3/4} = \dfrac{1}{3}$.

직관 함정: "나머지 한 명도 남아일 확률 $1/2$"라고 답하기 쉽지만, 정보가 "특정한 한 명"이 아니라 "적어도 한 명"이므로 표본공간이 달라진다.

📖 풀이:
핵심 아이디어: 두 절단점 $(x, y)$를 단위정사각형 위의 점으로 보고, 삼각형 조건을 좌표 부등식으로 환원.

[단계 1] 가정 $y > x$. 세 조각의 길이는 $x, y-x, 1-y$.
[단계 2] 삼각형 조건은 "가장 긴 변 < 나머지 두 변의 합" 즉 모든 조각이 $1/2$ 미만이어야 한다.
- $x < 1/2$
- $y - x < 1/2$
- $1 - y < 1/2 \Rightarrow y > 1/2$
[단계 3] 이 영역은 꼭짓점 $(0, 1/2), (1/2, 1/2), (1/2, 1)$인 삼각형, 넓이 $1/8$.
[단계 4] $y < x$ 영역도 대칭이므로 똑같이 $1/8$. 합 $= 1/4$.

결론: 확률 $= \boxed{1/4}$.

📖 풀이:
핵심 아이디어: 비둘기집 원리 + 케이스 분석.

[단계 1] $n \geq 6$이면 항상 가능함을 보임. 임의의 한 사람 $A$를 잡으면, 나머지 5명과의 관계는 "친구"/"모르는사이" 둘 중 하나. 비둘기집에 의해 적어도 $\lceil 5/2 \rceil = 3$명이 같은 종류 (예: 모두 $A$의 친구).
[단계 2] 그 3명을 $B, C, D$라 하자. $B, C, D$ 중 어떤 두 명이 친구라면, 그들과 $A$로 친구 3인조 형성. 셋 다 서로 모르는 사이면, $\{B, C, D\}$가 서로 모르는 3인조.
[단계 3] $n = 5$로는 부족한 예시: 5명을 정오각형 정점에, 5개 변은 빨간색(친구), 5개 대각선은 파란색(모르는사이). 어떤 단색 삼각형도 없음. (오각형 그래프 $C_5$와 그 보그래프 모두 삼각형 free.)

결론: 최소값은 $\boxed{6}$. 즉 $R(3,3) = 6$.

📖 풀이:
핵심 아이디어: $a + b + ab = (1+a)(1+b) - 1$이라는 항등식. 따라서 $\prod_i (1 + a_i)$가 불변량.

[단계 1] 두 수 $a, b$를 $a + b + ab$로 바꾸면 $1 + (a+b+ab) = (1+a)(1+b)$.
[단계 2] 즉 칠판 위 모든 수에 1을 더한 값들의 곱은 매 단계마다 동일하다 (두 인자가 한 인자로 합쳐질 뿐 곱은 같음).
[단계 3] 초기 곱: $(1+1)(1+2)(1+3)\cdots(1+100) = 2 \cdot 3 \cdot 4 \cdots 101 = 101!$.
[단계 4] 99번 후 한 수 $x$만 남으면 $1 + x = 101!$, 즉 $x = 101! - 1$.

📖 풀이:
핵심 아이디어: 코시-슈바르츠 부등식의 엥겔(Titu) 형태 $\sum \dfrac{x_i^2}{y_i} \geq \dfrac{(\sum x_i)^2}{\sum y_i}$.

[단계 1] 분모들의 합: $(b+c) + (c+a) + (a+b) = 2(a+b+c) = 2$.
[단계 2] 분자들의 합: $a + b + c = 1$.
[단계 3] 엥겔 형태에 의해 $\dfrac{a^2}{b+c} + \dfrac{b^2}{c+a} + \dfrac{c^2}{a+b} \geq \dfrac{(a+b+c)^2}{2(a+b+c)} = \dfrac{1}{2}$.
[단계 4] 등호는 $\dfrac{a}{b+c} = \dfrac{b}{c+a} = \dfrac{c}{a+b}$, 즉 $a = b = c = 1/3$일 때 성립.

결론: 최솟값 $= \boxed{1/2}$.

📖 풀이:
핵심 아이디어: 선택된 $5$개의 수 $a_1 < a_2 < \cdots < a_5$에 대해 $b_i = a_i - (i-1)$로 치환하면 연속 금지 조건이 단순한 "서로 다름"으로 환원된다 (격자점-비연속 ↔ 격자점-자유 일대일 대응).

[단계 1] $a_{i+1} \geq a_i + 2$ 조건은 $b_{i+1} = a_{i+1} - i \geq a_i + 2 - i = b_i + 1$, 즉 $b_1 < b_2 < \cdots < b_5$.
[단계 2] 또한 $b_1 = a_1 \geq 1$, $b_5 = a_5 - 4 \leq 20 - 4 = 16$. 따라서 $b_i \in \{1, 2, \ldots, 16\}$이고 서로 다르며 증가.
[단계 3] 이는 $\{1, \ldots, 16\}$에서 $5$개를 고르는 방법과 일대일 대응: $\dbinom{16}{5} = 4368$.

일반 공식: $n$ 중 $k$개를 연속하지 않게 뽑는 방법은 $\dbinom{n-k+1}{k}$.

📖 풀이:
핵심 아이디어: $B$를 중심으로 $60°$ 회전하여 세 길이 $3, 4, 5$를 한 삼각형에 모은다 (페르마 점 회전 트릭).

[단계 1] $\triangle BPC$를 점 $B$를 중심으로 시계반대방향 $60°$ 회전. 정삼각형이므로 $C \mapsto A$. $P \mapsto P'$라 하면 $BP' = BP = 4$, $P'A = PC = 5$.
[단계 2] $\triangle BPP'$: $BP = BP' = 4$, $\angle PBP' = 60°$, 따라서 정삼각형. $PP' = 4$.
[단계 3] $\triangle APP'$: 세 변 $PA = 3$, $PP' = 4$, $P'A = 5$. $3^2 + 4^2 = 5^2$이므로 $\angle APP' = 90°$ (피타고라스 역).
[단계 4] $\angle APB = \angle APP' + \angle P'PB = 90° + 60° = 150°$.
[단계 5] $\triangle APB$에 코사인 법칙 적용:
$$AB^2 = 3^2 + 4^2 - 2 \cdot 3 \cdot 4 \cdot \cos 150° = 9 + 16 - 24 \cdot \left(-\dfrac{\sqrt{3}}{2}\right) = 25 + 12\sqrt{3}.$$

결론: $AB^2 = \boxed{25 + 12\sqrt{3}}$.

📖 풀이:
핵심 아이디어: 와이토프 게임의 P-포지션(이전 플레이어 필승 = 차례인 사람 필패)은 황금비 $\varphi = \dfrac{1+\sqrt{5}}{2}$를 이용해 $(\lfloor n\varphi \rfloor, \lfloor n\varphi^2 \rfloor)$ (단, $n = 0, 1, 2, \ldots$)로 표현된다 (베티 정리).

[단계 1] 작은 P-포지션 나열: $n=0: (0,0)$, $n=1: (1,2)$, $n=2: (3,5)$, $n=3: (4,7)$, $n=4: (6,10)$, $n=5: (8,13)$, $\ldots$
[단계 2] $(4, 7)$이 정확히 $n=3$의 P-포지션. P-포지션에서 시작하면 어떤 합법 수를 두어도 N-포지션(차례인 사람 필승)으로 옮겨가고, 상대는 항상 P-포지션으로 되돌려 놓을 수 있다.
[단계 3] 따라서 $(4,7)$에서 차례인 첫 번째 사람은 무엇을 하든 패배하고, 두 번째 사람이 필승.

[검증] 한 가지 수순 예: 선공이 $(4,7) \to (4,3)$ (오른쪽 무더기에서 $4$개)으로 두면, 후공은 두 무더기에서 $2$개씩 가져가 $(4,3) \to (2,1) = (1,2)$로 P-포지션에 복귀한다. 이어 선공이 $(1,2)$에서 무엇을 두든(예: $(1,2) \to (1,1)$) 후공은 두 무더기에서 같은 수를 가져가 $(0,0)$으로 만들어 마지막 돌을 가져간다. 선공이 다른 첫수를 두어도 후공은 같은 원리로 늘 가장 가까운 P-포지션으로 되돌릴 수 있다.

결론: 두 번째 사람 필승.

📖 풀이:
핵심: 13이 소수이므로 페르마 소정리에 의해 $2^{12} \equiv 1 \pmod{13}$.
단계 1) $100 = 12 \cdot 8 + 4$이므로 $2^{100} = (2^{12})^{8} \cdot 2^{4} \equiv 1^{8} \cdot 16 \pmod{13}$.
단계 2) $16 = 13 + 3$이므로 $16 \equiv 3 \pmod{13}$. 따라서 나머지는 $3$.

📖 풀이:
핵심: $\gcd(7, 11) = 1$이 100을 나누므로 정수해 존재.
단계 1) $7x \equiv 100 \pmod{11}$, 즉 $7x \equiv 1 \pmod{11}$.
단계 2) $7 \cdot 8 = 56 \equiv 1 \pmod{11}$이므로 $x \equiv 8 \pmod{11}$.
단계 3) 일반해 $x = 8 + 11t,\ y = 4 - 7t$.
단계 4) 양정수 조건 $x \geq 1,\ y \geq 1$에서 $t \geq 0$이면서 $t \leq 3/7$. 즉 $t = 0$. 해는 $(8, 4)$ 단 하나.

📖 풀이:
핵심: $T_n$을 $n$칸 오르는 방법 수라 하면 마지막 한 걸음이 1·2·3 중 하나이므로 $T_n = T_{n-1} + T_{n-2} + T_{n-3}$ (트리보나치 점화).
단계 1) 초기값: $T_1 = 1,\ T_2 = 2,\ T_3 = 4$.
단계 2) $T_4 = 4 + 2 + 1 = 7$.
단계 3) $T_5 = 7 + 4 + 2 = 13$.

📖 풀이:
핵심: 면 단위로 표본공간을 정의한다 (카드 단위 아님!).
단계 1) 총 6개의 면 중 빨강 면은 3개.
단계 2) 그 3개의 빨강 면 중 '반대편도 빨강'인 것은 카드A의 두 면, 즉 2개.
단계 3) 조건부확률 $P(\text{반대면 빨강} \mid \text{보이는 면 빨강}) = \dfrac{2}{3}$.
흔한 오답 $\frac{1}{2}$은 '카드'를 표본공간으로 잘못 잡았기 때문.

📖 풀이:
핵심: '마지막 두 자리'는 $\pmod{100}$의 나머지.
단계 1) $7^1 = 7,\ 7^2 = 49,\ 7^3 \equiv 43,\ 7^4 = 2401 \equiv 1 \pmod{100}$. 따라서 $7$의 100에 대한 위수는 4.
단계 2) $2026 = 4 \cdot 506 + 2$이므로 $7^{2026} \equiv 7^{2} = 49 \pmod{100}$.
참고: 오일러 토션트 $\phi(100) = 40$도 같은 결론을 주지만, 실제 위수는 4로 더 작다.

📖 풀이:
핵심: 이 조건의 경로 수는 카탈란 수 $C_n = \dfrac{1}{n+1}\binom{2n}{n}$.
단계 1) 총 자유 경로 수는 $\binom{10}{5} = 252$.
단계 2) 거울 원리(반사 보조정리): $y > x$를 침범한 경로는 시작점을 $y=x+1$에 대해 반사하여 $(-1, 1)$에서 $(5,5)$로 가는 경로와 1대1 대응 — 그 수는 $\binom{10}{4} = 210$.
단계 3) $252 - 210 = 42 = C_5$.

📖 풀이:
핵심: 이 방정식은 펠 방정식의 변형으로, 해는 점화 관계로 생성된다.
단계 1) 단위 해 $(x_1, y_1) = (3, 1)$에서 다음 해는 점화
$$x_{n+1} = \frac{3x_n + 5y_n}{2}, \quad y_{n+1} = \frac{x_n + 3y_n}{2}.$$
단계 2) $(3,1) \to (7, 3) \to \left(\dfrac{21 + 15}{2}, \dfrac{7 + 9}{2}\right) = (18, 8)$.
단계 3) 검산: $18^2 - 5 \cdot 8^2 = 324 - 320 = 4$ ✓.
단계 4) $x + y = 18 + 8 = 26$.

📖 풀이:
핵심: 악수 정리 — 모든 정점의 차수의 합은 간선 수의 2배.
단계 1) 각 사람을 정점, 악수를 간선으로 보는 그래프 $G$에서 모든 정점의 차수는 4.
단계 2) 차수합 $= 7 \cdot 4 = 28$.
단계 3) $\sum \deg(v) = 2|E|$이므로 $|E| = 14$. 따라서 악수는 총 14회.

📖 풀이:
핵심: 균등분포에서 확률 = (호의 면적 비) = (정삼각형 넓이) / (원 넓이).
단계 1) 단위원에 내접하는 정삼각형의 한 변 길이는 $a = \sqrt{3}$ (외접원 반지름 공식 $R = \dfrac{a}{\sqrt{3}}$에서 $a = R\sqrt{3} = \sqrt{3}$).
단계 2) 정삼각형 넓이 $= \dfrac{\sqrt{3}}{4} a^{2} = \dfrac{\sqrt{3}}{4} \cdot 3 = \dfrac{3\sqrt{3}}{4}$.
단계 3) 원 넓이 $= \pi$.
단계 4) 확률 $= \dfrac{3\sqrt{3}/4}{\pi} = \dfrac{3\sqrt{3}}{4\pi} \approx 0.4135$.

📖 풀이:
핵심: 직접 단계 계산 + 일반항 검증.
단계 1) $a_1 = 1$.
단계 2) $a_2 = 2 \cdot 1 + 1 = 3$.
단계 3) $a_3 = 2 \cdot 3 + 2 = 8$.
단계 4) $a_4 = 2 \cdot 8 + 3 = 19$.
단계 5) $a_5 = 2 \cdot 19 + 4 = 42$.
단계 6) $a_6 = 2 \cdot 42 + 5 = 89$.
검증(일반항): 풀이하면 $a_n = 3 \cdot 2^{n-1} - n - 1$. $n=6$: $3 \cdot 32 - 6 - 1 = 96 - 7 = 89$ ✓.

📖 풀이:
핵심: $\pmod{41}$로 인수분해.
단계 1) $n^2 + n + 41 \equiv 0 \pmod{41} \iff n^2 + n \equiv 0 \pmod{41}$.
단계 2) $n(n + 1) \equiv 0 \pmod{41}$. 41이 소수이므로 $n \equiv 0$ 또는 $n \equiv -1 \equiv 40 \pmod{41}$.
단계 3) 양의 정수 중 최소는 $n = 40$. (확인: $40^2 + 40 + 41 = 1681 = 41^2$. 정말로 41의 배수.)

📖 풀이:
핵심: 대입을 통한 배각 공식 유도.
단계 1) 주어진 식에 $y = x$ 대입:
$$f(2x) + f(0) = 2 f(x)^{2}.$$
단계 2) $f(0) = 1$이므로 $f(2x) = 2 f(x)^{2} - 1$.
단계 3) $x = 1$ 대입: $f(2) = 2 f(1)^{2} - 1 = 2 \cdot 0 - 1 = -1$.
참고: 이 함수방정식은 코사인 형태 $f(x) = \cos(\theta x)$를 일반화하며, 실제로 $f(x) = \cos\!\left(\dfrac{\pi x}{2}\right)$가 한 해이다.

📖 풀이:
핵심: 합동식으로 $y$ 의 후보 좁히기. $3x = 47 - 5y > 0$ 이므로 $y \leq 9$. $47 \equiv 2, 5y \equiv 2y \pmod 3$ 이므로 $2y \equiv 2 \pmod 3$, 즉 $y \equiv 1 \pmod 3$. 따라서 $y \in \{1, 4, 7\}$ 이고 각각 $x = 14, 9, 4$. 총 3개.

📖 풀이:
핵심: 두 구간으로 쪼개어 곱한다. $(0,0) \to (2,3)$ 경로 수는 $\binom{2+3}{2} = \binom{5}{2} = 10$. $(2,3) \to (5,5)$ 경로 수는 $\binom{3+2}{3} = \binom{5}{2} = 10$. 두 구간이 독립이므로 $10 \times 10 = 100$.

📖 풀이:
핵심: $n \geq 5$ 이면 $n!$ 은 $10$ 의 배수이므로 일의 자리는 $0$. 따라서 일의 자리는 $1! + 2! + 3! + 4! = 1 + 2 + 6 + 24 = 33$ 의 일의 자리 $3$. 답: $3$.

📖 풀이:
핵심: $f$ 는 곱셈을 덧셈으로 바꾸므로 로그와 유사하게 작용. $72 = 2^3 \cdot 3^2$. $f(2^3) = 3 f(2) = 3$, $f(3^2) = 2 f(3) = 4$. 따라서 $f(72) = f(2^3) + f(3^2) = 3 + 4 = 7$.

📖 풀이:
핵심: 면적비. 곡선 $y = x^2$ 위쪽 영역의 면적 $= \int_0^1 (1 - x^2)\, dx = \left[x - \frac{x^3}{3}\right]_0^1 = 1 - \frac{1}{3} = \frac{2}{3}$. 정사각형 면적이 1이므로 확률은 $\frac{2}{3}$.