Does there exist a sequence $ F(1), F(2), F(3), \ldots$ of non-negative integers that simultaneously satisfies the following three conditions? (a) Each of the integers $ 0, 1, 2, \ldots$ occurs in the sequence. (b) Each positive integer occurs in the sequence infinitely often. (c) For any $ n \geq 2,$ \[ F(F(n^{163})) = F(F(n)) + F(F(361)). \]
Problem
Source: IMO Shortlist 1995, S1
Tags: algebra, IMO Shortlist, functional equation, Iteration
mr.danh
11.08.2008 11:14
Answer: Yes
Choose F(1)=0, F(361)=1, the condition (c) will become $ F(F(n^{163})) = F(F(n))$ for every $ n\ge 2$
Construct the sequence as follows:
* $ F(n) = n$ for every $ 2\le n\le 360$
* $ F(n^{163}) = F(n)$ so that the condition (b) is satisfied.
* For remain cases, let F(n) be the smallest of numbers which are other than F(k) with k<n.
There are infinitely numbers not form $ n^{163{}}$, so the condition (a) is satisfied.
We also have $ F(n^{163m}) = F(n)$ for every naturals numbers m, which implies each positive integer appears infinitely often, the condition (b) is satisfied.
The constructed sequence proves the answer "yes"
omegatheo
06.10.2009 19:20
when i click the solution it sends me to the top of the page;it's a problem with my browser?
GaryTam
29.08.2017 04:05
Yes. Just take $F(n)$ to be the number of prime factors of $n$ (counted with multiplicity).
Yes. Just take $F(n)$ to be the number of prime factors of $n$ (counted without multiplicity).
math_pi_rate
27.02.2019 12:55
Nice and easy. Here's my solution (with motivations): Note that, by condition (c), we cannot have $F(n)=0$ for $n \geq 2$. So, using condition $(a)$, we get that $F(1)=0$. To make condition (c) simpler, this motivates us to take $F(361)=1$, which gives $F(F(n^{163}))=F(F(n))$. I first thought about trying to find solutions to the equation $F(n^{163})=F(n)$, which would directly give condition (c). Even though I didn't really think that any function would work, but fortunately on trying the basic functions which I always try while working on any existential NT FE problem, the prime omega function $\omega(n)$ seemed to work (One can also think of this function by noticing the fact that $361$ has only one prime factor, which seems to coincidentally match our assumption that $F(361)=1$). And the problem's done .