## Olympiad Number Theory+AIME Number Theory

1993 AIME #9: Two thousand points are given on a circle. Label one of the points 1. From this point, count 2 points in the clockwise direction and label this point 2. From the point labeled 2, count 3 points in the clockwise direction and label this point 3. (See figure.) Continue this process until the labels are all used. Some of the points on the circle will have more than one label and some points will not have a label. What is the smallest integer that labels the same point as 1993?

Solution

Note that and can’t divide using basic Euclid’s, therefore, and or and (unless one of them is which will be obviously not true after doing computations).

The first gives and . The second gives .

The first gives (after doing some simple cases). For the second, we get a cycle of: which mod 16 gives us therefore we are done and the answer is .

Two positive integers differ by The sum of their square roots is the square root of an integer that is not a perfect square. What is the maximum possible sum of the two integers?

Solution

We want to maximize . We have either is a multiple of , or odd (theorem on perfect squares). In the first case, or .

However, gives which gives which definitely isn’t maximal and same with . Also, gives being a perfect square and so that’s absurd.

Therefore, . The first case gives us which gives for maximum, or . Therefore, in this case.

gives or as maximum therefore .

Therefore, maximum value of is in all cases. Therefore, we get therefore the sum is .

ISL 1995 S3:

For an integer let be the least prime that does not divide and define to be the product of all primes less than In particular, For having define Consider the sequence defined by and

Solution

Note that the numbers without the factor of the th prime (this is the leading factor) are going to create the group to by induction hypothesis. Also, we get that for to , we get an added factor of the th prime by all these numbers, therefore we are done by induction.

. Therefore, putting this in this form of induction, we get (where we only include digits which are in the prime factorization). Therefore, we get . This is .

For a positive integer , let denote the sum of the remainders when is divided by respectively. Prove that for infinitely many positive integers . (1981 K¨ursch´ak Competition)

Solution

Okay so note that and therefore I desire to prove always works.

For , we compare remainders with . Starting with we are going to get a sum starting with and going down, which is the same with and going down. Also, gives , therefore we are going to prove that from down they are the same.

We are going to have the remainder when divides a number always to be more than unless the number we divide by divides . This happens only for and in this case we get remainder being and remainder being . Therefore, summing this up we get .

When it doesn’t divide this, we get incidences (subtracting all the ones that worked above), which is the same as above, and hence we are done.

## Complex Numbers and some Number Theory

Let , , be the three sides of a triangle, and let , , , be the angles opposite them. If , find (1989 AIME #10)

Solution

Next, use Law of Cosines to give us . Therefore, . Also, . Hence, .

Solution

.

.

and . The second equation gives which is the same as the first.

Therefore or … however, testing gives and gives therefore, which gives solutions.

Solution

Solution

b. Prove that is never an integer for .

a.

Proof: This is pretty simple, let , then and . Also, . Therefore, and since , we have .

Now, using the Lemma , and then continue on in this manner we are going to get the highest power of in the denominator, therefore we have . We need, however, for this to be true we need however since this is false.

As an aside: The reason we choose is because this way we always have or and can never have equality (due to parity).

b

Continue on in this manner of grouping to give us . We need this to be greater than or equal to or therefore, which is obviously false because .

We have (with equality when for some non-negative integer ) . We have (with equality again when . Therefore, as a conclusion of this long inequality chain, with equality when . Therefore, at most we will have equality which holds when (as we need for it to be greater).

This completes both sides of our if and only if statement, so we are done.

Solution

85) If you’re stuck with a ratio that you’d like to show is inamginary, here’s a hint. If , then what does equal?

Now we have a HIGHLY computationally intense problem so let’s try it.

which we need to be imaginary.

This is crucial in the next part of the problem.

or Therefore, we get which is true by the definition of .

Yay, lemma proven.

We note that letting this value be , we get .

Therefore, we must now prove that is imaginary.

Since is a primitive 6th root of unity, we get or .

In the first case, we get or therefore it is the same as

## A bunch of inequalities

Let . Prove that . (2004 USAMO #5)

Solution

We have our desired from above.

Prove that (Online Math Circle)

Solution

Let be positive real numbers. Prove that, . (Online Math Circle)

Solution

Therefore, now by taking the cube root of this inequality, we are done.

Let be real numbers such that . Prove that . (Centro American Math Olympiad, 2009)

Solution

Let be positive reals such that . Prove . (Source: Online Math Circle)

Solution

.Now, we need , which is true by AM-GM, so we are done.

Let be positive reals such that . Prove that . (Belarus IMO TST 1999)

Solution

For arbitrary positive numbers , prove that (1999 Czech and Slovak Republic)

Solution

Let be positive real numbers with . Prove that, . (Ireland 1999).

Solution

Let be positive reals. Prove that . (Online Math Circle)

Solution

Let be positive reals such that . Prove that . When is there equality?

(French TST 2006 Problem 2)

Solution

## Some geometry AIME problems and other problems

1984 AIME Problem #3:

A point is chosen in the interior of so that when lines are drawn through parallel to the sides of , the resulting smaller triangles, , , and in the figure, have areas 4, 9, and 49, respectively. Find the area of .

Solution

Using this, we get . Therefore, . Similarly, we get , and . Sum up all these areas in the picture to give us .

1984 AIME Problem #9:

In tetrahedron , edge has length 3 cm. The area of face is 15 and the area of face is 12 . These two faces meet each other at a angle. Find the volume of the tetrahedron in

Solution

So, we find the height of to be . Therefore, the height of the whole figure is , and the total area of the figure is going to be .

1985 AIME Problem #4:

A small square is constructed inside a square of area 1 by dividing each side of the unit square into equal parts, and then connecting the vertices to the division points closest to the opposite vertices. Find the value of if the the area of the small square is exactly 1/1985.

Solution

As shown in the figure, triangle is divided into six smaller triangles by lines drawn from the vertices through a common interior point. The areas of four of these triangles are as indicated. Find the area of triangle .

Solution

Let . Note that because of same altitudes. Using Ceva’s on these lines intersecting at gives us . Using similar logic as before, we have and . Therefore, we now have . Denote and now as well. Therefore, we get .

Substituting this back into gives us . This gives us . We list out the factors, which are . Therefore, we find . Next, .

1988 AIME Problem #7:

In triangle , , and the altitude from divides into segments of length 3 and 17. What is the area of triangle ?

Solution

1990 AIME Problem #7:

A triangle has vertices , , and . The equation of the bisector of can be written in the form . Find .

Solution

Therefore, the line we want is from . The slope of this line is , so the equation of the line is . This gives us . Therefore, and our answer is .

1994 AIME Problem #2:

A circle with diameter of length 10 is internally tangent at to a circle of radius 20. Square is constructed with and on the larger circle, tangent at to the smaller circle, and the smaller circle outside . The length of can be written in the form , where and are integers. Find .

Solution

Solution

gives us . Since , giving and completing this case.

gives us or (since ). Therefore, giving us giving two values of .

Solution

We continue with putting everything involving on the LHS to give us .

Therefore, for some constant .

Substituting this into our original equation gives which is true.

Therefore our general form is true, and for all constants . Since is any constant, we can also write this in the form .

.If and are integers such that is a factor of , then find . (AHSME)

Solution

If is the product of two linear factors with integral coefficients, find the value of . (CMO)

Solution

These are the equations we get. From the first equation, and because we have integral coefficients, we WLOG let and .

From the first two equations, . Therefore, letting and , we have and . Therefore, .

We go through cases on . gives us absurd. gives absurd. gives absurd. gives absurd. gives which is possible. gives absurd. Therefore, . Furthermore, . But so this isn’t possible.

We go through cases on again. gives us absurd. gives us absurd. gives us . gives us .

gives and gives . But so again absurd.

Let be a fourth degree polynomial with leading coefficient such that , , and . Find . (Intermediate Algebra)

Solution

Note that letting , we have giving us after subtracting out equations, . Also, so after subtracting out equations, we have . Therefore, , and . Also is given.

Now it’s a matter of just solving equations.

Show that the polynomial does not have a pair of real roots with product . (Intermediate Algebra).

Solution

Therefore, . Next, and . Therefore, or . Therefore, . However, this doesn’t check with the last equation, so we are done .

Solve for all complex numbers such that . (HMMT)

Solution

We have looking at terms. Therefore, . Hence, we have .

From , and , we have . WLOG, we let the pair be

The first case gives us . We now have as desired.

The second case gives us . We have , so therefore , .

Solution

Now, first off, , therefore . Assume that holds for all integers . Therefore, or therefore and our induction is completed. For negative values, assume that holds. Therefore, completing induction as well.

Now, for odd integers, we get .

Now, use similar induction by assuming for all integers . Therefore, completing our induction. For negative values, assume holds. Then, completing our induction.

Therefore, we are finished with both cases and we are done .

.

## Logarithmic, Polynomial, Sequences and Series Problems

Let be a positive integer, and let be a sequence of reals such that , , , and for . Find . (2005 AIME II Problem 11)

Solution

Evaluate the infinite product . (Source: Putnam)

Solution

Find a closed form for . (AoPS)

Solution

A sequence of numbers satisfies and for all . Determine the value of for . (CMO)

Solution

Find the last three digits of the product of the positive roots of(1995 AIME #2)

**Solution**

**Solution**

**Problem:**

**Solution:**

has two solutions and . Find . (2001 AIME I Problem 9)

**Solution**

The second equation gives . Therefore, or .

Lastly, the third equation gives or therefore .

Multiply all the equations to give us .

We care most about the variable , so we go from teh equation to give us . First off, simplify this, to give us . Therefore . Therefore, substitute to give us .

**Solution**

**Solution**

**Solution**

If you don’t know this identity, here’s the proof: Assume it holds for . Therefore, . We need . Therefore, we must have which is true by definition. The last thing we need is for the base case to work, which it does, since .

**Solution**

Note that for the points to be on a line, we need for them to satisfy for all of them. Let and be constants as they are already, and we have , , . Therefore, the roots of the polynomial are , so hence and we are done .

## USAMO, AIME, Inequalities

The sum of the following seven numbers is exactly 19: , , , , , , . It is desired to replace each by an integer approximation , , so that the sum of the ‘s is also 19 and so that , the maximum of the “errors” , the maximum absolute value of the difference, is as small as possible. For this minimum , what is ? (1985 AIME Problem 8)

**Solution**

**Solution**

**Solution**

After expanding this out, the rest is obvious by Muirheads majorizes .

**Problem:**Prove that if for all then . (AoPS)15 second method

5 minute method

This is the equivalent of proving or .

We get this being the equivalent of proving .

The rest is simple, we note that if then both terms are greater than so product is greater than . If , then both are negative, so the product is greater than so all products are greater than so their sum is as well .

**Solution:**

. Note that , and (both from previous equation), so we get

so we get the coefficient is .

so the coefficient of this is

so the coefficient of this is .

so the coefficient of this is .

## Polynomials and Catan

Show that where is a positive integer.

**Solution**

Now, assume it works for , therefore we have . We must prove .

Again, by hypothesis, , so has remainder when divided by

Since , we can add to it to further simplify it (with a wishful eye!), to give us or , so we have proven

We wanted to prove or which is exactly what I got above, so we are done .

**Solution**

Lastly, , so . This gives that . We could use this to find , but that’s terribly un-interesting, instead we have or .

**Solution**

**Solution**

Okay, so Brazil wins the first game and we get to without going through any points on on this graph. We make a one to one correspondence with this and to . We also make another one to one correspondence between going through and . If it goes through it must have gone through so to count to , we just move up (we can’t move right since it’s a grid), so we get or .

**Solution(using hint)**

So now, looking at the casework that we have internal nodes on the left node to start out with, then , then so forth until we get . This gives us . By our inductive hypothesis, we have all of these , therefore we get which by the recursive definition of catalan numbers is true .

**Solution**

Letting the second term be , I note that the third term is going to be , the fifth term is going to be , the seventh term is going to be , and the ninth term is going to be . My proof of the lemma that it works is that noting that this means the fourth term is going to be d(2d-1), then d(3d-2), and so forth and this satisfies arithmetic sequence condition. The eight term is hence . Therefore, we have:

Eight term=(3d-2)(4d-3)

Ninth term=(4d-3)(4d-3)

Tenth term=(5d-4)(4d-3)

Therefore, we get (4d-3)(9d-7) which we want equal to 646. d=5 works (646=2*17*19 using W|A).

Therefore, we get, ninth term of (17)^2, tenth term of 21*17, eleventh term of 21^2, twelve term of 21*25, thirteenth term of 25^2, fourteenth term of 25*29, fifteenth term of 29^2, sixteenth term of 29*33, seventeenth term of 33^2.

Since 33^2>1000, and 29*33<1000, , and since this is the sixteenth term, our answer is .

Set consists of consecutive integers whose sum is , and set consists of consecutive integers whose sum is . The absolute value between the greatest element of and the greatest element of is . Find . (2004 AIME I Problem 2)

**Solution(outline)**

Now, subtract those two, we get .

In an increasing sequence of four positive integers, the first three terms form an arithmetic progression, the last three terms form a geometric progression, and the first and fourth terms differ by 30. Find the sum of the four terms. (2003 AIME I Problem 8)

**Solution**

Therefore, our desired answer is the same as .

Now, since is positive, and when multiplying by and taking , we get , we do casework on . gives or contradiction. gives or , but since the first term is positive, so contradiction. Therefore, giving or .

This gives the last term (to check for all conditions) to be equal to which is clearly an integer, so hence the answer is .

## A bunch of polynomial problems and one induction

Consider the polynomials and Given that and are the roots of find (2003 AIME II)

**Solution**

By Vieta’s, . Now, or therefore . , so or .

**Solution**

I’m going to use strong induction here, and start out with the base case , which gives points and line segments. Since there are total line segments we can draw, and we must remove one we are still left with a triangle no matter what (removing one line doesn’t take away all triangles, this can be proven with taking away a diagonal giving a triangle with another diagonal and a side giving a triangle with 2 other sides and a diagonal).

I assume that it works for all values of up to . I’ll prove it works for now. First off, I claim that WLOG there is two points next to each other that are connected in the regular figure. For the cases there are not, move one of the line segments so that the two points are next to each other. Everything else in the diagram stays the same, so if we prove it for the two points next to each other case, we are done.

Start out with drawing in this line in the diagram and singling out this one line segment. We note that if for the other points, that there are at least lines in this region of points, then we are done by inductive hypothesis. So assume not, and therefore there are more that points with one of the two “starting” points. Therefore, we must have at least lines, and since we already have one, we have more lines to draw. There are points that are not these starting points, and we have lines connecting through either of the points or both. Therefore, we have objects, and we have boxes, and objects, so one object must have at least objects in it by pigeonhole, so one point has a line through both of these starting points. These starting points are also connected, so we have formed a triangle and we are done .

**Solution**

Now, multiply the first by and second by to give us and . Subtracting the two gives us .

This is the same as . so we get (*)

We desire to find . Manipulate (*) to give us or . Therefore, now (**).

Now, go back to the original equation, to give us and so therefore we get and .

**Solution**

Factor into a product of linear terms. (AoPS)

**Solution**

Substitute to give , so we get , so and our factorization is .

**Solution Outline**

Using some grouping, we get desired=(c-b).

So now, inside the parenthesis, we get .

Therefore beginning expression is the same as .

We end up getting ugly starting thing=.

Note that to homogenize we take giving us .

Since the degree of that is , and I don’t see any factorizations of it, we’re done.

## Polynomial problems

Determine if , and are the three real roots of the polynomial . (Mandelbrot)

**Solution**

Show that if the roots of are rational numbers , and , then the roots of are also rational. (Intermediate Algebra)

**Solution**

Let , and be the distinct roots of . Find . (ARML)

**Solution**

Consider all lines that meet the graph of in four distinct points, , , , and . Show that is independent of the line and find it’s value. (Putnam)

**Solution**

**Solution**

Essentially, it is the same thing as

So now, we get the right term is the same as .

Since by Vieta’s, , we get the term in parenthesis equals , so our answer is . Since , we get an answer of .

## USAMO 1997 #2

Let be a triangle. Take points , , on the perpendicular bisectors of , , respectively. Show that the lines through , , perpendicular to , , respectively are concurrent.

Solution:

Consider the circles, centered at passing through . These circles exist since lie on the perpendicular bisectors and their radical axis are the perpendiculars through to , , as the radical axis is perpendicular to the line connecting the centers and the points lie on both circles. Thus they are concurrent at the radical centers.