Gyepesítsünk minél kisebb költséggel!

Probléma:

Adott egy n×m-es (n és m pozitív egész számok) téglalap alakú kert, és ezt szeretnénk befüvesíteni. Ehhez vehetünk 1×1-es gyepkockákat. Minden nap folyamán begyepesedik az az 1×1-es négyzet a mezőn, amelynek legalább két füves szomszédja van. Legalább hány 1×1-es gyepkockát kell vásárolni? Hány kockát vegyünk, ha a lehető legkisebb költséggel akarjuk megúszni a gyepesítést?

Amikor ezt a problémát kitűztem a tanítványaim számára, akkor konkrét esetekben kezdtek el "gyepesíteni". Amikor elkészültek egy-egy megoldással, bemutatták, majd a többiekhez fordultunk azzal a kérdéssel, hogy kevesebb gyepkockával nem tudnák-e elérni a célt az adott esetben. Hosszadalmas, nagy türelmet igénylő keresgélés eredményeképpen Gigi megfogalmazta a következő sejést:

Sejtés:

A kert befüfesítéséhez szükséges, kezdetben vásárlandó gyepkockák számára (k) igaz, hogy

(1).

Érezhető volt Gigi megállapításában, hogy ezt a számot ő elegendőnek is gondolja.

Ezek után még néhány konkrét esetet megvizsgálva, a tapasztaltak alátámasztották a Gigi-féle sejtést.

A bizonyítása céljából megvizsgáltuk, hogy egy mező gyepesedésekor a gyepes mezők összkerülete nem nőhet. Kezdetben a gyepes mezők összkerülete 4k (ha a kiindulásul szolgáló gyepkockák nem érintkeznek). Ha az egész kertet fű borítja, akkor a gyepes mezők összkerülete 2(m+n). Így már adódik az (1) összefüggés.

Azt, hogy ez a szám elegendő is, Anett mutatta meg. Három esetben vizsgálta a problémát:

1. Ha m és n is páros

Ha m=2t és n=2v, akkor (1)-ből adódik, hogy k legkisebb értéke k0=t+v. Hogy ennyi kezdeti gyepkockával megoldható a teljes kert gyepesítése, az mutatja a következő ábra. (Ez egy konkrét, 6×7-es kertet mutat, de ebből nyilvánvaló az eljárás tetszőleges esetre vonatkozóan.

0
5
6
7
8
9
10
11
1
4
5
6
7
8
9
10
0
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
0
1
2
3
4
5
6
7
1
0
1
0
1
0
1
0

(A vásárolandó gyepkockák helyét a '0' jelzi. A többi számok az mutatják, hogy az adott mező hányadik napon válik gyepessé.)

2. Ha n és m is páratlan

Ha m=2t+1 és n=2v+1, akkor (1)-ből adódik, hogy k legkisebb értéke k0=t+v+1. Azt, hogy ennyi kezdeti gyepkockával megoldható a teljes kert gyepesítése, az alábbi, az előzőhöz hasonló módon készült ábra mutatja

0
5
6
7
8
9
10
11
12
1
4
5
6
7
8
9
10
11
0
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
0
1
0
1
0
1
0
1
0

 

3. Ha n és m közül az egyik páros, a másik páratlan

Ha m=2t+1 és n=2v, akkor (1)-ből adódik, hogy k legkisebb értéke - felhasználva, hogy k0 egész szám - k0=t+v+1. Azt, hogy ennyi kezdeti gyepkockával megoldható a teljes kert gyepesítés, ismét egy ábrával mutatjuk meg.

0
5
6
7
8
9
10
11
12
1
4
5
6
7
8
9
10
11
0
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
0
1
2
3
4
3
2
1
0
1
0
1
0
1
0
1
0
1

 

 

Portál