Some of my personal favourites

by navi_09220114, Nov 15, 2023, 5:27 PM

I have been creating proposals for the past 4-5 years now, and I would like to make a small collection of my own favourites here. Hope you (the reader) will like them

Algebra:

1. Find all functions $f : \mathbb{R} \rightarrow \mathbb{R}$ such that for all real numbers $x, y$ $f(x^2+f(y))=f(f(y)-x^2)+f(xy)$
[It was restricted to continuous functions in the actual test to lower its difficulty, but it can be solved in more generality]

2. A sequence of reals $a_1, a_2, \cdots$ satisfies for all $m>1$ , $a_{m+1}a_{m-1}=a_m^2-a_1^2$ Prove that for all $m>n>1$ , the sequence satisfies the equation $a_{m+n}a_{m-n}=a_m^2-a_n^2$
3. For each integer $k\geq 2$ , determine all infinite sequences of positive integers $a_1$ , $a_2$ , $\ldots$ for which there exists a polynomial $P$ of the form $P(x)=x^k+c_{k-1}x^{k-1}+\dots + c_1 x+c_0,$ where $c_0$ , $c_1$ , $\dots$ , $c_{k-1}$ are non-negative integers, such that $P(a_n)=a_{n+1}a_{n+2}\cdots a_{n+k}$
Combinatorics

1. Let $a_1,a_2,\cdots$ be a strictly increasing sequence on positive integers.

Is it always possible to partition the set of natural numbers $\mathbb{N}$ into infinitely many subsets with infinite cardinality $A_1,A_2,\cdots$ , so that for every subset $A_i$ , if we denote $b_1<b_2<\cdots$ be the elements of $A_i$ , then for every $k\in \mathbb{N}$ and for every $1\le i\le a_k$ , it satisfies $b_{i+1}-b_{i}\le k$ ?

2. Let $\mathcal{S}$ be a set of $2023$ points in a plane, and it is known that the distances of any two different points in $S$ are all distinct. Ivan colors the points with $k$ colors such that for every point $P \in \mathcal{S}$ , the closest and the furthest point from $P$ in $\mathcal{S}$ also have the same color as $P$ .

What is the maximum possible value of $k$ ?

3. Ivan is playing Lego with $4n^2$ $1 \times 2$ blocks. First, he places $2n^2$ $1 \times 2$ blocks to fit a $2n \times 2n$ square as the bottom layer. Then he builds the top layer on top of the bottom layer using the remaining $2n^2$ $1 \times 2$ blocks. Note that the blocks in the bottom layer are connected to the blocks above it in the top layer, just like real Lego blocks. He wants the whole two-layered building to be connected and not in seperate pieces.

Prove that if he can do so, then the four $1\times 2$ blocks connecting the four corners of the bottom layer, must be all placed horizontally or all vertically.

4. Let $k$ be a fixed integer. In the town of Ivanland, there are at least $k+1$ citizens standing on a plane such that the distances between any two citizens are distinct. An election is to be held such that every citizen votes the $k$ -th closest citizen to be the president. What is the maximal number of votes a citizen can have?

5. Given two positive integers $m$ and $n$ , find the largest $k$ in terms of $m$ and $n$ such that the following condition holds:

Any tree graph $G$ with $k$ vertices has two (possibly equal) vertices $u$ and $v$ such that for any other vertex $w$ in $G$ , either there is a path of length at most $m$ from $u$ to $w$ , or there is a path of length at most $n$ from $v$ to $w$ .

Geometry:

1. Given an acute triangle $ABC$ , mark $3$ points $X, Y, Z$ in the interior of the triangle. Let $X_1, X_2, X_3$ be the projections of $X$ to $BC, CA, AB$ respectively, and define the points $Y_i, Z_i$ similarly for $i=1, 2, 3$ .

a) Suppose that $X_iY_i<X_iZ_i$ for all $i=1,2,3$ , prove that $XY<XZ$ .

b) Prove that this is not neccesarily true, if triangle $ABC$ is allowed to be obtuse.

2. Given a triangle $ABC$ with $AB=AC$ and circumcenter $O$ . Let $D$ and $E$ be midpoints of $AC$ and $AB$ respectively, and let $DE$ intersect $AO$ at $F$ . Denote $\omega$ to be the circle $(BOE)$ . Let $BD$ intersect $\omega$ again at $X$ and let $AX$ intersect $\omega$ again at $Y$ .

Suppose the line parallel to $AB$ passing through $O$ meets $CY$ at $Z$ . Prove that the lines $FX$ and $BZ$ meet at $\omega$ .

3. Let triangle $ABC$ with $AB<AC$ has orthocenter $H$ , and let the midpoint of $BC$ be $M$ . The internal angle bisector of $\angle BAC$ meet $CH$ at $X$ , and the external angle bisector of $\angle BAC$ meet $BH$ at $Y$ . The circles $(BHX)$ and $(CHY)$ meet again at $Z$ .

Prove that $\angle HZM=90^{\circ}$ .

4. Let $ABC$ be an acute triangle with $AB\neq AC$ . Let $D, E, F$ be the midpoints of the sides $BC$ , $CA$ , and $AB$ respectively, and $M, N$ be the midpoints of minor arc $BC$ not containing $A$ and major arc $BAC$ respectively. Suppose $W, X, Y, Z$ are the incenter, $D$ -excenter, $E$ -excenter, and $F$ -excenter of triangle $DEF$ respectively.

Prove that the circumcircles of the triangles $ABC$ , $WNX$ , $YMZ$ meet at a common point.

Number Theory:

1. Given a natural number $n$ , call a divisor $d$ of $n$ to be $\textit{nontrivial}$ if $d>1$ . A natural number $n$ is $\textit{good}$ if one or more distinct nontrivial divisors of $n$ sum up to $n-1$ .

Prove that every natural number $n$ has a multiple that is good.

2. Given a four digit string $k=\overline{abcd}$ , $a, b, c, d\in \{0, 1, \cdots, 9\}$ , prove that there exist a $n<20000$ such that $2^n$ contains $k$ as a substring when written in base $10$ .

3. Find all polynomials with integer coefficients $P$ such that for all positive integers $n$ , the sequence $0, P(0), P(P(0)), \cdots$ is eventually constant modulo $n$ .

This post has been edited 2 times. Last edited by navi_09220114, Nov 15, 2023, 5:29 PM

14/3/2022: Some of my own problems so far in BIMOs

by navi_09220114, Mar 13, 2022, 5:44 PM

So I have been teaching the IMO camps since 2020 :>

and here are some of the problems i created, some sucks, some are nice i think, but none of them are hard enough :v

.................................................................................................................

IMO 2020 Final Training

1. Find all functions $f : \mathbb{R} \rightarrow \mathbb{R}$ such that for all reals $x, y$ , $f(x^2+f(x+y))=y+xf(x+1)$ 2. Let $a_1,a_2,\cdots$ be a strictly increasing sequence on positive integers.

Is it always possible to partition the set of natural numbers $\mathbb{N}$ into infinitely many subsets with infinite cardinality $A_1,A_2,\cdots$ , so that for every subset $A_i$ , if we denote $b_1<b_2<\cdots$ be the elements of $A_i$ , then for every $k\in \mathbb{N}$ and for every $1\le i\le a_k$ , it satisfies $b_{i+1}-b_{i}\le k$ ?

3. Let $G$ be the centroid of a triangle $\triangle ABC$ and let $AG, BG, CG$ meet its circumcircle at $P, Q, R$ respectively. Let $AD, BE, CF$ be the altitudes of the triangle.

Prove that the radical center of circles $(DQR),(EPR),(FPQ)$ lies on Euler Line of $\triangle ABC$ .

.................................................................................................................

BIMO 2021

1. Find all continuous functions $f : \mathbb{R} \rightarrow \mathbb{R}$ such that for all real numbers $x, y$ $f(x^2+f(y))=f(f(y)-x^2)+f(xy)$ [Extra: Try solve this without continuity!]

2. There are $k$ piles of stones with $2020$ stones in each pile. Amber can choose any two non-empty piles of stones, and Barbara can take one stone from one of the two chosen piles and puts it into the other pile. Amber wins if she can eventually make an empty pile. What is the least $k$ such that Amber can always win?

3. Let $ABC$ be an actue triangle with $AB<AC$ . Let $\Gamma$ be its circumcircle, $I$ its incenter and $P$ is a point on $\Gamma$ such that $\angle API=90^{\circ}$ . Let $Q$ be a point on $\Gamma$ such that $QB\cdot\tan \angle B=QC\cdot \tan \angle C$ Consider a point $R$ such that $PR$ is tangent to $\Gamma$ and $BR=CR$ . Prove that the points $A, Q, R$ are colinear.

4. Given a natural number $n$ , call a divisor $d$ of $n$ to be $\textit{nontrivial}$ if $d>1$ . A natural number $n$ is $\textit{good}$ if one or more distinct nontrivial divisors of $n$ sum up to $n-1$ .

Prove that every natural number $n$ has a multiple that is good.

5. Let $ABC$ be a triangle with incircle centered at $I$ , tangent to sides $AC$ and $AB$ at $E$ and $F$ respectively. Let $N$ be the midpoint of major arc $BC$ (wrt to the circumcircle) passing through $A$ . Let $IN$ intersect $EF$ at $K$ , and $M$ be the midpoint of $BC$ . Prove that $KM\perp EF$ .

6. Given a cyclic quadrilateral $ABCD$ , consider two variable points $P, Q$ inside the quadrilateral, satisfying these properties: $\angle PAB=\angle QCD$ and $\angle PBA=\angle QDC$

Prove that $PQ$ always passes through a fixed point.

.................................................................................................................

BIMO 1 2022

1. Find all functions $f:\mathbb{R}\rightarrow \mathbb{R}$ such that for all real numbers $x,y$ , we have $f(xf(x)+2y)=f(x)^2+x+2f(y)$ 2. It is known that a polynomial $P$ with integer coefficients has degree $2022$ . What is the maximum $n$ such that there exist integers $a_1, a_2, \cdots a_n$ with $P(a_i)=i$ for all $1\le i\le n$ ?

[Extra: What happens if $P \in \mathbb{Q}[X]$ and $a_i\in \mathbb{Q}$ instead?]

3. Given a polynomial $P\in \mathbb{Z}[X]$ of degree $k$ , show that there always exist $2d$ distinct integers $x_1, x_2, \cdots x_{2d}$ such that $P(x_1)+P(x_2)+\cdots P(x_{d})=P(x_{d+1})+P(x_{d+2})+\cdots + P(x_{2d})$ for some $d\le k+1$ .

[Extra: Is this still true if $d\le k$ ? (Of course false for linear polynomials, but what about higher degree?)]

4. Let $ABC$ be a triangle with with incenter $I$ and $A$ -excenter $J$ . Choose two points $P$ and $Q$ on the circumcircle $(ABC)$ such that $\angle API=\angle AQJ=90^{\circ}$ Prove that $PQ\parallel BC$ .

5. Let $\omega$ be the circumcircle of an actue triangle $ABC$ and let $H$ be the feet of aliitude from $A$ to $BC$ . Let $M$ and $N$ be the midpoints of the sides $AC$ and $AB$ . The lines $BM$ and $CN$ intersect each other at $G$ and intersect $\omega$ at $P$ and $Q$ respectively. The circles $(HMG)$ and $(HNG)$ intersect the segments $HP$ and $HQ$ again at $R$ and $S$ respectively. Prove that $PQ\parallel RS$ .

6. A pentagon $ABCDE$ is such that $ABCD$ is cyclic, $BE\parallel CD$ , and $DB=DE$ . Let us fix the points $B,C,D,E$ and vary $A$ on the circumcircle of $BCD$ . Let $P=AC\cap BE$ , and $Q=BC\cap DE$ .

Prove that the second intersection of circles $(ABE)$ and $(PQE)$ lie on a fixed circle.

7. Let $ABCD$ be a circumscribed quadrilateral with incircle $\gamma$ . Let $AB\cap CD=E, AD\cap BC=F, AC\cap EF=K, BD\cap EF=L$ . Let a circle with diameter $KL$ intersect $\gamma$ at one of the points $X$ . Prove that $(EXF)$ is tangent to $\gamma$ .

BIMO 2 2022

8. Let $ABC$ be a triangle, and let $BE, CF$ be the altitudes. Let $\ell$ be a line passing through $A$ . Suppose $\ell$ intersect $BE$ at $P$ , and $\ell$ intersect $CF$ at $Q$ . Prove that:

i) If $\ell$ is the $A$ -median, then circles $(APF)$ and $(AQE)$ are tangent.

ii) If $\ell$ is the inner $A$ -angle bisector, suppose $(APF)$ intersect $(AQE)$ again at $R$ , then $AR$ is perpendicular to $\ell$ .

9. Let $n$ , $k$ be fixed integers. On a $n \times n$ board, label each square $0$ or $1$ such that in each $2k \times 2k$ sub-square of the board, the number of $0$ 's and $1$ 's written are the same. What is the largest possible sum of numbers written on the $n\times n$ board?

5/1/2021: 3 more original questions (At least I hoped so..)

by navi_09220114, Jan 5, 2021, 8:53 AM

1) Find all functions $f : \mathbb{R} \rightarrow \mathbb{R}$ such that for all reals $x, y$ , $f(x^2+f(x+y))=y+xf(x+1)$
2) Let $a_1,a_2,\cdots$ be a strictly increasing sequence on positive integers.

Is it always possible to partition the set of natural numbers $\mathbb{N}$ into infinitely many subsets with infinite cardinality $A_1,A_2,\cdots$ , so that for every subset $A_i$ , if we denote $b_1<b_2<\cdots$ be the elements of $A_i$ , then for every $k\in \mathbb{N}$ and for every $1\le i\le a_k$ , it satisfies $b_{i+1}-b_{i}\le k$ ?

3) Let $G$ be the centroid of a triangle $\triangle ABC$ and let $AG, BG, CG$ meet its circumcircle at $P, Q, R$ respectively. Let $AD, BE, CF$ be the altitudes of the triangle.

Prove that the radical center of circles $(DQR),(EPR),(FPQ)$ lies on Euler Line of $\triangle ABC$ .

(Turns out that problem 3 isn't exactly original, even though I made it myself..)

Anyway, have fun!

2/1/2021: Four problems that I created for the IMO training

by navi_09220114, Jan 2, 2021, 11:11 AM

A very quick post: I have been involved in the IMO trainings lately in my country, and now I am sharing the problems that I had created myself.
...........................
1) Given a natural number $n$ , call a divisor $d$ of $n$ to be $\textit{nontrivial}$ if $d>1$ . A natural number $n$ is $\textit{good}$ if one or more distinct nontrivial divisors of $n$ sum up to $n-1$ .

Prove that every natural number $n$ has a multiple that is good.

2) Find all continuous functions $f : \mathbb{R} \rightarrow \mathbb{R}$ such that for all real numbers $x, y$ $f(x^2+f(y))=f(f(y)-x^2)+f(xy)$ (In fact continuity is not necessary - it just simplifies one part of the argument!)

3) There are $k$ piles of stones with $2020$ stones in each pile. Amber can choose any two non-empty piles of stones, and Barbara can take one stone from one of the two chosen piles and puts it into the other pile. Amber wins if she can eventually make an empty pile. What is the least $k$ such that Amber can always win?

4) Let $ABC$ be an actue triangle with $AB<AC$ . Let $\Gamma$ be its circumcircle, $I$ its incenter and $P$ is a point on $\Gamma$ such that $\angle API=90^{\circ}$ . Let $Q$ be a point on $\Gamma$ such that $QB\cdot\tan \angle B=QC\cdot \tan \angle C$ Consider a point $R$ such that $PR$ is tangent to $\Gamma$ and $BR=CR$ .

Prove that the points $A, Q, R$ are colinear.
.............................
Enjoy!

own

24/10/2018: Random Questions

by navi_09220114, Oct 24, 2018, 1:27 PM

Ok, I will "re-set" the question number to 1 just for this post: Because the questions here are for you to solve for fun! (if you are reading this)

And there is no mystery to this: I am simply busyyyyyy!

1. Suppose you have a sequence $x_1, x_2, \cdots, x_n, \cdots$ such that the sum $\sum_{m=1}^{\infty}x_{mk}$ converges to $0$ for all $k\in \mathbb{N}$ . Must $x_n$ converge to $0$ as well?

2. If $k$ is a field and $G\le k$ is a finite multiplicative subgroup of $k^*$ (the multiplicative group of $k$ ), then $G$ is cyclic.

3. Show that if a set $E$ is recursive iff $E$ and $\mathbb{N}/E$ are both recursive enumerable.

4. Why is $SO(3)$ isomorphic to $SO(2)/ \mathbb{Z}_2$ ?

5. (Hard) Show that $ij$ -compression of a set system reduces its shadow. (Can you generalize to "sets" instead of singletons $\{i\}$ and $\{j\}$ ?)

This post has been edited 6 times. Last edited by navi_09220114, Oct 24, 2018, 1:45 PM

20/10/18: Some Group Theory

by navi_09220114, Oct 20, 2018, 2:47 PM

I apologize for the inactivity of my blog. There are mainly 3 reasons to that:

1) I am practicing for the IMO quite heavily since June till the IMO. I still did badly at the IMO though, but the IMO was very fun and nice.

2) Right after that I started learning some university math seriously. I realized there is nothing much interesting stuff to write here, so i didn't. This lasted untill I started my university.

3) Obviously after that it took me a month (which is right now!) to settle down and get in pace with the lectures.

But since I do have time now, allow me to continue writing here if I may do so!

..........................

Anyway let me write something easy first. (I need time to process the "hard" stuff to write them here, and I promise I will try to find the time to do so!)

15. You have a non-abelian group $G$ . If we denote $\text{Comm}(G)$ to be the probability that two random elements of $G$ commute with each other, then prove that $\text{Comm}(G)\le \frac{5}{8}$ .

Proof: I will sketch the proof a bit: I am genuinely busy and the example sheets are not easy to do them!

So consider $C_G(a)$ be the centralizer of $a$ , then clearly $\text{Comm}(G)=\frac{1}{|G|^2}\sum_{a\in G}|C_G(a)|=\frac{1}{|G|^2}\sum_{a\in G}\frac{|G|}{|ccl(a)|}$ which the latter is simply Orbit-Stabilizer Theorem. Now double count to simplify it as $\frac{n}{|G|}$ , where $n$ is the number of conjugacy classes of $G$ . Then we need that $n\le \frac{5}{8}|G|$ Counting conjugacy classes can be difficult, especially when you look at the bigger ones. Instead, we turn to the other side: Count the number of singleton orbits. Then these elements will form the center of $G$ !

Now we see what to prove: Every other orbit of elements not in $Z(G)$ will have size at least $2$ , so the number of conjugacy classes is at most $|Z(G)|+\frac{1}{2}(|G|-|Z(G)|)$ , in which we are done if we can prove that $|Z(G)|\le \frac{|G|}{4}$ . Do observe that this is an important step, since the equality does hold when $G=Q_8$ , the quarternion group! This in fact, lies a hidden but stronger truth:

Lemma: $Z(G)$ is a normal subgroup of $G$ which has index at least $4$ if $G$ is non-abelian. In fact, $G/Z(G)$ must not be cyclic in this case!

Proof of Lemma: The first statement is trivial. Now suppose we consider $G/Z(G)$ to be cyclic, then every such cosets are in the form $a^kZ(G)$ for some $a\in G$ and $k\in \mathbb{N}$ . Now suppose $x=a^ix_1\in a^iZ(G), y=a^jy_1\in a^jZ(G)$ , then $xy=a^ix_1a^jy_1$ . But remember that $x$ and $y$ are in the center of $G$ hence commute with every element in $G$ ! Then we get $xy=a^ix_1a^jy_1=a^{i+j}x_1y_1=a^ja^iy_1x_1=a^jy_1a^ix_1=yx$ So $G$ is abelian, contradiction.

Finally, any group like $G/Z(G)$ that is non-cyclic must have composite order, hence at least $4$ . So $|Z(G)|\le \frac{|G|}{4}$ . Yay $\blacksquare$

This post has been edited 4 times. Last edited by navi_09220114, Oct 21, 2018, 7:15 AM

25/5/18: IMO 2011 P2

by navi_09220114, May 24, 2018, 3:03 PM

14. Let $\mathcal{S}$ be a finite set of at least two points in the plane. Assume that no three points of $\mathcal S$ are collinear. A windmill is a process that starts with a line $\ell$ going through a single point $P \in \mathcal S$ . The line rotates clockwise about the pivot $P$ until the first time that the line meets some other point belonging to $\mathcal S$ . This point, $Q$ , takes over as the new pivot, and the line now rotates clockwise about $Q$ , until it next meets a point of $\mathcal S$ . This process continues indefinitely.

Show that we can choose a point $P$ in $\mathcal S$ and a line $\ell$ going through $P$ such that the resulting windmill uses each point of $\mathcal S$ as a pivot infinitely many times.

\textbf{Solution.} Let the $n$ points be $A_1, A_2, \cdots, A_n$ . Let us give the windmill a direction modulo $2\pi$ , so we can think of it as a directed line, then we can define the left region and the right region of the line when the line is pointing upwards. Call $\ell$ be the directed line, and $L$ , $R$ be the set of points in the left region and right region of $\ell$ , and let $V$ be the set of all unit vectors in $\mathbb{R}^2$ except unit vectors that is parallel to any vector in the form $A_iA_j$ $1\le i \neq j \le n$ . We are only interested in $\ell$ that has a direction in $V$ .

Now start with any line and point arbitarily, and we start the windmill.

Claim 1: Right before the windmill with pivot $A$ reaches another point $B$ in $S$ and right after it leaves the point $A$ with pivot $B$ , the size of $L$ and $R$ is unchanged.

Proof: We consider the moment the windmill is the directed line $AB$ , call the left region and right region at this moment to be $L', R'$ respectively. Right before this moment, $L=L', R=R'\cup \{B\}$ , and right after this moment, $L=L'\cup \{A\}, R=R'\cup \{A\}$ . So $|L|$ and $|R|$ is unchanged whenever the windmill has a direction in $V$ .

Claim $1$ means we can let $p=|L|, q=|R|, p+q=n-1$ , be two fixed nonnegative integers, such that when the windmill has direction $v\in V$ , it has $p$ points at the left region and $q$ points at the right region.

Claim 2: Given a vector in $v\in V$ , then there exist a unique $A\in S$ such that at anytime when the windmill $\ell$ has the same direction as $v$ , it has pivot at $A$ .

Proof: Do a scan according to the vector $v$ . In detail, rotate $v$ and the points in $S$ so that $v$ is parallel to the $y$ -axis. The points $A_1, A_2, \cdots A_n$ can be reordered according to their $x$ coordinates, and they are all distinct by definition of $v\in V$ . Choose the point $A$ with the $p+1$ -th smallest $x$ -coordinate. This point $A$ will have $p$ points in $S$ having smaller $x$ coordinate than $A$ . After we identify $A$ , let's start the windmill. At any time when the windmill has direction $v$ , at this moment the left region has exactly $p$ points by Claim 1, hence the pivot must be $A$ !

Now with Claim $2$ , we just need to show that for any configuration of points, we can draw a directed line passing through every point in $S$ , such that each directed line splits $S$ into left and right regions with $p$ and $q$ points respectively. It suffices to choose the correct choice of $p$ and $q$ . Consider a regular polygon with the circumcenter indicates that $|p-q|=1$ must hold for this case. Conversely, we will prove that if $p-q\in \{0,1\}$ , then it will work for any set $S$ .

Claim 3: For such choice of $p$ and $q$ , we can choose such a vector $v(A)$ for every point $A$ in $S$ .

Proof: This time we do ''radial'' scanning. Pivot $\ell$ at $A$ and do not change the pivot. Keep track of the values of $a=|L''|$ and $b=|R''|$ be the number of points in the left region and right region when the direction is $v$ . Now rotate $v$ clockwise, at any point $\ell$ must not meet two or more points other than $A$ , otherwise we get at least $3$ colinear points in $S$ including $A$ . So the value of $a$ changes by $\pm 1$ and $b$ changes by $\mp 1$ , so the value $a-b$ must change with an integer in $\{-2, 2\}$ .

Let's consider any arbitary initial direction $v_0$ , the difference $|L''|-|R''|$ is $a-b$ . When the direction is $-v_0$ , the difference $|L''|-|R''|$ is $-(a-b)$ . So from the above paragraph, the difference $|L''|-|R''|$ must be in the range $[0,1]$ for some direction $v$ , since it changes is in range $[-2, 2]$ . Then we can assign this vector $v$ for $A$ as $v(A)$ .

To finish the problem, note that if we start with any point $A$ in $S$ with direction $v$ that is assigned to $A$ , then $p-q\in \{0,1\}$ . By Claim $2$ , at any time $\ell$ has direction $v$ , there is a unique such pivot for $v$ , and by Claim $3$ all points in $S$ are one of such pivots by choosing $v(A)$ for all $A\in S$ . This is our desired windmill. $\blacksquare$

22/5/2018: IMOSL 2012 N5

by navi_09220114, May 21, 2018, 4:51 PM

I am actually still angry. I am not going to sleep now untill I properly solve something decent tonight. I will try the N5 right now before I sleep -_-

I dont care, let it be 1 AM right now >:-(

13. For a nonnegative integer $n$ define $\operatorname{rad}(n)=1$ if $n=0$ or $n=1$ , and $\operatorname{rad}(n)=p_1p_2\cdots p_k$ where $p_1<p_2<\cdots <p_k$ are all prime factors of $n$ . Find all polynomials $f(x)$ with nonnegative integer coefficients such that $\operatorname{rad}(f(n))$ divides $\operatorname{rad}(f(n^{\operatorname{rad}(n)}))$ for every nonnegative integer $n$ .

Solution: Of course $f(x)=ax^m$ works for all non-negative integers $a, m$ . Now we wish to show this is the only solution.

Hmm so $f(n)$ and $f(n^{rad(n)})$ .. I tried to investigate $rad(n)$ a little bit, so I fixed $rad(n)$ say a prime, but it didn't help, like $rad(f(p^k))\mid rad(f(p^{kp}))$ for all primes $p$ . What on earth is this...

After for 10 minutes or so, I felt angry for being so dumb: I won't do any good by looking at $rad(f(n))$ ! I need to break those primes in the $rad$ down!

So let's look at one prime $p$ , then the statement becomes $p|f(n)\Rightarrow p|f(n^{rad(n)})$ . This is so much more better. Ok I will attack from here.

1) $p\mid f(n) \Rightarrow p\mid f(n^{rad(n)})$ .

This condition still felt very rigid, I need more varying factors to it. But what happens if I do this thing again to $n^{rad(n)}$ ?

2) Apply the condition again, $rad(n^{rad(n)})=rad(n)\Rightarrow p\mid f(n^{rad(n)^2})$ as well!
3) Apply the condition reapeatedly and since $rad(n^{rad(n)^k})=rad(n)$ , then $p\mid f(n^{rad(n)^k})$ as well.

This is good, then I can play with quite a lot of numbers in the form $n^m$ , $m=rad(n)^k$ . Maybe I should look into what are the possible residues of $n^m$ modulo $p$ ?

Well let's remove some cases first.

4) If now $p\mid n$ too, then $p\mid f(0)$ , nothing else is relevant from the condition.

Now let's consider $p\nmid n$ , then the discussion of residues of $n^m$ will make sense here. At this point I am still clueless what to do next. So I take some time to reorganize what I done above. I want $f(0)=0$ , or $f$ to be constant. How should I make $f(something)$ to overload with primes? (this is a very routine idea of proving constant functions)

And then after 10 or 15 minutes..."I am stupid, now this is so obvious: Look at $m$ modulo $p-1$ huh, STILL DON'T SEE WHY IT WON'T WORK?!"

Of course it won't!! I can't fix $rad(n)$ in a way that $rad(n)^k$ is divisible by $p-1$ , of course i will never get $0$ . But how can I not see that I can also vary $n$ itself?!!!

5) Since $p\mid f(n)$ , $p\mid f(n+p\ell)$ as well!
6) Since $(n+p\ell)^{rad(n+p\ell)}\equiv n^{rad(n+p\ell)} \pmod p$ , $p\mid f(n^{rad(n+p\ell)})$ too.
7) We choose $\ell$ such that $rad(n+p\ell)$ is a multiple of $rad(p-1)$ , then a large $k$ will ensure that $rad(n+p\ell)^k$ is divisible by $p-1$ !
8) But this can be done by taking $n+p\ell$ to be a multiple of $p-1$ , or say $\ell=2018(p-1)+(p-2)n$ .
9) So $p\mid f(n)\Rightarrow p\mid f(n^{rad(n+p\ell)^k}) \Rightarrow p\mid f(1)$ .

Very well. Now every prime that divides $f(n)$ must divide $f(0)$ or $f(1)$ , that is $f(0)f(1)$ in general.

10) Every constant functions $f$ work. So suppose $f$ is non-constant.
11) By Schur's Theorem, there exist infinitely many primes $p$ that divides some terms $f(n)$ .
12) By 9), these primes $p$ will all divide $f(0)f(1)$ . This is impossible unless $f(0)=0$ , since $f(1)=0$ implies sum of coefficients of $f$ is zero, false. In fact, $f(1)>0$ .
13) So $f$ can be factored in the form $f(x)=x^mg(x)$ for some $m$ and $g(0)\neq 0$ .
14) Suppose $g$ is nonconstant, then again there are infinitely many primes $p$ that divide some term $g(n)$ .
15) For such prime with $p\mid g(n)$ , if $p\nmid n$ then $p\mid g(n)\mid f(n)\Rightarrow p\mid f(1)$ , so there are only finitely many such primes since $f(1)>0$ .
16) So there are infinitely many primes $p$ with $p\mid g(n)$ and $p\mid n$ .
17) But these primes will all divide $g(0)\neq 0$ . Contradiction.
18) So $g$ must be constant, and so $f(x)=ax^m$ for some non-negative $a, m$ . $\blacksquare$

Good grief... It's 2:40 AM now #ripsleep

why do i actually take so long to solve this.. Now I look back this is actually quite routine NT polynomial problem.. I have to think about this matter tomorrow.

This post has been edited 24 times. Last edited by navi_09220114, May 22, 2018, 3:58 AM

21/5/2018: IMO 2005 p2

by navi_09220114, May 21, 2018, 4:48 PM

And I would like to praise my student for able to solve this problem.

He just started olympiad math and attended the IMO camp training around last December, without much knowledge. But in just a few months he improved this much. He must have worked very hard to acheive this

12. Let $a_1,a_2,\ldots$ be a sequence of integers with infinitely many positive and negative terms. Suppose that for every positive integer $n$ the numbers $a_1,a_2,\ldots,a_n$ leave $n$ different remainders upon division by $n$ .

Prove that every integer occurs exactly once in the sequence $a_1,a_2,\ldots$ .

Solution: Of course, $|a_i-a_j|\le max (i,j)$ . Then put the terms one by one and they must be consecutive..

If you have $x+1$ to $x+k$ , then consider the two intervals of length $2(k+1)$ from centers are $x+1$ and $x+k$ , then the two interval intersect at only $x$ or $x+k+1$ , so this will only be the possible next term, hence they are still consecutive.

Since there are infinitely many negative and positive terms, the consecutive numbers must extend both ways hence includes every integer. $\blacksquare$ .

Comment: Well my method is more straightforward, once we get $|a_i-a_j|\le \max(i,j)$ , then $\max(a_1, a_2, \cdots, a_n)-\min(a_1, a_2, \cdots, a_n)\le n$ as well, so they are consecutive blocks, and continue as above.

This post has been edited 1 time. Last edited by navi_09220114, May 21, 2018, 4:48 PM

21/5/2018: Iran TST FE

by navi_09220114, May 21, 2018, 4:20 PM

Since I fail combi for the whole day again, I NEED TO DO SOMETHING ELSE TO BE PRODUCTIVE!

So I chose FE, which is something i am still decent at, at least not like my combi -.-

11. Find all surjective functions $f:\mathbb{R}\rightarrow \mathbb{R}$ so that $f(x+f(x)+2f(y))=f(2x)+f(2y)$ .

Solution:
0) $P(x,y): f(x+f(x)+2f(y))=f(2x)+f(2y)$ .
1) $P(x,0), P(0,x) \Rightarrow f(x+f(x)+2f(0))=f(2x)+f(0)=f(f(0)+2f(x))$

Let's pop more $f(x)$ 's without the $x$ to interfere surjectivity

2) $f(x+f(x)+2f(y))=f(2x)+f(f(0)+2f(y))$
3) Since $f(y)$ represents every real $z$ , $f(x+f(x)+z)=f(2x)+f(f(0)+z)$
4) $z=x-f(x) \Rightarrow f(f(0)+x-f(x))=0$
5) $x=0\Rightarrow f(0)=0$ .

Good, now we have many things clean up.

6) $f(x+f(x))=f(2x)=f(2f(x))$

This is very suggestive of injectivity.. So let's try to consider $f(a)=f(b)$ .

7) $f(a)=f(b)\Rightarrow f(2f(a))=f(2f(b))\Rightarrow f(2a)=f(2b)$
8) $f(2a)=f(2b) \Rightarrow f(a+f(a)+2f(y))=f(b+f(b)+2f(y))$
9) By surjectivity again, take $y$ with $f(y)=\frac{-f(a)}{2}+c$
10) This choice of $y$ gives $f(a+c)=f(b+c)$ for every real $c$ .

Period of $a-b$ huh. Very well.

11) From $6$ , $f(x)-x$ is a period of $f$ .
12) $f(f(x)-x+c)=f(c)$ .
13) Take $c=x$ then $f(f(x))=f(x)$ . By surjectivity, $f(x)=x$ . $\blacksquare$

This post has been edited 2 times. Last edited by navi_09220114, May 21, 2018, 5:02 PM

Submit

Hi IMO god, CANBANKAN
by 799786, Aug 6, 2022, 5:28 PM
Hi geo god
by CANBANKAN, May 7, 2022, 4:35 AM
Updates please !
by Kayak, Aug 6, 2018, 6:47 AM
Wow Navi, so this is what you have been up to lately. Interesting!
by SeanGee, May 27, 2018, 3:12 PM
how r u so good?
by claserken, May 18, 2018, 6:43 PM
Contrib please
by WizardMath, Mar 16, 2018, 8:38 PM
Contrib?
by anantmudgal09, Mar 15, 2018, 7:35 AM
Nice blog! Second shout lol
by WizardMath, Mar 9, 2018, 10:41 AM
first shout >
by doitsudoitsu, Mar 5, 2018, 12:20 PM

9 shouts

lol