Discrete Mathematics

Prof : Sang-Gu LEE  (http://matrix.skku.ac.kr/sglee/ )

SKKU Math Lectures and Labs

Chapter 6  Counting Methods and the Pigeonhole Principle

Lecture Note     http://matrix.skku.ac.kr/2018-DM/Ch-6/

DM-Ch-6-Lab   http://matrix.skku.ac.kr/2018-DM/DM-Ch-6-Lab.html
DM Ch. 6,
동영상강의
6.1 Basic Principles  https://youtu.be/AU_AbwTSI_Y
6.2 Permutations and Combinations  https://youtu.be/yBwkCoX460o
6 Catalan Number (Review)

6.3, 6.7, 6.8, 비둘기집의 원리

http://matrix.skku.ac.kr/2018-DM/DM-Labs.htm  Discrete Math Labs (실습실)

http://matrix.skku.ac.kr/2018-DM-PBL/      (PBL report 보고서)
http://matrix.skku.ac.kr/2018-DM-PBL-Eng/  (PBL report Eng, 영문 보고서)

Problem 1

[Final OK by SGLee]CH.6 page 370 Problem 1 solved by 김승연, 모하메드

Problem

How many eight-bit strings begin with 0 and end with 101?

Solution

Let's consider the final layout for the number as following:

0 □ □ □ □ 1 0 1

Step A) The 1st and the 5th-8th bit already have specific values.so there is no selection involved in these fixed bits.

Step B) The number of remaining bits are 4 bits. Moreover, there are two ways to select each bit (either 0 or 1).

Step C) By the Multiplication Principle, the total number of eight-bit encoding is 2= 16.

2= 16.  ■

Comment

문제는 공간에 중복이 없는 가지 선택지가 있는 문제로 문제를 풀었다면 선택지가 개인 문제뿐만 아니라 간단한 선택 문제는 모두 있다.

Problem 2

[Final OK by SGLee]CH.6 page 370 Problem 2 solved by 김승연, 정호진, 강병훈

Problem

How many ways can we select three books each from a different subject from a set of six distinct history books, nine distinct classics books, seven distinct law books, and four distinct education books?

Solution

1) {history, classics, law}          6×9×7 =378

2) {history, classics, education}  6×9×4 =216

3) {history, law, education}        6×7×4 =168

4) {classics, law, education     9×7×4 =252

378 + 216 + 168 + 252 = 1014

Discussion

We want to select three books from 4 different categories(History,Classics,Law, Education). This means we can have 4 different scenarios considering the fact that order doesn't matter.

Comment

문제는 각각의 카테고리가 선택지를 가지고 있어 카테고리를 먼저 고른 생길 있는 조합을 구하는 문제로 쉽게 있다.

Problem 3

[Final OK by SGLee] CH.6 page 370 Problem 3 solved 오동찬, 신혜수, 김영철, 정호진, 강병훈

Problem

How many functions are there from an n-element set onto {0, 1}?

Solution

1.      f(x)={a1, a2, ,an}  {0,1}

All possible function =2​n​​

2.      Non onto funcion

=2

3.      # of all onto functions

=2​n​​​ - 2​

# of all onto functions = 2n-2

Comment

전사함수의 정의를 알고 그에 맞춰서 푸는 문제로 마지막에 전사함수가 아닌 함수를 빼주는 것을 잊으면 틀리기 쉬운 문제이다.

Problem 4

[Final OK by SGLee]CH.6 page 370 Problem 4 solved 오동찬,  김영철, 엄자균, 강병훈

Problem

A seven-person committee composed of Greg, Hwang, Isaac, Jasmine, Kirk, Lynn, and Manuel is to select a chairperson, vice-chairperson, social events chairperson, secretary, and treasurer. How many ways can the officers be chosen if either Greg is secretary or he is not an officer?

Solution

​There are seven person and five position to be selected.

1.      Greg is a secretary: ××× 3 = 360

2.      Greg is not an officer: 6 × 5 × 4 × 3 ×= 720

Total: 360 + 720 = 1080 ​ ■

Comment

문제는 각각의 상황에 대해서 이름과 직업이 정해져 있어 중복이 불가능 하다. 이를 유념하여 계산하여야 한다. 1번문제가 확장된 유형이라고 있다. 이를 이용한다면 후에 공무원이나 군인의 인사이동이 전산으로 처리될 수도 있을 것이라 생각한다.

Problem 5

[Final OK by SGLee]CH.6 page 371 Problem 5 solved 오동찬, 김영철, 모하메드, 엄자균, 강병훈

Problem

How many 3-combinations are there of six objects?

Solution

C (6 ,3 ) = 6 ! ÷  (3 ! × 3 ! ) = 20

Note

 Definition  2.15 Given a set containing  n (distinct) elements,  (a) An  r-combination of  X is an unordered selection of  r-elements of  X.   (i.e. an r -element subset of X).  (b) The number of  r-combination of a set of  n distinct elements is  C(n, r) .                       C(n, r)  =    n!  /  (n-r)! r!

Comment

콤비네이션 함수의 기본을 알고 있다면 다른 문제를 푸는데 문제가 없을 것이다.

Problem 6

[Final OK by SGLee]CH.6 page 371 Problem 6 solved 신혜수, 전종문, 강병훈

Problem

How many strings can be formed by ordering the letters ABCDEF if A appears before C and E appears before C​ ?

Solution

1. choose 3 boxes. C(6, 3)

The last box is C​​.

2. AE​​C​​​ and E​​A​​​C​​​ , × 2

3. B​, D, F ordering =3!

C(6, 3) * 2! * 3! = 240

Another method)

Comment

In this case, We only have to find B,D,F boxes among 6 boxes,

because then the remaining 3 boxes will be automatically decided, in A-E-C or A-C-E order. Then answer is C(6,3)x2!=240

Comment

문제는 순서대로 배열하는 문제지만 규칙이 주어져서 규칙에 맞게 배열하는 문제이다. 규칙이 없는 문자를 먼저 배열하고 규칙대로 배열하면 쉽게 있다.

Problem 7

[Final OK by SGLee]CH.6 page 371 Problem 7 solved 오동찬, 김영철, 모하메드, 엄자균, 강병훈

Problem

How many six-card hands chosen from an ordinary 52-card deck
contain three cards of one suit and three cards of another suit?

Solution

​​1.    C (13,  3) = 286 (one suit)

2.    C (13,  3) = 286 (another suit)

3.    C (4 , 2) = 6 (2 suits)

4.    286 x 286 x 6 = 490,776.

Comment

52장 카드에 13개의 같은 문양이 있다는 것을 생각해서 콤비네이션 함수를 이용하면 쉽게 풀 수 있는 문제이다.

Problem 8

[Final OK by SGLee]CH.6 page 371 Problem 8  solved 오동찬, 김영철, 모하메드, 엄자균, 강병훈

Problem

A shipment of 100 compact discs contains five defective discs. In how many ways can we select a set of four compact discs that contains more defective than non defective discs?

Solution

1.    defective : 3, not defective : 1  C(5,3) × C(95,1).

2.    defective : 4  C(5,4)

C(5,3) × C(95,1).+ C(5,4) = 955

Comment

직접 답을 구하기 어려운 문제는 독립시행이라면 답을 더하거나 빼서 구할 수 있다.

Problem 9

[Final OK by SGLee]CH.6 page 371 Problem 9 solved 오동찬, 김영철, 신혜수, 김주형, 강병훈

Problem

How many strings can be formed by ordering the letters ILLINOIS?

Solution

ordering the 8 letters,

n !=8 !

I : 3 repetition

L: 2 repetition

8!/(3!×2!)

Answer:    8 ! / (3 ! × 2 !) = 3360. ■​​

Comment

겹치는 문자가 있을 때는 그 문자들을 배열하는 개수만큼 나눠주면 경우의 수를 쉽게 구할 수 있다.

Problem 10

[Final OK by SGLee]CH.6 page 371 Problem 10 solved 오동찬, 김영철, 전종문, 정호진, 강병훈

Problem

How many strings can be formed by ordering the letters ILLINOIS if some I appears before some L?

Solution

1.    8!/32! = 3360

2.     put LLIII order 8!/5! = 336

3.    3360 336  = 3024

Comment

9번 문제에서 규칙이 추가된 문제이고 ​ I L보다 앞에 있는 strings 수를 직접 구하기 힘들기 때문에 전체 strings수에서 모든 L I보다 앞에 있는 strings 수를 빼서 구하는 방법을 생각하는 것이 중요하다.

Problem 11

[Final OK by SGLee]CH.6 page 371 Problem 11 solved 전종문, 김영철, 신혜수, 모하메드, 정호진, 강병훈

Problem

In how many ways can 12 distinct books be divided among four students if each student gets three books?

Solution

1st student: C(12,3)

2nd student: C(9,3)

3rd student:C(6,3)

4th student:C(3,3)

C(12,3) × C(9,3) × C(6,3)× C(3,3)  12!/(3!)4  ■

Comment

선택 형 문제에서는 선택한 후에 선택지가 없어진다는 것을 알아두는 것이 중요하다.

Problem 12

[Final OK by SGLee] CH.6 page 371 Problem 12 solved 신혜수, 전종문, 모하메드, 김주형, 강병훈

Problem

How many integer solutions of

x1 + x2 + x3 + x4 = 17

Satisfy

x1 ​≥ 0, x2 ​≥ 1, x3 ​≥ 2, x4 ​≥ 3

Solution

x2 = x2'+ 1, x3 = x3'+ 2, x4 = x4' + 3

x1 + x2+ x3 + x4 = x1 + (x2'+1) + (x3'+2) + (x4'+3) = 17

x1 + x2' + x3' + x4' = 11

Satisfy

x1 ​≥ 0, x2' ​≥ 0, x3' ​≥ 0, x4' ​≥ 0

﻿ For combination for repetition,

nHr = n+r-1Cr = 11+4-1C4 = 14C4 = 14!/(4!×10!) = (14×13×12×11)/(4×3×2×1)=1001

Comment

이 문제는 단순히 생각하면 어렵겠지만 변수를 변경해주어 11번 문제와 똑같이 만들어서 풀 수 있는 문제이다.

Problem 13

[Final OK by SGLee]CH.6 page 371  Problem 13  solved 전종문, 김희성, 강병훈

​​

Problem

Find the 5-combination that will be generated by Algorithm 4.9 after 12467 if = 7.

Solution

suppose

s1 = 1,  s2 = 2,  s3 = 4,  s4 = 6,  s5 = 7.

At line 13, s3 is the rightmost element not at its maximum value.

Step3:

At line 14, s3 is set to 5.

At lines 16 and 17, s4 is set to 6 and s5 is set to 7.

s1 = 1,  s2 = 2,  s3 = 5,  s4 = 6,  s5 = 7.

Comment

4단원에서 배운 알고리즘을 이용해서 문제를 해결했다.

Note

Pseudo Code :

1. combination(rn{

2. for i 1 to r

3. si i

4. println(s1, . . . sr ) // print the first r-combination

5. for i 2 to C(n{

6. m r

7. max val n

8. while (sm == max val{

9. // find the rightmost element not at its maximum value

10.  1

11. max val max val  1

12}

13. // the rightmost element is incremented

14. sm sm 1

15. // the rest of the elements are the successors of sm

16. for 1 to r

17. s j s j1

18. println(s1, . . . sr ) // print the ith combination

19}

20}

for --> repetitive statement (반복문)

ex) for i to j

i, i+1 ... j-1 , j

println --> print statement (출력문)

while -->repetitive statement (반복문)

ex) while(state)

Repeat until state is true

Comment

I think this code is too hard some non-coder. So i added some help sentence.

Problem 16

[Final OK SGLee]CH.6 page 371  Problem 16 solved 김정주, 모하메드, 이양휘, 강병훈

Problem

Find the permutation that will be generated by Algorithm 4.14 after 6427135.

Solution

Step1:  Algorithm 4.14 generates the permutation that follows 6427135 by supposing tha

t:

s1 = 6, s2 = 4, s3 = 2, s4 = 7, s5 = 1, s6 = 3, s7 = 5

Step2:  At line 6, the largest index m satisfying sm < sm+1 is 6 (s6 = 3)

Step3:  At lines 1013, we find that the largest index k satisfying sk > sm  is 7 (s7 = 5).

Step4:  At line 14, swap sm and sk

s6 = 5 and s7 = 3

Step5:  Swap  6 and 7 : 6427153

Note

*what is lexicographic order?

it is an order that generalizes ordinary dictionary order.

*Algorithm 4.14 Generating Permutations

This algorithm lists all permutations of {1, 2, . . . , n} in an increasing lexicographic

order.

Input: n

Output: All permutations of {1, 2, . . . , n} in increasing lexicographic order

1. permutation(n) {

2. for i = 1 to n

3. si = i

4. println(s1, . . . , sn) // print the first permutation

5. for i = 2 to n! {

6. m = n 1

7. while (sm > sm+1)

8. // find the first decrease working from the right

9. m = m 1

10. k = n

11. while (sm > sk )

12. // find the rightmost element sk with sm < sk

13. k = k 1

14. swap(sm, sk )

15. p = m + 1

16. q = n

17. while ( p < q) {

18. // swap sm+1 and sn, swap sm+2 and sn1, and so on

19. swap(sp, sq )

20. p = p + 1

21. q = q 1

22. }

23. println(s1, . . . , sn) // print the ith permutation

24. }

25. }

Comment:
코드를 모르는 사람들에게는 조금 어려울 수도 있는 문제이지만 어느 정도의 코드는 익히고 있는 것이 앞으로 문제를 해결하기 위해서는 좋을 것이라고 생각한다.

Problem 17

[Final OK by SGLee]CH.6 page 371  Problem 17 solved 정호진, 김희성, 김은율, 김주형, 강병훈

Problem

A card is selected at random from ordinary 52-card deck.

What is the probability that it is a heart?

Solution

probability that it is a heart, P(heart)=13 ÷ 52 = 1÷4 = 0.25

Discussion

definition 6.6.1 A probability function P assigns to each outcome x in a sample space S a number P(x) so that, 0P(x)1, for all xS, and, P(x) =1

For this problem, S={heart, spade, clover, diamond}

Comment

뿐만 아니라 카드에서 숫자가 나올 확률은 4/52 = 1/13모든 숫자가 같다.

Problem 18

[Final OK by SGLee]CH.6 page 371 Problem 18 solved 정호진, 칭기즈, 김주형, 강병훈

Problem

Two pair dice are rolled, What is the probability that the sum of the numbers on the dice is 8?

Solution

If n1+n2=8,

(n1,n2) S'

S'={(2,6),(3,5),(4,4),(5,3),(6,2)} number of favorable outcomes=5

S={(1,1),(1,2),(1,3),...,(6,5),(6,6)} total number of possible outcomes=6×6=36

Discussion

​​- the condition : n1+n2=8

All cases,

1) n1=1 n2=7(impossible!)

2) n1=2 n2=6

3) n1=3 n2=5

4) n1=4 n2=4

5) n1=5 n2=3

6) n1=6 n2=2

S'={(2,6),(3,5),(4,4),(5,3),(6,2)}number of favorable outcomes = 5

- product rule

 Multiplication Principle (Product Rule) total number of possible outcomes=6×6=36

Comment

주변에서 가장 흔하게 확률을 접할 수 있는 주사위의 확률을 구하는 법으로 6면체가 아니더라도 모든 주사위에 대해서 적용할 수 있다.

Problem 20

[Final OK by SGLee] CH.6 page 371  Problem 20 solved 김영철, 전종문, 전솔람

Problem

Find the probability of obtaining a bridge hand with 6-5-2-0 distribution, that is, six cards in one suit, five cards in another suit, two cards in another suit, and no card in the fourth suit.

Solution

0.    There are 4 suits and 13 cards in each suit, which makes total of 52 cards.

​1.    Number of cases of choosing 6 cards, 5 cards, 2 cards, 0 cards from some suit is

C(13, 6) ,
C(13, 5) , C(13, 2) , C(13, 0)​

respectively.

2.   We can see from above we need 4 distinct suits, from total of 4 suits.

So the number of cases of choosing 4 suits out of 4 suits is,
P(4,4).

3.    To get entire number of cases, we need to multiply all the numbers above,

which is C(13, 6) x
C(13, 5) x C(13, 2) x C(13, 0) x P(4, 4).

To rewrite, it is C(13, 6) x
C(13, 5) x C(13, 2) x 4 x 3 x 2.

4.    ​Total number of cases of choosing 13 cards out of 52 cards is C(52,13)

5.    ​So the probability here is { C(13, 6) x C(13, 5) x C(13, 2) x 4 x 3 x 2 } / C(52, 13).

{ C(13, 6) x C(13, 5) x C(13, 2) x 4 x 3 x 2 } / C(52, 13) = 0.65%  ■

Comment

카드를 배열하는 방법뿐만 아니라 문양 또한 다르게 들어갈 수 있다는 것에 주의해야 하면 혹시나 같은 개수가 나온다면 나눠주어야 하기 때문에 그 점은 주의하여야 한다.

Problem 21

[Final OK by SGLee]CH.6 page 371 Problem 21 solved 김영철, 김희성, 전솔람, 만우흠, 강병훈

Problem

A coin is loaded so that a head is five times as likely to occur as a tail. Assign probabilities to the outcomes that accurately model the likelihood of the outcomes to occur.

Solution

Let event H denote: the head occurs on a coin and T denote the tail occur on it.

Therefore P(H)=5 P(T)  (P: probability)

We know that

P(H)+P(T)=1

5 P(T)+P(T)=1

6 P(T)=1

P(T)=1/6

Then

P(H)=1-P(T)

=1-1/6

=5/6

Probability that a head occurs : P(H)=5/6

Probability that a tail occurs : P(T)=1/6    ■

Note

Comment

시행으로 인하여 확률을 정한다. 시행횟수가 많아지면 달라질 수도 있겠지만 이산수학이기에 이미 시행된 정보만으로 확률을 설정한다.

Problem 22

[Final OK by SGLee]CH.6 page 371 Problem 22  solved 서명원, 김영철, 김은률, 전솔람, 김주형, 강병훈

Problem

A family has three children. Assume that it is equally probable for a boy or a girl to be born. Are the events "there are children of both sexes." and "there is at most one girl." independent? Explain.

Solution

​​Event A : "there are children of both sexes."

Event B : "there is at most one girl."

If P(A B) = P(A)​ × P(B) , they are independent

P(A) = 1 - [P(only boys) + P(only girls)] = 1 - (1/2×1/2×1/2 + 1/2×1/2×1/2) = 1 - 1/4 = 3/4

P(B) = P(only boys) + P(1 girl) = 1/8 + (​3C1​×1/2×1/2×1/2) = 1/8 + 3/8 = 1/2

P(A B) = P(1 girl) = 3/8

P(A) × P(B) = P(A B)  A and B are independent.

The events "there are children of both sexes." and "there is at most one girl." are independent.

Comment

각각의 사건이 독립인지 아닌지 구분할 수 있다.

Problem 23

[Final OK by SGLee]CH.6 page 371 Problem 23  solved 김영철, 전종문, 전솔람

Problem

Joe and Alicia take a final examination in C++. The probability that Joe passes  is 0.75, and the probability that Alicia passes  is 0.80. Assume that the events “Joe passes the final examination” and “Alicia passes the final examination” are independent. Find the probability that Joe does not pass Find the probability that both pass. Find the probability that both fail. Find the probability that at least one passes.

Solution

0.    If two events A and B are independent, the probability of those two events

occurring at the same time is the P[A] x P[B].

​1.    As the problem states that Joe passing the final exam(= event A)

and Alicia passing the final exam(= event B) are independent,

the probability of both passing the final exam is

P[A] x P[B] = 0.75 x 0.8 = 0.6

2.    The probability that Joe fails is 1 - P[A] = 0.25

and the probability that Alicia fails is 1 - P[b] = 0.2

So the probability that both fail is

(1-P[A]) x (1-P[B]) = 0.25 x 0.2 = 0.05.

​3.    The probability at least one passes is

1 - P[both fails] = 1 - 0.05 = 0.95

P[Joe fail]=1 - P[A] = 0.25,

P[both pass] = 0.6,

P[both fail] = 0.05,

P[At least 1 passes] = 0.95   ■​​

Comment

전체 확률을 1 두고 반대 확률을 뺴면 간단하게 있는 문제이다

Problem 24

[Final OK by SGLee] CH.6 page 371 Problem 24 solved 서명원, 김승연, 김은율, 정호진, 강병훈

Problem

Trisha, Roosevelt, and José write programs that schedule tasks for manufacturing dog toys. The following table shows the percentage of code written by each person and the percentage of buggy code for each person

 coder Trisha Roosevelt José percentage of code 30 45 25 percentage of bugs 3 2 5

Given that a bug was found, find the probability

that it was in the code written by José.

Solution
1.
Let

B : Probability of bug code occur​

BT​ : Trisha

BR : Roosevelt

BJ: José

​P: Probability of he or she made the code

﻿﻿T: Probability of each person made a bug

2.

TT : BT​​ ×PT = 0.9 (percent)

TR : BR ×PR = 0.9 (percent)

T​J​​  : B​J​ ×P​J= 1.25 (percent)

Probability of José. made a bug / sum of probability of all people made a bug

T​J​​ /(TT +T​R +T​J​) = ​1.25 / 3.05 = 0.409836

Comment

경우의 수만 이용하여 확률을 구하는 것이 아니라 각각의 확률을 이용해서 확률을 구할 수 있다.

Problem 26

[Final OK by SGLee] CH.6 page 371 Problem 26 solved 오동찬, 김영철, 전종문, 만우흠, 강병훈

Problem

Find the coefficient of x 3yz 4 in the expansion of (2x + y + z)8

Solution

expansion of (2x + y + z)8=(2x + y + z)​​(2x + y + z)(2x + y + z)(2x + y + z)(2x + y + z)(2x + y + z)(2x + y + z)(2x + y + z)

Then choose three terms for the x in C(8,3) ways.

choose on term for y in C(5,1) ways.

Thus the coefficient of x3yz4 in the expansion (2x + y + z)8 is

23​×C(8,3) / C(5,1)

= 23​×(8! / 3!)5

= 23×8! / 3! ×4!

= 322560/144

= 2240

The coefficient of x 3yz 4  = 2240   ■​​

Comment

콤비네이션을 이용하여 전개항의 계수도 파악할 수 있다.

Problem 30

[Final OK by SGLee]CH.6 page 371 Problem 30 solved 김승연, 전종문, 이양휘, 강병훈

Problem

Nineteen persons have first names ZekeWally, and Lindamiddle names Lee and David; and last names YuZamora and Smith. Show that at least two persons have the same first, middle, and last names.

Solution

Step A) There are 3 independent name categories (first, middle, and last name)

I)             First names ZekeWally, and Linda

II)   Middle names Lee and David

II)           Last names YuZamora and Smith

Step B)

3 × 2 × 3 = 18 ways (Using Multiplication Rule)

There are 18 possible names for the 19 persons.

By the Pigeonhole Principle,

Some name (pigeonhole) is assigned to at least two persons (pigeons).  ■

Comment

경우의 수를 계산할 알면 비둘기 원리에 의해서 쉽게 증명이 있다.

Problem 31

[Final OK by SGLee]CH.6 page 372 Problem 31 solved 김승연, 오동찬, 권혁찬, 만우흠, 강병훈

Problem

An inventory consists of a list of 200 items, each marked “available” or “unavailable”. There are 110 available items. Show that there are at least two available items in the list exactly 19 items apart.

Solution

Step A) to simplify problem, we can consider there is an empty string of a length of 200 as following:

□ ......... □ □

. now we going let's assume that  “available” items are marked as"", and unavailable  items as " 0 ". So there are 110  "" , and 90  "  ".

Step B) now Let's create 19 partitions using the rest of division. (use X mod 19)

 1 20 39 58 77 96 115 134 153 172 191 2 21 40 59 78 97 116 135 154 173 192 3 22 41 60 79 98 117 136 155 174 193 4 23 42 61 80 99 118 137 156 175 194 5 24 43 62 81 100 119 138 157 176 195 6 25 44 63 82 101 120 139 158 177 196 7 26 45 64 83 102 121 140 159 178 197 8 27 46 65 84 103 122 141 160 179 198 9 28 47 66 85 104 123 142 161 180 199 10 29 48 67 86 105 124 143 162 181 200 11 30 49 68 87 106 125 144 163 182 12 31 50 69 88 107 126 145 164 183 13 32 51 70 89 108 127 146 165 184 14 33 52 71 90 109 128 147 166 185 15 34 53 72 91 110 129 148 167 186 16 35 54 73 92 111 130 149 168 187 17 36 55 74 93 112 131 150 169 188 18 37 56 75 94 113 132 151 170 189 19 38 57 76 95 114 133 152 171 190

If any one element in the partition is A, the adjacent elements must not be A. That means, The array in the partition will be"1 " and "0 " alternately.

1st to 10th ​​partition have 11 elements, so need at least five "0 " s.​​

11th to 19th partition have 10 elements, so need at least five "0 " s too.​​​

Now, we need 5 × 10 + 5 × 9 = 95   "0 " are needed.

But we have only 90  "0 " are left.

By the contradiction , there are at least two available items in the list exactly 19items apart.                           ■

Comment

해당 방법을 이용하면  필요한 정보가 어디에 있는지 예측할 있다.