https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Kkd&feedformat=atomAoPS Wiki - User contributions [en]2024-03-29T06:48:00ZUser contributionsMediaWiki 1.31.1https://artofproblemsolving.com/wiki/index.php?title=1997_AIME_Problems/Problem_12&diff=1312291997 AIME Problems/Problem 122020-08-09T16:30:02Z<p>Kkd: /* Solution 6 (Short) */</p>
<hr />
<div>== Problem ==<br />
The [[function]] <math>f</math> defined by <math>f(x)= \frac{ax+b}{cx+d}</math>, where <math>a</math>,<math>b</math>,<math>c</math> and <math>d</math> are nonzero real numbers, has the properties <math>f(19)=19</math>, <math>f(97)=97</math> and <math>f(f(x))=x</math> for all values except <math>\frac{-d}{c}</math>. Find the unique number that is not in the range of <math>f</math>.<br />
<br />
__TOC__<br />
== Solution ==<br />
=== Solution 1 ===<br />
First, we use the fact that <math>f(f(x)) = x</math> for all <math>x</math> in the domain. Substituting the function definition, we have <math>\frac {a\frac {ax + b}{cx + d} + b}{c\frac {ax + b}{cx + d} + d} = x</math>, which reduces to<br />
<cmath>\frac {(a^2 + bc)x + b(a + d)}{c(a + d)x + (bc + d^2)} =\frac {px + q}{rx + s} = x. </cmath><br />
In order for this fraction to reduce to <math>x</math>, we must have <math>q = r = 0</math> and <math>p = s\not = 0</math>. From <math>c(a + d) = b(a + d) = 0</math>, we get <math>a = - d</math> or <math>b = c = 0</math>. The second cannot be true, since we are given that <math>a,b,c,d</math> are nonzero. This means <math>a = - d</math>, so <math>f(x) = \frac {ax + b}{cx - a}</math>.<br />
<br />
The only value that is not in the range of this function is <math>\frac {a}{c}</math>. To find <math>\frac {a}{c}</math>, we use the two values of the function given to us. We get <math>2(97)a + b = 97^2c</math> and <math>2(19)a + b = 19^2c</math>. Subtracting the second equation from the first will eliminate <math>b</math>, and this results in <math>2(97 - 19)a = (97^2 - 19^2)c</math>, so<br />
<cmath>\frac {a}{c} = \frac {(97 - 19)(97 + 19)}{2(97 - 19)} = 58 . </cmath><br />
<br />
Alternatively, we could have found out that <math>a = -d</math> by using the fact that <math>f(f(-b/a))=-b/a</math>.<br />
<br />
=== Solution 2 ===<br />
First, we note that <math>e = \frac ac</math> is the horizontal [[Asymptote (Geometry)|asymptote]] of the function, and since this is a linear function over a linear function, the unique number not in the range of <math>f</math> will be <math>e</math>. <math>\frac{ax+b}{cx+d} = \frac{b-\frac{cd}{a}}{cx+d} + \frac{a}{c}</math>. [[Without loss of generality]], let <math>c=1</math>, so the function becomes <math>\frac{b- \frac{d}{a}}{x+d} + e</math>. <br />
<br />
(Considering <math>\infty</math> as a limit) By the given, <math>f(f(\infty)) = \infty</math>. <math>\lim_{x \rightarrow \infty} f(x) = e</math>, so <math>f(e) = \infty</math>. <math>f(x) \rightarrow \infty</math> as <math>x</math> reaches the vertical [[Asymptote (Geometry)|asymptote]], which is at <math>-\frac{d}{c} = -d</math>. Hence <math>e = -d</math>. Substituting the givens, we get <br />
<br />
<cmath>\begin{align*}<br />
19 &= \frac{b - \frac da}{19 - e} + e\\<br />
97 &= \frac{b - \frac da}{97 - e} + e\\<br />
b - \frac da &= (19 - e)^2 = (97 - e)^2\\<br />
19 - e &= \pm (97 - e)<br />
\end{align*}</cmath><br />
<br />
Clearly we can discard the positive root, so <math>e = 58</math>.<br />
<br />
=== Solution 3 ===<br />
<!-- some linear algebra --><br />
We first note (as before) that the number not in the range of<br />
<cmath> f(x) = \frac{ax+b}{cx+ d} = \frac{a}{c} + \frac{b - ad/c}{cx+d} </cmath><br />
is <math>a/c</math>, as <math>\frac{b-ad/c}{cx+d}</math> is evidently never 0 (otherwise, <math>f</math><br />
would be a constant function, violating the condition <math>f(19) \neq f(97)</math>).<br />
<br />
We may represent the real number <math>x/y</math> as<br />
<math>\begin{pmatrix}x \\ y\end{pmatrix}</math>, with two such [[vector|column vectors]]<br />
considered equivalent if they are scalar multiples of each other. Similarly,<br />
we can represent a function <math>F(x) = \frac{Ax + B}{Cx + D}</math> as a matrix<br />
<math>\begin{pmatrix} A & B\\ C& D \end{pmatrix}</math>. Function composition and<br />
evaluation then become matrix multiplication.<br />
<br />
Now in general,<br />
<cmath> f^{-1} = \begin{pmatrix} a & b\\ c&d \end{pmatrix}^{-1} =<br />
\frac{1}{\det(f)} \begin{pmatrix} d & -b \\ -c & a \end{pmatrix} .</cmath><br />
In our problem <math>f^2(x) = x</math>. It follows that<br />
<cmath> \begin{pmatrix} a & b \\ c& d \end{pmatrix} = K<br />
\begin{pmatrix} d & -b \\ -c & a \end{pmatrix} , </cmath><br />
for some nonzero real <math>K</math>. Since<br />
<cmath> \frac{a}{d} = \frac{b}{-b} = K, </cmath><br />
it follows that <math>a = -d</math>. (In fact, this condition condition is equivalent<br />
to the condition that <math>f(f(x)) = x</math> for all <math>x</math> in the domain of <math>f</math>.)<br />
<br />
We next note that the function<br />
<cmath> g(x) = x - f(x) = \frac{c x^2 + (d-a) x - b}{cx + d} </cmath><br />
evaluates to 0 when <math>x</math> equals 19 and 97. Therefore<br />
<cmath> \frac{c x^2 + (d-a) x - b}{cx+d} = g(x) = \frac{c(x-19)(x-97)}{cx+d}. </cmath><br />
Thus <math>-19 - 97 = \frac{d-a}{c} = -\frac{2a}{c}</math>, so <math>a/c = (19+97)/2 = 58</math>,<br />
our answer.<br />
<br />
=== Solution 4 ===<br />
Any number that is not in the domain of the inverse of <math>f(x)</math> cannot be in the range of <math>f(x)</math>. Starting with <math>f(x) = \frac{ax+b}{cx+d}</math>, we rearrange some things to get <math>x = \frac{b-f(x)d}{f(x)c-a}</math>. Clearly, <math>\frac{a}{c}</math> is the number that is outside the range of <math>f(x)</math>.<br />
<br />
<br />
Since we are given <math>f(f(x))=x</math>, we have that <cmath>x = \frac{a\frac{ax+b}{cx+d}+b}{c\frac{ax+b}{cx+d}+d} = \frac{a^2x +ab+bcx+bd}{acx+bc+cdx+d^2} = \frac{x(bc+a^2)+b(a+d)}{cx(a+d)+(bc+d^2)}</cmath><br />
<cmath>cx^2(a+d)+x(bc+d^2) = x(bc+a^2) + b(a+d)</cmath><br />
All the quadratic terms, linear terms, and constant terms must be equal on both sides for this to be a true statement so we have that <math>a = -d</math>.<br />
<br />
This solution follows in the same manner as the last paragraph of the first solution.<br />
<br />
=== Solution 5 ===<br />
Since <math>f(f(x))</math> is <math>x</math>, it must be symmetric across the line <math>y=x</math>. Also, since <math>f(19)=19</math>, it must touch the line <math>y=x</math> at <math>(19,19)</math> and <math>(97,97)</math>. <math>f</math> a hyperbola that is a scaled and transformed version of <math>y=\frac{1}{x}</math>. Write <math>f(x)= \frac{ax+b}{cx+d}</math> as <math>\frac{y}{cx+d}+z</math>, and z is our desired answer <math>\frac{a}{c}</math>. Take the basic hyperbola, <math>y=\frac{1}{x}</math>. The distance between points <math>(1,1)</math> and <math>(-1,-1)</math> is <math>2\sqrt{2}</math>, while the distance between <math>(19,19)</math> and <math>(97,97)</math> is <math>78\sqrt{2}</math>, so it is <math>y=\frac{1}{x}</math> scaled by a factor of <math>39</math>. Then, we will need to shift it from <math>(-39,-39)</math> to <math>(19,19)</math>, shifting up by <math>58</math>, or <math>z</math>, so our answer is <math>\boxed{58}</math>. Note that shifting the <math>x</math> does not require any change from <math>z</math>; it changes the denominator of the part <math>\frac{1}{x-k}</math>.<br />
<br />
=== Solution 6 (Short) ===<br />
<br />
From <math>f(f(x))=x</math>, it is obvious that <math>\frac{-d}{c}</math> is the value not in the range. First notice that since <math>f(0)=\frac{b}{d}</math>, <math>f(\frac{b}{d})=0</math> which means <math>a(\frac{b}{d})+b=0</math> so <math>a=-d</math>. Using <math>f(19)=19</math>, we have that <math>b=361c+38d</math>; on <math>f(97)=97</math> we obtain <math>b=9409c+194d</math>. Solving for <math>d</math> in terms of <math>c</math> leads us to <math>d=-58c</math>, so the answer is <math>\boxed{058}</math>. <br />
- solution by mathleticguyyy<br />
<br />
=== Solution 7===<br />
Begin by finding the inverse function of <math>f(x)</math>, which turns out to be <math>f^{-1}(x)=\frac{19d-b}{a-19c}</math>. Since <math>f(f(x))=x</math>, <math>f(x)=f^{-1}(x)</math>, so substituting 19 and 97 yields the system, <math>\begin{array}{lcl} \frac{19a+b}{19c+d} & = & \frac{19d-b}{a-19c} \\ \frac{97a+b}{97c+d} & = & \frac{97d-b}{a-97c} \end{array}</math>, and after multiplying each equation out and subtracting equation 1 from 2, and after simplifying, you will get <math>116c=a-d</math>. Coincidentally, then <math>116c+d=a</math>, which is familiar because <math>f(116)=\frac{116a+b}{116c+d}</math>, and since <math>116c+d=a</math>, <math>f(116)=\frac{116a+b}{a}</math>. Also, <math>f(f(116))=\frac{a(\frac{116a+b}{a})+b}{c(\frac{116a+b}{a})+d}=116</math>, due to <math>f(f(x))=x</math>. This simplifies to <math>\frac{116a+2b}{c(\frac{116a+b}{a})+d}=116</math>, <math>116a+2b=116(c(\frac{116a+b}{a})+d)</math>, <math>116a+2b=116(c(116+\frac{b}{a})+d)</math>, <math>116a+2b=116c(116+\frac{b}{a})+116d</math>, and substituting <math>116c+d=a</math> and simplifying, you get <math>2b=116c(\frac{b}{a})</math>, then <math>\frac{a}{c}=58</math>. Looking at <math>116c=a-d</math> one more time, we get <math>116=\frac{a}{c}+\frac{-d}{c}</math>, and substituting, we get <math>\frac{-d}{c}=\boxed{58}</math>, and we are done.<br />
<br />
=== Solution 8 (shorter than solution 6) ===<br />
Because there are no other special numbers other than <math>19</math> and <math>97</math>, take the average to get <math>\boxed{58}</math>. (Note I solved this problem the solution one way but noticed this and this probably generalizes to all <math>f(x)=x, f(y)=y</math> questions like these)<br />
<br />
== See also ==<br />
{{AIME box|year=1997|num-b=11|num-a=13}}<br />
<br />
[[Category:Intermediate Algebra Problems]]<br />
{{MAA Notice}}</div>Kkdhttps://artofproblemsolving.com/wiki/index.php?title=1997_AIME_Problems/Problem_12&diff=1312281997 AIME Problems/Problem 122020-08-09T16:29:41Z<p>Kkd: /* Solution 8 (shorter than solution 6) */</p>
<hr />
<div>== Problem ==<br />
The [[function]] <math>f</math> defined by <math>f(x)= \frac{ax+b}{cx+d}</math>, where <math>a</math>,<math>b</math>,<math>c</math> and <math>d</math> are nonzero real numbers, has the properties <math>f(19)=19</math>, <math>f(97)=97</math> and <math>f(f(x))=x</math> for all values except <math>\frac{-d}{c}</math>. Find the unique number that is not in the range of <math>f</math>.<br />
<br />
__TOC__<br />
== Solution ==<br />
=== Solution 1 ===<br />
First, we use the fact that <math>f(f(x)) = x</math> for all <math>x</math> in the domain. Substituting the function definition, we have <math>\frac {a\frac {ax + b}{cx + d} + b}{c\frac {ax + b}{cx + d} + d} = x</math>, which reduces to<br />
<cmath>\frac {(a^2 + bc)x + b(a + d)}{c(a + d)x + (bc + d^2)} =\frac {px + q}{rx + s} = x. </cmath><br />
In order for this fraction to reduce to <math>x</math>, we must have <math>q = r = 0</math> and <math>p = s\not = 0</math>. From <math>c(a + d) = b(a + d) = 0</math>, we get <math>a = - d</math> or <math>b = c = 0</math>. The second cannot be true, since we are given that <math>a,b,c,d</math> are nonzero. This means <math>a = - d</math>, so <math>f(x) = \frac {ax + b}{cx - a}</math>.<br />
<br />
The only value that is not in the range of this function is <math>\frac {a}{c}</math>. To find <math>\frac {a}{c}</math>, we use the two values of the function given to us. We get <math>2(97)a + b = 97^2c</math> and <math>2(19)a + b = 19^2c</math>. Subtracting the second equation from the first will eliminate <math>b</math>, and this results in <math>2(97 - 19)a = (97^2 - 19^2)c</math>, so<br />
<cmath>\frac {a}{c} = \frac {(97 - 19)(97 + 19)}{2(97 - 19)} = 58 . </cmath><br />
<br />
Alternatively, we could have found out that <math>a = -d</math> by using the fact that <math>f(f(-b/a))=-b/a</math>.<br />
<br />
=== Solution 2 ===<br />
First, we note that <math>e = \frac ac</math> is the horizontal [[Asymptote (Geometry)|asymptote]] of the function, and since this is a linear function over a linear function, the unique number not in the range of <math>f</math> will be <math>e</math>. <math>\frac{ax+b}{cx+d} = \frac{b-\frac{cd}{a}}{cx+d} + \frac{a}{c}</math>. [[Without loss of generality]], let <math>c=1</math>, so the function becomes <math>\frac{b- \frac{d}{a}}{x+d} + e</math>. <br />
<br />
(Considering <math>\infty</math> as a limit) By the given, <math>f(f(\infty)) = \infty</math>. <math>\lim_{x \rightarrow \infty} f(x) = e</math>, so <math>f(e) = \infty</math>. <math>f(x) \rightarrow \infty</math> as <math>x</math> reaches the vertical [[Asymptote (Geometry)|asymptote]], which is at <math>-\frac{d}{c} = -d</math>. Hence <math>e = -d</math>. Substituting the givens, we get <br />
<br />
<cmath>\begin{align*}<br />
19 &= \frac{b - \frac da}{19 - e} + e\\<br />
97 &= \frac{b - \frac da}{97 - e} + e\\<br />
b - \frac da &= (19 - e)^2 = (97 - e)^2\\<br />
19 - e &= \pm (97 - e)<br />
\end{align*}</cmath><br />
<br />
Clearly we can discard the positive root, so <math>e = 58</math>.<br />
<br />
=== Solution 3 ===<br />
<!-- some linear algebra --><br />
We first note (as before) that the number not in the range of<br />
<cmath> f(x) = \frac{ax+b}{cx+ d} = \frac{a}{c} + \frac{b - ad/c}{cx+d} </cmath><br />
is <math>a/c</math>, as <math>\frac{b-ad/c}{cx+d}</math> is evidently never 0 (otherwise, <math>f</math><br />
would be a constant function, violating the condition <math>f(19) \neq f(97)</math>).<br />
<br />
We may represent the real number <math>x/y</math> as<br />
<math>\begin{pmatrix}x \\ y\end{pmatrix}</math>, with two such [[vector|column vectors]]<br />
considered equivalent if they are scalar multiples of each other. Similarly,<br />
we can represent a function <math>F(x) = \frac{Ax + B}{Cx + D}</math> as a matrix<br />
<math>\begin{pmatrix} A & B\\ C& D \end{pmatrix}</math>. Function composition and<br />
evaluation then become matrix multiplication.<br />
<br />
Now in general,<br />
<cmath> f^{-1} = \begin{pmatrix} a & b\\ c&d \end{pmatrix}^{-1} =<br />
\frac{1}{\det(f)} \begin{pmatrix} d & -b \\ -c & a \end{pmatrix} .</cmath><br />
In our problem <math>f^2(x) = x</math>. It follows that<br />
<cmath> \begin{pmatrix} a & b \\ c& d \end{pmatrix} = K<br />
\begin{pmatrix} d & -b \\ -c & a \end{pmatrix} , </cmath><br />
for some nonzero real <math>K</math>. Since<br />
<cmath> \frac{a}{d} = \frac{b}{-b} = K, </cmath><br />
it follows that <math>a = -d</math>. (In fact, this condition condition is equivalent<br />
to the condition that <math>f(f(x)) = x</math> for all <math>x</math> in the domain of <math>f</math>.)<br />
<br />
We next note that the function<br />
<cmath> g(x) = x - f(x) = \frac{c x^2 + (d-a) x - b}{cx + d} </cmath><br />
evaluates to 0 when <math>x</math> equals 19 and 97. Therefore<br />
<cmath> \frac{c x^2 + (d-a) x - b}{cx+d} = g(x) = \frac{c(x-19)(x-97)}{cx+d}. </cmath><br />
Thus <math>-19 - 97 = \frac{d-a}{c} = -\frac{2a}{c}</math>, so <math>a/c = (19+97)/2 = 58</math>,<br />
our answer.<br />
<br />
=== Solution 4 ===<br />
Any number that is not in the domain of the inverse of <math>f(x)</math> cannot be in the range of <math>f(x)</math>. Starting with <math>f(x) = \frac{ax+b}{cx+d}</math>, we rearrange some things to get <math>x = \frac{b-f(x)d}{f(x)c-a}</math>. Clearly, <math>\frac{a}{c}</math> is the number that is outside the range of <math>f(x)</math>.<br />
<br />
<br />
Since we are given <math>f(f(x))=x</math>, we have that <cmath>x = \frac{a\frac{ax+b}{cx+d}+b}{c\frac{ax+b}{cx+d}+d} = \frac{a^2x +ab+bcx+bd}{acx+bc+cdx+d^2} = \frac{x(bc+a^2)+b(a+d)}{cx(a+d)+(bc+d^2)}</cmath><br />
<cmath>cx^2(a+d)+x(bc+d^2) = x(bc+a^2) + b(a+d)</cmath><br />
All the quadratic terms, linear terms, and constant terms must be equal on both sides for this to be a true statement so we have that <math>a = -d</math>.<br />
<br />
This solution follows in the same manner as the last paragraph of the first solution.<br />
<br />
=== Solution 5 ===<br />
Since <math>f(f(x))</math> is <math>x</math>, it must be symmetric across the line <math>y=x</math>. Also, since <math>f(19)=19</math>, it must touch the line <math>y=x</math> at <math>(19,19)</math> and <math>(97,97)</math>. <math>f</math> a hyperbola that is a scaled and transformed version of <math>y=\frac{1}{x}</math>. Write <math>f(x)= \frac{ax+b}{cx+d}</math> as <math>\frac{y}{cx+d}+z</math>, and z is our desired answer <math>\frac{a}{c}</math>. Take the basic hyperbola, <math>y=\frac{1}{x}</math>. The distance between points <math>(1,1)</math> and <math>(-1,-1)</math> is <math>2\sqrt{2}</math>, while the distance between <math>(19,19)</math> and <math>(97,97)</math> is <math>78\sqrt{2}</math>, so it is <math>y=\frac{1}{x}</math> scaled by a factor of <math>39</math>. Then, we will need to shift it from <math>(-39,-39)</math> to <math>(19,19)</math>, shifting up by <math>58</math>, or <math>z</math>, so our answer is <math>\boxed{58}</math>. Note that shifting the <math>x</math> does not require any change from <math>z</math>; it changes the denominator of the part <math>\frac{1}{x-k}</math>.<br />
<br />
=== Solution 6 (Shortest) ===<br />
<br />
From <math>f(f(x))=x</math>, it is obvious that <math>\frac{-d}{c}</math> is the value not in the range. First notice that since <math>f(0)=\frac{b}{d}</math>, <math>f(\frac{b}{d})=0</math> which means <math>a(\frac{b}{d})+b=0</math> so <math>a=-d</math>. Using <math>f(19)=19</math>, we have that <math>b=361c+38d</math>; on <math>f(97)=97</math> we obtain <math>b=9409c+194d</math>. Solving for <math>d</math> in terms of <math>c</math> leads us to <math>d=-58c</math>, so the answer is <math>\boxed{058}</math>. <br />
- solution by mathleticguyyy<br />
<br />
=== Solution 7===<br />
Begin by finding the inverse function of <math>f(x)</math>, which turns out to be <math>f^{-1}(x)=\frac{19d-b}{a-19c}</math>. Since <math>f(f(x))=x</math>, <math>f(x)=f^{-1}(x)</math>, so substituting 19 and 97 yields the system, <math>\begin{array}{lcl} \frac{19a+b}{19c+d} & = & \frac{19d-b}{a-19c} \\ \frac{97a+b}{97c+d} & = & \frac{97d-b}{a-97c} \end{array}</math>, and after multiplying each equation out and subtracting equation 1 from 2, and after simplifying, you will get <math>116c=a-d</math>. Coincidentally, then <math>116c+d=a</math>, which is familiar because <math>f(116)=\frac{116a+b}{116c+d}</math>, and since <math>116c+d=a</math>, <math>f(116)=\frac{116a+b}{a}</math>. Also, <math>f(f(116))=\frac{a(\frac{116a+b}{a})+b}{c(\frac{116a+b}{a})+d}=116</math>, due to <math>f(f(x))=x</math>. This simplifies to <math>\frac{116a+2b}{c(\frac{116a+b}{a})+d}=116</math>, <math>116a+2b=116(c(\frac{116a+b}{a})+d)</math>, <math>116a+2b=116(c(116+\frac{b}{a})+d)</math>, <math>116a+2b=116c(116+\frac{b}{a})+116d</math>, and substituting <math>116c+d=a</math> and simplifying, you get <math>2b=116c(\frac{b}{a})</math>, then <math>\frac{a}{c}=58</math>. Looking at <math>116c=a-d</math> one more time, we get <math>116=\frac{a}{c}+\frac{-d}{c}</math>, and substituting, we get <math>\frac{-d}{c}=\boxed{58}</math>, and we are done.<br />
<br />
=== Solution 8 (shorter than solution 6) ===<br />
Because there are no other special numbers other than <math>19</math> and <math>97</math>, take the average to get <math>\boxed{58}</math>. (Note I solved this problem the solution one way but noticed this and this probably generalizes to all <math>f(x)=x, f(y)=y</math> questions like these)<br />
<br />
== See also ==<br />
{{AIME box|year=1997|num-b=11|num-a=13}}<br />
<br />
[[Category:Intermediate Algebra Problems]]<br />
{{MAA Notice}}</div>Kkdhttps://artofproblemsolving.com/wiki/index.php?title=1981_IMO_Problems/Problem_2&diff=1267131981 IMO Problems/Problem 22020-06-27T15:18:26Z<p>Kkd: /* Solution 5 */</p>
<hr />
<div>== Problem ==<br />
<br />
Let <math>1 \le r \le n </math> and consider all subsets of <math>r </math> elements of the set <math> \{ 1, 2, \ldots , n \} </math>. Each of these subsets has a smallest member. Let <math>F(n,r) </math> denote the arithmetic mean of these smallest numbers; prove that<br />
<br />
<center><br />
<math><br />
F(n,r) = \frac{n+1}{r+1}.<br />
</math><br />
</center><br />
<br />
== Solutions ==<br />
<br />
=== Solution 1 ===<br />
<br />
Clearly, the sum of the desired least elements is <math> \sum_{k=1}^{n} k {n-k \choose r-1} = \sum_{k=1}^{n} {k \choose 1}{n-k \choose r-1} </math>, which we claim to be equal to <math>{n+1 \choose r+1} </math> by virtue of the following argument.<br />
<br />
Consider a binary string of length <math>n+1 </math> which contains <math>r+1 </math> 1s. For some value of <math>k</math> between 1 and <math>n</math>, inclusive, we say that the second 1 will occur in the <math>(k+1) </math>th place. Clearly, there are <math> {k \choose 1} </math> ways to arrange the bits coming before the second 1, and <math>{n-k \choose r-1} </math> ways to arrange the bits after the second 1. Our identity follows.<br />
<br />
Since the sum of the least elements of the sets is <math>{n+1 \choose r+1}</math>, the mean of the least elements is <math>\frac{{n+1 \choose r+1}}{{n \choose r}} = \frac{n+1}{r+1}</math>, Q.E.D.<br />
<br />
=== Solution 2 ===<br />
<br />
We proceed as in the previous solution, but we prove our identity using the following manipulations:<br />
<br />
<center><br />
<math><br />
\begin{matrix}\sum_{k=1}^{n}k{n-k \choose r-1 } &=&\sum_{k=1}^{n-(r-1)}{k}{n-k \choose r-1}\\<br />
&=& \sum_{i=1}^{n-(r-1)}\sum_{k=i}^{n-(r-1)}{n-k \choose r-1}\\<br />
&=&\sum_{i=1}^{n-(r-1)}{n-i+1 \choose r}\\<br />
&=&{n+1 \choose r+1}<br />
\end{matrix}<br />
</math><br />
</center><br />
<br />
Q.E.D.<br />
<br />
=== Solution 3 ===<br />
<br />
We proceed by strong induction.<br />
<br />
We define <math>F(k, k-1)</math> to be zero (the empty sum).<br />
<br />
We consider <math>r</math> to be fixed. The assertion obviously holds for <math>r = n</math>. We now assume the problem to hold for values of <math>n</math> less than or equal to <math>k</math>. By considering subsets containing <math>k+1</math> and not containing <math>k+1</math>, respectively, we conclude that<br />
<br />
<center><br />
<math><br />
F(k+1, r) = \frac{{k \choose r-1}F(k,r-1) + {k \choose r}F(k,r)}{{k+1 \choose r}} = 1 + \frac{k-r+1}{r+1} = \frac{k+2}{r+1}<br />
</math>.<br />
</center><br />
<br />
This completes our induction, Q.E.D.<br />
<br />
===Solution 4===<br />
<br />
Consider a bipartite graph <math>G</math> with bipartition <math>\{A,B\}</math>. The vertices in <math>A</math> are the <math>(r+1)</math>-element subsets of <math>\{0, \dots , n\}</math>, and the vertices in <math>B</math> are the <math>r</math>-element subsets of <math>\{1, \dots , n\}</math>, and we draw an edge <math>\overline{ab}</math> iff the subset <math>b \in B</math> may be obtained from <math>a \in A</math> by deleting the smallest element in <math>a</math>. <br />
<br />
Note that <br />
<br />
<center><br />
<math>|A|=\binom{n+1}{r+1}, |B|=\binom{n}{r}, |E(G)|=\binom{n+1}{r+1}=\frac{n+1}{r+1} \binom{n}{r}.</math><br />
</center> <br />
<br />
The degree of a vertex in <math>B</math> is the value of the least element of its corresponding subset. Hence <cmath>F(n,r)=\frac{1}{\binom{n}{r}} \sum_{v \in B} \deg (v)= \frac{n+1}{r+1}.</cmath><br />
<br />
===Solution 5===<br />
<br />
We will count how many times each element of the set <math>\{1, 2, \ldots, n\}</math> appear as the smallest element in a set, which will lead us to the result. <br />
<br />
To count how many times <math>1</math> appears as the smallest element of a subset, we need to choose an <math>r-1</math> element subset from the remaining <math>n - 1</math> numbers, as all of them are greater than <math>1.</math> There are simply <math>\dbinom{n - 1}{r - 1}</math> ways to do this. <br />
<br />
Similarly, to count how many times <math>2</math> appears as the smallest element, we need to choose an <math>r - 1</math> element subset from the remaining <math>n - 2</math> numbers greater than <math>2.</math> There are <math>\dbinom{n - 2}{r - 1}</math> ways to do this. <br />
<br />
As there are <math>\dbinom{n}{r}</math> subsets, and thus smallest elements, in total, it now becomes clear that we need to evaluate the sum <cmath>\frac{\binom{n - 1}{r - 1} + 2\binom{n - 2}{r - 1} + \cdots + (n - r + 1)\binom{r - 1}{r - 1}}{\binom{n}{r}}.</cmath> We can rearrange this sum as <cmath>\frac{\left(\binom{n - 1}{r - 1} + \binom{n - 2}{r - 1} + \cdots + \binom{r - 1}{r - 1}\right)+\left(\binom{n - 2}{r - 1} + \binom{n - 3}{r - 1} + \cdots + \binom{r - 1}{r - 1}\right)+\cdots+ \binom{r-1}{r-1}}{\binom{n}{r}}.</cmath> Using the Hockey Stick Identity on each of the smaller sums on the numerator gives us <cmath>\frac{\binom{n}{r} + \binom{n - 1}{r} + \binom{n-2}{r} + \cdots + \binom{r}{r}}{\binom{n}{r}}.</cmath> Using Hockey stick again gives us <cmath>\frac{\binom{n + 1}{r + 1}}{\binom{n}{r}},</cmath> which simplifies to <cmath>\frac{\frac{(n + 1)!}{(r + 1)!(n-r)!}}{\frac{n!}{r!(n-r)!}} = \left(\frac{(n + 1)!}{(r + 1)!(n - r)!}\right) \left(\frac{r!(n-r)!}{n!}\right) = \frac{n + 1}{r + 1},</cmath> as desired. <br />
<br />
Solution by Ilikeapos<br />
<br />
{{alternate solutions}}<br />
<br />
{{IMO box|num-b=1|num-a=3|year=1981}}<br />
<br />
[[Category:Olympiad Combinatorics Problems]]</div>Kkdhttps://artofproblemsolving.com/wiki/index.php?title=American_Scholastic_Mathematics_Association&diff=105812American Scholastic Mathematics Association2019-05-14T17:11:40Z<p>Kkd: </p>
<hr />
<div>The '''American Scholastic Mathematics Association''' (ASMA) hosts competitions for middle and high school students.<br />
<br />
== General Information and Rules==<br />
The American Scholastic Mathematics Association (ASMA) is a middle/high school team competition with the top eight scorers of each team counted towards the team's total. The test is 35 minutes long and assumes the use of a calculator. <br />
<br />
==Awards==<br />
Awards and certificates will be given to the top schools. The student with the highest score in each school will also receive a certificate<br />
== 2019-2020 Contest Dates ==<br />
<br />
Contest #1 - October 10, 2019<br />
Contest #2 - November 14 2019<br />
Contest #3 - December 12, 2019<br />
Contest #4 - January 9, 2020<br />
Contest #5 - February 13, 2020<br />
Contest #6 - March 12, 2020<br />
<br />
It features questions with probability, counting, arithmetic, algebra, and geometry. It is 35 minutes long and contains 7 questions.<br />
<br />
==Difficulty ==<br />
The difficulty of this math competition is similar to MOEMS (easier problems) and AMC 8 (harder problems)<br />
== Resources ==<br />
* [http://www.asan.com/asa/asma1.htm ASMA homepage]<br />
* [[Mathematics competition resources]]<br />
{{stub}}<br />
<br />
[[Category:Mathematics competitions]]</div>Kkd