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 "Mock AIME 4 2006-2007 Problems/Problem 6"

m
 
(One intermediate revision by one other user not shown)
Line 3: Line 3:
 
==Solution==
 
==Solution==
  
−
{{solution}}
+
The formula for the number of diagonals of a convex n-gon is <math>\dfrac{n(n-3)}{2}</math>. We need to count the <math>n<1000</math> for which this is a perfect square.
  
 +
The numbers <math>n</math> and <math>n-3</math> are either relatively prime, or their greatest common divisor is <math>3</math>. We will handle each case separately.
  
 +
=== Case 1: relatively prime ===
 +
 +
If they are relatively prime, we know the following things:
 +
* neither of them is divisible by <math>3</math>
 +
* one of them is an odd perfect square
 +
* the other is twice a perfect square
 +
 +
One possible way of handling this case would be to try all odd perfect squares less than <math>1003</math>, there are just <math>11</math> of them. We will show an alternate approach.
 +
 +
The one that is the odd perfect square not divisible by <math>3</math> is of the form <math>(6k\pm 1)^2</math>.
 +
The other one is either larger or smaller by <math>3</math>.
 +
 +
<math>(6k\pm 1)^2 + 3 \equiv 4 \pmod 8</math>, hence the number that is <math>3</math> larger is divisible by <math>2^2</math> and not by <math>2^3</math>, and thus it can not be twice a perfect square.
 +
 +
<math>(6k\pm 1)^2 - 3 \equiv 4 \pmod 6</math>, thus <math>\frac{ (6k\pm 1)^2 - 3 }2 \equiv 2 \pmod 3</math>. This means that half the smaller number can not be a perfect square, as perfect squares give only the remainders <math>0</math> and <math>1</math> modulo <math>3</math>.
 +
 +
Thus in this case there are no solutions.
 +
 +
=== Case 2: both are divisible by 3 ===
 +
 +
Let <math>n=3m</math>, then <math>n-3=3(m-1)</math>. We now want to count all <math>m\leq 333</math> for which <math>\dfrac{m(m-1)}2</math> is a perfect square.
 +
Once again we can make a similar observation about <math>m</math> and <math>m-1</math>:
 +
* one of them is an odd perfect square
 +
* the other is twice a perfect square
 +
 +
There are nine odd perfect squares less than <math>333</math>. Trying each of them as either <math>m</math> or <math>m-1</math>, we find the following <math>\boxed{5}</math> solutions:
 +
<math>m\in\{1,2,9,50,289\}</math>, giving <math>n\in\{3,6,27,150,867\}</math>.
  
 
----
 
----

Latest revision as of 00:41, 31 January 2009

Problem

For how many positive integers $n < 1000$ does there exist a regular $n$-sided polygon such that the number of diagonals is a nonzero perfect square?

Solution

The formula for the number of diagonals of a convex n-gon is $\dfrac{n(n-3)}{2}$. We need to count the $n<1000$ for which this is a perfect square.

The numbers $n$ and $n-3$ are either relatively prime, or their greatest common divisor is $3$. We will handle each case separately.

Case 1: relatively prime

If they are relatively prime, we know the following things:

  • neither of them is divisible by $3$
  • one of them is an odd perfect square
  • the other is twice a perfect square

One possible way of handling this case would be to try all odd perfect squares less than $1003$, there are just $11$ of them. We will show an alternate approach.

The one that is the odd perfect square not divisible by $3$ is of the form $(6k\pm 1)^2$. The other one is either larger or smaller by $3$.

$(6k\pm 1)^2 + 3 \equiv 4 \pmod 8$, hence the number that is $3$ larger is divisible by $2^2$ and not by $2^3$, and thus it can not be twice a perfect square.

$(6k\pm 1)^2 - 3 \equiv 4 \pmod 6$, thus $\frac{ (6k\pm 1)^2 - 3 }2 \equiv 2 \pmod 3$. This means that half the smaller number can not be a perfect square, as perfect squares give only the remainders $0$ and $1$ modulo $3$.

Thus in this case there are no solutions.

Case 2: both are divisible by 3

Let $n=3m$, then $n-3=3(m-1)$. We now want to count all $m\leq 333$ for which $\dfrac{m(m-1)}2$ is a perfect square. Once again we can make a similar observation about $m$ and $m-1$:

  • one of them is an odd perfect square
  • the other is twice a perfect square

There are nine odd perfect squares less than $333$. Trying each of them as either $m$ or $m-1$, we find the following $\boxed{5}$ solutions: $m\in\{1,2,9,50,289\}$, giving $n\in\{3,6,27,150,867\}$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_4_2006-2007_Problems/Problem_6&oldid=29834"