🦜 Pigeonhole Principle

intro

🦜 총 19개의 구멍이 있는 비둘기집에서 20마리의 비둘기가 들어가려고 할 때, 적어도 한 곳의 비둘기집에는 적어도 2마리 이상의 비둘기가 반드시 있을 수 밖에 없다는 원리. 

① theorem I: 각 구멍에 A마리의 비둘기가 평균적으로 들어가 있다면, A가 정수가 아니라면, 적어도 한 곳에는 ceil(A)마리의 비둘기가 있다는 뜻. 나머지 비둘기 집에는 최대 floor(A)마리의 비둘기가 있다.

② theorem II: n+1개의 물건을 n개의 상자에 넣으려고 할 때, 적어도 한 개 이상의 상자에는 2개 이상의 물건을 넣을 수 밖에 없다.

 

🦜  generalization

①) 만약 Kn+1마리의 비둘기가 n개의 비둘기집에 들어가려고 할 때, (Kn+1)/n은 K + 1/n이므로 적어도 한 곳의 비둘기집에는 K+1마리 이상의 비둘기가 존재한다.

 

②) strong form - theorem III: q1, q2, ... qn을 자연수라 하자. q1 + q2 + ... + qn - n +1개의 물체를 n개의 상자에 넣는다고 가정하자. 그러면 첫번째 상자가 최소 q1개를 갖거나, 두번째 상자가 q2개를 갖거나, 세번째 상자가 q3개를 갖거나 ~ n번째 상자가 qn개를 갖게 된다. 생각해보면 자명한 원리. q1 상자는 q1개 이상이 있어야 조건을 충족하므로, 조건을 충족하지 않으면서 최대로 넣을 수 있는 물체의 개수는 q1 - 1 / q2는 q2 -1 ~~ / qn은 qn - 1이므로, 다 더하면 q1 + q2 + ... + qn - n이 된다. 이 때 1만 더 추가하면 최소의 물체 개수로 위 상자 조건 중 적어도 한 곳 이상은 조건을 만족한다!

application & questions

Questions로 n과 K+1을 이용해 역으로 Kn+1을 구하는 문제가 많이 등장.

 

Q1. how many students must be in a class to guarantee that at least 2 student receive the same score on final exam, if the exam is graded on a scale from 0 to 100 points?

A1: n을 100 / K+1을 2라고 한다면 Kn+1은 100*1 + 1로 101. 즉 최소 101명이 있어야 똑같은 점수를 받는 학생이 존재한다.

 

Q2. A bag contains 10 red marbles, 10 white marbles, and 10 blue marbles. What is the minimum no. of marbles you have to choose randomly from the bag to ensure that we get 4 marbles of same color?

A2: 색깔의 개수 n = 3 / 한 곳에 최소 4개 구슬이 들어가야 하므로 K + 1 = 4 → 따라서 Kn+1 = 3*3 + 1 = 10. 최소 10번은 골라야 한다.

 

Q3. How many cards must be selected from a standard deck of 52 cards to guarantee that at least 3 cards of same suit chosen?

A3: 카드 종류의 개수 n = 4(heart, spade, diamonds, clubs - 각각 13개씩 존재) / 한 곳에 최소 3개의 카드가 들어가야 하므로 K + 1 = 3 → 따라서 Kn+1=2*4+1=9로 최소 9개의 카드는 골라야 한다.

 

Q4. How many cards must be selected from a standard deck of 52 cards to guarantee that at least 3 hearts are selected?

A4: 특정 비둘기집에서 최소 3개의 카드를 고르기 위한 문제. 즉 한 곳만 최소 3개의 카드가 들어가야 하고 나머지는 상관 x / 이 때 나머지 비둘기집에 다 들어가는 경우의 수 13 + 13 + 13 이후, 카드 종류의 개수 n = 1 / 해당 비둘기집에 최소 3개의 카드 들어가야 하므로 K + 1 = 3 따라서 Kn+1=2*1+1로 3. 즉 39 + 3으로 최소 42개의 카드는 골라야 한다. 특정 비둘기집이 아닌 다른 집이 모두 끝까지 골라지고 난 다음, 특정 비둘기집에 대해서만 비둘기집의 원리 공식 적용.

 

Q5. In a computer science department, a student club can be formed with either 10 members from first year or 8 members from second year or 6 from third year or 4 from final year. What is the minimum no. of students we have to choose randomly from department to ensure that a student club is formed?

A5: 각 비둘기집별 들어가는 최소 비둘기의 개수가 다르다. 10 / 8 / 6 / 4의 조건을 최소 한 곳의 비둘기집만 맞추면 되므로, 위 공식에 의해 10 + 8 + 6 + 4 - 4(n) + 1로 25명이 정답.

 

Q6. A box contains 6 red, 8 green, 10 blue, 12 yellow and 15 white balls. What is the minimum no. of balls we have to choose randomly from the box to ensure that we get 9 balls of same color?

A6: 일단 red와 green은 9개 미만이므로 적용 불가능하기에 먼저 다 고르고(6+8), 이후 3개의 ball에서 비둘기집의 원리를 부분적으로 적용하면 된다. n = 3 / K + 1 = 9이므로 Kn+1=25. 따라서 25+14인 39개의 공 고르면 끝!

 

Q7. (BOJ 20529 가장 가까운 세 사람의 심리적 거리) 

Solution7: MBTI 유형은 16개 pigeonhole number. 같은 MBTI가 3개 이상 있게끔 하려면 n = 16 / K+1=3이므로 nK+1=33. 즉 최소 33개 이상 있다면 세 개의 같은 MBTI 등장. 즉 개수가 33개 이상이라면 세 사람의 심리적 최소 거리는 무조건 0 활용으로 코드 실행시간 단축

---

geeksforgeeks

thumbnail