2020년 과고2 확률과 통계 - 비둘기집 원리 프린트

 

1. 한 변의 길이가 $\displaystyle 2 $인 정사각형에 $\displaystyle 5 $개의 점이 있으면, 두 점 사이의 거리가 $\displaystyle \sqrt {2} $이하인 두 점이 반드시 존재함을 보여라.

 

https://youtu.be/iW0qIHKZMV8(구독과 좋아요)

 

 

오른쪽의 그림처럼 한 변이 $\displaystyle 2 $인 정사각형을 $\displaystyle 1 \times 1 $인 한 변의 길이가 정사각형 넷로 나누자. 이 $\displaystyle 4 $개의 정사각형에 $\displaystyle 5 $개의 점을 넣으면 정사각형 중에 두 개의 점이상을 가진 정사각형이 존재한다. 이 정사각형의 내부의 임의의 두점 사이의 거리는 $\displaystyle \sqrt {2} $이하이므로 두 점 사이의 거리가 $\displaystyle \sqrt {2} $이하인 두 점이 반드시 존재한다.

 

 

 

 

 

 

2. $\displaystyle 28 $마리의 금붕어를 $\displaystyle 9 $개의 어항에 넣으려고 한다. $\displaystyle 4 $마리 이상의 금붕어가 들어가는 어항이 있음을 보여라.

 

 

https://youtu.be/Cmfgl1DLqPY (구독과 좋아요)

 

$\displaystyle 4 $마리 이상의 금붕어가 들어가는 어항이 없게 하려면 $\displaystyle 9 $개의 어항에 3마리 이하로 넣어야 한다. 그러면 금붕어의 개수는 $\displaystyle 27 $개다. 그런데 $\displaystyle 28 $마리의 금붕어가 있으므로 어느 한 어항에는 $\displaystyle 4 $마리 이상 금붕어가 들어간다.

 

 

 

3. $\displaystyle 100 $이하의 자연수 중에서 $\displaystyle 10 $개를 뽑아 만든 집합을 $\displaystyle A $라 하자. 그러면 $\displaystyle A $에는 공집합이 아니고 서로소이며 원소의 합이 같은 두 부분집합이 있음을 보여라.

 

https://youtu.be/xh6Pzgdoajw (구독과 좋아요)

 

 

(증명) 집합 $\displaystyle A $의 $\displaystyle 2 ^ {10} =1024 $개의 부분집합을 $\displaystyle A _ {1} ,~A _ {2} ,~ \cdots ,~A _ {1024} $라고 하고

$\displaystyle i=1,2,3, \cdots ,1024 $에 대하여 $\displaystyle A _ {i} $의 원소의 합을 $\displaystyle s _ {i} $라 하면

$$\displaystyle 0 \leq s _ {i} \leq 91+92+ \cdots +100=995 $$

이므로

$$\displaystyle \left\{ s _ {1} ,s _ {2} , \cdots ,s _ {1024} \right\} \subset \left\{ 0,1, \cdots ,995 \right\} $$

비둘기집의 원리에 의해 $\displaystyle s _ {i} =s _ {j} $인 $\displaystyle i,~j ( i \neq j) $가 존재한다. 이제 두 집합 $\displaystyle X,~Y $를

$$\displaystyle X=A _ {i} - \left ( A _ {i} \cap A _ {j} \right ) ,~ Y=A _ {j} - \left ( A _ {i} \cap A _ {j} \right ) $$

로 두면 집합 $\displaystyle X,~Y $는 원소의 합이 같고 서로소인 집합 $\displaystyle A $의 부분집합이다.

 

 

 

4. $\displaystyle 100 $명이 참가한 어느 모임에서 참가자들은 다른 참가자들과 악수를 하였다. 이 모임에 참가한 사람 중에는 악수한 횟수가 같은 두 사람이 있음을 보여라.

 

https://youtu.be/yr0YMPpdBF8 (구독과 좋아요)

 

 

 

증명) $\displaystyle 100 $명 각각의 개인이 악수한 횟수는 $\displaystyle 0 $에서 $\displaystyle 99 $번이다. 그런데 악수한 횟수가 $\displaystyle 0 $명인 사람이 있다면 악수횟수가 $\displaystyle 99 $명인 사람이 존재할 수 없다. 즉 악수한 횟수 $\displaystyle N $는

$\displaystyle 0 \leq N \leq 98 $이거나 $\displaystyle 1 \leq N \leq 99 $이다. 그런데 100명이 있으므로 비둘기 집의 원리에 의해 악수한 횟수가 같은 두 사람이 반드시 존재한다. (참고 비둘기는 $\displaystyle 100 $, 비둘기집은 $\displaystyle 99 $)

 

https://youtu.be/MBf2-7IPIKA (구독과 좋아요)

 

 

5. 서로 다른 $\displaystyle 52 $개의 정수를 포함하고 있는 집합을 $\displaystyle A $라 하자.

(1) 집합 $\displaystyle A $에는 두 수의 합이나 차가 $\displaystyle 100 $의 배수인 두 수가 있음을 보여라.

(2) 두 수의 합이나 차가 $\displaystyle 100 $의 배수가 되지 않도록 $\displaystyle 51 $개의 정수를 뽑아라.

 

https://youtu.be/MBf2-7IPIKA(구독과 좋아요)

 

 

 

(1) 집합 $\displaystyle A= \left\{ a _ {1} ,a _ {2} , \cdots ,a _ {52} \right\} $라 하자. $\displaystyle i=1,2,3, \cdots ,52 $에 대하여

$\displaystyle a _ {i} =100q _ {i} +b _ {i} $ ($\displaystyle q _ {i} ,~b _ {i} $는 정수, $\displaystyle 0 \leq b _ {i} <100 $)

로 나타낼 수 있다.

① 어떤 $\displaystyle b _ {i} $와 $\displaystyle b _ {j} $가 서로 같으면 즉 $\displaystyle b _ {i} =b _ {j} $ ($\displaystyle i \neq j $)이면

$\displaystyle a _ {i} -a _ {j} = \left ( 100q _ {i} +b _ {i} \right ) - \left ( 100q _ {j} +b _ {j} \right ) =100 \left ( q _ {i} -q _ {j} \right ) $

이므로 두 수 $\displaystyle a _ {i} $와 $\displaystyle a _ {j} $의 차는 $\displaystyle 100 $의 배수이다.

② 모든 $\displaystyle b _ {i} $가 다르면 $\displaystyle b _ {1} ,~b _ {2} ,~ \cdots ,~b _ {52} $는 다음 $\displaystyle 51 $개의 집합

$\displaystyle \left\{ 0 \right\} ,~ \left\{ 1,99 \right\} ,~ \left\{ 2,98 \right\} , \left\{ 3,97 \right\} ,~ \cdots ,~ \left\{ 49,51 \right\} ,~ \left\{ 50 \right\} $ $\displaystyle \cdots \cdots (\mathrm{i})$

중 하나에 속해야 한다. $\displaystyle 52 $개의 수가 $\displaystyle 51 $개의 집합에 속하므로 비둘기집의 원립에 의해 어떤 $\displaystyle b _ {i} ,~b _ {j} $ ($\displaystyle i \neq j $)는 같은 집합에 속한다. $\displaystyle b _ {i} \neq b _ {j} $이므로 $\displaystyle b _ {i} ,~b _ {j} $는

$\displaystyle \left\{ 1,99 \right\} ,~ \left\{ 2,98 \right\} , \left\{ 3,97 \right\} ,~ \cdots ,~ \left\{ 49,51 \right\} $

중 하나의 집합에 속한다. 곧 $\displaystyle b _ {i} +b _ {j} =100 $이다. 따라서

$\displaystyle a _ {i} +a _ {j} $$\displaystyle = \left ( 100q _ {i} +b _ {i} \right ) + \left ( 100q _ {j} +b _ {j} \right ) $$\displaystyle =100 ( q _ {i} +q _ {j} )+ \left ( b _ {i} +b _ {j} \right ) $$\displaystyle =100 \left ( q _ {i} +q _ {j} +1 \right ) $

이므로 두 수 $\displaystyle a _ {i} $와 $\displaystyle a _ {j} $의 합은 $\displaystyle 100 $의 배수이다.

(2) (1)의 (i)에 있는 $\displaystyle 51 $개의 집합에서 한 원소씩 거내면 된다. 예를 들어

$\displaystyle \left\{ 0,1,2, \cdots ,49,50 \right\} $, $\displaystyle \left\{ 0,99,98, \cdots ,51,50 \right\} $

등은 두수의 합이나 차가 $\displaystyle 100 $의 배수가 되지 않는 정수의 집합이다.

 

 

 

 

6.어떤 운동선수는 $\displaystyle 11 $주($\displaystyle 77 $일) 동안 매일 한 번 이상, 일주일에 $\displaystyle 12 $번 이하로 연습한다고 한다. 이 선수가 연속으로 며칠동안 연습한 횟수의 합이 $\displaystyle 21 $이 되는 경우가 있음을 보여라.

 

 

https://youtu.be/3XYbJPxtMaw(구독과 좋아요)

 

 

첫째날부터 $\displaystyle i $째 날가지 연습한 횟수의 총합을 $\displaystyle a _ {i} $라 하면, 매일 한번이상 연습하고 일주일에 $\displaystyle 12 $번이하만 연습하므로

$\displaystyle 1 \leq a _ {1} <a _ {2} < \cdots <a _ {76} <a _ {77} \leq 12 \times 11=132 $

이다. 다음과 같은 $\displaystyle 154 $개의 자연수

$\displaystyle a _ {1} ,a _ {2} , \cdots ,a _ {77} ,a _ {1} +21,a _ {2} +21, \cdots ,a _ {77} +21 $ $\displaystyle \cdots \cdots $(i)

을 생각해보자. $\displaystyle a _ {1} +21<a _ {2} +21< \cdots <a _ {77} +21 \leq 153 $이므로 (i)에 있는 $\displaystyle 154 $개의 수는 모두 $\displaystyle 153 $이하인 자연수이다. 따라서 비둘기집의 원리에 의해 이들 중 적어도 두 수는 서로 같다. 한편, $\displaystyle a _ {1} ,a _ {2} , \cdots ,a _ {77} $는 서로 다르고 $\displaystyle a _ {1} +21,a _ {2} +21, \cdots ,a _ {77} +21 $도 서로 다르다. 결국 $\displaystyle a _ {1} ,a _ {2} , \cdots ,a _ {77} $ 중의 한 수 $\displaystyle a _ {i} $가 $\displaystyle a _ {1} +21,a _ {2} +21, \cdots ,a _ {77} +21 $이 한 수중 $\displaystyle a _ {j} +21 $과 같아야 한다. 따라서 $\displaystyle a _ {j} -a _ {i} =21 $이고 $\displaystyle \left ( i+1 \right ) $째날부터 $\displaystyle j $째날까지 연습한 회수는 꼭 $\displaystyle 21 $회이다.

 

 

 

7. 집합 $\displaystyle A= \left\{ 1,~2,~3,~ \cdots ,~2n \right\} $이라 하자. $\displaystyle A $에서 임의로 $\displaystyle n+1 $개의 원소를 뽑으면 그 중에는 서로소인 두 수가 있음을 보여라.

 

 

https://youtu.be/zxZF21kXKTo (구독과 좋아요)

 

(풀이1) 먼저 연속한 두 자연수(예를 들면 $\displaystyle 5,~6 $)은 서로소임을 알자. 즉 공약수가 $\displaystyle 1 $밖에 없다.

그러므로 $\displaystyle 1 $부터 $\displaystyle 2n $까지의 정수 중에서 $\displaystyle n+1 $개를 뽑을 때 그 속에 연속한 두 자연수가 있음을 보이면 충분하다.

비둘기집의 원리를 이용하기 위해 다음과 같은 집합을 생각하자.

$\displaystyle \left\{ 1,~2 \right\} $, $\displaystyle \left\{ 3,~4 \right\} $, $\displaystyle \cdots $, $\displaystyle \left\{ 2n-1,~2n \right\} $

이 집합을 비둘기집이라 생각하고, 집합 $\displaystyle A= \left\{ 1,~2,~3,~ \cdots ,~2n \right\} $의 원소를 비둘기라 생각하여 $\displaystyle n+1 $개의 비둘기를 뽑으면 위의 원소가 두 개인 집합 $\displaystyle n $개 중 어느 하나는 반드시 뽑힌다. 따라서 이 집합의 원소는 서로소이므로 이 두수가 문제의 조건을 만족하는 두 수이다.

 

 

 

** $\displaystyle 200 $이하의 자연수 중에서 $\displaystyle 101 $개를 택하면 그 중 하나는 다른 하나의 약수가 됨을 증명하여라.

 

 

집합 $\displaystyle \left\{ 1,2, \cdots ,200 \right\} $에 속하는 각각의 홀수 $\displaystyle 2m-1 $에 대하여 다음과 같은 집합을 생각하자.

$\displaystyle S _ {m} = \left\{ \left ( 2m-1 \right ) 2 ^ {0} ,~ \left ( 2m-1 \right ) 2 ^ {1} ,~ \left ( 2m-1 \right ) 2 ^ {2} ,~ \cdots ,~ \left ( 2m-1 \right ) 2 ^ {k} ,~ \cdots \right\} $

즉 이 집합은 홀수 $\displaystyle \left ( 2m-1 \right ) $에 $\displaystyle 2 ^ {k} $ ($\displaystyle k=0,1,2, \cdots $)을 곱한 값을 원소로 갖는 집합이다. 이 집합의 어느 두 원소도 서로 약수와 배수의 관계이다.

이제 비둘기 집은 $\displaystyle S _ {1} ,S _ {2} ,S _ {3} , \cdots ,S _ {10} $이다. $\displaystyle 1,~2,~ \cdots ,~200 $이 비둘기이다. 이 $\displaystyle 200 $개 중 $\displaystyle 101 $개를 택하면 비둘기집의 원리에 의해 $\displaystyle S _ {i} $ ($\displaystyle i=1,2, \cdots ,10 $)에 속하는 두 수가 존재한다. 따라서 이 두 수는 서로 약수배수의 관계이다.

따라서 증명되었다.

예를 들어 $\displaystyle n=4 $일 때, 비둘기집을 한번 구해보면

$\displaystyle S _ {1} = \left\{ 1 \times 2 ^ {0} ,1 \times 2 ^ {1} ,1 \times 2 ^ {2} ,1 \times 2 ^ {3} \right\} $

$\displaystyle S _ {2} = \left\{ 3 \times 2 ^ {0} ,3 \times 2 ^ {1} \right\} $

$\displaystyle S _ {3} = \left\{ 5 \times 2 ^ {0} \right\} $

$\displaystyle S _ {4} = \left\{ 5 \times 2 ^ {0} \right\} $

 

 

 

8. 어떤 바둑전문기사는 하루 한 번 이상 바둑을 두는데 $\displaystyle 20 $일 동안 둔 바둑횟수는 $\displaystyle 30 $회를 넘지는 않는다. 그러면 연속으로 며칠 동안 둔 바둑 횟수의 합이 $\displaystyle 7 $인 기간은 적어도 $\displaystyle 3 $번 있음을 보여라.

 

 

https://youtu.be/xqwAD241l-I (구독과 좋아요)

 

이기사가 첫날 둔 바둑의 횟수를 $\displaystyle a _ {1} $, 둘째날까지 둔 바둑횟수를 $\displaystyle a _ {2} $, $\displaystyle \cdots $, $\displaystyle 20 $일동안 둔 바둑횟수를 $\displaystyle a _ {20} $이라 하자. 그러면 매일 바둑을 두었고 $\displaystyle 30 $회를 넘기지 않았으므로

$\displaystyle 1 \leq a _ {1} <a _ {2} < \cdots <a _ {19} <a _ {20} \leq 30 $

이다. 또, 위의 식에 모두 $\displaystyle 7 $을 더하면

$\displaystyle 8=1+7 \leq a _ {1} +7<a _ {2} +7< \cdots <a _ {19} +7<a _ {20} +7 \leq 30+7=37 $

이다. 그러므로 이 $\displaystyle 40 $개의 수

$\displaystyle a _ {1} ,~a _ {2} ,~ \cdots ,~a _ {20} ,~a _ {1} +7,~a _ {2} +7,~ \cdots ,~a _ {19} +7,~a _ {20} +7 $ $\displaystyle \cdots \cdots $(i)

은 모두 $\displaystyle 1 $부터 $\displaystyle 37 $까지이 자연수이므로 비둘기집의 원리에 의해

$\displaystyle a _ {j} =a _ {i} +7 $ ($\displaystyle 1 \leq i \leq j \leq 20 $)

인 서로 다른 $\displaystyle a _ {i} ,~a _ {j} $가 존재한다. 즉 $\displaystyle a _ {j} -a _ {i} =7 $이므로 $\displaystyle a _ {i+1} ,~ \cdots ,~a _ {j} $ 동안 바둑둔 횟수는 $\displaystyle 7 $이다. 또, (i)에서 $\displaystyle a _ {j} $와 $\displaystyle a _ {i} +7 $을 제외한 나머지는 많아야 $\displaystyle 36 $개의 자연수이므로 다시 같아지는 두 쌍의 수가 더 있다. 그러므로 연속으로 며칠동안 둔 바둑 횟수의 합이 $\displaystyle 7 $인 기간이 적어도 $\displaystyle 3 $번 있다.

 

 

 

9. 아래의 행렬 $\displaystyle A $는 서로 다른 $\displaystyle mn $개의 실수로 이루어져 있으며 각 행은 오른쪽으로 갈수록 점점 커진다.

$ A= \left( \begin{matrix} a _ {11} & a _ {12} & \cdots & a _ {1n}\\ a _ {21} & a _ {22} & \cdots & a _ {2n}\\ \vdots & \vdots & \vdots & \vdots \\ a _ {m1} & a _ {m2} & \cdots & a _ {mn}   \end{matrix} \right)$

이 행렬의 각 열을 밑으로 갈수록 커지게 재배열하면 행동 오른쪽으로 갈수록 점점 커짐을 보여라.

 

 

https://youtu.be/cT2x58XXh-c (구독과 좋아요)

 

 

10. 자연수로 이루어진 수열 $\displaystyle a _ {1} ,~a _ {2} ,~ \cdots $이 다음 두가지 성질을 갖는다.

(1) $\displaystyle a _ {n} <a _ {n+1} $

(2) $\displaystyle a _ {n+1} \leq 2n $

이때, 임의의 자연수 $\displaystyle k $에 대하여 어떤 두 항의 차가 $\displaystyle k $가 될 수 있음을 보여라.

 

 

https://youtu.be/blLAd6xaR1Y(구독과 좋아요)