Here is the puzzle:
There is a captain, names  Captain Contangent, who owns a boat, along with a fox, a chicken and he also has a package of corn. His goal is is to cross the river and take his two animals and the package of corn. The problem is this. The boat is so small, he can olny take one thing at a time, and to make matters worse, he knows that if he leaves the fox alone with the chicken, the fox will eat the chicken, and similarly, if he leaves the chicken with the corn, the chicken will gobble up the corn.

How can the captain getall himself and all three items to the other side of the river? Identify the least number of trips across the river and who goes on which trip.

If anyone can help me figure this out it would be great!!!
Thanks

[quote="i_like_pie"]This is a classic (with different animals, however), and has been posted at least once.

[hide="Solution"]The Captain takes the chicken across the river, and goes back. He then takes one of the other things over, and brings the chicken back on the same trip. Then, he brings the third item over, and goes back. Finally, he takes the chicken over.[/hide][/quote]

But I thought that you could only take one thing...

[hide="Solution?"]Maybe the Captain throws the fox and the corn over, then sails the chicken over.[/hide]

[quote="D3m0n Shad0w"]If you brought the chicken with you while you brought the fox, the boat would sink, wouldn't it?[/quote]
But you can't bring two things at once, and my solution doesn't require taking more than one thing at once.

[quote="D3m0n Shad0w"][quote="i_like_pie"][quote="D3m0n Shad0w"]But I thought that you could only take one thing...[/quote]
...at a time.[/quote]

At a time, yes, but lets say the boat could only carry 100 pounds...

The man weighs 90 pounds, everything else weighs 10. If you brought the chicken with you while you brought the fox, the boat would sink, wouldn't it?[/quote]
He's saying that he brings the fox over, puts the fox down, then brings the chicken back. See, he only takes one thing.

and the fox wont eat the chicken because the man is around....right?

[quote="xpmath"][/quote][quote="D3m0n Shad0w"][quote="i_like_pie"][quote="D3m0n Shad0w"]But I thought that you could only take one thing...[/quote]
...at a time.[/quote]

At a time, yes, but lets say the boat could only carry 100 pounds...

The man weighs 90 pounds, everything else weighs 10. If you brought the chicken with you while you brought the fox, the boat would sink, wouldn't it?[/quote][quote="xpmath"]
He's saying that he brings the fox over, puts the fox down, then brings the chicken back. See, he only takes one thing.[/quote]

the fox would eat the chicken when the man goes to pick up the corn, wouldn't he?

the man takes the chicken back over after he puts the fox down

So the idea is it goes like this:
[code]
M = Man
F = Fox
C = Chicken
K = Korn (Corn)
[/code]

[code]
MFCK     ----
-F-K     M-C-
MF-K     --C-
---K     MFC-
M-CK     -F--
--C-     MF-K
M-C-     -F-K
----     MFCK
[/code]

It need not go ONLY in that particular order.


Prove that if $ p$ is prime and if $ p^{m}\, |\, n!$, then $ m<\frac{n}{p-1}$.

[hide="Hint..."]
\[ m \leq \sum_{k=1}^\infty \left\lfloor \frac{n}{p^{k}}\right\rfloor \]
[/hide]


Eight people are in a room. One or more of them get an ice-cream cone. One or more of them get a chocolate-chip cookie. In how many different ways can this happen, given that at least one person gets both an ice-cream cone and a chocolate-chip cookie?

It doesn't look that bad..

[hide]

Pick one person to get both an ice cream and a cookie. There are eight ways to do this.

Now, since one person has both items, you've fulfilled the first two conditions (that at least one of each is given out), so you can do whatever you want with the remaining seven people. Each of them has four positions (nothing, cookie, IC, IC+Cookie), so there are  ways to do this.

Multiplying together gives .[/hide]

I think that overcounts the number of ways. For example, the scenario where person A gets both, person B gets both, and everyone else gets, for example, a cookie, is counted twice.

[hide] My solution: there are $4^{8}$ ways to pick something for everybody. There are $3^{8}$ ways for nobody to get both ice cream and cookie. Therefore, the answer should be $4^{8}-3^{8}$. [/hide]

[hide]Well,

for each person there are four possibilites

Both
1 of one, none of other, viceversa
neither

So, there are $4^{8}$ ways of no restriction

But there are $3^{8}$ ways of making sure no one gets both.

So the answer is $4^{8}-3^{8}=58975$[/hide]


Does anyone here know for a fact that he or she has perfect pitch?

For those who don't know what perfect pitch is, I would say this

Perfect Pitch : Music :: IQ : Succeeding at Academics

I'll be shocked if I don't get 10 or so people replying with angry comments against that analogy ;) ...

Just curious, since I think perfect pitch is quite a neat talent to have...I personally don't have it, but I know many who do, and it really fascinates me.

I happen to have passive absolute (perfect) pitch. Whee~
I'm not so sure about active absolute pitch, though...

[quote]Perfect Pitch : Music :: IQ : Succeeding at Academics[/quote]

I think the analogy is far weaker than that. Absolute pitch is a single specific skill that may not even be particularly useful in music. Of far, far greater importance is relative pitch - being able to hear intervals, and being able to adjust a note in relation to other notes being played at the same time or a nearby time. And relative pitch can be taught.

A musician I know, who is a retired bass player who played for decades in our state's top orchestra, considers absolute pitch more of a nuisance than a help: it means he can always hear when a musical performance is out of tune. For most musicians, having a strong sense of relative pitch is enough: there is always someone who is in charge of tuning the instruments, or establishing the pitch for an orchestra.

well so far as i know i have perfect pitch... but this only applies to the ability to hear a note and name it or hear a line of music and play it back... umm i don think it applies directly to acedemics... i think it helps me with mathematics but not history and english... haha because perfect pitch makes you lazy when you practice so you do not devote yourself as much as another would... in a way i guess it can be detrimental to your academics

i have a brother that has perfect pitch. it is impressive beacuse he can identify 1/4 of a tone! And he is not good in math but he is a really good writer and composer...

I have relative pitch I can hear intervals well.  I'm decent at mathematics and sciences.

Some of you misread/misinterpreted the analogy; I did not by any means mean to suggest that perfect pitch helps in academics - merely that it helped in music.

I have very accurate relative pitch, but I feel that if I had perfect pitch, it would be a great advantage.

I personally play the piano and the violin, both of which I am quite proficient at.

Wow.  I went to a music camp last summer and most people had perfect pitch: it was amazing!  One 7 year old could immediately identify the note a car was making as it was starting! :D   As for myself, I believe I have a relatively accurate relative pitch, but nothing more than that... :(

By the way, one thing that I heard recently is that all babies are born with perfect pitch (or at least the ability to ontain perfect pitch, as some studies have put it)!  Did anyone else hear anything about that?

Yes, I have heard that all babies are born with the capacity for perfect pitch.

Yeah, I guess I would have to agree with tokenadult.

I don't want to be mean or anything but...

what's your point and I don;t care about IQ's...

[quote="tokenadult"]Absolute pitch is just long term memory of the standard reference notes, and any baby, if exposed to enough examples from a tuning fork or electronic piano, could probably store up those examples in long term memory. Most people aren't trained with perfectly tuned note examples in childhood, so it's not surprising that most people don't have absolute pitch.[/quote]

Actually, that's not quite accurate. [url=http://www.centreforthemind.com/publications/AbsolutePitch.pdf]Here's[/url] an interesting read.

That is an interesting read, although I don't think it is contrary to what I said. The analogy with drawing is interesting, as all of my children are more accurate at life drawing than most of their age mates, and I think that is because of conscious educational measures I followed in their early childhood. We haven't, because we know musicians with absolute pitch, had any comparable desire to train absolute pitch in our children. As the interesting article you cite says, there doesn't seem to be much by way of advantage to having absolute pitch. By the way, relating the issue to acquiring a second language without an accent, as the article authors did, is interesting.

Did read the [i]whole[/i] thing, but enough to understand.

That's very interesting, thanks for sharing.

I think it can come either way. My mom has always had perfect pitch, but I have a friend who has played the cello for many years and as such seems to have acquired perfect pitch.

[quote="aadavi"]Yep. I don't think I was born with it but hey I can still learn it so that's encouraging.[/quote]

I myself wasn't born with perfect pitch, but at this time I'm part of a choir and I've noticed that if I sing a song a lot in a certain key than I can automatically go back to that key later. This would suggest that over time I could develop perfect pitch. I happen to also do the sing-a-note-and-go-play-it-on-the-piano-to-see-if-its-right-thing. I feel like this actually does work as long as, like EpicSkills32 pointed out, you [i]can[/i] sing :)

I use E as the highest note I can't sing and then work my way down lol.

I can tell when a note is sharp or flat when it is ~10 cents sharp, and I can identify any note when someone plays it. I've learned the Angry Birds theme song by ear, and also the Shire theme. I think I'm lucky, because the "Out of tune" thing doesn't drive me crazy as much as some other people. :)

 Unfortunately, my voice is terrible, so I can't sing the note without being like 25 cents sharp/flat and the pitch fluctuating. :(

Actually, out of tune instruments make me cringe on the inside. Also I can hit a note spot on with voice.

I can hit a note about a fifth below it.

And if you're looking for a note at least an octave above middle C, I'll hit it a fifth plus another two octaves below it.

 XP

I also have perfect pitch, and I think it comes from both practice and intuition.
At early ages, I could recognize notes as played. However, creating them took practice, and only perfected it after becoming a percussionist, of all things. I used timpani drums.

I have partial perfect pitch. I know C, D, A, B and it's kind of hard to tell between E and F and no sharps or flats.

I think I have perfect pitch. I can recognize any single note that is played. The only thing that kinda stumps me is the triad.

[quote="EpicSkills32"]All things considered, perfect pitch actually isn't that important. Also, many who believe that they have perfect pitch actually don't.

http://www.unconservatory.org/perfect_pitch/3.html

http://www.themusiciansbrain.com/?p=190

http://blog.musivu.co/2013/06/04/perfect-pitch-doesnt-matter/[/quote]

This is actually true. I had perfect pitch from the beginning of my music studies. I identified whatever correct. At least mostly(If you play D and D# together, it's possible I wouldn't be able to tell). Either way, my musicality sucks, and my sound is always bad. I can never play with expression, and I fail to correct it, even though musicality should be natural. So perfect pitch didn't help much(other than really good music theory :) )

[quote="EpicSkills32"]All things considered, perfect pitch actually isn't that important. Also, many who believe that they have perfect pitch actually don't.

http://www.unconservatory.org/perfect_pitch/3.html

http://www.themusiciansbrain.com/?p=190

http://blog.musivu.co/2013/06/04/perfect-pitch-doesnt-matter/[/quote]

Im pretty sure that I have it. I can hit a note spot on when singing. Also, it just doesnt have to be instruments. I can identify the notes of wind chimes or car horns. Even vacuum cleaners when they suck up air.

I had a test on piano and my music teacher said that my ears were gifted, once. My teacher played a note on the piano and I named it perfectly MANY times. I could do the part b part that you just gave in the first article.

One of my friends is obsessed with perfect pitch even though she already has it. She knows like 10 other people who have it as well.


congrats aswath for making it to the imotc!

what study material did you refer for the inmo?  :roll:  :o  :wink:

book "an excursion in mathematics" order from bhaskaracharya prathisthan pune .


Here I'm posting all the problems from Bulgarian Math Olympiad. I believe they are problems with very high quality and they will be useful for all mathlinkers. Enjoy them! I wish success to everyone!

I suppose - yes! It is the goal - as many people as possible to see them. As I said I have lots of problems still missing on the popular sites I exchange problems with different people, invent new problems and share them. I would like people to follow my example and share more problems from their competitions. I would like to see more problems from Iran for example, Australia 2008 problems and problems from other countries.

Amazing work. Since 2007 you use the name regional and national. Does that correspond to the 3rd and 4th round, respectively?

[quote="greentreeroad"]Thanks a lot! Can we put them into resource section?[/quote]

Given the available tex-source problems could be posted in reasonable time. I guess only a few forum-related changes need to be made in the code. But then certain ML mods (and users) would scream that how can you post problems without checking whether they have been posted before. But those people usually do not post whole years of competitions systematically. But doing that checking before each problem would take ages! I think this is a useful approach for most members who only post maybe 2-3 problems a day at most. So the compromise I usually do now if I post big amount of problems: I do not check before. And users who try to solve the problem may want to check the forum for the problem (before or after they tried the problem) and can post links to possibly earlier discussion of the very problem (NOT just saying it was posted before). And I will merge those topics. It is mostly helpful if the notation in most of the discussions roughly matches when they are put together in one thread. As was discussed somewhere else by an admin who said it is okay to re-post  problems (that I intend to merge) or revive old thread. At the end of the day math is not a spectator sport of reading old threads but actually messing around with it yourself.

School round was removed ... now the rounds are III instead of IV ... you may consider the problems here as the problems from the lasy two rounds before TST.

Could you post the TST problems as well?


algebra
polynomial
Dan Schwarz
roots
IMO Shortlist
IMO
IMO 2006

My solution to this one:
If $a_{1}, a_{2},\ldots, a_{k}$ are points of a periodic orbit of $P$ ($P(a_{i})=a_{i+1}$) we have \[a_{2}-a_{1}\mid a_{3}-a_{2}\mid \ldots\mid a_{1}-a_{k}\mid a_{2}-a_{1}\] So we have $|a_{i+1}-a_{i}|$ is a constant. But this is impossible for $k>2$. (Guess why)
So all periodic orbits are of degree $1$ or $2$.
If we have no $2$nd degree periodic orbit we are done ($P(x)=x$ has at most $n$ roots)
If we have two $2$nd degree orbits like $(a,b)$ and $(c,d)$, then we have \[a-c\mid b-d\mid a-c\] So we have $|a-c|=|b-d|$ and similarly $|a-d|=|b-c|$ which easily proves that $a+b=c+d$. If we have a $2$nd degree orbit like $(a,b)$ and a fixed point $t$ then similarly we would have $t+t=a+b$. So now let just $u=a+b$ then all periodic points are the roots of equation $x+P(x)=u$ which obviously has at most $n$ roots.

[quote="Nima Ahmadi Pour"]My solution to this one:
If $a_{1}, a_{2},\ldots, a_{k}$ are points of a periodic orbit of $P$ ($P(a_{i})=a_{i+1}$) we have \[a_{2}-a_{1}\mid a_{3}-a_{2}\mid \ldots\mid a_{1}-a_{k}\mid a_{2}-a_{1}\] [/quote]

Can you explain me this, please?

It follows from the well-known lemma that, for all integers $a, b$ ($a \neq b$), $a-b | P(a)-P(b)$.

[quote="Soarer"][quote="ychjae"] then $P(P(t))=t$ iff $P(t)\in S$[/quote]

huh? why?[/quote]
Sorry, I make a very big mistake here :oops: .

My question: does this problem still hold over the reals?

When I first saw it, I intuitively thought that the maximum possible cycle should be 2, because if you consider the graph of an arbitrary polynomial $f(x)$ of degree greater than 1, and the line $y = x$, then while you're iterating you're basically jumping from points on the function, to the line $y = x$, then back to the function, etc. So you're going around in a rectangular motion, and you either start diverging, start converging, or in the special case of an iteration of length 2, you create a perfect rectangle ($P(a) = b, P(b) = a$). Oh yeah and there's the case $P(a) = a$ as well, of course.

Since we are given a positive integer $k$, and the convergence case would require infinitely many iterations, my first instinct is that the problem still holds over real polynomials with real coefficients.

EDIT: Courtesy of Thomas Mildorf and Mathematica I see that it does not hold over all reals. Just pounding out the resulting polynomials from applying $P(P(x))$ for instance will give many distinct roots....

Maybe we should exploit the fact that $P$ divides iterations of $P$.
In the easiest case, $P^{(2)}=QP$, where $P^{(k)}=PoPo \dots oP$ ($k>1$ times). Now $P^{(2)}(t)=t=Q(t)P(t) \Rightarrow P(t)$ divides $t$. But also $P(t)=Q(P(t))t$, and t divides $P(t)$, meaning $|P(t)|=|t|$. Now we have at most $2n$ such $t$. How do you finish it for this case ?

I feel slightly robbed by this question. For the case where the cycle length of $P(P\ldots P(x) \ldots ))$ is 3 or more, I quoted a famous problem out of from the USAMO in the 1970s, proved in Engel's Problem Solving.

I got nothing for quoting it whereas I would have got 3 for proving it.

I also think some contestants got a serious advantage here. The problem from the USAMO is really famous, and it's also well known that any fixed point of $P \circ P \circ \cdots \circ P$ must be a fixed point of $P \circ P$.

is this solution right?please read it and tell me :blush: because if it is then again this problem is not hard at all.if it's wrong then :blush:  :blush:  :blush: if $k=1$ it is obvious.if $k=2$
let's say that there are  $n+1$(if there are more it is even better) integers $x$ such that $P(P(x))=x$.let $a_{1}> a_{2}>... > a_{(}n+1 )$ be those $n+1$ integers.we clearly have$a_{i}-a_{(}i+1) \mid P(a_{i})-P(a_{(}i+1)) \mid P(P(a_{i}))-P(P(a_{(}i+1)))=a_{i}-a_{(}i+1)$so $| P(a_{i})-P(a_{(}i+1)) |=a_{i}-a_{(}i+1)$.adding this for all $i=1,2,...,n$ we get that $|P(a_{1})-P(a_{2})|+....+|P(a_{n})-P(a_{(}n+1))|=a_{1}-a_{(}n+1)= |P(a_{1})-P(_{(}n+1))|$.

but$|P(a_{1})-P(a_{2})|+....+|P(a_{n})-P(a_{(}n+1))| \ge |P(a_{1})-P(_{(}n+1))|$.since in the last one we have equality then all $|P(a_{i})-P(_{(}i+1))|$have the same sign.
1)$P(a_{i})-P(_{(}i+1))>0$ =>$P(a_{i})-a_{i}=k$ for all $i=1,2,..,n+1$ =>$P(x)-x-k=0$ for n+1 numbers but this is a contradiction since P's degree is n
2)$P(a_{i})-P(a_{(}i+1))<0$=>$P(x)+x-k=0$ for n+1 numbers and again contradiction.
if $k>2$ again we easily get in the same way that $| P(a_{i})-P(a_{i}+1) |=a_{i}-a_{i}+1$ and this is just case $k=2$
i can't find any mistakes.are there any?

well in Fact it is not a "hard" problem if you are used to polinomials! Obviouslyiy you have integeer coefficients you must use $a-b|p(a)-p(b)$ and later analitic properties: in this case analitic properties didnt help sou you only needed the divisibility and inequalities and some classical facts ( a polinomial of degree $n$ has $n$ roots)

And finally the key idea was considering the numbers $p_{k+1}(x)-p_{k}(x)$ which was typical since their sum telescope to what we wanted!

I didnt like about this problem some thinks, for example its ancestors

[url]http://www.kalva.demon.co.uk/usa/usa74.html[/url]

However, It  is not too bad if someone knewed that problem, it just told him there is no period of lenght 3, which I think many people thought whitout knowing it...

Edit: I didnt read whats before my post... :wink:

indeed, the "ancestror" that pascual says is a very famous and wellknown usamo problem.
in every olympiad training they teach it...

Lemma 1: $P(P(x)) - x$ has at most $\deg P$ integer roots, where $P\in\mathbb{Z}[x]$ and $\deg P\geq2$..

Proof: Clearly the only roots of this equation is either $a$ such that $P(a) = a$, or $a, b$ such that $P(a) = b, P(b) = a$. If no $a\neq b \in \mathbb{Z}$ existed such that $P(a) = b, P(b) = a$, then we are done, since then the only integer roots of this would be $P(x) - x$, which has at most $\deg P$ roots. Otherwise, consider $a, b$ such that $P(a) = b, P(b) = a$. If $c,d$ exist such that $P(c) = d, P(d) = c$, and $c,d\neq a,b$, then $a - c | P(a) - P(c) = b - d | P(b) - P(d) = a - c$, so $|a-c| = |b-d|$. Similarly, $|a-d| = |b=c|$, which implies $a+b= c+d$. We can similarly get that if $P(t) = t$, then $|t-a| = |t-b|$, so $2t = a+b$ as well, which means if $x$ is a root of $P(P(x)) - x$, then $P(x) + x = M$ for some constant $M$. There are at most $\deg P$ roots of $P(x) + x -M$, which means there are at most $\deg P$ integer roots total. We conclude.

Lemma 2: If $r\geq 3$, there does not exist $x_{1}, x_{2},\ldots x_{r}\in \mathbb{Z}$, where $x_{i}\neq x_{j}$, such that $P(x_{i}) = x_{i+1}$, and we define $x_{r+1} = x_{1}$.

Proof: Assume there existed such integers. We have
\[x_{2} - x_{1} | P(x_{2}) - P(x_{1}) | x_{3} - x_{2} | P(x_{3}) - P(x_{2}) | \ldots | P(x_{r} - x_{1}) | x_{1} - x_{2}\]
This means $|x_{2} - x_{1}| = |x_{3} - x_{2}|$, since $x_{1}\neq x_{3}$ this means $x_{2} - x_{1} = x_{3} - x_{2}$, and $x_{3} - x_{2} = x_{4} - x_{3}, \ldots$. But this yields a contradiction when we get to $x_{r+1} - x_{r} = x_{1} - x_{r} = x_{2} - x_{1}$.

Now, we move onto the main part of the problem. Consider a graph of integers, and draw an arrow between $x$ and $P(x)$. By lemma 2, the only cycles are cycles of length $1$ and $2$. We do not need to consider $x$ that are not in a cycle (no $k$ will exist such that $P^{k}(x) = x$). Thus, if $t$ is a root of $P^{k}(x) - x$, then it is in a cycle of length $1$ or $2$, which means $t$ is also a root of $P(P(x)) - x$. By Lemma 1, this has at most $n$ integers roots.

[quote=Valentin Vornicu]Let $P(x)$ be a polynomial of degree $n > 1$ with integer coefficients and let $k$ be a positive integer. Consider the polynomial $Q(x) = P(P(\ldots P(P(x)) \ldots ))$, where $P$ occurs $k$ times. Prove that there are at most $n$ integers $t$ such that $Q(t) = t$.[/quote]
Nice problem, probably became very famous now. BTW I just wanted to post my solution so..
Let $P^k(x)$ be the composition of $P$ $k$ times.
Claim 1-: For some integer $x$ such that $Q(x)=x$ then $Q(x)=x=P^k(x)\implies P^2(x)=x$. For any $k\in N$
Prove-: Then as $P(x)$ is the polynomial with integer coefficient so for that integer $x$ we have $P^{2}-x|P^3(x)-P(x)|P^4(x)-P^2(x)|...|P^{k-1}(x)-P^{k-3}(x)|P^k(x)-P^{k-2}(x)\implies P^2(x)-x|x-P^{k-2}(x)$ and also $P^{k-2}(x)-x|P^k(x)-P^2(x)\implies P^{k-2}(x)-x|x-P^2(x)\implies P^2(x)-x=x-P^{k-2}(x)\implies P^2(x)-x=P^{n}(x)-P^{n-2}(x)$ for all $3\leq n\leq k$ Now by this for such $n$ we also get $P^{n-2}(x) -x=P^n(x)-P^2(x)=P^{n-1}(x)-P(x) \implies P(x)-x=P^{n-1}(x)-P^{n-2}(x)--*$ and also $P(x)-P^2(x)=P^{n-1}(x) -P^n(x)--**$ Now for some $n$ equating Eq$*$ and $**$ we get $P(x)-x=P(x)-P^2(x)\implies P^2(x)=x$

Claim 2-: $P(P(x))-x=0$ has atmost $\text{deg P}$ Number of solutions
Prove-: FTSOC Assume there are greater then $\text{deg P}$ number of solutions of set $S=\{x_1, x_2,.., x_{\text{deg P}+y}\}$ out of which we can pick any $2$ integer $x$ say $x_m,x_n$ then $P(P(x_m))-P(P(x_n))=x_m-x_n$ and now as $x_m-x_n|P(x_m)-P(x_n)|P(P(x_m))-P(P(x_n))=x_m-x_n\implies P(x_m)-P(x_n)=x_m-x_n$ So say for $m=1$ we must get total of greater then $\text{deg P}$ number of values of $n$ But then as we also have $P(x_1)-x_1=P(x_n)-x_n$ has atmost $\text{deg P}$ number of solution which is contradiction. Hence our assumption was wrong.
Now if we have $P(x)=x$ which clearly has atmost $\text{deg P}$ number of solutions. $\blacksquare$

[hide=Solution]
Let the order of $x$ to be the minimum value $k$ such that $P^k(x)=x$ if it exists, otherwise it is $\infty$. Then, we claim that the only possible orders are $1$, $2$, and $\infty$. Suppose that there exists $x_1$, $x_2$, $\ldots$, $x_i$ such that $i\geq3$, $x_j$ are distinct, and $P(x_j)=x_{j+1}$ where $x_{i+a}=x_a$. Then, we have $x_j-x_{j+1}\mid x_{j+1}-x_{j+2}$ for all $j$. Multiplying all of these equations, we get $(x_1-x_2)(x_2-x_3)\ldots(x_i-x_1)\mid(x_1-x_2)\ldots(x_i-x_1)$. Therefore, this means that $|x_j-x_{j+1}|=|x_{j+1}-x_{j+2}|$ for all $j$. Suppose that $x_j-x_{j+1}=x_{j+2}-x_{j+1}$. Then, $x_j=x_{j+2}$, which contradicts the fact that $i\geq3$. Therefore, $x_j-x_{j+1}=x_{j+1}-x_{j+2}=c$ for some constant $c$. However, adding up all of these equations, we get $ic=0$, which implies $c=0$, so $x_j=x_{j+1}$, which is also a contradiction.

Therefore, it suffices to show $P(P(x))=x$ has at most $n$ integer solutions. Suppose that $P(P(x))=x$ has more than $n$ integer solutions. Since $P(x)=x$ has at most $n$ solutions, this means that there exists an integer with order $2$. Let $a_1$, $a_2$, $\ldots$, $a_i$ be the solutions to $P(x)=x$, and let $x_1$, $y_1$, $\ldots$, $x_j$, $y_j$ be the solutions to $P(P(x))=x$ and $P(x)\neq x$ such that $P(x_i)=y_i$. Then, if $i\geq2$, then we have $a_1-x_1\mid a_1-y_1\mid a_1-x_1$ and $a_2-x_1\mid a_2-y_1\mid a_2-x_1$. Therefore, either $a_1-x_1=a_1-y_1$ or $a_1-x_1=y_1-a_1$. Since $x_1\neq y_1$, we must have $x_1+y_1=2a_1$. Similarly, $x_1+y_1=2a_2$, so $a_1=a_2$, which is a contradiction. Therefore, $i\leq1$. If $i=1$, then $x_m+y_m=2a_1$, so if $i+2j>n$, then $2j\geq n$, and we get $P(x_m)=2a_1-x_m$, $P(y_m)=2a_1-y_m$, and $P(a_1)=2a_1-a_1$. Therefore, $P(x)=2a_1-x$ has at least $2j+1>n$ solutions. Since $P(x)$ has degree $n>1$, this means that $P(x)+x-2a_1$ also has degree $n$, which contradicts the fact that it has at least $n+1$ solutions.

Now, if $i=0$ and $i+2j>n$, then since $n>1$, we have $j>1$. Now, we have $x_a-x_b\mid y_a-y_b\mid x_a-x_b$, so $|x_a-x_b|=|y_a-y_b|$. Therefore, either $x_a-y_a=x_b-y_b$ or $x_a+y_a=x_b+y_b$. Similarly, since $x_a-y_b\mid y_a-x_b\mid x_a-y_b$, we must have $x_a-y_a=y_b-x_b$ or $x_a+y_a=x_b+y_b$. Suppose that $x_a+y_a\neq x_b+y_b$. Then, we must have $x_a-y_a=x_b-y_b=y_b-x_b$, so $x_b=y_b$, which is a contradiction. Therefore, $x_a+y_a=x_b+y_b=c$, so $P(x_a)=c-x_a$ and $P(y_a)=c-y_a$. However, since $2j>n$, the equation $P(x)=c-x$ has at least $2j$ solutions, which contradicts the fact that $P(x)+x-c$ has degree $n$.

Therefore, there are at most $n$ integer solutions to $P^k(x)=x$ for any integer $k$.

My solution from WOOT:
Well-known and easy to show that $t$ is a fixed point of $Q$ iff it's a fixed point of $P\circ P$, so it suffices to show it for the case $k=2$.
Let $P(a)=b$ and $P(b)=a$, where $a\ne b$. If such an $a,b$ do not exist, then the only fixed points of $P\circ P$ and fixed points of $P$, of which there are at most $n$.

[b]Case 1:[/b] there are $c,d$ with $c\ne d\ne b$ with $P(c)=d$ and $P(d)=c$
We have
$$a-c\mid b-d\mid a-c,$$
so $|a-c|=|b-d|$. We also have $a-d\mid b-c\mid a-d$ which gives $|a-d|=|b-c|$. By simple casework, we have $a-b=c-d$. For all $x$ with $P(P(x))=x$ and $P(x)-x\ne0$, we will then have $P(x)-x$ constant (let this constant be $k$). Then $P(x)-x-k$ obviously has at most $n$ roots.

[b]Case 2:[/b] $P(u)=u$, and no other $2$-cycles exist
Similarly, $a+b=2u$ and the same result holds.

Let $S$ be the set of fixed points of $Q$. Then, all pairs $x,y\in S$ satisfying $Q(x)=x, Q(y)=y$ also satisfy
\[x-y \mid P(x)-P(y) \mid P^2(x)-P^2(y) \cdots \mid P^k(x)-P^k(y) = Q(x)-Q(y) = x-y\]
Since the inequality must hold at all steps, we have $x-y = \pm (P(x)-P(y))$. Consider some fixed $s_1\in S$, then we have $P(x)=P(s_1)+e_x(x-s_1)$ where $e_x\in \{-1,1\}$. Then, \[x-y = e_{xy} (P(x)-P(y) ) = e_{xy} (e_x(x-s_1) - e_y(y-s_1))\]
If $e_x=-e_y$, then we get either $x-y = x+y-2s_1\Longrightarrow y=s_1$ or $y-x = x+y-2s_1 \Longrightarrow x=s_1$, both of which are contradictions. Thus, all $e_x,e_y$ are equal. Thus, we either have all $P(x) = P(s_1)+(x-s_1)$ or $P(x) = P(s_1)-(x-s_1)$. Both of these are degree $n$ equations, which have at most $n$ solutions, so we are done. $\blacksquare$.

First we reduce this to the case $k=2$.

[b][color=#f00]Claim.[/b][/color] If $Q(x) = x$, then $P(P(x)) = x$.

We utilize the fact that $$a-b \mid P(a)-P(b)$$ for any integers $a, b$ and polynomial $P$ with integer coefficients. Construct the chain of divisibilities $$P(x) - x \mid P^2(x) - P(x) \mid \cdots \mid P^{n+1}(x) - P^n(x) = P(x) - x.$$ This means that $$|P(x) - x| = |P^2(x) - P(x)| = \cdots = |x-P^{n-1}(x)|.$$ Assume none of the terms are zero -- then, we are done. Observe their sum is 0, which means that there must exist at least one positive and negative term. Correspondingly, there must also exist a $k$ such that $$P^k(x) - P^{k-1}(x) = -(P^{k+1}(x) - P^k(x)).$$ This means that $$P^{k+1}(x) = P^{k-1}(x).$$ In turn, the terms of $P^i(x)$ are periodic with cycle 2, so $P(P(x)) = x$ as required. $\blacksquare$

Let $a, b$ be two distinct integers such that $P^2(a) = a$ and $P^2(b) = b$. We prove the following: either
[list]
[*]$P(x) = x$ for all $x$ with $P^2(x) = x$ ($\clubsuit$) or
[*]$P(x) + x = c$ is constant for all $x$ satisfying the condition. ($\diamondsuit$)
[/list]
We argue by contradiction. First, observe the two divisibility relations $$a-P(b) \mid P(a) - P^2(b) = P(a) - b,$$ so $$|a-P(b)| = |P(a) - b|$$ and $$a-b \mid P(a) - P(b) \mid a-b \iff |a-b| = |P(a) - P(b)|.$$ There are four cases.
[list]
[*]$a-P(b) = P(a) - b$ and $a-b = P(a) - P(b)$. Then, $P(a) - a = b - P(b) = P(b) -b$, so $P(b) = b$ and $P(a) = a$.
[*]$a-P(b) = b-P(a)$ and $a-b = P(a) - P(b)$. Then, $a-b = P(b) - P(a) = b-a$, so $a=b$, contradiction.
[*]$a-P(b) = b-P(a)$ and $a-b = P(b) - P(a)$. Both assertions give us $a+P(a) = b + P(b)$, so $x+P(x)$ is constant for all necessary $x$.
[*]$a-P(b) = P(a) - b$ and $a-b = P(b) - P(a)$. The two assertions give $a-P(a) = b-P(b)$ and $a+P(a) = b+P(b)$, and adding yields $2a=2b$, contradiction.
[/list]
Assume for the sake of contradiction that there existed distinct $a, b$ such that $a$ satisfied $\clubsuit$ and $b$ satisfied $\diamondsuit$. Then the divisibility condition on $a, b$ implies $b$ must satisfy $\clubsuit$ as well, so the constant value $c = 2b$. But $a$ must satisfy $\diamondsuit$ as well, so $c=2a$, leading to a contradiction, as required. Since there are at most $n$ integers satisfying each condition, we are done.

Assume that there existed distinct $t_1 \leq t_2 \leq \ldots \leq t_{n+1}$ such that $P^k(t_i)=t_i$. Then, $ (t_i-t_j) \mid (P(t_i)-P(t_j)) \mid (P(P(t_i))-P(P(t_j))) \mid \ldots \mid P^k(t_i)-P^k(t_j)=(t_i-t_j)$, hence $|P(t_i)-P(t_j)|=t_i-t_j$ for all $i>j$.

Note that $$t_n-t_1=|P(t_n)-P(t_1)| \leq |P(t_n)-P(t_{n-1})|+|P(t_{n-1})-P(t_{n-2})|+\ldots+|P(t_2)-P(t_1)|=(t_n-t_{n-1})+\ldots+(t_2-t_1)=t_n-t_1,$$ hence we must have equality in the triangle inequality, so all $P(t_i)-P(t_{i+1})$ have the same sign.

Suppose they are all positive, then $P(t_i)-P(t_j)=t_i-t_j$ for all $i>j$, hence $P(t_i)-t_i=P(t_j)-t_j=c$ for all $i,j$. Let $Q(x)=P(x)-x-c$. Then $Q$ has all $t_i$ as real roots, and as there are $n+1$ of them, $Q$ must be the zero polynomial, hence $P$ is linear, which contradicts the fact that $\deg P >1$.

[hide=Solution]
Note that if $$Q(x)=\underbrace{P(P(\ldots P}_{n\text{ times}}(x)\ldots))-x=0,$$ then we can let $$P(x)=x_1,P(x_1)=x_2,\ldots,P(x_{n-1})=x.$$ This means that $$x-x_1|P(x)-P(x_1)=x_1-x_2,x_1-x_2|P(x_1)-P(x_2)=x_2-x_3\ldots x_{n-1}-x|P(x_{n-1})-P(x)=x-x_1.$$ In other words, $$|x-x_1|=|x_2-x_3|=\ldots=|x_{n-1}-x|=|x-x_1|.$$
We will now prove by induction that in order for $$|x-x_1|=|x_1-x_2|=\ldots=|x_{i-1}-x|$$ to be true, we must have $x=x_2,$ for all $i>2.$
\\Base Case:
\\For $i=3,$ we find that $$|x-x_1|=|x_1-x_2|=|x_2-x|.$$ Now, let $y_1,y_2,y_3$ be a permutation of $x,x_1,x_2$ such that $y\geq y_1\geq y_2.$ This means that $$y-y_1=y-y_2=y_1-y_2\implies y_1=y_2=y_3$$$$\implies x=x_1=x_2\implies x=x_2.$$
\\Inductive Step:
\\Suppose that when $i=n,$ $x=x_2$ must be true. This means that the equation $$|x-x_1|=|x_1-x_2|=\ldots=|x_{n-1}-x|$$ results in $x=x_2.$ Now, the equation for $i=n+1$ would be $$|x-x_1|=|x_1-x_2|=\ldots=|x_{n-1}-x|=|x_n-x|.$$ But, from $$|x-x_1|=|x_1-x_2|=\ldots=|x_{n-1}-x|,$$ we have $x=x_2.$
\\Lastly, for $i=2,$ we find that $P(P(x))=P(x_1)=x_2.$ But if $P(P(x))=x,$ then $x=x_2.$ Thus, we may conclude that for $$|x-x_1|=|x_2-x_3|=\ldots=|x_{n-1}-x|=|x-x_1|$$ and $Q(x)=x$ to be satisfied, we must have $P(P(x))=x$
\\Now, since we have proven $P(P(x))=x$ must be satisfied for $Q(x)=x,$ it suffices to prove that $P(P(x))=x$ has at most $n$ solutions. Now, let $a,b$ be two solutions to $P(P(x))=x.$ This means that $a-P(b)|P(a)-P(P(b))=P(a)-b.$ In addition, $P(a)-b|P(P(a))-P(b)=a-P(b).$ Combining, this means that $|a-P(b)|=|P(a)-b|.$ In addition, note that $a-b|P(a)-P(b)$ and $P(a)-P(b)|P(P(a))-P(P(b))=a-b.$ Combining, this means that $|a-b|=|P(a)-P(b)|.$ Now, we can split this into two cases
\\Case 1: $a-P(b)=P(a)-b,$ $a-b=P(a)-P(b)$
\\Rearranging, we obtain $P(a)-a=-(P(b)-b).$ Let $P(x)-x=G(x).$ This means that $|G(a)|=|G(b)|=c,$ for some constant $c.$ There are at most $n$ integer solutions to $G(x)=c$ and at most $n$ integer solutions to $G(x)=-c.$ In addition, from the second equation, we have $P(b)-b=P(a)-a,$ which means that this case has $n$ solutions. This means that there are $\binom{n}{2}=\frac{n(n-1)}{2}$ possible values of ordered pair $(a,b).$
\\Case 2: $a-P(b)=P(a)-b,$ $a-b=P(b)-P(a)$
\\Rearranging, we obtain $P(a)-a=-(P(b)-b).$ Let $P(x)-x=G(x).$ This means that $|G(a)|=|G(b)|=c,$ for some constant $c.$ There are at most $n$ integer solutions to $G(x)=c$ and at most $n$ integer solutions to $G(x)=-c.$ In addition, from the second equation, we have $P(b)+b=P(a)+a,$ $G(a)+2a=G(b)+2b\Leftrightarrow G(a)-G(b)=2(b-a),$ but this means that $a-b|G(a)-G(b)$ is not true. Thus, there are 0 solutions for this case.
\\Case 3: $a-P(b)=b-P(a),$ $a-b=P(a)-P(b)$
\\Rearranging, we obtain $P(a)+a=P(b)+b.$ Now, let $G(x)=P(x)+x.$ This means that $Q(a)=Q(b)=c,$ for some constant $c.$ In addition, $\deg P>1\implies\deg G=\deg P.$ This means that $G(x)$ is a nonconstant polynomial, which means that $G(x_1)=c$ can have at most $n$ solutions. Now, from the second equation, we have $P(a)-a=P(b)-b.$ This means that $G(a)-2a=G(b)-2b\Leftrightarrow G(a)-G(b)=2(a-b).$ But this means that the equation $a-b|G(a)-G(b)$ is not true. Thus, there are 0 solutions for this case.
\\Case 4: $a-P(b)=b-P(a),$ $a-b=P(b)-P(a)$
\\Rearranging, we obtain $P(a)+a=P(b)+b.$ Now, let $G(x)=P(x)+x.$ This means that $Q(a)=Q(b)=c,$ for some constant $c.$ In addition, $\deg P>1\implies\deg G=\deg P.$ This means that $G(x)$ is a nonconstant polynomial, which means that $G(x_1)=c$ can have at most $n$ solutions. This means that there are $\binom{n}{2}=\frac{n(n-1)}{2}$ possible values of ordered pair $(a,b).$
\\This means that there are a total of $\frac{n(n-1)}{2}+\frac{n(n-1)}{2}=n(n-1)$ possible values of ordered pair $(a,b).$ If there are $c$ solutions to $Q(x)=x,$ then there should be $c(c-1)$ possible values of ordered pair $(a,b).$ Since $n(n-1)$ is the number of possible ordered pairs $(a,b),$ we conclude that $c=n.$ In other words, $$Q(x)=\underbrace{P(P(\ldots P}_{n\text{ times}}(x)\ldots))-x=0,$$ has at most $n$ integral solutions.
[/hide]

Let $x,y$ be distinct roots of $Q.$ Notice $P^k(x)-P^k(y)=x-y\mid P(x)-P(y)$ and $P(x)-P(y)\mid P^2(x)-P^2(y)\mid\dots\mid P^k(x)-P^k(y)$ so $$x-y=|P(x)-P(y)|=|P^k(x)-P^k(y)|.\quad(*)$$ [b][color=lightblue]Claim:[/color][/b] $P$ is either increasing or decreasing over the integers.
[i]Proof.[/i] Notice $$|P(x+1)-P(x)+P(x+2)-P(x+1)|=2=|P(x+1)-P(x)|+|P(x+2)-P(x+1)|$$ so $P(x+1)-P(x)$ and $P(x+2)-P(x+1)$ have the same sign. Induction finishes. $\blacksquare$

By $(*),$ $x-y=P(x)-P(y)$ for all root $x,y$ of $Q$ (or $x-y=P(y)-P(x),$ but assume $P(x)-P(y)$ is positive) so $P(x)-x=P(y)-y=\ell.$ We are done by considering $R(x)=P(x)-x-\ell,$ noting $n=\text{deg}(P)=\text{deg}(R)\ge\text{deg}(Q).$ $\square$

Suppose we have $P^k(a)=a$ and $P^k(b)=b$, so $P^k(a)-P^k(b)=a-b$. Since $x-y \mid p(x)-p(y)$ for all integer polynomials $p$, we have
$$a-b \mid P(a)-P(b) \mid P^k(a)-P^k(b)=a-b,$$
hence $|P(a)-P(b)|=|a-b|$. Not suppose $r_1>\ldots>r_m$ are the roots of $P^k(x)-x$, so we have $|P(r_i)-P(r_j)|=|r_i-r_j|$. I claim that $(r_i,P(r_i))$ are all collinear. Shift $P$ such that $P(r_1)=r_1$, and also WLOG $P(r_2)-P(r_1)=r_2-r_1$, so $P(r_2)=r_2$. Now, for any $i>2$, we have $P(r_i)-P(r_1)=P(r_i)-r_1=\pm(r_i-r_1) \implies P(r_i) \in \{r_i,2r_1-r_i\}$. Likewise, replacing $1$ with $2$ gives $P(r_i) \in \{r_i,2r_2-r_i\}$, hence $P(r_i)=r_i$ for all $i$. But if $m>n$, then $P$ is linear on at least $n+1$ points, which implies that $P$ itself is linear—contradiction. $\blacksquare$

Let $x$ be a value for which $Q(x)=x$. Note that \[x-P(x)\mid P(x)-P^2(x)\mid \dots \mid P^k(x)-P^{k+1}(x)=x-P(x)\] so $d=|P^i(x)-P^{i+1}(x)|$ is constant for $i=0,1,\dots,k-1$. Now, we'll show that if $Q(x)=x$ then either $P(x)=x$ or $P(P(x))=x$.

Suppose otherwise, then $k\ge 3$. Without loss of generality, let $P(x)=x+d$. If $d=0$ we are done. If $P(P(x))=x$ we are done. If not, $P(P(x))=x+2d$. Thereafter, by discrete continuity there exists $i\ge 1$ such that $P^i(x)=x+d$ and $P^{i+1}(x)=x$. However, $P^{i+1}(x)=P(P^i(x))=P(x+d)=x+2d$, contradiction.

It suffices to show that for at most $n$ integers does $P(x)=x$ or $P(P(x))=x$. Suppose $P(P(x_1))=x_1$ and $P(P(x_2))=x_2$, then $x_1-x_2\mid P(x_1)-P(x_2)\mid x_1-x_2$ so $|x_1-x_2|=|P(x_1)-P(x_2)|$. Similarly, $|x_1-P(x_2)|=|x_2-P(x_1)|$. Therefore, $x_1+P(x_1)=x_2+P(x_2)$. Thus, for all $x$ such that $Q(x)=x$, $x+P(x)$ is constant. Clearly, for any given constant $c=x+P(x)$ has at most $n$ roots. We are done.

It seems to me that the fact that $Q$ is an iterate of $P$ is unnecessary; we only need $Q = g \circ P$ for some non-constant polynomial $g$. The fact that we are working over integers is unnecessary; any integral domain whose group of units is $\{\pm 1\}$ works as well. I'll attempt a more general problem of interest.

(In contrast, post #46 seems to be mainly interested in the cycles itself; just in case someone finds this post similar to #46...)

[quote]
Let $R$ be an integral domain such that its group of units, $R^{\times}$, is finite. Let $P \in R[X]$ be a polynomial of degree $n > 1$, and let $g \in R[X]$ be an arbitrary polynomial. Then $g \circ P$ has at most $\max\{n, |R^{\times}| + 1\}$ fixed points, and at most $n$ points if $|R^{\times}| = 2$, even when $n = 2$.
[/quote]

I'll prove this when $|R^{\times}| = 2$ and when $R$ has positive characteristic. Further comments come after the attempted partial solution.

------------
Clearly, we can assume that $g$ is non-constant; else $g \circ P$ is constant and this only has one fixed point.

By the theory of polynomials, for any $x, y \in R$, we have $x - y \mid P(x) - P(y) \mid g(P(x)) - g(P(y))$. In particular, since $R$ is an integral domain, if $x$ and $y$ are fixed points of $g \circ P$, then $P(x) - P(y)$ and $x - y$ are associates, i.e. $P(x) - P(y) = \alpha (x - y)$ for some $\alpha \in R$. Note that here, $\alpha$ may depend on $x$ and $y$, but the choice of $\alpha$ is unique if $x \neq y$. We will ignore $g$ from now on.

Consider the complete graph $G = (V, E)$, where $V \subseteq R$ is the set of fixed points of $g \circ P$. Note that $V$ is finite since $\deg(g \circ P) = \deg(g) \deg(P) > 1$. Our goal is to show that $|V| \leq \max\{n, |R^{\times}| + 1, 25\}$.

We colour each edges in $G$ with a unit of $R$; given $x, y \in V$ distinct, the edge $(x, y)$ is coloured $\alpha \in R^{\times}$ iff $P(x) - P(y) = \alpha(x - y)$. This is always possible due to the second previous paragraph. We claim that each triangle in $G$ uses exactly $1$ colour or $3$ colours. Indeed, fix a triangle in $G$, say with vertices $x, y, z$, and suppose that two of its edges have the same colour, say $(x, y)$ and $(x, z)$ with colour $\alpha \in R^{\times}$. Then $P(x) - P(y) = \alpha(x - y)$ and $P(x) - P(z) = \alpha(x - z)$... but then this forces $P(y) - P(z) = \alpha(y - z)$. So the third edge, $(y, z)$, also has colour $\alpha$, as desired.

The above setup provides a quick solution when $|R^{\times}| = 2$. Indeed, in this case, we only have $2$ colours available, so every triangle in $G$ has to be monochromatic. Since $G$ is complete, this necessarily implies that $G$ is monochromatic, i.e. $P(x) - P(y) = \alpha(x - y)$ for all $x, y \in V$. In particular, there exists a constant $c \in R$ such that every element of $V$ is a root of the polynomial $P(X) - \alpha X - c$. This forces $|V| \leq n$ since $\deg(P) = n > 1$. The same holds as long as $G$ is monochromatic, even when $|R^{\times}| > 2$.

On the other hand, consider the case where $R$ has characteristic $p > 0$, necessarily prime. The upper bound $|R^{\times}| + 1$ works here. To prove this, I'll start by proving a cute property that $R^{\times} \cup \{0\}$ is in fact a field contained in $R$.

[hide=Proof]
To prove that $R^{\times} \cup \{0\}$ is a field, it suffices to show that it is an additive group. Indeed, it is naturally closed under multiplication, and all its non-zero elements have an inverse by definition of units.

First, if $p \mid |R^{\times}|$, Cauchy's theorem implies that there exists $a \in R$, $a \neq 1$ such that $a^p = 1 \iff (a - 1)^p = 0$. A contradiction, since $R$ is an integral domain, so $p \nmid |R^{\times}|$. That means $|R^{\times}| \mid p^k - 1$ for some $k \geq 1$.

Now we show that $R^{\times} \cup \{0\}$ is a group. It can be reduced to showing that for any $a, b \in R^{\times}$ with $a \neq b$, we have $a - b \in R^{\times}$. Since $R$ has characteristic $p$, we have $(a - b)^{p^k} = a^{p^k} - b^{p^k}$. Since $a, b \in R^{\times}$ and $|R^{\times}| \mid p^k - 1$, we get $(a - b)^{p^k} = a - b$. Since $a \neq b$, this implies $(a - b)^{p^k - 1} = 1$. Thus $a - b$ is a unit, as desired.
[/hide]

For any triangle $(a, b, c)$ with $3$ colours, say with $(a, b)$ of colour $\gamma$, $(b, c)$ with colour $\alpha$, and $(c, a)$ of colour $\beta$, we obtain the equation $\gamma(a - b) + \alpha(b - c) + \beta(c - a) = 0$. In particular, solving for $c$ in terms of $a$, $b$, and the units $\alpha$, $\beta$, and $\gamma$ yields
\[ (\gamma - \beta)(a - b) + (\alpha - \beta)(b - c) = 0 \iff c = b + \frac{\gamma - \beta}{\alpha - \beta} (a - b). \]
If we write $a = b + r$, then $c = b + \delta r$, where $\delta = \dfrac{\gamma - \beta}{\alpha - \beta}$. But it is a unit by the above proof in this case. This sets up the solution for the positive characteristic case.

Now fix a triangle $(a, b, c)$ with $3$ colours, and write $b = a + r$. As above, $c = a + \delta r$ for some unit $r$. Not only that, since $(a, b)$ and $(a, c)$ has distinct colour, for any $d \in V$ with $d \neq a, b, c$, the edge $(a, d)$ has distinct colour with at least one of $(a, b)$ or $(a, c)$. The previous paragraph yields that $d - a$ is a unit multiple of $r$ or $\delta r$; since $\delta$ is a unit, $d - a$ is a unit multiple of $r$ regardless. This means any vertices in the graph $G$ is either $a$ or can be written as $a + \alpha r$ for some unit $\alpha$. This proves that $|V| \leq |R^{\times}| + 1$.

----------------
For characteristic zero case, one can show that $|R^{\times}| \leq 6$, and $R$ contains $\mathbb{Z}[i]$ if $|R^{\times}| = 4$, or $\mathbb{Z}[\omega]$ if $|R^{\times}| = 6$, where $\omega = \dfrac{1 + \sqrt{-3}}{2}$. In the former case with $G$ non-monochromatic, I got $|V| \leq 5$ by direct bashing. In the latter case, I got $|V| \leq 25$ using pure graph theory. But $25$ seems far from the best... would $|V| \leq 7$ be possible?

Clearly the claim hold for $k=1$ as $P(x)-x$ has at most $\deg(P)$ number of real zeors.\\

Now suppose $k$ is the minimal integer such that $P^{k}(t)=t$.\\

$\textcolor{red}{\mathrm{Claim:-}}$ either  $k=1$ or $k=2$.\\

$\textcolor{blue}{\mathrm{Pf:}}$ for $k=1$ it's shown , define $a_{n+1}=P(a_{n})$ for $n \geqslant 0$ , where $a_{0}=x$ and $P(a_{k})=a_{0}$  , now define $d_{i}=a_{i+1}-a_{i}$\\

Now since $P(x) \in \mathbb{Z}[x]$ , we have $a_{i+1}-a_{i}|P(a_{i+1})-P(a_{i}) =a_{i+2}-a_{i+1}=d_{i+1}$\\

so we have $d_{i}|d_{i+1}$ $\forall$ $0 \leqslant i \leqslant k$\\

now we also have $a_{k+1}=x$  , so $a_{k+1}=a_{0}$ , and $a_{k+2}=a_{1}$ , hence we have $d_{k+1}=d_{0}$\\

hence we have $|d_{0}|=|d_{1}|=|d_{2}|=\cdots =|d_{i}|=\Omega$ for $0 \leqslant i \leqslant k+1$\\

Now:\\

[list]

[*] if $\Omega=0$\\

so we have all $a_{i}'s$ to be equal , giving us $k \geqslant 3$ is not possible.\\

[*] if $\Omega \neq 0$\\

so we have that the set $\{ a_{1} , a_{2} , \cdots , a_{k+1}\} \subseteq \mathbb{Z}^{+}_{0}$ , hence by well ordering principle  this set has a minimum. say $a_{\ell}$ , so $a_{\ell-1}>a_{\ell}$ , $a_{\ell+1}>a_{\ell}$ , so we have $d_{\ell-1}=-d_{\ell} \implies a_{\ell-1}=a_{\ell+1}$  , now we can take $P$ over until we get $a_{2}=a_{0}=x$ , or if not then we have $P(a_{\ell-2})=P(a_{\ell})\implies a_{\ell-2}=a_{\ell}$ so we do this until we get $a_{2}=a_{0}$
[/list]

 Hence in either case we have $k=2$ or $k=1$. So claim follows $\square$.
-----
Now:\\

$\textcolor{red}{\mathrm{Claim:}}$ $P(P(x))=x$ has at most $\deg(P)$ number of integer solutions.\\

$\textcolor{blue}{\mathrm{Pf:}}$ FTSOC assume that $P(P(x))=x$ has more than $\deg(P)$ number of solutions, suppose the solution set is represented by $\mathcal{S}:=\{x_{1}, x_{2} , \cdots x_{\deg(P)+m}\}$ for $m \in \mathbb{Z}^{+}$ , then we have $x_{1}-x|P(x_{1}-P(x)|P(P(x_{1})-P(P(x))=x_{1}-x \implies P(x_{1})-P(x)=|x_{1}-x|$ for each $x \in \mathcal{S}$, so we get the polynomial equation $P(x)-x+c=0$ for some constant $c$ has more roots than it's degree which is a contradiction, hence the claim follows. $\square$\\

and hence  there are at most $n$ integers $t$ such that $Q(t)=t.$

$\color{red}\textbf{Claim:-}$ We have to prove there are at most $n$ integers $t$ such that $Q(t)=t.$

$\color{blue}\textbf{Proof:-}$ We have $P(x)$ is an integer polynomial with degree $n > 1.$ And satisfies $Q(x)$ is a polynomial satisfies $$Q(x)=P(\underbrace{P(....(P(x)....))}_{\textbf{k times.}}\implies \boxed{Q(x)=P^{k}(x).}$$ For proving this we use two lemmas.

$$\textbf{Lemma-1:-}   P^k(x)=x\implies P^2(x)=x.$$  and

$\textbf{Lemma -2:-}$ If $a$ and $b$ are two distinct integers and let $P(x)$ is a polynomial with integer coefficients then it satisfies $$a-b|P(a)-P(b).$$ Assume for contradiction.  Let's say  $Q(t)=t$ has at least $n+1$ integer solutions. Now $\forall x$ $Q(t)=t\implies P(x)=x.$ The number of integer solution is at most $n$
Now Let's assume for every integer $y$ it follows that $Q(t)=t$ but $P(x) \ne x.$ But this satisfies $P^2(x)=x$ by first Lemma.
We get from $$a-b|P(a)-P(b)\implies x-y|P(x)-P(y)|\underbrace{P(P(x)-P(P(y))}_{=x-y}$$ Therefore we get, $$x-y|P(x)-P(y)|x-y$$ Now from divisibility rule we get, $$|x-y| \le |P(x)-P(y)| \le |x-y|\implies \boxed{x-y=\pm P(x)\pm P(y).}$$ Now From First equation we get, $$x-y=\underbrace{P(x)}_{=x}-P(y)\implies \boxed{y=P(y).} \implies\textbf{contradiction.}$$ Now from second equation we get, $$x-y=-P(x)+P(y)\implies x+P(x)=y+P(y).$$ Now we have $$P^k(x)=x\implies P^2(x)=x\implies x+P(x)=y+P(y).$$ Let's assume $y$ is a constant $c$ we get, $x+P(x)=c$ has integer solution. Therefore from this we also get, $$x+P(x)=c\implies Q(x)=x.$$

Consider $P^k\left(x\right)=x$ and $P^k\left(y\right)=y$
It is obvious that $\left|P\left(x\right)-P\left(y\right)\right|=\left|x-y\right|$
So for any $t\in\mathbb{N}$,$P^t\left(x\right)-P^t\left(y\right)\mid P\left[P^t\left(x\right)\right]-P\left[P^t\left(y\right)\right]$
Then we get $P\left(x\right)-P\left(y\right)\mid x-y$
$\left|P\left(x\right)-P\left(y\right)\right|=\left|x-y\right|$
Now consider $a_1<a_2<\ldots<a_d$,$P^k\left(a_i\right)=a_i$
$\left|P\left(a_{i+2}\right)-P\left(a_{i+1}\right)\right|+\left|P\left(a_{i+1}\right)-P\left(a_i\right)\right|=a_{i+2}-a_i=\left|P\left(a_{i+2}\right)-P\left(a_i\right)\right|=\left|P\left(a_{i+2}\right)-P\left(a_{i+1}\right)+P\left(a_{i+1}\right)-P\left(a_i\right)\right|$
$P\left(a_{i+1}\right)-P\left(a_i\right)$ and $P\left(a_{i+2}\right)-P\left(a_{i+1}\right)$ have the same symbol
So $P\left(a_i\right)$ is monotony,Let it be monotonously incremental
$\left|P\left(a_{i+1}\right)-P\left(a_i\right)\right|=a_{i+1}-a_i$
$P\left(a_i\right)-a_i=C$
$P\left(x\right)-x-C$ The number of times is k
So d is smaller than k
Certification


calculus
integration
calculus computations

solve the following differential equation

(dy/dx) - y=xy5

i got upto

du/dx +4u = -4x (as i set u= 1/(y^4)

after doing some reading on intergrating factors, from

du/dx +4u = -4x

ive used the intergrating factor, whereby f(x) = -4x and a(x) = 4

so g(x)= exp^(intergral of 4 dx)

so g(x) = e^4x

now using the formula y= 1/g(x).[intergral of f(x)g(x) dx]

so y=1/e^4x [intergral -4xe^4x]

is this correct and how would i carry on from this?javascript:emoticon(':maybe:')
maybe

hello, at first you must solve the homogenius part of your equation:
$ \frac{du}{dx}\equal{}\minus{}4u \Leftrightarrow \frac{du}{u}\equal{}\minus{}4dx$. From here we have
$ u\equal{}Ce^{\minus{}4x}$. You can find a special solution of the inhomogenius part
by making the ansatz $ y_p\equal{}Ax\plus{}B$. After a simple calculation we get
$ u\equal{}Ce^{\minus{}4x}\plus{}\frac{1}{4}\minus{}x$. With $ y^4\equal{}\frac{1}{u}$ you can find the solution of your equation $ \frac{dy}{dx}\minus{}y\equal{}xy^5$.
Sonnhard.


geometry
parallelogram
circumcircle
analytic geometry
geometry proposed

$ 1\blacktriangleright$ [color=darkred]Let $ ABC$ be a triangle with the circumcircle  $ C(O,R)$ and the incircle $ C(I,r)$, where $ I\not\equiv O$. Suppose $ a\ge b$ and $ a\ge c$.

Denote the points $ \{\begin{array}{c}D\in (AB)\ ,\ AD=a-b\\\\ E\in (AC)\ ,\ AE=a-c\end{array}$ and the circumcenter $ S$ of the triangle $ ADE$. Prove that $ AIOS$ is a parallelogram.

================================================================================================

$ 2\blacktriangleright$ [size=134][b]Extension.[/b][/size] Let $ ABC$ be a triangle with the circumcircle  $ w=C(O,R)$ and the incircle $ C(I,r)$, where $ I\not\equiv O$.

Denote the points $ \{\begin{array}{c}D\in (BA\ ,\ E\in (CA\\\\ BD=CE=b+c-a\end{array}$ and the circumcenter $ S$ of the triangle $ ADE$. Prove that $ AIOS$ is a parallelogram.[/color]

It should be easy to find the barycentric coordinates of S because it is the intersection of the perpendicular bisectors of AD and AE. The rest is an ugly computation. Perhaps there is a better solution?

[color=blue][b]Lemma1[/b][/color]: Let $ ABC$ be a triangle and $ O$ it circumcenter. $ D,E$ are on $ AC,AB$ such $ B,C,D,E$ is cyclic. Then $ AO$ is perpendicular to $ DE$.
[color=blue][b]Lemma2[/b][/color]:  http://www.mathlinks.ro/Forum/viewtopic.php?t=14655

Denote the points $ \{\begin{array}{c}X\in (BA\ ,\ Y\in (CA\\ \\ BX = CY = a\end{array}$. then  $ \{\begin{array}{c}AX = a-c, AD = b-a\\ \\ AY = a-b,AE = c-a\end{array}$ therefore $ AX\cdot AD = AY\cdot AE$. Therefore $ D,E,X,Y$ are cyclic. so $ \triangle AED$ and $ \triangle AXY$ are inversely similar.

Therefore, by lemma1, $ AS$ is perpendicular to $ XY$. By lemma2, $ XY$ is perpendicular to $ OI$. So $ AS$ is parallel to $ OI$.

I can prove $ OS$ is parallel to internal or external bisector of $ A$ using directed angle. But I can't prove $ OS$ is parallel to internal bisector of $ A$.

So I will prove $ AS$=$ IO$. Since $ \triangle AED$ and $ \triangle AXY$ are congruent, $ AS$ is circumradius of $ \triangle AXY$.

So it is suffice to show circumradius of $ \triangle AXY$ is $ OI$. This can be proved using proof of darij grinberg:[url]http://www.mathlinks.ro/Forum/viewtopic.php?t=14655[/url]


Solve the equation in $\mathbb{Z}$ , where $n\geq 2$ and $x^n+y^n=1994.$

Hay Guys I think it is beautiful ,isn't it?  ;)


Find the first integer $ n > 1$ such that the average of

$ 1^{2}, 2^{2}, 3^{2}, ..., n^{2}$

is itself a perfect square.

Hi Andrew;

Interesting problem could only find this:

n=337 is the next solution:

Problem reduces down to finding integer solutions to

A)   2n^2 +3n +1 = 6 y^2 which is not exactly a pell equation.

Another solution is
y = 37829
n = 65521

from the factorization:

(n+1)(2n+1) = 6 y^2 you can see that n must be odd.

I finally achieved a parametrization for n and y:

Xn+1 = -7 Xn -12 Yn - 6
Yn+1 = -4 Xn -7 Yn - 3

Since we have X1 = 337 and Y1 = 195 we just plug into the double recurrence which yields X2 = -4705, Y2 = -2716 which are false solutions. Now plug them in and you get X3 = 65521, Y2 = 37829. You can get the rest in the same way.


Let $ a, b, c, d$ be real numbers such that $ \max\{a,b,c,d\}\cdot\min\{a,b,c,d\}\ge \sqrt{abcd}$. Prove that
\[ \max\{a,b,c,d\} \plus{} \min\{a,b,c,d\}\ge\frac {a \plus{} b \plus{} c \plus{} d}{2}.
\]

[hide="Solution"]
WLOG, assume $ a\ge b\ge c\ge d$. So we have $ ad\ge bc$ and we have to prove $ a \plus{} d\ge b \plus{} c$.  Let $ a \equal{} b \plus{} x,c \equal{} d \plus{} y$. Now we have to prove $ x\ge y$. $ ad\ge bc$, so $ bd \plus{} xd\ge bd \plus{} yb$, and so we get $ xd\ge yb$ or  $ x\ge y$. [/hide]

Very nice Bugi! A slightly stronger one:

Let $ a\ge b\ge c\ge d$ be real numbers such that $ a\plus{}b\plus{}c\plus{}d\equal{}2$. Prove that
\[ a^2\plus{}2bc\plus{}d^2\ge 1.\]
Note that the initial post in this thread is a corollary of the above, as we use $ ad\ge bc$. Have fun with this one!

[quote="Bugi"]
 and so we get $ xd\ge yb$ or  $ x\ge y$. [/quote]
You can't get $ x\ge y$. Note that $ b,d$ can be negative or 0, not only positive :maybe:
For example, let's try $ d\equal{}\minus{}2,b\equal{}\minus{}1$ and $ x\equal{}2,y\equal{}1$ so $ xd\equal{}\minus{}4\ge yb\equal{}\minus{}1$?? :huh:
.


induction
function
superior algebra
superior algebra unsolved

Hello out there.

I'm working on a proof by induction of the Wronskian and need a little boost to get going.

So, here goes:

If [tex]y_1,...,y_n \in C^n[a,b][/tex], then their Wronskian is:

[tex]Wr(y_1,...,y_n)=det\left(\begin{array}{ccc}y_1&\cdots&y_n\\y_1\prime&\cdots&y_n\prime\\\vdots&\vdots&\vdots\\y_1^{(n-1)}&\cdots&y_n^{(n-1)}\end{array}\right)[/tex]

In general, a set of functions will be linearly independent IFF the Wronskian is not identically zero.

Prove this for n = 2, that is [tex]f(x), g(x)[/tex] are independent IFF

[tex]\left\vert\begin{array}{cc}f(x)&g(x)\\f\prime(x)&g\prime(x)\end{array}\right\vert[/tex] is not identically zero.

Okay, I think I understand how to prove this in one direction. That is, assuming the [tex]Wr(f,g) \neq 0[/tex] and showing that [tex]f(x), g(x)[/tex] are independent.

But I'm a little stuck in the assumptions for proving the other direction.

Any and all help would be greatly appreciated.

Thanks,
Bailey

try to ptove that $y->(y(x_0), y'(x_0),..,y^{(n-1)}(x_0))$ is an isomorphism if the differential is a linear homogenous.(Cauchy)

This is what I have for the proof in one direction:

Assume [tex]Wr(f(x),g(x)) \neq 0[/tex].
Then there exists some [tex]x_o[/tex] such that [tex]Wr(f(x_o),g(x_o)) \neq 0[/tex].

Assume:
[tex]c_1 f(x) + c_2 g(x) \equiv 0[/tex]
[tex]c_1 f\prime(x) + c_2 g\prime(x) \equiv 0[/tex]

then
[tex]c_1 f(x_o) + c_2 g(x_o) = 0[/tex]
[tex]c_1 f\prime(x_o) + c_2 g\prime(x_o) = 0[/tex]

We have two equations in the unknowns [tex]c_1[/tex] and [tex] c_2[/tex].

[tex]\left \vert \begin{array}{cc}f(x_o) & g(x_o) \\ f \prime (x_o) & g \prime (x_o) \end{array} \right \vert \neq 0 [/tex]

Therefore there are unique solutions.

One such solution is: [tex]c_1 = c_2 = 0[/tex]

This turns out to be the only solution.

Therefore [tex]f(x)[/tex] and [tex]g(x)[/tex] are independent.

.....
I'm sure my wording is a little off.  But I'm still confused about how I would prove it the other way.

Thanks,
Bailey

I think $W(f, g)\equiv 0$ does not imply $f(x), g(x)$ are dependent. Consider $f(x)=x^2|x|$ and $g(x)=x^3$, which are independent on $-1<x<1$ but $W(f, g)\equiv 0$ in $(-1, 1)$.
But I think it is true if $f(x)$ and $g(x)$ are solutions of some linear second order ODE.


1.How many circles in the plane contain at least three of the points (0, 0, ), (0, 1),
(0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)?

2. Nine points are distributed around a circle in such a way that when all 9
2pairs
of points are connected by segments, no three of the segments are concurrent.
How many points of intersection are there inside the circle?

3. Two points are randomly and simultaneously selected from the 4 × 5 grid of
20 lattice points {(m, n)|1  m  5 and 1  n  4}. What is the probability
that the distance between them is rational?

4. A falling number is an integer whose decimal representation has the property
that each digit except the units digit is larger than the one to its right. For
example 96521 is a falling number but 89642 is not. How many n-digit falling
numbers are there, for n = 1, 2, 3, 4, 5, 6, and 7?

5. How many numbers can be expressed as a sum of four distinct members of the
set {17, 21, 25, 29, 33, 37, 41}?

6. How many numbers can be obtained as the product of two or more of the
numbers 3, 4, 4, 5, 5, 6, 7, 7, 7?

7. (1994 UNC Charlotte Comprehensive Exam) How many of the first 100 positive
integers are expressible as a sum of three or fewer members of the set
{30, 31, 32, 33, 34} if we are allowed to use the same power more than once. For
example, 5 can be represented, but 8 cannot.

8. How many integers can be expressed as a sum of two or more different members
of the set {0, 1, 2, 4, 8, 16, 31}?

9. John has 2 pennies, 3 nickels, 2 dimes, 3 quarters, and 8 dollars. For how
many different amounts can John make an exact purchase?

10. What is the size of the largest subset, S, of {1, 2, 3, . . . , 50} such that no pair
of distinct elements of S has a sum divisible by 7?

11. Recall that a Yahtzee Roll is a roll of five indistinguishable dice.
a. How many different Yahtzee Rolls are possible?
b. How many Yahtzee Rolls have exactly 3 different numbers showing?

12. How many six digit numbers
a. consist of six different digits?
b. consist of five different digits?
c. consist of three odd and three even digits?
d. have six different digits with no two even digits adjacent?
e. have four distinct odd digits and two distinct even digits which are not
adjacent?

13. How many four digit numbers abcd satisfy |a − d| = 2?

14. A box contains 2 pennies, 4 nickels, and 6 dimes. Six coins are drawn without
replacement, with each of the 12 coins having the same probability of being
chosen. What is the probability that the value of the coins is at least 50 cents?

15. Let S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.
a. How many five element subsets does the set have?
b. How many subsets of S have an odd number of members?
c. How many subsets of S have 1 as a member?
d. How many subsets have 1 as a member and do not have 2 as a member?

16. How many positive integers less than 1000 have an odd number of positive
integer divisors?

17. How many integers can be obtained as a sum of two or more of the numbers
1, 3, 5, 10, 20, 50, 82?

 :)


I have a few questions to ask. I have these probability questions but am slightly unsure to how to solve them. Please help.

[quote]1(a) The probability that an event A occurs is P(a)=0.4. B is an event independent of A and P(A or B or both) = 0.7. Find (B)

(b) C and D are two event such that P(D|C)=$ \frac{1}{5}$ and P(D|D)=$ \frac{1}{4}$. Given that P(C and D occur) = [i]p[/i], (i) P(c), (ii) P(D).

(c) Given also that P(C or D or both occur)=$ \frac{1}{5}$, find the value of [i]p[/i].[/quote]

Thanks
 :?:

[quote="AstroPhys"][hide=" 1 a"]
$ P(a)\plus{}P(b)\plus{}P(a)\cdot P(b) \equal{} 0.7\Rightarrow P(b) \equal{}\frac{0.7\minus{}0.4}{1\plus{}0.4}\equal{}\frac{3}{14}$.
[/hide][/quote]

[hide="That should be"]$ P(a)\plus{}P(b)\minus{}P(a)P(b) \equal{} 0.7$, and the result is $ P(b) \equal{} 0.5$[/hide]

[hide="Another method"]$ 1\minus{}\overline{P(a)}\cdot\overline{P(b)}\equal{} 0.7$

$ \overline{P(a)}\cdot\overline{P(b)}\equal{} 0.3$

$ 0.6\overline{P(b)}\equal{} 0.3$

$ \overline{P(b)}\equal{} 0.5$

$ P(b) \equal{} 0.5$[/hide]

For 1.b did you mean to write $ P(C|D)$ rather than $ P(D|D)$?  Going on that suspicion:
[hide]
$ P(D|C) \equal{}\frac{P(C\cap D)}{P(C)}\implies\frac{p}{P(C)}\equal{}\frac{1}{5}\implies P(C) \equal{} 5p$.
Similarly, $ P(C|D) \equal{}\frac{P(C\cap D)}{P(D)}\implies P(D) \equal{} 4p$.

[/hide]


If $ AD, BE, CF$ are cevians of $ \Delta ABC$ concurrent at a point $ P$ inside it, prove that
1.$ \frac {AP}{PD} \plus{} \frac {BP}{PE} \plus{} \frac {CP}{PF} \geq 6$

2.$ \frac {AP}{PD}. \frac {BP}{PE}. \frac {CP}{PF} \geq 8$

3.$ \frac {AD}{PD}. \frac {BE}{PE}. \frac {CF}{PF} \geq 27$

4.$ \frac {AD}{AP} \plus{} \frac {BE}{BP} \plus{} \frac {CF}{CP} \geq \frac {9}{2}$

5.$ \frac {PD}{AP} \plus{} \frac {PE}{BP} \plus{} \frac {PF}{CP} \geq \frac 32$

$ \frac{AF}{FB}\equal{}n$ , $ \frac{BD}{DC}\equal{}m$ , $ \frac{CE}{EA}\equal{}k$  --> $ nmk\equal{}1$--->
(Van-obel )
$ \frac{AP}{PD}\equal{}\frac{AF}{FB}\plus{}\frac{AE}{EC}\equal{}n\plus{}\frac{1}{k}$
$ \frac{BP}{PE}\equal{}\frac{BD}{DC}\plus{}\frac{BF}{FA}\equal{}m\plus{}\frac{1}{n}$
$ \frac{CP}{PF}\equal{}\frac{CD}{BD}\plus{}\frac{CE}{EA}\equal{}\frac{1}{m}\plus{}k$
$ \frac{AD}{PD}\equal{}1\plus{}\frac{AP}{PD}\equal{}1\plus{}n\plus{}\frac{1}{k}$
$ \frac{BE}{PE}\equal{}1\plus{}\frac{BP}{PE}\equal{}1\plus{}m\plus{}\frac{1}{n}$
$ \frac{CF}{PF}\equal{}1\plus{}\frac{CP}{PF}\equal{}1\plus{}\frac{1}{m}\plus{}k$

$ 1. \frac{AP}{PD}\plus{}\frac{BP}{PE}\plus{}\frac{CP}{PF}\equal{}n\plus{}\frac{1}{k}\plus{}m\plus{}\frac{1}{n}\plus{}\frac{1}{m}\plus{}k\geq 6\sqrt[6]{\frac{mnk}{mnk}}\equal{}6$
$ 2. \frac{AP}{PD}\frac{BP}{PE}\frac{CP}{PF}\equal{}(n\plus{}\frac{1}{k})(m\plus{}\frac{1}{n})(\frac{1}{m}\plus{}k)\geq 2\sqrt{\frac{n}{k}} 2\sqrt{\frac{m}{n}} 2\sqrt{\frac{k}{m}}\equal{}8$
$ 3.\frac{AD}{PD}\frac{BE}{PE}\frac{CF}{PF}\equal{}(1\plus{}n\plus{}\frac{1}{k})(1\plus{}m\plus{}\frac{1}{n})(1\plus{}\frac{1}{m}\plus{}k)\geq3\sqrt[3]{\frac{n}{k}}3\sqrt[3]{\frac{m}{n}}3\sqrt[3]{\frac{k}{m}}\equal{}27$

[hide=" 4 and 5 are equivalent"]
Let $ x\equal{}(BPC)$,$ y\equal{}(CPA)$ and $ z\equal{}(APC)$
$ \sum{\frac{PD}{AP}}\equal{}\sum{\frac{x}{y\plus{}z}}\ge\frac{3}{2}$ and for this last one (Nesbitt's inequality) you can find here in the internet or by yourself infinitely many proofs.
[/hide]

 :)

Sorry in the post above it is $ z\equal{}(APB)$

This substitutions also works for 1, 2 and 3:
[hide="1"]
$ \sum{\frac {AP}{PD}}\equal{}\sum{\frac{y\plus{}z}{x}}\equal{}\sum{\frac{z}{x}\plus{}\frac{x}{z}} \ge 6$
[/hide]
[hide="2"]
$ \prod{\frac {AP}{PD}}\equal{}\prod{\frac{y\plus{}z}{x}}\equal{}\prod{\frac{y}{x}\plus{}\frac{z}{x}}\ge\prod{2\frac{\sqrt{yz}}{x}}\equal{}8$
[/hide]
[hide="3"]
$ \prod{\frac {AD}{PD}}\equal{}\prod{\frac{x\plus{}y\plus{}z}{x}}\equal{}\prod{1\plus{}\frac{z}{x}\plus{}\frac{y}{x}}\ge\prod{3\sqrt[3]{\frac{yz}{x^2}}}\equal{}27$
[/hide]

 :)


hi, im really suck with this one question n i cant seem to goet out of this mind block;

basically i need to show that 2sin(3x)sin(2x) = cos(x) - cos(5x)

any help would be greatly appreciated :lol:

its okay now, i managed to solve it, quite simple actually

its just the same as cos(3x-2x) - cos(3x+2x) = cosx - cos5x, then all i gotta do now is integrate!


vector
abstract algebra
superior algebra
superior algebra unsolved

What is the meaning of $ \mathbb{Z}/n\mathbb{Z}^\times$? The definition of $ \mathbb{Z}/n\mathbb{Z}$ is the set of congruence classes modulo n.

Read that as $ (\mathbb{Z}/n\mathbb{Z})^*$; the star (and I prefer an asterisk to a cross/x) belongs to the whole object. That star means "the multiplicative group of invertible elements" in a ring, so this is the group of invertible elements in the ring of integers mod $ n$.

[quote="jmerry"]Read that as $ (\mathbb{Z}/n\mathbb{Z})^*$; the star (and I prefer an asterisk to a cross/x)[/quote]

Bah... you really like asterisks in this context? They usually denote duals of vector spaces or modules - and there are good chances for both to make sense (an algebra is both a module and a ring, so $ *$ could mean both).

Or do you have a better way to distinguish between them?

  darij

I use both, but prefer $ ^\times$ as it feels better (hard to explain  :D ).

I don't think I've ever had a problem with ambiguous notation in context here. There aren't many places where both a group and a module or vector space could make sense. Also, there are very few reasons to talk about the dual of something one-dimensional.

Just to think of one example: "The inclusion map $ \mathbb{R}^{n\times n}\to\mathbb{C}^{n\times n}$ induces a map $ \left(\mathbb{R}^{n\times n}\right)^{\ast}\to\left(\mathbb{C}^{n\times n}\right)^{\ast}$." Of course, this is only clear in a context, but if the context just says "Consider $ \mathbb{R}^{n\times n}$ and $ \mathbb{C}^{n\times n}$ as $ \mathbb{R}$-algebras", this would be ambiguous.

Some people write $ A^{\vee}$ for the dual of $ A$. Of course, if such a notation is consequently used, we can denote multiplicative groups by $ \ast$ without having to worry.

  darij

[quote="LydianRain"]Well if it's really the dual, the map would be in the opposite direction. :)[/quote]

 :D You are right here. But imagine $ \mathbb{R}^{n\times n}\to\mathbb{R}^{n\times n}$ ;)

  darij

Here I am finding the automorphisms of $ \mathbb{Z}/n\mathbb{Z}$. It says that Aut$ \mathbb{Z}/n\mathbb{Z}\equal{}{\mathbb{Z}/n\mathbb{Z}}^\times$.

[quote="kan"]Here I am finding the automorphisms of [b]the group[/b] $ \mathbb{Z}/n\mathbb{Z}$.[/quote]If you paid attention to my first post, I already answered your question- and those automorphisms act by the natural ring multiplication.

Without the bold words I added, we can't specify an automorphism group. The only automorphism of $ \mathbb{Z}/n\mathbb{Z}$ as a ring or field is trivial.

For a more interesting problem, count the automorphisms of $ \mathbb{Z}\slash n\mathbb{Z}$ as a ring without unity.

  darij

Not really. If there is an identity, we can always identify it uniquely by its multiplicative action, and thus it must be sent to itself by any automorphism. Ignoring the identity is only significant if we look at non-surjective maps.

Bah... sorry  :blush: read endomorphisms for automorphisms.

  darij


vector
geometry
angle bisector
geometry solved

XOY is angle in the plane.A,B are variable point on OX,OY such that 1/OA+1/OB=1/K (k is constant).draw two circles with diameter OA and OB.prove that common external  tangent to these circles is tangent to the constant circle( ditermine the  radius and the locus of its center).

consider rays OA OB OD
where OD bisect the angle BOA.
Draw a circle with center O and radius 1.
Then inverse A B D with respect to the circle.
We got A'B'D',and here A'B'D'O are cyclic.
Also <A'OD'=<D'OB',by Ptolemy's Theorem.
We have (A'O)+(B'O)=k(D'O)
this leads to 1/OA+1/OB=k/OD
So,if 1/OA+1/OB is a constant 1,line AB pass through
a fixed point D on the angle bisector of <BOA.

Take the midpoint C of OD as center,1 the radius.
Because OC is the angle bisector,
AC/BC=AO/BO=a/b  (Let OA=a,OB=b)
Let T U be the midpoint of OA,OB
the vector <OC>=b/(a+b)<OT>+a/(a+b)<OU>
and the radius 1=[b/(a+b)](a/2)+[a/(a+b)](b/2)
(here we used 1/a+1/b=1)
By now we can easily check that with the circle we draw,
and the circles with diameter OA,OB.
They have two common tangents all the time.

Best regards,
Chao


find all positive integer $ x$ and $ y$ such that
$ x\minus{}y\equal{}x^2\plus{}xy\plus{}y^2$

[quote="greatestmaths"]find all positive integer $ x$ and $ y$ such that
$ x \minus{} y \equal{} x^2 \plus{} xy \plus{} y^2$[/quote]
[hide="Solution"]
\[ xy\minus{}x\plus{}y\minus{}1\equal{}\minus{}x^2\minus{}y^2\minus{}1\] \[ (x\plus{}1)(y\minus{}1)\equal{}\minus{}x^2\minus{}y^2\minus{}1<0\] Notice that $ (x\plus{}1)(y\minus{}1)\ge 0$ since $ x$ and $ y$ are positive integers and thus there are no solutions. [/hide]

Or you could note that $ x$ is real, so the discriminant is nonnegative, so

$ \minus{}3y^2\minus{}6y\plus{}1\ge 0$, but this implies that $ y<1$, so there are no solutions.

$ x\le x^2$ for positive integers and adding more stuff to the RHS makes the inequality strict.


equation
algebra
number theory
roots
parametric equation
IMO Longlist
IMO Shortlist

For which real numbers $p$ does the equation $x^{2}+px+3p=0$ have integer solutions ?

I dont get something, when you say integer solutions you are saying that both of it roots are integers or just one neccesarily?

Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=15623]introduction for the IMO ShortList/LongList project[/url] and regarding[url=http://www.mathlinks.ro/Forum/viewtopic.php?t=15623]solutions[/url]  :)

If that equation has an integer root, called $ x_{0}$, then $ x_{0}\not =-3$ and $ p=-\frac{x_{0}^{2}}{x_{0}+3}\in\mathbb Q$. We write $ p=\frac{m}{n}$, here $ \gcd (m,n)=1$.

Who can continue? :D

[quote="orl"]For which real numbers $ p$ does the equation $ x^{2}+px+3p=0$ have integer solutions ?[/quote]
$ \{p\in \mathbb{R}|\ x^{2}+px+3p=0\ have\ integer\ solution\}=\{-\frac{a^{2}}{a+3}|\ a\in\mathbb{Z}-\{-3\}\}$ :P


abstract algebra
linear algebra
matrix
algebra
function
domain
vector

Find the range and kernel of:
a) T(v1,v2) = (v2, v1)
b) T(v1,v2,v3) = (v1,v2)
c) T(v1,v2) = (0,0)
d) T(v1,v2) = (v1, v1)

Unfortunately the book I'm using (Strang, 4th edition) doesnt even mention these terms and my professor isn't helpful. My professor said:

"Since range and kernel are subspaces of R^2 (in this problem) you need not give a basis but, rather, simply describe the subspace (i.e. plane, line, zero subspace)"

I dont really know what I'm supposed to find. Let's look at d)

I constructed a 2 x 2 matrix:

[1 0][v1]   [v1]
[1 0][v2] =[v1]

Up to this point, I'm not sure what to do or if i'm doing this problem right...I'm stuck, please help!

Some synonymous terms used in linear algebra: range=column space, kernel=null space. The kernel is a subspace of the domain, and the range is a subspace of the codomain.

These can all be done without actually constructing matrices. The case (d) you were trying clearly has rank 1; $Tx$ is a multiple of $v_{1}$ for all $x$. The range of $T$ is the subspace $Fv_{1}$ ($F$ is the field), which is a line. The kernel in this case is another line, the multiples of $v_{1}-v_{2}$.

You're not constructing the matrices right. We want to think of the $v_{i}$ as columns, and also think of our coefficient vectors as columns; $a_{1}v_{1}+a_{2}v_{2}+\cdots+a_{n}v_{n}$ is represented by the column vector $\begin{pmatrix}a_{1}\\a_{2}\\ \vdots\\a_{n}\end{pmatrix}.$
The matrix $A=\begin{pmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{pmatrix}$ of $T$ relative to the basis $(v_{1},v_{2})$ has the property (in (d)) that $A\cdot \begin{pmatrix}1\\0\end{pmatrix}= \begin{pmatrix}a_{11}\\a_{21}\end{pmatrix}= \begin{pmatrix}1\\0\end{pmatrix}$ and $A\cdot \begin{pmatrix}0\\1\end{pmatrix}= \begin{pmatrix}a_{12}\\a_{22}\end{pmatrix}= \begin{pmatrix}1\\0\end{pmatrix}.$ That makes $A=\begin{pmatrix}1&1\\0&0\end{pmatrix}.$


modular arithmetic
number theory
least common multiple
function
relatively prime

[quote="futuremontrealian"]Here is my problem.  I am decently versed in modular arithmetic, but I still have no idea about any of the ways to find a number that is say x mod y as well as a mod b and c mod d.

If you need further clarification, I mean a problem like this:

Find x where x = 1 mod 7, 2 mod 5, 1 mod 2, 11 mod 13, and 22 mod 30.

How would I solve a problem like this?  It might be elementary, but I've never been taught it, and my math coach hardly ever does modular arithmetic.

Thanks if you could help![/quote]

[hide]Well I took the first two cases 1 mod 7 and 2 mod 5. then x can be represented as 7a+1 and 5b+2. so then 7a+1=5b+2, 7a=5b+1. then $7a\equiv 1\mod 5$, $7a\equiv 21\mod 5$, $a\equiv 3\mod 5$. Plug $a$ into 7a+1 and you get 35c+22=x, and $x\equiv 22\mod 35$. Just do that with each thing...and you should get your answer...

But then I just realized there's no solution...if x=1 mod 2, then x is even. But then it says 22 mod 30, which means x is even, contradicting itself.  :? [/hide]

lol sorry :)  i just put a jumble of numbers on there (I actually left the problem in my binder at school accidentally).  ty :)

I'll make it x = (for lack of congruency key) 1 mod 2, x = 23 mod 30, x = 5 mod 6.

The key to attacking these problems is converting the mod expressions into their algebraic counterparts. From there you deduce information about other unknown quantities by looking at divisibility.
If $x\equiv1 \pmod{2}$ we can write $x=2k+1$ for some integer $k$. Also, if $x\equiv23 \pmod{30}$, we can write $x=30j+23$ for some integer $j$. Note that $j$ and $k$ must be different. So let's equate these expressions for x:
$30j+23=2k+1$
We want to deduce more information about $j$ and $k$. Let's rewrite the equation as $30j+22=2k$. At this point we can divide through by 2 giving $15j+11=k$. So let's plug $k$ into the expression $x=2k+1$ to get $x=30j+23$. This information is useless because we already knew that! This is an important thing to keep in mind though. Notice that $x\equiv23 \pmod{30}$ implies $x\equiv1 \pmod{2}$, so an experienced number theororist would have discarded that congruence. Nevertheless, the techniques were important to go over.
In fact, the other congruence leads to the same thing. So we can discard it and any $x$ such that $x\equiv23 \pmod{30}$ is a solution.
So notice how this problem became trivial and the first had no solution. This tends to happen when the "mod" numbers (the 6, 30, 2) are not relatively prime. Since 6 and 30 share a factor greater than 1, 6, there is a possibility of getting no solution. The same follows with 2 and 6 or 2 and 30, as you noticed before.
Instead, let's try $x\equiv2 \pmod{5}$ and $x\equiv1 \pmod{3}$. We know that there exists an integer $k$ such that $x=2+5k$ and that there exists an integer $j$ such that $x=1+3j$. So $2+5k=1+3j$, or $1+5k=3j$. Consider the equation mod 3 (basically replay every number by its remainder when divided by 3). It becomes $1+5k\equiv0 \pmod{3}$. So $5k\equiv-1\equiv2\equiv5\pmod{3}$. Thus $k\equiv1 \pmod{3}$. This is the kind of information we wanted to deduce because now we can write $x=5k+2=5(1+3s)+2=7+15s$, for some integer $s$. This is our solution, which gives infinitely many integers that satisfy the conditions. If you had another congruence in the system we would get another algebraic expression and equate it to $7+15s$ to get more information, like ch1n... was doing.
I believe that congruences will have either no solution or infinitely many. Also notice that $15=3*5$, the product of our "mod" numbers. So in the future, the easy way to get a solution is to find a small integer (like 7) that satisfies the congruences, then realize that every other solution will differ by the lcm of the "mod" numbers. This is because adding the lcm to our original number will not change the remainder when you divide by either of the "mod" numbers. But be careful, because you need to check if there even is a solution. To be sure you understand you should do some practice problems.   ;)

[quote="ShoeFactory"][quote="chesspro"]You should look up the Chinese Remainder Theorem. It specifically addresses problems like this.[/quote]

The only thing it says is that a solution does exist and in what modulo it exists in.[/quote]

The CRT should give the modulo and the residue.

It's very curious that a lot of people learn the Chinese Remainder Theorem (CRT) as something like:

When you have residues $a_1,a_2,...,a_n$ and pairwise coprime moduli $m_1,m_2,...,m_n$, then there exists $x$ such that $x \equiv a_i \mod m_i$.

Forget that boring version!

Let $A$ be the set of all $n$-tupels $(a_1 \mod m_1,a_2 \mod m_2 ,..., a_n \mod m_n)$ (the $\mod$'s there will be omited from now) of residues $a_i \mod m_i$.
Let $M$ the set $M$ of residues $x \mod m=(m_1m_2...m_n)$.
Note that both, $A$ and $M$, have addition, subtraction, multiplication and sometimes division defined on them:
On $M$, we clearly have addition and multiplication, that one $\mod m$.
On $A$, it's the coordinatewise addition and multiplication given for $a=(a_1,a_2,...,a_n) , b= (b_1,b_2,...,b_n)\in A$ by $a+b = (a_1+b_1 \mod m_1, ... , a_n+b_n \mod m_n)$ and $a \cdot b = (a_1 \cdot b_1 \mod m_1, ... , a_n \cdot b_n \mod m_n)$.
Similar, differences can be defined on $A$ and $M$.
Also when $x \mod m$ is given and $\gcd(x,m)=1$, then an inverse $x^{-1} \mod m$ exists such that $x \cdot x^{-1} \equiv 1 \mod m$; these $x^{-1}$ can indeed be found by the Euclidian algorithm. By this, $a/b \mod m$ can be defined as $a b^{-1} \mod m$.
For $a=(a_1,a_2,...,a_n) \in A$, having an $a^{-1}=(b_1,b_2,...,b_n)$ means having $a_i b_i \equiv 1 \mod m_i$, thus inverses $\mod$ each single $m_i$. So this is possible iff $\gcd(a_i,m_i)=1$ everytime, such that in this cases we can define division through $a$ as before.

Then the CRT says that there existist a [u]bijective[/u] function $f$ from $A$ to $M$ such that:
a) $f(a_1,a_2,...,a_n) \equiv a_i \mod m_i$ (the most common part).
Let $a,b \in A$.
b1) $f(a+b)\equiv f(a)+f(b) \mod m$.
b2) $f(a-b)\equiv f(a)-f(b) \mod m$.
c) $f(a \cdot b)\equiv f(x) \cdot f(y) \mod m$.
d) An inverse of $a$ exists iff there is one for $f(a)$; then also $f(a^{-1}) \equiv f(a)^{-1} \mod m$.
e) Explicitely, $f$ is given by $f(a_1,a_2,...,a_n) = a_1 c_2 + ... + a_n c_n \mod m$ where $c_i \equiv 1 \mod m_i$ and $c_i \equiv 0 \mod m_j$ for $i \neq j$. Such $c_i$ can be found by the Euclidean algorithm.
(you need $x_i \cdot \prod_{j \neq i} m_j + k \cdot (-m_i) = 1$ and set $c_i=x_i \cdot \prod_{j \neq i} m_j$ then, clearly existing and constructible by Euclid)
f) I will not write that thing out, but when you bundle some of the $a_i$ together and use the CRT first only on each of those bundles $a_i$ and then on the result, the function given by this coincides with $f$; this is the way you normaly do: start with the frist two moduli, use the CRT for them, then use the CRT on the result and the third moduli and so on...

The conditions a) , b1) and c) can be summarized by the statemant that $A$ and $M$ are isomorphic as rings.
Without even knowing that you work $\mod$ something, with the conditions b1) and c) only you can e.g. show that $f(0)=0, f(1)=1, f(-a)=-f(a)$ and also b2) and d).

More generally, when $\mathfrak{a}_1, \mathfrak{a}_2 , ... , \mathfrak{a}_n$ are pairwise coprime ideals (meaning $\mathfrak{a}_i+\mathfrak{a}_j=R$ for $i \neq j$) of a commutative ring $R$ (with unity), we set $\mathfrak{a}: = \mathfrak{a}_1 \cdot \mathfrak{a}_2 \cdot ... \cdot \mathfrak{a}_n$ and have
\[ \prod_{i=1}^n R/\mathfrak{a}_i \cong R/\mathfrak{a} \]

that must be graduate level, right?  :huh:
I think I know the version of the Chinese Remainder Thm. your stating. Here's another way of saying it.
We want to find a solution to the linear system of congruences $x\equiv a_i \pmod{m_i}$, where the moduli (the $m_i$) are pairwise relatively prime and $1\leq i \leq k$.

Let $M=m_1m_2 \ldots m_k$ and $M_i=\frac{M}{m_i}$,$1\leq i \leq k$. Then $M_i \equiv 0 \pmod{m_j}$ when $i \not= j$ and since the moduli are pairwise relatively prime, $(M_i,m_i)=1$. The last observation tells us that we can find a unique $y_i$ such that $M_iy_i \equiv 0 \pmod{m_i}$ (by definition $y_i$ is the inverse of $M_i$). Here is our general solution to the system:

$x=a_1M_1y_1+a_2M_2y_2+\ldots+a_kM_ky_k$. All other solutions differ by $LCM(m_1,m_2,\ldots,m_k)=m_1m_2 \ldots m_k$ since the moduli are pairwise relatively prime. Notice what happens when we look at it modulo $m_1$; the first term becomes $a_1(1)$ and the rest of the terms become $0$ because $M_i \equiv 0 \pmod {m_j}$ when $i \not= j$ (look at how $M_i$ is defined if you don't understand). So we're left with $x \equiv a_1 \pmod{m_1}$. The same type of thing happens for all $m_i$, $1\leq i \leq k$.

Let's do an example. Suppose we want to find the solution to $x \equiv 1 \pmod{3}$, $x \equiv 2 \pmod{5}$, and $x \equiv 3 \pmod{7}$. Then $M=3*5*7=105$, $M_1=35$, $M_2=21$, and $M_3=15$. Now we need to find the solutions $y_i$ to $M_iy_i \equiv 1 \pmod{m_i}$ and we're practically done!. For $M_1$ we have $y_1=2$, for $M_2$ we have $y_2=1$, and for $M_3$ we have $y_3=1$. So our solution is
$x=(1)(35)(2)+(2)(21)(1)+(3)(15)(1)=157$. All solutions differ by $3*5*7=105$ so the smallest positive solution is $157-105=52$.

wow thanks guys!  Today, I forced my math coach to do the problem and he turned up with 2 solutions, using drunner's method with the a's m's and y's, as well as the equation solution used like x = 3 mod 5 , or 5y + 3 = x.

I understand it all now, so thank you!

You have a math coach during the summer? Are you at some camp?

lol I'm in "Math Camp" the summer school class.  It's pretty fun, but for the last 2 days we've been drilled over just plain mod stuff, nothing futher than that really.  I've learned plenty though :)


Σε αυτό το topic θα προσπαθήσω να μαζέψω λίγα θεωρήματα απο την θεωρία γραφημάτων. Αρχικά οι ασκήσεις που θα βάζω θα είναι άμεσες εφαρμογές ορισμένων θεωρημάτων. Θα βάζω όμως τις ασκήσεις προτού γράψω τα θεωρήματα, με την ελπίδα ότι θα τα ανακαλύψουμε. Αν λοιπόν γνωρίζετε το θεώρημα που κάνει κάποια άσκηση τετριμμένη, περιμένετε λίγες μέρες προτού απαντήσετε. Αν όχι τότε γράψτε την λύση σας. Αργότερα ίσως συζητήσουμε και πιο δύσκολες ασκήσεις.

[b]Πρόβλημα 1:[/b] Σε μια χώρα υπάρχουν 100 πόλεις με αεροδρόμια. Δεν συνδέονται όμως όλα μεταξύ τους με απευθείας πτήσεις. Αν δυο αεροδρόμια συνδέονται με απευθείας πτήσεις, τότε συνδέονται έτσι και προς τις δύο κατευθήνσεις. Ο Ανδρέας παρατηρεί ότι αν ξεκινήσει από οποιαδήποτε πόλη, για να ξαναεπιστρέψει σε αυτήν  πρέπει να κάνει άρτιο αριθμό πτήσεων. Να δειχθεί ότι όλες ο πόλεις μπορούν να χωριστούν σε δύο ομάδες Α και Β ώστε δεν υπάρχουν απευθείας πτήσεις μεταξύ δύο πόλεων στην ομάδα Α ούτε και απευθείας πτήσεις μεταξύ δύο πόλεων στην ομάδα Β.

Είχα ξεχάσει τελείως πως έβαλα αυτήν την άσκηση. Ελπίζω ο λόγος που δεν απαντήσατε είναι διότι ήδη γνωρίζατε την απάντηση.  :)

Η άσκηση οδηγούσε στο ακόλουθο θεώρημα:

[b]Θεώρημα 1:[/b] Ένα γράφημα είναι διμερές αν και μόνο αν δεν περιέχει κανένα περιττό κύκλο.

Όπου: Ένα γράφημα ονομάζεται [i]διμερές[/i] (bipartite) αν οι κορυφές του μπορούν να χωριστούν σε δύο υποσύνολα Α και Β ούτως ώστε να μην υπάρχεί καμία πλευρά μεταξύ κορυφών του Α και κορυφών του Β. Ένας [i]κύκλος[/i] C σε ένα γράφημα G είναι μια ακολουθία $ v_1,e_1,v_2,e_2,\ldots,v_k,e_k,v_{k\plus{}1}$, όπου τα $ v_1,\ldots,v_k$ είναι ξεχωριστές κορυφές του G, $ v_{k\plus{}1} \equal{} v_1$ και κάθε $ e_i$ είναι πλευρά του G μεταξύ των $ v_i$ και $ v_{i\plus{}1}$. Ο κύκλος ονομάζεται [i]περιττός[/i] ή [i]άρτιος[/i] ανάλογα με το αν το $ k$ είναι περιττός ή άρτιος.

Ας βάλει κάποιος μια απόδειξη για να πάμε στην επόμενη άσκηση/θεώρημα.


Here's mine:

1) Tupac: Hail Mary
2) Notorious B.I.G.: Big Poppa
3) Eminem: The Way I Am
4) Puff Daddy: I'll Be Missing You
5) Outkast: Ms. Jackson

Yeah, I'm really one dimensional: I just like old skool rap  :coolspeak:  :gleam:

billie jean, dirty diana, smooth criminal, with arm wide open, maria maria, one last breath, and many more i can't remember

Stairway to Heaven
Paradise City
The Wall
Hotel California
Thunderstruck

i hope you know who all of those are by and yeah im really quite one dimensional too just in a completely different area

in no particular order:
1. renegades of funk - rage against the machine
2. heresy - nine inch nails
3. kashmir - led zeppelin
4. iron man - black sabbath
5. dirty deeds done dirt cheap - AC/DC

1. untitled gabber song - emotional joystick :P
2. hate it or love it - the game ft. 50 cent
3. Numb/encore - Jay-Z & Linkin Park
4. Evolution - Ayumi Hamasaki
5. Dokudenpa - Sharpnelsound

1.  Silly Love Songs (Paul McCartney)
2.  Foreplay/Long Time (Boston)
3.  Waiting for a Girl Like You (Foreigner)
4.  Captain Jack (Billy Joel)
5.  Stairway to Heaven (Led Zepplin)

There are some rap/etc songs that I like, but they fall just short of my top 5 list.

i like so many songs...i can't decide my top five! :)


If $x, y$ and $2x + \frac{y}{2}$ are not zero, then
\[ \left( 2x + \frac{y}{2} \right)\left[(2x)^{-1} + \left( \frac{y}{2} \right)^{-1} \right] \]
equals

$\textbf{(A) }1\qquad\textbf{(B) }xy^{-1}\qquad\textbf{(C) }x^{-1}y\qquad\textbf{(D) }(xy)^{-1}\qquad \textbf{(E) }\text{none of these}$

Are you sure this is in the right place?  :huh:

I'm getting $\frac{(4x+y)^2}{4xy}$.

[quote="math92"]I think this is a little hard for basics... :?
anyways my answer is: [hide]E.  I keep getting $x^2(8y+16x+y)$[/hide][/quote]

Do you have an $y^2$ in there?...

[quote="MCrawford"]If $x, y$ and $2x + \frac{y}{2}$ are not zero, then
\[ \left( 2x + \frac{y}{2} \right)\left[(2x)^{-1} + \left( \frac{y}{2} \right)^{-1} \right]  \]
equals
(A)	1
(B)	$xy^{-1}$
(C)	$x^{-1}y$
(D)	$(xy)^{-1}$
(E)	none of these[/quote]

[hide]$\left( 2x + \frac{y}{2} \right)\left[(2x)^{-1} + \left( \frac{y}{2} \right)^{-1} \right]$

$\frac{4x+y}{2}*\left(\frac{1}{2x}+\frac{2}{y}\right)$

$\frac{4x+y}{2}*\frac{y+4x}{2xy}$

$\frac{(4x+y)^2}{4xy}$

$\frac{16x^2+8xy+y^2}{4xy}$

$\frac{4x}{y}+\frac{2}{1}+\frac{y}{4x}$

That's the farthest I can go. So I'm guessing it's E.[/hide]


calculus
integration
derivative
trigonometry
limit
complex analysis

I was looking at the following contour integrals and can not come up with a right answer:

$ \oint_{C} \frac {sin(z)}{z^4} dz$ where C is the unit circle

Is this the way to solve this integral?
Using Cauchy's Integral formula with a $ z_0 = 0$, is this derived through the fact that the third derivative of $ \oint_{C} \frac {1}{z} dz$ = $ 2i\pi$ = ${ \frac {3!}{2i\pi}} \oint_{C} \frac { - 1}{z^4} dz$ so then $ \oint_{C} \frac {sin(z)}{z^4} dz = \frac { - 2i\pi}{3!}I(C,0)f'(z_0) = \frac { - i\pi}{3}cos(0) = \frac { - i\pi}{3}$? where $ I(C,0)$ is the index or how many times the curve C winds around $ z_0$.

What about this one:
$ \oint_{C} \frac {sin(e^z)}{z} dz$ where C is the unit circle
I evaluated this as if $ z_0 = 0$ then the integral is equal to  $ 2i\pi*I(C,0)f'(z_0)$ with $ f'(0) = \cos(e^0)e^0$ so the integral is equal to $ 2i\pi\cos(1)$ according to my calculations but parametrizing the integral and putting it into Maple using numerical approximation I get $ \int _{0}^{2\,\pi }\!i\sin \left( {{\rm e}^{{{\rm e}^{it}}}} \right) dt \approx 5.287118128i$. How is this contour integral solved?

Thanks for your help.

Anybody know? The main problem I have is with the 2nd one, I can grasp the concepts on the 1st integral. These integrals are confusing and so is the Cauchy's theorem to me. Anybody know how to apply it to the $ \oint_{C} \frac {sin(e^z)}{z} dz$ contour integral? Thanks.

$ \int _{0}^{2\,\pi }\!i\sin \left( {{\rm e}^{{{\rm e}^{it}}}} \right) dt \approx 5.287118128i$

have you tried with Matlab?  :lol: , it is weird for me also

Do as the Cauchy theorem states, the integral is equal to $ 2\pi i$ times the residue(s) inside the contour.

The residue of the integrand at zero is $ \lim_{z\to0} (z\minus{}0)\frac{\sin(e^z)}{z}\equal{}\sin(1)$.

So your integral is equal to $ 2\pi i \cdot \sin(1)$.

Try to recall how to calculate residues if you get stuck on tasks like this.


inequalities
function
inequalities unsolved

Let $a_k>0$, $k=1,2,3,...$. And it is known that for $n=1,2,3,...$ we have
\[\sum_{k=1}^{n}{a_k} \geq 2\sqrt{n}.\]
Prove for all $n \in \mathbb{N}$ the inequality
\[\sum_{k=1}^{n}{a_k^2} \geq \sum_{k=1}^{n}{\frac{1}{k}}.\]

I agree hard but this is famous Hardy inequality:
I think you meant $\sum_{1}^{k} a_{i}\geq 2\sqrt{k}$ so
$4(\sum_{k=1}^{n}{\frac{1}{k}})\leq a_1^2+(\frac {a_1+a_2}{2})^2+...+(\frac {a_1+a_2+...+a_n}{n})^2\leq 4(a_1^2+a_2^2+...+a_n^2)$

Link: http://www.mathlinks.ro/Forum/viewtopic.php?p=135847#135847

Yes, you are right.

Some time ago I had been solving the problem for several days without any result. Therefore I called it hard.

Here is another solution (without using any advanced inequalities) that I know.

Since
$\frac{1}{k}=\frac{4}{(\sqrt{k}+\sqrt{k})^2}<\frac{4}{(\sqrt{k}+\sqrt{k-1})^2}=4(\sqrt{k}-\sqrt{k-1})^2,$
then
$\sum_{k=1}^{n}{a_k^2}-\sum_{k=1}^{n}{\frac{1}{k}}=\sum_{k=1}^{n}{(a_k^2-\frac{1}{k})}>\sum_{k=1}^{n}{(a_k^2-4(\sqrt{k}-\sqrt{k-1})^2)}=\sum_{k=1}^{n}{(a_k-2(\sqrt{k}-\sqrt{k-1}))(a_k+2(\sqrt{k}-\sqrt{k-1}))}=\sum_{k=1}^{n}{c_k(c_k+4(\sqrt{k}-\sqrt{k-1}))}=\sum_{k=1}^{n}{c_k^2}+4\sum_{k=1}^{n}{(\sqrt{k}-\sqrt{k-1})c_k} \geq 4\sum_{k=1}^{n}{(\sqrt{k}-\sqrt{k-1})c_k},$
where $c_k=a_k-2(\sqrt{k}-\sqrt{k-1})$, $k=1,\ldots,n$.

Hence it is sufficient to prove the inequality $\sum_{k=1}^{n}{(\sqrt{k}-\sqrt{k-1})c_k} \geq 0$.

Assume $s_k=\sum_{i=1}^{k}{c_i}$ for $k=1,\ldots,n$. Then we will have
$\sum_{k=1}^{n}{(\sqrt{k}-\sqrt{k-1})c_k}=c_1+\sum_{k=2}^{n}{((\sqrt{k}-\sqrt{k-1})s_k-(\sqrt{k-1}-\sqrt{k-2})s_{k-1}+(2\sqrt{k-1}-\sqrt{k}-\sqrt{k-2})s_{k-1})}=c_1+(\sqrt{n}-\sqrt{n-1})s_n-c_1+\sum_{k=2}^{n}{(2\sqrt{k-1}-\sqrt{k}-\sqrt{k-2})s_{k-1}}.$

Observe that
$s_k=\sum_{i=1}^{k}{c_i}=\sum_{i=1}^{k}{(a_i-2(\sqrt{i}-\sqrt{i-1}))} \geq 2\sqrt{k}-2\sqrt{k}=0$
for $k=1,\ldots,n$.

Also it is easy to see that $2\sqrt{k-1}-\sqrt{k}-\sqrt{k-2} \geq 0$ for $k \geq 2$ (since the function $y=\sqrt{x}$ is convex upwards).

The last two observations complete the proof.

Very similar technique was used by prowler in his recent post.


Let $ f(n)$ ($ n$ positive integer) be the minimum $ i$ such
$ 1-\frac{1}{n}$ equals the sum of $ i$ reciprocals of positive integers.

a) Prove that $ f(p) \le p-1$, p prime, is it equal?

b) Prove that $ f(p^{n}) \le (p-1)n$, p prime, is it equal?

c) Prove that $ f(2007) \le 223+3$, is it equal?

Nice,aviateurpilot  :lol: . This is problem similary http://www.mathlinks.ro/Forum/viewtopic.php?t=156549 . I solved 1) and 2) .

Thanks for your solution and sorry for the duplicate, I was not sure where to put this problem.

Here comes a better boundary to $ f(2007)$

c2) Prove that $ f(2007) \le 12$


geometry
circumcircle
Euler
ratio
geometric transformation
homothety
incenter

Given triangle $ ABC$ with incircle $ (I)$, circumcircle $ (O). (I)$ touches $ BC, AC, AB$ at $ A', B', C'$. Prove that the radical center $ L$ of $ (A, AA'), (B, BB'), (C, CC')$ lies on the line $ OI$. Moreover, if $ B'C'$ cuts $ (O)$ at $ A_1, A_2$, similar for $ B_1, B_2, C_1, C_2$ then $ L$ is the radical center of $ (A'A_1A_2), (B'B_1B_2)$ and $ (C'C_1C_2)$

Let $ L$ be the orthocenter of the intouch triangle $ \triangle A'B'C'$ lying on its Euler line $ IO.$ $ H$ is the foot of the perpendicular from $ A'$ to $ B'C'$ and $ S$ is the intersection of $ A'H$ with the external bisector of $ \angle BAC.$ Let $ \mathcal{P}_a$ denote the power of $ L$ WRT $ (A,AA').$ Then we have $ \mathcal{P}_a \equal{} (AA')^2 \minus{} AL^2,$ but since $ AS \perp SA'$ $ \Longrightarrow$ $\mathcal{P}_a \equal{} (SA')^2 \minus{} LS^2$

$ \mathcal{P}_a \equal{} (LS \plus{} LA')^2 \minus{} LS^2 \equal{} (LA')^2 \plus{} 2LS \cdot LA'$

$ \mathcal{P}_a \equal{} (LA')^2 \plus{} 2LA'(SH \plus{} LH) \equal{} (LA')^2 \plus{} 2LA' \cdot SH \plus{} 2LA' \cdot LH$

Denote $ J \equiv AI \cap B'C'.$ We have then

$ \mathcal{P}_a \equal{} (2IJ)^2 \plus{} 4IJ \cdot SH \plus{} 2LA' \cdot LH \equal{} 4IJ(IJ \plus{} SH) \plus{} 2LA' \cdot LH$

$\mathcal{P}_a=4IJ \cdot IA \plus{} 2LA' \cdot LH \equal{} 4r^2 \plus{} 2LA' \cdot LH$

$ LA' \cdot LH$ equals the power of the inversion with center $ L$ taking $ (I)$ into the nine-point circle of $ \triangle A'B'C'.$ Hence, $ \mathcal{P}_a$ is symmetric in terms of $ a,b,c$ $ \Longrightarrow L$ has equal power WRT the circles $ (A,AA'),(B,BB'),(C,CC').$ $\blacksquare$

Let $ D \equiv B'C' \cap BC$ and $M_a$ be the midpoint of $BC.$ From the harmonic cross ratio $ (B,C,A',D),$ it follows that $ DB \cdot DC \equal{} DM_a \cdot DA',$ but $ D$ has equal power WRT $ (O)$ and $ \odot(A'A_1A_2)$ $\Longrightarrow$ $ DB \cdot DC \equal{} DA_1 \cdot DA_2$ $ \Longrightarrow$ $ DA_1 \cdot DA_2 \equal{} DM_a \cdot DA$ $\Longrightarrow$ $ M_a \in \odot(A'A_1A_2)$. Analogously $ M_b,M_c$ lie on $ \odot(B'B_1B_2),\odot(C'C_1C_2),$ respectively. Center $ O_a$ of $ \odot(A'A_1A_2)$ is the intersection of the perpendicular bisector of $ M_aA'$ with the perpendicular to $ A_1A_2$ through $ O.$ In other words, if $ A''$ is the intersection of $ IA'$ with the perpendicular to $ A_1A_2$ from $ O,$ then $ O_a$ is the midpoint of $ OA''.$ Similarly, $ O_b,O_c$ are midpoints of $ OB'',OC''.$ Note that $ \triangle OA''B''$ and $ \triangle LA'B'$ are homothetic with homothety center $ I,$ since $ OA'' \parallel LA' , OB'' \parallel LB'$ and $ OL,A'A'',B'B''$ concur at $ I.$ Thereby, $ A''B'' \parallel A'B' \parallel O_aO_b.$ Hence, radical axis $ \mathcal{L}_c$ of $ (O_a),(O_b)$ goes through $ C',$ due to $ C'A_1 \cdot C'A_2 \equal{} C'B_1 \cdot C'B_2$ and it is orthogonal to $ O_aO_b \parallel A'B'$ $\Longrightarrow$ $ \mathcal{L}_c$ is identical with the C'-altitude of $ \triangle A'B'C'.$ Analogously, $ \mathcal{L}_a,\mathcal{L}_b$ are identical with the A'- and B'- altitudes of $\triangle A'B'C'$ $ \Longrightarrow$ $ L$  is the radical center of $ (O_a),(O_b),(O_c).$ $\blacksquare$

Dear [b]Luis[/b],
Thanks you very much for your nice solution! I have learned so much from you  :idea:
The orthocenter of triangle $ A'B'C'$ is the radical center of three circles $ (A'A_1A_2), (B'B_1B_2), (C'C_1C_2)$ was mentioned in a nice problem which was proposed by [b]Cosmin Pohoata[/b] and [b]Darij Grinberg[/b].
My solution is base on this lemma: "Given triangle $ ABC$ and circumcenter $ O$, incenter $ I. M$ is inside triangle $ ABC. MA'\perp BC, MB'\perp AC, MC'\perp AB$ then $ M$ lies on $ OI$ iff $ AC' \plus{} BA' \plus{} CB' \equal{} p$"  :)

Here is my solution for this problem
[b]Solution[/b]

Let $H$ be orthocenter of $\triangle$ $A'B'C'$; the lines through $A'$, $B'$, $C'$ and parallel with $B'C'$, $C'A'$, $A'B'$ intersec ($I$) at second points $D$, $E$, $F$; $M$ $\equiv$ $B'E$ $\cap$ $C'F$, $N$ $\equiv$ $C'F$ $\cap$ $A'D$, $P$ $\equiv$ $A'D$ $\cap$ $B'F$
It's easy to see that: $D$ $\in$ ($A$; $AA'$), $E$ $\in$ ($B$; $BB'$), $F$ $\in$ ($C$; $CC'$), $H$ is circumcenter of $\triangle$ $MNP$ and $H$ $\in$ $IO$
We have: $B'E$, $C'F$ are radical axises of (($B$; $BB'$), ($I$)); (($I$), ($C$; $CC'$)), so $M$ is radical center of ($I$), ($B$; $BB'$), ($C$; $CC'$), then $M$ lie on radical axis of ($B$; $BB'$) and ($C$; $CC'$)
But: $MH$ $\parallel$ $IA'$ and $IA'$ $\perp$ $BC$ so $MH$ $\perp$ $BC$
Hence: $MH$ is radical axis of ($B$; $BB'$) and ($C$; $CC'$)
Similarly: $NH$, $PH$ are radical axises of (($C$; $CC'$), ($A$, $AA'$)) and (($A$, $AA'$), ($B$; $BB'$))
Therefore: $H$ is radical center of ($A$, $AA'$), ($B$; $BB'$) and ($C$; $CC'$)

Here is the rest part of my solution for this problem
[b]Solution[/b]

Let $X$, $Y$, $Z$, $J$ be the midpoints of $\stackrel\frown{BAC}$, $\stackrel\frown{ABC}$, $\stackrel\frown{ACB}$ and $\stackrel\frown{BC}$ which not contain $A$; $X'$, $Y'$, $Z'$, $S$ be the midpoints of $IX$, $IY$, $IZ$, $BC$; $G$ $\equiv$ $EF$ $\cap$ $BC$
We have: ($BCA'G$) = $-$ 1 so $\overline{GA'}$ . $\overline{GS}$ = $\overline{GB}$ . $\overline{GC}$ = $\overline{GA_1}$ . $\overline{GA_2}$ or $S$ $\in$ ($A'A_1A_2$)
But: $O$, $X'$ are midpoints of $XJ$, $IX$, respectively, then $OX'$ $\parallel$ $IJ$, so $OX'$ $\perp$ $A_1A_2$
It's easy to see that $X'$ line on perpendicular bisector of $A'S$, combine with $A'$, $S$, $A_1$, $A_2$ lie on a circle, hence $X'$ is center of ($A'A_1A_2$)
Similarly: $Y'$, $Z'$ are centers of ($B'B_1B_2$), ($C'C_1C_2$), respectively
But: $Y'Z'$ $\parallel$ $YZ$ $\parallel$ $B'C'$, $A'H$ $\perp$ $B'C'$ so $A'H$ $\perp$ $Y'Z'$
We also have: $\overline{A'B_1}$ . $\overline{A'B_2}$ = $\overline{A'C_1}$ . $\overline{A'C_2}$, then $A'H$ is radical axis of ($B'B_1B_2$) and ($C'C_1C_2$)
Similarly: $B'H$, $C'H$ are radical axises of (($C'C_1C_2$), ($A'A_1A_2$)), (($A'A_1A_2$), ($B'B_1B_2$))
Therefore: $H$ is radical center of ($A'A_1A_2$), ($B'B_1B_2$) and ($C'C_1C_2$)


trigonometry
algebra
polynomial
algebra proposed

Let $a_0 \in R$ and $a_{n+1}=(a_n)^3 + sin(n)$ for all $n\geq 1$.
Prove that for every $k \in N$ we can choose $a_0$ such that $a_k = 2005$.

cam'on, it's not that hard, I can also say that it is easy!

noone interested ?  :?

Ok, I write solution to this one, you write solution to the problem with prime numbers. Is it ok? My solution: it is clear that each term of the sequence is a polynomial of degree a power of $3$ in the first term. Conclusion follows since polynomials with odd degree have real roots. Now, your turn. ;)

ok, you win!  ;)

(But in your solution you also have to mention some useless terms which involve the sine... but i'm satisfied anyway  :)  )