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 1, 2, 3, \dots, 1993 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?

int x=101, y=3*floor(x/4);draw(Arc(origin, 1, 360*(y-3)/x, 360*(y+4)/x));int i;for(i=y-2; i<y+4; i=i+1) {dot(dir(360*i/x))...


From the point 1, the distance to each must be the same \pmod{2000}.Therefore, 2+3+\cdots 1993=2+3+\cdots+x letting the smallest be x.

Therefore, (x+1)+\cdots+1993\equiv 0\pmod{2000}

Therefore, (1993-x)(\frac{x+1994}{2})\equiv 0\pmod{2000} or (1993-x)(x+1994)\equiv 0\pmod{4000}.

Note that 2 and 5 can’t divide \gcd(1993-x, x+1994) using basic Euclid’s, therefore, 1993-x\equiv 0\pmod{25} and x+1994\equiv 0\pmod{16} or 1993-x\equiv 0\pmod{16} and x+1994\equiv 0\pmod{25} (unless one of them is 0\pmod{4000} which will be obviously not true after doing computations).

The first gives x\equiv 1993\pmod{25}\equiv 18\pmod{25} and x\equiv 6\pmod{25}. The second gives x\equiv 9\pmod{16}, x\equiv 6\pmod{25}.

The first gives x=118 (after doing some simple cases). For the second, we get a cycle of:6, 31, 56, 81, 106, 131 which mod 16 gives us 6, -1, 8, 1, 10, 3 therefore we are done and the answer is \boxed{118}.

Two positive integers differ by 60. 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?


x-y=60 and \sqrt{x}+\sqrt{y}=\sqrt{z}. We therefore get \sqrt{y+60}+\sqrt{y}=\sqrt{z}. Let \sqrt{y+60}=m\sqrt{n} and \sqrt{y}=a\sqrt{b}. We therefore get b=n when n and b are perfect squares.Therefore, y+60=m^2*n and y=a^2*n. Therefore, 60=(m^2-a^2)*n.

We want to maximize m^2*n. We have either n is a multiple of 4, or odd (theorem on perfect squares). In the first case, n=4, 12, 20, 60 or n=1,3,5, 15.

However, n=60 gives m^2-a^2=1 which gives a=0 which definitely isn’t maximal and same with n=15. Also, n=1,4 gives y being a perfect square and y+60 so that’s absurd.

Therefore, n=3, 5, 12, 20. The first case gives us m^2-a^2=20 which gives m-a=2, m+a=10 for maximum, or m=6. Therefore, m^2*n=108 in this case.

n=5 gives m^2-a^2=12 or m=4 as maximum therefore m^2*a=80.

n=12 gives m^2-a^2=5 or m=3 as maximum therefore m^2*a=108

n=20 gives m^2-a^2=3 or m=2 as maximum therefore m^2*a=80

Therefore, maximum value of m^2*a is 108 in all cases. Therefore, we get y=48 therefore the sum is \boxed{156}.

ISL 1995 S3:

For an integer x \geq 1, let p(x) be the least prime that does not divide x, and define q(x) to be the product of all primes less than p(x). In particular, p(1) = 2. For x having p(x) = 2, define q(x) = 1. Consider the sequence x_0, x_1, x_2, \ldots defined by x_0 = 1 and

x_{n+1} = \frac{x_n p(x_n)}{q(x_n)}for n \geq 0. Find all n such that x^n = 1995.


Okay so note that x_1=2x_2=3. Then x_3=\frac{3*2}{1}=6=2*3. We let this be 11. Then, x_4=\frac{3*2*5}{3*2*1}=5 let this be 100. I will prove in general the correspondence between binary numbers.Assume via induction that this binary pattern holds. The base case is proved above. Now, assume it holds for the set x_{2^k} to x_{2^{k+1}} and I prove that it works for x_{2^{k+1}} to x_{2^{k+2}}.

Note that the numbers without the factor of the k+1th prime (this is the leading factor) are going to create the group 2^{k+1} to 3*2^k by induction hypothesis. Also, we get that for 3*2^k to 2^{k+2} , we get an added factor of the k+1th prime by all these numbers, therefore we are done by induction.

1995=3*5*7*19. Therefore, putting this in this form of induction, we get (19)(17)(13)(11)(7)(5)(3)(2)_2 (where we only include digits which are in the prime factorization). Therefore, we get 10001110_2. This is 2^7+2^3+2^2+2=\boxed{142}.

For a positive integer n, let r(n) denote the sum of the remainders when n is divided by 1, 2, . . . , nrespectively. Prove that r(k) = r(k-1) for infinitely many positive integers k. (1981 K¨ursch´ak Competition)


Okay so note that r(3)=r(4)=1 and r(7)=r(8)=8 therefore I desire to prove n=2^k always works.

For r(2^k), we compare remainders with r(2^k-1). Starting with 2^k\div 2^{k-1}+1 we are going to get a sum starting with 2^{k-1}-1 and going down, which is the same with 2^k-1\div 2^{k-1} and going down. Also, 2^k\div 2^{k-1} gives 0, therefore we are going to prove that from 2^{k-1}-1 down they are the same.

We are going to have the remainder when 2^k divides a number always to be 1 more than 2^{k}-1unless the number we divide by divides 2^k. This happens only for 2^1, 2^2, \cdots 2^{k-2} and in this case we get 2^k remainder being 0 and 2^{k}-1 remainder being 2^m-1. Therefore, summing this up we get 2^{k-1}-2-(k-2)=2^{k-1}-k.

When it doesn’t divide this, we get (2^{k-1}-1)-1-(k-2) 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 a_{}^{}b_{}^{}c_{}^{} be the three sides of a triangle, and let \alpha_{}^{}\beta_{}^{}\gamma_{}^{}, be the angles opposite them. If a^2+b^2=1989^{}_{}c^2, find \frac{\cot \gamma}{\cot \alpha+\cot \beta} (1989 AIME #10)


Use the hint in the book to turn all the \cot into \cos and \sin. Then, use Law of cosines to give us c^2=a^2+b^2-2ab\cos(\gamma) or therefore \cos(\gamma)=\frac{994c^2}{ab}. Next, we are going to put all the sin’s in term of \sin(a). We get \sin(\gamma)=\frac{c\sin(a)}{a}. Therefore, we get \cot(\gamma)=\frac{994c}{b\ sin a}.

Next, use Law of Cosines to give us b^2=a^2+c^2-2ac\cos(\beta). Therefore, \cos(\beta)=\frac{a^2-994c^2}{ac}. Also, \sin(\beta)=\frac{b\sin(a)}{a}. Hence, \cot(\beta)=\frac{a^2-994c^2}{bc\sin(a)}.

Lastly, \cos(\alpha)=\frac{b^2-994c^2}{bc}. Therefore, we get \cot(\alpha)=\frac{b^2-994c^2}{bc\sin(a)}.

Now, \frac{\cot(\gamma)}{\cot(\beta)+\cot(\alpha)}=\frac{\frac{994c}{b\sin a}}{\frac{a^2-994c^2+b^2-994c^2}{bc\sin(a)}}. After using a^2+b^2=1989c^2, we get \frac{994c*bc\sin a}{c^2b\sin a}=\boxed{994}.

For how many positive integers n less than or equal to 1000 is (\sin t+i\cos t)^n=\sin(nt)+i\cos(nt) true for all real t?  (2005 AIME II Problem 9)


(\sin t+i\cos t)^n=\sin(nt)+i\cos(nt)
\implies (-\cos t+i\sin t)^n=i^n(\sin(nt)+i\cos(nt)).
\implies (-1)^n(\cos nt-i\sin nt)=i^n(\sin(nt)+i\cos(nt)).
\implies (-1)^n=i^{n+1} and (-1)^n*-i=i^n. The second equation gives (-1)^n=-i^{n-1}=i^{n+1} which is the same as the first.
Therefore n\equiv 1\pmod{4} or n\equiv 3\pmod{4}… however, testing n\equiv 3\pmod{4}gives -1=1 and n\equiv 1\pmod{4} gives -1=-1 therefore, n\equiv 1\pmod{4} which gives \boxed{250} solutions.
The equation z^6+z^3+1=0 has one complex root with argument \theta between 90^\circ and 180^\circ in the complex plane. Determine the degree measure of \theta. (1984 AIME Problem 8)


We get that z must be a 9th root of unity but not a 3rd root of unity. Therefore, we find z=e^{\frac{8\pi}{9}i} so the answer is \frac{8*180}{9}=\boxed{160^\circ}.
Given that z is a complex number such that z+\frac 1z=2\cos 3^\circ, find the least integer that is greater than z^{2000}+\frac 1{z^{2000}}. (2000 AIME Problem 9)


Use the hint to solve for z to give (z-\cos(3^\circ))^2=-\sin^2(3^\circ) or therefore z-\cos(3^\circ)=i\sin(3^\circ). Hence, z=\text{cis}(3^\circ).

z^{2000}=\text{cis}(6000^\circ)+\frac{1}{\text{cis}(6000^\circ)}=\frac{-1}{2}+\frac{\sqrt3}{2}i+\frac{1}{\frac{-1}{2}+\frac{\sqrt3}{2}i}=-1 (after simplifying) so an answer of \boxed{0}.

a. Prove that \sum_{i=1}^{n}(\frac{1}{i}) is never an integer for n\ge 2.
b. Prove that \sum_{i=1}^{n+1}(\frac{1}{2i-1}) is never an integer for n\ge 1.


Lemma (from dinoboy): If v_p(a)<v_p(b) then v_p(a+b)=v_p(a).
Proof: This is pretty simple, let v_p(a)=x, v_p(b)=y, then a=p^x*q and b=p^y*z. Also, x<y. Therefore, a+b=p^x(q+p^{y-x}*z) and since \gcd(q,p)=1, we have v_p(a+b)=x=v_p(a) \Box.

We now have 1+\frac12+\frac13+\cdots \frac{1}{n}=\frac{n!+\frac{n!}{2}+\cdots \frac{n!}{n}}{n!}.

Now, using the Lemma v_2(n!+\frac{n!}{2})=v_2(\frac{n!}{2}), and then continue on in this manner we are going to get the highest power of 2 in the denominator, therefore we have v_2(\frac{n!}{2^{\lfloor \log_2(n) \rfloor}}). We needv_2(\frac{n!}{2^{\lfloor \log_2(n) \rfloor}}) \ge v_2(n!), however, for this to be true we need -\lfloor \log_2(n) \rfloor\ge 0 however since n\ge 2 this is false.

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


Let 1*3*5*7*\cdots (2n+1)=(2n+1)!! (I think this is the right notation).

We therefore get \frac{\frac{(2n+1)!!}{1}+\frac{(2n+1)!!}{3}+\frac{(2n+1)!!}{5}+\cdots \frac{(2n+1)!!}{2n+1}}{(2n+1)!!}

v_3((2n+1)!!+\frac{(2n+1)!!}{3})=v_3(\frac{(2n+1)!!}{3}). Now, v_3(\frac{(2n+1)!!}{3}+(\frac{(2n+1)!!}{5}+\frac{(2n+1)!!}{7})=v_3(\frac{(2n+1)!!}{3}) because v_3(\frac{(2n+1)!!}{3})<v_3(\frac{12(2n+1)!!}{35}).

Continue on in this manner of grouping to give us v_3(\frac{(2n+1)!!}{3^{\lfloor \log_3(2n+1) \rfloor}})=v_3((2n+1)!!)-\lfloor \log_3(2n+1) \rfloor. We need this to be greater than or equal to v_3((2n+1)!!) or therefore, -\lfloor \log_3(2n+1) \rfloor\ge0 which is obviously false because n\ge 1.

Prove that 2^{n - 1} divides n! if and only if n = 2^{k - 1} for some positive integer k. (Canada 1985 #4)
We look at the power of 2 in both numbers. v_2(2^{n-1})=n-1 and v_2(n!)=\sum_{i=1}^{\infty}(\lfloor \frac{n}{2^i} \rfloor). We have v_2(n!) \ge v_2(2^{n-1}) from the given statement.

Let \lfloor \log_2(n) \rfloor=p.

We have \sum_{i=1}^{\infty}(\lfloor \frac{n}{2^i} \rfloor)=\sum_{i=1}^{p}(\lfloor \frac{n}{2^i} \rfloor) \le \sum_{i=1}^{p}(\frac{n}{... (with equality when n=2^m for some non-negative integer m= \frac{n(2^p-1)}{2^p}= n-\frac{n}{2^p}. We have n\ge 2^p (with equality again when n=2^m). Therefore, as a conclusion of this long inequality chain, \sum_{i=1}^{\infty}(\lfloor \frac{n}{2^i} \rfloor)\le n-1with equality when n=2^m. Therefore, at most we will have equality which holds when n=2^m(as we need for it to be greater).

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

Given the triangle ABC we consider the points X,Y,Z such that the triangles ABZ,BCX,CAZ are equilateral, and they don’t have intersection with ABC. Let B' be the midpoint of BCN' the midpoint of CY, and M,N the midpoints of AZ,CX, respectively. Prove that B'N' \bot MN.


Hints from AoPS

127) Let A be the origin. What must be true about (m-n)/(n'-b') if and only if \overlin{MN} \perp \overline{B'N'}?
85) If you’re stuck with a ratio that you’d like to show is inamginary, here’s a hint. If \frac{z_1}{z_2}=\frac{z_3}{z_4}=k, then what does \frac{z_1b+z_3c}{z_2b+z_4c} equal?

Let A be the origin

We desire: \frac{m-n}{b'-n'} being imaginary.

We know: b-a=\zeta(z-a)\implies b=\zeta*z

Also, x-c=\zeta(b-c) and y=\zeta(c).

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

m=\frac{z+a}{2}=\frac{\frac{b}{\zeta}+a}{2}. Next, n=\frac{x+c}{2}=\frac{2c+\zeta(b-c)}{2}. Also, b'=\frac{b+c}{2} and n'=\frac{c+y}{2}=\frac{c+\zeta(c)}{2}.

\frac{m-n}{b'-n'}=\frac{\frac{b}{\zeta}-2c-\zeta(b-c)}{b-\zeta*c} which we need to be imaginary.

This is the same thing as \frac{\frac{b}{\zeta}-2c-\zeta(b)+\zeta*c}{b-\zeta*c}

This is also the same as \frac{b-\zeta^2(b)-2\zeta*c+\zeta^2*c}{b\zeta-\zeta^2*c}

Therefore, we get \frac{b(1-\zeta^2)+c(\zeta^2-2\zeta)}{b\zeta+c(-\zeta^2)}

We now prove \frac{1-\zeta^2}{\zeta}=\frac{\zeta^2-2\zeta}{-\zeta^2}.

This is crucial in the next part of the problem.

\frac{1-\zeta^2}{\zeta}=\frac{\zeta-2}{-\zeta} or 1-\zeta^2=-\zeta+2 Therefore, we get \zeta^2-\zeta+1=0 which is true by the definition of \zeta.

Yay, lemma proven.

Find \frac{bz_1+cz_3}{bz_2+cz_4} where \frac{z_1}{z_2}=\frac{z_3}{z_4}.

We note that letting this value be k, we get z_1=kz_2.

Therefore, we have \frac{bkz_2+ckz_4}{bz_2+cz_4}=k.

Therefore, we must now prove that \frac{1-\zeta^2}{\zeta} is imaginary.

Since z is a primitive 6th root of unity, we get z=e^{\frac{\pi}{3}i} or z=e^{\frac{5\pi}{3}i}.

Therefore, z=\frac{\sqrt3}{2}+\frac{i}{2} or z=\frac{1}{2}-\frac{i\sqrt3}{2}.

In the first case, we get z^2=e^{\frac{2\pi}{3}i} or therefore it is the same as \frac{-1}{2}+\frac{\sqrt3}{2}i

We then get \frac{\frac32-\frac{\sqrt3}{2}i}{\frac{\sqrt3}{2}+\frac{i}{2}}
= \frac{3-\sqrt3*i}{\sqrt3+i}=\frac{(3-\sqrt3*i)(\sqrt3+i)}{4}=\frac{3-4\sqrt{3}i-3}{4}=-\sqrt{3}i.

In the second case, we get z^2=e^{\frac{4\pi}{3}i}=-\frac{1}{2}-\frac{\sqrt3}{2}i.
Also, we get \frac{1-z^2}{z}=\frac{3+\sqrt3i}{1-\sqrt3i}=\frac{(3+\sqrt3i)(1+\sqrt3i)}{4}=\frac{4\sqrt3i}{4}=\sqrt3i.

We are finally done. \Box.

A bunch of inequalities

Let a, b, c > 0. Prove that (a^5 - a^2 + 3)(b^5 - b^2 + 3)(c^5 - c^2 + 3) \geq (a + b + c)^3. (2004 USAMO #5)


(a^2-1)(a^3-1)\ge 0 because (a-1)^2(a+1)(a^2+a+1)\ge 0 because a>0. (This was the first hint from the AoPS book)Now, because (a^2-1)(a^3-1)\ge 0, we have a^5-a^2-a^3+1\ge 0. Therefore, a^5-a^2+3\ge a^3+2.Now, we desire (a^3+2)(b^3+2)(c^3+2)\ge (a+b+c)^3 which is directly true by Holder’s.

Prove that for all positive real numbers a,b,c,\frac{a}{\sqrt{a^2 + 8bc}} + \frac{b}{\sqrt{b^2 + 8ca}} + \frac{c}{\sqrt{c^2 + 8ab}} \geq 1.(IMO 2001 #2)Solution

We use the technique found on page 3 of the online math circle lecture: http://onlinemathcircle.com/wp-content/ … older1.pdfFrom Holder’s, (\sum(\frac{a}{\sqrt{a^2+8bc}}))^2(a(a^2+8bc)+b(b^2+8ca)+c(c^2+8ab))\ge (a+b+c)^3.Now, we have (\sum(\frac{a}{\sqrt{a^2+8bc}}))^2 \ge \frac{(a+b+c)^3}{a(a^2+8bc)+b(b^2+8ca)+c(c^2+8ab)}.

We have our desired \sum \frac{a}{\sqrt{a^2+8bc}}\ge 1\iff \frac{(a+b+c)^3}{a(a^2+8bc)+b(b^2+8ca)+c(c^2+8ab)}\ge 1from above.

Therefore, we now have to prove \frac{(a+b+c)^3}{a(a^2+8bc)+b(b^2+8ca)+c(c^2+8ab)}\ge 1. We desire a^3+b^3+c^3+3a^2b+3ab^2+3a^2c+3ac^2+3b^2c+3bc^2+6abc\ge a^3+b^3+c^3+24abc.

Therefore, we now want 3a^2b+3ab^2+3a^2+3ac^2+3b^2c+3bc^2\ge 18abc which is true by AM-GM.


Let a,b,c be the side lengths of a triangle. Prove that \sum \frac{a}{3a-b+c}\ge 1. (Samin Riasat)Solution

Use Ravi’s transformations with a=x+y, b=x+z, c=y+z. Therefore, we now desire \sum \frac{x+y}{3x+3y-x-z+y+z}\ge 1 or \sum \frac{x+y}{2x+4y}\ge 1. We now have \frac{x+y}{2x+4y}=\frac{1}{4}+\frac{\frac{x}{2}}{2x+4y}.Therefore, we now desire \sum \frac{x}{2x+4y}\ge \frac12. We can now just apply Titu’s:\sum \frac{x}{2x+4y}=\sum \frac{x^2}{2x^2+4xy}\ge \frac{(x+y+z)^2}{2(x^2+y^2+z^2+2xy+2yz+2xz)}=\frac12, and we are done.
Prove that (ab+ac+bc)(a+b+c)^4\le 27(a^3+b^3+c^3)^2 for a,b,c\ge 0. (Source: WOOT)Solution

By Power Mean or Holder’s, we have 3(a^3+b^3+c^3)^2\ge (a^2+b^2+c^2)^3 (try to find the way that both inequalities are applied!) Now, 27(a^3+b^3+c^3)^2\ge 9(a^2+b^2+c^2)^3.Now, we want 9(a^2+b^2+c^2)^3\ge (ab+ac+bc)(a+b+c)^4.9(a^2+b^2+c^2)^3\ge 9(a^2+b^2+c^2)^2(ab+ac+bc)\ge (ab+ac+bc)(a+b+c)^4\iff 9(a^2+b^2+c^2)^2\ge (a+b+c)^4. This is true iff 3(a^2+b^2+c^2)\ge (a+b+c)^2 which is true by a^2+b^2+c^2\ge ab+ac+bc (or power mean if you like).

Let x,y,z be positive real numbers such that z=x+y. Prove that (x^2+y^2+z^2)^3\ge 54x^2y^2z^2. (Source: Mathematical Database)Solution

There is probably a method using Holder’s, but I want to use the finding equality method.I find one case of equality is when x=y=\frac{z}{2}. So use AM-GM, with the equality case to give (x^2+y^2+\frac{z^2}{4}+\frac{z^2}{4}+\frac{z^2}{4}+\frac{z^2}{4})^3\ge (6\sqrt[6]{\frac{x^2y^2z^8}{4^4}})^3=\frac{6^3}{4^3}*x....We now want \frac{6^3}{4^2}*xyz^4\ge 54x^2y^2z^2. Therefore, we need xyz^4\ge 4x^2y^2z^2 or z^2\ge 4xy. Therefore, we need (x+y)^2\ge 4xy which can be proven many ways.

et a,b, and c be positive real numbers. Prove that, \frac{a}{\sqrt{a+2b}}+\frac{b}{\sqrt{b+2c}}+\frac{c}{\sqrt{c+2a}}\ge \sqrt{a+b+c}. (Vasile Cirtoaje)Solution

We use the same method on page 3 of the onlinemathcircle Holder document.By Holder’s, \sum_{cyc}(\frac{a}{\sqrt{a+2b}})^2\sum_{cyc}(a(a+2b))\ge (a+b+c)^3. Therefore, \sum_{cyc}(\frac{a}{\sqrt{a+2b}})^2\ge \frac{(a+b+c)^3}{\sum_{cyc}(a(a+2b)}=a+b+c, and we are done.

Prove that 2a^2+3b^2+6c^2\ge (a+b+c)^2 (Online Math Circle)


Use Holder’s to give us (\frac{1}{2}+\frac{1}{3}+\frac{1}{6})(2a^2+3b^2+6c^2)(a+b+c)\ge (a+b+c)^3 and we are done.

Let a,b,c be positive real numbers. Prove that, \frac{a+\sqrt{ab}+\sqrt[3]{abc}}{3}\le \sqrt[3]{a*\frac{a+b}{2}*\frac{a+b+c}{3}}. (Online Math Circle)


We think of what terms we want on the greater side to produce the respective terms on the less than side in Holder’s.We get a*\frac{a+b}{2}*\frac{a+b+c}{3}=(\frac{a}{3}+\frac{a}{3}+\frac{a}{3})(\frac{a}{3}+\frac{a+b}{6}+\frac{b}{3})(\frac{a}{3}+\fra....All the terms match up nicely when using Holder’s, besides for \frac{a+b}{6}. We note that \frac{a+b}{6}\ge \frac{\sqrt{ab}}{3}by AM-GM, so now we try to put this into the equation above, and we find that it works out nicely.

Therefore, a*\frac{a+b}{2}*\frac{a+b+c}{3}\ge (\frac{a}{3}+\frac{a}{3}+\frac{a}{3})(\frac{a}{3}+\frac{\sqrt{ab}}{3}+\frac{b}{3})(\frac{a... (AM-GM)
\ge \frac{(a+\sqrt{ab}+\sqrt[3]{abc}))^3}{3^3} (Holder’s)

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

For any real numbers x,y>1, prove that \frac{x^2}{y-1}+\frac{y^2}{x-1}\ge 8. (Russia 1992)Solution

By Titu’s, \frac{x^2}{y-1}+\frac{y^2}{x-1}\ge \frac{(x+y)^2}{x+y-2}.Therefore, we want to prove (x+y)^2\ge 8(x+y-2)\iff (x+y)^2-8(x+y)+16\ge 0\iff (x+y-4)^2\ge 0which is true.
Let a,b,c be real numbers such that a+b, b+c and a+c are non-negative. Prove that, \frac32\ge \sqrt{a+b}+\sqrt{b+c}+\sqrt{a+c}-(a+b+c). (Online Math Circle)Solution

The constant on the LHS is weird. Try letting x=a+b, y=b+c, z=a+c, then we want \frac32\ge \sqrt{x}+\sqrt{y}+\sqrt{z}-(\frac{x+y+z}{2}).We know perfectly how to proceed. If \frac12\ge \sqrt{x}-\frac{x}{2} for all positive x, then we are done. We must find the positive max of \sqrt{x}-\frac{x}{2}. Let x=y^2, giving us y-\frac{y^2}{2}=\frac{2y-y^2}{2}. Now, we must maximize 2y-y^2=-((1-y)^2-1) which has max at y=1 giving the value of 1. Therefore, y-\frac{y^2}{2} \le \frac12 as desired, and we are done.

Let x,y,z be real numbers such that xyz=1. Prove that (x^2+1)(y^2+1)(z^2+1)\ge (1+\frac{x}{y})(1+\frac{y}{z})(1+\frac{z}{x}). (Centro American Math Olympiad, 2009)


Rewrite the RHS as (x+y)(y+z)(x+z).Now, expand both sides to give us \frac{[2,2,0]+[2,0,0]}{2}+2\ge [2,1,0]+2\iff \frac{[2,2,0]+[2,0,0]}{2}\ge [2,1,0](using symmetric sum notation).Use the well known \frac{[p]+[q]}{2}\ge [\frac{p+q}{2}] (from http://www.math.ust.hk/excalibur/v11_n1.pdf page 2, fact) to give us \frac{[2,2,0]+[2,0,0]}{2}\ge [\frac{4}{2}, \frac{2}{2}, 0]=[2,1,0] as desired.

Let h_ah_b and h_c be the altitudes of triangle ABC and let r be its inradius. Prove that, h_a+h_b+h_c\ge 9r. (Puerto Rico TST 2009)Solution

[ABC]=\frac{ah_a}{2}\implies h_a=\frac{2[ABC]}{a} and similarly, h_b=\frac{2[ABC]}{b} and h_c=\frac{2[ABC]}{c}.Also, rs=[ABC]\implies r=\frac{[ABC]}{s}.Therefore, h_a+h_b+h_c\ge 9r \iff \frac{2[ABC]}{a}+\frac{2[ABC]}{b}+\frac{2[ABC]}{c}\ge 9\frac{[ABC]}{\frac12(a+b+c)}

This is the same as \frac{2}{a}+\frac{2}{b}+\frac{2}{c}\ge \frac{18}{a+b+c} which is true by Cauchy (Titu’s).

Let a,b,c be positive reals such that abc=1. Prove a^2+b^2+c^2\ge a+b+c. (Source: Online Math Circle)


Using Cauchy (or QM-AM which is derived from cauchy), to give (a^2+b^2+c^2)(1^2+1^2+1^2)\ge (a+b+c)^2
\implies (a^2+b^2+c^2)\ge \frac{(a+b+c)^2}{3}.Now, we need \frac{(a+b+c)^2}{3}\ge a+b+c\iff a+b+c\ge 3, which is true by AM-GM, so we are done.

Let a,b,c be positive reals such that a^2+b^2+c^2=3. Prove that \frac{1}{1+ab}+\frac{1}{1+ac}+\frac{1}{1+bc}\ge \frac32. (Belarus IMO TST 1999)


\frac{1}{1+ab}+\frac{1}{1+ac}+\frac{1}{1+bc}\ge \frac{9}{3+ab+ac+bc} by Cauchy (Titu’s). We now need \frac{9}{3+ab+ac+bc}\ge \frac32\iff 6\ge 3+ab+ac+bcThis is the same as needing 3\ge ab+ac+bc which is true by a^2+b^2+c^2\ge ab+ac+bc.

For arbitrary positive numbers a,b,c, prove that \frac{a}{b+2c}+\frac{b}{c+2a}+\frac{c}{a+2b}\ge 1 (1999 Czech and Slovak Republic)


This was fun.By Cauchy, (\frac{a}{b+2c}+\frac{b}{c+2a}+\frac{c}{a+2b})(a(b+2c)+b(c+2a)+c(a+2b))\ge (a+b+c)^2. Therefore, \frac{a}{b+2c}+\frac{b}{c+2a}+\frac{c}{a+2b}\ge \frac{a^2+b^2+c^2+2ab+2ac+2bc}{3ab+3ac+3bc}(doing some simplification). Also, a^2+b^2+c^2\ge ab+ac+bc, therefore, \frac{a}{b+2c}+\frac{b}{c+2a}+\frac{c}{a+2b}\ge \frac{3ab+3ac+3bc}{3ab+3ac+3bc}=1 as desired.

Let a, b, c, d be positive real numbers with a + b + c + d = 1. Prove that, \frac{a^2}{a+b}+\frac{b^2}{b+c}+\frac{c^2}{c+d}+\frac{d^2}{a+d}\ge \frac12. (Ireland 1999).


Use Cauchy (or Titu’s) to give \frac{a^2}{a+b}+\frac{b^2}{b+c}+\frac{c^2}{c+d}+\frac{d^2}{a+d}\ge \frac{(a+b+c+d)^2}{2(a+b+c+d)}=\frac12.

Let a,b,c be positive reals. Prove that \frac{a^2}{c}+\frac{b^2}{a}+\frac{c^2}{b}\ge a+b+c. (Online Math Circle)


\frac{a^2}{c}+\frac{b^2}{a}+\frac{c^2}{b}\ge \frac{(a+b+c)^2}{a+b+c}=a+b+c.

Let a,b,c be positive reals such that abc=1. Prove that \frac{a}{(a+1)(b+1)}+\frac{b}{(b+1)(c+1)}+\frac{c}{(c+1)(a+1)}\ge \frac34. When is there equality?
(French TST 2006 Problem 2)


First off, we expand the LHS and put it under a common denominator.We get \frac{a(c+1)+b(a+1)+c(b+1)}{(a+1)(b+1)(c+1)}\ge \frac34
\implies \frac{ab+ac+bc+a+b+c}{abc+ab+ac+bc+a+b+c+1}\ge \frac34
\iff ab+ac+bc+a+b+c\ge 3(abc+1)=6.Which is true by AM-GM.

Equality holds in AM-GM when ab=ac=bc=a=b=cabc=1 is given, so a\neq 0and ab=a gives b=1, and similarly (a,b,c)=(1,1,1) is where equality holds.

Let a_1, a_2, \cdots, a_n, b_1, b_2, \cdots, b_n be positive numbers with a_1+a_2+\cdots+a_n=b_1+b_2+\cdots+b_n. Prove that \frac{a_1^2}{a_1+b_1}+\cdots+\frac{a_n^2}{a_n+b_n}\ge \frac{1}{2}(a_1+a_2+\cdots+a_n). (1991 APMO)Solution

\sum_{i=1}^{n}(\frac{a_i^2}{a_i+b_i})\ge \frac{(\sum_{i=1}^{n}(a_i))^2}{\sum_{i=1}^{n}(a_i)+\sum_{i=1}^{n}(b_i))}=\frac{\sum_....
If a,b,c>0 satisfy that abc=1, prove that \frac{1+ab}{1+a}+\frac{1+bc}{1+c}+\frac{1+ac}{1+c}\ge 3.(Source: Inequalities: A mathematical olympiad approach)Solution

We get \frac{c+abc}{c+ac}+\frac{a+abc}{a+ac}+\frac{b+abc}{b+bc}\ge 3\implies \frac{c+1}{c(a+1)}+\frac{a+1}{a(c+1)}+\frac{b+1}{b(c+1)..., which is true by AM-GM and abc=1 (on the denominator).

Some geometry AIME problems and other problems

1984 AIME Problem #3:
A point P is chosen in the interior of \triangle ABC so that when lines are drawn through P parallel to the sides of \triangle ABC, the resulting smaller triangles, t_1t_2, and t_3 in the figure, have areas 4, 9, and 49, respectively. Find the area of \triangle ABC.
size(200);pathpen=black+linewidth(0.65);pointpen=black;pair A=(0,0),B=(12,0),C=(4,5);D(A--B--C--cycle); D(A+(B-A)*3/4--A+(C-A...

Note that if we have \triangle ABC\sim \triangle DEF, and \frac{AB}{DE}=k, then \frac{[ABC]}{[DEF]}=k^2. We use this to get the following ratios:
/* File unicodetex not found. */ /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki, go to Us...

Using this, we get \frac{[EBF]}{[EID]}=(\frac{9}{2})^2\implies [EBF]=4*\frac{81}{4}=81. Therefore, [BGID]=28. Similarly, we get [AIJ]=25\implies [AEDH]=12, and [HGC]=100\implies [JDFC]=42. Sum up all these areas in the picture to give us \boxed{144}.

1984 AIME Problem #9:

In tetrahedron ABCD, edge AB has length 3 cm. The area of face ABC is 15 \text{cm}^2 and the area of face ABD is 12 \text{cm}^2. These two faces meet each other at a 30^\circ angle. Find the volume of the tetrahedron in \text{cm}^3

I’ve seen this problem way too many times.

So, we find the height of \triangle ABD to be 8. Therefore, the height of the whole figure is 8\sin(30^\circ)=4, and the total area of the figure is going to be \frac13[ABC]*4=\boxed{20}.

1985 AIME Problem #4:

A small square is constructed inside a square of area 1 by dividing each side of the unit square into nequal parts, and then connecting the vertices to the division points closest to the opposite vertices. Find the value of n if the the area of the small square is exactly 1/1985.
pair A=(0,1), B=(1,1), C=(1,0), D=origin;draw(A--B--C--D--A--(1,1/6));draw(C--(0,5/6)^^B--(1/6,0)^^D--(5/6,1));pair point=( 0...

We find after doing a lot of algebra that the two intersection points on one side of the square are (\frac{n^2-2n+1}{2n^2-2n+1}, \frac{n^2-n}{2n^2-2n+1}), (\frac{n^2-n}{2n^2-2n+1}, \frac{n^2}{2n^2-2n+1}). The distance between these two points is going to be \sqrt{\frac{(n-1)^2+n^2}{(2n^2-2n+1)^2}}. This is the side length of the square, so the area of the square is \frac{(n-1)^2+n^2}{(2n^2-2n+1)^2}=\frac{1}{1985}. Therefore, 2n^2-2n+1=1985. This gives us after dividing by 2 and factoring, (n-32)(n+31)=0, so n=\boxed{32}.

As shown in the figure, triangle ABC 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 ABC.

pair A=origin, B=(14,0), C=(9,12), D=foot(A, B,C), E=foot(B, A, C), F=foot(C, A, B), H=orthocenter(A, B, C);draw(F--C--A--B--...(1985 AIME Problem 6)


Denote the point on AB to be D, the point on AC to be E and the point on BC to be F.

/* File unicodetex not found. */ /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki, go to Us...

Let CD\cap BE\cap AF=M. Note that \frac{[ADM]}{[BDM]}=\frac43=\frac{AD}{BD} because of same altitudes. Using Ceva’s on these lines intersecting at M gives us \frac43*\frac{BF}{CF}*\frac{CE}{AE}=1. Using similar logic as before, we have \frac{BF}{CF}=\frac{[BMF]}{[CMF]} and \frac{CE}{AE}=\frac{[CEM]}{[AEM]}. Therefore, we now have \frac43*\frac{35}{[CMF]}*\frac{84}{[AEM]}=1. Denote [CMF]=a and [AEM]=b now as well. Therefore, we get ab=28*4*35.

Now, \frac{[ACD]}{[CDB]}=\frac43 or therefore \frac{124+b}{65+a}=\frac43.

Hence, now 372+3b=260+4a\implies 112+3b=4a. Therefore, b=\frac{4a-112}{3}.

Substituting this back into ab=28*4*35 gives us \frac43*a(a-28)=28*4*35. This gives us a(a-28)=28*3*35. We list out the factors, which are 2*2*7*3*5*7. Therefore, we find a=2*5*7\implies a=70. Next, b=\frac{280-112}{3}\implies b=56.

Therefore, the sum of all the areas is 56+70+40+30+35+84=\boxed{315}.

1988 AIME Problem #7:
In triangle ABC\tan \angle CAB = 22/7, and the altitude from A divides BC into segments of length 3 and 17. What is the area of triangle ABC?


We get letting the altitude be h, that \tan(\angle BAC)=\frac{\frac{3}{h}+\frac{7}{h}}{1-\frac{21}{h^2}}=\frac{22}{7} (using sum formula), so after expanding and solving (I did this via hand don’t want to show work though), h=11. We want \frac{20h}{2}=\boxed{110}.

1990 AIME Problem #7:

A triangle has vertices P=(-8,5)Q=(-15,-19), and R=(1,-7). The equation of the bisector of \angle P can be written in the form ax+2y+c=0. Find a+c.


First off, using the distance formula, we find PQ=25, PR=15, QR=20 (yes, it is a right triangle, but that’s irrelevant to this problem). Use the angle bisector theorem now, to give us letting the angle bisector be PM\frac{QM}{25}=\frac{MR}{15}\implies \frac{QM}{5}=\frac{MR}{3} and QM+MR=20. Therefore, solving these, we get QM=\frac{25}{2}, MR=\frac{15}{2}. Therefore, the point M is \frac{5}{8} of the points along the line segment QR, hence it is the point (-5, \frac{-23}{2}) (using basic algebra).

Therefore, the line we want is from (-5, \frac{-23}{2}), (-8,5). The slope of this line is \frac{-11}{2}, so the equation of the line is y-5=\frac{-11}{2}(x+8). This gives us 2y-10+88+11x=0. Therefore, 2y+78+11x=0 and our answer is \boxed{89}.

1994 AIME Problem #2:

A circle with diameter \overline{PQ} of length 10 is internally tangent at P to a circle of radius 20. Square ABCD is constructed with A and B on the larger circle, \overline{CD} tangent at Q to the smaller circle, and the smaller circle outside ABCD. The length of \overline{AB} can be written in the form m + \sqrt{n}, where m and n are integers. Find m + n.


Use coordinates. the center of the largest circle is (0,0). Now, therefore, letting CD be vertical, we get the coordinates of C being (10,m) and of D being (10, -m). Now, by using the circle x^2+y^2=400, we get the two other points A and B being (-\sqrt{400-m^2}, m) and (-\sqrt{400-m^2}, -m). Therefore, setting the square to have equal side lengths, we get 2m=10+\sqrt{400-m^2}\implies m=\frac{8\pm \sqrt{64+240}}{2}. We desire 2m=AB=8+\sqrt{304} so \boxed{312}
Let f(x)=4x-x^2. Consider the sequence x_1, x_2, x_3, \cdots where x_i=f(x_{i-1}) for i>1. Compute the number of values x_1 such that x_1, x_2, and x_3 are distinct, but x_i=x_3 for all i>3.  (ARML)


Note that x_3=f(x_3) gives the desired x_i=x_3 (induction). Therefore, x_3=4x_3-x_3^2 or x_3=0, 3.

x_3=0 gives us 0=4x_2-x_2^2. Since x_3\neq x_2x_2=4 giving x_1=2 and completing this case.

x_3=3 gives us x_2^2-4x_2+3=0 or x_2=1 (since x_2\neq 3). Therefore, 4x_1-x_1^2=1 giving us x_1^2-4x_1+1=0 giving two values of x_1.

Therefore, the answer is \boxed{3}.

Find all functions f:  \mathbb{R}\to \mathbb{R} such that for all real x and y, we have yf(2x)-xf(2y)=8xy(x^2-y^2). (Saudi Arabia)


We use separation, by dividing by xy to give:


We continue with putting everything involving x on the LHS to give us \frac{f(2x)}{x}-8x^2=\frac{f(2y)}{y}-8y^2.

Therefore, \frac{f(2x)}{x}-8x^2=c for some constant c.

Therefore, f(2x)=cx+8x^3 or therefore f(x)=\frac{c}{2}x+x^3.

Substituting this into our original equation gives y(cx+8x^3)-x(cy+8y^3)=8xy(x^2-y^2)\implies 8yx^3-8xy^3=8xy(x^2-y^2)which is true.

Therefore our general form is true, and f(x)=\frac{c}{2}x+x^3 for all constants c. Since c is any constant, we can also write this in the form f(x)=cx+x^3.

10\le \log_{10}(\log_{10}(b))\le 100. If b is a positive integer, and S is the sum of the digits of the number of possible values of b, find the sum of the digits of S. (ARML)


Okay, so after doing some algebra, we get that 10^{10^{10}}\le b\le 10^{10^{100}}.

Therefore, there are 10^{10^{100}}-10^{10^{10}}+1 total ways.

First sum of the digits is going to be 9(10^{100}-10^{10})+1 looking at number of 9‘s.

Then, this is the same as 899999999\cdots 999991000\cdots0001, with 89 9‘s. Therefore, the sum is 89*9+8+1+1=\boxed{811}

Let x and y be positive real numbers such that x+y=1. Prove (1+\frac{1}{x})(1+\frac{1}{y})\ge 9. (1971 CMO #2)


By Cauchy, (1+\frac{1}{x})(1+\frac{1}{y})\ge (1+\sqrt{\frac{1}{xy}})^2.

Now, by AM-GM, \frac{x+y}{2}\ge \sqrt{xy}\implies \frac{1}{2} \ge \sqrt{xy}\implies \frac{1}{\sqrt{xy}}\ge 2. Therefore (1+\frac{1}{x})(1+\frac{1}{y})\ge (1+\sqrt{\frac{1}{xy}})^2\ge (1+2)^2=9 and we are done \Box.


.If a and b are integers such that x^2-x-1 is a factor of ax^3+bx^2+1, then find b. (AHSME)



Note that 1*d=a\implies d=a.

Now we get ax^3+bx^2+1=(x^2-x-1)(ax+e).

Comparing x coefficients, we have -e-a=0 or e=-a.

Therefore, we get ax^3+bx^2+1=(x^2-x-1)(ax-a).

Lastly, a=1\implies a=1.

Therefore, we get the x^2 term (which is a+a), to be \boxed{2}.

If 3x^2+kxy-2y^2-7x+7y-6 is the product of two linear factors with integral coefficients, find the value of k. (CMO)




These are the equations we get. From the first equation, and because we have integral coefficients, we WLOG let a=3 and d=1.

The equations are now:

From the first two equations, bcfe=12. Therefore, letting m=bf and n=ce, we have m+n=7 and mn=12. Therefore, (m,n)=(4,3), (3,4).

Case 1: bf=4ce=3

We go through cases on ff=4 gives us 12+c=-7 absurd. f=2 gives 6+c=-7 absurd. f=1 gives c=-10 absurd. f=-1 gives c=-4 absurd.f=-2 gives c=-1 which is possible. f=-4 gives c=5 absurd. Therefore, f=-2, c=-1. Furthermore, b=-2, e=-3. But be=-=2 so this isn’t possible.

Case 2: bf=3ce=4

We go through cases on f again. f=3 gives us c=-16 absurd. f=1 gives us c=-10absurd. f=-1 gives us c=-4f=-3 gives us c=2.

f=-1 gives b=-3 and c=-4 gives e=-1. But be=-2 so again absurd.

f=-3, c=2 gives us b=-1e=2. These satisfy all the equations.

Therefore k=bd+ae=(-1)(1)+(3)(2)=\boxed{5}.

Let p(x) be a fourth degree polynomial with leading coefficient 2 such that p(-2)=34, p(-1)=10p(1)=10, and p(2)=34. Find p(0). (Intermediate Algebra)


Note that letting p(x)=ax^4+bx^3+cx^2+dx+e, we have p(-2)=p(2) giving us after subtracting out equations, 16b+4d=0. Also, p(-1)=p(1) so after subtracting out equations, we have 2b+2d=0. Therefore, b=d=0, and p(x)=ax^4+cx^2+e. Also a=2 is given.

Now it’s a matter of just solving equations.

p(2)=34 gives us 32+4c+e=34 or 4c+e=2
p(1)=10 gives us 2+c+e=10 or c+e=8.

Therefore, 4c+4e=32 and therefore 3e=30\implies e=10. Also, c=-2.

Therefore, p(0)=e=\boxed{10}.

Show that the polynomial x^3+3x^2+8x+21 does not have a pair of real roots with product 1. (Intermediate Algebra).


We use a method similar to the one in the book by assuming there is. Hence x^3+3x^2+8x+21=(x^2+bx+1)(x+c)

Therefore, b+c=3. Next, bc+1=8 and c=21. Therefore, 21b+1=8 or 21b=-7. Therefore, b=\frac{-1}{3}. However, this doesn’t check with the last equation, so we are done \Box.

Solve for all complex numbers z such that z^4+4z^2+6=z. (HMMT)


After doubting any rational roots, we are going to try to put this in terms of two quadratic polynomials.


We have a+c=0 looking at z^3 terms. Therefore, a=-c. Hence, we have (z^2+az+b)(z^2-az+d).

Next, we have d+ac+b=4 or d+b-a^2=4(z^2)

ad-ab=-1 is next (z) and lastly bd=6.

From a(d-b)=-1, and db=6, we have (d,b)=(\pm 3, \pm 2), (\pm 2, \pm 3). WLOG, we let the pair be (d,b)=(3,2), (-3, -2)

The first case gives us a=-1. We now have d+b-a^2=4 as desired.

The second case gives us a=1. We have d+b-a^2=-6, so therefore (d,b)=(3,2)a=-1.

Therefore, the polynomial is hence (z^2-z+2)(z^2+z+3).

Therefore, z=\boxed{\frac{1\pm i\sqrt{7}}{2}, \frac{-1\pm i\sqrt{11}}{2}}

Prove that f(n)=1-n is the only integer-valued function defined on the integers that satisfies the following conditions: (i) f(f(n))=n for all integers n, (ii) f(f(n+2)+2)=n for all integers n, (iii) f(0)=1 (Putnam 1992 A1)


Note that from (ii), f(f(f(n+2)+2)=f(n). Now use (i) to give us f(n+2)+2=f(n).

Now, first off, f(2)+2=1, therefore f(2)=-1. Assume that f(2n)=1-2n holds for all integers n\le k. Therefore, f(2k+2)=f(2k)-2 or therefore f(2k+2)=1-2(k+1) and our induction is completed. For negative values, assume that f(2n)=1-2n holds. Therefore, f(2n-2)=1-2(n-1) completing induction as well.

Now, for odd integers, we get f(3)+2=f(1)\implies f(3)=-2.
Now, use similar induction by assuming f(2k+1)=-2k for all integers k\le n. Therefore, f(2n+3)=-2k-2 completing our induction. For negative values, assume f(2k+1)=-2k holds. Then, f(2k-1)=-2k+2=-2(k-1) completing our induction.

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


Logarithmic, Polynomial, Sequences and Series Problems

Let m be a positive integer, and let a_0, a_1,\ldots,a_m be a sequence of reals such that a_0=37a_1=72a_m=0, and a_{k+1}=a_{k-1}-\frac{3}{a_k} for k=1,2, \dots, m-1. Find m. (2005 AIME II Problem 11)


Let a_m=0. Therefore, using the recurrence, a_{m-2}*a_{m-1}=3. Now, use the recurrence on a_{m-1} to give us a_{m-2}(a_{m-3}-\frac{3}{a_{m-2}})=3 or a_{m-2}a_{m-3}=6. Using similar logic, we obtain the equation a_{m-k}a_{m-k-1}=3k. We desire to have m-k-1=0 and m-k=1 giving us a_0a_1=37*72=3k. Therefore k=37*24 and m=k+1so m=\boxed{889} doing simple calculations.

Evaluate the infinite product \prod_{n=2}^{\infty}(\frac{n^3-1}{n^3+1}). (Source: Putnam)


We get \prod_{n=2}^{k}(\frac{n-1}{n+1}*\frac{n^2+n+1}{n^2-n+1}). This is equal to \frac{1*2}{k(k+1)}*\frac{k^2+k+1}{3}.\lim_{k\to \infty}(\frac23*\frac{k^2+k}{k^2+k+1})=\boxed{\frac23}.


Find a closed form for \sum_{k=1}^{n}(\frac{k}{k^4+k^2+1}). (AoPS)


\sum_{k=1}^{n}(\frac{k}{k^4+k^2+1})=\sum_{k=1}^{n}(\frac{k}{(k^2+k+1)(k^2-k+1)}. We now use partial fraction decomposition to give us \sum_{k=1}^{n}(\frac{\frac12}{k^2-k+1}-\frac{\frac12}{k^2+k+1}). We now note that the sum cancels for each m and m+1, because the denominators are going to be the same for the plus term and the minus term. Therefore, we end up with \frac12(1-\frac{1}{k^2+k+1})=\frac12(\frac{k^2+k}{k^2+k+1}).

A sequence of numbers a_1, a_2, a_3, \cdots satisfies a_1=\frac12 and a_1+a_2+\cdots+a_n=n^2a_n for all n\ge 1. Determine the value of a_n for n\ge 1. (CMO)


Using the given equations, we have \sum_{i=1}^{n}(a_i)=n^2a_n and \sum_{i=1}^{n+1}(a_i)=(n+1)^2a_{n+1}.Subtracting the two given equations gives us a_{n+1}=n^2(a_{n+1}-a_n)+2na_{n+1}+a_{n+1}. We now get a_{n+1}(n^2+2n)=n^2a_n or a_{n+1}=\frac{n^2}{n^2+2n}a_n=\frac{n}{n+2}.

Therefore, a_{n+1}=a_1\prod_{i=1}^{n}(\frac{n}{n+2})=\frac{2*1}{(n+2)(n+1)}*a_1=\frac{1}{(n+2)(n+1)}using telescoping series. Therefore, we get a_n=\frac{1}{(n+1)n}.

Find the last three digits of the product of the positive roots of\sqrt{1995}x^{\log_{1995}x}=x^2.(1995 AIME #2)


Let y=\log_{1995}x so 1995^y=x. Therefore, we have x^y=1995^{y^2}, and x^2=1995^{2y}, so we get \sqrt{1995}*1995^{y^2}=1995^{2y}. Take \log_{1995} of both sides to give us y^2+\frac12=2y or therefore 2y^2-4y+1=0. Therefore we want the product of all x‘s. There are two values of y, therefore we have x_1x_2=1995^{y_1+y_2}=1995^{2}. We want this \pmod{1000} or \boxed{025}
Find (\log_2 x)^2 if \log_2 (\log_8 x) = \log_8 (\log_2 x).
Okay so let x=2^{2^m}. Then we get after doing some equation stuff with the given equation that m=\frac{-3}{2}\log_2(1/3).Then we get x=2^{(1/3)^{-3/2}} so \log_2(x)=(1/3)^(-3/2) so \log_2(x)^2=(1/3)^(-3)=\boxed{27}.
Let x and y be positive numbers such that x^{\log_y(x)}=2 and y^{\log_x(y)}=16. (Bay Area Math Meet)

Let \log_x(y)=a. Therefore, we get:x=2^ay^a=16x^a=y.Therefore, we have x^{a^2}=16

Therefore we get 2^{a^3}=16 so a=\sqrt[3]{4} or therefore x=2^{\sqrt[3]{4}}.

The system of equations
\begin{eqnarray*}\log_{10}(2000xy) - (\log_{10}x)(\log_{10}y) & = & 4 \\\log_{10}(2yz) - (\log_{10}y)(\log_{10}z) &am...has two solutions (x_{1},y_{1},z_{1}) and (x_{2},y_{2},z_{2}). Find y_{1} + y_{2}. (2001 AIME I Problem 9)Solution

First equation gives 3\log_{10}2+\log_{10}(x)+\log_{10}(y)-\log_{10}x\log_{10}y=4.Wait first off let’s let \log_{10}x=a, \log_{10}y=b, \log_{10}z=c.Therefore 3\log_{10}2+a+b-ab=4 or therefore 3\log_{10}2-(a-1)(b-1)=3. This is the same as (a-1)(b-1)=3\log_{10}2-3.

The second equation gives \log_{10}2+y+z-yz=1. Therefore, \log_{10}2-(y-1)(z-1)=0 or \log_{10}2=(b-1)(c-1).

Lastly, the third equation gives a+c=ac or therefore (a-1)(c-1)=1.

Multiply all the equations to give us ((a-1)(b-1)(c-1))^2=(3\log_{10}2-3)(\log_{10}2).

We care most about the variable b, so we go from teh equation (a-1)(c-1)=1 to give us (b-1)^2=(3\log_{10}2-3)(\log_{10}2). First off, simplify this, to give us \log_{10}(2000)-\log_{10}(1000)=\log_{10}2. Therefore b-1=\pm \log_{10}2. Therefore, substitute b=\log_{10}y to give us \log_{10}y-1=\log_{10}2, -\log_{10}2.

The first gives us \log_{10}y=\log_{10}(20) and second gives us \log_{10}y=\log_{10}(5) so their sum is \boxed{25}.

Determine the value of S=\sqrt{1+\frac{1}{1^2}+\frac{1}{2^2}}+\sqrt{1+\frac{1}{2^2}+\frac{1}{3^2}}+\cdots+\sqrt{1+\frac{1}{1999^2}+\frac{1}{2000^2}}. (USAMTS)Solution

First off, each term is of the form \sqrt{1+\frac{1}{x^2}+\frac{1}{(x+1)^2}}=\frac{x^2+x+1}{x^2+x} using simple algebraic manipulation. Now, the desired sum is the same thing as \sum_{x=1}^{1999}(1+\frac{1}{x^2+x})=1999+\sum_{i=1}^{1999}(\frac{1}{x}-\frac{1}{x+1})=1999+1-\frac{1}{2000} which using W|A gives us \boxed{\frac{3999999}{2000}}.

Find the value of \frac{1}{3^2+1}+\frac{1}{4^2+2}+\frac{1}{5^2+3}+\cdots. (HMMT)


First off, each term is of the form \frac{1}{x^2+x-2}=\frac{1}{(x+2)(x-1)}=\frac{1}{3}(\frac{1}{x-1}-\frac{1}{x+2}). Take the sum of this from 3to infinity to give us \frac{1}{3}(\frac{1}{2}-\frac15+\frac13-\frac16+\frac14-\frac17+\frac15-\frac18+\cdots)=\frac13(\frac12+\frac13+\frac14).This is the same as \frac13(\frac34+\frac13)=\frac{13}{36}.
Let (F_n) be the Fibonacci sequence: F_1 = F_2 = 1F_{n + 2} = F_{n + 1} + F_n (n \ge 1), and let p(x) be the polynomial of degree 990 satisfying p(k) = F_k for k = 992, 993, \dots, 1982. Prove that p(1983) = F_{1983} - 1. (ISL 1983)Solution

Row m contains the elements F_{992-m}, \cdots, F_{1982-2m} using finite differences (and simple fibonacci formulas). Therefore, the last row (990) contains the element 1. Therefore, the next element in this row is 1 and we have to add this to all of the last elements in the other rows to give us the next element in row 0. Therefore, we need to prove F_2+F_4+\cdots F_{1982}=F_{1983}-1. This is true by a well known fibonacci identity (proven via induction).

If you don’t know this identity, here’s the proof: Assume it holds for n=k. Therefore, F_2+F_4+\cdots F_{2k}=F_{2k+1}-1. We need F_2+F_4+\cdots F_{2k}+F_{2k+2}=F_{2k+3}-1. Therefore, we must have F_{2k+1}+F_{2k+2}-1=F_{2k+3}-1 which is true by definition. The last thing we need is for the base case k=1 to work, which it does, since F_2=F_3-1.

Let P(x) be a polynomial of degree 100, such that P(k) = k2^{k - 1} for k = 0, 1, \dots, 100. Find P(101).  (Duke Math Meet)

I claim that the first number in all of the rows is going to be k for row k. Here is my proof: By the handout, a_k=\sum_{i=0}^{k}(i*\binom{k}{i}). From this, we re-write this as i*\frac{k!}{i!(k-i)!}=\frac{k!}{(i-1)!(k-i)!}=k\binom{k-1}{i-1}. Therefore, our desired sum is k\sum_{i=0}^{k}(\binom{k-1}{i-1})=k2^{k-1} (note that we ignore the first term since it’s 0). We now use this same formula, but with a_{101}=\sum_{i=0}^{100}(i*\binom{101}{i})=101\sum_{i=1}^{100}(\binom{100}{i-1})=101(2^{100}-1).
Let C be the curve y^2 = x^3 and (x_1,y_1)(x_2,y_2)(x_3,y_3) three distinct collinear points on C. Show that
\frac{x_1}{y_1} + \frac{x_2}{y_2} + \frac{x_3}{y_3} = 0.
(Sweden, 1992)
Change the points into:(z_1^2, z_1^3), (z_2^2, z_2^3), (z_3^2, z_3^3)We desire to prove \frac{1}{z_1}+\frac{1}{z_2}+\frac{1}{z_3}=0. This is true if z_1z_2+z_1z_3+z_2z_3=0, so we’ll be looking at the coefficient of x in our third degree polynomial.

Note that for the points to be on a line, we need for them to satisfy y=mx+b for all of them. Let m and b be constants as they are already, and we have z_1^3=mz_1^2+bz_2^3=mz_2^2+bz_3^3=mz_3^2+b. Therefore, the roots of the polynomial x^3-mx^2+b are z_1, z_2, z_3, so hence S_2=z_1z_2+z_1z_3+z_2z_3=0 and we are done \Blacksquare.

USAMO, AIME, Inequalities

The sum of the following seven numbers is exactly 19: a_1 = 2.56a_2 = 2.61a_3 = 2.65a_4 = 2.71a_5 = 2.79a_6 = 2.82a_7 = 2.86. It is desired to replace each a_i by an integer approximation A_i1\le i \le 7, so that the sum of the A_i‘s is also 19 and so that M, the maximum of the “errors” \| A_i-a_i\|, the maximum absolute value of the difference, is as small as possible. For this minimum M, what is 100M? (1985 AIME Problem 8)


So essentially, if a number is more than 4 or less than 1, then we get the largest difference at least 1 but I can make it less than 1. We have 3m+n=14, m+n=7 solve to give m=5, n=2. Therefore we get 2.56, 2.61 going to 2 rest going to 3, therefore largest is 0.61 for answer of \boxed{61}.
Let S be a list of positive integers – not necessarily distinct – in which the number 68 appears. The average (arithmetic mean) of the numbers in S is 56. However, if 68 is removed, the average of the remaining numbers drops to 55. What is the largest number that can appear in S?
Let the set have b 1‘s and 1 68 (essentially being greedy as 68‘s bring up the average. Therefore, letting largest element in set be x, we have \frac{68+b+x}{b+2}=56. We also have \frac{b+x}{b+1}=55. Therefore, b+x=55(b+1) and 68+b+x=56(b+2). We therefore get b+x=56b+44, or therefore 56b+44=55(b+1) or b=11. We therefore get \frac{11+x}{12}=55 or therefore x=\boxed{649}.
Let a,b,c be positive real numbers. Prove that (1+\frac{a}{b})(1+\frac{b}{c})(1+\frac{c}{a})\ge 2(1+\frac{a+b+c}{\sqrt[3]{abc}}). (AoPS)Solution

Expand gives \frac{a^2b+ab^2+a^2c+ac^2+b^2c+bc^2+2abc}{abc}\ge 2+\frac{2a+2b+2c}{\sqrt[3]{abc}}.This is the equivalent of \frac{a^2b+ab^2+a^2c+ac^2+b^2c+bc^2}{abc}\ge \frac{2a+2b+2c}{\sqrt[3]{abc}}.

After expanding this out, the rest is obvious by Muirheads (\frac73, \frac43, \frac13) majorizes (2, 1, 1).

Problem:  Prove that if x_i>0 for all i then (x_1^{19}+x_2^{19}+\cdots+x_n^{19})(x_1^{93}+x_2^{93}+\cdots+x_n^{93})\ge (x_1^{20}+x_2^{20}+\cdots+x_n^{20})(x_1^{92}+\cdots....  (AoPS)15 second method

All x_m^{112} terms cancel, rest is Muirhead’s \Box.

5 minute method

Expand as before, and then you desire:\sum_{sym}(x_1^{19}*x_2^{93})\ge \sum_{sym}(x_1^{20}*x_2^{92}).

This is the equivalent of proving \sum_{sym}(x_1^{19}*x_2^{93}-x_1^{20}*x_2^{92})\ge 0 or \sum_{sym}(x_1^{19}*x_2^{92}(x_2-x_1)\ge 0.

We get this being the equivalent of proving \sum_{i,j, i>j}((x_1^{19}*x_2^{92}-x_2^{19}*x_1^{92})(x_2-x_1))\ge 0.

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

Problem:  If a and b are two of the roots of x^4+x^3-1=0, prove that ab is a root of x^6+x^4+x^3-x^2-1=0. (1977 USAMO Problem 3)
Let a,b,c,d be the roots of the original equation. Then ab, ac, ad, bc, bd, cd are the roots of the next equation is what we’re trying to prove. Note that:S_0=1=a_6.
S_2=3abcd+\sum(a^2bc+ab^2c+abc^2)=3abcd+\sum abc(a+b+c)=3abcd+\sum abc(-1-d)=-abcd-abc-abd-acd-bcd. Note that abcd=-1, and abc+abd+acd+bcd=0 (both from previous equation), so we get 1=a_4
S_3=abcd(a^2+b^2+c^2+d^2)+\sum a^2b^2c^2+\sum 2a^2b^2cd=-1*1+ (abc+abd+acd+bcd)^2-2(\sum a^2b^2cd)+2\sum 2a^2b^2cd=-1 so we get the coefficient is (-1)^3(-1)=1=a_3.
S_4=abcdS_2=-1 so the coefficient of this is -1=a_2
S_5=a^2b^2c^2d^2S_1=0 so the coefficient of this is 0=a_1.
S_6=a^3b^3c^3=-1 so the coefficient of this is -1=a_0.

Therefore, the polynomial with roots ab, ac, ad, bc, bd, cd is a_6x^6+a_5x^5+a_4x^4+a_3x^3+a_2x^2+a_1x+a_0=x^6+x^4+x^3-x^2-1 so we are done \Box

Polynomials and Catan

Show that (x-1)^2|(x^n-n(x-1)-1) where n is a positive integer.


We induct on nn=1/2 are easy to check, first gives 0 second gives (x-1)^2.

Now, assume it works for n=k, therefore we have (x-1)^2|(x^k-k(x-1)-1). We must prove (x-1)^2|(x^{k+1}-(k+1)(x-1)-1).

We have by hypothesis (x-1)^2|(x^k-kx+k-1)(x-1)=x^{k+1}-x^k-kx^2+kx+kx-k-x+1

Again, by hypothesis, (x-1)^2|(-x^k+kx-k+1), so (-x^k+kx+1) has remainder k when divided by (x-1)^2

Therefore (x-1)^2|(x^{k+1}-kx^2+kx-k+k-x).

Since (x-1)^2|(x^{k+1}-kx^2+kx-x), we can add k(x-1)^2 to it to further simplify it (with a wishful eye!), to give us (x-1)^2|(x^{k+1}-kx^2+kx-x+1+kx^2-2kx+k) or (x-1)^2|(x^{k+1}-kx-x+k), so we have proven (x-1)^2|(x^{k+1}-(k+1)x+k)

We wanted to prove (x-1)^2|(x^{k+1}-kx+k-x+1-1) or (x-1)^2|(x^{k+1}-(k+1)x+k) which is exactly what I got above, so we are done \Blacksquare.

The roots of 2x^3-19x^2+mx-54=0 are in geometric progression for some constant k. Find k. (AoPS)


Let the roots be \frac{r}{k}, r, rk. Therefore, \frac{r}{k}+r+rk=\frac{19}{2}, or r+rk+rk^2=\frac{19}{2}k, so r(1+k+k^2)=\frac{19}{2}k.

Next, \frac{r}{k}*r+\frac{r}{k}*rk+r*rk=r^2(\frac{1}{k}+1+k)=\frac{m}{2}, or r^2(1+k+k^2)=\frac{m}{2}k.

Lastly, \frac{r}{k}*r*rk=r^3=\frac{54}{2}=27, so r=3. This gives that 3(1+k+k^2)=\frac{19}{2}k. We could use this to find k, but that’s terribly un-interesting, instead we have r^2(1+k+k^2)=9(1+k+k^2)=\frac{57}{2}k or \frac{57}{2}=\frac{m}{2}\implies m=\boxed{57}.

How many 5-digit numbers are such that the digits, as read left-to-right, are non decreasing, and that theith digit from the left is at most i? (For example, 12235 is such a number.) (AoPS)


We have 5 numbers, which we let each difference be d, and we set up a one to one correspondence with a similar problem. For every spot before a sequence of )‘s (which sum up to 5), we use a ( and for every spot where we have another number added to the difference, we use a ). Therefore, we start out with a (, and the rest gives catalan numbers in the sense that it starts with a (, we must have more (‘s than )’s at all points, because this is by definition of catalan numbers, and we must have the difference total starting at 0 being less than i. Lastly, we use the non-decreasing fact by that all differences are positive, so we have C_5. We use C_n=\frac{1}{n+1}\binom{2n}{n} to give us \frac{1}{6}\binom{10}{5}=\boxed{42}.
Brazil defeats Germany in a wild World Cup final by the score of 8 to 6. Assuming the 14 goals were equally likely to be scored in any order, find the probability that the score was never tied (expect at 0-0). (AoPS)


Okay, so the total number of outcomes is going to be \binom{14}{6}. We draw a huge diagram, and get that we can never have Germany beating Brazil because if so then Brazil and Germany will be tied at a point with the final score.

Okay, so Brazil wins the first game and we get (1,0) to (8,6) without going through any points on y=x on this graph. We make a one to one correspondence with this and (0,0) to (7,6). We also make another one to one correspondence between going through (7,7) and (7,6). If it goes through (7,7) it must have gone through (7,6) so to count to (7,6), we just move up (we can’t move right since it’s a 7 \times 7 grid), so we get \frac{C_7}{\binom{14}{6}} or \boxed{\frac17}.

Prove that the number of rooted binary trees with n internal nodes is the nth Catalan number. (AoPS)

Solution(using hint)

Denote d_k to be the number of rooted binary trees with k internal nodes. We assume using strong induction that the result holds for all 0\le k\le n-1.

So now, looking at the casework that we have n-1 internal nodes on the left node to start out with, then n-2, then so forth until we get 0. This gives us \sum_{i=0}^{n-1}(d_i*d_{n-1-i}). By our inductive hypothesis, we have all of these d_j=C_j, therefore we get d_n=\sum_{i=0}^{n-1}(C_i*C_{n-1-i}) which by the recursive definition of catalan numbers is true \Blacksquare.

The expression \sqrt{\sqrt[3]{4}-1}+\sqrt{\sqrt[3]{16}-\sqrt[3]{4}} is equal to \sqrt{k} for some integer k. Find k.  (ARML)


Letting the expression be m, we want m^2.

Due to ugliness, let x=\sqrt[3]{4} for now. Therefore m^2=x^2-1+2(x-1)\sqrt{x}=(x-1)(x+1+2\sqrt{x})=(x-1)(\sqrt{x}+1)^2.

Now, letting x=\sqrt[3]{4}, we get (\sqrt[3]{4}-1)(\sqrt[3]{2}+1)^2 which is (\sqrt[3]{4}-1)(\sqrt[3]{4}+1+2\sqrt[3]{2})=\sqrt[3]{16}-1+4-2\sqrt[3]{2}=\boxed{3}.

A sequence of positive integers with a_1=1 and a_9+a_{10}=646 is formed so that the first three terms are in geometric progression, the second, third, and fourth terms are in arithmetic progression, and, in general, for all j\ge 1, the terms a_{2j-1}, a_{2j}, a_{2j+1} are in geometric progression, and the terms a_{2j}, a_{2j+1}, and a_{2j+1} are in arithmetic progression. Let the greatest term in the sequence less than 1000 be a_n. Find n+a_n. (2004 AIME II #9)


I used the book hint to experiment a bit on the second term. This hint worked quite nice!

For n=2, we get:

1,2,4,6,9, 12, 16, 20, 25, 30

Letting the second term be d, I note that the third term is going to be d^2, the fifth term is going to be (2d-1)^2, the seventh term is going to be (3d-2)^2, and the ninth term is going to be (4d-3)^2. 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 (3d-2)(4d-3). 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, a_n=29*33=957, and since this is the sixteenth term, our answer is 957+16=\boxed{973}.

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


Let the smallest element in A be a, and the smallest in B be b. Therefore, we get 2a+(m-1)=4 and 2b+2m-1=1.

Now, subtract those two, we get 2(a-b)-m=3.

We have either a-b-m=99 or a-b+m=-99.

For the first case, we get a-b=m+99, so we get m=3-2*99 absurd.

For the second case, we get a-b=-99+m, so 2(-99+m)-m=3, or m=\boxed{201}.

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)


Let the terms be a-d, a, a+d, \frac{(a+d)^2}{a}.

Then the sum is 3a+\frac{a^2+2ad+d^2}{a} or 4a+2d+\frac{d^2}{a}.

Also, \frac{(a+d)^2}{a}-a+d=30, so \frac{(a+d)^2-a^2+ad}{a}=30, or therefore \frac{3ad+d^2}{a}=30.

This also gives 3d+\frac{d^2}{a}=30.

Therefore, our desired answer is the same as 4a+30-d.

Now, since d is positive, and when multiplying by a and taking \pmod{3}, we get d\equiv 0\pmod{3}, we do casework on dd=3 gives 9+\frac{9}{a}=30 or a=\frac{1}{3} contradiction.d=6 gives \frac{36}{a}=12 or a=3, but a>d since the first term is positive, so contradiction. Therefore, d=9 giving \frac{81}{a}=3 or a=27.

This gives the last term (to check for all conditions) to be equal to \frac{(27+9)^2}{9} which is clearly an integer, so hence the answer is 4*27+30-9=\boxed{129}.

A bunch of polynomial problems and one induction

Consider the polynomials P(x)=x^{6}-x^{5}-x^{3}-x^{2}-x and Q(x)=x^{4}-x^{3}-x^{2}-1. Given that z_{1},z_{2},z_{3}, and z_{4} are the roots of Q(x)=0,find P(z_{1})+P(z_{2})+P(z_{3})+P(z_{4}). (2003 AIME II)


Note that this is S_6-S_5-S_3-S_2-S_1.

By Vieta’s, S_1=1. Now, a_4*S_2+a_3*S_1+2a_2=0 or therefore S_2+(-1)(1)-2(1)\implies S_2=3a_4*S_3+a_3*S_2+a_2*S_1+3a_1=0, so S_3-3-1=0 or S_3=4.

Next, a_4*S_4+a_3*S_3+a_2*S_2+a_1*S_1+4a_0=0, therefore S_4-4-3-4=0 so S_4=11.

Next, a_4*S_5+a_3*S_4+a_2*S_3+a_1*S_2+a_0*S_1=0. So S_5-11-4-1=0, so S_5=16. Lastly, a_4*S_6+a_3*S_5+a_2*S_4+a_1*S_3+a_0*S_2=0, so S_6-S_5-S_4-S_2=0 therefore S_6=30.

The answer is thus, 30-16-4-3-1=\boxed{6}.

2n points (where n>1 is a positive integer) are given in space, such that no 3 of them are on a line. We draw n^2+1 line segments connecting pairs of these points. Prove that there must exist a triangle whose vertices are 3 of the points and whose sides are 3 of the drawn segments.  (AoPS)


First off, WLOG let the figure be a regular figure. If it’s not, then we can just rotate the regular figure into whatever form we want and still have the triangle in it.

I’m going to use strong induction here, and start out with the base case n=2, which gives 4 points and 5 line segments. Since there are 6 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 n up to k+1. I’ll prove it works for k+1 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 2k points, that there are at least k^2+1 lines in this region of 2k points, then we are done by inductive hypothesis. So assume not, and therefore there are more that (k+1)^2+1-(k^2+1) points with one of the two “starting” points. Therefore, we must have at least 2k+2 lines, and since we already have one, we have 2k+1 more lines to draw. There are 2k points that are not these starting points, and we have 2k+1 lines connecting through either of the 2 points or both. Therefore, we have 2k+1 objects, and we have 2k boxes, and 2k+1objects, so one object must have at least \lceil \frac{2k+1}{2k} \rceil=2 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 \Blacksquare.

Let x and y be real numbers that differ in absolute value and satisfy the equations x^3=13x+3y, y^3=3x+13y. Find (x^2-y^2)^2. (Dropped AIME)


Start with multiplying the first equation by 13 second by 3 then subtracting then flip-flopping to give us:

13y^3-3x^3=160y and 13x^3-3y^3=160x.

Now, multiply the first by x and second by y to give us 13y^3x-3x^4=160xy and 13x^3y-3y^4=160xy. Subtracting the two gives us 13xy(x^2-y^2)+3(x^4-y^4)=0.

This is the same as 13xy(x^2-y^2)+3(x^2-y^2)(x^2+y^2)=0|x|\neq |y| so we get 13xy+3(x^2+y^2)=0(*)

We desire to find x^4-2x^2y^2+y^4. Manipulate (*) to give us 169x^2y^2=9(x^4+2x^2y^2+y^4) or 151x^2y^2=9x^4+9y^4. Therefore, now x^4-2x^2y^2+y^4=\frac{151}{9}x^2y^2-2x^2y^2=\frac{133}{9}x^2y^2(**).

Now, go back to the original equation, to give us x(x^2-13)=3y and y(y^2-13)=3x so therefore we get x^2=13+\frac{3y}{x} and y^2=13+\frac{3x}{y}.

Therefore we get x^2y^2=178+39(\frac{x}{y}+\frac{y}{x})=178+39(\frac{x^2+y^2}{xy}). Apply (*) to this to give \frac{x^2+y^2}{xy}=\frac{-13}{3} or therefore x^2y^2=178-169=9.

Substitute this into (**) gives us x^4-2x^2y^2+y^4=\frac{133}{9}*9=\boxed{133}.

Show that \frac{b+c}{(a-b)(a-c)}+\frac{a+c}{(b-c)(b-a)}+\frac{a+b}{(c-a)(c-b)}=0 for all distinct a, b,c .  (AoPS)


Multiply by (a-b)(a-c)(b-c) to give us the numerator equal to (b+c)(b-c)-(a+c)(a-c)+(a+b)(a-b)=b^2-c^2-(a^2-c^2)+(a^2-b^2)which is 0 so done.

Factor (x-a)^3(b-c)^3+(x-b)^3(c-a)^3+(x-c)^3(a-b)^3 into a product of linear terms. (AoPS)


Let it be f(x,a,b,c) then f(a,a,b,c)=0 (left for the reader to check). Therefore x-adivides the expression(multivariable polynomial factor theorem), and by symettry so does x-b and x-c. Also, f(x,b,b,c)=0 (again, left to reader) so a-b, a-c, b-c divides the expression, and since \deg(f)=6, we get f(x,a,b,c)=k(x-a)(x-b)(x-c)(a-b)(a-c)(b-c).

Substitute x=2, a=1, b=0, c=-1 to give 1^3(-1)^3+2^3(-2)^3+3^3(1^3)=k(1)(2)(3)(1)(2)(-1), so we get -48=-12k, so k=4 and our factorization is 4(x-a)(x-b)(x-c)(a-b)(a-c)(b-c).

Factor a^4(c-b)+b^4(a-c)+c^4(b-a). (AoPS)

Solution Outline

Hmmm so use multivariable factor theorem to get a-b, a-c, b-c are all factors.

Using some grouping, we get desired=(c-b)(a^4-ab^3-ac^3-abc^2-ab^2c+bc^3+b^2c^2+b^3c).

So now, inside the parenthesis, we get a(a^3-b^3)+(b-a)c^3+bc^2(b-a)+b^2c(b-a).

Therefore beginning expression is the same as (c-b)(b-a)(c^3+bc^2+b^2c-a(a^2+ab+b^2))=(c-b)(b-a)(c^3+bc^2+b^2c-a^3-a^2b-ab^2).

We now need an a-c as well…

We end up getting ugly starting thing=(c-b)(b-a)(c-a)(b^2+b(c+a)+(c^2+ac+a^2)).

Note that to homogenize we take (c-b)(b-a)=(a-b)(b-c) giving us (a-b)(b-c)(c-a)(a^2+b^2+c^2+ab+ac+bc).

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

Let x^3=8x+y and y^3=x+8y. If |x|\neq |y|, then find x^2+y^2. (AoPS)


So divide by x to give x^2=8+\frac{y}{x}y^2=8+\frac{x}{y} (also x\neq 0 because if so then y=0contradiction). Subtract these two to give x^2-y^2=\frac{y}{x}-\frac{x}{y}=\frac{y^2-x^2}{xy}, so xy=-1since |x|\neq |y|. Therefore, we multiply our two original equations by x to give us x^4=8x^2+xy and y^4=xy+8y^2, so x^4-8x^2+1=0 and y^4-8y^2+1=0. Therefore, (x^2-4)^2=15 and (y^2-4)^2=15, therefore we get (x^2, y^2)=(\sqrt{15}+4, -\sqrt{15}+4), (-\sqrt{15}+4, \sqrt{15}+4) (keeping in mind x^2\neq y^2 since |x|\neq |y|). In both cases, x^2+y^2=\boxed{8}.

Polynomial problems

Determine (r+s)(s+t)(t+r) if r,s, and t are the three real roots of the polynomial x^3+9x^2-9x-8. (Mandelbrot)


(r+s)(s+t)(t+r)=2rst+\sum_{sym}(r^2s)=2rst+rst(\frac{r+s}{t}+\frac{r+t}{s}+\frac{s+t}{r}).Since r+s+t=-9, we get 2rst+rst(\frac{-9-t}{t}+\frac{-9-s}{s}+\frac{-9-r}{r}) = 2rst+rst(\frac{-9}{t}+\frac{-9}{s}+\frac{-9}{r}-3)=-rst-9(rs+st+rt)
= -9(-9)-8=\boxed{73} using Vieta’s.

Show that if the roots of x^3+ax+b=0 are rational numbers m,n, and p, then the roots of mx^2+nx+p are also rational. (Intermediate Algebra)


We have m+n+p=0 from Vieta’s on the first equation. Now, we desire to have \frac{-n\pm \sqrt{n^2-4mp}}{2m} being rational, so since n and m are rational, we need \sqrt{n^2-4mp}being rational. From m+n+p=0, we have n^2=m^2+p^2+2mp. Therefore n^2-4mp=(m-p)^2, or \sqrt{n^2-4mp}=m-p which is rational so we are done \Blacksquare.

Let p,q, and r be the distinct roots of x^3-x^2+x-2=0. Find p^3+q^3+r^3. (ARML)


We get p^3+q^3+r^3=(p+q+r)^3-3(p^2q+p^2r+q^2p+q^2r+r^2p+r^2q)-6pqr=
= 1-3pqr(\frac{1-r}{r}+\frac{1-s}{s}+\frac{1-q}{q})-6pqr
= 1-3pqr(\frac{1}{r}+\frac{1}{s}+\frac{1}{s}-3)-6pqr
= 1+3pqr-3(pq+pr+rq)
= 1+3(2)-3(1)=\boxed{4}.

Consider all lines that meet the graph of y=2x^4+7x^3+3x-5 in four distinct points, (x_1, y_1)(x_2, y_2)(x_3, y_3), and (x_4, y_4). Show that \frac{x_1+x_2+x_3+x_4}{4} is independent of the line and find it’s value. (Putnam)


Let the line it’s intersecting be y=ax+b. Therefore the roots of the equation 2x^4+7x^3+x(3-a)+(-5-b)=0 are x_1, x_2, x_3, x_4. By Vieta’s, x_1+x_2+x_3+x_4=\frac{-7}{2}, so \frac{x_1+x_2+x_3+x_4}{4}=\boxed{\frac{-7}{8}} which is independent of the line since our final answer doesn’t have any a‘s or b‘s in it.
Let r_1, r_2, r_3 be the 3 zeros of the cubic polynomial x^3-x-1=0. Then, the expression r_1(r_2-r_3)^2+r_2(r_3-r_1)^2+r_3(r_1-r_2)^2 equals a rational number. Find this number.Solution

Essentially, it is the same thing as -6r_1r_2r_3+\sum_{sym}(r_1r_2^2)

So now, we get the right term is the same as r_1r_2r_3(\frac{r_1+r_3}{r_2}+\frac{r_2+r_3}{r_1}+\frac{r_1+r_3}{r_2}).

Since by Vieta’s, r_1+r_2+r_3=0, we get the term in parenthesis equals -1-1-1=-3, so our answer is -9r_1r_2r_3. Since S_3=(-1)^3(-1)=1, we get an answer of \boxed{-9}.

Let x_1 and x_2 be the roots of the equation x^2-(a+d)x+(ad-bc)=0. Show that x_1^3+x_2^3 are the roots of the equation y^2-(a^3+d^3+3abc+3bcd)y+(ad-bc)^3. (Source: Hungary)My Solution

First off, x_1x_2=(ad-bc), so therefore (x_1x_2)^3=(ad-bc)^3 matching the constant term of the desired polynomial. We now have to prove that x_1^3+x_2^3=a^3+d^3+3abc+3bcd. We now that x_1+x_2=a+d, so x_1^3+x_2^3+3x_1x_2(x_1+x_2)=(a^3+3a^2d+3ad^2+d^2).The given equation is true \iff (a^3+d^3+3abc+3bcd)+3x_1x_2(x_1+x_2)=(a^3+3a^2d+3ad^2+d^3)
\iff 3abc+3bcd+3x_1x_2(x_1+x_2)=3a^2d+3ad^2
\iff 3abc+3bcd+3(ad-bc)(a+d)=3a^2d+3ad^2
\iff 3abc+3bcd+3a^2d+3ad^2-3abc-3bcd=3a^2d+3ad^2.

Which is true, so reversing our steps we are done \Blacksquare.

USAMO 1997 #2

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


Consider the circles, centered at D,E,F passing through (B,C),(A,C),(A,B). These circles exist since D,E,F lie on the perpendicular bisectors and their radical axis are the perpendiculars through A,B,C to EFFDED 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.