a Let S be a set with partition A B If we want to be sure th

(a) Let S be a set with partition A, B. If we want to be sure that either |A| m or |B| n, what can we say about |S|? Justify your answer.

(b) Suppose we have ten people at a party. Show that there must be either a group of three mutual acquaintances or a group of four mutual strangers

Solution

1. if A>=m and B >= n then maximum size of S will be m+n-1

since in the partition at least , one element must be common

2.this can be shown by pigeonhole priniciple

greatest integer of (10/3) = 4

therefore at least group of four mutual integers.