Let $f: \mathbb{N} \rightarrow \mathbb{N}$ be a function satisfying the following conditions: (1) $f(1)=1$; (2) $\forall n\in \mathbb{N}$, $3f(n) f(2n+1) =f(2n) ( 1+3f(n) )$; (3) $\forall n\in \mathbb{N}$, $f(2n) < 6 f(n)$. Find all solutions of equation $f(k) +f(l)=293$, where $k<l$. ($\mathbb{N}$ denotes the set of all natural numbers).
Problem
Source: China mathematical olympiad 1995 problem2
Tags: function, algebra unsolved, algebra, functional equation
15.09.2013 15:46
$3f(n)$ and $1+3f(n)$ are coprime. $3f(n)|f(2n)$ and $f(2n)<6f(n)$ yield $f(2n)=3f(n)$ and $f(2n+1)=3f(n)+1$. If we represent $n$ in base $2$, $f(n)$ is the number explained in base $3$. For example, $n=24=11000_2$, then $f(n)=11000_3=108$. Now $293=101212_3$. We will have four solutions $k=1111_2=15,l=100101_2=37$ $k=1101_2=13,l=100111_2=39$ $k=111_2=7,l=101101_2=45$ $k=101_2=5,l=101111_2=47$
21.09.2013 07:37
wow, very-very beautiful! I think I can not solve the function.
04.01.2020 20:37
Not necessarily a "tough" problem to solve, but... just wow... Putting $n=1$ in condition 2 gives us $3f(1)f(3)=f(2)(1+3f(1)) \implies 3f(3)=4f(2) \implies 3 \mid f(2)$ but $f(2)<6 \implies f(2)=3$ and $f(3)=4$. Trying out a couple more values of $n$ gives us the hint to use $3f(n) \mid f(2n)$, as $\text{gcd}(3f(n),3f(n)+1)=1$, and by condition 3, $f(2n)=3f(n)$, thus $f(2n+1)=3f(n)+1$. Hence every $f(n)$ is uniquely determined by preceding $n$, and as initial value is fixed to be $1$, our aim is simply to find one function satisfying conditions 2 and 3. Okay, so trying out a few values gives us $f(2)=3$, $f(4)=9$, and so on- of course, that's obvious, as $f(2n)=3f(n) \implies f(2^k)=3^k$. Huh, that's a weird function... by $f(2n+1)=3f(n)+1$, we also have $f(2^k+1)=3^k+1$ for $k>0$, but computing $f(7)$ doesn't seem suggestive of some nice polynomial-type or even semi-standard property. Honestly, it's almost pure luck on when the idea strikes you; you could easily spend half an hour more at this stage of the problem with virtually no headway- luckily enough for me, I'd recently heard of a Tower-of-Hanoi like problem a few days back, and thus the problem, with one breakthrough, gets reduced to mere computation: The trick is to look at the digits of a number in binary, and now treat the string of numbers as if they were in ternary- for example, $f(5)=f(101_2) \rightarrow 101_3=9+0+1=10$. Clearly this satisfies both the condition of the recursive and more importantly all conditions specified in the original problem, thus it's the required function. As for the actual problem, note $293_{10}=101212_3$. Note there is no "carry-forward" while adding 2 $f(x)$ in base-3 as they only consist of 1s and 0s as digits. Thus the format of the numbers must be (_0_1_1), where the _ can be 0 or 1, thus there'll be 8 solutions altogether: $(101111,000101)_3,(101101,000101)_3,(100111,001101)_3,(001111,100101)_3$ and permutations (conversion to denary is left as an exercise to the readers ) @below we get the permutations of the solutions too, aka if $(k,l)$ is a solution then so is $(l,k)$. And no they certainly aren't twin primes.
04.01.2020 21:57
3f(n) and 1+3f(n) are twin primes. f(2n+1) = 3f(n) + 1 By this property we get 4 solution,... as I see xxp said.
04.01.2020 22:44
Bad problem $293$ is far too less jred wrote: Let $f: \mathbb{N} \rightarrow \mathbb{N}$ be a function satisfying the following conditions: (1) $f(1)=1$; (2) $\forall n\in \mathbb{N}$, $3f(n) f(2n+1) =f(2n) ( 1+3f(n) )$; (3) $\forall n\in \mathbb{N}$, $f(2n) < 6 f(n)$. Find all solutions of equation $f(k) +f(l)=293$, where $k<l$. ($\mathbb{N}$ denotes the set of all natural numbers). The valid pairs are $(5,47),(7,45),(13,39),(15,37)$.Note by induction $f(2n)=3f(n)$ and $f(2n+1)=3f(n)+1$
@2above $k<\ell$ ...