KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles
Contest Rules
Entry Form
Problems
Results
Previous years

 

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

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley