The sum of two numbers is $ 10$; their product is $ 20$. The sum of their reciprocals is:

$ \textbf{(A)}\ \frac{1}{10}\qquad
\textbf{(B)}\ \frac{1}{2}\qquad
\textbf{(C)}\ 1\qquad
\textbf{(D)}\ 2\qquad
\textbf{(E)}\ 4$

Let $ a$ and $ b$ be the two numbers so that:

$ a \plus{} b \equal{} 10$ and $ ab \equal{} 20$.

The sum of the reciprocals is $ \dfrac{1}{a} \plus{} \dfrac{1}{b} \equal{} \dfrac{a \plus{} b}{ab} \equal{} \dfrac{10}{20} \equal{} \dfrac{1}{2}$

Hence the answer is $ \boxed{\mathbf{(B)}}$


induction
number theory proposed
number theory

Find all subsets $A$ of $\left\{ 1, 2, 3, 4, \ldots \right\}$, with $|A| \geq 2$, such that for all $x,y \in A, \, x \neq y$, we have that $\frac{x+y}{\gcd (x,y)}\in A$.

[i]Dan Schwarz[/i]

But this one it says $x\neq y$.

Come on, Romania won't copy problems  :)  :D

May you tell me where it's mentioned in this problem that $A$ is finite?
And, of course, we must have that $x \neq y$.

Here's an outline of a proof: consider two smallest elements of the set and call them $x \leq y$. There are to cases: one easy to tackle is $(x,y)>1$ and another is $(x,y)=1$. To deal with second one see that $kx+y$ and $ky+x \in A$ hence $yx+x \in A$ and $\frac{(yx+y)+y)}{y}=x+2 \in A$ so either $y=x+1$ or $y=x+2$. See that $xy+x+y \in A$, then $2xy+x^{2}+y^{2}+kx+ky \in A$ (just by adding $x$ or $y$ one by one) hence $\frac{(x+y)(x+y+k)+(x+y)}{x+y}=x+y+k+1 \in A$ and taking sufficient k we get $3 \in A$. Now there are some cases to check and we get generally that $\mathbb{N}, \mathbb{N}-\{1\}, \mathbb{N}-\{1,2\}$ works. Also from the first case $(x,y)>1$ we get $A=\mathbb{N}$

actually, there is another solution, more precisely, a family of finite solutions.
when $\gcd(a,b)>1$ ($a<b$ are the two smallest elements of $A$), note that $\frac{a+b}{\gcd(a,b)}<b$, thus it must be equal to $a$. from here it`s not very hard to see that $a=d$, $b=d(d-1)$.
now, let $c$ be the third element of $A$. if $\gcd(b,c)=1$ or $\gcd(a,c)=1$, then it is the same as the case when $\gcd(a,b)=1$ (with some work it can be proved that $3,4\in A$, and from there it`s easy).
if $\gcd(a,c)>1$ and $\gcd(b,c)>1$, note that $\frac{a+c}{\gcd(a,c)}$ and $\frac{b+c}{\gcd(b,c)}$ are smaller than $c$, thus they must be $a$ and $b$. checking both cases leads to contradiction.
thus, the solutions are that above, and sets of the form $\{d,d(d-1)\}$, where $d\geq 3$.

1. $\frac{x+x}{gcd(x,x)}=2\in A$.
2. If all terms A even and x is minimal term, greater, than 2 we get $2<\frac{x}{2}+1<x\in A$ give contradition. Therefore exist odd terms. If x odd term, then $\frac{x+2}{gcd(x,2)}=x+2\in A$, therefore all odd primes greater N in A. Let $x$ odd term, then $x<3x\in A$, therefore $\frac{x+3x}{gcd(x,3x)}=4\in A$ and $\frac{2+4}{gcd(2,4)}=3\in A$, therefore all odd numbers greater 1 in A.
3. All even numbers in A, because if m even, then odd terms $x, (m-1)x\in A$, therefore $\frac{x+(m-1)x}{gcd(x,(m-1)x)}=m\in A.$
It mean $A=N$ or $A=N/\{1\}.$

Rust, $x \not =y$ is one of the conditions

Ok!
1. If exist to terms $x,y\in A$, suth that $(x,y)=1$, then $x,y+x\in A, (x,y+x)=1$, therefore (by induction $x,y+nx\in A, (x,y+nx)=1, \ \forall n\in N$.
It give $y+yx\in A\Longrightarrow \frac{y+y+yx}{(y,y+yx)}=x+2\in A.$
Because $(x,y)=1$ one of them odd, let it be x. It give all odd numbers greater, than x in A. Therefore $x,(2n-1)x\in A\Longrightarrow 2n\in A \ \forall n\ge 2.$ From $4,8\in A\Longrightarrow 3\in A$.
In mean, that we proof if exist x,y in A, suth that (x,y)=1, then $n\in A \ \forall n>2$.
2. Let x is minimal term in A and y is term, suth that $(x,y)=d$ - minimal divisor. Then $x=ad, y=bd, (a,b)=1,a+b\in A$.
We have $(x,a+b)|(x,ad+bd)=(x,x+y)=(x,y)=d$. Because d is minimal mean for (x,y) we get $(x,a+b)=d$ and $a+b<y$. Because we have finite numbers in interval (x,y) it give contradition with $(x,z)\ge d \ \forall z\in A.$
It mean exist y, suth that $(x,y)=1$, therefore $3\le n\in A \ \forall n\in N$.

as i said above, the case when there exists no pair $a,b$ with $\gcd(a,b)=1$ leads to a solution with $|A|=2$, that is, the family of sets of the form $\{d,d(d-1)\}$, with $d\geq 3$.
here is my proof :
take $a<b$ the smallest elements of $A$, and assume $d=\gcd(a,b)>1$. let $a=dx$, $b=dy$. from the hypothesis, $x+y\in A$. however, $x+y=\frac{a+b}{d}\leq \frac{a+b}{2}<b$, thus $x+y=a$, that is $x+y=dx$, or $y=x(d-1)$. this means $x|y$, but since $\gcd(x,y)=1$, it follows that $x=1$ and $y=d-1$.
thus, $a=d$ and $b=d(d-1)$, leading to a solution.
now, i assume that $|A|>2$. take $c$ the third element of $A$ (that is, $a<b<c$ are the smallest elements of $A$).
if $\gcd(a,c)=1$ or $\gcd(b,c)=1$, then this case is solved (by methods above).
so let`s assume $\gcd(a,c)>1$, $\gcd(b,c)>1$. using the same idea as above, the numbers $\frac{a+c}{\gcd(a,c)}$ and $\frac{b+c}{\gcd(b,c)}$ are in $A$, but they are both smaller than $c$, so they must be $a$ and $b$. if $\frac{a+c}{\gcd(a,c)}=a$, it follows that $c=b$, contradiction. now, let $a=eu$, $c=ev$, with $e=\gcd(a,c)$. from the fact that $u+v=b$, it follows that $v=b-u=a(a-1)-u=eu(a-1)-u=u(e(a-1)-1)$. so again $u=1$, $e=d$, $v=d(d-1)-1$. thus, $\gcd(b,c)=\gcd(a,c)=d$, and $b=\frac{a+c}{\gcd(a,c)}<\frac{b+c}{\gcd(b,c)}<c$, so i found an element of $A$ between $b$ and $c$, contradiction.
thus, if $|A|\geq 3$, there exists two coprime elements of $A$.

[quote="Megus"]then $ 2xy \plus{} x^{2} \plus{} y^{2} \plus{} kx \plus{} ky \in A$ (just by adding $ x$ or $ y$ one by one) [/quote]

Hmm... are you sure you can get this by adding $ x$ or $ y$ one by one?  :wink:

I've proved to finite sets the following statement: If S= {a_1 < a_2 <  ... < a_n} satisfies these conditions, then a_k = a_1(a_k -1) for all k which means that the sequence is established by the smallest term. Then it's not hard to check that the 3 smallest elements cause an absurd. Then it must have at maximum 2 elements which leads us to the solution: {x, x(x-1)}


inequalities
trigonometry
algebra
function
domain
real analysis
real analysis unsolved

If f:R^n -> R^n such that |f(x) - f(y)| >= |x - y| for all x,y in R^n show that
if A is an open set in R^n, then f(A) is open.

A counterexample:
$ f(x)\equal{}x\plus{}\frac{x}{|x|}$ for $ x\neq 0$, $ f(0)\equal{}0$. The image of $ \mathbb{R}^{n}$ is the origin and the outside of the unit ball.

A semi-geometric proof of the inequality:
It's obvious if either point is the origin. Suppose neither $ x$ nor $ y$ is zero.
Let $ |x|\equal{}a,|y|\equal{}b$, and let $ \theta$ be the angle between them. The square of the old distance was $ a^{2}\plus{}b^{2}\minus{}2ab\cos\theta,$ and the square of the new distance is $ (a\plus{}1)^{2}\plus{}(b\plus{}1)^{2}\minus{}2(a\plus{}1)(b\plus{}1)\cos\theta\equal{}a^{2}\plus{}b^{2}\minus{}2ab\cos\theta\plus{}2(a\plus{}b\plus{}1)(1\minus{}\cos\theta)$.

It's true if $ f$ is also continuous though. More generally, a one-to-one continuous self-map of a Euclidean space is open, by [url=http://mathworld.wolfram.com/DomainInvarianceTheorem.html]Brouwer's Domain Invariance Theorem[/url].


number theory
greatest common divisor
induction

Prove that for any integers $ a_1,a_2,\cdots,a_n$ there exist integers $ x_1,x_2,\cdots,x_n$ with
\[ \gcd(a_1,a_2,\cdots,a_{n})\equal{}x_1a_1\plus{}x_2a_2\plus{}\cdots\plus{}x_na_n\]

[b]Lemma 1[/b] [i](Bézout's identity[/i] There exist $ m,n$ such that $ am\plus{}bn\equal{}d$, where $ \text{gcd}(a,b)\equal{}d$.
[hide="Proof"]
Let $ S$ be the set of integers of the form $ ai\plus{}bj$. Let $ d\equal{}am\plus{}bn$ be the least member of $ S$. We may write $ a\equal{}dq\plus{}r$ with $ 0\leq r<d$ (Division algorithm). However, if $ r\equal{}a\minus{}dq\equal{}a\minus{}(am\plus{}bn)q\equal{}a(1\minus{}amq)\minus{}bnq$, we must have $ r\equal{}0$. Otherwise $ r$ is in $ S$ and smaller than $ d$, which is a contradiction. Then $ d|a$. By the same process, we find that $ d|b$, so $ d$ is the gcd of $ a$ and $ b$.
[/hide]

Now we can solve the problem by induction on $ n$. We've shown as a base case that there exists $ x_1$ and $ x_2$ such that $ \text{gcd}(a_1,a_2)\equal{}x_1a_1\plus{}x_2a_2$.

Suppose $ \text{gcd}(a_1,\ldots,a_k)\equal{}\sum{i}^{k} x_ia_i$

We have that $ \text{gcd}(a_1,\ldots, a_{k\plus{}1})\equal{}\text{gcd}(\text{gcd}(a_1,\ldots,a_k), a_{k\plus{}1})$, because the gcd is associative. Therefore, we have $ \text{gcd}\left(\sum_i^kx_ia_i,a_{k\plus{}1}\right)\equal{}m\left(\sum_i^kx_ia_i\right)\plus{}na_{k\plus{}1}$, which leads to the conclusion $ \Box$


[i]Problem :[/i]

    [i]Find[/i]

 $ \lim_{n\to\infty} (\ \frac{1}{2}  \plus{} sin^{2}\frac{\pi}{7}sin^{\frac{1}{n}}\frac{\pi}{7}  \plus{} sin^{2}\frac{2\pi}{7}sin^{\frac{1}{n}}\frac{2\pi}{7} \plus{} sin^{2}\frac{3\pi}{7}sin^{\frac{1}{n}}\frac{3\pi}{7}  )^{n}$

         [i]This problem from  a  contest  take place at Hồ Chí Minh city[/i]

Are you sure this is the correct question?


You can prove it by the same way like here:
http://www.artofproblemsolving.com/Forum/viewtopic.php?t=152850


rezolvati si discutati ecuatia $\sqrt{2x+a}+\sqrt{2x-a}=\sqrt{5x}$ , a este numar real

ridicam la patrat ,simplificam 4x mai odata la patrat si ramane 15x^2=4a^2 ,de unde x=...


limit
function
logarithms
real analysis
real analysis unsolved

I) Let $ a \in (1,+\infty) \backslash\{e\}$. Show the equation $ a^x = x + 1 $ has, besides the solution $ x_1 = 0 $, another solution $ x_2(a)$.

II) Let $ x_n^' $ be the only non zero solution of the equation ${ (1+ \frac {1} {n}})^{nx} = x + 1 $ and $ x_n^{''}$ the only non zero solution of the equation ${ (1+ \frac {1} {n}})^{(n+1)x} = x + 1 $, for all integer $ n \geq 1 $.
Find $ \displaystyle\lim_{n\to +\infty}x_n^'$, $ \displaystyle\lim_{n\to +\infty}x_n^{''}$ and $ \displaystyle\lim_{n\to +\infty}\frac {x_n^'} {x_n^{''}}.$

I see only problem here ;) : find $\lim x_n'/x_n''$.

Well, number one is very easy except for one step:

a^x=e^(x*lna)=x+1, set u=x*lna, then e^u=1+u+u^2/2!+u^3/3!+...=u/lna+1, subtract sides and divide both of them by u, get (1-1/lna)+u/2+(u^2)/6+(u^3)/24+...=0.  Now, the function u/2+(u^2)/6+... is analytic everywhere, so it must assume every possible complex value at least once, except possibly a single value (I forget what that theorem is called but it can be found in various books on complex variables).  Now then, I guess you would have to prove that for the values of a in question, 1/lna-1 is not this one single value that cannot be satisfied, if such a value exists at all.[/code]

NO, goodyfresh741, don't use the complex plane. This is a real problem. The existence of the second solution is actually quite simple. There are two cases:

If $a>e$ and $f(x)=a^x$, then $f'(0)>1.$ Hence for $x<0$ but near zero, $a^x<1+x$. However, $a^x>0$ always but for $x<-1,\,1+x<0.$ Hence for $x<-1,\,a^x>1+x$ and the Intermediate Value Theorem guarantees a solution.

If $a<e,$ $f'(0)<1.$ Hence for $x>0$ but near zero, $a^x<1+x.$ However, we know that as $x\to\infty,\,a^x$ grows much faster than $x$ so that for large $x,\,a^x>1+x.$ Again, the Intermediate Value Theorem guarantees a solution.

If $g(x)=a^x-1-x$, then $g'(x)=a^x\ln a-1$ which has only one zero, at $x=\frac{\ln\ln a}{\ln a}.$ Hence by Rolle's Theorem, $g(x)$ can have at most two zeros.

Part two is much more challenging. Just note two things to start: for all $n$, $\left(1+\frac1n \right)^n<e$ and $\left(1+\frac1n \right)^{n+1}>e.$

The equation $(1+1/n)^{nx}=x+1 $ has  non zero solution $ x^{'}_n=1/n $ and the equation $ (1+1/n)^{(n+1)x}=x+1$ has non zero solution $ x''_n=-1/(n+1) $.
Then
\[
\displaystyle \lim_{n \to +\infty}x'_n=\displaystyle \lim_{n \to +\infty}x''_n=0\qquad \textrm{and}\qquad\displaystyle \lim_{n \to +\infty}x'_n/x''_n=-1
\]

Whoops, my earlier post was pretty stupid. . .I'm only in highschool, so you guys are probably better off ignoring me anyway.


calculus
integration
quadratics
abstract algebra
algebra
polynomial
number theory

Let $ S$ be the set of positive integers which ca be written in the form $ a^2 \plus{} 5b^2$ for some co-prime integers $ a$ and $ b$. Let $ p$ be a prime congruent to $ 3$ modulo $ 4$ .Prove that if some integral multiple of $ p$ belongs to $ S$ , then $ 2p$ belongs to $ S$ as well.

A number $ n$ is of form $ a^2 \plus{} 5b^2$ iff the following properties hold all together:
a) The prime factors $ p \equiv 11,13,17,19 \mod 20$ occure each an even number of times: $ 2| v_p(n)$ for those $ p$.
b) The totel amount of prime factors $ p \equiv 2,3,7 \mod 20$ is even (counted with multiplicity): $ 2| \sum_p v_p(n)$ where the sum is over those primes.

The result follows immediatly.

[quote="ZetaX"]A number $ n$ is of form $ a^2 \plus{} 5b^2$ iff the following properties hold all together:
a) The prime factors $ p \equiv 5,11,13,17,19 \mod 20$ occure each an even number of times: $ 2| v_p(n)$ for those $ p$.
b) The totel amount of prime factors $ p \equiv 2,3,7 \mod 20$ is even (counted with multiplicity): $ 2| \sum_p v_p(n)$ where the sum is over those primes.

The result follows immediatly.[/quote]

Can you show me please?

Yes  :wink: (Assuming you know some algebraic number theory; I will avoid Class Field Theory here)

[b]Lemma 1:[/b]
A number $ n$ is of the form $ x^2 + 5y^2$ iff it's a norm from $ \mathbb Z[\sqrt { - 5}]$ iff there is a principial ideal $ \mathfrak a \subset \mathbb Z[\sqrt { - 5}]$ having ideal norm $ n$.
[u]Proof:[/u]
The first part is trivial.
The only fact needed for the second part is that the ideal norm and element norm coincide: $ \mathcal N ((a)) = N_{\mathbb{Q}[\sqrt { - 5}] | \mathbb Q}(a)$ for $ a \in \mathbb Z[\sqrt { - 5}]$. See any text on Algebraic Number Theory for this one.

[b]Lemma 2:[/b] (splitting of the ideals $ (p)$).
Let $ p$ be a rational prime. Then the complete ideal factorisation of $ (p)$ in $ \mathbb Z[\sqrt { - 5}]$ is:
a) $ (2) = (2,1 + \sqrt { - 5})^2$.
b) $ (5) = (\sqrt { - 5})^2$.
c) $ (p) = \mathfrak a_p \mathfrak b_p$, $ \mathfrak a_p \neq \mathfrak b_p$, iff $ ( \frac { - 5}{p} ) = 1$.
d) $ (p) = (p)$ iff $ ( \frac { - 5}{p} ) = - 1$.
For simplification, we will use $ \mathfrak a_p, \mathfrak b_p$ for the factors of $ (2),(5)$ as well.
[u]Proof:[/u]
See Neukirch, Algebraic number theory, theorem 8.3. A sketch of a direct approach:
a) and b) can be checked directly. In case c), we find an integer $ a$ such that $ a^2\equiv - 5 \mod p$; one checks directly that $ (p) = (p,a - \sqrt {-5})(p,a + \sqrt {-5})$, that the two ideals on the right are different, and that they are prime (look at their norms; see also c) of the next lemma) . In case d), one easily checks that $ \mathbb Z[\sqrt { - 5}] / (p)$ is a field, thus the result.

[b]Lemma 3:[/b]
The prime ideal factors of the previous lemma have the following norms:
a) $ \mathcal N((2,1 + \sqrt { - 5})) = 2$.
b) $ \mathcal N((\sqrt { - 5})) = 5$.
c) $ \mathcal N(\mathfrak a_p) = p = \mathcal N(\mathfrak b_p)$.
d) $ \mathcal N((p)) = p^2$.
[u]Proof:[/u]
Trivial by multiplicativity of $ \mathcal N$.

[b]Lemma 4:[/b] (more exact description of splitting).
Let $ p$ be a rational prime such that $ ( \frac { - 5}{p} ) = 1$. Then the ideal factors of case c) of Lemma 2 are principal iff $ ( \frac { - 1}{p} ) = 1$.
[u]Proof:[/u]
Note that $ ( \frac { - 1}{p} ) = 1$ iff $ p \equiv 1 \mod 4$.
1st case: $ p \equiv 3 \mod 4$:
Assume that the factor $ \mathfrak a_p$ is principal. By Lemma 1, this means that $ p = x^2 + 5y^2$ for some integers $ x,y$. But this contradicts $ p = x^2 + 5y^2 \equiv x^2 + y^2 \equiv 0,1,2 \not\equiv 3 \equiv p \mod 4$. Thus $ \mathfrak a_p$ is not principal.
2nd case: $ p \equiv 1 \mod 4$:
That one is rather tough if we don't want to use class field theory. Here one way to go:
The integral closure of $ \mathbb Z[\sqrt { - 5}]$ in $ \mathbb Q[ \sqrt { - 5}, i]$ is $ R = \mathbb Z[i, \frac {1 + \sqrt {5}}{2}]$ (use standard methods). Let $ a^2\equiv - 5 \mod p, \ b^2 \equiv - 1 \mod p$ (exist because $ ( \frac { - 1}{p} ) = 1 = ( \frac { - 5}{p} )$). Then we have the factorisations $ (p,a - \sqrt { - 5}) = (p,a - \sqrt { - 5},b - i)(p,a - \sqrt { - 5},b + i)$ of prime ideals of norm $ p$ in $ R$ (again, just check directly). By the next lemma, these ideals are principal, so $ (p,a - \sqrt { - 5},b - i) = (s)$ for some $ s \in R$. But then let $ t = N_{\mathbb Q[ \sqrt { - 5}, i] | \mathbb Q[ \sqrt { - 5}]}(s)$, thus $ N_{\mathbb{Q}[\sqrt { - 5}] | \mathbb Q}(t) = N_{\mathbb Q[ \sqrt { - 5}, i] | \mathbb Q}(s) = \mathcal N((p,a - \sqrt { - 5},b - i)) = p$, so by Lemma 1, we are finally done.

[b]Lemma 5:[/b]
$ R$ (see the proof before) is a principal ideal domain.
[u]Proof:[/u]
The Minkowski bound is somewhere around $ 3$, thus it's just checking two ideals.

[b]Lemma 6:[/b]
$ \mathbb Z[\sqrt { - 5}]$ has class number $ 2$.
[u]Proof:[/u]
Just use standard methods (the Minkowski bound is somewhat around $ 5$, so it's a short task).

Now define:
$ S = \{ p \in \mathbb P | p \equiv 1,5,9 \mod 20\}$
$ T = \{ p \in \mathbb P | p \equiv 2,3,7 \mod 20\}$
$ U = \{ p \in \mathbb P | p \equiv 11,13,17,19 \mod 20\}$
Note that by what we have shown (and a simple application of quadratic reciprocity), in $ \mathbb Z[\sqrt { - 5}]$, the primes of $ U$ don't factor, but those in $ S$ and $ T$ do; the factors are principal exactly in $ S$.

[u][b]Theorem:[/b][/u]
Let $ n \in \mathbb N$. Then $ n$ is of type $ x^2 + 5y^2$ iff the following conditions hold all together:
a) $ 2|v_p(n)$ for all $ p \in U$
b) $ 2|\sum_{p\in T} v_p(n)$.
[u]Proof:[/u]
Let $ \mathcal J$ be the abelian multiplicative monoid of ideals of $ \mathbb Z[\sqrt { - 5}]$ and $ \mathcal P$ the submonoid of principal ideals. A basis of $ \mathcal J$ is given by $ B = \{\mathfrak a_p, \mathfrak b_p | p \in S\cup T\} \cup\{(p) | p \in U\}$ as these prime ideals are independent (by unique factorisation) and generate $ \mathcal J$ (by being all possible prime ideal divisors of ideals extending prime ideals $ (p)$ of $ \mathbb Z$).
The Norm $ \mathcal N : \mathcal J \to \mathbb N$ is a homomorphism (of abelian multiplicative monoids). Now the claim is by Lemma 1 equivalent to: $ \mathcal N(\mathcal P)$ is the submonoid of natural numbers $ n$ fulfilling the mentioned properties a) and b).
The norms of the basis $ B$ are given by $ \{ p | p \in S \cup T\} \cup \{ p^2 | p \in U\}$ by Lemma 3. Thus $ \mathcal N(\mathcal J)$ are those $ n$ fulfilling property a).
As the class number of $ \mathbb Z [\sqrt { - 5}]$ is $ 2$ (Lemma 6), for being a principal ideal, it's necessary and sufficient to have an even number of non-principal prime ideal factors. The nonprincipal basis elements are exactly $ \{\mathfrak a_p, \mathfrak b_p | p \in T\}$. So for $ n \in \mathcal N(\mathcal J)$, having preimage $ \mathcal N^{ - 1}$ in $ \mathcal P$ is equivalent to having an even number of prime factors of type $ T$. Thus $ n \in \mathcal N(\mathcal P)$ iff a) and b) hold.
[b]q.e.d.[/b]

Note completely the same proofs apply if we replace $ 5$ by $ 13$. Also note that an easy consideration gives the coprimality you want for your numbers exactly if there is no divisor of $ U$ and at most one factor $ 5$.
The general setting for describing numbers of type $ x^2 + dy^2$ is as follows:
Lemmas 1, 2, 3 generalise to arbitrary $ d > 0$ instead of $ 5$. For Lemmas 4 and 5, we need a ring $ R$ having the following properties:
- every ideal of $ \mathbb Z [\sqrt { - d}]$ gets principal in $ R$.
- an ideal is completely split iff it was already principal (with possible exception the ramified ideals).
Such a ring is given by class field theory, namely the ring of integers of the Hilbert class field. Thus by taking a primitive element $ \alpha$ with minimal polynomial $ f$ of the Hilbert class field (over $ \mathbb Q[\sqrt { - d}]$), we can describe the possibility of writing a prime $ p$ as $ x^2 + dy^2$ by this polynomial $ f$ having a root $ \mod p$ (except for those primes dividing the discriminant or $ 2d$).

Have anyone has another solution please?

I did some minor corrections to the above proof.

ricardo4: For your original problem, use Thue's lemma. See http://www.mathlinks.ro/Forum/viewtopic.php?p=293201#293201 . It gives you that you can find $ a,b$ such that $ a^2 \plus{} 5b^2$ is one of $ p,2p,3p,4p,5p$. You can then exclude all cases except $ 2p$ and $ 3p$: $ a^2 \plus{} 5b^2 \equal{} p$ gives a contradiction $ \mod 4$, $ 5p$ reduces to the case $ p$, and the case $ 4p$ reduces to $ p$ by looking $ \mod 4$ again. So you get that $ a^2 \plus{} 5b^2$ is $ 2p$ or $ 3p$.
For the case $ 3p \equal{} a^2 \plus{} 5b^2$, show that $ 2p \equal{} \left(\frac {a \plus{} 5b}{3}\right)^2 \plus{} 5\left(\frac { \minus{} a \plus{} b}{3}\right)^2 \equal{} \left(\frac {a \minus{} 5b}{3}\right)^2 \plus{} 5\left(\frac {a \plus{} b}{3}\right)^2$ and that at least on of those two representations is integral.

If I'm in very (!) good mood, I may one day write down the completely elementary way to classify numbers of type $ x^2\plus{}5y^2$.


Did anyone solve anything from round 6? Please post your solutions

My soln for problem 1 was very ugly :

[hide="my soln"]
\section*{Exercise 1}

We will first study $g(a,b,c,d)=(a+b+c+d)(\frac{1}{a} + \frac{1}{b} + \frac{1}{c} + \frac{1}{d})$.

\subsection*{g(a,b,c,d)}

Without loss of generality we can assume $a\leq b\leq c\leq d$.
Let us first fix $a$ and $d$, and study the values that $g$ can take for $a\leq b\leq c\leq d$.
We have
\[ \partial_{b} \, g(a,b,c,d) = \frac{ac+cd+da}{acd} - \frac{a+c+d}{b^2},  \]
so $\partial_b \, g$ is positive iff
\[ b > \sqrt{\frac{acd(a+c+d)}{ac+cd+da}}=h(a,c,d)  \]

\subsubsection*{Minimizing}

(Let us prove that $g$ is minimal for $b=c=\sqrt{ad}$.)

Since
\[ a \leq \sqrt{ac} \leq \sqrt{ac}\sqrt{\frac{ad+cd+d^2}{ad+cd+ac}} = h(a,c,d) \]

$g$ is minimal for $b=\min(c,h(a,c,d))$.

1) First case : $b=c$.

In this case $c\leq h(a,c,d)$, so
\[ c^2 (ac+cd+da) \leq acd(a+c+d),  \]
that is
\[ c^2 (ac+cd) + adc^2 \leq ad (ac+cd) + adc^2,  \]
thus since $ac+cd>0$, $c \leq \sqrt{ad}$.

As for $b$, $\partial_c \, g > 0$ iff
\[ c > h(a,b,d),  \]
so $g$ is minimal for $c=\max(b,h(a,b,d))$.

Since $b \leq c \leq \sqrt{ad}$,
\[ h(a,b,d) = \sqrt{\frac{abd(a+b+d)}{ab+bd+da}} = b \sqrt{\frac{ad(a+d) + abd}{(a+d)b^2 + abd}} \geq b, \]
so $c=h(a,b,d)$. Thus $b=h(a,b,d)$, and the inequality above must be an equality.
We thus get that $b=c=\sqrt{ad}$.

2) Second case : $b=h(a,c,d)$.

There, for $g$ to be minimal we need either $c=b$ (which has already been treated),
or $c=h(a,b,d)$. In the second case we will prove that in fact $b=c$. Indeed we have
\[ b^2 (ac+cd+da) = acd(a+c+d), \]
\[ c^2 (ab+bd+da) = abd(a+b+d). \]
Therefore, by substraction, we get
\[ bc(a+d)(c-b) + ad(c+b)(c-b) = - ad(a+d)(c-b) - ad(b+c)(c-b),  \]
thus
\[ (c-b)(abc+bcd+acd+abd+a^2d+ad^2+abd+acd)=0,  \]
which gives the desired conclusion.

We can finally deduce that $g$ is minimal for $b=c=\sqrt{ad}$, which gives
\[ g(a,b,c,d) = \left(a+2\sqrt{ad}+d\right)\left(\frac{1}{a} + \frac{2}{\sqrt{ad}} +\frac{1}{d}\right) = \left(2+\sqrt{\frac{a}{d}} +\sqrt{\frac{d}{a}}\right)^2. \]

\subsubsection*{Maximizing}

As before we have $\partial_{b} \, g$ of the same sign as $b-h(a,c,d)$, so $g$ is maximal when $a=b$ or $b=c$.
Likewise we have $b=c$ or $c=d$.

If $b\neq c$, then $a=b$, $c=d$, so
$g(a,b,c,d)=(2a+2d)\left(\frac{2}{a}+\frac{2}{d}\right)=8+4\left(\frac{a}{d}+\frac{d}{a}\right)$.

If $b=c$ we get
\[ g(a,b,c,d) = (a+2b+d)\left(\frac{1}{a}+\frac{2}{b}+\frac{1}{d}\right) \]
\[ = 6 + \left(\frac{a}{d}+\frac{d}{a}\right) + 2 \left(\frac{b}{d}+\frac{d}{b}+\frac{a}{b}+\frac{b}{a}\right) \]
\[ \leq 6 + \left(\frac{a}{d}+\frac{d}{a}\right) + 2 \left(\frac{b}{d}+\frac{d}{b}+\frac{a}{b}+\frac{b}{a}\right) + 2\left(1-\frac{a}{b}\right)\left(1-\frac{b}{d}\right)+ 2\left(\frac{b}{a}-1\right)\left(\frac{d}{b}-1\right) \]
\[ = 6 + \left(\frac{a}{d}+\frac{d}{a}\right) + 2 + 2 \frac{a}{d} + 2 + 2 \frac{d}{a} \]
\[ = 10 + 3 \left(\frac{a}{d}+\frac{d}{a}\right) \]
\[ \leq 8 + 4 \left(\frac{a}{d}+\frac{d}{a}\right). \]

Thus $\max(g)=8+4\left(\frac{a}{d}+\frac{d}{a}\right)$.
Since $g$ is continuous, it takes all values between
\[ \left(2+\sqrt{\frac{a}{d}} +\sqrt{\frac{d}{a}}\right)^2,  \]
and
\[ 8+4\left(\frac{a}{d}+\frac{d}{a}\right).  \]

%-----------------------------

\subsection*{Original problem}

A ratio $R=d/a$ is possible to get iff $16 p^2$ is in the range of values taken by $g$, that is iff
\[ \left(2+\sqrt{\frac{1}{R}} +\sqrt{R}\right)^2 \leq 16 p^2 \leq 8+4\left(R+\frac{1}{R}\right).  \]

The first inequality is equivalent to
\[ \sqrt{\frac{1}{R}} + \sqrt{R} \leq 4p-2,  \]
thus to
\[ R+\frac{1}{R} \leq (4p-2)^2-2,  \]
which is itself equivalent to
\[ R^2 - R (16p^2 - 16p + 2) + 1 \leq 0,  \]
that is to
\[ \frac{16p^2-16p+2 - \sqrt{(16p^2-16p+2)^2 -4}}{2} \leq R \leq \frac{16p^2-16p+2 + \sqrt{(16p^2-16p+2)^2 -4}}{2} \]
\[ 8p^2 - 8p + 1 - \sqrt{(8p^2 - 8p)(8p^2 - 8p + 2)} \leq R \leq 8p^2 - 8p + 1 + \sqrt{(8p^2 - 8p)(8p^2 - 8p + 2)} \]
\[ 8p^2 - 8p + 1 - 4(2p-1)\sqrt{p(p-1)} \leq R \leq 8p^2 - 8p + 1 + 4(2p-1)\sqrt{p(p-1)}. \]
Since $8p^2 - 8p + 1 - 4(2p-1)\sqrt{p(p-1)}$ is the inverse of $8p^2 - 8p + 1 + 4(2p-1)\sqrt{p(p-1)}$, and since the second one
is bigger than $1$, $8p^2 - 8p + 1 - 4(2p-1)\sqrt{p(p-1)} \leq 1$, so since $R \geq 1$, we can reduce the interval to
\[ 1 \leq R \leq 8p^2 - 8p + 1 + 4(2p-1)\sqrt{p(p-1)}.  \]

The second inequality is equivalent to
\[ 4p^2 - 2 \leq R + \frac{1}{R},  \]
thus to
\[ R^2 - (4p^2 - 2) R + 1 \geq 0.  \]
Since $R \geq 1$, this is equivalent to
\[ R \geq \frac{4p^2 - 2 + \sqrt{(4p^2-2)^2 - 4}}{2} \]
\[ = 2p^2 - 1 + \sqrt{(2p^2-2) 2 p^2} \]
\[ R \geq 2p^2 - 1 + 2 p \sqrt{p^2 - 1}, \]
which is bigger than $1$.

We thus get that $R$ is a possible value of $\frac{\max(a,b,c,d)}{\max(a,b,c,d)}$ iff
\[ 2p^2 - 1 + 2 p \sqrt{p^2 - 1} \leq R \leq 8p^2 - 8p + 1 + 4(2p-1)\sqrt{p(p-1)}.  \]

[/hide]

anyone solved problem 2?

any nice solutions for 1?

I did half of q1, showing that one of the bounds (lower or upper, i can't remember) for the expression is $(\sqrt{p} + \sqrt{p-1})^4$. I presume this was the easy part. I didn't submit it though.

[quote="perfect_radio"]
any nice solutions for 1?[/quote]
I solve this problem white use this old ineq.
$(x_1+x_2+...+x_n)(\frac{1}{x_1}+\frac{1}{x_2}+...+\frac{1}{x_n})\leq n^2\frac{(m+M)^2}{4Mm}$,wher$m\leq x_1\leq x_2\leq ...\leq x_n\leq M$ ;)
(My solution is not wery ugly :D)

At the Mongolian inequality darij or Myth (sorry i am not remember who) post an article for the majorization ineq .In this article the ineq posted by tiks is solved in three lines using Karamata, but i don't know russian so I cannot read full solution

[quote="Makaveli"](My solution is not wery ugly :D)[/quote]
Then why don`t you post it.[/quote]
You want solution of this problem
$(x_1+x_2+...+x_n)(\frac{1}{x_1}+\frac{1}{x_2}+...+\frac{1}{x_n})\leq n^2\frac{(m+M)^2}{4Mm}$
or solution of the problem from round 6?


Both x and y are positive numbers less than 2.  Every positive number less than 2 is equally likely to be the value of x; and every positive number less than 2 is equally likely to be the value of y.  What is the probability that x and y differ by less than 1?

[hide]
This can be solved geometrically.  Think of each (x,y) as a point.  If we put all of the possible points on a graph, we get the region bounded by x=2, y=2 and the x and y axes.  This region has an area of 4.  We want to find the region where the difference between x and y is less than 1.  Thus:
$|x-y|<1 \Rightarrow x-y<1$ AND $ y-x<1$
If we graph these two lines, $y>x-1$ and $y<x+1$ along with the previous restraints, we get a region of area 3.  Thus the probabality that x and y will differ by less than one is 3/4.
[/hide]

[hide]the green represtnts the ones that work

so 6/8=[b]3/4[/b][/hide]


Determinati numrele naturale nenule ce se pot scrie sub forma $\frac{(x+y+z)^2}{xyz}$, cu $\ x,y,z$ naturale.

Nu stiam ca nu e originala.Eu am vazut-o in cartea dansului.Poti da totusi o solutie?

Pot da o solutie, numai ca ar fi mult mai simplu sa o cauti pe forumul olimpiadelor (teoria numerelor), imi amintesc ca a fost rezolvata acolo.  Cartile nu sunt facute cu probleme originale (cel putin cu siguranta nu cele de olimpiade).

[quote="harazi"]Hmmm... asta numai originala nu e.[/quote]
   Da, acum mi-am dat seama.Cred ca a fost data la Olimpiada din Franta, deci nu e originala.


Let $ a,b,c$ be positive such that $ \min\{4ac\minus{}b^2,4ba\minus{}c^2,4cb\minus{}a^2\}>0$ and reals $ x,y$ with $ x\plus{}y\equal{}1$.

$ \prod{ax^2\plus{}bxy\plus{}cy^2}\ge\prod{\frac{4ac\minus{}b^2}{a\plus{}c\minus{}b}}$

Where the products are cyclic over $ (a,b,c)$

 :)

[hide="hint"]
$ (x\plus{}y)^6\equal{}1$
[/hide]

 :)

It's not true when $ x\plus{}y\equal{}1$ (take $ a\equal{}b\equal{}c\equal{}1,x\equal{}y\equal{}\frac{1}{2}$), but it is true when $ x\plus{}y\equal{}2$.

In this case, $ (a\plus{}c)^2\geq 4ac>b^2$ implies $ a\plus{}c\minus{}b$ is strictly positive. In this case,
\[ ax^2\plus{}bxy\plus{}cy^2\equal{}ax^2\plus{}bx(2\minus{}x)\plus{}c(2\minus{}x)^2\equal{}(a\plus{}c\minus{}b)x^2\plus{}2(b\minus{}2c)x\plus{}4c\]
\[ \equal{}\frac{[(a\plus{}c\minus{}b)x\plus{}(b\minus{}2c)]^2\plus{}4c(a\plus{}c\minus{}b)\minus{}(b\minus{}2c)^2}{a\plus{}c\minus{}b}\]
\[ \equal{}\frac{[(a\plus{}c\minus{}b)x\plus{}(b\minus{}2c)]^2\plus{}4ac\minus{}b^2}{a\plus{}c\minus{}b}\]
\[ \geq \frac{4ac\minus{}b^2}{a\plus{}c\minus{}b} (>0)\]
so taking similar inequalities for other terms and multiplying yields the result.

You are completely right.

Somehow when I posted the problem I forgot to add $ \frac{1}{4}$ on the right side.

What I did is finding the best constant $ k$ such that the inequality

$ ax^2\plus{}bxy\plus{}cy^2\ge k(x\plus{}y)^2$ holds.

 :)


analytic geometry
geometry
3D geometry
tetrahedron
linear algebra
linear algebra unsolved

Is there an equilateral triangle in the plane all of whose vertices have integer coordinates?  If you can, answer the same question for vertices required to have rational coordinates.

Extend this to a tretahedron in the 3-D Cartesian coordinates system.

let $ A(x,y),B(\alpha,\beta)$ and $ C(a,b)$ then : $ [(\alpha \minus{} x)^2 \plus{} (\beta \minus{} y)^2]\sqrt {3}/2 \equal{} AB^2\sqrt {3}/2 \equal{} \parallel{}\vec{AB} \wedge \vec{AC}\parallel{} \equal{}
 (\alpha \minus{} x)(b \minus{} y) \minus{} (a \minus{} x)(\beta \minus{} y)$.
and since $ \sqrt {3}$ is irrational and we cannot have $ (\alpha \minus{} x)^2 \plus{} (\beta \minus{} y)^2 \equal{} 0$ then there are no rational number $ x,y$,....

A tetrahedron (not necessarily regular) with rational coordinates (in $ 3$-space) has rational volume, but it's straightforward to show that a regular tetrahedron with side length the square root of a rational has irrational volume.

No, that's not true. Consider the regular tetrahedron with vertices $ (0,0,0),(1,1,0),(1,0,1),(0,1,1)$.
Volume scaling as the cube of the side rather than the square makes a difference.


geometry
trapezoid
rectangle
Pythagorean Theorem

In trapezoid $ABCD$ with bases $\overline{AB}$ and $\overline{CD}$, we have $AB=52$, $BC=12$, $CD=39$, and $DA=5$. The area of $ABCD$ is

(A) 182
(B) 195
(C) 210
(D) 234
(E) 260

Oh yes never mind the exact answer is C (210) I was forgetting something. I dont think this should be in Intermediate Topics. Heres a solution:

[hide]Draw Perpendiculars to AB from C and D. Since we know that AB and BD are parallel the perpendiculars are congruent because the perpendicular distance between any two points on parallel lines is always congruent. Now we have divided the Trapezoid into two right triangles one with lengths 5, x, and y and the other with side lengths 12, 13-x and y. Now using the Pythagorean theorem we set up equations:

$12^{2}= y^{2}+(13-x)^{2}$
$5^{2}=y^{2}+x^{2}$

Solving  for those we get that x= 25/13 thus y=60/13 then using that we can conclude that the trapezoid's area is 210.[/hide]

[quote="mathgeniuse^ln(x)"][quote="sonny"]Hmmm.....I seem to have gotten 214.6153846........ So if it was asking closest to then the answer would be C but if they wanted an exact answer then I dont know.[/quote]

Please don't tell me u've used Brahmagupta's Formula.[/quote]

Brahmagupta's Formula can only be applied when the quadrilaterlal is cyclic, but in this case it's not

k how was this question # 25 on a recent AMC 10..like even for a grade 10 it seems trivial..

[quote="SM4RT"][hide]

its (c) 210

[/hide][/quote]

OK, that's really unhelpful, and a pointless post.
As to the solutions, they are correct.

[quote="sonny"][quote="mathgeniuse^ln(x)"][quote="sonny"]Hmmm.....I seem to have gotten 214.6153846........ So if it was asking closest to then the answer would be C but if they wanted an exact answer then I dont know.[/quote]

Please don't tell me u've used Brahmagupta's Formula.[/quote]

Read my post right above your post[/quote]

Oh, I didn't notice it sorry.

But that is what you used to get the first answer right?

[hide="simple solution"]
Notice that 52-39 = 13.  So If we extend AD and CB to intersect at E, triangle ABE is similar to a 5-12-13 right triangle.  From that, it's easy to see that CE = 36, DE = 15, and Area(ABCD) = Area(ABE) - Area(CDE) = 480-270 = 210.

[/hide]

Edit: Trivial (meaning stupid) mistake in solution

[quote="SM4RT"]Do you mean extend AD and CB??[/quote]
yes, I'll edit that, sorry.

ya i found a simple solution too..
[hide]
Dropping perpendiculars from $AB$ to $CD$ and call the intersection $E$ and $F$ respectively. We see that $AE+BF = 13$ also..$AD = 5$ and $BC = 12$..thats a $5-12-13$ triangle...so the height of this triangle is the height of $ABCD$... so

$5\cdot12 = 13\cdot h$
$h = \frac{60}{13}$

so you can calculate the area by either
(a) $=\frac{52+39}{2}\cdot\frac{60}{13}= \frac{91}{2}\cdot\frac{60}{13}= \boxed{210}$
(b) Area of the Right-Triangle + Area of Rectangle
     $= \frac{5\cdot12}{2}+39\cdot\frac{60}{13}$
     $= 30+180$
     $= \boxed{210}$
[/hide]

That is smart.

Too Bad, that might not always work.

[quote="SM4RT"]ya i know but it works well in this case..ya it works as well for question 3a on the COMC (its 6-8-10)..too bad i didnt notice that on the real contest..[/quote]

Well, yeah, and of course the dropping perpendiculars never fails us, I think.


Hi.

In which city will be the IMO 2008?

(this topic is related to http://www.mathlinks.ro/Forum/viewtopic.php?t=158416)

I think it's Granada, (it's in the south)

I don't think so... in the official site says it's in Madrid
See:http://www.imo-official.com/host_list.asp

It will be Madrid for the students, and Granada for the Leaders and Coordinators.


modular arithmetic
quadratics
special factorizations
number theory proposed
number theory

Suppose that $ p$ is a prime number. Prove that for each $ k$, there exists an $ n$ such that:
\[ \left(\begin{array}{c}n\\ \hline p\end{array}\right)\equal{}\left(\begin{array}{c}n\plus{}k\\ \hline p\end{array}\right)\]

This is equivalent to proving that there exists $ n$ such that $ \left( \frac{n(n\plus{}k)}{p} \right) \equal{} 1$, which is equivalent to showing the existence of a point on the curve $ x(x \plus{} k) \equal{} y^2$.  Completing the square gives

$ (x \plus{} k)^2 \equal{} y^2 \plus{} k^2$

and now it's enough to observe that we can find $ m, n$ such that $ k \equiv 2mn \bmod p$ for any odd prime $ p$.  The result is obvious for $ p \equal{} 2$.

[quote="t0rajir0u"]... $ x(x \plus{} k) \equal{} y^2$.  ...

$ (x \plus{} k)^2 \equal{} y^2 \plus{} k^2$[/quote]
Are the two equivalent? Or were they not meant to be?

My apologies.  For $ p$ odd, $ \frac{1}{2}$ exists $ \bmod p$ so we can write $ k' \equal{} \frac{k}{2}$ and $ (x \plus{} k')^2 \equal{} y^2 \plus{} k'^2$.

If $p|k$ then just take $n=p$ , now consider two sets $A,B$ such as $(\frac{n}{p})=1\implies n\in\ A$ otherwise $n\in\ B$. Now we've condition that $a,b\in\ A\implies ab\in\ A$ and $a,b\in\ B\implies ab\in\ B$ also $a\in\ A,b\in\ B \implies ab\in\ B$ and call this operation as $T$. Now assume that there doesn't exist such a $n$ at all. Now if $n+k \in\ P$ and so $n+(2x+1)k \in\ P$ also $n+2xk \in\ Q$ where $\{P,Q\}=\{A,B\}$. First if $P=A,Q=B$ then taking $n=k$ applying $T$ we get $P\cap Q \neq \phi$ otherwise taking $n=k-1$ again applying $T$ we get $P\cap Q \neq \phi$ but it's absurd, other case is similar, so we arrived at a contraction and so done.

Another proof:for odd $p$ not equal to $3$ and any $k$ there exist some $n$ such that $3n=k(mod p)$.So such $n$ exists $(\frac{n}{p})=(\frac{4n}{p})$.For $p=2,3$ we can count with hands.

There exists $a,b\in\mathbb{N}$ such that $ k \equiv a^2 -b^2 \ (\textrm{mod}\ p)$

$n=b^2$ complete the proof.

There is a slight theoretical issue here. Originally, Legendre defined $\genfrac {(} {)} {} {} {a} {p} \equiv a^{\dfrac {p-1}{2}} \pmod{p}$, for odd primes $p$ only. According to that, and to other approaches, $\genfrac {(} {)} {} {} {a} {p} = 0$ when $p\mid a$. If we extend the symbol to $p=2$ by $\genfrac {(} {)} {} {} {a} {2} = 1$ for $a$ odd and $\genfrac {(} {)} {} {} {a} {2} = 0$ for $a$ even, then the problem fails for $p=2$ and $k$ odd, since then, for any $n$, the numbers $n$ and $n+k$ are of different parity. For the same reason, the problem also fails for $p=3$ when $3\nmid k$. Likely, for the problem setters, since indeed $0$ is a (trivial) quadratic residue, they assumed $\genfrac {(} {)} {} {} {0} {p} = 1$, which for most authorities is wrong.

So let us work with primes $p>3$ only. The idea of the post above needs clarification in its claim. Now $2$ is inversible modulo $p$. Let us take $a\equiv \dfrac {k+1}{2} \pmod{p}$ and $b\equiv \dfrac {k-1}{2} \pmod{p}$; then indeed $a^2-b^2 \equiv k \pmod{p}$. Taking $n=b^2$ we have $n+k \equiv a^2 \pmod{p}$, and so we achieve $\genfrac {(} {)} {} {} {n} {p} = 1 = \genfrac {(} {)} {} {} {n+k} {p}$, thus even more than what was asked, but that [b]only[/b] if $p\nmid a$ and $p\nmid b$.
But we cannot always avoid $p\mid a$ or $p\mid b$ if we look for $a^2-b^2 \equiv k \pmod{p}$, for example for $k=1$ and $p=5$. Therefore for $k\equiv \pm 1 \pmod{p}$ it is generally false that we can find $n$ such that $\genfrac {(} {)} {} {} {n} {p} = 1 = \genfrac {(} {)} {} {} {n+k} {p}$, so we must go back to the original requirement, and only hope for $\genfrac {(} {)} {} {} {n} {p} = \genfrac {(} {)} {} {} {n+k} {p}$, unless told to consider $\genfrac {(} {)} {} {} {0} {p} = 1$.

But now [b]hal9v4ik[/b]'s idea works. Finding $3n\equiv k \pmod{p}$ makes $n+k\equiv 4n \pmod{p}$, and so $\genfrac {(} {)} {} {} {n} {p} =  \genfrac {(} {)} {} {} {2^2n} {p} = \genfrac {(} {)} {} {} {n+k} {p}$ (but not necessarily of value $+1$).

[b]Addendum[/b]. The case $p=5$ is special (as already hinted at in the above). For $k\not \equiv \pm 1 \pmod{p}$ we can find $n$ such that both Legendre symbols are $+1$, as above. For $k\equiv \pm 1 \pmod{p}$ we cannot find two consecutive not-null quadratic residues, so we are left with taking $n=2$ when $k\equiv 1 \pmod{p}$, and $n=3$ when $k\equiv -1 \pmod{p}$, and thus get both Legendre symbols equal to $-1$. For $p>5$ we can however do more. Since at least one of $\{2,5,10\}$ must be a not-null quadratic residue (if $2$ and $5$ are not, then $10=2\cdot 5$ must be), and since $2=1^2+1, 5=2^2+1, 10=3^2+1$, we can actually find two consecutive not-null quadratic residues, and by this strengthen the claim of the problem.

Another solution by inspecting $p\pmod{8}$. Let $p>3$.

If $p\equiv \pm 1\pmod{8}$, simply let $n=k$, as $2$ is a quadratic residue modulo $p$. If not, then start with the case $p\equiv 3\pmod{8}$. In this case, $-1$ is not a quadratic residue, and $-2$ is a quadratic residue. If $p\equiv 1\pmod{6}$ then $-3$ is a quadratic residue modulo $p$ too, so $n=-3k$ works. If $p\equiv 5\pmod{6}$, then $-3$ is not a quadratic residue, and thus, $3$ is a  quadratic residue. In this case, $n=3k$ works.

Now let $p\equiv 5\pmod{8}$. Similar to above, $-1$ is a quadratic residue, and $-2,2$ are not. Now if $p\equiv 1\pmod{6}$ then $-3$ is a quadratic residue as well, and thus, so do $3$. Hence, $n=3k$ works. If $p\equiv 5\pmod{6}$, then neither $-3$ nor $-2$ are quadratic residues modulo $p$, thus, $n=-3k$ works.


Find all polynomial solutions of the functional equation:

f(x)*f(x + 1) = f(x^2 + x + 1)

[quote="mikeynot"]Find all polynomial solutions of the functional equation:

$f(x).f(x + 1) = f(x^2 + x + 1) \forall x\in R$[/quote]

My solution:
*)If$f(x)\equiv a\Rightarrow a=0 or a=1$
*)Another
If f(x) have root x then f(x) have many infinite root,a contradition
$\Rightarrow$f(x) have no real root$\Rightarrow$degf=2n
$\Rightarrow f(x)=a_{2n}x^{2n}+...+a_0\Rightarrow a_{2n}=a_0=1$
Suppose that f(x) have root:$x_1,...,x_{2n}(x_i\notin R)$.By Viet theorem we have:
$x_1.x_2.....x_{2n}=1\Rightarrow |x_1|...|x_{2n}|=1$
If exist j such that $|x_j-1|>0\Rightarrow$f(x) have many infinite root.a contradition
$\Rightarrow |x_1|=...|x_{2n}|=1$
Given $x_k=cos\alpha+isin\alpha\Rightarrow x_{k+1}=x_i^2+x_i+1$
$\Rightarrow x_{k+1}=(cos2\alpha+cos\alpha+1)+i(sin2\alpha+sin\alpha)$
$\Rightarrow (cos2\alpha+cos\alpha+1)^2+(sin2\alpha+sin\alpha)^2=1$
$\Rightarrow cos\alpha(cos\alpha+1)=0\Rightarrow x_k=+_-i\Rightarrow f(x)=(x^2+1)^n$

nice solution.it's also appears in a book of professor Nguyen Van Mau


pigeonhole principle
decimal representation
number theory
Divisibility
multiple
IMO Shortlist
Digits

Prove that every integer $ k$ greater than 1 has a multiple that is less than $ k^4$ and can be written in the decimal system with at most four different digits.

Let n be the unique integer such that 2n−1 ≤ k < 2n. Let S(n) be the set
of numbers less than 10n that are written with only the digits {0, 1} in
the decimal system. Evidently |S(n)| = 2n > k and hence there exist two
numbers x, y ∈ S(n) such that k | x − y.
Let us show that w = |x − y| is the desired number. By definition k | w.
We also have
w < 1.2 · 10n−1 ≤ 1.2 · (23√2)n−1 ≤ 1.2 · k3√k ≤ k4.
Finally, since x, y ∈ S(n), it follows that w = |x−y| can be written using
only the digits {0, 1, 8, 9}. This completes the proof.

[quote="ramakrishna"]Let n be the unique integer such that 2n−1 ≤ k < 2n. $ \cdots$[/quote]
Why should $ k$ be odd?
[quote="ramakrishna"]$ \cdots$ Evidently |S(n)| = 2n $ \cdots$[/quote]
I don't understand this. :maybe:

Take $m$ such that $2^{m-1}\le n<2^m$. There are $2^m>n$ numbers with $m$ digits or less and whose digits are all $0$ or $1$, so by the Pigeonhole Principle two of them must be equivalent $\mod n$. Hence, their difference is congruent to $0\mod n$, and is less or equal to \[\frac{10^m}{9}=16^{m-1}\left(\frac{10}{16}\right)^{m-1}\left(\frac{10}{9}\right)<16^{m-1}\le n^4\] for $m>1$. But the difference between any two numbers with digits $0$ and $1$ consists only of the digits $0$, $1$, $8$, and $9$.


Find a six digit square where the number formed by the last three digits are one more than the one formed by the first three. (123124 is one such number, but it isn't the number)

[hide]
Call the three digit number that is formed by the first three digits $a$. The $6$ digit number can then be expressed as \[1001a+1\] For some positive integer $m$, we have \[1001a+1 = m^{2}\] Solving for $a$ \[a =  \frac{(m+1)(m-1)}{1001}\] $1001$ has the factors $7, 11, 13$, so trying out all different possible system of congruences (is there a faster way?), we find \begin{eqnarray*}m &\equiv&-1 \mod{7}\\ m &\equiv&-1 \mod{11}\\ m &\equiv& 1 \mod{13}\end{eqnarray*} provides $m=846$ as a solution, so the $6$ digit number is equal to $715716$
[/hide]

[b]Adunakhor[/b], nice solution, but

[hide]why do you take only this value of m?

Shouldn't we solve the following system of congruences? \begin{eqnarray*}m &\equiv&\pm 1 \mod{7}\\ m &\equiv&\pm 1\mod{11}\\ m &\equiv&\pm 1 \mod{13}\end{eqnarray*} Then we get the values $155,274,428,573,727,846$ for $m$

From this values of m, the first two are rejected because they give 5-digit numbers[/hide]

[color=brown]P.S. I see that the user [b]PenguinIntegral[/b] changed the initial message, so I suspect that the initial problem was asking for the [u]maximum[/u] 6-digit number[/color]

Oh, :oops:. For some reason, when I read the question, I was under the impression that there was only one such number, so I stopped after finding $m=846$.


geometry
geometric transformation
rotation

Suppose $ A_1A_2A_3....A_{20}$, be a 20-sided regular polygon. How many scalene triangles, can be formed whose vertexes are among the vertexes of the polygon, but whose sides are not the sides of the polygon?

I am not sure:

[hide]
Each type of triangle can be identified with a triple $ (a,b,c)$ where the three represent the number of sides between two adjacent vertices. For it to be scalene, all three values must be different. Then for it not to use the sides of he polygon itself, each must be greater than or equal to 2.

List all sets of 3 distinct integers greater than 2 that have a sum of 20.

You have 16. THen you take into account rotation nand flipping. $ 16\cdot 40 \equal{} 640?$[/hide]

Once more, i am terribly unsure.

The answer is correct but can you explain this line?

[code]Then for it not to use the sides of he polygon itself, each must be greater than or equal to 2.[/code]

What he's saying is that there has to be at least two sides of the polygon between two vertecies of the triangle. If this wasn't true then one of the sides of the triangle would coincide with a side of the polygon.

I counted ways to pick $ 3$ vertices for the triangle (leaving $ 17$ vertices not used). That means finding triples $ (a,b,c)$ of natural numbers adding to $ 17$ with $ a<b<c$. From there, follow the same reasoning.
Say $ A_1$ is the vertex of the triangle between the shortest and longest sides. Going in one direction, we can skip over $ 1$ vertex to connect it to $ A_3$, then skip $ 2$ vertices to connect $ A_3$ to $ A_6$ for a second side. Then the third side would be skipping $ 14$ vertices, and $ (1, 2, 14)$ represents the number of vertices skipped. The total number of vertices skipped will always be $ 20-3=17$. We can make $ 16$ such triples, hence $ 16$ scalene triangles with a vertex $ A_1$ between a shorter side in the direction of $ A_2$ and a longer side in the direction of $ A{}_2{}_0$.
We can start at any vertex, and we can go in the opposite direction, so we multiply $ 16$ (number of triplets that work) by $ 20$ (starting vertices) and $ 2$ (directions) to get $ 640$ triangles.


Let a_1,a_2,...,a_n, where n>3 be real numbers such that
a_1+a_2+...+a_n \geq n and a_1 2 +a_2 2 +...+a_n 2  \geq n 2 . Prove that max{a_1,a_2,...,a_n} \geq 2.


Let a,b,c=>0 such that a+b+c=6 prove that  a^2+2b^2+3c^2+abc=>24

in the past, i was post this topic but no one didn't reply the answer.

--------------------------------------------------------------------------------
please reply as fast as you can..

i'm korean,so i poor at english(understand about that)

[quote="swanny1080"]Let $ a,b,c\equal{}>0$ such that $ a\plus{}b\plus{}c\equal{}6$ prove that  $ a^2\plus{}2b^2\plus{}3c^2\plus{}abc\equal{}>24$
[/quote]
Yes, it's true. The equality holds when $ a\equal{}4,$ $ b\equal{}2$ and $ c\equal{}0.$


How many different triangles can be formed having a perimeter of 7 units if each side must have integral length?

Refer to [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=249028]this[/url]. The answer is $ \boxed2$.


[quote="kunny"]If $a\geqq b\geqq c, x\geqq y\geqq z, x+y+z=0$, prove that we have $ax+by+cz\geqq 0$.[/quote]
$ax+by+cz \ge \frac{(a+b+c)(x+y+z)}{3} = 0$

siuhochung: Can you use this ineq also for negative terms?

BTW it's quite easy. From $x\geq y\geq z$ and $x+y+z=0$ we have $x\geq 0, x+y\geq 0$. Now:
$ax+by+cz=x(a-b)+(x+y)(b-c)+(x+y+z)c=x(a-b)+(x+y)(b-c)\geq 0$
Because $x(a-b)\geq 0$ and also $(x+y)(b-c)\geq 0$.

i think rearrangement/chebyshev do not require the terms to be positive.

[url=http://planetmath.org/encyclopedia/ChebyshevsInequality.html]There[/url] they say that at least one of the sequences should consist of positive numbers.[/hide]

Nevertheless, both rearrangement and Chebyshev inequalities work for arbitrary real numbers. The standard proofs don't require any of the numbers to be positive.

  Darij

Here is  my solution.

As we have $z\leq 0,x\geq 0,x+y+z=0,ax+by+cz\geq bx+by+bz=b(x+y+z)=0$ Q.E.D.

kunny


If $g(X)=ax^{3}+bX^{2}+cX+d\in Q[X]$ has the root $\sqrt{5}-\sqrt{2}$ then $a=b=c=d=0$.

[hide="Solution"]Put in $X = \sqrt{5}-\sqrt{2}$. $b$ is the only one that is a coefficient of $\sqrt{10}$, so it is therefore $0$. Then $d$ is the only one that is a coefficient of a rational number, so it too is $0$. This leaves $a$ and $c$.

$a(\sqrt{5}-\sqrt{2})^{3}= a(11\sqrt{5}-17\sqrt{2})$ so $0 = (11a+c)\sqrt{5}-(17a+c)\sqrt{2}$, which clearly only has $a = c = 0$ a solution.[/hide]

I do not think your solution stands as it is not necessary for the coefficent of the rational number to be $0$, neither the coefficent of $\sqrt{10}$ .
Try finding the minimal polynomial over $Q[X]$ of $\sqrt{5}-\sqrt{2}$.

I get $x^{4}-14x^{2}+9$ as a polynomial, so the problem is equivalent to showing that it's irreducible.

[hide]It clearly has no linear factors, since it can't even be divisible by 7 if $x$ is integer. Then if it weren't irreducible, we would get a factorization of the form
\[(x^{2}+ax+b)(x^{2}+cx+d)\]
Setting $x^{3}$ coefficients equal, we get $a=-c$, and setting $x$ coefficients equal, we get $b=d$. Now our polynomial looks like
\[(x^{2}+ax+b)(x^{2}-ax+b)=x^{4}+(2b-a^{2})x^{2}+b^{2}\]
So $b=\pm 3$, and $a^{2}=20$ or $a^{2}=8$. Neither work.[/hide]

[quote="spix"]I do not think your solution stands as it is not necessary for the coefficent of the rational number to be $0$, neither the coefficent of $\sqrt{10}$ .[/quote]
How do you cancel out the $\sqrt{10}$ when $a,b,c,d$ are all rational?

[quote="scorpius119"]I get $x^{4}-14x^{2}+9$ as a polynomial, so the problem is equivalent to showing that it's irreducible.[/quote]
You are right.

$x=\sqrt{5}-\sqrt{2}\Longrightarrow x^{2}=(\sqrt{5}-\sqrt{2})^{2}\Longleftrightarrow x^{2}=7-2\sqrt{10}$
$\Longleftrightarrow (x^{2}-7)^{2}=(-2\sqrt{10})^{2}\Longleftrightarrow x^{4}-14x^{2}+9=0$.

[quote="t0rajir0u"][quote="spix"]I do not think your solution stands as it is not necessary for the coefficent of the rational number to be $0$, neither the coefficent of $\sqrt{10}$ .[/quote]

Actually, it's provable that the members of $\mathbb{Q}[ \sqrt{2}][ \sqrt{5}]$ are distinct.  In other words,

$a, b, c, d \in \mathbb{Q}, a+b \sqrt{2}+c \sqrt{5}+d \sqrt{10}= 0 \Leftrightarrow a = b = c = d = 0$[/quote]

Doesn't proving that the members $Q[\sqrt{2}][\sqrt{5}]$ are independent require more than intermmediate high school knowledge?
If the minimal polynomial has degree 4 and it divides all other polynomials with the root $\sqrt{5}-\sqrt{2}$ (being the minimal one) and our polynomial has max degree 3 (3<4 :) ) then it is the null polynomial.

[quote="spix"]Doesn't proving that the members $Q[\sqrt{2}][\sqrt{5}]$ are independent require more than intermmediate high school knowledge?[/quote]

True.  I prefer the solution by minimal polynomial myself, but I was just pointing out that the other method is also technically valid.

[quote="Altheman"]I see the whole $Q[i]$, etc floating around frequently. Can somebody either explain what that means exactly, or direct me to a source that gives a development of this notation, and common theorems that are associated with it.[/quote]

http://mathworld.wolfram.com/AlgebraicNumberTheory.html
http://mathworld.wolfram.com/QuadraticField.html

Edit:  The notation $F[\alpha]$, to be read "F adjoin alpha," denotes the field/ring generated by the members of the field/ring $F$ and the element $\alpha$.  For example, $\mathbb{Z}[x]$ is the ring of polynomials in $x$ with integer coefficients, and $\mathbb{Z}[x][y]$ is the ring of polynomials in $x, y$ with integer coefficients.

thank you...i was always wondering how that was said exactly...

some thoughts [not posted in that other thread]

when we have something like $Z[i]$, we are really doing something like $a+bi+ci^{2}+di^{3}+...$ but we have repetition, apparently any algebraic number has this property.

perhaps there is a nice way to find teh period? something to with irreducibile polynomials? probably...like in $Z[x]$, $x^{2}+1$ is our minimal polynomial with $i$ as a root

this could make an interesting problem, something like $x=\sqrt{3+2\sqrt{2}}$, we know it is just $1+\sqrt{2}$, but how would we find that in our generation of the minimal polynomial?

$(x^{2}-3)^{2}=8$ is reducible then...this is another interesting way to generate polynomials that reduce into a pair of quadratics...

another comment: the only reason that it sufficies to only consider the minimal polynomial is by using abel's irreducibility theorem
http://mathworld.wolfram.com/AbelsIrreducibilityTheorem.html

[quote="Altheman"]perhaps there is a nice way to find teh period? something to with irreducibile polynomials? probably...like in $Z[x]$, $x^{2}+1$ is our minimal polynomial with $i$ as a root[/quote]

The word you're looking for is "dimension." $\mathbb{Z}[i]$ is a vector space of dimension two over $\mathbb{Z}$, which means that it can be represented by a two-element basis (the vectors $1$ and $i$).  Generally, the dimension of $F[\alpha ]$ corresponds to the degree of the minimal polynomial of $\alpha$ over $F$.

[quote="spix"]Doesn't proving that the members $Q[\sqrt{2}][\sqrt{5}]$ are independent require more than intermmediate high school knowledge?[/quote]
Sure, but the theorems that you know about minimal polynomials do as well.

In general, $F[x]$, where $F$ is a ring (so also acceptable is a field) is the ring generated by $x$ and by the elements of $F$, so has the general form Altheman gave ($a+bx+cx^{2}+\ldots$ where $a, b, c, \ldots$ are elements of $F$ and the sum has finitely many terms).

If we're talking about a field $F$ and $x$ is algebraic over $F$ (so if $F = \bf Q$, then we're asking for $x$ to be an algebraic complex number), $x$ is a root of some minimal polynomial with coefficients in $F$.  The degree of this polynomial is the [i]degree of $x$[/i].  Now, because the minimal polynomial exists, if we keep taking powers of $x$, we eventually stop gaining new information, since larger powers can be written in terms of smaller ones.  In particular, if the minimal polynomial of $x$ is $P(z) = z^{n}+a_{n-1}z^{n-1}\ldots+a_{1}z+a_{0}$ with $a_{n}\neq 0$, then we can write $x^{n}$ in terms of smaller powers of $x$.  By minimality of this polynomial, there is no linear combination of $x^{n-1}, \ldots, x, 1$ over $F$ which gives 0, i.e. $F[x]$ has dimension $n$ over $F$ as a vector space.  It also follows that $F[x] = F(x)$ -- the ring extension of $F$ by $x$ is equal to the extension of $F$ as a field.  In other words, it is possible to write $x^{-1}$ as a polynomial in $x$.  This is [i]not[/i] true of non-algebraic elements: ${\bf Q}[\pi]$ does not contain $\pi^{-1}$ (or lots of other things, like $\frac{1}{\pi^{2}-9}$) which are elements of ${\bf Q}(\pi)$.  When $x$ is algebraic, the same value $n$ is equal to the degree of the field extension $F(x) / F$.


search
number theory solved
number theory

Given two integers $a$ and $b$ s.t. for every natural number $n$, $2^{n}\cdot a+b$ is a square. Prove that $a=0$.

posted before many times - search for it

who confirms?
because it may be that I made a fault


[quote="bpms"][quote="rnwang2"]If candy bars are priced $\$$$0.28$ each how many would you have to buy to make all the digits of the total cost the same?[/quote]
[hide]We need a value of n such that n 1s is divisible by seven. The smallest value of n that works is 6. So our answer is $\frac{4444.44}{.28}=15873$ bars of candy[/hide]I really hope you are rich because I wouldn't buy that many candy bars...[/quote]

Neither would I.

And yeah, that makes sense, since it has to have the same digits, and a factor of that number must have all 1s in it.

Or you could buy 0 bars!
The price would be $0.00! :rotfl:

Good Point, but I honestly think bpms's answer was the one he was looking for.


salam,
prove that, for any quadrilateral with sides a,b,c,d

a²+b²+c²>  (d²/3)

thanks :lol:

[quote="reda"]salam,
prove that, for any quadrilateral with sides $ a,b,c,d$

$ a^2\plus{}b^2\plus{}c^2 >  \frac{d^2}{3}$

thanks :lol:[/quote]

[hide]
We know
$ a\plus{}b\plus{}c>d$ and $ 2(a^2\plus{}b^2\plus{}c^2)\geq 2(ab\plus{}bc\plus{}ca)$
So we get:
$ d^2<(a\plus{}b\plus{}c)^2\equal{}a^2\plus{}b^2\plus{}c^2\plus{}2(ab\plus{}bc\plus{}ca)\leq 3(a^2\plus{}b^2\plus{}c^2)$
[/hide]


wait. 10 PEOPLE GET SCHOLARSHIPS JUST FROM STATES?
-jorian

pfft, like I'm actually going to Purdue.

Not to bash it or anything, it's good for a state school... but yeah right.

I got #5 last year. Pardon me for being "optimistic" and assuming I get in the top 10 at state again. Chances are I get two of these thingies. I wish they'd pay me to go :(.

Anyways, I hope to get 30+ on chapter written and 10+ at states on the written (if I make it)

[quote="13375P34K43V312"][quote="jhredsox"]ok, who said they would get to countdown (7 PEOPLE!!!!!!!), because i think only 3 of you got top 50 at nats

-jorian[/quote]

So, are you saying that just because we didn't come in the top 57 we can't improve and make countdown?

Because you're very wrong if you are.[/quote]

Yeah, people improve a lot over an one year period so its possible.

nononononononono, i think you guys misunderstood me...i just said there's no way that 7 of u are going to go to nats top 12 if like 19 have polled

carl, please don't take offense as i think you're good at math...ok, amazing :)

-jorian

i have a weird feeling I'll get 13 at nats. I did AWFUL last year, and will be at least(if I'm not stupid again-why would they ask for y intercepts when the equation is in the form y=mx+b) top 20. If I have a good day, CD.

I must confess I did. Remember, this poll is about GOALS.

I would have had I had more confidence in my reading under pressure skills...

set realistic goals people. 10 people who think they'll be in countdown so far... :shakes head:
Me personally, county, hopefully states. If I do make it to states, I'll probably get something like 15 on the written, :meh: I don't know how you guys are all so smart to have 10 of you in countdown, you guys are geniuses. I wish I was smart enough to get even top 30 at nats...

I hope I will do a lot better on the real national test. The highest I got on a practice is a 33.

[hide]MY 500TH POST. YANG-MILLS THEORY :wow:  :wow:  :wow: [/hide]

Hey ubemaya! 5th place rox!!!

high five! Same happened to me in Indiana. But my score was 38 :(. Missed the last two targets on dumb errors and changed the last one from right to wrong at the last possible second.

I DIDN'T GET A 41 OR A 5TH PLACE!!!!!!!
At least, I don't think so...  :huh:

[quote="Ubemaya"]In CA the scores were 42, 41, 41, 41. I got a 41 and was 5th :mad:[/quote]

[quote="Ubemaya"]
I DIDN'T GET A 41 OR A 5TH PLACE!!!!!!!
[/quote]

Contradictory information...

By the way, the top quote came from this topic:[url]http://www.artofproblemsolving.com/Forum/viewtopic.php?t=82210[/url]

Yes, Ubemaya stop being a syncophant...I used it in the wrong text...

And guys...your goals should just be to do your best, and improve from last year...

[quote="13375P34K43V312"][quote="bpms"][quote="Ubemaya"]Those are my serious goals.
Who told you that I got a 41 and 5th at CA states?!
What did you get last year?[/quote]
Okay, it is obvious that those aren't your serious goals. No need to lie... You can get higher than your AMC 12 goal by leaving all the questions blank...[/quote]

Lol you're the wrong person to be talking about this considering your sig[/quote]
Hey, I admit that my goals are complete bs...
If you noticed, I increased my amc 8 goal by 10 points the day before we took it...
I also just edited them to be what I think I was capable of exactly two years ago.

Oh, I hated the AMC 8, always made a stupid mistake...mathcounts was fun...got to talk with friends, and it was a great time...our coach was awesome...

[quote="Fanatic"]OH MY GOD that thread brings back memories!

<3 all those people overestimating me. Well I took it as a compliment :).

Anyhow indiana will probably suck this year... might not though. I know a few peeps in my grade that are good at higher level math but not MC.

Oh back on topic...

ummm...

yeah, goals...

if you don't set high goals, don't set any at all.

Discuss.[/quote]
Look at my leet guessing skills
http://www.artofproblemsolving.com/Forum/viewtopic.php?p=475631#475631

Not bad... but 26/12 was right and you guessed 27/12 =/.

If you set a "goal" that's in your words "easy", then you might as well not set it at all.

I'm all confundled now...
what did I get?

[quote="indianamath"]What are you guys's goal in mathocunts this year? For me, I except to go to state and probablay finish top 10 in IN (Top 10 gets full-ride scholarships to Purdue). If I'm lucky and do good maaaayyybbbeee ill get to Nats. :D[/quote]

Those are the same goals I have. (top 10 at IN)

BTW, what is your name?

my "goal" is to win.  however, with that being veeeeery unlikely, I will try and make it to nats.  this is my first year doing MathCounts  :D


[quote="Jumbler"]Let $f(x) = x(x-1)(x-2)...(x-2006)$. Find $f'(2006)$[/quote]
 I think $f' ( 2006 ) = 0$. Maybe I was wrong. Thax.


inequalities
induction
function
inequalities unsolved

Real numbers $a_{1},a_{2},\dots,a_{n}$ satisfy $a_{i}\geq\frac{1}{i}$, for all $i=\overline{1,n}$. Prove the inequality:
\[\left(a_{1}+1\right)\left(a_{2}+\frac{1}{2}\right)\cdot\dots\cdot\left(a_{n}+\frac{1}{n}\right)\geq\frac{2^{n}}{(n+1)!}(1+a_{1}+2a_{2}+\dots+na_{n}).\]

HI, prowler! I have made the substitutions. However, I didn't use induction! I have considered the expression as a linear function in $x_{1}$ with positive "leading coefficient" (that is, an increasing linear function on $[1,\infty)$. So $x_{1}=1$. Repeating this step for each $i$ we get $x_{1}=x_{2}=\dots=x_{n}=1$.
Good luck!

Let just induct
Obviously, the inequality should hold for $n=1$. Assume it holds for $n=k$. We will prove it holds for $n=k+1$.
Consider \[ LHS=\left(a_{1}+1\right)\left(a_{2}+\frac{1}{2}\right)\cdots\left(a_{n}+\frac{1}{n}\right)\left(a_{n+1}+\frac{1}{n+1}\right)\geq\frac{2^{n}}{(n+1)!}(1+a_{1}+2a_{2}+\dots+na_{n})\left(a_{n+1}+\frac{1}{n+1}\right) \] We will prove that \[ \begin{aligned} (1+a_{1}+2a_{2}+\dots+na_{n})\left(a_{n+1}+\frac{1}{n+1}\right) & \geq\frac{2}{n+2}(1+a_1+2a_2+\cdots+na_n)+\frac{2(n+1)a_{n+1}}{n+2}\\
\Leftrightarrow (1+a_{1}+2a_{2}+\dots+na_{n})\left(\frac{(a_{n+1}(n+1)(n+2)+n+2-2n-2}{(n+1)(n+2)}\right) & \geq\frac{2(n+1)a_{n+1}}{n+2}
\end{aligned}  \] By the given condition, we have $LHS\geq\frac{a_{n+1}(n+1)(n+2)-n}{n+2}$. From here, by simple algebraic manipulation, we got $a_{n+1}\geq\frac{1}{n+1}$, which is true.


function
vector
topology
real analysis
real analysis unsolved

If
$f: \mathbb{R}^{n}\to \mathbb{R}^{n}$ diferentiable then for any open set $E\subset \mathbb{R}^{n}$
the set
$\{x\in \mathbb{R}^{n}|f'(x)\in E\}$ is empty or has positive measure.

[quote="fedja"]Should it be $f : \mathbb R^{n}\to \mathbb R$?[/quote]

$f=(f_{1},f_{2},...,f_{n}), f_{i}: \mathbb{R}^{n}\to R, i=\overline{1,n}$ are differentiable. $f'(x)=(f_{1}'(x),f_{2}'(x),...,f_{n}'(x))$ where
$f_{i}'(x)$ means the diffrerentials value in $x=(x^{1},x^{2},...,x^{n})$.

But the differential of each function $f_{i}: \mathbb R^{n}\to \mathbb R$ is already a vector of $n$ partial derivatives. So it should be either $f : \mathbb R^{n}\to \mathbb R$, or $f : \mathbb R\to\mathbb R^{n}$, or $E\subset \mathbb R^{n^{2}}$. Each of those would make sense but as wrtitten, something is wrong.


calculus
trigonometry
geometry unsolved
geometry

It is given triangle ABC with points M, N, P on its sides (internally). U, V, W are intersection points of AN and CM, BP and AN, CM and BP. Triangle UVW is equaliteral. If BM=CN=AP is it true that ABC is equaliteral?

1. If it is possible - try to solve the problem without the approch shown by fedja.
2. If you are interested of such kind of problems I may post one problem weekly.
3. May somebody post the exact text of the problem that appeared at Indian TST 2008?
4. I still have a problem not solved from years on many forums do you want to see it?

[quote="borislav_mirchev"] try to solve the problem without the approach shown by fedja[/quote]
For those who are new here or just forgot what it was, borislav is referring to [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=214127]this[/url].

I asked for solution without calculus, because I saw two solutions using trigonometry of my first similar problem. It was given on Romanian TST 1993. I didn't know that before inventing the problem.

If it is possible ... try to find any solution ... as it seems it is not an easy problem at all.


analytic geometry
graphing lines
slope
LaTeX

:rotfl:

(Just did that for fun)

Find the equation that has x-intercept (-3,0) and y-intercept (0,4) without finding the slope first.

Answer:

[hide]This can be written as:

\[\frac {x}{a} + \frac {y}{b} = 1\]
\[a \neq  0, b \neq 0\]
\[\frac {x}{-3} + \frac {y}{4} = 1\]
\[4x-3y = -12\]
\[-3y = -4x-12\]
\[y =\frac {4}{3}x + 4\][/hide]

[quote="Silverfalcon"]:

This can be written as:

\[\frac {1}{a} + \frac {1}{b} = 1\]
\[a \neq  0, b \neq 0\]
[/quote]

????

He meant $\frac{x}{a} + \frac{y}{b} = 1$.

Sorry about that.

I had problem with Latex before posting this (problem with margins and other some weird stuffs) so I messed up with the Latex.

Thanks for pointing out.

Fixed.

is this topic included in linear algebra?  if not what would i find it under.  I seemed to have missed this during my studies


Is the following correct?

\[ (|x|^{p\minus{}2}x\minus{}|y|^{p\minus{}2}y)(x\minus{}y)\ge C_p|x\minus{}y|,\] where $ p\ge 2,$ $ C_p$ only depends on $ p$ and is independent of $ x,y\in\mathbb{R}.$

Homogeneity does not match? If you multiply both $ x$ and $ y$ by the same positive number $ \lambda$, the left side gets multiplied by $ \lambda^p$, the right side by $ \lambda$. So it can't work.

Did you mean to put $ |x\minus{}y|^p$ on the right? Then the answer would be yes. Even in $ \mathbb R^n$, and for any $ p>1$.

[quote="mlok"]Homogeneity does not match? If you multiply both $ x$ and $ y$ by the same positive number $ \lambda$, the left side gets multiplied by $ \lambda^p$, the right side by $ \lambda$. So it can't work.

Did you mean to put $ |x \minus{} y|^p$ on the right? Then the answer would be yes. Even in $ \mathbb R^n$, and for any $ p > 1$.[/quote]

Thank you very much. You are right that if the right-hand side is $ |x \minus{} y|^p$, then the inequality holds for $ p > 1$.


integration
limit
function
real analysis
real analysis unsolved

Let $ F: (1, +\infty) -> R$

$ F(x) = \int\limits_{x}^{2x} \frac{t}{ln \ t} dt$
      $ x>1$.

a) Prove, that:
 $ \lim_{x\to\11^{+}} F(x)=+\infty$ and $ \lim_{x\to\++\infty} F(x)=+\infty$.

b) Show that there exist a point $ x_{0}>1$ such as $ F(x_{0})$ is the smalles value on the ray $ (1, +\infty)$. Find $ x_{0}$

Hi :) !!

Our function is : $ \int_x^{2x} \frac {t}{ln(t)}dt \qquad \forall x \succ 1$

a)  Let $ x \succ 1$ :

1) see that $ \forall t \; ln(t) \leq t \minus{} 1 \Rightarrow F(x) \succ x \plus{} ln \left| \frac {2x \minus{} 1}{x \minus{} 1} \right|$

than :

$ \lim_{x \to 1^ \plus{} } F(x) \equal{} \plus{} \infty$

2) see also that $ \forall x \succ 1 \; \frac {x^2}{ln(2x)} \leq F(x) \leq \frac {2x^2}{ln(x)}$

than: $ \lim_{x \to \plus{} \infty}F(x) \equal{} \plus{} \infty$

i will be bach for b)

thanks


Let ABC be an acute triangle, in which $ \angle BAC$ is the smallest. Prove that there exists such point P inside the triangle, that $ \angle ABP \equal{} \angle ACP \equal{} \alpha$ and $ \angle BAC \equal{} \pi \minus{} 3 \alpha$

this is equivalent to showing that $ \angle ABC$ and $ \angle ACB$ are both $ >\alpha$. but that's false: for example, let $ \alpha \equal{} 55^{\circ}$ and the three angles be $ m\angle ACB \equal{} 54^{\circ}, m\angle ABC \equal{} 111^{\circ}, m\angle BAC \equal{} 15^{\circ}$.

i can give a specific example...take P as the orthocenter..then angle BAC = 45 = alpha...and BTW i assume the Q talks about only those triangles where such a case is possible...obviously the value of alpha depends on the value of the angles of triangle..u cant fiz an alpha and then the angles of triangle..n BTW then u may say take ABC = 2 degree BAC=1 degree and ACB=177 and alpha = 55

doesnt work that way

[quote="sahilsharma94"]u cant fiz an alpha and then the angles of triangle..n BTW then u may say take ABC = 2 degree BAC=1 degree and ACB=177 and alpha = 55

doesnt work that way[/quote]

i don't think you know what you're talking about here. the value of $ \alpha$ is determined by the triangle $ ABC$, and for a triangle with angles $ 15, 54, 111$, $ \alpha$ must be 55, in which case the statement is clearly false.

oh..sorry for the mistake..so the Q doesnt hold for all acute angled triangles

oops, didn't see that it said acute :oops:

in that case, it *is* true. so again, we have to prove that $ B, C$ are both bigger than $ \alpha$.

assume that $ B\leq \alpha$. then $ 180\minus{}3\alpha \equal{} A \leq B \leq \alpha$, so $ \alpha \geq 45$. but then $ C\geq 2\alpha \geq 90$, contradiction.

yea..and then ppl are out to proove others wrong  :P  :oops:


Can methyl groups shift from anywhere on a molecule to form a more stable carbocation or only from nearby carbons? For example, if we have a decane and the carbocation and methyl groups are on opposite ends, does methyl shift still occur?

Such rearrangements occur more readily when the carbons are neighbours. In your example, of a decane, a hydride shift would occur to form a secondary carbocation.

Shifts always occur so as to form a more stable carbocation. Wrt your doubt, methyl shifts take place in steps. Yes, in case of decane, if there are 2 methyl groups on the second carbon (numbered) then the + will shift toward it and you will get a 3-degree carbocation no matter what the initial position of the + was.


inequalities
logarithms
inequalities unsolved

Given three reals $ x$, $ y$, $ z$ which are all $ \geq 1$, prove that

$ x^{x^2\plus{}2yz} \cdot y^{y^2\plus{}2zx} \cdot z^{z^2\plus{}2xy}\geq (xyz)^{xy\plus{}yz\plus{}zx}$.

Given reals $x,y,z>=1$, prove that

$x^{x^2+2yz} \cdot y^{y^2+2zx} \cdot z^{z^2+2xy}>=(xyz)^{xy+yz+zx}$

Looks like it can be done by dividing through by the right hand side, obtaining

$x^{(x-y)(x-z)}y^{(y-z)(y-x)}z^{(z-x)(z-y)} \ge 1$

which is symmetric; hence, we assume WLOG $x \ge y \ge z \ge 1$, and it follows easily.

[quote="Mildorf"]$x^{(x-y)(x-z)}y^{(y-z)(y-x)}z^{(z-x)(z-y)} \ge 1$[/quote]A more sophisticated way of saying the same thing as Mildorf is to take the logarithm of both sides and to apply the Vornicu-Schur inequality  :)

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=24555]http://www.artofproblemsolving.com/Forum/viewtopic.php?t=24555[/url]  post #9

You got out of our subject! The solution is: We use logarithms and then we use the inequality of Tschebychev. Then we use  (x+y+z)^2>=3( xy+yz+zx) Thats a good solution! Right?

siloan, why did she get out of the subject? The inequalities are equivalent. I don't htink you should limit others' thinkings.
monique, I'm sorry that you are wrong. It's because you cannot guarantee $ln x$ \ge 0. We need all x,y,z to be positive in vornicuschur.

[quote="Monique"][quote="siuhochung"]I'm sorry that you are wrong. It's because you cannot guarantee $ln x$ \ge 0. We need all x,y,z to be positive in vornicuschur.[/quote] In the hypotheses given by silouan, it was explicitly stated that $x,y,z\geq 1$, which implies $\log\ldots\geq 0$. Otherwise, Mildorf's proof would fail too![/quote]
oops, i didn't read that, then you are right. Congratulations.


F=A-apollonius circle
E=circumcircle
D=intersection of E and F
Prove that AD is A-symmedian.

Is this not-good problem ? If so, I will feel miserable.  :)
Thank you for reading my post. Happy New Year !

let the A-apollonius circle touch BC internaly on R and esternaly on T. Let the tangent to the circumcircle at A meet BC on F'. Then $ \angle RAF' \equal{} \angle RAC \plus{}  \angle CAF' \equal{} \angle RAB \plus{} \angle ABC \equal{} \angle ARC$ so $ F' \equiv F$. Then A-apollonius circle anf the circumcircle are orthogonal circle, then the tangent to the circumcircle at A meet the tangent to the circumcircle at D on F, then BF is the B-symmedian of $ \triangle BAD$, so the quadrilateral ABDC is and harmonic quadrilateral and so AD is the A-symmedian of $ \triangle ABC$.

Dear Mathlinkers,
for a synthetic proof see :
http://perso.orange.fr/jl.ayme    contenu : vol. 2  La fascinante figure de Cundy p.5.
Sincerely
Jean-Louis

Since $ D$ is on A-apollonius circle, we have $ \frac{AB}{AC}\equal{}\frac{DB}{DC}$.Also, $ D$ lie on circumcircle of $ ABC$. It follows that tangent lines at $ B,D$ and $ AD$ are concurrent. Hence $ AD$ is symmedain.


The whole numbers 11 through 19 are arranged in the squares shown so that the sum of the numbers in each row, column and diagonal is the same. What is the common sum?

[asy]for(int i = 0; i < 4; ++i){
draw((0,i)--(3,i)); draw((i,0)--(i,3));
}[/asy]

Let the common sum be $ S$.  Then, adding up all the columns gives us $ 3S$, and it is also the sum of all the number used.  So \[ 3S\equal{}11\plus{}12\plus{}13\plus{}\cdots \plus{}18\plus{}19\Rightarrow S\equal{}\boxed{45}\]


trigonometry
function
real analysis
real analysis unsolved

$m(x)=\sin (\sum_{k=0}^{1000}\frac{(2k)!}{2^{2k}(k!)^{2}}\frac{x^{2k+1}}{2k+1} )$

Give asymptotic expansion around $0$ at order $2005$

or if you prefer find $a_k$ such that

$m(x)=\sum_{k=0}^{2005}a_kx^k+o(x^{2005})$  when $x$ is near $0$

[quote="Moubinool"]No answer ?[/quote] [hide="Hint"] The argument of the $\sin$ function is just a partial sum for the Taylor series of the $\arcsin$ function [/hide]


I recently wrote a math contest for my school and one of the questions that stumped me was this question regarding the amount of equilateral triangles on a chinese checker board.
http://img149.imageshack.us/img149/9647/chineseln7.th.jpg
Edit: the diagram depicted was is not exactly the one showed on the test, the diagram shown here has 9 triangles along each side while the one on the test has 15.

To say the least I had no idea how to approach that question and just out of curiousity's sake I posted it here wondering if some of you know how to solve this question?
The question is asking how many equilateral triangles are there on that board of chinese checkers.

Any input would be appreciated to cure my curiousity.

There is probably a more elegant method for the general case involving a bijection method, and this is what you should be interested in, but I would just do a casebash, as I can't remember any good techniques and the board shape is hard to generalize to. The trick is to find a method to could all the triangles quickly enough. The single ones are fairly easy, and I would split the further cases into ones facing up and facing down. I think because of the symmetry they are equal, so only count the ones facing upwards. Then you biject each triangle to its lower lefthand point, and count all the points that produce valid triangles. Repeat for longer sides, etc. A pattern should emerge after a few tries which would allow you to sum the series quickly...

But that is just speculation. I don't think there is a quick, pretty way to do this problem because of the odd shape.

I guess one should approach the problem in this way- Any equilateal trinagle in this figure should have a two-power no. of smaller triangles.


function
superior algebra
superior algebra unsolved

Hi
I am interested in numbertheoretic functions

I heard that in the dirichlet ring, a multiplicative function, with f(1) nonzero, has a multiplicative inverse

why is this inverse multiplicative?
is there a simple argument?

If $f$ is multiplicative then it is determined by its values on prime powers $p^a$.  If $f(1) \not=0$ then it is $=1$.  Let $g$ be a possible inverse for $f$: that is, $\sum_{d\mid n} f(d)g(n/d) = 1$ if $n=1$ otherwise $0$.  We determine what $g$ has to be on $p^a$ by assuming $g(p^i)$ known for $i<a$ and writing $0 = \sum_{i=0}^a g(p^i) f(p^{a-i})$ which expresses $g(p^a)$ in terms of previously determined values.

Did you prove existence of an inverse now, or multiplicativity of the inverse?

I showed how to construct a candidate function $g$ for for being an inverse of $f$: it's multiplicative because I defined it on prime powers and extended to all positive integers by multiplicativity.  You still need to show (i) that is is well-defined (ii) that it is an inverse to $f$.  Once done this shows that $f$ has a unique multiplicative inverse.  You should then show that the inverse of $f$ is unique even when not restricted to multiplicative functions only.

I'm sorry, but I still don't understand any of this?
Can anyone help?

Im curious, what is not clear about the above¿  :?

Another way would be to define the inverse for all, not only prime powers, as above and then directly to show multiplicativity. That's really just use of that definition and multiplicativity of the original function (don't forget that $f(1)=1$) connected with some easy term-rearrengement.


inequalities
geometric sequence
algebra proposed
algebra

Find the maximal constant $ M$, such that for arbitrary integer $ n\geq 3,$ there exist two sequences of positive real number $ a_{1},a_{2},\cdots,a_{n},$ and $ b_{1},b_{2},\cdots,b_{n},$ satisfying
(1):$ \sum_{k \equal{} 1}^{n}b_{k} \equal{} 1,2b_{k}\geq b_{k \minus{} 1} \plus{} b_{k \plus{} 1},k \equal{} 2,3,\cdots,n \minus{} 1;$
(2):$ a_{k}^2\leq 1 \plus{} \sum_{i \equal{} 1}^{k}a_{i}b_{i},k \equal{} 1,2,3,\cdots,n, a_{n}\equiv M$.

[quote="mathangel"]I don't understand the problem

Why is the first summation from i=1 to n and what the second sum means ?[/quote]

That's just a typo, i.e. the

$ \sum_{i\equal{}1}^n b_k\equal{}1$

should be

$ \sum_{k\equal{}1}^n b_k\equal{}1$

Others are correct.

Thank you for correcting my mistake, Dear shalex.

[quote="joao1"]Is the answer M=3/2?[/quote]
Yeah! :)

Can any Chinese Mathlinkers post the solution of this problem?I waited it for a long time. :oops:

The proposer of this problem is Professor Li Weigu from Peking University.

my solution:
If all $ b_{i} (1\le i \le n)$ are given, it is trivial that $ a_{n}$ reaches its maxim al value iff all inequalities in condition (2) are equalities.In other word, w.l.o.g we can assume all inequalities in condition (2) are equalities.

Compare the condition (2) of k and k-1 we get $ a_{k}^2-a_{k-1}^2=a_{k}b_{k}$ for k=0,1,…,n-1 (In order to make it convenient we let $ a_{0}$=1
Then we can get $ a_{k}=(b_{k}+\sqrt {b_{k}^2+4a_{k-1}^2})/2$
Since $ \sqrt {b_{k}^2+4a_{k-1}^2} > 2a_{k-1}$, we have $ a_{k}=(b_{k}+\sqrt {b_{k}^2+4a_{k-1}^2})/2 > (b_{k}+2a_{k-1})/2=a_{k-1}+\frac {b_{k}} {2}$.
So $ a_{n} > a_{0}+\frac {\sum_{i=1}^{n} b_{i}} {2}=1+1/2=3/2$, which mean $ M=3/2$ satisfies the condition.

On the other hand, since $ a_{i}$ is increasing and $ a_{1} > 1$,we have $ a_{i} > 1$, so $ a_{k-1}b_{k}^2 > b_{k}^2$ for every k.
Thus $ \sqrt {b_{k}^2+4a_{k-1}^2} < \frac {b_{k}^2}{4}+2a_{k-1}$ and $ a_{k}=(b_{k}+\sqrt {b_{k}^2+4a_{k-1}^2})/2 < \frac {b_{k}+\frac {b_{k}^2}{4}+2a_{k-1}}{2}=a_{k-1}+\frac {b_{k}}{2}+\frac {b_{k}^2}{8}$
So $ a_{n}<a_{0}+\frac {\sum_{i=1}^{n} b_{i}} {2}+\frac {\sum_{i=1}^{n} b_{i}^2} {8}=3/2+\frac {\sum_{i=1}^{n} b_{i}^2}{8}$

Next we prove that $ \sum_{i=1}^{n} b_{i}^2$ can be arbitrarily small.

Assume $ n=2m$(m is a positive integer).Since 2$ b_{k}\ge b_{k - 1} + b_{k + 1},k = 2,3,\cdots,n - 1$, it is easy to prove for $ 1<x<y<n$, $ b_{x-1}+b{y} \ge b_{x}+b{y-1}$.So for $ 1\le i \le m$, $ b_{i}+b_{2m} \le b_{i+1}+b_{2m-1} \le \cdots \le b_{[\frac {i+2m}{2}]-1}+b_{i+2m+1-[\frac {i+2m}{2}]}$.
There are at least $ \frac {m-1}{2}$ terms in the former inequality links, so $ b_{i} < b_{i}+b_{2m} <\frac{\sum_{j=i}^2m b_j}{\frac {m-1}{2}}<\frac {1}{\frac {m-1}{2}=\frac {2}{m-1}$.i.e. for $ 1\le i \le m$, $ b_{i} < \frac {2}{m-1}$. For the same reason for $ m+1\le i \le 2m$, $ b_{i} < \frac {2}{m-1}$
Thus $ \sum_{i=1}^{n} b_{i}^2 < 2m(\frac {2}{m-1})^2=\frac {8m}{(m-1)^2}$, and for m is an arbitrary positive integer $ \frac {8m}{(m-1)^2}$ can be arbitrarily small.
Combined with $ a_{n}<3/2+\frac {\sum_{i=1}^{n} b_{i}^2}{8}$ we get $ M$ can not be greater than 3/2.So the the maximal constant $ M$ is 3/2
Q.E.D

PS: it pissed me for a long time because during the test I came up with this solution but failed for a extremely stupid reason. Right after I got $ a_{n}<3/2+\frac {\sum_{i=1}^{n} b_{i}^2}{8}$, of course I would guess whether $ \sum_{i=1}^{n} b_{i}^2$ can be arbitrarily small. I decided to take a set of special $ b_{i}$ to check it. Unfortunately I took $ b_{i}$ as a geometric progression which contradicts the condition (1)! And the result was that $ \sum_{i=1}^{n} b_{i}^2$ is about 1/3. This mistake cost me a lot of time and made me unable to guess the answer.Partly as a result I didn't make myself into the six members of the China team last year.

[quote="linboll"]The proposer of this problem is Professor Li Weigu from Peking University.

my solution:
If all $ b_{i} (1\le i \le n)$ are given, it is trivial that $ a_{n}$ reaches its maxim al value iff all inequalities in condition (2) are equalities.In other word, w.l.o.g we can assume all inequalities in condition (2) are equalities.

Compare the condition (2) of k and k-1 we get $ a_{k}^2 \minus{} a_{k \minus{} 1}^2 \equal{} a_{k}b_{k}$ for k=0,1,…,n-1 (In order to make it convenient we let $ a_{0}$=1
Then we can get $ a_{k} \equal{} (b_{k} \plus{} \sqrt {b_{k}^2 \plus{} 4a_{k \minus{} 1}^2})/2$
Since $ \sqrt {b_{k}^2 \plus{} 4a_{k \minus{} 1}^2} > 2a_{k \minus{} 1}$, we have $ a_{k} \equal{} (b_{k} \plus{} \sqrt {b_{k}^2 \plus{} 4a_{k \minus{} 1}^2})/2 > (b_{k} \plus{} 2a_{k \minus{} 1})/2 \equal{} a_{k \minus{} 1} \plus{} \frac {b_{k}} {2}$.
So $ a_{n} > a_{0} \plus{} \frac {\sum_{i \equal{} 1}^{n} b_{i}} {2} \equal{} 1 \plus{} 1/2 \equal{} 3/2$, which mean $ M \equal{} 3/2$ satisfies the condition.

On the other hand, since $ a_{i}$ is increasing and $ a_{1} > 1$,we have $ a_{i} > 1$, so $ a_{k \minus{} 1}b_{k}^2 > b_{k}^2$ for every k.
Thus $ \sqrt {b_{k}^2 \plus{} 4a_{k \minus{} 1}^2} < \frac {b_{k}^2}{4} \plus{} 2a_{k \minus{} 1}$ and $ a_{k} \equal{} (b_{k} \plus{} \sqrt {b_{k}^2 \plus{} 4a_{k \minus{} 1}^2})/2 < \frac {b_{k} \plus{} \frac {b_{k}^2}{4} \plus{} 2a_{k \minus{} 1}}{2} \equal{} a_{k \minus{} 1} \plus{} \frac {b_{k}}{2} \plus{} \frac {b_{k}^2}{8}$
So $ a_{n} < a_{0} \plus{} \frac {\sum_{i \equal{} 1}^{n} b_{i}} {2} \plus{} \frac {\sum_{i \equal{} 1}^{n} b_{i}^2} {8} \equal{} 3/2 \plus{} \frac {\sum_{i \equal{} 1}^{n} b_{i}^2}{8}$

Next we prove that $ \sum_{i \equal{} 1}^{n} b_{i}^2$ can be arbitrarily small.

Assume $ n \equal{} 2m$(m is a positive integer).Since 2$ b_{k} \ge b_{k \minus{} 1} \plus{} b_{k \plus{} 1},k \equal{} 2,3,\cdots,n \minus{} 1$, it is easy to prove for $ 1 < x < y < n$, $ b_{x \minus{} 1} \plus{} b_{y} \ge b_{x} \plus{} b_{y \minus{} 1}$.So for $ 1\le i \le m$, $ b_{i} \plus{} b_{2m} \le b_{i \plus{} 1} \plus{} b_{2m \minus{} 1} \le \cdots \le b_{[\frac {i \plus{} 2m}{2}] \minus{} 1} \plus{} b_{i \plus{} 2m \plus{} 1 \minus{} [\frac {i \plus{} 2m}{2}]}$.
There are at least $ \frac {m \minus{} 1}{2}$ terms in the former inequality links,

 so $ b_{i} < b_{i} \plus{} b_{2m} < \frac{ \sum_{j \equal{} i}^{2m} b_j }{ \frac{m \minus{} 1}{2} } < \frac{1}{\frac{m \minus{} 1}{2}} \equal{} \frac{2}{m \minus{} 1}$.i.e. for $ 1\le i \le m$, $ b_{i} < \frac {2}{m \minus{} 1}$. For the same reason for $ m \plus{} 1\le i \le 2m$, $ b_{i} < \frac {2}{m \minus{} 1}$
Thus $ \sum_{i \equal{} 1}^{n} b_{i}^2 < 2m(\frac {2}{m \minus{} 1})^2 \equal{} \frac {8m}{(m \minus{} 1)^2}$, and for m is an arbitrary positive integer $ \frac {8m}{(m \minus{} 1)^2}$ can be arbitrarily small.
Combined with $ a_{n} < 3/2 \plus{} \frac {\sum_{i \equal{} 1}^{n} b_{i}^2}{8}$ we get $ M$ can not be greater than 3/2.So the the maximal constant $ M$ is 3/2
Q.E.D

PS: it pissed me for a long time because during the test I came up with this solution but failed for a extremely stupid reason. Right after I got $ a_{n} < 3/2 \plus{} \frac {\sum_{i \equal{} 1}^{n} b_{i}^2}{8}$, of course I would guess whether $ \sum_{i \equal{} 1}^{n} b_{i}^2$ can be arbitrarily small. I decided to take a set of special $ b_{i}$ to check it. Unfortunately I took $ b_{i}$ as a geometric progression which contradicts the condition (1)! And the result was that $ \sum_{i \equal{} 1}^{n} b_{i}^2$ is about 1/3. This mistake cost me a lot of time and made me unable to guess the answer.Partly as a result I didn't make myself into the six members of the China team last year.[/quote]

Let me give another approach to bound $a_n$ from above: as linboll pointed out we may assume $a_k^2-a_{k-1}^2=a_kb_k$ for $1\leq k \leq n$ (where $a_0=1$), that is
\[a_1-1=\frac{a_1}{a_1+1}b_1,a_2-a_1=\frac{a_2}{a_2+a_1}b_2,...,a_n-a_{n-1}=\frac{a_n}{a_n+a_{n-1}}b_n.\]
Also it's not hard to show that (1) implies $b_k\leq\frac{2}{n-1}(1\leq k \leq n)$. Then we have
\[2a_n-3=\sum_{k=1}^n[2(a_k-a_{k-1})-b_k]=\sum_{k=1}^n\frac{a_k-a_{k-1}}{a_k+a_{k-1}}b_k\leq\sum_{k=1}^n\frac{a_k-a_{k-1}}{n-1}=\frac{a_n-1}{n-1},\]
i.e. $a_n\leq\frac{3}{2}+\frac{1}{4n-6}$. Thus $M\leq\frac{3}{2}$.


[hide]Writing this in exponential notation, we see $x^{-2}=\frac{9}{16}$.  So from this we can see that $x=\frac{4}{3}$.[/hide]
[hide]Writing this in exponential notation, we see $x^{-3}=\frac{27}{8}$.  So from this we can see that $x=\frac{2}{3}$.[/hide]

[quote="Silverfalcon"]Two easy logarithrm problems.

1. The value of $x$ for which $\log_x \frac{9}{16} = -2$ is what?

2. The value of $x$ in the equation $\log_x \frac{27}{8} = -3$ is what?

Very similar. Enjoy. :)[/quote]

[hide="1"]$x^{-2}=\frac{9}{16}$

$x^2=\frac{16}{9}$

$x=\frac{4}{3}$[/hide]

[hide="2"]$x^{-3}=\frac{27}{8}$

$x^3=\frac{8}{27}$

$x=\frac{2}{3}$[/hide]

[hide]x^-2=9/16. This can be rearranged to x^2=16/9. Then the square root of 16/9 = 4/3, which ='s X.[/hide]

[hide]x^-3=27/8. This can be rearranged to x^3=8/27. Then the cube root of 8/27 = 2/3, which ='s X.[/hide]


IMO, IOI, summer games are all in Greece?  dont tell me the physics, bio, chem olympiad are all in greece also?

http://news.yahoo.com/news?tmpl=story&u=/ap/20040309/ap_on_sp_ol/oly_greece_government_4

=.= I was wondering why IOI is in Sept this year

Physics is in Korea this year. Don't know about bio, chem.

The IOI is in Sept because they are using facilities being built for the Olympic Games, so they have to schedule it for after the games are over.

yeah, thats what i figured...  had i chance to taste greek food.  yuck :(  (my excuse of not making the teams ;))

it will be interesting to see if the late date affects who is available for this year's team. Two of the people who were on last year's team are now seniors. Going to the IOI in Sept would mean taking 10 days off from college just as their freshman year is getting going. Ouch! That would be hard to recover from.


number theory
least common multiple
number theory unsolved

$ 2^{n - 1} = \sum_{i = 0}^{n - 1}{\binom{n - 1}{i}} < n.\binom{n - 1}{[\frac {n - 1}{2}]}$.
We necessary proof ${ n\binom{n - 1}{k}}|lcm(n,n - 1,n - 2,. . .,n - k)$.
Indeed, assume $ p^{\alpha}$ is a divisor of $ lcm(n,n - 1,n - 2,. . .,n - k)$ then $ p^{\alpha}|n - l$, for some $ l$.
So easy proof ${ n\binom{n - 1}{k}}$ not is divisible by $ p^{\alpha + 1}$.


geometry
analytic geometry
graphing lines
slope
geometry proposed

[color=darkred]Let $A,B,C,D,E$ be fixed collinear points and let $\delta$ be a mobile line so that $A\in\delta$. For the mobile points $\{M,N\}\subset\delta$

denote $\{\begin{array}{c}U\in BM\cap DN\\\ V\in CM\cap EN\end{array}$. Prove that the line $UV$ passes through a fixed point. Study some particular remarkable cases.

[b]Remark.[/b] This problem has three degrees of freedom : the slope of the mobile line $\delta$ and for each mobile point $M\in \delta$ or $N\in\delta$ one from coordinates is free.[/color]

Consider a central proiection which put  line AMN to infty.
Then $B'U' \parallel C'V'$ and $D'U' \parallel E'V'$.
Let $S'=U'V' \cap B'D'$. Then $\frac{S'B'}{S'C'}=\frac{B'U'}{C'V'}=\frac{B'D'}{C'E'}$.
$\Leftrightarrow \frac{SC}{CE}*\frac{EA}{SA}=\frac{SB}{BD}*\frac{DA}{SA}\Leftrightarrow \frac{SB}{SC}=\frac{EA}{CE}*\frac{BD}{DA}$.So $S$ is fixed.


[quote="Iversonfan2005"][quote="José"][quote="Iversonfan2005"]the midpoint $E$ shows that $[\triangle{AEC}]=[\triangle{AEB}]$ (same base value, share the same altitude), so therefore, $[\triangle{APD}]=\boxed{3}$[/quote]

Not sure Iversonfan2005, $A,P,E$ are not necesairly collinear[/quote]

oh oops, didn't read the question carefully :blush: didn't see that P is an arbitrary point..heh

that makes the question a bit tougher now doesn't it ;)[/quote]

Yeah, but see if you can solve it.... you surely can

[quote="xxxyyyy"]In triangle ABC, D, E and F are the midpoints of AB, BC and CA respectively. An arbitrary point P in the interior of the triangle is connected to A, D, E and F by straight lines. The area of PFA is 5, of PECF is 20 and of PDBE is 22 as shown in the figure. What is the area of PAD?

PS: If the moderator feel that this problem does not fit here, please move it to the relevant section.[/quote]

[hide]
Extend P to C, B, and A. Because D, E, and F are midpoints, $\triangle PFA = \triangle PFC=5$, $\triangle PDA = \triangle PDB=7$, $triangle PEC = \triangle PED = 15$.

Thus $PAD = 7$[/hide]

[quote="Iversonfan2005"][quote="xxxyyyy"][quote="Iversonfan2005"]The answer is $7$. what you do is make triangles with all the line segments and use the same reasoning with medians..be back w/ diagram.[/quote]

can you provide explanation for your answer? It would a great help to me.

Thanks ![/quote]

In the diagram, each of those line segments for each triangle is the median, and the median splits the triangle into two equal areas. Essentially, it's the same thing agolsme did.[/quote]

Thanks, I got it now.


#4 Circles of radius 3 and 6 are externally tangent to each other and are internally tangent to a circle of radius 9.  The circle of radius 9 has a chord that is a common external tangent of the other two circles.  Find the square of the length of this chord.

[hide]
sorry about all these points.
I thought that the circles with radius 3 and 6 have diameters that are two segments of the the diameter of the radius 9 circle.
here, AD = AB = CI = GJ = BJ = HK = 3
DE = BD = BF = 6
AF = AE = AX = 9
we see that triangle KCA is similar to JCB since AH and BG are parallel.
then CJ = GI = $6\sqrt{2}$
then $\frac{BC}{AC} = \frac{CJ}{CK} = \frac{BJ}{AK} = 3/2$
AK = 2, AH = AK + HK = 5, HX = HY = $\sqrt{9^2-5^2} = 2\sqrt{13}$
$(XY)^2 = 56 * 4 = 224$
i hope this makes sense

[/hide]
EDIT: click on the picture for better quality


Just thought I'd share this with everyone: I recently learned that Mathematica expressions can be converted directly to Latex code.  First enter the expression in Mathematica (I generally use the Basic Palette and keyboard codes). Then choose the expression, then choose Edit/Copy As/Latex.  This copies the code to the clipboard in Latex format.  Just paste it now.   For example, I entered the following code in AoPS recently and the only Latex code I directly typed were the dollar signs, some \begin{align} and a little re-formatting.  The advantage of doing it this way is that you can see directly how the code will look since the Mathematica front end displays it similar to how it looks below (minus align).  Also, you avoid any typing errors when inputting Latex which can be tedious to troubleshoot when the code is long.  Often too I work with the code in Mathematica anyway so have most of it already input.

\[ \begin{align*}
\sum _{k\equal{}0}^{\infty } \sum _{j\equal{}0}^k \frac{(j\plus{}1) (\minus{}1)^{k\minus{}j} (\pi  i)^{2k\minus{}j\plus{}2}}{2^{k\minus{}j\plus{}1}(2\plus{}k)!}&\equal{}\sum _{k\equal{}0}^{\infty } \left\{\frac{(\minus{}1)^k(\pi  i)^{2k\plus{}2}}{2^{k\plus{}1} (2\plus{}k)!} \sum _{j\equal{}0}^k \frac{(j\plus{}1) 2^j}{(\minus{}1)^j(\pi  i)^j}\right\} \\
&\equal{}\frac{(\pi  i)^2}{2}\sum _{k\equal{}0}^{\infty } \frac{(\minus{}1)^k(\pi  i)^{2k}}{2^k (2\plus{}k)!} \sum _{j\equal{}0}^k \frac{(\minus{}1)^j(j\plus{}1) 2^j}{(\pi  i)^j} \\
&\equal{}\frac{(\pi  i)^2}{2}\sum _{k\equal{}0}^{\infty } \frac{(\pi  i)^{2k}}{2^k (2\plus{}k)!} \sum _{j\equal{}0}^k (j\plus{}1) \left(\frac{2i}{\pi }\right)^j
\end{align*}\]
Now at this point, the sums are in the form as you suggested.  However, I cannot just let the index on $ j$ go to infinity independently from $ k$.  That is:
\[ \frac{(\pi  i)^2}{2}\sum _{k\equal{}0}^{\infty } \frac{(\pi  i)^{2k}}{2^k (2\plus{}k)!} \sum _{j\equal{}0}^k (j\plus{}1) \left(\frac{2i}{\pi }\right)^j\ne\frac{(\pi  i)^2}{2}\sum _{k\equal{}0}^{\infty } \frac{(\pi  i)^{2k}}{2^k (2\plus{}k)!} \sum _{j\equal{}0}^{\infty} (j\plus{}1) \left(\frac{2i}{\pi }\right)^j\]
Rather seems I'd need to first calculate:
\[ \sum _{j\equal{}0}^k (j\plus{}1) \left(\frac{2i}{\pi }\right)^j\equal{}\frac{\pi ^{\minus{}k} \left(\pi ^{2\plus{}k}\plus{}(2 i)^{1\plus{}k} (2 i (1\plus{}k)\minus{}(2\plus{}k) \pi )\right)}{(\minus{}2 i\plus{}\pi )^2}\]
which I cannot show by direct calculation,then merge that expression with the first sum and conclude:
\[ \begin{align*}
\sum _{k\equal{}0}^{\infty } \sum _{j\equal{}0}^k \frac{(j\plus{}1) (\minus{}1)^{k\minus{}j} (\pi  i)^{2k\minus{}j\plus{}2}}{2^{k\minus{}j\plus{}1}(2\plus{}k)!}&\equal{} \\
&\hspace{\minus{}50pt}
\frac{(\pi  i)^2}{2}\sum _{k\equal{}0}^{\infty } \frac{(\minus{}1)^k(\pi  i)^{2k}}{2^k (2\plus{}k)!}\frac{\pi ^{\minus{}k} \left(\pi ^{2\plus{}k}\plus{}(2 i)^{1\plus{}k} (2 i (1\plus{}k)\minus{}(2\plus{}k) \pi )\right)}{(\minus{}2 i\plus{}\pi )^2}
\end{align*}\]

$ \int\frac{dx}{x^{4}\plus{}1}\equal{}\frac{1}{4 \sqrt{2}}\left(\minus{}2 \text{ArcTan}\left[1\minus{}\sqrt{2} x\right]\plus{}2 \text{ArcTan}\left[1\plus{}\sqrt{2} x\right]\minus{}\text{Log}\left[\minus{}1\plus{}\sqrt{2} x\minus{}x^2\right]\plus{}\text{Log}\left[1\plus{}\sqrt{2} x\plus{}x^2\right]\right)$

Pretty cool I must admit.  Probably wouldn't have seen it otherwise.

It's very good but, like all computer generated code, it can never be perfect. For example, using \text{Log} instead of \log and \text{ArcTan}\left[1+\sqrt{2} x\right] instead of \arctan (1+\sqrt{2} x).
Mathematica also can't tell if \left ... \right is required or not, so to be sure, it defaults to using those commands.


The sequence [tex](x_n)[/tex] is defined by [tex]x_1=1,x_2=2,x_{n+2}=x_{n+1}^2-\frac{x_n}{2}[/tex].Prove that the sequence converges and find the limit

Obviously, $x_n\to \infty$ ;) There is a typo in your post, I think.

Suppose that is has a limit that it is easily found as $\frac{2}{3}$. But on the other hand it looks like
$x_n > = 2^{n-1}$. Or am I wrong  :?

The limit is 3/2 according to my calculations.
Only the people who know me know that my calculations cannot be relied upon..
Ne we my answer is 3/2... :)

If it does have a limit, it is pretty clear that it has to be either 0 or $\frac32$, but with those initial values it does not. Actually, I think (haven't proof, and don't have much time now) that if $\max\{|x_1|,|x_2|\}>\frac32$, then the sequence does not have one. I am sure that in your case it doesn't.

[quote="djimenez"]if $\max\{|x_1|,|x_2|\}>\frac32$, then the sequence does not have one. I am sure that in your case it doesn't.[/quote]

Will you kindly explain what did you meant by the last statement?? :?

What I meant is that I have the hypothesis that if $\max\{|x_1|,|x_2|\}>\frac32$, then, the secuence defined by $x_{n+2}=x_{n+1}^2-\frac{x_n}{2}$ does not have a limit. I appologize if it was too confusing above!

Best,

Yeah right thats something I have also got..


Prove ${\sum_{k=0}^{n}}(-1)^{k}{n \choose k}=0$
Simplify ${n\choose 1}+{{n+1}\choose 2}+{{n+2}\choose 3}+\cdot\cdot\cdot+{{n+m+1}\choose m}$

For the second one, by simplify, do you mean to put it in $\sum$ form, or else?

P.S. I think you typoed:

${n\choose 1}+{{n+1}\choose 2}+{{n+2}\choose 3}+\cdot\cdot\cdot+{{n+m+1}\choose m}$, I think, should be ${n\choose 1}+{{n+1}\choose 2}+{{n+2}\choose 3}+\cdot\cdot\cdot+{{n+m-1}\choose m}$

Is this correct?

P.P.S. Wait...Maybe not...can you clarify, both this question and my first one?

[hide="hint"]
1. Consider $f(x) = (1+x)^{n}$.[/hide]

[quote="anirudh"][hide="EUREKA!"]

For the first one,

${\sum_{k=0}^{n}}(-1)^{k}{n \choose k}=(1+x)^{n}$, because of a variation of the Binomial Theorem
In this case, $x=-1$. $[1+(-1)]^{n}=0^{n}=0$. Therefore, ${\sum_{k=0}^{n}}(-1)^{k}{n \choose k}=0$[/hide][/quote]

In your first summation, I think you mean to say $x^{k}$ (or $-1$ instead of the $x$).

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=119683]Here[/url] is a good next step to this problem.

[hide="Hint"]There is a typo in #2.

You can use the formula $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ and you can keep simplifying this until we get to $\binom{n}{k}=\binom{n-1}{k}+\binom{n-2}{k-1}+...+\binom{n-k}{1}+1$. (I think)[/hide]

sorry
but I don't understand.
what will happen when k=0?
how can n be divided by 0?

@bibobeo are you talking about ${n \choose 0}$? If so, ${ n \choose k}= \frac{n!}{k!(n-k)!}$. Since $0!=1$ (by convention) => ${n \choose 0}=\frac{n!}{0!(n-0)!}= \frac{n!}{n!}=1$

[hide="Incomplete"]
$%Error. "mathstyle" is a bad command.
\sum_{k=0}^{n}(-1)^{k}{n \choose k}= 0$
$(-1)^{0}{n \choose 0}+(-1)^{1}{n \choose 1}+\cdots+(-1)^{n}{n \choose n}=0$

$1-n+\cdots+n-1 = 0$ which is true but i need someone to clear this mess.

[/hide]

[url=http://www.mathlinks.ro/Forum/viewtopic.php?t=90529]Here[/url] is a nice generalisation of the first equality.