[quote="hatchguy"]Solve in the positive integers the ecuation

$ x^2 \plus{} y^2 \plus{} z^2 \minus{} xy \minus{} yz \minus{} xz \equal{} w^2$

I tried a lot of ways to do it and i just got a solution.

Taking $ w^2 \equal{} 0$

It is known that $ x^2 \plus{} y^2 \plus{} z^2 \ge xy \plus{} yz \plus{} xz \equal{} > x^2 \plus{} y^2 \plus{} z^2 \minus{} xy \minus{} yz \minus{} xz \ge 0$

Equality holds when x=y=z. Then thats a solution. I dont know how to get the rest of the solutions..[/quote]

This equation may be written $ (2x \minus{} y \minus{} z)^2 \plus{} 3(y \minus{} z)^2 \equal{} 4w^2$

And we just have to solve $ u^2 \plus{} 3v^2 \equal{} 4w^2$ and then we have the solutions $ (z \plus{} \frac {\epsilon_1 u \plus{} \epsilon_2 v}{2}, z \plus{} \epsilon_2 v, z, w)$ (where $ \epsilon_1 \equal{} \pm 1$ and $ \epsilon_2 \equal{} \pm 1$).

$ u^2 \plus{} 3v^2 \equal{} 4w^2$ $ \iff$ $ 3v^2 \equal{} (2w \minus{} u)(2w \plus{} u)$ and so two families of solutions :

1) $ 2w \minus{} u \equal{} 3ab^2$ and $ 2w \plus{} u \equal{} ac^2$ $ \implies$ $ u \equal{} a\frac {c^2 \minus{} 3b^2}{2}$ and $ w \equal{} a\frac {3b^2 \plus{} c^2}{4}$ with $ b$ and $ c$ both even or both odd.

2) $ 2w \minus{} u \equal{} ab^2$ and $ 2w \plus{} u \equal{} 3ac^2$ $ \implies$ $ u \equal{} a\frac {3c^2 \minus{} b^2}{2}$ and $ w \equal{} a\frac {b^2 \plus{} 3c^2}{4}$ with $ b$ and $ c$ both even or both odd.

These two families are the same (changing signs) and so we have the general solution :

Let any $ a,b,c,d\in\mathbb Z$ such that : $ b$ and $ c$ both even or both odd, $ a\neq 0$, $ b,c$ not both $ 0$ and $ d > \max(0, \minus{} abc, \minus{} a(\frac {(b \plus{} c)^2}{4} \minus{} b^2))$ (in order to have a solution in positive integers). Then :

$ x \equal{} d \plus{} abc$
$ y \equal{} d \plus{} a(\frac {(b \plus{} c)^2}{4} \minus{} b^2)$
$ z \equal{} d$
$ w \equal{} |a|\frac {3b^2 \plus{} c^2}{4}$

[quote="hatchguy"]Solve in the positive integers the ecuation

$ x^2 \plus{} y^2 \plus{} z^2 \minus{} xy \minus{} yz \minus{} xz \equal{} w^2$

I tried a lot of ways to do it and i just got a solution.

Taking $ w^2 \equal{} 0$

It is known that $ x^2 \plus{} y^2 \plus{} z^2 \ge xy \plus{} yz \plus{} xz \equal{} > x^2 \plus{} y^2 \plus{} z^2 \minus{} xy \minus{} yz \minus{} xz \ge 0$

Equality holds when x=y=z. Then thats a solution. I dont know how to get the rest of the solutions..[/quote]
The way I got the idea:
$ 2(x^2 \plus{} y^2 \plus{} z^2 \minus{} xy \minus{} yz \minus{} zx) \equal{} (x \minus{} y)^2 \plus{} (y \minus{} z)^2 \plus{} (z \minus{} x)^2 \equal{} 2w^2$
Let $ a \equal{} x \minus{} y, b \equal{} y \minus{} z$, then $ z \minus{} x \equal{} \minus{} a \minus{} b$. So we have:
$ a^2 \plus{} b^2 \plus{} (a \plus{} b)^2 \equal{} 2w^2 \iff$
$ a^2 \plus{} ab \plus{} b^2 \equal{} w^2$.
Now it's only three variables at least :)
Let $ \omega \equal{} e^{i\frac {2\pi}{3}} \equal{} \frac { \minus{} 1 \plus{} \sqrt {3}i}{2}$. (Don't confuse it with $ w$. So $ \omega^2 \plus{} \omega \plus{} 1 \equal{} 0$.)
Then $ a^2 \plus{} ab \plus{} b^2 \equal{} (a \minus{} \omega b)(a \minus{} \omega^2 b) \equal{} w^2$. Now we'll use that FTA holds in $ \mathbb{Z}[\omega]$.
Wlog assume that $ \gcd(a,b) \equal{} 1$.
$ \gcd(a \minus{} \omega b,a \minus{} \omega^2 b) \equal{} \gcd( \omega(\omega \minus{} 1)b, a \minus{} \omega^2 b) \equal{}$ $ 4\gcd((\omega \minus{} 1)b, a \minus{} b) \equal{} \gcd(\omega \minus{} 1,a \minus{} b)$. (Since $ \omega$ is a unit and $ \gcd(a,b) \equal{} 1$).
Hence both $ a \minus{} \omega b$ and $ a \minus{} \omega b^2$ is a square times an unit, or a square times an unit times $ \omega \minus{} 1$.
First assume $ \gcd(a \minus{} \omega , a \minus{} \omega^2 b) \equal{} 1$:
Then either $ a \minus{} \omega b \equal{} (p \plus{} \omega q)^2$ or $ a \minus{} \omega b \equal{} \minus{} \omega(p \plus{} \omega q)^2$, where $ p,q \in \mathbb{Z}$. (Because all units are on the form $ ( \minus{} \omega)^n$.)
The first case: $ a \minus{} \omega b \equal{} (p \plus{} \omega q)^2$
$ a \minus{} \omega b \equal{} p^2 \plus{} 2pq \omega \plus{} \omega^2 q^2 \equal{} p^2 \minus{} q^2 \minus{} \omega (q^2 \minus{} 2pq)$.
Hence $ a \equal{} p^2 \minus{} q^2$ and $ b \equal{} q^2 \minus{} 2pq$.
Inserting back into the equation, gives: $ (p^2 \minus{} q^2)^2 \plus{} (p^2 \minus{} q^2)(q^2 \minus{} 2pq) \plus{} (q^2 \minus{} 2pq)^2 \equal{}$ $ p^4 \minus{} 2p^3q \plus{} 3p^2q^2 \minus{} 2pq^3 \plus{} q^4 \equal{} (p^2 \minus{} pq \plus{} q^2)^2$
(We could have seen this immediatly: $ a^2 \plus{} ab \plus{} b^2 \equal{} (a \minus{} \omega b)(a \minus{} \omega^2 b) \equal{}$ $ (a \minus{} \omega b)\overline{(a \minus{} \omega b)} \equal{} ((p \plus{} q \omega)(p \plus{} q \omega^2))^2 \equal{} (p^2 \minus{} pq \plus{} q^2)^2$)
The case $ a \minus{} \omega b \equal{} \minus{} \omega(p \plus{} \omega q)^2$ will just give the solution $ a \equal{} q^2 \minus{} 2pq, b \equal{} p^2 \minus{} q^2$.
Then assume $ \gcd(a \minus{} \omega, a \minus{} \omega^2 b) \equal{} 1 \minus{} \omega$.
Then either $ a \minus{} \omega b \equal{} (1 \minus{} \omega)(p \plus{} \omega q)^2$ or $ a \minus{} \omega \equal{} \minus{} \omega(1 \minus{} \omega)(p \plus{} \omega q)^2$.
If $ a \minus{} \omega b \equal{} (1 \minus{} \omega)(p \plus{} \omega q)^2$ then $ a^2 \plus{} ab \plus{} b^2 \equal{} (1 \minus{} \omega)(1 \minus{} \omega^2)(p \plus{} \omega q)^2(p \plus{} \omega^2 q) \equal{} 3(p^2 \minus{} pq \plus{} q^2)^2$ which is clearly not a perfect square. (But $ 3$ is a square in $ \mathbb{Z}[\omega]$ so that is why we get this "solution")
Hence $ (a,b) \equal{} (p^2 \minus{} q^2, q^2 \minus{} 2pq)$ (Or a permutation) (And of course $ w \equal{} p^2 \minus{} pq \plus{} q^2$)
We assumed earlier that $ \gcd(a,b) \equal{} 1$. So we have to multiply with $ \gcd(a,b) \equal{} t$
So $ x \minus{} y \equal{} t(p^2 \minus{} q^2), y \minus{} z \equal{} t(q^2 \minus{} 2pq), z \minus{} x \equal{} t(2pq \minus{} p^2)$ and letting $ x \equal{} r$ we get:

$ (x,y,z,w) \equal{} (r,r \plus{} t(q^2 \minus{} p^2),r \plus{} t(2pq \minus{} p^2),t(p^2 \minus{} pq \plus{} q^2))$ (Or any permutations of $ x,y,z$)

This is solved for all integers, so you have to make sure that $ r > 0, p^2 \minus{} q^2,p^2 \minus{} 2pq$, and $ (p,q) \neq (0,0)$.

How come it doesn't look like pco's solution ? :)

Edit: It does actually. If we let $ b \equal{} 2q\minus{}p, c \equal{} p, a \equal{} t$ :)

[quote="pco"][quote="Mathias_DK"] How come it doesn't look like pco's solution ? :)

Edit: It does actually. If we let $ b \equal{} 2q \minus{} p, c \equal{} p, a \equal{} t$ :)[/quote]

... and $ d \equal{} r$  :)

It's always strange to see how multiple expressions may give the same family of results ... :)

But yours is prettier.[/quote]
Thanks. I like $ (x,y,z,w) \equal{} (r\plus{}t \cdot p^2,r\plus{}t \cdot q^{2},r\plus{}t \cdot 2pq,t(p^{2}\minus{}pq\plus{}q^{2}))$ more though :) Doesn't really matter though :P


A parking structure contains 300 monthly spaces, 1500 daily spaces, and 100 executive spaces. If the structure is to be enlarged proportionally to 2090 spaces, how many daily spaces should be added?

Since the enlargment is proportional, $ \frac{2090}{300\plus{}1500\plus{}100}\equal{}\frac{11}{10}$, or an increase of $ \frac{1}{10}$. So the number of spaces that should be added is $ 1500\times{\frac{1}{10}}\equal{}\boxed{150}$.


function
trigonometry
calculus
calculus computations

try to multiply $ x \minus{} 1$
but I think it don't help. :blush:
[EDIT]

[hide="Solution"]As x = 0 is not a solution, divide both sides by $ x^2$ to get

$ x^2 \plus{} x \plus{} 1 \plus{} \frac {1}{x} \plus{} \frac {1}{x^2} \equal{} 0$

which can be written as

$ \left(x \plus{} \frac {1}{x}\right)^2 \plus{} \left(x \plus{} \frac {1}{x}\right) \minus{} 1 \equal{} 0$

and now make $ x \plus{} \frac {1}{x} \equal{} u$ to get

$ u^2 \plus{} u \minus{} 1 \equal{} 0$,

whose solutions are $ u \equal{} \frac{\minus{}1 \pm \sqrt{5}}{2}$ => $ u \equal{} \phi \,\,or \,\, u \equal{} \phi \minus{}1$.

It's easy from now on.[/hide]

Extremal's hint is, in my opinion, more useful.  We get $ x^5 \equal{} 1$.  In fact, this is $ \Phi_5(x)$ and its roots are precisely the primitive fifth roots of unity $ e^{ \frac{2\pi i k}{5} }, k \equal{} 1, 2, 3, 4$.

A Geometric Series.

$ \sum _{i\equal{}0}^n x^i\equal{}\frac{x^{n\plus{}1}\minus{}1}{x\minus{}1}\equal{}0$ for $ x\neq 1$

$ x^{n\plus{}1}\equal{}1$

so $ x\equal{}e^{\frac{(2 \pi ) i }{n\plus{}1} k} | x\in \mathbb{Z}$

The link between the methods is that Carcul has provided a way to find the exact trigonometric functions of $ \frac{2\pi}5.$ For instance, it follows from what he started that $ \cos\left(\frac{2\pi}5\right)\equal{}\frac{\sqrt{5}\minus{}1}4.$ From that we can get the sine of that angle, and so on.


Pascal\u0027s Triangle
algebra
binomial theorem

Note that by the [url=http://en.wikipedia.org/wiki/Binomial_theorem]Binomial Theorem[/url]

$ (1\plus{}1)^n\equal{}\binom{n}{0}\cdot 1\plus{}\binom{n}{1}\cdot 1 \plus{}\cdots \plus{}\binom{n}{n}\cdot 1$

Therefore $ 2^n\equal{} \binom{n}{0}\plus{}\binom{n}{1}\plus{}\cdots\plus{}\binom{n}{n}$

http://www.artofproblemsolving.com/Forum/viewtopic.php?t=311891

Don't create two topics for the same thing :mad:
Anyway, this is not pre-olympiad or intermediate level.


I wouldn't call this a typical olympiad problem, because it's easy to prove, but it's so cute...  :)
It's created by O. Bottema

Let $BM$ and $CN$ be external bisectors of the angles $B=12^{\circ}$ and $C=132^{\circ}$ of a special triangle $ABC$, each terminated at the opposite side. Without using trigonometric functions, compare the lengths of the angle bisectors.

Indeed. :)
I think it's quite cute, don't know why.


$ x_1>0$ and $ x_{n\plus{}1}\equal{}\sqrt[n]{1\plus{}nx_n}\minus{}1$ for $ n\equal{}1,2,\dots$.

prove that $ n^2x_n$ is convergent.

uhm... by Bernoulli $ x_{n\plus{}1}\ge x_n$ so $ n^2x_n\ge n^2x_1\to\infty$...

I think that $ (x_n)$ is  [b]decreasing[/b] and Bernoulli gives only $ x_n\to 0$ (easy)


limit
induction
real analysis
real analysis unsolved

Let $ (a_n) $ be a sequence defined : $ a_0=\alpha  ;  a_{n+1}=2a_n-n^2 $ . Find the condition of $ \alpha $ such that : $ a_n >0 $ $ \forall n $

$a_0=\alpha,\ a_n=2^n b_n,\ \left( \forall\right) n\in N\Longrightarrow b_0=\alpha,\ b_{n+1}=b_n-\frac {n^2}{2^{n+1}},\ \left(  \forall \right) n\in N\Longrightarrow$

$b_n=\alpha -\frac 12\sum\limits_{k=1}^{n-1} \frac {k^2}{2^k}\Longrightarrow \alpha \ge \frac 12\lim_{n\to\infty} \sum\limits_{k=1}^{n} \frac {k^2}{2^k}\Longrightarrow \overline {\underline {\left|  \alpha\ge 3 \right| }}.$

[b]Remark[/b]. $L_0=\lim_{n\to\infty}\sum \limits_{k=1}^n \frac {1}{2^k}=1,\ L_1=\lim_{n\to\infty}\sum \limits_{k=1}^n \frac {k}{2^k}=2,\ \sum \limits_{k=1}^n \frac {k^2}{2^k}=\sum \limits_{k=0}^{n-1}\frac {(k+1)^2}{2^{k+1}}=$ $\frac 12 \left( \sum \limits_{k=1}^{n-1} \frac {k^2}{2^k} +2\sum \limits_{k=1}^{n-1} \frac {k}{2^k} +\sum \limits_{k=0}^{n-1} \frac {1}{2^k} \right) ,\ L_2=\lim_{n\to\infty}\sum \limits _{k=1}^n \frac {k^2}{2^k}$ $\Longrightarrow 2L_2=L_2+2L_1+L_0 +1\Longrightarrow L_2=6.$

Can you write down the proof for: $ \lim_{n\to \infty}\sum{\frac{k^2}{2^k}}=\frac{3}{2} $ ?

I think the limit is 6, not $\frac{3}{2}$ :)

You could prove by induction that \[\sum_{k = 1}^n \frac{k^2}{2^k} = 6 - \frac{n^2 + 4n + 6}{2^n},\] for example.

But $\sum_{k = 1}^{\infty} \frac{k^2}{2^k} = 6$ right? Or am I missing something, Levi?

No, Levi, you made a mistake in your computations. We have $\sum_{k = 1}^{\infty} \frac{k^2}{2^k} = 6$ and we must have $\alpha \geq 3$.

Believe me: for $\alpha = \frac{5}{2}$ you get the sequence 5/2, 5, 9, 14, 19, 22, 19, 2, -45.

This is easy for me. :lol:
$a_{n+1}=2a_n-n^2\Longleftrightarrow a_{n+1}-\{(n+1)^2-2(n+1)-3\}=2(a_n-n^2-2n-3)$
Thus we have $a_n=n^2+2n+3+2^n(\alpha-3)\ (n=0,1,\cdots)$
Since $n^2+2n+3\geq 3$,the desired condition of $\alpha$ is $\alpha\geq 3$.

All are right !. You see the first my reply. I corrected.


[quote="1=2"]Show that the smallest n such that in a group of n people there must be a pair of people who have the same birthday is 367.

[hide="hint"]The year is 2008.[/hide][/quote]
[hide="Solution"]
Let each integer from 1 to 366 represent a day, starting from January 1st to Dec. 31st. (note this includes Feb. 29)
If there were any less than 367 people, there would not necessarily have to be anyone sharing a birthday with another. By the pigeonhole principle, if there are 367 people, and 366 days that anyone can have their birthday on, there MUST be at least 2 people sharing a birthday.
[/hide][/hide]

[quote="moogra"]lol intermediate topics? Trivial with pigeon hole.[/quote]
Exactly..


Three people went to the market to sell their chickens. The first one has 10 chickens, the second one has 16 and the third one has 26. All prices for each chicken are the same. They have all sold some of their chickens before lunch. Afraid of not being able to sell everything they lowered the price in the afternoon and they sold all the remaining chicken at the lower price. At the end of the day, each person collected 35 monies. What was the price of the chicken in the morning and in the afternoon?

Are the monies only available in whole amounts?

[hide]Let $ a$ be the higher price, $ b$ the lower price and let the sellers sold $ x,y,z$ chickens in the morning respectively. Then

$ xa\plus{}(10\minus{}x)b\equal{}35$
$ ya\plus{}(16\minus{}y)b\equal{}35$
$ za\plus{}(26\minus{}z)b\equal{}35$

Subtracting the second from the first and the third from the second we get

$ (x\minus{}y)(a\minus{}b)\equal{}6b$
$ (y\minus{}z)(a\minus{}b)\equal{}10b$

Therefore $ {x\minus{}y\over y\minus{}z}\equal{}{3\over 5}$. Since $ x,y,z$ are integer, we must have $ x\minus{}y\equal{}3\land y\minus{}z\equal{}5$ (the case $ x\minus{}y\equal{}6\land y\minus{}z\equal{}10$ is impossible since it would imply $ x\minus{}z\equal{}16$, and the first seller can't sell $ 16$ chickens more than the third since he has only $ 10$ total.)

Since they all sold some chickens in the morning, the possible cases are $ x\equal{}9, y\equal{}6, z\equal{}1$ and $ x\equal{}10, y\equal{}7, z\equal{}2$ (If no one sold ALL of his chickens, that should also be expressly stated.)

Now it's easy to solve corresponding systems for $ a,b$: in the first case we get $ a\equal{}3.75, b\equal{}1.25$ and in the second $ a\equal{}3.5, b\equal{}{7\over 6}$. Since monies probably don't come in sixths, what's most probably wanted is the first solution.[/hide]

The third seller must sell at least one chicken, from which we get $ z \equal{} 1,y \equal{} 6, x \equal{} 9$.

The first seller can't sell more than ten chickens, from which we get $ x \equal{} 10, y \equal{} 7, z \equal{} 2$.

Also, observe that $ (x\minus{}y)(a\minus{}b)\equal{}6b>0$ implies $ x>y$, and in the same manner $ y>z$, so we can't have something like $ x\minus{}y\equal{}\minus{}3\land y\minus{}z\equal{}\minus{}5$


The average of four numbers is 72. three of the numbers are 60, 70, and 80. What is the fourth number?

Solve an equation for mean:

$ \frac{60\plus{}70\plus{}80\plus{}x}{4}\equal{}72$
$ x\plus{}210\equal{}288$
$ x\equal{}\fbox{78}$

More intuitively, we could note that the average of the first three is $70$. We want the average to be $72$, which is $2$ greater than the current average. However, we are dividing by $4$, so we must add:
\[2*4=8\]
to the current average, which is $70$, to get:
\[\boxed{78}\]

We can prove that this works for all problem in which we are given the first $n-1$ scores for $n$ tests. If we know that the average of the first $n-1$ scores is $a$, and we set $x$ as the amount we add to $a$ for the last score, we have (with $m$ representing the difference between the average of the first $n-1$ and the target average of the $n$):
\[\dfrac{a(n-1)+(a+x)}{n}=a+m\]
\[\dfrac{a(n)+x}{n}=a+m\]
\[a+\dfrac{x}{n}=a+m\]
\[\dfrac{x}{n}=m\]
\[x=mn\]


nice problem!
make the substitution $a=\sqrt[3]x, b=\sqrt[3]y, c=\sqrt[3]z$, and we have that $abc=1$, so the problem is equivalent to
$(abc+a^3)(abc+b^3)(abc+c^3)\geq 2+2(\dfrac{a}{c}+\dfrac{b}{a}+\dfrac{c}{b}) \\\Leftrightarrow (bc+a^2)(ac+b^2)(ab+c^2)\geq 2+2(a^2b+b^2c+ac^2) \\\Leftrightarrow a^3+b^3+c^3+(ab)^3+(ac)^3+(bc)^3\geq2(a^2b+b^2c+ac^2)$

but from am-gm we have that $a^3+(ab)^3+1\geq3a^2b$, taking the cyclic sum we obtain $a^3+b^3+c^3+(ab)^3+(ac)^3+(bc)^3+3\geq2(a^2b+b^2c+ac^2)+a^2b+b^2c+ac^2\geq2(a^2b+b^2c+ac^2)+3\sqrt[3]{(a^2b)(b^2c)(ac^2)}=2(a^2b+b^2c+ac^2)+3 \\\Rightarrow a^3+b^3+c^3+(ab)^3+(ac)^3+(bc)^3\geq2(a^2b+b^2c+ac^2)$
and we're done!!! :D

maybe the substitution is useless but it is easier, at least for me, to work without any kind of roots...

[quote=Amir.S]Let $x$, $y$ and $z$ be positive real numbers such that $xyz = 1$. Prove that
$$\left(1+x\right)\left(1+y\right)\left(1+z\right)\geq 2\left(1+\sqrt[3]{\frac{x}{z}}+\sqrt[3]{\frac{y}{x}}+\sqrt[3]{\frac{z}{y}}\right).$$[/quote]

I thought this is APMO 1998/3 for a second. Anyway, here's cleaner writeup than @2above but mostly the same.

Note that the inequality is equivalent to proving
$$x+y+z+xy+yz+zx\geq 2\left(\sqrt[3]{\frac{x}{z}}+\sqrt[3]{\frac{y}{x}}+\sqrt[3]{\frac{z}{y}}\right).$$
Of course, the RHS term look very sus... Indeed, we'll be using AM-GM.
$$x+xy+1\geq 3\sqrt[3]{x\cdot xy\cdot 1}=3\sqrt[3]{\frac{x}{z}}$$
and vice versa. Sum it up to get
$$x+y+z+xy+yz+zx+3\geq 3\left(\sqrt[3]{\frac{x}{z}}+\sqrt[3]{\frac{y}{x}}+\sqrt[3]{\frac{z}{y}}\right).$$
Now, we'll use AM-GM one last time. We have
$$\sqrt[3]{\frac{x}{z}}+\sqrt[3]{\frac{y}{x}}+\sqrt[3]{\frac{z}{y}}\geq 3$$
and it's easy to see that we're done. :)


If $ c\equal{} (1$ $ 2 ... n)$ is an n-cycle and $ t \equal{} (1$   $ d)$ is a transposition, for which $ d$
do $ t$ and $ c$ generate the whole symmetric group of order $ n$? ($ Sym \equal{} <c , t>$)

why you've sent it two times? , here:[url]http://www.mathlinks.ro/viewtopic.php?p=1274712#1274712[/url]

$ c^ktc^{\minus{}k}\equal{}(1\plus{}k,d\plus{}k)$, therefore all transpositions $ (i,j)$ can be represented in these form, if $ j\minus{}i\equal{}d\minus{}1\mod n$. If $ (d\minus{}1,n)\equal{}1$ all traspositions.
If $ (d\minus{}1,n)\equal{}r>1$ then we get $ <c,t>\equal{}S_{n/r}^r$ - r summ of r symmetric groups sizes n/r.

Yes Rust. Do you know how to prove it??? I mean, if $ (d\minus{}1, n) \equal{} 1$ then they generate the symmetric group of order n??

I give prove all transpositions give all symmetric group.
If r>1 we get r transpositions $ (i_k,j_k),i_k\equal{}j_k\mod r$ transpositions in sets $ (1,r\plus{}1,...,mr\plus{}1),(2,r\plus{}2,...,mr\plus{}2),...(r,2r,...,(m\plus{}1)r\equal{}n).$


group theory
abstract algebra
Ring Theory
calculus
integration
superior algebra
superior algebra unsolved

Let $ A$ be ring without divisors of zero and $ B$ a finite subgroup of $ (U(A),*)$. Probe that $ B$ is cyclic.

It reduces to the at least three tiomes posted problem:
If in a finite group, $ x^n\equal{}e$ (neutral element) has at most $ n$ solutions for all $ n$, then this groupis cyclic.

This is not true.
The [url=http://en.wikipedia.org/wiki/Quaternions]quaternions[/url] $ \mathbb{H}$ have no zero-divisors, but
$ \mathbb{H}^\times$ contains the finite group $ Q_8 \equal{} \{\pm 1,\pm i,\pm j,\pm k\}$.
In fact $ \mathbb{H}^\times$ even contains a subgroup isomorphic to the non-solvable finite group $ \text{SL}_2(\mathbb{F}_5)$.

I'll prove that $ B$ is in fact a finite subgroup of the multiplikative group of a division ring.
Those groups have been classified by Zassenhaus. (they are all [url=http://en.wikipedia.org/wiki/Frobenius_complement]Frobenius complements[/url])

Let $ R: \equal{} \sum_{b\in B} \mathbb{Z}b$ be the smallest subring of $ A$ containing $ B$.
If $ A$ has finite characteristic, i.e. $ n\cdot 1_A \equal{} \underbrace{1_A \plus{} \ldots \plus{} 1_A}_{n\text{ times}} \equal{} 0$ for some $ n\in\mathbb{N}$,
then $ R$ is a finite zero-divisor free ring, and then the left and right multiplication in $ R$
with any $ 0\not \equal{} x\in R$ is injective, and then also surjective.
So $ R$ is a division ring, and then by [url=http://en.wikipedia.org/wiki/Division_ring]Wedderburn[/url] a finite field. (or $ A \equal{} B \equal{} 0$)
Then $ B\le R^\times$ cyclic.

Otherwise if $ n\cdot 1_A\not \equal{} 0$ for all $ n\in \mathbb{N}$,
then $ R$ is a subring of the [url=http://en.wikipedia.org/wiki/Localization_of_a_ring]localization[/url] $ D: \equal{} \mathbb{N}^{ \minus{} 1}R$,
which is a finite dimensional zero-divisor free $ \mathbb{Q}$-algebra.
So the left and right multiplication in $ D$
with any $ 0\not \equal{} x\in D$ is injective and $ \mathbb{Q}$-linear, and then also surjective.
So $ D$ is a division ring with $ B\le D^\times$.
If $ B$ is commutative, then so are $ R$ and $ D$.
So $ D$ is a field and $ B$ is as finite subgroup of $ D^\times$ cyclic.
This gives every abelian subgroup of $ B$ cyclic.

Ring in the first post obviously (?) means "unitial commutative ring". And for those, my argument works  :wink:
For the noncommutative case and a commutative finite subgroup, we may restrict to the subring generated by it's elements and procede.

I don't think so, because "unitial commutative ring" without divisors of zero
is simply an integral domain. And then we can take the quotient field $ K$ of $ A$
and get $ B$ a finite subgroup of $ K^\times$, which is well-known to be cyclic.
Also the fact you used holds for all finite groups, and is almost trivial in the abelian case.


Find the total number of positive integers less than 999 which are neither divisible by 3 nor 5. :)
Anyways, could you give a detailed explanation on how you do these kind of sums.??:lol:

welll....
what i;d first do was find all integers under 999 which ARE divisible by 3 or 5
so for 3 you have 3-996 which is 332 integers
for 5 you have 5-995 which is 199 integers
however you have to subtract all multiples of 15 because you have counted them twice
15-990 is 67 integers
so 332+199-67=464 integers which are divisible by 5 or 3 so integers not divisible by them would be 1-998 which is 998 integers minus 464 which is [b]534[/b]

I dont think 15 - 990 is 67 .....I guess it's 66 only {15 - 90 is only 6 , ---15 , 30 , 45 , 60 , 75 , 90 } You needn't include the 15 once more...
Do tell me if I'm worng....
And , well , your ultimate answer is 533 :D

oops yea i made a mistake... i meant 975/15 +1 but thats same as 990/15  :blush:

err...do you mean $15-190$ or $\frac{15}{190}$? The calculations seems as the later but the written thing seems like the first.

Hey A.s.o.d ,
I didnt mean 15 minus 990 when I wrote 15 - 990 .
I meant from 15 to 990....{there are 66 numbers which are divisible by 15............} :)


$S_{1}$ and $S_{2}$ are two circles that intersect at distinct points $P$ and $Q$. $\ell_{1}$ and $\ell_{2}$ are two parallel lines through $P$ and $Q$. $\ell_{1}$ intersects $S_{1}$ and $S_{2}$ at points $A_{1}$ and $A_{2}$, different from $P$, respectively. $\ell_{2}$ intersects $S_{1}$ and $S_{2}$ at points $B_{1}$ and $B_{2}$, different from $Q$, respectively. Show that the perimeters of the triangles $A_{1}QA_{2}$ and $B_{1}PB_{2}$ are equal.

Let the intersection point of$ A_1Q $and $B_1P$ be $Y$ and that of $B_2P$ and $A_2Q$ be $Z$.
Let $<YA_1P=x$. Then by easy angle chasing we get $<YPA_1=<YQB_1=<YB_1Q=x$.
Thus $A_1Y=YP$ and $YQ=YB_1$.Adding these we get $A_1Q=B_1P$.Similarly $PB_2=A_2Q$
Also note that $PQB_2A_2$ and $PQB_1A_1$ are isosceles trapezoids(proof is too easy fo inclusion) so $A_2P=B_2Q$ and
$A_1P=B_1Q$.Adding these we get $A_1A_2$=$B_1B_2$ and the result follows.

Tell you what....It is too easy for any prestigious mathematics competition.Don't challenge anyone with this problem.

$A_1PQB_1$ and $A_2PQB_2$ are isosceles trapezoids.
Hence, $PB_2$ = $A_2Q$ and $A_1Q$ = $PB_1$.
Again, $A_1A_2B_2B_1$ is a ||gm.
So, $A_1A_2$ = $B_1B_2$.
Thus, the result immediately follows.

Let's change $P,Q$ to $A,B$
Easy to see, $A_1A_2B_2B_1$ is a parallelogram $\implies$ $A_1A_2=B_1B_2$, Let $A_1B \cap AB_1=X_1$ and $AB_2 \cap A_2B=X_2$ $\implies$ $\Delta AA_1X_1 \sim \Delta B_1BX_1$ and $\Delta AA_2X_2$ $\sim$ $\Delta B_2BX_2$ $\implies$ $A_1B+A_2B$ $=$ $A_1X_1+X_1B+BX_2+A_2X_2$ $=$ $AX_1+B_1X_1$ $+$ $B_2X_2$ $+$ $AX_2$ $=$ $AB_1+AB_2$ $\implies$ $A_1B$ $+$ $A_2B$ $=$ $AB_1$ $+$ $AB_2$ combined with $A_1A_2$ $=$ $B_1B_2$ gives the desired result


Source: 2005 AMC-10B #13

How many numbers between 1 and 2005 are integer multiples of 3 or 4 but not 12?

$\text{(A)}\ 501 \qquad\text{(B)}\ 668 \qquad\text{(C)}\ 835 \qquad\text{(D)}\ 1002 \qquad\text{(E)}\ 1169$

[hide="Click to reveal hidden text"]Calculate how many numbers in every set of 12 is a multiple of 3 or 4 but not 12. So in the first 12, there's 3, 4, 6, 8, and 9. That's $\frac{5} {12}$ Multiply that by 2005 to get $835\frac{5} {12}$ or $\boxed {C}$

The reason why it doesn't come out at 835 even is that 2005 isn't divisible by 12.[/hide]

[hide]There are 501 multiples of 4 and 668 multiples of 3 between 1 and 2005.

There are also 167 multiples of 12.

So, since we want no multiples of 12, $501+668-2(167)=835 \implies \boxed{C}$[/hide]

[hide]There are $\lfloor{\frac{2005}{3}}\rfloor=668$ multiples of 3 under 2005. There are $\lfloor{\frac{2005}{4}}\rfloor=501$ multiples of 4 under 2005. The sum of that is 1069. However, we counted the multiples of 12 under 2005 (which is $\lfloor{\frac{2005}{12}}\rfloor=167$)[i] twice[/i], so the answer is 1069-2(167) = 835. [/hide]


Estoy colgando el examen de las olimpiadas de un nivel aceptable para esta seccion
 que es de nive de inciacion en olimpiadas .
espero les agrade...

Carlos Bravo ;)
----
[b][size=150][color=blue]VI Olimpiada del Cono Sur
Bolivia - 1995[/color][/size] [/b]

$\blacktriangleright$  [color=blue]Problema 1.[/color]
Halle un n\'umero de tres d\'igitos, sabiendo que la suma de los
mismos es 9, el producto es 24 y el n\'umero, cuando es leido de
la derecha a la izquierda, es igual a $27/38$ del n\'umero
original.

$\blacktriangleright$  [color=blue]Problema 2.[/color]
Hay diez puntos marcados sobre una circunferencia, numerados del 1
al 10 en alg\'un orden. Trazamos en seguida todos los segmentos
que esos puntos determinan y los pintamos, unos de rojo y los
dem\'as de azul. Es posible, sin cambiar los colores de los
segmentos, re - enumerar los puntos de 1 al 10 de modo que si dos
n\'umeros eran unidos por un segmento rojo, ahora lo sean por un
segmento azul y viceversa?

$\blacktriangleright$ [color=blue]Problema 3.[/color]
Sea $ABCD$ un rect\'angulo cuyos lados miden $AB = a$ y $BC = b$.
Dentro del resct\'angulo trazamos dos circunferencias tangentes
exteriormente, de modo que una de ellas es tangente a los lados
$AB$ y $AD$, mientras que la otra es tangente a los lados $BC$ y
$CD$ del rect\'angulo.
(a) Calcule, en funci\'on de $a$ y $b$, la distancia entre los
centros de las circunferencias.
(b) Haciendo variar los radios de las circunferencias de modo que
la situaci\'on de tangencia se mantenga, determine el lugar
geom\'etrico descrito por el punto de tangencia de las
circunferencias.

$\blacktriangleright$ [color=blue]Problema 4.[/color]
Escribamos los d\'igitos de 1995 del modo siguiente:
$199511999955111999999555...$
(a) ¿Cu\'antos d\'igitos deben ser escritos para que la suma de
los mismos sea 2880?
(b) ¿Qu\'e d\'igito aparece en la posici\'on 1995 a partir
de la izquierda?

$\blacktriangleright$ [color=blue]Problema 5.[/color]
Una semicircunferencia de centro $O$ y di\'ametro $AC$ es dividida
en dos arcos $AB$ y $BC$, en la raz\'on 1:3. Sea $M$ el punto
medio del radio $OC$ y $T$ el punto del arco menor $BC$ para el
cual el \'area del cuadril\'atero $OBTM$ es el mayor posible.
Calcule esa \'area en funci\'on del radio de la semicircunferencia.

$\blacktriangleright$  [color=blue]Problema 6.[/color]
Para cada $n\in \textsc{N}$, sea $f(n)= 2n - 1995[n/1000]$.
(a) Muestre que, si existe $r\in \textsc{N}$ tal que
$f^{(r)}(n)=1995$ entonces $n$ es un m\'ultiplo de 1995.
(b) Muestre que si $n$ fuera m\'ultiplo de 1995 entonces existe
$r\in \textsc{N}$ tal que $f^{(r)}(n)=1995$.
(c) Determine $r$ si $n= 1995 \times 500$.

(Nota: $f^{(r)}$ significa la compuesta de $f$ consigo misma, $r$
veces).

$\text{\LaTeX}{}ed$ by Carlos Bravo 2006.

Haber  aki la version en pdf......

Saludos,

Carlos Bravo


trigonometry
linear algebra
matrix
trig identities

Prove the inverse trig identities:

 $\arcsin(x)+\arccos(x)=\pi/2\; \\ \\ \arctan(x)+\arccos(x)=\pi/2.\; \\ \\ \arctan(x)+\arctan(1/x)=\left\{\begin{matrix}\pi/2, & \mbox{if }x > 0 \\-\pi/2, & \mbox{if }x < 0 \end{matrix}\right. \\ \\ \arctan(x)+\arctan(y)=\arctan\left(\frac{x+y}{1-xy}\right)+\left\{\begin{matrix}\pi, & \mbox{if }x,y>0 \\-\pi, & \mbox{if }x,y<0 \\ 0, & \mbox{otherwise }\end{matrix}\right.$

The first expression can be proven easily with unit circle.

[b]Another example :[/b] $|x|<\frac{\pi}{4}\Longrightarrow$ $\arcsin (\tan x)=\arctan\frac{\sin x}{\sqrt{\cos 2x}}\ .$


I've been working with some timeseries analysis for the financial markets, where I use linear regression. The problem is that if we have a straight trend, it's "straight calculated in percentages", not by points. So even though the market is efficienct, by moving in a straight line (percentage), i get "wrong" results with linear regression...(the market looks straight on a logarithmic scale, thereby the regressionline looks curvilinear).

My regression knowledge is were limited, and i've been searching for a forumla for logarithmic regression without finding any.. is there perhaps a way to change your calculation of linear regression to a logaritmic scale?

Thanks in advance
/Johan

You don't actually need a different regression formula, you simply need to transform the original variables into log form, and then run a linear regression on the transformed variables.

That is, suppose you have a vector of observations of your Y variable and a vector of observations of your X variable.

If you believe that log Y is a linear function of log X, then you just define new variables Z = log Y and W = log X, and then run the usual linear regression on Z vs. W.

Similarly, suppose you believe that Y is actually a quadratic function of X and you want to find the best fitting Y = a + bX^2.   Let W = X^2 and run a regression of Y vs. W.

This sort of variable transformation is very easy to do in a program like Excel.

Sensibly interpreting your results, on the other hand, can be another matter altogether.  But that's true even when you run a linear regression on untransformed variables.

A classic really good book to read on this subject that is not very difficult for smart but inexperienced students is [i]Applied Econometrics[/i] by Rao & Miller.  It's an oldie-but-goodie from 1971 that is likely out of print, but you should be able to find a copy in a nearby college library.

Another really good classic that should be accessible to you is Edward Tufte's Data Analysis for Politics & Policy.  It is an inexpensive paperback and very short, but Prof. Tufte has generously made the book available for free at his website:

http://www.edwardtufte.com/tufte/dapp/

It truly is a classic--it has justly been compared to Strunk & White's Elements of Style.  I highly recommend it.

Thank you for your quick reply sophia,

I was hoping there was an easy solution 'cause otherwise it would require a few ours of programming of me. ( I think I skipped the log-classes in school :-S )

Just changing the input (y) to log(y) gave med results I needed!

I will check the links, the free book seems interesting.

Once again, thank you sophia, you made my day  :wink:


i want to know the best your momma jokes you have heard

mods if this is inappropriate please feel free to delete this

your momma jokes are retarded, nobody uses them, they rnt even funny.This is prolly gonna get locked, Valentin locked one like this before

[quote="GoBraves"]This is prolly gonna get locked, Valentin locked one like this before[/quote]GoBraves, it looks like you're a prophet :D :D


hello   ppl !  :D

can you  sum

$ 3\plus{}\dfrac{1\cdot 1}{4\cdot 5\cdot 3}\left(8 \plus{} \dfrac{2\cdot 3}{7\cdot 8\cdot 3}\left(13 \plus{} \dfrac{3\cdot 5}{10\cdot 11\cdot 3}\left(18 \plus{} \dfrac{4\cdot 7}{13\cdot 14\cdot 3}\left(23 \plus{} \dfrac{5\cdot 9}{16\cdot 17\cdot 3}\left(28 \plus{} \dfrac{6\cdot 11}{19\cdot 20\cdot 3}\left(\;\ldots\;\right)\right)\right)\right)\right)\right)$

i am giving the answer below, but don't look just yet !    :blush:

[hide]
$ answer: \qquad \boxed{\pi}$
[/hide]


geometry
geometric transformation
reflection

:) a small slab of  material is placed on a dish containing liquid nitrogen.The material is a superconductor at the temperature of liquid nitrogen.A small but strong magnet is moved near and placed over the slab.The magnet is seen to wobble but remains suspended over the slab.
 :arrow: describe the motion of the magnet qualitatively(if possible derive an equation of motion by assuming standard constants like temperature,mass,gravity etc.)
 :arrow: suggest the reason for the wobbling motion of the magnet.
Can anyone suggest me links on the web for:
1. national phy. olymp. papers of different countries?
2.study matter on the concepts and the application method in context of the above problem? :roll:

So a superconducter will exclude any magnetic field which comes nearby just like it where a "magnetic mirror". If a north pole approaches the superconductor, the magnet will behave as though another magnet, just like itself, is approaching from the other side of the surface of the superconductor.  At some distance, the magnet's north pole will start to repel the "other magnet's north pole", which is really a reflection of its own.  It doesn't matter if it is a north or south pole, it will act the same way.  This is the Meissner effect where a magnet will float, or levitate, above a superconductor.
To describe the motion qualitatively after this is easy.


hi guys

has anyone received invitation to waterloo seminar based on EUCLID mark yet?

thanks!

the marks are not out yet

but' i dunno if they send it before they post marks online

from what i've heard, all papers have been marked already =(

panick panick

So, if you are in gr. 10, what mark do you need to get invited?

 :maybe:  :maybe:

Where and when is the seminar?
will gr 9's be invited?

Seminar is June 10-16 this year, usually it is held during the middle week of June.

Grade 9s are invited but it is very unlikely.
(Last yr a grade 9 won Euclid but was not invited, same happened the year before).
Unless you pwn CMO or make IMO.

[quote="cynthia1991"]Most ppl that are invited are Gr11, right?[/quote]

yes most ppl that are invited are in gr. 11


calculus
integration
number theory proposed
number theory

Find all integral solutions $ (x,y)$ of the equation
\[ \frac{1}{x^2y} \plus{} \frac{1}{x^2} \plus{} \frac{2}{y} \equal{} 1.\]

one of the fraction must be at least $ \frac{1}{3}$ .now just consider the 3 cases and then the value of $ x$ or $ y$(or both of them) will be at maximum 6.the rest is trivial


Hi all, just a quick question

In our chemistry class we are currently learning to balance equations using these methods and, truthfully, in the time that I use to actually figure out how to apply these methods, I could have used some mental math and balanced the equation myself. And for some, more complicated reactions these methods just seem to deter me even more from the correct answer.

I'm just wondering if anyone can perhaps explain an easier way to understand these methods that might aid me in my equation balancing, and hopefully to explain it to my class (My chemistry teacher himself doesn't understand the purpose of these methods, so if there actually is a purpose it would be nice to know for all of our sakes! :P)

Thanks in advance!

You are absolutely right.  Any methods for balancing equations other than a quick mental observation are pointless as they waste time and do tend to accumulate errors.  Unless your teacher is specifically grading you on the use of these methods, I would advise your class to simply ignore them.

i know some cool methods of balancing formulas, but you will have to wait for some time since i have to study Chem Ehglish first...

If you can't do it in your head, set up a system of equations.

Yeah, I don't find balancing equations a problem, just wondering if there was any substance to these methods.

Well, they basically center around equalizing lost and gained electrons.  I tend to balance by half-rxn if there are any tricky H+ or OH- reactants running around.

Balancing by inspection is fine, of course, as long as the charge balance is checked.  Getting the charges to balance is what causes problems for most students.  Hence the systematic methods you mentioned.

Either the half-reaction or oxidation number methods should yield the correct answer.  I never teach both to my students, btw.

as a matter of fact, i like the half reaction balancing methde, more than others... :D

Yeah, we just finished the test for that stuff, and of course the second after the test ended, I realized that they weren't at all that hard to do.  Luckily there weren't any questions on it (half reaction) because our Chem teacher knew that no one would get them. But he did have 2 for extra credit. While doing them, I realized what I didn't know, so I went back to the book and then read it, looking for what I wanted to know and figured out how to do it!

And, Entropy, both of them were contained into the same section in our chemistry book. It says that the half-reaction method is best for ionic-compounds, and oxidation can be used for others.

Well, good thing is I know how to use them now, even if it is past the test :P

I usually balance by inspection when the compunds are fairly simple (especially if each atom appears in only one compound).  If not, I'll half-rxns if the water and H+/OH- aren't already put in (to figure out where they'll go, because I'm lame like that); oxidation state, otherwise.


calculus
integration
function
real analysis
real analysis unsolved

find non negative unbounded function f on [0,infinity) s.t.  it's riemann integrable and integral f on
  [0,infinity) is finite! :D

I'm afraid that you'll encounter at least two severe problems when trying to integrate an unbounded function over an unbounded set in the Riemann sense ;). Did you actually mean "Lebesgue integrable"?

An example: $f(x)=\sum_{n=1}^{\infty}\max\{0,n-2^{n}|x-n|\}$. The improper integral exists in the Riemann sense.

$f(x) = x$ on integers and $f(x) = 0$ otherwise.


% MathType!MTEF!2!1!+-
% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr
% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9
% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x
% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGceaqabeaacaqGSb
% GaaeyzaiaabshacaqGGaGaaeyyaiaabYcacaqGIbGaaeilaiaaboga
% caqGGaGaaeOpaiaabccacaqGWaGaaeilaaqaaiaabcfacaqGYbGaae
% 4BaiaabAhacaqGLbGaaeiiaiaabshacaqGObGaaeyyaiaabshacaqG
% 6aaabaWaaabuaeaadaWcaaqaaiaadggadaahaaWcbeqaaiaaikdaaa
% GccqGHRaWkcaWGIbGaam4yaaqaamaabmaabaGaamOyaiabgUcaRiaa
% dogaaiaawIcacaGLPaaadaahaaWcbeqaaiaaikdaaaaaaaqaaiaadg
% gacaGGSaGaamOyaiaacYcacaWGJbaabeqdcqGHris5aOGaeyyzIm7a
% aSaaaeaacaaIZaaabaGaaGOmaaaaaaaa!5DD7!
\[ \begin{array}{l}
 {\rm{let a}}{\rm{,b}}{\rm{,c  >  0}}{\rm{,}} \\
 {\rm{Prove that: }} \\
 \sum\limits_{a,b,c} {\frac{{a^2  \plus{} bc}}{{\left( {b \plus{} c} \right)^2 }}}  \ge \frac{3}{2} \\
 \end{array}
\]

[quote="Nguyen The Ky Cuong"]
\[ \begin{array}{l} {\rm{let a}}{\rm{,b}}{\rm{,c > 0}}{\rm{,}} \\
{\rm{Prove that: }} \\
\sum\limits_{a,b,c} {\frac {{a^2 \plus{} bc}}{{\left( {b \plus{} c} \right)^2 }}} \ge \frac {3}{2} \\
\end{array}
\]
[/quote]
Nice!My proof
$ \begin{array}{l}
 \sum {\frac{{a^2  \plus{} bc}}{{(b \plus{} c)^2 }}}  \ge \frac{3}{2} \\
  \Leftrightarrow \sum {\frac{{2a^2  \minus{} b^2  \minus{} c^2 }}{{(b \plus{} c)^2 }}}  \ge 0 \\
  \Leftrightarrow \sum {(a^2  \minus{} b^2 )(\frac{1}{{(b \plus{} c)^2 }} \minus{} \frac{1}{{(a \plus{} c)^2 }}} ) \ge 0 \\
  \Leftrightarrow \sum {(a \minus{} b)^2 } \frac{{(a \plus{} b \plus{} 2c)(a \plus{} b)}}{{(b \plus{} c)^2 (a \plus{} c)^2 }} \ge 0 \\
 \end{array}$
How do you arrive this inequality? :lol:

[hide="solution"]
We can assume w.l.o.g $ a\ge b \ge c$
So Using the fact that
$ \sum \frac {a}{b \plus{} c} \ge \frac {3}{2}$
It suffices to show that

$ \sum \frac {a^2 \plus{} bc}{(b \plus{} c)^2} \minus{} \sum \frac {a}{b \plus{} c} \ge 0$

$ \sum \frac {(a \minus{} b)(a \minus{} c)}{(b \plus{} c)^2} \ge 0$

Now let $ \frac {1}{(b \plus{} c)^2} \equal{} x,\frac {1}{(a \plus{} c)^2} \equal{} y,\frac {1}{(b \plus{} a)^2} \equal{} z$
Sine $ (x,y,z)$ and $ (a,b,c)$ are similarly sorted we have the generalisation of Schur's Inequality

$ x(a \minus{} b)(a \minus{} c) \plus{} y(b \minus{} a)(b \minus{} c) \plus{} z(c \minus{} a)(c \minus{} b) \ge 0 \qquad Q.E.D$  :lol: [/hide]


algebra
polynomial
system of equations
algebra unsolved

Prove that the polynomial $ X^4 \minus{} 4X^2 \plus{} 16$ is irreducible over $ Q$.
Well,it's trivial.What is the shortest solution to this,i need to know.
For example,we can try to write $ X^4 \minus{} 4X^2 \plus{} 16\equal{}(X^2\plus{}aX\plus{}b)(X^2\plus{}cX\plus{}d)$ and show that the resulting system of equations doesn't have solutions in Q.
Is there a more simple way?

Let's solve a a more general problem- when is $ x^4 \plus{} ax^2 \plus{} b$ is irreducible over Q?
First of all, when $ a$ and $ b$ are not both rational, it can't be reducible (because $ Q[x]$ is closed under multiplication).
Otherwise, if there is a rational root, it is reducible (we only need to check a few cases because of the Rational Root Theorem).
When there are no rational roots, it is reducible iff it can be factored as $ x^4 \plus{} ax^2 \plus{} b \equal{} (x^2 \plus{} \lambda_1x \plus{} \lambda_2)(x^2 \plus{} \lambda_3x \plus{} \lambda_4)$ (where $ \lambda_i$ are rational). Expanding and comparing coefficients gives the following system:
$ \lambda_2\lambda_4 \equal{} b$
$ \lambda_1 \plus{} \lambda_3 \equal{} 0$
$ \lambda_3\lambda_2 \plus{} \lambda_1\lambda_4 \equal{} 0$
$ \lambda_1\lambda_3 \plus{} \lambda_2 \plus{} \lambda_4 \equal{} a$

It yields that $ \lambda_1 \equal{} \minus{} \lambda_3$. If they are both 0, then the polynomial is reducible iff there are rational solutions to $ x^2 \plus{} ax \plus{} b$.
Otherwise, we assume that they are non-zero and get: $ \lambda_2 \equal{} \lambda_4, \lambda_2^2 \equal{} b$, so $ b$ must be a square of a rational and also it follows that $ \lambda_1^2 \equal{} 2\lambda_2 \minus{} a$.
Conclusion: it is reducible iff $ a$ and $ b$ are in $ Q$, and one of the following holds:
1. There's a rational root,
2. $ a^2 \minus{} 4b$ is a square of a rational (equivalent to: $ x^4 \plus{} ax \plus{}b$ can be factored as $ (x^2 \plus{} s)(x^2 \plus{} t)$)
3. $ b$ is a square of a rational, and one of $ \pm2\sqrt {b} \minus{} a$ is rational.

In our case: there are no rational roots: it suffices to check $ \pm 2^i, i \equal{} 0,1,\cdots, 4$, but actually $ x^4 \minus{} 4x^2 \plus{} 16 \equal{} x^2(x^2 \minus{} 4) \plus{} 16$, so when $ |x| \ge 2$, $ x$ can't be a root, and also $ \pm 1$ are not roots because an integer root must be even.
In addition, $ 4^2 \minus{} 4 \cdot 16 \equal{} \minus{} 48$ is not a square so there is no 'trivial' factorization.
So, it is enough to show that $ \pm2\sqrt {b} \minus{} a$ are not squares, and this is $ \minus{} 4$ or $ 12$ - not squares, QED.


Support
HCSSiM
summer program
Mathcamp
SuMAC
Ross Mathematics Program
PROMYS

Hi,

I'd like to know if there is any summer program for students from all around the world. Because I'm from germany and here there aren't such great things like this.

Thnx for help

I believe that many, if not most, of the US high-school summer programs welcome international students.  (The college summer programs are generally NSF-funded, which means they can't support international students.)  Definitely HCSSiM and Mathcamp and Michigan Math/Science Scholars are happy to have international applicants.  I'm not sure about SUMaC or Ross or PROMYS (anyone else know?).  In any case, if you look under Resources (left sidebar menu) and click on Internet Guide and then the Summer Programs tab, you'll find links to the abovementioned programs and more.  A more comprehensive list (but with lots of local, not necessarily national or international, programs) is at [url]http://www.ams.org/employment/mathcamps.html[/url].

at SUMaC, 8/33 kids were international. including one from germany. 9 were californian. go figure.


Let $n$ be a positive integer and let $a_1, \dots, a_n$ be arbitrary positive reals. Determine with proof the smallest real number $k$ such that

\[ \sum_{i=1}^n \frac{a_i}{ka_i+a_{i+1}} \le \frac{n}{k+1}  \]

for all $(a_1,\dots,a_n)$, where $a_{n+1}$ denotes $a_1$.

It's not much, but here's a start:

Let $b_i = \frac{a_{i+1}}{a_i}$ so $b_1b_2\cdots b_n = 1$ and the inequality is equivalent to
\[ \sum_{i=1}^n \frac{1}{k+b_i} \leq \frac{n}{k+1}. \]
For $n=2$ we can expand it directly to obtain the equivalent $(b_1+b_2-2)(k-1) \geq 0$ which holds for all $k \geq 1$ since $b_1 + b_2 \geq 2$ by AM-GM.

Now, for the general case let $b_1 = b_2 = \cdots = b_{n-1} = c$ for some constant $c$ so $b_n = \frac{1}{c^{n-1}}$ and if we plug that in expand... maybe something useful pops up?

The reverse inequality is true for k=1, right?

I think the best constant is $n-1$ and the resever inequal true for $\frac{1}{n-1}$

agree,and I also think it has been discussed before.


probability
logarithms
linear algebra
matrix
vector
algorithm
probability and stats

This may be better suited for G&FF but, since it requires good understanding of probability and at least some knowledge of analysis, I'm posting it here. It was a puzzle given to me by one of my friends. I liked it so much that I decided to share it.

In some intergalactic prison with [b]really huge[/b] number of prisoners, the warden decided to get rid of all the prisoners by either releasing or executing them all. On the next day all the prisoners will be brought to the prison yard and the guards will put randomly a black or a white hat on each prisoner (independently and with probability 1/2 each), so that each prisoner will be able to see all hats except his own. Then the prisoners will be brought to the warden's office one by one where they will be asked about the color of their own hats. Each prisoner can say either "black", or "white", or "don't know". No prisoner will know other people's answers.

If all prisoners say "don't know" or if at least one of them gives a definitive answer ("black" or "white") and is wrong, everybody gets executed. If at least one person gives a definitive answer and everybody who gives a definitive answer is correct about his hat color, they all get released.

Today the prisoners are allowed to get together and develop any strategy they want. The task is to find a strategy that allows the prisoners to get released with probability at least $0.999$.

This looks like a fun problem.  Here's my idea, although it's definitely not a complete solution.

Let $n$ be the number of prisoners.  Let's imagine the prisoners lined up in a row with their hats on.  What is the longest run of consecutive prisoners with the same color hat?  It's going to be very close to $\log_{2}n$ with high probability.  Let's assume that the longest run is a particular number $k(n)$ with high probability.  Actually, I don't think that strong a statement is true, but something like it should be true.

With that assumption, here will be the strategy.  If a prisoner sees the previous $k$ hats are the same color, then he or she will announce the opposite color.

Like I said, this is just an idea...  Am I on the right track?

This is precisely [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?&t=31478]Todd Ebert's hat problem.[/url]

The solution depends on error correcting codes. It can be shown that if there are $n$ prisoners, the best you can do is a probability of survival of $\frac{n}{n+1}.$ This upper bound can be achieved whenever $n=2^{k}-1$ by a perfect Hamming error-correcting code.

I described the $n=3$ case on that other topic.

I do like to see my current colleague and former student, Todd Ebert, get credit for this - it seems to have passed from his hands into "folklore" in a matter of months.

Here's my proof of that upper bound for the probability of survival. Define random variables $X_{j}$ by saying that $X_{j}=1$ if the $j$th person guesses correctly, $X_{j}=-1$ if he guesses incorrectly, and $X_{j}=0$ if he doesn't guess. The one thing you can't beat about the setup: $E(X_{j})=0$ for each $j.$ That in turn means that $E\left(\sum_{j=1}^{n}X_{j}\right)=0.$

$P(\text{survival})\le P\left(\sum_{j=1}^{n}X_{j}>0\right)= P\left(\sum_{j=1}^{n}X_{j}\ge 1\right).$

(That last equality simply because we're dealing with integer-valued functions.)

Let $Y=\sum_{j=1}^{n}X_{j}$ and let $A$ be the set $\{Y\ge 1\}.$

$Y\ge 1$ on $A$ and $Y\ge-n$ on $A^{C}$. Hence,

$0=E(Y)\ge 1\cdot P(A)-n(1-P(A))=(n+1)P(A)-n$

Rearranged, that gives $P(A)\le\frac{n}{n+1},$ which in turn gives that the probability of survival does not exceed $\frac{n}{n+1}.$

Now let $p(n)$ be the optimized probability of survival given $n$ participants. We know three things. The first is that $p(n)$ is a nondecreasing function. (If you have an strategy that achieves $p(n)$ and if you add one more participant, then that participant can simply not guess himself and be ignored by all the others, while they pursue the previous strategy.) The second, given above, is that $p(n)\le\frac{n}{n+1}.$ Finally the third thing is that that upper bound can be achieved for $n=2^{k}-1.$ That's where the construction of Hamming codes comes in.

Looks like I was way off.  The funny thing is now I remember reading about this problem in the New York Times (Science section) about 5 years ago.

Clever problem and solution.

A little more explanation in the $n=2^{k}-1$ perfect code case. Fix an order for the $n$ prisoners and consider an arrangement of hats to be an ordered $n$-tuple of bits. There are $2^{n}$ possible "words" (arrangements of hats.) The Hamming code consists of a set of $\frac{2^{n}}{n+1}=2^{2^{k}-k-1}$ of these words. Call this distinguished set the set of "code words." Then every word either is a code word itself, or can be changed to a code word in exactly one possible way by changing one bit.

The prisoners' strategy is this. Each prisoner can see all but one hat. Either it is possible to assign the missing bit so as to have a code word (if this is possible, then the assignment is unique), or it is not possible to make a code word with either assignment of the missing bit. If there is no code word available, the prisoner does not guess. If the missing bit can be assigned so as to make a code word, then that prisoner "guesses the error" - that is, guesses that his hat is the wrong color to complete the code word.

If the actual arrangement of hats is not a code word, then there is exactly one way to change one of the bits to make it a code word. The prisoner corresponding to that bit guesses that it's not a code word, and in so doing, gets his own hat color right; every other prisoner does not guess, and they all survive. This happens for each of the $\frac{n}{n+1}\cdot 2^{n}$ words that are not code words - in other words, with probability $\frac{n}{n+1}.$ On the other hand, if the actual arrangement is a code word, then every prisoner guesses, and every prisoner guesses wrong. This happens with probability $\frac{1}{n+1}.$

Before the hat procedure begins, each prisoner has an $\frac{n}{n+1}$ probability of survival; but the moment a prisoner learns that he must personally submit a guess, his odds of survival go down to 50-50.

To create the code for $n=2^{k}-1:$ let $M$ be the $k\times (2^{k}-1)$ matrix whose columns consist of all $n=2^{k}-1$ possible nonzero vectors in $(\mathbb{Z}_{2})^{k}.$ The set of code words is now the null space of this matrix. Since the matrix has rank $k$, the null space has dimension $2^{k}-k-1$ and thus has $2^{2^{k}-k-1}$ elements. There's even a simple decoding algorithm: arrange the columns of $M$ in the order of the binary expansions of the numbers $\{1,2,\dots2^{k}-1\}.$ Given a word $x$ (considered as a column vector), compute $Mx.$ If $Mx=0,$ then $x$ is itself a code word. Otherwise if $Mx=y,$ then read $y$ as the binary expansion of the integer $q.$ We can change the $q$th bit of $x$ to produce the nearest code word.

To Kent: A marvelous solution! As to crediting the author, I will tell my friend where the problem came from and he will, probably, tell the person whom he heard it from, but I do not guarantee that this will spread "in a matter of months" :P

To RaviB: You were way off from the best possible solution but your idea can be used to get a $1-\frac 1{\ln n}$ bound or something like that. Only it doesn't work with runs. What you need instead is to split the prisoners into groups with $m$ persons in each group and tell each prisoner to say the opposite color if he sees that all other hats in his group are of the same color and "don't know" otherwise. I leave the correct choice of $m$ for this strategy to you.

The connection to error-correcting codes was there from the beginnings of the problem; when I give that Hamming code construction, I'm only passing on what I learned along with the problem in the first place. I hadn't seen a proof of that $p(n)\le\frac{n}{n+1}$ before I came up with what I showed above - of course, that was all several years ago.


I need some help with the following

A shepherd has some sheep.  He buys 3 more
sheep.  Now he has 7 times as many sheep
than if he had sold 3 sheep instead of buying
3 sheep. How many sheep does he have now?

Unless I misread the question, it should be set up like this:

$x+3=7(x-3)$, so $x=4$ and he has $7$ sheep right now.

A shepherd has some sheep. He buys 3 more
sheep. Now he has 7 times as many sheep
than if he had sold 3 sheep instead of buying
3 sheep. How many sheep does he have now?

x + 3 = 7(x-3)

6x = 24

x = 4

x + 3 = 7

I think that's right

Should this be moved to Mathcounts or something lower? ;) But I guess Muhammad is a new member so it's okay.

[quote="dakyru"]He just wanted a hint!   :P[/quote]

Lol, I was wondering what "hit" meant :rotfl: This is a simple word problem, though, it should probably be moved.

There really is no point in moving it because the problem has already been solved.

1st of all my keyboard is not working properly thats y i mistyped hint
nd 2nd i know that the value of x is 4
but some body told me that its answer is 27 thats y i was confused that how can it be that my answer is wrong.

Anyways thanks for confirming my answer

Muhammad ,Dont take these professional guys and their  :rotfl:  :rotfl:  to seriously
cause you will get use to it  :lol: , but
cause you are a new fellow , if you want to post some problems just asked the moderators for some helps .
their ids are indicated by green.
welcome aboard and happy problem solving

P.S.When this "some one" told you that the answer is 27, simply there exist some better reactions rather than asking the other:
1.just show him(or her :lol: ) your solution.
2.prove that 27 can not be the answer.
3.ask him\her , his\her solution.


Find the set of 7 possible integers,denote by $A$ such that the number of the set of number $(x,y,z)$ satisfying $x,y,z\in A,x\neq y$ and $x+y=z$ is greatest
(may be $A=\{1,2,3,4,5,6,7\}$)

$A=\{a_1,a_2,a_3,a_4,a_5,a_6,a_7\},0<a_1<a_2<a_3<a_4<a_5<a_6<a_7$
Then if $x,y,z\in A,x<y,x+y=z$
(1)$z=a_3$,then there exists at most one such triple $(x,y,z)=(a_1,a_2,a_3)$
(2)$z=a_4$,since $a_1+a_2<a_1+a_3<a_2+a_3$,so there is at most one such triple $(x,y,z)$
Similar,for $z=a_5$,at most two
$z=a_6$ at most two
$z=a_7$ at most three
So there exist at most 9 such triples
And $\{1,2,3,4,5,6,7\}$ make it true.


group theory
abstract algebra
superior algebra
superior algebra solved

Let $G$ be a subgroup in $SL_2(Z)$. Show that the intersection of all finite index subgroups in $G$ is trivial.

Let $x\in G$, $x\neq I_2$. Chose a prime number $p$ larger in modulus than every entry of $x$.
The natural $\mod p$ application $\pi:G\to SL_2(\mathbb{Z}_p)$ sends $x$ to a nontrivial element.
Therefore $x\not\in ker(\pi)$ which is a group of finite index because $SL_2(\mathbb{Z}_p)$ is finite.

This generalizes to:
The intersection of all subgroups of finite index of a residually finite group is trivial.
A residually finite group is a group such that for all $x$ in it, there exists a morphism from the group to a finite group that doesn't "kill" $x$. $SL_2(\mathbb{Z})$ is a residually finite group, and generally, a subgroup of a residually finite group is residually finite.


Given $ n \ge 3$, find a configuration of $ n$ points in the plane such that the mutual distance of no pair of points exceeds $ 1$ and exactly $ n$ pairs of points have a mutual distance equal to $ 1$.

[hide="I think this works..."]
First, use 3 points to create an equilateral triangle of side length 1.  Call this triangle $ ABC$.  Next, consider the circular arc $ BC$ centered at $ A$.  Simply place the remaining $ n\minus{}3$ points on this arc and you're done.
[/hide]

A very old IMO problem is to prove that you can't have more than $ n$ of the distances be $ 1$. See [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=347432#347432]here[/url].


Six politicians, three red and three blue, are training for a relay race and have put on identical outfits to disguise their political affliction. Either all of the red politicians tell the truth, and all blue ones lie or vice versa. One of the candidates holds a baton as they run together around a circular track in a clockwise direction. Candidate B is in front of Candidate A, C is in front of B, etc., and A is also in front of F as they spread out evenly around the circle. They were all asked the same 2 questions as they passed out evenly around the circle. They were all asked the same two questions as the passed by a reported.

1. Does the candidate in front of you tell the truth?
2. Does the candidate behind you hold the baton?

Their replies are as follows:

Candidate A----- Yes. No.
Candidate B -----No. Yes.
Candidate C -----Yes. No.
Candidate D ------No. Yes.
Candidate E ------No. Yes.
Candidate F -----No .No

Which One is Holding the Baton?

Let's see, I have 2 questions for you.
1. Is this homework?
2. If not, where did you get this problem from?

Well it doesn't say where D and E are positioned, so you can't know if they're in front or in back.
But I'm gonna take a guess and say A has it, since A is a liar and lied about B being a liar so that means B tells the truth, which means A has the baton.

[quote="mathguy999"]its homework...[/quote]
You really shoud not be putting your homework problems on the site, simply because you want other people to answer it for you. The point of homework is to learn the concepts by yourself.

Someone posted the EXACT same problem in the MD section.
I gave a solution.
I suggest you go search for it.

It does say where D and E are positioned. Read the OP and find the "etc." Just follow the given pattern.

How I would solve this problem:

Test each person's statements if A has the baton, if B has the baton, etc.
Then just see which one works.

i guess b is the liar, jz a smart guess, i dun even noe theres such homework for 'geniuses' at ure lvl i persume?

I believe this was posted, here.

http://www.artofproblemsolving.com/Forum/viewtopic.php?t=198257

Locked.


graph theory
combinatorics open
combinatorics

This question shouldn't be too difficult for you guys, but since I don't know for sure if there is a solution I'm posting it here.

There are 6 points somewhere in a plane. We draw a line connecting each two points (15 lines). At the intersection of each of these lines, we get a new point (if the intersection isn't one of the 6 original points). What is the minimum number of new points you can get?

I think it will be the 19 (right?) points you get when the six points are arranged in a regular hexagon, but I can't find a good prove.

Sorry, I had to mention that. No 3 points may be colinair.

But lines may be parallel, or three lines may intersect at one point, like in my example of the regular hexagon.

[quote="manuel"]OK maybe i dont understand the question,
are you asking for a configuration of 6 points in the plane that minimizes the number of crossings of a complete graph in 6 vertices (where the edges can only be straight line segments) ???
if that is the question you can draw a $K_6$ with straight segments joining the vertices and only having 4 crossings.

We know that $K_5 - e$ where $e$ is an edge is planar, so starting with this graph
it is easy to construct a $K_6$ with minimum crossings and straight edges by adding a vertex and some edges, where 3 segments are concurrent.[/quote]

Sorry if my question isn't very clear. But I don't understand your answer neither :-). Could you explain it in terms so that it is understandeble for someone who doesn't know anything about graph theory?

A planar graph is one that can be drawn without crossings.
$K_5$ is not planar but $K_5$ minus an edge is. Moreover we can draw $K_5$ with exactly one crossing and straight edges (the edges of a graph don't have to be straight they just display a combinatorial structure, but in this case they are).
So once you have drawn the $K_5$ with one crossing you can add  a vertex in a place where when you join that vertex to the other 5 can only produce 3 more crossings (to do this one of the new edges has to cross through thr previous crossing of $K_5$.


$a_{1}, a_{2}... a_{n}$vare positive real numbers and they satisfy a condition: $a_{1}\cdot a_{2}\cdot ... \cdot a_{n}=1$. Prove, that \[\frac{1}{1+a_{1}}+\frac{1}{1+a_{2}}+...+\frac{1}{1+a_{n}}\geq 1\] When inequality changes into equality?

[quote="romano"]Using Ravi's substitution : $a_{1}=\frac{x_{2}}{x_{1}}, a_{2}=\frac{x_{3}}{x_{2}},...$ , the problem becomes easy .[/quote]

I still can't find a solution :(

If I'm not mising something obvious this shouldn't be hard.

if $n \geq 2$
$LHS=\sum_{i=1}^{n}{\frac{x_{i+1}}{x_{i+1}+x_{i}}}\geq \sum_{i=1}^{n}{\frac{x_{i+1}}{\sum_{i=1}^{n}{x_{i}}}}=1$

equality holds iff and only if $n=2$ for arbitary $a_{1},a_{2}$.

For $n=1$ this is not true.


function
induction
algebra unsolved
algebra

Let $S$ and $Q$ be the set of nonnegative integers and rational numbers, respectively.
Define the function $f : S \rightarrow Q$ by $f(0) = 0$ and $f(3n+i)=-\frac{3}{2}f(n)+i$ where $i=0,1,2$
Prove that $f$ is one-to-one, and determine its range.

here's a basic outline... the missing details aren't many and can easily be filled in...

an easy induction shows that if $ n = i_ki_{k-1}...i_0 $ in base 3, then $ f(n) = \frac {n_{3,-3}}{2^k} $, where $ n_{3,-3} $ denotes the result of interpreting the base 3 representation of n in base -3.

it's then clear that the range is a subset of the dyadic rationals.  now, choose an arbitrary dyadic rational, $ \frac {N}{2^k} = r $; and attempt to find an n such that $ f(n) = \frac {N}{2^k} $.  let $ n = 3q+i $.  then we need

$ -\frac{3}{2}f(q)+i = \frac {N}{2^k} $

which means we need $ 3 \mid N - i2^k $; note that there's exactly one $ i \in {0, 1, 2} $ for which this happens.  this means the rightmost digit (in base 3) of the n for which $ f(n) = r $ (if it exists, that is.  and in fact it does, as we show below) is unique.  one more, similar step shows that the next-to-rightmost digit of n (in base 3) is unique, and so on.  this proves 1-1'ness.

as for the range... given the arbitrary dyadic rational $ \frac {N}{2^k} = r $, we continue along the described track -- computing digits of a possible n for which $ f(n) = r $ one by one.  observe that during this process, at each step we're seeking to solve a new equation of the form $ f(n) = \frac {N}{2^k} $, with k decreased by 1 from the previous step.  eventually we're left with solving $ f(n) = M $ for some M, which we then reduce to solving $ f(n) = -\frac {M-2i}{3} $, where $ i \in {0, 1, 2} $ is the unique element that makes $ 3 \mid M-2i $.  we do this again and again... til we get to solving $ f(n) = m \in {0, 1, 2} $, which obviously has the solution $ n = m $.  (to show that finitely many applications of $ M \rightarrow -\frac {M-2i}{3} $, where $ i \in {0, 1, 2} $, brings you to one of 0, 1, 2 is relatively easy...)


If a,b,c are real positive numbers, show that
$ \left( {a^3  \plus{} b^3  \plus{} c^3 } \right)^2  \geqslant \left( {a^4  \plus{} b^4  \plus{} c^4 } \right)\left( {ab \plus{} bc \plus{} ac} \right)$

[quote="Dimitris X"][quote="FantasyLover"][hide="Solution"]$ (a^3 \plus{} b^3 \plus{} c^3)^2\ge (a^4 \plus{} b^4 \plus{} c^4)(a^2 \plus{} b^2 \plus{} c^2)$

First part follows from Cauchy-Schwarz Inequality[/hide][/quote]
I dont think so..... :wink:[/quote]

Yes Dimitris' right. But i think $ uvw$ kills it, i didnt try the manipulations though.
For Dimitris-->[hide]Pos ta piges eukleidi? To trito tsimpouse e?[/hide]

[quote="Γιώργος"] But i think $ uvw$ kills it,[/quote]
I agree with you! :)

As suggested, I will try to give a proof by $ uvw$ .
[hide]
Let $ a\plus{}b\plus{}c\equal{}3u ,ab\plus{}bc\plus{}ca\equal{}3v^2$ and $ abc\equal{}w^3$. Therefore, given inequality can be rewritten as :
\[ \left(27u^3 \minus{}27uv^2 \plus{}3w^3\right)^2 \geq \left(81u^4 \minus{}108u^2 v^2 \plus{}18v^4 \plus{}12uw^3\right)\cdot 3v^2\]
\[ \iff f(w^3)\equal{}Aw^6 \plus{}Bw^3 \plus{} C \geq 0\]
where $ A\equal{}9  \ , \ B\equal{}6(27u^3 \minus{}27uv^2 \minus{}6uv^2)$ and $ C\equal{}(27u^3\minus{}27uv^2)^2 \plus{} u^2 v^2(324v^2 \minus{}243u^2) \minus{}54v^6$
We fix $ u$ and $ v^2$, then $ f$ is a convex function of $ w^3$, so it is enough to prove inequality in the boundaries.
$ w^3$ assumes maximum only when two of $ a,b,c$ are equal  and minimum either when two of $ a,b,c$ are equal or when one of them is zero.
Let $ c \rightarrow 0$ , then we have to prove that :
\[ (a^3 \plus{}b^3)^2 \geq (a^4 \plus{}b^4)ab\]
\[ \iff a^6 \plus{}b^6 \plus{}2a^3 b^3 \geq a^5 b \plus{}ab^5\]
Which is obviously true because $ a^6 \plus{}b^6 \geq a^5 b \plus{}ab^5$
Now let $ a\equal{}b$ ,we have :\[ (2a^3 \plus{}c^3)^2 \geq (2a^4 \plus{}c^4)(a^2 \plus{}2ac)\]
\[ \iff 4a^6 \plus{}4a^3 c^3 \plus{}c^6 \geq 2a^6 \plus{}4a^5 c \plus{}a^2 c^4 \plus{}2ac^5\]
\[ \iff 2a^6 \plus{}4a^3 c^3 \plus{}c^6 \geq 4a^5 c \plus{}a^2 c^4 \plus{}2ac^5\]
Which is supposed to be true, but i don't see how -probably easy AM-GM ,or maybe my $ uvw$ solution is all wrong .  arqady ?
[/hide]

[quote="enndb0x"]
\[ \iff 2a^6 \plus{} 4a^3 c^3 \plus{} c^6 \geq 4a^5 c \plus{} a^2 c^4 \plus{} 2ac^5\]
Which is supposed to be true, but i don't see how -probably easy AM-GM ,or maybe my $ uvw$ solution is all wrong .  arqady ?
[/quote]
It's equivalent to $ (a\minus{}c)^2(c^4\minus{}2c^2a^2\plus{}2a^4)\geq0.$ :wink:

Thank you arqady,

When we're looking for the case $ a\equal{}b$, can we say that inequality is homogeneous and then $ a\plus{}b\plus{}c\equal{}1$, so $ c\equal{}1\minus{}2a$ and we are left with only one variable inequality ? I'm not sure because actually $ u$ is  a fixed number...

EDIT: I have found it! See [url]http://www.mathlinks.ro/viewtopic.php?t=299589[/url]. It's equivalent to
$ \frac {1}{2}[(a \minus{} b)^{6} \plus{} (b \minus{} c)^{6} \plus{} (c \minus{} a)^{6}] \plus{} 2[ab(a \minus{} b)^{4} \plus{} bc(b \minus{} c)^{4} \plus{} ca(c \minus{} a)^{4}] \plus{} \frac {1}{2}[a^{4}(b \minus{} c)^{2} \plus{} b^{4}(c \minus{} a)^{2} \plus{} c^{4}(a \minus{} b)^{2}]\ge 0$
It is very strong.

Hey dgreenb801 Can you explain how you obtained this result, please?

Actually, I just did it simply by working out the algebra. I started with the terms $ (a\minus{}b)^6$, $ (b\minus{}c)^6$, and $ (c\minus{}a)^6$ and started with the terms of highest degree of a single variable when I move everything in the original equation to the left, which are $ a^6$, $ b^6$ and $ c^6$. Thus, I knew I had to take half the sum of $ (a\minus{}b)^6$, $ (b\minus{}c)^6$, and $ (c\minus{}a)^6$ to get each of these terms once. Now that I've dealt with terms of highest degree of a single variable, I deal with the terms of second highest highest degree of a single variable, which are $ a^5b$, $ a^5c$, $ b^5a$, $ b^5c$, $ c^5a$, $ c^5b$. There's gonna be $ \minus{}1$ of each of them when I move everything to the left side of the original equation. The $ (a\minus{}b)^6$ term gives me a $ \minus{}3a^5b$ and a $ \minus{}3ab^5$ after expanding it and taking half of it as I said before, so I know I have to add a $ 2ab(a\minus{}b)^4$, which will add a $ 2a^5b$ and $ 2ab^5$ so that we will end up with just $ \minus{}a^5b$ and $ \minus{}ab^5$. Now for the term of the next highest degree of a single variable, and so on. It is pretty tedious, but worth it in the end.


inequalities
function
inequalities unsolved

Let $ m$ and $ n$ be two positive integers with $ m,n \geq 2$. For any $ n$-element set $ A\equal{}\{a_1,...,a_n\}$, create the $ C^n_2$ sums $ a_j\minus{}a_i$ where $ (j>i).$ Let $ A'$ be the ordering of these $ C^n_2$ numbers from least to greatest. Furthermore, let $ A'(m)$ be the number of elements in A' divisible by m.

Given that $ A\equal{}\{a_1,...,a_n\}$ and $ B\equal{}\{1,2,...,n\}$, show that for all $ m \geq 2$, we have $ A'(m) \geq B'(m)$.

is there any constraints on $ {a_i}$? like they're all pairwisely distinct? otherwise the inequality may not hold..... like when $ a_i \equal{}$ constant for all i = 1,2,3,..., n. and 2m<n, we have LHS = 1, RHS >1

First of all, $ m|0$. Hence, when $ a_i\equal{}k$ for all $ i$, we have LHS = $ C^n_2$. ($ A'$ is not a set. It is merely an ordering of the sums.)

Get it~ sorry for that. (just realized it's really stupid question coz the question told us that $ A$ is a $ n$-element 'set')

So here's the solution:
We shall first partition $ A'$ into $ m$ sets $ X_0, X_1, X_2, ..., X_{m \minus{} 1}$ such that $ X_i$ contains all the elements in $ A$ that is congruent to $ i$ modulo $ m$. Let $ x_i \equal{} | X_i | \forall i \equal{} 1,2,3,..., m \minus{} 1$.

As for every two elements in the same set $ x_i$ their difference is divisible by $ m$, while every two elements in different set gives difference that isn't divisible by $ m$, thus:
$ A'(m) \equal{} \displaystyle\sum_{i \equal{} 0}^{m \minus{} 1}C^{x_i}_2$, with $ \sum x_i \equal{} C^n_2$

Now if $ m\geq n$ then as the RHS of the original inequality is zero, the inequality holds trivially.
If $ m < n$, let $ n \equal{} mq \plus{} r$ where $ q$ is the quotient and $ r$ is the remainder when $ n$ is divided by $ m$.
So $ B'(m) \equal{} \displaystyle\sum_{i \equal{} 0}^{m \minus{} 1}C^{y_i}_2$, where $ y_i \equal{} q \plus{} 1 \forall i \equal{} 0,1,2,3,...,r$ and $ y_i \equal{} q \forall i \equal{} r \plus{} 1,r \plus{} 2,r \plus{} 3,...,m \minus{} 1$

The rest of the work shall follows from the following lemma:
For positive integers $ a,b$, if $ 2|a \plus{} b$, $ C^a_2 \plus{} C^b_2 \geq 2C^{\frac {a \plus{} b}{2}}_2$ and if $ 2\nmid a \plus{} b$, $ C^a_2 \plus{} C^b_2 \geq C^{\frac {a \plus{} b \plus{} 1}{2}}_2 \plus{} C^{\frac {a \plus{} b \minus{} 1}{2}}_2$
These two can easily be justified as function $ C^x_2 \equal{} \frac {x(x \minus{} 1)}{2}$ is convex.

From the lemma, we can get that the minimum of function $ f(x_0,x_1,...,x_{m \minus{} 1}) \equal{} \displaystyle\sum_{i \equal{} 0}^{m \minus{} 1}C^{x_i}_2$ is when the difference among $ x_i$ is at most 1, i.e. when $ x_i \equal{} q \plus{} 1 \forall i \equal{} 0,1,2,3,...,r$ and $ x_i \equal{} q \forall i \equal{} r \plus{} 1,r \plus{} 2,r \plus{} 3,...,m \minus{} 1$, which is $ B'(m)$.
Otherwise, if in the minimum case there exist two numbers $ x_i,x_j$ such that $ | x_i \minus{} x_j |\geq2$, then we can find a smaller case for the function $ f$ using the lemma.

Thus the original inequality holds.

Besides can you kindly post all the other questions for this competition? I'm looking forward to it~~ thx~


induction
number theory unsolved
number theory

Let $p\geq 3$be a prime number. The sequence ${a_{n}}_{n\geq}$ defined by $a_{n}=n$  for all $0\geq n \geq p-1$, and $a_{n}=a_{n-1}+a_{n-p}$ for all $n\geq p$compute $a_{p^{3}}(modp)$.

The solution just tell me what $a_{n}$ is and prove it by indution,but i don`t how to get the answer.

See here http://www.mathlinks.ro/Forum/viewtopic.php?highlight=number+theory+sequence&t=23201  :wink:


inequalities
vector
complex numbers
triangle inequality
absolute value
Pythagorean Theorem
geometry

How do you prove

$ |z \plus{} w| \leq  |z| \plus{} |w|$

Where $ z$ and $ w$ are distinct complex numbers in rectangular form? I know how to prove it for real numbers, but the same method doesn't work in the complex plane because we cannot determine, for instance, if $ 3 \plus{} 4i > 0$ (at least as far as I know), which is what's leaving me stuck. How can inequalities with complex numbers be formed at all if introducing complex numbers makes it impossible to compare different number values?

The best way to deal with this compelx triangle inequality is to think about these absolute value signs as "Complex Modulus" signs.

Just as the absolute value of a real number can be defined as the distance that number lies from Zero, we can also define "complex modulus" as the distance a point in the complex plane is from zero.

By a fairly simple application of the pythagorean theorem, for any point $ z \equal{} (a, bi)$ its complex modulus $ |z|$ is just $ \sqrt {a^2 \plus{} b^2}$.

Now given two points $ Z \equal{} a \plus{} bi$, $ W \equal{}c \plus{} di$, we can use our definition of complex absolute value.$ |Z \plus{} W| \equal{} |a \plus{} bi \plus{} c \plus{} di| \equal{} |(a \plus{} c) \plus{} (b \plus{} d)i| \equal{} \sqrt {(a \plus{} c)^2 \plus{} (b \plus{} d)^2}$

See if you can work out the rest of the inequality.

Yeah I understand that fine. I suppose I just made an algebra mistake or something.

In essence, we're trying to show that

$ \sqrt {(a \plus{} c)^{2} \plus{} (b \plus{} d)^{2}} \leq \sqrt {a^{2} \plus{} b^{2} } \plus{} \sqrt {c^{2} \plus{} d^{2}}$

right? from there it's just simple algebra.

"Simple algebra" is somewhat misleading (it's fairly tedious).  Moreover, this is essentially the [b]triangle inequality[/b] in two dimensions; algebraically, the $ n$-dimensional version is known as [b]Minkowski's inequality[/b], and the proof of the general inequality relies on Cauchy.

There is also a diagram way to show this relation. I'll type it up at night time. (diagram will take long)

The algebra IS quite simple. Square the expression, simplify it, then square it again and expand. Lots of letters there, but the task is a no-brainer.

Sorry; I was implicitly referring to the $ n$-dimensional case, although I suppose that wasn't clear.

I think that any n-dimensional version should be analogous to a 2 dimensional plane because we always have that those vectors will be on a plane. Hence we can apply the necessary isometries to map our vectors onto the xy-plane and apply the 2 dimensional triangle inequality.


group theory
abstract algebra
linear algebra
matrix
vector
function
absolute value

here an easy but interesting one:
Let $G$ be a compact subgroup of $Gln(R)$ that contained $O(n)$ the group of orthogonal Matrices.
Prove that $G=O(n)$

I'll in words, mostly (I hope it works):

Assume there is at least one matrix $A$ in our group which is not orthogonal. Then multiplication by $A$ of column vectors is not an isometry, so there is a vector ${\bf x}$ s.t. $\|A{\bf x}\|\ne \|{\bf x}\|$.

We can find an orthogonal matrix $T_1$ s.t. the first column of $T_1A$ has the same direction as ${\bf x}$ (and it has the same length as the first column of $A$, of course, because $T_1$ is an isometry). After this we multiply $A$ with $T_1A$ and we obtain a matrix having the first column with the same direction as $A{\bf x}$, and length different from that of the first column of $A$. We can now repeat the process: find an orthogonal matrix $T_2$ s.t. the first column of $T_2AT_1A$ has the same direction as ${\bf x}$, and look at the first column of $AT_2AT_1A$, etc.

Taking the limit of the length of the first column of $AT_nA\ldots AT_1A$, we obtain either $0$ (in which case our set contains a singular matrix, since the set is closed) or $\infty$, in which case our set is unbounded and thus not compact.

I was trying the following idea for proof: if $A\in G$ and $A\not\in O$, then WLOG, $A^TA=D$, diagonal, and $d_{1,1}>1.$ The only problem with this approach: it is easy to show that as $n\to\infty$, $(A^TA)^n$ is unbounded. But does that make $(A^n)^TA^n$ unbounded?

By the way, we do need the condition that $O(n)\subset G.$ Grobber used that explicitly when he multiplied his original matrix $A$ by various orthogonal matrices $T_1,T_2,\dots.$

As an example of why we have to have that condition:

Let $P=\begin{bmatrix} 1 & -5 \\ 2 & -1 \end{bmatrix}$ and let $G=\{e^{tP}:t\in\mathbb{R}\}.$ Then $G$ is a compact group which can also be written as the set of all matrices of the form

$\begin{bmatrix} \cos3t+\frac13\sin3t & -\frac53\sin3t \\
\frac23\sin3t & \cos3t-\frac13\sin3t \end{bmatrix}$ for $t\in\mathbb{R}.$

$G$ is a compact group, but the matrices it consists of are not orthogonal. However, $O(2)\not\subset G$, as well.

very nice and intuitive solution Grobber. Mine was as following:
let $A \in G$. $A=OS$ where $O$ is orthogonal and $S$ symetric positive.
Then $S=O_2D{O_2}^T$ where $D$ is diagonal with positive coefficients. But $D \in G$
so its eigenvalues must be equal to 1. So $A$ is orthogonal.

I was thinking about the another approach which has stuck in a point.

At first, since $O(n)$ is a connected component of the identity, then it is normal in $GL(n, \mathbb{R}).$  Therefore, if one shows that $GL(n, \mathbb{R})/O(n)$ is a simple group, it implies that $O(n)$ is a maximal normal subgroup of $GL(n, \mathbb{R}).$ I wonder, what is the structure of $GL(n, \mathbb{R})/O(n)$ as a topological group?

[quote="ehsan2004"]I was thinking about the another approach which has stuck in a point.

At first, since $O(n)$ is a connected[/quote]

?

[quote="ehsan2004"]component[/quote]

??

[quote="ehsan2004"] of the identity, then it is normal in $GL(n, \mathbb{R}).$[/quote]

???

Sorry, but I think you should re-read this topic...

[quote="darij grinberg"]Sorry, but I think you should re-read this topic...[/quote]

Hmmm... I realized that $O(n, \mathbb{R})$ has two connected components, which I was wrong. Maybe I mixed it up with $U(n).$

BTW thanks for your correction.

If there existed some $G$ contained $O(n)$ as a proper subset, then we could fix some $A \in G$ such that $\det A \neq \pm 1$ with $\det A$ the determinant of $A$. We can assume without loss of generality $|\det A| > 1$ since groups are closed under inverses, and note that by closure that $A^n \in G$ for all $n \in \mathbb{N}$. From here, the determinant function and the absolute value function are both continuous, so if we take $f(X) = |\det X|$ then the image $f(G)$ should be compact, but since the subgroup generated by $A$ has an unbounded image under $f$, this contradicts the continuity of $f$ and so all elements of $G$ must have determinants $\pm 1$ which is to say, be an element of $O(n)$ which is the desired result.


calculus
derivative
limit
trigonometry
calculus computations

f:R->R, |f(x)-x|<=x*arctgx ... show that f'(0) exists and its value is 1.
Could someone please tell me how should I begin this?

First you write the definition of a derivative in $ x\equal{}0$:

$ \lim_{x \to 0}(\frac{f(x)\minus{}f(0)}{x})$.

Therefore you must calculate $ f(0)$ from the given conditions. After you know the value of $ f(0)$, try to make the left hand side similar to the above definition of derivative.

One note: since $ \tan^{\minus{}1}x$ behaves like $ x$ near zero, there is no practical difference between the condition you were given and the condition $ |f(x)\minus{}x|\le x^2.$ If you were given the latter problem, what would you say?


trigonometry
inequalities
algebra
polynomial
triangle inequality
calculus
calculus computations

Hi, does anyone know how to solve this question?

 1.) a.) By using  lim sinθ=0 and lim cosθ=1, prove f(x)=sinx and g(x)=cosx are both continuous for all values of x.
 ..............................θ->0...............θ->0

b.) for f(x)={x if rational, 0 if not irrational)
     Using epsilon and delta,

     i.) Prove f is not continuous at x=1
     ii.) Prove f is continuous at x=0

Thanks a lot

1) Write $\sin(x+\alpha)=\sin x\cos \alpha+\sin\alpha\cos x$.  Use the given limits (if you need to do this in terms of epsilons and deltas, it shouldn't be hard to rewrite it accordingly - you would just subtract out $\sin x$ and use the triangle inequality)

2) Say that $a\not=0$.  Then if $|x-a|<\delta$, there exists some rational $k$ in that interval such that $|f(k)|>|a|$.  There also is an irrational $l$ in that interval, so we have $f(l)=0$.  Combine these, and we see that for every $\delta>0$ and $a\not=0$, there exists $y$ with $|y-a|<\delta$ such that $|f(y)-f(a)|>|a|$ (divide into cases based on whether $a$ is rational or irrational).  In particular, $f$ is not continuous at $a$.

Next, say that $a=0$.  Then $|f(x)-f(a)|=|f(x)|\leq |x|$.  So given $\epsilon>0$, take $\delta=\epsilon$.  Then $|x|<\delta$ implies $|f(x)|<\epsilon$, so $f$ is continuous at $0$.

I hope I didn't make any mistakes, but it's 2am over here, so who knows.  I guess I'll see in the morning.

[quote="blahblahblah"]Say that $a\not=0.$ Then if $|x-a|<\delta,$ there exists some rational $k$ in that interval such that $f(k)>a$[/quote]
Let's clean this up a little bit:

Say that $a\ne 0,$ Choose any $\delta <\frac{|a|}2.$ Then $\exists$ a rational $k$ with $|k-a|<\delta$ such that $|f(k)|=|k|>\frac{|a|}2.$

Then proceed as above, but choosing $\epsilon < \frac{|a|}4.$

As you said, 2 a.m. proofs need to be looked at in the morning.

[quote="Kent Merryfield"]As you said, 2 a.m. proofs need to be looked at in the morning.[/quote]

That's nothing - I wrote my analysis midterm last week on 3 hours of sleep, and I stated that all polynomials are compactly supported.


hello, write your equation in the following form:
$ \frac {2\tan\left(\frac {1}{2}x\right)}{1 \plus{} \tan^2\left(\frac {1}{2}x\right)} \plus{} \frac {1 \plus{} \tan^2\left(\frac {1}{2}x\right)}{1 \plus{} \tan^2\left(\frac {1}{2}x\right)} \equal{} \frac {2\tan\left(\frac {1}{2}x\right)}{1 \minus{} \tan^2\left(\frac {1}{2}x\right)}$.
Setting $ t \equal{} \tan\left(\frac {1}{2}x\right)$ you get the equation
$ \frac {2t}{1 \plus{} t^2} \plus{} \frac {1 \minus{} t^2}{1 \plus{} t^2} \equal{} \frac {2t}{1 \minus{} t^2}$.
You can solve this.
Sonnhard.

[size=117][color=darkred]Hello, [b]Dr. Sonnhard Graubner[/b], please write correctly your proof ! [/color][/size]

$ \sin x \plus{} \cos x \equal{} \tan x$ $ \Longleftrightarrow$ $ \frac {2\tan\frac {x}{2}}{1 \plus{} \tan^2\frac {x}{2}} \plus{} \frac {1 \minus{} \tan^2\frac {x}{2}}{1 \plus{} \tan^2\frac {x}{2}} \equal{} \frac {2\tan\frac {x}{2}}{1 \minus{} \tan^2\frac {x}{2}}$.
Setting $ t \equal{} \tan\frac {x}{2}$ you get the equation $ \frac {2t}{1 \plus{} t^2} \plus{} \frac {1 \minus{} t^2}{1 \plus{} t^2} \equal{} \frac {2t}{1 \minus{} t^2}$ $ \Longleftrightarrow$
$ \left|t^2 \minus{} 1\right| \equal{} 4t^3$ which has only two real roots $ 0 < t_1 < 1 < t_2$ ( graphically ! ).

hello, thank your for your hint.
Sonnhard.

sorry but I conculated as follow:
\[ \frac {{2t}}{{1 \plus{} t^2 }} \plus{} \frac {{1 \minus{} t^2 }}{{1 \plus{} t^2 }} \minus{} \frac {{2t}}{{1 \minus{} t^2 }} \equal{} 0
\]

\[ \Leftrightarrow \frac {{t^4 \minus{} 4t^3 \minus{} 2t^2 \plus{} 1}}{{(1 \plus{} t^2 )(1 \minus{} t^2 )}} \equal{} 0 \\
\]

In general this euation is not hard cause we have the formula to solve the quartic equation! But can anybody find another solution which is nicer than the above solutions?

$ \sin x \plus{} \cos x \equal{} \tan x\Longleftrightarrow \cos x(1 \plus{} \tan x) \equal{} \tan x$
Squaring both sides and use $ 1 \plus{} \tan ^ 2 x \equal{} \frac {1}{\cos ^ 2 x}$, we have $ (1 \plus{} \tan x)^2 \equal{} \tan ^ 2x (1 \plus{} \tan ^ 2 x)$.
$ \therefore \tan ^ 4 x \minus{} 2\tan x \minus{} 1 \equal{} 0$.


Sue has 122 crates of the same size. Each crate contains at least 90 apples and at most 100 apples. Crates containing the same number of apples are stacked one on top of another in their own stack. Not all of the stacks have the same number of crates. What is the least possible number of crates in the tallest stack of crates?

There are 11 possibilities for crats (90,91,92,93,94,95,96,97,98,99,100), so by pigeonhole, there must be at least 12 in one stack.


MATHCOUNTS
number theory
prime factorization

The product of two positive 3-digit palindromes is 436,995.  What is their sum?

[hide="palindromes are..."]Palindromes are numbers that read the same forwards as backwards.  Examples, 12321, 1001, 555...[/hide]

[hide="Educated guess and check"]
585 * 747
[/hide]

I remember this from last year. It took everyone forever to do it. Is there any way to narrow down the numbers further than 5_5 * _ _ _?

Yes, I know that once you know the 5_5, you can find the other number by dividing. But is there a way to narrow down the possibilities for 5_5?

[quote]But is there a way to narrow down the possibilities for 5_5?[/quote]
Once you know, one number is 5_5 it is easy to know the other number as 7_7 (Beccause  43xxxx divided by something like 500+ will give 7_7 -  specially if you notice that 8 being even 8_8) is not possible.)

Once you know that, and if you notice the original number is divisible by 9 (check sum of digits) one of the number 5_5 (or 7_7) must be divisible by 9 only  way you can add  5+5+something  (5+5=10; 1+0 = 1; and 9-1=8) so either one number has to be 585 or the other 747 .. luckily you would be right in both the counts...:)

Gyan's solution narrows it down considerably, but is there a way to solve it algebraically?  What about a more general solution?

how can it be solved using algebra? the fuctions are not identical...  :huh:

[quote="risinglegend"]yea i think it can be worked out using algebra[/quote] How??  :?:

I did what Treething probably did (knew that the first number ends and therefore starts with 5, then divided 436995 by 515 and 595 to get 7_7, then guessed and checked). This is a Mathcounts problem, therefore there should be a faster way than prime factorization or algebra. I like Gyan's idea.

Well, since its a workout problem, and you know that the first number is 5_5, couldnt you just repeatedly divide 436995 by 505, 515, ..., 595 on a calculator?

That's what I remember doing last year.

Again, Gyan's solution: now that you have 5_5 and 7_7, and that the original number is divisible by 9, one of the factors also does, and you can narrow it down even further than anyone else has been doing. :cool:

EDIT: Of course, it is possible that each factor is divisible by 3 and not 9... but I haven't checked that.


Find all nonnegative integer solutions to
3^x - y^3 = 1.

Find all pairs of nonnegative integers x,y that solve
p^x - y^p = 1
where p is a given odd prime.

isn't there an infinite number of solutions to the first one?

ok, then
i can prove that (0,0) and (2,2) are the only solutions

[quote="darkquantum"]Proof for number 1:

3^x-y^3=1.
3^x=y^3+1
3^x=(y+1)(y^2-y+1)
[/quote]

from here, one could use a slightly different method: y+1 must also be a power of 3, so for some j, we can write y=3^j-1. Then, since as darkquantum says, y^2-y+1 must be a power of 3. Plugging in y=3^j-1, we find that 3^2j-3^(j+1)+3 must be a power of 3. We get 3^(j+1)(3^(j-1)-1) has to be a 3 less than a power of 3 (note that i'm tacitly assuming j>0 when I assume 2j:ge:j+1, but that's ok, I can add in the case j=0 later...) Anyway, the only way for 3^(j+1)(3^(j-1)-1) to be 3 less than a power of 3 is for j to be 1. Any bigger and it will be at least 9 away from a power of 3. Anyways, you can check that j=1 gives (2,2) and adding back the case where j=0, you see that (0,0) also works.

This method isn't anywhere near as elegant as darkquantum's, but it may be easier to generalize to the second equation.

[quote="darkquantum"]for number 2,
do u mean x and y are constants (like actual integers) that will make the expression hold true for all odd primes???[/quote]

no, I think it's for a given prime p. That means, [b]for any[/b] odd prime p, find all order pairs (x,y)...

Lol
u sound as if my solution is a good one...

[quote="darkquantum"]Proof for number 1:

3^x-y^3=1.
3^x=y^3+1
3^x=(y+1)(y^2-y+1)
NOw, since x and y are nonnegative integers, y^2-y+1 must be a power of three.

Thus, y^2-y+1=3^k.
When we solve for y, y is an integer, thus the discriminant ,
1-4(1-3^k), must be an integer.
so 4*3^k-3 is an integer
3(4*3^(k-1)-1) is an integer.
This means that 4*3^(k-1)-1 is a power of 3.
This is only true when k=0,1.
Thus, plugging this back in and solving for y,
we get our only solutions

(0,0) and (2,2)[/quote]

Just wondering, how did you get from 3(4*3^(k-1)-1) is an integer to 4*3^(k-1)-1 is a power of 3..

[quote="darkquantum"]so is the answer to # 2 supposed to be integers, or something expressed in terms of p?[/quote]

Yeah. You are given p, and want to find x and y.

because the only way for sqrt[3(4*3^(k-1)-1)] to be an integer is if (4*3^(k-1)-1) is an odd power of three, so that 3 mulitplied to it will result in a perfect square.

I hope i explained it clearly enough

Hm. I think you missed out the square root when you initially posted it :)

But sqrt (3x) being an integer doesn't mean x is an odd power of 3, it can be an odd power of three times any other square. For example, sqrt(3x12).

[quote="darkquantum"]ok
thx for the catch:
a slight revision is in order:

so,

4*3^(k-1)-1=3^a*x^2.
Let k-1=y for convenience

so 4*3^y=3^a*x^2
4*3^y-3^a*x^2=1.

Now, the left side factors
And if the product of 2 integers is 1, then both must be one.

I think  can work it out from there.[/quote]

So 3^a (4*3^(y-a) - x^2) = 1
So a=0 and 4*3^y - x^2 = 1 or 4*3^y - 1 = x^2. So we're right back where we started..

but the latter is not possible
so we need only consider when its only a power of 3, and not a power of 3 times a perfect square

and, o, if u want to know why the latter is impossible:

4*3^y-1=x^2.
Look at the left and right sides of the equation mod4.

Now, do u see why there are no integer solutions to this?


floor function
combinatorics unsolved
combinatorics

There are 2n subjects in a school, all of the students' achievements in any subject are good or bad.Every two student' achievements are different. And between any two students, neither of them is better than the other(If A is better than B, it means that any of A' ssubject is not worse than B, and A has at least one subject better than B).Prove: there are at most  2nCn students in this school.[/code]

This is Steiner's theorem: in a set with $m$ elements, the maximal number of subsets in an antichain is $\binom m{\lfloor\frac m2\rfloor}$. Here we have $m=2n$, of course.

If we construct chains of length $m$ which contain our sets, two chains containing two different sets will be different. Given a set with $k\le m$ elements, there are $k!(m-k)!$ chains of length $m$ which contain that set. If $p_k$ the number of sets with $k$ elements in our collection, we get $\sum_{k=0}^m p_k\cdot k!(m-k)!\le m!$ (we count the chains with $m$ elements containing our sets and we get the LHS, and then we count the chains with $m$ elements, and we get the RHS). That condition translates to $\sum \frac{p_k}{\binom mk}\le 1$. On the other hand, $\binom mk\le \binom m{\lfloor\frac m2\rfloor}$, so $\frac{\sum_{k=0}^m p_k}{\binom m{\lfloor\frac m2\rfloor}}\le 1$, Q.E.D.

There are advanced version of this problem.
Suppose $A$ is a set of $n$ elements, $A_1$, $A_2$, ..., $A_k$ are subsets of $A$, $A_i\not\subset A_j$ for all $i\neq j$. Let $s_i=|A_i|$.
Prove that
\[\frac{1}{C_n^{s_1}}+\frac{1}{C_n^{s_2}}+...+\frac{1}{C_n^{s_k}}\leq 1.\]

Solution can be found in Solved Problems Section.
Maybe grobber will find appropriate link?

Sorry about this: I edited my post above before seeing Myth's reply :). I had no idea it had been solved before here though..

Yes, your solution is the same what I wrote one year ago.  :)

That is the standard solution for this problem. I've seen it lots and lots of times.

I heard it would be due to Bollobas...

Pierre.

[quote="orl"][quote="Myth"]And this problem was on SPb MO or 239 MO (I don't exactly remember).[/quote]

Look [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=1162]here.[/url] Myth proves to have a good memory.  ;)[/quote]
I would wish it was true :(


trigonometry
linear algebra
linear algebra unsolved

[quote="Kent Merryfield"]Possible key words: Fourier discrete cosine transform.

Suggestion: compute $ A^2$ just to see what happens.[/quote]

Could you tell me the details? I'm a high-school student and I know a little.


inequalities
number theory unsolved
number theory

[hide="solution"]Let $ s_k$ denote the sum of the reciprocals of all $ k$-digit integers that do not contain a $ 9$ in their decimal representation.  Since for each positive integer $ a$ we have $ \sum_{k \equal{} 0}^8\frac {1}{10a \plus{} k} < \frac {9}{10a}$ , evidently we must also have $ s_{k \plus{} 1} < \frac {9}{10}s_k$.  By direct computation we find that $ s_1 < 3$, and hence $ \sum_{k \equal{} 1}^\infty s_k < 30$ (actually $ s_1 < \frac {11}{4}$, so the sum is less than $ \frac {55}{2}$).[/hide]

[quote="orl"]Let $ a_1, \ldots, a_n$ be distinct positive integers that do not contain a $ 9$ in their decimal representations. Prove that the following inequality holds
\[ \sum^n_{i\equal{}1} \frac{1}{a_i} \leq 30.\][/quote]
See that $S(1989)=27$ and $S(27)=9$ ($S(M)$ denotes the sum of the digits of $M$.)
So they asked the question for $9$ in particular. :P
Since this is year $2014$, I would like to ask what if in the original question, we replace $9$ by $7$,(since $S(2014)=7$), what number could we get in place of $30$?
That is:
Let $a_1, \ldots, a_n$ be distinct positive integers that do not contain a $7$ in their decimal representations.If  the following inequality holds:
\[ \sum^n_{i=1}\frac{1}{a_i}\leq N \] then what value can $N$ take? Please provide a proof as well. :D

If we replace $9$ by $7$, just repeating the argument in my old post immediately gives $\sum_{k=1}^\infty s_k < 10s_1=\frac{967}{36}<26.87$.

You can do better with the inequality $\sum_{k=1}^\infty s_k < s_1+s_2+\frac{81}{10}s_3<19.14$, and you can obtain arbitrarily tight bounds with the obvious modification.


function
calculus
algebra
polynomial
algebra proposed

Let $f_1,f_2,\ldots,f_n:\mathbb R\to\mathbb R$ be additive functions, i.e. $f_i(x+y)=f_i(x)+f_i(y),\ \forall i\in\overline {1,n},\ \forall x,y\in\mathbb R$. Show that if there is a constant $a\in\mathbb R$ s.t. $f_1(x)\cdot f_2(x)\cdot\ldots\cdot f_n(x)=ax^n,\ \forall x\in\mathbb R$, then at least one of the $n$ functions has the form $bx$.

I can't understand why you put it to Calculus?
Suppose $f_i\not \equiv 0$ for all $i$, then thre is an $x$ s.t. $f_i(x)\neq 0$ for all $i$.
Let $t$ be an arbitrary integer, and consider $\prod_{i=1}^n f_i(x+ty)=\prod_{i=1}^n (f_i(x)+tf(y))=a(x+ty)^n$. Since this equality holds for infinitely many $t$, we conclude two polynomials are equal.
[b]Case 1.[/b] $a=0$. It follows that polynomial of $t$ in the LHS is 0, so there is an $i$ s.t. $f_i(x)=0$ -- contradiction.
[b]Case 2.[/b] $a\neq 0$. Then $f_i(x)\neq 0$ and \[\prod_{i=1}^{n}\left(1+t\frac{f_i(y)}{f_i(x)}\right)=\prod_{i=1}^n\left(1+t\frac{y}{x}\right)^n.\]
We see two equal polynomials, therefore $\frac{f_i(y)}{f_i(x)}=\frac{y}{x}$ for all $x,y$.

Yes, I suppose the Algebra section would suit this better. Sorry about that :).