trigonometry
analytic geometry
rotation
complex numbers

Prove that if $a_1,a_2,a_3$ are (distinct) complex numbers that satisfy $a_1^2+a_2^2+a_3^2=a_1a_2+a_2a_3+a_3a_1$, then they form an equilateral triangle in the complex plane.

multiply both sides by 2, make squares: $(a_1-a_2)^2+(a_1-a_3)^2+(a_2-a_3)^2=0$, which can be written like $[(a_1-a_3)+(a_3-a_2)]^2+(a_1-a_2)^2=2(a_1-a_3)(a_3-a_2)$.  This simplifies to $(a_1-a_2)^2=(a_1-a_3)(a_3-a_2)$.  take complex magnitudes of both sides to get

$|(a_1-a_2)|^2=|(a_1-a_3)||(a_3-a_2)|$.

Denote $x=|a_1-a_2|, y=|a_1-a_3|, z=|a_3-a_2|$, and we have $x^2=yz$.  Similarly we can get $y^2=xz$ and $z^2=xy$.  Adding all 3 eqns and multiplying by 2 we have $(x-y)^2+(y-z)^2+(x-z)^2=0$.  Since $x, y, z$ are real, $x=y=z$.

Sure, that works.

Any equilateral triangle triangle in the complex plane can also be represented as the roots of $(z-p)^3=q$.  Can you prove that $a_1,a_2,a_3$ are the roots of such an equation?

$a_1^2+a_2^2+a_3^2-a_1a_2-a_2a_3-a_3a_1=0$

$\Longleftrightarrow a_3^2-(a_1+a_2)a_3+a_1^2-a_1a_2+a_2^2=0$

$\Longleftrightarrow \left(a_3-\frac{a_1+a_2}{2}\right)^2=-\frac{3}{4}(a_2-a_1)^2$

$\Longleftrightarrow a_3-\frac{a_1+a_2}{2}=\pm \frac{\sqrt{3}}{2}(a_2-a_1)i$

$\Longleftrightarrow a_3-a_1=(a_2-a_1)\left(\frac{1}{2}\pm \frac{\sqrt{3}}{2}i\right)$

$\Longleftrightarrow a_3-a_1=(a_2-a_1)\left\{\cos \left(\pm \frac{\pi}{3}\right)+i\sin \left(\pm \frac{\pi}{3}\right)\right\}$

$\Longleftrightarrow \triangle a_1a_2a_3$ is equilateral triangle.  Q.E.D.

Here is my solution.

We have $(a_1+a_2+a_3)^2=3(a_1a_2+a_2a_3+a_3a_1)$.  Set $a_1+a_2+a_3=3t$

Therefore we have $(z-a_1)(z-a_2)(z-a_3)=z^3-3tz^2+3t^2-(t^3+u)$ for some $u\in\mathbb{C}$.

Hence $(z-t)^3=u$ for some $t,u$.  The result follows.

(Lars) Ahlfors is the author of a famous graduate-level/advanced undergraduate-level textbook on Complex Analysis.  In it, he tries to build up some geometric intuition for working with complex numbers, and this is one of the questions that appears in that section.

[quote="kunny"]$a_{1}^{2}+a_{2}^{2}+a_{3}^{2}-a_{1}a_{2}-a_{2}a_{3}-a_{3}a_{1}=0$

$\Longleftrightarrow a_{3}^{2}-(a_{1}+a_{2})a_{3}+a_{1}^{2}-a_{1}a_{2}+a_{2}^{2}=0$

$\Longleftrightarrow \left(a_{3}-\frac{a_{1}+a_{2}}{2}\right)^{2}=-\frac{3}{4}(a_{2}-a_{1})^{2}$

$\Longleftrightarrow a_{3}-\frac{a_{1}+a_{2}}{2}=\pm \frac{\sqrt{3}}{2}(a_{2}-a_{1})i$

$\Longleftrightarrow a_{3}-a_{1}=(a_{2}-a_{1})\left(\frac{1}{2}\pm \frac{\sqrt{3}}{2}i\right)$

$\Longleftrightarrow a_{3}-a_{1}=(a_{2}-a_{1})\left\{\cos \left(\pm \frac{\pi}{3}\right)+i\sin \left(\pm \frac{\pi}{3}\right)\right\}$

$\Longleftrightarrow \triangle a_{1}a_{2}a_{3}$ is equilateral triangle.  Q.E.D.[/quote]

I followed all your factorizations and simplifications, but I don't understand why the last statement implies that the triangle is equilateral. What I'm most confused by however, is that since points $a$, $b$, and $c$ are in the complex plane, why can't one prove the equality, by saying that $a$=$c+di$, $b$=... and so on, and then use the distance formula or something...I tried it but it turned out really ugly, and I don't think it works... Any help would be appreciated!

Putting down coordinates is a really ugly way of approaching the problem.  It works in theory, but it's good to be able to solve problems without bashing.

As for kunny's solution, what the last line asserts is that the 'side' $a_{3}-a_{1}$ is the same as the side $a_{2}-a_{1}$ rotated $60$ degrees clockwise, as well as the side $a_{2}-a_{1}$ rotated $60$ degrees counterclockwise.

[quote="blahblahblah"]Putting down coordinates is a really ugly way of approaching the problem.  It works in theory, but it's good to be able to solve problems without bashing.[/quote]
Yeah, I know, except I'm very new at this material, , and directly manipulating the equation seems like doing operations with points and not quantities... and thats really weird...(again its's because this stuff is unfamiliar)

[quote="blahblahblah"]As for kunny's solution, what the last line asserts is that the 'side' $a_{3}-a_{1}$ is the same as the side $a_{2}-a_{1}$ rotated $60$ degrees clockwise, as well as the side $a_{2}-a_{1}$ rotated $60$ degrees counterclockwise.[/quote]
Thanks, I understand this solution now  :lol:

[quote="me@home"]Operations with points and not quantities? What do you mean?[/quote]
The triangle is defined in the complex plane with complex numbers say $a$, $b$, and $c$ as its vertices (which gave me the impression I was working with points)...directly using $a$, $b$, and $c$ in equations seems like doing operations with points...I think it's because I'm so used to the euclidean plane, and I have very little experience with vectors.

this is equivalent to $x^{2}+y^{2}+z^{2}=0=x+y+z\implies x,y,z$ are verticies of an equilateral triangle, where $\{x,y,z\}\subset\mathbb{C}$

[hide="solution"]$-z=x+y$, substitute, then $x^{2}+xy+y^{2}=0$, $x=e^\frac{\pm2i\pi}{3}\cdot y$, $|x|=|y|$, result follows[/hide]

this problem is also pretty much owned by using the factorization formulas developed in mathematical olympiad treasures

"Factorization formulas in mathematical olympiad trasures"?

$\sum a^{2}-\sum_{cyc}ab=(a+b\omega+c\omega^{2})(a+b\omega^{2}+c\omega)$

where $\omega^{3}=1$, $\omega\ne 1$

thats cool to know
does it hold for higher roots of unit in larger symmetric sums/diffs


geometry
number theory unsolved
number theory

Solve the diophantine (with elementary tools) : $x^4+y^4=17z^4$.

With elementary tools? jaja This is not a nice condition!

Really, what do you consider by "elementary tools"?

Without $\mathbb{Z}[i]$ and other similar things ;)

I guess there are some people interested in advanced solutions also so Pascual please try it!
Anyway, here is something that pretends to be useful.
Lemma:
If $u^2+v^2=x^2+y^2$ are not all odd then there are integers $a,b,c,d$ with $u=ac+bd, v=ac-bd, x=ad+bc, y=ac-bd$.
Proof is quite easy, i guess ;) just write $u^2-x^2=y^2-v^2$ and factorize.
Pick up a minimal solution (so $gcd(x,y)=1$ and others).
Now apply lemma to $x^2, y^2, z^2, 4z^2$.
Thus we get a system of four equations.
$ac+bd=x^2$, $ad-bc=y^2$, $ad+bc=4z^2$ and $ac-bd=z^2$.
Now from last two equations we express $c,d$ by $a,b,z$:
$c=\frac {a+4b}{a^2+b^2} z^2$
$d=\frac {4a-b}{a^2+b^2} z^2$.
Now we get that $x^2,y^2$ are $\frac {4a^2-2ab-b^2}{a^2+b^2}$ and $\frac {a^2+8ab-b^2}{a^2+b^2}$.
Now we easily prove that $a^2+b^2, 4a^2-2ab-b^2, a^2+8ab-b^2$ are coprime so they are perfect squrea.
Now let's prove that $b=0$.
Indeed suppose not.
Then we see that $a$ is odd and $b$ is even, moreover divisible by $4$.
However, the last expression is $t^2=(a+4b)^2-17b^2$
Thus we get $17b^2=(a+4b-t)(a+4b+t)$ and we now deduce the last factors are $2u^2, 34v^2$.
Thus we get $a+4b=u^2+17v^2$. Howver $b=2uv$ and so $a=u^2+17v^2-8uv=(u-4v)^2+v^2$.
But since $a^2+b^2$ is a perfect square we get $b=2rs$ and $a=r^2-s^2$
The second equation writes $4h^2=(4a-b)^2-5b^2$ thus $(4a-b)^2-4h^2=5b^2$.
Now as above we get $4a-b=4(k^2+5l^2), b=4kl$ hence $a=k^2+5l^2+kl$

I have an approach using algebraic geometry [I'm learnin it so I have to test it somewhere  :D ]. Put $a=\frac{x^2}{z^2}$, $b=\frac{y^2}{z^2}$ to get $a^2+b^2=17$ so now we're looking for rational solutions of $a,b$. Draw a line through $(4,1)$ with coefficient $t$, I mean: $b=t(a-1)+4$ . From equation:

$a^2 +t^2(a-1)^2+8t(a-1)+16=17$ we get:

$a=\frac{t^2-8t-1}{t^2+1}$
from this

$b=\frac{-4t^2-2t+4}{t^2+1}$

now plugging $t=\frac{m^2}{n^2}$ into $a,b$ we characterize $x,y,z$ and so get the solutions of the first equation.

Is it correct?

$Zi$ tools only give your first lemma. The rest is the same! :)


30. Consider the 16 points in the first quadrant of a Cartesian coordinate plane with integer corrdinates less than or equal to 4. How many squares can be formed using four of tese points as vertices?

I only get 18.. what the heck.. Can you guys point out the missing ones?
I get the ones that look like a square(1x1,2x2,3x3) and there are 14. Then I counted for rhombus looking ones, (with the sides length of $ \sqrt{2}$) and I find 4 of those...
[hide="Answer"]20 squares[/hide]

There also two squares that have side length $ \sqrt{5}$


Could someone please explain the Mobius Mu Function and the Mobius Inversion Rule?

Also, what are their revelance to problem solving if they have any?  Please show an example or link to a problem involving it if possible.

One of the motivations for the Mobius function comes from the Principle of Inclusion-Exclusion.

Specifically, it turns out that using PIE you can show that

$\varphi(m) = m \prod_{p \in \mathbb{P}, p | m}\left( 1-\frac{1}{p}\right) = \sum_{d > 0, d | m}\mu(d) \frac{n}{d}$

(Expand the product to get the sum.)  This leads to our definition.

$\mu(1) = 1$
$\mu( p_{1}p_{2}... p_{k}) = (-1)^{k}$ (distinct primes $p_{i}$)
$\mu(n) = 0$ otherwise.

This function also has a rather amazing property with respect to arithmetic functions (functions on the positive integers).  If $f(n), g(n)$ are arithmetic functions such that

$f(n) = \sum_{d > 0, d | n}g(d)$

Then

$g(n) = \sum_{d > 0, d | n}\mu(d) f( \frac{n}{d})$

This leads to a variety of interesting results.  For example, the above result I mentioned concerning $\varphi$ can be inverted in the opposite direction to produce

$n = \sum_{d > 0, d | n}\varphi(d)$

I wouldn't say that the Mobius function is relevant to other areas of problem solving, but it's a very interesting number theoretic function its own right - the subject of its own problems.


Let $a,b,c$ be positive real numbers. Prove the inequality
\[\frac{a^2}{b}+\frac{b^2}{c}+\frac{c^2}{a}\geq a+b+c+\frac{4(a-b)^2}{a+b+c}.\]
When does equality occur?

Hi [b]zhaoli[/b],

Thanks for the problem, but do you know the other BMO problems?? If so, can you please post them.

Regards,
Zhivko

Rewrite the intial inequality to: $\frac{(a-b)^2}{b}+\frac{(b-c)^2}{c}+\frac{(c-a)^2}{a} \geq \frac{4(a-b)^2}{a+b+c}$. This is equivalent to $(a+b+c)\left(\frac{(a-b)^2}{b}+\frac{(b-c)^2}{c}+\frac{(c-a)^2}{a} \right) \geq 4(a-b)^2$. Using [b]Cauchy[/b] one can prove $(a+b+c)\left(\frac{(a-b)^2}{b}+\frac{(b-c)^2}{c}+\frac{(c-a)^2}{a} \right) \geq 4$ $($[b]max[/b]$(a,b,c)-$[b]min[/b]$(a,b,c)$$)^2$.
[i]q.e.d.[/i]

Nice solution! I always don't know how to deal with some non-symmetric inequalities.  :)

The problems of Balkan Mathematical Olympiad from 1984-2003 can be found [url=http://www.mathlinks.ro/Forum/resources.php?cid=19]here[/url]

The problems of Balkan Mathematical Olympiad from 2004 can be found at:
http://www.artofproblemsolving.com/Forum/topic-5591.html

Jivko, look better, they are in the corresponding subforums.  ;)

[quote="jivko777"]Yes, [b]harazi[/b], but some of us are only looking in the algebra section  :lol: ... and are expecting to find all the BMO 2005 problems there.

Thanks, [b]harazi[/b]!
Zhivko[/quote]Check out this thread: http://www.mathlinks.ro/Forum/viewtopic.php?t=36018 ;)

[quote="Andrei"]Using [b]Cauchy[/b] one can prove $(a+b+c)\left(\frac{(a-b)^2}{b}+\frac{(b-c)^2}{c}+\frac{(c-a)^2}{a} \right) \geq 4$ $($[b]max[/b]$(a,b,c)-$[b]min[/b]$(a,b,c)$$)^2$.
[i]q.e.d.[/i][/quote]
I don't understand about it.Could you explain anymore?

[quote="mathpk"]Thank you very very much.[/quote]

Equality hold iff one of twe cases occur :

  (1).a=b=c ;

  (2).  c=ωb and a=ωc ,where ω=(5^1/2-1)/2.

[quote="jivko777"]Thanks [b]zhaoli[/b], but what I meant were the problems from BMO 2005 (you posted only the third one). Well anyways, they will certainly appear at some point.

Regards,
Zhivko[/quote]

 you can find the questions of bmo 2005 at http://www.rms.unibuc.ro/balkan.html

[quote="ciprian"]With Lagrange you have a^2/b+b^2/c+ c^2/a - (a+b+c)= (  (ac-b^2)^2/bc + (bc - a^2)^2/ab + (ab-c^2)^2/ac )/a+b+c. [/quote]

who on earth can you obtain smth like this?

[quote="Andrei"]Rewrite the intial inequality to: $\frac{(a-b)^2}{b}+\frac{(b-c)^2}{c}+\frac{(c-a)^2}{a} \geq \frac{4(a-b)^2}{a+b+c}$.
[i]q.e.d.[/i][/quote]

I guess the given inequality can be rewritten as :
$\frac{(a^2-b^2)}{b}+\frac{(b^2-c^2)}{c}+\frac{(c^2-a^2)}{a} \geq \frac{4(a-b)^2}{a+b+c}$.

Not as Andrei stated it to be.......Now how will you solve it? :?

Andrei's right. We do the calculation $a^2/b -2a+b$

Is this problem hard or easy for those who have solved it ?!?!?!

[quote="ciprian"]You just use Lagrange identity  for 3 numbers :)[/quote]

i forgot about this! what's lagrange identity?

thanks :D

i think i have seen it in Kedlaya's notes

[quote="ciprian"]With Lagrange you have a^2/b+b^2/c+ c^2/a - (a+b+c)= (  (ac-b^2)^2/bc + (bc - a^2)^2/ab + (ab-c^2)^2/ac )/a+b+c. So you have to prove that  (ac-b^2)^2/bc + (bc - a^2)^2/ab + (ab-c^2)^2/ac  >=  4(a-b)^2.But (ab-c^2)^2/ac   >=  0 and (ac-b^2)^2/bc + (bc - a^2)^2/ab  >=  (ac-b^2-bc+a^2)^2/b(a+c) =(a-b)^2(a+b+c)^2/b(a+c). With AM-GM you have b(a+c) <= (a+b+c)^2/4 so (a-b)^2(a+b+c)^2/b(a+c) >= 4(a-b)^2. We get a^2/b+b^2/c+ c^2/a - (a+b+c) >= 4(a-b)^2/(a+b+c). :D[/quote]

Could someone explain it to me with more details?

We have $\dfrac{a^2}{b}+\dfrac{b^2}{c}+\dfrac{c^2}{a}\geq a+b+c+\dfrac{4(a-b)^2}{a+b+c} \Leftrightarrow$

$\dfrac{a^2}{b} + b - 2a +\dfrac{b^2}{c} + c - 2b +\dfrac{c^2}{a}+ a - 2c \geq \dfrac{4(a-b)^2}{a+b+c} \Leftrightarrow$

$\dfrac{(a-b)^2}{b} + \dfrac{(b-c)^2}{c} + \dfrac{(c-a)^2}{a} \geq \dfrac{4(a-b)^2}{a+b+c}$

Furthermore, by Cauchy, we have that $\dfrac{(a-b)^2}{b} + \dfrac{(a-b)^2}{a+c} \ge \dfrac{4(a-b)^2}{a+b+c}$

Therefore, its enough to prove that

$\dfrac{(a-b)^2}{b} + \dfrac{(b-c)^2}{c} + \dfrac{(c-a)^2}{a} \geq \dfrac{(a-b)^2}{b} + \dfrac{(a-b)^2}{a+c} \Leftrightarrow$

$(a+c) \left ( \dfrac{(b-c)^2}{c} + \dfrac{(c-a)^2}{a} \right ) \ge (a-b)^2$, which is also Cauchy.

Let $a_1,a_2,\cdots,a_n$ be positive real numbers. Prove the inequality\[\frac{a_1^2}{a_2}+\frac{a_2^2}{a_3}+\cdots+
\frac{a_{n-1}^2}{a_n}+\frac{a_n^2}{a_1}\geq a_1+a_2+\cdots+a_n+\frac{4(a_1-a_2)^2}{a_1+a_2+\cdots+a_n}.\]
$\Leftrightarrow $\[ \frac{(a_1-a_2)^2}{a_2}+\frac{(a_2-a_3)^2}{a_3}+\cdots+
\frac{(a_{n-1}-a_n)^2}{a_n}+\frac{(a_n-a_1)^2}{a_1}\geq \frac{4(a_1-a_2)^2}{a_1+a_2+\cdots+a_n}.\]
http://www.artofproblemsolving.com/Forum/viewtopic.php?f=52&p=2995638

I learned too much andrei!thanks a lot:)

Fixing $ \text\LaTeX $ in ciprian's solution:

By Lagrange we have

$\frac{a^2}{b}+\frac{b^2}{c}+ \frac{c^2}{a} - (a+b+c)= \frac{ \frac{\left(ac-b^2 \right)^2}{bc} + \frac{\left(bc - a^2\right)^2}{ab} + \frac{\left(ab-c^2\right)^2}{ac}}{a+b+c}$

So we have to prove that $\frac{(ac-b^2)^2}{bc} + \frac{(bc - a^2)^2}{ab} + \frac{(ab-c^2)^2}{ac}\geq 4(a-b)^2$

But $\frac{(ab-c^2)^2}{ac}\geq 0$ and $\frac{(ac-b^2)^2}{bc} + \frac{(bc - a^2)^2}{ab} \geq \frac{(ac-b^2-bc+a^2)^2}{b(a+c)} = \frac{(a-b)^2(a+b+c)^2}{b(a+c)}$

By $\text{AM-GM}$ we have $b(a+c) \leq \frac{(a+b+c)^2}{4} \implies \frac{(a-b)^2(a+b+c)^2}{b(a+c)} \geq 4(a-b)^2$

Hence we get $\frac{a^2}{b}+\frac{b^2}{c}+ \frac{c^2}{a} - (a+b+c) \geq \frac{4(a-b)^2}{(a+b+c)}$

Let $a,b,c$ be positive real numbers. Prove the inequality
\[\frac{a^2}{b}+\frac{b^2}{c}+\frac{c^2}{a}>a+b-2c+\frac{5(a-b)^2}{a+b}.\]

Let $a,b,c$ be positive real numbers. Prove the inequality
\[\frac{a^2}{b}+\frac{b^2}{c}+\frac{c^2}{a}>2(a+b-6c)+\frac{7(a-b)^2}{a+b}\]


raaaaaaaaaaaaaaaaaar

Farenhajt posted it before I did...but my solution is almost identical to his (except I didn't substitute $S_{100}=100$ until the very end) so my solution wouldn't add any insight, really

But I totally support his answer completely since I got the same thing

Normally I wouldn't substitute it too, but this way it was easier to type in Latex  :lol:

[quote="junggi"]why is $S_{100}=100$ :?:[/quote]

Substitute $n = 100$ into the original equation.  Since $a_{n+1}$ is not in the sequence, the RHS is $100\left(1+0 \right)$ (the empty sum).


Square corners, 5 units on a side, are removed from a 20 unit by 30 unit rectangular sheet of cardboard. The sides are then folded to from an open box. The surface area, in square units, of the interior of the box is:
A) 300 unit2 B) 500 unit2 C) 550 unit2 D) 600 unit2

$ 20\cdot30\minus{}4\cdot5^2\equal{}500$
$ \boxed B$


How many diagonals does an octagon have?

20, because an octagon has 8 sides and the diagonals formula is (n/2)x(n-3), where is n is the number of sides.


analytic geometry
induction
geometry
rectangle
combinatorics unsolved
combinatorics

Let $n$ be a positive integer.

A [i]corner[/i] means a finite set $S$ of ordered $n$-tuples of positive integers such that if $a_1,a_2,...,a_n,b_1,b_2,...,b_n$ are positive integers satisfying $a_k\geq b_k$ for all $k=1,2,...,n$ and satisfying $(a_1,a_2,...,a_n)\in S$, then $(b_1,b_2,...,b_n)\in S$.

Prove that among any infinite collection of corners, there exist two corners, one of which is a subset of the other one.

The corners are actual corners of parallelepipeds in $n$ dimensions. We only need to look at the top inner point of a corner (let's call this vertex $V(S)$ or just $V$). This vertex completely characterizes the corner. We prove it for $n=2$: assume that there is $t$ s.t. infinitely many $V$'s have something $\le t$ as an $x$-coordinate (or $y$-coordinate). Then we easily find two corners s.t. one contains the other, so if we consider a corner with $V(x_v,y_v)$, then only finitely many corners have $x$-coordinate $<x_v$ (and the same goes for the $y$-coordinate), so there will be some corner which contains $V$.

I think induction is quite straightforward now..

grobber, I don't quite understand your idea with paralellipipeds and top inner points.
Can you explain it more?

Well, I'm not entirely sure what it is that you want me to explain.. I called it an "inner" vertex because it's the only vertex which is completely inside the quadrant. For example, in the rectangle $(0,0),(0,m),(n,0),(m,n)$ the vertex is $(m,n)$ the corner is the set of all lattice points inside and on the boundaries of the rectangle.

Sorry if the argument from my previous post is wrong (that certainly is a possibility :)).

Grobber, I think you misunderstood the problem. A corner may be something like {(1,2), (2,1), (1,1)}, so like a staircase.

Btw, this is from the 2000 TST, not 2002

[quote="billzhao"]Grobber, I think you misunderstood the problem. A corner may be something like {(1,2), (2,1), (1,1)}, so like a staircase.[/quote]

I think you're right. That's because I immediately assumed that there would be an $n$-tuple in the corner s.t. each of its components is maximal, but that's not true, as your example shows. I guess the problem is harder than I thought.

I've spend quite time on this but I think I solved it.
We prove for any collection of corners $C_1..C_n..$ we can select
$C{}_i{}_1..C{}_i{}_n..$ s.t. $C{}_i{}_k+1$ contains $C{}_i{}_k$ by induction on n.
For n=1 it's evident.
For n+1 if for each C_i we can have C_j j>i containing it we can construct easily.
Suppose this is false for C_1
Then for every component of C_i one of its n+1 coordinates is smaller than a constant=max{corrdinates of C_1}.
Divide the corners into finitely many classes according to this small coordinate.
Then apply IH for first class, selecting an infinite sequence, then for second and so on.

I don't understand iura's argument, could you explain it a bit more?

My fault I didn't explain well.
We prove from any sequence of corners $C_1..C_i..$ we can select an  infinite sequence $C{}_i{}_1..$ s.t. the next term contains the previous by induction on n.
For n=1 obvious.
If any$ C_i$ has a $C_j$ containing it then we can construct our sequence inductively.
Suppose not, the WLOG no $C_i$ contains $C_1$
Then form every component of the corners at least one entry is smaller than $M$=max{entries of $C_1$}.
Now divide the corner components  into M(n+1) classes pairs (k,l) meaning the entry number k is equal to $l \leq M$.
By incution we can remove some corners but leave infinitely many of them s.t.
the first class of one is contained in the first class of next element (this classe are also corners but one entry is equal at them so we can 'forget' about it and use IH)
Now repeat the procedure with the remaining corners and the second class and so on.
At the end we get what we wished


Let $1=d_1<d_2<....<d_k=n$ be all different divisors of positive integer n written in ascending order. Determine all n such that:
\[ d_7^{2} + d_{10}^{2}= \left(\frac{n}{d_{22}}\right)^{2}\]

$ n \equal{} 2040$ is the only solution.

Divisors $ d_7$, $ d_{10}$, and $ n/d_{22} \equal{} d_{k \minus{} 21}$ form a Pythagorean triple. Let $ g \equal{} \gcd(d_7,d_{10})$. Then $ d_7$ and $ d_{10}$ equal $ 2uvg$ and $ (u^2 \minus{} v^2)g$ (in some order), where $ u > v$ are coprime integers, one of which is even.
Notice that the integers $ 1,2,v,u,2v,2u,u \plus{} v,u \minus{} v$ are all smaller than $ \min\{2uv,u^2 \minus{} v^2\}$ unless $ u \minus{} v \equal{} 1$ or $ v \equal{} 1$. Consider the following cases:

1) If $ u \minus{} v > 1$ and $ v > 1$ then among $ 1,2,v,u,2v,2u,u \plus{} v,u \minus{} v$ there are at least 7 distinct integers, which is impossible.

2) If $ v \equal{} 1$ then $ d_7 \equal{} 2ug$ and $ d_{10} \equal{} (u^2 \minus{} 1)g$. In this case $ 1,2,u,u \plus{} 1,u \minus{} 1,2(u \minus{} 1)$ are the smallest 6 divisors of $ n$ (in some order), implying that $ u \equal{} 4$ and $ g \equal{} 1$. Then the smallest 7 divisors of $ n$ are $ 1,2,3,4,5,6,8$ and $ d_{10} \equal{} 15$, $ d_{k \minus{} 21} \equal{} 17$. Between $ 8$ and $ 15$ there are two divisors $ 10 \equal{} lcm(2,5)$ and $ 12 \equal{} lcm(3,4)$, i.e., $ d_8 \equal{} 10$ and $ d_9 \equal{} 12$. There are two cases:

2.1) 16 divides $ n$, inplying that $ k \minus{} 21 \equal{} 12$, i.e., $ k \equal{} 33$. But in this case $ n$ is a square while it is not divisible by $ 9$, a contradiction.

2.2) $ 16$ does not divide $ n$, implying that $ k \minus{} 21 \equal{} 11$, i.e., $ k \equal{} 32$. Trivially, we have $ n \equal{} 2^3\cdot 3\cdot 5\cdot 17 \equal{} 2040$.

3) If $ u \minus{} v \equal{} 1$ then $ d_7 \equal{} (2v \plus{} 1)g$ and $ d_{10} \equal{} 2v(v \plus{} 1)g$ (it is divisible by 4). Since $ d_7\geq 7$, we have $ v\geq 3$.
The integers $ 1,2,4,v,v \plus{} 1,2v,2v \plus{} 1,2(v \plus{} 1),2(2v \plus{} 1),v(v \plus{} 1),2v(v \plus{} 1)$ are among the smallest 10 divisors of $ n$, implying that $ v \equal{} 3$ or $ v \equal{} 4$.

3.1) If $ v \equal{} 3$ then $ d_7 \equal{} 7$, implying that $ 1,2,3,4,5,6,7$ are the smallest $ 7$ divisors of $ n$. But then below $ d_{10} \equal{} 24$ there also divisors $ 10,12,14,15,20,21$, a contradiction.

3.2) If $ v \equal{} 4$ then $ d_7\geq 9$ and $ 1,2,4,5,8,9,10,12,18,20,40$ are divisors of $ n$. But then $ 1,2,3,4,5,6,8$ are also divisors, implying that $ d_7\leq 8$, a contradiction.


Spot's doghouse has a regular hexagonal base that measures one yard on each side. He is tethered to a vertex with a two-yard rope. What is the area, in square yards, of the region outside the doghouse that Spot can reach? \[ \text {(A) } \frac{2}{3}\pi \qquad \text {(B) } 2\pi \qquad \text {(C) } \frac{5}{2}\pi \qquad \text {(D) } \frac{8}{3}\pi \qquad \text {(E) } 3\pi  \]

[hide]The regions that Spot can travel around are sectors of circles. Spot's tether can wrap around the hexagonal base, allowing him to travel around 4 sides of the hexagon. Overall, he can travel in a $240^\circ$ region of a circle of radius 2, and 2 $60^\circ$ sectors of radius 1 circles. This gives an area of $4\pi\cdot\frac{240}{360}+2\cdot\pi\cdot\frac{60}{360}=3\pi\implies\boxed E$

Sorry, I know it's not a very good explanation without a diagram. :( [/hide]

[hide="Answer"]We have a circle of radius two yards until the rope lies flat along one edge; this gives two-thirds of the circle. Then, we have the area given from the rope lying flat along one side until it lies flat along two. This is a $60^\circ$ angle of a circle with radius $1$, but on both sides, so we have one-third of this circle. Therefore, our answer is $4\pi \cdot \frac{2}{3}+\pi \cdot \frac{1}{3}=3\pi \Rightarrow \boxed{E}$.[/hide]


function
number theory unsolved
number theory

Find all function $f: N\to N-\{1\}$ for all $n\in\mathbb{N}$ satisfying

$f(n+1)+f(n+3)=f(n+5)\cdot f(n+7)-1357$

[quote="Arne"]This is definitely not Pre-Olympiad.

[url=http://www.mathlinks.ro/Forum/viewtopic.php?t=56591]an Iranian olympiad problem[/url]

Sure there is no typo?[/quote]

I dont know that it is from Iranian olimpiad problem . I got this problem from some olimpiad training book . And yes , they are the sam problem after  I checked . The hint in the book said we define $a_k=f(2k-1),b_k=f(2k)$ but I cant seem to see anything . Anyone wanna enlighten me ?  :)

I moved it to the number theory section.


If the probability that it will rain on Thursday is 5/6, what is the probability that it will not rain on Thursday?

Tell me, is it 1 - 5/6?????

Yes it would be $1-\frac{5}{6}=\frac{1}{6}$.

[quote="Interval"]I guessed correctly.

How about that?[/quote]

its because the total probability is 1.  like the probability that i either get an A or not get an A on my test is 1.  Also, 1 is 100%.  This is why the answer is 1/6

this should probably be moved to MOEMS or something like that :maybe:

Everything is in percentages, so to get the probability of rain you would have to subtract the whole (6/6) by the probability of no rain (5/6) thereby incurring a 16 2/3% of actually having rain and 83 1/3% rain.

[quote="ra5249"]Wait, by probability does it mean percent or fraction?[/quote]

Either.

[b]What grade level is this in? Isn't it a little to easy to be posted here?[/b]

It's obviously 1 - 5/6 because 1 being it will certainly rain. We subtract that by the probability that will rain to achieve the probability that will not rain.

1 - 5/6 = 1/6. There's 1/6 chance it will not rain.

[quote="redsmartie"][b]What grade level is this in? Isn't it a little to easy to be posted here?[/b][/quote]

See the quote below from a stickie. Please do not post reply unless you have a different solution than others :)

[quote="MCrawford"]MOEMS is an elementary math problem solving contest for students just learning about mathematical problem solving at the elementary school and middle school levels.  MOEMS problems are more basic than the problems in nearly every other forum on this site.

If you are unfamiliar with the MOEMS curriculum, please do not post in this forum at all.  There are plenty of places to post problems at AoPS.

Thank you for following these guidelines.  Users who do not will lose their ability to post here at all.[/quote]

you have to tell the units like percent or decimal or fraction cuz if you dont you can get points taken off but its probably a fraction resulting in 1/6

[quote="IntrepidFish"]its 1/6........ :lol:[/quote]
After an answer and explanation has been posted (especially more than one), another answer, unless it has a much better explanation, which it doesn't, is unnecessary.


Trodgor the dragon is burning down a village consisting of $ 90$ cottages.  At time $ t \equal{} 0$ an angry peasant arises from each cottage, and every $ 8$ minutes ($ 480$ seconds) thereafter another angry peasant spontaneously generates from each non-burned cottage.  It takes Trodgor $ 5$ seconds to either burn a peasant or to burn a cottage, but Trodgor cannot begin burning cottages until all the peasants around him have been burned. How many [b]seconds[/b] does it take Trodgor to burn down the entire village?

It was all I could do not to fix the spelling and add "thatch-roofed" when I posted this.

sry, i cant type in latex but here is my solution

http://i217.photobucket.com/albums/cc7/Rakia69/rejsenje.jpg


function
limit
induction
real analysis
real analysis unsolved

Suppose we have two functions $f,g: \mathbb{N}\rightarrow \mathbb{R}$ such that $f(1)=\frac{\sqrt{3}}{2}, g(1)=\sqrt{3}$ and for every $n\in \mathbb{N}$ we have:
$f(2n)=\left( \frac{f(n)g(2n)}{2}\right )^\frac{1}{2}, g(2n)=\frac{-1+\sqrt{1+g^{2}(n)}}{g(n)}$

Now we define the sequences $\{u_{n}\}_{n=1}^{\infty}$ and  $\{v_{n}\}_{n=1}^{\infty}$ in the following way:

$u_{n}=2^{n}f(2^{n}), v_{n}=2^{n}g(2^{n})$

Prove that:

I. $\{u_{n}\}_{n=1}^{\infty}$ and  $\{v_{n}\}_{n=1}^{\infty}$  are strictly monotone.

II.$\lim_{n\to \infty}u_{n}=\lim_{n\to \infty}v_{n}=\frac{\pi}{3}$

What do you think about this problem? Is it interesting or boring or...

Hello, mathematica!
I think this problem is very beautiful. g(1)=tan(Pi/3),f(1)=sin(Pi/3).
By induction it is easy to obtain, that g(2^n)=tan(Pi/(3*2^n))
and f(2^n)=sin(Pi/(3*2^n)).
So we have:  v(n)=2^n*tan(Pi/(3*2^n)) and u(n)=2^n*sin(Pi/(3*2^n)).
The rest part of solution is easy.
[sin(x)/x->1,tan(x)/x->1 as x->0  :  for the second part.]
[sin(2*x)=2*sin(x)*cos(x)   :   for the second part.  u(n) increase,
v(n) decrease.]


Given a, b positive integer.

There are n persons in a cycle. In order: 0, 1, ... n-1. First a pointer will move to 0. Then to $ax^{2}+b (mod n)$th person where x is the person where current person belongs. x will then be the index of current person and move to $ax^{2}+b (mod n)$th person and it will go on. when a pointer will come to a person twice he will suicide. and if the pointer comes to a person thrice then process will stop. Now Output how many persons survive?

I think it is congruece problem, but i can't solve. it is something like, find the number from where the loop begins and length of loop. but how?

As usual, it all depends on how big n is..

N <= 10^9, and it is guaranteed that the first suicide happens in no more than 10^6 steps.

This problem is from yesterday's uVa competition. The problem statement can be found here: http://acm.uva.es/p/v110/11053.html

A simple solution with a hashtable takes a [size=75]little[/size] less than 3sec (the original timelimit).

[url]http://www.informatik.uni-ulm.de/acm/Locals/2006/html/judge.html[/url]

Any one explain me the first method stated here (Problem F)?

Obviously if the 2 pointers end up with the same value, x, then you have a cycle (as the one pointer is ahead of the other) so you just have to keep increasing only the speed-1 pointer (slow pointer) until it finds x again. Thus you know how many people have committed suicide.

Now you need to be certain that these two pointers will eventually take the same value, at some point. This is easily proven.

Suppose the cycle has length L. Consider the moment when the speed-1 pointer first enters the cycle. Then the speed-2 pointer surely is inside the cycle (although it may have gone through it more than once, which makes no difference). If d is the distance of indices in the cycle between the 2 pointers taken mod L, you should notice that d constantly increases by +1 (mod L). So eventually d will become 0 mod L.

Here's an example in case I made it seem complicated:

[code]
Suppose you have a cycle of 5 elements:

Step | speed-1 pointer index | speed-2 pointer index
----------------------------------------------------
1    |           0           |         1 (random choice, d = 1)
2    |           1           |         3 (d = 2)
3    |           2           |     5 i.e. 0 mod 5 (d = -2 i.e. 3 mod 5)
4    |           3           |         2 (d = -1 i.e. 4 mod 5)
5    |           4           |         4 (d = 0) solved
[/code]


How many other users on AoPS do you actually know?

I only know one other person.

I know quite a few... some are inactive, though.

21+... don't know if its 50+...

Well, my sister has an AoPS account, and so does another kid at our school. I might know as many as ten but I only know two for sure.

Seven. I know them all from state mathcounts.

JoshD
whitesoxfan
jgjgjmath
Stargirl240
avec_une_h
ManHatTaNatiVe74
RussianRocket

Oops, I put 3 on the poll but I really know four...

Also, what sort of an option is 50+?

6;

mz94
BOGTRO
infinitypi
MyRascal
soltixnj
max221

$ \frac{Around}{8\ to\ 9}...\frac{I}{think}$

Sorry, my earlier post was wrong.

Actually 8...

I was missing laughinghead505 (lol i can't believe i forgot her because i met her in chapter mathcounts 2007)

Lemme count...

james4l, NotA, ak909090, donghyun, leafiness0, lifeisacircle, enter.the.blahger, superquark123, infinite_sigma, jeffyuan (for those who know me, you might say there is a mistake), AIME15. Might see Dojo soon.

Thats 11 (+1)

lol id say more than 20 considering the fact that i know like 5 from my school
and like gazilion from awesomemath :P

too lazy to count. ill count later.
goofing off in debate class is just awesome.


[quote="aidan"]Catherine drives to the station each day to pick up her husband Andrew, who usually arrives on a train at 5 o'clock. Last Monday, Andrew finished work earlier, caught an earlier train and arrived at the station at 4 o'clock. He started to walk home and eventually met Catherine who drove him the rest of the way, getting there twenty minutes earlier than usual. On Tuesday, he again finished early and found himself at the station at 4.30. Again, he began to walk home, again he met Catherine, and she drove him the rest of the way. How much earlier than the usual time were they this time?

Source: Mathematics Challenge for Young Australians, Problem 70[/quote]

[hide]Is it $\frac{20}{2}=\boxed{10}$ minutes[/hide]

Unfortunately no.. we can't just half the time, there are snags.  :)

Any solutions?  I have tried this, but I'm not good at rate, time, & distance...

Ok I offer a full solution:

[hide]We will assume that Catherine leaves home so as to arrive at the station at 5:00. Catherine's drive is shortened by 20 minutes, so she takes 10 minutes less to meet Andrew (this is at 4:50). So on Monday Andrew walks as far in 50 minutes as Catherine drives in 10 minutes. On Tuesday Andrew walks for 30 minutes less than on Monday, so Catherine must drive $\frac{30 \times 10}{50}= 6$ minutes longer. So she drives for $(10-6) = 4$ minutes less than usual, and her round trip is shortened by 8 minutes. Thus they arrive home 8 minutes earlier than the usual time. [/hide]

There might be a more interesting way to it.  :)


Putnam
function
real analysis
real analysis unsolved

Show that the functional equation: $ f(f(x)) = 6x-f(x)$ has a unique solution, where $ f : R^{+}\rightarrow R^{+}$.

Here's the statement of Putnam 2001 B5:

Let $ a$ and $ b$ be real numbers in the interval $ (0,1/2)$, and let $ g$ be a continuous real-valued function such that $ g(g(x))= ag(x)+bx$ for all real $ x$. Prove that $ g(x)=cx$ for some constant $ c$.

This is a little different, and to solve it we can't use all of the tools N.T.TUAN just used - we'll need some different arguments.

We had that before (in the Olympiad Algebra section) : http://www.mathlinks.ro/Forum/viewtopic.php?t=128763

I think its [b]putnam 1988[/b]...
anyway assume that $ f$ is such function,now like what [b]N.T.TUAN[/b] said let $ (a_{n})_{n=0}^{\infty}$ be a sequence where $ a_{0}=x$ and for $ n\geq 0$ we put: $ a_{n+1}=f(a_{n})$ so we get that:
$ a_{n+2}+a_{n+1}-6a_{n}=0$
for $ n\geq 0$ now we know that the roots of the equation $ x^{2}+x-6=0$ are $ -3,2$ so we get that for some constant numbers $ c,k$ we have:
$ a_{n}=(-3)^{n}c+2^{n}k$ for $ n\geq 0$ now note that $ f: \mathbb{R^{+}}\rightarrow\mathbb{R^{+}}$ we get that $ a_{n+1}=f(a_{n})>0$ hence we have $ c=0$ so $ f(x)=2x$.and at the end its easy to see that $ f(x)=2x$ satisfies the problem`s conditions...


In a rectangular coordinate system, the line $ 5y \equal{} 2x$ intersects the line $ 3x \minus{} 4y \equal{} 7$ at point $ Z$. What is the sum of the coordinates of point $ Z$?


For any integer $ n > 1$, prove that there exists $ a,b,c$ between $ n^2$ and $ (n \plus{} 1)^2$ (not inclusive) such that $ c$ divides $ a^2 \plus{} b^2$.

[hide]$ (n^2\plus{}1) \mid \left(\left(n^2\plus{}2\right)^2 \plus{} \left(n^2\plus{}n\plus{}1\right)^2\right)$[/hide]


function
topology
geometry
3D geometry
sphere
advanced fields
advanced fields unsolved

Is there any way to visualize the Banach algebra C(X) of continuous functions on compact Hausdorff spaces X?

Is there any way to think of classifying such an algebra?

What, for example, is a good way to visualize C(S^2), where S^2 is the unit sphere in R^3?

What do you mean by "visualize" :? I always think of continuous functions as of some wiggles over the space, but I can hardly call this "visualization". As to classification, $ C(X)$ is isomorphic to $ C(Y)$ (in the sense of isomorphism of Banach algebras) if and only if $ X$ is homeomorphic to $ Y$, so all of them are different.


A sequence a(n) of integers is defined by a{1} = 1, a{2} = 2 and
a{n}=3a{n-1}+5a{n-2}   for n=3; 4; 5...
does there exist an integer  t >1 for which  a{t} divides a{t+1}a{t+2}

OK, I'm not sure about this solution, but here it goes:

Let $ a_{t \plus{} 2}\cdot a_{t \plus{} 1} \equal{} m\cdot a_t$, $ m$ being a natural number. Now, we have $ (3\cdot a_{t \plus{} 1} \plus{} 5\cdot {a_t})\cdot a_{t \plus{} 1} \equal{} m\cdot a_t$, meaning $ 3\cdot {a_{t \plus{} 1}}^2$ must be divisible by $ a_t$. It's easy to prove by induction that none of the members of the sequence is divisible by either $ 3$ or $ 5$, which means $ {a_{t \plus{} 1}}^2$ must be divisible by $ a_t$. I claim there is no solution. I will therefore prove that for any $ t\geq 1$ numbers $ a_t$ and $ a_{t \plus{} 1}$ are relatively prime.
For $ t \equal{} 1$ the statement is obviously valid. Let's now assume the opposite: there is some $ m$ such that $ GCD(a_m,a_{m \minus{} 1}) > 1$ and $ GCD(a_{m \minus{} 1},a_{m \minus{} 2}) \equal{} 1$. If $ GCD(a_m,a_{m \minus{} 1}) \equal{} d$ we have $ k\cdot d \equal{} 3l\cdot d \plus{} 5\cdot a_{m \minus{} 2}$. Then $ 5\cdot a_{m \minus{} 2}$ is divisible by $ d$. Because $ a_m$ isn't divisible by $ 5$ (meaning $ GCD(5,d) \equal{} 1$) and $ d > 1$, $ GCD(a_{m \minus{} 2},d) > 1$. But then $ GCD(a_{m \minus{} 1},a_{m \minus{} 2}) > 1$, which leads us to a contradiction.

This finishes the solution and the answer to the question in the problem is no. Please, let me know if this solution contains any mistakes, which is far from impossible.


$ \angle BEG \equal{} 90\minus{}\frac{\beta}{2}\equal{}\frac{\alpha}{2}\plus{}\frac{\gamma}{2}\equal{}\angle GOA$ so EGOA is a cyclyc quad and $ \angle AGO \equal{} 90$
$ \angle GOF\plus{}\angle GAF \equal{} 90\minus{}\frac{\gamma}{2}\plus{}90\plus{}\frac{\gamma}{2}\equal{} 180$ so AGOF is a cyclyc quad
Then AFOGE is a cyclyc pentagon and equally for CFOHD so

$ \angle GEH \equal{} 180\minus{}\left ( 90\minus{}\frac{\beta}{2}\right )\minus{}\left (90\minus{}\frac{\beta}{2}\right ) \equal{}\beta$


Probably posted before, but I didn't find it on search.

Find all integer solutions to the equation

$ \frac{1}{x}\plus{}\frac{1}{y}\equal{}\frac{1}{z}$     :D

[quote="Sashsiam_2"]Probably posted before, but I didn't find it on search.

Find all integer solutions to the equation

$ \frac {1}{x} \plus{} \frac {1}{y} \equal{} \frac {1}{z}$

That smiley was distracting to me, as it is no near the equation.

[quote]There are infinite solutions: x=2z, y=2z[/quote]

Fine, but there are still solutions missing. In fact $ (1,\minus{}2,2)$ and $ (3,6,2)$ are solutions too.

A nice reformulation: find integers $ a$, $ b$ such that $ a\plus{}b$ divides $ ab$.

We have $ 1\plus{}1\geq\frac1a \plus{} \frac1b \equal{} k\implies k \equal{} 1$.

Assume without loss of generality that $ a\leq b$, so that $ \frac1a\geq\frac {\frac1a \plus{} \frac1b}2 \equal{} \frac12\implies a\leq2$, so, because $ a > 1$ as well, $ (a,b) \equal{} (2,2)$ is the only solution.

Well, I can find the solutions when given either of $ x$, $ y$ and $ z$:

$ \frac {1}{x} \plus{} \frac {1}{y} \equal{} \frac {1}{z}$
$ zx \plus{} zy \equal{} xy$ (if x = 1, then zy + z - y = 0
$ zx \plus{} zy \minus{} xy \equal{} 0$
$ xy \minus{} zx \minus{} zy \equal{} 0$
$ xy \minus{} zx \minus{} zy \plus{} z^2 \equal{} z^2$
$ x(y \minus{} z) \minus{} z(y \minus{} z) \equal{} z^2$
$ (x \minus{} z)(y \minus{} z) \equal{} z^2$

Hint: analyze the gcd of x, y and z (note: this hint isn't mine).

My solution uses [b]ffao[/b] reasoning and the hint (from a brazilian training material).

Without loss of generality assume $ gcd(x,y,z)\equal{}1$. Investigation leads to a clear pattern:

$ \frac{1}{2}\plus{}\frac{1}{2}\equal{}\frac{1}{1}$

$ \frac{1}{6}\plus{}\frac{1}{3}\equal{}\frac{1}{2}$

$ \frac{1}{12}\plus{}\frac{1}{4}\equal{}\frac{1}{3}$

$ \frac{1}{20}\plus{}\frac{1}{5}\equal{}\frac{1}{4}$

We can work only with positive integers. In fact, if all terms are negative, we just multiply by $ \minus{}1$. If two terms are negative, we just rearrange. And if just one term is negative, we multiply by $ \minus{}1$ and then rearrange.

Using  [b]ffao[/b] manipulations, we find $ (x\minus{}z)(y\minus{}z)\equal{}z^2$. If $ z\equal{}1$ the only solution is $ (2,2,1)$. If $ z>1$ with our assumption that $ gcd(x,y,z)\equal{}1$ we have either $ x\minus{}z\equal{}1$ or $ y\minus{}z\equal{}1$ so the solutions are $ (z\plus{}1,z(z\plus{}1),z)$ and $ (z(z\plus{}1),z\plus{}1,z)$. The others are obtained multiplying by some non-negative integer.


linear algebra
matrix
linear algebra unsolved

Is it true that every singular matrix can be expressed as product of idempotent matrices?

It depends.
The answer to "Is it true that every singular matrix over a filed can be expressed as product of idempotent matrices?" is yes. And I think it has been discussed on this forum in the past.
But if the matrix considered is over a certain ring the asertion becomes false.

It is a result of Erdos (1967). There exists an elementary proof in Am. Math. Mon. 112,n°7 p. 641-645 (2005). The result is true in a field and also in an Euclidean domain. In particular the result is true in $ \mathbb{Z}$ and then a singular matrix is the product of $ 3n\plus{}1$ projectors.
     I have not in mind a proof.

It is worth mentioning that Erdos here is not the famous Paul Erdos.
To find a ring where the asertion becomes false is not obvious I think.

Over a field, a stronger result is known: a linear map $ L$ is a product of $ k$ idempotents iff $ k\cdot\dim\ker L\geqslant \mathrm{rk}\left(I\minus{}L\right)$. It is proved in C. S. Ballantine, Products of idempotent matrices, Linear Algebra Appl. 19 (1978), 81-86. A generalisation of this result to a wider class of algebraic structures is described in Gracinda M. S. Gomes and John M. Howie, Proceedings of the Edinburgh Mathematical Society (1995) 38, 107-116.


geometry
geometric transformation
reflection

(1) Find the arithmetic mean, expressed as common fraction, of all the
solutions of $ \left|7x\right| \minus{} \sqrt {7x} \equal{} 0$.

[hide="ANSWER"]$ \boxed{\frac {1}{14}}$[/hide]

(2) The units digit of a six-digit number is $ 1$ and is removed, leaving a
five-digit number. The removed units digit $ 1$ is then placed at the far
left of the five-digit number, making a new six-digit number. If the
new number is $ \frac {1}{3}$ of the original number, what is the original
number?

[hide="ANSWER"]$ \boxed{42857}$

I got $ 428571$, but couldn't find why my answer is wrong.[/hide]

(3) The point $ A (7, \minus{} 4)$ is reflected about the $ x$-axis to give the point $ B$ ,
then $ A$ is reflected about the line $ y \equal{} x$ to give the point $ C$ , and finally
$ A$ is reflected about the $ y$-axis to give the point $ D$ . What is the area of
the quadrilateral $ ABCD$?

[hide="ANSWER"]$ \boxed{121}$[/hide]

[hide="1."]
$ \left|7x\right| \minus{} \sqrt {7x} \equal{} 0$
$ \left|7x\right|\equal{}\sqrt {7x}$
So,
$ \minus{}7x\equal{}\sqrt {7x}$
or
$ 7x\equal{}\sqrt{7x}$
These both square to the same thing,
$ 49x^2\equal{}7x$
If you look at it, you can see that $ 0$ is a solution.
Dividing both sides by $ x$,
$ 49x\equal{}7$
Simplifying,
$ x\equal{}\frac{1}{7}$
Since the two solutions are $ 0$ and $ \frac{1}{7}$,
the answer is $ \frac {1}{14}$
[/hide]

[quote="vamathletes"][hide]$ \left|7x\right| \equal{} \sqrt {7x}$
So,
$ \minus{} 7x \equal{} \sqrt {7x}$
or
$ 7x \equal{} \sqrt {7x}$
These both square to the same thing,
$ 49x^2 \equal{} 7x$[/hide][/quote]This split part can be skipped if you knew $ |x|\equal{}\sqrt{x^2}$ ;)

[hide="2"]
Write an equation:

$ \frac {100000 \plus{} x}{10x \plus{} 1} \equal{} 1/3$, where X is the five-digit number.

Cross-multiply:

$ 300000x \plus{} 3x \equal{} 10x \plus{} 1$
$ 299999 \equal{} 7x$
$ x \equal{} 42857$

Since that's the 5-digit number and the units digit is 1, the original number is $ \boxed{428571}$

[/hide]

you're right.  the solution must have an error because i got the same thing you got, whoever wrote the solution must have made a careless mistake  :)

[hide="for 3, i have a different answer..."]
The points are (7,-4), (7,4), (4,7), and (-4,7).  You can use shoelace from here.

7 -4
7 4
4 7
-4 7

(28+49+28-16)-(49+16+28-28)=24, 24/2=[b]12[/b].

Umm... I think you mistyped... 121 seems way too big.
[/hide]

Uh oh...I might have written something wrong. Okay, 56 seems right now.

[quote="vamathletes"][hide]For #3, I get 56.  Can someone point out the flaw?
7 -4
7  4
4  7
-4 7
7 -4
Using shoelace,
(28+49+28+16)-(-28+16-28+49)=112
Half of 112 is 56
[/hide][/quote]

Your points are wrong.

The answre is 121.

First of all, you have the point (4,7).  That is not a point.  Remember you are [b]only[/b] reflecting the point A, not point B and then point C..

The opints should be [b](7,-4)-A[/b]
[b] (7,4)-[/b]reflection of A across x-asix
[b](-4,7)-[/b]reflection of A across x=y and
[b](-7,-4)-[/b]refelction of A across y-axis


probability
invariant
topology
real analysis
real analysis unsolved

Let $X$ be a countable compact Haussdorf space. Prove that every continuous map $f: X\to X$ has a periodic point.

We can use basically the same approach as [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?highlight=returning&t=75825]here[/url]. More precisely:

We can find a regular probability measure $\mu$ on $X$ with respect to which $f$ is measure-preserving. Then, we apply the same Recurrence Theorem that was cited there. This time, however, we apply it to a set with positive measure consisting of only one point. There must be such a set since if $(x_{n})_{n\ge 1}$ is an enumeration of $X$, then $1=\sum_{n\ge 1}\mu(\{x_{n}\})$, so at least one $\mu(\{x_{n}\})$ is positive.

I was thinking about similar problems and I remembered this one. Here's a less artificial proof:

An application of Zorn's Lemma shows that we can find a non-empty closed subset of $X$ which is invariant under $f$ and which is minimal with respect to these properties. In order to keep the notation simple, assume $X$ itself is minimal. This is equivalent to saying that for every $x\in X$, the positive orbit $\mathcal O(x)=\{x,f(x),f^{2}(x),\ldots\}$ of $x$ is dense in $X$. Now, $X$ is a countable compact metric space, so it cannot be perfect (the fact that a perfect compact metric space has continuum cardinality has been discussed and proven on the forum). In other words, $X$ has at least one isolated point. The fact that $X$ is minimal implies that every isolated point $x$ is periodic (just consider the orbit $\mathcal O(f(x))$, which must be dense), so we're done.


algebra
polynomial
linear algebra
linear algebra unsolved

If $P = a_nX^n + a_{n-1}X^{n-1} + \cdots + a_1X + a_0 \in R[X]$, has real distinct roots $x_1, ..., x_n$ and $a_n = a_0$, then
$\sum_{i=1}^n \frac{x_i^n + 1}{x_i \cdot P'(x_i)} = 0$
[cool isn't it ?  ;) ]

i) Lemma: let $P(x)=a_{n}x^{n}+\cdots+a_{0}\in\mathbb{C}[x]$ be a polynomial which has complex distinct and NON ZERO roots $a_{1},\cdots,a_{n}$. Then $\sum_{k=1}^{n}\frac{1}{a_{k}P'(a_{k})}=-\frac{1}{a_{0}}$.
Proof: $\frac{1}{xP(x)}=\frac{b_{0}}{x}+\frac{b_{1}}{x-a_{1}}+\cdots+\frac{b_{n}}{x-a_{n}}$; calculate the $b_{i}$,.........
ii) Apply the lemma to the polynomial $y^{n}P(\frac{1}{y})$ which admits as roots the $\frac{1}{x_{i}}$. One obtains $\sum_{k=1}^{n}\frac{-a_{k}^{n}}{a_{k}P'(a_{k})}=-\frac{1}{a_{n}}$.
QED


induction
number theory unsolved
number theory

A positive integer $N$ is said to be $n-$ good if
(i) $N$ has at least $n$ distinct prime divisors, and
(ii) there exist distinct positive divisors $1, x_{2}, . . . , x_{n}$ whose sum is $N$ .
Show that there exists an $n-$ good number for each $n\geq 6$.

this problem was in the first Brazilian Training List!

My solution:

See that if n is k-good, n(n+1) will be (k+1)-good,
because if $n = 1+x_{2}+...+x_{k}$, we will have $n(n+1) = 1+n+x_{2}(n+1)+...+x_{k}(n+1)$
and n(n+1) will have one prime that not divide n.

So, we have to find one 6-good number! (and the problem follows from one induction)
We will begin with one little 'bad' number and will find one 6-good number:

6 = 3+2+1
42 = 21 + 14 + 6 + 1
1806 = 21.43+14.43+6.43+42+1
$3263442 = 21.43.1807+14.43.1807+6.43.1807+42.1807+1806+1$

see that 3263442 is a 6-good number, because is the sum of 5 divisors + 1 and $3263442 = 2.3.7.13.43.139$

Very Nice!  :)

[quote="e.lopes"]

See that if n is k-good, n(n+1) will be (k+1)-good,
because if $n = 1+x_{2}+...+x_{k}$, we will have $n(n+1) = 1+n+x_{2}(n+1)+...+x_{k}(n+1)$
and n(n+1) will have one prime that not divide n.
[/quote]
You are right! Here is nice, thanks  :wink:


I have sold 2/3 of my pencils for $0.15 each. If I have 8 pencils left, how much money did I collect for the pencils I sold?


calculus
integration
LaTeX
calculus computations

Okay.. I'm new here so hello to all and thanks in advance for helping me with this problem..

I'm studying calculus now and my sensei gave us this problem and im really flustered right now cause i cant get it done... anyhoo  the problem is related to the Center of Mass of a Rod

here it is:

The length of a rod 8in. and the linear density of the rod at a point x inches from the left end is 2(x+1)^1/2 slugs per inch<--( this means (x+1) raised to the power of 1/2.. in short the square-root of (x+1).. sorry for the inconvenience :D) Find the total mass of the rod and center of mass..

Thanks for the replies :D i'll be waiting.. i've got dozens of problems that still needs to be solved >.<

hi canephalanx
welcome
let $ \lambda (x)$ be the linear mass density of the rod .
so we have $ \frac{dm}{dx}= \lambda$
so $ M=\int dm = \int_{0}^{8}\sqrt{x+1}dx$
thus $ M=\frac{52}{3}$ slugs
also by definition the position $ X_{cm}$ of  the centre of mass from origin is

$ X_{cm}=\frac{\int_{M}x dm }{M}$

so $ X_{cm}=\frac{\int_{0}^{8}x \sqrt{x+1}dx}{M}$
the integral can be done by writing $ x=(x+1)-1$

that makes sense now... but i think u missed the 2 in the main equation..
it was supposed to be 2(x+1)^1/2... :P

so the final answer now shud be 104/3...

is this correct?

thanks for ur help :D

yes sorry
well try learning some $ \ latex$ it's easy


trigonometry
inequalities
function
analytic geometry
ratio
conics
ellipse

There are some problems from my school:

Prove the inequalities:
1) $x^2+y^2=1$, $a^2+b^2=1$, prove that $-1 \leq (ax+by) \leq 1$
2) $a^2+b^2 \leq 1$, prove that $|a^2+ 2 \sqrt 2 ab - b^2| \leq 2$
3) $a^2+b^2+ab=1$, prove $ \frac23 \leq a^2+b^2 \leq 2$
............

And in all these problems, we let $a=\sin{\alpha}$ and $b=\cos{\alpha}$, or $a=m\sin{\alpha}, b=m\cos{\alpha}$
I wonder, why can we use trig function to express a and b and x and y??
Can you explain it?

In all cases (I didn't completely verify, I'm just kinda assuming), we have $-1 \le a \le 1$ (or for some other variable).  Then you can let $a = sin \theta$.  Using $1 - \sin^2 \theta = \cos \theta$, you can let another variable be $\cos \theta$.  For the case of #2 you can use WLOG $a^2+b^2 = 1$, since you can always scale them up to increase the LHS of the other inequality.

[quote="shobber"]can you prove that if $a^2+b^2=1$ then we can put $a=\sin{\alpha}$, $b=\cos{\alpha}$ WLOG?   :?[/quote]

It's trivial, $\forall x\in [-1,1],\exists t\in [0,2\pi)$ such that $\sin t=x$

[quote="kunny"]Just the definition of polar coordinates.[/quote]
i don't know about the polar coordinates, but how can we transform two unknown into one variable?

How about examining the definition of $\cos \theta, \sin \theta$? :)

I will post the problem in relation to that.

(1) Describe the definition of $\sin \theta,\cos \theta$ for a general angle.

(2) Prove the following equations on basis the definition you described in (1)  for a general angle.

\[\sin (\alpha+\beta)=\sin \alpha\cos \beta+\cos \alpha\sin \beta\]

\[\cos (\alpha+\beta)=\cos \alpha\cos \beta-\sin \alpha\sin \beta\]

                                                                                [b]1999 Tokyo University[/b]

the definition we learn at school is the ratio of the coordinate and the radius.

Yes. That is to say, on xy-plane let the point $P(x,y),\ \angle POx=\theta$ and the distance $OP=r$,

we have $\frac{x}{r}=\cos \theta,\ \frac{y}{r}=\sin \theta\Longleftrightarrow x=r\cos \theta,\ y=r\sin \theta$.

that makes $\sin^2{x}+\cos^2{x}=r^2$.
from the distance formula, we have $\cos{(x+y)}=\cos{x}\cos{y}-\sin{x}\sin{y}$. By the induced formula, we get the other identities.
these are easy, but still, i don't understand the substitution...

[quote="shobber"]i am still confused.
also, for problem 3, why we can put $m \sin{\alpha}$ and $m\cos{\alpha}$ in?? We don't have $a^2+b^2=1$... :?[/quote]

This problem asks us to find  the range of the square of the distance on ab-plane origin and the point $P(a,b)$ on the ellipse $a^2+ab+b^2=1$.
That is to say, we are to the condition such that circle $a^2+b^2=r^2$ have the intersection point  with ellipse $a^2+ab+b^2=1$.
Now we can set the intersection point as $(a,b)=r(\cos \theta,\sin \theta)$.

By the way from $a^2+ab+b^2=1\Longleftrightarrow \left(a+\frac{b}{2}\right)^2+\left(\frac{\sqrt{3}}{2}\right)^2=1$,

we can set  $a+\frac{b}{2}=\cos \theta,\ \frac{\sqrt{3}}{2}=\sin \theta\Longleftrightarrow a=\cos \theta-\frac{1}
{\sqrt{3}}\sin \theta,\ b=\frac{2}{\sqrt{3}}\sin \theta$.

my teacher's solution was to put: $a=m \sin{x}$ and $b=m \cos{x}$.
Then $a^2+b^2+ab=m^2+m^2(\sin{x} \cos{x})=m^2(1+\frac12 \sin{2x})=1$
hence:
\[m^2=\frac{2}{2+\sin{2x}}\]
so:
\[\frac23 \leq m^2 \leq 2\]

This one also get the answer, but unlike Kunny's, it does the trig substitution in the first step, that made me confused...

Thanks kunny!

I know your teacher's solution.

Another solution:

Since $a^2+b^2\geqq 2|ab|\Longleftrightarrow 1-ab\geqq 2|ab|\Longleftrightarrow -(1-ab)\leqq 2ab\leqq 1-ab$

$\Longleftrightarrow -1\leqq ab\leqq \frac{1}{3}$, from $a^2+b^2=1-ab$,

we have $\frac{2}{3}\leqq a^2+b^2\leqq 2$.


prove that there exist two infinite sequences <a_n>n>=1and <b_n>n>=1 of positive integers such that the following conditions hold simultaneously :
(1) 1<a_1<a_2<a_3< .... ;
(2) a_n<b_n<(a_n)^2   for all n>=1 ;
(3) (a_n)-1 divides (b_n)-1 for all n>=1 ;
(4) ((a_n)^2)-1 divides ((b_n)^2)-1 for all n>=1 .

[quote="tamal banerjee"]prove that there exist two infinite sequences $ \langle a_n\rangle _{n\geq 1}$and $ \langle b_n\rangle_{n\geq 1}$ of positive integers such that the following conditions hold simultaneously :
(1)$ 1 < a_1 < a_2 < a_3 < \cdots$ ;
(2) $ a_n < b_n < (a_n)^2$   for all $ n\geq1$ ;
(3) $ a_n \minus{} 1$ divides $ b_n \minus{} 1$ for all $ n\geq1$ ;
(4) $ a_n^2 \minus{} 1$ divides $ b_n^2 \minus{} 1$ for all $ n\geq 1$ .[/quote]
This is Indian Regional Mathematical olympiad 2008 ;)
I solved this sequence by constructing:
$ a_n \equal{} 2n \plus{} 1; b_n \equal{} 2n^2 \plus{} 4n \plus{} 1$
As we see; $ a_n < b_n \equal{} 2n^2 \plus{} 4n \plus{} 1 < a_n^2 \equal{} 4n^2 \plus{} 4n \plus{} 1$
$ 2n|(2n^2 \plus{} 4n)$
$ 4n^2 \plus{} 4n|(2n^2 \minus{} 4n \plus{} 1)^2 \minus{} 1 \equal{} b_n^2 \minus{} 1$

We are done :)


abstract algebra
group theory
superior algebra
superior algebra unsolved

Hi.

How can I prove the following:

Let $ (G, \Omega )$ be a transitive group such that $ G$ is also abelian.

Prove $ |G| \equal{} | \Omega |$ , ( $ (G ,\Omega )$ is regular permutation group).

Thanks.

Well that's not true. You need the condition that $ G$ operates faithful.

The proof is easy: Consider the stabilizers $ G_\omega$. Since $ G$ is transitiv we get, that all stabilizers are conjugated, i.e. equal. Now the kernel of the operation is $ K: \equal{}\bigcap_{\omega} G_\omega\equal{}G_\omega$. Since $ G$ operates faithful the kernel is 1, so all stabilizers are 1 and hence $ G$ operates regulary.

That the kernel is 1 is neccessary. Simple counterexample: Let $ G\neq 1$ be an arbitrary abelian group and $ U\leq G$. Then $ G$ is transitive on $ \Omega\equal{}G/U$ but in general not regular.

edit:

$ (G ,\Omega )$ is regular is a mistake.

correct: $ (G ,\Omega )$ is regular permutation group .

Sorry for the typo, fixed in main post,

Is there a chance there's another proof for it that doesnt use stabilizers, faithfulness and kernel?

Since I didn't ran into these before. (Only kernel but not in that context).

Thanks!

I think almost every proof of this statement is essentially the same proof as I gave. The difference is only how you wirte it down.

The following is exactly the same proof:
Assume there are $ g\in G, \omega\in\Omega$ with $ ^g\omega \equal{} \omega$. Then $ ^h \omega \equal{} ^h(^g \omega) \equal{} ^{hg}\omega \equal{} ^{gh}\omega\equal{}^g(^h\omega)$. Since $ G$ is transitive, every element of $ \Omega$ is of the form $ ^h \omega$, i.e. if $ g$ stabilizes one element, it stabilizes every element.
Now you have to use the (still) missing assumption, that $ G$ operates faithful to conclude from that $ g \equal{} 1$. (as I mentioned this has to be assumed, the proposition is false without it. The only question is which formulation is used if you don't know the term faithful...)

In other word: The only element which stabilizes some $ \omega$ is the identity. This and the transitivity yields immediatly the regularity. (Look up your definition of "regular" and prove it yourself if this is not clear directly)


I have enrolled in the independent study and I dont see the message board, it has been 4 days.
Is there not one or is it not in the online school section?

Yes i can :). I guess it was a matter of the administrators adding me to the group.


I am particularly interested in number theory.  Can you direct me to some good elementary number theory books, post some number theory questions, or post things that you think are important to know about number theory for the AMC/AIME?

http://artofproblemsolving.com/Forum/viewtopic.php?t=6143

Try searching this forum for other information.  I'm sure that many people have asked similar questions before.

Find a divisibility rule for :

a)7

b)13

c)23

Show that, given integers $a$ and $b$, there exist integer solutions $(x, y)$ to

$ax+by = 1$

If and only if $gcd(a, b) = 1$.


$e$=$lim (1+\frac{1}{n})^{n}$=$lim\underbrace{(1+\frac{1}{n})(1+\frac{1}{n})\cdots(1+\frac{1}{n})}_{n times}$
=$\underbrace{lim(1+\frac{1}{n})lim(1+\frac{1}{n})\cdots\lim(1+\frac{1}{n})}_{n times}$

=$\underbrace{1.1\cdots1}_{n times}=1$

what is wrong?

[color=green]Mathematics is the cheapest science. Unlike physics or chemistry, it does not require any expensive equipment. All one needs for mathematics is a pencil and paper.[/color]

Please don't double-post.

$1^{\infty}$ is undefined.

[quote="mahyar_math"]$\lim\underbrace{(1+\frac{1}{n})(1+\frac{1}{n})\cdots(1+\frac{1}{n})}_{n times}=\underbrace{\lim(1+\frac{1}{n})\lim(1+\frac{1}{n})\cdots\lim(1+\frac{1}{n})}_{n times}$
[/quote]
This step is incorrect.

[quote="ZetaX"]No, the next one is incorrect.[/quote]
Oh, sorry, you are right  :blush: . I made a mistake during deleting the rest of [b]mahyar_math[/b]'s post from the quote. I'll edit it.

In particular, $n$ exists only inside the limit, but in that step you moved $n$ outside the limit, which is invalid.

[quote="breez"]Isn't 1 to any power equal to 1?[/quote]

To any [b]finite[/b] power.

Now, it is true that if $f_{1}(x), f_{2}(x), ... f_{n}(x)$ are any [b]finite[/b] sequence of functions with $\lim_{x \to \infty}f_{k}(x) = 1$, then

$\lim_{x \to \infty}\prod_{k=1}^{n}f_{k}(x) = 1$

However, this process cannot be extended infinitely since two limits need to be taken; one for the number of functions, and another for their input.

The mistake in the above proof essentially amounts to splitting the limit and evaluating it separately twice in a way that leads to contradictory results.

[quote="breez"]So you can't evaluate a limit by evaluating 2 limits in the function or series of functions?

Because you said taking limit for the functions and limit for the input. So you can't determine the limit of a strand of functions by evaluating the limit of the inputs and then evaluating the limit of the functions with the specific inputs?[/quote]

Well, what's really happening (as far as I can tell) is that the original proof evaluates

$\lim_{n \to \infty}\left( 1+\frac{1}{n}\right)^{n}$

By evaluating the limit

$\lim_{x, y \to \infty}\left( 1+\frac{1}{x}\right)^{y}$

Which is [b]not defined[/b].  This means that you can evaluate it in different ways to get different results, which is what we are seeing here.

Okay, I see that the problem is with taking a number approaching 1 to infinite. Since if it's not quite at 1 and you multiply it infinite times, the value could be between 1 and infinite.

[quote="JBL"][quote="breez"]Why is $1^{n}$ undefined?[/quote]

He wrote $1^\infty$, not $1^{n}$, and what he meant was if you have $\lim_{x\to a}f(x) = 1$ and $\lim_{x\to a}g(x) = \infty$ then you cannot immediately determine the limit $\lim_{x \to a}f(x)^{g(x)}$ -- it could converge to any nonnegative real, diverge to infinity, or diverge by not approaching anything.  It's an indeterminate form.[/quote]

So $1^{\infty}$ is only undefined when we are talking about a function approaching 1 to the infinite power?

Because I think 1 x 1 x 1 x 1 x 1... is equal to 1.

[b]breez[/b], what you are saying is that \[1\times 1\times\cdots = 1,\] when in fact \[1\times 1\times\cdots\times 1=1.\] (the first would imply an infinite product of $1$'s.)

The infinite product of ones is one!

The problem is that there is no $1$; there is some limit going to $1$. And as was already said before, you can't just do the inner limits indepent from the outer ones.

This is JUST a helping clue, NOT a valid proof, repeat NOT a valid proof:

If you write $1=a^{0}$, where $a$ is any finite real number, you get $1^\infty=(a^{0})^\infty=a^{0\cdot\infty}=a^{0\cdot{1\over 0}}=a^{0/0}$, and the exponent is not defined.

Or to be somewhat stricter in what I've wrote: Notation "$\to l$" means "something that tends to $l$ when the independent variable tends to whatever it tends to".

Then $(\to 1)^{\to\infty}=(a^{\to 0})^{\to\infty}=a^{(\to 0)(\to\infty)}=a^{(\to 0)\cdot\frac{1}{\to 0}}=a^\frac{\to 0}{\to 0}$, and the exponent is not defined. For example, take $\frac{C/n^{2}}{1/n},\frac{C/n^{2}}{1/n^{2}},\frac{C/n^{2}}{1/n^{3}}$. They tend to $0,C,\infty$ respectively when $n\to\infty$, and all have the form ${{\to 0}\over{\to 0}}$.

NOTE: $(\to 1)^{\to\infty}$ is different from $1^{\to\infty}$, as [b]ZetaX[/b] pointed out in his second post.

Thank you.

If the value is tending toward 1, that value to infinite is undefined.

But if the value is exactly 1, it's infinite product is 1.

Also, if $a^{0}= 1$, then $1^{\infty}$ is undefined. So is $1^{\infty}$ also undefined?

EDIT: Nevermind, I see that if we raise $a^{0}= 1$ to infinite, or $\frac{1}{0}$, that the denominator is actually tending towards 0, since 1/0 as an explicit value is undefined. So that means, raising 1 to a value tending to infinite is still 1.


Let $ a\oplus b\equal{}3a\plus{}4b$ for all real numbers $ a$ and $ b$.  Find $ 3\oplus 1$.


Solve the inequality

$ \lvert\ x\minus{}1 \rvert \plus{} 3\lvert\ x\minus{}3 \rvert \plus{}5\lvert\ x\minus{}5 \rvert\plus{}...\plus{}2009\lvert\ x\minus{}2009 \rvert \geqslant 2\lvert\ x\minus{}2\rvert\plus{}4\lvert\ x\minus{}4 \rvert\plus{}6\lvert\ x\minus{}6 \rvert\plus{}...\plus{}2008\lvert\ x\minus{}2008 \rvert$  :?:

(O.Kukush).

__________________________________
$ \textbf{Azerbaijan Land of Fire }$

[quote="Pirkuliyev Rovsen"]Solve the inequality

$ \lvert\ x \minus{} 1 \rvert \plus{} 3\lvert\ x \minus{} 3 \rvert \plus{} 5\lvert\ x \minus{} 5 \rvert \plus{} ... \plus{} 2009\lvert\ x \minus{} 2009 \rvert \geqslant 2\lvert\ x \minus{} 2\rvert \plus{} 4\lvert\ x \minus{} 4 \rvert \plus{} 6\lvert\ x \minus{} 6 \rvert \plus{} ... \plus{} 2008\lvert\ x \minus{} 2008 \rvert$  :?:

(O.Kukush).

[/quote]
It holds for all $ x\in\mathbb R$ and we can use majorization theory to prove it  :D

Let $ f_n(x): \equal{} \sum_{k \equal{} 0}^n(2k \plus{} 1)\cdot|x \minus{} (2k \plus{} 1)|$ and $ g_n(x): \equal{} \sum_{k \equal{} 1}^n 2k \cdot|x \minus{} 2k |$, further $ h_n(x): \equal{} f_n(x) \minus{} n\cdot|x \minus{} (2n \plus{} 1)|$.
 It is sufficient to prove $ h_n(x)\ge g_n(x)$ for all $ x\in\mathbb R$.

By majorization theory, it is equivalent to prove $ \pi_n\succ \rho_n$ for the corresponding partitions, where
\[ \pi_n \equal{} (1_13_3...(2n \minus{} 1)_{2n \minus{} 1}(2n \plus{} 1)_n)\]
and
\[ \rho_n \equal{} (2_24_4...(2n)_{2n})\]
are both partitions of the same total $ {2n \plus{} 2\choose3}$.  (As usual for partitions, the indices denote multiplicities.)

We'll use an easy induction.
For $ n \equal{} 1$, we have $ (3,1)\succ(2,2)$.
For showing
\[ ((2n \plus{} 1)_n(2n \minus{} 1)_{2n \minus{} 1}...3_31_1) \succ((2n)_{2n}(2n \minus{} 2)_{2n \minus{} 2}...4_42_2)\]
we have to compare the partial sums of both sides. For the first $ 2n$ terms there is no problem, and for the $ 2n$th one they are equal, so we can remove them and are just left with $ \pi_{n \minus{} 1}\succ \rho_{n \minus{} 1}$, which is true by induction.  :lol:

Equality of $ f_n(x)$ and $ g_n(x)$ occurs only for $ x \equal{} 2n \plus{} 1 \equal{} 2009$.


[quote="madness"]What is the major product in Elbs Persulphate oxidation - Catchecol or Quinol?[/quote]
i think it is catchecol as i have heard of this elbs reaction in  only one place where our teacher has taught us ie preparation of anthracene and in that we use only 1,2 substituted benzene  reagents so is it right???i am sure it is catchecol!!! :lol:  :lol:

Different people different opinions.  :D

[quote="madness"]Different people different opinions.  :D[/quote]
let they have different opinions tell the answer???

[quote="pardesi"]it's quinol due to steric hidrance of the intermediate[/quote]
are you sure???

In the Elbs Persulphate Oxidation the major product is hydroquinone. Catechol derivatives are only obtained when the para position is blocked, but then the reaction is slower and yields are lower.

Yes thats what i thought too. But is cathecol a kinetic product?  :maybe:

no in any case catechol could only be a "thermodynamic product" because of the high stability due to intramolecular H-bonding...also it will have a comparatively high activation energy due to steric reason

P.S.: with this post i am the Indian with Highest number of posts(officially)   :first: crossing Rushil.

I think the same way as carcul and hydroquinone is the major product.
The quinol formed(as least steric hindrance) will readily undergo further oxidation
to give hydroquinone due to extended conjugation.
This is why phenol on long exposure to air becomes brown due to its oxiation to quinone

@pardesi: I think catechol is the kinetic product because the electron density on the orho
is going to be relatively high and so the S2O8 2- might try and attack the ortho yielding the
ortho product and at higher temperatures quinol is the product.


trigonometry
inequalities proposed
inequalities

[quote="SUPERMAN2"]Let $ a,b,c > 0$ satisfy $ a^2 \plus{} b^2 \plus{} c^2 \plus{} abc \equal{} 4$.Prove that
$ \sqrt {2 \minus{} a} \plus{} \sqrt {2 \minus{} b} \plus{} \sqrt {2 \minus{} c} \leq 3$.[/quote]

Trig substitution kills it.

[hide="hint"]
$ a\equal{}2\cos{A}$, $ b\equal{}2\cos{B}$, $ c\equal{}2\cos{C}$, where $ A$, $ B$, $ C$ are angles of a triangle.[/hide]


If $S_{xx}=\sum\limits^n_{i=1} x^2_i-\dfrac{\left(\sum\limits^n_{i=1} x_i\right)^2}{n}$ , $S_{yy}=\sum\limits^n_{i=1} y^2_i-\dfrac{\left(\sum\limits^n_{i=1} y_i\right)^2}{n}$ ,  $S_{xy}=\sum\limits^n_{i=1} x_iy_i-\dfrac{\left(\sum\limits^n_{i=1} x_i\right)\left(\sum\limits^n_{i=1} y_i\right)}{n}$

for $i,n\in \mathbb{N}$ , $x_i,y_i\in\mathbb{R}$

Prove that $\left|\dfrac{S_{xx}}{S_{xy}}\right|\geq \left|\dfrac{S_{xy}}{S_{yy}}\right|$

[hide="click if you are interested with source"]
This inequality is actually some application in statistic where we were to calculate the gradient of the regression line and such . The interesting part is gradient of the line $x$ on $y$ is always greater or equal to the gradient of the line $y$ on $x$(when they are drawn in same plane ) . Well , i try to prove it in inequality ways but in vain . It looks like Cauchy but somehow I didnt manage to get it .  So I guess maybe someone out there can give me a help  :) [/hide]

[quote="julien_santini"]As it is posted it is obviously wrong since $S_{yy}$ or $S_{xy}$ can be $0$. You should rewrite it as:
$S_{xx}S_{yy} \geq |S_{xy}|$, which is now true in general. But that is just the Cauchy-Schwarz inequality applied to the bilinear symmetric positive form $(x,y) \rightarrow S_{xy}$.[/quote]

I guess you mean $|S_{xy}|^2$  ;)  . Anyway , what is mean by bilinear symmetric positive form you stated above ? Can you explain more detail ?

Yeah I meant $S_{xx}S_{yy} \geq S_{xy}^{2}$.

Cauchy-Schwarz inequality remains true for any scalar product, and also any bilinear symmetric positive form (but the condition of inequality will change in the latter case). In your question, $(x,y) \rightarrow S_{x,y}$ is such a form. For the definition of the terms, Google or another member will do a great job ;).


show
sinA*sinB*sinC<=A*B*C*(3sqrt(3)/(2pi))^3
where A,B,C are the radian measures of a triangle

[quote="belenos"]Believe it or not, log (sin(x)/x) is concave. That's it  :)[/quote]

JENSEN'S STRIKES AGAIN.


I have a question about the registration for MathCamp. I didn't realize there was a mail-in component until I checked my account a little while ago. Would there be some way for me to get my forms to the MathCamp office on time? I wouldn't have waited until recently to access my account; I thought I needed to wait until I heard back on a scholarship application. Thanks.

It should be fine, but send us an email to let us know that the forms are slightly late.


Να δειχθεί ότι $ a^b \plus{} b^a > 1$, $ \forall a,b\in(0,1)$.Βασικά εκεί που τη βρήκα τη ζητούσε $ \forall a,b > 0$ αλλά η περίπτωση $ a\ge1$ ή $ b\ge1$ είναι πανεύκολη. :wink:

Λοιπόν μιας και δε βλέπω να ασχολείται κανείς βάζω μία λύση που σκέφτηκα μόλις τώρα αλλά ας μου πει κανείς μήπως κάνω κάποιο λάθος γιατί αυτή τη στιγμή είμαι πολύ κουρασμένος :wink:
[hide]Θεωρούμε την $ f(x) \equal{} a^x,x\in[0,1]$.Τότε $ f''(x) \equal{} a^x(lna)^2 > 0$ άρα η $ f$ είναι κυρτή.Οπότε θα είναι "πάνω" από την εφαπτομένη της στο 0 δηλαδή $ a^x \minus{} 1 \ge xlna \Rightarrow a^b \ge blna \plus{} 1$.Όμοια $ b^a \ge alnb \plus{} 1$. Άρα θα έχουμε
$ a^b \plus{} b^a \ge alnb \plus{} blna \plus{} 2$.Όμως
$ {blna \plus{} alnb \minus{} blnb \minus{} alna \equal{} (b \minus{} a)(lnb \minus{} lna) \ge 0\Rightarrow alnb \plus{} blna\ge alna \plus{} blnb \equal{} lna^a \plus{} lnb^b\ge 2ln{(\frac {1}{e})}^{\frac {1}{e}} \equal{} \minus{} \frac {2}{e} > \minus{} 1}$
qed :) [/hide]

Φιλε paulos18
η ανισοτητα ειναι

$ alna\plus{}blnb\ge alnb\plus{}blna$ οπως ειχαμε συζητησει και εδω http://www.mathlinks.ro/viewtopic.php?t=194836

Επισης πως βγαζεις οτι $ lna^a \plus{} lnb^b\ge 2ln{(\frac {1}{e})}^{\frac {1}{e}}$ ?
Ουτως η αλλως νομιζω οτι αυτο $ alnb\plus{}blna>\minus{}1$ δεν ισχυει για $ a\equal{}\frac{1}{2}$ και b κοντα στο 0
Πες μου αν κανω καπου λαθος

Φιλικα,
Αλεξανδρος
 :)

Ναι τώρα το είδα μου ξέφυγε ένα μείον. Είναι $ blna \plus{} alnb \minus{} blnb \minus{} alna \equal{} (b \minus{} a)(lna \minus{} lnb) \le 0$ :blush:
Το άλλο προκύπτει από τα ακρότατα της $ f(x) \equal{} x^x \equal{} e^{xlnx}$

Τελικά ποια είναι η λύση;Κάποιος παιδιά;;;; :o  :maybe:  :huh:

Νομίζω η ανισότητα του Bernoulli (http://en.wikipedia.org/wiki/Bernoulli_inequality) κάνει κατι εδώ.....
Όσο το a,b ∈ (0,1) τότε υπάρχουν αντίστοιχα κάποια Α,Β τέτοια ώστε να ΄ναι και τα δύο μαεγαλύτερα της μονάδας και a=1/A and b=1/B.
Επιπλέον αφού Α,Β>1, τότε θα υπάρχουν αντιστοιχα και οι A' & B' (θετικοί αμφότεροι) τέτοιοι ώστε A=1+A' and B=1+B'. Λαμβάνοντας αυτές τις σχέσεις υπόψη η ανισότητα γίνεται ως εξής:
1/(1+A')^b+1/(1+B')^a>1. Η ανισότητα τώρα του Bernouli μας λέει ότι για κάθε
μη-μηδενικό x>-1 and c ∈(0,1) έχουμε  (1+x)^c<1+cx . Έτσι στη δικιά μας έχουμε
(1+A')^b<1+bA'  and  (1+B')^a<1+aB' δηλαδή και 1/(1+A')^b>1/(1+bA') and 1/(1+B')^a>1/(1+aB').  Προσθέτω κατά μέλη και γίνεται:
1/(1+A')^b+1/(1+B')^a>1/(1+bA')+1/(1+aB').
Όμως A'=1/a-1 and B'=1/b-1. Έτσι :
1/(1+bA')+1/(1+aB')=a/(a+b-ab)+b/(a+b-ab)
=(a+b)/(a+b-ab)
=1+(ab)/(a+b-ab)=1+1/(1/a+1/b-1).
Αφού a and b ∈ (0,1), τότε 1/a και 1/b είναι μεγαλύτερα του άσσου και έτσι
1/a+1/b-1>1 άρα και θετικοί . Αυτό σημαίνει κιόλας 1+1/(1/a+1/b-1)>1.

Νομίζω Q.E.D. αλλά μπορεί και να 'ναι πατάτα όλη η σκέψη....Σόρι προκαταβολικά για τυχόν typo και που δυσκολεύεστε να το διαβάσετε επείδή δεν ξέρω LaTeX...Να μου επισημάνετε και το παραμικρό λάθος σας παρακαλώ και να μου το εξηγήσετε επειδή είμαι Α' λυκείου και όχι καλός.....

[quote="wallace"]Νομίζω η ανισότητα του Bernoulli (http://en.wikipedia.org/wiki/Bernoulli_inequality) κάνει κατι εδώ.....
Όσο το $ a,b \in (0,1)$ τότε υπάρχουν αντίστοιχα κάποια $ A,B$ τέτοια ώστε να ΄ναι και τα δύο μαεγαλύτερα της μονάδας και $ a \equal{} \frac {1}{A}$ and $ b \equal{} \frac {1}{b}$.
Επιπλέον αφού $ A. B > 1$, τότε θα υπάρχουν αντιστοιχα και οι $ A'$ & $ B'$ (θετικοί αμφότεροι) τέτοιοι ώστε $ A \equal{} 1 \plus{} A'$ and $ B \equal{} 1 \plus{} B'$. Λαμβάνοντας αυτές τις σχέσεις υπόψη η ανισότητα γίνεται ως εξής:
$ \frac {1}{(1 \plus{} A')^b} \plus{} \frac {1}{(1 \plus{} B')^a} > 1$. Η ανισότητα τώρα του Bernouli μας λέει ότι για κάθε
μη-μηδενικό $ x > \minus{} 1$ and $ c \in (0,1)$ έχουμε  $ (1 \plus{} x)^c < 1 \plus{} cx$ . Έτσι στη δικιά μας έχουμε
$ (1 \plus{} A')^b < 1 \plus{} bA'$  and  $ (1 \plus{} B')^a < 1 \plus{} aB'$ δηλαδή και $ \frac {1}{(1 \plus{} A')^b} > \frac {1}{1 \plus{} bA'}$ and $ \frac {1}{(1 \plus{} B')^a} > \frac {1}{1 \plus{} aB'}$.  Προσθέτω κατά μέλη και γίνεται:
$ \frac {1}{(1 \plus{} A')^b} \plus{} \frac {1}{(1 \plus{} B')^a} > \frac {1}{1 \plus{} bA'} \plus{} \frac {1}{1 \plus{} aB'}$.
Όμως $ A' \equal{} \frac {1}{a \minus{} 1}$ and $ B' \equal{} \frac {1}{b \minus{} 1}$. Έτσι :
$ \frac{1}{1 \plus{} bA'} \plus{} \frac {1}{1 \plus{} aB'} \equal{} \frac {a}{a \plus{} b \minus{} ab} \plus{} \frac {b}{a \plus{} b \minus{} ab} \equal{} \frac {a \plus{} b}{a \plus{} b \minus{} ab} \equal{} 1 \plus{} \frac {ab}{a \plus{} b \minus{} ab} \equal{} 1 \plus{} \frac {1}{\frac {1}{a} \plus{} \frac {1}{b} \minus{} 1}$.
Αφού $ a,b \in (0,1)$, τότε $ \frac {1}{a},\frac {1}{b} > 1$ και έτσι
$ \frac {1}{a} \plus{} \frac {1}{b} \minus{} 1 > 1$ άρα και θετικοί . Αυτό σημαίνει κιόλας $ 1 \plus{} \frac {1}{\frac {1}{a} \plus{} \frac {1}{b} \minus{} 1} > 1$.

Νομίζω Q.E.D. αλλά μπορεί και να 'ναι πατάτα όλη η σκέψη....Σόρι προκαταβολικά για τυχόν typo και που δυσκολεύεστε να το διαβάσετε επείδή δεν ξέρω LaTeX...Να μου επισημάνετε και το παραμικρό λάθος σας παρακαλώ και να μου το εξηγήσετε επειδή είμαι Α' λυκείου και όχι καλός.....[/quote]
Αν έκανα κάπου λάθος στη μεταφορά της λύσης σου σε Latex διόρθωσέ με..
Πάντως το είχα δημοσιεύσει και στο αγγλικό foroum και λύθηκε για όποιον ενδιαφέρεται εδώ: http://www.mathlinks.ro/viewtopic.php?t=204371

Λίγο διαφορετικά (in english όμως επειδή βιάζομαι).....

Suppose x  1.
Then xy  1 and yx > 0.
Therefore xy + yx > 1.

Now suppose 0 < x < 1.  Then 1/x > 1.

By Bernoulli's inequality (Mitrinovic's generalization of), (1 + x/y)1/x > 1 + 1/y.
Hence (1 + x/y)1/x > 1/y.
Then 1 + x/y > (1/y)x, since x/y > 0 and y > 0.
That is, (x + y)/y > (1/y)x.
Taking the reciprocal of both sides reverses the inequality, and so y/(x + y) < yx.

By symmetry, x/(x + y) < xy.
Adding, we get 1 < xy + yx.

Therefore xy + yx > 1, for all positive real x and y.

Δεν καταλαβα τιποτα  :roll:
Μαθε Latex! Ειναι πολυ ευκολο...

Καταρχήν γεια σε όλους και συγχαρητήρια για το πολύ ωραίο forum.
Για την άσκηση μου φαίνεται ότι μπορεί εύκολα να δειχθεί και με κυρτότητα.Αφού $ 0 < a < 1$ η συνάρτηση $ f(x) = x^a$ προφανώς είναι κοίλη άρα
${ f \left( \frac {1}{b} \right) - f(1) \le f'(1) \left( \frac {1}{b} - 1 \right) \Rightarrow \left( \frac {1}{b} \right)^a - 1 \le a \left( {\frac {1}{b}} - 1 \right) \Rightarrow \left( \frac {1}{b} \right)^a \le \frac {a}{b} - a + 1 < \frac {a}{b}} + 1 \Rightarrow \frac {1}{b^a} < \frac {a + b}{b}\Rightarrow b^a > \frac {b}{a + b}$
μετά τα ίδια για το $ a^b$ αθροίζουμε και QED.Βέβαια αν το καλοσκεφτεί κανείς ουσιαστικά η ίδια λύση είναι με την ανισότητα του Bernoulli στο αγγλικό forum γιατί στην απόδειξη της γενικευμένης ανισότητας Bernoulli χρησιμοποιούμε κυρτότητα αλλά νομίζω έτσι είναι λίγο πιο εύκολο :)


Find the number of odd coefficients in the expansion of: $(x^{2}+x+1)^{n}$.

i know how to solve it, but I don't think the solution is suitable for Pre-olympiad.

I have only gotten as far as showing that [hide="it is congruent to this..."] $\prod (x^{2 \cdot 2^{i}}+x^{2^{i}}+1) \bmod 2$

Where $i$ is such that $2^{i}$ is one of the binary digits of $n$ (this can be proven by Lucas or similar).  Unlike the case with $(x+1)$, dealing with this case becomes quite a hassle when digits are close together  :( [/hide]

Here is what I came up with.  As t0rajir0u suggested, let's look at the binary expansion of $n$.  Specifically, let's look at the blocks of $1$.  Let $b_{1}$, $b_{2}$, ..., $b_{t}$ be the lengths of those blocks.  Then the number of odd coefficients is
\[\prod_{i=1}^{t}\frac{4 \cdot 2^{b_{i}}-(-1)^{b_{i}}}{3}\, . \]

The proof method is to first analyze the case when $n$ is 1 less than a power of two (say $2^{b}-1$).  In that case, we can say exactly how the odd coefficients are distributed.  (Except for a couple of coefficients in the middle, exactly two out of every three consecutive coefficients will be odd.)

To handle the general case, we can use the product that t0rajir0u gave.  Because each block of 1's is separated by at least one 0, the different blocks will not overlap in the calculations.

I hope I didn't make a mistake.


Didn't go too bad, though, I'm kind of angry...

Finished the gold contest after 1.5 hours, spent 1.5 more hours writing test cases and I thought I made another perfect score... until the result came down...

[code]                     -- case number --
            1  2  3  4  5  6  7  8  9 10 11 12
cowturn     *  *  *  *  *  *  *  *  *  *
lineup      *  *  x  *  *  *  *  *  *  *  *  *
ranking     *  *  *  *  *  *  *  *  *  *[/code]

Grrrrr!!! I initialized the "answer" variable to 1, not realising that the answer could also be 0.  :(

Not great, I suppose I'll have to be home for a week in June instead of going to computer camp, but then it _is_ gold and I find it amazing that I'm in gold, so I'm happy enough.

[code]                    -- case number --
           1  2  3  4  5  6  7  8  9 10 11 12
cowturn     *  *  *  *  *  *  t  t  t  t
lineup      *  *  x  x  x  x  t  t  t  t  *  *[/code]

Didn't know how to do the other, spent about an hour trying to do it. Tried to do an RMQ for lineup, but it worked just as well as my bruteforce solution. Cowturn was fun though. Java's hard to do in time always; I had the right[analysis] solution, but you see I TOd on 4.

Lol, I found it harder than previous contests:

[hide="my results"]
[code]
                     -- case number --
            1  2  3  4  5  6  7  8  9 10 11 12
cowturn     *  *  *  t  t  t  t  t  t  t
lineup      *  *  *  *  *  *  *  *  *  t  *  *
ranking     *  *  *  *  *  *  *  *  *  *
[/code]
[/hide]

[hide="cowturn solution a la zhai"]
Consider the polynomial with coefficients equal to the input data (1 for B and 0 for F). Then dividing it by $1+x+\ldots+x^{k-1}$ is equivalent to whatever operation you want to perform. So this is the same (in mod 2, where we are working) as multiplying by $x+1$ and dividing by $x^{k}+1$. Implement this and you are essentially done.
[/hide]

[quote="Weeblie"]cowturn analysis:

[hide]It's actually a rather easy task. Loop through all "lengths". For each length, start from the first position and greedily walk to the end to "correct" the cows so they point forward. O(n^2) solution which passes the time. :)[/hide][/quote]

Not in java :P.

[code]

                     -- case number --
            1  2  3  4  5  6  7  8  9 10 11 12
balance     *  *  *  *  *  *  *  t  t  t
expense     *  *  x  x  x  x  x  x  t  t
traffic     *  *  *  *  *  *  *  *  *  *  *  *
[/code]

I tried to do expense with a greedy algorithm - I disproved it after the contest. I also had the O(N^2) solution to balance - precomputing their way is very nice. I was actually quite surprised that I got full credit for traffic. My code breaks if any field at all has more than 770 paths going to or from it. However, no such test case existed, so I won :D.

[code]cowturn     *  *  *  *  *  *  *  *  *  *
lineup      *  *  *  *  *  *  *  *  *  *  *  *
ranking     *  x  x  x  x  x  *  x  t  t [/code]

I interpreted ranking wrong :(. I thought he could get the results of each comparison back before making the next one, so my solution did not work obviously. My numbers were considerably smaller (but I'm not sure at all if they are even right, I suspected not).

Well, since everyone is already going to know my results anyway, I might as well
[hide="show everybody right now"][code]                     -- case number --
            1  2  3  4  5  6  7  8  9 10 11 12
cowturn     *  *  *  *  *  *  *  t  t  t
lineup      *  *  *  *  *  *  *  t  t  t  *  *
ranking     *  x  x  x  t  t  t  t  t  t[/code][/hide]
Yeah... couldn't quite get my solutions fast enough for 'lineup' and 'cowturn'. For 'ranking' I realized it was basically trying to build a strongly connected directed acyclic graph with the fewest additional edges possible, but I didn't really know how to do that.  :roll:
So... can anybody explain to me how to do the 'ranking' problem then?  :)
I did read the analysis for it, and I [i]thought[/i] I understood it. But then I tried to implement a solution, and it didn't work, so apparently I didn't.  :|

Also, I'm not sure I understand exactly how the XORing for cowturn seems to work. ([url]http://ace.delos.com/TESTDATA/MAR07.cowturn.htm[/url]) Could someone explain how that takes care of all of the flips?
(specifically, the following loop:)
[code]for (i=0; i<=N-k; i++) {
    count += Parity[i];
    Parity[i+k] ^= Parity[i];
  }[/code]

OK, maybe I'm just really, really dumb (third question already), but for 'lineup' ([url]http://ace.delos.com/TESTDATA/MAR07.lineup.htm[/url]), how can you sort all of the a [] entries in order to find x and y with the biggest separation for which a[x][k] = a[y][k] for all l?

I think I [i]really[/i] need more practice with these contests.  :wink:

(By the way, JSteinhardt and paladin8, good job on the last TopCoder round!  :) Hope to see you two at Purdue!)

[quote="Weeblie"]cowturn analysis:

[hide]It's actually a rather easy task. Loop through all "lengths". For each length, start from the first position and greedily walk to the end to "correct" the cows so they point forward. O(n^2) solution which passes the time. :)[/hide][/quote]

I originally had the problem with $N \le 500$ which lets a naive $O(N^{3})$ pass, which is shamefully easy for Gold. I'm glad they at least made it $N \le 5000$. That was my favorite problem I submitted :). I also sped it up a little by sieving, i.e. if some $k$ does not work, then any multiple of $k$ cannot work.

@nebula42: I know you can sort vectors in C++, so that should work. I used a map <vector <int>, int> though, which makes the solution very simple.

EDIT: To elaborate, I kept an array of the number of cows who had each characteristic as I processed the input. At each step, I created a new array that initialized the first element to zero and held the relative differences to the first element. For example,

1 2 3 4 -> 0 -1 -2 -3

and

4 5 6 7 -> 0 -1 -2 -3.

Any time the new array is the same as a previous one, the lineup is balanced between the two indices. So with my map I stored the smallest index that some vector (0 -1 -2 -3, for example) showed up.

[quote="JSteinhardt"]Consider the polynomial with coefficients equal to the input data (1 for B and 0 for F). Then dividing it by $1+x+\ldots+x^{k-1}$ is equivalent to whatever operation you want to perform. So this is the same (in mod 2, where we are working) as multiplying by $x+1$ and dividing by $x^{k}+1$. Implement this and you are essentially done.[/quote]

Shouldn't it be multiply by $x-1$ and divide by $x^{k}-1$?

But anyway, that's a pretty awesome solution. Funny how my problem turns out to be mathematical :wink:.

Yes, but we are working in mod 2, so that $-1 \equiv 1$. It's basically equivalent to xoring the sequence with itself shifted by $1$, which means that an (effective) xor of length $k$ actually only changes two bits.

Funnily, I misinterpreted the problem as well (the way we interpreted it, btw, is NP). But since I obviously couldn't solve it, since it's NP, I submitted a BS solution that involved floodfilling to get all possible initially deducible relations, then counting the number of leftover edges. Fortunately for me, this was the correct solution to the intended interpretation of the problem  :D .

Btw, Jeffrey, did you already know the solution to the $O(N^{2})$ case or did you have to solve it during the contest?

@nebula42: Thanks!

Oh, haha. Forgot about mod 2.

And no, I only had the $O(N^{3})$ coded up already, since I usually don't think too hard about the solutions to my problems. But it definitely didn't take as long as I would have needed to think of the solution from scratch.

well i think i cant understand the ranking problem, can any one help me?

for example when i give this test case to the judge soln:

1 > 2
3 > 4 > 5 > 6

then it answers 8.

but should not it be 2?

for example, say we will merge the second sequence into the first one. then we can do it with in 4+2=6 asking. coz we already know the relationship among {3,4,5,6} and {1,2}. so once 3 is placed in the sequence we will ask from after position of 3. whats wrong with this thinking?

huh.......

the problem means so? i am very angry with it now. hwo did others correctly interpret it? i again read it and i cant understand how do they mean so in the problem statement!

When I read the task, I noticed that it could be interepted in two ways. Knowing that one of them is NP complete, I went for that the task asked for the other. And, to be 100% sure, I sent a message to RK. ;)

How did you know that cowturn was NP complete (what problem did you reduce it to)?

[quote="paladin8"]That's the same reason I missed the problem; we interpreted incorrectly. He has to make the entire list BEFORE doing ANY comparisons. So he cannot assume he knows where a cow will end up while making his list.[/quote]
Oh man... I just realized I also misunderstood the problem.  :wallbash:
Oh well... I don't know if I would have been able to solve it anyway though.  :| Although I guess now the analysis seems to make more sense.
Next time, I think I'll try to read the problem twice before doing [i]anything[/i].  :wink:


AC and BC are tangents to circle P at points A and B respectively, PC=7, and the diameter of circle P is 7.  If the area of the region inside quadrilateral APBC, but outside the circle, is expressed in simplest form a sqrtb +c*pi, what is the value of 8asq b/c+3?

[quote="myspacesucks"] what is the value of 8asq b/c+3?[/quote]
Not clear at all like question ! Besides , $P$ is the center of circle $P$ ? :mad:

How can $AC$ and $BC$ be tangent, and $PC$ (if $P$ is a point on the circle) be the diameter?

The question could be improved you know!!! :P

But maybe this is what you wanted

[hide]
Radius of circle P would be half of the diameter which is 7
$radius=\frac{7}{2}$

Triangle PBC and PAC are definitely 30-60-90 triangles.
Therefore AC and BC would be $\frac{7}{2}\sqrt{3}$

The area of APBC would be
$2\frac{1}{2}(\frac{49}{4}\sqrt{3})$

Angle APB equals 120. the overlapping area would be
1/3 times (7/2)^2*pi.

The desired area is then
$\frac{49}{4}\sqrt{3}-\frac{49}{12}\pi$
Here, a=49/4, b=3, c=49/12.

$8a\sqrt{b/c}+3$
is $8\frac{49}{4}\sqrt{\frac{3}{49/12}}+3$
or $98\frac{6}{7}+3$ or $84+3$ or $87$

The answer is $87$
[/hide]


geometry
circumcircle
parallelogram
geometric transformation
reflection
analytic geometry
graphing lines

Given a scalene acute triangle $ ABC$ with $ AC>BC$ let $ F$ be the foot of the altitude from $ C$. Let $ P$ be a point on $ AB$, different from $ A$ so that $ AF\equal{}PF$. Let $ H,O,M$ be the orthocenter, circumcenter and midpoint of $ [AC]$. Let $ X$ be the intersection point of $ BC$ and $ HP$. Let $ Y$ be the intersection point of $ OM$ and $ FX$ and let $ OF$ intersect $ AC$ at $ Z$. Prove that $ F,M,Y,Z$ are concyclic.

Actually the problem is kind of trivial. A quick look at the drawing shows that the definition of the points $ Y$ and $ Z$ are useless. What we really need to prove is that $ OF \perp FX$. For that we can use complex numbers: let $ a,b,c$ be the affixes of the triangle $ ABC$, $ a\overline a = b \overline b = c\overline c = 0$. Then $ h = a + b + c$, $ f = \frac { a + b + c - ab\overline c}{2}$, $ p = b + c - ab\overline c$. Then take $ X$ to be the intersection between the line $ BC$ and the perpendicular in $ F$ on $ OF$. We get the equations
\begin{align*} x + \overline x bc & = b + c \\
x\overline f + \overline x f & = 2 |f|^2 . \end{align*}
We get $ x = \frac { 2|f|^2 + \cfrac {b + c}{bc} f }{\overline f - \cfrac { f}{bc} }$, and now we just have to prove that $ h,x,p$ are collinear, namely $ \begin{array}{|ccc|}x & \overline x & 1 \\
h & \overline h & 1 \\
p & \overline p & 1 \end{array} = 0$, which is just an easy computation.

We really don't need complex numbers here. The following purely synthetic solution is quite natural.

Denote by $ C^{\prime}$ the second intersection of $ CH$ with the circumcircle of triangle $ ABC$. Since $ F$ is the midpoint of the segment $ HC^{\prime}$, the quadrilateral $ AC^{\prime}PH$ is a parallelogram, and $ F$ is its center of symmetry. Since $ X$ lies on line $ PH$, its reflection $ X^{\prime}$ into $ F$ lies on $ AC^{\prime}$. Thus, according to the butterfly theorem applied in the cyclic quadrilateral $ AC^{\prime}BC$ with circumcenter $ O$, we have that $ OF \perp XF$, and therefore the points $ F$, $ M$, $ Y$, $ Z$ are concyclic.

[quote="pohoatza"]We really don't need complex numbers here. The following purely synthetic solution is quite natural.[/quote]Well it took me around 2 minutes to find the above solution, and say another 10 minutes max to write it in the competition. I take 7 points at the Balkan in 12 minutes than the chance of not finding the synthetic solution in 20 or more :D

I have the pleasure to present you the synthetic solution I found during the competition.

I don't like complex numbers, but I like coordinates.
Put origin in $ F$ and $ B(b,0), b<0$, $ A(a,0), a>0$ and $ C(0,1)$. Then $ H(0,\minus{}ab)$ and $ O(\frac {a\plus{}b}2, \frac {ab\plus{}1}2)$, $ P(\minus{}a,0)$ and we compute $ X(\frac {b(ab\plus{}1)}{1\minus{}b^2}, \frac{\minus{}b^2 \minus{} ab}{1\minus{}b^2})$. So, slope of $ FO$ is $ \frac {ab\plus{}1}{a\plus{}b}$ and the slope of $ FX$ is $ \minus{}\frac{a\plus{}b}{ab\plus{}1}$ so $ OF\bot FX$, that's it.
Bye

[color=darkblue][b]Very nice Pohoata's and Nick Rapanos' proofs ![/b]

Indeed, the points $ M$ , $ Y$ , $ Z$ are useless . Here is a "cleaner" enunciation :[/color]

[quote] [color=darkred]Given a scalene acute triangle $ ABC$ with orthocenter $ H$ , circumcenter $ O$ and $ AC > BC$ .

Denote : $ F\in AB\ ,\ CF\perp AB$ ; the reflection $ P$ of $ A$ w.r.t. $ F$ ; $ X\in HP\cap BC$ . Prove that $ FO\perp FX$ .[/color] [/quote]
[quote="Virgil Nicula"][color=darkred][b][u]Lemma.[/u][/b] Let $ ABC$ be a triangle for which exists a point $ D\in (BC)$ so that $ AD\perp BC$ .

Consider an interior point $ X$ of the triangle $ ABD$ and an interior point $ Y$ of the triangle $ ACD$ so that

$ \widehat {XAB}\equiv\widehat {XBA}\equiv\widehat {YAD}\equiv\widehat {YCD}$ . Then $ DX\perp DY\ \Longleftrightarrow\ AB = AC$ .[/color][/quote]
[hide="Proof."]
[color=darkblue]Denote : $ \|\begin{array}{ccc} m(\widehat {XAB}) = y & \implies & \|\begin{array}{c} m(\widehat {XBD}) = B - y\ ,\ m(\widehat {XAD}) = 90^{\circ} - B - y \\
 \\
m(\widehat {YCA}) = C - y\ ,\ m(\widehat {YAC}) = 90^{\circ} - C - y\end{array} \\
 \\
m(\widehat {XDA}) = \phi & \implies & m(\widehat {XDB}) = 90^{\circ} - \phi \\
 \\
m(\widehat {YDC}) = \psi & \implies & m(\widehat {YDA}) = 90^{\circ} - \psi\end{array}\|$

Apply the trigonometric form of the [b]Ceva's theorem[/b] to the points $ X$ , $ Y$ in the triangles $ ABD$ , $ ACD$ respectively :

$ \{\begin{array}{c} \sin\widehat {XAB}\cdot\sin \widehat {XBD}\cdot\sin \widehat {XDA} = \sin\widehat {XAD}\cdot\sin\widehat {XDB}\cdot\sin\widehat {XBA} \\
 \\
\sin\widehat {YAC}\cdot\sin\widehat {YCD}\cdot\sin\widehat {YDA} = \sin\widehat {YAD}\cdot\sin\widehat {YDC}\cdot\sin\widehat {YCA}\end{array}\|$ $ \implies$

$ \{\begin{array}{c} \sin y\cdot\sin (B - y)\cdot\sin\phi = \cos(B + y)\cdot\cos \phi\cdot\sin y \\
 \\
\cos (C + y)\cdot\sin y\cdot\cos\psi = \sin y\cdot\sin\psi\cdot\sin (C - y)\end{array}\|$ $ \implies$ $ \{\begin{array}{c} \tan\phi = \frac {\cos (B + y)}{\sin (B - y)} = \frac {1 - \tan B\tan y}{\tan B - \tan y} \\
 \\
\tan\psi = \frac {\cos (C + y)}{\sin (C - y)} = \frac {1 - \tan C\tan y}{\tan C - \tan y}\end{array}$ .

Therefore, $ DX\perp DY$ $ \Longleftrightarrow$ $ \frac {1 - \tan B\tan y}{\tan B - \tan y} = \frac {1 - \tan C\tan y}{\tan C - \tan y}$ $ \Longleftrightarrow$

$ (\tan B - \tan C)\cdot (\tan^2y - 1) = 0$ $ \Longleftrightarrow$ $ B = C$ $ \Longleftrightarrow$ $ AB = AC\ \ (\ y = 45^{\circ}\Longleftrightarrow PA\perp PB$ , what is falsely $ )\ .$

[u]Otherwise[/u], $ DX\perp DY$ $ \Longleftrightarrow$ $ \cos (B + y)\sin (C - y) = \cos (C + y)\sin (B - y)$ $ \Longleftrightarrow$

$ \sin (B + 2y - C) = \sin (C + 2y - B)$ $ \Longleftrightarrow$ $ B = C$ or $ y = 45^{\circ}$ $ \Longleftrightarrow$ $ B = C$ $ \Longleftrightarrow$ $ AB = AC$ .[/color][/hide]
[color=darkblue][b]Remark.[/b] If we'll apply the upper lemma to the $ C$ - isosceles triangle $ CAP$ , i.e. $ CA = CP$

and the points $ O$ , $ X$  then we'll obtain the required property $ FO\perp FX$ .[/color]

Just observe that reflection of $ X$ wrt $ CF$ is isogonaly conjugate to $ O$ wrt triangle $ AFC$ so $ FO \perp FX$.

i cant find what is difficult with this problem as we see that it can be done only after few trigonometric computations....

[color=darkblue]I am sorry, but I must to say that [b]this problem is "painted" clumsy[/b]. Here is "disgusting paint" : if we suppress the points $ M$ , $ Y$ , $ Z$
and replace the its conclusion with only "Prove that $ FX\perp FO$ " then obtain a classical problem which appears and in the book
[b]"Harmonic division" of V. N. & C.P.[/b] , where it is solved with the butterfly property (see the upper [b]Pohoata[/b]'s proof)
of the point $ F\in AB\cap CH$ in the circumcircle of $ \triangle ABC$ .

Best regards, Virgil Nicula

[b]P.S.1.[/b] I have a curiosity : [b]who is the author of the problem 1 from BMO 2008 ?[/b]

[b]P.S.2.[/b] My upper proof is an entertaiment for to find a [u]metrical proof - my great pleasure[/u] ![/color]

This problem is equivalent to 1996 shortlist problem.

Hmm this problem appears on the Blue MOP homework...

This problem can be solved directly by two applications of trig ceva.

Another approach:

$ \angle OCA \equal{} \angle OAC \equal{} m,\angle OCF \equal{} n$  $ \implies$  $ \angle HCB \equal{} m \equal{} \angle ABH$

$ CF\perp AP,AF \equal{} FP$  $ \implies$ $ \angle HPA \equal{} m,\angle BCP \equal{} n$

$ \angle XFB \equal{} \alpha,\angle HFZ \equal{} \beta$

 let we use in $ \triangle AFC,\triangle PFC$ trig ceva

$ \implies$  $ \alpha \equal{} \beta$   $ \implies$  $ FZ\perp FX$  $ \implies$  $ FMYZ$ concylic

Dear Mathlinkers,
this problem has a relation with the butterfly theorem...
see also
http://perso.orange.fr/jl.ayme  vol. 7 Butterfly... p. 55
Sincerely
Jean-Louis

Umm...
if I'm not mistaken and if my computations aren't either, then $OM\parallel FX \Leftrightarrow \dfrac{\tan{A}\cdot \cos{C}}{\sin{(A-B)}}=1$, and I think one can find angles $A,B,C$ to satisfy the condition and hence the point $Y$ (might) not exist in some situations..

My solution:

Let $ X' $ be the reflection of $ X $ in $ CF $ .

Easy to see $ X' \in AH $ .

Since $ \angle X'CA=\angle PCX=\angle FCO $ ,
so we get $ X', O $ are isogonal conjugate of $ \triangle CAF $ ,
hence $ \angle YFZ=\angle XFO=90^{\circ}-\angle OFC+\angle AFX'=90^{\circ}=\angle YMZ $ .
ie. $ F, M, Y, Z $ are concyclic

Q.E.D

Let $B'$ be the antipode of $B$ wrt $O$, and let $N$ be the midpoint of $AB$.
It suffices to prove that $OF \perp FX$.
It is well-known that $CH = 2ON = B'A$. Also, $PB=2AF-AB=2(AF-AN)=2NF$.
From $\angle XCH=\angle HAB = \angle XPB$ and $\angle CXH = \angle PXB$, we have $\triangle CXH \sim \triangle PXB$.
Now note that $\frac{FD}{DX}=\frac{LX}{DX}=\frac{CX \sin \angle XCH}{XP \sin \angle XPB}=\frac{CX}{XP}=\frac{CH}{PB}=\frac{2ON}{2NF}=\frac{ON}{NF}$, so $\triangle ONF \sim \triangle FDX$.
Therefore, we have $OF \perp FX$, as desired $\blacksquare$

We need $ \measuredangle XFO=90$ which is equivalent to $\measuredangle BFX = \measuredangle CFO $ or $\measuredangle XFH = \measuredangle OFA $.
applying the sine law in triangles $OFA $, $OFC $, $XFB$, $XFH$ we get : $$ \frac {sin\measuredangle BFX }{sin\measuredangle XFH} =\frac {sin\measuredangle CFO}{sin\measuredangle OFA}$$ and we know that $$\measuredangle BFX + \measuredangle XFH =\measuredangle OFA + \measuredangle CFO =90 $$ hence $\measuredangle BFX = \measuredangle CFO $ and $\measuredangle XFH = \measuredangle OFA $ and we are done.

[quote=orthocentre]Why does $FO$ being perpendicular to $FX$ imply that $F, M, Y, Z$ are concyclic?[/quote]

Because OM is already perpendicular to AC.


Prove that for any $ k$, $ k$ positive integer, there is also a positive integer $ n$ such as $ [ 1\plus{}\frac{1}{2}\plus{}\frac{1}{3}\plus{}...\plus{}\frac{1}{n}] \equal{} k$ ,  where $ [x]$ means the integer part of $ x$.

[quote="balan razvan"]Prove that for any $ k$, $ k$ positive integer, there is also a positive integer $ n$ such as $ [ 1 \plus{} \frac {1}{2} \plus{} \frac {1}{3} \plus{} ... \plus{} \frac {1}{n}] \equal{} k$ ,  where $ [x]$ means the integer part of $ x$.[/quote]

$ 1\plus{}\frac{1}{2}\plus{}\frac{1}{3}\plus{}\frac{1}{4}\plus{}...>1\plus{}\frac{1}{2}\plus{}(\frac{1}{4}\plus{}\frac{1}{4})\plus{}(\frac{1}{8}\plus{}\frac{1}{8}\plus{}\frac{1}{8}\plus{}\frac{1}{8})\plus{}...\equal{}1\plus{}\frac{1}{2}\plus{}\frac{1}{2}\plus{}....$

So $ 1 \plus{} \frac {1}{2} \plus{} \frac {1}{3} \plus{} ... \plus{} \frac {1}{n}$ can be made arbitrarily large.

$ \Rightarrow$ for any $ k$ we can find $ n$ so that $ 1 \plus{} \frac {1}{2} \plus{} \frac {1}{3} \plus{} ... \plus{} \frac {1}{n} < k \le 1 \plus{} \frac {1}{2} \plus{} \frac {1}{3} \plus{} ... \plus{} \frac {1}{n}\plus{}\frac{1}{n\plus{}1}<(1 \plus{} \frac {1}{2} \plus{} \frac {1}{3} \plus{} ... \plus{} \frac {1}{n})\plus{}1<k\plus{}1$, done.