전설적인 IMO 문제

양의 정수 가 있어 이 정수라면, 이 값은 완전제곱수이다. 1988년 호주에서 열린 IMO(국제수학올림피아드)의 6번 문제. IMO 역사에서 아직도 전설적인 문제로 남아있고, IMO 사상 가장 어려운 문제라고도 일컬어지고 있다. 단순히 정답률만 따지면 2017년 3번 문제가 가장 어려운 문제로 등극할 수도 있지만 (7명만이 1점 이상의 점수를 받았고 2명만이 7점 만점을 받았다) 위 문제의 경우 그와 관련된 아래의 […]

Read More 전설적인 IMO 문제

소수의 무한성

소수는 무수히 많이 존재한다. 정수론에서 가장 근본에 위치하는 기본적인 명제이면서 수학의 역사에서 가장 중요한 역할을 차지하는 결과물 중의 하나인 명제이다. 유클리드가 귀류법으로 증명한 이래 수많은 다양한 증명이 등장했는데, 피타고라스의 정리가 200가지가 넘는다해도 사실 많은 증명들은 다소 대동소이한 경우가 많은 반면 이쪽은 정말 그야말로 완벽히 다른 분야의 맥락에서 증명되는 경우도 많아 더 의미가 있다고 봄. 대부분 […]

Read More 소수의 무한성

다음 소수를 찾는 또 다른 방법 (2)

이전 글: (1) 최근 AMM에 또 다른 소수 생성식이 실렸다.[1] 어떤 상수 를 잡으면, 로 정의한 수열 의 정수부 은 번째 소수 이 된다는 것. 마치 특정 상수로부터 소수들만을 얻게 된다는 점에서 Mills’ theorem과 비슷하지만(“수학적으로 화수를 표현하는 특촬“에서 잠깐 소개된 적이 있다) 이전 글에서 소개한 정리처럼 모든 소수들을 순차적으로 찾을 수 있다는 점에서 차이가 있다. […]

Read More 다음 소수를 찾는 또 다른 방법 (2)

반원 위에 있을 확률, 반구 위에 있을 확률

원 위에 임의로 균일하게 개의 점을 잡았을 때 그들이 한 반원 위에 있을 확률은? 브레인 티저로도 종종 쓰이는 유명한 문제. Bull이 1948년 Mathematical Gazette에 한 문제를 냈고[1], Rushton이 1949년 동지에 해당 문제를 이 문제로 변형하여 매우 간단한 증명을 내놓았다.[2] 먼저 개의 점을 이라 둔다. 원 위에서 에서 시작해 시계방향으로 움직여 의 반대쪽까지 움직이면서 지나게 되는 […]

Read More 반원 위에 있을 확률, 반구 위에 있을 확률

랜덤 워드에서 특정 워드가 등장할 확률 (3)

이전 글: (1), (2) 이전 글에서는 알파벳 집합이 , 그 사이즈가 로 정해져있을 때 특정 워드 가 들어가지 않는 길이 의 워드 개수는 의 해들로 표현될 수 있음을 보였다. (은 의 길이, 는 의 순환주기) 이 특성방정식을 에 대해 미분한 식과 이 식이 공통근을 갖지 않으므로 중근이 없어, 더 정확히 말하자면 이 해들의 거듭제곱의 선형합이라 […]

Read More 랜덤 워드에서 특정 워드가 등장할 확률 (3)

조합적으로 증명하는 삼각함수식

탄젠트와 시컨트의 정의만 알면 바로 증명되는 항등식인데 이것을 조합적으로 보일 수 있다. 그를 위해선 몇 가지 해석적인 작업이 조금 필요함. 일전에 “의 조합적 증명“에서 소개했던 교대순열이란게 있다. 교대순열은 를 만족시키는 순열. 부등호가 < > < > … 으로 정의되는 경우도 있으며 위 글 역시 그러한데, 여기서는 > < > < …으로 정의하고, < > < > […]

Read More 조합적으로 증명하는 삼각함수식

조합적으로 증명하는 합동식

정수론의 기초에서 다뤄지는 여러 합동식들 중 조합적인 아이디어로 증명하는 것이 가능한 경우가 있다. 여기서 일부 그러한 증명들을 소개하고자 함. 먼저, 소수 와 정수 에 대해 가 성립한다는 페르마의 소정리를 조합적으로 보일 수 있다. 원 하나를 개의 동일한 부채꼴로 등분한다. 이 부채꼴들을 주어진 개의 색들로 칠한다면, 그 모든 경우의 수는 가 된다. 이 색칠된 결과는 크게 […]

Read More 조합적으로 증명하는 합동식