Solutions to Problems in Informatics, September 2001

In this page only the sketch of the solutions are published; in some cases only the final results. To achieve the maximum score in the competition more detailed solutions needed.

Sz. 1. We learned from an article of József Bölcsföldi and Géza Balázs (KöMaL Homapage Dec. 2000) that ``already the Pythagoreans knew about numbers that form a friendly pair--which is a pair (a,b) of natural numbers with both numbers being equal to the sum of the proper divisors (i.e. including 1 but excluding the number itself) of the other. Clearly, one number in a friendly pair has many divisors (typed in bold below), while the other one has only few of them. Some friendly pairs include (220, 284), (1184, 1210), (2620, 2924), (5020, 5564), (6232, 6368), (10744, 10856), ...'' Write a program which asks for two natural numbers (N<M<10⁶), then prints all the friendly pairs (a,b) with N<a, b<M. (10 points)

A simplified algorithm can be as follows:

Algorithm Friendly_Pairs
  Input: N, M
The first step is to read the interval,
  Loop from I:=N to M
whose elements are to be tested separately whether there is a corresponding friendly pair in the interval.
    K:=1; J:=2;
where K is the sum of the divisors, and J is the divisor being examined.
    Loop while J*J<I
      If I mod J=0 then K:=K+J+I div J;
      J:=J+1;
We keep on summing up divisors while the divisor is less than or equal to the square root of the number. The divisor (which divides the number, hence division by it gives no remainder) as well as the result of the division is added to the sum.
    End of the loop.
    If (J*J=I) AND (I mod J=0) then K:=K+J
If the number happens to be a perfect square (J*J=I), only the divisor (J) should be added once.
    End of branch
    If (K>I) AND (K<=M)
If the sum of the divisors (K) has not been checked yet, i.e. K>I holds, but it is still a member of the interval, then we have to verify, whether K and I form a friendly pair, i.e. I equals to the sum of the proper divisors of K. (However, concerning efficiency, this is not the best solution, since these numbers are checked many times---when their turn comes.)
      then L:=1; J:=2;
One proceeds as above to compute the sum of the divisors. L will denote the sum of the divisors, and J is the divisor currently examined.
      Loop while J*J<K
        If K mod J=0
          then L:=L+J+K div J;
        End of branch
        J:=J+1;
We have to sum up divisors while the divisor is less than or equal to the square root of the number. The divisor (which divides the number, hence division by it gives no remainder) as well as the result of the division is added to the sum.
      End of loop
      If (J*J=K) AND (K mod J=0) then L:=L+J;
If the number happens to be a perfect square (J*J=K), only the divisor (J) should be added once.
      End of branch
      If I=L
        then Out: I,K
A friendly pair is to be printed if each of them is equal to the sum of the proper divisors of the other. That is K is equal to the sum of the proper divisors of I, and the sum of the proper divisors of K is L. In other words, if I=L.
      End of branch
    End of branch
  End of loop
End of procedure

A sample program in Turbo Pascal:

Program friendly;
  uses newdelay,crt;
  var i,j,k,l,n,m: longint;
begin
  clrscr; writeln('Friendly pairs'); writeln;
  writeln('From'); readln(n);
  writeln('To'); readln(m);
  for i:=n to m do
  begin
    k:=1; j:=2;
    while j<sqrt(i) do
    begin
     if i mod j=0 then k:=k+j+i div j;
     j:=j+1;
    end;
    if (j=sqrt(i)) and (i mod j=0) then k:=k+j;
    if (k>i) and (k<=m) then
    begin
     l:=1; j:=2;
     while j<sqrt(k) do
     begin
      if k mod j=0 then l:=l+j+k div j;
      j:=j+1;
     end;
    if (j=sqrt(k)) and (k mod j=0) then l:=l+j;
    if i=l then writeln(i,'-',k);
  end;
  end;
  readln;
end.

Sz. 2. In most programming languages an ellipse can be displayed by a single command, however this ellipse must have axes parallel to the edges of the screen. Write a program that enables us to draw the ellipse in any position. The parameters are the length of the axes and the angle between the major axis and the upper edge of the screen in degrees. (10 points)

Solution:

Algorithm Ellipse(a,b,angle:Real)
where a denotes the major axis, b is the minor axis, and angle is the angle of rotation.
  c_angle:=0;
  Loop while c_angle<180
Two points are drawn in each turn. Hence we keep on drawing till we reach the half of the ellipse, according to the angle.
    r:=a*b / sqrt(b*b*cos(pi*c_angle/180)*cos(pi*c_angle/180)+
           a*a*sin(pi*c_angle/180)*sin(pi*c_angle/180));
where r is the distance in polar coordinates. To devise this, notice that using x=rcos $alpha$ and y=rsin $alpha$ , the equation of the ellipse becomes $\displaystyle 1={x^2\over a^2}+{y^2\over b^2}={r^2\cos^2\alpha\over a^2}+{r^2\sin^2\alpha\over b^2}$, hence we have $\displaystyle r^2={1\over{{\cos^2\alpha\over a^2}+{\sin^2\alpha\over b^2}}}$ and $\displaystyle r={ab\over\sqrt{b^2\cos\alpha+a^2\sin^2\alpha}}$. Thus
    x:=r*cos(pi*(c_angle-angle)/180);
    y:=r*sin(pi*(c_angle-angle)/180);
Recovering from polar coordinates (together with the rotation) is now an easy task. Then we can write
    PointDraw(MaxX div 2 + Trunc(x),MaxY div 2 + Trunc(y));
    PointDraw(MaxX div 2 - Trunc(x),MaxY div 2 - Trunc(y));
since programming languages can display a single point. All we have to do is to shift the coordinates x and y to the centre of the screen.
    epsilon:=arctan(1/sqrt(x*x+y*y));
    c_angle:=c_angle+epsilon;
The last step before processing the next point is to compute the angle of rotation as well as the new angle. Let $epszilon$ be the angle of rotation which is defined as the smallest visible angle on the screen: falling into a neighbouring pixel without leaving out any adjacent one. In other words, we advance 1 pixel into the direction perpendicular to the line from the centre. The length of this line is just $\displaystyle \sqrt{x^2+y^2}$.
  End of loop;
End of procedure; {Ellipse}

Sz. 3. We deposit our savings for N years (1 $le$ N $le$ 10) according to the following: 1. Throughout N years, at the beginning of every month we place A Forints into the bank, and lock it up for one year at a rate of interest X percent (X>0 a real number). 2. When the lockup is over, at the beginning of the next month we get the yearly interest, which is put back and locked up again for one year together with our savings so far. Make a sheet (named PENZ.XLS) which the numbers N, A and X can be entered into, then our bank balance is calculated throughout N years. The sheet should contain exactly N rows, that is unnecessary rows should not be visible even if N is changed. Example (with N=3, A=1000, X=10)

1st year: 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 11000 12000

2nd year: 13100 14200 15300 16400 17500 18600 19700 20800 21900 23000 24100 25200

3rd year: 26410 27620 28830 30040 31250 32460 33670 34880 36090 37300 38510 39720

(10 points)

Solution.

There is no problem with static cells (i.e. cells with constant content). However, in the case of dynamically changing cells, we have to use functions whose values will be displayed.

During the solution, a cell can get a value only if that cell is in the row of a year to be printed. I.e. the cell is empty or contains a value depending on the position of the given row. We achieve this by using the function IF(condition; is true, is false). Let us put the condition into shape. We will make use of another function, namely the function ROW(cell), which gives the number of the row of that cell. That is, our condition will contain the number of the row of the given cell. It is printed only when necessary (otherwise nothing is displayed), thus, when the number of the year (number of the row minus number of the first row) is less than or equal to the number of years to be printed (which is always in cell G1, that is why a $ sign is needed in front of the row and the column marks.)

It is harder to decide what to print. Divide the problem into two parts, then write a conditional printout for both groups of three columns in the two tables. The first and second column contain (for both tables) only whether the number of the given year and the text "...th year" is displayed or not, according to the condition above.

Now the hard part of the problem follows. In the first table we give---for the given year (row) and given month (column/cell)---the amount of payable money, the capital newly invested and the amount of interest. The second table contains the money we gathered. We compute the amount of our money in the bank in a given month of a given year by using the first table as follows. Sum the values in the first table in the given year (row) till the given month (column/cell), and take also into consideration the amount corresponding to the unaccounted months of the previous year.

Hence the solution reads

A4: "=IF(ROW(A4)-3$<$=$G$1;ROW(A4)-3;"")" till A13.

B4: "=IF(ROW(B4)-3$<$=$G$1;"th year:";"")" till B13.

C4: "=IF(ROW(B4)-3$<$=$G$1;$C$1+C3*$E$1/100+C3;"")" till N13.

A24: "=IF(ROW(A24)-23$<$=$G$1;ROW(A24)-23;"")" till A33.

B24: "=IF(ROW(B24)-23$<$=$G$1;"th year:";"")" till B33.

C24: "=IF(ROW(B24)-23$<$=$G$1;SUM(D3:$N3)+SUM($C4:C4);"")" till N33.

Already signed up?
New to KöMaL?