Maths Olympiad Prep

Library / /17 of 37

Algebra Difficulty 6.7 National olympiad Find the answer

Let f:NNf: \mathbb{N} \rightarrow \mathbb{N} be a function satisfying the following conditions:
(1) f(1)=1f(1)=1;
(2) nN\forall n\in \mathbb{N}, 3f(n)f(2n+1)=f(2n)(1+3f(n))3f(n) f(2n+1) =f(2n) ( 1+3f(n) );
(3) nN\forall n\in \mathbb{N}, f(2n)<6f(n)f(2n) < 6 f(n).
Find all solutions of equation f(k)+f(l)=293f(k) +f(l)=293, where k<lk<l.
(N\mathbb{N} denotes the set of all natural numbers).

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let f:NN f: \mathbb{N} \rightarrow \mathbb{N} be a function satisfying the following conditions:
1. f(1)=1 f(1) = 1 ;
2. For all nN n \in \mathbb{N} , 3f(n)f(2n+1)=f(2n)(1+3f(n)) 3f(n) f(2n+1) = f(2n) (1 + 3f(n)) ;
3. For all nN n \in \mathbb{N} , f(2n)<6f(n) f(2n) < 6 f(n) .

We need to find all solutions of the equation f(k)+f(l)=293 f(k) + f(l) = 293 where k<l k < l .

By induction, we can show that f(2n)=3f(n) f(2n) = 3f(n) and f(2n+1)=3f(n)+1 f(2n+1) = 3f(n) + 1 . Using these properties, we can compute the values of f(n) f(n) for various n n :

f(1)=1,f(2)=3,f(3)=4,f(4)=9,f(5)=10,f(6)=12,f(7)=13,f(8)=27,f(9)=28,f(10)=30,f(11)=31,f(12)=36,f(13)=37,f(14)=39,f(15)=40,f(16)=81,f(17)=82,f(18)=84,f(19)=85,f(20)=90,f(21)=91,f(22)=93,f(23)=94,f(24)=108,f(25)=109,f(26)=111,f(27)=112,f(28)=117,f(29)=118,f(30)=120,f(31)=121,f(32)=243,f(33)=244,f(34)=246,f(35)=247,f(36)=252,f(38)=255,f(39)=256,f(40)=270,f(41)=271,f(42)=273,f(43)=274,f(44)=279,f(45)=280,f(46)=282,f(47)=283. \begin{aligned} f(1) &= 1, \\ f(2) &= 3, \\ f(3) &= 4, \\ f(4) &= 9, \\ f(5) &= 10, \\ f(6) &= 12, \\ f(7) &= 13, \\ f(8) &= 27, \\ f(9) &= 28, \\ f(10) &= 30, \\ f(11) &= 31, \\ f(12) &= 36, \\ f(13) &= 37, \\ f(14) &= 39, \\ f(15) &= 40, \\ f(16) &= 81, \\ f(17) &= 82, \\ f(18) &= 84, \\ f(19) &= 85, \\ f(20) &= 90, \\ f(21) &= 91, \\ f(22) &= 93, \\ f(23) &= 94, \\ f(24) &= 108, \\ f(25) &= 109, \\ f(26) &= 111, \\ f(27) &= 112, \\ f(28) &= 117, \\ f(29) &= 118, \\ f(30) &= 120, \\ f(31) &= 121, \\ f(32) &= 243, \\ f(33) &= 244, \\ f(34) &= 246, \\ f(35) &= 247, \\ f(36) &= 252, \\ f(38) &= 255, \\ f(39) &= 256, \\ f(40) &= 270, \\ f(41) &= 271, \\ f(42) &= 273, \\ f(43) &= 274, \\ f(44) &= 279, \\ f(45) &= 280, \\ f(46) &= 282, \\ f(47) &= 283. \end{aligned}

From these values, we find the pairs (k,l)(k, l) such that f(k)+f(l)=293 f(k) + f(l) = 293 and k<l k < l . The valid pairs are:
(5,47),(7,45),(13,39),(15,37). (5, 47), (7, 45), (13, 39), (15, 37).

The answer is: \boxed{(5, 47), (7, 45), (13, 39), (15, 37)}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.