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

📖 풀이:
핵심: $3^6\equiv 1\pmod 7$ (페르마). $100 = 6\cdot 16 + 4$ 이므로 $3^{100} = (3^6)^{16}\cdot 3^4 \equiv 3^4 \pmod 7$. $3^4 = 81 = 7\cdot 11 + 4 \equiv 4 \pmod 7$. 따라서 나머지는 $4$.

📖 풀이:
핵심(베이즈): $P(\text{병}\mid +) = \dfrac{0.01\times0.99}{0.01\times0.99 + 0.99\times0.05} = \dfrac{0.0099}{0.0099+0.0495} = \dfrac{0.0099}{0.0594} = \dfrac16 \approx 16.7\%$. 민감도가 $99\%$ 라도 기저율(유병률)이 낮으면 양성의 대부분은 위양성이라 사후확률이 의외로 작다.

📖 풀이:
핵심: $13x\equiv 2 \pmod 7 \Rightarrow 6x\equiv 2 \Rightarrow 3x\equiv 1\pmod 7$. $3\cdot5=15\equiv1$ 이므로 $x\equiv 5\pmod 7$. 일반해 $x = 5+7t,\ y=-9-13t$. 양의 정수 중 최소는 $t=0$ 일 때 $x=5$ (이때 $y=-9$). 확인: $13\cdot5+7\cdot(-9)=65-63=2$.

📖 풀이:
핵심: 부분합 공식 $\sum_{k=1}^{n}F_k = F_{n+2}-1$. $n=10$ 이면 $F_{12}-1 = 144-1 = 143$. (귀납: 가정 $\sum_{k=1}^{n}F_k=F_{n+2}-1$ 에 $F_{n+1}$ 을 더하면 $F_{n+2}-1+F_{n+1}=F_{n+3}-1$, 정의에 의해 성립.)

📖 풀이:
핵심: 첫 달걀을 처음에 $m$ 층, 다음 $m-1$ 층 위, 그다음 $m-2$ 층 위... 식으로 간격을 1씩 줄여 떨어뜨린다. 첫 달걀이 어디서 깨지든 남은 구간을 둘째 달걀이 한 층씩 올라가며 검사하면 총 횟수가 항상 $\le m$. 100층을 덮으려면 $\frac{m(m+1)}{2}\ge 100$, 즉 $m\ge 14$ ($\frac{14\cdot15}{2}=105$). 따라서 최소 보장 횟수는 $14$.

📖 풀이:
핵심(램지 수 $R(3,3)=6$): 한 사람 $A$ 에게서 나머지 5명으로 향하는 관계는 두 종류뿐이라, 비둘기집에 의해 같은 종류가 최소 3명($B,C,D$) 있다. 이 셋이 그 종류로 서로 한 쌍이라도 연결되면 $A$ 와 함께 단색 삼각형, 셋이 모두 반대 종류면 $B,C,D$ 자체가 단색 삼각형. 어느 경우든 동색 삼각형이 존재.

📖 풀이:
핵심(뺄셈 게임): 4의 배수 개수가 남으면 그 차례 사람이 진다(P-포지션). 상대가 $1\sim3$ 을 가져가면 나는 합이 4가 되도록 맞춰주면 되기 때문. $21 = 4\cdot5+1$ 이므로 선공이 1개를 가져가 20(=4의 배수)을 남기면 이후 항상 4 맞춤 전략으로 승리.

📖 풀이:
핵심(중국인 나머지정리): $3,5,7$ 이 서로소라 $\bmod 105$ 에서 해가 유일하게 존재. $x\equiv2\pmod3$ 과 $x\equiv2\pmod7$ 을 합치면 $x\equiv2\pmod{21}$, 즉 $x\in\{2,23,44,65,86\}$. 이 중 $\bmod 5$ 가 $3$ 인 것은 $23$ ($23=4\cdot5+3$). 검산: $23\bmod3=2,\ \bmod5=3,\ \bmod7=2$. 모두 만족.

📖 풀이:
핵심(기하확률): 도착 시각을 $(x,y)\in[0,60]^2$ 로 두면 만남 조건은 $|x-y|\le 15$. 여사건은 $|x-y|>15$, 즉 양쪽 직각삼각형 두 개로 넓이 $2\cdot\frac12\cdot45^2 = 45^2$. 따라서 만날 확률 $= 1 - \dfrac{45^2}{60^2} = 1-\dfrac{2025}{3600} = 1-\dfrac{9}{16} = \dfrac{7}{16}$.

📖 풀이:
핵심: $y=1$ 이면 $x^2=3$ (불가), $y=2$ 이면 $x^2 = 1+2\cdot4 = 9$, $x=3$ ✓. 따라서 기본해는 $(3,2)$. 이후 모든 해는 $x_{n}+y_n\sqrt2 = (3+2\sqrt2)^n$ 으로 생성된다(예: 다음 해 $(17,12)$).

📖 풀이:
핵심(무한강하): $x^3=4z^3-2y^3$ 이 짝수이므로 $x$ 도 짝수, $x=2x_1$. 대입해 $8x_1^3+2y^3=4z^3 \Rightarrow 4x_1^3+y^3=2z^3$. 다시 $y$ 가 짝수, $y=2y_1$, 정리하면 $2x_1^3+4y_1^3=z^3$ 꼴로 $z$ 도 짝수. 이렇게 $x,y,z$ 가 모두 무한히 2로 나눠지므로 양의 해는 존재할 수 없고 $(0,0,0)$ 만 남는다.

📖 풀이:
핵심: '본 금액 $X$ 가 작은 쪽일 확률 $=$ 큰 쪽일 확률 $=\frac12$' 라는 가정은 모든 금액에 동시에 성립할 수 없다. 만약 항상 그렇다면 봉투 안 금액의 사전분포가 양의 실수 전체에 균등해야 하는데, 그런 확률분포는 존재하지 않는다(전체 합이 1이 될 수 없음). 실제 사전분포를 고정하면 큰 $X$ 일수록 '이미 큰 쪽을 봤을' 확률이 높아져 $\frac54$ 이득이 사라진다.

📖 풀이:
핵심: 끝 0의 개수는 $100!$ 의 소인수 $10=2\cdot5$ 의 개수, 즉 $\min$(2의 지수, 5의 지수)인데 2가 훨씬 많으므로 5의 지수가 답. $\left\lfloor\frac{100}{5}\right\rfloor+\left\lfloor\frac{100}{25}\right\rfloor+\left\lfloor\frac{100}{125}\right\rfloor = 20+4+0 = 24$. 따라서 끝의 0은 $24$개.

📖 풀이:
핵심: 비제차 선형점화는 양변에 $1$을 더해 등비수열로 바꾼다. $a_{n+1}+1=2(a_n+1)$ 이므로 $b_n=a_n+1$ 은 $b_1=3$, 공비 $2$ 인 등비수열. 따라서 $a_n+1=3\cdot 2^{n-1}$, 즉 $a_n=3\cdot 2^{n-1}-1$. $a_6=3\cdot 32-1=95$.

📖 풀이:
핵심: 비둘기집을 위한 적절한 칸(쌍) 분할. $\{1,2\},\{3,4\},\dots,\{99,100\}$ 의 $50$개 쌍으로 나눈다. $51$개를 고르면 비둘기집 원리로 어떤 쌍에서 두 수를 모두 고르게 되어 연속한 두 수가 생긴다. 반면 홀수 $50$개 $\{1,3,\dots,99\}$ 는 연속쌍이 없으므로 $50$개로는 보장 못 한다. 따라서 최소 $51$.

📖 풀이:
핵심: 일의 자리는 $\pmod{10}$ 의 거듭제곱 주기. $7^1\equiv7,\ 7^2\equiv9,\ 7^3\equiv3,\ 7^4\equiv1\pmod{10}$ 으로 주기 $4$. $2026=4\cdot506+2$ 이므로 $7^{2026}\equiv 7^2\equiv 9\pmod{10}$.

📖 풀이:
핵심: 합이 일정할 때 곱은 두 수가 같을 때 최대(AM-GM). 가로 $x$, 세로 $10-x$ 이면 넓이 $S=x(10-x)=25-(x-5)^2\le25$, 등호는 $x=5$. 즉 정사각형 $5\times5$ 일 때 넓이 $25$ 가 최대.

📖 풀이:
핵심: 오른쪽 $R$ $4$번, 위 $U$ $4$번의 배열 순서를 고르는 문제. 전체 $8$번의 이동 중 어디에 $R$ 을 놓을지 고르면 되므로 $\binom{8}{4}=70$.

📖 풀이:
핵심 불변량: 모든 수의 합의 홀짝. $a,b$ 를 $|a-b|$ 로 바꾸면 합은 $a+b$ 만큼 줄고 $|a-b|$ 만큼 늘어 변화량 $a+b-|a-b|=2\min(a,b)$ 로 항상 짝수 변화 → 합의 패리티 보존. 처음 합 $1+2+\cdots+2026=\frac{2026\cdot2027}{2}=1013\cdot2027$ 은 (홀)$\times$(홀)$=$홀수. 따라서 마지막 한 수도 홀수.

📖 풀이:
핵심: 두 점 $(x_1,y_1),(x_2,y_2)$ 의 중점이 격자점일 필요충분조건은 $x_1\equiv x_2$, $y_1\equiv y_2\pmod2$. 좌표의 홀짝쌍은 (짝,짝),(짝,홀),(홀,짝),(홀,홀) 의 $4$종류. 점 $5$개 중 두 점은 같은 종류(비둘기집)이고, 그 두 점의 중점은 격자점이다.

📖 풀이:
핵심: 악수 정리(차수 합 = 간선 수의 $2$배). 모든 차수가 $3$ 이면 차수 총합 $=7\times3=21$ 인데, 이는 간선 수의 두 배여야 하므로 짝수여야 한다. $21$ 은 홀수이므로 모순. 따라서 불가능.

📖 풀이:
핵심: 교란순열 수 $D_n=n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}$. $D_4=4!\left(1-1+\tfrac12-\tfrac16+\tfrac1{24}\right)=9$. 전체 배열 $4!=24$ 이므로 확률 $=\frac{9}{24}=\frac{3}{8}$.

📖 풀이:
핵심: 길이 $n$ 의 그런 수열 수를 $a_n$ 이라 하면, 마지막 칸이 $0$ 이면 앞 $n-1$ 칸은 자유($a_{n-1}$), $1$ 이면 그 앞 칸은 반드시 $0$ 이고 그 앞 $n-2$ 칸 자유($a_{n-2}$). 따라서 $a_n=a_{n-1}+a_{n-2}$(피보나치). $a_1=2,\ a_2=3$ 에서 $a_3=5,a_4=8,a_5=13,a_6=21$.

📖 풀이:
핵심: 소피 제르맹 항등식. $n^4+4=n^4+4n^2+4-4n^2=(n^2+2)^2-(2n)^2=(n^2-2n+2)(n^2+2n+2)$. 두 인수가 모두 $1$ 보다 크면 합성수다. 작은 인수 $n^2-2n+2=(n-1)^2+1=1$ 이 되는 경우는 $n=1$ 뿐이고 이때 $n^4+4=5$ (소수). $n\ge2$ 이면 두 인수 모두 $\ge2$ 라 합성수. 따라서 $n=1$.

📖 풀이:
핵심 불변량: 세 수의 제곱합. $(0.6a-0.8b)^2+(0.8a+0.6b)^2=a^2+b^2$ (회전이라 노름 보존)이므로 손대지 않은 수까지 합치면 세 수의 제곱합은 항상 일정하다. 시작값 $3^2+4^2+12^2=169$, 목표값 $4^2+6^2+12^2=196$. $169\ne196$ 이므로 불가능.