Let us consider a function `P_n(x,y)` of two integer variables
`x` and `y`, defined by the following expression:

`P_n(x,y) = a_0 + a_1 x + a_2 y + a_3 y^2 + a_4 xy + a_5 y^2
+ a_6 x^3 +
a_7 x^2 y + a_8 x y^2 + a_9 y^3 + ...
+ a_m x^n +
a_(m+1) x^(n+1) y + a_(m+2) x^(n-2) y^2 + ...
+ a_(k-1) x
y^(n-1) + a_k y^n,`

where `a_0, a_1, a_2, ..., a_k` are integers, `n >= 1`.

Write a program, that

a) inputs a value of `n` and coefficients `a_0, a_1,
a_2, ..., a_k,` which are necessary to define the function `P_n(x,y);`

b) inputs values of `X` and `Y; `calls the subroutine
described in problem 2 in order to compute the value of `P_n(x,y)`
at `x=X` and `y=Y,` and outputs the obtained result;

c) calls the subroutines described in problems 3 and 4, and outputs the results found there.

Write a program, that computes the value of `P_n(x,y)`using the
minimal number of additions and multiplications.

Write a program, that computes the elements `b_i` of an array
`B, i=0,1,2,...,I,` where `b_i` is the smallest number from
among the numbers `P_n(i,0), P_n(i,1), ..., P_n(i,Y).` The numbers
`I` and `Y` should be entered into your program before
calling the subroutine.

Write a program, that finds out all the samples `{b_(i_1), b_(i_2),
..., b_(i_p): i_1 < i_2 < ... < i_p, 1 <= p <= I} `from
among the elements of B (defined in problem 3), so that the relation `b_(i_1)
+ b_(i_2) + ... + b_(i_p) = M `holds. The number `M` should
be entered into your program before calling the subroutine.

Given are `n` objects, `a_1, a_2, ..., a_n, (3 <= n <=
20)`. No any two of them have the same weight. We use the notation
`(i,j)` to indicate that the object `a_i `is lighter
than `a_j (i <> j, 1 <= i <= n, 1 <= j <= n). `For
example, at `n=6`, the pairs {(5,1), (5,3), (1,4), (4,6)} mean that
`a_5` is lighter than `a_1 `and `a_3`, `a_1`
is ligther than `a_4` and `a_4` is lighter than `a_6`.

After weighing, several relations of the above type are recordered.

Write a program, that inputs the number n of the objects and the recordered relations, calls subsequently subroutines for solving problems 2, 3 and 4, and outputs the obtained results.

Find out how to order the objects, so that any object will precede all the objects heavier than it. For the above given data, an example of ordering is (5, 1, 2, 4, 3, 6).

Find out how many new weighings have to be made, so that all the objects could be arranged in an increasing order. The number of the additional measurements should be minimal.

Let all the necessary additional weighings have been made. Input their values and perform full ordering of the objects in an increasing order.

Source: Obuchenieto po matematika, journal published by Bulgarian Ministry
of Education, n. 3, 1986, pp. 55-56.

© The text is translated from Bulgarian by Emil
Kelevedzhiev (keleved@math.bas.bg)

Return to the Home
Page of Bulgarian Mathematics and Informatics Competitions.