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

📖 풀이:
핵심: $\pmod4$ 분석. 모든 정수에 대해 $n^2\equiv0$ 또는 $1\pmod4$이므로 두 제곱의 합은 $0,1,2\pmod4$만 가능하다. 그런데 $2023=4\cdot505+3$이므로 $2023\equiv3\pmod4$. 따라서 정수해가 존재할 수 없다.

📖 풀이:
핵심: $x^2-y^2=(x-y)(x+y)$. 두 인수 $x-y,\ x+y$는 합·차가 짝수여야 하므로 같은 패리티이고, 곱이 짝수 $2024$이므로 둘 다 짝수여야 한다. $x-y=2a,\ x+y=2b$로 두면 $ab=506=2\cdot11\cdot23$. $506$의 약수는 8개이므로 $a<b$인 쌍은 4개이고, 각 쌍이 양의 정수해 $(x,y)$를 하나씩 준다. 따라서 4개.

📖 풀이:
핵심: 차분 점화. $k$번째 직선은 앞선 $k-1$개의 직선과 서로 다른 $k-1$개의 점에서 만나 자신이 $k$개의 조각으로 나뉘고, 각 조각이 기존 영역 하나를 둘로 가른다. 즉 영역 수 $R_k=R_{k-1}+k$, $R_0=1$. 따라서 $R_n=1+\sum_{k=1}^{n}k=1+n+\binom{n}{2}$.

📖 풀이:
핵심: $\pmod3$에서 제곱수는 $0,1$뿐이다. $x^2+y^2\equiv0\pmod3$이려면 $x\equiv y\equiv0\pmod3$이어야 한다. 그러면 좌변이 $9$의 배수이므로 $3z^2$도 $9$의 배수, 즉 $3\mid z$. $x=3x_1,\ y=3y_1,\ z=3z_1$로 두면 $x_1^2+y_1^2=3z_1^2$로 같은 형태의 더 작은 해를 얻는다. 0이 아닌 최소 양의 해가 존재한다는 가정에 모순(무한강하)이므로 자명해뿐이다.

📖 풀이:
핵심: 상대에게 항상 '4의 배수'를 남기면 이긴다. 내가 남긴 더미가 4의 배수일 때, 상대가 $k$개($1\le k\le3$)를 가져가면 나는 $4-k$개를 가져가 매 라운드 정확히 4개씩 줄일 수 있다. $21=4\cdot5+1$이므로 선공이 먼저 1개를 가져가 20(4의 배수)을 남기면 이 전략으로 필승한다.

📖 풀이:
핵심: 체바(Ceva) 정리. $AD,BE,CF$가 한 점에서 만날 필요충분조건은 $\dfrac{BD}{DC}\cdot\dfrac{CE}{EA}\cdot\dfrac{AF}{FB}=1$이다. 넓이비(같은 높이를 갖는 삼각형의 밑변비)나 메넬라우스 정리로 증명할 수 있다. 무게중심(세 중선)은 세 비가 모두 1인 특수한 경우.

📖 풀이:
핵심: 특수값 대입. $x=y=0$을 넣으면 $f(0)^2-f(0)=0$이므로 $f(0)\in\{0,1\}$. 다음 $y=0$을 넣으면 $f(x)f(0)-f(0)=x$. 만약 $f(0)=0$이면 $0=x$가 모든 $x$에서 성립해야 하므로 모순. 따라서 $f(0)=1$이고 $f(x)-1=x$, 즉 $f(x)=x+1$. 원식에 대입하면 $(x+1)(y+1)-(xy+1)=x+y$로 성립한다.

📖 풀이:
핵심: 색 불변량. 나이트는 한 번 움직일 때마다 칸의 색이 반드시 흑↔백으로 바뀐다. 출발 칸과 도착 칸이 같으면 색도 같아야 하므로 색이 짝수 번 바뀌어야 한다. 따라서 이동 횟수는 항상 짝수이다.

📖 풀이:
핵심: 하키스틱(hockey stick) 항등식 $\sum_{k=r}^{n}\binom{k}{r}=\binom{n+1}{r+1}$. 여기서 $r=2,\ n=10$이므로 합은 $\binom{11}{3}=165$. (조합론적으로: $\{1,\dots,11\}$에서 세 수를 고를 때 가장 큰 수 $k+1$로 분류하면 각 경우의 수가 $\binom{k}{2}$이 되는 이중계산.)

📖 풀이:
핵심: $100$ 에 대한 $3$ 의 위수를 찾는다. $3^{10} \equiv 49$, $49^2 = 2401 \equiv 1 \pmod{100}$ 이므로 $3^{20} \equiv 1 \pmod{100}$ (위수 $20$, $\varphi(100)=40$ 의 약수). $1000 = 20 \times 50$ 이므로 $3^{1000} \equiv (3^{20})^{50} \equiv 1 \pmod{100}$. 끝 두 자리는 $01$.

📖 풀이:
핵심: 동일한 공 $12$ 개를 칸 $4$ 개에 나누기. 공 $12$ 개 사이에 칸막이 막대 $3$ 개를 배치하는 방법 수이므로 $\binom{12+3}{3} = \binom{15}{3} = 455$.

📖 풀이:
핵심: 부분분수 분해 후 소거. $\frac{1}{k(k+1)} = \frac{1}{k} - \frac{1}{k+1}$ 이므로 합은 $\left(1-\tfrac12\right)+\left(\tfrac12-\tfrac13\right)+\cdots+\left(\tfrac1{99}-\tfrac1{100}\right) = 1 - \frac{1}{100} = \frac{99}{100}$.

📖 풀이:
핵심: 두 절단점 $x,y$ 를 단위정사각형 위 균등 분포로 보고 삼각부등식(가장 긴 조각 $<\tfrac12$)을 만족하는 영역의 넓이를 구한다. 그 영역은 넓이 $\tfrac18$ 인 두 삼각형으로 전체의 $\frac14$. 따라서 확률은 $\frac14$.

📖 풀이:
핵심: 차수의 홀짝만 보면 된다. 차수는 $V_1=3, V_2=2, V_3=4, V_4=2, V_5=3$. 홀수 차수 정점이 $V_1, V_5$ 정확히 두 개. 연결그래프에서 홀수 차수 정점이 $0$ 개면 오일러 회로, 정확히 $2$ 개면 오일러 경로(그 두 점이 양 끝)가 존재한다. 따라서 회로는 없고 경로는 존재.

📖 풀이:
핵심: 홀수 사이클 + 모두에 인접한 허브. 둘레 $C_5$ 는 홀수 사이클이라 $3$ 색이 필요하고 $3$ 색으로 충분. 중심 $O$ 는 둘레 다섯 꼭짓점 모두와 인접하므로 둘레에 등장한 세 색과 모두 달라야 해 네 번째 색이 필요. 따라서 $\chi(W_5) = 4$.

📖 풀이:
핵심 아이디어: $a+b+ab = (a+1)(b+1)-1$. 따라서 각 수에 $1$ 을 더한 값들의 곱 $\prod (x_i+1)$ 이 연산에 대해 불변이다. 처음 곱은 $(1{+}1)(2{+}1)(3{+}1)(4{+}1)(5{+}1) = 2\cdot3\cdot4\cdot5\cdot6 = 720$. 끝에 남는 수 $N$ 은 $N+1 = 720$, 즉 $N = 719$.

📖 풀이:
핵심: 불변량은 '앞면 동전 개수의 홀짝성'. 인접한 두 동전을 뒤집으면 (앞,앞)→(뒤,뒤)는 $-2$, (앞,뒤)→(뒤,앞)은 $0$, (뒤,뒤)→(앞,앞)은 $+2$ 만큼 변해 항상 짝수만큼 변한다. 즉 앞면 개수의 홀짝성은 보존. 시작은 $7$(홀수), 목표는 $0$(짝수)이므로 도달 불가능.

📖 풀이:
핵심: 두 수의 차가 $5$ 의 배수 $\iff$ 두 수의 $5$ 로 나눈 나머지가 같음. 나머지는 $0,1,2,3,4$ 의 다섯 종류뿐(비둘기집 $5$ 개). 정수 $6$ 개를 고르면 같은 나머지를 갖는 두 수가 반드시 생기고 그 차는 $5$ 의 배수. $5$ 개로는 나머지를 하나씩 모두 다르게 고를 수 있어 보장되지 않는다. 따라서 최소 $6$.

📖 풀이:
핵심: 큰 정사각형을 한 변 $\frac12$ 인 작은 정사각형 $4$ 개(비둘기집)로 나눈다. 점 $5$ 개를 넣으면 비둘기집 원리로 한 작은 정사각형에 두 점이 들어간다. 작은 정사각형의 최대 거리(대각선)는 $\sqrt{(\tfrac12)^2+(\tfrac12)^2} = \frac{\sqrt2}{2}$ 이므로 그 두 점의 거리는 $\frac{\sqrt2}{2}$ 이하.

📖 풀이:
핵심: 재배열 부등식에 의해 두 수열을 같은 순서(둘 다 오름차순)로 짝지을 때 곱의 합이 최대, 역순으로 짝지을 때 최소. 계수 $(1,2,3)$ 에 값 $(1,2,3)$ 을 같은 순서로 대응하면 $1\cdot1+2\cdot2+3\cdot3 = 14$ 가 최댓값(역순이면 $1\cdot3+2\cdot2+3\cdot1=10$ 이 최솟값).

📖 풀이:
핵심: 양변에 $1$ 을 더해 등비형으로 만든다. $a_n + 1 = 2(a_{n-1}+1)$ 이므로 $a_n + 1 = 2^{n-1}(a_1+1) = 2^{n-1}\cdot 2 = 2^n$, 즉 $a_n = 2^n - 1$. 따라서 $a_6 = 2^6 - 1 = 63$ (수열: $1,3,7,15,31,63$).

📖 풀이:
핵심: 처음 고른 문이 정답일 확률은 $\frac13$, 오답일 확률은 $\frac23$. '바꾸기' 전략은 처음에 오답을 골랐을 때 정확히 자동차로 이어지므로 성공 확률은 $\frac23$. 진행자가 반드시 염소 문을 열어 정보를 주기 때문에 두 남은 문이 $\frac12$ 씩이라는 직관이 깨진다.

📖 풀이:
핵심 아이디어: 윌슨 정리를 직접 적용한다. $17$이 소수이므로 $(17-1)! = 16! \equiv -1 \pmod{17}$. $-1 \equiv 16 \pmod{17}$이므로 나머지는 $16$. (직접 곱셈에서도 $2\cdot 3\equiv6,\ \dots$ 짝지어 $1$로 소거되고 마지막에 $-1$이 남음을 확인할 수 있다.)

📖 풀이:
핵심 아이디어: 중국인 나머지정리. $x\equiv2\pmod3$와 $x\equiv2\pmod7$을 합치면 $x\equiv2\pmod{21}$. 따라서 $x\in\{2,23,44,\dots\}$. 이 중 $x\equiv3\pmod5$를 만족하는 것은 $23$ ($23\equiv3\pmod5$). 검산: $23\equiv2\pmod3,\ 23\equiv3\pmod5,\ 23\equiv2\pmod7$. 모듈러가 서로소이므로 해는 $\mathrm{mod}\ 105$에서 유일하다.

📖 풀이:
핵심 아이디어: $5$로 나눈 나머지(잉여류)는 $0,1,2,3,4$의 $5$가지뿐이다(비둘기집). $5$개를 고르면 모두 다른 나머지일 수 있어 두 수의 차가 $5$의 배수가 아닐 수 있다. 그러나 $6$개를 고르면 비둘기집 원리에 의해 같은 나머지를 갖는 두 수가 반드시 존재하고, 그 차는 $5$의 배수다. 따라서 최소 개수는 $6$.