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(구독과 좋아요)

 

과고1학년, 2학년 대신대비를 위해 더플러스수학학원의 구술시스템에서 실제로 하고 있는 문제를 보시려거나 과학고 3학년 AP미적분학을 준비하고자 하거나 대학교1학년 미적분학에 대해 공부하려고 하면 더플러스수학 프리미엄콘텐츠 를 이용해 보세요.

https://naver.me/FsR64KUy

과학고전문더플러스수학 : 네이버 프리미엄콘텐츠