[quote="dduclam"]Problem 1: Give positive numbers $ a,b,c$ satisfying $ abc = 1$. Find the maximum value of
         P=$ \sum_{cyc} \frac1{\sqrt {(1 + b)(1 + c)}}$

 Problem2: Given $ a,b,c \ged 0$ such that $ ab + bc + ca = \frac3{2}$. Prove that
        $ \sum_{cyc} \frac1{1 + a^2} \leq 2$[/quote]
Problem2 :   $ \sum_{cyc} \frac1{1 + a^2} \leq 2$ $ \Leftrightarrow \frac {a^2}{1 + a^2} + \frac {b^2}{1 + b^2} + \frac {c^2}{1 + c^2} \geq 1$ Cauchy $ (3 + (a^2 + b^2 + c^2))(\frac {a^2}{1 + a^2} + \frac {b^2}{1 + b^2} + \frac {c^2}{1 + c^2}) \geq (a + b + c)^2$ $ \therefore \frac {a^2}{1 + a^2} + \frac {b^2}{1 + b^2} + \frac {c^2}{1 + c^2} \geq \frac {(a + b + c)^2}{3 + (a^2 + b^2 + c^2)} = 1$

$ \sum_{cyc} \frac {1}{\sqrt {(1 \plus{} b)(1 \plus{} c)}}\leq \sum_{cyc} \frac {1}{\frac {2}{\frac {1}{(1 \plus{} b)} \plus{} \frac {1}{(1 \plus{} c)}} } \equal{}$
$ \equal{} \sum_{cyc} \frac {\frac {1}{1 \plus{} b} \plus{} \frac {1}{1 \plus{} c}}{2} \equal{} \frac {1}{1 \plus{} a} \plus{} \frac {1}{1 \plus{} b} \plus{} \frac {1}{1 \plus{} c}$
but equality comes only if $ (1 \plus{} b) \equal{} (1 \plus{} c) \equal{} (1 \plus{} a)$ <=> $ a \equal{} b \equal{} c \equal{} 1$
so $ \sum_{cyc} \frac {1}{\sqrt{(1 \plus{} b)(1 \plus{} c)}}\leq \frac {3}{2}$

Am i right ?

[quote="BG Yoda"]$ \sum_{cyc} \frac {1}{\sqrt {(1 \plus{} b)(1 \plus{} c)}}\leq \sum_{cyc} \frac {1}{\frac {2}{\frac {1}{(1 \plus{} b)} \plus{} \frac {1}{(1 \plus{} c)}} } \equal{}$
$ \equal{} \sum_{cyc} \frac {\frac {1}{1 \plus{} b} \plus{} \frac {1}{1 \plus{} c}}{2} \equal{} \frac {1}{1 \plus{} a} \plus{} \frac {1}{1 \plus{} b} \plus{} \frac {1}{1 \plus{} c}$
but equality comes only if $ (1 \plus{} b) \equal{} (1 \plus{} c) \equal{} (1 \plus{} a)$ <=> $ a \equal{} b \equal{} c \equal{} 1$
so $ \sum_{cyc} \frac {1}{\sqrt {(1 \plus{} b)(1 \plus{} c)}}\leq \frac {3}{2}$

Am i right ?[/quote]
 Your solution is false :D

why can't we use GM>HM then ?
1+b , 1+c and 1+a are positive ; where is the problem  :oops:

[quote="dduclam"]Problem 1: Give positive numbers $ a,b,c$ satisfying $ abc \equal{} 1$. Find the maximum value of
         P=$ \sum_{cyc} \frac1{\sqrt {(1 \plus{} b)(1 \plus{} c)}}$[/quote]

Not sure if this is right:

We have

$ \frac {\sqrt {1 \plus{} a} \plus{} \sqrt {1 \plus{} b} \plus{} \sqrt {1 \plus{} c}}{\sqrt {(1 \plus{} a)(1 \plus{} b)(1 \plus{} c)}}\le\sqrt {\frac {3(1 \plus{} a \plus{} 1 \plus{} b \plus{} 1 \plus{} c)}{(1 \plus{} a)(1 \plus{} b)(1 \plus{} c)}}$.

We will prove that $ \sqrt {\frac {3(1 \plus{} a \plus{} 1 \plus{} b \plus{} 1 \plus{} c)}{(1 \plus{} a)(1 \plus{} b)(1 \plus{} c)}}\le\frac 32$

$ \iff 3(1 \plus{} a)(1 \plus{} b)(1 \plus{} c)\ge 4(3 \plus{} a \plus{} b \plus{} c)$

$ \iff a \plus{} b \plus{} c \plus{} 6\le 3(ab \plus{} bc \plus{} ca)$

Let WLOG $ a \equal{} \frac xy, b \equal{} \frac yz, c \equal{} \frac zx$, where $ x\ge y\ge z$ are positive real numbers. Then the above inequality is equivalent to

$ \frac xy \plus{} \frac yz \plus{} \frac zx \plus{} 6\le 3\left(\frac xz \plus{} \frac yx \plus{} \frac zy\right)$

$ \iff xy^2 \plus{} yz^2 \plus{} zx^2 \plus{} 6xyz\le 3(x^2y \plus{} y^2z \plus{} z^2x)$

This is true because $ x^2y \plus{} y^2z \plus{} z^2x\ge xy^2 \plus{} yz^2 \plus{} zx^2\iff (x \minus{} y)(y \minus{} z)(x \minus{} z)\ge 0$ and $ x^2y \plus{} y^2z \plus{} z^2x\ge 3xyz$.

If we use the fact that for the max value of $ \frac{1}{\sqrt{xy}}$ ( min value of $ \sqrt{xy}$ ) we have equality between GM=HM , but this equality holds only if $ x\equal{}y$ , why don't we just deduce that the max value of $ \sum_{cyc} \frac {1}{\sqrt {(1 \plus{} b)(1 \plus{} c)}}$ holds only if $ 1\plus{}a\equal{}1\plus{}b\equal{}1\plus{}c\equal{}2$ ?

If this is wrong , tell me why , please  :blush:


limit
induction
calculus
calculus computations

Consider the sequence $\left\{ a_{n}\right\}_{n \geq 1}$, $a_{1}\in \left( 0, 1 \right)$ and $a_{n+1}= a_{n}^{3}-a_{n}^{2}+1, \, \forall n \geq 1$.

Compute $\lim_{n \to \infty}\left( a_{1}\cdot a_{2}\cdot \ldots \cdot a_{n}\right)$.

By induction on $n$ we have $a_{n+1}>a_{n}$ and $a_{n}\in (0,1)$ for all $n$.(*)

From hypothesis $a_{n+1}-1=a_{n}^{2}(a_{n}-1)$ for all $n$, so $a_{n}^{2}=\frac{a_{n+1}-1}{a_{n}-1}$ for all $n$. By this and telescopic product, we have $\prod_{k=1}^{n}a_{k}^{2}=\frac{a_{n+1}-1}{a_{1}-1}$ for all $n$. Therefore $s=\lim_{n\to+\infty}\prod_{k=1}^{n}a_{k}=\sqrt{\frac{L-1}{a_{1}-1}}$, where $L=\lim_{n\to+\infty}a_{n}$ exist by (*).

Now $L^{3}-L^{2}-L+1=0\Rightarrow L\in \{1,-1\}$ , so $L=1$ because $a_{n}>0$ forall $n$.

Final $s=0$.


geometry
3D geometry
function
Putnam
algebra
polynomial
calculus

A can buoy is to made of three pieces, namely, a cylinder and two equal cones, the altitude of each cone beoing equal to the altitude of the cylinder.
For a given area of surface, what shape will have the greatest volume?

Hey,
[quote="durt"]
[hide]
Presumably this buoy is shaped sort of like a football. Let $ h$ be the height of each piece and $ r$ the radius of each base. So the surface area is $ A \equal{} 2 \pi r h \plus{} 2 \pi r \sqrt {r^2 \plus{} h^2}$. Manipulating this, we can find $ r h$ in terms of $ A$ and $ r^4$, which we can then substitute into the equation for the buoy's volume: $ V \equal{} \frac {5}{3} \pi r^2 h$. So now we have $ V \equal{} \frac {5 A}{12} r \minus{} \frac {5 \pi^2}{3 A} r^5$. To find the $ r$ for which $ V$ is maximum, we solve $ \frac {dV}{dr} \equal{} 0$, which has solution $ r^4 \equal{} \frac {A^2}{20 \pi^2}$. Substituting this back into the surface area equation, we get $ \frac {h}{r} \equal{} \frac {2 \sqrt {5}}{5}$.
[/hide]
[/quote]
Since, the total volume ($ {V}$) and the total surface area ($ {S}$) of the shape can be written in terms of the variables: $ {h}$ (height of each piece) and $ {r}$ (radius of each piece).

How do I treat each (the surface area and volume) as a function of several variables?

That is, which is correct,
$ {S} \equal{} {S(h, r)}$
$ {V} \equal{} {V(h, r)}$
Or
$ {S} \equal{} {S(r, h)}$
$ {V} \equal{} {V(r, h)}$

And why?

Thanks,

-APSStudent

You gave those variables their names (they weren't in the original statement.) So you decide what order to put them in. It truly makes no difference, as long as you maintain some internal consistency.

This being a constrained multivariable optimization problem, the technique of Lagrange multipliers should be well suited to the task of solving this.

The Putnam in 1938 did not closely resemble what the Putnam is today. It appears to me that at the beginning, the Putnam belonged to a very different culture than the problem and contest culture that already existed in Eastern Europe by that time. Now the Putnam does belong to the worldwide problem and contest culture.

Hey,

[quote="Kent Merryfield"]
You gave those variables their names (they weren't in the original statement.) So you decide what order to put them in. It truly makes no difference, as long as you maintain some internal consistency.

This being a constrained multivariable optimization problem, the technique of Lagrange multipliers should be well suited to the task of solving this.
[/quote]

Thanks for the reply Kent Merryfield. Ok, so that clears up the variable consistency question.

When trying to solve this problem I could also see that the technique of Lagrange Multipliers suited this problem. However, I thought I would try something different,
[hide="My attempt at a solution,"]
Note: In case someone did not remember the volumes and surface areas of a right: cone and cylinder; these could be pretty easily derived from Pappus's Centroid Theorem's 1 and 2 respectively.

Ok, now on to the problem,
Let,
$ {S} {\equiv} {\textrm{Total Surface Area}}$
$ {V} {\equiv} {\textrm{Total Volume}}$

Let,
$ {S} = {S(h, r)}$
$ {V} = {V(h, r)}$

Where, $ {S}$ is fixed and and is therefore a constant.
Consider the following system of equations,
$ {S} = {{\pi}{r}{{[}{{\sqrt {{h}^{2} + {r}^{2}}} + {2(r + h)}}{]}}}$
$ {V} = {\frac {{5}{\pi}{{r}^{2}}{h}}{3}}$

Solving both equations for $ {h}$ ($ {h > 0}$) and setting them equal to each other leads to,
$ {{(}{\frac {{3}{V}}{{5}{\pi}{{r}^{2}}}}{)}} = {{(}{\frac {{{ - }{4}{\pi}{{r}^{2}}} + {{2}{S}} + {\sqrt {{{S}{{(}{{S} - {{4}{\pi}{{r}^{2}}}}{)}}} + {{7}{{\pi}^{2}}{{r}^{4}}}}}}{{3}{\pi}{r}}}{)}}$
[hide="Some tips for doing the above step,"]
Admittedly, this step took a while. However, it's pretty straight forward:
$ {S} = {{\pi}{r}{{[}{{\sqrt {{h}^{2} + {r}^{2}}} + {2(r + h)}}{]}}}$
(1) Isolate the radical first.
(2) Square both sides.
(3) Combine like terms.
(4) Move all terms involving the variable $ {h}$ to one side of the equation.
(5) Apply the general technique for completing the square on the polynomial that is a function of $ {h}$.
(6) Combine like terms (again).
(7) Take the (positive) square root of both sides (remember, $ {h > 0}$).
(8) Solve for $ {h}$, :-).
[/hide]
Solving for $ {V}$,
$ {V} = {\frac {{{ - }{20}{\pi}{{r}^{3}}} + {{10}{r}{S}} + {{{5}{r}}{\sqrt {{{S}{{(}{{S} - {{4}{\pi}{{r}^{2}}}}{)}}} + {{7}{{\pi}^{2}}{{r}^{4}}}}}}}{9}}$

Now from here is where it gets a little tricky - my original idea was to take the derivative of $ {V}$ with respect to $ {r}$ and setting the derivative equal to zero to find $ {r}$ for $ {max(V)}$. However, I am not quite sure if this is right way to go... Additionally, I have not solved for the derivative yet (since it takes some time) but I'm not even sure I can directly solve for $ {r}$ once I set the derivative equal to zero.
I guess what I am asking is - is it possible to solve directly for $ {r}$ this way and is it correct?
[/hide]
Thanks,

-APSStudent

Hey,

[quote="APSStudent"]
Where, $ {S}$ is fixed and and is therefore a constant.
Consider the following system of equations,
$ {S} = {{\pi}{r}{{[}{{\sqrt {{h}^{2} + {r}^{2}}} + {2(r + h)}}{]}}}$
$ {V} = {\frac {{5}{\pi}{{r}^{2}}{h}}{3}}$
[/quote]

I calculated the incorrect Surface Area of the shape since I forgot to [u]not[/u] include the bases of the: cones and cylinder.

In addition, I made some more progress on this problem by continuing it from where I left off in the above quote.

[b]2. Relevant equations[/b]
Solving for Critical Numbers.

[b]3. The attempt at a solution[/b]
[hide="My Second Attempt at a Solution."]
[hide="Solving for the Shape that will give the Maximum Volume for a Given Surface Area."]
Note that the "shape" of the object with respect to it's Volume and Surface Area is a function of: $ {h}$ and $ {r}$. Where, $ {h}$ represents the altitude of each of the three individual shapes and $ {r}$ represents the radius of each of the three individual shapes.

Therefore, solving for the "shape" of the object that will give the Maximum Volume for a given Surface Area is exactly the same as solving for the: $ {(h, r)}$ that will maximize $ {V(h, r)}$ for a given Surface Area $ {S}$.

Treating,
$ {\{}\begin{array}{ll} {{{S(h, r)}} = {{{2}{\pi}{r}}{{(}{{h} + {\sqrt {{{h}^{2}} + {{r}^{2}}}}}{)}}}} \\
{{{V(h, r)}} = {\frac {{5}{\pi}{h}{{r}^{2}}}{3}}} \\
\end{array}{\}}$
As a System of Equations.

We can proceed to solve for the $ {{(}{h, r}{)}}$ that will maximize $ {V(h, r)}$ for a given surface area $ {S}$ by isolating: $ {V(r)}$ and $ {V(h)}$; and then solving for the: $ {r}$ and $ {h}$; that will maximize each function respectively. In other words: isolating $ {V(r)}$ we can then solve for the $ {r}$ that will maximize $ {V(r)}$ and isolating $ {V(h)}$ we can then solve for the $ {h}$ that will maximize $ {V(h)}$. Together, we will have the $ {{(}{h, r}{)}}$ that will maximize $ {V(h, r)}$ for a given surface area $ {S}$.
[hide="Solving for the $ {r}$ that will Maximize $ {V(r)}$."]
We can proceed to solve by substitution for $ {V(r)}$ by solving each equation individually for $ {h}$ and setting them equal to each other.

$ {{{S}} = {{{2}{\pi}{r}}{{(}{{h} + {\sqrt {{{h}^{2}} + {{r}^{2}}}}}{)}}}}$
$ {{h} = {\frac {{{{S}}^{2}} - {{4}{{\pi}^{2}}{{r}^{4}}}}{{4}{\pi}{r}{{S}}}}}$
$ {{{V}} = {\frac {{5}{\pi}{h}{{r}^{2}}}{3}}}$
$ {{h} = {\frac {{3}{{V}}}{{5}{\pi}{{r}^{2}}}}}$

$ {{h} = {h}}$
${{ {{{(}{{\frac {{3}{{V}}}{{5}{\pi}{{r}^{2}}}}}}{)}} = {{(}{{\frac {{{{S}}^{2}} - {{4}{{\pi}^{2}}{{r}^{4}}}}{{4}{\pi}{r}{{S}}}}}}{)}}}$
$ {{{V(r)}} = {\frac {{{5}{r}{{{S}}^{2}}} - {{20}{{\pi}^{2}}{{r}^{5}}}}{{12}{{S}}}}}$

$ {{{V}^{\prime}{(r)}} = {\frac {{5}{{(}{{{S}^{2}} - {{20}{{\pi}^{2}}{{r}^{4}}}}{)}}}{{12}{S}}}}$
Let,
$ {\{}\begin{array}{ll} {{{{V}^{\prime}{(r)}} = {0}}{\,}{\,}{\,}{\,}{,}{\,}{\,}{\,}{\,}{{{{V}^{\prime}{(r)}} = {U.D.}} }}\end{array}{\}}$
$ {\{}\begin{array}{ll} {{0} = {\frac {{5}{{(}{{{S}^{2}} - {{20}{{\pi}^{2}}{{r}^{4}}}}{)}}}{{12}{S}}}}{\,}{\,}{\,}{\,} {\,}{\,}{\,}{\,}{{U.D.} \neq {\frac {{5}{{(}{{{S}^{2}} - {{20}{{\pi}^{2}}{{r}^{4}}}}{)}}}{{12}{S}}}} \end{array}{\}}$
$ {0} = {\frac {{5}{{(}{{{S}^{2}} - {{20}{{\pi}^{2}}{{r}^{4}}}}{)}}}{{12}{S}}}$

Solving for $ {r}$,
$ {r} = {{{\pm}{{5}^{\frac {1}{4}}}{\sqrt {\frac {S}{{10}{\pi}}}}}, {{\pm}{{5}^{\frac {1}{4}}}{\sqrt {\frac {S}{{10}{\pi}}}{i}}}}$
$ {{r} > {0}}{\,}{\,}{\,}{\,}{\therefore}$
$ {r} = {{{5}^{\frac {1}{4}}}{\sqrt {\frac {S}{{10}{\pi}}}}}$

[/hide]
[hide="Solving for the $ {h}$ that will Maximize $ {V(h)}$."]
We can proceed to solve by substitution for $ {V(h)}$ by solving each equation individually for $ {r}$ and setting them equal to each other.

$ {{{S}} = {{{2}{\pi}{r}}{{(}{{h} + {\sqrt {{{h}^{2}} + {{r}^{2}}}}}{)}}}}$

Note that by elementary methods $ {r}$ cannot be solved for directly, however $ {r}$ may be rexpressed in the following form as a quartic equation.
$ {{{4}{{\pi}^{2}}{{r}^{4}}} + {{4}{\pi}{h}{S}{r}} - {{S}^{2}}} = {0}$

From here I am stuck since I think the only way to proceed is application of the Quartic Formula, which is very very tedious, even for Maple. Any ideas? Seriously a response would be nice, :-).

If in fact there is a "nice" solution to the above quartic equation then I could use that to finish the problem by solving for $ {h}$ and then finally solving for the $ {(}{h, r}{)}$ that will maximize $ {V(h, r)}$ for a given Surface Area $ {S}$.

Additionally, I wanted to know if treating the equations for the Surface Area and Volume of the object as a System of Equations was a correct approach. I get the feeling like it maybe wasn't? Any ideas?

[/hide]
[/hide]
[/hide]
Thanks,

-APSStudent

Hey,

So essentially my progress on this problem hinges on finding elementary solutions for $ {r}$ in the following quartic equation:

$ {{{4}{{\pi}^{2}}{{r}^{4}}} \plus{} {{4}{\pi}{h}{S}{r}} \minus{} {{S}^{2}}} \equal{} {0}$

I have Maple, however it resolves the answer indirectly that is in terms of its' "Z" function. Resolving it directly, that is by direct application of the quartic equation is very tedious even for a program like Maple to run.

Can anyone run this quartic through and find, if there are any, elementary solutions. That would be great if anyone could make progress in that direction.

Thanks,

-APSStudent

Maple should be able to solve for a symbolic solution, and your equation isn't too bad; it only has terms for r^4, r, and r^0. Whatever Maple outputs, you should be able to simplify it further.

Otherwise, if you just want to quickly check numerical results, here is an online utility:

[url]http://www.akiti.ca/Quad4Deg.html[/url]

Regards.

Robert


Let $P(x)=x^5-x+a$
$a\in\mathbb{Z}$, $5\not|a$. Prove, that $P(x)$ cannot be the product of two polynomials of positive degree with integer coefficients.


algebra
polynomial
superior algebra
superior algebra theorems

I have found some easy method  to solve polynomial equations(when all the roots are real). It is a unique and simple method.I released it as an E-BOOK,'NEW AND SIMPLE METHOD OF SOLVING POLYNOMIAL EQUATIONS'(ALL REAL ROOTS).

see link.

http://ifile.it/1lgv3bh

                     Please read and post your opinion here.

                                                 Thank you

If you find any trouble to download, another link is

http://rkmath.synthasite.com/

I have shown some more methods which is much quicker than previous ones for solving real roots polynomial equations. These examples are from’ Solving Real Roots Polynomial Equations’(New And Simple Methods Of Solving Real Roots Polynomial Equations Part-2). Try it to see whether it works well. Click here.
http://www.rkmath.yolasite.com


Please explain how to solve this problem for step by step. Thanks. [/img]

Really? OK!

From $ \sqrt[5]{x^2 \plus{} 2x} \equal{} \minus{}1$, by raising to $ 5$ power get $ x^2 \plus{} 2x \equal{} \minus{}1$, i.e. $ (x\plus{}1)^2 \equal{} 0$, with unique solution $ x \equal{} \minus{}1$. So?

[quote="Anonymous52111"][quote="mavropnevma"]Really? OK!

From $ \sqrt [5]{x^2 \plus{} 2x} \equal{} \minus{} 1$, by raising to $ 5$ power get $ x^2 \plus{} 2x \equal{} \minus{} 1$, i.e. $ (x \plus{} 1)^2 \equal{} 0$, with unique solution $ x \equal{} \minus{} 1$. So?[/quote]

Could you show your work of using the answer to verify the mathematical question? Thanks.[/quote]Plug in $ x\equal{}\minus{}1$ and get $ \sqrt[5]{\minus{}1}\equal{}\minus{}1$...


Triangle $ PAB$ is formed by three tangents to circle $ O$ and $ < APB \equal{} 40^{\circ}$; then angle $ AOB$ equals:

$ \textbf{(A)}\ 45^{\circ} \qquad\textbf{(B)}\ 50^{\circ} \qquad\textbf{(C)}\ 55^{\circ} \qquad\textbf{(D)}\ 60^{\circ} \qquad\textbf{(E)}\ 70^{\circ}$

$ \angle PBA \plus{} \angle PAB\equal{} 140$, so $ \angle RBA \plus{} \angle TAB\equal{}360\minus{}140\equal{}220$. But OB and OA are angle bisectors, so $ \angle OBA \plus{} \angle OAB\equal{}110$, so $ \angle AOB\equal{}70$.

[quote="Brut3Forc3"]and $ \angle APB \equal{} 40^{\circ}$;[/quote]LaTeX housekeeping.


Hopefully its reeeeeeaaaly close so they have to waste time recounting the votes like 20 times... :rotfl:

I think it will be close and we will never ever know for sure.

I want it to be close, but sadly it will never happen. And MO has always (with the exception of 1 election) voted for the president, so using that logic, I have no idea who will win.

rememeber the time when there were like 5 swing states> Now there are like 30..... :rotfl:

The forseeable day in the future (if another bush is prez)=WE currently have 51 swing states! I will win by defeating my opponents in Virginia, West Virginia, AND East Virginia!

Have you checked out http://www.fivethirtyeight.com/
There is no bias seeing how he says Obama will win, and he supports McCain.


I got 1st place in the MathCounts Chapter round!  And my team got 1st!  And I got 2nd in the Countdown round!

I never thought I could do so well.  I'm happy now.

in new haven?

cause luyi got 2nd writen, then 1st cd :P

i got 6th written, 1st countdown in hartford

jorian

I'm pretty sure Barna won the countdown. Just sayin'

I will (hopefully) be writing the AMC 12. Congrats to all the great performances at Chapters. Anyone here from the Avon team?

[quote="dkushnir"]360_fan is in Southwest CT (Fairfield county).
I am his coach (mom).
You guys in New Haven are good!
Anybody writing AMC 10 tomorrow?
Good luck![/quote]

do you mean taking?

360_fan: Can you pm me and we can discuss scores?
thanks,

jorian

[quote]do you mean taking? [/quote]

Yes, taking.

Good luck to all of you tomorrow!


inequalities
function
calculus
derivative
inequalities proposed

Let x be a positive real number.

Prove that $\frac 1 x \geq (1-\frac{ln x}{x})^x$.

Since $lnx\leq x-1 < x$ , we take  natural logatithm in both members and the ineq. becomes equivalently :

     $ln(1-u) \leq -u , u = \frac{lnx}{x}$
Now take the function

  $f(x) = ln(1-u)+u , u < 1$ and with a standard method (derivative and extreme values) we find $f'(u) =\frac{u}{u-1}$ , so we  are done , since $f(x) \leq f(0) = 0$. We have equality only if $u = 0$ , that is $x=1$

 [u]Babis[/u]

 I must see it again ,  because I must ran to the class !!!!!!!


Can anybody help me to find the roots of this cubic:

$ 4{x^{3}}-3(t+u+v+w)x^{2}+2(tu+tv+tw+uv+uw+vw)x-(tuv+tuw+tvw+uvw)$

(The roots for x will be in terms of t, u, v, and w)

try using vieta's theorem:

for polynomial degree 3, call roots a, b, and c.

If the polynomial is of the form x^3+px^2+qx+r, then a+b+c = -p, ab+bc+ac = 1, and abc = -r.

I don't know if this helps: [hide]\[ \begin{aligned}& 4{x^{3}}-3(t+u+v+w)x^{2}+2(tu+tv+tw+uv+uw+vw)x-(tuv+tuw+tvw+uvw) \\ & = (x-u)(x-v)(x-w)+(x-v)(x-w)(x-t)+(x-w)(x-t)(x-u)+(x-t)(x-u)(x-v)\end{aligned}\][/hide]


articles
function
algebra
domain
search
trigonometry
arithmetic sequence

What exactly is a sequence? Does it have to follow certain rules or can they be completely random?

http://en.wikipedia.org/wiki/Sequence

Sequences can have duplicates, and can be "random".

[url]http://www.artofproblemsolving.com/Wiki/index.php/Sequence[/url]

Basically just a list of numbers I think.

Beaten.

So from the wiki article, when you are dealing with sequences with real numbers, the sequence can be represented by a function?

I think some can, but I'm not sure if it's a requirement.

all sequences are basically functions, try to find out why if you haven't thought about that yet

Arithmetic Sequence;

1, 4, 7, 10, ... You are adding/subtracting the same number each time, and it forms a pattern.

Geometric Sequence;

2, 4, 8, 16, ... You are multiplying/dividing the same number each time, and it forms a pattern.

I guess a function could also be some kind of sequence, like f(x)=3x - 1 then the sequence would be;
1, 2, 5, 14, ... etc.

Hope that helped.  :lol:

A sequence is any function whose domain is $ \mathbb{N}$.

N is natural number. Right? What does domain mean? i thought that I would include that question so that anybody interested about sequences could just search for this post, and then see what the definition for domain was without having to google it. I am being considerate for my fellow AoPSers.

More specifically, it is the set of all possible inputs of a function $ f(x)$.

Alright thanks. That rings a bell. Is there a name for the y values?

[quote="JRav"]The set of all [i]possible[/i] y-values is called the codomain.  The set of all actual y-values is called the range.[/quote]

Hmm, I had not heard that before.

So for anybody that doesn't understand. If f(x) = y, then x is the domain, and y is called the codomain.

Not quite.

A function $ f: A\rightarrow B$ maps from the domain $ A$ to the codomain $ B$.

The set of all $ x$ such that the function $ f(x)$ makes sense is called the domain (represented by $ A$).  The set of all [u]possible[/u] values of $ y$ is the codomain.  However, it is very possible that $ f(x)$ does not actually attain these values.  For example, $ f: \mathbb{R}\rightarrow\mathbb{R}$ defined by $ f(x)\equal{}\sin{x}$ has $ \mathbb{R}$ as its domain and codomain.  But $ \sin{x}$ will only equal values of $ y$ between -1 and 1.  So we say $ [\minus{}1,1]$ is the range of $ f$.  That is, the range is the set of all $ y$ in the codomain that are actually attained.


ratio
algebra
polynomial
real analysis
real analysis solved

the 3rd one is quite easy:

lim(x-->1) [((1-sqrt(x))(1-(x)^(1/3))*...*(1-x^(1/n))]/(1-x)^(n-1);

do like so:

(1-sqrt(x))/(1-x)=(1-sqrt(x))/((1-sqrt(x))(1+sqrt(x)))=1/(1+sqrt(x))
and you get the limit by multiplying the similar relations!

[quote="Georg"]
2) lim(x-->1) (ax^n+bx^p+c)/(x-1)^2; with a+b+c=0 na+pb=0 n,p are natural numbers<>0;
[/quote]

b=-an/p, c=a(n/p-1).
Then lim(x-->1) (ax^n+bx^p+c)/(x-1)^2=a*lim(x-->1) (x^n-(n/p)*x^p+n/p-1)/(x-1)^2. Apply l'Hospital 2 times to get lim(x-->1) (ax^n+bx^p+c)/(x-1)^2=an(n-p)/2.

[quote="Georg"]
1)lim(x-->oo) (x-((x-x1)(x-x2)*..*(x-xn))^(1/n)); x_k are real numbers, n>=2,fixed;
[/quote]

lim(x->oo) (x-((x-x1)(x-x2)*..*(x-xn))^(1/n))=lim(x n-(x-x1)*...*(x-xn))/ \sum {k=0..n-1}x k*[(x-x1)*...*(x-xn)] (n-1-k)/n.

This limit is the limit of a ratio of a polynomial of degree n-1 and leading coefficient (x1+x2+...+xn), and an expresion P such that limP/x n-1=n.
So lim(x->oo) (x-((x-x1)(x-x2)*..*(x-xn))^(1/n))=(x1+x2+...+xn)/n.

2) lim(x-->1) (ax^n+bx^p+c)/(x-1)^2; with a+b+c=0 na+pb=0 n,p are natural numbers<>0;

can be done without l'Hopital, all you do is replace c with -a-b and you get rid of (x-1)^2 very easy and you get the limit!

But you might have to treat some small cases for n and p separately.


geometry
geometric transformation
reflection
geometry proposed

In the convex pentagon $ ABCDE$ following equalities holds: $ \angle ABD\equal{} \angle ACE, \angle ACB\equal{}\angle ACD, \angle ADC\equal{}\angle ADE$ and $ \angle ADB\equal{}\angle AEC$. The point $S$ is the intersection of the segments $BD$ and $CE$. Prove that lines $AS$ and $CD$ are perpendicular.

Let $ X\equal{}AC\cap BS$, $ Y\equal{}AC\cap ES$, $ Z\equal{}AS\cap CD$.

We see that $ ABCS$ and $ AEDS$ are cyclic, so
\[ \angle ASB\equal{}\angle ACB\equal{}\angle ZCX,
\]
so $ XCZS$ is cyclic. Similar, $ YDZS$ is cyclic. It thus follows that
\[ \angle AXS \equal{} \angle CZS \equal{} \angle DYS,
\]
so $ AXSY$ is cyclic. Hence,
\[ \angle YDC \equal{} \angle ADC \equal{} \angle EDA \equal{} \angle ESA \equal{} \angle YSA \equal{} \angle YXA,
\]
so $ XCDY$ is cyclic. It follows that
\[ \angle SXC \equal{} \angle DYS.
\]
But $ \angle SXC \equal{} \angle SZD$ and $ \angle DYS \equal{} \angle CZS$, so
\[ \angle SZD \equal{} \angle CZS.
\]
Thus $ \angle SZD \equal{} \angle CZS \equal{} 90^\circ$.

reflect $ A$ to $ CD$ and apply Jacobi theorem.

hmmmmmmmmmm,a good problem :wink:

$ \angle ABD\equal{}\angle ACE\equal{}\alpha$(1)

$ \angle ACB\equal{}\angle ACD\equal{}\beta$(2)

$ \angle ADC\equal{}\angle ADE\equal{}\delta$(3)

$ \angle ADB\equal{}\angle AEC\equal{}\gamma$(4)

according to (1)and(4),we find out $ \triangle ABD$and $ \triangle ACE$ are similar to each other.

Infact $ \triangle ABD$ turns into $ \triangle ACE$ by a spiral similarity with radius$ \frac{AD}{AB}$

And angle $ 180\minus{}(\beta\plus{}\gamma)$,

Then it shows that $ \triangle ABC$and $ \triangle ADE$,are also similar to each other.And:

$ \angle CBA\equal{}\angle CDA\equal{}\delta$

but it shows that:$ \triangle ABC$=$ \triangle ADC$,then the points $ D$and$ B$,turn into each other

with a reflect to segment $ AC$,and we conclude that $ AC$ is perpendicular to$ BD$.

With a similar way,we can show $ AD$ is perpendicular $ CE$,too.

$ AC \cap BD\equal{}M$

$ AD \cap CE\equal{}N$

then in triangle $ ACD$,the altitudes are $ DM$and $ CN$.

And according to concurrency of the three altitudes of triangle,

$ AS$ is also the third altitude of triangle $ ACD$,and it means that: $ AS \bot CD$

Let $X = AD \cap CE, Y = AC \cap BD, Z = AS \cap CD$.

Observe trivially that $AEDS$ and $ABCS$ are cyclic. We then make the following observations:

[b][color=#f00]Claim:[/color][/b] $SYCZ$ and $SXDZ$ are cyclic.
[i]Proof:[/i] We have that \[\angle BCA = \angle BSA = \angle DSZ = \angle YCZ.\] A similar angle chase ensues for $SXDZ$. $\square$

[b][color=#f00]Claim:[/color][/b] $AXSY$ and $DXYC$ are cyclic.
[i]Proof:[/i] We have that
\begin{align*}
\angle CSY &= 180^{\circ} - (\angle BSA + \angle ASE) \\
&= 180^{\circ} - (\angle YCD + \angle XDZ) \\
&= \angle DAC \implies AXSY \text{ is cyclic.}\\
\end{align*} Hence we then have that \[\angle AYX = \angle ASX = \angle ZDX \implies DXYC \text{ is cyclic. } \square \]

Now observe that
\begin{align*}
\angle SYC &= \angle SYZ + \angle ZYC \\
&= \angle XCD + \angle ZSC \\
&= \angle XYD + \angle XSA \\
&= \angle XYD + \angle XYA \\
&= \angle SYA,
\end{align*} so that as \[\angle SYC + \angle SYA = 180^{\circ} \implies \angle SYC = 90^{\circ} \implies \angle SZC = 180^{\circ} - \angle SYC = 90^{\circ},\] as desired. $\blacksquare$


I want to play this game online but I seem to have lost my cd key. If someone used to play this game and is no longer playing it, could you please [url=http://www.mathlinks.ro/privmsg.php?mode=post&u=2639]PM[/url] me your cd key? (D2+LoD)

You'd really make my day! :D

hmm, i used to play the original, but not the expansion. I have the same question about black & white, another game. I bought it and payed money, but i lost the cd key and now i cant even play it, online of off.

I play at my friend's house  :D I didn't really get that far, and he's not playing it for a while, and I don't know the cd key.


function
logarithms
trigonometry
floor function
algorithm
parameterization
geometry

Suppose you have a programming (or spreadsheet) environment in which the function $ \text{rand}()$ returns a random variable with a uniform distribution that is uniform on $ [0,1],$ and that if we call this function repeatedly, each instance that it returns is independent of all others. (At least that's the "face value". Of course, it's really "pseudo-random" but let's just take it at face value for the purposes of this problem.) This environment also has all of the usual "calculator" functions: powers, roots, exponential, logarithm, trig, inverse trig, absolute value, integer part ($ \lfloor\cdot\rfloor$), and mod.

Describe algorithms or procedures for producting random variables with the following distributions. You may call $ \text{rand}()$ multiple times within the algorithm, but being able to execute this with reasonable efficiency is a virtue.

(i) Distributed as the number showing on one throw of a fair six-sided die.

(ii) Exponentially distributed with given mean $ \beta.$

(iii) $ (X,Y)$ uniformly distributed on the triangle with vertices $ (0,0),(0,1),$ and $ (2,0).$

(iv) Geometrically distributed with parameter $ p.$

(v) $ (X,Y)$ uniformly distributed on the unit disk, $ X^2 \plus{} Y^2 < 1.$

(vi) As a Poisson distribution with given mean $ \lambda.$

(vii) Normally distributed with given mean $ \mu$ and variance $ \sigma^2.$

(viii) As the following hypergeometric: We have 30 red balls and 20 blue balls. We select 6 balls without replacement. How many of them are red?

for (iii) and (v), is there a better way that to generate points uniformly distributed inside the smallest rectangle that contains the shape, and wait that the points fall inside ?

For (v) you can do radius and angle (both are one-dimensional distributions with fairly easy to invert cumulative distribution functions) but I doubt that computation of one $ \sin$, $ \cos$, or $ \sqrt{\phantom{x}}$ is any faster than calling $ \text{rand()}$ an extra couple of times, so honestly, I don't know...

(iii) and (v) can be done using two rand() calls. one call for $ X$ and then another call for $ Y$. Just consider what is the distribution of $ X$ and what is the conditional distribution of $ Y$ given a value of $ X$. While it calls rand() less often, it calls operations such as $ \sqrt{\phantom{x}}$ more often than the throw-dart approach.

For (iii), there is an algorithm involving only two rand()s and only $ \plus{}$,$ \minus{}$,$ \times$,$ /$: cut the triangle into two peices and rearrange the pieces to make a rectangle.

I've used (v) as a classroom example, offering up for criticism this algorithm:

$ R: \equal{}\text{rand}()$
$ \Theta: \equal{}2\pi\,\text{rand}()$
$ X: \equal{}R\cos(\Theta)$
$ Y: \equal{}R\sin(\Theta)$

Half the class usually falls for it; I have to show scatterplots produced by this algorithm to convince them that it's wrong and the fix is to change the first line to $ R: \equal{}\sqrt{\text{rand}()}.$

I started doing this a long time ago - long enough ago that my primary compute had an 8 MHz CPU with no FPU. Using the algorithm above to produce, say, 5000 points for a scatterplot was noticeably slower than what redkimchi called the "throw-dart" approach. However, when I switched to a computer with a 16 MHz CPU that did have an FPU, I could no longer notice any difference.

Just to codify it - the "throw-dart" algorithm:

DO
$ \ X: \equal{}2\,\text{rand}()\minus{}1$
$ \ Y: \equal{}2\,\text{rand}()\minus{}1$
LOOP UNTIL $ X\cdot X\plus{}Y\cdot Y<1$

The number of times the loop will execute is a geometrically distributed random variable with mean $ \frac{4}{\pi}.$

[quote="Kent Merryfield"](vii) Normally distributed with given mean $ \mu$ and variance $ \sigma^2.$
[/quote]
Make 12 rand() random numbers, add them, and subtract 6. Multiply with $ \sigma$ and add $ \mu$. Close enough by the Central Limit Theorem :)

A uniform $ (0,1)$ random variable has mean $ \frac12$ and variance $ \frac1{12}.$ We're going to have to account for that. Here's a more careful statement of what hpe said.

Choose a fixed modest sized integer $ m.$ (hpe suggests $ m \equal{} 12.$)

$ X: \equal{} 0$
FOR $ i \equal{} 1$ to $ m$ DO
$ \ X: \equal{} X \plus{} \text{rand}()$
NEXT $ i$
$ X: \equal{} X \minus{} \frac {m}2$
$ X: \equal{} X\cdot\sqrt {\frac {12}{m}}$
$ X: \equal{} \mu \plus{} \sigma X$

Ah - I see that hpe did account for the variance of the uniform, which was why he let $ m\equal{}12.$ That makes the next to the last line above irrelevant.

-----

It turns out that there's a more exact procedure than that, based on polar coordinates (and the fact that you can deal with a two dimensional Gaussian more easily than a one dimensional Gaussian).

$ R: \equal{} \sqrt { \minus{} 2\ln(\text{rand}())}$
$ \Theta: \equal{} 2\pi\cdot\text{rand}()$
$ X: \equal{} R\cos\Theta$
$ Y: \equal{} R\sin\Theta$
$ U: \equal{} \mu \plus{} \sigma X$
$ V: \equal{} \mu \plus{} \sigma Y$

Then $ U$ and $ V$ are independent and both have the required distribution.

Perhaps I should add the following:

(ix) For a given positive definite $ n\times n$ matrix $ C,$ and a given fixed vector $ M \equal{} (\mu_1,\mu_2,\dots,\mu_n),$ produce $ (X_1,X_2,\dots,X_n)$ with a joint normal distribution with mean $ M$ and covariance matrix $ C.$

[quote="Kent Merryfield"]It turns out that there's a more exact procedure than that, based on polar coordinates (and the fact that you can deal with a two dimensional Gaussian more easily than a one dimensional Gaussian)...[/quote]That's how Matlab implemented its $ \tt{randn}$ function until about version 3. Since taking logarithms, sines and cosines is computationally expensive, they now use something called the "ziggurat" algorithm. See [url=http://www.mathworks.com/company/newsletters/news_notes/clevescorner/spring01_cleve.html]here[/url] for details.

Matlab's $ \tt{rand}$ function however is not state of the art. That honor (afaik) goes to the [url=http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html]Mersenne Twister[/url], implemented for example in [url=http://www.r-project.org/]R[/url]. Its period is $ 2^{19937} \minus{} 1$.
[quote](ix) For a given positive definite $ n\times n$ matrix $ C,$ and a given fixed vector $ M \equal{} (\mu_1,\mu_2,\dots,\mu_n),$ produce $ (X_1,X_2,\dots,X_n)$ with a joint normal distribution with mean $ M$ and covariance matrix $ C.$[/quote]Compute the Cholesky factorization $ C \equal{} RR^T$, where $ R$ is triangular. Make a vector $ Y \equal{} (Y_1,Y_2,\dots, Y_n)^T$  of independent $ N(0,1)$ random variables. Set $ X \equal{} RY \plus{} M$.


algebra
polynomial
calculus
integration
function
derivative
analytic geometry

[quote="Hokkage"]For consecutive integral values of $x$, a polynomial function has respective values $-3, 1, 12, 33, 67,$ and $117$. Find the least possible degree of this polynomial.
\[ (A) 2 \ \ \ \ \ \ \ \ (B) 3 \ \ \ \ \ \ \ \ (C) 4 \ \ \ \ \ \ \ \ (D) 5 \ \ \ \ \ \ \ \ (E) 6  \]Please show work![/quote]Consider successive differences.
$\Delta(P): 4, 8, 21, 34, 50$
$\Delta(\Delta(P)): 4, 13, 13, 26$
$\Delta(\Delta(\Delta(P))): 9, 0, 13$
$\Delta(\Delta(\Delta(\Delta(P)))): -9,13$

Hence, $\deg(P)>4$.

[quote="towersfreak2006"]Consider successive differences.
$\Delta(P): 4, 8, 21, 34, 50$
$\Delta(\Delta(P)): 4, 13, 13, 26$
$\Delta(\Delta(\Delta(P))): 9, 0, 13$
$\Delta(\Delta(\Delta(\Delta(P)))): -9,13$

Hence, $\deg(P)>4$.[/quote]The second term in $\Delta(P)$ should be $11$, no? This throws off the other ones as well...

Actually, the 8 should be 11.  And the 26 should be 16.  Which changes it to 3, 3, 3 on the third set of differences.  Answer is B.

So when you get to a similar number all across at the $x$ difference, or unless it becomes a two numbers, then the minimum degree is $x$? I don't really understand why. Can anyone explain or link me to something that might explain?

Try it out for yourself.  Take the polynomial $x^2$ and check the differences.  http://mathworld.wolfram.com/FiniteDifference.html

If you want to read more, google "polynomial finite differences" or something along those lines.

edit: as for the why, if you know a bit of calculus, it should be apparent.  The derivative of a polynomial will be another polynomial of one degree less.  The change or slope of a line will be constant.  For a quadratic, the second-order derivative would be a constant, meaning its concavity doesn't change.  And so on.

No problemo. :D

When you have a linear function, say y=3+7x, the differences between the terms will be constant,
$y=3,10,17,24$
$\Delta{y}=7,7,7$

When you have a quadratic function, the differences between sucessive terms will be linear. Consider $a(x+\Delta{x})^2+b(x+\Delta{x})+c- (ax^2+bx+c)$, the difference between two terms. The difference is linear, you see why, right? So if you take the difference between sucessive terms of this linear function, you will have a constant.

This can be extended to all nth power functions. (Keep applying repeatedly). If the nth differences of a function all are constant, the function can be at most a nth degree polynomial.

See why? Pardon my unclear wording at times, though.

Thanks guys! After I asked the question I started messing around. I got stuck and then those two answers helped me finish it up. This should come in handy in the future.


Snape has 2000 mL of a magic potion solution that is $ 30\%$ DeMuggle Juice.  He also has hundreds of 25 mL bottles that are full of  $ 75\%$ DeMuggle Juice solution.  Every time he waves his wand, one of these bottles is added to his  magic potion. How many times must he wave his wand to have a solution that is at least $ 34\%$ DeMuggle Juice?

The 2000mℓ potion contains 600 mℓ DeMuggle juice, and each 25mℓ bottle contains 18.75 mℓ DeMuggle juice. When [i]n[/i] of those little bottles are added, the concentration of the magic potion is $ \frac{600\plus{}18.75n}{2000\plus{}25n}\times100\%$.

Solve for [i]n[/i] where $ \frac{600\plus{}18.75n}{2000\plus{}25n}\ \geq\ 0.34$.


algebra polynomial function calculus integration parameterization inequalities

[quote="puuhikki"]Prove that $ \sum_{i \equal{} 0}^n \binom{2i}{i}\binom{2n \minus{} 2i}{n \minus{} i} \equal{} 4^n$. Is there a proof not using random walks?[/quote]

How to prove it [i]with[/i] random walks? I don't see any appropriate interpretation... On the other hand, I see an easy algebraic proof of the above identity:

Recall the Vandermonde identity

$ \sum_{i \equal{} 0}^n\binom{a}{i}\cdot\binom{b}{n \minus{} i} \equal{} \binom{a \plus{} b}{n}$,

which holds for any natural $ n$ and any natural $ a$ and $ b$. This identity is clearly a polynomial identity in $ a$ and $ b$, so that the fact that it holds for any natural $ a$ and $ b$ immediately yields that it holds for any [i]real[/i] $ a$ and $ b$. In particular, it must hold if $ a \equal{} \minus{} \frac12$ and $ b \equal{} \minus{} \frac12$. In this case, $ a \plus{} b \equal{} \left( \minus{} \frac12\right) \plus{} \left( \minus{} \frac12\right) \equal{} \minus{} 1$, so that this identity takes the form

$ \sum_{i \equal{} 0}^n\binom{ \minus{} \frac12}{i}\cdot\binom{ \minus{} \frac12}{n \minus{} i} \equal{} \binom{ \minus{} 1}{n}$.

But now, by the definition of binomial coefficients,

$ \binom{ \minus{} \frac12}{i} \equal{} \frac {\left( \minus{} \frac12\right)\cdot\left( \minus{} \frac12 \minus{} 1\right)\cdot ...\cdot\left( \minus{} \frac12 \minus{} i \plus{} 1\right)}{i!}$
$ \equal{} \frac {1}{i!}\cdot\left( \minus{} \frac12\right)\cdot\left( \minus{} \frac12 \minus{} 1\right)\cdot ...\cdot\left( \minus{} \frac12 \minus{} i \plus{} 1\right)$
$ \equal{} \frac {1}{i!}\cdot\left( \minus{} \frac {1}{2}\right)\cdot\left( \minus{} \frac {3}{2}\right)\cdot ...\cdot\left( \minus{} \frac {2i \minus{} 1}{2}\right)$
$ \equal{} \frac {1}{i!}\cdot\left( \minus{} \frac12\cdot 1\right)\cdot\left( \minus{} \frac12\cdot 3\right)\cdot ...\cdot\left( \minus{} \frac12\cdot\left(2i \minus{} 1\right)\right)$
$ \equal{} \frac {1}{i!}\cdot\left( \minus{} \frac12\right)^i\cdot\left(1\cdot 3\cdot ...\cdot\left(2i \minus{} 1\right)\right)$.

Since

$ 1\cdot 3\cdot ...\cdot\left(2i \minus{} 1\right) \equal{} \frac {1\cdot 2\cdot 3\cdot ...\cdot\left(2i\right)}{2\cdot 4\cdot 6\cdot ...\cdot\left(2i\right)}$
$ \equal{} \frac {1\cdot 2\cdot 3\cdot ...\cdot\left(2i\right)}{\left(2\cdot 1\right)\cdot\left(2\cdot 2\right)\cdot\left(2\cdot 3\right)\cdot ...\cdot\left(2\cdot i\right)} \equal{} \frac {1\cdot 2\cdot 3\cdot ...\cdot\left(2i\right)}{2^i\cdot\left(1\cdot 2\cdot 3\cdot ...\cdot i\right)} \equal{} \frac {\left(2i\right)!}{2^i\cdot i!}$,

this becomes

$ \binom{ \minus{} \frac12}{i} \equal{} \frac {1}{i!}\cdot\left( \minus{} \frac12\right)^i\cdot\frac {\left(2i\right)!}{2^i\cdot i!} \equal{} \frac {1}{i!}\cdot\frac {\left( \minus{} 1\right)^i}{2^i}\cdot\frac {\left(2i\right)!}{2^i\cdot i!} \equal{} \frac {\left( \minus{} 1\right)^i}{\left(2^i\right)^2}\cdot\frac {\left(2i\right)!}{i!\cdot i!}$
$ \equal{} \frac {\left( \minus{} 1\right)^i}{4^i}\cdot\frac {\left(2i\right)!}{i!\cdot\left(2i \minus{} i\right)!} \equal{} \frac {\left( \minus{} 1\right)^i}{4^i}\cdot\binom{2i}{i}$.

Similarly,

$ \binom{ \minus{} \frac12}{n \minus{} i} \equal{} \frac {\left( \minus{} 1\right)^{n \minus{} i}}{4^{n \minus{} i}}\cdot\binom{2\left(n \minus{} i\right)}{n \minus{} i}$.

Finally, by the definition of binomial coefficients again,

$ \binom{ \minus{} 1}{n} \equal{} \frac {\left( \minus{} 1\right)\cdot\left( \minus{} 2\right)\cdot ...\cdot\left( \minus{} 1 \minus{} n \plus{} 1\right)}{n!} \equal{} \frac {\left( \minus{} 1\right)\cdot\left( \minus{} 2\right)\cdot ...\cdot\left( \minus{} n\right)}{n!}$
$ \equal{} \frac {\left( \minus{} 1\right)^n\cdot\left(1\cdot 2\cdot ...\cdot n\right)}{n!} \equal{} \frac {\left( \minus{} 1\right)^n\cdot n!}{n!} \equal{} \left( \minus{} 1\right)^n$.

Thus, the above identity $ \sum_{i \equal{} 0}^n\binom{ \minus{} \frac12}{i}\cdot\binom{ \minus{} \frac12}{n \minus{} i} \equal{} \binom{ \minus{} 1}{n}$ becomes

$ \sum_{i \equal{} 0}^n\left(\frac {\left( \minus{} 1\right)^i}{4^i}\cdot\binom{2i}{i}\right)\cdot\left(\frac {\left( \minus{} 1\right)^{n \minus{} i}}{4^{n \minus{} i}}\cdot\binom{2\left(n \minus{} i\right)}{n \minus{} i}\right) \equal{} \left( \minus{} 1\right)^n$.

This simplifies to

$ \sum_{i \equal{} 0}^n\frac {\left( \minus{} 1\right)^n}{4^n}\cdot\binom{2i}{i}\cdot\binom{2\left(n \minus{} i\right)}{n \minus{} i} \equal{} \left( \minus{} 1\right)^n$.

Upon division by $ \left( \minus{} 1\right)^n$ and multiplication by $ 4^n$, this equation becomes

$ \sum_{i \equal{} 0}^n\binom{2i}{i}\cdot\binom{2\left(n \minus{} i\right)}{n \minus{} i} \equal{} 4^n$.

This is exactly the identity we wanted to prove.

[b]EDIT:[/b] Argh!! I'm taking a look at R. L. Graham, D. E. Knuth, O. Patashnik, [i]Concrete Mathematics[/i], 1988, paragraph 5.3, formula (5.39), and what do I find? The same identity with the same proof...

  Darij

Thanks for your solution! I solved the same problem with random walks couple of years ago and I have lost that piece of paper where I wrote that solution. If I remember correctly my idea was to compute how many different ways we can return to the real line in 1-dimensional random walk in 2n steps.

[quote="puuhikki"]Prove that $\sum_{i=0}^n \binom{2i}{i}\binom{2n-2i}{n-i}=4^n$. Is there a proof not using random walks?[/quote]

It is a famous and difficult problem to prove this by purely combinatorial means, so it would be interesting to see a solution with random walks.   The usual solution is to use the fact that $\sqrt{\frac{1}{1-4x}}$ is the generating function of the sequence ${2n} \choose n$; the above identity is just a restatement of this fact (and the fact itself follows from the binomial theorem).

[quote="puuhikki"]$ \sum_{i \equal{} 0}^n \binom{2i}{i}\binom{2n \minus{} 2i}{n \minus{} i} \equal{} 4^n$. Is there a proof not using random walks?[/quote]
[i] SOLUTIONS and possible  GENERALIZATIONS[/i]
[b]First solution (using integral calculus).[/b]  Multiply both sides of the identity $ 1 \equal{} \sum\limits_{k \equal{} 0}^{n}{n\choose k}t^{k}(1 \minus{} t)^{n \minus{} k}$ by $ \sqrt {t(1 \minus{} t)} .$     One finds
\[ (1.1)\; \; \; \; \sqrt {t(1 \minus{} t)} \equal{} \sum\limits_{k \equal{} 0}^{n}{n\choose k} t^{k \plus{} \frac {1}{2}} (1 \minus{} t)^{n \minus{} k \plus{} \frac {1}{2}}.
\]
By integrating (1)  over $ [0,1]$ , we give
\[ \displaystyle \int\limits_{0}^{1}\sqrt {t(1 \minus{} t)}\; dt \equal{} \displaystyle \sum\limits_{k \equal{} 0}^{n}{n\choose k}\int\limits_{0}^{1}t^{k \plus{} \frac {1}{2}}(1 \minus{} t)^{n \minus{} k \plus{} \frac {1}{2}}\; dt \; .
\]
But  $ \int\limits_{0}^{1}\sqrt {t(1 \minus{} t)}\; dt \equal{} \pi$ and  $ \displaystyle \int\limits_{0}^{1}t^{k \plus{} \frac {1}{2}}(1 \minus{} t)^{n \minus{} k \plus{} \frac {1}{2}}\; dt \equal{} \displaystyle \frac {\pi {2k \choose k}{2n \minus{} 2k\choose n \minus{} k}}{4^n{n\choose k}}.$
[i]Note:[/i] For $ p > 0, q > 0$ we have $ \int\limits_{0}^{1}t^{p \minus{} 1}(1 \minus{} t)^{q \minus{} 1}\; dt \equal{} \displaystyle \frac {\Gamma(p)\Gamma(q)}{\Gamma(p \plus{} q)}$, where $ \Gamma$ is the Gamma function. We have $ \Gamma(1) \equal{} 1\; ,\; \Gamma\left(\frac {1}{2}\right) \equal{} \sqrt {\pi}\; ,\; \Gamma(x \plus{} 1) \equal{} x\Gamma(x) \; ,\; \forall x > 0 .$
[b]Second solution (using interpolation)[/b] For all polynomial functions $ f$ of degree $ \le n$, we have
\[ (2.1)\; \; f(x) \equal{} \sum\limits_{k \equal{} 0}^{n}[x_0,x_1,...,x_k\; ; f](x \minus{} x_0)(x \minus{} x_1)\cdots(x \minus{} x_{k \minus{} 1})
\]
where  $ {\mathcal X}: \equal{} \{x_0,x_1,...,x_n\}$ is a system of distinct points from $ {\mathbb R} ,$ and
\[ [x_0,x_1,...,x_k\; ; f]: \equal{} \sum\limits_{j \equal{} 0}^{k}\frac {f(x_j)}{w_k^{\prime}(x_j)}\; ,\; \; \omega_k(x): \equal{} (x \minus{} x_0)(x \minus{} x_1)\cdots(x \minus{} x_k).
\]
The numbers $ [x_0,x_1,...,x_k\; ; f]\; ,\; k\in \{0,1,...,n\}$ are called the  "divided differences " of $ f$ at the system $ {\mathcal X} .$ In (2.1) let us select $ x_k \equal{} \minus{} \; k$  and
\[ f(x) \equal{} (x \plus{} y)(x \plus{} y \plus{} 1)\cdots (x \plus{} y \plus{} n \minus{} 1) \; \; ,\; \; y\; \;\mbox{being a real parameter.}
\]
If  $ (A)_0: \equal{} 1 \; ,\; (A)_k: \equal{} A(A \plus{} 1)\cdots(A \plus{} k \minus{} 1) \; ,\; (k\ge 1 ) ,$ then from (2.1) we give
\[ (2.2)\; \; \; (x \plus{} y)_n \equal{} \sum\limits_{k \equal{} 0}^{n}{n\choose k}(y)_{n \minus{} k}(x)_k \;
\]
which in fact is [b]Chu-Vandermonde identity.[/b] Further put $ x \equal{} y \equal{} \frac {1}{2}$  in (2.2) .

[b]Possible generalizations:[/b] [b]I.[/b] For arbitrary  real or complex parameters $ a, b , c$ we have
\[ (I)\; \; \; \; \; \begin{array}{|c|} \hline \displaystyle \sum\limits_{k \equal{} 0}^{n}{a \plus{} bk\choose k}{c \minus{} bk \choose n \minus{} k} \equal{} \displaystyle \sum\limits_{k \equal{} 0}^{n}{a \plus{} c \minus{} k\choose n \minus{} k}b^{k} \\
\hline \end{array}\; .
\]
When $ (a,b,c) \equal{} \left(0, 2 , 2n\right) ,$  the identity (I) is the same with your proposed equality.
The equality (I) is known as [b]Jensen identity.[/b] It is said that  (I) is an [i] "abelization variant"[/i] of  Chu-Vandermonde identity.
[b]II.[/b] Suppose that $ \minus{} C\not \in {\mathbb N} \;$ and $ \; C \minus{} A \minus{} B > 0$. Then
\[ (II)\; \; \; \;\begin{array}{|c|} \hline \displaystyle \sum\limits_{k \equal{} 0}^{\infty}\frac {(A)_k(B)_k}{k!(C)_k} \equal{} \displaystyle \frac {\Gamma(C)\Gamma(C \minus{} A \minus{} B)}{\Gamma(C \minus{} A)\Gamma(C \minus{} B)} \\
\hline \end{array}\; .
\]
[b]III.[/b]   For $ q\in (0,\infty)\; ,\; q\ne 1 ,\; k \in {\mathbb N}$ we adopt the  notations  \ :
\[ \left\{\begin{array}{lll} \displaystyle [x]_q & \equal{} & \displaystyle \frac {q^x \minus{} 1}{q \minus{} 1} \\
& \\
\displaystyle \left[k\right]_q \; !\; & \equal{} & \prod\limits_{\nu \equal{} 1}^{k}[j]_q \; ,\; \; [0]_q!: \equal{} 1 \; \\
& \\
\displaystyle \left[\begin{array}{c} n \\
k \end{array}\right]_q & \equal{} & \displaystyle \frac {[n]_q !}{[k]_q! [n \minus{} k]_q!} \; ,\; \; k\in \{0,1,\ldots ,n\} \\
& & \\
\displaystyle \left[x;q\right]_k & \equal{} & \displaystyle \prod\limits_{\nu \equal{} 0}^{k \minus{} 1}[x \plus{} \nu]_q \; ,\; \; [x;q]_0 \equal{} 1 \end{array}\right. \; .
\]
Then
\[ (III)\; \; \begin{array}{|c|} \hline \\
\displaystyle \left[x \plus{} y;q\right]_n \equal{} \displaystyle \sum\limits_{k \equal{} 0}^{n} \left[\begin{array}{c} n \\
k \end{array}\right]_q \; q^{ky}[x;q]_k[y;q]_{n \minus{} k} \\
 \\
\hline \end{array}\; .
\]
In the case $ x \equal{} y \equal{} \displaystyle \frac {1}{2} ,$ for $ q\to 1$ , (III)  is your identity.

[b]Try to prove (I)--(III) .[/b]

In the Clay Math Research Academy the following proof was found by the combinatorics group:

Consider a random walk of 2n steps that go always right-up or right-down (so the steps are in diagonals). So we begin from $(0,0)$ and end up in $(2n, x)$ for some even integer $x$.

Clearly there are $2^{2n}$ such paths

Now we do a bijection to map some special paths counted by $\binom{2k}{k}\binom{2n-2k}{n-k}$ to good paths.

The idea is the following:

Pick a path, and pick the last point where it touch the $x$ axxis. let it be $(2n-2k,0)$ there are $\binom{2n-2k}{n-k}$ such paths. Now the rest is a path of lenght $2k$ that never goes below the diagonal, we must show there are $\binom{2k}{k}$ such paths. I have a nice bijection that proves it, pick a path from $(0,0)$ to $(2k,0)$ and consider the leftmost downest peack. put a new origin in there and put the first part of the walk backwards from the ending of the first path.

just wondering... is the identity $\sum_{i=0}^n\binom{a}{i}\cdot\binom{b}{n-i}=\binom{a+b}{n}$ impossible to prove algebraically?

i did it in class, tried to prove it algebraically, with no success of course; after that, the teacher gave the very nice, short, etc. combinatorical proof

[quote="blahblahblah"]Consider the coefficient of $x^n$ in $(1+x)^{a+b}$ and $(1+x)^{a}(1+x)^b$[/quote]
For $ c, p,q\in {\mathbb N} , c\le \min{(p,q)} , $ try to find the coefficients of $ x^{c} $ in both sides of the identity $
(1+t)^{p}(1+t)^{q}=(1+t)^{p+q} .$ The answer as above !

[b]But,...[/b] " A simple proof is important when this enable us to find another nice generalizations." Let us try starting with the identity   $ \begin{array}{|cc|} \hline
 &\\
(1)\; \; & \; \; \displaystyle  e^{xh(t)}e^{yh(t)}=\displaystyle e^{(x+y)h(t)}\\
&\\
\hline
\end{array}    $ where :
[b] Case 1: $ \begin{array}{|c|} \hline
 h(t)=t\\
 \hline
 \end{array}
  $ .[/b] Further we
shall work with formal power series and there are used some elementary notions from [i]Combinatorics[/i] or [i] Theory of generating functions[/i]. Because \[(*)\; \; \; \; \left( \sum\limits_{k=0}^{\infty}A_k\frac{t^k}{k!}\right)\cdot
\left( \sum\limits_{k=0}^{\infty}B_k\frac{t^k}{k!}\right)=
\sum\limits_{k=0}^{\infty}\left(\sum\limits_{j=0}^{k}{k\choose j}
A_jB_{k-j}\right)\frac{t^k}{k!}\; ,
\]
if we identify the coefficient of $ t^k $ we find the well-known  binomial identity $  (x+y)^k=\sum\limits_{j=0}^{k}{k\choose j} x^{k-j} y^{j}\; . $
[b]Case 2: [/b]   observe that $ (2)\; \; \; (1+t)^{x}(1+t)^{y}=(1+t)^{x+y} $ suggest us to use the same method .
It's possible ? The answer is affirmative , because (2) may be written  as  in (1) but with $ \begin{array}{|c|}
 \hline
\\
\displaystyle h(t)=\displaystyle \frac{\ln{(1+t)}}{t}\\
\\
\hline
\end{array}\; .
$ Because $\displaystyle (1+t)^x=\displaystyle \sum\limits_{k=0}^{\infty}(x)_k\frac{t^k}{k!}\; , $ by identifying the coefficients of $ x^k $ (see (*)) ,  one finds the [i]Chu-Vandermonde identity[/i]
\[(3)\; \; \;
(x+y)_k =\sum\limits_{j=0}^{k}{k\choose j}(x)_{n-k}(y)_k\; ,
\]
where $ (z)_k $ is the so-called Pochhammer symbol defined as $(z)_0=1\; ,\; (z)_k=z(z+1)\cdots (z+k-1)\; . $ Further,if you like put $x=-a \; ,\; y=-b $ in (3)  and we give \[ {a+b \choose k}=\sum\limits_{j=0}^k{a\choose j}{b\choose k-j}\; ,
\; \; a,b\in {\mathbb C}.
\]
[i]In the following ,[/i] let us try to generalize above questions. Following problem arise :
[b]i)[/b] How we must select the function (the formal power series) $ h(t) $ in (1) ? Of course such that the coefficients $ b_k(x) $ in the development \[(4)\;  \; \; \; \begin{array}{|c|}
\hline
\\
 \displaystyle e^{xh(t)}=\displaystyle \sum\limits_{k=0}^{\infty}b_k(x)
 \frac{t^k}{k!} \\
 \\
 \hline
 \end{array}
\]
to be polynomials and moreover, for each $ k \in {\mathbb N} $ of   the exact degree $ k .$ In both particular cases we have $h(0)=0$ and $ h ^{\prime}(0) \ne 0 . $ Try to prove following propositions
[b]Lemma 1. [/b] [i]For each  $k\in {\mathbb N} $ the coefficients $
b_k $ from (4) are polynomials of exact degree $ k $ , iff
\[(5)\; \; \; \;  h(t)=h_1 t+h_2t^2+\ldots \; \; \; \; \mbox{with}\; \; h_1\ne 0\;
.\] [/i]
[b]Lemma 2. [/b] [i] Suppose that $ h(t) $ is as in (5) and let the polynomial sequence $  \left(b_k(x)\right)_{k=0}^{\infty} $ generated by (4). Then this sequence is binomial, i.e.
\[\begin{array}{|c|}
\hline
 b_k(x+y)=\sum\limits_{j=0}^{k}{k\choose j
}b_{k-j}(x)b_j(y)\\
\hline
\end{array}\; ,\; \; \forall k\in {\mathbb N}\;  .
\]
Moreover every binomial sequence has a generating function as in (4)-(5).
 [/i]

[b]In conclusion, let us note [/b]that :
[b]1)[/b] Binomial polynomials are very important in Combinatorics, Theory of Enumeration, Umbral Calculus or Finite Operator Calculus (a modern variant of the so-called Calculus of Finite Differences).
Some important contributors in Umbral Calculus  are: Gian-Carlo Rota, Steven Roman,R.Mullin, A. Odlyzko,... . If someone need exact references, please inform me.
[b]2)[/b] The proof of original proposed equality , starting with  $(1+t)^p(1+t)^q=(1+t)^{p+q} $ was important. However, most important was to write it in the equivalent   form $ e^{xh(t)}e^{y(h(t)}=e^{(x+y)h(t)} $ with $ h(t) $  as in case 2.
Regards,Alex

where can i learn more about generating functions? (on the net i mean)

[quote="blahblahblah"]Google 'generatingfunctionology'.[/quote]
It's OK ! However let us note also following references:
[1]E.B.Mc BRIDE ,[i] Obtaining generating functions[/i], Springer Tracts in Natural Philosophy 21(1971), Springer Verlag,Berlin.
[2]Ivan NIVEN ,[i]Formal power series[/i], Amer.Math.Monthly (76) 8(1969) 871--889.

and one last thing: in the expression ${n \choose k}$, what $n$ and $k$ be?

I saw in flip2004's post that $n$ can be in $\mathbb{C}$, but $k$ can be only an integer, right?

In essense, $k$ indexes the product $\binom{n}{k}$ - it defines a product containing $k$ terms in the numerator and $k$ in the denominator.  What would it mean for the product to contain, say, $0.7$ terms?

$n \choose k$ can be interpolated to arbitrary $n$ and integer $k$ as a polynomial in $n$, or interpolated to (some) complex $n$ and $k$ using the Euler beta and gamma functions.  These interpolations agree.

[quote="Pascual2005"]Now the rest is a path of lenght $2k$ that never goes below the diagonal, we must show there are $\binom{2k}{k}$ such paths. I have a nice bijection that proves it, pick a path from $(0,0)$ to $(2k,0)$ and consider the leftmost downest peack. put a new origin in there and put the first part of the walk backwards from the ending of the first path.[/quote]

i can't understand how you construct this bijection. can you detail it a bit?

[quote="perfect_radio"]in the expression ${n \choose k}$, what $n$ and $k$ be? I saw in flip2004's post that $n$ can be in $\mathbb{C}$, but $k$ can be only an integer, right?[/quote]
Let $z$ be a complex number  and  $k\in {\mathbb N}: =\{0,1,...\} .$  Then  ${z\choose k}: = \frac{z(z-1)\cdots (z-k+1)}{k!} \; .$ At the right we have a polynomial of degree $k$  which is well-defined.
Next consider that  $z\in {\mathbb C}$ such that $-z\not\in {\mathbb N} .$  Using Gamma function there is possible to write  ${n\choose k}: = \frac{\Gamma(z+1)}{\Gamma(z-k+1)\Gamma(k+1)} .$
Recently in literature there is also the notion of "[b] Roman symbol[/b]" (try on Google) which generalizes the polynomials (binomial coefficients)  ${z\choose k}\; , k\in \{0,1,...\} .$

[i]YAP![/i][hide=" :lol: "]Yet Another Proof![/hide]
Let $ S_n(X) \equal{} \sum_{i\equal{}0}^n \binom{2i}{i}\binom{2n\minus{}2i}{n\minus{}i} X^{n\minus{}i}$
Check that :
$ X^n S_n \left(\frac 1X \right) \equal{} S_n(X)$ and $ S'_{n\plus{}1}(X) \equal{} 4XS'_n(X) \plus{} 2S_n(X)$
Differentiate the first one, set $ X\equal{}1$, plug the result into the second one to get :
$ \forall n \in \mathbb{N}, S_{n\plus{}1}(1) \equal{} 4S_n(1),$
hence the result.

What is the proof using the generating function for $ \frac{1}{\sqrt{1\minus{}4x}}$??
I don't really know how to do it but I tried doing $ \frac{1}{\sqrt{1\minus{}4x}}*\frac{1}{\sqrt{1\minus{}4x}}\equal{}\frac{1}{{1\minus{}4x}}$ but I got messed with the algebra.


modular arithmetic
algebra
polynomial
calculus
integration
number theory solved
number theory

Let $p$ be a prime number
$p|x(a_1-b_1)+x^2(a_2-b_2)+\cdots+x^n(a_n-b_n)$ for all integer $x$
Is it true, that:
$a_1\equiv{b_1}\pmod{p}$
$a_2\equiv{b_2}\pmod{p}$
                 ...
$a_n\equiv{b_n}\pmod{p}$

No, since, for example, $x^p\equiv x$ mod $p$ for all $x$ by Fermat's theorem, and so $p|x(1-0)+x^p(0-1)$ for all $x$.

A polynomial of degree $n$ has at most $n$ roots in an integral domain/a field...


[quote="MTM"]For every positive integer n, let f(n) denote the number obtained by reversing the order of digits in the decimal form of n. (For example, f(2500)=52, f(1456)=6541.) Find all positive integers k, such that for any multiple n of k, k also divides the number f(n).[/quote]

there's no solution?

[quote="Rust"]$ k \equal{} 10^m \minus{} 1,\frac {10^m \minus{} 1}{3},\frac {10^m \minus{} 1}{9}$. It is easy to chek, that these $ k$ work. But prove, that only these k work long. See solution in Russian forum dxdy.[/quote]

k=333 is not solution.

You are right, I forget, that these numbers are answer for another question.
These problem is not hard.
1, Prove, that $ (k,10)\equal{}1$. Let $ (k,10)\not \equal{}1$. Consider number $ n\equal{}k([\frac{10^l}{k}]\plus{}1)$. For big l first digit of n or last digit of f(n) is 1.
Therefore $ k\not |f(n)$.
2. Consider mbnimal l, suth that $ k|10^l\minus{}1$ (it exist, because $ (k,10)\equal{}1$).
$ k|n\equal{}\sum_{i\equal{}0}^m a_i10^i$ if and only if $ k|\sum_{i\equal{}0}^{l\minus{}1}b_i10^i\equal{}t(n)$, were $ b_i\equal{}(a_i\plus{}a_{i\plus{}l}\plus{}a_{i\plus{}2l}\plus{}....)\mod k$, because, obviosly $ n\equal{}t(n)\mod k$..
Let $ a*k\minus{}10^{l\minus{}1}*b\equal{}1, 0<a<10^{l\minus{}1},0<b<k$. Consider number $ n\equal{}1\plus{}\sum_{i\equal{}1}^a 10^{il\minus{}1}$. We construct n, suth that $ k|n$.
It is rasy to chek, that $ k|f(n)$ if and only if $ ab\equal{}1\mod k$. If $ l>2,ab\equal{}1\mod k$, we can take
$ a_1\equal{}10a$ and consider power $ 10^{l\minus{}2}$, ($ n\equal{}1\plus{}\sum_{i\equal{}1}^{a_1}10^{il\minus{}2}$) then $ a_1b\not \equal{}1\mod k$
and for these n, $ k\not |f(n)$.  We prove, that $ k|99$. It is easy to chek, that all $ k|99$ work.

[quote="Rust"]You are right, I forget, that these numbers are answer for another question.
These problem is not hard.
1, Prove, that $ (k,10) \equal{} 1$. Let $ (k,10)\not \equal{} 1$. Consider number $ n \equal{} k([\frac {10^l}{k}] \plus{} 1)$. For big l first digit of n or last digit of f(n) is 1.
Therefore $ k\not |f(n)$.
2. Consider mbnimal l, suth that $ k|10^l \minus{} 1$ (it exist, because $ (k,10) \equal{} 1$).
$ k|n \equal{} \sum_{i \equal{} 0}^m a_i10^i$ if and only if $ k|\sum_{i \equal{} 0}^{l \minus{} 1}b_i10^i \equal{} t(n)$, were $ b_i \equal{} (a_i \plus{} a_{i \plus{} l} \plus{} a_{i \plus{} 2l} \plus{} ....)\mod k$, because, obviosly $ n \equal{} t(n)\mod k$..
Let $ a*k \minus{} 10^{l \minus{} 1}*b \equal{} 1, 0 < a < 10^{l \minus{} 1},0 < b < k$. Consider number $ n \equal{} 1 \plus{} \sum_{i \equal{} 1}^a 10^{il \minus{} 1}$. We construct n, suth that $ k|n$.
It is rasy to chek, that $ k|f(n)$ if and only if $ ab \equal{} 1\mod k$. If $ l > 2,ab \equal{} 1\mod k$, we can take
$ a_1 \equal{} 10a$ and consider power $ 10^{l \minus{} 2}$, ($ n \equal{} 1 \plus{} \sum_{i \equal{} 1}^{a_1}10^{il \minus{} 2}$) then $ a_1b\not \equal{} 1\mod k$
and for these n, $ k\not |f(n)$.  We prove, that $ k|99$. It is easy to chek, that all $ k|99$ work.[/quote]

That's correct.


Consider the intervals $ A\equal{}[\minus{}1,2[,\, B\equal{}]\minus{}\infty,1[\, e\, C\equal{}]0,\plus{}\infty[.$  The $ C\minus{}(A\cap B)$ is set equal to:

a) {}
b) [-1,0]
c) [-1,1[
d) [1, + $ \infty$]
e) ]1,+8[

ANSWER: D

$ A \cap B \equal{} [\minus{}1, 1)$

$ C\minus{} (A \cap B) \equal{} [1, \infty)$

I don't understand , why $ C\minus{}(A\cap B) \equal{} [1,\infty)$ ?
Can you explain me ?  :blush:

Sorry for the delay.

$ A \cap B \equal{} [\minus{}1, 1)$ and $ C$ is all the positive real numbers, so the set $ C \minus{} (A \cap B)$ consists of all the positive real numbers which are not in the interval $ \minus{}1 \leq x < 1$, that is $ x \geq 1$, that is $ [1, \infty )$.

You could also draw some number lines if that would help.

I hope this makes it clearer.

I am not getting what the heck you are writing for the question are you basically saying that B is in A and C is in b so C is also in A. so all the elements are in A but you have to find the union of of A and B.

If that is what the question basically is I am confused that is very confusing and not very hard but because it is confusing it makes it harder

I'm not saying anything of the sort. I don't know how to explain it further in English.

Forgive me if I'm wrong but I'm guessing that English is not your first language; perhaps we have another language in common.

Ok, Thanks Andrew.
I understand now. ;)
Yes, my english is not very good.

Boa tarde, luiseduardo.

Your English is fine; I was referring to a different post which I found difficult to understand at first.


geometry
3D geometry
analytic geometry
vector
trigonometry

Given a cube with edges of length 1, $e$ the midpoint of $[bc]$, and $m$ midpoint of the face $cdc_1d_1$, as on the figure.
Find the area of intersection of the cube with the plane through the points $a,m,e$.

[img]http://www.mathlinks.ro/Forum/album_pic.php?pic_id=279[/img]

Put the coordinate origin at the point a and the positive x-, y-, z-axes along the rays $ab, ad, aa_1$. The plane $\pi \equiv (aem)$ through the points $a = (0, 0, 0),\ e = \left(1, \frac 1 2, 0\right),\ m = \left(\frac 1 2, 1, \frac 1 2\right)$ has an equation

$Ax + By + Cz = D$

Substituting the coordinates of the points $a, e, m$, we get 3 equations for the 4 unknowns coefficients A, B, C, D:

$0 = D$

$A + \frac B 2 = D$

$\frac A 2 + B + \frac C 2 = D$

which leads to $B = -2A, C = 3A$. Putting A = 1 (the equation of the plane can be multiplied by an arbitrary number different from zero), we get the plane equation as

$x - 2y + 3z = 0$

The plane $\pi$ intersects the line $cc_1$ at a point p with coordinates $p = (1, 1, z_p)$. Substituting this to the equation of the plane $\pi$,

$1 - 2 + 3z_p = 0,\ \ z_p = \frac 1 3$

Likewise, the plane $\pi$ intersects the line $dd_1$ at a point q with coordinates $q = (0, 1, z_q)$. Substituting this to the equation of the plane $\pi$,

$0 - 2 + 3z_q = 0,\ \ z_q = \frac 2 3$

Knowing the xyz-coordinates of the points e, p, m, q, we know their radius vectors $\vec e, \vec p, \vec m, \vec q$:

$\vec e = \left(1, \frac 1 2, 0\right),\ \ \vec p = \left(1, 1, \frac 1 3\right),\ \ \vec m = \left(\frac 1 2, 1, \frac 1 2\right),\ \ \vec q = \left(0, 1, \frac 2 3\right)$

The areas of the triangles $\triangle aep, \triangle apm, \triangle amq$ are equal to

$S(\triangle aep) = \frac 1 2 |\vec e||\vec p| \sin \widehat{eap} = \frac 1 2 |\vec e \times \vec p|$

$S(\triangle apm) = \frac 1 2 |\vec p||\vec m| \sin \widehat{pam} = \frac 1 2 |\vec p \times \vec m|$

$S(\triangle amq) = \frac 1 2 |\vec m||\vec q| \sin \widehat{maq} = \frac 1 2 |\vec m \times \vec q|$

Calculating the vector products:

$\vec e \times \vec p = \left(1, \frac 1 2, 0\right) \times \left(1, 1, \frac 1 3\right) = \left(\frac 1 6, -\frac 1 3, \frac 1 2\right)$

$\vec p \times \vec m = \left(1, 1, \frac 1 3\right) \times \left(\frac 1 2, 1, \frac 1 2\right) = \left(\frac 1 6, -\frac 1 3, \frac 1 2\right)$

$\vec m \times \vec q = \left(\frac 1 2, 1, \frac 1 2\right) \times \left(0, 1, \frac 2 3\right) = \left(\frac 1 6, -\frac 1 3, \frac 1 2\right)$

Thus we see that all 3 triangles have the same area equal to

$S_\triangle = \frac 1 2 \sqrt{\frac{1}{36} + \frac 1 9 + \frac 1 4} = \frac{\sqrt{14}}{12}$

and that the area of the pentagon $aepmq$ (actually the quadrilateral $aepq$, for the points $p, m, q$ are collinear) is equal to

$S(aepmq) = S(\triangle aep) + S(\triangle apm) + S(\triangle amq) = 3 S_\triangle = \frac{\sqrt{14}}{4}$

That's an option too. :) I had another one in mind, but yours is probably also a lot simpler.

[quote="shobber"][quote="Peter VDD"]There's a MUCH easier and nicer solution... try to find it. ;)[/quote]
First find the angle between plane $AEM$ and $ABCD$, then the area of $AECD$, then use $S'=S \cos{\theta}$.

Is it the easier solution you meant, Peter?[/quote]

could you please explain how you know that? is is some property (of projection?) that i don't know

This is a well known Theoreme: If two planes form an angle $\alpha$ and the ortogonal progection of figure from the first plane $A$ in the second is $A'$ then $S(A')=S(A)*\cos \alpha$
To prove this first consider $\Delta ABC$ where $AB$ are on the line $l$ common for both planes (sorry dont know the word in english). Then prove for a  triangle with only one vertex on $l$ and then for an arbitrary triangle.
As any polygon is formed from triangles it is valid for any polygon.
For any figure regard it as formed from infity of very small triangles.

[quote="delta"]This is a well known Theoreme: If two planes form an angle $\alpha$ and the ortogonal progection of figure from the first plane $A$ in the second is $A'$ then $S(A')=S(A)*\cos \alpha$
To prove this first consider $\Delta ABC$ where $AB$ are on the line $l$ common for both planes (sorry dont know the word in english). Then prove for a a triangle with only one vertex on $l$ and then for an arbitrary triangle.
As any polygon is formed from triangles it is valid for any polygon.
For any figure regard it as formed from infity of very small triangles.[/quote]

i understand, thank you

[quote="delta"][hide]I suppose that the solution Peter VDD had in mind is:
extend $ae$ and $pq$ until they intersect in $s$. Then find area of $\Delta aqs$ and $\Delta eps$. [/hide][/quote] :yup:[hide]And this is trivial due to heron's formula.[/hide]

Given a cube with edges of length 1, $e$ the midpoint of $[bc]$, and $m$ midpoint of the face $cdc_1d_1$, as on the figure.
Find the area of intersection of the cube with the plane through the points $a,m,e$.
[img]https://1.bp.blogspot.com/-tKTjm0ObL-E/XWuvxQdKKZI/AAAAAAAAKpM/3mYA93r8D6E1kFumgNVVz2HDyiNkTeCqACK4BGAYYCw/s400/1998%2Bflandres%2Bp2.png[/img]


[quote="gemath"]Given are $\triangle ABC$ with Fermat point $F$ and centroid $G$ with any $M$ on plane prove that
$MA^{3}+MB^{3}+MC^{3}\ge(MG^{2}+\frac{a^{2}+b^{2}+c^{2}}{9})(FA+FB+FC)$
equal when $ABC$ is equaliteral triangle and  $M\equiv$ center of it :)  :)[/quote]
May be not hard.
$MA^{3}+MB^{3}+MC^{3}\ge\frac{1}{3}(MA^{2}+MC^{2}+MC^{2})(MA+MB+MC)\ge(MG^{2}+\frac{a^{2}+b^{2}+c^{2}}{9})(FA+FB+FC)$
because$\frac{1}{3}(MA^{2}+MC^{2}+MC^{2})=(MG^{2}+\frac{a^{2}+b^{2}+c^{2}}{9})$
and $MA+MB+MC\geq FA+FB+FC$

ok thank you for good solution , I found it quite intricate but really it has a simple solution of you  :blush:  :blush:


inequalities
real analysis
real analysis unsolved

Let $ f(x)\equal{}c_0\minus{}\sum\limits_{i\equal{}1}^\infty c_ix^i$, where $ c_0>c_1>c_2>,\cdots,>0$. For a positive integer $ p\ge 2$, define $ g(x)\equal{}[f(x)]^{\minus{}p}\equal{}\sum\limits_{i\equal{}0}^\infty c'_ix^i$, show that $ c'_1>c'_2>c'_3,\cdots,>0$.

Nonsense again: $ (1\minus{}x)^{\minus{}2}$ (or, if you insist on strict inequalities, a slight perturbation thereof) is an obvious counterexample to the decreasing property of the new coefficients.

In general, before proving anything (or asking how to prove anything), it is always a good idea to consider a few simple examples you can investigate completely and to see if your conjecture holds for them :).


geometry
circumcircle
power of a point
radical axis
similar triangles
geometry solved

I don't have a complete solution, but I've noticed quite a few things about the configuration:

First of all, we don't need to stick to $H_i$: $H_1H_2$ is the radical axis of $\omega_1,\omega_2$, where $\omega_1,\omega_2$ are the circles having $AC,BD$ as diameters respectively. Try to show this, it's not hard at all.

Next, try to show that $X$ is on this line iff $AC=BD$. I can show the $\Leftarrow$ part, and maybe the $\Rightarrow$ part follows by some movement argument, but I'm not sure, I'll have to look into it. Also notice that when $AC=BD$, $QX,QY$ are the bisectors of the angle formed by $AC,BD$. This helps a lot in proving the $\Leftarrow$ part.

I think I've got it (the $\Rightarrow$ part):

$X$ is on the radical axis of $\omega_i$ iff $XO_1^2-\frac {AC^2}4=XO_2^2-\frac {BD^2}4$, where $O_1,O_2$ are the midpts of $AC,BD$ respectively. By applying the median theorem, this is equivalent to $XA^2+XC^2-AC^2=XB^2+XD^2-BD^2\ (*)$. However, it's easy to show that the triangles $XAC,XBD$ are similar, which means that $(*)$ translates to the triangles $XAC,XBD$ being congruent $\Rightarrow AC=BD$.

[quote="grobber"]I don't have a complete solution, but I've noticed quite a few things about the configuration:

First of all, we don't need to stick to $H_i$: $H_1H_2$ is the radical axis of $\omega_1,\omega_2$, where $\omega_1,\omega_2$ are the circles having $AC,BD$ as diameters respectively. Try to show this, it's not hard at all.[/quote]

Let T, L be the midpoints of AC, BD
we have H1,H2 is the radical axis of the circles having AC,BD as diameters
iff  vector(H1H2)*vector(TL)=0
but i think it is only right when PCD and PAQ are similar
Can you check it again?

[quote="Master"]Let $APD$ be a triangle, and $B$ and $C$ be two points on its sides $AP$ and $PD$, respectively. The diagonals of the quadrilateral $ABCD$ intersect at a point $Q$.
Let $H_{1}$ and $H_{2}$ be the orthocenters of triangles $APD$ and $BPC$, respectively.
The circumcircles of triangles $ABQ$ and $CDQ$ intersect at a point $X$ (apart from $Q$).
The circumcircles of triangles $BCQ$ and $DAQ$ intersect at a point $Y$ (apart from $Q$).
Prove that, if the points $H_{1}$, $H_{2}$, $X$ are collinear, then the points $H_{1}$, $H_{2}$, $Y$ are collinear.[/quote]

Here is a simplification of Grobber's solution:

For any three points P, Q and R, we call QR(P) the power of the point P with respect to the circle with diameter QR.

At first, let U and V be the feet of the altitudes of triangle APD issuing from the vertices A and D, respectively. Since $H_{1}$ is the orthocenter of the triangle APD, the point $H_{1}$ lies on the two altitudes AU and DV. Now, $\measuredangle AVH_{1}= 90^{\circ}$ and $\measuredangle DUH_{1}= 90^{\circ}$, so that $\measuredangle AVH_{1}= \measuredangle DUH_{1}$. Also, $\measuredangle AH_{1}V = \measuredangle DH_{1}U$. Thus, the triangles $AVH_{1}$ and $DUH_{1}$ are similar. Thus, $AH_{1}: VH_{1}= DH_{1}: UH_{1}$, so that $AH_{1}\cdot UH_{1}= DH_{1}\cdot VH_{1}$. But $AH_{1}\cdot UH_{1}$ is the power of the point $H_{1}$ with respect to the circle with diameter AC (this is because the point U lies on this circle, since < AUC = 90°). Similarly, $DH_{1}\cdot VH_{1}$ is the power of the point $H_{1}$ with respect to the circle with diameter BD. Hence, the equation $AH_{1}\cdot UH_{1}= DH_{1}\cdot VH_{1}$ yields that the point $H_{1}$ has equal powers with respect to the circles with diameters AC and BD. In other words, the point $H_{1}$ lies on the radical axis of these two circles with diameters AC and BD. Similarly, the point $H_{2}$ also lies on this radical axis. Thus, the line $H_{1}H_{2}$ is the radical axis of the circles with diameters AC and BD.

Now, we have to prove that the point X lies on the line $H_{1}H_{2}$ if and only if the point Y lies on the line $H_{1}H_{2}$. In other words, we have to prove that the point X lies on the radical axis of the circles with diameters AC and BD if and only if the point Y lies on this radical axis. Since the radical axis of two circles is the locus of all points having equal powers with respect to these two circles, this is equivalent to showing that the point X has equal powers with respect to the circles with diameters AC and BD if and only if the point Y has equal powers with respect to these two circles. In other words, we must show that AC(X) = BD(X) holds if and only if AC(Y) = BD(Y).

Actually we will prove that AC(X) = BD(X) holds if and only if AC = BD. Then, by analogy, it will follow that AC(Y) = BD(Y) holds if and only if AC = BD, too, and this will imply the equivalence of AC(X) = BD(X) and AC(Y) = BD(Y), solving the problem.

Since the point X lies on the circumcircle of triangle ABQ, we have < XAQ = < XBQ. In other words, < XAC = < XBD. Similarly, < XCA = < XDB. Thus, the triangles XAC and XBD are similar. But in similar triangles, similar linear values have equal ratios. In particular, for our two similar triangles XAC and XBD, it follows that AC(X) : BD(X) = AC : BD. But this immediately implies that AC(X) = BD(X) holds if and only if AC = BD. And the solution is complete.

  Darij

I participate that contest :)
This problem was really exremely hard.
Nobody proved it including our Chinese guests.
:wallbash: :)

I took many days to find this generalization.

Let $M, N$ be the intersections of the circles of diameter $AC$ and $BD$,  then $M, N, X, Y$ are cyclic(or collinear).

also we can get that $H_1, H_2, M , N$ are on the radical axis of circles of diameters $AC$, $BD$, $PR$  ( $R$ is the intersection of $AD$ and $BC$).

therefore, $H_1 H_2$ passes through $X$ iff $H_1 H_2$ passes through $Y$.

Here is the sol
1    Lemma (left of the pic)
      $H_1, H_2, M , N$ are on the radical axis of circles of diameter $AC$, $BD$, $PR$  ( $R$ is the intersection of $AD$ and $BC$)
      Proof of lemma,
         Just consider the power of $H_1$ and $H_2$ to the circles of diameters $AC$, $BD$, $PR$ respectively.

2     $M, N, X, Y$ are cyclic (right of the pic)
      Proof (use inversion )
      Let $Q$ be the center of inversion, $A' , B', C', D', X', Y', M', N'$ be the images of $A, B, C, D, X, Y, M, N$
      Thus $X'=A'D' \bigcap B'C'$, $Y'=A'B' \bigcap C'D'$ , also $N',N'$ are the intersection of the circles of diameters $A'C'$, $B'D'$,      (Because the inversion center $Q=A'C' \bigcap B'D'$)
      By the lemma the circles of diameters $A'C'$, $B'D'$, $X'Y'$ have the same radical axis say $M'N'$, so $M',N'$ are also on circle of diameter $X'Y'$, then $M',N',X',Y'$ are cyclic, hence $M, N, X, Y$ are cyclic $Q.E.D.$


Let $ (u_n)$ be a sequence. Define for all $ n$

$ v_n \equal{} \frac{u_1 \plus{} u_2 \plus{} \cdots \plus{} u_n}{n}$

i) Suppose that $ u_n \ge 0$ for all $ n \ge 1$, show that:

$ \lim \text{inf }u_n \le \lim \text{inf }v_n \le \lim \text{sup }v_n \le \lim \text{sup }u_n$

ii) Suppose again that $ u_n \ge 0$ for all $ n \ge 1$, show that if $ \lim u_n$ exists, then $ \lim v_n$ exists and $ \lim u_n \equal{} \lim v_n$.

iii) Suppose now that $ u_n$ is a convergent sequence but not necessarily positive for all $ n \ge 1$, let $ \alpha$ be the limit of $ u_n$, show that $ \lim v_n \equal{} \alpha$.

[quote="gotztahbeazn"]
ii) Suppose again that $ u_n \ge 0$ for all $ n \ge 1$, show that if $ \lim u_n$ exists, then $ \lim v_n$ exists and $ \lim u_n \equal{} \lim v_n$.

iii) Suppose now that $ u_n$ is a convergent sequence but not necessarily positive for all $ n \ge 1$, let $ \alpha$ be the limit of $ u_n$, show that $ \lim v_n \equal{} \alpha$.[/quote]

Part (iii) is know as Cauchy's theorem. The theorem says

$ Theorem$ If exist $ \lim a_n \equal{} a$, then sequence $ b_n \equal{} \frac{a_1 \plus{} \ldots  \plus{} a_n}{n}$ is also convergent and $ \lim b_n \equal{} a$.

This is special case of Stolz theorem

$ Theorem$ Let $ (b_n)$ be strictly increasing sequence of real numbers and $ \lim b_n \equal{} b$, and let $ (a_n)$ be sequence in $ R$. If there exist $ \lim \frac{a_n \minus{} a_{n\minus{}1}}{b_n \minus{} b_{n\minus{}1}}\equal{}l$, then we have $ \lim \frac{a_n}{b_n}\equal{}l$.

You can prove this theorem using: $ \frac{a_n}{b_n} \minus{} l \equal{} \frac{a_m \minus{} lb_m}{b_n} \plus{} (1 \minus{} \frac{b_m}{b_n})(\frac{a_n \minus{} a_m}{b_n \minus{} b_m} \minus{} l), n>m$.


calculus
integration
algebra
polynomial
calculus computations

Determine for $k=0, 1, 2,3 , 4$ the polynomial $p_{k}(t)$ of degre at most $k$ that minimizes the integral
\[\int_{-2}^{2}|x^{4}-p_{k}(x)|^{2}dx \]

This is a least-squares problem; we have the inner product $\langle f,g\rangle=\int_{-2}^{2}f(x)g(x)\,dx$. Start with the basis $1,x,x^{2},x^{3},x^{4}$ for polynomials of degree $\le 4$, and apply Gram-Schmidt to get an orthogonal basis. For each $k$, $p_{k}$ is the orthogonal projection of $x^{4}$ onto the space spanned by the first $k+1$ of these vectors. An orthonormal basis makes calculating these projections easy.


MATHCOUNTS calculus geometry AMC AIME USA(J)MO USAMO

who do you think will be first in indiana next year. yes it is legal to vote for yourself.

that would be me :D  i don't stand a chance i just voted for myself anyways

[quote="indianamath"]huh who's anirudh[/quote]

lmao! wow.. but after i read that, for some reason, the bottom right corner of my vision sorta just blacked out :huh:

i'm gonna vote lyndon ji just cause he's the only one i know, and anirudh's annoying :D

whoa... where the hell did this come from??... im not voting -_-... so ya... but if i would, i would put youkow homma down as a choice (definitely)

i voted justin ahmann. that kid is a beast. actually, it's going to be a pretty close call. i just don't think andrew kaiser or michael mardini will be first (or anirudh cuz he's annoying :D . jk, but still...)

but that could be way off, prove me wrong guys :lol: !!

Yeah I'd put Youkow Homma down as an option.

However honestly my vote would go to Lyndon. Justin as a close second.

If I had to make an on the spot prediction for next year:

1. Lyndon
2. Justin
3. Yuqing
4. Youkow

Huh I left off all Honey Creekers. =/. I guess Michael and Andrew are 5th and 6th? Marissa can be like 10th.

uh-_-hu... justin ahmann does things during team rounds... lol XD... its... kinda...

lol i voted for you despite your constant snubbing of me.

cb
bb
ctpt

oh and remember "leaves?" from science bowl. haha.

Anyhow now that I think of it, my vote goes to Yuqing. Always vote for the kid that has the most desire to win, and that's Yuqing.

Lyndon cares more about higher math [and is addicted to starcraft :P], and Justin... doesn't seem to care that much.

[quote="indianamath"]omg you guys know how behind i am in math compared to lyndon right?[/quote]

That doesnt matter in mathcounts.  Speed is the most improtant thing that matters...plus you can brute force many of the problems.

brute force doesn't work in mathcounts due to the time restraint. Unless it's a VERY easy brute force... which doesn't really count as a brute force, does it?

Anyhow Justin took Calculus in 6th grade so he's MUCH farther ahead in math than I am. But I still beat him this year, because speed is important.

No i mean brute force like easy brute force.  Like for mnay counting problems, you can list out all the possibilities instead of having a standard way of counting (because there are so few).  Also, for some geometry problems, you can guess sides lengths and all...but I was never good at mathcounts so dont take my word on it..

And who is this Justin kid?  Is he the guy who got 2nd..because if you took caculus in 6th grade, he cant really take anymore math in school.. (unless he self taught it or leanred with tutor or something)...but if hes that high advanced in math, he'll probalby do well on stuff like AIME.

justin ahmann took calculus in 6th grade?? i feel soo inferior...

hey, wait a second. why didn't he make it to AIME? or did he?

he probably didn't take the AMC. i know...he's already done calculus and AP statistics. iamstupid :|

That is SO SPAM but i'm rating it as excellent XD.

yay USO. did u dance with anyone? Last year I was forced with mrs. prince (bleh), and mrs. sheffield asked me to ask ellie [and i did and we danced] (XD XD XD XD XD).

rofl i so want a picture of u in military gear.

see... mrs. sheffield actually knows who are you. lol

i'm guessing that Justin will win next year? he only got 1st written at NATIONALS!!!

justin got 1st written at nationals? amazing.

who wants to sign the "make Justin move" petition?
ya but what do you expect? He did calculus in 6th grade...I'm still working on algebra 2 :(

i wanna sign it.

i remember how everyone said that Justin wasn't that good. Now it backfired.

Well look on the bright side: someone from IN got first...
and plus we've got an uber genius for next year...

I'm very happy for justin, but it sorta makes me think "anyone can win on any given day", considering that when we did practice, justin's score and my score were always very close to each other, with either of us winning on any given day. And suddenly he kapownd my target lol.

I wasn't very nervous actually. I had a very good night's sleep and all that jazz. The target just had problems that didn't fit what I was good at.

[quote="indianamath"]i bet it was because justin wasn't as nervous as you.  YOu know, you even said once it was your dream since 3rd grade to win nationals, remember? lol. so, you had more to lose.[/quote]

It was your dream to win..omg no wonder you lost.  You cant dream about winning, only about losing.  paradox..

CAN I see what the target round questions were?  just to see how hard, because I heard only 2 people go perfects.

[quote="GoColts0626"]justin and lyndon go #1 and 2, either order.

rest is up for grabs[/quote]

I WILL BE THIRD

also, who's gocolts?

and i know this is reaalllly late but when did we say justin wasn't very good? All i remember was saying he wasn't that threatening after REGIONALS [when i heard he got a 39], but after state I said nothin of the sort.


trigonometry
geometry
incenter
geometry proposed

Given a triangle $ABC$ and a point $P$ inside it choose $P$ to maximize the quantity

$PA\sin{B\hat{P}C} + PB\sin{C\hat{P}A} +PC\sin{A\hat{P}B}  $

At last I got the solution. It was quite nice problem. The point we are looking for is the incenter of the triangle $ABC$. And the quantity of corresponding sum is equal to the semiperimetre of the triangle $ABC$. So my target is to prove that

$PA\sin\angle{BPC}+PB\sin\angle{CPA}+PC\sin\angle{APB}\leq\frac{AB+BC+CA}{2} (*).$
for all points $P$ Inside of traingle $ABC$. Well it was not so easy.
I used trigonometry and got that $(*)$ is equvivalent  to
$\cos{\varphi}\cos{\delta}\cos{\omega}+\cos({\alpha-\varphi})\cos({\beta-\delta})\cos({\gamma-\omega})
\leq\frac{\sin{\alpha}+\sin{\beta}+\sin{\gamma}}{2}$, where $\varphi=\angle{PAB},\delta=\angle{PBC},\omega=\angle{PCA},\alpha=\angle{BAC},\beta=\angle{ABC},\gamma=\angle{BCA}.$
And again using a little trigonometry we get another equivalent inequaliy
$\sum_{cyclic}\sin{\alpha}\cos(\frac{-\alpha+\beta+\gamma}{2}+\varphi-\delta-\omega)\leq\sin{\alpha}+\sin{\beta}+\sin{\gamma}$ which is obvious and equality holds if and only if $\varphi=\frac{\alpha}{2},\delta=\frac{\beta}{2},\omega=\frac{\gamma}{2}$ i.e. $ P$ is incenter of triangle $ABC.$


You just have to solve the characteristic equation $X^3 - 3X^2 + 3X - 1 =0$, which has $1$ as root with multiplicity $3$.
Thus, for all $n$, we have $x_n = an^2+bn+c$ for some constant $a,b,c$.
Direct checking leads to $x_n = - \frac 1 2n^2 + \frac 9 2 n - 3$.

Pierre.

When talkin bout the recurrence I have two questions:

1) What to do if there is some constant in recurrence ?

2) What to do if there is some product of variables ?

I'll be glad if someone answer me

i dont think there is any general method for 2), but for 1 you can solve the homogeneous recurrence for a general solution, then find a particular solution for yours and add the two.

for example an easy one,

$a_0 = 4, a_{n+1} = a_n + n+1$

so the homogeneous version is $a_{n+1} = a_n$ which has solutions $a_n = k$ for some k.

for a particular solution, try $a_n = \frac{n*(n+1)}{2}$ then the general solution is $a_n = k + \frac{n*(n+1)}{2}$ and since a_0 = 4, k = 4 and the solutions are

$a_n = 4 + \frac{n(n+1)}{2}$

Hello, megus!

[quote]1) What to do if there is some constant in recurrence ?[/quote]
I have been shown one technique ... it doesn't always work out nicely, though.

Suppose we have: $x_{n+2} \;= \;x_{n+1} + x_n + 3\quad[1]$

The 'next' term is: $x_{n+3} \;= \;x_{n+2} + x_{n+1} + 3\;\;[2]$

Subtract [1] from [2]: $x_{n+3} - x_{n+2} \;= \;x_{n+2}-x_{n+1} + x_{n+1} - x_n$

Simplify: $x_{n+3} - 2x_{n+2} + x_n \;= \;0$

The characteristic equation is: $X^{n+3} - 2X^{n+2} + X^n \;= \;0$

Divide by $X^n:\;\;X^3 - 2X^2 + 1 \;= \;0$

Factor: $(X - 1)(X^2 + X - 1) \;= \;0$

And get roots: $X = 1,\;\frac{-1\pm\sqrt{5}}{2}$ . . . etc.

Thank you both zscool and Soroban. So in 2) case there's no other way than "guessing" ? I don't believe it, there's always a way   :P


[quote="Silverfalcon"]Hi,

I did Problem Solving Marathon when I first got this site which was before we had MathLink and AoPS combined.. :)
Anyway, this worked out very well, going over 7 pages and I forgot how many problems we did but quite a lot. If you search for "Marathon" for just this forum, you'll find it. Just don't post there again to revive it though.[/quote]
i have painstakingly edited a lot of the problems and it resulted into this compact pdf file. feel free to download. sorry no commercializing of this file or i will sue you :)
ps: dont pm me comments about it whether you liked it or not. if you dont like it, delete it from your machine. good day :pilot:

Excellent :lol:  :D !! Thanx Palytoxin, I'm surprised no one else made a comment about this.

[quote="prototypex24"][quote="Palytoxin"]if you dont like it, delete it from your machine. good day :pilot:[/quote]

Man, after all you did, there's no way anyone won't like it[/quote]

Definitely! :) It's great!

I'm currently working on one for the MC Problem Solving Marathon.

We should write books for these problems.  :rotfl:
Palytoxin, great format!

nice job palytoxin, how long did this take you? :D  :D  :D  :D

[quote="Palytoxin"]well, here is one easy way to figure out how long it took me: i estimate that my average rate of work is about 10 min per problem. now calculate how long it took me to do it :D[/quote]
The real question is, at that rate, how long will it take you to do Marathon #2? ;)

HINT: We're on problem 310  :rotfl:

Wow, for the MC Marathon, I finished the whole thing in about an hour, so I guess that would be about $0.\overline{769230},$ or $46.\overline{153846}$ seconds. :D I did it really fast, just copied and pasted the problems. But then, I haven't done the solutions yet. And plus, look at the quality difference! :) Your's is much better.


Find the range of values of F= x^2/(1+x^4) for real values of x

[hide]we know that it cant be negative because everything is positive.  It is equal to 0 when x=0 and also approaches 0 as x goes to infinity.  im not sure how to find the upper range without differentiating it.[/hide]

$ F=\frac{1}{x^{2}+\frac{1}{x^{2}}}$ for $ x\ne 0$.

$ x^{2}+\frac{1}{x^{2}}\ge 2\sqrt{(x^{2})*\left(\frac{1}{x^{2}}\right)}=2\implies F=\frac{1}{x^{2}+\frac{1}{x^{2}}}\le \frac{1}{2}$ with equality when $ x=1$ by the AM-GM inequality.

It is clear that $ F\ge 0$ since $ x^{2}\ge 0$ and $ x^{4}+1>0$. $ F=0$ when $ x=0$.

In summary, $ F(0)=0$ and $ F(1)=1$ are the smallest and largest values, respectively, that $ F$ can take.

By the intermediate value theorem, it follows that there exists $ x\in[0,1]$ for all $ y\in\left[0,\frac{1}{2}\right]$ where $ F=y$.

Hence, $ \boxed{0\le F\le \frac{1}{2}}$.


Students interested in AoPS classes should know that AoPS offers a group discount for 4 or more or 8 or more students from the same school taking the same class.  Students must make us aware of their discount status as we do not keep track or even know which usernames are associated with any given school.

4-7 students pay 10% less for the class.

8 or more students pay 20% less for the class.

We will probably be having around 8 people taking the AIME Problem Series class, but I don't have a list of people commited to doing it. Some of them haven't signed up for the forums yet. Should I have everyone wait for enrollment until we get a list of usernames or is there any other way I can do it? Maybe have people enroll and hold off payments until the 12/23 deadline?

This sounds great.  If 8 are going to enroll, we'll give a 20% discount.  You can do this one of two ways.  You could register individually using credit cards in our automated enrollment area or you could send checks for 38.40 each.  If you enroll automated, we will have to apply the discounts by bouncing 9.60 back to the credit cards (we've done this before and it's no big deal).

Either way, email me a list of the usernames at crawford@artofproblemsolving.com.  The class begins tomorrow, so go ahead and email me as many of the names as you know for sure are signing up.


geometry
geometric transformation
dilation
power of a point
radical axis
4th edition

Did anyone solve the round 7 problems? If so, could they perhaps post them. (I didn't get anywhere.)

[quote="darij grinberg"]For problem 1: http://www.mathlinks.ro/Forum/viewtopic.php?t=17206 .
For problem 2: well, I have a synthetic one but it is quite long, and I'm not really in the mood to write it up now...

  Darij[/quote]For 1: It's unfortunate that I didn't see that sooner. Anyways I am pretty sure that no-one cheated :)
For 2, Darij I am very interested in your (synthetical) solution. Can you post it in the future?
For 3, it's an application of [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=150]Perron's Criterion[/url] I made up.

I have a proof for number 2 using inversion and some cool theorem in Darij's Awesome geometry web site. Since I already wrote it up, i will just copy and paste. (It's shorter than it looks, I over elaborated in the details.)

{\bf Solution:}
Let $ D$, $ E$, $ F$ be where the incircle $ I$ touches the lines $ BC$, $ AC$, and $ AB$ respectively. Let $ B_1$ be the midpoint of $ BF$, $ B_2$ the midpoint of $ BD$, $ C_1$ the midpoint of $ CE$, $ C_2$ the midpoint of $ CD$, $ A_1$ the midpoint of $ AF$ and $ A_2$ the midpoint of $ AE$.
Let $ B_1B_2 \cap C_1C_2 \equal{} P$, $ A_1A_2 \cap C_1C_2 \equal{} Q$, $ B_1B_2 \cap A_1A_2 \equal{} R$. Then $ PQ \| C_1C_2 \| ED$. Similarly, $ PR \| FD$, and $ QR \| FE$. This implies that $ \bigtriangleup DEF$ and $ \bigtriangleup PQR$ are similar and their corresponding sides are parallel. Thus, there is a unique dilation that carries $ \bigtriangleup DEF$ to $ \bigtriangleup PQR$. Let the centre of this dilation be K. Then by the definition of the dilation centre, $ KDP$, are collinear. Similarly, $ KEQ$ and $ KFR$ are collinear. We now show that $ A'KD$ are collinear.

	Given a circle with centre $ (x_0, y_0)$ and radius $ r$, define the power of the point $ (x, y)$ with respect to the circle as $ (x \minus{} x_0)^2 \plus{} (y \minus{} y_0)^2 \minus{} r^2$. Define the radical axis of two circles as the locus of points which have equal powers with respect to the two circles. It is well-known that the radical axis is a line. Also, given any 3 circles, the 3 radical axes with respect to each pair of the circles are concurrent, at what is called the radical centre with respect to the 3 circles. (This follows easily from the transitivity of our definition of the power of a point.)

	If we think of points $ B$ and $ C$ as circles with centre $ B$ and $ C$ and radius 0, we will show that $ P$ is the radical centre of incircle $ I$, the "circle" $ B$, and the "circle" $ C$. Since $ \left| B_1B \right| \equal{} \left| B_1F\right|$, the point $ B_1$, and similarly the point $ B_2$, have equal powers with respect to circle $ I$ and the "circle" $ B$. (Since for a point outside a circle, the power of point of the point with respect to the circle is equal to the square of the length of the tangent from the point to the circle.) Thus, $ RB_1B_2P$ is the radical axis with respect to incircle $ I$ and the "circle" $ B$, and similarly, $ QC_1C_2P$ is the radical axis with respect to incircle $ I$ and the "circle" $ C$. Therefore, $ P$ is the radical centre with respect to incircle $ I$, and the "circles" $ B$, $ C$. Let the line $ PD$ meet incircle $ I$ again at point $ A''$. The above implies that $ {\left| BP \right|}^2 \equal{} {\left| PD \right| \left| PA'' \right|} \equal{} {\left| CP \right|}^2$. Now, consider the inversion with centre $ P$ and radius of inversion $ \left| BP \right|$. This will carry the point $ D$ to the point $ A''$, and keep $ B$ and $ C$ fixed. Moreover, the above equality implies that the incircle $ I$ is carried to itself by inversion. Since inversion preserves tangency, the image of $ BC$ in the inversion is a circle passing through $ P$, $ B$, $ A''$, $ C$, that is tangent to the circle $ I$ at point $ A''$. However, there exists only one circle passing through $ B$, and $ C$ and is tangent to the incircle at a point on the side of the incircle opposite to $ D$. (Or else the $ A'$ is not uniquely defined.) Thus, $ A'' \equal{} A'$, and our inversion carries $ D$ to $ A'$. This implies that $ A'DP$ are collinear. Combining this with the fact that $ KDP$ are collinear, we get that $ A'KD$ are collinear. Similarly, $ B'KE$ are collinear, and $ C'KF$ are collinear.

	We now apply Steinbart's theorem, which states that If the incircle of a triangle $ ABC$ touches the sides $ BC$, $ CA$, $ AB$ at $ D$, $ E$ and $ F$, and if $ A'$, $ B'$, $ C'$ are three arbitrary points on the incircle such that the lines $ DA'$, $ EB'$, $ FC'$ concur, then the lines $ AA'$, $ BB'$, $ CC'$ concur, too. A proof of this theorem can be found here:

[url=http://www.cip.ifi.lmu.de/~grinberg/SteinbartVarPDF.zip]Variations of the Steinbart Theorem[/url].

As we have shown, the lines $ DA'$, $ EB'$ and $ FC'$ concur at $ K$. Therefore, it follows from this theorem that $ AA'$, $ BB'$ and $ CC'$ are concurrent.

{\bf Q.E.D}

What should I say? My solution used exactly the same idea as Pengshi's one (with the Steinbart theorem) but was a way longer than necessary since I didn't take the time to simplify it properly. Anyway, two remarks on the solution:

[b]1.[/b] The crucial point of the solution, namely showing that the circle through the points B, C and P is tangent to the incircle of triangle ABC, has also been discussed here: http://www.mathlinks.ro/Forum/viewtopic.php?t=16689 .

[b]2.[/b] In order to prove strictly that there exists only one circle passing through the points B and C and tangent to the incircle of triangle ABC, one could argue as follows: An inversion with center B maps every circle through the point B to a line; thus, the image of any circle passing through the points B and C and tangent to the incircle of triangle ABC under this inversion would be a line passing through the image of the point C and tangent to the image of the incircle of triangle ABC. Of course, there are two such lines (as there are two tangents from a point to a circle), but one of them is just the image of the line BC under our inversion, and hence only the other one is the image of an actual circle. Hence, there is only one circle passing through the points B and C and tangent to the incircle of triangle ABC.

By the way, the line through the points A', K, D and P also passes through the A-excenter of triangle ABC and through the midpoint of the altitude of triangle ABC issuing from the vertex A. See http://www.mathlinks.ro/Forum/viewtopic.php?t=14741 , for instance. The point K is the isogonal conjugate of the Mitten point of triangle ABC and it is X(57) in Kimberling's ETC. The point of concurrence of the lines AA', BB' and CC' is X(479).

Anyway, here is a reference for this problem:

Clark Kimberling and Peter Yff, [i]Problem 10678[/i], American Mathematical Monthly 105 (1998) 666.

I remember having seen a trigonometric solution by Peter Woo on the web, but the site seems to be down now.

  Darij

For 1 I also used the "Harazi Substitution" (as Darij called it).
For 2, I used some not-so-nice (but certainly doable) calculations, and then finished with Ceva. (I was overly pedantic with the details.  :blush:  )
For 3, I had no idea :)

I'll see if i can attach my sols here

Actually, I came across the idea of constructing $P$ from "the Gergonne Solution" to the Apollonius problem. http://whistleralley.com/tangents/tangents.htm
Basically, what we have here is a special case of apollonius' problem, where 2 of the "circles" are points. The lines $B_1B_2$, etc are the radical axis of the circles. And $P$ is the radical centre, as in the Gergonne solution.

for problem 2 I think I have a nice solution, but after using Steinbart's theorem (actually I didn't know it was a well known theorem and proved it as a lemma in my solution..).
To show that $DA',EB',FC'$ are concurrent consider the polar transformation with respect to the incircle of $ABC$. It's easy to check that $A'$ maps to the radical axis of the incircle and the circle through $B,C$ and tangent to the incircle at $A'$ (let's call it $C_a$). And since $D$ maps to the radical axis of $C_a$ and the circunscribed circle of $ABC$, then the line $DA'$ maps to the radical center of the inscribed circle, the circunscribed circle and circle $C_a$. In particular, $DA'$ maps to a point on the radical axis of the inscribed and the circunscribed circle of $ABC$. The same with $EB'$ and $FC'$, and therefor by the duality principle (since the 3 points that are the image of $DA',EB',FC'$ under the polar transformation are collinear) we have that the lines $DA',EB',FC'$ are concurrent and that's it.


function
real analysis
real analysis unsolved

1) We know that continuous function is measurable. I dont know is a left continuous function is measurable. and how to show it is or it is not?
2) We know that if a two variable function which is measurable for one variable and continuous for other variable then it is measurable
How about the function which is measurable for one variable and left continuous for other variable? Is this function measurable?

See [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=272429]this[/url] thread of mine, which discusses non-measurable functions.