MathDB

Given

1000

linear functions

f_k(x)=p_k x + q_k

where

k = 1 , 2 ,... , 1000

, it is necessary to evaluate their composite

f(x) =f_1 (f_2(f_3 ... f_{1000}(x)...))

at the point

x_0

. Prove that this can be done in no more than

30

steps, where at each step one may execute simultaneously any number of arithmetic operations on pairs of numbers obtained from the previous step (at the first step one may use the numbers

p_1 , p_2 ,... ,p_{1000}, q_l , q_2 ,... ,q_{1000} , x_o

).
{S. Fomin, Leningrad)

Problem Statement