help how do I do this
I run a book club with n people, not including myself. Every day, for 100 days, I invite members in the club to review a book. What is the smallest positive integer n so that I can avoid ever having the exact same group of members over all 365 days?
+938 The problem can be restated as finding the smallest positive integer n such that there exist 100 distinct subsets of the club, each of size k, where 1 <= k <= n. This is equivalent to finding the smallest positive integer n such that n choose k is greater than or equal to 100 for all values of k from 1 to n.
By the Pigeonhole Principle, if we have n people, then at most n choose k people can review the same book. Hence, we want the smallest positive integer n such that:
C(n,1) >= 100
C(n,2) >= 100
...
C(n,n) >= 100
We can start by computing some of the binomial coefficients and finding the smallest value of n that satisfies the conditions.
C(2,1) = 2 >= 100 (not satisfied)
C(3,1) = 3 >= 100 (not satisfied)
C(3,2) = 3 >= 100 (not satisfied)
C(4,1) = 4 >= 100 (not satisfied)
C(4,2) = 6 >= 100 (not satisfied)
C(4,3) = 4 >= 100 (not satisfied)
C(5,1) = 5 >= 100 (not satisfied)
C(5,2) = 10 >= 100 (not satisfied)
C(5,3) = 10 >= 100 (not satisfied)
C(5,4) = 5 >= 100 (not satisfied)
The smallest n that satisfies all the conditions is 6, so the smallest positive integer n that allows us to avoid having the exact same group of members over all 100 days is 6.
