11개의 정수 중 6개의 수를 선택하여 6의 배수 만들기 (출처 : KMO)

[질문]

 

KMO 17회 2차 (2003년) 중등부 4번 문제입니다.

 

http://www.kms.or.kr/home/kmo/

 

4. 임의의 정수 11개가 주어지면, 그 중 6개를 뽑아 그 합이 6의 배수가 되게 할 수 있음을 보여라. 단, 주어진 11 개의 정수가 모두 서로 다를 필요는 없다.

 

[답]

임의의 정수 11개를 홀수는 홀수끼리 짝수는 짝수끼리 짝을 맺는다.

이렇게 하면 합이 짝수인 쌍이 5개가 생긴다.  5개 미만으로는 생길 수 없다.

 

짝수인 쌍은 2n+0, 2n+2, 2n+4 로 표시할 수 있다.

 

가장 많은 종류의 쌍이 3개 이상이 있다면, 그 종류의 쌍 3개를 선택해서 더하면 6의 배수가 된다.

가장 많은 종류의 쌍이 3개 미만이 있다면, 모든 종류의 쌍이 존재한다.  그러므로 각각의 종류의 쌍을 더하면 6의 배수가 된다.

 

그러므로 임의의 정수 11개중 6개를 뽑아서 그 합이 6의 배수가 되게 할 수 있다.