CS206 -Discrete Mathematics II
Instructor: Chitoor V.Srinivasan
PROBLEM SET 2 SOLUTIONS

  1. 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.

  2. Let   tex2html_wrap_inline20   be the number of matches played on or before the j'th hour. Then   tex2html_wrap_inline22   is an increasing sequence of distinct positive integers with   tex2html_wrap_inline24   For any integer k,   tex2html_wrap_inline26   is an also increasing sequence of distinct positive integers with   tex2html_wrap_inline28   There are 150 integers in these two sequences. If tex2html_wrap_inline30 , 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 tex2html_wrap_inline32 . By definition of tex2html_wrap_inline34 , the wrestler had exactly k matches during the period from hour j to hour i. In summation, for every   tex2html_wrap_inline36   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.

  3. 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.)

  4. The terms of the expansion are of the form   tex2html_wrap_inline38   (A is the coefficient) where   tex2html_wrap_inline40   The number of such terms is the number of ways of choosing n items [one item from each of the n factors tex2html_wrap_inline42 ] with repitition from m distinct types. Thus, there are C(n+m-1,n) terms.

  5. C(n-1,m-1). This problem is discussed in section 2.8.2 of the course notes.