The three cups problem states that: Strting with three cups with one of them right side up and two of them upside down, the aim is to turn all the cups upside down in six moves, and you must turn exactly two cups over each turn.

How to prove that this is impossible?

[hide]No matter what you do, either one or all of the cups will be right side up, making it impossible to have them all upside down.[/hide]

[hide="To clarify"] We can at any point overturn two right-side-up cups, a right-side-up cup and an upside-down cup, or two upside-down cups.  These operations leave the parity of the number of right-side-up cups invariant, so this number can never be $ 0$ since it begins odd. [/hide]

Oh I see, how can we generalise this problem, so we can have: Strting with n cups with one of them right side up and n-1 of them upside down, the aim is to turn all the cups upside down in k moves, and you must turn exactly m cups over each turn. Such that the problem is still impossible. (what should k and m be?)


geometry
geometric transformation
reflection
geometric sequence

How do you guys explain the equality $ (\frac {1}{4}) \plus{} (\frac {1}{4})^{2} \plus{} (\frac {1}{4})^{3} \plus{} ................. \equal{} \frac {1}{3}$ it seemed me very interesting  when I saw it for the first time.

by Geometric progression we have
$ (\frac{1}{4})\plus{}(\frac{1}{4})^2\plus{}...\plus{}(\frac{1}{4})^n\equal{}\frac{\frac{1}{4}(1\minus{}(\frac{1}{4})^n)}{1\minus{}\frac{1}{4}}$
it is simple when you consider
$ lim((\frac{1}{4})\plus{}(\frac{1}{4})^2\plus{}...\plus{}(\frac{1}{4})^n)$

Elio, please give your posts more descriptive titles.  Names like "interesting" and "question" are totally useless for determining the content of the post.

Or, let the sum in question equal k.

Multiplying both sides by 4, we get 1+k=4k

k=1/3

Not a completely correct argument.

$ (1 \plus{} 2 \plus{} 4 \plus{} \ldots ) \minus{} 2(1 \plus{} 2 \plus{} 4 \plus{} \ldots ) \equal{} 1$, but $ 1 \plus{} 2 \plus{} 4 \plus{} \ldots \neq \minus{}1$. It's better to use the limit of partial sums, because otherwise the issue of convergence can mislead you. This example is silly, but your method might get values of sums where it is very difficult to determine convergence

Not exactly Pre-Olympiad material.  Nevertheless, I like to think of this identity in the following way.  Consider an equilateral triangle with area $ 1$, and divide it up into four congruent equilateral triangles of area $ \frac{1}{4}$.  The middle triangle can further be divided into four congruent equilateral triangles of area $ \frac{1}{4^2}$, and the middle triangle of that triangle can further be divided into four congruent equilateral triangles of area $ \frac{1}{4^3}$, ad infinitum.  The total area of all the triangles created in this process is

$ \frac{3}{4} \plus{} \frac{3}{4^2} \plus{} \frac{3}{4^3} \plus{} ...$

but we know that the area of the original equilateral triangle is just $ 1$.  :)

[quote="Ibn Rochde"][quote="t0rajir0u"]Not exactly Pre-Olympiad material.  Nevertheless, I like to think of this identity in the following way.  Consider an equilateral triangle with area $ 1$, and divide it up into four congruent equilateral triangles of area $ \frac {1}{4}$.  The middle triangle can further be divided into four congruent equilateral triangles of area $ \frac {1}{4^2}$, and the middle triangle of that triangle can further be divided into four congruent equilateral triangles of area $ \frac {1}{4^3}$, ad infinitum.  The total area of all the triangles created in this process is

$ \frac {3}{4} \plus{} \frac {3}{4^2} \plus{} \frac {3}{4^3} \plus{} ...$

but we know that the area of the original equilateral triangle is just $ 1$.  :)[/quote]
i like the idea it reflects the power of your immagination  :)[/quote]
I think that idea might be present elsewhere... in fact, I see the animation right now. :P


function
probability
integration
parameterization
calculus
probability and stats

Suppose we are given a probability distribution function $ P(\xi \leqslant t)\equal{}\int_{a}^{\infty} \sqrt{\frac{2}{\pi t}}e^{\minus{}\frac{x^2}{2t}}dx$. Help me to find the density function.

First of all may be you could chek that $ Lim_{t\rightarrow \plus{}\infty} P(\xi\leq t)\equal{}1$
This is not really obvious from your expression, I think that might have to mulitply with a copnstant (may depending on your parameter $ a$).
You should also check for the vailidity of your expression for example it is not well defined for negative $ t$.

Once you get there, apply derivation under integral sign theorem of your expression $ P(\xi\leq t )$ with respect to $ t$ to get your pdf.


Prove that for all $ a,b,c > 0   ,    abc \geq 1$
$ \frac{1}{1\plus{}a\plus{}b} \plus{} \frac{1}{1\plus{}b\plus{}c} \plus{} \frac{1}{1\plus{}c\plus{}a} \leq 1$

 :?:

[quote="navidj"]Prove that for all $ a,b,c > 0 , abc \geq 1$
$ \frac {1}{1 \plus{} a \plus{} b} \plus{} \frac {1}{1 \plus{} b \plus{} c} \plus{} \frac {1}{1 \plus{} c \plus{} a} \leq 1$

 :?:[/quote]
After expanding,this inequality is equivalent to:
$ 2 \plus{} 2(a \plus{} b \plus{} c) \le (a \plus{} b)(b \plus{} c)(c \plus{} a)$
But $ (a \plus{} b)(b \plus{} c)(c \plus{} a) \equal{} (a \plus{} b \plus{} c)(ab \plus{} bc \plus{} ca) \minus{} abc \ge \frac {8(a \plus{} b \plus{} c)(ab \plus{} bc \plus{} ca)}{9} \ge \frac {8(a \plus{} b \plus{} c)}{3} \ge 2(a \plus{} b \plus{} c) \plus{} 2$
Then,we have Q.E.D :)

nice and easy,
By Cauchy-Schwarz;   $ (1\plus{}a\plus{}b)(c\plus{}1\plus{}1)\geq (\sqrt{a}\plus{}\sqrt{b}\plus{}\sqrt{c})^2$ therfore, $ \frac{1}{a\plus{}b\plus{}1}\leq\frac{c\plus{}2}{(\sqrt{a}\plus{}\sqrt{b}\plus{}\sqrt{c})^2}$ thus, $ \sum \frac{1}{a\plus{}b\plus{}1}\leq \frac{a\plus{}b\plus{}c\plus{}6}{(\sqrt{a}\plus{}\sqrt{b}\plus{}\sqrt{c})^2}$
then it's suffice to prove that, $ \frac{a\plus{}b\plus{}c\plus{}6}{(\sqrt{a}\plus{}\sqrt{b}\plus{}\sqrt{c})^2} \leq 1$
$ \Leftrightarrow (\sqrt{a}\plus{}\sqrt{b}\plus{}\sqrt{c})^2\geq a\plus{}b\plus{}c\plus{}6$
$ \Leftrightarrow 2\sum \sqrt{ab} \geq 6$ wich is AM-GM, ($ 2\sum \sqrt{ab} \geq 6\sqrt[3]{abc}\geq 6$ because $ abc\geq1$ )
equality only if $ a\equal{}b\equal{}c\equal{}1$


$2\cdot sin\left(\frac{7x}{3} \right)=1 \leftrightarrow sin\left(\frac{7x}{3} \right)=\frac{1}{2}$
so we got
$x=\frac{3}{7}\cdot \left(\frac{\pi}{6} + 2k\pi\right),k\in %Error. "varmathbb" is a bad command.
{Z}$
is this right or wrong?

at the answer section of my book i get somethin totally different:
$(-1)^k \cdot \frac{\pi}{14} + \frac {3k\pi}{7},k\in %Error. "varmathbb" is a bad command.
{Z}$

[hide]$2\cdot sin\left(\frac{7x}{3} \right)=1 \Longleftrightarrow sin\left(\frac{7x}{3} \right)=\frac{1}{2}$
And now $\frac{7x}{3}=(-1)^{k}\arcsin{\frac{1}{2}}+k\pi$ or $x=(-1)^{k}\frac{\pi}{14}+\frac{3k\pi}{7}$
[/hide]

[u]Basic Trig equations[/u]

[b]1.[/b] $\sin x=a$, $a \in [-1,1] \Rightarrow x \in{ (-1)^{k} \arcsin a+k\pi|k\in Z}$

[b]2.[/b] $\cos x=a$, $a \in [-1,1] \Rightarrow x \in{ +/- \arccos a+2k\pi|k\in Z }$

[b]3.[/b] $\tan x=a$, $a \in R \Rightarrow x \in{ \arctan a+k\pi|k\in Z }$

[b]4.[/b] $\cot x=a$, $a \in R \Rightarrow x \in{ arccot a+k\pi|k\in Z }$

cot=ctg, tan=tg  ;)


I was wondering, is it possible to make a superconducting wire which has EXACTLY zero resistance?? I mean, it shouldn't be possible right?, since if a have a superconducting wire attached to a voltage source then having zero resisitance would give us an infinite current which we obviously cannot have in real life!

-Swapnil

yes it is possible, in 1942 , karlmecling ornes discover it
but it can only occur in high temperature
now, the problem is how can we find out superconductor which can occur in room temperature using " :rotfl: cooper"

[quote=cuong]but it can only occur in high temperature[/quote]

Err... by "high" you meant low? As far as I know, superconductivity has been achieved at very low temps first.

[quote="cuong"]
but it can only occur in high temperature
[/quote]

Errr... bye "high" you mean low, right? Cause as far as I know, first superconductors were achieved at very low temperature.

[quote="swapnillium"]Wait... What about there being INFINITE current if the wire has zero resistance? Isn't that impossible??[/quote]why would the implication of 0 resistance be infinite current? electrons can't move at an infinite speed.

Because if we have a superconducting wire attached to a voltage source then having zero resisitance would give us an infinite current. That is, $v = i/R \Rightarrow i = v/R$; so then (if $v$ is constant) as $R \rightarrow 0, i \rightarrow \infty$

Ohm's law doesn't account for the effects of relativity, so it only applies for relatively low electron drift speeds. Hence, as that speed approaches a significant fraction of the speed of light, the predictions of Ohm's law are inaccurate. So, a wire of finite thickness cannot carry an infinite current.

to ANDERSON yes low temperature,sory for my mistake.

ohm law can not be apply here.OHM law is found by experiment with normal voltage and current, in this case R-----0,we can't apply OHM law to find out the voltage or the magnitude of the current.

another example is the mechanic mass of photon which velocity is c.We can't find its mass by EInstein equation:$m=\frac{mo}{\sqrt{1-\frac{v^2}{c^2}}}$,the velocity of PHOTON is c so m tends to infinity which is wrong , so we can't apply it here.
the mechanic mass of photon is $\frac{hf}{c^2}$ :D

So what exactly are the limitations of Ohm's law?
BTW, thank you all for answering my questions.  :)

I had asked my father about this question, he is researching it in HCM university of technology,but he didn't answer me :blush: .

btw,i also creat a technology to find the magnitude of current , i will check it.so wait for me ,the main idea is refered from an A level book :ninja:


[quote="sebescu"]prove that:

[tex] (a+b+c) - ( a^2b+ac^2+b^2c)+(ab+bc+ca)-3 \leq \ 0 [/tex]

where abc=1[/quote]

This inequality is equivalent to $a^2b+b^2c+c^2a+3\geq a+b+c+bc+ca+ab$ and was solved in the thread http://www.mathlinks.ro/Forum/viewtopic.php?t=42056 . Note that you need the condition that the numbers a, b, c are positive; else, the inequality is not generally true.

  darij


I searched for the following problem, but I couldn't find it on mathlinks.  I would really like to see a proof of the following using inversive geometry.

Two circles $\Gamma$ and $\Gamma'$ intersect at $A$ and $D$. A line is tangent to $\Gamma$ and $\Gamma'$ at $E$ and $F$, respectively. A line passes through point $D$ and intersects circles $\Gamma$ and $\Gamma'$ at $B$ and $C$, respectively. Show that the circumcircles of $\triangle BDE$ and $\triangle CDF$ intersect again on the line $AD$.

Aren't the circumcircles of $\triangle BDE$ and $\triangle CDF$ just $\Gamma$ and $\Gamma'$ respectively?
Did I misunderstand anything :maybe:


geometry
geometric transformation
reflection
AMC
AIME
AMC 10
AMC 10 B

Okay, I've taken the AMC 12A. I was wondering if it would be possible to take the 10B at a public school (with their permission of course) without paying the registration fee and whatnot. If I'm not mistaken, students can take tests at another school without registering. I was wondering if that would apply in my case.

According to our general principles, you should register as a "Visitor" in order to take the AMC 10 B or AMC 12B at a school which is not the school you  regularly attend.  In order to register as a visitor, you should call the  AMC office at 402-472-2257 and request a visitor registration form.  The
form and accompanying instruction will have directions about which CEEB  number to use.  The fee for registering as a "Visitor" is $32.
If you do not register as a visitor, the following consequences may happen:
1.  The host school you visit will have a CEEB number on the school cover  sheet, which precedes the scoring of the answer forms form that school.  If your answer form in the midst of the host school's answer forms has the  CEEB of your school we may believe that a serious mix-up has occurred
within our office and it can cause us great confusion.  This slows up the  scoring of everyone's answer forms!
2.  If you take the AMC 12 B at a host school which is not your own school  and use the host school's CEEB number, then we believe you are a student  at that host school.  If you score among the top three scores from that
school, then we automatically make you a member of the host school's team  score.  This is not an honest reflection of the school's score or  standing.  In addition, since Sliffe awards are partially based on the  school's team score, the potential exists to select a Sliffe winner on the  basis of a non-representative score.  This is not fair to other teachers.
3.  If you take the AMC 12 B at a host school which is not your own school  and use the host school's CEEB number, then we believe you are a student  at that school.   If you qualify for the AIME on the basis of what you
score on the AMC 12 B, we report you as an AIME qualifier to the host school, not your own school.  We also send an AIME exam to that host  school for you.  That puts the burden on a teacher who does not know you to contact
you to make arrangments for the AIME.  That is not a fair request to make of the hosting teacher, and it runs the risk of you rnot being notified
that you qualify for the AIME if the host teacher either does not have  the time or the will to contact you.
If you register as a Visitor, then the $32 fee is used to extract your  personal answer sheet from the host school's bundle and to process you  separately, and contact you separately eliminating all three of the  problems above.

AMC Director
Steve Dunbar

I won't bother with the 10B then. Thanks for the clarification on that.

I didn't catch all this visitor information on the AMC site or in the materials I received in the mail until AFTER I had already registered a group for the "A" tests in the name of my homeschool math club group, and indicated that my son would take a "B" test in the name of another homeschool group that has been organizing AMC 10/12 tests for several years across town. (My son took the 10B with the other group last year, so that is actually his "previous school" for the 10B, but my group is his "previous school" for the AMC 8, now three years running.) I am sorry that I missed that. I will have to see if I can unsnarl things.


Determine all distinct triangles having one side of length 6,with the other two sides being integers,and the perimeter numerically equal to the area.

Yay for Heron :D

[hide="a start"]perimeter = a+b+c
s = (a+b+c)/2
Area = ¬/(s(s-a)(s-b)(s-c))
a = 6

So we want to find all integers (b,c) such that
6+b+c = ¬/(s(s-6)(s-b)(s-c))
(6+b+c)^2 = s(s-6)(s-b)(s-c)
...
:stink:

Just by testing, I found one: (6,8,10) [/hide]


could anyone give me hints on how to graph this one?

$ y\equal{}|x\minus{}2| \plus{} |x\minus{}4| \plus{} |2x\minus{}6|$

See what happens at $ x\equal{}2$, $ x\equal{}3$, and $ x\equal{}4$. In other words, set each of the expressions within the absolute value signs to zero.

yes, i know, i did that, these are the "vertices" of each of the 3 "sub-graphs". yet, i still dont understand what you are trying to tell me...:(

First, understand what a typical graph of the absolute value function looks like, which is like a "V" shape. Now set intervals at which each of the absolute values changes sign. Let me illustrate my idea here, this should be clear:

I'll begin with a much simpler example and you apply the same technique to your problem.

Suppose we want to graph $ y\equal{}|x|\plus{}|x\minus{}1|$. The first thing you want to make sure is to know the proper definition of absolute value. You can't graph a function without knowing what it is!

To review that definition, [hide="click here"]\[ |x|\equal{}\begin{cases}x&\text{if }x\ge0\\\minus{}x&\text{if }x<0\end{cases}\][/hide]

Take 123456789's hint, we look at the "corners" at $ x\equal{}0$ and $ x\equal{}1$.

So we have a domain to analyze the values of $ y$: (sorry I have to put this in code)

[code]
<------------------+-------------------+------------------>
x                  0                   1[/code]
Set intervals to make your "piecewise" graph:

for $ x<0$, $ y\equal{}(\minus{}x)\plus{}(\minus{}x\plus{}1)\equal{}1\minus{}2x$

for $ 0\le x<1$, $ y\equal{}(x)\plus{}(\minus{}x\plus{}1)\equal{}1$

for $ 1\le x$, $ y\equal{}(x)\plus{}(x\minus{}1)\equal{}2x\minus{}1$.

ohhh..so it becomes a piecewise function? that's incredible...:)thanks

Every absolute value function is really a piecewise function.  I always tell people that's by far the easiest way to deal with absolute values.


Find all pairs of prime numbers (p,q) such that :

    pq divides  $(7^p - 2^p)(7^q - 2^q)$

Suppose that $p,q>7$ (if they are smaller or equal, you just go through all the cases).
Then $7^p-2^p\equiv 7-2 \mod p$ so $p|7^q-2^q$ and $q|7^p-2^p$. Now we have that $p|7^{p-1}-2^{p-1}$ so $p|gcd(7^q-2^q,7^{p-1}-2^{p-1})$ and $gcd(7, 2)=1$ so \[ p|gcd(7^q-2^q,7^{p-1}-2^{p-1})=7^{gcd(q, p-1)} - 2^{gcd(q, p-1)}  \] and like that \[ q|7^{gcd(p, q-1)}-2^{gcd(p, q-1)}.  \]
Now $qcd(p, q-1)$ and $gcd(q, p-1)$ can't be equal $1$, so it has to be $p|q-1$ and $q|p-1$...
edit: so $p\leq q-1 \leq p-2$  which is imposible.

bye

[quote="{x}"][quote] so it has to be $p|q-1$ and $q|p-1$ ... [/quote]
... hence $p \leq q-1$ and $q \leq p-1$. Therefore $q \leq p-1 \leq q-2$, a contradiction. ;)
I don't understand how does $p|q-1$ and $q|p-1$ imply that $p=q$ ?  :?[/quote]

I couldn't agree with you more, I made a mistake because I wrote this maybe little to fast whitout much of thinking...

I will edit it now

[quote] It is obviosly one of them 5. [/quote]

I wonder why is this so obvious?

Let $p\not =5,2,7 q\not =5,2,7$, then $p|(7^q-2^q),q|(7^p-2^p)$. If $q\not |(p-1)$ then exist k: kq=1(mod (p-1)). Therefore $p|(7^q-2^q)|(7^{kq}-2^{kq}=5(mod p)$ give contradition. If $q|(p-1),p|(q-1)$ we have contradition.
If p=2 or 7 give contradition $7|2^q$ or $2|7^q$.

Well, proof in 4 lines isn't so obvious :D

bye


algebra
polynomial
trigonometry
modular arithmetic
algebra unsolved

Polynomial $ P(t)$ is such that for all real $ x$,
\[ P(\sin x) \plus{} P(\cos x) \equal{} 1.
\]
What can be the degree of this polynomial?

(*) $P(\sin x)+P(\cos x)=1$

First $P(-y)=P(\sin (-x))=1-P(\cos (-x))=1-P(\cos x)=P(y)$ for all $y=\sin x\in [-1,1]$ using (*).
Then $P(t)-P(-t)$ has infinitely many roots, and so $P(t)=P(-t)$ is even.
Therefore $P(t)=Q(t^{2})$ for some polynomial $Q$.
Then $1=P(\sin x)+P(\cos x)=Q(\sin^{2}x)+Q(\cos^{2}x)=Q({1\over 2}+y)+Q({1\over 2}-y)$ for all $y=\sin^{2}x-{1\over 2}\in [-{1\over 2},{1\over 2}]$.
So the polynomial $Q({1\over 2}+t)+Q({1\over 2}-t)-1$ has infinitely many roots, and therefore the polynomial
$Q({1\over 2}+t)-{1\over 2}=-(Q({1\over 2}-t)-{1\over 2})$ is odd. So $Q({1\over 2}+t)-{1\over 2}=tR(t^{2})$ for some polynomial $R$.
But now $Q(t)=(t-{1\over 2})R((t-{1\over 2})^{2})+{1\over 2}$ and
$P(t)=Q(t^{2})=(t^{2}-{1\over 2})R((t^{2}-{1\over 2})^{2})+{1\over 2}$.

Conversely every so defined polynomial satisfies (*),
where $\deg P=2+4\deg R$ runs through all natural numbers $\equiv 2 \pmod{4}$ for $R\not \equiv 0$,
and $\deg P=0$ for $R\equiv 0$.


A flat decorator is planning a hanger for clothes. He attaches two identical very strong but elastic metal fibres with a shape of a quarter circle, as in the picture below. He noticed that if he put the same amount of weight on the two hangers, one of them will bend lower than the other one. He couldnt tell why. Lets help him and tell him why one of them bends lower.

No one wants to help the flat decorator? :D  :D
The inside wont be ready in time :D

No help from me, I'm afraid :( Could you post the solution?

ok here it is shortly:
We apply carefully a maximum of $G$ force to the fibres. then the endpoints of the fibre will be $\delta h$ lower, than in the beginning. The work done by is the same as the elastic energy in the little bit bended fibre. Using the analogy with  the elastic energy the energy in the fibre is proportional to the length of a little piece of fibre and the square of the torque at the end of it.
So:
$\frac{\delta h_{a}}{\delta h_{b}}=\frac{\int M(a)^{2}ds}{\int M(b)^{2}ds}= \frac{\int_{0}^{\frac{\pi}{2}}\sin^{2}\phi d\phi}{\int_{0}^{\frac{\pi}{2}}(1-\cos \phi)^{2}d\phi}=\frac{\pi}{3\pi-8}=2,2$
So  the bending in the a.) diagram is greater.


AMC AIME articles percent USA(J)MO USAMO geometry \/closed

We are now taking enrollments for our [url=http://www.artofproblemsolving.com/Classes/AoPS_C_WOOT.php]2009-2010 Worldwide Online Olympiad Training[/url] (WOOT!)

WOOT is a 7-month training program for national high school International Math Olympiad selection tests such as the AIME and USAMO.  WOOT offers classes, articles, problem sets, practice tests, and an outstanding peer group.  This year's schedule can be found [url=http://www.artofproblemsolving.com/Classes/AoPS_C_WOOTSchedule.php]here[/url].  As in past years, generous sponsorship allows us to invite the 2009 MOSP students (those selected to train with the United States IMO team) to participate in WOOT for free.  This year's sponsors are D. E. Shaw group, Jane Street Capital, and Two Sigma Investments, LLC.  We also have received sponsorship from Science House to fund six top students from Central and South America.  So, we expect to again have a truly outstanding group of students in WOOT!

We are offering an early-bird discount on enrollment.  The registration fee is \$695 if you enroll before August 15, 2009, and \$845 thereafter.  WOOT begins in mid-September and runs through mid-April, 2010.  We will host two Math Jams to discuss WOOT in the fall, on August 4 and September 8, both at 7:30 PM ET.

Thanks a lot but I have a little question. Is the classes on Date 1 and Date 2? or Date OR Date 2?
And what is the maximum participants number?

Thanks

No maximum participant number -- if we have way too many people enroll, we'll add another class date.  The "Date 1" and "Date 2" classes are the same -- this is to give students multiple opportunities to fit WOOT into their schedules.

[quote="myyellowducky82"]Math Jams are free, right?[/quote]

yes

[quote="PowerOfPi"]What is the difference between the two math jams?[/quote]

nothing, i think
other than they are at different times

[quote="nikeballa96"]would someone who got a $ 5$ on AIME be ready for this?[/quote]

[quote="WOOT page"]Students who are not capable of consistently scoring 5 or higher on the American Invitational Mathematics Exam should strongly consider waiting until they have more experience before joining WOOT.
[/quote]

i'd say you should try

I took it after getting a 4 on the AIME.

I was ready for about half the material I think, more or less

[quote="PowerOfPi"]What is the difference between the two math jams?[/quote]

Nothing -- there isn't any math in these two math jams; they will mainly be question&answer sessions about WOOT.

To those of you asking about "Should I take this with a 4-6 on the AIME?", the answer depends a lot on two things:

1) What will you have done between the AIME and WOOT?  If you take some AoPS classes, work through some books, or go to some summer programs, then you're probably ready.  If you do nothing, then you may not be ready.

2) Will you have plenty of time during the school year to investigate/ask questions about parts of WOOT you don't understand the first time you see them?

[quote="xpmath"][quote="nikeballa96"]would someone who got a $ 5$ on AIME be ready for this?[/quote]

I know someone who took it as an 8th grader after getting a 5 on AIME in 7th grade...I plan on taking it, and I got a 6 (although this isn't really a good representative of my math skill).[/quote]

Well this person did not do particularly well in woot :P.(trust me, i would know)

dang. so expensive. should've gone to MOP.

[quote="1=2"][quote="abacadaea"]Well this person did not do particularly well in woot :P.(trust me, i would know)[/quote]

HEY! I did decent! :P

If you make AIME and score at least a 3 you should consider trying WOOT. It has some hard problems that really make you think, and it has increased my mathematical maturity/confidence. This is my third year participating (scholarships FTW).[/quote]

I wasnt refering to you... :P

If you can go through it before WOOT, and are ready to do so, by all means, do go through it.  If not, that's OK.  It will be a fine complement to WOOT.

[quote="simo14"]If one does WOOT, would it still be useful to go through acops? Would it be best to go through it before, during, or after?[/quote]

What is "acops" ?

Art and Craft of Problem Solving. It's a book by Paul Zeitz that's about early olympiad level.

I went through part of ACoPS (the first few chapters about general problem solving skills) during part of WOOT (and went through several other math books as well) without a problem. It is a fine complement to WOOT, as rrusczyk said; I only have to add that, depending on how busy your life is, you may have to work very hard to add room to study this or any other book, especially in addition to WOOT. However, it is indeed quite possible, and I found it refreshing (since it was less intensive than working on IMO shortlist problems in the WOOT classroom, yet still had some very useful and applicable ideas).

[quote="qwertythecucumber"]If I get done AoPS Vol. 2 by the time WOOT starts, will WOOT be fit for me? By that time, I also plan to finish up Intermediate Algebra. Before that, I took an Intro to Counting and Probability course, as well as studied Intro to Number Theory and Geometry. so, i want to make sure this is right for me before asking my parents to sign me up for this.[/quote]

If by "getting done" you mean "worked on a lot of the problems and understand the material pretty well", then yes, you should be ready to try WOOT in the fall.  Some of it will still be quite hard for you, probably, but you should have the core knowledge necessary to fight through a lot of the hard parts and ask good questions when you're stuck.

Exactly how difficult does the course get? (in both classes and problems) also how does taking WOOT differ from studying out of a book? :huh:

I think the difficulty question was answered earlier in the thread.

To answer your second question: you get to work with some of the brightest minds in your age group and learn better ways to approach/solve problems from them and the instructors/handouts/lectures. You won't get this feature in any other program other than MOP (as far as I know). The instructors also have been USAMO winners and can give you various tips based on their experience. I highly doubt you would get this in any book. But of course to get all this, you must put time into it and allot time for yourself to work with others in the open classrooms.

[quote="sunehra"]I think the difficulty question was answered earlier in the thread.[/quote]Ita.

[quote]To answer your second question: you get to work with some of the brightest minds in your age group and learn better ways to approach/solve problems from them and the instructors/handouts/lectures. You won't get this feature in any other program other than MOP (as far as I know).[/quote]  Other high level summer programs like the AMSP and AMY have this as well.

[quote]The instructors also have been USAMO winners and can give you various tips based on their experience. I highly doubt you would get this in any book. But of course to get all this, you must put time into it and allot time for yourself to work with others in the open classrooms.[/quote]True, True, True, and QFT.

[quote="rrusczyk"][quote="batteredbutnotdefeated"]If you make USAMO you get to go to WOOT for free? How does that work? Do they send an invitation or something to USAMO qualifiers?[/quote]

No; only the MOP students are invited for free among the USAMO qualifiers.[/quote]

Does this work for every year's MOP, or only this year?

I believe it's every year. Correct me if I am wrong.

Are the woot lessons going to be the same as last year? Are the problem sets all the same?

The lessons and problem sets will be different this year than last.  There will be some overlap in lessons from 3 years ago.


[quote="April"]Let be given a triangle $ABC$. Find the least value of the expression:
\[\frac{\sqrt{1+2\cos^{2}A}}{\sin B}+\frac{\sqrt{1+2\cos^{2}B}}{\sin C}+\frac{\sqrt{1+2\cos^{2}C}}{\sin A}\]
[/quote]
AM-GM
\[LHS \ge \root 6 \of{{{\prod{1+2\cos^{2}A}}\over{\prod{\sin^{2}B}}}}\]
We need prove
\[\root 6 \of{{{\prod{1+2\cos^{2}A}}\over{\prod{\sin^{2}B}\geq3\sqrt 2\]
$Min=3\sqrt 2$

[quote="kcbu"][quote="April"]Let be given a triangle $ABC$. Find the least value of the expression:
\[\frac{\sqrt{1+2\cos^{2}A}}{\sin B}+\frac{\sqrt{1+2\cos^{2}B}}{\sin C}+\frac{\sqrt{1+2\cos^{2}C}}{\sin A}\]
[/quote]
AM-GM
\[LHS \ge \root 6 \of{{{\prod{1+2\cos^{2}A}}\over{\prod{\sin^{2}B}}}}\]
We need prove
\[\root 6 \of{{{\prod{1+2\cos^{2}A}}\over{\prod{\sin^{2}B}}}}\geq3\sqrt 2 \]
$\min=3\sqrt 2$[/quote]
Could you show me the complete solution?
Thanks  :lol:

We use some facts as following to infer the rezult:
$\sin A.\sin B.\sin C\leq\frac{3\sqrt{3}}{8}$
$(1+\cos^{2}A)(1+\cos^{2}B)(1+\cos^{2}C)\geq\frac{125}{64}$

we have a similar rezult relating the problem: Given a triangle $ABC$ then
$\frac{\sqrt{1+8\cos^{2}A}}{\sin B}+\frac{\sqrt{1+8\cos^{2}B}}{\sin C}+\frac{\sqrt{1+8\cos^{2}C}}{\sin A}\geq 6$

Okay, the general problem is:
$\frac{\sqrt{1+k\cos^{2}A}}{\sin B}+\frac{\sqrt{1+k\cos^{2}B}}{\sin C}+\frac{\sqrt{1+k\cos^{2}C}}{\sin A}\geq 3\sqrt{\frac{k+4}{3}}$ where $k$ is a positive integer number.

[quote="April"]Please post the complete solution  :)[/quote]
Solution:
$A=\sqrt{\frac{(2+1)(1+2\cos^{2}A)}{\sqrt{3}\sin B}}+\sqrt{\frac{(2+1)(1+2cos^{2}B)}{\sqrt{3}\sin C}}+\sqrt{\frac{(2+1)(1+2\cos^{2}C)}{\sqrt{3}\sin A}}$
$\geq\frac{\sqrt{2}+\sqrt{2}\cos A}{\sqrt{3}\sin B}+\frac{\sqrt{2}+\sqrt{2}\cos B}{\sqrt{3}\sin C}+\frac{\sqrt{2}+\sqrt{2}\cos C}{\sqrt{3}\sin A}$
$=\frac{\sqrt{2}}{\sqrt{3}}\left(\frac{1}{\sin A}+\frac{1}{\sin B}+\frac{1}{\sin C}+\frac{\cos A}{\sin B}+\frac{\cos B}{\sin C}+\frac{\cos C}{\sin A}\right)$
$=\frac{\sqrt{2}}{\sqrt{3}}\left(\frac{1}{\sin A}+\frac{1}{\sin B}+\frac{1}{\sin C}+\frac{2\cos^{2}\frac{A}{2}-1}{\sin B}+\frac{2\cos^{2}\frac{B}{2}-1}{\sin C}+\frac{2\cos^{2}\frac{C}{2}}{\sin A}\right)$
$=\frac{\sqrt{2}}{\sqrt{3}}\left(\frac{\cos^{2}\frac{A}{2}}{\sin\frac{B}{2}\cdot\cos\frac{B}{2}}+\frac{\cos^{2}\frac{B}{2}}{\sin\frac{C}{2}\cdot\cos\frac{C}{2}}+\frac{\cos^{2}\frac{C}{2}}{\sin\frac{A}{2}\cdot\cos\frac{A}{2}}\right)$
$\geq\frac{\sqrt{2}}{\sqrt{3}}.3\sqrt[3]{\cot\frac{A}{2}\cdot\cot\frac{B}{2}\cdot\cot\frac{C}{2}}\geq\frac{\sqrt{2}}{\sqrt{3}}\cdot 3\cdot\sqrt{3}=3\sqrt{2}$

Done :roll:

Yes, it's my opinion. Sory for my typing mistake

Nice proof, do you have any ideas for the general case?

NOTE: please keep your final step left unproven because that simple inequality is on the current application test for SIMUW

[quote="me@home"]
NOTE: please keep your final step left unproven because that simple inequality is on the current application test for SIMUW[/quote]

What's is SIMUW?

Summer Math Institute at the University of Washington (in washington state)


analytic geometry
calculus
geometry
integration
calculus computations

Hey every1!!

These are some questions from multivariable calculus - polar coordinates. I've tried them out but I guess I need help.

[b]1) Find the points of intersection of the curves with the the given polar equations: r = 1 + cosθ, r = 1 - sinθ [/b]

1 + cosθ = 1 - cosθ
(cosθ + sinθ)^2 = 0
cos^2θ + 2cosθsinθ + sin^2θ = 0
1 + 2cosθsinθ = 0
sin2θ = -1
?????

[b]2)Find the area bounded by the curve: a) r = 2 - 2sinθ
b) r = 3 + 2sinθ[/b]
a) r = 2 - 2sinθ
    2 - 2sinθ = 0
    1 - sinθ = 0
    sinθ = 1
    θ = π/2

A = (integral from 0 to π/2) [1/2f(θ)^2 dθ]
   = (integral from 0 to π/2) [1/2 (2 - 2sinθ)^2 dθ]
   = (integral from 0 to π/2) [1/2 (4 + 4sin^2θ - 4sinθ) dθ]
   = (integral from 0 to π/2) [2θ + 2cosθ dθ]
????

b) r = 3 + 2sinθ
    3 + 2sinθ = 0
    sinθ = -3/2
????

Thanks alot for your time and help everyone! uhhh sorry but im not sure how to put in eqts nd stuff. :( hope u still understand tho

eagle

i think you should take a look in your results and analyse then before start to use some tricks in them, like the first problem. you got:
$cos(x)+sin(x)=0$ it´s quite easy to realize that the values of x which satisfies this equality are 3pi/4 and 7pi/4.No extra algebra is necessary.  About the secod one i am not so sure, polar cordinates it´s not my best... but i think using the general formula for finding areas is enough:

$\int_{0}^{2\pi}(2-2sin(\theta))^{2}.d\theta$ so :
$\int_{0}^{2\pi}4.d\theta+\int_{0}^{2\pi}4sin^{2}(\theta).d\theta-\int_{0}^{2\pi}8sin(\theta).d\theta$ and so on...
we know that $\int_{0}^{2\pi}4sin^{2}(\theta).d\theta =\int_{0}^{2\pi}(4/2-4cos(\theta)/2 *d\theta =4\pi$
we also know that $\int_{0}^{2\pi}8sin(\theta).d\theta =0$ and $\int_{0}^{2\pi}4.d\theta =8\pi$ so the area is $12\pi$


calculus
integration
calculus computations

$ \int\limits_{0}^{1} \frac {4\sqrt {1 \minus{} x} \minus{} \sqrt {3x \plus{} 1}}{(3x \plus{} 1)^2\left(4\sqrt {1 \minus{} x} \plus{}\sqrt {3x \plus{} 1} \right)} dx$

Sorry., i edited !  :blush:

[quote="Hong Quy"]$ \int\limits_{0}^{1} \frac {4\sqrt {1 \minus{} x} \minus{} \sqrt {3x \plus{} 1}}{(3x \plus{} 1)^2\left(4\sqrt {1 \minus{} x} \plus{} \sqrt {3x \plus{} 1} \right)} dx$

Sorry., i edited !  :blush:[/quote]
Ans= $ \frac{log5}{16}$

[quote="ith_power"]
Ans= $ \frac {log5}{16}$[/quote]

how did you get it? :huh:

Let $ \sqrt{\frac{3x\plus{}1}{1\minus{}x}} \equal{}t$
 my friend ith_power   !  a  how did you solve this problem?


In the sequence 2001, 2002, 2003, ..., each term after the third is found by subtracting the previous term from the sum of the two terms that precede that term. For example, the fourth term is 2001 + 2002 - 2003 = 2000. What is the 2004th term in this sequence?

Please Post Hints Only

[hide="Hint 1"]Try to find an expression for $ n_i$ in terms of $ n_1,n_2$ and $ n_3$[/hide]

[hide="Hint 2"]My expression for $ n_i$ is different depending on whether $ i$ is odd or even[/hide]


I have a question about the eligibility for AMC 10. Next year, I will be in grade 10, but I am going to take gr.11 course mathematics, so am I still eligible to write the AMC 10 (its not clear from the website)?

Thank you for your help.

[quote="klebian"]AMC 10 and 12 are dependent on solely grade level.
Thus, regardless of what course you are taking, if you are 10th or below (which you are), you will be eligible to take the AMC 10.
[/quote]
While grade-level (and maximum age) are the only [url=http://www.unl.edu/amc/b-registration/b1-archive/2007-2008/2008-AMC1012Bro.pdf]restrictions[/url] the AMC places on exam registrants, some schools may place additional restrictions on who can take the contests, which contest may be taken, costs paid by the student, and whether one can take the contest on the A date, B date, or both.

A contest manager (typically a math teacher) will be placing orders for a specific number of 10A and 12A contests at most schools in early December (cheap A-date registration deadline:  16 Dec 2007.)  Ideally, the contest manager will have a pretty good idea about who will be taking each contest so that enough exams are ordered.  Make sure that your contest manager knows that you are interested in taking the AMC contest(s) and whether you are available on the A date (12 Feb 2008) or B date (27 Feb 2008).

A few schools order AMC 10 & AMC 12 contests for both the A date and the B date but this is more expensive than ordering for just one date.  So most schools order for just one date. It's important to make your contest manager aware of possible conflicts in early December.  If your school orders contests for both dates, you could take the AMC 10 on one date and the AMC 12 on the other.  Alternatively, you could also take the AMC 10 on both dates.

Some schools restrict enrollment for the AMC 12 to juniors and seniors - all others take the AMC 10.  If you want to take the AMC 12 prior to your junior year at such a school, make sure you convince the contest manager at your school that you are capable - well before the contest ordering deadline (i.e. early fall.)

Unfortunately, most schools do not participate in the AMC contests.  If your school does not participate, you can speak with a math teacher (two or three if necessary) about becoming the school contest manager.  You'll need to find a way to pay for the contests.  Assuming the school won't foot the bill, students who register will need to split the costs.  For early [url=http://www.unl.edu/amc/b-registration/b1-archive/2007-2008/08-AMC1012ARegisForms.pdf]A date registration[/url] you can get ten AMC 10 contest booklets for $\$$14 plus $\$$40 registration ($\$$54 total which could be split by up to 10 students).  You can reduce the per-student costs to a few dollars by getting more students to participate in either AMC 10 or AMC 12 on that date.

Other possible obstacles to AMC contest participation:  1.  a room and a proctor that will be available for ~90 minutes on the contest date(s).  2.  excused class absences for participants, assuming the contest is given during class hours.  3.  conflicts with other activities if the contest is administered after school hours.

If you can find enough interested students willing to pay for the contest, it's usually not very difficult to find a math teacher willing to administer it.  Supporting a math team or extra-curricular math activities looks good on any teacher's resume, especially newer instructors.


geometry
trigonometry
analytic geometry
incenter
inradius
projective geometry
power of a point

The incircle $ k$ of a non-isosceles $ \triangle ABC$ touches the sides $ AB,BC,CA$ at $ C_{1},A_{1},B_{1}$ , respectively. If $ M$ and $ N$ are midpoints of $ B_{1}C_{1}$ and $ A_{1}C_{1}$ , respectively and $ MN \cap BC\equal{}P$ prove that $ C_{1}P\parallel{}AA_{1}$.

Let $ MN\cap BA\equiv M_a$, $ A_1B_1\cap AB\equiv D$. Since $ M,N$ respectively are the midpoints of $ C_1B_1,C_1A_1$. But $ MN\parallel{}A_1B_1$. Hence $ M_a$ will be midpoint of $ C_1D$. Now it is so obvious that $ PM_a\parallel{}A_1D\Longrightarrow \frac {\overline {PB}}{\overline {PA_1}} \equal{} \frac {\overline {M_aB}}{\overline {M_aD}}$. Note that $ (DC_1BA) \equal{} \minus{} 1$, $ M_a$ is midpoint of $ DC_1\Longrightarrow M_aD^2 \equal{} \overline {M_aB}\cdot \overline {M_aA}$. Therefore

$ \frac {\overline {M_aB}}{\overline {M_aD}} \equal{} \frac {\overline {M_aD}}{\overline {M_aA}} \equal{} \frac {\overline {M_aB} \minus{} \overline{M_aD}}{\overline {M_aD} \minus{} \overline {M_aA}} \equal{} \minus{} \frac {\overline {DB}}{\overline {DA}} \equal{} \frac {\overline {C_1B}}{\overline {C_1A}}\Longrightarrow \frac {\overline {PB}}{\overline {PA_1}} \equal{} \frac {\overline {C_1B}}{\overline {C_1A}}$, which implies $ PC_1\parallel{}AA_1$

Our proof is completed then.

[color=darkblue]We have

$ \small{d(C,MN)=d(C,A_1B_1)+d(A_1B_1,MN)=}$

${CA_1 \cos \frac{C}{2}+\dfrac{1}{2}d(C_1,A_1B_1)=(p-c)\cdot  \cos \frac{C}{2}+r \cos \frac{A}{2} \cos \frac{B}{2} }$

$ \small{A_1D=CD-A_1C=\dfrac{d(C,MN)}{\cos \frac{C}{2}}-(p-c)=r \dfrac{\cos \frac{A}{2} \cos \frac{B}{2}}{\cos \frac{C}{2}}=}$

${\dfrac{\sqrt{p(p-a)(p-b)(p-c)} \cdot \sqrt{\frac{p(p-a)}{bc}}  \cdot \sqrt{\frac{p(p-b)}{ac}} }{p\sqrt{\frac{p(p-c)}{ab}} }}=\dfrac{(p-a)(p-b)}{c}$

We need to prove

$ \dfrac{AC_1}{AB}=\dfrac{A_1D}{A_1B} \Longleftrightarrow \dfrac{p-a}{c}=\dfrac{\dfrac{(p-a)(p-b)}{c}}{p-b}$,

clearly true.[/color]

We'll use barycentric coordinates with respect to $\triangle ABC.$

$ I_c  (a: b: \minus{} c) \ , \  A_1 (0: p \minus{} c: p \minus{} b)$

Line $B_1C_1$ meets $ BC$ at $ X_a  (0: p \minus{} c: b \minus{} p)$

$ I_cA_1 \equiv (c(p \minus{} c) \plus{} b(p \minus{} b))x \minus{} a(p \minus{} b)y \minus{} a(p \minus{} c)z \equal{} 0$

$ Q \equiv AB \cap I_cA_1 \equiv  (a(p \minus{} b): c(p \minus{} c) \plus{} b(p \minus{} b): 0)$

The incenter $ I \ (a: b: c)$ clearly satisfies the equation of the line $I_cA_1$

$ X_aQ \equiv (p \minus{} b)(c(p \minus{} c) \plus{} b(p \minus{} b))x \minus{} a(p \minus{} b)^2y \minus{} a(p \minus{} c)(p \minus{} b)z \equal{} 0$

$ \Longrightarrow Q,I, X_a$ are collinear.

$ X_a, I_c$  and $ P$ are the poles of  $ AA,MN$ and $ I_cA_1$ WRT $ (I)$ $\Longrightarrow$  $ Q \equiv {} AB \cap I_cA_1$ is the pole of  $ PC_1$ WRT $ (I).$ Since the line $ X_aQ$ goes through $ I$ then the polars of $ X_a, Q$ meet at infinite  $ \Longrightarrow$ $ PC_1 \parallel AA_1.$

[quote="babylon"]The incircle $ k$ of a non-isosceles $ \triangle ABC$ touches the sides $ AB,BC,CA$ at $ C_{1},A_{1},B_{1}$ , respectively. If $ M$ and $ N$ are midpoints of $ B_{1}C_{1}$ and $ A_{1}C_{1}$ , respectively and $ MN \cap BC = P$ prove that $ C_{1}P\parallel{}AA_{1}$.[/quote]
My idea is to slog with trigonometry! :)
Here it is enough to prove that, $ \frac {AB}{AC_1}\frac {BA_1}{PA_1} \iff \frac {c}{s - a} = \frac {s - b}{PA_1}$
Now we calculate $ PA_1$. Using sine law in $ \triangle PNA_1$ we get, $ \frac {PA_1}{\cos \frac A2} = \frac {\frac {C_1A_1}{2}}{\cos \frac C2}$
Also, using sine law in $ \triangle BA_1C_1$ we get, $ \frac {C_1A_1}{\sin B} = \frac {s - b}{\cos \frac B2}\iff C_1A_1 = 2(s - b)\sin \frac B2$
Finally, $ PA_1 = \frac {(s - b) \cos \frac A2 \sin \frac B2}{\cos \frac C2}$
Now setting the values for half angles we get,
\[{ \frac {s - b}{PA_1} = \frac {\cos \frac C2}{\cos \frac A2 \sin \frac B2} = \frac {\sqrt {\frac {s(s - c)}{ab}}}{\sqrt {\frac {s(s - a)}{bc}} \sqrt {\frac {(s - a)(s - c)}{ac}}}} = \frac {c}{s - a}
\]
As desired.

EDIT: Fixed typo.

Dear Mathlinkers,
think to draw the parallel to BC through A...
Sincerely
Jean-Louis

Let $ AA_1\cap (I)\equal{}\{R\}, Q$ be the midpoint of $ RA_1$.
We have $ \angle NA_1P\equal{}\angle C_1RQ$
But $ PN//A_1B_1 \Rightarrow \angle NPA_1\equal{}\angle B_1A_1C\equal{}\angle A_1C_1B_1$
Because quadrilateral $ A_1C_1RB_1$ is harmonic, this result is well-known: $ \angle A_1C_1B_1\equal{}\angle RC_1Q$
Therefore, $ \Delta PA_1N\sim \Delta C_1RQ\Rightarrow \Delta C_1PA_1$~$ \Delta A_1C_1R$
$ \Rightarrow \angle PC_1A_1\equal{}\angle C_1A_1R \Rightarrow$ QED

[quote="No Reason"]The sketch of my proof (sorry because I don't have many time left)
Let $ C_1P$ meet $ A_1B_1$ at $ R$.Using harmonic division,it is equivalent to prove that $ (A_1R,A_1P,A_1C,A_1A)$ is harmonic,which is true since $ AA_1,BB_1,CC_1$ are concurrent.[/quote]
Sorry for asking but $ A_1P\equiv A_1C$, isn't it?

It's an typo,it must be $ A_1C_1$ not $ A_1C$  :P

[quote="jayme"]Dear Mathlinkers,
let L be the meet point of AA1 and MN.
For beginning synthetically this nice problem, we have to prove that C1L is parallel to BC and we are done.
Sincerely
Jean-Louis[/quote]

Nice idea Jean-Louis! Let $ \{T\} \equal{} AM\cap A_1B_1$, then $ AT\perp BT$. Therefore
\[ \frac {AC_1}{BC_1} \equal{} \frac {AM}{MT} \equal{} \frac {AL}{LA_1},
\]
which proves that $ C_1L\parallel{}BC$ and the conclusion follows.

Dear Mathlinkers,
a purely synthetic proof:
1. let U, V the meetpoints of the parallel to BC through A with A1B1, A1C1
and L, X the meetpoints of the parallel to BC through C1 with AA1, A1B1
2. According to Boutin's theorem,	A is the midpoint of UV ; it follows that L is the midpoint of  C1X
(see for example,   http://perso.orange.fr/jl.ayme   vol. 1 A propos du théorème de Boutin)
3. According to the Thales's theorem (the line joining two midpoints in a triangle), L, M, N are collinear.
and we are done.
Sincerely
Jean-Louis

Let $ r$ be the inradius of $ \triangle ABC$.
Note that
$ \frac {BP}{PA_1} \equal{} \frac {[BNP]}{[PNA_1]} \equal{} \frac {BN \cdot NP \cdot sin BNP}{NP \cdot NA_1 \cdot sin PNA_1}$. But $ \frac {BN}{NA_1} \equal{} \frac {BA_1}{r}$ and $ \angle BNP \equal{} \angle MNI$, and $ \angle PNA_1 \equal{} 90 \minus{} \angle MNI$. So
$ \frac {BP}{PA_1} \equal{} \frac {BA_1}{r} \cdot \frac {sin INM}{cosINM} \equal{} \frac {BA_1}{r} \cdot tan INM \equal{} \frac {BA_1}{r} \cdot tan C_1AI* \equal{} \frac {BA_1}{r} \cdot \frac {r}{C_1A} \equal{} \frac {BA_1}{C_1A} \equal{} \frac {BC_1}{C_1A}$
Thus, $ \frac {BP}{PA_1} \equal{} \frac {BC_1}{C_1A}$, so $ C_1P \parallel AA_1$.

*This is true because $ \triangle IC_1M \sim \triangle IC_1A$, so $ IM \cdot IA \equal{} C_1I^2 \equal{} IN \cdot IB$, so $ AMNB$ is cyclic by power of a point, so $ \angle BAM \plus{} \angle MNB \equal{} 180$, so $ \angle C_1AM \equal{} \angle MNI$.

[quote="livetolove212"]Let $ AA_1\cap (I) \equal{} \{R\}, Q$ be the midpoint of $ RA_1$.
We have $ \angle NA_1P \equal{} \angle C_1RQ$
But $ PN//A_1B_1 \Rightarrow \angle NPA_1 \equal{} \angle B_1A_1C \equal{} \angle A_1C_1B_1$
Because quadrilateral $ A_1C_1RB_1$ is harmonic, this result is well-known: $ \angle A_1C_1B_1 \equal{} \angle RC_1Q$
Therefore, $ \Delta PA_1N\sim \Delta C_1RQ\Rightarrow \Delta C_1PA_1$~$ \Delta A_1C_1R$
$ \Rightarrow \angle PC_1A_1 \equal{} \angle C_1A_1R \Rightarrow$ QED[/quote]

Q: What does "Harmonic Quadrilateral" mean?


For what values of $ k$ does $ (k\plus{}1)\cdot9^{x}\minus{}4k\cdot3^{x}\plus{}k\plus{}1\equal{}0$ have 2 solutions for $ x$?

$ (k\plus{}1)\cdot9^{x}\minus{}4k\cdot3^{x}\plus{}k\plus{}1\equal{}0$...
Um...I changed $ 9^{x}$ to $ 3^{2x}$ to $ 9\cdot3^{x}$.
I distributed the 9, and ended up with $ (9k\plus{}9)\cdot3^{x}\minus{}4k\cdot3^{x}\plus{}k\plus{}1\equal{}0$.
Subtracting like terms gave me $ (5k\plus{}9)\cdot3^{x}\equal{}\minus{}k\minus{}1$,
leaving me with $ 3^{x}\equal{}\frac{\minus{}k\minus{}1}{5k\plus{}9}$. What now? I think I went about this the wrong way.

[hide]Let $ 3^{x}\equal{}y$.  Thus, the equation becomes:

$ (k\plus{}1)y^{2}\minus{}4ky\plus{}k\plus{}1\equal{}0$

For there to be 2 roots of this equation, the discriminant must be positive, so we have:

$ (4k)^{2}\minus{}4(k\plus{}1)(k\plus{}1)>0$

$ 16k^{2}\minus{}4k^{2}\minus{}8k\minus{}4>0$

$ 3k^{2}\minus{}2k\minus{}1>0$

$ (3k\plus{}1)(k\minus{}1)>0$

$ k<\minus{}\frac{1}3$ or $ k>1$[/hide]

b-flat, that's a great start, but $ k$ cannot be $ \minus{}1$ because the equation becomes linear and therefore only has 1 solution. Also, you need to show that $ y$ is positive because it equals $ 3^{x}$.

[quote="Icy"]$ (k\plus{}1)\cdot9^{x}\minus{}4k\cdot3^{x}\plus{}k\plus{}1 \equal{} 0$...
Um...I changed $ 9^{x}$ to $ 3^{2x}$ to $ 9\cdot3^{x}$.
I distributed the 9, and ended up with $ (9k\plus{}9)\cdot3^{x}\minus{}4k\cdot3^{x}\plus{}k\plus{}1 \equal{} 0$.
Subtracting like terms gave me $ (5k\plus{}9)\cdot3^{x}\equal{}\minus{}k\minus{}1$,
leaving me with $ 3^{x}\equal{}\frac{\minus{}k\minus{}1}{5k\plus{}9}$. What now? I think I went about this the wrong way.[/quote]

I think your mistake is here:

9^x = 3^(2x) = [b]9*3^x[/b]

It should be: 9^x = 3^(2x) = (3^x)^2, then substitute 3^x with y.

I don't think it was a mathematical error, I just used the wrong approach.

It is a mathematical error.  $ 3^{2x}\neq 9\cdot 3^{x}\equal{} 3^{x\plus{}2}$.


There is a triangle ABC with lengths 4,7,9. For a point inside the triangle, X, Find the value of AX^2+BX^2+CX^2 such that it is minimum.

(AX,BX,CX being the line segments)

Just as how a rectangle's minimum area is when it is a square, I think the minimum here is when x is the circumradius.  That would make the answer we need $3d^2$ where $d$ is the circumradius, or distance from x to any vertex.  There is a fun formula to find the circumradius of a circle, which is
$\frac{abc}{4\sqrt{s(a+b-s)(b+c-s)(c+a-s)}}$ where $s$ is the semiperimeter.  So we want
$\frac{3a^2b^2c^2}{16s(a+b-s)(b+c-s)(c+a-s)}$
Plugging in values, our answer is $\frac{1323}{20}$

sorry, but since i got this problem from TJHSST Inequality lesson, is there a way to use Cauchy-Schwarz, AM-GM chain, or any other inequality to solve this??? Maybe Mildorf can help, since he wrote this.

But the triangle is obtuse...which means that the circumradius lies outside the circle, and so it can't be X.
Yet I have no idead how to solve this...
If you put the point on the side with length 9 (let's say it's BC) and AX is an altitude, then the sum is 505/9...


Angle bisectors of angles A,B,C of triangle ABC meet its circumcircle in K,L,M respectively. Choose on AB a point R. For points P,Q holds the following: RP parallel to AK, BP perpendicular to BL, RQ parallel to BL and AQ perpendicular to AK. Prove that KP,LQ, MR are concurrent.

I am sure it was posted here some time ago, but I can't find it...

Yes, it was...

http://www.mathlinks.ro/Forum/viewtopic.php?p=118910

  Darij

That's exactly what I was looking for! Thanks :lol:


Prove that in any triangle $ ABC$ exists the strict inequality $ \cos A + 2(\cos B + \cos C) < 3\ .$

[b]Remark.[/b] Obtain "equality" for $ \{\begin{array}{c}
B=C\searrow 0\\\
A\nearrow\pi\end{array}\ .$

Can we use casework?
Rephrase it as
$ f\equal{} 2.(cosA\plus{}cosB\plus{}cosC) \minus{} cosA$
For A acute
Clearly by Jensen's$ (cosA\plus{}cosB\plus{}cosC)<\equal{}3/2$
Clearly $ f<2.3/2 \equal{}3$ (As cosA>0)
For A=90
TST $ 2.(cosB\plus{}cosC)<3$
$ 2.sqrt(2).cos(B\plus{}\pi/4)<3$
Which is true.
[b] I AM STUCK IN THE 3RD (AND MOST EASIEST CASE?) CAN SOMEONE HELP? [/b]

[quote="madness"] [color=darkred]I AM STUCK IN THE 3RD ( AND [b]MOST EASIEST CASE[/b] ? ) CAN SOMEONE HELP ?[/color] [/quote]
[color=darkblue]The third case is [b]most difficultly[/b] ! See the my remark from topic.[/color]

[hide]
If either $ B$ or $ C$ is obtuse, the inequality is obvious. Otherwise, use Jensen to get
\[ \cos B\plus{}\cos C\leq 2\cos \frac{B\plus{}C}{2}\equal{}2\sin \frac{A}{2}\]
Let $ x\equal{}\sin \frac{A}{2}$. Then
\[ 1\minus{}2x^2\plus{}4x\equal{}3\minus{}2(x\minus{}1)^2<3\]
since $ 0<\frac{A}{2}<\frac{\pi}{2}$ implies $ x\neq 1$.
[/hide]

"If either  or  is obtuse, the inequality is obvious."
How is it so? Can you please provide a proof?
 :)

If $ B$ obtuse, then $ \cos A,\cos C\leq 1$ and $ \cos B<0$.

[hide="For Madness & Co."]
[quote="Virgil Nicula"] [color=darkred]$ \triangle\ ABC$ $ \implies$ $ \cos A + 2(\cos B + \cos C) < 3$ with "equality" iff $ \{\begin{array}{c} B = C\searrow 0 \\
\ A\nearrow\pi\end{array}$[/color] [/quote]
[color=darkblue][b][u]Method I.[/u][/b] Prove easily that $ \cos A = - 2\cos B\cos C + \cos (B - C)\ .$ Therefore,

$ \cos A + 2(\cos B + \cos C) = - 2\cos B\cos C + \cos (B - C) + 2(\cos B + \cos C) =$

$ 3 - \underbrace {2(1 - \cos B)(1 - \cos C)}_{\ge 0} - \underbrace {[1 - \cos (B - C)]}_{\ge 0}\le 3\ .$

We'll have equality iff $ B - C = 0$ and $ B = 0$ or $ C = 0$, i.e. $ B = C\searrow 0$ and $ A\nearrow \pi\ .$

[b][u]Method II.[/u][/b] $ \cos A + 2(\cos B + \cos C) =$ $ 1 - 2\sin^2\frac A2 + 4\sin\frac A2\cos\frac {B - C}{2} =$

$ 1 - 2(\sin\frac A2 - \cos\frac {B - C}{2})^2 + 2(1 - \sin^2\frac {B - C}{2}) =$

$ 3 - \underbrace {2[(\sin\frac A2 - \cos\frac {B - C}{2})^2 + \sin^2\frac {B - C}{2}]}_{\ge 0}\le 3\ .$

We'll have equality iff $ B = C$ and $ \sin\frac A2 = 1$ , i.e. $ A\nearrow\pi$ and $ B = C\searrow 0\ .$

[b][u]Remark.[/u][/b] $ \{\begin{array}{c} (1 - \cos x)(1 - \cos y) = (\cos\frac {x + y}{2} - \cos\frac {x - y}{2})^2 \\
 \\
\cos^2\frac {x + y}{2} + \cos^2\frac {x - y}{2} = 1 + \cos x\cos y\end{array}$

[b][u]Method III.[/u][/b] Distinguish two cases : $ A\le 90^{\circ}$ or $ A>90^{\circ}\ .$ Therefore :

$ 1\blacktriangleright$ $ A\le 90^{\circ}$ , i.e. $ \cos A\ge 0$ . I'll use the well-known inequality $ \sum\cos A\le\frac 32$ .

Thus, $ \cos A+2(\cos B+\cos C)=2\sum\cos A-\cos A\le 3-\cos A\le 3\ .$

$ 2\blacktriangleright$ $ A>90^{\circ}$ , i.e. $ \cos A<0$ . Thus, $ \{B,C\}\subset (0,90^{\circ})$ and $ 0<\sin\frac A2< 1$ $ \implies$

$ \cos A+2(\cos B+\cos C)=$ $ 1-2\sin^2\frac A2+4\sin\frac A2\cos\frac {B-C}{2}\le$

$ 1-2\sin^2\frac A2+4\sin\frac A2=$ $ 3-2(1-\sin\frac A2)^2\le 3\ .$[/color][/hide]


what is the standard way of labeling a cube (two squares, ABCD and EFGH)?

Which is what I was wondering also...probably like A corresponds to E, B corresponds to F, C corresponds to G, D corresponds to H? Maybe? (corresponds is not the best word choice, but I think you can figure out what I am saying...)

[quote="Chinaboy"]A cube (ABCDEFGH) has side length of 6. What is the distance between AC and DF?[/quote]
Is that the distance between a face diagonal and a space diagonal that does not intersect it?

I'm pretty sure its the diagonal of the cube; otherwise, if its a diagonal of one of the faces, why would the problem include a cube and not just a square?

It could also be a face diagonal and a side. 2 skew lines? (If the top face ABCD and bottom EFGH are labeled in opposite directions, so A-E D-F C-G B-H correspond.)

If it's a face dia + space dia, I think [hide]we can draw the common perpendicular. That would be a vertical line through the center. Call it MN (M on AC, N on DF).

Then draw AN. We know AN = DN and DN = 3 :rt3: . AM = 3 :rt2: . Using Pythagoras we get

(AM) :^2: + (MN) :^2: = (AN) :^2: .

So MN = 3? Not sure if this is right.[/hide]

What I got last night, but I did it really quicky in my head....

Sorry for the confusion.

E is under A
F is under B
G is under C
H is under D

the two are indeed skew lines.

One is the space diagonal, one's a face diagonal.


induction
quadratics
real analysis
real analysis solved

Let two real numbers $p_1>0,q_1<0$. The equation $x^2+p_1x+q_1=0 $ have two real roots $p_2>0,q_2<0$.....The equation $ x ^2 +p_nx+q_n=0$ have two real roots $ p_{n+1}>0,q_{n+1}<0.....$.Prove that two sequences $\{p_n\},\{q_n\}$ have finite limit at $+\infty$ and find theirs limit

Ok, I think I got it even the following is neither very elegant nor short.
First I think that $q_1 < 0$ otherwise you wouldn't have $p_2 > 0$.
Moreover, wed may note that by an easy induction, from $q_1 < 0$ that $q_n <
0$ for all $n$ (that is 0 is never a solution of the quadratic).

Solving the quadratic, it is easy to get :
$p_{n+1}q_{n+1} = q_n$ (1) and $p_{n+1}+q_{n+1} = -p_n$ (2)
that is :
$p_{n+1} = \frac {-p_n + \sqrt {p_n^2 - 4q_n} } 2$ (3) and $q_{n+1} = \frac {-p_n - \sqrt {p_n^2 - 4q_n} } 2$ (4)

Now, we have
$p_{n+1} - 1 = \frac {-p_n - 2 + \sqrt {p_n^2 - 4q_n} } 2 = \frac {-2(p_n+q_n+1)} {p_n + 2 + \sqrt {p_n^2 - 4q_n} } $.
Using (2), it leads to :
$p_{n+1} - 1 = \frac {2(p_{n-1} - 1)} {p_n + 2 + \sqrt {p_n^2 - 4q_n} }$ (5)

Thus, $p_{n+1} - 1 $ and $p_{n-1} - 1 $ have the same sign.
Now, if $p_1 \geq 1$, then $p_{2n+1} \geq 1$ for all $n$. It follows that :
$|p_{2n+2} - 1 | = \frac {2|p_{2n} - 1|} {p_{2n+1} + 2 + \sqrt {p_{2n+1}^2 - 4q_{n2+1}} } \leq \frac {2|p_{2n} - 1|} {2p_{2n+1} + 2 } \leq \frac {|p_{2n} - 1|} {2 } $,
from which we deduce easily that the sequence $\{p_{2n} \}$ is convergent to 1.

Thus, for $n$ sufficientely large, we have $p_{2n} > \frac 1 2 $.
Using (5) again, we deduce in the same manner that
$|p_{2n+1} - 1 | = \frac {2|p_{2n-1} - 1|} 3$
from which it follows that $\{ p_{2n+1 \}}$ converges to 1.
Thus $\{ p_n \}$ has limit 1, and from (2) we deduce that $\{ q_n \}$ has limit -2.

In fact, the reasoning above holds again if $p_2 \geq 2$ (interchanging the parity).

Now, assume that $0<p_1,p_2 < 1$.
From (5), we deduce that $0 < p_n <1$ for all $n$.
From (2), it follows that $-2 < q_n < 0$ for all $n$.
Moreover, we may rewrite (1) as :
$p_{n+1} = \frac {q_n} {q_{n+1}}$, from which we deduce that
$p1p_2 \cdots p_n = \frac {q_0} {q_n}$ (6)

Now, assume for a contradiction, that $\{ p_n \}$ has a convergent subsequence, say $\{ p_{f(n)} \}$, with limit 0.
Then, since $\{ q_{f(n)} \}$ is bounded, we deduce that $\{ p_{f(n)} q_{f(n)} \}$ converges to 0, so that (from (1) ) $\{ q_{f(n)-1} \}$ has limit 0.
Thus, from (6), it follows that $p_1p_2 \cdots p_{f(n) - 1} $ has limit $+ \infty$, which contradicts that none of the $p_i$'s is greater than 1.
Therefore, there is no subsequence of $\{ p_n \}$ which has limit 0, and then there is $e>0$ such that $e \leq p_n$ for all $n$.
Using (5) and the reasoning above, we have $|p_{n+1} - 1| \leq \frac {|p_{n-1} - 1|} {1+e}$, and the conclusion is the same.

Thus, in any case, the sequence $\{ p_n \}$ has limit $1$, and the sequence $\{ q_n \} $ has limit $-2$.

Pierre.


floor function
number theory unsolved
number theory

The questions on the programming contest asked for $N$th square free number, where $N=100,1000,10^6,10^9$.
My student solved this problem (by writing not too short program :) ) and obtained that $10^9$-th square free number is $1644934081$.
After that I asked him to calculate $10^9\cdot \frac{\pi^2}{6}\approx 1644934066$ and said that it is an approximate answer. He was very surprized.
Justify my observation!

[b]Open question[/b] (at least for me)
What is the estimation for difference $N$-th square free number - $N\cdot \frac{\pi^2}{6}$?

Is true that $N$-th square free number > $N\cdot \frac{\pi^2}{6}$ ?

I think I've find a way to solve the problem but I'm not sure it's right:
$M=N^{th}$ square free number

$M = N+card(n, \exists p>1\ p^2|n, n<M) = N + \sum_{k=2}^{[\sqrt{M}]} \Big[\frac{M}{k^2} \Big]$

I think that $M=N\times\sum_{k=1}^{M}\frac{1}{k^2}$

Hmm... It contradicts with my observation that $10^9$th square free number is greater than $10^9\cdot\frac{\pi^2}{6}$.

right, I'm wrong
What about $ M = N + \sum_{k=2}^{[\sqrt{M}]} \Big[\frac{M}{k^2} \Big]$, is it right ? It looks hard to solve

At least, your formulae gives 1644887919 for $10^9$th square free number, and the right answer is showed above.

My formulae is wrong
is $M = N + \sum_{k=2}^{[\sqrt{M}]} \Big[\frac{M}{k^2} \Big]$ right if you take $N=10^9$ and $M=1644934081$ ?

Wait!
Hmm... $N + \sum_{k=2}^{[\sqrt{M}]} \Big[\frac{M}{k^2} \Big]\approx 2\cdot 10^9$ for these values.

Don't know why I'm wrong with $M = N + \sum_{k=2}^{[\sqrt{M}]} \Big[\frac{M}{k^2} \Big]$ since $M-N$ is the number of non square free integer less than M so they are $\sum_{k=2}^{[\sqrt{M}]} \Big[\frac{M}{k^2} \Big]$ because there is $\Big[\frac{M}{k^2} \Big]$ numbers less than $M$ and divisible by $k^2$ with $k$ between $2$ and $[\sqrt{M}]$.
What's my error ?

Very interesting problem

You count some numbers twice. For example, the number can be divisible by 36, then you will count it for $k=2$, $k=3$ and $k=6$.

Well, i think i get it.
Let $K(n) $,$ P(n)$ and ${p_n}$ be the number of square free numbers not greater than n, the nth square free number and the primes, respectivly.
By inclusion, exclusion principle, it is easy to get :
$ K(n) \approx n\cdot (1-\frac{1}{(p_1)^2})(1-\frac{1}{(p_2)^2})... , n \rightarrow \infty$
But  $K(P(n))=n$ and  $\frac{1}{ (1-\frac{1}{(p_1)^2})(1-\frac{1}{(p_2)^2})... } = \frac{\pi^2}{6}$ (this is in fact Euler's result). The rest follows...

[quote="Myth"]Open question (at least for me)
What is the estimation for difference $N$-th square free number - $N\cdot \frac{\pi^2}{6}$? [/quote]
I'll work instead with $f(N)-\frac{6N}{\pi^2}$, where $f(N)$ is the number of square-free integers no greater than $N.$
$f(N)=\sum_{k^2\le N} \mu(k)\cdot\left\lfloor\frac N{k^2}\right\rfloor=\sum_{k^2\le N} \frac N{k^2}\mu(k)-a_k\mu(k),$ where $0\le a_k<1.$

Thus $f(N)=\frac{6N}{\pi^2}-\sum_{k^2\le N} a_k\mu(k)-\sum_{k^2>n}\mu(k)\frac N{k^2}.$ Both sums can be estimated easily by taking absolute values; the first is less than $\sqrt{N}$ and the second is less than $\frac N{\sqrt{N}}=\sqrt{N}$. Thus $f(N)=\frac{6N}{\pi^2}+O(\sqrt{N}).$

Since $f$ and $f^{-1}$ differ by at most a constant multiple, the same estimate applies to your original problem.
These are usually gross overestimates; the normal values should be more like $\sqrt[4]{N}.$ Your actual value at $10^9$ is even closer, but it is possible to get lucky. I wouldn't expect the direction of the error to be consistent, although sign changes would be very infrequent.


Carla must arrive at the airport that is 49 miles away in 70 minutes or less. What is the minimum average speed in miles per hours that Carla must maintain to get to the airport in 70 minutes or less? Express your answer as a whole number.

$ 70 minutes \equal{} \frac{7}{6}hours$
$ v\equal{}\frac{d}{t}\equal{}\frac{49}{\frac{7}{6}}\equal{}\boxed{42}$

Because of per hour, we convert 70 min to 60 min (an hour) :

$70 minutes*\frac{60}{70}=60$

$49 minutes*\frac{6}{7}=42$

Hence the answer is 42


which window on an automatic grapher shows the graph of y =-7x +11 in three quagrant ?

a)  -10 ≤  x ≤ 10,  -5 ≤  y ≤ 10       b)  -5  ≤ x ≤ 5,   -10 ≤  y  ≤  5

c)  -10  ≤ x ≤  10  , -5 ≤  y ≤ 15    d)  -5 ≤ x ≤ 10 ,  -5 ≤  y ≤  5

hello, i think it must be c),$ \minus{}10\le x\le 10$,$ \minus{}5\le y \le 15$
Sonnhard.


If a,b,c are sides of a triangle with <C=90
then, prove that,    [b] c^n > a^n+b^n[/b] for all n>2 natural nos.

the inequality  is equavilent  to :
 $ (a^2\plus{}b^2)^n \geq  (a^n\plus{}b^n)^2$
 It's  familar  with

Hong Quy wrote;
[quote]the inequality is equavilent to :
(a^2+b^2)^n => (a^n+b^n)^2
It's familar with[/quote]

NOT FAMILIAR TO ME!!!  :(

[quote="not_trig"]it's the power mean inequality[/quote]

I have heard of this inequality, but what is the general statement of the inequality and the proof(s)?  Thanks.


Prove that :
\[ \sum_{k\equal{}0}^{n\minus{}1} (\minus{}1)^{k}  (n\minus{}k)^n\binom{n}{n\minus{}k} \equal{} n!\]

[b]Question:[/b]  How many functions $ f : [n] \to [n]$ are bijections?

[b]Answer 1:[/b]  $ n!$.  This is the RHS.

[b]Answer 2:[/b]  For every subset $ S$ of $ [n]$ of size $ n\minus{}k$, there are $ (n\minus{}k)^n$ functions with range contained in $ S$ and $ {n \choose n\minus{}k}$ such subsets.  To compute the number of functions with range exactly $ [n]$ is just inclusion-exclusion:  start with the functions with range contained in $ [n]$, subtract the functions with range contained in $ [n\minus{}1]$, etc.  This is the LHS.


function
limit
linear algebra
matrix
algebra
domain
induction

What condition(s) are necessary for newton's method to converge?  My calc textbook says something about $ \minus{}1< f(x)f''(x)/(f'(x))^2 < 1$, but where does this come from/how is it used?

The Newton's Method is a Iterative method. For the Iterative method ,if the Iterative function |g'(x)|<=1 .the Iterative sequence converge to the exact solution of the equation.

g(x)=x-f(x)/f'(x) is the Iterative function of Newton's Method. you can refer to any numerical analysis textbook for the Iterative Method

thanks... I think it makes some sense now.  I do not have access to any textbooks though (other than my calc book), so could you please explain where the condition $ |g'(x)| \le 1$ comes from?

Another thing that I am interested in is how to determine which start values will produce a convergent sequence.  Though most of the problems I have faced seem to work with nearly any start value, a few seem to require relatively good starting guesses to converge - such as $ y\equal{}tan x \minus{}x$ with $ x \in (\pi/2, 3\pi/2)$.

When we use Iterative Methods (include Newton's Method) to  solve the equation $ f(x)\equal{}0$, we convert $ f(x)\equal{}0$ to it's equivalent equation $ x\equal{}g(x)$.such as $ g(x)\equal{}x\minus{}f(x)$,then, if $ x_0$ is a root of $ x\equal{}g(x)$, namely $ x_0\equal{}g(x_0)$ , so that
$ x_0$ is a root of $ f(x)\equal{}0$,because $ g(x_0)\equal{}x_0\minus{}f(x_0)\Rightarrow f(x_0)\equal{}0$. vice versa!
The function $ g(x)$ was called Iterative function ,For any initial value $ x_0$(here $ x_0$ is not root of $ x\equal{}g(x)$ )can produce an Iterative sequence {$ x_n$}:
$ x_1\equal{}g(x_0)$...$ x_2\equal{}g(x_1)$......$ x_n\equal{}g(x_{n\minus{}1})$  if $ {x_n}$ converge to $ x^*$ then $ \lim_{n\rightarrow \plus{}\infty}x_n\equal{}\lim_{n\rightarrow\infty}g(x_{n\minus{}1}) \Rightarrow  x^*\equal{}g(x^*)$  so, $ x^*$ is a root of $ x\equal{}g(x)\Leftrightarrow f(x)\equal{}0$

I am sorry ,the condition $ |g'(x)\leq 1|$ is wrong .the  correct condition is that : exist $ L$ ,s.t. $ |g'(x)|\leq L<1$

The condition $ |g'(x)|\leq L<1$ can ensure the Iterative sequence {$ x_n$}'s convergence for any initial value $ x_0$ :
Because :
\[ |x_{k\plus{}i}\minus{}x_{k\plus{}i\minus{}1}|\equal{}|g(x_{k\plus{}i\minus{}1})\minus{}g(x_{k\plus{}i\minus{}2})|\equal{}|g'(\xi)\parallel{}x_{k\plus{}i\minus{}1}\minus{}x_{k\plus{}i\minus{}2}|\leq L|x_{k\plus{}i\minus{}1}\minus{}x_{k\plus{}i\minus{}2}|\leq\cdots \leq L^{k\plus{}i\minus{}1}|x_1\minus{}x_0|\]
so \[ |x_{k\plus{}p}\minus{}x_k|\leq\sum_{i\equal{}1}^{p}|x_{k\plus{}i}\minus{}x_{k\plus{}i\minus{}1}|\leq \sum_{i\equal{}1}^{p}L^{k\plus{}i\minus{}1}|x_1\minus{}x_0|\equal{}\frac{L^k(1\minus{}L^p)}{1\minus{}L}|x_1\minus{}x_0|\]
The above expression tells a  fact that {$ x_n$} is a Cauchy sequence .

I am sorry!Because my English is very poor,  so some syntax errors in my reply is inevitable,however i hope taking pleasure in help anybody!

xiangtianxu, thanks for the explanation!  I only have a few things to say:

-we are not necessarily using $ f(x)\equal{}0$ for our iteration, we are just using a function with the same zeros.  For example, with newton's method we are using $ g(x) \equal{} x\minus{}\frac{f(x)}{f'(x)}$ - but $ \frac{f(x)}{f'(x)}$ has the same zeros as $ f(x)$ as long as none of the zeros are shared with $ f'(x)$.

-The existence of $ |L|<1$ proves that the method converges, but if such an $ L$ does not exist, the method could still converge for some $ x_0$ values... right?  So my next question - how could we find/predict these values?  Anyway, I suppose that this question may not have a definite answer.

-what's a cauchy sequence?

On a side note, xiangtianxu, I think your English is pretty good.  Though your grammar is imperfect, you still manage to communicate your ideas well, which is the main goal of language anyway.

a small note:
when you say "The condition $ |g'(x)| \le L < 1$ can ensure," you are saying that the condition might or it might not imply that the sequence converges.  I believe what you mean is that "the condition $ |g'(x)| \le L < 1$  will ensure the iterative sequence's convergence" or that "the condition $ |g'(x)| \le L < 1$  ensures that the iterative sequence will converge".  The difference here is that either of these two statements assert that the condition implies the sequence's convergence, while the wording you used does not really say what the condition proves.

Other than that, I think that everything you said is pretty clear.

A condition for the iterative scheme $ x_{n\plus{}1} \equal{} g(x_n)$ with $ f(a) \equal{} 0$ to converge given an initial guess within some neighbourhood of $ a$ is that g is differentiable and $ |g'(x)| < 1$ for x within that interval.

If we want to use Newton's Method on f with $ f(a) \equal{} 0$, we can let $ g(x) \equal{} x \minus{} \frac{f(x)}{f'(x)}$ and it can be shown that there exists an interval around a for which $ |g'(x)| < 1$ provided that $ f''$ exists and is bounded in this interval, with $ f'(a) \ne 0$, and so Newton's Method will converge.

TO facis:
      "-what's a cauchy sequence? "
Cauchy sequence's Definition:
     {$ x_n$} is a sequence,if  $ \forall \epsilon>0,\quad \exists N_0\in N$,while $ n,m>N_0$,then $ |x_n\minus{}x_m|<\epsilon$(apparently ,we can write m=n+p for $ p\in N$)
we called {$ x_n$} as a Cauchy sequence.

In the real number field:The Cauchy sequence is a equivalence of the convergent sequence. (it hold on the general  complete matric space).
Then, the condition   $ |g'(x)|\leq L<1$ imply which for any initial value $ x_0$ in the function's(f) domain of definition .Certainly,  the existence of $ g'(x)$ is required!

"The existence of  proves that the method converges, but if such an  does not exist, the method could still converge for some  values... right? So my next question - how could we find/predict these values? Anyway, I suppose that this question may not have a definite answer"

I think that any methods should to hold  some conditions.so ,Iteration can't solve some  questions which haven't hold the conditions of Iteration.Newton's method else.
But,if a equation f(x) holds on the conditions of Iteration(Newton's method) ,we can use Iteration(Newton's method) to solve it.

For example:
    If f(x) is a defined in an interval [a,b] ,and hold on following conditions
$ f(a)f(b)<0,\quad f'(x)f''(x)\neq  0 \quad for \quad x\in [a,b],$
we can prove that for the starting number  $ x_0\in [a,b]$ if $ f(x_0)f''(x_0)>0$ then the Iterative sequence which was produced by the Newton's method is a monotonic sequence with convergence。
Proof:
\[ \because f(a)f(b)<0,f'(x)f''(x)\neq 0\]
$ \therefore f'(x)\neq 0$ imply f(x)  is a  monotone function , therefore  f(x)=0 has a unique $ x^*$ solution in [a,b].

 For the condition $ f'(x)f''(x)>0$,there are four cases should be  considered.
1.$ f'>0,f''>0$
2.$ f'>0,f''<0$
3.$ f'<0,f''>0$
4.$ f'<0,f''<0$
Here we just consider case 1,  there is same way to handle the other cases.
$ \because f(x_0)f''(x_0)>0$,therefore $ f(x_0)>0$
$ \therefore x_0>x^*$ ,therefore  $ x_1\equal{}x_0\minus{}\frac{f(x_0)}{f'(x_0)}<x_0$
let $ g(x)\equal{}x\minus{}\frac{f(x)}{f'(x)}$,  then $ g'(x)\equal{}\frac{f(x)f''(x)}{[f'(x)]^2}$
so we can see
      $ x_1\minus{}x^*\equal{}g(x_0)\minus{}g(x^*)\equal{}g'(\xi)(x_0\minus{}x^*)>0$
      $ x_0>x_1>x^*$
use the induction,we can get that:
      $ x_{n\minus{}1}>x_n>x^*$ it tells our a fact that the sequence {$ x_n$} is a monotone decreasing sequence with inf $ x^*$
$ \therefore \lim_{n\rightarrow\infty}x_n\equal{}x^*$
This proof already tells our a truth that how to choose the starting number when the f hold on the conditions

Sorry again: :)
Use English to express my opinion is so difficult to me,there should  have many syntax error in my state which would bring
some trouble for you.i honestly say :"i am so sorry". in the  meantime, i hope you can point  my error and correct it in paraphrase.
Thank you very much!


I don't know if it was proposed before.

    Two triangles, which lie on the same circle, intersect at points A,B,C,D,E,F.
  Then prove that lines AD, BE, CF intersect at one point.

Sketch :
From Pascal theorem we have to demonstrate that $KN, LP, MQ$ are cevians in triangle $UVW$,
equaling to demonstrate $\frac{sin \phi_1 }{sin \phi_2} \cdot \frac{sin \phi_3 }{sin \phi_4} \cdot \frac{sin \phi_5 }{sin \phi_6}=1$.
But denoting arc angles as $\alpha, \beta , \gamma, d, e, f$ (multiplyied by 2) and using
Ceva theorem in triangles $ABU$ and others we have
$\frac{sin f}{sin e} \frac{sin \phi_1 }{sin \phi_2} \frac{sin j}{sin b}= 1$,
multiplying we get the desired result.

Nice solution.
   In Coxeter's book I found that some of Pascal's lines are concurrent. Does it mean that this problem has been already proposed?


In the $xy$-plane, what is the length of the shortest path from $(0,0)$ to $(12,16)$ that does not go inside the circle $(x-6)^{2}+(y-8)^{2}=25$?

[hide]The circle has center (6,8) with radius 5. (6,8) is the midpoint of the line from (0,0) to (12,16). The length from (0,0) to (6,8) is 10.

If we go around the circle, the straight parts of the path would be the leg of right triangle with other sides 5 and 10, which makes a 30-60-90 triangle, so the straight parts have length $5\sqrt{3}$, and there are two of these. The arc part of the path has a angle of 60 degrees, so the length is $10\pi/6$

$\boxed{10\sqrt{3}+\frac{5\pi}{3}}$.[/hide]


Let $ a,b,c$ be nonnegative real numbers, no two of which are zero. Prove that
\[ \sum a\sqrt{a^2\plus{}bc} \ge (2\minus{}\sqrt{2})(\sum a^2\plus{}\sqrt{2}\sum ab).\]
:)

Actually, for all $ p>1$, the inequality holds

$ \sum a\sqrt {a^2\plus{}(p^2\minus{}1)bc} \ge (2\minus{}p)\sum a^2\plus{}2(p\minus{}1)\sum ab$.

[quote="Vasc"]Actually, for all $ p > 1$, the inequality holds

$ \sum a\sqrt {a^2 \plus{} (p^2 \minus{} 1)bc} \ge (2 \minus{} p)\sum a^2 \plus{} 2(p \minus{} 1)\sum ab$.[/quote]
Of course, VasC. :) It follows from Schur's Inequality and my result:
\[ \sum \frac{1}{a\plus{}\sqrt{a^2\plus{}kbc}} \ge \frac{9}{(1\plus{}\sqrt{k\plus{}1})(a\plus{}b\plus{}c)}.\]
:)

But it is not shalex's one,it is from me .:(


$a=-3,b=-4,c=-5$ also works . But none of them equal to the sum up to ther other two.

For non-negative reals it's easy:

Squaring and rearranging the first inequality we get

$(a-b-c)(a-b+c)\geqslant 0$ or

$(-a+b+c)(a-b+c)\leqslant 0\qquad(1)$

Similarly, from other two we get

$(a-b+c)(a+b-c)\leqslant 0\qquad (2)$
$(a+b-c)(-a+b+c)\leqslant 0\qquad(3)$

If neither of $-a+b+c,a-b+c,a+b-c$ is zero, the we have three numbers that are pairwise of opposite sign, which is impossible. Hence, at least one of them is zero.

Actually, it seems much easier than that: suppose without loss of generality that $a \geq b \geq c$.  Then we have immediately that  $b \geq a + c$.  From this it immediately follows that $c \leq 0$.  If we're looking only at the non-negative case, it's immediately clear that the only solution is $(a, a, 0)$.  Also, if we don't restrict ourselves to the non-negative case, any solution of the form $(a, b, c)$ with $a \geq b$ and $c\leq b - a$ will work.

but in the question i think it was for all real
but it does not work for negative real

[quote=Rushil]If $a,b,c$ are positive three real  numbers such that $| a-b | \geq c , | b-c | \geq a, | c-a | \geq b$ . Prove that one of $a,b,c$ is equal to the sum of the other two.[/quote]
[url=http://www.artofproblemsolving.com/community/c6h579719p3423804]Romania District Olympiad 2014[/url]

WLOG, We may assume that a>=b>=c.
Now,a-b>=c,
         b-c>=a
         a-c>=b
Summing up the first 2 equations we get 0>=c.
But since c is positive, c=0.
Again from the first 2 equations we get a>=b and b>=a. This implies that a=b.
Therefore, we get a=b+c.


induction
number theory proposed
number theory

I have a question: does $\|$ mean that $p^{n+1}$ is the power of $p$ with the maximal exponent which divides that number? (I've seen this notation before).

Induction after $n$ works perfectly fine:

$p^n\|(p-1)^{p^{n-1}}+1=a+1$. We now use the formula $a^p+1=(a+1)(a^{p-1}-a^{p-2}+\ldots-a+1)$. It's pretty clear (also making use of the fact that $p$ is odd) that $a^{p-1}=M_{p^2}+1,\ -a^{p-2}=M_{p^2}+1,\ldots$, so we get $a^{p-1}-a^{p-2}+\ldots-a+1=M_{p^2}+p$, so $p\|\frac{a^p+1}{a+1}$, and since $p^n\|a+1$, we get $p^{n+1}\|a^p+1$.


Putnam
greatest common divisor
number theory unsolved
number theory

1)
prove that the number of 5-tuples of positive integers (a,b,c,d,e) satisfying
1/a + 1/b + 1/c + 1/d + 1/e = 1/5
 is an  odd integer

2)let S denote the set of 6-tuples  (a,b,c,d,e,f) satisfying
a 2 +b 2 +c 2 +d 2 +e 2  = f 2
consider the set T = {abcdef } a,b,c,d,e,f beLonging to S.
Find the greatest common divisor of the elements of T

3)Let p be a prime > 3 .find the pairs of integers (a,b) satisfying
a 2  + 3ab + 2p(a+b) + p 2  = 0

cheers!!

I have a question regarding (1): by (a,b,c,d,e) we usually denote ordered 5-tuples. Is this the case here? I mean, if a=/=b, is (a,b,c,d,e) the same as (b,a,c,d,e) or not?

I think it should be ordered 5-tuples :? though the paper doesnt mention it explicitly it got me confused me in the real exam as well.it was the last question and the only one in which i dint make real progress even though i had a full hour at my disposal :( .that effectively kills my chances for selection this year,given the fact that they select only 3-4 students from 12th grade.(for me it's been a double blow,i was in the last 250 in national physics olympiad as well,but cudnt make it to the last 25 :(  :(  :(

Well, I think the 5-tuples could be found. We take min{a,b,c,d,e}. We can se that it must be <=25 and so on. I don't know if it works though, because there are WAY TOO MANY cases  :?

I think there's another idea here.

HEY
look up putnam 1997.it has got a similar problem

I think I've made some mistake. For ordered 5-tuples I get an EVEN number. I didn't count them, but I considered the cases: all of the 5 numbers are distinct, 2 of them are equal and the other 3 are different from the first 2 and distinct etc. If we have ordered 5-tuples we multiply each solution by some number, which is even for many of the cases I mentioned above, so we can eliminate them.

Can someone else try to do this as well? I think I'm missing something.

Let me tell you what I mean:

We have 1 solution where all the numbers are the same:{25,25,25,25,25}.

Each solution of the form {a,a,a,a,b} has to be counted 5 times, because we have 5C5 possible positions for b. I'll find the solutions of this sort later.

Each solution of the form {a,a,a,b,b} has to be counted 5C2=10 times, which is even, so we can disregard it.

Each solution of the form {a,a,a,b,c} has to be counted 20 times, which is also even.

Each solution of the form {a,a,b,b,c} has to be counted 30 times (also even).

Each solution of the form {a,a,b,c,d} has to be counted 60 times (even).

Finally, each solution of the form {a,b,c,d,e} has to be counted 120 times (even).

This means that for the parity of the total number of solutions we only need to cionsider the solutions of the form (a,a,a,a,a) (1 such solution) and those of form (a,a,a,a,b). The parity of the total number of ordered 5-tuples is the parity of the number of solutions of the form {a,a,a,a,b}+1, which means that in order to have an odd number of solutions (in total) the number of sets of the form {a,b} which satisfy 4/a+1/b=1/5 has to be EVEN.

Now let's solve the eqn 4/a+1/b=1/5. 1/5-1/b=4/a, so (b-5)/5b=4/a. It's easy to show that the only pair (a,b) is (45,9), so we have an ODD number of pairs (a,b) s.t. 4/a+1/b=1/5. This statement contradicts the last word of the last paragraph, so where's the mistake? Maybe they didn't want ORDERED 5-tuples?

ya MAYB they did not want ordered 5-tuples!!!(i.e after seeing your calculations)
i am really sorry i can not make the question any more clearer.and i am really sorry about the fact that you (grobber,i mean) have wasted quite some time on it. (but i cant help it)
if u "wish",try it for unordered 5-tuples
cheers mate!!

Don't worry about it, it didn't take that much time. :D

I doubt I'll try it for unordered 5-tuples, since I have no idea how to start :)


According to CEE's website, the USABO Semifinalists (top 10%) will be announced on March 3 (Monday). From what I know, the list itself will be posted on CEE's website, and your teacher will be able to see your score (even if you did not make semifinals).

Last year, the cutoff for Semifinals was a score of 30 out of 50 on the Open Exam.

Good luck everyone!

haha...i didn't know that my teacher would be able to see my score as well.
wow i'm really nervous. good luck to everyone who took the exam.

Are the semifinalists actually posted on the website? I can't find it anywhere and my school was off today... I want to know if I made it o.o

[quote="kops723"]I can't find it anywhere and my school was off today... I want to know if I made it o.o[/quote]

I think if you find the teacher that distributed the test, he/she might have your results.

omg! i got in XD
how did everyone else do?

I made it too! :)

The passing score this year is 29 out of 50 on the Open Exam. I believe the highest score in the nation is 43 (correct me if I'm wrong), which is the same as last year's highest.

Correction from previous post: Only your teacher/test distributor has your score right now. However, if your teacher/test distributor gives you his/her username and password for CEE, then you can check various other statistics (ie: how many students took the Open Exam, how many qualified for Semifinal Round, how many students qualified per school, etc).

The [b]Semifinal Exam[/b] will be administered between March 10th and March 21st (ask your test distributor when he/she will administer the test). According to CEE's website:
[quote] The Semi-final is a two hour exam consisting of three sections. Part A of the Semi-Final Exam covers basic knowledge in a multiple choice format (approximately 40 minutes). Parts B and C consist of higher level questions with multiple answers, interpretation of graphs, analysis of data, case studies, fill in the blank questions and some open response questions (approximately 80 minutes). A student must pace him/herself over the three sections. [/quote]

Last year, Part A was multiple choice, Part B was matching & fill-in-the-blank, and Part C was free response (mostly on genetics if I remember correctly). My teacher told me they change the free response emphasis each year (ie: genetics, plant biology, etc), but I am [i]not[/i] sure how accurate this is.

does anyone know where we can find practice questions? this is the first time i've qualified for semifinals so i'm new to this

good luck to everyone and congrats

Darn, I was expecting a 40+ and I ended up with a 33...

BTW the first question about iron-deficiency was BS, it had two answers....

wow, i guessed on half the questions and i still got a 32 and got in..
i was like blah i dont know anything about bio ill just see what happens
and i got in. hm

approximately how many students each year take USABO?
and how many get into semifinals?

I think the number last year was about 8000... And 500 usually make it into semifinals.

Yeah, the first question threw me in a loop, too.

But I got in: 39 , woohoo!

I got in too! Quite excited--my AP bio class had barely finished genetics, like chapter 15 in Campbell, and I hadn't had general bio since 9th grade.

Is there anyone here who's done the semifinal round before? I imagine that many people take AMC/AIME every year, but not many retake USABO since it is so year-specific.

I got in :)
39 hehhehee

Semifinals look impossible tho

[quote="7h3.D3m0n.117"][quote="Harmonikdiskorde"]I got in too! Quite excited--my AP bio class had barely finished genetics, like chapter 15 in Campbell, and I hadn't had general bio since 9th grade. [/quote]

Campbell is a good book but my 9th grade AP bio class uses the Solomam. I wanted to take the test by my teacher didn't distribute it  :( .[/quote]

9th grade AP Bio? Alas, our schools must have different educational philosophies. At mine, AP sciences must be preceded by a first year, level honors science course. "Biology I" is the standard 9th grade science, and AP Bio is generally off-limits until 12th grade, per Madame Department Head.

I remember a zebra-striped bio book in 9th grade. It actually tried to teach the details of the Krebs cycle, succinyl coA and all, a section that the teachers most eagerly skip.

[quote="Harmonikdiskorde"]9th grade AP Bio? Alas, our schools must have different educational philosophies. At mine, AP sciences must be preceded by a first year, level honors science course. "Biology I" is the standard 9th grade science, and AP Bio is generally off-limits until 12th grade, per Madame Department Head.

I remember a zebra-striped bio book in 9th grade. It actually tried to teach the details of the Krebs cycle, succinyl coA and all, a section that the teachers most eagerly skip.[/quote]

It's a new program designed to give the "smarter" kids in the class something challenging (which I would say has quite worked). We are taking the AP exam on May 12th, but I was nudging my teacher to register the school for the USABO, which apparently he never go to.

We had just finished evolution and genetics so I don't think we would have gotten in anyway, since we just started organismal during the test times.


geometry
inradius
Functional Analysis
real analysis
real analysis unsolved

here's a nice problem. I found an idea but I couldn't solve the hole problem
Let $ E$ be a Banach Space, and let $ \Omega \subset E$ be an open bounded set.
suppose that for all $ x,y \in \Omega$ there is a ball containd in $ \Omega$ which contains $ x$ and $ y$
show that $ \Omega$ is a ball

Let $ d$ be the diameter of $ \Omega$, and $ r$ be its inradius (i.e. the supremum of the radii of all open balls contained in $ \Omega$). Our assumption implies $ d \equal{} 2r$. It follows that for any $ n\ge 1$ there is a point $ x_n$ such that $ B(x_n,r\minus{}1/n)\subset \Omega\subset B(x_n,r\plus{}1/n)$. The sequence $ x_n$ has a limit, or so I hope.


geometry
circumcircle
congruent triangles
Pythagorean Theorem

A ten foot ladder leans against a vertical wall.  Its midpoint is twice the distance from the floor as from the wall.  How high does the top of the ladder go on the wall?

solutions!  post solutions, not answers.  Or at least outline your method or phrase it as a hint or something.

Explain the steps you took.
"Let the top of the ladder be point A, the bottom be point B, and the middle be point M.  Let C be the corner of the wall.  Draw perpendiculars from M to BC and CA, and let them intersect respectively at P and Q.  We are given MP = 2MQ.  We know
MB = AM = 5.  MP and AC are two parallel lines cut by the transversal AMB, so angle MAQ = angle BMP.  Also, angle AQM = angle MPB because both are right.  Thus, triangle AQM is similar to triangle MPB, and since they have the same hypotenuse, they are congruent."

I mean, this was more technical really then you have to do -- you just have to explain everything you did.  It's usually helpful to make an explicit labeling to begin with, and then after that just say everything you found and why you found it was true.  I didn't finish the rest of the proof, but it can be written up the same way -- congruent triangles, so equal segments, then the pythagorean theorem, and then we're done.

Arg, I'm not very good with English  so I thought the distance between the midpoint and the wall was twice the distance from the floor, but the answer is just 2*the answer I got ([hide]2:rt5:[/hide] so meh.

I have to say it does get kind of annoying when people don't post solutions, especially on a constant basis

Yes, I'm talking about you, not you ml2, but you *looks at someone's name in AoPS*

Here is simplified version of JBL's description. (that one was kinda confusing)

[img]http://bwsolo.com/prob1.jpg[/img]

Heh hopefully this is right, tell me if im wrong lol

Wow, nice.  Yes, you could post pictures, too :).

Click on the "Img" button before and after you type in the address (URL) for the Image.
You can also highlight the URL and click on "Img", either way.

What I'm curoous about is how you found the perfect pucture for this problem, do you host this website yourself?

Umm I made the image in photoshop and then put it on my webspace and linked it in  tags

As JBL mentioned, you should label all the points you plan to use. A is the top of the ladder, B is the bottom, M is the midpoint, C is the right angle and such( refer to JBL's solution). MC is congruent to AM and BM because the circumradius of a right triangle is equal to half the hypotenuse. Using this you can determine that PC is congruent to BP and that ABC is a 30-60-90 degree triangle, and solve for AC.

[/quote] If home is where the heart is and my heart is in this universe, what are you doing in my house?


[x] is defined to be the least integer which exceeds or is equal to x. Compute [((3^(1/2)) +1)^2m] for m=1,2,3,4,& 5. Show that 2^(m+1) divides these numbers. Prove
2^(m+1) always divide [((3^(1/2)) +1)^2m].

The sequence in question is $ a_m \equal{} (1 \plus{} \sqrt {3})^{2m} \plus{} (1 \minus{} \sqrt {3})^{2m}$, which we can write as $ (4 \plus{} 2 \sqrt{3})^m \plus{} (4 \minus{} 2 \sqrt{3})^m \equal{} 2^m \left( (2 \plus{} \sqrt{3})^m \plus{} (2 \minus{} \sqrt{3})^m \right)$.  The sequence $ \frac{a_m}{2^m} \equal{} b_m$ satisfies the recurrence relation

$ b_{m\plus{}2} \equal{} 4b_{m\plus{}1} \minus{} b_m$

with $ b_0 \equal{} 2, b_1 \equal{} 4$.  Hence $ b_m$ is always even.


Gauss probability function algorithm ARML calculus derivative

I know how to solve Two-Person Zero-Sum games, but how do you solve N-Person Zero-Sum games? For example, how would you find the optimal solution for each player in the following game:

Three players simultaneously choose a number (with replacement) from the set $ \{1,2,3\}$. The person with the smallest [i]unique[/i] number recieves a payoff of 2, while the other two players each recieve a payoff of -1. When all players choose the same number, the payoff is 0 to each of them.

Winning this game depends on the strategies that your opponents use, so it cannot have an optimal solution.

With these kinds of games, the best you can generally do is make up a few strategies, see how they fare against each other, and tabulate the results.  Of course, even doing that requires specifying some tournament rules.

This is not true. By the Minimax Theorem of von Neumann there always exists an optimal strategy in a Constant/Zero-Sum game.

[quote="Mathworld and Wikipedia"]Minimax Theorem: The fundamental theorem of game theory which states that every finite, zero-sum, two-person game has optimal mixed strategies. It was proved by John von Neumann in 1928.

In 1944 John von Neumann and Oskar Morgenstern proved that any zero-sum game involving n players is in fact a generalized form of a zero-sum game for two players.[/quote]

These two results imply that any constant/zero-sum game should have an optimal (mixed) strategy. In fact, I even know what the optimal mixed strategy is for this game, I just don't know how it was found.

You did not use the word "mixed" in your first post.  It is a different question.  Perhaps I misunderstood, but "optimal for each player" has a specific meaning.

"Strategy" is widely used to mean "mixed strategy" in the context of strategic games, for the reason that analyzing the pure strategies isn't interesting on its own (it's just some finite computation and it doesn't exhibit the same nice properties).

Gauss: I don't know how to do these in general except as differential equations.  For the particular game you mentioned, the Nash Equilibrium is that each player picks 1 with probability $ \frac{1}{2}$ and the other two with probability $ \frac{1}{4}$, assuming I've correctly ruled out any equilibria on the boundary.

That's the solution that I have also, but I did it in a very ad hoc "logic-it-out" kind of way. I was hoping to find a procedure for how to solve N-Player games in general. What is your method with differential equations?

Well, it's a procedure, but to actually implement it with reasonable amounts of effort seems to require using the "solve" function on your favorite CAS.  For this particular game, we have six variables (the probability that player $ i$ chooses $ j$ for $ i \equal{} 1,2,3$, $ j \equal{} 1,2$) with certain constraints (nonnegative and the sums of the appropriate pairs are at most 1); for each collection of variables, we can write down the utility to each player of choosing that strategy.  At a Nash equilibrium, the partials of the utility to player $ i$ with respect to the variables he controls must be zero; this gives you six equations to solve, and Mathematica tells me that the solution I mentioned is unique.  (I haven't tried to solve by hand, actually.)

As it turns out, there are some other Nash equilibria for this game on the boundary: for example, player 1 always picks 1 and player 2 and 3 never pick 1 is a Nash equilibrium, but it's clearly not optimal for players 2 and 3.

I gather that there are algorithms for computing Nash equilibria, but I don't know anything about any of their details :(

Is your "logic-it-out" approach simple enough to write down here?

Completely unrelatedly, I gather SC will be going to the new ARML site -- I hope it goes well, though I'm sorry I won't see you at Penn State.

My solution went like this:

My solution assumed that the equilibrium was symmetric with respect to all the players and involved experimenting with different mixes until I got close enough to prove the rest.

After playing around with numbers I conjectured that the optimal strategy involved picking 1 50% of the time. To prove this I reasoned as follows: If each player plays a mixed strategy $ (p,q,r)$, where $ p < .5$, I can improve against them by playing the strategy $ (1,0,0)$. This is because my expected value when we all play $ (p,q,r)$ is zero, but when I play (1,0,0) against their mixed strategy my expected value is $ E \equal{} 2(1\minus{}p)^2 \minus{} 2p(1\minus{}p) \equal{} 2(1\minus{}p)(1\minus{}2p) > 0$.

If we all play a mixed strategy $ (p,q,r)$ with $ p > .5$, I can improve depends on how they mix q and r. If $ p \geq .5$ and $ q < r$, I can improve by playing $ (0,1,0)$. This is because my expected value against such a strategy is $ E \equal{} 2(p^2 \plus{} r^2) \minus{} (2pq \plus{} 2qr) \equal{} 2p(p\minus{}q) \plus{} 2r(r\minus{}q) > 0$. Likewise, if $ p \geq .5$ and $ q > r$, I can improve by playing $ (0,0,1)$.

This shows that if there is a symmetric Nash equilibrium it must have $ p \equal{} .5$ and $ q \equal{} r$. If you continue to look at the expected values as above you can show that both of these are in fact sufficient for a Nash Equilibrium. So an equilibrium strategy is $ (.5, .25, .25)$. This method does not rule out the possibility of other Nash equilibria.

A few days later I realized that this could be changed into a calculus and/or algebraic solution by setting the partial derivatives of the expected value equal to zero and proving that the solution was in deed a local minimum for E (but I was still working under the assumption that the equilibrium was symmetric for all players).

More recently, in a book called [u]Dynamic Noncooperative Game Theory[/u] by Tamer Basar and Geert Jan Olsder, I found an algebraic procedure for how to find all [i]inner[/i] mixed strategies for N-Person finite games in Normal Form. It leads to a system of nonlinear (quadratic) equations. The nasty looking, but simple, formula can be found on p.93 of their book.

They say, however, "there is no simple method to determine the [boundary] Nash equilibrium solutions of N-Person finite games in normal form. One basically has to check exhaustively all possible combinations of N-tuples of strategies, to see which ones provide a Nash equilibrium. This enumeration, though straightforward, could at times be rather strenuous, especially when N, or $ m_i$ (the number of possible strategies for each player) are large. However, given an N-tuple of strategies asserted to be in Nash equilibrium, it is relatively simple to verify their equilibrium property..." (p.89)

Thanks for the reference and the details.  My knowledge of game theory is rather thin, so I was curious if you can answer the following (rather vague) question: why are zero-sum games special?  I gather that solving them is relatively simpler than solving arbitrary strategic games -- is there a "natural" explanation for this phenomenon?

Here's a quote from some [url=http://www.math.ucla.edu/~tom/Game_Theory/Contents.html]lecture notes[/url] by Thomas S. Ferguson. They make a decent introduction to the subject of game theory, but focus mainly toward economics students.

"When the sum of the payoffs is no longer zero (or constant), maximizing one’s own payoff is no longer equivalent to minimizing the opponent’s payoff. The minimax theorem does not apply to bimatrix games. One can no longer expect to play “optimally” by simply looking at one’s own payoff matrix and guarding against the worst case. Clearly, one must take into account the opponent’s matrix and the reasonable strategy options of the opponent. In doing so, we must remember that the opponent is doing the same. The general-sum case requires other more subtle concepts of solution."

Additionally, non-constant sum games can be complicated by the possibility (if allowed) of cooperation/punishment.