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

Mock AIME 4 2006-2007 Problems/Problem 6

Revision as of 01:41, 31 January 2009 by Misof (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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"