Problem 4 of Second round

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Problem 4 of Second round

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: IV International Festival of Young Mathematicians Sozopol 2013, Theme for 10-12 grade

The post below has been deleted. Click to close.

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

437 posts

Pinko

#1 h Jan 22, 2020, 1:20 PM • 1 Y

Y by Adventure10

Let $k<<n$ denote that $k<n$ and $k\mid n$ . Let $f:\{1,2,...,2013\}\rightarrow \{1,2,...,M\}$ be such that, if $n\leq 2013$ and $k<<n$ , then $f(k)<<f(n)$ . What’s the least possible value of $M$ ?

This post has been edited 1 time. Last edited by Pinko, Jan 22, 2020, 1:20 PM

Z K Y

The post below has been deleted. Click to close.

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

2564 posts

#2 h Jan 23, 2020, 3:18 AM • 2 Y

Y by Pinko, Adventure10

Note that

$f(1) << f(2)<< f(4) << \cdots << f(1024)$
This means
$f(1024)\ge 2f(512) \ge 4f(256) \ge \cdots \ge 1024f(1) \ge 1024$
Therefore $M$ is at least $1024$ . Equality can hold; for every $n \in \{1,2,\cdots , 2013\}$ , take $f(n)=2^{a_1+a_2+\cdots + a_t}$ , where $n=p_1^{a_1}p_2^{a_2} \cdots p_t^{a_t}$ is the canonical factorisation of $n$ .

This post has been edited 1 time. Last edited by biomathematics, Jan 23, 2020, 3:20 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a