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

📖 풀이:
강귀납법. ($n=1$) $2\times2$에서 한 칸을 제거하면 남은 $3$칸이 곧 L-트로미노다. (귀납) $2^n\times2^n$에서 항상 가능하다고 가정하고 $2^{n+1}\times2^{n+1}$ 판을 $2^n\times2^n$ 사분면 $4$개로 나눈다. 제거된 칸은 한 사분면에 속한다. 정중앙에 L-트로미노 하나를 놓아 나머지 세 사분면에서 중심에 닿는 칸을 하나씩 덮으면, 네 사분면 모두 '한 칸이 빠진 $2^n\times2^n$'이 되어 귀납 가정으로 각각 덮인다. 따라서 모든 $n\ge1$, 임의의 제거 위치에서 가능하다. (칸 수 $4^n-1$이 항상 $3$의 배수라는 점도 이와 일치한다.)

📖 풀이:
$y=1$을 대입하면 $f(n+1)=f(n)+f(1)+n=f(n)+(n+1)$, 즉 $f(n+1)-f(n)=n+1$. $f(1)=1$에서 차분을 누적하면 $f(n)=1+2+\cdots+n=\dfrac{n(n+1)}{2}$. 따라서 $f(10)=\dfrac{10\cdot11}{2}=55$ (삼각수와 일치).

📖 풀이:
핵심: 흰 공의 개수의 홀짝(패리티)이 불변량이다.
- 흰+흰: 흰 $2$개 제거, 검 $1$개 추가 → 흰 개수 $-2$ (홀짝 보존)
- 검+검: 검 $2$개 제거, 검 $1$개 추가 → 흰 개수 불변
- 흰+검: 흰·검 $1$개씩 제거, 흰 $1$개 추가 → 흰 개수 불변
모든 경우에서 흰 공 개수의 홀짝은 변하지 않는다. 처음 흰 공은 $7$개(홀수)이므로 끝까지 흰 공 개수는 항상 홀수이다. 마지막에 공은 $1$개 남고, 그 개수가 짝수($0$)일 수 없으므로 남는 공은 흰 공이다.

📖 풀이:
핵심: 인접한 두 개미의 운동방향은 항상 수직이므로, 추격하는 개미는 표적 개미에게 '옆으로' 접근하는 성분이 없다.
$A$가 $B$를 향해 속력 $v$로 다가갈 때, $B$의 속도는 항상 선분 $AB$에 수직($\angle$가 $90^\circ$)이다. 따라서 $B$의 운동은 거리 $AB$를 늘이거나 줄이지 않고, 거리 $AB$는 오직 $A$의 접근 때문에 속력 $v$로 줄어든다. 처음 $AB=1$이므로 만나기까지 걸리는 시간은 $t=\dfrac{1}{v}$. 그동안 각 개미가 이동한 거리는 $v\cdot t = 1$.
경로 자체는 무한히 감기는 나선이지만 그 '길이'는 유한하며 정확히 한 변의 길이와 같다.

📖 풀이:
핵심: $\{1,2\},\{3,4\},\dots,\{99,100\}$의 $50$개 묶음을 비둘기집으로 본다.
$1$부터 $100$까지를 연속한 두 수로 묶으면 정확히 $50$개의 묶음이 생긴다. $51$개의 수를 고르면 비둘기집 원리에 의해 어떤 한 묶음에서 두 수가 동시에 선택되며, 그 두 수의 차는 $1$이다.
(②는 짝수가 $50$개뿐이라 $51$개 불가능, ③은 $\{1,\dots,49\}$에 $50$을 더해 합이 $100$인 짝을 피할 수 있어 거짓, ④도 반례 존재.) 따라서 항상 참인 것은 ①.

📖 풀이:
핵심: $n$칸을 오르는 마지막 동작이 $1$칸이면 앞은 $a_{n-1}$가지, $2$칸이면 $a_{n-2}$가지이므로 $a_n=a_{n-1}+a_{n-2}$.
초기값 $a_1=1,\ a_2=2$에서 차례로
$$a_3=3,\ a_4=5,\ a_5=8,\ a_6=13,\ a_7=21,\ a_8=34,\ a_9=55,\ a_{10}=89.$$
이는 피보나치 수열이며 $a_n=F_{n+1}$ 꼴이다. 따라서 $10$칸은 $89$가지.

📖 풀이:
핵심: 식을 전개해 '$x+\dfrac{4}{x}$' 꼴을 만들고 두 양수의 합에 부등식 $a+b\ge 2\sqrt{ab}$를 적용한다.
$$f(x)=\frac{x^2+5x+4}{x}=x+\frac{4}{x}+5.$$
$x>0$이므로 $x+\dfrac{4}{x}\ge 2\sqrt{x\cdot\frac{4}{x}}=2\cdot 2=4$, 등호는 $x=\dfrac{4}{x}$ 즉 $x=2$일 때.
따라서 $f(x)\ge 4+5=9$, 최솟값은 $x=2$에서 $9$.

📖 풀이:
핵심: 그래프가 $2$색으로 칠해진다는 것은 이분그래프(홀수 길이 사이클이 없음)와 동치다.
$C_5$는 길이 $5$의 홀수 사이클이므로 $2$색으로 칠할 수 없다. ($V_1$에 색 A, 둘레를 따라 A,B,A,B,A로 칠하면 $V_5$(A)와 $V_1$(A)가 인접해 충돌.)
반면 $V_1{=}A, V_2{=}B, V_3{=}A, V_4{=}B, V_5{=}C$ 처럼 $3$색이면 모든 인접쌍이 다른 색이 된다. 따라서 채색수(chromatic number)는 $3$.
일반적으로 홀수 사이클 $C_{2k+1}$의 채색수는 $3$, 짝수 사이클은 $2$이다.

📖 풀이:
핵심: $3$의 거듭제곱을 $7$로 나눈 나머지가 주기적으로 순환함(위수)을 이용한다.
$$3^1\equiv3,\ 3^2\equiv2,\ 3^3\equiv6,\ 3^4\equiv4,\ 3^5\equiv5,\ 3^6\equiv1 \pmod 7.$$
나머지는 주기 $6$으로 순환한다($3$의 법 $7$에 대한 위수는 $6$). $1000=6\cdot166+4$이므로
$$3^{1000}\equiv 3^{4}\equiv 4 \pmod 7.$$

📖 풀이:
핵심: '별과 막대(stars and bars)' - $10$개의 별을 $3$개의 칸막이로 $4$구역에 나눈다.
별 $10$개와 칸막이 $3$개, 총 $13$개의 자리 중 칸막이가 놓일 $3$자리를 고르면 되므로
$$\binom{10+4-1}{4-1}=\binom{13}{3}=\frac{13\cdot12\cdot11}{6}=286.$$
각 배열이 하나의 음이 아닌 정수해와 일대일 대응되므로 답은 $286$이다.

📖 풀이:
핵심: 식을 연속한 세 정수의 곱 꼴로 변형하거나 수학적 귀납법으로 $3\mid n^3+2n$ 을 보인다.
변형: $n^3+2n=(n^3-n)+3n=(n-1)n(n+1)+3n.$ 연속한 세 정수의 곱 $(n-1)n(n+1)$은 항상 $3$의 배수이고 $3n$도 $3$의 배수이므로 합은 항상 $3$의 배수.
귀납법: $n=1$이면 $3$. $n=k$에서 $k^3+2k$가 $3$의 배수라 하면
$$(k+1)^3+2(k+1)=k^3+2k+3k^2+3k+3,$$
뒤의 $3(k^2+k+1)$이 $3$의 배수이므로 $n=k+1$에서도 성립.
한편 $n=1$일 때 값이 $3$이므로 모든 $n$의 공약수는 $3$을 넘을 수 없다. 따라서 최대 $d=3$.

📖 풀이:
핵심: 이 게임은 비토프(Wythoff) 게임이며, 패배 위치(P-위치)는 황금비 $\varphi=\frac{1+\sqrt5}{2}$를 이용한
$$(\lfloor n\varphi\rfloor,\ \lfloor n\varphi^2\rfloor)\quad(n=0,1,2,\dots)$$
으로 $(0,0),(1,2),(3,5),(4,7),(6,10),\dots$ 이다.
$n=2$: $\lfloor 2\varphi\rfloor=3,\ \lfloor 2\varphi^2\rfloor=5$이므로 $(3,5)$가 P-위치.
검증(다른 보기는 모두 한 수로 P-위치에 도달 가능 → 승리 위치):
- $(2,3)\to(1,2)$ [양쪽 $1$개]
- $(4,6)\to(3,5)$ [양쪽 $1$개]
- $(5,7)\to(3,5)$ [양쪽 $2$개]
반면 $(3,5)$에서는 어떤 합법수로도 다른 P-위치에 갈 수 없으므로 두는 사람이 진다.

📖 풀이:
핵심: 직사각형에서 한 점부터 네 꼭짓점까지 거리에 대한 '영국 국기 정리' $PA^2+PC^2=PB^2+PD^2$ 를 쓴다.
증명 아이디어: $P$에서 두 쌍의 변에 수선을 내려 거리들을 가로·세로 성분으로 분해하면, 대각으로 마주 보는 두 꼭짓점 거리 제곱의 합이 양쪽에서 같은 (가로성분$^2$+세로성분$^2$의 전체 합)으로 일치한다.
따라서
$$PC^2=PB^2+PD^2-PA^2=25+36-16=45,$$
$$PC=\sqrt{45}=3\sqrt5.$$

📖 풀이:
핵심: 끝의 $0$의 개수는 $n!$에 들어 있는 소인수 $5$의 개수와 같고, 르장드르 공식으로 센다.
$$Z(n)=\left\lfloor\frac n5\right\rfloor+\left\lfloor\frac n{25}\right\rfloor+\left\lfloor\frac n{125}\right\rfloor+\cdots$$
($2$의 개수는 항상 $5$의 개수보다 많아 $5$의 개수가 $0$의 개수를 결정한다.)
$Z(400)=80+16+3=99,$ $\quad Z(405)=81+16+3=100.$
$401\sim404$는 $\lfloor n/5\rfloor$가 아직 $80$이라 $Z=99$이고, $n=405$에서 처음으로 $100$이 된다. 따라서 가장 작은 $n=405$.
(참고로 끝의 $0$이 정확히 $100$개인 $n$은 $405,406,407,408,409$이며, '정확히 $101$개'로 넘어가는 건 $410$이다.)

📖 풀이:
핵심(악수 정리): 모든 정점의 차수 합은 간선 수의 2배이므로 항상 짝수다. 각 정점의 차수가 3이고 정점이 7개면 차수 합은 $7\times3=21$ 로 홀수가 되어 $2|E|$ 일 수 없다. 따라서 홀수 차수를 가진 정점은 항상 짝수 개여야 하는데, 7개 모두 홀수 차수가 될 수 없다. 그러므로 불가능하다.

📖 풀이:
핵심: 두 수의 차가 5의 배수 $\iff$ 두 수가 5로 나눈 나머지가 같다($a\equiv b\pmod5$). 나머지는 $0,1,2,3,4$ 의 다섯 종류(비둘기집)뿐이므로, 정수를 6개 고르면 비둘기집 원리에 의해 같은 나머지를 갖는 두 수가 반드시 존재하고 그 차는 5의 배수다. 한편 5개만 고르면 각 나머지를 하나씩 골라($0,1,2,3,4$) 차가 5의 배수인 쌍을 피할 수 있어 5개로는 보장되지 않는다. 따라서 답은 6.

📖 풀이:
핵심(이중 계산): 총합을 '원소별 기여'로 바꿔 센다. 고정된 원소 $k$ 가 몇 개의 부분집합에 들어가는가? 나머지 9개 원소를 자유롭게 넣고 뺄 수 있으므로 $2^9$ 개의 부분집합에 포함된다. 따라서 각 원소는 총합에 $2^9$ 만큼 기여하고, 원소가 10개이므로 $$\text{총합}=10\cdot2^{9}=10\cdot512=5120.$$ 일반적으로 $n$ 원소 집합에서는 $n\cdot2^{n-1}$.

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

📖 풀이:
핵심(중국인 나머지정리): 법이 서로소($3,5,7$)이므로 $\bmod 105$ 에서 유일한 해가 있다. 먼저 $x\equiv2\pmod3,\ x\equiv3\pmod5$ 를 합치면 $x\equiv8\pmod{15}$ ($8$ 은 $3$ 으로 나눠 2, $5$ 로 나눠 3). 이제 $x=8+15k$ 를 셋째 식에 대입: $8+15k\equiv2\pmod7$. $15\equiv1,\ 8\equiv1\pmod7$ 이므로 $1+k\equiv2$, 즉 $k\equiv1\pmod7$. 최소 $k=1$ 이면 $x=23$. 검산: $23=3\cdot7+2,\ 23=5\cdot4+3,\ 23=7\cdot3+2$ 로 모두 성립.

📖 풀이:
핵심(프로베니우스 수): 서로소인 두 자연수 $a,b$ 로 표현 불가능한 가장 큰 수는 $ab-a-b$ 이다. $\gcd(7,9)=1$ 이므로 $$7\cdot9-7-9=63-16=47.$$ 검증의 아이디어: $48=7\cdot3+9\cdot3$ 처럼 $48$ 이상은 모두 표현 가능하고, $47$ 은 $7,9$ 의 비음수 조합으로 만들 수 없다($47=9\cdot0..5$ 각 경우 남는 수가 7의 배수가 아님). 따라서 47.

📖 풀이:
핵심(착시의 정체): 두 직각삼각형의 빗변 기울기가 $\tfrac{2}{5}=0.4$ 와 $\tfrac{3}{8}=0.375$ 로 미세하게 다르다. 따라서 전체 외곽의 '빗변'은 실제로는 직선이 아니라 위 배치에서는 살짝 안쪽으로 휜 사변형, 아래 배치에서는 바깥으로 휜 사변형이다. 두 휜 영역의 넓이 차이가 정확히 $1$ 칸이며, 그것이 구멍처럼 보일 뿐 조각 넓이의 합은 변하지 않는다(불변량은 넓이). 넓이는 보존되고, 변하는 것은 '직선처럼 보이던' 경계의 실제 모양이다.

📖 풀이:
핵심(코시-슈바르츠 / 티투 보조정리): $\dfrac{a_1^2}{b_1}+\dfrac{a_2^2}{b_2}+\dfrac{a_3^2}{b_3}\ge\dfrac{(a_1+a_2+a_3)^2}{b_1+b_2+b_3}$ 를 $a_i=1,2,3,\ b_i=x,y,z$ 에 적용하면 $$\frac{1^2}{x}+\frac{2^2}{y}+\frac{3^2}{z}\ge\frac{(1+2+3)^2}{x+y+z}=\frac{36}{1}=36.$$ 등호는 $\dfrac{1}{x}=\dfrac{2}{y}=\dfrac{3}{z}$ 즉 $x:y:z=1:2:3$ 일 때, 곧 $x=\tfrac16,y=\tfrac26,z=\tfrac36$ 에서 성립한다. 따라서 최솟값은 $36$.

📖 풀이:
핵심(순열 패리티 불변량): 한 번의 슬라이드는 빈 칸과 이웃 타일의 위치를 맞바꾸는 '전위(transposition)'이며, 전위 한 번마다 타일 배열의 순열 부호가 뒤집힌다. 빈 칸이 원래 자리(구석)로 돌아오려면 상·하·좌·우 이동 수가 균형을 이뤄 \emph{짝수 번} 움직여야 한다(격자를 체스판처럼 색칠하면 빈칸은 짝수 번 이동해야 같은 색 칸으로 복귀). 따라서 도달 가능한 타일 배열은 항상 \emph{짝치환}(부호 $+1$)뿐이다. 그런데 14와 15만 바꾸는 것은 단 한 번의 전위 = \emph{홀치환}(부호 $-1$)이므로 불변량과 모순된다. 그러므로 절대 맞출 수 없다.

📖 풀이:
핵심: 조건부확률은 '남은 표본'의 비율이다. 표본공간 {남남, 남녀, 녀남, 녀녀}는 각 확률 $\frac14$. '적어도 한 명 아들' 조건은 녀녀를 제외한 3가지로 좁혀진다. 그중 '모두 아들'은 남남 1가지뿐이므로 $\frac{1}{3}$. 한 명을 콕 집어 '아들'이라 한 것이 아니라 '적어도 한 명'이라는 정보임에 주의(직관적 답 $\frac12$는 틀림).

📖 풀이:
핵심: 새 직선 한 개를 추가할 때 늘어나는 영역 수를 센다. $n$번째 직선은 기존 $n-1$개 직선과 서로 다른 $n-1$개 점에서 만나므로 그 직선은 $n$개의 조각으로 나뉘고, 각 조각이 기존 영역을 하나씩 둘로 가른다 → 영역이 $n$개 증가. 따라서 $R(0)=1$, $R(n)=R(n-1)+n$. 풀면 $R(n)=1+\frac{n(n+1)}{2}$. $R(5)=1+\frac{5\cdot6}{2}=1+15=16$.