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

📖 풀이:
핵심 아이디어: 반사 원리(reflection principle). 전체 경로 수 $= \binom{7+5}{5} = \binom{12}{5} = 792.$ '나쁜 경로'는 어느 시점에서 $y = x+1$ 선 (위쪽 경계 너머)에 닿는 경로. 첫 닿는 순간 이전 부분을 $y = x+1$ 직선에 대해 반사하면, 시작점 $(0,0)$ 이 $(-1, 1)$ 로 옮겨지고 이는 $(-1, 1) \to (7, 5)$ 로 가는 격자경로와 일대일 대응. 그 수는 오른쪽 $8$, 위 $4$ 이동이므로 $\binom{12}{4} = 495.$ 따라서 좋은 경로 수 $= 792 - 495 = 297.$

📖 풀이:
핵심: 점 $P$ 에 대한 원의 멱 (Power of a Point). 외부 점 $P$ 에서의 접선의 길이의 제곱은 임의의 할선이 원과 만나는 두 점까지의 거리의 곱과 같다: $PT^2 = PA \cdot PB.$ $PB = PA + AB = 4 + 12 = 16.$ 따라서 $PT^2 = 4 \cdot 16 = 64$, $PT = 8.$ (증명 약식: $\triangle PTA \sim \triangle PBT$, 접현각 = 원주각 이용.)

📖 풀이:
핵심: 선형 점화식의 특성방정식. 특성방정식 $x^2 - 5x + 6 = 0,$ 즉 $(x-2)(x-3) = 0$ 의 근은 $x = 2, 3.$ 일반해 형태 $a_n = A \cdot 2^n + B \cdot 3^n.$ 초기조건: $a_1 = 2A + 3B = 1,\ a_2 = 4A + 9B = 5.$ 첫 식 $\times 2$ 를 둘째에서 빼면 $3B = 3,$ 즉 $B = 1,\ A = -1.$ 따라서 $a_n = 3^n - 2^n.$ 검증: $a_3 = 27 - 8 = 19 = 5 \cdot 5 - 6 \cdot 1$ ✓.

📖 풀이:
핵심: $\varphi$ 는 곱셈적 함수이고 소인수분해에서 바로 계산된다. $36 = 2^2 \cdot 3^2$ 이므로 $$\varphi(36) = 36\left(1-\tfrac{1}{2}\right)\left(1-\tfrac{1}{3}\right) = 36 \cdot \tfrac{1}{2} \cdot \tfrac{2}{3} = 12.$$ 실제로 $1,5,7,11,13,17,19,23,25,29,31,35$ 의 12개가 36과 서로소다.

📖 풀이:
핵심: 두 꼭짓점을 잇는 모든 선분에서 변을 빼면 된다. 꼭짓점 8개 중 2개를 고르는 선분은 $\binom{8}{2}=28$ 개, 이 중 변이 8개이므로 대각선은 $28-8=20$ 개. 일반식은 $\frac{n(n-3)}{2}=\frac{8\cdot 5}{2}=20$.

📖 풀이:
핵심: 기댓값의 선형성과 지시확률변수를 쓰면 분포 전체를 구할 필요가 없다. $i$ 번째 사람이 자기 모자를 집는 사건의 지시변수 $X_i$ 는 $E[X_i]=\Pr(X_i=1)=\tfrac{1}{5}$. 전체 수 $X=\sum_{i=1}^{5}X_i$ 이므로 $$E[X]=\sum_{i=1}^{5}E[X_i]=5\cdot\tfrac{1}{5}=1.$$ 사람 수 $n$ 에 무관하게 항상 $1$ 이다.

📖 풀이:
핵심: 코시-슈바르츠 부등식 $(1^2+1^2+1^2)(x^2+y^2+z^2)\ge (x+y+z)^2$ 를 적용한다. $$3(x^2+y^2+z^2)\ge 12^2=144 \;\Rightarrow\; x^2+y^2+z^2\ge 48.$$ 등호는 $x=y=z=4$ 일 때 성립하므로 최솟값은 $48$. (제곱평균-산술평균 관계와 동치.)

📖 풀이:
핵심: 그런디(Grundy) 분석에서 $g(n)=n \bmod 4$ 이고, $4$ 의 배수가 패배(P) 위치다. 후공은 '선공이 $k$ 개 가져가면 자신은 $4-k$ 개 가져가기' 전략으로 매 라운드 정확히 4개를 줄여, 항상 4의 배수를 상대에게 넘긴다. $20=4\cdot 5$ 가 4의 배수이므로 선공이 P위치에서 시작 → 후공 필승.

📖 풀이:
핵심: 사이클의 채색수는 짝수 길이면 2, 홀수 길이면 3이다. $C_5$ 는 홀수 사이클이라 2색으로는 칠할 수 없다(2색이면 색이 번갈아 나타나야 하는데 홀수 둘레에서 시작과 끝이 충돌). $V_1{=}a, V_2{=}b, V_3{=}a, V_4{=}b, V_5{=}c$ 처럼 3색이면 가능하므로 채색수는 $3$. 홀수 사이클을 포함하면 그래프는 이분그래프가 아니다.

📖 풀이:
핵심: 표본공간을 출생 순서까지 구분하면 $\{BB, BG, GB, GG\}$ 로 각 확률 $\tfrac{1}{4}$. '적어도 한 명 남자' 조건은 $GG$ 를 제거해 $\{BB,BG,GB\}$ 세 경우만 남긴다. 이 중 모두 남자는 $BB$ 한 가지뿐이므로 $$\Pr(BB \mid \text{적어도 한 명 남}) = \frac{1/4}{3/4} = \frac{1}{3}.$$

📖 풀이:
핵심: 특성방정식으로 일반항을 구한다. $x^2-5x+6=0 \Rightarrow x=2,3$ 이므로 $a_n = A\cdot 2^n + B\cdot 3^n$. 초기조건 $a_0=A+B=0,\ a_1=2A+3B=1$ 에서 $B=1,\ A=-1$, 즉 $a_n = 3^n - 2^n$. 따라서 $a_4 = 81-16 = 65$. (직접 계산: $a_2=5,\ a_3=19,\ a_4=5\cdot19-6\cdot5=95-30=65$ 로 확인.)

📖 풀이:
핵심: 수학적 귀납법으로 $9 \mid 4^n+15n-1$ 을 증명한다. 기저 $n=1$: $4+15-1=18=9\cdot 2$ ✓. 귀납 가정 $9 \mid f(n)$ 에서 $f(n)=4^n+15n-1$ 라 하면 $$f(n+1)-4f(n) = (4^{n+1}+15n+14)-(4^{n+1}+60n-4) = -45n+18 = 9(2-5n)$$ 은 9의 배수. 따라서 $f(n+1)=4f(n)+9(2-5n)$ 도 9의 배수다. $n=1,2,3$ 에서 값은 $18,45,108$ 이고 $\gcd=9$ 이므로 18은 보장되지 않는다($18 \nmid 45$). 답은 $9$.

📖 풀이:
핵심: $y=1$ 을 넣어 점화식을 만든다. $f(x+1)=f(x)+f(1)+2x = f(x)+2x+1$. 이는 $f(x+1)-f(x)=2x+1$ 로, 차분이 홀수열이다. $f(1)=1$ 에서 출발해 누적하면 $$f(n)=f(1)+\sum_{k=1}^{n-1}(2k+1)=1+(n^2-1)=n^2.$$ 실제로 $f(x)=x^2$ 는 $(x+y)^2=x^2+y^2+2xy$ 로 원식을 만족한다. 따라서 $f(5)=25$.

📖 풀이:
핵심: 원에 내접하는 사각형 $ABPC$ 에 톨레미(Ptolemy) 정리를 적용한다. $$PA \cdot BC = PB \cdot AC + PC \cdot AB.$$ 정삼각형이라 $AB=BC=CA$ 이므로 양변을 변의 길이로 나누면 $PA = PB + PC = 3+5 = 8$. (호 $BC$ 위의 점에서 가장 먼 꼭짓점까지의 거리는 나머지 두 거리의 합.)

📖 풀이:
핵심: 각 정수를 $2^k \cdot m$ ($m$ 은 홀수)로 쓰면, 홀수 부분 $m$ 이 같은 두 수는 한쪽이 다른 쪽을 나눈다. $1$ - $100$ 의 홀수는 $1,3,5,\dots,99$ 로 정확히 50개(비둘기집의 '집'). 51개를 고르면 비둘기집 원리로 같은 홀수 부분을 가진 두 수가 생겨 배수 관계가 강제된다. 한편 $\{51,52,\dots,100\}$ 의 50개는 어느 두 수도 배수 관계가 없다($2\times 51=102>100$). 따라서 50개로는 피할 수 있고, 답은 $51$.

📖 풀이:
핵심: $a+b+ab+1=(a+1)(b+1)$. 따라서 모든 수에 $1$을 더한 값들의 곱 $\prod (x_i+1)$이 연산에 대해 불변이다. 처음 값은 $(1+1)(2+1)(3+1)(4+1)(5+1)=2\cdot3\cdot4\cdot5\cdot6=720$. 마지막 남는 수 $x$에 대해 $x+1=720$이므로 $x=719$. 연산 순서와 무관하다.

📖 풀이:
각 수를 $2^k\cdot m$ ($m$ 홀수)로 쓰면 홀수 부분 $m\in\{1,3,5,\dots,99\}$로 $50$가지뿐이다. $51$개를 고르면 비둘기집 원리로 같은 홀수 부분을 갖는 두 수가 존재하고, 둘 중 하나는 다른 하나의 $2$의 거듭제곱 배이므로 배수 쌍이 생긴다. 한편 $\{51,52,\dots,100\}$의 $50$개는 어떤 수의 $2$배도 $100$을 넘으므로 배수 쌍이 없다. 따라서 보장에 필요한 최소 개수는 $51$.

📖 풀이:
점과 직선 사이 거리 공식: $d=\dfrac{|3\cdot0+4\cdot0-25|}{\sqrt{3^2+4^2}}=\dfrac{25}{5}=5$. 코시-슈바르츠로도: $(3x+4y)^2\le(3^2+4^2)(x^2+y^2)$에서 $25^2\le25(x^2+y^2)$, 즉 $x^2+y^2\ge25$이고 등호는 $(x,y)=(3,4)$일 때. 최단거리는 $5$.

📖 풀이:
$100$을 법으로 $7$의 거듭제곱을 보면 $7^1\equiv07,\ 7^2\equiv49,\ 7^3\equiv43,\ 7^4\equiv01\pmod{100}$으로 주기가 $4$다. $2024=4\cdot506$이므로 $7^{2024}\equiv(7^4)^{506}\equiv1^{506}\equiv1\pmod{100}$. 따라서 마지막 두 자리는 $01$.

📖 풀이:
$2\times n$을 덮는 방법 수를 $a_n$이라 하자. 맨 왼쪽 열을 세로 도미노 $1$개로 채우면 나머지는 $a_{n-1}$, 가로 도미노 $2$개로 채우면 나머지는 $a_{n-2}$. 따라서 $a_n=a_{n-1}+a_{n-2}$, $a_1=1,\ a_2=2$. 수열은 $1,2,3,5,8,13,21,34,55,89$이고 $a_{10}=89$ (피보나치수열).

📖 풀이:
음이 아닌 정수해의 개수는 '별과 막대(stars and bars)' 방법으로 센다. $10$개의 별을 $3$묶음으로 나누려면 칸막이 $2$개가 필요하고, 별 $10$개와 칸막이 $2$개를 일렬로 배열하는 경우의 수와 같다: $\binom{10+2}{2}=\binom{12}{2}=66$.

📖 풀이:
표본공간은 넓이 $1$인 단위정사각형. 여사건 $|x-y|\ge\frac13$은 좌상·우하의 두 직각삼각형이고, 각 삼각형의 두 다리는 길이 $\frac23$이므로 넓이 합은 $2\cdot\frac12\left(\frac23\right)^2=\left(\frac23\right)^2=\frac49$. 따라서 구하는 확률은 $1-\frac49=\frac59$.

📖 풀이:
한 사람 $A$에서 나가는 $5$개의 관계를 두 종류(앎/모름)로 나누면 비둘기집 원리로 같은 종류가 $3$개 이상 있다. 그 상대 $3$명을 $B,C,D$라 하자. 이들 셋 사이에 $A$와 같은 종류의 변이 하나라도 있으면 그 둘과 $A$가 단색삼각형을 이루고, 하나도 없으면 $B,C,D$끼리는 모두 반대 종류라 그 자체가 단색삼각형이다. 따라서 $n=6$에서 강제된다. $n=5$에서는 오각형(빨강)+오각별(파랑) 칠하기로 단색삼각형 없는 예가 있으므로 최소값은 $6$ (램지수 $R(3,3)=6$).

📖 풀이:
핵심 불변량: 쪼개기 $1$회마다 전체 조각 수가 정확히 $1$ 증가한다. 처음 $1$조각에서 시작해 끝에는 모두 $1\times1$이 되어 $mn$조각이 되므로, 게임 종료까지 쪼개는 총 횟수는 전략과 무관하게 항상 $mn-1$로 고정된다. $4\times7$이면 $28-1=27$회. $27$은 홀수이므로 마지막($27$번째) 쪼개기를 선공이 하고, 그다음 차례인 후공은 움직일 수 없어 패배. 따라서 선공이 항상 이긴다.

📖 풀이:
양변에 $6xy$를 곱하면 $6y+6x=xy$, 즉 $xy-6x-6y=0$. 양변에 $36$을 더해 인수분해하면 $(x-6)(y-6)=36$. $x,y>0$이고 $\frac1x<\frac16$이므로 $x>6$, 마찬가지로 $y>6$이라 $x-6,\ y-6$은 $36$의 양의 약수다. $36$의 양의 약수는 $1,2,3,4,6,9,12,18,36$로 $9$개이며, 각 약수 선택이 하나의 순서쌍을 주므로 해는 $9$개.