"AOPS 문제들이 너무 체계적이지 않다"라고 친구에게 불평했더니 IMO 쇼트를 풀어보라는 답변이 돌아왔다. 그 친구의 말을 믿어도 될런지 모르겠지만... 일단 풀거나 Give up한 순서대로 포스팅해보자. N2. (solved, 171231)Find all natural number \(n\) s.t. \(\tau (n)^3 = 4n\).전형적인 수론함수 노가다 문제이다. 내가 잘 푸는 몇 안되는 유형... 일단 \(n\)을 다음과 같이 소인수분해할 수 있음이 자명하다. $$ n = 2^{3b+1} \cdot p_{1}^{3a_1}p_{2}^{3a_2} \cdots p_{t}^{3a_{t}}$$ 이 때 \((\frac{\tau(n)^3}{4n})^{\frac{1}{3}} = \frac{3b+2}{2^{..

http://codeforces.com/contest/908 Result : A, B, C(+3), D (4 / 8) Rating Change :1985 -> 2046 (+61, 343rd place) Editorial : This section is intentionally left blank. A. New Year and Counting Cards (04 : 52) Tag : Implementation A 답게 간단한 문제이다. 모든 홀수와 모음의 개수가 답이 된다. 대회에서는 문제 해석 + 코드 세팅하느라 시간을 많이 잡아먹었다. B. New Year and Buggy Bot (20 : 24) Tag : Brute - Force B 답게 간단하...지만 일단 그리드이기 때문에 코딩이 빡친다. 다양한..

#003은 현재 미완성 + 비공개 상태이다.문제 링크 모든 실수 \(x,y\)에 대해 다음 식을 만족하는 함수 \(f : \mathbb{R} \rightarrow \mathbb{R}\)를 모두 구하여라. $$ \frac{f(x)+f(y)}{2} = f(\frac{x+y}{2}) + (x-y)^2 $$This section is intentionally left blank. \((x-y)^2 = 2x^2 + 2y^2 - (x+y)^2\)이므로, 양변을 다음과 같이 정리할 수 있다. $$\frac{(f(x)-4x^2) \ + \ (f(y)-4y^2)}{2} = f(\frac{x+y}{2})-(x+y)^2$$ 따라서 \(g(x) = f(x) - 4x^2\)로 두면 다음이 성립한다. $$ g(x)+g(y) = ..

HGHC는 graph theory / combinatorics에서 오랫동안 제기되어 왔던 추측을 반증하는 lemma로, 확률론적 방법의 대표적인 예제이다. 확률론적 방법의 진수를 보여주는 lemma라고 생각하는데, 확률론적 방법 전체를 소개하기에는 너무 길고, 이 정리의 증명만 포스트에 싣기로 한다. 아마 wikipedia 수준의 사전 지식 이외에는 필요하지 않을 것이다. Thanks to. claim 0. Introduction 임의의 자연수 \(t, \ u\)에 대해 \(g(G) > t\)와 \(\chi (G) > u\)를 동시에 만족하는 그래프 \(G\)가 존재한다. 여기서 그래프의 girth \(g(G)\)는 \(G\)에서 가장 작은 cycle의 크기를 의미하고, \(\chi (G)\)의 경우 g..

문제 링크 홀수 소수 \(p\)에 대해, \(1,2, \cdots \lfloor \sqrt{p} \rfloor + 1\)의 수 중 \(p\)에 대한 이차비잉여가 반드시 존재함을 보여라. This section is intentionally left blank to protect you from spoiler. 가장 작은 이차비잉여를 \(b \le p-1\)라고 하고, 귀류법으로 \(b \ge \lfloor \sqrt{p} \rfloor + 2\)라고 하자. 그렇다면 \(b \ | \ p+r\)을 만족하는 정수 \(0 \le r \le b-1\)이 존재한다. 이 때 \(p + r = ab\)라고 놓으면, \(a \ge\lfloor \sqrt{p} \rfloor + 2\)일 경우 \(p = ab-r > ab..

문제 링크 스포 방지를 위해 더보기 기능을 쓰니까 수식이 깨지는 문제가 있어서 그냥 밑으로 내리기로 했다. statement : \(\omega := \omega^p = 1\)의 한 허근$$ X := \sum_{\text{k : Quadratic Residue of mod }p}\omega^{k} $$ $$ Y := \sum_{\text{k : Quadratic Irresidue of mod }p}\omega^{k} $$ \(XY \in \mathbb{Z}\)임을 보여라. 이차잉여 개념을 이용해서 해결할 수 있는데, 수업 시간에 배우기도 했던 중요한 Lemma를 사용할 수 있다. 일단 \(X,Y\)가 굉장히 보기 싫으니까 이렇게 바꾸자. $$ X = \frac{1}{2}\sum_{k=1}^{p-1}(1+..