IMO Marathon

Discussion on International Mathematical Olympiad (IMO)
User avatar
ahmedittihad
Posts: 181
Joined: Mon Mar 28, 2016 6:21 pm

Re: IMO Marathon

Unread post by ahmedittihad » Sun Aug 28, 2016 8:03 pm

We can't save any units on the outside of the grid. So, we better fill them with triangles. The problem reduces to a 98*98 grid for which we could ignore the outside edges. We notice that out of any 2*1 grid, we must have one unit with a triangle. So there are at least 98*98/2=4802 units filled with triangles. We have 4802 free units left! Let us save them :D. We now show a construction that saves 4802 units. CHESSBOARD the 98*98.
Frankly, my dear, I don't give a damn.

User avatar
ahmedittihad
Posts: 181
Joined: Mon Mar 28, 2016 6:21 pm

Re: IMO Marathon

Unread post by ahmedittihad » Sun Aug 28, 2016 8:47 pm

$\boxed{\text{Problem 48}}$ Prove that, for any positive integer set $\{a_1,a_2,...,a_n\}$ there exists a positive integer $b$ such that the set $\{ba_1,ba_2,...,ba_n\}$ consists of perfect powers.
Source -Number Theory Structures examples and problems.
Frankly, my dear, I don't give a damn.

Nirjhor
Posts: 136
Joined: Thu Aug 29, 2013 11:21 pm
Location: Varies.

Re: IMO Marathon

Unread post by Nirjhor » Tue Aug 30, 2016 8:03 pm

Solution $\boxed{48}$
Suppose $\displaystyle a_i = \prod_{j=1}^k p_j^{e_{i_j}}$ for each $1\le i\le n.$ Take $n$ distinct primes $d_1,d_2,...,d_n.$ Then we can take $b=\displaystyle\prod_{j=1}^k p_j^{\alpha_j}$ where $\alpha_j+e_{i_j}\equiv 0~(\bmod~d_i)~$ for each $1\le j \le k$ and $1\le i\le n$. Such a sequence $\alpha_1,\alpha_2,...,\alpha_k$ exists due to CRT. $\square$
Problem $\boxed{49}$

Is it possible to write $\dbinom n 2$ consecutive natural numbers on the edges of $K_n$ such that for every path or cycle of length $3$, if the numbers written on the $3$ edges are $a,b,c$ then $\gcd(a,c)\mid b$ is satisfied? In case of a path, the edge $b$ lies between the edges $a$ and $c$.

Source: some Iran TST.
- What is the value of the contour integral around Western Europe?

- Zero.

- Why?

- Because all the poles are in Eastern Europe.


Revive the IMO marathon.

User avatar
asif e elahi
Posts: 183
Joined: Mon Aug 05, 2013 12:36 pm
Location: Sylhet,Bangladesh

Re: IMO Marathon

Unread post by asif e elahi » Sat Sep 03, 2016 12:54 pm

Nirjhor wrote: Problem $\boxed{49}$

Is it possible to write $\dbinom n 2$ consecutive natural numbers on the edges of $K_n$ such that for every path or cycle of length $3$, if the numbers written on the $3$ edges are $a,b,c$ then $\gcd(a,c)\mid b$ is satisfied? In case of a path, the edge $b$ lies between the edges $a$ and $c$.

Source: some Iran TST.
I split the problem into $2$ cases.
Case $1$: $\dfrac{n(n-1)}{2}$ is even
Consider the two edges which have $\dfrac{n(n-1)}{2}$ and $\dfrac{n(n-1)}{4}$ written on them. Take another edge which connects both of them. Easy to see that such an edge always exist. Now the number written on that edge must be divisible by $gcd(\dfrac{n(n-1)}{2},\dfrac{n(n-1)}{4})=\dfrac{n(n-1)}{4}$. But $\dfrac{n(n-1)}{4}$ and $\dfrac{n(n-1)}{2}$ are the only numbers which are less or equal to $\dfrac{n(n-1)}{2}$ and divisible by $\dfrac{n(n-1)}{4}$ unless $\dfrac{n(n-1)}{4}=1$. This gives us no solution.

Case $2$: $\dfrac{n(n-1)}{2}$ is odd
Take the edges with numbers $\dfrac{n(n-1)}{2}-1$ and $\dfrac{\dfrac{n(n-1)}{2}-1}{2}$. Also take an edge which connects them. Now the number written on it must be multiple of $\dfrac{\dfrac{n(n-1)}{2}-1}{2}$. Using a similar argument as the previous case, we can show that $\dfrac{\dfrac{n(n-1)}{2}-1}{2}$ must be equal to $1$.
However this gives us a solution $n=3$.

Nirjhor
Posts: 136
Joined: Thu Aug 29, 2013 11:21 pm
Location: Varies.

Re: IMO Marathon

Unread post by Nirjhor » Sat Sep 03, 2016 3:56 pm

The $\dbinom n 2$ consecutive natural numbers don't necessarily have to be the first $\dbinom n 2$ natural numbers.
- What is the value of the contour integral around Western Europe?

- Zero.

- Why?

- Because all the poles are in Eastern Europe.


Revive the IMO marathon.

Nirjhor
Posts: 136
Joined: Thu Aug 29, 2013 11:21 pm
Location: Varies.

Re: IMO Marathon

Unread post by Nirjhor » Sun Sep 04, 2016 3:29 am

Solution $\boxed{49}$
The key fact is that for any positive integer $d$ the set of edges divisible by $d$ forms a clique. Indeed, for any positive integer $d$ if there's only one edge divisible by $d$ then it's an induced $K_1$. Otherwise take two edges $\alpha d$ and $\beta d$. For any edge $\gamma$ that connects these two edges satisfies $d\mid\gcd(\alpha d,\beta d)\mid \gamma$. So the number of edges divisible by some positive integer $d$ is a triangular number.

Now consider the set of edges divisible by $d=\dfrac 1 p \dbinom n 2$ where $p$ is a prime divisor of $\dbinom n 2$. Since we have $\dbinom n 2$ consecutive natural numbers, the number of integers divisible by $d$ in this range is $p$. So $p$ must be a triangular number by the above reasoning. The only prime triangular number is $p=3$. Thus $\dbinom n 2$ must be a power of $3$, leading us to $n\in\{2,3\}$.

For $n=2$ take any positive integer $t$.
For $n=3$ take $t-1,~t,~t+1$ where $t$ is an even positive integer. $\square$
Someone post the next problem.
- What is the value of the contour integral around Western Europe?

- Zero.

- Why?

- Because all the poles are in Eastern Europe.


Revive the IMO marathon.

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

Re: IMO Marathon

Unread post by rah4927 » Sat Jan 07, 2017 6:24 pm

$\text{Problem }50$

In every $1\times1$ square of an $m\times n$ table we have drawn one of two diagonals. Prove that there is a path including these diagonals either from left side to the right side, or from the upper side to the lower side.

Source: Iran TST $2010$

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

Re: IMO Marathon

Unread post by rah4927 » Wed Feb 01, 2017 10:34 pm

$\text{Solution to Problem } 50$

A solution can be found following this link : https://artofproblemsolving.com/communi ... 58p1871421

$\text{Problem } 51$

Let $A$ be a set of $N$ residues $\pmod{N^{2}}$. Prove that there exists a set $B$ of of $N$ residues $\pmod{N^{2}}$ such that $A + B = \{a+b|a \in A, b \in B\}$ contains at least half of all the residues $\pmod{N^{2}}$

Nirjhor
Posts: 136
Joined: Thu Aug 29, 2013 11:21 pm
Location: Varies.

Re: IMO Marathon

Unread post by Nirjhor » Sat Feb 04, 2017 2:48 am

Solution $\boxed{51}$
Screams probabilistic approach. Take a random set $B$. Clearly $|A+B|=N^2$, we let $X$ to be the number of distinct elements in $A+B$. For some fixed residue $r$ we have $N$ possible elements to complement with an element from $A$, precisely $r-A_i$ for $1\le i\le N$. So the probability that $r$ appears in $B$ is $1-\left(\dfrac{N^2-N}{N^2}\right)^N$. And by linearity of expectation
\[\mathbb E(X) = N^2\left(1-\left(\dfrac{N^2-N}{N^2}\right)^N\right)= N^2\left(1-\left(1-\dfrac{1}{N}\right)^N\right) .\]
We can check that $\left(1-\dfrac{1}{N}\right)^N$ is increasing in $(1,\infty)$ by checking that the derivative is always positive in that interval. So
\[ \left(1-\dfrac{1}{N}\right)^N < \lim_{N\to\infty} \left(1-\dfrac{1}{N}\right)^N =e^{-1}.\]
And thus
\[ \mathbb E(X) = N^2\left(1-\left(1-\dfrac{1}{N}\right)^N\right) > N^2\left(1-e^{-1}\right).\]
The fact that $1-e^{-1} \ge 0.5\Leftrightarrow e\ge 2$ is left as an exercise. $\square$
Problem $\boxed{52}$

Find all pairs $(f,g)$ of functions from $\mathbb R$ to $\mathbb R$ that satisfy
\[g(f(x+y))= f(x) +(2x+y)g(y)\] for all $(x,y)\in \mathbb R^2$.
- What is the value of the contour integral around Western Europe?

- Zero.

- Why?

- Because all the poles are in Eastern Europe.


Revive the IMO marathon.

Nirjhor
Posts: 136
Joined: Thu Aug 29, 2013 11:21 pm
Location: Varies.

Re: IMO Marathon

Unread post by Nirjhor » Mon Feb 06, 2017 7:45 pm

Solution $\boxed{52}$
Let $P(x,y)$ denote $g(f(x+y))=f(x)+(2x+y)g(y)$.

If $g$ is constant then setting $g\equiv c$ we see that $f(x)=(1-2x-y)c$ for all $(x,y)\in\mathbb R^2$, implying $c=0$. So $f\equiv 0$ and $g\equiv 0$. This pair satisfies the equation. We now assume that $g$ is non-constant.

Suppose $s=f(0)$ and $t=g(0)$.
\[\begin{eqnarray}
P(x,0)~&\Rightarrow &~g(f(x)) = f(x) + 2xt, ~~~~~ &(1) \\
P(0,x)~ &\Rightarrow &~g(f(x)) =s + xg(x). ~~~~~ &(2)\\
\end{eqnarray}\]
Combining $(1)$ and $(2)$ we have
\[\begin{eqnarray}
f(x)=x(g(x)-2t)+s. ~~~~~ &(3)
\end{eqnarray}\]
Then
\[\begin{eqnarray}
P(x,y)~&\Rightarrow &~g(f(x+y))=x(g(x)-2t)+s+(2x+y)g(y), ~~~~~ &(4) \\
P(y,x)~&\Rightarrow &~g(f(x+y)) = y(g(y)-2t)+s+(2y+x)g(x). ~~~~~ &(5)\\
\end{eqnarray}\]
Combining $(4)$ and $(5)$ and simplifying we get \[x(g(y)-t) = y(g(x)-t).\] Setting $y=1$ above we see that $g$ is linear. So $g(x)=ax+t$ for $a\neq 0$. Plugging into $(3)$ we find
\[f(x)=x(g(x)-2t)+s= ax^2-tx+s\]
where $a\neq 0$.
Finally, plugging these into $(2)$ we have
\[ax^2+tx+s=g(f(x))=af(x)+t=a^2x^2-atx+as.\]
Equating coefficients, we have $a^2=a\Rightarrow a=1$, and $t=-t\Rightarrow t=0$. So $g(x)=x$ and $f(x)=x^2+s$. It's easy to check that this pair satisfies the original equation.

So we have two pairs of functions: $f\equiv 0, ~g\equiv 0$ and $f(x)=x^2+f(0), ~g(x)=x$. $\square$
Someone post the next problem.
- What is the value of the contour integral around Western Europe?

- Zero.

- Why?

- Because all the poles are in Eastern Europe.


Revive the IMO marathon.

Post Reply