To each positive integer $ n$ it is assigned a non-negative integer $f(n)$ such that the following conditions are satisfied: (1) $ f(rs) = f(r)+f(s)$ (2) $ f(n) = 0$, if the first digit (from right to left) of $ n$ is 3. (3) $ f(10) = 0$. Find $f(1985)$. Justify your answer.
Problem
Source: Spanish Communities
Tags: Columbia, function, pigeonhole principle, number theory, relatively prime, number theory unsolved
06.04.2006 13:53
$0=f(10)=f(2)+f(5)$; thus $f(5)=0$. Thus $f(1985)=f(5)+f(397)=f(397)$. Now $0=f(3573)=f(9)+f(397)=0$, and the result follows from $f(397)=0$. It's not hard to show that the function is identically $0$ in that way.
16.03.2009 02:02
I'm sorry for reviving this thread, but I'm not quite sure how $ f(2) + f(5) = 0 \implies f(5) = 0$.
16.03.2009 02:06
It follows because $ f(n)$ is non-negative by the problem statement. Indeed, to show that $ f(n)$ is identically zero, simply consider primes ending in $ 2$, $ 5$, ...
16.03.2009 02:55
Note that $ f(10k+r)=f(r)$ so we need only to prove that $ f(1)=f(2)=f(3)=\ldots=f(10)=0$. $ f(10)=f(1)+f(10)=f(2)+f(5)=0\implies f(1)=f(2)=f(5)=f(10)=0$ $ f(4)=f(2)+f(2)=0, f(6)=f(2)+f(3)=0$ $ f(8)=f(2)+f(2)+f(2)+f(2)=0$ $ 0=f(35)=f(5)+f(7)\implies f(5)=f(7)=0$ $ f(9)=f(3)+f(3)=0$ Done.
16.03.2009 07:45
Johan Gunardi wrote: Note that $ f(10k + r) = f(r)$ so we need only to prove that $ f(1) = f(2) = f(3) = \ldots = f(10) = 0$. $ f(10) = f(1) + f(10) = f(2) + f(5) = 0\implies f(1) = f(2) = f(5) = f(10) = 0$ $ f(4) = f(2) + f(2) = 0, f(6) = f(2) + f(3) = 0$ $ f(8) = f(2) + f(2) + f(2) + f(2) = 0$ $ 0 = f(35) = f(5) + f(7)\implies f(5) = f(7) = 0$ $ f(9) = f(3) + f(3) = 0$ Done. Why $ f(10k+r)=f(r)$? It's $ f(rs)=f(r)+f(s)$, not $ f(r+s)=f(r)+f(s)$ $ f(n)=0$ for all $ n$ because WLOG $ n$ is not divisible by $ 2, 5$ $ \Rightarrow$ we can find a positive integer $ x \le 9$ so that the last digit of $ f(nx)$ is $ 3$ $ \Rightarrow f(n)=0$
16.03.2009 09:21
Oopss. Sorry, I was wrong. Let me try again It suffices to prove that every positive integer has a multiple which begins with 3. But it is well known (and easy to prove by pigeonhole) that every positive integer has a multiple of the form 111...1000...0, so it also has a multiple of the form 333...3000...0. QED?
16.03.2009 13:09
Johan Gunardi wrote: Oopss. Sorry, I was wrong. Let me try again It suffices to prove that every positive integer has a multiple which begins with 3. But it is well known (and easy to prove by pigeonhole) that every positive integer has a multiple of the form 111...1000...0, so it also has a multiple of the form 333...3000...0. QED? But the first digit is from right to left.
16.03.2009 15:54
Uh, just consider $ f(2)=f(5)=0$ and $ f(10n+3)=0$ and $ f((10n+1)*3)=0=f(10n+1)$ and $ f((10n+7)*9)=0=f(10n+7)$ and $ f((10n+9)*7)=0=f(10n+9)$ and the result follows.
13.10.2009 04:14
We just need to prove that f(p)=0 for every p prime p=10k+1, 10k+3,10k+5,10k+7,10k+9 for p=10k+5: p=5 =>f(10)=f(5)+f(2)=0 => f(5)=0 => f(p)=0 for p=10k+1: f(3p)=0 => f(3)+f(p)=0=>f(p)=0, because f(3)=0 for p=10k+3: f(p)=0 for p=10k+7: f(9p)=0 => f(p)+f(3)+f(3)=0 => f(P)=0, because f(3)=0 for p=10k+9: f(7p)=0 => f(p) +f(7)=0 => f(p)=0 So, for every x, f(x)=0, because f(p)=0 for every p prime
14.10.2009 12:52
An alternative approach is that $ f(ab) = 0 \Rightarrow f(a) = 0 = f(b).$ Therefore immediate that $ f(2) = 0 = f(5),$ and $ f(2^a5^bx) = f(x).$ But $ x$ relatively prime to both $ 2$ and $ 5 \Rightarrow \exists k \ni xk$ ends in $ 3 \Rightarrow f(xk) = 0 \Rightarrow f(x) = 0 \Rightarrow f(2^a5^bx) = 0.$
07.04.2024 23:11
At first, note that $0=f(10)=f(5\cdot 2)=f(5)+f(2)$. Since $f$ maps to $\mathbb{Z^{+}}\cup{0}$, we get $f(5)=0$. On the other hand $f(1985)=f(5\cdot 397)=f(5)+f(397)=f(397)$, so we just need to calculate $f(397)$. Now, note that $f(3)=0$, and $397\cdot 3^2 \equiv 3 \pmod{10}$, hence, $f(397\cdot 3^2)=f(397)+2f(3)=f(397)$, but given that the last digit of $397\cdot 3^2$ is $3$, we deduce $f(397)=0$, hence, $f(1985)=0$.