+0

# Counting

0
91
1

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?

Feb 11, 2023

#1
0

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.

Feb 11, 2023