Page 18 of 19

### Re: IMO Marathon

Posted: 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 . We now show a construction that saves 4802 units. CHESSBOARD the 98*98.

### Re: IMO Marathon

Posted: 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.

### Re: IMO Marathon

Posted: Tue Aug 30, 2016 8:03 pm
Solution $\boxed{48}$
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.

### Re: IMO Marathon

Posted: 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$.

### Re: IMO Marathon

Posted: 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.

### Re: IMO Marathon

Posted: Sun Sep 04, 2016 3:29 am
Solution $\boxed{49}$
Someone post the next problem.

### Re: IMO Marathon

Posted: 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$

### Re: IMO Marathon

Posted: 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}}$

### Re: IMO Marathon

Posted: Sat Feb 04, 2017 2:48 am
Solution $\boxed{51}$
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$.

### Re: IMO Marathon

Posted: Mon Feb 06, 2017 7:45 pm
Solution $\boxed{52}$
Someone post the next problem.