# Difference between revisions of "Mock AIME 4 2006-2007 Problems/Problem 6"

Line 3: | Line 3: | ||

==Solution== | ==Solution== | ||

− | The formula for the number of diagonals of a convex n-gon is | + | 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. |

− | <math> | + | 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 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 .