$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번문제
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)$의 평균값을 구하여라.