Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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 2)
 
(12 intermediate revisions by 3 users not shown)
Line 10: Line 10:
 
\textbf{(E)}\ 17  </math>
 
\textbf{(E)}\ 17  </math>
  
−
==Solution==
+
==Solution <math>1</math>==
  
 
Note that for all polynomials <math>f(x)</math>, <math>f(x + 6) \equiv f(x) \pmod 6</math>.   
 
Note that for all polynomials <math>f(x)</math>, <math>f(x + 6) \equiv f(x) \pmod 6</math>.   
  
 
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>.
  
 
This means for <math>s=1, 2, 4, 5</math>, <math>f(s)</math> is divisible by <math>6</math>.  Since <math>f(1)</math> is divisible, so is <math>f(s)</math> for <math>s=7, 13, 19, 25</math>, which is <math>5</math> values of <math>s</math> that work.  Since <math>f(2)</math> is divisible, so is <math>f(s)</math> for <math>s=8, 14, 20</math>, which is <math>4</math> more values of <math>s</math> that work.  The values of <math>s=4, 5</math> will also generate <math>4</math> solutions each, just like <math>f(2)</math>.  This is a total of <math>17</math> values of <math>s</math>, for an answer of <math>\boxed{\textbf{(E)}}</math>
 
This means for <math>s=1, 2, 4, 5</math>, <math>f(s)</math> is divisible by <math>6</math>.  Since <math>f(1)</math> is divisible, so is <math>f(s)</math> for <math>s=7, 13, 19, 25</math>, which is <math>5</math> values of <math>s</math> that work.  Since <math>f(2)</math> is divisible, so is <math>f(s)</math> for <math>s=8, 14, 20</math>, which is <math>4</math> more values of <math>s</math> that work.  The values of <math>s=4, 5</math> will also generate <math>4</math> solutions each, just like <math>f(2)</math>.  This is a total of <math>17</math> values of <math>s</math>, for an answer of <math>\boxed{\textbf{(E)}}</math>
 +
 +
==Solution 2==
 +
 +
*We know that,
 +
<math>f(x)</math> = <math>x^2</math> +<math>3x</math> + <math>2</math> is <math>0</math> congruent modulo 6 that implies <math>x+1</math> or/and <math>x+2</math> is <math>0</math> congruent modulo <math>6</math>.The numbers are of the form <math>6k+5</math> and <math>6k+4</math> for some integer <math>k</math> and due to restrictions of number of elements in the set <math>S</math> we get the inequality <math>k<4</math>.Then we calculate the possible combinations to get  <math>17</math> as answer i.e. option <math>\boxed{\textbf{(E)}}</math>.
 +
                                                                                                                                                <math>Solution</math> <math>by</math> <math>GEOMETRY-WIZARD</math>
 +
 +
THE above solution does not give you the answer there are more cases,
 +
<math>f(x)</math> = <math>x^2</math> + <math>3x</math> + <math>2</math> is congruent to <math>0</math> modulo 6 this has 4 cases,
 +
When,
 +
* <math>x+1</math> ≡ <math>0</math>(mod 6)
 +
* <math>x+2</math> ≡ <math>0</math>(mod 6)
 +
* <math>x+1</math> ≡ <math>2</math>(mod 6), <math>x+2</math> ≡ <math>3</math> (mod 6)
 +
* <math>x+1</math> ≡ <math>0</math> (mod 6), then <math>x+2</math> ≡ <math>4</math> (mod 6), which satisfies.
 +
Therefore by solvin' these cases we get 17.
 +
 +
<math>EDITED</math> <math>by</math> <math>RNVAA</math>
  
 
==See Also==
 
==See Also==

Latest revision as of 10:58, 30 August 2024

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 $1$

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)}}$

Solution 2

  • We know that,

$f(x)$ = $x^2$ +$3x$ + $2$ is $0$ congruent modulo 6 that implies $x+1$ or/and $x+2$ is $0$ congruent modulo $6$.The numbers are of the form $6k+5$ and $6k+4$ for some integer $k$ and due to restrictions of number of elements in the set $S$ we get the inequality $k<4$.Then we calculate the possible combinations to get $17$ as answer i.e. option $\boxed{\textbf{(E)}}$. 

                                                                                                                                               $Solution$ $by$ $GEOMETRY-WIZARD$

THE above solution does not give you the answer there are more cases, $f(x)$ = $x^2$ + $3x$ + $2$ is congruent to $0$ modulo 6 this has 4 cases, When,

  • $x+1$ ≡ $0$(mod 6)
  • $x+2$ ≡ $0$(mod 6)
  • $x+1$ ≡ $2$(mod 6), $x+2$ ≡ $3$ (mod 6)
  • $x+1$ ≡ $0$ (mod 6), then $x+2$ ≡ $4$ (mod 6), which satisfies.

Therefore by solvin' these cases we get 17. 

$EDITED$ $by$ $RNVAA$

See Also

1964 AHSC (Problems • Answer Key • Resources)
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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1964_AHSME_Problems/Problem_16&oldid=226037"