An integer is called [i]parity-monotonic[/i] if its decimal representation $a_{1}a_{2}a_{3}\cdots a_{k}$ satisfies $a_{i}<a_{i+1}$ if $a_{i}$ is odd, and $a_{i}>a_{i+1}$ is $a_{i}$ is even. How many four-digit parity-monotonic integers are there?

This is almost identical to a 2004 AIME problem (also #6), so I got it pretty quickly on the test.

The one thing that screwed both me and someone else at my school (a MOPper) up was that we both read it as $a_{i}<a_{i+1}$ for $i$ odd, instead of $a_{i}$ odd.  I caught my error, he didn't.

I got 640 ... is that right?

Not too great explanation, just copied it from what I wrote in the [url=http://www.artofproblemsolving.com/Wiki/index.php/2007_AIME_II_Problems/Problem_6]AoPSWiki[/url]

[hide="solution"]
Notice that $a_{0}, a_{1}, a_{2}$ cannot be 0 or 9.

For any number from 1-8, there are exactly $4$ numbers from 1-8 that are odd and less than the number or that are even and greater than the number (the same will happen for 0 and 9 in the last column). Thus, the answer is $ 4^{k-1}* 10 = 4^{3}10 = 640$.

I verified this with a computer.
[/hide]

By the way, 2004 AIME I #6 is somewhat different, as this problem seemed to be easier after writing out a chart of values.

Yeah ... that's what I did, but it was over 1000 so I read the problem a few more times.

I just ended up putting 900 and moved on although I was regretting not putting 394 >_> <_<, I wanted to check the rest of my problems which turned out to be an extremely good choice (1-5 had no errors, however I made a minor error on both #7 and #8 and caught them while checking)

Woah, 900 was also my initial blind guess, except I realized with two minutes to go that I could do it backwards. Without that property, 6 would easily have been the most difficult question of the contest.

Guess we were betting on the shrewd coincidence (the likes of which so often happens in mathematics) that the number of four-digit parity-monotonic integers equals the number of three-digit integers!

Is it supposed to say:

An integer is called [i]parity-monotonic[/i] if its decimal representation $a_{1}a_{2}a_{3}\cdots a_{k}$ satisfies $a_{i}<a_{i+1}$ [b]if[/b] $a_{i}$ is odd, and $a_{i}>a_{i+1}$ [b]if[/b] $a_{i}$ is even. How many four-digit parity-monotonic integers are there?

If so please edit.

(Just trying to get it perfect since it's been added to the resources section  :D )

[quote="bloodysloth"][quote="Ignite168"][quote="samath"]The one thing that screwed both me and someone else at my school (a MOPper) up was that we both read it as $a_{i}<a_{i+1}$ for $i$ odd, instead of $a_{i}$ odd.  I caught my error, he didn't.[/quote]

This is what I did for 3 hours and I kept getting 1394.[/quote]

This is what I did too.  I never caught my mistake.

I was getting 1310 though, and I did it two different methods... you sure you discluded anything starting with zero?[/quote]

Yep, did you also consider the possibility of having two of the same digits? Also, keep in mind that the number of possibilities if the digits you picked are like 1123 is different from 1223 but the same as 1233. 0 can also never be a repeating digit, etc.

[quote="samath"]The one thing that screwed both me and someone else at my school (a MOPper) up was that we both read it as $a_{i}<a_{i+1}$ for $i$ odd, instead of $a_{i}$ odd.  I caught my error, he didn't.[/quote]
Haha I must be like the 20th person to have misread along those lines now (I didn't take the test). A friend gave me the problem and said there was a 1-line solution, and I was basically like WTF how can you do this without *some* casework?? :D

Yep, I misread it, and did a disgusting amount of casework- something like 19 of them, because sometimes that's just what you need to do. I got 1410 though.... weird.

[hide]List each pair of adjacent digits that is valid.  There are 40 such pairs.  Organize them in a table to check for patterns:

$\begin{array}{l|c|c|c|c|c|c|c|c|c|c|}& x0 & x1 & x2 & x3 & x4 & x5 & x6 & x7 & x8 & x9 \\ \hline 0x &&&&&&&&&& \\ \hline 1x & & & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 \\ \hline 2x & 20 & 21 & & & & & & & & \\ \hline 3x & & & & & 34 & 35 & 36 & 37 & 38 & 39 \\ \hline 4x & 40 & 41 & 42 & 43 & & & & & & \\ \hline 5x & & & & & & & 56 & 57 & 58 & 59 \\ \hline 6x & 60 & 61 & 62 & 63 & 64 & 65 & & & & \\ \hline 7x & & & & & & & & & 78 & 79 \\ \hline 8x & 80 & 81 & 82 & 83 & 84 & 85 & 86 & 87 & & \\ \hline 9x &&&&&&&&&& \\ \hline\end{array}$

Notice there are four valid choices in every column.  This means that for every digit, there are four valid digits to the left.  Ten choices for the rightmost digit.  Four choices for each remaining digit to the left.  $10\times 4\times 4\times 4=\boxed{640}$
[/hide]

i'm 100% sure it's 640

misread it a bunch of times and got 1410 but realized it was 640

[quote="Ignite168"][quote="bloodysloth"]

This is what I did too.  I never caught my mistake.

I was getting 1310 though, and I did it two different methods... you sure you discluded anything starting with zero?[/quote]

Yep, did you also consider the possibility of having two of the same digits? Also, keep in mind that the number of possibilities if the digits you picked are like 1123 is different from 1223 but the same as 1233. 0 can also never be a repeating digit, etc.[/quote]

Yeah.  I took that into account.  Hmm... 2 others got 1410... I'm guessing you made a dumb mistake somewhere, and I added wrong somewhere

Well, I didn't take the AIME II, but when I saw this problem here, I immediately thought DP (after noticing that I had read it incorrectly, of course).

There is one way for any of the digits to be the first digit of a one digit number. I'll then append numbers to the front in 3 steps, then exclude 0 on the last step.

At each step, the number for each digit gets added to the odds less than it, and the evens greater than it.
$\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}\hline 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\\hline \hline 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\\hline 0 & 8 & 2 & 6 & 4 & 4 & 6 & 2 & 8 & 0\\\hline 0 & 32 & 8 & 24 & 16 & 16 & 24 & 8 & 32 & 0\\\hline 0 & 128 & 32 & 96 & 64 & 64 & 96 & 32 & 128 & 0\\\hline \end{tabular}$

So, our answer is $128+32+96+64+64+96+32+128=\boxed{640}$

Note: It happens that I'm multiplying by 4, but I'm actually adding the number from all the numbers greater than it if the digit being appended is odd and less than it if it's even.

The rightmost digit has 10 choose, each of the else digits has 4 choose, so the answer is 10*4*4*4=640.
Seem to be difficult, but it's so easy.

I'm sorry but i don't see if how we can pick from 0 to 10 for the last digit and then four choices for each digit.  If the last digit is 9, the digit next to it can be from 1 to 8, how come we only have 4 choices?

If the last digit is 9, there can only be 4 choices, because the one to the right must be an odd number (1,3,5,7).

Note that $a_1 < a_2, a_2 > a_3, a_3 < a_4$. Say we have four digits $x, y, z, w$ and $x<y<z<w$. Then we can arrange as $(x,y), (z,w)$ where $x, y$ are $a_1, a_3$ in some order and $z, w$ are $a_2, a_4$ in some order. Therefore, there are $4$ ways to arrange our number. Now we take cases

Case 1: No zeros.

Then we can pick the digits in $\binom{9}{4}$ ways, and arrange them in $4$ ways, giving $4 \cdot \binom{9}{4}$ ways.

Case 2: One zero.

Then we can pick the digits in $\binom{9}{3}$ ways, and arrange them in $2$ ways, giving $2 \cdot \binom{9}{3}$.

But these add up to $672$, not $640$; what happened?

Bump. Please help, the AIME is tomorrow! :)

Now I'm even more confused. Is this correct so far: Say I pick $4$ different digits and none of them are $0$. Let them be $a, b, c, d$ with $a<b<c<d$, and there are five ways to arrange them; acbd, adbc, bcad, bdac, cdab. Therefore, in the nonzero digits case, it is $\binom{9}{4} \cdot 5$.

This is very close to $640$ and there's still another big case, so it seems wrong...

[quote=channing421]Reread the problem carefully.[/quote]

it says $a_i$ not $i$

Oh god what am I doing... thank you channing


Given $x_i > 0$, prove that.
$\frac{1}{x_1^2} + \frac{2^2}{(x_1+x_2)^2} + ...+ \frac{n^2}{(x_1+...+x_n)^2} \leq \frac{9}{4}(\frac{1}{x_1^2} + ...+ \frac{1}{x_n^2})$

9/4 is the best constant. I hope I will see a reasonable solution.

Is there anyone who are interested in my inequality? Because it is ugly or it is not solved by SOS or you are not familiar with its type or something else?.

9/4 is the best constant for every x_i and n.

Your problem was lack of something, i.e. $\{x_i\},\ i=\overline{1,n}$ is increasing sequence.

Do you mean that it is wrong?

I may do some wrong calculations but No there is no other conditions.

of course it's wrong!
take $x_1=1$ and $x_{i}\rightarrow 0$ for $i>1$ see what you get! :)

$x_1 = 1, x_i \to 0$, then

$LHS \to (1^2 + ...+n^2)$, $RHS$ goes to infinity. Whats wrong?

LOL, it looks like a failure when not many of you are interested in this problem.

Should I challenge all inequality solvers in this forum?

I add another one:

$\frac{1}{x_1} + \frac{2}{x_1+x_2} + ...+ \frac{n}{x_1+...+x_n} \leq 2 (\frac{1}{x_1} + ...+ \frac{1}{x_n})$

The coefficient is 2 not 4 as many of you have ever seen it.

About the second one :
http://www.mathlinks.ro/Forum/viewtopic.php?t=18543
http://www.mathlinks.ro/Forum/viewtopic.php?t=18542
:)

Thank you mathmanman for the second one. My solution is exactly as the post about Hardy inequality.  Now it is a generalization:
Given $k \in Z$
$x_1^k + (\frac{x_1 + x_2}{2})^k + ... + (\frac{x_1 + ...+x_n}{n})^k \leq (\frac{k}{k-1})^k (x_1^k + ...x_n^k)$ with $k \geq 2$

and Replace $(\frac{k}{k-1})^k$ by $(\frac{k-1}{k})^{\|k\|}$ with $k$ negative.


limit
real analysis
real analysis unsolved

Let $ (x_n)_{n \geq 1}$ such that $ x_n\equal{} \frac{a_1^{n\plus{}1}\plus{} a_2^{n\plus{}1}\plus{} \dots \plus{} a_{2003}^{n\plus{}1} }{a_1^n \plus{} a_2^n \plus{} \dots \plus{} a_{2003}^n}$.

It is obvious that $ x_n$ is convergent. Let $ \lim_{n \to \infty}x_n\equal{} l$. Now compute:
\[ \lim_{n \to \infty} n^k (x_n \minus{} l ).\]

I will assume $ a_i > 0$ and $ k$ is a fixed real number, independent of $ n$.

Put $ a \equal{} \max a_i$. Without loss of generality, we may assume $ a \equal{} a_1 \equal{} \cdots \equal{} a_N > a_{N\plus{}1} \geq a_{N\plus{}2} \geq \cdots \geq a_{2003}$.

Letting $ \lambda_i \equal{} a_i / a$, we have $ x_n \equal{} \frac{aN \plus{} \sum_{N\plus{}1}^{2003} a_i \lambda_i^n}{N \plus{} \sum_{N\plus{}1}^{2003} \lambda_i^n} \to a$ as $ n \to \infty$. Especially, we have $ 0 < x_n \leq a$ for all $ n$.

Then $ l \equal{} a$, and we have $ 0 \leq n^k (a \minus{} x_n) \equal{} n^k \frac{\sum_{N\plus{}1}^{2003} (a \minus{} a_i) \lambda_i^n}{N \plus{} \sum_{N\plus{}1}^{2003} \lambda_i^n} \leq \frac{1}{N} \sum_{N\plus{}1}^{2003} (a \minus{} a_i) n^k \lambda_i^n$.

Since $ \lambda_i < 1$ for $ i > N$, squeezing theorem shows that $ n^k (a \minus{} x_n) \to 0$ as $ n \to \infty$.


There is a polinom $P(x)$ with integer coefficents.
$P(-2006)<P(2006)=2005$
Prove That $P(-2006)\leq-2007$.
Edited: Sorry, I forgot the minus.  :?

Something smells here. Please review the statement of the problem, because such as it is, it's trivial: $P(-2006)<2005\leqslant 2007$

Farenhajt, now it's ok, I have forgotten the minus :?

I solved this problem, tell me if it's ok!
$T(x)$ - All the terms in polinom $P(x)$ such that in each term the degree of $x$ is odd.
$K(x)$ - All the terms in polinom $P(x)$ such that in each term the degree of $x$ is even.
So we get trivial equations:
$T(2006)=-T(-2006)$
$K(2006)=K(-2006)$
So:
$P(2006)+P(-2006)=2K(2006),P(2006)=2005$
And:
$P(-2006)=2K(2006)-2005$
Suppose that $P(-2006)>-2007$ , because the polinom have integer coefficents so:
$P(-2006)=2K(2006)-2005\geq-2006$
$K(2006)\geq-\frac{1}{2}$
Again because of the integer coefficents:
$K(2006)\geq0$
$P(2006)=K(2006)+T(2006)$ So:
$T(2006)\leq2005$

$P(-2006)<P(2006)$
$K(-2006)+T(-2006)<K(2006)+T(2006)$
$T(-2006)<T(2006)$
$T(2006)>0$
Now, suppose that $m$ is the minimal degree of $x$ of one of the terms in $T(x)$ so:
$T(x)=l{x^m}$ for some integer l.
$T(2006)=l{2006^m}$
$T(2006)>0$ so $l>0$. $l$ is integer so $l\geq1$.
$m\geq1$ because all degrees of $x$ in each of the terms in $T(x)$ are odd.
So:
$T(2006)\geq2006$ and here we get contradiction so:
$P(-2006)\leq-2007$.

Please check my solution, and tell if it's ok, Thanks. :)


I got a new ti-89 titanium (because i made states for mathcounts).  So i used the ti link thing, and hooked it up to my computer.  I got 3 games from ticalc.org and my calculator says USB receved: snake (i downloaded snake)
Now how do i get to play snake?  I tried typing in snake() on the home screen and nothing works! Please help me! :(

I perceive that it is a BASIC program, meaning you access it through the PRGM menu. (At least so I think, from my experience.) Go to the PRGM menu and select SNAKE. :) Tell me if I'm completely wrong. :D

Can you tell me how to get to the program menu? :?

Never mind. Have you read your guidebook? http://education.ti.com/educationportal/appsdelivery/download/download_eula.jsp?applicationId=6129&contentPaneId=17&cid=US page 295 looks like what you need to look at.

I downloaded snake from the internet and put it on my calculator.  THen when i type in snake() on the screen, nothing happens!  I don't know whats wrong!  This also happens when i try to run any of my other games!

I think that what [b]solafidefarms[/b] is suggesting would work for TI-83+, but for the TI-89, try going into the Var-Link menu by pressing 2nd + Var-Link (above the '-' key).  Check to see if you can find your snake program somewhere in there.  If it's called "snake", then when you select it, it should write "snake(" on the screen.  Then just type in the closing parenthesis and hit enter.


#1. ToBe (animation)

[url]http://www.artofproblemsolving.com/Forum/files/snowmanflash_164.swf[/url]

#2. DarkKnight (graphic)

[img]http://img51.echo.cx/img51/4544/snowcopy0oz.jpg[/img]

#3. LynnelleYe (graphic)

[img]http://img.photobucket.com/albums/v189/bigsister/snowflake.gif[/img]

#4. -Terminator- (graphic)

[img]http://www.artofproblemsolving.com/Forum/files/thumbs/t_snow_142.gif[/img]

#5. hmoonster (graphic)

[img]http://www.artofproblemsolving.com/Forum/files/thumbs/t_snow_142.jpg[/img]

You have one week to vote. Next Monday we will find out the winner! I will vote in case of a tie.

NOTE: The competitors CAN vote for themselves.

Guess who I voted for???  :D  :D  :D  :D  :D  :D  :D  :D  :yoda:  :yoda:

Must come to you as a shock, but I vote for ToBe.


a,b,c,d>0
3/2 *(a^3+b^3+c^3+d^3) \geq ad \sqrt bc+ bd \sqrt ac + cd \sqrt ab + bc \sqrt ad + ab \sqrt cd + ac \sqrt bd

The desired inequality may rewritten as :

 6\sum a^3  \geq 4 \sum ab \sqrt (cd)
where the sums are symetric in all the variables

Since the sequence (3,0,0,0) majorizes the sequence (1,1,1/2,1/2), the inequality is a direct consequence of Muirhead inequality.

Pierre.

[quote="Ji Chen"]If $a,b,c,d$ be nonnegative real numbers, then

$(bcd+cda+dab+abc)^{2}\geq 2(a^{2}b^{2}cd+b^{2}c^{2}da+c^{2}d^{2}ab+d^{2}a^{2}bc)$.

Proof
$(bcd+cda+dab+abc)^{2}-2(a^{2}b^{2}cd+b^{2}c^{2}da+c^{2}d^{2}ab+d^{2}a^{2}bc)$

$=(bcd-cda+dab-abc)^{2}$.
[/quote]
There you go, but it should be of course $4$ instead of $2$:

 $(bcd+cda+dab+abc)^{2}\geq 4(a^{2}b^{2}cd+b^{2}c^{2}da+c^{2}d^{2}ab+d^{2}a^{2}bc)$.

Note that the above & the previous ineq are both valid for all real $a,b,c,d$.

Trying the same thing for $n\ge5$ (nonnegative) reals: We can't do better than a weak $k=4$ in $(\sum_{cyc}abc)^{2}\ge k\sum_{cyc}a^{2}b^{2}cd$. (See $(a_{1},...a_{n})=(1,1,1,1,0,...,0)$.) I think your method can be tweaked to prove that too.  :wink:

Now how many minutes do you need for the following:
 $n=4$, for $a,b,c,d$ nonnegative real numbers prove $(\sum_{cyc}ab)^{3}\ge 16\sum_{cyc}a^{2}b^{2}cd$   :rotfl:

More seriously: Prove
$(\sum_{cyc}ab)^{3}\ge 25\sum_{cyc}a^{2}b^{2}cd$ for $n=5$,
$(\sum_{cyc}ab)^{3}\ge 27\sum_{cyc}a^{2}b^{2}cd$ for $n>5$.  :wink:

[quote="Maverick"]$a,b,c,d>0$
\[\frac32 (a^{3}+b^{3}+c^{3}+d^{3}) \geq ad \sqrt{bc}+bd \sqrt{ac}+cd \sqrt{ab}+bc \sqrt{ad}+ab \sqrt{cd}+ac \sqrt{bd}\][/quote]
[quote="pbornsztein"]The desired inequality may rewritten as :

\[6\sum a^{3}\geq 4 \sum ab \sqrt{cd}\]
where the sums are symmetric in all the variables

Since the sequence $(3,0,0,0)$ majorizes the sequence $(1,1,1/2,1/2)$, the inequality is a direct consequence of Muirhead inequality.

Pierre.[/quote]

[quote="spanferkel"]
$(\sum_{cyc}ab)^{3}\ge 25\sum_{cyc}a^{2}b^{2}cd$ for $n=5$.
[/quote]
This is not ture, for a counterexample $a=0,b=c=e=2,d=1$:

$(ab+bc+cd+de+ea)^{3}=8^{3}=512$,

$25(a^{2}b^{2}cd+b^{2}c^{2}de+c^{2}d^{2}ea+d^{2}e^{2}ab+e^{2}a^{2}bc)=25\times32=800$.

But the following inequalities

$(ab+bc+cd+de+ea)^{3}\geq25(ab^{2}c^{2}d+bc^{2}d^{2}e+cd^{2}e^{2}a+de^{2}a^{2}b+ea^{2}b^{2}c)$

and $(ab+bc+cd+de+ea)^{3}\geq25abcde(a+b+c+d+e)$

hold for all nonnegative real numbers $a,b,c,d,e$.
[hide="Proof."]Put $a=ab,b=bc,c=cd,d=de,e=ea$ in the inequalities of
http://www.mathlinks.ro/Forum/viewtopic.php?t=126544.
[/hide]


real analysis
inequalities
complex analysis
complex analysis unsolved

prove: if $|x|=|y|$ and $x\neq y$ then
\[2\ge\limsup\left|1-\left(\frac{x}{y}\right)^{n}\right|\ge\sqrt{3}\]

You're raising a fixed positive real number to the $\frac1n$ power; it always goes to 1.

What did you really mean to ask?

mad_cow, are you sure about your exercice ?!?

an quick way to see it: draw a picture of the unit circle and an equilateral triangle inscribed in it ..

I've done the draw
but i don't see the solution :(
(of course $2\ge \dots$ is clear, the second inequality is needed)

Can you see where the equality case in the lower bound comes from? Understanding that equality case is the key.


Determine all pairs $ (P(x), Q(x))$ monic polynominals such that:
$ (P(Q(x)) \equal{} x^{1994}$

suppose P(x) is m degree, Q(x) is n degree. Then mn=1994.

suppose a is the smallest number not larger than m that x^a has non-zero coefficient s in P(x), define such b for Q(x).(coefficient of x^b is t)
if a<m or b<n. then the coefficient of x^ab in P(Q(x)) is s*t^a(Is that right?)

But since P(Q(x))=x^1994 so the coefficient of x^ab should be zero, contradiction.
so a=m, b=n.

which follows that P(x)=x, Q(x)=x^1994; P(x)=x^2, Q(x)=x^997;
P(x)=x^997, Q(x)=x^2; P(x)=x^1994, Q(x)=x

Hmmm... I have done some work on this exercise but I don't not have a complete solution of it yet.

$ P(x) \equal{} x_n \plus{} a_{n\minus{}1}x^{n\minus{}1}\plus{}...\plus{}a_1x\plus{}a_0$
$ Q(x) \equal{} x_m \plus{} b_{m\minus{}1}x^{m\minus{}1}\plus{}...\plus{}b_1x\plus{}b_0$

$ P(Q(x)) \equal{} (x_m \plus{} b_{m\minus{}1}x^{m\minus{}1}\plus{}...\plus{}b_1x\plus{}b_0)^n \plus{} ...\plus{}a_1(x_m \plus{} b_{m\minus{}1}x^{m\minus{}1}\plus{}...\plus{}b_1x\plus{}b_0) \plus{} a_0 \equal{} x^{1994}$

By the Multinomial Theorem we have :

$ (x_m \plus{} b_{m\minus{}1}x^{m\minus{}1}\plus{}...\plus{}b_1x\plus{}b_0)^n \equal{} \Sigma_{k_1, ..., k_{m\plus{}1}}(n!/k_1!...k_{m\plus{}1}!) * (b_{m\minus{}1}^{k_2}...b_1^{k_m}b_0^{k_{m\plus{}1}})*x^{mk_1\plus{}(m\minus{}1)k_2...\plus{}k_m}$

where $ k_1\plus{}k_2\plus{}...\plus{}k_{m\plus{}1}\equal{}n$

We have to prove now that $ mk_1\plus{}(m\minus{}1)k_2...\plus{}k_m \leq mn$. This is straightforward from $ k_1\plus{}k_2\plus{}...\plus{}k_{m\plus{}1}\equal{}n$ multiplying by m both sides and the maximum value is reached when $ k_1\equal{}n$.

This was all to prove that the degree of the polynomial P(Q(x)) is achieved as the degree of Q multiplied by that of P. I didn't have the confidence that in the case when all the monomials have the same variable (x), the degree of P(Q) was the multiplication of the degree P and with that of Q.

1994 = 2*997 where 997 is a prime number. Therefore we will have to polynomials one with degree 2 and the other with degree 997.

P(x) = $ x^2 \plus{} a_1x \plus{}a_0$ and Q(x)= $ x^{997} \plus{} b_{996}x^{996}\plus{}...\plus{}b_1x\plus{}b_0$.
We have now that P(Q(x)) = $ (x^{997} \plus{} b_{996}x^{996}\plus{}...\plus{}b_1x\plus{}b_0)^2 \plus{} a_1(x^{997} \plus{} b_{996}x^{996}\plus{}...\plus{}b_1x\plus{}b_0) \plus{} a_0 \equal{} x^{1994}$. From the Multiparty Theorem on the term squared we know that all the monomials with an exponent $ \neq 0$ should have coefficient equal to 0 as there is no way to eleminate $ {x^{996}}^2, ..., x^2$ by using the other monomials presented in the polynom multiplied by $ a_1$. By that we have P(x) still the same and Q(x)= $ x^{997} \plus{} b_0$.

In order for P(Q(x))=$ x^{1994}$, the values $ a_0, a_1, b_0$ shouls satisfy the equalities $ 2b_0\equal{}\minus{}a_1$ and $ b_0^2\plus{}a_1b_0\plus{}a_0\equal{}0$.

I have still to investigate the other case when P(x) = $ x^{997} \plus{} b_{996}x^{996}\plus{}...\plus{}b_1x\plus{}b_0$ and Q(x)= $ x^2 \plus{} a_1x \plus{}a_0$.

Sorry I've made a big mistake, because if the constant exist, the other component of the polynomial may be canceled. I try to revise it below.

suppose P(x) is m degree, Q(x) is n degree.
we have mn=1994, so (m,n)=(1,1994), (2,997), (997,2), (1994,1).

1) if (m,n)=(1,1994) suppose P(x)=x+c
then P(Q(x))=Q(x)+c=x^1994, so Q(x)=x^1994-c

2) if (m,n)=(1994,1) suppose Q(x)=x+c
then P(Q(x))=P(x+c)=x^1994, which suggest that P(x)=(x-c)^1994

3) if (m,n)=(2,997) suppose P(x)=x^2+ax+b
put x=0 we have P(Q(0))=0, so Q(0) is a root of P(x)=0
suppose another root of P(x)=0 is r
since degree of Q(x) is odd, so there exist real s that Q(s)=r
so P(Q(s))=0 but since P(Q(s))=s^1994, so s=0
so P(x)=0 has double roots Q(0) so P(x)=(x-Q(0))^2
so P(Q(x))=(Q(x)-Q(0))^2=x^1994
we get Q(x)=x^997+Q(0)(since Q(x) has leading coefficient 1)
so P(x)=(x-c)^2, Q(x)=x^997+c is the general solution of this case.

4) at last if (m,n)=(997,2) suppose Q(x)=x^2+ax+b (we have Q(0)=b)
put x=0 we get P(Q(0))=P(b)=0^1994=0
put x=-a we get P(Q(-a))=P(b)=(-a)^1994=a^1994
so a=0 and Q(x)=x^2+b
so P(x^2+b)=x^1994=(x^2)^997 and P(x^2)=(x^2-b)^997
and P(x)=(x-b)^997

combining 1,2,3,4 we get all the polynomials

P.S. 1) can this problem be done just by comparing the coefficient two sides?
2) how about change 1994 to any other number (for example, 2008)
3) Of course, tell me any mistake if there is any :)


invariant
topology
advanced fields
advanced fields unsolved

if we have diffeomorphism $f: M\rightarrow N$ between two manifolds such that maps geodesics to geodesics the is it isometric?

No: for example, the standard torus $\mathbb R^{2}/\mathbb Z^{2}$ can be mapped onto another torus $\mathbb R^{2}/(2\mathbb Z\times \mathbb Z)$ by the map $(x,y)\mapsto (2x,y)$. This preserves geodesics, yet the tori are not isometric.

by preserving geodesic s i meant that it preservs the velocity too


The incircle with center $I$ of $\Delta ABC$ touches it's sides $BC,AC,AB$ in $D,E,F$ respectively.
$EF$ meets $BC$ again in $G$. The line $GI$ meets $AC$ at $P$, also $EI$ and $AD$ meet at $Q$.

Prove that $PQ \parallel EF$.

[quote="April"]
[size=150][color=red]Nice problem![/color][/size]  :lol:
[/quote]

Thank you April! :)
I always greatly appreciate it when people tell me what they think of my self-made problems.

I like your solution, it's a bit different from the one I expected, and your proof is very nice.  :P

[quote="April"][quote="Jan"][color=darkred]The incircle with center $I$ of $\Delta ABC$ touches it's sides $BC,AC,AB$ in $D,E,F$ respectively. $EF$ meets $BC$ again in $G$. The line $GI$ meets $AC$ at $P$, also $EI$ and $AD$ meet at $Q$.
Prove that $PQ \parallel EF$[/color][/quote]
[size=150][color=red]Nice problem![/color][/size]  :lol:

[color=indigo][b]Proof.[/b] Let $L=GI\cap AD,\,H=AQ\cap EF,\,K=AI\cap EF$
We have: $IL\perp AD$ (well-known)
$\Longrightarrow\triangle AHK\sim \triangle AIL\Longrightarrow AH\cdot AL=AK\cdot AI=AF^{2}$
$\Longrightarrow\triangle AFH\sim\triangle ALF\Longrightarrow\angle AFH=\angle ALF$$\Longrightarrow \angle AEF=\angle ALF\Longrightarrow AFLE$ is cyclic.
 $\Longrightarrow A,\,E,\,F,\,I,\,L$ are cyclic $\Longrightarrow \angle EQP=\angle ELP=\angle EFI=\angle FEQ$
Hence: $PQ\parallel EF$[/color][/quote]

[b] NICE PROBLEM , NICE SOLUTION TOO! [/b]

  [b]a)[/b] How do you  prove that  $IL\perp AD$ (well-known) , without polars ? I read your solution , but to this point I gave an explanation with polars. Have you any other idea?
  [b]b)[/b] Jan , can you send some words of your solution? I would like to have two solutions to this problem.

  Thank you. -
 [u]Babis[/u]

[quote="April"][color=indigo]To prove $IL\perp AD,$ I have another way (without use polars). And now, I'll present it  :lol:

We have:
\begin{eqnarray*}LA^{2}-LD^{2}&=&(LA^{2}-EA^{2})+(EA^{2}-LD^{2})\\ &=& (IL^{2}-IE^{2})+(EA^{2}-LD^{2})\\ &=&(IL^{2}-DL^{2})+(EA^{2}-EI^{2})\\ &=&ID^{2}+(EA^{2}-EI^{2})\\ &=&EA^{2}=IA^{2}-IE^{2}\\ &=&IA^{2}-ID^{2}\end{eqnarray*}
Hence $LA^{2}-LD^{2}=IA^{2}-ID^{2}\Longrightarrow IL\perp AD$[/color][/quote]

 [color=red]Very beatufull solution ! [/color]

 I write it down !

Thank you -  Babis

[quote="silouan"] [color=indigo][b]Another proof.[/b] (I will use [b]April[/b]'s notation)
We have $GL\bot AD$ so $GF\cdot GE=GD^{2}=GL\cdot GI$ so $FLIE$ is cyclic.[/color] [color=red](nice work)[/color]
[color=indigo]Also it is well known that $(E,\,F,\,H,\,G)$ is a harmonic division and $GL\bot AL$  so $LH$ is the bisector of $\angle{FLE}$ so $\angle{FLH}=\angle{HLE}$
But $LEPQ$ is also cyclic, so $\angle{EQP}=\angle{ELP}=90^\circ-\angle{ALE}=90^\circ-\angle{ALF}=\angle{FLG}=\angle{FEI}$
So $FE\parallel PQ$[/color] [/quote]

[color=red][size=150]Very nice and very elegant proof![/size][/color]

[quote="silouan"][quote="stergiu"]  I would like to have two solutions to this problem.
 [/quote]

Now you have also mine mr Babis .(I hope you will liked it  :) )

I have a little different proof .(I will use April's notation)
We have $GL\bot AD$ so $GF\cdot GE=GD^{2}=GL\cdot GI$ so FLIE is cyclic.
Also it is well known that $(E,H,F,G)$ is an harmonic quadraple and $GL\bot AL$  so LH is the bisector of $\angle{FLE}$ so $\angle{FLH}=\angle{HLE}$
But LEPQ is also cyclic ,so $\angle{EQP}=\angle{ELP}=90-\angle{ALE}=90-\angle{ALF}=\angle{FLG}=\angle{FEI}$

so $FE//PQ$ . Hope you will like it.[/quote]

 Silouan, congrats  ! I read carefully your solution. It proves nicely the assertion and  that you have strong fundamentals in geometry! So , we all wish you:

 [size=150][color=red]GOOD LUCK by  BMO - 2007 [/color] [/size]

 in Rhodes (Greece) next week.

[u] Babis[/u]

 [i](Thanks to Jan and April, too, for this nice problem and all these nice solutions. I think that every student with olympiad intersting must study them carefully.)[/i]

[quote="April"][quote="Jan"][color=darkred]The incircle with center $I$ of $\Delta ABC$ touches it's sides $BC,\,AC,\,AB$ in $D,\,E,\,F$ respectively.  $EF$ meets $BC$ again in $G$. The line $GI$ meets $AC$ at $P$, also $EI$ and $AD$ meet at $Q$.
Prove that $PQ \parallel EF$[/color].[/quote]

[color=red]I like this problem very much and I always think about it. And now, I have another proof for it!  :lol:  [/color]

[hide="Very nice and simple proof."][color=indigo][b]Proof.[/b] We have:
$\begin{cases}PL\perp AQ\\ QE\perp AP\end{cases}\Longrightarrow \begin{cases}AI\perp QP\\ AI\perp EF\end{cases}\Longrightarrow PQ\parallel EF$[/color][/hide][/quote]

 Very good !  :lol:

    Some problems , like this , give you much pleasure , if you have time to spend with them!

[color=darkblue][b][u]Commentary.[/u][/b] [size=134][b]April[/b][/size] proved in the his last message that the above well-known property $\mathcal P\ : \ \boxed{GI\perp AD}$ is essentially for this problem

and the remainder is ... no essentially, i.e. for who knows the property $\mathcal P$ this problem is very easily, even obviously !

[size=134][u][b]Stergiu[/b][/u][/size], see http://www.mathlinks.ro/Forum/viewtopic.php?t=46146 where is a proof of the well-known property $\mathcal P$ without the theory of the pol-polars w.r.t. a circle.[/color]

[color=darkblue]You are right, [i][b]Tjhance[/b][/i] ![/color]

[quote="April"][quote="Jan"][color=darkred]The incircle with center $I$ of $\Delta ABC$ touches it's sides $BC,\,AC,\,AB$ in $D,\,E,\,F$ respectively.  $EF$ meets $BC$ again in $G$. The line $GI$ meets $AC$ at $P$, also $EI$ and $AD$ meet at $Q$.
Prove that $PQ \parallel EF$[/color].[/quote][/quote]
I think he mean

[color=indigo][b]Proof.[/b] We have:
$\begin{cases}PI\perp AQ\\ IQ\perp AP\end{cases}\Longrightarrow G\;\textrm{is the orthocentre of triangle}\; AIP\Longrightarrow AI\perp QP$
On the otherhand, we have: $AI\perp EF\Longrightarrow PQ\parallel EF$[/color]

[quote="tjhance"][quote="April"][quote="Jan"][color=darkred]The incircle with center $I$ of $\Delta ABC$ touches it's sides $BC,\,AC,\,AB$ in $D,\,E,\,F$ respectively.  $EF$ meets $BC$ again in $G$. The line $GI$ meets $AC$ at $P$, also $EI$ and $AD$ meet at $Q$.
Prove that $PQ \parallel EF$[/color].[/quote]

[color=red]I like this problem very much and I always think about it. And now, I have another proof for it!  :lol:  [/color]

[hide="Very nice and simple proof."][color=indigo][b]Proof.[/b] We have:
$\begin{cases}PL\perp AQ\\ QE\perp AP\end{cases}\Longrightarrow \begin{cases}AI\perp QP\\ AI\perp EF\end{cases}\Longrightarrow PQ\parallel EF$[/color][/hide][/quote]

I must be missing something simple

but I can't see how $AI\perp QP$ or $AI\perp EF$[/quote]

[b] ANSWER[/b]

 I think it is well written ! See the figure :

Here is the pdf version of the solution.  :P

[b]Commen.[/b] I think the proof for the property $GI\perp AD$ is of [b]Mr. Virgil Nicula[/b]! :wink:


function
induction
inequalities
modular arithmetic
algebra
functional equation
algebra unsolved

Find all numbers k for which we can find a function defined on {1,2,...} with values in the same set such that $ f(f(f(n)))=f(n+1)+k $ for all natural numbers n.

At first I state the answer:

Given functional equation has solution for and only for odd $k\geqslant 1$ and $k=0$.

Proof goes in three parts.

1) Odd $k\geqslant -1$ or $k=0$

In this case the equation has a solution $f(n)=n+\frac{k+1}2$ for odd $k\geqslant -1$, and $f(n)=q$ ($q$ is an arbitrary constant) for $k=0$.

2) $k\leqslant -2$

I shall change the notation a bit for easir understanding. I will prove the following:

There is no $f: \mathbb{N}\to\mathbb{N}$ such that
\[ f(f(f(n)))=f(n+1)-k\quad(*)  \]
where $k\geqslant 2$ is given.

Proof:

By induction on $n$ we shall prove the following assertion:
\[ f(n)=\min f\big(\mathbb{N}\setminus\{1,\dots,n-1\}\big)\quad(**)  \]
Suppose that there is $n_0\geqslant 2$ such that $f(n_0)=\min f(\mathbb{N})$. Putting $n=n_0-1$ into $(*)$ we have
\[ f(f(f(n_0-1)))=f(n_0)-k  \]
and so we have got a contradiction. Therefore, the assertion is indeed valid for $n=1$. Suppose that it is valid for all numbers less than $n$ and prove the correctness for $n$. Again, we suppose that there is $n_1\geqslant n+1$ for which $(**)$ holds. Putting $n=n_1-1$ into $(*)$ we have:
\[ f(f(f(n_1-1)))=f(n_1)-k  \]
Notice that if $v\geqslant n$ then it must be $f(v)\geqslant n$, because $f(v)>f(n-1)>f(n-2)>\dots>f(2)>f(1)\geqslant 1$ (what follows from inductial assertions). Since $n_1-1\geqslant n$, hence $f(n_1-1)\geqslant n$, and so $f(f(n_1-1))\geqslant n$. That way we have got a contradiction, and the proof of assertion $(**)$ is completed. Notice that moreover the strict inequality holds, and that this assertion immediately implies that $f$ is monotone increasing.

Let a sequence $a_i$ be given by the reccurent formula $a_{i+1}=2a_i+2$, $a_1=1$. We shall prove by induction on $i$ that for each $i$ and all $n\geqslant 3$ holds the following assertion (which in turn implies nonexistence of $f$):
\[ f(n)\geqslant n+a_ik-a_i\quad(\star)  \]
Putting $n=1$ in equality $(*)$ we have $f(f(f(1)))=f(2)-k$, hence it must be $f(2)\geqslant k+1=2+k-1$, and since the function is increasing, for all $n\geqslant 2$ holds $f(n)\geqslant n+k-1$. Suppose that $(\star)$ holds for $i$. For any $n\geqslant 2$ from $(*)$ we have:
\[ f(n+1)=f(f(f(n)))+k\geqslant f(f(n+k-1))+k\geqslant f(n+(a_i+1)k-(a_i+1))+k\geqslant n+(2a_i+1)k-(2a_i+1)+k=(n+1)+(2a_i+2)k-(2a_i+2)=n+1+a_{i+1}k-a_{i+1}\blacksquare  \]

3) Even $k\geqslant 2$

Let $f(a)=f(b)$. Therefore, $f(f(f(a)))=f(f(f(b)))$, and so $f(a+1)+k=f(b+1)+k$ from what we get $f(a+1)=f(b+1)$, and by iterating we conclude that $f(a+j)=f(b+j)$ holds for all $j\in\mathbb{N}$. There are two possibilities: $f$ is either periodic (starting from some point) if $a\not=b$, or is injective.

Suppose that it is periodic. Therefore it has a finite set of values. Let $f(m)$ be the greatest one of them. If $m>1$ putting $n=m-1$ in the given functional equation we get $f(f(f(m-1)))>f(m)$, contradiction. Therefore, $f(1)$ is the unique greatest image. Let $f(l_2)$ be the second greatest one (not necessairly unique). From the starting equation we get $f(f(f(l_2-1)))=f(l_2)+k=f(1)$ (otherwise $f(l_2)$ wouldn't be the second greatest one), and since $f(1)$ is unique it follows that exists a number (in particular $f(f(l_2-1))$ is about) which corresponds to $1$. Also notice that the greatest two images differ precisely by $k$, and similar, if $f(l_3)$ is the third greatest one then it holds $f(f(f(l_3-1)))=f(l_3)+k=f(l_2)$ and the difference between the second and the third greatest ones is again $k$, and so on all the way through the end. Hence, the set of values of the considered function is the set $\{1+ik: 0\leqslant i\leqslant m\}$ for a natural number $m$, and $f(1)=1+mk$ holds. Let $t$ be the period.

Suppose that only $f(1)$ is out of the periodic part. In that case is $t=m$. Further, we have that it holds:
\[ f(f(f(t+1)))=f(t+2)+k=f(2)+k=f(f(f(1)))  \]
On the other hand, also holds $f(t+1)=f(kt+1)=f(f(1))$. From this and the preeceding it follows that $f(f(f(f(1))))=f(f(f(1)))$, what means that $f(f(f(1)))$ is a fixed point of this function. Let us try to find the first iteration of $f(1)$ which is the fixed point. Notice that it is impossible $f(1)=1$ and $f(f(1))=f(1)$ (the second one follows from the uniqueness of $f(1)$), and so we are left with $f(f(f(1)))=f(f(1))$ or $f(f(f(f(1))))=f(f(f(1)))$. In both cases we come to a situation that $f(ak+1)=f(bk+1)$ holds for different $0<a,b\leqslant t$. That further means $ak+1\equiv bk+1\pmod t$, what means $k(a-b)\equiv 0\pmod t$. Since $a-b\not\equiv 0\pmod t$ it must be $k\equiv 0\pmod t$. However, that means $1+k\equiv 1+2k\equiv\dots\equiv 1+tk\pmod t$. Therefore, all these numbers correspond to the same image, say $c$. It couldn't be $c=1$ because that would mean $f(f(f(f(1))))=1\neq 1+tk=f(f(f(1)))$. It holds $f(n)=1+ik$ for each $n\geqslant 2$. If $i=0$ then we have $f(f(n))=1+tk$, what means $f(f(f(n)))=c$, while for $i>0$ immediately holds $f(f(n))=c$ and therefore also $f(f(f(n)))=c$. However, that further means that for arbitrary different $n_1,n_2\geq 2$ we have $f(n_1+1)+k=f(n_2+1)+k$, and so also $f(n_1+1)=f(n_2+1)$. Contradiction.

Therefore, at least $f(2)$ also doesn't belong to periodic part, i. e. value $f(2)$ is unique. Let $f(2)=u$. If $u=1$ then from the uniqueness of $f(2)$ and the fact that $f(f(l_2-1))=1$ we have that $f(l_2-1)=2$. For $u>1$ choose $z$ such that $f(z)=u-k$. Putting $n=z-1$ in the starting functional equation we get $f(f(f(z-1)))=f(z)+k=u=f(2)$, and again from the uniqueness of $f(2)$ we have that $f(f(z-1))=2$. In both cases we have got a contradiction, because, as we have showed earlier, number $2$ doesn't belong to the set of values of the considered function.

Therefore, it is proved that $f$ is injection.

Let, further, $A=n\setminus f(\mathbb{N})$, $B=f(A)$ and $C=f(B)$. These sets are pairwise disjoint, and since $f$ is injection, it holds $|A|=|B|=|C|$. It is obvious that $B=f(\mathbb{N})\setminus f(f(\mathbb{N}))$ and $C=f(f(\mathbb{N}))\setminus f(f(f(\mathbb{N})))$. Since $\mathbb{N}\supseteq f(\mathbb{N})\supseteq f(f(\mathbb{N}))\supseteq f(f(f(\mathbb{N})))$, we have that $B\cup C=f(\mathbb{N})\setminus f(f(f(\mathbb{N})))$. Notice that from the given functional equation also follows $s\in f(f(f(\mathbb{N})))\iff s-k\in f(\mathbb{N})\setminus\{f(1)\}$.

For $0\leqslant i\leqslant k-1$ let us define $r_i=\min\{f(x): f(x)\equiv i\pmod k\}$. Denote also $r_k=\min\{f(1)+jk: f(1)+jk\in f(\mathbb{N}),j\in\mathbb{N}\}$. It could happen that an $r_i$ doesn't exist, in that case we simple ignore it onward. We claim that $B\cup C=\{r_i: 0\leqslant i\leqslant k\}$. For a starting point, it is obvious that $r_i\in f(\mathbb{N})$ for each $0\leqslant i\leqslant k$. On the other hand, if for an $i$ held $r_i\in f(f(f(\mathbb{N})))$ then we would have $r_i-k\in f(\mathbb{N})\setminus\{f(1)\}$, which is in contradiction with minimality of $r_i$. Let us now check whether an element different from every $r_i$ belongs to the considered union. Write it in form $x=r_k+jk$ if that is possible, otherwise if that is not possible in form $x=r_i+jk$ for an $0\leqslant i\leqslant k-1$, where $j\in\mathbb{N}$. Then it holds $x-k\in f(\mathbb{N})\setminus\{f(1)\}$, and it follows $x\in f(f(f(\mathbb{N})))$, hence $x\not\in B\cup C$.

Therefore, $B\cup C$ has finitely many elements, and hence it holds for $A$ too, i. e. all but finitely many natural numbers are contained in the set of values of the function $f$. We conclude that every $r_i$ exist, and hence $B\cup C$ has precisely $k+1$ elementes. However, since $B$ and $C$ are disjoint and with the same number of elements, their union must contain even number of elements, while $k+1$ is odd. Contradiction!$\blacksquare$

I read this solution again and found inapprehensible mistake. Fortunately, it could be (relatively simple) corrected.

[quote="Bojan Basic"]That further means $ak+1\equiv bk+1\pmod t$, what means $k(a-b)\equiv 0\pmod t$. Since $a-b\not\equiv 0\pmod t$ it must be $k\equiv 0\pmod t$. However, that means $1+k\equiv 1+2k\equiv\dots\equiv 1+tk\pmod t$. Therefore, all these numbers correspond to the same image, say $c$. It couldn't be $c=1$ because that would mean $f(f(f(f(1))))=1\neq 1+tk=f(f(f(1)))$. It holds $f(n)=1+ik$ for each $n\geqslant 2$. If $i=0$ then we have $f(f(n))=1+tk$, what means $f(f(f(n)))=c$, while for $i>0$ immediately holds $f(f(n))=c$ and therefore also $f(f(f(n)))=c$. However, that further means that for arbitrary different $n_{1},n_{2}\geq 2$ we have $f(n_{1}+1)+k=f(n_{2}+1)+k$, and so also $f(n_{1}+1)=f(n_{2}+1)$. Contradiction.[/quote]
Clearly, cancelling $a-b$ in the above congruence is not premitted, since we don't know whether $a-b$ and $t$ are coprime or not. (Counterexample: $4\cdot(4-1)\equiv 0\pmod 6$, but from this we could [b]not[/b] conclude that $4\equiv 0\pmod 6$.) This paragraph needs to be completely rewritten, i. e. like this.

Notice that it is not possible $t=2$, because in that case one would have $f(1)=2k+1$ and now whether one choose $f(2)=k+1$ and $f(3)=1$, whether $f(2)=1$ and $f(3)=k+1$, neither $f(f(1))$ nor $f(f(f(1)))$ would be a fixed point, and we have shown earlier that (at least) one of them is. Therefore, $t\geqslant 3$ (of course, it is clear that $t=1$ is impossible). Let us check for a moment what would happen if $a$ and $b$ are "inappropriate" (the meaning of this expression will soon become clear): if $\{a,b\}=\{1,t\}$, from $k+1\equiv tk+1\equiv 1\pmod t$ one has $k\equiv 0\pmod t$, and therefore $k+1\equiv (t-1)k+1\pmod t$ (remember, $t-1>1$ because $t\geqslant 3$!), what will be a congruence we shall regard if this case happens; if $b=t$ and $a>1$ (or the other way around), we shall simply regard congruence $(a-1)k+1\equiv (b-1)k+1\pmod t$. In the all cases (the original one and the two special ones) we have a congruence such that coefficients of $k$ are between $1$ and $t-1$ (those included). Notice now the numbers $p,q$ which correspond to, respectively, the left and the right side of the regarded congruence, such that $2\leqslant p,q\leqslant t+1$ (from the previous reasoning, it is clear that $p,q\neq 1$ and $f(p)=f(q)$). Now it is $f(p+1)=f(f(f(p)))-k=f(f(f(q)))-k=f(q+1)$. Because of $3\leqslant p+1,q+1\leqslant t+2$, it is clear that images of different numbers from this interval must be different, not the same one as we have just found. Contradiction.

[quote="Bojan Basic"]I read this solution again and found inapprehensible mistake. Fortunately, it could be (relatively simple) corrected.

[quote="Bojan Basic"]That further means $ak+1\equiv bk+1\pmod t$, what means $k(a-b)\equiv 0\pmod t$. Since $a-b\not\equiv 0\pmod t$ it must be $k\equiv 0\pmod t$. [/quote]
Clearly, cancelling $a-b$ in the above congruence is not premitted, since we don't know whether $a-b$ and $t$ are coprime or not. (Counterexample: $4\cdot(4-1)\equiv 0\pmod 6$, but from this we could [b]not[/b] conclude that $4\equiv 0\pmod 6$.) This paragraph needs to be completely rewritten, i. e. like this.[/quote]
Incredible proof!!!  :o
But you could also simply take $n\in\mathbb{N}$ with $f(f(n))=f(2)$ as in this paragraph
[quote="Bojan Basic"]
Therefore, at least $f(2)$ also doesn't belong to periodic part, i. e. value $f(2)$ is unique. Let $f(2)=u$. If $u=1$ then from the uniqueness of $f(2)$ and the fact that $f(f(l_{2}-1))=1$ we have that $f(l_{2}-1)=2$. For $u>1$ choose $z$ such that $f(z)=u-k$. Putting $n=z-1$ in the starting functional equation we get $f(f(f(z-1)))=f(z)+k=u=f(2)$, and again from the uniqueness of $f(2)$ we have that $f(f(z-1))=2$.[/quote]
and then $f(n)=1+ik$ for some $i\geq 0$ and $t|f(n)-2=ik-1$.
So $t$ and $k$ are coprime.

And then find $m,n\in\mathbb{N}$ with $f(m)\not =f(n)$ but $f(f(m))=f(f(n))$ as in
[quote="Bojan Basic"]
Suppose that only $f(1)$ is out of the periodic part. In that case is $t=m$. Further, we have that it holds:
\[f(f(f(t+1)))=f(t+2)+k=f(2)+k=f(f(f(1))) \]
On the other hand, also holds $f(t+1)=f(kt+1)=f(f(1))$. From this and the preeceding it follows that $f(f(f(f(1))))=f(f(f(1)))$, what means that $f(f(f(1)))$ is a fixed point of this function. Let us try to find the first iteration of $f(1)$ which is the fixed point. Notice that it is impossible $f(1)=1$ and $f(f(1))=f(1)$ (the second one follows from the uniqueness of $f(1)$), and so we are left with $f(f(f(1)))=f(f(1))$ or $f(f(f(f(1))))=f(f(f(1)))$.[/quote]
Then $f(m)\not =1\not =f(n)$, or else $f(f(m))=f(f(n))=f(1)$ and the uniqueness of $f(1)$ forces $f(m)=f(n)=1$. Contradiction!
So $f(m)=ak+1$ and $f(n)=bk+1$ for some $0<a,b\leq m=t$
and $f(f(m))=f(f(n))$ gives $t|f(m)-f(n)=(a-b)k$ and $t|a-b$, as $\gcd (t,k)=1$. Contradiction!
This shortens your original proof a little. :)  Again incredible work!

Only one more thing.
If $a,b\in\mathbb{N},a<b$ with $f(a)=f(b)$ and $a+b$ minimal, then $f(1),f(2),\ldots, f(b-1)$ are pairwise distinct
and $\forall x,y\in\mathbb{N}: f(x)=f(y)\Rightarrow x\equiv y \pmod{b-a}$.
This is easy but not trivial.  :wink:

Yup, this indeed shortens my proof a little, but it is still very long and, I dare to say, a pretty boring one. :)

I noticed just a minor detail, I believe a typo:

[quote="olorin"]...and then $f(n)=1+ik$ for some $i\geq 0$...[/quote]
Probably: $i\geqslant 1$.

Also:
[quote="olorin"]So $f(m)=ak+1$ and $f(n)=bk+1$ for some $0<a,b\leq m=t$[/quote]
The first and the second $m$ do not represent the same value ;) (an other letter would be more convenient, but nevermind, I undestood the point).

[quote="olorin"]Only one more thing.
If $a,b\in\mathbb{N},a<b$ with $f(a)=f(b)$ and $a+b$ minimal, then $f(1),f(2),\ldots, f(b-1)$ are pairwise distinct
and $\forall x,y\in\mathbb{N}: f(x)=f(y)\Rightarrow x\equiv y \pmod{b-a}$.
This is easy but not trivial.  :wink:[/quote]
This was used extensively during the course of the proof. :) Actually, it directly follows from this paragraph:

[quote="Bojan Basic"]Let $f(a)=f(b)$. Therefore, $f(f(f(a)))=f(f(f(b)))$, and so $f(a+1)+k=f(b+1)+k$ from what we get $f(a+1)=f(b+1)$, and by iterating we conclude that $f(a+j)=f(b+j)$ holds for all $j\in\mathbb{N}$.[/quote]

Anyway, I am really glad that you liked the proof, a whole year passed till the first comment here. :)

An acquaintance of mine found a (much) simpler way to show that $f$ cannot be periodic (and hence, that it is an injection).

His idea starts immediately after we show that the set of values is $\{1+ik: 0\leqslant i\leqslant m\}$. Notice that from $f(f(f(n)))=f(n+1)+k$ it follows that there is no $n$ such that $f(f(f(n)))=1$. On the other hand, since $f(l_{2}-1)\neq 1$ (otherwise it would not be possible $f(f(l_{2}-1))=1$) it follows that there is an $m_{0}>1$ such that $f(m_{0})=f(l)-k$; hence $f(f(f(m_{0}-1)))=f(m_{0})+k=f(l)$, and now from $f(f(l_{2}-1))=1$ it follows $f(f(f(f(m_{0}-1))))=1$. Contradiction!


algebra
polynomial
function
quadratics
number theory
relatively prime

I can't figure this thing out:

The equation $x^6-3x^5-x^3-x+8=0$ has

(A) no real roots
(B) exactly two distinct negative roots
(C) exactly one negative root
(D) no negative roots but at least one positive root
(E) none of these

and also:

A polynomial $p(x)$ has a remainder three when divided by $x-1$ and remainder five when divided by $x-3$.  The remainder when $p(x)$ is divided by $(x-1)(x-3)$ is

(A) $x-2$
(B) $x+2$
(C) $2$
(D) $8$
(E) $15$

thanks

For 1, [hide]you have to count the number of sign changes. Since there are two sign changes, there are either 2 or 0 positive roots. Then change x to -x and count the sign changes for negative roots. There are no sign changes, so there are no negative roots.
We see that there must be two real roots because when we substitute in 2, it's negative, and since there are definitely positive values, there is at least one real root.
So the answer is D.[/hide]

[quote="Iversonfan2005"]Number 2:
[hide]
$(x-1)n1+3=p(x)$
$(x-3)n2+5=p(x)$

I'm assuming it's linear function right?
 ;) So, $p(1)=3 \Longrightarrow a+b=3$
$p(3)=5 \Longrightarrow 3a+b=5$, so $a=1, b=2 \Longrightarrow p(x)=x+2$[/hide]

Number 1:[hide]

Notice that if we we have a negative root, then then the result will always be positive and $>0$, so a negative root is impossible, but since it's a sixth degree polynomial, there are $6$ possible roots and atleast one is positive real root. [/hide][/quote]

for number 2, it doesnt say it has to be a linear funtion

for number 1, how do you know it doesnt have 6 imaginary roots?

1.

[hide]
If you use synthetic substitution, you get f(1)=4 and f(2)=-40, so you know for a fact that there is at least one real root between 1 and 2.  And if you use Descartes' Rule of Signs, you get that there cannot be any negative roots.  Therefore, the answer is [b] (D) no negative roots but at least one positive root [/b].
[/hide]

[hide="2"]Q(x)(x-1)+3=P(x)
R(x)(x-3)+5=P(x)
now to find out the remainder  when P(x) is divided by (x-1)(x-3), we find what Q(x) is in modulo x-3, multiply that by x-1, and add 3

so Q(x)(x-1)+3=R(x)(x-3)+5 and that implies that
(Q(x)-1)(x-1)+(x+2)=(R(x)-1)(x-3)+(x+2)
thus (Q(X)-1)(x-1)=(R(x)-1)(x-3).
Since x-1 and x-3 are relatively prime, then Q(x)-1 is divisible by x-3
thus Q(x) gives remainder 1
thus  1(x-1)+3=x+2

so our answer is B[/hide]

[quote="F u r u y á"][hide][b]2)[/b]
$P(x) = (x - 1)Q_1(x) + 3$
$P(1) = 3$ (I)

$P(x) = (x - 3)Q_2(x) + 5$
$P(3) = 5$ (II)

Since the rest's degree is zero and the dividor's degree is one, we can say that $P(x)$ degree is one and $P(x)$ is in the form $P(x) = ax + b$. From (I) and (II) we can mount a system to find $a$ and $b$:
$P(x) = ax + b$
$P(1) = a + b = 3$
$P(3) = 3a + b = 5$
So $a = 1$ and $b = 2$. $P(x) = x + 2$

Therefore, when $P(x)$ is divided by $(x - 1)(x - 3)$ we get the quotient $Q_3 = 0$ and the rest $R(x) = P(x) = x + 2$, which give us the alternative (B)[/hide][/quote]
how can you say P(x) is of degree one? How do you know you wont get a different answer if its degree two?

[quote="chesspro"][hide="1"]Another thing you could use here is the Rational Roots Theorem, which says that if you have some polynomial

$ax^n + bx^{n-1} + \cdots + C = 0$

then all possible real roots must be

$\displaystyle \pm \frac{\text{factor of C}}{\text{factor of a}}$

Although it's probably not the best way here, it could help for other problems.[/hide][/quote]

there are no rational roots

[quote="Scrambled"][quote="hmoonster"][hide="2"]
$P(x)=(x-1)(x-3)Q(x)+ax+b$
$P(1)=a+b=3$
$P(3)=3a+b=5$
 $a=1$, $b=2$
so the remainder is $x+2$
[/hide]
$P(x)$ is not a linear function but the remainders are. You don't get a different answer if it is of higher degree because the terms of higher degree *magically* cancel out.[/quote]
uh, how so?[/quote]
Yes, how do you know you can treat it as linear?

If you've noticed my solution, P(x) can be of any degree (because I have not defined what Q(x) is). The only thing I'm treating as linear is the remainder because P(x) is divided by a quadratic factor.

P(x)=(x-1)(x-3)Q(x)+ax+b
we don't know what Q(x) is but we know that the remainder is linear
for P(1) we change all x's into 1 so
P(1)=(1-1)(1-3)Q(1)+a(1)+b
whatever Q is it does not matter because it is being multiplied by zero
so the remainder is just the linear part a+b
same when you plug in 3.

That's what I meant by *magically* cancels out.

Hope this answers your questions.


How many ordered pairs of integers (a,b) satisfy a^2+b^2=17?

c'mon Tare

Look at the question again

it says a^2+b^2

[quote]c'mon Tare

Look at the question again [/quote]

tsk, tsk. I'm tellin ya, those misreads will really screw up that 150 on the AMC.  8-)

Wait, I don't get what I did wrong...

And FYI, I got a measly 100 last year, so don't expect anything brilliant from me.

Well, actually, I am not sure whether you misread the problem. The only four numbers you are dealing with are -4, -1, 1, and 4, whose squares are 1 and 16. However you included references to -16 in your original solution, so I was a bit confused. Sorry if you actually read and did it correctly the first time.

No, see Tare was half right

he correctly deduced that 1 and 16 are the needed square, but he forgot one vital information: 1 and 16 are the [i]squares[/i]needed.

yea

just be careful about the problem

always read the problem carefully

*sigh* I know, I know. I also need to whack in the fact that 1 isn't prime and 0 is composite.

yea, but zero is pretty weird.

Anyway, there's only 2 to memorize. I think u can handle that :wink:

See, the hard part is my intuitive side tells me 1 is a prime every time. For me, the law of cosine is [b]much [/b]much easier to memorize than the fact that 1 isn't a prime nor composite.

Yes, I know. I'm stupid. :o *drool*

Ok here it is (spoiler):

[hide]a^2 + b^2 = 17.

(a,b) are positive integers.

a    l    b

----------

1    l    4

2    l    (sqrt 13)

3    l    2 (sqrt 2)   Out of this table, (1,4) is the only one that works.

It could also be (1,4), (1, -4), (-1, 4), (-1, -4) so that's 4 results there.  But since order matters, multiply by two to get 8.[/hide]

Um, Tare, i suggest you can stop spamming now. After all, if you go at this rate, ur gonna exceed ComplexZeta pretty soon! :D


Show that the length of the latus rectum of an ellipse whose equation is $\frac{x^{2}}{a^{2}}+\frac{y^{2}}{b^{2}}= 1$, $a>b$, is $\frac{2b^{2}}{a}$.

So the latus rectum for an ellipse is the line segment that goes through the focus that is parallel to the minor axis, this means that we are looking for some point $(c,y)$ (if we assume the focus is at the point $(c,0)$) that lies on the ellipse:

$\frac{c^{2}}{a^{2}}+\frac{y^{2}}{b^{2}}= 1$

$y^{2}a^{2}= a^{2}b^{2}-c^{2}b^{2}$

There is a proof to show that $c^{2}=a^{2}-b^{2}$ (where $c$ is the x coordinate of the focus and $a$ and $b$ are the x and y coordinates of the major and minor arcs respectively) which I won't prove now, assume it is fact (and since you are probably getting these questions from vol. 2, it's proved there).

$y^{2}= \frac{b^{2}(a^{2}-c^{2})}{a^{2}}$

$y^{2}= \frac{b^{4}}{a^{2}}$

$y = \frac{b^{2}}{a}$

But this is only the distance from the x axis to the point (c,y) so we double it:

$\frac{2b^{2}}{a}$

This was probably a lame explanation, do with it what you will.

whoa.. that was good.

Actually, this and another post I posted a few hours ago are both from my precalculus homework that I didn't get how to start :blush: and I just looked at the AoPS VII.. has a similar thing.. hopefully I can understand the rest of that chapter and not have to post anything else for today.

Thanks for the help!


induction algebra polynomial vector calculus integration function

Hello,
I try to solve this exercise :
\[ A_1=\mathbb{C}[X,Y]/(X-Y,XY-1)\\ A_2=\mathbb{C}[X]/((X-1)^2)\\ A_3=\mathbb{C}\times \mathbb{C}\\ A_4=\mathbb{C}[X,Y]\\ A_5=\mathbb{C}[X]/(X^2) \]
I need to find which rings are isomorph.

I have shown that $A_2=A_3$ with morphism $P\rightarrow (P(1),P'(1))$, $A_4$ is alone (how can I prove it ?), I think $A_1=A_2=A_3=A_5$ so I need to show $A_1=A_2$ or $A_3$ (how ?) and $A_5=A_2$ (using $P\rightarrow Q, P(X)=Q(X+1)$ ?).

Thanks !

uhm..
i think $A_1 \cong A_3$, $A_2 \cong A_5$, and $A_4$ stands all alone..
well, it's kind of easy to see that $A_4$ is the only infinite space on $\mathbb{C}$, so it can't be isomorph to any other one.
as regarding 2-5, you can send $1\mapsto 1, x-1 \mapsto x$, and verify it's an isomorphism.
1-3... hm.. call it intuition, i think sending $f \mapsto (f(1), f(-1))$ should work.. but i didn't verify..
the fact that 1-3 is not isomorph to 2-5 can be seen since no elements in $\mathbb{C}^2$ are nilpotent, except for $(0,0)$.
let me know if it's working, i didn't actually check.

Clarifications: The isomorphism from $A_1$ to $A_3$ is $\phi(f)= (f(1,1),f(-1,-1)$. It is easy to show that this is a surjective homomorphism.
Since $x^2-1=x(x-y)+(xy-1)$, $y^2-1=-y(x-y)+(xy-1)$, and $xy-1=1(xy-1)$, we have $x^2\equiv 1$, $y^2\equiv 1$, and $xy\equiv 1$ mod $I=(x-y,xy-1)$. By induction, we have that for each polynomial $p$, there is a polynomial $q$ of degree at most 1 such that $p\equiv q\mod I$. This $q$ can be further reduced to depend only on $x$, and it is clear that the family $a+bx$ maps injectively to $\mathbb{C}^2$.

This leaves the isolation of $A_4$. $A_4$ is infinite-dimensional as a vector space over $\mathbb{C}$, which would obviously be enough if we were talking about $\mathbb{C}$-algebras.
We're not, so we need to find some ring properties. There are no nilpotent elements, so  $A_4$ is not isomorphic to $A_2$ or $A_5$. $A_3$ has exactly two nontrivial ideals ($C\times 0$ and $0\times C$), with all other elements invertible. $A_4$ has infinitely many ideals, including infinitely many maximal ideals $(x-c)$. Therefore, $A_4$ is not isomorphic to $A_1$ or $A_3$.

yes, sorry.. i was thinking to write that $A_1 \cong \mathbb{C}[x]/(x^2-1)$, but i forgot :s
anyway.. could you please explain why it's not enough saying that $A_4$ is an infinite dimensional vector space over $C$? thanks...

It is (I think) possible to construct a proper subfield of $\mathbb{C}$ which is isomorphic to $\mathbb{C}$. If $\mathbb{C}$ is an infinite-dimensional complex vector space, we're not getting anywhere.

thanks, you're right... anyway... couldn't we just say that $A_4$ is an integral (integer? entire?) domain? (i.e. no $0$ divisors)

by the way.. i was thinking about a measure-theoretic proof that you can't find a subfield $\mathbb{E} <_F \mathbb{C}^2$ such that $\mathbb{E}[x,y] \cong \mathbb{C}^2$. consider the isomorphism $\Phi: \mathbb{E}[x,y] \to \mathbb{C}^2$.
$\Phi(\mathbb{E})$ is a proper subfield of $\mathbb{C}^2$.
but every proper subfield of $\mathbb{C}$ is either with null measure, either the whole $\mathbb{C}$, either non-measurable, then you can't have that isomorphism... is it working?

The integral domain/entire ring idea is the simplest version here. I don't think measure does anything interesting.

Thanks,
$A_2=A_3$ ? Else where is it false ?

For $1-3$, is it true to write this:
In $A_1$, elements are like $a+bX$ since $X=Y$ and $XY=1$ then $X^2=1$ ?
Then we use $a+bX\rightarrow (a,b)$, it's easily bijectiv ?
It looks too simple ... ?!

the fact is that it's not an isomorphism of rings, but just of additive groups: in $A_3$ you don't have any inverse for an element $(a,0)$ with $a\neq 0$, while in $A_1$ you have $(a,0)\cdot (a^{-1},0) = 1$ (where $1 = (1,0)$ is the unity of $A_1$).


probability
real analysis
algebra
polynomial
probability and stats

4 dice are rolled.Probability that the sum is 18 :(

Yes Right.But this not the way I was looking forward to

There is another way

find coefficient of x^18 in the expansion of (x+x^2+x^3+x^4+..x^6)^4
and you will have your ans.I figured it out some days latter   :|

Build an array. The first row has the elements $ 1,1,1,1,1,1.$
Starting with the second row, let each element be the sum of the first 6 elements to the left of that on the line above. The second row has its first nonzero element in the third position, and goes $ 1,2,3,4,5,6,5,4,3,2,1.$

The third row starts at the third position:
$ 1,3,6,10,15,21,25,27,27,25,21,15,10,6,3,1.$

The fourth row starts at the fourth position:
$ 1,4,10,20,35,56,80,104,125,140,146,140,125,104,80,56,35,20,10,4,1$

Those are the numerators of probabilities; we only need to divide by $ 6^n$ to get the probability. The item in the fourth row, 18th position is $ 80.$ Hence the probability of rolling the $ 18$ with four dice is $ \frac{80}{6^4}\equal{}\frac{80}{1296}\equal{}\frac{5}{81}.$

What I'm doing is computing a convolution; it's very closely related to what the previous poster said. It's a snap to do this on a spreadsheet and not too hard to do the arithmetic by hand.

a funny easy exercice related to this one: is this possible to load $ 2$ different dices in such a manner that each of the sums $ 2,3, \ldots, 12$ comes up with the same probability ?

To answer alekk, I'll go back to JamesBond007's approach - the generating function.

Do there exist probability assignments $ p_k$ and $ q_k$ such that $ p_k\ge 0,q_k\ge0$ and $ \sum_{k \equal{} 1}^6p_k \equal{} \sum_{k \equal{} 1}^6q_k \equal{} 1$ such that

$ \left(\sum_{k \equal{} 1}^6p_kx^k\right) \left(\sum_{k \equal{} 1}^6q_kx^k\right) \equal{} \frac1{11}\sum_{n \equal{} 2}^{12}x^n?$

The first thing I'll do is factor out some common powers of $ x$ to get

$ \left(\sum_{k \equal{} 0}^5p_{k \plus{} 1}x^k\right) \left(\sum_{k \equal{} 0}^5q_{k \plus{} 1}x^k\right) \equal{} \frac1{11}\sum_{n \equal{} 0}^{10}x^n \equal{} \frac {x^{11} \minus{} 1}{11(x \minus{} 1)}.$

On the left side of this, we have two real fifth degree polynomials. A real fifth degree polynomial must have at least one real root; any root of either of the polynomials on the left would then be a root of the polynomial on the right. But the tenth degree polynomial $ \frac {x^{11} \minus{} 1}{x \minus{} 1}$ has no real roots. That by itself shows that we cannot solve these equations.

To answer alekk: no, we cannot find such a loading.


Lately I have seen a lot of problems posted which are pretty obviously homework problems for a class. I think we need to give a really clear message to people that they cannot do that sort of thing -- we're not here to do people's homework. I don't spend much time in HSB, but I imagine the same thing applies there too. While there is no really good way to make sure people are not posting their homework, we should at least refrain from solving a suspicious question (i.e. unsourced, relatively easy, time limit, low post count poster) until the poster has given us a direct answer that it is not a homework problem. It's obviously a bad thing if someone is giving their teacher solutions from AoPS and not from their own brain. Obviously I have no problems with asking for broad help on topics, but specific questions is going a bit far.

Any thoughts? Any other ideas for controlling this?

Either a)Just don't respond or b) give a hint

...as long as the person is respectful, and is trying to get the problem, then there should be no problem...i agree that just solving the problem is wrong...also many people are posting extra credit things...we should not be solving those for kids

a previous comment from one of the admins said not to discourage this...i am not really sure what the deal is...but i can infer that the admins want to encourage people come to the boards...people who come here for homework help might also be exposed to other problems...not sure about that though

i would advocate a homework help forum...that way we could isolate all the [...] that gets posted elsewhere...but i don't see this happening

I think posting homework problems is perfectly fine; after all this is a forum.  However, homework problems should be clearly cited as such to prevent direct solutions of the problems.

So all in all I completely agree that people posting hints is far more beneficial to the homework poster in question than simply posting an answer.


Prove that a convex polygon can be divided into two polygons such that their interiors don't meet.

[quote="Rushil"]Basically we wish to prove $ \exists $ such a diagonal before actually drawing one.[/quote]This is an absurdity. Topic closed.


calculus
integration
topology
function
symmetry
real analysis
limit

I am taking a course on integration theory this semester, and I just started reading the text today (Foundations of Modern Analysis by Friedman). On the second page Friedman efines the superior limit of a sequence of sets $\{E_{n}\}$ (subsets of a set $X$).

The analogy with other lim sup concepts I've seen so far are clear (for example: lim sup of real sequences, or real functions). By definition $\{E_{n}\}$ has a limit iff lim sup and lim inf are equal, and the limit exists for any monotone sequence of sets.

However, I'd like a clearer picture of the analogy. Is the lim sup for real sequences a special case of lim sup for sets? Or do I need to wait for my course in topology to get the bigger picture on lim sups?

[quote="Kalle"]
However, I'd like a clearer picture of the analogy. Is the lim sup for real sequences a special case of lim sup for sets?
[/quote]
Let $x_{k}$ be a sequence of numbers and let $E_{k}=(-\infty, x_{k})$. Then $\limsup E_{k}$ is almost the same as $(-\infty,\limsup x_{k})$ (up to the inclusion of the right endpoint). So, if you know $\limsup E_{k}$, you surely know $\limsup x_{k}$.

[quote]
Or do I need to wait for my course in topology to get the bigger picture on lim sups?[/quote]
As far as I remember my courses in topology, none of them added anything to what I knew about $\limsup$'s (not that there is much to know about them :P). This construction (for sets) is quite a useful tool in measure theory and once you understand how it is used there, in my opinion, there will be nothing to add to your perception of the concept.

Let $\chi_{E}$ be the characteristic function of $E$; that is, $\chi_{E}(x)=1$ for $x\in E$ and $\chi_{E}(x)=0$ otherwise. It is easy to see that
$\chi_{\limsup E_{n}}=\limsup \chi_{E_{n}}$ and $\chi_{\liminf E_{n}}=\liminf \chi_{E_{n}}$. Thus, $\limsup$ and $\liminf$ for sets are special cases of $\limsup$ and $\liminf$ for real-valued functions.

Thanks guys. I still don't feel comfortable with the concepts; I don't feel like I see "symmetry" in the definitions, or how they naturally occur. Of course it's hard to pin-point what my issue is. That's the way I've always felt with lim sups, that I don't understand them because they don't feel natural to me.

Nothing is natural when you see it for the first time, not even natural numbers. :)

The symmetry in the definitions becomes apparent if you look at the definition of $\sup$ or $\inf$ first. What is $\sup Y_{k}$? It is just such $Y$ that every $Y_{k}$ is smaller than or equal to $Y$, and no smaller $Y'$ satisfies this property. Note that I used the language that can be equally well applied to numbers and to sets (except no one calls such a $Y$ for sets a supremum; it is usually called a union). The same with $\inf$. And once we have both $\sup$ and $\inf$, we can define $\limsup$ using [b]exactly the same words[/b] for sets and for numbers.

As to the "naturalness" of the concept of $\limsup$ itself, it is just "rich man's $\sup$". By "rich" I mean that he doesn't need to care about any finite number of elements in his sequence and  is always ready to throw them away. In the case of $\limsup_{x\to x_{0}}$ he is even ready to throw away everything except an arbitrarily small neighborhood of $x_{0}$, which he wants to keep for himself.

This idea of not caring much about finitely many elements in the sequence is the same as in the concept of the limit, say. What is a sequence with a limit? It is just a "rich man's almost constant sequence": if he throws away a few (finitely many) elements, he will hardly be able to see the difference between each element in his sequence and its limit value. The same with Cauchy sequences except now one has to say that "he will hardly be able to see the difference between any two elements in his sequence" instead. This idea of "rich man" is one of the central things in analysis and, in my opinion, it is not very unnatural (though not completely trivial either).

Of course, this explanation assumes that you are completely comfortable with $\sup$. If not, you'd better start there.

If something of the above sounds unclear, just ask a question. If everything I said is completely clear, I do not see why you think that you don't feel comfortable with the concept: there is nothing in it beyond what I said above and all you may need then is to go through a series of exercises of various degrees of difficulty involving the concept to get a really good grasp of it.

[quote="fedja"]
The symmetry in the definitions becomes apparent if you look at the definition of $\sup$ or $\inf$ first. What is $\sup Y_{k}$? It is just such $Y$ that every $Y_{k}$ is smaller than or equal to $Y$, and no smaller $Y'$ satisfies this property. Note that I used the language that can be equally well applied to numbers and to sets (except no one calls such a $Y$ for sets a supremum; it is usually called a union). The same with $\inf$. And once we have both $\sup$ and $\inf$, we can define $\limsup$ using [b]exactly the same words[/b] for sets and for numbers.
[/quote]
Wow, now I completely understand the analogy! My book just says that $\limsup Y_{k}$ is the set containing those elements which are contained in infinitely many $Y_{k}$. I did not think of $\limsup Y_{k}= \cap_{k=1}^\infty \cup_{n\ge k}Y_{n}$ until today, and I also did not realize that $\sup$ is like union. Doesn't it make a difference that real numbers have an order relation between every element while sets only between some, though?

Another thing I need some help with is the concept of a limit of a sequence of sets. Today I learned the result that for monotone sequences, you can pass limits through measures. However, I really don't feel that I understand what the limit of a sequence of sets is. Can it also be visualized in terms of the (partial) order relation? Is it natural that measures preserve limits? Do we have limit laws for sequences of sets, for example for set differences and unions (something like this seems to be understood in my textbook)?

I realize I am asking many questions and it seems like I should spend time thinking through these things myself. However, I only have a finite amount of time and so far I've spent like 10 hours trying to work through 7 pages. I don't think I am mature enough for the book; it's all definitions and proofs without providing any help. I really appreciate your long explanation!

edit: Would it help to think of some concrete space like $R^{2}$ while reading about measure theory? So far I have just seen the space as any abstract set and that hasn't provided me with much of an understanding of what I am doing.

Well, the primary lemmas about passing limits of sets through measure involve monotone sequences of set. For an increasing sequence of sets (each one contained in the next), the limit is the union. For a decreasing sequence of sets (each one containing the next), the limit is the intersection, and the measure theory lemma has an additional hypothesis about starting from finite measure.

In general, we can define the limit of a sequence of set to be equal to both the limsup and the liminf, provided those coincide. Note that that's a difficult condition to satisfy, and that it would be unusual for a sequence of sets to have a limit.

[quote="Kent Merryfield"]
In general, we can define the limit of a sequence of set to be equal to both the limsup and the liminf, provided those coincide. Note that that's a difficult condition to satisfy, and that it would be unusual for a sequence of sets to have a limit.[/quote]
Yes, this is exactly the definition I am talking about. I cannot visualize it at all. What does it mean?

If $A=\lim A_{n},$ then every point outside $A$ is in at most finitely many of the $A_{n}$ and every point inside $A$ is in at least all but finitely many of the $A_{n}.$

In the special case of an increasing sequence, with the limit being the union, points outside of $A$ are in none of the $A_{n}$, whereas point inside $A$ are in some $A_{n},$ which is contained in $A_{m}$ for $m>n.$ We could say that it if $x\in A,$ then it is eventually true that $x\in A_{n}.$

In the special case of a decreasing sequence, with the limit being the intersection, points inside of $A$ are are in all of the $A_{n},$ whereas for points outside $A,$ there is some $A_{n}$ such that $x\not\in A_{n},$ which imples that $x\not\in A_{m}$ for $m>n.$

There's a concept of the symmetric difference of sets: $A\Delta B=(A\cup B)\setminus (A\cap B)=(A\setminus B)\cup (B\setminus A).$ This measures how different $A$ and $B$ are; after all $A=B\iff A\Delta B=\emptyset.$

We should have $\lim A_{n}=A$ iff $\limsup(A_{n}\Delta A)=\emptyset.$

[quote="Kent Merryfield"]
In general, we can define the limit of a sequence of set to be equal to both the limsup and the liminf, provided those coincide. Note that that's a difficult condition to satisfy, and that it would be unusual for a sequence of sets to have a limit.[/quote]

Is this the default notion of limit of a sequence of sets?  For example, convergence in $L^{1}$ or $L^{1}_{\loc}$ of the characteristic functions of sets (in $\mathbb{R}^{n}$) seems like a fairly reasonable notion of convergence to me, as does pointwise convergence of the characteristic functions (this may be equivalent to your definition), I'm too lazy to see whether it is actually the same.

It's equivalent to pointwise (everywhere!) convergence of the characteristic functions. These notions of limsup, liminf, or limit of a sequence of sets are purely set theoretic concepts, even though they commonly appear in measure and integration courses. You don't want to be bringing notions of measure (or integral, or $L^{1}$ norm) into it.

[quote="Kent Merryfield"]Well, the primary lemmas about passing limits of sets through measure involve monotone sequences of sets. [/quote]
Once you get familiar with these lemmas, it is a good and fairly simple exercise to show that, for arbitrary sequences of measurable subsets $E_{n}$ of a finite measure space $X$, one has
\[\mu(\limsup E_{n})\ge \limsup\mu(E_{n})\ge \liminf\mu(E_{n})\ge \mu(\liminf E_{n})\,.\]
Not that this chain of inequalities is used often, but it completes the statements about passing limits of sets through measure. Note that if our sequence of sets has a limit, it follows immediately that you can exchange the operations of taking measure and passing to the limit.

Thanks to everyone participating in this thread. It cleared up a lot of things for me.

Is it true that if $\lim A_{n}= A$ and $\lim B_{n}= B$ then $\lim (A_{n}-B_{n}) = A-B$? I can't figure out how to prove or disprove

\setminus is the right $\LaTeX$ code for the set difference operation.

Yes, it is true. The best way to think of it is to follow Kent's description of the limit: $x\in A$ iff $x\in A_{n}$ for all sufficiently large $n$, $x\notin A$ iff $x\notin A_{n}$ for all sufficiently large $n$ and similarly for $B$. So, to say that something is (is not) in $\lim A_{n}$ is the same as to say that it is (is not) in all but finitely many $A_{n}$. On this way, you can easily see that you can pass to the limit in any reasonable set-theoretic operation like union, intersection, difference, and Cartesian product of finitely many sets. You can even use the operation of taking the set of all finite subsets! But infinite Cartesian products and power sets cannot be passed through limits; can you see why?

Alternatively, you can try to prove first that
\[\limsup (A_{n}\setminus B_{n})\subset \limsup A_{n}\setminus\liminf B_{n}\]
and
\[\liminf (A_{n}\setminus B_{n})\supset \liminf A_{n}\setminus\limsup B_{n}\]
(I hope I placed $\sup$s and $\inf$s the right way here :lol:).

I have done some study of limits of sequences of sets: most fruitful has been [u]Measure Theory[/u], by Halmos, in which the limit of a sequence of sets is defined as the set $A = \liminf A_{n}= \limsup A_{n}$, where the upper and lower limits of a sequence of sets $\left\{ A_{n}\right\}$ are defined by

$\liminf A_{n}= \bigcup_{j=1}^{\infty}\bigcap_{k=j}^{\infty}A_{k}$

and

$\limsup A_{n}= \bigcap_{j=1}^{\infty}\bigcup_{k=j}^{\infty}A_{k}$

[quote="Kent Merryfield"]Those are the same definitions that we've been working with for the whole topic. I had assumed that Kalle started with these definitions (the ones benorin just gave) and was looking for other ways to look at it.[/quote]

Ah! Well here you go:

\[\limsup_{n\to\infty}A_{n}= \left\{ x | x\in \mbox{ infinitely many }A_{n}\right\}\]

and

\[\liminf_{n\to\infty}A_{n}= \left\{ x | x\in \mbox{ all but finitely many }A_{n}\right\}\]

Also, some special cases are:

i. If $A_{2n+1}=A$ and $A_{2n}=B$ so that $\left\{ A_{n}\right\}=\left\{ A,B,A,B,\ldots\right\}$, then $\limsup_{n\to\infty}A_{n}=A\cup B$ and $\liminf_{n\to\infty}A_{n}=A\cap B$ and hence such a sequence of sets converges iff $A=B$.

ii. If $\left\{ A_{n}\right\}$ is a decreasing sequence of sets ($A_{n+1}\subset A_{n}$ for $n=1,2,3,\ldots$), then $\lim_{n\to\infty}A_{n}=\bigcap_{n=1}^{\infty}A_{n}$.

iii. If $\left\{ B_{n}\right\}$ is an increasing sequence of sets ($B_{n}\subset B_{n+1}$ for $n=1,2,3,\ldots$), then $\lim_{n\to\infty}B_{n}=\bigcup_{n=1}^{\infty}B_{n}$.

proof:

i. \[\limsup_{n\to\infty}A_{n}= \left\{ x | x\in \mbox{ infinitely many }A_{n}\right\}\]
\[= \left\{ x | x\in A\mbox{ or }x\in B\right\}= \left\{ x | x\in A\cup B\right\}= A\cup B\]

and

\[\liminf_{n\to\infty}A_{n}= \left\{ x | x\in \mbox{ all but finitely many }A_{n}\right\}\]
\[=\left\{ x | x\in A\mbox{ and }x\in B\right\}=\left\{ x | x\in A\cap B\right\}=A\cap B\]

since, in this case, if $x\in A_{n}$ for any $n$, then $x\in A_{n}$ for infinitely many $n$ so that either $x\in\mbox{ infinitely many }A_{n}$ or $x\nin A_{n}$.

Clearly $\limsup_{n\to\infty}A_{n}=\liminf_{n\to\infty}A_{n}$ iff $A\cap B=A\cup B\Rightarrow A=B$.

ii. $A_{n+1}\subset A_{n}\Rightarrow \bigcup_{m=n}^{\infty}A_{m}=A_{n}$ so $\limsup_{n\to\infty}A_{n}= \bigcap_{n=1}^{\infty}\bigcup_{m=n}^{\infty}A_{m}=\bigcap_{n=1}^{\infty}A_{n}$.
Also $\liminf_{n\to\infty}A_{n}= \bigcup_{n=1}^{\infty}\bigcap_{m=n}^{\infty}A_{m}=\bigcap_{n=1}^{\infty}A_{n}$.

$\lim_{n\to\infty}A_{n}=\bigcap_{n=1}^{\infty}A_{n}$.

I'm tired...


combinatorial geometry
combinatorics unsolved
combinatorics

Find the greatest possible integer $n$ such that one can place $n$ points in a plane with no three on a line, and color each of them either red, green, or yellow so that:
(i) inside each triangle with all vertices red there is a green point.
(ii) inside each triangle with all vertices green there is a yellow point.
(iii) inside each triangle with all vertices yellow there is a red point.

I claim that the answer is 18.

Define $ R,G,Y$ to be the set of red, green, and yellow points, respectively.  For any set of points $S,$ let $I(S)$ denote the interior of the convex hull of $S$.

Lemma:
 \[ |G \cap I(R)| \ge |R|+|R \cap I(R)|-2 \,.\]
Proof:
  Triangulate $ R$, and consider the triangulation as a graph.  There are $ |R|$ vertices.  Let $ f$ be the number of faces.  The outer face has $ |R|-|R \cap I(R)|$ sides, and the other faces have three sides.  So there are $ \frac{3(f-1)+(|R|-|R \cap I(R))}{2}$ edges.  By Euler's formula, we have
\[ f+|R|-2=\frac{3(f-1)+(|R|-|R \cap I(R)|)}{2} \,, \]
which implies
\[ f=|R|+|R \cap I(R)|-1.\]
Each face except the outer one must contain at least one green point.  So there are at least $ |R|+|R \cap I(R)|-2$ green points contained in triangles formed by red points. This proves the lemma.

By similar reasoning,
\[ |Y \cap I(G \cap I(R)) | \ge |G \cap I(R)| - 2 \,, \]
\[ |R \cap I(Y \cap I(G \cap I(R)))| \ge |Y \cap I(G \cap I(R)) | - 2 \,. \]

Combining the above inequalities yields
\[ |R \cap I(Y \cap I(G \cap I(R)))| \ge |R| + |R \cap I(R)| - 6 \,. \]
But $R \cap I(R)$ contains $R \cap I(Y \cap I(G \cap I(R)))$, so $|R|-6 \le 0$.
Hence $|R| \le 6$, and similarly, $|G|$ and $|Y|$ must be at most $6$.

I don't have time right now to come up with a rigorous proof that 18 is possible so a picture will have to do.  (pdf attached)


limit
algebra
function
domain
calculus
derivative
calculus computations

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

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

$ \frac{f(2x)\minus{}f(x)\plus{}f(0)\minus{}f(0)}{x}\equal{}2\frac{f(2x)\minus{}f(0)}{2x}\minus{}\frac{f(x)\minus{}f(0)}{x}\to 0$

so $ \frac{f(x)}{x}\to 0$

I'm sorry, kenn4000, I don't understand one part of your argument (perhaps it's my "stupid day", so I apologize if my question is utterly obvious). Could you perhaps explain this:
[quote="kenn4000"]$ \lim_{x \to 0} \frac {f(x) - 0}{x - 0} = f'(0)$[/quote]

Shouldn't it be $ \lim_{x\rightarrow 0}\frac {f(x) - f(0)}{x - 0} = f'(0)$? Even then, how can we be sure that $ f$ is differentiable in $ 0$ i.e. that limit exists? As I see it, $ 0$ may not even be in the domain of $ f$...

The best I could do is: if we know $ \lim_{x\rightarrow 0}\frac {f(x)}{x}$ exists and equals $ L$, it is obvious that $ \lim_{x\rightarrow 0}{\frac {f(2x) - f(x)}{x} = \lim_{x\rightarrow 0}{2\frac {f(2x)}{2x} - \frac {f(x)}{x}}}$, which is obviously $ 2L - L$, so $ L = 0$. Therefore, $ \frac {f(x)}{x}\rightarrow 0$. But this argument only works if $ \lim_{x\rightarrow 0}\frac {f(x)}{x}$ exists. What if it doesn't? (What I mean is: is there such an example?)

However, we're not using $ f(x)\rightarrow 0$ anywhere here, which makes me think there's a better solution.

true, if zero isnt in the domain then what i wrote doesnt make literal sense, but a continuous extension at the point zero shouldnt affect the limit we are looking for right?  but that may still not be differentiable... so i guess i couldnt write the derivative at zero, but replacing it with any other symbol such as L gets the same result, as you showed

This appears to be a particular case of the question in [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=299969]this topic.[/url]

One note: once we have $ \lim_{x\to0}f(x) \equal{} 0,$ there's no harm to defining (or redefining) $ f(0) \equal{} 0.$ That answers mornik's first objection. On the other hand, kenn4000's argument is not valid, because he cannot answer mornik's second objection: we do not know, [i]a priori,[/i] that $ f'(0)$ exists. That's why we need the telescoping sum approach of my argument in the other topic.

An other point de vue ..  Let's $ a$ be such that $ |a|\neq 1$ . If $ \lim_{x\rightarrow 0}\frac {f(x) \minus{} f(ax)}x \equal{} 0$ and $ \lim_{x\rightarrow 0}f(x) \equal{} 0$ then $ \lim_{x\rightarrow 0}\frac {f(x)}x \equal{} 0$. Of course, we have to prove that the last limit exists.
Let's suppose that $ |a| < 1$. (For the case $ |a| > 1$ it's sufficient to change  $ x \leftrightarrow \frac xa$).
Let's denote $ g(x) \equal{} \frac {f(x) \minus{} f(ax)}x$. We can write $ f(x) \equal{} f(ax) \plus{} xg(x),\ f(ax) \equal{} f(a^2x) \plus{} axg(ax),$$ ...,\ f(a^nx) \equal{} f(a^{n \plus{} 1}x) \plus{} |a|^nxg(a^nx)$,
so $ f(x) \equal{} f(a^{n \plus{} 1}x) \plus{} x(g(x) \plus{} ag(ax) \plus{} ... \plus{} a^ng(a^nx))$ , so $ |\frac {f(x)}x|\leq |\frac {f(a^{n \plus{} 1}x)}x| \plus{} (|g(x)| \plus{} |a|.|g(ax)| \plus{} ... \plus{} |a|^n|.g(a^nx)|)$
Let's take  $ \epsilon > 0$ .  Because of $ \lim_{x\rightarrow 0}g(x) \equal{} 0$ there is $ u > 0$ such that $ \forall_{0 < |x| < u},|g(x)| < \epsilon$, so $ \forall_{0 < |x| < u},|g(a^kx)| < \epsilon$
Let' $ x$ be such that   $ 0 < |x| < u$ . Because of $ \lim_{t\rightarrow 0}f(t) \equal{} 0$ there is $ v > 0$ such that $ \forall_{0 < |t| < v},|f(t)| < \epsilon.x$ .
Manifestly there is an integer $ n$  such that $ a^{n \plus{} 1} < \frac v{|x|}$ , so we can write $ \forall_{0 < |x| < u}|,|\frac {f(x)}x|\leq \epsilon \plus{} \epsilon (1 \plus{} |a| \plus{} ... \plus{} |a|^n) \leq \epsilon.\frac 2{1 \minus{} |a|}$
Therefore $ \lim_{x\rightarrow 0}\frac {f(x)}x \equal{} 0$
Now you can obtain :  If $ \lim_{x\rightarrow 0}\frac {F(x) \minus{} F(ax)}x \equal{} p$ and $ \lim_{x\rightarrow 0}F(x) \equal{} q$ , then $ \lim_{x\rightarrow 0}\frac {F(x)\minus{}q}x \equal{}\frac p{1\minus{}a}$
It's sufficient to take $ f(x)\equal{}F(x)\minus{}q\minus{}\frac p{1\minus{}a}x$ and so on ..
 :cool:


Let $A\in M_{n}(\mathbb{R})$ be a matrix. Prove that $trA=0$ iff there are two matrices $X, Y\in M_{n}(\mathbb{R})$ such that \[A=XY-YX\] .

Posted at least 5 times. If I remember correctly, the problem I had in ENS exam and which I posted said much more. Give a search.

This the ultimate Linear Algebra problem!
1. [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=104546]The last thread.[/url]
2. [url=http://www.mathlinks.ro/Forum/viewtopic.php?highlight=ens&t=101774]The thread harazi was talking about.[/url]

I also posted this problem [url=http://www.mathlinks.ro/Forum/viewtopic.php?&t=86676]here[/url].


inequalities
geometry
trigonometry
invariant
geometric transformation
function
inequalities proposed

I think that this is a fascinating problem (unsolved on Kalva):

In acute $\Delta ABC$, $u, v$, and $w$ are the perpendicular distances from $A, B$, and $C$ respectively to some line $L$.  Prove that

$u^2 tanA + v^2 tanB + w^2 tanC \geq 2[ABC]$ for all $L$.

Moreover, when does equality hold?

I have a beautiful advanced solution for this, but I want to see how everybody handles this one (hopefully using more elementary properties).  Please give it your best shot.

~Mike

Well, I have a very not-smart way of showing that the equality holds when the line passes through $H$ (the computations aren't tough at all, but I don't like the method). I'm pretty sure this is the answer, but I haven't proven the inequality or the fact that the equality doesn't hold anywhere else.

Grobber,

Isn't it trivially true that equality holds for the altitudes?

Say WLOG that it's the altitude from $A$.  Then

$u^2tanA + v^2tanB + w^2tanC = 0 + 2[ABH_a] + 2[ABH_b] = 2[ABC]$, as required.  And yes, you're correct that the only equality cases are $L$ = an altitude.  This is a very interesting equality case, but of course the inequality, not the equality, is the highlight of the problem.

Note that I've edited the original problem.  I forgot to mention that ABC is an acute triangle.  Sorry about that.

But I found that the equality cases aren't $\ell=$ an altitude, but $\ell$ passes through $H$.. You can see that it also holds for $\ell$ passing through $H$ and parallel to a side of the triangle, for example, just to convince yourself that the equality case contains more than just the altitudes.

Sorry, Grobber.

I was extremely tired this morning, and accidentally called altidues arbitrary lines through $H$ (hmm...).
First, note that we can assume $u, v$, and $w$ are the signed distances.  Then, this equality condition from my proof, namely $utanA + vtanB + wtanC=0$ easily translates into $L$ passing through $H$ since $H=(tanA, tanB, tanC)$, in barycentrics.

I'm sort of annoyed with my proof because it depends on an area formula for a triangle which is probably trivial but that I'm having difficulty proving.

Since nobody is posting, I feel the need to encourage the entire forum: you don't know what you're missing if you don't try this problem!

Well, since the equality holds for lines which pass through $H$, we can look at what happens when we take a line and consider it as being obtained from a parallel line through $H$ which was moved with distance $x$. It's trivial that the smallest values for that sum are achieved when the line intersects (at least) two of the segments $BC,CA,AB$, so we only need to look at these cases.

The computations turn out to be pretty easy once we observe that when $H\in \ell$, if $u,v,w$ are, as you said, signed distances, then $u\tan A+\ldots=0$. Here's what we do: assume, for example, that $u$ has a sign opposite to $v,w$. Then move the line $\ell$, which originally passes through $H$, with distance $x$ in either direction (consider $x$ to have any sign you want), such that it still intersects two of the sides of the triangle (so that no problems regarding the signs of the distances arise). Then $(u+x)^2\tan A+(v-x)^2\tan B+(w-x)^2\tan C=u^2\tan A+v^2\tan B+w^2\tan C+x^2(\tan A+\tan B+\tan C)>u^2\tan A+v^2\tan B+w^2\tan C=2[ABC]$, because equality holds for $u,v,w$ ($u,v,w$ are the distances coresponding to $\ell\ni H$).

I think it works..

Lemma: $2[ABC] = (v-w)^2 cot A + (w-u)^2 cotB + (u - v)^2 cotC$.

Notice that all expressions remain invariant under translation of the line, so it suffices to consider when the line passes through a vertex.  From here, it's easy to prove (if anybody actually wants to see my proof, just say so).

Then we must prove that $0 \leq \sum (u^2tanA - (v-w)^2cotA) = cotAcotBcotC(utanA + vtanB + wtanC)^2$, which is certainly true since $\Delta ABC$ is acute (making use of the identity $tanA - cotB - cotC = tanAcotBcotC$, and cyclically).  Hence, equality holds iff $utanA + vtanB + wtanC=0$ or equivaletly iff the line passes through $H$.

Grobber: Your solution is nice, but depends on the equality case.  I'd like to see how you proved that equality holds iff the line passes through H.

You don't need iff, if suffices: you show that the equality holds [b]if[/b] the line passes through $H$, then move the line and the equality doesn't hold anymore.

As for my proof of the "if" part, it's really ugly and I doubt that I'll be posting it :). I just considered a line through $H$, and took $x$ to be the angle that it makles with $h_a$, and as a function of $x$ I computed what I wanted, showing that it's constant. Just a nasty trigonometric bash. Your solution is, however, beautiful!


a test tube contains 18 ml of water and 2 ml dye. how much dye should be added to make the solution 45% dye?

I remember I used to stink at mixture problems.
[hide]
Let x=the amount of dye needed.
The total amount of solution in the test tube right now is 20 ml.
So, we are trying to solve this equation.

$ \frac{2\plus{}x}{20\plus{}x}\equal{}.45$

$ 2\plus{}x\equal{}9\plus{}.45x$

$ .55x\equal{}7$

$ x\equal{}\boxed{\frac{140}{11}ml}$
[/hide]

there is a faster solution.

[hide="hint"]the amount of water stays the same. what percent of the desired solution is water?[/hide]

Oh, so the percentage of water is 55%.
[hide]
$ \frac{18}{20\plus{}x}\equal{}.55$

$ 18\equal{}11\plus{}.55x$

$ x\equal{}\frac{140}{11}$
[/hide]

Thanks abacadaea!

space cadet, your solution errs when you don't add x mL to 20 (the denominator).  If you're adding solution to a substance, not only the amount of that substance, but also the amount of substance total, is changed.

In addition, I believe the solution would be attained faster if you set 45% equal to 45/100=9/20, and not .45 =/

I never had trouble with these kinds of problems when I was in Mathcounts, but now that I'm thinking harder about it...

From a chemistry perspective, how do you know that the total volume of the mixture is simply the sum of the volumes of solute and solvent?

[hide="ok heres my solution, which got a different answer"]
let x be the total amount in the wanted solution. since the desired solution is 55 percent water, .55x=18. then solve for x. getting 198/5=x. subtract the 20 ml we start out with getting 98/5[/hide]

anderson, i think you multiplied both sides by 5/11 instead of 11/5 when solving for x. but then you would get 77/5...which is still not what i got.

...
$ .55\equal{}\frac{11}{20}$...

In other words, andersonw is right

[quote="somebodyspecial"]From a chemistry perspective, how do you know that the total volume of the mixture is simply the sum of the volumes of solute and solvent?[/quote]

[quote="abacadaea"]a test tube contains 18 ml of water and 2 ml dye[/quote]
Both water and dye are in liquid or in aqueous form, therefore the volumes add up  :wink:

Oh, haha, I see...  :blush: The dye can't "dissolve" in the water if it's already a solution in water.
Thanks!

[quote="mathcrazed"]...
$ .55 \equal{} \frac {11}{20}$...

In other words, andersonw is right[/quote]

oh...wow, i missed my own problem


geometry
circumcircle
rhombus
vector
angle bisector
geometry solved

Let ABC be a triangle so that: 1/ha+1/hb=2/lc
Show that:
a) C=60
b)OI=IH

Hi Maverick,

lc is the length of the angle bisector of BCA? First attempt: Multiply with 2A=a*ha=b*hb to get rid of the altitudes. Then substitute lc^2 = ab[1-c^2/(a+b)^2]. ... Without guarantee!

-Eckard

For point a) I think the formula lc=2ab*cos(C/2)/(a+b) works better. We replace lc with this, and then replace ha by bsinC and hb by asinC and we get 1/a*sinC+1/b*sinC= (a+b)/ab*cos(C/2) iff (a+b)/ab=2*sin(C/2)*(a+b)/ab, so sin(C/2)=1/2, so C is 60 deg.

For b) there are lots of computational proofs, but here's a geometrical one: we proved C is 60 deg. By a quick angle chase we prove that A, B, H, I, O are concyclic (just calculate the angles AHB, AIB, AOB). Let O' be the circumcenter of AHB. It's a well known fact that The circumcircles of ABC and AHB have equal radii. Then AOBO' is a rhombus with angle AOB = 120 deg, so OAO' is equilateral, so R (the circumradius of ABC and of AHB) = OO'=CH (this is also a known fact; you can derive it from the fact that vectors OA+OB+OC=OH). This means that OC=R=CH (1). By another angle-chase we can easily see that CH and CO are isogonals (for any triangle, not just the ones with angle C=60 deg). This means that I is on the bisector of angle OCH. Since OCH is isosceles from (1), we get that IO=IH.


$ a,a\plus{}d,a\plus{}2d,\ldots$ be an arithmetic sequence $ a,d \in \mathbb{Z}^\plus{}$. Prove that this sequence contains infinity many perfect square numbers of does not contain any perfect square number.

Sorry for my bad English.
Source: My friend also  :D.

Note that if $ b\equal{}n^2$ is a term of this sequence then $ c\equal{}n^2\plus{}2nd\plus{}d^2\equal{}(n\plus{}d)^2$ is a term of this sequence too.

[hide="trivial"]
This sequence contains all integers $ b\equiv a \pmod{d}$. If there exists e such that $ b\equiv e^2 \pmod{d}$, then every integer of the form $ e\plus{}kd$ will have a square in this sequence; if there doesn't, none will.[/hide]


number theory
graph theory
number theory proposed

This question is both combinatorics and Number Theory :
a ) Prove that we can color edges of $K_{p}$ with $p$ colors which is proper, ($p$ is an odd prime) and $K_{p}$ can be partitioned to $\frac{p-1}2$ rainbow Hamiltonian cycles. (A Hamiltonian cycle is a cycle that passes from all of verteces, and a rainbow is a subgraph that all of its edges have different colors.)
b) Find all answers of $x^{2}+y^{2}+z^{2}=1$ is $\mathbb Z_{p}$

Here is my solution to (a):
Numbering vertex $0, 1, ...$ to $p-1$ and consider the graph as the $\mathbb Z_{p}$ aditive cyclic group. Since $p$ is and odd prime and the graph is complete, we have $\frac{p(p-1)}2$ edges. Denote by $i--j$ the edge joining vertex $i$ and $j$.
Notice that being $\mathbb Z_{p}$ cyclic, we have a cycle of vertex iff we make a "generator" route, i.e., making $0--k--2k--...--(p-1)k--0$ cycle where k is a generator.
There are $p-1$ generators in $\mathbb Z_{p}$, so we have exactly $\frac{p-1}2$ of these cycles (notice that cycle $0--i--2i--...$ is the same to cycle $0--(p-i)--2(p-i)--...$ in backward sense). Each of these cycles pass once in each of the vertex, and has exactly $p$ edges, no one ocurring in another cycle. Therefore, we have partitioned the graph in $\frac{p-1}2$ Hamiltonian cycles. Coloring each edge with one of the $p$ colors in each of the subgraphs, we obtain the required rainbow partition.


trigonometry
geometry
angle bisector
geometry solved

Let $A_{1}$, $B_{1}$, $C_{1}$ be the feet of the altitudes of an acute-angled triangle $ABC$ issuing from the vertices $A$, $B$, $C$, respectively. Let $K$ and $M$ be points on the segments $A_{1}C_{1}$ and $B_{1}C_{1}$, respectively, such that $\measuredangle KAM = \measuredangle A_{1}AC$. Prove that the line $AK$ is the angle bisector of the angle $C_{1}KM$.

Let T be the intersection between AK and CC1. We should prove that triangles C1Tk and AMK are similar (in that order of the vertices). We already know angle KAM=angle A1AC=angle KC1T, so all we need is
C1K/AK=C1T/AM.

I considered M on the ray (C1B1, on the outside of (B1C1), so it's not like in the prb, but the idea is the same (I did that because I didn't remember the prb right):

Let angle B1AM=x. From sine law in AC1T we get C1T/sin(90-B+x)=AC1/sin(B-x) (1). From sine law in AC1K we get C1K/sin(90-B+x)=AK/sin(180-C)=AK/sinC (2). From sine law in AC1M we get AM/sinC=AC1/sin(B-x) (3). We use these 3 relations to find C1K/AK=C1T/AM, which is what we needed in the first place (to get it we divide (1) to (3) and we compare it to (2)).

Maybe some things are different if M and K are on the inside of the segms A1C1 and B1C1, but the idea stays the same.

Denote $AK\cap CC_1=U$, $AM\cap CC_1=V$, $AC_1\cap KV=T$ and $H$ as orthocenter.

$\angle A_1AC=\angle HC_1B_1=\angle UC_1B_1=\angle UAM=\angle KAM$.
Hence $AC_1UM$ is concyclic and $\angle AC_1U=\angle UMA=90$ or $UM\perp AV$

Analogously $\angle A_1AC=\angle A_1C_1C=\angle VC_1K=\angle KAV=\angle KAM$.
Thus  $AC_1KV$ is concyclic and $\angle AC_1V=\angle AKV=90$ or $AK\perp KV$.

We observe that $U$ is orthocenter for triangle $ATV$ and easy property that $AK$ is bisector for $C_1KM$ is also well known.

Yes. This a longlisted problem, proposed from Soviet Union(or Russia). I have posted in the forum  almost the same solution  , some time ago.

 Prowler , nice work !

[u]Babis[/u]

 Oh !!!  I found it. See

               http://www.mathlinks.ro/Forum/viewtopic.php?t=51165
               http://www.mathlinks.ro/Forum/viewtopic.php?t=6229


[quote="mna851"]What should I do if in my grader feedback page, for one problem it says I received $\ 5$ points, but in the score report that score is reported as a $\ 3$?[/quote]

see [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=18394]here[/url]


In a  quadrilateral  $ABCD$  we have

                 $\angle BCA = \angle 2BDA , \angle ACD = \angle 2ABD$.

                         Prove that  $CA = CB = CD$

  [u]Babis[/u]

I think the problems already tells us... $C$ is the circumcentre of $\triangle{ABD}$.

Dear shobber.

    I now that ! I saw this in a solution of you ,for a problem in the fourm(recently).You use it without proof. But this (obvious)proposition has a nice proof. Please do not answer. I leave the proof for the other students. Thanks.

   [u]Babis[/u]

Let $\angle ADB=\alpha \quad \angle ABD=\beta$
Let $O$ be the centre of a circumcircle of triangle $ABD$. Then $\angle AOB=2\alpha \quad \angle AOD =2\beta$
Notice that locus of points $X$ such that $\angle AXB=2\alpha$ lies on a circumcircle of triangle $AOB$.
Similarly locus of points $Y$ such that $\angle AYD=2\beta$ lies on a circumcircle of triangle $AOD$
So point $C$ lies on both of these circles. They intersect at $A$ and $O$,  since $A\not=C$, $C=O$and finally $CA=CB=CD$

This is simple , too.

 Produce  $AC$ and take segment $CE = BC$ . Then   $\angle BEA = \angle BDA$ , so  $ABED$ is inscribed. But then
 $\angle DEA = \angle DBA$ and finally  $CD = CE$ . The rest is the same , since C will be the circummcenter of  $ABED$.

 [u]Babis[/u]


[quote]Standard Theory before I start. As usual. :D Consider a circular loop above which there is a bar magnet falling under gravity with its north pole towards the loop. This is the most famous example given to illustrate Lenz law. So "Since the effect opposes the source" we can look at it in two ways. The total flux  through the loop increase since the magnet falls towards the loop. So to oppose the effect and bring about a field in the upward direction, the current in loop flows anti-clockwise (viewed from top) and brings about a field in the upward direction.

Or else, we can also say that the side where the direction is anticlockwise is North Pole in the loop. So there is North-North repulsion and the accelaration of Bar Magnet is slowed.

In both cases the result is the same. [/quote]

Now consider when it falls with the southpole towards the loop. Now I get contradicting answers when I examine it by above 2 ideas. By Pole-Pole Repulsion, the loop top should have current in clockwise. But since magnet is falling towards loop, then flux inside increases and loop top has clockwise.

Can anybody give the answer with proper explanation.
Thanks
~ Shreyas

[quote="Cyber-Shreyas"]

Now consider when it falls with the southpole towards the loop. Now I get contradicting answers when I examine it by above 2 ideas. By Pole-Pole Repulsion, [b]the loop top should have current in clockwise. But since magnet is falling towards loop, then flux inside increases and loop top has clockwise.
[/b]
Can anybody give the answer with proper explanation.
Thanks
~ Shreyas[/quote]
see u first have to define what the positive normal is ...as in case I that is north pole falling down if the positive normal is away from the loop then when the south pole falls the flux [b] decreases[/b] and not increase as it becomes more and more negative :)

Shreyas lets take energy conservation which is the basis of lenz law...ok

Now to repel the upcoming magnet ,the above side of the coil develops a south polarity and the bottom side produces a north polarity...

Now flux lines always flow from south to north...
So the current in the coil is in the clockwise direction..............


If it is currently Tuesday at noon, what day of the week will it be in 500 hours?

[hide="Answer"]Wednsday about $8:00$. Since $500$ divided by $24$ is $20$ $r20$. You take the remainder ($20$ hours) and add it to $12:00$ (noon is about $12:00$) and is about $8:00$ the next day. [/hide]


Should've combined this with the last one...arrg..sorry x_x

$ f(n)$ is the sum of all integers less than n and relatively prime to n. Find all integers $ n$ such that there exist integers $ k$ and $ l$ such that $ f(n^{k})\equal{}n^{l}$

Is this problem too hard for this forum?