http://matrix.skku.ac.kr/2018-DM/DM-Labs.htm Discrete Math Labs (실습실)
http://matrix.skku.ac.kr/2018-album/2018-Lectures-sglee.htm (강의실)
http://matrix.skku.ac.kr/2018-DM-QnA/
(질문과 답변)
http://matrix.skku.ac.kr/2018-DM-Sol/2018-DM-Sol.htm (문제풀이)
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 24 =
16.
Answer:
24 = 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
Answer
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,
All possible function =2n
2.
Non
onto funcion
=2
3.
# of all onto functions
=2n
- 2
Answer
# 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: 6 × 5 × 4 × 3 = 360
2.
Greg is not an officer: 6 × 5 ×
4 × 3 × 2 = 720
Answer
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
Answer: 20 ■
Note
|
Definition
2.15 |
|
|
Given a set (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! |
|
containing n (distinct) elements,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. AEC and EAC , × 2
3. B, D,
F ordering =3!
Answer
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.
Answer: 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
2.
defective
: 4
∴ C(5,3) ×
C(95,1).+ C(5,4)
= 955
Answer: 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!/3!×2!
= 3360
2.
put LLIII order 8!/5!
= 336
3.
3360
– 336 = 3024
Answer: 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)
Answer
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
Answer 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 n =
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.
Answer ∴12567 ■
Comment
4단원에서 배운 알고리즘을 이용해서 문제를 해결했다.
Note
Pseudo Code :
1. combination(r, n) {
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, r ) {
6. m = r
7. max val = n
8. while (sm == max val) {
9. // find the rightmost element not at its maximum value
10. m = m − 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 j = m + 1 to r
17. s j = s j−1 + 1
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 10–13, 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
Answer 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 sn−1, 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
Answer 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, 0≤P(x)≤1, for all x∈S, and, ∑P(x) =1
For this problem, S={heart, spade, clover, diamond}
P(heart)=P(spade)=P(clover)=P(diamand)=13/52=1/4
∑P(x)=P(heart)+P(spade)+P(clover)+P(diamond)=1/4+1/4+1/4+1/4=1
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
Answer Probability=5/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).
Answer
{ 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
Answer
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
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
P(A) × P(B) = P(A
Answer
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
Answer
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)
TJ : BJ ×PJ
= 1.25
(percent)
Answer
Probability of José. made a bug / sum of
probability of all people made a bug
TJ /(TT +TR +TJ) = 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
Answer
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 Zeke, Wally, and Linda; middle names Lee and David; and last names Yu, Zamora 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 Zeke, Wally,
and Linda
II)
Middle names Lee and David
II) Last
names Yu, Zamora 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,
Answer
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"1 ", and “unavailable ” items as
" 0 ". So there are 110 "1 " , and 90 " 0 ".
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 |
Step C) Using Contradiction ,
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.
Answer
∴ By the contradiction , there are at least two available items
in the list exactly 19items apart.
■
Comment
해당 방법을 이용하면 필요한 정보가 어디에 있는지 예측할 수 있다.