+0

# Counting

0
69
1

Help how to solve using combination

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?

Mar 7, 2023

#1
0

To avoid having the exact same group of members over all 365 days, we need to ensure that the combination of members invited on any two days is different.

We can use the formula for combinations to calculate the total number of unique combinations of n people that can be invited on any given day. The formula for combinations is:

nCk = n! / (k! * (n-k)!)

where n is the number of people in the book club, k is the number of people invited on any given day, and ! denotes the factorial function.

We want to ensure that the combination of members invited on any two days is different, so we need to find the smallest n such that:

nCk1 ≠ nCk2 for all k1 and k2 where 1 ≤ k1 < k2 ≤ n

In other words, we need to find the smallest n such that the number of unique combinations of k people that can be invited on any given day is greater than or equal to 100 (the number of days).

We can start by trying different values of n and calculating the number of unique combinations of k people that can be invited on any given day for each value of k from 1 to n. Once we find an n that satisfies the condition above, we know that it is the smallest n that will work.

For example, if we try n = 5, we can calculate the number of unique combinations of k people that can be invited on any given day for k = 1, 2, 3, 4, and 5:

nC1 = 5C1 = 5
nC2 = 5C2 = 10
nC3 = 5C3 = 10
nC4 = 5C4 = 5
nC5 = 5C5 = 1

The total number of unique combinations is 31, which is greater than 100. Therefore, n = 5 is a valid solution.

We could continue trying different values of n until we find the smallest one that works, but a more efficient approach is to use the principle of inclusion-exclusion. This principle states that the number of combinations that satisfy at least one of several conditions is equal to the sum of the number of combinations that satisfy each individual condition, minus the sum of the number of combinations that satisfy each pair of conditions, plus the sum of the number of combinations that satisfy each triple of conditions, and so on.

In this case, we can apply the principle of inclusion-exclusion to count the number of combinations that are repeated over the 100 days. Let N be the total number of combinations of n members that can be invited on any given day. Then, the number of combinations that are repeated at least once over the 100 days is:

N - (N choose 2) + (N choose 3) - ... + (-1)^99 (N choose 100)

We want to find the smallest n such that this number is less than or equal to 0 (i.e., all 100 combinations are unique). We can start with n = 1 and calculate this expression for each value of n until we find the smallest n that works. This approach is more efficient than trying all possible values of n.

Mar 7, 2023