Difference between revisions of "2017 AMC 12B Problems/Problem 25"
m (→Solution) |
|||
(10 intermediate revisions by 6 users not shown) | |||
Line 7: | Line 7: | ||
==Solution== | ==Solution== | ||
− | + | 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 that includes a given 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 | ||
<cmath>T{n-5\choose 4}.</cmath> | <cmath>T{n-5\choose 4}.</cmath> | ||
Line 40: | Line 37: | ||
<cmath>2^5\cdot3^2\cdot5\cdot7\big|(n)(n-1)(n-2)(n-3)(n-4).</cmath> | <cmath>2^5\cdot3^2\cdot5\cdot7\big|(n)(n-1)(n-2)(n-3)(n-4).</cmath> | ||
− | It is obvious that <math>5</math> divides the RHS, and that <math>7</math> does | + | It is obvious that <math>5</math> divides the RHS, and that <math>7</math> does if <math>n\equiv 0,1,2,3,4\mod 7</math>. Also, <math>3^2</math> divides it if <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>. |
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>. | 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>. | ||
Line 46: | Line 43: | ||
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>. | 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 | + | ==Solution 1.0== |
+ | Another way to find the average number of teams in a group of 9 or 8 people is as follows: | ||
+ | |||
+ | Let there be <math>T</math> teams. There are <math>\binom{n}{5}</math> total possible teams. So, the probability of any 5 people being a team is <math>\frac{T}{\binom{n}{5}}</math>. There are <math>\binom{9}{5}</math> possible teams in a group of 9. So, on average, there will be | ||
+ | <cmath>\frac{T}{\binom{n}{5}} \binom{9}{5} </cmath> | ||
+ | teams in any group of 9 people. Similarly, on average, there will be | ||
+ | <cmath>\frac{T}{\binom{n}{5}} \binom{8}{5} </cmath> | ||
+ | teams in any group of 8 people. So, | ||
+ | \begin{align*} | ||
+ | \frac{T}{\binom{n}{5}} \binom{9}{5} = \frac{1}{\frac{T}{\binom{n}{5}} \binom{8}{5}} \implies& \binom{9}{5}\binom{8}{5} T^2 = \binom{n}{5}^2 \ | ||
+ | \implies& 84T = \binom{n}{5} | ||
+ | \end{align*} | ||
+ | Therefore <math>84 \mid \binom{n}{5}</math> and proceed as shown in solution 1. | ||
+ | |||
+ | FYI, to find n such that <math>32 \mid n(n-1)(n-2)(n-3)(n-4)</math> without bashing everything: | ||
+ | Clearly <math>n \equiv 0, 1, 2, 3, 4 \pmod{32}</math> works. Then, do cases. | ||
+ | |||
+ | Case 1: <math>4 \mid n</math>. | ||
+ | This will always work, as <math>4 \mid n</math>, <math>4 \mid n-4</math>, and <math>2 \mid n-2</math>, so <math>4 \cdot 4 \cdot 2 = 32 \mid n(n-1)(n-2)(n-3)(n-4)</math>. So, | ||
+ | <cmath>n \equiv 0, 4, 8, 12, 16, 20, 24, 28 \pmod{32}</cmath> | ||
+ | are also solutions. | ||
+ | |||
+ | Case 2: <math>n \equiv 2 \pmod{4}</math> | ||
+ | Then <math>n-4 \equiv 2 \pmod{4}</math> as well. <math>n</math> and <math>n-4</math> can only contribute one 2 each, since <math>4 \nmid n, n-4</math>. We need a factor of <math>2^3</math> in <math>n-2</math> then. So, <math>n \equiv 2 \pmod{8}</math>. Then, we get | ||
+ | <cmath>n \equiv 2, 10, 18, 26 \pmod{32}</cmath>. | ||
+ | |||
+ | Case 3: <math>4 \nmid n</math> | ||
+ | We can only get twos from <math>n-1</math> and <math>n-3</math>. Note that one of them can only contribute a single factor of 2, because otherwise <math>4 \mid n-1</math> and <math>4 \mid n-3</math>, so <math>n</math> has a remainder of both 1 and 3 mod 4, which is impossible. So, one must have a factor of 16. We get <math>n \equiv 1, 3 \pmod{16}</math> so | ||
+ | <cmath>n \equiv 1, 3, 17, 19 \pmod{32}</cmath> | ||
+ | |||
+ | In all, we get the solutions | ||
+ | <cmath> n \equiv 0, 1, 2, 3, 4, 8, 10, 16, 17, 18, 19, 20, 24, 26, 28 \pmod{32} </cmath> | ||
+ | |||
+ | ~[https://artofproblemsolving.com/wiki/index.php/User:Crazyvideogamez CrazyVideoGamez] | ||
+ | |||
+ | ==Video Solution by Dr. Nal== | ||
https://www.youtube.com/watch?v=2p2qYRWbvV4&feature=emb_logo | https://www.youtube.com/watch?v=2p2qYRWbvV4&feature=emb_logo |
Latest revision as of 17:23, 16 October 2024
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 that includes a given 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 if . Also, divides it if . One can also bash out that divides it in out of the possible residues .
Note that so by 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 .
Alternatively, it is enough to approximate by finding the floor of to get .
Solution 1.0
Another way to find the average number of teams in a group of 9 or 8 people is as follows:
Let there be teams. There are total possible teams. So, the probability of any 5 people being a team is . There are possible teams in a group of 9. So, on average, there will be
teams in any group of 9 people. Similarly, on average, there will be
teams in any group of 8 people. So,
FYI, to find n such that without bashing everything: Clearly works. Then, do cases.
Case 1: . This will always work, as , , and , so . So, are also solutions.
Case 2: Then as well. and can only contribute one 2 each, since . We need a factor of in then. So, . Then, we get .
Case 3: We can only get twos from and . Note that one of them can only contribute a single factor of 2, because otherwise and , so has a remainder of both 1 and 3 mod 4, which is impossible. So, one must have a factor of 16. We get so
In all, we get the solutions
Video Solution by Dr. Nal
https://www.youtube.com/watch?v=2p2qYRWbvV4&feature=emb_logo
See Also
2017 AMC 12B (Problems • Answer Key • Resources) | |
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.