Problem I. 167. (October 2007)

I. 167. We know that a very tiny - in fact, to us invisible - flea is jumping on certain integer coordinates of a ruler between 0 and 7 according to the following rule: in every second its next position will be the sum of its current and previous positions modulo 8. We want to catch the flea, but we can check only one position in every second.

Your task is to give a sequence of length of at most 30 so that if we check positions on the ruler in every second according to this sequence, we will surely catch the flea at the end. The shorter your sequence, the more points you may receive. An Excel sheet is available at www.komal.hu to check your sequences.

You can use any tools (e.g., write a program or use a spreadsheet) to complete the solution. Your sequence should be submitted (possibly using the downloadable compressed Excel sheet (bolha.zip) above) together with some remarks (i167.txt, i167.pdf, ...) commenting on your solution.

(10 pont)

Deadline expired on November 15, 2007.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás

Mintamegoldásként Adrián Patrik, 8. osztályos debreceni tanuló dolgozatát közöljük:

i167.pdf

bolhamegoldas.xls

Ezen kívül sokan programot írtak, mely valamilyen bejárás szerint megkereste a legrövidebb megoldásokat. Volt olyan is, aki táblázatkezelő segítségével, valószínüségi megfontolások alapján talált meg több, 12 hosszú sorozatot.

Statistics:

10 students sent a solution.
10 points:	Adrián Patrik, Englert Péter, Fábián András, Földes Imre, Hodosy Gábor, Horváth 135 Loránd, Véges Márton.
9 points:	Erdős Gergely.
7 points:	2 students.

Problems in Information Technology of KöMaL, October 2007