algebra
polynomial
hojoo lee
functional equation
IMO
IMO 2004
IMO Shortlist

Find all polynomials $f$ with real coefficients such that for all reals $a,b,c$ such that $ab+bc+ca = 0$ we have the following relations

\[ f(a-b) + f(b-c) + f(c-a) = 2f(a+b+c). \]

straightforward solution + 2 pages of calculations = bad IMO problem.

  Darij

In my opinion the first day characteristic was uglyness. And this problem is the best example. Of course, problem 3 is quite nice and difficult, but I bet another combinatorics problem could have been given. Again, just my opinion.

[quote="darij grinberg"]straightforward solution + 2 pages of calculations = bad IMO problem.[/quote]

And I say this inspite of the fact that I have solved it correctly and many others have made errors  :D  :D  :D

  dg

Why do you say 2 pages of computations? I might be wrong, but doesn't it reduce immediately to an exponential equation which has bounded solution ( i mean, you only need to see if 6 is a solution, which yes requires computation) by 7. But probably I'm wrong. Anyway, my opinion is that this problem is very idiot. Sorry...

I think a much interesting problem is the following: find all polynomials f such that for any such a,b,c like in the official problem, the number $\frac{f(a-b)+f(b-c)+f(c-a)}{2} $ is in the image of f (I mean, for any such a,b,c there exists a number $ g(a,b,c) $ such that that number equals f(g(a,b,c))).

Actually the answer is $P\left( x\right) = kx^4 + lx^4$, with constant real k and l. But in order to prove that $x^4$ works, one needs some rather messy calculations  :D

  Darij

you're actually right harazi(ok, i needn't tell you about mathlinks, anyway). but some idiots like me are too dumb to check that it works for n=4. hope they don't cancel too many points.

A reasonably clean solution:

We want to find all polynomials f such that $f(a-b)+f(b-c)+f(c-a)=2f(a+b+c)$ whenever $ab+bc+ca=0$. Equivalently, $ab+bc+ca$ divides $f(a-b)+f(b-c)+f(c-a)-2f(a+b+c)$.
Let $f(x)=r_nx^n+r_{n-1}x^{n-1}+...+r_0$ and $a'=ta,b'=tb,c'=tc$
Then $a'b'+b'c'+c'a'=0$ if $ab+bc+ca=0$ so $t^nr_n((a-b)^n+(b-c)^n+(c-a)^n-2(a+b+c)^n)+...+r_0(1+1+1-2)=0$
The functions of t $t^n,t^{n-1},...,1$ are linearly independent, so each coefficient $r_k((a-b)^k+(b-c)^k+(c-a)^k-2(a+b+c)^k)$ must be zero.
This means that either $r_k=0$ or $ab+bc+ca$ divides $(a-b)^k+(b-c)^k+(c-a)^k-2(a+b+c)^k$
For $k=2$, $(a-b)^2+(b-c)^2+(c-a)^2-2(a+b+c)^2=-4(ab+bc+ca)$
For $k=4$, $(a-b)^4+(b-c)^4+(c-a)^4-2(a+b+c)^4=
-6(ab+bc+ca)(2a^2+2b^2+2c^2+ab+bc+ca)$

Consider the case $a=2,b=2,c=-1$. Then $(-3)^k+(-3)^k=2*3^k$
This forces k to be even. Now take $a=6,b=3,c=-2$. This gives
$3^k+5^k+(-8)^k=2*7^k$.
Since $8^6>2*7^6$,
$3^k+5^k+(-8)^k>2*7^k$ for all even $k>4$.
By previous arguments, we must have $f(x)=dx^4+ex^2$

This problem becomes very simple once we get rid of all the dependencies (after milking them for all they're worth):

$a=b=c=0: f(0)=0$
$b=c=0: f(a) = f(-a)$ for all $a$.  Therefore, all of $f$'s exponents have even degree.  Then making the substitutions $x=a-b, y=b-c, z=c-a, w=a+b+c$ (so that $x+y+z=0$), the given condition becomes $2w^2 = x^2+y^2+z^2$.  Therefore, the original problem is completely equivalent to finding all even polynomials $f$ with $f(0) = 0$ satisfying the functional equation

$f(x)+f(y)+f(x+y) = 2f(\sqrt{x^2+xy+y^2})$ for all $x,y \in R$.

Suppose $deg f = 2n$.  Equating terms of degree $2n$, we find that

$x^{2n} + y^{2n} + (x+y)^{2n} = 2(x^2+xy+y^2)^n$ or letting $y=tx$, $1+t^{2n}+(1+t)^{2n} = 2(1+t+t^2)^n$.

Assume that $n \geq 3$.  Then the root $\omega = \frac{-1+\sqrt{3} i}{2}$ appears with multiplicity at least $3$ on the $RHS$, and hence on the $LHS$ as well.
However, letting $g(t)=LHS$, $0=g''(\omega) =  2n(2n-1)(\omega^{2n-2}+(1+w)^{2n-2}) = 2n(2n-1)(\omega^{2n-2}+(-\omega^2)^{2n-2}) = 2n(2n-1)\omega^{2n-2}(1+w^{2n-2}) \not= 0$, a contradiction.

It follows that $deg f \leq 4$ so that $f(x) = kx^4 + lx^2$ (since $f(0)=0$) for $k,l \in R$ are the only possibly solutions.  A quick check shows that these solutions are indeed valid.

The fact that I found this problem simple supports your opinions, namely that this problem is relatively simple.
However, I disagree that this problem is ugly.  I think the concepts behind it are reasonably nice, and appropriate.  But then again, this is all a matter of perspective.  If you, Darij, spent 2 pages tediously computing this answer, I understand why you're bitter.  But it's really not that tedious, if you check things the right way.  When you reduce this to 2 variables instead of 3, it's very simple to check manually (or doing a root check the way I did above...the above method (with slightly more explanation) shows necessity AND sufficiency).
Finally, I'm not sure how they mark these, but wouldn't you be safe just saying that "plugging this back into the functional equation, we find that these solutions indeed satisfy it"?  That way, you avoid the hassle of computing the thing over 2 pages, saving lots of time and effort.

~Mike

If a=b=c you get f(0)=0. With a=b=0 we get f(c)=f(-c), then f(x)=P(x^2) for some P(x).(P(0)=0). Then put x=a-b=b-c (you can easy check that the system have real solution for infinite values of x) then the identity becames 2P(x^2)+P(4x^2)=2P(3x^2)..... looking at the leading coefficient we find that 2+4^n=2*3^n. But 4^n>2*3^n  for n>2 hence f(x)= ax^2+bx^4 as we want.

A much less elegant solution  :(  :( :
(1) we have f(0)=0, f is even by trivial substituions
(2) Define g(x1,x2,k), where x1,x2 are reals and k is an even integer:
g(x1,x2,k) = (x1-x2)^k + (x2+x3)^k + (x1+x3)^k - (x1+x2-x3)^k,
where x3 = - (x1*x2)/(x1 + x2).
since f is even, let the coefficients of x^2,x^4 ... x^(2n) be a(2),a(4) ... a(2n).
it follows from the given condition that, for all reals x1,x2:
sum, from k=1 to n of a(2k)*g(x1,x2,2k)  = 0  ... (*)
now g(x1,-3*x1,2k) = x1^2k ( 4^(2k) + (3/2)^(2k) + (5/2)^(2k) - 2*(7/2)^2k) (where x1 is not 0). now after some computations we have
b(2k) = 4^2k + (3/2)^2k + (5/2)^2k - 2*(7/2)^2k
is strictly positive for k>2, and zero for k=1,2. (for k=1,2 we just verify. for k>=3,
8^k > 2*7^k)
using that in (*), and setting for convenience c(2k)=b(2k)*a(2k),
sum of, from k=3 to n, x^(2k) * c(2k) = 0 for all x.
this implies c(2k) = 0 for all k>3, and since b(2k) is non-zero for thos values, a(2k)=0 for all k>3 -- > f is of the form a*x^2 + b*x^4. now we verify that it works ...
i totally agree that this problem isn't a very good IMO problem, despite some of the nicer solutions that it does have. It doesn't really use any clever ideas at all, and is a bit too simple for q2/5 level problems.

Indeed my solution was quite similar to all of your ones.

[quote="Michael Lipnowski"]Finally, I'm not sure how they mark these, but wouldn't you be safe just saying that "plugging this back into the functional equation, we find that these solutions indeed satisfy it"?  That way, you avoid the hassle of computing the thing over 2 pages, saving lots of time and effort.[/quote]

Well, maybe they wouldn't like this... the calculation is really heavy if you do not have the right idea, so I think one would lose some points with this.

  darij

Anyway, a really cool solution is the following: just take instead of a,b,c the numbers 6x, 3x, -2x. Then identify the coefficients and you will find a simple exponential equation. That's all!

It is really nice and natural idea. In sln of jmery it was mentioned in other form. I think it is shortest way to find that $degf \le 4$. The rest is so trivial.

Namdung

[hide=Sketch]Let $Q(a,b,c)$ denote the assertion of the polynomial equation. Note that $Q(0,0,0)$ gives $P(0)=0$ and $Q(a,0,0)$ gives $P(a)=P(-a)$, so $P$ is even. Then, set $P(x) = a_{2n}x^{2n} + a_{2n-2}x^{2n-2} + \cdots + a_2x^2 + a_0$. Taking $Q(3,6,-2)$ gives $P(x) = cx^4 + dx^2$ as the only solution, which clearly works.[/hide]

Observe that if $P(x)$ and $Q(x)$ are solutions, then $aP(x) +bP(x)$ are solutions for any $a, b \in \mathbb R$. Furthermore, it is easy to see that $P$ must be even.

Letting $a=-2x, b = 3x, c = 6x$, we must have $$\sum_{n \geq 0} a_n((-5x)^n + (-3x)^n + (8x)^n)= \sum_{n \geq 0} a_n(2 \cdot (7x)^n).$$ Observe that $8^7-3^7-5^7 > 2 \cdot 7^7$, so by comparing the leading coefficients, we must have $\deg P = 2$ or $\deg P = 4$. Thus, $P(x) = mx^4+nx^2$ for any $m, n \in \mathbb R$ are the solutions, which indeed work.

@below this seems to be fixed by considering $(-2x, 3x, 6x)$ in general instead of specific values.

[hide=@above]
How do you know something like $x^8+x^6$ can't be a solution?

It's $P(x)$ instead of $f(x)$ in OTIS, but same thing
[hide=Solution]
The answer is $P(x) = \boxed{px^4+qx^2}$ for real numbers $p, q$.

To show that these work, note that if $P$ works, then $cP$ works for any real number $c$, and if $P, Q$ work, then $P+Q$ work as well, so it suffices to show that $x^4$ works, and that $x^2$ works. To see that $x^4$ works, note that for any real numbers $a, b, c$ with $ab+bc+ca = 0$, we have that if $r = a+b+c, s = abc$, that
\begin{align*}
    (a-b)^4 + (b-c)^4 + (c-a)^4 &= 2(a^4+b^4+c^4) - 4(a^3(b+c) + b^3(c+a) + c^3(a+b)) \\ &+ 6(a^2b^2+b^2c^2+c^2a^2) \\
                                &= 2(a^4+b^4+c^4) - 4(a^3(p-a) + b^3(p-b) + c^3(p-c)) \\ &+ 6((ab+bc+ca)^2 - 2(abc)(a+b+c)) \\
                                &= 6(a^4+b^4+c^4) - 4p(a^3+b^3+c^3) -12(abc)(a+b+c) \\
                                &= 6(p(a^3+b^3+c^3)+pr) - 4p(p^3 + 3r) - 12pr \\
                                &= 6(p(p^3 + 3r) + pr) - 4p(p^3+3r) - 12pr \\
                                &= 6(p^4 + 4pr) - 4p(p^3+3r) - 12pr \\
                                &= 2p^4 \\
                                &= 2(a+b+c)^4,
\end{align*}
where we use Newton's sums a bunch of times. To see that $x^2$ works, note that for any real numbers $a, b, c$ with $ab+bc+ca = 0$,
\begin{align*}
    (a-b)^2 + (b-c)^2 + (c-a)^2 &= 2(a^2+b^2+c^2 - ab-bc-ca) \\
                                &= 2(a^2+b^2+c^2 + 2ab+2bc+2ca) \\
                                &= 2(a+b+c)^2.
\end{align*}
Thus, $x^4$ and $x^2$ works, so $px^4$ works for any real number $p$, and $qx^2$ works for any real number $q$, so $px^4+qx^2$ works for any real numbers $p, q$.

Now, we show that these are the only such solutions.

Let $Q(x, y, z)$ denote the assertion. Note that $0\cdot 0 + 0\cdot 0 + 0 \cdot 0 = 0$, so $$Q(0, 0, 0)\implies 3P(0) = 2P(0) \implies P(0) = 0.$$ Then, for any real number $a$, $$\left(\frac{2}{3}a\right)\left(\frac{2}{3}a\right) + \left(\frac{2}{3}a\right)\left(\frac{-a}{3}\right) + \left(\frac{-a}{3}\right)\left(\frac{2}{3}a\right) = \frac{4}{9}a^2 - \frac{2}{9}a^2 - \frac{2}{9}a^2 = 0,$$ so we have that $$Q\left(\frac{2}{3}a, \frac{2}{3}a, -\frac{a}{3}\right) \implies P\left(\frac{2}{3}a - \frac{2}{3}a\right) + P\left(\frac{2}{3}a + \frac{a}{3}\right) + P\left(-\frac{a}{3} - \frac{2}{3}a\right) = 2P\left(\frac{2}{3}a + \frac{2}{3}a - \frac{a}{3}\right),$$ i.e. $$P(a) + P(-a) + P(0) = 2P(a),$$ so since $P(0) = 0$, $$P(a) + P(-a) = 2P(a),$$ so $$P(a) = P(-a).$$ Thus, $P$ is even. The significance of this is that all terms in the expansion of $P$ are of the form $ax^{2d}$ for some nonnegative integer $d$.

Now, assume for the sake of contradiction that $\deg P  > 4$. Then, since $P$ is even, $\deg P \geq 6$, so $\deg P = 2d$ for some $d\geq 3$. Now, note that for any real number $k$, $$(3k)(6k) + (6k)(-2k) + (-2k)(3k) = 18k^2 - 12k^2 - 6k^2 = 0,$$ so $$Q(3k, 6k, -2k) \implies P(-3k) + P(8k) + P(-5k) = 2P(7k).$$ The cofficient of $k^{2d}$ on the LHS is $3^{2d} + 8^{2d} + 5^{2d}$, whilst the coefficient of $k^{2d}$ on the RHS is $2\cdot 7^{2d}$. Thus, we have that $$3^{2d} + 8^{2d} + 5^{2d} = 2\cdot 7^{2d}.$$ Thus, $$\left(\frac{8}{7}\right)^{2d} + \left(\frac{5}{7}\right)^{2d} + \left(\frac{3}{7}\right)^{2d} = 2.$$ Now, note that since $d\geq 3$, we have that
\begin{align*}
     2 &= \left(\frac{8}{7}\right)^{2d} + \left(\frac{5}{7}\right)^{2d} + \left(\frac{3}{7}\right)^{2d} \\ &> \left(\frac{8}{7}\right)^{2d} \\ &\geq \left(\frac{8}{7}\right)^6 \\ &= \left(1 + \frac{1}{7}\right)^6 \\ &> 1 + \frac{1}{7}\cdot 6 + \frac{1}{7^2}\cdot \binom{6}{2} \\ &= 1 + \frac{6}{7} + \frac{15}{49} \\ &= \frac{106}{49} \\ &> 2,
\end{align*}
a contradiction. Thus, $\deg P \leq 4$.

Thus, since $\deg P \leq 4$, and $P$ is even, we have that $P(x) = px^4+qx^2+r$ for real numbers $p, q, r$ (not necessarily nonzero). Now, since $P(0) = 0$, we have that $r = 0$, so $P(x) = px^4+qx^2$ for real numbers $p, q$, as desired.

Thus, we have shown that $P$ must be of this form and that all $P$ of this form work, so we're done. $\blacksquare$

We claim the answer is $f(x) = mx^4 + nx^2$ for any reals $m, n$. First, we will show that these work. Note that if $p(x)$ and $q(x)$ are two polynomials satisfying the given equation, then $\alpha p(x) + \beta q(x)$ is also a solution for any reals $\alpha, \beta$. Therefore, it suffices to show that $x^2$ and $x^4$ work. Starting with $x^2$, we see that
$$\begin{aligned} (a - b)^2 + (b - c)^2 + (c - a)^2 &= 2(a^2 + b^2 + c^2) - 2(ab + bc + ca) \\ &= 2(a^2 + b^2 + c^2 + 2(ab + bc + ca)) \\ &= 2(a + b + c)^2. \end{aligned}$$
To see why $x^4$ works, note that
$$\begin{aligned} (a - b)^4 + (b - c)^4 + (c - a)^4 &= 2(a^4 + b^4 + c^4) - 4\sum_{\text{sym}}a^3b + 6\sum_{\text{cyc}} a^2b^2 \\ &= 2(a^4 + b^4 + c^4) - 4\sum_{\text{sym}}a^3b + 6\sum_{\text{cyc}}a^2b^2 - 2(ab + bc + ca)(ab + bc + ca - 2(a^2 + b^2 + c^2)) \\ &= 2(a^4 + b^4 + c^4 + 2(a^2b^2 + b^2c^2 + c^2a^2)) \\ &= 2(a^2 + b^2 + c^2)^2 \\ &= 2(a^2 + b^2 + c^2 + 2(ab + bc + ca))^2 \\ &= 2(a + b + c)^4. \end{aligned} $$
To see that no other solutions work, let $P(a, b, c)$ denote the original assertion. Then $P(0, 0, 0)$ gives $f(0) = 0$, and $P(x, 0, 0)$ gives $f(x) + f(-x) = 2f(x) \iff f(x) = -f(x)$, so $f$ only has terms of even degree. Now, let $n$ be the degree of $f$, and $a_n$ be the leading coefficient. Then from $P(-2, 3, 6)$, since $n$ is even we get
$$ \begin{aligned} a_n(3^n + 5^n  + 8^n) &= 2a_n(7^n) \\ \iff \left(\frac{3}{7}\right)^n + \left(\frac{5}{7}\right)^n + \left(\frac{8}{7}\right)^n &= 2 \end{aligned}$$
But for $n \ge 6$ we have $(\tfrac{8}{7})^n \ge 2$, so we must have $n = 2$ or $n = 4$. Since $f(0) = 0$, $f$ has no constant term, so the only solutions must be of the form $f(x) = mx^4 + nx^2$ for real $m, n$, as desired.

In OTIS where f(x) is P(x). Notice 0,0,0 yields P(0)=0, whence a,0,0 gives P(a)+P(-a)=2P(a), so P is even. 3x,6x,-2x gives P(-3x)+P(8x)+P(-5x)=2P(7x); It's obvious that for P having degree $2p\ge 6$, the coefficient of the largest degree on the right side is 3^p+8^p+5^p>2*7^p, a contradiction, so our only solutions are of the form P(x)=ax^4+bx^2+c, and checking we need c=0 while all the other coefficients match up. $\blacksquare$

Kinda disappointed this boiled down to guess and check, but okay.

We claim the only solutions are of the form $f(x) = mx^4 + nx^2$, which clearly work.

Let $Q(a, b, c)$ denote the assertion. Clearly $Q(0, 0, 0)$ gives $P(0) = 0$. Then from $Q(x, 0, 0)$ we see $P(x) = P(-x)$ implying $P$ is even. Thus $P$ can be written as $G(x^2) = P(x)$ for some polynomial $G(x)$.

Now we claim that all polynomials of the form $f(x) = mx^4 + nx^2$ work. It is [hide=easy] left as an excercise [/hide] to show that these work from just plugging.

Now we claim if $\text{deg}(P) > 6$ fails. To see this we consider the leading coefficients of the polynomial. Note that we want the following to fail,
\begin{align*}
    (a-b)^{2n} + \left(b + \frac{ab}{a+b}\right)^{2n} + \left(a + \frac{ab}{a+b}\right)^{2n} = 2\left(a + b - \frac{ab}{a+b}\right)^{2n}
\end{align*}
This is equivalent to showing that the leading coefficients of the following fail,
\begin{align*}
    (a^2 - b^2)^{2n} + \left(2ab + b^2 \right)^{2n} + \left(2ab + a^2 \right)^{2n} = 2\left(a^2 + b^2 + ab\right)^{2n}
\end{align*}
Setting $a = 2x$ and $b = x$ we see we need,
\begin{align*}
    (3x)^{2n} + (5x)^{2n} + (8x)^{2n} = 2 \cdot (7x)^{2n}
\end{align*}
However it is easy to see the LHS is much greater than the RHS for $n \geq 3$, so it is impossible for this equation to hold. Thus we are done.

Notice $(a,b,c)=(0,0,0)$ gives $P(0)=0$ so then we can plug in $(a,b,c)=(x,0,0)$ to get that $P$ is even.

Set $P(x) = a_{2n}x^{2n} + a_{2n-2}x^{2n-2} + \cdots + a_2x^2 + a_0$. Taking $(a,b,c) = (3x,6x,-2x)$ gives $\deg P <6$. Solving, we get $\boxed{P(x)=cx^4+dx^2, \ c,d \in \mathbb{R}}$.

Taking $a=b=c=0$ we find that $P(0) = 0$.
Taking $a=b=0$ we find that $P(-c) = P(c)$, so $P$ must be even.

Now, let $a = -2k$, $b = 3k$ and $c = 6k$.
Clearly this satisfies $ab+bc+ca=0$, and we obtain
\[ P(5k) + P(3k) + P(8k) = 2P(7k) \]
Now, suppose that $P(x)$ has degree $n$. Then we obtain
\[ 5^n + 3^n + 8^n = 2\cdot 7^n \]
From Bernoulli we see that $\frac{8^7}{7^7} \geq 2$. Thus, $n \leq 7$. Taking modulo 6, we see that $n \neq 6$.
Therefore, the maximal degree is $4$, as $n$ must be even.

Then, we find that $P(x) = k_1x^4 + k_2x^2$ for some reals $k_1$ and $k_2$. To see how $x^4$ works, note that
\[ (a-b)^4 + (b-c)^4 + (c-a)^4 - 2(a+b+c)^4 = -6(ab+bc+ca)(ab+bc+ca+a^2+b^2+c^2) \]
and $x^2$ works as
\[ (a-b)^2 + (b-c)^2 + (c-a)^2 - 2(a+b+c)^2 = -6(ab+bc+ca) \]
so indeed all polynomials of that form work. $\blacksquare$

Let our polynomial be of the form $P(x)=a_n \cdot x^n+a_{n-1} \cdot x^{n-1}+...+a_1\cdot x+a_0$. Let's play with the coefficients of the polynomial, that is, if there is some $c_i*A$ on the left in the expression, where say $A$ is an expression of $a,b,c$, then we should have the same thing on the right.

Let's look at how the coefficient $a_0$ behaves: $$a_0+a_0+a_0=2a_0,$$ $$\Rightarrow \a_0=0.$$

Let's see how $a_1$ behaves: $$a_1((a-b)+(b-c)+(c-a))=2a_1(a+b+c),$$ $$\Rightarrow 0=a_1(a+b+c).$$

$a+b+c$ is not always $0$, so $a_1=0$.

And how $a_2$ behaves: $$a_2((a-b)^2+(b-c)^2+(c-a)^2)=2a_2(a+b+c)^2,$$ $$\Rightarrow a_2(2a^2+2b^2+2c^2)=a_2(2a^2+2b^2+2c^2).$$

Everything works, so we can say that $a_2$ can essentially be anything, and we leave it that way.
Of course, I would like to work with $a_3$ further, but I'm so lazy, a lot of numbers appear with it, and something tells me that equality does not always happen, I thought. Then, it would be worthwhile to come up with some universal values for $a,b,c$ so that the condition $ab+bc+ac=0$ would be satisfied at the same time, and so that the coefficients could be conveniently estimated.

The equality of the coefficient $a_i$ looks like this: $$a_i((a-b)^i+(b-c)^i+(c-a)^i)=2a_i(a+b+c)^i.$$ It is very inconvenient to disclose this whole thing with large values of $i$, then let's find convenient values for $a,b,c.$ Then, let's look at $(a-b)$, I thought it would be quite convenient if $a=b+1$ and the value would be identical to $1$ for any $i$. With the same logic, I made it so that $c=b+2$, then let's see what happens to $ab+bc+ac$:

$$b(b+1)+b(b+2)+(b+1)(b+2)=0,$$
$$3b^2+6b+2=0,$$
$$ \Rightarrow b_1=\frac{1}{\sqrt{3}}-1, \ b_2=-\frac{1}{\sqrt{3}}-1.$$
We get two roots, I see that the first one is more convenient and I take it. Let's look at our coefficient $a_i$ under these values: $$a_i((\frac{1}{\sqrt{3}}-(\frac{1}{\sqrt{3}}-1))^i+((\frac{1}{\sqrt{3}}-1)-(\frac{1}{\sqrt{3}}+1))^i+((\frac{1}{\sqrt{3}}+1)-\frac{1}{\sqrt{3}})^i)=2a_i(\sqrt{3})^i,$$ $$\Rightarrow a_i((-2)^i+2)=2a_i(\sqrt{3})^i.$$
Let's say $a_i$ is not $0$, then $(-2)^i+2=2(\sqrt{3})^i.$ With $i\geq 3$ and odd, the two sides will have different signs, and with $i\geq 6$ and $i$ even, the growth will be faster on the left than on the right (it can be proved by induction that there will always be more on the left with $i\geq 6$.) Works for $i=2.4$, but this does not mean that this will always be the case. If $i=2$ we have checked. Check $i=4$, use the facts that $(a+b+c)^2=a^2+b^2+c^2$, $(ab+bc+ac)^2=0,$ $(a^2+b^2+c^2)(ab+bc+ac)=0$ and make sure that the equality is identical.

Accordingly, any coefficient except $a_4$ and $a_2$ must be zero, and these two can take any value.

[b]Answer:[/b] $\boxed{P(x)=a_4\cdot x^4+a_2 \cdot x^2.}$

$P \equiv kx^4 + lx^2$ works where $k$, $l\in \mathbb R$.

Let $Q(a,b,c)$ denote the assertion $P(a-b)+P(b-c)+P(c-a) = 2P(a+b+c)$.

$Q(0,0,0)\implies P(0) = 0$.

\begin{align*}
    Q\left(c,c,-\frac{c}{2}\right) &\implies P(0) + P\left(\frac{3c}{2}\right) + P\left(\frac{-3c}{2}\right) = 2 P\left(\frac{3c}{2}\right)\\
    &\implies P\left(\frac{-3c}{2}\right)=P\left(\frac{3c}{2}\right)\\
    &\implies P(-x) = P(x)\\
    &\implies P(x) \text{ is even}
.\end{align*}

All the terms are of even degree.

$P(x) = a_nx^{2n} + \cdots + a_1x^2 + a_0x^0$. So $P(0) = 0 \implies a_0 = 0$.

Now $Q\left(\frac{-c}{3},\frac{c}{2},c\right) \implies P\left(\frac{-5c}{6}\right) + P\left(\frac{-c}{2}\right) + P\left(\frac{4c}{3}\right) = 2P\left(\frac{7c}{6}\right)$.

So, we have,
\[  P\left(\frac{5c}{6}\right) + P\left(\frac{c}{2}\right) + P\left(\frac{4c}{3}\right) = 2P\left(\frac{7c}{6}\right). \]

Now comparing the coefficients of the $c^{2i}$ term, we get that,
\[ a_i\left(\frac{5}{6}\right)^{2i} + a_i\left(\frac{1}{2}\right)^{2i} + a_i\left(\frac{4}{3}\right)^{2i} = 2\left(\frac{7}{6}\right)^{2i}. \]
$\implies a_i(5^{2i} + 3^{2i} + 8^{2i}) = a_i(2\cdot 7^2i)$.

If $a_i\neq 0$, then $25^i + 9^i + 64^i = 2\cdot 49^i$. Now note that $64^i > 2\cdot 49^i$ for all $i\ge 3$.

Thus we must have $i\le 2$. Checking gives that $i=1$ and $2$ both work. So we get our desired form and we are done. :yoda:

We claim our solutions are of the form $\boxed{P(x)=px^4+qx^2, \quad p,q \in \mathbb{R}}$, which can be tested to work. Denote the assertion as $A(a,b,c)$. Then
\begin{align*}
A(0,0,0) &\implies P(0)=0 \\
A(a,0,0) &\implies P(a)=P(-a) \implies P \text{ even.} \\
A(1, 1-\sqrt 3, 1+\sqrt 3) &\implies (\sqrt 3)^{2k} + (-2\sqrt 3)^{2k} + (\sqrt 3)^{2k} = 2 \cdot 3^{2k} \\
&\implies 4^k+2 = 2 \cdot 3^k \\
&\implies k=1,2.
\end{align*}

Hence the only possible degrees of nonzero terms of $P$ are 2 and 4, as desired. $\blacksquare$

We claim that the answer is $P(x)=rx^4+sx^2$ for any real number $r,s$, which clearly works.\\

By plugging $a=b=c=0$, we find that $P(0)=0$. Then, plugging $b=c=0$, we have that $P$ is even.\\

We would like to cancel the right side by setting $a+b+c=0$, but this isn't possible since $a+b+c=0,ab+ac+bc=0$ implies $a=b=c=0$ over reals. The next best thing would be to consolidate terms of the left hand side: $$a-b=b-c$$ $$c=2b-a.$$ Plugging $c=2b-a$ gives us that $$2P(a-b)+P(2b-2a)=2P(3b).$$ However, we also have $$ab+ac+bc=0$$ $$ab+(2b-a)(a+b)=0$$ $$a^2-2ab-2b^2=0$$ $$a=b(1\pm \sqrt{3}).$$ We will only use $a=b(1+\sqrt{3}),$ which when plugged into $$2P(a-b)+P(2b-2a)=2P(3b),$$ we get $$2P(b\sqrt{3})+P(-2b\sqrt{3})=2P(3b).$$ We will equate coefficients of $b^{2n}$ on both sides, noting that $P$ is even. If the coefficient of $x^{2n}$ in $P$ is $a_2n$, then we have $$a_{2n}(2\cdot 3^n+12^n)=a_{2n}(2\cdot 9^n).$$ Thus, or each nonnegative integer $n$, either $$a_{2n}=0$$ or $$2\cdot 3^n+12^n=2\cdot 9^n.$$ This is only true for $n=1$ and $n=2$, as we can test that $n=0$ doesn't work, and $12^n>2\cdot 9^n$ for $n\geq 3.$ Thus, only the $x^2$ and $x^4$ coefficients are allowed to be nonzero, thus done.

[b][color=#f00]remark: [/color][/b] The main idea here is to make a substitution that, combined with the constraint of $ab+ac+bc=0$, makes it so that all terms are of the form $$kP(rb).$$ This is very nice because this means that the $x^n$ coefficent of this only depends on the $x^n$ coefficient of $P$, allowing us to easily equate coefficients. By only setting "homogeneous" constraints, like $a-b=b-c$ that I used, one can prevent the input of the polynomial from having a constant shift. In fact, $$(a,b,c)=(b(1+\sqrt{3}),b,b(1-\sqrt{3}))$$ is really the only substitution you need to solve this problem.

[quote=Cusofay]We can check that $P(x)=mx^4+nx^2$ for real numbers $m,n$ works and we want to prove its uniqueness.
Note that if $P$ and $Q$ are solutions, $aP+bQ$ is a solution for all real numbers $a,b$ so it's enough to find all solutions of the form $x^n$.$P(0,0,0)$ and $P(0,0,x)$ gives us that $n$ is even

$$P(6,3,-2) \Rightarrow 3^n+5^n+(-8)^n=2 \cdot 7^n$$

If $n=0$, then this obviously doesn't hold.

 If $n=2$, then $9+25+64= 98 =2 \cdot 49$, which works.

If $n=4$, then $81+625+4096 = 4802 = 2 \cdot 2401 $, which also works.

If $n=6$, then $$3^6+5^6+8^6>8^6=(7+1)^6=7^6+\frac{6}{7} \cdot 7^6 + \frac{15}{49} \cdot 7^6 = (2+\frac{8}{49}) \cdot 7^6>2 \cdot 7^6,$$ which is a contradiction.

If $n \ge 8$, then $$3^n+5^n+8^n>8^n=(7+1)^n>7^n+n \cdot 7^{n-1} > 2 \cdot 7^n,$$ contradiction.

$$\mathbb{Q.E.D.}$$[/quote]

unfortunately, the linear combination of any two solutions also being a solution does not necessarily imply that checking $x^n$ suffices

for example, if hypothetically the solution set is $r(x+1)$ for real numbers $r$, then it is true that the linear combination of any two solutions is still a solution, but in this case there are no solutions of the form $x^n$ even though there does exist solutions.

the issue here is that $1,x,x^2,\dots$ is not the only basis for real polynomials, and there are plenty of other choices, so closure under addition like this does not imply that only checking these suffices

it's ok though :D I wish you good luck in the future!


geometry
3D geometry
sphere
tetrahedron
pyramid
Pythagorean Theorem

Three spherical melons, radius 9 cm each, are placed on a flat table, each touching both the others. What is the radius of the largest orange that will sit on the table in the space between the 3 melons?

Can someone give a reasonably good explanation on how to do this?

[hide="My answer"]
Using Pic:

Draw an altititude (red line from the center of one sphere tangent to the other two.
Using Pythag. Th. or 30-60-90 triangle trick we see the altitude is $9 \sqrt{3}$ then we see that in the problem, the orange must be equidistant from all angles thus, it is $\frac 23$ from each angle and so the distance from one center to the center of the orange (green dot) is $6 \sqrt{3}$. Subtracting the radius of the melon we find the radius of the orange must be: $r = 6 \sqrt{3} - 9$

[/hide]

Yeah, that's pretty much how I did it.  Except, I used the fact that the center of the orange will be the centroid of the triangle, because then you can do it for any triangle...

Doesn't the sphere have to also be tangent to the table?

(Also, I'm moving this to intermediate, as it's a touch hard for getting started.)

Which sphere, the orange?  That shouldn't matter.  It can slide down to touch the table as long as it fits between all of them at their widest point, when they are closest together, and our solution found the largest the orange can be and fit between them at that point...

The oranges being tagent to the table is irrelevent, JavaMAn added this dimension unecessarilly. Though some could debate the answer is even less than mine sue to the outer bulge of the melon.

I don't think so.  What you and I did lets the orange fit between the melons at any point, which is what the question asks...

So that actually makes the answer larger, because it doesn't need to fit through the space we were making it...

Nice.  You end up using tetrahedrons a lot in 3-D geometry, don't you?

Yeah, you do..but they generally can be simplified to triangles...as in this example
If the melons were different sizes, you'd actually have to do the 3-D geometry.

Yeah.  I actually solved a problem similar to this the other day in almost the same exact method you used on this one...

[quote="K81o7"]...[hide="What I think Javaman intended..."]
The orange has to be tangent to the table at the same time as it is to the melons.
If you draw a view from the side, and only look at one melon and the orange, you know that the centroid of the triangle formed by the center of the melons has to be directly above the center of the orange.  Let the radius of the orange be $r$.  The distance from one melon's center to the centroid of the triangle is $6\sqrt{3}$.  The center of the orange is $9-r$ below the centroid of the triangle, being $r$ above the table.  The distance between the center of a melon and the center of the orange is $9+r$.  So by the pythagorean Theorem, we have \[ (9+r)^2=(9-r)^2+(6\sqrt{3})^2 \implies 18r=108 \implies \boxed{r=6}  \][/hide]

Fireforce, the problem with your solution is that you assume that the center of the orange is in the same plane as the three melon centers.  If it were, then it would not touch the table unless its radius wer also $9$.
The orange with the radius of $6$ fits in the little cave-like area formed under the melons, and is tangent to all three melons and the table at the same time.

I can attach some diagrams if needed...or real life pictures...[/quote]

Thanks, that was helpful. Must've made a small error as 36r = 108. r = 3.

[quote="K81o7"]...[hide="What I think Javaman intended..."]
The orange has to be tangent to the table at the same time as it is to the melons.
If you draw a view from the side, and only look at one melon and the orange, you know that the centroid of the triangle formed by the center of the melons has to be directly above the center of the orange.  Let the radius of the orange be $r$.  The distance from one melon's center to the centroid of the triangle is $6\sqrt{3}$.  The center of the orange is $9-r$ below the centroid of the triangle, being $r$ above the table.  The distance between the center of a melon and the center of the orange is $9+r$.  So by the pythagorean Theorem, we have \[ (9+r)^2=(9-r)^2+(6\sqrt{3})^2 \implies 18r=108 \implies \boxed{r=6}  \][/hide]

Fireforce, the problem with your solution is that you assume that the center of the orange is in the same plane as the three melon centers.  If it were, then it would not touch the table unless its radius wer also $9$.
The orange with the radius of $6$ fits in the little cave-like area formed under the melons, and is tangent to all three melons and the table at the same time.

I can attach some diagrams if needed...or real life pictures...[/quote]
Are you sure that isn't $r=3$?

Edit: Disregard, I didn't see the other post.

It is.  Mistakes like these (and simpler) kill me on every math contest.

Yeah, they kill me too. Anyone know any reasonable methods to reduce these 'stupid' mistakes?

Is there a formula for finding the volume of a sphere inside a regular pyramid?

BTW:
You do stupid mistakes only when you are nervious. Here are some of my ways (they may look odd) the chance of making dumb mistakes:

1)Pracrice by taking a lot of tests is the bggest mistake reducer but heres some of my tricks.

2)At competitions, take deep breaths btw questions (it is possible u just have to take fast deep breaths :) )

3)Don't try to speed read every problem, take time to read medium sized word problems. Most people miss words and trip up.

4)Drink lots of fluids, have a good breakast/dinner, etc.

5)Relax.  ;)

I can't eat when i'm nervous, and does eating really make that big a deal  :?


linear algebra
matrix
algorithm
algebra
polynomial
linear algebra theorems

Can someone give me an explicit proof of the theorem stating that a linear operator can be decomposed as the direct sum of a diagonal and a nilpotent operator?

At first, this statement is valid only in finite-dimensional spaces.

Now, if the space is finite-dimensional there is a standard theorem of linear algebra, which sais that for a given operator $ T$ there is a basis $ (e_n)$ such that the matrix $ A$ of operator is triangular (i.e. all the elements of matrix above the diagonal are zeros). Now decompose this matrix into sum $ A \equal{} B\plus{}C$ with $ B$ being diagonal (with the same diagonal as $ A$) and $ C$ being triangular with zeros on the diagonal. This $ C$ is nilpotent.

Is this proof sufficiently explicit? In my opinion it is, because the triangular representation theorem is explicit and there is an algorithm how one can construct the corresponding basis $ (e_n)$ starting from eigenvectors, then passing to their non-trivial preimages (if they exist), then to preimages of preimages, etc.

volodya's proof has a flaw: he is assuming the existence of eigenvalues. That is, he's assuming that the characteristic polynomial of $ T$ splits over the field in question. But if you're working over a field that isn't algebraically complete, then you can't use this proof.

For instance, consider $ \begin{bmatrix}0 & \minus{} 1 \\
1 & 0\end{bmatrix}$ as a matrix over $ \mathbb{R}.$

This matrix has no real eigenvalues, so we cannot apply volodya's proof to it. But is it the sum of a diagonal and a nilpotent matrix? Well, yes it is.
\[ \begin{bmatrix}0 & \minus{} 1 \\
1 & 0\end{bmatrix} \equal{} \begin{bmatrix} \minus{} 1 & \minus{} 1 \\
1 & 1\end{bmatrix} \plus{} \begin{bmatrix}1 & 0 \\
0 & \minus{} 1\end{bmatrix}\]
So there is still more to be said here.

One more comment: what if you do have eigenvalues? volodya seems to be talking about Jordan canonical form - at least that's how I read the last paragraph of his post. That's overkill; Schur's Lemma suffices. That is, assuming the existence of all eigenvalues, any square matrix is similar to an upper triangular matrix.

Kent Merryfield has right: since the field was not specified I assumed that the linear space is over the field of complex numbers. The reason is evident: I live in a complex reality  :wink:


[quote="tchebytchev"]let $f : R\to R*$  satify : $f(x+2)=f(x-1)f(x+5)$.
prove that $f$ is a period function.[/quote]

I think I found a solution .Tell me if it is correct.
From the given relation we have that  $f(x+5)=f(x+2)f(x+8)$

So $f(x+2)=f(x+2)f(x+8)f(x-1)$  and because  f is not 0 we have that

$f(x)f(x+9)=1$ .From this  $f(x+9)f(x+18)=1$  so

$f(x)f(x+9)=f(x+9)f(x+18)$  so  $f(x)=f(x+18)$  as f is not  0

I show more funtion that period, too
$f: R\rightarrow R$ that satified condition: $f(x)=f(x-3)f(x+3)$

another similar problem:
Let $f: R\rightarrow R$ satifies: Exist a number $a>0$ such that:
$f(x+a)=\frac{1}{2}+\sqrt{f(x)-f^2(x)}$

I think it is similar to problem from Malaysia MO1999

Can you show an example about such function that satified condition above


This is $ 2^{1003.5}\left(\cos-\frac{\pi}{4}+i\sin-\frac{\pi}{4}\right)$.  You could re-write this as $ 2^{1003.5}e^{-\frac{i\pi}{4}}$ if you wanted, or you could just evaluate those sines and cosines.  In that case,
$ 2^{1003.5}\left(\frac{\sqrt{2}}{2}-i\frac{\sqrt{2}}{2}\right)=2^{1003}(1-i)$

cool....
btw, how to use DeMoivre's theorem to get the roots of x^3+1=0 and x^5-1=0?

See [url=http://en.wikipedia.org/wiki/De_Moivre's_formula]here[/url] and [url=http://en.wikipedia.org/wiki/Root_of_unity]here[/url].

More specifically, let $ z \equal{} re^{ix}$. Then the solutions to $ z^n \equal{} 1$ are the same as the solutions to $ r^ne^{inx} \equal{} 1$. You want $ inx$ to be zero, so $ r$ must be 1. So then you just solve for $ x$. (Hint: $ x$ is not just 0.)

This might be more clear by letting $ e^{inx}\equal{}\cos nx \plus{} i\sin nx$.

For $ x^5 \minus{} 1 \equal{} 0$, we have $ x^5 \equal{} 1$. Now, let's let $ z^5 \equal{} 1$ so that $ z \equal{} re^{ix}$. Then we have
\[ r^5e^{5ix} \equal{} e^{0}.
\]
Try to go from here. Remember that $ e^{ix}\equal{}e^{i\left(x\plus{}2\pi\right)}$.

Let $ z\equal{}re^{i\theta}$.  Then the $ m$th roots of $ z$ are given by
$ \xi\equal{}\sqrt[m]{r}e^{\frac{i\theta}{m}}\zeta^{k}$,
where $ \zeta$ is the $ m$th root of unity and $ k\equal{}0,\ldots,m\minus{}1$.


Let $\{ a_n\}_{n \ge 0}$ be a sequence of real numbers such that $a_{n+1} \ge a_n^2 + \frac{1}{5}$ for all $n \ge 0$. Prove that $\sqrt{a_{n+5}} \ge a_{n-5}^2$ for all $n \ge 5$.

This trivially follows from $a_{n+5}\geq a_n^2$ and $a_n\geq a_{n-5}^2$, what, in turn, follows from the inequality proved at http://www.mathlinks.ro/Forum/viewtopic.php?t=28048 .

  darij


calculus
integration
trigonometry
Euler
calculus computations

Evaluate $\int\frac{\sqrt{\cos 2x}}{\sin x}dx$

An outline of the solution:

Writing the integral as$\int\frac{sinx\sqrt(Cos2x)dx}_{sin^{2}x$  or $\int\frac{sinx\sqrt(2cos^{2}x-1)dx}_{1-cos^{2}x$ and using the substitution u=cosx ,du=-sinxdx we obtain the integral

$\int\frac{\sqrt(2u^{2}-1)du}_{u^{2}-1}$=$\int\frac{2u^{2}-1}_{(u^{2}-1)\sqrt(2u^{2}-1)$ , which becomes

$\int\frac{2}{\sqrt(2u^{2}-1)}$ +$\int\frac{1}{(u^{2}-1)(\sqrt(2u^{2}-1)}$ ,
after writing the numerator $2u^{2}-1$ as $2(u^{2}-1)+1$.

We are now left with the sum of two integrals each of which is of a standard type.The remaining calculations are routine and tedious.
The second integral can be calculated by a method due to Euler and there are  other ways as well. As I am a very slow typist I wont go into the details.
However I will post them if anyone wants to know.
Thanks to Prithwijit for this devlish collection of integrals!


[hide]Do all the coins in the bag have to weigh 11 grams each? If you were to divide the 10 bags into 2 piles, with 5 bags in each pile, you could combine the bags for each pile into one bag. You could then put both new bags on the scale, and the one that is heavier is the one with the coins that weigh 11 grams.  :)  :)  :)  :lol:  :P [/hide]

simpler one..

I think...

here..

make them two seperate piles..

put both sets of piles on the scale

5pile : 5pile
(one side has to heavier)
(since we have only one chance to weigh ...)

take out each piles at a time from both sides

4pile : 4pile
3pile : 3pile
......

The question is a little ambiguous: do you weigh one quantity versus another or do you get to weigh it on a scale which tells you its weight?

If it is the latter, then I have a sollution:
First label and empty the bags, making sure you keep organized what came from where.  Then put 1 coin from bag 1 onto the scale, 2 coins from bag 2 onto the scale, etc... 10 coins from bag 10 onto the scale.  The weight will have a digits number equal to the bag from which the coins came from.  If you wanted to remember which coins on the scale came from where, you could keep them in bags and empty some of the coins instead.

Here is a more fun problem if you haven't seen it before:

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

5 to 5
one will be heavier
than make it less by taking one off from two sides:
4:4
3:3
2:2
1:1
if you took one and it will not be balanced, than do the second.
if it is not balanced, the one in the side of heavier one will be the remaining.

sorry i forgot to add that it is a veryy veryy classic logic problem in turkey.

[quote="math92"]Ten bags each contain ten golden coins

Nine out of then bags contain coins weighing 10 grams each

the remaining bag contains coins of 11 grams each

you will be given [b]one[/b] chance to weigh to find the particular bag that the weighing 11 grams each.

how would you do this?[/quote]

Do most of you realize that $\textbf{one}$ is bolded?
I agree with Wumbate's solution. If you only have a balance that does not give a numerical weight, this cannot be done in one try.

there is one weighing and we're reducing bags from it.
we're not weighing it again


In how many different ways can 3 men and 4 women be placed into two groups of two people and one group of three people if there must be at least one man and one woman in each group?

Okay, obviously, the groups have to be MF, MF, and MFF.

There are $ 3$ possible men and $ 4$ possible women for the first group. ($ 3 \times 4 \equal{} 12$)

There are $ 2$ possible men and $ 3$ possible women for the second group. ($ 12 \times 2 \times 3 \equal{} 72$)

Thus, the answer is $ \boxed{72?}$.

Please post if I am wrong.

But shouldn't you also use combinations because the order of the people in the groups doesn't matter?

[quote=Mewto55555]You are indeed. You have to divide by 2! since the first "group" and seconds "group" of 2 are indistinguishabel. Thus the answer is 36.[/quote]

thanks

@above  Is this the only two posts u have?

I didn't know how to solve this so I just entered in a random answer on my second try. and got it wrong, but I dont care. can someone give me an understandable sol

yeah why do you multiply by 2 if the 2 remaining groups are indistinguishable?

Bruh I'm such an idiot! So I got the 72 part and then promptly said that the number of ways to arrange the groups, since two are the same, is 3, and did 72/3 = 24, got it wrong, and guessed on the second try. RIP good C&P rating.

[hide=Solution]The amount of ways to assign people into the groups of two is $3 \cdot 4 \cdot 2 \cdot 3$. Then we just put the remaining people into the other group and divide by $2$ since the same-sized groups are indistinguishable, giving $\boxed{36}$.[/hide]

how's this lvl 25? simple combinations so [hide=you get]$3*2*6 = 36$[/hide]

This problem is way overrated. How on earth is this supposed to be level $25$-
[hide=Solution]For the first group, you can choose $4$ men and $3$ women, which makes $12$ possibilities. For the second group, we have $3$ men left and $2$ women left, which makes $6$. Finally, the third group is already determined. $12\cdot6=72$, so we divide that by $2$ since groups of the same size are indistinguishable, to get $36$.[/hide]


If the base of a rectangle is increased by $ 10\%$ and the area is unchanged, then the altitude is decreased by:

$ \textbf{(A)}\ 9\% \qquad\textbf{(B)}\ 10\% \qquad\textbf{(C)}\ 11\% \qquad\textbf{(D)}\ 11\frac {1}{9}\% \qquad\textbf{(E)}\ 9\frac {1}{11}\%$

[hide="Click for solution"]
$ bh\equal{}\left (\frac{11}{10}b \right )(xh) \implies x\equal{}\frac{10}{11}$, so $ h$ is reduced by $ \frac{1}{11}$ or $ 9 \frac{1}{11} \%$ or $ \boxed{\textbf{(E)}}$.
[/hide]


Here is a problem that I couldn't understand its solution.
2n ambassadors are invited to a banquet. Every ambassador has at most n-1 enemies. Prove that the ambassadors can be seated around a round table,
so that nobody sits next to an enemy.
Solution: First, we seat the ambassadors in any way. Let H be the number of neighboring hostile couples. We must find an algorithm which reduces this number
whenever H > 0. Let (A, B) be a hostile couple with B sitting to the right of A.(Fig. 1.3). We must separate them so as to cause as little disturbance as possible.
This will be achieved if we reverse some arc BA' getting Fig. 1.4. H will be reduced if ( A, A' ) and ( B, B' ) are friendly couples ...

Let (B,C) and (A',C') are neighboring couples and let B is an enemy of C', A' is an enemy of C. And (B, C) ,(A',C') are friendly coupless. Then H won't be reduced.
Can somebody explain this ?

He said to invert the [i]whole arc[/i] BA'. Thus, after the inversion, all the points between B and A' will be changed, leading to this:

[code]
            B'
                  B
                        C

                        C'
                  A'
            A
[/code]


I just noticed there's a user named timwu225. I kind of suspect it's someone impersonating the user timwu?
Admins can this be investigated?

Alternately, it could be someone else named Tim Wu. That sounds like a common enough name.


Kαλησπερα σας και απο μενα! Οσον αφορα τις: α)συνεχεις, β)γνησιως μονοτονες, γ)"1-1" συναρτησεις.
Αν μια συναρτηση f πληροι ενα απο τα ζευγη α), β)    ή    β),γ)    ή    γ),α) μπορουμε να ισχυριστουμε οτι σιγουρα θα ισχυει και το γ) , α), β) αντιστοιχα ή αυτο είναι κατι οχι τοσο προφανες :maybe:  ?

Ευχαριστω!

Νομίζω πως δεν ισχύει η παρακάτω περίπτωση

αν β) και γ) τότε και η α)

Πάρε για παράδειγμα την συνάρτηση

$ f(x)\equal{}x, 0\leq x\leq1$
$ f(x)\equal{}x\plus{}1, 1<x\leq2$

Είναι γνησίως μονότονη και "1-1" αλλά δεν είναι συνεχείς

Οι άλλες δύο περιπτώσεις ισχύουν και είναι πολύ καλά θεωρήματα...

Ισχύει πάντα ότι μία γνήσια μονότονη συνάρτηση θα είναι και "1-1". Από αυτό βγάλε τις συνεπαγωγές που προκύπτουν.

Συνέχεια ως αποτέλεσμα μονοτονίας ή "1-1", όχι.

Για την τελευταία συνεπαγωγή, η απάντηση εξαρτάται  από το πεδίο ορισμού της $ f$: μην ξεχνάς ότι η $ f: \mathbb{R}^*\to\mathbb{R}$ με $ f(x) \equal{} \frac {1}{x}$ για $ x\neq 0$ είναι μία συνεχής συνάρτηση. Τι πεδίο ορισμού θέλεις? $ \mathbb{R}$? Διάστημα? Συμπαγές υποσύνολο του $ \mathbb{R}$? Μόνο κλειστό? Μόνο φραγμένο? Ο,τιδήποτε? Η απάντηση αλλάζει κάθε φορά...

Cheerio,

Durandal 1707

σωστα.. :blush:  στην περιπτωση συνεχους και 1-1 πχ. στο $ R$ για την αποδειξη μπορω να χρησιμοποιησω το γεγονος οτι:
για $ a_1<a_2<a_3$ , εστω οτι $ a_2<a_1<a_3$ με θεωρημα ενδιαμεσων τιμων στο [$ a_2,a_3$] (... ατοπο). Aρα  θα ειναι $ f(a_1)<f(a_2)<f(a_3)$ ή $ f(a_1)>f(a_2)>f(a_3)$ , συνεπως θα ισχυει οτι και για $ a_1<a_2<...<a_n$  η  αντιστοιχη σχεση για τις τιμες των $ a_1, a_2,...,a_n$? μηπως ειναι λαθος καπου ο συλλογισμος ? Αν ναι τοτε η αποδειξη αυτου πως μπορει να γινει?
Ευχαριστω και παλι για το ενδιαφερον! :lol:


geometry
trigonometry
ratio
similar triangles
algebra
system of equations
angle bisector

(****)

18. Let $ \triangle ABC$ have an inscribed semicircle, diameter on $ BC$, that touches $ AB$ and $ AC$ at $ F$ and $ E$, respectively. Provided that $ BF=1$, $ CE=9$, and $ AB+AC=40$, find the area of $ \triangle ABC$.

[hide]Let $ b=BO=\sqrt{r^{2}+1}$ and $ c=CO=\sqrt{r^{2}+81}$ where $ r$ is the radius of the semicircle. Let $ h$ be the altitude from $ A$ to $ BC$. Clearly $ [ABC]=20r$

$ \cot B+\cot C=\frac{10}{r}=\frac{b+c}{h}\Rightarrow [ABC]=\frac{(b+c)h}{2}=\frac{r(b+c)^{2}}{20}=20r \Rightarrow b+c=20$

Solve to see $ r=3\sqrt{7}$ and $ [ABC]=60\sqrt{7}$[/hide]

That is a correct solution. There is a more elegant geometric way. Think...what can we do with semicircles?

I also got $ 60\sqrt{7}$

I found that the area was $ 20r$ splitting it into two triangles.  Then I went the non-trig route, finding [i]similar triangles[/i].  One similar triangle ratio is created by one of the triangles divided by the height and the use of one of the right triangles created by the radius.  Then another similar triangle is the other right triangle created by the height and the other right triangle created by the radius.  Eventually, you'll get all these variables but they all cancel out, and you can find that $ BC=20$ (from similar triangles you will find the height divides BC into 2 and 18).  Then you can use pythagorean theorm and a resulting system of equations and find that the center divies BC into parts of 8 and 12.  Then from the pythagorean theorm $ 8^{2}-1^{2}$ which is also $ 12^{2}-9^{2}$  equals the radius of $ \sqrt{63}=3\sqrt{7}$ so its $ 60\sqrt{7}$

Okay take the semi-circle and make it into a full circle. Let the second tangent from $ C$ to the circle touch at $ D$. Let $ CD\cap AB=G$. $ AF=AE=15$, and $ CD=CE=9$. Let $ GD=GF=x$. By the angle bisector theorem, $ \frac{9+15}{15+1}=\frac{9+x}{x-1}\implies x=21$. It follows that $ [CAG]=\sqrt{(21)(9)(15)(21+9+15)}=135\sqrt{7}$. Then $ [CAG]: [ABC]=36: 16$, so $ [ABC]=\boxed{60\sqrt{7}}$.


modular arithmetic
number theory unsolved
number theory

[quote="Orif"]The number $2^{29}$ is a $9$-digit number with distinct digits.Which $digit$ is missing?[/quote]

4???:)

if we consider that the digits are different the problem becomes trivial...

it's well known that every number is congruent to its digit sum modulo 9.
\[2^{29}\equiv (2^{3})^{9}\cdot 4 \equiv (-1)^{9}\cdot 4 \equiv-4 \pmod{9}\]
because of this we have $2^{29}\equiv 0+1+...+9-x \pmod{9}$ where x denotes the wanted number. $0+1+2+...+9 = 45$ -> $2^{29}\equiv-4 \equiv 45-x \equiv-x \pmod{9}$
$4$ is the only digit with this property -> $4$ is missing.

Naphthalin

Naphthalin Can you pove that $2^{29}$ has different digits?

i thought i could assume that. if i can't i don't know a way without calculating directly...

Naphthalin


abstract algebra
group theory
superior algebra
superior algebra unsolved

Let $G$ be a finitely generated group, generated by given $g_{1},...,g_{r}$, and let $N$ a normal abelian subgroup of $G$.

Prove that every element in $g\in [G,N]$ can be represented as \[g=[g_{1},n_{1}][g_{2},n_{2}]\cdots[g_{r},n_{r}].\] (with all the $n_{i}\in N$)

What I had is that $[G,N]\le N$ so is abelian, so $[g_{i},m][g_{i},n]=[g_{i},mn]$. So we can rearrange any finite sequence of commutators with $g_{i}$ to the requested form.

But then: how do we know every element in $[G,N]$ is a product of $[g_{i},n]$'s?

No one?  :maybe: I still found no solution.

For $a,b\in G, m,n\in N$ the following relations hold: 1) $[a,mn]=[a,m][a,n];$  2) $[ab,n]=[a,bnb^{-1}][b,n];$ and 3) $[a^{-1},ama^{-1}]=[a,m^{-1}].$ It follows, by 2 and the fact that $N$ is abelian, that an element of $[G,N]$ then is of the form \[\prod_{i=1}^{r}\left(\prod_{j}[g_{i},n_{i_{j}}][g_{i}^{-1},m_{i_{j}}]\right).\] Now apply relation 1 and 3. (I overlooked the inverse bit in an earlier post.)

Of course! How stupid I couldn't think of that.  :(


$ \text {If }\theta \text{ is acute angle ,}$

$ \text{Prove that } \left ( \frac{3}{\cos\theta} \plus{}\frac{2}{sin\theta}\right)^2  \text{obtains min. value }\text { when } \tan\theta \equal{} \sqrt[3]{\frac{2}{3}} .$

[hide]By Holder, $ \left ( \frac {3}{\cos\theta} \plus{} \frac {2}{sin\theta}\right)^2 \left(\cos ^2 \theta \plus{} \sin^2 \theta \right) \ge (\sqrt[3]{4} \plus{}\sqrt[3]{9})^3$ with equality iff $ \frac{3/\cos \theta}{\cos^2 \theta}\equal{} \frac{2/\sin \theta}{\sin^2 \theta} \Longrightarrow \tan \theta \equal{} \sqrt[3]{\frac 23}$.[/hide]


(1) $a_{1},...a_{n}>0, \prod a_{i}=1.$ Prove $\sqrt{\frac1n\sum a_{i}^{2}}\geq\sqrt[n-1]{\frac1n\sum\frac1{a_{i}}}.$

(2)* More generally, for $a_{1},...a_{n}\ge0$ and natural $k\le n$, prove $\sqrt{\frac1n\sum a_{i}^{2}}\geq\sqrt[k]{\frac1n\sum_{cyc}a_{1}\cdots{a_{k}}}.$ :P
(indices are cyclical $a_{n+i}: =a_{i}$)

Hey,the first one is equal to :
$\sum_{k=1}^{n}a_{k}^{2}=n$($a_{k}\ge 0$),then $a_{1}a_{2}\cdots a_{n}(\sum_{k=1}^{n}\frac{1}{a_{k}})\le n$
But I think we can prove the stronger one following:
$\sum_{k=1}^{n}a_{k}=n$($a_{k}\ge 0$),then $a_{1}a_{2})\cdots a_{n}(\sum_{k=1}^{n}\frac{1}{a_{k}}\le n$ :D

The second one is not always right:
when $n=2N,k=N$
let $a_{1}=\cdots=a_{N}=\sqrt{2}$ and $a_{N+1}=\cdots=a_{n}=0$
and $n$ is large enough. :)

[quote="zhaobin"]The second one is not always right:
when $n=2N,k=N$
let $a_{1}=\cdots=a_{N}=\sqrt{2}$ and $a_{N+1}=\cdots=a_{n}=0$
and $n$ is large enough. :)[/quote]Right :oops:  so let´s ask a different question: Given $n$, find the smallest $k$ such that for all $a_{1},...,a_{n}\ge0$ such that $\sum_{i=1}^{n}a_{i}^{2}=n$, we have
$\sum_{i=1}^{n}a_{i+1}\cdots{a_{i+k}}\le n$.

(And of course we could further vary the condition replacing 2 by another exponent):)


How many distinct ways are there to arrange $4$ couples into a [u]circular[/u] arrangement of $8$ seats, if couples cannot be neighbors and we cannot have a person of one gender with neighbors both of the same gender (i.e. no groupings of three)?

Can we generalize to $n$ couples and $2n$ seats?

That seems an odd question to me without first posing the question,
"How many ways are there to seat $ n$ couples around a round table so that each individual sits between two individuals of the opposite gender and no couple is seated together?"  (Tractable cases: $ n \leq 4$, $ n = 5$ for the ambitious.)

Your sequence is http://www.research.att.com/~njas/sequences/A114939
Mine is http://www.research.att.com/~njas/sequences/A094047

Neither have formulas attached to them, and both could use additional terms, if you can compute them.


Find function $\large f: R R$ satisfying:
$\large f(xf(y))=(1-y)f(xy)+ x^{2}y^{2}f(y)$.

x=0 -->f(0)=0, y=1-->f(xf(1))=f(1)x^2,-->f(1).
Let f(a)=b is not equal 0. Then a is not equal 0 or 1.
Let c=b/a,z=x/a -->f(cz)=(1-a)f(z)+bz^2. g(z)=f(z)-k*z^2, where k=b/(c^2-1+a).
We have g(cz)=(1-a)g(z). If f is continuosly g(z)=z^m. f(x)=k*z^2+z^m is not solution. Therefore c^2=1-a.
It is mean f(a)^2=a^2-a^3. This function is not solution. Therefore f(0)=0.

[quote="Rust"]Therefore f(x)=0.[/quote]
Not only! :)
There is also : $f(x) = x-x^2$.

EDIT : I see it has already been posted and solved here : http://www.mathlinks.ro/Forum/viewtopic.php?t=61219.


inequalities
integration
trigonometry
logarithms
calculus
calculus computations

I think the inequality is incorrect.

Observe that $\sum_{n=1}^{\infty}(-1)^{n}\frac{e^{2n}}{(2n)!}<\infty$, in other words the series converges.
If you add this series to your series you get that

$\sum_{n=1}^{\infty}e^{2n}(1-\frac{e}{2n(2n+1)})$ should converge, which is definitely false. Therefore the inequality you stated does not hold since the series in question diverges.

actually i tried to desighn the problem by determining the series of $\int^{e}_{1}x(\sin x+\ln x)dx$, so maybe i've some mistakes in it....


Euler
geometry
area of a triangle
Heron\u0027s formula
inequalities proposed
inequalities

[color=blue]prove this inegalité it's very easy[/color]

It's trivial because $ab+bc+ca \le a^2+b^2+c^2$ is well known and $a^2+b^2+c^2 \le 2(ab+bc+ca)$ is true because when $a,b,c$ are sidelengths of a triangle, $\sqrt{a},\sqrt{b},\sqrt{c}$ are also sidelengths of a triangle.

Very interesting ! Although simply, the solution which was presented by Fermat-Euler is more dearly than the Siuhochung's solution. It is my opinion.

[quote="levi"]If $X=\frac{(a+b+c)^2}{ab+bc+ca}$, then $[X]=3,\ i.e.\ 3\le X<4 $!. It shows nicely !
My dear Siuhochung killed a butterfly with the atomic bomb. The manufacturier carpet is more invaluable than the mechanical carpet !. It is my opinion.[/quote]
Why do you say so? I didn't use an atomic bomb.  :P The L.H.S. is really trivial. For the R.H.S. I only used heron's formula and that area of a triangle is larger or equal to 0.

[quote="levi"]I am sorry, but the expression with $\"\ \sqrt a ,\ \sqrt b \ ,\sqrt c\ \"$ ?[/quote]
because the area of a triangle with sidelengths a,b,c is $\frac{1}{4} \sqrt{2(a^2b^2+b^2c^2+c^2a^2)-a^4-b^4-c^4}$

Think you that I don't understood ?. To be one stubborn man is not wrongly. But here is not the case. The idea is important and not the concrete case. I hope, my dear, that  you  don't  understand me wrongly.


the only even digit which is a prime is 2. If n is a hiperprime with a digit 2, it most be the first digit (else, we have a 2-digit segment divisible by 2, therefore not a prime). If n is a hiperprime with a digit 5, it most be the first digit (else, we have a 2-digit segment divisible by 5). The digit 9 can't occur in a hiperprime, and also 1.
9|27, 11|33,77, 3|57
(1) If the segment "37" is contained in n, and there's a digit to the right of 7, it may only be 3. There's no digit to the right of 373, because: 37|3737, 3|33.
(2) If the segment "73" is contained in n, and there's a digit to the right of it, it may only be 7 (3|33). There's no digit to the right of 737, because by the previous case, it may only be 3, but: 73|7373.

From the above, we need to check only a finite number of cases.
If n is 1-digit long: n=2,3,5,7. If n is 2-digit long: n=23,37,53,73.
else-
If the first digits are 37: 373
If the first digits are 73: 737 (not good - $ 11|7\minus{}3\plus{}7\equal{}11 \implies 11|737$)
If the first digits are 23: 237 is divisible by 3, 233 contains 33
If the first digits are 53: 533 contains 33, 537 is divisible by 3.
The only hiperprimes: 2,3,5,7,23,37,53,73,373 (they are all primes)

I wrote a long solution at first because I forgot 1 can't be in n :(

[quote=Ahiles]Natural nonzero numder, which consists of $ m$ digits, is called hiperprime, if its any segment, which consists    $ 1,2,...,m$ digits is prime (for example $ 53$ is hiperprime, because numbers $ 53,3,5$ are prime). Find all hiperprime numbers.[/quote]

I assume you mean “any consecutive m digits in the number are prime”. Note that all even digits impossible, except 2, which can only occur in the first digit, or else we can have two digits with 2 as the last one, which is not prime. Similarly with 5. 1 cannot be there as 1 is not a prime, 9 cannot be there 9 is not a prime. So we casework on #s starting with 2 (2, 23), 5 (5, 53), 3 (3, 37, 373), and 7 (7, 73).


[quote="mysmartmouth"]Is there a formula for $1^2 + 2^2 + 3^2......x^2$   :?:[/quote]
If you look on the left side of the page, eventually there will be a proof with no words of the sum of squares

This problem is asked so many times. Can people use Search? I use Search and find 2 links already

[url=http://www.mathlinks.ro/Forum/viewtopic.php?t=34287]http://www.mathlinks.ro/Forum/viewtopic.php?t=34287[/url]
[url=http://www.mathlinks.ro/Forum/viewtopic.php?t=42048]http://www.mathlinks.ro/Forum/viewtopic.php?t=42048[/url]

[quote="10000th User"][quote="mysmartmouth"]10000th User, what is up with your signature?[/quote]
??? What do you mean? I copy it from Discover magazine. It is 10th dimension equation of universe, physics. I thought it looks cool so $\LaTeX$ it :)[/quote]

It does look cool  :lol:

Also, there are plenty of proofs of this formula.

The formula of the sum of the first n odd natural numbers (which is $n^2$) just appeared on the left bar again.


Given a,b,c>0 and ab+bc+ca=1.Prove that $ \sqrt(a^3\plus{}a) \plus{}\sqrt(b^3\plus{}b)\plus{}\sqrt(c^3\plus{}c)$≥$ 2\sqrt(a\plus{}b\plus{}c)$


geometry
trigonometry
ratio
angle bisector
geometry proposed

Let $ABC$ be a triangle and let $M,N,P$ be points on the line $BC$ such that $AM,AN,AP$ are the altitude, the angle bisector and the median of the triangle, respectively. It is known that

$\frac{[AMP]}{[ABC]}=\frac{1}{4}$ and $\frac{[ANP]}{[ABC]}=1-\frac{\sqrt{3}}{2}$.
Find the angles of triangle $ABC$.

aria(ABP)=1/2aria(ABC),aria(AMP)=1/4aria(ABC), so M is the midpoint of BP. this means the triangle ABP has AB=AP and this means the measure of the angle PAC is the difference between the angles B and C of the triangle ABC.

using trigonometry we obtain 3sinCcosB=sinBcosC where C<=B.

NP=BC(b-c)/2(b+c) and we have the ratio between the area of the triangle ANP and ABC,so we obtain b/c=sqrt3  and using he other relation we obtain C=30,B=60,A=90 and B=30,C=60,A=90 because we suppose C<=B.


I need help with the question and please show ur solution
the AMC 10B questions 21(http://www.artofproblemsolving.com/Wiki/index.php/2005_AMC_10B_Problems#Problem_21) and question 15 (http://www.artofproblemsolving.com/Wiki/index.php/2005_AMC_10B_Problems#Problem_15)

[hide="15"]Is that all you got wrong?
Let the roots be $ r$ and $ s$, then by Vietas we have $ n \equal{} 4rs$ and $ p \equal{} ( \minus{} r \minus{} s)$, so $ \frac {n}{p} \equal{} \frac {4rs}{ \minus{} r \minus{} s}$, but we also know again by Viets and the fact that m is in both equations that $ 2r \plus{} 2s \equal{} \minus{} rs$, which simplifies the above fraction to $ 8$.[/hide]
[hide="21"]First note that we don't have to worry about denominators because when we take $ q/p$ they will cancel. So for our purposes we have $ p \equal{} 10$, because there are 10 ways to choose the number, and $ q \equal{}$ $ 10\choose{2}$$ {4\choose{2}}^2\equal{} 1620$, so the answer is A[/hide]

u put question 16 instead of 15
and I need also help with 22 in AMC 10B 2005

ok for 15 there are 5 pairs that make 20 dollars : $ (20,(1,5,10,20))$and $ (10,10)$. There are also 4 types of bills and you are choosing 2 of them, which can be done in (4C2) + 4 = 10 ways, so the answer is 1/2.
For 22, we simplify to $ \frac{2(n\minus{}1)!}{n\plus{}1}$ which is not reducible iff n + 1 is an odd prime. There are 8 odd primes less than 24 so the answer is $ 24 \minus{}8 \equal{} 16$

[quote="information5"][quote="mathemonster"]
For 22, we simplify to $ \frac {2(n \minus{} 1)!}{n \plus{} 1}$ which is not reducible iff n + 1 is an odd prime. There are 8 odd primes less than 24 so the answer is $ 24 \minus{} 8 \equal{} 16$[/quote]
how did u know that odd primes would not work[/quote]

If $ n \plus{} 1$ is prime, it will not be a divisor of $ (n \minus{} 1)!$. We have to exclude the even prime, $ 2$, because there is a 2 in the numerator, so $ 2$ will always divide evenly. This leaves us with the odd primes.


research has shown that adult male deer with large antlers tend to have more mating opportunities and produce more offspring than adult males with smaller antlers. why hasnt natural selection produced male deer with hugh antler?

does selection act more efficiently on dominant or recessive alleles? beneficial or deleterious alleles?

what are the 5 factors that will cause allele frequencies to change in a population? which of them produce adaptive evolutionary change?

not too sure, but it may be because the male deer with huge antlers are more easily hunted and killed.

Selection works a lot more efficiently on dominant than on recessive alleles, since dominant alleles are expressed a lot more often. That's why you see a lot of fatal recessive alleles in populations but not a lot of fatal dominant alleles. Deleterious recessive alleles can hide in a population for a long time without really causing enough trouble for them to be eliminated.

I'm not really sure if you could say that selection acts more "efficiently" on beneficial or deleterious alleles. In fact, since an allele might be beneficial relative to one allele in a population but deleterious relative to another, I don't think there's necessarily always a clear distinction. If I had to choose just one, however, I'd probably say deleterious, as those  often present a much bigger difference in fitness than an allele that is superior to most in the population.

And finally, Elston is right about the deer. While having bigger antlers may make it easier for them to reproduce, it doesn't matter how easily they can mate if they're not able to llive long enough. Increasing antler size represents a tradeoff between fecundity and survivability. Fitness depends on both, and hence a moderate size tends to emerge in a population.


vector
function
inequalities
triangle inequality
real analysis
real analysis unsolved

We call a set E, which is a subset of Rk, convex if

ex + (1-e)y is an element of E, whenever x and y are elements of E, and 0<e<1.

Question : How to prove metric "balls" are convex?

solution : | ey + (1-e)z -x| =.....<=r.
how does "| ey + (1-e)z -x|" fit with equation "ex + (1-e)y" ??

=)

What does it mean for $ ey \plus{} (1 \minus{} e)z$ to be an element of a ball centered at $ x$ and of radius $ r$?

[hide="definition"]$ ey \plus{} (1 \minus{} e)z\in B(x, r)$ if and only if $ |ey \plus{} (1 \minus{} e)z \minus{} x| < r$[/hide]

Edit: Ack. I meant to copy the variables used in the OP, but then accidentally switched to the way I would have written it if I had started the problem...

HilbertThm90: That should be the segment between $ z$ and $ y$, not $ x$ and $ y$. We want to look at segments between any two points in the ball, not just segments with one endpoint at the center.

It matters what metric you use. Here's an [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1226548#1226548]example[/url] of a space in which balls aren't convex.

Now, I assume you're using the Euclidean metric, or at least one of the standard norms. The key properties of a normed vector space: (1) The distance $ d(x,y)$ is $ N(x\minus{}y)$ for some norm function $ N$. (2) $ N(ax)\equal{}|a|\cdot N(x)$ for any $ x$ and any real $ a$. (3) $ N(x\plus{}y)\le N(x)\plus{}N(y)$, so we have the triangle equality. For the Euclidean norm, the triangle inequality is Cauchy-Schwarz.
[hide="A proof for any normed vector space"]First, translate everything so that the center of the ball is zero. Distances are unchanged. Now, $ N(ty\plus{}(1\minus{}t)z)\le N(ty)\plus{}N((1\minus{}t)z)\equal{}tN(y)\plus{}(1\minus{}t)N(z)\le tr\plus{}(1\minus{}t)r\equal{}r$.
That's the version for a closed ball; the latter inequality becomes strict for an open ball.[/hide]


Just wondering:

"The Rd 1 solutions must be postmarked by Oct. 13 to receive credit. They do not have to reach us by Oct. 13"

Does this mean we just have to mail by Oct. 13?

There is no specific deadline for the Entry Form.


Find the sum of the series $ S \equal{} \sum_{n\equal{}0}^{\infty} (n^3 \plus{} 6n^2 \plus{} 11n \plus{} 6)x^n\,\,, |x| < 1,$ without calculating expressions for $ \sum_{n\equal{}0}^{\infty}n^k x^n\,\,, k \equal{} 1,2,3$.

\[ S \equal{} \sum\limits_{n \equal{} 0}^{ \plus{} \infty } {\left( {n \plus{} 1} \right)\left( {n \plus{} 2} \right)\left( {n \plus{} 3} \right)x^n } \equal{} \left( {\sum\limits_{n \equal{} 0}^{ \plus{} \infty } {x^{n \plus{} 3} } } \right)^{\prime ^{\prime ^\prime}}\equal{} ... \equal{} \frac {{ \minus{} 6}} {{\left( {1 \minus{} x} \right)^4 }}.
\]

Bookworm_vn, note that the sum should be positive.

[hide="Another way"]By using the concept of Cauchy product of two convergent series, it can be shown that

$ S \equal{} 6 \cdot \left(\sum_{n\equal{}0}^{\infty}x^n\right)^4$.[/hide]


function
inequalities
real analysis
real analysis unsolved

$f,g: \mathbb R\to\mathbb R$ are onto functions, and $g\circ(g-f)$ is decreasing. There is an $L>1$ such that $|g(x)-g(y)|\ge L|x-y|,\ \forall x,y\in\mathbb R$. Prove that $f$ has a unique fixed point.

if u dont mean strictly decreasing i found a counter example:

let $\displaystyle g(x) = \begin{cases} 2x & \text{for } x < c\\2x+1 & \text{for } x\ge c\end{cases}$ and $f(x) = g(x) -c$,

then all the createria is fulfilled, but $f(x) > x$ for $x\ge c$ and $f(x) <x$ for $x < c$. so there is no fixed point

and i think i got a counter example for stricly decreasing as well:

let $\displaystyle g(x) = \begin{cases} -2x-\frac12 & \text{for } x > 0\\-2x+\frac12 & \text{for } x\le 0\end{cases}$ and $\displaystyle f(x) = \begin{cases} 2x & \text{for } x < 0\\2x+1 & \text{for } x\ge 0\end{cases}$

(but its late over here, and it could well be i just have a knot in my head ;) )

Those aren't counterexamples- our functions must be surjective.

Our conditions force $g$ to be continuous and strictly monotone. If $g$ is increasing, $g-f$ must be decreasing, and therefore $f$ is strictly increasing, with $f(x)-f(y)>g(x)-g(y)>L(x-y)$ when $x>y$. Since $f$ is strictly monotone and surjective, it is continuous as well. It is now easy to show that $f$ has exactly one fixed point by the intermediate value theorem.
If $g$ is decreasing, $g-f$ is increasing and $f$ is strictly decreasing, with $f(x)-f(y)>g(x)-g(y)>L(y-x)$ whenever $y>x$. As above, $f$ is continuous and has exactly one fixed point.

[quote="jmerry"]
Our conditions force $g$ to be continuous and strictly monotone.
[/quote]
Can you explain why?

assume that $g(x)=g(y)$. It implies that :$0=|g(x)-g(y)|\ge L|x-y|$ so $x=y$. $g$ is injective. Since g is injective and surjective, it is bijective.
Now, we can rewrite the inequality from the problem like follows:

$|g^{-1}(x)-g^{-1}(y)|\le \frac 1 L |x-y|$ that means that $g^{-1}$ is a contraction, so it is continuous. Hence $g$ si continuous. And since $g$ is injective we get that $g$ is monotone.

Is there any relation with the fixed point of g and the fixed point of f ?


Let $N$ be midpoint of the side $AB$ of a triangle $ABC$ with $\angle A$ greater than $\angle B$. Let $D$ be a point on the ray $AC$ such that $CD=BC$ and $P$ be a point on the ray $DN$ which lies on the same side of $BC$ as $A$ and satisfies the condition $\angle PBC =\angle A$. The lines $PC$ and $AB$ intersect at $E$, and the lines $BC$ and $DP$ intersect at $T$. Determine the value of  $\frac{BC}{TC} - \frac{EA}{EB}$.

[b]The first part is finding  $ \frac{AE}{BE}$.[/b]

Let $ DA \cap BP \equal{} \{F\}$. $ \triangle ABC \sim \triangle BFC$. So $ AC \cdot FC \equal{} BC^2 \equal{} DC^2$ $ (..1..)$

Menelaus on $ \triangle ABF$, for $ P,E,C$ : $ \frac{AE}{BE} \frac{BF}{FP} \frac{FC}{AC}\equal{} 1$   $ (..2..)$

Menelaus on $ \triangle ABF$, for $ P,N,D$ : $ \frac{AN}{BN} \frac{BF}{FP} \frac{FD}{AD}\equal{} 1$   $ (..3..)$

$ \frac {(..2..)}{(..3..)} \Rightarrow \frac{AE}{BE} \equal{} \frac{AC}{FC} \frac{FD}{AD}$  $ (..4..)$.

If you write $ (..1..)$ on  $ (..4..)$, you will get  $ \frac{AE}{BE} \equal{}  \frac{AC}{DC}$. $ (..5..)$

[b]The second part is finding  $ \frac{BC}{TC}$.[/b]

Menelaus on $ \triangle ABC$, for $ N,T,D$ : $ \frac{AN}{BN} \frac{BT}{CT} \frac{CD}{AD}\equal{} 1$   $ (..6..)$

So  $ \frac{BC}{TC}  \equal{} \frac{BT}{TC} \plus{} 1 \equal{}  \frac{AD}{CD} \plus{} 1 \equal{} \frac{AC \plus{} DC}{DC} \plus{} 1 \equal{} \frac{AC}{DC}  \plus{} 2$ $ (..7..)$

$ (..7..) \minus{} (..5..) \Rightarrow \frac{BC}{TC} \minus{} \frac{AE}{BE} \equal{} 2$

Find the BC/TC - EA/EB
Turkey TST 2005 problem 2
Let N be midpoint of the side AB of a triangle ABC with m(A) greater than m(B).
Let D be a point on the ray AC such that CD=BC and P be a point on the ray DN which lies on the same side of BC as A and satisfies the condition m(PBC)=m(A). The lines PC and AB intersect at E, and the lines BC and DP intersect at T. Determine the value of BC/TC - EA/EB.

Sorry but what does m(A) mean? Is it <BAC?


vector
integration
probability and stats

let $ X_1,X_2, \ldots, X_n$ be random variables such that for any permutation $ \sigma$ the vector $ (X_1, \ldots, X_n)$ has same distribution as $ (X_{\sigma(1)}, \ldots, X_{\sigma(n)})$. How would you prove that if $ S_k \equal{} X_1 \plus{} \ldots \plus{} X_k$ then:
\[ \sum_{k \leq n} 1_{S_k > 0} \equal{}_{\text{(law)}}\inf \{k: S_k \equal{} \max_{j \leq n} S_j\}\]

Even for iid random variables it seems difficult ! (and for positive random variables it is obvious  :lol:  )
ps: this lemma is quite useful to study quantities like $ \int_{[0;1]} 1_{X_s > 0} ds$ for many different processes $ X_s$

Since the permutation property is the only thing we know, it is necessary (and sufficient) to prove this for the random permutation of fixed numbers. Fix $ t$. The left hand side then counts the rearrangements with exactly $ t$ positive sums. The right hand side counts the rearrangements with the maximal sum at the position $ t$ and not below $ t$.

Now, if $ X_1,\dots, X_n$ satisfies the latter property, then all partial sums of the sequence $ X_t,X_{t\minus{}1},\dots, X_1$ are positive and all partial sums of the sequence $ X_{t\plus{}1},\dots, X_n$ are non-positive and vice versa.

On the other hand, if $ X_1,\dots, X_n$ has exactly $ t$ positive partial sums $ S_{k_1},\dots,S_{k_t}$, then all partial sums of the sequence $ X_{k_1},\dots,X_{k_t}$ are positive and all partial sums of the complementary sequence are non-positive.

This suggests the idea to show that there is at least or at most one way to insert a sequence with positive partial sums into a sequence with non-positive ones so that in the resulting sequence a partial sum is positive exactly when it ends at a term from the first sequence.

I'll show that such insertion always exists. Take our sequence with positive sums and split it into blocks. The first block starts at the first term and ends at the term that gives the least partial sum. The second block is chosen in the same way using the remaining tail and so on. Do a similar procedure with the sequence with non-positive partial sums (with maxima instead of minima). Now, if we insert blocks between blocks, we see that the problem reduced to the following: we need to insert a sequence of positive numbers into a sequence of non-positive numbers so that each partial sum ending with a positive number is positive and vice versa.

Now just take the first positive number and put it as far to the right as you can so that the partial sum ending with it is positive. After that, do it with the second positive number (note that it will be put to the right of the first because the position right after the first positive number is always acceptable) and so on.

I have no doubt that there exists an even easier way, but, at least, this solves the problem :).

thank you very much Fedja ! I have been looking for a simple proof of this one for quite a long time !

Hi alekk

Another proof is in Kallenberg's book Chapter 9 corollary 9.20
The proof seems quite simple but uses previous result so maybe fedja's one is more elementary

Regards


LaTeX
AMC
AIME
algebra
binomial theorem
AIME I

[hide="use algebra and the binomial theorem!"]$(a+b\imath )^{2}=a^{2}+2ab\imath-b^{2}$

$(a+b\imath)^{3}=a^{3}+3a^{2}b\imath-3ab^{2}-b^{3}\imath$[/hide]

@jli:  looks correct

apparently the answers for the divsion one is wrong, im doing this on an online homework thing so i know if its wrong. but i dont know why. AHHHHHHH math bugs me because i know its some simple error and i cant see it

[quote="The QuattoMaster 6000"][quote="grizzland"]ok so i forgot to mention this earlier but the answer need to be in ______+_____ i

so for (a+bi)^2 , the answer is (a^2+b^2) + (2abi)

anyone got the other one i cant get it into that form. im not seeing it i guess

oh i got some more that need to be answered in that format as well here they are:

1/(a+bi)
(a+bi)/(c+di)[/quote]
[hide="Answer for $(a-bi)^{3}$"] This one is $(a^{3}-3ab^{2})+i(3a^{2}b-b^{3})$
[/hide]
The solution for $\frac{1}{a+bi}$:
[hide] Multiply the numerator and denominator by $a-bi$ to get $\frac{a-bi}{a^{2}-b^{2}i^{2}}=\frac{a-bi}{a^{2}+b^{2}}=\boxed{\frac{a}{a^{2}+b^{2}}-\frac{bi}{a^{2}b^{2}}}$
[/hide]
The solution for $\frac{a+bi}{c+di}$
[hide] Multiply the numerator and denominator by $c-di$ to obtain $\frac{ac-bd}{c^{2}+d^{2}}+\frac{i(bc+ad)}{c^{2}+d^{2}}$[/hide][/quote]

For $\frac{1}{a+bi}$, it is actually:
[hide] $\frac{a}{a^{2}+b^{2}}-\frac{b}{a^{2}+b^{2}}i$ (typo there)[/hide]

For $\frac{a+bi}{c+di}$ , it is actually
[hide]$\frac{(a+bi)(c-di)}{(c+di)(c-di)}=\frac{(ac+bd)+(bc-ad)i}{c^{2}+d^{2}}=\frac{ac+bd}{c^{2}+d^{2}}+\frac{bc-ad}{c^{2}+d^{2}}i$[/hide]

You should look up something called like Demoirvre's Theorem or something....Helps with expansions such as $(a+bi)^{n}$. By the way I probably spelled the theorem above incorrectly so excuse me.

[quote="chickendude"]DeMoivre's theorem only applies to the polar form
I suppose we could convert to polar

[hide]
$a+bi = \pm\sqrt{a^{2}+b^{2}}cis Tan^{-1}\frac{b}{a}$

selecting the sign based off the quadrant of the point

$(a+bi)^{n}= \pm(a^{2}+b^{2})^{\frac{n}{2}}cis n(Tan^{-1}\frac{b}{a})$

I guess we could convert back into rectangular at this point, but this isn't the best way to go about it at all, unless the original rectangular point yielded an exact angle measure

How do I latex a cis symbol properly?
[/hide][/quote]
unfortuantely cis isn't a latex command.
You have to do \text{latex}

[quote="Art of Owna"][quote="grizzland"][img]http://webwork2.math.utah.edu/webwork_system_html/tmp/equations/d8/4e2ea8949c33fda23bdefdbdb1b8041.png[/img]

[img]http://webwork2.math.utah.edu/webwork_system_html/tmp/equations/99/ae02f46fd99e449972e49d89b328481.png[/img][/quote]

lol this was number 3 on AIME I this year..and I wasted 5 mins trying to use DeMovie Therom before I gave up finding sin(3a) interms of cosine(3a) and that crap...then I used the biomial expansion and did it in 30 secs..[/quote]

lol genius...you know, I thought that was the easiest question on the AIME, even more so than #1.
Yeah, I tend to make things harder for myself too.  :P


What is the maximum number of subsets, having property that none of them is a subset of another, can a set with 10 elements have?

$\textbf{(A)}\ 126  \qquad\textbf{(B)}\ 210  \qquad\textbf{(C)}\ 252  \qquad\textbf{(D)}\ 420  \qquad\textbf{(E)}\ 1024$

See: [url=http://www.cut-the-knot.org/pigeonhole/sperner.shtml]Sperner Theorem at Cut-the-knot[/url] or at [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?f=45&t=14689&p=104108&hilit=sperner#p104108]mathlinks[/url].
The answer is $\binom{10}{[10/2]}=\binom{10}{5}=252$. The answer is $\boxed{C}$.

Any 5-minute solution without knowing Sperner welcome.

Let $S$ be one of maximal set of subsets.
Let $S_a \in S$ be the subset having maximum number of elements and $|S_a| = a$.
Let $S_b \in S$ be the subset having minimum number of elements and $|S_b| = b$.
Assume $a \neq b$.
We add $a-b$ number of elements to $S_b$. Let $X$ be the set of these new subsets and let $X_{a} \in X$.
We know $S_b \not \subset S_a$ and $S_b \subset X_{a}$, so $X_{a} \not \subset S_a$.
We remove $S_b$ from $S$ and adding all elements of $X$ to $S$. Call $S^\prime$ to this new set of subsets.
It is obvious that $|S^\prime| > |S|$. Contradiction with the assumption that $S$ is maximal.
We conclude $a=b$ which means the elements of $S$ are subsets with same length.
Number of $k$-subset of $10$-element set is maximum at $k = 5$. So the answer is  $\binom{10}{5} = 252$.


real analysis
calculus
integration
real analysis unsolved

Let $ f_n$ be a sequence of measurable functions.  Then prove that the set of points $ x$ such that $ f_n(x)$ converges is measurable.

edit: sorry, meant to put it in here. i agree, not computations.

In my opinion, measure theory and Lebesgue integral problems, no matter how basic, should not be posted in "Computations and Tutorials."


I just finished a class in C# and I wondered if anybody else knew any.

I put 3...

C/C++
A little bit of Python
A little bit of Tcl/Tk

Shell  scripting doesn't count,
and then too-small-to-count amounts of Perl, PHP, BASIC, Assembly, Visual Basic (grrrr... Microsoft), ...

Does the language the TIs program in count (I think its BASIC).  I also am learning a bit of Java, but its too little to do anything with.  (only been learning for like 2 weeks)

I know C and BASIC, trying to learn JAVA...

I know C and Java, but I've learned Basic, Logo, TI-83 programming language, C++, but then forgot it all, so I only put 2.

ive taken some courses in java and stuff before, but ive forgotten it all

Now, semantic variants count? I mean, I know Lisp and Scheme, but both are pretty similar. Or if you know C and C++? Well, let's count them as one.

On the other hand, some edition languages could be counted as programming languates, because you are telling a compilator or interpreter what to do with your source code. For example: Latex, Html. I suppose most of the people wouldn't count them as programming languages.

Let's see Basic, C++, Pascal, Java, Scheme. Some scripting languates as JavaScript, ActionScript (I love it), Xml (yes, it can be used as a scripting language, ask anyone who had worked with Struts!). Some variants of some languates used to program for the web: jps, php. Well, they are not that few!

Best,

C, C++, TI-BASIC, QBASIC, some javascript, some java, LaTeX, HTML
That's what, 3 or 4? :)

i don't know any yet, but a bunch of my friends and I will be taking computer programming next year where we will learn C++, HTML, and Java

[quote="Valentin Vornicu"]HTML and LaTeX can't be really counted as "programming languages" ... at least that's what I think ...  :?[/quote]

Well Valentin, I disagree with you, at least with respect to LaTeX. I think we can consider a programming language every collection of structures that inform to a computer interpreter or compiler what to do with data that is either internal or external to the instruction, it must contain Instructions, Control Flow, Reference, Design Phillosophy, and must have a way to reuse.

Now, HTML may be does not hold with the reuse part, but also did most of the first programming languages too, and we could say that any Browser is a HTML interpreter.

On the other hand, Latex has everything, even standar libraries of rutines and subrutines (and loops and arithmetic functions, and ...)!!

Best,

Anyone know assembly?

If so, could you recommend a place to learn it?

Thanks,

[quote="Gyan"]FORTRAN, PL/I, COBOL,ALGOL,RPG,APL, IBM-ASSEMBLER, -  Just to name a few..
WYLBUR, REXX,JCL, Most of Unix scripting languages ...etc[/quote]
Jeez :what?: , are there any that you don't know?

C++, C, VB, some Perl, some JavaScript, calc Basic (2 variants), DarkBASIC (hehe), umm...that's it, I think...

I know C++ ,C ,logo, and last and least VB.

ummm........my friend taught me couple of programming languages...some basic, and java, ...etc..... anyways he's studyin software programmmin at unc. so.....???? :D

A user had requested information on where to begin with assembly language.  One of the most useful references available online is the Art of Assembly Language Programming by Randall Hyde and I recommend the interested individuals to download the pdf from

http://www.planetpdf.com/developer/article.asp?ContentID=6633

It covers mostly the x86 architecture but can be used as a basepoint for further study.

I must say the book is a marvel.

C/C++,  Java, QBasic, Windows ShellScript, Lisp, Scheme, HTML, LaTeX, Maple, JavaScript, most of the TI-Basics, and a little Assembly.
 :lol: Gee, I hope I didn't leave any out.

[quote="Myth"]I can't believe that Delphi is so unpopular! Delphi is very widely explotable here, in Russia. :?[/quote]

That is interesting. I have never worked with Delphi, but before starting grad school, I worked as programmer (in Costa Rica, not here in the US), and I can tell you that at least there I never saw a company that program in Delphi (just a guy that did some small comercial applications in Delphi).  The most usual languages that I found were: Visual Basic (the kingdom of Windows), C++, Java and sometimes Oracle (I must confess I don't know anything about the last one), and for web applications, well, the server part with some of the ones before, but the client part with PHP, JSP and when necessary, JavaScript. Of course, also SQL or MySQL, and some XML. I have looked in some of the adds here, and those are also the languages the companies ask for.

Nevertheless, the guy I know that programmed by himself some comercial applications, he used Delphi and he loved it! In my case, I like a lot Java, even when I consider a lot more efficient C++.

Best,

[quote="jackroland"][quote="djimenez"]I like a lot Java, even when I consider a lot more efficient C++.[/quote]
If you consider C++ efficient then you should look at C#(pronounced "c sharp")
It combines the best of C and C++ and adds some new stuff too.[/quote]

WHAT??????, no, down to the domination of Microsoft. Well, just kidding. I personally, even when I use windows around 30% of the time that I am infront of a computer, I try to use other kind of software. Neverthless, as far as I understand, C# is part of the .NET, and given that VB is not exactly the most efficient (even when it is easier than most of the languages), then I really don't try the programming tools offered by MS. And I also like to program in Linux  :D .

By the way, remember, the Borgs are like Windows: "YOU WILL BE ASSIMILATED. RESISTENCE IS FUTILE!!". :D  :D  :D  :D

Best,

I know C++, Visual Basic, Perl, Java, some Python and some Ruby...

When I say know I mean I know basics... Like I am really familiar with the C++ VB and Java libraries while I would need to look up stuff for almost everything else up there.

Although I really dont consider scripting a kind of programming language since it does not directly deal with the computer, I know:
HTML, XHTML, CSS, ActionScript 2.0, JavaScript, PHP, VBScript, some ASP, some JSP,  XML, and a bit of SQL...

[quote="furious"]i'm pathetic. i can barely make programs on my TI-83+[/quote]

Don't hesitate, that is probably just lack of knowledge!, I believe you are in high-school, probably there has been no good reason for you to learn a programming language, and probably eventually you will. In general, as everything, programming can become as complex as you want, but most of the ideas are pretty simple  :D .

Best,

I agree, I know visual basic, pascal and calculator programmings, and I can feel that as long as you know the fundaments of one programming language, it won't be hard to start another since they share same concepts like for..next loops, do while, etc. --i'm going to learn C++ this summer, wish me luck  :D


$ x,y,z,t>0$ and $ x\plus{}y\plus{}z\plus{}t\equal{}1$ Then prove:

$ 6(x^3\plus{}y^3\plus{}z^3\plus{}t^3) \ge x^2\plus{}y^2\plus{}z^2\plus{}t^2 \plus{} \frac{1}{8}$

From CBS:
$ (x^2\plus{}y^2\plus{}z^2\plus{}t^2)\geq\frac{1}{4}$.
Hence $ 4(x^3\plus{}y^3\plus{}z^3\plus{}t^3)\equal{}4(x^3\plus{}y^3\plus{}z^3\plus{}t^3)(x\plus{}y\plus{}z\plus{}t)$
$ \geq 4(x^2\plus{}y^2\plus{}z^2\plus{}t^2)^2\geq x^2\plus{}y^2\plus{}z^2\plus{}t^2$.
So all we need to prove is:
$ (x^3\plus{}y^3\plus{}z^3\plus{}t^3)\geq\frac{1}{16}$.Which is true because $ (x^3\plus{}y^3\plus{}z^3\plus{}t^3)\geq (x^2\plus{}y^2\plus{}z^2\plus{}t^2)^2\geq\frac{1}{16}$.

I was posted solutions at here: http://batdangthuc.net/forum/showthread.php?t=26&page=2
[b]First solution( NguyenDungTN):[/b]
By AM-GM inequality, we have:
$ 2x^3\plus{}\frac{1}{4^3} \ge \frac{3x^2}{4} \\x^2\plus{}\frac{1}{4^2} \ge \frac{x}{2}$
It follows that:
$ 6(x^3\plus{}y^3\plus{}z^3\plus{}t^3)\plus{}\frac{3}{16} \ge \frac{9(x^2\plus{}y^2\plus{}z^2\plus{}t^2)}{4} \\\frac{5(x^2\plus{}y^2\plus{}z^2\plus{}t^2)}{4}\plus{}\frac{5}{16} \ge \frac{5(x\plus{}y\plus{}z\plus{}t}{8}\equal{}\frac{5}{8}$
Adding up two of them we get
$ 6(x^3\plus{}y^3\plus{}z^3\plus{}t^3) \ge x^2 \plus{} y^2 \plus{} z^2 \plus{} t^2 \plus{}\frac{1}{8}$
[b]Second solution( Zaizai-hoang) [/b]
We known that
$ 6x^3\ge x^2\plus{}\frac{5a}{8}\minus{}\frac{1}{8}\Leftrightarrow \frac{(4x\minus{}1)^2(3x\plus{}1)}{8}\ge 0$
Adding up four similar inequalities, we are done!

[hide="My solution:"]This inequality is true for all positive numbers:
$ 6(x^3 \plus{} y^3 \plus{} z^3 \plus{} t^3) \ge (x^2 \plus{} y^2 \plus{} z^2 \plus{} t^2)(x\plus{}y\plus{}z\plus{}t) \plus{} \frac {1}{8}(x\plus{}y\plus{}z\plus{}t)^3$

and the proof is by schur 3 times.
[/hide]


Consider the sequence of numbers defined by x1 = 0 and xn+1 = :sqrt:(2 + xn) for n :ge: 1.  The "Art of Problem Solving" volume 2 (Chapter 18) shows how to evaluate the limit of xn as n approaches infinity.  It also says that the finite value of xn can only be evaluated with a calculator.  But it doesn't point out that there is a closed-form solution for xn.  Can you find one?

Let xinfinity = k. Then, k = sqrt(2+sqrt(2+sqrt(2+sqrt(2+.... Then, we make the substitution:

k = sqrt(2+k)
k^2 = 2 + k
k^2 - k - 2 = 0

(k-2)(k+1) = 0

k = 2, since we want the principal root.[/code]

Great, you've found that the limit of xn is 2.  But can you find a formula for xn itself?

I get [hide]xn = 2sin(:pi:*(2^(n-1)-1)/2^n), but I must say that I certainly wouldn't have gotten that without Mathematica and I haven't really tried to prove it yet.  I just got a little lucky guessing that it was sines of angles, which came to me because the number :sqrt:(2 + :rt2:) reminded me of sin(:pi:/8).[/hide]

Yes, your formula is correct!  Here is a little simpler way to write it: [hide]xn = 2 cos(:pi:/2n) [/hide].  Perhaps that version will suggest a proof.


Hi,

I try to buy a calculator that I can use for Mathcounts and for my regular school works.
Which calculator is the best?

I heard that TI-89 Titanium is a good calculator.
Is TI-89 allowed in Matchcounts competition (Target and Team)?

Does TI-89 Titanium offer a good programming interface?

I personally prefer the TI-84 silver. It also has good programming interface and is allowed at MATHCOUNTS

But of course the TI-89 is a newer version. I don't know if it is allowed or not

The TI-89 Titanium doesn't have a QWERTY keyboard, it has an ABCDEF keyboard. I think it is allowed.

The TI-89 is helpful because it can solve equations, prime factorize numbers, .... I don't know about the TI-84.

My trusty ti-84 silver has served me well since 4th grade and gotten me to 2nd place written nationally.

The 89 Titanium's interface is really nice.  I can confirm it's allowed on MATHCOUNTS, SAT, etc.

Also, not [b]all[/b] graphing calculators are allowed.  Only those without a QWERTY keyboard are allowed (so TI-92, Voyage are not allowed).

Yes, QWERTY keyboards are not allowed.  However, virtually NO graphing calculators use a QWERTY keyboard.  Most simply have an alphabetical key system.  Other calculators not allowed:
                       those that have paper tape used to print calculations
                       those that have a camera
                       those that require a wall outlet
                       those that provide internet access
                       calculators that also function as PDAs, cell phones, etc.
Also, calculators DO NOT need official approval from Mathcounts.  As long as they follow the rules above and a few others, they're OK.  Also, calculators can store information(formulas, advice, etc.) but I'm pretty sure it's cheating if you take advantage of that.  Anyways, most graphing calculators should be pretty similar in performance, as long as you know how to use them.  :lol:

[quote="maybach"]as long as you know how to use them.[/quote]

Yeah, you should master using your calculator. If you aren't sure how to use it, bring a back-up. For example, this year I had a good calculator, but it was hard to find the $ \pi$ key and some others, so I brought a back up and used that.

[quote="maybach"]Also, calculators can store information(formulas, advice, etc.) but I'm pretty sure it's cheating if you take advantage of that.[/quote]

Actually, you are allowed to have programs and formulas on your calculator.

I personally own a TI-89 and think it's much better than the TI-84 silver. It has way more functions and is useful in MathCounts.

Btw, in grades 6/7 I was dependent on formulas and such and got pwned. This year, the only benfit of a fancier calculator than a regular 4 function one was the ability to see previous commands and use the ANS key (of course, i did check everything with programs :wink: )

[quote="isabella2296"]All graphing calculators are allowed. I really like the TI-89, because its interface is nice and it has always served my purposes well. As for scientific calculators, nothing beats my trusty old Casio fx-300ES.  :D[/quote]

I totally agree with you. The TI-89 Titanium kicks @ss. Most of the other calcs can only be programmed in BASIC (which is a n00bs language), the TI-89 T can be programmed in FULL ANSI C. That's right, with pointers and everything. It will make programming a LOT easier. It also has fast 3D graphing which I don't think the TI-84 has but if it does you'll be sitting there for about 10 minutes waiting for it to graph it because of the slow processor. I had to get for my class (it was basically an excuse to get one, I never used it in class) and I have loved it ever since. If you want to settle for a scientific(which are easier to use), use the one that izzy says (I can't find mine right now but its similar and it is the best scientific calculator EVER, its been given to me by my brother so its had about 7 years of work and still works great).

[quote="Poincare"]......I totally agree with you. The TI-89 Titanium kicks @ss......[/quote]

Please refrain from using words like that :|

I think the TI-89 is too confusing--only fitting for high-schoolers.  The TI-84 performs all functions needed on MATHCOUNTS so why not the TI-84?

@ Pink Panther (signature)--yeah he did, and broke two records too

The problem is that once you get used to one of them it is hard to switch because the layout is completly different

It's not that hard to switch between, just you need to remember the shortcuts and programming languages.


[quote="mustafa"]Why is the math jam for round 2 9 days after the solutions were due?[/quote]

Holidays.

[quote="13375P34K43V312"]Who cares, we can discuss them now.[/quote]
Umm, at the point that was posted it had been said that Round 2 most likely couldn't be officially discussed until after the math jam.


Although I can't tell you how to solve it, I have seen similar problems so I am doubting that it is impossible.

What I mean by impossible:

I posted it everywhere for like a month and nobody solved it.

能不能用中文?
我看不懂题目...

[quote="ILKA"][quote="paganinio"][quote="blackbelt14253"]Ok. Here's a (apparently impossible) problem.

3 dots are randomly selected within a square of side length 12. What is the probability that they will lie in some circle of radius 6?[/quote]

题目的中文意思如下：一个矩形的边长是12，在该矩形内部随机选取三个点，那么这三个点位于某个半径为6的圆之中的概率是多少？

换句话说，这三个点相距的距离不能太远，必须能够用一张圆形卡片把三个点都遮盖住。

这个题目用纯数学方法，目前尚未有人能解出，但是用计算机模拟，一秒钟就可以得出答案。[/quote]
Will you translate to english,please[/quote]

I believe the OP's problem is in english.

$\boxed{\frac{(6\pi)^2}{144}}$ I believe is the answer

I'm quite sure that's not the answer, otherwise it would be too easy...

[quote="kuing"]能不能用中文?
我看不懂题目...[/quote]

3个点内随机选择一个正方形边长12。什么是概率，他们将在于一些圈半径6？

I wrote a C proram and got a result of $0.92651$ by doing experiments.

Here N is the number  of experiments,  M is the number that satisfying the condition.

RAND_MAX=2147483647

 The probability is 0.966667, When M=29, N=30.
 The probability is 0.936667, When M=281, N=300.
 The probability is 0.925947, When M=277784, N=300000.
 The probability is 0.926505, When M=27795155, N=30000000.
 The probability is 0.926510, When M=92650968, N=100000000.


function
inequalities
number theory unsolved
number theory

Let $ f: N\rightarrow N$ be a function such that $ kf(n)\leq f(kn)\leq kf(n)\plus{}k\minus{}1$ for all $ k,n\in N$.

(a) Prove that $ f(a)\plus{}f(b)\leq f(a\plus{}b)\leq f(a)\plus{}f(b)\plus{}1$ for all $ a,b\in N$.

(b) If $ f$ satisfies $ f(2007n)\leq 2007f(n)\plus{}2005$ for every $ n\in N$, prove that there exists $ c\in N$ such that $ f(2007c)\equal{}2007f(c)$.

Solution for part (a). Still trying to finish (b).

[hide]The following equations are (1) for $ k \equal{} ab, n \equal{} a\plus{}b$, (2) for $ k \equal{} a(a\plus{}b), n \equal{} b$, and (3) for $ k \equal{} b(a\plus{}b), n \equal{} a$.

(1) $ ab f(a\plus{}b) \leq f(a^2b \plus{} ab^2) \leq ab f(a\plus{}b) \plus{} ab \minus{} 1$
(2) $ (a^2 \plus{} ab) f(b) \leq f(a^2b \plus{} ab^2) \leq (a^2 \plus{} ab) f(b) \plus{} a^2 \plus{} ab \minus{} 1$
(3) $ (ab \plus{} b^2) f(a) \leq f(a^2b \plus{} ab^2) \leq (ab \plus{} b^2) f(a) \plus{} ab \plus{} b^2 \minus{} 1$

For convenience of writing, set $ S \equal{} a^2b \plus{} ab^2$.

Multiply (1) by $ a\plus{}b$ to get (4).
(4) $ S f(a\plus{}b) \leq (a\plus{}b) f(S) \leq S f(a\plus{}b) \plus{} S \minus{} a \minus{} b$
Then multiply (2) by $ b$ and (3) by $ a$. Add these together to get (5).
(5) $ S (f(a) \plus{} f(b)) \leq (a\plus{}b) f(S) \leq S (f(a) \plus{} f(b)) \plus{} 2S \minus{} a \minus{} b$

($ S$ no longer has any significance beyond being positive and equal to itself) From here we can prove each side of the inequality.

[b]Left inequality[/b]

Consider the right inequality of (4) and the left inequality of (5). Combined, we get
$ S(f(a) \plus{} f(b)) \leq (a\plus{}b)f(S) \leq S f(a\plus{}b) \plus{} S \minus{} a \minus{} b$
$ f(a) \plus{} f(b) \leq f(a\plus{}b) \plus{} 1 \minus{} \frac{a\plus{}b}{S}$
Since $ 1 \minus{} \frac{a\plus{}b}{S} < 1$ and all other terms are integers, we have $ f(a) \plus{} f(b) \leq f(a\plus{}b)$.

[b]Right inequality[/b]

Consider the left inequality of (4) and the right inequality of (5). Combined, we get
$ S f(a\plus{}b) \leq (a\plus{}b) f(S) \leq S (f(a) \plus{} f(b)) \plus{} 2S \minus{} a \minus{} b$
$ f(a\plus{}b) \leq f(a) \plus{} f(b) \plus{} 1 \plus{} (1 \minus{} \frac{a\plus{}b}{S})$
Since $ 1 \minus{} \frac{a\plus{}b}{S} < 1$ and all other terms are integers, we have $ f(a\plus{}b) \leq f(a) \plus{} f(b) \plus{} 1$.[/hide]

Can anybody solve the (very difficult-looking) part (b)?

Unless I am being stupid and missing an idea, a definite possibility, part (b) is both very hard-looking and very hard. Since I made that first reply I have been working on this problem a lot, and I haven't gotten that close.

Some small hints that I think are useful:

The equation in part (a) easily generalizes to the following: Given a sequence of positive integers $ a_1, a_2, \ldots a_n$, $ \sum f(a_i) \leq f(\sum a_i) \leq \sum f(a_i) \plus{} (n\minus{}1)$. This equation is much stronger than both the given one and the part (a) one. The additional condition in (b) must be used separately though.

Define $ g(x) \equal{} f(x) \minus{} xf(1)$. Then $ g(1) \equal{} 0$ and $ g$ satisfies all the conditions $ f$ does. This cleans up some equations.

The minimum $ c$ that works for any function $ f$ is always less than $ 2007$, I'm pretty sure.

[quote="radio"][quote="nguyentrang"]i think i've seen this problem. it's from china or something[/quote]

So can you solve it?[/quote]

Well, not yet  :D

it's from korea :lol:
it was on the Korea NMO in last year for No.6.

for part b) we can use pigeon hole theorem.

think $ f(2007i)$ for $ i \equal{} 1,,,,,2007$ and let $ a_i \equal{} f(2007i)$
assume that there is no $ t$ such that $ a_t$ is a multiple of 2007.
first $ 2007f(i) \plus{} 2006 \ge a_i \ge 2007f(i)$. but there is no $ i$ such that $ f(2007i) \equal{} 2007f(i)$
and because of the given condition ....then, $ 2007f(i) \plus{} 2005 \ge a_i > 2007f(i)$
then $ a_i(mod2007)$ is one of $ 1,,,,2006$ so there is $ k,l$ such that $ a_k \equiv a_l(mod2007)$ ($ k > l$)
then by part a), $ a_k \minus{} a_l \ge a_{k \minus{} l} \ge a_k \minus{} a_l \minus{} 1$
so, $ a_{k \minus{} l} \equal{} a_k \minus{} a_l, or,a_k \minus{} a_l \minus{} 1$
then $ a_{k \minus{} l} \equiv 0 or \minus{} 1(mod 2007)$
both result contrdiction because $ 2007f(i) \plus{} 2005 \ge a_i > 2007f(i)$.

so there is $ t$ such that $ a_t$ is a multiple of 2007, and combine it with $ 2007f(t) \plus{} 2006 \ge a_t \ge 2007f(t)$, then $ f(2007t) \equal{} 2007f(t)$