말랑말랑 수학문제 #10

<문제>

다음 조건을 만족하는 가장 작은 자연수 $n \geq 4$ 를 구하여라.

임의의 서로 다른 $n$ 개의 정수들에 대해서 언제나 다음과 같은 조건을 만족하는 서로 다른 4개의 수 $a, b, c, d$ 를 고를 수 있다.

 

'$a+b-c-d$ 는 $20$ 으로 나눠 떨어진다'

 

-----풀이 스포를 주의하세요-----

 

 

 

 

 

 

 

 

 

 

<풀이>

문제의 풀이에 앞서 $n$ 개의 정수들을 각각 $20$ 으로 나눈 나머지로 생각하자. $(\because$ $20$ 의 배수는 $20$ 으로 나눈 나머지가 $0$ 과 동일한 말이기 때문에$)$

 

$a+b-c-d$ 가 $20$ 으로 나눠 떨어진다 라는 의미는 쉽게 생각해보면, 서로 다른 $m$ 개의 정수들에 대해서 총 $\binom{m}{2}$ 개의 두 수의 합을 나열하였을 때 $20$ 으로 나눈 나머지가 동일한 $2$ 개의 수가 존재한다는 뜻이다.

 

$m \geq 7$ 이상이면 $\binom{7}{2} \geq 21$ 인데 $20$ 으로 나눈 나머지는 $0, 1, 2, \cdots,19$ 여서 $21$ 개의 두 수 합 중 $20$ 으로 나눈 나머지가 같아지는 경우가 존재하여 $a+b-c-d$ 가 $20$ 으로 나눠 떨어지게 된다.

하지만 문제에서 $n$ 개의 정수를 뽑을 때 $20$ 으로 나눈 나머지가 서로 다를 필요는 없으므로 우리가 구하고 싶은 $n$ 은 $7$ 보단 좀 더 늘어나게 된다.

 

만약 $n$ 개의 정수들 중 두 수 이상이 중복된다면, 각각 $x, y$ 라고 하자. $x+y-y-x$ 는 $20$ 으로 나눈 나머지가 $0$ 이므로 $20$ 의 배수가 되어서 모순이다. (여기서 $x,y$ 는 $20$ 으로 나눈 나머지이므로 실제로는 다른 수들이다.)

 

따라서 $n$ 개의 정수들 중 반복될 수 있는 수는 한 종류뿐이고, 그 수도 $4$ 개 이상이 되면 $a, b, c, d$ 를 그 $4$ 개로 뽑으면 $20$ 의 배수가 되기 때문에 모순이다. 

따라서 $7+2$ 해서 $n \geq 9$ 인 경우에 문제가 성립함을 알 수 있다.

$n = 8$ 인 경우의 반례를 살펴보면, 

 

$$\{ 1, 1, 1, 2, 3, 5, 8, 13 \}$$

 

이 집합에선 수 $4$ 개를 어떻게 뽑더라도 $a+b-c-d$ 가 $20$ 으로 나눠 떨어지지 않는다. (실제로는 $1, 1, 1$ 대신 $1, 21, 41$ 이 들어가는 것이 맞지만 편의상 저렇게 적었다.)

따라서 가장 작은 자연수 $n$ 은 $9$ 가 된다.

답) 9