Mock AIME 4 2006-2007 Problems/Problem 6
Contents
[hide]Problem
For how many positive integers does there exist a regular
-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 . We need to count the
for which this is a perfect square.
The numbers and
are either relatively prime, or their greatest common divisor is
. 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
- 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 , there are just
of them. We will show an alternate approach.
The one that is the odd perfect square not divisible by is of the form
.
The other one is either larger or smaller by
.
, hence the number that is
larger is divisible by
and not by
, and thus it can not be twice a perfect square.
, thus
. This means that half the smaller number can not be a perfect square, as perfect squares give only the remainders
and
modulo
.
Thus in this case there are no solutions.
Case 2: both are divisible by 3
Let , then
. We now want to count all
for which
is a perfect square.
Once again we can make a similar observation about
and
:
- one of them is an odd perfect square
- the other is twice a perfect square
There are nine odd perfect squares less than . Trying each of them as either
or
, we find the following
solutions:
, giving
.