geometry
rectangle
trapezoid
geometry unsolved

$ ABCD$ is rectangle. Let $ X \in \overrightarrow{AC}$ and $ X \notin \overline{AC}$ such that $ \angle BXD \equal{} \angle CBX$. If $ CX \equal{} 1$, find $ BX$.

Let $ E \equiv AC \cap BD,$ $ P \equiv BX \cap DC,$ $ Q \equiv DX \cap BC.$ $ XCE$ is median of $ \triangle BXD$ $ \Longrightarrow$ $ PQ \parallel BD.$ Parallel to $ BX$ through $ D$ cuts $ BC$ at $ Y.$ $ \angle BXD \equal{} \angle CBX \equal{} \angle YBX$ $ \Longrightarrow$ $ BXYD$ is cyclic isosceles trapezoid with diagonal intersection $ Q.$ By Ptolemy theorem, $ BX \cdot DY \equal{} DX^2 \minus{} BD^2$ $ \Longrightarrow$

$ \frac {XP}{PB} \equal{} \frac {XQ}{QD} \equal{} \frac {BX}{DY} \equal{} \frac {BX^2}{DX^2 \minus{} BD^2}.$

By van Aubel theorem for $ \triangle BXD,$

$ \frac {XC}{CE} \equal{} \frac {XP}{PB} \plus{} \frac {XQ}{QD} \equal{} \frac {2 BX^2}{DX^2 \minus{} BD^2}.$

$ XCE$ is median of $ \triangle BXD$ $ \Longrightarrow$

$ (XC \plus{} CE)^2 \equal{} XE^2 \equal{} \frac {_1}{^4}(2 BX^2 \plus{} 2 DX^2 \minus{} BD^2).$

Substitute $ CE \equal{} \frac {_1}{^2} BD$  and the van Aubel theorem result $ \Longrightarrow$

$ XC^2 \plus{} XC \cdot BD \equal{} \frac {_1}{^2}(BX^2 \plus{} DX^2 \minus{} BD^2) \equal{} \frac {BX^2}{2} \left(1 \plus{} \frac {BD}{XC}\right),$

$ XC \cdot (XC \plus{} BD) \equal{} \frac {BX^2}{2 XC} \cdot (XC \plus{} BD).$

Reduce by $ XC \plus{} BD \neq 0$ $ \Longrightarrow$ $ BX^2 \equal{} 2 XC^2,$ $ BX \equal{} XC \sqrt {2}.$


What is the least possible number of digits in the positive difference between a positive five-digit integer and a positive four-digit integer?

The smallest five digit integer is 10000 and the largest four digit integer is 9999. Thus the smallest difference between a five digit integer and four digit integer is $ 10000 \minus{} 9999 \equal{} 1$, which has $ \boxed{1}$ digit.


AMC
AIME
trigonometry
inequalities
LaTeX
Asymptote
AIME II

I often need to make arrays with conditions that are sentences interspersed with mathematics. The easiest way for me to do this is to do \ textrm{ ...all my conditions... } but inside use $ \$$'s to isolate the one mathematical snippet. This had never led to a compile error with WinEdt but I think the AoPS forum compiler hates it. Here's the exact code that works perfectly for me at home but was a puzzler to fix on AoPS:

[hide="2008 AIME II #14 solution piece"]\begin{align*}
a_{n+1} & =  2(2^n\cos\theta\sin\alpha + \sin\theta
\sqrt{4^n(1-\sin^2\alpha)} \\
& =  2^{n+1}(\cos\theta\sin\alpha + \sin\theta\cdot|\cos\alpha|)
\\
& =  \left\{\begin{array}{ll} 2^{n+1}(\cos\theta\sin\alpha +
\sin\theta\cdot\cos\alpha) & \textrm{if $ \cos \alpha > 0$} \\
2^{n+1}(\cos\theta\sin\alpha - \sin\theta\cdot\cos\alpha) &
\textrm{if $ \cos \alpha < 0$}
\end{array}\right. \\
& =  \left\{\begin{array}{ll} 2^{n+1}\sin(\alpha+\theta) & \textrm{if $ \cos \alpha > 0$} \\
2^{n+1}\sin(\alpha-\theta) & \textrm{if $ \cos \alpha < 0$}
\end{array}\right.
\end{align*}[/hide]

In order to get it to look fine, I had to take the cosine inequalities out of the textrm [i]and[/i] enclose the entire shebang in \ [ and \ ], which feels redundant. I never have had to use brackets around an align or eqnarray environment before, so I would like to know what it is I'm not seeing correctly here...

When you use align in a document you don't put it inside dollar signs but here you have no choice. To get round that put \par before \begin{align*} (which tells LaTeX you want to be in text mode) and that will work.
As you can see you can't put dollar signs inside dollar signs otherwise AoPS reads them wrongly. So use the alternative \(...\) which do exactly the same job as dollar signs:
$ \par\begin{align*}
a_{n+1} & = 2(2^n\cos\theta\sin\alpha + \sin\theta
\sqrt{4^n(1-\sin^2\alpha)} \\
& = 2^{n+1}(\cos\theta\sin\alpha + \sin\theta\cdot|\cos\alpha|)
\\
& = \left\{\begin{array}{ll} 2^{n+1}(\cos\theta\sin\alpha +
\sin\theta\cdot\cos\alpha) & \textrm{if\ \(\cos\alpha\geq 0\)} \\
2^{n+1}(\cos\theta\sin\alpha - \sin\theta\cdot\cos\alpha) &
\textrm{if\ \(\cos\alpha<0\)}
\end{array}\right. \\
& = \left\{\begin{array}{ll} 2^{n+1}\sin(\alpha+\theta) & \textrm{if\ \(\cos\alpha\geq 0\) } \\
2^{n+1}\sin(\alpha-\theta) & \textrm{if\ \(\cos\alpha<0\) }
\end{array}\right.
\end{align*}$
Note also the space "\ " required after 'if'

Hi,

I would prefer \(...\) instead of $ \$...\$$. Some reasons:
[list][*] with \(...\) you can easily distinguish opening and closing of the math mode, in contrary to $ \$...\$$, mistakes in code could be harder to find with $ \$$,
[*] additional error checks by LaTeX, $ \$...\$$ is plain TeX and is used internally by \(...\),
[*] \(...\) is working inside alltt-environments, $ \$...\$$ causes errors,
[*] \( and \) could be redefined or extended easily,
[*] \( and \) are not robust, possibly causing problems in sectioning for instance, but that could be fixed by loading the fixltx2e package.[/list]
Stefan

--
[url=http://texblog.net]TeXblog.net[/url]

As an aside, I think the cases environment works better in that example.  It's simpler, and the spacing is handled better.
\[ \begin{cases} 2^{n\plus{}1}\sin(\alpha \plus{} \theta) & \text{if } \cos \alpha \ge 0 \\
2^{n\plus{}1} \sin(\alpha \minus{} \theta) & \text{if } \cos\alpha < 0 \end{cases}\]
You need to include amsmath.

I usually avoid the original problem like you did in your original example.  Maybe it's not as elegant, though.
[code]\begin{cases} 2^{n+1}\sin(\alpha + \theta) & \text{if } \cos \alpha \ge 0 \\
2^{n+1} \sin(\alpha - \theta) & \text{if } \cos\alpha < 0 \end{cases}[/code]

By the way, I agree that \( . . . \) is useful, but I think it's kind of unconventional, which makes it harder for other humans to read the code.  It is useful for getting around some bugs in imperfect embeddings of LaTeX, though, or when you need to get around annoying stipulations in a package you must use---I remember once there was a problem with the Asymptote diagrams made on the wiki here, when $ \$$ . . . $ \$$ was automatically changed to <math> . . . </math> before any of the asymptote code was processed.  You can imagine the spectacularly bizarre results with complicated math labels in the diagram, especially with <,> turned into $ \text{<,>}$. :D

Leslie Lamport, the initial developer of LaTeX, recommends \(...\) in his book "LaTeX: A Document Preparation System", perhaps restricting the use of $ \$...\$$ to very short formulas. Of course \(...\) ist not so easy to type, I know, and $ \$...\$$ is used traditionally. Why not, and why not to mention a difference.  :)

Stefan

--
[url=http://texblog.net]TeXblog.net[/url]


calculus
integration
arithmetic sequence
number theory proposed
number theory

[b]1)[/b]Solve the equation:
\[x^4-2y^4=1\]
[b]2)[/b]Solve the equation:
\[x^4-2y^4=-1\]
I think two problems are famous! ;).Can you solve it for me? ;)

Are $x,y$ integers?

If $x^2$ and $y^2\ (x,y\in \mathbb{Z})$ are non zero integers, then the equation $X^2-2Y^2=(-1)^n\ (n=0,1,2,\cdots)$ is called Pell's equation.

[quote="kunny"]Are $x,y$ integers?[/quote]

Yep,$x,y$ are integers.
 [quote="kunny"]then the equation $X^2-2Y^2=(-1)^n\ (n=0,1,2,\cdots)$ is called Pell's equation.[/quote]
I have known that,but in this problem the power of $x$ and $y$ are $4$,and I think it is not easy(at least for me :( )

[quote="pigfly"][b]2)[/b]Solve the equation:
\[x^4-2y^4=-1\][/quote]
Numbers $1$, $(y^2)^2$ and $(x^2)^2$ form arithmetic progression, so it is well known fact, that if these numbers are pairwise distinct and coprime then
\[1=m^2-n^2+2mn\]
\[y^2=m^2+n^2\]
\[x^2=-m^2+n^2+2mn\]
So $y^2+\frac{1+x^2}{2}=(m+n)^2$, but $\frac{x^2+1}{2}$ is an integer number and, thus it is 1 modulo 4. It follows that $y^2$ must be even. On the other hand $y^2=m^2+n^2$. Therefore $m$ and $n$ are even - contradiction (1=even number).

We proved that $1$, $(y^2)^2$ and $(x^2)^2$ are the same numbers.

[quote="pigfly"][b]1)[/b]Solve the equation:
\[x^4-2y^4=1\][/quote]
It is clear $x$ is odd. Since $(x^2-1)(x^2+1)=2y^4$ and $\gcd(\frac{x^2+1}{2},x^2-1)=1$ we conclude both $\frac{x^2+1}{2}$ and $x^2-1$ are fourth powers, i.e. $x^2-1=z^4$ - finita la comedia.

Sorry, I do not quite get your solution for x^4-2y^4=-1. I do not understand why you can exclude easily another possibility: 1=n^2-m^2-2mn.

This problem is solved in a book but it is quite involved.

[quote="bomb"]Similar proble,:
find all integers k such that k^2+(k+1)^2 is a perfect square. There is only one such k...

Bomb[/quote]
In fact, there are four!  :D  :D  :D
$k=-4, -1, 0, 3$

[quote="pigfly"][b]1)[/b]Solve the equation:
\[ x^4-2y^4=1 \]
[b]2)[/b]Solve the equation:
\[ x^4-2y^4=-1 \]
I think two problems are famous! ;).Can you solve it for me? ;)[/quote]
Hey,pigfly!!! :)
Here is my approach:We will use two lemma(i think it's well-known and plz prove it on your own if you don't know):Both two following equations have no positive integeral root:
$1/x^4+y^4=z^2 2/x^4-y^4=z^2$
Return ur problems:$x^4-2y^4=1<\to x^4+(y^2)^4=(y^4+1)^2$ has no any-positive integeral root.(according 1/)
$x^4-2y^4=-1<\to (y^2)^4-x^4=(y^4-1)^2$ .And $y=1$ works->$x=1$.we have unique root $(1,1)$
---------------------------
Where are you from,pigfly??What ur accout in dd?? :D


A collection $S$ of integers is defined by the following three runes: (I) 2 is in $S$; (II) for every $x$ in $S$, $3x$ and $x+7$ are also in $S$; (III) no integers except those define by runes (I) and (II) are in $S$. Wat is the smallest integer greater than 2004 which is NOT in $S$?

Is it [hide]2009[/hide]?   I don't want to post a solution that is wrong.

i have no clue if the answer is right but that's what i got  :lol:
I need sommore posts to confirm this

oh, and can u plz explain how you did it?

Imagine trying to get a number by adding 7 or multiplying it by 3 to 2 over and over again.

If we can change 2 such that the remainder when divided by 7 is equal to that of the number we want to get, as long as we are still below the target number, we can just add a bunch of 7s to get the target number.

We can see that 2*3^6=1458<2004.  And by fermats theorem or by just plugging them in, we can see we can get 1,2,3,4,5, and 6 (mod 7) from 2*3^n where n is one of the first 6 positive integers.  Or basically, we can get the remainder to whatever we want but 0 without going over 2004.

That means we can obtain all numbers that are not divisible by 7 above 2004.  Since 2009 is divisible by 7, 2009 should be the answer.

Yes, that's right! I remember this problem was posted a while ago.


Let $a,b,c$ be positive numbers such that $abc\ge1.$
Prove that $\frac{a+1}{a^{2}+a+1}+\frac{b+1}{b^{2}+b+1}+\frac{c+1}{c^{2}+c+1}\le2.$

[i]Comment:[/i] It is a generalization of [url=http://www.mathlinks.ro/Forum/viewtopic.php?p=837061#837061]inequality from Kyiv festival[/url]

Pretty straightforward by expanding... wondering if anybody's got anything different.


Hi folks, I haven't been able to access AOPS forum for the past few weeks (as I was busy). I am back, hi all!

I have a rather interesting query, though, it might sound silly/fatuous,it is an unresolved query (for me); I had perused through the Internet for probable answers but those answers weren't satisfactory.

Query 1

[b] What is the difference between a generalization and an over-simplification? Are they similar in any manner? [/b]

If anyone answers this query, I would want them to cite the relevant/ appropriate instances/examples to corroborate their answer.

I think maybe a generalization might have a positive connotation, while , an over-simplification might have only a negative connotation.

For example,

A: Some inhabitants of country 'X' are foolish.
B: Mr Y is an inhabitant of country X.

Conclusion: Mr Y is foolish.

The above is an instance of a generalization, am I correct?

Do provide an instance for a  generalization and an over-simplification, and point out the differences between them.

Thanks!

"The above" is an instance of [i]incorrect logical derivation[/i], period. I do not know anything about "over-simplification" (this is the first time I hear the term) but I know that the last thing one needs for teaching/learning the elementary logic is a detailed pseudo-scientific classification of common logical fallacies with fine borderlines between them. Where does all this fancy terminology come from?

I think this is a very bizarre question.

"generalization" and "over-simplification" do not describe disjoint sets. In fact, words like "generalization" and "over-simplification" don't describe sets at all. You can't ask whether a conclusion is one or the other and expect to get the same answer from different people.

Anyway, a generalization is when you only know a fact is true in a certain domain but you assume that it is true in a larger domain. For example, I believe all old people are slow, because my grandparents are slow.

An oversimplification is when you make an argument that ignores the complexity of the situation. For example, the Roman Empire fell because Ceasar was assassinated.

Basically, the only similiarity between an over-simplification and a generalization is that they are both forms of bad reasoning.

Also, wikipedia is your friend for learning common knowledge things like these:

http://en.wikipedia.org/wiki/Generalization

http://en.wikipedia.org/wiki/Fallacy_of_the_single_cause

[quote="FibonacciFan"]For example, the Roman Empire fell because Ceasar was assassinated.[/quote]  This is something quite different than an over-simplification ;)

[quote="Gen8"]A: Some inhabitants of country 'X' are foolish.
B: Mr Y is an inhabitant of country X.

Conclusion: Mr Y is foolish.

The above is an instance of a generalization, am I correct?[/quote]
I would not call that a generalization or an over-simplification; I would call it a faulty assumption with no logical basis (to put it more nicely than fedja did).

If you wanted to turn your example into a generalization, we could start with:
A: Mr. Y is foolish.
B: Mr. Y is an inhabitant of country X.
Conclusion (generalization): All inhabitants of country X are foolish.

Could my conclusion be true?  Maybe-but I have no way of knowing without figuring out who is and is not foolish in country X.  An over-simplification would be something like: the US economy is screwed because housing prices dropped.  Did the fall in housing prices contribute to the situation?  Of course.  But there's a lot more behind the collapse-housing bubbles, predatory lenders, adjustable and high-interest rate mortgages, lack of federal oversight, collapse in the credit market.  And even THAT might be an over-simplification!!  Why?  Because I'm drawing a conclusion while considering only one (or a few) pieces of evidence.

Okay, I wholly appreciate [b] FibonacciFan , Fedja, and JRav's [/b] replies (in particular JRav's examples).


For any $ a_k$, $ \frac{a_k}{a_n} (\minus{}1)^{n\plus{}k}$ represents the sum of the product of the roots, taken $ (n\minus{}k)$ at a time.

Can you give me an example please?

This is not, strictly speaking, the Remainder theorem (although it is a direct consequence).  The Remainder theorem states that the remainder when a polynomial $ P(x)$ is divided by $ x \minus{} a$ is $ P(a)$ (in particular, if $ a$ is a root of $ P(x)$, then $ x \minus{} a | P(x)$; this is the [i]Factor[/i] theorem).

The result you state is known as [i]Vieta's theorem[/i], although you will more common see the sums involved as [i]Vieta's sums[/i] or [i]Vieta's formulas.[/i]

[b]Case:[/b]  $ n \equal{} 2$.  An arbitrary monic quadratic looks like

$ (x \minus{} a)(x \minus{} b) \equal{} x^2 \minus{} (a \plus{} b)x \plus{} ab$

Here the second coefficient is $ \minus{} 1$ times the sum of the roots taken $ 1$ at a time, and the third coefficient is the sum of the roots taken $ 2$ at a time.

[b]Case:[/b]  $ n \equal{} 3$.  An arbitrary monic cubic looks like

$ (x \minus{} a)(x \minus{} b)(x \minus{} c) \equal{} x^3 \minus{} (a \plus{} b \plus{} c) x^2 \plus{} (ab \plus{} bc \plus{} ca) x \minus{} abc$

Here the second coefficient is $ \minus{} 1$ times the sum of the roots taken $ 1$ at a time, the third is the sum of the roots taken $ 2$ at a time, and the fourth is $ \minus{} 1$ times the sum of the roots taken $ 3$ at a time.

[b]Case:[/b]  $ n \equal{} 4$.  An arbitrary monic quartic looks like

$ (x \minus{} a)(x \minus{} b)(x \minus{} c)(x \minus{} d) \equal{} x^4 \minus{} (a \plus{} b \plus{} c \plus{} d) x^3 \plus{} (ab \plus{} ac \plus{} ad \plus{} bc \plus{} bd \plus{} cd \plus{} da) x^2 \minus{} (abc \minus{} bcd \minus{} cda \minus{} dab) x \plus{} abcd$

Here the second coefficient is $ \minus{} 1$ times the sum of the roots taken $ 1$ at a time, the third $ 2$ at a time, the fourth $ 3$ at a time, and the fifth $ 4$ at a time.

Hopefully after $ n \equal{} 4$ the general pattern should be clearer, as should the source of the $ ( \minus{} 1)^{n \plus{} k}$ term.  :)


[img]http://img217.imageshack.us/img217/3726/bisecwy7.png[/img]

En un $\Delta ABC$ escaleno, se ubica un punto $D$ sobre el lado $\overline{AC}$ tal que $\overline{BD}$ es bisectriz del $\measuredangle \ B$. Sean $E$ y $F$ las proyecciones ortogonales de $A$ y $C$ sobre la bisectriz $\overline{BD}$. Siendo $M$ un punto del lado $\overline{BC}$ tal que $\overline{DM}\perp \overline{BC}$. Demostrar que el $\measuredangle \ EMD = \measuredangle \ DMF$

Saludos.

Bueno, ps aki mi solucion, a ver si no me ekivoke en algun lado:

Es facil ver que MDFC es ciclico (angulos opuestos suman 180), entonces DMF=DCF=DAE (la ultima igualdad debido a que AE y CF son paralelas, lo cual es claro). Aora prolonguemos AE asta que corte a BC en un punto R. Es claro que AE=ER, por congruencia.Ahora vemos tambien que REDM es ciclico (angulos opuestos suman 180) entonces DME=DRE=DAE (la ultima igualdad se da pues por otra congruencia tenemos que AD=DR). Ya de aqui concluimos que  DMF=DAE=DME lo cual queriamos demostrar.


Columbia geometry Duke college ARML MATHCOUNTS calculus

Hi, I am moving to South Carolina next year, and I was wondering what kind of math contests are available for high school students here.

Also, I am moving to the Columbia area, so which high schools are best? Especially for math/science.

Thanks!

dude I am from NC but I know some competitions in SC

there's like

Furman

and College of Charleston

both are on-site meets

and then there's Duke Math Meet in NC which is a pretty big regional thing

So, I just updated the sticky we had going which listed all the competitions in SC and surrounding areas: http://www.artofproblemsolving.com/Forum/viewtopic.php?t=215459

The big ones in SC tend to be USC Columbia, C of C math meet, and Furman.  The C of C math meet has often attracted a vast range of schools from surrounding states: NC, GA, I think IL once...  Furman gets quite a few GA teams.  USC usually has only SC teams and pretty much all of the best in SC come so it gives you a decent idea of who the top math competitors are in the state.

Since you're interested in math, you should know of Mr. Rybarczyk (Mr. R for short) who's the head coach for the SC All State Team and Mr. Neal who's an assistant coach.  They both teach at schools in the Columbia area: Mr R teaches at AC Flora and Mr. Neal teaches at Hammond.  The two schools are very different though.  Flora's public while Hammond is private.  Anyway, they'd be the best to help you figure out what steps you should take from here.

A list of South Carolina math contests can be found here: http://www.artofproblemsolving.com/Resources/AoPS_R_Contests.php#sc

The list is a bit out of date, however, as the Winthrop University contest is no longer being held, and I'm not sure about the USC Aiken contest. There are also math contest at Wando High School and the Citadel (both near Charleston). In my opinion, the most prestigious of the contests in SC are the [url=http://www.math.sc.edu/contest/]University of South Carolina Contest[/url], the [url=http://math.furman.edu/tournament/tournament.html]Furman Math Tournament[/url], and the [url=http://math.cofc.edu/MATHMEET/]College of Charleston Math Meet[/url].

There are several schools in Columbia that regularly participate in math contests including the school where I teach, [url=http://www.hammondschool.org]Hammond School[/url] (a K-12 independent school with a high school student body of about 250 students), AC Flora High School (an IB school), Spring Valley High School (has a special science/math program), Dreher High School, and Irmo High School (an IB school). There is also the [url=http://www.scgssm.org/]South Carolina Governor's School for Science and Math[/url] (a publicly funded two year residential school for Juniors and Seniors that specializes in math and science).

We also have a SC ARML team (of which Patrick Rybarczyk from AC Flora and myself are two of the coaches). This year it also looks likely that we will start a South Carolina Math Circle based in Columbia.

What grade will you be in next year?

Thanks for the help!

I'll be in 9th grade this coming school year, but I will most likely be starting my 10th grade year when I move.

I was in the same situation you were at the end of my eighth grade year.  I had a house zoned for Spring Valley, and a house zoned for Dreher.  I could also get a programmatic transfer to AC Flora, because they offered the IB program, which Dreher did not.  Hammond offered me a lot of financial aid.  It was a really tough choice.

Hammond is a school that had a solid academic reputation.  Some kids really like the private school atmosphere.  However, when I visited, I found a majority of the kids to be stuck up, and I didn't really fit in very well.  But they do have an excellent math teacher and coach in Mr. Neal (a coach of the SC ARML team), and the school is nicer than most public schools.  Of course, the cost is another factor.

Spring Valley is a really good school, academically.  The quality of education is supposed to be pretty good.  If you are Asian, then Spring Valley has a larger Asian population than a lot of other schools.  SV also has a much larger population in general than most other schools, which I actually liked.  However, I felt that when I was around Spring Valley kids, I was immediately classified as a smart Asian kid, and I didn't like that.  Also, last I heard, they don't have a math coach who is as dedicated as Mr R or Mr Neal.  That would be a big factor in my opinion.

Dreher is another good school.  As far as I know, they don't have a great math coach, but they do have a great band program.  The only really bad thing I have to say about Dreher is that the environment seems to discourage girls.  I know a lot of math team girls from middle school who went to Dreher and just kinda fell off the math scene.

AC Flora is an IB program school, which is the reason I chose it.  One nice thing about Flora is that in addition to a Higher Level Math IB class, they have recently started offering a IB Further Math class, which I would say is the hardest math class offered in any public school.  Mr R teaches all the advanced math classes, and he is a great math teacher, as well as a coach of the SC ARML team.  The one thing I could see someone disliking about Flora is the lack of diversity.  I'm one of the only Asian kids, and I actually enjoy that, but some people feel differently.  I found a ton of friends at Flora, and people were pretty friendly to me.  Also, Hardie and Elliot would be in your grade here, and they are both extremely intelligent kids who made national MathCounts in eight grade.

Anyways, any of those schools would be a good choice.  I would tell you to choose Flora, because you would have an excellent coach, an excellent peer group, and advanced math classes that go beyond any classes offered by any other high school in Columbia.  Of course, I go to Flora so I'm a little biased, but I think it was the right choice for me.

I will add a couple of things about my school:

Dreher's main draw for me was the band program.  This year we are getting a new band director, so the program could go anywhere.

For the past decade?, Dreher's coaches have been Mrs. Williams and Mrs. Murphy.  Both are excellent teachers, and have been so for quite some time.  Their main concentration seems to be a competition called academic decathlon, which seems to go deep in many subject areas, math being one of them.  Dr. Barrineau, also excellent and (in)famous throughout the state, has also make a showing on our math team scene.

Recently, our math team has been more of a student run organization rather then set up as a varsity team.

Dreher has a very strong and proven Advanced Placement program.  This is a collection of classes for which you can get college credit.  People take as many or as few as they wish.  The highest math is Calculus BC, but several of us are signed up for USC courses, as the University is close by.

I can hardly speak for Hammond or Spring Valley.  I do know Flora is an excellent school, with an excellent and active coach.

Right now, our (Flora and Dreher) district is in a construction phase:  Dreher has just moved into a new building and Flora is in the process.


1. Let [tex]A=(a_{ij})_{n\times n}[/tex] be a matrix over [tex]\mathbb{R}[/tex] such that for each [tex]i=1,2,\ldots,n[/tex],

[tex]\displaystyle\sum_{j\not=i} |a_{ij}| < |a_{ii}|[/tex].

Show that [tex]A[/tex] is invertible.

2. Let [tex]A=(a_{ij})_{n\times n}[/tex] be a matrix over [tex]\mathbb{R}[/tex] such that

[tex]\displaystyle\sum_{j\not=i} a_{ij}^2< \min_{1\le i\le n}a_{ii}^2[/tex].

Show that [tex]A[/tex] is invertible.

1/

[hide]

A is invertible iff Ax = 0 => x = 0

Let's suppose Ax=0 with x = (x1, ..,xn) != 0. So xi = max |xj|(j=1..n) > 0.

aii *xi = -  :Sigma: aij*xj (j != i) implies |aii| |xi| <= |xi| *  :Sigma: |aij| (j != i)

which is impossible.[/hide]

2/

[hide]Cauchy -Schwarz ?[/hide]


We are given three nuggets of weights $ 1$ kg, $ 2$ kg and $ 3$ kg, containing different percentages of gold, and need to cut each nugget into two parts so that the obtained parts can be alloyed into two ingots of weights $ 1$ kg ande $ 5$ kg containing the same proportion of gold. How we can do that?

Is there any info on how the gold is distributed within each of the nuggets? Otherwise seems impossible.


In triangle $ ABC$, $ AB\equal{}AC$, $ \angle A\equal{}40^\circ$.  Point $ O$ is within the triangle with $ \angle OBC \cong \angle OCA$.  The number of degrees in angle $ BOC$ is:

$ \textbf{(A)}\ 110 \qquad
\textbf{(B)}\ 35 \qquad
\textbf{(C)}\ 140 \qquad
\textbf{(D)}\ 55 \qquad
\textbf{(E)}\ 70$

[hide="Click for solution"]
$ \angle BOC\equal{}180\minus{}\frac{1}{2}(\angle B\plus{}\angle C)$.  But $ \frac{1}{2}(\angle B\plus{}\angle C)\equal{}\frac{1}{2} \cdot 140 \equal{}70 \implies \angle BOC\equal{}110 ^ \circ$ or $ \boxed{\textbf{(A)}}$.
[/hide]


quadratics
induction
binomial coefficients
algebra
Miscellaneous Problems

If $x$ is a real number such that $x^2 -x$ is an integer, and for some $n \ge 3$, $x^n -x$ is also an integer, prove that $x$ is an integer.

Let $ x^{2}\minus{}x \equal{} m\in\mathbb{Z}$. Then $ x \equal{}\frac{1\pm\sqrt D}{2}$, where $ D \equal{} 4m\plus{}1 > 0$. If $ \sqrt{D}$ isn't irrational, clearly results $ x\in\mathbb{Z}$. Assume the contrary. Take firstly $ x \equal{}\frac{1\plus{}\sqrt D}{2}$. Then $ x^{n}\minus{}x \equal{}\left(\frac{1\plus{}\sqrt D}{2}\right)^{n}\minus{}\frac{1\plus{}\sqrt D}{2}\equal{}\frac{1}{2^{n}}\left[(1\plus{}\sqrt D)^{n}\minus{}2^{n\minus{}1}(1\plus{}\sqrt D)\right]$ is an integer. This implies the weaker assertion that $ (1\plus{}\sqrt D)^{n}\minus{}2^{n\minus{}1}\sqrt D$ is an integer. Because $ (\sqrt D)^{2}\in\mathbb{Z}$, we must consider only the odd exponents in the expansion of $ (1\plus{}\sqrt D)^{n}$. So, we have that $ \sqrt D\left[\minus{}2^{n\minus{}1}\plus{}\sum_{k \equal{} 0}^{\left[\frac{n\minus{}1}{2}\right]}D^{k}\binom{n}{2k\plus{}1}\right]$ is an integer. It results that $ E \equal{}\minus{}2^{n\minus{}1}\plus{}\sum_{k \equal{} 0}^{\left[\frac{n\minus{}1}{2}\right]}D^{k}\binom{n}{2k\plus{}1}$ is $ 0$. However, we have $ D\ge4\cdot1\plus{}1 \equal{} 5$, so $ E >\sum_{k \equal{} 0}^{\left[\frac{n\minus{}1}{2}\right]}\binom{n}{2k\plus{}1}\minus{}2^{n\minus{}1}\equal{} 0$. Contradiction.
The case $ x \equal{}\frac{1\minus{}\sqrt D}{2}$ is treated completely analogously. Because when taking odd exponents, all the binomial coefficients will have a $ \minus{}$ in front of them, and the 'separate' $ \sqrt D$ we'll have the coefficient $ 2^{n\minus{}1}$, not $ \minus{}2^{n\minus{}1}$ we'll obtain a similar contradiction getting this time $ E < 0$.

Just as a commentary, I think this problem belongs more to the $ F$ section - Rational and irrational numbers.

Let $ r_1 > r_2$ be the solutions to the quadratic equation $ y^2\minus{}y\equal{}\lambda$, where: $ \lambda\equal{}x^2\minus{}x$ (the minimum of $ y^2\minus{}y$ is -0.25, so $ \lambda$ is non-negative).

Induction shows that $ x^n\equal{}a_{n}x\plus{}b_{n}$ for all $ n \in N$, where: $ a_{n\plus{}2}\equal{}a_{n\plus{}1}\plus{}\lambda a_{n}$, $ b_{n\plus{}2}\equal{}b_{n\plus{}1}\plus{}\lambda b_{n}, a_{0}\equal{}0, a_{1}\equal{}1, b_{0}\equal{}1, b_{1}\equal{}0$ (an important thing is that they also satisfy $ a_{n\plus{}1}\equal{}b_{n}\plus{}a_{n}, b_{n\plus{}1}\equal{}\lambda a_{n}$)

Notice that $ a_{n}, b_{n}$ are integer sequences. So, if $ x^n\minus{}x$ is an integer, it implies that either x is a rational number (because $ (a_{n}\minus{}1)x\plus{}b_{n}, a_{n}, b_{n} \in Z$), or $ a_{n}\equal{}1$.

First case: x is rational. $ x^2\minus{}x\minus{}\lambda\equal{}0 \implies \frac{1\pm\sqrt{1\plus{}4\lambda}}{2} \in Q \implies 1\plus{}4\lambda$ is a square, or: x is an integer (because this square is a odd square and its root is also odd).
Second case: $ a_{n}\equal{}1$. From the recursion $ a_{n\plus{}1}\equal{}b_{n}\plus{}a_{n}, b_{n\plus{}1}\equal{}\lambda a_{n}$, we have that $ a_{n}, b_{n}$ are positive integers for n>2, and that $ a_{n\plus{}1}\equal{}b_{n}\plus{}a_{n}>a_{n} \implies a_{n} \ge a_{3}\equal{}1\plus{}\lambda$ for $ n \ge 3$. If $ \lambda\equal{}0$, we have $ x^2\minus{}x\equal{}0$, or: $ x\equal{}0,1 \in Z$. Else, $ a_{n}>1$ and we get a contradiction.


floor function
equation
number theory
algebra
IMO Shortlist

Find all positive integers $ a$ and $ b$ for which

\[ \left \lfloor \frac{a^2}{b} \right \rfloor \plus{} \left \lfloor \frac{b^2}{a} \right \rfloor \equal{} \left \lfloor \frac{a^2 \plus{} b^2}{ab} \right \rfloor \plus{} ab.\]

[quote="orl"]Find all positive integers $ a$ and $ b$ for which
\[ \left \lfloor \frac {a^2}{b} \right \rfloor \plus{} \left \lfloor \frac {b^2}{a} \right \rfloor \equal{} \left \lfloor \frac {a^2 \plus{} b^2}{ab} \right \rfloor \plus{} ab.
\]
[/quote]
I only remember the result $ (n,n^2\plus{}1)$ and $ (n^2\plus{}1,n)$

[quote=""ISL questions and solutions from 1995-2001" by A.Ajorloo"]
we must have $ a\neq b$,so WLOG assume that $ a > b$ and let:

$ \lfloor\frac {a^2}b\rfloor = \alpha,\lfloor\frac {b^2}a\rfloor = \beta$.

so we must have:

$ \begin{eqnarray*}\alpha + \beta & = & \lfloor\frac {a^2 + b^2}{ab}\rfloor + ab \\
& = & \lfloor\frac {a^2 + b^2}{ab}\rfloor + \frac {a^2}b\cdot\frac {b^2}a \\
& \geq & 2 + \alpha\beta\Rightarrow a\lpha + \beta\geq 2 + \alpha\beta \\
& \Rightarrow & (\alpha - 1)(\beta - 1)\leq - 1$

but we have $ \alpha\geq 1$ so $ \beta = 0$ which means that $ a > b^2$.so assume that $ a = b^2 + c$ in which $ c$ is a natural number,so if we plug in $ b^2 + c$ instead of $ a$ in the given equation,we get that:

$ b^3 + 2bc + \lfloor\frac {c^2}b\rfloor = \lfloor\frac {b^4 + 2b^2c + c^2 + b^2}{b^3 + bc}\rfloor + b^3 + bc$

$ \Rightarrow (c - 1)b + \lfloor\frac {c^2}b\rfloor = \lfloor\frac {b^2(c + 1) + c^2}{b^3 + bc}\rfloor$ (1)

now the last equation obviously holds for $ c = 1$ so $ (a,b) = (n^2 + 1,n)$ is a solution,now let $ c\geq 2$,from (1) we have:

$ (c - 1)b\leq\frac {b^2(c + 1) + c^2}{b^3 + bc}$

which is equivalent to:

${ c^2(b^2 - 1) + b^2\{c(b^2 - 2) - (b^2 + 1)}\leq 0$ (2)

$ \Rightarrow c(b^2 - 2) - (b^2 + 1)\leq 0$

$ \Rightarrow 2(b^2 - 2) - (b^2 + 1)\leq 0$

$ \Rightarrow b = 1\textrm{ or }2$

for $ b = 1$ we get $ a = 2$,also for $ b = 2$,using (2) we get that:

$ 3c^2 + 4(2c - 5)\leq 0$

so we must have $ c < 2$,contradiction.

so the only solutions are $ (a,b) = (n,n^2 + 1)$ and $ (a,b) = (n^2 + 1,n)$ in which $ n$ runs over the naturals.[/quote]

We claim that all ordered pairs of integers $(a, b)$ are of the form $(k, k^2+1)$ or $(k^2+1, k)$ for $k\in\mathbb{Z}^{+}$.

Let $a=b^2+1$. If $b>1$, then we have \[\text{LHS}=\left[b^3+2b+\frac{1}{b}\right]+\left[\frac{b^2}{b^2+1}\right]=b^3+2b,\] and \[\text{RHS}=\left[b+\frac{1}{b}+\frac{b}{b^2+1}\right]+b^3+b=b^3+2b,\] so we have a solution. It is easy to confirm that $b=1$ also yields a solution. There is an obvious symmetry between $a$ and $b$, so $b=a^2+1$ is also a solution.

Now we must show there are no other solutions. WLOG, asume $b\ge a$.

Let $a$ be fixed and let $f(b)=\frac{a^2}{b}+\frac{b^2}{a}-\left(\frac{a}{b}+\frac{b}{a}\right)-ab$ and $g(b)=\frac{a^2}{b}+\frac{b^2}{a}-\frac{a}{b}-\frac{b}{a}-ab$. From this we have $|g(a)-f(a)|<3$.

Observe that we have \[g(a)=\frac{1}{a}\left(b-\frac{a^2+1}{2}\right)^2=\frac{1}{4m}\left(\frac{a^2+1}{2}\right)^2=\frac{a^2-a}{b}.\] So if $b\ge a^2+2$, then \[g(b)\ge a+\frac{2}{a}+\frac{a^2-a}{a^2+2}>a.\] Hence $f(b)>a-3$. So for $m>2$ there are no solutions for $b>a^2+1$.

Also if $a\le b\le a^2-1$, then $\left(b-\frac{a^2+1}{2}\right)^2\le\frac{(a^2-3)^2}{4}$ and $\frac{a^2-a}{b}\le a-1$, so $g(b)\le -a+\frac{2}{a}-1<0$. Hence $f(b)<0$ for $b>2$. So for $b>2$ there are also no solutions for $b<a^2$. It is also easy to check that $f(a^2)=-(a-1)<0$.

Now, it remains to check $a=1$ and $a=2$. For $a=1$, we have $f(1)=-1$. If $b>1$ then we have $f(b)=0+b^2-2b=b(b-2)$. So for $a=1$ the only solution is $b=2$.

Finally take $a=2$, and consider $b\ge 2$. It is easy to check that $f(2)=-2$, $f(3)=-3$, and $f(4)=-1$. For $b\ge 6$ we have $f(b)=0+\frac{b^2}{2}-\frac{b}{2}-2b\ge\frac{b^2}{2}-\frac{1}{2}-\frac{5b}{2}>0$.

Hence, $(a, b)= (k, k^2+1)$ or $(k^2+1, k)$ for $k\in\mathbb{Z}^{+}$. $\Box$


logarithms
induction
graph theory
combinatorics proposed
combinatorics

A transitive tournament is an orientation of complete graph for which the vertices can be numbered in such a way that (i,j) is an edge iff i<j.
a) show that if $k<\log_2 n$a directed $K_n$always has atransitive subtournament on k vertices.

So ... where is question b) :) . a) is quite nice, but almost trivial.
I prove by induction on $k$ that among the vertices of any complete directed graph $G\left(V,E\right)$, $\left|V\right|=2^{k}$, I can find a $k+1$ transitive tournament. For $k=1$ this is trivial. To make the step from $k-1$ to $k$ you just have to notice that there is a vertice $v \in V$ s.t. $d_{+}\left(v\right) \geq 2^{k-1}$ and apply the induction hypothesis for some $2^{k-1}$ of these points.


Suppose that we have an 8-sided die with 4 red faces, 3 yellow faces, and a blue face.  What is the probability of rolling a yellow face?


I got some money saved up but Im not using for anything.. Should I buy a couple of stocks? Should I observe certain stocks? How much should I invest?

Watching stocks is always something fun to do. I'd probably pick one company and just buy one stock of it as a start.

[url=http://en.wikipedia.org/wiki/Index_fund]you may want to read up on index funds[/url].

Im guessing there's a lot more to it than what I thought.


When Joyce counts the pennies in her bank by fives, she has one left over.  When she counts them by threes, there are two left over.  What is the least possible number of pennies in the bank?

[hide]answer:11 the problem can be solved both algebraicly, and through guess and test, im too lazy to show either :lol: [/hide]

Mcrawford please allow me to post a continuation of ur problem.

  Joyce can have any number of pennies in her bank from 1-1000, but the amount of coins she has must still satisfy the conditions of the original problem posted.  How many different combinations of pennies can she have?  Canu genralize a formula for the number of different combinations of pennies she can have, from 1.........n?

[hide="original problem answer"]
$\frac{11}{5}=2r1\\
\frac{11}{3}=3r2$

The "r" is for remainder.[/hide]

[hide]p=15x-4

where x is a positive integer.[/hide]

orginal problemo

[hide]If there is a remainder of one when the amount of pennies is divided by 5, the number ends in 1 or 6. Since the remainder is two when divided by three, the digits of the number add up to 2 more than a multiple of 3.

[b]11 pennies. There's your answre.[/b][/hide]

Guess and check is the best way
[hide]The possible amounts counting by 5 with reminader 1 are 6, 11, 16...
11 works. 11 is the answer.[/hide]


Consider two-sided infinite sequence of real numbers. Given  a sequence  $\{a_{n}\}$ we obtain a new sequence by formula
$b_{n}=2a_{n}-a_{n-1}.$ All sequences derived from initial sequence by this way, are increasing. Is it true that initial sequence is
an arifmetic progression?

suppose $a$ is a polynomial of degree $k$

It's easy to proof that for all $k >1$,  $b$ is increasing for some initial conditions.

So, $a$ can be or cannot be an arithmetic progression.

I don't undersstand exactly what do you mean, but may be something isn't clear
in the setting of the problem. Sequence is infinite by two sides (therefore, for example we can't get an even k)
and process of producing new sequences is infinite.


Let $ n\geq 3 $ be an integer and let $ x_1,x_2,\ldots,x_{n-1} $ be nonnegative integers such that

\begin{eqnarray*} \ x_1 + x_2 + \cdots + x_{n-1} &=& n \\ x_1 + 2x_2 + \cdots + (n-1)x_{n-1} &=& 2n-2. \end{eqnarray*}

Find the minimal value of $ F(x_1,x_2,\ldots,x_n) = \sum_{k=1}^{n-1} k(2n-k)x_k $.

We observe that $F \equiv n(2n-1) + n(n-2)+L(x_{2},x_{3} \cdots x_{n-2})$ where the form is obtained by utilizing constraint 1 and then the constraint obtained by subtracting 2 by 1.
Where $L$ is linear in each variable and has just pluses in it.So $L \geq 0$
Also we observe that $x=(n-1,0,0,\cdots 0,1)$ is a solution of the linear equations.This will imply $L(x)=0$
Thus $F$ is minimum at $(n-1,0,0 \cdots 0,1)$ the value being $3n(n-1)$

See that $F(x_1,x_2,...,x_{n-1})=2n\displaystyle\sum_{k=1}^{n-1}kx_k-\displaystyle\sum_{k=1}^{n-1}k^2x_k=4n(n-1)-\displaystyle\sum_{k=1}^{n-1}k^2x_k$, so we should find $\max \displaystyle\sum_{k=1}^{n-1}k^2x_k$.
After checking small cases we guess that our maximum is achieved when $(x_1,x_2,...,x_{n-1})=(n-1,0,...,1).$
Indeed, we can easily prove now that $\displaystyle\sum_{k=1}^{n-1}k^2x_k=\displaystyle\sum_{k=1}^{n-1}x_k +\displaystyle\sum_{k=2}^{n-1}(k-1)(k+1)x_k\le n+n\displaystyle\sum_{k=2}^{n-1} (k-1)x_k=n(n-1)$.


group theory
abstract algebra
function
superior algebra
superior algebra unsolved

Let $ K$ be a subgroup of $ G$ and $ N$ a normal subgroup of $ G$.  Define the function $ \phi : K\rightarrow KN/N$ by $ \phi : k\mapsto kN$.  How do I show that $ \phi$ is a bijection?  I started by letting $ kN\equal{}k'N$ for some $ k,k'\in K$ but I'm a bit lost trying to show that $ k\equal{}k'$.  Thanks :)

Hi, I don't think $ \phi$ is a bijection. Its kernel should be $ K \cap N$. This is the second isomorphism theorem.

Oh yeah that's right, thanks.  I forgot that $ \phi$ only needs to be a homomorphism for the First Isomorphism Theorem to hold.


function
number theory
number theory unsolved

Let's share a hard problem.
Let p be an odd prime,and let [img]http://www.artofproblemsolving.com/Forum/latexrender/pictures/d08c67ad3f52a0174046bdbf525b2ee2.gif[/img] denote the set of permutations of the set {1,2,...,p-2}.For any permutation [img]http://www.artofproblemsolving.com/Forum/latexrender/pictures/079d6019b766ef46daa135719f467853.gif[/img]  in [img]http://www.artofproblemsolving.com/Forum/latexrender/pictures/d08c67ad3f52a0174046bdbf525b2ee2.gif[/img],let [img]http://www.artofproblemsolving.com/Forum/latexrender/pictures/3b57a89e7d99387edc2c1ed19b04d455.gif[/img] denote the number of cycles in [img]http://www.artofproblemsolving.com/Forum/latexrender/pictures/079d6019b766ef46daa135719f467853.gif[/img].Prove that

[img]http://www.artofproblemsolving.com/Forum/latexrender/pictures/b326889fab7b8e846f0ef4640994d34f.gif[/img]

Excuse the idiot question, but do you also consider fixed points as cycles when counting them?

you consider fixed points as Cycles of length $1$ I think, at least it is the standard convention!  Anyway I think the problem is not hard! Just use the generating function $F(x)=x(x+1)(x+2)...(x+n-1)$ where the coefficient of $x^t$ is the number of permutations of the set $[n]$ with $t$ cycles.

My English is so bad that I can't follow your words. : :blush:
For example,let pi={1,3,2,5,4},then we can rewrite pi as (1,2,3)(4,5),because (1,2,3) and (4,5) are both cyclic,so f(pi)=2.It is hard for me to translate it into English. :blush:

There is also straightforward solution using some monstruous identities. I will try to write what I found:
   Since here are $\frac{n!}{c_1!...c_n! 1^{c_1}... n^{c_n}}$ permutations of $1,2,...,n$ that have exactly $ c_1$ cycles of length $1$,..., $c_n$ cycles of length n, it is trivial to observe that the sum over all permutations of $ 2^{f(\sigma)}$ is the coefficient of $x^n$ in $\sum_{j=0}^{n}{\frac{1}{j!}{(\frac{2x}{1}+...+\frac{2x^n}{n})^j}}$ multiplied by $n!$. To see why it suffices to develop each paranthesis using the multinomial formula and it's done.  Now, let's pass a little bit to some entire series. Observe that in fact the coefficient of $x^n$ in the last splendid sum is exactly the coefficient of $x^n$ in the developement of $ e^{2(x+\frac{x^2}{2}+...+\frac{x^n}{n})}$ seen a an entire series. But since $ x+\frac{x^2}{2}+...+\frac{x^n}{n}=-ln(1-x)+o(x^{n})$ in a neighbourhood of $0$, it follows that this coefficient is nothing else than the coefficient of $ x^n $ in $ e^{-2ln(1-x)}=\frac{1}{(1-x)^2}$, which is $n+1$. Thus our sum of $2^{f(\sigma)}$ is in fact $(n+1)!$ and the conclusion follows by Wilson theorem. If I'm not wrong, this method gives a nice closed formula for $\sum_{\sigma\in S_n}{c^{f(\sigma)}}$ for all real number $c$. Sorry if I wrote stupidities here.

I like the problem :).

By Polya's counting theorem, $\frac 1{(p-2)!}\cdot\sum_{\pi\in S_{p-2}}2^{f(\pi)}$ is precisely the number of distinct colorings of a set with $p-2$ elements in two colors s.t. two colorings are considered the same iff we can get from one of them to the other one by a permutation in $S_{p-2}$.

Clearly, the equivalence class of a coloring is uniquely determined by the number of white (we assume the colors are black and white) elements in our $p-2$-element set, so there are $p-1$ such colorings. This means that $\frac 1{(p-2)!}\cdot\sum_{\pi\in S_{p-2}}2^{f(\pi)}=p-1$ or, in other words, $\sum_{\pi\in S_{p-2}}2^{f(\pi)}=(p-1)!$. All we need to do now is use Wilson's theorem to finish it off.

Thank  everyone who likes the problem,I will post more problems like this  later. :)

Was the problem to show $\sum_{\pi\in S_{p-2}}2^{f(\pi)}\equiv 1 \mod p$¿

Sorry,but why can't I read the post normally?

Some people, here sss, came somehow to the idea to TeX the code in the AoPS-TeXer and then link to the image created by this. But those images are gone now (cause the server was changed and that stuff was not contained).

To all: don't do so!

Thanks.But do you remember what sss posted?


inequalities
LaTeX
inequalities proposed

Let $a, b, c$ sides of a triangle. Prove that:

                           \[ 11(\sum {a^{2}b^{2})+4\sum {ab(a+b)}\geq 20abc(\sum {a})+\frac{3}{2}(\sum {a^{4}). }}\]

Maybe you commited an error with Latex, because this ineq isn´t true if $a=b=c=1$.

So, can you edit this problem? It seems to be nice! Thank you!


The question is: let U,V,W be subspaces of linear space X. Is the following statement true?
Dim(U+V+W)=Dim(U) + Dim (V) + Dim (W) - Dim (U intersect V) - Dim (V intersect W) - Dim (U intersect W) + Dim (intersection of U, V, and W).
If so, prove it. If not, provide a counter-example.

I think I have created a counter-example:

Let X = R^3. Let U be the space with the basis (1,0,0), (0,1,0). Let V be the subspace (0,1,1), (1,0,0). Let W be the subspace (0,-1,1), (1,0,0). Then the dimension of (U+V+W) = 3. Dim U = Dim V= Dim W = 2. Dim (U intersect V)=Dimension(V intersect W)=Dimension (U intersect W) = 1. Dimension (intersection U, V, W) = 1. Clearly, 2+2+2-1-1-1+1=4, which is not equal to three.

Is my reasoning correct here?

Thanks!


place to put clever things are puns
e.g. why do we park in the driveway and drive in the parkway
why do noses run and feet smell
u get teh idea...

Why are threads in an educational forum stupid?

i read those things at http://www.funnythought.com

I've got some

1. How can you dig out of a hole?
2. What's the difference between new and brand new?
3. Why are wise man and wise guy opposites?
4. When somebody greets us with "how do you do", why don't we ever reply "do what"?
5. How come even after you lose your temper, you still have a temper?

My physics teacher makes puns all the time. He's hella quick with them also.

After lecturing about currents and electric stuff, he asked if the lecture was "shocking or electrifying"?

...

I told him it was re"volt"ing.

what does:
[b]ygolohcysp[/b]
stand for?

here are some others i liike (ok i shouldnt have named this topic punny things cuz some of these arent puns but anyways...)
You show me a piano falling down a mine shaft, and i'll show you A flat minor

what if there was someone named Will in the army? wouldnt he be scared when the officers said, "FIRE AT WILL!

Never greet Jack in a plane.

"HI JACK!!!"

why is there braille on drive thru ATMs?


geometry
cyclic quadrilateral
geometry proposed

(D.Shnol, 8--9) The bisectors of two angles in a cyclic quadrilateral are parallel. Prove that the sum of squares of some two sides in the quadrilateral equals the sum of squares of two remaining sides.

Suppose that the bisectors from $ B$ and $ D$ are parallel.

The bisector of $ \angle ADC$ intersects $ AB$ in $ E$ and the bisector of $ \angle ABC$ intersects $ DC$ in $ F$.

$ \angle DEB\equal{}A\plus{}\frac {D} {2}$ and $ \angle FBE\equal{}\frac {B} {2}$

$ DE \parallel FB \Rightarrow A\plus{}\frac {D} {2}\plus{}\frac {B} {2}\equal{}180^{\circ}\Rightarrow A\equal{}C\equal{}90^{\circ}$

Finally $ AB^2\plus{}AD^2\equal{}BC^2\plus{}CD^2\equal{}4R^2$

If the bisectors of B and D are parallel, doesnt that mean $ \angle B\equal{}\angle D\equal{}90$? Then, $ AB^2\plus{}BC^2\equal{}CD^2\plus{}AD^2\equal{}AC^2$.


Show that $ 2^n\plus{}1$ is not divisible by $ 15$ for all $ n\in \mathbb{N}$.

hello, note that $ 2^4\equiv1 \mod 15$, so we have the following cases
$ 2^{4n\plus{}1}\equiv 2\mod 15$ and $ 2^{4n\plus{}1}\plus{}1\equiv3 \mod 15$
$ 2^{4n\plus{}2}\equiv4 \mod 15$ and $ 2^{4n\plus{}2}\plus{}1\equiv4\mod 15$
$ 2^{4n\plus{}3}\plus{}1\equiv9\mod 15$
$ 2^{4n\plus{}4}\plus{}1\equiv 2 \mod 15$
and so we have proved that $ 2^n\plus{}1$ is for any $ n$ not divisible by $ 15$.
Sonnhard.

Suppose $ 2^n\plus{}1\equiv 0\pmod{15}$.
$ 15\equal{}3\cdot 5$, so $ 2^n\plus{}1\equiv 0\implies 2^n\equiv\minus{}1\equiv 4\pmod{5}$ and $ 2^n\equiv \minus{}1\equiv 2\pmod{3}$.
The first implies that $ 2^n\equal{}5k\plus{}4$. Substituting, $ 5k\plus{}4\equiv 2\implies 2k\equiv\minus{}2\equiv 1\pmod{3}$.
$ 2\cdot 2k\equiv k\equiv 2\cdot 1\equal{}2\pmod{3}\implies k\equal{}3j\plus{}2$.
Therefore, $ 2^n\equal{}5(3j\plus{}2)\plus{}4\equal{}15j\plus{}14$
Examining $ 15j\plus{}14$ modulo 2, we have $ 15j\plus{}14\equiv 1\pmod{2}$ unless $ j$ is even. $ 2^n$ is always even, so $ j$ must be even. Let $ j\equal{}2a$.
Then $ 2^n\equal{}30a\plus{}14\equal{}2(15a\plus{}7)\implies 2^{n\minus{}1}\equal{}15a\plus{}7$.
$ 15a\plus{}7$ is odd unless $ a$ is odd, so $ a$ must be odd. Let $ a\equal{}2b\plus{}1$.
Now $ 2^{n\minus{}1}\equal{}15(2b\plus{}1)\plus{}7\equal{}30b\plus{}15\plus{}7\equal{}30b\plus{}22\equal{}2(15b\plus{}11)\implies 2^{n\minus{}2}\equal{}15b\plus{}11$.
Now $ b$ must be odd, so let $ b\equal{}2c\plus{}1$.
Then $ 2^{n\minus{}2}\equal{}30c\plus{}15\plus{}11\equal{}2(15c\plus{}13)$.

We start to see that $ c$ must always be odd for $ 15c\plus{}12$ to be even, but by factoring out the two and dividing, we will end up again with an odd number. Applying this repeatedly, we end up with $ 1\equal{}15x\plus{}y$, where $ y$ is some odd number and $ 0<y<15$. But then $ x\equal{}\frac{1\minus{}y}{15}$ must be an integer, which is impossible; so we have a contradiction.

grn_trtle, your solution is a way to hard for such a simple problem  :roll:

Dr Sonhard Graubner's solution is much easier  :)

Maybe so, but it was certainly an elegant proof.  :lol:

By the way, would Dr. Graubner's solution be considered induction?

I believe the problem asked to show it for [b]all[/b] natural numbers n, so just the base case would not be sufficient.

[quote="blackinferno"]Couldnt you just show that the base case is wrong and its done.[/quote]
Nope, because this problem is asking us to prove that no integer $ n$ can ever satisfy those conditions. Even if we prove this works for the base case (i.e. 15 doesn't divide $ 2^1\plus{}1$), we may still have another $ n$ that is a counterexample to the problem.
You seem to be thinking that proving the base case wrong creates the "domino" effect that proves the same property all successive integers, which isn't right, unless you can demonstrate it with some induction algebra. :)


When a circle with 39 chords is given such that the number of regions inside the circle is maximized, how many regions are in this circle?

If we have 0 chords, there is 1 region.

If we have 1 chord, there are 2 regions.

If we have 2, there are 4 regions.

If we have 3, there are 7 regions.

If we have 4, there are 11 regions.

Letting the number of regions be $ f(n)$ we can quickly see that $ f(n)\equal{}n\plus{}f(n\minus{}1)$ and that $ f(0)\equal{}1$

Thus we have $ f(1)\equal{}1\plus{}1$

$ f(2)\equal{}1\plus{}(1\plus{}2)$

$ f(3)\equal{}1\plus{}(1\plus{}2\plus{}3)$

$ f(n)\equal{}1\plus{}(1\plus{}2\plus{}3\plus{}...\plus{}n)\equal{}1\plus{}\frac{n(n\plus{}1)}{2}$

Thus $ f(39)\equal{}1\plus{}\frac{39\cdot40}{2}\equal{}1\plus{}39\cdot20\equal{}781$

Despite the fact that it is enclosed in a circle, it is no different from [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?search_id=1217949413&t=247370]this problem.[/url]

It is much simpler to note that this is $ \binom{n\plus{}1}{2}\plus{}1$.

For a more general relation in higher dimensions, look [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1357876#1357876]here[/url].

Math154, that is precisely the link [i]I[/i] gave!

Sorry, I didn't suspect that you would've linked there as well, since the problems are actually not the same--what you referred to as the content of the link was really only part of it. But again, I'm sorry.


The population of a country is 21.2 million. If 86% of the people live in urban areas, which of the following is the best approximation (in millions of people) of the total urban population?

A. 20 divided by 0.80

B. 20 divided by 0.90

C. 20 * 0.90

D. 20 * 0.80

E. 30 divided by 0.80

86% is closer to 90% than 80%.

and 21.2 million is about 20 million.

so the total urban population would be 20 million * 0.9

Answer : C

When doing estimates, the best idea is to round, and then carry out the required math.

Of course, then there are all the operations, and the different ways you need to round and/or truncate to solve those, but it isn't practical to try and remember how to round when you're estimating every time you try to solve a problem.


addad $ k^2\plus{}2kn\plus{}m^2$ be ezay binahayat $ k$ morabae kamel ast sabet konid :: $ m\equal{}n$
 :?:

avval az hame bedoone az das dadane kolliate masale,farz konid $ k>0$ va $ k^2\plus{}2kn\plus{}m^2\equal{}r^2$,khob hala gharar bedid $ k\equal{}t\minus{}n$,pas darim:

$ \left(t\minus{}n\right)^2\plus{}2(t\minus{}n)n\plus{}m^2\equal{}r^2$

$ \Rightarrow t^2\plus{}m^2\minus{}n^2\equal{}r^2$

$ \Rightarrow t^2\minus{}r^2\equal{}n^2\minus{}m^2$

$ \Rightarrow (t\minus{}r)(t\plus{}r)\equal{}\text{ye adade sabet}$

hala ba borhane kholf farz konid masalan $ m<n$,pas $ t>r$,amma midoonim ba afzayeshe adade $ k$,adade $ t$ ham ziad mishe,hamchenin $ t\minus{}r>0$ pas samte chape tasavie fogh harghaddi ke bekhad mitoone bozorg beshe,vali samte rastesh sabete,ke inam tanaghoze...
ba hamin estedlal,halate $ m>n$ ham be tanaghoz mirese...
pas bayad dashte bashim $ m\equal{}n$.

Could you please post in english?
I am an Indian and am unable to understand. Please.

[color=red][b][u]Problem: [/b][/u]
If there are infinitely many integers $ k$ satisfying that $ k^2 \plus{} 2kn \plus{} m^2$ is a perfect square where $ m,n$ are positive integer constants, prove that $ m \equal{} n$[/color]

You might want to solve it yourself, it's fairly easy, so I'm hiding my solution.

[hide="My Solution"][color=blue]There exists infinitely many integer pairs $ (k,l)$ satisfying
$ k^2 \plus{} 2kn \plus{} m^2 \equal{} l^2\iff (k \plus{} n)^2 \minus{} n^2 \plus{} m^2 \equal{} l^2\iff (k \plus{} n)^2 \minus{} l^2 \equal{} n^2 \minus{} m^2\iff (k \plus{} n \plus{} l)(k \plus{} n \minus{} l) \equal{} n^2 \minus{} m^2$
This is satisfied by infinitely many pairs $ (k,l)$, and for all those $ (k,l)$, $ (k \plus{} n \plus{} l)(k \plus{} n \minus{} l)$ is constant.
Both of $ k \plus{} n \plus{} l$ and $ k \plus{} n \minus{} l$ can't be bounded because each pair of them gives a unique solution for $ (k,l)$, and if both are bounded then there are finitely many pairs. So one of them is unbounded. Thus the only way for $ (k \plus{} n \plus{} l)(k \plus{} n \minus{} l)$ to be bounded is when the other one is $ 0$, in that case $ n^2 \minus{} m^2 \equal{} (k \plus{} n \plus{} l)(k \plus{} n \minus{} l) \equal{} 0\implies m \equal{} n$ (both $ m,n$ positive).
QED[/color][/hide]

Ok here is the soln: (I don't if it is correct)

Let k^2 + 2kn +m^2=E= a^2.
==>  (k+n-a)(k+n+a)=(n+m)(n-m) [hide]

Since there will be infinitely many k and a satisfying this equation,
One of the two factorised forms in LHS will be unbounded and the other bounded as if both are bounded we will have finite number of solutions and hence for LHS to bound and still giving infite solutions, we must have LHS=0.
=====>  RHS=(n+M)(n-m)=0. As m, n are positive integer constants, we have m + n >0.
===> n=m.[hide][/hide][/hide]

I am sorry.
One correction.
For LHS to be bounded and still giving[b] infinite [/b]solns,

And also Akashnil, dont underestimate me as someone who can solve only fairly easy problems in number theory. Anything can happen to anyone anyday. It is just a matter of the right idea striking u at the right time.

I am very much surprised to see that ur solution is just same as mine. U may think that I had copied u but I know that I didn't.
Maybe, great minds think alike but definitely u r 100000 times greater than me.

[quote="Aravind Srinivas L"]And also Akashnil, dont underestimate me as someone who can solve only fairly easy problems in number theory.[/quote]
I'm sorry. I didn't mean it, I swear. I didn't say you couldn't do harder problems.

[quote="Aravind Srinivas L"]I am very much surprised to see that ur solution is just same as mine. U may think that I had copied u but I know that I didn't. [/quote]
I know you didn't.
[quote="Aravind Srinivas L"]Maybe, great minds think alike but definitely u r 100000 times greater than me.[/quote]
Not necessarily. Knowing some extra theory doesn't mean I'm greater or anything,

please don't spam in this forum,you guys better continue this kind of discussions using PMs... :)

Sorry Iranians.
But this is not a spam on this forum if u think so.
And also Akashnil, I apologize if I made U apologize to me. Because U are someone 10^4 times greater than me.
---------------Thread locked of my posts---------
I won't post hereafter here.


calculus
integration
function
logarithms
derivative
calculus computations

The method is ridiculous. Also, $dx=(\ln 2 )2^{y}dy$.

what is 'the method of inverse function? it doesn't seem as if there are any benefits. also isn't the integrand equivalent to log x/log 2, which has a well known antiderivative?

>>what is 'the method of inverse function? it doesn't seem as if there are any benefits.

Apparently sometimes the inverse of the intergrand is easier to integrate.   The method seemed to be very effective with $\int sin^{-1}xdx$,$\int tan^{-1}xdx$, and$\int sec^{-1}xdx$.  It's not my method I'm just required to use it for class.  I guess my main problem is that I differentiated incorrectly in the beginning.  I'll try it with the correct derivative $dx=(\ln2)2^{y}dy$.
Thanks


geometry
parallelogram
combinatorics proposed
combinatorics

A set [b]S [/b]with a finite number [b]n[/b] of points in the plane, [b]n≥4[/b], at most[b] n-2 [/b]of them co lineal, has the property that for any four distinct points [b]A, B, C, D [/b]the intersection point  of lines [b]AB[/b] and [b]CD[/b] (if lines [b]AB[/b] and [b]CD[/b] are different and not parallel) also belongs to [b]S[/b]. Find the maximum value of [b]n[/b].

I will prove that the maximum is $5$. The example is simple: the four points of a parallelogram and the point of intersection of the diagonals.
Like the number $n$ is finite, and not all $n$ points are in the same line, then there is at least a triangle of minimal area. Let $ABC$ be one of them. It is not hard to prove that all other points of $S$ belong to one of the lines $AB$, $BC$ or $AC$. WLOG suppose that $R_1$ and $R_2$ are points of $S$ that belongs to $AB$ and $AC$ respectively (They always exists cos there are at most $n-2$ collinear points) . It's clear that the point of intersection between $R_1C$ and $R_2B$ doesn't belong to any of the three lines $AB$, $BC$ or $AC$, so $R_1C$ and $R_2B$ are parallel. So is obvious that we will have at most one point (different of $A$, $B$, $C$) in each of the lines $AB$, $BC$ and $AC$. But it's not hard to prove that if we have points $R_1$, $R_2$ and $R_3$ in lines $AB$, $AC$ and $BC$ respectively, and $R_1C$, $R_2B$, $R_3A$ are parallel,  then one of the $R_i$ belong to a side of the triangle $ABC$, and that's impossible. So, the solution is $5$ :) :D

Nice solution gilcu3!
My solution went like this: the "at most n-2 collineal points" condition implies there is a nondegenerate quadrilateral, pick it and prove if it isn´t a parallelogram the number
of points spirals to infinity.


trigonometry
calculus
calculus computations

[quote="EquinoX"]give the answer in a cartesian form

1. (10e^i*(pi/2))^4

by writing the complex number in polar form, z = re^i*(theta) find a value for the quantities of
(i+1)^100[/quote]

$\left( 10 e^{(\pi/2) i}\right)^{4}= 10000 \cdot e^{4\cdot (\pi/2) i}= 10000\cdot e^{2\pi i}= 10000$

sorry guys it's not supposed to be (10e^i*(pi/2))^4  but (10e^i*(pi/2))^1/4


How many people here self-study through textbooks (besides AOPS) with no connection to school credit?

Those who study for MO all meets your condition.


Sorry if someone has asked this question before but if I took the AMC 12 and I'm in grade 10 or below, do I only need to get the floor score or does my AMC score count?  Because on the websitel it says only AMC 10 takers need the floor score while other people say differently.  Thanks.

Well. . . you got some balls takin' the 12 as a 10th grade or lower, but I think that anyone who takes the 12 must get 100 or above to qual for the AIME.

Hope this helps.

Noooo, I mean, on the AIME, do I only need the floor score or do I have to get among the top 160 AMC 12 + AIME indices in the nation?

There was an earlier thread on this question:
[url]http://www.artofproblemsolving.com/Forum/viewtopic.php?t=8422[/url]

You need the floor. Last year, all you needed was 8 questions. I got 7 cause I thought that a triangle could have sides of 15-15-30 :(

Oh well.


vector
linear algebra
linear algebra unsolved

Given a vector space V and subspaces H,K,L of V
Define H+K+L={a|a=x+y+z; xEH, yEK, zEL}

a) Show that H+K+L is a subspace of V.
b) Show that H+K+L contains H, K and L.
c) Show that H+K+L is the smallest subspace containing H, K and L.

a) $ 0\in H\plus{}K\plus{}L$ since $ 0\equal{}0\plus{}0\plus{}0$.

Let $ u,v\in H\plus{}K\plus{}L$, then $ u\equal{}x_1\plus{}y_1\plus{}z_1$ for some $ x_1\in H$, $ y_1\in K$, and $ z_1\in L$. Likewise $ v\equal{}x_2\plus{}y_2\plus{}z_2$. So $ u\plus{}v\equal{}(x_1\plus{}x_2) \plus{} (y_1\plus{}y_2) \plus{} (z_1\plus{}z_2)$ and clearly by subspace properties each one of those sums is in the proper respective places. So $ u\plus{}v\in H\plus{}K\plus{}L$.

Let $ \alpha\in F$. Then $ \alpha u\equal{}\alpha (x_1\plus{}y_1\plus{}z_1)\equal{}\alpha x_1 \plus{} \alpha y_1 \plus{} \alpha z_1\in H\plus{}K\plus{}L$.

b) Since $ H$, $ K$, and $ L$ are subspaces the zero vector is in each. So, $ H\equal{}\{a : a\equal{}x\plus{}0\plus{}0, x\in H\}\subset H\plus{}K\plus{}L$.

c) Let $ U$ be subspace of $ V$ such that $ H,K,L \subseteq U$. It's easy to see that $ H\plus{}K\plus{}L \subseteq U$ (because $ U$ is closed for operation $ \plus{}$). So, $ H\plus{}K\plus{}L \subseteq U$, which show the problem.


HCSSiM geometry Columbia MATHCOUNTS blogs search AoPSwiki

OK, here's Geography. Someone starts with a city, state country, etc..., and the person below me posts a different city, state, country, etc... that starts with the last letter of the country the person above them said. An example:

    person #1: Arkansas

    #2: San Diego

    #3: Oklahoma

    ...

    ...

    ...   End Example...

So I'll start with:

                                    HALIFAX!!
                                    just kidding.

                         I'll start with Texas.

South Korea

Btw, are rivers, lakes, seas, and oceans allowed?

yuma (I think thats a city in arizona)

Can we repeat things?

Antarctica

Lets change the rule: the place must end in an 'a'.

@ ProtestanT: yup...it just has to be a real river, lake, se, or ocean!

@dragon96: Nope, no repeats...

if we just end in a's then we will run out of things to write, so...

Arkansas!!

;-)

YEMEN

The message is too small. Please make the message longer before submitting.

BAHHH

[quote name="RedFireTruck" url="/community/p17790112"]
^ this post is a few months b4 my birthday :rotfl:
[/quote]

again, how did u find this thread XD


algebra
polynomial
calculus
integration
function
domain
linear algebra

let $n\geq 3$ and $\omega_{n}=e^{\frac{2\pi i}{n}}$
consider $R=\mathbb{Z}[\omega_{n}]$ and $K=\mathbb{Q}(\omega_{n})$

Show that the only algebraic integers in $K$ are those in $R$, meaning that the only elements of $K$ that satisfy a monic polynomial with integer coefficients are those in $R$

If I understand well, it means that $R$ is algebraically closed?

That mean's not that $R$ is algebraically closed, but integrally closed.

But the prove for the statement itself is kind of longer, I will post a solution later on.

Here it goes:

Let $\zeta$ be any primitive $z$-th root of unity and $\mathfrak{o}$ be the integrally closure of $\mathbb{Z}$ in $\mathbb{Q}(\zeta)$.

First some prerequisite:
Theorem 1: Let some integrally closed integral domain $A$ and it's field of fractions $K$ be given. Let $x_1,x_2,...,x_n$ be an integral basis (in respect to $A$) of the finite seperable extension $L$ of $K$. Let $B$ be the algebraical closure of $A$ and $d$ the discriminant in respect to this basis.
Then $dB \subset A[x_1,x_2,...,x_n]$.
Prove:
Take any $b=b_1x_1+b_2x_2+...+b_nx_n \in B$, $b_i \in K$. Then the $b_i=y_i$ are the solutions of the system $Tr_{L|K}(x_ib)=\sum_{j=1}^n Tr_{L|K}(x_ix_j)y_j$ for $1 \leq i \leq n$. Since $b,x_i \in B$, also $bx_i \in B$, thus $Tr_{L|K}(bx_i) \in A$. But by Cramer's rule, the $b_i$ are then just quotients $b_i=\frac{a_i}{d'}$ with $a: i \in A$ and $d'$ being the determinant of $(Tr_{L|K}(x_ix_j))_{1\leq i,j \leq n}$. So when we can prove that $d=d'$, the result immediatly follows.
But when $\sigma_k,1\leq k \leq n$ are the $K$-imbeddings of $L$ into it's integral closure, $Tr_{L|K}(x_ix_j)=\sum_{k=1}^n \sigma_k(x_ix_j)=\sum_{k=1}^n \sigma_k(x_i) \sigma_k(x_j)$, thus the matrix $(Tr_{L|K}(x_ix_j))_{1\leq i,j \leq n}$ is the product of the matrix $(\sigma_k(x_i))_{1 \leq i,k\leq n}$ and it's transpose, giving the result by multiplicativity of the determinant.

Now let's show it for prime powers $z=p^n$:

Lemma 1: For every $m$ coprime to $p$ we have that $1-\zeta$ and $1-\zeta^m$ are associated.
Prove:
There exists a $k$ with $km \equiv 1 \mod p^n$. Take it and $\frac{1-\zeta^m}{1-\zeta}=1+\zeta+\zeta^2+...+\zeta^{m-1}$ and also $\frac{1-\zeta}{1-\zeta^m}=\frac{1-\zeta^{km}}{1-\zeta^m}=1+\zeta^m+\zeta^{2m}+...+\zeta^{(k-1)m}$ will both be integral, thus the desired numbers are associated.

Lemma 2: We have that $(1-\zeta)^{\phi(p^n)}$ and $p$ are associated, thus the ideal $<p>$ splits totally.
We have (consider the $p^n$-th cyclotomic polynomial $\Phi_{p^n}(x)$)
\[ \prod_{m \in \mathbb{Z}/p^n \mathbb{Z}^*} (x-\zeta^m) = \Phi_{p^n}(x) = \frac{x^{p^n}-1}{x^{p^{n-1}}-1}= x^{(p-1)p^{n-1}} + x^{(p-2)p^{n-1}} + ... + x^{p^{n-1}} + 1  \]
and setting $x=1$ yields $\prod_{m \in \mathbb{Z}/p^n \mathbb{Z}^*} (1-\zeta^m)=p$.
But $1-\zeta$ and $1-\zeta^m$ are associated by Lemma 1, so we get $p=\epsilon (1-\zeta)^{\phi(p^n)}$ with unit $\epsilon$, meaning that the ideal $<p>$ totally splits into $<1-\zeta>^{\phi(p^n)}$.

Lemma 3: When writing some $a \in \mathfrak{o}$ as $a=a_0+a_1\zeta+a_2\zeta^2+...+a_{\phi(p^n)-1}\zeta^{\phi(p^n)-1}$ with $a_i \in \mathbb{Q}$ (this can be done on a unique way for every such $a$ since $\zeta^i; i=0,1,2,...,\phi(p^n)-1$ is a basis), we have that $v_p(a_i) \geq 0$ for all $a_i$, saying that the denominator of the $a_i$, if written in reduced form, is not divisible by $p$.
Prove:
Also $(1-\zeta)^i;i=0,1,2,..., \phi(p^n)-1$ builds a basis, so lets write $a=b_0+b_1 (1-\zeta) + b_2 (1-\zeta)^2 + ... + b_{\phi(p^n)-1} (1-\zeta)^{\phi(p^n)-1}$ with $b_i \in \mathbb{Q}$. Looking at the valuation $v_{1-\zeta}(o)$ given by $1-\zeta$ (so the highest integer $k$ with $o \in <(1-\zeta)^k>$) gives that $v_{1-\zeta}(b_i) \equiv 0 \mod \phi(p^n)$ by Lemma 2.
But by that $v_{1-\zeta}(b_i(1-\zeta)^i)=v_{1-\zeta}(b_i) + v_{1-\zeta}((1-\zeta)^i) \equiv i \mod \phi(p^n)$ give pairwise different residue classes , so the valuations $v_{1-\zeta}(b_i(1-\zeta)^i)$ are pairwise different, and since this valuation is not archimedian, we get $0\leq v_{1-\zeta}(a) = \min_i (v_{1-\zeta}(b_i (1-\zeta)^i)$.
Now using that $v_{1-\zeta}((1-\zeta)^i)=i < \phi(p^n)$ for all desired $i$, finally (here again $v_{1-\zeta}(b_i) \equiv 0 \mod \phi(p^n)$ is needed) $v_p(b_i)=\phi(p^n) v_{1-\zeta}(b_i) \geq 0$ follows. Now just reorder back to $a=a_0+a_1\zeta+a_2\zeta^2+...+a_{\phi(p^n)-1}\zeta^{\phi(p^n)-1}$ and none of $a_i$ will fulfill $v_p(a_i)<0$.

Lemma 4: the discriminant of the basis $1,\zeta, \zeta^2,...,\zeta^{\phi(p^n)-1}$ is (up to sign) a power of $p$.
Prove:
We are looking for the square of the determinant of $(\sigma_i(\zeta^j))_{0 \leq i,j < \phi(p^n)}$ where $\sigma$ runs through all different $\mathbb{Q}$-imbeddings of $\mathbb{Q}[\zeta]$ into $\overline{\mathbb{Q}}$, so the automorphisms of $\mathbb{Q}[\zeta]$. But these are generated by $\zeta \mapsto \zeta^k$ with $\gcd(p,k)=1$.
Thus, we want the determinant of $(\zeta^{dk})_{0\leq d < \phi(p^n) ; k \in \mathbb{Z}/p^n \in \mathbb{Z}^*}$, and by Vandermond it's square (that's the reason why we need not to look at any ordering) is equal to $\prod_{k,l \in \mathbb{Z}/p^n \mathbb{Z}^*} (\zeta^k-\zeta^l) = \epsilon(1-\zeta)^t$ with some integer $t$ and unit $\epsilon$ by Lemma 2. But the last number must be an integer and is up to unit a power of $1-\zeta$, so must be a power of $p$ multiplied with an integral unit, thus the statement.

Now finally:
Lemma 5: $\mathfrak{o}=\mathbb{Z}[\zeta]$
Prove:
By Theorem 1 and Lemma 4, we get that $p^s\mathfrak{o} \subset \mathbb{Z}[\zeta]$ for some integer $s$, thus every element $a=a_0+a_1\zeta+a_2\zeta^2+...+a_{\phi(p^n)-1}\zeta^{\phi(p^n)-1} \in \mathfrak{o}$ fulfills that $p^sa_i \in \mathbb{Z}$, but by Lemma 3 this already means that $a_i \in \mathbb{Z}$, giving the result.

We will now use the following theorem (I can give a prove when needed):
Let $A$ be an integrally closed integral domain and $K$ it's field of fractions. Let also $M,N$ be finite seperable extensions of $K$ with integral closures $B,C$ of $A$ such that there exist a integral bases for them (e.g. extensions of number fields). When then also $deg(MN|K)=deg(M|K)deg(N|K)$ holds and the discriminants $b,c$ of $B,C$ in respect to $A$ are relatively prime, then we have that the integral closure of $A$ in $MN$ equals $BC$ and has discriminant $d=b^{deg(N|K)}c^{deg(M|K)}$.

Now when $\zeta, \eta$ are primitive $m,n$-th root's of unity with $\gcd(m,n)=1$, then inductively all conditions of the theorem are fulfilled (by Lemma 4 and $deg(\mathbb{Q}[\zeta,\eta]|\mathbb{Q})=\phi(mn)=\phi(m)\phi(n)=deg(\mathbb{Q}[\zeta]|\mathbb{Q})deg(\mathbb{Q}[\eta]|\mathbb{Q})$) and finally the goal of $\mathfrak{o}=\mathbb{Z}[\zeta]$ in general is archieved.


geometry
rectangle
geometric transformation
rotation
function
combinatorics proposed
combinatorics

Here is a theorem of my own which implies as a special case one of the most difficult problems to be proposed on an All-Russian Mathematical Olympiad (Problem 11.8, 1998). I have actually managed to obtain a significantly stronger result (to be published somewhere  ;) ), but won't bother you with redundant definitions and notations. The Russian problem, which you can find at http://www.kalva.demon.co.uk, is an easy corollary to the following theorem by taking $S$ to be the set of all cells of the rectangle and $F \subseteq 2^S$ to be  collection of all subsets of $S$ corresponding to some translation (or its rotation) of our figure (see the kalva site for the problem, once again.)

Theorem. Let $S$ be a finite set and $F \subseteq 2^S$ be a collection of subsets of $S$ with the following property. For any (not necessarily pairwise distinct) sets $A_1,\ldots,A_k \in F$, there exist two elements $x,y \in S$ such that the number of indices $i$ for which $x \in A_i$ differs from the number of indices $j$ for which $y \in A_j$. Then, there exists a function $f : S \to \mathbb{R}$ with the following properties:
  (i) For each set $X \in F$, $\sum_{x \in X} f(x) < 0$; and
  (ii) $\sum_{x \in S} f(x) > 0$.

I won't (yet) send in a solution to give you a chance to think of an alternative one. I used this theorem as a lemma in proving and generalizing a conjecture of Gabriel Carroll.

--Vesselin

[quote="vess"]
I used this theorem as a lemma in proving and generalizing a conjecture of Gabriel Carroll.
[/quote]
Great! Is Gabriel a user of this forum?
By the way, what was Gabriel's conjecture?

Nope. The conjecture I was referring to is this:

Let $S$ be a finite set and $F \subseteq 2^S$ be closed under taking unions. Then, there exists a function $f:S \to \mathbb{R}$ such that, for any non-empty $T \subseteq S$, $\prod_{{x \in  T} f(x)}$ is an integer iff $T \in F$.

Note that the requirement that $F$ is closed under arbitrary unions cannot be weakend to closure under disjoint unions, as the example of
\[
F = \{1\}, \{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}, \{3,4\}, \{4,1\}, \{1,2,3\}, \{1,3,4\}, \{1,4,2\}
\]
shows. I have completely characterized all families $F$ for which there is such a function $f : S \to \mathbb{Q}$, and have obtained some partial results in the case of functions $S \to \mathbb{R}$.

Anyway, this is a little off-topic. The post suggest a discussion on the All-Russian problem and its generalizations.

[quote="MindFlyer"][quote="vess"]
I used this theorem as a lemma in proving and generalizing a conjecture of Gabriel Carroll.
[/quote]
Great! Is Gabriel a user of this forum?
[/quote]

Gabriel I think it is not (yet). However Reid Barton is :P:)

Well, the Russian problem was hard enough..
I can't understand how anyone can find such a solution, though the idea not so hard.( I refer to the solution I found in Titu Andreescu, maybe there exists a simpler one)
Vess you must be really great if you can generalise such problems!
Are you still a student?


Here is a nice problem:

Let $a,b$ be positive integers such that
               i) $gcd(a,b)=1$
              ii) if $p$ is a prime number such that $p\le \sqrt{a^2+b^2}$, then $p|ab$
Prove or disprove that $a^2+b^2<49$

Easy but very nice problem. :cool:
Assume $ a<b $(If $a=b$ then both of them are equal to $1$).
We have $ b-a \leq \sqrt{a^2+b^2} $.But $(b-a,ab)=1$ then $b-a=1$.
We have: $a-1 \leq \sqrt{2a^2+2a+1}, ((a-1),a(a+1)) \leq 2$
So $a-1=2^x$.
By a similar way,we have:$a+2=2^y$ if $a+2 \leq \sqrt{2a^2+2a+1}$.
Hence $a=2 \Rightarrow 2a^2+2a+1 =13<49$
If $a+2>\sqrt{2a^2+2a+1}$ then $a<3$.Thus $2a^2+2a+1<25<49$.  :)


geometry
circumcircle
inequalities
inequalities solved

Let R and r be respectively the radius of the circumcirle and the incircle of triangle ABC. Put x=r/R, y=(a+b+c)/(2*R).
Prove that: y>=x1/2(61/2 + (2-x)1/2)

Write the inequality in the form p \geq  \sqrt (6Rr)+ \sqrt (2Rr-r 2 ), or p 2 \geq 8Rr-r 2 +2 \sqrt [6Rr(2Rr-r 2 )]. But it is known that p 2 \geq 16Rr-5r 2  \geq 8Rr-r 2 +2 \sqrt [6Rr(2Rr-r 2 )]. The last inequality is equivalent with 4(2Rr-r 2 )\geq 2 \sqrt [6Rr(2Rr-r 2 )], or 4(2Rr-r 2) \geq 6Rr or R \geq 2r, which is true.


How'd you do? I got a 5/6... stupidly missed #6

6/6. I dont like the problems this time at all. 1) was a problem to be given to 2nd graders. 2), 3), 4) were trivial. 5) seemed the toughest, but it was easy to guess. 6) was better.

I'm confused. I took the county math league and the problems were completely different from the state contest. Does anybody take county contest or something in similar?

The county contest is independant.  All the state math leagues are run by one group, so your state math league is the same as my state math league and it's totally different than your county math league.

Oy now I know I suck major bum...we got a meet coming up this week and I scored a measly 4, 4, 6, 6, and 6 on the preliminaries...*sigh* and this isn't even high school math league, depressing ain't it?

I think you are talking about a different league than us tare. The Math League, who organizes the 6 monthly contests for high school, has a middle school contest. It is only 1 contest though, sometime in late february. format is 30 minutes, 40 questions. what math league is the one you are mentioning?

[quote="cats..."]I got 5/6, and got the 1st question wrong.  They were not too good this time... i think i had the first 4 in < 5 minutes.  But then again i got the first question wrong.[/quote]
You missed the first one? Are you talking about the same contest? It was ceiling(365/7)=53

(problem: what is the maximum number of sundays that can occur in a 365 day year?)

ach do you remember what problems 5 and 6 were?

I think tare's talking about her local contest, she posted some questions from it before, i forget the website though.  At least i think that's what she's talking about.

For number one, i thought it was the max. sundays in a month.  I put 5.

5 was the rates one, 6 was the finding of the coefficient of a multinomial expansion.

5. I drove at constant speed for 3 hours and traveled x km. If I had driven each km 1 minute faster, I'd have driven 30 km further in the 3 hours. Find x.

6. The second term of (-x3 + 3x2 - 5x + 7)2004 is kx6011. Find k.

#6 could have been much harder had they asked for the coefficient of, say, the x^2921 term. In fact, I can't think of a good way to solve that at all. Any ideas?

for 6, the next largest power of x is 6011, which u get by having an x :^2: in the place of an x :^3:. so it'll look like [(-1)^2003]3x :^2:. but we can choose any one of the 2004 sums to pick the 3x :^2: from, so the answer is (-1)(3)(2004) or -6012. for 5, i think you could use conversion factors to get the answer.

The answer to #5 was 60. Play around with D=vt for a while.

I got a 5/6... screwed up on the last one pretty badly.. =)


This  is buzzzing all over in the world in  Math circles.

You heard it here first.

K  Majoomdar,  a first year IIT  student  has caused a major stir by producing this  map which actually requires  a minimum of five colors  to color.

[b]So now it is suspected that the  famous  proof of four color theorem given by Robertson, Sanders, Seymour, and Thomas  is flawed.
[/b]
[img]http://mathforum.org/wagon/fall97/images/5colormap.gif[/img]

It is easy to check and try it out, you would actully need five colors to color it.

[edit] Nice one...I wasn't expecting the joke so early (it's still March here).

My guess is that this topic is an April Fool's joke.

I've seen it before, and I've also seen its coloring. I wish I could remember when and where.
That freshman should be expelled for plagiarizing! (Just kidding, but if he did find it on his own, it would be very impressive.)

Yea, it's on Math World: [url=http://mathworld.wolfram.com/Four-ColorTheorem.html]Only picture on the page[/url]

I hate to ruin the joke, but I'd hate to be the fool

I read too much at mathworld.

http://mathworld.wolfram.com/Four-ColorTheorem.html

[hide]

[img]http://mathworld.wolfram.com/fimg2717.gif[/img]

[/hide]

ok, so i had definately printed out the paper, and was planning on colouring it in in study hall tomorrow. how pathetic am i?  :blush:

:blush:  sorry i dont understand what the joke is.....

[hide="Please donot click for next 25 hours"]Oh well ... Guess recycled Scientific Americna coulum has a shorter half life than  a pi-meson  in this company  :)

I remember this Martin Gardner's April fool  colum (Late 1970's) (I used to subscribe to Scientific American) .. hate to admit it but I actully  spend my time in computer room to write  a program (in those days  this was puching cards for an IBM 370 type computer  using PL/I language) to test that  and then realized that it was a joke .. :blush:

The issue had other  intersting news items - Like  a   computer program finding chess move  P-KR4 wins  for white (With Bobby Fisher saying that he  does not belive this and would play with the computer if it (the computer ) played without making noise.  (P-KR4 happens to be  one of the worst move  a person can make as white)

It also had a "interesting" formul for  $\pi$ (which  Ramanujan could  not prove but checked it with hand for a million digits and found it correct.

(Yes, if I read the whole thing (instead of running to write the program to test the figure) would have realized that it was a joke>

BTW today (April 1) also happens to be my birthday.

Times of India has this really funny news item too..
[url=http://timesofindia.indiatimes.com/articleshow/1066268.cms]Kashmir a part of US ..[/url]

[quote] Using spectroscopic analysis (a technique described in detail in  The Da Vinci Code'  the author claims to have discovered the original document over which the Instrument of Accession, signed by Kashmir maharaja Hari Singh and preserved in the National Archives, New Delhi, was later superimposed.

The secret document reveals that Hari Singh, equally apprehensive of joining either India or Pakistan, covertly ceded Kashmir to the US. According to Brown, when the map of Kashmir is reversed it becomes, uncannily, congruent with the hilly state of Kentucky in the southern US..
 For instance, when the longitude of Frankfort, the capital of Kentucky, is divided by the latitude of Srinagar, the Kashmiri capital, the prime number so obtained has the same numeric valency as Article 370 of the Indian Constitution which accords a special status to Kashmir. [/quote]

 :lol:  :lol:  :lol:[/hide]

[quote="Gyan"][b]So now it is suspected that the  famous  proof of four color theorem given by Robertson, Sanders, Seymour, and Thomas  is flawed.[/b]
[/quote]

This is a good one!, perfect, I have to see Professor Thomas tomorrow I will show it to him to see what does he think  :D  :D (I hope he won't get mad :P )

[quote="Gyan"][hide="Please donot click for next 25 hours"]Oh well ... Guess recycled Scientific Americna coulum has a shorter half life than  a pi-meson  in this company  :)

I remember this Martin Gardner's April fool  colum (Late 1970's) (I used to subscribe to Scientific American) .. hate to admit it but I actully  spend my time in computer room to write  a program (in those days  this was puching cards for an IBM 370 type computer  using PL/I language) to test that  and then realized that it was a joke .. :blush:

The issue had other  intersting news items - Like  a   computer program finding chess move  P-KR4 wins  for white (With Bobby Fisher saying that he  does not belive this and would play with the computer if it (the computer ) played without making noise.  (P-KR4 happens to be  one of the worst move  a person can make as white)

It also had a "interesting" formul for  $\pi$ (which  Ramanujan could  not prove but checked it with hand for a million digits and found it correct.[/hide][/quote]

[hide="Do not click if you did not read the above"]I have that article... it was the last chapter in the collection of Mathematical Games articles called "The Colossal Book of Mathematics".  The article was called "Six Sensational Discoveries".

The first discovery was the five color map.

The second discovery is what I think Gyan meant when he remembered the formula for $\pi$... it was "discovered" that $e^{\pi\sqrt{163}}$ is rational :D (actually, not just rational, an integer).

The third discovery was the P-KR4 win for White in chess

The fourth discovery was a disproof of the Special Theory of Relativity.

The fifth discovery was old papers that "prove" Leonardo DaVinci invented the first flush toilet.

The sixth discovery was a motor that runs on psychic energy.[/hide]

lots of mathematicians are suckers for these kinds of tricks

This may be [one day] old news:
[url=http://www.scmagazine.com/news/index.cfm?fuseaction=newsDetails&newsUID=d5ee7707-4e08-49f9-8bdf-299e79743c18&newsType=Latest%20News]Lethal computer virus spreads in humans[/url][quote]The first computer virus that passes from PCs to humans has been discovered in the wild. Leading anti-virus firms are putting users on high alert after Malwarlaria.B was spammed worldwide in the early hours of Friday morning.[/quote]


[hide="a"]$\cos k\theta=\Re\{\mathrm{cis}^{k}\,\theta\}$

\begin{eqnarray*}\sum_{k=0}^{n}(-1)^{k+1}\binom{n}{k}\frac{\cos{k\theta}}{\cos^{k}{\theta}}&=&-\Re\left\{\sum_{k=0}^{n}{n\choose k}\left(-\frac{\mathrm{cis}\,\theta}{\cos\theta}\right)^{k}\right\}\\ &=&-\Re\left\{\left(1-\frac{\mathrm{cis}\,\theta}{\cos\theta}\right)^{n}\right\}\\ &=&-\Re\{(-i\tan\theta)^{n}\}\\ &=&-\tan^{n}\theta\cdot\Re\{\mathrm{cis}^{n}\,(-{\pi\over 2})\}\\ &=&-\tan^{n}\theta\cos{{n\pi}\over 2}\end{eqnarray*}[/hide]

Similar idea for (b).


ARML
algebra
polynomial
number theory solved
number theory

Hi. I am from the United States of America. i tried asking this question to a couple guys in the SoCal ARML forum but they're a bit too advanced for me(freshman). I was hoping you'd understand and answer it without using any freaky theorems or postulates no one's ever heard of. just use simple polynomial factoring.

Prove:
if $n\in\&\&Z$
then prove $n^{7}-n$ is divisible by $7$.

Why have you posted this problem in multiple forums?

In that case, I will give multiple answers.  This polynomial cannot be factored into seven linear factors, if that's what you want.  The closest you can get is

$n(n+1)(n-1)(n^{2}+n+1)(n^{2}-n+1)$

However, because we're only concerned with [b]divisibility[/b], we can employ a neat trick, which is to add or subtract $7$ from any of the coefficients of any of the factors.  Hence we can look at it as

$n(n+1)(n-1)(n^{2}+n-6)(n^{2}-n-6)$

Which is, of course,

$n(n+1)(n-1)(n+3)(n-2)(n-3)(n+2)$


inequalities
Functional Analysis
linear algebra
linear algebra unsolved

If $ \{x_i\}$ is an ON-basis in a hilbert space $ H$.
And if
$ \parallel{}\sum_1^{\infty} (x_i, y) c_i x_i \parallel{} \leq C \parallel{} \sum_1^{\infty}(x_i,y)x_i\parallel{}$
for all $ y \in H$, with $ C$ a constant, and $ c_i$ scalars.
Does this imply that $ \sup{c_i}$ is finite?


calculus
derivative
function
integration
complex analysis
complex analysis unsolved

Hi all,

This is a problem from a previous problem set that I had some difficulty with, and in fact, could not complete it.  Any help would be very much appreciated.

Let $ D\equal{} \{ (x,y) \in \mathbb{R}^2 | x^2\plus{}y^2<r^2 \}$ where $ r>0$ is given.  Let $ f: D \rightarrow \mathbb{R}$ be a continuous function such that $ \frac{\partial f}{\partial x}$, $ \frac{\partial f}{\partial y}$ exist everywhere on $ D$ and are continuous.  Assume that $ g(x,y)\equal{}\frac{\partial}{\partial y} \left( \frac{\partial f}{\partial x} \right)$ exists, and is continuous everywhere on $ D$.  Prove that, for $ (x,y) \in D$, we have $ f(x,y)\minus{}f(0,y)\minus{}f(x,0)\plus{}f(0,0)\equal{}\int_0^x \left( \int_0^y g(x,y) \, \mathrm{d}y \right) \, \mathrm{d}x$.  Deduce that $ \frac{\partial}{\partial x} \left( \frac{\partial f}{\partial y} \right)$ exists and equals $ g(x,y)\equal{}\frac{\partial}{\partial y} \left( \frac{\partial f}{\partial x} \right)$.

Changing this to complex variables seems like the right thing to do, but I've had some trouble getting anywhere after that.  Thanks in advance for your responses!

Okay, so I got the first part, namely that $ f(x,y)\minus{}f(0,y)\minus{}f(x,0)\plus{}f(0,0)\equal{}\int_0^x \left( \int_0^y g(x,y) \, \mathrm{d}y \right) \, \mathrm{d}x$, simply by using the First Fundamental Theorem of Calculus.

I'm left with showing the equality of $ \frac{\partial}{\partial x} \left( \frac{\partial}{\partial y}f \right)$ and $ \frac{\partial}{\partial y} \left( \frac{\partial}{\partial x}f \right)$.  I'm not sure how to proceed, because I thought that the $ \textit{second}$ partial derivatives must be continuous for equality to be assured.  Maybe it has something to do about the premise, that $ f$ is a function from the open disc of radius $ r$, but I don't know.  Please help, someone!

Anyone?  I have an exam tomorrow, and this is really the only problem that I can't completely understand.  Sorry if I'm being a bother, but I could use some help.

This isn't a complex analysis issue.  Use the mean value theorem.  The integration argument isn't really essential--it's the iterated use of mean-value and its unwrapping that is really the crux of the argument.


algebra
polynomial
function
limit
modular arithmetic
induction
number theory unsolved

I know the solution you are talking about... I mean, I know the official solution, which is heavy on advanced mathematics :) I had difficulties to understand it myself, I cannot remember it properly now, but I am quite sure that it is correct...

Where the official solution can be found ? [any link], or at least what is the name of that book ?

Don't know, I got the booklet from Kaloyan Slavov - the 777776 guy :D - in Tokyo.

Is it long ? Or can I ask you to write it here please ?  :)

It is Tournaments of Towns 1982, 9-10 grades ;)
But the initial problem contains an additional condition: $P(x)$ is monic.

[quote="Myth"]Also it was on Russian TST 1997 (where I participated :) ).

Easy case: $\deg P$ is even.
Let $x_n$ be an integer root of $P(x)=2^n$. We may wlog assume $x_n>0$ and $x_n$ is increasing for all large $n$. We see that $P(x_{n+1})-P(x_n)=2^n$ is divisible by $x_{n+1}-x_n$, so $x_{n+1}-x_n=2^{k_n}$. And it is clear $k_n$ is increasing for all large $n$. Thus $\frac{x_{n+1}}{x_n}=1+\frac{2^{k_n}}{x_l+2^{k_l}+...+2^{k_{n-1}}}$, where $l$ is an integer s.t. $k_l<k_{l+1}<...$. It follows that $\liminf \frac{x_{n+1}}{x_n} \geq 2$. It is an absurd if $\deg P>1$.

For case $\deg P$ is odd we need more accurate boring arguments to justify this approach.

Hope it is correct. :blush:
I never saw any solution of this problem.[/quote]

Sorry, but I can't see WHY $k_n$ increases, can you explain better?  :?   I like your easy idea, and I suppose it's no hard to give a general solution. Good luck.

Best regards.

RX the Crazy Math

[quote="Myth"]But $x_{n+1}-x_n$ increases![/quote]

Not agree with the fact that $x_n$ increases, the following example is NOT a solution but shows you why $x_n$ doesn't increase if $x_n\ge 0$, $p(x)=-3x^2+x+4$ has the following properties $x_2=0$ and $x_1=1$, so WHY increases?, I think you can't assume $x_n$ increases if $x_n\ge 0$.

Best regards.

RX the Crazy Math

You should read solutions more carefully: I said $x_n$ and $x_{n+1}-x_n$ increase for all LARGE $n$.

With the assumption that the leading coefficient is positive, $x_n$ eventually increases, i.e. increases for $n\ge N$ for some $N$.

I think there is a quite simple solution:
Lemma: Any polynomial $P(X)=uX^n+vX^{n-1}+\cdots+$ satisfies $\lim_{x\rightarrow \infty} \frac{P(x)}{(ax+b)^n}=1$, where $a=\sqrt[n] {u}, b=\frac{v}{nu}$.
The proof of lemma is obvious.

Now to pass to the proof of our problem.
Let $deg(P)=n$. We prove that $n=1$. Indeed, suppose not.
Approximate $P(X)$ by $(aX+b)^n$ as in the lemma.

We get two cases:
1) $a$ is integer. Then let $k_m$ be one solution of the equation $P(X)=2^{nm+1}$. Obviously $k_m \rightarrow \infty$
Then from the lemma we get $\lim_{m \rightarrow \infty} {ak_m+b-2^mj}=0$ where $j=\sqrt[n] 2$.
This means $\lim_{m\rightarrow \infty} \{2^mj\}=\{ak_m+b\}=\{b\}$. But $j$ is irrational, and now we easily derive a contradiction.
2) $a$ is not integer, so $a$ is irrational. This case is quite similar, just we have to look to $l_m$ the integer solution of the equation $P(X)=2^{mn}$.
Analogously we get $\lim_{m \rightarrow \infty} {al_m+b-2^m}=0$ thus
$\lim_{m \rightarrow \infty} \{\frac{2^m}{a}\}=\{l_m+\frac ba\}=\{\frac ba\}$. Since $\frac 1a$ is irrational we again get a contradiction.

Hence $n=1$ and this case is really easy to handle.
The proof is finished.

[quote="iura"]Then from the lemma we get $\lim_{m \rightarrow \infty} {ak_m+b-2^mj}=0$ [/quote]
Are you sure?
In my opinion we have only $ak_m+b \sim 2^mj\ (m \rightarrow \infty) $
Can you explain?

Yes, I also want to know iura's answer to this question ;)

Myth and Blang, you are right. The solution is not wrong, just the lemma must be rewritten in a stronger way (but it's still obvious). Here's the correct version of the solution.

Lemma: Any polynomial $P(X)=uX^n+vX^{n-1}+\cdots+$ satisfies $\lim_{x\rightarrow \infty} |\sqrt[n]{P(x)}-(ax+b)|=0$, where $a=\sqrt[n] {u}, b=\frac{v}{na}$. (Actually the lemma is the 'aproximation' of the polynomial with a power of a linear and can have more versions)
Proof of lemma:

Suppose, for contrary, that for some $t>0$ we have $|\sqrt[n]{P(x)}-(ax+b)|>t$ for arbitrary large $x$.
Then, either $\sqrt[n]{P(x)}-(ax+b)>t$ for infinitely many $x$ or $\sqrt[n]{P(x)}-(ax+b)<-t$ for infinitely many $x$.
First case: Since starting from somewhere $P$ is increasing we get $P(X)>(ax+b+t)^n$ so $Q(X)=(aX+b+t)^n-P(X)<0$.
But the leading coefficient of $Q(X)$ is $ntX^{n-1}$ which is positive. Thus we can't have $Q(x)<0$ for large $x$ contradiction.
Second case: That's pretty similar: We get $P(x)<(ax+b-t)^n$ for arbitrary large $x$ so $R(X)=P(X)-(aX+b-t)^n$ again has positive leading coefficient and is negative for arbitrary large $x$ and we have the same contradiction.

Now to pass to the proof of our problem.
Let $deg(P)=n$. We prove that $n=1$. Indeed, suppose not.
Approximate $P(X)$ by $(aX+b)^n$ as in the lemma.

We get two cases:
1) $a$ is integer. Then let $k_m$ be one solution of the equation $P(X)=2^{nm+1}$. Obviously $k_m \rightarrow \infty$
Then from the lemma we get $\lim_{m \rightarrow \infty} {ak_m+b-2^mj}=0$ where $j=\sqrt[n] 2$.
This means $\lim_{m\rightarrow \infty} \{2^mj\}=\{ak_m+b\}=\{b\}$. But $j$ is irrational, and now we easily derive a contradiction.
2) $a$ is not integer, so $a$ is irrational. This case is quite similar, just we have to look to $l_m$ the integer solution of the equation $P(X)=2^{mn}$.
Again we get $\lim_{m \rightarrow \infty} {al_m+b-2^m}=0$ thus
$\lim_{m \rightarrow \infty} \{\frac{2^m}{a}\}=\{l_m+\frac ba\}=\{\frac ba\}$. Since $\frac 1a$ is irrational we again get a contradiction.

Hence $n=1$ and this case is really easy to handle.
The proof is finished.

[quote="blang"]First, OK for your new lemma ;) .But...

[quote="iura"]([i]case a integer[/i])
Then from the lemma we get $\lim_{m \rightarrow \infty} {ak_m+b-2^mj}=0$ where $j=\sqrt[n] 2$.
But $j$ is irrational, and now we easily derive a contradiction[/quote]
I don't see any contradiction here :? .[/quote]
Consider fractional part.

[quote="Myth"]Consider fractional part.[/quote]
OK, it's obvious :blush:

;)  The following is a simple corollary of the [url=http://mathworld.wolfram.com/ChebotarevDensityTheorem.html]Chebotarev density theorem[/url]:

[i] Let $f(x) \in \mathbb{Z}[x]$ be an irreducible integer polynomial. Assume that, for all sufficiently large primes $p$, the reduction of $f(x)$ modulo $p$ has a zero in $\mathbb{F}_p$. Then, $f$ is linear. [/i]

In this problem, choose a $k \in \mathbb{N}$ for which the polynomial $2^kP(x) - 1$ is irreducible, and consider $f(x) = 2^kP(x) - 1$. Evidently, $f(x)$ has a zero modulo each prime $p \geq 3$, because $f(x_{p-1-k}) = 2^{p-1} - 1 \equiv 0 \pmod{p}$. By the claim above and the irreducibility of $f$, $f(x)$ (and hence $P(x)$) must be linear. That's all!  :)

--Vesselin

Well, if $P(x) = y^2$  and $P(x) = 2y^2$  are both of genus 0, and parametrized by polynomials, this doesn't leave many options for P(x).

My solution is based on the fact that $a-b|P(a)-P(b)$.
suppose that $P(a_n)=2^n$, and WLOG let $a_1=0$(otherwise let $Q(x)=P(x-a_1)$)
It's easy to see $a_2$ must equal to one of $\pm1, \pm2$.
By a huge discussion involves $a_2,a_3,a_4,a_6,a_8$,we get (for all possible values of $a_2$)
\[ a_i=(2^{i-1}-1)a_2,  i=2,3,4,6,8.\]
then we could proceed on induction and get the above equation holds for all $i\in Z_+$.
Thus the only possible solution is $P(x)=\pm x+a,\pm 2x+a$ where $a\in Z$.

[quote="Alexander Lenin"]P(x) is a polynomial and all of its coefficients are integers, now, for any n belongs to N+, function P(x)=2^n at least has one root which is an integer. Give every P(x) that is possible.

(This problem is from my book, but I can't understand the solution in the book :( , it's so involved, even I suppose the solution might be wrong.)[/quote]

Is your book named "Way to IMO: A collection of MO Problems in 2004"?

[quote="wpolly"]Is your book named "Way to IMO: A collection of MO Problems in 2004"?[/quote]

No, it's form <Zhong Den Shu Xue>(2004 extra issue)

[quote="nguyenvuthanhha"][i]here is one nice solution that i have just founded[/i]
 :lol:[/quote]
It is in book of Bulgaria 2003-2006 olympiad of Nikolai Nikolov
Can some body explain me more about more the idea of Iura?
What fraction part work here as [b]Myth[/b] said?
Does is use Kronecker theorem?
Thanks you.
[b]T[/b]

This is a rough argument but its simple and im sure it works. define $x_i$ such that $p(x_i) = 2^i$ and it is clear that for large i we have $x_i-x_{i-1}$ is increasing but we can also see that eventually $x_i-x_{i-1} \le \frac{x_{i+1}-x_i}{2}$ because $x_i-x_{i-1} \mid 2^{i-1}$. Noting that if deg $p \ge 2$ then this growth is too fast and eventually you will start missing powers of 2 so clearly $p$ is linear and the answer is now clearly $x+c$.

@peregrinefalcon88

How does $ x_i-x_{i-1}\le\frac{x_{i+1}-x_i}{2} $ hold due to that divisibility? Why can't say $x_i - x_{i-1} = x_{i+1} - x_i = 2^{i-1}$?

Here is a solution expanding on [b]peregrinefalcon88's[/b] ideas.

Define the $x_i$ the same way as he did. Let $\deg f = k$. Now, I claim $x_{n+k} - 2x_n$ is a converging sequence of integers. First, note that $\lim_{n \to \infty} \frac{x_{n+k}}{x_n} = 2$ because for large $x$ $f(x)$ looks like $x^k$ times its leading coefficient. Proving this rigorously is quite boring so I'll omit it.

Now, write $f(x) = a_kx^k + \sum_{i=0}^{k-1} a_ix^i$. As $f(x_{n+k}) = 2^kf(x_n)$, we have \[ x_{n+k} - 2x_n = \frac{\sum_{i=0}^{k-1} a_i(2^kx_n^i - x_{n+k}^i)}{a_k\sum_{i=1}^0 (2x_n)^ix_{n+k}^{k-i-1}}\]

Using the limit we defined earlier it becomes a boring but easy process to show the RHS converges as we take $n \to \infty$, so it follows $x_{n+k} - 2x_n$ converges. This means for all sufficiently large $n$ (i.e. $n > N$ for some $N$) we have $x_{n+k} - 2x_n = M$ where $M$ is fixed. Thus it follows for all big enough $n$ we have $f(2x_n + M) = 2^kf(x_n)$, which only has finitely many roots unless as a polynomial identity we have $f(2x+M) = 2^kf(x)$. Let $z$ be a complex root of $f$ and note that $2z + M, 4z + 3N, 8z + 7N,...$ are all roots of $f$. Since $f$ has finite degree this sequence contains only finitely many elements and it is easy to see this only occurs for $z = -M$ (write $z = \alpha M$ and then see what happens). Thus it follows $f(x) = a(x+M)^k$ for some $a$. Clearly $a$ is a power of $2$, so let $a = 2^b$. Now note that $2^b \cdot (x_{k+b+1} + M)^k = 2^{k+b+1} \implies (x_{k+b+1} + M)^k = 2^{k+1}$ which implies $2^{1/k}$ is an integer, which is absurd unless $k=1$ so we are done. From here the problem is simple.