2021 국제수학올림피아드 1번문제

$n$은 100 이상의 정수이다. 민수는 숫자 $n$, $n+1$, $\ldots$, $2n$을 서로 다른 $(n+1)$장의 카드에 각 각 하나씩 적고, 이 카드들을 섞은 후에 두 개의 묶음으로 나눴다. 이때 적어도 한 묶음에는 카드에 적힌 숫자의 합이 완전제곱수가 되는 두 장의 카드가 존재함을 보여라.

2021 국제수학올림피아드 5번문제

두 마리의 다람쥐 갑과 을이 2021개의 도토리를 모았다. 을은 2021개의 도토리에 1부터 2021까지의 숫자를 적었고,2021개의 구멍을 원형 배열로 팠다. 다음 날 갑이 각각의 구멍에 임의로 도토리를 하나씩 집어넣었다. 을은 2021번의 시행을 통하여 도토리를 재배열하는데, $k$-번째 시행에서는 숫자 $k$가 적혀있는 도토리에 인접한 두 도토리의 위치를 서로 바꾼다. 이때 다음을 만족하는 $k$가 존재함을 보여라: $k$-번째 시행에서 위치를 바꾸는 두 도토리에 적힌 숫자 $a$, $b$가 $a < k < b$를 만족한다.

2020 국제수학올림피아드 3번문제

서로 무게가 다른 조약돌 $4n$개가 있고 각 조약돌의 무게는 $1$, $2$, $3$, $\ldots$, $4n$ 중 하나이다. 각 조약돌은 $n$개의 색 중 하나로 색칠되어 있고, 같은 색을 가진 조약돌은 정확히 4개씩 있다. 이 때 다음 두 조건을 모두 만족하도록 조약돌을 두 개의 그룹으로 나눌 수 있음을 보여라.

  • 각 그룹의 조약돌의 무게의 총합은 서로 같다.
  • 각 그룹에는 각각의 색에 대하여 그 색으로 색칠된 조약돌이 정확히 2개 있다.

2020 국제수학올림피아드 4번문제

정수 $n > 1$이 있다. 한 산의 오르막에 $n^2$개의 역이 있고, 역들은 서로 다른 높이에 있다. 두 개의 케이블카 회사 A 와 B는 각각 $k$개의 케이블카를 운행한다. 각각의 케이블카는 낮은 위치에 있는 역에서 출발하여 더 높은 위치에 있는 역까지 운행한다. (중간에 멈추지 않는다.) A 회사 에서 운행하는 $k$개의 케이블카는 $k$개의 서로 다른 역에서 출발하여 서로 다른 $k$개의 역까지 운행하고, 더 높은 곳에서 출발한 케이블카는 더 높은 곳까지 운행한다. B 회사가 운행하는 케이블카도 같은 조건으로 운행한다. 두 역이 어떤 회사에 의해 연결된다는 것은 한 회사에서 운행하는 하나 또는 여러 개의 케이블카를 이용하 여 이 두 역 중 낮은 위치에 있는 역에서 높은 위치에 있는 역까지 이동할 수 있다는 것이다. (역들 사이의 다 른 이동은 허용되지 않는다)
두 회사 모두에 의해 연결되는 두 역이 항상 존재하는 가장 작은 양의 정수 $k$를 구하여라.

2019 국제수학올림피아드 3번문제

한 SNS망 안에 2019명의 이용자가 있고, 그들 사이에 어떤 친구관계가 존재한다. 이용자 A가 이용자 B와 친구관계이면, B도 A와 친구관계이다. 다음과 같은 이벤트가 반복적으로 시행된다고 하자.

세 명의 이용자 A, B, C에 대하여 A가 B, C와 친구관계이고 B와 C는 친구관계가 아닌 경우, 다음과 같이 친구관계를 바꾼다. B와 C는 친구관계가 되도록 하고, A와 B는 친구관계가 안 되고, A는 C와도 친구관계가 안 되도록 한다. 이때, 그 외의 친구관계는 바뀌지 않는다.

처음 단계에서, 1010명의 이용자 각각은 1009명의 이용자와 친구관게이고, 나머지 1009명의 이용자 각각은 1010명의 이용자와 친구관계라 하자. 위와 같은 이벤트를 계속 시행하여, 결국에는 모든 이용자들이 각각 한 명 이하의 이용자와 친구관계가 되도록 하는 일련의 이벤트가 존재함을 보여라.

2019 국제수학올림피아드 5번문제

Bath은행은 한 면은 H, 반대면은 T인 동전을 발행한다. Harry는 $n$개의 동전을 왼쪽에서 오른쪽으로 일렬로 늘어놓았다. 그는 다음과 같은 시행을 반복적으로 한다: 만일 이 동전 중 H가 정확히 $k$($k>0$)개가 있으면 왼쪽부터 $k$번째 동전을 뒤집는다. 만일 모든 동전이 모두 T이면 시행을 멈춘다. 예를 들어, $n=3$이고 초기 놓임이 THT인 경우, 다음과 같이 3번의 시행을 한 후 멈춘다. THT$\to$HHT$\to$HTT$\to$TTT.

(a) 초기 놓임이 어떠하든, Harry는 유한 번의 뒤집는 시행을 한 후에 시행을 멈추게 됨을 보여라.

(b) 각 초기 놓임 $C$에 대하여, $L(C)$를 Harry가 시행을 멈추기 전까지 한 시행의 횟수라 하자. 예를 들어 $L(THT)=3$이고 $L(TTT)=0$이다. $2^n$개의 모든 가능한 초기 놓임 $C$에 대하여, $L(C)$의 평균값을 구하여라.