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.