Waste less time on Facebook — follow Brilliant.

IMO 2017 Day 1

Discussions of these problems have already started on AoPS. Let's start a few over here. :)

Day 2

Problem 1

For each integer \(a_0>1\), define the sequence \(a_0, a_1, a_2, \ldots, a_n, \ldots\) for \(n \geq 0\) as

\[a_{n+1}= \begin{cases} \begin{align} \sqrt{a_n} \quad &\text{if } \sqrt{a_n} \text{ is an integer}\\ a_n+3 \quad &\text{otherwise} \end{align} \end{cases}\]

Determine all values of \(a_0\) such that there exists a number \(A\) such that \(a_n = A\) for infinitely many values of \(n\).

Problem 2

Let \(\mathbb{R}\) be the set of real numbers. Determine all functions \(f: \mathbb{R} \rightarrow \mathbb{R}\) such that, for any real numbers \(x\) and \(y\),

\[f(f(x)f(y)) + f(x+y) = f(xy).\]

Problem 3

A hunter and an invisible rabbit play a game in the Euclidean plane. The rabbit's starting point, \(A_0,\) and the hunter's starting point, \(B_0\) are the same. After \(n-1\) rounds of the game, the rabbit is at point \(A_{n-1}\) and the hunter is at point \(B_{n-1}.\) In the \(n^{\text{th}}\) round of the game, three things occur in order:

\((\text{i})\) The rabbit moves invisibly to a point \(A_n\) such that the distance between \(A_{n-1}\) and \(A_n\) is exactly \(1\).

\((\text{ii})\) A tracking device reports a point \(P_n\) to the hunter. The only guarantee provided by the tracking device to the hunter is that the distance between \(P_n\) and \(A_n\) is at most \(1\).

\((\text{iii})\) The hunter moves visibly to a point \(B_n\) such that the distance between \(B_{n-1}\) and \(B_n\) is exactly \(1\).

Is it always possible, no matter how the rabbit moves, and no matter what points are reported by the tracking device, for the hunter to choose her moves so that after \(10^9\) rounds, she can ensure that the distance between her and the rabbit is at most \(100\)?

Note by Sharky Kesa
4 weeks ago

No vote yet
1 vote


Sort by:

Top Newest

This was my method of going about solving P1:

The sequence looks a bit weird, so I went about first trying a few small cases for \(a_0\). I found that the sequence became periodic if \(3 \mid a_0\). This was what I would try to prove, since a direct corollary is there exist numbers \(A\) that appear infinitely many times in the sequence.

I decided to use \(\pmod{3}\) since that would both satisfy my result. Secondly, whilst the sequence increases by 3, it remains the same \(\pmod{3}\).

Firstly, note that \(n^2 \equiv 0, 1 \pmod{3}\), so if \(a_0 \equiv 2 \pmod{3}\), then the sequence would be increase continuously without changing its residue \(\pmod{3}\). Thus, \(a_0 \not \equiv 2 \pmod{3}\).

Secondly, if \(a_0 \equiv 1 \pmod{3}\), we can show this isn't periodic by strong induction. For base case \(a_0=4\), \(a_0=7\), \(a_0=10\), \(a_0=13\) and \(a_0=16\), we find this to be true. Now, we can assume \(m^2 < a_0 \leq (m+1)^2\) for \(m \geq 4\). If a perfect square is equivalent to \(1 \pmod{3}\), then the square root of it is also not divisible by 3. Now, there must exist a term in the sequence \(a_i\) such that \(a_i = (m+1)^2\) or \(a_i = (m+2)^2\), so \(a_{i+1} = m+1\) or \(a_{i+1}=m+2\). Now, we have \(m+2 < (m-1)^2\) for all \(m\geq 4\). Thus, this sequence is eventually decreasing to the base cases, so by strong induction, this isn't periodic.

Finally, if \(3 \mid a_0\), we have base cases \(a_0=3\), \(a_0=6\) and \(a_0=9\) which all satisfy. Now, we can assume \((3(m-1))^2 < a_0 \leq (3m)^2\) for \(m \geq 2\). Note that if a perfect square is divisible by 3, then it's square root is divisible by 3. Thus, there exists a term in the sequence \(a_i\) such that \(a_i = (3m)^2\), so \(a_{i+1}=3m < (3(m-1))^2\), which is true for all \(m \geq 2\). Thus, this sequence is evnetually decreasing to the base cases, so by strong induction, this is periodic.

Thus, we must have \(3 \mid a_0\). Sharky Kesa · 4 weeks ago

Log in to reply


If \(f(0)=0,\) substitute \(y=0.\)

You get \(f(x)=\boxed{0}.\)

Now then let \(f(0)\neq0\)

\(\boxed{\text{If }~f(k)=0,~\text{ then }k=1}.\)

Cus if \(k\neq1\), we can substitute \(x=k,~y=\dfrac{k}{k-1},\) and it yields \(f(0)=0\) which is a direct contradiction in the face.

Substitute \(x=0,~y=0\) and you get \(f(f(0)^2)=0,\) which leads to \(f(0)=\pm 1,\) and therefore \(f(1)=0.\)

Then let \(y=1,\) and you get \(\boxed{f(0)+f(x+1)=f(x)}.\)

Assume there exists \(a,~b\) such that \(f(a)=f(b).\)

But in fact if \(a>1,\) we can add \(f(0)\) to both sides of \(f(a)=f(b)\) however many times we want and lower the values that are inside the function.

Therefore, \(f(a)=f(b)\) and \(a<1.\) From it we can say that there are real numbers \(p,~q\) such that \(pq+1=a\) and \(p+q=b,\) since then \(pq\) would be negative and therefore the discriminant of the quadratic equation \(t^2-bt+(a-1)=0\) that has \(p,~q\) as its roots would be always positive. \((D=b^2-4(a-1)=b^2-4pq>0.)\)

Then substitute \(x=p,~y=q.\)

\(f(f(p)f(q))+f(b)=f(a-1)=f(a)+f(0)=f(b)+f(0),\) and so \(f(f(p)f(q))=f(0),\) \(f(f(p)f(q)+1)=0.\)

\(f(p)f(q)=0\) and therefore \(p=1\) or \(q=1,\) which leads to \(a=b.\)

Therefore \(\boxed{\text{if }~f(a)=f(b),~a=b}.\)

Substitute \(y=-x\) and \(y=1-x\) respectively.



Subtract the second equation from the first.

\(f(0)f(x)=-x+1,\) and since \(f(0)=\pm1,\)

\(f(x)=\boxed{x-1}\) or \(f(x)=\boxed{-x+1}.\)

Therefore, there are only three possible solutions for \(f(x),\)

\(\boxed{f(x)=0},~\boxed{f(x)=x-1},~\boxed{f(x)=-x+1}.\) H.M. 유 · 4 weeks ago

Log in to reply

@H.M. 유 I'm confused as to how you can say there exist reals \(p\) and \(q\) such that \(pq+1=a\) and \(p+q=b\). I haven't seen this substitution and am curious as to how it is inspired. I proved you can always do it, but it doesn't seem like a trivial result.

Edit: After much fooling around, I determined how it is inspired. Nice. :) Sharky Kesa · 4 weeks ago

Log in to reply

@Sharky Kesa Haha xD

Yea... it was almost an accident.

I first tried it with \(pq=a,~p+q=b,\) but it didn't work by a very tiny bit, so yeah. :') H.M. 유 · 3 weeks, 6 days ago

Log in to reply

@H.M. 유 It'll probably get 6 since you didn't directly prove it. Use it as a lemma instead. Sharky Kesa · 3 weeks, 6 days ago

Log in to reply

@Sharky Kesa I don't even know what a lemma is though.

Hold on lemme search- H.M. 유 · 3 weeks, 6 days ago

Log in to reply

@H.M. 유 Here is my description of what some definitions required in proof writing. :P Sharky Kesa · 3 weeks, 6 days ago

Log in to reply

@Sharky Kesa Yeaa now I know what a lemma is. Thank you!

But it's kinda true that my solution went on without any logical flaws xD

Well... I added as to why we can always say that \(pq+1=a<1,~p+q=b\) such that \(p,~q\) are all real numbers.

...if that is what you meant. H.M. 유 · 3 weeks, 6 days ago

Log in to reply

Here are my solutions to these problems:

Problem 1: I found this problem a little flawed, as we will see in my solution. First, let's break this problem down by first finding the square roots of the perfect square values in the sequence. So basically, we are finding some number \(a_0\) and all \(a_0 + 3n\) such that \(a_0 + 3n \leq a^2\) and there is no other integer \(b^2 = a_0 + 3n\), otherwise, the next term in the sequence would be knocked into the sequence of some other \(c^2\). Now, notice, we can write a recursive sequence for perfect squares as \(a_1 = 1, a_n = a_{n-1}+(2n-1)\). Because of this, we can't have more than \(2\) perfect squares in the range \([a,a^2]\). This brings down the range of \(a_0\) to \([2,5]\). In addition to that, the value \(a^2-a=a(a-1)\) must be a multiple of \(3\) for \(a\) to go to \(a^2\) by adding a number of \(3\)s. This implies that \(a \equiv 1, 0 \pmod{3}\), so \(a_0=3\) or \(a_0=4\).

Now, we can start finding terms in between \(a\) and \(a^2\) inclusive. We can start by listing out all of the multiples of \(3\) from \(a_0\). For \(3\), this would be \(\{3,6,9\}\) and for \(4\), this would be \(\{4,7,10,13,16\}\).

One final possibility of an \(a_0\) so that it hits \(9\) or \(16\) an infinite amount of times is for it to reach an even power of \(3\) or \(4\). This means values such as \(3^4=81\). For example, let's say \(a_0 = 72\). The sequence would go \(\{72,75,78,81,9,3,6,9,3,6,9,\dots\}\). Because of this final possibility, there are actually an infinite number of \(a_0\)s. I feel like this should not happen, especially since it says to determine all possible values of \(a_0\). As a final example of this final possibility, let's say \(a_0 = 6558\). The sequence would then be \(\{6558,6561,81,9,3,6,9,3,6,9,\dots\}\).

For the sake of listing a finite number of \(a_0\)s, I will just say my answer is \(\{3,4,6,7,9,10,13,16\}\).

Problem 2: I did not get very far with problem 2, but here's what I have done so far: Let's try to get the same input for some of these functions, set \(x+y=xy\) and solve :\[x+y=xy \\ x-xy+y=0 \\ x(1-y)-(1-y)=-1 \\ (1-y)(x-1)=-1 \\ (y-1)(x-1)=1 \\ x=\frac{1}{y-1}+1=\frac{y-1+1}{y-1}=\frac{y}{y-1}\] So now, let's set \(x=\frac{y}{y-1}\): \[f(f(\frac{y}{y-1}) \cdot f(y))+f(\frac{y^2}{y-1})=f(\frac{y^2}{y-1} \\ f(f(\frac{y}{y-1}) \cdot f(y))=0 \implies f((f(2))^2)=f((f(0))^2)=0\] Through this, I got the function \(f(x)=0\). I'm not very good at these type of problems, so I just decided to stop there, although, I definitely could've gone farther.

Problem 3: First of all, I want to mention, from looking at the IMO 2017 results, I was quite intimidated by this problem, only 2 people got a 7 on this problem, 1 got a 5, 1 got a 4, 3 got a 1, and everyone else got a 0 on this problem. Here is my solution: Once again, I believe this problem is flawed, because the hunter can simply always move away from the rabbit, so of course it is not always possible for the hunter to be at most 100 units from the rabbit after \(10^9\) rounds. For the sake of having a solution, I'm going to assume that the hunter will always go towards the point indicated on the tracking device. We want to find extreme case in which the distance between the rabbit and the hunter is maximized each round. Let's use polar coordinates for the sake of this problem. Let \(A_0 = B_0 = (0, 0 radians)\) In the first round, let's assume \(A_1 = (1, \frac{\pi}{2})\) for the sake of simplicity. Now, to maximize the distance between the hunter and the rabbit, let \(P_1\) be the intersection between the circle of radius one centered at the origin and one centered at \(A_1\). Now, because this is a distance of 1 from the origin, the hunter can go there. Through this, the rabbit is \(1\) unit away from the hunter. For the rabbit to move as far away from the hunter, let's say \(A_2\) is at the opposite end of the circle centered at \(A_1\). Now, let's say \(P_2\) is at the intersection between the circle centered at point \(A_2\) and \(A_1\). Now, if the hunter goes in that direction, he would be \(\sqrt{5-2\cdot \sqrt{3}}\) units from the rabbit. If this process continues with the rabbit going to the side of the circle directly opposite of that of the position of the hunter, we can derive an equation for the distance between \(A_{n}\) and \(B_{n}\), which I was not able to do (That's the hard part). I did manage to approximate \(A_{2} B_{2} \approx \sqrt{2}\), which is greater than \(A_{1} B_{1}\). Kevin Tong · 2 weeks, 4 days ago

Log in to reply

Arguably, I have to say that this paper had one of the greatest difficulty ranges between Problem 1 to 3, if not the greatest (2012 came close though). From what I've heard, there are not yet any confirmed solves of P3 at the IMO, but CHN, JPN and KOR have kept their performance hidden. Sharky Kesa · 4 weeks ago

Log in to reply

@Sharky Kesa Hahah! One of the members of our IMO team got 7/7 for it. :) Sharky Kesa · 2 weeks, 5 days ago

Log in to reply

@Sharky Kesa Indeed, the range of difficulty level is tremendous!

P1 is easy once you consider modulo 3 (and apply induction).

I've seen the an actual solution for P3 on another math forum, and it's a real beast! Pi Han Goh · 4 weeks ago

Log in to reply

@Pi Han Goh Yes, I saw the solution on AoPS. It's amazing, but intense. Sharky Kesa · 4 weeks ago

Log in to reply

@Sharky Kesa Yes, I'm pretty confident that there's a (much) shorter solution Pi Han Goh · 4 weeks ago

Log in to reply

P1 seems very simple. You want to add 3 until you reach a square, then get the square root and keep adding 3 until you square root to 9 if the first term is larger than 9. So square rooting 9 leads to infinite values of a number. So basically any multiple of 3 will eventually square root down to 9, and then 3, and then a loop creates infinite values of 3 or 6 or 9. I basically just did some basic cases, then realized that if the first term is not a multiple of 3, then the squares it reaches will allow it to continue adding 3 to a different square, which will lead to no maximum term in the sequence. If the first term is not a multiple of 3, the first square it reaches will also not be a multiple of 3, and neither will be the square root, so adding 3 will never lead to the same square again. Keanu Ac · 2 weeks, 5 days ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...