평면 위의 $n$개의 정사각형의 집합이 아래 세 조건을 모두 만족시키면 셋연결되어 있다고 하자.
(i) 모든 정사각형은 합동이다.
(ii) 만일 두 정사각형에 동시에 속한 점 $P$가 있다면, $P$는 이 두 정사각형 각각의 꼭짓점이다.
(iii) 각각의 정사각형은 정확히 세 개의 다른 정사각형과 만난다.
셋연결된 $n$개의 정사각형이 존재할 양의 정수 $n$ 중 $2018\le n\le 3018$인 것은 모두 몇 개인가?
카테고리 보관물: 조합
2018 미국수학올림피아드 4번문제
어떤 소수 $p$개 만큼의 정수 $a_1$, $a_2$, $\ldots$, $a_p$가 있다. 이때 \[ a_1+k, a_2+2k, \ldots, a_p+pk\] 각각을 $p$로 나눈 나머지로 얻을 수 있는 값이 적어도 $p/2$개 이상이 되도록 하는 정수 $k$가 존재함을 보여라.
2018 미국수학올림피아드 6번문제
정수 $1$, $2$, $\ldots$, $n$으로 이루어진 순열 $(x_1,x_2,\ldots,x_n)$ 중 $n$개의 비율 $\frac{x_k}{k}$ (단, $1\le k\le n$)의 값이 모두 서로 다른 것의 수를 $a_n$이라 하자. 이때 모든 양의 정수 $n$에 대하여 $a_n$은 홀수임을 보여라.
2018년 유럽여학생수학올림피아드 3번문제
EGMO 참가자 $n$명을 $C_1$, $C_2$, $\ldots$, $C_n$이라 하자. 대회가 끝난 후 식당에 참가자들이 다음 규칙을 모두 만족하도록 줄을 선다.
- 심판이 처음에 참가자들이 서는 줄 순서를 먼저 정해준다
- 매 1분마다 심판이 정수 $i$ ($1\le i\le n$)를 고른다.
- 만일 $C_i$ 앞에 있는 사람 수가 $i$명 이상인 경우 이 사람은 1유로를 심판에 내고 줄에서 정확히 $i$칸 앞으로 이동한다.
- 만일 $C_i$ 앞에 있는 사람 수가 $i$명이 되지 않는 경우 식당이 영업을 시작하고 이 게임이 끝난다.
(a) 심판이 어떻게 하더라도 이 게임이 무한정 계속될 수는 없음을 보여라.
(b) 각각의 $n$에 대하여 심판이 받을 수 있는 돈의 최댓값을 구하라.
2018년 유럽여학생수학올림피아드 4번문제
도미노란 $1\times2$나 $2\times 1$ 형태의 타일을 뜻한다.
정수 $n\ge 3$이 있다. 이제 $n\times n$ 바둑판에 각각의 도미노가 정확히 두 칸을 차지하고 서로 겹치지 않도록 올려놓으려고 한다.
어떤 열이나 행의 값이란, 그 열, 혹은 그 행을 일부라도 덮고 있는 도미노의 수를 뜻한다. 도미노를 올려놓았을 때 만일 각각의 열, 각각의 행 모두 정확히 값이 $k$가 되는 어떤 양수 $k$가 존재하면 균형이 잡혔다고 하자.
임의의 $n\ge 3$에 대하여 균형잡힌 도미노 배치가 존재함을 보여라. 그리고 그러한 도미노 배치에서 필요한 도미노 수의 최솟값을 구하여라.
2018 캐나다수학올림피아드 1번문제
평면 위에 여러 동전이 놓여 있는데 한 점에 여러 동전이 있을 수도 있다. 다음과 같은 작업을 계속 하는 것이 허용된다: 점 $A$에 있는 동전과 점 $B$에 있는 동전이 있을 때 두 동점을 모두 $A$, $B$의 중점으로 옮긴다.
처음에 놓인 동전 $n$개를 위 작업을 유한번만 하여 모두 같은 점으로 이동하도록 할 수 있으면 그 동전 $n$개의 배치를 모을 수 있는 배치라고 하자. 모든 $n$개의 동전 배치가 다 모을 수 있는 배치가 될 필요충분조건은 $n$이 $2$의 거듭제곱임을 보여라.