quadratics
Gauss
modular arithmetic
number theory
relatively prime
Divisibility Theory
pen

We will treat rational numbers, which have their denominator relatively prime to $p$, as residues mod $p$.
From the Fermat's Little Theorem: $\frac{1}{i} \equiv i^{p-2} \mod{p}$
So we see that:
$\sum_{i=1}^{p-1} \frac{1}{i} \equiv \sum_{i=1}^{p-1} i^{p-2} = \sum_{i=1}^{\frac{p-1}{2}} i^{p-2} + (p-i)^{p-2} \equiv \sum_{i=1}^{\frac{p-1}{2}} p(p-2)i^{p-3} = p(p-2) \sum_{i=1}^{\frac{p-1}{2}} i^{p-3} \mod{p^2}$
The last congruence comes from the fact that the rest term vanishes mod $p^2$. We are left with proving that:
$\sum_{i=1}^{\frac{p-1}{2}} i^{p-3} \equiv 0 \mod{p}$
or (one more time from FTL):
$\sum_{i=1}^{\frac{p-1}{2}} \frac{1}{i^2} \equiv 0 \mod{p}$
Now if $i, j \leq \frac{p-1}{2}$ and $\frac{1}{i^2} \equiv \frac{1}{j^2} \mod{p}$ then also $(i-j)(i+j) \equiv 0 \mod{p}$ but since $i, j \leq \frac{p-1}{2}$ we must have $i=j$. So the numbers: $\frac{1}{i^2}$ for $i=1,2,...,\frac{p-1}{2}$ are all different quadratic residues (and there are exactly $\frac{p-1}{2}$ quadratic residues), as well as the numbers $i^2$ for $i=1,2,...,\frac{p-1}{2}$ so:
$\sum_{i=1}^{\frac{p-1}{2}} \frac{1}{i^2} \equiv \sum_{i=1}^{\frac{p-1}{2}} i^2 = \frac{p(p-1)(p+1)}{24} \equiv 0 \mod{p}$
which ends the proof.

[quote="Peter"](Wolstenholme's Theorem) Prove that if
\[ 1 + \frac {1}{2} + \frac {1}{3} + \cdots + \frac {1}{p - 1}\]
is expressed as a fraction, where $ p \ge 5$ is a prime, then $ p^{2}$ divides the numerator.[/quote]

This is an updated version of [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=46121]an older MathLinks post of mine[/url], and I am submitting it here since I will refer to it in a number of other proofs.

I will generalize the problem, but first I explain some preliminaries about primes.

[color=blue][b]1. p-adic valuation[/b][/color]

Let $p$ be an arbitrary prime. We denote by $ \mathbb{Z}_{p}$ the field of residues of integers modulo $p$.

For any rational number $x$, we will now define the so-called [i]$p$-adic valuation of $x$[/i]. This valuation will be denoted by $ v_{p}\left(x\right)$, and it is defined as follows: If $ x\neq 0$, then $ v_{p}\left(x\right)$ is the greatest integer $k$ such that $\frac{x}{p^{k}}$ can be written as a ratio of two integers with the denominator not being divisible by $p$. Besides, we set $ v_{p}\left(0\right) = + \infty$, where $ + \infty$ is just a symbol satisfying $ + \infty > a$ and $ + \infty + a = + \infty$ for any integer $ a$. (The main thing we will need about $+ \infty$ is that $ v_{p}\left(0\right) > v_{p}\left(x\right)$ for any nonzero $x$).

We can easily see how to compute $ v_{p}\left(x\right)$ for rationals $ x\neq 0$:

* If $x$ is a nonzero integer, then $ v_{p}\left(x\right)$ is the greatest integer $k$ such that $ p^{k}$ divides $x$ (thus, in particular, we have $ v_{p}\left(x\right) = 0$ if $p$ doesn't divide $x$).

* If $x$ is a ratio of two nonzero integers, say $ x = \frac{a}{b}$ with nonzero integers $a$ and $b$, then $ v_{p}\left(x\right) = v_{p}\left(a\right) - v_{p}\left(b\right)$.

Note that there is a simple way to interpret the sign of the $p$-adic valuation $ v_{p}\left(x\right)$ of a rational number $x$: If we write $x$ as a reduced fraction (i.e., a fraction with numerator and denominator coprime; if $x$ is an integer, then just write it in the form $x = \frac{x}{1}$), and it turns out that the numerator is divisible by $p$, then $ v_{p}\left(x\right) > 0$; if neither the numerator nor the denominator is divisible by $p$, then $ v_{p}\left(x\right) = 0$; if the denominator is divisible by $p$, then $ v_{p}\left(x\right) < 0$.

A [i]$p$-integer[/i] shall mean a rational number $x$ satisfying $v_p\left(x\right) \geq 0$. In particular, every integer is a $p$-integer. Moreover, any fraction of integers is a $p$-integer if its denominator is coprime to $p$.

It is rather easy to prove that for any two rational numbers $x$ and $y$, we have $ v_{p}\left(xy\right) = v_{p}\left(x\right) + v_{p}\left(y\right)$ and $v_{p}\left(x + y\right)\geq\min\left(v_{p}\left(x\right);\;v_{p}\left(y\right)\right)$. Thus, the sum and the product of two $p$-integers are $p$-integers again. Hence, it is not hard to see that any sum or product of finitely many $p$-integers is a $p$-integer, and that a difference of two $p$-integers is always a $p$-integer. (In the language of abstract algebra, this is saying that the $p$-integers form a subring of $\mathbb{Q}$.)

[color=blue][b]2. Working with fractions modulo $p$[/b][/color]

I will use the notation $\mathbb{Z}_{p}$ for the ring $\mathbb{Z} / p\mathbb{Z}$ (that is, the ring of integers modulo $p$).

We will also need some familiarity with fractions in $\mathbb{Z}_{p}$. The main idea is to extend the notion of congruence modulo $p$ from integers to $p$-integers: If $x$ and $y$ are two $p$-integers, then we say that $x\equiv y\mod p$ (in words: "$x$ is congruent to $y$ modulo $p$") if and only if $v_{p}\left(x - y\right) > 0$. Thus we have defined a relation ("congruence modulo $p$") on the set of all $p$-integers. This relation is an equivalence relation (this is easy to prove; do it!). Moreover, if $x$ and $y$ are two integers, then $x \equiv y \mod p$ with respect to this new equivalence relation if and only if $x \equiv y \mod p$ in the usual sense (i.e., we have $p \mid x-y$ in $\mathbb{Z}$). This fact allows us to use the same notation for both equivalence relations without worrying about possible ambiguity.

It is easy to see that this equivalence relation has the same properties as the classical "congruence modulo $p$" relation on integers:

* If $a$, $b$, $c$ and $d$ are $p$-integers, and if $a \equiv b \mod p$ and $c \equiv d \mod p$, then $a+c \equiv b+d \mod p$ and $a-c \equiv b-d \mod p$ and $ac \equiv bd \mod p$. In other words, congruences modulo $p$ between $p$-integers can be added, subtracted and multiplied just as congruences between integers.

* The same holds for larger sums: i.e., if $a_1, a_2, \ldots, a_j, b_1, b_2, \ldots, b_j$ are $p$-integers, and if every $i$ satisfies $a_i \equiv b_i \mod p$, then $\sum\limits_{i=1}^j a_i \equiv \sum\limits_{i=1}^j b_i \mod p$.

* If $a$, $b$, $c$ and $d$ are $p$-integers such that $v_p\left(b\right) = 0$ and $v_p\left(d\right) = 0$, and if $a \equiv b \mod p$ and $c \equiv d \mod p$, then $a/c \equiv b/d \mod p$. In other words, congruences modulo $p$ between $p$-integers can be divided by one another, as long as the $p$-integers we are dividing by have $p$-adic valuations equal to $0$. We shall refer to this fact as the [i]division rule[/i].

Recall that congruence modulo $p$ is an equivalence relation on the set of $p$-integers. Let $F_p$ denote the set of equivalence classes of this equivalence relation. One might expect that $F_p$ is larger than $\mathbb{Z}_p$, seeing that the equivalence classes that comprise $F_p$ consist of $p$-integers whereas the equivalence classes that comprise $\mathbb{Z}_p$ consist of integers only. But in fact, it turns out that $F_p$ is in bijection with $\mathbb{Z}_p$. Indeed, it is easy to prove that for every $p$-integer $x$, there is one and only one integer $n$ satisfying $0\leq n < p$ such that $x\equiv n\mod p$. Thus, every equivalence class in $F_p$ contains exactly one of the integers $0, 1, \ldots, p-1$, and thus corresponds to a unique equivalence class in $\mathbb{Z}_p$. Equivalence classes in $F_p$ can be added, subtracted and multiplied (just as in $\mathbb{Z}_p$), and these operations match precisely the analogous operations in $\mathbb{Z}_p$ (that is, if you add two equivalence classes in $F_p$, then the corresponding class in $\mathbb{Z}_p$ is obtained by adding the classes in $\mathbb{Z}_p$ that correspond to the two addends; and similarly for subtraction and multiplication). Furthermore, if $x$ and $y$ are two equivalence classes in $F_p$, then $x/y$ is a well-defined equivalence class in $F_p$ provided that $y$ is the equivalene class of a $p$-integer $u$ with $v_p\left(u\right) = 0$. (Again, it is constructed as usual: Pick an element $a \in x$ and an element $b \in y$, and form the equivalence class of the rational number $a/b$.) Hence, you can work with $p$-integers modulo $p$ in the same way as you work with integers modulo $p$. This also means that modulo $p$, you can uniquely divide by any integer not divisible by $p$. [A nice application of this is [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=44573]problem 4 of the IMO 2005[/url] - see Fedor Petrov's proof in post #2.]

[color=blue][b]3. Generalization of Wolstenholme's Theorem[/b][/color]

Now, the problem A 23 asks us to show that if $ p$ is a prime number such that $ p\geq 5$, then $ v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k}\right)\geq 2$. This is a particular case (namely, the $ u = 1$ case) of the following result:

[color=blue][b]Theorem 1.[/b] Let $ p$ be a prime number, and $ u$ be an odd integer such that $ p\geq u + 3$ and $ u\geq 0$. Then,

$ v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right)\geq 2$.[/color]

[i]Proof of Theorem 1.[/i] We have $ p > 2$ (since $ p\geq u + 3$ and $ u\geq 0$). We start with the Gauss trick:

$ 2\sum_{k = 1}^{p - 1}\frac {1}{k^{u}} = \sum_{k = 1}^{p - 1}\frac {1}{k^{u}} + \sum_{k = 1}^{p - 1}\frac {1}{k^{u}} = \sum_{k = 1}^{p - 1}\frac {1}{k^{u}} + \sum_{k = 1}^{p - 1}\frac {1}{\left(p - k\right)^{u}}$
$= \sum_{k = 1}^{p - 1}\left(\frac {1}{k^{u}} + \frac {1}{\left(p - k\right)^{u}}\right) = \sum_{k = 1}^{p - 1}\frac {k^{u} + \left(p - k\right)^{u}}{k^{u}\left(p - k\right)^{u}}$.

Now, define $ s_k=\sum_{i=2}^u\left(-1\right)^{u-i}\binom{u}{i}p^{i-2}k^{u-i}$ for every $ k\in\left\{1,2,...,p-1\right\}$. Obviously, $ s_k$ is an integer for every $ k$. We can expand $ \left(p - k\right)^{u}$ according to the binomial formula:

$ \left(p - k\right)^{u}=\sum_{i=0}^u\left(-1\right)^{u-i}\binom{u}{i}p^ik^{u-i}$
$ =\left(-1\right)^{u-0}\binom{u}{0}p^0k^{u-0}+\left(-1\right)^{u-1}\binom{u}{1}p^1k^{u-1}+\sum_{i=2}^u\left(-1\right)^{u-i}\binom{u}{i}p^ik^{u-i}$
$ =\left(-1\right)^uk^u+\left(-1\right)^{u-1}upk^{u-1}+p^2\sum_{i=2}^u\left(-1\right)^{u-i}\binom{u}{i}p^{i-2}k^{u-i}$
$ =\left(-1\right)^uk^u+\left(-1\right)^{u-1}upk^{u-1}+p^2s_k$
$=\left(-1\right)k^u+1upk^{u-1}+p^2s_k$      (since $u$ is odd, so that $ \left(-1\right)^u=-1$ and $ \left(-1\right)^{u-1}=1$)
$ =-k^u+upk^{u-1}+p^2s_k$.

Thus, $ k^u+\left(p-k\right)^u = upk^{u-1}+p^2s_k$ for every $ k\in\left\{1,2,...,p-1\right\}$, and therefore

$ 2\sum_{k = 1}^{p - 1}\frac {1}{k^{u}} = \sum_{k = 1}^{p - 1}\frac {k^{u} + \left(p - k\right)^{u}}{k^{u}\left(p - k\right)^{u}} = \sum_{k = 1}^{p - 1}\frac {upk^{u-1}+p^2s_k}{k^{u}\left(p - k\right)^{u}} = \sum_{k = 1}^{p - 1} p \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}}$
$ = p \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}}$.

Hence,

$ v_{p}\left(2\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right) = v_{p}\left( p \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \right) = \underbrace{v_{p}\left(p\right)}_{=1} + v_{p}\left( \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \right)$
$ = 1 + v_{p}\left( \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \right)$.

But since $ 2$ isn't divisible by $ p$ (since $ p > 2$), we have $ v_{p}\left(2\right) = 0$, so that

$ v_{p}\left(2\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right) = \underbrace{v_{p}\left(2\right)}_{=0} + v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right) = v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right)$.

Comparing these two equalities, we get

$ v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right) = 1 + v_{p}\left( \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \right)$.

Hence, instead of showing $ v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right)\geq 2$, it will be enough to prove $ v_{p}\left( \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \right)\geq 1$. This is equivalent to $ v_{p}\left( \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \right) > 0$, i.e., to $ \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \equiv 0\mod p$. Here, we are using the fact that for every $ k\in\left\{1,2,...,p-1\right\}$, the fraction $ \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}}$ is a $p$-integer (because its denominator, $ k^{u}\left(p - k\right)^{u}$, is not divisible by $ p$, since $ 1\leq k\leq p - 1$ and since $ p$ is a prime), and therefore it makes sense to say that the sum of all these fractions is $\equiv 0 \mod p$.

Let us now look more closely at such a fraction $\frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}}$ (with $k \in \left\{1,2,\ldots,p-1\right\}$).
The numerator $ uk^{u-1}+ps_k$ of this fraction is congruent to $ uk^{u - 1}$ modulo $p$ (since $ p\equiv 0\mod p$, and thus all terms containing $ p$ can be omitted). Also, the denominator can be simplified modulo $p$: Since $ p - k\equiv - k\mod p$, we have $ k^{u}\left(p - k\right)^{u}\equiv k^{u}\left( - k\right)^{u} = \left( - 1\right)^{u}k^{2u} \mod p$. Dividing the congruence $uk^{u-1}+ps_k \equiv uk^{u-1} \mod p$ by the latter congruence, we obtain $ \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \equiv \frac {uk^{u-1}}{\left(-1\right)^u k^{2u}}\mod p$ (here, we have applied the division rule, since the rational numbers $k^{u}\left(p - k\right)^{u}$ and $\left(-1\right)^u k^{2u}$ have $p$-adic valuation $0$). Therefore,

[color=green][b](1)[/b][/color] $ \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}}\equiv\sum_{k = 1}^{p - 1}\frac {uk^{u - 1}}{\left( - 1\right)^{u}k^{2u}} = \sum_{k = 1}^{p - 1}\frac {uk^{-u - 1}}{\left( - 1\right)^{u}} = \frac {u}{\left( - 1\right)^{u}}\sum_{k = 1}^{p - 1}k^{ - u - 1}\mod p$.

But by Fermat's Little Theorem, $ k^{p - 1}\equiv 1\mod p$ for every integer $ k$ such that $ 1\leq k\leq p - 1$. Thus, every such $k$ satisfies $ k^{ - u - 1}\equiv k^{ - u - 1}k^{p - 1} = k^{p - u - 2}\mod p$, and the relation [color=green][b](1)[/b][/color] becomes

$ \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}}\equiv\frac {u}{\left( - 1\right)^{u}}\sum_{k = 1}^{p - 1}k^{p - u - 2}\mod p$.

Now, $ p - u - 2\geq 1$ (since $ p\geq u + 3$) and $ p - u - 2\leq p - 2$. Also, $ p$ is an odd prime (since $ p$ is a prime and $ p > 2$). Now, according to http://www.problem-solving.be/pen/viewtopic.php?t=676 part [b]a)[/b] (and also http://www.mathlinks.ro/Forum/viewtopic.php?t=40171 ), we have:

[color=blue][b]Theorem 2.[/b] If $ p$ is an odd prime and $ \rho$ is an integer such that $ 1\leq\rho\leq p - 2$, then $ p\mid\sum_{k = 1}^{p - 1}k^{\rho}$.[/color]

Applying this Theorem 2 to our prime $ p$ and $ \rho = p - u - 2$ (we know that $ p$ is an odd prime and $ \rho = p - u - 2$ satisfies $ 1\leq p - u - 2\leq p - 2$), we get $ p\mid\sum_{k = 1}^{p - 1}k^{p - u - 2}$, so that $ \sum_{k = 1}^{p - 1}k^{p - u - 2}\equiv 0\mod p$, and thus

$ \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}}\equiv\frac {u}{\left( - 1\right)^{u}} \underbrace{\sum_{k = 1}^{p - 1}k^{p - u - 2}}_{\equiv 0\mod p} \equiv \frac {u}{\left( - 1\right)^{u}}\cdot 0 = 0\mod p$.

This completes the proof of Theorem 1.

[color=blue][b]4. A divisibility by $ p^3$[/b][/color]

We can use almost the same tactics to prove a similar result:

[color=blue][b]Theorem 3.[/b] Let $ p$ be a prime number such that $ p>3$. Then,

$ v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^p}\right)\geq 3$.[/color]

[i]Proof of Theorem 3.[/i] It is known that for every integer $ i$ such that $ 0<i<p$, we have $ p\mid \binom{p}{i}$ (since $ p$ is prime); in other words, $ \binom{p}{i}\equiv 0\mod p$.

Besides, $ p-2>0$ (since $ p>3>2$).

Set $ u=p$. Also, denote $ s_k=\sum_{i=2}^u\left(-1\right)^{u-i}\binom{u}{i}p^{i-2}k^{u-i}$ for every $ k\in\left\{1,2,...,p-1\right\}$. Obviously, $ s_k$ is an integer for every $ k$. Then, every $ k\in\left\{1,2,...,p-1\right\}$ satisfies

$ s_k=\sum_{i=2}^u\left(-1\right)^{u-i}\binom{u}{i}p^{i-2}k^{u-i}=\sum_{i=2}^p\left(-1\right)^{p-i}\binom{p}{i}p^{i-2}k^{p-i}$      (since $ u=p$)
$ =\sum_{i=2}^{p-1}\left(-1\right)^{p-i}\underbrace{\binom{p}{i}}_{\substack{\equiv 0\mod p,\\ \text{ since } 0<i<p}}p^{i-2}k^{p-i}+\left(-1\right)^{p-p}\binom{p}{p}\underbrace{p^{p-2}}_{\substack{\equiv 0\mod p,\\ \text{ since } p-2>0}}k^{p-p}$
$ \equiv \underbrace{\sum_{i=2}^{p-1}\left(-1\right)^{p-i}0p^{i-2}k^{p-i}}_{=0}+\underbrace{\left(-1\right)^{p-p}\binom{p}{p}0k^{p-p}}_{=0}=0+0=0\mod p$.

Just as in the proof of Theorem 1, we can show that

[color=green][b](2)[/b][/color] $ v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right) = 1 + v_{p}\left( \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \right)$.

Since $ u=p$, we have

$ v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right) = v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^p}\right)$

and

$ v_{p}\left( \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \right) = v_{p}\left( \sum_{k = 1}^{p - 1} \frac {pk^{p-1}+ps_k}{k^p\left(p - k\right)^p} \right)$
$ = v_{p}\left( p\cdot \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \right)$         (since $ \sum_{k = 1}^{p - 1} \frac {pk^{p-1}+ps_k}{k^p\left(p - k\right)^p} = \sum_{k = 1}^{p - 1} \frac {p\left(k^{p-1}+s_k\right)}{k^p\left(p - k\right)^p} = \sum_{k = 1}^{p - 1} p\cdot \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} = p\cdot \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p}$)
$ = \underbrace{v_p\left(p\right)}_{=1} + v_p\left( \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \right) = 1 + v_p\left( \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \right)$.

Thus, [color=green][b](2)[/b][/color] becomes

$ v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^p}\right) = 1 + \left(1 + v_p\left( \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \right)\right)$.

In other words,

$ v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^p}\right) = 2 + v_p\left( \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \right)$.

Hence, instead of showing $ v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^{p}}\right)\geq 3$, it will be enough to prove $ v_p\left( \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \right)\geq 1$. This is equivalent to $ v_p\left( \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \right) > 0$, i.e., to $ \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \equiv 0\mod p$. Here, we are using the fact that for each $k \in \left\{1,2,\ldots,p-1\right\}$, the fraction $\frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p}$ is a $p$-integers (because its denominator, $ k^p\left(p - k\right)^p$, is not divisible by $ p$, since $ 1\leq k\leq p - 1$ and since $ p$ is a prime), and thus it makes sense to speak of congruence modulo $p$ for the sum of these fractions. Let us study such a fraction $\frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p}$ (with $k \in \left\{1,2,\ldots,p-1\right\}$) more closely: Its numerator $ k^{p-1}+s_k$ is congruent to $ k^{p-1}$ modulo $p$ (since $ s_k\equiv 0\mod p$, and thus the term $ s_k$ can be omitted). Also, the denominator can be simplified: Since $ p - k\equiv - k\mod p$, we have $ k^p\left(p - k\right)^p\equiv k^p\left( - k\right)^p = \left( - 1\right)^pk^{2p} \mod p$. Hence, $ \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \equiv \frac {k^{p-1}}{\left( - 1\right)^pk^{2p}} \mod p$ (by the division rule). Therefore,

[color=green][b](3)[/b][/color] $ \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \equiv \sum_{k = 1}^{p - 1}\frac {k^{p-1}}{\left( - 1\right)^pk^{2p}} = \frac{1}{\left(-1\right)^p} \sum_{k = 1}^{p - 1}\frac {k^{p-1}}{k^{2p}} \mod p$.

But by Fermat's Little Theorem, $ k^p\equiv k\mod p$ for every integer $ k$. Thus, $ \left(k^p\right)^2\equiv k^2\mod p$, so that $ k^{2p}=\left(k^p\right)^2\equiv k^2\mod p$. Hence, for every $k \in \left\{1,2,\ldots,p-1\right\}$, we have $\frac{k^{p-1}}{k^{2p}} \equiv \frac{k^{p-1}}{k^2} \mod p$ (here we used the division rule again, because $k^{2p}$ and $k^2$ are rational numbers with $p$-adic valuation $0$). Hence, the relation [color=green][b](3)[/b][/color] becomes

$ \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \equiv \frac{1}{\left(-1\right)^p} \sum_{k = 1}^{p - 1}\underbrace{\frac {k^{p-1}}{k^2}}_{ = k^{\left(p-1\right)-2}=k^{p-3}} = \frac{1}{\left(-1\right)^p} \sum_{k = 1}^{p - 1}k^{p-3} \mod p$.

Now, $ p-3\geq 1$ (since $ p>3$ yields $ p-3>0$, and $ p-3\in\mathbb{Z}$) and $ p-3\leq p-2$. Also, $ p$ is an odd prime (since $ p$ is a prime and $ p > 2$). Applying Theorem 2 to our prime $ p$ and $ \rho = p - 3$ (we know that $ p$ is an odd prime and $ \rho = p-3$ satisfies $ 1\leq p-3\leq p - 2$), we get $ p\mid\sum_{k = 1}^{p - 1}k^{p - 3}$, so that $ \sum_{k = 1}^{p - 1}k^{p - 3}\equiv 0\mod p$, and thus

$ \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \equiv \frac{1}{\left(-1\right)^p} \underbrace{\sum_{k = 1}^{p - 1}k^{p-3}}_{\equiv 0\mod p} \equiv \frac{1}{\left(-1\right)^p}\cdot 0 = 0\mod p$.

This completes the proof of Theorem 3.

[EDIT: Made the proof of Theorem 1 slightly more formal, and added section 4. See [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=46121]the other thread[/url] for the old version of this post.

EDIT 2: Improved the exposition of $p$-integers and their congruence significantly.]

  Darij

[quote="TomciO"]
$ \sum_{i \equal{} 1}^{p \minus{} 1} \frac {1}{i} \equiv \sum_{i \equal{} 1}^{p \minus{} 1} i^{p \minus{} 2}$
[/quote]

Why is this true mod $ p^2$?

Yes, you are right. Thank you for pointing out the mistake. I have corrected the proof accordingly since it's not a big difference.

We will treat rational numbers, which have their denominator relatively prime to $ p$, as residues mod $ p$.
From the Euler's Theorem: $ \frac {1}{i} \equiv i^{p(p\minus{}1) \minus{} 1} \mod{p^2}$
So we see that:
\[ \sum_{i \equal{} 1}^{p \minus{} 1} \frac {1}{i} \equiv \sum_{i \equal{} 1}^{p \minus{} 1} i^{p(p\minus{}1) \minus{} 1} \equal{} \sum_{i \equal{} 1}^{\frac {p \minus{} 1}{2}} i^{p(p\minus{}1) \minus{} 1} \plus{} (p \minus{} i)^{p(p\minus{}1) \minus{} 1} \equiv \sum_{i \equal{} 1}^{\frac {p \minus{} 1}{2}} p(p(p\minus{}1) \minus{} 1)i^{p(p\minus{}1) \minus{} 2} \equiv \minus{}p \sum_{i \equal{} 1}^{\frac {p \minus{} 1}{2}} i^{p(p\minus{}1) \minus{} 2} \mod{p^2}\]
The congruence come from the fact that the rest term vanishes mod $ p^2$. We are left with proving that:
$ \sum_{i \equal{} 1}^{\frac {p \minus{} 1}{2}} i^{p(p\minus{}1) \minus{} 2} \equiv 0 \mod{p}$
or from FTL:
$ \sum_{i \equal{} 1}^{\frac {p \minus{} 1}{2}} \frac {1}{i^2} \equiv 0 \mod{p}$
Now if $ i, j \leq \frac {p \minus{} 1}{2}$ and $ \frac {1}{i^2} \equiv \frac {1}{j^2} \mod{p}$ then also $ (i \minus{} j)(i \plus{} j) \equiv 0 \mod{p}$ but since $ i, j \leq \frac {p \minus{} 1}{2}$ we must have $ i \equal{} j$. So the numbers: $ \frac {1}{i^2}$ for $ i \equal{} 1,2,...,\frac {p \minus{} 1}{2}$ are all different quadratic residues (and there are exactly $ \frac {p \minus{} 1}{2}$ quadratic residues), as well as the numbers $ i^2$ for $ i \equal{} 1,2,...,\frac {p \minus{} 1}{2}$ so:
$ \sum_{i \equal{} 1}^{\frac {p \minus{} 1}{2}} \frac {1}{i^2} \equiv \sum_{i \equal{} 1}^{\frac {p \minus{} 1}{2}} i^2 \equal{} \frac {p(p \minus{} 1)(p \plus{} 1)}{24} \equiv 0 \mod{p}$
which ends the proof.

Maybe we can use fields to solve this in a more efficient way!

We begin with a lemma.

Lemma. Let $k \in \mathbb{Z}$. Then $1^k + 2^k + \cdots + (p - 1)^k \equiv 0 \pmod{p}$ whenever $p - 1$ does not divide $k$.

Proof: This is an often used result in number theory. See my post in [url]http://www.artofproblemsolving.com/Forum/viewtopic.php?t=422958[/url] for a proof.

Unless mentioned otherwise, all quantities should be taken as elements of $\mathbb{Z}/p^2\mathbb{Z}$.
Next, observe that if $1 \leq i \leq p - 1$, we have
\[(p - i)(p + i) = p^2 - i^2 = -i^2,\]
which, after some rearranging, gives
\[\frac1{p - i} = -\frac{p + i}{i^2}.\]
Therefore,
\[1 + \cdots + \frac1{p - 1} = -\left(\frac{p + 1}{1^2} + \frac{p + 2}{2^2} + \cdots + \frac{p + (p - 1)}{(p - 1)^2}\right),\]
so, after splitting up the fractions on the right side and rearranging, we get
\[2\left(1 + \cdots + \frac1{p - 1}\right) = -p\left(1 + \frac 1{2^2} + \cdots + \frac1{(p - 1)^2}\right).\]
Since $p \neq 2$, if we can show that $p | 1 + \frac1{2^2} + \cdots + \frac1{(p - 1)^2}$, then we know that $p^2 | 1 + \frac12 + \cdots + \frac1{p - 1}$, as desired. Indeed, since $p > 3$, $p-1$ does not divide $-2$, so the lemma gives that
\[1 + \frac1{2^2} + \cdots + \frac1{(p - 1)^2} = 1^{-2} + 2^{-2} + \cdots + (p - 1)^{-2} \equiv 0 \pmod{p},\]
completing the proof.

is that obvious that we can write fractions mod n that way?

[quote="Peter"](Wolstenholme's Theorem) Prove that if \[1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{p-1}\] is expressed as a fraction, where $p \ge 5$ is a prime, then $p^{2}$ divides the numerator.[/quote]
$1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{p-1}\ = \sum_{i=1}^{\frac{p-1}{2}} (\frac{1}{i}+\frac{1}{p-i}) = \sum_{i=1}^{\frac{p-1}{2}} \frac{p}{i(p-i)}$. So it'a enough to show that $\sum_{i=1}^{\frac{p-1}{2}} \frac{1}{i(p-i)} \equiv 0 \mod{p}$. $\sum_{i=1}^{\frac{p-1}{2}} \frac{1}{i^2}=0$. It's obviously that if $i^2 \equiv j^2 \mod{p}$. Than $i \equiv j$, if $0<i,j<\frac{p+1}{2}$. So that summ is equivalent to $\frac{1}{x_1}+\cdots+\frac{1}{x_\frac{p-1}{2}}$, where $x_1, \cdots , x_\frac{p-1}{2}$ is all quadratic resedues $\mod{p}$. But $\frac{1}{x_i}$ is also quadratic resedue, so we need to show that $x_1+\cdots+x_\frac{p-1}{2} \equiv 0 \mod{p}$. We can do it using 2 ways:
1. Let $S$ be that sum, and let $x_j$ be a quadratic resedue more than 1, than $S\equiv x_jS \mod{p}$, because $x_ix_j$ is quadratic resedue. Than $S\equiv 0 \mod{P}$. Q.E.D.
2. Let $e$ be a primitive root modulo $p$. Than all quadratic resedues is $e^{2k}$. So we need to show that $e^2+\cdots + (e^2)^\frac{p-1}{2} \equiv 0 \mod{p}$. $\frac{(e^2)^\frac{p+1}{2}-1}{e^2-1}-1$ the last one is $0$ by the Fermat's theorem.

[b][size=100]well to prove the lemma that [i]Duelist[/i] said, ( 1^k + 2^k +... + p^k = 0 (mode p) if p-1 doesn't divide k) there is
 an easier way than what he has said in that page.

we know every odd prime number has primitive root . So if we let g be the primitive root of p , we know
 for each i , 1=< i =< p-1 , there exists a g^Si  in {1 , g , g^2 .... g^φ(p)-1 } that  i = g^Si ( mode p ).

So 1^k + 2^k +... + p^k = 1^k + 2^k +... +(P-1)^K = g^kS1 + g^kS2 + .... + g^kSp-2. (mode p)

We let T= 1 + g^k + g^2k + ... + g^(p-2)k.
Then T(g^k - 1) = (g^(p-1)k  - 1) , and we know p divides the right side, so it must divide the left side too.
But p -1 doesn't divide k , so p doesn't divide g^k - 1 , So p divides T.[/size][/b] :-D  :)

because of Euler's theorem we can say:

$\sum_{i=1}^{p-1} \frac{1}{i} \equiv \sum_{i=1}^{p-1} i^{p^2-p-1} = \sum_{i=1}^{\frac{p-1}{2}} (i^{p^2-p-1}+(p-i)^{p^2-p-1}) \equiv \sum_{i=1}^{\frac{p-1}{2}}  (-p)\times i^{p^2-p-2} \mod{p^2} $

so $\sum_{i=1}^{p-1} \frac{1}{i}  \equiv 0 \mod{p^2}$ if and only if $ \sum_{i=1}^{\frac{p-1}{2}} i^{p^2-p-2} \equiv 0 \mod{p}$

$ i^{p^2-p-2} \equiv (p-i)^{p^2-p-2} $ which implies $ \sum_{i=1}^{\frac{p-1}{2}}  i^{p^2-p-2} \equiv 0 \mod{p} $

 if and only if $ \sum_{i=1}^{p-1}  i^{p^2-p-2} \equiv 0 \mod{p}$

and with lemma $1^k + 2^k + \cdots + (p - 1)^k \equiv 0 \pmod{p}$ whenever $p - 1$ does not divide $k$ we're done!


Compute the coefficient of $x^{21}$ in the expansion of
\[(x+x^{2}+x^{3}+x^{4}+x^{5}+x^{6})^{6}\]


trigonometry
function
calculus
calculus computations

A clock has radius 20 m. At what rate is the distance between the tip of the second hand and the 12 o'clock mark changing when the second hand points to 4 o'clock?

The distance x between the 12 o'clock mark and the tip of the second hand is given by cosine law. Differentiating with respect to the angle between the 12 o'clock mark and the second hand will give you a function to calculate the rate of change at any point on the clock face. You'll need the angular velocity of the second hand in the equation you get.


Would 3 lines make 7 disjoint regions or 1 disjoint region?

Umm...3 lines would make 7 disjoint regions.

This is the same as the number of intersection points+1 right?
If so:
[hide]336[/hide]

[quote="bpms"]If so:
[hide]336[/hide][/quote]
Close.

[quote="rnwang2"]10 lines and 10 circles divide the plane into at most $n$ disjoint regions. Find $n$.[/quote]

Smells like a mildorf mock AIME problem.

[quote="mathgeniuse^ln(x)"]Smells like a mildorf mock AIME problem.[/quote]
It is.  :roll:

[hide]Euler's Theorem States that the v - e + f = 2 in all 2-dimensional graphs.  The number of vertices in the perfect construction of the graph with 10 circles is 90 b/c every circle will intersect every other circle exactly two times c(c+1) where c is the amount of circles.  The number of vertices that n intersecting lines will have must be (n)(n-1)/2 b/c every line will intersect every other line exactly once.  Every line will at best also intersect every circle exactly twice, so n times c times 2 are the amount of vertices constructed by intersecting the circles and lines.  The number of edges(e) will be twice the amount of vertices b/c every vertex has 4 edges, but every edge is share with by one vertex; hence, e=v*4/2=v*2=e.  So to answer the question at hand, v - e + f = 2 is by substitution v - v*2 + f = 2 which implies -v + f = 2.  So -[c(c+1) + n(n-1)/2 + n*c*2] + f = 2 which implies f = c(c+1) + n(n-1)/2 + n*c*2 + 2.  If n and c = 10 then f (the number of regions) = 10(11) + 10(9) + 10(10)(2) + 2 = 402.... The outside regions however are also being divided by the lines that are not edges which will be n*2 regions, hence 422.[/hide]

I don't think that is right, because the answer is 346, but that is good reasoning.

So how do you do this?  since no one has aposted a solution and im tryin to study for AIME

[hide]
Ten lines divide the plane into

$1+2+3+\ldots+10+1=56$ regions.

There are at most $2\cdot 10\cdot 10=200$ line-circle intersections,

and at most $2\cdot\dbinom{10}{2}=90$ circle-circle intersections.

This gives $56+200+90=346$ regions.[/hide]


Let $ a, b, c$ be the (distinct) side-lengths of a triangle, then

$ \sum\frac{a(b\plus{}c)}{(a\minus{}b)^2}\geq1$

WLOG we can assume that $ abc \equal{} 1$.
But $ c^2 > (a \minus{} b)^2 \Longleftrightarrow \frac {a(b \plus{} c)}{(a \minus{} b)^2} \ge \frac {a(b \plus{} c)}{c^2}$.
So $ \sum\frac {a(b \plus{} c)}{(a \minus{} b)^2}\ge \sum\frac {a(b \plus{} c)}{c^2} \ge 6 > 1$.


Find all positive reals $a,b,c$ which fulfill the following relation
\[ 4(ab+bc+ca)-1 \geq a^2+b^2+c^2 \geq 3(a^3+b^3+c^3) . \]

created by Panaitopol Laurentiu.

Here the short version of my sol:

from the first piece of inequality we get $a+b+c \geq 1$:
order inequality, replacing 1 ($ab+bc+ac$ by $a+b+c$ will keep the inequality, then simplify and again do this gives $a+b+c \geq 1$

from the second part we get $a+b+c \leq 1$:
$(a+b+c)(a+b+c) \leq 3(a+b+c)$ but the problem says without $(a+b+c)$ it's $\geq$ so $a+b+c \leq 1$

Therefor, a+b+c = 1
which also implies that order inequality in the second case is an equality, so a=b=c

Which results in $a=b=c=\frac{1}{3}$

i don't get this solution
can anybody clear it up to me?

what is it exactly you don't get?

I first prove that a+b+c must be >= 1 (first part)
Then I prove that a+b+c must be <= 1 at the same time, so that means a+b+c = 1 for sure.

from there I call in the order inequality I used to prove the above, which states that it becomes an equality iff a=b=c. So since the sign is reversed, we must have an equality here for the given to be possible, thus a=b=c with a+b+c=1, this results in a=b=c=1/3.

Is it one of the proofs of the first/second step you don't get? :)

actually both of them i don't understand (what is "order" ineq?)

:) order ineq says that 5 bills of 5 dollar + 2 bills of 1 dollar is worth more than 2 bills of 5 dollar and 5 bills of 1 dollar :)

(so the greedy law, take most of the highes and fewest of the lowest to get best result)

thus, order ineq: if a>=b>=c then a^2+b^2+c^2>=ab+bc+ca [ that is a common ineq, which can also be constructed by taking (a-b)^2+(b-c)^2+(c-a)^2>=0 ]

that's quite important, a^2+b^2+c^2>=ab+bc+ca for all a,b,c in R.

(so in each of the steps I could have added: assume without loss of generality that a>=b>=c)

Is it clear now, or do you want me to explain it in full detail? :)

Adding $2(a^2+b^2+c^2)$ to both sides of the left inequality, we obtain

\[2(a+b+c)^2-1 \geq 3(a^2+b^2+c^2).\]

Clearly, $3(a^2+b^2+c^2) \geq (a+b+c)^2$ (easily proven by Cauchy or Power-Mean, for example and equality iff $a=b=c$), so we have

\[2(a+b+c)^2-1 \geq (a+b+c)^2 \iff a+b+c \geq 1,\]

since $a,b,c$ are positive.

Now note that $3(a^3+b^3+c^3) \geq (a+b+c)(a^2+b^2+c^2)$ which easily follows from $(a^3+a^3+b^3)/3 \geq a^2b$, etc by AM-GM.  The right side of the inequality implies that $a+b+c \leq 1$, so combining this with the above, we conclude that $a+b+c=1$, so equality must hold, or $a=b=c=1/3$.

Yes. [quote="ThAzN1"]... so equality must hold, or $a=b=c=1/3$.[/quote]=> here for the case it may be unclear: you substitute the given of equalness in the second step, to find that (like I said) to find another equality, from which you can conclude like I said that a=b=c. :)

thanks, i get it now.
I think order ineq is the ineq known in my country as "rearrangament ineq":
given $a_{1} \geq \cdots \geq a_{n}$ and $b_{1} \geq \cdots \geq b_{n}$ we have:
$a_{1} \cdot b_{1} + \cdots + a_{n} \cdot b_{n}  \geq a_{1} \cdot b_{ \tau (1) } \cdots a_{n} \cdot b_{ \tau (n) } \geq a_{1} \cdot b_{n} + \cdots + a_{n} \cdot b_{1}$
for any permutation $\tau$ of $(b_{1}, \cdots, b_{n})$.

yes, that is another (even better) name for it, rearrangement :)

[quote=Mamat]$\frac{4(a+b+c)^2}{3}\geq4(ab+ac+bc)\geq a^2+b^2+c^2+1\geq \frac{(a+b+c)^2}{3}+1 \Rightarrow a+b+c\geq1$
$a^2+b^2+c^2 \geq 3(a^3+b^3+c^3) \geq (a+b+c)(a^2+b^2+c^2) \Rightarrow  a+b+c\leq1$
 Then $ a=b=c=\frac{1}{3}$[/quote]

Nice! I did the same thing, after spending a ton of time on it. A bit of an explanation: The first one follows from a^2+b^2+c^2+2ab+2ac+2bc >= 3ab+3ac+3bc, which is true by a^2+b^2-2ab >=0, so adding all cyclic permutations of it and dividing by two, gives a^2+b^2+c^2-ab-ac-bc >= 0. (a^2+b^2+c^2)(1+1+1) >= (a+b+c)^2 by C-S, so the third-fourth part is true. thanks @below for clarifying a final part, I thought you would have to use some inequality but I wasn’t considering just expanding :)

[b]Claim:[/b] $3(a^3+b^3+c^3)\ge (a+b+c)(a^2+b^2+c^2)$

[b]Proof:[/b] Rearrange the inequality to
\[2a^3+2b^3+2c^3\ge a^2b+ab^2+b^2c+bc^2+c^2a+ca^2.\]
It suffices to prove
\[a^3+b^3\ge a^2b+ab^2\]
but this is equivalent to
\[(a-b)^2(a+b)\ge 0\]
after rearranging, clearly true since $a$, $b$, and $c$ are positive reals.
$\blacksquare$


$ f$ is a real-valued function on the reals. It satisfies $ f(x^3 \plus{} y^3) \equal{} (x \plus{} y)(f(x)^2 \minus{} f(x) f(y) \plus{} f(y)^2)$ for all $ x, y$. Prove that $ f(1996x) \equal{} 1996 f(x)$ for all $ x$

[hide="Hint"] Use $ 2$ lemmas:
1) If $ f(ax)\equal{}af(x)\forall x$ then $ f(\sqrt[3]{a}x)\equal{}\sqrt[3]{a}f(x)\forall x$ ($ a>0$)
2) If $ f(ax)\equal{}af(x);f(bx)\equal{}bf(x)$ then $ f((a\plus{}b)x)\equal{}(a\plus{}b)f(x)$ ($ a,b>0$)[/hide]

Let me complete this argument.

$ (1)$ $ f(x^3\plus{}y^3)\equal{}(x\plus{}y)(f(x)^2\minus{}f(x)f(y)\plus{}f(y)^2)$ for all $ x,y\in\mathbb{R}$

$ x\equal{}y\equal{}0$ gives $ f(0)\equal{}0$.
Then $ y\equal{}0$ gives $ (2)$ $ f(x^3)\equal{}xf(x)^2$ for all $ x\in\mathbb{R}$.

Then $ f(x)f(y)\equal{}\sqrt[3]{xy}\left[ f(\sqrt[3]{x})f(\sqrt[3]{y}) \right] ^2$ for all $ x,y\in\mathbb{R}$.
So $ (3)$ $ f(x)f(y)\ge 0$ for all $ x,y\in\mathbb{R},xy\ge 0$.

If $ n\in\mathbb{N}$ with $ f(nx)\equal{}nf(x)$ for all $ x\in\mathbb{R}$, then using $ (2)$
$ nxf(x)^2\equal{}nf(x^3)\equal{}f(nx^3)\equal{}(\sqrt[3]{n}x)f(\sqrt[3]{n}x)^2$
and using $ (3)$ we have $ \sqrt[3]{n}f(x)f(\sqrt[3]{n}x)\ge 0$.
So $ f(\sqrt[3]{n}x)\equal{}\sqrt[3]{n}f(x)$ for all $ x\in\mathbb{R}$. (using $ f(0)\equal{}0$ for $ x\equal{}0$)

And then using $ (1)$ and $ (2)$
$ f((n\plus{}1)x)\equal{}f((\sqrt[3]{nx})^3\plus{}(\sqrt[3]{x})^3)\\
\hspace*{0.67in}\equal{}(\sqrt[3]{nx}\plus{}\sqrt[3]{x})(f(\sqrt[3]{nx})^2\minus{}f(\sqrt[3]{nx})f(\sqrt[3]{x})\plus{}f(\sqrt[3]{x})^2)
\\ \hspace*{0.67in}\equal{}(\sqrt[3]{n}\plus{}1)\sqrt[3]{x}\, ((\sqrt[3]{n})^2\minus{}\sqrt[3]{n}\plus{}1)f(\sqrt[3]{x})^2\\ \hspace*{0.67in}\equal{}(n\plus{}1)f(x)$
for all $ x\in\mathbb{R}$.

Then by inuction $ f(nx)\equal{}nf(x)$ for all $ n\in\mathbb{N}_0,x\in\mathbb{R}$.
$ (2)$ gives $ f(1)\equal{}f(1)^2$, so $ c: \equal{}f(1)\in\{0,1\}$.
Then $ f(n)\equal{}cn$ for all $ n\in\mathbb{N}$ and $ (x,y)\equal{}(2,\minus{}1)$ in $ (*)$ gives
$ 7c\equal{}4c^2\minus{}2cf(\minus{}1)\plus{}f(\minus{}1)^2\Rightarrow  f(\minus{}1)\equal{}\minus{}c$ or $ f(\minus{}1)\equal{}3c$.
But $ (2)$ gives $ f(\minus{}1)\equal{}\minus{}c$, so $ f(n)\equal{}cn$ for all $ n\in\mathbb{Z}$.

Now $ nf({m\over n})\equal{}f(m)\equal{}cm$ for all $ m\in\mathbb{Z},n\in\mathbb{N}$,
so $ f(x)\equal{}cx$ for all $ x\in\mathbb{Q}$.

For all $ x\in\mathbb{R}$ we find $ x_1,x_2,\ldots\in\mathbb{Q}$ with $ x_n\mathop{\longrightarrow}_{n\to\infty}x$.
Then $ y_n: \equal{}\sqrt[3]{x_n^3\minus{}x^3}\mathop{\longrightarrow}_{n\to\infty}0$ with $ x^3\plus{}y_n^3\equal{}x_n^3\in\mathbb{Q}$ and $ x\plus{}y_n\mathop{\longrightarrow}_{n\to\infty}x$.
So for $ x\not\equal{}0$ we have $ x\plus{}y_n\not\equal{}0$ for sufficiently large $ n$, and then
$ c(x^2\minus{}xy_n\plus{}y_n^2)\equal{}{f(x^3\plus{}y_n^3)\over x\plus{}y_n}\equal{}f(x)^2\minus{}f(x)f(y_n)\plus{}f(y_n)^2\\ \hspace*{1in}\equal{}{3\over 4}f(x)^2\plus{}({f(x)\over 2}\minus{}f(y_n))^2\ge {3\over 4}f(x)^2$
and $ n\to\infty$ gives $ cx^2\ge {3\over 4}f(x)^2$ for all $ x\not \equal{}0$.
So $ f(x)\to 0$ for $ x\to 0$. (using $ f(0)\equal{}0$)

And now for $ x\in\mathbb{R}$ we find $ x_1,x_2,\ldots\in\mathbb{Q}$ with $ x_n\mathop{\longrightarrow}_{n\to\infty}\sqrt[3]{x}$.
Then $ y_n: \equal{}\sqrt[3]{x\minus{}x_n^3}\mathop{\longrightarrow}_{n\to\infty}0$ with $ x\equal{}x_n^3\plus{}y_n^3$ and also $ f(y_n)\mathop{\longrightarrow}_{n\to\infty}0$.
This gives
$ f(x)\equal{}f(x_n^3\plus{}y_n^3)\equal{}(x_n\plus{}y_n)(f(x_n)^2\minus{}f(x_n)f(y_n)\plus{}f(y_n)^2)
\\ \hspace*{1.11in}\equal{}(x_n\plus{}y_n)(cx_n^2\minus{}cx_nf(y_n)\plus{}f(y_n)^2)\mathop{\longrightarrow}_{n\to\infty}cx$
and therefore $ f(x)\equal{}cx$ for all $ x\in\mathbb{R}$.

So we find only $ 2$ solutions $ f\equiv 0$ and $ f(x)\equal{}x,x\in\mathbb{R}$.


If i partially solved a solution, according to the grading scale, I can still receive some points. Should i just send in the solution with the proof to where i got to w/o an answer?

It's best to solve the problem, which almost always guarantees a 5/5. However, partially solving a problem can almost always get you a 3, or maybe even a 4, depending on how close you got to the answer.

Hope this helps.  :)


probability
analytic geometry
trigonometry
quadratics
inequalities

I am going to post a string of NYCIML questions.

#1:
an ordinary pack of playing cards is shuffled, and two cards are delt facce up.  Find the probability that one of these is a spade.

Exactly one or at least one?  Two different questions...

[hide="Exactly one"]spade, not-spade = $\frac{13}{52}\cdot\frac{39}{51} = \frac{507}{2652} = \frac{13}{68}$
not-spade, spade = $\frac{39}{52}\cdot\frac{13}{51} = \frac{507}{2652} = \frac{13}{68}$
So the answer should be $\frac{13}{34}$, I believe.[/hide]

[hide="At least one"]1 - (not-spade, not-spade) = $1-\frac{39}{52}\cdot\frac{39}{51} = \frac{29}{68}$[/hide]

It all depends on what you're being asked for.

I believe these are both correct.

Small error there, the second one should be...
[hide]$1-\frac{39}{52}\cdot\frac{38}{51} = \frac{15}{34}$
Because there is one less non-spade card after the first choice.[/hide]

[quote="lyra"]an ordinary pack of playing cards is shuffled, and two cards are delt facce up.  Find the probability that one of these is a spade.

1/104?[/quote]

Reality check: if I turn over a couple of cards from a deck, I should expect to get a spade between a quarter and a half of the time.  If 1/104 were the correct answer, that would be telling me that it's nearly impossible to draw a spade on two tries -- something which common sense should dictate is totally unreasonable.

As to JBL your right, I was being stupid, I am going to start a string of questions here if no one minds?

Problem #2
In a rectangular coordinate system, a tangent from teh point (24,7) to the circle whose equation is x^2+y^2=400 has a point of tangency (a,b) where b>0. Find a.

Smiles,
lyra

I'm not completely sure about this solution so if you think there's something wrong with it, feel free to attack it.

[hide="Solution for problem 2"]

Let the center of this circle be $O$ and certain point that has $b > 0$ be $A$. Also, call $(24,7)$ as $B$. From this, we know that there is a right triangle $OAB$ where $A$ is the right angle. $OB$ is simply distance from origin to $(24,7)$ and this can be calculated $\sqrt{24^2+7^2} = 25$. Also, $OA$ is radius so we know that it's 20. This means that $AB = \sqrt{25^2-20^2} = 15$. So, comparing $A$ And $B,$ we get $(24-a)^2+(7-b)^2 = 225$. But, we also know that $a^2+b^2 = 400$ by the problem. Playing with algebra gives $24a+7b = 400$. At $(12,16)$ this equation is satisfied with $b > 0$. I had to use calculator for this part but yeah, this one works out so maybe it is right. [/hide]

Nice solutions Silver Falcon and alan!!!  Silver Falcon: can you explain what you did with the algebra, I kindof see what you did but I am not quite sure.

Problem #3:
Find the smallest positive value of m such that the solutions (for x) of ((x^2+x+1)/x)=m are real numbers

is m=3?

[quote="lyra"]Problem #3:
Find the smallest positive value of m such that the solutions (for x) of ((x^2+x+1)/x)=m are real numbers

is m=3?[/quote]
[hide="Solution 1"]Rewrite the equation into a quadratic: $x^2+(1-m)x+1=0$. Since the roots of this equation must be real, its discriminant must be nonnegative so $(1-m)^2-4(1)(1)=m^2-2m-3=(m-3)(m+1)\ge0$. Solve for $m$ and you get $m\ge3$ because $m$ is positive.[/hide]

[hide="Solution 2"]This solution requires a bit of an insight: Write the equation as $m=x+1+\frac1x$. Easily, by AM-GM, we have $x+\frac1x\ge2$ because $x$ is a nonzero real number. So, $m=x+1+\frac1x\ge3$.[/hide]

So you are saying if you had to write a solution it would be m=3 because that is the smallest.  That is what I did.

Smiles,
lyra

Problem #4:
For all real numbers x, $f(x)=\sqrt{x^2+25} + \sqrt{(x-1)^2+25}$. If the minimum value of $f(x)$ is $\sqrt{a}$, find a.

Smiles,
lyra

[quote="lyra"]Nice solutions Silver Falcon and alan!!!  Silver Falcon: can you explain what you did with the algebra, I kindof see what you did but I am not quite sure.[/quote]

Well, you have $(24-a)^2 + (7 - b)^2 = 225$ and $a^2+b^2 = 400$. Expand the first one and subtract to cancel $a^2$ and $b^2$. You should get something as what I have.

Oh, yes I see what your saying.

The next one is pretty fun, you should try it.

Smiles,
lyra

[quote="chess64"][hide="Cauchy it"]
By Cauchy's inequality,

\begin{eqnarray*} (1\cdot \sqrt{x^2+25}+1\cdot \sqrt{(x-1)^2+25})^2 &\le & [1+1][(x^2+25)+((x-1)^2+25)]\\ &\le & 2(2x^2-2x+51)\\ &\le & (2x-1)^2+101\\ &\le & 101\\ \Rightarrow a &=& \boxed {101} \end{eqnarray*}
[/hide][/quote]

Ooh, good solution, I didn't think of that, that takes away some messy stuff!

Smiles,
lyra


Is there any good source where I can learn everything about barycenters and their applications?
I have seen mr. Luis Geometria solve a lot of problems using that technique hin Gemetry problems section.Has he or someone else   have any material on this topic? I am in urgent need of it. Thank you very much in advance.

Dear Mathlinkers,
see for example
http://garciacapitan.auna.com/baricentricas/  (in Spain)
Sincerely
Jean-Louis


find all natural numbers $n$ such that $2^{n}+1$is the power of natural number.

The only solution is 2^3+1=3^2. Assume 2^n+1=x^a where a>1. Then 2^n=(x-1)(x^(a-1)+x^(a-2)+...+x+1) Then x=2^k+1. As a result a must be even for otherwise the second expression would be a sum of an odd number of odd numbers which can't be a power of two. Set a=2b. Then one has 2^n=(x^b-1)(x^b+1). This results in n=3, x=3, a=2 as the only solution for a>1.


geometry
trapezoid
rectangle
power of a point
radical axis

[hide]Note that $\triangle OAB$ and $\triangle O'A'B'$ are isosceles with bases $\overline{AB}$ and $\overline{A'B'}$ respectively.
Draw $\overline{OO'}$. It bisects $\angle A'O'B'$ and is thus perpendicular to $\overline{A'B'}$. Similarly it is perpendicular to $\overline{AB}$. Thus $\overline{AB}\parallel\overline{A'B'}$.[/hide]

O,A,B  are collinear   :maybe:  so what triangle $OAB$

The way you state it, it sounds like you construct 2 line segments from $O$, one for each of the possible tangents, and each one only intersects circle $O$ once.  In that case $AB$ and $A'B'$ are obviously parallel.

Now that I know $A$ and $B$ are colinear, here's a proof:

[hide]Look at $A$, the point above $O$ where $AB$ intersects circle $O$.  Call the angle $AOO'$ $\theta$.  Call the radius of $O$ $r$, and the radius of $O'$ $r'$.  Call the length of $OO'$ $d$.  The height, $h$ of $A$ above line $OO'$ is $r$sin($\theta$).  Now look at where line $AB$ is tangent to circle $O'$, and call it point $C$.  Triangle $OCO'$ has right angle $C$ and acute angle $\theta$.  Looking at it we can see that sin($\theta$) $= \frac{r'}{d}$, and therefore $h = \frac{r*r'}{d}$.  The same argument applies to the other circle, and we can see that $A$ and $A'$ have the same height above $OO'$, as do $B$ and $B'$.  Therefore, $AA'$ and $BB'$ are both horizontal, and parallel.[/hide]

[quote="silouan"]Circles with centers $O$ and $O'$ are disjoint. A tangent from $O$ to the second circle intersects the first in $A$ and $B$ .
A tangent from $O'$ to the first circle intersects the second circle in $A'$ and $B'$ such that $A$ and $A'$ lie on the same side of $OO'$ .Prove that $AA'B'B$ is a trapezoid .[/quote][color=darkblue]Denote : the circles $w=C(O)$, $w'=C(O')$ ; the tangent points $T\in w$, $T'\in w'$ [u]so that the line[/u] $OO'$ [u]separates these points[/u] $T$, $T'$; the intersection $S\in \overline{BOAT'}\cap\overline{A'O'B'T}$. Therefore, the quadrilateral $OTO'T'$ is cyclically , i.e. $\widehat{AOT}\equiv\widehat{A'O'T'}$ $\Longrightarrow$ the isosceles triangles $AOT$, $A'O'T'$ are similarly $\Longrightarrow$ $\widehat{OAT}\equiv\widehat{T'A'T}\ ,\ \widehat{STB}\equiv\widehat{BT'B'}$ $\Longrightarrow$ the quadrilaterals $ATA'T'$, $BTB'T'$ are cyclically $\Longrightarrow$ $SA\cdot ST'=ST\cdot SA'\ ,\ SB\cdot ST'=ST\cdot SB'$ $\Longrightarrow$ $\frac{SA}{SB}=\frac{SA'}{SB'}$ $\Longrightarrow$ $\boxed{\ AA'\parallel BB'\ }\ .$

[b]Remarks.[/b] Prove easily that : $BT\parallel A'T'$, $AT\parallel B'T'$, i.e. and the quadrilaterals $BTA'T'$, $ATB'T'$ are trapezoids ; if denote the intersections $U\in AT\cap A'T'$ and $V\in BT\cap B'T'$ then the quadrilateral $TUT'V$ is rectangle and the line $UV$ is radical axis between the circles $w$, $w'$. [/color]


Show that there exist infinitely many natural numbers that are not representable as sum of two different powers of $2$ (with non-nagative exponents) and a prime number.

I can give you the classic proof by Crocker, if it is of interest.


Does anyone know where can I found the APMO tests? :D

Currently at http://www.kalva.demon.co.uk/apmo.html and very soon at http://www.mathlinks.ro/Forum/resources.php?c=1&cid=20


it's well-known that :
 1+2^3+3^3+...............+n^3=(n(n+1)/2)^2
 but i want someone to find it with a good way

no man you did not understand me
 calculate
  1+2^3+3^3+...................+n^3

it's true with n=1 or n=2.Then if it's true with n=k, you can easily prove that it's true with n=k+1.I think it's a traditional way to prove the problems like this.What do you think?

I think he understood you well (or at least I understand it the same way).
What do you mean by 'calculate'¿ Rust just gave you one idea how to proof it by induction.
You could also take a look at http://www.mathlinks.ro/Forum/viewtopic.php?t=59905 , it has a similar content.


Two friends A and B receive cups of coffee those are at equal temperature.A adds some cool cream immediately and takes his coffee 10minutes later.B waits for 10 minutes,and adds the same amount of cool cream and begins to take.Decide who takes hotter coffee?

I cannot understand how should I use Newton's law of cooling here in this example.Please help me to start with.

Assuming that the cool cream is cooler than room temperature, friend B takes the hotter coffee.

Newton's law of cooling states that the rate of change of the temperature of an object is proportional to the difference between its own temperature and the temperature of its surroundings.

The rate of change of temperature when the cream is immediately added has 10 minutes worth of effect on the temperature, combined with the temperature of its surroundings.

The rate of change of temperature has no time have much effect on the temperature of friend B's coffee, so only the surroundings' temperature cooled the coffee.


[quote="Ahiles"][color=brown]Let $ a,b,c$ be positive reals with $ ab \plus{} bc \plus{} ca \equal{} 3$. Prove that:
\[ \frac {1}{1 \plus{} a^2(b \plus{} c)} \plus{} \frac {1}{1 \plus{} b^2(a \plus{} c)} \plus{} \frac {1}{1 \plus{} c^2(b \plus{} a)}\le \frac {1}{abc}
\]
[/color][/quote]

It just mathlinks contest but weaker  :wink: .

[quote="silouan"]Yes it is very similar and here there exist and easy solution .
We have

$ \sum\frac {1}{1 \plus{} a^2(b \plus{} c)}\leq\sum\frac {1}{abc \plus{} a^2(b \plus{} c)} \equal{} \sum\frac {1}{3a} \equal{} \frac {1}{abc}$[/quote]

Nice solution,silouan !  :o

[quote="akai"]
Nice solution,silouan !  :o[/quote]

Thank you akai  :) .

Well the nice solution has already been posted... so I might as well note that there is a lower bound with Jensen's:
Let $ f(x)\equal{}\frac{1}{x\plus{}k}$ which is convex for arbitrary $ k$. In particular set $ k\equal{}1\minus{}abc$.
\[ \sum\frac{1}{1\plus{}a^2(b\plus{}c)}\equal{}\sum f(3a)\geq\frac{1}{a\plus{}b\plus{}c\plus{}\frac13\minus{}\frac{abc}{3}}\]

[quote="silouan"]Yes it is very similar and here there exist and easy solution .
We have

$ \sum\frac{1}{1\plus{}a^2(b\plus{}c)}\leq\sum\frac{1}{abc\plus{}a^2(b\plus{}c)}\equal{}\sum\frac{1}{3a}\equal{}\frac{1}{abc}$[/quote]

how did you write first inequality? i didn't understand why abc <= 1? (abc small or equal = 1)

sorry for my english.

Use am_gm
$\sum_{cyc} ab \geq3 \sqrt[3] {a^2b^2c^2}$

[quote="Ahiles"]Let $ a,b,c$ be positive reals with $ ab \plus{} bc \plus{} ca \equal{} 3$. Prove that:
\[ \frac {1}{1 \plus{} a^2(b \plus{} c)} \plus{} \frac {1}{1 \plus{} b^2(a \plus{} c)} \plus{} \frac {1}{1 \plus{} c^2(b \plus{} a)}\le \frac {1}{abc}.
\][/quote]

\[ \frac {1}{1 \plus{} a^2(b \plus{} c)} \plus{} \frac {1}{1 \plus{} b^2(a \plus{} c)} \plus{} \frac {1}{1 \plus{} c^2(b \plus{} a)}\le Q \le \frac {1}{abc}.
\]

$Q=\frac{1}{3}(\frac{c(1+a)}{1+b}+\frac{a(1+b)}{c+1}+\frac{b(c+1)}{1+a})$

We have \[\sum_{cyc} \frac{1}{1+a^2(b+c)}\leq \frac{1}{abc} \iff \sum_{cyc}\frac{1}{3a}-\frac{1}{1+a(3-bc)}\geq 0 \iff \sum_{cyc} \frac{1-abc}{3a(1+3a-abc)} \geq 0\iff 1\geq abc\] which follows from \[1=\frac{ab+bc+ca}{3}\geq \sqrt[3]{a^2b^2c^2} \implies 1\geq abc.\]


geometric series
real analysis
real analysis unsolved

The series $1+\frac12+\frac13+\cdots+\frac18+\frac1{10}+\cdots\frac1{18}+\frac1{20}+\cdots$ "strangely" converges. The sum of every line \[1+\frac12+\frac13+\cdots+\frac18\]  \[\frac1{10}+\cdots+\frac1{18}+\cdots+\frac1{88}\]  \[\cdots\] is $\le 8^{n}\frac1{10^{n-1}}$.
Then \[\sum_{n=1}^{\infty}8^{n}\frac1{10^{n-1}}=400\]

Nene beat me by a minute or two :-)

No -- there are $8\cdot9^{n}$ numbers with $n+1$ digits, none of which is 9, so the sum of their reciprocals is bounded above by $\frac{8\cdot9^{n}}{10^{n}}$ and the entire sum is bounded by $\sum_{n\geq 0}\frac{8\cdot9^{n}}{10^{n}}= 72$.

[quote="Ravi B"]Yes, except I think that your last geometric series evaluates to 80, not 72.  Some of us with too much time on our hands figured out that the sum is approximately 22.9.  See
[url]http://www.artofproblemsolving.com/Forum/viewtopic.php?t=32625[/url].[/quote]

Yes, I accidentally started my sum at $n = 1$ instead of $n = 0$. :oops:

By the way, it's not as hard as you suggested in that post to extend your method to grouping by the first two digits.  One of the 72-term sum we need is (I think) $h_{88}-h_{9}-\frac1{19}-\frac1{29}-\frac1{39}-\frac1{49}-\frac1{59}-\frac1{69}-\frac1{79}$ where $h_{n}$ is the $n$th harmonic number, which is easy to approximate.  Using Mathematica to get that sum exactly, and following through with the same methods, I get an upper bound of $23.25777\ldots$.


inequalities
calculus
inequalities unsolved

[quote="imababy"][quote="hungkhtn"]Find the minimum of:
$\frac{a+2b}{a+2c}+\frac{b+2c}{b+2a}+\frac{c+2a}{c+2b}$[/quote]
I dont know why you cant slove it. It's very easy !
P >= 3.
\[ P+3= 2(a+b+c)(\frac{1}{a+2c}+\frac{1}{b+2a}+\frac{1}{c+2b}) \geq 6  \]
+++++++>>>>>>>> P>=3
and P can be 3 when a=b=c>0[/quote]

  Really,so how about the case in which at least one of three nos is less than 0...
I don't think it can have minimum value.....Because by specializing it we can see there will be alot of set (a,b,c ) that can makes it tend to negative infinite...
  Hope i'm not wrong...

Oh..I'm Sorry.. Sorry alot. My problem ism't it. Here is right:

Find the minimum of:

$\frac{a+2c}{b+2c}+\frac{b+2a}{c+2a}+\frac{c+2b}{a+2b}$

With $a,b,c \ge 0$.

[quote="Kummer"]For c tend to -1( but still less than -1)..a=2 and b=0 we have negative infinite....I think there must be at least 1 more conditions for a,b,c...Agree with Imababy,if a,b,c>0 this inequality is very easy...[/quote]

Uh`, i didnt conside some case!    But i think a,b,c>0 must be on!@@@@@@@@

Yes. Mo matter. All problems of mine allways have condition $a,b,c \ge 0$.

[quote="Peter VDD"][quote="hungkhtn"]Find the minimum of:

$\frac{a+2c}{b+2c}+\frac{b+2a}{c+2a}+\frac{c+2b}{a+2b}$

with $a,b,c\ge0$[/quote]

I still don't see the problem in imababy's (trivial) solution? That are the conditions he took right? :?[/quote]

hungkhtn had a typo originally, and now he fixed his post.

I think the classical substitution $b=a+x$, $c=a+x$, $x,y \geq 0$ works here to show that
$\frac{a+2c}{b+2c}+\frac{b+2a}{c+2a}+\frac{c+2b}{a+2b} \geq 3$.

Hmm... what's wrong with this?

$\sum_{cyc}\frac{a+2c}{b+2c} \ge 3$

$\sum_{cyc}\frac{a-b}{b+2c} \ge 0$

$\sum_{cyc}\frac{a}{b+2c} \ge \sum_{cyc}\frac{b}{b+2c}$

which follows from rearrangement?

Denote for short $A=\sum_{cyc}\frac{a}{b+2c}, B=\sum_{cyc}\frac{b}{b+2c}, C=\sum_{cyc}\frac{c}{b+2c}$.

I thought it was quite obvious that $A\ge B\ge C$... apparently it is not that easy to prove this. The part $B\ge C$ is trivial but the part $A\ge B$ is not. We have:
$A-B = \frac{2S-3T+3xyz}{(y+2z)(z+2x)(x+2y)}\ge0$ with $S=x^3+y^3+z^3, T=xy^2+yz^2+zx^2$

I think this nice ineq has been on before? But it is not easy indeed. :)

[quote="imababy"]I dont know why you cant slove it. It's very easy !
P >= 3.
\[ P+3= 2(a+b+c)(\frac{1}{a+2c}+\frac{1}{b+2a}+\frac{1}{c+2b}) \geq 6  \]
+++++++>>>>>>>> P>=3
and P can be 3 when a=b=c>0[/quote]

I think imababy solution is nicest and shortest

It's interesting that hungkhtn ineq is equivalent to

2(a^3+b^3+c^3) + 3abc >= 3(ab^2+bc^2+ca^2)

So, the natural question is to find the maximum k such that

        a^3 + b^3 + c^3 + kabc >= (1+k/3)(ab^2+bc^2+ca^2)

Namdung

[quote="Namdung"]I think imababy solution is nicest and shortest[/quote]No, imababy works with an old version...

[quote="Namdung"]It's interesting that hungkhtn ineq is equivalent to

2(a^3+b^3+c^3) + 3abc >= 3(ab^2+bc^2+ca^2)

So, the natural question is to find the maximum k such that

        a^3 + b^3 + c^3 + kabc >= (1+k/3)(ab^2+bc^2+ca^2)

Namdung[/quote]isn't that exactly what I said? ;)

Oh, yes, so sorry. For long time I've not been here and I did so many misteakes.

The ineq  2(a^3 + b^3 + c^3) + 3abc >= 3(ab^2+bc^2+ca^2)  (*)

can be proven as Vasc comment: put b = a + x and c = a+ y then

        LHS - RHS = 3a(x^2 - xy + y^2) + 2x^3 + 2y^3 - 3xy^2

My question about maximal k is still in force: Find the max k such that

                    (a^3 + b^3 + c^3) + kabc >= (1+k/3)(ab^2+bc^2+ca^2)
for all a, b, c >= 0.

In (*) k = 3/2, but I believe that it can be replaced by greater constant.

Also not that k = 3 not works. Just take a = 0, b = 2, c = 3.

[u]A easy generalization[/u]:

$\{ x,y,a,b,c\} \subset (0,\infty),\ x<y\Longrightarrow \sum \frac{a+yb}{xa+yc}\ge 3\cdot \frac{2y-x}{y^2-x^2}.$

(with equality iff $a=b=c,\ y=x+1$).

Thus, for $x<y\ne x+1$, the previous inequality is strictly !

[u]A particular case:[/u] $x>0\Longrightarrow \sum \frac{(a+b)+xb}{c+x(a+c)}\ge 3\cdot \frac{x+2}{2x+1}$ (with equality iff $a=b=c$).

[u]Remark.[/u] What is the minimum for the sum $\sum \frac{a+b}{a+c}\ ?$

$\sum_{cyc}\frac{a+b}{c+a}\geq 3$ by AM-GM. Equality holds when $a=b=c$.

Stupid Mistake of mine. I don't know that after expanding We have a easy problem. Because at first I don't think the minimum is $3$.

How about this:

Find the minimum of:

$\frac{a+4c}{b+4c}+\frac{b+4a}{c+4a}+\frac{c+4b}{a+4b}$

At first when I creat it, I intend to find an easy express cyclic inequality, but

the equal is not hold if $a=b=c$. But I don't believe that if $k=2$, the equal

easy hold if $a=b=c$. Notice that if we can't guess the minimum is $3$ ,we can't

expand anything.

Sorry and try to help me if $k=4$ in the following:

$\frac{a+kc}{b+kc}+\frac{b+ka}{c+ka}+\frac{c+kb}{a+kb}$

[quote="Namdung"]
The ineq  2(a^3 + b^3 + c^3) + 3abc >= 3(ab^2+bc^2+ca^2)  (*)

can be proven as Vasc comment: put b = a + x and c = a+ y then

        LHS - RHS = 3a(x^2 - xy + y^2) + 2x^3 + 2y^3 - 3xy^2

My question about maximal k is still in force: Find the max k such that

                    (a^3 + b^3 + c^3) + kabc >= (1+k/3)(ab^2+bc^2+ca^2)
for all a, b, c >= 0.

In (*) k = 3/2, but I believe that it can be replaced by greater constant.

Also not that k = 3 not works. Just take a = 0, b = 2, c = 3.[/quote]
We have
$(LHS - RHS) = (2-k/3)(x^2 - xy + y^2) + x^3 + y^3 - (1+k/3)xy^2$.
By the AM-GM inequality, we get
$x^3+y^3/2+y^3/2 \geq \frac{3}{\sqrt[3]{4}}xy^2$. Thus, the best $k$ is $\frac{9}{\sqrt[3]{4}}-3$.

Yes. Thank you Vasc. Let think about Hung prb.

I think without calculus we are forceless, because max ~ 2.8836030805

Oh? Why? We haven't any condition of $a,b,c$?Do you calculate it when $a=b$?

[quote="hungkhtn"]$ a,b,c>0.$ Find the minimum of:

$ \frac {a \plus{} 2c}{b \plus{} 2c} \plus{} \frac {b \plus{} 2a}{c \plus{} 2a} \plus{} \frac {c \plus{} 2b}{a \plus{} 2b}$[/quote]

This inequality is [b]Problem 2.23[/b], page 70 of new book (where it is presented with a simple proof by Cauchy-Schwarz):

Vasile Cirtoaje, Vo Quoc Ba Can, Tran Quoc Anh, [url=http://canhang2007.wordpress.com/2009/12/08/new-book-inequalities-with-beautiful-solutions-v-cirtoaje-v-q-b-can-t-q-anh/][b][i]Inequalities with Beautiful Solutions[/i][/b][/url], GIL publishing house 2009.


search
linear algebra
matrix
induction
vector
linear algebra unsolved

what is the maximal dimension of a subspace of $M_n(K)$ such that any $2$ matrices of that space commute.

I posted this problem not too long ago
I can give you an answer: $[\frac{n^2}{4}]+1$.Also in that i post i mentioned i gave an example
I'll try to search it

I just can't believe this was the real problem. I asked a teacher in muy school who is a real genius and he told me the problem of finding the maximal dimension of a commutative subalgebra is extremely difficult. Alekk, are you generalizing again the problem? ;)

No. My friend really got this at the oral examination last week (the examinator was also the director of the departement of mathematic at ENS  :)  ). Anyway he told me that he received a lot of hints ... Nevertheless I do not know the proof since my friend forgot how he solved the pb  :(

in fact the field was $\mathbb{C}$ but I'm not sure it helps very much ..

That guy I was talking about was the first at ENS contest at his age and he said this problem is impossible to solve in one hour. And they give it at oral examination. I think the examinator was a little bit drunk.  :)

Of course as for me it is too difficult problem for an examination
I have a proof a bit less then a page in my book

i'm really beginner in linear algebar but if $K=\mathbb{C}$ i think such a idea maybe work.there exist $P$ which is invertible such that $PSP^{-1}$ for any $S\in subspace$ such that its form is some lowertriangular matrix with equal diagonal .it is obvious that $PSP^{-1}$  also commute. so we compute maximum independent matrix for one block.if our block is $m*m$ and $m=2k$.they should be $\begin{pmatrix}xI_k&0\\ *&xI_k\end{pmatrix}$and if $m=2k+1$ ,they should be like $\begin{pmatrix}xI_{k+1}&0\\ *&xI_k\end{pmatrix}$,so for this block we have $[\frac{m^2}{4}]+1$ and at last totaly we have $\sum [\frac{m_i^2}{4}]+k$and we have $n=\sum m_i$ so i think we are done any way excuse me if i'm totaly wrong :huh:

[quote="sam-n"]i'm really beginner in linear algebar but if $K=\mathbb{C}$ i think such a idea maybe work.there exist $P$ which is invertible such that $PSP^{-1}$ for any $S\in subspace$ such that its form is some lowertriangular matrix with equal diagonal [/quote]
Sam-n, could you please explain, why all  the matrices $PSP^{-1}$ have equal numbers on it's diagonal, i thought they should have it's eigenvalues on main diagonal

Maybe i don't understand what theorem you are using, but i t seemed to me that that you are using at first this one: if the set of matrices is commuting then we can find an invertible $P$ s.t. $PSP^{-1}$ are lowertriangular(uppertriangular) for all $S$ from our set of matrices
In this meaning i quite don't undertstand what kind of blocks $\begin{pmatrix}xI_k&0\\ *&xI_k\end{pmatrix}$ you are meaning (if you are meaning blocks obtained by equal eigenvalues on the diagonal, then as far as i undertsand it isn't necesseraly for them to commute with blocks from other matrices, our lowertriangular matrices are not block-form)
Sam-n,could you please clairify

[quote="harazi"]I would be very grateful to you, eugene, if you posted the solution. Thanks. I remember you posted the problem, but nobody made any headway. :([/quote]

We'll prove our result by induction on $n$.
Let's suppose our dimension $m \geq [\frac{n^2}{4}]+2$.
It is known fact that every set of commuting matrices have common eigenvalue, thus let it be $x$ for our set of matrices.Therefore all the mtarices in our set can be represented in form $A_j=\left( \begin{array}{cc} \lambda_j & * \\ 0 & B_j \end{array} \right) $. Since all the matrices $A_1,A_2,...,A_m$ commute the matrices $B_1,B_2,...B_m$ also commute. Let $\mathfrak{R}=<B_1,...,B_m>_\mathbb{C}$. By the induction hypothesis $r=dim \mathfrak{R} \leq [\frac{(n-1)^2}{4}]+1$. WLOG we can assume that matrices $B_1,B_2,...,B_r$ are linearly independent, thus $B_i= \sum_{j=1}^{r} \alpha_{ij}B_j$. For $i>r$ put $C_i=A_i-\sum_{j=1}^{r} \alpha_{ij}A_j$. It is evident that all the matrices $C_j$ are linearly independent and for $i=r+1,...,m$ they are of the form $C_i= \left( \begin{array}{c} c_i \\ 0 \end{array}  \right)$, where $c_i$ is $1 \times n$ matrix. Moreover, vectors $c_i$ must be linearly independent over $\mathbb{C}$.

Form now let's do almost the same from another point: Our uppertriangular commuting matrice we can also write in form $A_j=\left( \begin{array}{cc} B'_j & u_{1j} \\  & . \\ & . \\ & . \\ 0 & u_{nj} \end{array} \right)$ with commuting matrices $B'_j$. Using again induction hypothesis we can again get the set of $n \times 1$ linearly independent  matrices $c'_{s+1},...,c'_m$, where $s \leq [\frac{(n-1)^2}{4}]+1$. Now $C'_j= \left( \begin{array}{c} c'_j \\ 0 \end{array}  \right)$ for $s \geq s+1$. Since all the matrices $C_i$ and $C'_j$ belong to the same commuting set, $c_ic'_j=0$ for $i\r+1,...,m$ and $j=s+1,...,m$.

To this end, condsider $(m-r) \times n$ matrix $C$, which has as it's $i$'th row $c_i$, $i=r+1,...,m$. Since all the $c_i$ are linearly independent we have $rank A \geq m-r$. From the other side $Cc'_j=0$ for $j = s+1 ,...,m$. Since $c'_j$ are linearly independent and $dimKer\mathfrak{C}+dimIm\mathfrak{C}=n$ for linear operator $\mathfrak{C}$ with matrix $C$, taking into account ineaulities with $m,r,s$ we get
$n \geq (m-r)+(m-s) \geq 2 \left( [\frac{n^2}{4}]-[\frac{(n-1)^2}{4}]+1 \right) \geq 2[\frac{n}{2}]+2 \geq n$ - contradiction which proves our hypothesis.

I decompose matrix in lowertrianguar block simultenously and maximum nuber of independent matrix for block of $m*m$ which commute with each other is $[\frac{m^2}{4}]+1$ as i said so maximum in total is $\sum [\frac{m_i^2}{4}]+1$ which is lesser than$[\frac{n^2}{4}]+2$.


function
inequalities solved
inequalities

Prove that if x is in [0,pi/2] then we have x/sqrt(1+x^2)<=sin(x)<=x.

sin x -x is negative on [0,pi/2], you can study the function f(x)=sinx-x

for x/ \sqrt (1+x^2)   \leq  sinx take the square
x^2/(1+x^2)   \leq  (sinx)^2
<=>
1  \leq  (sinx)^2 + 1/(1+x^2)

minimum of RHS is x=0


[quote="DonkeyKong"]The sum of the 3 different unit fractions is 6/7. What is the sum of the denominator?

Answer?
[hide]
47[/hide][/quote]

Couldn't you just have $ \frac17\plus{}\frac27\plus{}\frac37\equal{}\frac67$?

The problem said unit fraction - 1 over some integer.

[quote="DonkeyKong"]The sum of the 3 different unit fractions is 6/7. What is the sum of the denominator?

Answer?
[hide]
47[/hide][/quote]

We have $ \frac1a \plus{} \frac1b \plus{} \frac1c \equal{} \frac67$. Assume, WLOG, that $ \frac1a\geq\frac1b\geq\frac1c$.

Then $ \frac1a\geq\frac {\frac1a \plus{} \frac1b \plus{} \frac1c}3 \equal{} \frac27$, and $ a\leq3 < \frac72$. However, $ a\geq2$ as well, since $ \frac1a < \frac67 < 1$.

If $ a \equal{} 2$, then $ \frac1b \plus{} \frac1c \equal{} \frac5{14}$, so, similar to above, we  have $ \frac1b\geq\frac5{28}\implies2\leq b\leq5$ (remember that $ \frac1a\geq\frac1b\geq\frac1c$!), and testing, we find that $ (a,b,c) \equal{} (2,3,42)$ is the only possibility for this case. Note that SFFT would have worked as well.

If $ a \equal{} 3$, then $ \frac1b \plus{} \frac1c \equal{} \frac {11}{21}$. Again, we have $ \frac1b\geq{11}{42}\implies3\leq b\leq3$. However, $ b \equal{} 3$ is not valid.

We conclude that the only solution is $ (a,b,c) \equal{} (2,3,42)$, which gives an answer of $ \boxed{47}$.

Edit: Thanks, mewto55555. :) You see, I was typing this at school today while helping emotionless1 in a countdown. :P

[quote="math154"][quote="DonkeyKong"]The sum of the 3 different unit fractions is 6/7. What is the sum of the denominator?

Answer?
[hide]
47[/hide][/quote]

We have $ \frac1a \plus{} \frac1b \plus{} \frac1c \equal{} \frac67$. Assume, WLOG, that $ a\geq b\geq c$.

Then $ \frac1a\geq\frac {\frac1a \plus{} \frac1b \plus{} \frac1c}3 \equal{} \frac27$, and $ a\leq3 < \frac72$. However, $ a\geq2$ as well, since $ \frac1a < \frac67 < 1$.

If $ a \equal{} 2$, then $ \frac1b \plus{} \frac1c \equal{} \frac5{14}$, so, similar to above, we  have $ \frac1b\geq\frac5{28}\implies2\leq b\leq5$ (remember that $ a\geq b\geq c$!), and testing, we find that $ (a,b,c) \equal{} (2,3,42)$ is the only possibility for this case. Note that SFFT would have worked as well.

If $ a \equal{} 3$, then $ \frac1b \plus{} \frac1c \equal{} \frac {11}{21}$. Again, we have $ \frac1b\geq{11}{42}\implies3\leq b\leq3$. However, $ b \equal{} 3$ is not valid.

We conclude that the only solution is $ (a,b,c) \equal{} (2,3,42)$, which gives an answer of $ \boxed{47}$.[/quote]

A slight problem there. You say that a>b>c yet your answer is a<b<c. This can be easily corrected by reversing the order of your letters.

[quote="math154Note that SFFT would have worked as well.

If $ a \equal{} 3$, then $ \frac1b \plus{} \frac1c \equal{} \frac {11}{21}$. Again, we have $ \frac1b\geq{11}{42}\implies3\leq b\leq3$. However, $ b \equal{} 3$ is not valid.

We conclude that the only solution is $ (a,b,c) \equal{} (2,3,42)$, which gives an answer of $ \boxed{47}$.

[/quote]

How would you have done it with SFFT?

Just multiply both sides by $ bc$, move all terms to one side, divide so the coefficient of the $ bc$ term is one, and then beast it. :wink:


calculate the minimum value of $x+\frac{1}{x^{2}}$ when $x>0$

this is probably a very simple problem...i'm actually really ashamed that i got stuck on it...but yea...i got stuck on it... :(

so can someone please help me...tank you!!!

Just AM-GM on $x/2$, $x/2$ and $1/x^{2}$.

Tank you...  :rotfl:

oooooohh...i see...that's soooo easy...haha...

tank you!!!! :rotfl:

It's also easy with calculus.  Call it f(x), take the derivative, set it equal to 0, and plug the value of x you get into the original function.  Then verify that it's a minimum with a second derivative test.

Julian are you taking calculus in school?

o...part of my math course covers calculus...but i sort of skip math...mentally...lol :P
school is finally over...hurray!!!
1 more provincials though... :|


algebra
polynomial
Galois Theory
superior algebra
superior algebra unsolved

Cezar i dont understand the problem,could you reformulate and give some examples if possible ?

well, the minimal polynomial of an algebraic number $\alpha$ over the field $K$ is the monic irreducible polynomial $\mu_\alpha \in K[x]$ such that $\mu_\alpha(\alpha)=0$.
for example, the minimal polynomial $\mu_{\sqrt2}$ of $\sqrt2$ over $\mathbb{Q}$ is trivially $\mu_{\sqrt2}(x) = x^2-2$, and so on...
by the way, the degree of the minimal polynomial equals the degree of the simple extension: $\partial \mu_\alpha = [K(\alpha): K]$.

[quote="ZetaX"]And when someone is really bored, he could take all the $6$ the conjugates $a_1,...,a_6$ of $\sqrt{2}+\sqrt[3]{3}$, the minimal polynomial is $(x-a_1)(x-a_2)...(x-a_6)$ then (the conjugates are $\pm \sqrt{2}+\zeta_3^{k}\sqrt[3]{3}$).[/quote]

I guess this is the only way out.

[quote="-oo-"]The result is $x^6 - 6 x^4 - 6 x^3 + 12 x^2 - 36 x + 1$. ;)

It is easy to see that the conjugates of $\sqrt{2} + \sqrt[3]{3}$ have the form $\pm \sqrt{2} + \zeta_3^k \sqrt[3]{3}$?[/quote]

Can you please write in detail your solution?  :?

He just did what I said above (at least I think so), so what is not clear¿
(that these are the conjugates can be seen by considering the extension of adjuncting $\sqrt{2}$ to $\mathbb{Q}[\sqrt[3]{3}]$ and converse; in total, we don't even need to prove it formaly since what we get has the desired degree and the desired coefficients ;) )

hm.. as far as i can see...
it's easy to see that $\alpha$ has to be a root of this polynomial. moreover, $\sqrt2 + \sqrt[3]{3}\in\mathbb{Q}(\sqrt2, \sqrt[3]{3})$, hence $[\mathbb{Q}(\sqrt2 + \sqrt[3]{3}): \mathbb{Q}]|[\mathbb{Q}(\sqrt2, \sqrt[3]{3}): \mathbb{Q}] = 6$. but trivially $\sqrt2 + \sqrt[3]{3}$ can't have a minimal polynomial of degree less then $4$ (you can see it by "brute force").

Ok, we can [i]verify[/i] that the result is correct. But how can one [i]see[/i] that the conjugates have the desired form? I don't know how to investigate the galois group here ...

@-oo-: how exactly is your question to understand¿ (I find it very "naturally" that the conjugates come from conjugating each summand for itself)

Just a proof that $-\sqrt{2}+\sqrt[3]{3}$ is a conjugate of $\sqrt{2}+\sqrt[3]{3}$ (the others are similar):
Over $\mathbb{Q}[\sqrt[3]{3}]$ we have the irreducible polynomial $x^2-2$ (to see irreducibility ony could just calculate through it to see that there is no root; a more convenient but more theoretic way would be to use Eisenstein). Thus adjuncting $\sqrt{2}$ is possible, giving us an automorphism that sends $\sqrt{2}$ onto $-\sqrt{2}$, but lets $\mathbb{Q}[\sqrt[3]{3}]$ fixed.


[quote="akimatsu"]if [i]p[/i] and [i]k[/i] are the roots of [i]x[/i] in the equation $x^2 + px + k$ and $p \ne k$ then find the values of [i]p[/i] and [i]k[/i].[/quote]
[hide]
$p+k=-p$
$pk=k$
$2p=-k$
$-2p^2=-2p$
$2p^2-2p=0$
$p_1=0$, $p_2=1$
But if $p=0$ then $k=0$ but $p\neq k$ so $\boxed{p=1}$, $\boxed{k=-2}$[/hide]


which do you think was better of the beijing olympics. write which one was better and why?

If I had to pick, I'd choose Opening Ceremony.  There was slightly more pizazz in it, and you actually wanted to see what would happen next.  In the Closing Ceremony, I was thinking like "finish it up", so there's my reason.  I feel bad for London though, they're gonna have to match these 2 spectacular ceremonies.

both ceremonies were really good because they both illustrated Chinese history and culture, as well as modern themes and stuff. but if i had to choose i guess opening ceremony, since it had better effects and the theme was much clearer. plus london kinda had a not-as-good show in the closing ceremony compared to china, so it kind of effected the ending too.


Prove that a square matrix of $n\times n$ where $n=p\cdot q$ can be written as a sum of $p$ matrixes of rank $q$. Prove that $I_n$ cannot be written as a sum of less than $p$ matrixes of rank $q$.

This seems to be a generalisation for a problem from the district round a couple of year ago.

For the second part:
  $rank(A_1+A_2+...+A_t) \leq rank(A_1)+rank(A_2)+...+rank(A_t)$ which means that $p\leq t$ contradiction beacause $t<p$.

For the first part : Suppos $rank(A)=r$ then there exist $Q,D$ such that $A=QI_rD$ where $I_r=diag(1,1,...,1,0,0,...,0)$ where there are $r$ ones. All we have to do is to write $I_r$ as the sum of $p$ matrixes of rank $q$ wich is posiblle because we can take matrixes that have the rank $q$ and sum up to $0$ when $n$ is odd and when $n$ is even we just have to write $I_r$ as the sum of $2$ matrixes of rank $q$ which is easily done.


$x(x+1)(x+7)(x+8)=y^2$ solve for  x,y integers..

I just want to check myself so please don't write solution just answers!!!

THANKS  JIMBO!!!

Maybe this would be helpfull...
Let $t=x+4$...

This problem is form TST for imo (Lower grades).

By inspection : x={0,-1,-7,-8} and y=0.

Set as said above $x=t-4$ then we want to solve:
$(t^2-3^2)(t^2-4^2)=y^2$
Now $\gcd(t^2-9 , t^2-16)= 1,7$,thus:

1. Case $\gcd(t^2-9 , t^2-16)= 1$:
Then $t^2-9=u^2$ and $t^2-16=v^2$ have to be perfect squares (theoretically, they could be negatives of perfect squares, but it's easy to see that this doesn't happen), giving $u^2-v^2=7$, thus $(u,v)=(\pm 4,\pm 3)$ and $t=\pm 5$.

1. Case $\gcd(t^2-9 , t^2-16)= 7$:
Then $t^2-9=\pm 7u^2$, $t^2-16=\pm 7v^2$ are seven times a perfect square (up to sign, but both signs equal), and again we get something: $u^2 - v^2=\pm 1$, thus $(u,v)= (\pm 1,0), (0,\pm 1)$, giving $t=\pm 4 , \pm 3$.

This are all solutions:
$(x,y)= (-4 \pm 3 , 0) , (-4 \pm 4 , 0) , (-4 \pm 5 , 12)$

THANKS EVERY BODY YOU HELPED ME!!!!!!!!!!! :)


graph theory
combinatorics proposed
combinatorics

On the edges of a regular 2003-gon bricks with a red and a blue side are placed.
The following operation is permitted:
[i]If two adjacent edes have the same color facing upwards on their bricks, one can
switch their colors so the other color is facing up.[/i]
Show that independent of the initial distriution of colors, one can always, using the mentioned
operation, flip side of all of the brick such that they all have the same color facing upwards.

Consider the coloring as a series of "blocks," where each block is a maximal set of consecutive edges, all colored the same.  Suppose there is more than one block (i.e., the task is not already complete). I claim that there is always a block of even length: otherwise, we would have all odd-length blocks.  Since there are 2003 edges, there would be an odd number of blocks.  But this is not possible, because the blocks form a bipartite graph (they are two-colored, and each block of color red borders only blocks of color blue and vice versa).  So, take our block of even length and switch all of its edges to the opposite color.  We thereby reduce the number of blocks, and go back to the beginning.  This process can only terminate when we reach a monochromatic coloring.

Clearly 2003 could be replaced with any odd number.


conics
ellipse
analytic geometry
graphing lines
slope
trigonometry
vector

Help required :-

Q1. The number of normals that can be drawn from an external   point to the curve $4x^2 + 9y^2 = 36$

  (a) 1                                                  (b) 3
  (c) 4                                                   (d) infinite

Q2. The number of distinct  normal lines from an exterior point  $(0,c)$, $c > b$ to the ellipse ${\frac{x^2}{a^2}} + {\frac{y^2}{b^2}} = 1$ is

  (a) 3                                                  (b) 4
  (c) 2                                                   (d) 1

I am getting (c) for both problems.

[quote="Fermat2"]Q1) If by external point, the question means a particular point, then there is only one line that can be drawn through that point which will be normal to the ellipse.
If, however, the questions means [i]any[/i] point, then there is an inifinite number of such points and hence an inifinite number of normals.
I suspect the answer should be (d)

Q2) This ellipse is centred on the origin. The point (0,c) is a point on the y-axis somewhere above the top curve of the ellipse. The only line that can be drawn through this point [i]and[/i] normal to the ellipse is the y-axis itself. So the answer is (d), again.[/quote]

I did the following :-
The given equation is of the form $\frac{x^2}{a^2} {+} \frac{y^2}{b^2} =1$
Then when you find the equation to a normal with slope $(m)$
the equation wold be ${y} {=} {mx} {+} {\frac{(b^2 - a^2)m}{\sqrt{a^2 + {b^2}{m^2}}}}$i.e, in general four normals can be drawn from an external point.
When the point is $(0,c)$ the equation reduces to ${{c^2}(a^2 +{b^2}{m^2})} {=} {{m^2}(b^2 - a^2)^2}$
so we can have two values of m. Hence 2 such normals.
Point out the mistake if i have done.
Bye. :lol:

The direction of a normal to the curve (ellipse in this case) $F(x, y) = \frac{x^2}{a^2} + \frac{y^2}{b^2} - 1 = 0$ is $\text{grad} F = (\frac{\partial F}{\partial x},\ \frac{\partial F}{\partial y}) = (\frac{2x}{a^2},\ \frac{2y}{b^2})$. This gradient cannot be zero on the ellipse, because if the x-component is zero, $\frac{2x}{a^2} = 0,\ x = 0$, then from the ellipse equation $\frac{y^2}{b^2} = 1,\ y = \pm b,\ \frac{2y}{b^2} = \pm \frac{2}{b} \neq 0$, the y-component is non-zero, and the other way around. Since $\text{grad} F = (0,\ \frac{2}{b})$ is an external normal at ellipse point (x, y) = (0, b), $\text{grad} F$ is an external normal at any ellipse point (x, y). Let P = (p, q) be an arbitrary point not on the ellipse main axes, i.e., $p \neq 0, q \neq 0$, and let U = (u, v) be the intersection of the normal to the ellipse from P with the ellipse. Since U is on the ellipse, $\frac{u^2}{a^2} + \frac{v^2}{b^2} = 1$. Since $p \neq 0$, the ellipse normals at (0, b) and (0, -b) do not pass through the point P, hence $u \neq 0$. Likewise, since $q \neq 0$, the ellipse normals at (a, 0) and (-a, -) do not pass through the point P, hence $v \neq 0$. The equation of the ellipse normal at U = (u, v) is then $y - v = m (x - u)$ where the slope $m = \frac{\partial F}{\partial y} : \frac{\partial F}{\partial x}|_{(x,y) = (u,v)} = \frac{a^2v}{b^2u}$. If this line passes through the point P = (p, q), then $q - v = \frac{a^2v}{b^2u} (p - u)$. Together with $\frac{u^2}{a^2} + \frac{v^2}{b^2} = 1$, this yields 2 equations for (u, v). For example, rearranging and squaring the 1st equation and then substituting the 2nd equation leads to a quartic equation for v:

$\frac{avp}{b^2q + (a^2 - b^2) v} = \frac{u}{a},\ \ (\frac{avp}{b^2q + (a^2 - b^2) v})^2 = \frac{u^2}{a^2} = 1 - \frac{v^2}{b^2}$

This indicates that up to 4 distinct normal lines to the ellipse from the point P may exist.

We can parametrize the ellipse equation as $x = a \cos t,\ y = b \sin t,\ t \in (0, 2\pi)$. The gradient is then $\text{grad} F = ( \frac{2 \cos t}{a},\ \frac{2 \sin t}{b})$ and $|\text{grad} F| = \frac{2}{ab} \sqrt{b^2 \cos^2 t + a^2 \sin^2 t}$, so that the exterior unit normal to the ellipse is $\vec n = \frac{1}{\sqrt{b^2 \cos^2 t + a^2 \sin^2 t}} (b \cos t,\ a \sin t)$. The ellipe curvature $\kappa$ is given by

$\kappa = \frac{|x''y' - y''x'|}{(x'^2 + y'^2)^{3/2}} = \frac{|(-a \cos t)(-b \cos t) - (-b \sin t)(-a \sin t)}{(a^2 \sin^2 t + b^2 \cos^2 t)^{3/2}} = \frac{ab}{(a^2 \sin^2 t + b^2 \cos^2 t)^{3/2}}$

The normal line to an ellipse tangent from the tangency point passes through the center of a circle with radius $R = \frac{1}{\kappa}$ tangent to the ellipse. If an ellipse point has the radius vector $\vec r = (x, y) = (a \cos t, b \sin t)$, the center C of this circle has the radius vector $\vec r_C = \vec r - R \vec n$,

$x_C = a \cos t - \frac{(a^2 \sin^2 t + b^2 \cos^2 t)^{3/2}}{ab} \cdot \frac{b \cos t}{\sqrt{b^2 \cos^2 t + a^2 \sin^2 t}} =$

$= \frac{\cos t}{a}\ [a^2(1 - \sin^2 t) - b^2 \cos^2 t] = \frac{a^2 - b^2}{a}\ \cos^3 t$

and similarly,

$y_C = \frac{a^2 - b^2}{b}\ \sin^3 t$

The locus of the centers of these circles is the envelope of the normals to the ellipse tangents at the tangency points (the ellipse evolute). Elliminating the parameter t from the parametric equations of the evolute and skipping the subscripts C from $x_C, y_C$, we get its equation as

$(ax)^{2/3} + (by)^{2/3} = (a^2 - b^2)^{2/3} (\cos^2 t + \sin^2 t) = (a^2 - b^2)^{2/3}$

This is an astroid with the main axes $\frac{|a^2 - b^2|}{a},\ \frac{|a^2 - b^2|}{b}$ (kind of astroid, usually, astroid is supposed to have equal main axes). Assume again, that the arbitrary point P does not lie on the ellipse main axes. If the point P lies inside the ellipse evolute, 4 distinct normal lines from P to the ellipse exist, if the point P lies on the ellipse evolute, 3 distinct normal lines from P to the ellipse exist, and if the point P lies outside the ellipse evolute, 2 distinct normal lines from P to the ellipse exist. If the point P lies on one of the ellipse main axes, 2 of the normal lines become identical.

Applying these result to the question (Q1), the ellipse semimajor and semiminor axes are a = 3, b = 2. The evolute has 2 vertices on the x-axis at $(\frac{a^2 - b^2}{a},\ 0)$ and $(-\frac{a^2 - b^2}{a},\ 0)$ or $(\frac 5 3,\ 0)$ and $(-\frac 5 3,\ 0)$. These 2 vertices lie in the ellipse interior. On the other hand, the evolute has 2 vertices on the y-axis at $(0,\ \frac{a^2 - b^2}{b})$ and $(0,\ -\frac{a^2 - b^2}{b})$ or $(\frac 5 2,\ 0)$ and $(-\frac 5 2,\ 0)$. These 2 vertices lie in the ellipse exterior and so does a part of the evolute. Consequently, exterior points of the ellipse exist, which lie inside the evolute, i.e., with 4 distinct normal lines to the ellipse. Obviously, exterior points of the ellipse exist, which lie on or outside the evolute, i.e. with 3 or 2 distinct normal lines to the ellipse. Without an additional info about the exterior point P, it is not possible to say, whether the answer (c) is correct or whether the correct answer is not on the list. Therefore, the problem is wrong. Ditto the question (Q2). Without an additional info about the ellipse main axes a, b, it is not possible to decide, whether the evolute lies completely inside the ellipse or whether some part of it sticks out. But if it sticks out along the y-axis, i.e., if $\frac{a^2 - b^2}{b} > b,\ a^2 > 2b^2,\ a > b \sqrt 2$, then either 1 or 3 distinct normal lines to the ellipse from an exterior point on the y-axis may exist and again, it is not possible to choose among the answers (a), (d). Therefore, the problem is also wrong.


Find all primes of the form 4k+1.
(I think there are finitly many numbers of this form.)

There are $\infty$ many ;)
Proof:
The equation $x^2 \equiv -1 \mod p$ cannot have solutions for primes $p \equiv 3 \mod 4$ since that would give (using that $p-1=4k+2$) us $1 \equiv x^{p-1} = x^{4k+2} = (x^4)^k \cdot x^2 \equiv -1 \mod p$.
Now assume there are only finetely many $\equiv 1\mod 4$, then let their product be $P$.
Now look at $n=(2P)^2+1$:
It is odd, and coprime to all primes $\equiv 1 \mod 4$ contained in $P$. But any prime $q$ dividing $n$ gives $(2P)^2 \equiv -1 \mod q$, thus (remember $q \not\equiv 0,2 \mod 4$) $q \equiv 1\mod 4$, which is clearly not possible, contradiction.


superior algebra
superior algebra unsolved

Let $ F$ be a field with characteristic $ p$ and $ E$ a finite extension of $ F$. Prove that there is a non-negative integer $ n$ such that $ [E: F]\equal{}p^n[E: F]_s$.

Consider the maximal separable intermediate extension.


In a convex pentagon $ABCDE$, $\angle ABC = \angle AED = 90 ^\circ$. Let $F$ be the midpoint of $CD$. If $FB=FE$, prove that $\angle BAC = \angle DAE$.

Let $M$ and $N$ be the midpoints of $DA$ and $CA$. Then:
$MF=\frac12 AC=NB$ and $NF=\frac12 DA=EM$ (because triangles $EAD$ and $ABC$ are rightangled and $DA$ and $AC$ are hypotenuses). $FE=FB$ from the text so $\triangle EMF \cong \triangle FNB$.

Now problem is done, because $\angle EAD=\frac12 \angle EMD=\frac12(\angle EMF-\angle DAC)=\frac12(\angle FNB-\angle DAC)=\frac12 \angle CNB=\angle BAC$.

bye


Let's say we are chatting computers. We all input something, and a computer outputs something. Please put it in some sort of computer code, or typeset. Once the game has gotten a few pages, we may be able to put in phrases. I'll make that rule starting in the 21st post in this topic. This is almost a conversation.

input: prompt x,y,z

ALMOST. You can input calculator program threads, phrases, but only things you can type. Like this:

output:
x=?
y=?
z=?

inupt: (1,2,3)

sometimes it can be funny.

input: $x\star y = \frac{(\frac{97332}{5x})^{y}\times \frac{x-y}{y-x}}{xy}\times \sqrt{x}$
$value= OPERATION(find): \infty^{E}\star\sqrt{\pi}$

output: error 1
input: $(a,b,c,d,e,...,x,y,z)$

output: error, omega does not compute

input: 4 store omega

Output: A can of coca cola

Input: 2 dollars

output: Thank you for the moolah. Now I have enough money to buy a computer.
input: Output 2 dollars


calculus
integration
function
limit
inequalities
real analysis
real analysis unsolved

Find all continuous functions $f : \mathbb R \to \mathbb R$ such that:
(a) $\lim_{x \to \infty}f(x)$ exists;
(b) $f(x) = \int_{x+1}^{x+2}f(t) \, dt$, for all $x \in \mathbb R$.

Let $\lim_{x\to \infty}f(x) = L$. Then for every $\epsilon>0$, there exists $C$ such that $|f(x)-L|<\epsilon$ whenever $x>C$.

Now let $x>C$ and $I_{k}=(x-k, \infty)$. Then $L-\epsilon < f < L+\epsilon$ on $I_{0}$, so integrating both side of (1) on $I_{0}$ gives

$L-\epsilon < f(x-1) < L+\epsilon$

or

$L-\epsilon < f(x) < L+\epsilon$ on $I_{1}$

If we recursively repeat this process, then for any $r \in \mathbb{R}$, we have $L-\epsilon < f(r) < L+\epsilon$. But this inequality holds for arbitrary $\epsilon>0$, we conclude that $f(r) = L$. Therefore, $f$ is a constant function.

-o- but I can't sure my proof is right...

It's right. I would probably use $\le\epsilon$ rather that $<\epsilon$, just to avoid having to justify strict inequalities after integration.

[quote="sos440"]$I_{k}=(x-k, \infty)$
...
Then $L-\epsilon < f < L+\epsilon$ on $I_{0}$, so integrating both side of (1) on $I_{0}$ gives

$L-\epsilon < f(x-1) < L+\epsilon$
[/quote]
Unless I'm misunderstanding, don't you mean $I_{k}=(x-k, x-k+1)$?

[quote=ciprian]Or we can start with an $x_{0}$ and construct an increasing to infinity sequence $x_{n}$ that is constant (we use Lagrange for example). Taking the limit of $f(x_{n})$ it is L=$\lim_{x\to\infty}f(x)$ but also $x_{0}$ so the problem is solved. A quick computation shows that all constant functions verify the hyphotesis .[/quote]

Could you provide full solution


calculus geometry derivative integration

Question:
Are there any books that anyone would recommend for someone just starting out in physics? (aka knows about nothing at all) I am looking to participate in physics competitions sometime in the future, but as of right now, I know next to nothing about physics.

Thanks!

What is your level of math?  Whether or not you know calculus will impact what books I recommend.

Uh...I know most everything before calculus (Algebra I and II, Geometry, Precalculus) and a little bit of calculus (basic limits, some derivatives)
I will be takin calculus next year.

If you're not already comfortable with calculus (by which I mean that taking derivatives, limits, and integrals is the easy part), then I will recommend a book by Giancoli.  He has another one which uses calculus so try to avoid that one.  I used this book to self-study and I really liked it.  There are good explanations and lot's of good problems.


Suppose the operation # is defined on the set of real numbers as $a\#b=a+ab$. What is the identity for this operation?

[quote="4everwise"]Suppose the operation # is defined on the set of real numbers as $a$#$b=a+ab$. What is the identity for this operation?[/quote] There isn't one.

Suppose an identity $e$ for $a$#$b$ exists.

Then by definition of an identity element, $e$#$a = e +ea = a$ and likewise $a$#$e = a + ae = a$.

$e$#$a = a \Rightarrow e =\frac{a}{1+a}$

$a$#$e = a \Rightarrow ae = 0$

If $a \neq 0$ then $ e = 0 \;\&\; e \neq 0$ ; this follows from the supposition and therefore the supposition is false.


Two circles touch each other externally at $ A$ and touch a common tangent at $ B$ and $ C$ $ (B \not\equal{} C)$. Let $ D$ and $ E$ be the points such that $ BD$ and $ CE$ are diameters of the circles. Prove that points $ D,A,C$ are collinear.

Construct a common tangent $ l$ which passes through $ A, l\cap BC\equal{}\{M\}$
$ \Rightarrow MB\equal{}MC\equal{}MA \Rightarrow \angle BAC\equal{}90^o \rightarrow$ QED


algorithm
Gauss
linear algebra
matrix
parameterization

I was thinking of writing a program to balance chemical equations for me, and since that involves converting the equation into a system of linear equations and then solving that, I was wondering how I should go about doing that?  I don't know how to use Gaussian Elimination with matrices containing zero elements, so that seems out.

Edit:  Ok, scratch that, Gaussian Elimination does work with matrices with zero elements, but the number of linear equations have to be at least equal to the number of variables (i.e. the number of elements in the equation has to be at least equal to the number of chemicals, which often doesn't happen in chemical equations).

[quote="probability1.01"]I would suggest setting one variable to 1, then figuring out all the other variables, then multiplying through to clear denominators. Of course you will need to make a rational class or something silly like that.[/quote]
Yeah, but doesn't Gaussian elimination require the same number of equations as variables?  Every iteration you set one column to zero, so after (n-1) iterations you have 1 last variable = 1 constant, and then work backwards from that.

In a balancing equations problem, you will have more variables than equations.

eghm, when gauss-reducing, the program must be aware of the pivots chosen iteration by iteration, otherwise errors can be greatly amplyfied, or "divide by 0" problem can arise.
having more variables than equations is not that big problem, there will be a set of solutions instead of a unique solution, anyway, by gaussian elimination in the later case you obtain a upper hessenberg matrix, in this form, once chosen the variables to be free parameters of the system, just solve via back-substitution as always.
I would suggest to divide logically the program in two parts, first gaussian elimination, than once chosen the values of the free parameters, solve by backsubstitution.
Another way may be chosing the free parameters in the beginning, and then use an iterative method for solving the system...


geometry
trigonometry
LaTeX
analytic geometry
angle bisector
area of a triangle
Pythagorean Theorem

ABC is a triangle with angle B=90.
AD is an angle bisector.
E lies on the side AB with AE=3 and BE=9 and F lies on AC with AF=10 and FC=27.
EF meets AD at G.
Find the nearest integer to area GDCF.

thank you.......

This would be an easy question if calculators were allowed. Somehow, because of the "find the nearest integer" I don't think they are.

Are they allowed?

NO .....CALCULATOR IS NOT ALLOWED
WE R ASKED TO GIVE A SOLUTION..... :)

[hide="obvious hint"]use the angle bisector theorem[/hide]
[hide="helpful hint "]
Use the fact that the area of a triangle is $ \frac{1}{2}ab\sin{C}$[/hide][/hide]

you could divide. And you should learn $ LaTeX$... there's a great guide on this site (look at the left taskbar).

Coordinates would be interesting here :ninja:

I've used latex, just I was too lazy to use it for those geometric things lol


Replace x by 3x and expand we have to prove
$23x^2y^2z^2+5\sum x^2y^2 + 3\sum x^2 +1 \ge 8\sum x^2yz + 8\sum x^2y^2z$
It can be resolved into three inequalities
1. $\sum x^2y^2 + 2x^2y^2z^2 + 1 \ge 2\sum x^2yz$ (APMO 04 no.5)
2. $\sum x^2 + 3x^2y^2z^2 \ge 2\sum x^2yz$ (amgm)
3. $\sum x^2y^2 + 3x^2y^2z^2 \ge 2\sum x^2y^2z$ (amgm)
(1)+3*(2)+4*(3)
Then it's done.

Really nice , Siuhochung !
 You used $ \sum x^2y^2 + 2x^2y^2z^2 + 1 \ge 2\sum x^2yz $ in my 2 posts  :lol:
  The problem has a nicer solution

then can you post your solution? When I meet this type of problem I always expand, expand and expand.  :D  :P

Change the problem into : $ (a^2+3)(b^2+3)(c^2+3) \geq 4(a+b+c+1)^2 $ , where $ a=\frac{3}{x} $ . The problem becomes smarter  ;)


Prove that-

1+(1/2)+(1/3).....1/n is not an integer(too lazy to type latex :D )

hint :
[hide]
I'm too lazy to answer in details. ;)

By induction, prove it is odd/even

No doubt it was answered previously on Mathlinks before[/hide]

[hide]Let $a$ be the largest integer such that $2^a\leq n$. Since $2*2^a=2^{a+1}>n$, there is exactly 1 integer from 1 to n divisible by $2^a$.

When writing $\sum_{k=1}^n \frac{1}{k}$ under a common denominator, the numerator of the term when $k=2^a$ is odd, but for all other $k$ it will be even. The sum is then
(odd number)/(multiple of $2^a$).

If $n>1$, then $a\in \mathbb{N}$, so the denominator is not 1. Then the sum cannot be an integer.[/hide]

[hide]euler showed that the harmonic series is bounded and convergent to $\frac{\pi^2}{6} \approx 1.645$, so the only integer it can be is $1$, (which occurs), and besides that, it goes in the range $(1,1.645)$, so it is never an integer

(i am sure that you are not counting $n=1$)[/hide]

woops...i was thinking $\sum_{k=1}^{\infty} \frac{1}{k^2}$


E and F are variable points on the sides AD and CD, respectively, of square ABCD such that DE=CF. BE and BF divide AC into three segments AG, GH, and HC which, as it turns out, can always be arranged to form a triangle. Prove that every such triangle has an angle of 60 degrees.

$AGE$ is similar with $CGB$ and
$\frac{y}{x+y}=\frac{a}{b+c}$
$FHC$ is similar with $BHA$ and
$\frac{x}{x+y}=\frac{c}{a+b}$
$\frac{y}{x+y}+\frac{x}{x+y}=\frac{c}{a+b}+\frac{a}{b+c}$
$1=\frac{c}{a+b}+\frac{a}{b+c}$
$a^2+c^2-ac=b^2$
$a^2+c^2-2ac*cos60=b^2$

triangles with a,b,c has one 60 degrees at last.

I have one question: We've already know that the length of the three segments satisfy the equation, but do we have to prove that they can form a triangle togather before we say one angle is $60^o$?

no, the problem says that the segments can form a triangle

btw gunes nice job


Let $ a,b,c,x,y,z\geq 0$. Prove that

$ x(b\plus{}c)\plus{}y(c\plus{}a)\plus{}z(a\plus{}b)\geq 2\sqrt{(xy\plus{}yz\plus{}zx)(ab\plus{}bc\plus{}ca)}$

[quote="easternlatincup"]Let $ a,b,c,x,y,z\geq 0$. Prove that

$ x(b \plus{} c) \plus{} y(c \plus{} a) \plus{} z(a \plus{} b)\geq 2\sqrt {(xy \plus{} yz \plus{} zx)(ab \plus{} bc \plus{} ca)}$[/quote]
See here:
http://www.artofproblemsolving.com/Forum/viewtopic.php?t=186636


Each morning Boris walks to school. At one-fourth of the way he passes the machine and tractor station; at one-third of the way, the railroad station. At the machine and tractor station its clock shows 7:30, and at the railroad station its clock shows 7:35.
When does Boris leave his house, when does he reach school ?

[i]from book "The Moscow puzzles" by Boris A. Kordemsky[/i]
[u]Please hide Your solution . Write inside Hide ... /Hide[/u]

[hide="Solution"]

In $ 5$ minutes, Boris walks $ \frac{1}{12}$ of the way, so the whole journey to school takes $ 60$ minutes. $ \frac{1}{4}$ of the way takes $ 15$ minutes, so he left home at $ 7: 15$ and reaches school at $ 8: 15$.

[/hide]

[hide]Time Left Home: 7:15[/hide]

[hide]Time Arrive: 8:15[/hide]