'비둘기집의원리' 태그의 글 목록

해시를 하기 전에, 비둘기집의 원리를 간단하게 짚고 넘어가겠습니다. 집이 k개가 있고 비둘기가 k+1마리가 있습니다. 그리고 비둘기들은 상자들 중 하나에 들어갔을 때, 이들이 2마리 이상 들어가는 집이 최소한 하나 존재합니다. 집 k개를 그려보았습니다. 그리고 밑에는 비둘기 k+1마리가 있어요. 그러면, 결론을 부정해 봅시다. '2마리 이상 들어가는 집이 최소한 하나 존재한다'는 명제의 부정은, 2마리 이상 들어가는 집이 존재하지 않는다입니다. 그러면 k+1마리가 있고, 집이 k개 있을 때, 많아봤자 1마리가 들어간다가 참이라고 해 봅시다. 즉 ~p가 참이다라고 한 겁니다. 그러면 각 상자에는 최대 1마리씩만 들어갈 수 있으니까, k개의 상자에는 최대 k마리가 들어갈 수 있습니다. 그러면 나머지 1마리는..