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 "1998 AJHSME Problems/Problem 24"
m (→‎Problem)
 
(11 intermediate revisions by 8 users not shown)
Line 1: Line 1:
−
A rectangular board of 8 columns has squared numbered beginning in the upper left corner and moving left to right so row one is numbered 1 through 8, row two is 9 through 16, and so on. A student shades square 1, then skips one square and shades square 3, skips two squares and shades square 6, skips 3 squares and shades square 10, and continues in this way until there is at least one shaded square in each column. What is the number of the shaded square that first achieves this result?
+
==Problem==
 +
A rectangular board of 8 columns has squares numbered beginning in the upper left corner and moving left to right so row one is numbered 1 through 8, row two is 9 through 16, and so on. A student shades square 1, then skips one square and shades square 3, skips two squares and shades square 6, skips 3 squares and shades square 10, and continues in this way until there is at least one shaded square in each column. What is the number of the shaded square that first achieves this result?
  
−
[[File:[asy]
+
<asy>
 
unitsize(20);
 
unitsize(20);
 
for(int a = 0; a < 10; ++a)
 
for(int a = 0; a < 10; ++a)
Line 25: Line 26:
 
fill((1,7)--(2,7)--(2,8)--(1,8)--cycle,black);
 
fill((1,7)--(2,7)--(2,8)--(1,8)--cycle,black);
 
fill((6,7)--(7,7)--(7,8)--(6,8)--cycle,black);
 
fill((6,7)--(7,7)--(7,8)--(6,8)--cycle,black);
−
label("<math>2</math>",(1.5,8.2),N);
+
label("$2$",(1.5,8.2),N);
−
label("<math>4</math>",(3.5,8.2),N);
+
label("$4$",(3.5,8.2),N);
−
label("<math>5</math>",(4.5,8.2),N);
+
label("$5$",(4.5,8.2),N);
−
label("<math>7</math>",(6.5,8.2),N);
+
label("$7$",(6.5,8.2),N);
−
label("<math>8</math>",(7.5,8.2),N);
+
label("$8$",(7.5,8.2),N);
−
label("<math>9</math>",(0.5,7.2),N);
+
label("$9$",(0.5,7.2),N);
−
label("<math>11</math>",(2.5,7.2),N);
+
label("$11$",(2.5,7.2),N);
−
label("<math>12</math>",(3.5,7.2),N);
+
label("$12$",(3.5,7.2),N);
−
label("<math>13</math>",(4.5,7.2),N);
+
label("$13$",(4.5,7.2),N);
−
label("<math>14</math>",(5.5,7.2),N);
+
label("$14$",(5.5,7.2),N);
−
label("<math>16</math>",(7.5,7.2),N);[/asy]]]
+
label("$16$",(7.5,7.2),N);
 +
</asy>
  
 
<math> \text{(A)}\ 36\qquad\text{(B)}\ 64\qquad\text{(C)}\ 78\qquad\text{(D)}\ 91\qquad\text{(E)}\ 120 </math>
 
<math> \text{(A)}\ 36\qquad\text{(B)}\ 64\qquad\text{(C)}\ 78\qquad\text{(D)}\ 91\qquad\text{(E)}\ 120 </math>
 +
 +
==Solution 1==
 +
 +
The numbers that are shaded are the triangular numbers, which are numbers in the form <math>\frac{(n)(n+1)}{2}</math> for positive integers.  They can also be generated by starting with <math>1</math>, and adding <math>1, 2, 3, 4...</math> as in the description of the problem.
 +
 +
Squares that have the same remainder after being divided by <math>8</math> will be in the same column.  Thus, we want to find when the last remainder, from <math>0</math> to <math>7</math>, is found.
 +
 +
So, instead of adding <math>1, 2, 3, 4, 5, 6, 7, 8, 9, 10...</math>, we can effectively either add <math>1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3...</math> or subtract <math>7, 6, 5, 4, 3, 2, 1, 0, 7, 6, 5...</math> if we are only concerned about remainders when divided by <math>8</math>.  We will pick the number that keeps the terms on the list between <math>1</math> and <math>8</math>.  We get:
 +
 +
<math>1</math>
 +
 +
<math>1 + 2 = 3</math>
 +
 +
<math>3 + 3 = 6</math>
 +
 +
<math>6 - 4 = 2</math>
 +
 +
<math>2 + 5 = 7</math>
 +
 +
<math>7 - 2 = 5</math>
 +
 +
<math>5 - 1 = 4</math>
 +
 +
<math>4 + 0 = 4</math>
 +
 +
<math>4 + 1 = 5</math>
 +
 +
<math>5 + 2 = 7</math>
 +
 +
<math>7 - 5 = 2</math>
 +
 +
<math>2 + 4 = 6</math>
 +
 +
<math>6 - 3 = 3</math>
 +
 +
<math>3 - 2 = 1</math>
 +
 +
<math>1 - 1 = 0</math>
 +
 +
Finally, a term with <math>0</math> is found, and checking, all numbers <math>1</math> through <math>7</math> are also on the right side of the list.  This means the last term in our sequence is the first time that column <math>8</math> is shaded.  There are <math>15</math> terms in the sequence, leading to an answer of <math>\frac{15\cdot 16}{2} = 120</math>, which is choice <math>\boxed{E}</math>.
 +
 +
==Solution 2==
 +
 +
Note that the triangular numbers up to <math>120</math> are <math>1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120</math>.  When you divide each of those numbers by <math>8</math>, all remainders must be present.  We first search for number(s) that are evenly divisible by <math>8</math>; if two such numbers exist, we search for numbers that leave a remainder of <math>1</math>, etc.
 +
 +
Quickly scanning the list, only <math>6, 10, 28, 36, 66, 78</math> and <math>120</math> are even.  That smaller list doesn't have any multiples of <math>8</math> until it hits <math>120</math>.  So <math>\boxed{120, E}</math> must be the answer.
 +
 +
==Solution 3==
 +
 +
The numbers shaded are triangular numbers of the form <math>\frac{(n)(n+1)}{2}</math>.  For this number to be divisible by <math>8</math>, the numerator must be divisible by <math>16</math>.  Since only one of <math>n</math> and <math>n+1</math> can be even, only one of them can have factors of <math>2</math>.  Therefore, the first time the whole expression is divisible by <math>8</math> is when either <math>n+1=16</math> or when <math>n=16</math>.  This gives <math>n=15</math> as the first time <math>\frac{n(n+1)}{2}</math> is divisible by <math>8</math>, which gives <math>120</math>.  No other triangular number lower than that is divisible by <math>8</math>, and thus the <math>8^{th}</math> column on the checkerboard won't be filled until then.  That gives <math>\boxed{E}</math> as the right answer.
 +
 +
 +
== See also ==
 +
{{AJHSME box|year=1998|num-b=23|num-a=25}}
 +
* [[AJHSME]]
 +
* [[AJHSME Problems and Solutions]]
 +
* [[Mathematics competition resources]]
 +
{{MAA Notice}}

Latest revision as of 14:35, 29 May 2021

Problem

A rectangular board of 8 columns has squares numbered beginning in the upper left corner and moving left to right so row one is numbered 1 through 8, row two is 9 through 16, and so on. A student shades square 1, then skips one square and shades square 3, skips two squares and shades square 6, skips 3 squares and shades square 10, and continues in this way until there is at least one shaded square in each column. What is the number of the shaded square that first achieves this result?

[asy] unitsize(20); for(int a = 0; a < 10; ++a) { draw((0,a)--(8,a)); } for (int b = 0; b < 9; ++b) { draw((b,0)--(b,9)); } draw((0,0)--(0,-.5)); draw((1,0)--(1,-1.5)); draw((.5,-1)--(1.5,-1)); draw((2,0)--(2,-.5)); draw((4,0)--(4,-.5)); draw((5,0)--(5,-1.5)); draw((4.5,-1)--(5.5,-1)); draw((6,0)--(6,-.5)); draw((8,0)--(8,-.5)); fill((0,8)--(1,8)--(1,9)--(0,9)--cycle,black); fill((2,8)--(3,8)--(3,9)--(2,9)--cycle,black); fill((5,8)--(6,8)--(6,9)--(5,9)--cycle,black); fill((1,7)--(2,7)--(2,8)--(1,8)--cycle,black); fill((6,7)--(7,7)--(7,8)--(6,8)--cycle,black); label("$2$",(1.5,8.2),N); label("$4$",(3.5,8.2),N); label("$5$",(4.5,8.2),N); label("$7$",(6.5,8.2),N); label("$8$",(7.5,8.2),N); label("$9$",(0.5,7.2),N); label("$11$",(2.5,7.2),N); label("$12$",(3.5,7.2),N); label("$13$",(4.5,7.2),N); label("$14$",(5.5,7.2),N); label("$16$",(7.5,7.2),N); [/asy]

$\text{(A)}\ 36\qquad\text{(B)}\ 64\qquad\text{(C)}\ 78\qquad\text{(D)}\ 91\qquad\text{(E)}\ 120$

Solution 1

The numbers that are shaded are the triangular numbers, which are numbers in the form $\frac{(n)(n+1)}{2}$ for positive integers. They can also be generated by starting with $1$, and adding $1, 2, 3, 4...$ as in the description of the problem.

Squares that have the same remainder after being divided by $8$ will be in the same column. Thus, we want to find when the last remainder, from $0$ to $7$, is found.

So, instead of adding $1, 2, 3, 4, 5, 6, 7, 8, 9, 10...$, we can effectively either add $1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3...$ or subtract $7, 6, 5, 4, 3, 2, 1, 0, 7, 6, 5...$ if we are only concerned about remainders when divided by $8$. We will pick the number that keeps the terms on the list between $1$ and $8$. We get:

$1$

$1 + 2 = 3$

$3 + 3 = 6$

$6 - 4 = 2$

$2 + 5 = 7$

$7 - 2 = 5$

$5 - 1 = 4$

$4 + 0 = 4$

$4 + 1 = 5$

$5 + 2 = 7$

$7 - 5 = 2$

$2 + 4 = 6$

$6 - 3 = 3$

$3 - 2 = 1$

$1 - 1 = 0$

Finally, a term with $0$ is found, and checking, all numbers $1$ through $7$ are also on the right side of the list. This means the last term in our sequence is the first time that column $8$ is shaded. There are $15$ terms in the sequence, leading to an answer of $\frac{15\cdot 16}{2} = 120$, which is choice $\boxed{E}$.

Solution 2

Note that the triangular numbers up to $120$ are $1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120$. When you divide each of those numbers by $8$, all remainders must be present. We first search for number(s) that are evenly divisible by $8$; if two such numbers exist, we search for numbers that leave a remainder of $1$, etc.

Quickly scanning the list, only $6, 10, 28, 36, 66, 78$ and $120$ are even. That smaller list doesn't have any multiples of $8$ until it hits $120$. So $\boxed{120, E}$ must be the answer.

Solution 3

The numbers shaded are triangular numbers of the form $\frac{(n)(n+1)}{2}$. For this number to be divisible by $8$, the numerator must be divisible by $16$. Since only one of $n$ and $n+1$ can be even, only one of them can have factors of $2$. Therefore, the first time the whole expression is divisible by $8$ is when either $n+1=16$ or when $n=16$. This gives $n=15$ as the first time $\frac{n(n+1)}{2}$ is divisible by $8$, which gives $120$. No other triangular number lower than that is divisible by $8$, and thus the $8^{th}$ column on the checkerboard won't be filled until then. That gives $\boxed{E}$ as the right answer.


See also

1998 AJHSME (Problems • Answer Key • Resources)
Preceded by
Problem 23 		Followed by
Problem 25
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 AJHSME/AMC 8 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=1998_AJHSME_Problems/Problem_24&oldid=154432"