CS206 -Discrete Mathematics II
Instructor: Chitoor V.Srinivasan
PROBLEM SET 2 SOLUTIONS
- Let A be one of the 20 people. There are 19 others. By the
pigeonhole principle A has at least 10 friends or at least 10 enemies.
Case 1: A has at least 10 friends
If there are 4 mutual enemies among these 10 people we are done. Otherwise
the given result implies that this group of 10 people contains 3 mutual
friends. But these 3 are all friends of A thus forming a group of 4 mutual
friends.
The case where A has at least 10 enemies is symmetric; simply replace every
occurrence of friend with enemy and vice-versa in the above to obtain a proof.
- Let
be the number of matches played on or before the j'th hour.
Then
is an increasing sequence of distinct positive
integers with
For any integer k,
is an also increasing sequence of distinct
positive integers with
There are 150 integers in
these two sequences. If
, we will have
more integers in the two sequences than the total number of distinct integers.
By the pigeonhole principle, at least two numbers, say x and y, in the
sequences are the same. Since each sequence is made up of distinct numbers,
x and y come from different sequences. Thus, there is an i and a j such that
. By definition of
, the wrestler had exactly k
matches during the period from hour j to hour i. In summation, for every
there will be a sequence of consecutive hours during which k
matches are held. Hence, the answers are, (a) Yes, (b) Yes, (c) No and (d) No. -
Any two distinct vertices defines a line segment joining them. There are
C(n,2) line segments. N of these constitute the sides of the polygon. Thus,
the remaining C(n,2) - n line segments are the diagonals. Alternative
solution: From any vertex you can draw a diagonal to every other vertex except
itself and its two neighbors. I.e. each vertex participates in n-3 diagonals.
If you sum this over all n vertices, you will count each diagonal twice -
once for each of the two endpoints. Thus, there are n * (n-3) / 2 diagonals.
(You can algebraically show that these two answers are the same, if you wish.)
- The terms of the expansion are of the form
(A is the coefficient) where
The number of such terms is the number of ways of choosing n items
[one item from each of the n factors
]
with repitition from m distinct types. Thus, there are C(n+m-1,n) terms. - C(n-1,m-1). This problem is discussed in section 2.8.2 of the
course notes.