어려운 정수론 문제 2개
문제1: 소수 \(p\)와 양의 정수 \(a_1, a_2, ... , a_p\)에 대하여 다음 조건을 만족하는 양의 정수 \(k\)가 존재함을 보여라. $$ a_1+k, a_2+2k, ... , a_p+pk $$ 를 \(p\)로 나눈 나머지들이 적어도 \(p/2\)개 이상의 서로 다른 값를 갖는다. [2018 USAMO P4] (sol) 더보기 \(k=1, 2, ... , p\)에 대해 무향그래프 \(G=G_1, G_2, ... , G_p\) 를 구성하자. \(a_i\)에 해당하는 점을 \(i\)로 둔다. \(a_i+ik\equiv a_j+jk \quad(\textup{mod} \; p) \)를 만족하면 점 \(i\)와 \(j\)를 잇는다. (단, \(i < j\)) 이 때, $$ a_i+ik\equiv..
2023. 12. 26.
멋진 정수론 문제들
정말 좋은 문제들이니 충분한 고민을 거쳐 풀어보자. 문제1 : 다음 조건을 만족하는 양의 정수 순서쌍 \((a, b, c)\) 을 모두 구하여라. $$ \textup{lcm}(a, b, c)=\frac{ab+bc+ca}{4} $$ [Japan 2020 Final] (sol) 더보기 일반성을 잃지않고 \(a \geq b \geq c \)라고 하자. \(a | \textup{lcm}(a,b,c) \)이고 \(a|ab+ca\)이므로 \(a|bc\)이다. 따라서 \(\textup{lcm}(a,b,c) \leq bc\)가 성립한다.. 즉, 최댓값이 \(bc\)이고 \(\textup{gcd}(b, c)>1\)이라면 \(bc/p \)꼴이 된다. 그런데, \(ab+bc+ca \geq 3bc\)이므로, $$ \frac{..
2023. 12. 21.
2021 IMO Problem 6 [대수/조합]
문제: \(2\) 이상의 양의 정수 \(m\)에 대하여 정수들의 유한집합 \(A\)의 부분집합 \(B_1, B_2, ..., B_m\)은 각각의 \(k=1, 2, ..., m\)에 대하여 \(B_k\)의 모든 원소의 합이 \(m^k\)이다. 이 때, \( n(A)\geq m/2 \)임을 증명하여라. 2021 국제수학올림피아드 마지막 문제이다. 짧지만 풀기 어려운 문제다. hint 1) 더보기 \(m^1, m^2, ... , m^k\)를 보니 왠지 \(m\)진법이 떠오른다. hint 2) 더보기 더블카운팅을 이용해보자. 풀이) 더보기 \(A=\left\{a_1, a_2, ..., a_n \right\}\)라고 하자. \(B_k\)는 원소의 합이 \(m^k\)이므로, 다음과 같이 표현 가능하다. $$ m^k..
2023. 12. 19.
아이디어 문제 1개
문제: 양의 실수 \(a_1, a_2, ... , a_n\)에 대하여, \(b_i=(a_{i-1}+a_{i+1})/a_i \) 로 정의한다. (단, \(a_0=a_n, a_{n+1}=a_1 \)) 이 때, 다음 조건이 성립한다. (조건): 모든 \(1\leq i, j\leq n \)에 대해 \(a_i \leq a_j \)와 \(b_i \leq b_j \)는 필요충분조건이다. 이 때, 수열 \(a_n\)은 모든 항이 같음을 보여라. (풀이) 더보기 \(m=\min(a_1, ..., a_n)\)이라 하고, \(M=\max(a_1, ..., a_n)\)이라 하자. 어떤 \(x, y\)가 존재하여 \(a_x=m, a_y=M\)을 만족한다. \(a_x \leq a_y\)가 성립함은 자명하다. 이 때, $$ b_x..
2023. 12. 16.