MathDB
Problems
Contests
International Contests
Tournament Of Towns
1989 Tournament Of Towns
(219) 3
(219) 3
Part of
1989 Tournament Of Towns
Problems
(1)
TOT 219 1989 Spring S3 composition of 1000 linear functions
Source:
3/7/2021
Given
1000
1000
1000
linear functions
f
k
(
x
)
=
p
k
x
+
q
k
f_k(x)=p_k x + q_k
f
k
(
x
)
=
p
k
x
+
q
k
where
k
=
1
,
2
,
.
.
.
,
1000
k = 1 , 2 ,... , 1000
k
=
1
,
2
,
...
,
1000
, it is necessary to evaluate their composite
f
(
x
)
=
f
1
(
f
2
(
f
3
.
.
.
f
1000
(
x
)
.
.
.
)
)
f(x) =f_1 (f_2(f_3 ... f_{1000}(x)...))
f
(
x
)
=
f
1
(
f
2
(
f
3
...
f
1000
(
x
)
...
))
at the point
x
0
x_0
x
0
. Prove that this can be done in no more than
30
30
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
p_1 , p_2 ,... ,p_{1000}, q_l , q_2 ,... ,q_{1000} , x_o
p
1
,
p
2
,
...
,
p
1000
,
q
l
,
q
2
,
...
,
q
1000
,
x
o
).{S. Fomin, Leningrad)
composition
function