Exercises and problems in Informatics October 2004

Please read The Rules of the Problem Solving Competition.

New exercises of sign I

I. 88. Suppose we are given the vectors w₁, w₂, ...,w_n and a binary tree of depth n. We travel from its root to one of its leaves. The k^th vector w_k is selected if and only if we have turned left at the k^th node of the tree. The selected vectors are then summed up at each leaf.

Write your program (i88.pas, ...) that displays in the same figure the endpoints of all the vector-sums corresponding to each of the leaves of the binary tree of depth n, if the positive integer n and the vectors w₁, w₂, ..., w_n are given.

As a particular example, consider the vectors w₁, w₂,..., w_n with

\(\displaystyle \mathbf{w}_{k}=\left[\big(1/\sqrt{2}\,\big)^{k};k\cdot\frac{3\pi}{4}\right] \)

in polar coordinates, where the polar form w=[r,\(\displaystyle \alpha\)], as it is well-known, can be represented in Cartesian coordinates as w=(r^.cos \(\displaystyle \alpha\); r^.sin \(\displaystyle \alpha\)). Consider the corresponding figures for n=4,..., 15. (10 points)

I. 89. Notice that the first few powers of 5 can be represented as sum of squares as follows: 5¹=5=1+4=1²+2², 5²=25=9+16=3²+4², 5³=125=100+25= 10²+5².

a) Using a program or a table, find the number of integer solutions of equation kⁿ=x²+y², if k and n are fixed (k=2,..., 9, n=1,..., 10).

b) Could you also derive a formula for the number of solutions?

c) Can you make a program that checks your conjecture even for n=15, 30, 50 or 100?

Your program or Excel sheet (i89.pas, i89.xls, ...) is to be submitted.

(For parts a) and b), a maximum of 10 points can be awarded, provided that the conjecture is correct, while for part c), further 10 points can be given, depending on the structure and explanations in the program.)

I. 90. We are given some points in the plane together with their coordinates.

Prepare a sheet such that the name of each point (e.g., P, Q, A, B, C, M_a) as well as their x and y coordinates can be entered into the first 3 columns, and then the name of the farthest point from the origin, its x and y coordinates and its distance from the origin are displayed, respectively, in the 7^th, 8^th, 9^th, 10^th cells of the 6^th row.

Your sheet (i90.xls) is to be submitted. (10 points)

Send your solutions by e-mail to: i@komal.hu

New problem of sign S

S. 3. Alice and Bob play a game. They pronounce words in turn, such a way that the first letter of each new word matches the last letter of the previous one. At the beginning they agree on the set of words that can be used (e.g. cities, animals, etc.). Previous words can not be repeated and the loser is who can not select a new word.

Write a program that helps Alice to choose the first word from a given list such that she has a winning strategy: the first line of the input contains the number of words - at most 20 - which are then listed in the remaining lines. The output should be similar: the number of winning words followed by the words themselves. If there is no winning word, the output is to be a single line containing a 0.

Example:

(10 points)

Send your solutions by e-mail to: s@komal.hu

Deadline: 15 November 2004