2018 IMOC problems

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

74 posts

#1 h Nov 19, 2018, 12:17 PM • 13 Y

Y by TheDarkPrince, MNJ2357, pablock, MATH1945, Darghy, Hamel, ltf0501, Supercali, parmenides51, amar_04, megarnie, tiendung2006, Adventure10

As promised, here is the problems used for $2018$ IMOC. Hope that there isn't any typo ... :blush:

https://drive.google.com/file/d/1Pa1JzsfDb6OVuuDHvov7yYpxVdnHPmEv/view?usp=sharing

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

rmtf1111

698 posts

rmtf1111

#2 h Dec 1, 2018, 10:18 PM • 1 Y

Y by Adventure10

What is IMOC?
A1
A2
A3
A4
A5
A6
A7

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

liekkas

370 posts

liekkas

#3 h Dec 3, 2018, 12:40 PM • 2 Y

Y by Adventure10, Mango247

I got stuck at N1... :wacko:

Can anyone help me how to continue after showing injectivity ...

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

USJL

540 posts

USJL

#4 h Dec 4, 2018, 1:03 AM • 3 Y

Y by amar_04, Adventure10, Mango247

rmtf1111 wrote:

What is IMOC?
A1
A2
A3
A4
A5
A6
A7

I like your solution to A6

liekkas wrote:

I got stuck at N1... :wacko:

Can anyone help me how to continue after showing injectivity ...

Think about what kind of inequality the dividing condition is implicitly implying. There are a bunch of solutions to that problem I recall, but most of them rely on this.

Also I just want to claim C3, C6, N1, N3, N5 and N6, although I am just adapting C6 and N6 from somewhere else and the others are not that quality :p
(if they were better I would have saved them for Taiwan TST hehe)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Bobson

11 posts

Bobson

#5 h Dec 4, 2018, 2:59 AM • 2 Y

Y by Adventure10, Mango247

I proposed these two questions:
A5
A7

This post has been edited 2 times. Last edited by Bobson, Dec 4, 2018, 3:12 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

kaede

620 posts

kaede

#6 h Dec 4, 2018, 6:40 AM • 2 Y

Y by Adventure10, Mango247

For N5

The only possible value of $k$ are $1,2,3,6$

First, we will show that these $k$ satisfy the condition.
Suppose that $n$ can be expressed as the sum of $k$ squares of positive divisors of $n$ .

For $k=1$ , $\quad$ $n=n$ is valid expression, of course.
For $k=2$ , $\quad$ $n$ must be even, so $n=n/2+n/2$ is valid expression.
For $k=3$ , $\quad$ $n$ must be divisible by $3$ , so $n=n/3+n/3+n/3$ is valid expression.
For $k=6$ , $\quad$ $n$ must be divisible by $6$ , so $n=n/6+n/6+...+n/6$ is valid expression.
Why?

Second, we will show that there is no other possible value of $k$ .

For $k=4$ , $\quad$ $n=(2\cdot 7)^{2} +\left(2\cdot 7^{2}\right)^{2} +2\cdot 7^{2}$ cannot be expressed as the sum of $k$ positive divisors of $n$ .
For $k=5$ , $\quad$ $n=\left(7^{2}\right)^{2}+4\cdot 7^{2}$ cannot be expressed as the sum of $k$ positive divisors of $n$ .

For $k>6$ , $\quad$ consider the following two cases (1),(2)

(1) $k$ is not divisible by $4$
We can choose an odd $a\in \mathbb{N}$ such that $\mathrm{min}\left\{d\in \mathbb{N};\ \ d\mid a^{2}\left( a^{2} +k-1\right) ,d >6\right\} >6k$ and $5 \nmid a^{2}\left( a^{2} +k-1\right)$
Why?
Then $n=a^{2}\left(a^{2} +k-1\right) =\left(a^{2}\right)^{2} +(k-1) a^{2}$ cannot be expressed as the sum of $k$ positive divisors of $n$ .
Why?

(2) $k$ is divisible by $4$
We can choose an odd $a\in \mathbb{N}$ such that $\mathrm{min}\left\{d\in \mathbb{N} ;\ \ d\mid a^{2}\left(4a^{2} +k+2\right) ,d >6\right\} >6k$ and $5 \nmid a^{2}\left(4a^{2} +k+2\right)$
Then $n=a^{2}\left(4a^{2} +k+2\right) =\left(2a^{2}\right)^{2} +(2a)^{2} +(k-2) a^{2}$ cannot be expressed as the sum of $k$ positive divisors of $n$ .

$\blacksquare$

This post has been edited 4 times. Last edited by kaede, Dec 4, 2018, 7:53 AM
Reason: done

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

liekkas

370 posts

liekkas

#7 h Dec 4, 2018, 9:26 AM • 2 Y

Y by Adventure10, Mango247

Some questions:
C6 Are there $n$ sub-decks of cards rather than $k$ ? Since you pick $n$ cards in the end.
G1 What is $k$ ?
Also any hints for N2 , C5 and C6...?

USJL wrote:

Think about what kind of inequality the dividing condition is implicitly implying. There are a bunch of solutions to that problem I recall, but most of them rely on this.

I get that if $x>2y$ then $f^{f(x)}(y)=y$ or $x+2y$ , but I can't get more from it. Can you show the full solution?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jayme

9801 posts

jayme

#8 h Dec 4, 2018, 10:08 AM • 2 Y

Y by Adventure10, Mango247

Dear Mathlinkers,
for G5, http://www.artofproblemsolving.com/community/c6t48f6h1124893_parallel_lines_with_incenter

Sincerely
Jean-Louis

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jayme

9801 posts

jayme

#9 h Dec 4, 2018, 10:10 AM • 2 Y

Y by Adventure10, Mango247

Dear Mathlinkers,
for G5, see also

http://jl.ayme.pagesperso-orange.fr/Docs/La%20droite%20de%20Gray.pdf p. 10...

Sincerely
Jean-Louis

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

USJL

540 posts

USJL

#10 h Dec 4, 2018, 1:43 PM • 3 Y

Y by FEcreater, Adventure10, Mango247

liekkas wrote:

Some questions:
C6 Are there $n$ sub-decks of cards rather than $k$ ? Since you pick $n$ cards in the end.
G1 What is $k$ ?
Also any hints for N2 , C5 and C6...?

USJL wrote:

Think about what kind of inequality the dividing condition is implicitly implying. There are a bunch of solutions to that problem I recall, but most of them rely on this.

I get that if $x>2y$ then $f^{f(x)}(y)=y$ or $x+2y$ , but I can't get more from it. Can you show the full solution?

Yeah you are right. It should be $n$ sub-decks.

For N1,I think there is another typo (._.) It is supposed to be $x+f^{(x)}(y)|2(x+y)$ . Sorry about that, and I promise that I will blame FEcreater for that(X
But the wrong version might also be solvable... let me think for a while...

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

USJL

540 posts

USJL

#11 h Dec 4, 2018, 2:17 PM • 2 Y

Y by Adventure10, Mango247

Cool, I think it is still possible to solve that.

Step 1. For every given $y\in\mathbb{N}$ , we have that $f^{f(x)}(y) = y$ for sufficiently large $x$ .
Proof
Step 2. $f(y) = y$ for all $y\in\mathbb{N}$ .
Proof

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Supercali

1261 posts

Supercali

#12 h Dec 5, 2018, 1:22 PM • 1 Y

Y by Adventure10

Proof outline for N3:
The only solutions are $(x,y)=(1,1)$ . The given conditions imply that $x|y^2-y+1$ and $y|x^2-x+1$ , as well as $gcd(x,y)=1$ . So we get $xy| x^2+y^2-x-y+1$ After that it is an easy infinite descent.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Supercali

1261 posts

Supercali

#13 h Dec 5, 2018, 1:32 PM • 1 Y

Y by Adventure10

C1 can be overkilled by using Four Colour Theorem on the map+sea. Just note that if the sea is coloured suppose red, then red cannot be used to colour any region on land. Hence, we have used 3 colours.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

liekkas

370 posts

liekkas

#14 h Dec 8, 2018, 9:22 AM • 2 Y

Y by Adventure10, Mango247

USJL wrote:

Yeah you are right. It should be $n$ sub-decks.

But what if $n$ is even, and each sub-deck consist of a single number? In this case the sum must be $1+2+\cdots+n$ , which is not a multiple of $n$ .
By the way, can you clarify G1? Thanks.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

USJL

540 posts

USJL

#15 h Dec 8, 2018, 5:38 PM • 2 Y

Y by Adventure10, Mango247

liekkas wrote:

USJL wrote:

Yeah you are right. It should be $n$ sub-decks.

But what if $n$ is even, and each sub-deck consist of a single number? In this case the sum must be $1+2+\cdots+n$ , which is not a multiple of $n$ .
By the way, can you clarify G1? Thanks.

Ah sorry I messed it up. It is supposed to be k subdecks, choose 1 from each and show that the sum is divisible by k.

This post has been edited 1 time. Last edited by USJL, Dec 8, 2018, 5:44 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

USJL

540 posts

USJL

#39 h Dec 21, 2018, 11:03 AM • 2 Y

Y by Adventure10, Mango247

liekkas wrote:

What is the answer to C5? I have proved that Alice can guarantee to make $8$ components (with ugly method), but I haven’t proved the opposite direction.

It's more than 8

There is a really elegant strategy for both people. I actually like this problem very much so I won't spoil it unless you want a hint

This post has been edited 1 time. Last edited by USJL, Dec 21, 2018, 11:07 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

liekkas

370 posts

liekkas

#40 h Dec 22, 2018, 7:21 AM • 2 Y

Y by Adventure10, Mango247

Sorry for a late solution for C5. The answer is $10$ .
For Alice, she can open her strategy: choose square $(1,4),(1,8),(2,1),(3,6),(4,3),(5,8),(6,1),(6,5),(8,3),(8,7)$ . For the picture see the attachment below (I don't know how to draw a picture with LaTeX

).It can be found that any two squares have Descartes distance at least $4$ , so Bob can't connect them to form one component.
For Bob, define a "box" to be a pack of squares, such that any two squares of it have Descartes distance at most $3$ . Now we can dissect the chessboard to $10$ boxes (see the attachment). It's easy to see that Bob can guarantee there is no more than $1$ component in any box (Bob shouldn't color the square that is not in the same box as Alice's) .
Anyway, I want to see the (maybe much nicer) official solution

Attachments:

This post has been edited 2 times. Last edited by liekkas, Dec 22, 2018, 7:27 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MathStudent2002

934 posts

MathStudent2002

#41 h Dec 23, 2018, 2:51 AM • 4 Y

Y by Adventure10, Mango247, Mango247, Mango247

Here is another solution to G4.

As with juckter we get easily that $T$ is the reflection of $I_A$ over $BC$ . Let $N$ be the midpoint of arc $BC$ of $(ABC)$ and let $D_0$ be the foot from $I$ to $BC$ . It is well known (e.g. invert about the incircle) that $P, D_0, N$ are collinear, and now we have that $PEFI \sim PBCN$ by Spiral Sim so if $M$ is the midpoint of $BC$ we have $\angle PIA = \angle PNM = \angle D_0NM = \angle D_1NM$ where $D_1$ is the extouch point. Let $PI$ meet $TX$ at $Q$ , then $\angle ND_1Q = \angle MND_1 = \angle PIA = \angle QIN,$ so $(INQD_1)$ is cyclic. In particular, $\angle IQT = \angle IND_1 = \angle AIT = \angle AXT,$ so $IQ\parallel AX$ . Here we use the fact that $IT\parallel NX$ by homothety centered at $I_A$ with ratio $2$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

USJL

540 posts

USJL

#42 h Dec 23, 2018, 4:30 AM • 1 Y

Y by Adventure10

liekkas wrote:

Sorry for a late solution for C5. The answer is $10$ .
For Alice, she can open her strategy: choose square $(1,4),(1,8),(2,1),(3,6),(4,3),(5,8),(6,1),(6,5),(8,3),(8,7)$ . For the picture see the attachment below (I don't know how to draw a picture with LaTeX

).It can be found that any two squares have Descartes distance at least $4$ , so Bob can't connect them to form one component.
For Bob, define a "box" to be a pack of squares, such that any two squares of it have Descartes distance at most $3$ . Now we can dissect the chessboard to $10$ boxes (see the attachment). It's easy to see that Bob can guarantee there is no more than $1$ component in any box (Bob shouldn't color the square that is not in the same box as Alice's) .
Anyway, I want to see the (maybe much nicer) official solution

This is about the same idea that the official solution uses. It's just that the official construction is more periodic. The official solution uses an 8-mino, the Manhattan distance between any two squares of which is not greater than 3. It turns out that one can use this 8-mino to tile the whole plane, and this will provide another construction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SAT1001

233 posts

SAT1001

#43 h Dec 23, 2018, 4:51 AM • 1 Y

Y by Adventure10

Can you share the official solutions.
Thank You

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

USJL

540 posts

USJL

#44 h Dec 23, 2018, 3:50 PM • 2 Y

Y by Adventure10, Mango247

SAT1001 wrote:

Can you share the official solutions.
Thank You

Unfortunately the official solutions are all in Chinese (and also they are extremely brief). I think it will be OK to post it here, but I doubt if it will be helpful or not...

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SAT1001

233 posts

SAT1001

#45 h Dec 23, 2018, 4:25 PM • 3 Y

Y by USJL, Adventure10, Mango247

Oops!
Thanks for the information.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

liekkas

370 posts

liekkas

#46 h Dec 26, 2018, 1:54 PM • 2 Y

Y by USJL, Adventure10

USJL wrote:

This is about the same idea that the official solution uses. It's just that the official construction is more periodic. The official solution uses an 8-mino, the Manhattan distance between any two squares of which is not greater than 3. It turns out that one can use this 8-mino to tile the whole plane, and this will provide another construction.

Yeah. I first noticed that 8-mino works fine, and $8 \times 8$ doesn’t require accurate construction. It can be generalised that for a $n \times n$ chessboard, the final situation will be $\lceil \frac{n(n+2)}{8} \rceil$ connected components. But I somehow found that the way that 8-mino tiling the plane is not optimal for special $n$ ’s. However, construction can be completed by comparing Alice’s strategy.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

USJL

540 posts

USJL

#47 h Dec 26, 2018, 2:18 PM • 2 Y

Y by Adventure10, Mango247

liekkas wrote:

USJL wrote:

This is about the same idea that the official solution uses. It's just that the official construction is more periodic. The official solution uses an 8-mino, the Manhattan distance between any two squares of which is not greater than 3. It turns out that one can use this 8-mino to tile the whole plane, and this will provide another construction.

Yeah. I first noticed that 8-mino works fine, and $8 \times 8$ doesn’t require accurate construction. It can be generalised that for a $n \times n$ chessboard, the final situation will be $\lceil \frac{n(n+2)}{8} \rceil$ connected components. But I somehow found that the way that 8-mino tiling the plane is not optimal for special $n$ ’s. However, construction can be completed by comparing Alice’s strategy.

Interesting. I actually haven't tried to generalize this since the natural generalization of the strategies gives that the answer is $n^2/8 + O(n)$ and I don't like to calculate the $O(n)$ term :p
I'd like to know how you calculate the exact answer if you feel like explaining your idea though

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

liekkas

370 posts

liekkas

#48 h Dec 27, 2018, 2:02 PM • 3 Y

Y by USJL, Adventure10, Mango247

USJL wrote:

Interesting. I actually haven't tried to generalize this since the natural generalization of the strategies gives that the answer is $n^2/8 + O(n)$ and I don't like to calculate the $O(n)$ term :p
I'd like to know how you calculate the exact answer if you feel like explaining your idea though

Well, Alice’s construction can be easily generalized that $2n \times 2n$ chessboard can be put $\frac{n(n+1)}{2}$ . For odd lengths, it can be constructed in similar way(the only difference is that any two “consecutive” squares have Euclidean Distance $\sqrt{8}$ , none of $\sqrt{10}$ is used). For Bob’s strategy, I am quite sure that the tiling with $8-mino$ can be constructed by letting any $8-mino$ covers exactly one black square in Alice’s construction, which fulfills the condition. But I didn’t find an elegant way to show it without using induction.

Sorry for not having devices to attach pictures. I will complete it in some days.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.