AMC
AIME
probability
number theory
relatively prime

1. Ten points in the plane are given, with no three collinear. Four distinct segments joining pairs of these points are chosen at random, all such segments being equally likely. The probability that some three of the segments form a triangle whose vertices are among the ten given points is m/n, where m and n are relatively prime positive integers. Find m + n.

2. Forty teams play a tournament in which every team plays every other team exactly once. No ties occur, and each team has a 50% chance of winning any game it plays. The probability that no two teams win the same number of games is m/n, where m and n are relatively prime positive integers. Find log2 n.

Anyone solved this one yet?

I am dumbfounded by probability questions of any kind, and thus am vastly interested in the solutions to these problems

Well, I'll try number 1..

[hide]

How many ways are there of picking 4 segments? There are 10C2 = 45 possible segments, so 45C4.

How many ways of picking them with a triangle included? Well, there are 10C3 ways of choosing the three vertices of the triangle, and then there are 42 other segments.

So I make it 5040/148995, or 16/473..

[/hide]

O, that's nice, but it sorta almost seems too easy.....

Number 1

Answer: [hide]okay, we take the number of ways to form a triangle, and one more segment. The number of ways to form a triangle is C(10,3). From there, the number of ways to choose a segment is 3*7+7*6/2. (the first term is the number of ways to choose a segment with one vertex shared with the triangle, and the second term is the number of ways to choose a segment not connected to the triangle) So we multiply those two numbers to find the number of ways we can find our four segments. We divide that by the number of ways to choose 4 segments, or C(C(10,2),4). From here out it's arithmetic.[/hide] could someone check this, please?

Hint: [hide]how many ways can you choose your four segments to form a triangle? Try to form the triangle first, and then consider the fourth segment.[/hide]

do you get the same thing TripleM got?

Im too lazy to do the arithmetic...sigh  :cry:

yeah i think i did. I'm also too lazy.

anyway, for #2, this is probably too simple, but here's my solution:

[hide]One team had to win 0 games, one team had to win 1 game, one team had to win 2 games, etc. up to 1 team had to win 39 games. The way to assign these teams according to the number of games they won is 40!. Once we assign the teams, the way the win/lose games is determined (Basically, I conjecture team #0 loses all games (duh), team #1 loses all games to the one but team #0, team #2 loses all games to the ones but team #0 and team #1, etc.). So, the probability is 40!/2^40[/hide]

Just wondering.. what about 1,2,..40 wins? Should you double this? I'm not sure, I'm in the middle of a game and have to think fast :)

you can't play yourself..you can't have 40 wins

True :-D I knew I shoulda waited until I had finished (winning of course)..

Ok, for number 1, TripleM's solution is correct. I am not sure about MysticTerminator's, since I, like you all, am lazy as well.

[quote]wait, does the question ask for log in base 2 of n, or log in base 10 of 2n??[/quote]

Log in base 2 of n. But it doesn't really matter, the problem just asks that so that the answer follows the AIME's standard. And, after checking the numerical answer, I don't think MysticTerminator's solution is correct.  :(

[quote="Tare"]Tell me, what are you playing?[/quote]

Oh, just good old msn messenger games. None of that AIM stuff. :)

Yeah...my solution's definitely wrong...the probability's way way waaaay greater than 1. Hold on while I figure out what's wrong.

Should the bottom be, perhaps, [hide]2^(40C2)?[/hide].

Then we just gotta count the 2s in 40! and we're done.

The answer on the AMC site is [hide]742[/hide], but I dunno why...

Its pretty much all been said:

[hide]MysticTerminator had most it it, the 40!/2^40 but its not 2^40, as there are 40C2 games in total that have to go the correct way (and 40! is the ways of choosing the order of the teams). So its 40!/2^(40C2), and when we simplify that, we have to take out the powers of 2 in 40!. Of which there are 20+10+5+2+1.[/hide]

Hmm...:

Ok, I get where 40! came from, and I get where C(40, 2) came from (the number of possible pairs of teams), but I don't understand why you have 2 raised to the C(40, 2) power.

Ah I should have said it all myself without referring to older posts. [hide]

Once we pick the final order in 40! ways, then the top team must have won all their games, the second team won all but that one, etc etc. Every game must go higher beating lower. So there are only 40! possibilities of the 40C2 going the right ways. But any possible win/loss situation of the 40C2 games is possible, 2 choices per game, which is 2^(40C2) possible outcomes. [/hide]

Ah darn it I'm really stupid Thanks MMM. Yeah, let me give a full explanation now.

Since the minimum number of games one can win is 0, and the maximum is 39, there are 40 possible totals for the number of games one can win. Thus, we have a bijection (I think that's the term) relationship between the each team and the number of games one. Well, what I mean is, one team had to win 0 games, one team had to win 1 game, one team had to win 2 games, etc. up to one team had to win all 39 games that it played. Now, let the team that won n games be called team #n. The number of ways to assign numbers to teams is 40!. Once we have assigned numbers to teams, the way the games will be won/lost is uniquely determined. (Team #0 loses all games, team #1 loses all games but the one with team #0, team #2 loses all games but the ones with team #0 and team #1, etc.). Since there are C(40,2) games, the probability of the tournament happening like that will be 1/2^C(40,2). Since there are 40! possible outcomes, we multiply by 40! to get the final probability equal to 40!/2^C(40,2).

Now, we need to cancel all powers of 2. To do that, we find the number of factors of 2 in 40!. This will be floor(40/2)+floor(40/4)+floor(40/8)+floor(40/16)+...

This method was discussed in a math jam; just look through the transcripts.

Anyway, doing that, we find the number of factors of 2 in 40! is 38. So we subtract that from the number of 2's in the denominator (which is C(40,2)) to get our final solution.

C(40,2)-38=780-38=742

Ah, I see now. That helped clarify things a lot. Thanks for the help everyone.

um...that's what this whole page was about. the solution is right above your post.

hehe

wow

13 straight hours in a bus has really messed up my head...


The Art and Craft of Problem Solving, 2nd Edition
By: Paul Zeitz

[b]1. The problem statement, all variables and given/known data[/b]
1.3.7
(AIME 1994)
Find the positive integer $ n$ for which,

$ {{\lfloor}{{\log_{2}}1}{\rfloor} \plus{} {\lfloor}{{\log_{2}}2}{\rfloor} \plus{} {\lfloor}{{\log_{2}}3}{\rfloor} \plus{} {\cdot}{\cdot}{\cdot} \plus{} {\lfloor}{{\log_{2}}n}{\rfloor}} \equal{} {1994}$

Where $ {\lfloor}{x}{\rfloor}$ denotes the greatest integer less than or equal to $ x$. (For example, $ {\lfloor}{\pi}{\rfloor} \equal{} {3}$.)

[b]2. Relevant equations[/b]

None really.

[b]3. The attempt at a solution[/b]

Well it seems like the first step would be to rewrite the problem as a summation,

$ {\sum_{i \equal{} 1}^{n}}{ {\log}_{2}{i} }$

From here I don't seem to remember any formulas for this type of summation that will help me find $ n$.

Any ideas on where to go from here?

Thanks,

-APSStudent

If you think of problem solving as just applying equations, you will not get far.

The technique is to consider when floor (log _2 x )=some constant

In my opinion, there really is no "slick" way to do this other than to try out the first few terms, and notice when you get different values for the greatest integer function. For example, for n=1, you get 0. For n=2-3, you get 1. For n=4-7, you get 2. For n=8-15, you get 3. ectr. From here, it doesn't take very long to get the answer.
I don't know if there is a very slick solution for this.
By the way, you could just look this up in the aops contest problem database that has been so generously compiled. ;)

Well not exactly all too slick but: $ \lfloor \log_{2}n \rfloor\plus{}1$ is the number of digits of n in binary. That establishes your pattern. Now if you count the sum in a different way, you can get an answer.

Hey,

Ok, I can see the following pattern,
$ {\sum_{i = 1}^{15}}{{\log}_{2}{i}} = {(0) + (1) + (1) + (2) + (2) + (2) + (2) + (3) + (3) + (3) + (3) + (3) + (3) + (3) + (3)}$

That, the number of "equivalent terms" is given as a power of 2, such that I can rewrite the problem as follows,
$ {\sum_{i = 1}^{15}}{{\log}_{2}{i}} = {({2}^{0})(0) + ({2}^{1})(1) + ({2}^{2})(2) + ({2}^{3})(3)}$

So, I can see this pattern so far--however, it looks like with just a bit of tweaking I can pull an nth-summation formula out of this pattern but so far no luck.

I'll keep looking over this problem and post what I come with later.

In the mean time, any other suggestions are welcome.

Thanks,

-APSStudent

$ \sum n2^n$ has several ways of being evaluated, some more slick than others :)

My favorite one is "summation by parts," which says $ \sum u\Delta v \equal{} uv \minus{} \sum v_{\plus{}1}\Delta u$. Here, $ \Delta u \equal{} u(n\plus{}1)\minus{}u(n)$ and the subscript $ \plus{}1$ means to use $ v(n\plus{}1)$ instead of $ v(n)$. See if you can figure out how to apply it here.

[quote="Hamster1800"]$ \sum n2^n$ has several ways of being evaluated[/quote]

Methinks you can divide by two and integrate right? That would be fairly slick in the end...

well, $ \lfloor \log_2{1}\rfloor \equal{} 0$
$ \lfloor \log_2{2}\rfloor \equal{} 1$
$ \lfloor \log_2{3}\rfloor \equal{} 1$
$ \lfloor \log_2{4}\rfloor \equal{} 2$

so you see a pattern, for the sum being:

1  $ 2^3 \minus{} 2^2 \equal{} 2$  terms
2  $ 2^4 \minus{} 2^3 \equal{} 4$ terms
3 there will be 8 terms
4 16 terms

with some simple calculation we see that

$ \displaystyle\sum_{i\equal{}1}^{7}i\times2^i \equal{} 1538$ and
$ \displaystyle\sum_{i\equal{}1}^{8}i\times2^i \equal{} 3586$

so the rest of the terms are 8, and there have already been 255 terms because

$ \displaystyle\sum_{i\equal{}0}^{n}2^i \equal{} 2^{n\plus{}1}\minus{}1$

so our answer is just $ \frac{1994\minus{}1538}{8} \plus{} 255 \equal{} \fbox{312}$. idk if its the right answer.

Hey,

[quote="caffeineboy"]
Well not exactly all too slick but: $ \lfloor \log_{2}n \rfloor + 1$ is the number of digits of n in binary. That establishes your pattern. Now if you count the sum in a different way, you can get an answer.
[/quote]

Hmm, I didn't notice that, I'll look over the pattern and see how I can count the sum. Thanks for the suggestion.

[hide="Here is my progress so far"]
First let's generalize the problem for a given sum, $ {S}$,
$ {{\lfloor}{{\log_{2}}1}{\rfloor} + {\lfloor}{{\log_{2}}2}{\rfloor} + {\lfloor}{{\log_{2}}3}{\rfloor} + {\cdot}{\cdot}{\cdot} + {\lfloor}{{\log_{2}}n}{\rfloor}} = {S}$

Where,
$ {S \in \mathbb{M}}$
$ {\mathbb{M} = \{0, 1, . . . , \infty\}}$

Which can be rewritten as,
$ {\sum_{i = 1}^{n}}{{\lfloor}{\log}_{2}{i}{\rfloor}} = {S}$

Then again rewritten as,
${ {\sum_{i = 1}^{n}}{{\lfloor}{\log}_{2}{i}{\rfloor}} = {\sum_{j = 0}^{m}}{{j}{{2}^{j}}} + {C}}$

Where,
$ {m \in \mathbb{M}}$
$ {\mathbb{M} = \{0, 1, . . . , \infty\}}$

$ {C \in \mathbb{M}}$
$ {\mathbb{M} = \{0, 1, . . . , \infty\}}$

Note that we want $ {C}$ to be postive since the original summation has no negative terms.
In order to find $ {n}$ we want to get as close as possible or equal to $ {S}$ by collecting terms of powers of two without going over.
The reason we do not want to go over is that would result in the constant $ {C}$ being negative and therefore inaccurately
representing the original summation.
So the problem can now be rewritten as,
${ {\sum_{i = 1}^{n}}{{\lfloor}{\log}_{2}{i}{\rfloor}} = {\max{(}{\sum_{j = 0}^{m}}{{j}{{2}^{j}}}{)}} + {C}}$

Note from here the constant $ {C}$ can be reexpressed as,
$ {C} = {k(m + 1)}$

Where,
$ {k \in \mathbb{M}}$
$ {\mathbb{M} = \{0, 1, . . . , \infty\}}$
Note that here $ {k}$ represents the number of terms of $ {m + 1}$ needed to add to the summation, $ {\max{(}{\sum_{j = 0}^{m}}{{j}{{2}^{j}}}{)}}$ to reach the sum, $ {S}$.
So now we have,
${ {\sum_{i = 1}^{n}}{{\lfloor}{\log}_{2}{i}{\rfloor}} = {\max{(}{\sum_{j = 0}^{m}}{{j}{{2}^{j}}}{)}} + {{(}{k(m + 1)}{)}}}$

${ {\sum_{i = 1}^{n}}{{\lfloor}{\log}_{2}{i}{\rfloor}} = {\max{(}{\sum_{j = 0}^{m}}{{j}{{2}^{j}}}{)}} + {{k(m + 1)}}}$

From here it seems like the next step is to evaluate the summation,
$ {\sum_{j = 0}^{m}}{{j}{{2}^{j}}}$

However even if I evaluate the expression in terms of $ {m}$, I still then need to figure out some way of choosing $ {m}$ such that it will maximize,
$ {\sum_{j = 0}^{m}}{{j}{{2}^{j}}}$

and then still find $ {k}$ in order to find $ {n}$.

So from here I am not sure how to proceed, any ideas?
[/hide]
Thanks,

-APSStudent


calculus
integration
function
calculus computations

Suppose two functions $ f(x)\equal{}x^4\minus{}x,\ g(x)\equal{}ax^3\plus{}bx^2\plus{}cx\plus{}d$ satisfy $ f(1)\equal{}g(1),\ f(\minus{}1)\equal{}g(\minus{}1)$.

Find the values of $ a,\ b,\ c,\ d$ such that $ \int_{\minus{}1}^1 (f(x)\minus{}g(x))^2dx$ is minimal.

[quote="makar"]

$ \equal{} 2\left(\frac {32}{35} \plus{} \frac {8b^2}{15} \minus{} \frac {128b}{105} \plus{} \frac {8a^2}{105}\right)$

[/quote]

The part seems to be incorrect. :(

[quote="makar"][quote="kunny"]Suppose two functions $ f(x) \equal{} x^4 \minus{} x,\ g(x) \equal{} ax^3 \plus{} bx^2 \plus{} cx \plus{} d$ satisfy $ f(1) \equal{} g(1),\ f( \minus{} 1) \equal{} g( \minus{} 1)$.

Find the values of $ a,\ b,\ c,\ d$ such that $ \int_{ \minus{} 1}^1 (f(x) \minus{} g(x))^2dx$ is minimal.[/quote]

Let $ \ h(x) \equal{} f(x) \minus{} g(x) \equal{} x^4 \minus{} ax^3 \minus{} bx^2 \minus{} (c \plus{} 1)x \minus{} d$

$ h( \minus{} 1) \equal{} 0\implies 1 \plus{} a \minus{} b \plus{} (c \plus{} 1) \minus{} d \equal{} 0$ and $ \ h(1) \equal{} 0\implies 1 \minus{} a \minus{} b \minus{} (c \plus{} 1) \minus{} d \equal{} 0$

$ \implies d \equal{} 1 \minus{} b$ and $ \ c \equal{} \minus{} 1 \minus{} a$

$ \implies h(x) \equal{} x^4 \minus{} ax^3 \minus{} bx^2 \plus{} ax \plus{} b \minus{} 1$

$ \implies \int _{ \minus{} 1}^{1}(h(x))^2\ dx \equal{} 2\int _{0}^{1}(x^4 \minus{} bx^2 \plus{} b \minus{} 1)^2 \plus{} (ax \minus{} ax^3)^2\ dx$

$ \equal{} 2\int _{0}^{1}((x^4 \minus{} 1) \minus{} b(x^2 \minus{} 1))^2 \plus{} a^2(x \minus{} x^3)^2\ dx$

$ \equal{} 2\int _{0}^{1}(x^8 \minus{} 2x^4 \plus{} 1) \plus{} b^2(x^4 \minus{} 2x^2 \plus{} 1) \minus{} 2b(x^6 \minus{} x^4 \minus{} x^2 \plus{} 1) \plus{} a^2(x^6 \minus{} 2x^4 \plus{} x^2)\ dx$

$ \equal{} 2\left(\frac {32}{45} \plus{} \frac {8b^2}{15} \minus{} \frac {128b}{105} \plus{} \frac {8a^2}{105}\right)$

$ \equal{} \frac {16}{105}a^2 \plus{} \frac {16}{15}\left(b \minus{} \frac {8}{7}\right)^2 \plus{} \frac {64}{2205}$

$ \implies \min \int_{ \minus{} 1}^1 (f(x) \minus{} g(x))^2dx \equal{} \frac {64}{2205}$ for $ a \equal{} 0,$ and $ \ b \equal{} \frac {8}{7}$

$ \implies \boxed{\boxed{a \equal{} 0,\ b \equal{} \frac {8}{7},\ c \equal{} \minus{} 1,\ d \equal{} \minus{} \frac {1}{7}}}$

[hide="Thanks"]Thanks kunny I fixed it[/hide][/quote]

That's correct. :lol:

[quote="kunny"][hide][quote="makar"][quote="kunny"]Suppose two functions $ f(x) \equal{} x^4 \minus{} x,\ g(x) \equal{} ax^3 \plus{} bx^2 \plus{} cx \plus{} d$ satisfy $ f(1) \equal{} g(1),\ f( \minus{} 1) \equal{} g( \minus{} 1)$.

Find the values of $ a,\ b,\ c,\ d$ such that $ \int_{ \minus{} 1}^1 (f(x) \minus{} g(x))^2dx$ is minimal.[/quote]

Let $ \ h(x) \equal{} f(x) \minus{} g(x) \equal{} x^4 \minus{} ax^3 \minus{} bx^2 \minus{} (c \plus{} 1)x \minus{} d$

$ h( \minus{} 1) \equal{} 0\implies 1 \plus{} a \minus{} b \plus{} (c \plus{} 1) \minus{} d \equal{} 0$ and $ \ h(1) \equal{} 0\implies 1 \minus{} a \minus{} b \minus{} (c \plus{} 1) \minus{} d \equal{} 0$

$ \implies d \equal{} 1 \minus{} b$ and $ \ c \equal{} \minus{} 1 \minus{} a$

$ \implies h(x) \equal{} x^4 \minus{} ax^3 \minus{} bx^2 \plus{} ax \plus{} b \minus{} 1$

$ \implies \int _{ \minus{} 1}^{1}(h(x))^2\ dx \equal{} 2\int _{0}^{1}(x^4 \minus{} bx^2 \plus{} b \minus{} 1)^2 \plus{} (ax \minus{} ax^3)^2\ dx$

$ \equal{} 2\int _{0}^{1}((x^4 \minus{} 1) \minus{} b(x^2 \minus{} 1))^2 \plus{} a^2(x \minus{} x^3)^2\ dx$

$ \equal{} 2\int _{0}^{1}(x^8 \minus{} 2x^4 \plus{} 1) \plus{} b^2(x^4 \minus{} 2x^2 \plus{} 1) \minus{} 2b(x^6 \minus{} x^4 \minus{} x^2 \plus{} 1) \plus{} a^2(x^6 \minus{} 2x^4 \plus{} x^2)\ dx$

$ \equal{} 2\left(\frac {32}{45} \plus{} \frac {8b^2}{15} \minus{} \frac {128b}{105} \plus{} \frac {8a^2}{105}\right)$

$ \equal{} \frac {16}{105}a^2 \plus{} \frac {16}{15}\left(b \minus{} \frac {8}{7}\right)^2 \plus{} \frac {64}{2205}$

$ \implies \min \int_{ \minus{} 1}^1 (f(x) \minus{} g(x))^2dx \equal{} \frac {64}{2205}$ for $ a \equal{} 0,$ and $ \ b \equal{} \frac {8}{7}$

$ \implies \boxed{\boxed{a \equal{} 0,\ b \equal{} \frac {8}{7},\ c \equal{} \minus{} 1,\ d \equal{} \minus{} \frac {1}{7}}}$

[hide="Thanks"]Thanks kunny I fixed it[/hide][/quote][/hide]

That's correct. :lol:[/quote]

Hi kunny, I am not full satisfied by solution although it is correct. I used brute force method. Is there any alternate and elegant solution?

Here is my solution:

From $ f(1) \equal{} g(1),\ f( \minus{} 1) \equal{} g( \minus{} 1)$, we can set $ f(x) \minus{} g(x) \equal{} (x^2 \minus{} 1)(x^2 \plus{} px \plus{} d)$.

$ \therefore I \equal{} \int_{ \minus{} 1}^1 (f(x) \minus{} g(x))^2\ dx \equal{} \int_{ \minus{} 1}^1 (x^2 \minus{} 1)^2(x^2 \plus{} d \plus{} px)^2\ dx$

$ \equal{} \int_{ \minus{} 1}^1 (x^2 \minus{} 1)^2(x^2 \plus{} d)^2 dx \plus{} 2p^2\int_{ \minus{} 1}^1 x^2(x^2 \minus{} 1)^2 dx$

$ \because 2px(x^2 \plus{} d)\ \text{is an odd function}$

$ \geq \int_{ \minus{} 1}^1 (x^2 \minus{} 1)^2(x^2 \plus{} d)^2\ dx\ (\text{the equality when}\ p \equal{} 0)$

$ \equal{} d^2\int_{ \minus{} 1}^1 (x^2 \minus{} 1)^2\ dx \plus{} 2d\int_{ \minus{} 1}^1 x^2(x^2 \minus{} 1)^2\ dx \plus{} \int_{ \minus{} 1}^1 x^4(x^2 \minus{} 1)^2\ dx$

$ \equal{} \frac {16}{15}d^2 \plus{} \frac {32}{105}d \plus{} \frac {16}{315}$

$ \equal{} \frac {16}{15}\left(d \plus{} \frac {1}{7}\right)^2 \plus{} \frac {64}{2205}$.

Thus $ I$ is maximal when $ d \equal{} \minus{} \frac 17$ and $ p \equal{} 0\Longleftrightarrow f(x) \minus{} g(x) \equal{} (x^2 \minus{} 1)\left(x^2 \plus{} 0\cdot x \minus{} \frac 17\right)$

$ \Longleftrightarrow g(x) \equal{} f(x) \minus{} \left(x^4 \minus{} \frac 87x^2 \plus{} \frac 17\right) \equal{} \frac 87x^2 \minus{} x \minus{} \frac 17$, yielding

$ \boxed{a \equal{} 0,\ b \equal{} \frac 87,\ c \equal{} \minus{} 1,\ d \equal{} \minus{} \frac 17}$


$ \frac{x}{100}\equal{}\frac{66}{20}\Rightarrow 20x\equal{}6600\Rightarrow x\equal{}330$


Many private colleges seem to request students to take at least two subject tests for admission. However, 99% kids from my school who got accepted to private colleges didn't even take subject tests or AP tests. What do you think is happening here? Do colleges understand your situation if your school does not teach toward subject tests? I wasn't going to take subject tests but it looks like many people who go to private colleges take subject tests and I'm wondering whether I should do this or not.

Thanks for your inputs.

[quote]However, 99% kids from my school who got accepted to private colleges didn't even take subject tests or AP tests.[/quote]

wow, what high school do you go to?

i would recommend taking subject tests cause some schools specfically require 3 subject tests before your app is complete and they consider you.

Some colleges expect all applicants to submit SAT II Subject Test scores.

http://talk.collegeconfidential.com/showthread.php?t=229607

Not having those test scores in time probably is one of the biggest issues that keep students out of such colleges.

Don't count on your high school course to prepare you for an SAT II Subject Test. Yes, do learn your high school course thoroughly, but also read independently on that subject, and practice with [url=http://amazon.com/s/ref=nb_ss_gw/002-5307435-7696005?url=search-alias%3Daps&field-keywords=The+Official+Study+Guide+for+All+SAT+Subject+Tests]released genuine tests[/url] so you know what to expect, and what fine points of the subject to learn. As usual, the test doesn't expect you to be perfect, just well prepared. Typically a test-taker can miss several items (either leaving them blank or making a mistake on them) and still get the peak scaled score of 800.

So generally we should have completed all the SAT II tests we plan to take by January or so of junior year?

[quote="joml88"]No...I would try to take them at the end of your junior year so you'll be at your peak for the tests you're taking (assuming you were in that class your junior year).[/quote]
When do people usually apply to college then?

[quote="rnwang2"]When do people usually apply to college then?[/quote]

Here in the United States, the usual pattern is for a twelfth-grade student in high school (a "high school senior") to prepare applications during the autumn, usually submitting them around New Year Day. (Stanford University is famous for tricking applicants each year with its earlier deadline, which if I remember correctly is December 15th.) Colleges are supposed to notify applicants of admission decisions by April 1st, and applicants who are admitted to more than one college are supposed to indicate which college they choose to enroll at by May 1st. All of what I just wrote refers to the "regular admission" cycle, and there are some variations from this pattern for "early action" or "early decision" colleges and also for "rolling admission" colleges. But, in general, students in the United States apply to college DURING their last school year of secondary school.

When I lived in Taiwan, and I think still today, the date of college admission testing there was the first week of July, and decisions are announced soon after that, almost entirely on the basis of test scores. So students have graduated from high school (usually) by the time they take the most decisive step to apply to college.

tokenadult, aren't quite a few application deadlines Nov. 30? I know that's the case for the UC's. New Year's Day sounds too late.

There may be more regular admission deadlines in the autumn than I have personally encountered. Recalling another state in another region, it might be important to check deadlines for state universities, which in some states have a very large number of applications and possibly quite early deadlines. There are supposed to be [url=http://www.nacacnet.org/NR/rdonlyres/9A4F9961-8991-455D-89B4-AE3B9AF2EFE8/0/SPGP.pdf]NACAC rules[/url] that somewhat standardize these deadlines within certain spans of dates during the United States school year calendar, but, yes, check the deadlines for any college you are at all interested in BEFORE your last year of high school begins, and plan when you have to have your application turned in.


linear algebra
matrix
vector
linear algebra unsolved

Let $ p$ an odd prime, and $ V$ a vectorial space over $ Z/pZ$. Let $ u\in \text{GL}\left(V\right)$, and look at $ u$ as a permutation. Then prove that its signature is $ (\frac {\det u}{p})$ where $ (\frac {a}{p})$ is the Legendre symbol.

Indeed, very beautiful.

Clearly, every transvection is a square of another transvection, so every transvection performs an even permutation. Now, if the determinant of a matrix is $d$, then that matrix can be transformed into $\mbox{diag}(1,1,\ldots,1,d)$ through multiplication with transvections, and since we have established that transvections are even, it means that $\mbox{diag}(1,1,\ldots,1,d)$ has the same sign as the original permutation. $\mbox{diag}(1,1,\ldots,1,d)$ also has the same sign as the permutation determined by the map $x\mapsto dx$ in $\mathbb Z_p$, or, in other words, the problem has been reduced to one-dimensional vector spaces over $\mathbb Z_p$.

Let $g$ be a primitive root modulo $p$. $d$ is a square modulo $p$ iff $d=g^{2k}$. The map $x\mapsto gx$ is an even cycle (a cycle of length $p-1$), so it's an odd permutation. On the other hand, $x\mapsto g^2x$ is the square of a map, so it's an even permutation. It's clear now that the maps $x\mapsto g^{2k+1}x$ are odd and the maps $x\mapsto g^{2k}x$ are even, as desired.

That was the idea, grobber. Good job!!! This problem is really among my favourites.  :)


geometry
rotation
conics
ellipse
calculus
integration
linear algebra

Calculuate the area of the area of the region bounbed by the curve
$ ax^{2}+bxy+cy^{2}= 1$
if the curve is an ellipse.

Note: "if the curve is an ellipse" can be expressed more algebraically as $ 4ac-b^{2}>0,a>0.$

Basic idea: set up an integral - easiest if it's a double integral - and make [i]linear[/i] changes of variables until it turns into the integral needed to compute the area of some circle. Knowing some linear algebra might help in choosing the substitutions, but you can brute-force it with the technique of completing the square in any case.


I don't really get how to solve this problem.

Sorry if it's too easy for MC. I wasnt sure where to post it. :oops:

Are you sure you labeled it right?
I think you might have mislabled it.
If not, then sorry, I really don't know how to do it either.

[quote="LadyKn1ght"]Since it is triangle BCE I am supposing the bottom of the E was chopped off somehow in the picture.

BCE is an equlateral triangle and BEFG is a square, so BC = BG.
So if you draw a line from G to C, BCG is an isosceles triangle.
angle CBE = 60
angle EBG = 90
angle CBG = 150
So angle BCG = 15
60-15 = 45, so angle GCE is 45 degrees.[/quote]

Yeah the E was messed up. Thanks for the help. :)


analytic geometry
geometry
cyclic quadrilateral

Points $C$ and $D$ lie on opposite sides of line $AB$. Let $M$ and $N$ be the centroids of $\triangle ABC$ and $\triangle ABD$ respectively. If $AB=25,BC=24,AC=7,AD=20,BD=15$, compute $MN$.

(Try not to put it in the coordinate plane.)

[hide="Hint"]First, find the length of $CD$.
Is there any relationship between $CD$ and $MN$?
[/hide]

I'm not sure if you made a typo in the question, but is $AC$ supposed to equal a value?

edit, I'm going to assume it's 7 because it probably is

[hide]
If I call the median on $AB$ "$E$", I get $ME = NE = \frac{25}{6}$

The only other thing I notice is that $\bigtriangleup MNE \cong \bigtriangleup CDE$. Because $\frac{NE}{DE} = \frac13, MN = \frac{CD}{3}$.

and now I get stuck; any tips?

[/hide]

Yeah I guess I hit the backspace key instead of =... :blush:

@Pocket Sand:
[hide]
Cyclic quadrilateral...
[hide]
PTOLEMY! :lol:
[/hide]
[/hide]

[hide]
I looked up Ptolemy's Theorem and it says the sum of the products of 2 opposite sides in a cyclic quadrilateral equal the product of the diagonals. I guess this has a purpose if you actually know one of the diagonals, making it a lot shorter than the diagonal formula.

so in the case, we have
$\\7 \cdot 15 + 20 \cdot 24 = 105 + 480 = 585 = 25x \\ \\ x = \frac{117}{5}$

but we want one third of this value, so $\boxed{MN = \frac{39}{5}}$

and just to check that I applied this formula correctly, I'll plug these into the diagonal formula as well:
$\\ \sqrt{ \frac{(20 \cdot 15 + 7 \cdot 24)(20 \cdot 24 + 7 \cdot 15)}{20 \cdot 7 + 15 \cdot 24}} \\ = \sqrt{ \frac{(468)(585)}{500}} = \sqrt{ \frac{2^2 \cdot 3^4 \cdot 5 \cdot 13^2}{2^2 \cdot 5^3}} = \sqrt{ \frac{3^4 \cdot13^2}{5^2}} = \frac{3^2 \cdot 13}{5}$
we want one third of this value, so once again, $\boxed{MN = \frac{39}{5}}$
[/hide]

while i don't like analytic geometry, it is a very easy solution

Yeah, it is very easy with analytic geometry but it doesn't really teach you anything...

well seeing the $CD$ thing was pretty important.... so i guess thats something we could get out of this problem... and recognizing that $ABCD$ is important too

uhh $MN$ isnt on $CD$, but $CD$ is parallel to $MN$ and from there you get similar triangles


algebra
function
domain
inequalities
real analysis
calculus
calculus computations

can someone please explain to me some of the following concepts.

1) what is meant big O and little O notation and how can it be used?

2) for $\alpha>0$ there exist a $\beta>0$ such that $x_{1},x_{2}\in{A}$ ,where $A$ is the domain of the function (or part of it), satisyf $|x_{1}-x_{2}|<\beta$, then $|f(x_{1})-f(x_{2})|<\alpha$

how would one use this to prove that $f(x)=\frac{1}{x}$ is uniformly continuous on $[2,1000]$ (this is a problem in ACoPS)

"O and o" is a [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=31517]sticky topic[/url] in this forum.

Part (2) is a definition of a uniformly continuous function: given a positive number $\alpha$, you must produce some positive number $\beta$ so that... In practical terms, you mess around with $|f(x_{1})-f(x_{2})|$ (replacing it with a large quantity if needed) until it turns into some algebraic expression involving $|x_{1}-x_{2}|$, but not $x_{1}$ or $x_{2}$ separately. Like this: \[\left|\frac{1}{x_{1}}-\frac{1}{x_{2}}\right|=\left|\frac{x_{2}-x_{1}}{x_{1}x_{2}}\right|=\frac{|x_{1}-x_{2}|}{x_{1}x_{2}}\] The numerator looks good, but I still have $x_{1}$ and $x_{2}$ in the denominator. However, these numbers are in the interval $[2,1000]$, which should help. Remember: you goal is to produce an inequality \[|f(x_{1})-f(x_{2})|\le \text{some function of }|x_{1}-x_{2}|\]

The function $f(x)=\frac1x$ is Lipschitz on $[2,1000]$:
$|\frac{1}{x_{1}}-\frac{1}{x_{2}}|\leq \frac{|x_{1}-x_{2}|}{x_{1}x_{2}}\leq \frac14 |x_{1}-x_{2}|$, hence uniformly continous; Let $\alpha>0$ and choose $\beta < 4\alpha$.. then as long $|x_{1}-x_{2}|<\beta$ we have $|f(x_{1})-f(x_{2})|<\alpha$

where did you get the $\frac{1}{4}|x_{1}-x_{2}|$ from?

From the inequalities $x_{1}\ge 2$ and $x_{2}\ge 2$.

ok.
thanks for clearing that up for me.  :)


topology
advanced fields
advanced fields unsolved

Please help me with this problem because I really don't know how to solve it :(
It's like this:
The set of all total orders of natural numbers is countable
Prove or disprove.

I know that it's false statement but I don't know how to disprove it

Thx you for help
Doma

Every permutation of $\mathbb{N}$ induces a distinct total order - in fact, a well-ordering - on $\mathbb{N}.$ This is a subset of the total orders, so if we can prove that the number of such permutations is uncountable, we will be done. The proof is a version of that old standby, the Cantor diagonal argument.

Suppose that we have a sequence $f_n$ of permutations of $\mathbb{N}.$ We will construct a permutation $g$ that does not equal any of the $f_n.$

Let $g(1)$ be the smallest $k\ne f_1(1).$

After that, let $g(n)$ be the smallest $k\not\in\{g(1),g(2),\dots,g(n-1),f_n(n)\}.$

We have constructed $g$ to be one-to-one. Is it onto? The only way that a particular $j$ could avoid being chosen as a value of $g$ would be for $f_n(n)=j$ for all large enough $n.$ It should be clear in this case that our original list is not all of the permutations. Otherwise, $g$ cannot be any of the $f_n$ because $g(n)\ne f_n(n).$ Either way, our original list does not contain all of the permutations.

Alternatively, we can do this:

The set of ordinal numbers corresponding to sets which are at most countable is a well-ordered set (every set of ordinal numbers is well-ordered), so there is an ordinal number representing it. This ordinal number must then be larger than any ordinal number in the set, i.e. it's larger than all ordinal numbers which are at most countable, meaning that it cannot be countable.

There are uncountably many permutations (and therefore orderings) which, for each $n$, either exchange $2n-1$ and $2n$, or leave them in place.

thanks a lot but I have another one to solve:

Let (X,q) be a metric space and let A be a subset of X. Prove that int (int(A)) = int(A)
where int(A) means the interior of the set A

thx for your help


inequalities
geometry
inradius
LaTeX
triangle inequality
area of a triangle
Heron\u0027s formula

$a,b,c$ are sides of a triangle.
What is the lower and upper bound of
$\frac {a}{b+c} + \frac {b}{a+c} + \frac {c}{a+b}$

This is a pretty classical problem. In fact, if a, b, c are the sidelengths of a triangle, then

$\frac32\leq\frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b}<2$.

[i]Proof.[/i] The inequality $\frac32\leq\frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b}$ is the well-known Nesbitt inequality. What remains to prove is the inequality $\frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b}<2$. Actually, since b + c > a by the triangle inequality, we have (b + c) + (b + c) > (b + c) + a; in other words, 2 (b + c) > a + b + c. Similarly, 2 (c + a) > a + b + c and 2 (a + b) > a + b + c. Thus,

$\frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b}=\frac{2a}{2\left(b+c\right)}+\frac{2b}{2\left(c+a\right)}+\frac{2c}{2\left(a+b\right)}$
$<\frac{2a}{a+b+c}+\frac{2b}{a+b+c}+\frac{2c}{a+b+c}=2$,

and thus the proof is complete.

Note that the bounds are sharp: We have $\frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b}=\frac32$ if a = b = c, i. e. if our triangle is equilateral, and we have $\frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b}\to 2$ if b = c and $a\to 0$.

  Darij

I recently met an exercise in which the upper-bound has been slightly improved, namely,

$\frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b}\leq 2-\frac{r}{R}$

where $r,R$ are the inradius and circumradius. In this way, the bound is sharp even for an equilateral triangle.

I have tried to use the Ravi transformation : there exist $x,y,z>0$ such that $a=y+z$, $b=z+x$, $c=x+y$. In conjunction with Heron's formula, we have

$\frac{r}{R}=\frac{8S^2}{abc(a+b+c)}=\ldots=\frac{4xyz}{(x+y)(y+z)(z+x)}$.

Then, the inequality to be proven reads

$\frac{y+z}{2x+y+z}+\frac{z+x}{x+2y+z}+\frac{x+y}{x+y+2z}+ \frac{4xyz}{(x+y)(y+z)(z+x)}\leq 2$.

Next, I computed the sum of the first three terms, so as to have

$\frac{N(x,y,z)}{(2x+y+z)(x+2y+z)(x+y+2z)} + \frac{4xyz}{(x+y)(y+z)(z+x)}\leq 2$

where $N()$ stands for the numerator. Using the AM-GM inequality, we can minorize the denominator by

$(2x+y+z)(x+2y+z)(x+y+2z)\geq 8(x+y)(y+z)(z+x)$

so that now, we have to prove

$\frac{N(x,y,z)+32xyz}{8(x+y)(y+z)(z+x)}\leq 2$

Since $N$ is an intricated expression, I'm stuck here :fool: Could somebody give me a hint ?

[quote="Monique"]I recently met an exercise in which the upper-bound has been slightly improved, namely,

$\frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b}\leq 2-\frac{r}{R}$

where $r,R$ are the inradius and circumradius.[/quote]

Argh... Is it me who is so stupid or is this "exercise" a rather challenging problem? Here is the only solution I could find:

If $\Delta$ is the area and $s=\frac{a+b+c}{2}$ is the semiperimeter of triangle ABC, then well-known formulas yield $r=\frac{\Delta}{s}$ and $R=\frac{abc}{4\Delta}$, so that $\frac{r}{R}=\frac{\left(\frac{\Delta}{s}\right)}{\left(\frac{abc}{4\Delta}\right)}=\frac{4\Delta^2}{sabc}$. But by Heron's formula, $\Delta^2=s\left(s-a\right)\left(s-b\right)\left(s-c\right)$. Thus, $\frac{r}{R}=\frac{4s\left(s-a\right)\left(s-b\right)\left(s-c\right)}{sabc}=\frac{4\left(s-a\right)\left(s-b\right)\left(s-c\right)}{abc}=\frac{2\left(s-a\right)\cdot 2\left(s-b\right)\cdot 2\left(s-c\right)}{2abc}$. But 2 (s - a) = 2s - 2a = (a + b + c) - 2a = b + c - a, and similarly 2 (s - b) = c + a - b and 2 (s - c) = a + b - c. Hence, $\frac{r}{R}=\frac{\left(b+c-a\right)\left(c+a-b\right)\left(a+b-c\right)}{2abc}$. Hence, the inequality that we have to prove,

$\frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b}\leq 2-\frac{r}{R}$,

is equivalent to

$\frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b}\leq 2-\frac{\left(b+c-a\right)\left(c+a-b\right)\left(a+b-c\right)}{2abc}$.

We have to prove this inequality for a, b, c being the sidelengths of a triangle; however, this inequality holds, more generally, for arbitrary positive real numbers a, b, c. In order to prove this, it is enough to note that

$\left(2-\frac{\left(b+c-a\right)\left(c+a-b\right)\left(a+b-c\right)}{2abc}\right)-\left(\frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b}\right)$
$=\frac{\sum_{\text{cyc}} a^3\left(b+c\right)\left(a-b\right)\left(a-c\right) + \sum_{\text{cyc}} b^2c^2\left(b-c\right)^2}{2abc\left(b+c\right)\left(c+a\right)\left(a+b\right)}\geq 0$.

Hereby, we have used $\sum_{\text{cyc}} b^2c^2\left(b-c\right)^2\geq 0$, what is trivial, and $\sum_{\text{cyc}} a^3\left(b+c\right)\left(a-b\right)\left(a-c\right)\geq 0$, what can be proven as follows:

Since we are dealing only with symmetric inequalities, we can WLOG assume that $a\geq b\geq c$. Define $x=a^3\left(b+c\right)$, $y=b^3\left(c+a\right)$, $z=c^3\left(a+b\right)$. Then, $a\geq b$ yields $ca\geq bc$, so that $ca+ab\geq ab+bc$. In other words, $a\left(b+c\right)\geq b\left(c+a\right)$. Multiplying this with $a^2\geq b^2$ (what again follows from $a\geq b$), we get $a^3\left(b+c\right)\geq b^3\left(c+a\right)$. In other words, $x\geq y$. Similarly, from $b\geq c$, we can deduce $y\geq z$. Hence, $x\geq y\geq z$. Now, by the Vornicu-Schur inequality (Lemma 1 in http://www.mathlinks.ro/Forum/viewtopic.php?t=24555 post #9), applied to the six nonnegative reals a, b, c, x, y, z satisfying $a\geq b\geq c$ and $x\geq y\geq z$, we get $\sum_{\text{cyc}} x\left(a-b\right)\left(a-c\right)\geq 0$; in other words, $\sum_{\text{cyc}} a^3\left(b+c\right)\left(a-b\right)\left(a-c\right)\geq 0$. And this completes our proof.

Does anybody see something less complicated?

  Darij

i´m not sure but i think there could be a solution using this identity:

CosA + CosB +CosC= r/R + 1

could someone maybe pursue?? this i dont think even i did try find a soltuion im not so good at algebra :blush:

[quote="darij grinberg"]Argh... Is it me who is so stupid or is this "exercise" a rather challenging problem?[/quote] Thank you very much for solving. I like your solution  :)  It is rather "natural", not as "complicated" as you think, although perhaps not totally "elementary" (we need to recognize Vornicu-Schur's inequality, but well, this should be OK in the Olympiads section :D ).

I did it: we can suppose that a+b+c=6 so we have to prove:
   \frac{a}{6-a} +\frac{b}{6-b}+\frac{c}{6-c}+\frac{4(3-a)(3-b)(3-c)}{abc}\leq2
  Then we define x=ab+bc+ca ,y=abc so the inequality is:
      \(3y-10x +54)^2\leq\28x^2 -\54*8x+\54^2
  we have  simply  9<x<=12,y<=8 .Then the inequality is given
 (sorry ,i have just learnt Latex)

Can't we use ?
$0 < \frac{r}{R} \le \frac{1}{2}$

Long time ago, I gave an ugly proof of the following:

[quote="Monique"]I recently met an exercise in which the upper-bound has been slightly improved, namely,

$ \frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b}\leq 2-\frac{r}{R}$

where $ r,R$ are the inradius and circumradius.[/quote]

Here is a better proof I found some time later, attached as a PDF file.

  Darij

Sorry for reviving this old topic after 4 years(!), but I have got some kind of a solution after trying this for sometime. However, it's not as elegant as Darij's and I did not want to start a new topic for this old inequality.

Again I apologise for reviving this old topic.

The following boxed inequality is sharper : $\boxed{\boxed{\ \frac a{b+c}+\frac b{c+a}+\frac c{a+b}\ \le\ \frac 52-\frac {ab+bc+ca}{a^2+b^2+c^2}\ }}\ \le\ 2-\frac rR$ .

You can see [url=http://www.artofproblemsolving.com/blog/48838][color=darkblue][b]here[/b][/color][/url] a proof for the refined version based on identities expressed in terms of $Rrs$.

[quote="Monique"]I recently met an exercise in which the upper-bound has been slightly improved, namely,

$ \frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b}\leq 2-\frac{r}{R}$

where $ r,R$ are the inradius and circumradius.[/quote]
This inequality is equivalent to :
$s^2 \le 6R^2+2Rr-r^2$ which follows from Gerretsen's Inequality : $s^2 \le 4R^2+4Rr+3r^2$ since $R \ge 2r$


5. For each description below, construct and verify an example of a linear transformation satisfying the description. Write down the standard matrix for each of you examples.

...

c) A linear transformation $ T: \mathbb{R}^3 \rightarrow \mathbb{R}^3$ such that the image of T is the plane $ x \plus{} y \plus{} z \equal{} 0$

I've managed to do parts a) and b) but am stuck here on c), I don't know what to do. Any help would be great, thanks!

Set $ T\equal{}\left(\begin{array}{ccc} 1 & 1 &0\\ \minus{}1 & \minus{}1 & \minus{}1\\ 0 & 0 & 1\end{array}\right)$. Since $ (1,1,1)T\equal{}(0,0,0)$ we have $ Im(T)\subseteq\{x\plus{}y\plus{}z\equal{}0\}$ and since $ rank(T)\equal{}2$ the set inclusion is an identity.


vector
linear algebra
linear algebra theorems

Let $ n$ be a positive integer and $ F$ a field. Let $ W$ be the set of all vectors $ (x_1,\ldots, x_n)$ in $ F^n$ such that $ x_1\plus{}\cdots\plus{}x_n\equal{}0$.
(a) It is proved.  :)
(b) Show that the dual space $ W^{\star}$ of $ W$ can be 'natuarally' identified with the linear functionals
$ f(x_1,\ldots, x_n)\equal{}c_1 x_1\plus{}\cdots\plus{}c_n x_n$
on $ F^n$ which satisfy $ c_1\plus{}\cdots\plus{}c_n\equal{}0$.

I know that every linear functional has the form $ f(x_1,\ldots, x_n)\equal{}c_1 x_1\plus{}\cdots\plus{}c_n x_n$. But what should I mean under 'naturally'?

Thanks.

Each $ f \in W^*$ can be extended to $ \hat{f} \in (F^n)^*$, so we can express $ f(x_1, \ldots, x_n) = c_1 x_1 + \ldots c_n x_n$, where $ (x_1, \ldots, x_n) \in W^*$.  Note that $ f(x_1, \ldots, x_n) = (c_1 + a)x_1 + \ldots (c_n + a)x_n$ for any $ a \in F$ because $ (x_1, \ldots, x_n) \in W$.  We can then choose $ a$ so that $ (c_1 + a) + \ldots + (c_n + a) = 0$.  In fact, this correspondence of writing $ f(x_1, \ldots, x_n) = c_1 x_1 + \ldots c_n x_n$ where $ c_1 + \ldots + c_n = 0$ is made clear by the following exact sequence:

You have $ 0 \to W \to F^n \xrightarrow{g} F \to 0$ where $ g$ is nothing but $ g(x_1, \ldots, x_n) = x_1 + \ldots + x_n$.  Then taking dual and keeping in mind that over a field, Hom is exact (because split exact..), $ 0 \to F^* \xrightarrow{g^*} (F^n)^* \to W^* \to 0$ is exact again.  If we identify $ F^*$ and $ F$ in the natural way, as well as $ F^n$ and $ (F^n)^*$, then $ g^*$ is just the map identifying $ F$ as a subspace of $ F^n$ by $ a \to (a, a, \ldots, a)$.  So $ \boxed{W^* \cong (F^n)^* / F^* \overset{identify}{=} F^n / F}$  (by the natural identification), where $ F$ sits inside $ F^n$ as a linear span of $ (1, 1, \ldots, 1)$.  Each element of $ W^*$ then can be represented by $ (c_1, \ldots, c_n) \in F^n$ where $ c_1 + \ldots c_n = 0$ and vice versa.


number theory
relatively prime
Divisibility Theory

Find all triples $(l, m, n)$ of distinct positive integers satisfying \[{\gcd(l, m)}^{2}= l+m, \;{\gcd(m, n)}^{2}= m+n, \; \text{and}\;\;{\gcd(n, l)}^{2}= n+l.\]

The problem doesn't actually require $ m,n,l$ to be different. Anyway, this doesn't change anything.

I will use $ (m,n)$ for $ \gcd(m,n)$ in this solution.
Let $ (m,n) \equal{} a$, $ m \equal{} am'$. From $ m \plus{} n \equal{} a^2$, we get $ n \equal{} a^2 \minus{} am'$. In a similar way, let $ (m,l) \equal{} b$, $ m \equal{} bm''$ and $ l \equal{} b^2 \minus{} bm''$. Because $ (m',a \minus{} m') \equal{} 1$ and $ (m'',b \minus{} m'') \equal{} 1$ we have $ (a,m') \equal{} (b,m'') \equal{} 1$. From $ am' \equal{} bm''$ we deduce the existence of $ 4$ positive integers $ x,y,z,t$ pairwise coprime, such that $ a \equal{} xy$, $ m' \equal{} zt$, $ b \equal{} xz$, $ m'' \equal{} yt$. This is really a well-known fact; anyway, for showing it, start by taking $ \dfrac ab \equal{} \dfrac{m''}{m'} \equal{} \dfrac yz$, with $ (y,z) \equal{} 1$.
Then $ n \equal{} a^2 \minus{} am' \equal{} x^2y^2 \minus{} xyzt$ and $ l \equal{} b^2 \minus{} bm'' \equal{} x^2z^2 \minus{} xyzt$. We have $ (n,l) \equal{} x(xy^2 \minus{} yzt,xz^2 \minus{} yzt) \equal{} x(xy \minus{} zt,xz \minus{} yt)$, because $ (y,xz^2) \equal{} (z,xy^2) \equal{} 1$.
Then $ (n,l)^2 \equal{} n \plus{} l$ rewrites as $ x^2(xy \minus{} zt,xz \minus{} yt)^2 \equal{} x^2(y^2 \plus{} z^2) \minus{} 2xyzt$. This means $ 2xyzt$ is divisible by $ x^2$. But $ (x,yzt) \equal{} 1$, from where $ x|2$.
[i]Case 1[/i]
$ x \equal{} 2$. Because we're working with positive integers, $ xy \minus{} zt$ and $ xz \minus{} yt$ are positive, so $ 2y > zt$ and $ 2z > yt$, from where $ t \equal{} 1$. Then $ y^2 \plus{} z^2 \minus{} yz \equal{} (2y \minus{} z,2z \minus{} y)^2$. Suppose $ p^k\parallel{}(2y \minus{} z,2z \minus{} y)$, where $ p$ is a prime number. Then $ p^k|4y \minus{} 2z \plus{} 2z \minus{} y$, or $ p^k|3y$. Similarly $ p^k|3z$. Since $ (y,z) \equal{} 1$, $ p \equal{} 3$ and $ k \equal{} 1$ or $ p$ doesn't exist at all. This means $ y^2 \plus{} z^2 \minus{} yz\in\{1,9\}$. The equation $ y^2 \plus{} z^2 \minus{} yz \equal{} 1$ has the only solution $ y \equal{} z \equal{} 1$. This case leads to $ m \equal{} n \equal{} l \equal{} 2$. Let's analyze $ y^2 \plus{} z^2 \minus{} yz \equal{} 9$. WLOG, let $ y\ge z > 0$ and let $ y \equal{} z \plus{} k$. Then the last equation becomes $ z^2 \plus{} zk \plus{} k^2 \equal{} 9$. The only solutions are $ z \equal{} 3$ and $ k \equal{} 0$. But then $ y \equal{} z \equal{} 3$ and $ (y,z)\neq1$.
[i]Case 2[/i]
$ x \equal{} 1$. Again, because we're working with positive integers, we must have $ xy > zt$ and $ xz > yt$, or $ y > zt$ and $ z > yt$, from where $ 1 > t$, impossible.

The only such numbers are $ m \equal{} n \equal{} l \equal{} 2$.

Also see page 99 (or 100) \ problem 38.\ of this book:

[url]http://www.unl.edu/amc/a-activities/a4-for-students/problemtext/mc97-98-01feb.pdf[/url]

Another method. Suppose that l is smaller than m and n.

Then 2l < l+m = gcd(l,m)^2. Similarly 2l < l + n = gcd(l,n)^2.

Multiply together and square rooting, we get that 2l < gcd(l,m)gcd(l,n).

It is well know that gcd(u,v)lcm(u,v)=uv for all integers u,v.
Thus gcd(l,m)gcd(l,n)=gcd(gcd(l,m),gcd(l,n))lcm(gcd(l,m),gcd(l,n)). The first term in this product is gcd(l,m,n). The second is a factor of l. Thus gcd(l,m)gcd(l,n) is a factor of gcd(l,m,n)l.

Since 2l < gcd(l,m)gcd(l,n) we see that 2 < gcd(l,m,n).

Now let z = gcd(l,m,n). z^2 is a factor of (gcd(l,m)^2)=l+m. z^2 is also a factor of m+n and l+n. Thus z^2 is a factor of (l+m)+(l+n)-(m+n)=2l. Similarly z^2 is a factor of 2m and 2n. Thus z^2 is a factor of gcd(2m,2l,2n)=2z. Thus z is a factor of 2.

CONTRADICTION

[quote="Vinxenz"]$ gcd(l,m)^t\equal{}l\plus{}m, gcd(m,n)^t\equal{}m\plus{}n, gcd(n,l)^t\equal{}n\plus{}l,t>2$ has no solutions in N.[/quote]
Can somebody solve the problem above?

[quote="Vinxenz"]$ gcd(l,m)^t=l+m, gcd(m,n)^t=m+n, gcd(n,l)^t=n+l,t>2$ has no solutions in N.[/quote]

Letting $l=gx,m=gy,n=gz$ with $g=\gcd(l,m,n)$ so that $\gcd(x,y,z)=1$, we have
\[g^t|\gcd(l,m)^t=l+m=g(x+y)\implies g^{t-1}|x+y,\]etc. So $g^{t-1}|(x+y)+(x+z)-(y+z)=2x$, etc., whence $g^{t-1}|2$ and $g=1$. Thus letting $u=\gcd(y,z),v=\gcd(z,x),w=\gcd(x,y)$, we have $x=x'vw$, $y=y'wu$, and $z=z'uv$, where the triples $(x',y',z')$ and $(u,v,w)$ contain pairwise relatively prime elements, with $u^{t-1}=y'w+z'v$, $v^{t-1}=z'u+x'w$, and $w^{t-1}=x'v+y'u$. Now assume for the sake of contradiction that $p|\gcd(x',u)$ for a prime $p$. Then we find from our equations that $p|v,w$, a contradiction. Similarly, if some prime $q|\gcd(x',v)$, the fact that $\gcd(x',y')=\gcd(x',z')=1$ gives us $q|u,w$, another contradiction.

We conclude that $x',y',z',u,v,w$ are all pairwise relatively prime. Note that
\[(x',y',z')=\left(\frac{v^t+w^t-u^t}{2vw},\frac{w^t+u^t-v^t}{2wu},\frac{u^t+v^t-w^t}{2uv}\right).\]With some computing power, we find that $t=6$ actually has some solutions (there don't seem to be any under 9000 for $3\le t\le5$, although $t=4$ seems to have many examples where one of $x',y',z'$ is an integer and the other two are half-integers); the smallest example is
\begin{align*}
u &= 65 = 5\cdot13\\
v &= 72 = 2^3\cdot3^2\\
w &= 73\\
x' &= 20474639 = 2029\cdot10091\\
y' &= 9213809 = 11\cdot837619\\
z' &= 6773369 = 109\cdot62141\\
l &= gx = x'vw = 2^3\cdot3^2\cdot73\cdot2029\cdot10091=107614702584\\
m &= gy = y'wu = 5\cdot11\cdot13\cdot73\cdot837619=43719523705\\
n &= gz = z'uv = 2^3\cdot3^2\cdot5\cdot13\cdot109\cdot62141=31699366920.
\end{align*}
Whoops I just wasted a few hours on this.


For $a,b,c$ positive real numbers, prove that

$\frac{a^2+ab}{b+c}+\frac{b^2+bc}{c+a}+\frac{c^2+ca}{a+b}\ge a+b+c$

Here's my solution:

First substitute, [tex] b+c=x, a+c=y, a+b=z [/tex]:
[tex]
\iff \sum (x+y-z)\frac{y}{z} \geq x+y+z\\
\iff \sum \dfrac{y^2}{z} + \sum \dfrac{xy}{z} \geq 2x+2y+2z
[/tex]
But by Rearrangement we get:
[tex]
\sum \frac{y^2}{z} \geq x+y+z\\
\sum \frac{xy}{z} \geq x+y+z
[/tex]


Vasc, why do we need a hint? Cauchy-Schwarz works very fine here.

[quote="sbos"]If $x,y,z$ are positive and $x+y+z=1$, prove that
\[\sqrt{xy(1-z)}+\sqrt{yz(1-x)}+\sqrt{zx(1-y)}\leq\sqrt{\frac{2}{3}}.\][/quote]\[\left(\sqrt{xy(1-z)}+\sqrt{yz(1-x)}+\sqrt{zx(1-y)}\right)^2\leq \] \[\leq(xy+yz+zx)((1-z)+(1-y)+(1-x))=2(xy+yz+zx)\leq \frac{2}{3}.\]

You are right, Harazi and Myth. But my hint can be used to show the following stronger ineq

$\sum (xy-xyz)^{2/3} \le \frac{\sqrt[3]4}{3}$.

[quote="Vasc"]If $ x,y,z$ are nonnegative real numbers such that  $ x \plus{} y \plus{} z \equal{} 1$, then

$ \sum (yz \minus{} xyz)^{2/3} \le \frac {\sqrt [3]4}{3}$.[/quote]
$ \sum{\left[yz\left(\frac {y \plus{} z}{2}\right)\right]^{\frac {2}{3}}}\leq\sum\frac {y^2 \plus{} 4yz \plus{} z^2}{6} \equal{} \frac {(x \plus{} y \plus{} z)^2}{3}$,

which is obviously true for

$ \left(y^2 \plus{} 4yz \plus{} z^2\right)^3 \minus{} 54y^2z^2(y \plus{} z)^2$

$ \equal{} (y \minus{} z)^2\left(y^4 \plus{} 14y^3z \plus{} 24y^2z^2 \plus{} 14z^3y \plus{} z^4\right)\geq 0$.


modular arithmetic
search
number theory
least common multiple

1) Find the smallest positive integer which when divided by 10 leaves a remainder of 9, when divided by 9 leaves a remainder of 8, by 8 leaves a remainder of 7, etc. down to where, when divided by 2, it leaves a remainder of 1.

2) IF a set of markers is placed in rows of 4 each, there are 2 markets left over; if in rows of 5 each, there are 3 left over; and if in rows of 7 there are 5 left over. What is the smallest number of markers that the set could contain?

[hide="1"]We have the systems
\begin{eqnarray*}x&\equiv& 9{\pmod{10}}\\ x&\equiv& 8{\pmod 9}\\ x&\equiv& 7{\pmod 8}\\ &\cdots& \\ x&\equiv& 1{\pmod 2}\\ \end{eqnarray*}
Notice when we add one to each sides of all the equations, we get:
\begin{eqnarray*}x+1&\equiv& 10 \equiv 0{\pmod{10}}\\ x+1&\equiv& 9 \equiv 0{\pmod 9}\\ x+1&\equiv& 8 \equiv 0{\pmod 8}\\ &\cdots& \\ x+1&\equiv& 2 \equiv{\pmod 2}\\ \end{eqnarray*}
We can see that $x+1$ is a multiple of ${1, 2, 3, 4, \ldots 9, 10}.$ We wish to find the smallest value of $x$, so our answer is $\text{lcm}{1, 2, 3, 4, 5, \ldots 9, 10}-1=2520-1=\boxed{2519}$[/hide]

[quote="Glen Mann"]ragnarok, basicly you find $lcm(1,2,3,4,5,6,7,8,9,10)$ right? which seems like it would be awefully hard to do..

do you have some method?[/quote]
Yes. Consider 8. If the number we search for is divisible by 8, we don't need to worry about 4 and 2. The same goes for 9 and 3. Since we already have a 3 and 2 in our product, we dont need to wrry about the six. Also, if we have a 5, we dont need to worry about the 10 because we already have another 2. 7 shares no common factors with any other number in the set, so it must be included in our product. The desired number is 9*8*7*5=2520.

[hide="practically same thing"]Except it is -2 mod each number.  Thus, the answer is $\text{LCM}(4,5,7)-2=138$.[/hide]


calculus
integration
geometry
perimeter
quadratics
greatest common divisor
symmetry

The side lengths of a right triangle are each an integral number of units. If one of
the legs is 13 units, what is the perimeter of the triangle?

A pythagorean triple with 13 as a leg is 13-84-85
So the perimeter is 13+84+85=182

if it was me, i would do one of two things:

1) if i have a calculator; make a program to find the other leg for which the hypotenuse is an integer

2) if i don't have a calculator; use the fact that any pythagorean triple can be written as $ {2kmn, k(m^2 \minus{} n^2, k(m^2 \plus{} n^2)}$ for integers $ k, m,$ and $ n$.

[hide="alternatively"] It's well known that primitive Pythagorean Triples can be represented as $ (2mn, m^2\minus{}n^2, m^2\plus{}n^2)$ where m>n and m and n are natural numbers. Since 13 is prime, we know that the triple is primitive and it must be equal to $ m^2\minus{}n^2$. Also since 13 is prime we have $ (m\minus{}n)(m\plus{}n)\equal{}13\rightarrow{m\plus{}n\equal{}13, m\minus{}n\equal{}1}$ so m=7, n=6. Thus the other two sides are 84 and 85, so the perimeter is 182.[/hide]

I just noticed something!!!

Note this: $ 84 \plus{} 85 \equal{} 13^2$

$ 13 \plus{} 12 \equal{} 5^2$

$ 5 \plus{}4 \equal{} 3^2$

IDK why that works, but it seems to.

[quote="mathemagician1729"]Um xp, is there like a proof of that relationship, or is it something that you need to memorize?[/quote]

Certainly; plug it in and bash it :P

If you're talking about how you would find that formula, that's a bit complex. If I recall, it was covered in chapter 24 of Volume 2.

[hide="derivation"] So you have $ a^2\plus{}b^2\equal{}c^2$. We're assuming that this is a primitive triple, since we can find all the others using the primitive ones. Clearly, a and b cannot both be even, as then c would be even and the triple wouldn't be primitive. They also cannot both be odd; taking (mod 4), the left hand side is congruent to 2 (mod 4), which is not a quadratic residue (mod 4). Thus, a and b are of the opposite parity.

Now, we claim that a, b, and c have no common prime factor.
[hide="proof"] We have already stated that this triple is primitive, so gcf(a, b, c)=1. Now assume that gcf(a, c)=d and is greater than 1. Then d divides the right hand side of our equation, so it must also divide the left. Thus d must also divide b. However, that means this triple is not primitive, which is a contradiction. So, gcf (a, c)=1, and by symmetry, gcf(b, c)=1. If gcf(a, b)=d and is greater than one, than by the same reasoning, it must also divide c, which gives another contradiction. We're done now.[/hide]

Without loss of generalization, let a be even. Now we rearrange the equation so $ a^2\equal{}(c\plus{}b)(c\minus{}b)$. Since c and b are both odd and relatively prime, both (c+b) and (c-b) are even and have no common factor other than 2. Thus, both (c+b) and (c-b) must be perfect squares themselves. Let $ c\plus{}b\equal{}2m^2$ and $ c\minus{}b\equal{}2n^2$. We now find $ c\equal{}m^2\plus{}n^2$ and $ b\equal{}m^2\minus{}n^2$ and that $ a^2\equal{}4m^2n^2\rightarrow{a\equal{}2mn}$.

This gives us our formula, since $ (a, b, c)\equal{}(2mn, m^2\minus{}n^2, m^2\plus{}n^2)$.[/hide]


Prove that, for a triangle $ ABC$,

$ \sin(\frac{A}{2})\cdot\sin(\frac{B}{2})\cdot\sin(\frac{C}{2}) \le \frac{1}{8}$.

The ineq. is equivalent to : $ \sqrt{\frac{(s\minus{}b)(s\minus{}c)}{bc}}\cdot\sqrt{\frac{(s\minus{}c)(s\minus{}a)}{ca}}\cdot\sqrt{\frac{(s\minus{}a)(s\minus{}b)}{ab}}\le \frac 18$

$ \Longleftrightarrow\ \frac{(s\minus{}a)(s\minus{}b)(s\minus{}c)}{abc}\le \frac 18\ \Longleftrightarrow\ (\minus{}a\plus{}b\plus{}c)(a\minus{}b\plus{}c)(a\plus{}b\minus{}c)\le abc$ , well-known .

What is the best way to prove that well-known inequality? (at least not well-known to me)... right off the top of my head I only found expanding the whole expression... is there a short-cut?

hello, substituting
$ a\equal{}y\plus{}z$
$ b\equal{}x\plus{}z$
$ c\equal{}x\plus{}y$
in
$ (\minus{}a\plus{}b\plus{}c)(a\minus{}b\plus{}c)(a\plus{}b\minus{}c) \le abc$
we get
$ (y\plus{}z)(x\plus{}z)(x\plus{}y)\geq8xyz$
and this is AM-GM.
Sonnhard.

You could also use [url=http://www.artofproblemsolving.com/Wiki/index.php/Jensen's_Inequality]Jensen's inequality[/url].

Let $ f(x)=\ln \sin x$, so by Jensen's we have,

\begin{eqnarray*}
\dfrac{f\left(\dfrac{A}{2}\right)+f\left(\dfrac{B}{2}\right)+f\left(\dfrac{C}{2}\right)}{3}&\le& f\left(\dfrac{A+B+C}{6}\right)\\
\dfrac{\ln \sin\left(\dfrac{A}{2}\right)+\ln \sin\left(\dfrac{B}{2}\right)+\ln \sin \left(\dfrac{C}{2}\right)}{3}&\le& f(30^{\circ})\\
\dfrac{\ln \sin\left(\dfrac{A}{2}\right)\cdot \sin \left(\dfrac{B}{2}\right)\cdot \sin \left(\dfrac{C}{2}\right)}{3}&\le& \ln \sin 30^{\circ}\\
\dfrac{\ln \sin\left(\dfrac{A}{2}\right)\cdot \sin \left(\dfrac{B}{2}\right)\cdot \sin \left(\dfrac{C}{2}\right)}{3}&\le& \ln \dfrac{1}{2}\\
\ln \sin\left(\dfrac{A}{2}\right)\cdot \sin \left(\dfrac{B}{2}\right)\cdot \sin \left(\dfrac{C}{2}\right)&\le&\ln \dfrac{1}{2^3}\\
\ln \sin\left(\dfrac{A}{2}\right)\cdot \sin \left(\dfrac{B}{2}\right)\cdot \sin \left(\dfrac{C}{2}\right)&\le&\ln \dfrac{1}{8}\\
\sin\left(\dfrac{A}{2}\right)\cdot \sin \left(\dfrac{B}{2}\right)\cdot \sin \left(\dfrac{C}{2}\right)&\le&\dfrac{1}{8}
\end{eqnarray*}

Also

The following inequalities are true:

\[ \sin \frac{\alpha}{2} \leq \frac{a}{b\plus{}c}\]

\[ \sin \frac{\beta}{2} \leq \frac{b}{a\plus{}c}\]

\[ \sin \frac{\gamma}{2} \leq \frac{c}{b\plus{}a}\]

Thus , multiply to obtain:

\[ \sin \frac{\alpha}{2}\cdot \sin \frac{\beta}{2} \cdot  \sin \frac{\gamma}{2} \leq \frac{a}{b\plus{}c}\cdot \frac{b}{a\plus{}c} \cdot\frac{c}{b\plus{}a} \leq \frac{abc}{8abc}\equal{}\frac{1}{8}\]


function
calculus
derivative
real analysis
real analysis unsolved

This question was on our recent qualifying exams (which I didn't write), and I found a solution but it seems too complicated.  Does anyone have a shorter one?

Let $ f$ be a differentiable real valued function with $ f(0) \equal{} 0$ which satisfies $ f'(x) > f(x)$ for all $ x\in\mathbb{R}$.  Prove that $ f(x) > 0$ for all $ x > 0$.

[hide]Use the fact that $ f'(0) > 0$ and find an interval $ I \equal{} (0,\epsilon)$ with $ f(x) > f'(0)/2$ on $ I$.  Then consider $ u \equal{}\inf\{t\in f^{\minus{}1}(\{0\}): t >\epsilon\}$.  If it is empty, we're done, otherwise, by compactness, $ u$ is contained in $ f^{\minus{}1}(\{0\})\cap [\epsilon,\infty]$.  Note that $ f > 0$ on $ [\epsilon,u]$ but $ f'$ is less than zero somewhere on $ [\epsilon,u]$ (by the mean value theorem).  This establishes a contradiction.

I guess it isn't a tough solution to find but it seems like there should be something simpler.  I tried considering auxillary functions like $ \exp(\minus{}x)f(x)$ and so forth, but couldn't get anywhere.
[/hide]

Your idea of considering $ e^{\minus{}x}f$ looks good to me.  We have
\[ (e^{\minus{}x}f)' \equal{} e^{\minus{}x}f'\minus{}e^{\minus{}x}f > 0.\]
Thus $ e^{\minus{}x}f$ is strictly increasing.  In particular, $ e^{\minus{}x}f(x) > e^{\minus{}0}f(0) \equal{} 0$ for all $ x > 0$.  Thus $ f(x) > 0$ for all $ x > 0$.

I came up with my solution yesterday but didn't think of taking $ e^{\minus{}x}f(x)$ until I was in the shower this morning.  Unfortunately I am not good at taking derivatives in the shower and added a minus sign so I thought that $ e^{\minus{}x}f(x)$ was strictly [i]decreasing[/i]!.

I think that there is a moral to this anecdote but I am not sure what it is :(

Yeah the first thought that came to my mind was to consider the number $ \eta \equal{}\inf\{ t > 0\mid f(t) \equal{} 0\}$. Obviously due to continuity $ f(\eta) \equal{} 0$. If $ \eta > 0$, then for all $ x\in(0,\eta)$, $ f(x) > 0$, and also by Rolle's theorem, $ f'(c) \equal{} 0 > f(c)$ for some $ c\in (0,\eta)$, contradiction. If $ \eta \equal{} 0$, then, since $ f'(0) > 0$, there exists an $ \varepsilon > 0$ such that $ f'(x) > 0$ for all $ x\in[0,\varepsilon]$, and thus the function $ f$ is increasing on the interval $ [0,\varepsilon]$ so $ f(x) > f(0) \equal{} 0$, for all $ x\in (0,\varepsilon]$ contradicting the fact that $ \eta \equal{} 0$. Solved it in like 3 seconds in my head but the solution seems so much more complicated than the $ e^{\minus{}x}f(x)$ solution :D

[hide="My thought"]
by Lagranage's Mean Value theorem for every $ x,x > 0$ there exists a $ c_{1}\in (0,x)$ such that $ \frac{f(x)}{x}\equal{} f^{'}(c_{1}) > f(c_{1}) > c_{1}f(c_{2}) > c_{1}c_{2}f(c_{3})......>\prod_{i \equal{} 1}^{n}c_{i}f(c_{n\plus{}1})$
for some $ c_{i}\in (0,c_{i\minus{}1}) ,i > 1$
but since $ f^{'}(x) > 0$ hence there exists an interval suffieciently close to $ 0$ where $ f$ is positive so by the above formulation since $ x > 0$ we have $ f(x) > 0$[/hide]

[quote="blahblahblah"]I think that there is a moral to this anecdote but I am not sure what it is :([/quote]Maybe don't differentiate in showers?  :lol:


A palace which has a square shape is divided into $ 2003 \times 2003$ square rooms of the same size which form a square grid. There might be a door between two rooms if they have a common side. The main gate leads to the room at the northwest corner. Someone has entered the palace, walked around for a while and upon returning to the room at the northwest corner for the first time, immediately left the palace. It turned out that this person visited each of the other rooms 100 times, except the room at the southeast corner. How many times did this person visit the room at the southeast corner?

[hide="Hint"]Divide the palace as a cheesboard with the northwest room and the southeast room painted as white.
Notice that the amount of crossing the inner edges of the white ones equals the amount of crossings of the black ones.
[/hide]


People say physics is the study of matter and energy, but also chemistry is the study of matter. So would you be a fact that both chemistry and physics both study matter. And physics is just more indepth meeting it goes over electrcity, mechanics, nuclear, atomic physics, and so on..Where as chemsitry just studies chemicla reactions and properties of chemicals??

If you really want to get technical, even English is the study of matter (a book or some other physical representation of matter).

In reality Physics studies matter (and energy, another form of matter) when there are no changes in the matter in a consistent way, at the atomic level.  Chemistry on the other hand is the study of matter and energy when the matter changes in a consistent way, at the atomic level.

There are other studies that overlap.  Mountain climbing is a specialzed form of Physics, so is balistics.  Explosives is a particular branch of chemistry.

On and on it goes, but one can easily see what area each focuses on even if the boundries between subjects are not subject to elegant definitions.


topology
geometry
3D geometry
sphere
rotation
geometric transformation
advanced fields

Find the orbit space $\mathbb{R}^n/SO(n)$, where $SO(n)$ acts on $\mathbb{R}^n$ naturally as linear operators.

Is it homeomorphic to $\mathbb R^+\cup\{0\}$(the nonnegative reals)?

[b]Lemma[/b] $SO(n)$ acts transitively on $S^{n-1}$ (the $n-1$ dimensional sphere; it embeds naturally in $\mathbb R^n$)

Proof: Let $x,y\in S^{n-1}$. If $x=y$, then $Ix=y$, where $I\in SO(n)$ is the identity map.
If $x\neq y$, then intersect with $S^{n-1}$ a 2 dimensional plane containing $x,O,y$, where $O$ is the origin of $\mathbb R^n$. (this plane is unique unless $x=\pm1y$)
The plane intersects $S^{n-1}$ in a circle. Now rotate $x$ over $y$ in this circle. This rotation can be extended to an element $T$ of $SO(n)$ by linearity with 0 on an orthogonal complement of the plane in $\mathbb R^n$. Now $T\in SO(n)$ and $Tx=y$.
Therefore $SO(n)$ acts transitively on $S^{n-1}$.
---------------------------------------------------------------------------------------------------
At least as a set, the orbit space can be identified to $\mathbb R_{\geq 0}$. You work out the topology!


function
limit
real analysis
real analysis unsolved

We consider the function $f:R->R$ with $f(x)=x^{5}+x$, $\forall x \in R$. If $g=f^{-1}(x)$ then compute $\displaystyle \lim_{x\to \infty} x^{a}(g(x)-\sqrt[5]{x})$ $\forall   a \in R$ .

[quote="Valentin Vornicu"]Lagrangia you can use \displaystyle command to make the $\lim_{x\to \infty}$ look nice :P  like this: $\displaystyle \lim_{x\to \infty}$ use \to for $\to$ :)[/quote]

okay! :D


Prove that if $a,b,c$ are the [i]sides of a triangle [/i]then the following inequality holds:
${\displaystyle\sum{\frac{a^3}{b^2}}\geq{\sum{\frac{a}{c}\cdot(a+b-c)}}}$.

Posted again by KMN .here
http://www.mathlinks.ro/Forum/viewtopic.php?t=65729

What is your solution ?


modular arithmetic
IMO Shortlist
number theory
Integer sequence
recurrence relation

* Notice that the numbers $ 11^{11}, 12^{12}, 13^{13}, 14^{14}$ are not of importance. They could be replace by any other number. Hence, we do not concentrate on the value of $ a_{14^{14}}$ itself but look for a different representation of it.

* Treat every element $ a_i$ as a vector with 3 weight $ a_1, a_2, a_3$. It means: rewrite $ a_i \rightarrow (\alpha_i , \beta_i, \gamma_i)$ with the property:
$ a_i \equal{} (\alpha_i , \beta_i, \gamma_i) \cdot (a_1, a_2, a_3)$ (the dot product of 2 real vectors)
Enumerating the sequence of vectors, we observe that: $ a_{7k\plus{}6} \equal{} (\minus{}1, 1, 0)$ for all $ k \in \mathbb{N}$. Proving this is just a routine.

* Also of interest is the sequence $ a_{7k}$:
(0,-1,1)
(2,-3,1)
(4,-5,1)
...
One easily get the pattern: $ a_{7k} \equal{} (2k\minus{}2 , \minus{} 2k\plus{}1 , 1)$ and the answer for the IMO shortlist problem is:

$ a_{14^{14}} \equal{} (4\times 14^{13} \minus{} 2)\times 11^{11} \minus{} (4\times 14^{13} \minus{} 1)\times 12^{12} \plus{} 13^{13}$

Final Remark: Generalization could be made to obtain the  formula for all $ a_n$.

[quote="mathangel"]* Treat every element $ a_i$ as a vector with 3 weight $ a_1, a_2, a_3$. It means: rewrite $ a_i \rightarrow (\alpha_i , \beta_i, \gamma_i)$ with the property:
$ a_i \equal{} (\alpha_i , \beta_i, \gamma_i) \cdot (a_1, a_2, a_3)$ (the dot product of 2 real vectors)
Enumerating the sequence of vectors, we observe that: $ a_{7k\plus{}6} \equal{} (\minus{}1, 1, 0)$ for all $ k \in \mathbb{N}$. Proving this is just a routine.
[/quote]
This claim is completely false.

[hide="My solution"]Let $c_n = |a_{n+1} - a_n|$. Then $c_1 = 12^{12} - 11^{11}$, $c_2 = 13^{13} - 12^{12}$, $c_3 = 11^{11}$, and $c_4 = 12^{12} - 2 \cdot 11^{11}$. Since $a_n = |a_{n-1} - a_{n-2}| + |a_{n-2} - a_{n-3}| = c_{n-2} + c_{n-3}$, $a_{n+1} = c_{n-1} + c_{n-2}$. Subtracting these two yields $c_n = |c_{n-1} - c_{n-3}|$ for all $n \geq 3$.

[b]Lemma[/b]: For any positive integer $i$, $\gcd(c_i, c_{i+1}, c_{i+2}) = 1$.
[i]Proof[/i]: Suppose that there exists some positive $i$ for which $\gcd(c_i, c_{i+1}, c_{i+2}) > 1$; consider the minimal such $i$. If $i > 1$, since $c_{i+2} = |c_{i+1} - c_{i-1}|$, $\gcd(c_i, c_{i+1}, c_{i+2}) | c_{i-1}$ as well, so $\gcd(c_{i-1}, c_i, c_{i+1}) > 1$, contradicting the minimality of $i$. Hence, $i = 1$; but it is clear that $\gcd(c_1, c_2, c_3) = 1$, so we have a contradiction.

Define a [i]sharp peak[/i] of $\{c_n\}$ to be some term $c_i$ such that $c_i > c_{i+1}, c_{i+2}$. We claim that for every sharp peak $c_p$, if $c_p > 2$, there exists some integer $i \leq 5$ such that $c_{p+i}$ is a smaller sharp peak. First, we will suppose that neither $c_{p+1}$ nor $c_{p+2}$ are 0, and show that we can find some $i \leq 3$ such that $c_{p+i}$ is a smaller sharp peak when $c_{p+1}, c_{p+2}$ are both nonzero.

If $c_{p+1} > c_{p+2}$, let $c_p = a + b + c$, $c_{p+1} = a + b$, and $c_{p+2} = a$, where $a$, $b$, and $c$ are nonnegative integers (with $a, b \neq 0.$) Then $c_{p+3} = b + c$. If $a > c$, then $a+b > a, b + c$. Since $a \neq 0$, $c_{p+1}$ is a sharp peak. If $a < c$, then $c_{p+3} = b + c$, $c_{p+4} = c - a$, and $c_{p+5} = |c - 2a|$. Since $0 \leq a < c < c + 2a$, $-c < -a < c - 2a < c$, giving $|c - 2a| < c < b + c$. In addition, $c - a < c < b + c$, so we have that $b + c > c - a, |c - 2a|$, so $c_{p+3}$ is a sharp peak. If $a = c$, then $a_{p+3} = a + b$, $a_{p+4} = 0$, and $a_{p+5} = a$; since $a + b > 0, a$, $a_{p+3}$ is a sharp peak.

If $c_{p+1} < c_{p+2}$, let $c_p = a + b + c$, $c_{p+1} = a$, and $c_{p+2} = a + b$, where $a$, $b$, and $c$ are nonnegative integers (with $a,b \neq 0$). It follows easily that $c_{p+3} = c$. If $a > c$, then $c_{p+4} = a - c$; since $a > c, a - c$, we have that $c_{p+1}$ is a sharp peak. If $a < c$, then $c_{p+4} = c - a$. If $a + b > c$, then $a + b > c > c - a$, so $c_{p+2}$ is a sharp peak. If $a + b \leq c$, then $c_{p+5} = |(c - a - b) - a| \leq a$, making $c_{p+3}$ a sharp peak. Finally, if $a = c$, then $c_{p+3} = a$ and $c_{p+4} = 0$; as $a + b > a, 0$, we have that $c_{p+2}$ is a sharp peak.

Finally, we consider the case in which $c_{p+1} = c_{p+2}$; here, let $c_p = a + b$ and $c_{p+1} = c_{p+2} = a$. Then $c_{p+3} = b$ and $c_{p+4} = |a - b|$. If $a > b$, then $a > b, |a - b|$, making $c_{p+2}$ a sharp peak. If $a < b$, then $c_{p+5} = |b - 2a|$. Also, $a < b < b + 2a$, so $-b < -a < b - 2a < b$, giving $|b - 2a| < b$. Hence, $c_{p+3} > c_{p+4}, c_{p+5}$, making $c_{p+3}$ a sharp peak. If $a = b$, then by our lemma, $\gcd(c_p, c_{p+1}, c_{p+2}) = \gcd(2a,a, a) = 1$, giving $a = 1$ and hence $c_p = 2$, which is a contradiction.

We now consider the case in which $c_{p+2}$ or $c_{p+1}$ is 0. In the former case, let $c_p = a$ and $c_{p+1} = b$.  Then $c_{p+2} = a$, and $c_{p+3} = c_{p+4} = |a - b|$. If $a = b$ or if $b = 0$, then our lemma tells us that $\gcd(c_p, c_{p+1}, c_{p+2}) = a = 1$, contradicting our assumption that $c_p > 2$. Hence, from what we have shown before, we can find some $i \leq 3$ such that $c_{p+2+i}$ is a sharp peak smaller than $a$ (since $c_{p+2} > c_{p+3}, c_{p+4}.)$ As $2 + i \leq 5$, our proof of this case is done.

If $c_{p+1}$ is 0, let $c_p = a$ and let $c_{p+2} = b$ (because of the above case, we may assume $b \neq 0$.) Then $c_3 = c_4 = a - b$. If $a - b < b$, then $c_{p+2} > c_{p+3}, c_{p+4}$, making $c_{p+2}$ a sharp peak. If $a \geq 2b$, $c_5 = a - 2b$ and $c_6 = b$. $a - b > a - 2b, b$, so $c_4 > c_5, c_6$, making $c_4$ a sharp peak.

$c_2$ is a sharp peak, so it follows from what we have shown that for some $M \leq 5(13^{13} - 12^{12}) < 14^{14} - 11$, we have that there is some sharp peak $c_M$ such that $c_M \leq 2$. By simply going through all possible cases, it can easily be shown that no matter what the values of $c_{M+1}$ and $c_{M+2}$ are, there will be some $M_0$ with $0 < M_0 - M < 10$ such that $c_{i+k}, c_{i+k+1}$, and $c_{i+k+2}$ are all 1. It follows trivially from here that whenever $m > M_0$, $c_m$ is either 1 or 0.

In particular, since $M_0 < 14^{14} - 3$, we have that $a_{14^{14}} = c_{14^{14}-2} + c_{14^{14}-3}$ is either 0, 1, or 2.

We will now show that $a_{14^{14}} = 1$. Taking the recurrence formula of $\{a_n\}$ mod 2 gives $a_n \equiv a_{n-1} + a_{n-3} \pmod{2}$. Simple computations reveal that $a_n \equiv a_{n+7} \pmod{2}$, giving $a_{14^{14}} \equiv a_7 \equiv 1 \pmod{2}$, from which it follows that $a_{14^{14}} = 1$.[/hide]

From IMO shortlist booklet:

Fro $n \ge 2$, define $s_n=\left | a_n-a_{n-1} \right |$. Then for $n\ge 5$, $a_n=s_{n-1}+s_{n-2}$ and $a_{n-1}=s_{n-2}+s_{n-3}$, and hence $s_n=\left | s_{n-1}-s_{n-3} \right |$. Because $s_n\ge 0$, it follows that if $\max\left \{ s_n,s_{n+1},s_{n+2} \right \}\le T$, then $s_m\le T$ for all $m\ge n$. In particular, the sequence $(s_n)$ is bounded. We now prove the following claim.

[b]Claim.[/b] If $\max\left \{ s_i,s_{i+1},s_{i+2} \right \}=T\ge 2$ for some $i$, then $\max\left \{ s_{i+6},s_{i+7},s_{i+8} \right \}\le T-1$.

[i]Proof. [/i] If this were not the case, then $\max\left \{ s_{j},s_{j+1},s_{j+2} \right \}=T\ge 2$ for $j=i,i+1,i+2,\ldots,i+6$. We show by contradiction that this cannot happen. If the claim were false, then for $j=i,i+1$, or $i+2$ the sequence $s_j,s_{j+1},s_{j+2},\ldots$would have the form \[ T,x,y,T-y,\ldots, \] with $0\le x,y\le T$, and $\max\left \{ x,y,T-y \right \}=T$. Hence either $x=T$ or $y=T$ or $y=0$. We consider each case:

(a) If $x=T$, then the sequence has the form $T,T,y,T-y,y,\ldots$ Because $\max\left \{ x,y,T-y \right \}=T$ we must have $y=0$ or $y=T$.

(b) If $y=0$, then the sequence takes the form $T,x,0,T,T-x,T-x,x,\ldots$ Hence $\max\left \{ x,T-x \right \}=T$, so $x=0$ or $x=T$.

(c) If $y=T$, then the sequence is $T,x,T,0,x,T-x,\ldots$ We then have $\max\left \{ x,T-x \right \}=T$, so $x=0$ or $x=T$.

In each case we find that both $x$ and $y$ must be either $0$ or $T$. In particular, $T$ must divide each of $s_i,s_{i+1}$ and $s_{i+2}$, which implies that $T$ divides $s_n$ for all $n\ge 2$. However, because $s_2=12^{12}-11^{11}$ and $s_4=11^{11}$ are relatively prime we have a contradiction. This establishes the claim.

Now let $M=14^{14}$ and $N=13^{13}$. From the bound $\max\left \{ s_2,s_3,s_4 \right \}\le N$, we use the claim to deduce inductively that $\max\left \{ s_{6N+2},s_{6N+3},s_{6N+4} \right \}=1$. In particular $s_n=0$ or $1$ for $n\ge 6N+2$. Hence $a_n=s_{n-1}+s_{n-2}$ may only take on the values $0, 1$ or $2$ when $n\ge M>6N+4$. In particular, $a_m=0,1$ or $2$. Now the recursion for $a_n$ implies that \[ a_n \equiv (a_{n-1}-a_{n-2})+(a_{n-2}-a_{n-3})  \pmod 2. \] From the initial values for $a_1,a_2$, and $a_3$ it can easiliy shown that modulo $2$, the sequence $(a_n)$ is periodic with period $7$, and that $a_$ is odd. Because $14^{14}$ is a multiple of $7$, we conclude that $a_M=1$.

[quote=TheUltimate123]Solved with [b]eisirrational[/b], [b]goodbear[/b], [b]Th3Numb3rThr33[/b].

The answer is 1. Instead consider the sequence \(x_n=|a_n-a_{n-1}|\), with the property that \(a_n=x_{n-1}+x_{n-2}\).

[color=red][b]Claim:[/b][/color]      \(x_n=|x_{n-1}-x_{n-3}|\).

[i]Proof.[/i]      We have \(a_n=x_{n-1}+x_{n-2}\) and \(a_{n-1}=x_{n-2}+x_{n-3}\), so     \[x_n=|a_n-a_{n-1}|=\big\lvert(x_{n-1}+x_{n-2})-(x_{n-2}+x_{n-3})\big\rvert=|x_{n-1}-x_{n-3}|.\] \(\blacksquare\)

[color=red][b]Claim:[/b][/color]      No three consecutive elements of \((x_n)\) share a common divisor.

[i]Proof.[/i]      If \(x_n\equiv x_{n+1}\equiv x_{n+2}\equiv0\pmod p\), we can verify via \(x_{n+2}=|x_{n-1}+x_{n-1}|\) that \(x_{n-1}\equiv0\pmod p\). Continuing backwards, the entire sequence is divisible by \(p\). However, \(x_2=12^{12}-11^{11}\) and \(x_4=11^{11}\) are relatively prime, contradiction. \(\blacksquare\)

[color=red][b]Claim:[/b][/color]      \(\max(x_n,x_{n+1},x_{n+2})\) is nonincreasing, and if \(\max(x_n,x_{n+1},x_{n+2})=A\ge2\), then \(\max(x_{n+6},x_{n+7},x_{n+8})\le A-1\).

[i]Proof.[/i]      The sequence is obviously nonincreasing, since \(x_{n+3}\le\max(x_n,x_{n+2})\). Let \(x_n=A\), \(x_{n+1}=B\), \(x_{n+2}=C\). We will show that if \(x_n=A\ge\max(B,C)\), then \(\max(x_{n+4},x_{n+5},x_{n+6})\le A-1\).

Assume \(\max(x_{n+4},x_{n+5},x_{n+6})=A\), so \(\max(B,C,x_{n+3})=A\) as well. This is only possible if \(A=B\), \(A=C\), or \(C=0\). Let's take the three cases:     [list]         [*]If \(A=B\), then the sequence runs \(A\), \(A\), \(C\), \(A-C\), \(C\), 0, \ldots. For \(\max(x_{n+3},x_{n+4},x_{n+5})=A\) to hold, either \(C=0\) or \(C=A\). By Claim 2, \(A=1\).         [*]If \(A=C\), then the sequence runs \(A\), \(B\), \(A\), 0, \(B\), \(A-B\), \ldots. For \(\max(x_{n+3},x_{n+4},x_{n+5})=A\) to hold, either \(B=0\) or \(B=A\). By Claim 2, \(A=1\).         [*]If \(C=0\), then the sequence runs \(A\), \(B\), 0, \(A\), \(A-B\), \(A-B\), \(B\), \ldots. In order for \(\max(x_{n+4},x_{n+5},x_{n+6})=A\) to hold,  either \(B=0\) or \(B=A\). By claim 2, \(A=1\).     [/list] \(\blacksquare\)

Let \(N=14^{14}\). Observe that \(\max(x_2,x_3,x_4)<13^{13}\), so for \(n>13^{13}/6\), we have \(x_n\in\{0,1\}\). Therefore \(a_N=x_{N-1}+x_{N-2}\in\{0,1,2\}\). It will suffice to show \(a_N\) is odd.

Indeed, the sequence \((a_n)\) modulo 2 begins 1, 0, 1, 0, 0, 1, 1, \(\ldots\) and repeats with period 7. Since \(7\mid N\), we have \(a_N\equiv a_7\equiv0\pmod2\). The end.[/quote]

Really cool proof, TheUltimate123, just wanted to note there is a typo at the end, I'm pretty certain it should be $a_{N}\equiv a_{7} \equiv 1\pmod2$.

Let $ a_1 = 11^{11}, \, a_2 = 12^{12}, \, a_3 = 13^{13}$, and $ a_n = |a_{n - 1} - a_{n - 2}| + |a_{n - 2} - a_{n - 3}|, n \geq 4.$ Determine $ a_{14^{14}}$.

We claim that $\boxed{a_{14^{14}} =1}$.

Let $x_n = | a_n - a_{n-1} | $ for each $n>1$. The condition becomes \[ a_n = x_{n-1}+ x_{n-2}\]

We see that \[x_n = |x_{n-1} - x_{n-3}|   \] because $x_n = |a_n - a_{n-1}| = |x_{n-1} - x_{n-3}|$.

Now let $y_n = \max(x_n, x_{n+1}, x_{n+2})$.

Claim 1: $y_n \ge y_{n+1}$ for all positive integers $n$ (i.e. the sequence $(y_i)$ is nonincreasing).
Proof:  Suppose $y_{n+1} > y_n$ for some $n$. This implies that $x_{n+3}$ is greater than $x_n, x_{n+1}, x_{n+2}$. Now, $x_{n+3} = |x_n - x_{n+2}|$ is either less than or equal to $x_n$ or less than or equal to $x_{n+2}$, which is a contradiction.   $\square$

Claim 2: $x_n, x_{n+1}, x_{n+2}$ cannot share a common integer factor greater than $1$ for $n\ge 2$.
Proof: If they did share a common factor of $d$, then $0\equiv x_{n+2} = |x_{n+1} + x_{n-1}|\pmod d$, so $d\mid x_{n-1}$. We may repeat such a process and get $d\mid x_2, x_3, x_4$.

We can now compute that $a_4 = 13^{13} - 11^{11}$, so $x_4 = 11^{11}$.

Therefore $d$ must be a multiple of $11$, so $d$ cannot divide $12^{12} - 11^{11}$, absurd. $\square$

Claim 3: For any positive integer $m>2$, if $y_m = y_{m+1}$, then either $\max(x_m, x_{m+1}, x_{m+2}) = x_{m+1}, x_{m+2} $, or $x_{m+2} =0$.
Proof: Suppose we have $x_m$ is the max (and $x_{m+1}, x_{m+2}$ are less than $x_m$), and $x_{m+2} \ne 0$. Then $x_{m+3} = |x_{m+2} - x_m|$ is less than $x_m$, so the $x_{m+1}, x_{m+2}, x_{m+3}$ are all less than $x_m$, absurd. $\square$

Claim 4: For any positive integer $n\ge 5$, if $y_{n-3} > 1$, then $y_{n-3} > y_{n+3}$.
Proof: Suppose we had $y_{n-3} = y_{n+3}$. Then \[y_{n-3} = y_{n-2} = \cdots = y_{n+2} = y_{n+3} = M\] for some $M>1$.

Since $y_{n-3} = y_{n-2}$, by claim 3, we have $x_{n-1} = 0, x_{n-2}  = M, $ or $x_{n-1} = M$.

Case 1: $x_{n-1} = 0$.
If $x_{n-3} = M$ and $x_{n-2} = a \le M$, then the sequence starting from $x_{n-3}$ is as follows:

\[\left(M, a, 0, M, |a-M|, |a-M|, ||a-M| - M|, \ldots, \right)\] By claim 2, $a$ cannot be equal to $0$ or $M$, so $0<|a-M| < M$. Since $y_{n+1} = M$, we must have $||a-M| - M| = M$, so $|a-M| \in \{0,2M\}$.

If $x_{n-3} = a\le M$ and $x_{n-2} = M$, then the sequence starting from $x_{n-3}$ is as follows:

\[\left( a, M, 0, a, |a-M|, |a-M| , \ldots, \right) \] By claim 2, $a$ cannot be equal to $0$ or $M$ . Since $y_n = M$, we must have $|a-M| = M$, so $a = 0$ or $2M$, both of which are clearly absurd.

Henceforth $x_{n-1} \ne 0$.

Case 2: $x_{n-2} = M$.
Let $a= x_{n-3}, b = x_{n-1}$ .

If $a = M$, then the sequence starting from $x_{n-3}$ is as follows (using the fact that $M > b$):
\[(M,M,b, M-b,b, \ldots, ),\] which is absurd since it implies $y_{n-1} =\max(b, M-b, b) < M$.

If $b = M$, then the sequence starting from $x_{n-3}$ is as follows (using the fact that $M > a$):

\[(a, M, M, M-a, a, M-a, \ldots, ),\]which is absurd since it implies $y_n = \max(M-a, a, M-a) < M$.

Now assume $a,b<M$. Note that $b>0$. The sequence is as follows:

\[(a, M, b, |a-b|, M - |a-b|, \ldots, ) ,\] since $y_{n-1}= M$, we have $a = b$. However, then the sequence is \[(a, M, a, 0, M, M-a, M-a,\]however by claim 3, since $y_{n+1} = y_{n + 2}$, we have $M-a = 0$ or $a=0$. However, if $a = 0$, we have an obvious contradiction by claim 2, so $a = M$, which is absurd.

Case 3: $x_{n-1} = M$.
Let $a = x_{n-3}, b = x_{n-2}$.

If $a =0 $, the sequence is \[(0, b, M, M, M-b, b, M-b, \ldots ),\]however since $y_{n+1} = M$, we have $\max(M-b, b, M-b) = 0$, so $M\mid b$, which is absurd because then $M$ divides $x_{n-3}, x_{n-2}, x_{n-1}$.

If $b=0$, the sequence is $(a, 0, M, M-a, M-a, \ldots, )$, however by claim three we get $a=0$ or $M - a = 0$, both of which are absurd by claim 2. Hence forth we assume that $a,b > 0$ and $b < M$.

Then the sequence starting from $x_{n-3}$ is as follows: \[ (a, b, M, M-a, |M-a-b| \ldots, ) \] However, by claim 3, since $y_{n-1} = y_n$, we have $|M  - a - b| = 0$ or $M - a = M$, the latter is impossible so $a + b = M$.

Now replacing $b$ with $M-a$ we get the sequence is \[(a, M-a, M, M-a, 0, M, a, a, M-a, \ldots, ),\] however then $y_{n+3} = \max(a, a, M-a) < M$, absurd.

We have exhausted all cases, so the claim is proven $\square$.

So $y_{n+6} \le y_n - 1$, and repeating this iteratively gives that $y_{n + 6k} \le y_n - k$ for $k\le y_n - 1$ and $y_{n + 6k} = 1$ for larger $k$.

Now, fix a $11^{11} < c<14^{14} - 2$ such that $y_c = 1$ (this is doable since $y_{2 + 6\cdot (11^{11} - 1) } = 1$)  . This means that each of $x_c, x_{c+1}, x_{c+2}$ are all either zero or one, but by claim 2, they cannot all be zero.

Therefore using the fact that $x_n = |x_{n-1} - x_{n-3} |$, we have $x_i \in \{0,1\}\forall i\ge c$, so then $a_n = x_{n-1} + x_{n-2}\in \{0,1,2\}$ for all $n>c + 2$.

Thus $a_{14^{14}}\in \{0,1,2\}$. However the parity of the sequence $(a_i)$ goes Odd, Even, Odd, Even, Even, Odd, Odd, and then repeats from there, so it has a period of $7$. Therefore $a_{14^{14}} \equiv a_7\pmod 2$, which is odd, therefore $a_{14^{14}} = 1$.

ding a ling

$a_{14^{14}} = 1$

$c_n=|a_{n+1}-a_n|$

$c_n=|c_{n-1}-c_{n-3}|$

Notice that it's bounded above and therefore there is some $N$ where $N$ appears arbitrarily many times in $\{c\}$ and is actually the maximum after a point $c_i$.

So take $c_j=N$ which has $j$ arbitrarily large. The idea is that $c_{k}\in \{0,N\}$ for $k>i+O(1)$ (im too lazy to work out the intricacies of the constant factor, it's irrelevant)

In any case, working backwards we find $c_i\equiv a_i\equiv 0\pmod N$ always. That means $N=1$. We can also find that $1110100$ is the eventual repeating string for $\{c\}$ by casework, thus $2211101$ is the repeating string for $\{a\}$. Now notice that $a_i\equiv 1\pmod 2$ where $7\mid i$, therefore the answer is $1$.


number theory
prime factorization
superior algebra
superior algebra unsolved

Find the degree of $ \mathbb{Q}(\sqrt{2},2^{1/3})$ and find a basis for it.

The maximum degree is obviously 6. The problem is that I cannot prove it is not less than 6. The minimum degree is obviously 3. This amounts to proving that $ \sqrt{2}$ is not contained in $ \mathbb{Q}(2^{1/3})$. On the contrary, assume it is. Then $ \sqrt{2}\equal{}a\plus{}b 2^{1/3} \plus{}c 2^{2/3}$ where a,b,c are rationals. Then you can square both sides and rearrange to get an equation of the form $ d\equal{}e 2^{1/3}\plus{}f 2^{2/3}$ where d,e,f are rational numbers. But then why is that a contradiction. This seems so obvious but how to prove it?

Just as an aside, does anyone know how to prove that if a is an integer (can you prove it for a rational even?) then the nth root of a $ a^{1/n}$ has degree n over $ \mathbb{Q}$?

It's easy to show that this field is actually $ \mathbb{Q}(\sqrt[6]{2})$, so you just need to show $ t^6\minus{}2$ irreducible over $ \mathbb{Q}$. Are you familiar with Eisenstein's Criterion?

[quote="scorpius119"]It's easy to show that this field is actually $ \mathbb{Q}(\sqrt [6]{2})$, so you just need to show $ t^6 \minus{} 2$ irreducible over $ \mathbb{Q}$. Are you familiar with Eisenstein's Criterion?[/quote]

I am familiar with Eisenstein's Criterion. I see why $ \mathbb{Q}(\sqrt [6]{2})$ will contain $ \mathbb{Q}(\sqrt [3]{2},\sqrt {2})$. But why will $ \mathbb{Q}(\sqrt [3]{2},\sqrt {2})$ contain $ \mathbb{Q}(\sqrt [6]{2})$? Oh wait--I see that also since $ \frac{1}{2^{1/3}}\times \frac{1}{2^{1/2}} \times 2 \equal{} 2^{1/6}$. Thanks.

What about my second question?

Eisenstein's criterion answers your second question in the case that at least one exponent in the prime factorization of $ a$ is $ 1$.  In other words, $ t^n \minus{} a$ is irreducible.  (The statement is false if $ a$ is a perfect $ d^{th}$ power, where $ d > 1$ and $ d | n$.)


prove that (secx-tanx)^2 = (1-sinx) / (1+sinx)

(secx-tanx)^2 = (1-sinx) / (1+sinx)

Left hand side:
sec^2-2sectan+tan^2
1/cos^2 - 2*(1/cos)*(sin/cos) + sin^2/cos^2
(1-2sin+sin^2)/cos^2

Right hand side

(1-sin)/(1+sin) * (1-sin)/(1-sin)
(1-2sin+sin^2)/(1-sin^2)
(1-2sin+sin^2)/cos^2

Same thing.

you're supposed to work with the left side so simplify
(secx-tanx)^2

the right hand side gives $ \frac {(1 \minus{} \sin x)^{2}}{\cos^{2} x}$ now take the $ \cos^{2} x$ to the left hand side

$ LHS\equal{}(\sec x\minus{}\tan x)^2$

$ \equal{}\left(\frac{1}{\cos x}\minus{}\frac{\sin x}{\cos x}\right)^2$

$ \equal{}\frac{(1\minus{}\sin x)^2}{\cos^2x}$

$ \equal{}\frac{(1\minus{}\sin x)^2}{1\minus{}\sin^2x}$

$ \equal{}\frac{(1\minus{}\sin x)^2}{(1\plus{}\sin x)(1\minus{}\sin x)}$

$ \equal{}\frac{1\minus{}\sin x}{1\plus{}\sin x}$


I have been wondered what is the Finnish word "samastuskuvaus" in English. The definition is the following:

Let $ X$ and $ Y$ be two topological spaces. The mapping is samastuskuvaus if $ f: X\to Y$ is a surjection and $ V\subset Y$ is open if and only if $ f^{\minus{}1}V\subset X$ is open, i.e. $ f$ coinduces the topology in $ Y$.


quadratics
algebra
polynomial
quadratic formula
linear equation

How would you guys attempt this problem:

Factor the expression $ a^{10}\plus{}a^5\plus{}1$.

I know it would be possible if the expression had the form:
$ a^{4k}\plus{}a^{2k}\plus{}1$, but obviously, this is not of that form. Thanks for all your help!

Let $ y \equal{} a^5$, then

$ a^{10} \plus{} a^5 \plus{} 1 \equal{} y^2 \plus{} y \plus{} 1$

Now we just use the quadratic formula to get

$ \left(y \minus{} \frac { \minus{} 1 \plus{} i\sqrt {3}}{2} \right) \left(y \minus{} \frac { \minus{} 1 \minus{} i\sqrt {3}}{2} \right) \equal{} \boxed{\big( a^5 \minus{} \frac { \minus{} 1 \plus{} i\sqrt {3}}{2} \big) \big( a^5 \minus{} \frac { \minus{} 1 \minus{} i\sqrt {3}}{2} \big) }$

These roots for $ a^5$ are also written as $ (1,120^{\circ})$ and $ (1, 240^{\circ})$.

These are the third roots of unity, but I don't know how to manipulate that fact to finish.

hello, we get
$ a^{10}\plus{}a^5\plus{}1\equal{}(a^2\plus{}a\plus{}1)(1\minus{}a\plus{}a^3\minus{}a^4\plus{}a^5\minus{}a^7\plus{}a^8)$
Sonnhard.

No, I meant to factor it with integer coefficients, not complex numbers. By the way Dr. Sonhard, can you post the way you did this, or did you try casework, like saying some linear equation is a factor, some quadratic is, etc.?

One trick is to note that if $ a \equal{} \omega$ is a primitive third root of unity then $ \omega^{10} \plus{} \omega^5 \plus{} 1 \equal{} \omega \plus{} \omega^2 \plus{} 1 \equal{} 0$, hence we immediately get divisibility by $ a^2 \plus{} a \plus{} 1$.  To show that this factorization is complete you should use the fact that $ a^{15} \minus{} 1$ has a well-known factorization into [url=http://en.wikipedia.org/wiki/Cyclotomic_polynomial]cyclotomic polynomials[/url].

I have the same as Sonnhard by dividing by $ a^{2} \plus{} a \plus{} 1$.

Oops, just seen t0rajir0u's post so I guess mine is redundant.


search
combinatorics proposed
combinatorics

How many ways can $ 8$ mutually non-attacking rooks can be placed on the $ 9 \times 9$ chessboard, colored as usual, so that all $ 8$ rooks are on squares of the same color?
[Two rooks attack each other if they are in the same row or column.]

Again, please do a search: many of these problems already exist on the forum:
http://www.artofproblemsolving.com/Forum/viewtopic.php?search_id=1852658024&t=190445
http://www.artofproblemsolving.com/Forum/viewtopic.php?search_id=1852658024&t=140383
(Those I got by searching for "rooks chessboard," but even a simple search for "Canada 2004" or variants would have turned up one of them.)


vector
linear algebra
matrix
algebra
polynomial
linear algebra unsolved

Prove that , if $ f$ is a bilinear form on a vector space $ V$ such that $ f(V,y)\equal{}0$ implies $ y\equal{}0$, then also $ f(x,V)\equal{}0$ implies $ x\equal{}0$.

If that's finite-dimensional, pick a basis. With respect to this basis, $ f(x,y)\equal{}x^TAy$ for some $ n\times n$ matrix $ A$. We have $ f(V,y)\equal{}0$ iff $ Ay\equal{}0$, and this implies $ y\equal{}0$ iff the columns of $ A$ are linearly independent. Similarly, $ f(x,V)\equal{}0$ implies $ x\equal{}0$ iff the rows of $ A$ are linearly independent. By standard theorems of elementary linear algebra, both of those are equivalent to $ A$ being nonsingular.

Now, if that's infinite-dimensional, this is false. Consider the space of all polynomials, with $ f(x^j,x^k)\equal{}\begin{cases}1&j\equal{}k\plus{}1\\0&\text{otherwise}\end{cases}$, extended by bilinearity to all pairs of polynomials. Essentially, we make $ A$ the matrix of a shift operator. For that example, $ f(1,V)\equal{}0$, but there is no nonzero $ y$ with $ f(V,y)\equal{}0$.


function
algebra
polynomial
algebra proposed

Find all functions $f: \mathbb N \to \mathbb N$ for which
\[ f(n) + f(n+1) = f(n+2)f(n+3)-1996\]
holds for all positive integers $n$.

[quote="MJ GEO"]$ f$ from $ N$ to $ N$ and $ f(n) \plus{} f(n \plus{} 1) \equal{} f(n \plus{} 2)f(n \plus{} 3) \minus{} 1996$[/quote]

$ f(n) \plus{} f(n \plus{} 1) \equal{} f(n \plus{} 2)f(n \plus{} 3) \minus{} 1996$
$ f(n\plus{}1) \plus{} f(n \plus{} 2) \equal{} f(n \plus{} 3)f(n \plus{} 4) \minus{} 1996$

Subtracting : $ f(n)\minus{}f(n\plus{}2)\equal{}f(n\plus{}3)((f(n\plus{}2)\minus{}f(n\plus{}4)$ and so :

$ f(1)\minus{}f(3)\equal{}f(4)f(6)f(8)...f(2p\plus{}2)(f(2p\plus{}1)\minus{}f(2p\plus{}3))$ $ \forall p\ge 1$
$ f(2)\minus{}f(4)\equal{}f(5)f(7)f(9)...f(2p\plus{}3)(f(2p\plus{}2)\minus{}f(2p\plus{}4))$ $ \forall p\ge 1$

Considering the first line, we conclude that :
either $ f(2p\plus{}1)\equal{}f(2p\plus{}3)$ from a given point and then $ f(2p\plus{}1)\equal{}c$ $ \forall p>p_0$
either $ f(2p\plus{}2)\equal{}1$ and $ f(2p\plus{}1)\minus{}f(2p\plus{}3)\equal{}c$ from a given point

Combining with the same analysis for second line, we conclude that, from a given point, we have :
either $ a,b,a,b,a,b,....$
either $ 1,k,1,k\plus{}c,1,k\plus{}2c,1,k\plus{}3c, ...$

Using then the original equation, we can write :
$ a\plus{}b\equal{}ab\minus{}1996$ and so $ (a\minus{}1)(b\minus{}1)\equal{}1997$ and so $ a\equal{}2$ and $ b\equal{}1998$ (or the reverse)
$ 1\plus{}k\equal{}1(k\plus{}c)\minus{}1996$ and so $ c\equal{}1997$

So the function ends with :
either $ 2,1998,2,1998,2,1998,...$
either $ 1,k,1,k\plus{}1997,1,k\plus{}2\cdot 1997, ...$

It's then immediate to show that if this is true from a given point, it's true from the beginning. Hence the four solutions :

$ \{f(1),f(2),f(3),...\}\equal{}\{2,1998,2,1998,2,1998, ...\}$
$ \{f(1),f(2),f(3),...\}\equal{}\{1998,2,1998,2,1998,2 ...\}$
$ \{f(1),f(2),f(3),...\}\equal{}\{1,a,1,a\plus{}1997,1,a\plus{}2\cdot 1997,1,a\plus{}3\cdot 1997, ...\}$
$ \{f(1),f(2),f(3),...\}\equal{}\{a,1,a\plus{}1997,1,a\plus{}2\cdot 1997,1,a\plus{}3\cdot 1997,1 ...\}$

[quote="MJ GEO"]thanks.did you think on my polynomials problems?[/quote]

Since you already have solutions, we are in no hurry to solve these problems ...

Let $\mathbb N$ be the set of positive integers. Find all functions defined on $\mathbb N$ and taking values on $\mathbb N$ satisfying, for all $n\in\mathbb N$,
$$f(n)+f(n+1)=f(n+2)f(n+3)-1998.$$


The centers of the two circles are 12 meters apart, and the overlapping space is 8 meters wide at the widest point between the centers as shown. What is the area of the shaded region?

yes the circles are congruent; kunny, care to give any explanation at all?

[hide="Small hint 1"] The easiest thing to do is to count half of the desired area.  [/hide] [hide="Small hint 2"] If you divided the area in half correctly, it is the difference between the area of an arc and a triangle. [/hide]


How would you veterans suggest dividing up your time on the individual round? Should you go for the problem you find easier and then move to the second one when your finished? Or should you stop after 5 minutes if you haven't finished and move to the second one or something?

Thanks!

I usually do the easier one (or the one that seems more doable) first because some of the ARML problems are pretty hard. I want to make sure I get easy ones. I can usually get the easier one within 2-4 minutes, so I spend the rest of the time to work on the other problem.

I'm hardly a veteran, but the main thing to remember is that you get 1 point if you completely solve one problem and never look at the other one, but you get 0 points if you halfway solve both.  Don't stop working on a problem if you think there is any way you could solve it in the remaining time.

It's a judgment call, really.  Personally, I usually plow through whatever problems I have in order.

By the way, Mr. Slater (my school coach, ARML coach) says that (at Penn State, anyhow, although I can't imagine that they would do this just there and nowhere else), they have everybody turn the question over, with pencils, down, they read the questions, and [i]then[/i] you are allowed to pick up your pencil and begin writing.  The purpose is to make sure that everybody does in fact have the right two questions in front of them.

Look at the two and go for the one that is easier for you.

I can usually do the first 2 or 3 pairs with plently of time to spare, so I just start on the one that is 1st. If I get stuck, confused, or the arithmetic isn't pretty, I do the next one.

oh I dont remember if that such thing has been done in San Jose (or Las Vegas this year). I didn't think I ever had time to read the questions.

Here is how I will do it.

Choose an easy problem and attempt it for 3-4 minute. If you do not see an immediate way (that is, you can't simplify to a easy expression or get equation with 3-4 variables that you can't do anything with), read the other problem and see if you know any idea to do that one. If you don't, restart the easy one with new method. Either way, I would only spend 9 to 9.5 minutes for each pair because I want to check my answers to make sure that I do them right. Remember, the time is a big thing and I remember on one practice that I did at home, I thought $-5b+2b = -7b$ because I was in hurry.

But then again, it's possible that you change right answer at the end  :oops:  so yeah, it really depends. But I really like this quote:

[quote]but the main thing to remember is that you get 1 point if you completely solve one problem and never look at the other one, but you get 0 points if you halfway solve both.[/quote]

[quote="Sly Si"]Yes, the reading of the questions happens at Iowa, and I assume it happens everywhere.  You're allowed to start thinking about the questions (how could they stop you?) before they finish reading, but you can't pick up your pencil.

Just pick whichever question you think is easier (read them both!) and solve it all the way.  Don't change unless you're sure that you can't solve the one you're op and can solve the other one.[/quote]

Yeah, I don't think we've done this at the San Jose site in the last couple of years at least. We just get the questions, flip it over, and start.

As for the question at hand, I would just pick one and do it for a few minutes at least. If you have the right method, that's usually enough to solve it. If you don't, you'll know by now so go to the next problem. I always get owned on the ARML individual because I lose a pair from a misread and spending too much time on that problem (along with other various dumb mistakes... but yeah).


Find all pairs of natural numbers $x,y$ such that $(x+y)^2-2(xy)^2=1$

This should be bumped to intermediate, since no one here seems to be solving it.

i got $-x^2y^2=(x^2-1)(y^2-1)$. left is negative no matter what, and so one of them must be between 0 and 1 inclusive. but there is no integer between 0 and 1. so let $x=0$, then $y^2=1$. since $x,y$ are natural numbers, $y=1$. answer $(x,y)=(1,0),(0,1)$. i hope its correct unless i missed something

edit: nevermind, my solution is wrong, i missed the $2xy$ term, im fixing it now, ill correct this post
rather than correcting above, i retype everything

i got $x^2+2xy+y^2-2x^2y^2=1$
$1=x^2y^2-2xy+1+x^2y^2-x^2-y^2+1=(xy-1)^2+(x^2-1)(y^2-1)$
if $x\geq 2$ and $y\geq 2$, then $(xy-1)^2+(x^2-1)(y^2-1)>2>1$. so suppose $x=1$.
then we get $1=(y-1)^2$, solve and get $y=2$. answer $(x,y)=(1,2),(2,1)$


function
probability
inequalities
LaTeX
triangle inequality
topology
probability and stats

Let $ \left(\Omega,A,P\right)$ be a probability space. Prove that

$ \rho(A,B) = \frac {P(S(A,B))}{P(A \cup B)} \mbox{ if P(A \cup B) \ne 0}$
$ \rho(A,B) = 0 \mbox{ if P(A \cup B) = 0}$

where S means the symmetric difference satisfies the triangle inequality.

I can show that P(S(A,B)) satisfies the triangle inequality if that helps at all.

The big issue is going to be positive definiteness. You want $ \rho(A,B)\equal{}0$ to imply that $ A\equal{}B.$ I only see two ways of getting that.

Either

1. Every nonempty measurable event in this probability space has positive probability

or

2. The elements of the metric space are not the events in $ \Omega$ but rather equivalence classes of events under the relation $ A\sim  B$ iff $ P(S(A,B))\equal{}0.$ (That is, we essentially ignore events of probability zero.)

[quote="Kent Merryfield"]The big issue is going to be positive definiteness. You want $ \rho(A,B) \equal{} 0$ to imply that $ A \equal{} B.$ I only see two ways of getting that.

Either

1. Every nonempty measurable event in this probability space has positive probability

or

2. The elements of the metric space are not the events in $ \Omega$ but rather equivalence classes of events under the relation $ A\sim B$ iff $ P(S(A,B)) \equal{} 0.$ (That is, we essentially ignore events of probability zero.)[/quote]

I'm really sorry Kent, I totally botched the question. I took me forever to get the latex right that I forgot to finish the problem statement. I corrected it if you still want to help me.


function
calculus
derivative
vector
real analysis
calculus computations

This is likely very easy, but I am missing the point (an old exam question):

:  Suppose F=F(u,v) is a smooth function from R^2 to R with F(1,2)=0 and F_v(1,2)~=0 where F_v is the partial derivative with respect to v and ~= means not equal to.  Show that F(xy, (x^2+z^2)^.5)=0 defines a smooth surface (x,y,z(x,y)) in a neighborhood of (1,1,3^.5), and find a normal vector n to this surface at this point if it is known that F_u(1,2)=1 and F_v(1,2)=2.  :

A smooth solution v(u) is direct from the implicit function theorem, but what about z(x,y)?  Any help/solution would be appreciated.  Thanks![/code]

Define $G(x,y,z)=F(xy,\sqrt{x^{2}+z^{2}})$. You want to compute the gradient of $G$ at the point $(1,1,\sqrt{3})$. As long as the gradient is not a zero vector, the surface $G=0$ is smooth near that point and $\nabla G(1,1,\sqrt{3})$ is normal to it.

Time to break out the good old chain rule: $G_{x}=yF_{u}+\frac{x}{\sqrt{x^{2}+z^{2}}}F_{v}$, etc.