Revision as of 16:09, 12 May 2023

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

Solution 3

We first notice that when a polygon has $n$ sides where $n\not\equiv 0\pmod{3}$ , there cannot exist any three vertices that form an equilateral triangle. Also, the parody of $n$ and $n+1$ also matters, since they influence how many isosceles triangles including equilateral triangles exist in the polygon. We can model an equation $2x+y=n$ , where the lines that connect the vertices that are congruent are $x$ vertices apart and the other line is $y$ vertices apart. If $n$ is even, there are $\frac{n-2}{2}$ solutions for $(x,y)$ which would determine the "type" of isosceles triangle. Note that we subtract two since $y$ cannot be zero. If $n$ is odd, there are $\frac{n-1}{2}$ solutions for $(x,y)$ . Next, we do casework on the congruence of $n$ mod $3$ and the parody of $n$ using the information above:

Case $1$ :

$n\not\equiv 0\pmod{3}$ , $n+1\not\equiv 0\pmod{3}$

$n$ is even, $n+1$ is odd

There are $\frac{n-2}{2}$ "types" of isosceles triangles in the polygon with $n$ sides. Each isosceles triangle has a "unique point" which connects the two congruent sides. Therefore, for each "type" of triangle, there exists $n$ of those triangles since the "unique point" can be any of the $n$ vertices. There are $\frac{n}{2}$ "types" of isosceles triangles in the polygon with $n+1$ sides and $n+1$ unique points for each "type" of triangle. Therefore, $\frac{n}{2}\cdot{(n+1)}-\frac{n-2}{2}\cdot{(n)}=78$ . Solving, we get $n=52$

Case $2$ :

$n\not\equiv 0\pmod{3}$ , $n+1\not\equiv 0\pmod{3}$

$n$ is odd, $n+1$ is even

There are $\frac{n-1}{2}\cdot{(n)}$ possible isosceles triangles in the $n$ sided polygon. There are $\frac{n-1}{2}\cdot{(n+1)}$ possible isosceles triangles in the $n+1$ sided polygon. The difference should be $78$ , so $\frac{n-1}{2}\cdot{(n+1)}-\frac{n-1}{2}\cdot{(n)}=78$ . Solving

Video Solution

https://youtu.be/fFgakiw66WY

~MathProblemSolvingSkills.com

@@ Line 78: / Line 78: @@
 == Solution 3 ==
-We first notice that when a polygon has <math>n</math> sides where <math>n\not\equiv 0\pmod{3}</math>, there cannot exist any three vertices that form an equilateral triangle. Also, the parody of <math>n</math> and <math>n+1</math> also matters, since they influence how many isosceles triangles including equilateral triangles exist in the polygon. We can model an equation <math>2x+y=n</math>, where the lines that connect the vertices that are congruent are <math>x</math> vertices apart and the other line is <math>y</math> vertices apart. If n is even, there are <math>\frac{n-2}{2}</math> solutions for <math>(x,y)</math> which would determine the "type" of isosceles triangle. Note that we subtract two since <math>y</math> cannot be zero.
+We first notice that when a polygon has <math>n</math> sides where <math>n\not\equiv 0\pmod{3}</math>, there cannot exist any three vertices that form an equilateral triangle. Also, the parody of <math>n</math> and <math>n+1</math> also matters, since they influence how many isosceles triangles including equilateral triangles exist in the polygon. We can model an equation <math>2x+y=n</math>, where the lines that connect the vertices that are congruent are <math>x</math> vertices apart and the other line is <math>y</math> vertices apart. If <math>n</math> is even, there are <math>\frac{n-2}{2}</math> solutions for <math>(x,y)</math> which would determine the "type" of isosceles triangle. Note that we subtract two since <math>y</math> cannot be zero. If <math>n</math> is odd, there are <math>\frac{n-1}{2}</math> solutions for <math>(x,y)</math>.
+Next, we do casework on the congruence of <math>n</math> mod <math>3</math> and the parody of <math>n</math> using the information above:
+Case <math>1</math>:
+<math>n\not\equiv 0\pmod{3}</math>, <math>n+1\not\equiv 0\pmod{3}</math>
+<math>n</math> is even, <math>n+1</math> is odd
+There are <math>\frac{n-2}{2}</math> "types" of isosceles triangles in the polygon with <math>n</math> sides. Each isosceles triangle has a "unique point" which connects the two congruent sides. Therefore, for each "type" of triangle, there exists <math>n</math> of those triangles since the "unique point" can be any of the <math>n</math> vertices. There are <math>\frac{n}{2}</math> "types" of isosceles triangles in the polygon with <math>n+1</math> sides and <math>n+1</math> unique points for each "type" of triangle. Therefore, <math>\frac{n}{2}\cdot{(n+1)}-\frac{n-2}{2}\cdot{(n)}=78</math>. Solving, we get <math>n=52</math>
+Case <math>2</math>:
+<math>n\not\equiv 0\pmod{3}</math>, <math>n+1\not\equiv 0\pmod{3}</math>
+<math>n</math> is odd, <math>n+1</math> is even
+There are <math>\frac{n-1}{2}\cdot{(n)}</math> possible isosceles triangles in the <math>n</math> sided polygon. There are <math>\frac{n-1}{2}\cdot{(n+1)}</math> possible isosceles triangles in the <math>n+1</math> sided polygon. The difference should be <math>78</math>, so <math>\frac{n-1}{2}\cdot{(n+1)}-\frac{n-1}{2}\cdot{(n)}=78</math>. Solving
 ==Video Solution==

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

Page

Toolbox

Search

Difference between revisions of "2017 AIME II Problems/Problem 13"