IMO Marathon

Discussion on International Mathematical Olympiad (IMO)
tanmoy
Posts: 289
Joined: Fri Oct 18, 2013 11:56 pm
Location: Rangpur,Bangladesh

Re: IMO Marathon

Unread post by tanmoy » Tue Aug 16, 2016 11:48 am

asif e elahi wrote:$\textbf{Problem} \text{ }\boxed{41}$ FInd all primes $p$ for which there exists $n\in \mathbb{N}$ so that
$$
p|n^{n+1}-(n+1)^n
$$
This is true for all odd prime $p$.Take $n=(p-1)^{2}$
"Questions we can't answer are far better than answers we can't question"

rah4927
Posts: 108
Joined: Sat Feb 07, 2015 9:47 pm

Re: IMO Marathon

Unread post by rah4927 » Fri Aug 19, 2016 2:02 pm

Problem ${42}$

The number $N$ is the product of $k$ different primes ($k \ge 3$). A and B take turns writing composite divisors of $N$ on a board, according to the following rules. One may not write $N$. Also, there may never appear two coprime numbers or two numbers, one of which divides the other. The first player unable to move loses. If $A$ starts, who has the winning strategy?

Source: St.Petersburg 1997

tanmoy
Posts: 289
Joined: Fri Oct 18, 2013 11:56 pm
Location: Rangpur,Bangladesh

Re: IMO Marathon

Unread post by tanmoy » Fri Aug 19, 2016 3:50 pm

Too easy.
$A$ has a winning strategy.First,$A$ can write $pq$,where $p$ and $q$ are distinct prime divisors of $N$.The next numbers should be of the forms $pn$ ar $qn$ where $n > 1$ and $(n,pq)=1$.If $B$ writes $pn$,$A$ will write $qn$ and vice versa.Continuing like this,$A$ will eventually win.
"Questions we can't answer are far better than answers we can't question"

rah4927
Posts: 108
Joined: Sat Feb 07, 2015 9:47 pm

Re: IMO Marathon

Unread post by rah4927 » Fri Aug 19, 2016 4:23 pm

tanmoy wrote:Too easy.
$A$ has a winning strategy.First,$A$ can write $pq$,where $p$ and $q$ are distinct prime divisors of $N$.The next numbers should be of the forms $pn$ ar $qn$ where $n > 1$ and $(n,pq)=1$.If $B$ writes $pn$,$A$ will write $qn$ and vice versa.Continuing like this,$A$ will eventually win.
You are also supposed to provide the next problem.

$\textbf{Problem}$ $\boxed{43}$ There are $n$ points in the plane such that no three of them are
collinear. Prove that the number of triangles, whose vertices are chosen from these n points and
whose area is $1$, is not greater than $\dfrac23(n^2-n)$ .

Source: Iran

tanmoy
Posts: 289
Joined: Fri Oct 18, 2013 11:56 pm
Location: Rangpur,Bangladesh

Re: IMO Marathon

Unread post by tanmoy » Fri Aug 19, 2016 8:25 pm

rah4927 wrote:$\textbf{Problem}$ $\boxed{43}$ There are $n$ points in the plane such that no three of them are
collinear. Prove that the number of triangles, whose vertices are chosen from these n points and
whose area is $1$, is not greater than $\dfrac23(n^2-n)$ .

Source: Iran
Let the number of such triangles satisfying problem condition be $k$.For each edge between two points in the set,we counted the number of triangles which have it as an edge.Let the total number over all edges be $T$.

There are $\dbinom {n} {2}$ edges.For any edge $AB$,we can find at most $4$ triangles of equal area with $AB$ as an edge.So,$T \leq 4\dbinom{n}{2}$.........................(i)

On the other hand,each triangle has $3$ edges.So,$T \geq 3k$....................(ii)

From (i) and (ii),we get that $k \leq \dfrac {T} {3} \leq \dfrac {4} {3}\dbinom{n}{2}=\dfrac {2} {3} (n^{2}-n)$
Last edited by tanmoy on Fri Aug 19, 2016 8:35 pm, edited 2 times in total.
"Questions we can't answer are far better than answers we can't question"

tanmoy
Posts: 289
Joined: Fri Oct 18, 2013 11:56 pm
Location: Rangpur,Bangladesh

Re: IMO Marathon

Unread post by tanmoy » Fri Aug 19, 2016 8:30 pm

$\boxed{\textbf{Problem 44}}:$Let $k$ be a nonzero natural number and $m$ an odd natural number.Prove that there exists a natural number $n$ such that the number $m^{n}+n^{m}$ has at least $k$ distinct prime factors.

$\textbf{Source}:$ Romania TST $2014$
"Questions we can't answer are far better than answers we can't question"

rah4927
Posts: 108
Joined: Sat Feb 07, 2015 9:47 pm

Re: IMO Marathon

Unread post by rah4927 » Sat Aug 20, 2016 8:56 pm

tanmoy wrote:$\boxed{\textbf{Problem 44}}:$Let $k$ be a nonzero natural number and $m$ an odd natural number.Prove that there exists a natural number $n$ such that the number $m^{n}+n^{m}$ has at least $k$ distinct prime factors.

$\textbf{Source}:$ Romania TST $2014$
My solution uses a useful idea that is handy in increasing the number of prime factors of this type of expression.

$\textbf{Lemma:}$ $a^{p^k}+b^{p^k}$, where $p$ is an odd prime , has at least $k$ distinct prime factors.

$\textbf{Proof:}$ Take out all the common divisors of $a$ and $b$ and assume that $(a,b)=1$. Inducting on $k$, we get that $a^{p^k}+b^{p^k}$ has at least $k-1$ distinct prime factors since $a^{p^{k-1}}+b^{p^{k-1}}|a^{p^k}+b^{p^k}$ . So it suffices to prove that $G=\left(\dfrac{a^{p^k}+b^{p^k}}{a^{p^{k-1}}+b^{p^{k-1}}},a^{p^{k-1}}+b^{p^{k-1}}\right)=1$. This is true since $\left(\dfrac{a^n+b^n}{a+b},a+b\right)|n$ , where $n$ is odd and $(a,b)=1$. Since $G|p$, but $\dfrac{a^{p^k}+b^{p^k}}{a^{p^{k-1}}+b^{p^{k-1}}}$ is greater than $p$, so it must have another prime factor different from $p$ and we are done.

Now, let $n=p^{p^k}$ for some prime not dividing $m$ and we are done.

$\boxed{\textbf{Problem 45}}$ The isosceles triangle $\triangle ABC$, with $AB=AC$, is inscribed in the circle $\omega$. Let $P$ be a variable point on the arc $\stackrel{\frown}{BC}$ that does not contain $A$, and let $I_B$ and $I_C$ denote the incenters of triangles $\triangle ABP$ and $\triangle ACP$, respectively.

Prove that as $P$ varies, the circumcircle of triangle $\triangle PI_BI_C$ passes through a fixed point.

Source: USAJMO

User avatar
nahin munkar
Posts: 81
Joined: Mon Aug 17, 2015 6:51 pm
Location: banasree,dhaka

Re: IMO Marathon

Unread post by nahin munkar » Sun Aug 21, 2016 2:41 am

rah4927 wrote: $\boxed{\textbf{Problem 45}}$ The isosceles triangle $\triangle ABC$, with $AB=AC$, is inscribed in the circle $\omega$. Let $P$ be a variable point on the arc $\stackrel{\frown}{BC}$ that does not contain $A$, and let $I_B$ and $I_C$ denote the incenters of triangles $\triangle ABP$ and $\triangle ACP$, respectively.

Prove that as $P$ varies, the circumcircle of triangle $\triangle PI_BI_C$ passes through a fixed point.

Source: USAJMO
OK.Here is my solution:
By scaled diagram, we let $ M_A $ is the fixed point where $ M_A $ is the midpoint of arc $ \stackrel{\frown}{BC} $. We extend $ M_AP $ to $ L $ & $ I_CP $ to $ K $. As, $ PA $ bisects $ \angle I_BPI_C $ & $ \triangle APM_A $ is right angled (get from ABC is isosceles & $ M_A $ is midpoint of arc $ BC $),we get $ \angle I_BPL= \angle KPL $. So,$ M_AP $ bisects $\angle I_BPI_C $ externally...(1).

Now,we define two points $ M_B $ , $ M_C $ as the midpoint of arc $ AC,AB $ resp. Here,$ P,I_C,M_B $ & $ P,I_B,M_C $ both collinear from well-known incenter lemma. Now we get again using it, $ M_BI_C=M_BA=M_CA=M_CI_B $...@. & It's obvious that, $ M_AM_B=M_AM_C $...(b). & it can be seen easily, $ \angle M_AM_CI_B = \angle M_AM_BI_C $....(c). SO,from @,(b),(c), $ \triangle M_AM_CI_B \cong \triangle M_AM_BI_C $ . So, $ M_AI_B=M_AI_C. $ From (1), we get, $ M_A $ is the midpoint of arc $ I_BI_C $ of $ \bigodot PI_BI_C $ (here just the angle is externally bisected of a well-known lemma).Now, we can conclude as $ M_A $ lies on the circle. SO, $ \bigodot PI_BI_C $ passes through a fixed point .....(proved) :mrgreen:
# Mathematicians stand on each other's shoulders. ~ Carl Friedrich Gauss

rah4927
Posts: 108
Joined: Sat Feb 07, 2015 9:47 pm

Re: IMO Marathon

Unread post by rah4927 » Sun Aug 21, 2016 3:10 pm

$\boxed{\textbf{Problem 46}}$ Let $\leftarrow$ denote the left arrow key on a standard keyboard. If one opens a text editor and types the keys "ab$\leftarrow$ cd $\leftarrow \leftarrow$ e $\leftarrow \leftarrow$ f", the result is "faecdb". We say that a string $B$ is reachable from a string $A$ if it is possible to insert some amount of $\leftarrow$'s in $A$, such that typing the resulting characters produces $B$. So, our example shows that "faecdb" is reachable from "abcdef".

Prove that for any two strings $A$ and $B$, $A$ is reachable from $B$ if and only if $B$ is reachable from $A$.

Source : USA TSTST

rah4927
Posts: 108
Joined: Sat Feb 07, 2015 9:47 pm

Re: IMO Marathon

Unread post by rah4927 » Sun Aug 28, 2016 12:56 am

I will apply induction on the length of the string, and leave some of the finer details to the reader.

Let's just do one case. Take $n=6$ (i.e. the string $123456$). Now let's randomly put some arrow signs inside, and try to apply the algorithm. The essence of this solution lies in knowing precisely how one can execute the algorithm efficiently.

\[12\underbrace{\leftarrow 34\leftarrow \leftarrow 5 \leftarrow \leftarrow 6}\]

\[1|\: \underbrace{34\leftarrow \leftarrow 5 \leftarrow \leftarrow 6}|\: 2\]

This was the first step of our algorithm. See what we did here ? We picked the leftmost arrow, and implemented that first. If you have spent some time with the problem, it should be obvious that repeatedly doing this will result in our final expression.

\[1|\: 5 \leftarrow \leftarrow 6 |\: 34|\: 2\]

\[6|\:1|\:5|\:34|\:2\]

Now, it is essential to note that when we apply one step of this algorithm, we take some "block" of the string and shift it entirely to the left. Consider the first step of the algorithm again.

\[12\underbrace{\leftarrow 34\leftarrow \leftarrow 5 \leftarrow \leftarrow 6}\]

\[1|\: \underbrace{34\leftarrow \leftarrow 5 \leftarrow \leftarrow 6}|\: 2\]

Here, we took the $\leftarrow 34\leftarrow \leftarrow 5 \leftarrow \leftarrow 6$ block and shifted it to the left. This left $2$ (which was originally on the left) on the extreme right side of the string. Can you now see why $2$ will always be to the extreme right of the string in the subsequent steps ? Since our algorithm always shifts some block to the left, $2$ is never going to be bothered to move again. So now, haven't we reduced our algorithm to a string of length $5$ ? Can you see why induction is now pretty obvious ? Of course, you will need to use strong induction, since the block that moves to the extreme right of the string may not be of size $1$, like in our case. As I said, the finer details are left to the reader.

In general, when you have to execute really hairy algorithms, it is always worth taking the time to find out a "doable" way to execute the algorithm fast on paper - it helps in experimentation, if nothing else. Lucky for me, the algorithm yielded the solution.
$\boxed{\text{Problem 47}}$ In a $100\times 100$ board, you put right angled isosceles triangles in some unit squares, such that every side (including the ones on the boundary) of each unit square is a leg of some isosceles triangle. What is the maximum number of unit squares with no triangles ?

Source : ARO (not sure)
Last edited by rah4927 on Sun Aug 28, 2016 8:52 pm, edited 2 times in total.

Post Reply