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

# Exercises and problems in InformaticsOctober 2004

### New exercises of sign I

I. 88. Suppose we are given the vectors w1, w2, ...,wn and a binary tree of depth n. We travel from its root to one of its leaves. The kth vector wk is selected if and only if we have turned left at the kth 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 w1, w2, ..., wn are given.

As a particular example, consider the vectors w1, w2,..., wn 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: 51=5=1+4=12+22, 52=25=9+16=32+42, 53=125=100+25= 102+52.

a) Using a program or a table, find the number of integer solutions of equation kn=x2+y2, 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, Ma) 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 7th, 8th, 9th, 10th cells of the 6th row.

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

### 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:

 Input Output 7tableglasseggsaltcheesegarlicfruit 2cheesefruit

(10 points)