problemsforlunch

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?

Solution

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?

Solution

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

Solution

Okay so note that $x_1=2$ , $x_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+1$ th 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+1$ th 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, . . . , n$ respectively. Prove that $r(k) = r(k-1)$ for infinitely many positive integers $k$ . (1981 K¨ursch´ak Competition)

Solution

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}-1$ unless 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.

Posted in IMO

Leave a comment

Tags: Number Theory

Complex Numbers and some Number Theory

Jan 3

Posted by Justin Stevens

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)

Solution

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)

Solution

$(\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)

Solution

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)

Solution

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 need $v_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-1$ with 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 $BC$ , $N'$ the midpoint of $CY$ , and $M,N$ the midpoints of $AZ,CX$ , respectively. Prove that $B'N' \bot MN$ .

Solution

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

Posted in AIME, Argentina Math Olympiad, Canada Math Olympiad

Leave a comment

Tags: Number Theory, Trigonometry

A bunch of inequalities

Dec 14

Posted by Justin Stevens

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)

Solution

$(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 1$ from 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)

Solution

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)

Solution

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 0$ which 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)

Solution

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_a$ , $h_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)

Solution

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)

Solution

$\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+bc$ This 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)

Solution

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).

Solution

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)

Solution

$\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)

Solution

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=c$ . $abc=1$ is given, so $a\neq 0$ and $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).

Posted in IMO, USAMO

Leave a comment

Tags: Inequalities

Some geometry AIME problems and other problems

Nov 19

Posted by Justin Stevens

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_1$ , $t_2$ , and $t_3$ in the figure, have areas 4, 9, and 49, respectively. Find the area of $\triangle ABC$ .

Solution

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$
Solution

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 $n$ equal 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.

Solution

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

(1985 AIME Problem 6)

Solution

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

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$ ?

Solution

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

Solution

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

Solution

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)

Solution

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_2$ , $x_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)

Solution

We use separation, by dividing by $xy$ to give:

$\frac{f(2x)}{x}-\frac{f(2y)}{y}=8(x^2-y^2)$ .

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)

Solution

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)

Solution

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)

Solution

$ax^3+bx^2+1=(x^2-x-1)(dx+e)$

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)

Solution

$3x^2+kxy-2y^2-7x+7y-6=(ax+by+c)(dx+ey+f)$

$ad=3$
$cf=-6$
$be=-2$
$af+cd=-7$
$bf+ce=7$

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:
$cf=-6$
$be=-2$
$3f+c=-7$
$bf+ce=7$

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=4$ , $ce=3$

We go through cases on $f$ . $f=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=3$ , $ce=4$

We go through cases on $f$ again. $f=3$ gives us $c=-16$ absurd. $f=1$ gives us $c=-10$ absurd. $f=-1$ gives us $c=-4$ . $f=-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=-1$ , $e=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)=10$ , $p(1)=10$ , and $p(2)=34$ . Find $p(0)$ . (Intermediate Algebra)

Solution

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).

Solution

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)

Solution

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

$z^4+4z^2-z+6=(z^2+az+b)(z^2+cz+d)$

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)

Solution

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

Posted in Other Posts

Leave a comment

Tags: Algebra, Geometry, Inequalities

Logarithmic, Polynomial, Sequences and Series Problems

Oct 27

Posted by Justin Stevens

Let $m$ be a positive integer, and let $a_0, a_1,\ldots,a_m$ be a sequence of reals such that $a_0=37$ , $a_1=72$ , $a_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)

Solution

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+1$ so $m=\boxed{889}$ doing simple calculations.

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

Solution

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)

Solution

$\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)

Solution

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)

Solution

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)$ .

Solution

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

Problem:

Let $x$ and $y$ be positive numbers such that $x^{\log_y(x)}=2$ and $y^{\log_x(y)}=16$ . (Bay Area Math Meet)

Solution:

Let $\log_x(y)=a$ . Therefore, we get: $x=2^a$ , $y^a=16$ , $x^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)

Solution

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 $3$ to 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 = 1$ , $F_{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)

Solution

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+b$ , $z_2^3=mz_2^2+b$ , $z_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$ .

Posted in Other Posts

Leave a comment

USAMO, AIME, Inequalities

Oct 5

Posted by Justin Stevens

The sum of the following seven numbers is exactly 19: $a_1 = 2.56$ , $a_2 = 2.61$ , $a_3 = 2.65$ , $a_4 = 2.71$ , $a_5 = 2.79$ , $a_6 = 2.82$ , $a_7 = 2.86$ . It is desired to replace each $a_i$ by an integer approximation $A_i$ , $1\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)

Solution

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$ ?

Solution

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)

Solution:

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_1=ab+ac+ad+bc+bd+cd=0=-a_5$
$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$

Posted in Other Posts

Leave a comment

Polynomials and Catan

Sep 16

Posted by Justin Stevens

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

Solution

We induct on $n$ , $n=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)

Solution

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 the $i$ th digit from the left is at most $i$ ? (For example, 12235 is such a number.) (AoPS)

Solution

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)

Solution

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 $n$ th 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)

Solution

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)

Solution

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 $2m$ consecutive 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)

Solution(outline)

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)

Solution

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 $d$ . $d=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}$ .

Posted in AIME, ARML

Leave a comment

Tags: Algebra, Combinatorics

A bunch of polynomial problems and one induction

Sep 9

Posted by Justin Stevens

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)

Solution

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=3$ . $a_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)

Solution

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+1$ objects, 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)

Solution

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)

Solution

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)

Solution

Let it be $f(x,a,b,c)$ then $f(a,a,b,c)=0$ (left for the reader to check). Therefore $x-a$ divides 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)

Solution

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=0$ contradiction). Subtract these two to give $x^2-y^2=\frac{y}{x}-\frac{x}{y}=\frac{y^2-x^2}{xy}$ , so $xy=-1$ since $|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}$ .

Posted in AIME

Leave a comment

Tags: Algebra, Combinatorics

Polynomial problems

Sep 2

Posted by Justin Stevens

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)

Solution

$(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)

Solution

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)

Solution

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{p+q}{r}+\frac{p+r}{q}+\frac{r+q}{p})-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)

Solution

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

Posted in ARML, Mandelbrot, Putnam

Leave a comment

USAMO 1997 #2

Aug 17

Posted by sjaelee

Let $ABC$ be a triangle. Take points $D$ , $E$ , $F$ on the perpendicular bisectors of $BC$ , $CA$ , $AB$ respectively. Show that the lines through $A$ , $B$ , $C$ perpendicular to $EF$ , $FD$ , $DE$ respectively are concurrent.

Solution:

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 $EF$ , $FD$ , $ED$ 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.