induction
function
algebra
polynomial
Ring Theory
vector
binomial theorem

They are infinite sequences in both directions, that is, are $ \ldots,a_{\minus{}3},a_{\minus{}2},a_{\minus{}1},a_0,a_1,a_2,a_3,\ldots$. Sorry for being ambiguous.

$ \{x_{k}\}$ is a $ good$ sequence. then $ x_{k}, x'_{k}, x''_{k}, ...$ are integers. For the first average sequence we have $ x'_{k}\equal{}\frac{x_{k} \plus{} x_{k\plus{}1}}{1}$ then $ x_{k} \equiv \minus{} x_{k\plus{}1} \bmod{2}$. That means $ x_{k}, x_{k\plus{}1} \equiv 1,0 \bmod{2}$. For ist squares we have $ x_{k}^{2}, x_{k\plus{}1}^{2} \equiv 1,0 \bmod{2}$ so the first average sequence of $ x'_{k}$ is integer. From this we are using the same argument for the second average sequence of $ x'_{k}$.

I'm not sure that the end of your proof is correct.  :lol:

[quote="freemind"]If $ \{a_k\}$ is a sequence of real numbers, call the sequence $ \{a'_k\}$ defined by $ a_k' \equal{} \frac {a_k \plus{} a_{k \plus{} 1}}2$ the [i]average sequence[/i] of $ \{a_k\}$. Consider the sequences $ \{a_k\}$; $ \{a_k'\}$ - [i]average sequence[/i] of $ \{a_k\}$; $ \{a_k''\}$ - average sequence of $ \{a_k'\}$ and so on. If all these sequences consist only of integers, then $ \{a_k\}$ is called [i]Good[/i]. Prove that if $ \{x_k\}$ is a [i]good[/i] sequence, then $ \{x_k^2\}$ is also [i]good[/i].[/quote]

Two extensions of the problem which must also hold if my solution is right:

[b]1)[/b] Not only is the sequence $ \left\{x_k^2\right\}$ good, but all sequences $ \left\{x_k^t\right\}$ for integers $ t\geq 0$ are good.
Thanks Peter for a more reasonable version of this: If $ \left\{x_k\right\}$ and $ \left\{y_k\right\}$ are two good sequences, then the sequence $ \left\{x_ky_k\right\}$ is good as well.

[b]2)[/b] And they are still good if you define the average sequence not by $ a_k' \equal{} \frac {a_k \plus{} a_{k \plus{} 1}}2$, but by $ a_k' \equal{} \frac {a_k \minus{} a_{k \plus{} 1}}2$.

  darij

Here is a very rough outline, not proofread. I feel this is not the best solution by far, so you should better wait until someone posts something more intelligent.

I will only show this assertion:

[i]Assertion 1.[/i] If $ \left(x_k\right)_{k\in\mathbb{Z}}$ and $ \left(y_k\right)_{k\in\mathbb{Z}}$ are two good sequences, then the sequence $ \left(x_ky_k\right)_{k\in\mathbb{Z}}$ is good as well.

(I'm denoting sequences by $ \left(x_k\right)_{k\in\mathbb{Z}}$ rather than by $ \left\{x_k\right\}$ here.)

(Note that this Assertion 1 immediately yields the problem and its extension [b]1)[/b] and quickly yields extension [b]2)[/b] after one observes that $ \left(\left( - 1\right)^k\right)_{k\in\mathbb{Z}}$ is a good sequence, and thus, after Assertion 1, if $ \left(x_k\right)_{k\in\mathbb{Z}}$ is a good sequence, then $ \left(\left( - 1\right)^kx_k\right)_{k\in\mathbb{Z}}$ is a good sequence as well.)

Proving Assertion 1 is done in several steps:

[b]1°[/b] Show (by induction over $ u$) that the $ u$-fold average sequence of the sequence $ \left(x_k\right)_{k\in\mathbb{Z}}$ has the form $ \left(\frac {1}{2^u}\sum_{i = 0}^u\binom{u}{i}x_{k + i}\right)_{k\in\mathbb{Z}}$. (The "$ u$-fold average sequence" just means ${ \underbrace{\text{the average sequence of the average sequence of the ... of the average sequence}}_{u\text{ times } < < \text{ average sequence } > > }}$.)

[b]2°[/b] It will thus be enough to show that if $ x_0$, $ x_1$, ..., $ x_n$, $ y_0$, $ y_1$, ..., $ y_n$ are integers satisfying $ 2^u\mid\sum_{i = 0}^u\binom{u}{i}x_i$ for all $ u\in\left\{0,1,...,n\right\}$ and $ 2^v\mid\sum_{j = 0}^v\binom{v}{j}y_j$ for all $ v\in\left\{0,1,...,n\right\}$, then $ 2^n\mid\sum_{p = 0}^n\binom{n}{p}x_py_p$. (This way we can conclude that the $ 0$-th element of the $ n$-fold average sequence of the sequence $ \left(x_ky_k\right)_{k\in\mathbb{Z}}$ is an integer, but if we "move" the initial sequences $ \left(x_k\right)_{k\in\mathbb{Z}}$ and $ \left(y_k\right)_{k\in\mathbb{Z}}$ a few steps forward or backward, we can also see this way that all the other elements of the $ n$-fold average sequence are integers as well. And since this holds for all $ n$, the sequence $ \left(x_ky_k\right)_{k\in\mathbb{Z}}$ must be good.)

[b]3°[/b] Denote $ X_u = \sum_{i = 0}^u\binom{u}{i}x_i$ for all $ u\in\left\{0,1,...,n\right\}$. Then, $ x_p = \sum_{i = 0}^p\left( - 1\right)^{p - i}\binom{p}{i}X_i$ for all $ p\in\left\{0,1,...,n\right\}$. (This is a purely algebraic fact, an analogue of the [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=112581]binomial inversion[/url].) Don't forget that $ 2^u\mid X_u$ for all $ u$. Similarly, $ y_p = \sum_{j = 0}^p\left( - 1\right)^{p - j}\binom{p}{j}Y_j$ for all $ p\in\left\{0,1,...,n\right\}$ and $ 2^v\mid Y_v$. Thus, proving that $ 2^n\mid\sum_{p = 0}^n\binom{n}{p}x_py_p$ is equivalent to showing that

$ 2^n\mid\sum_{p = 0}^n\binom{n}{p}\left(\sum_{i = 0}^p\left( - 1\right)^{p - i}\binom{p}{i}X_i\right)\left(\sum_{j = 0}^p\left( - 1\right)^{p - j}\binom{p}{j}Y_j\right)$.

This rewrites as

$ 2^n\mid\sum_{p = 0}^n\sum_{i = 0}^p\sum_{j = 0}^p\left( - 1\right)^{p - i}\left( - 1\right)^{p - j}\binom{n}{p}\binom{p}{i}\binom{p}{j}X_iY_j$,

i. e. as

$ 2^n\mid\sum_{i = 0}^n\sum_{j = 0}^n\left( - 1\right)^{i + j}\sum_{p = 0}^n\binom{n}{p}\binom{p}{i}\binom{p}{j}X_iY_j$.

This will obviously be proven once we show that for every $ i\in\left\{0,1,...,n\right\}$ and every $ j\in\left\{0,1,...,n\right\}$, we have

$ 2^n\mid\sum_{p = 0}^n\binom{n}{p}\binom{p}{i}\binom{p}{j}X_iY_j$.

Remembering that $ 2^i\mid X_i$ and $ 2^j\mid X_j$, we see that this is obvious if $ i + j\geq n$, while for $ i + j < n$, it remains to prove that

$ 2^{n - \left(i + j\right)}\mid\sum_{p = 0}^n\binom{n}{p}\binom{p}{i}\binom{p}{j}$.

This was shown in http://www.mathlinks.ro/Forum/viewtopic.php?t=192313 .

That's all, and I don't really have the time now to go into more details. But simplifications are welcome. And finally, what on Earth is the combinatorial meaning of sequences $ x_0$, $ x_1$, ..., $ x_n$ satisfying $ 2^u\mid\sum_{i = 0}^u\binom{u}{i}x_i$ for all $ u\in\left\{0,1,...,n\right\}$ ? I believe that this is the question that leads to the "real" solution of the problem.

  darij

So, is there an easier solution?

Anyway, the Darij solution is already very nice  :)

[quote="freemind"]If $ \{a_k\}$ is a sequence of real numbers, call the sequence $ \{a'_k\}$ defined by $ a_k' = \frac {a_k + a_{k + 1}}2$ the [i]average sequence[/i] of $ \{a_k\}$. Consider the sequences $ \{a_k\}$; $ \{a_k'\}$ - [i]average sequence[/i] of $ \{a_k\}$; $ \{a_k''\}$ - average sequence of $ \{a_k'\}$ and so on. If all these sequences consist only of integers, then $ \{a_k\}$ is called [i]Good[/i]. Prove that if $ \{x_k\}$ is a [i]good[/i] sequence, then $ \{x_k^2\}$ is also [i]good[/i].[/quote]

[quote="greentreeroad"]They are all infinite sequences, right?[/quote]

[quote="freemind"]They are infinite sequences in both directions, that is, are $ \ldots,a_{ - 3},a_{ - 2},a_{ - 1},a_0,a_1,a_2,a_3,\ldots$. Sorry for being ambiguous.[/quote]

I am writing again because I think I found the "real" solution of this problem now.

First let's restate and extend the problem beyound recognition. Instead of "infinite sequences in both directions", we will just say "functions from $ \mathbb{Z}$ to $ \mathbb{R}$", i. e. "elements of $ \mathbb{R}^{\mathbb{Z}}$". We will use some algebraic terminology, most importantly rings. However, the only result from algebra that we will need is the fact that if some elements of a (non-commutative) ring pairwise commute with each other, then any two polynomials of these elements commute with each other as well. (This is easy to prove.) Our goal is to prove:

[color=blue][b]Theorem 1.[/b] Let $ \mathbb{R}^{\mathbb{Z}}$ denote the commutative ring of all functions $ \mathbb{Z}\to\mathbb{R}$, where addition and multiplication are defined pointwise. We consider the commutative ring $ \mathbb{Z}^{\mathbb{Z}}$ of all functions $ \mathbb{Z}\to\mathbb{Z}$ as a subring of $ \mathbb{R}^{\mathbb{Z}}$.

Additionally, the ring $ \mathbb{R}^{\mathbb{Z}}$ has the structure of an $ \mathbb{R}$-vector space, where addition and multiplication by a scalar are defined pointwise.

The (non-commutative) ring of all endomorphisms of the $ \mathbb{R}$-vector space $ \mathbb{R}^{\mathbb{Z}}$ (not of the ring $ \mathbb{R}^{\mathbb{Z}}$ !) will be denoted by $ \text{End}_{\mathbb{R}}(\mathbb{R}^{\mathbb{Z}})$ (as usual in linear algebra). The addition in this ring is pointwise addition, but the multiplication in this ring is composition of endomorphisms (not pointwise multiplication!).

Whenever $ R: \mathbb{R}^{\mathbb{Z}}\to\mathbb{R}^{\mathbb{Z}}$ is a map and $ x\in\mathbb{R}^{\mathbb{Z}}$, we use $ Rx$ as a shorthand notation for $ R(x)$.

(An important remark about our notation:
For any two functions $ x\in\mathbb{R}^{\mathbb{Z}}$ and $ y\in\mathbb{R}^{\mathbb{Z}}$, we denote by $ xy$ (or, equivalently, $ x\cdot y$) their pointwise product (defined by $ (xy)(i) = x(i)y(i)$ for all $ i\in\mathbb{Z}$).
But for any two endomorphisms $ U\in\text{End}_{\mathbb{R}}(\mathbb{R}^{\mathbb{Z}})$ and $ V\in\text{End}_{\mathbb{R}}(\mathbb{R}^{\mathbb{Z}})$, we denote by $ UV$ (or, equivalently, $ U\cdot V$) their composition (defined by $ (UV)x = U(Vx)$ for all $ x\in\mathbb{R}^{\mathbb{Z}}$).)

We define two functions $ F_ + : \mathbb{R}^{\mathbb{Z}}\to\mathbb{R}^{\mathbb{Z}}$ and $ F_ - : \mathbb{R}^{\mathbb{Z}}\to\mathbb{R}^{\mathbb{Z}}$ as follows: For every $ x\in\mathbb{R}^{\mathbb{Z}}$, we define two elements $ F_ + x$ and $ F_ - x$ of $ \mathbb{R}^{\mathbb{Z}}$ by the equations

$ (F_ + x)(i) = \frac {x(i) + x(i + 1)}{2}$;
$ (F_ - x)(i) = \frac {x(i) - x(i + 1)}{2}$

for every $ i\in\mathbb{Z}$.

Also, let $ \mathbf{1}$ denote the identity map $ \mathbb{R}^{\mathbb{Z}}\to\mathbb{R}^{\mathbb{Z}}$.

[b](a)[/b] The functions $ \mathbf{1}$, $ F_ +$ and $ F_ -$ belong to $ \text{End}_{\mathbb{R}}(\mathbb{R}^{\mathbb{Z}})$ and commute with each other. They satisfy $ F_ + + F_ - = \mathbf{1}$.

[b](b)[/b] Let us define a function $ S: \mathbb{R}^{\mathbb{Z}}\to\mathbb{R}^{\mathbb{Z}}$ as follows: For every $ x\in\mathbb{R}^{\mathbb{Z}}$, we define an element $ Sx$ of $ \mathbb{R}^{\mathbb{Z}}$ by the equation $ (Sx)(i) = x(i + 1)$ for every $ i\in\mathbb{Z}$. Then, $ S$ is an element of $ \text{End}_{\mathbb{R}}(\mathbb{R}^{\mathbb{Z}})$ and commutes with $ \mathbf{1}$, $ F_ +$ and $ F_ -$. Besides, $ F_ + = \frac {\mathbf{1} + S}{2}$ and $ F_ - = \frac {\mathbf{1} - S}{2}$. Furthermore, $ S(\mathbb{Z}^{\mathbb{Z}})\subseteq\mathbb{Z}^{\mathbb{Z}}$.

[b](c)[/b] For every two elements $ x$ and $ y$ of $ \mathbb{R}^{\mathbb{Z}}$, we have

$ F_ - (xy) = F_ - x\cdot y + Sx\cdot F_ - y$.

(Here and in the following, operators like $ S$, $ F_ -$ and $ F_ +$ have higher priority than $ \cdot$, so that, for instance, $ Sx\cdot F_ - y$ means $ (Sx)\cdot(F_ - y)$.)

[b](d)[/b] For every two elements $ x$ and $ y$ of $ \mathbb{R}^{\mathbb{Z}}$, and for every integer $ n\geq 0$, we have

$ F_ - ^n(xy) = \sum_{k = 0}^n\binom{n}{k}\cdot S^{n - k}(F_ - ^kx)\cdot F_ - ^{n - k}y$.

From now on, let $ n\geq 0$ be a fixed integer.

[b](e)[/b] Let $ x\in\mathbb{R}^{\mathbb{Z}}$. Then, the following two assertions are equivalent:

[i]Assertion $ \mathcal{A}_ - (x)$.[/i] We have $ F_ - ^ix\in\mathbb{Z}^{\mathbb{Z}}$ for all $ i\in\{0,1,...,n\}$.

[i]Assertion $ \mathcal{A}_ + (x)$.[/i] We have $ F_ + ^ix\in\mathbb{Z}^{\mathbb{Z}}$ for all $ i\in\{0,1,...,n\}$.

A function $ x\in\mathbb{R}^{\mathbb{Z}}$ will be called [i]good[/i] if it satisfies these two equivalent assertions.

[b](f)[/b] If two functions $ x\in\mathbb{R}^{\mathbb{Z}}$ and $ y\in\mathbb{R}^{\mathbb{Z}}$ are good, then $ xy$ is good as well.

[b](g)[/b] The function that maps every $ i\in\mathbb{Z}$ to $ ( - 1)^i$ is good.[/color]

Clearly, the operator $ F_ +$ is precisely the operator that maps a function a. k. a. "infinite sequences in both directions" to its "average sequence" as defined in the original problem. Thus, the original problem will immediately follow from Theorem 1 [b](f)[/b] for $ x = y$. My assertions in post #7 follow from Theorem 1 [b](e)[/b], [b](f)[/b] and [b](g)[/b]. Of course, the original problem nowhere uses $ F_ -$, but we will use $ F_ -$ as an intermediate step of our proof - in fact, the analogue of Theorem 1 [b](d)[/b] for $ F_ +$ instead of $ F_ -$ is much uglier, so the introduction of $ F_ -$ actually makes the problem easier!

You don't need the below proof of Theorem 1 - it is straightforward and a pain to read, while all the ideas are already present in the above statement of Theorem 1. I include the proof for the sake of completeness.

[i]Proof of Theorem 1.[/i] We begin by proving points [b](a)[/b] and [b](b)[/b]:

It is clear that $ \mathbf{1}$ and $ S$ are elements of $ \text{End}_{\mathbb{R}}(\mathbb{R}^{\mathbb{Z}})$ (this just means that $ \mathbf{1}$ and $ S$ are $ \mathbb{R}$-linear maps from $ \mathbb{R}^{\mathbb{Z}}$ to $ \mathbb{R}^{\mathbb{Z}}$, what is obvious). Note that $ \mathbf{1}$ is the multiplicative unity of the ring $ \text{End}_{\mathbb{R}}(\mathbb{R}^{\mathbb{Z}})$. From $ \mathbf{1}\in\text{End}_{\mathbb{R}}(\mathbb{R}^{\mathbb{Z}})$ and $ S\in\text{End}_{\mathbb{R}}(\mathbb{R}^{\mathbb{Z}})$ we can conclude that $ \frac {\mathbf{1} + S}{2}\in\text{End}_{\mathbb{R}}(\mathbb{R}^{\mathbb{Z}})$ and $ \frac {\mathbf{1} - S}{2}\in\text{End}_{\mathbb{R}}(\mathbb{R}^{\mathbb{Z}})$ (because linear combinations of elements of $ \text{End}_{\mathbb{R}}(\mathbb{R}^{\mathbb{Z}})$ with real coefficients lie in $ \text{End}_{\mathbb{R}}(\mathbb{R}^{\mathbb{Z}})$).

For every $ x\in\mathbb{R}^{\mathbb{Z}}$, we have

$ (F_ + x)(i) = \frac {x(i) + x(i + 1)}{2} = \frac {x(i) + (Sx)(i)}{2} = (\frac {\mathbf{1} + S}{2}x)(i)$

for every $ i\in\mathbb{Z}$, and therefore $ F_ + x = \frac {\mathbf{1} + S}{2}x$. Thus, $ F_ + = \frac {\mathbf{1} + S}{2}$. Similarly, $ F_ - = \frac {\mathbf{1} - S}{2}$. Thus, $ \frac {\mathbf{1} + S}{2}\in\text{End}_{\mathbb{R}}(\mathbb{R}^{\mathbb{Z}})$ and $ \frac {\mathbf{1} - S}{2}\in\text{End}_{\mathbb{R}}(\mathbb{R}^{\mathbb{Z}})$ become $ F_ + \in\text{End}_{\mathbb{R}}(\mathbb{R}^{\mathbb{Z}})$ and $ F_ - \in\text{End}_{\mathbb{R}}(\mathbb{R}^{\mathbb{Z}})$.

Besides, $ F_ + = \frac {\mathbf{1} + S}{2}$ and $ F_ - = \frac {\mathbf{1} - S}{2}$ yield that $ F_ +$ and $ F_ -$ are polynomials of $ S$, so that all four operators $ \mathbf{1}$, $ S$, $ F_ +$ and $ F_ -$ commute with each other.

Clearly, $ S(\mathbb{Z}^{\mathbb{Z}})\subseteq\mathbb{Z}^{\mathbb{Z}}$, because for every $ x\in\mathbb{Z}^{\mathbb{Z}}$, we have $ Sx\in\mathbb{Z}^{\mathbb{Z}}$ (because $ x\in\mathbb{Z}^{\mathbb{Z}}$ yields $ x(i)\in\mathbb{Z}$ for every $ i\in\mathbb{Z}$, thus also $ x(i + 1)\in\mathbb{Z}$ for every $ i\in\mathbb{Z}$, and hence $ (Sx)(i) = x(i + 1)\in\mathbb{Z}$ for every $ i\in\mathbb{Z}$, so that $ Sx\in\mathbb{Z}^{\mathbb{Z}}$). This completes the proof of Theorem 1 [b](b)[/b].

We have already proven that the operators $ \mathbf{1}$, $ F_ +$ and $ F_ -$ belong to $ \text{End}_{\mathbb{R}}(\mathbb{R}^{\mathbb{Z}})$ and commute with each other. Besides, $ F_ + + F_ - = \mathbf{1}$ follows from $ F_ + = \frac {\mathbf{1} + S}{2}$ and $ F_ - = \frac {\mathbf{1} - S}{2}$. Thus, Theorem 1 [b](a)[/b] is also proven.

Theorem 1 [b](c)[/b] follows from a simple computation: For every $ i\in\mathbb{Z}$, we have

$ (F_ - (xy))(i) = \frac {(xy)(i) - (xy)(i + 1)}{2} = \frac {x(i)y(i) - x(i + 1)y(i + 1)}{2}$
$ = \frac {x(i) - x(i + 1)}{2}\cdot y(i) + x(i + 1)\cdot\frac {y(i) - y(i + 1)}{2}$
$ = (F_ - x)(i)\cdot y(i) + (Sx)(i)\cdot(F_ - y)(i) = (F_ - x\cdot y + Sx\cdot F_ - y)(i)$.

Thus, $ F_ - (xy) = F_ - x\cdot y + Sx\cdot F_ - y$, proving Theorem 1 [b](c)[/b].

Now we will show Theorem 1 [b](d)[/b] by induction over $ n$: The induction base ($ n = 0$) is obvious. Now to the induction step: Assume that Theorem 1 [b](d)[/b] is proven for some integer $ n\geq 0$. That is, for some integer $ n\geq 0$ we have shown that

[color=green][b](1)[/b][/color] $ F_ - ^n(xy) = \sum_{k = 0}^n\binom{n}{k}\cdot S^{n - k}(F_ - ^kx)\cdot F_ - ^{n - k}y$.

We now have to show that Theorem 1 [b](d)[/b] also holds for $ n + 1$ in place of $ n$; that is, we have to prove that

[color=green][b](2)[/b][/color] $ F_ - ^{n + 1}(xy) = \sum_{k = 0}^{n + 1}\binom{n + 1}{k}\cdot S^{n + 1 - k}(F_ - ^kx)\cdot F_ - ^{n + 1 - k}y$.

So let us do this now: For every $ k\in\{0,1,...,n\}$ we have

[color=green][b](3)[/b][/color] $ F_ - ( S^{n - k}(F_ - ^kx)\cdot F_ - ^{n - k}y )$
$ = F_ - (S^{n - k}(F_ - ^kx))\cdot F_ - ^{n - k}y + S(S^{n - k}(F_ - ^kx))\cdot F_ - (F_ - ^{n - k}y)$    (by Theorem 1 [b](c)[/b], applied to $ S^{n - k}(F_ - ^kx)$ and $ F_ - ^{n - k}y$ instead of $ x$ and $ y$)
$ = F_ - (S^{n - k}(F_ - ^kx))\cdot F_ - ^{n - k}y + S^{n + 1 - k}(F_ - ^kx)\cdot F_ - ^{n + 1 - k}y$       (since $ S(S^{n - k}(F_ - ^kx)) = S^{n + 1 - k}(F_ - ^kx)$ and $ F_ - (F_ - ^{n - k}y) = F_ - ^{n + 1 - k}y$)
$ = S^{n - k}(F_ - ^{k + 1}x)\cdot F_ - ^{n - k}y + S^{n + 1 - k}(F_ - ^kx)\cdot F_ - ^{n + 1 - k}y$      (since $ F_ - (S^{n - k}(F_ - ^kx)) = S^{n - k}(F_ - ^{k + 1}x)$, because $ S$ and $ F_ -$ commute).

Thus,

$ F_ - ^{n + 1}(xy) = F_ - (F_ - ^n(xy)) = F_ - (\sum_{k = 0}^n\binom{n}{k}\cdot S^{n - k}(F_ - ^kx)\cdot F_ - ^{n - k}y)$       (by [color=green][b](1)[/b][/color])
$ = \sum_{k = 0}^n\binom{n}{k}\cdot F_ - ( S^{n - k}(F_ - ^kx)\cdot F_ - ^{n - k}y) )$    (because $ F_ -$ is a linear map, since $ F_ - \in\text{End}_{\mathbb{R}}(\mathbb{R}^{\mathbb{Z}})$)
$ = \sum_{k = 0}^n\binom{n}{k}\cdot( S^{n - k}(F_ - ^{k + 1}x)\cdot F_ - ^{n - k}y + S^{n + 1 - k}(F_ - ^kx)\cdot F_ - ^{n + 1 - k}y )$       (by [color=green][b](3)[/b][/color])
$ = \sum_{k = 0}^n\binom{n}{k}\cdot S^{n - k}(F_ - ^{k + 1}x)\cdot F_ - ^{n - k}y + \sum_{k = 0}^n\binom{n}{k}\cdot S^{n + 1 - k}(F_ - ^kx)\cdot F_ - ^{n + 1 - k}y$
$ = \sum_{k = - 1}^n\binom{n}{k}\cdot S^{n - k}(F_ - ^{k + 1}x)\cdot F_ - ^{n - k}y + \sum_{k = 0}^{n + 1}\binom{n}{k}\cdot S^{n + 1 - k}(F_ - ^kx)\cdot F_ - ^{n + 1 - k}y$    (here we have inserted two additional terms into the two sums (namely, the $ k = - 1$ term into the first sum and the $ k = n + 1$ term into the second sum), but the sums did not change, because these terms are both $ 0$ (since $ \binom{n}{k} = 0$ for $ k = - 1$ and for $ k = n + 1$))
$ = \sum_{k = 0}^{n + 1}\binom{n}{k - 1}\cdot S^{n - (k - 1)}(F_ - ^{(k - 1) + 1}x)\cdot F_ - ^{n - (k - 1)}y$
$ + \sum_{k = 0}^{n + 1}\binom{n}{k}\cdot S^{n + 1 - k}(F_ - ^kx)\cdot F_ - ^{n + 1 - k}y$    (here we have substituted $ k$ by $ k - 1$ in the first sum)
$ = \sum_{k = 0}^{n + 1}\binom{n}{k - 1}\cdot S^{n + 1 - k}(F_ - ^kx)\cdot F_ - ^{n + 1 - k}y$
$ + \sum_{k = 0}^{n + 1}\binom{n}{k}\cdot S^{n + 1 - k}(F_ - ^kx)\cdot F_ - ^{n + 1 - k}y$
$ = \sum_{k = 0}^{n + 1} (\binom{n}{k - 1} + \binom{n}{k}) \cdot S^{n + 1 - k}(F_ - ^kx)\cdot F_ - ^{n + 1 - k}y$
$ = \sum_{k = 0}^{n + 1} \binom{n + 1}{k} \cdot S^{n + 1 - k}(F_ - ^kx)\cdot F_ - ^{n + 1 - k}y$      (since $ \binom{n}{k - 1} + \binom{n}{k} = \binom{n + 1}{k}$),

and [color=green][b](2)[/b][/color] is proven. Thus, the induction step is complete, and Theorem 1 [b](d)[/b] is established.

Next, we will verify Theorem 1 [b](e)[/b]. First let us show that $ \mathcal{A}_ - (x)\Longrightarrow\mathcal{A}_ + (x)$:

Assume that Assertion $ \mathcal{A}_ - (x)$ holds. Then, $ F_ - ^ix\in\mathbb{Z}^{\mathbb{Z}}$ for all $ i\in\{0,1,...,n\}$. The equation $ F_ + + F_ - = \mathbf{1}$ yields $ F_ + = \mathbf{1} - F_ -$. Hence, for every $ i\in\{0,1,...,n\}$, we have

$ F_ + ^i = (\mathbf{1} - F_ - )^i = \sum_{k = 0}^i( - 1)^{i - k}\binom{i}{k}\mathbf{1}^kF_ - ^{i - k}$     (by the binomial theorem, since $ \mathbf{1}$ and $ F_ -$ commute)
$ = \sum_{k = 0}^i( - 1)^{i - k}\binom{i}{k}F_ - ^{i - k}$.

Thus,

$ F_ + ^ix = (\sum_{k = 0}^i( - 1)^{i - k}\binom{i}{k}F_ - ^{i - k})x = \sum_{k = 0}^i( - 1)^{i - k}\binom{i}{k}\cdot \underbrace{F_ - ^{i - k}x}_{\in\mathbb{Z}^{\mathbb{Z}}}$      (here, $ F_ - ^{i - k}x\in\mathbb{Z}^{\mathbb{Z}}$ follows from Assertion $ \mathcal{A}_ - (x)$ because of $ i - k\in\{0,1,...,n\}$)
$ \in\mathbb{Z}^{\mathbb{Z}}$       (because $ \mathbb{Z}^{\mathbb{Z}}$ is a ring).

So we see that $ F_ + ^ix\in\mathbb{Z}^{\mathbb{Z}}$ for all $ i\in\{0,1,...,n\}$. That is, Assertion $ \mathcal{A}_ + (x)$ holds. We have therefore derived Assertion $ \mathcal{A}_ + (x)$ from Assertion $ \mathcal{A}_ - (x)$. Hence, $ \mathcal{A}_ - (x)\Longrightarrow\mathcal{A}_ + (x)$. A completely analogous argument shows $ \mathcal{A}_ + (x)\Longrightarrow\mathcal{A}_ - (x)$. Thus, $ \mathcal{A}_ - (x)\Longleftrightarrow\mathcal{A}_ + (x)$, and Theorem 1 [b](e)[/b] is proven.

Now let us prove Theorem 1 [b](f)[/b]: Since the function $ x$ is good, it satisfies Assertion $ \mathcal{A}_ - (x)$; thus,

[color=green][b](4)[/b][/color] $ F_ - ^ix\in\mathbb{Z}^{\mathbb{Z}}$ for all $ i\in\{0,1,...,n\}$.

Similarly,

[color=green][b](5)[/b][/color] $ F_ - ^iy\in\mathbb{Z}^{\mathbb{Z}}$ for all $ i\in\{0,1,...,n\}$.

Now, pick a $ i\in\{0,1,...,n\}$. Then, Theorem 1 [b](d)[/b] yields

$ F_ - ^i(xy) = \sum_{k = 0}^i\binom{i}{k}\cdot S^{i - k}(F_ - ^kx)\cdot F_ - ^{i - k}y$.

For every $ k\in\{0,1,...,i\}$, we have $ F_ - ^kx\in\mathbb{Z}^{\mathbb{Z}}$ (by [color=green][b](4)[/b][/color], because $ k\in\{0,1,...,n\}$) and thus $ S^{i - k}(F_ - ^kx)\in\mathbb{Z}^{\mathbb{Z}}$ (since $ S^{i - k}(\mathbb{Z}^{\mathbb{Z}})\subseteq\mathbb{Z}^{\mathbb{Z}}$, what follows by iteration from $ S(\mathbb{Z}^{\mathbb{Z}})\subseteq\mathbb{Z}^{\mathbb{Z}}$). Also, $ F_ - ^{i - k}y\in\mathbb{Z}^{\mathbb{Z}}$ (by [color=green][b](5)[/b][/color], because $ i - k\in\{0,1,...,n\}$). Thus,

$ F_ - ^i(xy) = \sum_{k = 0}^i\binom{i}{k}\cdot \underbrace{S^{i - k}(F_ - ^kx)}_{\in\mathbb{Z}^{\mathbb{Z}}}\cdot \underbrace{F_ - ^{i - k}y}_{\in\mathbb{Z}^{\mathbb{Z}}}\in\mathbb{Z}^{\mathbb{Z}}$

(because $ \mathbb{Z}^{\mathbb{Z}}$ is a ring). So we have proven that $ F_ - ^i(xy)\in\mathbb{Z}^{\mathbb{Z}}$ for all $ i\in\{0,1,...,n\}$. Thus, the function $ xy$ satisfies Assertion $ \mathcal{A}_ - (xy)$. Hence, $ xy$ is good, and Theorem 1 [b](f)[/b] is proven.

Finally we will show Theorem 1 [b](g)[/b]:

Define the function $ m\in\mathbb{R}^{\mathbb{Z}}$ by $ m(i) = ( - 1)^i$ for every $ i\in\mathbb{Z}$. Then, Theorem 1 [b](g)[/b] states that this function $ m$ is good. Let us prove this now.

Define the function $ \overrightarrow{0}\in\mathbb{R}^{\mathbb{Z}}$ by $ \overrightarrow{0}(i) = 0$ for every $ i\in\mathbb{Z}$. This function $ \overrightarrow{0}$ is the zero of the ring $ \mathbb{R}^{\mathbb{Z}}$.

Both functions $ m$ and $ \overrightarrow{0}$ obviously lie in $ \mathbb{Z}^{\mathbb{Z}}$. Besides, for every $ i\in\mathbb{Z}$, we have

$ (F_ + m)(i) = \frac {m(i) + m(i + 1)}{2} = \frac {( - 1)^i + ( - 1)^{i + 1}}{2} = \frac {( - 1)^i - ( - 1)^i}{2} = 0$
$ = \overrightarrow{0}(i)$,

so that $ F_ + m = \overrightarrow{0}$.

Thus, for every $ i\in\{0,1,...,n\}$, we have $ F_ + ^im\in\mathbb{Z}^{\mathbb{Z}}$ (because for $ i = 0$, we have $ F_ + ^im = F_ + ^0m = m\in\mathbb{Z}^{\mathbb{Z}}$, and for $ i\geq 1$, we have

$ F_ + ^im = F_ + ^{i - 1}(F_ + m) = F_ + ^{i - 1}(\overrightarrow{0}) = \overrightarrow{0}$       (since $ F_ + ^{i - 1}$ is a linear map)
$ \in\mathbb{Z}^{\mathbb{Z}}$).

Thus, the function $ m$ satisfies Assertion $ \mathcal{A}_ + (m)$. Hence, $ m$ is good, and Theorem 1 [b](g)[/b] is proven. The proof of Theorem 1 is thus complete.

  darij

Actually, these solutions are far from what I expect from a Russian question.(I don't mean beauty. They are long at first, moreover one of them requires computation and the other needs knowladge) There must be another one. Andrei you have written the question, maybe you can inform us. What is the solution you know?

I believe, you all overestimate the problem a bit. To be perfectly honest, it is not hard to come up with a solution. I would consider the problem to be "if-you-guess-the-very-first-step-the-problem-is-almost-solved".

[i]The second account of Erken.[/i]

Is this helpful?
$ a_k' \equal{} \frac {a_k \plus{} a_{k \plus{} 1}}2$
$ a_k'' \equal{} \frac {a_k \plus{}2 a_{k \plus{} 1}\plus{}a_{k\plus{}2}}{2^2}$
$ a_k''' \equal{} \frac {a_k \plus{}3 a_{k \plus{} 1}\plus{}3a_{k\plus{}2}\plus{}a_{k\plus{}3}}{2^3}$
$ \cdots$

[b]@Erken[/b]: I am somewhat surprised that an experienced-enough problem solver like you says this. By now, you certainly know that solving a problem quickly doesn't mean the problem is easy. It is correct that most difficult Russian problems involve a single idea, but most of the times you must be either very lucky or have very trained insight to find it.

[b]@mszew[/b]: I guess not  :D

[hide="Official Solution"]
Call a sequence [i]$ m$-good[/i] if the sequence and its first $ m$ averages consist of integer numbers. We prove by induction that if a sequence $ \{x_k\}$ is $ m$-good, then so is $ \{x_k^2\}$.

The base of our induction, $ m\equal{}0$ is trivial, for a $ 0$ good sequence has only integer numbers, as their squares are. Assume now $ \{x_k\}$ is $ m\plus{}1$-good and we'll show that $ \{x_k^2\}$ is $ m\plus{}1$-good.

Note that if $ \{x_k\}$ is $ m\plus{}1$-good then $ \dfrac{x_k\plus{}x_{k\plus{}1}}2$, $ \dfrac{x_k\plus{}x_{k\plus{}1}}2\minus{}x_{k\plus{}1}$ are $ m$-good. Using the induction hypothesis for the above-mentioned sequences, we have that their squares are $ m$-good. This implies $ \dfrac{x_k^2\plus{}x_{k\plus{}1}^2}2\equal{}\left(\dfrac{x_k\plus{}x_{k\plus{}1}}2\right)^2\plus{}\left(\dfrac{x_k\minus{}x_{k\plus{}1}}2\right)^2\equal{}$ $ \left(\dfrac{x_k\plus{}x_{k\plus{}1}}2\right)^2\plus{}\left(\dfrac{x_k\plus{}x_{k\plus{}1}}2\minus{}x_{k\plus{}1}\right)^2$ is $ m$-good, or that $ \{x_k^2\}$ is $ m\plus{}1$-good $ \blacksquare$

[/hide]
The official solution was also followed by two remarks:

[i]Remark 1[/i]
The sequence need not be constant, an example being the sequence $ \ldots,\minus{}3,\minus{}1,1,3,5,7,\ldots$.

[i]Remark 2[/i]
Modify the problem and define the average sequence as $ \{a_k'\}\equal{}\dfrac{a_k\plus{}\ldots\plus{}a_{k\plus{}p\minus{}1}}p$, where $ p$ is a fixed positive integer. It can be proved that for $ p\equal{}3$ a similar statement holds: if $ \{x_k\}$ is good, then so is $ \{x_k^p\}$. A further problem is determining for which $ p$ this is true. A conjecture is - only for primes $ p$.

I am thinking of maybe starting a new topic for this problem, what do you guys think? I haven't analyzed [b]darij[/b]'s solution (too long :D) yet, so I don't know if it gives some insights for this.

[quote="freemind"]Call a sequence [i]$ m$-good[/i] if the sequence and its first $ m$ averages consist of integer numbers. We prove by induction that if a sequence $ \{x_k\}$ is $ m$-good, then so is $ \{x_k^2\}$.

The base of our induction, $ m \equal{} 0$ is trivial, for a $ 0$ good sequence has only integer numbers, as their squares are. Assume now $ \{x_k\}$ is $ m \plus{} 1$-good and we'll show that $ \{x_k^2\}$ is $ m \plus{} 1$-good.

Note that if $ \{x_k\}$ is $ m \plus{} 1$-good then $ \dfrac{x_k \plus{} x_{k \plus{} 1}}2$, $ \dfrac{x_k \plus{} x_{k \plus{} 1}}2 \minus{} x_{k \plus{} 1}$ are $ m$-good. Using the induction hypothesis for the above-mentioned sequences, we have that their squares are $ m$-good. This implies $ \dfrac{x_k^2 \plus{} x_{k \plus{} 1}^2}2 \equal{} \left(\dfrac{x_k \plus{} x_{k \plus{} 1}}2\right)^2 \plus{} \left(\dfrac{x_k \minus{} x_{k \plus{} 1}}2\right)^2 \equal{}$ $ \left(\dfrac{x_k \plus{} x_{k \plus{} 1}}2\right)^2 \plus{} \left(\dfrac{x_k \plus{} x_{k \plus{} 1}}2 \minus{} x_{k \plus{} 1}\right)^2$ is $ m$-good, or that $ \{x_k^2\}$ is $ m \plus{} 1$-good $ \blacksquare$[/quote]

Wow, this is so nice! And it generalizes to a proof of Theorem 1 [b](f)[/b]:

$ \frac {x_ky_k \plus{} x_{k \plus{} 1}y_{k \plus{} 1}}{2} \equal{} \frac {x_k \plus{} x_{k \plus{} 1}}{2}\cdot\frac {y_k \plus{} y_{k \plus{} 1}}{2} \plus{} \frac {x_k \minus{} x_{k \plus{} 1}}{2}\cdot\frac {y_k \minus{} y_{k \plus{} 1}}{2}$.

In my terminology, this is equivalent to

$ F_ \plus{} \left(xy\right) \equal{} F_ \plus{} x\cdot F_ \plus{} y \plus{} F_ \minus{} x\cdot F_ \minus{} y$.

[quote="freemind"][i]Remark 2[/i]
Modify the problem and define the average sequence as $ \{a_k'\} \equal{} \dfrac{a_k \plus{} \ldots \plus{} a_{k \plus{} p \minus{} 1}}p$, where $ p$ is a fixed positive integer. It can be proved that for $ p \equal{} 3$ a similar statement holds: if $ \{x_k\}$ is good, then so is $ \{x_k^p\}$. A further problem is determining for which $ p$ this is true. A conjecture is - only for primes $ p$.[/quote]

Is it at least true for primes $ p$?
Ah, I've got the source now ([url=http://kvant.mirror1.mccme.ru/1993/06/XIX_vserossijskaya_olimpiada_s.htm]last page here[/url] and [url=http://kvant.mirror1.mccme.ru/1993/06/otvety_ukazaniya_resheniya.htm]pre-last page here[/url]). Proven for $ p\equal{}3$, conjectured for primes beyound that.

I will post again when I know more; currently, I am pretty sure this stuff is related to a bialgebra structure on (a reasonable subalgebra of) $ \mathrm{End}_{\mathbb{R}}\left(\mathbb{R}^{\mathbb{Z}}\right)$.

  darij

This is definitely what I was looking for, thanks Andrei.


[quote="arkgnael"]$ S \equal{}\sum_{i \equal{} 5}^{n}{\frac{2i\minus{}5}{\left({i\minus{}2}\right)i^{2}}}$[/quote]

$ \frac{2i\minus{}5}{({i\minus{}2})i^{2}}\equal{}\frac{5}{2i^{2}}\plus{}\frac{1}{4}(\frac{1}{i}\minus{}\frac{1}{i\minus{}2})$ so $ S_{n}\equal{}\frac{5}{2}\sum_{i \equal{} 5}^{n}\frac{1}{i^{2}}\plus{}\frac{1}{4}(\frac{1}{n}\plus{}\frac{1}{n\minus{}1}\minus{}\frac{1}{3}\minus{}\frac{1}{4})$ $ \forall n>5$

I don't think there is an expression without $ \sum$.

If you are looking for the limit, you have $ \lim_{n\rightarrow\plus{}\infty}S_{n}\equal{}\frac{5}{2}(\frac{\pi^{2}}{6}\minus{}1\minus{}\frac{1}{4}\minus{}\frac{1}{9}\minus{}\frac{1}{16})\minus{}\frac{1}{4}(\frac{1}{3}\plus{}\frac{1}{4})$ $ \equal{}\frac{5\pi^{2}}{12}\minus{}\frac{1067}{288}$

But I don't think it's an olympiad exercise ...


Euler
function
number theory open
number theory

Is is true, that if $\varphi(ab)=\varphi(a)\varphi(b)$, then $(a,b)=1$ :?:

i think that  $\varphi(ab)=\varphi(a)\varphi(b)$ iff $(a,b)=1$
just see the common factors, because the others will cut then just show that $\varphi(ab)\geq \varphi(a)\varphi(b)$ equality occurs when $(a,b)=1$


with $ a,b,c>0$. Prove that
        $ \sum{ \frac{1}{ \sqrt{a^2+bc}}} \geq \sum{ \frac{1}{ \sqrt{a^2+b^2}}}$

[quote="2424"]with $ a,b,c > 0$. Prove that
        $ \sum{\frac {1}{\sqrt {a^2 + bc}}} \geq \sum{\frac {1}{\sqrt {a^2 + b^2}}}$[/quote]
Try $ a=b=1$ and $ c=3.$


How do I prove the following:

Let X and Y be discrete random variables. Show that
E[(X^2)Y given X] = (X^2)E[Y given X]

Thanks for any help.

This is just linearity of expected value- $ X^2$ is a constant here.

Is there some way I can show it using the definitions and such? Thanks for the response.

Try rewriting your notation so that $ X$ doesn't stand for two different things. Once you do that, it should be obvious.

Right, I understand the linearity, but it applies here even with the X on the other side?

Once we've conditioned on a specific value, $ X$ is not a variable. Try using a different symbol for the original variable and the value we condition on, such as $ E(X^2\cdot Y\text{ given }X\equal{}x) \equal{} E(x^2\cdot Y\text{ given }X\equal{}x) \equal{} x^2\cdot E(Y\text{ given }X\equal{}x)$

You might notice me using exactly the same language jmerry just used on [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=253549]your other topic.[/url]


Let $ (O)$ be a circle with Diameter $ AB$.$ C;D$ in this circle.$ CD$ cuts $ AB$ at $ M$ such that $ MB<MA;MB<MC$.Circumcircle of triangle $ BCO$ cuts circumcircle of triangle $ BDO$ at $ K$$ (K \neq O)$.Prove that $ \angle MKO\equal{}90^o$

[quote="chien than"]Circumcircle of triangle $ BCO$ cuts circumcircle of triangle $ BDO$ at $ K$$ (K \neq O)$.[/quote]
I'm sure that you have a typo mistake. K is the intersection of circle BCO and circle ADO, not BDO as you wrote.

[quote="chien than"]Let $ (O)$ be a circle with Diameter $ AB$.$ C;D$ in this circle.$ CD$ cuts $ AB$ at $ M$ such that $ MB < MA;MD < MC$.Circumcircle of triangle $ ACO$ cuts circumcircle of triangle $ BDO$ at $ K$$ (K \neq O)$.Prove that $ \angle MKO \equal{} 90^o$[/quote]
I correct it :D
[img]http://i209.photobucket.com/albums/bb172/Ineq/Circle.jpg[/img]
Easy to prove $ AC,BD,OK$ concurent
and $ M$ lie on polar of $ N$ respect to $ (O)$
We have
$ P_{N|(ACO)} \equal{} P_{N|(BDO)} \equal{} P_{N|(O)} \\
\Rightarrow NK.NO \equal{} NP.NQ \Rightarrow (NKPQ) \equal{} \minus{} 1$
so $ K$ lie on polar of $ N$ respect to $ (O)$
$ \Rightarrow$ $ MK$ is polar of $ N$ respect to $ (O)$
$ \Rightarrow KM\perp KO$ so $ \angle MKO \equal{} 90^o$
:D


This is knind of easy, actually, you just use (a^3+b^3+c^3)/(a+b+c) >= (a^2+b^2+c^2)/3. For this we just use rearrangement ineq a couple of times.


[quote="shobber"]Find out the smallest real number $m$, such that for all positive real number $a,b,c$ with $a+b+c=1$, $m(a^{3}+b^{3}+c^{3})\geq 6(a^{2}+b^{2}+c^{2})+1$.[/quote]
$m(a^{3}+b^{3}+c^{3})\geq 6(a^{2}+b^{2}+c^{2})+1\Leftrightarrow$
$\Leftrightarrow m(a^{3}+b^{3}+c^{3})\geq6(a+b+c)(a^{2}+b^{2}+c^{2})+(a+b+c)^{3}\Leftrightarrow$
$\Leftrightarrow\sum_{cyc}((m-7)a^{3}-9a^{2}b-9a^{2}c-2abc)\geq0.$
If $a=b=c$ then $m-7-9-9-2\geq0.$ Hence, $m\geq27$ and
$\sum_{cyc}(20a^{3}-9a^{2}b-9a^{2}c-2abc)\geq0$ is obviously true.

My solution:
$27(\sum a^{3})$
$=3(\sum a^{3})(\sum 9a)$
$\geq 3(\sum 3a^{2})^{2}$ (Cauchy)
$\geq 9(\sum a^{2})$ (Power Mean)
$=6(\sum a^{2})+3(\sum a^{2})$
$\geq 6(\sum a^{2})+1$ (Power Mean)
 I think this question is similar to this year CHKMO Problem 3 but this is in 3 variables, I able to finish it very quickly during the competition :P

Also mixing variables works - I won't post solution as it is a little bit longer than those presented above.

One line solution
$27\sum a^{3}-6\sum a^{2}-1\geq 0$ is equivalent to
$\sum\frac{(3a-1)^{2}(4+9a)}{3}\geq 0$ which is trivial.....

and my solution shows that the inequality holds for
$a,b,c\geq-\frac{4}{9}$

Undoubtedlly there are still many possible solutions to the problem, mainly because of the extremely "strong" term (3,0,0) on the LHS.

Actaully I wonder how come such kind of "Muirhead-killable" inequality still appears in a contest...

[b]generalize[/b]
Let $a_{i}> 0(i = 1,2, \cdots ,n),n \in N,n \ge 2,\sum_{i = 1}^{n}{a_{i}= 1}$,Prove that
$3n^{2}\sum_{i = 1}^{n}{a_{i}^{3}}\ge 2n\sum_{i = 1}^{n}{a_{i}^{2}}+1$

n=3,3rd China Southeast MO  Problem 6

n=4, 8th Hong Kong(china) MO Problem 3

[quote="arqady"]
$\sum_{cyc}((m-7)a^{3}-9a^{2}b-9a^{2}c-2abc)\geq0.$
[/quote]

Sorry, but I'm trying to start solving inequalities.

What is that "cyc" below the sigma?? What does it mean and how do I use it?


Easy solution first:  $(-1, 1, 1)$ and permutations.

Too much algebra for the other solutions.   :(

Given $f$ with zeroes $x,y,z$ we know:

$f(r) = r^3 - (x + y +z)r^2 + (xy + xz + yz)r - xyz$

We can find an easy recursion from this:

$0 \cdot (x^{n-3}) = f(x) \cdot (x^{n-3}) = x^n - (x + y +z)x^{n-1} + (xy + xz + yz)x^{n-2} - (xyz)x^{n-3}$

$0 \cdot (y^{n-3}) = f(y) \cdot (y^{n-3}) = y^n - (x + y +z)y^{n-1} + (xy + xz + yz)y^{n-2} - (xyz)y^{n-3}$

$0 \cdot (z^{n-3}) = f(z) \cdot (z^{n-3}) = z^n - (x + y +z)z^{n-1} + (xy + xz + yz)z^{n-2} - (xyz)z^{n-3}$

Now, say $S_n = x^n + y^n + z^n$. Adding our 3 equations together, we get:

$0 = S_n - (x + y +z)S_{n-1} + (xy + xz + yz)S_{n-2} - (xyz)S_{n-3}$

We know $x + y + z = 1 \Rightarrow 1 = (x+y+z)^2 = x^2 + y^2 + z^2 + 2xy +2xz + 2yz$

$= 3 + 2(xy+xz+yz) \Rightarrow xy + xz + yz = -1$

Now, we say $xyz = K$

This gives us:

$S_n - S_{n-1} - S_{n-2} - KS_{n-3} = 0$

$\Rightarrow S_3 - S_{2} - S_{1} - KS_{0} = 0$

$S_0 = x^0 + y^0 + z^0 = 1 + 1 + 1 = 3$

$\Rightarrow S_3 - 3 - 1 - 3K = 0 \Rightarrow S_3 = 4 + 3K$

We now use our recurrence to find $K$.

$S_4 - S_{3} - S_{2} - KS_{1} = 0 \Rightarrow - S_{3} - S_{2} - KS_{1} = -S_4$

$0 = S_5 - S_{4} - S_{3} - KS_{2} = S_5 - S_{3} - S_{2} - KS_{1} - S_{3} - KS_{2}$

$= S_5 - 2S_{3} - (1+K)S_{2} - KS_{1} = 1 - 2(4+3K) - (1+K)3 - K$

$K = -1$

So, now we know $x,y,z$ are solutions to the $f$ and we have all of the coefficients:

$x + y + z = S_1 = 1$

$xy + xz + yz = \frac{S_1^2 - S_2}{2} = -1$

$xyz = K = -1$

$\Rightarrow f(r) = r^3 - r^2 - r + 1$

The zeroes of $f$ are ${-1,1,1}$ and thus those are the only solutions.

P.S. I was thinking of using my method posted [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=279446&highlight=#279446]here[/url] to find the sums of $r = x$, $r = x^2$ and $r=x^5$. Go there, I like it :lol:.

[hide]say we have a monic polynomial with roots x,y,z

$f(n)=n^3+an^2+bx+c$

using [b]newton's sums[/b], $a=-1$

$1*3+-1(1)+2b=0$, $b=-1$

uugh, the next one is a pain...using newton's sums...

$1*s_3-1*3-1*1+3c=0$
$s_3=4-3c$
$1*s_4-1(4-3c)-1*3+c*1=0$
$s_4=7-4c$
$1*s_5-1(7-4c)-1(4-3c)+c*3=0$
$c=1$

so our polynomial is

$n^3-n^2-n+1=(n-1)(n^2-1)=(n-1)^2(n+1)$, so our solutions are $(-1,-1,1)$, and any permutation

it might be hard to understand, so you should look at the section about newton's sums in aops volume 2, i just used the formulas
[/hide]

EDIT: woops, i did not notice that this was already done...oh well


calculus
integration
trigonometry
function
real analysis
real analysis unsolved

Show that for $ x >0$

$ \int^x_0  \frac{\sin t}{1\plus{}t}\,dt    > 0$

More generally: suppose that $ g(x)$ is positive and nonincreasing on $ [0,\infty).$ Then $ \int_0^xg(t)\sin t\,dt \ge 0$ for all $ x > 0.$

In other words, the only properties of $ \frac1{1 \plus{} x}$ that we'll use are that it is positive and decreasing.

For the proof below, I will assume that $ g$ is reasonably smooth ($ C^1,$ say), but we could accommodate more general monotone functions in the same proof by using Stieljes integrals. I will also assume that $ g(0)$ is finite although that could be weakened to allow some possible rates of growth in $ g(t)$ as $ t\to 0$ - the structure of the proof will tell us what we can get away with there.

We integrate by parts, and use $ 1 \minus{} \cos t$ as the antiderivative of $ \sin t.$

$ \int_0^xg(t)\sin t\,dt \equal{} g(t)(1 \minus{} \cos t)\bigg{|}_0^x \minus{} \int_0^xg'(t)(1 \minus{} \cos t)\,dt$

$ \equal{} g(x)(1 \minus{} \cos x) \plus{} \int_0^x( \minus{} g'(t))(1 \minus{} \cos t)\,dt.$

Since $ 1 \minus{} \cos x\ge 0,\ g(x)\ge 0,$ and $ \minus{} g'(x)\ge 0,$ all parts of this last expression are nonnegative, and we are done.

Oh, I remember the past my post, [url=http://www.mathlinks.ro/viewtopic.php?p=192888&search_id=177335804#192888]here is[/url].

On which topic I made essentially the same post. So I repeat myself.

[color=blue]Congratulations on your $ \geq 10000$ posts, Kent Merryfield. [/color]:lol:

I wonder when will I reach 10000 posts? :)

Easy proof for this problem is the following
$ [0,x] \equal{} [0,\pi]\bigcup[\pi,2\pi]\bigcup...\bigcup[l \pi,x]$, where $ l\equal{}max(m \in \mathbb{N}: m \pi \leq x)$
and then note that $ f(t) \equal{} \frac {1} {t \plus{} 1}$ is a monotone hence
$ f(t),t \in [0,\pi]$ is bigger then $ f(t),t \in [\pi,2\pi]$ for all $ t$ and hence
$ \int \limits^{\pi}_{0}f(t) \cdot \sin t dt$>$ \int\limits^{2\pi}_{\pi}f(t) \sin t dt$ and so on. From additivity of and integral we have our statement.


limit
real analysis
real analysis unsolved

This is a classic telescoping product. $k^3-1=(k-1)(k^2+k+1)$ and $(k^3+1)=(k+1)(k^2-k+1)$. Note that $(k+1)^2-(k+1)+1=k^2+k+1$.

Now, the product is $\frac{3\cdot3\cdot4\cdot7\cdot5\cdot13\cdots}{1\cdot7\cdot2\cdot13\cdot3\cdot21\cdots} =\frac3{1\cdot2}\cdot\frac{n(n+1)}{n^2+n+1}$. As $n%Error. "toinfty" is a bad command.
$, $\frac{n(n+1)}{n^2+n+1}$ clearly goes to 1, so the infinite product is $\frac32$.


function
trigonometry
real analysis
real analysis unsolved

Prove that function:
\[ f(x)\equal{}\sum_{k\equal{}1}^{\infty}\frac{1}{2^{k}}\cos(13^{k}\pi x)\]
is uniformly continous

try to Google before post those kind of problems..

This Function ins't interesting about it be continuous, but about not be differentiable.

see:

http://epubl.ltu.se/1402-1617/2003/320/index-en.html

[quote="EulerIntegral"]http://epubl.ltu.se/1402-1617/2003/320/index-en.html[/quote]

I looked through that; he gave a proof that the Weierstrass function is continuous, but he didn't give a proof that it's uniformly continuous.

We want to show that, for any $ \varepsilon > 0$, there exists a $ \delta > 0$ so that, for all $ x, y$ such that $ |y - x| < \delta$, $ |W(y) - W(x)| < \varepsilon$. What I have so far:

\[ |W(y) - W(x)| = \left|\sum^{\infty}_{k = 1}\frac{1}{2^k}\cos(13^k\pi y) - \sum^{\infty}_{k = 1}\frac{1}{2^k}\cos(13^k\pi x)\right| \\
 = \left|\sum^{\infty}_{k = 1}\frac{1}{2^k}\left[\cos(13^k\pi y) - \cos(13^k \pi x)\right]\right| \\
 \le \sum^{\infty}_{k = 1}\frac{1}{2^k}\left|\cos(13^k\pi y) - \cos(13^k \pi x)\right| \\
 = \sum^{\infty}_{k = 1}\frac{1}{2^k}\left|-2\sin\left[\frac{13^k\pi}{2} (y + x)\right]\sin\left[\frac{13^k\pi}{2} (y - x)\right]\right|
\]

The last equality is true by a trigonometric identity. Then I'm not sure what to do but it looks pretty darn close.

If $ f$ is continuous on $ \mathbb{R}$ and periodic of period $ P$ for some fixed positive $ P,$ then $ f$ is uniformly continuous on $ \mathbb{R}.$

We start by arguing that $ f$ is uniformly continuous on $ [0,P],$ since a continuous function on a closed bounded interval is uniformly continuous. Then the uniform continuity on the line follows from the periodicity.

This function is periodic of period $ 2.$ it is continuous because it's the limit of a uniformly converging series of continuous functions, by the Weierstrass M-test.


geometry
perimeter
algebra
polynomial
inradius
trapezoid
modular arithmetic

April 26, 2009.

XVII. National Mathematical Olympiad in Turkey.
The contest is held among high school students. Every high school sends 8 students. The top 20 are educated by Olympiad Committee in the summer. The top 40 pass the second round which is a classical exam.

There are 36 problems. 9G, 9N, 9A, 9C.
Four wrong answers cancel one right answer.
Time is limited to 150 minutes.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483168#p1483168]Problem 1[/url]

$ ABCD$ is a square. Let $ E$ be a point on the segment $ BC$ and $ F$ be a point on the segment $ ED$. If $ DF \equal{} BF$ and $ EF \equal{} BE$, then $ \angle DFA$ is

a) $ 45^\circ$  b) $ 60^\circ$ c) $ 75^\circ$ d) $ 80^\circ$  e) $ 85^\circ$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483173#p1483173]Problem 2[/url]

If $ a,b,n$ are positive integers, number of solutions of the equaition $ a^2 \plus{} b^4 \equal{} 5^n$ is

a)$ 1$ b)$ 2$ c)$ 3$ d)$ 4$ e) Infinitely many

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483177#p1483177]Problem 3[/url]

If $ x \equal{} \sqrt [3]{11 \plus{} \sqrt {337}} \plus{} \sqrt [3]{11 \minus{} \sqrt {337}}$, then $ x^3 \plus{} 18x$ = ?

a) 24 b) 22 c) 20 d) 11 e) 10

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483186#p1483186]Problem 4[/url]

Let $ a,b$ be integers greater than $ 1$. What is the largest $ n$ which cannot be written in the form $ n \equal{} 7a \plus{} 5b$ ?

a) 82 b) 47 c) 45 d) 42 e) none

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483193#p1483193]Problem 5[/url]

What is the perimeter of the right triangle whose exradius of the hypotenuse is $ 30$ ?

a) 40 b) 45 c) 50 d) 60 e) 75

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483197#p1483197]Problem 6[/url]

How many ordered integer pairs of $ (a,b)$ satisfying $ a^2b \plus{} ab^2 \equal{} 2009201020092010$ ?

a) 4 b) 2 c) 1 d) 0 e) none

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483201#p1483201]Problem 7[/url]

The product of uncommon real roots of the two polynomials $ x^4 \plus{} 2x^3 \minus{} 8x^2 \minus{} 6x \plus{} 15$ and $ x^3 \plus{} 4x^2 \minus{} x \minus{} 10$ is ?

a) $ \minus{} 4$ b) $ 4$ c) $ \minus{} 6$ d) $ 6$ e) none

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483208#p1483208]Problem 8[/url]

$ S \equal{} \{1,2,\dots,n\}$ is divided into two subsets. How the set is divided, if there exist two elements whose sum is a perfect square, then $ n$ is at least  ?

a) 13 b) 14 c) 15 d) 16 e) 17

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483210#p1483210]Problem 9[/url]

Let $ E$ be the intersection of the diagonals of the convex quadrilateral $ ABCD$. The perimeters of $ \triangle AEB$, $ \triangle BEC$, $ \triangle CED$, and $ \triangle DEA$ are all same. If inradii of $ \triangle AEB$, $ \triangle BEC$, $ \triangle CED$ are $ 3,4,6$, respectively, then inradius of $ \triangle DEA$ will be ?

a) $ \frac {9}{2}$ b) $ \frac {7}{2}$ c) $ \frac {13}{3}$ d) $ 5$ e) none

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483214#p1483214]Problem 10[/url]

For how many integer $ n$, $ P \equal{} n^4 \plus{} 4n^3 \plus{} 3n^2 \minus{} 2n \plus{} 7$ is prime?

a) 1 b) 2 c) 3 d) 4 e) Infinitely many

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483217#p1483217]Problem 11[/url]

$ (a_n)_{n \equal{} 1}^\infty$ is defined on real numbers with $ a_n \not \equal{} 0$, $ a_na_{n \plus{} 3} \equal{} a_{n \plus{} 2}a_{n \plus{} 5}$ and $ a_1a_2 \plus{} a_3a_4 \plus{} a_5a_6 \equal{} 6$. So  $ a_1a_2 \plus{} a_3a_4 \plus{} \cdots \plus{}a_{41}a_{42} \equal{} ?$

a) 21 b) 42 c) 63 d) 882 e) none

[url=http://www.artofproblemsolving.com/viewtopic.php?t=274007]Problem 12[/url]

How many 8-digit numbers are there such that exactly 7 digits are all different?

a) $ {{9}\choose{3}}^2 \cdot 6! \cdot 3$
b) $ {{8}\choose{3}}^2 \cdot 7!$
c) $ {{8}\choose{3}}^2 \cdot 7! \cdot 3$
d) $ {{7}\choose{3}}^2 \cdot 7!$
e) $ {{9}\choose{4}}^2 \cdot 6! \cdot 8$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483228#p1483228]Problem 13[/url]

In trapezoid $ ABCD$, $ AB \parallel CD$, $ \angle CAB < 90^\circ$, $ AB \equal{} 5$, $ CD \equal{} 3$, $ AC \equal{} 15$. What are the sum of different integer values of possible $ BD$?

a) 101 b) 108 c) 115 d) 125 e) none

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483235#p1483235]Problem 14[/url]

For how many ordered pairs of positive integers $ (m,n)$, $ m \cdot n$ divides $ 2008 \cdot 2009 \cdot 2010$ ?

a) $ 2\cdot3^7\cdot 5$ b) $ 2^5\cdot3\cdot 5$ c) $ 2^5\cdot3^7\cdot 5$ d) $ 2^3\cdot3^5\cdot 5^2$ e) none

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483238#p1483238]Problem 15[/url]

For real numbers, if $ |x| \plus{} |y| \equal{} 13$, then $ x^2 \plus{} 7x \minus{} 3y \plus{} y^2$ cannot be

a) $ 208$ b) $ 15\sqrt {2}$ c) $ \frac {35}{2}$ d) $ 37$ e) none

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483242#p1483242]Problem 16[/url]

$ x \plus{} 19y \equiv 0 \pmod {23}$ and $ x \plus{} y < 69$. How many pairs of $ (x,y)$ are there in positive integers?

a) 100 b) 102 c) 105 d) 109 e) none

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483249#p1483249]Problem 17[/url]

$ ABC$ is an equilateral triangle. $ D$ is a point inside $ \triangle ABC$ such that $ AD \equal{} 8$, $ BD \equal{} 13$, and $ \angle ADC \equal{} 120^\circ$. What is the length of $ DC$?

a) 12 b) 13 c) 14 d) 15 e) 16

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483252#p1483252]Problem 18[/url]

$ 1 \le n \le 455$ and $ n^3 \equiv 1 \pmod {455}$. The number of solutions is ?

a) 9 b) 6 c) 3 d)1 e) none

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483255#p1483255]Problem 19[/url]

$ a$ is a real number. $ x_1$ and $ x_2$ are the distinct roots of $ x^2 \plus{} ax \plus{} 2 \equal{} x$. $ x_3$ and $ x_4$ are the distinct roots of $ (x \minus{} a)^2 \plus{} a(x \minus{} a) \plus{} 2 \equal{} x$. If $ x_3 \minus{} x_1 \equal{} 3(x_4 \minus{} x_2)$, then $ x_4 \minus{} x_2$ will be ?

a) $ \frac {a}{2}$ b) $ \frac {a}{3}$ c) $ \frac {2a}{3}$ d) $ \frac {3a}{2}$ e) none

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483268#p1483268]Problem 20[/url]

Let $ A$ be the numbers of 5-digit positive numbers satisfying following condition:
The first digit is odd. Remaining $ 0$, or $ 2$ or $ 4$ digit/digits are even.

Let $ B$ be the numbers of 5-digit positive numbers satisfying following condition:
The first digit is even. Remaining $ 0$, or $ 2$ or $ 4$ digit/digits are even.

$ A \minus{} B \equal{} ?$

a) 5000 b) 4640 c) 3200 d) 0 e) none

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483276#p1483276]Problem 21[/url]

$ AB \equal{} AC$, $ \angle BAC \equal{} 80^\circ$. Let $ E$ be a point inside $ \triangle ABC$ such that $ AE \equal{} EC$ and $ \angle EAC \equal{} 10^\circ$. What is the measure of $ \angle EBC$?

a) $ 10^\circ$ b) $ 15^\circ$ c) $ 20^\circ$ d) $ 25^\circ$ e) $ 30^\circ$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483284#p1483284]Problem 22[/url]

$ (a_n)_{n \equal{} 0}^\infty$ is a sequence on integers. For every $ n \ge 0$, $ a_{n \plus{} 1} \equal{} a_n^3 \plus{} a_n^2$. The number of distinct residues of $ a_i$ in $ \pmod {11}$ can be at most?

a) 2 b) 3 c) 4 d) 5 e) 6

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483290#p1483290]Problem 23[/url]

The minimum value of $ x(x \plus{} 4)(x \plus{} 8)(x \plus{} 12)$ in real numbers is ?

a) $ \minus{} 240$ b) $ \minus{} 252$ c) $ \minus{} 256$ d) $ \minus{} 260$ e) $ \minus{} 280$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483303#p1483303]Problem 24[/url]

In $ xy \minus{}$plane, there are $ b$ blue and $ r$ red rectangles whose sides are parallel to the axis. Any parallel line to the axis can intersect at most one rectangle with same color. For any two rectangle with different colors, there is a line which is parallel to the axis and which intersects only these two rectangles. $ (b,r)$ cannot be ?

a) $ (1,7)$ b) $ (2,6)$ c) $ (3,4)$ ) d) $ (3,3)$ e) none

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483316#p1483316]Problem 25[/url]

The incircle of $ \triangle ABC$ touches $ BC$, $ AC$, and $ AB$ at $ A_1$, $ B_1$, and $ C_1$, respectively. The line $ AA_1$ intersects the incircle at $ Q$, again. $ A_1C_1$ and $ A_1B_1$ intersect the line, passing through $ A$ and parallel to $ BC$, at $ P$ and $ R$, respectively. If $ \angle PQC_1 \equal{} 45^\circ$ and $ \angle RQB_1 \equal{} 65^\circ$, then $ \angle PQR$ will be ?

a) $ 110^\circ$ b) $ 115^\circ$ c) $ 120^\circ$ d) $ 125^\circ$ e) $ 130^\circ$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483320#p1483320]Problem 26[/url]

For every $ 0 \le i \le 17$, $ a_i \equal{} \{ \minus{} 1, 0, 1\}$.
How many $ (a_0,a_1, \dots , a_{17})$ $ 18 \minus{}$tuples are there satisfying :
$ a_0 \plus{} 2a_1 \plus{} 2^2a_2 \plus{} \cdots \plus{} 2^{17}a_{17} \equal{} 2^{10}$

a) 9 b) 8 c) 7 d) 4 e) 1

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483329#p1483329]Problem 27[/url]

$ f\left( x \right) \equal{} \frac {x^5}{5x^4 \minus{} 10x^3 \plus{} 10x^2 \minus{} 5x \plus{} 1}$.
$ \sum_{i \equal{} 1}^{2009} f\left( \frac {i}{2009} \right) \equal{} ?$

a) 1000 b) 1005 c) 1010 d) 2009 e) 2010

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483344#p1483344]Problem 28[/url]

We divide entire $ Z$ into $ n$ subsets such that difference of any two elements in a subset will not be a prime number. $ n$ is at least ?

a) 6 b) 5 c) 4 d) 3 e) none

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483348#p1483348]Problem 29[/url]

$ P$ is the intersection point of diagonals of cyclic $ ABCD$. The circumcenters of $ \triangle APB$ and $ \triangle CPD$ lie on circumcircle of $ ABCD$. If $ AC \plus{} BD \equal{} 18$, then area of $ ABCD$ is ?

a) $ 36$ b) $ \frac {81}{2}$ c)$ \frac {36\sqrt 3}{2}$ d)$ \frac {81\sqrt 3}{4}$ e) none

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483358#p1483358]Problem 30[/url]

How many of
$ 11^2 \plus{} 13^2 \plus{} 17^2$,  $ 24^2 \plus{} 25^2 \plus{} 26^2$, $ 12^2 \plus{} 24^2 \plus{} 36^2$, $ 11^2 \plus{} 12^2 \plus{} 132^2$ are perfect square ?

a) 4 b) 3 c) 2 d)1 e) 0

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483361#p1483361]Problem 31[/url]

For all $ |x| \ge n$, the inequality $ |x^3 \plus{} 3x^2 \minus{} 33x \minus{} 3| \ge 2x^2$ holds. Integer $ n$ can be at least ?

a) 9 b) 8 c) 7 d) 6 e) 5

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483366#p1483366]Problem 32[/url]

There are $ n$ sets having $ 4$ elements each. The difference set of any two of the sets is equal to one of the $ n$ sets. $ n$ can be at most ? (A difference set of $A$ and $B$ is $ (A\setminus B)\cup(B\setminus A) $)

a) 3 b) 5 c) 7 d) 15 e) none

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483370#p1483370]Problem 33[/url]

$ AL$, $ BM$, and $ CN$ are the medians of $ \triangle ABC$. $ K$ is the intersection of medians. If $ C,K,L,M$ are concyclic and $ AB \equal{} \sqrt 3$, then the median $ CN$ = ?

a) $ 1$ b) $ \sqrt 3$ c) $ \frac {3\sqrt3}{2}$ d) $ 3$ e) none

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483373#p1483373]Problem 34[/url]

$ x$ and $ y$ are two distinct positive integers. What is the minimum positive integer value of $ (x \plus{} y^2)(x^2 \minus{} y)/(xy)$ ?

a) 3 b) 8 c) 14 d) 15 e) 17

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483376#p1483376]Problem 35[/url]

For every $ n \ge 2$, $ a_n \equal{} \sqrt [3]{n^3 \plus{} n^2 \minus{} n \minus{} 1}/n$. What is the least value of positive integer $ k$ satisfying $ a_2a_3\cdots a_k > 3$ ?

a) 100 b) 102 c) 104 d) 106 e) none

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1483389#p1483389]Problem 36[/url]

There are one-way flights between 100 cities of a country. It is possible to fly  starting from the capital city and visiting all other 99 cities and returning again to the capital city. Let $ N$ be the smallest number of flights inorder to form such a flight combination. Among all flight combinations (satisfying previous condtions), $ N$  can be at most ?

[hide="ANSWER KEY"]$ \begin{tabular}{|p{0.5in}|p{1.2in}|} \hline \multicolumn{2}{|p{1in}|}{\textbf{Answer Key}} \\
\hline NO. & Correct Answer \\
\hline \textbf{1} & \textbf{C} \\
\hline \textbf{}\textbf{2} & \textbf{E} \\
\hline \textbf{}\textbf{3} & \textbf{B} \\
\hline \textbf{}\textbf{4} & \textbf{B} \\
\hline \textbf{}\textbf{5} & \textbf{D} \\
\hline \textbf{}\textbf{6} & \textbf{D} \\
\hline \textbf{}\textbf{7} & \textbf{D} \\
\hline \textbf{}\textbf{8} & \textbf{C} \\
\hline \textbf{}\textbf{9} & \textbf{A} \\
\hline \textbf{}\textbf{10} & \textbf{D} \\
\hline \textbf{}\textbf{11} & \textbf{B} \\
\hline \textbf{}\textbf{12} & \textbf{A} \\
\hline \textbf{}\textbf{13} & \textbf{B} \\
\hline \textbf{}\textbf{14} & \textbf{A} \\
\hline \textbf{}\textbf{15} & \textbf{E} \\
\hline \textbf{}\textbf{16} & \textbf{A} \\
\hline \textbf{}\textbf{17} & \textbf{D} \\
\hline \textbf{}\textbf{18} & \textbf{A} \\
\hline \textbf{}\textbf{19} & \textbf{A} \\
\hline \textbf{}\textbf{20} & \textbf{A} \\
\hline \textbf{}\textbf{21} & \textbf{C} \\
\hline \textbf{}\textbf{22} & \textbf{B} \\
\hline \textbf{}\textbf{23} & \textbf{C} \\
\hline \textbf{}\textbf{24} & \textbf{E} \\
\hline \textbf{}\textbf{25} & \textbf{D} \\
\hline \textbf{}\textbf{26} & \textbf{B} \\
\hline \textbf{}\textbf{27} & \textbf{B} \\
\hline \textbf{}\textbf{28} & \textbf{C} \\
\hline \textbf{}\textbf{29} & \textbf{D} \\
\hline \textbf{}\textbf{30} & \textbf{D} \\
\hline \textbf{}\textbf{31} & \textbf{A} \\
\hline \textbf{}\textbf{32} & \textbf{C} \\
\hline \textbf{}\textbf{33} & \textbf{E} \\
\hline \textbf{}\textbf{34} & \textbf{C} \\
\hline \textbf{}\textbf{35} & \textbf{D} \\
\hline \textbf{}\textbf{36} & \textbf{C} \\
\hline \end{tabular}$[/hide]

Please follow the threads for Problem 31, 32, 36. They contain errata for the problems.


geometry
search
combinatorics unsolved
combinatorics

In a regular $ 6n\plus{}1$-gon, $ k$  vertices are painted in red and the others in blue. Prove that the number of isosceles triangles whose vertices are of the same color does not depend on the arrangement of the red vertices.

Have a look here :
http://www.mathlinks.ro/Forum/viewtopic.php?search_id=689203960&t=46111

Pierre.


Given that $a,b,c$ are positive real numbers, prove

\[(a+b+1)(b+c+1)(c+a+1)+2 \geq 7(ab+bc+ca)+2(a+b+c+abc)\]

Expand, and it becomes
\[
a^2+b^2+c^2+a^2b+b^2a+a^2c+c^2a+b^2c+c^2b + 3 \geq 4(ab+bc+ca)
\]
which is the sum of
$a^2 + b^2 + c^2 \geq ab + ba + ca$
$a^2b+b^2a + 1 \geq 3ab$
$a^2c+c^2a + 1 \geq 3ac$
$c^2b+b^2c + 1 \geq 3bc$
the first is well known, and the latter three are by AM-GM


$(x+y)^2=x^2+y^2 \Longrightarrow xy=0$, so either $x=0, y=R$, or $y=0, x=R$, thus, two intersecting lines at the origin.

[quote="subhash333"]Which of the following describes the graph of the equation(x+y)squared=x squared+y squared?

A)The empty set
B)One point
C)Two lines
D)A circle
E)The entire plane

Subhash[/quote]

Which of the following describes the graph of the equation $(x+y)^2=x^2+y^2$?

[hide="Click to reveal hidden content"]Expanding $(x+y)^2$ will give $x^2+2xy+y^2=x^2+y^2$. Subtracting from both sides gets $2xy=0$. Divide by 2 to get $xy=0$. You should then immediately realize those are just the axis.[/hide]

Try using $LaTeX$ next time, it makes it clearer what you are asking.
Since I've seen this problem, I know what you mean.

$(x+y)^2=x^2+y^2$
[hide]
$x^2+2xy+y^2=x^2+y^2$

$2xy=0$

$xy=0$

From this it is clear that either:

$x=0$ or $y=0$

these two possibilities are the x and y axis. So the graph is two lines (C)[/hide]

This is too easy to be an intermediate topic.

[quote="Xantos C. Guin"]

This is too easy to be an intermediate topic.[/quote]

I agree, and sadly this was like problem 13 on the AMC 12 ;)


algebra
polynomial
induction
system of equations
algebra proposed

Let's call a finite subset $ \mathcal{S}$ of $ \mathbb{R}^{n}$ a [i]brick[/i] if it is a Cartesian product $ S_{1}\times \cdots \times S_{n}$, with each $ S_{i}\subset \mathbb{R}$ a finite set. The [i] weight[/i] of the brick $ \mathcal{S}$ is the number $ w(\mathcal{S}) : = \sum_{i=1}^{n}|S_{i}|$. A [i] subbrick[/i] $ \mathcal{T}\subset \mathcal{S}$ is a brick which is at the same time a subset of $ \mathcal{S}$; it has the shape $ T_{1}\times \cdots \times T_{n}$ with each $ \emptyset \neq T_{i}\subset S_{i}$.

[b] Algebraic problem. [/b] Let $ \mathcal{S}$ be a brick in $ \mathbb{R}^{n}$, and let $ \mathcal{T}_{1}, \ldots, \mathcal{T}_{k}$ be subbricks of $ \mathcal{S}$, not necessarily disjoint. Let $ F(x_{1},\ldots,x_{n}) \in \mathbb{R}[x_{1},\ldots,x_{n}]$ be a nonzero polynomial such that $ D_{F}\cap \mathcal{S}= \bigcup_{i=1}^{k}\mathcal{T}_{i}$, where, for a polynomial $ f \in \mathbb{R}[x_{1},\ldots,x_{n}]$, the usual notation $ D_{f}: = \mathbb{R}^{n}-Z(f) = \{\boldsymbol{x}\in \mathbb{R}^{n}\mid f(\boldsymbol{x}) \neq 0 \}$ for the nonvanishing set of $ f$ is used. Then show that $ \deg{F}\geq w(\mathcal{S})-\sum_{i=1}^{k}w(\mathcal{T}_{k})$.

[b] Deduce the following. [/b] In order to cut out a union of subbricks $ \mathcal{T}_{1}, \ldots, \mathcal{T}_{k}$ from a brick $ \mathcal{S}$ by hyperplane sections, one needs at least $ w(\mathcal{S})-\sum_{i=1}^{k}w(\mathcal{T}_{k})$ hyperplanes. More precisely: if the intersection of $ \mathcal{S}$ with the union of $ s$ hyperplanes equals $ \mathcal{S}\setminus \bigcup_{i=1}^{n}\mathcal{T}_{i}$, then $ s \geq w(\mathcal{S})-\sum_{i=1}^{k}w(\mathcal{T}_{k})$.

[b]Other applications. [/b] Show that $ \mathbb{R}$ is not at all special in the algebraic problem above, and may be replaced by any field $ K$, of arbitrary characteristic. Taking $ K$ to be a finite field, show in particular:

[b][i]Generalization of Chevalley-Warning: [/i][/b] Suppose the set of solutions to a system $ f_{1}= \cdots = f_{m}= 0$ of polynomial equations in $ \mathbb{F}_{p}[x_{1},\ldots,x_{n}]$ on $ n$ variables contains bricks $ \mathcal{T}_{1}, \ldots, \mathcal{T}_{k}$ (in other words, all those polynomials vanish identically on each brick $ \mathcal{T}_{i}$). Suppose also that $ \sum_{i=1}^{m}\deg{f_{i}}< \frac{np-\sum_{i=1}^{k}w(\mathcal{T}_{i})}{p-1}$. Show that the system has a solution not lying in $ \bigcup_{i=1}^{k}\mathcal{T}_{i}$. [With $ k=1$ and $ \mathcal{T}_{1}$ the trivial brick $ \{0\}\times \cdots \times \{0\}$, so that $ w(\mathcal{T}_{1}) = n$, this is the original Chevalley-Warning theorem. ]

[b][i] Find other applications! [/i][/b]

Well, my finite difference method is stronger than it appears to be. Darij just made me aware of the fact that one can prove the whole CNS with it and in fact, also your generalization in a more general setting.

So I will solve your $ \textbf{Algebraic problem}$, but I will only assume that $ D_f\cap \mathcal{S}\subseteq \bigcup_{i \equal{} 1}^k \mathcal{T}_i$.

Let's use induction on $ \omega(\mathcal{S}) \minus{} \sum_{i \equal{} 1}^k \omega(\mathcal{T}_i)$. If $ \omega(\mathcal{S}) \minus{} \sum_{i \equal{} 1}^k \omega(\mathcal{T}_i)\leq 0$, there is nothing to prove. Thus assume $ \omega(\mathcal{S}) \minus{} \sum_{i \equal{} 1}^k \omega(\mathcal{T}_i) > 0$. Then by a really simple counting argument, there is some $ i \equal{} 1,...,n$ and some $ s\in S_i$ such that $ S_1\times ...\times S_{i \minus{} 1}\times \{s\}\times S_{i \plus{} 1}\times ... \times S_n$ does not intersect any $ \mathcal{T}_i$. Now, consider

$ g(x_1,...,x_n) \equal{} \frac {f(x_1,...,x_{i \minus{} 1},x_i,x_{i \plus{} 1},...,x_n) \minus{} f(x_1,...,x_{i \minus{} 1},s,x_{i \plus{} 1},...,x_n)}{x_i \minus{} s}$.

Of course, this is again a polynomial and it is zero on $ S_1'\times ...\times S_n'$ where $ S_j' \equal{} S_j$ for $ j\neq i$ and $ S_i' \equal{} S_i \minus{} \{s\}$ except for maybe elements of $ \mathcal{T}_i$ for $ i \equal{} 1,...,k$. Thereby we reduced the degree of $ f$ by one and simultaneously the term $ \omega(\mathcal{S}) \minus{} \sum_{i \equal{} 1}^k \omega(\mathcal{T}_i)$ by one. QED.

Looking at the proof, we see that the formulation is maybe not the best: Instead of considering $ \omega(\mathcal{S}) \minus{} \sum_{i \equal{} 1}^k \omega(\mathcal{T}_i)$, it might be better to just count the "full hyperplanes" (like $ S_1\times ...\times S_{i \minus{} 1}\times \{s\}\times S_{i \plus{} 1}\times ... \times S_n$). This might also give a reformulation of the whole problem; instead of cutting out subbricks, we just leave certain "full hyperplanes".

Concerning Chevalley-Warning, this gives the following alternative and more general version:

Choose $ m$ nonconstant polynomials $ f_1,...,f_m$ from $ \mathbb{F}_p[x_1,...,x_n]$ in $ n$ variables. Furthermore, choose $ k$ hyperplanes $ H_1,...,H_k$ given by an equation of the form $ x_i \equal{} c$ for some $ i \equal{} 1,...,n$ and $ c\in \mathbb{F}_p$. Assume that $ \sum_{i \equal{} 1}^m \deg f_i < \frac k{p \minus{} 1}$ and that there is at least one solution to the systems of equations $ f_1 \equal{} ... \equal{} f_m \equal{} 0$. Then there is at least one solution of the system of equations $ f_1 \equal{} ... \equal{} f_m \equal{} 0$ in $ \bigcup_{i \equal{} 1}^k H_i$.

One question: Can one weaken the condition on the structure of the planes?

I think I solved the Agebraic Problem with Combinatorial Nullstellensatz Theorem.
  Here is a sketch of my solution:
Supposing the assertion is false,i.e. $ \deg f < \omega(\mathcal S) \minus{} \sum_{i \equal{} 1}^k\omega(\mathcal T_i)$ .
  This says that there exists some indices $ j\in \mathcal J$ such that:$ |\mathcal S_j| > \sum_{i \equal{} 1}^k|\mathcal T^j_i|$.Now we choose  abitraryly $ (s_1,s_2,...,s_n)\in \mathcal T_i$ for some $ \mathcal T_i$.We define the polynomial:
$ G(x_1,x_2,...,x_n) \equal{} F(x_1,x_2,...,x_n) \minus{} \lambda\prod_{j\in\mathcal J,c\in \mathcal S_j\setminus\bigcup_{i \equal{} 1}^k \mathcal T^j_i}(x_j \minus{} c)$
   Here $ \lambda$ was choosen such that
\[ G(s_1,s_2,...,s_n) \equal{} 0
\]
.It's easy to see that $ \lambda \ne 0.$
Now by our assuption we have $ \deg(G) > \deg(F)$ and the leading coefficient  is $ \lambda\ne 0$.So, Combinatorial Nullstellensatz theorem( with $ \mathcal S'_i \equal{} \{s_i\}$ for$ i\notin \mathcal J$ and $ \mathcal S_j' \equal{} \{s_j\}\cup\mathcal S_j\setminus\bigcup_{i \equal{} 1}^k \mathcal T^j_i$ for $ j\in\mathcal J$) states that we must obtain $ (v_1,v_2,...,v_n)\in \mathcal S'_1\times\mathcal S'_2\times\cdots\times \mathcal S'_n$ such that:
     $ G(v_1,v_2,...,v_n)\ne 0$
But this contradicts to the hypothesis :$ D_f\cap \mathcal S \equal{} \bigcup_{i \equal{} 1}^k\mathcal T_i$.QED.

   I agree with Peter  that the condition could be reduced

I am wondering: I guess we only have $ \deg f \plus{} (n\minus{}1)\geq \omega(\mathcal{S}) \minus{} \sum_{i\equal{}1}^k \omega(\mathcal{T}_i)$. Take e.g. $ \mathcal{S}$ as just one point and no $ \mathcal{T}_i$. In fact, looking back at my proof, this is only what i prove(i need that $ \mathcal{S}$ stays nonempty to do the induction!).


Let $a,b,c>0$ be real numbers with sum 1. Prove that

$\frac{a^{2}}b+\frac{b^{2}}c+\frac{c^{2}}a \geq 3(a^{2}+b^{2}+c^{2})$

Notice that

$\frac{a^{2}}{b}+\frac{b^{2}}{c}+\frac{c^{2}}{a}\geq 3(a^{2}+b^{2}+c^{2}) \\\Leftrightarrow \frac{a^{2}}{b}+\frac{b^{2}}{c}+\frac{c^{2}}{a}-(a+b+c)-3(a^{2}+b^{2}+c^{2})+(a+b+c)^{2}\geq 0 \\\Leftrightarrow \frac{(a-b)^{2}}{b}+\frac{(b-c)^{2}}{c}+\frac{(c-a)^{2}}{a}-(a-b)^{2}-(b-c)^{2}-(c-a)^{2}\geq 0 \\\Leftrightarrow \frac{(a-b)^{2}(a+c)}{b}+\frac{(b-c)^{2}(b+a)}{c}+\frac{(c-a)^{2}(c+b)}{a}\geq 0$

 :D

Edit: I didn't see that you made a double post, and that my solution was the same as one in [url]http://www.mathlinks.ro/Forum/viewtopic.php?p=515092#p515092[/url]... it uses the same identity used for solving a problem of the Balkan MO '05

A stronger is here: http://www.mathlinks.ro/Forum/viewtopic.php?t=38369


As written in crux, this inequality is wrong as stated. Just choose $x=y= \frac 1 4$ and $z= \frac 3 4$.

Pierre.

It was pointed out in crux that the inequality is incorrect (e.g. set $x=y=1/4$, $z=3/4$). However, as a remark, it pointed out that it is true if x, y, z are sides of a triangle.

Sorry Billzhao, you are one minute late :D

Pierre.

This was solved by Pcalin in the topic "Baurjan inequality"

For your convenience I copy here Pcalin solution

[quote="pcalin"]After some computations, the given condition becomes [tex] 4R+r=4Rp[/tex]. Homogenize the inequality as follows [tex]64\prod [4Rp-a(4R+r)]\leq (4Rp)^3 \Leftrightarrow 64\prod [4Rrp-ar(4R+r)]\leq (4Rrp)^3 \Leftrightarrow 64\prod (bc-4Rr-r^2)\leq a^2b^2c^2 \Leftrightarrow 64\prod (p^2-ab-ca)\leq a^2b^2c^2 \Leftrightarrow \prod (-a+b+c)^2\leq a^2b^2c^2 [/tex], which is well known, and the proof is complete.[/quote]


Hi again,

I'd like to know how we can change the size of the caption of a figure ? Why? because now my caption is a long text explaining the subfigures and the caption is as wide as the page!! I'd want to size it to fit as large as the two subfigures that are side by side.

Thank again for anyone who can help!

Peter

The [b]caption[/b] package allows you to do various customizations to float captions.  You'll have to see the package documentation for all the specifics.

[url]http://www.ctan.org/tex-archive/help/Catalogue/entries/caption.html[/url]

Thank alot,

but is there any reason why it doesn't work ?? I'm using TexLive 2003 with WinShell last version and it's always telling me "Undefined Control Sequence" ??? I've added the

[code]
\usepackage{caption}
[/code]

I even try to use

[code]
\usepackage[font = small, justification = centerlast,%
            width = 400pt, position = top]{caption}
[/code]

But there's nothing I can do!! The PDF file doesn't compile.

Thank again if you can help !

Peter

Hi,
I prefer the minipage environment to the subfig environment. Unless you have a reason to stick with the subfig environment, I think you'll find this much easier. If you play around with the width parameters, you can get what you want. 7 cm is what I normally use. I'm not sure why you're having problems with the caption package, but sometimes two packages may conflict; and in rare cases, the order in which you add the packages to your code also matters.
[code]
\begin{figure}
\begin{minipage}[!h]{??? cm}
\begin{center}
\includegraphics[angle=???, width=??? cm]{???}
\caption{???}
\end{center}
\end{minipage}
\hfill
\qquad
\begin{minipage}[!h]{??? cm}
\begin{center}
\includegraphics[angle=???, width=??? cm]{???}
\caption{???}
\end{center}
\end{minipage}
\hfill
\end{figure}
[/code]
SSN.


MIT
college
number theory proposed
number theory

Let $x,y,n,k >2$ be natural numbers(n odd) that : \[x^{n}+y^{n}=p^{k}\] prove that \[n =p^{a}\] for some natural $a$.

Anyway I don't understand: $(17\cdot 2)^{4}+17^{4}=17^{5}$.
How many condtions did you forget?

Just One condition , n is odd.(n >2 was already in the problem )

Sorry about that.

I also think it was already posted then  :maybe:

Assume that $x,y,p$ are coprime.

Write $n=p^{s}q$ mit $p \nmid q$. Then set $a=x^{p^{s}}, b=y^{p^{s}}$ and we have for (w.l.o.g. prime) $q$ odd that $(a+b)(a^{q-1}-+...+b^{q-1})=a^{q}+b^{q}=p^{k}$, so $a+b$ and $a^{q-1}-+...+b^{q-1}$ are powers of $p$.
Thus $a \equiv-b \mod p$, giving $a^{q-1}-+...+b^{q-1}\equiv qa^{q-1}\not\equiv 1 \mod p$, thus $a^{q-1}-+...+b^{q-1}=1$ and $a^{q}+b^{q}=a+b=p^{k}$, only possible if $q=1$ or $a=b=1, p=2$.


If $a,b,c \in R$ so that $a \geq b \geq c$ then we have $a^2+b^2+c^2-ab-bc-ca \geq \frac{7}{3}(a-b)(b-c)$.

made by Cranganu J.

[quote="Namdung"]Straightforward: Put a = c + x + y, b = c + y! The constant 7/3 can be replaced by 3.

Namdung[/quote]
$a^2+b^2+c^2-ab-bc-ca = \frac{1}{2}\left((a-b)^2+(b-c)^2 \right)+\frac{1}{2}\left((a-b)+(b-c)\right)^2$
$\geq (a-b)(b-c)+2(a-b)(b-c)=3(a-b)(b-c)$.

$\Rightarrow a^2+b^2+c^2-ab-bc-ca \geq 3(a-b)(b-c)$.


For all positive numbers $ a,b,c,d$, prove that:
$ \frac{1}{(a\plus{}b)^2}\plus{}\frac{1}{(a\plus{}c)^2}\plus{}\frac{1}{(a\plus{}d)^2}\plus{}\frac{1}{(b\plus{}c)^2}\plus{}\frac{1}{(b\plus{}d)^2}\plus{}\frac{1}{(c\plus{}d)^2}$$ \ge \frac{1}{ab\plus{}cd}\plus{}\frac{1}{ac\plus{}bd}\plus{}\frac{1}{ad\plus{}bc}$

Next Peace, it is a very easy inequality. You have to use Cauchy Schwarz inequality. That is all needed.


Let $ p$ be a prime,and let $ a_1,a_2,...,a_{p\plus{}1}$ be distinct positive integers.Prove that there are indices $ i$ and $ j$,$ 1$≤$ i<j$≤$ p\plus{}1$,such that $ \frac{max\{a_i,a_j\}}{gcd(a_i,a_j)} \geq p\plus{}1$

[quote="SUPERMAN2"]Let $ p$ be a prime,and let $ a_1,a_2,...,a_{p \plus{} 1}$ be distinct positive integers.Prove that there are indices $ i$ and $ j$,$ 1$≤$ i < j$≤$ p \plus{} 1$,such that $ \frac {max\{a_i,a_j\}}{gcd(a_i,a_j)} \geq p \plus{} 1$[/quote]

WLOG, we have $ p \neq \gcd(a_1,a_2,...,a_{p \plus{} 1})$, i.e. at least one of them, say $ a_1$ is not divisible by $ p$.

[b]Case 1:[/b] There is less than $ 2$ distinct $ a_i$ such that $ p|a_i$.
Then by pigeon-hole principle we can find $ a_q < a_r$ so that $ a_q \equal{} kp \plus{} x, a_r \equal{} mp \plus{} x$, where $ 1 \le x \le p \minus{} 1$ is integer.

Now $ \gcd(a_q,a_r) \equal{} \gcd((m \minus{} k)p, mp \plus{} x) \equal{} \gcd(m \minus{} k, mp \plus{} x)$

So $ \frac {\max\{a_q, a_r \}}{\gcd(a_q,a_r)} \ge \frac {mp \plus{} x}{\gcd(m \minus{} k, mp \plus{} x)} > \frac {p(m \minus{} k)}{\gcd(m \minus{} k, mp \plus{} x)} \ge p$, done for this case.

[b]Case 2:[/b] There exist distinct $ i,j$ so that $ p|a_i, a_j$ and $ a_i < a_j$, then

$ p|\frac {a_i}{\gcd(a_1,a_i)}$ and $ p|\frac {a_j}{\gcd(a_1,a_j)}$

As $ \frac {a_i}{\gcd(a_1,a_i)}$ and $ \frac {a_j}{\gcd(a_1,a_j)}$ are distinct,

we have $ \frac {max\{a_1,a_j\}}{gcd(a_1,a_j)} \ge \frac {a_j}{gcd(a_1,a_j)} \ge 2p > p \plus{} 1$, done for this case also.


Is sqrt(2)^sqrt(2) rational or irrational?


Functional Analysis
advanced fields
advanced fields unsolved

The general setting here is an infinite-dimensional complex Hilbert space $\mathcal H$. A [i]commutator[/i] is an operator of the form $ABA^{-1}B^{-1}$, with $A$ and $B$ being invertible linear operators on $\mathcal H$.

(a) Prove that every unitary operator is a commutator;

(b) Prove that every invertible operator is a product of at most three commutators.

P.S.

In (b), three is the best I can do. Clearly, one does not work (if $I$ is the identity operator and $\alpha\in\mathbb C$, then $\alpha I$ is a commutator iff $|\alpha|=1$, for example), and I have no idea whether all invertible operators are products of two commutators.

Ok, (b) is obsolete :): prove that every invertible operator is a product of [i]two[/i] commutators.

Sorry about the double post. I forgot I had to edit the message within 24 hours.


I tried another proof and I don't know how to finish.

I know that a triangle have AB=AC=BC if a^2+b^2+c^2=ab+ac+bc, where A(a),B(b),C(c).

But after some calculations I have that:  a^2-2ac+c^2+3b^2=0

                                                           b^2-2bc+c^2+3a^2=0

                                                           a^2-2ab+b^2+3c^2=0

But from here I can't reach the condition that I wrote above.
Isn't a good proof??

Here's a proof :P . The triangle ABC has AB=BC=AC $\leftrightarrow$ $a^{2}+b^{2}+c^{2}=ab+bc+ac$, where A(a),B(b),C(c).
(1) \[a^{2}+b^{2}+c^{2}=ab+bc+ac \leftrightarrow (a-b)^{2}=(c-a)(b-c)\] (2)\[a^{2}+b^{2}+c^{2}=ab+bc+ac \leftrightarrow (a-c)^{2}=(b-a)(c-b)\]  ,(3)\[a^{2}+b^{2}+c^{2}=ab+bc+ac \leftrightarrow (b-c)^{2}=(a-b)(c-a)\]
From (1),(2),(3)$\rightarrow$ \[|a-b|^{2}=|c-a\parallel b-c|(*)\] , \[|a-c|^{2}=|b-a\parallel c-b|(**)\] and \[|b-c|^{2}=|a-b\parallel c-a|(***)\]
We denote $|a-b|=x$ , $|b-c|=y$ and $|c-a|=z$ ,$x,y,z\in \mathbb R_{+}$
If we use those notations and we sum up the realations (*),(**) and (***) we have: \[x^{2}+y^{2}+z^{2}=xy+yz+xz\] $\leftrightarrow$ $x=y=z$ but $x=AB$,$y=BC$ and $z=CA$,QED.


The circle $ (\omega)$ is given. Prove that we can not construct its center with only ruler.

I don't know whether this helps or not,but your problem is equivalent to the following one:

[b]a line $ \Delta$ is given,prove that we can't draw a line $ \Delta'$ perpendicular to $ \Delta$ using only a ruler.[/b]

Taking into account what BaBak Ghalebi said, lets suppose we have a construction that gives us a perpendicular line to another using only ruler. If so, then proyect the picture to a plane that is not parallel to the original one, the construction remains the same, but the perpendicularity doesn't. This means our construction is useless. i.e. we can't find such process.

We can do exactly same thing without restating the problem, because for a fixed circle and a point in it there always exists a projective transformation which maps circle into circle and a given point into the center of this circle, so in particular the old center won't be a center anymore.


AMC
AIME
analytic geometry
algebra
system of equations

For certain ordered pairs $(a, b)$ of real numbers, the system of equations \[ ax + by = 1 \] \[ x^2 + y^2 = 50 \] has at least one solution, and each solution is an ordered pair $(x, y)$ of integers. How many such ordered pairs $(a, b)$ are there?

$x^2+y^2=50$ Also, x,y are intgers.
Take the pair, $(x,y)=(1,7)$,
 $\rightarrow a+7b=1$
Therefore there is a infinite number of $(a,b)$ that give a solution to these equation...

Have i missed something?

The equation $x^{2}+y^{2}=50$ describes a circle centered around the origin with radius $5\sqrt{2}$.  There are three points on the circle with integer coordinates in the first quadrant: (1,7), (5,5), (7,1), so there are twelve total points on the circle with integer coordinates.

The equation $ax+by=1$ can describe any line on the plane.  It can intersect the circle at one or two points.

Intersects at one point with integer coordinates:  There are 12 points, so there are 12 lines.

Intersects at two points with integer coordinates:  $\displaystyle{12\choose 2}=66$ lines.

So total there are 78 ordered pairs.


Is there an easy way to find the range of complex functions?

example: f(z) = z^2

You just have to think about. For your example, since the variable is squared and any number squared is always either 0 or positive, it makes sense that the range of the function is $ [0,\infty)$. As far as I know there are no tricks to it besides logical thinking (or maybe graphing it).

Let $ y \equal{} f(z)$.  Thus, we get that $ y \equal{} z^{2}$.  Taking the square root, we get that $ \sqrt {y} \equal{} z$.  Since we're trying to find all possible values of $ f(z)$, we know that it can't be negative, for otherwise $ z$ would not be real (an assumption that I'm making, of course).  Thus, the possible values of f(x) are in the range $ [0,\infty)$.

If by "complex" you actually mean complex, think about how to take the square root of a complex number in polar form.  Equivalently, try to visualize the action of $ z \mapsto z^2$ on the unit circle and extend that to an idea of what it does to all of $ \mathbb{C}$.

Or you can argue by the Fundamental Theorem of Algebra that all nonconstant polynomials $ \mathbb{C} \to \mathbb{C}$ are surjective, but this is less likely to get you a good picture of what's actually happening.


logarithms geometry circumcircle limit Gauss algebra polynomial

Let $D$ be a closed disc in the complex plane. Prove that for all positive integers $n$, and for all complex numbers $z_1,z_2,\ldots,z_n\in D$  there exists a $z\in D$ such that $z^n = z_1\cdot z_2\cdots z_n$.

I have tried to apply school methods here and I have troubles with case $0\in D$. Does anybody manage this case?

BTW what results on this problem during TST?

you must probably mean you have problems in the case $0 \notin D$, right? :)
the only student that solved the problem (but not completely) was iura :).
also andreis had some ideas about how to proceede, but did not complete his paper with the details.

I mean exactly what I said: problems with case $0\in D$. Maybe I don't see some obvious things.

Hi myth,

your avatar looks smart and relaxed. I really could imagine you studying problems and looking like him.  :)  But kind of younger...  :D

Hi Orlando!

And I like your mysterious avatar!

And what about solution? Does anybody know it?

I repeat my question: What about solution? Does anybody know it?

I had this idea about taking the disc of minimal radius which covers the $n$ points and proving that we can modify the positions of the points s.t. the product of the complex numbers representing them remains the same but the radius of the disc decreases. Then we consider the infimum of the set of such radii and show that there must be some disc with strictly inferior radius as long as we assume the infimum to be $>0$, but I don't know if it works (and I got $0$ pts during the examination , although I didn't use this :D).

that's what I did:

If any of the $z_i=0$ then we can take $z=0$. If all the $z_i\neq 0$ we can take off the disk a segment  [$0,w$]
$=\{tw\,/\,0\leq t\leq 1\}$ with $|w|=1$ and $z_1,\ldots,z_n\in D-[0,w]$. Now we can define an holomorfic logarithm $ln$ in $D-[0,w]$ so \[z=exp\left(\frac{ln z_1+\ldots+ln z_n}{n}\right)\] works.

Suppose the $z_j$ are all nonzero.

First we address the $n=2$ case; WLOG assume $z_1z_2=1$, so we want to show that for any $z\ne0$ and disk $D$ containing $z,1/z$, one of $\pm1$ must lie in $D$. Note that any such $D$ must contain a smaller $D'$ with $z,1/z$ on its boundary. If $z\in\mathbb{R}$, $\operatorname{sgn}(z)\in\{1,-1\}$ must always lie in $D'\subseteq D$. Otherwise, the identity $\frac{z-1}{1/z-1}\bigg{/}\frac{z+1}{1/z+1} = -1$ tells us that $z,1,1/z,-1$ form a harmonic quadrilateral, whence the segments from $z$ to $1/z$ and $-1$ to $1$ must intersect. In particular, if $D'$ is not the circumcircle of $z,1,1/z,-1$, it must contain exactly one of $1,-1$ in its interior, so we're done.

Now suppose $n\ge 3$ and WLOG assume $z_1z_2\cdots z_n = 1$. The key is that for any two indices $j,k$, the $n=2$ case gives us a geometric mean $z_{j,k}$ of $z_j,z_k$ with $z_{j,k}\in D$ and $|z_{j,k}| = \sqrt{|z_j|\cdot |z_k|}$. Call this $z_j,z_k\mapsto z_{j,k},z_{j,k}$ operation $T_{j,k}$; then there exists an infinite sequence* $(j_1,k_1),(j_2,k_2),\ldots$ such that for any $\epsilon>0$, there exists a positive integer $N(\epsilon)$ such that  for all positive integers $N\ge N(\epsilon)$ and indices $j$, $2^{-\epsilon} \le |z_j^{(N)}| \le 2^{\epsilon}$. (Here ${z_j^{(N)} = (T_{j_N,k_N}\circ T_{j_{N-1},k_{N-1}}\circ \cdots \circ T_{j_1,k_1}}) (z_j)$.)

To finish, let $c\in\mathbb{C}$ and $r\ge0$ denote the center and radius of $D$, respectively. For each $\epsilon>0$ and $N\ge N(\epsilon)$, we have $z_1^{(N)}\cdots z_n^{(N)} = 1$, so there must exist two roots of unity $\omega_1 = \omega_1^{(N)},\omega_2 = \omega_2^{(N)}$ and indices $j,k$ such that (the arguments of) $z_j^{(N)},\omega_1,z_k^{(N)},\omega_2$ run counterclockwise in that order. But if we let $z'_j = z_j^{(N)}/|z_j^{(N)}|$ and $z'_k = z_k^{(N)}/|z_k^{(N)}|$, then
\[ |c-z'_j| \le |c-z_j^{(N)}| + |z_j^{(N)} - z'_j| \le r + \lvert |z_j^{(N)}| - 1\rvert \le r + (2^\epsilon-1). \]Yet $z'_j,\omega_1,z'_k,\omega_2$ lie in that order on the unit circle, so a similar argument to that of the $n=2$ case shows that at least one of $|c-\omega_1|,|c-\omega_2|$ is bounded above by $r+(2^\epsilon - 1)$ ("close" to $D$).

Hence for any $\epsilon>0$, there exists an $n$th root of unity at most distance $2^\epsilon - 1$ from $D$. Since there are only finitely many such roots and $\lim_{\epsilon\to0} 2^\epsilon - 1 = 0$, one of the $n$th roots of unity must lie in $D$, as desired.

*To prove this, let $a_j = \log_2 |z_j|$ and note  that $\sum a_j = 0$. If $|a_j|\in [\epsilon,2\epsilon)$, there must then exist $a_k$ of opposite sign from $a_j$, so $|(a_j+a_k)/2| < \epsilon$ means $T_{j,k}$ reduces the number of $l$ with $|a_l|\in [\epsilon,2\epsilon)$ by at least one. Repeating this proves the desired claim.

The following post by [b]Andrew[/b] was lost in the crash a while ago, but I found it in an online PDF (attached). (Well, I've edited it a bit to make it slightly more natural---but perhaps only from the perspective of coming up with the problem from scratch, rather than purely solving the problem.)

Suppose monic $f(x) = \prod (x-t_k)$ of degree $n$ has complex roots $t_1,\ldots,t_n$, and [b]all $t_i$ lie (strictly) outside some closed disk $D$[/b] (call the boundary, a circle, $C$) in the complex plane.

Let $u$ be an arbitrary point in $D$. Then along the lines of the [url=http://en.wikipedia.org/wiki/Gauss%E2%80%93Lucas_theorem]Gauss-Lucas theorem[/url] convexity argument, note that an inversion $I$ (say of radius $1$) about $u$ sends $t_1,\ldots,t_n$ to points $I(t_1),\ldots,I(t_n)$ (strictly) inside the image $I(C)$ (a circle). In particular, $\frac{I(t_1)+\cdots+I(t_n)}{n}$ lies inside $I(C)$ by convexity, so it equals $I(\alpha)$ for some $\alpha$ strictly outside $D$.

But of course, $I(z) = \frac{z-u}{|z-u|^2} = \frac{1}{\overline{z}-\overline{u}}$, so we've shown that if $\alpha$ satisfies $\frac{1}{n} \frac{-f'(u)}{f(u)} = \frac{1}{n} \sum \overline{I(t_k)} = \overline{I(\alpha)} = \frac{1}{\alpha - u}$, then $\alpha\notin D$.

More powerfully, consider the contrapositive statement: if $\alpha\in D$, then all solutions $u$ to $\frac{1}{n} \frac{-f'(u)}{f(u)} = \frac{1}{\alpha - u}$ must have $u\notin D$.

---

Applied to our problem, go by contradiction with $n$ WLOG minimal (so $n\ge2$), and take $f(x) = x^n - z_1\cdots z_n$. Then for all $\alpha\in D$, the roots of $g(x) := n f(x) - (x-\alpha) f'(x) = n\alpha x^{n-1} - nz_1\cdots z_n$ must all lie strictly outside $D$. But then taking $\alpha = z_n$, say, contradicts the $n-1$ case, so we're done.

Oh wow, see Polya/Szego, Problems in analysis II, Part Five. The Location of Zeros, Chapter 2. The Geometry of the Complex PllDe IDd the Zeros of Polynomials, Section 3. Derivative of a Polynomial with respect to a Point. (Problem 134 in my edition basically corresponds to the lemma above... this book is ridiculous...)


For $ a,b,c,d$ non-zero real numbers and $ k>0$, prove that the following inequality holds
$ \sum_{cyc} \frac{a^2}{3kb^2\plus{}\sqrt{3}(k^2\plus{}1)bc\plus{}kc^2}\geq\frac{2}{(k\plus{}1)^2}$

Firstly, prove that
${ \frac{1}{2}(k+1)^2\cdot(3b^2+c^2) \geq 3kb^{2}+\sqrt{3}(k^{2}+1)bc+kc^{2}}$
Also, the other three similar inequalities hold.

[quote="marin.bancos"]Firstly, prove that
${ \frac {1}{2}(k + 1)^2\cdot(3b^2 + c^2) \geq 3kb^{2} + \sqrt {3}(k^{2} + 1)bc + kc^{2}}$
Also, the other three similar inequalities hold.[/quote]

But now it's easy...your inequality follows from AM-GM, the rest, namely
\[ \sum_{cyc} \frac {a^2}{3b^2 + c^2}\geq1\]
is a simple application of Cauchy-Schwartz.

My solution was exactly what you posted, marin.bancos!

I just set $ a^2\equal{}x$, $ b^2\equal{}y$...  :P  but it doesn't change anything...


i don't think my question deals with maths, but just wanted to know.
as in 2nd World War more  males were killed  than female  like 1/4 of them.
now why in recent researching the equations is something like 3/4 ?

[url]http://en.wikipedia.org/wiki/Wikipedia:Reference_desk/Humanities[/url] is a really good place to ask questions like that  :wink: .


Given M be an expression as follow:
$ M\equal{}\frac{1\minus{}ab\plus{}\sqrt{a^2\plus{}1}\minus{}a\sqrt{1\minus{}b^2}}{1\minus{}ab\plus{}\sqrt{b^2\plus{}1}\minus{}b\sqrt{1\minus{}a^2}}$.
How to simplify M?

>> Simplify << the expression of two variables a and b?

[quote="vuthailuan"]Given M be an expression as follow:
$ M \equal{} \frac {1 \minus{} ab \plus{} \sqrt {a^2 \plus{} 1} \minus{} a\sqrt {1 \minus{} b^2}}{1 \minus{} ab \plus{} \sqrt {b^2 \plus{} 1} \minus{} b\sqrt {1 \minus{} a^2}}$.
How to simplify M?[/quote]

I would state that the original fraction is already "simplified" as no factors are cancelled
from the numerator to the denominator.  The fraction has been made more complicated
with at least twice the number of characters used in Dr Sonnhard Graubner's answer
(note:  I am NOT disagreeing with Dr Sonnhard Graubner's answer in his rationalizing of
the denominator) as compared to the number of characters in the original fraction.

I also reference:
http://regentsprep.org/Regents/mathb/2b2/LAlgFrac.htm

The problem (headline) should state specifically to "rationalize the denominator."

Thank you for discussing!
I received the problem from a friend. I agree with your comments. So, i think there are some errors in the problem.


function
limit
real analysis
real analysis unsolved

Let $f: \mathbb{C}\backslash\{0\}\to({0,+\infty})$ be continuous function such that $\mathop{\lim}_{z \to 0}f(z)=0,\,\mathop{\lim}_{|z| \to\infty}f(z)=\infty.\,$ Prove that for every $T> 0$ there exist a solution of differential equation $\frac{dz}{dt}=izf(z)$ which has period $T.$
(O. Stanzhitskyy)

the problem can be write like

$x'+iy'=(ix-y)g(x,y)$ where $f(z)=g(x,y)$

we have an autonomous system

$x'=-yg(x,y)$
$y'=xg(x,y)$  with

$g$:$R^{2}-(0,0)\rightarrow (0,+\infty)$ continous and  $\lim_{(0,0)}g=0$
$\lim_{\infty}g=+\infty$

...

for the existence of a solution maximal $(x,y)$ passing trough $(a,b)$
use  Peano theorem (here we don't have the unicity the statement not allowed us to use Cauchy-lispchitz theorem)


function
parameterization
binomial coefficients
algebra proposed
algebra

[b]Find   a set $\left\{ C(n,k)\right\} , n,k \in {\mathbb N} \; ,\; ( k\ge n+1 ) ,$  of (non-zero)  numbers of the form  $C(n,k)=\frac{1}{D(n,k)}\; ,\; D(n,k)\in {\mathbb Z}\setminus\{0\} ,$
 which satisfies the[/b]  [color=green][b]"  Pascal rule "  [/b][/color]   \[ C(n,k)=C(n-1,k) +C(n-1,k-1)\; \; \; ,\; \; k\in \{n+1,n+2,...\} .  \]

[quote="flip2004"]Find   a set $ \left\{ C(n,k)\right\} , n,k \in {\mathbb N} \; ,\; ( k\ge n+1 ) , $  of (non-zero)  numbers of the form  $ C(n,k)=\frac{1}{D(n,k)}\; ,\; D(n,k)\in  {\mathbb Z}\setminus\{0\} , $  which satisfies the [i] Pascal rule [/i]   \[ C(n,k)=C(n-1,k) +C(n-1,k-1)\; \;  \; ,\; \;  k\in \{n+1,n+2,...\} . \][/quote]
A solution is  $ C(n,k):=\frac{(-1)^{k-n-1}}{(k-n){k\choose n}} $ where $n\in {\mathbb N}^* \; ,\; k\in \{n+1,n+2,...\}. $  There are other solutions (essential distinct) from that  ?

I think you can use the gamma-function extension of the binomial coefficients to argue that no other solutions exist (and maybe prove it, assuming some irrationality statements about the gamma function).

Given values of $D$ at $(n,k)$ and $(n+1,k)$, find values of the parameters so that these correspond to $m{a \choose b}$ and $m{{a+1} \choose b}$.  Then the rest of the triangle is filled in the expected Pascal pattern, but using continuous binomial coefficients.  Assuming that there are no strange unexpected rationalities of the Gamma function, this would not happen for non-integer $b$.

Just an idea.


33)  In the multiplication shown, each letter represents a digit (not necessarily distinct).  What is the sum of all possible products?

$2A \times B7 = 2CD1$

[hide][code]   2A
X  B7
-----
  xxx
 xxx
-----
 2CD1[/code]

$7\cdot{A}$ has units digit of 1, so $A=3$. We can immediately deduce a large part of the multiplcation problem:

[code]   23
X  B7
-----
  161
 xxx
-----
 2CD1[/code]

Notice the 1000s digit of the product is 2, which means that $23\cdot{B}$ must be at least 184. $\frac{184}{23}=8$, so $B=\{8,9\}$. $B=8$ gives the product $2001$, and $B=9$ gives  the product $2231$, for a sum of $4232.$[/hide]


Hehe, funniest thing, I took that AMC like 2 days ago.  I think it's #13 on the 2000 AMC->12.  What I did was set up equations and solved one of the diophantine equations.  Grr...I gtg.  I'll post more later.

-interesting_move

[hide]Let M be the amount of milk, and let C be the amount of coffee. Then M/4+C/6=8, or 3M+2C=96. Since M+C :equiv: 0 (mod 8), we can subtract 2(M+C) from 3M+2C=96 and get M :equiv: 0 (mod 8). Thus M is 8, 16, or 24. M=8 gives C=36, or M+C=44, which isn't divisible by 8. M=24 gives C=12, or M+C=36, which isn't divisible by 8 either. Only if M=16 and C=24 do we get M+C=40 to be divisible by 8. Thus there are 40/8=5 people in the family.[/hide]

s0mp wrote:One morning each member of Angela's family drank an 8-ounce mixture of coffee with milk. The amounts of coffee and milk varied from cup to cup, but were never zero. Angela drank a quarter of the total milk and a sixth of the total amount of coffee. How many people are in the family?

[hide]okay. so i let m=milk and c=coffee and x=amount of people in the fambly. so m/4+c/6=(m+c)/x or (6m+4c)/24=(m+c)/x, cross multiplying i got x(6m+4c)=24(m+c) or 6mx+4cx=24m+24c. dividing by 2 you get 3mx+2cx=12m+12c or 3mx-12m=12c-2cx. factoring you get 3m(x-4)=2c(6-x). knowing that m and c are positive. the only number x could be yielding a postive solution would be 5. so 5 is my answer. [/hide]

hope i helped.

s0mp wrote:One morning each member of Angela's family drank an 8-ounce mixture of coffee with milk. The amounts of coffee and milk varied from cup to cup, but were never zero. Angela drank a quarter of the total milk and a sixth of the total amount of coffee. How many people are in the family?

Ah, I remember this one...well, not the solution, so I'll answer it.

[hide]Angela drinks X oz. of milk and 8-X oz. of coffee.  So 4X + 6(8-X) = 8Y, where Y is the number of people.  Therefore 48 - 2X = 8Y.  In order for Y to be an integer, X has to be 4, 8, 12, 16, 20, etc.

Now, if X is 4, Y is 5.

If X is 8, Y is 4

If X is 12, Y is 3.

If X is 16, Y is 2.

If X is 20, Y is 1.

However, of these values, only the first makes sense, since the criteria is that X :le: 8.  Therefore, there must have been five people.

Check: if X is 4, then Angela drank 4 oz. milk and 4 oz. coffee.  Then in all, 16 oz. of milk and 24 oz. of coffee were drunk, which adds up to 40, which equals 5 people times 8 oz.[/hide]

Umm...hope I've helped...I guess.  I don't think I'm helping anyone since other people have already answered this and the person who posted this probably didn't need help anyway.

[quote="mathfanatic"]  I don't think I'm helping anyone since other people have already answered this and the person who posted this probably didn't need help anyway.[/quote]

correct. but gj everyone.

well its just a challenge thingie. and other people learn from it.

HOPEFULLY AT LEAST

true, true brudda o mine.

P.S. See my LJ.


Let V  be a normed(is this correct?) $ S_V$= [All x in V such  that norm of v is 1]. Is $ S_V$ compact if
 V= $ C_1[0,1]$

That won't be compact in any infinite dimensional normed space.

[quote="zhoraster"]However, if $ V \equal{} C^1[0,1]$ (continuously differentiable), $ S_V$ is compact in $ C[0,1]$.[/quote]
Definitely not. It's merely totally bounded.

[quote="dihuana"]
Definitely not. It's merely totally bounded.[/quote]
Pre-compact, yes, that's what I wanted to write :).


group theory
abstract algebra
linear algebra
linear algebra unsolved

Prove that any finite subgroup in $GL_n(Z)$ has at most $ (2n)!$ elements. Much more difficult, I think, but not impossible is: for any $\epsilon>0$ there is a constant $C=C(\epsilon)$ such that any finite subgroup in $GL_n(Z)$ has at most $ (n!)^{1+\epsilon} C^n$ elements.

Ok, I have finally found a solution to the first problem and since I find it interesting and nobody answered, I will post a solution:
  Lemma 1
     If $G$ is a finite subgroup then $|G|$ is a divisor of $\sum_{g\in G}{ (trg)^k}$ for all $k$.
   This has been proved by Leva 1980, so I will just remind a little bit the proof. For $k=1$ it is easy to prove observing that the mean value of all $g$ for $g\in G$ is idempotent. For $k>1$ apply this to $G+G+...+G$ where $G+G+...+G$ is the set of matrices $A*A*A...*A$ with $A\in G$ and $A*B$ the Kronecker product.
    Here is a quite nice result, that I found solving this problem. Yet, I am sure it is well-known.
   Lemma 2
      If $m| a_1 x_1^p+...+a_k x_k^p$ for all $p$ and $a_i, x_j$ are integers, then $ m| a_1 (x_1-x_2)...(x_1-x_k)$.
    The proof is very nice. COnsider $ f(z)=\sum{\frac{a_i}{1-zx_i}}$ and observe that developping it as an entire series, all coefficients are multiples of $m$, thus also all coefficients of $\sum{a_1 (1-zx_2)...(1-zx_k)}$ are multiples of $m$. Write them explicitely and after some boring computations the lemma is proved.
      Now, consider $x_1>...>x_k$ the set of traces of elements in $G$ and $a_1,...,a_k$ the number of times they appear. Obviously, the conditions of lemma 2 are verified by lemma 1 and thus $ |G|| a_1 (x_1-x_2)...(x_1-x_k)$. But since $x_1=n$ (easy to prove) and $ a_1=1$, the conclusion follows by noting that $x_1-x_2,...,x_1-x_k$ are different natural numbers smaller than or equal to $2n$.


trigonometry
geometry
trig identities
Law of Sines
Pythagorean Theorem

Given square ABCD with side 8 feet. A circle is drawn through vertices A and D and tangent to side BC. The radius of the circle, in feet, is:
(A) 4
(B) $4\sqrt{2}$
(C) 5
(D) $5\sqrt{2}$
(E) 6

Not the most elegant way, I don't think...
[hide]
Let $E$ be the tangent point and the midpoint of $BC$.

Using the law of sines,
$\frac{8}{\sin AED} = 2R$ where $R$ is the circumradius.
$AED = 180 - 2 \sin^{-1} \frac{2\sqrt{5}}{5}$
$\sin AED = 2 \sin^{-1} \frac{2\sqrt{5}}{5}$
$= 2 \frac{2\sqrt{5}}{5} \cos \sin^{-1} \frac{2\sqrt{5}}{5}$
$= 2 \frac{2\sqrt{5}}{5} \frac{\sqrt{5}}{5}$
$= \frac 4 5$
$R = 5$
$C$
[/hide]

[quote="frt"]Let $O$ be the center of the circle and let $E$ and $F$ be the midpoints of $BC$ and $AD$, respectively.

Since $EF\perp AD$, use Pythagorean theorem to $\triangle AFO$.
$AO=r$ and $AF=4$, so $OF=\sqrt{r^2-16}$.

$OE+OF=r+\sqrt{r^2-16}=8$
$\Longrightarrow r^2-16=r^2-16r+64$
$\Longleftrightarrow 16r=80$
$\Longleftrightarrow r=\boxed{5}$[/quote]
 used the same method can it be more elegant than this?


Why is this not working and how should I fix it?

\begin{cases} \begin{eqnarray*} f & = & g \\ & = & h \end{eqnarray*} & x\ge 0 \\ 0 & x<0 \end{cases}

The ugly workaround is by writing everything as simple arrays, but maybe there's a better solution? Thanks!

Is this the effect you are trying to achieve?

\begin{eqnarray*}f&=&\begin{cases}g,&x\ge 0\\h,&x<0\end{cases}\end{eqnarray*}
The code for that is:

[code]\begin{eqnarray*}
f&=&\begin{cases}g,&x\ge 0\\h,&x<0\end{cases}
\end{eqnarray*}[/code]
(with cases inside the eqnarray*)

I'm not sure what the point of eqnarray is here as it is't needed.
[code]\[
f=\begin{cases}
 g, &x\ge 0\\
 h, &x<0
\end{cases}
\][/code]
In any case eqnarray should never be used any more - see [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=123690]LaTeX FAQ 5[/url]

I was trying to generate this effect: $blabla = \left\{\begin{array}{ll}\begin{array}{rcl}f & = & g \\ & = & h \end{array}& x\ge 0 \\ 0 & x<0\end{array}\right.$

(the line split is needed because in my situation $f,g,h$ were too long to fit on the same line)

But it works so that's fine, I was mainly curious why the first didn't work. :)

[quote="Peter VDD"] I was mainly curious why the first didn't work. :)[/quote]Because eqnarray changes from text to math mode and cases has to be done in math mode. So you can have cases inside eqnarray but not vice-versa.


calculus
integration
logarithms
calculus computations

Integrate

$\int \frac{dx}{a+bx^{2}}$ if $ab < 0$.