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 "2017 AIME II Problems/Problem 13"
(→‎Solution 2 (elaborates on the possible cases))
(5 intermediate revisions by 3 users not shown)
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
−
<math>\boxed{245}</math>
+
Considering <math>n \pmod{6}</math>, we have the following formulas:
 +
 
 +
Even and a multiple of 3: <math>\frac{n(n-4)}{2} + \frac{n}{3}</math>
 +
 
 +
Even and not a multiple of 3: <math>\frac{n(n-2)}{2}</math>
 +
 
 +
Odd and a multiple of 3: <math>\frac{n(n-3)}{2} + \frac{n}{3}</math>
 +
 
 +
Odd and not a multiple of 3: <math>\frac{n(n-1)}{2}</math>
 +
 
 +
To derive these formulas, we note the following:
 +
Any isosceles triangle formed by the vertices of our regular <math>n</math>-sided polygon <math>P</math> has its sides from the set of edges and diagonals of <math>P</math>. Notably, as two sides of an isosceles triangle must be equal, it is important to use the property that same-lengthed edges and diagonals come in groups of <math>n</math>, unless <math>n</math> is even when one set of diagonals (those which bisect the polygon) comes in a group of <math>\frac{n}{2}</math>. Three properties hold true of <math>f(n)</math>:
 +
 
 +
When <math>n</math> is odd there are <math>\frac{n(n-1)}{2}</math> satisfactory subsets (This can be chosen with <math>n</math> choices for the not-base vertex, and <math>\frac{n-1}{2}</math> for the pair of equal sides as we have <math>n-1</math> edges to choose from, and we must divide by 2 for over-count).*
 +
*Another explanation: For any diagonal or side of the polygon chosen as the base of the isosceles triangle, there is exactly 1 isosceles triangle that can be formed. So, the total number of satisfactory subsets is <math>\dbinom{n}{2}=\dfrac{n(n-1)}{2}.</math>
 +
 
 +
When <math>n</math> is even there are <math>\frac{n(n-2)}{2}</math> satisfactory subsets (This can be chosen with <math>n</math> choices for the not-base vertex, and <math>\frac{n-2}{2}</math> for the pair of equal sides as we have <math>n-1</math> edges to choose from, one of them which is not satisfactory (the bisecting edge), and we must divide by 2 for over-count).
 +
 
 +
When <math>n</math> is a multiple of three we additionally over-count equilateral triangles, of which there are <math>\frac{n}{3}</math>. As we count them three times, we are two times over, so we subtract <math>\frac{2n}{3}</math>.
 +
 
 +
Considering the six possibilities <math>n \equiv 0,1,2,3,4,5 \pmod{6}</math> and solving, we find that the only valid solutions are <math>n = 36, 52, 157</math>, from which the answer is <math>36 + 52 + 157 = \boxed{245}</math>.
 +
 
 +
==Solution 2 (elaborates on the possible cases)==
 +
In the case that <math>n\equiv 0\pmod 3</math>, there are <math>\frac{n}{3}</math> equilateral triangles. We will now count the number of non-equilateral isosceles triangles in this case.
 +
 
 +
Select a vertex <math>P</math> of a regular <math>n</math>-gon. We will count the number of isosceles triangles with their vertex at <math>P</math>. (In other words, we are counting the number of isosceles triangles <math>\triangle APB</math> with <math>A, B, P</math> among the vertices of the <math>n</math>-gon, and <math>AP=BP</math>.)
 +
 
 +
If the side <math>AP</math> spans <math>k</math> sides of the <math>n</math>-gon (where <math>k<\frac{n}{2}</math>), the side <math>BP</math> must span <math>k</math> sides of the <math>n</math>-gon, and, thus, the side <math>AB</math> must span <math>n-2k</math> sides of the <math>n</math>-gon. As <math>\triangle ABP</math> has three distinct vertices, the side <math>AB</math> must span at least one side, so <math>n-2k \ge 1</math>. Combining this inequality with the fact that <math>1\le k<\frac{n}{2}</math> and <math>k\not = \frac{n}{3}</math> (as <math>\triangle ABP</math> cannot be equilateral), we find that there are <math>\lceil\frac{n}{2}\rceil-2</math> possible <math>k</math>.
 +
 
 +
As each of the <math>n</math> vertices can be the vertex of a given triangle <math>\triangle ABP</math>, there are <math>\left(\lceil \frac{n}{2} \rceil -2 \right)\cdot n</math> non-equilateral isosceles triangles.
 +
 
 +
Adding in the <math>\frac{n}{3}</math> equilateral triangles, we find that for <math>n\equiv 0\pmod 3</math>: <math>f(n) = \frac{n}{3}+\left(\lceil \frac{n}{2} \rceil -2\right)\cdot n</math>.
 +
 
 +
On the other hand, if <math>n\equiv 1, 2\pmod 3</math>, there are no equilateral triangles, and we may follow the logic of the paragraph above to find that <math>f(n)=\left(\lceil \frac{n}{2} \rceil -1\right)\cdot n</math>.
 +
 
 +
We may now rewrite the given equation, based on the remainder <math>n</math> leaves when divided by 3.
 +
 
 +
 
 +
Case 1: <math>n\equiv 0\pmod 3</math>
 +
The equation <math>f(n+1)=f(n)+78</math> for this case is <math>\left(\lceil \frac{n+1}{2} \rceil -1\right)\cdot (n+1)=\frac{n}{3}+\left(\lceil \frac{n}{2} \rceil -2\right)\cdot n+78</math>.
 +
 
 +
In this case, <math>n</math> is of the form <math>6k</math> or <math>6k+3</math>, for some integer <math>k</math>.
 +
 
 +
Subcase 1: <math>n=6k</math>
 +
Plugging into the equation above yields <math>k=6\rightarrow n=36</math>.
 +
 
 +
Subcase 2: <math>n=6k+3</math>
 +
Plugging into the equation above yields <math>7k=75</math>, which has no integer solutions.
 +
 
 +
Case 2: <math>n\equiv 1\pmod 3</math>
 +
The equation <math>f(n+1)=f(n)+78</math> for this case is <math>\left(\lceil \frac{n+1}{2} \rceil -1\right)\cdot (n+1)=\left(\lceil \frac{n}{2} \rceil -1\right)\cdot n+78</math>.
 +
 
 +
In this case, <math>n</math> is of the form <math>6k+1</math> or <math>6k+4</math>, for some integer <math>k</math>.
 +
 
 +
Subcase 1: <math>n=6k+1</math>
 +
In this case, the equation above yields <math>k=8\rightarrow n=52</math>.
 +
 
 +
Subcase 2: <math>n=6k+4</math>
 +
In this case, the equation above yields <math>k=26\rightarrow n=157</math>.
 +
 
 +
Case 3: <math>n\equiv 2\pmod 3</math>
 +
The equation <math>f(n+1)=f(n)+78</math> for this case is <math>\frac{n+1}{3}+\left(\lceil \frac{n+1}{2} \rceil -2\right)\cdot (n+1)=\left(\lceil \frac{n}{2} \rceil -1\right)\cdot n+78</math>.
 +
 
 +
In this case, <math>n</math> is of the form <math>6k+2</math> or <math>6k+5</math>, for some integer <math>k</math>.
 +
 
 +
Subcase 1: <math>n=6k+2</math>
 +
The equation above reduces to <math>5k=77</math>, which has no integer solutions.
 +
 
 +
Subcase 2: <math>n=6k+5</math>
 +
The equation above reduces to <math>k=-80</math>, which does not yield a positive integer solution for <math>n</math>.
 +
----------------------
 +
In summary, the possible <math>n</math> are <math>36, 52, 157</math>, which add to <math>\boxed{245}</math>.
  
 
=See Also=
 
=See Also=
 
{{AIME box|year=2017|n=II|num-b=12|num-a=14}}
 
{{AIME box|year=2017|n=II|num-b=12|num-a=14}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 16:55, 14 February 2018

Problem

For each integer $n\geq3$, let $f(n)$ be the number of $3$-element subsets of the vertices of the regular $n$-gon that are the vertices of an isosceles triangle (including equilateral triangles). Find the sum of all values of $n$ such that $f(n+1)=f(n)+78$.

Solution

Considering $n \pmod{6}$, we have the following formulas:

Even and a multiple of 3: $\frac{n(n-4)}{2} + \frac{n}{3}$

Even and not a multiple of 3: $\frac{n(n-2)}{2}$

Odd and a multiple of 3: $\frac{n(n-3)}{2} + \frac{n}{3}$

Odd and not a multiple of 3: $\frac{n(n-1)}{2}$

To derive these formulas, we note the following: Any isosceles triangle formed by the vertices of our regular $n$-sided polygon $P$ has its sides from the set of edges and diagonals of $P$. Notably, as two sides of an isosceles triangle must be equal, it is important to use the property that same-lengthed edges and diagonals come in groups of $n$, unless $n$ is even when one set of diagonals (those which bisect the polygon) comes in a group of $\frac{n}{2}$. Three properties hold true of $f(n)$:

When $n$ is odd there are $\frac{n(n-1)}{2}$ satisfactory subsets (This can be chosen with $n$ choices for the not-base vertex, and $\frac{n-1}{2}$ for the pair of equal sides as we have $n-1$ edges to choose from, and we must divide by 2 for over-count).*

  • Another explanation: For any diagonal or side of the polygon chosen as the base of the isosceles triangle, there is exactly 1 isosceles triangle that can be formed. So, the total number of satisfactory subsets is $\dbinom{n}{2}=\dfrac{n(n-1)}{2}.$

When $n$ is even there are $\frac{n(n-2)}{2}$ satisfactory subsets (This can be chosen with $n$ choices for the not-base vertex, and $\frac{n-2}{2}$ for the pair of equal sides as we have $n-1$ edges to choose from, one of them which is not satisfactory (the bisecting edge), and we must divide by 2 for over-count).

When $n$ is a multiple of three we additionally over-count equilateral triangles, of which there are $\frac{n}{3}$. As we count them three times, we are two times over, so we subtract $\frac{2n}{3}$.

Considering the six possibilities $n \equiv 0,1,2,3,4,5 \pmod{6}$ and solving, we find that the only valid solutions are $n = 36, 52, 157$, from which the answer is $36 + 52 + 157 = \boxed{245}$.

Solution 2 (elaborates on the possible cases)

In the case that $n\equiv 0\pmod 3$, there are $\frac{n}{3}$ equilateral triangles. We will now count the number of non-equilateral isosceles triangles in this case.

Select a vertex $P$ of a regular $n$-gon. We will count the number of isosceles triangles with their vertex at $P$. (In other words, we are counting the number of isosceles triangles $\triangle APB$ with $A, B, P$ among the vertices of the $n$-gon, and $AP=BP$.)

If the side $AP$ spans $k$ sides of the $n$-gon (where $k<\frac{n}{2}$), the side $BP$ must span $k$ sides of the $n$-gon, and, thus, the side $AB$ must span $n-2k$ sides of the $n$-gon. As $\triangle ABP$ has three distinct vertices, the side $AB$ must span at least one side, so $n-2k \ge 1$. Combining this inequality with the fact that $1\le k<\frac{n}{2}$ and $k\not = \frac{n}{3}$ (as $\triangle ABP$ cannot be equilateral), we find that there are $\lceil\frac{n}{2}\rceil-2$ possible $k$.

As each of the $n$ vertices can be the vertex of a given triangle $\triangle ABP$, there are $\left(\lceil \frac{n}{2} \rceil -2 \right)\cdot n$ non-equilateral isosceles triangles.

Adding in the $\frac{n}{3}$ equilateral triangles, we find that for $n\equiv 0\pmod 3$: $f(n) = \frac{n}{3}+\left(\lceil \frac{n}{2} \rceil -2\right)\cdot n$.

On the other hand, if $n\equiv 1, 2\pmod 3$, there are no equilateral triangles, and we may follow the logic of the paragraph above to find that $f(n)=\left(\lceil \frac{n}{2} \rceil -1\right)\cdot n$.

We may now rewrite the given equation, based on the remainder $n$ leaves when divided by 3.


Case 1: $n\equiv 0\pmod 3$ The equation $f(n+1)=f(n)+78$ for this case is $\left(\lceil \frac{n+1}{2} \rceil -1\right)\cdot (n+1)=\frac{n}{3}+\left(\lceil \frac{n}{2} \rceil -2\right)\cdot n+78$.

In this case, $n$ is of the form $6k$ or $6k+3$, for some integer $k$.

Subcase 1: $n=6k$ Plugging into the equation above yields $k=6\rightarrow n=36$.

Subcase 2: $n=6k+3$ Plugging into the equation above yields $7k=75$, which has no integer solutions.

Case 2: $n\equiv 1\pmod 3$ The equation $f(n+1)=f(n)+78$ for this case is $\left(\lceil \frac{n+1}{2} \rceil -1\right)\cdot (n+1)=\left(\lceil \frac{n}{2} \rceil -1\right)\cdot n+78$.

In this case, $n$ is of the form $6k+1$ or $6k+4$, for some integer $k$.

Subcase 1: $n=6k+1$ In this case, the equation above yields $k=8\rightarrow n=52$.

Subcase 2: $n=6k+4$ In this case, the equation above yields $k=26\rightarrow n=157$.

Case 3: $n\equiv 2\pmod 3$ The equation $f(n+1)=f(n)+78$ for this case is $\frac{n+1}{3}+\left(\lceil \frac{n+1}{2} \rceil -2\right)\cdot (n+1)=\left(\lceil \frac{n}{2} \rceil -1\right)\cdot n+78$.

In this case, $n$ is of the form $6k+2$ or $6k+5$, for some integer $k$.

Subcase 1: $n=6k+2$ The equation above reduces to $5k=77$, which has no integer solutions.

Subcase 2: $n=6k+5$ The equation above reduces to $k=-80$, which does not yield a positive integer solution for $n$.

In summary, the possible $n$ are $36, 52, 157$, which add to $\boxed{245}$.

See Also

2017 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 12 		Followed by
Problem 14
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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2017_AIME_II_Problems/Problem_13&oldid=91215"