Az A. 893. feladat (2024. december)

A. 893. Egy szövegszerkesztő programban kezdetben egy lábnyom jel (L) szerepel, amelyet szeretnénk megsokszorozni. Sajnos hekkertámadás áldozata lett a gépünk, és csak két funkció működik: a Másolás és a Beillesztés, ráadásul mindkettő $\displaystyle 1$ Dürer dollárba kerül használatonként. A Másolás funkció használatakor kijelölhetünk egy vagy több egymás utáni jelet a meglévők közül, és a gép megjegyzi azok darabszámát. A Beillesztés funkció használatakor annyi új lábnyom jelet tesz hozzá a gép a jelsorozathoz, amennyit a legutóbbi Másolásnál kijelöltünk. Ha még nem Másoltunk, nem használhatjuk a Beillesztést. Jelölje $\displaystyle D(n)$ azt, hogy legkevesebb hány Dürer dollár kell ahhoz, hogy pontosan $\displaystyle n$ darab lábnyom jelet kapjunk. Bizonyítsuk be, hogy bármilyen pozitív egész $\displaystyle k$-ra létezik olyan $\displaystyle N$ pozitív egész szám, amelyre

$$\begin{gather*} D(N)=D(N+1)+1=D(N+2)=D(N+3)+1=D(N+4)=\ldots\\ \ldots=D(N+2k-1)+1=D(N+2k). \end{gather*}$$

Dürer Verseny feladat alapján

(7 pont)

A beküldési határidő 2025. január 10-én LEJÁRT.

Osszuk a lépéseket blokkokra: egy blokk induljon Másolással és záruljon a következő Másolás előtt közvetlenül, azaz minden blokkban pontosan egyszer Másolunk, a blokk első lépéseként. Először megmutatjuk, hogy tetszőleges $\displaystyle n$ esetén el lehet érni $\displaystyle n$ lábnyomot $\displaystyle D(n)$ lépéssel úgy, hogy minden blokk legfeljebb 3 méretű. Indirekten tegyük fel, hogy ez nem igaz, és létezik egy $\displaystyle n$ szám, melyre akármelyik $\displaystyle D(n)$ költségű, $\displaystyle n$ lábnyomot elérő sorozat esetén van legalább 4 méretű blokk. Tekintsünk egy olyan lépéssorozatot, ami $\displaystyle D(n)$ lépés alatt csinál $\displaystyle n$ lábnyomot, és a leghosszabb blokk hossza minimális, ahol ez a minimum $\displaystyle k \geq 4$. Tekintsünk egy $\displaystyle k$ hosszú blokkot, ami tehát egy Másolásból, és $\displaystyle k-1$ Beillesztésből áll. Ehelyett csináljuk azt, hogy a Másolást ugyanúgy megcsináljuk, majd csak $\displaystyle k-3$ Beillesztést csinálunk (ahol $\displaystyle k-3 \geq 1$), majd Másolunk kétszer annyi karaktert, mint amennyit a blokk elején Másoltunk, és ezt egyszer Beillesztjük. Így ugyanannyi lépést használtunk, és végül ugyanannyi lábnyomot kaptunk, azonban a blokkot két rövidebb blokkra osztottuk. Ezt elvégezve az összes $\displaystyle k$ hosszú blokkra rövidítettük a leghosszabb blokk hosszát, így ellentmondásra jutottunk. Ezzel beláttuk, hogy mostantól mindig feltehetjük, hogy minden blokk legfeljebb 3 hosszú.

Ezek alapján megmutatjuk, hogy $\displaystyle D(n)$-re teljesül az alábbi rekurzió ha $\displaystyle n \geq 2$.

$\displaystyle D(n)=\min\left(2+\min_{n/2 \leq k <n} D(k), \ \ 3+\min_{\substack{n/3 \leq k <n \\ 2 \mid n-k}} D(k)\right).$

Ez azért teljesül, mert ha $\displaystyle n$-et felírjuk $\displaystyle D(n)$ költséggel legfeljebb 3-hosszú blokkokkal, akkor az utolsó blokk vagy 2, vagy 3 hosszú. Előbbi esetben az utolsó blokk előttig elő kellett állítani legalább $\displaystyle n/2$ lábnyomot, majd plusz két dollárért elő tudjuk állítani az utolsó blokkal a kimaradó lábnyomokat. Utóbbi esetben akkor tudjuk egy három hosszú utolsó blokkal elérni, hogy összesen $\displaystyle n$ lábnyom legyen, ha addig van legalább $\displaystyle k \geq n/3$, illetve ha kétszer ugyanannyit Beillesztve pont $\displaystyle n$-et tudunk kapni, ami a $\displaystyle 2 \mid n-k$ feltételt adja.

Kis esetek vizsgálatával meg lehet sejteni az általános képletet $\displaystyle D(n)$-re, ami a következőképpen írható le, ha $\displaystyle n \geq 4$. Legyen $\displaystyle k$ az egyértelmű pozitív egész szám, melyre $\displaystyle 3^k+1 \leq n \leq 3^{k+1}$. Majd osszuk még tovább ezt az intervallumot:

Ha $\displaystyle 3^k+1 \leq n \leq 3^k+3^{k-1}$, akkor $\displaystyle D(n)=3k+1$,
Ha $\displaystyle 3^k+3^{k-1}+1 \leq n \leq 2 \cdot 3^k$, akkor $\displaystyle D(n)=3k+2$,
Ha $\displaystyle 2 \cdot 3^k+1 \leq n \leq 2 \cdot 3^k+2 \cdot 3^{k-1}$, akkor $\displaystyle D(n)=3k+3$,
És ha $\displaystyle 2 \cdot 3^k+2 \cdot 3^{k-1}+1 \leq n \leq 3^{k+1}$, akkor $\displaystyle D(n)=3k+3$, ha $\displaystyle 2 \nmid n$, és $\displaystyle D(n)=3k+4$, ha $\displaystyle 2 \mid n$.

Látható, hogy az utolsó esetben felváltva szerepel a $\displaystyle 3k+3$ és a $\displaystyle 3k+4$ érték, így amennyiben bizonyítjuk, hogy tényleg ez a képlet $\displaystyle D(n)$-re, a feladat állításával is készen vagyunk.

A rekurzív képletet használva már kevés nehézség van a képlet $\displaystyle k$ szerinti indukcióval történő bizonyításában, csak végig kell nézni az eseteket. A kezdőlépéshez ellenőrizzük, hogy $\displaystyle D(1)=0$, $\displaystyle D(2)=2$, $\displaystyle D(3)=3$, $\displaystyle D(4)=4$, $\displaystyle D(5)=D(6)=5$, $\displaystyle D(7)=D(8)=D(9)=6$, így $\displaystyle k=1$ esetén, azaz ha $\displaystyle 3^1+1 \leq n \leq 3^{2}$ tényleg teljesül az állítás.

Most tegyük fel, hogy már minden $\displaystyle n \leq 3^k$ számra bizonyítottuk a képletet, és most igazoljuk $\displaystyle 3^k+1 \leq n \leq 3^{k+1}$ esetén is.

Ha $\displaystyle 3^k+1 \leq n \leq 3^k+3^{k-1}$, akkor $\displaystyle 3^{k-1}+3^{k-2} < n/2 \leq 2 \cdot 3^{k-1}$, amiből látható, hogy ha olyan konstrukciót akarunk, amiben kettő hosszú az utolsó blokk, akkor $\displaystyle 3k+1$ a legjobb, amit el tudunk érni. Továbbá $\displaystyle 3^{k-1} < n/3 \leq 3^{k-1}+3^{k-2}$, így hármas utolsó blokkal sem tudunk $\displaystyle (3k+1)$-nél jobbat elérni, azaz ebben az esetben tényleg $\displaystyle D(n)=3k+1$.
Ha $\displaystyle 3^k+3^{k-1}+1 \leq n \leq 2 \cdot 3^k$, akkor $\displaystyle 2 \cdot 3^{k-1}<n/2 \leq 3^{k}$, amiből következik, hogy ha kettő hosszú az utolsó blokk, akkor nem tudunk $\displaystyle (3k+2)$-nél jobbat elérni, és ennyit pedig el is lehet érni, ha először $\displaystyle 3k$ lépésből csinálunk $\displaystyle 3^k$ lábnyomot, majd egy Másolás-Beillesztéssel a további szükséges mennyiséget megcsináljuk. Továbbá ekkor $\displaystyle 3^{k-1}+3^{k-2} < n \leq 2 \cdot 3^{k-1}$, így hármas utolsó blokkal sem lehet $\displaystyle (3k+2)$-nél jobbat elérni, azaz $\displaystyle D(n)=3k+2$.
Ha $\displaystyle 2 \cdot 3^k+1 \leq n \leq 2 \cdot 3^k+2 \cdot 3^{k-1}$, akkor $\displaystyle 3^k < n/2 \leq 3^k+ 3^{k-1}$, valamint $\displaystyle 2 \cdot 3^{k-1} < n/3 \leq 2 \cdot 3^{k-1}+2 \cdot 3^{k-2}$, így az előző esetekhez hasonlóan, se kettes se hármas utolsó blokkal nem lehet $\displaystyle (3k+3)$-nál kevesebbet elérni, de kettes utolsó blokkal ez elérhető.
Végül ha $\displaystyle 2 \cdot 3^k+2 \cdot 3^{k-1}+1 \leq n \leq 3^{k+1}$, akkor $\displaystyle 3^k+ 3^{k-1} < n/2 \leq 2 \cdot 3^{k}$, így kettes utolsó blokkal $\displaystyle 3k+4$ a legjobb, ami elérhető. Továbbá $\displaystyle 2 \cdot 3^{k-1}+2 \cdot 3^{k-2} < n/3 \leq 3^{k}$, így ha $\displaystyle 2 \nmid n$, akkor $\displaystyle 3k$ dollárral csinálva $\displaystyle 3^k$ lábnyomot, majd egy további megfelelő hármas blokkal el lehet érni összesen $\displaystyle 3k+3$ dollárért a kívánt mennyiségű lábnyomot. Ha pedig $\displaystyle 2 \mid n$, akkor hármas utolsó blokk esetén is kell $\displaystyle 3k+4$, mivel minden páros számhoz, ami legalább $\displaystyle n/3$ szükséges $\displaystyle 3k+1$ dollár. Ezzel ebben az esetben is igazoltuk a kívánt képletet, ami befejezi a bizonyítást.

Statisztika:

Az A. 893. feladat értékelése még nem fejeződött be.

A KöMaL 2024. decemberi matematika feladatai

Már regisztráltál?
Új vendég vagy?