geometry
circumcircle
inradius
incenter
trigonometry
function
trig identities

Let $ABC$ be a triangle. Prove that $b+c=2(R+r)\Longrightarrow A=90^{\circ}$

Can you define what the terms R, r, b, and c stand for?

[color=darkred][b][u]Standard notations[/u][/b] (at least in the my country), for the triangle $ABC$ :

$\{\begin{array}{c}\{\begin{array}{c}\mathrm{a=BC\ ;\ b=CA\ ;\ c=AB\ .}\\\\ \mathrm{p\--\ the\ semiperimeter\ ;\ S\equiv[ABC]\--\ the\ area\ .}\end{array}\\\\ \{\begin{array}{c}\mathrm{m_{a}\--\ the\ A-median\ .}\\\\ \mathrm{h_{a}\--\ the\ A-altitude\ .}\\\\ \mathrm{l_{a}\--\ the\ A-bisector\ .}\end{array}\\\\ \{\begin{array}{c}\mathrm{R\--\ the\ circumradius\ ;\ O\--\ the\ circumcenter\ .}\\\\ \mathrm{r\--\ the\ inradius\ ;\ I\--\ the\ incenter\ .}\\\\ \mathrm{r_{a}\--\ the\ A-exinradius\ ;\ I_{a}\--\ the\ A-exincenter\ .}\end{array}\\\\ \{\begin{array}{c}\mathrm{\delta_{d}\ (A)\--\ the\ distance\ of\ the\ point\ A\ to\ the\ line\ d\ .}\\\\ \mathrm{Pr_{d}\ (A)\--\ the\ projection\ of\ the\ point\ A\ to\ the\ line\ d\ .}\\\\ \mathrm{\overline{MNP}\--\ the\ points\ M,N,P\ are\ collinearly\ .}\end{array}\\\\ \mathrm{a.s.o.}\end{array}$

[size=134][b][u]Remark.[/u][/b] In the my opinion, this Site has the posibility to construct a set of the standard notations

(a pocket dictionary), in short an [b]U[/b]niversal [b]M[/b]athematical [b]L[/b]anguage - [b][u]U.M.L.[/u][/b] !

[b][u]Question.[/u][/b] Exists anywhere (an address) such a thing ? If not, then come on construct (create) it ![/size][/color]

we may use some trig identities to solve this: namely:

$\frac{b}{2R}=\sin B$, and $\frac{r}{R}+1=\cos A+\cos B+\cos C$

the result follows from a little algebra work and $A+B+C=180$

Can you offer us some details ? Please !

it's too easy!

everybody knows the solution.

do you think it's correct girino?

hello welcome on candid camera!

Girino, you found at least one, but you don't prove it is singlely !

Oh, not again!!! :) http://www.mathlinks.ro/Forum/viewtopic.php?t=116742

[hide="to girino"][quote="girino"]b+c=2(R+r)=$2\left(\frac{abc}{4S}+\frac{2S}{a+b+c}\right)$

and with the substitution $\frac{bc}{2}=S$

comparing last two terms we obtain an identity[/quote]
girino, You assume that $A=90^{o}$ and you prove that $b+c=2(R+r)$
The problem asks for the inverse $b+c=2(R+r) \Rightarrow A=90^{o}$
[/hide]
[hide="My approach"]
[color=brown]If we know that $\angle A$ is not acute, then we have the result.
But if we have not such an information, we can't be sure if A is right angle
That is, there are acute angles A, which satisfy $b+c=2(R+r)$[/color]

$b+c = 2(R+r)$

$b+c-a = 2R+2r-a$

$2(s-a) = 2R+2r-a$

$\boxed{2(s-a)-2r = 2R-a}\ \ (1)$

We know that $2R\geq a$, so we have $2R-a\geq 0$

$\hline$

$\blacktriangleright$ If the problem said that $A\geq 90$, then we would say

$45^{o}\leq \frac{A}{2}<90\Rightarrow \tan\frac{A}{2}\geq 1\Rightarrow \frac{r}{s-a}\geq 1 \Rightarrow r\geq s-a\Rightarrow (s-a)-r\leq 0$

So, if we knew that $\angle A$ is not acute, then we would easy solve the problem, because in $(1)$ we have

First part $\leq 0$
Second part $\geq 0$

The only possibility such that we have equality is $\boxed{s-a=r}\ \wedge\ \boxed{2R=a}$

Each of the boxed equations means that $A=90^{o}$

$\hline$

$\blacktriangleright$ The problem doesn't say anything about the range of $A$, so we can't be sure

In fact, I found some triangles such that $b+c = 2(R+r)$ holds, though $A$ is acute.

I didn't prove it (yet)

I just took some examples in an Excel Sheet, and I saw that we can have solution

For example, if $b=2,c=3$ and $a$ is about $1.19882241220556$, then we have $b+c = 2(R+r)$, but the triangle is not right

You can try these numbers (Heron formula to get the area, and from this we get r and R)
 [/hide]

So, I think that the problem is wrong

[quote="pontios"]
So, I think that the problem is [b]wrong[/b][/quote]
Fixing $a=5$ and $b=4$ it is obvious that $F(c)=b+c-2(R+r)$ is a continuos function when $c \in (1,9)$. My geom program C.a.R. says that $F(8,09)*F(8.1)<0$ so there is some c in this interval where $F(c)=0$. [b]So the inverse theoreme is not true[/b]!

sorry,you are right. what is the range of A? thanks

[quote="pontios"]The problem doesn't say anything about the [i]range[/i] of  Α[/quote]
[quote="girino"]what is the [i]range[/i] of A?[/quote]

with [i][b]range[/b][/i], I mean the a set with [u]all[/u] the possible values of A.

For example, if an angle $\theta$ takes all the values between $30^{o}$ and $60^{o}$, then the range of $\theta$ is $30^{o}<\theta<60^{o}$
Or simply, the interval $(30,60)$

[color=darkblue]Is evidently the implication $A=90\Longrightarrow b+c=2(R+r)\ .$ Indeed, $2p-a=a+2(p-a)\ .$

I'll prove that $b+c=2(R+r)\Longleftrightarrow$ $A=90^{\circ}$ or exists $x>0$ so that $\{\begin{array}{c}\tan\frac{A}{2}=x\ ,\ \tan\frac{B}{2}=y\ ,\ \tan\frac{C}{2}=z\\\\ y+z=\frac{4}{1+3x}\ ,\ y\cdot z=\frac{1-x}{1+3x}\end{array}\ .$

[b]Proof.[/b] Is abviously $A=90\Longrightarrow b+c=2(R+r)\ .$ Indeed, $2p-a=a+2(p-a)\ .$ Thus, can suppose $A\ne 90\ .$

$\{\begin{array}{c}\boxed{\ b+c=2(R+r)\ }\\\\ b=2R\sin B\ ,\ c=2R\sin C\end{array}$ $\Longleftrightarrow$ $\{\begin{array}{c}\boxed{\ \sin B+\sin C=1+\frac{r}{R}\ }\\\\ \cos A+\cos B+\cos C=1+\frac{r}{R}\end{array}$ $\Longleftrightarrow$ $\{\begin{array}{c}\boxed{\ (\sin B-\cos B)+(\sin C-\cos C)=\cos A\ }\\\\ \sin x-\cos x=\sqrt 2\cdot\sin (x-45)\end{array}$ $\Longleftrightarrow$

$\{\begin{array}{c}\boxed{\ \sqrt 2\cdot [\sin(B-45)+\sin (C-45)]=\cos A\ }\\\\ \sin x+\sin y=2\cdot\sin \frac{x+y}{2}\cos \frac{x-y}{2}\\\\ \cos x=\sin (90-x)\end{array}$ $\Longleftrightarrow$ $\{\begin{array}{c}\boxed{\ 2\sqrt 2\cdot\sin\frac{B+C-90}{2}\cos\frac{B-C}{2}=\sin (90-A)\ }\\\\ B+C-90=90-A\\\\ \sin x=2\cdot\sin\frac{x}{2}\cos\frac{x}{2}\end{array}$ $\Longleftrightarrow$

$\{\begin{array}{c}\boxed{\ 2\sqrt 2\cdot\sin\frac{90-A}{2}\cos\frac{B-C}{2}=2\cdot\sin\frac{90-A}{2}\cos\frac{90-A}{2}\ }\\\\ 90-A=(B+C)-90\end{array}$ $\Longleftrightarrow$ $\{\begin{array}{c}\boxed{\ \sqrt 2\cdot\cos\frac{B-C}{2}=\cos (\frac{B+C}{2}-45)\ }\\\\ \cos (x-45)=\frac{\sqrt 2}{2}\cdot (\cos x+\sin x)\end{array}$  $\Longleftrightarrow$

$\{\begin{array}{c}\boxed{\ 2\cdot\cos\frac{B-C}{2}=\cos\frac{B+C}{2}+\sin\frac{B+C}{2}\ }\\\\ \tan\frac{A}{2}=x\ ,\ \tan \frac{B}{2}=y\ ,\ \tan\frac{C}{2}=z\\\\ x(y+z)+yz=1\end{array}$ $\Longleftrightarrow$ $\{\begin{array}{c}\boxed{\ 2(1+yz)=1-yz+y+z\ }\\\\ x(y+z)+yz=1\\\\ \{x,y,z\}\subset (0,\infty )\end{array}$ $\Longleftrightarrow$ $\underline{\overline{\|\begin{array}{c}x>0\ ,\ \tan\frac{A}{2}=x\\\\ \tan\frac{B}{2}=y\ ,\ \tan\frac{C}{2}=z\\\\ y+z=\frac{4}{1+3x}\ ,\ yz=\frac{1-x}{1+3x}\end{array}\|}}\mathrm{\ \ \ q.e.d.}$[/color]

[color=#006699][b]Virgil Nicula[/b][/color], congratulations for the nice result!     :first:

I was working to find a formula about the case $A\neq 90^{o}$, but I could not.

So much this solution what the  [url=http://www.mathlinks.ro/Forum/viewtopic.php?p=666482#666482][b]other[/b][/url] are really awesome :coolspeak:


I have two cubes such that, on each cube, three faces are painted red and three faces are painted white. If I roll each of the cubes once, what is the probability that they will land such that there is one red face and one white face up?

You could also have said that there are 2C1 ways to pick one of the dice to have a red face, and then multiplied by 1/2.

[hide="Alternative Solution"]
There are only four possibilites, so you could list them and find:

R R
R W
W R
W W

We see that $ 2$ out of the $ 4$ possible outcomes are successful, thus the probability is $ \frac12$.
[/hide]

@PowerOfPi: But that only works because each case is weighted evenly;probability of rolling red = probability of rolling white.


1.	When Francis the Frog, hops on his left foot, his hop is 2 feet long and when he hops on his right foot, then his hop is 4 feet long. If Francis hops using both his feet , then his hop is 7 feet long. What is the smallest number of hops that Francis must make to travel exactly 1000 feet?

2.	I like to spend all my $ 41 to buy different types of pens that cost$ 2, $ 3 and$ 4 respectively. If I want to buy at least 1 pen of each type, what is the maximum number of pens I can buy?

3.	One year in December, there were5 Mondays, which day/s of the week would not appear in this month also 5 times?

4.	Victor will write the list of consecutive integers, starting with 1, at the speed of 5 digits per second. What will be the last digit he will write on his list of the end of 1 minute?

5.	A journal is constructed by stapling 25 sheets of short bond paper together down the middle and then folding into half. Starting with the front page, the pages are numbered consecutively from 1 to 100. A certain page is numbered 15. If the journal is then unstapled, three other numbers will appear on this same sheet of paper. Find these three numbers.

6.	From noon until midnight, Kevin the cat sleeps under a tree. From midnight until noon, he is wake looking for food. There is a note on that tree which says: “ Three hours ago, Kevin was doing the same thing that he will be doing in two hours.” How many hours out of the 24 hours is the note true?

7.	How many zeroes are there in the quotient when 111…1111 (2007 times) is divided by 3?

8.	The odometer of the car shows 17,971km . Jireh, the driver noticed that this number is a palindrome. Exactly 16 hours later, Jireh saw his 12th palindromic reading. How many km/hour was the car’s average speed those 16 hours?

The first 3 solutions.
[hide="Number 1"]
Because Fracis' maximum jump is $ 7$ feet, he should hop as far as he can using both feet. This takes him $ 994$ feet using $ 142$ hops. This takes him $ 6$ feet away from the $ 1000$ foot mark. Now if he hops once with his left foot and once with his right, he jumps $ 6$ feet meaning that he has jumped a total of $ 1000$ feet using $ \fbox{144}$ jumps.
[/hide]

[hide="Number 2"]
If you want to by at least $ 1$ pen of each type you have already spent $ 2 \plus{} 3 \plus{} 4 \equal{} 9$ dollars. This leaves $ 32$ dollars left. If you want to by the maximum amount of pens, you should spend the rest of the money on $ 2$ dollar pens. This means you have bought $ \fbox{19}$ pens.
 [/hide]

[hide="Number 3"]
If December has $ 5$ Mondays, that means that the first day of the month must either be a Saturday, Sunday, or Monday.
If December begins on a Saturday, then, Tuesday, Wednesday, Thursday,  and Friday have $ 4$ days.
If December begins on a Sunday, then, Saturday, Wednesday, Thursday,  and Friday have $ 4$ days.
If December begins on a Monday, then, Saturday, Sunday, Thursday,  and Friday have $ 4$ days.
The only days that always have $ 4$ days are [b]Thursday and Friday[/b].
[/hide]

[hide="Number 4"]
In 1 minute, Victor will write 300 digits. The numbers from 1 to 9 take up 9 digits, so he still has 291 to go. The numbers from 10 to 99 take up 180 digits, so he still has 111 to go. $ \frac{111}{3}\equal{}37$, so he is able to write 37 two digit numbers, meaning the last number he writes is 136, and so the last digit he writes is 6.[/hide]

[hide="#4"] First you subtract the 1 digit integers from 5*60=300 and you get 291 digits left. There are 90 2-digit integers, multiplying that by 2 and subtracting we get 291-180=111. Dividing 111 by 3 we get 37. Our answer is then the units digit of the 37th 3-digit number, so our answer is 6.[/hide]

[hide="#7"] Since there is a 0 every 3 digits there are 2007/3=669 zero's [/hide]

Just three more to go. Thanks to those who provided the correct answers.

5

6

7 The answer here is 668 zeroes only.

[hide="Number 5"]
The next pages are $ 15 \plus{} 1 \equal{} \fbox{16}$,  $ 100 \minus{} 15 \equal{} \fbox{85}$,  and $ (100\minus{}15) \plus{} 1 \equal{} \fbox{86}$.
It is hard for me to explain.
[/hide]

[hide="number 6"]
Ok lets say the thing that keving is doing is sleeping... the first time that works is 2:00 all the way until 9:00. So that is 8 hours. That is the same as looking for food so the answer is $ 2\times8\equal{}\boxed{16}$
[/hide]


Let $ X$ and $ Y$ are two topology spaces. map $ f: X\to Y$.
The following propositions are equivalent.
1, $ f$ is a continuous map.
2,for any subset $ A\subset X$, we have $ f(\bar{A})\subset \overline{f(A)}$.
3, for any subset $ B\subset Y$, we have $ f^{\minus{}1}(\bar{B})\supset \overline{f^{\minus{}1}(B)}$.

How to understand 2 and 3 ?
Thanks

[quote="JRav"]I'm assuming the set with the bar means closure, right?  Then the second part is telling you that if a function is continuous, then the image of the closure of any set is contained in the closure of the image of the set, while the third one tells you that the closure of the preimage of a set is contained in the preimage of the closure.

As a hint, remember that since $ f$ is continuous, the preimage of any closed set is also closed.[/quote]

Yes , it is closure.
I can not remember them.
How to deepen the understanding?
Thanks

You can imagine the points in the topological closure of some set A the point which "are not to far from A" (they are aderent!)
so you can say that:

2) points not so far from the set A are mapped to points not so far from the image of A
3) points not so far from the set B come from points not so far from the preimage of B

better?

Here's another piece of information you might want to know: in general, if $ A$ is a subset of the range, $ f(f^{\minus{}1}(A))\subseteq A$ and if $ B$ is a subset of the domain, $ B\subseteq f^{\minus{}1}(f(B))$.


Does anyone have a list of probable answers that they can post?

Did anyone else get $ 160$ for number 10?

Edit: nevermind

Well, for number 10, shouldn't it be divisible by 9?...

And a couple people for number 9 got 29 as an answer.

Just adding what I've heard.

No, a path of length ten can be achieved.

Oh, you're right... I misread the problem. Hmm, English is a good skill to have on the AIME (or the ability to count points).

[quote="hypo3400"]Did anyone else get 485 for #12?[/quote]
Nope.

I brute forced #12 and got 364 or something like that, and I just did it again this morning and got 310. Oh well...

[url=http://www.unl.edu/amc/e-exams/e7-aime/e7-1-aimearchive/2008-aa/08-2-AIME-Answers.shtml]Official Answers[/url]

The answers Hamster1800 posted are all right.


find the volume of the solid obtained by rotating the region bounded by the given curves about the specified line. Sketch the region, the solid, and a typical disk or washer.

I drew the graphs and sketched them already.

y^=x, x= 2y,  about the y-axis

then i used the formula Vk= pie(r)^2 h

the answer is 64pie/15

all i need is too see how to do it the problem

i figured it out, i didn't know that you had to you use the range of y when you move the area to the y-axis


Think your PC is secure...check this site out then:

http://forums.net-integration.net/

every one of you should sign up, download HijackThis (google it if you want) and post a logfile there to be analyzed. Then download Ad-Aware, Spybot Search and Destroy, and SpyWareBlaster

Hijackthis isn't enough to ensure PC security..... :spider:
You see ....there are plenty of such spiders in the WORLD WIDE WEB if there's one in a smiley which is approx. one square inch.... :D

[quote="MithsApprentice"]Moving to Support.

Why was a guest able to post?[/quote]Have you checked the date of that post? :) I don't remember but perhaps this was moved from some other forum before the merge last year, and ended up in the Games and Fun Factory forum.


geometry
ratio
area of a triangle
geometry proposed

Given a regular pentagon with a side of $a$,let $F$ be a point of intersection of the diagonals $AC$ and $BE$.
Find the area of a triangle $ABF$.

I've got ugly solution  :D :
We can see (using some angles) that triangles $BCE$ and $FBC$ are similar. Also we can see that $|EF|=|CF|=a$. Now use this similarity:
$\frac{|EB|}{|BC|}=\frac{|BC|}{|BF|}$ => $\frac{a+|FB|}{a}=\frac{a}{|FB|}$ =>
=> $|FB|=\frac{\sqrt{5}-1}{2}a$.
From this we know that triangle $ABE$ has sides $a,a,\frac{\sqrt{5}+1}{2}a$ so we can compute it's area by Heron's formula. Also We from these ratios we know that $\frac{S_{ABE}}{S_{ABF}}=\frac{\sqrt{5}+1}{\sqrt{5}-1}$ so we can compute it. But I hope that it has nicer solution, because this one was absolutely straighforward :)

Thank you for your reply,ondrob.

You can remark $\angle ABF$.

kunny


Someone needs to post here...I don't like friends dying... :(

hmm.... what should I say that would start another spam war?

We should plot first...Can I be Supreme Spam Commander?

[size=200]Super war of the teletubbies[/size]

[size=150]Who will win?  Gauss or tinytim?  DUN DUN DUN.[/size]

[quote="tinytim"][quote="dynamo729"]Uh oh tinytim adopted gauss' avatar[/quote]

For your information, gauss1181 stole mine, I didn't get it from him. I had it first.[/quote]

Gauss is a girl.

[quote="pianoforte"]mewto is a girl

inside[/quote]

What exactly was the point of that 2nd part?

Morse code for: Do I usually have a point?

Ok let's start a spam war by thinking about who will win the French Open Final. Soderling vs. Del Potro/Federer?

Remember, Del Potro is up a set (currently).

Oh too late...It's going to be Robin vs. Roger.  :o

No it's obviously gonna be Hillary Clinton vs. Ron Paul.


group theory
superior algebra
superior algebra unsolved

Let $ p$ be an odd prime, and let $ z$ be an integer such that $ [z]_p$, i.e., the residue class modulo $ p$ generates the group $ (\mathbb Z/ p)^*.$ Consider the $ p$ numbers $ z_i: \equal{}z\plus{}ip$ for $ 0 \leq i < p;$
they all have the same residueclass modulo $ p$, but the residue classes $ [z_i]_{p^2}$ are different.
(i) Show that out of  $ p$ residue classes there are $ p\minus{}1$ which generates the cyclic group $ (\mathbb Z/p^2)^*.$

(ii) Show that if the residueclass $ [z]_{p^2}$ generates the group $ (Z/p^2)^*$, then the residue class $ [z]_{p^\nu}$ generates the group  $ (\mathbb Z/p^{\nu})$ for all $ \nu.$

This sounds like an exercise/lemma on the way to prove that $ (\mathbb{Z} / p^n \mathbb{Z})^\times$ is cyclic. Is this the case, or perhaps you already proved that this group is cyclic, and this is just an exercise on finding generators? Also, do you know any group theory? Please provide some context... and what have you tried so far?

You can find a sketch of an elementary proof in my sci.math post here
http://google.com/groups?selm=y8zljw6ick0.fsf%40nestle.csail.mit.edu

but this is not the same question you show that it is cyclic and my question is different.


trigonometry
induction
inequalities unsolved
inequalities

Define max m and min M?

not the min/max functions...   i mean, your definition of m implies it is a singleton.

He mean that we need to determine the maximal value of $m$ over all possible sets $(x_1,...,x_n)$.

WoW! Coooool!

1. We are to notice that $\max m$ attains only if $x_1=x_2+\frac{1}{x_1}=x_3+\frac{1}{x_2}=...=\frac{1}{x_n}$ :!: . Indeed, if it is not true then we can easily modify sequence $\{x_i\}$ in order to increase minimum value $\min\left(x_1,x_2+\frac{1}{x_1},...,x_n+\frac{1}{x_{n-1}},\frac{1}{x_n}\right)$. Just suppose that two of these values are different, then we can increase minimal of them. For example, if minimum is $x_2+\frac{1}{x_1}$ and $x_3+\frac{1}{x_2}>x_2+\frac{1}{x_1}$, then we can slightly increase $x_2$ in order to increase minimal value. Note that it is possible there are more than one minimums, then we should increase them all.

2. Suppose :!: holds. Let $x_1=z+\frac{1}{z}$, then we can easily prove by induction, that $x_k=\frac{z^{2k+2}-1}{z(z^{2k}-1)}$. So $z+\frac{1}{z}=x_1=\frac{1}{x_n}=\frac{z(z^{2n}-1)}{z^{2n+2}-1}$. Note, that $z\neq 1$ (actually, you need to check it. Hint: $x_n=\frac{n}{n-1}$ for $z=1$). But then $z^{2n+4}=1$. Therefore $z=\exp\left(\frac{\pi ki}{n+2}\right)$. It follows $x_1=2\cos \frac{\pi k}{n+2}$. Put $k=1$ to obtain the maximum.


geometry
3D geometry
arithmetic sequence
Irrational numbers

Show that the cube roots of three distinct primes cannot be terms in an arithmetic progression.

Assume that $p<q<r$ are primes with $2q^3=p^3+q^3=(p+q)(p^2-pr+r^2)$.
Obviously none of these is $=2$. By this $p+q$ is even and we get that one of the following cases happens:

a) $p+r=2$: nonsense.
b) $p+r=2q$: then $p,q,r$ is an arithmetic progression and $4(p^3+r^3) = (2q)^3 = (p+r)^3 \iff p^3+r^3 = pr(p+r) \iff (p-r)^2 = 0$, impossible.
c) $p+r=2q^2$: then $p^2-pr+r^2=q$ and thus $(p+r)^2 > p+r = 2q(p^2-pr+r^2) > 4p^2-4pr+4r^2$. This yields $2pr > p^2+r^2$, nonsense.
d) $p+r=2q^3$: then $4=4p^2-4pr+4r^2=(2p-r)^2+3r^2$, wrong by already $3r^2>4$.

Your solution is very nice.
Mine is:
Suppose it is true.
So, we can have $ \sqrt [  3 ] {p_1} \equal{}a$, $ \sqrt [ 3] {p_2} \equal{}a \plus{}m\cdot d$,
 $ \sqrt [ 3] {p_3} \equal{}a\plus{}n \cdot d$,
 where $ p_1,p_2, p_3$  three different primes, and  $ a,d \in N$ .
After eliminaton of $ a$ and $ d$, we have
$ m \cdot \sqrt [ 3 ] {p_3}  \minus{} n \cdot  \sqrt [  3 ] {p_2} \equal{} (m \minus{} n )\cdot \sqrt [   3 ] {p_1}$,
the cube of which is
$ m^3\cdot p_3 \minus{} n^3 \cdot p_2 \minus{} 3 m\cdot n \sqrt [  3 ] {p_2 \cdot p_3} (m\cdot \sqrt [  3 ] {p_3}  \minus{}  n \cdot \sqrt [  3 ] {p_2})\equal{} (m \minus{} n )^3 \cdot p_1$.
Finally,
$ \sqrt [  3 ] {p_1 \cdot p_2 \cdot p_3} \equal{}
\frac{m^3 \cdot p_1 \minus{} n^3 \cdot p_2 \minus{} (m \minus{} n )^3 \cdot p_1}{ 3 \cdot m \cdot n ( m \minus{} n )}$,
so contradiction, since  $ \sqrt [  3 ] {p_1 \cdot p_2 \cdot p_3}$ is irrational.


This well-known fact goes by the name of the [url=http://en.wikipedia.org/wiki/Birthday_problem]birthday paradox[/url] and is responsible for the power of the [url=http://en.wikipedia.org/wiki/Birthday_attack]birthday attack[/url].

I didn't realize there was a Wiki article on this.

Does the birthday attack affect similar types of problems (especially in competitions)?

Related problem:
A family has two children, one younger, one older. One (at least) of the children is a girl; what is (more likely) the gender of the other child?

Even better related problem (which everyone has already heard):
A ball is placed under one of three cups, which are shuffled around so that you cannot tell what cup the ball is under. The con-artist (cup shuffler) has you place your hand on a cup of your choice, but you do not turn it over. He turns over one of the remaining cups; it has nothing underneath. Now, the option: you can either flip over the cup your hand is on, or flip over the other unflipped cup. Which choice is better (assuming you want to find the ball)?

-Eh... I just discovered this question was just posted a couple topics down... apologies

[quote="7h3.D3m0n.117"]What is the probability that a class of 23 contains at least two students with the same birthday? (Ignore leap-years)

(Hint - the answer is not what you may think!)[/quote]

Hello
Probability of at least two share their birthday=$ 1\minus{}\frac{365!}{342!{365}^{23}}$
                                                             =$ 1\minus{}0.49$
                                                              =$ 0.51$
more than 50% .
Thank u.


linear algebra
matrix
linear algebra unsolved

Who can tell me what important properties the matrix I-A*inv(A'*A)*A' has?

A' is the transpose of A. A is an m x n matrix.
inv(B) is the inverse of B.
I is the m x m identity matrix.

I know this is an very important matrix in the scientific research of different disciplines. There must be something special with it.

The expression is defined only when $ \mathrm{rank}(A) \equal{} n$ (otherwise, $ A'A$ is singular). Then $ (A'A)^{\minus{}1}A'$ equals $ A^\plus{}$, the [i]pseudoinverse [/i]of $ A$ (see [url]http://en.wikipedia.org/wiki/Moore-Penrose_pseudoinverse[/url] for details). So $ A(A'A)^{\minus{}1}A'$ is the projection on the image of $ A$ (=column space of $ A$). Finally, $ I \minus{} A(A'A)^{\minus{}1}A'$ is the projection on the orthogonal complement to the image of $ A$.


Um, order doesn't matter in sets, so how do you define the previous two terms?

And set N isn't a valid set since it includes 1 twice.

For the first question, this proof can be done by without naming all the elements of the sets(which is impossible) just take the few cases and examine them. You should see why it's impossible to have any integer factor, say k, greater than 1.

The question is fixed so the second question is answered. For the previous two terms, just ignore how 1 came from and also 2.

Just:

$a_1 = 1$
$a_2 = 2$

are given.

$a_3 = 3$
$a_4 = 5$
$a_5 = 8$
$a_6 = 13$

But if order doesn't matter in sets you can't define nonadjacent.

Order matters. The reason order matter is that the new term is summed up by the previous two terms.

Does this make sense? I know Fibonnaci sequence is not so getting started but this proof is not that hard as it looks...

Oh it's Sunday. Does that mean I missed the round?

It says the answers need to be turned in by Saturday, not Sunday.

Yes, and NEXT Saturday.

Not the 1/2 one. 1/9 one. :)

At the end of question 1, where is says, "prove that there exists no integer greater than 1 which is a divisor of any kinds of $n$", what does it mean by "any kind of $n$"?

EDIT: does it mean, "prove that the elements of $n$ have no common factor greater than one"?

Any kinds of sets of n.

n can be:

{1,3,8}

{1,5,13}

See they're different but they're both different set of n. :)

OK, so it's asking to prove that there is no integer greater than 1 which is a common factor of all the elements of $n$, for every possible $n$? That seems too easy, so I'm not sure if I understand it right.

Ha. Yea, it maybe easy. :D

But you have to answer in all cases that I consider happen.

 ;) Plus, I'm grading the paper so just do your best. :)

"... , the order in which we list the elements [of a set] does not matter; ..."
~AoPS Volume 1 Pg.326

Since you've admitted that the Fibonacci sequence is involved, how about we say N is the set of all Fibonacci numbers?

Send me the answers by TOMORROW!!

If no one sends me the answer, alan automatically becomes a winner.

[quote="Silverfalcon"]Question 1:

If n is the set three randomly picked nonadjacent integers (meaning you can pick 1, 2, 8 but not 1,2,3) result from the set N {1,2,3,5...} where the numbers on the set N is made by the sums of two previous terms, prove that there exists no integer greater than 1 which is a divisor of any kinds of n.
[/quote]

This wants you to prove that there is no integer greater than one which is a divisor of all possible elements of set n right?

If it wants you to prove that for any set n, there is no common divisor of all of n's elements, then n could equal {2,8,34}, and 2 could divide it.

P.S. Rule two implies that the answers will be accepted iff they are sent on Saturday.

I don't think I quite understood you.

So, you're saying 2 is the integer > 1 that divides all the sets?

I thought I already told that there exists no integer.

[quote]This wants you to prove that there is no integer greater than one which is a divisor of all possible elements of set n right? [/quote]

Yes.

I deleted RC-7th answer because it seems pretty close to the answer but I want the full proof of it.

Silverfalcon

Repost of the question #2:

Prove that the adjoining of the convex triangle and convex quadrilateral is not ALWAYS convex nor concave, meaning it differs from case to case.


inequalities
geometry
inradius
inequalities unsolved

I think It is very difficult and i haven't had a solution

This problem is a directly consequence of $ \textbf{Turkish National Olympiad 2005 problem 5}$ which is

$ a,b,c$ are side lengths of a triangle and $ r$ is the inradius of that triangle.

Prove that$ : \quad \frac {1}{4r^2} \geq \frac {1}{a^2} \plus{} \frac {1}{b^2} \plus{} \frac {1}{c^2}$

$ \frac {1}{4r^2} \geq \frac {1}{a^2} \plus{} \frac {1}{b^2} \plus{} \frac {1}{c^2} \; \Longleftrightarrow \; \frac {1}{(x \plus{} y)^2} \plus{} \frac {1}{(y \plus{} z)^2} \plus{} \frac {1}{(z \plus{} x)^2} \leq \frac {x \plus{} y \plus{} z}{4xyz}$ where

$ a \equal{} y \plus{} z \; , \; b \equal{} z \plus{} x \; ,\; c \equal{} x \plus{} y$

The last one is not so hard by using a well-known lemma that is $ (a \plus{} b)^2 \geq 4ab$  :roll:


[hide="Answer"]We have $499$ numbers less than $1000$ divisible by $2$, $167$ divisible by $3$, and $67$ divisible by $5$, but $2$, $3$, $5$ are counted among the primes already and $1$ is not included under any of the categories, so the answer is $999-168-499-167-67+3-1=100\Rightarrow \boxed{A}$.[/hide]

Wait...wouldn't that count numbers like 6 (divisble by 2 and 3) twice?

Well, no, I didn't really explain that, but I didn't count the overlaps.

[hide]$499$ are divisible by $2$ and any other factor. $167$ are divisible by $3$ and any other factor besides $2$. $67$ are divisible by $5$ and any other factor besides $2, 3$.

$168$ are prime.

$1$ is not prime and is not divisible by $2, 3, or 5,$ thus it is not included in $499 + 167+ 67$.

$1000 - (499 + 167 + 67) = 267 =$ number of integers not divisible by $2, 3, 5$, including primes and $1$, which is not prime and is not composite. We must subtract the primes and 1 as they are not composite. We must substract $168 - 3$ because $2, 3, 5$ were already subtracted in the previous equation because they of course are divisible by $2, 3, 5$ respectively.

Final equation is:

$999 - (499 + 167 + 67) - 165 - 1 = \boxed{A = 100}$[/hide]

Oh I get it now. That was  a stupid misunderstanding :blush:

how do u get 67 that are divisible by 5 and not 2 or 3?

o  its basically PIE (principle of inclusion-exculsion)

Yeah, also $A \cup B = A + B - A \cap B$

[quote=chess64]Call a number "prime-looking" if it is composite but not divisible by 2, 3, or 5. The three smallest prime-looking numbers are 49, 77, and 91. There are 168 prime numbers less than 1000. How many prime-looking numbers are there less than 1000?

$ \textbf{(A)}\ 100 \qquad \textbf{(B)}\ 102 \qquad \textbf{(C)}\ 104 \qquad \textbf{(D)}\ 106 \qquad \textbf{(E)}\ 108$[/quote]

This problem is a simple application of PIE and complementary probability. Furthermore, [i][b]thank you MAA for telling us that there are $168$ prime numbers less than $1000$  :rotfl: [/b][/i]

[hide=Number-Theoretic Solution without PIE]
Call a positive integer [i]good[/i] if it is not divisible by $2$, $3$, or $5$.

First, we count the number of good integers in $[1,990]$.Out of these integers, $\frac12$ of them are not divisible by $2$. CRT then guarantees that $\frac23$ of the remaining integers are not divisible by $3$. Using CRT again, we find that $\frac45$ of the remaining integers are not divisible by $5$. Therefore, $990\cdot\frac12\cdot\frac23\cdot\frac45=264$ such integers are good.

Looking at integers from $991$ to $999$, we see that only $991$ and $997$ are good, so $266$ positive integers less than $1000$ are good.

Since there are $168-3=165$ good primes, and $1$ is also a good number, there must be $266 - 165 - 1 = \boxed{\textbf{(A) } 100}$ prime-looking numbers.


Hello,

Let a, b, c be positive integers such as :
$ a\plus{}b<c\plus{}d$ and $ (a\plus{}b)(c\plus{}d)<ab\plus{}cd$ and $ (a\plus{}b)cd<ab(c\plus{}d)$

Prove that at least one of those propositions is wrong

Mhdi

Consider the polynomial  $ y \equal{} (x \plus{} a)(x \plus{} b)(x \minus{} c)(x \minus{} d)$

Expanding,
$ y \equal{} x^4 \plus{} (a \plus{} b \minus{} c \minus{} d)x^3 \plus{} (ab \plus{} cd \minus{} ac \minus{} ad \minus{} bc \minus{} bd)x^2 \plus{} (abc \plus{} abd \minus{} acd \minus{} bcd)x \plus{} abcd$

By the given inequalities, all the coefficients are positive; therefore, by Descartes' rule of signs, the polynomial's real roots are all negative.  But this is a contradiction, since both $ c$ and $ d$ are given to be positive and are roots of the polynomial.

solution inspired by a similar problem on USAMTS last year :)

I think he means the polynomial $ y\equal{}(x\minus{}a)(x\minus{}b)(x\plus{}c)(x\plus{}d)$, which would make it work.

oops...

Well, I suppose I did intend $ y\equal{}(x\minus{}a)(x\minus{}b)(x\plus{}c)(x\plus{}d)$, but the polynomial I gave would work if I had expanded it correctly (the coefficient on the $ x$ term is exactly opposite of what I claimed). Then the rest of my proof should be as follows: from the given inequalities, the coefficients alternate between positive and negative, so by descartes rule of signs there are no negative real zeros; which is contradiction, since both $ \minus{}a$ and $ \minus{}b$ are zeros of the polynomial.

Lets say that all three inequalities are true
Multiply first two inequalities yields
$ ab\plus{}cd>(a\plus{}b)^2 \geq 4ab$  $ \implies$  $ \boxed{cd>3ab}$ $ (1)$
Multiply last two inequalities yields
$ (ab\plus{}cd)ab>(a\plus{}b)^2cd \geq 4abcd$  $ \implies$ $ \boxed{ab>3cd}$ $ (2)$

and finally from $ (1)$ and $ (2)$ we got $ cd>3ab>9cd$ contradiction...


limit
combinatorics unsolved
combinatorics

Prove that

              \[ \displaystyle\lim_{n\to\infty}\displaystyle\sum_{i\equal{}o}^{n}\sqrt[3n]{(\binom{3n}{3i})}\equal{}2\]

Sorry. :D

        \[ \lim_{n\to\infty}\displaystyle \sqrt [3n]{\sum_{i \equal{} o}^{n}\binom{3n}{3i}}  \equal{} 2\]


inequalities
geometry
incenter
trigonometry
inradius
perimeter
cyclic quadrilateral

Let $P$, $Q$, and $R$ be the points where the incircle of a triangle $ABC$ touches the sides $AB$, $BC$, and $CA$, respectively.
Prove the inequality $\frac{BC} {PQ} + \frac{CA} {QR} + \frac{AB} {RP} \geq 6$.

are you absolutely sure about the letters pierre, cuz they don't seem to be symetrical :?

okay, i've solved it too. i just didn't want to get into computations without being sure about the statement.

let's compute $PQ$. Let $I$ be the incenter, then $APIR$ and $BPIQ$ are cyclic quadrilaterals, so $\angle QPI=\angle IBQ = \angle B /2$ and $\angle IPR= \angle IAR = \angle A/2$, so $\angle QPR = \displaystyle  \frac {\angle A+\angle C}2 =\frac \pi 2 - \frac { \angle B} 2$.
So, using the Sines Law in the triangle $PQR$ we get $PQ = 2r \sin \displaystyle \frac \pi 2 - \frac { \angle B} 2 = 2r \cos \frac {\angle B}2$, where $r$ is the inradius of the triangle $ABC$.
Thus the inequality becomes
\[ \sum \frac a{ 2r\cos \frac {\angle B}2 }\geq 6 \ \Leftrightarrow \sum \frac a{\cos \frac {\angle B}2 } \geq 12r \quad (1)\]
But
\[\displaystyle \sum \frac a{\cos \frac {\angle B}2} \geq 3 \sqrt[3] { \frac {abc}{ \cos \frac {\angle A}2 \cos \frac {\angle B}2 \cos \frac {\angle C}2 }} \quad (2) \]  so we must prove that
\[{ abc \geq 4^3\cdot  r^3 \cos \frac {\angle A}2 \cos \frac {\angle B}2 \cos \frac {\angle C}2 } \]
\[{ 4Rrs \geq 4^3\cdot  r^3 \cos \frac {\angle A}2 \cos \frac {\angle B}2 \cos \frac {\angle C}2 } \]
\[ Rs \geq 16\cdot  r^2 \sqrt{ \frac { s^3(s-a)(s-b)(s-c)}{(abc)^2}} \]
\[ Rs \geq 16 \cdot  r^2 \frac {Ss}{4RS} \  \Leftrightarrow \ R^2 \geq 4\cdot  r^2 \] which is true by Euler's inequality (I used the relationships $abc=4RS = 4Rrs$, where $S,s$ are the area and semi-perimeter of the triangle $ABC$).

The  PIQB is  cyclic  quadrilateral  so  by  Ptolemy  theorem  we  have
[tex] a\cdot r = PQ\cdot IB   [/tex] or   [tex]  \frac {BC}{PQ} = \frac{IB}{r}[/tex] . So  its  enought  to  prove that  [tex] \Sigma{IA} \geq 6r[/tex]  which is  true  by Erdos-Mordell  theorem.

i forgot the paper i'll post my sol later

here is my solution:
we have
BC/PQ+CA/QR+AB/RP>=3(BC.CA.AB/PQ.QR.RP)^(1/3)
but: PQ=BIsinB=2BQsin(B/2)where I is the incenter of ABC
and similarly: QR=2CRsin(C/2); RP=2APsin(A/2).
so PQ.QR.RA=BQ.CR.AP.8sin(A/2)sin(B/2)sin(C/2)
but 8sin(A/2)sin(B/2)sin(C/2)<=1.(by AM-GM and jensen)
and BC.CA.AB=(BQ+CR)(CR+AP)(AP+BQ)>=8BQ.CR.AP
so BC.CA.AB/PQ.QR.RP>=8 and we are done.

actualy, this problem is too easy. :lol:


probability
counting
derangement
function
graph theory

In a 6 person class, each student chooses (randomly) a partner. What is the probability that at least one pair of students chooses each other? (note: this is from an AoPS class post-test or something, so is this allowed to be posted?)

So I tried counting the complement, and was like ... graph theory ...  => I am confused. :|

[hide="I think..."]
Each student can choose from the $5$ other students, so there are a total of $5^{6}$ different possible selection outcomes.

We can use PIE to correctly count the number of selection outcomes in which there is at least one pair of students who chose each other.

There are $\binom{6}{2}$ ways to choose two students who form the pair, and $5^{4}$ ways for the other students to choose.

But this double counts the cases where there are two pairs, of which there are $\binom{6}{2}\binom{4}{2}\times 5^{2}$ possible outcomes so we have to subtract that many.

But this means that the cases where there are three pairs aren't counted at all, so we have to add them back in; there are $\binom{6}{2}\binom{4}{2}\binom{2}{2}$ such outcomes.

So the total number of desired outcomes is equal to
\[\binom{6}{2}\times 5^{4}-\binom{6}{2}\times 5^{2}+\binom{6}{2}\binom{4}{2}\binom{2}{2}= 7215 \]
and the desired probability is equal to
\[\frac{7215}{5^{6}}\]
[/hide]

No -- a derangement is a permutation with no fixed points.  Here, we don't have permutations, just general functions from a set to itself, and we have both no fixed points and no cycles of size 2.

[i]Later edit[/i]:
Fraxia: you have made at least one error, I'm afraid.  Unfortunately, even accounting for this error, I can't reconcile your solution with my answer (which I've acquired by a computer search).  In particular, you've inclusioned-exclusioned wrong.  You really want $\frac{1}{2!}\binom{6}{2}\binom{4}{2}$ and $\frac{1}{3!}\binom{6}{2}\binom42\binom22$ as the factors to account for the double- and triple-counting.  Adjusting for this change, your new answer would be 8265 such possibilities; however, this is just over 100 smaller than I believe it should be.  Are there other adjustments to be made, or have I mis-programmed?
Also, your signature is wrong: it's Hobbes who says that line.  (Also, there's an interjection from Calvin in the middle of it.)

[i]Even later edit[/i]:
The answer, for those who care, is that there was something wrong with my program.  This is good, because the (slightly) fixed-up solution of Fraxia certainly [i]looks[/i] correct :-)
For those who are curious, the first few terms are (I hope) 0, 1, 6, 51, 580, 8265, ....


Two positive integers are chosen. The sum is revealed to logician A, and the sum of squares is revealed to logician B. Both A and B are given this information and the information contained in this sentence. The conversation between A and B goes as follows: B starts

B : "I can't tell what the two numbers are."
A : "I can't tell what the two numbers are."
B : "I can't tell what the two numbers are."
A : "I can't tell what the two numbers are."
B : "I can't tell what the two numbers are."
A : "I can't tell what the two numbers are."
B : "Now I can tell what the two numbers are."

What are the two numbers ?


Do you know is there any place where we can find solutions (or discussions) of problems that appeared in Vietnamese Mathscope magazine :?:

[quote="delegat"]Vietnamese [b]Mathscope[/b] magazine :?:[/quote]
What is that?  :maybe:

Please see:

[url]http://www.imo.org.yu/othercomp/Journ/mathscope.pdf[/url]

Ah, that is Mathematics and Young Magazine . I don't know , too  :( . But if you want know solution of some in them then you can post it on forum . I'll help you, if can  :)

[quote]Ah, that is Mathematics and Young Magazine . I don't know , too  . But if you want know solution of some in them then you can post it on forum . I'll help you, if can[/quote]

OK [b]N.T.TUAN[/b]  Thanks for help
I will post some of them but later That are really beautiful problems :)


Let $ a,b $ be two parallel lines . $ (O,R) $ tangents $ a,b $ at $ I,K $ . $ (O_1,R_1) $ externally tangents $ (O) $ and tangents $ a $ at $ A $ . $ (O_2,R_2) $ externally tangents $ (O) $ and $ (O_1) $ , tangents $ b $ at $ B $ . Prove that : $ R = 2\sqrt{R_1R_2} $

This is just Pythagoras, though I can only work it out when R_1 < R (so all three circles are between the two lines). But when R_1 > R, I seem to get a contradiction.

Am I the only one?  :?

I mean $ R > R_1 , R_2 $ .
  Can you show me a proof ?

You get $(R_1+R_2)^2=(2R-R_1-R_2)^2+(2\sqrt {R_1R}-2\sqrt{R_2R})^2$. I believe it shouldn't be hard to derive from here. Like al.M.V said, this is just Pythagoras applied to the triangle $O_1O_2M$, where $M$ is the intersection between $O_1A$ and the parallel through $O_2$ to $a$.

The inversion of pole $ A$ and power $ AI^2$ will transform the circles $ O$ and $ O_2$ into themselves, and the circle $ O_1$ into the line $ b$. From $ \triangle OO_1L$, seeing that $ O_1L \equal{} AI$, we get common tangent $ AI^2\equal{}4RR_1$, similarly $ KB^2\equal{}4RR_2$.
Seeing now that $ AN \equal{} KB\minus{}AI$ and $ NO_2\equal{}NB\minus{}BO_2\equal{}2R\minus{}R_2$, it follows that $ O_2A^2\equal{}O_2N^2\plus{}AN^2$. Next, the power of $ A$ w.r.t. circle $ O_2$ is $ O_2A^2\minus{}R^{2}_2\equal{}AI^2$, from last equality, after substitutions and calculations getting the required relation.

Best regards,
sunken rock


let $ M_1\equal{}\bigcup_{r\in[0,1]}\{m\plus{}r: m\in M\}$

is $ M_1$ measurable for every measurable $ M\subset[0,1]$ ?

Yes. A possible approach:
Write $ \displaystyle M_1 \equal{} \bigcup_{r \in (0,1)} \{m \plus{} r : m \in M \} \cup M \cup (M \plus{} 1)$
and try to rewrite the first object by using $ M$ as index.

How should I write $ \bigcup_{r \in (0,1)} \{m \plus{} r : m \in M \}$ ?
 :|

Try  $ \bigcup_{m \in M} \{m \plus{} r : r \in (0,1) \}$ !


AMC
AIME
USA(J)MO
USAMO
number theory
relatively prime

Is there a place where you can view past AMC and AIME tests?

for the AIME you can go to [url=http://http://www.kalva.demon.co.uk/aime.html]http://www.kalva.demon.co.uk/aime.html[/url] although some of the wording has been changed to avoid copyright problems

I might also add that the wording can be really annoying at times, and the answers may not be integers.  If they are in the form m/n, where m and n are relatively prime positive integers, the real AIME would probably have asked for m+n. :D

ooo thanks, but what about past amc tests?  Are the exact original tests for amc, aime, and usamo on the AMC site? because i cant find any.  Are they even open to the public?

You can order almost all past AMC/AIME/USAMO material from the AMC website.

They have a special practice AMC here:
http://www.unl.edu/amc/a-activities/a7-problems/problem81012archive.html


The lengths of two line segments are $ a$ units and $ b$ units respectively. Then the correct relation between them is:
$ \textbf{(A)}\ \frac{a\plus{}b}{2} > \sqrt{ab} \qquad\textbf{(B)}\ \frac{a\plus{}b}{2} < \sqrt{ab} \qquad\textbf{(C)}\ \frac{a\plus{}b}{2} \equal{} \sqrt{ab}\\
\textbf{(D)}\ \frac{a\plus{}b}{2} \leq \sqrt{ab} \qquad\textbf{(E)}\ \frac{a\plus{}b}{2} \geq \sqrt{ab}$


Determine x_n if x_0=3, x_1=0 and x_2=-1
x_(n+3)=4x_(n+2)-6x_(n+1)+4x_n for every n natural.

cheers! :D :D

I hope you're kiding or that you did't write the correct problem, since this one is trivial and is also quite ugly and without any ideas. Maybe only the fact that the attached equation has roots 2,1+i,1-i.

I think that the fact that :

x_n=5*2^(n-1)+(sqrt(2))^(n-2)*[cos(n*pi/3)-11*sin(n*pi/3)] scared me!!

cheers! :D :D


Original problem:

Find the smallest positive integer $ a$, so that $ 1971|50^n\plus{}a\times 23^n$ for odd $ n$.

**

I separated them out and did some algebra/congruence stuff to get $ 73x\minus{}23y\equal{}\minus{}2$, where $ a\equal{}73x\plus{}1, 23y\minus{}1$. How do I find the solution that minimizes a?

[hide]
easier way: 50^2 is congruent to 23^2 modulo 1971. Therefore, if we let n = 2k+1, 50*2500^k + a*(23^2)^k*23 = (50+23a)2500^k. This implies 50 + 23a is the smallest number such that 1971 divides 50+23a. [/hide]


[quote="sinajackson"]$a,b,c$ are positive real numbers such that $abc=1$. Prove that:

$(a+b+c)(\frac{b}{a}+\frac{a}{c}+\frac{c}{b})(\frac{b^{2}}{c}+\frac{c^{2}}{a}+\frac{a^{2}}{b})(\frac{b^{4}}{c}+\frac{c^{4}}{a}+\frac{a^{4}}{b})\geq (a^{2}+b^{2}+c^{2})^{4}$[/quote][hide]Since $abc=1$, then \[\frac{b}{a}+\frac{a}{c}+\frac{c}{b}=b^{2}c+a^{2}b+c^{2}a.\] By Cauchy-Schwartz, \[\left(a+b+c\right)\left(\frac{b^{4}}{c}+\frac{c^{4}}{a}+\frac{a^{4}}{b}\right)\ge(a^{2}+b^{2}+c^{2})^{2}.\] Also, by Cauchy-Schwartz, \[(b^{2}c+a^{2}b+c^{2}a)\left(\frac{b^{2}}{c}+\frac{c^{2}}{a}+\frac{a^{2}}{b}\right)\ge(a^{2}+b^{2}+c^{2})^{2}.\] Multiply the two inequalities and substitue $\frac{b}{a}+\frac{a}{c}+\frac{c}{b}$ for $b^{2}c+a^{2}b+c^{2}a$ to obtain the desired inequality.[/hide]


ARML geometry calculus integration trigonometry

1.
In right triangle $ABC$, $\angle C = 90^\circ$, $c=3$, and $a+b=\sqrt{17}$.  Compute the area of the triangle.

2.
If $(a+b): (b+c): (c+a) = 6: 7: 8$, and $a+b+c=14$, compute the value of $c$.

3.
Let $z$ be a root of $z^{5}-1=0$, with $z \not= 1$.  Compute the value of
\[z^{15}+z^{16}+z^{17}+\cdots+z^{50}. \]
4.
A regular polygon of $2n$ sides is inscribed in a circle of radius 5.  The sum of the squares of the distances from any point on the circle to the vertices of the polygon is 600.  Compute the value of the integer $n$.

5.
The circles, each of radius 5, lie in perpendicular planes.  They intersect in two points, $X$ and $Y$, thus determining a common chord $\overline{XY}$.  If $XY = 8$, compute the distance between the centers of the circles.

6.
How many positive integers less than 54 are equal to the product of their proper divisors?

7.
Find all positive integers $n$, less than 17, for which $n!+(n+1)!+(n+2)!$ is an integral multiple of 49.

8.
In triangle $ABC$, $a \ge b \ge c$.  If $ \frac{a^{3}+b^{3}+c^{3}}{\sin^{3}{A}+\sin^{3}{B}+\sin^{3}{C}}= 7$, compute the maximum possible value of $a$.


the larger of two cubes has twice the volume of the smaller cube. if the diagonal of the smaller cube is 1, find the diagonal of the larger cube.

can i check my answer with you guys?

[hide="answer?"]$\sqrt[3]{2}$[/hide]

Right
If the ratio of the volume is 2, then the ratio of the side lengths is $\sqrt[3]{2}$ and therefore the ratio of the diagonals is also $\sqrt[3]{2}$.


superior algebra
superior algebra theorems

Suppose you have a set with some binary operation $ \cdot$, with an identity $ e$ such that $ a\cdot e \equal{} e \cdot a \equal{} a$. Then, we can show that the identity is unique by considering $ e\cdot f$ where $ e$ and $ f$ are identities.

However, what if we only guaruntee that the $ e\cdot a \equal{} a$? It's easy to prove that every left identity is equal to every right identity, so if we guaruntee that one of each exists, then we again have a unique identity. However, what if there is no right identity? Is it possible to have two distinct left identities? If so, are these structures at all useful?

Let $ S$ be any set, and define $ x*y\equal{}y$ for $ x,y\in S$.  Then every element of $ S$ is a left identity.

It's my understanding that there's not a lot that you can say about binary options in general, but of course "useful" is a very relative term.  You should definitely throw in associativity to get much of an interesting structure, but I don't know a thing about the theory of semigroups.


Have you got China TST 2005?

Sorry,because English of mine is very bad :P

[quote="vnmathboy"]You have China MO 1900-2005??[/quote]

I haven't got.

[quote="vnmathboy"]You have China MO 1900-2005??[/quote]

See <snipped url> see the better one below! :)

No, actually see http://www.mathlinks.ro/Forum/resources.php?c=37&cid=47 !!  :!:

[quote="vnmathboy"]No, I need Chinese MO, not TST[/quote]

It will be put up in the future as well!  :)


inequalities
trigonometry
geometry
3D geometry
tetrahedron
probability

These inequalities are from the (old) APMOs.  They're not that difficult, so don't be intimidated by the source:

1.  Let $a,b,c$ be sides of a triangle.  Prove that:

$\sqrt {a+b-c}+\sqrt{b+c-a}+\sqrt{c+a-b}\leq \sqrt{a}+\sqrt{b}+\sqrt{c}$

2.  Let $k,n$ be positive integers with $k<n$ and let $x_1,x_2,\ldots x_n$ be positive integers.  Define $s_i$ to be the $i$th symmetric sum of the $x_i$s.  Prove that

$s_ks_{n-k}\geq\binom{n}{k}^2s_n$

3.  Say that $x_1,\ldots x_n$ and $y_1,\ldots y_n$ are positive reals with the same sum.  Prove that:

$\sum^n_{i=1}\frac{x^2_i}{x_i+y_i}\geq\frac {1}{2}\sum^n_{i=1}x_i$

4.  Prove that $(n+1)^mn^m\geq\frac{(n+m)!}{(n-m)!}\geq 2^mm!$ for integers $n \geq m>0$.

3.

[hide] By Cauchy in the alternative form,

LHS $\geq \frac{(x_1+\ldots +x_n)^2}{x_1+\ldots + x_n + y_1 +\ldots +y_n} = \frac{(x_1+\ldots +x_n)^2}{2(x_1 +\ldots + x_n)} =$ RHS[/hide]

1.

[hide]First, we use the substitution $a=x+y$, $b=y+z$, $c=x+z$, which is acceptable since $a,b,c$ are triangle sides. Now our inequality becomes:

$\sqrt{2x} + \sqrt{2y} + \sqrt{2z} \leq \sqrt{x+y} + \sqrt{z+y} + \sqrt{x+z}$

Now we put $x = \alpha^2, y = \beta^2, z=\gamma^2$. Our inequality looks like this:

$\alpha +\beta +\gamma \leq \sqrt{\frac{\alpha^2+\beta^2}{2}} +  \sqrt{\frac{\beta^2+\gamma^2}{2}} +  \sqrt{\frac{\alpha^2+\gamma^2}{2}}$

But, from QM-AM

$\sqrt{\frac{\alpha^2+\beta^2}{2}} \geq \frac{\alpha+\beta}{2}$
$\sqrt{\frac{\beta^2+\gamma^2}{2}} \geq \frac{\beta+\gamma}{2}$
$\sqrt{\frac{\alpha^2+\gamma^2}{2}} \geq \frac{\alpha+\gamma}{2}$

Sum it up, and we're done.[/hide]

Number 1 has another interesting way which involves [hide="these"]squaring both sides and using law of cosines[/hide].

[quote="blahblahblah"]
2. ... Define $s_i$ to be the $i$th symmetric sum of the $x_i$s.[/quote]

What exactly would that mean?  :blush:  Edit--oh, does it mean the symmetric sum with i terms?

[quote="blahblahblah"]
4.  Prove that $(n+1)^mn^m\geq\frac{(n+m)!}{(n-m)!}\geq 2^mm!$ for integers $n \geq m>0$.[/quote]

[hide]Part 1:
For any integer (or real, for that matter) k,
$n^2 + n = n^2 + n - k^2$
$(n+1)n \ge (n+k)(n-k+1)$

$(n+1)^mn^m \ge \frac{(n+m)!}{(n-m)!}$

Part 2:

${n \choose 1} = n \ge 2 = 2^1$
$\mbox{Given that } {n+m \choose m} \ge 2^m$
${n+m+1 \choose m+1} = \frac{n+m+1}{m+1}{n+m \choose m} \ge \frac{n+m+1}{m+1}2^m \ge 2^{m+1}$

$\therefore {n+m \choose m} \ge 2^m \implies \frac{(n+m)!}{(n-m)!} > \frac{(n+m)!}{n!} \ge m!2^m$[/hide]

Solution for [b]1[/b]:

Let $x=a+b-c,y=b+c-a,z=c+a-b\ (x>0,y>0,z>0)$,we can rewrite our inequality to

\[\sqrt{x}+\sqrt{y}+\sqrt{z}\leqq \frac{\sqrt{x+y}+\sqrt{y+z}+\sqrt{z+x}}{\sqrt{2}}\]

By Jensen's inequality $\frac{\sqrt{x}+\sqrt{y}}{2}\leqq \sqrt{\frac{x+y}{2}}$ and so on,adding up these 3 inequality,we are done.

[quote="blahblahblah"]Your solutions are all good!

My solution for 1) was Kunny's, for 2) it was Tetrahedrons, and for 4) it was very similar to probability 1.01's.

Now does anyone have one for the easiest question, which is 2)?[/quote]

I still don't quite know what it's asking :(

Maybe I am wrong, but isn't 2) just multiplying 2 AM-GM's?

Absolutely, and noting that $\binom{n}{n-k}=\binom{n}{k}$

Well, I saw the AM-GM connection, but was stuck in details trying to find out how many "a"s would be in the expansion of $s_k s_{n-k}$.

Can anyone provide a detailed solution?

It's more counting than anything

AM-GM on $s_k$ yields

$s_k\geq\binom {n}{k}(x_1x_2\ldots x_n)^{\frac {k}{n}}$
$s_{n-k}\geq\binom {n}{n-k}(x_1x_2\ldots x_n)^{\frac {n-k}{n}}$

(this is because (obviously) each $x_i$ appears in exactly $i$ of the terms)
Multiplying we get:

$s_ks_{n-k}\geq \binom {n}{k}\binom {n}{n-k}(x_1x_2\ldots x_n)^{\frac {n-k+k}{n}}$
$\Longrightarrow s_ks_{n-k}\geq \binom {n}{k}^2(x_1x_2\ldots x_n)$
$\Longrightarrow s_ks_{n-k}\geq \binom {n}{k}^2s_n$

For the second part of #4, doesn't it follow almost trivially by noting C(n+m,2m) >= 1, and (2m)! >= 2^m * m! ?

Ahh! Kicking myself.

For 2, I was trying to apply AM-GM after I expanded $s_k s_{n-k}$, instead of separately applying AM-GM to both $s_k$ and $s_{n-k}$.

Good.  Now solve the questions from the other APMO thread I created.

Here is the solution for 1): \[
\sqrt{a+b-c}+\sqrt{a+c-b}\leq\sqrt{2\times 2\times a}.
 \sqrt{a+c-b}+\sqrt{c+b-a}\leq\sqrt{2\times 2\times c}.
 \sqrt{b+c-a}+\sqrt{b+a-c}\leq\sqrt{2\times 2\times b}.
 So  \sum\sqrt{a+b-c}\leq\sum\sqrt{c}.\]

For 1) we can use Karamata's inequality or ( Caramata's ).   :)


trigonometry
algebra
polynomial
calculus
calculus computations

Hi everyone,
I have a problem solving this using a series expansion. Can you help please?

xy"+(sinx)y'+2xy=3x^2
y(0)=y'(0)=1

[quote="Kent Merryfield"]One little thing I'd do is to write the equation as

$y''+\left(\frac{\sin x}x\right)y'+2y=3x.$

Note that $\frac{\sin x}x$ is a perfectly respectable analytic function.

The messiest part of this is that you're going to have to multiply together two power series.

Assume that $y=\sum_{n=0}^{\infty}a_{n}x^{n}.$

(By the way, the initial conditions tell us that $a_{0}=a_{1}=1.$)

Then:

$y'=a_{1}+2a_{2}x+3a_{3}x^{2}+4a_{4}x^{3}+\cdots$

$\frac{\sin x}x=1-\frac{x^{2}}{3!}+\frac{x^{4}}{5!}-\frac{x^{6}}{7!}+\cdots$

Now multiply these to get:

$\left(\frac{\sin x}x\right)y'=a_{1}+2a_{2}x+\left(3a_{3}-\frac{a_{1}}{3!}\right)x^{2}+\left(4a_{4}-\frac{2a_{2}}{3!}\right)x^{3}$
$+\left(5a_{5}-\frac{3a_{3}}{3!}+\frac{a_{1}}{5!}\right)x^{4}+\left(6a_{6}-\frac{4a_{4}}{3!}+\frac{2a_{2}}{5!}\right)x^{5}+\cdots$

This goes into the differential equation, along with the series for $y''$ and for $2y.$ Note that the polynomial $3x$ is its own power series. Equate the coefficients of the same powers of $x.$

It may be hard to get closed-form formulas for the coefficients $a_{n}$ but you should be able to work out the first few.[/quote]

Thanks a lot. I have a question. What do you mean by "the polynomial 3x is its own power series."? How should I write the 3x so that I can equate the coefficients of the same powers of x?
Thanks in advance

a power series is in some sense a(possibly infinite) polynomial approximation to a given fn. what is the best polynomial that you can think of which comes "close" to $3x$? it is nothing but $3x$ itself

Written out in full,

$3x = 0+3x+0x^{2}+0x^{3}+\cdots.$

Every coefficient of $x^{n}$ is zero, with the sole exception of the $n=1$ case.


Fie f:$\mathbb{R}\to\mathbb{R}$ o functie care admite primitive si $F$ una dintre ele.
Aflati $f$ astfel incat
$(xf(x)-2F(x))(F(x)-x^2)=0$ pentru orice $x\in\mathbb{R}$.


hi
what is the single bound theorem...4 roots of a polynomial :?:

da theorem says that:
 :arrow:
Consider the monic polynomial P(x) = x^n+An−1x^n−1 +· · ·+A1x+A0, where Ai are real . Let M1 = 1+max{|A0|, |A1|, . . . , |An−1|} and M2 = max{1, |A0|+|A1|+· · ·+|An−1|}. Also, let M = min{M1,M2}. The Single Bound Theorem
states that all roots of P(x) are between −M and M.

where can i find da proof?
ssivark

Maybe your terminology isn't standard. You should try to enounce your theorem ...


[b]Problem:[/b] An international society has its members from six different countries. The list of members has 1978 names, numbered $1, 2, ... , 1978$. Prove that there is at least one member whose number is the sum of the numbers of two members from his own country, or twice the number of a member from his own country.

The solution is [url=http://www.kalva.demon.co.uk/imo/isoln/isoln786.html]here[/url]. But I dont understand it. It is written very poorly in explanation. One thing that is troubling me is that it says $C_{2}$ must have at least $66$ members. But that's not true, It can be 1,1,1,1,1,1973.

There are $329$ differences $a_{2}-a_{1}, ... a_{330}-a_{1}$.  The problem is finished if any of them are in $C_{1}$, so they must be among the other $5$ countries.  By Pigeonhole, at least one country must have $66$ members, so that country is $C_{2}$.  Also, the differences are distinct, so no repetition is possible.


true or false and why?
1) every square matrix can be written as the product of elementary matrices.
2) The inverse of an elementary matrix is an elementary matrix.
3) Every system with 3 equations in 4 unknowns has at least one solution.

4) A square matrix is defined to be stochastic if all its elements are nonnegative and the sum of the elements in any given column is 1.
Prove that the product of any two stochastic matrices is stochastic.

Thank you .  :)

1. [hide="False"]A square matrix can be written as a product of elementary matrices if and only if it is invertible. Nonivertible matrices exist.[/hide]

2. [hide="True"]You should provide details, of course. There are three distinct types of elementary matrix, so there are three cases to describe. Each elementary matrix corresponds to a type of elementary row operations. (That comment assumes you are acting on the left.) How do you [i]undo[/i] an elementary row operation? Answer that, and you'll see what the inverse matrix has to be.[/hide]

3. [hide="False"]To make this a correct answer, you'll have to supply a counterexample - one such example will do. Building counterexamples is a good skill to have, so I'll leave it to HAPPYSTUDENT to do so.[/hide]

As for #4, try writing out what stochastic means using summation notation and subscripts, defining matrix multiplication using summation notation, and then just plowing into it and doing what you have to do.

[hide="A better hint for 4."]
Suppose $ A$ is a matrix with nonnegative entries. Define $ u\equal{}\begin{bmatrix}1\\1\\ \vdots\\1\end{bmatrix}$.

What is the relationship between $ A$ being stochastic and a statement you can make about $ Au?$[/hide]


topology
real analysis
real analysis unsolved

Prove that a open disk B(0,1) cannot be expressed as disjoint union of open rectangles.

Could anyone provide me some help on this question? Thanks.

Suppose that $B=\bigcup_{k=1}^{\infty}R_{k}$ (disjoint union). Then $B\setminus R_{1}=\bigcup_{k=2}^{\infty}R_{k}$. But $B\setminus R_{1}$ is not an open set.

Actually, this question has more to do with topology than with measure theory. Since the set $B$ is connected, it cannot be written as a disjoint union of two open sets (whatever their shape is).


I don't know the solution to this problem, so lets discover it together.

Find all x, y, and z such that {x, y, z} C {integers}, z > y > x > 1, and
0 :equiv: (xyz - 1) mod [(x - 1)(y - 1)(z - 1)].

It's worth noting that this problem is equivelent to:

[hide]x+y+z :equiv: xy+xz+yz mod (x-1)(y-1)(z-1) when, in the original statement, you replace 0 with (x-1)(y-1)(z-1) and expand.[/hide]

I believe that you can just do lots of casework -- if we pick values for x and y, z automatically becomes bounded.  Eventually, large enough values for x and y should fix z in a set for which we know there are no solutions.  This is because the ratio of the two sides will be about xyz/((x - 1)(y - 1)(z - 1)), which, for reasonably large x and y will be less than 2 no matter what.

(2, 4, 8) works, but unless I'm missing something terribly simple, substitution of the triple (3, 5, 11) into the given equivalency yields a false statement: (3*5*11 - 1) mod [(3 - 1)(5 - 1)(11 - 1)] :equiv: 0 is not true. Nice work though.

I tried to to solve this problem by thinking of it as a Diophantine equation. From the given information we can write

(xyz - 1) / [(x - 1)(y - 1)(z - 1)] = k,

where k is a natural number. We can rearrange this equation to get

xyz - 1 - k(x - 1)(yz - y - z - 1) = 0
xyz - k(xyz - xy - xz - x - yz + y + z + 1) = 1
(1 - k)xyz + k(xy + xz + x + yz - y - z) = k + 1,

which I think can be solved by the decomposition method. Anyone know how to factor the left side of this equation?

:oops:  I'm very good at making last line stupid mistake ...

I did my computations again (and checked them !) , I find now (2,4,8) and  (3,5,15) as only solutions. Perhaps there is a simpler solution using xy=z ??

[quote]Perhaps there is a simpler solution using xy=z ??[/quote]

What do you mean?

Both of his solutions (2, 4, 8) and (3, 5, 15) have the interesting property that the third entry is the product of the first two.  He was wondering if it might be possible to solve the equation using that fact somehow.

One thing you can do that might go down that track is to notice that
xyz - 1 :equiv: 0 (mod (z - 1))
z - 1 | xyz - 1
z - 1 | xyz - 1 - xy(z - 1) = xy - 1
z :le: xy.

Then I suppose you just have to show z :ge: xy, and then solve when z = xy.


floor function
inequalities
calculus
function
algebra proposed
algebra

Let $k$ and $a_0>1$ be positive integers. The sequence $a_n$ is defined by the recursion
\[ \displaystyle a_{n+1}=\frac{1}{k}\left\lfloor (k-1)a_n + \frac{2}{a_n^{k-1}}\right\rfloor \]
where $\lfloor x \rfloor$ denotes the greatest integer $\leq x$.
Prove that there is a index $N$ so that for all $n>N$
\[ a_{2n}=a \text{ and } a_{2n+1}=b \]
holds. Also determine $a$ and $b$.

We will prove that $a_{n}=1$ for some $n$ and then the sequence oscillates between $1+\frac{1}{k}$ and $1$ (that is, $a_{n+1}=1+\frac{1}{k},a_{n+2}=1,$ etc.)

First, observe that $a_{n}\geq1$ for all $n.$ Indeed, the AM-GM inequality gives
\[ \left( k-1\right) a_{n}+\frac{2}{a_{n}^{k-1}}=a_{n}+a_{n}+\ldots+a_{n} +\frac{2}{a_{n}^{k-1}}\geq k\sqrt[k]{a_{n}^{k-1}\frac{2}{a_{n}^{k-1}} }=k\sqrt[k]{2},  \]
hence
\[ a_{n+1}\geq\frac{\left\lfloor k\sqrt[k]{2}\right\rfloor }{k}\geq1.  \]
Next, if $a_{n}>\sqrt[k]{2},$ it follows that $a_{n+1}<a_{n}.$ To see this, note that $ka_{n}$ is an integer for all $n,$ so
\[ a_{n+1}-a_{n}=\frac{\left\lfloor \left( k-1\right) a_{n}+\frac{2} {a_{n}^{k-1}}\right\rfloor -ka_{n}}{k}=\frac{\left\lfloor \frac{2-a_{n}^{k} }{a_{n}^{k-1}}\right\rfloor }{k}<0.  \]

If $a_{n}>\sqrt[k]{2}$ for all $n,$ the sequence is decreasing and bounded from below, hence convergent. Then $\left( ka_{n}\right)$ is also convergent and since it is a sequence of integers it must be (from some term onwards) constant. Suppose $a_{n}\longrightarrow x.$ Replacing in the recursive equation we find that $x\leq\sqrt[k]{2},$ hence $x=\sqrt[k]{2},$ which is a contradiction, since $k\sqrt[k]{2}$ is not an integer.

We deduce that $a_{n}\leq\sqrt[k]{2}$ for some $n.$

We will use the inequality $2^{x}<1+x$ for $x\in\left( 0,1\right)$ (one does not need calculus to prove this; just observe that $2^{x}$ is a convex function and its graph intersects the line $y=1+x$ at points $0$ and $1).$

From the above inequality it follows that $\sqrt[k]{2}<1+\frac{1}{k},$ hence
$a_{n}<1+\frac{1}{k},$ implying $a_{n}=1.$

Now, a short computation shows that $a_{n+1}=1+\frac{1}{k}$ and $a_{n+2}=1,$ again.

A final observation: when proving that $a_{n+2}=1,$ one needs the inequality
\[ \left( 1+\frac{1}{k}\right) ^{k}>2  \]
for all $k\geq2.$


Bonjour .

there is a work about an olympiad exercise and one auther sequence ...

Could you please translate it into English?

Hello !

I will try but it's going to take me a little time

I am moroccan and I write  little english


algorithm
rotation
geometry
geometric transformation
logarithms
combinatorics

Suppose that $n$ people $A_1$, $A_2$, $\ldots$, $A_n$, ($n \geq 3$) are seated in a circle and that $A_i$ has $a_i$ objects such that
\[ a_1 + a_2 + \cdots + a_n = nN \]
where $N$ is a positive integer. In order that each person has the same number of objects, each person $A_i$ is to give or to receive a certain number of objects to or from its two neighbours $A_{i-1}$ and $A_{i+1}$. (Here $A_{n+1}$ means $A_1$ and $A_n$ means $A_0$.)  How should this redistribution be performed so that the total number of objects transferred is minimum?

it's the hardest problem in APMO 1997;most of our team's member get 0
the offical solution(the only solution i know too): http://www.kalva.demon.co.uk/apmo/asoln/asol975.html

I'm sorry but I can't open the link.Can you post the solution here please?
Thanks.

Yes, sure :
[quote="Kalva"]Label the people from 1 to n, with person i next to person i+1, and person n next to person 1. Let person i initially hold ci coins. Let di = ci - k.

It is not obvious how many moves are needed. Clearly at least 1/2 ∑ |di| are needed. But one may need more. For example, suppose the starting values of di are 0, 1, 0, -1, 0. Then one needs at least 2 moves, not 1.

Obviously ∑ di = 0, so not all di can be negative. Relabel if necessary so that d1 ≥= 0. Now consider X = |d1| + |d1 + d2| + |d1 + d2 + d3| + ... + |d1 + d2 + ... + dn-1|. Note first that X is zero iff all di are zero. Any move between i and i+1, except one between n and 1, changes X by 1, because only the term |d1 + d2 + ... + di| is affected. Thus if we do not make any moves between n and 1, then we need at least X moves to reach the desired final position (with all di zero).

Assume X > 1. We show how to find a move which reduces X by 1. This requires a little care to avoid specifying a move which might require a person with no coins to transfer one. We are assuming that d1 ≥ 0. Take the first i for which di+1 < 0. There must be such an i, otherwise all di would be non-negative, but they sum to 0, so they would all have to be zero, contradicting X > 0. If d1 + ... + di > 0, then we take the move to be a transfer from i to i+1. This will reduce |d1 + ... + di| by 1 and leave the other terms in X unchanged, so it will reduce X by 1. If d1 + ... + di is not strictly positive, then by the minimality of i we must have d1 = d2 = ... = di = 0. We know that di+1 < 0. Now find the first j > i+1 such that dj ≥ 0. There must be such a j, otherwise we would have ∑ dm < 0. We have d1 + ... + dj-1 < 0, so a transfer from j to j-1 will reduce |d1 + ... + dj-1| and hence reduce X. Finally note that the move we have chosen leaves d1 ≥ 0. Thus we can repeat the process and reduce X to zero in X moves.

We have proved that this procedure minimises the number of moves if we accept the restriction that we do not make any transfers between 1 and n. Thus the full algorithm is: calculate the effect of the transfers from 1 to n and from n to 1 on X. If either of these transfers reduces X by more than 1, then take the move with the larger reduction; otherwise, find a move as above which reduces X by 1; repeat. [/quote]

The solution appears to be wrong. Here's a counterexample: Suppose $n = 9, N = 1$ and after relabeling that the people have, in order, 2, 0, 0, 1, 1, 1, 1, 3, 0 objects. The given algorithm will first make person 1 pass an object to person 2, and then have the people numbered 4 and above each pass an object to the previous person.

(0) 2, 0, 0, 1, 1, 1, 1, 3, 0
(1) 1, 1, 0, 1, 1, 1, 1, 3, 0
(2) 1, 1, 1, 0, 1, 1, 1, 3, 0
(3) 1, 1, 1, 1, 0, 1, 1, 3, 0
(4) 1, 1, 1, 1, 1, 0, 1, 3, 0
(5) 1, 1, 1, 1, 1, 1, 0, 3, 0
(6) 1, 1, 1, 1, 1, 1, 1, 2, 0
(7) 1, 1, 1, 1, 1, 1, 1, 1, 1

But the optimal solution, which is not discovered because it involves passing objects to the border between person 1 and person $n$ from more than one person away, only requires 6 moves:

(0) 2, 0, 0, 1, 1, 1, 1, 3, 0
(1) 1, 1, 0, 1, 1, 1, 1, 3, 0
(2) 1, 0, 1, 1, 1, 1, 1, 3, 0
(3) 0, 1, 1, 1, 1, 1, 1, 3, 0
(4) 0, 1, 1, 1, 1, 1, 1, 2, 1
(5) 1, 1, 1, 1, 1, 1, 1, 2, 0
(6) 1, 1, 1, 1, 1, 1, 1, 1, 1

The string of 1s can be extended arbitrarily in this counterexample; the optimal solution remains at 6 moves while the algorithm's solution becomes $n - 2$, which can obviously be arbitrarily big.

The key failure in the solution is a bit vaguely phrased: if we "calculate the effect of the transfers from 1 to n and from n to 1 on X" and find one move that does decrease X by more than 1, there's no guarantee that there are any objects present that enable us to make that move. I'm assuming the algorithm simply gives up and goes to the next step to find a normal reduce-X-by-1 move. The algorithm might actually be correct if it moves an object across several people to make that decrease-X-by-more-than-1 move, partially because if there are so many people near the border between person 1 and person $n$ with 0 objects, then passing an object across them would also be standard reduce-X-by-1 moves. However, I don't know how to prove this. It's far from obvious that the reduction of X by more than 1 is used to its fullest potential and won't be affected by the intermediate moves.

I think this question is very oddly phrased for a math olympiad problem, and it's hard to specify what a solution has to do to count as having solved it. For what it's worth, if this had been given as a programming problem, my algorithm would be as follows:

Transform the problem into this isomorphic representation to make things easier: arrange the $nN$ objects in a circle and place labeled dividers between adjacent objects to represent the initial distribution of objects to people. Each person's share of objects is represented by the number of objects between two particular adjacent dividers. Then each transfer of objects is equivalent to moving one divider forward or backward one step in the circle, with the restriction that dividers cannot overtake one another (they can be in the same space between two objects, but their relative positions inside the space must still be preserved). Now the goal is to arrange the dividers so that they are equally spaced $N$ objects apart around the circle with the least number of moves.

Positioning any one divider locks down the target positions of the others, so since there are $nN$ positions between objects, there are only $nN$ possible ending configurations. But in fact, we only need to consider at most $n$ of them, namely those ending configurations where at least one divider is not moved from its initial position. This is because if no dividers are correct in an ending configuration, the number of moves required to obtain it changes linearly if the ending configuration is rotated to the left or right. So we can rotate the ending configuration in one direction until one divider is in the correct position without increasing the number of moves required to obtain it.

There is now a $O(n^2)$ solution: brute-force all possible ending configurations, determine the number of moves required to reach it by checking every divider, and take the minimum.

But the calculation step can be optimized by noting that the number of moves required for any one divider changes linearly most of the time as the ending configuration is rotated, with only one "inversion" when its initial position crosses over its ending position. So we can record when the inversion occurs for each divider, presort this list of inversions, keep track of a delta during the rotation step that tells us how much to update the "total moves required" in $O(1)$, and only update the delta when we meet an inversion. Then we can check all possible ending configurations in an $O(n)$ sweep. This algorithm takes only $O(n \log n)$ time and is dominated by the cost of presorting the list of inversions.

I think changing the algorithm from finding the smallest $j$ such that $d_j \geq 0$ to smallest j such that $d_1+...+d_j \geq 0$ when $d_1 = .... = d_i$ fixes it.

We can view this problem as person $i$ giving $x_i$ objects to person $i+1$ ($x_i$ can be negative), where we want to minimize the cost $\sum_{i=1}^n |x_i|$.
Since $a_i + x_{i - 1} - x_i = N$, we have $x_i = x_{i - 1} + a_i - N$. Thus if we fix $x_1$, the rest of $x_i$ are fixed as well. This allows us to rewrite the cost as $\sum_{i=1}^n |x_1 - b_i|$ for $b_i$ such that $|x_1 - b_i|=|x_i|$, which is minimized when $x_1$ is the median of all $b_i$. This algorithm also takes $O(n\log n)$ with the bottleneck being sorting the list of $b_i$ to find the median.

By the way, this problem was given on a programming contest a couple years ago: http://usaco.org/index.php?page=viewproblem2&cpid=128

The solution is in the Example 8 of the 1st chapter of [url=https://artofproblemsolving.com/community/c6h601134p3568667]this book[/url]

solution from book [b]Mathematical Olympiads 1997-1998: Problems and Solutions[/b]

I think my solution is wrong :blush:
Label the people inthe circle clockwise by $i = 1, 2 , …,n$. Define $L_j = \sum |a_i - a_{i-1}|$ over all $i$ in the j-th step. We also define $a_i$ as the amount of objects the person $i$ has. It is almost trivial that $L$ can change only by $4$ and that $L$ is always divisble by 4. Now we can formulate the algorithm as follows: Make a transfer each step such that $L_j - L_{j+1} = 4$. If $L_j = 0$ for some natural number $j$, then stop.
EDIT: Could someone give me a correction?

I have a bit different solution, thanks to the help of [b]CANBANKAN[/b]

[quote = Solution]
Consider the maximal $a_{j}$, note that either $a_{1}+a_{2}.....a_{j-1} < (j-1)k$ or $a_{j+1}+....a_{n} < (n-j)k$ or both, so if the side 2 is lesser or the side 1, keep giving coins from $a_{j}$ unless $a_{j} = k$, similarly keep repeating this process unless all of them become equal to $k$, this is minimal since the difference of the indices bigger than k, need to be distributed, no matter how we distribute it, the number of move remains the same.


Let $ P_1(x), P_2(x), \ldots, P_n(x)$ be real polynomials, i.e. they have real coefficients. Show that there exist real polynomials $ A_r(x),B_r(x) \quad (r \equal{} 1, 2, 3)$ such that

\[ \sum^n_{s\equal{}1} \left\{ P_s(x) \right \}^2 \equiv \left( A_1(x) \right)^2 \plus{} \left( B_1(x) \right)^2\]
\[ \sum^n_{s\equal{}1} \left\{ P_s(x) \right \}^2 \equiv \left( A_2(x) \right)^2 \plus{} x \left( B_2(x) \right)^2\]
\[ \sum^n_{s\equal{}1} \left\{ P_s(x) \right \}^2 \equiv \left( A_3(x) \right)^2 \minus{} x \left( B_3(x) \right)^2\]

[quote="bogdanno"]a more general result holds:
Any polynomial $p\in \mathbb{R}[x]$ such that $p\geq 0$ can be written as a sum of two squares of polynomials.
It results from the fact that any such polynomial can be written as
$p=a^2\prod_i (x-b_i)^{2s_i}\prod_j [(x-c_j)^2+d_j^2]^{t_i}$
and from the relation:
$(a^2+b^2)(c^2+d^2)=(ac-bd)^2+(ad+bc)^2$.[/quote]

By a similar line of reasoning, noting that any polynomial $p \geq 0$ can be written as
$p(x)=q^2(x)\prod_j [(x-e_j)^2+f_j^2 x]$ where $q$ is a polynomial and $e_j$,  $f_j$ are real numbers, and from a mimicked from of the above-mentioned relation:
$(a^2 + b^2 x)(c^2 + d^2 x) = (ac - bdx)^2 + (ad + bc)^2 x$

The third equation can be proved similarly, but actually one could have noticed the obvious equivalence between the second and third equation.


[quote="orl"]A triangle $ ABC$ is given. Let $ B_1$ be the reflection of $ B$ across the line $ AC$, $ C_1$ the reflection of $ C$ across the line $ AB$, and $ O_1$ the reflection of the circumcentre of $ ABC$ across the line $ BC$. Prove that the circumcentre of $ AB_1C_1$ lies on the line $ AO_1$.[/quote]

Let $ (O)$ be circumcircle of $ \triangle ABC$. Let parallel to $ BC$ through $ A$ cut $ (O)$ again at $ Z.$
By Ptolemy for isosceles trapezoid $ AZBC,$ $ AZ \cdot BC \equal{} AB^2 \minus{} AC^2.$

Let $ D \equiv BC_1 \cap CB_1.$ $ \triangle ABC \cong \triangle ABC_1 \cong \triangle AB_1C$ are congruent $ \Longrightarrow$
$ \angle BDC \equal{} 2\pi \minus{} (3 \angle A \plus{} \angle B \plus{} \angle C) \equal{} \pi \minus{} 2 \angle A \equal{} \pi \minus{} \angle COB$ $ \Longrightarrow$
$ OBDC$ is cyclic, let $ (P)$ be its circumcircle.

Let $ CD$ cut $ (O)$ again at $ E$ $ \Longrightarrow$
$ \angle BDE \equal{} \pi \minus{} 2 \angle A,$ $ \angle DEB \equal{} \angle A$  $ \Longrightarrow$ $ \triangle BDE$ is isosceles with $ BD \equal{} ED$ and
$ \angle CBE \equal{} \pi \minus{} (\angle A \plus{} 2 \angle B) \equal{} \angle C \minus{} \angle B.$ Consequently, $ AZ \equal{} CE \equal{} CD \minus{} ED \equal{} CD \minus{} DB.$
Let $ K, L$ be midpoints of $ BD, CD,$ respectively. Then

$ AB_1^2 \minus{} AC_1^2 \plus{} KB_1^2 \minus{} KD^2 \plus{} LD^2 \minus{} LC_1^2 \equal{} AB^2 \minus{} AC^2 \plus{} BC_1 \cdot DB \minus{} CB_1 \cdot DC \equal{}$
$ \equal{} AZ \cdot BC \minus{} BC \cdot (CD \minus{} DB) \equal{} AZ \cdot BC \minus{} BC \cdot CE \equal{} 0$

By Carnot theorem for $ \triangle DB_1C_1,$ perpendiculars to $ B_1C_1, C_1D, DB_1$ from $ A, L, K$ are concurrent at $ P.$

Let $ N$ be 9-point circle center of $ \triangle ABC$; $ N$ is midpoint of $ AO_1.$
Kosnita point $ Ko \equiv N^*$ is isogonal conjugate of $ N$ (well known, see hidden stuff below) and $ Ko \in AP.$
Triangles $ \triangle ABC, \triangle AB_1C_1$ have common internal bisector of $ \angle A.$
Since $ AKoP$ is A-altitude of $ \triangle AB_1C_1$ passing through its orthocenter $ \Longrightarrow$
its isogonal $ ANO_1$ WRT $ \angle C_1AB_1$ passes through its circumcenter. $ \square$

[hide]Let $ \triangle A_0B_0C_0$ with circumcircle $ (N)$ be medial triangle of $ \triangle ABC.$ Let $ I$ be incenter of $ \triangle ABC.$ Inversion with center $ A$ and power $ AO^2$ takes $ B, C$ into $ B' \in AB, C' \in AC$ and $ (O)$ into the perpendicular bisector $ B'C'$ of $ AO.$ $ \triangle AC'B' \cong \triangle OC'B'$ are congruent and $ B'C'$ is antiparallel of $ BC$ WRT $ \angle A.$ Let $ \triangle O''C''B''$ be reflection of $ \triangle OC'B'$ in the internal bisector $ AI$ of $ \angle A$ and $ (P'), (P'')$ their respective circumcircles. $ (P') \sim (P)$ are centrally similar with similarity center $ A$ $ \Longrightarrow$ $ A, P', P$ are collinear. $ \triangle O''C''B'' \sim \triangle A_0B_0C_0$ are centrally similar with the same similarity center $ A$ $ \Longrightarrow$ $ A, P'', N$ are collinear. Since $ P''$ is reflection of $ P'$ in $ AI$ $ \Longrightarrow$ $ AP \equiv AP'$ is isogonal of $ AN \equiv AP''$ WRT $ \angle A.$[/hide]

Let us to present an elementary solution of this nice problem.

We denote as $ M,\ N,$ the midpoints of the side-segments $ AC,\ AB$ respectively and let be the points $ D\equiv AC_{1}\cap OM$ and $ E\equiv AB_{1}\cap ON.$

It is easy to show that $ DE\parallel B_{1}C_{1}$ $ ,(1)$ because of $ \frac {AD}{AE} = \frac {AC}{AB} = \frac {AC_{1}}{AB_{1}}$ from the similar right triangles $ \bigtriangleup MAD,\ \bigtriangleup NAE$ and the similar isosceles triangles $ \bigtriangleup ABB_{1},\ \bigtriangleup ACC_{1}.$

So, from $ (1)$ we conclude that $ DE\parallel KL$ $ ,(2)$ where $ K,\ L,$ are the midpoints of the segments $ AC_{1},\ AB_{1},$ respectively.

$ \bullet$ Let $ BB',\ CC'$ be, the altitudes of the given triangle $ \bigtriangleup ABC$ $ ($ where $ B'\equiv AC\cap BB_{1}$ and $ C'\equiv AB\cap CC_{1}$ $ )$

and we denote the points $ P\equiv CC'\cap OM$ and $ Q\equiv BB'\cap ON.$

Because of $ \angle CPM = 90^{o} - \angle PCM = 90^{o} - \angle OCB = 90^{o} - \angle O_{1}CB = \angle CO_{1}O,$

we conclude that the quadrilateral $ OPCO_{1}$ is cyclic and then we have that $ \angle OPO_{1} = \angle OCO_{1}$ $ ,(3)$

From $ (3)$ $ \Longrightarrow$ $ \angle OPO_{1} = 2\angle OCB = 2\angle PCA = \angle CAD$ $ \Longrightarrow$ $ \angle MAD = \angle MPK'$ $ ,(4)$ where $ K'\equiv AD\cap O_{1}P.$

From $ (4)$ and because of $ PM\perp AC,$ we conclude that $ PK'\equiv O_{1}K'\perp AD$ and by the same way we can prove that $ QL'\equiv O_{1}L'\perp AE,$ where $ L'\equiv AE\cap O_{1}Q.$

$ \bullet$ Because of the similar right triangles  $ \bigtriangleup K'PD,\ \bigtriangleup L'QE$ $ ($ from $ \angle K'PD = \angle MAD = \angle NAE = \angle L'QE$ $ ),$

we have that $ \frac {K'D}{L'E} = \frac {PD}{QE}$ $ ,(5)$

Because of the similar triangles $ \bigtriangleup APD,\ \bigtriangleup AQE,$ $ ($ from $ \angle PDA = \angle QEA$ and

$ \angle PAD = \angle PAC + \angle CAD = \angle PCA + \angle CAD = \angle QBA + \angle BAE$ $ \Longrightarrow$ $ \angle PAD = \angle QAB + \angle BAE = \angle QAE$ $ ),$

we have that $ \frac {AD}{AE} = \frac {PD}{QE}$ $ ,(6)$

From $ (5),\ (6)$ $ \Longrightarrow$ $ \frac {K'D}{L'E} = \frac {AD}{AE}$ $ \Longrightarrow$ $ K'L'\parallel DE$ $ ,(7)$

From $ (2),\ (7)$ $ \Longrightarrow$ $ KL\parallel K'L'$ $ \Longrightarrow$ $ \frac {AK}{AK'} = \frac {AL}{AL'}$ $ (8)$

$ \bullet$ We consider now, the points $ K,\ A,\ K',$ as the orthogonal projections of $ O',\ A,\ O_{1}$ respectively, on the line segment $ AC_{1},$

where $ O'$ is the circumcenter of the triangle $ \bigtriangleup AB_{1}C_{1}.$

Similarly, we consider the points $ L,\ A,\ L',$ as the orthogonal projections of $ O',\ A,\ O_{1}$ respectively, on the line segment $ AB_{1}.$

Hence, because of $ (8),$ we conclude that the points $ O',\ A,\ O_{1},$ are collinear and the proof is completed.

$ ($ As well known, if the orthogonal ( or parallel ) projections of three given points, on two lines intersect each other, form segments with the same ratio then, these points are collinear with the same ratio $ ).$

$ \bullet$ This proof is dedicated to [b][size=100]Jean-Louis Ayme[/size][/b].

Kostas Vittas.

Dear Kostas,
thank you for your dedication. Your attached figure is very interesting and has much more to say.
Sincerely
Jean-Louis

First we will prove the lemma: :blush:
Let $ ABC$ be a triangle and $ H$ be its orthocenter.$ BH,CH$ meet $ AC,AB$ at $ B_1,C_1$.$ B_2,C_2$ are reflection points of $ A$ through $ B_1,C_1$.$ P$ be the reflection point of H through $ B_2C_2$.Let the reflections of $ BH,CH$ through $ AB,AC$ meet at $ Q$.Then $ A,P,Q$ are collinear.
We see that $ PB_2 \| AC_3,PC_2 \| PB_3,B_2C_2 \| B_3C_3$.Then $ AP,B_2C_3,B_3C_2$ are concurrent.Now we need to prove that $ AQ,B_2C_3,B_3C_2$ are also concurrent.
Let $ AB \cap CQ \equal{} B_4,AC \cap BQ \equal{} C_4$.We have $ \angle{B_4BC_4} \equal{} \angle {C_4CB_4}$ then $ B,C,B_4,C_4$ lie on a circle.Apply Reim's theorem to the tranversals $ BC_1B_4,CB_1C_4$ we conclude that $ B_4C_4 \| B_1C_1$.Let $ B_1C_1 \cap B_2C_2 \equal{} R$ in the infinity line,then $ B_4,C_4,R$ are collinear.Apply Desargue's theorem to the triangles $ AB_2C_2$ and $ QC_3B_3$ we have $ AQ,B_2C_3,B_3C_2$ are concurrent.
Return to our problem,apply the previous lemma to triangle $ AB'C'$, we have completed the proof. :P

Figure of the lemma:
[img]http://img505.imageshack.us/img505/716/tuymada.jpg[/img]

Let $ H$ be the orthocenter of $ ABC$. Let $ AB_1$ and $ CH$ meet at $ P$, and $ AC_1$ and $ BH$ meet at $ Q$. Let $ K_1$ and $ K_2$ be the circumcircles of $ BHC$ and $ AB_1C_1$, respectively.

We have $ \angle HBC \equal{} 90^{o} \minus{} \angle BCA$ and $ \angle BCH \equal{} 90^{o} \minus{} \angle ABC$, so $ 180^{o} \minus{} \angle CHB \equal{} \angle CAB$.
Now as $ O$ is the circumcentre of $ ABC$, $ \angle COB \equal{} 2\angle CAB$. Therefore $ \angle BO_1C \equal{} 2(180^{o} \minus{} \angle CHB)$. Using that $ O_1C \equal{} O_1B$, we get that $ O_1$ must be the center of $ K_1$.

Consider the quadrilateral $ B_1AHC$. We have $ \angle HCA \equal{} 90 \minus{} \angle CAB \equal{} \angle ABH \equal{} \angle HB_1A$. Therefore $ B_1AHC$ is cyclic.
Similarly, $ C_1AHB$ is cyclic. Let $ K_3$ and $ K_4$ be their circumcircles, respectively.

Now, the radical axis of $ K_2$ and $ K_3$ is $ aB_1$, and the radical axis of $ K_1$ and $ K_3$ is $ CH$. Then $ P$ is the radical center of $ C_1$, $ C_2$ and $ C_3$, and it must be in the radical axis of $ C_1$ and $ C_2$.
Similarly we can get that $ Q$ lies on the radical axis of those circumferences. Therefore, $ PQ$ is perpendicular to $ O_1O_2$.

Now, $ \angle QC_1P \equal{} \angle HCA \equal{} 90 \minus{} \angle CAB \equal{} \angle ABH \equal{} \angle QB_1P$. Then $ PQB_1C_1$ is cyclic, and $ AQP$ is similar to $ AC_1B_1$.
As $ \angle C_1AO_2 \equal{} 90^{o} \minus{} \angle AB_1C_1 \equal{} 90^{o} \minus{} \angle PQA$, we get that $ O_2A$ is perpendicular to $ PQ$.

But then both $ O_2A$ and $ O_2O_1$ are perpendicular to $ PQ$, and $ A$, $ O_1$ and $ O_2$ are collinear.

[hide="Special Cases"]
If $ H$ is outside $ ABC$, the same proof holds, if you work with directed angles.

If $ H \equal{} A$, $ O_1$ and $ O_2$ are the midpoints of $ BC$ and $ B_1C_1$, respectively. As $ B_1$ and $ C_1$ are the reflections of $ B$ and $ C$ over $ A$, respectively, $ A$, $ O_1$ and $ O_2$ are collinear.

If $ H \equal{} B$, $ K_1$ and $ K_4$ are tangent (if $ O_4$ is the center of $ K_4$, we have $ \angle O_4BA \plus{}  \angle CBO_1 \equal{} \angle ABC \equal{} 90^{o}$, because $ O_4$ is the reflection of $ O$ over $ AB$. Then it is clear that $ \angle O_4BO_1 \equal{} 180^{o}$) and the rest of the proof holds.

If $ H \equal{} C$, $ K_1$ and $ K_3$ are tangent.

If $ \angle CAB \equal{} 45^{o}$, $ P$ and $ Q$ are points at the infinity. This means $ O_1$, $ O_2$ and the center of $ K_3$ are collinear, and $ O_1$, $ O_2$ and the center of $ K_4$ are collinear. This can only happen if $ O_1$ = $ O_2$ (because the centers of $ K_1$, $ K_2$, $ K_3$ cannot be collinear, as they are the reflections of $ O$ over $ BC$, $ AC$ and $ AB$, and $ O$ is not on the circumcircle of $ ABC$)
[/hide]

[b][u]Solution[/u].[/b] First, let's introduce some new points:
\[ \bigoplus \ \ \ \boxed{\begin{array}{l} M \minus{} \mathrm{ midpoint \ of }\ [AC], \ N \minus{} \mathrm{midpoint \ of}\ [AB], \ P \minus{} \mathrm{midpoint \ of} \ [BC] \\
 \\
M_1 \minus{} \mathrm{midpoint \ of}\ [AC_1], \ N_1 \minus{} \mathrm{midpoint \ of}\ [AB_1] \\
 \\
O_2 \equal{} \mathrm{sim}_{AC}\ O, \ O_3 \equal{} \mathrm{sim}_{AB}\ O, \ O' \equal{} O_3 M_1 \ \cap\ O_2 N_1 \\
 \\
S \equal{} \mathrm{pr}_{O'M_1} \ O_1, \ T \equal{} \mathrm{pr}_{O'N_1} \ O_1\end{array}}\]

Now, it's obvious to observe that $ O'$ is the circumcenter of $ \triangle{AB_1 C_1}.$ We have:

$ O_1\in AO' \ \Longleftrightarrow\ \frac {\mathrm{d}(A;O'O_3)}{\mathrm{d}(A;O'O_2)} \equal{} \frac {\mathrm{d}(O_1;O'O_3)}{\mathrm{d}(O_1;O'O_2)} \ \Longleftrightarrow\ \frac {AM_1}{AN_1} \equal{} \frac {OS}{OT} \ \Longleftrightarrow$

$ \Longleftrightarrow \ \frac {AC}{AB} \equal{} \frac {O_1O_3}{O_1O_2}\cdot\frac {\cos{\widehat{SO_1O_3}}}{\cos{\widehat{TO_1O_2}}}$

$ \bullet$ Note that: $ \triangle{ABC}\ \equiv\ \triangle{O_1 O_2 O_3}\ \Longrightarrow\ \frac {O_1O_3}{O_1O_2} \equal{} \frac {AC}{AB}\dots\dots (*)$

$ \bullet$ We also have:

$ \angle{SO_1O_3} \equal{} \angle{(O_3O_1;SO_1)} \equal{} \angle{(AC; AC_1)} \equal{} \angle{(AB_1; AB)} \equal{}$

$ \equal{} \angle{(O_1T; O_1O_2)} \equal{} \angle{TO_1O_2}\ \Longrightarrow\ \cos{\widehat{SO_1O_3}} \equal{} \cos{\widehat{TO_1O_2}}\dots\dots (**)$

According to $ (*)$ and $ (**)$ we get the result.

I denote:

$ \boxed{\begin{array}{l} \mathrm{sim_{YZ}\ X} \minus{} \mathrm{the \ reflection \ of} \ X \ \mathrm{across \ line} \ YZ \\
 \\
\mathrm{d(X,YZ)} \minus{} \mathrm{the\ distance\ between}\ X \ \mathrm{and} \ YZ \\
 \\
\mathrm{pr_{YZ}\ X} \minus{} \mathrm{the \ projection\ of\ point}\ X\ \mathrm{onto\ line}\ YZ \end{array}}$

[quote]A triangle $ ABC$ is given. Let $ B_1$ be the reflection of $ B$ across the line $ AC$, $ C_1$ the reflection of $ C$ across the line $ AB$, and $ O_1$ the reflection of the circumcentre of $ ABC$ across the line $ BC$. Prove that the circumcentre of $ AB_1C_1$ lies on the line $ AO_1$.

[i]Proposed by A. Akopyan[/i][/quote]

We note that if we let $ ABC$ be a triangle with $ H$ is its orthocenter. Denote $ H_a,H_b,H_c$ respectively by the projections of $ H$ onto $ BC,CA,AB$. Let $ P_b,P_c$ respectively be the intersections of $ H_aH_c$ with $ HB$; $ H_aH_b$ with $ HC$. Let $ K_b,K_c$ respectively be the intersections of $ (HAB)\cap ([AC])$; $ (HAC)\cap ([AB])$. Denote $ I_a,O_a,$ $ \mathcal {E}$ respectively by the circumcenters of $ (AK_bK_c)$, $ (HBC)$ and the Euler circle wrt $ \triangle ABC$. Then $ \mathcal {E}$ $ ,O_a,I_a\in d_a$. (Where $ ([PQ])$ here means the circle with diameter $ PQ$)

Indeed, consider the inversion through pole $ A$, power $ k \equal{} \overline {AH}\cdot \overline {AH_a}$ $ \equal{} \overline {AH_c}\cdot \overline {AB}$ $ \equal{} \overline {AH_b}\cdot \overline {AC}$. We have $ \mathcal {I}(A,k):$ $ H_c\mapsto B,$ $ H_b\mapsto B,$ $ H\mapsto H_a$. Therefore by $ \mathcal {I}(A,k)$, $ H_cH_a\mapsto (AHB)$, $ H_aH_b\mapsto (AHC)$, $ HB\mapsto ([AC])$ and $ HC\mapsto ([AB])$. As the result, $ P_b\mapsto K_b$ and $ P_c\mapsto K_c$ $ \Longrightarrow$ $ P_bP_c\mapsto (AK_bK_c)$, which leads to the fact that $ I_a\in d_a$ $ (*)$. In the other hand, we have $ \overline {P_bK_b}\cdot \overline{P_bA} \equal{}$ $ \overline {P_bH_c}\cdot \overline {P_bH_a} \equal{}$ $ \overline {P_bH}\cdot \overline {P_bB}$ $ \Longrightarrow$ $ \mathcal {P}_{P_b/(AK_bK_c)} \equal{}$ $ \mathcal {P}_{P_b/(H_aH_bH_c)} \equal{}$ $ \mathcal {P}_{P_b/(HBC)}$. With the same argument for $ P_c$. Then it is followed that $ P_bP_c$ is the radical axes of $ (H_aH_bH_c)$, $ (HBC)$ and $ (AK_bK_c)$ $ \Longrightarrow$ $ \mathcal {E},$ $ O_a$ and $ I_a$ are collinear and $ \overline {\mathcal {E}O_aI_a}\perp P_bP_c$ $ (**)$. From $ (*)$ and $ (**)$, we obtain result. $ \square$

Back to our problem. Let $ K_b,K_c$ respectively be the intersections of $ (HAB)\cap ([AC])$; $ (HAC)\cap ([AB])$ and $ H_a,H_b,H_c$ respectively be the projections from $ H$ onto $ BC,CA,AB$.In order to prove the circumcenter $ I_a$ of $ \triangle AB_1C_1$ $ \in AO_1$ and also by the notice mentioned above, which is $ A,O_a,O_1$ are collinear- where $ O_a$ is the circumcenter of $ \triangle AK_bK_c$; we will prove that $ A,I_a,O_a$ are collinear. Indeed:

Consider the inversion through pole $ A$, power $ k \equal{} \overline {AH}\cdot \overline {AH_a}$ $ \equal{} \overline {AH_c}\cdot \overline {AB}$ $ \equal{} \overline {AH_b}\cdot \overline {AC}$. We have $ \mathcal {I}(A,k):$ $ (AK_bK_c)\mapsto K_bK_c$ $ \equiv P_bP_c$ $ (*)$- where $ P_b,P_c$ respectively are the intersections of $ H_aH_c,HB$ and $ H_aH_b,HC$. In the other hand, since $ C_1$ is the reflection of $ C$ wrt $ AB$ $ \Longrightarrow$ $ (C_1A,C_1B)$ $ \equiv (CB,CA)$ $ \equiv (HA,HB)$ $ \pmod \pi$, which implies that $ C_1\in (HAB)$, also note that $ C_1\in CH_c$. Now, we have known that $ \mathcal {I}(A,k):$ $ (AHB)\mapsto H_cH_a$ and $ CH_c\mapsto ([AB])$. Therefore if $ C_1\mapsto Q_c$ then $ Q_c\equiv H_aH_c\cap ([AB])$. With the same argument, we also conclude $ Q_b\equiv H_aH_b\cap ([AC])$. $ \mathcal {I}(A,k):$ $ (AC_1B_1)\mapsto Q_cQ_b$ $ (**)$.

In the other hand, we have $ (H_bA,H_bQ_c)\equiv (H_aA,H_aQ_c)$ $ \pmod \pi$ but $ (H_aA,H_aH_c)\equiv (CA,CH_c)$ $ \equiv (H_bA,CH_c)$ $ \pmod \pi$ $ \Longrightarrow$ $ CH_c\| Q_cH_b$. With the same argument, we also have $ Q_bH_c\| P_bH_b$. Therefore, by the [i]Pappus theorem[/i] apply for $ \begin{vmatrix}H_c & Q_c & P_b \\
H_b & P_c & Q_b\end{vmatrix}$, we have $ H_cP_c\cap Q_cH_b\equiv \infty$, $ H_cQ_b\cap P_bH_b\equiv \infty$, thus $ Q_cQ_b\cap P_bP_c\equiv \infty$, which implies that $ Q_cQ_b\|P_cP_c$. From $ (*)$ and $ (**)$, we conclude that $ (AB_1C_1)$ tangents to $ (AK_bK_c)$ at $ A$, which leads to the fact that $ A,I_a,O_a$ are collinear. Our proof is completed then. $ \square$

It’s easy to see that $ AO_1$ passes through the center $ N$ of nine-point circle of triangle $ ABC.$
We want to have the center of $ (AB_1C_1)$ lies on $ AN$ therefore the A-altitude of triangle $ AB_1C_1$ must pass through the isogonal conjugate point $ K$ of $ N$ wrt triangle $ ABC$ ( [b]Kosnita[/b] point).
We know that $ AK$ passes through the circumcenter $ J$ of triangle $ BOC$.
So $ AJ\perp B_1C_1 \Leftrightarrow AB^2_1 - AC^2_1 = JB^2_1 - JC^2_1$
$ \Leftrightarrow 4R^2(\sin^2 C - \sin^2 B) = (B_1C^2 + CJ^2 - 2B_1C.JC.\cos \angle B_1CJ - BC_1^2 - BJ^2 + 2BC_1.BJ.\cos \angle C_1BJ)$
$ \Leftrightarrow 4R^2(\sin^2 C - \sin^2 B) = 2BC.R_{BOC}(\cos \angle C_1BJ - \cos \angle B_1CJ)$
$ \Leftrightarrow 4R^2(\sin^2 C - \sin^2 B) = 2R.\sin A.\frac {R}{\cosh}.(\cos(2A + 2B - 90^o) - \cos (2A + 2C - 90^o))$
$ \Leftrightarrow 2(\sin C - \sin B)(\sin C + \sin B) = \tan A(\sin2B - \sin2C)$ (right!)
We are done.

Sorry for digging up old posts but here's my solution to this problem. See attachment..

if $M$ is the midpoint of $AB$ and $D=BB_{1}\cap  AC$ then clearly $AMO\sim ADC$ where $O$ is the circumcenter of $ABC$. so $BO*BD=BM*BC$ so $BB_{1}*BO=BA*BC$ but $\angle O_{1}BA=\angle B_{1}BC_{1}$ so $BB_{1}C_{1}\sim BO_{1}A$ and $\angle BAO_{1}=\angle BB_{1}C_{1}$ if $L$ is the circumcenter of $AB_{1}C_{1}$ then
$\angle C_{1}AO_{1}=\angle C_{1}AB+\angle BAO_{1}=\angle BAC+\angle BB_{1}C_{1}=90-\angle BB_{1}A+\angle BB_{1}C_{1}=90-\angle C_{1}B_{1}A=\angle C_{1}AL$ so $L$ is on $AO_{1}$

Well, I used the same similar triangle pair of leader, but my finishing is a bit different.
[hide="Proof"]Let $O,O_2$ be the circumcenter of $ABC$ and $ABC_1$, resp. and the perpendicular bisector of $AC_1$ meets $AO_1$ at $R$. Easy to prove $AO_2||CO_1\implies AO_2O_1C$ is a parallelogram. Also note that $\angle O_1CA=\angle C_1CB_1$ and $\frac {AC}{R}=2\sin B\implies \frac {AC}{CO_1}=\frac {CC_1}{CB_1}$. Thus $CAO_1\sim CC_1B_1\implies 180-(\angle B+\angle C_1B_1A)=180-\angle CB_1C_1=180-\angle CO_1A$ $=180-\angle O_2AO_1=90-\angle B+\angle RAC_1\implies \angle RAC_1=90-\angle C_1B_1A$. Since $RAC_1$ is isosceles, we get $\angle C_1RA=2\angle C_1B_1A$. So $R$ is the circumcenter of $AB_1C_1$.[/hide]

This problem is the combination of two properties of nine point center :)

$ (1) $

Let $ O' $ be the reflection of the circumcenter $ O $ of $ \triangle ABC $ in $ BC $ .
Then the nine point center of $ \triangle ABC $ lie on $ AO' $ .

$ (2) $

Let $ A', B', C' $ be the reflection of $ A, B, C $ in $ BC, CA, AB $ .
Then $ \triangle A'B'C' $ is homothety with the pedal triangle of the nine point center of $ \triangle ABC $ .

Just consider point $F$ such that $<FO1B=<BAC$ and $<O1BF=<CBA$.Now,we have spiral similarity with center B that pictures $BFO1$ in $BCA$ so we have that $BO1A$ is similar to $BFC$ and we have that $FO1C$ is similar to $AB1C1$,so from here it is pure angle chasing,so we are finished.

An extension.

Let $ABC$ be a triangle inscribed incircle $(O)$. $P$ is an any point. $PC,PB$ cut $(O)$ again at $M,N$. $E,F$ are reflections of $B,C$ through $AM,AN$. $K,L$ are circumcenters of triangles $AEF$ and $PBC$. $G$ is inversion image of $L$ through $(O)$. Prove that $\angle KAG=180^\circ-|\angle NAB-\angle MAC|$.

See the figure in the case $P$ outside $(O)$. When $PB,PC$ are tangent to $(O)$ we get Tuymaada problem.

[quote=buratinogigle]An extension.

Let $ABC$ be a triangle inscribed incircle $(O)$. $P$ is an any point. $PC,PB$ cut $(O)$ again at $M,N$. $E,F$ are reflections of $B,C$ through $AM,AN$. $K,L$ are circumcenters of triangles $AEF$ and $PBC$. $G$ is inversion image of $L$ through $(O)$. Prove that $\angle KAG=180^\circ-|\angle NAB-\angle MAC|$.

[/quote]
By simple angle chasing $ \Longrightarrow $ $ \measuredangle EMP $ $ = $ $ \measuredangle FNP, $ so combining $ \tfrac{EM}{PM} $ $ = $ $ \tfrac{BM}{PM} $ $ = $ $ \tfrac{CN}{PN} $ $ = $ $ \tfrac{FN}{PN} $ and $ \triangle BPL $ $ \stackrel{+}{\sim} $ $ \triangle BMO $ $ \stackrel{+}{\sim} $ $ \triangle BEA $ we get $ \triangle PME $ $ \stackrel{+}{\sim} $ $ \triangle LOA $ $ \stackrel{+}{\sim} $ $ \triangle PNF, $ hence $ \measuredangle (MN, EF) $ $ = $ $ \measuredangle (OL,AL) $ $ \Longrightarrow $ $ \measuredangle (AL, \perp EF) $ $ = $ $ \measuredangle (BC, MN) $ $ (\star) $ $.$ On the other hand, it's easy to see that the angle between the bisector of $ \angle BAC $ and $ \angle EAF $ is equal to $ \measuredangle (BC, MN), $ so from $ (\star) $ and notice $ AG, $ $ AL $ are isogonal conjugate WRT $ \angle A $ (well-known) we conclude that $ \measuredangle (AG, AK) $ $ = $ $ \measuredangle (BC, MN). $

Another proof. Let $O_a, O_b, O_c, J$ be the circumcenters of triangles $BHC, CHA, AHB$, $AB_1C_1$. By simple angle chasing, $\angle O_bOO_c=\angle OO_bJ=\angle OO_cJ=180^\circ-\angle BAC$. From lemma in my post at [url=http://www.artofproblemsolving.com/community/u57217h458563p6500835]here[/url], we get $J$ lies on Euler line of triangle $OO_bO_c$ or $J,A,O_a$ are collinear.

Let $B_2,C_2,C_3,B_3$ be projections of $B,C,C_1,B_1,$ onto lines $AC_1,AB_1.$ Also let $U \equiv B_2B \cap C_2C.$

Easy angle chasing shows us that $\angle O_1BC=\angle O_1BC=\angle ACC_2=\angle ABB_2=\frac{\pi}{2}-\alpha$ while $\angle B_2AB=\angle CAC_2=\alpha.$ Hence by Jacobi theorem on hexagon $AB_2BO_1CC_2$ we deduce that $B_2C,BC_2,AO_1$ concur at $V.$

By Dual of Desargues Involution theorem it follows that $AB_2 \mapsto AC_2, AB \mapsto AC, AU \mapsto AV$ is involution which then coincides with reflection over A-angle bisector. Hence $\angle BAV=\angle CAU$ so easy angle chasing gives us $AV \perp B_2C_2.$ Since $V$ lies on $AO_1$ it follows that $AO_1 \perp B_2C_2.$

Note that $\frac{AB_2}{AC_2}=\frac{AB}{AC}=\frac{AB_1}{AC_1} \implies C_1B_2C_2B_1$ is cyclic. But $C_1C_3B_3B_1$ is also cyclic, hence by Reim's theorem it follows that $B_2C_2 \parallel B_3C3 \implies AO_1 \perp B_3C_3 \implies$ center of $\odot(AB_1C_1)$ lies on $AO_1$ as desired.

Complex numbers rule!!!
Let $(ABC)$ be the unit circle.Denote with $x$ the affixe of point $X$.We have:
$$b_1=a+c-a\overline{b}c,c_1=a+b-ab\overline{c},o_1=b+c$$
By making a translation  which takes $A$ to the origin we have to show that the circumcenter $o_2$ of $0(b_1-a)(c_1-a)$ lies on the line $0(o_1-a)$.
It is known that the circumcenter of $0xy$ is $o=\frac{xy(\overline{x}-\overline{y})}{\overline{x}y-x\overline{y}}$,so
$o_2=\frac{(c-a\overline{b}c)(b-ab\overline{c})(\overline{c-b+a(b\overline{c}-\overline{b}c)})}{(\overline{c-a\overline{b}c})(b-ab\overline{c})-(c-a\overline{b}c)\overline{b-ab\overline{c}}}=\frac{cb(1-\frac{a}{b})(1-\frac{a}{c})\frac{b-c}{bc}(1-\frac{\overline{a(b+c)}}{\overline{bc}})}{\frac{b}{c}(1-\frac{b}{a})(1-\frac{a}{c})-\frac{c}{b}(1-\frac{c}{a})(1-\frac{a}{b})}=\frac{\frac{b-c}{bc}(-1+\frac{\frac{b+c}{bca}}{\frac{1}{bc}})}{\frac{b}{ac^2}-\frac{c}{ab^2}}=\frac{bc(b-c)(b+c-a)}{b^3-c^3}=(b+c-a)\cdot \frac{bc}{b^2+bc+c^2}$.
Now,just note that $\frac{o_2}{o_1-a}=\frac{bc}{b^2+bc+c^2}=\frac{\frac{1}{bc}}{\frac{1}{b^2}+\frac{1}{bc}\frac{1}{c^2}}=\overline{\frac{bc}{b^2+bc+c^2}}\Rightarrow \frac{o_2}{o_1-a}\in\mathbb{R}\Rightarrow o_2 \text{ is on } 0(o_1-a)$  $\square$