과학

재밌는 수학 증명: Pigeonhole Principle

안녕 얘들아 

 

나는 지금 대학교에서 Discrete Mathmatics 라는 수업을 듣고있는데 재밌는 수학증명 하나 배워서 한번 써보려고 해 ㅎㅎ

 

Pigeonhole Principle 이란?

 

11마리의 피죤과 10개의 구멍이 있다고 치자. 구멍의 개수가 피죤의 개수보다 더 적기때문에 무조껀 하나의 구멍에는 피존이 두마리 이상이 존재한다 라는 이론이야!

 

언뜻보면 너무도 당연한 이론이 어떻게 수학적 증명으로 사용되는지 한번 봐보자!

 

S = {a1,a2,a3,a4,a5} a1...a5는 모두 다른수라고 했을때 a1...a5에 어떠한 숫자를 넣던 2개를 골라서 둘의 차이를 4로 나눌수있다!

 

다른말로하면 5개의 숫자가 어떤것이든 이 다섯숫자중에 2개를 골라 조합을 만든다고할때, 두개 고른숫자의 차이를 4로 나눌수있는 조합이 무조건 있다는거야 ㅎㅎ

 

 

 

 

이러한 가정을 어떻게 증명할까?

 

정답은 위해 말한 pigeonhole principle로 증명을 할수가 있어

 

S에 있는 a들을 4로 나누어서 나온 나머지들의 집합을 S*라고 하자 S = {1,2,3,4,5} 였다면 S = {1,2,3,0,1} 이 되는거지

 

어떠한 수를 4로 나누면 나올수있는 나머지의 경우의 수는 무었일까? 0,1,2,3      4개가 나올수있지!

 

그렇다면 S* = { a1*,a2* ,,, a5*} 가 나올텐데, 어라? 총 5개네?

 

그러면 이중하나는 똑같은 숫자일수밖에 없는거지 ㅎㅎ

 

그래서 만약 a1*과 a5*의 나머지가 같다고하면

 

a1-a5의 값은? 4로 나누었을때 나머지가 같았기때문에 a1-a5는 무조껀 4로 나눌수있어!!!

 

 

 

 

 

이번껀 꼭 수학적 증명이 아니어도 직관적으로 맞아보이긴 했을수도 있어.

 

 

하지만 이 명제는 어떨까?

 

 

77개의 바구니가 있다 {a1,a2,a3, ... a77} , 그 바구니에는 무조건 1개씩 공이 들어있고, 바구니에는 총 132개의 공이있다!

 

이 바구니들에 공들을 어떠한 방법으로 배치한다고해도, 무조껀 그 배치된 바구니들중 한 연속된 구간의 공의 개수는 정확히 21개다.

 

좀 이해하기 어렵지?

 

77개의 바구니안에 최소한 공을 한개씩 배치한후, 나머지 공들은 자기 맘대로 배치했을때

 

정확히 어디서부터 어딘지는 알수없지만, n번째부터 n+x번째의 연속된 바구니들의 공개수를 다 더하면 무조껀 21개가 나오는 구간이 있다는거야!

 

이건 좀 어렵지???

 

 

 

 

 

 

 

 

 

하지만 이것도 pigeonhole principle로 증명할수있어

 

공의 개수를 {a1,a2,  ... , a77} 이라고 할때

 

Ai를 i번째 까지 있는 공의 개수라고 하자

 

A1는 a1안에 있는 공의 개수겠지 그럼?

 

그렇다면 최소한 바구니 안에는 공이 하나씩 들어가있고 총 132개가 있으니

 

1 <= A1 < A2 < .... < A77 = 132 가 성립해!

 

그렇다면 여기에 21씩만 더해줘보자 그렇다면

 

22 <= A1 + 21 < A2 + 21 < ... < A77 + 21 = 153  이 되지!

 

이제 이걸 하나의 집합으로 묶어볼께, 특별한게 아니라 그냥 위에 있는 숫자들을 나열하는거 뿐이야!

 

{A1, A2, ... , A77(여기까지가 첫번째 식 숫자들), A1+21, A2+21, A3+21, ... A77+21}

 

이 숫자들을 이렇게 나열한다고했을때, A1이 가질수있었던 가장 작은 숫자는 뭐였지? 첫번째 바구니니깐 1!

그렇다면 A77+21의 숫자는? 공이 총 132개니깐 153이지

 

그렇다면 이 숫자들은 지금 1 ~ 153 사이의 숫자들로 이루어져있다는건데..

 

그런데 이 숫자들은 지금 몇개가 있을까? 77개의 숫자들을 두개로 이어붙힌거니깐... 총 154개가있어!!!

 

그렇다는것은? Pigeonhole Principle에 의해서 이 숫자들중 하나는 무조껀 같다는거지 ㅎㅎ

 

 

결과적으로

만약 An = Ax+21이라고 치면, x번째바구니부터 n번째 바구니까지의 연속된 바구니들의 공의 개수는 합이 21이 라는거야 ㅎㅎ

 

이렇게 Pigeonhole Principle처럼 얼핏보면 당연한 사실을 이용해서 이렇게 활용하는 수학자들은 참 변태스러우면서도 대단하다고 느꼇어

 

 

 

 

 

 

최대한 쉽게 써보려했는데 재밌게 이해가됬으면 좋겠어!!

 

참고로 나는 컴퓨터 공학전공이고 수학전공인사람들한테는 까불어서 미안 ㅜ

 

이해가 안되는게 있으면 언제든지 물어봐!

 

 

 

 

 

 

 

 

 

 

 

 

42개의 댓글

28 일 전

구멍의 개수가 피죤의 개수보다 더 많기때문에 무조껀 하나의 구멍에는 피존이 두마리 이상이 존재한다 라는 이론이야!

0
28 일 전
@그게

수정했엉 미안 ㅋㅋ

0

비둘기집 원리임

수학 10-가 집합론에 나오는 내용이었기도 하고.

0
28 일 전
@햄치즈휠렛버거세트

ㅜㅜ 난 그저께 처음배움... 10-가 가 뭐임??

0
@혼자잘노는애

요새는 교과과정 저렇게 안부르나..?

고1 공통수학 1학기 분량을 10-가 2학기는 10-나

2학년은 11이 아니라 문이과 나눠져서

문과는 수1만(혹은 +미적분과 통계기본)

이과는 수리1, 2 +선택과목(미적/기하벡터/확통)

...

0
27 일 전
@햄치즈휠렛버거세트

아조시...

0
27 일 전
@번한강행

시발 저게 아조시 과정이야? 시무룩..

0
@보라뚱이

아조시 이후로 두 번 이상 바뀌었어요...

0
27 일 전
@햄치즈휠렛버거세트

아항...

0
28 일 전

하지만 힐베르트가 비둘기집을 차린다면?

0
28 일 전
@Awrfs757fswr

여기 맛집이네

0
28 일 전

Discrete에서 머배움

0
27 일 전
@그게

Induction, Graph, Big O, Trees, 이런거??

0
@그게

이산수학은 유한 개수를 헤아리는 과목이라고 얼핏 들음. 그래프같은거 하더라

0

중딩때 크모준비하면서 배운거 새록새록생각나네

그땐 ㅈㄴ힘들엇엇는디

0
27 일 전
@宮本フレデリカ

헐 이걸 중학교때 준비함?? ㄷㄷ

0
@혼자잘노는애

과고준비생이엇어서 올림피아드공부햇엇는데

비둘기집원리는 필수였지 ㅇㅇ

0
27 일 전
@宮本フレデリカ

ㅇㅎ 고렇구만

0
27 일 전

비슷한 유형(?)의 부동점 정리를 더 좋아하는데... ㅋ

0
27 일 전

비둘기집의원리네

이거첨볼때 너무나 자명한 사실인데 이걸또 증명하고있는 수학의 꼼꼼함에 학을 뗄수밖에없더라

0
27 일 전
@gogogog

마자... 참 이런거 보면 수학이 매력있긴한거같어 ㅋㅋ

0
27 일 전

흥미롭네 ㅋㅋㅋ 한국에서 학교 다니면 증명은 모르지만 비둘기집 원리는 보통 아는데 글쓴이 혹시 외국에서 다닌거?

0
27 일 전
@오리도리탕

ㅇㅇ ㅋㅋ 고등학교때 이런걸 배움? 신기하네

0
27 일 전
@혼자잘노는애

비둘기집의 원리를 안배웠다고? 교육과정 많이 바뀌었나보네

0
27 일 전
@쿨라임피지오

외국에서 고등학교 나옴 ㅋㅋ

0
27 일 전

생일 패러독스로 배웟었는데 ㅋㅋ 이 증명을 토대로 난수해킹 진행함 와이파이 비밀번호같은거 물론 이전버전 암호화

0
AZ
27 일 전

모든 해시함수는 필연적으로 충돌값을 갖는다 이말이야

0
27 일 전

"완벽하게 이해했다"

1
27 일 전
1

잘 봤어 비둘기집 원리 응용 저런게 있었구나 흥미롭네 그런데 보다보니

 

{A1, A2, ... , A77(여기까지가 첫번째 식 숫자들), A1+21, A2+22, A+23, ... A77+21}

 

여기서 A2+22, A+23 부분이 A2+21, A3+21 가 되어야 할 것 같네!

 

0
27 일 전
@여자친구생기면탈퇴할거다

앗 수정했쓰 ㅎㅎ

0
27 일 전
0

단방향 해시함수의 취약점 흑흑

0
27 일 전

이걸 컴퓨터에 응용하는거?

0
27 일 전
@맥구라거

컴퓨터 로직짤때 쓴데 교수가!! 아마 알고리즘 배울때 써먹을꺼야 ㅋㅋ

0
27 일 전

와 피존홀 프린씨쁠 졸업논문할때 메인 스트림으로 썼던 이론인데 ㅋㅋㅋㅋ 오랫만에 보니까 엄청반갑네 수학과 졸업자임 ㅋ

0
27 일 전
@크파페퍼

ㅋㅋㅋ 수학 엄청 좋아하진 않았는데 이건 너무 잼뜨라

0

"야 10개의 구멍"

0
@웃음이헤픈사람

"넣을게"

1
26 일 전
@난죽음을택하겠다
0
25 일 전

인구절반이 여자인데 제 짝은 왜 없는거죠?

0
24 일 전

직관을 수학으로 풀어내는게 수학인건가

재밌네

0
번호 제목 글쓴이 추천 수 날짜
공지 [게임] 게임 연재, 게임 정보는 게임 연재 판을 이용 해주시기 바랍니다 91 overflow 5 2017.04.18
공지 [기타 지식] 후기, 리뷰, 감상문은 허용 하지 않습니다 overflow 2 2016.07.29
공지 [기타 지식] 글 작성 금지 항목들 overflow 2 2014.04.06
공지 [기타 지식] 연속적인 글과 제목에 대하여 28 overflow 2 2013.08.11
공지 [기타 지식] 읽을 거리 판 입니다. 44 애드립 2 2012.07.25
9712 [과학] 고무동력기를 세계는 어떻게 바라보고 있는가? 10 만덕후 8 7 시간 전
9711 [기묘한 이야기] 야마시타의 황금 7 그그그그 5 15 시간 전
9710 [호러 괴담] [Reddit] 소개팅앱 괴담 (유툽주의) 24 년차ASMR 3 1 일 전
9709 [역사] [독일 근현대 산책] 6. 낭만 속에 숨겨진 불편함, 「비더마이... 3 Volksgemeinschaft 3 1 일 전
9708 [기타 지식] 길거리에서 종종보이는 신앙촌상회 가게에 대해 아는사람? 11 켈로그 2 1 일 전
9707 [역사] [독일 근현대 산책] 5. 낭만 속에 숨겨진 불편함, 「비더마이... 2 Volksgemeinschaft 2 1 일 전
9706 [기묘한 이야기] 소원을 이룬 남자 6 줴렐레 7 2 일 전
9705 [기타 지식] [확률문제] 당신이 눈앞에서 버스를 놓쳤을 때, 다음 버스가 ... 25 줴렐레 1 2 일 전
9704 [기타 지식] [확률문제] 당신이 하루 내내 걷다가 동전을 k개 주울 확률을... 5 줴렐레 1 2 일 전
9703 [기타 지식] [잡지식] 파생연계증권(DLS, ELS)은 무엇일까? - [DLF사태! ... 8 뿌앙뿌뿌 7 2 일 전
9702 [역사] [독일 근현대 산책] 4. 낭만 속에 숨겨진 불편함, 「비더마이... 6 Volksgemeinschaft 6 2 일 전
9701 [호러 괴담] 성실하고 가정에 충실한 남성, 그의 가면 뒤 감춰진 진짜 모습 6 그그그그 5 2 일 전
9700 [기타 지식] [잡지식] Pair Trading - 단순한 규칙으로 돈을 벌어보자. 11 뿌앙뿌뿌 12 3 일 전
9699 [기타 지식] [재테크] 아무도 믿지않는 매매방법 이야기 70 작은투자자 10 3 일 전
9698 [기타 지식] 나라별 살인마 비율 통계 26 그그그그 18 3 일 전
9697 [유머] 아이유팀이 10년이나 유지될수 있는 이유 49 LOLOLOLOL 14 3 일 전
9696 [기타 지식] [주식] 왜 떨어졌는가에 주목하라 23 머리카락단한올 3 4 일 전
9695 [역사] [독일 근현대 산책] 3. 「나폴레옹 시대」의 종언 12 Volksgemeinschaft 5 4 일 전
9694 [유머] 은화 서른 닢과 삶 24 한그르데아이사쯔 5 4 일 전
9693 [기타 지식] 개드립 하는 군인이 있을까 싶어 나도 써보는 혹한기 꿀팁 61 리을받침 7 4 일 전
서버에 요청 중입니다. 잠시만 기다려 주십시오...