Skip to main content
OlympiadHQ

Browse · MATH

Print

jmc

counting and probability senior

Problem

A set of people participate in an online video basketball tournament. Each person may be a member of any number of -player teams, but no two teams may have exactly the same members. The site statistics show a curious fact: The average, over all subsets of size of the set of participants, of the number of complete teams whose members are among those people is equal to the reciprocal of the average, over all subsets of size of the set of participants, of the number of complete teams whose members are among those people. How many values , , can be the number of participants?
Solution
Let there be teams. For each team, there are different subsets of players including that full team, so the total number of team-(group of 9) pairs is Thus, the expected value of the number of full teams in a random set of players is Similarly, the expected value of the number of full teams in a random set of players is The condition is thus equivalent to the existence of a positive integer such that Note that this is always less than , so as long as is integral, is a possibility. Thus, we have that this is equivalent to It is obvious that divides the RHS, and that does iff . Also, divides it iff . One can also bash out that divides it in out of the possible residues . Using all numbers from to , inclusive, it is clear that each possible residue is reached an equal number of times, so the total number of working in that range is . However, we must subtract the number of "working" , which is . Thus, the answer is .
Final answer
557