Difference between revisions of "1964 AHSME Problems/Problem 16"

(Created page with "==Problem== Let <math>f(x)=x^2+3x+2</math> and let <math>S</math> be the set of integers <math>\{0, 1, 2, \dots , 25 \}</math>. The number of members <math>s</math> of <math...")
 
(Solution)
 
Line 15: Line 15:
  
 
Proof:
 
Proof:
If <math>f(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_0</math>, then <math>f(x+6) = a_n(x+6)^n + a_{n-1}(x-6)^{n-1} +...+ a_0</math>.  In the second equation, we can use the binomial expansion to expand every term, and then subtract off all terms that have a factor of <math>6^1</math> or higher, since subtracting a multiple of <math>6</math> will not change congruence <math>\pmod 6</math>.  This leaves <math>a_nx^n + a_{n-1}x^{n-1} + ... + a_0</math>, which is <math>f(x)</math>, so <math>f(x+6) \equiv f(x) \pmod 6</math>.
+
If <math>f(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_0</math>, then <math>f(x+6) = a_n(x+6)^n + a_{n-1}(x+6)^{n-1} +...+ a_0</math>.  In the second equation, we can use the binomial expansion to expand every term, and then subtract off all terms that have a factor of <math>6^1</math> or higher, since subtracting a multiple of <math>6</math> will not change congruence <math>\pmod 6</math>.  This leaves <math>a_nx^n + a_{n-1}x^{n-1} + ... + a_0</math>, which is <math>f(x)</math>, so <math>f(x+6) \equiv f(x) \pmod 6</math>.
  
 
So, we only need to test when <math>f(x)</math> has a remainder of <math>0</math> for <math>0, 1, 2, 3, 4, 5</math>.  The set of numbers <math>6, 7, 8, 9, 10, 11</math> will repeat remainders, as will all other sets.  The remainders are <math>2, 0, 0, 2, 0, 0</math>.
 
So, we only need to test when <math>f(x)</math> has a remainder of <math>0</math> for <math>0, 1, 2, 3, 4, 5</math>.  The set of numbers <math>6, 7, 8, 9, 10, 11</math> will repeat remainders, as will all other sets.  The remainders are <math>2, 0, 0, 2, 0, 0</math>.

Latest revision as of 20:31, 23 July 2019

Problem

Let $f(x)=x^2+3x+2$ and let $S$ be the set of integers $\{0, 1, 2, \dots , 25 \}$. The number of members $s$ of $S$ such that $f(s)$ has remainder zero when divided by $6$ is:

$\textbf{(A)}\ 25\qquad \textbf{(B)}\ 22\qquad \textbf{(C)}\ 21\qquad \textbf{(D)}\ 18 \qquad \textbf{(E)}\ 17$

Solution

Note that for all polynomials $f(x)$, $f(x + 6) \equiv f(x) \pmod 6$.

Proof: If $f(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_0$, then $f(x+6) = a_n(x+6)^n + a_{n-1}(x+6)^{n-1} +...+ a_0$. In the second equation, we can use the binomial expansion to expand every term, and then subtract off all terms that have a factor of $6^1$ or higher, since subtracting a multiple of $6$ will not change congruence $\pmod 6$. This leaves $a_nx^n + a_{n-1}x^{n-1} + ... + a_0$, which is $f(x)$, so $f(x+6) \equiv f(x) \pmod 6$.

So, we only need to test when $f(x)$ has a remainder of $0$ for $0, 1, 2, 3, 4, 5$. The set of numbers $6, 7, 8, 9, 10, 11$ will repeat remainders, as will all other sets. The remainders are $2, 0, 0, 2, 0, 0$.

This means for $s=1, 2, 4, 5$, $f(s)$ is divisible by $6$. Since $f(1)$ is divisible, so is $f(s)$ for $s=7, 13, 19, 25$, which is $5$ values of $s$ that work. Since $f(2)$ is divisible, so is $f(s)$ for $s=8, 14, 20$, which is $4$ more values of $s$ that work. The values of $s=4, 5$ will also generate $4$ solutions each, just like $f(2)$. This is a total of $17$ values of $s$, for an answer of $\boxed{\textbf{(E)}}$

See Also

1964 AHSC (ProblemsAnswer KeyResources)
Preceded by
Problem 15
Followed by
Problem 17
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 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
All AHSME Problems and Solutions

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

Invalid username
Login to AoPS