Can you learn most math just from reading papers? And if you get stuck at one point, then only look it up in a textbook and learn it. After all, really the point of a professional mathematician is to publish paper after paper (at a big school). So why not read a paper, study it, and then go to textbooks to learn the stuff you do not understand?

Because you can't write a paper unless you know the material.  I could give you a paper on advanced topology and there's no way you could understand it.  You have to know the material first.

Of course I wouldn't advocate only learning from papers, but I definitely can't overemphasize how much you can learn from reading papers that you wouldn't learn otherwise.

Papers tend to leave out "obvious" details, that will start to become obvious to you after you work them out a couple of times, that you might not have learned otherwise.

I highly encourage reading papers as early as possible. It will also help you see what is actually being done in fields, to help you decide what you like and want to do.

That being said. There is no substitute for learning the basics from a class/textbook.


induction
number theory
prime numbers
algebra unsolved
algebra

The sequence $ < x_n >$ is defined through:
$ x_{n \plus{} 1} \equal{} \left(\frac {n}{2004} \plus{} \frac {1}{n}\right)x_n^2 \minus{} \frac {n^3}{2004} \plus{} 1$ for $ n > 0$
Let $ x_1$ be a non-negative integer smaller than $ 204$ so that all members of the sequence are non-negative integers.
Show that there exist infinitely many prime numbers in this sequence.

From condition we obtain $ 2004|x_1^2 \minus{} 1$ ,it means that $ 167|x_1^2 \minus{} 1$ and $ x$ is an odd number .
If $ x_1 > 1$ we have $ x\geq 2.167 \minus{} 1$ , which gives contradiction because $ x < 204$ .
When $ x_1 \equal{} 1$ by induction , we can show that $ x_n \equal{} n$ ,and obvious  this sequence contain infinite prime numbers.


calculus
integration
calculus computations

$f(x) = \sqrt{a+1/x}$
Calculate
$\int f(x) dx$ and $\int \frac{1}{f(x)}dx$

Make the substitution $a+1/x \, = \, u^{2}$ and you´ll get a rational integral

Really? Thanks, but I've already solved it. I'm not looking for help.
Why do you [i]do[/i] it? The solution is actually complicated.


geometry
trigonometry
geometric transformation
homothety
ratio
circumcircle
incenter

Let $ ABC$ be a triangle with $ \angle A = 60^{\circ}$.Prove that if $ T$ is point of contact of Incircle And Nine-Point Circle, Then $ AT = r$,
$ r$ being inradius.

[color=brown][b]1.[/b][/color] [color=darkblue]Points $ B,O,I,H,C$ are conciclic[/color]

[hide="Proof"]
[color=darkred]$ \angle BOC \equal{} 2\angle A \equal{} 120^\circ$

$ \angle BIC \equal{} 180^\circ \minus{} \dfrac{\angle B \plus{} \angle C}{2} \equal{} 120^\circ$

$ \angle BHC \equal{} 180^\circ \minus{} \angle A \equal{} 120^\circ$[/color]
[/hide]

[color=brown][b]2.[/b][/color][color=darkblue] $ AH \equal{} OH$[/color]

[hide="Proof"]
[color=darkred]$ AH \equal{} 2R\cos \angle A \equal{} R \equal{} AO$[/color]
[/hide]

[color=brown][b]3.[/b][/color][color=darkblue] $ OI \equal{} IH$ [/color]

[hide="Proof"]
[color=darkred]Suppose $ AB\ge AC$.

$ \angle IOH \equal{} \angle IBH \equal{} \angle IBC \minus{} \angle HBC \equal{} \frac {\angle B}{2} \minus{} 90^\circ \plus{} \angle C \equal{} \frac {\angle C}{2} \minus{} 30^\circ$

$ \angle IHO \equal{} \angle ICO \equal{} \angle ICB \minus{} \angle OCB \equal{} \frac {\angle C}{2} \minus{} 30^\circ$

Thus, $ \angle IOH \equal{} \angle IHO$ and $ IO \equal{} IH$.[/color][/hide]

[color=brown][b]4.[/b][/color][color=darkblue] $ T$ is midpoint of $ AI$ [/color]

[hide="Proof"]
[color=darkred]Let $ A_1$ be the tangency point of the incircle with $ AB$. Then $ \angle TIA_1 \equal{} 60^\circ$, and, therefore triangle $ TIA_1$ is equilateral. So $ TI \equal{} IA_1 \equal{} \dfrac{AI}{2}$. [/color]
[/hide]

[b][color=indigo]Therefore, $ AT \equal{} TI \equal{} r$.[/color][/b]

my solution:
Prove that N lies on AI. so A,T,I are colliner.AI=2r,Done.

[u]Another solution[/u]

Let $ T'$ be the midpoint of $ AI$. Drop perpendicular $ IX$ to $ AB$. right triangle $ AIX$ has $ \angle A = 30^0$ So $ AI = 2IX = 2r$. So $ AT' = r$.
Let $ D,E,F$ be the respective midpoints of sides $ BC,CA,AB$ of triangle $ ABC$

It is sufficient to show $ T = T'$.
Consider the homothety with ratio $ \frac {1}{2}$ centered at $ A$.
$ B$ gets mapped to $ F$, $ C$ to $ E$ and $ I$ to $ T'$.
Hence $ \angle FT'E = \angle BIC = 90^0 + \frac {1}{2}\angle A = 120^0$.
And $ \angle EDF = \angle A = 60^0$. So $ \angle EDF + \angle FT'E = 180^0$
Hence $ DFT'E$ concyclic. So $ T'$ lies on the circumcircle of $ \Delta DEF$ which is the medial triangle of $ \Delta ABC$.
This triangle's circumcircle is the nine-point circle of $ \Delta ABC$.
Hence $ T'$ belongs to the incircle as well as nine-point circle of $ ABC$.
But they touch (at an unique point) by feurbach's theorem. Hence $ T = T'$
QED

this problem is quite easy. we denote the nine point centre by N , incenter by I, circumcenter by O and orthocenter by H. As the incircle touches the nine point circle at T we get N,I,T collinear.Now applying <A=60 we get AH=R and AI=2r and hence we get that the triangle AOH is isosceles. Hence AN is perpendicular bisector of OH( since N bisects OH).Hence AN is the angular bisector of OAH and by angle chasing we get AN is the angular bisector of BAC. Hence A,T,I,N are all collinear.Now AI=2r and IT=r. Hence AT=r


algebra
polynomial
function
topology
linear algebra
matrix
advanced fields

Show that the set of diagonalizable n x n matrices over C is dense in the set of all n x n matrices.

A slightly stronger statement is true: the set of matrices with distinct eigenvalues is dense.

Consider the characteristic polynomial $ f(\lambda) \equal{} \det(A\minus{}\lambda I)$. Since $ \det(M)$ is a polynomial function of the $ n^2$ coefficients of $ M$, the coefficients of $ f$ are polynomias in the coefficients of $ A$. The eigenvalues are not distinct iff the discriminant of $ f$ is zero. Recall that the discriminant is simply $ \prod_{i<j}(\lambda_i \minus{} \lambda_j)^2$, usually with some constant coefficient thrown in which doesn't matter to us, so it vanishes exactly when two of the roots are equal.

The only thing you need to know about discriminants here is this: The discriminant of $ f$ is itself a polynomial in the coefficients of $ f$. Therefore, the set of "bad" matrices (those with degenerate eigenvalues) is the zero set of a polynomial. More precisely, there is a polynomial

$ p : \mathbb{C}^{n^2} \to \mathbb{C}$

$ p(A) \equal{} \mbox{disc}(\det(A\minus{}\lambda I))$

such that $ p(A) \neq 0$ iff $ A$ has distinct eigenvalues. So now the problem becomes: what can you say about the zero set of a polynomial, or about its complement? You can forget about matrices and diagonalizations now and consider this problem in general. If you're stuck with this part of the proof, let me know - it can be done in many ways.

In which topology?The natural matrix topology for $ \mathbb{C}^{n^2}$ or the Zariski topology?
Anyway,both in the above two topologies,the proposition is true.
And we can use it to prove the elemtary theorem------Hamilton-Caylay's Theorem.

Follow-up: what is the Hausdorff dimension of the set of non-diagonalizable $ n\times n$ matrices?


We have updated the "Alcumus score" portion of the algorithm.  Previously, this had a bias that favored users who had been part of the testing period of the system over the last year.  We believe we have removed that bias.

No specific number of problems needed to be ranked.

[quote="dragon96"]How many problems are needed to be completed for your score to be ranked (if it belongs in the rank list)? Does this have to do with the score rank slipping about 90 for some?[/quote]

The ranks that slipped a bunch were inflated before we did this patch to the scoring system.  Basically, people who had Alcumus access during the non-public testing phase had inflated scores.


algebra
polynomial
logarithms
Rational Root Theorem

Basically, you would have a very weird number (unless it was ${\sqrt(\text{a perfect square)}}$ but that is obvious.  Never mind).  ${4^\sqrt{5}} \approx 22.19...$  However, I'm not 100% sure.   :D

if the square root power is not perfect, the resulting number is probably gonna be irrational...but that's just my thinking.

I thought of a new *theory* :D
If there's a non-zero real number [i]n[/i] to the m.p power, where m and p are real numbers and p is not negative, then n^m.p -> (n^m)(n^p/100) -> (n^m)(100th root of n)^p
Note:the fractional exponent p/100  can be modified to have a different denominator so p is whole.

Example:2^2.78 -> (2^2)(2^.78) -> (4)(2^78/100) -> (4)(100th root of 2)^78 which is about 6.869.
I guess a calculator is still needed for the last part...any comments on this?  :)

Yes, because $2^{2.78} \Rightarrow 2^{\frac{278}{100}} \Rightarrow$the hundredth root of $2^{278}$ from the rule of a number raised to a fraction.

$2^{2.78}$ is a real root of the polynomial $x^{100} - 2^{278} = 0$ and because it is not an integer, by the Rational Root Theorem it must be irrational.

Edit:  [quote="easyas3.14159..."]What would you do if you had something to a power that was a square root? (n^sqrtm)[/quote]

The answer, as near as I can figure, is "it depends."  For example, $\left( \sqrt{2} ^ {\sqrt{2}} \right) ^ {\sqrt{2}} = 2$.  Excepting these special cases, $n^{ \sqrt{m} }$ is irrational.

$n^{ \sqrt{m} } = \frac{p}{q}$
$\sqrt{m} = \log_n p - \log_n q$
$m = (\log_n p)^2 - 2 \log_n p \log_n q + (\log_n q)^2$

And it's hard to see a product of logs being integer (unless $p, q$ were powers of $n$, in which case $m$ becomes a square).  (This is by no means a proof, but at least it's fairly convincing evidence.)


http://www.artofproblemsolving.com/Forum/weblog.php?w=1755

There's my blog.  As you can probably see, I have a bunch of entries that are in different branches of math.  How can I categorize them, like, for example, in [url=http://www.artofproblemsolving.com/Forum/weblog.php?w=1569]PowerofPi's blog?[/url]

When you want to post an entry (or edit it), below the box where you enter your text, there are four links. I think the third one says something like "Tags and Categories". If you click on that, below it should appear a place where you can select a category or type in a new one.

Also, there is a FAQ thread on the second page of this forum. [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1513465#1513465]This post[/url] should answer your question.


When simplified and expressed with negative exponents, the expression $ (x \plus{} y)^{ \minus{} 1}(x^{ \minus{} 1} \plus{} y^{ \minus{} 1})$ is equal to:

$ \textbf{(A)}\ x^{ \minus{} 2} \plus{} 2x^{ \minus{} 1}y^{ \minus{} 1} \plus{} y^{ \minus{} 2} \qquad\textbf{(B)}\ x^{ \minus{} 2} \plus{} 2^{ \minus{} 1}x^{ \minus{} 1}y^{ \minus{} 1} \plus{} y^{ \minus{} 2} \qquad\textbf{(C)}\ x^{ \minus{} 1}y^{ \minus{} 1}$
$ \textbf{(D)}\ x^{ \minus{} 2} \plus{} y^{ \minus{} 2} \qquad\textbf{(E)}\ \frac {1}{x^{ \minus{} 1}y^{ \minus{} 1}}$

[hide]

$ \frac{\frac{1}{x}\plus{}\frac{1}{y}}{x\plus{}y}\equal{}\frac{\frac{x\plus{}y}{xy}}{x\plus{}y}\equal{}\frac{1}{xy}$

This is $ \textbf{ (C) }$

[/hide]


[code]Consider the two patterns of 'O' and 'X' below ('.' represent an empty square). We want the first pattern to be transformed into the second pattern in one time unit. During this time unit, each symbol ('O' and 'X') can move one step in any of the four directions (or remain at its current square). All movements happen simultaneously, so a symbol can move to an occupied square, if that symbol is moved to some other square. If a symbol moves from square A to B, and the symbol at B moves to A, we have a swap. Write a program which calculates the least number of swaps needed to transform a given pattern into another given pattern.

.XO..  ..XO.

..OX.  .XX..

.XX..  ..OX.

To transform the first pattern above into the second one requires one swap: The two symbols in the first line are moved to the right, the 'O' in the second line must be swapped with the 'X' below. The other two 'X' are moved up and down, respectively.

[/code]

Actually the example given above is wrong: it can be done without any swapping.

[code]Input
The first line in the input contains the number of test cases to follow (at most 20). Each test case starts with a line containing two integers, w and h (1 ≤ w, h ≤ 8), the width and height of the two patterns. Then follow h lines describing each row of the two patterns (the two patterns will be separated with a single space, see the sample input). The only allowed characters in the patterns will be the symbols 'O', 'X' and '.'.
[/code]

[code]Output
For each input you should output a line containing a single integer: the least number of swaps required to transform the first pattern into the second. If the transformation is not possible, output  a -1.
[/code]

Sample
[code]
3

5 3

.XO.. ..XO.

..OX. .XX..

.XX.. ..OX.

4 4

OXOX XOXO

XX.O OX.X

O..X X..O

XOXO OXOX

3 4

.X. .X.

.OX XO.

..O .O.

... ...

[/code]

[code]
0

0

-1

[/code]

in the algorithmist site i got this hint: Backtracking+DP.

But still i can't figure it out how! Can any one? If so please help me :(


MATHCOUNTS AMC AIME MIT college geometry Harvard

Nothing.
No one made the team because everyone scored 0 points.

Peijin isn't saying stuff that isn't clear in his blog.

hmmm i'm thinking someone told people to be all shady about this

First- xiaoyu from Acton, sorry if I spelled your name wrong.

[b]CLARKE[/b]
Jason- 2nd :winner_second:
Allison- 4th
Alan- 5th
Hao- 15th
Peijin- 23rd

AND

Clarke- 1st :first:

Then, Allison gave up her spot on for nationals and let Alan take it.

And of course, Alan pwned 5 people in countdown and got 1st, unofficially.

[b]Diamond[/b]
Amy- 6th
Matt- 10th
Sheila- I think this is the correct spelling- 11th
Kevin- 20th

Diamond- 3rd :winner_third:

[quote="shentang"]]
[b]Diamond[/b]
Amy- 6th
Matt- 10th
Sheila- I think this is the correct spelling- 11th
Kevin- 20th[/quote]

not to disrespect anyone or anything but i'm not completely surprised that kevin finished below the top 4 (but i wouldn't have expected 20th)

that's intense, i should have gone

For real :

MASSACHUSETTS :

Teams:
1st Jonas Clarke
2nd RJ Grey
3rd Diamond

Individuals :

1st Xiaoyu He  (RJ Grey)
2nd Jason Li (Clarke)
3rd Yongyi Chen (John Glenn Bedford)
4th Allison Bukys(Clarke, but not going to Nats due to prior commitment)
5th Alan chou (Clarke, going to Nats in Allison's place)
(names will appearon MATHCOUNTS website so i assumed safe to post0

Countdown, Alan went from 5th to 1st, so if countdown had been official we'd have the same Nats team anyway :lol:

Great job to everyone in Mass!!

was team as much of a blowout as it was last year? apparently clarke doesn't suck. not that it ever did (well, 2 years ago it kinda did) good job.

we can't talk about scores, or even how scores related to each other.  I'll fill you in off the forum on that stuff Carl.

[quote="perfect628"]It would suck to make nats then not be able to go...ouch.

P.S. Welcome to the club kevin. Well, I did slightly better(grr cd not counting), but still.[/quote]

I agree, but great to be able to let your teammate go in your place and still get to go on a great trip.  Plus she will get the calculator :lol:

Eh, now I only have...
AIME to look forward to?
..
(._.")
Dang.
 :mad:

Eh, I'm going because people tell me it helps a lot, (like Carl), and that it's really fun, (like what Carl said), and that I can laugh at people who lost their glasses at the beach. (Like Carl).
HA I'M ALMOST DONE.
I'll send it out tomorrow.

[quote="alkjash"]Well, you learn stuff at home 2...
I mean, I went through the entire Introduction series except for Algebra and AoPS 1 last summer...[/quote]

Anything you can learn at a math camp, you can learn at home, yes. But as I've said before, the true experience is being around people who share a love of math, and being inspired by each other. And yeah, it's a lot of fun. You'll probably meet lifelong friends as well.

Hey, I like croquet!  We get pretty vicious at our 4th of July gathering every year!

what is up with all this spam about croquet

then lets talk about something else.......like............wait this is state mathcounts......but thats over already. :(

[quote="perfect628"]During senior week (last week) at RL the seniors played croquet sometimes...They played bocce more though.[/quote]

ahhhh.....bocce......another quality lawn game!!  I think I will make a math problem about Bocce!!!

again, what's with all this spam about croquet and bocce guys

dude, I brought it up in order to form an analogy in a content-based, useful post. Then came the stream of pointless spam.

[quote="ZhangPeijin"]No idea what bocce is...
Played croquet with some of my dad's work friends when I was like 5, didn't make sense to me but I still have a set in the basement.
Let's talk about how Nats is next week.
:|[/quote]

So lets talk about Nats. How good are you guys on the team round. Like what do you guys usually get?

It's probably confidential Hao, because they don't want other teams to know.
:P
Yay I finished my MP test...


Consider the function $ f: R\minus{}>R$ , $ f(x)\equal{}\{x\}(1\minus{}\{x\})$, where $ x\equal{}[x]\plus{}\{x\}$, $ [x]$ is the integer part of number $ x$.Find out the period of function $ f$

We clearly have $ f(x\plus{}1)\equal{}f(x)$, so the period is at most 1. Also, if $ r$ is the minimal period, then we must have $ f(r)\equal{}f(0)\equal{}0$. The smallest solution for this greater than 0 is $ x\equal{}1$, the period is at least 1.
Thus, the period is 1.


Find all functions $f: R \rightarrow R$ such that
\[f(x+yf(x))+f(xf(y)-y)=f(x)-f(y)+2xy\]
for all $x,y \in R$

at least i have found these things maybe helfull

we define this:$A:$$x \longrightarrow y$ means in$A$ put $y$ beside of $x$.
we name $f(yf(x)+x)+f(xf(y)-y)=f(x)-f(y)+2xy$(we name this $A$)

1.$f(0)=0$
2.$f(-x)=-f(x)$
3.$f(xf(x)+x)+f(xf(x)-x)=2x^2$
4.$f(xf(x)+x)=f(x)+x^2$
5.$f(xf(x)-x)=x^2-f(x)$

and these are the proves of the steps
                                                                              $1$.

 $A$:$x,y \longrightarrow 0 $ and $f(0)=0$

                                                                              $2$.

 $A$:$x \longrightarrow y, y \longrightarrow x$ and  adding what we will have to $A$ we will have
$f(yf(x)+x)+f(yf(x)-x)+f(xf(y)+y)+f(xf(y)-y)=4xy$
now $y \longrightarrow0$ and using $f(0)=0$ we will have $f(-x)=-f(x)$

                                                                              $3$

$A$ : $y \longrightarrow x $ and we will have
$f(xf(x)+x)+f(xf(x)-x)=2x^2$

                                                                              $4$

$A$ : $x \longrightarrow -x$ and using $f(-x)=-f(x)$ we will have $f(yf(x)+x)+f(xf(y)+y)=f(x)+f(y)+2xy$($B$)
now $B$:$y \longrightarrow x$ we will have  $f(xf(x)+x)=f(x)+x^2$

                                                                              $5$

from $4$ we have reach $B:(yf(x)+x)+f(xf(y)+y)=f(x)+f(y)+2xy$ now we have
$C: A+B=2f(yf(x)+x)+f(xf(y)+y)+f(xf(y)-y)=2f(x)+4xy$ and $C: y \longrightarrow x$ we will have
$3f(xf(x)+x)+f(xf(x)-x)=2f(x)+4x^2$
but from $4$ we have that $f(xf(x)+x)=f(x)+x^2$ so $3f(xf(x)+x)+f(xf(x)-x)=3f(x)+3x^2+f(xf(x)-x)=2f(x)+4x^2$
that will lead us to $f(xf(x)-x)=x^2-f(x)$

you have made a mistake. In 3) you should have a $2$ on the RHS. Moreover, $f(x)=x$ is clearly a solution.

you are right  then the whole thing is useless :surrender:  :stretcher:  :wallbash:

Here's my partial solution.

$f(x+yf(x))+f(-y+xf(y))=f(x)-f(y)+2xy$ (1)

Putting $x=y=0$, we get $f(0)=0$ easily.
Now putting only $x=0$, we have
$f(0) + f(-y) = f(0) - f(y)$
so that
$f(-x) = -f(x)$.

Next, we prove that $0$ is the only $x$ for which $f(x)=0$. Suppose $z$ is such that $z \neq 0$, $f(z)=0$. Put $x=y=z$. Then we get $2z^2=0$ out of (1), a contradiction.

Now, we prove that $f(x)$ satisfies the Cauchy equation.

Substitute $-y$ for $y$ in (1). Because $f(y)=-f(-y)$, we get

$f(x-yf(x))+f(y-xf(y))=f(x)+f(y)-2xy$

Adding this to (1) gives

$f(x+yf(x))+f(x-yf(x))+(-f(y-xf(y)))+f(y-xf(y))=f(x)+f(x)+f(y)-f(y)+2xy-2xy$

so that

$f(x+yf(x))+f(x-yf(x))=2f(x)$

If $f(x) \neq 0$ (that is iff $x \neq 0$) we can fix $x$ and vary $y$ so this becomes

$f(x+a)+f(x-a)=2f(x)$ (2)

 for $a \in R$, $x \neq 0$. But it works for $x=0$ as well, as we have proved above. Putting $x=a$ in (2) gives $f(2x) = 2f(x)$. Putting $x=\frac{x+y}2$ and $a=\frac{x-y}2$ gives

$f(x)+f(y)=2f(\frac{x+y}2)=f(x+y)$.

If $f(x)=kx$, then $2k^2=2$ from (1) so $k=1$ or $-1$. $f(x)=x$ works and $f(x)=-x$ also works.

But I don't know how to eliminate the wild solutions... bijectivity doesn't do it, does it?

The problem is just getting started after we get:
f(x+y)=f(x)+f(y) and f(xf(x))=x^2
Anyone? ;)

In fact note that since f(xf(x))=x^2 (*)
we get that 2yx = f(xf(y)) + f(yf(x))
Also so replacing y by 1 we obtain that
2x= f(f(x)) + f(bx) where b=f(1)
But since f(xf(x))=x^2 we get that f(b)=1.
f(xf(x))=x^2 and f(x+y)=f(x)+f(y) imply that f(x) is rational only if x is rational.
(proof. if f(x) rational then f(xf(x)) = f(x)^2 =x^2 so x is rational)
so since b=1, f(1)^2 = 1 and so f(1)=1/-1.
Case1.
f(1)=1
hence f(Q) = Q
Also f(f(x)) + f(x) =2x.
so f is bijective and therefore: xf(1/x) +1/x f(x) =2

Well, no one is interested in finishing this problem :(
So I will do it :P  :P

Observe that f(1)=1 or -1.
I will only solve for the case when f(1)=1, the other case is exactly the same.
f(f(x)) + f(x) =2x and additivity of f(x) imply that f(x) +x is one to one.
So Now replace in equation f(xf(x))=x^2 , x with f(x)
to observe together with injectivity of f(x)+x that f(x^2) = f(x)^2
This implies that f(x) is increasing. So f(x)=x...

-Ali

I almost understood nothng how you finished your solution. (I think you supposed that $f$ is continious). But this is my solution

First if $x=y=0$ then $f(0)=0$. Now if $x=0$ then $f(-y)=-f(y)$. So $f$ is odd. Now replace $x$ with $-x$ in the problem, then: \[f(x+yf(x))+f(y+xf(y))=f(x)+f(y)+2xy \ \ \ \ \ \ (*)\]
Suppose $f(c)=0$ and $c\in\mathbb R$. Then in relation $(*)$ if $x=y=c$ then $c^2=0$ and $c=0$. Now in relation $(*)$ replace $y$ with $-y$ then: \[f(x-yf(x))-f(y+xf(y)=f(x)-f(y)-2xy\]
Adding the 2 last relations we obtain: $f(x+yf(x))+f(x-f(x))=2f(x)$. Then if we suppose $a=x+yf(x),\ b=x-yf(x)$ then \[\forall a,b \in\mathbb R \ \ f(a)+f(b)=2f(\frac{a+b}{2})\]
If $b=0$ then $\displaystyle f(\frac{a}2)=\frac{f(a)}2$. So \[\forall a,b \in\mathbb R\ \ f(a)+f(b)=f(a+b) \ \ (**)\]
Now noticing relations $(*)$ and $(**)$:\[f(x)+f(xf(y))+f(y)+f(yf(x))=f(x)+f(y)+2xy\]
So \[f(xf(y))+f(yf(x))=2xy\ \ (1)\]
Also because if $f(a)=f(b)\Rightarrow f(a-b)=0\Rightarrow a=b$ so $f$ is injective.
Now we prove that, there exist $t\in\mathbb R\backslash\{0\}$ that $f(t)=t$ or there exist $t\in\mathbb R\backslash\{0\}$ that $f(t)=-t$. For this in relation $(*)$ if $x=y=1$ and $x=-y=1$ then: \[f(f(1)+1)=f(1)+1\mbox{ and } f(1-f(1))=f(1)-1\]
And at least one of the numbers $f(1)+1$ and $1-f(1)$ is nonzero. WLOG Suppose there exist $t$ that $f(t)=t$ (for the other case the calculations are similiar)

Now we prove that $f(1)=1$. In relation (1) if $x=1,y=t$ then $t+f(tf(1))=f(t)+f(tf(1))=2t$. So $f(tf(1))=t=f(t)\Rightarrow t=tf(1)\Rightarrow f(1)=1$

Now if $y=1$ then $f(f(x)+x)=2x$. So $f(f(x)-x)=f(f(x)+x)-2f(x)=2x-2f(x)$. Now if $f(x)\neq x$ then if $u=f(x)-x$ then $u\neq0$ and $f(u)=-2u$. So $=f(-2u^2)=f(uf(u))=u^2$. So $f(2u^2)=-u^2$. Now suppose $x=1$ and $y=2u^2$ then $f(f(2u^2)+2u^2)=4u^2=f(2u.f(2u))=f(4uf(u))$. So $f(2u^2)=2u^2=4u.f(u)$. So $-u^2+2u^2=4u.(-2u)=-8u^2$. Therefore $u=0$ and $f(x)=x$ for each $u\in\mathbb R$.
Also if there exist $t$ that $f(t)=-t$ then with similiar calculations $f(x)=-x$ for each $x$ and solutions are $f(x)=x$ and $f(x)=-x$

My solution is perfectly valid...No extra assumption, such as continuty

:mad:  :mad:  :!:
 BE ALWAYS SPECIFIC..
JUST DON'T WRITE A CRAP FOR ME...
IF IT IS WRONG, SHOW WHY?

First I didn't say your solution is wrong :D  :D
Second Why do you get impatient?

I just didn't understood how you proved $f(x)$ is increasing and how you said $f(x)=x$

I'll be pleased if you explain more.


When I try to post I get logged out? Why is this?

Give more details of what you're doing, OS, browser, links, the exact steps you take to recreate this, the full works.


Given a set $ S \subseteq Z$ and $ S$ satisfies
(1)$ \exists a,b \in S$ and $ (a,b)\equal{}(a\minus{}2,b\minus{}2)\equal{}1$
(2) for any $ x,y \in S$ then $ x^2\minus{}y \in S$($ x,y$ can be equal)
Prove $ S\equal{}Z$

Let $ A\equal{}\{a|y\in S\Rightarrow y\plus{}a\in S, y\minus{}a\in S\}$.
Obviously if $ a_1,a_2\in A, gcd(a_1,a_2)\in S$,

From $ u^2\minus{}y\rightarrow v^2\minus{}(u^2\minus{}y)\equal{}v^2\minus{}u^2\plus{}y$ ,
$ u^2\minus{}v^2\in A, \forall u,v\in S$.

Now let $ a,b$ satisfy condition (1),
$ a^2\minus{}b^2\in A$ and $ (a^2\minus{}b)^2\minus{}(a^2\minus{}a)^2\equal{}(a\minus{}b)(2a^2\minus{}a\minus{}b)\in A$ imply
$ (a\minus{}b)2a^2\in A$. Similarly $ (a\minus{}b)2b^2\in A$,
$ (a,b)\equal{}1\Rightarrow ((a\minus{}b)2a^2,(a\minus{}b)2b^2)\equal{}2(a\minus{}b)\in A$.

WLOG, assume $ a$ is odd, $ (a^2\minus{}a)^2\minus{}a^2\equal{}a^3(a\minus{}2)\in A$
We see $ (a,2)\equal{}(a\minus{}2,2)\equal{}1$, $ (a,a\minus{}b)\equal{}(a,b)\equal{}1$ and $ (a\minus{}2,a\minus{}b)\equal{}(a\minus{}2,b\minus{}2)\equal{}1$. so
$ (a^3(a\minus{}2),2(a\minus{}b))\equal{}1\in A$

$ 1\in A\Rightarrow S\equal{}Z$.


geometry
cyclic quadrilateral
geometry proposed

let $ ABCD$ be a cyclic quadrilateral, and has an incircle (inscriptible)
then prove that $ (PR)$ is perpendicular to $ (QS)$ where $ P,Q,R,S$ are the points where the incircle touches $ AD,  AB, BC, CD$ respectively.

Denote $ T: SQ \cap PR$. Then
$ \angle PTQ \equal{} 180 \minus{} \angle PQS \minus{} \angle QPR \equal{} 180 \minus{} \frac{180 \minus{} \angle ADC}{2} \minus{} \frac{180 \minus{} \angle ABC}{2} \equal{} \frac{\angle ABC \plus{} \angle ADC}{2} \equal{} 90^\circ$


analytic geometry
graphing lines
slope
AMC

[hide]
Let $L_1$ be the line that goes through $(2,4)$ and $(14,9)$, and let $L_2$ be the line $y=mx+b$. If we let $\theta$ be the measure of the acute angle formed by $L_1$ and the x-axis, then $\tan{\theta}=\frac{5}{12}$. $L_1$ clearly bisects the angle formed by $L_2$ and the x-axis, so $m=\tan{2\theta}=\frac{2\tan{\theta}}{1-\tan^2{\theta}}=\frac{120}{119}$. We also know that $L_1$ and $L_2$ intersect at a point on the x-axis. The equation of $L_1$ is $y=\frac{5}{12}x+\frac{19}{6}$, so the coordinate of this point is $(-\frac{38}{5},0)$. Hence the equation of $L_2$ is $y=\frac{120}{119}x+\frac{912}{119}$, so $b=\frac{912}{119}$, and our answer choice is $\boxed{E}$.
[/hide]

[hide]ooh, i see.

I did the same tangent thing as above for the slope, but then finished it with point-line distance formula.

Knowing the slope, the line can be written in the form $120x-119y+119b=0$ and this line is a distance of $4$ from the point $(2,4)$.  Then $4=\frac{120(2) + (-119)(4) + 119b}{\sqrt{120^2+119^2}}$
The square root comes out nicely and the thing simplifies to $b=\frac{912}{119}$[/hide]

[hide="Alternate Solution"]
Sorry for reviving but this is a pretty neat solution using non-analytic methods.
The tangent length to the larger circle is 12. The tangent to the smaller circle is $\frac{4}{5}\cdot12=\frac{48}{5}$.
The distance from the point where the tangents intersect to the y-axis is $\frac{48}{5}-2=\frac{38}{5}$. So we find that $b=\frac{120}{119}\cdot \frac{38}{5}=\frac{912}{119}$
[/hide]

Let $l$ be the line tangent to the circles, and let $k$ be the line through the two centers. Then $l$ and $k$ have the x-intercept, which we can easily calculate to be (-\frac{38}{5},0). The slope of $k$ is $\frac{5}{12}$, and by using the tangent double angle formula we calculate the slope of $l$ to be $\frac{120}{119}$. Hence the equation of $l$ is $y=\frac{120}{119}(x+\frac{38}{5})$, and hence the answer is (E).

Out of curiosity, is there any way to solve this without trignometry?

[quote=mathman523]A separate question, how is it determined that $L_1$ bisects and angle formed by $L_2$ and the x-axis in skiron's solution?[/quote]

If you draw the other external tangent, it is clearly symmetric to the first over $L_1$. The other external tangent is the x-axis.

You could probably avoid trigonometry by using calculus to create a  system of equations.  This, however, would be more tedious because you would have to create equations for the circles and manipulate them.

[hide="Alternate Approach"] Use the distance from a point to a line formula. You get a system of two equations in two variables. [/hide]

How do you know the two lines would intersect?

Because one is the angle bisector of the other.

Let the centers be $O_1,O_2$ respectively and let the tangency points be $T_1, T_2$ respectively. Drop the perpendicular from $O_1$ to $T_2O_2$ and let the foot be $F$. We can easily see that $FO_2=5, O_1F=12, FT_2=4$. Then if $F=(a,b)$, we have $(a-2)^2+(b-4)^2=144, (a-14)^2+(b-9)^2=25$, so $F=\left(\frac{1766}{169}, \frac{2116}{169}\right)$. From this we can obtain $T_2=\left(\frac{1286}{169}, \frac{2592}{169}\right)$. We can calculate that the slope of $O_1F$ is $\frac{120}{119}$, and this is parallel to $T_1T_2$. Using this and the point $T_2$, the equation of line $T_1T_2$ is $y=\frac{120}{119}x+\boxed{\frac{912}{119}}$.

let the line connecting the centers be $\ell$. then the x-intercept of $\ell$ is $-\frac{38}{5}$, while the tangent of the angle formed by the two external tangents is $$\tan(2\theta)=\frac{2\tan \theta}{1-\tan^2\theta}=\frac{120}{119}$$ so the answer is $\frac{38}{5}\cdot \frac{120}{119}=\boxed{\frac{912}{119}}$

[b]Walk-Through:[/b]

$\bullet$ Looking at the $y$-coordinates of our two centers, i.e. $O_1$ and $O_2$, implies the $x$-axis is one of the common external tangents.
$\bullet$ Similar triangles yields the concurrency point of $y = 0$, $O_1O_2$, and the other external tangent as $\left( - \frac{38}{5}, 0 \right)$.
$\bullet$ By symmetry, we know the angle formed by the two external tangents is double the angle formed by the $x$-axis and $O_1O_2$, which we denote by $\theta$.
$\bullet$ Using double angle formulas yields $$\tan 2\theta = \frac{2 \sin \theta \cos \theta}{cos^2 \theta - sin^2 \theta} = \frac{120}{119}$$ which immediately yields our answer.


trigonometry
inequalities
geometry
perimeter
circumcircle
area of a triangle
Heron\u0027s formula

Suppose that $\alpha, \beta, \gamma$ are three real numbers in the interval $[0,\pi]$ and $\alpha+\beta+\gamma =\pi$. Without using the Jensen inequality, prove that:
$\sin \alpha+\sin \beta+\sin \gamma \leq \frac{3\sqrt{3}}{2}$

We'll prove that $\sum\sin^{2}\alpha\leq \frac{9}{4}$, it here http://www.mathlinks.ro/Forum/viewtopic.php?t=147870

[quote="Yulia"]$(\alpha, \beta, \gamma)$ majorize $(\frac{\pi}{3},\frac{\pi}{3},\frac{\pi}{3})$
And by Karamata inequality we get
$\sin{\alpha}+\sin{\beta}+\sin{\gamma}\leq \frac{3\sqrt{3}}{2}$[/quote]

In fact Karamata's inequality for $(a_{1},a_{2},...,a_{n}) \succ (\frac{a_{1}+a_{2}+...+a_{n}}{n},\frac{a_{1}+a_{2}+...+a_{n}}{n},\frac{a_{1}+a_{2}+...+a_{n}}{n})$ is Jensen inequality.And mathematica wrote:
[quote]Without using the Jensen inequality[/quote]
  :)

Here's my proof:

Suppose that $x,y,z$ are three positive real numbers. Using the AM-GM inequality it can easily be proved that:

$10xyz\sum_{cyc}x^{3}\leq 5\sum_{sym}x^{4}y^{2}$
$22xyz\sum_{sym}x^{2}y\leq 22\sum_{sym}x^{4}y^{2}$
$8xyz\sum_{sym}x^{2}y \leq 8\sum_{sym}x^{3}y^{3}$
$114x^{2}y^{2}z^{2}\leq 19\sum_{sym}x^{3}y^{3}$

By adding up these inequalities we get:

$10xyz\sum_{cyc}x^{3}+30xyz\sum_{sym}x^{2}y+114x^{2}y^{2}z^{2}\leq 27\sum_{sym}(x^{4}y^{2}+x^{3}y^{3})$

which is equivalent to:

$64xyz\left(\sum_{cyc}(x^{3}+2xyz)+3\sum_{sym}x^{3}y^{3}\right) \leq 27(2xyz+\sum_{sym}x^{2}y)^{2}$
or

$64xyz(x+y+z)^{3}\leq 27(x+y)^{2}(y+z)^{2}(z+x)^{2}$

Here's the rest of my proof:

If either of the angles $\alpha,\beta,\gamma$ are $0$ or $\pi$, the inequality is trivial. Now suppose otherwise and construct a triangle $ABC$ with angles $\alpha,\beta,\gamma$.  Suppose that $s,\Delta$ and $R$ are the semi-perimeter, area and the circumradius of $\triangle ABC$. Using the law of sines in $\triangle ABC$ it can easily be proved that $\frac{s}{R}=\sin \alpha+\sin \beta+\sin \gamma$. Thus we have to prove:

$\frac{s}{R}\leq \frac{3\sqrt{3}}{2}$

Since $R=\frac{abc}{4\Delta}$ we have:

$\frac{4\Delta s}{abc}\leq \frac{3\sqrt{3}}{2}$

By squaring and using Heron's formula we get:

$64s^{3}(s-a)(s-b)(s-c)\leq 27a^{2}b^{2}c^{2}$

Now by substituting $a=x+y, b=y+z, c=z+x$ we have:

$64xyz(x+y+z)^{3}\leq 27(x+y)^{2}(y+z)^{2}(z+x)^{2}$

which is the inequality proved in part I.

[quote="mathematica"]Suppose that $\alpha, \beta, \gamma$ are three real numbers in the interval $[0,\pi]$ and $\alpha+\beta+\gamma =\pi$. Without using the Jensen inequality, prove that:
\[\sin \alpha+\sin \beta+\sin \gamma \leq \frac{3\sqrt{3}}{2}\][/quote]

See here: http://www.mathlinks.ro/Forum/viewtopic.php?t=136464


induction
inequalities
inequalities proposed

It's a difficult one ,I have ever done it .

use A-G ineq,

_______
I wii out of here

Is there anyone who could solve this question?  :D

After considering the fact that the big sum in the left side in the inequality is produtect of all the a's times the sum of the b/a;after using the inequality condition on the b's ,we need only to show that the product of any n a's is less than (1/n)^n whenever their sum is one and are positive.The fact that the sum of the b's is one is not necessary.Sorry for not beeing more specific.Dont have latex.
Wher can i have the software.Help please.


Hi anyone knows any specific statistical test that test on the how fairly occurances are distributed across the data?

eg data 1 : 11111111111000000000000,
data 2 101010101010101010
data 3 110111010000000000

Data 2 is fairly distributed with 1 fairly distributed and occurs across the entire data while data 1 and data 2 have 1 clustered at the front.

Is there a specific stat test to test for this type of distribution?

What do you mean by "fair"? I wouldn't believe any of these as a random sequence; they're all too regular. The least regular one is #3; I could believe that that had some random input.


superior algebra
superior algebra unsolved

1. In S_5, whether the set {(12), (123), (1234)} is an equivalence class modulo some subgroup.

2. Prove that S_4/K, where K={e, (12)(34), (13)(24), (14)(23)} isomorphic to S_3.

Thanks

For #2,  consider the map ${ {\varphi}: S_3}$ to $ S_{4}/K$ defined as $ {\varphi}(\pi)={\pi}K$.

[quote="Hashbrownie"]For #2,  consider the map ${ {\varphi}: S_3}$ to $ S_{4}/K$ defined as $ {\varphi}(\pi) = {\pi}K$.[/quote]

Yes, thank you, I already understood :)


inequalities
real analysis
real analysis unsolved

Let $ P$ be the "standard" nonmeasurable set in $ [0,1]$ and let $ E\equal{}[0,1] \setminus P$. If $ A \cap [0,1]$ is a measurable set, what is $ m^{*}(A \cap E)$? Will it be $ m(A \cap [0,1])$?

The "standard" construction is not sufficiently well controlled to be able claim anything for certain about such outer measures; you can further manipulate the construction to get varying answers.

I see. I suppose I can only say that $ m^{*}E\equal{}1$.

If you can say that $ m^*(E)\equal{}1$, then you can also automatically say that $ m^*(A\cap E)\equal{}m(A\cap [0,1])$ for all measurable $ A$. Indeed, for measurable sets $ A$, you have
\[ m^*(E)\equal{}m^*(E\cap A)\plus{}m^*(E\setminus A)\]
so, to reach $ 1$, both terms on the right have to be at their possible maxima.

Now, what exactly do you mean by the "standard construction": choosing one representative in $ [0,1]$ from each class $ x\plus{}\mathbb Q$? If so, you are fine with $ m^*(E)\equal{}1$. Indeed, every set of positive measure contains 2 points with rational difference, so it cannot be a subset of $ P$.

I'm not sure what Kent meant. Most likely, he was thinking of $ A\cap P$ rather than of $ A\cap E$. The outer measure of the former can, indeed, be just anything between $ 0$ and $ m(A\cap [0,1])$.

[quote] Now, what exactly do you mean by the "standard construction": choosing one representative in $ [0,1]$ from each class $ x \plus{} \mathbb{Q}$? [/quote]

Yes, that was what I meant.

[quote] so, to reach 1, both terms on the right have to be at their possible maxima. [/quote]

Sorry fedja, I don't quite get this point. Could you perhaps explain a little more?

$ m^*(A\cap E)\le m(A\cap[0,1])$ and $ m^*(E\setminus A)\le m([0,1]\setminus A)$. But the right hand sides in these inequalities add to $ 1$, so the left hand sides may add to $ 1$ only if both inequalities are identities.

Indeed. That second inequality just eluded me.
Thanks a lot.


algebra
polynomial
analytic geometry
graphing lines
slope
algebra unsolved

[i]Let  $ P(x)$ be a polynomial

 , $ deqP(x) \equal{} n$ , $ n \in N^{*}$

    Prove that

   $ P( x \plus{} n \plus{} 1) \equal{} \sum_{i \equal{} 1}^{n}\binom{n\plus{}1}{i}( \minus{} 1)^{n \minus{} i}P(x \plus{} i)$[/i] :lol:

otherwise, for example for $ n \equal{} 1$, you get $ P(x \plus{} 2) \equal{} 2P(x \plus{} 1)$, which is obviously wrong.  However, if the sum extends from $ i \equal{} 0$ to $ i \equal{} n$, then you get $ P(x \plus{} 2) \equal{} 2P(x \plus{} 1) \minus{} P(x)$, or $ P(x \plus{} 2) \minus{} P(x \plus{} 1) \equal{} P(x \plus{} 1) \minus{} P(x)$, obviously true since both sides equal the slope of the 1st degree polynomial...

Now that is cleared, just take any real value $ x_0$, and consider the following polynomial:
\[ Q(x) \equal{} \sum_{i \equal{} 0}^n\frac {P(x_0 \plus{} i)}{\prod_{j \equal{} 0,j\neq i}^n(i \minus{} j)}\prod_{j \equal{} 0,j\neq i}^n(x \minus{} x_0 \minus{} j).
\]
This polynomial has degree $ n$, and takes values $ P(x_0 \plus{} i)$ at $ x \equal{} x_0 \plus{} i$ for $ n \plus{} 1$ different values of $ i$, or $ P(x) \minus{} Q(x)$ is a polynomial with degree at most $ n$, and with $ n \plus{} 1$ real roots, ergo $ P(x) \equal{} Q(x)$.  Write now $ Q(x_0 \plus{} n \plus{} 1)$ (which obviously equals $ P(x_0 \plus{} n \plus{} 1)$), it results on the RHS of the given equation except that the sum goes from $ i \equal{} 0$ to $ i \equal{} n$, and we are done, since we may repeat the procedure for any $ x_0$ that we wish...


inequalities
AMC
USA(J)MO
USAMO
inequalities unsolved
1991

Let $a = \frac{m^{m+1} + n^{n+1}}{m^m + n^n}$, where $m$ and $n$ are positive integers.  Prove that $a^m + a^n \geq m^m + n^n$.

[hide="liangchene original post hidden"][quote="liangchene"]Here is a problem u can solve with Bernoulli's inequality:

The theorem goes like this

[b]for x>1 and x>-1 (or r an even integer and x any real)[/b]

\[ (1+x)^r \geq 1+xr  \]

the question is :

Let \[ a = \frac{m^{m+1} + n ^ {n+1}}{m^m+n^n}  \] for m,n positive intergers. Prove that $a^m + a^n \geq m^m+n^n$

I have no idea how to start this problem, can anybody give me a hint?[/quote][/hide]
In your post, I boldfaced the part that you stated confusing conditions

[hide="First step hint"]Assume WLOG $m\ge n$ because the expression in $a$ and the inequality are symmetric.[/hide]

[hide="Second step hint"]Play with division: make binomials that look like this form: $1+f(m,n)$[/hide]

The problem is solved in the book" Winning Solutions" by Lozansky & Rousseau

Here is a hint based on their solution: write a  as  m[ 1 + (a-m)/m]  and  n[ 1+ (a-n)/n]

This is Question 4 in USAMO 1991.You can find a further solution at the Kalva site.

I have lots of exercices using Bernoulli's inequality. ;)

[hide="Solution"]
Because $ m$, $ n$, and $ a$ are all positive, $ f(x) \equal{} x^{m}$ is convex between $ a$ and $ m$, so it lies above the tangent line through $ m$.

The equation of this line is $ L(x) \equal{} m^{m}\plus{}f'(m)(x\minus{}m) \equal{} m^{m}\plus{}m^{m}(x\minus{}m)$

Thus $ a^{m}\ge L(a) \equal{} m^{m}\plus{}m^{m}(a\minus{}m)$.

Similarly, $ a^{n}\ge n^{n}\plus{}n^{n}(a\minus{}n)$.

Adding these gives $ a^{m}\plus{}a^{n}\ge m^{m}\plus{}n^{n}\plus{}m^{m}(a\minus{}m)\plus{}n^{n}(a\minus{}n)$.

But $ m^{m}(a\minus{}m)\plus{}n^{n}(a\minus{}n) \equal{} (m^{m}\plus{}n^{n})(a)\minus{}m^{m\plus{}1}\minus{}n^{n\plus{}1}\equal{} 0$, so we have that $ a^{m}\plus{}a^{n}\ge m^{m}\plus{}n^{n}\plus{}0$ as desired.

QED[/hide]

[quote="calc rulz"][hide="Solution"]
Because $ m$, $ n$, and $ a$ are all positive, $ f(x) \equal{} x^{m}$ is convex between $ a$ and $ m$, so it lies above the tangent line through $ m$.

The equation of this line is $ L(x) \equal{} m^{m} \plus{} f'(m)(x \minus{} m) \equal{} m^{m} \plus{} m^{m}(x \minus{} m)$

Thus $ a^{m}\ge L(a) \equal{} m^{m} \plus{} m^{m}(a \minus{} m)$.

Similarly, $ a^{n}\ge n^{n} \plus{} n^{n}(a \minus{} n)$.

Adding these gives $ a^{m} \plus{} a^{n}\ge m^{m} \plus{} n^{n} \plus{} m^{m}(a \minus{} m) \plus{} n^{n}(a \minus{} n)$.

But $ m^{m}(a \minus{} m) \plus{} n^{n}(a \minus{} n) \equal{} (m^{m} \plus{} n^{n})(a) \minus{} m^{m \plus{} 1} \minus{} n^{n \plus{} 1} \equal{} 0$, so we have that $ a^{m} \plus{} a^{n}\ge m^{m} \plus{} n^{n} \plus{} 0$ as desired.

QED[/hide][/quote]

Your proof is not quite right.

see here
http://www.artofproblemsolving.com/Forum/viewtopic.php?p=280201
 :winner_first:
and the same method can prove the generalisation for $ n_i\in\mathbb N \ \ \ (i\equal{}1,...,k)$:

$ \sum a^{n_i}\ge\sum {n_i}^{n_i}$ where $ a\equal{}\frac{\sum {n_i}^{n_i\plus{}1}}{\sum {n_i}^{n_i}}.$

[hide="Solution"]Note that \[a=m(1+\frac{a-m}{m})=n(1+\frac{a-n}{n})\]
Using the Bernoulli's  inequality ,\[a^m=m^m(1+\frac{a-m}{m})^m \ge m^m(1+a-m)\] and  \[a^n=m^m(1+\frac{a-n}{n})^n \ge n^n(1+a-n)\]  Adding we have  ${a^m+a^n\ge (m^m+n^n)+a(m^m+n^n)-(m^{m+1}}+n^{n+1})$.Putting the value of $a$,we get \[a^m+a^n\ge (m^m+n^n)\] as desired
$\blacksquare$[/hide]

Just another solution via Induction:

Let the given statement be $P(m,n)$, base case is trivial.  Now assume that its true for all $i\le m$ and $j\le n$ for some $m,n\in \mathbb{N}$. Its easy to see that $P(m,n)\Rightarrow P(m+1,n+1)$. Its easy to see that $a^{m+1}+a^n<m^{m+1}+n^n$ and $a^{m}+a^{n+1}<m^{m}+n^{n+1}$ cant be simultaneously true, if they were then adding both of them will give a contradiction. Thus at least one of them is false. But by symmetry both will be false thus $a^{m+1}+a^n\ge m^{m+1}+n^n$ and $a^{m}+a^{n+1}\ge m^{m}+n^{n+1}$ and we conclude that $P(m,n)\Rightarrow P(m+1,n)$ and $P(m,n)\Rightarrow P(m,n+1)$. Thus from the principle of induction the result holds.


analytic geometry
geometry unsolved
geometry
Steiner Trees
Germany
TST
Team Selection Test

Let $M$ be a set of points in the Cartesian plane, and let $\left(S\right)$ be a set of segments (whose endpoints not necessarily have to belong to $M$) such that one can walk from any point of $M$ to any other point of $M$ by travelling along segments which are in $\left(S\right)$. Find the smallest total length of the segments of $\left(S\right)$ in the cases

[b]a.)[/b] $M = \left\{\left(-1,0\right),\left(0,0\right),\left(1,0\right),\left(0,-1\right),\left(0,1\right)\right\}$.
[b]b.)[/b] $M = \left\{\left(-1,-1\right),\left(-1,0\right),\left(-1,1\right),\left(0,-1\right),\left(0,0\right),\left(0,1\right),\left(1,-1\right),\left(1,0\right),\left(1,1\right)\right\}$.

In other words, find the Steiner trees of the set $M$ in the above two cases.

These are so counterintuitive.. I believe the answer to the first one to be $\sqrt 6+\sqrt 2$ and I can find a construction with $2(\sqrt 6+\sqrt 2)$ for the second one, but I have no idea whether this is correct.

I say they are counterintuitive because, for example, I struggled for quite some time to prove that the answer to the first one was $4$, until I realized that if we let $ABCD$ be a square and $O$ its center, then we can take $F_1,F_2$ to be the Fermat-Torricelli points of $OAB,OCD$, and we can consider the segments $F_1O,F_1A,F_1B,F_2O,F_2C,F_2D$. An easy computation shows that the sum of these is $\sqrt 6+\sqrt 2=3.8637033..<4$.

Like I said, I don't know if this is the actual answer.

My example for [b](b)[/b] gives $2\sqrt{3}+4$  ...

What is the best known estimate for [b](b)[/b], Peter?

To the problem, I think informatics will be a little usefull here. What about Minimal Spanning tree??? I think what we have to find for this set of points is the minimal spanning tree... A greedy strategy will work. $O(N^2)$ :) :D

Actually, it's called a [url=http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK4/NODE181.HTM]Steiner tree[/url], as Darij mentioned in the very first post in this topic :).

I am very sorry for the above post, I didn't even read the problem carefully and made a connection to an informatics problem I have recently solved. Sorry again for my not very smart post above....

Now I have read the link that grobber provided (thank btw). Just for the sake of completeness, every point that we add must me connected only to 3 other points, and consequently all angles must be 120 degrees. But can someone prove this?
I mean the part with the 3 points?

[quote="Myth"]What is the best known estimate for [b](b)[/b], Peter?[/quote]

well, i don't really know, myth. the best estimate i explicitly know is that one you gave. besides, i know that someone claims to have solved that problem but i neither know who it was nor what's the best solution. however, maybe something like below(all angles are 120?) might be better:

Rrrr... [b]Myth[/b]

Wow, it is really fantastic tree.

ok, if i didn't miscalculate it gives something like 7.55703... which is worse than $2\sqrt{3}+4$.

How did you do it ????  :?

Anyway, we have a chance to prove that our supposition is correct.

how i did it: i just used the angles to think of a construction for the points and then explicitly calculated the points using mathematica. as you mentioned, there is a chance to prove it, just by considering lots of cases and in each case, calculating the length but that's not what a TST problem is supposed to be like. btw, can someone calculate the length for the following(again, all angles at the extra points are 120):

Try this, Peter. :)

All angles that look like 120 are 120.

Actually, it is the same what I proposed and what Peter meant.


[quote="bkunchanapalli"]when are iit jee 2006 results released[/quote]

i think tomorrow.does any body know iit study circle in hyderabad

I guess the results coming on 31st......I dont know about any study circle in hyderabad though...... :)

the results are out.How did rushil and bubka do?The topper Raghu went to the internat. math olymp. training camp as well.

WoW.Varun got AIR 190!!!Awesome!! :wow:

And there's a person named sathej gopalakrishnan.If its the AoPS sathej,CONGRATULATIONS!!!(AIR-927).hehe,I saw ur photos as well  :D


Given three $a$'s, three $b$'s, and two $c$'s, how many different arrangements are there if no $a$'s can be side by side?

[quote="xscapezaer"]Please correct me if I'm wrong...(I usually am)
[hide]
To make sure that we never have any $a$'s side by side, we first find the total number of ways distinct arrangements of these letters. This is $\frac{8!}{3!3!2!}$ which is 560. Then, we subtract the number of ways we can have two $a$'s side to side, which is $\frac{7!}{3!2!2!}$ or 210. Our final result is 350[/hide][/quote]

I get a different answer then you...I get 200.  You subtracted the number of ways you can have 2 as side by side wrong I think...and you can have three side by side.

Yes, the answer is 200, could you please post your solution? I have a serious mental block right now...

[hide="hint"]The basic idea is to place the $b$'s and $c$'s first.  Then place the $a$'s.[/hide]

[hide="solution"]The number of ways to place the $b$'s is ${5\choose 3}=10$.  It is not ${8\choose 3}$ because we don't care where the $a$'s will go yet.

Now place the $a$'s.  They can go in $6$ different places (because there is a sequence of 5 letters) and none of the $a$'s can go next to each other.  So it has to be ${6\choose 3}=20$.

Multiply the two numbers gives us $\boxed{200}$.[/hide]

[quote="xscapezaer"]Please correct me if I'm wrong...(I usually am)
[hide]
To make sure that we never have any $a$'s side by side, we first find the total number of ways distinct arrangements of these letters. This is $\frac{8!}{3!3!2!}$ which is 560. Then, we subtract the number of ways we can have two $a$'s side to side, which is $\frac{7!}{3!2!2!}$ or 210. Our final result is 350[/hide][/quote]

[hide]The number of ways we can have two $a$'s side by side is:
$\frac{7!}{3!2!}-\frac{6!}{3!2!}= 360$

Sorry, I don't know how to explain this very well.[/hide]

[hide="Another approach"]
[b]PIE[/b] (Principle of Inclusion-Exclusion). First, treat the three $a$'s as separate; then, two of them as one element and the third $a$ as separate; then, the three of them together as one element.

$\frac{8!}{3!3!2!}-\frac{7!}{3!2!1!1!}+\frac{6!}{3!2!1!}= \boxed{200}$.[/hide]


I'm more a logician than mathematician and am currently struggling with solving:

D(n) = a*D(n-1) + b*[Y - sum(D(0) to D(n-1))]

The level of complexity is spiralling out of control for me to handle. How do I tackle this or what is the answer? Any help greatly appreciated.

Best wishes.

Forgot to mention: I'm looking for D(n) in terms of a, b, and Y

Thanks again!

I am not sure that this recursion has a simple closed-form solution.  In what context did it arise?  Under certain circumstances, it can be simplified, but I am not sure that in general it can be.

I'm constructing a project whereby a variable, D(T) consists of (the sum) of two components: D(a) and D(b). D(a) depends on the previous value of D(T) but D(b) depends on the stock of D(T) compare to some limit, Y; hence the sum from D(0) to D(n-1) part in the original question. Call this stock H. Thus I am trying to find expressions for how D(a), D(b), H, and finally D(T) grow dependant on the values of a, b, and Y.

My peers had expressed concern that it was insolvable but thought there might be some package which could churn it over. I prefer manual solutions though - call me old fashioned!

So do you think Excel/Maple with actual values of a, b, Y is the only way to go - i.e. no generalisation possible?

I take it back!  This is totally tractable.  Let's go!

$H(t) = H(t- 1) + D(t)$ (by definition) and
$D(t) = aD(t-1) + bY - bH(t-1)$.  Let's try and build an expression by elliminating H.
$D(t) - D(t - 1) = aD(t-1) + bY - bH(t-1) - \left(aD(t-2) + bY - bH(t-2)\right) = aD(t - 1) - aD(t - 2) - b\left(H(t-1) - H(t-2)\right)$
However, we know
$H(t -1) - H(t -2) = D(t -1)$, so this gives us the relation
$D(t) - D(t - 1) =aD(t - 1) - aD(t - 2) - bD(t-1)$.  Collecting terms, (this threw me off because we've lost Y, but that's actually a bonus feature and it will come back later):
$D(t) + (b - 1 - a)D(t-1) + aD(t - 2) = 0$.  This is a simple linear recursion.  We know that it has general solutions of the form
$D(t) = c_1 r_1^t + c_2 r_2^t$ where $r_1, r_2$ are roots of the characteristic equation $X^2 + (b - 1 - a)X + a = 0$ and $c_1, c_2$ are any constants.  We solve the equation (dependent on $a, b$ and very ugly in the general case) to find $r_1, r_2$.  Then, we (presumably) know the initial value $D(0)$ and $D(1) = aD(0) + bY - bD(0)$, so we can solve for $c_1, c_2$ by equating our expression with those two terms to get linear equations (also massively ugly).  And that's that! :juggle:

Thank you for all your help. I will mull this over.

It would be good to also get a solution to:

D(m) = b(Y - sum(D(0) to D(m-1))

and also: Sum [D(0) to D(m)]

I forgot to orgiginally mention that: D(0) = 0 and b > 0 and m takes integer values

I've played around with things a little for the Sum [D(0) to D(m)] and as b approaches 1 then the sequence converges to Y (the closer b gets to 1, the quicker this convergence takes place) whereas if b > 1 then the sequence springs above Y and then
i/ convergingly oscillates towards Y if b < 2
ii/ oscillates between 2Y and -2Y indefinately if b = 2
iii/ divergingly oscillates around 0.

It would be great to therefore get the algebra to back this up. Again, I'm afraid it's beyond me.

Similarly, for the original expression I posted, if we consider the sum of all these, i.e. Sum[D(0) to D(n)], getting algebraic expression of this would be great. As I say it seems simple with similar oscillatory patterns depedning on the values of a, and b, with Y merely affecting the scale. However I'd rather back up my playing around figures with algebraic proof.

Any ideas?

Thanks in advance.

sorry, if b = 2, Sum[D(0) to D(m)] oscillates between 2Y and 0

Answers on a postcard... or message board

So, let me just give you a little more of the explanation that goes with my post:

My first two equations, in terms of H and D, were given: as H is the sum of terms of the sequence D, we get the next term of H from the previous by adding the appropriate term D.  The second equation was the given equation defining D.  I wanted to have an equation involving only one of these two sequences (so it would be solvable), so I connived to eliminate the H term from the second sequence through a clever manipulation.  The result was an equation in terms of the sequence D.  This was a linear recursive sequence, of the form

(*) $f(n + 1) = mf(n) + nf(n - 1)$

for constants $m$, $n$.  Equations of this sort (more general versions of the famous Fibonacci sequence) have a known solution form.  If you solve the quadratic equation $X^2 - mX - n = 0$, you will get two roots, $r_1$ and $r_2$.  Provided these two roots are different, any sequence that satisfies the equation (*) can be written in terms of them as

$f(n) = c_1 r_1^n + c_2 r_2^n$

where $c_1$ and $c_2$ are any constants.  Provided we know two different values of the sequence $\{f(n)\}$, we can solve for the constants and get an explicit expression for the sequence.

Let me do an example:

Let us say, in your original equation, that $a = 1, b = -\frac{1}{2}, Y = 3$.  Then (skipping over my manipulations and jumping straight to my final form), we have

$D(t) - \frac{5}{2}D(t-1) + D(t - 2) = 0$

The associated quadratic equation is

$X^2 - \frac{5}{2}X + 1 = 0$

Solving this however you like, we find that it has roots $r_1 = 2, r_2 = \frac{1}{2}$.  (Normally, they will not be so nice, of course, but I chose a, b and Y to make the calculation more pretty.)  This means that the sequence satisfies

$D(t) = c_1 2^t + c_2 \frac{1}{2^t}$

for some constants $c_1, c_2$.  We know that $D(0) = 0$ and $D(1) = bY = -\frac{3}{2}$.  So, plugging in,
$0 = D(0) = c_1 2^0 + c_2 \frac{1}{2^0} = c_1 + c_2$ and
$ -\frac{3}{2} = D(1) = c_1 2^1 + c_2 \frac{1}{2^1} = 2c_1 + \frac{c_2}{2}$.
These are just linear equations, so we can solve them to find that $c_1 = -1, c_2 = 1$ and so our sequence is
$D(t) = -(2^t) + \frac{1}{2^t}$.

If you calculate out the first few values using your recursion and compare them to the values from this formula, you'll see they agree.

Once we know that, it's clear to see from the roots what the behavior will be.  If we take $a = 0$, which is what you suggested in your last post, the quadratic equation will simply be $X^2 - (b - 1)X = 0$ which has roots 0 and $b - 1$.  We have to take $0^0 = 1$ to make this make sense, but when we do, we see that the general solution will be

$D(t) = c_1 (b - 1)^t - c_1 0^t$

(It happens that $c_1 = \frac{bY}{b-1}$, but this is not so important.)  It should be immediately clear why the behavior of this function is what you described, based on knowledge of how exponential functions behave.

Now, if you want to find out what H is, we already know H in terms of D -- it's just the sum of the first m terms.  Since we have a "nice" expression for D, calculating H isn't hard at all -- if you split the $r_1^t$ and $r_2^t$ portions up, you're summing two geometric sequences.

Feel free to ask any more questions, by the way.  I may be out of commission on this forum for the next few days, but hopefully someone else will fill in (or you'll have to wait until after the weekend).

Thanks that's really great. I often seem to end up with what (for me!) are complicated problems in areas I don't specialise in, working from basic assumptions.

If you would like a credit on my research just let me know.

All the best.


LaTeX
integration
calculus
calculus computations

Please learn to type in $ \text{\LaTeX}$:

$ \int_{1/2}^2 \frac {1}{x} \csc^{101} \left(x - \frac {1}{x}\right)\,dx$.

Let $ I$ be the given integral. Performing the change of variables $ x = \frac1t$ we have

$ I = \int_{1/2}^2 \frac1t \csc^{101} \left[-\left(t - \frac1t\right)\right]\,dt = -  \int_{1/2}^2 \frac1t \csc^{101} \left(t - \frac1t \right)\,dt = -I => I = 0$.


Does anybody know where I can get the actual [i][b]proof[/b][/i] of Fermat's Last Theorem by Andrew Wiles?

I don't think it'll be of much use to you unless you are very familiar with higher mathematics.


I'd appreciate any help you can offer toward rigorous, yet simple and clear, proofs in response to questions (a) through (f) below:

Most positive integers can be expressed as a sum of two or more consecutive positive integers. For example, 24 = 7 + 8 + 9, 36 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8, and 51 = 25 + 26.  A positive integer that cannot be expressed as a sum of two or more consecutive positive integers is therefore interesting. The simplest example of an interesting number is 1.

(a)	Show that no other odd number is interesting.
(b)	Show that 14 is not an interesting number.
(c)	Show that 82 is not an interesting number.
(d)	Find three ways to show that 190 is not an interesting number.
(e)	Find three ways to show that 2004 is not an interesting number.
(f)	How many interesting numbers precede 2004?

I tried phrasing (a) as a conditional--namely, "If n is an odd integer greater than 1, then n is not interesting"--but couldn't see a proof.  I got a bit further with the contrapositive--namely, "If n is interesting, then is an even integer"--but still couldn't see a proof.

A
[hide]All odd numbers can be expressed in the form $ 2n \plus{} 1$.  This becomes $ (n) \plus{} (n \plus{} 1)$, which are consecutive.[/hide]

B
[hide]$ 2 \plus{} 3 \plus{} 4 \plus{} 5 \equal{} 14$[/hide]

C
[hide] We need either $ 2n\plus{}1$ or $ 4n$ integers to ensure an even integer is expressible by consecutive integers.  Notice if we have an odd number, then we can write $ ..., n\minus{}1, n, n\plus{}1,...$ as the sum.  This suggests that the the sum is $ \equiv 0 \mod 2a$, where $ a$ is the number of consecutive integers.  This shows that $ 82$ isn't expressed with an odd number of integers.

If we have four integers, $ n\minus{}1, n, n\plus{}1, n\plus{}2$, the sum must be $ \equiv 2 \mod 4$, which works for $ 82$.  Thus, $ 19\plus{}20\plus{}21\plus{}22\equal{}82$.[/hide]

D
[hide]By argument above, $ 190\equal{}2\cdot5\cdot19$.  We can have 5 integers $ 36\plus{}37\plus{}38\plus{}39\plus{}40$.  We can also have $ \sum_{n\equal{}1}^{19}n$, or 19 integers.  By second argument above, we can also have 4 integers $ 46\plus{}47\plus{}48\plus{}49$.[/hide]

Grr.  Someone already read this before.

Anyway,
E
[hide]$ 2004 \equal{} 2^2\cdot3\cdot167$.  We have three integers $ 667 \plus{} 668 \plus{} 669 \equal{} 2004$.  Also, $ 2004 \equiv 4 \mod 8$.  We have eight integers $ \sum_{n \equal{} 247}^{254}n$.  Finally, $ 2004 \equiv 12 \mod 24$, so $ \sum_{n \equal{} 72}^{95}n$ works as well.[/hide]

Edit for last post:[hide] The $ \equiv 4 \mod 8$ is only one case.  In general, it must be $ \equiv 2n \mod 4n$.[/hide]

For F
[hide]Only one odd number works.  For $ n$, $ n \equiv 2 \mod 4$, there are only multiples of four left.  As we increase $ a$ in $ n \equiv 2a \mod 4a$, n will never be divisible by 4.  We have $ \dfrac{2004}{4}\plus{}2\equal{}503$.  The extra 2 come from $ 1, 2$.[/hide]

Darn! I'm not fast enough at composing clear answers. It's all answered up already.
So, for (f) there are 11 interesting (power of two) numbers: 1, 2, 4, 8, 16, ..., 1024.
General strategy for generating sums:
All numbers that are not powers of 2 will have an odd factor that will be used to figure out the sum.
If we have a number with even and odd factors, we can write it as n = f (2m+1), with f and m positive integers. If our odd factor (2m+1) is small, we try to write n as a sum of (2m+1) consecutive integers centered on f
n = (f-m) + (f-m+1) + .... + f + .... + (f+m)
It can only fail if (f-m)<1, or f<m+1.
In that case we write a sum of 2f consecutive numbers centered on m + (m+1)
n = (m+1-f) + .....+ m + (m+1) + .... + (m+f) with (m+1-f)>0.

This sounds awfully familiar. This problem (or very similar) has been out before.

[quote="azn6021023"]A
[hide]All odd numbers can be expressed in the form $ 2n \plus{} 1$.  This becomes $ (n) \plus{} (n \plus{} 1)$, which are consecutive.[/hide]

B
[hide]$ 2 \plus{} 3 \plus{} 4 \plus{} 5 \equal{} 14$[/hide]

C
[hide] We need either $ 2n \plus{} 1$ or $ 4n$ integers to ensure an even integer is expressible by consecutive integers.  Notice if we have an odd number, then we can write $ ..., n \minus{} 1, n, n \plus{} 1,...$ as the sum.  This suggests that the the sum is $ \equiv 0 \mod 2a$, where $ a$ is the number of consecutive integers.  This shows that $ 82$ isn't expressed with an odd number of integers.

If we have four integers, $ n \minus{} 1, n, n \plus{} 1, n \plus{} 2$, the sum must be $ \equiv 2 \mod 4$, which works for $ 82$.  Thus, $ 19 \plus{} 20 \plus{} 21 \plus{} 22 \equal{} 82$.[/hide]

D
[hide]By argument above, $ 190 \equal{} 2\cdot5\cdot19$.  We can have 5 integers $ 36 \plus{} 37 \plus{} 38 \plus{} 39 \plus{} 40$.  We can also have $ \sum_{n \equal{} 1}^{19}n$, or 19 integers.  By second argument above, we can also have 4 integers $ 46 \plus{} 47 \plus{} 48 \plus{} 49$.[/hide][/quote]

azn, these answers are phenomenal--thank you so much.  Can you point me to any books that would help me learn better how to solve this kind of problem?  All the best.

[quote="azn6021023"]A

C
We need either $ 2n \plus{} 1$ or $ 4n$ integers to ensure an even integer is expressible by consecutive integers.  Notice if we have an odd number, then we can write $ ..., n \minus{} 1, n, n \plus{} 1,...$ as the sum.  This suggests that the the sum is $ \equiv 0 \mod 2a$, where $ a$ is the number of consecutive integers.  This shows that $ 82$ isn't expressed with an odd number of integers.

If we have four integers, $ n \minus{} 1, n, n \plus{} 1, n \plus{} 2$, the sum must be $ \equiv 2 \mod 4$, which works for $ 82$.  Thus, $ 19 \plus{} 20 \plus{} 21 \plus{} 22 \equal{} 82$.

Can you please explain the above?  In particular:

1.  Why is it the case that "We need either $ 2n \plus{} 1$ or $ 4n$ integers to ensure an even integer is expressible by consecutive integers" ?

2.  Why is it the case that "Notice if we have an odd number, then we can write $ ..., n \minus{} 1, n, n \plus{} 1,...$ as the sum" ?

Okay, we do a parity check on odd numbers.  Even sums require even numbers of odd numbers.  If we set our middle term to be even and we have an odd number of terms, the sum will be even, because every odd number greater than the middle term has a counterpart less than the middle term.

If there is no middle term (even number of terms), we can still create even sums.  Doing another parity check shows that we can only use 4, 8, 12, etc. terms; otherwise, we will have an odd sum.

As for part two, if $ n$ is the middle term and we have an odd number of terms, we can write the sum as $ ...,n \minus{} 1,n,n \plus{} 1,...$ because it is symmetric about $ n$ and they are all consecutive.


These aren't hard to make using Kalva's website and TexnicCenter, and they are so much cleaner than printing off Kalva.  I'm starting with 1992 here, but the idea is for people to make PDFs and post them here.  We can also repost the solutions floating around.

EDIT: [size=150][b]Pictures ADDED; Please redownload AGAIN![/b][/size]

Thanks. You are right. It is a lot better than the kalva page.

Here is the 1st year, 1983.  I included the Kalva images, and the layout looks very nice.  This time, I used AoPS Resources questions, and they are written better.  The only thing that I wish I could change is the quality of images.  If someone can make better images, post them here and I will add them to the PDF.

Here is the 1984 AIME PDF.  Someone please make some nice diagrams for these!

Here is the 1990 PDF. Please PM me with corrections.

I don't know how to implement them into pdf's, but here are sketchpad diagrams for the 1984 AIME.  If they're any help, I can make more.

The image looks nice in Sketchpad, but I can't figure out how to convert it to JPG without losing quality.  Any suggestions?

Also, Xaero, nice!  Can you send me the LaTeX so I can format it like the rest of them?  Perhaps we will have a whole set eventually.  I will soon post a template and easy instructions for including an image so we can get more people to help.

Sorry for DP, but I have a reformatted version of the 1990 AIME, courtesy of Xaero.  Also, I am putting these all on a [url=http://seansoni.googlepages.com/contests]website[/url], with other resources, (which is definitely a work in progress).

Also, feel free to compile an AIME with pictures missing.  Just send me the TeX file, and I will add in the pictures from Kalva (or pics you send me).

I've seen several places with these aime documents.  They should all be collected into one easily accessible resource/thread on aops.

I transfered the AIME II from 2005 into a PDF.  It's not formatted as well as yours though.

[b]@seesaw:[/b]

If you send me the TeX file, I can make it nicer, and format it to fit in.
[b]
@jhcreinhadrt:[/b]

See the [url=http://www.artofproblemsolving.com/Wiki/index.php/Resources]Wiki Resources[/url] page I made, and [url=http://seansoni.googlepages.com/contests]this[/url].

Reformatted AIME II 2005, attached.

Eventually I will run out of attachbox space; when that happens I will start uploading these on my website and direct linking from here.


Nothing. What does that have to do with the earth Ameem? LOL

i took a test on ecology. that was a coincedence. i also dunked some admins in a dunking booth, ate cookies, and had hot tea for breakfast.

[quote="GoBraves"]What did you do for Earth Day??

[hide="Here is what I did"]I cleaned my room[/hide][/quote]

I don't know if the ecologist would really consider that a pro-nature act, but I am sure your mother is greatful for that!  :D

I skipped school, attending an Open House event at the UW College of Engineering

We picked up Garbages on the highways...
SO MANY CIGARETTE BUTTS AND BEER BOTTLE CAPS!!!!!!!!!!!!!!!!!!!!

Earth day Earth day Earth day ...~~~

i yelled "Hail to Earth Day in school"
awesome!!!!!!!!!!


A monument consists of a flagpole 15m tall standing on a mound in the shape of a cone with vertex angle 140degrees. How long a shadow does the pole cast on the cone when the angle of elevation of the sun is 62degrees?
(answer is 10.5)
(please explain/show the picture if possible)

its a simple  application of  heights  and distances.   got it? :?:


A palindrome is a number that is read the same way front and back like 513315.
What is the difference between the number of 10 - digit palindromes and the number of 6 - digit palindromes?

Have fun! :)

I bet I can!
[hide="Solution"]
For a ten digit palindrome, we only care about the last 5 digits and for a six digit one, we only care about the last 3.  For the 10 digit one, the first digit can be anything but 0, and then the next 4 can be anything.  The last 5 must match the first 5 so each of those have only one possibility.  Hence there are $ 9\cdot 10\cdot 10\cdot 10\cdot 10\equal{}90,000$ 10 digit palindomes.  For six digits, there are $ 9\cdot 10\cdot 10\equal{}900$ so the difference is $ 89,100$.[/hide]

Easy. 89,100. Only 1/2 the number of total digits in a palindrome even matter.

I'm pretty sure I already pointed that out in my solution.  And you give us no clue as to how you came up with the number 89,100.


it says chat blazer has a digital signal error and asks if i should run it or not.
i pressed run, but is this an error on chat blazer or i should just press run every time
i use firefox

It's fine to go ahead and continue, clicking OK, Allow, or whatever your browser's dialog box says.


Segments AB and AC form a right angle. AB has a length of 3. The figure is made into a quarter circle by forming an arc from point C to point B. Square AEFG is then inscribed in the triangle such that AE and AG lie on BA and AC respectively and F is tangent to BC. A semi-circle is then created with it's center at E and radii  EF and EA and the other radius partly on EB. What is the area of circle E over the area of quarter circle A?

another one of my own problems.

if i understood correctly, AC=AB=3, otherwise we could not form an arc. if EF=s, AG=s, FG=s. since $ FGC\sim BAC$, CG=s, so s=1.5. then just find the areas


Find three positive integers $ x,y \text{ and } z\,(x\neq y, x\neq z, y\neq z)$ such that $ \frac {1}{x} \plus{} \frac {1}{y} \plus{} \frac {1}{z} \equal{} k,\,k$ integer.

How do you find the solution?

And how do you proof that there are no solution for $ k \geq 3$ ?

:D $ \frac {1}{x} \plus{} \frac {1}{y} \plus{} \frac {1}{z}\leq3$
If $ \frac {1}{x} \plus{} \frac {1}{y} \plus{} \frac {1}{z}\equal{}3$ then
x=1 y=1 z=1 but $ (x\neq y, x\neq z, y\neq z)$

[quote="TFPNH"]And how do you > proof < ...[/quote]
How do you "prove" ...

That restriction is basically saying that x, y, and z are all distinct, correct?

[hide="solution"] As positive integers, $ x,y,z\ge{1}$. Since $ \frac{1}{a}$ decreases as a increases, the value of $ \frac{1}{x}\plus{}\frac{1}{y}\plus{}\frac{1}{z}$ is less than or equal to 3, with equality occuring when x=y=z=1. However, we're given that x, y, and z are all distinct, so that is impossible and k must be 2 or 1.

Without loss of generality, assume x<y<z.

k=1: Assume that x>2. Then, the value of $ \frac{1}{x}\plus{}\frac{1}{y}\plus{}\frac{1}{z}$ is at most $ \frac{1}{3}\plus{}\frac{1}{4}\plus{}\frac{1}{5}$, which is less than 1. Hence, x must be 2. That means $ \frac{1}{y}\plus{}\frac{1}{z}\equal{}\frac{1}{2}$. Now, assume that y>3. Then the value of $ \frac{1}{y}\plus{}\frac{1}{z}$ is at most $ \frac{1}{4}\plus{}\frac{1}{5}$, which is less than $ \frac{1}{2}$. Hence, y must be 3. We then find that   z is 6. Hence, (x, y, z) is any permutation of (2, 3, 6).

k=2: Since x, y, and z are all distinct, the value of $ \frac{1}{x}\plus{}\frac{1}{y}\plus{}\frac{1}{z}$ is at most $ \frac{1}{1}\plus{}\frac{1}{2}\plus{}\frac{1}{3}\equal{}\frac{11}{6}<2$, so there are no solutions here.

So all solutions are $ (x, y, z)\equal{} (2, 3, 6), (2, 6, 3), (3, 2, 6), (3, 6, 2), (6, 2, 3),$ and $ (6, 3, 2)$.[/hide]

Very nice explanation. Good job [b]xpmath[/b].


algebra
polynomial
number theory
greatest common divisor
algorithm
algebra proposed

I believe it's sufficient to prove that two irreducible polynomials over the rationals either share no roots or are identical.  If they share a root, then we consider the field extension generated by it.

The GCD of two polynomials is obtained by applying Euclid's algorithm and this involves only additions, subtractions, multiplications and divisions. Therefore, if the two polynomials have rational coefficients, the same happens to their GCD.

[quote="Nemion"]Prove that if two polynomials with rational coefficients share a root, then their MCD is a polynomial with rational coefficients.[/quote]

May I know what "MCD" is?

[quote="t0rajir0u"]Maximal (i.e. greatest) common divisor.[/quote]

Thank you; that's what I guessed.  I assume MCD is not a very well-used term.


Can someone explain the Ball and Urn principle to me please?

The number of ways to place $b$ balls in $u$ urns is ${b+u-1\choose b}$

There are $u-1$ separators that indicate urns. ummm...im not really good at explaining.  look it up on wikipedia or mathworld.com.


"a:0:{}}}'); ?>a:0:{}}}'); ?>" appears at the top of the screen in MathLinks mode. I have IE7.

I hope I'm not repeating what someone else has already said.


[quote="Aafour"]use the unite circle to explain why cos (bi/3) = cos (5bi/3)[/quote]

What's your "definition" of [b]bi[/b]? :maybe:

$ \cos x \equal{} \cos (2\pi \minus{} x)$...


linear algebra
matrix
induction
function
real analysis
real analysis unsolved

Let $ f$ $ \mathbb N *\mathbb N \to \mathbb N$
$ (x,y)\to \frac{(x\plus{}y)(x\plus{}y\plus{}1)}{2}\plus{}y$
Prove that $ f$ is a bijection

Can you prove that $ f$ is an injection and a surjection?

Well, writing out the $ \mathbb f{N}*\mathbb f{N}$ like this

$ \begin{matrix} (1,1) & (1,2) & (1,3) & (1,4) \\
(2,1) & (2,2) & (2,3) & (2,4) \\
(3,1) & (3,2) & (3,3) & (3,4) \\
(4,1) & (4,2) & (4,3) & (4,4) \\
\end{matrix}$

And starting from the top left (1,1), draw lines in a way to mark each placement.
Go from $ (1,1)$ to $ (2,1)$ to $ (1,2)$ to $ (3,1)$ to $ (2,2)$ to $ (1,3)$ to $ (4,1)$ to $ (3,2)$ etc...
Then you can derive a formula like this.
$ f(x,y) = \frac {\left(x + y - 1\right)\left(x + j - 2\right)}{2} + y$
but from here I am not really sure how to get it into the form you have :( Sorry.
The point of this was to go through every point and correspond an positive integer to it.
Like $ f(1,1) = 1$
$ f(2,1) = 2$, etc..

clearly $ f(n,0) \equal{} \binom{n\plus{}1}{2} \equal{} 1\plus{}2\plus{}\ldots\plus{}n$ for all integers $ n\geq 0$.

for $ 0\leq i\leq n$, $ f(n\minus{}i,i)\equal{}f(n,0)\plus{}i$ (since $ (n\minus{}i)\plus{}i\equal{}n\plus{}0$)

by induction and the above, $ A_n\triangleq\{(a,b)\in\mathbb{N}^2: a\plus{}b\leq n\}$ satisfies $ f(A_n)\equal{}\{0,1,\ldots,\binom{n\plus{}1}{2}\minus{}1\}$.

This shows that $ f$ is surjective.  If $ f$ were not injective, so that $ f(a,b)\equal{}f(c,d)$ for some $ (a,b),(c,d)\in\mathbb{N}^2$ with $ (a,b)\not\equal{}(c,d)$, then, as long as $ N\geq \max(a\plus{}b,c\plus{}d)$, we have $ f(A_N)\leq |\{(a,b)\in\mathbb{N}^2: a\plus{}b\leq N\}|\minus{}1\equal{}\binom{N\plus{}1}{2}\minus{}1$.  On the other hand, $ f(A_N)\equal{}|\{0,1,\ldots,\binom{N\plus{}1}{2}\minus{}1\}|\equal{}\binom{N\plus{}1}{2}$, a contradiction.

i'm aware that the last two paragraphs of this proof are very silly, nevertheless, i don't see a conspicuously less hand-wavy way of doing it.

This problem is a classical one, and as such has surely appeared here before.
However, let us settle it "once and for all."

I'll do a bit more than what's required, namely I'll also precise, for some given $ n \in \mathbb{N},$ its preimage $ (x, y).$

First off, $ f$ is indeed a mapping from $ \mathbb{N}^2$ into $ \mathbb{N}$ since, for any pair $ (x, y)$ of nonnegative integers, one of the two integers $ x + y$ or $ x + y + 1$ is even (or one can also notice, like [b]blahblahblah[/b], that $ \frac {(x + y)(x + y + 1)}2 = 1 + 2 + \ldots + (x + y)$ is an integer for $ x + y \ge 1$).

As a little note, and as previously noticed by [b]Fermat's Little Turtle[/b], the numbering of $ \mathbb{N}^2$ was done in the following way :
\begin{tabular}{|c|c|c|c|c|c|c|c|c} & 0 & 1 & 2 & 3 & \ldots & x & \ldots \\
\hline 0 & 0 & 1 & 3 & 6 & & & & \\
\hline 1 & 2 & 4 & 7 & & & & \\
\hline 2 & 5 & 8 & & & & & \\
\hline 3 & 9 & & & & & & \\
\hline \vdots & & & & & & & \\
\hline y & & & & & & & \\
\hline \vdots & & & & & & & \\
\end{tabular}
On a parallel line to that of equation $ y = - x,$ the sum $ x + y$ is constant. The same goes for the expression $ \frac {(x + y)(x + y + 1)}2$ and when we go down by 1 for $ y,$ we move by 1 in the numbering.

[b]Lemma :[/b]
$ \forall n \in \mathbb{N}, \exists ! k \in \mathbb{N} / \frac {k(k + 1)}2 \le n < \frac {(k + 1)(k + 2)}2.$
[b]Proof :[/b]
I'll leave this to the reader, just mentioning that if one wants to get $ k$ explicitly in terms of $ n,$ it is given by :
$ k =  [\frac { - 1 + \sqrt {8n + 1}}2  ].$

Now let us show that $ f$ is surjective (and while we're at it, let us determine the preimage of a given $ n.$)
Let $ n$ be a nonnegative integer and let $ k =  [\frac { - 1 + \sqrt {8n + 1}}2  ].$
We let $ \{\begin{array}{rrr} x + y & = & k \\
y & = & n - \frac {k(k + 1)}2 \end{array} $
At first, $ y + \frac {(x + y)(x + y + 1)}2 = n.$ But it still remains to prove that the so-defined $ x$ and $ y$ (which are clearly integers) are nonnegative integers.
Since $ \frac {k(k + 1)}2$ is a nonnegative integer and $ n \ge \frac {k(k + 1)}2,$ $ y$ is indeed a nonnegative integer.
Then, $ \frac {k(k + 3)}2 = \frac {k(k + 1)}2 + k$ is also a nonnegative integer and besides,
$ \frac {k(k + 3)}2 - n \ge \frac {k(k + 3)}2 -  ( \frac {(k + 1)(k + 2)}2 - 1  ) = 0,$ so that $ x$ is a nonnegative integer.
Thus, for some given $ n,$ if we let $ k, x, y$ be defined as above, we get that $ x$ and $ y$ are nonnegative integers such that $ f((x, y)) = n.$
Hence $ f$ is surjective.

Let us show that $ f$ is injective.
To do this, we show that if $ x$ and $ y$ are nonnegative integers satisfying $ y + \frac {(x + y)(x + y + 1)}2 = n,$ then necessarily, $ x + y = k$ (and $ y = n - \frac {k(k + 1)}2$).
So, let $ x$ and $ y$ be two nonnegative integers.
$ \frac {(x + y)(x + y + 1)}2 \leq \frac {(x + y)(x + y + 1)}2 + y = n$
$ < \frac {(x + y)(x + y + 1)}2 + (x + y + 1) = \frac {(x + y + 1)(x + y + 2)}2,$
and the lemma show that $ x + y = k.$ The uniqueness of the pair $ (x, y)$ is thus proven.

We're done, $ f$ is a bijection and its inverse function is :
${ f^{ - 1} : \mathbb{N} \to \mathbb{N}^2}, \ \ n \mapsto  ( \frac {k(k + 3)}2, n - \frac {k(k + 1)}2  )$
where $ k =  [\frac { - 1 + \sqrt {8n + 1}}2  ].$


1. What can you say about $ n$ if the value of $ \phi{(n)}$ is a prime number?

2. What can you say about $ n$ if the value of $ \phi{(n)}$ is the square of a prime number?

3. Solve $ \phi{(n)}=\frac{n}{6}$.

4. Give a simple criterion that allows you to predict the last four digits of $ a^{1000}$ from the value of $ a$.

[hide="1"]Consider $ n = [2^{a}] p_{1}^{b}p_{2}^{c}\ldots, b,c, \ldots > 1$, where the bracketed term exists iff. the number is even.
Then, $ \varphi ( n ) = [2^{a-1}] (p_{1}-1) p_{1}^{b-1}(p_{2}-1) p_{2}^{c-1}\ldots$

Note that all $ p_{i}$ are odd, since the only even case is already accounted for.

Note that for all $ p_{i}> 3$, the factor $ p_{i}-1$ is even and composite. Thus, $ n=2^{a}3^{b}$.

Also note that if $ a>2$, the number must be composite (has a factor of $ 2^{a-1}= 4k$) and if $ b>1$, the number must be composite (has a factor of $ (3-1)3^{b-1}= 6k$).

So, $ a=0,1,2$ and $ b=0,1$, leaving the possible cases $ n=1, 2, 3, 4, 6, 12$.

Checking $ n=3,4,6$ are the only solutions, and give $ \varphi (n) = 2$
[/hide]

[hide="2"]
[i]Again, brackets denote conditional factors.[/i]

As shown in my first post, $ \phi (n)$ is even if $ n$ has an odd prime factor, and also if it has more than one factor of $ 2$. unless it is $ 1$. $ n^{2}\equiv n \pmod{2}$ and the only even prime is $ 2$, it follows that $ \sqrt{\varphi (n)}\in \mathbb{N}\iff \varphi (n) = 2^{2}=4$.

We now search for numbers such that $ \varphi (n) = 4$. Again, note that the existence of any prime factor over $ 5$ will introduce a factor of $ p-1 > 4$, so the number is of the form $ n = [2^{a}] [3^{b}] [5]$.

If there is a factor of $ 5$, then $ 4[2^{a-1}][2 (3^{b-1})] = 4$ Because of the forced $ 2$ in the second set of brackets (which denote the existence of $ b$ factors of $ 3$), there are no factors of $ 3$. Also, there are either no factors of 2, or $ a-1 = 0 \implies a=1$.

Hence, $ 5 | n \iff n = 5, 10$

What if $ 5 \not | n$? Now we have $ 4 = [2^{a-1}][2 (3^{b-1})]$. If there are no factors of $ 3$, then $ 2^{a-1}=4 \implies n = 2^{a}= 8$. If there are factors of $ 3$, then we have $ [2^{a-1}] 3^{b-1}= 2$, and clearly $ 3^{b-1}= 1 \implies b = 1$. Then, $ 2^{a-1}=2 \implies 2^{a}= 4 \implies n=12$.

Compiling the results of all our cases, $ n=5,8,10,12$
 [/hide]

[hide="3"]

Let $ p_{i}$ be the $ i$th prime divisor of $ n$.

$ \varphi (n) = n \prod_{j}\left( 1-\frac{1}{p_{j}}\right) = n \prod \frac{p_{j}-1}{p_{j}}$

$ \varphi (n) = n/6 \iff \prod \frac{p_{j}-1}{p_{j}}= \frac{1}{6}$

This implies that there is exactly one more factor of $ 2$ in the denominator than in the numerator of the product expansion.

For $ p=2$, this works just fine, since $ \frac{2-1}{1}=\frac{1}{2}$. However, all other $ p_{i}$ add a finite number of factors of 2 to the numerator and none to the denominator. Hence, the only possible prime divisor of $ n$ is $ 2$. But even for $ 2$, the product expansion is $ \frac{1}{2}$, not $ \frac{1}{6}$.

Hence, there are no solutions.

[/hide]


If in a computer there's 15 different programs and you can only use 5 each day, how many different combinations are there?

Except $ 3\cdot 7\cdot 13\cdot 11\equal{}3\cdot 1001\equal{}\boxed{3003}$ :wink:

In general, $ \binom{n}{r}\equal{}\frac{n!}{r!(n\minus{}r)!}\equal{}\frac{n(n\minus{}1)(n\minus{}2)\cdots (n\minus{}r\plus{}1)}{r!}$.  $ \binom{n}{r}$ denotes the way to choose $ r$ objects from $ n$ if order doesn't matter.


A rectangular sheet of paper is folded so that two diagonally opposite corners come together.  If the crease formed is the same length as the longer side of the sheet, what is the ratio of the longer side of the sheet to the shorter side?

I can provide the solution if you need it, but:

[hide="Hint"]Use the Pythagorean theorem and similar triangles.
[/hide]


Let a,b,c be positive real numbers.Determine the minimum value of
$ (1\plus{}abc) [\frac{1}{a(1\plus{}b)} \plus{} \frac{1}{b(1\plus{}c)} \plus{} \frac{1}{c(1\plus{}a)}]$

Hello Hamddi  :lol:

we have :

$ \sum_{cyc}(\frac{1+abc}{a(b+1)}+1)=\sum_{cyc}(\frac{ab(c+1)+a+1}{a(b+1)})=\sum_{cyc}(\frac{b(c+1)}{(b+1)}+\frac{a+1}{a(b+1} ) \geq 6$

then $ \text{min}(LHS)=3$

equality when $ a=b=c=1$
 :)


LaTeX
inequalities
induction
superior algebra
superior algebra unsolved

suppose that we have $\leq_{1},\dots,\leq_{k}$ ordering on $\mathbb{N}$ such that $(\mathbb{N},\leq_{i})$ is well-ordering.($i=1,\dots,k$).show that there exist $x,y$ such that for any $1\leq i\leq k$ we have $x\leq_{i} y$.

why there are some error in my post all the simbol that i wrote in latex was shown as an original code :(  :?

I have slightly complicated solution with using Ramsey's theorem (I feel there are more simple solution).

Actually, we need to prove that for $(\mathbb{N},\leq_1)$ and $(\mathbb{N},\leq_2)$ there exists infinite (countable :) ) subset $M\in\mathbb{N}$ s.t. for all $x,y\in M$ relation $x\leq_1 y$ holds iff $x\leq_2 y$.

Consider infinite graph $G=(\mathbb{N},E)$, where vertices $x\in\mathbb{N}$ and $y\in\mathbb{N}$ are connected by mean of red edge iff ($x\leq_1 y$ and $x\leq_2 y$) OR ($y\leq_1 x$ and $y\leq_2 x$); and by mean of blue edge iff ($x\leq_1 y$ and $y\leq_2 x$) OR ($x\leq_2 y$ and $y\leq_1 x$).

Due to Ramsey's theorem we can find infinite monochromatic subgraph $G'$ (i.e. all edges in $G'$ have the same color).

If $G'$ is 'red' graph, we are done: $M=G'$.

Suppose $G'$ is 'blue' graph. Consider minimal element $a\in G'$ with respect to $\leq_1$ and minimal element $b\in G'$ with respect to $\leq_2$. Let $K$ be subset of $G'$ s.t. for all $x\in K$ set $\{y\in K\,|\,y\leq_1 x\}$ is countable (infinite). Note [b](!)[/b] that $b\in K$, so $K$ is nonempty. Therefore, we can find minimal element $k\in K$ with respect to $\leq_1$. Consider nonempty set $L=\{x\in G'\,|\,k\leq_2 x,\ k\neq x\}$. Let $l$ be minimal element of $L$ with respect to $\leq_2$. Thus we know $k\leq_2 l$, $k\neq l$. It implies that $l\leq_1 k$ $\Longrightarrow$ set $\{x\in G'\,|\,x\leq_1 l\}$ is [i]finite[/i]. Let $l'$ be successor of $l$ with respect to $\leq_1$ in $G'$. Then [b](!)[/b] $l'\leq_1 k$, $l'\neq k$. It means that $k\leq_2 l'\leq_2 l$. Contradiction with definition of $l$.
So it is impossible for $G'$ to be blue!

P.S. Maybe Sam-n will condescend and give some comments this time.

I think I get the idea of Myth!!
 Just simplify the text  :)

 We will prove that we can infact find an infinite chain whose order is preserved in any well-ordering.
 Let proceed by induction. Assume we have an infinite chain

 \[x_1 \leq x_2 \leq x_3 \leq .... \leq x_n \leq .... \]

 where all the inequalities hold in all first $k$ orderings. Now we will choose a subchain
\[x_{i_1} \leq x_{i_2} \leq ....\]
so that the inequalities also hold in the $(k+1)^{th}$ ordering ( called $\leq_{k+1}$ )

 Let $A_i = $ the set of all $x_j , j \geq i+1$ .
 Choose $x_{i_1}$ to be the smallest element in $A_1$ according to $\leq_{k+1}$
 Then $x_{i_2}$ to be the smallest element in $A_{i_1}$ , according to $\leq_{k+1}$, and so on...
 $x_{i_n}$ is the smallest element in $A_{i_{n-1}}$ , according to $\leq_{k+1}$. This process cannot stop since $A_{i_n}$ is always infinite.

 Now we have
 $x_{i_{n+1}}$ > $x_{i_{n}}$ for each $n$ so the chain we've created has it order preserved in $\leq_{k+1}$, so...... :D

[quote="dickchimney"]I think I get the idea of Myth!!
 Just simplify the text  :) [/quote]
It seems you are wrong about understanding ;)

[quote]This process cannot stop since $A_{i_1}$ is always infinite.[/quote]
It is wrong statement! ;)

[quote="dickchimney"][quote]This process cannot stop since $A_{i_1}$ is always infinite.[/quote]

 Hm... It must be $A_{i_n}$ is always infinite! That is what I need! I will edit it!![/quote]
No, any of $A_{i_n}$ can be finite! So your solution will not work. Sorry. ;)

$A_{i_n}$ is $ x_{i_{n}+1}, x_{i_{n}+2}, x_{i_{n}+3}.....$ ; why can it be finite?   As my induction hypothesis, it is [b]infinite[/b]

  I can be wrong!!If it is, can you explain clearly for me??
  Here is what I did:

 1. Choose an [b]infinite[/b] chain in the first well-ordering ( it is easy to prove that such a chain exist, namely : choose the smallest, the second smallest, and so on...!!)
 2. Process by induction, at each step we choose an infinite subchain in such a way that this subchain is an infinite chain with respect to a new well-ordering.
 3. My method of choosing subchain.

 At what step I was wrong??

[quote="Myth"]See:
first ordering is 2, 3, 4, ..., 1
second ordering is 1, 2, 3, 4, ...

Then $A_{i_1}=%Error. "varempty" is a bad command.
$.

Is it clear now? ;)[/quote]

 No ;)

  Now let take step 1, what we get?
   \[A = 2 \leq 3 \leq 4 \leq ....\]
 $1$ has been crossed out ( not consider it anymore )
 Then, step 2 indicate that
   $i_1 = 1, i_2=2....$

 If you dont believe, then just follow the three steps I mentioned above.
 If we can't agree, I think we need other to comment!!

 By the way, your proof is nice!!

[quote="dickchimney"][quote="Myth"]See:
first ordering is 2, 3, 4, ..., 1
second ordering is 1, 2, 3, 4, ...
Then $A_{i_1}=%Error. "varempty" is a bad command.
$.
Is it clear now? ;)[/quote]
 No ;)
  Now let take step 1, what we get?
   \[A = 2 \leq 3 \leq 4 \leq ....\]
 $1$ has been crossed out ( not consider it anymore )
 Then, step 2 indicate that
   $i_1 = 1, i_2=2....$
 If you dont believe, then just follow the three steps I mentioned above.
 If we can't agree, I think we need other to comment!![/quote]
Are you still trying to justify your solution? It is useless. Sorry ;)

Happy New Year!

One issue here that makes it harder than it looks: the well-ordering does not have to be isomorphic to the natural numbers.

Ramsey's theorem is probably the best solution; we also need to argue that the reverse of a well-ordering on an infinite set is not a well-ordering.

[quote]we also need to argue that the reverse of a well-ordering on an infinite set is not a well-ordering[/quote]
What do you mean?
My solution is complete. I proved all fact, which I used.

It's just a paraphrase, really- the big picture of what you proved. I wasn't saying you were wrong.

[quote="jmerry"]One issue here that makes it harder than it looks: the well-ordering does not have to be isomorphic to the natural numbers.

.[/quote]

 But it does contain a subset that is isomorphic to the natural numbers, that's what my proof is about!!: :D. Yes, I agree that the Ramsey's is the best solution :P


modular arithmetic
Putnam
group theory
abstract algebra
blogs
Congruences

[quote="Peter"]Suppose that $p$ is an odd prime. Prove that \[\sum_{j=0}^{p}\binom{p}{j}\binom{p+j}{j}\equiv 2^{p}+1\pmod{p^{2}}.\][/quote]

For any integer $j$ with $1\leq j\leq p-1$, we have

$\binom{p+j}{j}\cdot j!=\frac{\left(p+j\right)\cdot\left(\left(p+j\right)-1\right)\cdot ...\cdot\left(\left(p+j\right)-j+1\right)}{j!}\cdot j!$
$=\left(p+j\right)\cdot\left(\left(p+j\right)-1\right)\cdot ...\cdot\left(\left(p+j\right)-j+1\right)=\left(p+j\right)\cdot\left(p+j-1\right)\cdot ...\cdot\left(p+1\right)$
$\equiv j\cdot\left(j-1\right)\cdot ...\cdot 1=j!\text{ mod }p$,

and since $j!$ is coprime to $p$ (since $j!=1\cdot 2\cdot ...\cdot j$, and each of the numbers $1$, $2$, ..., $j$ is coprime to $p$ because $p$ is prime and $j<p$), we can divide this congruence by $j!$ and obtain $\binom{p+j}{j}\equiv 1\text{ mod }p$, so that $p\mid \binom{p+j}{j}-1$. On the other hand, since $1\leq j\leq p-1$, we have $p\mid\binom{p}{j}$. Thus, $p\cdot p\mid\binom{p}{j}\cdot\left(\binom{p+j}{j}-1\right)$, what rewrites as $p^{2}\mid\binom{p}{j}\binom{p+j}{j}-\binom{p}{j}$. Hence, $\binom{p}{j}\binom{p+j}{j}\equiv\binom{p}{j}\text{ mod }p^{2}$. This has now been proven for $1\leq j\leq p-1$, but it is also true for $j=0$ (because $\binom{p}{0}\binom{p+0}{0}=1\cdot 1=1=\binom{p}{0}$). Thus, $\binom{p}{j}\binom{p+j}{j}\equiv\binom{p}{j}\text{ mod }p^{2}$ holds for every $j$ such that $0\leq j\leq p-1$. Thus,

$\sum_{j=0}^{p}\binom{p}{j}\binom{p+j}{j}=\sum_{j=0}^{p-1}\binom{p}{j}\binom{p+j}{j}+\binom{p}{p}\binom{p+p}{p}\equiv\sum_{j=0}^{p-1}\binom{p}{j}+\binom{p}{p}\binom{p+p}{p}$
$=\left(\sum_{j=0}^{p}\binom{p}{j}-\binom{p}{p}\right)+1\binom{2p}{p}=\left(2^{p}-1\right)+\binom{2p}{p}\text{ mod }p^{2}$.

Now, we will show that $\binom{2p}{p}\equiv 2\text{ mod }p^{2}$. Once this is shown, we can conclude that

$\sum_{j=0}^{p}\binom{p}{j}\binom{p+j}{j}\equiv \left(2^{p}-1\right)+\binom{2p}{p}\equiv\left(2^{p}-1\right)+2=2^{p}+1\text{ mod }p^{2}$,

and the problem is solved. Thus, it remains to show that $\binom{2p}{p}\equiv 2\text{ mod }p^{2}$. One possible way to do this is the following:

For every integer $k$ with $1\leq k\leq p-1$, we have $p\mid\binom{p}{k}$ and thus $p^{2}\mid\binom{p}{k}^{2}$, so that $\binom{p}{k}^{2}\equiv 0\text{ mod }p^{2}$. Now remember the combinatorial identity $\binom{2n}{n}=\sum_{k=0}^{n}\binom{n}{k}^{2}$. Applying it to $n=p$, we get

$\binom{2p}{p}=\sum_{k=0}^{p}\binom{p}{k}^{2}=\binom{p}{0}^{2}+\sum_{k=1}^{p-1}\binom{p}{k}^{2}+\binom{p}{p}^{2}$
$\equiv \binom{p}{0}^{2}+\sum_{k=1}^{p-1}0+\binom{p}{p}^{2}=1^{2}+0+1^{2}=2\text{ mod }p^{2}$.

Proof complete.

[b]PS.[/b] The prime $p$ needs not be odd.

  darij

[quote="Peter"]Suppose that $ p$ is an odd prime. Prove that
\[ \sum_{i = 0}^{p}\binom{p}{i}\binom{p + i}{i}\equiv 2^{p} + 1\pmod{p^{2}}.
\]
[/quote]

I have a different approach leading to other possible generalizations (It is actually generalizing the Lemma from the second proof of Putnam 1991/B4 from the PEN bi-week file). We begin with a preliminary result (which actually does all the work):

[color=darkblue][b]Theorem 1[/b][/color]. Let $ x$, $ y$ be real numbers, and let $ p$, $ q$ be two positive integers. Then the following identity holds
\[ \sum_{i = 0}^{p}{\binom{p}{i}\binom{q + i}{i}x^{p - i}y^{i}} = \sum_{i = 0}^{p}{\binom{p}{i}\binom{q}{i}(x + y)^{p - i}y^{i}.
}\]
[i]Proof[/i]. Let $ m$, $ n$ be two real numbers. Consider the identity:
\[ E: = \left[(x + y)m + y\right]^{p}(1 + m)^{q} = \left(\sum_{i = 0}^{p}{\binom{p}{i}\left(x + y\right)^{p - i}m^{p - i}y^{i}}\right)\left(\sum_{i = 0}^{q}{\binom{q}{i}m^{i}}\right).
\]
The coefficient of $ m^{p}$ from the right hand side of the identity is $ B: = \sum_{i = 0}^{p}{\binom{p}{i}\binom{q}{i}(x + y)^{p - i}y^{i}}$.
On other hand, since
\[ E = \left[mx + y(1 + m)\right]^{p}(1 + m)^{q} = \sum_{i = 0}^{p}{\binom{p}{i}x^{p - i}m^{p - i}y^{i}(1 + m)^{q + i}},
\]
the coefficient of $ m^{p}$ is also equal to $ A: = \sum_{i = 0}^{p}{\binom{p}{i}\binom{q + i}{i}x^{p - i}y^{i}}$, and therefore $ A = B$, which proves Theorem 1.

Returning to our problem, set $ x = y = 1$, and let $ q = p$ be a prime number. In this case,
\[ \sum_{i = 0}^{p}\binom{p}{i}\binom{p + i}{i} = \sum_{i = 0}^{p}{\binom{p}{i}\binom{p}{i}2^{p - i} = 1 + 2^{p} + \sum_{i = 1}^{p - 1}{\binom{p}{i}^{2}2^{p - i} \equiv 2^{p} + 1\pmod{p^{2}}.
}}\]
This completes the proof of our problem.

Nice, but you are free to delete all appearances of the word "nonzero" from your post. $ 0^0$ is defined to be $ 1$, this is not a matter of discussion. You can still mention that $ 0^0$ should be $ 1$, but don't let this impose unnecessary restrictions in your theorems.

  darij

It is known fact, and don't hard to prove (but long).

I want to prove it combinatorially.

I'm a combinatorist, sue me.

The left hand side counts the number of pairs of sets $ (X,Y)$ where $ X$ is a subset of $ \{1,\ldots,p\}$, $ Y$ is a subset of $ \{1,\ldots,2p\}$, $ |X|=|Y|$ and $ Y\subset X\cup\{p+1,\ldots,2p\}$.

Consider the subgroup $ G$ of $ S_{2p}$ generated by $ (1,2,\ldots,p)$ and $ (p+1,\ldots,2p)$. $ G$ acts naturally on the above set of pairs. The count of such pairs is equivalent $ (mod |G|=p^2)$ to the count of such pairs that have a non-trivial stabilizer.

If a pair has a non-trivial stabilizer, then for some $ S$ in $ \{\{1,\ldots,p\},\{p+1,\ldots,2p\}\}$, ($ S\subset X$ or $ S\cap X=\emptyset$) and ($ S\subset Y$ or $ S\cap Y=\emptyset$).

Take each potential $ S$ at a time. For $ S=\{1,\ldots,p\}$, since $ X\subset S$, either $ X=S$ or $ X=\emptyset$. If $ X=\emptyset$, then since $ |X|=|Y|$, $ Y=\emptyset$. If $ X=S$, then $ |Y|=p$. Now since $ Y$ either contains $ S$ or misses $ S$, it follows that $ Y=S$ or $ Y=\{p+1,\ldots,2p\}$.

For $ S=\{p+1,\ldots,2p\}$, we already know that $ X$ misses $ S$. Thus the condition is either that $ Y$ contains $ S$ or $ Y$ misses $ S$. Since $ Y$ is contained in $ S\cup X$, $ Y=X$ or $ Y$ contains $ S$. If $ Y$ contains $ S$ then $ Y=\{p+1,\ldots,2p\}$ and $ X=\{1,\ldots,p\}$.

Thus we have shown that the elements with a non-trivial stabiliser are precisely the pairs $ (X,X)$ for subsets $ X$ of $ \{1,\ldots,p\}$ and $ (\{1,\ldots,p\},\{p+1,\ldots,2p\})$. Thus there are $ 2^p+1$ of them.

Luke
See my puzzle blog at [url]http://bozzball.blogspot.com[/url]

I did it the following way.

Let $ A\equal{}\{a_1$, $ a_2$, $ \dots$, $ a_p\}$ and $ B\equal{}\{b_1$, $ b_2$, $ \dots$, $ b_p\}$.
For any $ 0 \le j \le p$, we choose a set $ A_j$ consisting of $ p\minus{}j$ distinct elements from $ A$ and color them green. Then we choose $ j$ elements from the union $ (A \setminus A_k) \cup B$ and color them red. Hence we've chosen $ p$ elements in total. If we sum up over all $ 0 \le j \le p$, we get the desired sum.

Next, for any $ 0 \le k \le p$, choose $ k$ elements from $ A$ and $ p\minus{}k$ elements from $ B$. Color each of the $ p\minus{}k$ elements red. For each of the $ k$ elements, there are two possibilities, namely it is red or green. Hence there are in total $ 2^k$ possibilities to color the $ k$ elements chosen from $ A$. This gives $ 2^k \binom{p}{k} \binom{p}{p\minus{}k}$ possibilities for every $ k$. If we sum up over all $ 0 \le k \le p$, we get $ \sum_{k\equal{}0}^{p} 2^k \binom{p}{k}^2$ possibilities.

It's easy to see that the above "operations" of choosing and coloring the elements are equivalent. Hence the two sums are equal. The conclusion follows, as $ \binom{p}{j}^2 \equiv 0 \mod p^2$ for every $ 0<j<p$.

(I hope it's not the same as another solution, but, to be honest, I didn't read them...^^)

[quote="dule_00"][quote="Rust"]
Because for odd prime $ \binom{ap}{bp} \equal{} \binom{a}{b}\mod p^3$ [/quote]

How do you prove this?[/quote]
In fact, we don't need Wolstenholme's theorem or its proof here. Just note: \[\binom{2p}p=\sum_{i=0}^p\binom p i^2\equiv2\mod p^2\]
This is because $p|\binom p i$ for $0<i<p$. Moreover the theroem is true if $p>3$
[quote="Rust"]If $ 0<j<p$, then $ p|\binom{p}{j},  \ \ \binom{p\plus{}j}{j}\equal{}1\mod p.$ Therefore
\[ \sum_{j\equal{}0}^p\binom{p}{j}\binom{p\plus{}j}{j}\equal{}2^p\minus{}2\plus{}1(j\equal{}0)\plus{}\binom{2p}{p}(j\equal{}p)\mod p^2.\]
Because for odd prime $ \binom{ap}{bp}\equal{}\binom{a}{b}\mod p^3$, we get $ \sum_j\binom{p}{j}\binom{p\plus{}j}{j}\equal{}2^p\plus{}1\mod p^2.$[/quote]
I didn't get the point why $\binom{p+i}i\equiv1\mod p$ implies
\[ \sum_{j\equal{}0}^p\binom{p}{j}\binom{p\plus{}j}{j}\equal{}2^p\minus{}2\plus{}1(j\equal{}0)\plus{}\binom{2p}{p}(j\equal{}p)\mod p^2.\]
The second modulo is taken over $p^2$ whereas the first modulo was for $p$.

I used the modulo lemma for rational numbers which is : $1/q=x$(mod p ) in which gcd (p,q)=1 and $xq=1$ (mod p )

It is known that \(\binom{2p}p\equiv2\pmod{p^2}\). Now the following claim will suffice:

[color=red][b]Claim:[/b][/color]      For \(i=0,1,\ldots,p-1\),     \[\binom{p+i}i\binom pi\equiv\binom pi\pmod{p^2}.\]

[i]Proof.[/i]      The claim obviously holds for \(i=0\), so assume \(i\ge1\).     Then, \(p\mid\binom pi\) and     \[\binom{p+i}i\equiv\frac{(p+i)\cdots(p+1)}{i\cdots1}\equiv\frac{i\cdots1}{i\cdots1}\equiv1\pmod p.\] \(\blacksquare\)

Finally, \[\sum_{i=0}^p\binom{p+i}i\binom pi\equiv1+\sum_{i=0}^p\binom pi\equiv2^p+1\pmod p.\]


Prove that the sum:

$1^{k}+2^{k}+.........+n^{k}$

Where $n$ is an arbitrary integer and $k$ is odd is divisible by $1+2+..........+n$

:| Hint [hide]I think this is a solution
$1+2+......+n=\frac{(n+1)n}{2}$
So we only Prove that $1^{k}+2^{k}+......+n^{k}$ divisible by n+1,n and (n+1;n)=1(not very hard)[/hide] :)


Solve equation
$ x^2\plus{}yz\equal{}a$
$ y^2\plus{}zx\equal{}b$
$ z^2\plus{}xy\equal{}c$
($ a,b,c$ be the const)

[quote="Algadin"]pco? where are you?[/quote]

You never acknowledge the solutions or explanations we give you.
You post wrong problems and never apologize or even simply correct the problem.
So I'll avoid from now to spend time on your problems.

I hope a lot of other mathlinkers will help you.