algebra
polynomial
inequalities
complex analysis
complex numbers
Polynomials

A prime $p$ has decimal digits $p_{n}p_{n-1} \cdots p_0$ with $p_{n}>1$. Show that the polynomial $p_{n}x^{n} + p_{n-1}x^{n-1}+\cdots+ p_{1}x + p_0$ cannot be represented as a product of two nonconstant polynomials with integer coefficients

Set $x=10$. If the polynomial can be factored into two other polynomials, then $p$ can be expressed as two decimal factors, and so is not prime, a contradiction.

This seems really easy. Is there a flaw?

Flaw: The decimal factors could be $\pm 1$ or $\pm p$ if you set $x=10$.

[quote="Peter"]Indeed, that would be too easy to be true (but I admit it's deceiving). I'm afraid you'll need some complex analysis to kill this one correctly.[/quote]
Nope,this problem has very elementary solution,if I am not mistaken,it is enough to observe one inequality between roots and coefficients of the given polynomial...

[quote="Peter"]Inequalities between complex roots is complex analysis, no? You won't need deep theorems, obviously, since it's from the BaMO.[/quote]
Hmm...I didn't know that.Probably I have some misconceptions in definition of complex analysis.I can't figure out what you mean by your last sentence,whatever it means I agree with you,solution is pretty simple...
Maybe you would be so kind to post the proof,assuming you have solved this problem.

Well I don't even know a definition of complex analyis, but if you do analysis (inequalities) on complex numbers, I'd be inclined to call that complex analysis. Sorry if that's a wrong wording. :)

From Kalva: [quote]If w is a (complex) root of the polynomial, then since each coefficient is at most 9, we have |pn| ≤ 9(1/|w| + 1/|w|2 + ... + 1/|w|n-1). So if |w| ≥ 9, then |pn| ≤ 9(1/9 + 1/81 + ... ) < 9/8. But pn ≥ 2, so we must have |w| < 9.

Suppose the polynomial has a factor with integer coefficients (and positive degree less than n). Then Gauss' lemma tells us that it must be a product of two polynomials with integer coefficients (and each with positive degree less than n). Suppose they are f(x) and g(x). Suppose the (complex) roots of f(x) are z1, ... , zm. Then f(x) = A(x - z1) ... (x - zm) with A and integer. Hence |f(10)| = |A| |10 - z1| ... |10 - zm|. But |A| ≥ 1 and each factor |10 - zi| > 10 - 9 = 1. So |f(10)| > 1. Similarly, |g(10)| > 1. But f(10) and g(10) are integers and their product is the prime p. So we have a contradiction. So the polynomial cannot have any such factor. [/quote]

By the way, it is also in the Resources section on this site.

Isn't this Cohn's irreducibility criterion?


[hide]Obviously, x must be greater than -1.  SImilarly, [0,1) is undefined.  However, values from [-1,0) are clearly failures since the left hand side has an unattainable maximum of 1 while the right hand side has a minimum of $1+\sqrt{2}$.  For $[1,\infty)$, we get $\frac{(x^{2}-x+1)^{2}}{4x^{2}-4x}>1$.  Subtracting one, we get $\frac{x^{4}-2x^{3}-x^{2}+2x+1}{4x^{2}-4x}>0$.  Now, that factors into $\frac{(x^{2}-x-1)^{2}}{4x^{2}-4x}>0$ which is true for all values of x greater than 1 except x=$\frac{1+\sqrt{5}}{2}$.[/hide]


23. Consider two uniform spherical planets of equal density but unequal radius. Which of the following quantities is the same for both planets?
(a) The escape velocity from the planet's surface.
(b) The acceleration due to gravity at the planet's surface.
(c) The orbital period of a satellite in a circular orbit just above the planet's surface.
(d) The orbital period of a staellite in a circular orbit at a given distance from the planet's center.
(e) None of the above.

I'll give a few hints instead of answering:

a) $ E_{tot} \equal{} \frac {1}{2} mv_{esc}^2 \minus{} \frac {GMm}{R} \equal{} 0$ (at infinity, where potential = 0 and kinetic = 0)

b) Use the Law of Gravitation (you probably know this)

c) Use the concept of centripetal force, coupled with the Law of Gravitation. Use volume density $ \rho \equal{} \frac {M}{\frac {4}{3} \pi R^3}$. Main equation: $ T \equal{} \frac {2\pi R}{v}$.

d) Same as option c, except differentiate between the planets' radii, $ R_{1}$ and $ R_{2}$, and the orbit radius $ r$.

Oh yeah, I forgot to ask for hints. Ahh, thanks! I can't believe I keep on forgetting such simple concepts!

Here's the solution just to make sure I'm doing it correctly (I'm just showing c here)
[hide="solution"]Knowing that $ T \equal{}\frac{2\pi R}{v}$ and $ F_g\equal{}F_c\equal{}G\frac{Mm}{f^2}\equal{}\frac{mv^2}{r}$, you can rearrange to get $ v\equal{}\sqrt{\frac{GM}{r}}$ and plug it into the first equation to get $ T\equal{}2\pi r\sqrt{\frac{r}{GM}}$.
Since mass $ M$ is proportional to the planet's volume, one can say that $ M\equal{}k\frac{4}{3}\pi r^3\equal{}jr^3$ (where $ k$ and $ j$ are both constants).
Therefore, $ T\equal{}2\pi r\sqrt{\frac{r}{Gjr^3}}\equal{}\frac{2\pi}{Gj}$. Thus, the period does not depend on anything except some constants, so the period has to be same for both planets.[/hide]

Yes, looks right.

And option D doesn't work because the orbital radius doesn't cancel with the planet's radius, so $ T$ isn't independent of the two planets' radii.


prove that $a(a+1)(a+2)(a+3)+1$ is perfect square.

[quote="mahyar_math"]Show that the polynomial $x^{5}+x+1$can be expressed as the product
of two nonconstant polynomials with integer coefcients.[/quote]

[hide=" :spam: "]$x^{5}+x+1=(x^{2}+x+1)(x^{3}-x^{2}+1)$[/hide]

[quote="mahyar_math"]Show that the polynomial $x^{5}+x+1$can be expressed as the product
of two nonconstant polynomials with integer coefcients.[/quote]

[hide="simple factorization..."]
$(x^{2}+x+1)(x^{3}-x^{2}+1)$
use synthetic division[/hide]


superior algebra
superior algebra solved

Please help me with this problem

Let a and b be elements of a finite group G. Show that ab and ba have the same order.

Thank you.

Assume that $(ab)^n=e$, then $(ba)^n=b(ab)^nb^{-1}=b e b^{-1}=e$. Changing $a,b$ gives that they have the same orders.


let $ m\in\mathbb{N}$ be a fixed positive integer and $ x_n\equal{}1\plus{}mn^2$. Is it true that for every $ p$ - prime there is a term of this sequence divisible by $ q^p$ for some $ q\ge 2$ ?
The case $ p\equal{}2$ is trivial (consider $ x_{4m\plus{}3}$ and $ q\equal{}4m\plus{}1$), but I have no idea for $ p\equal{}3,5,7,\dots$ or for the general proof (if this conjecture is true)

Yes.  If $ q$ is an odd prime not dividing $ m$ one can use [url=http://en.wikipedia.org/wiki/Hensel%27s_lemma]Hensel's lemma[/url].  There's no benefit to be gained by restricting $ p$ to primes.

obviously if it works for $ p$ primes then for other $ p$ it works too, so the main problem was the case with primes
Thanks :) I haven't heard about Hensel's lemma before


invariant
combinatorics unsolved
combinatorics

There's a $ 3\times3$ square, one is empty and the others are with numbers 1~8 in it. Move one number up or down or left or right to the empty place each time. Prove it is impossible to do such change in finite steps,
$ \boxed{ \begin{array}{*{20}c}1 & 2 & 3 \\ 4 & 5 & 6 \\ 8 & 7 &{}\\ \end{array}}\to \boxed{ \begin{array}{*{20}c}1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 &{}\\ \end{array}}$

Loyd's game  :lol: Find one invariant :)

[quote="N.T.TUAN"]Loyd's game  :lol: Find one invariant :)[/quote]
But...to be more specific...what is the invariant :?:


Calculate the weight percent of Fe(III) in
$ K_3[Fe(C_2O_4)]3H_2O$ (theoretical)

Isn't missing something in your formula?

I don't know. What's missing? and once I find it how can use it to give me the answer

Look at the charges. If what you meant is $ K_3[Fe(C_2O_4)] \cdot 3H_2O$ then the formula is incorrect; if you wanted to mean $ K_3[Fe(C_2O_4)]_3 \cdot H_2O$ then it is correct but the "3s" are not needed.
Also, to calculate a mass percentage of an element in a compound just divide the mass of the element present in one mole of the compound by its molar mass, and then multiply by 100.


In a triangle $ ABC$, where $ a \equal{} BC$, $ b \equal{} CA$ and $ c \equal{} AB$, it is known that: $ a \plus{} b \minus{} c \equal{} 2$ and $ 2ab \minus{} c^2 \equal{} 4$. Prove that $ ABC$ is an equilateral triangle.

[quote="mohamed_3ab9or_maths"]$ a \plus{} b \minus{} c \equal{} 2$ and $ 2ab \minus{} c^2 \equal{} 4\implies (a \plus{} b \minus{} c)^2 \equal{} 2ab \minus{} c^2\implies a^2 \plus{} b^2 \plus{} 2c^2 \minus{} 2c(a \plus{} b) \equal{} 0$

$ a^2 \plus{} b^2 \plus{} 2c(c \minus{} a \minus{} b) \equal{} 0\implies 2ab \minus{} 4c\leq a^2 \plus{} b^2 \minus{} 4c \equal{} 0\implies 2ab \minus{} 4c\leq 0$

$ 2ab \equal{} 4 \plus{} c^2\implies 2ab \minus{} 4c \equal{} 4 \plus{} c^2 \minus{} 4c \equal{} (c \minus{} 2)^2\leq 0$. So $ c \minus{} 2 \equal{} 0\implies c \equal{} 2$.

Therefore, $ a \plus{} b \equal{} 4$ and $ 2ab \equal{} 8,\ (a \plus{} b)^2 \equal{} 16$ and $ 4ab \equal{} 16\implies (a \plus{} b)^2 \equal{} 4ab\implies a \equal{} b$

Then we deduce that $ a \equal{} b \equal{} c \equal{} 2$

So $ \triangle ABC$ is an equilateral triangle.[/quote]

I corrected and cleaned some parts of solution.


conics
geometry
angle bisector
geometry proposed

Let a triangle ABC and a point P inside it. AP, BP, CP meet BC, CA, AB in D,E,F. The angle bisector of $ \angle CPE$ meet the angle bisector of $ \angle PBC$ in $ P_1$ and the angle bisector of $ \angle PCB$ in $ P_2$, the angle bisector of $ \angle CPD$ meet the angle bisector of $ \angle PCA$ in $ P_3$ and the angle bisector of $ \angle PAC$ in $ P_4$, the angle bisector of $ \angle APE$ meet the angle bisector of $ \angle PAB$ in $ P_5$ and the angle bisector of $ \angle PBA$ in $ P_6$.

1) Prove that $ P_1$, $ P_2$, $ P_3$, $ P_4$, $ P_5$, $ P_6$ stay on the same conic $ \xi(P)$
2) Find the locus of the point P for which A is on the interior of $ \xi(P)$
3) Can A,B,C be all on the interior of $ \xi(P)$?

[hide="figure"][img]http://img442.imageshack.us/img442/6910/conicaty5.jpg[/img][/hide]


induction
number theory unsolved
number theory

$p$ is a prime number that is greater than $2$. Let $\{ a_{n}\}$ be a sequence such that $ na_{n+1}= (n+1) a_{n}-\left( \frac{p}{2}\right)^{4}$.

Show that if $a_{1}=5$, the $16 \mid a_{81}$.

$na_{n+1}= (n+1) a_{n}-\left( \frac{p}{2}\right)^{4}$

$\Longleftrightarrow \frac{1}{n+1}\left\{a_{n+1}-\left(\frac{p}{2}\right)^{4}\right\}=\frac{1}{n}\left\{a_{n}-\left(\frac{p}{2}\right)^{4}\right\}=\cdots\cdots =\frac{1}{1}\left\{a_{1}-\left(\frac{p}{2}\right)^{4}\right\},$ yielding Rust's result.


For circumference (O1), (O2) contact ben wherewith (O) for before at P, Q and in addition to after-birth. Circumference cutting this two-way's ben general tangent line (O) at 4 points, among them choosed B, C it be 2 points to lie the same margarine half-plane O1O2. Two-way's wherewith tangential rather only general parallel proof BC (O1), (O2)
 :(  :(

Maybe you had used an automatic way of translating, but the wording is ununderstandable, at least for me.


[hide]1/3 * 24 = 8    1/2*8 = 4       4/24 = 1/6 = 16 and 1/6 percent     and rounded to the nearest whole number is 17%[/hide]

[quote="MCrawford"]One-third of a 24-student class is absent today.  One-half of those were also absent yesterday.  What percent of the class has been absent for two straight days?  Express your answer to the nearest whole number.[/quote]

[hide]1/3 of 24 = 8
1/2 of 8 = 4
8-4=4
4/24=1/6
=0.166...
17%[/hide]

One piece of information in that problem could have been left out, and the problem would still be solvable.  What was that piece of information?

i don't know..
wait...could it be solved without knowing that there were 24 students?

the info about the 24 students can be left out cuz 1/2*1/3 = 1/6, so the answer would be 16.6... anyways.

8 are absent the firstt time
8/2=4
4/24=1/6
16.6..%

Not necessarily. What if there weren't 6n students? Do you cut 'em in halves and thirds like I do?

i don't know the answer to Treething's question but the answer to the original problem is[hide]17%[/hide]

one-third of 24 is 8, and one-half of that is 4. 4/24=1/6 or $16.\overline{6}$.  The nearest whole number is 17.

[quote="shinwoo"][hide]one third of the class=8
half of 8 = 4
4 / 24 = 1/6

100/6%=50/3% = 16.6.........%[/hide][/quote]
round the answer

[quote="Devendra Patel"]We can solve the problem without being that there are 24 students[/quote]
what, i don't understand what you are saying


Could someone translate in english thank you

----------------------------------
1/

fie  f,g :R $\rightarrow$R
functii surjective
Daca $go(g-f)$ este descrescatoare
si exista L>1, astfel incat $|g(x)-g(y)|\geq L|x-y|$ $\forall x,y \in R$

sa se arate ca f are un unic punit fix
--------------------------------------------------------
2/fie $A\in M(n,C)$ o matrice cu coeficienti intregi inversabila si astfel incat
multinea {$A^{k}, k\in N$} este finita
sa se demonstreze ca aceasta multine are cel mult $3^{n^2}$ element

1.Let f,g be surjective functions. If ... is a nonincreasing
function and if there exists L >1 such that ...., prove that f has
a unique fixed point.
2. Let A... be an invertible matrix with
integer coefficients, such that the set... is finite. Prove that this
set has at most ... elements.


Let $ a_1,a_2,...,a_6$ be real numbers such that:
$ a_1 \not \equal{} 0, a_1a_6 \plus{} a_3 \plus{} a_4 \equal{} 2a_2a_5 \ \mathrm{and}\ a_1a_3 \ge a_2^2$
Prove that $ a_4a_6\le a_5^2$. When does equality holds?

That's false!Consider for example a1=1;a2=2;a3=4;a4=14;a5=7;a6=10


linear algebra
matrix
linear algebra unsolved

Let $M$ be a set of matrix $A_{3,3}$ that has elements from ${ { 1, 2,3,4,5,6,7,8,9} }$. Prove the fallowing:
Show that, if B is from M then $B^{-1}$ is $not$ from M

If $A$ and $B$ are in $M$, each entry of $AB$ is at least $1\cdot 1+1\cdot 1+1\cdot 1=3$. Therefore, $AB$ is not the identity and the two matrices are not inverses.


[quote="Zamfirmihai"]Solve in $\mathbb Z$:
$\sqrt{x+\sqrt{x+\sqrt{x+...+\sqrt{x}}}}=y$, the number of $\sqrt$ is $2007$[/quote]

If I call $f_{n}(x)=\sqrt{x+\sqrt{x+\sqrt{x+...+\sqrt{x}}}}$, where the number of $\sqrt$ is $n$, then I have to solve $f_{2007}(a)=b$
So $f_{2006}(a)=b^{2}-a \in\mathbb{Z}$, so $f_{n}(a)\in \mathbb{Z}$ $\forall n\leq 2007$

So $f_{1}(a)\in\mathbb{Z}$ and so $a=u^{2}$
Then $f_{2}(a)\in\mathbb{Z}$ and $u^{2}+u=v^{2}$

But, if $u\neq 0$ $u^{2}+u$ is in $((|u|-1)^{2},(|u|+1)^{2})$  and can't be $v^{2}$

And the only solution $(x,y)$ is $(0,0)$


How to compute $\pi_{1}(\mathbb{S}^{2}\vee \mathbb{S}^{1})$ and $\pi_{1}(\mathbb{S}^{2}\vee \mathbb{S}^{2})$?

i guess you mean $X\vee Y$ to be $X \sqcup Y$ where you identify two points, one for each space, right?

if so, you can use van kampen's theorem, in both cases:
$A = \mathbb{S}^{2}\vee\mathbb{S}^{1}$: call $x_{2}\in \mathbb{S}^{2}, x_{1}\in \mathbb{S}^{1}$ the two points you identified, then you can find contractible open neighbourhoods of each point in its "original" space, and call them $U_{2}, U_{1}$. then $U_{1}\cup U_{2}\subset A$ is open and connected, which allows you to use quoted theorem.
same as before for the other thing.
so they come out to be $\mathbb{Z}$ and the trivial group.

anyway, you can do it more "by hands", and split any path $\gamma$ in $\gamma_{i}$, where each of these "sub-path" is closed, and starts in the points you've identified, and $\text{spt }\gamma_{i}$ lies in one of the two "original" spaces. you can do it, since $\text{spt }\gamma$ is compact...
then you have the same result..
of course, this is nothing but the proof of van kampen's theorem, a bit simplified...


If $r$ and $s$ are the roots of the equation $ax^2 + bx + c = 0$, the value of $\frac{1}{r^2} + \frac{1}{s^2}$ is:
\[ \text{(A)}\ b^2 - 4ac \qquad \text{(B)}\ \frac{b^2 - 4ac}{2a} \qquad \text{(C)}\ \frac{b^2 - 4ac}{c^2} \qquad \text{(D)}\ \frac{b^2 - 2ac}{c^2} \qquad \text{(E) none of these} \]

[hide]We wish to find the value of $\frac{1}{r^{2}}+\frac{1}{s^{2}}$.  If we can write this sum as a combination of the sums and products of the roots, we can find the value, because we know that the sum of the roots is $-\frac{b}{a}$, and the product is $\frac{c}{a}$.

We can do this by writing $\frac{1}{r^{2}}+\frac{1}{s^{2}}=\frac{r^{2}+s^{2}}{r^{2}s^{2}}=\frac{(r+s)^{2}-2rs}{(rs)^{2}}$.  Substituting in the sums and products of the roots gives us $\frac{\displaystyle\left(\displaystyle-\frac{b}{a}\right)^{2}-2\left(\displaystyle\frac{c}{a}\right)}{\left(\displaystyle\frac{c}{a}\right)^{2}}$, which simplifies to:

[b]D[/b]: $\frac{b^{2}-2ac}{c^{2}}$.[/hide]

[hide="heres another way"]
The equation:

\[a\left(\frac{1}{\sqrt{x}}\right)^2+b\left(\frac{1}{\sqrt{x}}\right)+c=0\]

has roots $\frac{1}{r^2}$ and $\frac{1}{s^2}$.  So let's just find the sum of the roots of this equation.  First multiply through by $x$:

\[a+b\sqrt{x}+cx=0.\]

Isolate $b\sqrt{x}$ and square:

\[b\sqrt{x}=-(a+cx)\Rightarrow b^2x=a^2+2acx+c^2x^2.\]

So then:

\[c^2x^2+(2ac-b^2)x+a^2=0\]

and it follows that:

\[\frac{1}{r^2}+\frac{1}{s^2}=\frac{b^2-2ac}{c^2}.\]

QED[/hide]

[quote="BornForMath"]yea, using transformation of the function is clever.
btw, what is QED?[/quote]I'm not sure exactly what it stands for, but I think it's used to signify that a proof or whatever is complete.

[quote="kunny"][quote="BornForMath"]yea, using transformation of the function is clever.
btw, what is QED?[/quote]

QED stands for [color=blue]Q[/color]uad [color=blue]E[/color]sta [color=blue]D[/color]emostrandom in Latin,
which can be translated in English, [b]which is to be proved[/b].[/quote]

Actually, it stands for "Quod Erat Demonstrandum."

Oh! yes, I am wrong. esta is for Spanish? Thank you. ;)


inequalities AMC USA(J)MO USAMO ARML function trigonometry

For those of you preparing for the USAMO, here's an inequality.

Given $x,y,z>0$, prove that:

$\frac {x}{(x+y)(x+z)}+\frac {y}{(y+x)(y+z)}+\frac{z}{(z+x)(z+y)}\leq \frac {9}{4(x+y+z)}$

My solution:

[hide]

As before, homogenize to get x+y+z = 1.  Get a common denominator.  Now:

last ineq is clearly true, its equivalent to the first, so the first is true, QED.

[/hide]

wow, this ineq was easy!

In your hint, I get the part up until applying Schur. I can't seem to get it to work that way. Would someone mind explaining that last bit?

However, simply expanding the whole thing out under a common denominator was the way I first did it and it seems to be very easy (as shown by Singular).

i dont get how you apply the homogenous rule of x+y+z = 1. isnt it just simple to multiply and factor some out and use the derivations of
$\displaystyle x^2 + y^2 + z^2 = (x+y+z)^2 - 2(xy+yz+zx)$?

oh never mind.....

i misread the $(x+y)(y+z)(z+x)$ part....

but i still dont get the aprt with x+y+z = 1 or how to apply Schur's.

xxreddevilzxx, I didn't use Schur so I don't know about that.  As for the x+y+z=1, assume x+y+z=k for some real k then there exist reals a, b, c such that x=ka, y=kb, and z=kc so the condition is equivalent to a+b+c=1.  So we can make this substitution since the degree is the same on both sides (the k factors out) and then proceed from there.  I hope this is enough.

P.S. Were you on the ARML Washinton A team last year?

I also don't see where to apply Schur here, but to be honest, I also tend to think that the function $\frac{1}{x}$ is convex and not concave (at least on $\mathbb{R}^{+}$), so I'm not sure whether Blahblahblah's hint is correct at all...

Anyway, here is how I would solve the problem:

[hide="Solution of the problem"]

We have to prove the inequality

$\frac{x}{\left(z+x\right)\left(x+y\right)}+\frac{y}{\left(x+y\right)\left(y+z\right)}+\frac{z}{\left(y+z\right)\left(z+x\right)}\leq\frac{9}{4\left(x+y+z\right)}$

for any positive reals x, y, z.

Let a = y + z, b = z + x and c = x + y. Then, since b + c = (z + x) + (x + y) = y + z + 2x > y + z = a, and similarly, c + a > b and a + b > c, the numbers a, b, c are the sides of a triangle. Let A, B and C be the corresponding angles and $s=\frac{a+b+c}{2}$ the semiperimeter of this triangle. Then,

$s=\frac{a+b+c}{2}=\frac{\left(y+z\right)+\left(z+x\right)+\left(x+y\right)}{2}=\frac{2\left(x+y+z\right)}{2}=x+y+z$,

and s - a = (x + y + z) - (y + z) = x, and similarly s - b = y and s - c = z. Thus, the inequality that we have to prove,

$\frac{x}{\left(z+x\right)\left(x+y\right)}+\frac{y}{\left(x+y\right)\left(y+z\right)}+\frac{z}{\left(y+z\right)\left(z+x\right)}\leq\frac{9}{4\left(x+y+z\right)}$,

becomes

$\frac{s-a}{bc}+\frac{s-b}{ca}+\frac{s-c}{ab}\leq\frac{9}{4s}$.

Multiply both sides of this inequality with s to get:

$\frac{s\left(s-a\right)}{bc}+\frac{s\left(s-b\right)}{ca}+\frac{s\left(s-c\right)}{ab}\leq\frac94$.

Upon multiplication with 2, this becomes:

$2\frac{s\left(s-a\right)}{bc}+2\frac{s\left(s-b\right)}{ca}+2\frac{s\left(s-c\right)}{ab}\leq\frac92$.

And upon subtraction of 3 this becomes

$2\frac{s\left(s-a\right)}{bc}+2\frac{s\left(s-b\right)}{ca}+2\frac{s\left(s-c\right)}{ab}-3\leq\frac92-3$,

what is equivalent to

$\left(2\frac{s\left(s-a\right)}{bc}-1\right)+\left(2\frac{s\left(s-b\right)}{ca}-1\right)+\left(2\frac{s\left(s-c\right)}{ab}-1\right)\leq\frac32$.

But after the half-angle formulas for the angles of triangle ABC, we have

$\cos^2\frac{A}{2}=\frac{s\left(s-a\right)}{bc}$.

Thus,

$\cos A=\cos\left(2\frac{A}{2}\right)=2\cos^2\frac{A}{2}-1=2\frac{s\left(s-a\right)}{bc}-1$.

Similarly,

$\cos B=2\frac{s\left(s-b\right)}{ca}-1$;
$\cos C=2\frac{s\left(s-c\right)}{ab}-1$.

Thus, the inequality in question becomes

$\cos A+\cos B+\cos C\leq\frac32$.

But this is a well-known inequality (see, for instance, http://www.mathlinks.ro/Forum/viewtopic.php?t=21188 ). This completes the proof of the initial inequality.[/hide]

[b]EDIT:[/b] As I see, this inequality has also been proven in http://www.mathlinks.ro/Forum/viewtopic.php?t=4908 . I have a bad memory!

  Darij

[quote="DPopov"]The function is convex, $f''(x)=\frac{2}{x^3}$ and $f''(x)>0$ for all $x>0$[/quote]

*sigh* duh... no wonder when i tried to do it after applying Jensen's everything was backwards :blush:

[quote="DPopov"]Too bad I'm not familiar with Jensen's :([/quote]

[url=http://mathworld.wolfram.com/JensensInequality.html]Here[/url] you can find it. Basically it says that if you have a continuous concave function in $[a,b]$, and $x_1,\dots,x_n$ are points in that interval, $t_i>0,\ t_1+\cdots+t_n=1$, then

\[\sum_{i=1}^{n}t_if(x_i)\leq f\left(\sum_{i=1}^{n}t_ix_i\right)\]

If the function is convex, then the inequality goes in the other direction

\[\sum_{i=1}^{n}t_if(x_i)\geq f\left(\sum_{i=1}^{n}t_ix_i\right)\]

I have seen some books that call it "The Mother of all Inequalities" (Specially some Math Olympiad Books) because most of the inequalities that you use on Olympiads are particular cases of the Jensen's Inequality (Included GM-AM and many others).

Best,

could someone explian or point me to schurs inequality?

Schur:

$a^k(a-b)(a-c)+b^k(b-c)(b-a)+c^k(c-a)(c-a) \ge 0$

for $a,b,c$ nonnegative reals and $k>0$.

Couldn't find it on Mathworld, interestingly enough.

[quote="mna851"]I still don't understand how you can assume that x+y+z=1.  Does that mean if an inequality is homogenous of degree 2 you can say x^2 + y^2 + z^2=2[/quote]

So assume x+y+z=k instead. By scaling each variable down to x'=x/k, y'=y/k, z'=z/k, we see that x',y', and z' still satisfy the inequality (by canceling out all the k's) and x'+y'+z'=1.

Another way is by proving it for x+y+z=1, we can multiply the whole thing by k/k^2 to get x+y+z=k for any k.

lollerskates.  I think that using Jensen's in the wrong direction has to be the most common mistake in inequalities.  Anyways, it holds easily by Muirhead's, although all such solutions are inevitably very unsatisfying.

We have to prove that
$\frac{2(xy+xz+yz)}{(x+y)(x+z)(y+z)}\leq \frac{9}{4(x+y+z)}$

or $(x+y)(x+z)(y+z)\geq \frac{8(xy+xz+yz)(x+y+z)}{9}$
It is easy
$(x+y)(x+z)(y+z)= (x+y+z)(xy+xz+yz)-xyz\geq (x+y+z)(xy+xz+yz)-\frac{(x+y+z)(xy+xz+yz)}{9}=\frac{8(xy+xz+yz)(x+y+z)}{9}$

[hide="brute force w/o muirhead"]
We have:
$\sum_{cyc}\frac{x}{(x+y)(x+z)}\leq \frac{9}{4(x+y+z)}$
$\sum_{cyc}4x(y+z)(x+y+z)\leq \sum_{cyc}3(x+y)(x+z)(y+z)$
$\sum_{cyc}4x^{2}y+4xy^{2}+4xyz+4x^{2}z+4xyz+4xz^{2}\leq $$\sum_{cyc}3x^{2}y+3x^{2}z+3xyz+3xz^{2}+3xy^{2}+3xyz+3y^{2}z+3yz^{2}$

$6xyz\leq \sum_{sym}x^{2}y$ Which follows from $\text{AM-GM}$.
[/hide]


Inside triangle $ ABC$, point $ P$ is taken. The lines that pass through $ P$ and vertices
of the triangle intersect the sides at points $ A_1$, $ B_1$ and $ C_1$. Prove that the area of the triangle
determined by the midpoints of segments $ AA_1$, $ BB_1$ and $ CC_1$ is equal to $ 1/4$ of the area of
triangle $ A_1B_1C_1$.  :wink:  :huh:

A2C’=A2’B’    B’C2’=C2A’    A’B2=B2’C’
Denote A’B2=a  A’C2=b   C2B’=c   B’A2=d   A2C’= e  C’B2=f
S(⊿A’B2C2)+S(⊿C2B’A2)+S(⊿A2C’B2)=ab*sinA + cd*sinB + ef*sinC （1）
S(⊿A’B2’C2’)+S(⊿C2’B’A2’)+S(⊿A2’C’B2’)=cf*sinA + be*sinB + ad*sinC （2）
Notice sinA=(e+d)/2R  sinB=(a+f)/2R  sinC=(d+e)/2R  （3）
(1)=abd + abe + acd + cdf + ebf + efc
(2)=abd + adc + aeb + ebf + fcd +efc
So (1)=(2)
Thus we have S(⊿A2B2C2)=S(⊿A2’B2’C2’)=1/4S(⊿A1B1C1)

Let $ M, N$ and $ P$ the midpoint of sides $ [BC], [CA]$ and $ [AB]$, respectively; and let $ G$ the centroid of $ \triangle {ABC}\Rightarrow \{G\} \equal{} AA_1\cap BB_1 \cap CC_1.$
Denote
$ \{A_0\} \equal{} AA_1\cap PN; \ \{A_2\} \equal{} A_1G\cap PN; \ \{B_0\} \equal{} BB_1\cap PM; \\
\{B_2\} \equal{} B_1G\cap PM; \ \{C_0\} \equal{} CC_1\cap MN; \ \{C_2\} \equal{} C_1G\cap MN.$
[b]1).[/b] Have:  $ |A_0P| \equal{} |A_2N|; |B_0M| \equal{} |B_2P|; |C_0N| \equal{} |C_2M|\Rightarrow$
$ \Rightarrow area (\triangle{A_0B_0C_0}) \equal{} area(\triangle{A_2B_2C_2}). \ \ (1)$
[b]2). [/b]The $ \triangle{A_2B_2C_2}$ and $ \triangle{A_1B_1C_1}$ is inversly homotetic; the homotetic center is $ G$ and the homotetic ratio is $ \frac {1}{2}\Rightarrow$
$ \Rightarrow area(\triangle{A_2B_2C_2}) \equal{} \frac {1}{4}.area(\triangle{A_1B_1C_1}). \ \ (2).$
[b]3).[/b] $ (1);(2)\Rightarrow area(\triangle{A_0B_0C_0}) \equal{} \frac {1}{4}.area(\triangle{A_1B_1C_1}).$


[b]If $ (x,y)$ is a solution for the system of equations below, find the maximum value of $ x^{2}\plus{}y^{2}$.

$ 2x^{2}\plus{}5xy\plus{}3y^{2}\equal{}2$
$ 6x^{2}\plus{}8xy\plus{}4y^{2}\equal{}3$
[/b]

[hide="solution"]
Multiplying the first equation by -3 and the second by 2 and then adding them we obtain
$ 6x^{2}\plus{}xy\minus{}y^{2}\equal{}0$
Divide the last equation by $ y^{2},\ (y\neq 0)$ and note $ \frac{x}{y}\equal{}t$:
$ 6t^{2}\plus{}t\minus{}1\equal{}0\Rightarrow t_{1}\equal{}\minus{}\frac{1}{2},t_{2}\equal{}\frac{1}{3}$
If $ \frac{x}{y}\equal{}\minus{}\frac{1}{2}$ then $  x^{2}\equal{}\frac{1}{2},y^{2}\equal{}2\Rightarrow x^{2}\plus{}y^{2}\equal{}\frac{5}{2}$
If $ \frac{x}{y}\equal{}\frac{1}{3}$ then $  x^{2}\equal{}\frac{1}{27},y^{2}\equal{}\frac{1}{3}\Rightarrow x^{2}\plus{}y^{2}\equal{}\frac{10}{27}$
So the maximum of $ x^{2}\plus{}y^{2}$ is $ \frac{5}{2}$
[/hide]

OK for the solution and for the results but this :
[quote="red_dog"] If $ \frac{x}{y}\equal{}\frac{1}{3}$ then $ x^{2}\equal{}\frac{1}{27},y^{2}\equal{}\frac{1}{3}$[/quote]
is wrong.

Fortunately, this does not change the result.

\[\begin{array}{l}
\left. \begin{array}{l}
2{r^2}{\cos ^2}\theta  + 5{r^2}\sin \theta \cos \theta  + 3{r^2}{\sin ^2}\theta  = 2\\
6{r^2}{\cos ^2}\theta  + 8{r^2}\sin \theta \cos \theta  + 4{r^2}{\sin ^2}\theta  = 3
\end{array} \right\}\mathop  \Rightarrow \limits^{(II) \div (I)} \frac{{6{{\cos }^2}\theta  + \sin \theta \cos \theta  + {{\sin }^2}\theta }}{{2{{\cos }^2}\theta  + 5\sin \theta \cos \theta  + 3{{\sin }^2}\theta }} = \frac{3}{2}\\
 \Rightarrow \sin \theta  =  \cdots ,\cos \theta  =  \cdots  \Rightarrow r =  \cdots  \Rightarrow {x^2} + {y^2} = {r^2} =  \cdots
\end{array}\]


why is genetic polymorphism important to evolution?
1.individual variability provides the raw material for natural selection to act on
2.genes cant mutate unless they are polymorphic
3.only heterozygous individuals are selected in natural populations
4. the hardy weinberg equilibrium is less likely to be disturbed in polymorphic population
5. none of the above; genetic polymorphism is not important to evolution

in a population of wildflowers, the frequency of the alle for the red flowers was 0.8 what was the frequency of the white allele the only other allele for flower color?

it is .2?

refer to the question above what is the frequency of homozygous white flower plants in the population?
1.     .04
2.     .16
3.     .32
4.     .48
5.     .64

refer to the question above what is the frequency of the plants in the population that are heterozygous for flower color?
1.     .04
2.     .16
3.     .32
4.     .48
5.     .64

a virus killed most of the seals in the north sea eg. dropped the population from 8000 to 800. in an effort to help preserve the species scientists caught 20 seals and used them to start a new population in the northwest pacific ocean. what of the following factors would most likely have the least impact in this new population?
1. founder principle
2. random mating
3.genetic drift
4.bottleneck effect

does inbreeding occur in plants?

an individual of which of the following species is likely to have the highest level of heterozygous genes?
1. fish
2.land snail
3. self pollinating plant
4. bird
5. mammal

a scientist measures the circumference of acorns in a population of oka trees and discovers that the most common circumference is 2 cm. what would you expect the most commom circumference to be after 10 generation of stabilizing selection?
1. 2cm

refer to the question above, but this time answer what you expect after 10 genertation of disruptive selection.
3. greater than 2 cm and less than 2 cm

refer to the question above, but this time answer what you expect after 10 genertation of directional selection.
2. greater than 2 cm or less than 2 cm

what is the ultimate source of genetic variability?
1. mutation

sry can't help u on the last one

If u look at the graphs of stabilzing, disruptive, and directional selections u will understand...

Fade, genetic polymorphism is one of the most important aspects of evolution. This is the reason:

Mutations produce individual genetic variation (aka, polymorphism.) Polymorphism in a population means a variety of alleles and nucleotide sequences for a certain gene. These differences provide a basis for natural selection to work. For example, the genes that control eye color are polymorphic among members of [i]Homo sapiens[/i].


Prove that the sides a,b,c of any triangle suck that $ a \plus{} b \plus{} c \equal{} 3$   satisfy the inequality
i/$ \sum\frac {a}{b\plus{}c^2}>\equal{}\frac{3}{2}$

[quote="tranquoc"]Prove that the sides a,b,c of any triangle suck that $ a \plus{} b \plus{} c \equal{} 3$   satisfy the inequality
i/$ \sum\frac {a}{b \plus{} c^2} > \equal{} \frac {3}{2}$[/quote]

It is true with $ a,b,c$ are nonegative real numbers such that $ a\plus{}b\plus{}c\equal{}3$.


Let be $ a,b,c$ the side-lenghts of an triangle. Prove that the follow inequality holds: \[ 4(a^5\plus{}b^5\plus{}c^5)>abc(a\plus{}b\plus{}c)^2\][b]
Claudiu Mindrila[/b]

It is easily killed by rearrangement theorem as shown
$ 3\left( a^5\plus{}b^5\plus{}c^5 \right) \geq \left(a^2\plus{}b^2\plus{}c^2 \right)\left(a^3\plus{}b^3\plus{}c^3 \right).$
I wonder whether there would be a nice proof for this problem using the condition the a, b, c be lengths of the triangle.
How about your idea, Mîndrilă Claudiu?

We know that $ \frac{a}{b\plus{}c}\plus{}\frac{b}{c\plus{}a}\plus{}\frac{c}{a\plus{}b}<2$ . Use that and the rearrangement  :) .

$ f(a,b,c) \equal{} 4 (a^5 \plus{} b^5 \plus{} c^5) \minus{} a b c (a \plus{} b \plus{} c)^2$.

$ f(a, b, c) \minus{} f(a, \frac {b \plus{} c}{2},\frac {b \plus{} c}{2})$
$ \equal{} \frac {1}{4} (b \minus{} c)^2 (a^3 \plus{} 2 a^2 b \plus{} a b^2 \plus{} 15 b^3 \plus{} 2 a^2 c \plus{} 2 a b c \plus{} 25 b^2 c \plus{} a c^2 \plus{} 25 b c^2 \plus{} 15 c^3)$.

So WLOG $ a \plus{} b \plus{} c \equal{} 3$, $ b \equal{} c \equal{} x$, $ a \equal{} 3 \minus{} 2x$. WLOG $ a\le b\le c$ so $ 3 \minus{} 2x\le x\implies x\ge 1$. $ a\ge 0\implies x\le\frac {3}{2}$.

So it suffices to check $ f(3 \minus{} 2x,x,x) > 0$ for $ x\in [1,\frac {3}{2}]$.

$ f(3 \minus{} 2x,x,x) \equal{} 3 \plus{} (x \minus{} 1)^2(323 \minus{} 434x \plus{} 240x^2 \minus{} 40x^3)$ which is an easy enough computation. The second factor is greater than 72.


A $ 3''\times5''$ photo is enlarged proportionally such that its smaller dimension is now $ 1'3''$. How many inches are in the larger dimension?

Since it is proportional, we divide to get the proportionality constant, then multiply through to get the other dimension.
                              $ \frac{15''}{3''}\equal{}5$
Now, multiply $ 5$ by the other dimension.
                              $ 5''\times5\equal{}\boxed{25''}$


my teacher says that atoms have a full valence of 8 electrons and i disagreed because i know the valences go
2, 8, 8, 18, 18, 32, 32 but then she coutners by saying something about sub levels which i do not believe so can someone please clear up the situation on valence electrons  :)

the last shell of an atom always has 8 electrons .this is called the octet rule


MATHCOUNTS
blogs
probability
geometry
3D geometry

1) NO SIGNING UP REQUIRED. This tournament(more like test) is open to everyone. i just made that other thread to see if anyone would be interested.

2) PM me the answers. no solutions required.

3) No rescources, calculators, ect. Only pencil and paper.

4) All of these problems can be solved using mathcounts techniques.

5) Each part of the test is due 1 week after it is posted, Not necisarily when i post the next set of problems.

Combinatorics problems will be posted on my blog in a few moments...

At the end, i will make a word document of the problems

why did you revive that topic? you don't have to post another thread on the same thing.

and when are the problems gonna be posted?

EDIT:
I have a feeling some people dont know the problems are on my blog, so now they will be right here:

Combinatorics
1.	Calculate $ 0*\binom{10} {0} \plus{} 1*\binom{10} {1} \plus{} 2*\binom{10} {2}...10*\binom{10} {10}$.
2.	There are 20 candies and 7 kids. One kid will envy another if his/her amount of candies is 3 or more less than the other. For example, a kid with 2 candies will envy another kid with 5 candies, but not a kid with 4 candies. How many envy-free ways can we distribute the candies?
3.	How many 8 digit integers with distinct digits in decreasing order when read from left to right are multiples of 3?
4.	We fill a jar with marbles such that probability of drawing a blue marble from the jar is $ \frac {1} {3}$, and the probability of drawing 2 blue marbles(without replacement) from the jar is $ \frac {1} {11}$. We draw 3 marbles from this jar. Given that a blue marble is drawn, find the probability that all 3 marbles are blue.
5.	On a circle circular track radius 100 meters, 3 people stand on the track. What is the probability that each person can run $ 50\pi$ meters along the track in either direction and not run into someone else?

Due date is extended to next sunday

For number 5, are do you mean that "each pair of people are at least $ 50\pi$ meters away from each other" or like "it's impossible for them to run in to each other" or "it's possible for them to run in a fashion such that no two meet" or something I was too stupid to think of :P ?

Im not sure what you are asking. If the wording is confusing, this is the same question worded differently:
What is the probability that for any person to run to another along the track, he/she must run atleast $ 50\pi$ meters.

Combinatorics problems are not due yet.(sunday is the due date)

Number thoery

1. How many positive integers less than 1000 cannot be expressed as the sum of 2 cubes?
2. How many positive integer solutions $ (a,b,c,d)$ are there to $ a^42 \plus{} b^6 \plus{} c^2 \plus{} d \equal{} 1337$?
3. Let $ N$ be the largest positive integer with the following property: reading from left to right, each pair of consecutive digits of $ N$ forms a perfect square. What are the leftmost three digits of $ N$?
4. How many integers less than $ 10^6$ are perfect square multiples of 24?
5. How many factors does $ 111,111,111,111$ have?

Remember, no calculators. These problems are due Tuesday.

I think he means that all candies must be given and if the number of candies given to each kid is $ \{a_1,a_2,a_3,a_4,a_5,a_6,a_7\}\equal{}A$, then $ \max{A}\minus{}\min{A}\leq2$. This notation is probably incorrect, but I hope you know what I mean. :P

[quote="Bachukas"]#1. What does envy-free mean? Can some candies don't be given to kids? for example 2,2,2,2,2,2,2 are given and another 6 candies are not given.[/quote]

All the candies must be given

[quote="abacadaea"]2. How many positive integer solutions $ (a,b,c,d)$ are there to $ a^42 \plus{} b^6 \plus{} c^2 \plus{} d \equal{} 1337$? [/quote]

I think you mean $ a^{42} \plus{} b^6 \plus{} c^2 \plus{} d \equal{} 1337$.

EDIT: Where have I seen #3 before... hmm...

For #5 on the NT one, do I seriously have to check for primes under a <large> four digit number?

I HAVE SENT MY ANSWERS IN.

If you have done the test:
Ok, I'm sorry if this is against the rules or anything, but is there a simple, applicable, practical primality test for a big number, oh [hide] that big number just below 10000 perhaps?[/hide]

I'm getting off topic with this subject; can someone who finished pm me?

lol. i guess i can answer that. the answer is yes.

I guess this could be considered a failure. only 3 people have submitted answers, but ill just keepn posting problems until we get through all 25

[quote="abacadaea"] 1. How many positive integers less than 1000 cannot be expressed as the sum of 2 cubes? [/quote]

Cannot be expressed as the sum of 2 [b]positive integer[/b] cubes, or cannot be expressed as the sum of 2 [b]integer[/b] cubes?

[quote="shentang"]if it was integer, you would get the same answer if it was positive integer.[/quote]

I don't think so.

19 can be expressed as $ (\minus{}2)^3\plus{}3^3$, but it can't be expressed as a sum of two positive integer cubes.

hmmm good point, hadn't thought about that  :oops:

I would totally do this if it was during the summer.  :(


Hello
[hide="hint"]
As the eq. of the an arbitrary circle is $ x^2\plus{}y^2\plus{}2gx\plus{}2fy\plus{}c\equal{}0$
put the three points on the eq. so that u will get the value of g,f,c.
radius of circle=$ \sqrt{g^2\plus{}f^2 \minus{}c}$
Now find the area by its radius.
[/hide]
Thank u.

[quote="brianb"]The points (18,0), (0,0) and (0,80) lie on a circle in teh coordinate plane. Find its area in terms of pi.

This is to be done without a calculator. Thanks in advance![/quote]

[hide="Hint 1"]
Draw the triangle formed by the three points. What type of triangle is it?
[hide="Hint 2"]
It's a right triangle. What is special about the circumradius of a right triangle?
[/hide]
[/hide]


Prove that $ \sqrt{a^{2}\plus{}b^{2}\plus{}c^{2}}\le |a|\plus{}|b|\plus{}|c|$ for a,b,c real

(lal+lbl+lcl)^2=a^2+b^2+c^2+2labl+2lacl+2lbcl>=a^2+b^2+c^2

Since both a^2+b^2+c^2 and lal+lbl+lcl are both positive taking the square root of both sides of the above equation we get the desired result.

If this is hard to read, sorry, I'm in the process of getting Latex.

[hide]Consider the distance in Euclidean 3-space from the origin to $ (a,b,c)$ along the following two paths:

1. A straight line -- length is $ \sqrt {a^2 \plus{} b^2 \plus{} c^2}$

2. The path $ O \to (a,0,0) \to (a,b,0) \to (a,b,c)$ -- length is $ |a| \plus{} |b| \plus{} |c|$

The shortest distance between two points is via a direct line segment.[/hide]


Find all positive integers (a,b), so that a-b is a prime, and ab is a perfect sqaure

[hide="What's wrong with my logic?"]
1. $a$ and $b$ cannot be perfect squares or $a-b$ would be factorable as a difference of squares.
2. $a$ and $b$ cannot share any factors, or $a-b$ would be factorable by that shared factor.
3. Since $ab$ is a perfect square, either both $a$ and $b$ are perfect square (invalidating 1) or $a$ and $b$ share one or more factors which are odd powers in both. However, that would invalidate 2, as $a$ and $b$ are relatively prime.[/hide]

[quote="worthawholebean"][hide="What's wrong with my logic"]
1. $a$ and $b$ cannot be perfect squares or $a-b$ would be factorable as a difference of squares.
2. $a$ and $b$ cannot share any factors, or $a-b$ would be factorable by that shared factor.
3. Since $ab$ is a perfect square, either both $a$ and $b$ are perfect square (invalidating 1) or $a$ and $b$ share one or more factors which are odd powers in both. However, that would invalidate 2, as $a$ and $b$ are relatively prime.[/hide][/quote]Perhaps prove your statements first. Counterexample to statement #1: Let $a=4$, $b=1$. $4-1=3$ is prime and $4\cdot1=4$ is a perfect square, both $a,b$ are also perfect squares...

[quote]Perhaps prove your statements first. Counterexample to statement #1: Let $a=4$, $b=1$. $4-1=3$ is prime and $4\cdot1=4$ is a perfect square, both $a,b$ are also perfect squares...[/quote]This exception occurs when one of the factors of $a-b$ is 1, which only occurs when $\sqrt{a}$ and $\sqrt{b}$ are consecutive integers.  As for $a-b$ being prime, this occurs infinitely many times, as the difference of two consecutive perfect squares can take on any odd number.

A given odd prime, $p$ can be rewritten as $2k+1$.  The two squares whose difference is $p$ are $(k+1)^{2}$ and $k^{2}$.  The difference is $p$, and their product is the square of $k(k+1)$.

I think that worthawholebean's second point is valid, so those are the only solutions.

wait... aren't there infinitely many solutions?

[hide="because"]worthawholebean's second point is valid. Therefore, a is a perfect square, and b is also a perfect square relatively prime to a. But a and b cant be of the same parity. So one is odd, and one is even.

Let's say 1 and 4. that's good. 4 and 9. that's good. 9 and 16. that's good. 25 and 36. that's good. so on. Those squares differ by primes, and there are infinitely many of them![/hide]

[quote="1=2"]wait... aren't there infinitely many solutions?[/quote]Yes, there are certainly infinitely many solutions, as long as $2k+1=p$ is prime and we know there are an infinite number of odd primes.

[quote="renatzu"][quote="Cartman"]Yes there are infinite many solutions, but can someone find some way to calculate a and b?[/quote]Already did.

If $2k+1 = p$ (prime), then $a$ and $b$ are $k^{2}$ and $(k+1)^{2}$[/quote]
Oh... sorry. Of some reason i missed that


pigeonhole principle
algebra
system of equations

1. Find all pairs of positive integers $(x,y)$ which satisfy the  equation: $x^{3}-y^{3}= xy+61.$

2. Find all integer solutions to the equation: $xy+3x-5y=-3.$

3. Find all solutions $(x,y,z,t)$ that satisfy: $x!+y!+z!=t!$

4. Find all positive integers $(x,y)$ that satisfy: $\sqrt{x}+\sqrt{y}=\sqrt{2001}$

5. Let $x,y,z,a,b,c$ be integers such that

$x^{2}+y^{2}=a^{2}$
$x^{2}+z^{2}=b^{2}$
$y^{2}+z^{2}=c^{2}$

Prove that the number $xyz$ is divisible by 55.

Has anyone got any equations or systems of equations that they found the solution to be interesting?

[quote="FieryHydra"]Please post each problem separately. It becomes difficult to post solutions and keep track of them if more than one problem are posted all together.[/quote]

Sorry about that. :blush:

[quote="matt276eagles"][hide="1"]$(x-y)(x^{2}+xy+y^{2})=xy+61$
$(x-y)((x-y)^{2}+3xy)=xy+61$
$(x-y)^{3}+3xy(x-y)=xy+61$
$3xy(x-y)-xy=61-(x-y)^{3}$
$xy(3(x-y)-1)=61-(x-y)^{3}$
$xy=\frac{61-(x-y)^{3}}{3(x-y)-1}$

Since $x$ and $y$ are positive, the numerator and denominator are either both positive or both negative.  If $x-y$ is not positive, then the denominator is negative but the numerator is positive.  Therefore, $x-y$ is positive.  But if $x-y$ is greater than $3$, then the numerator is negative while the denominator is positive.  Testing $x-y=1,2,3$, we find that $xy$ is only an integer when $x-y=1$.  Therefore, $x-y=1$, and $xy=30$.  The only solution is $(6,5)$.[/hide]

Nice problem!  :)[/quote]
We may also argue by looking at the original equation that $x>y$ since $x^{3}-y^{3}= xy+61>0$ and $x,y$ are both positive.

Now looking at $xy=\frac{61-(x-y)^{3}}{3(x-y)-1},$ we note that $3(x-y)-1 > 0$ and so $61-{(x-y)}^{3}$ must be positive. So, we only have the following possibilities for the values of $(x-y): 1,2,3.$

After this, we proceed the way [b]matt276eagles [/b]mentioned in his solution above.

[hide] 1. Let $d=x-y$ then substitute $x=d+y$ into the equation to obtain $(3d-1)y^{2}+(3d^{2}-d)y+d^{3}=61$.

Therefore, $d^{3}\leqslant 61$ or $d \leqslant 3$. So, $d=1, d=2$ or $d=3$ and by substituting these values into the equation above, we can safely conclude that the only solution in positive integers that exists is $(x,y)=(6,5)$.
$QED$.
 [/hide]

I did these a while ago so I might have made some minor mistakes :) . If you find these hard, try doing number 4 (which is really easy).

Oops, I was a bit slow.

[quote="Franz Joseph"]
2. Find all integer solutions to the equation: $xy+3x-5y=-3.$
[/quote]
$xy+3x-5y=-3$
$\Rightarrow (5-x)(y+3)=2\cdot3^{2}$

After this, it's just a matter of evaluating individual cases, such as $5-x=1, y+3=18,$ and so on.

[hide="#2"]
$xy+3x-5y=-3$
$(x-5)(y+3)=-18$
the solutions are $(6,-21), (4,15), (-13,-2), (23,-4)$,etc..
wow alot of them....did i make a mistake?? :maybe: [/hide]
FieryHydra, u beat me 3 min..

[hide]2. By rearranging the equation, we obtain

$y= \frac{3-3x}{x-5}=\frac{15-3x-18}{x-5}=-3-\frac{18}{x-5}$

We now observe that $x-5$ must be a factor of $18$ so in total we should have $12$ solutions all together.

(Since $x-5= \pm 1, \pm 2, \pm 3, \pm 6, \pm 9, \pm18$).

$QED$. [/hide]

[hide="#4"]$\sqrt{y}=\sqrt{2001}-\sqrt{x}\&\implies\& y=2001-2\sqrt{2001x}+x$

Since $x$ is natural, $\sqrt{2001x}$ can be either natural or irrational, but as $y$ is natural, it must be natural. Hence $2001x$ must be a perfect square, but since $2001=3\cdot 23\cdot 29$, we obtain $x=2001a^{2}$ where $a$ is some natural number.

In the same manner we find $y=2001b^{2}$.

Substituting those into the given equation, we get $a+b=1$, which has no solution in positive integers. (It DOES have a solution in non-negative integers - $(0,1),(1,0)$ - which would give $(x,y)\in\{(0,2001),(2001,0)\}$)[/hide]

[hide="3"]PS: Nevermind, I found a solution: $(2,2,2,3)$[/hide]My solution was faulty, still finding a proof :oops:

[quote="10000th User"][hide="3"]This reduces to $1+(y-x)!+(z-x)!=(t-x)!$. For integers $m>1$, $m!$ is always even. If $t-x>1$, RHS is even; but, LHS is odd. So, $t-x\le1$ and $(t-x)!=1$. But, $(y-x)!\ge1$ and $(z-x)!\ge1$ and so $1=(t-x)!=1+(y-x)!+(z-x)!\ge3$, which is impossible. Therefore, no solution.

PS: Nevermind, I found a solution: $(2,2,2,3)$
[/hide][/quote]

It does have a solution.

[hide]3. We can safely assume that $x \leqslant y \leqslant z \leqslant t$. Since $z!<t! \Rightarrow (z+1)z! \leqslant t!$.

Thus, $x!+y!+z!=t! \leqslant 3z! \Rightarrow (z+1)z! \leqslant 3z! \Rightarrow z \leqslant 2$.

Therefore, by inspection we conclude that the only solution is $(x,y,z,t)= (2,2,2,3)$.

$QED$.[/hide]

[quote="D.P.L"]What is RHS and LHS? :blush:[/quote]

 I think it mean Left Hand Side and Right Hand Side.

[quote="Franz Joseph"]5. Let $x,y,z,a,b,c$ be integers such that

$x^{2}+y^{2}=a^{2}$
$x^{2}+z^{2}=b^{2}$
$y^{2}+z^{2}=c^{2}$

Prove that the number $xyz$ is divisible by 55.[/quote]

Quite boring...does anyone have another solution?
[hide="#5"]For the divisibility by 5, it's easy. Suppose it isn't divisible by 5, then we would have that $x^{2}, y^{2}, z^{2}\equiv 1, 4\mod{5}$, so the pigeonhole principle would say that two of them are congruent modulo 5, say $x^{2}$ and $y^{2}$. But then $a^{2}\equiv x^{2}+y^{2}\equiv 2, 3\mod{5}$, which is impossible.

To prove $xyz$ is divisible by 11, it's A LOT of case-working. First remark is that $m^{2}\equiv 0, 1, 3, 4, 5, 9\mod{11}$, for all integers $m$. Second remark is that $x^{2}\not\equiv y^{2}\not\equiv z^{2}\not\equiv x^{2}\mod{11}$, because otherwise there would be one of $a^{2}, b^{2}$ and $c^{2}$ that is congruent to $2\left(0, 1, 3, 4, 5, 9\right) \equiv 0, 2, 6, 8, 10, 7 \mod{11}$, which is impossible, unless those numbers are both congruent to 0 modulo 11, which would be "Jackpot!". And now, we go case-working.

1. Suppose one of $x^{2}, y^{2}, z^{2}$ is congruent to 1 modulo 11, say $x^{2}$, then we would have that $a^{2}, b^{2}\equiv 0, 1, 3, 4, 5, 9\mod{11}$, so $y^{2}, z^{2}\equiv a^{2}-x^{2}, b^{2}-x^{2}\equiv 10, 0, 2, 3, 4, 8\mod{11}$. Only 0, 3 and 4 are possible. If $y^{2}$ or $z^{2}$ is congruent to 0 modulo 11, we're done, so suppose it isn't. Then $\left(y^{2}, z^{2}\right)$ would be a permutation of $(3, 4)$ modulo 11, because $y^{2}\not\equiv z^{2}\mod{11}$. But then $c^{2}\equiv y^{2}+z^{2}\equiv 7\mod{11}$, which is impossible. So $x^{2}, y^{2}, z^{2}\not\equiv 1\mod{11}$.

2. Suppose one of $x^{2}, y^{2}, z^{2}$ is congruent to 3 modulo 11, say $x^{2}$, then we would have that $a^{2}, b^{2}\equiv 0, 1, 3, 4, 5, 9\mod{11}$, so $y^{2}, z^{2}\equiv a^{2}-x^{2}, b^{2}-x^{2}\equiv 8, 9, 0, 1, 2, 6\mod{11}$. Only 0, 1 and 9 are possible. If $y^{2}$ or $z^{2}$ is congruent to 0 modulo 11, we're done, so suppose it isn't. Then $\left(y^{2}, z^{2}\right)$ would be a permutation of $(1, 9)$ modulo 11, because $y^{2}\not\equiv z^{2}\mod{11}$. But we've just proven that $y^{2}, z^{2}\not\equiv 1\mod{11}$, so that's impossible. So $x^{2}, y^{2}, z^{2}\not\equiv 3\mod{11}$.

3. Suppose one of $x^{2}, y^{2}, z^{2}$ is congruent to 4 modulo 11, say $x^{2}$, then we would have that $a^{2}, b^{2}\equiv 0, 1, 3, 4, 5, 9\mod{11}$, so $y^{2}, z^{2}\equiv a^{2}-x^{2}, b^{2}-x^{2}\equiv 7, 8, 10, 0, 1, 5\mod{11}$. Only 0, 1 and 5 are possible. If $y^{2}$ or $z^{2}$ is congruent to 0 modulo 11, we're done, so suppose it isn't. Then $\left(y^{2}, z^{2}\right)$ would be a permutation of $(1, 5)$ modulo 11, because $y^{2}\not\equiv z^{2}\mod{11}$. But we've just proven that $y^{2}, z^{2}\not\equiv 1\mod{11}$, so that's impossible. So $x^{2}, y^{2}, z^{2}\not\equiv 4\mod{11}$.

4. Suppose one of $x^{2}, y^{2}, z^{2}$ is congruent to 0 modulo 11; we're done. So suppose there isn't one. Then $x^{2}, y^{2}, z^{2}\equiv 5, 9\mod{11}$. Once again, thanks to the pigeonhole principle, there would be two of the numbers $x^{2}, y^{2}, z^{2}$ which would be congruent modulo 11, but we proved that this is impossible, so we're done.

[/hide]

[quote="Franz Joseph"]Has anyone got any equations or systems of equations that they found the solution to be interesting?[/quote]

I like the [url=http://www.mathlinks.ro/Forum/viewtopic.php?p=445334#p445334]system of equations of Canada 1996[/url]...


function
integration
limit
real analysis
real analysis unsolved

You can cast your vote on this either this product is ugly or beautiful but the product is fun:

Evaluate   \pi (j 2 /(j 2 +1)) from j=1 to  \infty , where  \pi is the product symbol as  \sum is the summation symbol

Query: Is this related to Riemann-Zeta function? Try it and find out!

Edit: Hey you are right I put wrong symbol, now it is correct :D

Am I missing something obvious but it seems to me that the sum is +oo ??

[quote="3X.lich"]or how about this?

Does the  \sum (j / (j 2 +1)) converge? If so evaluate it.[/quote]

Yes it converges,  but in IR U +oo :D

j/^2+1 = 1/j + 1/^2+1 and  \sum 1/j = +oo (harmonic sum)

you mean this?

(j/(j 2 +1)) = 1/j - 1/(j(j 2 +1))

because it's not quite harmonic  :(

[quote="3X.lich"]
Does the  \sum (j / (j 2 +1)) converge? If so evaluate it.[/quote]

It is divergent since j/(j^2+1) ~ 1/j when j-->+oo
 \sum (j / (j 2 +1)) has the same nature of  \sum 1/j wich
is divergent numerical serie.

[quote="3X.lich"]Sorry for the confusion, what i meant is the following

 \pi (j 2 /(j 2 +1)) = (1 2 /(1 2 +1))(2 2 /(2 2 +1))...[/quote]

p(n)=  \pi _(j=1 to n) j^2/(j^2+1)

lnp(n) =  \sum _(j=1 to n) ln (j^2/(j^2+1))
= - \sum _(j=1 to n) ln((j^2+1)/j^2)
= -  \sum _(j=1 to n) ln(1+ 1/j^2)

when j-->+oo, ln(1+1/j^2) ~ 1/j^2 so
-  \sum _(j=1 to n) ln(1+ 1/j^2)  has the same nature of --  \sum _(j=1 to n) 1/j^2 wich is convergent
p(n) is convergent

I have something to add here, for those in college, many students are familiar with the 'integral convergence test'. It's kind of overly used and way off from elementary but it helps to do a quick check for convergence in this problem.

Let f(x)=x/(x 2 +1). Clearly this function is positive definite for x>0 and strictly decreasing since

df/dx = (1 - x 2 )/(1 + x 2 ) 2  \leq 0 for all x \geq 1.

Now convergence of  \int  f(x) dx <==> convergence of  \sum f(n)

But  \int {0--> \infty } f(x) dx = (1/2) \lim log (1+x 2 ) -->  \infty , the original sum is divergent.

PS: Has anyone gotten a value for the infinite product? I know it's convergent by means of the log on the product but to find its value is not easy. I was trying some Taylor expansions around powers of trigonometric functions or exponentials but couldn't find the right pattern. This is like a method I did to find the value of the zeta function z(2) =  \pi  2 /6


linear algebra
matrix
geometry
geometric transformation
rotation
linear algebra unsolved

Caracterise A matrix in M(n,R) such that   tA=A^(k)  where tA is the transpose of A

A^(k) is  k power of A,  k is integer greater than 1

the complex case:
suppose that $ A^{*}= A^{k}$.
Schur's Lemma shows that there exists a unitary matrix $ U$ such that $ A = U^{*}T U$ and $ T$ is upper triangular. Then $ T^{*}= T^{k}$, wich shows that $ T$ is actually diagonal: $ D=diag(d_{1}, d_{2}, \ldots, d_{n})$ where $ d_{i}^{k}= \overline{d_{i}}$. Hence every $ d_{i}$ is a $ k+1$-th root of the unity, or is null. is it a good description ?

The real case (following Alekk).
$ d_{j}=e^{\frac{2i\pi\lambda_{j}}{k+1}}$ where $ \lambda_{j}\in\{0,\cdots,k\}$.
By associating pairwise the conjugate $ A$-eigenvalues we obtain that there exists an orthogonal matrix $ P$ s.t. ${ A=P^{T}diag[Rot(\frac{2\pi\lambda_{1}}{k+1}),\cdots,Rot(\frac{2\pi\lambda_{p}}{k+1}}),0_{1},\cdots,0_{q})]P$ where $ 2p+q=n$ and $ Rot(\alpha)$ is the matrix of the vectorial rotation of angle $ \alpha$.


geometry
geometric transformation
reflection
geometry proposed

Let B, C be two fixed points on the circle (O). Let M be the middle point of the smaller arc of BC. Let D be an changing point on the smaller arc of BC. DM intersects BC at H. Let H' be the reflection of H by DC. Find the locus of H'. :D

If $DH'$ cuts $(O)$ again at $N,$ then $DC$ bisects $\angle HDH' \equiv \angle MDN$ $\Longrightarrow$ arcs $CM$ and $CN$ of $(O)$ are congruent $\Longrightarrow$ $N$ is fixed. $DM$ bisects $\angle BDC$ $\Longrightarrow$ $\angle CDM=\angle BDH$ and since $\angle DBH=\angle DMC,$ then it follows that $\angle DHC=\angle DCM$ $\Longrightarrow$ $\angle DNM=\angle DCM=\angle DHC=\angle DH'C.$ Hence, if $U \equiv CH' \cap MN,$ $\triangle UNH'$ is U-isosceles, or $UN=UH'$ $\Longrightarrow$ $H'$ runs on an oblique strophoid  with pole $C,$ cusp $N$ and construction line $NM.$

What happens when D varies all over the circle?


I am currently an eigth grader enrolled in Honors Geometry and am rather ignorant about how high school works.

Do the counselors at high schools allow testing out of Algebra 2, you is it necessary for me to take 2 math courses simultaneously next year?

It all depends on your high school.  Some may let you test out of a course, some may require you take a summer course.  The best thing to do is discuss the issue with your counselor and the administration.

I am pretty sure that you have to take the class. It's an easy class but you have lots to learn (it's the basics for all the problem solving stuff here). I think Algebra II is a requirement of MY high school.. I don't know about yours though.

If I want to I can pass out of it. I'm going to study the book this summer and take Pre Cal next year.


[hide="solution"]
taking $ x^{2}$ out we get $ \lim_{x \to \minus{} \infty} \frac {  \sqrt {2 \plus{} \frac {1}{x^{2}}}}{ \minus{} 4 \minus{} \frac {1}{x}} \equal{} \lim_{u\to 0^{ \minus{} }}\frac {  \sqrt {2 \plus{} u^{2}}}{ \minus{} 4 \minus{} u} \equal{} \frac {1}{\minus{}2 \sqrt {2}}$[/hide]

Final answer is wrong. Think Logically. Numerator is positve, denominator is negative.

sorry this happend when u don't solve it with pen and paper  :D
the answer is $ \frac{\minus{}1}{2\sqrt{2}}$

Edit your post above. The key point is that, when you take $ x^2$ out of the root, it becomes -x and not x. ;)

ye si have done that  :)
the only thing i did wrong though i divided by $ \minus{}x$ but forgot to take the minus sign from above :)


Euler
function
number theory solved
number theory

Solve the equation

phi(n) = d(n) where phi(n) is Euler function, d(n) is the number

of divisor of n

I think I solved it, but my soln is so long it scares me. There's nothing smart abt it, it's just a case chase. We write n=p1^a1*..*pk^a^k where pi are primes, we write phi(n) and we use the fact that d(n)<=(a1+1)*..*(ak+1). Then we take the cases k=1, k=2 etc. and we find that k>=4 does not work (I think, I haven't checked everything). I won't post the actual soln, here's what I found: n is in the set {1, 3, 8, 10, 18, 24, 30}. Are these all?


A leaky faucet can be expensive. Suppose you put a measuring cup under a leak and collect a 1/2 cup of water from 8am to 4pm. How many gallons of water would this amount to in 1 day if there are 16 cups in a gallon?

[hide]That's 1/2 per 8 hours and 3/2 per day. So 3/32 of a gallon.[/hide]


geometry
induction
pigeonhole principle
USAMO
Hi

Let $n$ be an integer greater than 1. Suppose $2n$ points are given in the plane, no three of which are collinear. Suppose $n$ of the given $2n$ points are colored blue and the other $n$ colored red. A line in the plane is called a [i]balancing line[/i] if it passes through one blue and one red point and, for each side of the line, the number of blue points on that side is equal to the number of red points on the same side.
Prove that there exist at least two balancing lines.

Hmm... A strange problem.

Consider a convex hull of the whole set. If it contains red and blue points then, obviously, we are done. Therefore suppose the convex hull consists of blue points only.

Take $A,B,C$ three consecutive vertices on the convex hull. We state there is a balancing $A$ through $A$. Indeed, consider the leftmost line $k$ through $A$ s.t. the right open halfplane contains the same number of red and blue points :!:. The line $k$ exists due to discrete continuity arguments (just rotate $k$ from $AB$ towards to $AC$). We know that $k$ contains a point $D$ from our set. If $D$ is a red point then we are done. If $D$ is a blue point, then there is another line between $AB$ and $k$ satisfying the condition :!: . Contradiction.
Since the convex hull contains at least three points we conclude that there are at least three balancing lines for this case.

Please, someone read it! I think I missed something :(

I solved it the same way. So, I missed the same thing as you.

I solved it almost exactly the same way, except I didn't know what a convex hull was so I had to write a page defining the convex hull.

Let C be right of A. Label the red points $R_i, i=1,2,...,n $ so that $i > j \Rightarrow \angle CAR_i  > \angle CAR_j $ (i.e., counterclockwisely)

If we draw all the lines $AR_i $, then the number of red points on the right side of $AR_i $ is $i-1, i=1,2,...,n.$ The number of blue points on the right side of $AR_i $ increases from 1 to at most n-2 as i increases from 1 to n.

So $i-1$ starts smaller and ends larger than the number of blue points right of $AR_i $, and $i-1$ also takes on every single value between 0 and n-1, so they have to equal at some point. So this is a balancing line. Do the same thing for B.

[quote="tekno10m"]I guess, iff you're experienced. I spent like an hour trying to do it via induction... :?[/quote]

I also tried it via induction.   I didn't have much time to do it though, and ended up getting in the base case, which was to show its true for 2 reds and 2 blues.

Then, obviously, if you put the red and blue point on the same point of the balancing line, that line still acts as a balancing line.

If not, that's where it gets a little wierd.  Lets say you put the red on side "A" of the line and the blue on side "B."  Rotate your old balancing line about the blue point so that the red point it formerly passed through falls into side "B."  If the line next crosses a red point, you have found a new balancing line.  If not, you cross a blue point before a red point, then you will have more blues on side B than reds.  Therefore, once you hit a red point, rotate the line about that red point so as to move more blues to side A.

I conjectured (but was unable to prove) that eventually you will eventually find a new balancing line by this method.  Therefore, each balancing line for 2n points has a corresponding balancing line for 2n+2 points, QED.

Obviously I dont expect full credit, but hopefully they will give me a point or two for my base case and conjecture.

JB

Just a word about balanced lines, about which there are many papers.

J. Pach and R. Pinchasi proved that, according to a conjecture of G. Baloglou, for $n$ red points and $n$ blue points in general position in the plane there are at least $n$ balanced lines.
And this bound is sharp.

J.Pach, R. Pinchasi, 'On the number of balanced lines', Discrete and Computational Geometry, 2001, p. 611-628.

Their lemma 1-5 states that for any vertex $v$ of the convex hull of the given set, there is a balanced line passing through $v$.
Their argumentation in the proof of this lemma is Myth's one.

Pierre.

[quote="Myth"]So, it means that the problem is really "trivial". I.e. it is just a direct application of well known ideas: convex hull + discrete continuity.[/quote]

Well-known to you, perhaps.  But not to most high school students, even olympiad-types.  Furthermore, there are so many other techniques that less-experienced students might be led to try.  With your level of experience, a glance at the problem suggests discrete continuity, and the convex hull comes soon after.  But we don't all have your level of experience!

I might also describe #3 in the same terms.  #3 uses even simpler well-known ideas - parallel lines, inscribed angles, and cyclic quadrilaterals.  But I wouldn't describe it as trivial.

America... What should I do that everyone see I wrote [b]"trivial"[/b], not trivial.
Indeed, problem is not trivial, but it is absolutely straightforward in some sense. You see that Fedor did exactly the same things as me.

The students more experienced with problem solving that I know all jumped straight to the convex hull. I, for one, spent many hours trying induction, pigeonhole, extremal, contradiction, and even connecting-the-lines (kinda sorta graph theory I guess) while expending many pieces of paper on plots. So I guess this problem gives a huge advantage to experience, arguably much more so than most of the other problems.

I did this for fun.  My solution is not fundamentally different than those presented here.  Just a slightly different explanation.

Consider the convex hull of points.  If the convex hull contains both red and blue points, then as we consider the points on the hull in a counterclockwise direction, there must be at least one blue point immediately followed by a red point, and there must be at least one red point immediately followed by a blue point.  Lines connecting these pairs of points will be balancing lines.  There are at least two such lines.

Otherwise, the convex hull is monochrome.  In the following, we consider the convex hull to be monochrome blue, but we note that similar arguments would apply if the convex hull were monochrome red.

If the convex hull is monocrome blue, we choose one point on the convex hull and divide the half-plane containing all points into $n+1$ sectors, by drawing a series of rays from the chosen point through each red point.  Sectors $S_1$ and $S_{n+1}$ must each contain at least one blue point.  The remaining sectors may or may not contain blue points.

[img]http://www.artofproblemsolving.com/Forum/files/usamo2005-5_673.gif[/img]

Recall that the total number of blue points is equal to the total number of red points.  If we consider $L_1$, we note there is an excess of blue points to the right of the ray.  We denote the excess of blue points to the right of line $L_i$ by $K_i$.  $(K_1 > 0)$  If we consider $L_n$, we note there is an excess of blue points to the left of the ray.  (Or a negative excess of blue points to the right of the ray.)  $(K_n < 0)$

Consider each successive line, $L_i$, from $L_2$ through $L_n$.  If Sector $S_i$ contains one blue point, the imbalance in $L_i$ will equal the imbalance in line $L_{i-1}$.  $(K_i = K_{i-1})$  If Sector $S_i$ contains more than one blue point, the excess of blue points to the right of $L_i$ will increase, compared to the excess of blue points to the right of $L_{i-1}$.  $(K_i > K_{i-1})$  However, if Sector $S_i$ contains no blue points, the excess of blue points to the right of $L_i$ will decrease by exactly one, compared to the excess of blue points to the right of $L_{i-1}$.  $(K_i = K_{i-1} - 1)$

The value(s) where $K_i = 0$ correspond to a balancing line.  Since the sequence, $K_1, K_2, K_3, \ldots, K_n$ is known to go from a positive value at $K_1$ to a negative value at $K_n$, by positive integer steps, zero steps, or steps of negative one, the sequence must pass through 0 at least once.  Thus, at least one of the lines is a balancing line.

If we choose another point on the convex hull, we are guaranteed to find another (distinct) balancing line.

Thus, in every case, there are at least two balancing lines.  QED

If you've seen IMO 99 #1 you were probably more than ready to use Convex Hull on this problem.

I experimented for a while with the rotate-the-line method, then succumbed to a very seductive application of the Pigeonhole Principle and induction.  And in any case, my line-rotating was restricted to an inductive method that would generate a new balancing line from those in a set of 2n-2 points.  I abandoned it because it seemed messy, and I couldn't get it to work.  Darn.

I didn't know about convex shells, either, so I just proved it. Then, with the line rotation, I made $ a_0, a_1, ... a_n$ the counts of blue points before, after, and in between the n red points. Then you have the sum of the $a_i$ equal to $n - 1$. Then a balancing line exists through our blue point and the $k + 1^{st}$ red point met in the rotation iff the sum of the $a_i$ for $i$ from $0$ to $k$ is equal to $k$. It does not seem hard, then, to prove that there must be at least one $k$ for which this is true. I did not have time to do it on the USAMO, but I would have liked to. It sounds like if I had scattered the words "finite", "discrete", and "continuity" here and there in my proof, the judges would be happier with my proof. Oh well. I liked this problem anyways. I might have done it the hard way, though. Or is the hard way the inductive proof ... ? (Which I also briefly looked at, then decided that it was too hard. Then I solved it this way)
Yeah. I don't see anything wrong with your proof, Myth. On the other hand, I might just be missing something ... oh wait! You forgot to prove that deterministic primality testing only takes $O(n^{O(1)})$ in the worst case! I fill in for your glaring omission here:

Theorem: Deterministic primality testing for positive integer n can be computed in $O(n^{O(1)})$

Proof: It has been done; such algorithms exist, and I was standing within about 20 feet of the source code (and the source of the source code) for one such algorithm written in Mathematica, at the NorthWest Science Expo. I got to do that for several hours. That was fun.

Actually, my doubts were concerned only with the fact, that problem is too straightforward (for experienced olympiad students). I see now that it were baseless doubts, since many people did the same things as me.

I solved this problem the same way a [i]very[/i] similar problem is solved in [u]Math Olympiad Challenges[/u]:

[quote]3.1 Arrange in Order
Example 2: Given $2n+2$ points in the plane, no three collinear, prove that two of them determine a line that separates $n$ of the points from the other $n$.[/quote]
I guess I'm just lucky I happened to read that particular section and that that problem stuck in my mind.

I tried induction and wrote a 5 page long solution that really made no sense, but that's ok.  I have no idea what a convex hull is....oh well, I still have many more years left.

[quote]
3.1 Arrange in Order
Example 2: Given 2n+2 points in the plane, no three collinear, prove that two of them determine a line that separates n of the points from the other n. [/quote]

So basically almost the exact same problem wow.

[quote="rrusczyk"]

Well-known to you, perhaps.  But not to most high school students, even olympiad-types. [/quote]

I solved the problem very similar, using convex h. and d. continuity... I think one can easily think of convex hull because you think of it as a trivial case, when one side of the balancing line has no points and the other has  the remaining 2n-2...
once you get to a convex hull you try some example for small n and see how can you get a balancing line.. making some arguments clear may be the matter of expierience, but the idea isn't..
croatia hasn't got as good results as US but contestants are mostly familiar with those terms (hull and continuity)...

[quote="Philip_Leszczynski"]I think the proof given in the AMC website is flawed; it claims that every point on the convex hull lies on a balancing line.

But suppose we have the 2 red points (0,0) and (0,1) and the 2 blue points (-1,-1) and (1,-1).
Obviously the convex hull is (0,1) (-1,-1) (-1,1).
But the point (0,1) is not on any balancing lines (look at the diagram) but it is on the convex hull.[/quote]

Err, aren't the lines through (0,1); (-1,-1) and (0,1); (1,-1) both balancing lines? They both have one red and one blue on one side and none on the other...

[b][u]Lemma.[/u][/b]
Let $k \ge 3$ be an integer. Then, given any $k$ distinct points in the plane with no three points collinear, there exists a convex polygon, with vertices from the $k$ given points, such that all of the $k$ points lie within the polygon.
[i]Proof.[/i]
We proceed by induction on $k.$ The base case, $k = 3$, is trivial. We simply connect the three points into a triangle. Since every triangle is convex, the claim follows. Now, for the induction hypothesis, assume the claim to be true for some $k = m$, where $m \in \mathbb{N}, m \ge 3.$ We prove the claim true for $k = m + 1.$

Let us label the points $X_1, X_2, ..., X_{m + 1}.$ By the induction hypothesis, there exists a convex polygon, which we will denote by $\oslash$ with vertices from the set $\{X_1, X_2, ..., X_m\}$, that contains all points $X_1, X_2, ..., X_m.$ Now, if the point $X_{m + 1}$ also lies in $\oslash$, then we are done. If $X_{m + 1}$ does not lie in $\oslash$, then consider a line $\gamma$ passing through $X_{m + 1}$ such that $\gamma$ does not intersect $\oslash.$ Note that since $X_{m + 1} \notin \oslash$, such a line $\gamma$ must exist.

Now, we rotate $\gamma$ couterclockwise until it first  intercepts a vertex $X_p$ of $\oslash.$ We continue to rotate $\gamma$ counterclockwise until it intercepts a vertex $X_q$ of $\oslash$, such that $X_q$ is the last vertex that $\gamma$ intercepts during this rotation (until it once again intercepts $X_p$ after rotating through $180^{\circ}$).
Denote by $S$ the sequence of consecutive vertices of $\oslash$ that connect $X_p$ and $X_q$, where $S$ lies on the opposite side of line $X_pX_q$ as $X_{m + 1}.$
It follows that all vertices of $\oslash$ that are not $X_p, X_q$ or in $T$ are contained within the lines $X_{m + 1}X_p$ and $X_{m + 1}X_q.$ Therefore, $X_{m + 1}X_pTX_q$ is a convex polygon that contains all $m + 1$ points.
Therefore we have shown the claim true for $k = m + 1.$ This completes the induction.

Now, since $n \ge 2$, there are at least $2 \cdot 2 = 4$ given points. Therefore, by our Lemma, there must exist a convex polygon, which we will denote by $\otimes$, with vertices from the $2n$ given points, such that all of the $2n$ points lie within $\otimes.$ We label these vertices (in the order that they appear in $\otimes$) $P_1, P_2, ..., P_i$, where $i \in \mathbb{N}, i \le 2n.$  We now consider two cases:

[u]Case 1:[/u] $P_1, P_2, ..., P_i$ are all the same color.
WLOG, assume that these points are all red. Then the adjacent vertices $P_1$ and $P_2$ are both red. Now, consider the line $P_1P_2.$ We rotate this line about $P_1$ in the direction such that $P_2$ is rotated into $\otimes.$ Let $Q$, where $Q$ is one of the given $2n$ points, be the first blue point that the line $P_1P_2$ intercepts during this rotation. Then the line $P_1Q$ divides the plane into two regions, one of which contains only red points (among which is $P_2$), and the other contains the remaining of the given $2n$ points (other than $P_1$ and $Q$, of course). Since the first region contains only red points, it follows that the second region, which contains the point $P_i$, contains more blue points than red points.
Now, we continue rotating the line $P_1P_2$ in the same direction until it intercepts $Q*$, where $Q*$ is one of the $2n$ given points, and $Q*$ is the last blue point that the line $P_1P_2$ will intercept during its rotation, until $P_1P_2$ intercepts $P_i.$ Then the line $P_1Q*$ divides the plane into two regions, one of which contains only red points (among which is $P_i$), and the other contains the remaining of the given $2n$ points (other than $P_1$ and $Q*$, of course).

Therefore, during this rotation, the line $P_1Q$ divides the plane into two regions. The region containing the point $P_i$ has more blue points than red points. Then, the line is further rotated to $P_1Q*.$ The line $P_1Q*$ divides the plane into two regions, where the region containing $P_i$ contains more red points than blue points.

Therefore, by the principle of continuity, there must exist a blue point $R \in \otimes$, such that the line $P_1R$ divides $\otimes$ into two regions, with each region containing an equal number of red and blue points. Hence, there exists a balancing line passing through $P_1.$ Similarly, we can show that there exists a balancing line passing through $P_2$, and in general, through all of the $P_k$'s. Since we have shown that there exist at least two balancing lines, this concludes Case 1.

[u]Case 2:[/u] The set $\{P_1, P_2, ..., P_i\}$ contains both red and blue elements.
Consider the longest consecutive sequence of red vertices on $\otimes.$ Since the vertices of $\otimes$ are not all red, it follows that the first and last red vertex in this sequence must be adjacent to a blue vertex. Therefore, $\otimes$ must contain at least two pairs of consecutive vertices that are opposite in color. Suppose these pairs of adjacent vertices are $(P_a, P_b), (P_c, P_d)$ where $P_a, P_c$ are red and $P_b, P_d$ are blue. Note that these pairs are distinct, since if $P_a = P_c$ and $P_b = P_d$, then it follows that $\otimes$ has only two vertices, absurd.
Now, since the pairs $(P_a, P_b)$ and $(P_c, P_d)$ are distinct, the two lines $P_aP_b$ and $P_cP_d$ are also distinct. In addition, since the $P_i$'s are simply vertices of a convex polygon, $\otimes$, that encloses the given $2n$ points, it follows that the each of the lines $P_aP_b$ and $P_cP_d$ divides the plane into two regions, one of which fully contains $\otimes.$ Therefore each of these lines divides the plane into two regions, one of which contains the remaining $2n - 2$ points (other than the two in the line itself), and the other containing none of the given points. Clearly these $2n - 2$ points are comprised of $n - 1$ red points and $n - 1$ blue points, i.e., an equal number of red and blue points. Therefore, the lines $P_aP_b$ and $P_cP_d$ are both balancing lines. Since we have shown that there exist at least two balancing lines, this concludes Case 2.

Since we have considered all cases, the proof is complete.

Actually good cg problem??

Let $S$ be the set of all of the points. Also, given a line $\overline{PQ}$ (where the order of vertices matters) and a point $X$ not on that line, say $X$ is to the "left" of $\overline{PQ}$ if it is on the left half-plane from the perspective of an ant at $P$ looking towards $Q$, and say it is to the "right" otherwise.
Consider the convex hull of $S$. If it contains points of both colors, then any line drawn from a red point to a blue point is clearly balancing. Since there are at least two of these, the result is true in this case.
Hence suppose that the convex hull of $S$ contains points of only one color. WLOG let this color be blue. I will now prove the following key claim:

[b]Claim:[/b] For every blue point $B$ on the convex hull of $S$, there exists at least one balancing line passing through $B$.
[b]Proof:[/b] Consider the $n$ red points, none of which are on the convex hull. Number these points $R_1,R_2,\ldots,R_n$ such that $R_i$ is to the left of $\overline{BR_j}$ if and only if $i<j$. Also define a function $f$ such that $f(i)$ is equal to the number of blue points to the left of $\overline{BR_i}$ minus the number of red points to the left of $\overline{BR_i}$. It is evident that the line $\overline{BR_i}$ is balancing if and only if $f(i)=0$.
Consider the difference between consecutive values of $f$. Since there is exactly one red point to the left of $\overline{BR_{i+1}}$ and not to the left of $\overline{BR_i}$ (namely $R_i$), it follows that $f(i)-f(i+1)$ is at most $1$ for all $i$; that is $f(i)$ decreases by at most $1$ when $i$ increases by $1$.
Now, note that $f(1)>0$, since there are no red points to the left of $\overline{BR_1}$, but there must be at least one blue point (else $R_1$ lies on the convex hull), and by similar reasoning $f(n)<0$. Hence there must be some value $1 \leq x \leq n$ such that $f(x)=0$, otherwise $f(i)$ decreases by at least $2$ when $i$ increases by $1$. (This is known as discrete continuity/discrete IVT).

To finish, note that the number of points on the convex hull of $S$ is at least $3$, hence there are at least $2$ balancing lines for $S$, as desired. $\blacksquare$

Consider the convex hull of the $2n$ points. It must consist of at least $3$ points such that any 3 are not collinear. First consider when it consists of both red and blue points. WLOG assume there must be at least 2 red points. Call these 2 red points $R_1$ and $R_2$. Then, the 2 balancing lines are $R_1B$ and $R_1B$, where $B$ is any blue point on the convex hull. For both $R_1B$ and $R_2B$, the other $2n-2$ points all lie on one side of the line, so $R_1B$ and $R_2B$ are indeed balancing.

Now consider when all the points on the convex hull is one color. WLOG let the color be red. Label the points on the convex hull $R_1, R_2, \dots, R_i$ $(i \ge 3)$. Focus on $R_1$. Then, label the blue points $B_1, B_2, \dots B_n$ such that $R_1B_j$ is to the left of $R_1B_{j+1}$ for all $j$. For all $R_1B_j$, let $X_j$ denote the number of blue points to the left of $R_1B_j$ subtracted from the number of red points to the left of $R_1B_j$. We know that $R_1B_1 \ge 1$ and $R_1B_n \le -1.$ Moreover, if $X_{j+1} < X_j$, $X_{j+1}$ must be at most 1 less than $X_j$ since there are no blue points between $B_j$ and $B_{j+1}$. By the intermediate value theorem, there exists an $X_{\ell}$ such that $X_{\ell}=0.$ Then $A_1B_{\ell}$ is the desired balancing line. A similar process can be done for $R_2$, so we have another balancing line and we are done. (In fact, every red line on the convex hull is part of a balancing line).

POV: you spend 1 hour proving the existence of a convex hull

Consider the convex hull of the points. If both red and blue points exist on the convex hull, then we are done because taking an adjacent red/blue pair produces a balancing line.

Otherwise, WLOG suppose only blue points are on the convex hull. Taking one such point, we can continuously sweep clockwise by taking red points inside the convex hull.

Initially, one side of the line will have at least one blue points and no red points, and at the end, the same side of the line will contain $n-1$ red points, but at most $n-2$ blue points. Since the number of red points on this side of the line increases by exactly $1$ each time we take a new line, and the number of blue points on that side cannot decrease, one of the lines drawn will be a balancing line.

This works for all points on the boundary, and since our convex hull consists of at least $3$ points, we will have at least $2$ balancing lines, as desired.

CASE 1: One can notice That if any blue and red point have not points on one of it's sides this mean the line between them is a balancing line (as on the other side we will have $n-1$ blue points and $n-1$ red).\\

CASE 2: Now we consider the case in which all the points are inside a polygon with all vertices being one color (assume WLOG it's blue).
Now consider a line that is pivoting at any vertex and rotating till reaching the other vertex of the polygon (convex hull) passing through every point in side the polygon. and let $x$ be the number of red points.\\
minus the number of blue points on one side of the line.
In other words every time the line passes through a blue point $x$ will increase by $1$, and decrease by $1$ if it passes through a red point.\\
Firstly we have that $x=1$ and when the line reaches the other vertex of the polygon  it will be equal to $-1$.
So when $x$ will be equal to zero, we have a balancing line.
Now repeating this process on all the other vertices of the polygon (convex hull) then we will have balancing lines equal to the number of the vertices.

If the convex hull is not monochromatic, the result is true by considering any dichromatic edge of the convex hull.

Otherwise, take a line $\ell$ through two (say) consecutive blue points on the convex hull, and rotate $\ell$ counterclockwise until it touches a red point; call this line $\ell_0$. We keep track of the difference $D$ between the number of red and blue points on the side that originally contained the edge containing $\ell$. In particular, $D$ must be negative to begin (as there are no red points on that side by assumption). Now, we rotate $\ell$, stopping to compute $D$ every time $\ell$ hits another red point.

In particular, any difference $D$ increases by at most $1$ every time we hit a new red point. In particular, the last such line $\ell$ will have $D$ nonnegative. So by continuity, there exists a point in between where $D=0$ precisely.

We have demonstrated that there exists a balancing line through some vertex of the convex hull. As there are at least two such vertices, we are done.


Solve equation $ 2sin2x\plus{}(2\sqrt{3}\minus{}3)sinx\plus{}(2\minus{}3\sqrt{3})cosx\minus{}6\plus{}\sqrt{3}\equal{}0$.

Thank.


I've already proved that's imposible for k=2, k=3 and k>4 but I don't know how to solve this:
      $\sqrt{a_{1}+\sqrt[3]{a_{2}+\sqrt[4]{a_{3}}}}\ge\sqrt[32]{a_{1}a_{2}a_{3}}$ for any real numbers $a_{1},a_{2},a_{3}\ge0$.

I have already posted this [url=http://www.mathlinks.ro/Forum/viewtopic.php?highlight=shortlist&t=58937]here[/url].


according to a post at Slashdot, Professor Arenstorf from Vanderbilt University presented a 38-page possible proof of the twin-prime conjecture.  The paper can be found here: http://arxiv.org/abs/math.NT/0405509

interesting...too bad most of it is way over my head...

there are bizarre stuff on that website, like: http://arxiv.org/PS_cache/math/pdf/0405/0405509.pdf

cant be trusted completely since it hasnt been peer reviewed

Well it [i]is[/i] "owned, operated, and funded" by Cornell University.

I went to look at the paper he wrote and got the message "A serious error has been found in the paper, specifically, Lemma 8 is incorrect."  Thus, the twin prime conjecture is still unproved.

Since Arenstorf's (faulty) proof is no more available from arxiv.org could anybody upload it here (or send it to me)?

Thank you in advance.

The proof was demonstrated to be incorrect within a few days of its posting, I think there was an article with the disproof (by a different author) posted on arxiv shortly after the paper appeared.


linear algebra
matrix
algorithm
vector
search

Consider the following algorithm for encoding alphabetical messages.
Step 1:Break the message(including spaces) into 4 letter blocks.
Step 2:Convert each 4 letter block into a 4*1 vector d(i),using:
         space=0 , a=1, b=2,...,z=26.
Step 3:Encode each  block by computing Ad(i) ,where A is a 4*4 matrix.
Step 4:Present the encoded message as a numerical sequence,where the first four terms of the sequence are the entries in Ad(1),reading from the top down ,teh second four are the entries in Ad(2),etc.

Suppose an encoded message,using matrix A and the algorithm above,is : 225,465,-240,246,82,182,-100,87,-42,3,-9,-114,-72,-57,25,-144.

Decode this message.

we can make a better process of encoding seting space=0 , a=1, b=2,...,z=26.

and after make a list like "abc" = (1,2,3)

After that we subtract the following number by the previously. and make another list and convert the number to the characteres.

only a person who know the first letter can decipher it.

but codes like that is easy so decode. since we know how to decode.

this is not a challenge. make 7 steps enconding just to become more hard. but the code itself it's not a true code

you can search on google about DES, if you like codes


if a+b+c=1 and a,b,c>0 then Prove that:
\[ \sum{\frac{a}{4b^{2}+1}}\geq(\sum{a\sqrt{a}})^{2}\]

It proved by Cauchy-Schwarz
\[ \sum{\frac{a}{4b^{2}+1}}=\sum{\frac{a^{3}}{4a^{2}b^{2}+a^{2}}}\geq\frac{(a\sqrt{a}+b\sqrt{b}+c\sqrt{c})^{2}}{a^{2}+b^{2}+c^{2}+4(a^{2}b^{2}+b^{2}c^{2}+c^{2}a^{2})}\]
And we prove
\[ \sum{a^{2}}+\sum{4a^{2}b^{2}}\leq\ 1=(a+b+c)^{2}\]

\[ \Leftrightarrow\sum{2a^{2}b^{2}}\leq\sum{ab}\]

\[ \Leftrightarrow\sum{ab(1-2ab)}\geq\ 0 \]
(This is easily :a+b+c=1 => ab,bc,ca<1/2)
Equation when (a,b,c)=(0,0,1)and the permutations.
[color=red]Keep it simple: As simple as possible, but no simpler

___Albert Einstein__[/color]
[color=blue]I'm Nguyễn Tâm Đăng , vietnam[/color]


[quote="Lucky_Luke"]Sometimes alcumus wont give me two tries... is this normal?[/quote]

If you get it right, then you don't get two tries...

Maybe you had tried it, closed the window, and later came back to the problem.  You would be on your second try, but thought it was your first...

no, i mean when i get the problem wrong the first try, it doesn't even show the "That is incorrect" screen it just jumps to the solution and says i'm wrong

I kinda have the same problem. When I get a question wrong and want to try it again, it takes me to a new problem.

same problem on all, I used everyone except safari.

How many people are experiencing this problem?

Just to confirm the issue:

User enters answer incorrectly
User directed directly to solution page, bypassing second chance
User gets new problem and answers incorrectly
User directed directly to solution page, bypassing second chance

well, not consecutively. it's only happened three times

Maybe it's an issue on a specific problem(s)?

Probably not, if its three different times.

Well it works for me:
Windows XP
Opera 9.5 I think.


Three mutually external circles $ C_1,C_2,C_3$ with respective centers $ O_1,O_2,O_3$ are given.

Let $ l_1$ be the tangent from $ O_1$ to $ C_2$, one nearer to $ C_3$.
Let $ l_2$ be the tangent from $ O_3$ to $ C_2$, one nearer to $ C_1$.
Let $ l_3$ be the tangent from $ O_2$ to $ C_3$, one nearer to $ C_1$.
Let $ l_4$ be the tangent from $ O_1$ to $ C_3$, one nearer to $ C_2$.
Let $ l_5$ be the tangent from $ O_3$ to $ C_1$, one nearer to $ C_2$.
Let $ l_6$ be the tangent from $ O_2$ to $ C_1$, one nearer to $ C_3$.

Let $ A\equal{}l_1\cap l_2,B\equal{}l_2\cap l_3,...,F\equal{}l_6\cap l_1$

Prove that $ AB\cdot CD\cdot EF\equal{}BC\cdot DE\cdot FA$ if and only if $ AD,BE,CF$ are concurrent.


Find all solutions in integers of the equation:
$ y^2\plus{}y\equal{}x^4\plus{}x^3\plus{}x^2\plus{}x$ :ninja:

Fix some $ x\in \mathbb{Z}$ and try to find $ y$. We have an second grade equality with variable $ y$: $ y^2 \plus{} y \minus{} (x^4 \plus{} x^3 \plus{} x^2 \plus{} x) \equal{} 0$.
To obtain $ y\in \mathbb{Z}$ we need that $ 1 \plus{} 4(x^4 \plus{} x^3 \plus{} x^2 \plus{} x)$ be an perfect square but note the following: $ 1 \plus{} 4(x^4 \plus{} x^3 \plus{} x^2 \plus{} x) \equal{} (2x^2 \plus{} x)^2 \plus{} 3x^2 \plus{} 4x \plus{} 1$.
If $ 3x^2 \plus{} 4x \plus{} 1 \equal{} 0$, the $ x \equal{} \minus{} 1$ and this is a solution.
Otherwise $ 3x^2 \plus{} 4x \plus{} 1 > 0$ for $ x\in\mathbb{Z}$. Then $ (2x^2 \plus{} x \plus{} 1)^2\le 1 \plus{} 4(x^4 \plus{} x^3 \plus{} x^2 \plus{} x) \to 1 \plus{} 4x^2 \plus{} 2x\le 3x^2 \plus{} 4x \plus{} 1 \to x^2\le 2x \to 0\le x(2 \minus{} x)$.
Finally we put $ x \equal{} 0,1,2$ and get the solution, $ x \equal{} 2, \minus{} 1,0$. Finally the pair are (2,6), (2,-5), (-1, 0), (-1,1), (0, 0), (0,-1).


function
abstract algebra
algebra
polynomial
induction
group theory
calculus

Let $ k$ be an algebraically closed field. Prove that any $ k\subset A\subset k(x)$ which is a valuation ring is in fact a discrete valuation ring.
Is this result true ?
I was thinking that this might be a counterexample: $ A \equal{} \left\{\frac{f(x)}{g(x)}\in k(x): g(0)\neq0 \right\}$. This $ A$ satisfies the property if $ a\in k(x)$ then either $ a$ or $ a^{\minus{}1}$ is in $ A$ (which is an alternative definition for a valuation ring). But $ A$ is not Noetherian so it can't be a DVR.
Is there something wrong ?

[quote]$ A$ is a localisation of a noetherian ring $ k[x]$, thus it is notherian.[/quote]
:oops: stupid mistake...

We don't need $ k$ algebraically closed.
Statement: Let $ k$ be a field and let $ K/k$ be a finitely generated field extension of trdeg=1. Then any valuation ring $ k\subset A\subsetneq K$ is a DVR.

Step 1. $ K = k(X)$. Let $ k\subset A\subsetneq K$ be a valuation ring. We can suppose that $ X\in A$, otherwise $ X^{ - 1}\in A$ and $ K = k(Y), Y = X^{ - 1}$ so it will be the same argument.
Observe now that there is a unique irreducible polynomial $ P\in k[X]$ such that $ P^{ - 1}\not\in A$: there must exist at least one, else $ A$ would be $ K$. If there exist $ P,Q$ irreducible with $ P^{ - 1},Q^{ - 1}\not\in A$ then by localisation we see that there exist $ \frak{m}, \mathfrak{n}\in A$ different maximal ideals - which is a contradiction since $ A$ is local.
So our ring $ A$ must be $ S^{ - 1}k[X]$ where $ S = \{Q\in k[X], (P,Q) = 1\}$ and this is clearly a discrete valuation ring.

Step 2. If $ L\supset K\supset k$ where $ K = k(X)$ is a finite algebraic extension with $ [L: K] = r$ and if $ v: L^*\to G$ is a valuation of $ L$ then if we denote by $ H = v(K^*)$ we have $ [G: H] \le r$. Take $ \alpha_i\in G, i = 1,r + 1$. Then there exist $ x_i, i = 1,r + 1$ in $ L$ such that $ v(x_i) = \alpha_i$. Since $ [L: K] = r$ it follows that there exist $ t_i\in K, i = 1,r + 1$ not all $ 0$ such that $ \sum_{i = 1}^{r + 1}t_ix_i = 0$. Using the fact that if $ v(x)\neq v(y)$ then $ v(x + y) = min(v(x),v(y))$ we deduce by induction that there is some $ i\neq j$ such that $ t_ix_i = t_jx_j$. So $ \alpha_i - \alpha_j = v(t_j) - v(t_i)\in H$ and this is what we want to conclude that $ [G: H]\le r$.

Step 3. If $ G$ is an abelian ordered group and if $ H < G$ is an [url=http://en.wikipedia.org/wiki/Archimedean_property]archimedean[/url], finite index subgroup of $ G$ then $ G$ is archimedian. If $ G$ has a least positive element then it is isomorphic to $ \mathbb{Z}$.
Let $ n = [G: H]$ and $ x,y\in G, x,y > 0$. Then $ nx,ny\in H$ so there is some $ m$ such that $ mnx > mny$ and then $ mx > y$ and $ G$ is therefore archimedean. Therefore if $ H$ has a least positive element also $ G$ has a least positive element.

Let $ x\in G, x > 0$ be the least positive element. Then because $ G$ is archimedean any element of $ G$ is of the form $ nx$ with $ n\in\mathbb{Z}$, so $ G$ is isomorphic to $ \mathbb{Z}$.

Step 4 Let $ k\subset L$ of trdeg=1 and $ v: L^*\to G$ be a valuation. Then $ L/K, K = k(X)$ is a finite algebraic extension so $ v(K^*)$ is a finite index subgroup of $ G$ from Step 2. From Step 1 we have that $ v(K^*)$ is isomorphic to $ \mathbb{Z}$ and from Step 3 we get $ G$ isomorphic to $ \mathbb{Z}$.

Is this correct?

1. Consider an element $ x \in K$ which is transcendental over $ k$. Without loss of generality, assume that $ x \in A$ (otherwise we have $ \frac{1}{x} \in A$), i.e. $ k[x] \subset A$. Since $ A$ is integrally closed, the integral closure of $ k[x]$, say $ B$, satisfies $ B \subset A$.

Of course, since $ x$ is transcendental over $ k$, we have that $ K$ is a finite extension of $ k(x)$.

Theorem: The integral closure of a Dedekind domain in a finite extension of its quotient field is also a Dedekind domain.

Since $ k[x]$ is a Dedekind domain, we see that $ B$ is also a Dedekind domain by the theorem.

2. Let $ m$ be the maximal ideal of $ A$, and consider $ n \equal{} B \cap m$. Since $ B$ has dimension 1, $ n$ is either maximal or $ (0)$. If $ n$ is maximal, then note that $ B_n \subset A$ and A dominates $ B_n$ (as local ring). However,
a. $ B_n$ is a DVR since $ B$ is a Dedekind domain.
b. valuation rings are maximal elements in the poset ordered by domination. Since $ A$, $ B_n$ are both valuation rings, we must have $ A \equal{} B_n$, i.e. $ A$ is also DVR.

3. Therefore it suffices to show that $ n$ is not 0. Indeed, if $ n \equal{} (0)$, that means $ K(B) \subset A$, where $ K(B)$ is the fractional field of $ B$. However, as $ K$ is a finite extension of $ k(x)$ and $ B$ is the integral closure of $ k[x]$, this implies that $ K(B) \equal{} K$, which means that $ A \equal{} K$, which contradicts the given assumption.

I don't quite understand your proof, and may have made some mistakes.

I think the vital process is as following: suppose $ \frac {P}{Q} \in A$, since (P,Q)=1, there is such a U(x) that PU+QV=1. Since A is a ring, $ \frac {P}{Q}U \plus{} V \equal{} \frac {1}{Q} \in A$. If all prime polynomials' reciproties belongs to A then $ A \equal{} k(x)$, a contradiction. So suppose $ \frac {1}{H(x)}$ is not in A, where H is prime. Then for any other prime polynomial L(x), and from the above argument we have $ \frac {L}{H}$ is not in A and $ \frac {H}{L}$ is in A, hence $ \frac {1}{L} \in A$.

Thus (H) is the only maximal ideal in A.

I don't think you are proving Kuba's statement in his fourth post.

oh, I see. What does feild extension trdeg=1 means? I search the google and wiki but didn't find it, Seems familiar.

Transcendence degree. The maximal number of algebraically independent elements you can find.

It seems to be very similar proof with Soarer's, explaining a little more, why discrete val ring is "ordered". The first step is the same, consider the int ring in A, Soarer has already showed it's Dedkind. Then it remains to prove:
If D is a Dedkind domain, $ D\subsetneq A\subsetneq Frac(D)$, A is valuation, then A is discrete valuation.

(1).by a similar process in my #6 post, if $ \frac {a}{b}\in A$ then $ \frac {k_{1}a \plus{} k_{2}b}{b}\in A$ thus "pure" fractional ideal $ \frac {(a,b)}{b}\in A$.
(2).If all fractional ideal is in A then A=Frac(D), a contradiction.
(3).If two prime ideals' reciprocal $ \frac {1}{\alpha},\frac {1}{\beta}$ are not in A, consider $ \frac {q_{1}\alpha}{q_{2}\beta}$ which belongs to principle ideal class, such $ q_{1},q_{2}$ must exist by chinese remainder theorem, then from (1) either $ \frac {1}{q_{1}\alpha}$ or $ \frac {1}{q_{1}\beta}$ is in A, thus either $ \frac {1}{\alpha}$ or $ \frac {1}{\beta}$ is in A. Which means A is local, and thus, discrete valuation.


logarithms
inequalities
function
calculus
calculus computations

Show that if $ \sum a_n$ converges, then so does $ \sum\frac{\sqrt{a_n}}{n}$.

[hide="Answer"]Let $ \sum a_n$ and $ \sum b_n$ be to convergent series of positive terms. Then, as the sum of two convergent series also converges, then the sum whose general term is $ \frac{a_n \plus{} b_n}{2}$ is convergent. Therefore, $ \sum \sqrt{a_n b_n}$ also converges because for every n, $ \sqrt{a_n b_n} \leq \frac{a_n \plus{} b_n}{2}$.

In the present case, consider $ b_n \equal{} \frac{1}{n^2}$.[/hide]

And in fact Carcul's proof shows that $ \sum_{n \geq 1} \frac {\sqrt {a_n}}{n^{\frac {1}{2} \plus{} \varepsilon}}$ converges for any $ \varepsilon > 0$.  However, it's not true that $ \sum_{n \geq 1} \frac {\sqrt {a_n}}{n^{\frac {1}{2}}}$ will converge: take $ a_n \equal{} \frac{1}{n (\log n)^2}$, for example.

One can use the Cauchy-Schwarz inequality:

$ \sum \frac {\sqrt {a_n}}n\le\left(\sum a_n\right)^{\frac12}\left(\sum\frac1{n^2}\right)^{\frac12}$

What Carcul used was something that could be used in a proof of Cauchy-Schwarz, so it's a closely related argument.

And Cauchy-Schwarz also works with everything JBL said.

Now prove this:

Suppose $ 0 < s < 1$ and $ a_n > 0.$

If $ \sum a_n$ converges, then $ \sum\frac {a_n^s}{n}$ converges.

Don't all of these follow straight from the comparison test?

Depends on what you mean.  Could you explain your argument further?

[quote="Kent Merryfield"]Suppose $ 0 < s < 1$ and $ a_n > 0.$

If $ \sum a_n$ converges, then $ \sum\frac {a_n^s}{n}$ converges.[/quote]

[hide]If $ p \plus{} q \equal{} 1$, $ p, q \geq 0$ then $ pa \plus{} qb \geq a^pb^q$ for all $ a, b > 0$.  (This is just weighted AM-GM, or equivalently the convexity of the function $ a^xb^{1 \minus{} x}$.)  Thus $ pa_n \plus{} qn^{ \minus{} \frac {1}{q}} \geq \frac {a_n^p}{n}$ and so $ \sum \frac {a_n^p}{n}$ converges by comparison.  (Note $ \minus{} \frac {1}{q} < \minus{} 1$, so $ \sum n^{ \minus{} \frac {1}{q}}$ converges.)[/hide]

Just to give an argument along the lines of what SouthStar might have meant:
[hide]Let's say that $ n$ is small if $ a_n < n^{\minus{}1/(1 \minus{} s)}$, and large otherwise.  The small terms are bounded above by the sum of $ n^{\minus{}1/(1\minus{}s)}$, which converges.  If $ n$ is large, then $ \frac{a_n^s}{n} \le a_n$, so the large terms are bounded above by the sum of $ a_n$.[/hide]


Prove that if $0\leq u<v\leq\frac{\pi}{2}$ then \[\frac{u}{v}\leq \frac{\sin{u}}{\sin{v}}\leq \frac{\pi}{2}.\frac{u}{v}.\]

Equality is at u=0.
[hide]Rearrange to get $1<v/\sin{v}*\sin{u}/u<\pi/2$, with the first equality removed since u cannot equal 0 here.  The first fraction there is greater than 1 and has a minimum of 1 and a maximum of $\pi/2$, the second function is always less than 1 and has a minimum of $2/\pi$ and a maximum of 1.  If u and v tend to the same thing, the expression has a limit of 1, but since v>u, the expression can never equal one.  Also, because of that stipulation, the expression is never less than 1.
Maximize the expression.  That is done by maximizing both fractions.  Incidentally, doing so still allows v>u.  Set $v=\pi/2$ and set the limit of u to 0.  The expression approaches $\pi/2$.[/hide]