Ramsey Theory
graph theory
combinatorics open
combinatorics

Here is a question relating to Ramsey Theory.

I can only explain this in terms of some examples.

The hypergraph Ramsey number R3(4,4) = 13 is to my knowledge the only known
hypergraph Ramsey number.

This translates as

'colour the 3-sets of a set of 13 objects red or green.
 However this is done, you will have to have a 4 set all of whose 3-sets are
 red or green'.

Now change the question slightly.

'colour the 3-sets of a set of X objects red or green.
 What is the minimum X such that there has to exist a 4-set (which is made up of
 4 3-sets) such that it contains an EVEN NUMBER of 3-sets of each colour?
 I.e. 2 red and 2 green, or all red, or all green.'

This number has to exist, as it is bounded by the above Ramsey number.
This X is in fact 5.
This is a consequence of a simple theorem in graph theory:
Imagine colouring the edges of a K5 red or green.
This represents the above question, as each of the vertices of the K5 can
be labelled as one of the 4-sets in a 5-set.
The edges then represent the 3-sets.

Change the colouring problem as follows:
If the colour is to be 'red' the edge exists, if 'green' it does not.
One of the simplest theories in graph theory states:
'The number of vertices of odd degree in a graph is always even'.
Therefore we must have a vertex in our K5 as required with 2 red or 2 green,
all red or all green edges.

Now to my question...
Does anyone know of a generalisation of this type of result?
By this I mean in a quantative way?

For example:

'colour the 3-sets of X objects red or green.
 What is the minimum X such that there has to be a 5-set such that each of the 4-sets
 of this 5-set contain an EVEN NUMBER of 3-sets of each colour?'

Again, this number will exist, and a very poor upper bound would be the Ramsey
number R3(5,5).

So, to re-iterate, does any know of a good, general upper bound for such a number?
(Just out of interest does this group of numbers have a name?).

Thanks in advance.
Richard.

O.k., I'll add the following:

There is a number X such that if you colour the 3-sets of X objects red or green you will have to a an n-set such that each of the 4-sets in this n-set contains
an EVEN NUMBER of 3-sets of each colour.
Define X(n) as the lowest such X.
As explained in my earlier comment, this X(n) is bounded above by R3(n,n), as any n where all the 3-sets are of one colour satisfies the criteria.
How much less is it?

The best known combinatorial upper bound (there are much better geometric ones!) for N(n) (the lowest number such that if N(n) points are placed in general position in the plane they will always contain a convex n-agon) I can find is:
 N(n) <= R3(n,n)
(The Erdos-Szekeres problem on points in convex position - a survey [Morris and Soltan] referencing Lewin(1976) and Johnson(1986) ).
In fact, it seems that N(n) <= X(n).
Indeed, this in turn means that X(n) >= 2^(n-2) + 1.
The reasoning behind this is fairly straightforward.
Take 4 points in general position in the plane, and label them (x1,x2,x3,x4).
Consider the triangles (were talking geometric now, so straight edges!)
x1 x2 x3
x1 x2 x4
x1 x3 x4
x2 x3 x4.

These can be all coloured red or green depending whether the route from the first point to the last takes a clockwise or anti-clockwise turn.
Try drawing the 16 different possible combinations.
You will see that any set that contains an EVEN number of triangles of one colour is either a convex quadrilateral, or is not drawable.
All ODD combinations are drawable and are representative of a point within a triangle.
Now, take as many points as you like in general position.
Label them x1,...,xn.
Can we always get a list of triangles such that every 4 point set is of the above form?
I.e.
xa xb xc
xa xb xd
xa xc xd
xb xc xd.

Of course we can, just select the triangle combinations by numeric order from x1,...,xn.

Hence, N(n) is bounded above by X(n).
Also,  we can draw any set of points in general position with 2^(n-2) points
such that none contains a convex shape of size n.
Therefore, if we label such a diagram and pull off triangles in the above way,
we will have no n-set such that each of the 4-sets in this n-set contains
an EVEN NUMBER of 3-sets of each colour. Hence X(n) >= 2^(n-2)+1.

It would still be interesting to know if there any upper bounds other than the
trivial one I gave for X(n) ?
[Either in terms on n or in some term of R3(n,n)].
Failing that, can anyone help me by suggesting a method by which such a
bound could be constructed?

Looking at various texts with respect to normal graphs, similar results here hinge on Turan's theorem and the Regularity lemma.
Do such useful tools yet exist for 3-regular hypergraphs?

Thanks Richard.

Okay, let me simplify my requirement...

Consider:

'colour the 3-sets of X objects red or green.
 What is the minimum X such that there has to be a 5-set such that each of the 4-sets
 of this 5-set contain an EVEN NUMBER of 3-sets of each colour?'

From earlier communication we can see that the number of 4-sets that have 3-sets of
either 2-red and 2-green, all red or all green in a 5-set has to be odd, so this
number must be 1, 3 or 5.

Let us consider a set of size 9.

We can use the following sum:

5x +3y +z = 5A, where x+y+z=126.

Here x represents the number of 5-sets within the 9 that have 5 4-sets of even colour,
y represents the number of 5-sets within 9 that have 3 4-sets of even colour, and
z represents the number of 5-sets within 9 that have 1 4-set of even colour.
x+y+z obviously is the total number of 5-sets in 9.

Therefore, the left-hand side of the equation represents a sum of the even 4-sets as
counted within the 5-sets.
However, each 4-set appears, for 9 points, in 5 of the 5-sets.
Hence the right-hand side of the equation.

If we were to require all of the 5 sets to have only one even 4-set we would have:
x=0, y=0 and z=126.
However, z is not divisible by 5, therefore this cannot be so.
If we were to require that we had no 5-sets where all of the 4-sets are even, then
x=0 and y+z =126, and 3y +z =5A.
For the 9 points, therefore, the smallest possible y in this case would be 2,
as 6+124 =130 is divisible by 5.
We can have x=0 and y=0 for integers up to and including 8 and have the above work
(with the obviously necessary amendments to the equations).
So 9 points seems to be a bound such that at least one 5-set has 3 4-sets of an even
colour.

How could I move this forward to find such a bound for my X stated above in such a way?
I can't get my head around whether I can apply the 9 bound to move forward.
A start would be an equation giving the number of 5-sets that have to have 3 4-sets of an
even colour for integers of 9 and upwards!

Is there a combinatorial genius out there who can help me?

Richard.

Okay...

I'll do it myself!

First I need to expand on my previous communication:
Smallest y is indeed 2 for 9 points, but note, next possible y is 7, since
(7*3) + 119 = 140.
So, from 2 the possibles for y go up by 5 each time:
(2*3) + 124 = 130
(7*3) + 119 = 140
(12*3) + 114 = 150...
etc.

Let us now consider when we must find a 9-set with MORE than 2 5-sets that
have 3 even 4-sets.

With 12 points we have:

12!/9!3! = 220 9-sets.

Each of those 9-sets must have within them at least 2 5-sets that have even 4-sets.

So, looking at the 5-sets within 9-sets we need (if we can still achieve just 2),

220*2 = 440 5-sets within the 9-sets that have 3 even 4-sets.

However when we count all the 5-sets for 12 points as they appear in 9-sets we can note:

Each 5-set must appear within (12-5)!/(12-5-4)!4! 9 sets.
I.e. 7!/4!3! 9 sets = 35 9-sets.
However 440 is not divisible by 35, so we cannot achieve this minimum.

What is the next highest number of 5-sets with 3 even 4-sets allowed?
From our previous discussion we can see this is 7, and the lowest number of these
we can have is 3, since

3*7 + 217*2 = 455 = 13*35.

I.e. in 12 point set we need 3 9-sets with 7 5-sets that have 3 even 4-sets,
AND 217 9-sets with 3 5-sets that have 3 even 4-sets.

Anyway, 12 points is another step along the way. When we get to 12 points, we must have at least 3 9-sets each having at least 7 5-sets that have 3 even 4-sets. Phew!

How do we go on from here?
How about 13 points?
Again, same thing:

13!/10!3! = 286 9-sets.
Each 5-set must appear within (13-5)!(13-5-4)!4! 9 sets = 8!/4!4! = 70 9-sets.

But! We now have a big problem.
We require  :

2n1 + 7n2 + 12n3 + 17n4 + 22n5 + 27n6 + 32n7 + ... = 70N

where n1+n2+n3+... = 286.
Well, I'm no more of a number theorist than I am a combinatorialist (is there such a word?),
but when I try the left hand sum, I always get a number ending in 7 or 2 ???
Maybe someone out there can explain this, but IF there is no way of making this
sum be MOD 70, then 13 points is the magic number.
We will need at least one 5 set in 13 points to have all 5 of its 4-sets have even coloured 3-sets!!!

Funny that R3(4,4) =13 also?
Obviously this doesn't prove anything of the sort (if it makes any sense at all!!!).

Please don't give up on me! If it doesn't look correct put me out of my misery.
I can cope with being wrong, it's the not knowing that hurts....

Richard.

o.k. I'm wrong...
I can't count! I should have been using 13!/9!4! = 715.
This quite obviously has valid solutions.
Ah well, I knew it would happen...
Serves you all right for not helping me out!

Richard.


linear algebra
matrix
function
inequalities
geometry
3D geometry
absolute value

Given an $n \times n$ matrix such that $|a_{ij}| \le 1$ for $1 \le i,j \le n$, what is the maximum value of its determinant?

I remember from somewhere that the value is less than or equal to n^(n/2), but I can't remember ever seeing an analytic form for the function you're describing of n.

This is Hadamard's problem (1893). The upper bound is given by Brenner [i]et al.[/i] (1972).

$\lambda det(A,v_{2},v_{3}, \ldots, v_{n})+(1-\lambda) det(B,v_{2},v_{3}, \ldots, v_{n}) =det(\lambda A+(1-\lambda) B,v_{2},v_{3}, \ldots, v_{n})$. That shows that if the maximum is achieved at $(V_{1}, V_{2}, \ldots, V_{N})$, then every $V_{i}$ is a vertex of the unit cube.
PS: the upper bound is easy(Hadamard inequality) because $\|V_{i}\|_{2}= n^{\frac{1}{2}}$

The max is $n^{\frac{n}{2}}$  only if you can construct an Hadamard matrix of order $n$. The existence of a such matrix is unknown if, for example, $n=668$. (cf. Wikipedia: Hadamard matrix).

If $n\geq3$ and if $n$ isn't a divisor of 4 then there don't exist any Hadamard matrix. We have a look on the case $n=3$:
I think that the sup is 4 but I am not sure; if it's true then the sup (in absolute value) is obtained with the matrices: \[A=\begin{pmatrix}1&-1&-1\\-1&-1&-1\\-1&-1&1\end{pmatrix},B=\begin{pmatrix}u&-1&-1\\-1&-1&1\\-1&1&-1\end{pmatrix}\]
The first $B$-column isn't a vertex of the unit cube.

Now I understand the Alekk's post: he proved that a point $M$ in the convex cube can be joined, by a line (a straightline by parts), to a vertex $S$ s.t. $det(M,v_{2},\cdots,v_{n})\leq{det(S,v_{2},\cdots,v_{n})}$. Thus the required max, $a[n]$, is reached (between others) by a det., each column of which being a vertex of the unit cube.
Moreover it's easy to see that $2^{n-1}$ is a divisor of $a[n]$ and it's known that $a[n]\leq{n^{n/2}}$ with equality if 4 is a divisor of $n$ and if $n<668$. Thus we obtain easily $a[i]$ for  $i\leq5$.
  Here the $a[n]$'s values until $n=18$:
  cf:"mathworld, Hadamard matrix" and
 http://www.research.att.com/~njas/sequences/A003433

n  a(n)
1  1
2  2
3  4
4  16
5  48
6  160
7  576
8  4096
9  14336
10  73728
11  327680
12  2985984
13  14929920
14  77635584
15  418037760
16  4294967296
17  21474836480
18  146028888064


In $ \triangle{DEF}$, $ G$ and $ H$ are two points on sides $ EF$ and $ DF$, respectively. Given that $ EG: GF\equal{}4: 6$ and $ DH: HF\equal{}2: 5$, find $ DJ: DG$ if $ J$ is the intersection of $ \bar{EH}$ and $ \bar{DG}$.

Assign a mass of 10 to F. Then, D has a mass of 25, E has a mass of 15, H has a mass of 35, G has a mass of 25.

Therefore, we have DJ:JG = 1:1, of DJ:DG = 1:2


hello,

solve in $ \mathbb{R}$ the equations :
\[ i)\; \lfloor x \rfloor \equal{} x^4 \minus{} 2x^2\]\[ ii)\; x\Big| 3 \minus{} \big|x \plus{} 5\big|\Big| \equal{} x^2\]
Solve in $ \mathbb{N}^2$ the equation :  \[ 2^{\frac{x\minus{}y}{y}} \minus{} \frac{3}{2}y \equal{} 1.\]

[hide="Problem (i)"]$ (x^2\minus{}1)^2\equal{}\lfloor x\rfloor\plus{}1$, hence $ \lfloor x\rfloor\geqslant \minus{}1$

For $ \lfloor x\rfloor\equal{}\minus{}1$ we get $ x^2\minus{}1\equal{}0\implies x\equal{}\minus{}1$

For $ \lfloor x\rfloor\equal{}0$ we get $ |x^2\minus{}1|\equal{}1\implies x\equal{}0$

Hence we study $ x\geqslant 1$. Put $ \lfloor x\rfloor \equal{}n$. Then $ (x^2\minus{}1)^2\equal{}n\plus{}1\iff x\equal{}\sqrt{1\plus{}\sqrt{n\plus{}1}}$. By the definition of $ n$, we must have $ n\leqslant\sqrt{1\plus{}\sqrt{n\plus{}1}}$. That yields $ n^3\minus{}2n\minus{}1\leqslant 0$, but this obviously can be satisfied only for $ n\equal{}1$, yielding $ x\equal{}\sqrt{1\plus{}\sqrt{2}}$, which we check as a solution - it's easy to show $ \left\lfloor\sqrt{1\plus{}\sqrt{2}}\right\rfloor\equal{}1$.

Hence $ x\in\left\{\minus{}1,0,\sqrt{1\plus{}\sqrt{2}}\right\}$[/hide]

[hide="Problem (ii)"]For $ x<0$ there's no solution. For $ x\equal{}0$ the equation is satisfied. For $ x>0$ we have $ |3\minus{}(x\plus{}5)|\equal{}x\iff |x\plus{}2|\equal{}x\iff x\plus{}2\equal{}x$, which has no solution. Therefore $ x\equal{}0$ is the unique solution.[/hide]

[hide="Problem (iii)"](If $ \mathbb{N}$ includes zero, it's irrelevant in this problem since $ y\neq 0$ and we check $ x\equal{}0$ can't yield a natural solution for $ y$)

$ 2^{x/y}\minus{}3y\equal{}2\iff 2^x\equal{}(2\plus{}3y)^y$

Therefore $ 2\plus{}3y\equal{}2^k$ for some natural $ k$. Then $ y\equal{}{2\left(2^{k\minus{}1}\minus{}1\right)\over 3}$, so $ 2^{k\minus{}1}\equiv 1\pmod{3}$, but $ 2^{k\minus{}1}\equiv(\minus{}1)^{k\minus{}1}\pmod{3}$, so $ k\equal{}2n\plus{}1, n\geqslant 1$. (The possibility $ n\equal{}0$ is excluded as it would give $ y\equal{}0$.)

Hence $ y\equal{}{2\left(2^{2n}\minus{}1\right)\over 3}\implies 2^x\equal{}\left(2^k\right)^y\implies x\equal{}ky\equal{}{2(2n\plus{}1)\left(2^{2n}\minus{}1\right)\over 3}$

So all pairs are $ (x,y)\equal{}\left({2(2n\plus{}1)\left(2^{2n}\minus{}1\right)\over 3}, {2\left(2^{2n}\minus{}1\right)\over 3}\right),n\geqslant 1$[/hide]


Determine the units digits of the product of the first $2006$ prime numbers.

[quote="Farenhajt"]Well, since 2 and 5 are there, it's 0.[/quote]

We can generalize further:  Call $p_k$ the $k^{th}$ prime.  Then in any base $b$ such that $p_k | b \implies k \le 2006$ the units digit will still be $0$.

 :rotfl:

[quote="t0rajir0u"]
We can generalize further:  Call $p_k$ the $k^{th}$ prime.  Then in any base $b$ such that $p_k | b \implies k \le 2006$ the units digit will still be $0$.

 :rotfl:[/quote]

Very useful generalization, don't you think?  :rotfl:


Let $\beta=\frac{\alpha}{\pi}.$

If $\beta$ is irrational, the sup is 1.
If $\beta$ is rational with (in lowest terms) an even denominator, then the sup is the max is 1.
If $\beta$ is rational with a large odd denominator, then the sup is close to 1.

What we need is the smallest possible odd denominator for $\beta.$ But note that since we can't have $\alpha=\pi,$ then we have ruled out a denominator of $1.$

The desired smallest supremum is $\frac{\sqrt{3}}2,$ which is realized when $\alpha = \frac{\pi}3$ or $\alpha=\frac{2\pi}3.$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=116847]Same old, same old[/url]


Let $ a,b$ such that
$ 0<b\leq a\leq 4$
$ a\plus{}b\leq 7$
Find the maximum $ P\equal{}a^2\plus{}b^2$

use graphis   we have
$ f_{max} \equal{}  max(f(4,3);f(3,5;3,5)) \equal{}25$

This problem is very easyand a solution is very nice!
We have
$ A\equal{}a^2\plus{}b^2\equal{}a(a\minus{}b)\plus{}b(a\plus{}b)\le 4(a\minus{}b)\plus{}7b\equal{}4a\plus{}3b\equal{}3(a\plus{}b)\plus{}a\le 3.7\plus{}4\equal{}25$
So, $ maxA\equal{}25$ when $ a\equal{}4,b\equal{}3$ :D
____________________
Nguyen The Cuong
 :rotfl:  :rotfl:  :rotfl:
You....teacher... :D


$ f: R \rightarrow R$ and $ a \in (0,\frac {1}{2})$ s.t.
$ f(\frac {x \plus{} y}{2})\leq af(x) \plus{} (1 \minus{} a)f(y)$ and $ |f(x)|\leq x$ for any $ x,y \in R$
Show that f=0.
__________________________
Mihai Piticari, RMO Shortlist 2005

If $ x<0$ , then the condition $ |f(x)|\leq x$ doesn't hold .Is this the real statement ?

[quote="Svejk"]If $ x < 0$ , then the condition $ |f(x)|\leq x$ doesn't hold .Is this the real statement ?[/quote]
that's how i found it. :| .i found it in the RMO shortlist 2005
i suppose the statement is $ |f(x)|\leq|x|$  :maybe:


[quote="manlio"]It was already posted by Vasc in the topic "Nice" together other inequalities.

As I cannot solve it directly I post it again with own topic

$(a+b)(b+c)(c+a) \ge 2 \sqrt{(a^2+bc)(b^2+ca)(c^2+ab)}$[/quote]
I think this inequality  should be $(a+b)(b+c)(c+a) \ge 2 \sqrt{2(a^2+bc)(b^2+ca)(c^2+ab)}$

[quote="manlio"]It was already posted by Vasc in the topic "Nice" together other inequalities.

As I cannot solve it directly I post it again with own topic

$(a+b)(b+c)(c+a) \ge 2 \sqrt{2(a^2+bc)(b^2+ca)(c^2+ab)}$[/quote]

Using SOS, the problem is not hard. But I think there exists a similaer one.

Manlio, the initial form of the problem is correct; that is

$(a+b)(b+c)(c+a) \ge 2 \sqrt{(a^2+bc)(b^2+ca)(c^2+ab)}$.

Equality occurs for $a=0$ and $b=c$.

[quote="manlio"]
$(a+b)(b+c)(c+a) \ge 2 \sqrt{2(a^2+bc)(b^2+ca)(c^2+ab)}$[/quote]

Is it true ? :?

[quote="manlio"]

As I cannot solve it directly I post it again with own topic

$(a+b)(b+c)(c+a) \ge 2 \sqrt{(a^2+bc)(b^2+ca)(c^2+ab)}$[/quote]

$(a+b)(b+c)(c+a) \ge 2 \sqrt{(a^2+bc)(b^2+ca)(c^2+ab)}\Leftrightarrow$
$\Leftrightarrow(a-b)^2(a-c)^2(b-c)^2+4\cdot\sum_{sym}a^3b^2c+8a^2b^2c^2\geq0.$ :)

A nice solution for

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

is to consider $a \geq b \ge c$ and to use the inequality $a+c \geq \sqrt{a^2+bc}$.

Can anyone complete Vasc solution?

Thank you.

We have that  $ab+ac+b^2+bc\geq b^2+c^2+ca+ab\geq 2\sqrt{(b^2+ca)(c^2+ab)}$  by AM-GM  ;)

Very nice, silouan and vasc. We have very short solution to a hard and nice inequality. Congratulations!


Lol !
WE learnt these type of problems in 7th grade. ( Inverse Variations)

P.S. : What is AHSME??

American High School Mathematics Examination. see here: http://www.artofproblemsolving.com/Wiki/index.php/American_High_School_Mathematics_Examination


algebra polynomial inequalities calculus derivative trigonometry function

Prove that there exists constant real number $c$ such that:
$\displaystyle \max_{0 \leq x \leq 2}\prod_{j=1}^n|x-a_j| \leq c^n\max_{0 \leq x \leq 1}\prod_{j=1}^n|x-a_j|$

This is a super-problem. Where did you find it? I guess that c must be independent of $ a_i $, otherwise the problem is trivial. I think I have a proof. I found that $ c=4e $ is a good constant. Indeed, let us take a monic polynomial of degree n, f(x) such that $ M=max_{0\leq x\leq 1}|f(x)| $. We want to prove that for $ 0\leq x\leq 1$ we have $ |f(x+1)|\leq (4e)^n\cdot M $. Take the numbers $ x_k=\frac{k}{n} $ for $k=0,1,,n$. Write the Lagrange interpolation formula for these nodes and apply the triangular inequality, majorizing each $ |f(x_k)| $ with M and each product $ (x-x_1+1)(x-x_n+1) $ with $ 2^n $. If Im not wrong, youll find that $|f(x+1)|\leq \frac{4^n\cdot n^n}{n!} $ . Since $ n!>(\frac{n}{e})^n $ , I think we are done. Or at least I hope so.

A very nice solution, but why do you say?

[quote="harazi"] I guess that c must be independent of $ a_i $, otherwise the problem is trivial.[/quote]

Sorry, if I am so idiot not to undestand what you say.

If a_i are fixed, then of course there is such a constant, but it may depend on a_i. The idea is that this constant really doesn't depend on a_i, which is magnificient.

What to try? Have you read the solution? Isn't it good?

[i] [size=150]Indeed, this is a nice question ![/i][/size]

[size=150] [b] If $ x_1,x_2,...,x_n $ are the roots of a polynomial with real coefficients, then
\[
\max\limits_{x\in [0,2]}{\prod\limits_{k=1}^{n}|x-x_k|}\le
\left(5+2\sqrt{6}\right)^n\cdot \max\limits_{x\in
[0,1]}{\prod\limits_{k=1}^{n}|x-x_k|}\; ,
\]
[/b][/size]
[b] Solution:[/b]
In the following let  $ -\infty< a<b<\infty , $ and

 $ {\mathcal P} $= linear space of all complex polynomials,

 $ {\mathcal P}_n $= the set of algebraic polynomials $\; p\; $ of degree at most $ n $ ,

 $ D $ =the derivative defined on $ {\mathcal P} $ ,

$ T_n $ = the Chebychev polynomial of the first kind, defined for $ t\in [-1,1] $ by $ T_n(t)=\cos\left(n\cdot \arccos{t}\right)\; .\;  $ Another representation of $ T_n  $ is
\[(1)\hspace*{0.5cm}
T_n(x)=\frac{1}{2}\left( \;  \left(x+\sqrt{x^2-1}\right)^n\; +\;
\left(x-\sqrt{x^2-1}\right)^n \; \right)\; \; ,\; \; \forall x\in
{\mathbb  R} \; .
\]
Let us remind that $ T_0(x)=1 ,T_1(x)=1 $ and $
T_n(x)=2^{n-1}x^n+\ldots \; ,\; n\ge 1. $
 All the roots of  $ T_n $ are in   [-1,1] ,  and $ T_n> 0 $ on  [1,$\infty$) .  Moreover $ T_n $ is an increasing function on [1,$\infty$).

 For $ f \in {\mathcal P} $ let us consider following norm $ ||f||_{[a,b]} =\max\limits_{x\in [a,b]}|f(x)|. $ I use following known facts :

[b]1)[/b] Taylor-formula for polynomials $p\in {\mathcal P}_n $:
$\hspace*{0.5cm}(2)\hspace*{1cm}\hspace*{1cm} p(x)=\sum\limits_{k=0}^{n}\frac{(x-x_0)^k}{k!}
\left(D^kp\right)(x_0 ). $

[b]2)[/b] According to an inequality attributed to W.Markoff (see  the beautiful monographs  [1] , [2], (  3.3.32 ,page 229 ) or [3]: [i]  if $\; P\; $ is a complex  polynomial of the degree $\; \le n $ \ with the property $ |P(x)|\le 1 \;  ,\; \; \forall x\in [-1,1]\; , $ then for  $k=1,2,...$ and all  $ x\in [-1,1]$
\[ (*)\hspace*{1cm} \left|\left(D^kP\right)(x) \right| \le \frac{n^
2\left(n^2-1\right)...
\left(n^2-(k-1)^2\right)}{(2k-1)!!}=\left(D^kT_n\right)(1)\; . \]
[/i]
Of course, here is a  question ! How we prove the equality from RHS of (*) ? Try  to find a proof.

 By means of the linear transformation $\; p(x)= P\left(\frac{2x-a-b}{b-a}\right)\; , $ it may be seen that the above Markoff result may be reformulated as :

 [b] 1.1)    If  $\; p\in {\mathcal P} $  is  of the degree at most $n$  ,   then for $k=0,1,...$ and all $ x\in [a,b] $
\[(3)\hspace*{1cm}\hspace*{1cm} \left|\left(D^kp\right)(x)\right|\le
 \left(\frac{2}{b-a}\right)^k \cdot ||p||_{[a,b]}\cdot \left(D^kT_n\right)(1)\; \;
 .
\]
 In (3) the equality cases hold for $\; p(x)=T_n\left(\frac{2x-b-a}{b-a}\right)\; $ and $ x=a $ or $x=b .$
[/b]

[b] THEOREM.[/b]  [i] Suppose that $\; p\in  {\mathcal P}_n\; .\; $ Then for $x_0\in[a,b] \; $ and  any positive $h$
\[
(4)\hspace*{1cm} \hspace*{1cm} |p(x_0+h)|\le
T_n\left(1+\frac{2h}{b-a}\right)\cdot ||p||_{[a,b]}\; .
\]
The equality case is verified for $\;
p(x)=T_n\left(\frac{2x-a-b}{b-a}\right)\; ,x_0=a
 \; $ or $x_0=b\; .$
[/i]

[b] Proof.[/b] Using  Taylor formula and (3) , one finds
\[|p(x_0 +h)|=\sum\limits_{k=0}^n \frac{|\left(D^kp\right)(x_0)|
}{k!}h^k\le ||p||_{[a,b]} \sum\limits_{0}^n\frac{1}{k!}
 \left( \frac{2h}{b-a}\right)^k \left( D^kT_n \right)(1) =\]
\[=T_n\left(1+\frac{2h}{b-a}\right)\cdot ||p||_{[a,b]} .
\]
Now suppose [a,b]=[0,1]  , $\; x_0=0 , $ and let $ x^* \in [0,2]$ such that  $ |p(x^*)|=\max\limits_{z\in [0,2]}|p(z)|\; . $ If $ h = x^* $, using (4) we give
\[
||p||_{[0,2]}\le  T_n\left(1+ 2x^*\right)\cdot ||p||_{[0,1]}\; .
\]
Because $ 1\le 1+2x^* \le 5 $ we have $ T_n(1+2x^*)\le T_n(5).  $ Using identity (1)  we conclude with
\[
||p||_{[0,2]}\le  T_n\left(5\right)\cdot ||p||_{[0,1]}=
\frac{1}{2}\left( \;  \left(5+2\sqrt{6}\right)^n\; +\;
\left(5-2\sqrt{6}\right)^n \; \right)\cdot ||p||_{[0,1]} .
\]
Therefore $ ||p||_{[0,2]}\le  c^n ||p||_{[0,1]} $ with $ c:=
\left(5+2\sqrt{6}\right)^n\; . $  If we put  $ p(x)=\prod\limits_{k=1}^{n}(x-x_k) $ , we may write
\[
\max\limits_{x\in [0,2]}{\prod\limits_{k=1}^{n}|x-x_k|}\le
\left(5+2\sqrt{6}\right)^n\cdot \max\limits_{x\in
[0,1]}{\prod\limits_{k=1}^{n}|x-x_k|}\; ,
\]
which is a solution of the problem. Note that $5+2\sqrt{6}<9.45 $

                  [b] REFERENCES:[/b]

[1] G.V.Milovanovic , D.S. Mitrinovic, Th.M. Rassias , [b] Topics in Polynomials:[/b]  [i] Extremal Problems, Inequalities, Zeros[/i], World Scientific ,  1994.
[2] D.S.Mitrinovic , ( in cooperation with P.M.Vasic)},  [b]Analytic Inequalities[/b], Springer Verlag ,Grundlehren der math.Wissenschaften, Band 1656,Berlin, 1970.
[3] T.J.Rivlin ,[b]  The Chebychev Polynomials[/b], John Wiley,New York,1974,page 93.

Perhaps help,regards,Alex.


Is it OK if I use the template for the solutions, print them, draw diagrams, and then scan them again?

You could also use Asymptote for diagrams.


Hey, I am currently in College.  Though I am in College, I've never studied Number Theory.  I'd like to know if it would serve me to even study the AoPS Number Theory book, or perhaps I should stick to Undergraduate level texts.  I am pretty sure that the AoPS book would still prove to be somewhat a challenge, but I just want an honest opinion so I can save myself some money.

This is the text I am currently interested in:  Elementary Number Theory by Gareth Jones
http://www.amazon.com/Elementary-Number-Theory-Gareth-Jones/dp/3540761977/ref=pd_sim_b_title_4

I also have Apostol's Number Theory text in mind:  Introduction to Analytic Number Theory
http://www.amazon.com/Introduction-Analytic-Number-Undergraduate-Mathematics/dp/0387901639/ref=pd_sim_b_title_6

I think [url=http://www.artofproblemsolving.com/Forum/index.php?f=319]this[/url] is a more appropriate forum.

Sorry, I can't help you.


Z is a complex number satisfying the conditions

I Z-1 I<=1   and  I Z-i I<=1

Find the maximum value of IZI

From the two inequalities, we have (with $Z = a+bi$):

$(a-1)^2+b^2 \le 1$
$a^2+(b-1)^2 \le 1$

so obviously $a, b \le 1$. Then the maximum of $|Z| = \sqrt{1^2+1^2} = \sqrt{2}$, where $a=b=1$.

EDIT: sorry, forgot square root

Well, really |Z|=sqrt(2), but that's just a little change.


modular arithmetic
number theory
relatively prime

Let $p_1, p_2, \ldots$ be a sequence of primes such that $p_1 =2$ and for $n\geq 1, p_{n+1}$ is the largest prime factor of $p_1 p_2 \ldots p_n +1$ . Prove that $p_n \not= 5$ for any $n$.

[hide]The expression $p_1p_2\cdots p_n+1$ will be relatively prime with any $p_k$ where $k$ ranges from $1$ to $n$, because $p_1p_2\cdots p_n+1\equiv 1\mod{p_k}$ for any such $k$. Since $p_1=2$ and $p_2=3$, $p_1p_2\cdots p_n+1$ will not be divisible by either 2 or 3 for $n\geq 2$. This also means that only one of the $p_k$ will be 2.

Since only the largest prime factor of $p_1p_2\cdots p_n+1$ is chosen, it will have to be a power of 5 for $p_{n+1}$ to equal 5. But $5^a\equiv 1\pmod{4}$ for any $a$ so $p_1p_2\cdots p_n$ would have to be divsible by 4. This is a contradiction, since there is only one factor of 2. Therefore 5 can never be the largest prime factor.[/hide]

Same question as Iberoamerican 1987 question.

What's Iberoamerican?is it here in aops?and plz don't post off topic..

Assuming, on the contrary, that $p_n=5$ for some n.
Therefore, no prime $>5$ divides $p_{n-1} \implies p_{n-1}=2^x3^y5^z$. But, $p_1=2, p_2=3, p_3=7$ and for all $i\geq 4$, $2\mid p_1p_2\cdots p_i \implies 2\nmid p_1p_2\cdots p_i+1$
Also, $3\mid p_1p_2\cdots p_i \implies 3\nmid p_1p_2\cdots p_i+1$
Thus we can conclude that for $n\geq 4$, $2\nmid p_n$, $3\nmid p_n$ and thus, $p_n$ must be a power of $5$.

But, then, $p_1p_2\cdots p_{n-1}=5^z-1 \implies 4\mid p_1p_2\cdots p_{n-1}$. But only one of the $p_is$ can be equal to $2$, and we have a contradiction! Therefore, $p_n \not= 5$ for any $n$.  :play_ball:


In the town with the population of 10^5 people, there is an infectious disease.So far there has been 1% of the residents being infected.
Provided that there is a testing centre which can test up to 10^4 samples per day.

 the centre can test either a combination of  blood samples or separate ones

however , if there is more than 1 infectious sample in a m-sized sample (n>m>1), the result will be wrong.else, if there is 0 or 1 infectious sample in a m-sized sample, the result will be correct.

How many days does it take to find out all the infected people

So you can test as many samples as you want.

If there is 0 samples result= disease-free

1 sample= Disease

2+ samples=Disease-free

Is this a correct interpretation?

Needless to say, we can find the maximum possible answer is 10. This could narrow down our search.

[quote="mewto55555"]So you can test as many samples as you want.

If there is 0 samples result= disease-free

1 sample= Disease
[b]
2+ samples=Disease-free[/b]

Is this a correct interpretation?

Needless to say, we can find the maximum possible answer is 10. This could narrow down our search.[/quote]

Not necessarily. Say $ 5$ people were found infected; the actual result could be anything. Of course, that's my interpretation. With mewto's interpretation, $ 10$ is the answer, as we must assume the worst case. With mine, it would take at most $ 10^5 \minus{} 0.01\cdot10^5 \equal{} 99000$ tests.

to clarify , i will explain it once again:

1/ 0 infected person's blood sample in a  sample of size m --> result " positive"
2/ 1 infected person's blood sample in the whole sample of size m  (m>=1)--->" negative" , without inform the infected person's name
3/ >=2 infeted people's blood samples in the whole sample of size m(m>=2)--->"negative"

so far no answer given by u two is correct. keep on trying

Take 50000 tests with 2 people per tests. This takes 5 days. 1000 will be found infected (at most). then we divide those up for 2000 which take 1/5 of a day so 5.2?


Hi!
Is there any official site of IMO 2005?
Good luck to all the teams, especially, the Moldavian and the Romanian!

Have a look [url=http://erdos.fciencias.unam.mx/]here.[/url] So go and practice in order to be on the Moldavian team next year.  :)

thanks.
hope i'll be next year in the team!
i think imo 2006 will be in slovenia.

best of luck to bekjan jumabaev (hardsoul) and the whole Kyrgyzstan team at the IMO 2005!!!!!!!

do you know the points of all paticipants???
there is a friend of mine in china team.

full results here:

http://erdos.fciencias.unam.mx/results.htm

team scores:

china 235
usa 213
russia 212
iran 201
korea 200

UNITED STATES OF AMERICA
Score P1 P2 P3 P4 P5 P6 Final Medal
USA1 5  7  7  7  3  7  36  Gold
USA2 1  7  0  7  7  6  28  Silver
USA3 1  1  7  7  7  4  27  Silver
USA4 7  7  7  7  7  4  39  Gold
USA5 7  7  7  7  7  7  42  Gold
USA6 6  7  7  7  7  7  41  Gold
TOTAL 213

gold: 35---42
silver:23---34
bronze: 12---22

16 total perfect scores

who are those ppl in the US team, like who is who?

http://www.unl.edu/amc/e-exams/e9-imo/e9-1-imoarchive/2005-ia/2005imoresults.html

A sophomore got perfect score. Unbelievable :O

Not really, or at least considering that's Bryan Lawrence.

Hello. Does anyone know why "official results" are off and preliminary results are on, and why scores of some of the problems of different teams were removed?
Example:
Mexico got a perfect P4 as a team (all members 7) but today those scores are no longer there. I guess that given Mexico was the "weakest" country getting a perfect P4, it was subject to some kind of doubt.
Well, any thoughts on this or help would be appreciated.

Victor

[quote="jerry_science"]who are those ppl in the CHINESE team?[/quote]
Check the Chinese community.


[quote="No Reason"][quote="can_hang2007"]Let $ a,b,c$ be nonnegative real numbers, no two of which are zero. Prove that
1)
\[ 2\left( \frac {a^2 \plus{} bc}{b^2 \plus{} c^2} \plus{} \frac {b^2 \plus{} ca}{c^2 \plus{} a^2} \plus{} \frac {c^2 \plus{} ab}{a^2 \plus{} b^2}\right) \plus{} \frac {a^2 \plus{} b^2 \plus{} c^2}{ab \plus{} bc \plus{} ca} \ge 7
\]
2)
\[ 4\left( \frac {a^2 \plus{} bc}{(b \plus{} c)^2} \plus{} \frac {b^2 \plus{} ca}{(c \plus{} a)^2} \plus{} \frac {c^2 \plus{} ab}{(a \plus{} b)^2}\right) \ge 3 \plus{} \frac {3(a^2 \plus{} b^2 \plus{} c^2)}{ab \plus{} bc \plus{} ca}
\]
Equality holds if and only if $ a \equal{} b \equal{} c$ or $ a \equal{} b,c \equal{} 0$. :)

PS: 2) was posted by Ji Chen. :)[/quote]

I think we can kill the first problem by S.O.S method. :blush:[/quote]
You are right. :) And the second?

[quote="can_hang2007"]Let $ a,b,c$ be nonnegative real numbers, no two of which are zero. Prove that
1)
\[ 2\left( \frac {a^2 \plus{} bc}{b^2 \plus{} c^2} \plus{} \frac {b^2 \plus{} ca}{c^2 \plus{} a^2} \plus{} \frac {c^2 \plus{} ab}{a^2 \plus{} b^2}\right) \plus{} \frac {a^2 \plus{} b^2 \plus{} c^2}{ab \plus{} bc \plus{} ca} \ge 7
\]
2)
\[ 4\left( \frac {a^2 \plus{} bc}{(b \plus{} c)^2} \plus{} \frac {b^2 \plus{} ca}{(c \plus{} a)^2} \plus{} \frac {c^2 \plus{} ab}{(a \plus{} b)^2}\right) \ge 3 \plus{} \frac {3(a^2 \plus{} b^2 \plus{} c^2)}{ab \plus{} bc \plus{} ca}
\]
Equality holds if and only if $ a \equal{} b \equal{} c$ or $ a \equal{} b,c \equal{} 0$. :)

PS: 2) was posted by Ji Chen. :)[/quote]
VasC, do you have a nice solution for them? :)

[quote="Honey_S"][quote="can_hang2007"]Let $ a,b,c$ be nonnegative real numbers, no two of which are zero. Prove that
1)
\[ 2\left( \frac {a^2 \plus{} bc}{b^2 \plus{} c^2} \plus{} \frac {b^2 \plus{} ca}{c^2 \plus{} a^2} \plus{} \frac {c^2 \plus{} ab}{a^2 \plus{} b^2}\right) \plus{} \frac {a^2 \plus{} b^2 \plus{} c^2}{ab \plus{} bc \plus{} ca} \ge 7
\]
2)
\[ 4\left( \frac {a^2 \plus{} bc}{(b \plus{} c)^2} \plus{} \frac {b^2 \plus{} ca}{(c \plus{} a)^2} \plus{} \frac {c^2 \plus{} ab}{(a \plus{} b)^2}\right) \ge 3 \plus{} \frac {3(a^2 \plus{} b^2 \plus{} c^2)}{ab \plus{} bc \plus{} ca}
\]
Equality holds if and only if $ a \equal{} b \equal{} c$ or $ a \equal{} b,c \equal{} 0$. :)

PS: 2) was posted by Ji Chen. :)[/quote]

For the first we can prove that for $ a,b,c$ which are real numbers we have

$ 2\left( {\frac {{a^2 \plus{} bc}}{{b^2 \plus{} c^2 }} \plus{} \frac {{b^2 \plus{} ca}}{{c^2 \plus{} a^2 }} \plus{} \frac {{c^2 \plus{} ab}}{{a^2 \plus{} b^2 }}} \right) \ge 3 \plus{} \frac {{\left( {a \plus{} b \plus{} c} \right)^2 }}{{ab \plus{} bc \plus{} ca}}$[/quote]
This inequality is not true, Loc. For example $ a\equal{}b,c\equal{}0$

[quote="can_hang2007"]Let $ a,b,c$ be nonnegative real numbers, no two of which are zero. Prove that
1)
\[ 2\left( \frac {a^2 \plus{} bc}{b^2 \plus{} c^2} \plus{} \frac {b^2 \plus{} ca}{c^2 \plus{} a^2} \plus{} \frac {c^2 \plus{} ab}{a^2 \plus{} b^2}\right) \plus{} \frac {a^2 \plus{} b^2 \plus{} c^2}{ab \plus{} bc \plus{} ca} \ge 7
\]
2)
\[ 4\left( \frac {a^2 \plus{} bc}{(b \plus{} c)^2} \plus{} \frac {b^2 \plus{} ca}{(c \plus{} a)^2} \plus{} \frac {c^2 \plus{} ab}{(a \plus{} b)^2}\right) \ge 3 \plus{} \frac {3(a^2 \plus{} b^2 \plus{} c^2)}{ab \plus{} bc \plus{} ca}
\]
Equality holds if and only if $ a \equal{} b \equal{} c$ or $ a \equal{} b,c \equal{} 0$. :)

PS: 2) was posted by Ji Chen. :)[/quote]
Here is my solution :)
I am looking for your ideas


Twenty percent of the total cost of publishing the school newspaper during the academic year was the cost of the paper, while eighty percent was the cost of the printing. Over the following summer, the cost of paper increased by twenty percent, while the cost of printing decreased by twenty percent. By what percent did the total cost of publishing the paper decrease?

[hide]Call the total cost n. Then the paper costs .2n and the printing .8n. If the paper cost increased by 20%, it would be .24n. If the printing cost decreased by 20%, the cost would be .64n. .24n+.64n equals .88n, which is a 12% decrease from 1n.[/hide]


After applying some simple algebra to some trite phrases and cliches a new
understanding can be reached of the secret to wealth and success.

Here it goes.

         Knowledge is Power
         Time is Money and as every engineer knows,
         Power is Work over Time.

So, substituting algebraic equations for these time worn bits of wisdom,
we get:
        K = P    (1)
        T = M    (2)
        P = W/T  (3)

Now, do a few simple substitutions:

        Put W/T in for P in equation (1), which yields:
        K = W/T  (4)

Put M in for T into equation (4), which yields:

        K = W/M  (5).

Now we've got something. Expanding back into English, we get:

        Knowledge equals Work over Money.

What this MEANS is that:

        1. The More You Know, the More Work You Do, and
        2. The More You Know, the Less Money You Make.

Solving for Money, we get:

	M = W/K  (6)
	Money equals Work Over Knowledge.

From equation (6) we see that Money approaches infinity as Knowledge
approaches 0, regardless of the Work done.

What THIS MEANS is:

	The More you Make, the Less you Know.

Solving for Work, we get

	W = M K  (7)
	Work equals Money times Knowledge

From equation (7) we see that Work approaches 0 as Knowledge approaches 0.

What THIS MEANS is:

        The stupid rich do little or no work.

Working out the socioeconomic implications of this breakthrough is left as an
exercise for the reader.

Source: [url]http://userpages.umbc.edu/~dni1/humor/texts/math.shtml[/url]

[quote="Derek"]That's similar to the "girls are evil" math explaination.[/quote]

If you know that one, I'd love to hear it! :D

he-he, I remember last year in my Physics class my teacher derived the same thing.

I had loads of fun proving that 1 = 2 for a sub in math. When she said that this is not possible, i.e. one piece of paper is not equal to two, I ripped her piece of paper in half. :D

[quote="mcalderbank"]When she said that this is not possible, i.e. one piece of paper is not equal to two, I ripped her piece of paper in half. :D[/quote]

lol! That's great!

haha...the things we do to subs. ;)

Although, she could have argued that those would be two halves of the whole. But then again...can you really have half a piece of paper? I mean...you either have paper or you don't, right?

Lol. Here's the girls are evil one xD Which they are not, of course :P

Girls = time x money

We all know that time is money, so

Girls = money x money = money^2

We also know that money is the root of all evil, therefore

Girls = evil.

haha i like your conditions... man that's a great proof :D

or you could just say

$girls = \sum evil$
$girls^2 = (\sum evil)^2 = (-\sum good)^2 =(\sum good)^2$
$girls = \sum good$

a little quicker, perhaps.

no, because $\sqrt{\left(\sum\mbox{good}\right)^2}=\left|\sum\mbox{good}\right|$, not $\sum\mbox{good}$.

inteluser: Some people might require you to justify your assumption that girls are non-imaginary :P

Sly- I think you might want to consider getting out of the house a [i]bit[/i] more...

[quote="inteluser"]$\mbox{Girls} = \mbox{time} \cdot \mbox{money}$

$\mbox{time}=\mbox{money}$

$\mbox{Girls}=\mbox{money}^2$

$\mbox{money}=\sqrt{\sum{\mbox{evil}}}$

[tex]

\begin{eqnarray}
\mbox{Girls}&=&\left(\sqrt{\sum{\mbox{evil}}}\right)^2\nonumber\\
& = & \sqrt{\left(\sum{\mbox{evil}}\right)^2}\\
& = & \sqrt{\left(\mbox{evil}_1+\mbox{evil}_2+\ldots+\mbox{evil}_n\right)^2}\nonumber\\
& = & \sqrt{\left(\left(-\mbox{good}_1\right)+\left(-\mbox{good}_2\right)+\ldots+\left(-\mbox{good}_n\right)\right)^2}\nonumber\\
& = & \sqrt{\left(\left(-1\right)\left(\mbox{good}_1+\mbox{good}_2+\ldots+\mbox{good}_n\right)\right)^2}\nonumber\\
& = & \sqrt{\left(-1\right)^2\left(\mbox{good}_1+\mbox{good}_2+\ldots+\mbox{good}_n\right)^2}\nonumber\\
& = & \left|\sum{\mbox{good}}\right|\nonumber\\
\mbox{Girls} & = & \sum{\mbox{good}}
\end{eqnarray}
[/tex]

Note that eqn. 1 is valid if Girls are non-imaginary.
Note that eqn. 2 is valid if good is positive.[/quote]

The merits of a math forum!

So, inteluser, have you ever tried this as a pick-up line?

[quote="inteluser"]\begin{studMode}Never had too.\end{studMode}

Though I suppose it might work.  Anybody brave enough to try it?[/quote]
Same here :cool:

[quote="inteluser"]\begin{studMode}Never had too.\end{studMode}[/quote]\begin{CorrectionMode}Never had [b]to[/b].\end{CorrectionMode} :D

!!!!!

Ow ow ow ow ow ow ow ow ow ow ow....

Sorry; I don't usually do that.  **sigh** that's [i]another[/i] dollar...

[u]To[/u] [i]tow[/i] is [u]too[/u] [u]two[/u]-dimensional [u]to[/u] do [u]for[/u] long. [u]For[/u] my [u]Too[/u]th, I [u]ate[/u] [i]toe[/i][u]s, even[/u], [u]to[/u] avoid it.

All better now!


From 1997 AIME #3

M is a 2-digit number ab, and N is a 3-digit number cde. We have 9MN = abcde. Find M and N.

Our math chat wrangled with this one for a while, but we didn't come up with an answer.  Kalva's solution is confusing.  Anyone have any ideas?

The key is to look at the problem as:

[hide]9*M*N=1000M+N.

Then 9M divides 1000M+N = 999M + (M+N)

so 9M divides M+N.  From there we guess that

N = 8M.  If so, then the original equation simplifies to

72M*M = 1008M.

This results in M=14 and N=112.

We check to see that in fact 9*14*112 = 14112.

I'm not sure if there is good justification for guessing that N=8m.

It is true that N=(9k-1)M for some k with 1<=k<=11, but why does k=1?

[/hide]

--Dan

Dan -- if you wanted to prove [hide]k = 1, just go back to the step where you took N = 8M and take N = (9k - 1)M.  Plug that in and work it through to get M = (111 + k)/(9k - 1).  By the time k = 2, we're into 1-digit numbers, so it has to be 1.[/hide]

Here is how I did it: 9MN=1000M+N. Rewrite the equation we have 5M(N-200)=N(1-4M).
(1000M+N)/N= an positive integer, then 1000M must be divisible by N, also N is a multiple of M.  Put N=kM.Since 1-4M is obviously negative, then N must be less than 200 but greater than 100We have ab1de/ab=an integer X>1000 but <1100.  Then 111<N<123.   So k<12. k is a divisor of 1000 since1000M is divisible by N. So the possible values of k are 2,4,5,8,10. 5M(N-200)=kM(1-4M). Simplifying 9kM=1000+k. the only possible value of k is 8 since 1008 is the only possible value of 1000+k which divisible by 9. Solve the equation we haveM=14,N=112.


[quote="sonny"][quote="#H34N1"]In the figure below, the shaded region is formed by drawing two parallel segments which connect the midpoints of congruent squares. Each square has side length 1 centimeter. What is the number of square centimeters in the shaded region? Express your answer as a common fraction.

[img]7216[/img][/quote]
[hide]Is the answer $\frac{5}{4}$? [/hide][/quote]
I am not sure if my method is right, but I get a different answer than you.  I get 1 as the answer.
[hide] Say the big (nonshaded) figure is called ABCDEFGHIJKL with A at the topmost part of the figure to the left, and the succeeding letters are in order clockwise after A.  Say the midpoints of AL is M, of KL is N, of EF is P, and of FG is Q.  We know that IF and IL will trisect NQ.  Using this, we can figure out that \[NQ=3(.5\sqrt{2})=1.5\sqrt{2}=MP\]  Now, we can also figure out that \[MN=.5\sqrt{2}=PQ\]  From here, we can connect M, N, P, and Q to form a rectangle with a length of $1.5\sqrt{2}$ and a width of $.5\sqrt{2}$, thus having an area of $(2)(.5)(1.5)=1.5$.  We can also find the area of Triangles MNL and Triangle PFQ is $\frac{(2)(.5)(.5)}{2}=\frac{.5}{2}=.25$.  Thus, the area of the rectangle minus both of the triangles is 1.5-.25-.25=$1$ [/hide]

[quote="The QuattoMaster 6000"][quote="sonny"][quote="#H34N1"]In the figure below, the shaded region is formed by drawing two parallel segments which connect the midpoints of congruent squares. Each square has side length 1 centimeter. What is the number of square centimeters in the shaded region? Express your answer as a common fraction.

[img]7216[/img][/quote]
[hide]Is the answer $\frac{5}{4}$? [/hide][/quote]
I am not sure if my method is right, but I get a different answer than you.  I get 1 as the answer.
[hide] Say the big (nonshaded) figure is called ABCDEFGHIJKL with A at the topmost part of the figure to the left, and the succeeding letters are in order clockwise after A.  Say the midpoints of AL is M, of KL is N, of EF is P, and of FG is Q.  We know that IF and IL will trisect NQ.  Using this, we can figure out that
\[NQ=3(.5\sqrt{2})=1.5\sqrt{2}=MP \]
Now, we can also figure out that
\[MN=.5\sqrt{2}=PQ \]
From here, we can connect M, N, P, and Q to form a rectangle with a length of $1.5\sqrt{2}$ and a width of $.5\sqrt{2}$, thus having an area of $(2)(.5)(1.5)=1.5$.  We can also find the area of Triangles MNL and Triangle PFQ is $\frac{(2)(.5)(.5)}{2}=\frac{.5}{2}=.25$.  Thus, the area of the rectangle minus both of the triangles is 1.5-.25-.25=$1$ [/hide][/quote]
 I think you subtracted the area of the triangles twice since $\frac{(2)(.5)(.5)}{2}=\frac{.5}{2}=.25$ is the area of the two triangles combined also the question says express your answer as a common fraction.

[quote="sonny"][/quote][quote="The QuattoMaster 6000"][quote="sonny"][quote="#H34N1"]In the figure below, the shaded region is formed by drawing two parallel segments which connect the midpoints of congruent squares. Each square has side length 1 centimeter. What is the number of square centimeters in the shaded region? Express your answer as a common fraction.

[img]7216[/img][/quote]
[hide]Is the answer $\frac{5}{4}$? [/hide][/quote]
I am not sure if my method is right, but I get a different answer than you.  I get 1 as the answer.
[hide] Say the big (nonshaded) figure is called ABCDEFGHIJKL with A at the topmost part of the figure to the left, and the succeeding letters are in order clockwise after A.  Say the midpoints of AL is M, of KL is N, of EF is P, and of FG is Q.  We know that IF and IL will trisect NQ.  Using this, we can figure out that
\[NQ=3(.5\sqrt{2})=1.5\sqrt{2}=MP \]
Now, we can also figure out that
\[MN=.5\sqrt{2}=PQ \]
From here, we can connect M, N, P, and Q to form a rectangle with a length of $1.5\sqrt{2}$ and a width of $.5\sqrt{2}$, thus having an area of $(2)(.5)(1.5)=1.5$.  We can also find the area of Triangles MNL and Triangle PFQ is $\frac{(2)(.5)(.5)}{2}=\frac{.5}{2}=.25$.  Thus, the area of the rectangle minus both of the triangles is 1.5-.25-.25=$1$ [/hide][/quote][quote="sonny"]
 I think you subtracted the area of the triangles twice since $\frac{(2)(.5)(.5)}{2}=\frac{.5}{2}=.25$ is the area of the two triangles combined also the question says express your answer as a common fraction.[/quote]
Oh, yeah, you are right.  I am not focusing.

This is a really hard way to do it but...

[hide]
The total area of the figure if $5cm^{2}$ Split the shaded area into right triangles. Each of these triangles are $1/40$ of the whole figure. The total number of triangles in the shaded region is $10$. $\frac{10}{40}5 = \frac{5}{4}cm^{2}$
[/hide]


function
logarithms
real analysis
real analysis unsolved

Let $a_n, \lambda_n \geq 0$ ($n \in \mathbb{N}$) and $f(x)= \sum a_ne^{-\lambda_n x}$. Prove that $log f$ is convex on $\mathbb{R}$

I don't think that the condition $\lambda_{n}\geqslant 0$ is necessary, so let us assume $a_{n}>0$ and $\lambda_{n}\in \mathbb{R}$. And if $f~: ~x\mapsto \sum_{n=1}^{N}a_{n}e^{\lambda_{n}x}$, I'll show that $f$ is logarithmically convex.

[b]Lemma:[/b] $\varphi$ is logarithmically convex iff $x\mapsto \varphi(x)k^{x}$ is convex for all $k>0$.

[i]Proof:[/i] If $\mu \in [0,1]$, and $k>0$, $\varphi(\mu y+(1-\mu)z)k^{\mu y+(1-\mu)z}\leqslant \mu\varphi(y)k^{y}+(1-\mu)\varphi(z)k^{z}$.
So $\varphi(\mu y+(1-\mu)z)\leqslant \mu\varphi(y) t^{1-\mu}+(1-\mu)\varphi(z)t^{-\mu}$, where $t=k^{y-z}$.
And $\max_{t >0}\{\mu\varphi(y) t^{1-\mu}+(1-\mu)\varphi(z)t^{-\mu}\}= \varphi(y)^{\mu}\varphi(z)^{1-\mu}$, hence $\varphi$ is logarithmically convex
Reciprocally, it's clear that if $\varphi$ is logarithmically convex, $x\mapsto \varphi(x)k^{x}$ is convex for all $k>0$.

Now, using this lemma, the sum of logarithmically convex functions is logarithmically convex. And $x\mapsto a_{n}e^{\lambda_{n}x}$ is logarithmically convex, hence $f$ is logarithmically convex.

[b]Question:[/b] Does anyone know how to prove that the sum of logarithmically convex functions is logarithmically convex without using that lemma?

[quote="JC_math"]I don't think that the condition $\lambda_{n}\geqslant 0$ is necessary,[/quote]
What about $a_{1}=1,\lambda_{1}=-2$
and  $a_{n},\lambda_{n}=0$( n\ge 2)

zahobin,

With your asumptions and eugene's definitions you have $f(x)=e^{2x}$. So $\log f$ is convex.


Why does the National Olympiad forum look very disorganized of late? There are several posts containing only individual problems, and thus should not be there. Many posts look disorganized as well.

@Mods of this box: I think we need remove ''Stickies  '' for all old topic, and Stickies  for some( not all) topic have name kind  ''*** Mathematical Olympiad 2007''.

Yeah, and especially those "5th Bdmo 07 secondary" topics should be merged...


[quote="boo"]$ x\in [0,6)$
what is the difference between $ [$ and $ ($?
does this mean that x can be 0, but x can't be 6?[/quote]

Yes.

$ x\in[a,b]$ means $ x$ is in the closed interval, containing $ a,b$.
$ x\in (a,b)$ means $ x$ is in the open interval, not containing $ a,b$.

Basically, the $ ]$ means the endpoint is in, and $ )$ means it's out:

$ x\in (a,b]$ means $ x$ is in the half-open (half-closed?) interval, containing $ b$ and not containing $ a$.


Let be $ a\in \mathbb{R}_\plus{}^*$ such that $ \{a\}\plus{}\left\{\frac{1}{a}\right\}\equal{}1$ . Show that $ a\notin \mathbb{Q}$ and find a value of $ a$ .

[hide]Assume $ a$ is rational; let $ a \equal{} p/q$ in lowest terms. Our equation is then $ \{p/q\} \plus{} \{q/p\} \equal{} 1$. Regardless of whether $ p < q$ or $ q > p$, the equation becomes $ (p \minus{} 1)(q \minus{} 1) \equal{} 0$, hence $ p \equal{} 1$ or $ q \equal{} 1$. We can quickly verify that integers and numbers of the form $ 1/n$ are not solutions to the equation, however, hence no rational is.

A number that satisfies the equation is $ 1\plus{}\phi$.[/hide]

It's easy to see that the condition is equivalent to $ a\plus{}\frac{1}{a}$ is an integer and both $ a,\frac{1}{a}$ are not integers.

If $ a$ is rational, then we write $ a$ in the lowest form $ \frac{q}{p}$ we get $ \frac{p^2\plus{}q^2}{pq}$ is an integer , but $ p \neq 1 \Rightarrow$ the denominator does not divide the nominator, contradiction.

Let $ a\plus{}{\frac{1}{a}}\equal{}k$ for any constant integer $ k$, then we have the non-integer positive real roots of $ a^2\minus{}ka\plus{}1\equal{}0$ are all posible solutions. Simply put $ k\equal{}3$ we get $ a\equal{}\frac{3\plus{}\sqrt{5}}{2}$ and $ a\equal{}\frac{3\minus{}\sqrt{5}}{2}$ as two of the solutions.

going off of stephen's approach, the solutions are $ a \equal{} \frac{k \pm \sqrt{k^2\minus{}4}}{2}$.   We can then note that if $ k^2\minus{}4\equal{}b^2$ for some integer $ b$, then $ (k\minus{}b)(k\plus{}b) \equal{} 4$.  $ k\minus{}b$ and $ k\plus{}b$ must have the same parity, so the only factorizations of $ 4$ that work are $ 2*2$ and $ \minus{}2*\minus{}2$ ($ 1*4$ and $ \minus{}1*\minus{}4$ don't work because of parity).  so
we have $ k\minus{}b\equal{} \pm2$, $ k\plus{}b\equal{}\pm2$, and adding we get $ 2k\equal{}\pm4 \to k\equal{}\pm2$.  these $ k$'s give solutions $ a\equal{}\pm1$, but these both fail the condition that $ a$ and $ 1/a$ are not integers.  Since all other solutions have non-square determinants, all solutions are irrationals (and thus pass the requirement that both $ a$ and $ 1/a$ are not integers).


integration
limit
calculus
logarithms
real analysis
function
real analysis unsolved

does $ \int_0^\infty f<\infty,$ as long as $ \lim_{c\to\infty}\int_{\frac1c}^c f$ exists?

For $ f > 0,$ yes. But if you take that away, no. This is a version of a principal value integral, and for an exception, how about $ \int_0^{\infty}\ln x\,dx\ ?$

Edit: bad example. See below.

oh thanks, and, can you prove it formally?

As an improper integral:
Assuming $ f$ doesn't blow up anywhere else, $ \int_0^{\infty} f\equal{}\lim_{a\to 0^\plus{}}\int_a^1 f\plus{}\lim_{b\to\infty}\int_1^b f$, if both limits exist. Now, if $ f$ is nonnegative, $ \int_{a}^b f$ is between $ \int_a^{1/a} f\plus{}\int_{1/b}^b f$. As $ a\to 0^\plus{}$ and $ b\to\infty$, both parts of the right side tend to the same value, so the left side is squeezed and also converges to the same value.

As a Lebesgue integral: There's basically nothing to prove. If $ U$ is a set of infinite measure, $ V_n$ are an increasing sequence of subsets with union $ U$, and $ f$ is a nonnegative function on $ U$, $ \int_U f$ is $ \lim_n \int_{V_n} f$, practically by definition. See also the Monotone Convergence Theorem.

I gave a bad example above.

$ \int_0^{\infty}\frac{\ln x}x\,dx$ makes the point I wanted to make.

Or $ \int_0^{\infty}\frac{\ln x}{x(1\plus{}\ln^2x)}\,dx.$

[quote="jmerry"]Assuming $ f$ doesn't blow up anywhere else...[/quote]
What do you mean by this?
[quote="jmerry"]Now, if $ f$ is nonnegative, $ \int_{a}^b f$ is between $ \int_a^{1/a} f \plus{} \int_{1/b}^b f$. As $ a\to 0^ \plus{}$ and $ b\to\infty$, both parts of the right side tend to the same value, so the left side is squeezed and also converges to the same value.[/quote]
Could you please explain this also?


geometry
parallelogram
geometry proposed

Prove that a quadrilateral is a parallelogram if and only if its centroid coincides with the diagonals meetpoint.

[hide]Notice that the centroid of quadrilateral is the midpoint of a line segment which contacts two midpoints of the diagonals.[/hide]


A cube has a volume of 64 cubic meters. How many meters long is the line segment connecting the centers of two adjacent faces of the cube? Express your answer in simplest radical form.

We see that the length of each edge of the cube is 4. Since we want the distance between the center of two adjacent faces of the cube, we want the hypotneuse of 2 by 2 triangle. So the answer is $ 2\sqrt2$


ARML probability geometry trigonometry rectangle ratio inequalities

1.
When the sum of the first $k$ terms of the series

\[ 1^2 + 2^2 + 3^2 + \cdots + n^2 + \cdots \]
is subtracted from the sum of the first $k$ terms of the series

\[ 1 \cdot 2 + 2 \cdot 3 + 3 \cdot 4 + \cdots + n(n+1) + \cdots, \]
the result is 210.  Find the numerical value of $k$.

2.
Three coplanar circles are concentric, and the lengths of their respective radii are 10, 20, and 30.  A square is circumscribed about the smallest circle, and squares are inscribed in the other two circles.  Find the length of the shortest line segment that could contain a point on each square.

3.
Find the numerical value of $k$ for which

\[ \frac{7}{x+y} = \frac{k}{x+z} = \frac{11}{z-y}. \]

4.
Spender Sam always carried only dollars and pennies, but he never carried more than 99 pennies.  When leaving home one day, Sam noted that the number of dollars he had was 150% of the number of pennies he had.  After spending 10 dollars and 78 cents, Sam discovered that the number of dollars he had remaining was 1 less than the number of pennies he then had.  With how much money did Sam leave home that day?

5.
Two cards are randomly selected from a standard 52 card deck of playing cards, without replacement.  Find the probability that at least on king and at least one heart are selected (though not necessarily on different cards).

6.
Find the ordered pair of positive integers $(a, b)$, with $a<b$, for which
\[ \sqrt{1+\sqrt{21+12\sqrt{3}}} = \sqrt{a} + \sqrt{b}. \]

7.
The length of the base of an isosceles triangle is 20.  In the plane of the triangle, a point 4 units from this base is 10 units from each leg.  Find the area of the triangle.

8.
If Arc denotes the principle value, find all values of $x$ which satisfy

\[ \sin{(4\text{Arc}\tan{x})} = \frac{24}{25}. \]

1.
Darts are thrown randomly at a board showing three concentric circles of radii 2, 3, and 4.  If a dart hits inside one of the circles, what is the probability, expressed as a common fraction, that it is in the interior of the circle of radius 3 but not in the interior of the circle of radius 2?

2.
Three tennis balls are tightly sealed in a right cylindrical can, so that the balls cannot move inside the can.  If the radius of each ball is 4 cm, find the number of cubic centimeters in the volume of the space within the cylinder, not taken up by the three tennis balls.  Express your answer in terms if $\pi$.

3.
A custom made window is a single pane of glass consisting of a semicircular sheet of glass on top of the narrow end of a rectangular sheet of glass.  The rectangle has dimensions of 4 feet by 3.5 feet.  How many feet of weather-stripping will be needed to go around the glass?  Express your answer to the nearest integer.

4.
The numbers from 1 through 8 are separated into two sets, A and B.  The numbers in A are multiplied together to get $a$.  The numbers in B are multiplied together to get $b$.  The larger of the two numbers $a$ and $b$ is written down.  What is the smallest possible number that can be written down using this procedure?

5.
Eric's Florist Shop sells roses for 20 dollars per dozen, daises for 5 dollars per dozen, and chrysanthemums for 10 dollars per dozen.  At these rates how much would an arrangement of 9 roses, 6 daises, and 18 chrysanthemums cost in dollars?

6.
Given the equation $\displaystyle \frac{1}{m} + \frac{1}{n} = \frac{2}{15}$, where $m$ and $n$ are positive integers, find the value of $m+n$ such that $m>n$ and $m$ is not a multiple of $n$.

7.
Use the pattern below to express $100^2$ in the form $a^2+b^2-c^2$.  Then find $a+b+c$.
\begin{eqnarray*}
12^2 = 8^2 + 9^2 - 1^2\\
14^2 = 10^2 + 10^2 - 2^2\\
16^2 = 12^2 + 11^2 - 3^2\\
18^2 = 14^2 + 12^2 - 4^2
\end{eqnarray*}

8.
The ratio of the length of a rectangle to its width is the same as that of the diagonal to the length.  If the width is 2, how many units are in the length of the diagonal?

9.
Suppose a number $x$ satisfies $x^2-4x-1=0$.  How much greater is $x$ than its reciprocal?

10.
What is the difference between the largest and the smallest values of $x$ satisfying the following system of inequalities?
Express your answer as a mixed number.
\begin{eqnarray*}
2x-6 \le 6\\
4x+3 \ge 13
\end{eqnarray*}

Let's work on these others:
2.
Three coplanar circles are concentric, and the lengths of their respective radii are 10, 20, and 30.  A square is circumscribed about the smallest circle, and squares are inscribed in the other two circles.  Find the length of the shortest line segment that could contain a point on each square.

We have the inner square of side length 20 and the outer of $\frac{60}{\sqrt{2}}$, and any line intersecting the inner and the outer intersects the middle one. Thus the shortest line has length $\frac{30-10\sqrt{2}}{\sqrt{2}}$.

3.
Find the numerical value of $k$ for which
\[\frac{7}{x+y}= \frac{k}{x+z}= \frac{11}{z-y}. \]

4.
Spender Sam always carried only dollars and pennies, but he never carried more than 99 pennies.  When leaving home one day, Sam noted that the number of dollars he had was 150% of the number of pennies he had.  After spending 10 dollars and 78 cents, Sam discovered that the number of dollars he had remaining was 1 less than the number of pennies he then had.  With how much money did Sam leave home that day?

He must have gained 22 pennies and lost 11 dollars. Let us have $p$ pennies. Then after spending his money, he has $\frac{3p}2-11$ dollars and $p+22$ pennies. Then we add 1 dollar and we have $\frac{3p}2-10=p+22\rightarrow p=64$ so he had 96.64 originally.
5.
Two cards are randomly selected from a standard 52 card deck of playing cards, without replacement.  Find the probability that at least on king and at least one heart are selected (though not necessarily on different cards).

Ah, good old easy problem like last year's #7. JBleh. Right. There are 52*51/2 sets of two cards. We have 3*13 cards, but we haven't counted the cases where the king is the heart; there are 51 such cases. So the prob is $\frac{40}{663}$

6.
Find the ordered pair of positive integers $(a, b)$, with $a<b$, for which
\[\sqrt{1+\sqrt{21+12\sqrt{3}}}= \sqrt{a}+\sqrt{b}. \]

Yech, I don't know how to do this one. Squaring might not be great. Karthik told me how to, but I'll do this one tomorrow.

7.
The length of the base of an isosceles triangle is 20.  In the plane of the triangle, a point 4 units from this base is 10 units from each leg.  Find the area of the triangle.

Whoa, that's interesting.

8.
If Arc denotes the principle value, find all values of $x$ which satisfy
\[\sin{(4\text{Arc}\tan{x})}= \frac{24}{25}. \]

There's got to be a faster way to do this one than this, but...

OK, so we make our 7-24-25 triangle. Then we use the sin quadruple-angle-addition-formula ($\sin (4x)=4\sin x \cos x$), the sin-arctan formula (if $\arctan (x)=\frac{1}{x}$, $\sin\arctan x = \frac{x}{\sqrt{1+x^{2}}$), and $cos\arctan x=\frac{1}{\sqrt{1+x^{2}}$. Thus we have $\frac{4x}{1+x^{2}}=\frac{24}{25}$ thus one value of x that works is 1/3. Furthermore, we see that we could also have $\sin(4\arctan x+360)$ which has the same value and gives x=-3. Thus all values of x that work are -3,1/3.

[hide="3"]$\frac{7}{x+y}= \frac{11}{z-y}= \frac{7+11}{(x+y)+(z-y)}$[/hide]

[hide="6"]Hmm, these sums of radicals within radicals are called "surds" at my school.  So,
\begin{eqnarray*}\sqrt{1+\sqrt{21+12\sqrt{3}}}&=& \sqrt{1+\sqrt{21+2 \sqrt{12 \cdot 9}}\\ &=& \sqrt{ 1+3+2\sqrt{3}}\\ &=& \sqrt{1}+\sqrt{3}}\end{eqnarray*}[/hide]

[hide="7"]So clearly, if you project the point onto the legs of the triangle, it lands at new points 4 units from the respective base vertices.  But now we can see that we have some similar (congruent, in fact) right triangles which give us angles that sum to $\pi$, so we see that the other two legs of the alleged triangle are in fact parallel and the problem appears to be wrong.[/hide]

[hide="8"]Unfortunately, your quadruple-angle addition formula seems to be untrue (try $x = \frac{\pi}{4}$, for intance :wink: ).  But if you use the principle of the angle bisector theorem repeatedly, it actually works out fairly nicely.  If you draw an angle bisector in a 7-24-25 triangle, you get a scaled 3-4-5 triangle (with that orientation relative to the original), and it is fairly easy to see that if you bisect this angle again, you get $\frac{1}{2}$ as your tangent.

Or you could use $\tan (A/2) = \frac{a}{b+c}$ to get that the tangent of half of $\mbox{Arc}\sin \frac{24}{25}$ (which conveniently 4/3), and then the tangent of half of that angle is 1/2.

The only trouble is that we've computed $\tan \left( \frac{\mbox{Arc}\sin 24/25 }{4}\right)$, but what we really want is $\tan \left( \frac{ \pi /2 \pm ( \mbox{Arc}\sin{24/25}-\pi /2+2\pi n)}{4}\right)$.  However, this is obviously where elegance receives a severe blow to the head, and I have some other stuff to do soon, so if someone else would like to pick it up from here, that would be fine.[/hide]


calculus
Asymptote
function
conics
hyperbola
calculus computations

I was taking a quiz and I arrived at the question

[quote="quiz"]Given the relation $ x^2\minus{}y^2\equal{}1$, find all the asymptotes.[/quote]

My calculus course only covered asymptotes of functions. How would I do it with relations? TYiA.

Express one variable as a function of anohter and, thus, reduce the problem to what you know. (Not that it is the easiest way in this particular case, but it works :)).

[quote="1=2"]I was taking a quiz and I arrived at the question

[quote="quiz"]Given the relation $ x^2 \minus{} y^2 \equal{} 1$, find all the asymptotes.[/quote]

My calculus course only covered asymptotes of functions. How would I do it with relations? TYiA.[/quote]

Maybe I'm misunderstanding the term asymptote, but I don't think there's any in $ x^2 \minus{} y^2 \equal{} 1$ or $ y \equal{} \pm \sqrt{x^2 \minus{} 1}$.

The equation represents a hyperbola - there should be two asymptotes.


The value of the determinant $ \left|
\begin{array}{cc}
a & b \\
c & d \end{array}
\right| \equal{} ad\minus{}bc$. What is the value of $ x$ when
$ \left|
\begin{array}{cc}
3 & x \\
\minus{}4 & \minus{}7 \end{array}\right| \equal{} \minus{}13$?

Okay, so we have $ 3(\minus{}7) \minus{} (\minus{}4)x \equal{} \minus{}13 \implies \minus{}21 \minus{} (\minus{}4)x \equal{} \minus{}13 \implies x \equal{} \boxed{2}$.


They do, but are we allowed to use them on the USAMO/IMO? Just a question.

If you searched around the site, there have been many posts made on this topic. Brute-forcing an inequality with calculus using Lagrange Multipliers is technically allowed (it is math), but it is highly discouraged, and is supposed to make graders "mean." (meaner than they would normally be)

(Written in the same time as mihail's answer)

As far as IMO is concerned, the answer is yes. But you ought to be very careful, as the graders won't tolerate any "petty errors" in the process, so it is often an "all-or-nothing" situation when it comes to grading.

BTW, the fact is true if you can solve ugly systems which come up very often using Lagrange. Some inequalities  (even those appearing in the IMO) do have elegant LM solutions, but generally speaking, thigs can get really ugly.

"Discouraged" is pretty much the right word.  Lagrange multipliers can be used to prove a number of inequalities without revealing anything about the underlying structure of the problem, which sort of defeats the purpose of solving it.  Case in point:  IMO 2008 #2 can be solved by Lagrange multipliers, or you can factor it as $ f(x, y, z)^2 \ge 0$.  Which solution gets to the heart of the problem?

Lagrange multipliers and other calculus mistakes are very often used badly, and that gets you no sympathy.

For the IMO problem this year, it comes down to finding the equality cases no matter what. Since you're expecting double roots, calculus can be effective here- but it's easy enough with brute force algebra.


algebra
polynomial
symmetry
quadratics
geometry
3D geometry
Rational Root Theorem

I know that in an equation the rational root theorem will find the rational roots, but how does one find the complex and irrational roots in an equation, especially if the equation has only irrational and complex roots?

Ex:  x^4+(2-x)^4=34

For equations of degree three and four, there is a standard procedure- look up Cardano. It's time consuming and complicated; better remembered as a procedure than as a formula.

Your example, however, is much simpler; we can exploit its symmetry to solve it by chaining two quadratics.

Let $x=y+1$. The equation becomes $(1+y)^4+(1-y)^4=34$, which simplfies to $y^4+6y^2+1=17.$
I think you can solve this on your own.

I just wanted to know if there was some general way of doing the problem, without use of manipulation, because sometimes manipulation may not work.

All right, you asked for it. Here's how you solve a cubic or quartic polynomial equation:

General cubic $x^3+ax^2+bx+c=0$
Step 1: Let $y=x+\frac a3.$
This gives $y^3+py+q=0.$
Step 2: Let $x=u+v$, $uv=-p/3.$
We have $(u+v)^3+p(u+v)+q=u^3+v^3+3uv(u+v)+p(u+v)+q=u^3+v^3+q=0.$
Now, from $u^3+v^3=-q$ and $u^3v^3=\frac{-p^3}{27}$ we can derive a quadratic equation for $u^3$ and $v^3$. Solve it, take cube roots to find $u$ and $v$, then add them to get the roots of the cubic.

General quartic $x^4+ax^3+bx^2+cx+d=0$
Step 1: Let $y=x+\frac a4.$
This gives $y^4+py^2+qy+r=0.$
Step 2: Let the roots of this quartic be $u+v+w,u-v-w,-u+v-w,-u-v+w.$
We have $p=-2(u^2+v^2+w^2), q=8uvw,$ $r=(u^4+v^4+w^4)-2(u^2v^2+u^2w^2+v^2w^2).$
Then $-(u^2+v^2+w^2)=\frac p2,$ $u^2v^2+u^2w^2+v^2w^2=\frac14\left(\left(\frac p2\right)^2-r\right),$ and $-u^2v^2w^2=-\left(\frac q8\right)^2.$
This means $(z-u^2)(z-v^2)(z-w^2)=z^3+\frac p2z^2+\frac14\left(\left(\frac p2\right)^2-r\right)z-\left(\frac q8\right)^2.$
Step 3: Solve this cubic for $u^2,v^2,w^2.$
Step 4: Take square roots, choosing sign to match the known value of $uvw.$ Find the roots of the original quartic from $u,v,w.$

Higher degrees? Hope you get lucky.

the conclusion to this, my friends, is that root finding is painfully inefficient when done algebraicly and should only be approached by someone armed with a computer algebra system or a really good guesser.    :D

... or you can try the 1000 monkeys for 1000 years method which I claim is more likely to help with root finding than writing shakespeare.   :lol:

[quote="luther_driggers"]the conclusion to this, my friends, is that root finding is painfully inefficient when done algebraically[/quote]
And finding roots of polynomials approximately by numerical methods is easy and efficient. Newton's method is perfectly suited to polynomials.

I understand and thank you for your help


function
inequalities proposed
inequalities

I solved yesterday this problem but I want to see another solutions.
$a,b,c\geq 0$ and $a^2+b^2+c^2=1$
Prove that $\frac{a}{b^2+1}+\frac{b}{c^2+1}+\frac{c}{a^2+1}\geq\frac{3}{4}(\sum a\sqrt {a})^2$ :)

By Cauchy we have

$\frac{a}{b^2+1}+\frac{b}{c^2+1}+\frac{c}{a^2+1}
=\frac{a^3}{a^2b^2+a^2}+\frac{b^3}{b^2c^2+b^2}+\frac{c^3}{c^2a^2+c^2}
\geq \frac{(\sum a\sqrt {a})^2}{\sum a^2b^2+ \sum a^2}$

By using the condition $a^2+b^2+c^2=1$, we see that it is sufficient to show

$4(\sum a^2)^2\geq3(\sum a^4+ 3\sum a^2b^2)$

But this reduces to

$\sum a^4\geq\sum a^2b^2$

Very good solution. i am wonder if this can be solved with function?


Good morning,
Does someone have a nice solution, without considering , all different cases ( i mean , a all-in-1 solution for this problem)
$ \boxed{[0\le a \le b -and- 0\le c \le d] \implies |a-c|+|b-d|\le |a-d|+|b-c|}$

The solution is not "nice", and I do not know if you will consider this as "considering cases", but here it goes:

Square both sides to get the equivalent inequality (equivalent since all terms involved in the original inequality are positive):
\[ a^2 \plus{} c^2 \minus{} 2ac \plus{} b^2 \plus{} d^2 \minus{} 2bd \plus{} 2|a \minus{} c\parallel{}b \minus{} d|\leq a^2 \plus{} d^2 \minus{} 2ad \plus{} b^2 \plus{} c^2 \minus{} 2bc \plus{} 2|a \minus{} d\parallel{}b \minus{} c|,
\]
which after simplification reduces to
\[ (b \minus{} a)(d \minus{} c)\geq|a \minus{} c\parallel{}b \minus{} d| \minus{} |d \minus{} a\parallel{}b \minus{} c|.
\]
Multiply now both sides by $ |a \minus{} c\parallel{}b \minus{} d| \plus{} |d \minus{} a\parallel{}b \minus{} c|$.  The LHS is obviously positive, while the RHS, after some calculations, is
\[ (b \minus{} a)(d \minus{} c)\left(2ab \plus{} 2cd \minus{} (b \plus{} a)(d \plus{} c)\right).
\]
The first two factors are non-negative.  The third factor is equal to $ (a \minus{} c)(b \minus{} d) \plus{} (a \minus{} d)(b \minus{} c)$, which is obviously less than or equal to $ |a \minus{} c\parallel{}b \minus{} d| \plus{} |d \minus{} a\parallel{}b \minus{} c|$, and we are done.  Equality is reached when
$ c \minus{} a$ and $ d \minus{} b$ have the same sign, while simultaneously $ d \minus{} a$ and $ c \minus{} b$ have the same sign, or equivalently, when $ a,b$ are both either not smaller than, or not larger than, $ c,d$.  Equality is also reached (trivial cases) when either $ b\equal{}a$ or $ d\equal{}c$.


$ a_i ,b_i$ are nonnegative real numbers, prove that :

(1)
$ (a_1(b_2\plus{}b_3)\plus{}a_2(b_1\plus{}b_3)\plus{}a_3(b_1\plus{}b_2))^2\ge(a_1\plus{}a_2\plus{}a_3)(a_1b_2b_3\plus{}a_2b_1b_3\plus{}a_3b_1b_2)$

(2)
$ (a_1(b_2\plus{}b_3\plus{}b_4)\plus{}a_2(b_1\plus{}b_3\plus{}b_4)\plus{}a_3(b_1\plus{}b_2\plus{}b_4)\plus{}a_4(b_1\plus{}b_2\plus{}b_3))^3$
$ \ge(a_1\plus{}a_2\plus{}a_3)^2(a_1b_2b_3b_4\plus{}a_2b_1b_3b_4\plus{}a_3b_1b_2b_4\plus{}a_4b_1b_2b_3)$

These are special case of the post which I posted, but no one answered.
http://www.mathlinks.ro/viewtopic.php?t=258091

[quote="NextPeace"]I'm sorry, my problem needs modification.  :blush:
(1)
$ (a_1(b_2 \plus{} b_3) \plus{} a_2(b_1 \plus{} b_3) \plus{} a_3(b_1 \plus{} b_2))^2\ge4(a_1 \plus{} a_2 \plus{} a_3)(a_1b_2b_3 \plus{} a_2b_1b_3 \plus{} a_3b_1b_2)$

(2)
$ (a_1(b_2 \plus{} b_3 \plus{} b_4) \plus{} a_2(b_1 \plus{} b_3 \plus{} b_4) \plus{} a_3(b_1 \plus{} b_2 \plus{} b_4) \plus{} a_4(b_1 \plus{} b_2 \plus{} b_3))^3$
$ \ge27(a_1 \plus{} a_2 \plus{} a_3 \plus{} a_4)^2(a_1b_2b_3b_4 \plus{} a_2b_1b_3b_4 \plus{} a_3b_1b_2b_4 \plus{} a_4b_1b_2b_3)$[/quote]
I will post my solution for (1), the solution for (2), I will post the next time, right now I dont have too much time. :( The solution of (1) is:
If there are two of $ b_1,b_2,b_3$ equal to $ 0$, the inequality is trivial. Assume that $ b_3>0$ is the number between $ b_1$ and $ b_2$, then using AM-GM, we have
\[ 4(a_1 \plus{} a_2 \plus{} a_3)(a_1b_2b_3 \plus{} a_2b_1b_3 \plus{} a_3b_1b_2) \le \left[ (a_1 \plus{} a_2 \plus{} a_3)b_3 \plus{} \frac { a_1b_2b_3 \plus{} a_2b_1b_3 \plus{} a_3b_1b_2}{b_3}\right]^2
\]
And we can reduce our inequality to
\[ a_1(b_2 \plus{} b_3) \plus{} a_2(b_1 \plus{} b_3) \plus{} a_3(b_1 \plus{} b_2) \ge (a_1 \plus{} a_2 \plus{} a_3)b_3 \plus{} \frac { a_1b_2b_3 \plus{} a_2b_1b_3 \plus{} a_3b_1b_2}{b_3}
\]
which is just equivalent to
\[ \frac {a_3(b_1 \minus{} b_3)(b_3 \minus{} b_2)}{b_3} \ge 0
\]
which is trivial. :)

[quote="NextPeace"]I'm sorry, my problem needs modification.  :blush:
(1)
$ (a_1(b_2 \plus{} b_3) \plus{} a_2(b_1 \plus{} b_3) \plus{} a_3(b_1 \plus{} b_2))^2\ge4(a_1 \plus{} a_2 \plus{} a_3)(a_1b_2b_3 \plus{} a_2b_1b_3 \plus{} a_3b_1b_2)$

(2)
$ (a_1(b_2 \plus{} b_3 \plus{} b_4) \plus{} a_2(b_1 \plus{} b_3 \plus{} b_4) \plus{} a_3(b_1 \plus{} b_2 \plus{} b_4) \plus{} a_4(b_1 \plus{} b_2 \plus{} b_3))^3$
$ \ge27(a_1 \plus{} a_2 \plus{} a_3 \plus{} a_4)^2(a_1b_2b_3b_4 \plus{} a_2b_1b_3b_4 \plus{} a_3b_1b_2b_4 \plus{} a_4b_1b_2b_3)$[/quote]
Now, I will post my solution for (2). WLOG, we can assume that $ b_1 \equal{} \max\{b_1,b_2,b_3,b_4\}$ and $ b_4 \equal{} \min\{b_1,b_2,b_3,b_4\}$ (why?!), then using AM-GM Inequality, we have
$ LHS \le \left[ b_2(a_1 \plus{} a_2 \plus{} a_3 \plus{} a_4) \plus{} b_3(a_1 \plus{} a_2 \plus{} a_3 \plus{} a_4) \plus{} \frac { a_1b_2b_3b_4 \plus{} a_2b_1b_3b_4 \plus{} a_3b_1b_2b_4 \plus{} a_4b_1b_2b_3}{b_2b_3}\right]^3,$
it suffices to show that
$ a_1(b_2 \plus{} b_3 \plus{} b_4) \plus{} a_2(b_1 \plus{} b_3 \plus{} b_4) \plus{} a_3(b_1 \plus{} b_2 \plus{} b_4) \plus{} a_4(b_1 \plus{} b_2 \plus{} b_3) \ge b_2(a_1 \plus{} a_2 \plus{} a_3 \plus{} a_4) \plus{} b_3(a_1 \plus{} a_2 \plus{} a_3 \plus{} a_4) \plus{} \frac { a_1b_2b_3b_4 \plus{} a_2b_1b_3b_4 \plus{} a_3b_1b_2b_4 \plus{} a_4b_1b_2b_3}{b_2b_3},$
which is equivalent to
$ \frac {a_2 b_3 (b_1 \minus{} b_2)(b_2 \minus{} b_4) \plus{} a_3b_2 (b_1 \minus{} b_3)(b_3 \minus{} b_4)}{b_2b_3} \ge 0,$
which is trivial. This completes our proof. :)

Note: This way can also help us solve the general one. ;)

[quote="can_hang2007"]
$ a_1(b_2 \plus{} b_3 \plus{} b_4) \plus{} a_2(b_1 \plus{} b_3 \plus{} b_4) \plus{} a_3(b_1 \plus{} b_2 \plus{} b_4) \plus{} a_4(b_1 \plus{} b_2 \plus{} b_3)\ge b_2(a \plus{} b \plus{} c \plus{} d) \plus{} b_3(a \plus{} b \plus{} c \plus{} d) \plus{} \frac { a_1b_2b_3b_4 \plus{} a_2b_1b_3b_4 \plus{} a_3b_1b_2b_4 \plus{} a_4b_1b_2b_3}{b_2b_3},$
[/quote]
Maybe it means
$ a_1(b_2 \plus{} b_3 \plus{} b_4) \plus{} a_2(b_1 \plus{} b_3 \plus{} b_4) \plus{} a_3(b_1 \plus{} b_2 \plus{} b_4) \plus{} a_4(b_1 \plus{} b_2 \plus{} b_3) \ge b_2(a_1 \plus{} a_2 \plus{} a_3 \plus{} a_4) \plus{} b_3(a_1 \plus{} a_2 \plus{} a_3 \plus{} a_4)\plus{}\frac { a_1b_2b_3b_4 \plus{} a_2b_1b_3b_4 \plus{} a_3b_1b_2b_4 \plus{} a_4b_1b_2b_3}{b_2b_3},$

But it is very nice proof! Thanks, can_hang. I really like your proof :)

Here is my solution for the general one:
[quote="NextPeace"]Prove that if $ a_1,a_2_\ldots,a_n$ and $ b_1,b_2,\ldots,b_n$ $ (n \ge 2)$ are nonnegative real numbers, then
$ \left( \sum^n_{i = 1} a_i\sum_{j \ne i} b_j\right)^{n - 1} \ge (n - 1)^{n - 1} \left( \sum^n_{i = 1} a_i\right)^{n - 2} \left( \sum^n_{i = 1} a_i\prod_{j \ne i} b_j\right).$
[/quote]
If $ n = 2$, the inequality becomes equality. If $ n \ge 3$, we can assume that $ b_1 = \max\{b_1,b_2,\ldots ,b_n\}$ and $ b_n = \min\{b_1,b_2,\ldots ,b_n\}$, then according to AM-GM Inequality, we have
$ (n - 1) \sqrt [n - 1]{\left( \sum^n_{i = 1} a_i\right)^{n - 2} \left( \sum^n_{i = 1} a_i\prod_{j \ne i} b_j\right)} \le \left( \sum_{1 < i < n} b_i\right) \left( \sum^n_{i = 1} a_i\right) + \frac {\sum^n_{i = 1} a_i\prod_{j \ne i} b_j}{\prod_{1 < i < n} b_i}.$
And we reduce our inequality to
$ \sum^n_{i = 1} a_i\sum_{j \ne i} b_j \ge \left( \sum_{1 < i < n} b_i\right) \left( \sum^n_{i = 1} a_i\right) + \frac {\sum^n_{i = 1} a_i\prod_{j \ne i} b_j}{\prod_{1 < i < n} b_i},$
which is equivalent to
$ \sum_{1 < i < n}a_i \left( b_1 + b_n - b_i - \frac {b{}_1b{}_n}{b_i}\right) \ge 0,$
or
$ \sum_{1 < i < n} \frac {a_i(b_1 - b_i)(b_i - b_n)}{b_n} \ge 0,$
which is trivial and our proof is completed. :)


induction
modular arithmetic
number theory unsolved
number theory

Let we define a sequence of positive integers such that

$ a_0 \equal{} p$ , $ p$ is a prime number. and $ a_{n \plus{} 1} \equal{} 2a_n \plus{} 1$ (for $ n \equal{} 0,1,2...$)

Prove that there is no prime number $ p$ such that all the sequence will be prime numbers.

[quote="fallinlovewithmaths"]Let we define a sequence of positive integers such that

a0=p , p is a prime number. and a(n+1)= 2an + 1 (for n=0,1,2...)

Prove that there is no prime number p such that all the sequnce will be prime numbers.[/quote]

This problem is from Paul Zeitz's Art and Craft of Problem Solving. Here's my solution:

If $ a_0 \equal{} 2$, we get $ a_1 \equal{} 5, a_2 \equal{} 11, a_3 \equal{} 23, a_4 \equal{} 47, a_5 \equal{} 95$ which is not prime. Thus $ p > 2$.

It's easy to prove by induction that $ a_n \equal{} 2^n(a_0 \plus{} 1) \minus{} 1$. Thus $ a_{p \minus{} 1} \equal{} 2^{p \minus{} 1}(a_0 \plus{} 1) \minus{} 1\equiv a_0 \plus{} 1 \minus{} 1\pmod p\equiv a_0\pmod p$ for all odd primes $ p$ by FLT. Let $ a_0 \equal{} q$ be prime. Since $ q$ is odd, we have by the same reasoning that $ a_{q \minus{} 1}\equiv 0\pmod q$. On the other hand, it's clear that $ a_{q \minus{} 1} > a_0 \equal{} q$. This implies that there exists no such sequence consisting entirely of primes.


Given that 6Re(z) + 4Im(z) = 5 .... why is it that this can be rewriten as

(3 - 2i)*z + (3 + 2i)*_z  = 5

Were i^2 = -1, z is a complex number and _z =  the congugate of z.

This is only true if z =6 and _z = 4i...but thats wrong right???

Verify the identities

$ \Re(z) \equal{} \frac{z \plus{} \bar{z}}{2}$
$ \Im(z) \equal{} \frac{z \minus{} \bar{z}}{2i}$.

I am not sure how you came to your second conclusion.


function
trigonometry
real analysis
real analysis unsolved

if $f: R^{n}\to R^{m}$ is a function iwth a connected graph $G_{f}=$$\{ (x,f(x))|x\in R \}$,

$f$ is continuous.

False. Let $f(x)=\begin{cases}\sin\left(\frac1x\right)&x>0\\0&x\le0 \end{cases}.$

The graph of $f$ is connected, depsite the fact that $f$ is discontinuous at $x=0.$


Given that $ax^2+bx+c=0$ has two different roots, show that $ax^2+bx+c+x+\frac{b}{2a}=0$ has at least one root between the two roots of the previous function.

[quote="Unco"]We are given:

1. $b^2 - 4ac > 0$

2. And, of course, at the two roots of $f(x) = ax^2 + bx + c$, $ax^2 + bx + c = 0$.

3. Those roots are at  $x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$

We need to show that $g(x) = ax^2 + bx + c + x + \frac{b}{2a}$ is of opposite sign at each of those x-ordinates (3.), that is to use the Intermediate Value Theorem.

Are you ok to proceed?[/quote]
the proof is alright, but from $x_{1/2} = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$ it is a little simpler ;)
\[ x_{1/2} = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}\implies x_1 > -\frac b{2a} \wedge x_2 < - \frac b{2a} \]
therefore \[ g(x_1) = f(x_1) +x_1 + \frac b{2a} =x_1 + \frac b{2a} > -\frac b{2a}+\frac b{2a}= 0 \] \[ g(x_2) = f(x_2) +x_2 + \frac b{2a} =x_2 + \frac b{2a} < -\frac b{2a}+\frac b{2a}= 0 \]

(@shobber: it might be important to notice that the roots of $f$ must be real, otherwise you cant find an order in the root, as u probably know is $\mathbb C$ without order ;) )

[quote="peeta"]@shobber: it might be important to notice that the roots of $f$ must be real, otherwise you cant find an order in the root, as u probably know is $\mathbb C$ without order[/quote]
Thanks. I'll remember to mention it next time.

[quote="stergiu"]You can also find the discriminant of the new quadratic equation. It is more simple to see that this is positive.

 [u]babis[/u][/quote]
i guess its not quite enough to find the discriminant ... one als has to prove that its in the interval $(x_1,x_2)$


modular arithmetic
linear algebra
matrix
search
number theory

Is there a trick to this problem?  :?

(to write mod, use /pmod{x} to write $\pmod{x}$)

If you don't see why...

[hide]You know $5\equiv0\pmod{5}$.  When you multiply by 5, you have $0\cdot0\equiv0\pmod{5}$.  Each time you multiply by 5, you get the same result, so $5^5\equiv0\pmod{5}$.[/hide]

[quote="citistarz"]Find $5^5$mod(5)[/quote]

[hide]$\boxed {0}$[/hide]

Obviously its a multiple of 5.

[hide]$\boxed{0}$[/hide]

i dont know what mods are... could someone help me out? :help:

[hide]5^5 in base 5 is

100000

So it's 0[/hide]

[quote="easyas3.14159..."]Something for people to think about:
Would $6^5 (mod 5)$ be 0? Why or why not?[/quote]

[hide]
$6^5\equiv(6-5)^5\equiv1\pmod{5}$
[/hide]

[quote="Silverfalcon"]Moderator, can you move this to Getting Started.

Modular arithmetic is a difficult concept for middle schoolers. Basically, mod is when you take base of certain number. Our number system uses base 10 because there are numbers 0-9 and after 9, it goes upto 10. Binary system, however, uses two numbers 0 and 1 in their system. You probably recognize this from move Matrix 01010101010 or computers.

Anyway, in this problem, taking $5^5$ in mod 5 is same as finding $5^5$ in base 5. To do this, we divide $5^5$ by largest power of $5$ which is $5^5$. The remainder is 0 so $5^5$ in mod 5 is 0.

Search the forum for details. There are many good threads for it.[/quote]

Basically, when you want to write a number n is congruent to mod x, you just find the remainder r when x is divided by n and put n is congruent to r(mod x).

[quote="vicseb"][hide]the answer is 0[/hide][/quote]

right lol


geometry
3D geometry
arithmetic sequence

The terms $ x, x \plus{} 2, x \plus{} 4, ..., x \plus{} 2n$ form an arithmetic
sequence, with $ x$ an integer. If each term of the sequence is
cubed, the sum of the cubes is -1197. What is the value of $ n$ if
$ n > 3$?

[hide="the beginning"]ok what you basically want to do is find a sequence of perfect cubes whose roots differ by 2 each.

-1197=-729+-343+-125

but that would mean we only have 3 terms in the sequence, so n=2, but according to the rules, n>3. So what else?

Stop here and try to figure it out. When you finish, read on

[hide="The end"]Ah but we see that we can also do this:

-729+-343+-125+-27+-1+1+27=-1197

so, in this case, we have 7 terms, one of which is x, thus we have n=[hide="5+1=?"]6[/hide] at most[/hide][/hide]


Hmmm... Welcome on ML litter, but :

- You posted in a wrong section (please read the headlines. The solved section is for the solved problems on ML, not those that you solved before).
- Your post in unreadable (please use latex, there are sections to learn about it)
- Give an appropriate title to your thread (we all know that you are asking something).

Pierre.

Maybe I translate the problem into English:
Let $a_1,a_2,...,a_n$ and $b_1,b_2,...,b_n$ be two permutations of (1,1/2,1/3,....,1/n), satisfying $a_i+b_i\ge a_j+b_j$ for any integers $1\le i\le j\le n$. Prove that $a_i+b_i\le\frac{4}{i}$ for i=1,2,...n.

Thanks, now I move it to the unsolved problems section.

Pierre.

Let's assume that $a_i+b_i>\dsp \frac 4i$ and do the case $i=2k+1$ ($i=2k$ is even easier). The numbers $a_1+b_1,...,a_{2k+1}+b_{2k+1}$ will all be greater than $\dsp \frac 4{2k+1}$. But note than out of $a_j$ and $b_j$ (for any $1\leq j\leq 2k+1$), one of them must have the denominator at most $k$ (otherwise $a_j+b_j\leq \dsp \frac 4{2k+1}$) Of course, this cannot happen, because at most $2k$ of the numbers $a_j$ and $b_j$ can have denominator at most $k$ (since the available denominators which are at most $k$ are $1,2,...,k$, each of them twice)


AMC USA(J)MO USAMO AIME geometry trigonometry algebra

I find that I can usually solve #6-10 on the AIME more often than not.  #1-5 seem pretty easy, but still hard to come up with really elegant solutions; however, #11-15 seem to require skills that I haven't developed yet.

What is the hard part of the USAMO as compared to the AIME?  I've heard that #1, #4 are comparable in difficult to the very last AIME problems, and that #2, #5 are substantially harder.  I'm asking on only the basis of coming up with the solutions, assume that I can write the actual proof well.  One more thing, can you do well on the first two problems of the each day without knowing obscure theorems beyond what the AIME has?  For example, do geometry questions get tougher to solve because you need more insight or because the material that you have to know is also harder (like transformations, projections...that stuff)

you didn't need any inversion for #6...you could have just used law of cosines

Look up some past USAMOs at http://www.artofproblemsolving.com/Forum/resources.php?c=182&cid=27 I don't think anything but some experience will give you the right answers.

[quote="13375P34K43V312"][quote="mathmonster"]One more thing, can you do well on the first two problems of the each day without knowing obscure theorems beyond what the AIME has?  For example, do geometry questions get tougher to solve because you need more insight or because the material that you have to know is also harder (like transformations, projections...that stuff)[/quote]

Sure. Let's look at this year's USAMO.

#1 required nothing, essentially, other than the realization of [i]when[/i] k became sufficiently large such that the sequence became constant.

#2 required a pretty intuitive idea, and some creative realizations, then the ever-present law of cosines and some creative manipulations.

#3 i didn't look at the solution that closely but it seemed that it only required some creative thinking, no obscure theorems or methods.

#4, after "playing," was somewhat intuitive what the answer was, and took a few creative steps to prove it rigorously.

#5, you just had to get that factorization...considering that polynomial was really all you needed. nothing exceptionally fancy.

#6, the official solution involved inversion, which required prior knowledge of the method, but as far as i know it was possible to do it with trig, most likely not too hardcore.

As you see, basically with creative thinking, you can do very well on the USAMO, and as far as I know, that creative thinking comes with experience (well I have little of that, so it's hard for me to say  :D )[/quote]

This seems awfully condescending... the only person that I heard who solved #5 from MOP was Sergei Bernstein (NOTE: NO IMO TEAM MEMBERS). It was kind of a bad problem... hinging on whether you could be tricky enough to find a factorization. And [i]all[/i] problems only require "a little bit of creativity" - at least half of the USAMO qualifiers can probably understand how the solutions work... but how would you think of those solutions in such a short period of time?

[quote="not_trig"][quote="13375P34K43V312"][quote="mathmonster"].../quote]

...[/quote]

This seems awfully condescending... the only person that I heard who solved #5 from MOP was Sergei Bernstein (NOTE: NO IMO TEAM MEMBERS). It was kind of a bad problem... hinging on whether you could be tricky enough to find a factorization. And [i]all[/i] problems only require "a little bit of creativity" - at least half of the USAMO qualifiers can probably understand how the solutions work... but how would you think of those solutions in such a short period of time?[/quote][/quote]

I see and agree with what you're saying. It can definitely be hard to think up solutions in such short a time no matter how smart you are (that's why Phd's are cooler than olympiad medalists  :P ). It seems like the way to be able to think up solutions in an olympiad setting is to simply take a whole bunch of practice tests.

Yes and no. Don't just do practice olympiads. Sure, take 9 hours out of your day to do an olympiad every now and then, but make sure that you learn from the problems. If you can't get a problem, try again. Once you've tried for a while, ask for a small hint, and if you still can't get it, then look at the solution. However, don't just look at a solution right away. You'll learn much more from solving it yourself than looking at another's solutions.

[quote="mathmonster"]In other words, it's like an extremely difficult IQ test.
=)[/quote]

I don't see the connection.

[quote="mathmonster"]In other words, it's like an extremely difficult IQ test.
=)[/quote]
huh?

[quote="Treething"][quote="mathmonster"]In other words, it's like an extremely difficult IQ test.
=)[/quote]

An IQ test that will spit out nonzero results for maybe a couple thousand people in the USA, at most.

I like it.[/quote]
well theresprobalby like 10,000+ but yea..

[quote="not_trig"][quote="13375P34K43V312"][quote="mathmonster"]Stuff[/quote]More stuff[/quote]

This seems awfully condescending... the only person that I heard who solved #5 from MOP was Sergei Bernstein (NOTE: NO IMO TEAM MEMBERS). It was kind of a bad problem... hinging on whether you could be tricky enough to find a factorization. And [i]all[/i] problems only require "a little bit of creativity" - at least half of the USAMO qualifiers can probably understand how the solutions work... but how would you think of those solutions in such a short period of time?[/quote]

His point was that the USAMO doesn't require significant knowledge, not that it's easy.

Also, who are you?

Argh, these nested quotes are pretty tricky.

[quote="SuperThread"][/quote][quote="not_trig"][quote="13375P34K43V312"][quote="mathmonster"]Stuff[/quote]More stuff[/quote]

This seems awfully condescending... the only person that I heard who solved #5 from MOP was Sergei Bernstein (NOTE: NO IMO TEAM MEMBERS). It was kind of a bad problem... hinging on whether you could be tricky enough to find a factorization. And [i]all[/i] problems only require "a little bit of creativity" - at least half of the USAMO qualifiers can probably understand how the solutions work... but how would you think of those solutions in such a short period of time?[/quote][quote="SuperThread"]

His point was that the USAMO doesn't require significant knowledge, not that it's easy.

Also, who are you?[/quote]
uh well judging by his signature and location he must be from NC and a red MOP (which he did get into) and theres only one person..look at amc website.


inequalities
algebra
polynomial
invariant
geometry
geometric transformation
rotation

Let $ x_1,x_2,x_3$ are three complex roots of equation  $ ax^3 + bx^2 + cx - a = 0$ , $ a \neq 0 , (a,b,c) \in \mathbb{C}^3$
Prove that :
${{{ 2(|x_1|^2 + |x_2|^2 + |x_3|^2) \geq x_1(\sqrt {3} \overline{x_3} - \sqrt {2 + \sqrt {3}}\overline{x_2}}) + x_2(\sqrt {2} \overline{x_3} - \sqrt {2 + \sqrt {3}} \overline{x_1}}) + x_3(\sqrt{2} \overline{x_2} + \sqrt {3} \overline{x_1}})$
 With $ "="$ Find all $ x_1,x_2,x_3$

This isn't analysis. It's geometry/algebra.

First, that polynomial condition is utterly irrelevant. It says that the product of the $ x_i$ is 1, while the equation is clearly invariant under both real scaling and rotation, allowing the product to be anything.

Second, we recognize $ \frac{\sqrt{3}}{2}\equal{}\cos(30^\circ)\equal{}\minus{}\cos(210^\circ)$, $ \frac{\sqrt{2}}{2}\equal{}\cos(45^\circ)\equal{}\minus{}\cos(135^\circ)$, and $ \frac{\sqrt{2\plus{}\sqrt{3}}}{2}\equal{}\cos(15^\circ)$

Let $ \alpha\equal{}1,\beta\equal{}\cos(15^\circ)\plus{}i\sin(15^\circ)$, and $ \gamma\equal{}\cos(150^\circ)\plus{}i\sin(150^\circ)$
Then $ |\alpha x_1\plus{}\beta x_2\plus{}\gamma x_3|^2\plus{}|\overline{\alpha}x_1\plus{}\overline{\beta}x_2\plus{}\overline{\gamma}x_3|^2\equal{}\text{LHS }\minus{}\text{ RHS}$, proving the inequality. Equality of course holds if and only if both of those quantities inside the squares are zero, which happens when the $ x_i$ are parallel and in the appropriate proportions to form a 15/30/135 triangle after rotation by $ \alpha,\beta,\gamma$. (They're in the proportion $ \sin(135^\circ) : \minus{}\sin(30^\circ) : \sin(15^\circ)$). Linear algebra over $ \mathbb{C}$ establishes that these are all.

This was far too artificial. There is one nice general result here: if $ A\plus{}B\plus{}C\equiv 0\mod 2\pi$, $ \|u\|^2\plus{}\|v\|^2\plus{}\|w\|^2\plus{}2 u\cdot v\cos A\plus{}2 v\cdot w\cos B\plus{}2 w\cdot u\cos C\ge 0$ for any vectors $ u,v,w$ in Euclidean space.


inequalities
geometry
trapezoid
parallelogram
geometric transformation
homothety
geometry solved

A circle center $O$ is inscribed in the quadrilateral $ABCD$. $AB$ is parallel to and longer than $CD$ and has midpoint $M$. The line $OM$ meets $CD$ at $F$. $CD$ touches the circle at $E$. Show that $DE = CF$ iff $AB = 2CD$.

i think this question is so nice but i think it is easy either.anyway i will send my solution as soon as i can.(you know i like problems like this one.)

Jensen, either post your solution (or some hint, anyway something relevant to the problem) or don't say anything. Posts like the one you did are spam.

Here is my boring solution (I am really sure half of it is redundant). If the notations seem a bit strange to you: yes, I've interchanged E and F.

[color=blue][b]Problem.[/b] Let ABCD be a trapezoid with AB || CD and AB > CD. Assume that this trapezoid ABCD has an incircle k; let this incircle k have center O and touch the side CD at a point F. Also, let M be the midpoint of the segment AB, and let the line OM meet the segment CD at a point E. Prove that DF = CE holds if and only if $AB=2\cdot CD$.[/color]

[i]Solution.[/i] Let the legs BC and AD of the trapezoid ABCD intersect at a point K (they must intersect at some finite point, since AB > CD). Since AB > CD, the points C and D lie inside the segments BK and AK, respectively. Then, clearly, the circle k is the incircle of triangle ABK and the K-excircle of triangle DCK. Now, let the incircle of triangle DCK touch the side CD of this triangle at a point E'. Then, by the well-known formulas for the tangents from the vertices of a triangle to its incircle, we have $CE^{\prime}=\frac{CD+KC-KD}{2}$. On the other hand, since the point F is the point where the circle k, which is the K-excircle of triangle DCK, touches the side CD of this triangle, we have $DF=\frac{CD+KC-KD}{2}$. Hence, CE' = DF. Therefore, DF = CE holds if and only if CE = CE'. But since the points E and E' both lie on the segment CD, we have CE = CE' if and only if E = E'. Hence, DF = CE holds if and only if E = E'.

Let the incircle k of the trapezoid ABCD touch its side AB at a point H. Then, $OH\perp AB$, since O is the center of the circle k. On the other hand, $OF\perp CD$, as the point F is the point where the circle k touches the side CD. But since AB || CD, we thus get OH || OF. The lines OH and OF must therefore coincide (in fact, they are parallel and they have a common point - namely, the point O). This yields that the point O lies on the segment HF. Also, since the points H and F lie on the circle k, whose center is O, we have OH = OF. Now, since AB || CD, by Thales, $\frac{HM}{EF}=\frac{OH}{OF}$; since OH = OF, we thus get HM = EF. Combined with HM || EF (this is equivalent to AB || CD), this yields that the quadrilateral HEFM is a parallelogram; thus, HE || MF, so the point E is the point of intersection of the parallel to the line MF through the point H with the line CD.

Let N be the midpoint of the segment CD. Then, NC = ND; since CE' = DF, we thus have NE' = CE' - NC = DF - ND = NF, so the point N is the midpoint of the segment E'F.

Now, since AB || CD, and since the points D and C lie on the lines KA and KB, there exists a homothety h with center K which maps the points A and B to the points D and C. Hence, this homothety h must map the midpoint M of the segment AB to the midpoint N of the segment DC; since the center of the homothety h is the point K, it thus follows that the points K, M and N are collinear.

On the other hand, the homothety h must leave the point K fixed (since K is the center of this homothety); since it maps the points A and B to the points D and C, it must take the triangle ABK to the triangle DCK; consequently, it maps the point H where the incircle k of triangle ABK touches its side AB to the point E' where the incircle of triangle DCK touches its side CD. Since the center of the homothety h is the point K, we thus conclude that the points K, H and E' are collinear.

Now, in order to solve the problem, we have to prove two assertions:

[i]Assertion 1.[/i] If DF = CE, then $AB=2\cdot CD$.
[i]Assertion 2.[/i] If $AB=2\cdot CD$, then DF = CE.

[i]Proof of Assertion 1.[/i] Assume that DF = CE. Then, as we showed above, E = E', so the collinearity of the points K, H and E' becomes the collinearity of the points K, H and E. Also, instead of saying that the point N is the midpoint of the segment E'F, we can now state that the point N is the midpoint of the segment EF; thus, $EF=2\cdot EN$. Since HM = EF, we thus have $HM=2\cdot EN$, and $\frac{HM}{EN}=2$. Now, since AB || CD, Thales yields $\frac{AB}{CD}=\frac{KA}{KD}$, $\frac{KA}{KD}=\frac{KH}{KE}$ (since the points K, H and E are collinear) and $\frac{KH}{KE}=\frac{HM}{EN}$. Together with $\frac{HM}{EN}=2$, this yields $\frac{AB}{CD}=2$, and thus $AB=2\cdot CD$. Thus, Assertion 1 is proven.

[i]Proof of Assertion 2.[/i] Assume that $AB=2\cdot CD$. Then, $\frac{AB}{CD}=2$. But since AB || CD, Thales yields $\frac{AB}{CD}=\frac{KA}{KD}$ and $\frac{KA}{KD}=\frac{KM}{KN}$. Hence, $2=\frac{KM}{KN}$, so that $KM=2\cdot KN$, and thus the point N is the midpoint of the segment KM. But on the other hand, the point N is the midpoint of the segment E'F. Thus, the diagonals KM and E'F of the quadrilateral KE'MF bisect each other (they have the same midpoint N); hence, this quadrilateral KE'MF is a parallelogram, and it follows that KE' || MF. Hence, the line KE' is the parallel to the line MF through the point H. Consequently, the point E', lying on the line KE' and on the line CD, must be the point of intersection of the parallel to the line MF through the point H with the line CD. But this is exactly the way we characterized the point E in the above. Hence, E = E', and thus, according to the above, DF = CE. Hence, Assertion 2 is established, and the problem is solved.

  Darij


The mean of a collection of five positive integers is 7. If the collection has a unique mode, what is the greatest possible member of the collection?

hint

I don't think the part

[quote]If the collection has a unique mode, [/quote]

really matters....

dont' get distracted by it

[hide="myanswer"]35-4=31

I think the answer is 31.
 and the set is {1,1,1,1,31}[/hide]