Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?
I want the old design back!!! :-)

Exercises and problems in Informatics
December 2003

Please read The Conditions of the Problem Solving Competition.

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)


Send your solutions to the following e-mail address:

Deadline: 13 January 2004