과학

재밌는 수학 증명: 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처럼 얼핏보면 당연한 사실을 이용해서 이렇게 활용하는 수학자들은 참 변태스러우면서도 대단하다고 느꼇어

 

 

 

 

 

 

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

 

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

 

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

 

 

 

 

 

 

 

 

 

 

 

 

41개의 댓글

2019.11.17

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

0
2019.11.17
@그게

수정했엉 미안 ㅋㅋ

0

비둘기집 원리임

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

0
2019.11.17
@햄치즈휠렛버거세트

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

0
@혼자잘노는애

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

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

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

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

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

...

0
2019.11.17
@햄치즈휠렛버거세트

아조시...

0
2019.11.17
@번한강행

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

0
@보라뚱이

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

0
2019.11.17
@햄치즈휠렛버거세트

아항...

0
2019.11.17

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

0
2019.11.17
@Awrfs757fswr

여기 맛집이네

0
2019.11.17

Discrete에서 머배움

0
2019.11.17
@그게

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

0
@그게

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

0

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

그땐 ㅈㄴ힘들엇엇는디

0
2019.11.17
@宮本フレデリカ

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

0
@혼자잘노는애

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

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

0
2019.11.17
@宮本フレデリカ

ㅇㅎ 고렇구만

0
2019.11.17

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

0
2019.11.17

비둘기집의원리네

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

0
2019.11.17
@gogogog

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

0
2019.11.17

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

0
2019.11.17
@오리도리탕

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

0
2019.11.17
@혼자잘노는애

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

0
2019.11.17
@쿨라임피지오

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

0
2019.11.17

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

0
AZ
2019.11.17

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

0
2019.11.17

"완벽하게 이해했다"

1
2019.11.17
1

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

 

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

 

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

 

0
2019.11.18
@여자친구생기면탈퇴할거다

앗 수정했쓰 ㅎㅎ

0

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

0
2019.11.18

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

0
2019.11.18
@맥구라거

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

0
2019.11.18

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

0
2019.11.18
@크파페퍼

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

0

"야 10개의 구멍"

0
@웃음이헤픈사람

"넣을게"

1
2019.11.18
@난죽음을택하겠다
0
2019.11.20

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

0
2019.11.21

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

재밌네

0
무분별한 사용은 차단될 수 있습니다.
번호 제목 글쓴이 추천 수 날짜
12374 [기타 지식] 카우치 사건은 정말 인디 음악을 끝장냈는가? 21 프라이먼 12 17 시간 전
12373 [호러 괴담] [살인자 이야기] 1년마다 1명씩 잠을 자다 사망한 가족. 홀로... 2 그그그그 3 21 시간 전
12372 [역사] 송파장과 가락시장 3 Alcaraz 5 22 시간 전
12371 [호러 괴담] [살인자 이야기] "괴물을 쓰러뜨렸다." 어머니에... 2 그그그그 3 1 일 전
12370 [기타 지식] 알코올 중독에 빠질 수 있는 칵테일, 브랜디 알렉산더편 - 바... 1 지나가는김개붕 4 1 일 전
12369 [기타 지식] 세계에서 제일 잘 팔리는 칵테일 중 하나, 위스키 사워편 - ... 2 지나가는김개붕 3 2 일 전
12368 [기타 지식] 왜 나는 독일을 포기하고 캐나다로 왔는가 26 상온초전도체 10 2 일 전
12367 [역사] 미국인의 시적인 중지 2 K1A1 12 2 일 전
12366 [기타 지식] 독한 칵테일의 대표, 파우스트편 - 바텐더 개붕이의 술 이야기 5 지나가는김개붕 2 2 일 전
12365 [호러 괴담] [살인자 이야기] 아무도 듣지 못한 죽음의 비명이 들린 357호실 1 그그그그 6 4 일 전
12364 [기타 지식] 칵테일에도 아메리카노가 있다. 편 - 바텐더 개붕이의 술 이야기 6 지나가는김개붕 6 5 일 전
12363 [역사] 역사학자: 드래곤볼은 일본 제국주의사관 만화 16 세기노비추적꾼 13 6 일 전
12362 [과학] 번역)새들은 왜 알을 많이 낳는가? - 후투티의 형제살해 습성... 5 리보솜 3 6 일 전
12361 [호러 괴담] [살인자 이야기] 20년만에 해결된 미제사건 4 그그그그 9 9 일 전
12360 [호러 괴담] [미스테리] 고립된 남극 기지에서 사망한 남성. 근데 무언가 ... 14 그그그그 12 11 일 전
12359 [호러 괴담] [살인자 이야기] 문자를 차단했다고 살인까지? 3 그그그그 5 13 일 전
12358 [기타 지식] 미국은 왜 틱톡을 분쇄하려 하는가? 14 K1A1 29 13 일 전
12357 [기타 지식] 아마도, 미국에서 가장 사랑 받는 칵테일 마르가리타편 - 바... 7 지나가는김개붕 9 14 일 전
12356 [역사] 애니메이션 지도로 보는 고려거란전쟁 6 FishAndMaps 6 16 일 전
12355 [기묘한 이야기] 일본 멘헤라 아이템에 대해서 알아보자 25 Overwatch 17 16 일 전