Difference between revisions of "2005 AIME I Problems/Problem 4"

(alternative solution, box)
(Solution 5)
(20 intermediate revisions by 9 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
 
The director of a marching band wishes to place the members into a formation that includes all of them and has no unfilled positions. If they are arranged in a square formation, there are 5 members left over. The director realizes that if he arranges the group in a formation with 7 more rows than columns, there are no members left over. Find the maximum number of members this band can have.
 
The director of a marching band wishes to place the members into a formation that includes all of them and has no unfilled positions. If they are arranged in a square formation, there are 5 members left over. The director realizes that if he arranges the group in a formation with 7 more rows than columns, there are no members left over. Find the maximum number of members this band can have.
 +
__TOC__
  
__TOC__
 
 
== Solution ==
 
== Solution ==
 
=== Solution 1 ===
 
=== Solution 1 ===
If <math>n > 14</math> then <math>n^2 + 6n + 14 < n^2 + 7n < n^2 + 8n + 21</math> and so <math>(n + 3)^2 + 5 < n(n + 7) < (n + 4)^2 + 5</math>.  If <math>n</math> is an [[integer]] there are no numbers which are 5 more than a [[perfect square]] strictly between <math>(n + 3)^2 + 5</math> and <math>(n + 4)^2 + 5</math>.  Thus, if the number of columns is <math>n</math>, the number of students is <math>n(n + 7)</math> which must be 5 more than a perfect square, so <math>n \leq 14</math>.  In fact, when <math>n = 14</math> we have <math>n(n + 7) = 14\cdot 21 = 294 = 17^2 + 5</math>, so this number works and no larger number can.  Thus, the answer is 294.
+
If <math>n > 14</math> then <math>n^2 + 6n + 14 < n^2 + 7n < n^2 + 8n + 21</math> and so <math>(n + 3)^2 + 5 < n(n + 7) < (n + 4)^2 + 5</math>.  If <math>n</math> is an [[integer]] there are no numbers which are 5 more than a [[perfect square]] strictly between <math>(n + 3)^2 + 5</math> and <math>(n + 4)^2 + 5</math>.  Thus, if the number of columns is <math>n</math>, the number of students is <math>n(n + 7)</math> which must be 5 more than a perfect square, so <math>n \leq 14</math>.  In fact, when <math>n = 14</math> we have <math>n(n + 7) = 14\cdot 21 = 294 = 17^2 + 5</math>, so this number works and no larger number can.  Thus, the answer is <math>\boxed{294}</math>.
  
 
=== Solution 2 ===
 
=== Solution 2 ===
Define the number of rows/columns of the square formation as <math>s</math>, and the number of rows of the rectangular formation <math>r</math> (so there are <math>r - 7</math> columns). Thus, <math>s^2 + 5 = r(r-7) \Longrightarrow r^2 - 7r - s^2 - 5 = 0</math>. The [[quadratic formula]] yields <math>r = \frac{7 \pm \sqrt{49 - 4(1)(-s - 5)}}{2} = \frac{7 \pm \sqrt{4s^2 + 69}}{2}</math>. <math>\displaystyle \sqrt{4s^2 + 69}</math> must be an [[integer]], say <math>x</math>. Then <math>4s^2 + 69 = x^2</math> and <math>(x + 2s)(x - 2s) = 69</math>. The factors of <math>69</math> are <math>(1,69), (3,23)</math>; <math>x</math> is maximized for the first case. Thus, <math>x = \frac{69 + 1}{2} = 35</math>, and <math>r = \frac{7 \pm 35}{2} = 21, -14</math>. The latter obviously can be discarded, so there are <math>21</math> rows and <math>21 - 7 = 14</math> columns, making the answer <math>294</math>.
+
Define the number of rows/columns of the square formation as <math>s</math>, and the number of rows of the rectangular formation <math>r</math> (so there are <math>r - 7</math> columns). Thus, <math>s^2 + 5 = r(r-7) \Longrightarrow r^2 - 7r - s^2 - 5 = 0</math>. The [[quadratic formula]] yields <math>r = \frac{7 \pm \sqrt{49 - 4(1)(-s^2 - 5)}}{2} = \frac{7 \pm \sqrt{4s^2 + 69}}{2}</math>. <math>\sqrt{4s^2 + 69}</math> must be an [[integer]], say <math>x</math>. Then <math>4s^2 + 69 = x^2</math> and <math>(x + 2s)(x - 2s) = 69</math>. The factors of <math>69</math> are <math>(1,69), (3,23)</math>; <math>x</math> is maximized for the first case. Thus, <math>x = \frac{69 + 1}{2} = 35</math>, and <math>r = \frac{7 \pm 35}{2} = 21, -14</math>. The latter obviously can be discarded, so there are <math>21</math> rows and <math>21 - 7 = 14</math> columns, making the answer <math>294</math>.
 +
 
 +
=== Solution 3 ===
 +
The number of members is <math>m^2+5=n(n+7)</math> for some <math>n</math> and <math>m</math>. Multiply both sides by <math>4</math> and [[completing the square|complete the square]] to get <math>4m^2+69=(2n+7)^2</math>. Thus, we have <math>69=((2n+7)+2m)((2n+7)-2m)</math>. Since we want to maximize <math>n</math>, set the first factor equal to <math>69</math> and the second equal to <math>1</math>. Solving gives <math>n=14</math>, so the answer is <math>14\cdot21=294</math>.
 +
 
 +
=== Solution 4 ===
 +
Partially completing the square
 +
 
 +
Geometrically: Split up the formation of <math>n + 7</math> rows and <math>n</math> columns into a square of <math>n</math> rows and <math>n</math> columns and a separate rectangle of the dimensions <math>7</math> rows by <math>n</math> columns. We want to take the rows from the rectangle and add them to the square to get another square and <math>5</math> left over. If we attach exactly <math>2</math> rows on the top and exactly <math>2</math> rows on the side of the <math>n</math> x <math>n</math> square, then we have an <math>(n + 2)</math> x <math>(n + 2)</math> square that's missing a <math>2</math> x <math>2</math> corner. For the remaining <math>3n</math> to fill this square plus the <math>5</math> extra members, <math>n</math> must be <math>3</math>. If we instead plaster exactly <math>3</math> rows from the <math>7</math> x <math>n</math> formation to two adjacent sides of the <math>n</math> x <math>n</math> square, we have an <math>(n + 3)</math> x <math>(n + 3)</math> formation that's missing a <math>3</math> x <math>3</math> corner. For the remaining row of length <math>n</math> to fill this plus five, <math>n = 14</math>. Plugging these in, we find <math>n = 14</math> has a much higher count of members: <math>(n + 7)n; n = 14 --> 21(14) = 294</math>
 +
 
 +
Algebraically: We have <math>n^2 + 7n = m</math>, where <math>m</math> is the number of members in the band and <math>n</math> is a positive integer. We partially complete the square for <math>n</math> to get
 +
<math>n^2 + 7n = (n + 1)^2 + 5n - 1 = (n + 2)^2 + 3n - 4 = (n + 3)^2 + n - 9</math>
 +
Our goal is to get <math>n^2 + 7n = y^2 + 5</math> because we want <math>m</math> to be <math>5</math> more than a perfect square. From the above, <math>5n - 1 = 5</math> means <math>n</math> isn't an integer, <math>3n - 4 = 5</math> means that <math>n = 3</math>, and <math>n - 9 = 5</math> means that <math>n = 14</math>. Out of these, <math>n = 14</math> is associated with the highest number of members in the band, so <math>m = (14^2) + 7(14) = 294</math>
 +
 
 +
 
 +
=== Solution 5===
 +
 
 +
Let there be <math>m</math> members and <math>n</math> members for the square and <math>c</math> for the number of columns of the other formation. We have <math>n^2 +5 = c(c+7) \implies n^2+5 = \left(c+\frac{7}{2}\right)^2 -\frac{49}{4} \implies n^2 - \left(c+\frac{7}{2}\right)^2 = -\frac{69}{4} \implies \left(n-c-\frac{7}{2}\right)\left(n + c +\frac{7}{2}\right) \implies (2n-2c-7)(2n+2n+7) = -69.</math>
 +
 
 +
To maximize this we let <math>2n+2c+7 = 68</math> and <math>2n-2c-7 = 1.</math> Solving we find <math>n = 17</math> so the desired number of members is <math>17^2 + 5 = \boxed{294}.</math>
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=2005|n=I|num-b=3|num-a=5}}
 
{{AIME box|year=2005|n=I|num-b=3|num-a=5}}
 +
 +
[[Category:Intermediate Number Theory Problems]]
 +
{{MAA Notice}}

Revision as of 00:20, 22 September 2020

Problem

The director of a marching band wishes to place the members into a formation that includes all of them and has no unfilled positions. If they are arranged in a square formation, there are 5 members left over. The director realizes that if he arranges the group in a formation with 7 more rows than columns, there are no members left over. Find the maximum number of members this band can have.

Solution

Solution 1

If $n > 14$ then $n^2 + 6n + 14 < n^2 + 7n < n^2 + 8n + 21$ and so $(n + 3)^2 + 5 < n(n + 7) < (n + 4)^2 + 5$. If $n$ is an integer there are no numbers which are 5 more than a perfect square strictly between $(n + 3)^2 + 5$ and $(n + 4)^2 + 5$. Thus, if the number of columns is $n$, the number of students is $n(n + 7)$ which must be 5 more than a perfect square, so $n \leq 14$. In fact, when $n = 14$ we have $n(n + 7) = 14\cdot 21 = 294 = 17^2 + 5$, so this number works and no larger number can. Thus, the answer is $\boxed{294}$.

Solution 2

Define the number of rows/columns of the square formation as $s$, and the number of rows of the rectangular formation $r$ (so there are $r - 7$ columns). Thus, $s^2 + 5 = r(r-7) \Longrightarrow r^2 - 7r - s^2 - 5 = 0$. The quadratic formula yields $r = \frac{7 \pm \sqrt{49 - 4(1)(-s^2 - 5)}}{2} = \frac{7 \pm \sqrt{4s^2 + 69}}{2}$. $\sqrt{4s^2 + 69}$ must be an integer, say $x$. Then $4s^2 + 69 = x^2$ and $(x + 2s)(x - 2s) = 69$. The factors of $69$ are $(1,69), (3,23)$; $x$ is maximized for the first case. Thus, $x = \frac{69 + 1}{2} = 35$, and $r = \frac{7 \pm 35}{2} = 21, -14$. The latter obviously can be discarded, so there are $21$ rows and $21 - 7 = 14$ columns, making the answer $294$.

Solution 3

The number of members is $m^2+5=n(n+7)$ for some $n$ and $m$. Multiply both sides by $4$ and complete the square to get $4m^2+69=(2n+7)^2$. Thus, we have $69=((2n+7)+2m)((2n+7)-2m)$. Since we want to maximize $n$, set the first factor equal to $69$ and the second equal to $1$. Solving gives $n=14$, so the answer is $14\cdot21=294$.

Solution 4

Partially completing the square

Geometrically: Split up the formation of $n + 7$ rows and $n$ columns into a square of $n$ rows and $n$ columns and a separate rectangle of the dimensions $7$ rows by $n$ columns. We want to take the rows from the rectangle and add them to the square to get another square and $5$ left over. If we attach exactly $2$ rows on the top and exactly $2$ rows on the side of the $n$ x $n$ square, then we have an $(n + 2)$ x $(n + 2)$ square that's missing a $2$ x $2$ corner. For the remaining $3n$ to fill this square plus the $5$ extra members, $n$ must be $3$. If we instead plaster exactly $3$ rows from the $7$ x $n$ formation to two adjacent sides of the $n$ x $n$ square, we have an $(n + 3)$ x $(n + 3)$ formation that's missing a $3$ x $3$ corner. For the remaining row of length $n$ to fill this plus five, $n = 14$. Plugging these in, we find $n = 14$ has a much higher count of members: $(n + 7)n; n = 14 --> 21(14) = 294$

Algebraically: We have $n^2 + 7n = m$, where $m$ is the number of members in the band and $n$ is a positive integer. We partially complete the square for $n$ to get $n^2 + 7n = (n + 1)^2 + 5n - 1 = (n + 2)^2 + 3n - 4 = (n + 3)^2 + n - 9$ Our goal is to get $n^2 + 7n = y^2 + 5$ because we want $m$ to be $5$ more than a perfect square. From the above, $5n - 1 = 5$ means $n$ isn't an integer, $3n - 4 = 5$ means that $n = 3$, and $n - 9 = 5$ means that $n = 14$. Out of these, $n = 14$ is associated with the highest number of members in the band, so $m = (14^2) + 7(14) = 294$


Solution 5

Let there be $m$ members and $n$ members for the square and $c$ for the number of columns of the other formation. We have $n^2 +5 = c(c+7) \implies n^2+5 = \left(c+\frac{7}{2}\right)^2 -\frac{49}{4} \implies n^2 - \left(c+\frac{7}{2}\right)^2 = -\frac{69}{4} \implies \left(n-c-\frac{7}{2}\right)\left(n + c +\frac{7}{2}\right) \implies (2n-2c-7)(2n+2n+7) = -69.$

To maximize this we let $2n+2c+7 = 68$ and $2n-2c-7 = 1.$ Solving we find $n = 17$ so the desired number of members is $17^2 + 5 = \boxed{294}.$

See also

2005 AIME I (ProblemsAnswer KeyResources)
Preceded by
Problem 3
Followed by
Problem 5
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All AIME Problems and Solutions

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