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

 

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 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)

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:

InputOutput
7
table
glass
egg
salt
cheese
garlic
fruit
2
cheese
fruit

(10 points)

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

Deadline: 15 November 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