영희 , 철수 , 순돌이는 중국집에 갔다. 이 중국집에는 짜장면, 짬봉 두 가지 메뉴만있는 특화된 중국집이다. 그러면 이 세 사람 중 "적어도 두 사람은 같은 음식"을 시킬수 밖에 없겠죠.비둘기집의 원리란? 즉 n 마리의 비둘기가 있고 , 집이 n-1 개 가 있는 경우 적어도 두 마리는 같은 집에 들어간다.
이 개념에 적용하면 수가 n 개인 인 경우 비둘기 네 마리가 자기 집(0,1,2...,n-1)을 하나 가진 경우이 두가지 조건 중 하나라도 발생하면 이 비둘기 집중 한 곳은 비게 되겠죠.
- 이 비둘기 중 한마리라도 다른 집으로 가거나, ( 차가 n 이상의 수를 가지거나 )
- 한 집에 두마리가 들어가면(차가 0,1,2...n-1 중 2 개 이상 발생)
비둘기 집을 이용한 좋은문제 어디 없을까요? 보충 부탁드립니다.
2 혹은 5 로 나누어지지 않는 n 은 모든 자리수가 1 인 배수를 가진다1 , 11 , 111 세 수중 한 수는 3 의 배수이다. 1 , 11 , 111 , 1111 , 11111 , 111111 , 1111111 중 적어도 한 수는 7 의 배수이다.
이 성질은 2 혹은 5 로 나누어지지 않는 수에서 성립합니다. 3 ,7 은 2 혹은 5 로 나누어지지 않는 수 입니다.
(문제) 1 , 11 , 111 중 한 수는 적어도 3 의 배수이다.
(증명) 귀류법을 이용합니다.
"1 , 11 , 111 은 모두 3 의 배수가 아니다" 그러면 이 세 수는 3 으로 나눌 때 나머지가 1 혹은 2 가 됩니다. 그런데 수가 세 개이니 이를 비둘기집의 원리를 적용하면 수가 세개이고 나머지는 1 혹은 2 가 나와야 하므로 세 수 중 적어도 두 수는 같은 나머지를 가져야 하고, 같은 나머지를 가지는 두 수를 빼면 3 의 배수가 되어야 합니다. 여기에서 나올수 있는 두 수의 차는1 , 11 , 111 은 3 의 배수가 아니다라는 가정했으므로 10 혹은 100 이 3 의 배수가 되어야 하는데 3 은 10 의 배수가 아닙니다. 즉 가정에 모순되어서 1 , 11 , 111 중 한 수는 3 의 배수입니다.
- 11 - 1 = 10 = 1 * 10
- 111 - 1 = 110 = 11 * 10
- 111 - 11 = 100 = 1 * 100
(일반화) n 이 2 혹은 5 로 나누어지지 않으면 1,11 , 111 , 1111 , 11111 , 111111, 1111111, 1....1(1 이 n 개) 중 한 수는 n 의 배수이다
(증명)
1 , 11 , 111 , ... , 111...1 이 모두 n 의 배수가 아니다. 수의 개수가 n 이므로 이 수 중 적어도 나머지가 같은수 두 개는 존재한다. 이 두 수를 11..1(1 이 i 개) , 111.....1(1 이 j 개) i < j 라고 하고 , 두 수를 빼면 11..1(1 의 개수가 j-i개) * 10^i 11..1 은 n 의 배수가 아니다라고 했음로 10^i 는 n 의 배수가 되어야 함. 그런데 n 은 2 혹은 5 로 나누어진다라는 가정에 모순
출처:dovelet