Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
 Already signed up? New to KöMaL?

# Exercises and problems in InformaticsDecember 2003

I. 64. The Farey sequence FN for any positive integer N is the sequence of irreducible rational numbers between 0 and 1 for which the denominator is at most N and they are arranged in increasing order. For example, $\displaystyle F_6=\left\{\frac{0}{1},\, \frac{1}{6},\,\frac{1}{5},\,\frac{1}{4},\,\frac{1}{3},\, \frac{2}{5},\,\frac{1}{2},\,\frac{3}{5},\,\frac{2}{3},\, \frac{3}{4},\,\frac{4}{5},\,\frac{5}{6},\,\frac{1}{1} \right\}.$

For any given N (1$\displaystyle \le$N $\displaystyle \le$100), your program (i64.pas, ...) should display the Farey sequence FN.

(10 points)

I. 65. Given N+1 points (xi,yi) in the plane, a Bézier curve nicely approximating them is given by its coordinate-functions x and y in the following parametric form (with 0$\displaystyle \le$u $\displaystyle \le$1 being a real parameter):

$\displaystyle x(u)=\sum_{i=0}^nx_i{n\choose i}u^i(1-u)^{n-i},\quad y(u)=\sum_{i=0}^ny_i{n\choose i}u^i(1-u)^{n-i}.$

Write your program (i65.pas, ...) which reads the coordinates of the N+1 points then draws them together with the corresponding Bézier curve.

Example.:

N=14 The points: (0,0),(16,40),(25,45), (36,65),(49,70),(64,80), (81,90),(100,100),(121,120), (144,120),(169,120),(196,140), (225,150),(256,160),(289,170)

(10 points)

I. 66. Euler's number triangle is similar to Pascal's triangle, but instead of the binomial coefficients, it contains the Eulerian numbers E(n,k). For 0$\displaystyle \le$n $\displaystyle \le$15 and 0$\displaystyle \le$k $\displaystyle \le$n, E(n,k) is defined as the number of permutations of {1,2,...,n} having exactly k permutation ascents (i.e. having k pairs of adjacent positions in the permutation that are out of order).

Prepare your sheet (i66.xls) that - on entering the value of m (0$\displaystyle \le$m$\displaystyle \le$15) into cell <<\texttt>>A1 - displays the Eulerian numbers E(n,k) (n=0,1,...,m) in the first n+1 rows of the sheet. Numbers should only appear in valid cells.

Example for m=10:

 10 0 1 2 3 4 5 6 7 8 9 10 0 1 1 1 0 2 1 1 0 3 1 4 1 0 4 1 11 11 1 0 5 1 26 66 26 1 0 6 1 57 302 302 57 1 0 7 1 120 1191 2416 1191 120 1 0 8 1 247 4293 15619 15619 4293 247 1 0 9 1 502 14608 88234 156190 88234 14608 502 1 0 10 1 1013 47840 455192 1310354 1310354 455192 47840 1013 1 0

(10 points)