양의 정수 $n$에 대하여, $x+y+2z+3w=n-1$을 만족하는 음이 아닌 정수의 순서쌍 $(x,y,z,w)$의 개수를 $p(n)$이라고 하고, 다음 세 조건을 모두 만족하는 음이 아닌 정수의 순서쌍 $(a,b,c,d)$의 개수를 $q(n)$이라 하자.
(i) $a+b+c+d=n$
(ii) $a \ge b$이고 $c \ge d$이며 $a \ge d$이다.
(iii) $b<c$
모든 $n$에 대하여 $p(n)=q(n)$임을 보여라.
카테고리 보관물: 조합
2018 제32회 한국수학올림피아드 고등부 6번문제
서로 다른 $n$개의 양의 정수로 이루어진 집합 $S$에 대하여, 다음 조건을 만족하는 일대일대응 $f:\{1,2,\dots,n\}\to S$가 항상 존재함을 보여라. (단, $n$은 $3$ 이상인 정수이다.)
모든 $1\le i < j < k \le n$에 대하여, $\left(f(j)\right)^2 \ne f(i) \cdot f(k)$이다.
2018 제32회 한국수학올림피아드 중등부 4번문제
양의 정수 $n$에 대하여, $x+2y+2z+3w=n$을 만족하는 음이 아닌 정수의 순서쌍 $(x,y,z,w)$의 개수를 $p(n)$이라 하고, 다음 세 조건을 모두 만족하는 음이 아닌 정수의 순서쌍 $(a,b,c,d)$의 개수를 $q(n)$이라 하자.
(i) $a+b+c+d=n$
(ii) $a \ge b \ge d$
(iii) $a \ge c \ge d$
모든 $n$에 대하여 $p(n)=q(n)$임을 보여라.
2018 제32회 한국수학올림피아드 중등부 8번문제
서로 다른 $n$개의 정수로 이루어진 집합 $S$에 대하여, 다음 두 조건을 모두 만족하는 함수 $f \colon \{1, 2, \ldots, n\} \to S$가 항상 존재함을 보여라. (단, $n$은 $3$ 이상인 정수이다.)
(i) 집합 $\{ f(1), f(2), \ldots, f(n) \}$는 $S$와 같다.
ii) 모든 $1\le i < j < k \le n$에 대하여, $2 f(j) \ne f(i)+f(k)$이다.
2018 국제수학올림피아드 3번문제
정수들의 다음과 같은 정삼각형 모양의 나열을 역파스칼삼각형이라 하자: 가장 밑줄에 있는 수들을 제외하고, 나머지 각 수들은 바로 밑에 있는 두 수의 차(의 절대값)이다. 예를 들어, 다음 나열은 네 개의 가로줄로 이루어지고 $1$부터 $10$까지의 모든 수가 등장하는 역파스칼삼각형이다.
4
2 6
5 7 1
8 3 10 9
2018개의 가로줄로 이루어지고 $1$부터 $1+2+\dots +2018$까지의 모든 수가 등장하는 역파스칼삼각형이 존재하겠는가?
2018 국제수학올림피아드 4번문제
좌표평면 위의 점 $(x,y)$에 대하여, $x$와 $y$가 모두 $20$ 이하의 양의 정수일 때, 이 점을 지점이라 하자.
$400$개의 지점이 처음엔 모두 비어 있다. 수영과 상일이 번갈아 빈 지점에 돌을 놓고, 수영이 먼저 시작한다. 수영은 자기 차례에 빈 지점에 새로운 빨간 돌 하나를 놓되, 빨간 돌이 놓인 어떤 두 지점 사이의 거리도 $\sqrt{5}$가 되지 않도록 놓는다. 상일은 자기 차례에 빈 지점에 새로운 파란 돌 하나를 놓는다. (파란 돌은, 돌이 놓여 있는 지점과의 거리에 상관없이, 빈 지점 어디에나 놓을 수 있다.) 이 게임은 한 사람이 더 이상 돌을 놓을 수 없을 때까지 진행한다.
상일이 어떤 전략으로 파란 돌들을 놓든지 상관없이, 수영이 항상 최소한 $K$개의 빨간 돌을 놓을 수 있는 $K$값 중 가장 큰 값을 구하여라.