Kezdőlap


Feladat:	A.234	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Csóka Endre , Gyenes Zoltán , Harangi Viktor , Kiss Gergely , Varjú Péter , Zábrádi Gergely
Füzet:	2000/december, 543 - 544. oldal		PDF \| MathML
Témakör(ök):	Algoritmikus eljárások, Teljes indukció módszere, Nehéz feladat
Hivatkozás(ok):	Feladatok: 2000/március: A.234

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Nevezzük az $u$ és $v$ szavakat ekvivalensnek, ha átalakíthatók egymásba egymásba a megadott lépésekkel, és jelöljük ezt $u \sim v$ -vel. Ezen kívül jelentse $u v$ az $u$ és $v$ szavak egyszerű egymás után írását.

Lemma. Ha az

u

szó mindhárom betűt tartalmazza,

v

pedig tetszőleges szó, akkor

u v u \sim u

.
A lemmát a

v

hossza szerinti indukcióval igazoljuk. Ha

v

az üres szó, akkor

u v u = u u \sim u

. Ha

v

egyetlen betűből áll, akkor ezt a feltétel szerint

u

tartalmazza:

u = u_{1} v u_{2}

alkalmas

u_{1}

és

u_{2}

szavakkal. Ekkor

\begin{matrix} u v u = u_{1} v u_{2} v u_{1} \underset{̲}{v u_{2}} \sim \underset{̲}{u_{1} v u_{2} v u_{1} v u_{2} v} u_{2} \sim u_{1} \underset{̲}{v u_{2} v u_{2}} \sim u_{1} v u_{2} = u . \end{matrix}

Tegyük most fel, hogy a lemma igaz

k

-nál rövidebb

v

esetén (

k \geq 2

), és legyen

v

hossza

k

. Írjuk fel

v

-t

v_{1} v_{2}

alakban, ahol

v_{1}

és

v_{2}

k

-nál rövidebb szavak. Az indukciós feltevést alkalmazva az

u

és

v_{2}

, illetve

v_{2} u

és

v_{1}

szavakra

u v_{2} u \sim u

(v_{2} u) v_{1} (v_{2} u) \sim v_{2} u

és

\begin{matrix} u v u = u v_{1} v_{2} u \sim (u v_{2} u) v_{1} v_{2} u = u (v_{2} u) v_{1} (v_{2} u) \sim u (v_{2} u) \sim u . \end{matrix}

Ezzel a lemmát igazoltuk.
Ezután bebizonyítjuk a feladat állítását. Nyilván elég igazolni, hogy minden legalább 9 hosszúságú szó ekvivalens egy nála rövidebbel. Tekintsünk egy legalább kilencbetűs szót. Írjuk fel ezt

u v w

alakban, ahol

u

és

w

a szó első, illetve utolsó 4 betűjéből áll. Ha

u

vagy

w

valamelyike csak kétféle betűt tartalmaz, akkor vagy van benne egymás után két egyforma betű, vagy pedig kétféle betűt tartalmaz váltakozva. A szó mindkét esetben triviálisan rövidíthető: az első esetben az ismétlődő betűk egyikét hagyhatjuk el, a másik esetben a négybetűs szó két fele ugyanaz, ezért az egyik fele elhagyható. Feltételezhetjük tehát, hogy

u

és

w

is mindhárom fajta betűből tartalmaz legalább egyet. Ebben az esetben a lemma alapján

u w u \sim u

és

w u v w \sim w

, ezért

\begin{matrix} u v w \sim u w u v w \sim u w . \end{matrix}

u v w

szó tehát ekvivalens a nála rövidebb

u w

szóval.

Kiss Gergely (Fazekas M, Főv. Gyak. Gimn., 11. o.) dolgozata alapján

Megjegyzés. Nem minden kilencbetűs szó rövidíthető triviálisan. Az

A B

-vel kezdődő kilencbetűs szavak között 18 olyan van, amiben nincs két egymás utáni megegyező részlet. A megoldók többsége ezekre az esetekre egy-egy egyedi megoldást adott.