오늘은 정수집합과 관련된 문제를 소개합니다. ^^
집합 A = {1, 2, 3, ···, 37} 의 부분집합 S 가 다음 조건을 만족할 때 n(S) 의 최대값은?
조건 : a∈S, b∈S (a≠b) 이면 a+b≠5k (k 는 자연수)
먼저,
조건에 맞는 S 의 원소를 써보면 {1, 2, 5, 6, 7, 11 ······}
이 되는 것을 알 수 있습니다.^^
그러나 ····, 이러한 방법으로는 S 를 구하기 어려우므로 ······
집합 A 의 원소를 5로 나눌 때 나머지가 같은 수 집합으로
나누어 놓고 생각해봅니다.^^
1, 6, 11, 16, 21, 26, 31, 36 ← 5m+1
(m = 0,1,2,3,4,5,6,7)
2, 7, 12, 17, 22, 27, 32, 37 ← 5m+2
(m = 0,1,2,3,4,5,6,7)
3, 8, 13, 18, 23, 28, 33 ← 5m+3
(m = 0,1,2,3,4,5,6)
4, 9, 14, 19, 24, 29, 34 ← 5m+4
(m = 0,1,2,3,4,5,6)
5, 10, 15, 20, 25, 30
← 5m (m = 1,2,3,4,5,6)
위에서 5m+1, 5m+2 으로 나타내어지는 집합에 속하는 두 개의 수를 더하면 a+b≠5k 을 만족합니다. 따라서 5m+1, 5m+2 에 속하는 16 개의 수를 S 에 넣고 5m 에 속하는 수 중에서 한 개를 택하여 S 에 넣어도 조건이 만족되므로 집합 S 의 원소의 최대값은 8+8+1 = 17 입니다. ^^
♧ 정리하여 둡시다.
1)
2k, 2k+1 (2 로 나눌 때 나머지가 같은 수 집합)
2) 3k, 3k+1, 3k+2 (3 으로 나눌 때 나머지가
같은 수 집합)
3) 4k, 4k+1, 4k+2, 4k+3 (4 로 나눌 때 나머지가
같은 수 집합)
Today's Quotation
Beware of the young doctor and the old barber.
-Benjamin Franklin -