Matma dla raperów

DENNIS E. SHASHA

RUSZMY G¸OWÑ

Rozwiàzanie zagadki
z poprzedniego numeru:

Przy trzech poziomach
zaworów nie sà mo˝liwe
nast´pujàce permutacje:
NCSZ˚
˚ZNCS

By∏yby one mo˝liwe,
gdyby by∏y cztery
poziomy zaworów.

NINA FINKEL

Tematem tej zagadki b´dà powtórzenia. Ciàg
symboli (z których ka˝dy oznacza s∏owo lub
kilka) b´dziemy nazywaç „zaskakujàcym”, je-
Êli dla ka˝dej pary symboli X i Y i ka˝dej od-
leg∏oÊci D, tylko w jednym przypadku X wy-
st´puje przed Y w odleg∏oÊci D. Przyk∏adowo:
AABA jest zaskakujàcy, a AABB nie, ponie-
wa˝ B dwukrotnie wyst´puje po A w tym sa-
mym, równym dwa, odst´pie. Podobnie
AAXYBB nie jest zaskakujàcy, poniewa˝ B
dwukrotnie wyst´puje w odleg∏oÊci czterech
symboli po A.

Na rozgrzewk´ spróbuj wyt∏umaczyç,

dlaczego nie jest zaskakujàca sekwencja
BCBABCC i znajdê zaskakujàcà co najmniej
siedmioelementowà sekwencj´ liter A, B i C.

A teraz du˝o trudniejsze zadanie: skonstru-

uj jak najd∏u˝szà zaskakujàcà sekwencj´ z∏o˝o-
nà z pi´ciu, a nast´pnie z 10 i 26 ró˝nych sym-

boli. Dla wygody wykorzystaj litery alfabetu
∏aciƒskiego (odpowiednio od A do E, od A
do J i od A do Z). Przekonasz si´, ˝e d∏ugoÊç
ciàgów wzrasta powoli i nawet dla 26 symbo-
li jest mniejsza od 100. Do tej pory zajmowa-
liÊmy si´ poj´ciem dwuzaskakiwania, ponie-
wa˝ rozpatrywaliÊmy jednà par´ symboli.
Mo˝na tak˝e zdefiniowaç poj´cie trójzaskaki-
wania – dla ka˝dej trójki symboli i odleg∏oÊci
D1 i D2 najwy˝ej raz w ciàgu pierwszy symbol
(X) poprzedza drugi symbol (Y) o odleg∏oÊç
D1, a z kolei Y poprzedza trzeci (Z) o D2.

Skonstruuj jak najd∏u˝szy trójzaskakujàcy

ciàg z∏o˝ony z pierwszych pi´ciu liter alfabe-
tu. Przyznam, ˝e nie znam prostej zasady,
która pozwala∏aby dla dowolnych k i n znaj-
dowaç najd∏u˝sze mo˝liwe k-zaskakujàce cià-
gi n symboli, ale mo˝e uda ci si´ znaleêç ta-
kà regu∏´.

n

STYCZE¡ 2004 ÂWIAT NAUKI

93

Rozwiàzanie zagadki na rozgr

zewk´:

BCBABCC nie jest zaskakujàcy , poniewa˝ w dwóch pr

zypadkach jedno

B znajduje si´ w odleg∏oÊç dwu liter od drugiego. Zaskakujàcy ciàg siedmioelementowy to BACCBCA.

Zaskakujàcy czy nie?

Nie:

Nie:

Tak:

Nie: