algebra
polynomial
vector
linear algebra
matrix
inequalities
function

[color=orange][size=150]Open Competition for University Students[/size]
of The Faculty of Mechanics and Mathematics of Kyiv National Taras Shevchenko University[/color]

15.03.2006

[color=indigo]Problems for 1-2 years students[/color]

[b]1.[/b] Find all positive integers $n$ such that the polinomial $(x^{4}-1)^{n}+(x^{2}-x)^{n}$ is divisible by $x^{5}-1$.
(A. Kukush)

[b]2. [/b] Let $z\in\mathbb{C}$ be such that points $z^{3},$ $2z^{3}+z^{2},$ $3z^{3}+3z^{2}+z$ and $4z^{3}+6z^{2}+4z+1$ are the vertices of an inscribed quadrangle at complex plane. Find $Re\,z$.
(V. Brayman) [url=http://www.mathlinks.ro/Forum/viewtopic.php?p=582011#582011][color=olive]link to discussion/solution[/color][/url]

[b]3.[/b] Find the minimum over all unit vectors $x_{1},$ $\ldots,$ $x_{n+1}\in\mathbb{R}^{n}$ of $\max\limits_{1\le i < j \le n+1}(x_{i}, x_{j}).$
(A. Bondarenko,  M. Vyazovska)

[b]4. [/b] Let $E_{m}$ be $m\times m$ identity matrix, $A\in \mathbb{R}^{m\times n}$ and let $B$ be symmetric $n\times n$ matrix such that block matrix $\left(\begin{array}{cc}E_{m}& A \\ A^{T}& B\end{array}\right)$ is positively defined. Prove that "matrix determinant" $B-A^{T}A$ is also positively defined. (Symmetric matrix $M$ is said to be positively defined if for every vector-column $x\ne0$ the inequality $x^{T}Mx>0$  holds.)
(A. Kukush) [url=http://www.mathlinks.ro/Forum/viewtopic.php?p=554995#554995][color=olive]link to discussion/solution[/color][/url]

[b]5.[/b] Does there exist an infinite set of square symmetric matrices $\mathcal{M}$ such that for any distinct matrices $A, B\in \mathcal{M}$  $AB^{2}=B^{2}A$ holds but $AB\ne BA?$
(V. Brayman) [url=http://www.mathlinks.ro/Forum/viewtopic.php?p=554891#554891][color=olive]link to discussion/solution[/color][/url]

[b]6.[/b] Let $f: (0,+\infty)\to\mathbb{R}$ be continuous concave function, $\lim\limits_{x\to+\infty}f(x)=+\infty$, $\lim\limits_{x\to+\infty}\frac{f(x)}{x}=0$. Prove that $\sup\limits_{n\in\mathbb{N}}\ \{f(n)\}=1$, where $\{a\}=a-[a]$ is fractional part of $a$.
(O. Nesterenko) [url=http://www.mathlinks.ro/Forum/viewtopic.php?p=554978#554978][color=olive]link to discussion/solution[/color][/url]

[b]7.[/b] Does there exist a continuous function $f: \mathbb{R}\to(0,1)$ such that the sequence $a_{n}=\int_{-n}^{n}f(x)\,dx,\ n\ge1,$ converges and the sequence $b_{n}=\int_{-n}^{n}f(x)\ln f(x)\,dx,\ n\ge1,$ is divergent?
(A. Kukush) [url=http://www.mathlinks.ro/Forum/viewtopic.php?p=554979#554979][color=olive]link to discussion/solution[/color][/url]

[b]8.[/b] Let $P(x)$ be a polinomial such that there exist infinitely many pairs of integers $(a,b)$ such that $P(a+3b)+P(5a+7b)=0$. Prove that the polinomial $P(x)$ has an integer root.
(V. Brayman) [url=http://www.mathlinks.ro/Forum/viewtopic.php?p=577809#577809][color=olive]link to discussion/solution[/color][/url]

[b]9.[/b] For every real numbers $a_{1}, a_{2}, \ldots, a_{n}\in\mathbb{R}\setminus\{0\}$ prove the inequality $\sum\limits_{i,j=1}^{n}\dfrac{a_{i}a_{j}}{a_{i}^{2}+a_{j}^{2}}\ge0$.
(S. Novak, Great Britain) [url=http://www.mathlinks.ro/Forum/viewtopic.php?p=554983#554983][color=olive]link to discussion/solution[/color][/url]

[color=indigo]Problems for 3-4 years students[/color]
[b]1.[/b] Let $z\in\mathbb{C}$ be such that points $z^{3},$ $2z^{3}+z^{2},$ $3z^{3}+3z^{2}+z$ and $4z^{3}+6z^{2}+4z+1$ are the vertices of an inscribed quadrangle at complex plane. Find $Re\,z$.
(V. Brayman) [url=http://www.mathlinks.ro/Forum/viewtopic.php?p=582011#582011][color=olive]link to discussion/solution[/color][/url]

[b]2.[/b] Does there exist a continuous function $f: \mathbb{R}\to(0,1)$ such that $\int_{-\infty}^\infty f(x)\,dx<\infty$ while $\int_{-\infty}^\infty f(x)\ln f(x)\,dx$ is divergent?
(A. Kukush) [url=http://www.mathlinks.ro/Forum/viewtopic.php?p=554979#554979][color=olive]link to discussion/solution[/color][/url]

[b]3.[/b] Let $E_{m}$ be $m\times m$ identity matrix, $A\in \mathbb{R}^{m\times n}$ and let $B$ be symmetric $n\times n$ matrix such that block matrix $\left(\begin{array}{cc}E_{m}& A \\ A^{T}& B\end{array}\right)$ is positively defined. Prove that "matrix determinant" $B-A^{T}A$ is also positively defined.
(A. Kukush) [url=http://www.mathlinks.ro/Forum/viewtopic.php?p=554995#554995][color=olive]link to discussion/solution[/color][/url]

[b]4.[/b] Does there exist an infinite set of square symmetric matrices $\mathcal{M}$ such that for any distinct matrices $A, B\in \mathcal{M}$ holds $AB^{2}=B^{2}A$ but $AB\ne BA?$
(V. Brayman) [url=http://www.mathlinks.ro/Forum/viewtopic.php?p=554891#554891][color=olive]link to discussion/solution[/color][/url]

[b]5.[/b] a) Let $\xi$ and $\eta$ be random variables (not necessarily independent) which have continuous distribution functions. Prove that $\min(\xi, \eta)$ also has continuous distribution function.
b) Let $\xi$ and $\eta$ be random variables which have densities. Is it true that $\min(\xi, \eta)$ also has a density?
(A. Kukush, G. Shevchenko)

[b]6.[/b] Is it possible to choose uncountable set $\mathcal{A}\subset l_{2}$ of elements with unit norm such that for any distinct $x=(x_{1}, \ldots, x_{n}, \ldots)$, $y=(y_{1}, \ldots, y_{n}, \ldots)$ from $\mathcal{A}$ the series $\sum\limits_{n=1}^{\infty} |x_{n}-y_{n}|$ is divergent?
(A. Bondarenko) [url=http://www.mathlinks.ro/Forum/viewtopic.php?p=555328#555328][color=olive]link to discussion/solution[/color][/url]

[b]7.[/b] Let $\xi, \eta$ be independent identically distributed random variables such that $P(\xi\ne0)=1$. Prove the inequality $ E\dfrac{\xi\eta}{\xi^{2}+\eta^{2}}\ge0$.
(S. Novak, Great Britain)

[b]8.[/b] For every $n\in\mathbb{N}$ find the minimal $\lambda>0$ such that for every convex compact set $K\subset\mathbb{R}^{n}$ there exist a point $x\in K$ such that the set which is homothetic to $K$ with centre $x$ and coefficient $(-\lambda)$ contains $K$.
(O. Lytvak, Canada)

[b]9.[/b] Let $X=L_{1}[0,1]$ and let $T_{n}: X\to X$ be the sequence of nonnegative (i.e. $f\ge0$ $\Longrightarrow$ $T_{n}f\ge0$) linear operators such that $\|T_{n}\|\le 1$ and $\lim\limits_{n\to\infty}\|f-T_{n}f\|_{X}=0$ for $f(x)\equiv x$ and for $f(x)\equiv1$. Prove that $\lim\limits_{n\to\infty}\|f-T_{n}f\|_{X}=0$ for every $f\in X$.
(A. Prymak)

1.6: for $\epsilon > 0$, take $N_0$ such that $0 < f(n+1)-f(n) < \epsilon$ for $n > N_0$. Then, because $f$ tends to infinity, we get that $\sup \{f(n)\} \geq 1-\epsilon$.

1.7: if $f$ behaves like $\frac{1}{x ln(x)^{\frac{3}{2}}}$ it should work.

1.9 consider the matrix $M(x)_{i,j}=x^{a_i^2 - \frac{1}{2}}$ for $0<x<1$. $M(x)^tM(x)=A(x)$ is a positive matrix whose $(i,j)$ entry is $x^{a_i^2+a_j^2-1}$. Then $A=\int_0^1 A(x)dx$ is the matrix $A_{i,j}=\frac{1}{a_i^2+a_j^2}$. This is why $A$ is positive, and the conclusion follows because $\sum_{i,j} \frac{a_i a_j}{a_i^2+a_j^2}=(v,Av) \geq 0$ where $v=(a_1,a_2,..,a_n)^t$.

For 1.4 and 2.3 (to respect alekk's notational conventions :)), the following should work:

The positive definiteness of $U=\begin{pmatrix}1&A\\A^t&B\end{pmatrix}$ is equivalent to the fact that for all $x\in\mathbb R^m,y\in\mathbb R^n$, not both zero, we have $x^tx+x^tAy+y^tA^tx+y^tBy>0$. By taking $y$ to be arbitrary and non-zero and $x=-Ay$, we get precisely $y^t(B-A^tA)y>0$, as desired.

I think these should be posted in separate topics. The moderators aren't going to like the mess that this topic is likely to become if we keep posting proofs here :).

Guys, please each problem in it's own topic :)


induction
inequalities
limit
algebra proposed
algebra

$\sqrt {1+\sqrt {2+\ldots +\sqrt {n}}}< 2 , \forall n\ge 1$

$\sqrt {1+\sqrt {2+\sqrt {3+\ldots +\sqrt {n}}}}<\sqrt {2+\sqrt {2+\sqrt {3+\ldots +\sqrt {n}}}} , \forall n\ge 1$

$\sqrt {2+\sqrt {2+\sqrt {2+\ldots +\sqrt {2}}}}<\sqrt {2+\sqrt {2+\sqrt {3+\ldots +\sqrt {n}}}} , \forall n\ge 1$

Now we have

$\sqrt {1+\sqrt {2+\sqrt {3+\ldots +\sqrt {n}}}}<\sqrt {2+\sqrt {2+\sqrt {2+\ldots +\sqrt {2}}}} , \forall n\ge 1$

And that is true because

$1+\sqrt {2+\sqrt {3+\ldots +\sqrt {n}}}<1+1+\sqrt {2+\sqrt {2+\ldots +\sqrt {2}}} , \forall n\ge 1$

Is obviously that

$\sqrt {2+\sqrt {2+\sqrt {2+\ldots +\sqrt {2}}}}<2$

And I prove that

$\sqrt {1+\sqrt {2+\ldots +\sqrt {n}}}<\sqrt {2+\sqrt {2+\sqrt {2+\ldots +\sqrt {2}}}}< 2 , \forall n\ge 1$

[quote="enescu"]Prove that $\sqrt {1+\sqrt {2+\ldots +\sqrt {n}}}<2$, $\forall n\ge 1$.[/quote]

I think this problem is really well-known. I think I also have seen it on some "Tournament Of Town" paper. Probably our goldie is really loved by the mathematical community or it is to easy to rediscover it.  :)

[quote="Lucmar"]Now we have

$\sqrt {1+\sqrt {2+\sqrt {3+\ldots +\sqrt {n}}}}<\sqrt {2+\sqrt {2+\sqrt {2+\ldots +\sqrt {2}}}} , \forall n\ge 1$

And that is true because

$1+\sqrt {2+\sqrt {3+\ldots +\sqrt {n}}}<1+1+\sqrt {2+\sqrt {2+\ldots +\sqrt {2}}} , \forall n\ge 1$

[/quote]
I am not sure I understand this argument.

By the way, Orlando, I think you are refering to TOT problem 4 Spring 1987. But this is
$\sqrt {2\sqrt {3\sqrt {4\ldots \sqrt {n}}}}<3.$

It all follows from $\sqrt{k+\sqrt{k+1+\sqrt{\ldots+\sqrt n}}}<k+1$ for $k\ge 1$. It can be proven by "induction", starting from $k=n$ and going down to $k=1$.

Yes, of course. The same approach works for the TOT problem.

[quote="enescu"][quote="Lucmar"]Now we have

$\sqrt {1+\sqrt {2+\sqrt {3+\ldots +\sqrt {n}}}}<\sqrt {2+\sqrt {2+\sqrt {2+\ldots +\sqrt {2}}}} , \forall n\ge 1$

And that is true because

$1+\sqrt {2+\sqrt {3+\ldots +\sqrt {n}}}<1+1+\sqrt {2+\sqrt {2+\ldots +\sqrt {2}}} , \forall n\ge 1$

[/quote]
I am not sure I understand this argument.
[/quote]
I rise the equation to the 2nd power.

I wonder if it is another way to do the problems other than "induction". :huh:

[quote="Lucmar"]

I rise the equation to the 2nd power.

[/quote]
That I understood.
I still don't see why the inequality
 \[ \sqrt {2+\sqrt {3+\ldots +\sqrt {n}}}<1+\sqrt {2+\sqrt {2+\ldots +\sqrt {2}}} , \forall n\ge 1\]
is that obvious.

:D , i thinks this pro very easy and we have pro:
[b]PRO [/b]: assume q possitive real number,define: $f_q({n})=(1+(2+(........+n^q)^q).....)^q)^q$,show that if $q<1$ then there exist $\lim{f_q({n})}$
i think lucmar have some mistake
Sol:$\sqrt{n}<n$ so $\sqrt{n-1+\sqrt{n}}<\sqrt{2n-1}<n-1$ for $n-1>4$
and we obtain $\sqrt {1+\sqrt {2+\sqrt {n}}}<\sqrt{1+\sqrt{2+\sqrt{3+\sqrt{2\cdot{4}-1}}}}<2$

[quote=enescu]Prove that $$\sqrt {1+\sqrt {2+\ldots +\sqrt {n}}}<2$$  $\forall n\ge 1$[/quote]
For any natural $n$ [url=https://artofproblemsolving.com/community/c893771h2065978p14757036]prove the inequality[/url]
$$\sqrt{2\sqrt{2}{\sqrt{3}\sqrt{4 ...\sqrt{n-1\sqrt{n}}}}} <3$$
[b]Tournament of Towns, Spring 1987[/b]


A right triangle has sides whose lengths are 4 + 2^(1/3) and 3 + 7x2^(1/3). What is the length of the hypotenuse? Write your answer in the form a + bxc^(1/3), where a, b, and c are positive integers.

Square and add them together, then the only possible choices (due to the number under the cube root) for c is $2$ or $4$, so just plug in those two and you get an answer.


Let $ ABCD$ be a convex quadrilateral for which denote $ \left|\begin{array}{c} E\in AB\cap CD \\
 \\
F\in AD\cap BC\end{array}\right|$ . Define the points

$ \left|\begin{array}{c} N\in (FB\ ,\ FN \equal{} FA \\
 \\
M\in (EB\ ,\ EM \equal{} EC \\
 \\
Q\in AN\cap CM\ ,\ T\in DQ\cap AC\end{array}\right|$ and $ \left|\begin{array}{c} P\in AD\cap CM \\
 \\
R\in CD\cap AN \\
 \\
S\in AC\cap PR\end{array}\right|$ . Prove that $ MA \equal{} NC\ \Longleftrightarrow$

$ \frac {TA}{TC} \equal{}\frac {DA}{DC}$ $ \Longleftrightarrow$  $ \frac {SA}{SC} \equal{} \frac {DA}{DC}$ , i.e. the rays $ [DQ$ , $ [DS$ are the bisectors of the angle $ \widehat{ADC}$ .

See [url=http://www.mathlinks.ro/viewtopic.php?t=277841][color=red][b]here[/b][/color][/url] a particular case when $ ABCD$ is a parallelogram.

By Menelaus' theorem for $ \triangle FDC$ cut by transversal $ \overline{ANR},$ we get

$ \frac {RC}{RD} \cdot \frac {DA}{FA} \cdot \frac {FN}{NC} \equal{} 1  \Longrightarrow \ \frac {RC}{RD} \equal{} \frac {NC}{DA} \ \ (1)$

By Menelaus' theorem for  $ \triangle EAD$ cut by transversal $ \overline{PMC},$ we get

$ \frac {PA}{PD} \cdot \frac {DC}{CE} \cdot \frac{EM}{AM} \equal{} 1  \Longrightarrow \ \frac {PA}{PD} \equal{} \frac {AM}{DC} \ \ (2)$

By Menelaus' theorem for $ \triangle DPR$ cut by transversal $ \overline{ACS},$ we get

$ \frac {SC}{SA} \cdot \frac {PA}{PD} \cdot \frac{RD}{RC} \equal{} 1 \ \ (3)$

Combining $ (3)$ with $ (1)$ and $ (2)$ we get $ \ : \ \frac {SC}{SA} \cdot \frac {MA}{DC} \cdot \frac {DA}{NC} \equal{} 1$

Hence, it follows that $ MA \equal{} NC  \Longleftrightarrow \ \frac {SA}{SC} \equal{} \frac {DA}{DC}$

[u]Thank you[/u], [b]Luisgeometria ![/b]

Your proof is identically with mine. See again the enunciation of my proposed
problem because I added an interesting question  to the conclusion.

[quote="Vigil Nicula"]the rays $ [DQ,$  $ [DS$ are the bisectors of the angle $ \widehat{ADC}.$ [/quote]
We already know that $ \frac {_{SC}}{^{SA}} \equal{} \frac {_{DC}}{^{DA}}$ $ \Longleftrightarrow$ $ MA \equal{} NC.$ Then it follows that $ S$ is the foot of the external bisector of $ \angle ADC$ in $ \triangle ADC.$ Thus, $ T$ is the internal bisector of $ \angle ADC$ since the pencil of rays $ DA,DC,DS,DQ$ is harmonic $\Longrightarrow$ $ (A,C,S,T)$ are harmonically separeted $\Longrightarrow$  $ DQ$ and $ DS$ bisect $ \angle ADC$ internally and externally.

[color=darkblue][size=117][b]Here is the essential enunciation of my proposed problem and its proof. I like it very much.[/b][/size][/color]

[quote="Virgil Nicula"][color=darkred]Let $ ABCD$ be a convex quadrilateral for which denote $ \left|\begin{array}{c} E\in AB\cap CD \\
 \\
F\in AD\cap BC\end{array}\right|$ .

Define the points $ \left|\begin{array}{c} N\in (FB\ ,\ FN \equal{} FA \\
 \\
M\in (EB\ ,\ EM \equal{} EC\end{array}\right|$ and $ Q\in AN\cap CM$ .

Prove that $ MA \equal{} NC\ \Longleftrightarrow$ the rays $ [DQ$ is  one of the the bisectors of the angle $ \widehat{ADC}$ .

See [/color] [url=http://www.mathlinks.ro/viewtopic.php?t=277841][color=green][b]here[/b][/color][/url] [color=darkred]a particular case when $ ABCD$ is a parallelogram.[/color][/quote]

[color=darkblue][b][u]Proof[/u].[/b] Define the points $ \left|\begin{array}{c} P\in MC\cap AD \\
 \\
R\in NA\cap CD\end{array}\right|$ . Apply the [u][b]Menelaus[/b]' theorem[/u] to the mentioned transversals/triangles :

$ \left|\begin{array}{cccc} \overline {MCP}/ADE\ : & \frac {PD}{PA}\cdot\frac {MA}{ME}\cdot\frac {CE}{CD} \equal{} 1 & \stackrel{(CE \equal{} ME)}{\ \ \implies\ \ } & \frac {PA}{PD} \equal{} \frac {MA}{CD}\ \ (1) \\
 \\
\overline {NAR}/CDF\ : & \frac {RD}{RC}\cdot\frac {NC}{NF}\cdot\frac {AF}{AD} \equal{} 1 & \stackrel{(AF \equal{} NF)}{\ \ \implies\ \ } & \frac {RD}{RC} \equal{} \frac {AD}{NC}\ \ (2)\end{array}\right|$ . Define $ T\in DQ\cap AC$ and apply the

[u][b]Ceva[/b]'s theorem[/u] to $ Q$ for $ \triangle\ ACD\ : \ \ \frac {TA}{TC}\cdot\frac {RC}{RD}\cdot\frac {PD}{PA} \equal{} 1$ $ \implies$ $ \frac {TA}{TC} \equal{} \frac {PA}{PD}\cdot\frac {RD}{RC}$ $ \stackrel{(1)\wedge (2)}{\ \implies\ }$ $ \boxed {\ \frac {TA}{TC} \equal{} \frac {MA}{NC}\cdot\frac {DA}{DC}\ }\ (3)$ .

In conclusion, $ MA \equal{} NC\ \Longleftrightarrow\ \frac {TA}{TC} \equal{} \frac {DA}{DC}\ \Longleftrightarrow$ the rays $ [DQ$ is  one of the bisectors of the angle $ \widehat{ADC}$ .

[b][u]Remark[/u].[/b] Define the point $ S\in PR\cap AC$ and apply the [u][b]Menelaus[/b]' theorem[/u] to the pair $ \overline {PRS}/ACD$ :

$ \frac {PD}{PA}\cdot\frac {SA}{SC}\cdot\frac {RC}{RD} \equal{} 1$ $ \implies$ $ \frac {SA}{SC} \equal{} \frac {PA}{PD}\cdot\frac {RD}{RC}$ $ \stackrel{(1)\wedge (2)}{\ \ \implies\ \ }$ $ \frac {SA}{SC} \equal{} \frac {MA}{NC}\cdot\frac {DA}{DC}$ $ \stackrel{(3)}{\ \ \implies\ \ }$ $ \frac {SA}{SC} \equal{} \frac {TA}{TC}$ .

In conclusion, $ MA \equal{} NC\ \Longleftrightarrow$  the ray $ [DS$ is another bisector of the angle $ \widehat {ADC}$ .[/color]


Write $\frac{1}{10+7 \sqrt[3]{2}+4 \sqrt[3]{4}}$ in the form $a+b \sqrt[3]{2}+c \sqrt[3]{4}, a, b, c \in \mathbb{Q}$.

[hide="Hint"] There's an interesting factorization involving $x^{3}+y^{3}+z^{3}$ that might be useful here.  [/hide]

[hide="Hint"]
$\frac{1}{\sqrt[3]{a}+\sqrt[3]{b}+\sqrt[3]{c}}= \frac{\left(\sqrt[3]{a^{2}}+\sqrt[3]{b^{2}}+\sqrt[3]{c^{2}}-\sqrt[3]{ab}-\sqrt[3]{bc}-\sqrt[3]{ac}\right) \left[(a+b+c)^{2}+3(a+b+c)\sqrt[3]{abc}+9\sqrt[3]{(abc)^{2}}\right]}{(a+b+c)^{3}-27abc}$

Using factorization $x^{3}+y^{3}+z^{3}-3xyz = (x+y+z)(x^{2}+y^{2}+z^{2}-xy-yz-xz)$ then after $x^{3}-y^{3}= (x-y)(x^{2}+xy+y^{2})$.

I wrote a complete explanation in my blog a month ago (in portuguese). It's possible to understand without know portuguese. Just access my WWW an look for 01/06/2006 post ("Racionalização difícil").
[/hide]

[hide="i got"]
$\frac{946}{5633}-\sqrt[3]{2}\frac{817}{5633}+\sqrt[3]{4}\frac{387}{11266}$

I don't know if fractions are in their lowest form :)
[/hide]


abstract algebra
pigeonhole principle
modular arithmetic
induction
algebra
polynomial
vector

Let p be a prime. A set X is called good if
(i) the prime divisors of X comprise p-1 elements
(ii) there is no subset of X s.t. the product of its elements is a perfect p-th power.
Find the largest number of elements in a good set (in terms of p).
The problem is obviously equivialant to the following (its not really number theory lyk it looks):
Consider the p^(p-1) strings with p-1 numbers mod p. What is the largest number of these we can have (they can be repeated) s.t. the 'sum' of no subset is
0 0 0 ... 0 (p-1 '0's). (sorry if that wasnt phrased properly  :D )
I think the answer is 1/2(p^p-1 - 1) but im not sure, and i have no idea how to prove it. it works for p=3  :) but checking larger values of p would be hard  :?.

I didn't want to read the solution, but I glimpsed at the answer, and I'm afraid to tell you that that is not it :). I just wanted to say this in order to prevent you from trying to prove something wrong :). I'll try it myself.

This is a special case with $r=p-1, e_1 = \cdots = e_r=1$ in the following WELL, WELL KNOWN theorem.

Theorem. (Olson, 1969, A combinatorial problem in finite abelian groups, Journal of Number Theory, Vol. 1, pp. 8--10. (note: I know the information on this reference by heart  :lol: )).  Let
\[
G = \mathbb{Z}_{p^{e_1}} \oplus \mathbb{Z}_{p^{e_2}} \oplus \cdots \oplus \mathbb{Z}_{p^{e_r}}
\]
be a finite abelian $p$-group. Let
\[
k = 1 + \sum_{1 \leq i \leq r} (p^{e_i} - 1).
\]
Then, for any $k$ elements $g_1,\ldots,g_k \in G$, there exists a non-empty subset $I \subseteq \{1,\ldots,k\}$ such that $\prod_{i \in I} g_i = 1$ (the identity element of $G$.)

In the special case when $e_1 = \cdots = e_r = 1$, this is an easy corollary of the Chevalley-Warning Theorem (see andrew's proof.)  For the general case, although there are two other proofs, the following (in fact, the original one) is the simplest AND THE MOST BEAUTIFUL!!!

Consider the group algebra $\mathbb{F}_pG$. It is well-known that the Jacobson radical $J$ of $\mathbb{F}_pG$ (which is defined as the intersection of all maximal left ideals in a ring) coincides with the augmentation ideal (i.e. the ideal in $\mathbb{F}_pG$ generated by the elements $1-g$, $g \in G$) and is nilpotent of nilpotency class $k$:
\[
J^k = 0.
\]
This is actually proven very easily, elementarily and... beautifully (I'm very excited when discussing one of my FAVORITE results  ;) .) Indeed, by making use of the identity $1-xy = (1-x) + x(1-y)$, we see that, if $\alpha_1, \ldots, \alpha_r$ is a normal basis for $G$ (with each $\alpha_i$ of order $p^{e_i}$), each product of the form $(1-g_1) \cdots (1-g_k)$ is a linear combination of products of the form
\[
(1-\alpha_1)^{k_1} \cdots (1-\alpha_r)^{k_r},
\]
where $k_1 +\cdots + k_r = k = 1 + \sum_i (p^{e_i} - 1)$. By the pigeonhole principle, for any such $r$-tuple $(k_1,\ldots,k_r)$, there exists an index $i$ for which $k_i \geq p^{e_i}$, and, because in $\mathbb{F}_pG$ we have
\[
(1-\alpha_i)^{p^{e_i}} = 1 + (-\alpha_i)^{p^{e_i}} = 1 + (-1)^p = 0,
\]
it follows that
\[
(1-\alpha_1)^{k_1} \cdots (1-\alpha_r)^{k_r} = 0.
\]
Thus,
\[
(1-g_1) \cdots (1-g_k) = 0,
\]
as a linear combination of elements of the form $(1-\alpha_1)^{k_1} \cdots (1-\alpha_r^{e_r})$, proving the nilpotency of $J$ of class $k$.

Now, the theorem follows easily (!). Write $\prod (1-g_i)$ in normal form, as $\sum_{g \in G} k_gg$, $k_g \in \mathbb{F}_p$. Interpret the product combinatorially. If $E(1)$ denotes the number of representations of the identity $1$ as the product of an even number of elements among $g_1,\ldots,g_k$ and $O(1)$ is the number of representation of $1$ as the product of an odd number of elements, then the coefficient of the identity of $G$ in the product
\[
(1-g_1) \cdots (1-g_k)
\]
is equal to $1 + E(1) - O(1)$. On the other hand, we know that this product is $0$ in $\mathbb{F}_pG$, so
\[
O(1) \equiv 1 +  E(1) \pmod{p}.
\]
In particular, at least one of $O(1)$ and $E(1)$ is non-zero. This proves the claim.  ;)

This theorem is the first non-trivial result in Zero-Sum Theory, one of the three main fields of Additive Number Theory. (the field I am researching.) For those interested in such problems, don't hesitate to contact me at avding@hotmail.com or vessel@mit.edu.

As long as we are here, why not give an application of Olson's theorem to the following even more well-known result?

Theorem. (Erdos-Ginzburg-Ziv, 1961.) From any $2n-1$ integers one may choose some $n$ numbers whose sum is divisible by $n$.

Proof. By induction on the number of prime factors of $n$, it suffices to consider the when $n=p$ is a prime (check this: the correctness of the assertion for $n=k$ and for $n=l$ implies the assertion for $n=kl$.) Let $a_1,\ldots,a_{2p-1} $ be the given $2p-1$ numbers. Consider the group $G = \mathbb{Z}_p \oplus \mathbb{Z}_p$. We may identify its elements with pairs $(x,y)$ of integers, the group operation given by componentwise addition modulo $p$. Consider the elements
\[
(a_1,1), (a_2,1), \ldots, (a_{2p-1},1) \in G.
\]
This is a sequence of $2p-1= 1 + (p-1) + (p-1)$ elements of $G = \mathbb{Z}_p \oplus \mathbb{Z}_p$. By Olson's theorem, there is a non-empty set $I \subseteq \{1,\ldots,2p-1\}$ such that
\[
\sum_{i \in I} (a_i,1) = (0,0).
\]
By looking at the second components, we must have $p \, | \, |I|$. However, $0< |I| < 2p$, which forces $|I| = p$. In this manner, we have chosen exactly $p$ numbers $a_i$ ($i \in I$), the sum of which is $0 \pmod{p}$. The proof is complete.

Comment. How can this problem by proposed at an IMO?!  :?

Dear Vess, I apologise, but I have to say that the concept of well well known is very relative. I don't think anyone can be expert in all fields and can know absolutely anything in any such field. This is the reason for which we do not know so advanced theorems. You are an expert, you work with them and so you know them very well. But don't asks us to know them as well as you.

Yes, I completely agree. My comment raises another point, though. I don't say that this problem is unsuitable for IMO because it is well-known; it's not, in fact, well-known in math olympiad circles. The point is, the IMO is a challenge not only for contestants, but also for the proposers of problems. A good olympiad problem *must*: 1) have a neat and simple formulation (as this one, by the way), 2) have at least one smart and relatively short solution, and 3) revolve around a conceptually new fresh mathematical idea. (see Erd\H{o}s'  problems.) True, creating such a problem is a different endeavor and is much, much more difficult than solving it, but, after all, the IMO has a reputation of the supreme highschool math competition. Proposing a classical theorem at this high forum (the IMO) may be viewed as plagiarism. Moreover, it is kind of unfair to the contestants, for some may be acquainted with this idea and quickly solve the problem.

 From this point of view, both this problem (athough a beautiful one) and 2004/6 are unsuitable for an IMO event. The IMO, in my opinion, is not an examination of the breadth of contestant's knowledge and resourcefulness, but of his/her inner intelligence and *potential* of being resourceful in a scientific research. Basically, research and competition are *very* different concepts.

--Vesselin

Yes, I completely agree with you that research problems shouldn't be given in IMO, nor problems known very well but by the researchers. Nice problems with not very long solutions and with beautiful ideas I like most. Unfortunately, I saw how hard is to create a beautiful problem this year. Allmost all problems I proposed in our TST do not enter this category simply because they don't have smart ideas. At least I hope they aren't so well known, but I doubt smart people would ask such questions as those problems.  But as you said, it is quite super-hard to find a problem with a completely new idea. Allmost impossible, I would say.

Could someone please explain andrew's proof? I can't quite get the last argument, the one where he mentions "not more than $(p-1)^2$ variables".

Andrew's argument is as follows.

Theorem. (Chevalley-Warning.) Let $p$ be a prime and let $f_1,\ldots,f_n \in \mathbb{F}_p [x_1,\ldots,x_k]$ be polynomials over $\mathbb{F}_p$ such that $\sum_i \deg{f_i} < k$ (by $\deg{f}$, we mean the total degree of a polynomial, i.e. the maximal degree of a composing monom.) Suppose that the system
\[
f_1 = \cdots = f_n = 0
\]
has a solution $(x_1,\ldots,x_k)$. Then, this system has another solution.

Proof. We will show, more generally, that the number of solutions of the system is divisible by $p$, so the system cannot have a unique solution.

The following fact is well-known: if $0 \leq j < p-1$, then

Lemma. If at least one of $s_1,\ldots,s_k \in \mathbb{N}_0$ is in the set $\{0,1,\ldots,p-2\}$, then
\[
\sum_{x_1,\ldots,x_k} x_1^{s_1} \cdots x_k^{s_k} = 0.
\]
Here, the sum is over all $x_1,\ldots,x_k \in \mathbb{F}_p$.

Proof of the lemma.  The above sum factors $\prod_i \sum_{x_i} \big( x_i^{s_i} \big)$, and the lemma follows from the quite well-known fact that
\[
\sum_{0 \leq l \leq p-1} l^j \equiv 0 \pmod{p}.
\]
for $0 \leq j \< p-1$.

 Now, Consider the polynomial
\[
f(x_1,\ldots,x_k) := (1-f_1^{p-1})(1-f_2^{p-1}) \cdots (1-f_n^{p-1}).
\]
Let $N$ be the total number of solutions to our system. Then, because by Fermat's Little Theorem we have $a^{p-1} = 1$, if $a \neq 0$, and $0$, if $a=0$, we have
\[
N \equiv \sum_{x_1,\ldots,x_k}  f(x_1,\ldots,x_k) \pmod{p}.
\]
On the other hand, it is easy to see that the latter sum is the linear combination of monomials of the form
\[
x_1^{s_1} \cdots x_k^{s_k},
\]
where $s_1 + \cdots + s_k \leq (p-1) \sum_i \deg{f_i} < (p-1)k$. By the pigeonhole principle, some index $i$ satisfies $s_i < p-1$. It follows, by the lemma, that each of these monomials is $0$ in $\mathbb{F}_p$, thus so is $N$. The proof of the Chevalley-Warning theorem is complete.

Our problem is an easy corollary. We will show, more generally (the problem is a special case with $k=p-1$) that if we are given  more than $k(p-1)$ vectors in $\mathbb{F}_p^k$, then some of them have sum $0$. Let $s=1+k(p-1)$, and let $v_i=(a_{i1},\ldots,a_{ik})$, $1 \leq i \leq s$, be the given vectors. Consider the $k$ polynomials on $s$ variables
\[
f_j(x_1,\ldots,x_s) := \sum_i a_{ij} x_i^{p-1}.
\]
These polynomials fulfil the hypothesis of the Chevalley-Warning Theorem, for the sum of their degrees is $k(p-1)$, which is less than the number $s=1+k(p-1)$ of variables. Note that the system $f_1=\cdots=f_k=0$ has the trivial solution $x_1=\cdots=x_s=0$. By the Chevalley-Warning theorem, it has another one, say $(\alpha_1,\ldots,\alpha_s)$. Now, set $I : =\{i \, | \, \alpha_i \neq 0\}$. This set is non-empty and, by Fermat's Little Theorem, we have
\[
\sum_{i \in I} v_i = (0,\ldots,0),
\]
as desired. The proof is complete.

Is it clear now?

Yup! :) Thanks! For a moment there, I was getting really frustrated :D.

what does "comprise" mean? actually, i can't understand the whole problem and i don't wanna read the solution before working on it.  :blush:  :blush:  :blush:

Just a coment. Take the same problem but instead of zero sum subset put a subset with sum zero and with p elemnts. In other words.. find the maximal number of vectors of Z^k mod p.. such that there is no p subset with sum zero.
   For k=1 this is Erdos-... problems and the answer is 2p-2
    for k=2 this is Kemnitz conjecture wich was proved last year by a German student who went to the imo... the correct answer is 4p-4
   for k>2  very little is know..... in fact i think that its proved that this number is linear in p, but the bounds know are probably far from the truth.
    So anyone intrested in this problem and related ones who wants to share problems and ideas write me to Charlydif@hotmail.com.

[quote="vess"]...2004/6 are unsuitable for an IMO event... [/quote]

Hmm. I see you know the IMO questions of 2004 already...  :D

Sorry, I intended to write 2003/6.  :D  :D  :D

Yes, Carlos, it is proved by Alon and Dubiner in 1995 (Combinatorica, vol. 15, 301--309) that, for each fixed dimension $ k$, the bound grows linearly in $ p$. I have personally used this in showing a result about what is known as "Davenport constant" of finite abelian groups. And the (completion of the) solutions for $ k \equal{} 2$ belongs to Christian Reiher, now an undergraduate in Germany, who has managed to obtain 5 IMO medals (including 4 gold) and beat Barton's record.

Hey, as long as we're here, why not say what Davenport's constant is?  :lol:  For any finite abelian $ G$ (we have a similar thing for non-abelian groups as well, but I won't delve into details here) denote the least integer $ s$ such that from any $ s$ (not necessarily pairwise distinct) elements of $ G$ one may choose some whose product is the identity of $ G$. This is known as the "Davenport constant" of $ G$ and denoted $ D(G)$. As you've probably already noticed while reading this, the initial shortlisted problem is equivalent to calculating the Davenport constant for the elementary abelian group $ \mathbb{Z}_p^{p \minus{} 1}$ (direct sum of $ p \minus{} 1$ copies of the cyclic group of order $ p$.)

It is well-known that any finite abelian $ G$ may be uniquely written as $ G \equal{} \mathbb{Z}_{n_1} \oplus \cdots \mathbb{Z}_{n_r}$, where $ n_r > 1$ and $ n_1 | n_2 | \cdots | n_r$ (the $ n_i$ are the so-called "invariant factors" of $ G$.) Define the quantity
\[ d(G) \equal{} 1 \plus{} \sum_{1\leq i \leq r} (n_i \minus{} 1).
\]
Then, the theorem I stated and proved in the above post (Olson's theorem) is that $ D(G) \equal{} d(G)$ in the case when $ G$ is a $ p$-group (that is, $ |G|$ is a power of a prime.)
Obviously, $ D(G) \geq d(G)$ always, and there was a conjecture (by Olson, 1969) that $ D(G) \equal{} d(G)$ holds with equality for all groups, but this was proven false by many researchers. By using  the Alon-Dubiner estimates mentioned above, though, I have shown that, for any abelian $ G$ of rank $ r$ we have
\[ h(G): \equal{} D(G)/d(G) < (500r \ln r)^r.
\]
Thus, $ h(G)$, although  strictly $ > 1$ for many groups, is bounded within the class of groups of fixed rank.

--Vesselin


Let $ a^3 \plus{} b^3 \plus{} c^3 \equal{} 3,a,b,c\ge 0$
Prove that
$ \sqrt [3] {\frac {2a^3}{a^2 \plus{} b^2}} \plus{} \sqrt [3] {\frac {2b^3}{b^2 \plus{} c^2}} \plus{} \sqrt [3] {\frac {2c^3}{c^2 \plus{} a^2}}\le 3$
It is very easy,but I think the stronger one is also true
$ \sqrt [3] {\frac {2a^3}{a^2 \plus{} b^2}} \plus{} \sqrt [3] {\frac {2b^3}{b^2 \plus{} c^2}} \plus{} \sqrt [3] {\frac {2c^3}{c^2 \plus{} a^2}}\le \sqrt [6]{3^5(ab \plus{} bc \plus{} ca)}$
Who can help me? :lol:

For the second one, try $ a\equal{}b\equal{}0, c\equal{}3^{\frac{1}{3}}$.
For the first one, I don't have a complete proof. My approach is very very complicated and the result will hopefully follow from schur & muirhead, but I won't post it until I am done.
I think there is a much much better approach.

[quote="Sunkern_sunflora"]For the second one, try $ a \equal{} b \equal{} 0, c \equal{} 3^{\frac {1}{3}}$.[/quote]
But then the first term is indeterminate?

O.K. Let $ a\equal{}0, b \rightarrow 0, c \rightarrow 3^{\frac{1}{3}}$. Is it O.K. now?
If not, please explain me why?

[quote="Sunkern_sunflora"]O.K. Let $ a \equal{} 0, b \rightarrow 0, c \rightarrow 3^{\frac {1}{3}}$. Is it O.K. now?[/quote]
Perfectly OK. :wink:

[quote="Sunkern_sunflora"]For the second one, try $ a \equal{} b \equal{} 0, c \equal{} 3^{\frac {1}{3}}$.
For the first one, I don't have a complete proof. My approach is very very complicated and the result will hopefully follow from schur & muirhead, but I won't post it until I am done.
I think there is a much much better approach.[/quote]
OK thanks,If $ a,b,c>0$,I think it will be true but the first one is true and quite nice
How about $ a\plus{}b\plus{}c\plus{}d\equal{}1,a,b,c,d\ge 0$
Prove that $ \sum \sqrt[3] {\frac {3a^3}{a^2\plus{}b^2\plus{}c^2}}\le 4$

[quote="Allnames"][quote="Sunkern_sunflora"]For the second one, try $ a \equal{} b \equal{} 0, c \equal{} 3^{\frac {1}{3}}$.
For the first one, I don't have a complete proof. My approach is very very complicated and the result will hopefully follow from schur & muirhead, but I won't post it until I am done.
I think there is a much much better approach.[/quote]
OK thanks,If $ a,b,c > 0$,I think it will be true but the first one is true and quite nice
How about $ a \plus{} b \plus{} c \plus{} d \equal{} 1,a,b,c,d\ge 0$
Prove that $ \sum \sqrt [3] {\frac {3a^3}{a^2 \plus{} b^2 \plus{} c^2}}\le 4$[/quote]
It must be $ a \plus{} b \plus{} c \plus{} d \equal{} 4$. And both it and the original Inequality can be proved with Cauchy Schwarz Inequality. :)
P/s: the original still holds for $ a\plus{}b\plus{}c\equal{}3$. ;)

[quote="can_hang2007"][quote="Allnames"][quote="Sunkern_sunflora"]For the second one, try $ a \equal{} b \equal{} 0, c \equal{} 3^{\frac {1}{3}}$.
For the first one, I don't have a complete proof. My approach is very very complicated and the result will hopefully follow from schur & muirhead, but I won't post it until I am done.
I think there is a much much better approach.[/quote]
OK thanks,If $ a,b,c > 0$,I think it will be true but the first one is true and quite nice
How about $ a \plus{} b \plus{} c \plus{} d \equal{} 1,a,b,c,d\ge 0$
Prove that $ \sum \sqrt [3] {\frac {3a^3}{a^2 \plus{} b^2 \plus{} c^2}}\le 4$[/quote]
It must be $ a \plus{} b \plus{} c \plus{} d \equal{} 4$. And both it and the original Inequality can be proved with Cauchy Schwarz Inequality. :)
P/s: the original still holds for $ a \plus{} b \plus{} c \equal{} 3$. ;)[/quote]
Yes,Can hang,my proof is even only used $ a\plus{}b\plus{}c\le 3$
Thank for your hint,any full proof

[quote="Allnames"]
OK thanks,If $ a,b,c > 0$,I think it will be true but the first one is true and quite nice
How about $ a \plus{} b \plus{} c \plus{} d \equal{} 1,a,b,c,d\ge 0$
Prove that $ \sum \sqrt [3] {\frac {3a^3}{a^2 \plus{} b^2 \plus{} c^2}}\le 4$[/quote]

I think it 's similar to but it is harder and more compound than first problem

[quote="Allnames"]It is very easy,but I think the stronger one is also true
$ \sqrt [3] {\frac {2a^3}{a^2 \plus{} b^2}} \plus{} \sqrt [3] {\frac {2b^3}{b^2 \plus{} c^2}} \plus{} \sqrt [3] {\frac {2c^3}{c^2 \plus{} a^2}}\le \sqrt [6]{3^5(ab \plus{} bc \plus{} ca)}$[/quote]

It 's wrong. $ Try a\equal{}0,2 ; b\equal{}0,1 ; c\equal{}2,991$


Let $A=\{1,2,\ldots,n\}$. Find the number of unordered triples $(X,Y,Z)$ that satisfy $X\bigcup Y \bigcup Z=A$

A similar problem, http://www.artofproblemsolving.com/Forum/viewtopic.php?t=30360 (point b), appeared in a romanian shortlist a few years ago. I think without those nasty restrictions, the problem should be easier.

The problem is eqiuvalent to find the number of ways to color the elements of the given set with three colors (a point can be colored with more than one color) such that no point remains uncolored. For each point we can choose the color in $2^3-1=7$ ways (a non empty subset of the set of three colors). Hence the desired number is $7^n$ .

No if he would assume that an element appears in exactly one, then there would be $3$ choices each.
The $7$ comes from all $8$ possibilities to color them (with at least one color) minus the colourless one.

[quote="ZetaX"]That doesn't really make the problem harder, just observe additionally that we counted every triple with all sets different $6$ times, and use the same procedure for the case where exactly two are equal (three equal ones is trivial).[/quote]
Yes, I agree.I think the exact answer is $\frac{5*3^n+2+7^n}{6}$


inequalities
algebra
polynomial
inequalities proposed

Very nice one  :lol: but a nice solution perhaps hardly occurs  :( I also wait

I think we don't need an assumption $a,b,c>0$. According to my tests, the inequality holds for $a<0$ too. This means that one can write the expression as a positive linear combination of square terms.

[quote="Parkdoosung"]

I proved it by using computer.
[/quote]

What do you use for this ?Is there such a program ?

[quote="Svejk"]
What do you use for this ?Is there such a program ?[/quote]
No. I meant I used dirty methods like expanding with a computer program.

Can we replace $50$ by any $n\in\mathbb{N}?$  :maybe:

nope... since you have that
$\sum_{cyc}a^{2}b-\sum_{cyc}ab^{2}=(b-a)(c-b)(a-c)$ so the initial inequality is equivalent to
$\sum_{cyc}a^{6}-\sum_{cyc}a^{3}b^{2}c\geq 50abc(a-c)(c-b)(b-a)$
the question is what is the greatest real constant with which we can replace $50$...

[quote="Parkdoosung"]Let $a,b,c>0$, then prove that
$a^{6}+b^{6}+c^{6}+50abc(ab^{2}+bc^{2}+ca^{2})\geq 51abc(a^{2}b+b^{2}c+c^{2}a).$

I proved it by using computer, but I could not find a nice solution.
Is there a nice solution?[/quote]
Could you show us your non-elegant proof? I'm unable to solve that inequality in any method. I tried to expand $(a+b+c)^{6}$ but found nothing useful.

[quote="silouan"]I have not tried yet but I think that the subtitution $b=a+x$ , $c=a+y$ makes the work .[/quote]
I have checked  it, silouan. It's very hard to prove. Maybe by computer...

Could this be solved by Muirhead's inequality?

Let $ \frac {b}{a} \equal{} x,\ \frac {c}{a} \equal{} y$, W.L.O.G. $ a \equal{} min\{a,\ b,\ c\}$, we can rewrite the inequality as

$ 1 \plus{} x^6 \plus{} y^6 \plus{} 50xy(x^2 \plus{} xy^2 \plus{} y)\geq 51xy(x \plus{} x^2y \plus{} y^2)$ for $ x\geq 1,\ y\geq 1.$

[quote="puuhikki"]I think we don't need an assumption $ a,b,c > 0$. According to my tests, the inequality holds for $ a < 0$ too.[/quote]
We need that assumption. $ a\equal{}\minus{}2,b\equal{}3,c\equal{}4$.

[quote="Parkdoosung"]No. I meant I used dirty methods like expanding with a computer program.[/quote]
Um. What expression did you expand? I didn't found any useful identity.

One more. For the collection.
Let $ a,$ $ b$ and $ c$ are non-negative numbers such that $ ab\plus{}ac\plus{}bc\equal{}3.$ Prove that
\[ a^3\plus{}b^3\plus{}c^3\plus{}81(a^2b\plus{}b^2c\plus{}c^2a)\geq246\]

[quote="goc"]the question is what is the greatest real constant with which we can replace $ 50$...[/quote]
Could the constant probably be 124?? :maybe:

I guess this is an open question or why Park Doo Sung won't give his solution. I found an idea from NRICH but I'm unable to complete the proof.
[quote="David Loeffler"]
I've just done some numerical experimentation, and the verdict is that it does apparently hold but only by the tiniest of margins. Let $ r(x,y,z) \equal{} x^6 \plus{} y^6 \plus{} z^6, s(x,y,z) \equal{} xyz(xy^2 \plus{} \ldots )$, and $ t(x,y,z) \equal{} xyz(x^2y \plus{} \ldots )$.

Then the statement we're trying to prove is equivalent to saying that $ (r \minus{} s)/(t \minus{} s)$ is always at least $ 51$, for any positive real numbers $ x, y, z$. Applying a standard steepest-descent algorithm to try and find the minimum point (after taking $ x \equal{} 1$ and $ y,z \leq 1$ WLOG, which we can do by homogeneity and cyclic symmetry), I found that the minimum was apparently $ 52.9249917$, attained at $ (1, 0.7148798, 0.3305294)$. So it is apparently true, but only by the tiniest of margins.

In theory it should be possible to convert this into a rigorous proof, as if we fix $ x \equal{} 1$ and consider $ (r \minus{} s)/(t \minus{} s)$ as a function of $ y,z$ alone, then the locus of vanishing of its two derivatives should be a finite list of pairs of points whose coordinates are algebraic numbers; and the polynomials satisfied by these coordinates can be calculated using the method of Groebner bases.

It turns out, unfortunately, that the minimum attained by this function is a root of a polynomial over $ \mathbb{Q}$ of degree $ 48$, with truly enormous coefficients, and proving anything rigorously about whether or not it such a function has roots in certain intervals isn't going to be a lot of fun. :-) On the other hand this method does allow me to compute the minimum value to a high degree of accuracy quickly: it's $ 52.92499175929436524677274933089682409825702453021881690188234832654394981441595653642949265345933089$.

David[/quote]

I think you are correct but could you post more details? I don't see why those polynomials are irreducible.


A circle centered at [i]O[/i] has radius 1 and contains the point [i]A[/i]. Segment [i]AB[/i] is tangent to the circle at [i]A[/i] and  :ang: [i]AOB[/i]= :theta: . If point [i]C[/i] lies on [i]OA[/i] and [i]BC[/i] bisects :ang: [i]ABO[/i], then [i]OC[/i]=

(A)[hide]$\sec^{2}-\tan\theta$[/hide]
(B)[hide]$\frac{1}{2}$[/hide]
(C)[hide]$\frac{\cos^{2}\theta}{1+\sin\theta}$[/hide]
(D)[hide]$\frac{1}{1+\sin\theta}$[/hide]
(E)[hide]$\frac{\sin\theta}{\cos^{2}\theta}$[/hide]

If you've has basic trig, this should be as easy as 3.14159... ;)

I'd be very suprised if most middle schoolers know trig.

The school system I'm enrolled in teaches trig in the first year of high school at the earliest.

[quote="ln(dx/dy)"]I'm only in 7th grade and I know trig. :P[/quote]

I do too, but you rarely even see trig in getting started.

Yea, I'm in 7th grade and know trig. But that doesn't mean I'm not moving this.  :P  ;)

I'm going to move this.

I know I KNOW TRIG ALSO but guys, please keep this in Getting Started.

I know all you guys are very smart for your age but that doesn't mean you guys can just post any questions that aren't getting started.

[quote]I do too, but you rarely even see trig in getting started.[/quote]

It's not rare ----> It's not allowed.

It's obviously
[hide="answer"]
D :P .

Look for a similarity involved by the bisector. That should get you started.
[/hide]
Why it's not 1/2:

Draw a diagram where  :theta: is really small.

[quote="jli"]im in 6th grade and i know trig[/quote]
um, thats great, but most people dont. That wasnt the point of silverfalcon's post (for example, everyone who didnt know trig wouldnt post)


Let $ A$ is nxn real symmetric matrix and positive semidefinite , $ B \in M_n{(C)}$ such that :
    $ AB \plus{} BA \equal{} 4018A \minus{} B \plus{} 2009I_n$
$ I_n$ is identity matrix .
Prove that : $ B \equal{} 2009I_n$
 :spider:

[b]Lemma 1:[/b] Each diagonal entry of a positive definite matrix is strictly positive. That is, if $ U$ is real, symmetric, and positive definite, then $ u_{ii} > 0$ for each $ i.$

[b]Lemma 2:[/b] If $ U$ and $ V$ are real symmetric matrices with $ U$ positive definite and $ UV \plus{} VU \equal{} 0,$ then $ V \equal{} 0.$

[b]Proof of the problem:[/b] Rewrite the identity as

$ AB \plus{} BA \minus{} 4018A \plus{} B \minus{} 2009I \equal{} 0$

$ \left(AB \minus{} 2009A \plus{} \frac12B \minus{} \frac {2009}2I\right) \plus{} \left(BA \minus{} 2009A \plus{} \frac12B \minus{} \frac {2009}2I\right) \equal{} 0$

$ \left(A \plus{} \frac12I\right)(B \minus{} 2009I) \plus{} (B \minus{} 2009I)\left(A \plus{} \frac12I\right) \equal{} 0.$

Now let $ U \equal{} A \plus{} \frac12I$ and $ V \equal{} B \minus{} 2009I.$ The hypothesis was that $ A$ was positive semidefinite, but once we add the positive multiple of the identity, we have that $ U$ is positive definite. Hence the hypotheses of Lemma 2 are met and we have that $ V \equal{} 0,$ which means that $ B \equal{} 2009I.$

[b]Proof of Lemma 2:[/b] Since $ V$ is real symmetric, it is orthogonally diagonalizable. On the other hand, any matrix that is orthogonally similar to the positive definite $ U$ would also be symmetric and positive definite. Hence, WLOG we may assume that $ V$ is diagonal.

Block structure $ V$ as $ \begin{pmatrix}\lambda & 0 \\
0 & V'\end{pmatrix}$ and $ U$ as $ \begin{pmatrix}a & * \\
* & *\end{pmatrix}.$

Then $ UV \plus{} VU \equal{} \begin{pmatrix}2\lambda a & * \\
* & *\end{pmatrix} \equal{} \begin{pmatrix}0 & 0 \\
0 & 0\end{pmatrix}.$

Hence $ 2\lambda a \equal{} 0.$ But by Lemma 1, $ a\ne 0,$ so $ \lambda \equal{} 0.$ Since we could have rearranged the diagonalization to make $ \lambda$ any of the eigenvalues of $ V,$ we conclude that all of the eigenvalues of $ V$ are zero and thus $ V \equal{} 0.$

[b]Proof of Lemma 1:[/b] Just let $ x \equal{} e_i,$ the $ i$th standard basis vector. Then $ x^TUx \equal{} u_{ii}$ so we from the positivity of $ U$ we see that $ u_{ii} > 0.$

[quote][b]Lemma 2:[/b] If $ U$ and $ V$ are real symmetric matrices with $ U$ positive definite and $ UV \plus{} VU \equal{} 0,$ then $ V \equal{} 0.$[/quote]
 A  diferent solution : from $ UV \plus{} VU \equal{} 0$ we have $ U^2V \equal{} VU^2$ (1)
By $ U \in S^{ \plus{} \plus{} }_n(R)$ the exist $ T \in O_n(R), D \equal{} diag(\lambda_1,...,\lambda_n) \in D_n(R)$ Such that :
$ A \equal{} TDT^{ \minus{} 1}$
 By $ \lambda_1,...,\lambda_n \in R^{ \plus{} } \forall (i,j) \in${1,2,..,n} {$ \lambda^2_i \equal{} \lambda^2_j$ then $ \lambda_i \equal{} \lambda_j$} for all $ 1 \leq i,j \leq n$
Show that the exist $ P \in R[X]$ such that  $ \forall i \in${1,2,...,n} $ P(\lambda^2_i) \equal{} \lambda_i$ (by interpolation largaranger  for $ \lambda^2_i distinct$ ) imples $ P(U^2) \equal{} U$ (2)
 from (1) imples $ P(U^2)V \equal{} VP(U^2)$ and (2) $ UV \equal{} VU$ then $ UV \equal{} VU \equal{} 0$ from here $ V \equal{} 0$(by $ U > 0, U \in GLn(R)$)
I think that Shown need $ V \in M_n(C)$ !
Sory if i wrong !!

[quote="QuyBac"] from $ UV \plus{} VU \equal{} 0$ we have $ U^2V \equal{} VU^2$ [/quote]
Why? I don't immediately see the argument for this.

Edit: Never mind, I do see. $ UV\equal{}\minus{}VU$ so

$ U^2V\equal{}U(UV)\equal{}\minus{}U(VU)\equal{}\minus{}(UV)U\equal{}(VU)U\equal{}VU^2.$

[quote="QuyBac"]I think that Shown need $ V \in M_n(C)$ ![/quote]
Agreed. Here's my last version of the proof.

[b]Lemma:[/b] Suppose $ U,V\in M_n(\mathbb{C}),$ $ U$ is positive definite (which I would take to include being Hermitian), and $ UV \plus{} VU \equal{} 0.$ Then $ V \equal{} 0.$

Since $ U$ is positive definite, it can be diagonalized. WLOG assume we can write

$ U \equal{} \begin{pmatrix}\lambda & 0 \\
0 & U'\end{pmatrix}$ and $ V \equal{} \begin{pmatrix}a & y^T \\
x & V'\end{pmatrix}.$

Then $ UV \plus{} VU \equal{} \begin{pmatrix}2\lambda a & \lambda y^T \plus{} y^TU' \\
U'x \plus{} \lambda x & U'V' \plus{} V'U'\end{pmatrix} \equal{} \begin{pmatrix}0 & 0 \\
0 & 0\end{pmatrix}.$

We know that $ \lambda > 0$ so we have $ a \equal{} 0.$ Furthermore, we have both $ U'x \equal{} \minus{} \lambda x$ and $ U'y \equal{} \minus{} \lambda y.$ But $ U'$ must be positive definite and cannot have $ \minus{} \lambda$ as an eigenvalue. Hence we must have both $ x \equal{} 0$ and $ y \equal{} 0.$ We now have

$ V \equal{} \begin{pmatrix}0 & 0 \\
0 & V'\end{pmatrix}$ and $ U'V' \plus{} V'U' \equal{} 0.$

We continue this process inductively with $ U'$ and $ V',$ successfully zeroing out first columns and first rows of what's left of $ V$ until there's nothing left. We conclude that $ V \equal{} 0.$


Hey,

I'm about to purchase the Putnam Competition Three Volume Set and wanted to know if anyone has the first volume: [i]The William Lowell Putnam Mathematical Competition Problems & Solutions: 1938-1964[/i]. I wanted to ask, since I was not sure if is as well written and thorough in its' solutions as the other two volumes.
So any opinions on this volume?

Additionally, how useful have you found these three volumes to your own preparation for the Putnam?

Thanks,

-APSStudent

I own the first and third volumes.  They are both great.  They both contain well-written, comprehensive solutions.  Many problems are given more than one solution.

I don't have the second volume, so I can't comment on it.


geometry
incenter
circumcircle
inradius
inequalities
geometry proposed

The mittenpunkt of a $ \triangle ABC$ is the symmedian point of the excentral triangle (triangle of three excenters), let $ S$ be symmedian point of $ ABC$ and $ I$ is incenter of $ ABC$ prove that
\[ MI^2 \equal{} \frac {4R((R \plus{} r)p^2\minus{}r(4R \plus{} r)^2)}{(4R \plus{} r)^2}
\]

\[ MS^2 \equal{} \frac {4p^4R((R \plus{} r)p^2)\minus{}r(4R \plus{} r)^2}{(4R \plus{} r)^2(p^2 \minus{} 4Rr \minus{} r^2)^2}
\]
$ R,r,p$ is circumradius, inradius and semiperimeter.

So $ MI^2\ge 0$ or $ ML^2\ge 0$ we get $ p^2\ge\frac {r(4R \plus{} r)^2}{R \plus{} r}$

Many thank to Virgil Nicula, he suggest me to propose this problem :) .

p/s Sorry much, I edited because I got wrong result, thank to Virgil Nicula :blush: !

[color=purple] A very nice problem,I have a $ Rrp$ solution for the inequality :$ p^2\ge\frac {r(4R \plus{} r)^2}{R \plus{} r}$ and I am really amazed when I know Mittenpunkt point.
  A question of mine : Why do you know $ M$ call $ Mittenpunk$ point ? I have never seen it before.Please show me more features of this point:).Thank you very much !
At last sorry because of my spam post !
Best regard,
Evarist.[/color]

You can see [url=http://mathworld.wolfram.com/Mittenpunkt.html]here[/url] for Mittenpunkt point!


$ C_{1}$ and $ C_{2}$ be two externally tangent circles with diameter $ \left[AB\right]$ and $ \left[BC\right]$, with center $ D$ and $ E$, respectively. Let $ F$ be the intersection point of tangent line from A to $ C_{2}$ and tangent line from $ C$ to $ C_{1}$ (both tangents line on the same side of $ AC$). If $ \left|DB\right|\equal{}\left|BE\right|\equal{}\sqrt{2}$, find the area of triangle $ AFC$.

$\textbf{(A)}\  \frac{7\sqrt{3} }{2} \qquad\textbf{(B)}\  \frac{9\sqrt{2} }{2} \qquad\textbf{(C)}\  4\sqrt{2} \qquad\textbf{(D)}\  2\sqrt{3} \qquad\textbf{(E)}\  2\sqrt{2}$

[hide="Generalized solution"]Let the given tangents be $ AM_2$ and $ CM_1$, and let $ G$ be the foot of the perpendicular from $ F$ to $ AC$. If the radius of $ (D)$ is $ r$ and radius of $ (E)$ is $ R$, then

$ {GA\over FG}\equal{}{AM_2\over M_2E}\equal{}\frac{\sqrt{(2r\plus{}R)^2\minus{}R^2}}{R}\equal{}{2\sqrt{r^2\plus{}Rr}\over R}$

$ {GC\over FG}\equal{}{CM_1\over M_2D}\equal{}\frac{\sqrt{(2R\plus{}r)^2\minus{}r^2}}{r}\equal{}{2\sqrt{R^2\plus{}Rr}\over r}$

With $ GA\plus{}GC\equal{}AC\equal{}2(R\plus{}r)$, by adding the previous equations up we get

$ {2(R\plus{}r)\over FG}\equal{}2\sqrt{R\plus{}r}{{R\sqrt{R}\plus{}r\sqrt{r}}\over Rr}\iff FG\equal{}{Rr\sqrt{R\plus{}r}\over{R\sqrt{R}\plus{}r\sqrt{r}}}$

Now $ [ACF]\equal{}{AC\over 2}\cdot FG\equal{}(R\plus{}r)FG\equal{}{Rr(R\plus{}r)^{3/2}\over{R^{3/2}\plus{}r^{3/2}}}$

For $ R\equal{}r\equal{}\sqrt{2}$ we get

$ [ACF]\equal{}{2\cdot(2\sqrt{2})^{3/2}\over 2\cdot (\sqrt{2})^{3/2}}\equal{}2^{3/2}\equal{}2\sqrt{2}$, so the answer is $ E$.[/hide]


calculus
integration
factorial
trigonometry
calculus computations

[quote="oldman"][quote="siuhochung"]I thought of this problem recently when I was on the train.... Today I thought of it again but I still could not figure out the problem of the following "proof".
Let us consider the integral $T=\int {\frac{1}{{1 + x^2 }}dx}$, with $|x| < 1$.
On one hand, it's known that $T= tan^{-1} (x)$
On the other hand, $T = \int{1-x^2+x^4-x^6+.... dx} = x-\frac{x^3}{3}+\frac{x^5}{5}-\frac{x^7}{7}+...+C=sin x + C$
So does that mean if $|x|<1$, then $arctan(x)-sin(x)$ is a constant???
I think it must be false, but I simply can't see the fallacy of the proof above.[/quote]

I think you forgot the factorial sign :D
$\sin x=x-\frac{x^3}{3!}+\frac{x^5}{5!}+\cdots$[/quote]

oh my god.......... how can i be so stupid and ............. really.............  :blush:  :blush:


In the board there are a positive integer.A and B play acording the following rules:A replace $n$ by either $n/2$ or $n/4$(if possible) or $3n$,B replace $n$ by either $n-1$( if possible) or $n+1$.A  wins if $3$ is written in the board(no matter who writes).Show that:A has a winning stradegy!

[hide="1) We prove that player A can make numbers smaller in a couple of steps by dividing by the largest number possible."]
Case 1:
If A gets a number divisible by 2,  she can make it smaller easily.

Case 2:
If  A gets a number $x$ which is odd, and B makes it divisible by four in the next step:

\[ x \overset{A}{\to} 3x \overset{B}{\to} 3x\pm 1 \overset{A}{\to} \frac{3x \pm 1} 4 \overset{B}{\to} \frac{3x \pm 1} 4 \pm 1  \]

and $\frac{3x + 1} 4 + 1 < x$ for $x > 5$.

Case 3:
If  A gets a number $x$ which is odd, and B makes it divisible by two but not four in the next step:

\[ x \overset{A}{\to} 3x \overset{B}{\to} 3x \pm 1 \overset{A}{\to} \frac{3x \pm 1} 2 \overset{B}{\to} \frac{3x\pm1} 2 \pm 1 \overset{A}{\to} \frac{\frac{3x \pm 1} 2 \pm 1} 2 \overset{B}{\to} \frac{\frac{3x \pm 1} 2 \pm 1} 2\pm1  \]

and $\frac{\frac{3x + 1} 2 + 1} 2 +1< x$ for $x> 7$. [/hide]

So A can make sure that she gets one of the numbers $\{1,2,3,4,5,6\}$.

[hide="2)  The easy cases B1,B3,B4,B6 "]

If A gets 3, she has won.
If she gets 1, she triples it and has won.
If she gets 6, she halves it and has won.
If she gets 4, she halves it, then gets 1 or 3 and wins as above.
[/hide]

[hide="3) The icky cases B2 and B5"]

B8 is a win for A: A plays A2 giving either B3 or B1 and plays A3 in the second case
A7 is a win for A:  it gives either B6 or B8
A5 is a win for A:  it gives either B4 or B6
B14 is a win for A: A plays A7
B12 is a win for A: A plays 3
B10 is a win for A: A plays A5
A11 and A13 are wins for A: they give B10, B12 or B14
B20 is a win for A: A plays A5
B22 is a win for A: A plays A11
B26 is a win for A: A plays A13
B28 is a win for A: A plays A7
A21 and A27 are wins for A as they lead to B20,22,26 or 28
B7 and B9 are wins for A as A can play A21 and A27
A8 is a win for A as it leads to B7 or B9
B16 is a win for A as A can play A8
A15 is a win for A as it leads to B14 or B16
[b]B5 is a win for A, A plays A15
B2 is a win for A, A plays A6 which leads to B5 or B7
[/b]
[/hide]


linear algebra
matrix
algebra
polynomial
system of equations
linear algebra unsolved

As I am new to the subhect, I am having a problems with the following question...

"For which values of λ does the system of equations have a single solution,
For which values of λ does it have more than a single solution?"
2y - λz = 0
2x - λy + z = 0
-λx + y + 3z = 0

Using a matrix, i can get to -
(2    -λ    1
 0     2     -λ
-2λ   2     6)

But what next?

Thanks!

This is an eigenvalue question- if that matrix is invertible, the system has exactly one solution (zero). If it's not invertible, there is a nontrivial space of solutions.

A notational clarification: you're best off completely reversing the order from the way it was given. Then your matrix equation will be:

$ \begin{bmatrix}\minus{}\lambda&1&3\\ 2&\minus{}\lambda&1\\ 0&2&\minus{}\lambda\end{bmatrix} \begin{bmatrix} x\\ y\\ z\end{bmatrix}\equal{}\begin{bmatrix}0\\ 0\\ 0\end{bmatrix}$

Of course it's an eigenvalue equation, but you can do this problem even if you haven't gotten to that part of the course yet. This is a homogeneous system, and a square homogeneous system has non-unique solution precisely when the determinant of the square matrix is zero. Go ahead and expand out that determinant - you should get a cubic polynomial in $ \lambda.$

I should mention that I get a cubic equation, $ \lambda^3\minus{}4\lambda\minus{}12\equal{}0,$ that has no rational roots and only one real real root - so your answers won't be pretty. (Unless you miscopied the question somewhere.)


AMC AIME USA(J)MO USAMO USAMTS MIT college

How do you pronounce various math abbreviations?  Which do you say the letters, and which a word?  For example, for the AMC, I say A-M-C, but for the AIME, I say Aim-e.

For me-
USAMO:you-sah-moh
USAMTS:you-sampts
AOPS:A-O-P-S
AM-GM:ahm-gim

That's all I can think of quickly.

Capitalized letters represent the standard pronunciation of the name of the letter in English.

AoPS -- A - ops
USAMO -- U - sah - mo
USAMTS -- U - sah - mits
AIME -- A - mee
AM-GM -- A M G M

and, for semi-oldtimers

AHSME -- ash - mee
AJHSME -- aj - hiss - mee

I never noticed the S in AJHSME.  I always thought it was AJHME.  I guess I would pronounce it like AHSME with a J.

AOPS - A-ops
USAMO - U-sah-mo
USAMTS - U-sah-mats
AIME - A-mee
AM-GM - A-M-G-M
AHSME - ash-mee

I just say the letters for all of them.  I never thought of saying any of them like actual words.

I guess A+MATH and I will practice saying "A-ops" around the house now. That'll be a big change of habit for us, but will help prepare us to meet the AoPS staff someday.

[quote="theone853"]We have yet to hear how the creators of AOPS talk about their site...[/quote]

Umm...Mr. Crawford responded [url=http://artofproblemsolving.com/Forum/viewtopic.php?t=24257]here[/url]  :wacko:

AMC: spelled
AIME: ay-mee (Like the name Amy)
USAMO: spelled
USAMTS: spelled
AHSIMC: aah-zimk (or, just call it the iTest)

AMC: ay-em-cee
AIME: ay-mee
USAMO: you-sah-mo
USAMTS: you-sam-tz
AHSME: ash-mee
WLOG: wuh-log maybe? :)
AoPS: ay-ops

i never thought of saying them like words...i just say the letters and sound smart and no one at my school knows what i'm talking about :)

[quote="JBL"] I did once have someone ask me what the omega-log function the teacher kept writing on the board meant, though.  $\omega\log$.[/quote]

I suppose it must mean the natural logarithm of an angular velocity :D

[quote="JBL"]WLOG = W - log.  (That is, the name of the letter W, followed by the word for a piece of a felled tree.)  I did once have someone ask me what the omega-log function the teacher kept writing on the board meant, though.  $\omega\log$.[/quote]

Hmm.  I just realized that that is one I always say the whole thing for: "without a loss of generality."  I never say w-log or w-l-o-g.

The abbreviation I most enjoy abusing is HMMT.  Say it like a grunt.

I usually spell out AMC, AoPS, AHSIMC, and AM-GM, but I have pronunications for some words.  AIME is like Amy; USAMO is 'oo-sah-mo', and USAMTS is 'you-sampts'.

For IMO, it doesn't matter whether you say I-M-O or i-mow cuz if u say it fast, u always come up wit the latter.

or e-mow idk

to those who are mad at me for reviving a 15 year old thread: hey, this still applies ok? i don't wanna look like an idiot saying e-mow when everybody says i-mow


Triangle ABC has vertices $ A(0, 0)$, $ B(0, 3)$ and $ C(5, 0)$. A point $ P$ inside the triangle is $ \sqrt{10}$ units from point $ A$ and $ \sqrt{13}$ units from point $ B$. How many units is $ P$ from point $ C$? Express your answer in simplest radical form.

ok

we first draw a diagram (i cant post one)

P is $ \sqrt{10}$ units away from A

the only possible integer way you could do that is legs of 3&1

P is $ \sqrt{13}$ units from B

the only possible way that w/ integers is legs of 3&2
since P is in the triangle, it must be 2 away from (0,3) and 3 up, so the coordinates of P are (1,3) (check it, it works)
distance from P to C

draw perpindiculars as legs

the legs are of length 1&2

so PC=$ \sqrt{2^2\plus{}1^2}\equal{}\sqrt{5}$


inequalities
linear algebra
matrix
blogs

Let $ A,B,C$ are $ n$x$ n$ Hermitian matrices and definite positive such that  $ A^2\plus{}B^2\plus{}C^2\equal{}I_n$
Prove that inequality det of matrix :
     $ \det(A\plus{}A^{\minus{}1}\plus{}B\plus{}B^{\minus{}1}\plus{}C\plus{}C^{\minus{}1}) \geq (4\sqrt{3})^n$
Here $ I_n$ is identity matrix

Lemma1) If $ X,Y$ are  are $ n$x$ n$ Hermitian matrices and semi-positive definite such that  $ X \geq Y$ then $ \det(X) \geq \det(Y)$
Lemma2) If $ A,B,C$   are $ n$x$ n$ Hermitian matrices and positive definite Then $ A^{ \minus{} 1} \plus{} B^{ \minus{} 1} \plus{} C^{ \minus{} 1} \geq 9(A \plus{} B \plus{} C)^{ \minus{} 1}$
Lemma3) If $ A,B,C$   are $ n$x$ n$ Hermitian matrices  Then $ (A \plus{} B \plus{} C)^2 \leq 3(A^2 \plus{} B^2 \plus{} C^2)$ you can read proof in blog of me .
lemma4) If $ X,Y$ are  $ n$x$ n$ Hermitian matrices and positive definite and $ Y \geq X$ then $ X^{ \minus{} 1} \geq Y^{ \minus{} 1}$ You can see from proof lemma1)  :maybe:
lemma5) If  $ X,Y$ are  $ n$x$ n$ Hermitian matrices and positive definite such that $ XY \equal{} YX$ such that $ Y^2 \geq X^2$ then $ Y \geq X$ easy
Lemma6) If  $ X,Y,Z,T$ are  $ n$x$ n$ Hermitian matrices such that $ X \geq Y,Z \geq T$ then $ X \plus{} Z \geq Y \plus{} T$ (If $ X \geq Y$ , $ Z > T$ then $ X \plus{} Z > Y \plus{} T$)Very implies (Use many times)
 Proof lemma 1)
1.If $ \det(X) \equal{} 0$ then Implies $ \det(Y) \geq 0$
2. If $ \det(X) > 0$ then the exist $ U \in GL_n(\mathbb{C})$ such that $ X \equal{} U^{*}U,Y \equal{} U^{*}diag(\lambda_1,\lambda_2,..,\lambda_n)U$ (read in Theory matrix)
We have $ Y \minus{} X \equal{} U^{*}diag(\lambda_1 \minus{} 1,\lambda_2 \minus{} 1,...,\lambda_n \minus{} 1)U \geq 0$ Hence $ \lambda_k \geq 1 ,\forall k \in \{1,2,..,n\}$ Implies $ \det(Y) \equal{} |\det(U)|^2\prod_{k \equal{} 1}^{n}{\lambda_k} \geq |\det(U)|^2 \equal{} \det(X)$
  Proof lemma2)
With $ i \equal{} 1,2,3$ put $ M \equal{} (A \plus{} B \plus{} C)^{ \minus{} 1} > 0$ ,$ X \equal{} A^{ \minus{} \frac {1}{2}} \minus{} 3MA^{\frac {1}{2}}$,$ Y \equal{} B^{ \minus{} \frac {1}{2}} \minus{} 3MB^{\frac {1}{2}}$,$ Z \equal{} C^{ \minus{} \frac {1}{2}} \minus{} 3MC^{\frac {1}{2}}$
 and $ X \equal{} A^{ \minus{} \frac {1}{2}} \minus{} 3MA^{\frac {1}{2}}$ then $ X^{*} \equal{} A^{ \minus{} \frac {1}{2}} \minus{} 3A^{\frac {1}{2}}M$
 We have $ XX^{*} \equal{} A^{ \minus{} 1} \minus{} 6M \plus{} 9MAM \geq 0$ the same $ YY^{*} \equal{} B^{ \minus{} 1} \minus{} 6M \plus{} 9MBM \geq 0$ , $ ZZ^{*} \equal{} C^{ \minus{} 1} \minus{} 6M \plus{} 9MCM \geq 0$
 Hence $ XX^{*} \plus{} YY^{*} \plus{} ZZ^{*} \equal{} A^{ \minus{} 1} \plus{} B^{ \minus{} 1} \plus{} C^{ \minus{} 1} \minus{} 18M \plus{} 9M(A \plus{} B \plus{} C)M \geq 0$ or $ A^{ \minus{} 1} \plus{} B^{ \minus{} 1} \plus{} C^{ \minus{} 1} \geq 9(A \plus{} B \plus{} C)^{ \minus{} 1}$
 Have "=" since $ XX^{*} \equal{} YY^{*} \equal{} ZZ^{*} \equal{} 0$ Implies $ X \equal{} Y \equal{} Z \equal{} 0$ eassy see $ A^{ \minus{} 1} \equal{} B^{ \minus{} 1} \equal{} C^{ \minus{} 1} \equal{} 3(A \plus{} B \plus{} C)^{ \minus{} 1}$
 Generall $ A_1^{ \minus{} 1} \plus{} A_2^{ \minus{} 1} \plus{} .. \plus{} A_m^{ \minus{} 1} \geq m^2 (A_1 \plus{} A_2 \plus{} ... \plus{} A_m)^{ \minus{} 1}$ , For $ A_1,A_2,..,A_m$ are Hermitian matrix and positive definite !
Now , Applied we have :
 $ A^{ \minus{} 1} \plus{} B^{ \minus{} 1} \plus{} C^{ \minus{} 1} \geq 9(A \plus{} B \plus{} C)^{ \minus{} 1}$
 $ (A \plus{} B \plus{} C)^{2} \leq 3(A^2 \plus{} B^2 \plus{} C^2) \equal{} 3I_n$ then $ 0 < (A \plus{} B \plus{} C) \leq \sqrt {3}I_n$ ,$ (A \plus{} B \plus{} C)^{ \minus{} 1} \geq \frac {I_n}{\sqrt {3}}$ (Use lemma$ 4,5$)
Then
   $ A^{ \minus{} 1} \plus{} B^{ \minus{} 1} \plus{} C^{ \minus{} 1} \geq 3\sqrt {3}I_n$
   $ A^{ \minus{} 1} \plus{} B^{ \minus{} 1} \plus{} C^{ \minus{} 1} \plus{} 3(A \plus{} B \plus{} C) \equal{} (3A \plus{} A^{ \minus{} 1}) \plus{} (3B \plus{} B^{ \minus{} 1}) \plus{} (3C \plus{} C^{ \minus{} 1}) \geq 6\sqrt {3}I_n$ (Same as Cauchy read in blog of me  :wink: )
 Since we have :
   $ 3(A^{ \minus{} 1} \plus{} B^{ \minus{} 1} \plus{} C^{ \minus{} 1} \plus{} A \plus{} B \plus{} C) \geq 12\sqrt {3}$ Hece $ A \plus{} A^{ \minus{} 1} \plus{} B \plus{} B^{ \minus{} 1} \plus{} C \plus{} C^{ \minus{} 1} \geq 4\sqrt {3}I_n$ (2)
 We use lemma1) We will have  : $ \det(A \plus{} A^{ \minus{} 1} \plus{} B \plus{} B^{ \minus{} 1} \plus{} C \plus{} C^{ \minus{} 1}) \geq (4\sqrt {3})^n$
For (2) With "=" since $ A \equal{} B \equal{} C \equal{} \frac {I_n}{\sqrt {3}}$
 Do you have very interesting ?  :)

[quote="deimos-"]what do you have in mind when you say $ A\geq B$ where $ A$ and $ B$ are matrices?[/quote]
 Here I define in this topic $ A,B$ are Hermitian $ A\geq B$ mean $ A \minus{} B$ are Hermitian and semipositive definite.
 Can $ A,B$ don't must Hermitian but write $ A\geq B$ mean $ A \minus{} B$ are Hermitian and semipositive definite.
You want known many define about it ,You can find a book to read .


invariant
algebra
polynomial
calculus
China
function
arithmetic sequence

Consider a $ 7\times 7$ numbers table $ a_{ij} \equal{} (i^2 \plus{} j)(i \plus{} j^2), 1\le i,j\le 7.$ When we add arbitrarily each term of an arithmetical progression consisting of $ 7$ integers to corresponding to term of certain row (or column) in turn, call it an operation. Determine whether such that each row of numbers table is an arithmetical progression, after a finite number of operations.

I don't understand the problem enough. Can anyone give me an example or something about this "operation".

An unmotivated proof:
[hide]
Consider the expression $ a_{22}\minus{}2a_{23}\plus{}a_{24}\minus{}2a_{32}\plus{}4a_{33}\minus{}2a_{34}\plus{}a_{42}\minus{}2a_{43}\plus{}a_{44}$.  It can be directly verified that

(1) This expression remains invariant when an arithmetic progression is added to any row or column.

(2) If each row of numbers in the table is an arithmetic progression, the expression is 0.

(3) The expression is 4 for the initial table.
[/hide]

What's really going on (and where the above expression came from):
[hide]The polynomial in question has an $ x^2 y^2$ term, so has a nonzero fourth partial derivative $ f_{xxyy}$.  But arithmetic progressions are linear functions, so their second derivative vanishes.  Taking a $ f_{xxyy}$ derivative cancels both the row progressions and the column progressions, so the fourth derivative never changes.  The strange looking invariant above is just the discrete analogue of this derivative.

Alternatively, you can arrive at the expression by realizing that if you want to do an invariant argument, you want something that adds to 0 for arithmetic progressions.  For one-dimensional progressions, you have $ a_{i\minus{}1}\plus{}a_{i\plus{}1}\equal{}2a_i$, and the question is just what the proper 2-dimensional analogue of this is.  [/hide]

I think this one is the simplest among the problems that year!


Square ABCD is inscribed in a circle. Point X is on minor arc AC such that [XDC]=993 and [XAB]=1. Find [XAD]+[XBC]

[quote="JesusFreak197"]What are $XDC$ and $XAB$?[/quote]

Those are triangles...

[b]EDIT:[/b] Hmm... I have no idea how to figure this out, unless the answer is:

[hide]994[/hide]

Which was intuitive. :huh:

If you draw a diagram, placing X WLOG between A and B, you'll see that $[XAD] + [XDC] + [XCB] = [ABCD] + [XAB]$ therefore $[XAD] + [XCB] = [ABCD] - 992$.  Now we just need to find the area of the square.  $[XCD] = \dfrac{s(s + d)}{2}$ and $[XAB] = \dfrac{sd}{2}$, where $d$ is the distance between X and AB.  Solving, we get $s = 992d$, and plugging that back in gets us $s^2 = 1984$, so our answer is $1984-992 = \boxed{992}$

I liked your solution a little better than the book's solution  :D  (no offense authors... your other solutions are fine  :) ).


geometry trigonometry AMC AIME USA(J)MO USAMO calculus

I was wondering what AoPS books would be good for me to read. i tried to view the excerpts and table of contents for certain books, but for some strange reason it is not letting me.

I have the Intro to Algebra, and Volume 1: The Basics, and i have read most of the Intro: Counting and Probability. I took the post test for the Number Theory Intro, and I missed only two of the questions.

I think that the Geometry book would be good for me to read, because I stink at geometry.

Does the geometry book cover trig?

I am also interested in getting the more advanced books;

Volume 2
Intermediate C and P
Intermediate Algebra

Does anybody who knows what I can('t) do, and can they give me any suggestions?

Geometry has a bit of trig near the back, but btw, there's no trig on MathCounts/AMC 8 /AMC 10.

I know, but it is still on AIME, USAMO, and IMO, and i have been attempting to solve some AIME problems.

What do you mean by "a bit of trig" ?

Is that like five pages? Ten pages? ...

WAAAAAAAAAAAAAAAAAY more than 5-10 pages like almost 50. don't worry; the trig'll last you a while. i suggest getting trig by s.l. Loney (look at the Plane trig topic by me in this forum)
and, once you're done with the books don't move on to more advanced stuff until you can get atleast (this is like 100% of the time) a 130 on the AMC 10 or something like that. Because if you do, then you won't go very high on the math competitions or if you just want to learn math, then you'll have a weak understanding of the newer concepts.

I'm sorry Poincare, I do not really understand why you are saying I shouldn't get more advanced books.

How many questions do you have to get right on the AMC 10 to get a 130?

What do you mean by saying I won't go very high on the math competitions?

Why is wanting to learn math not making my understanding of newer concepts stronger?

I am sorry, I might be missing something. Which is most likely, but I still don't understand what u r trying to say.

[quote="pythag011"]I believe he is saying that you should wait before you have a very good understanding of the basics before moving on to advanced stuff.

This is certainly true. Also, the basics tend to be more useful than advanced stuff. Out of the geometry problems I have solved, most of them I used angle chasing, cyclic quads, etc. I've used those on probably 100 problems so far...

I've used inversion on 3 of them, pole-polars on 2 of them, and Brocard's thereom on 2 of them.

However, I'm not that good at geometry, so...

Learning everything up to calculus and being only able to use everything on trivial problems is not as useful as learning only algebra and geometry and being able to solve non-trivial problems about algebra and geometry.

However, I am not sure that getting a 130 on AMC 10 is indicative on whether you understand the topic...[/quote]
i just said the amc score just to make it clear how good you need to be.

But pythag is saying maybe you got 130 on AMC 10, but only got like 1/4 geometry questions rite...

omg, fine! :D
ignore the AMC 10 part![/hide]

Wait!!! Would if, I attempt the more difficult problems, and then I learn something on my own that helps me to solve similar problems later. I think that if I discover something on my own, then I will have a better understanding of it.

Uhh, but if you solve it INCORRECTLY, you'll solve the similar problems incorrectly also...

Basically, do the challenge problems in the AoPS books and take a class if you need.

Alright. So how do I know when I am ready for the AoPS books intented for highschool.

If you wanted to know if you're ready for geometry, go to the classes page, and click intro to geometry, then click "Am I Ready Yet"?  It's for the classes, but you could use it for the books also.  If the am i ready test is super easy, try the Do I Need This?  test.  ANd so on for the other books.

Alright, the geometry pre-test was really easy. The post test was really hard, so i think that that would be a good book for me.

Right?

They did not have pre-tests for the highschool books.  :(

[quote="worthawholebean"]I actually found ACoPS a lot more useful as it went more into the [i]process[/i] of problem solving rather than the actual mathematical [i]tools[/i]. It was far more difficult than AoPS 2.[/quote]

I agree that ACoPS is harder. But I don't know if it is necessarily more useful. It depends on what your goals are. ACoPS doesn't give you as much material, in a way, since it is a skinnier book and they spend a lot of time talking about problem solving strategies instead of feeding you theorems and rules. However, of course, this is very important to understand too.

Question: If I can do AoPS Vol. I pretty well, would Intro to Counting and Probability be too much of a review? Should I just get Intermediate?

Not necessarily. To me, it seemed like Volume 1 didn't have that much counting, so I was pretty challenged by Intro to Counting and Probability. It covers a lot more than Volume 1 does. Infact, I was thinking of going over the two intro books I have (geometry and counting and probability) just to make sure I understand everything.

The focus of Volume 1 is definitely geometry. The Intro, along with Alcumus, can help a lot in Counting and Probability (i.e. fill in a lot of the gaps in Volume 1).

Yeah, Alcumus helps a lot.  I've been using Alcumus for awhile now, and I found that my best subject is now Counting and Probability.

I would say do the stuff in volume 2 and stuff from 104 problems from Number Theory, there always is PEN, which is problems in elementary number theory and its on the NT olympiad section of this website (i love PEN because even though its pretty hard, it uses pretty basic concepts, not the later ones though) and finally there is [url=http://www.geocities.com/CapeCanaveral/Lab/4661/]this.[/url]

[quote="Smartguy"][quote="Poincare"]Also, once you get to the AIME level, I have been finding a lot of Number Theory problems (many of them diophantine equations) in the first 8 or 10 problems, so you may want to get a resource for Number Theory as well.[/quote]

What would be a good resource besides the intro book?[/quote]

PEN is very helpful. Not all the problems are hard (in the middle of the divisibility section there were some that were very easy).

104 NT problems is also helpful. Another resource (which is unfortunately out of print) is 250 Problems in Elementary Number Theory.

im getting acops, 104 NT, and probably int. algebra for xmas! so excited

I just got Intro to Geo.

@Mathemonster - Is Int. Introduction or Intermediate? I'm assuming you are talking about intermediate.  :lol:

I think for anybody who wants to improve their AIME, Intermediate Counting and Prob seems like the best choice. It seems like a lot of emphasis is put there on AIME. That is what I am going to purchase next.

Also, the intermediate algebra book was extremely helpful. My AoPS I and II are good, but I would recommend the single subject texts because the extra detail they have is very useful.

[quote="Chopstiks"]Are the Into to Geo significantly different from the Geometry section on AoPs Vol 1? Because there's already like 100 pages of Geo there.[/quote]

Please don't revive this thread, but to answer your question, I think Intro to Geo. would still be a good book, because it covers a lot more than Volume I, and it is also good for people that have never done Geometry before, because the geometry in Intro to Geo. is a lot easier than the geometry in Volume I.


I currently have Asymptote 1.42 running on my desktop and can use interactive mode and can use asymptote in texniccenter, but I am curious on how to make asymptote output to picture formats like .jpg and .png

Try using asymptote on the Forum, and just save it. :D (if that counts)

Well I that is what I'm doing now and I find it tedious and produces less than expected results since sometimes when I copy it the image becomes black and then I have to invert the colors, drastically reducing quality. Another thing I have done is to take a screen shot of an asymptote diagram in pdf form, but this too produces an image that is not as visually consistent as the real thing.

If you normally view your Asymptote output in GSview, then go to File>>Convert to convert the output to a variety of formats.

Hello,
Try ending your code with this line
[code]shipout(format="png", options="-density 200 -resample 96 -quality 75");[/code]


Since integers are rational numbers the result is trivial.  :D

Sorry I missread the question, but if $ a,b,$ and $ c$ are positive then the only solution to $ ax^2 \plus{} by^2 \plus{} cz^2 \equal{} 0$ is $ x,y,z \equal{} 0$

[quote="aktyw19"]sory  :oops:  $ a,b,c$ only integers
I have corrected
[quote="aktyw19"]Let $ a,b,c$ integers and equation  $ ax^{2} \plus{} by^{2} \plus{} cz^{2} \equal{} 0$ has	solution in  integer numbers.
Prove that equation  $ ax^{2} \plus{} by^{2} \plus{} cz^{2} \equal{} 1$ has	solution in  rational numbers .[/quote][/quote]

That's wrong :
Take $ a\equal{}b\equal{}c\equal{}\minus{}1$ : $ \minus{}x^2\minus{}y^2\minus{}z^2\equal{}0$ has the solution $ (x,y,z)\equal{}(0,0,0)$ while $ \minus{}x^2\minus{}y^2\minus{}z^2\equal{}1$ has no solution.
Take $ a\equal{}b\equal{}c\equal{}0$ : $ 0x^2\plus{}0y^2\plus{}0z^2\equal{}0$ has  solutions  while  $ 0x^2\plus{}0y^2\plus{}0z^2\equal{}1$  has no solution.

If we modify the problem in such manner :
"Let $ a,b,c$ non zero integers and equation  $ ax^{2} \plus{} by^{2} \plus{} cz^{2} \equal{} 0$ has solution in  positive integers.
Prove that equation  $ ax^{2} \plus{} by^{2} \plus{} cz^{2} \equal{} 1$ has solution in  rational numbers ." then :

Let $ ax^2\plus{}by^2\plus{}cz^2\equal{}0$ with $ a\neq 0$ and $ x\neq 0$. Then : $ a\left(\frac{a\plus{}1}{2a}\right)^2\plus{}$ $ b\left(\frac{(a\minus{}1)y}{2ax}\right)^2\plus{}$ $ c\left(\frac{(a\minus{}1)z}{2ax}\right)^2\equal{}1$


geometry
circumcircle
trigonometry
geometry solved

In the triangle ABC the bisector of the angle BAC meets the circumcircle of the triangle ABC in the point D, which is not A. The points K and L are the perpendicular projections of the points B and C onto the line AD, respectively. Prove that AD >= BK + CL

By looking at the right triangles $ABK,ACL$ you get $BK+CL=(AB+AC)\cdot \sin \frac A2$, and by applying Ptolemy to $ABDC$, you get $AD=(AB+AC)\cdot \frac 1{2\cos \frac A2}$. We thus get $\frac {BK+CL}{AD}=\sin A\le 1$.


FIRST PRIZE
[b]Yufei Zhao[/b], Don Mills Collegiate Institute, Don Mills, Ontario. :)

SECOND PRIZE
[b]Jacob Tsimerman,[/b] University of Toronto Schools, Toronto, Ontario.

THIRD PRIZE
[b]David Rhee[/b], McNally School, Edmonton, Alberta.

HONOURABLE MENTIONS
[b]Boris Braverman[/b], Simon Fraser Junior High, Calgary, Alberta
[b]Dennis Chuang[/b], Strathcona-Tweedsmuir School, Okotoks, Alberta
[b]Gabriel Gauthier-Shalom[/b], Marianopolis College, Montreal, Quebec
[b]Oleg Ivrii[/b], Don Mills Collegiate Institute, Don Mills, Ontario
[b]Jnos Kramr[/b], University of Toronto Schools, Toronto, Ontario
[b]Andrew Mao[/b], A.B. Lucas Secondary School, London, Ontario
[b]Richard Peng[/b], Vaughan Road Academy, Toronto, Ontario
[b]Peng Shi[/b], Sir John A. MacDonald Collegiate Institute, Agincourt, Ontario.

Source: [url]http://www.cms.math.ca/MediaReleases/2004/cmo.html[/url]

Congratulations! You must be pretty happy about now. :)

Congrats! Now the infernal waiting to find out just how badly I did. ;)

What did you receive as a prize? Just a trophy?

:D Congrats Yufei!  I knew you would be at the top.  Didn't realize your potential when we were in the same school...  Anyways, great job!  Beat everyone else in IMO too! :D

Btw, that was my post.  Didn't know that you can post anonymously.

[quote="Osiris"]Now the infernal waiting to find out just how badly I did. ;)[/quote] Same here... But I can be sure the end of my waiting would be much worse...

Once again, Jacob Tsimerman did pretty good.

Congrats to Yufei though

[quote="blahblahblah"]Congratulations, Yufei.

Did you get it pretty much perfect (or perfect, for that matter?)[/quote]

Maybe, but I would never know.

The thing is, unlike other Olympiads, the Canadian one doesn't release your actual score.

Oh, I know that (I wrote it, too)

I was asking more for your opinion of whether you got it close to perfect.

[quote]I was asking more for your opinion of whether you got it close to perfect.[/quote]

I suppose. Though in a way, I felt that CMO this year was really a fluke for me. I finished all the problems in two hours, shocked, thinking that I must have done something wrong. So I checked my paper over and over and again (I did find a minor error in #1, thank god).

[quote]Do any of you know Boris Braverman, one of the Honourable Mentions? I was friends with him in 7th grade, when he lived in Connecticut. Is there any way of telling which of the HMs is going to the IMO?[/quote]

No, he is one of the people who didn't attend the IMO winter training this year. It's strange to see so many new names. Anyways, Boris seems to be in grade 9. That's amazing.
The team selection process is way more complicated than just taking the highest CMO score. the APMO and (Canadian marked) USAMO scores are taken into account too. Though, no one I know knows how exactly they select the team members. Three years ago I believe, a CMO third place finisher wasn't selected for the team.

One more thing, anyone noticed that the top three are all in grade 10? 8-)

Btw, does anyone know why Jacob is so strong in math?  I mean he got an IMO gold medal in Grade 9 and all.  Did he tell you guys any secrets or is he just super talented? :roll:

Both his parents are math professors at UofT, I think.

Edit: never mind - I was thinking of Oleg. Congrats to Jacob nonetheless...

does he even know this forum or any other uts students?/

Don't "blame" the parents and the school for one's achievements, it feels as if you're demeaning his own hardwork. I'm sure that Jacob is such because he became interested in math at a young age, and was aware of the competitions (something I wish I did). There's no doubt that he has done thousands of Olympiad problems on his own.

I'm not saying that - but parents undoubtedly play an important role in the development of a child. He has vast amounts of information available to him that are not normally available to, say, me. It's not unreasonable to say that he is better at math than I am, partially because of his parents' influence and support.

Jacob (along with Janos) and I were at the National Camp in UWO a couple of summers ago - I must say, he's very diligent.

[quote="anipoh"]I would agree that it really depends on the individuals.  It's essentially whether you really like math or not and whether you really work hard or not.[/quote]

Well, as long as we're digressing along this path, what determines whether someone likes math and is willing to work hard on it?  Individuals aren't formed in a vacuum, you know, and they certainly don't form themselves.  One has to be raised in an appropriate environment in order to excell at things because one has to be introduced to it in a positive light, one has to have encouragement to study it, and so on and so on.

[quote="anipoh"]Besides, he's in UTS.  Probably the one school that can beat every other school in math contests.

I mean in a school like UTS gives you some ideas about how good other people are.  If you are in a school where most people are mathematically illiterate, you would think you are a math genius and never work hard.  Also, it would be harder to find someone with similar interests.[/quote]

actually, my school (Hon. Vincent Massey SS) is the one school that can beat other school in math contests including UTS (and other contests), in terms of team school (which is more realistic than the scores Jacob Tsimmerman obtains personally representing UTS)

maybe the only exception is the CMO which we dont do well on...  but as far as i know, we still hold the most invited for CMO in a single school (we had ~15 writing it out of the ~80 students)
besides, i would think that not all of UTS are good at math since only about 15 qualifed for the AIME

If you want a good math environment, our school definately have one of the best in all of North America...  here we encourage students to show interest in math (not beating you up in problems).  but this also means that the training isnt hardcore enough to get into olympiad level.

Hmm....what about Don Mills....many students do well in Waterloo contests from that school...like Yufei...for ex.

Yufei is just one of those guys that works pretty hard...  No offence to Yufei about his talents though. :wink:

Don Mills has just gotten "lucky" in the recent years. First there was Roger Mong, then Olena, then Oleg, and now me :D. But the school doesn't have a program or anything like that, we just work by ourselves. Though the teacher is pretty supportive.

Just because Don Mills has so many smart people, it can continue to attract good students who think that Don Mills has a really good learning environment.  (Whether it really does or not, I'll leave it to Yufei)  Besides, its gifted programs just seem to have its advantages in attracting good students, or at least more attractive than just regular enriched classes.

I just learnt my CMO score...   that is completely BS!!!  geez those stupid markers that dont know how to mark!!!  -- I've never said anything like this on any contest before --  now I am REALLY ANGRY!!

How did you know your CMO score? I thought they don't release them

why are you moderator yufei? and btw if you cant figure it out, of course my source is Dr. White...

Ok, so apparently CMS sent a letter with results to schools. What did you all get? Yufei aside, of course... >_>"

Just signed up today and this is my first-ever post in 'Art of Problem Solving' :-)

Congratulations to all those Grade 10s who did so well in CMO, as well as some Grade 9s and Grade 11s. It's a little sad for my part since I'm already a Grade 12.
Also, how many G12s made HM? I know Andrew Mao is one of them. I'm in division 2, does there exist a division 1 above division 2 while below HM? I think there could be one, since I messed up CMO pretty bad (I completely misread #2)

[quote="weileaf"]Just signed up today and this is my first-ever post in 'Art of Problem Solving' [/quote]

Welcome to the forum.

[quote="weileaf"] does there exist a division 1 above division 2 while below HM?[/quote]

I don't think so. Division I consists of the winners and the HMs.

When did you get the letter that told you the result? And what else is on that letter?

[quote="billzhao"]

When did you get the letter that told you the result? And what else is on that letter?[/quote]

My teacher showed me that letter a week ago, and I think he probably got it on last Monday or so. It has the score of everyone from my school who participated CMO (but in my shcool, it's just me). My score is 20.5. There was also a certificate for partcipating CMO with the letter.

I guess they will send the winners a letter later?

I certainly remember the certificates, but no results from my teachers.

of the eight ppl who took the CMO this year, three ppl answered the last question, and all of us got 5151 as the final answer (incorrect)...  apparently this caused some suspecions and so all of us were marked down purposely (not just on the question, but the whole contest)  thats just TOTALLY IRRESPONSIBLE and RIDICULOUS!!!  we are powerless to change it :(  I like the American way WAY better (for handling USAMO), there are no discriminations against a single school...  The Canadian system is just stupid, period (esp with the TLE stuff also)

hahah that reminds me of a calculus movie
"Stand and Deliever"
hahah maybe u should take a 2nd cmo


algorithm calculus integration probability

I found this problem interesting and I tried to brute force it via computer, is there anyway I can improve my algorithm? (It's programmed in Python)

Problem: Find $ 3\times 3$ matrices (there are infinitely many) $ (a_{ij})$ with integral entries, but no $ a_{ij}\equal{}\pm 1, 0$, so that the determinant of $ (a_{ij})$ is 1 and the determinant of $ (a_{ij}^{2})$ is also 1.

I decided to restrict myself so that each entry is between -9 and 9, inclusive, but suppose each entry is between -100 and 100? Definitely, my $ O(n^{9})$ algorithm is too slow...

[code]nums = [-9, -8, -7, -6, -5, -4, -3, -2, 2, 3, 4, 5, 6, 7, 8, 9]

for a in nums:
    for b in nums:
        for c in nums:
            for d in nums:
                for e in nums:
                    for f in nums:
                        for g in nums:
                            j = b * f * g
                            k = c * e * g
                            for h in nums:
                                m = c * d * h
                                n = a * f * h
                                for i in nums:
                                    p = a * e * i
                                    q = b * d * i
                                    if ((p + j + m - k - n - q == 1) and (p**2 + j**2 + m**2 - k**2 - n**2 - q**2 == 1)):
                                        print(a, b, c, d, e, f, g, h, i)

print("Finished Checking All Possibilities")[/code]

An obvious remark is that once you have set the values for $ a,\dots,g$, you can solve for $ h$ and $ i$ instead of trial and error, which immediately reduces the running time to $ n^7$. Still, since such matrices are rather rare, I believe that you can do much better than that.

I was thinking, using the fact that $ \det A \equal{} \det A^{T}$ would remove a lot of possibilities, but is there an efficient way of processing through them? The only way right now I can think of is to create an arraylist of all possibilities for matrices and remove entries one by one, but that would be generating a huge number of entries...

Well, an easy-to-implement way to cut off most of the double-counting associated with $ A$ versus $ A^T$ is to just require that $ b \leq d$.  You can also require $ a \leq e$ if you like.  Another savings: if the entries of the first row have a common divisor other than 1, you lose, so there's no point in running through the other six loops in that case.

Right, but all of this is just a constant reduction :(. I believe, there should be an order reduction and I cannot find it so far  :wallbash:

try modular. write each entry $ a_{ij}p \plus{} b_{ij}$, and get an eq for $ b_{ij}$, choose $ p_1\cdot p_2$ that $ (p_1,p_2) \equal{} 1$, $ p_1\approx p_2$ and $ p_1p_2\approx w$ , where w is the boundary you set. Since the matrics are so rare (even in the ring $ Z_m$), try combinitory of each "pair" and examine.

No, they are not rare in $ \mathbb Z_p$ with prime $ p$! Each condition holds with probability about $ 1/p$ and they are almost independent, so I would expect $ p^7$ of such matrices in $ \mathbb Z^p$.


Well, I don't think complex numbers belong in the basics.

[quote="subhash333"]what is (5+i)(i-6)[/quote]

To rephrase: What is $(5+i)(i-6)$ when multiplied out?

[hide="Click to reveal hidden content"]$(5+i)(i-6)=5i-30+i^2-6i$ Since $i^2=-1$, substitute that in to get $5i-30-1-6i$.

Simplify to get $\boxed {-i-31}$[/hide]

[quote="goldendomer"][quote="subhash333"]what is (5+i)(i-6)[/quote]

what???? :huh:[/quote]

I think that you're asking for $i$:$i^2=-1$.

The result is $\boxed {-31-i}$.

While the problem might have been a little more appropriate if the definition of i was there, but it wasn't, and even then it would be too hard.

[hide="solution"]FOIL it out to get $-i-31$, or $i^3-31$.[/hide]


1. A convex polygon has $n$ sides and $9n$ diagonals. Find the value of $n$.

2. When you expand $(a+b)^{10}$, what is the coefficient of $a^{5}b^{5}$?

3. What is the greatest integer that is less than the reciprocal of $0.107$? (In other words, what is $\left \lfloor \frac{1}{0.107}\right \rfloor$?)

4. Beginning with the letter P and reading diagonally or downward, how many ways are there to read the name   "PAULETTE"?
P
A A
U U U
L L L L
E E E E E
T T T T T T
T T T T T T T
E E E E E E E E

5. Solve for $x$: \[\frac{1}{10^{1}}+\frac{1}{10^{2}}+\frac{1}{10^{3}}+\frac{1}{10^{4}}+\frac{1}{10^{5}}+\frac{1}{10^{6}}= \frac{x}{10^{6}}\] EDIT: This is Countdown, so no calculators.  :wink:  Also, please try to do more than one when you post your solutions, since these are not very difficult problems.  :wink:

[quote="nebula42"]1. A convex polygon has $n$ sides and $9n$ diagonals. Find the value of $n$.
2. When you expand $(a+b)^{10}$, what is the coefficient of $a^{5}b^{5}$?
3. What is the greatest integer that is less than the reciprocal of $0.107$? (In other words, what is $\left \lfloor \frac{1}{0.107}\right \rfloor$?)
4. Beginning with the letter P and reading diagonally or downward, how many ways are there to read the name   "PAULETTE"?
P
A A
U U U
L L L L
E E E E E
T T T T T T
T T T T T T T
E E E E E E E E
5. Solve for $x$: \[\frac{1}{10}+\frac{1}{100}+\frac{1}{1000}+\frac{1}{10000}+\frac{1}{100000}+\frac{1}{1000000}= \frac{x}{1000000}\] [/quote]

[hide="3"]
When you divide, you get $9.3457\dots$. When you floor that $\lfloor 9.3457\dots \rfloor$ is equal to $9$[/hide]

[hide]1. The answer is 21. Since you know that $n(n-3)/2$ is equal to 9n you can solve for that :

$n(n-3)/2$= 9n
$n(n-3)$=18n

$n^{2}-21n$=0

solve for that and you get 21[/hide]

[quote="lotrgreengrapes7926"][quote="anirudh"][hide="3"]
When you divide, you get $9.3457\dots$. When you floor that $\lfloor 9.3457\dots \rfloor$ is equal to $9$[/hide][/quote]
I don't think that's the most efficient way, unless you're really fast at long division. Try to find another method. :D[/quote]

I can do long division really fast.  :lol: I did that in like 4 secs. :D

I'll just post the answers here so you can check them after you've finished the problems. However, if you want to post your answer to the problems afterward, please also post a solution (anyone can just copy an answer  :wink: ).

[hide="Answers"]
1. $21$
2. $252$
3. $9$
4. $128$
5. $111111$[/hide]

[hide="2"]The coefficient of $a^{5}b^{5}$ in $(a+b)^{10}$ is ${10\choose 5}=252$.[/hide]
[hide="4"]From a letter on a row, there are two ways to pick the next letter on the next row. There are 7 rows after P. There are $2^{7}=128$ ways.[/hide]
[hide="5"]Multiply both sides by $10^{6}$ and we get $x=111111$.[/hide]

[quote="pianoforte"][hide="2"]The coefficient of $a^{5}b^{5}$ in $(a+b)^{10}$ is ${10\choose 5}=252$.[/hide]
[hide="4"]From a letter on a row, there are two ways to pick the next letter on the next row. There are 7 rows after P. There are $2^{7}=128$ ways.[/hide]
[hide="5"]Multiply both sides by $10^{6}$ and we get $x=11111$.[/hide][/quote]

You might want to check your answer for number 5.

But everything else seems right.

[hide="1"]The number of diagonals for an n-gon is $\frac{n(n-3)}{2}$. We know the number of diagonals is $9n$, so we can say $\frac{n-3}{2}=9$, then solve from there to get $n=21$.[/hide]
I don't think that's the quickest solution, though...

easyaspi: yeah, that method is probably the easiest way to solve it - all you have to do is multiply by 2 and add 3.

[quote="mathgeniuse^ln(x)"][hide]Well...find a better method.

Take note that $\frac{1}{8}=0.125$ and $\frac{1}{7}=0.142857142857...$

And of course this is just a way of "Getting Started"[/hide][/quote]
Click the smiley. :D
[hide=" :huh: "] $\frac{1}{9}=0.\bar{1}$ and $\frac{1}{10}=0.1$ [/hide]

Yeah, that is what I meant...

Don't know where that came from...


Assume that $ m$ and $ n$ are odd integers such that
\[ m^{2} \minus{} n^{2} \plus{} 1 \mid n^{2} \minus{} 1.
\]
Prove that
\[ m^{2} \minus{} n^{2} \plus{} 1
\]
is a perfect square.

This turns out to be a very difficult problem! I know it was also given in a Moldavian TST not long time ago. Iura, do you have a solution for this one? Or anyone else?

I am really incredible! I found the equation, but I just made the computations of reducing the components wrong and I found this method cannot be applied. Of course, because I'm absolutely idiot and do not pay attention to computations. After this " masterpiece" I've tried all different possible tricke, but I didn't manage. Thanks, iura.

[quote="iura"]Let u=(m+n)/2,v=(m-n)/2; k=m^2/(m^2-n^2+1) a integer
The equation becomes u^2-(4k-2)uv+v^2-k=0
Doesn't it resemble to you like Engel's famous 1988 or 1989 IMO problem.
I mean, select (u,v) with u>=v and v minimal. If v <u the we can replace (u,v) by (v,(4k-2)v-u). So u=v and in this case k is a perfect square.
This solves the problem[/quote]

Ok !Your solution is very good I think.

But could you or anyone help me to clear that ?

For the first question

Why the equation becomes u^2-(4k-2)uv+v^2-k=0 ?

For the second question

You said that u=v so m+n=m-n so n = 0

But for (m,n) =(1,1)  and n is not 0 ???

Yes, but this is a particular case. When $u=v=1$ we actually have $(4k-2)v-u=u$ so $u=(2k-1)v$ and by substituting this we get $u=v=1$. I mean, that method works unless a class of small solutions which can be verified manually.


let a, b, c be positive real numbers. prove that
$ \frac{1}{a^{2}\plus{}ab\plus{}bc}\plus{}\frac{1}{b^{2}\plus{}bc\plus{}ca}\plus{}\frac{1}{c^{2}\plus{}ca\plus{}ab}\leq\ \frac{(a\plus{}b\plus{}c)^{2}}{(ab\plus{}bc\plus{}ca)^{2}}$

[quote="Luba1123"]let a, b, c be positive real numbers. prove that
$ \frac {1}{a^{2} \plus{} ab \plus{} bc} \plus{} \frac {1}{b^{2} \plus{} bc \plus{} ca} \plus{} \frac {1}{c^{2} \plus{} ca \plus{} ab}\leq\ \frac {(a \plus{} b \plus{} c)^{2}}{(ab \plus{} bc \plus{} ca)^{2}}$[/quote]
It's obviously true after expanding. :wink:

[quote="Luba1123"]let a, b, c be positive real numbers. prove that
$ \frac {1}{a^{2} \plus{} ab \plus{} bc} \plus{} \frac {1}{b^{2} \plus{} bc \plus{} ca} \plus{} \frac {1}{c^{2} \plus{} ca \plus{} ab}\leq\ \frac {(a \plus{} b \plus{} c)^{2}}{(ab \plus{} bc \plus{} ca)^{2}}$[/quote]
See here: http://can-hang2007.blogspot.com/2010/01/inequality-55-unknown-author.html