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

by ahmedittihad

$\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

by Nirjhor

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.

Re: IMO Marathon

Posted: Sat Sep 03, 2016 12:54 pm

by asif e elahi

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

by Nirjhor

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

by Nirjhor

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.

Re: IMO Marathon

Posted: Sat Jan 07, 2017 6:24 pm

by rah4927

$\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.

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

by Nirjhor

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

Re: IMO Marathon

Posted: Mon Feb 06, 2017 7:45 pm

by Nirjhor

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$