Difference between revisions of "2017 AMC 12B Problems/Problem 25"

(added problem and solution)
 
m (Added some clarification and an alternative approximation for the solution)
(6 intermediate revisions by 5 users not shown)
Line 6: Line 6:
  
 
==Solution==
 
==Solution==
 +
 +
Solution by Pieater314159
 +
 +
Minor edits by Zeric
  
 
Let there be <math>T</math> teams. For each team, there are <math>{n-5\choose 4}</math> different subsets of <math>9</math> players including that full team, so the total number of team-(group of 9) pairs is  
 
Let there be <math>T</math> teams. For each team, there are <math>{n-5\choose 4}</math> different subsets of <math>9</math> players including that full team, so the total number of team-(group of 9) pairs is  
Line 39: Line 43:
 
It is obvious that <math>5</math> divides the RHS, and that <math>7</math> does iff <math>n\equiv 0,1,2,3,4\mod 7</math>. Also, <math>3^2</math> divides it iff <math>n\not\equiv 5,8\mod 9</math>. One can also bash out that <math>2^5</math> divides it in <math>16</math> out of the <math>32</math> possible residues <math>\mod 32</math>.  
 
It is obvious that <math>5</math> divides the RHS, and that <math>7</math> does iff <math>n\equiv 0,1,2,3,4\mod 7</math>. Also, <math>3^2</math> divides it iff <math>n\not\equiv 5,8\mod 9</math>. One can also bash out that <math>2^5</math> divides it in <math>16</math> out of the <math>32</math> possible residues <math>\mod 32</math>.  
  
Using all numbers from <math>2</math> to <math>2017</math>, inclusive, it is clear that each possible residue <math>\mod 7,9,32</math> is reached an equal number of times, so the total number of working <math>n</math> in that range is <math>5\cdot 7\cdot 16 = 560</math>. However, we must subtract the number of "working" <math>2\leq n\leq 8</math>, which is <math>3</math>. Thus, the answer is <math>\textbf{(D) } 557</math>.
+
Note that <math>2016 = 7*9*32</math> so by using all numbers from <math>2</math> to <math>2017</math>, inclusive, it is clear that each possible residue <math>\mod 7,9,32</math> is reached an equal number of times, so the total number of working <math>n</math> in that range is <math>5\cdot 7\cdot 16 = 560</math>. However, we must subtract the number of "working" <math>2\leq n\leq 8</math>, which is <math>3</math>. Thus, the answer is <math>\boxed{\textbf{(D) } 557}</math>.
 +
 
 +
Alternatively, it is enough to approximate by finding the floor of <math>2017 \cdot \frac57 \cdot \frac79 \cdot \frac12 - 3</math> to get <math>\boxed{\textbf{(D) } 557}</math>.
 +
 
 +
Video Solution by Dr. Nal:
 +
 
 +
https://www.youtube.com/watch?v=2p2qYRWbvV4&feature=emb_logo
  
 
==See Also==
 
==See Also==
{{AMC12 box|year=2016|ab=B|num-b=24|after=Last Problem}}
+
{{AMC12 box|year=2017|ab=B|num-b=24|after=Last Problem}}
 
{{MAA Notice}}
 
{{MAA Notice}}
 +
 +
[[Category:Intermediate Combinatorics Problems]]

Revision as of 15:52, 7 November 2021

Problem

A set of $n$ people participate in an online video basketball tournament. Each person may be a member of any number of $5$-player teams, but no two teams may have exactly the same $5$ members. The site statistics show a curious fact: The average, over all subsets of size $9$ of the set of $n$ participants, of the number of complete teams whose members are among those $9$ people is equal to the reciprocal of the average, over all subsets of size $8$ of the set of $n$ participants, of the number of complete teams whose members are among those $8$ people. How many values $n$, $9\leq n\leq 2017$, can be the number of participants?

$\textbf{(A) } 477 \qquad \textbf{(B) } 482 \qquad \textbf{(C) } 487 \qquad \textbf{(D) } 557 \qquad \textbf{(E) } 562$

Solution

Solution by Pieater314159

Minor edits by Zeric

Let there be $T$ teams. For each team, there are ${n-5\choose 4}$ different subsets of $9$ players including that full team, so the total number of team-(group of 9) pairs is

\[T{n-5\choose 4}.\]

Thus, the expected value of the number of full teams in a random set of $9$ players is

\[\frac{T{n-5\choose 4}}{{n\choose 9}}.\]

Similarly, the expected value of the number of full teams in a random set of $8$ players is

\[\frac{T{n-5\choose 3}}{{n\choose 8}}.\]

The condition is thus equivalent to the existence of a positive integer $T$ such that

\[\frac{T{n-5\choose 4}}{{n\choose 9}}\frac{T{n-5\choose 3}}{{n\choose 8}} = 1.\]

\[T^2\frac{(n-5)!(n-5)!8!9!(n-8)!(n-9)!}{n!n!(n-8)!(n-9)!3!4!} = 1\]

\[T^2 = \big((n)(n-1)(n-2)(n-3)(n-4)\big)^2 \frac{3!4!}{8!9!}\]

\[T^2 = \big((n)(n-1)(n-2)(n-3)(n-4)\big)^2 \frac{144}{7!7!8\cdot8\cdot9}\]

\[T^2 = \big((n)(n-1)(n-2)(n-3)(n-4)\big)^2 \frac{1}{4\cdot7!7!}\]

\[T = \frac{(n)(n-1)(n-2)(n-3)(n-4)}{2^5\cdot3^2\cdot5\cdot7}\]

Note that this is always less than ${n\choose 5}$, so as long as $T$ is integral, $n$ is a possibility. Thus, we have that this is equivalent to

\[2^5\cdot3^2\cdot5\cdot7\big|(n)(n-1)(n-2)(n-3)(n-4).\]

It is obvious that $5$ divides the RHS, and that $7$ does iff $n\equiv 0,1,2,3,4\mod 7$. Also, $3^2$ divides it iff $n\not\equiv 5,8\mod 9$. One can also bash out that $2^5$ divides it in $16$ out of the $32$ possible residues $\mod 32$.

Note that $2016 = 7*9*32$ so by using all numbers from $2$ to $2017$, inclusive, it is clear that each possible residue $\mod 7,9,32$ is reached an equal number of times, so the total number of working $n$ in that range is $5\cdot 7\cdot 16 = 560$. However, we must subtract the number of "working" $2\leq n\leq 8$, which is $3$. Thus, the answer is $\boxed{\textbf{(D) } 557}$.

Alternatively, it is enough to approximate by finding the floor of $2017 \cdot \frac57 \cdot \frac79 \cdot \frac12 - 3$ to get $\boxed{\textbf{(D) } 557}$.

Video Solution by Dr. Nal:

https://www.youtube.com/watch?v=2p2qYRWbvV4&feature=emb_logo

See Also

2017 AMC 12B (ProblemsAnswer KeyResources)
Preceded by
Problem 24
Followed by
Last Problem
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
All AMC 12 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png