최근 편집
최근 토론
게시판 메인
도구
투표
무작위 문서
스킨 설정
파일 올리기
기타 도구
216.73.216.27
IP
사용자 도구
사용자 설정
로그인
회원 가입
최근 편집
최근 토론
돌아가기
삭제
이동
파일 올리기
비둘기집 원리
(편집)
(불러오기)
(편집 필터 규칙)
[[분류:가져온 문서/오메가]] Pigeonhole Principle, PHP 비둘기 [math(kn+1)]마리와 비둘기집 [math(n)]개가 있으면 적어도 한 집에는 비둘기가 [math(k+1)]마리 이상 들어가 있다는 원리이다. == 증명 == 직관적으로도 자명하고, 간단히 귀류법을 이용해 증명할 수 있다. == 예시 == === 문제 === 한 변의 길이가 3인 정사각형 내부에 10개의 점이 선택되었다. 이들 중 두 점 사이의 거리가 [math(\sqrt2)] 이하인 두 점이 존재함을 보여라. === 증명 === 자명하다.[* 농담입니다.] 먼저 변의 길이가 3인 정사각형을 변의 길이가 1인 정사각형 9개로 나누어보자. 여기서 점을 비둘기, 정사각형을 상자라 하면 어느 한 정사각형엔 두 개 이상의 점이 들어가고, 그 두 점 사이의 거리는 많아봐야 [math(\sqrt2)]인 것이다. ■ == 일반화 == 일반화된 비둘기집 원리(Generalized Pigeonhole Principle) >[math(1\leq i \leq n)]일 때, [math(n, k_i\in \mathbb{N})]에 대해 만약 [math(\displaystyle\sum_{i=1}^n k_i -n+1)]개 이상의 비둘기를 [math(n)]개의 비둘기 집에 넣었다면, 어떤 [math(i)]가 존재하여 [math(i)]번째 집에 [math(k_i)]마리 이상의 비둘기가 있다. == 영상 == [youtube(RiknxHRe24w)] [Include(틀:가져옴2,O=오메가, C=[[https://creativecommons.org/licenses/by-nc-sa/3.0/deed.ko|CC BY-NC-SA 3.0]])]
(임시 저장)
(임시 저장 불러오기)
기본값
모나코 에디터
normal
namumark
namumark_beta
macromark
markdown
custom
raw
(↪️)
(💎)
(🛠️)
(추가)
[[분류:가져온 문서/오메가]] Pigeonhole Principle, PHP 비둘기 [math(kn+1)]마리와 비둘기집 [math(n)]개가 있으면 적어도 한 집에는 비둘기가 [math(k+1)]마리 이상 들어가 있다는 원리이다. == 증명 == 직관적으로도 자명하고, 간단히 귀류법을 이용해 증명할 수 있다. == 예시 == === 문제 === 한 변의 길이가 3인 정사각형 내부에 10개의 점이 선택되었다. 이들 중 두 점 사이의 거리가 [math(\sqrt2)] 이하인 두 점이 존재함을 보여라. === 증명 === 자명하다.[* 농담입니다.] 먼저 변의 길이가 3인 정사각형을 변의 길이가 1인 정사각형 9개로 나누어보자. 여기서 점을 비둘기, 정사각형을 상자라 하면 어느 한 정사각형엔 두 개 이상의 점이 들어가고, 그 두 점 사이의 거리는 많아봐야 [math(\sqrt2)]인 것이다. ■ == 일반화 == 일반화된 비둘기집 원리(Generalized Pigeonhole Principle) >[math(1\leq i \leq n)]일 때, [math(n, k_i\in \mathbb{N})]에 대해 만약 [math(\displaystyle\sum_{i=1}^n k_i -n+1)]개 이상의 비둘기를 [math(n)]개의 비둘기 집에 넣었다면, 어떤 [math(i)]가 존재하여 [math(i)]번째 집에 [math(k_i)]마리 이상의 비둘기가 있다. == 영상 == [youtube(RiknxHRe24w)] [Include(틀:가져옴2,O=오메가, C=[[https://creativecommons.org/licenses/by-nc-sa/3.0/deed.ko|CC BY-NC-SA 3.0]])]
비로그인 상태입니다. 편집한 내용을 저장하면 지금 접속한 IP가 기록됩니다.
편집을 전송하면 당신은 이 문서의 기여자로서 본인이 작성한 내용이
CC BY 4.0
에 따라 배포되고, 기여한 문서의 하이퍼링크나 URL로 저작자 표시가 충분하다는 것에 동의하는 것입니다.
전송
미리보기
