combinatorics
imo 2000
invariant
algorithm
IMO
IMO Shortlist

Let $ n \geq 2$ be a positive integer and $ \lambda$ a positive real number. Initially there are $ n$ fleas on a horizontal line, not all at the same point. We define a move as choosing two fleas at some points $ A$ and $ B$, with $ A$ to the left of $ B$, and letting the flea from $ A$ jump over the flea from $ B$ to the point $ C$ so that $ \frac {BC}{AB} \equal{} \lambda$.

Determine all values of $ \lambda$ such that, for any point $ M$ on the line and for any initial position of the $ n$ fleas, there exists a sequence of moves that will take them all to the position right of $ M$.

For $\lambda\ge1/(n-1)$ just repeatedly jump the leftmost flea over the rightmost flea.

Now assume that $\lambda<1/(n-1)$. Let the positions after the $k^{th}$ jump be $x_1<x_2<\cdots<x_n$. If $x_i<x_j$, then jumping is equivalent to
\[(x_i,x_j)\mapsto (x_j,x_j+\lambda(x_j-x_i)).\]Letting $M_k,s_k$ denote the maximum and sum (respectively) of the positions after $k$ jumps, we see that
\[M_{k+1}-M_k \le x_j+\lambda(x_j-x_i)-x_n \le \lambda(x_j-x_i)\]while
\[s_{k+1}-s_k = x_j+x_j+\lambda(x_j-x_i)-x_i-x_j = (1+\lambda)(x_j-x_i),\]whence summing up yields
\[\frac{M_l-M_0}{s_l-s_0} \le \frac{\lambda}{1+\lambda} = c < \frac{1}{n}\]for all $l\ge1$. Then
\[M_l-M_0 \le c(s_l-s_0) \le c(nM_l-s_0)\implies M_l \le \frac{M_0-cs_0}{1-cn}.\]

Assume $ \lambda < \frac{1}{n-1} $. Then for a position of the fleas $ f=(f_1,...,f_n) $ with $ f_1 \ge ... \ge f_n $, define

$ M(f) = f_1 + \left( \frac{\lambda}{1-(n-1)\lambda} \right) \cdot \left( \sum_{k=2}^n (f_1-f_k) \right) $.

Clearly if $ f_n > M $ then $ M(f) \ge f_1 > M $. Thus, if the fleas were able to jump to infinity, then $ M \rightarrow \infty $. However, $ M $ is a monovariant! (It never increases). Indeed, if $ f_1 $ doesn't change then $ M $ decreases strictly, and if $ f_1 $ changes, $ M $ is easily computed to stay the same.

Thus, we're done.

If $ \lambda \ge \frac{1}{n-1} $, then by making the last one jump over the first one, we compute that the average distance between consecutive fleas never decreases, and $ f_n$ always increases, thus the fleas jump to infinity.

Hello! I was wondering if the following solution is correct? Here we replace lambda with c:

After each step k, denote x(k)(1), x(k)(2), ..., x(k)(n) in increasing orders to be the positions of the fleas. Hence x(n)(k) is the maximum position. Note that the optimal way to increase the maximum position is by jumping the leftmost fly over the rightmost fly.
Now, denote P(k) to be the maximum value of the positions after k steps (essentially the same as x(n)(k)). Note that P(k+1) - P(k) = c(x(n)(k) - x(n)(0)). After some algebra we get that c[(x(n)(k) - x(n)(1))] = [x(0)(n) - x(0)(1)][(n-1)(c)]^k, where x(0)(i) denotes the initial positions. Finally, let d = c(n-1). By collapsing the sum, we get that P(k) = (d^(k-1)+d^(k-2)+...+1)[x(0)(n) - x(0)(1)] = [(d^k - 1)/(d - 1)] * [x(0)(n) - x(0)(1)]. Note that [x(0)(n) - x(0)(1)] is constant, and we want that P(k) is unbounded as k approaches infinity. For all c < 1/(n-1), we see that P(k) is bounded above as k approaches infinity by 1/(1-d) * [x(0)(n) - x(0)(1)], and for c >= 1/(n-1) P(k) is unbounded, so we can move the fleas! Hence the desired answer is all c (lambda) >= 1/(n-1).

Thanks!  :-D

Write $n = N+1$; we claim the answer is \[
\boxed{\left\{\lambda\colon \lambda \geq \frac 1N\right\}}.
\]Place the points on the number line; let $p$ denote the coordinate of point $P$. For a configuration $x_1\leq x_2\leq \cdots \leq x_{N+1}$ of points $X_1,X_2,\ldots, X_{N+1}$, define its cap by $x_{N+1}$ and its score by $X_1X_{N+1} + X_2X_{N+1} + \cdots + X_NX_{N+1}$. Notice now that we can get all the points past $M$ if and only if we can get the cap to exceed $m$; only if clearly holds, and for if just notice that if $X_{N+1}$ is past $M$, we just reflect everything over $X_{N+1}$ and win. So, we just want to find $\lambda$ so that the cap can get arbitrarily large.

Lemma 1: $\lambda \geq \frac 1N$ all work.

Proof: First, note that we can get a configuration in which no two fleas are at the same point. To do this, first take the leftmost point and reflect over the rightmost point. Then, we have a point strictly to the right of all other points. Suppose the points are $P_1,P_2,\ldots, P_{N+1}$, respectively. Then, at each point, reflect the leftmost point over the rightmost one $N$ times, until we have $N+1$ points all at distinct places.

Suppose our current configuration is $X_1,X_2,\ldots, X_{N+1}$, and let $d_1 = X_1X_2$, $d_2 = X_2X_3, \ldots$, and write $d = \min(d_i)>0$. Reflect $X_1$ over $X_{N+1}$. Then, the configuration becomes $X_2,X_3,\ldots, X_{N+1}, X_1'$, and the pairwise distances become $d_2,d_3,\ldots, d_N, \lambda(d_1+d_2+\cdots+d_N)$, which are again all $\geq d$. So, at each step, we know that the cap has coordinate increasing by at least $d$ every time, so we can get the cap to be arbitrarily large. $\Box$

Lemma 2: $\lambda < \frac 1N$ all fail.

Proof: Define the value $V$ of a configuration to be \[
V = C + \frac{\lambda S}{1-N\lambda},
\]where $C$ is the cap and $S$ is the score, respectively. We claim that the value is nonincreasing. Indeed, suppose we have a configuration $X_1,X_2,\ldots, X_{N+1}$, where $x_1\leq x_2\leq \cdots \leq x_{N+1}$. Suppose we reflect $X_i$ over $X_j$ with $i<j$. Write $\alpha = X_iX_j$, and $\beta =X_jX_{N+1}$. If the cap does not change, then clearly the score decreases, since $X_i$ moves closer to $X_{N+1}$ and the other distances do not change. Otherwise, we see that the cap increases by $\lambda \alpha - \beta$.

Furthermore, since we went from $X_1,X_2,\ldots, X_{N+1}$ to $X_1,X_2,\ldots, X_{i-1},X_{i+1},\ldots, X_{N+1},Q$, where $Q$ is where $X_i$ jumped to, then the score changes from \[
\sum_{k=1}^N x_{N+1}-x_k = Nx_{N+1} - \sum_{k=1}^N x_k
\]to \[
\sum_{\substack{k=1\\ k\neq i}}^{N+1}q - x_k = Nq - \sum_{\substack{k=1\\k\neq i}}^{N+1} x_k,
\]so we compute that $\Delta S = N(q-x_{N+1}) - x_{N+1}+x_i = N(\lambda\alpha-\beta) - (\alpha+\beta)$. So, \[
\Delta V = \Delta C + \frac{\lambda \Delta S}{1-N\lambda} = (\lambda\alpha-\beta) + \frac{\lambda (N(\lambda\alpha-\beta)-\alpha-\beta)}{1-N\lambda} \leq \lambda\alpha + \frac{\lambda(N\lambda-1)\alpha}{1-N\lambda} = 0.
\]So, $V$ is indeed nonincreasing. So, if $V_0$ is the initial value, since $S\geq 0$ always we have that \[
C\leq V \leq V_0
\]implying that $m = V_0$ indeed works, and that we cannot move all the fleas to the right of $M$. $\Box$

Thus, with both lemmas proven, we may conclude.

The answer is $\lambda \ge \frac{1}{n-1}$.

We change the problem be replacing the fleas by [b]bowling balls[/b] $B_1$, $B_2$, \dots, $B_n$ in that order. Bowling balls aren't exactly great at jumping, so the operation now works as follows. [list] [*]Choose any indices $i < j$. [*]Then ball $B_i$ moves to $B_{i+1}$'s location, $B_{i+1}$ moves to $B_{i+2}$'s location, and so on; until $B_{j-1}$ moves to $B_j$'s location, [*]Finally, $B_j$ moves some distance at most $\lambda \cdot |B_j B_i|$ forward, but it may not pass $B_{j+1}$. [/list]

[b][color=red]Claim:[/color][/b]  	If $\lambda < \frac{1}{n-1}$ 	the bowling balls have bounded movement.

[i]Proof.[/i]  	Let $a_i \ge 0$ denote the initial distance 	between $B_i$ and $B_{i+1}$, 	and let $\Delta_i$ denote the distance travelled by ball $i$. 	Of course we have 	$\Delta_1 \le a_1 + \Delta_2$, 	$\Delta_2 \le a_2 + \Delta_3$, 	\dots, 	$\Delta_{n-1} \le a_{n-1} + \Delta_n$ 	by the relative ordering of the bowling balls. 	Finally, distance covered by $B_n$ is always 	$\lambda$ times distance travelled by other bowling balls, so 	\begin{align*} 		\Delta_n &\le \lambda \sum_{i=1}^{n-1} \Delta_i 		\le \lambda \sum_{i=1}^{n-1} 		\left( \left( a_i + a_{i+1} + \dots + a_{n-1} \right) 			+ \Delta_n \right) \\ 		&= (n-1)\lambda \cdot \Delta_n + \sum_{i=1}^{n-1} i a_i 	\end{align*} 	and since $(n-1)\lambda > 1$, this gives an upper bound. $\blacksquare$

[b][color=red]Claim:[/color][/b]  When $\lambda \ge \frac{1}{n-1}$, it suffices to always jump the leftmost flea over the rightmost flea.

[i]Proof.[/i]  If we let $x_i$ denote the distance travelled by $B_1$ in the $i$th step, then $x_i = a_i$ for $1 \le i \le n-1$ and $x_i = \lambda(x_{i-1} + x_{i-2} + \dots + x_{i-(n-1)})$.

In particular, if $\lambda \ge \frac{1}{n-1}$ then each $x_i$ is at least the average of the previous $n-1$ terms. So if the $a_i$ are not all zero, then $\{x_{n}, \dots, x_{2n-2}\}$ are all positive and thereafter $x_i \ge \min \left\{ x_n, \dots, x_{2n-2} \right\} > 0$ for every $i \ge 2n-1$. So the partial sums of $x_i$ are unbounded, as desired. $\blacksquare$

I claim the answer is $\lambda \ge \frac{1}{n-1}$. To see this works, consider the strategy of hopping the leftmost flea over the rightmost. After $n-1$ moves, all fleas will now be at distinct positions, and define $m$ to be the minimum distance between two consecutive fleas. Now, the minimum distance is always at least $m$, since the distance made by hopping is the average of all the other distances. So, every hop, the configuration's leftmost point moves forward at least $m$, and all fleas will eventually pass $M$.

If $\lambda <\frac{1}{n-1}$, define a point $P$, which is left of all the fleas, and call the distance from the $n$th rightmost flea to $P$ $d_n$. Then, call the leakiness of the configuration to be $d_1-\lambda(d_2+\ldots+d_n)$. If $\lambda<\frac{1}{n-1}$, this number is clearly always positive. Now, note that if a flea jumps but does not go past the 1st flea, then the leakiness must decrease. If the $i$th flea jumps over the $j$th, and actually becomes the first flea, then the leakiness changes by $-(1+\lambda)d_1+(d_j-d_i)\lambda+d_j+\lambda d_i=(1+\lambda)(d_j-d_1)$. As $d_j\le d_1$, this value is nonpositive, so the leakiness doesn't increase.

The minimum leakiness required to get across $M$ is $(1-(n-1)\lambda)PM$, so if we move $M$ sufficiently far to the right, this quantity becomes larger than the leakiness of the initial configuration, as desired.

I would like to point out that the problem solver should notice that the rightmost guy is special. We want the rightmost guy to the as far to the right as possible and all others as far left as possible. Then just from this we can make some monovariant.

The answer is $\lambda\ge\frac1{n-1}$.

[color=blue][b]Proof of lower bound.[/b][/color] We will use this obvious strategy --- the leftmost flea always jumps over the rightmost flea. Consider the nondecreasing sequence $(x_i)_{i\ge1}$ with $0<x_1\le\cdots\le x_n$ the starting coordinates of the fleas; for each $k>n$, let $x_k=x_{k-1}(\lambda+1)-x_{k-n}\lambda$. After $k$ moves, the fleas have coordinates $x_{k+1}$, $\ldots$, $x_{k+n}$. I will prove this sequence is unbounded.

Summing over $x_k-x_{k-1}=\lambda(x_{k-1}-x_{k-n})$, we have \[x_k-x_n=\lambda\left(x_{k-1}+\cdots+x_{k-(n-1)}\right)-\lambda(x_1+\cdots+x_{n-1}).\] In other words, $x_k-\lambda\left(x_{k-1}+\cdots+x_{k-(n-1)}\right)$ is a fixed constant $C>0$. Then since $x_{k-(n-1)}\le x_{k-i}$ for $0\le i\le n-2$, we have \begin{align*}     \frac{x_k+\cdots+x_{k-(n-2)}}{n-1}&\ge\frac{x_k+\cdots+x_{k-(n-1)}}n\\     &=\frac{C+(\lambda+1)\left(x_{k-1}+\cdots+x_{k-(n-1)}\right)}n\\     &\ge\frac Cn+\frac{x_{k-1}+\cdots+x_{k-(n-1)}}{n-1}, \end{align*} so $x_{k-1}+\cdots+x_{k-(n-1)}$ is unbounded, and thus so is $(x_i)_{i\ge1}$.

[color=blue][b]Proof of upper bound.[/b][/color] At some point in time, let the fleas have coordinates $0<x_1\le x_2\le\cdots\le x_n$, and let $I=x_n-\lambda(x_1+\cdots+x_{n-1})$.

[color=red][b]Claim:[/b][/color]      $I$ is nonincreasing.

[i]Proof.[/i]      Let $x_i$ jump over $x_j$ to $x_i'$, so that $x_i'=x_j(\lambda+1)-x_i\lambda$, and let $I$ map to $I'$. If $x_i'<x_n$, then \[I'=I-\lambda(x_i'-x_i)=I-\lambda(\lambda+1)(x_j-x_i)<I.\]     Otherwise $x_i'\ge x_n$, so $x_i'$ is the new maximum and     \begin{align*}         I'&=I+x_i'-x_n-\lambda(x_n-x_i)\\         &=I-x_n(\lambda+1)+(x_i'+\lambda x_i)\\         &=I-(x_n-x_j)(\lambda+1)\le I,     \end{align*}     which proves the claim. $\blacksquare$

However if at some point $x_n>M$, then \begin{align*} I&=x_n-\lambda(x_1+\cdots+x_{n-1})\\ &>x_n-\lambda(x_n+\cdots+x_n)\\ &=x_n\big[1-(n-1)\lambda\big]\\ &>M\big[1-(n-1)\lambda\big], \end{align*} which is larger than $I$ for sufficiently large $M$.

We want to find all $\lambda$ for which it is impossible to move all fleas infinitely rightward. I claim our answer is all $\lambda \geq \tfrac{1}{n-1}$.

When $\lambda \geq \tfrac{1}{n-1}$, we can simply let the leftmost flea jump over the rightmost one on each move. After $n-1$ moves, we will have $n$ fleas in positions $p_1 < p_2 < \ldots < p_n$. If we let $\delta = \min{(p_{i+1} - p_i)}$ for $i \in [1, n-1]$, then it is easy to see that after each move, the distance between the leftmost and rightmost fleas is nondecreasing and thus so is $\min{(p_{i+1} - p_i)}$, and that thus the new leftmost flea's position is at least $\delta$ to the right of the old one. Hence the leftmost flea can go arbitrarily far to the right by moving $\delta$ each time, and thus so can the rest of the fleas.

When $\lambda < \tfrac{1}{n-1}$, I claim that the position of the rightmost flea is bounded. Indeed, suppose that after some $\ell$ moves, the $n$ fleas are at positions\[q_1 \leq q_2 \leq \ldots \leq q_n\]with largest $m_{\ell} = q_n$ and sum $s_{\ell}$. If we were to perform a move on fleas on $q_i < q_j$, which must exist since all fleas can never be on the same point, then:[list]
[*]the maximum changes from $m_k$ to $m_{k+1}$ by at most $\lambda(x_j - x_i)$, which happens when $j = n$.
[*]the sum changes from $s_k$ to $s_{k+1}$ by exactly $(x_j + [x_j + \lambda(x_j - x_i)]) - (x_i + x_j) = (1 + \lambda)(x_j - x_i)$
[/list]
Therefore, after any number of moves $K$, we see that\[m_K \leq m_0 + (\lambda y_1 + \ldots + \lambda y_K) = m_0 + \lambda(y_1 + \ldots y_K)\]and\[s_K = s_0 + ([1 + \lambda]y_1 + \ldots + [1 + \lambda]y_K) = s_0 + (1 + \lambda)(y_1 + \ldots + y_K)\]where $y_i$ is the positive difference in the positions of the fleas moved in the $i$th move. Thus, we see that the ratio $\tfrac{\Delta m}{\Delta s}$ is at most $\tfrac{\lambda}{1 + \lambda}$ after any number of moves, and in fact we can solve\[\frac{m_K - m_0}{s_K - s_0} \leq \frac{\lambda}{1 + \lambda} \implies m_K \leq m_0 + \frac{\lambda}{1 + \lambda}\left(s_K - s_0\right) \leq m_0 + \frac{\lambda}{1 + \lambda}(nm_K - s_0)\]and obtain that $m_K \leq \tfrac{m_0 - \mathcal{C}s_0}{1 - \mathcal{C}n}$ which is a positive constant since $\lambda < \tfrac{1}{n-1} \implies \mathcal{C} = \tfrac{\lambda}{1 + \lambda} < \tfrac{1}{n}$. Thus, the fleas' positions are upper bounded by some positive constant, so if we make the starting points far left enough it is impossible to take them all to the right of a given position $M$. $\blacksquare$

[b]Setup[/b]
We claim that the answer is $\lambda \ge \tfrac{1}{n-1}.$ In the proof, we shall be making use of two variables that change with the flea's position. We define $R$, the position of the right-most flea. Suppose we have fleas $A_1, A_2, \dots, A_n$, and define $d(A_i,A_j)$ to be the positive difference between the positions of flea $A_i$ and flea $A_j.$ Define our second variable, $S$, to be $d(A_1,A_n)+d(A_2,A_n)+\dots + d(A_{n-1},A_n).$ To make our proof easier, we note that if $R\ge M$ at any point in our iteration of moves, we are done since any move that makes fleas jump over this right-most flea will bring that flea past $M$.

[b]Bound[/b]
To prove our bound first, let $\lambda<\tfrac{1}{n-1}$ and we consider a single move, which WLOG starts from a configuration such that $A_1,A_2,\dots, A_n$ are placed in that order from left to right. Then, define $d_i$ to be the initial value of $d(A_i,A_n).$ It is easy to see that $S=d_1+d_2+\dots + d_{n-1}$. Now, suppose $A_i$ jumps over $A_j$, and we split this into several cases.

[u]Case 1: $A_i$ ends up to the left of $A_n$[/u]
In this case, $S$ decreases and $R$ doesn't increase. We do not elaborate further.

[u]Case 2:  $A_i$ ends up to the right of $A_n$[/u]
In this case, $S$ and $R$ are both maximized when $A_2$ jumps over $A_n$. Indeed, we have $d(A_n,A_i)\le \lambda d_i.$ Thus, $R$ increases by at most $\lambda d_i$ Note that $d(A_j,A_i)\le d(A_j,A_n)+d(A_n,A_i)\le d_j+\lambda d_i$ so \[S\le d_1+\dots + \lambda (n-1)d_i+d_{i+1}+\dots +d_{n-1}\]
Thus, $S$ decreases by at least $(1-\lambda (n-1)) d_i.$

Combining both cases, for every $\lambda>0$ we want to increase $R$ by, we must proportionally decrease at least $(1-\lambda (n-1))>0$ from $S$. Since $S$ must be non-negative at all times, $R$ is bounded, so let $M$ be anything that $R$ cannot reach, and our bound is proved.

[b]Construction[/b]
Our construction for $\lambda \ge \tfrac{1}{n-1}$ is as follows: take the left-most flea and jump it across the right-most flea. We again let $A_1,A_2,\dots, A_n$ be placed in that order from left to right and define $d_i$ to be the initial value of $d(A_i,A_n).$ Initially, $S=d_1+d_2+\dots + d_{n-1}.$ After the move, $d(A_i,A_1)$ becomes $d(A_i,A_n)+d(A_n,A_i)=d_i+\lambda d_1$, so $S$ becomes \[\lambda(n-1)d_1+d_2+\dots + d_{n-1}\ge d_1+d_2+\dots + d_{n-1}.\] In particular, this means that the distance between the first and last flea is always at least $\tfrac{S}{n-1}$ so $R$ increases by at least $\tfrac{S}{(n-1)^2}$ each time. Therefore, $R$ is not bounded. We are done.

The answer is all $\lambda \geq \frac{1}{n-1}.$ To prove that this works, we let the leftmost flea jump over the rightmost on each move. If at some moment pairwise distances between consecutive fleas from left to right are $a_1,a_2,\dots ,a_{n-1},$ then after the move they become $a_2,a_3,\dots ,a_{n-1}, \lambda \sum a_i\geq \min a_i$. Therefore the average value of these distances doesn't decrease, so the distance between leftmost and rightmost fleas never decreases too and fleas can jump sufficently far.

Now assume $\lambda <\frac{1}{n-1}.$ Numerate fleas by $1,2,\dots ,n$ and let at the moment $x_i$ denotes the coordinate of $i-$th flea.

[b]Claim.[/b] Number $F=2\max x_i -\sum_{j=1}^n x_j$ is a nonincreasing monovariant under moves.
[i]Proof.[/i] Let $\varphi$ be a move $x_i\mapsto x_j+\lambda (x_j-x_i)$ for $x_i<x_j.$ Then $$\varphi (F)=\begin{cases} F-\lambda (\varphi(x_i) -x_i)<F,\, &\text{if } \varphi (x_i)<\max x_k \\ F-(1+\lambda)(x_n-x_j)\leq F,\, &\text{otherwise} \quad \Box \end{cases}$$

But for the moment $\max x_k >M$ we obtain $$F>(1-\lambda (n-1))x_n>(1-\lambda (n-1))M\implies M<\frac{\max F}{1-\lambda (n-1)}.$$

very cool
[hide = solution]
We show that the answer is all real numbers $\lambda \ge \frac{1}{n-1}$. Also in what follows, we'll assume the line to be the number line, with origin to the left of all fleas, so that they have positive coordinates (this is not necessary, but it has been done for convenience).

We'll show sufficiency for now. First, while there are fleas on the same position, we make them jump over the right most flea. Eventually all fleas are on distinct positions. Now let $\delta$ be the minimum gap between consecutive fleas. If we repeatedly make the left most flea jump over the right most flea, then the barycenter of the fleas moves to the right by at least $\delta$ every turn. Eventually the barycenter crosses the point $M$, and so some flea is beyond $M$. Then we make all the other fleas jump over this one, and all fleas are to the right of $M$, as required.

Now it suffices to show that if $\lambda < \frac{1}{n-1}$ then there is some point $M$ which no flea can go beyond. The idea is to look at the position of the barycentre and the position of the right most flea after (say) $m$ turns. Let these positions be $a_m, b_m$ respectively. Suppose the operation was performed on fleas with positions $x < y$ in the $m$th turn. Then some algebra reveals that: \[a_m-a_{m-1} = \frac{(1+\lambda)}{n} \cdot (y-x)\] and that $\[b_m-b_{m-1} \leq \lambda(y-x)\]$. It follows plainly that $\frac{b_m-b_{m-1}}{a_m-a_{m-1}} \leq \frac{n\lambda}{1+\lambda}$. Let $K$ denote the previous constant. Observe that $K < 1$ and that $b_m-b_{m-1} \leq K(a_m-a_{m-1})$. Adding up across all previous $m$, we obtain $b_m-b_0 \leq K(a_m-a_0) < K(b_m-a_0)$ implying that $b_m < \frac{b_0-Ka_0}{1-K}$, and so the point with coordinates $\frac{b_0-Ka_0}{1-K}$ works for $M$.
[/hide]

[hide=Solution]We claim that it is possible iff $\lambda \ge \frac{1}{n-1}$.\\
Let $a_i$ be the distance between the $i$th frog from the left and the $i+1$th frog from the left.
Consider the quantity $\sum ia_i$. Note that if the $k$th frog from the left jumps in front of the rightmost frog to a distance $x$ in front of the rightmost frog, then the new distances are $b_1,\cdots b_{n-1} = a_1,\cdots,a_{k-2},a_{k-1}+a_k,a_{k+1},\cdots,a_n,x$, where $a_0 = 0$. Note that $x \le (n-1)\lambda (a_k+\cdots+a_{n-1})$ with equality if the $k$th frog from the left actually jumps over the rightmost frog.\\
$[\sum ia_i] - [\sum ib_i] = a_k+\cdots +a_{n-1}-(n-1)x \ge a_k + \cdots + a_{n-1} - (n-1)\lambda (a_k + \cdots + a_{n-1}) = (1-(n-1)\lambda) (a_k+\cdots+a_{n-1}))$.\\
Note that if on the other hand the $k$th frog from the left jumps to in between the $j$th frog from the left and the $j+1$th frog from the right (and the distance between the $j$th frog from the left and the position the frog jumped to is $x$) then the new distances are
$b_1,\cdots,b_{n-1} = a_1,\cdots,a_{k-2},a_{k-1}+a_k,a_{k+1},\cdots,a_{j-1},x,a_j-x,a_{j+1},\cdots,a_{n-1}$. Therefore,\\
$[\sum ia_i] - [\sum ib_i] = a_k+a_{k+1}+\cdots+a_{j-1}+ja_j-(j-1)x-j(a_j-x) = a_k+\cdots+a_{j-1}+x$.\\
We now prove that if $\lambda \ge \frac{1}{n-1}$ then it is possible.\\
We employ the strategy of having the leftmost frog jump over the rightmost frog. Note that in this case $[\sum ia_i] - [\sum ib_i] = (1-(n-1)\lambda) (a_1+\cdots +a_n))$. However, note that this is non-positive for $\lambda \ge \frac{1}{n-1}$. Therefore, since $\sum_{a_i} > \frac{\sum ia_i}{n}$, and $\sum ia_i$ is increasing, $\sum a_i$ is bounded below by a constant $C$, so after
$n-1$ moves when the original rightmost frog is the leftmost, the new rightmost frog is at least a distance of $2C$ from the original leftmost frog, and in general in $k(n-1)$ moves the rightmost frog is at least $(k+1)C$ away from the rightmost frog. This can grow as large as required, as required.\\
We now prove that if $\lambda < \frac{1}{n-1}$ then it is not possible no matter the configuration.
Note that if $\lambda < \frac{1}{n-1}$ then $\sum ia_i$ is decreasing. Also note that if a frog doesn't jump in front of the rightmost frog, then $\sum ia_i$ decreases by the distance that it travelled, and so since $\sum ia_i < (n-1)(\sum a_i)$, the frogs can jump a distance of at most
$(n-1)(\sum a_i)$ in this manner. Note on the other hand that if a the $k$th frog from the left jumps to a distance $x$ in front of the rightmost frog, then it has traveled a distance of $a_k+\cdots+a_{n-1}+x$, and $\sum ia_i$ decreases by $a_k+\cdots+a_{n-1}-(n-1)x$, but
$\frac{a_k+\cdots+a_{n-1}-(n-1)x}{a_k+\cdots+a_{n-1}+x} = 1-\frac{nx}{a_k+\cdots+a_{n-1}+x} = 1-\frac{n}{\frac{a_k+\cdots+a_{n-1}}{x}+1}$, which is minimised when $\frac{n}{\frac{a_k+\cdots+a_{n-1}}{x}+1}$ is maximal, but this is maximised when $\frac{a_k+\cdots+a_{n-1}}{x}$ is minimal, but this is minimised when $x$ is maximal. The maximum value of $x$ is $\lambda(a_k+\cdots+a_n)$, so the minimum value of the fraction is
$\frac{(1-(n-1)\lambda)(a_k+\cdots+a_n)}{(1+\lambda)(a_k+\cdots+a_n)} = \frac{1-(n-1)\lambda}{1+\lambda}$. Therefore, $\frac{[\sum ia_i]-[\sum ib_i]}{\text{distance travelled}} \ge \frac{1-(n-1)\lambda}{1+\lambda} \implies \sum ib_i \le [\sum ia_i] - \frac{1-(n-1)\lambda}{1+\lambda}\text{distance travelled}$. Therefore, the total distance that can be travelled by jumping over the rightmost frog is at most $\frac{1+\lambda}{1-(n-1)\lambda}[\sum ia_i]$. Therefore, the total distance the frogs can jump is bounded above by a constant in terms of the $a_i$ and $\lambda$, and so the furthest distance a frog can jump is also bounded above by this constant, so we are done.[/hide]
[hide = Comments] When I found the monovariant $\sum ia_i$, I thought it would be pretty easy to finish from there, but it turned out that a lot more work had to be done to prove that $\lambda < \frac{1}{n-1}$ fails. Edit: after some algebra (turning the $a_i$ into the $f_i$) my invariant is actually almost the same as Juan Ortiz's invariant.[/hide]

Could not find this invariant until hinted largely ;-;

Note that this is equivalent to having one flea travel arbitrarily far.

[b][color=pink]Claim:[/color][/b] We can achieve $\lambda \ge \frac{1}{n - 1}$.
[i]Proof.[/i] Let the fleas have initial starting positions $a_1, a_2, \dots, a_n$. Let $C = \underset{i}{argmin} (a_{i+1} - a_i)$ be the minimum difference between two consecutive fleas.
Then $a_n - a_1 \ge (n-1)C$ so jumping $a_1$ over $a_n$ to position $a_{n+1}$ makes it so that $a_{n+1} - a_n \ge C$, so $C$ remains the minimum distance between any two fleas.  Repeatedly jumping the last flea over the first flea gives the result. $\blacksquare$

[b][color=pink]Claim:[/color][/b] $\lambda < \frac{1}{n-1}$ is impossible.
[i]Proof.[/i] Consider the value of $a_n - \lambda (a_1 + \dots + a_{n-1})$ where flies are re-labeled after each turn based on order.
We claim that this value is a monovariant that doesn't increase.
Unless the farthest fly changes, the value is guarenteed to decrease. Else, suppose that $a_i$ jumps over $a_j$ to become the furthest fly. As $j$ increases, the value afterwards decreases. Thus, assume $j = n$ and that $a_i$ jumps to $(1 + \lambda)a_n - \lambda a_i$.
However, then equality holds as \[ (1 + \lambda)a_n - \lambda a_i - \lambda (a_1 + \dots + a_n - a_i) = a_n - \lambda (a_1 + \dots + a_{n-1}). \]
Then, it follows that for some $C$ and given initial config \[ C \ge a_n - \lambda (a_1 + \dots + a_{n-1}) \ge a_n (1 - \lambda (n-1)) \] which implies $a_n \le \frac{C}{1 - \lambda(n-1)}$ which bounds growth. $\blacksquare$


quadratics
number theory proposed
number theory

Look at the equation modulo 3 firstly:

$(-1)^n + n^2 \equiv 0$ so $n\equiv 1$ or $2 \mod 3$. Then look modulo 7:

$n^2 \equiv -2^n \equiv -2 $ or $-4$ (as $2^3\equiv 1 \mod 7$) $\equiv 5$ or $3$. But $5$ nor $3$ are quadratic residues modulo 7 hence no solutions.

Is this problem really correct?  :?

I wonder, too. This looks too easy... Omid Hatami, please tell us?

I think you forget that some of the variables can equal zero. Anyway, the problem is easy, but there are some missed cases, since I see that $n1$ works perfectly for instance.

[quote="lomos_lupin"]Gentlemen(i mean the moderators , harazi ,megus & Arne ), I think the problem is in this form:
$p,q \in \mathbb{N} \cup \{0\}$
As megus has showd one of the $p,q$ must be zero  so we shall solve it in these forums:
1.$n^2=3^p-2^n$
2.$n^2=7^q-2^n$[/quote]
I think we can only consider $n^2=3^p-2^n$,since I think $n^2+2^n$ can't be divide by 7;I think p will be an odd number also.
(I don't know is my thought is correct or not :? )

[quote="cuopbientcd"]easy to prove that $q=0$.I have
$n^{2}+2^{n}=3^{p}\Rightarrow p is even$
$VietNam is always in my heart$[/quote]
or p=1.
All solutions $n=1$ and $n=3$.

[hide=Solution]
[quote=Iran MO Round 3 2005 N1]Find all $n,p,q\in \mathbb N$ that:\[2^n+n^2=3^p7^q\][/quote]
[b][color=#000]Solution:[/color][/b] Clearly, $n$ is odd. If $n=1$ $\implies$ $p=1,q=0$. If $p=0$,
$$2^n+n^2=7^q \implies n^2 \equiv -1 \pmod{3}$$
A Contradiction! Assume $n \geq 2$ & If $q=0$ $$\implies 2^n+n^2=3^p$$
Note, $3$ doesnot divide $n$. Taking, $\pmod{4}$ yields $p$ is even. Let $p=2p'$
$$2^n=3^{2p'}-n^2=(3^{p'}+n)(3^{p'}-n) \implies \begin{cases} 3^{p'}+n =2^a \\ 3^{p'}-n=2^b \end{cases} \implies 2\times 3^{p'}=2^a+2^b$$
Hence, $b=1$ $\implies$ $2n=2^{n-1}-2 \implies 2^{n-2}=n+1 $ which gives no solutions for $n \geq 2$. So, $p,q \geq 1$.
$$2^n+n^2=3^p7^q$$
Using the fact, $3$ doesnot divide $n$ $\implies$ taking $\pmod{7}$ yields contradiction! Hence $\boxed{(n,p,q)=(1,1,0)}$ $\qquad \blacksquare$
[/hide]


If $ A^T A \equal{} A$, prove that $ A \equal{} A^2$.

A is normal, hence similar to diagonal matrix by conjugation with an unitary matrix. Hence, wlog A can be assumed to be diagonal. From here is easy. ;)

Let's make it simpler. Take the transpose of both sides of $ A^TA\equal{}A$ to get $ A^TA\equal{}A^T.$ Hence $ A\equal{}A^T.$ From which it follows that ...

[quote="Kent Merryfield"]Let's make it simpler.[/quote]Oupps, some kind of overkill that was.  :whistling: Thanks for pointing it out.


If $ a,b,c\geq 0$ and $ a\plus{}b\plus{}c\equal{}1$ prove that:
\[ \frac{b}{\sqrt{a^{2}\plus{}3b}}\plus{}\frac{c}{\sqrt{b^{2}\plus{}3c}}\plus{}\frac{a}{\sqrt{c^{2}\plus{}3a}}\leq\frac{1}{\sqrt{1\plus{}3abc}}\]

[quote="Svejk"]If $ a,b,c\geq 0$ and $ a\plus{}b\plus{}c \equal{} 1$ prove that:
\[ \frac{b}{\sqrt{a^{2}\plus{}3b}}\plus{}\frac{c}{\sqrt{b^{2}\plus{}3c}}\plus{}\frac{a}{\sqrt{c^{2}\plus{}3a}}\leq\frac{1}{\sqrt{1\plus{}3abc}}\]
[/quote]
$ \sum_{cyc}\frac{b}{\sqrt{a^{2}\plus{}3b}}\leq\sqrt{\sum_{cyc}\frac{b}{a^{2}\plus{}3b}}.$ Hence, it remains to prove that $ \sum_{cyc}\frac{b}{a^{2}\plus{}3b}\leq\frac{1}{1\plus{}3abc}.$
But $ \sum_{cyc}\frac{b}{a^{2}\plus{}3b}\leq\frac{1}{1\plus{}3abc}\Leftrightarrow$
$ \Leftrightarrow\sum_{cyc}\left(\frac{3b}{a^{2}\plus{}3b}\minus{}1\right)\leq\frac{3}{1\plus{}3abc}\minus{}3\Leftrightarrow\sum_{cyc}\frac{a^{2}}{a^{2}\plus{}3b}\geq\frac{9abc}{1\plus{}3abc}.$
By C-S we obtain: $ \sum_{cyc}\frac{a^{2}}{a^{2}\plus{}3b}\geq\frac{1}{a^{2}\plus{}b^{2}\plus{}c^{2}\plus{}3}.$
And $ \frac{1}{a^{2}\plus{}b^{2}\plus{}c^{2}\plus{}3}\geq\frac{9abc}{1\plus{}3abc}\Leftrightarrow1\geq9abc(a^{2}\plus{}b^{2}\plus{}c^{2})\plus{}24abc\Leftrightarrow$
$ \Leftrightarrow(a\plus{}b\plus{}c)^{5}\geq9abc(a^{2}\plus{}b^{2}\plus{}c^{2})\plus{}24abc(a\plus{}b\plus{}c)^{2}\Leftrightarrow$
$ \Leftrightarrow\sum_{cyc}(a^{5}\plus{}5a^{4}b\plus{}5a^{4}c\plus{}10a^{3}b^{2}\plus{}10a^{3}c^{2}\minus{}13a^{3}bc\minus{}18a^{2}b^{2}c)\geq0,$ which Muirhead.

[quote="arqady"] 1\geq 9abc(a^{2} + b^{2} + c^{2}) + 24abc[/quote]

We can prove this inequality but not use Muirhead.

We have very easy to prove that :$ (ab+bc+ca)^{2}\ge 3abc(a+b+c) = 3abc$

Hence, it remains to prove that

$ 1\ge 27(ab+bc+ca)^{2}(a^{2}+b^{2}+c^{2})$(*)

Setting $ p = ab+bc+ca$.

(*)$ \Leftrightarrow 1-27p^{2}(1-2p) = (1-3p)^{2}(1+6p)\ge 0$.

Hence :$ 9abc(a^{2}+b^{2}+c^{2})\le\frac{1}{9}$
And by AM-GM , $ 24abc\le\24\left(\frac{a+b+c}{3}\right)^{3}=\frac{8}{9}$

We're done . :)

[quote="Albanian Eagle"]REmemeber that $ (a\plus{}b\plus{}c)^{5}\geq 81abc(a^{2}\plus{}b^{2}\plus{}c^{2})$ and it can be solved only by am-gm :P[/quote]

uhm, this is my solution, but i rewrite it in the form $ 1\ge 81abc(a^{2}\plus{}b^{2}\plus{}c^{2})$  :)


Can you post you're solution because I always miss these kind of problems.

[quote="xxxxx"]Tony mixed 50ml of chocolate syrup into 50 ml of milk, and drank 25 ml of chocolate milk. He decided it wasn't chocolaty enough so he added 25 ml more chocolate syrup to his cup. What percent of the new solution is chocolate syrup?[/quote]
[hide]When the original syrup and milk are mixed, there is 50 ml of syrup and 50 ml of milk. Since he drank 25 ml of chocolate milk, then that means he drank 12.5 ml of both. Then there is 37.5 ml of syrup and 37.5 ml of milk.
Since he then added 25 ml of syrup in, then there is 62.5 ml of syrup and 37.5 ml of milk.
The final equation is $\frac{62.5}{37.5+62.5}=\frac{62.5}{100}=62.5\%$ of chocolate syrup.

vishalarul-> you got the percent of [i]milk[/i] but it's supposed to be the percent of [i]syrup[/i].[/hide]


geometry
geometric transformation
homothety
circumcircle
parallelogram
power of a point

The circles $\mathcal C_1$ and $\mathcal C_2$ touch each other externally at $D$, and touch a circle $\omega$ internally at $B$ and $C$, respectively. Let $A$ be an intersection point of $\omega$ and the common tangent to $\mathcal C_1$ and $\mathcal C_2$ at $D$. Lines $AB$ and $AC$ meet $\mathcal C_1$ and $\mathcal C_2$ again at $K$ and $L$, respectively, and the line $BC$ meets $\mathcal C_1$ again at $M$ and $\mathcal C_2$ again at $N$. Prove that the lines $AD$, $KM$, $LN$ are concurrent.

[i]Greece[/i]

The tangency points $B \equiv \omega \cap \mathcal C_1,\ C \equiv \omega \cap \mathcal C_2$ are the external homothety centers of the circle pairs $(\omega, \mathcal C_1),\ (\omega, \mathcal C_1).$ Therefore, BC is the external homothety axis of the 3 given circles, intersecting the center line of the circles $\mathcal C_1,\ \mathcal C_2$ at their external homothety center E. The single common internal tangent AD of the circles $\mathcal C_1,\ \mathcal C_2$ is their radical axis. Therefore, powers of the point A to these 2 circles are equal, $AK \cdot AB = AL \cdot AC,$ which means that the quadrilateral KBCL is cyclic. Let EK meet the circles $\mathcal C_1,\ \mathcal C_2$ at points $K, P, Q, L'$ in this order or in the order $P, K, L', Q$. (If EK is a tangent to $\mathcal C_1$ form E, then it is also a tangent to $\mathcal C_2$ from E and both $K \equiv P,\ L' \equiv Q$ are identical.) Powers of the point E to the circles $\mathcal C_1,\ \mathcal C_2$ are $EB \cdot EM = EK \cdot EP$ and $EC \cdot EN = EL' \cdot EQ,$ respectively. Since E is the external homothety center of the circles $\mathcal C_1,\ \mathcal C_2$, we have

$\frac{EB}{EN} = \frac{EM}{EC} = \frac{EK}{EQ} = \frac{EP}{EL'} = \frac{r_1}{r_2}$

where $r_1,\ r_2$ are radii of the circles $\mathcal C_1,\ \mathcal C_2.$ Combining,

$EB \cdot EC = EK \cdot EL' = EM \cdot EN = EP \cdot EQ$

Thus the quadrilateral KBCL' is cyclic, which means that L' is the intersection of the circle $\mathcal C_2$ with the circumcircle of the triangle $\triangle KBC$, the points $L' \equiv L$ are identical, and the line KL passes through the external homothety center E of the circles $\mathcal C_1,\ \mathcal C_2.$ Let the opposite sides KM, LN of the quadrilateral KMNL meet at a point X. Since this quadrilateral is also cyclic, power of the point X to its circumcircle is equal to $XK \cdot XM = XL \cdot XN$. Consequently, powers of the point X to the circles $\mathcal C_1,\ \mathcal C_2$ are equal, so that this point lies on the radical axis AD, which is what we were supposed to prove.

The problem proposition is true for any point A on the single common internal tangent (radical axis) of the circles $\mathcal C_1,\ \mathcal C_2,$ not necessarily one of its intersections with the circle $\omega.$ What makes these intersections special is that KL is then not a secant of the circles $\mathcal C_1,\ \mathcal C_2$ from their external homothety center E, but a common external tangent. Indeed, since B is the external homothety center of the circles $\omega,\ \mathcal C_1,$ it is also the similarity center of the triangles $\triangle KBM \sim \triangle ABC,$ which makes the lines $KM \parallel AC \equiv AL$ parallel. Likewise, since C is the external homothety center of the circles $\omega,\ \mathcal C_2,$ it is also the similarity center of the triangles $\triangle LNC \sim \triangle ABC,$ which makes the lines $LN \parallel AB \equiv AK$ parallel. Consequently, AKXL is a parallelogram and its diagonals AX, KL cut each other in half. Since the diagonal AX is the radical axis of the circles $\mathcal C_1,\ \mathcal C_2$ and the diagonal KL passes through their external homothety center, KL is not a secant, but a common external tangent of these 2 circles.

BKLC cyclic(AK*BA=AL*AC)
BKM=NLC(to see draw tangents from B and C)
BMK=BCA(to see draw the tangent from A)analogues you can see CNL=CBA
so we have MKL+LNC=180(to see obseve that KL is the common tangent to O1 and O2)
MKLN cyclic so we imagine its circle and taking in counting the cercles O1 and O2 we observe that AD,MK,NL are concurent ass the radical axis of these 3 circles

Let $\{T\}=MK\cap NL$.

Observe inversion with center at $A$ and pover $r=AD$.

Since $AK\cdot AB =AD^2=AL\cdot AC$ this inversion sends circle $\omega$
to comon tangent $KL$ cirles $\mathcal{C}_1$ and $\mathcal{C}_2$.

Let $\{X\}= KL\cap t_C$, where $t_C$ is tangent line at $C$.  Now we have:

\begin{eqnarray*}
\angle LKM &= & \angle KBM \\
                  &=& \angle KBC \\
                  &=& \pi-\angle KLC\\
                 & =& \angle CLX \\
                 &=& \angle LNC \\
&=&\pi-\angle MNL
\end{eqnarray*}

so $KMNL $ is cyclic.

Then $TM\cdot TK = TN\cdot TL$ witch implies $T$ is on comon tangent at $D$.                      Q.E.D

Dear Vladimir and Mathlinkers,
thank you for your nice proof and hope you are well. When reading your message, I translate it in this way.
1. By using my favorite theorem (Reim):  AC//KM , AB//LN and (tangent at A, noted Ta) //KL.
2. Ta and BC are antiparallel wrt AB and AC; it follows that KL and BC are antiparallel wrt AB and AC.
    thus B, C, K, L are concyclic ; let 2 this circle
3. Using a converse of "the theorem of the five circles",  M, N, K and L are cocyclic.
4. According to the power of A wrt 2, AD is the radical axis of the two initial circles.
5. By Monge's theorem we are done.
Sincerely
Jean-Louis

http://perso.orange.fr   vol. 2  Du theoreme de Reim au theoreme des six cercles p. 6-8.

I ask Jean Louis Ayme for validification.......
A very short proof...
1. by monge, BKLC is cyclic.
2.  'theorem of five circles' shows MNKL is cyclic.
3. i look to monge again.
we are done.
4 years after the problem was preposed......
may i ask where this problem came from?

Dear Sincostan and Mathlinkers,
yes your proof is shorter and more synthetic than mine...
You are in a good way...
Sincerely
Jean-Louis

$A$ being on the radical axis of the two circles, from its power to the said circles, $BCLK$ is cyclic, so $\widehat {ALK}=\widehat{KBC}$ $(\ 1 \)$. The circles $\mathcal {C}_{1}$ and $\omega $ being homothetic at $B$, $AC\parallel KM$, similarly $LN\parallel AB$, therefore, if $\{ T\} \equiv KM \cap LN$, $AKTL$ is a parallelogram with its diagonals bisecting each other and $\widehat {LKM}=\widehat{ALK},$ $( \ 2 \ )$.
From $(1)$ and $(2)$ we get $\widehat {MKL}=\widehat{MBK}$, i.e. $KL$ is the common external tangent of the circles $\mathcal {C}_{1}$ and $\mathcal {C}_{2}$, that is, the midpoint of $[KL]$ lies on the radical axis of the two circles, or $AD$ is a diagonal of the above parallelogram, done.

Best regards,
sunken rock

Dear Mathlinkers,
an article IN ENGLISH concerning this proof has been put on my website
http://perso.orange.fr/jl.ayme vol. 10
Sincerely
Jean-Louis


inequalities
search
function
calculus
inequalities unsolved

Show that if $ x,y,z\ge 0$, $ x\plus{}y\plus{}z \equal{} 1$, we have
\[ x^{2}y\plus{}y^{2}z\plus{}z^{2}x\le\frac{4}{27}\]
(I'm very sorry if this has been posted before... I am not good with the search function :blush: )

[hide="Outline of my solution"]
If x<y<z (or any cyclic permutation) we have $ \sum_{cyc}{x^{2}y}\le\sum_{cyc}{x^{2}z}$, and by Schur, we have $ \sum_{sym}{x^{2}y}\le\frac{1}{4}(a\plus{}b\plus{}c)^{3}\equal{}\frac{1}{4}$, so the inequality holds.

If WLOG $ x\ge y\ge z$ (or any cyclic permutation), we let the LHS be $ f(x,y,z)$. It is easy to show that $ f(x\plus{}z,y,0)\ge f(x,y,z)$, and then we have a one-variable inequality $ a^{2}(1\minus{}a)\le\frac{4}{27}$, which is obvious by calculus (could someone show me a better way for that? :D )
[/hide]

Proof for $ a^{2}(1\minus{}a)\le\frac{4}{27}$. If $ 1\minus{}a<0$, the inequality is obvious. Otherwise, $ \frac{ (2\minus{}2a)\plus{}a\plus{}a}{3}\ge\sqrt[3]{2(1\minus{}a)(a)(a)}$, as desired.

Hi, I think it is not so hard. There are harder inequlities. Even I had success with this.
This one is from Canadian Math Olympiad - 1999. There are solutions at:
http://math.ca/Competitions/CMO/. Enjoy!


The Queen of Byteland is very loved by her people. In order to show her their love, the Bytelanders have decided to conquer a new country which will be named according to the queen's name. This new country contains N towns. The towns are connected by bidirectional roads and there is exactly ONE path between any two towns, walking on the country's roads. For each town, the profit it brings to the owner is known. Although the Bytelanders love their queen very much, they don't want to conquer all the N towns for her. They will be satisfied with a non-empty subset of these towns, with the following 2 properties: there exists a path from every town in the subset to every other town in the subset walking only through towns in the subset and the profit of the subset is maximum. The profit of a subset of the N towns is equal to the sum of the profits of the towns which belong to the subset. Your task is to find the maximum profit the Bytelanders may get.  1<=N<= 10000  Profit of every town can be negative it's an integer from interval [-1000, 1000].

You're given that the cities form a tree. So, make a tree with any arbitrary city as the root. Then, recursively calculate the answer as follows:
Recursively calculate all the answers for each child, and add up all the positive ones, also storing the max answer. Then the answer is the maximum of (max child, current profit + sum).


limit
modular arithmetic
real analysis
real analysis unsolved

Another problem from Royden. It's under the section on a Non-measurable set.

Give an example of a sequence of sets $<E_{i}>$ such that $E_{i}\supset E_{i+1}$ and $m^{*}E_{i}<\infty$ and $m^{*}(\cap E_{i})<\lim m^{*}E_{i}$.

Do the following, which is one variant of the standard construction. Partition $[0,1)$ into equivalence classes in which $x\sim y$ iff $x-y\in\mathbb{Q}.$ Let $A$ consist of one element chosen from each equivalence class.

Now let $r_{j}$ be an enumeration of the rationals in $[0,1).$ Define $F_{i}\subset[0,1)$ as follows: $x\in F_{j}$ iff $x\equiv a+r_{j}\pmod{1}$ for some $a\in A.$

(Essentially, $F_{j}=A+r_{j}$ but we are doing the addition modulo 1.)

Now let $E_{i}=\bigcup_{j=i}^{\infty}F_{j}.$

Each $E_{i}\subset[0,1)$ so each has outer measure no larger than 1. In fact, $E_{1}=[0,1)$ so its outer measure must be 1. Furthermore, for each $j,\ m^{*}F_{j}=m^{*}A,$ and since $A$ is nonmeasurable, $m^{*}A=m^{*}F_{j}>0.$ Then $m^{*}E_{i}\ge m^{*}A$ and $\lim m^{*}E_{i}\ge m^{*}A>0.$ But with the $F_{j}$ being pairwise disjoint, $\bigcap_{i=1}^{\infty}E_{i}=\emptyset,$ which has outer measure zero.

Thanks! I've thought of the same construction, but was too obsessed with calculating the measure of $A$.

So, my next question is: what is the measure of $A$? Is it dependent on the choice of elements from the equivalence classes?

You mean, what is the [b]outer[/b] measure of $A?$ (It's not measurable, of course.)

[hide="Deleted."]That outer measure is 1; I'm just not sure I want to show that.[/hide] As you noticed, I was intentionally ducking this question above. Anyone else want to take a crack at it?

[quote="Kent Merryfield"]That outer measure is 1; I'm just not sure I want to show that. As you noticed, I was intentionally ducking this question above. Anyone else want to take a crack at it?[/quote]
Why? You can make $A\subset[0,1/2)$ as well.

Hmmm. So, it's possible for to choose $A$ such that the outer measure is bounded above by any value. But the outer measure must definitely be positive.

Thanks!


geometry
incenter
circumcircle
Euler
trigonometry
angle bisector
geometry unsolved

let ABC an acuteangled triangle, the excircle opposite to A meet at M, K and N to the lines AC, AB and BC, Let T the midpoint of MK, if ABTC is cyclic, prove that I, O and N are collinear. I: incenter, O: circumcenter :D

AMK is isosceles, so AT is median and angle bisector, so T lies on the bisector of $\measuredangle BAC$ and on the circumcircle of $ABC$, therefore it's the midpoint of the arc $BC$.
Now, $MT=TK$, $BT=CT$, $\measuredangle BMT=\measuredangle CKT$ and angles $\measuredangle MTB$ and $\measuredangle CTK$ are both acute, so triangles $MTB, TCK$ are congruent.
This implies that $ABC$ is isosceles on basis $BC$. Wherefrom the thesis follows.

EvaristeG, you are completely wrong. First, you switched the tangency points K, M. Even using the correct labels, the triangles $\triangle KTB, \triangle MTC$ are not congruent, in spite of having 2 congruent sides BT = CT, KT = MT and corresponding congruent angles $\angle BKT = \angle CMT,$ because conditions of the Ssa theorem are not satisfied.

The incenter I is the orthocenter of the excentral triangle $\triangle E_{a}E_{b}E_{c}$ and the circumcircle $(O)$ is its 9-point circle. Thus IO is the Euler line of the excentral triangle. Its circumcenter $O_{E}$ is the intersection of the Euler line IO and the normal $E_{a}N,$ because $\angle BE_{A}N = \frac{\angle B}{2}= \angle CE_{a}A,$ i.e., $E_{a}N, E_{a}A$ are isogonals with respect to the angle $\angle E_{c}E_{a}E_{b}\equiv \angle BE_{a}C,$ $E_{a}A$ passing through the orthocenter I. Thus I, O, N are collinear, iff the points $O_{E}\equiv N$ are identical, i.e., iff $r_{a}= R_{E},$ where $R,\ R_{E}= 2R$ are the circumradii of the original triangle $\triangle ABC$ and the excentral triangle $\triangle E_{a}E_{b}E_{c},$ respectively.

By the problem condition, $AE_{a}\perp MK$ meet at T, which is the midpoint of both of the segment MK and  the arc BC of $(O)$ opposite to A. Hence

$s \cos \frac{A}{2}= AT = 2R \cos \frac{B-C}{2}$

where $s = AM = AK$ is the semiperimeter of $\triangle ABC.$ Substituting $r_{a}= s \tan \frac{A}{2},\ \sin \frac{A}{2}= \cos \frac{B+C}{2},$

$r_{a}\cos^{2}\frac{A}{2}= 2R \cos \frac{B-C}{2}\cos \frac{B+C}{2}$

$r_{a}(1+\cos A) = 2R (\cos B+\cos C)$

Substituting $\cos B+\cos C-\cos A = \frac{r_{a}}{R}-1,$

$r_{a}+r_{a}\cos A = 2r_{a}-2R+2R \cos A$

$2R(1-\cos A) = r_{a}(1-\cos A),\ \ \ r_{a}= 2R = R_{E}$

which means that the tangency point N of $(E_{a})$ with BC and the circumcenter $O_{E}$ of the excentral triangle $\triangle E_{a}E_{b}E_{c},$ both on the normal $E_{a}N \perp BC,$ are identical, hence the points $I, O, N\equiv O_{E}$ are collinear.

This problem is problem 1 in chapter 1 of Andrei Negut, [i]Problems for the Mathematical Olympiads[/i], Zalau: GIL 2005, and the source given is: IMAR test, October 2003. Also, it has been discussed at http://www.mathlinks.ro/Forum/viewtopic.php?t=6158 . But I don't see any nice solution in any of these locations...

  darij


logarithms
number theory open
number theory

Does for all natural numbers $n\geq 3$ there exist numbers $a,b,c,d \in \mathbb{N}_0$ such that:

$2^a3^b+2^c+3^d=n$

If the above isn't true (any counterexample?) - is it possible to characterize the set of all natural numbers which are expressible in this form ?

I think it is easy to show that most numbers $n$ cannot be represented in this form.  Let's consider a large number $N$, and bound how many numbers $n$ from $3$ to $N$ are representable.  In this interval, each of the exponents $a$, $b$, $c$, and $d$ must be less than $\log_2 N$.  There are at most $(\log_2 N + 1)^4$ such quadruples $(a, b, c, d)$.  Thus at most $(\log_2 N + 1)^4$ of the numbers from $3$ to $N$ is representable.  But for $N$ large, $(\log_2 N + 1)^4$ is much smaller than $N$.


analytic geometry
geometry
perimeter
inequalities
function
rotation
geometric transformation

1. 1984 #9: When $ x\equal{}\minus{}1, ax^2\plus{}bx\plus{}c\equal{}6.$
                  When $ x\equal{}7, ax^2\plus{}bx\plus{}c\equal{}6,$ and
                  When $ x\equal{}1, ax^2 \plus{}bx\plus{}c\equal{}\minus{}6$
                  Find the smallest value for $ ax^2\plus{}bx\plus{}c$

2. 1985 #2: Point A has coordinates $ (\minus{}2,1)$. Point B is the image of A reflected in the line $ y\equal{}3$. Point C is the image of B reflected in the line $ y\equal{}x\plus{}3$. Point D is the image of C reflected in the line $ x\equal{}0$. What is the distance between A and D?

3. 1985 #6: What is the perimeter of the region bounded by the inequalities?
   $ y > |x|$ and $ y < \minus{}|x|\plus{}4$

Express your answer in simplest radical form.

4. 1987 #5: If $ A \equal{} {1,2,3}$ and $ B \equal{} {a,b,c,d}$ how many different functions are there that map A into B?

5. 1988 #4: Triangle ABC has vertices $ A(0,0), B(9,0), and C(9,40)$. The region enclosed by the triangle is rotated about the line $ x\equal{}9$.  The solid generated by this rotation is then revolved about the y-axis. How many cubic units are in the volume of the solid generated by the second revolution? Express answer in terms of pi.

1. -10
2. 0
3. $ 8\sqrt{2}$
4. 64
5. 6480pi

ps. how do you type pi in latex?

1.
I don't really understand how you can find the lowest possible value of ax^2+bx+c when it already equals 6.

[hide="2"]

just go step by step, even draw it out if needed.

So after reflected across y=3, it goes to (-2,5) To find where it lies after being reflected across y=x+3, find perpendicular line that contains (-2,5). You find that that is y=-x+3. The point of intersection of those two lines is (0,3).
so the reflection is (2,1). Then, after you reflect it from x=0, you get (-2,1). Since they are the same point, the distance is 0.[/hide]

[hide="3"]

y>|x| is basically the intersection of the lines y>x and y>-x.
y< -|x| + 4 is basically the same thing, except upside down and 4 units upwards.

Since they both have a vertex on the same x coordinate, but one is 4 units higher, the intersections of the two lines is (-2,2) and (2,2) With the vertexes being (4,0) and (0,0), that makes each side of the figue equal to 2sqrt2. 2sqrt2*4=8sqrt2.[/hide]

4. I don't understand how one number can have more than one value.

5. I'm too dumb to do this.[/hide]

[quote="kl2836"]1. 1984 #9: When $ x \equal{} \minus{} 1, ax^2 \plus{} bx \plus{} c \equal{} 6.$
                  When $ x \equal{} 7, ax^2 \plus{} bx \plus{} c \equal{} 6,$ and
                  When $ x \equal{} 1, ax^2 \plus{} bx \plus{} c \equal{} \minus{} 6$
                  Find the smallest value for $ ax^2 \plus{} bx \plus{} c$

2. 1985 #2: Point A has coordinates $ ( \minus{} 2,1)$. Point B is the image of A reflected in the line $ y \equal{} 3$. Point C is the image of B reflected in the line $ y \equal{} x \plus{} 3$. Point D is the image of C reflected in the line $ x \equal{} 0$. What is the distance between A and D?

3. 1985 #6: What is the perimeter of the region bounded by the inequalities?
   $ y > |x|$ and $ y < \minus{} |x| \plus{} 4$

Express your answer in simplest radical form.

4. 1987 #5: If $ A \equal{} {1,2,3}$ and $ B \equal{} {a,b,c,d}$ how many different functions are there that map A into B?

5. 1988 #4: Triangle ABC has vertices $ A(0,0), B(9,0), and C(9,40)$. The region enclosed by the triangle is rotated about the line $ x \equal{} 9$.  The solid generated by this rotation is then revolved about the y-axis. How many cubic units are in the volume of the solid generated by the second revolution? Express answer in terms of pi.

1. -10
2. 0
3. $ 8\sqrt {2}$
4. 64
5. 6480pi

ps. how do you type pi in latex?[/quote]

to type pi in LATEX:
[code]$\pi$[/code]

[hide="Hint for #5"]The solid generated by the first rotation is a cone with height 40 and radius 9.[/hide]

[hide="1"]
Substituting the values of $ x$ into the equation, we have
$ a \minus{} b \plus{} c \equal{} 6$
$ 49a \plus{} 7b \plus{} c \equal{} 6$
$ a \plus{} b \plus{} c \equal{} \minus{} 6$
Solving this system, we get
$ a \equal{} 1$
$ b \equal{} \minus{} 6$
$ c \equal{} \minus{} 1$
We are asked to find the smallest possible value of
$ x^2 \minus{} 6x \minus{} 1$
which would correspond to the y-value of the vertex of the parabola. The x-value would be
$ \frac { \minus{} b}{2a} \equal{} \frac{6}{2} \equal{} 3$
which makes the y-value
$ 3^2 \minus{} 6 \cdot 3 \minus{} 1 \equal{} \boxed{ \minus{} 10}$.
[/hide]

[hide="5"]
The hardest part seems to be realizing that the final revolution results in a cylinder, r = 9, h = 80.  I guess you ignore the inside triangles.
Volume = $ (\pi9^2)80 \equal{} 6480\pi$
[/hide]


superior algebra
superior algebra unsolved

How many undirected graphs are there in which every vertex has valency 2 (2-regular), where $ m$ the the number of vertices.

Thanks in Advance.

Don't double post. See [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=314722]here[/url].


The lines joining the incenter of a triangle to the vertices divide the triangle into three triangles. If one of these triangles is similar to the initial one,determine the angles of the triangle.

[hide="solution"]let $I$ be the incenter. without loss of generality, $\triangle IBC\sim\triangle ABC$ with $\angle IBC=\frac{B}{2}=C, \angle ICB=\frac{C}{2}=A, \angle BIC=90+\frac{A}{2}$ so after solving, the answer we get $A=\frac{2\cdot 90}{7}, B=\frac{5\cdot 90}{4},C=\frac{4\cdot 90}{7}$ and permutations. [/hide]

Those values don't add up to 180 degrees. :maybe:

[hide]I got the three angles being $\frac{180}{7}, \frac{2 \cdot 180}{7}, \frac{4 \cdot 180}{7}$ degrees. Then the triangle containing the second and third angles bisected has angles equal to the first and second angles of the original triangle, and we have AA similarity.[/hide]

Let $ I $ be the incenter with $ \angle IBC=\frac{B}{2},\angle ICB=\frac{C}{2},\angle BIC=A+\frac{B}{2}+\frac{C}{2}>A$ so WLOG $ \angle BIC = B$ so $ 2A + C = B$

So $\angle IBC=\frac{B}{2} = A + \frac{C}{2}>A$ thus $\angle IBC=C$ so $B=2C$ and so $2A+C=2C$ so the angles are $A$, $2A$ and $4A$ i.e. $\frac{180}{7}$, $\frac{360}{7}$ and $\frac{720}{7}$


[color=blue] [b] Problem.[/b]

    Let $a, b, c$ three positive real numbers. Prove that the following inequality holds true:

                            \[ \frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b}\geq\frac{2abc}{(a+b)(b+c)(c+a)}\cdot (\frac{b+c}{a}+\frac{c+a}{b}+\frac{a+b}{c}). \]

  [/color]

\[ \frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b}\geq\frac{2abc}{(a+b)(b+c)(c+a)}\cdot (\frac{b+c}{a}+\frac{c+a}{b}+\frac{a+b}{c}) \]
$\Leftrightarrow\sum(\frac{a}{b+c}-\frac{2bc}{(a+b)(a+c)})\ge 0$
$\Leftrightarrow \sum a^3+\sum(a^2b+a^2c)+3abc-2\sum(a^2b+a^2c)\ge 0$\[ \Leftrightarrow\sum a^3+3abc\ge \sum(a^2b+a^2c) \](Schur)

well, nameless, can u plz tell me how have u shrunk RHS in that little cyclic sum? is it trivial calculation by breaking and making the terms / is there any short cut?

Well, you observe that the RHS is an expression $P$ times a cyclic sum. Since $P$ is symmetric in $a,b,c$ (changing $a$ with $b$ gives the same $P$), we can put $P$ under the cyclic sum sign. That's all.

Is this what you were looking for?

well... i did not notice. he just made that into cyclic sum form. i am sorry to ask such stupid Q.

But anyway, in the next line (i mean 3rd one) how can he brought that simple expression instead of those fractional expressions? i mean is it by calculations/any ez way?


How many parallelograms can be drawn using the line segments of a triangular lattice of side length $ n$? For example, with $ n\equal{}2$, we can form only $ 3$ parallelograms, each composed of two unit equilateral triangles.

[hide]the 60 degree angle on the parallelograms may be pointed
1)
up/down
2)
left up/right down
3)
left down/right up

after we have dont that we can transform the usable equaleteral triangles and fuse them with the other equalateral triangle that it must be used with and we get a staircase and now our problem is :
how many rectangles may be formed from a staircase shape of side length n-1
times 3
which i... do not know how to solve
[hide=":D"]
this is for n=7
i will try to generalize it
so suppose the left bottom corner is at the left bottom corner of the triangle
if the height is 1, you can have 6 rectangles.
if the height is 2, you can have 5 rectangles... and so on
so 6+5+4+3+2+1=21
if the left bottom corner is 1 square away* from the bottom left corner, there are 15 (5+4+3+2+1) rectangles you can make (and there are 2 such corners possible)
if the bottom left corner is 2 squares away*, there are 10 (4+3+2+1) rectangles you can make with 3 possible corners
the pattern continues
and the total is $ 3 (1 \cdot \frac {(6)(7)}{2} + 2 \cdot \frac {(5)(6)}{2} + 3 \cdot \frac {(4)(5)}{2} \ldots + 6 \cdot \frac {(1)(2)}{2} )$
note that this means the number of 'steps' it takes to get to the bottom left corner. so any square on the opposite edge would be 5 squares away

now to generalize:
$ 3 \sum_{x = 1}^n x \cdot \frac {(n - x)(n - x + 1)}{2}$
which i do not know how to evaluate
[hide=":D"]
which equals $ 3 \sum_{x=1}^n \frac12x^3-\frac{2n+1}{2}x^2+\frac{n^2+n}{2}x = 3 ( \frac{n^2(n+1)^2}{8} + \frac{(2n+1)^2(n)(n+1)}{12}+\frac{n^2(n+1)^2}{4}  = \frac{(n-1)(n)(n+1)(n+2)}{8}$
okay im done with tricks
[/hide]

[hide]yes click the smiley again[/hide]
[/hide]

woot go paint
[hide]click the  :D[/hide][/hide]


let $ a,b,c \geq 0$ and $ a.b.c \equal{} 1$
    Prove that
       $ 18.(\frac {1}{a^3 \plus{} 1} \plus{} \frac {1}{b^3 \plus{} 1} \plus{} \frac {1}{c^3 \plus{} 1}) \leq (a \plus{} b \plus{} c)^3$

I'm not sure your problem is true, but I think the original problem must be:
$ \sum {\sqrt{\frac{1}{x^3\plus{}1}}}\leq\sqrt{\frac{(x\plus{}y\plus{}z)^3}{6}} (1)$
And your ideas to solve this problem is apply the inequality:$ (a\plus{}b\plus{}c)^2\leq 3(a^2\plus{}b^2\plus{}c^2)$,but i think you can't finish its.
Now I can help you. I will prove the above inequality.
(1)$ \Leftrightarrow\sum {\sqrt{\frac{y^3z^3}{y^3z^3\plus{}1}}}\leq\sqrt{\frac{(x\plus{}y\plus{}z)^3}{6}}$
$ \Leftrightarrow\sum {\sqrt{\frac{y^2z^2}{yz\plus{}1}}}\leq\sqrt{\frac{(x\plus{}y\plus{}z)^3}{6}}$
$ \Leftrightarrow\sum{\sqrt{yz\sqrt{yz}}}\leq\sqrt{\frac{(x\plus{}y\plus{}z)^3}{3}}$
$ LHS^2\leq (xy\plus{}yz\plus{}zx)(\sqrt{xy}\plus{}\sqrt{yz}\plus{}\sqrt{zx})\leq\frac{(x\plus{}y\plus{}z)^2}{3}(x\plus{}y\plus{}z)\equal{}\frac{(x\plus{}y\plus{}z)^3}{3}\equal{}RHS^2$
$ \Rightarrow LHS\leq RHS$
now we are done!

I think my problem is stronger than your problem

$ \Leftrightarrow\sum {\sqrt{\frac{y^2z^2}{yz\plus{}1}}}\leq\sqrt{\frac{(x\plus{}y\plus{}z)^3}{6}}$
              Why?

The following inequality with same conditions is true too:
\[ 27\left(\frac {1}{2a^3 \plus{} 1} \plus{} \frac {1}{2b^3 \plus{} 1} \plus{} \frac {1}{2c^3 \plus{} 1}\right) \leq (a \plus{} b \plus{} c)^3\]

Can you help me slove my problem . I think your problem is hard than my problem

[quote="thanhak5"]Can you help me slove my problem [/quote]
Of cause!

$ 18\left(\frac {1}{a^3 \plus{} 1} \plus{} \frac {1}{b^3 \plus{} 1} \plus{} \frac {1}{c^3 \plus{} 1}\right) \leq (a \plus{} b \plus{} c)^3\Leftrightarrow$
$ \Leftrightarrow(a \plus{} b \plus{} c)^3\geq18a^2b^2c^2\sum_{cyc}\frac {1}{a^3 \plus{} abc}\Leftrightarrow(a \plus{} b \plus{} c)^3\geq18abc\sum_{cyc}\frac {bc}{a^2 \plus{} bc}\Leftrightarrow$
$ \Leftrightarrow(a \plus{} b \plus{} c)^3 \minus{} 27abc\geq18abc\sum_{cyc}\left(\frac {bc}{a^2 \plus{} bc} \minus{} \frac {1}{2}\right)\Leftrightarrow$
$ \Leftrightarrow\sum_{cyc}(a^3 \plus{} 3a^2b \plus{} 3a^2c \minus{} 7abc)\geq9abc\sum_{cyc}\frac {bc \minus{} a^2}{a^2 \plus{} bc}\Leftrightarrow$
$ \Leftrightarrow\sum_{cyc}(2a^3 \plus{} 6a^2b \plus{} 6a^2c \minus{} 14abc)\geq9abc\sum_{cyc}\frac {2bc \minus{} 2a^2}{a^2 \plus{} bc}\Leftrightarrow$
$ \Leftrightarrow\sum_{cyc}(a \minus{} b)^2(a \plus{} b \plus{} 7c)\geq9abc\sum_{cyc}\frac {(c \minus{} a)(a \plus{} b) \minus{} (a \minus{} b)(a \plus{} c)}{a^2 \plus{} bc}\Leftrightarrow$
$ \Leftrightarrow\sum_{cyc}(a \minus{} b)^2(a \plus{} b \plus{} 7c)\geq9abc\sum_{cyc}\left(\frac {(a \minus{} b)(b \plus{} c)}{b^2 \plus{} ac} \minus{} \frac {(a \minus{} b)(a \plus{} c)}{a^2 \plus{} bc}\right)\Leftrightarrow$
$ \Leftrightarrow\sum_{cyc}(a \minus{} b)^2\left(a \plus{} b \plus{} 7c \minus{} \frac {9abc(ab \minus{} c^2)}{(a^2 \plus{} bc)(b^2 \plus{} ac)}\right)\geq0,$ which true because
$ a \plus{} b \plus{} 7c \minus{} \frac {9abc(ab \minus{} c^2)}{(a^2 \plus{} bc)(b^2 \plus{} ac)}\geq0$ is true.

If $ (a \plus{} b \plus{} c)^3\geq9(\alpha \plus{} 1)\sum_{cyc}\frac {1}{\alpha a^3 \plus{} 1}$ is true for all positive $ a,$ $ b$ and $ c$ such that $ abc \equal{} 1$
then $ \alpha\leq\frac {5 \plus{} \sqrt {33}}{4} \equal{} 2.6861...$
It seems that it's true for $ \alpha \equal{} \frac {5 \plus{} \sqrt {33}}{4}.$
By the way, it's true for $ \alpha \equal{} 2.5.$ :wink:


Renaissance faires are festivals where participants dress, talk and act as if they are living in the 1500s. The graph shows the number of days various faires run during their season. For example, three faires run for exactly 10 days. What is the total number of faires that run more than 14 days?

[asy]size(200,100);
real textsize = 10*pt;
real w = 1;
draw((0,7)--(0,0)--(26,0),linewidth(w));
for(int i = 1; i < 4; ++i)
	draw(shift(2i*up)*((0,0)--(26,0)));
for(int i = 0; i < 6; ++i)
	draw(shift(i*up)*((-.3,1)--(.3,1)),linewidth(w));
void bar(int barnumber,int height)
{filldraw((2barnumber - 1,0)--(2barnumber-1,height)--(2barnumber,height)--(2barnumber,0)--cycle,gray(.6),black+linewidth(w));
}
bar(1,3); bar(2,1); bar(3,3); bar(4,6); bar(5,4); bar(6,5); bar(7,4); bar(8,1); bar(9,2); bar(10,2); bar(11,2); bar(12,1);
label("\textbf{Length of Faire (Days)}",(13,-3),fontsize(textsize));
for(int i = 1; i<4; ++i)
{label("\textbf{"+string(5i+5)+"}",(10i -8.5,-1),fontsize(textsize));
label("\textbf{"+string(2i)+"}",(-1,2i),fontsize(textsize));}
label(rotate(90)*"\textbf{Number of}",(-4.3,7/2),fontsize(textsize));
label(rotate(90)*"\textbf{Faires}",(-3,7/2),fontsize(textsize));
label("\textbf{Duration of Renaissance Faires}",(13,9),fontsize(textsize));[/asy]

We just add up the numbers: $ 5 \plus{} 4 \plus{} 1 \plus{} 2 \plus{} 2 \plus{} 2 \plus{} 1 \equal{} 17$ total fairs. (Off topic, but Renaissance Fairs are fun. :) )


In ABC, AC<AB, and AD is the angle bisector of <BAC. Let E be the foot of the altitude frrom C to AD. Let a line parallel to AB through E intersect BC at F. Prove F is the midpoint of BC.

just see that if the line CE meets AB at H , then the triangle ACH is isosceles with leg AC=AH, therefore the altitude AE is also median ---> E is midpoint of HC and then the parallel through E to BH has to go through the midpoint of BC.


Resonance energy is again infact negative but in order to compare the stabilities we might take their modulus  :)

yes i second that read that today in BOLD letters from R.C.Mukherjee :D

Another question, I felt FIITJEE had paethed this.

Anyway It gets confusing when using the words "Greater Than", "Lesser than" with resonance and heat of combustion because -45 < - 23 mathematically but ppl say that you must compare only the mod...
I invariably get confused in all tests.

You must take the mod for comparison cases da  :D

EDIT: MY 1000TH POST  :D


algebra
polynomial
number theory proposed
number theory

$ n \ge 2$ and $ p$ be prime number. Then, prove or disprove that below polynomial is irreducible in $ Z[P(x)]$

$ P(x)\equal{}x^{n}\plus{}x^{n\minus{}1}\plus{}...\plus{}x\plus{}p$


trigonometry
logarithms
calculus
integration
calculus computations

[quote="amirhtlusa"]not sure for 6:
$x^{\sin{x}}(\cos{x}\ln{x}+\frac{\sin{x}}{x})$[/quote]

 :)  :)

what? 2 is wrong? i thing  $\frac{-\cos{(4x)}}{4}$ IS the correct answer...
8 typo
$\displaystyle \frac{1}{4(x+1)^2\sqrt[4]{(\frac{x}{x+1})^3}}$

[quote="amirhtlusa"]what? 2 is wrong? i thing  $\frac{-\cos{(4x)}}{4}$ IS the correct answer... :? you made intgeral
8 typo
$\displaystyle \frac{1}{4(x+1)^2\sqrt[4]{(\frac{x}{x+1})^3}}$ :) [/quote]

yeah, that's right,
too much "TODAYS INTEGRAL" lol :)

$4\cos{(4x)}$


which letter is 500th
aabbbccdddeefffgghhhiijjj...

what happens after we get to z?  Do we start over with a?

[hide]The 500th letter is R?

The pattern occurs in 2-3 patterns (OOXXX).  You know that the 500th letter will be the last letter in the 100th "sets" of 5 letters.

Since there are 26 letters in the alphabet, and each "set" has two letters, the set of "YYZZZ" would be the 13th set.  From this you know that all the sets having a multiple of 13 would be YYZZZ.  The multiple closest to 100 is 91.  This means that the 91th set is also YYZZZ.  There are 9 more sets to the 100th set.  Multiplying 2 (the number of letters in each set) by 9 states that the last letter in the 100th set will be the 18th letter, which is R.  [/hide]

Nevermind, it's not V...
The answer is the 18th alphabet...

lemme see...

abcdefghijklmnopqrstuvwxyz

Rrrrr
I think...
'R'


inequalities
induction
inequalities proposed

We have $a_{1}a_{2}...a_{n}=1$ therefor Q.E.D, because , we know that problem  :maybe:

[quote="Little Gauss"]To N.T.TUAN,
I think that is not enough.
If n=3, a+b+c<=1/a+1/b+1/c does not hold when (a,b,c)=(4,0.5,0.5)[/quote]

Yes, i am sorry  :oops:

Define $s_{k}: =b_{1}+b_{2}+...+b_{k}$. Then $s_{1}\le...\le s_{n}=: s_{0}$ and we can write the ineq as $\sum_{k=1}^{n}\frac{s_{k}}{s_{k-1}}\le \sum_{k=1}^{n}\frac{s_{k-1}}{s_{k}}$. This is certainly old & well known, anyway easy by induction:

It suffices to show that $\frac{s_{ n+1 }}{s_{ n}}+\frac{s_{ 1}}{s_{ n+1}}-\frac{s_{ 1}}{s_{ n}}\le \frac{s_{ n}}{s_{ n+1}}+\frac{s_{ n+1}}{s_{ 1}}-\frac{s_{ n}}{s_{ 1}}$, which is equivalent to $(s_{1}-s_{n})(s_{n}-s_{n+1})(s_{1}-s_{n+1})\le 0$.  :)

Are there direct sols without induction ??


I will take the Preliminary Round in the US Physics Selection team for the first time on January. Therefore, I really want to know what's the cut-off score for this round. Can anybody help me on this issue? By the way, do we need to learn Young's model for this round? I see that it showed up last year on the Preliminary Round. Any tips on how to do this round well is welcome!

You truly should not worry about this round.  Last year, no one who took the test (including me) knew the cutoff score, and I don't think it is ever released (or at least it hasn't been since the 2008 F=ma test).

To my knowledge, statistical data for the U.S. Physics Olympiad is never released.  I think it's all for the better - it prevents the rampant speculation and fretting that you find elsewhere on this forum regarding other contests.

Just look at last year's F=ma exam to get a feel for the format.  That should be more than enough, given that you have a solid understanding of basic mechanics.  Remember that last year, since the format of the exam was entirely new, it was effectively everyone's first time.

By the way, the problem involving Young's modulus on the 2008 exam really doesn't require prior knowledge of elastic moduli - it was merely a reasoning problem (you'll see what I mean if you read it carefully).


trigonometry
inequalities proposed
inequalities

Prove that:

(x-y)(x-z)+(y-x)(y-z)+(z-y)(z-x)$\geq$ sin(x-y)sin(x-z)+sin(y-x)sin(y-z)+sin(z-x)sin(z-y) ,$\forall$ x,y,z real numbers.

[quote="DINHHIEU@89"]consider x-y=a;y-z=b;z-x=c
a+b+c=0
ab+bc+ca>=sinasinb+sinbsinc+sincsina[/quote]
No,you are wrong.
It become $-(ab+bc+ca) \ge \sin a \sin b+\sin b \sin c+\sin c\sin a$
Which is equivalent to:
$a^{2}+b^{2}+c^{2}\ge 2(\sin a \sin b+\sin b \sin c+\sin c\sin a)$
But we have:
$2\sin a \sin b=\cos (a-b)-\cos (a+b)\le 1-\cos (a+b)=2\sin^{2}\frac{a+b}2 \le (\frac{a+b}2)^{2}$
Thus
\[2(\sin a \sin b+\sin b \sin c+\sin c\sin a) \le 2\left((\frac{a+b}2)^{2}+(\frac{b+c}2)^{2}++(\frac{c+a}2)^{2}\right) \]
The rest is left for you :)


Point $P$ is in triangle $ABC$, and area$APC$=area$APB$=area$BPC$.

Show that $P$ is the centroid.

See the attached diagram.

Let $CP$ meet $AB$ at $Q$, let $CC_{1}$ be the altitude and let $PT\perp CC_{1}$. From $[APB]={1\over 3}[ACB]$ it follows $TC_{1}={1\over 3}CC_{1}$, hence by Thales $PQ={1\over 3}CQ$.

Extend $CQ$ to $R$ such that $QR=QP$. Then $PR=PC$, which gives

\begin{eqnarray*}[BPR]=[BPC]=[BPA]\implies [APQ]+[BPQ]=[BRQ]+[BPQ]\implies [APQ]=[BRQ]\end{eqnarray*}.

Since $PQ=QR$ and $\angle PQA=\angle BQR$, that gives $AQ=QB$, hence $CQ$ is the median. By extension, $P$ lies on all three medians, ergo is the centroid.

attempting a shorter version:
[hide]
draw $CP$ and let it intersect $AB$ at $Q$.  Since $[APB] = [APC] = [BPC]$, we have $[ABC] = 3[APB]$.  Therefore, by the common base theorem (I think so...), $\frac{CQ}{PQ}= 3$ implying that $2PQ = CP$.

Now consider $\frac{[ACP]}{[APQ]}$, since the base has a two-to -one ratio and they share a common height, $[APQ]$ is half of $[APC]$.  Similarly with $[BPQ]$.  Since $[APC] = [BPC]$, we must have $[APQ] = [BPQ]$, implying that $Q$ is the midpoint.

Apply this argument for two more times on the two other triangle we clearly see that $P$ is the centroid.  Yay!!
[/hide]

[quote="Franz Joseph"]Just wondering, weren't there $4$ points with this property? $1$ inside the triangle (being the centroid) and $3$ outside the triangle.[/quote]

Yeah, I'd think so... but I said $P$ is in the triangle  :)


function
linear algebra
matrix
induction
algebra unsolved
algebra

$ xy \equal{} x \plus{} y \Leftrightarrow (x \minus{} 1)(y \minus{} 1) \equal{} 1 \Leftrightarrow y \equal{} \frac{1}{x \minus{} 1} \plus{} 1 \equal{} \frac{x}{x \minus{} 1} \equal{} g(x)$.  Then the problem reduces to finding functions such that $ f(g(x)) \equal{} g(f(x))$, in other words, functions that commute with the Mobius transformation $ g(x)$.  The obvious candidate here is other Mobius transformations, but I am out of time.

The group of invertible Mobius transformations $ \frac{ax \plus{} b}{cx \plus{} d}$ is isomorphic to the [url=http://en.wikipedia.org/wiki/Projective_special_linear_group]projective linear group[/url], so the question of finding a Mobius transformation that commutes with $ g(x)$ is the question of finding a matrix that commutes with $ \left[ \begin{array}{cc} 1 & 0 \\ 1 & \minus{}1 \end{array} \right]$ (the matrix corresponding to $ \frac{x}{x \minus{} 1}$.  The set of such transformations is given by $ f(x) \equal{} \frac{(2c \plus{} d) x}{cx \plus{} d}$, but upon inspection it appears that only the identity transformation $ f(x) \equal{} x$ ($ c \equal{} 0, d \equal{} 1$) actually solves the original functional equation.  So I am out of ideas.

[quote="math man"]Find all function f:R-->R such that:
f(x+y)+f(x).f(y)=f(x.y)+f(x)+f(y)[/quote]
By induction mathematical we can easily prove that if h(x) isn't equal 2 or 0 then f(x)=x every x is ration.
then prove g(x) is monocal fuction

You can read in " Bài toán hàm số qua các kì thi olimpic" thân
Sorry about my English

The problem in this topic is a reduced version of the one [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=205785]here[/url], with the only difference being $ f(f(x)) \equal{} x$ an additional constraint. I used a rationals/monotonicity argument to finish it from that point, though better solutions were posted.


function
algebra
rational function
real analysis
real analysis theorems

For the alternating series test's conclusion, that the series a(subscript n) = (-1)^n b(subscript n) is conditionally convergent, to hold true, then there must be two conditions met: The series of b(subscript n) must be decreasing and that it must approach 0.
Why is it necessary to prove that the series is decreasing? After all, doesn't showing that it approaches 0 imply that it's decreasing? There's no way that it can approach 0 without decreasing or staying at 0, in which, case, it'll be convergent anyways.

Sure, maybe the whole series is negative, in which case it would be increasing to 0, but then you can just change (-1)^n to (-1)^(n+1).

Consider the following series:
$ 1\minus{}\frac12\plus{}\frac12\minus{}\frac14\plus{}\frac13\minus{}\frac16\plus{}\frac14\minus{}\frac18\plus{}\cdots$

Woah...
Is it possible to define that as a function other than a piecewise function or something? Or does the series b_n not have to be described as a function?

[quote="pascal12"]does the series b_n not have to be described as a function?[/quote]
The fact that you understood how to extrapolate what jmerry wrote down to any given term means that it [b]is[/b] a function.  Functions are not formulas, and the behavior of a function is not dictated by any particular method you have of writing it down.

Edit:  For what it's worth, $ b_n$ is a rational function of $ n$ and $ (\minus{}1)^n$.

Ahh, I understand:

Edit: Am I working too hard? The odd terms can be defined by 1/n while the even terms -1/(2n), so if you combine it, it reduces to 1/n, doesn't it? Which isn't really an alternating series...

By combining terms, you have defined a new series. That's the way to show that it doesn't converge, but it doesn't make the original series "not really" anything.

And note that by that logic, no series is "really an alternating series."

Actually, that's not quite true.  Hmm.  Can anyone come up with an example of an alternating series $ a_n$ with the property that $ a_{2n} \plus{} a_{2n\plus{}1}$ is still an alternating series, $ a_{4n} \plus{} a_{4n\plus{}1} \plus{} a_{4n\plus{}2} \plus{} a_{4n\plus{}3}$ is still an alternating series, and so forth?

Yes: for $ i \geq 0$ even, let $ a_{2i \plus{} 1} \equal{} a_{i \plus{} 1}$ and $ a_{2i \plus{} 2} \equal{} \frac {a_{i \plus{} 1}}{2}$, while for $ i$ odd let $ a_{2i \plus{} 1} \equal{} \frac {a_{i \plus{} 1}}{2}$ and $ a_{2i \plus{} 2} \equal{} a_{i \plus{} 1}$.  Taking $ a_1 \equal{} 1$ and adding signs, we get
\[ 1 \minus{} \frac {1}{2} \plus{} \frac {1}{4} \minus{} \frac {1}{2} \plus{} \frac {1}{4} \minus{} \frac {1}{8} \plus{} \frac {1}{4} \minus{} \frac {1}{2} \plus{} \frac {1}{4} \minus{} \frac {1}{8} \plus{} \frac {1}{16} \minus{} \frac {1}{8} \plus{} \ldots.
\]
Summing pairs of elements converts this to
\[ \frac {1}{2} \minus{} \frac {1}{4} \plus{} \frac {1}{8} \minus{} \frac {1}{4} \plus{} \frac {1}{8} \minus{} \frac {1}{16} \plus{} \ldots,
\]
which is exactly one-half what we started with.  (Should be possible to write a closed form for the sequence, right?)

Edit: Yes, here's the closed form: $ a_{i \plus{} 1} \equal{} 2^{ \minus{} s(i)}$ where $ s(i)$ is the number of runs in the binary expansion of $ i$ -- this is [url=http://www.research.att.com/~njas/sequences/A005811]A005811[/url] in the [url=http://www.research.att.com/~njas/sequences]OEIS[/url] and is essentially obvious from the recursive description.

Note that this series doesn't converge by the $ n$th term test: we have $ a_{2^n} \equal{} \frac {1}{2}$ for all $ n \geq 1$ from either the closed form or the recursive description.  Is there such a series that [i]does[/i] converge?


a,b,c,d>0 so:

$ 2 \sqrt [4]{(a \plus{} b)(b \plus{} c)(d \plus{} c)(a \plus{} c)} \ge ( \sqrt {ab} \plus{} \sqrt {bc} \plus{} \sqrt {dc} \plus{} \sqrt {ad})$

and:

$ 3 \sqrt[3]{(c\plus{}ab)(c\plus{}d)(ab\plus{}d)} \ge 2 ( \sqrt{abc} \plus{} \sqrt{abd}\plus{} \sqrt{cd})$

[quote="jin thynj"]a,b,c,d>0 so:

$ 2 \sqrt [4]{(a \plus{} b)(b \plus{} c)(d \plus{} c)(a \plus{} c)} \ge ( \sqrt {ab} \plus{} \sqrt {bc} \plus{} \sqrt {dc} \plus{} \sqrt {ad})$

[/quote]
Try $ c\equal{}d\rightarrow0^\plus{}.$ :wink:

i got it on a old book, so the first is wrong (as my solution)  :mad:
but in the second this idea doesn't work anyone?


How many degrees are in an angle whose measure is $ \frac23$ of its complement?

Let $ d$ = the degree measure of the angle. We can set up an equation. $ d \equal{} \frac{2(90 \minus{} d)}{3}$. Clearing the denominator, we have $ 3d \equal{} 180 \minus{} 2d \Rightarrow 5d \equal{} 180 \Rightarrow d \equal{} \boxed{36}$. If we wanted to check, it would be $ 36 \equal{} \frac{2(54)}{3}$ which is true.


advanced fields
advanced fields unsolved

What's an example of schemes $ X,Y,Z$ and morphisms $ X \rightarrow Z$ and $ Y \rightarrow Z$ such that there are two elements $ \alpha, \beta \in X \times_{Z} Y$ that agree on each of the projections $ p_1 : X \times_{Z} Y \rightarrow X \rightarrow Z$ and $ p_2 : X \times_{Z} Y \rightarrow Y \rightarrow Z$ but are NOT equal?

Clearly if there's a field $ K$ containing both $ k(\alpha), k(\beta)$ then by universal property $ \alpha \equal{} \beta$.  It's also clear that $ \alpha \equal{} \beta$ if instead of schemes $ X,Y,Z$ are varieties, say.

But Hartshorne says that something weird like this CAN happen if $ X,Y,Z$ are schemes.

I think you mean $ p_1 : X \times_Z Y \to X$ (instead of $ \to Z$). in other words, you look for an example where $ |X \times_Z Y| \to |X| \times_{|Z|} |Y|$ is not injective. take $ X\equal{}Y\equal{}Spec(\mathbb{C})$ and $ Z\equal{}Spec(\mathbb{R})$. then $ X \times_Z Y$ is the spectrum of $ \mathbb{C} \otimes_{\mathbb{R}} \mathbb{C} \cong \mathbb{C} \times \mathbb{C}$, thus $ |X \times_Z Y|$ has two elements but $ |X| \times_{|Z|} |Y|$ has only one.

Hello,

I didn't think it would make sense to say $ p_1(\alpha) \equal{} p_2(\beta)$ since they lie in different schemes ($ X$ and $ Y$).  Anyway, you answered my question perfectly.

Thank you!


induction
combinatorics unsolved
combinatorics

For $ n \in \mathbb{N}$ , $ n \geq 1$ , let $ a_n$ be the total numbers of ways we can pave an $ 1 \times n$ alley with $ 1 \times 1$ rocks of $ 5$ different colors , such that every consecutive sequence of $ 3$ rocks has at least $ 2$ rocks of the same colour .
Find $ a_n$ .

[hide="Answer :"] $ a_n \equal{} \frac {5}{2} \left(3^n \plus{} ( \minus{} 1)^n \right)$ . The answer helps if somebody find a solution using mathematical induction (i think) .   [/hide]

We get a pair of entangled recursive relations. Hope somebody can arrive at the closed form.

Equivalently, we construct a sequence of length $ n$ containing $ 1,2,3,4,5$ with no three consecutive terms all being different. We can add the $ n\plus{}1$ th term to a $ n$ length sequence to obtain the $ n\plus{}1$ length sequence and we get all the possible $ n\plus{}1$ length sequences.

Let $ f(n)$ be the number of $ n$ length sequences with last two terms being same.
Let $ g(n)$ be the number of $ n$ length sequences with last two terms being different.

Let $ F(n)$ denote the number of $ n$ length sequences.
Hence, $ F(n)\equal{}f(n)\plus{}g(n)$

We obtain the recursive relations,

$ f(n\plus{}1)\equal{}f(n)\plus{}g(n)$

$ g(n\plus{}1)\equal{}4f(n) \plus{} g(n)$

with initial conditions: $ f(3)\equal{}20,g(3)\equal{}100$

[quote="I hate rating"]with initial conditions: $ f(3) \equal{} 20,g(3) \equal{} 100$[/quote] should be $ f(3) \equal{} 25, g(3) \equal{} 40$ (or  $ f(2) \equal{} 5, g(2) \equal{} 20$, or even $ f(1) \equal{} 5, g(1) \equal{} 0$).

Solving a system like this is not too bad: solving the first equation for $ g(n)$ and substituting into the second gives $ f(n \plus{} 2) \minus{} f(n \plus{} 1) \equal{} 4f(n) \plus{} f(n \plus{} 1) \minus{} f(n)$, so $ f(n \plus{} 2) \minus{} 2f(n \plus{} 1) \minus{} 3f(n) \equal{} 0$.  Now this is just a standard problem for the method of characteristics -- our two associated roots are $ 3, \minus{} 1$, so $ f(n) \equal{} a3^n \plus{} b( \minus{} 1)^n$; we have two initial values to use, and we have $ F(n) \equal{} f(n \plus{} 1)$ to finish us off.


Euler
function
number theory
totient function
relatively prime
advanced fields
advanced fields unsolved

I am sure people have studied the properties of this function, but I couldn't find anything about the particular questions I was wondering about, so I'd be delighted if someone could give me some references or (even better) an answer + proof for either of the following questions.

Recall the totient function $ \phi(n)$ is the number of integers in $ \{1, 2, \ldots, n\}$ which are relatively prime to $ n$.

Consider the inverse $ \phi^{-1}(n)$. Of course, this is not well-defined: for all odd numbers other than 1, there's no inverse, and there are usually lots of values of the inverse (especially if $ n$ has many prime factors). So let $ \phi^{-1}(n)$ be the largest inverse, if one exists, and 0 if there aren't any.  Now it's well-defined.

(1) What is the asymptotic behavior of $ \sup_{k \le n}\phi^{-1}(k)$ as $ n \to \infty$?

(2) What is the asymptotic behavior of $ \#\{k : k \text{ is even, }\phi^{-1}(k) = 0, k \le n\}$ as $ n \to \infty$?

The OEIS doesn't have asymptotics for either sequence.

The sequence of largest inverses is http://www.research.att.com/~njas/sequences/A006511 .

The even values omitted in the sequence $ \{\phi(n)\}_{n \in{\bf Z}_{> 0}}$ are http://www.research.att.com/~njas/sequences/A005277 .

[quote="Xevarion"](1) What is the asymptotic behavior of $ \sup_{k \le n}\phi^{-1}(k)$ as $ n \to \infty$? [/quote]

Well, it's clear what the number will be. What's unclear is how to estimate it! I mean, you just want to choose numbers $ n$ with a lot of small prime factors so that you can use every prime. Like for example $ 1 \cdot 2 \cdot 4 \cdot 6 \cdot 10 \cdot 12 \cdot 16$ will have $ 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17$ as its inverse. But then we are looking at

$ \prod_{p}\frac{p}{p-1}$

That doesn't converge, does it? But it seems like estimates of its growth would follow easily from estimates of the growth of $ \sum \frac{1}{p}$ which is a more famous problem... ;)


calculus
derivative
trigonometry
limit
calculus computations

this problem was in a course prep book for AP calc:

Suppose the derivative of f at x=2 is 5.  which of the following must be true.

1)f is continuous at x = 2.

2)f is differentiable at x = 2.

3)The derivative of f is continuous at x = 2.

One and two are correct, of course, however the answer book states that #3 is false.  I can understand that answer by saying that since we only have one point on the derivative, we cannot verify continuity, however I can’t think of an example where the derivative WOULDN’T be continuous.  Can you think of one?

Here's the classic example:

Let $g(x)=\begin{cases}x^{2}\sin\left(\frac1x\right)&x\ne0\\0&x=0 \end{cases}.$

Then $g'(0)=0.$ To see this, go to the raw definition of derivative:

$g'(0)=\lim_{h\to0}\frac{g(h)-g(0)}{h}= \lim_{h\to0}h\sin\left(\frac1h\right)$

This is trapped between $-|h|$ and $|h|$ and thus by the Squeeze Theorem, has zero as it limit.

But for $x\ne0,\ g'(x)=2x\sin\left(\frac1x\right)-\cos\left(\frac1x\right)$

$\lim_{x\to0}g'(x)$ does not exist. (It's the second term, the one without the $x$ out front, that causes the trouble.) Hence $g'$ is not continuous at $0.$

To adapt this example to your situation, just let $f(x)=g(x-2)+5x.$

You could also do this:

Let $g(x)=\begin{cases}x^{2},&x\text{ rational}\\0,&x\text{ irrational}\end{cases}$

Then $g'(0)=0$ but the derivative only exists at that one point.


P,Q,R,S are polynomials such that

 P(x^5) + x*Q(x^5) + (x^2)*R(x^5) = (1 + x + x^2 + x^3 + x^4) * S(x) for all x.

Prove that x-1 is a factor of P(x).

[hide]

the RHS hints at plugging in the complex fifth roots of unity, because if $w$ is a complex fifth root of unity, then $1+w+w^2+w^3+w^4$=0.

[/hide]

[hide]

plugging in $w, w^2, w^3, w^4$ respectively gives

$P(1)+wQ(1)+w^2R(1)=0$ (i)

$P(1)+w^2Q(1)+w^4R(1)=0$ (ii)

$P(1)+w^3+Q(1)+wR(1)=0$ (iii)

$P(1)+w^4Q(1)+w^3R(1)=0$ (iv)

It looks like if we add those we can almost use the identity $1+w+w^2+w^3+w^4=0$ to cancel out the Q(1) and R(1)'s... but that doesnt look too easy, instead we'll try to do it on P(1).  Notice that if we multiply (i) by $-w$, (ii) by $-w^2$, (iii) by $-w^3$, (iv) by $-w^4$,  we have

$-wP(1)-w^2Q(1)-w^3R(1)=0$ (i')
$-w^2P(1)-w^4Q(1)-wR(1)=0$ (ii')
$-w^3P(1)-wQ(1)-w^4R(1)=0$ (iii')
$-w^4P(1)-w^3Q(1)-w^2R(1)=0$ (iv')

if we add all 8 equations we see that the Q(1)'s and R(1)'s cancel, and we're left with $4P(1)-P(1)[w+w^2+w^3+w^4]$=0, which means $5P(1)-P(1)[1+w+w^2+w^3+w^4]$=0.  Using the identity mentioned before, this implies that $P(1)=0$.
[/hide]

wait how did you figure it out that the fifth root of unity was in solving this problem?

how did i think to use them?  when you see things like $1+x+x^2+...+x^{n-1}$, you think complex n'th roots of unity because that factors as $1(x^n-1) / (x-1)$.  Also since our goal is to show that $P(1)=0$, plugging in the complex 5th roots of unity makes the RHS 0 which helps us towards our goal.

What are roots of unity and complex roots of unity?

an example is x^3=-1. The obvious solution is -1. but there are 2 others (which involve complex numbers)


prove that in triangle $ ABC$ we have:

\[ S\equal{}\frac{a^2 \sin B \sin C}{2 \sin A}\equal{}\frac{b^2 \sin A \sin C}{\sin B }\equal{}\frac{c^2 \sin B \sin A}{\sin C}\]

We can easily prove that in triangle $ ABC$ these relations are true:

\[ S\equal{}\frac{ab \cdot \sin \gamma}{2}\equal{}\frac{bc \cdot \sin \alpha}{2}\equal{}\frac{ac \cdot \sin \beta}{2} \ ... (*)\]

By [b]Law Of Sine[/b] we obtain :
\[ a\equal{}\frac{\sin \alpha}{\sin \beta} \cdot b\]
\[ b\equal{}\frac{\sin \beta}{\sin \gamma}\cdot c\]
\[ c\equal{}\frac{\sin \gamma}{\sin \alpha}\cdot a\]

substitute these formulas to $ (*)$ , than the conclusion follows.  :)


calculus
integration
logarithms
trigonometry
limit
calculus computations

I already have a solution to this, but I'd like to alternatives. Calculate
\[ \int_0^{\pi/2}\ln(\sin x)dx  \]

I think the following formula may help you :) :
$\prod_{i=1}^{n-1}\sin \frac{i\pi} {n}=\frac n{2^n-1}$
which can proved by complex number.
I knew there must have some other solution.
And what about your solution?

My solution is that by rewriting the integral a few times you can show that $\int_0^{\pi/2}\ln(\sin x)dx = 2\int_0^{\pi/2}\ln(\sin x)dx + \frac{\pi\ln 2}{2}$, and from that it's trivial.

How do you use your solution? I don't know anything about complex analysis. This was on an exam... I solved it like this, but I feel that I was just lucky that you could use my solution. Doesn't seem like that would generally work, which is why I want to learn more general methods.

This is a tough integral. I seen this way back in college and dug out the old papers.
I hope you can follow it. Hope this helps.

$\begin{array}{l} \int\limits_0^{{\textstyle{\pi \over 2}}} {\ln (\sin (x))dx}\\ \sin (x) = 2\sin ({\textstyle{x \over 2}})\cos ({\textstyle{x \over 2}})\\ W = \int\limits_0^{{\textstyle{\pi \over 2}}} {\ln (2\sin ({\textstyle{x \over 2}})\cos ({\textstyle{x \over 2}}))dx} \\ = \int\limits_0^{{\textstyle{\pi \over 2}}} {\ln (2)dx + \int\limits_0^{{\textstyle{\pi \over 2}}} {\ln (\sin ({\textstyle{x \over 2}}))dx + \int\limits_0^{{\textstyle{\pi \over 2}}} {\ln (\cos ({\textstyle{x \over 2}}))dx} } } \\ \theta = {\textstyle{x \over 2}} \\ W = {\textstyle{\pi \over 2}}\ln (2) + 2\int\limits_0^{{\textstyle{\pi \over 4}}} {\ln (\sin (\theta ))d\theta + 2\int\limits_0^{{\textstyle{\pi \over 4}}} {\ln (\cos (\theta ))d\theta } } \\ \cos (\theta ) = \sin ({\textstyle{\pi \over 2}} - \theta ) \\ \alpha = {\textstyle{\pi \over 2}} - \theta \\ \int\limits_0^{{\textstyle{\pi \over 4}}} {\ln (\cos (\theta ))d\theta } = - \int\limits_{{\textstyle{\pi \over 2}}}^{{\textstyle{\pi \over 2}}} {\ln (\sin (\alpha ))d\alpha = \int\limits_{{\textstyle{\pi \over 4}}}^{{\textstyle{\pi \over 2}}} {\ln (\sin (\alpha ))d\alpha } } \\ W = {\textstyle{\pi \over 2}}\ln (2) + 2\int\limits_0^{{\textstyle{\pi \over 4}}} {\ln (\sin (\theta ))d\theta + 2\int\limits_{{\textstyle{\pi \over 4}}}^{{\textstyle{\pi \over 2}}} {\ln (\sin (\alpha ))d\alpha } } \\ = {\textstyle{\pi \over 2}}\ln (2) + 2\int\limits_{}^{} {\ln (\sin (x))dx = {\textstyle{\pi \over 2}}} \ln (2) + 2W \\ W = - {\textstyle{\pi \over 2}}\ln (2) \\ \end{array}$

ok,I recall your solution is the solution in my course ;)
and sorry,I think that my formula may doesn't work(because $\lim \ln \sin 0=-\infty$)
sorry again :)

Kalle, did you use the same procedure as fredoniahead in solving this problem?


just yes or no  :lol:

and.... which was your favorite?

Obviously, the Upstate New York's "My Favorite Theorems" was the best.

well I'm not going to say anything about the songs. They were generally ok...

The thing that really annoyed me at the song contest was that the winners were based on clapping.... so it was unfair... they should change it to who had the best song...

eh the only people that were actually clapping for the aast team were the people from aast...except aast made up like 1/8 of everyone there and they were clapping pretty loud

well... yeah. AAST brought... 8 teams i think.
I was sitting right next to them (refusing to clap) and they [i]were [/i]pretty loud. If ASST had only one or two teams they probably would not have won.

lol asst that would be a more fitting name
i don't really see the point of them sending 8 teams...i mean their theta team got a total score of like 13 (like 4 team, 0 relay, 1 power, 8 individual), it's a little bit of a waste of money at that point.

I just remember that at the song contest one group was really far from the microphone and so couldn't be heard, while another group was extremely off from the rhythm. (but recovered...or maybe it was intended?)

they should just rename the teams to lkie

AAST GOOD
AAST MEDIOCRE
AAST FUN
AAST CULT
AAST RANDOM
AAST FRESHMEN
AAST BAD
AAST CLAPPERS

But we already discussed Penn State (and the lack at Iowa) in here: http://www.artofproblemsolving.com/Forum/viewtopic.php?t=152367
It should probably just be renamed to Song Contests

Greetings Everyone,

It is nice to see that you all have your opinions on both AAST's performance and on AAST's choice to bring eight teams.  I will not argue with anyone in this topic but will instead, as the songwriter, choreographer, and lead singer/dancer for AAST, give my advice to future performers in the hope that they will do even better than I did!  You'll probably notice that the advice I give is something that I myself did not know and is what led to many of the problems at the final performance:

(1)  The stage at ARML has no electrical connection at all.  Usually one might expect that a freestanding podium would have an outlet for a projector or something of that sort... but not at ARML.
(2)  The echo on the stage is ENORMOUS and it quickly becomes impossible to choreograph anything along with the music because the sound returns heavily diluted with a small delay
(3)  The stage is hollow so stepping on it makes noise that is picked up over the microphones (and the space is really small considering the podium in the way).
(4)  There are only two microphones which are tedious to carry (or impossible to carry if you have choreography) and which have a very strange range in which they pick up sound (as in they have to be held at almost an exact distance away from you in order to guarantee perfect sound... usually they're annoyingly loud or painfully soft.
(5)  The tryouts the night before are just awful... no one knows where they are held or when and no attempt to prepare you for the actual scenario when you walk on stage is made.
(6)  I hope this helps anyone interested in future song contests... it's not impossible but it requires proper preparation.  Feel free to send any further question to me at maree275@yahoo.com

As a side note, many people, especially Ignite168 and LeetSpeak, seemed to be mad at our bringing 8 teams.  Let me say just to things about that.  Firstly, it is our believe, as it is the belief of most mathematicians, that Mathematics is about the process of learning and that any experience is beneficial.  On the other hand, doing well in a competition means very little.  Why, then, should we deny people the chance to enjoy mathematics?  Everyone pays for themselves with a little help from Math team fundraisers so it's no waste of money but actually an amazing opportunity.  I would dare-say that it's people like you that make math so inaccessible to anyone who might enjoy it and not be good at it, necessarily.  Our Theta team was composed entirely of Middle Schoolers.  I would appreciate if you removed your insulting posts... thank you!

Lyrics
For anyone interested in my lyrics:
(Sung (strictly) to the tune of Bad Day by Daniel Powter)

Where is the theorem you needed the most?
You pick up the pen but the idea is lost?
They tell you that ARML's moved to May
But your best teammate moved away
and we won't get no place at all...

You look at the time but you're solvin' too slow
You were caught unaware when the proctor said go
Showin' a point was on a line
You got it in practice every time
and we won't get no place at all...

Because you wrote a bad proof
You're 20 points down
You wanna go to Harvard but they turned you around
Your team, they don't know
You tried to factor Pi
You're feelin' really down like an Angle Side Side
You wrote a bad proof
Graders don't lie
Your coach he just frowns and you feel like you'll die
You wrote a bad proof...
You wrote a bad proof.

So where is the person you needed the most?
Oh, my friend and I,
We stayed up all night 'till the problem was solved...

Because you wrote a bad proof
You're 20 points down
You wanna go to Harvard but they turned you around
Your team, they don't know
You tried to factor Pi
You're feelin' really down like an Angle Side Side
You wrote a bad proof
Graders don't lie
Your coach he just frowns and you feel like you'll die
You wrote a bad proof...
You wrote a bad proof!

People are indignant not because you brought 8 teams - bringing more people to math contests is good! - but that those 8 teams gave AAST an unfair advantage; you probably could not have won without your 8 teams. That's 120 people. Especially considering that many didn't clap at all, this heightened AAST's advantage.

[quote="MysticTerminator"][quote="marvel"]
(5)  The tryouts the night before are just awful... no one knows where they are held or when and no attempt to prepare you for the actual scenario when you walk on stage is made.[/quote]

uhh they're at findlay commons the night before[/quote]

Yeah... I know... but they didn't start on time and no one was quite sure where within findlay commons they were.  The more important fact is that they didn't prepare teams for anything near the scenario they would face on the actual ARML stage... at least they could have chosen a better place for the tryouts...

As a side note, many of the people from AAST cheered for our song not out of "school pride" but because they had already seen our song performed without mistakes and thought highly of it.  Had you seen our song performed correctly I'm sure you would have been less skeptical, too!
(Although I certainly understand where you're coming from)  :)

[quote="marvel"]
Yeah... I know... but they didn't start on time and no one was quite sure where within findlay commons they were.  The more important fact is that they didn't prepare teams for anything near the scenario they would face on the actual ARML stage... at least they could have chosen a better place for the tryouts...

As a side note, many of the people from AAST cheered for our song not out of "school pride" but because they had already seen our song performed without mistakes and thought highly of it.  Had you seen our song performed correctly I'm sure you would have been less skeptical, too!
(Although I certainly understand where you're coming from)  :)[/quote]

We cheered for AAST just because we didn't like the others.  :)

Not to sound like an idiot, but what does AAST stand for?

Academy for the Advancement of Science and Technology, or some such.  It's part of [url=http://bcts.bergen.org/index.php?option=com_multilink&Itemid=1353]Bergen County Academies[/url].

Ok... sorry for reviving something 5 months old... but

I don't like all this about AAST.

Seriously, they had the best song.

If you seriously liked New York's Favourite Theorems thing,

All I can say is that it appeared that they were struggling,

and you couldn't understand a thing they were saying.

And the other one was just stupid.

Sorry if you are from NY or wherever the other team was from...

but seriously. If you listen, and judge it fairly, who would you

really pick?

Anyway, yes, I was on AAST last year... And I sorta clapped

because I was supposed to... I was 10 ok?

Anyway, "Bad Day" is a great song in my opinion and I think

they executed it well.

To respond to BOGTRO's comments:

Upstate NY's Favorite Theorems was weak because we decided to perform about half an hour before the contest.  We had no rehearsal, and most of the team had never seen the lyrics before.  It was more of a "hey, let's do the song contest!" thing than something we actually worked on.  While I liked our song a lot (from the unbiased position of the person who wrote a lot of the lyrics :lol: ), in terms of musicality and performance we were definitely not the best.

However, AAST had difficulties in the finals.  I don't remember hearing them during the first round, and in the finals I couldn't hear a word they were saying.  I am not saying that their song was bad, but the finals performance was a bit less than perfect, as marvel has said.  Whether or not their song was good (I did like the lyrics from reading them), their performance in the finals had technical difficulties, which really made it hard for people to enjoy.  That's why I would have preferred to see a different team win than AAST.

Of course I don't mean to offend BOGTRO, marvel, or anyone else involved.  And there's nothing wrong with bringing 8 teams, but because AAST had 8 teams the song contest should be based on something besides clapping.

I thought it was a good concept.  However, I could barely hear it.  I guess the sound system used for the ARML song contest leaves quite a bit to be desired... but hey, it's a pretty cool thing.

Well, the ARML stage is a gym, which isn't meant for a singing

preformance. But, based on the song, who would you pick?

And if New York did do that, then that's really just an excuse.

If you weren't the best, I doesn't matter how much practice time

you had.

The if you really wanted that other song to win, which was

so forgettable and bad that I almost left in the middle,

I truly doubt your sanity.

I wouldn't have picked AAST because I couldn't hear them.  Does that mean I'm insane?

Well, the problem is that nobody

really could hear AAST's song at all

which is why most of us were rather surprised

when they won. And proceeded

to attribute the victory to the clearly biased teams

which I think is not unlikely.  If you think

that we should have voted for a song

that we couldn't even hear, then

I truly doubt your sanity.

EDIT: TimReyn! You screwed up the placement of my poem :wink:

So, I won't be going to ARML this year, but I went last year and talked with some AAST members at the princeton competition earlier this year. They are aware of the massive rigging ;).


function
integration
advanced fields
advanced fields unsolved

Let $ h(t,x)$ be a function from $ \mathbb{R}^2$ to $ \mathbb{R}$  such that $ \frac {\partial h(t,x)}{\partial t}$ and $ \frac {\partial h(t,x)}{\partial x}$ are bounded and $ h(t,x) < h(t,y)$ whenever $ x < y$.

Let $ \phi: [0,\infty) \rightarrow \mathbb{R}$ be a continuous function satisfying
\[ \phi (t) \leq \int_{0}^{t} h(s,\phi(s)) ds,\]
Let $ \psi(t)$ be the unique solution of the initial value problem
\[ \dot{x} \equal{} h(t,x)\]

\[ x(0) \equal{} 0\]
Show that
\[ \phi(t) \leq \psi(t).\]