counting
derangement
function
search
combinatorics proposed
combinatorics

I need to count the number of derangment but for arbitrary number of sets.

for example :

1                         2                      3
2                         3                      2
3                         1                      1

Original Order      Derangment 1   Derangment 2

The extension is that Derangment 2 is derangment of original order and Derangment 1 .

In this example we have only 1 such possibility . If anyone know how to formulate a genral formula for n rows and m groups ?

I don't understand.  Can you express what you're looking for in terms of conditions on a function?

Read the columns instead of rows..

I guess what they are looking for is the number of matrices in which each element appears exactly once in each row, and once in each column.

Except that the written table doesn't satisfy that property.   :maybe:

If Aryabhatta is correct, the key word is "Latin Square" and the internet will have lots of information available for you (e.g., in the [url=http://www.research.att.com/~njas/sequences/index.html?q=Latin+Square&language=english&go=Search]OEIS[/url]).


Figure shows a U - tube of uniform cross section that is open a both ends. It is partially filled with water. Now a liquid of density $ d_1$ is poured into the left arm. This liquid does not mix with water.It is observed that height of liquid surface in the left arm is $ 2cm$ more than the height of water surface in the right arm, as shown figure. Take density of water as $ 1000kg/m^3$ and answer these questions.

1) Density of liquid , $ d_1$ is (in kg/m^3):

a) 1200
b) 800
c) 1000
d)1400

2)Length of the liquid column in the left arm of the U-tube is(use density of liquid $ d_1$ a obtained above):

a)15cm
b)8.5cm
c)12cm
d)10cm

I dont understand how such an arrangement is possible, speaking of which I dont understand how we can have two liquids in a U tube in equilibrium. I hope you understand what I mean. In case B , pressure at water interface is Po but at the same level the pressure at the left arm is Po + d_1g(2cm). Infact if we pour any liquid I am getting diff pressure at atleast one point.

[quote="Conjurer"]
I dont understand how such an arrangement is possible, speaking of which I dont understand how we can have two liquids in a U tube in equilibrium. I hope you understand what I mean. In case B , pressure at water interface is Po but at the same level the pressure at the left arm is Po + d_1g(2cm). Infact if we pour any liquid I am getting diff pressure at atleast one point.

[/quote]

The fault lies here:

[quote="You"]
In case B , pressure at water interface is $ P_)$ but [b]at the same level[/b] the pressure at the left arm is $ P_0 \plus{} d_1g(2cm)$. Infact if we pour any liquid I am getting diff pressure at atleast one point.

[/quote]

Who said the water levels in the two arms are same?

The level at which you calculate the pressure must be in the same liquid.

Thus,

$ P_0 \plus{} h g\rho _{water} \equal{} P_0 \plus{} (h \plus{} 2)g d_1
\\
\\
\therefore d_1 \equal{} \left(\frac{h}{h\plus{}2}\right)g/cm^3$

I believe, we need to know $ h$.

Consider the bottom 2cm line in your fig. In the left arm the pressure is Po + d1g(2cm) and in the right arm Po. My question is why diff?

[quote="Conjurer"]
Consider the bottom $ 2cm$ line in your fig. In the left arm the pressure is $ P_0 \plus{} d_1g(2cm)$ and in the right arm $ P_0$. My question is why diff?

[/quote]

I did caution you:

[quote="I"]
[b]The level at which you calculate the pressure must be in the same liquid.
[/b]
[/quote]

Does the lower calibration of $ 2cm$ lie in the same fluid? Surely not!

You need to consider the lower line of $ h$ for that matter.

Then,
[quote="I"]
$ P_0 \plus{} h g\rho _{water} \equal{} P_0 \plus{} (h \plus{} 2)g d_1
\\
\\
\therefore d_1 \equal{} \left(\frac{h}{h\plus{}2}\right)g/cm^3$

[/quote]

[quote="Conjurer"]
I dont know man. As far as I remember, the fluids need to be interacting to apply this method.And in this case they are. I will confirm about this with my teacher.Thnx for reply.

[/quote]

I'm pretty sure this is correct. But your teacher can surely explain better.

And do inform me what your teacher suggests! :D

ans. to (1) is (b) i.e. d1=800kg/m^3

its density must be less than that of water to float on it. :lol:

[quote="iit2009"]
ans. to (1) is (b) i.e. d1=800kg/m^3

its density must be less than that of water to float on it.

[/quote]
I don't think so. :huuh:

What if the apparatus is like this?

Again:

Here:

$ d_1(h\plus{}2)g \equal{} \rho_{water} hg
\\
\\
d_1 \equal{} \frac{h}{h\plus{}2}$

[quote="Conjurer"]
I will confirm about this with my teacher.

[/quote]

Haven't you done that as yet?  :mad:  :wink:

I'm sorry. I confirmed it yesterday and you were right.


group theory
abstract algebra
inequalities
superior algebra
superior algebra unsolved

Let $ G$ be a group and $ \left|G\right| \equal{} 120$.
Show that $ G$ has a subgroup of index $ 3$ or a subgroup of index $ 5$ (or both).

As usual we start with the sylow theorems. Let $ s_p$ be the number of $ p$-sylow. One gets $ s_2\in\{1,3,5,15\}, s_3\in\{1,4,10,40\}, s_5\in\{1,6\}$.

If $ s_2=1$ then the 2-sylow is normal, so there is a $ N\unlhd G$ with $ \abs{G/N}=15 \implies G/N\cong \mathbb{Z}/15$. So there are subgroups of index 3 and 5.

If $ s_2=3$ or $ s_2=5$ then every normalisator of every 2-sylow does the job because the index of the normalisator is the number of sylowgroups.

If $ s_3=1$ or $ s_5=1$ then the 3-sylow (resp. 5-sylow) is normal. Let $ U$ be a 2-sylow. Then $ \abs{UN}=8\cdot 3$ (resp. $ \abs{UN}=8\cdot 5$), i.e. there is a subgroup of index 5 (resp. 3).
Short cut: Use the schur-zassenhaus theorem to get a complement to the normal sylow.

If $ s_3=4$ and $ s_5=6$ then the action on the 3-sylows induces a homomorphism $ G\to S_4$ with kernel $ K\unlhd G$. Because of the orders of $ G$ and $ S_4$ the 5-sylows are in $ K$. There are six 5-sylow which have together $ 1+6\cdot(5-1)=25$ elements.
$ K=\bigcap_{U\in Syl_3(G)} N_G(U)$. By sylow theorems $ |G: N_G(U)|=|Syl_3(G)|=4 \implies \abs{N_G(U)}=30$. Since $ K\leq N_G(U)$ and $ K$ has at least 25 elements it is equal to $ N_G(U)$ for every $ U\in Syl_3(G)$. Hence $ |K|=30$. Applying the sylow theorems to $ K$ we get a normal 3-sylow or 5-sylow group. This is a contradiction.

This leaves $ s_2=15, s_3\in\{10,40\}, s_5=6$. If the intersection of two 2-sylows is always the trivial subgroup then there would be $ \geq 15\cdot(8-7)+10\cdot(3-1)+6\cdot(5-1)=149>120$ elements in $ G$ which is a contradiction.

So let $ U_1,U_2$ be two 2-sylows with intersection $ 1<U_1\cap U_2=: D$ and $ |D|=4$. Then $ D$ is normal in $ U_1$ and $ U_2$ so $ <U_1,U_2>\leq N_G(D) \implies |N_G(D)|>8$. If $ |N_G(D)|=8\cdot 3$ or $ 8\cdot 5$ we would have found the subgroup with index 3 or 5. If not, $ N_G(D)=G \implies D\unlhd G$. $ G/D$ has order 30 and by applying the sylow theorems we get a normal subgroup $ N/D\unlhd G/D$ with $ |N/D|=3$ or $ |N/D|=5$ i.e. $ |N|=12$ or $ |N|=20$. So the quotient $ G/N$ has order 10 or 6. In both cases there is a subgroup of index 5 resp. 3.

The analog argument works fine for $ |D|=2$ as long as $ D$ is normal in $ U_1$ and $ U_2$ (You just have to work for groups of order 60). So for abelian $ U_1$ or $ U_1\cong Q_8$ everything is okay.
The last case we have to worry about is $ U_1\cong D_4$. And now I am running out of ideas...

If one was willing to classify the insoluble groups of order 120 (A5 x 2, SL(2,5), S5) and check them by hand, then take a maximal subgroup containing a Sylow 2-subgroup: such a subgroup has prime power index because the group is solvable and odd index, because it contains a Sylow 2.  The only possible indices of such a subgroup are then 3 and 5.

The motivation for the problem was not clear to me, so it is not clear what sorts of solutions are useful (the groups of order 120 are quite accessible, so one assumes this is a question about understanding general groups, using the groups of order 120 as an example, rather than actually trying to prove something about groups of order 120).

I do, however like Gockel's use of N_G(D) for D a Sylow intersection.  It turns out that a group of order 120 with 15 Sylow 2-subgroups always has a Sylow intersection of size 4.

[list]Perhaps it would be interesting to find some reasonably general way to see that a group of order 120 with 15 Sylow 2-subgroups always has a Sylow intersection of size 4 (rather than just listing the handful of groups of order 120)?[/list]

[quote="SD5225272"]15 is not congruent to 1 mod 4 or 8, so there exists 2 Sylow subgroups S and T such that |S : S/\T| = 2.

Steve[/quote]

Awesome, thanks for reminding me of Isaacs 1.16.


Canada/USA Mathcamp just posted its [url=http://www.mathcamp.org/quiz.php]qualifying quiz[/url] to apply for mathcamp this summer.  Whether you are interested in going to the camp or not, I would recommend having a look at the quiz.  I've done most of the first eight, but still need to spend some time with the last two.  My favorite is problem 7.  Obviously, to keep the integrity of the test we can't talk about the problems here, but I've enjoyed spending some time on them so I thought I'd share.

--Dan

On a similar note, SUMaC posted its problem set on the web a few days ago as well [url=http://math.stanford.edu/sumac/CompleteApplication.pdf]here[/url]. The problems range from rather easy to quite difficult, so I think there's something for everyone in there. The same rules apply for this test as for the MathCamp one.


$ P$ is an orbitary point inside the $ ABC$ triangle.$ G_a, G_b, G_c$ are centroid of $ PBC , PCA , PAB$.prove that $ AG_a , BG_b , CG_c$ are congurrent.

Let I be the point satisfies that $ \overrightarrow {PI}  \equal{} \frac{{\overrightarrow {PA}  \plus{} \overrightarrow {PB}  \plus{} \overrightarrow {PC} }}{4}$
We have
\[ \overrightarrow {C{G_C}}  \equal{} \frac{{\overrightarrow {CA}  \plus{} \overrightarrow {CB}  \plus{} \overrightarrow {CP} }}{3}\] and \[ \overrightarrow {CI}  \equal{} \overrightarrow {CP}  \plus{} \frac{{\overrightarrow {PA}  \plus{} \overrightarrow {PB}  \plus{} \overrightarrow {PC} }}{4} \equal{} \frac{{\overrightarrow {CP}  \plus{} \overrightarrow {CA}  \plus{} \overrightarrow {CB} }}{4}\]
So $ I$ lies in $ CG_C$. Similarly, we have I lies in $ AG_A$ and $ BG_B$. Therefore $ AG_A, BG_B, CG_C$ are concurrent


algebra
IMO
IMO 2007
Sequence
IMO Shortlist

Real numbers $ a_{1}$, $ a_{2}$, $ \ldots$, $ a_{n}$ are given. For each $ i$, $ (1 \leq i \leq n )$, define
\[ d_{i} \equal{} \max \{ a_{j}\mid 1 \leq j \leq i \} \minus{} \min \{ a_{j}\mid i \leq j \leq n \}
\]
and let $ d \equal{} \max \{d_{i}\mid 1 \leq i \leq n \}$.

(a) Prove that, for any real numbers $ x_{1}\leq x_{2}\leq \cdots \leq x_{n}$,
\[ \max \{ |x_{i} \minus{} a_{i}| \mid 1 \leq i \leq n \}\geq \frac {d}{2}. \quad \quad (*)
\]
(b) Show that there are real numbers $ x_{1}\leq x_{2}\leq \cdots \leq x_{n}$ such that the equality holds in (*).

[i]Author: Michael Albert, New Zealand[/i]

1a
Suppose on the contrary, $ |x_{i}-a_{i}|<\frac{d}{2}$ for every $ 1\leq i\leq n$.

Note that
$ d_{i}=a_{k}-a_{l}$ for some $ 1\leq k\leq i$ and $ i\leq l\leq n$. (So in particular $ k\leq l$ and $ x_{k}-x_{l}\leq 0$)
Now
$ d_{i}=(a_{k}-x_{k})+(x_{k}-x_{l})+(x_{l}-a_{l})$
$ \leq |a_{k}-x_{k}|+|x_{l}-a_{l}|$
$ <d$

Since this holds for every $ i$, then $ \max\{d_{i}\}<d$ (contradiction!)

For Part b we make the $ x_{k}$ like this:
Put $ x_{i}=\max\{a_{i}|1\leq i\leq k\}-\frac{d}{2}$.
We can easily check the conditions.

A very nice problem!
Maybe the best problem #1 of the last five years...

====================================================
It is convenient to understand the following related problem:
Given are n intervals I_1,...,I_n, where I_k=[L_k;R_k] for k=1..n.
Under which conditions do there exist real numbers x_1,...,x_n such that
(i) x_1 <= x_2 <= x_3 <= ... <= x_n
(ii) x_k in I_k for k=1..n.

====================================================
A necessary condition for a solution of the related problem is that
(**)  for all i<j, the interval I_i does not lie strictly to the right of I_j.

====================================================
Suppose that the related problem possesses a solution, and consider the
lexicographically smallest solution.  It can be shown (easy, easy) that this
lexicographically smallest solution is found by the following greedy algorithm:
1. Fix x_1 at the left endpoint L_1 of interval I_1
2. For k=2..n fix x_k as the maximum of x_{k-1} and L_k.

It can be shown furthermore that the greedy algorithm succeeds,
whenever the necessary condition (**)  is fulfilled.
Therefore, (**) is necessary and sufficient.

====================================================
The IMO problem considers the special case of the above problem where
I_k = [a_k-d; a_k+d].
In this case, condition (**) boils down to condition (*) in the IMO problem.
Part (a) settles necessity, and part (b) sufficiency.

:lol:  yes it could.

But seriously could you please elaborate on that [b]Goblin[/b]?

[quote="color"]
But seriously could you please elaborate on that [b]Goblin[/b]?[/quote]

Well, I just wanted to say that if you draw graphs of functions $ a: \mathbb N\rightarrow \mathbb R$ and $ x: \mathbb N\rightarrow\mathbb R$ it's very easy to find a solution.

yeh I also think so. In this problem configuration of the idea is very important to get a clear solution :wink:

[quote="Goblin"]This problem is very easy. Just draw some kind of diagram of this and the solution is obvious.[/quote]
[quote="shunka"]yes, I like goblin's solution. i think it applies to all other problems.[/quote]

But Goblin did not give a solution, did he?

All I tried to say is that Goblin's solution applies word for word (without any changes) to any problem in this competition as well as to any other problem. As such, it deserves our special attention and prise.

Of course, (s)he could have been more precise and offer more specifics in the crucial step saying "draw some kind of diagram", but if (s)he did that then the solution would lose its wast generality and we would not be able to use it for all other problems.

Thus, the solution is perfect just as presented by the author.

maybe found by any others, but here's my answer simplified:
case of $ d=0$, $ a_{i}$ is monotonically increasing and we let $ x_{i}=a_{i}$
otherwise, let $ d=a_{k}-a_{l}$. then
$ x_{i}=max(a_{1},\cdots,a_{i})-\frac{d}{2}$ for $ i < k$,
$ x_{i}=min(a_{i},\cdots,a_{n})+\frac{d}{2}$ for $ i > l$, and
$ x_{i}=\frac{a_{k}+a_{l}}{2}$ for $ k \leq i \leq l$.

it is not hard problem but it is good for imo1 :)

[hide="1b"]

Construct sequence $ b$ as following:

$ b_i\equal{}max(a_1,a_2,\ldots,a_i)\minus{}\frac d2$

We will prove that the sequence $ b$ is sequence $ x$ such that there is a equality case.

First, it's obvious that $ b$ is increasing (or remaining constant).

$ |b_1\minus{}a_1|\equal{}\frac d2$, so there is a equality case, now we have to prove that $ |b_j\minus{}a_j|\le \frac d2$ for $ j\in\{2,3,\ldots,n\}$

If every $ b_i$ lies in interval $ \left[ a_i\minus{}\frac d2, a_i\plus{}\frac d2\right]$, the problem is proven.

Because of the definition of $ b$, $ b_i$ cannot be less than any number in its interval, so we only inspect the case when for some $ l$, $ b_l>a_l\plus{}\frac d2$

As $ b_l\equal{}a_k\minus{}\frac d2$, for some $ k$ before, we have $ a_k\minus{}a_l>d$, but as $ k<l$, then we could take $ a_k$ and $ a_l$ to make $ d$, and $ d$ would be greater than it is - contradiction.

That means that for every $ i$ in $ \{1,\ldots,n\}$, we have $ b_i\in\left[ a_i\minus{}\frac d2, a_i\plus{}\frac d2\right]$, or $ |b_i\minus{}a_i|\le \frac d2$, with equality at $ b_1$, and maybe some more.

Take $ x_i\equal{}b_i,i\in\{1,\ldots,n\}$, and the sequence is constructed.

[/hide]

Let $i\in \lbrace 1,2,...,n \rbrace $ and consider $d_i=a_t-a_r $ for $t\leq i\leq r$ and $  a_t\geq a_i\geq a_r$
\[max \{ |x_{i} - a_{i}| \mid 1 \leq i \leq n \} \geq \frac{|x_t-a_t|+|x_r-a_r|}{2} \geq \frac{|a_t-a_r+x_r-x_t|}{2}\]
\[=\frac{a_t-a_r+x_r-x_t}{2} \geq \frac{d_i}{2}\]
so \[(\forall i\in \lbrace 1,2,...,n \rbrace) \ max \{ |x_{i} - a_{i}| \mid 1 \leq i \leq n \}  \geq \frac{d_i}{2}\]
hence \[max \{ |x_{i} - a_{i}| \mid 1 \leq i \leq n \}  \geq  \frac{max_{1\leq i\leq n} d_i}{2}=\frac{d}{2}\]

I wonder if there is a nice interpretation of this problem somewhere.

I am thinking there might be some financial motivation ($d$ is the greatest loss you could have made on a stock that traded with prices $a_i$). But I can't quite figure out what $x_i$s represent in that scenario.

[quote=Nazar_Serdyuk]Interesting
Very similar problem appears at                                                                                [url]http://www.ajorza.org/wimo/index.php/Romania_Pre-IMO[/url][/quote]
Am I the only person who can't access [url]www.ajorza.org[/url] or are others having this problem...

I'm confused by this; can't we have $a_i$ such that $d>0$ and then set $x_i = a_i$? Then it would be a counterexample. I know I've read it wrongly; where's my mistake?

You need $x_1 \leq x_2 \leq ... \leq x_n$ and so if you set $x_i = a_i$, you get that $d = 0$ as $d_i = a_i - a_i = 0$.

I have found a slightly different solution from the above ones.

-----
Let $a_p$ be the greateset number between $a_i$'s , and let $a_q $ be the smallest number between $a_i$'s such that $q>p$
Take $k$ any number between $p$ and $q$  (if $q=p+1$ take either $p$ or $q$ ) we have that :
$$d_k=a_p-a_q$$
and since $d_k$ is the greatest value that $d_i$ can take , we have that $d=d_k=a_p-a_q$

[color=#f00]Claim[/color]: $|x_q-a_q|+|x_p-a_p|\geq d \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; (\star)$
[color=#f00]Proof[/color]: Using triangle inequality we have that $$|x_q-a_q|+|x_p-a_p|\geq |x_q-x_p+a_p-a_q|\geq d$$

So , at least one of $|x_q-a_q|$ and $|x_p-a_p|$ is greater that or equal to $\frac{d}{2}$,  this  proves (a)

Note that we can dispense of $d_i$ immediately by realizing that the definition of $d$ just says \[ d = \max_{1 \le i \le j \le n} \left( a_i - a_j \right). \]

If $a_1 \le \dots \le a_n$ are already nondecreasing then $d = 0$ and there is nothing to prove (for the equality case, just let $x_i = a_i$), so we will no longer consider this case.

Otherwise, consider any indices $i < j$ with $a_i > a_j$. We first prove (a) by applying the following claim with $p = a_i$ and $q = a_j$:

[b][color=red]Claim:[/color][/b]  	For any $p \le q$, we have 	either $|p - a_i| \ge \frac{1}{2}(a_i-a_j)$ 	or $|q - a_j| \ge \frac{1}{2}(a_i-a_j)$.

[i]Proof.[/i]  	Assume for contradiction this is false. 	Then $p > a_i - \frac{1}{2}(a_i-a_j) 	= a_j + \frac{1}{2}(a_i-a_j) > q$, contradiction. $\blacksquare$

As for (b), we let $i < j$ be any indices for which $a_i - a_j = d > 0$ achieves the maximal difference. We then define $x_\bullet$ in three steps: [list] 	[*]We set $x_k = \frac{a_i + a_j}{2}$ for $k = i, \dots, j$. 	[*]We recursively set $x_{k} = \max(x_{k-1}, a_k)$ 	for $k = j+1, j+2, \dots$. 	[*]We recursively set $x_{k} = \min(x_{k+1}, a_k)$ 	for $k = i-1, i-2, \dots$. [/list] By definition, these $x_\bullet$ are weakly increasing. To prove this satisfies (b) we only need to check that \[ \left\lvert x_k - a_k \right\rvert \le \frac{a_i-a_j}{2} \qquad 	(\star) \] for any index $k$ (as equality holds for $k = i$ or $k = j$).

We note $(\star)$ holds for $i < k < j$ by construction. For $k > j$, note that $x_k \in \{a_j, a_{j+1}, \dots, a_k\}$ by construction, so $(\star)$ follows from our choice of $i$ and $j$ giving the largest possible difference; the case $k < i$ is similar.

If $a_i$ is increasing, then $d \le 0$ and the result is obvious. $a_{j+m} < a_j$ and $d$ is the distance between these two points. Because $x_i$ is increasing, $|a_j - x_j| \le d/2$ and $|a_{j+m} - x_{j+m}| \le d/2$ is only possible when $x_j = x_{j+m}$ (this follows from the triangle inequality). In particular, it is impossible for both $|a_j - x_j| < d/2$ and $|a_{j+m} - x_{j+m}| < d/2$.

ii) From i), we set $x_j = x_{j+1} = ... = x_{j+m}$

I have an easy solution por part a which I realized while drawing the graph for a and x. Let $d=d_j$, then $d=a_m-a_n, m\le n, a_m\ge a_i \ge a_n$. Then there are 3 options foe $x_m$:

1) $x_m\ge a_m\Rightarrow x_n\ge x_m\ge a_m\ge a_n \Rightarrow |x_n-a_n|=x_n-a_n\ge a_m-a_n=d\ge d/2$

2) $a_m\ge x_m \ge a_n \Rightarrow |a_m-x_m|+|a_n-x_n|=a_m-x_m-a_n+x_n=a_m-a_n+(x_n-x_m)\ge a_m-a_n=d$ Since the sum is larger or equal to $d$ bi pigeon hole one must be larger than $d/2$

3) $a_m\ge a_n\ge x_m\Rightarrow |a_m-x_m|=a_m-x_m\ge a_m-a_n=d\ge d/2$

Since the union of our cases is the universe of poisiblities for real $x_m$, we proved that in every posibility $max{|x_i-a_i|}\ge d/2$

[b](A):[/b] Assume for the the sake of contradiction that this is false. In other words, assume
\[\max \{ |x_{i} - a_{i}| \mid 1 \leq i \leq n \} < \frac {d}{2},
\]
For all $i$ possible. Removing the absolute value, we must have
$$x_k + 0.5d > a_k > x_k -0.5d.$$
We also get that
$$(x_k + 0.5d) - (x_k - 0.5d) = d > d_i,$$
implying that $\max (d_i) < d$, contradiction. $\square$

Observe that $d$ basically means the biggest difference between a term on the left and some term with the same index or to the right. Note $d \geq 0$ because we can always subtract an element from itself to obtain $0$.

It will help to picture what's going on by using a number line. We have some interval $[a_R, a_L]$ where $L \leq R$. Observe that all terms $a_i$ with $i \leq R$ are forced to be on the interval $(-\infty, a_L]$, since otherwise we could have taken one of those terms and made $d$ bigger. By identical logic, all terms $a_i$ with $L \leq i$ are in the interval $[a_R, \infty)$.

Let's now look at the interval $[a_R, a_L]$. The terms with $L \leq i \leq R$ are all crammed into this interval by taking the union of the sets above. If Observe that \begin{align*}
    2 \cdot \text{max} \geq |x_R - a_R| + |x_L - a_L| \geq |x_L - a_R| + |x_L - a_L| \geq d
\end{align*} by triangle inequality.

If we want equality to hold, we can simply use greedy: take $x_1 = a_1 - \frac d 2$, and define $x_{i + 1} = \max \left( a_{i + 1} - \frac d 2, x_i \right)$. This works by the assumption of $d$ maximal.

[quote=K81o7]Well, to help elaborate on the drawing a diagram method...

Consider some $ a_{j}$, $ a_{k}$ such that $ a_{j}-a_{k}=d, j \le k$.  Then for $ j \le i \le k$, $ a_{j}\le a_{i}\le a_{k}$, and for $ i \le j$, $ a_{i}\le a_{j}$, and for $ k \le i$, $ a_{k}\le a_{i}$.  Thus, if you plot it in the xy plane, you get a sort of "bent pipe" like shape.  And then it's clear if you look in the middle region where the "pipe" is going horizontally that $ a_{j}-x_{j}$ and $ a_{k}-x_{k}$ differ by at least $ d$, giving part a.  From there, it's also clear that the equality case occurs when $ x_{j}=x_{j+1}=...=x_{k}=\frac{a_{j}+a_{k}}{2}$.  From there, you kinda deduce after some thought experiments the bahavior of $ x_{i}$ otherwise, and get $ x_{i}=\text{max}\{x_{i-1}, a_{i}-\frac{d}{2}\}$[/quote]

Can someone elaborate on what @K81o7 is graphing here? I am confused because there does not seem to be any x,y...

[color=#f00][b]Part A:[/b][/color] Let $1\le I\le n$ be chosen such that $d_I=d$. Then let $a_M=d_{i} = \max \{ a_{j}\mid 1 \leq j \leq i \} , a_m = \min \{ a_{j}\mid i \leq j \leq n$, with $1\le M,m \le n$. Evidently $m>M$. If either $x_m$ or $x_M$ is not between $a_m$ and $a_M$, the inequality clearly stands, so assume that. Then $$(x_M-a_M)+(a_m-x_m) \ge x_M-x_m = d,$$ finishing the part.

[b][color=#f00]Part B:[/color][/b] We claim that $x_i = \text{max}(a_1, a_2, \ldots, a_i) - \frac{d}{2}$ works. Clearly the $x_i$ are nondecreasing. Now if $\text{max}(a_1, a_2, \ldots, a_i)-a_i \le d$, we must have $|a_i-x_i|\le \frac{d}{2}$. Thus it suffices to prove that this always occurs. Indeed, suppose that $\text{max}(a_1, a_2, \ldots, a_i)-a_i > d$ for some $i$, then $d_i\ge \text{max}(a_1, a_2, \ldots, a_i)-a_i > d$, contradiction.

Intimidating but not hard.

Assume for the sake of contradiction that $|x_i-a_i|<\frac{d}{2}$ for all $i.$

Let $d_i=a_j-a_k.$ Note that $j\le k.$

Then, $d_i=a_j-x_j+x_j-x_k+x_k-a_k\le |x_j-a_j|+|x_k-a_k|<d,$ for all $i,$ which is a contradiction.

Note that the construction $x_{i}=\max\{a_{i}|1\leq i\leq k\}-\frac{d}{2}$ implies equality.

I probably made a small error somewhere; the proof should be right, though.

Note that the case where $a_1\le a_2\le \dots \le a_n$ is trivial. Then note that $d>0$ is just equal to the maximal value of $a_i-a_j$ over all $1\le i<j\le n$. Consider some two fixed numbers $p$ and $q$ such that $p<q$ and $a_p-a_q=d$. Then at least one of $|x_p-a_p|$ and $|x_q-a_q|$ is at least $\frac{d}{2}$, so the first part is proven. For the second part, we give an algorithm to construct all $x_i$ for $i>q$, the case where $i<p$ being symmetric.

Consider an empty set $S$. We iterate through $a_i$ for $p\le i\le n$, using the following rules:
[list]
[*]If adding $a_i$ would not cause $\text{max}(S)-\text{min}(S)$ to exceed $d$, then add $a_i$.
[*]Otherwise, for all $x_i$ corresponding to the elements in $S$, set each one equal to $\frac{\text{max}(S)+\text{min}(S)}{2}$. Then clear $S$ and add $a_i$.
[/list]
At the end of the algorithm, perform the second step. Now, we show that this works. Clearly $(*)$ is satisfied; it suffices to show that $x_p\le x_{p+1}\le \dots \le x_n$. Suppose otherwise. Then suppose there exists a number $i$ such that $p\le i\le n$ and $x_{i-1} > x_i$. Then let the set $S$ at the second step of our algorithm for $x_{i-1}$ and $x_i$ be $S_1$ and $S_2$. We must have $\text{max}(S_2)>\text{min}(S_1)+d$ thus $x_i>\text{min}(S_1)+\frac{d}{2}$. But then $x_{i-1}\le \text{min}(S_1)+\frac{d}{2}$ which is a contradiction.

ISL Marabot solve

Let, $b_{i} = \max \{ a_{j}\mid 1 \leq j \leq i \} $
and, $c_i =\min \{ a_{j}\mid i \leq j \leq n \}$

$\textbf{Part (a):}$
Here, clearly, $d_i \geq 0$ as $b_i \geq a_i \geq c_i \ \forall \ i \in \{1,2,\dots,n\}$.
Now, if $d=0$ then it's trivial. So lets assume that $d=d_k > 0$ for some $1\leq k \leq n.$ Let, $a_p$ be the maximum among $a_1,\dots, a_k$ and $a_q$ is the minimum among $a_k,\dots, a_n$.
Now, $p < q$ as $d\neq 0$. So, $x_p \leq x_q$ but $a_p > a_q$. So clearly one of $|a_p-x_p|, |a_q-x_q|$ will be atleast, $\dfrac {a_p-a_q}{2} = \dfrac d 2. \ \ \ \ \blacksquare$

$\textbf{Part (b):}$
We, take $x_i = \dfrac{b_i+c_i} 2$.
This sequence is non-decreasing as both $(b_i)$ and $(c_i)$ are non-decreasing.
Now, $|a_i-x_i| \leq \dfrac {d_i} 2$ as, $b_i \geq a_i \geq c_i \ \forall \ i \in \{1,2,\dots,n\}$.
So, $\max \{ |x_{i} - a_{i}| \mid 1 \leq i \leq n \}\leq \frac {d}{2}$. And this along with the result from $\boxed{\text{Part (a)}}$ gives,  $\max \{ |x_{i} - a_{i}| \mid 1 \leq i \leq n \} = \frac {d}{2}. \ \ \ \ \blacksquare$

(a) Define the descent of an ordered pair $(i,j)$ with $i<j$ as $\max(0, a_i-a_j)$. Clearly, $d$ is the largest descent over all ordered pairs $(i,j)$. Suppose $(i_m,j_m)$ achieves a descent of $d$. Since $x_{i_m}\leq x_{j_m}$, the best we can do is $x_{i_m}=x_{j_m}=\frac{a_{i_m}+a_{j_m}}{2},$ which causes a maximum difference of $d/2$.

(b) We break up the sequence $a$ into groups, such that a new group starts if and only if the current value in the sequence is larger than all terms before it. For each group $G$ corresponding to indices $p$ through $q$, we assign $x_i=\frac{\max(G)-\min(G)}{2}$ for all $p\leq i \leq q$ if this fits $x$ being increasing, otherwise we use the same value as we did in the last group. This guarantees that $|a_i-x_i|\leq d/2$, so we are done.

In what follows, we index functionally and from \(0\). For natural \(\text{k}\), we mean by \(\text{i}\colon\text{k}\) that \(\text{i}\in\left\{0,\dots,\text{k}-1\right\}\).

[b](a)[/b] Remark that \begin{align*}\max_{\text{i}\colon\text{n}}\left\{\max_{\text{j}_{0}\colon\text{i}+1}\left\{a\left(\text{j}_{0}\right)\right\}-\min_{\text{j}_{1}\colon\text{n}-\text{i}}\left\{a\left(\text{i}-1+\text{j}_{1}\right)\right\}\right\}\ &=\ \max_{\text{i}\colon\text{n}}\left\{\max_{\text{j}_{0}\colon\text{i}+1,\ \text{j}_{1}\colon\text{n}-\text{i}}\left\{a\left(\text{j}_{0}\right)-a\left(\text{i}-1+\text{j}_{1}\right)\right\}\right\}\\ &=\ \max_{\text{i}\colon\text{n},\ \text{j}_{0}\colon\text{i}+1,\ \text{j}_{1}\colon\text{n}-\text{i}}\left\{a\left(\text{j}_{0}\right)-a\left(\text{i}-1+\text{j}_{1}\right)\right\}\\ &=\ \max_{\substack{\text{j}_{0}\colon\text{n},\ \text{j}_{1}\colon\text{n} \\ \text{j}_{0}\ \leq\ \text{j}_{1}}}\left\{a\left(j_{0}\right)-a\left(j_{1}\right)\right\}.\end{align*} In particular, for a maximizing pair \(\left(\text{j}_{0},\text{j}_{1}\right)=\left(\text{J}_{0},\text{J}_{1}\right)\) and any increasing sequence \(x\left(0\right)\leq\dots\leq x\left(\text{n}-1\right)\) we have that \begin{align*}\left|a\left(\text{J}_{0}\right)-x\left(\text{J}_{0}\right)\right|\ +\ \left|a\left(\text{J}_{1}\right)-x\left(\text{J}_{1}\right)\right|\ &\geq\ \left(a\left(\text{J}_{0}\right)-x\left(\text{J}_{0}\right)\right)\ -\ \left(a\left(\text{J}_{1}\right)-x\left(\text{J}_{1}\right)\right)\\ &=\ \left(a\left(\text{J}_{0}\right)-a\left(\text{J}_{1}\right)\right)\ +\ \left(x\left(\text{J}_{1}\right)-x\left(\text{J}_{0}\right)\right)\\ &=\  \max_{\substack{\text{j}_{0}\colon\text{n},\ \text{j}_{1}\colon\text{n} \\ \text{j}_{0}\ \leq\ \text{j}_{1}}}\left\{a\left(\text{j}_{0}\right)-a\left(\text{j}_{1}\right)\right\}\ +\ \left(x\left(\text{J}_{1}\right)-x\left(\text{J}_{0}\right)\right) \\ &=\ \max_{\text{i}\colon\text{n}}\left\{\max_{\text{j}_{0}\colon\text{i}+1}\left\{a\left(\text{j}_{0}\right)\right\}-\min_{\text{j}_{1}\colon\text{n}-\text{i}}\left\{a\left(\text{i}-1+\text{j}_{1}\right)\right\}\right\}\ +\ \left(x\left(\text{J}_{1}\right)-x\left(\text{J}_{0}\right)\right)\\ &\geq\ \max_{\text{i}\colon\text{n}}\left\{\max_{\text{j}_{0}\colon\text{i}+1}\left\{a\left(\text{j}_{0}\right)\right\}-\min_{\text{j}_{1}\colon\text{n}-\text{i}}\left\{a\left(\text{i}-1+\text{j}_{1}\right)\right\}\right\}\end{align*} whence either \[\left|a\left(\text{J}_{0}\right)-x\left(\text{J}_{0}\right)\right|\ \geq\ \frac{1}{2}\max_{\text{i}\colon\text{n}}\left\{\max_{\text{j}_{0}\colon\text{i}+1}\left\{a\left(\text{j}_{0}\right)\right\}-\min_{\text{j}_{1}\colon\text{n}-\text{i}}\left\{a\left(\text{i}-1+\text{j}_{1}\right)\right\}\right\} \] or \[\left|a\left(\text{J}_{1}\right)-x\left(\text{J}_{1}\right)\right|\ \geq\ \frac{1}{2}\max_{\text{i}\colon\text{n}}\left\{\max_{\text{j}_{0}\colon\text{i}+1}\left\{a\left(\text{j}_{0}\right)\right\}-\min_{\text{j}_{1}\colon\text{n}-\text{i}}\left\{a\left(\text{i}-1+\text{j}_{1}\right)\right\}\right\},\] as claimed. \(\blacksquare\)

[b](b)[/b] Consider the function \[x\left(\text{i}\right) := \frac{1}{2}\left(\max_{\text{j}_{0}\colon\text{i}+1}\left\{a\left(\text{j}_{0}\right)\right\}+\min_{\text{j}_{1}\colon\text{n}-\text{i}}\left\{a\left(\text{i}-1+\text{j}_{1}\right)\right\}\right),\] increasing in \(\text{i}\) as both summands are, and remark that \begin{align*}\left|\frac{1}{2}\left(\max_{\text{j}_{0}\colon\text{i}+1}\left\{a\left(\text{j}_{0}\right)\right\}+\min_{\text{j}_{1}\colon\text{n}-\text{i}}\left\{a\left(\text{i}-1+\text{j}_{1}\right)\right\}\right)\ -\ a\left(\text{i}\right)\right|\ &=\ \left|\frac{1}{2}\left(\max_{\text{j}_{0}\colon\text{i}+1}\left\{a\left(\text{j}_{0}\right)\right\}-a\left(\text{i}\right)\right)\ +\ \frac{1}{2}\left(\min_{\text{j}_{1}\colon\text{n}-\text{i}}\left\{a\left(\text{i}-1+\text{j}_{1}\right)\right\}-a\left(\text{i}\right)\right)\right| \\ &=\ \left|\frac{1}{2}\max_{\text{j}_{0}\colon\text{i}+1}\left\{a\left(\text{j}_{0}\right)-a\left(\text{i}\right)\right\}\ -\ \frac{1}{2}\max_{\text{j}_{1}\colon\text{n}-\text{i}}\left\{a\left(\text{i}\right)-a\left(\text{i}-1+\text{j}_{1}\right)\right\}\right|\\ &\leq\ \max\left(\frac{1}{2}\max_{\text{j}_{0}\colon\text{i}+1}\left\{a\left(\text{j}_{0}\right)-a\left(\text{i}\right)\right\},\ \frac{1}{2}\max_{\text{j}_{1}\colon\text{n}-\text{i}}\left\{a\left(\text{i}\right)-a\left(\text{i}-1+\text{j}_{1}\right)\right\}\right)\\ &\leq\ \frac{1}{2}\max_{\substack{\text{j}_{0}\colon\text{n},\ \text{j}_{1}\colon\text{n} \\ \text{j}_{0}\ \leq\ \text{j}_{1}}}\left\{a\left(j_{0}\right)-a\left(j_{1}\right)\right\}\\ &=\ \frac{1}{2}\max_{\text{i}\colon\text{n}}\left\{\max_{\text{j}_{0}\colon\text{i}+1}\left\{a\left(\text{j}_{0}\right)\right\}-\min_{\text{j}_{1}\colon\text{n}-\text{i}}\left\{a\left(\text{i}-1+\text{j}_{1}\right)\right\}\right\}\end{align*} Whence in conjunction with (a) the claimed equality. \(\blacksquare\)

[b](a)[/b] In case $a_1\leq a_2\leq \dots \leq a_n$ we have $\max |x_i-a_i|\geq 0\geq \frac d2$. Otherwise, let $d=a_k-a_l>0$ for $k<l.$ Then $$\max |x_i-a_i|\geq \frac{|a_k-x_k|+|x_l-a_l|}{2}\geq \frac{|a_k-a_l+x_l-x_k|}{2}= \frac{a_k-a_l+x_l-x_k}{2}\geq \frac d2 \quad \blacksquare$$

[b](b)[/b] We claim that the sequence $x_k=\max_{1\leq i\leq k} a_i-\frac d2$ satisfies. For an arbitrary fixed $i$ let $x_i=a_j-\frac d2.$ Then $$0\leq a_j-a_i\leq d\implies |x_j-a_i|=|a_j-a_i-\frac d2|\leq \frac d2.$$ By the part (a) the equality must occur, as required.

The key part of the problem is the following characterization of $d$.

[b][color=#00f]Claim:[/color][/b] $d=\max_{i<j}(a_i-a_j)$.
[color=#00f]Proof:[/color] Clear.

With this in mind, part (a) follows by the triangle inequality, since for $i>j$ with $a_i-a_j$ maximal we have
$$d=a_i-a_j=(a_i-x_i)+(x_i-a_j)\leq (a_i-x_i)+(x_j-a_j)=|x_i-a_i|+|x_j-a_j|$$
and the conclusion is clear.
Motivated by this, for part (b) we select $x_k=\max_{i\leq k} a_i-\frac{d}{2}$ which clearly works:
\begin{align*}
a_k-x_k&\leq \max_{i \leq k} a_i-x_k=\frac{d}{2}\\
x_k-a_k&\leq \max_{i \leq k} a_i-\frac{d}{2}-\left(\max_{i\leq k} a_i-d\right)=\frac{d}{2}.~\blacksquare
\end{align*}

It is easy to see $d = \max_{1\leq i\leq j \leq n} (a_i-a_j)$. Consider the pair $(i,j)$ that achieves this maximum. One of $|x_i - a_i|$ and $|x_j-a_j|$ is at least $\frac d2$, which proves part a. For part b, set $x_i = \max_{1\leq j \leq i}(a_i) - \frac d2$.

This could easily show up in a coding contest in a format such as: Given an array $A$ of $n$ numbers $a_1, a_2, a_3 \dots$, find an array $X$ of $n$ numbers $x_1 \leq x_2 \leq x_3 \dots x_n$ such that $\max_{1\leq i \leq n}|x_i - a_i|$ is minimized. "Binary searching on the answer" would allow one to motivate the following ideas/constructions:

Sketch of Proof:

a. We show by way of contradiction that it is not possible for there to exist $x_1 \leq x_2 \leq \dots x_n$ such that $a_i - \frac{d}{2} < x_i < a_i + \frac{d}{2} $ for $i = 1, 2, \dots n$. Now if there exist $j \leq k$ such that $a_j - \frac{d}{2} \geq a_k + \frac{d}{2} \implies a_j - a_k \geq d$, then this construction is infeasible. But by definition of how $d$ is defined, there will exist $j, k$ that satisfy this. This creates a contradiction.

b. Consider $x_i = \max(a_1 -\frac{d}{2}, a_2 - \frac{d}{2} \dots a_i - \frac{d}{2})$. Clearly $x_t \leq x_{t+1}$ and $a_t - \frac{d}{2} \leq x_t$. Now it suffices to show that $a_k - \frac{d}{2} \leq a_t + \frac{d}{2}$ for $k \leq t$. We merely need that $a_k - a_t \leq \frac{d}{2}$ which is true due to how $d$ is defined.


[url]https://www.tracy.k12.ca.us/igcg/TCHRS/dmedek/IMP%203%20docs/Meadows%20or%20Malls/p%20161-162%20POW%205%20Thats%20Entertainment.pdf#search='IMP%203%20POW%205%3A%20That%27s%20entertainment'[/url]
sorry, I forgot how to do the hyperlink...

I had trouble with the above problem... I tried to do it mathematically... but I'm kind of lost on the first step. I just knew that there are 52 cards, 13 denominations and 4 "something" in each denomination.

There were minor errors when I tried to experiment with the cards but I don't have a deck of card with me right now...

Help please!

[hide]THere are 52-5=47 cards distributed throughout the 6 piles. One possibilty for the number of cards in each pile is 10, 9, 8, 7, 7, 6. In that case the first card drawn for each pile is 3, 4, 5, 6, 6, 7.  They sum to [b]31[/b]. THe sum will not be different for different distributions of the 47 cards so the answer is 31.[/hide]

I think I get it. I didn't realize that the solution is that simple!
Thank you danthemanvt!  :)

Sorry for making two posts, I thought I type this one into the edit of the last one...

THe sum [b]will not be different for different distributions [/b]of the 47 cards so the answer is 31. I am trying to figure out how to clarify that...

hints and help? please?

What's evaluation of problem?

What I mean by that is that no matter how many cards are in each pile, as long as there are 47 cards total in the piles, the sum of the first card from each piile will always be the same.
Say the number of cards in the six piles are $a,b,c,d,e,f.$ Then   $a+b+c+d+e+f=47$.  The   first    card     drawn     in     each      pile     would     have    a    value    of    $13-a, 13-b, 13-c, 13-d, 13-e, 13-f$, respectively.    So     the     sum     of     those     cards     would     be
 $(13-a)+(13-b)+(13-c)+(13-d)+(13-e)+(13-f) = 78-(a+b+c+d+e+f) = 78-47 = 31$


superior algebra
superior algebra unsolved

Suppose $ F \subseteq K$ are fields, and that $ [K: F]\equal{}p$, where $ p$ is an odd prime.  Let $ \alpha \in K\minus{}F$.  Prove that $ K\equal{}F(\alpha^n)$ for any $ n$, $ 1 \leq n <p$.

This one seems simple, I am thinking to prove first that the basis for $ F(\alpha)$ is 1, $ \alpha$, $ \ldots$, $ \alpha^{p\minus{}1}$ and then this would mean that $ F(\alpha)\equal{}F(\alpha^m)$ for any $ n$, $ 1 \leq n <p$.  Is this a good way to go or is there an easier way I am not seeing now?

Seems easy enough.  You could also look at the chain of fields $ F\subset F(\alpha^n)\subset F(\alpha)\subset K$ and see what you can say about degrees.


I think i misplaced them. Finding out that posting tests are illegal i was wondering if parts of tests were to? I it is i heard emailing it was fine and it would be great either way =D

which test? school, chapter, state, nats?

Please and thank you =D answers would be nice to =]


algebra
polynomial
search
number theory unsolved
number theory

1. Let $ a_i$ be natural numbers for i=1,2,...,n
If $ P(x)\equal{}(x\minus{}a_1)(x\minus{}a_2)...(x\minus{}a_n)\minus{}2$ is reducible, show that $ n\equal{}3$

2. Find all positive integers n such that $ p(x)\equal{}x^n\minus{}64$ is reducible.

3. For any positive integers $ n\geq2$, show that $ f(x)\equal{}x^n\plus{}5x^{n\minus{}1}\plus{}3$ is irreducible.

i  have  a doubt,   in first question  we will get the  result  only  if  that  2 is  there  or even for anyother numbers?

[quote="BG Yoda"]The third is an obvious consequence of the Perron's criterion.[/quote]

Unfortunately not all of us knew that back then during the Imo '93...

[url]http://www.mathlinks.ro/Forum/viewtopic.php?p=372292#372292[/url]

[quote="ZetaX"][quote="b555"]is  perron`s crieterion  same  as perron`s formula or u meant something else?[/quote]
Something else. Take a search on the forum.[/quote]

i tried  but i could not get.  can u gimme the  link zetax?

The Perron's criterion says that if a polynomial has integer coefficients - $ f(x) \equal{} x^n \plus{} a_1x^{n \minus{} 1} \plus{} \dots \plus{} a_n$ , $ a_n \not \equal{} 0$ such that $ |a_1| > 1 \plus{} |a_2| \plus{} \dots \plus{} |a_n|$, then it is irreducible. If you need to prove this, first show that the polynomial has exactly one zero outside of the unit disk and all others are inside ...  :wink:


inequalities
vector
geometry
rectangle
inequalities proposed

I think this one seems terrible. But have you tried it? :D

My solution uses vector to prove it.
 Let ABCD be a rectangle and M is a point on it. Denote the angle MAB, MBC,MCD,MDA are a,b,c,d. Then we have tga*tgb*tgc*tgd=1.
 If xyzt=1 and x,y,z,t>0 then there exists a rectangle ABCD and a point M such that x=tga,y=tgb,z=tgc,t=tgd.
 Now put the unit vectors e1,e2,e3,e4 in MA,MB,MC,MD.
 And our inequality in equivalant to (e1+e2+e3+e4) 2 >=0.\ :)


Ascertain the angles of the triangle $ ABC$ for which $ \left|\begin{array}{c}
\sin A\plus{}\sin B\plus{}\sin C\equal{}\frac {3\plus{}\sqrt 3}{2}\\\\
\cos A\plus{}\cos B\plus{}\cos C\equal{}\frac {1\plus{}\sqrt 3}{2}\end{array}\right|$ .

Multiply the second equation by $ \sqrt {3}$, subtract from the first and rearrange to get

$ \sin\left(A - {\pi\over 3}\right) + \sin\left(B - {\pi\over 3}\right) + \sin\left(C - {\pi\over 3}\right) = 0$

Put $ a = A - {\pi\over 3}$ etc. to get

$ \sin a + \sin b + \sin c = 0\land a + b + c = 0$

\begin{eqnarray*}\sin a + \sin b + \sin c & = & 2\sin{a + b\over 2}\cos{a - b\over 2} + 2\sin{c\over 2}\cos{c\over 2} \\
& = & - 2\sin{c\over 2}\cos{a - b\over 2} + 2\sin{c\over 2}\cos{c\over 2} \\
& = & 2\sin{c\over 2}\left(\cos{c\over 2} - \cos{a - b\over 2}\right) \\
& = & - 4\sin{c\over 2}\sin{c + a - b\over 4}\sin{c - a + b\over 4} \\
& = & - 4\sin{c\over 2}\sin {b\over 2}\sin {a\over 2}\end{eqnarray*}

Therefore one of $ a,b,c$ is zero, and the other two are mutually opposite. Remembering $ a = A - {\pi\over 3}$ etc., WLOG $ A = {\pi\over 3}$. Now $ \sin B + \sin C = {3\over 2}$ and $ B + C = {2\pi\over 3}$ yields $ 2\sin{B + C\over 2}\cos{B - C\over 2} = {3\over 2}\iff B - C = \pm{\pi\over 3}$. WLOG we take the plus sign. Therefore $ B = {\pi\over 2}, C = {\pi\over 6}$ (i.e. $ 30 - 60 - 90$).

[color=darkblue]$ \dfrac{p}{R}\equal{}\dfrac{3\plus{}\sqrt{3}}{2}$

$ \dfrac{1\plus{}\sqrt{3}}{2}\equal{}1\plus{}\dfrac{r}{R} \Longleftrightarrow \dfrac{r}{R}\equal{}\dfrac{\sqrt{3}\minus{}1}{2}$

Therfore, $ p\equal{}2R\plus{}r \Longrightarrow \angle A\equal{}90^\circ$.

Then

$ 2(\cos B\plus{}\sin B)\equal{}1\plus{}\sqrt{3}$

$ \cos B\equal{}x \Longrightarrow$

$ 2x\plus{}2\sqrt{1\minus{}x^2}\equal{}1\plus{}\sqrt{3}$

$ 2\sqrt{1\minus{}x^2}\equal{}1\plus{}\sqrt{3}\minus{}2x$

$ 4\minus{}4x^2\equal{}1\plus{}3\plus{}4x^2\plus{}2\sqrt{3}\minus{}4x\minus{}4\sqrt{3}x$

$ \minus{}8x^2\plus{}x(4\plus{}4\sqrt{3})\minus{}2\sqrt{3}\equal{}0$

So $ \cos B\equal{}\frac{1}{2}$ or $ \cos B\equal{}\frac{\sqrt{3}}{2}$

So $ \triangle\equal{}\{30^\circ,60^\circ,90^\circ\}$[/color]

[quote="Virgil Nicula"]Ascertain the angles of the triangle $ ABC$ for which $ \left|\begin{array}{c} \sin A \plus{} \sin B \plus{} \sin C \equal{} \frac {3 \plus{} \sqrt 3}{2} \\
 \\
\cos A \plus{} \cos B \plus{} \cos C \equal{} \frac {1 \plus{} \sqrt 3}{2}\end{array}\right|$ .[/quote]

[b][u]Proof[/u].[/b] From the well-known relations $ \left|\begin{array}{c} \sin A \plus{} \sin B \plus{} \sin C \equal{} \frac pR \\
 \\
\cos A \plus{} \cos B \plus{} \cos C \equal{} 1\plus{}\frac rR\end{array}\right|$ obtain $ \left|\begin{array}{c} \frac pR\equal{} \frac {3 \plus{} \sqrt 3}{2} \\
 \\
1\plus{}\frac rR\equal{} \frac {1 \plus{} \sqrt 3}{2}\end{array}\right|$ $ \Longleftrightarrow$ $ \left|\begin{array}{c}
p\equal{}2R\plus{}r\\\\
p\equal{}\sqrt 3\cdot(R\plus{}r)\end{array}\right|$ .

Since $ \tan\frac A2\equal{}\frac {r_a}{p}\equal{}\frac {r}{p\minus{}a}$ and $ r_a\plus{}r_b\plus{}r_c\equal{}4R\plus{}r$ obtain easily $ \left|\begin{array}{c}
\tan\frac A2\plus{}\tan\frac B2\plus{}\tan\frac C2\equal{}\frac {4R\plus{}r}{p}\\\\
\tan\frac A2\tan\frac B2\plus{}\tan\frac B2\tan\frac C2\plus{}\tan\frac C2\tan\frac A2\equal{}1\\\\
\tan\frac A2\tan\frac B2\tan\frac C2\equal{}\frac rp\end{array}\right|$ .

With other words, the equation $ f(x)\equiv p\cdot x^3\minus{}(4R\plus{}r)\cdot x^2\plus{}p\cdot x\minus{}r\equal{}0$ has the roots $ \left\{\tan\frac A2,\tan\frac B2,\tan\frac C2\right\}$ .Observe that

$ \left|\begin{array}{c}
f(1)\equal{}0\\\\
f\left(\frac {\sqrt 3}{3}\right)\equal{}0\end{array}\right|$ $ \Longleftrightarrow$ $ \left\{1,\frac {\sqrt 3}{3}\right\}\subset \left\{\tan\frac A2,\tan\frac B2,\tan\frac C2\right\}$ $ \Longleftrightarrow$ $ \left\{60^{\circ},90^{\circ}\right\}\subset\{A,B,C\}$ $ \Longleftrightarrow$ $ \left\{30^{\circ},60^{\circ},90^{\circ}\right\}\equal{}\{A,B,C\}$ .


Euler
limit
real analysis
real analysis unsolved

Proove the limit

$ \lim_{n\to \infty }\, \left(\sum_{a=1}^{n}\left(\frac{a}{n}+1\right)^{n}\right)^{1/n}=2$

I think that this limit is a simple application of the problem I posed on the net, A nice problem, a couple of days ago.

Let $ f: [0,1]\rightarrow [0,\infty)$, $ f(x)=1+x$.

Then your limit equals $ \max f(x)=2$.

I do not know how to post the link, simply look down a couple of posts, it is called "A nice problem" with a solution by JBL.

[quote="didilica"]I do not know how to post the link,
[/quote]
Simply go to the post you want to post the link to, copy the content of the address line in your browser, and put it between the url tags in your reply. Try it on test forum if you wish :). If I understood you right, the link you wanted is
[url]http://www.artofproblemsolving.com/Forum/viewtopic.php?t=156406[/url]


geometry
rectangle
geometric transformation
reflection

Two mathematicians are playing mathematical pool.  One chalks his stick while the other sets the cue ball on the center of the square pool table.  He challenges his opponent to hit the ball so that it bounces off each wall exactly once before going in to a pocket.  Prove that his opponent cannot do it.

What is the set of points from which it is not possible to preform the above feat?

The second mathematician declares the game unfair.  "We should do it like this," he says, "I'll call what pocket I'm going to shoot it in, and you can place it anywhere on the table you want except the very center.  Then I'll bounce it off four walls and into a pocket."  What is the set of points on which the first mathematician could place the ball in order to be guaranteed a win?

Fed up with his two failed attempts, the second mathematician suggests they try the same challenge on a triangular pool table.  Are there any points on an equilateral triangular pool table from which it is impossible to bounce a ball off all three walls once each and then into a pocket?

A standard rectangular pool table is a rectangle whose length is twice as long as its width.  In addition to the standard pockets at each corner, there is also a pocket at the midpoint of each of the longer sides.  From what points on such a table is it impossible to bounce the ball off all four walls and then into a given corner pocket?  A given side pocket?

In mathematical pool, the ball is a point which continues travelling in a straight line until it hits a wall or a pocket.  If it hits a wall, it bounces off so that its angle of incidence is equal to its angle of reflection.  When it hits a pocket, it stops moving.  Pockets are traditionally at the corners of any polygonal mathematical pool table.

And a question of a similar variety from the Mandelbrot Problem Corner from 2 years ago:

http://www.mandelbrot.org/dialogue/prevyear/prob2001-3.gif

JBL wrote:Two mathematicians are playing mathematical pool.  One chalks his stick while the other sets the cue ball on the center of the square pool table.  He challenges his opponent to hit the ball so that it bounces off each wall exactly once before going in to a pocket.  Prove that his opponent cannot do it.

Here's a teeny first step. [hide]Let P = center, M = mdpt of first side hit, Q = first point hit. Let :phi: = :ang: MPQ, :theta: = :ang: MQP.

There are 2 possibilities: 1) the ball strikes side MQ and then an adjacent side, or 2) the ball strikes side MQ and then the opposite side. Consider case #1: angle of incidence = :theta: . The next angle of incidence will be the complement of that, or :phi: . We know:

0 < :phi: < 45 and 45 < :theta: < 90.

The ball must strike the next adjacent side, because :phi: < 45. The next angle of incidence will be :theta: . The final incident angle is :phi: -- then the ball is supposed to go into a corner lying on the opposite side. The minimal angle necessary is 45; however, :phi: is strictly less than this value. Therefore, it is impossible for case #1.

Case #2:

The second angle of incidence is :theta: . The ball must strike an adjacent side now -- this means that the next angle of incidence is its complement, or :phi: . In order to hit 4 sides, the ball must travel to the opposite side again. This is impossible, because that would require an angle of at least 45, whereas :phi: is strictly less.[/hide]

If by teeny first step, you mean the solution to the first problem, then yes, you are correct

A fairly useless hint for the other problems: [hide]Your method almost certainly won't work for pool tables once the shapes or starting positions are less regular.  [/hide]

A more useful, but still vague hint: [hide]In order to do the other problems, it helps to develop a method of examining bounces other than through angles of incidence and reflection.[/hide]

:approx:  :approx:  :approx:  :approx:  :approx:  :approx:  :approx:  :inf:  :inf:  :inf:  :inf:  :rt5:  :rt5:  :rt5:  :perp:  :ang:  :sqrt:  :rt2:  :rt2:  :Sigma:  :pi:  :pi:  :pi:

Um, can I help you?

Or, better, could some moderator help me by getting rid of that last comment (and this one, too)?

Please refer to little picture (attached). The pink is the starting pool table. Gray areas represent reflections. Colored dots identify the sides.

JBL wrote:What is the set of points from which it is not possible to preform the above feat?

Here's a second teeny step, which may or may not be correct: [hide]It was already shown that the ball must bounce off adjacent sides. Thus, to get to the two top corner pockets (A, B in the final reflections), the ball should travel in a straight line from the pink square through gray squares leading to that pocket. Because it must hit every side, the ball cannot pass through a corner.

Draw diagonal lines through corners from A and B to the pink table. Where they intersect (in the center) is the only point from which the stated feat is not possible.

The bottom pockets are just reflections of the top ones. [/hide]

JBL wrote:The second mathematician declares the game unfair.  "We should do it like this," he says, "I'll call what pocket I'm going to shoot it in, and you can place it anywhere on the table you want except the very center.  Then I'll bounce it off four walls and into a pocket."  What is the set of points on which the first mathematician could place the ball in order to be guaranteed a win?

[hide]Back to the diagram: Say the mathematician calls A as the pocket -- then placing the ball on any point along the diagonal through the center of the pink square to A will guarantee that the second mathematician cannot end in A. Likewise for all 4 corners.[/hide]

Sorry for the unevenness of the picture.. I've yet to understand Photoshop.

Nicely done.  I'm still thinking about the standard pool table question -- I'm wondering if I need to give it more thought.  But the two triangle questions are good, and you're well on your way to solving them now.


Given $ a, b, c > 0$. Prove that: $ \frac {ab}{c} \plus{} \frac {bc}{a} \plus{} \frac {ca}{b} \ge \sqrt {4(a^2\plus{}b^2\plus{}c^2)\minus{}(ab\plus{}bc\plus{}ca)}$
 :)
It's stronger than the well-known: $ \frac {ab}{c} \plus{} \frac {bc}{a} \plus{} \frac {ca}{b} \ge \sqrt {3(a^2 \plus{} b^2 \plus{} c^2)}$

[quote="nguoivn"]Given $ a, b, c > 0$. Prove that: $ \frac {ab}{c} \plus{} \frac {bc}{a} \plus{} \frac {ca}{b} \ge \sqrt {4(a^2 \plus{} b^2 \plus{} c^2) \minus{} (ab \plus{} bc \plus{} ca)}$
 :)
It's stronger than the well-known: $ \frac {ab}{c} \plus{} \frac {bc}{a} \plus{} \frac {ca}{b} \ge \sqrt {3(a^2 \plus{} b^2 \plus{} c^2)}$[/quote]

Squaring both sides,the inequality becomes :

$ \sum \frac {a^2b^2}{c^2} \plus{} \sum{ab} \geq 2\sum a^2$

Let $ ab \equal{} x,bc \equal{} y,ac \equal{} z$,we shall prove that :

$ \sum x^4 \plus{} xyz \sum x \geq 2\sum x^2y^2$

But this is clear,since by Schur's inequality of degree 4 we have :

$ \sum x^4 \plus{} xyz \sum x \geq \sum xy(x^2 \plus{} y^2) \geq 2\sum x^2y^2$.

Done !

[quote="nguoivn"]Thank you, Rachid for your nice proof. My proof is use SOS and Am-Gm  :)
Now, please try with this result:
[quote="nguoivn"]Another result: Given $ a, b, c > 0$, we also have: $ \frac {ab}{c} \plus{} \frac {bc}{a} \plus{} \frac {ca}{b} \ge 3. \sqrt [3]{\frac {a^3 \plus{} b^3 \plus{} c^3 \plus{} abc}{4}}$  :)[/quote][/quote]

It is equivalent to :

$ 4(a^6b^6\plus{}b^6c^6\plus{}c^6a^6)\plus{}12a^2b^2c^2(\sum a^2b^2(a^2\plus{}b^2)) \geq 3a^4b^4c^4$

$ \plus{}27a^3b^3c^3(a^3\plus{}b^3\plus{}c^3)$

Which is true :)

Done !

[quote="nguoivn"]Thank you, Materazzi. And the stronger seems also trues: $ \frac {ab}{c} \plus{} \frac {bc}{a} \plus{} \frac {ca}{b} \ge 3. \sqrt [3]{\frac {2(a^3 \plus{} b^3 \plus{} c^3) \plus{} abc}{7}}$
Do you think so ?  :)[/quote]

Of course  :lol:

[quote="nguoivn"]Thank you, Materazzi. And the stronger seems also trues: $ \frac {ab}{c} \plus{} \frac {bc}{a} \plus{} \frac {ca}{b} \ge 3. \sqrt [3]{\frac {2(a^3 \plus{} b^3 \plus{} c^3) \plus{} abc}{7}}$
Do you think so ?  :)[/quote]

The following is true also :)

$ \frac {ab}{c} \plus{} \frac {bc}{a} \plus{} \frac {ca}{b} \ge 3. \sqrt [3]{\frac {13(a^3 \plus{} b^3 \plus{} c^3) \plus{} 5abc}{44}}$


Let $ ABC$ be a triangle.$ P$ is a point in this triangle such that $ \angle PCA\equal{}\angle PBC\equal{}45^o$
$ M;N$ are points on $ AB$;$ AC$ such that $ \angle PMB\equal{}\angle PNC \equal{}45^o$
$ Q$ is isogonal point of $ P$ with triangle $ ABC$
Prove that $ \angle QMN\equal{}\angle QNM\equal{}\angle QBC\equal{}\angle QBC\equal{}45^o$

It couldn't be true!
If $ \angle PCA \equal{} \angle PBC \equal{} 45^{o}$ then $ \angle QBC$ is not $ 45^{o}$, if only $ BP$ is not a bisector of $ \angle ABC$.


Find Example
\[ \mathop{lim}_{x\to c}\left|{f(x)}\right| \equal{}\left| L\right|\]
then
\[ \mathop{lim}_{x\to c}f(x) \equal{} M\ne L\]

:lol:
but where is $ c$? what condition about $ f(x)$ ?
for example:
$ f(x)\equal{}\minus{}x^{2}$

[quote="Extremal"]:lol:
but where is $ c$? what condition about $ f(x)$ ?
for example:
$ f(x) \equal{}\minus{}x^{2}$[/quote]
But $ c\equal{}0$ it not true.
Other example
$ f(x)\equal{}\minus{}L$

yes , I know. but I suppose $ c$ is not equal to $ 0$.


geometry
trigonometry
ratio
circumcircle
incenter
parallelogram
angle bisector

Let $ ABC$ be a triangle and incircle of $ ABC$ touch side $ AB$ and $ AC$ at $ P$ and $ Q$ respectively. If orthocenter of $ ABC$ lies on $ PQ$, prove that $ \cos A \equal{} \frac {r}{2R}$.

[quote="mathpk"]Let $ ABC$ be a triangle and incircle of $ ABC$ touch side $ AB$ and $ AC$ at $ P$ and $ Q$ respectively. If orthocenter of $ ABC$ lies on $ PQ$, prove that $ \cos C \equal{} \frac {r}{2R}$.[/quote]

I think that it 's not true. The correct problem might be $ cos A \equal{} \frac{r}{2R}$

Here is my solution:

Realize that $ cosA$ equals to the ratio of the distance from the circumcenter to BC and R. So all we need to do is proving that the distance from the center of the circumcircle of $ \Delta ABC$ to $ BC$ is $ \frac{r}{2}$ which is equivalent to $ r\equal{}AH$.

Let $ R$ be the intersection of the incircle and $ BC$ and $ S$ be the intersection of $ PQ$ and $ BC$. Let $ H$ the orthocenter of $ \Delta ABC$ and $ I$ the incenter of $ \Delta ABC$

Using Menelaus theorem, we can prove that $ R, S$ harmoniously divides $ BC$ (or $ (S,B,R,C)\equal{}1$).

We can prove that $ PQ$ is the angle bisector of the ex-angle $ \angle{BHC}$ (since $ H$ lies on $ PQ$). So $ HR$ is the angle bisector of $ \angle{BHC}$. Therefore, $ HR$ is perpendicular to $ PQ$.

We have: $ AH$ is parallel to $ IR$
               $ HR$ is parallel to $ AI$ (they are both perpendicular to $ PQ$)
So $ AHRI$ is a parallelogram or $ HA\equal{}r$ (QED)

I 'm sorry. $ (S,B,R,C) \equal{} \minus{}1$ not $ (S,B,R,C)\equal{}1$

Let $ D$ be the tangency point of the incircle with $ BC$. It is enough to notice that $ \triangle{BHP}\sim\triangle{CHQ}$ in order to conclude that $ \frac {BH}{CH} \equal{} \frac {BP}{CQ} \equal{} \frac {BD}{CD}$. Thus $ HD$ is the bisector of $ \angle{BHC}$. Since $ \angle{BHP} \equal{} \angle{CHQ}$ it yields that $ DH\perp{PQ} \Longleftrightarrow{DH\parallel{}AI}$ and the rest is trivial.


$ 24\%$ of 50 is what fractional part of 36?

24% of 50 is 12, and 12/36=1/3, so the solution is 1/3.


geometry
3D geometry
tetrahedron
circumcircle

Let ABCD be a tetrahedron whose 4 altitudes are concurrent and let R be the radius of its circumcircle (sphere). Let $ h_1;h_2;h_3;h_4$ be the lengths of the altitudes corresponding A,B,C,D and $ R_1;R_2;R_3;R_4$ be the circumcircle's radius of the opposite faces of A,B,C,D. Prove that
$ \frac {1}{h_1 \plus{} 2\sqrt {2}R_1} \plus{} \frac {1}{h_2 \plus{} 2\sqrt {2}R_2} \plus{} \frac {1}{h_3 \plus{} 2\sqrt {2}R_3} \plus{} \frac {1}{h_4 \plus{} 2\sqrt {2}R_4} \geq \frac {1}{R}$.
When does equality occurs?


Hehehehe, I found these amusing, some of you might too.  Especially if you know Adrian.

Words of advice (and reminders)
1.) Use words like trivially, clearly, obviously and any idiot can see to
bypass steps you do not know how to explain. Bluff often. At least it'll
give the marking committee some hassle and laughter before they put a big
zero in the scorebox for that question or even better, they fall for your
bluff and give you perfect.

2.) Induction solves everything. Magic solves it even better.

3.) Name your own theorem. (i.e. Hill's Theorem, Braverman's Theorem,
Sun's Theorem, Yang's Theorem) Let the statement be whatever tool you need
to solve the problem. Don't be so blatant to let the theorem be the
solution to the actual problem. That's just immoral. Let the theorem be
something that IMPLIES the solution.

4.) Write philosophical essays regarding the invalidity of the question.

Example: If the problem states, you have n couples sitting in a circular
table. Find the number of ways to seat the 2n people so that each couple
do not sit with each other.

What you should do instead of solving the problem is, write a long-winded
essay as to how ridiculous it is that couples are not seated next to each
other. State that this situation can never occur and demand full marks.

An alternate is to also write that I know the solution but cannot write it
down because it is against my religion.

Good luck all!

[quote="Sunny"]
1.) Use words like trivially, clearly, obviously and any idiot can see to
bypass steps you do not know how to explain. Bluff often. At least it'll
give the marking committee some hassle and laughter before they put a big
zero in the scorebox for that question or even better, they fall for your
bluff and give you perfect.
[/quote]
Adrian's counter: one your markers plays poker excessively
[quote="Sunny"]
3.) Name your own theorem. (i.e. Hill's Theorem, Braverman's Theorem,
Sun's Theorem, Yang's Theorem) Let the statement be whatever tool you need
to solve the problem. Don't be so blatant to let the theorem be the
solution to the actual problem. That's just immoral. Let the theorem be
something that IMPLIES the solution.
[/quote]
During IMO training, Elyot used the 'Bonzai monkey tree theorem' for one of the problems.

Haha, good enlightment before Open..Not that I cared anyway T.T..just found out when open was less than a week b4 :S

Neways, GOOD LUCK ALL!  May the Bonzai monkey tree theorem solve all the problems.

[size=200]Good luck [/size]tomorrow to everyone who is going to write OPEN!

[quote="Sunny"][quote="Singular"]did he communicate these to you by msn ?  how come he doesnt post here ?[/quote]

Adrian always bugs the Calgary people through e-mail.  To make us do Olymon, to remind of us dates, and TT too, etc.  No idea why he doesn't post here.[/quote]

I decided to stumble upon this site to see what frequent posters are saying to prepare for the COMC. Instead, I see a copy (or half a copy) of my email sent to the Calgary students posted here.  :lol: Thanks Sarah. :) The second half of the email consisted of real advice that she conveniently left out of her post.  :P

To everyone, best of luck tomorrow on the COMC. Focus, be confident (this is important) and above all, have fun (this is the most important)!


I wonder how to solve the following problem, someone please help. :?:

Given a function $ f: (0,\plus{}\infty)\to\Re$ which is differentiable everywhere. Suppose it satisfies the identity $ xf'(x)\plus{}f(x)\minus{}1\equal{}0$ throughout its domain. It is given that $ f(1)\equal{}2$. Determine the function $ f(x)$ using the [b]Mean Value Theorem for Differential Calculus[/b].

Thank you for helping. :P

[quote="IrinaSharova"]I wonder how to solve the following problem, someone please help. :?:

Given a function $ f: (0,\plus{}\infty)\to\Re$ which is differentiable everywhere. Suppose it satisfies the identity $ xf'(x)\plus{}f(x)\minus{}1 \equal{} 0$ throughout its domain. It is given that $ f(1) \equal{} 2$. Determine the function $ f(x)$ using the [b]Mean Value Theorem for Differential Calculus[/b].

[/quote]

I don't understand your question but this ode seems trivial : $ (xf(x))'\equal{}1$ so $ xf(x)\minus{}f(1)\equal{}x\minus{}1$ so ... ???

Yes, finding f(x) by solving the differential equation is easy.

[hide="Answer"]Its an equation with separable variables, and so

$ x\frac{dy}{dx}\equal{} 1\minus{}y\Rightarrow \frac{dy}{y\minus{}1}\equal{}\minus{}\frac{dx}{x}\Rightarrow  y \equal{}\frac{C}{x}\plus{}1$.

Given f(1) = 2, then $ f(x) \equal{} y \equal{} 1\plus{}\frac{1}{x}$.[/hide]

However, I would also like to see how to solve this by using Lagrange's Theorem.

[quote="pardesi"][quote="IrinaSharova"]
Given a function $ f: (0,\plus{}\infty)\to\Re$ which is differentiable everywhere. Suppose it satisfies the identity $ xf'(x)\plus{}f(x)\minus{}1 \equal{} 0$ throughout its domain. It is given that $ f(1) \equal{} 2$. Determine the function $ f(x)$ using the [b]Mean Value Theorem for Differential Calculus[/b].

[/quote]
the given facts imply
$ xf'(x)\plus{}f(x) \equal{} 1\rightarrow\boxed{\frac{d(xf(x))}{dx}\equal{} 1}$
define $ \Psi(x) \equal{} xf(x)\rightarrow\Psi'(x) \equal{} 1$

$ \frac{\Psi(x)\minus{}\Psi(1)}{x\minus{}1}\equal{}\Psi'(c_{x})$
this implies $ xf(x) \equal{} x\plus{}1$
thus
 $ \boxed{f(x) \equal{} 1\plus{}\frac{1}{x}}$[/quote]

Thank you very much pardesi,  :P  this is how it should be done.
The differential equation is very trival to solve, but the bit about Mean Value Theorem is tedious.


geometry
3D geometry
number theory unsolved
number theory

Find all $ p$ prime numbers, such that

$ p^2\minus{}p\plus{}1$ is a [b]CUBE[/b]

$ p^2 \minus{} p \plus{} 1$ is odd, so let it equal $ (2k \plus{} 1)^3 \equal{} 8k^3 \plus{} 12k^2 \plus{} 6k \plus{} 1$

Hence $ p(p\minus{}1) \equal{} 2k(4k^3 \plus{} 6k \plus{} 3)$.  Since $ p \equal{} 2$ fails, we conclude $ p$ is odd.  Since $ p \equal{} 3$ fails and $ 4k^2 \plus{} 6k \plus{} 3$ is odd, we conclude that $ 4k^3 \plus{} 6k \plus{} 3 \equal{} p$ and $ 2k \equal{} p\minus{}1$; hence

$ 4k^3 \plus{} 6k \plus{} 3 \equal{} 2k \plus{} 1 \implies$
$ 2k^2 \plus{} 2k \plus{} 1 \equal{} 0$

which has no integer (indeed, positive) solution; hence no such $ p$ exists.

You are wrong ($ 4k^2\plus{}6k\plus{}3$ may be is not prime k=3 give $ 4k^2\plus{}6k\plus{}3\equal{}3*19$). $ p\equal{}19$ is solution $ 19^2\minus{}19\plus{}1\equal{}7^3$.

Sorry, I got a little confused.   :blush:

[hide]
Let $ p^2\minus{}p\plus{}1\equal{}n^3$. Then $ p(p\minus{}1)\equal{}(n\minus{}1)(n^2\plus{}n\plus{}1)$. Now it is easy to see $ p\not| n\minus{}1$ (if it did, then $ (n^2\plus{}n\plus{}1)|(p\minus{}1)$, but this would imply $ p\leq n\minus{}1$ and $ n^2\plus{}n\plus{}1\leq p\minus{}1$, which is ridiculous).

So $ p|(n^2\plus{}n\plus{}1)$ and $ (n\minus{}1)|(p\minus{}1)$. Let $ p\minus{}1\equal{}(n\minus{}1)d$. We then have $ n^2\plus{}n\plus{}1\equal{}pd\equal{}d\plus{}(n\minus{}1)d^2$, so that
\[ n^2\plus{}n(1\minus{}d^2)\plus{}(1\minus{}d\plus{}d^2)\equal{}0\]
and then $ (1\minus{}d^2)^2\minus{}4(1\minus{}d\plus{}d^2)$ is a perfect square. It's equal to $ d^4\minus{}6d^2\plus{}4d\minus{}3$, and
\[ (d^2\minus{}3)^2<d^4\minus{}6d^2\plus{}4d\minus{}3<(d^2\minus{}2)^2\]
as long as $ 12<4d$ (true for $ d\geq 4$) and $ 4d<2d^2\plus{}7$ (always true). So $ d\equal{}1,2,3$. But if $ d\equal{}1$ or $ d\equal{}2$, then the discriminant is negative. So $ d\equal{}3$. We then get
\[ 0\equal{}n^2\minus{}8n\plus{}7\equal{}(n\minus{}1)(n\minus{}7),\ p\equal{}1\plus{}3(n\minus{}1)\equal{}3n\minus{}2\]
so that $ p\equal{}\boxed{19}$.
[/hide]


This is from aime 1990:

A fair coin is tossed 10 times. What is the probability that no 2 consecutive tosses are both heads.

spoilerish type thing (been warned):

[hide]When i was taking this earlier tonight, i kept trying to do this through 1- p(2 heads being consec), but i was overcounting badly each time. And then when i started to do it just finding hte total number of times that the heads cant be consec, i did it with laying down tails and then putting heads in the middle of the tails (same method as putting sticks in partitions). Using this, the number of times comes to 6C5 + 7C4 + 8C3 + 9C2 + 10C1 + 11C0. After checking the answers with kalva, i noticed how their solution involved the fibonacci number, and then i remember how combinations can create the fibonacci number, and i thought, wow that was so cool. Hehe. The point of this is that this problem is just so cool in my opinion. O, and if anyone wants to prove how combinations relates to the fibonnaci numbers, id really like to see that proof (although if your proof involves induction, then go away. )[/hide]

What is the relationship between chooses and fibonacci numbers that you're interested in being proved?  (You might put it as a challenge or a question in the Intermedaite or Advanced forums.)

namely that a fibonacci number can be represented in terms of a sequence of combinatorcs... i believe i remember seeing it once as nC0 + (n-1)C1 + ... etc... Im not sure if this was it exactly....

Yeah, that's right. The primary method of solving this problem is recursive. One of the first problems like this I saw was:

Suppose you have a staircase with 10 (or any other number you like) steps. You can take one or two steps at a time. How many ways are there to get up the stairs?

I solved it with combinations that time, but I still got it right. (Interestingly, the problem poser got it wrong.)

That one is really basic though. The recursion can be seen quite easily if u call nth step f(n), then the ways to  get it are = to the ways to get to it from f(n-1) and f(n-2), so we just add them together, and u get fibonacci. Should we have someone move this to advanced to get a proof of combinatorics to fib?

So is there any way of reasoning that f(n) = f(n-1) + f(n-2) without having to go through the counting that jelyman did? That is, is there any way of discovering the recursive formula by simply thinking recursively?

This is a problem I used for practice with my ARML team. Here's the explaination that I gave:

A common technique for when there are a lot of cases to be counted is to try to find a recurrence based on the set of conditions. In this problem, call the number of sequences of n tosses of a coin with no consecutive heads H(n).

If there are no consecutive heads in a sequence of tosses, then it must either start with a T or an HT. If it starts with a T then the remaining n-1 tosses can be any sequence with no consecutive heads. The number of such sequences is H(n-1).

Likewise, if the sequence starts with an HT then the remaining n-2 tosses can be anything with no consecutive heads; the number of such sequences is H(n-2). Therefore the total number of sequences of length n without consecutive heads is given by: H(n) = H(n-1) + H(n-2), where H(1) = 2 and H(2) = 3. This is just the familiar Fibonnaci sequence!! So we find that H(10) = 144.

The total number of possible sequences is 210. Therefore the probability of having a sequence with no consecutive heads is 144/210 = 9/64.