Let $f:\mathbb{N}\to\mathbb{R}_{>0}$ be a given increasing function that takes positive values. For any pair $(m,n)$ of positive integers, we call it disobedient if $f(mn)\neq f(m)f(n)$. For any positive integer $m$, we call it ultra-disobedient if for any nonnegative integer $N$, there are always infinitely many positive integers $n$ satisfying that $(m,n), (m,n+1),\ldots,(m,n+N)$ are all disobedient pairs. Show that if there exists some disobedient pair, then there exists some ultra-disobedient positive integer. Proposed by usjl
Problem
Source: 2023 Taiwan TST Round 1 Independent Study 1-A
Tags: Taiwan, cringe
16.03.2023 06:13
Let's prove by contradiction, and suppose that there exists some disobedient pair, but there doesn't exist some ultra-disobedient positive integer. We can see that $f(1)=1$, otherwise $1$ is ultra-disobedient. If $m$ is not ultra-disobedient, then $\exists N$ s.t. $\not\exists n$ s.t. $(m, n), (m, n+1), \dots, (m, n+N)$ are disobedient. (Note that it is not the contrary of the definition of ultra-disobedient, but can be easily derived.) Let $N_m$ denote such $N$ with respective to $m$, and $g^+_m(n):=$ the smallest $k$ s.t. $(m, n+k)$ is not disobedient, $g^-_m(n):=$ the smallest $k$ s.t. $(m, n-k)$ is not disobedient. It's easy to see that $g^+_m(n)\leq N_m, g^-_m(n)\leq N_m$. Define $h^+_m(n):=m(n+g^+_m(n)), h^-_m(n)$. By the definition of $g^+$ and $g^-$ we know that $f(h^+_m(n))=f(m)f(n+g^+_m(n))$ and $f(h^-_m(n))=f(m)f(n-g^-_m(n))$. Since $f$ is increasing, we have $f(h^+_m(n))\geq f(m)f(n)\geq f(h^-_m(n))$. Lemma: $\forall\gcd(a, b)=1,\ a, b>1$, $\frac{\log a}{\log b}=\frac{\log(f(a))}{\log(f(b))}$. Proof: Suppose that $\exists\gcd(a, b)=1,\ a, b>1$ s.t. $\frac{\log a}{\log b}\neq\frac{\log(f(a))}{\log(f(b))}$. WLOG suppose $\frac{\log a}{\log b}<\frac{\log(f(a))}{\log(f(b))}$. Since $\mathbb Q$ is dense, $\exists c, d\in\mathbb N$ s.t. $\frac{\log a}{\log b}<\frac cd<\frac{\log(f(a))}{\log(f(b))}$. $\forall\epsilon_a>1$, take $K_a$ s.t. $\frac{K_a+N_a}{K_a}<\sqrt[d]{\epsilon_a}$, we can see that $\forall k\geq K_a, (h^+_a)^d(k)<\epsilon_aa^d$. $\forall\epsilon_b>1$, take $K_b$ s.t. $\frac{K_b-N_b}{K_b}>\frac1{\sqrt[c]{\epsilon_b}}$, we can see that $\forall k\geq K_b, (h^-_b)^c(k)>\frac{b^c}{\epsilon_b}$. Let $\epsilon_a\epsilon_b<\frac{b^c}{a^d}$, and we get that $\forall k\geq\max(K_a, K_b),\ (h^+_a)^d(k)<\epsilon_aa^d<\frac{b^c}{\epsilon_b}<(h^-_b)^c(k)$. But $f((h^+_a)^d(k))\geq f(a)^df(k)>f(b)^cf(k)\geq f((h^-_b)^c(k))$, contradicts to that $f$ is increasing. $\therefore$ the lemma holds. By the lemma, $\exists c$ s.t. $f(n)=n^c$. $\therefore f(n)f(m)=n^cm^c=f(nm)$, but there is no disobedient pair, and this finishes the proof.
16.03.2023 06:47
USJL wrote: Let $f:\mathbb{N}\to\mathbb{R}_{>0}$ be a given increasing function that takes positive values. For any pair $(m,n)$ of positive integers, we call it disobedient if $f(mn)\neq f(m)f(n)$. For any positive integer $m$, we call it ultra-disobedient if for any nonnegative integer $N$, there are always infinitely many positive integers $n$ satisfying that $(m,n), (m,n+1),\ldots,(m,n+N)$ are all disobedient pairs. Show that if there exists some disobedient pair, then there exists some ultra-disobedient positive integer. Proposed by usjl How Did You came up with the question
16.03.2023 07:01
SaintBroseph wrote: USJL wrote: Let $f:\mathbb{N}\to\mathbb{R}_{>0}$ be a given increasing function that takes positive values. For any pair $(m,n)$ of positive integers, we call it disobedient if $f(mn)\neq f(m)f(n)$. For any positive integer $m$, we call it ultra-disobedient if for any nonnegative integer $N$, there are always infinitely many positive integers $n$ satisfying that $(m,n), (m,n+1),\ldots,(m,n+N)$ are all disobedient pairs. Show that if there exists some disobedient pair, then there exists some ultra-disobedient positive integer. Proposed by usjl How Did You came up with the question There is an old FE question that says that all completely multiplicative increasing functions on $\mathbb{N}$ are of the form $f(n)=n^c$ for some $c>0$. An even harder question asks to determine all multiplicative increasing functions on $\mathbb{N}$. The technique there basically proves a much stronger statement, and this problem is just some setting where the technique proves to be useful. When I have time, I will talk about how I came up with the problems here: https://www.overleaf.com/read/bfbzksthmydz.