induction
probability
IMO 2009
IMO
algebra
IMO Shortlist
combinatorics

Let $ a_1, a_2, \ldots , a_n$ be distinct positive integers and let $ M$ be a set of $ n \minus{} 1$ positive integers not containing $ s \equal{} a_1 \plus{} a_2 \plus{} \ldots \plus{} a_n.$ A grasshopper is to jump along the real axis, starting at the point $ 0$ and making $ n$ jumps to the right with lengths $ a_1, a_2, \ldots , a_n$ in some order. Prove that the order can be chosen in such a way that the grasshopper never lands on any point in $ M.$

[i]Proposed by Dmitry Khramtsov, Russia[/i]

Well, as far as I know, many strong contestants did not solve it (maybe no italian, british, romanian, french...one german...) thus I guess the answer may be affirmative. :wink:

Pierre.

lol... looks like #3 and #6 are of similar flavor this year...

For this problem, can't you just

[hide]induct? Let $ a_n$ be largest, and consider the largest element $ m$ of $ M$. In the case that $ s \minus{} a_n$ is in $ M$ and $ m > s \minus{} a_n$, note that for some $ 1 \le i \le n\minus{}1$, we have that $ s \minus{} a_i$ and $ s \minus{} a_i \minus{} a_n$ are both not in $ M$. Thus, apply the inductive hypothesis to the $ a_i$ excluding $ a_i$ and $ a_n$, and we are able to dodge the elements of $ M$, since at most $ n\minus{}3$ elements of $ M$ are strictly between $ 0$ and $ s \minus{} a_i \minus{} a_n$.

Otherwise, apply the inductive hypothesis to $ a_1$ through $ a_{n\minus{}1}$ on the set $ M \minus{} \{ m \}$, so that we make $ n\minus{}1$ hops. If $ m$ is not reached after any of these hops, we can simply tag on a hop of length $ a_n$ at the end of the sequence. If $ m$ is reached after the $ k$th hop, then we revise the $ k$th hop to be of length $ a_n$ and move what was originally the $ k$th hop to the end.

Seems a bit simple (although not totally trivial), so I might have missed something...[/hide]

I'm not sure if I understand this part of your argument:
[quote="probability1.01"]

[hide]Otherwise, apply the inductive hypothesis to $ a_1$ through $ a_{n \minus{} 1}$ on the set $ M \minus{} \{ m \}$, so that we make $ n \minus{} 1$ hops. If $ m$ is not reached after any of these hops, we can simply tag on a hop of length $ a_n$ at the end of the sequence. If $ m$ is reached after the $ k$th hop, then we revise the $ k$th hop to be of length $ a_n$ and move what was originally the $ k$th hop to the end.[/hide][/quote]

Okay, so I have a sequence that doesn't reach $ M \minus{} \{m\}$.  But when I change one of  the middle hops to be of length $ a_n$, why should I expect the sequence to keep that property?

(EDIT: Ah, I missed that $ m$ was largest, as kdano pointed out.)

[quote="probability1.01"]lol... looks like #3 and #6 are of similar flavor this year...

For this problem, can't you just

[hide]induct? Let $ a_n$ be largest, and consider the largest element $ m$ of $ M$. In the case that $ s \minus{} a_n$ is in $ M$ and $ m > s \minus{} a_n$, note that for some $ 1 \le i \le n \minus{} 1$, we have that $ s \minus{} a_i$ and $ s \minus{} a_i \minus{} a_n$ are both not in $ M$. Thus, apply the inductive hypothesis to the $ a_i$ excluding $ a_i$ and $ a_n$, and we are able to dodge the elements of $ M$, since at most $ n \minus{} 3$ elements of $ M$ are strictly between $ 0$ and $ s \minus{} a_i \minus{} a_n$.

Otherwise, apply the inductive hypothesis to $ a_1$ through $ a_{n \minus{} 1}$ on the set $ M \minus{} \{ m \}$, so that we make $ n \minus{} 1$ hops. If $ m$ is not reached after any of these hops, we can simply tag on a hop of length $ a_n$ at the end of the sequence. If $ m$ is reached after the $ k$th hop, then we revise the $ k$th hop to be of length $ a_n$ and move what was originally the $ k$th hop to the end.

Seems a bit simple (although not totally trivial), so I might have missed something...[/hide][/quote]

I was just about to type my solution that's basically the same, and i couldn't find a bug in it either.

[quote="probability1.01"]For this problem, can't you just

[hide]induct? Let $ a_n$ be largest, and consider the largest element $ m$ of $ M$. In the case that $ s \minus{} a_n$ is in $ M$ and $ m > s \minus{} a_n$, note that for some $ 1 \le i \le n \minus{} 1$, we have that $ s \minus{} a_i$ and $ s \minus{} a_i \minus{} a_n$ are both not in $ M$. Thus, apply the inductive hypothesis to the $ a_i$ excluding $ a_i$ and $ a_n$, and we are able to dodge the elements of $ M$, since at most $ n \minus{} 3$ elements of $ M$ are strictly between $ 0$ and $ s \minus{} a_i \minus{} a_n$.

Otherwise, apply the inductive hypothesis to $ a_1$ through $ a_{n \minus{} 1}$ on the set $ M \minus{} \{ m \}$, so that we make $ n \minus{} 1$ hops. If $ m$ is not reached after any of these hops, we can simply tag on a hop of length $ a_n$ at the end of the sequence. If $ m$ is reached after the $ k$th hop, then we revise the $ k$th hop to be of length $ a_n$ and move what was originally the $ k$th hop to the end.

Seems a bit simple (although not totally trivial), so I might have missed something...[/hide][/quote]

It seems like you can, if you missed something, so did I when reading your solution.  Actually, I was trying along a similar line as you, but got stuck
[hide]
in the second case because I "forgot" to consider $ a_n$ as the largest, which makes the induction step work nicely in case you bump into $ m$ along the way...   :blush:  I found the first case relatively simple though...
[/hide]

I would like to know whether the shortlist contained any problems harder than #3 and #6, I guess I will have to wait for one year...  In last year's shortlist, after looking through it, I consider problems A6 and C6 harder than the actual problems #3 and #6 from last year.  I also think that A6 was quite original for a functional equation, and C6 a very beautiful problem, probably the most beautiful in the entire shortlist (working on it, haven't still got much).  Anyway, I was surprised after seeing them in the shortlist that neither got selected for the contest...   :?:

[quote="kevinatcausa"]I'm not sure if I understand this part of your argument:

Okay, so I have a sequence that doesn't reach $ M \minus{} \{m\}$.  But when I change one of  the middle hops to be of length $ a_n$, why should I expect the sequence to keep that property?[/quote]

No, you change the second last hop to $ a_n$, thus increasing it (not touching $ m$ but a greater number). The hops until that don't change, and since $ m$ is the greatest of $ M$, it doesn't touch any number in $ M$.

[quote="kdano"]
I was just about to type my solution that's basically the same, and i couldn't find a bug in it either.[/quote]

that is really weird, I've done essentially the same stuff, but can not find any mistake in it either...

[quote="probability1.01"]lol... looks like #3 and #6 are of similar flavor this year...

For this problem, can't you just

[hide]induct? Let $ a_n$ be largest, and consider the largest element $ m$ of $ M$. In the case that $ s \minus{} a_n$ is in $ M$ and $ m > s \minus{} a_n$, note that for some $ 1 \le i \le n \minus{} 1$, we have that $ s \minus{} a_i$ and $ s \minus{} a_i \minus{} a_n$ are both not in $ M$. Thus, apply the inductive hypothesis to the $ a_i$ excluding $ a_i$ and $ a_n$, and we are able to dodge the elements of $ M$, since at most $ n \minus{} 3$ elements of $ M$ are strictly between $ 0$ and $ s \minus{} a_i \minus{} a_n$.

Otherwise, apply the inductive hypothesis to $ a_1$ through $ a_{n \minus{} 1}$ on the set $ M \minus{} \{ m \}$, so that we make $ n \minus{} 1$ hops. If $ m$ is not reached after any of these hops, we can simply tag on a hop of length $ a_n$ at the end of the sequence. If $ m$ is reached after the $ k$th hop, then we revise the $ k$th hop to be of length $ a_n$ and move what was originally the $ k$th hop to the end.

Seems a bit simple (although not totally trivial), so I might have missed something...[/hide][/quote]

I also tried induction,but I havent finished it yet.

[hide="Kind of easy when saw what probability has done"]

Induction on n. Let it be true for k, now we prove it's true for k+1. We add $ m_k$, such that it's the largest of all m-s (if it isn't, then take all without greatest and add greatest to them in inductive step, as we assumed for all k number it's true). If it hits any point on which grasshoper lands, then just change that last jump before hitting $ m_k$ to some bigger jump... That's the whole problem...

Comments: I wouldn't probably do it without seeing the idea the probability did, but with it it's almost trivial...
[/hide]

[quote="pbornsztein"][quote="huang"]Did they really consider this hard enough for a problem 6??[/quote]

As the coordinations take place, it turns to be the most difficult problem of the IMO for the last 50 years in terms of full solutions (maybe only 2, surely less than 5), and in terms of nonzero scores (probably less than 10 contestants will receive a nonzero score).
So, please stop with all these complaining about the level of difficulties of the IMO problems (each problem and each year), it becomes ridiculous.

Pierre.[/quote]

Sir, who were the two solved this problem?  Could you please also check on the sketch posted by [b]probability 1.01[/b].

[quote="pbornsztein"][quote="huang"]Did they really consider this hard enough for a problem 6??[/quote]

As the coordinations take place, it turns to be the most difficult problem of the IMO for the last 50 years in terms of full solutions (maybe only 2, surely less than 5), and in terms of nonzero scores (probably less than 10 contestants will receive a nonzero score).
So, please stop with all these complaining about the level of difficulties of the IMO problems (each problem and each year), it becomes ridiculous.

Pierre.[/quote]

Well the idea of induction with carefully chosen numbers was really hard, but I wanted to pointed out that the problem was not hard in technique of solving the problem.

That means absolutely nothing. 2007/3 certainly didn't require anything fancy.

[quote="Bugi"]
Well the idea of induction with carefully chosen numbers was really hard, but I wanted to pointed out that the problem was not hard in technique of solving the problem.[/quote]

I might be overtrained in combinatorics, but I disagree with you. Induction was my second idea for this problem (after some Menger-related stuff, of which i had no knowledge last year, when i was in highschool). Of course one has to work with it to induct appropriately, but one gets promising results while trying to do so.
I always wondered how hard people find combinatorics problems.. like i found 2008/5 to be the easiest of all 2008's questions, and what i did for 2007/3 seemed pretty straightforward to me (so straightforward, that i didn't notice that the only cases left don't exist :P).. :huh:

[REDACTED] Needs some checking I am trying to improve my older solutions, so wil update soon.

WLOG let $a_1 < a_2 < a_3\ldots <a_n$ and let $A = \{a_1, a_2, \ldots a_n\}$, and for all $i \in [1, n-1]$, we have $m_i \in M$ and WLOG $m_1 < m_2 < m_3 \ldots < m_{n-1}$. We prove by induction with the base case of $n = 2$ being trivial. For the inductive step, notice by the Pigeonhole Principle that there exists an integer $i$ such that $s-a_i \not\in M$. We have a few cases.

[color=#3D85C6][b]Case 1: [/b][/color]$m_{n-1} \le s-a_n$.

By the inductive hypothesis on $A \setminus \{a_n\}$ and $M \setminus \{m_{n-1}\}$, there exists some way the grasshopper can jump that avoids all the points in $M \setminus \{m_{n-1}\}$, but with the possibility of it landing on $m_{n-1}$. Notice that if it does, we can replace the jump that lands the grasshopper on $m_{n-1}$ with a jump of $a_n$, which successfully brings the grasshopper to a point $p > m_{n-1}$ and have it avoid all points in $M$.

[color=#3D85C6][b]Case 2: [/b][/color]$m_{n-1} > s-a_n$.

If there exists a positive integer $i$ such that $s-a_i \not\in M$ and $s-a_i < m_{n-1}$, then we let $k$ be the index such that $m_k < s-a_i \le m_{k+1}$. We can just apply the inductive hypothesis to $A \setminus \{a_i\}$ and $M \setminus m_k$, and then let the grasshopper jump $a_i$ to reach $s$ where it never touches a point in $M$. Therefore, assume otherwise.

We know there must exist an $i$ such that $s-a_i \not\in M$, and let this be maximal. We must have $N = \{s-a_{i+1}, s-a_{i+2}, \ldots s-a_n\} \subseteq M$, where $\#(N) \ge 2$. Therefore, because there must exist some $s-a_n-a_j \not\in M$ for $1 \le j \le i$ by the Pigeonhole Principle, we can use our inductive hypothesis on $A \setminus \{a_j, a_n\}$ and $M \setminus N$ to get the grasshopper to a point $p$ where $p < s-a_n$ and $p+a_n>s-a_{i+1}$, which we then can make it jump $a_n$ and then $a_j$ to reach $s$ without touching a point in $M$.

Therefore, the inductive step is proven and we are done. $\blacksquare$

[color=#f00][b]Remarks: [/b][/color]I agree with people above that this problem has an easy solution (as I can do it lol), yet is one of the hardest IMO problems to date. Right after reading I instantly thought about induction and because I have unlimited time, I just tried it until I figured out that it worked. However this is a luxury that test-takers do not have and also with it being an "intimidating IMO #6" is probably the reason of its incredibly low solve rate.

[quote=jeteagle][quote=abvk1718]I am confused here, does all elements of M are less than S?[/quote]

You can assume this if it helps your proof because clearly if an element is greater than $s$ then the grasshopper won't be able to jump on it.[/quote]

Got it  :coolspeak:

We use the method of mathematical induction. Let our jump sizes be $a_1, a_2, \dots a_n$ and the forbidden points be $p_1, p_2, \dots, p_{n - 1}$. Assume $a_1 < a_2 < \dots a_n$ and $p_1 < p_2 \dots < p_n$. There are several cases:

[b]Case 1: [/b] $a_1 + a_2 + \dots + a_{n - 1} < p_{n - 1}.$
In this case, we can find some permutation of $a_{1}, a_2, \dots a_{n -1}$ which avoids $p_1, p_2, \dots p_{n - 2}$. It would also by default avoid $p_{n - 1}$, by our case 1 assumption. Then, we can jump $a_{n}$ to finish.

[b]Case 2: [/b] $a_1 + a_2 + \dots + a_{n - 1} \ge p_{n - 1}.$
In this case, let's also use some permutation of $a_1, a_2, \dots a_{n - 1}$ that avoids $p_1, p_2, \dots p_{n - 2}$. If that ordering also avoids $p_{n -1 }$, we're done, so let's assume that it hits $p_{n - 1}$ at some point. At the point where it hits $p_{n - 1}$, swap $a_i$ with $a_n$. Then, the path will be valid.

Can someone please tell the motivation behind [hide=the soltion][img]https://i.imgur.com/KPw8mBn.png[/img]

[img]https://i.imgur.com/rmiJ92a.png[/img]

[img]https://i.imgur.com/3jwiQcm.png[/img][/hide] in the [url=https://www.imo-official.org/problems/IMO2009SL.pdf]official booklet[/url].

Personally, I was also looking at least $k$ for which $|M \cap (0,T_k]| \ge k$ (as that's sort of a generalization to the case when $M$ contains an element $\le a_1$, which is easy to resolve by induction).
But I was unable to finish from there.

We induct on $n$, with the base case $n=1$ obvious. Set $a_1 < a_2 < \cdots < a_n$. For the inductive step, we split into four cases:

[b]Case 1.[/b] $s-a_n \in M$ is the maximal element of $M$. In this case, by the inductive hypothesis, there exists a sequence of jumps with lengths $a_1, a_2, \cdots, a_{n-1}$ that can avoid the first $n-2$ elements of $M$. Let $a_k$ be the last jump in this sequence. Then, instead of jumping $a_k$ and then $a_n$, we can jump $a_n$ and then $a_k$, which avoids the last mine, so we are done.

[b]Case 2.[/b] $s-a_n \in M$, and there are elements of $M$ greater than $s-a_n$. First, notice that of the $n-1$ values $s-a_k$, $1 \leq k \leq n-1$, one of them must not be in $M$ because $M$ has at most $n-2$ elements in this range. Now, suppose there are $k$ elements of $M$ after $s-a_n$. Then, there are at least $n-k-1$ values $i$ such that $s-a_{n-1-i}$ is not in $M$. Because there are at most $n-k-2$ elements in $M$ before $s-a_n$, there must exist an index $i$ such that $s-a_{n-1-i} - a_n$ is not in $M$. Now, there are at most $n-3$ elements of $M$ left and we have $n-2$ jumps remaining, so it is possible to avoid all these points via a sequence of jumps.

[b]Case 3.[/b] $s-a_n \not \in M$, and there are elements of $M$ greater than $s-a_n$. This case is obvious; simply make a mine-avoiding sequence of jumps to $s-a_n$, then jump $a_n$.

[b]Case 4.[/b] $s-a_n \not \in M$, and all elements of $M$ are strictly less than $s-a_n$. Let $m$ be the maximal element of $M$. There exists a sequence of jumps in $\{a_1, a_2, \cdots, a_{n-1}\}$ that avoids all elements of $M$ except for $m$. If it avoids $m$ as well, it lands on $s-a_n$, and we are done. If it lands on $m$, then on the jump right before it reaches $m$, change the grasshopper's jump length to $a_n$, which guarantees that it lands on a safe square as $m$ is maximal. Next, make the remaining jumps to reach $s$, as needed.

Thus, the induction is complete, and we are done.

Define $m=\max M,$ $A=\left \{ a_1,a_2, \dots ,a_n\right \}$ and WLOG $a_n=\max a_i$.
We induct on $n;$ base case $n\in \left \{ 1,2\right \}$ is trivial. For $n>2$ consider two cases.

[b]Case 1.[/b] $s-a_n\geq m.$
By inductive hypothesis there exist a sequence of jumps by lengths $A\backslash a_n$ which avoid points from $M\backslash m$ - add a jump by $a_n$ at the end. If the jump by $a_i$ leads to point $m,$ we swaps order of jumps by $a_i,a_n$ - clearly this works.

[b]Case 2.[/b] $s-a_n<m.$
If $(s-a_n)\notin M'=M\backslash m,$ construct by hypothesis a sequence of jumps by $A\backslash a_n$ which avoid points from $M',$ adding $a_n$ at the end. Otherwise, by PHP there exist pair of numbers $(s-a_k,s-a_n-a_k)$ not belonging to $M'$ - construct a sequence of jumps by $A\backslash a_k \backslash a_n$ avoiding points of $M'\backslash a_k,$ and adding consequent jumps by $a_n,a_k$ at the end, which works.

Can someone confirm that this is correct? I'm not sure but the problem statement seemed really clear and easy...
    We use induction. Let our jump sizes be $a_1<a_2<\dots<a_n$ and the forbidden points be $f_1<f_2<\dots<f_{n - 1}$. The base case n=1 and n=2 are obvious.
    If $a_1 + a_2 + \dots + a_{n - 1} < p_{n - 1}$, by inductive hypothesis use some ordering of $a_{1}, a_2, \dots a_{n -1}$ which avoids $p_1, p_2, \dots p_{n - 2}$. Then, we can jump $a_{n}$ to finish.
    If $a_1 + a_2 + \dots + a_{n - 1} \ge p_{n - 1}$, use inductive hypothesis again on some ordering of $a_1, a_2, \dots a_{n - 1}$ that avoids $p_1, p_2, \dots p_{n - 2}$; if it also avoids $p_{n -1 }$, we're done, but if it hits $p_{n - 1}$ after jumping $a_k$, we know that $p_{n-1}>p_{n-2},...,p_1$ implies that jumping $a_k$ jumps past the points; in particular, we can move $a_n$ instead of $a_k$ at that move, since it will jump a further distance past all points.

solved with hints

Induct on $n$. This is clearly true for $n=1,2$.

Define a critical point as a point that is the sum of $n-1$ out of the $a_i$. Define a trap as an element of $M$.\\

Consider the smallest critical point, $c$.\\

If there is no trap on $c$ and no trap after $c$, then there are $n$ traps between 0 and $c$. Ignore the last trap before $c$ for now, by induction we can then find a path to $c$ since there are only $n-2$ traps ignoring that one and then we could finish and jump from $c$ to $s$. The only issue is that we might hit the last trap. However, if we do, make the largest possible move in place of the move that stepped on the last trap, which would guarantee skipping it as the largest move is not part of the road to $c$ as $c$ does not contain that term.\\

If there is no trap on $c$ and trap after $c$, we can directly induct to find a path to $c$, as there are at most $n-2$ traps in that area, so we would be done.\\

If there is a trap on $c$ but it is the furthest one along and there are no traps after $c$, take a path that would get you to $c$ except replace the last move with the largest possible move and then finish with whatever move is left.\\

Finally, if there is a trap on $c$ and also a trap past $c$, consider the points that is one "jump" away from $c$, and the corresponding point that is that same jump away from $s$. There are $n-1$ such pairs, but with only $n-2$ traps other than the one at $c$, there must be a pair of these points that are both safe. Since there are at most $n-3$ traps before $c$, we can reach the point that is one jump away from $c$. Then, the last two jumps are used to get the corresponding point by making the largest jump and then finally jumping to the end.

Let's prove this statement by induction on $n$, the number of jumps the grasshopper makes.

Base case: When $n = 2$, there is only one jump with length $a_1$ or $a_2$. Since $M$ contains $n - 1 = 1$ integer and cannot contain $s = a_1 + a_2$, the grasshopper can simply make the jump to the right with the remaining length and avoid landing on the point in $M$.

Inductive step: Assume the statement holds for $n = k$, where $k$ is some positive integer. We'll prove it for $n = k + 1$.

Let the sequence of positive integers be $a_1, a_2, \ldots, a_{k+1}$, and let $M$ be a set of $k$ positive integers not containing $s = a_1 + a_2 + \ldots + a_{k+1}$. Consider $M'$, which is obtained by adding $s$ to each element of $M$, i.e., $M' = {m + s \mid m \in M}$.

By the induction hypothesis, there exists an order in which the grasshopper can jump $k$ times among $a_1, a_2, \ldots, a_k$ without landing on any point in $M$. Let $p$ be the position after these $k$ jumps. Now, if $p + a_{k+1} \notin M'$, the grasshopper can make the $k+1$-th jump to the right with length $a_{k+1}$ and avoid landing on any point in $M$ since $p + a_{k+1}$ cannot be in $M'$.

If $p + a_{k+1} \in M'$, then $p + a_{k+1} = m + s$ for some $m \in M$. But $p + a_{k+1} - s = p - (a_1 + a_2 + \ldots + a_k) = p - s$, which means $p - s = m \in M$. However, $p - s$ is the position after $k$ jumps, which, by the induction hypothesis, does not land on any point in $M$. This contradicts $p - s = m \in M$. Therefore, $p + a_{k+1} \notin M'$, and the grasshopper can make the $(k+1)$-th jump without landing on any point in $M$.

By induction, the statement holds for all positive integers $n$.

Proceed by induction on $n$. Let $a_1<a_2<\dots<a_n$. Then, suppose $\max{M}>s-a_n$ and $s-a_n\not\in M$. Then, by the induction hypothesis, there exists a path from $0$ to $s-a_n$ that avoids all integers in $M$ that uses jumps $a_1$, $a_2$, $\dots$, $a_{n-1}$. Then, once at $s-a_n$, the grasshopper can jump $a_n$ and win. If $\max{M}\le s-a_n$ then consider the path that the grasshopper would take if we removed $\max{M}$ from $M$. If it doesn't hit $\max{M}$, we're all good. If it does, then replace that move with a larger one. We can always do this since $a_n$ is available. The remaining case is $\max{M}>s-a_n$ and $s-a_n\in M$. Let $S'=\{\{s-a_n-a_i, s-a_i\}\mid 1\le i\le n-1\}$. Note that $|S'|=n-1$ and $|M\setminus \{s-a_n\}|=n-2$, there exists an element $k\in S'$ such that $|M\cap k|=0$. Note that $|M\cap \{1,2,\dots,s-a_n-a_i-1\}|\le n-3$, so by the induction hypothesis, the grasshopper can jump to $s-a_n-a_i$ and then to $s-a_i$ and then to $s$.

Groupsolved with [b]cursed_tangent1434[/b].
We will use induction, and WLOG $a_1 < a_2 < a_3 < \ldots < a_n$, and let the elements of set $M$ be $m_1 \leq m_2 \leq m_3 \leq \ldots \leq m_{n-1}$.
$\newline$
Our base case of $n = 1$ is clearly true, and so is our $n = 2$ case.
$\newline$

Now assume that $n - 1$ works.
We then have to prove that for any choice of $m_{n-1}$ and choice of $a_n$ then it is possible to order the jumps in a way so that we land on $a_1 + a_2 + \ldots + a_n = s$ without touching an element of $M$.
$\newline$

Case $1$: $s - a_n < m_{n-1}$
From here, we can simply add $a_n$ to $s - a_n$ to reach $s$.
Note that it is possible to reach $s - a_n = a_1 + a_2 + \ldots + a_{n-1}$ since our $n - 1$ case is true.
$\newline$

Case $2$: $s - a_n \geq m_{n-1}$
If $m_{n-1}$ does not coincide with the points the grasshopper jumps on, then we're done by simply adding $a_n$ to $s - a_n$.
If otherwise, then swap the distance that the grasshopper jumped to land on $m_{n-1}$ with $a_n$. Since $m_{n-1}$ is the maximum value in $M$ and that $a_n \geq m_{n-1}$, this avoids all other elements of $M$, and leads the grasshopper to $s$.
So, our induction is done. $\blacksquare$


WLOG x1+x2+x3+x4=1
f(x)=1/x convex we apply Jensen and we have that:

x1/(x2+x3)+x2/(x3+x4)+x3/(x4+x1)+x4/(x1+x2)>=1/(x1x2+2x1x3+x1x4+x2x3+2x2x4+x3x4).

we have that:

2(x1x2+2x1x3+x1x4+x2x3+2x2x4+x3x4)<=(x1+x2+x3+x4)^2=1 which is equivalent to
(x1-x3)^2+(x2-x4)^2>=0

This is the  like the ineq from Rusia 1980 (posted by Manlio)

cheers! :D :D

Or we could amplify the i'h fraction with x_i for i from 1 to 4 and then use the result
\sum a_i2/x_i >= (\sum a_i)2/ (\sum x_i) for positive a_i and x_i, i from 1 to n. We continue as Lagrangia did.


calculus
integration
trigonometry
conics
ellipse
vector
calculus computations

Calculate
\[\int_\gamma e^{x}(\sin{(xy)}+y\cos{(xy)})dx+xe^{x}(\cos{(xy)})dy \]

where $\gamma$ is the ellipse $4x^{2}+y^{2}=9$ oriented anticlockwise.

this vector is Path independence.

Since the start point and the end point is equal, the integral is zero.

see ya http://en.wikipedia.org/wiki/Line_integral

[quote="misan"]use Mr. Green!  :D

$\int_{\gamma}\;f\;dx\;+\;g\;dy\;=\bigcirc \hspace{-0.5cm}\int \hspace{-0.25cm}\int_{R}\; ( \;-\frac{\partial f}{\partial y}\;+\;\frac{\partial g}{\partial x}\; ) \;d\mathbb{A}$

$\;=\;-\;e^{x}\; ( \;x\;\cos{(xy)}\;+\;\cos{(xy)}\;-\; ( \;xy\; ) \sin{(xy)}\; )\\ \\ \hspace* \;\;\;\;\;\;\; \qquad-\; ( \;xy\; ) \;e^{x}\;\sin{(xy)}\;+\;x\;e^{x}\;\cos{(xy)}\;+\;e^{x}\;\cos{(xy)}$

$=\;\boxed{0}\;$

(circle or ellipse won't matter)[/quote]
Thanks  :lol:
I made that calculation too but initially got an $x$ too much but now i got it.

Err... I think is much more easy to see that this vector field is path independent

${\frac{\partial \left(e^{x}\sin (x y)\right)}{\partial x}=e^{x}(y \cos (x y)+\sin (x y))}$
${\frac{\partial \left(e^{x}\sin (x y)\right)}{\partial y}=e^{x}x \cos (x y)}$

Yes it is also easy to find a potential for the field as you have shown above.
Thanks :lol:


Put the best website you have ever been to and tell us why it is good.  (try not to post the same ones again)
I will make a list of them on this post.
[url=http://www.miniclip.com]www.miniclip.com[/url]
[url=http://www.gamesofgondor.com]www.gamesofgondor.com[/url]
[url=http://www.onemorelevel.com]www.onemorelevel.com[/url]
[url=http://www.artofproblemsolving.com]www.artofproblemsolving.com[/url]
[url=http://mathworld.wolfram.com]mathworld.wolfram.com[/url]
[url=http://www.braingle.com/index.php?ref=GarnetLover]www.braingle.com/index.php?ref=GarnetLover[/url]\
[url=http://www.albinoblacksheep.com/]www.albinoblacksheep.com/[/url]
[url=http://www.gnu.org/]www.gnu.org/[/url]

Since I get the first post, I will say:

[url=http://artofproblemsolving.com]www.artofproblemsolving.com!!!!!!![/url]

This is seriously the best site I've ever visited. I spend about 5x more time on this site than all the other put together. (Including classes)  :)

I totally agree with 4everwise!!! This site's awesome!

Also, [u]http://mathworld.wolfram.com[/u] is a complete reference that any problem solver could want or need

Yeah, you guys should check out AoPS. It's seriously my favorite site on the whole internet. I'm not kidding! Check it out! http://www.artofproblemsolving.com :roll:

besides AoPS, http://www.braingle.com is awesome

if u want to visit, plz click here:  http://www.braingle.com/index.php?ref=GarnetLover  thanx

My site! Well, actually its pretty terrible (haven't worked on it in about a year).. but i'm working on something new, so when i'm done with this new site ill put a post up.

Yeah, http://www.artofproblemsolving.com is pretty awesome. But I guess that makes me unoriginal.

So, as something new.. uh... http://www.albinoblacksheep.com is funny.

[url=http://www.gnu.org]www.gnu.org[/url] - Lots of free (open source) software
"Software is like sex, it's better when it's free." - Linus Torvalds


trigonometry ratio geometry circumcircle incenter conics parabola

[img]http://www.mathlinks.ro/Forum/viewtopic.php?mode=attach&id=14764[/img]

 :(

[color=darkblue]I'm not sure about this, but...

We have $ \frac {b \minus{} c}{a} \equal{} \frac {\sin{\frac {B \minus{} C}{2}}}{\cos{\frac {A}{2}}}$, so we can find $ \cos{\frac {A}{2}}$ and $ \sin{\frac {A}{2}}$.

Then $ \frac {b \plus{} c}{a} \equal{} \frac {\cos{\frac {B \minus{} C}{2}}}{\sin{\frac {A}{2}}}$ and we can find $ b \plus{} c$. But we know $ b \minus{} c$, so we can find lenghts of the sides $ b,c$. Then construction is trivial.

I've got only one question: Can we say that we can calculate the $ \sin$ in consctruction problems.[/color]

Ahiles construction is absolutely correct, even though it looks ugly when attempted. Sine or cosine can be used /calculated in construction problems. $ \sin \phi$ or $ \cos \phi$ mean ratio of the proper leg and hypotenuse of some right triangle with one angle $ \phi.$ The ratio can be constructed given the angle, and the angle can be constructed given the ratio.
______________________________________________

Let $ O$ be the circumcenter and $ H$ the orthocenter, $ \angle OAH \equal{} \angle B \minus{} \angle C.$ $ M$ is midpoint of the segment $ a \equal{} BC.$ Place the segment $ b \minus{} c \equal{} DE$ parallel to $ BC,$ so that $ M$ is also midpoint of $ DE.$ Then $ D, E$ are tangency points of the incircle $ (I)$ and the A-excircle $ (J)$ with $ BC.$ The perpendicular bisector $ OM$ of $ BC$ cuts the circumcircle at $ P, Q,$ such that $ P$ is on the opposite side of $ BC$ then $ A.$ The internal bisector $ AI$ of the $ \angle A$ cuts $ (O)$ again at $ P.$

$ R$ is the circumradius. The incenter $ I$ is on circle $ (P)$ with radius $ PB \equal{} PC \equal{} PI$ and $ MD \equal{} PI \sin \frac {B \minus{} C}{2}.$ From similar right $ \triangle PQB \sim PBM,$ $ MP \equal{} \frac {PB^2}{PQ} \equal{} \frac {PI^2}{2R}.$ Then $ \frac {MD^2}{MP} \equal{} 2R \sin^2 \frac {B \minus{} C}{2} \equal{} \text{const}$ (disregarding $ b \minus{} c$), which means that $ D$ is on a parabola $ \mathcal P$ with vertex $ P,$ axis $ PQ,$ and passing through $ A.$ Since the ratio $ \frac {DE}{BC} \equal{} \frac {b \minus{} c}{a}$ is fixed and the 2 segments have a common midpoint $ M$, $ D$ is also on ellipse $ \mathcal Q$ with center $ O,$ the major axis $ PQ,$ and minor axis length $ PQ \cdot \frac {b \minus{} c}{a}.$ To construct intersections of the parabola and ellipse, project the ellipse $ \mathcal Q$ to the circumcircle $ (O)$ and the parabola $ \mathcal P$ to a larger parabola $ \mathcal P^*.$ Let $ t \perp PQ$ be the common tangent $ t$ at $ P$ of the parabola $ \mathcal P$ and ellipse $ \mathcal Q,$ same as the common tangent of the projected parabola $ \mathcal P^*$ and circle $ (O).$ Put the coordinate origin at $ P,$ the x-axis along $ t$ and y-axis along $ PQ.$ Let $ F \in PQ$ be the focus of $ \mathcal P^*.$ Equations of the circle $ (O)$ and parabola $ \mathcal P^*$ with focus $ F$ are

$ x^2 \plus{} (y \minus{} OP)^2 \equal{} OP^2,\ \ y \equal{} \frac {x^2}{4\ PF}.$

Subtracting and reducing by $ x^2,$

$ x^2 \equal{} 4\ PF (2\ OP \minus{} 4\ PF),\ \ y \equal{} 2\ OP \minus{} 4\ PF \equal{} PQ \minus{} 4\ PF.$

$ y$ is the distance of the parabola $ \mathcal P^*$ / circle $ (O)$ intersections from their common tangent $ t.$
_____________________________________________

[b]Construction:[/b] Construct a right $ \triangle A'KL$ with the side $ A'L \equal{} a,$ right angle $ \angle A'KL,$ and $ \angle LA'K \equal{} \angle B \minus{} \angle C.$ Draw its circumcircle $ (O)$ centered at the midpoint $ O$ of $ A'L.$ Parallel to $ KL$ through $ O$ cuts the circle $ (O)$ at $ B, C$ and $ BC \equal{} a.$ Construct points $ D, E \in BC$ such that $ DE, BC$ have the common midpoint $ O$ and $ DE \equal{} b \minus{} c.$ Perpendicular bisector of $ BC$ cuts $ (O)$ at $ P, Q,$ such that $ P$ is on the opposite side of $ BC$ than $ A'.$

Project the ellipse $ \mathcal Q$ (not drawn) with major/minor axes $ PQ, DE$ to the circle $ (O).$ That is, do nothing, we already have the circle. To project the parabola $ \mathcal P,$ draw perpendiculars $ n_B, n_D$ to $ BC$ at $ B, D.$ Perpendicular $ n_D$ cuts $ A'P$ at $ S.$ Draw parallels $ p_A, p_S$ to $ BC$ at $ A', S.$ Perpendicular $ n_B$ cuts the parallel $ p_S$ at $ S^*.$ Parallel $ p_A$ cuts the line $ PS^*$ at the projection $ A^*$ of $ A'.$ The projected parabola $ \mathcal P^*$ (not drawn) has the same vertex $ P,$ the same axis $ PQ,$ and it passes through $ A^*.$

Let $ t \perp PQ$ at $ P$ be the parabola vertex tangent, the locus of perpendiculars from the parabola focus to the parabola tangents. Parallel to the parabola axis through $ A^*$ cuts $ t$ at $ U.$ Let $ V$ be the midpoint of $ PU.$ $ A^*V$ is the parabola tangent at $ A^*.$ Perpendicular to $ A^*V$ at $ V$ cuts the parabola axis $ PQ$ at the focus $ F.$

Quadruple the segment $ PF$ into $ PG,$ so that $ PG \equal{} 4\ PF$ and reflect $ G$ in $ BC$ into $ M'.$ Perpendicular to $ PQ$ at $ M'$ cuts the circle $ (O)$ at $ B'C'.$ The $ \triangle A'B'C'$ is just similar to the desired $ \triangle ABC,$ because, not knowing the circumradius, we started with a circle $ (O)$ with diameter $ BC \equal{} a.$ To finish, draw parallels to $ A'B', A'C'$ through $ B, C,$ respectively, intersecting at $ A.$

cuts the circle (O) at B,C

where's B and where´s C  ?

Construct points D,E\in BC such that DE, BC  have the common midpoint O and  DE=b-c

where's D and where´s E  ?

 :(

$ A'L \equal{} BC \equal{} PQ \equal{} a$ are all diameters of the circle $ (O).$ (This will not be circumcircle of the resulting $ \triangle ABC$, but of the similar $ \triangle A'B'C'.$) The diameter $ BC$ is parallel to $ KL$ and the diameter $ PQ$ perpendicular to $ KL.$ Small concentric circle with center $ O$ and radius $ \frac {b \minus{} c}{2}$ cuts $ BC$ at $ D, E.$ See the figure.


Salut! Are cineva posibilitatea sa posteze unele din problemele mai interesante de la Unirea 2005? Multumesc.

intrebarea este daca stie cineva care a fost la concurs despre forum? :)

Subiectele sunt in fisierul atasat (din pacate, .doc, deocamdata)

Multumesc. Va trebui sa mai astept putin pana sa le pot citi. Separe ca francezilor nu le plac prea mult documentele word.

Vezi că ţi-am ataşat o variantă .pdf a fişierului (creată din .doc-ul ala) :)

Multumesc, Valentin, acum il pot citi. Mersi.


calculus
integration
function
limit
calculus computations

Can anyone please explain the following problems? I don't know how to show them. Thanks.

1.  a.  Show that if $f$ is an even function and the necessary integrals exist, then $\displaystyle\int^\infty_{-\infty} f(x)\ dx = 2 \displaystyle\int^\infty_0 f(x)\ dx $.

b. Show that if $f$ is odd and the necessary integrals exist, then $\displaystyle\int^\infty_{-\infty} f(x)\ dx = 0$.

Any help is greatly appreciated.

The key step we need is the following lemma:

Lemma: If $\int_{-\infty}^{\infty}f(x)\, dx$ exists, $\int_{-\infty}^{\infty}f(x)\, dx=\lim_{M\to\infty}\int_{-M}^M f(x)\, dx.$
Proof: The limit of a sum is equal to the sum of the limits (if those limits exist), so
$\lim_{M\to\infty}\int_{-M}^M f(x)\, dx=\lim_{M\to\infty}\left(\int_{-M}^0 f(x)\, dx+\int_{0}^M f(x)\, dx\right)$
$=\lim_{M\to\infty}\int_{-M}^0 f(x)\, dx+\lim_{M\to\infty}\int_{0}^M f(x)\, dx$
$=\int_{-\infty}^0f(x)\, dx+\int_0^\infty f(x)\, dx=\int_{-\infty}^{\infty}f(x)\, dx.$

Now you can apply what you know about integrals of odd and even functions on finite intervals.


Let $ \left(a_1,a_2,...,a_n\right)$ and $ \left(b_1,b_2,...,b_n\right)$ be two sequences of positive reals. We are searching for a permutation $ \pi$ of the set $ \left\{1,2,...,n\right\}$ that minimizes the sum

$ \sum_{k\equal{}1}^n a_{\pi\left(k\right)} \sum_{i\equal{}k}^n b_{\pi\left(i\right)}$
$ \equal{}a_{\pi\left(1\right)}\left(b_{\pi\left(1\right)}\plus{}b_{\pi\left(2\right)}\plus{}...\plus{}b_{\pi\left(n\right)}\right)$
$ \plus{}a_{\pi\left(2\right)}\left(b_{\pi\left(2\right)}\plus{}b_{\pi\left(3\right)}\plus{}...\plus{}b_{\pi\left(n\right)}\right)$
$ \plus{}...\plus{}a_{\pi\left(n\right)}b_{\pi\left(n\right)}$.

Prove that any permutation $ \pi$ that satisfies

$ \frac{a_{\pi\left(1\right)}}{b_{\pi\left(1\right)}}\leq\frac{a_{\pi\left(2\right)}}{b_{\pi\left(2\right)}}\leq ...\leq\frac{a_{\pi\left(n\right)}}{b_{\pi\left(n\right)}}$

minimizes this sum.

[i]Remark.[/i] As an application, this yields an optimal strategy for fighting a group of monsters in a simplified RPG (no area damage, no pulling of enemies, etc.): Assume that one has to face $ n$ enemies, numbered $ 1$, $ 2$, ..., $ n$. For every $ i$, let $ a_i$ be the time that one needs to kill enemy $ i$ if one ignores the other enemies, and $ b_i$ the damage that enemy $ i$ deals to the player in one second. Then, in order to lose as little health as possible during the battle, one should first take on the enemy with the lowest ratio $ \frac{a_i}{b_i}$, then after killing him turn on the one with the second lowest $ \frac{a_i}{b_i}$, and so on.

Assume the contrary. Let $ k$ be the largest index so that $ \frac {a_{\pi(k)}}{b_{\pi(k)}}\le\frac {a_{\pi(k \plus{} 1)}}{b_{\pi(k \plus{} 1)}}\le...\le\frac {a_{\pi\left(n\right)}}{b_{\pi\left(n\right)}}$.
If $ k \equal{} 1$, we are done, so assume now $ k > 1$.

Let $ S$ be the current sum in question, and $ S'$ be the sum when $ a_{\pi(k)}$ and $ a_{\pi(k \minus{} 1)}$ are switched.

Then, $ S' \minus{} S \equal{} a_{\pi(k)}b_{\pi(k \minus{} 1)} \minus{} a_{\pi(k \minus{} 1)}b_{\pi(k)} \equal{} b_{\pi(k)}b_{\pi(k \minus{} 1)}(\frac {a_{\pi(k)}}{b_{\pi(k)}} \minus{} \frac {a_{\pi(k \minus{} 1)}}{b_{\pi(k \minus{}1 )}}) < 0$, contradicting the that $ S$ has the smallest sum of any arrangement, contradiction! Hence, the result.

Cheers,

Rofler

Yep. I have taken the liberty to fix some typos in your post (for instance, we are searching for the smallest, not the largest sum). Your solution is the first solution given in American Mathematical Monthly 1973, pp. 437-438.

I will post the second proposed solution (by R. J. Dickson, without his overcomplicated writeup) in a moment.

Here comes Dickson's solution. Note that the sequence $ \left(a_1,a_2,...,a_n\right)$ needs not consist of positive reals; arbitrary reals will do.

  darij


[b][size=100][color=Darkblue]Δίνεται τρίγωνο $ \bigtriangleup ABC$ εγγεγραμμένο σε κύκλο $ (O)$ και έστω $ M,\ N,$ σημεία επι των ευθειών των πλευρών του $ AB,\ AC$ αντιστοίχως, τέτοια ωστε $ BM \equal{} BC \equal{} CN$ $ ($ $ B,$ μεταξύ των $ A,\ M$ και $ C,$ μεταξύ των  $ A,\ N$ $ ).$ Αποδείξτε ότι $ OI_{a}\perp MN,$ όπου $ O$ είναι το περίκεντρο του $ \bigtriangleup ABC$ και $ I_{a}$ είναι το κέντρο του παρεγγεγραμμένου κύκλου στη γωνία $ \angle A.$[/color][/size][/b]

Το πρόβλημα αυτό μου το έστειλε με άλλη διατύπωση, ένας φίλος μας από το Βιετνάμ και παραξενεύτηκα για το ότι μπορεί να λύνεται τόσο δύσκολα ( όπως εγώ μπόρεσα ), ένα πρόβλημα με τόσο λιτή εκφώνηση.

Έχω την αίσθηση ότι υπάρχει απλούστερη λύση και προσβλέπω στη δική σας προσέγγιση, γιατί όπως ξέρουμε περνώντας τα χρόνια, το μυαλό αρέσκεται σε όλο και πιο πολύπλοκες λύσεις ( = complicated solutions... )  :(

Κώστας Βήττας.

Αν και δεν μου αρέσει η λύση μου (γιατί είναι μετρική) σίγουρα μπορεί να θεωρηθεί απλή.

Συγχωρέστε με, αλλά θα τη γράψω λίγο συνοπτικά. Το ζητούμενο είναι ισοδύναμο με:
$ OM^2 \minus{} ON^2 \equal{} I_aM^2 \minus{} I_aN^2$. Και τώρα δουλέυω με δύναμη σημείου. Δηλαδή:

$ OM^2 \minus{} ON^2 \equal{} MB\cdot MA \minus{} MC\cdot NA \equal{} BC(AB \minus{} AC)$

Ομοια, θεωρώντας $ K,L$ τα σημεία τομής του παραγγεγραμμένου με τις $ AB, AC$ αντίστοιχα, θα έχουμε:

$ I_aM^2 \minus{} I_aN^2 \equal{} MK^2 \minus{} NL^2 \equal{} (BM \minus{} BK)^2 \minus{} (NC \minus{} CL)^2 \equal{} ...\equal{}$

$ \equal{}BC (AB \minus{}AC)$

Επεται το ζητούμενο... :wink:

Πολύ ωραία . Αυτή είναι  επίσης η λύση μου . Να ένα εντελώς παρόμοιο πρόβλημα και η λύση του

Δημήτρη σ' ευχαριστώ πολύ για το βάρος που έβγαλες από πάνω μου, για ένα μακρύ απαντητικό μήνυμα.

Αυτή τη λύση προτιμώ γι' αυτό το πρόβλημα και είναι πολύ καλή. Αν αξίζει να κρατήσω κάτι από τη λύση μου ( έφτασα μέχρι Πολικές και Desarques... :ewpu: ), είναι μερικά ενδιάμεσα αποτελέσματα, που θα τα βάλω αργότερα σαν ξεχωριστές ασκήσεις.

Κώστας Βήττας.


Given an acute-angled triangle $ ABC$ with circumcenter $ O.$ The circle passing through two points $ A,\ O$ intersects with the line $ AB$ and $ AC$ at $ P,\ Q$ other than $ A$ respectively. If the lengths of the line segments $ PQ,\ BC$ are equal, then find the angle $ \leq 90^\circ$ that the lines $ PQ$ and $ BC$ make.

Consider circumcircles of $ APQ$ and $ ABC$. Since $ PQ \equal{} BC$ and $ \angle PAQ \equal{} \angle BAC$, it follows that the circles have same radius. let $ O_{1}$ be circumcentre of $ APQ$. Since $ AO \equal{} R \equal{} AO_{1} \equal{} OO_{1}$, $ AOO_{1}$ is equilatrel and $ \angle AO_{1}O \equal{} 60$. Then $ \angle OPC \equal{} \frac {\angle AO_{1}O}{2} \equal{} 30$, and since $ \angle OAC \equal{} 90\minus{}B$, then $ \angle POA \equal{} B \minus{} 60$, so $ \angle PQB \equal{} \angle B\minus{}60$. Since $ \angle ABC \equal{} B$, it follows the angle between $ PQ$ and $ BC$ is $ 60$ degrees.

Let D be the second intersection of $ (O')$ and $ (O). PQ\cap AC\equal{}\{L\}$
$ \angle PLC\equal{}\angle AQP\plus{}\angle ACB\equal{}\angle ADP\plus{}\angle ADB\equal{}\angle PDB$
But $ (O)$ and $ (O')$ have same radius and O' lies on $ (O)$ then $ \angle APD\equal{}\angle ABD\equal{}60^o \Rightarrow \angle PDB\equal{}60^o$
So $ \angle PLC\equal{}60^o$

Let $M,N$ be the midpoints of $AB,AC$ respectively, note $OM\perp AB, ON\perp AC$. Also, $A,O,M,N$ are cyclic $\implies \triangle OMN\sim \triangle OPQ$, since $PQ=BC=2MN$ it follows that $\triangle OPQ$ and $\triangle OMN$ are a $60^{\circ}$ rotation of each other hence the angle between $PQ$ and $BC$ is $60^{\circ}$.


number theory
least common multiple
number theory open

first consider Fibbonaci's seq: F1=F2=1, Fn=F(n-1)+F(n-2)
now consider this seq: Pn=Fn mod B ( B is a fixed integer)
this sequence is periodical with the maximum period B(B-1)/2
how can i actually determine the period... ?

As far as I know, the general case is an open problem.
Let m  \geq  2 be an integer.
Lucas (1878) has proved that the Fibonacci sequence is periodic modulo m, and that there exists n such that F_n = 0 mod[m].
Let k(m) the length of the lesat period of (F_i) mod[m], anf f(m) be the least n such that F_n = 0 mod[m].

Walls has found many conditions on k(m) and f(m). In particular, f(m) divides k(m) and if m =  prod (p_i) a_i  where the p_i's are distinct primes, then k(m) = lcm( k((p_i) a_i) ).
Moreover, if p is a prime and t is the largest integer such that k(p t ) = k(p) then k(p a+t ) = p a k(p) for all integers a  \geq  0.

Walls results may be used to determine some values of k(m), but as said above, the general determination of k(m) is difficult.
Thus, it may be useful to look at the two following theorems of Vinson. Let t(m) = k(m)/f(m) :

Th. 1 :
If m > 2 then :
t(m) = 4 if f(m) is odd.
t(m) = 1 if m =/= 0 mop[8] and f(p) = 2 mod[4] for each odd prime p dividing m.
t(m) = 2 in every other case.

Thus, it shows that the main problem is to determine f(m).

Th. 2 :
Let p be an odd prime. Then, for each integer e > 0 :
t(p e ) = 1 if p = 11 or 19 mod[20]
t(p e ) = 2 if p = 3 or 7 mod[20]
t(p e ) = 4 if p = 13 or 17 mod[20]
t(p e ) =/= 2 if p = 21 or 29 mod[40].
In the other cases 'everything' may happen...

Moreover, it is known [3] that k(m)  \leq  6m for all m.

References :
[1] D.D.Walls, 'Fibonacci series modulo m', A.M.M. (1960), p.525-532.
[2] J.Vinson, 'The relation of the period modulo to the rank of apparition of m in the Fibonacci sequence', Fibonacci Quaterly, 1963, p.37-45.
[3] A.M.M., 1992, exercice n E3410, p.272-273.

Pierre.

This problems resembles that of finding the order of 2 mod p for a prime p as much as finding F_p such that F_p is prime resembles that of finding all the primes of the form 2 p+1.
These are all, I think, open problems.


number theory
greatest common divisor
geometry
USAMTS
AMC

Given that P,Q are primes, with P>50.

Find the largest integer that must divide (P+Q) given that PQ is one less than a perfect square

I hope it's right:

[hide]Since PQ is 1 less than a perfect square, we could have a parametric form of P=x+1 and Q=x-1 so that PQ=x^2-1.  Thus, we are basically finding the largest integer that must divide P+Q=2x.  We know that x must also be even since all primes greater than two are odd (and so P is odd and Q is odd, which makes x even).  Given this amount of information, we could conclude that 2*2=4 must divide P+Q.[/hide]

-interesting_move

Can you? Two possible pairs are (3,5) and (5,7) (basically, any pair of twin primes), and their sums are 8 and 12 respectively, whose gcd is 4.

I'm sorry; I thought it said P<50. Sigh. Allright; we know that all large primes are neighbors of 6, therefore any twin primes must surround a multiple of 6, making their sum a multiple of 12.
59, 61 are twin primes; so are 71, 73 and 101, 103. (i think they are all primes). anyways, their sums will be 120, 144, and 204. The gcd of these three expressions is 12, so that is the largest integer possible.
How's that?

Yes, but it says that P>50...so you can get more.

Right. After someone posts the solution to this problem, remind me to tell an interesting anecdote about a similar problem.

So the answer is [hide]12[/hide]?

-interesting_move

Yes.

In the final round of Math Bowl at Bay Area Math Meet 2000, one question that Paul Zeitz asked was (worded differently almost certainly) ``a and b are 12-digit numbers differing by 2, and they're both prime. What is the remainder when ab is divided by 9?'' No one in the finals had a clue how to do it, but it's actually not that hard. a and b (mod 9) must be (2,4), (5,7), or (8,1) if we assume (WLOG) that a<b. In any of those three cases, ab :equiv: 8 (mod 9). The only one that doesn't satisfy this condition is (3, 5).

Just for fun, try this problem (from Century 2 of KoMaL, which was a USAMTS prize in 2001):

For which values of p and q such that p-q=2 is p^2-pq+q^2 a prime? Prove it!

Solution:

Obviously, we all got that 4 must divide (P+Q)

so, now to get the three, consider P and Q mod3.

SInce they are twin primes, they cannot be congruent mod3.
Thus, one is 1(mod3) and one is 2(mod3)

Add them up, and u get 0(mod3) thus, 3l(P+Q)


inequalities probability algebra polynomial calculus integration function

Here is the IMO shortlist problems 1983, I got it from internet.

[b][size=150]IMO 1983 ShortListed Problems (Posted in Forums):[/size][/b]

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013595#p2013595]1. (AUS 1)[/url] The localities $P_1, P_2, \dots, P_{1983}$ are served by ten international airlines $A_1,A_2, \dots , A_{10}$. It is noticed that there is direct service (without stops) between any two of these localities and that all airline schedules offer round-trip flights. Prove that at least one of the airlines can offer a round trip with an odd number of landings.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013598#p2013598]2. (BEL 1)[/url] Let $n$ be a positive integer. Let $\sigma(n)$ be the sum of the natural divisors $d$ of $n$ (including $1$ and $n$). We say that an integer $m \geq 1$ is superabundant (P.Erdos, $1944$) if $\forall k \in  \{1, 2, \dots , m - 1 \}$, $\frac{\sigma(m)}{m} >\frac{\sigma(k)}{k}.$
Prove that there exists an infinity of superabundant numbers.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=366619&#p366619]3. (BEL 3)[/url][b]IMO4[/b] Let $ABC$ be an equilateral triangle and $\mathcal{E}$ the set of all points contained in the three segments $AB$, $BC$, and $CA$ (including $A$, $B$, and $C$).  Determine whether, for every partition of $\mathcal{E}$ into two disjoint subsets, at least one of the two subsets contains the vertices of a right-angled triangle.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013660#p2013660]4. (BEL 5)[/url] On the sides of the triangle $ABC$, three similar isosceles triangles $ABP \ (AP = PB)$, $AQC \ (AQ = QC)$, and $BRC \ (BR = RC)$ are constructed. The first two are constructed externally to the triangle $ABC$, but the third is placed in the same half-plane determined by the line $BC$ as the triangle $ABC$. Prove that $APRQ$ is a parallelogram.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013665#p2013665]5. (BRA 1)[/url] Consider the set of all strictly decreasing sequences of $n$ natural numbers having the property that in each sequence no term divides any other term of the sequence. Let $A = (a_j)$ and $B = (b_j)$ be any two such sequences. We say that $A$ precedes $B$ if for some $k$, $a_k < b_k$ and $a_i = b_i$ for $i < k$. Find the terms of the first sequence of the set under this ordering.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013667#p2013667]6. (CAN 2)[/url] Suppose that ${x_1, x_2, \dots , x_n}$ are positive integers for which $x_1 + x_2 + \cdots+ x_n = 2(n + 1)$. Show that there exists an integer $r$ with $0 \leq r \leq n - 1$ for which the following $n - 1$ inequalities hold:
\[x_{r+1} + \cdots + x_{r+i} \leq 2i+ 1, \qquad \qquad  \forall i, 1 \leq i \leq n - r; \]
\[x_{r+1} + \cdots + xn + x_1 + \cdots+ x_i \leq 2(n - r + i) + 1, \qquad \qquad \forall i, 1 \leq i \leq r - 1.\]
Prove that if all the inequalities are strict, then $r$ is unique and that otherwise there are exactly two such $r.$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013668#p2013668]7. (CAN 5)[/url] Let $a$ be a positive integer and let $\{a_n\}$ be defined by $a_0 = 0$ and
\[a_{n+1 }= (a_n + 1)a + (a + 1)a_n + 2 \sqrt{a(a + 1)a_n(a_n + 1)} \qquad (n = 1, 2 ,\dots ).\]
Show that for each positive integer $n$, $a_n$ is a positive integer.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013675#p2013675]8. (SPA 2)[/url] In a test, $3n$ students participate, who are located in three rows of $n$ students in each. The students leave the test room one by one. If $N_1(t), N_2(t), N_3(t)$ denote the numbers of students in the first, second, and third row respectively at time $t$, find the probability that for each t during the test,
\[|N_i(t) - N_j(t)| < 2, i \neq  j, i, j = 1, 2, \dots .\]

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=343813&#p343813]9. (USA 3)[/url][b]IMO6[/b] Let $ a$, $ b$ and $ c$ be the lengths of the sides of a triangle. Prove that
\[ a^{2}b(a - b) + b^{2}c(b - c) + c^{2}a(c - a)\ge 0.
\]
Determine when equality occurs.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013677#p2013677]10. (FIN 1)[/url] Let $p$ and $q$ be integers. Show that there exists an interval $I$ of length $1/q$ and a polynomial $P$ with integral coefficients such that
\[ |P(x)-\frac pq | < \frac{1}{q^2}\]
for all $x \in I.$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013680#p2013680]11. (FIN 2’)[/url] Let $f : [0, 1] \to \mathbb R$ be continuous and satisfy:
\[ \begin{cases}bf(2x) = f(x), &\mbox{ if } 0 \leq x \leq 1/2,\\ f(x) = b + (1 - b)f(2x - 1), &\mbox{ if } 1/2 \leq x \leq 1,\end{cases}\]
where $b = \frac{1+c}{2+c}$, $c > 0$. Show that $0 < f(x)-x < c$ for every $x, 0 < x < 1.$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=366613&#p366613]12. (GBR 4)[/url][b]IMO1[/b] Find all functions $f$ defined on the set of positive reals which take positive real values and satisfy: $f(xf(y))=yf(x)$ for all $x,y$; and $f(x)\to0$ as $x\to\infty$.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013682#p2013682]13. (LUX 2)[/url] Let $E$ be the set of $1983^3$  points of the space $\mathbb R^3$ all three of whose coordinates are integers between $0$ and $1982$ (including $0$ and $1982$). A coloring of $E$ is a map from $E$ to the set {red, blue}. How many colorings of $E$ are there satisfying the following property: The number of red vertices among the $8$ vertices of any right-angled parallelepiped is a multiple of $4$ ?

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=366621&#p366621]14. (POL 2)[/url][b]IMO5[/b] Is it possible to choose $1983$ distinct positive integers, all less than or equal to $10^5$, no three of which are consecutive terms of an arithmetic progression?

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013684#p2013684]15. (POL 3)[/url] Decide whether there exists a set $M$ of natural numbers satisfying the following conditions:

(i) For any natural numberm $>1$ there are $a, b \in M$ such that $a+b = m.$

(ii) If $a, b, c, d \in M , a, b, c, d > 10$ and $a + b = c + d$, then $a = c$ or $a = d.$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013686#p2013686]16. (GDR 1)[/url] Let $F(n)$ be the set of polynomials $P(x) = a_0+a_1x+\cdots+a_nx^n$, with $a_0, a_1, . . . , a_n \in \mathbb R$ and $0 \leq a_0 = a_n \leq a_1 = a_{n-1 } \leq \cdots \leq a_{[n/2] }= a_{[(n+1)/2]}.$ Prove that if  $f \in F(m)$ and $g \in  F(n)$, then $fg \in  F(m + n).$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013689#p2013689]17. (GDR 3)[/url] Let $P_1, P_2, \dots , P_n$ be distinct points of the plane, $n \geq  2$. Prove that
\[ \max_{1\leq i<j\leq n} P_iP_j > \frac{\sqrt 3}{2}(\sqrt n -1) \min_{1\leq i<j\leq n} P_iP_j  \]

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=366618&#p366618]18. (FRG 3)[/url][b]IMO3[/b] Let $a,b$ and $c$ be positive integers, no two of which have a common divisor greater than $1$. Show that $2abc-ab-bc-ca$ is the largest integer which cannot be expressed in the form $xbc+yca+zab$, where $x,y,z$ are non-negative integers.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013692#p2013692]19. (ROM 1)[/url] Let $(F_n)_{n\geq 1} $ be the Fibonacci sequence $F_1 = F_2 = 1, F_{n+2} = F_{n+1} + F_n (n \geq 1),$ and $P(x)$ the polynomial of degree $990$ satisfying
\[ P(k) = F_k, \qquad \text{ for } k = 992, . . . , 1982.\]
Prove that $P(1983) = F_{1983} - 1.$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2012303&#p2012303]20. (ROM 3)[/url] [b]ISL 1984 P1[/b] Find all solutions of the following system of $n$ equations in $n$ variables:
\[\begin{array}{c}\  x_1|x_1| - (x_1 - a)|x_1 - a| = x_2|x_2|,x_2|x_2| - (x_2 - a)|x_2 - a| = x_3|x_3|,\ \vdots \ x_n|x_n| - (x_n - a)|x_n - a| = x_1|x_1|\end{array}\]
where $a$ is a given number.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013700#p2013700]21. (SWE 1)[/url] Find the greatest integer less than or equal to $\sum_{k=1}^{2^{1983}} k^{\frac{1}{1983} -1}.$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013701#p2013701]22. (SWE 4)[/url] Let $n$ be a positive integer having at least two different prime factors. Show that there exists a permutation $a_1, a_2, \dots , a_n$ of the integers $1, 2, \dots , n$ such that
\[\sum_{k=1}^{n} k \cdot \cos \frac{2 \pi a_k}{n}=0.\]

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=366615&#p366615]23. (USS 1)[/url][b]IMO2[/b] Let $A$ be one of the two distinct points of intersection of two unequal coplanar circles $C_1$ and $C_2$ with centers $O_1$ and $O_2$ respectively. One of the common tangents to the circles touches $C_1$ at $P_1$ and $C_2$ at $P_2$, while the other touches $C_1$ at $Q_1$ and $C_2$ at $Q_2$. Let $M_1$ be the midpoint of $P_1Q_1$ and $M_2$ the midpoint of $P_2Q_2$. Prove that $\angle O_1AO_2=\angle M_1AM_2$.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013703#p2013703]24. (USS 2)[/url] Let $d_n$ be the last nonzero digit of the decimal representation of $n!$. Prove that $d_n$ is aperiodic; that is, there do not exist $T$ and $n_0$ such that for all $n \geq n_0, d_{n+T} = d_n.$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013705#p2013705]25. (USS 3)[/url] Prove that every partition of $3$-dimensional space into three disjoint subsets has the following property: One of these subsets contains all possible distances; i.e., for every $a \in \mathbb R^+$, there are points $M$ and $N$ inside that subset such that distance between $M$ and $N$ is exactly $a.$

[b][size=150]IMO 1983 LongListed Problems (Posted in Forums):[/size][/b]

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013595#p2013595]1. (AUS 1)[/url] [b](SL83-1)[/b] The localities $P_1, P_2, \dots, P_{1983}$ are served by ten international airlines $A_1,A_2, \dots , A_{10}$. It is noticed that there is direct service (without stops) between any two of these localities and that all airline schedules offer round-trip flights. Prove that at least one of the airlines can offer a round trip with an odd number of landings.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2037642#p2037642]2.(AUS 2)[/url] Seventeen cities are served by four airlines. It is noted that there is direct service (without stops) between any two cities and that all airline schedules offer round-trip flights. Prove that at least one of the airlines can offer a round trip with an odd number of landings.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2037682#p2037682]3. (AUS 3)[/url] (a) Given a tetrahedron $ABCD$ and its four altitudes (i.e., lines through each vertex, perpendicular to the opposite face), assume that the altitude dropped from $D$ passes through the orthocenter $H_4$ of $\triangle ABC$. Prove that this altitude $DH_4$ intersects all the other three altitudes.

(b) If we further know that a second altitude, say the one from vertex A to the face $BCD$, also passes through the orthocenter $H_1$ of $\triangle BCD$, then prove that all four altitudes are concurrent and each one passes through the orthocenter of the respective triangle.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013598#p2013598]4. (BEL 1)[/url] [b](SL83-2).[/b] Let $n$ be a positive integer. Let $\sigma(n)$ be the sum of the natural divisors $d$ of $n$ (including $1$ and $n$). We say that an integer $m \geq 1$ is superabundant (P.Erdos, $1944$) if $\forall k \in  \{1, 2, \dots , m - 1 \}$, $\frac{\sigma(m)}{m} >\frac{\sigma(k)}{k}.$
Prove that there exists an infinity of superabundant numbers.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2037701#p2037701]5. (BEL 2)[/url] Consider the set $\mathbb Q^2$ of points in $\mathbb R^2$, both of whose coordinates are rational.

(a)	Prove that the union of segments with vertices from $\mathbb Q^2$  is the entire set $\mathbb R^2$.
(b)	Is the convex hull of $\mathbb Q^2$ (i.e., the smallest convex set in $\mathbb R^2$ that contains $\mathbb Q^2$) equal to $\mathbb R^2$ ?

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=366619&#p366619]6. (BEL 3)[/url][b]IMO4[/b] Let $ABC$ be an equilateral triangle and $\mathcal{E}$ the set of all points contained in the three segments $AB$, $BC$, and $CA$ (including $A$, $B$, and $C$).  Determine whether, for every partition of $\mathcal{E}$ into two disjoint subsets, at least one of the two subsets contains the vertices of a right-angled triangle.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2037703#p2037703]7. (BEL 4)[/url] Find all numbers $x \in \mathbb Z$ for which the number
\[x^4 + x^3 + x^2 + x + 1\]
is a perfect square.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013660#p2013660]8. (BEL 5)[/url] [b](SL83-4).[/b]On the sides of the triangle $ABC$, three similar isosceles triangles $ABP \ (AP = PB)$, $AQC \ (AQ = QC)$, and $BRC \ (BR = RC)$ are constructed. The first two are constructed externally to the triangle $ABC$, but the third is placed in the same half-plane determined by the line $BC$ as the triangle $ABC$. Prove that $APRQ$ is a parallelogram.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013665#p2013665]9. (BRA 1)[/url] [b](SL83-5).[/b]  Consider the set of all strictly decreasing sequences of $n$ natural numbers having the property that in each sequence no term divides any other term of the sequence. Let $A = (a_j)$ and $B = (b_j)$ be any two such sequences. We say that $A$ precedes $B$ if for some $k$, $a_k < b_k$ and $a_i = b_i$ for $i < k$. Find the terms of the first sequence of the set under this ordering.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2037704#p2037704]10. (BRA 2)[/url] Which of the numbers 1, 2, . . . , 1983 has the largest number of divisors?

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2037707#p2037707]11. (BRA 3)[/url] A boy at point $A$ wants to get water at a circular lake and carry it to point $B$. Find the point $C$ on the lake such that the distance walked by the boy is the shortest possible given that the line $AB$ and the lake are exterior to each other.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2037716#p2037716]12. (BRA 4)[/url] The number $0$ or $1$ is to be assigned to each of the $n$ vertices of a regular polygon. In how many different ways can this be done (if we consider two assignments that can be obtained one from the other through rotation in the plane of the polygon to be identical)?

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2039309#p2039309]13. (BUL 1)[/url] Let $p$ be a prime number and $a_1, a_2, \ldots, a_{(p+1)/2}$ different natural numbers less than or equal to $p.$ Prove that for each natural number $r$ less than or equal to $p$, there exist two numbers (perhaps equal) $a_i$ and $a_j$ such that
\[p \equiv a_i a_j  \pmod r.\]

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2039312#p2039312]14. (BUL 2)[/url] Let $\ell$ be tangent to the circle $k$ at $B$. Let $A$ be a point on $k$ and $P$ the foot of perpendicular from $A$ to $\ell$. Let $M$ be symmetric to $P$ with respect to $AB$. Find the set of all such points $M.$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2039315#p2039315]15. (CAN 1)[/url] Find all possible finite sequences $\{n_0, n_1, n_2, \ldots, n_k \}$ of integers such that for each $i, i$ appears in the sequence $n_i$ times $(0 \leq i \leq k).$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013667#p2013667]16. (CAN 2)[/url] (SL83-6). Suppose that ${x_1, x_2, \dots , x_n}$ are positive integers for which $x_1 + x_2 + \cdots+ x_n = 2(n + 1)$. Show that there exists an integer $r$ with $0 \leq r \leq n - 1$ for which the following $n - 1$ inequalities hold:
\[x_{r+1} + \cdots + x_{r+i} \leq 2i+ 1, \qquad \qquad  \forall i, 1 \leq i \leq n - r; \]
\[x_{r+1} + \cdots + xn + x_1 + \cdots+ x_i \leq 2(n - r + i) + 1, \qquad \qquad \forall i, 1 \leq i \leq r - 1.\]
Prove that if all the inequalities are strict, then $r$ is unique and that otherwise there are exactly two such $r.$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2039320#p2039320]17. (CAN 3)[/url] In how many ways can $1, 2,\ldots, 2n$ be arranged in a $2 \times  n$ rectangular array $\left(\begin{array}{cccc}a_1& a_2 & \cdots & a_n\\b_1& b_2 & \cdots & b_n\end{array}\right)$ for which:
(i) $a_1 < a_2 < \cdots < a_n,$

(ii)  $b_1 < b_2 <\cdots < b_n,$

(iii) $a_1 < b_1, a_2 < b_2, \ldots, a_n < b_n \ ?$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2039324#p2039324]18. (CAN 4)[/url] Let $b \geq 2$ be a positive integer.

(a) Show that for an integer $N$, written in base $b$, to be equal to the sum of the squares of its digits, it is necessary either that $N = 1$ or that $N$ have only two digits.

(b) Give a complete list of all integers not exceeding $50$ that, relative to some base $b$, are equal to the sum of the squares of their digits.

(c) Show that for any base b the number of two-digit integers that are equal to the sum of the squares of their digits is even.

(d) Show that for any odd base $b$ there is an integer other than $1$ that is equal to the sum of the squares of its digits.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013668#p2013668]19. (CAN 5)[/url] [b](SL83-7).[/b]  Let $a$ be a positive integer and let $\{a_n\}$ be defined by $a_0 = 0$ and
\[a_{n+1 }= (a_n + 1)a + (a + 1)a_n + 2 \sqrt{a(a + 1)a_n(a_n + 1)} \qquad (n = 1, 2 ,\dots ).\]
Show that for each positive integer $n$, $a_n$ is a positive integer.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2039347#p2039347]20. (COL 1)[/url] Let $f$ and $g$ be functions from the set $A$ to the same set $A$. We define $f$ to be a functional $n$-th root of $g$ ($n$ is a positive integer) if $f^n(x) = g(x)$, where $f^n(x) = f^{n-1}(f(x)).$

[b](a)[/b] Prove that the function $g : \mathbb R  \to \mathbb R, g(x) = 1/x$ has an infinite number of $n$-th functional roots for each positive integer $n.$

[b](b)[/b] Prove that there is a bijection from $\mathbb R$ onto $\mathbb R$ that has no nth functional root for each positive integer $n.$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2039348#p2039348]21. (COL 2)[/url] Prove that there are infinitely many positive integers $n$ for which it is possible for a knight, starting at one of the squares of an $n \times n$ chessboard, to go through each of the squares exactly once.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2039349#p2039349]22. (CUB 1)[/url] Does there exist an infinite number of sets $C$ consisting of $1983$ consecutive natural numbers such that each of the numbers is divisible by some number of the form $a^{1983}$, with $a \in \mathbb N, a \neq 1 \ ?$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013677#p2013677]23. (FIN 1)[/url] [b](SL83-10).[/b] Let $p$ and $q$ be integers. Show that there exists an interval $I$ of length $1/q$ and a polynomial $P$ with integral coefficients such that
\[ \left|P(x)-\frac pq \right| < \frac{1}{q^2}\]
for all $x \in I.$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2039359#p2039359]24. (FIN 2)[/url] Every $x, 0 \leq x \leq  1$, admits a unique representation $x = \sum_{j=0}^{\infty} a_j 2^{-j}$, where all the $a_j$ belong to $\{0, 1\}$ and infinitely many of them are $0$. If $b(0) = \frac{1+c}{2+c}, b(1) =\frac{1}{2+c},c > 0$, and
\[f(x)=a_0 + \sum_{j=0}^{\infty}b(a_0) \cdots b(a_j) a_{j+1}\]
show that $0 < f(x) -x < c$ for every $x, 0 < x < 1.$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013680#p2013680](FIN 2’)[/url] [b](SL83-11)[/b] Let $f : [0, 1] \to \mathbb R$ be continuous and satisfy:
\[ \begin{array}{cc}bf(2x) = f(x),& 0 \leq x \leq 1/2;\\ f(x) = b + (1 - b)f(2x - 1), & 1/2 \leq x \leq 1,\end{array}\]
where $b = \frac{1+c}{2+c}$, $c > 0$. Show that $0 < f(x)-x < c$ for every $x, 0 < x < 1.$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2039365#p2039365]25. (FRG 1)[/url] How many permutations $a_1, a_2, \ldots, a_n$ of $\{1, 2, . . ., n \}$ are sorted into increasing order by at most three repetitions of the following operation: Move from left to right and interchange $a_i$ and $a_{i+1}$ whenever $a_i > a_{i+1}$ for $i$ running from $1$ up to $n - 1 \ ?$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2039366#p2039366]26. (FRG 2)[/url] Let $a, b, c$ be positive integers satisfying $\gcd (a, b) = \gcd (b, c) = \gcd (c, a) = 1$. Show that $2abc-ab-bc-ca$ cannot be represented as $bcx+cay +abz$ with nonnegative integers $x, y, z.$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=366618&#p366618]27. (FRG 3)[/url] [b]IMO3[/b] Let $a,b$ and $c$ be positive integers, no two of which have a common divisor greater than $1$. Show that $2abc-ab-bc-ca$ is the largest integer which cannot be expressed in the form $xbc+yca+zab$, where $x,y,z$ are non-negative integers.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2039367#p2039367]28. (GBR 1)[/url] Show that if the sides $a, b, c$ of a triangle satisfy the equation
\[2(ab^2 + bc^2 + ca^2) = a^2b + b^2c + c^2a + 3abc,\]
then the triangle is equilateral. Show also that the equation can be satisfied by positive real numbers that are not the sides of a triangle.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2039373#p2039373]29. (GBR 2)[/url] Let $O$ be a point outside a given circle. Two lines $OAB, OCD$ through $O$ meet the circle at $A,B,C,D$, where $A,C$ are the midpoints of $OB,OD$, respectively. Additionally, the acute angle $\theta$ between the lines is equal to the acute angle at which each line cuts the circle. Find $\cos \theta$  and show that the tangents at $A,D$ to the circle meet on the line $BC.$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2039376#p2039376]30. (GBR 3)[/url] Prove the existence of a unique sequence $\{u_n\} \ (n = 0, 1, 2 \ldots )$ of positive integers such that
\[u_n^2 = \sum_{r=0}^n \binom{n+r}{r} u_{n-r} \qquad \text{for all  }  n \geq 0\]

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=366613&#p366613]31. (GBR 4)[/url] [b]IMO1[/b] Find all functions $f$ defined on the set of positive reals which take positive real values and satisfy: $f(xf(y))=yf(x)$ for all $x,y$; and $f(x)\to0$ as $x\to\infty$.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2039383#p2039383]32. (GBR 5)[/url]Let $a, b, c$ be positive real numbers and let $[x]$ denote the greatest integer that does not exceed the real number $x$. Suppose that $f$ is a function defined on the set of non-negative integers $n$ and taking real values such that $f(0) = 0$ and
\[f(n) \leq an + f([bn]) + f([cn]), \qquad \text{ for all  } n \geq 1.\]
Prove that if $b + c < 1$, there is a real number $k$ such that
\[f(n) \leq  kn \qquad \text{  for all  } n \qquad (1)\]
while if $b + c = 1$, there is a real number $K$ such that $f(n) \leq  K n \log_2 n$ for all $n \geq 2$. Show that if $b + c = 1$, there may not be a real number $k$ that satisfies $(1).$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013686#p2013686]33. (GDR 1)[/url] [b](SL83-16).[/b]  Let $F(n)$ be the set of polynomials $P(x) = a_0+a_1x+\cdots+a_nx^n$, with $a_0, a_1, . . . , a_n \in \mathbb R$ and $0 \leq a_0 = a_n \leq a_1 = a_{n-1 } \leq \cdots \leq a_{[n/2] }= a_{[(n+1)/2]}.$ Prove that if  $f \in F(m)$ and $g \in  F(n)$, then $fg \in  F(m + n).$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2041514#p2041514]34. (GDR 2)[/url] In a plane are given n points $P_i \ (i = 1, 2, \ldots , n)$ and two angles $\alpha$ and $\beta$. Over each of the segments $P_iP_{i+1}  \ (P_{n+1} = P_1)$ a point $Q_i$ is constructed such that for all $i$:
(i) upon moving from $P_i$ to $P_{i+1}, Q_i$ is seen on the same side of $P_iP_{i+1}$,
(ii) $\angle P_{i+1}P_iQ_i = \alpha,$
(iii) $\angle P_iP_{i+1}Q_i = \beta.$
Furthermore, let $g$ be a line in the same plane with the property that all the points $P_i,Q_i$ lie on the same side of $g$. Prove that
\[\sum_{i=1}^n d(P_i, g)= \sum_{i=1}^n d(Q_i, g).\]
where $d(M,g)$ denotes the distance from point $M$ to line $g.$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013689#p2013689]35. (GDR 3)[/url] [b](SL83-17).[/b]  Let $P_1, P_2, \dots , P_n$ be distinct points of the plane, $n \geq  2$. Prove that
\[ \max_{1\leq i<j\leq n} P_iP_j > \frac{\sqrt 3}{2}(\sqrt n -1) \min_{1\leq i<j\leq n} P_iP_j  \]

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2041516#p2041516]36. (ISR 1)[/url] The set $X$ has $1983$ members. There exists a family of subsets $\{S_1, S_2, \ldots , S_k \}$ such that:
(i) the union of any three of these subsets is the entire set $X$, while
(ii) the union of any two of them contains at most $1979$ members. What is the largest possible value of $k ?$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2041519#p2041519]37. (ISR 2)[/url] The points $A_1,A_2, \ldots , A_{1983}$  are set on the circumference of a circle and each is given one of the values $\pm 1$. Show that if the number of points with the value $+1$ is greater than $1789$, then at least $1207$ of the points will have the property that the partial sums that can be formed by taking the numbers from them to any other point, in either direction, are strictly positive.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2041522#p2041522]38. (KUW 1)[/url] Let $\{u_n \}$ be the sequence defined by its first two terms $u_0, u_1$  and the recursion formula
\[u_{n+2 }= u_n - u_{n+1}.\]
(a) Show that $u_n$ can be written in the form $u_n = \alpha a^n + \beta b^n$, where $a, b, \alpha, \beta$ are constants independent of $n$ that have to be determined.

(b) If $S_n = u_0 + u_1 + \cdots + u_n$, prove that $S_n + u_{n-1}$ is a constant independent of $n.$ Determine this constant.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2041524#p2041524]39. (KUW 2)[/url] If $\alpha $ is the real root of the equation
\[E(x) = x^3 - 5x -50 = 0\]
such that $x_{n+1} = (5x_n + 50)^{1/3}$ and $x_1 = 5$, where $n$ is a positive integer, prove that:
[b](a)[/b] $x_{n+1}^3 - \alpha^3 = 5(x_n - \alpha)$
[b](b)[/b] $\alpha  < x_{n+1} < x_n.$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2041537#p2041537]40. (LUX 1)[/url] Four faces of tetrahedron $ABCD$ are congruent triangles whose angles form an arithmetic progression. If the lengths of the sides of the triangles are $a < b < c$, determine the radius of the sphere circumscribed about the tetrahedron as a function on $a, b$, and $c$. What is the ratio $c/a$ if $R = a \ ?$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013682#p2013682]41. (LUX 2)[/url] [b](SL83-13).[/b]  Let $E$ be the set of $1983^3$  points of the space $\mathbb R^3$ all three of whose coordinates are integers between $0$ and $1982$ (including $0$ and $1982$). A coloring of $E$ is a map from $E$ to the set {red, blue}. How many colorings of $E$ are there satisfying the following property: The number of red vertices among the $8$ vertices of any right-angled parallelepiped is a multiple of $4$ ?

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2041544#p2041544]42. (LUX 3)[/url] Consider the square $ABCD$ in which a segment is drawn between each vertex and the midpoints of both opposite sides. Find the ratio of the area of the octagon determined by these segments and the area of the square $ABCD.$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2041547#p2041547]43. (LUX 4)[/url] Given a square $ABCD$, let $P, Q, R$, and $S$ be four variable points on the sides $AB, BC, CD$, and $DA$, respectively. Determine the positions of the points $P, Q, R$, and $S$ for which the quadrilateral $PQRS$ is a parallelogram, a rectangle, a square, or a trapezoid.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2041553#p2041553]44. (LUX 5)[/url] We are given twelve coins, one of which is a fake with a different mass from the other eleven. Determine that coin with three weighings and whether it is heavier or lighter than the others.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2041554#p2041554]45. (LUX 6)[/url] Let two glasses, numbered $1$ and $2$, contain an equal quantity of liquid, milk in glass $1$ and coffee in glass $2$. One does the following: Take one spoon of mixture from glass $1$ and pour it into glass $2$, and then take the same spoon of the new mixture from glass $2$ and pour it back into the first glass. What happens after this operation is repeated $n$ times, and what as $n$ tends to infinity ?

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2041559#p2041559]46. (LUX 7)[/url] Let $f$ be a real-valued function defined on $I = (0,+\infty)$ and having no zeros on $I$. Suppose that
\[\lim_{x \to +\infty} \frac{f'(x)}{f(x)}=+\infty.\]For the sequence $u_n = \ln \left| \frac{f(n+1)}{f(n)} \right|$, prove that $u_n \to +\infty$ as $n \to  +\infty.$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2041631#p2041631]47. (NET 1)[/url] In a plane, three pairwise intersecting circles $C_1, C_2, C_3$ with centers $M_1,M_2,M_3$ are given. For $i = 1, 2, 3$, let $A_i$ be one of the points of intersection of $C_j$ and $C_k \ (\{i, j, k \} =  \{1, 2, 3 \})$. Prove that if $ \angle M_3A_1M_2 = \angle M_1A_2M_3 = \angle M_2A_3M_1 = \frac{\pi}{3}$(directed angles), then $M_1A_1, M_2A_2$, and $M_3A_3$ are concurrent.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2041721#p2041721]48. (NET 2)[/url] Prove that in any parallelepiped the sum of the lengths of the edges is less than or equal to twice the sum of the lengths of the four diagonals.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2041725#p2041725]49. (POL 1)[/url] Given positive integers $k,m, n$ with $km \leq n$ and non-negative real numbers $x_1, \ldots , x_k$, prove that
\[n (  \prod_{i=1}^k x_i^m -1 ) \leq m \sum_{i=1}^k (x_i^n-1).\]

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=366621&#p366621]50. (POL 2)[/url] [b]IMO5[/b] Is it possible to choose $1983$ distinct positive integers, all less than or equal to $10^5$, no three of which are consecutive terms of an arithmetic progression?

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013684#p2013684]51. (POL 3)[/url] [b](SL83-15).[/b]  Decide whether there exists a set $M$ of natural numbers satisfying the following conditions:

(i) For any natural numberm $>1$ there are $a, b \in M$ such that $a+b = m.$

(ii) If $a, b, c, d \in M , a, b, c, d > 10$ and $a + b = c + d$, then $a = c$ or $a = d.$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013692#p2013692]52. (ROM 1)[/url] [b](SL83-19).[/b]  Let $(F_n)_{n\geq 1} $ be the Fibonacci sequence $F_1 = F_2 = 1, F_{n+2} = F_{n+1} + F_n (n \geq 1),$ and $P(x)$ the polynomial of degree $990$ satisfying
\[ P(k) = F_k, \qquad \text{ for } k = 992,\ldots , 1982.\]
Prove that $P(1983) = F_{1983} - 1.$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2041734#p2041734]53. (ROM 2)[/url] Let $a \in \mathbb R$ and let $z_1, z_2, \ldots, z_n$ be complex numbers of modulus $1$ satisfying the relation
\[\sum_{k=1}^n z_k^3=4(a+(a-n)i)- 3 \sum_{k=1}^n \bar{z_k}\]
Prove that $a \in \{0, 1,\ldots, n \}$ and $z_k \in \{1, i \}$ for all $k.$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2012303&#p2012303]54. (ROM 3)[/url] [b]ISL 1984 P1[/b] Find all solutions of the following system of $n$ equations in $n$ variables:
\[\begin{array}{c}\  x_1|x_1| - (x_1 - a)|x_1 - a| = x_2|x_2|,x_2|x_2| - (x_2 - a)|x_2 - a| = x_3|x_3|,\ \vdots \ x_n|x_n| - (x_n - a)|x_n - a| = x_1|x_1|\end{array}\]
where $a$ is a given number.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2041738#p2041738]55. (ROM 4)[/url] For every $a \in \mathbb N$ denote by $M(a)$ the number of elements of the set
\[ \{ b \in \mathbb N | a + b \text{  is a divisor of } ab \}.\]
Find $\max_{a\leq 1983} M(a).$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2041747#p2041747]56. (ROM 5)[/url] Consider the expansion
\[(1 + x + x^2 + x^3 + x^4)^{496} = a_0 + a_1x + \cdots + a_{1984}x^{1984}.\]
[b](a)[/b] Determine the greatest common divisor of the coefficients $a_3, a_8, a_{13}, \ldots , a_{1983}.$

[b](b)[/b] Prove that $10^{340 }< a_{992} < 10^{347}.$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2041752#p2041752]57. (SPA 1)[/url] In the system of base $n^2 + 1$ find a number $N$ with $n$ different digits such that:

[b](i)[/b] $N$ is a multiple of $n$. Let $N = nN'.$

[b](ii)[/b] The number $N$ and $N'$ have the same number $n$ of different digits in base $n^2 + 1$, none of them being zero.
[b]
(iii)[/b] If $s(C)$ denotes the number in base $n^2 + 1$ obtained by applying the permutation $s$ to the $n$ digits of the number $C$, then for each permutation $s, s(N) = ns(N').$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013675#p2013675]58. (SPA 2)[/url] [b](SL83-8). [/b] In a test, $3n$ students participate, who are located in three rows of $n$ students in each. The students leave the test room one by one. If $N_1(t), N_2(t), N_3(t)$ denote the numbers of students in the first, second, and third row respectively at time $t$, find the probability that for each t during the test,
\[|N_i(t) - N_j(t)| < 2, i \neq  j, i, j = 1, 2, \dots .\]

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2041754#p2041754]59. (SPA 3)[/url] Solve the equation
\[\tan^2(2x) + 2 \tan(2x) \cdot  \tan(3x) -1 = 0.\]

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013700#p2013700]60. (SWE 1)[/url] [b](SL83-21).[/b]  Find the greatest integer less than or equal to $\sum_{k=1}^{2^{1983}} k^{\frac{1}{1983} -1}.$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2041758#p2041758]61. (SWE 2)[/url] Let $a$ and $b$ be integers. Is it possible to find integers $p$ and $q$ such that the integers $p+na$ and $q +nb$ have no common prime factor no matter how the integer $n$ is chosen.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2041844#p2041844]62. (SWE 3)[/url] $A$ circle $\gamma$ is drawn and let $AB$ be a diameter. The point $C$ on $\gamma$ is the midpoint of the line segment $BD$. The line segments $AC$ and $DO$, where $O$ is the center of $\gamma$, intersect at $P$. Prove that there is a point $E$ on $AB$ such that $P$ is on the circle with diameter $AE.$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013701#p2013701]63. (SWE 4)[/url] [b](SL83-22).[/b]  Let $n$ be a positive integer having at least two different prime factors. Show that there exists a permutation $a_1, a_2, \dots , a_n$ of the integers $1, 2, \dots , n$ such that
\[\sum_{k=1}^{n} k \cdot \cos \frac{2 \pi a_k}{n}=0.\]

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2041848#p2041848]64. (USA 1)[/url] The sum of all the face angles about all of the vertices except one of a given polyhedron is $5160$. Find the sum of all of the face angles of the polyhedron.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2041861#p2041861]65. (USA 2)[/url] Let $ABCD$ be a convex quadrilateral whose diagonals $AC$ and $BD$ intersect in a point $P$. Prove that
\[\frac{AP}{PC}=\frac{\cot \angle BAC + \cot \angle DAC}{\cot \angle BCA + \cot \angle DCA}\]

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=343813&#p343813]66. (USA 3)[/url][b]IMO6[/b] Let $ a$, $ b$ and $ c$ be the lengths of the sides of a triangle. Prove that
\[ a^{2}b(a - b) + b^{2}c(b - c) + c^{2}a(c - a)\ge 0.
\]
Determine when equality occurs.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2041862#p2041862]67. (USA 4)[/url]The altitude from a vertex of a given tetrahedron intersects the opposite face in its orthocenter. Prove that all four altitudes of the tetrahedron are concurrent.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2041866#p2041866]68. (USA 5)[/url] Three of the roots of the equation $x^4 -px^3 +qx^2 -rx+s = 0$ are $\tan A, \tan B$, and $\tan C$, where $A, B$, and $C$ are angles of a triangle. Determine the fourth root as a function only of $p, q, r$, and $s.$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=366615&#p366615]69. (USS 1)[/url][b]IMO2[/b] Let $A$ be one of the two distinct points of intersection of two unequal coplanar circles $C_1$ and $C_2$ with centers $O_1$ and $O_2$ respectively. One of the common tangents to the circles touches $C_1$ at $P_1$ and $C_2$ at $P_2$, while the other touches $C_1$ at $Q_1$ and $C_2$ at $Q_2$. Let $M_1$ be the midpoint of $P_1Q_1$ and $M_2$ the midpoint of $P_2Q_2$. Prove that $\angle O_1AO_2=\angle M_1AM_2$.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013703#p2013703]70. (USS 2)[/url] [b](SL83-24). [/b] Let $d_n$ be the last nonzero digit of the decimal representation of $n!$. Prove that $d_n$ is aperiodic; that is, there do not exist $T$ and $n_0$ such that for all $n \geq n_0, d_{n+T} = d_n.$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2013705#p2013705]71. (USS 3)[/url] [b](SL83-25).[/b]  Prove that every partition of $3$-dimensional space into three disjoint subsets has the following property: One of these subsets contains all possible distances; i.e., for every $a \in \mathbb R^+$, there are points $M$ and $N$ inside that subset such that distance between $M$ and $N$ is exactly $a.$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2041872#p2041872]72. (USS 4)[/url] Prove that for all $x_1, x_2,\ldots , x_n \in \mathbb R$ the following inequality holds:
\[\sum_{n \geq i >j \geq 1} \cos^2(x_i - x_j ) \geq \frac{n(n-2)}{4}.\]

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2041939#p2041939]73. (VIE 1)[/url] Let $ABC$ be a nonequilateral triangle. Prove that there exist two points $P$ and $Q$ in the plane of the triangle, one in the interior and one in the exterior of the circumcircle of $ABC$, such that the orthogonal projections of any of these two points on the sides of the triangle are vertices of an equilateral triangle.

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2041947#p2041947]74. (VIE 2)[/url] In a plane we are given two distinct points $A,B$ and two lines $a, b$ passing through $B$ and $A$ respectively $(a  \ni  B, b  \ni A)$ such that the line $AB$ is equally inclined to a and b. Find the locus of points $M$ in the plane such that the product of distances from $M$ to $A$ and a equals the product of distances from $M$ to $B$ and $b$ (i.e., $MA \cdot  MA' = MB \cdot MB'$, where $A'$ and $B'$ are the feet of the perpendiculars from $M$ to $a$ and $b$ respectively).

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2041952#p2041952]75. (VIE 3)[/url] Find the sum of the fiftieth powers of all sides and diagonals of a regular $100$-gon inscribed in a circle of radius $R.$