From the first condition, $a_1=1$. We use induction to show that $a_n=n$ for all positive integers $n$. Suppose this is true for all $n<k$. Let $a_k=t$. Note $a_{k^m}=t^m$. If $t<k$, then for any $m>k$, there are at most $m-1$ distinct values in $(a_1,a_2,...,a_m)$, and this contradicts the second condition. If $t\ge k$, then take a sufficiently large $n$ that satisfies the second condition. Let $m$ be the largest number such that $k^m\le n$. Then, $a_{k^m}\le n\implies t^m\le n$. On the other hand, $n<k^{m+1}$, so $t^m<k^{m+1}\implies (\frac{t}{k})^m<k$. Taking a sufficiently large $n$, this is false unless $t=k$. Thus, $a_n=n$ for all $n$ which obviously works.

woo

Clearly $a_1 = 1$. Let $x$ be the smallest positive integer such that $a_1, a_2, \cdots, a_x$ is not a permutation of $x$. It is clear that this implies $a_ i = i$ for $i < x$ by a simple induction. Unless $x$ is prime, it splits into two proper factors which from the multiplicative condition yields that $a_x = x$, impossible. Thus such a $x$ must be prime (this is not terribly important but it feels right to me to make this obvious exclusion). Rename this $x$ to $p$ and note that $a_p \geqslant p+1$. Note that $a_{p^t} = a_p^t \geqslant (p+1)^t$. Let $n$ be a positive integer such that $a_1, a_2, \cdots, a_n$ are a permutation of $1, 2, \cdots, n$. Let $\ell$ be maximal with the property that $p^{\ell} \leqslant n$ and fix $u$ largest so that $up^{\ell} \leqslant n$. Then $n \geqslant a_{up^{\ell}} \geqslant u(p+1)^{\ell}$. Clearly $n < (u+1)p^{\ell}$, which yields $(u+1)p^{\ell} > u(p+1)^{\ell}$ or \[10^{1000} > 1+\frac{1}{u} > \left(1+\frac{1}{p}\right)^{\ell}\]However since there are infinitely many such $n$, $\ell$ is unbounded in the inequality above and this is a contradiction.

gghx wrote: From the first condition, $a_1=1$. We use induction to show that $a_n=n$ for all positive integers $n$. Suppose this is true for all $n<k$. Let $a_k=t$. Note $a_{k^m}=t^m$. If $t<k$, then for any $m>k$, there are at most $m-1$ distinct values in $(a_1,a_2,...,a_m)$, and this contradicts the second condition. If $t\ge k$, then take a sufficiently large $n$ that satisfies the second condition. Let $m$ be the largest number such that $k^m\le n$. Then, $a_{k^m}\le n\implies t^m\le n$. On the other hand, $n<k^{m+1}$, so $t^m<k^{m+1}\implies (\frac{t}{k})^m<k$. Taking a sufficiently large $n$, this is false unless $t=k$. Thus, $a_n=n$ for all $n$ which obviously works. nvm

starchan wrote: gghx wrote: From the first condition, $a_1=1$. We use induction to show that $a_n=n$ for all positive integers $n$. Suppose this is true for all $n<k$. Let $a_k=t$. Note $a_{k^m}=t^m$. If $t<k$, then for any $m>k$, there are at most $m-1$ distinct values in $(a_1,a_2,...,a_m)$, and this contradicts the second condition. If $t\ge k$, then take a sufficiently large $n$ that satisfies the second condition. Let $m$ be the largest number such that $k^m\le n$. Then, $a_{k^m}\le n\implies t^m\le n$. On the other hand, $n<k^{m+1}$, so $t^m<k^{m+1}\implies (\frac{t}{k})^m<k$. Taking a sufficiently large $n$, this is false unless $t=k$. Thus, $a_n=n$ for all $n$ which obviously works. Hi this seems to have a slight bug in it at the very end. If $t = k+1$, which is possible, you are saying that the mentioned inequality, which rewrites as $(k+1)^m < k^{m+1}$ fails to hold for large $n$. This is clearly false. $k^{m+1}$ infact exceeds $(k+1)^m$ for all large enough inputs of $m$. Hmm really? We can write $k^{m+1}>(k+1)^m\iff k>(\frac{k+1}{k})^m$, and the LHS is constant while the RHS can grow very large, right? A quick check with desmos seems to imply this as well.

gghx wrote: starchan wrote: gghx wrote: From the first condition, $a_1=1$. We use induction to show that $a_n=n$ for all positive integers $n$. Suppose this is true for all $n<k$. Let $a_k=t$. Note $a_{k^m}=t^m$. If $t<k$, then for any $m>k$, there are at most $m-1$ distinct values in $(a_1,a_2,...,a_m)$, and this contradicts the second condition. If $t\ge k$, then take a sufficiently large $n$ that satisfies the second condition. Let $m$ be the largest number such that $k^m\le n$. Then, $a_{k^m}\le n\implies t^m\le n$. On the other hand, $n<k^{m+1}$, so $t^m<k^{m+1}\implies (\frac{t}{k})^m<k$. Taking a sufficiently large $n$, this is false unless $t=k$. Thus, $a_n=n$ for all $n$ which obviously works. Hi this seems to have a slight bug in it at the very end. If $t = k+1$, which is possible, you are saying that the mentioned inequality, which rewrites as $(k+1)^m < k^{m+1}$ fails to hold for large $n$. This is clearly false. $k^{m+1}$ infact exceeds $(k+1)^m$ for all large enough inputs of $m$. Hmm really? We can write $k^{m+1}>(k+1)^m\iff k>(\frac{k+1}{k})^m$, and the LHS is constant while the RHS can grow very large, right? Oh darn. nvm

Let's call all $n$ satisfying $(ii)$ as $\text{smart}$ We will first state the crucial claim which will finish.. Claim - $a_{k} \le k$ for all natural $k$ Proof - Suppose assume FTSOC that $a_{k} > k$ for some natural $k$ , then note that for all natural $x$ we have $a_{k^x} = {a_{k}}^x$ , Now choose a smart $N > k^{x}$ , then $a_{k^x} = {a_{k}}^x < N$ , this implies there does not exist any smart number in the interval $( k^{x} , {a_{k}}^x )$ , but as $k$ is fixed , so for each arbitrarily large smart number $i$ we can choose a natural number $x$ s $$\frac{log i}{log a_{k}}>x>\frac{log i}{log k}$$, implying that there exist a smart number in the abovementioned interval, which is a contradiction. $\blacksquare$ Now note that no $2$ $a_{i}'s$ can be equal , which combined with the above claim and using $a_{1} = 1$ , we get $a_{n} = n$ for all natural $n$. $\blacksquare$ Hope its fixed @2 below..

Claim 1: $a_m=a_n \iff m=n$. Proof: If $m=n$, then obviously $a_m=a_n$. Suppose $a_m=a_n$ and $m \neq n$. WLOG let $m >n$, then there can't be any integer greater or equal than $m$ that satisfies the second condition, therefore there won't be infinite integers which satisfy the condition, which contradicts the statement of the problem, therefore if $a_m=a_n$ then $m=n$. Claim 2: $m \mid n \iff a_m \mid a_n$. Proof: Note that $a_m \mid a_n \iff a_n=a_m \cdot k$. Now choose $t$ that satisfies the second condition and $t \geq k$, then there must be an integer $i$ such that $a_i=k$. Then $a_n=a_m \cdot k =a_m \cdot a_i=a_{mi}$, but by claim 1 we have that $n=mi \iff m\mid n$. Suppose $a_x=y$ and $x\neq y$. Then choose $z=xy+w$ such that it satisfies the second condition. Then there must be the same number of multiples of $y$ in $(1,2,\dots,z)$ as multiples of $a_x$ in $(a_1,a_2,\dots,a_z)$. There are $\left\lfloor\frac{z}{y}\right\rfloor$ multiples of $y$ in $(1,2,\dots,z)$, and by claim 2, there will be $\left\lfloor \frac{z}{x} \right\rfloor$ multiples of $a_x$ in $(a_1,a_2,\dots,a_z)$. Therefore $$\left\lfloor \frac{xy+w}{y} \right\rfloor=\left\lfloor \frac{xy+w}{x} \right\rfloor,$$simplifying we get $$x+\left\lfloor\frac{w}{y}\right\rfloor=y+\left\lfloor\frac{w}{x}\right\rfloor.$$If $x>y$ then $$\frac{w}{y} >\frac{w}{x} \implies \left\lfloor\frac{w}{y}\right\rfloor \geq \left\lfloor\frac{w}{x}\right\rfloor,$$therefore $$x+\left\lfloor\frac{w}{y}\right\rfloor>y+\left\lfloor\frac{w}{x}\right\rfloor.$$Similarly if $y>x$ then $$y+\left\lfloor\frac{w}{x}\right\rfloor >x+\left\lfloor\frac{w}{y}\right\rfloor.$$Since both of these are impossible, we arrive at a contradiction, therefore $a_x=x$ for all positive integers $x$.

MatBoy-123 wrote: this implies there does not exist any smart number in the interval $( k^{x} , {a_{k}}^x )$ , but as $k$ is fixed we can choose $x$ to be arbitrarily large which is a contradiction to the statement that there exist infinite smart numbers. You need to prove that these ranges will "fill" up everything in $\mathbb{N}$ after a certain point. However, the ranges $(k^x,(k+1)^x)$ and $(k^{x+1},(k+1)^{x+1})$ may not intersect. (It is possible to prove that after a certain $x$ they do (see my post), but i think its a non-trivial part of the problem that cannot be skipped).

EMC 2014 P4 Junior Level https://artofproblemsolving.com/community/c6h617551p3680596