Mock AIME 4 2006-2007 Problems/Problem 6

From AoPSWiki

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

Personal tools

Navigation

Search

Toolbox