IMO 2017 Day 1

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

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{aligned} \sqrt{a_n} \quad &\text{if } \sqrt{a_n} \text{ is an integer}\\ a_n+3 \quad &\text{otherwise} \end{aligned} \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$ ?

Markdown

Appears as

*italics* or _italics_

italics

**bold** or __bold__

bold


- bulleted
- list

bulleted
list


1. numbered
2. list

numbered
list

Note: you must add a full line of space before and after lists for them to show up correctly

paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)

example link

> This is a quote

This is a quote

    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"

# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"

Math

Appears as

Remember to wrap math in $ ... $ or \[ ... \] to ensure proper formatting.

2 \times 3

2 \times 3

2^{34}

2^{34}

a_{i-1}

a_{i-1}

\frac{2}{3}

\frac{2}{3}

\sqrt{2}

\sqrt{2}

\sum_{i=1}^3

\sum_{i=1}^3

\sin \theta

\sin \theta

\boxed{123}

\boxed{123}

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

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 - 3 years, 11 months ago

Thank you,its beautiful!

Kabir Sahni - 2 years, 11 months ago

Brilliant, but not very lucid. The solutions on AoPS are much better written.

Star Light - 1 year, 11 months ago

P2.

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.

$f(f(x)f(-x))=f(-x^2)-f(0)~\Rightarrow~f(f(x)f(-x))=f(-x^2+1)~\Rightarrow~f(x)f(-x)=-x^2+1$

$f(f(x)f(1-x))=f(x(1-x))~\Rightarrow~f(x)f(1-x)=x-x^2~\Rightarrow~f(x)\{f(-x)-f(0)\}=-x^2+x$

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

Boi (보이) - 3 years, 11 months ago

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

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. :')

@Boi (보이) – It'll probably get 6 since you didn't directly prove it. Use it as a lemma instead.

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

Hold on lemme search-

@Boi (보이) – Here is my description of what some definitions required in proof writing. :P

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

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.

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 - 3 years, 11 months ago

Yes, I saw the solution on AoPS. It's amazing, but intense.

@Sharky Kesa – Yes, I'm pretty confident that there's a (much) shorter solution

Hahah! One of the members of our IMO team got 7/7 for it. :)

Sharky Kesa - 3 years, 10 months ago

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 - 3 years, 10 months ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$