Információk

Főmenü

 Aktuális szám: 35. szám 2025. március 

Oldjuk meg „kockás papíron”!

Oldjuk meg „kockás papíron”!

Az elemi matematikában számomra mindig azok a legizgalmasabb feladatok, amelyek megoldásához valamely látszólag nem odaillő terület ismereteit használjuk. Ismerjük algebrai feladatoknak például geometriai vagy függvénytani interpretációját. Nagyon inspirálók voltak ilyen tekintetben a speciális matematika tagozaton tanító tanárok számára évente megrendezésre kerülő ún. specmat-találkozók, ahol elsősorban Hraskó András tanár úr ilyen kiegészítéseit hallhattuk a megtekintett bemutatóórák után. Ez a cikk is ezen motiváló tényezők hatására született.

A következőkben néhány, a koordinátarácson megoldható feladattal ismerkedünk meg. Ezek egy része megfogalmazásában is tartalmazza a rácsot, mások megoldásához pedig úgy jutunk el, ha egy rácson jelenítjük meg, ezáltal a matematika több területét kapcsoljuk össze. A témát bizonyos formában már feldolgoztam a 2008-as debreceni Rátz László Vándorgyűlésen. Az akkor elhangzott feladatok egy részét megtartottam, frissítettem és újakkal egészítettem ki. 

Úgy gondolom, hogy a bemutatott példák jól használhatók tehetséggondozó szakköröket tartó tanárok számára, de akár tanórákon is bevethetők matematikából haladóbb szinten álló tanulócsoportok esetén. Ugyanakkor jó gondolatébresztők is lehetnek újabb feladatok kitűzése során.

1. Egy csiga a koordináta-rendszer origójából indul, és az ábrán látható mintának megfelelően folytatja útját. Másodpercenként 1 egységet tesz meg. Melyik pontban lesz egy, illetve két órával az indulás után?

 

Megoldás. Készítsünk rajzot! Írjuk fel a „kanyarokba” az ott-tartózkodás időpontját!

 

Ekkor a következő sejtésünk fogalmazható meg:

A csiga a $(2k+1)^2$ időpontban a koordináta-rendszer $(2k+1;0)$ pontjában, míg a $(2k)^2$ időpontban a $(0;2k)$ pontjában tartózkodik. Ez teljes indukcióval könnyen bizonyítható.

Tehát a csiga 1 óra ($=3600$ s) eltelte után a $(0;60)$ pontban lesz, és bármely időpont esetén csak azt kell megnézni, hogy az melyik két négyzetszám közé esik. Ez alapján ugyanis a tartózkodási hely könnyen meghatározható. Mivel $84^2<7200<85^2$, továbbá $7200=85^2-25$, így tehát két óra, azaz 7200 másodperc elteltével a $(85;0)$ ponttól 25 lépéssel „visszafelé”, a $(84;24)$ pontban lesz a csiga.

2. Bizonyítsuk be, hogy bármely 5 rácspont között van kettő, amelyek összekötő szakasza átmegy egy további rácsponton!

Megoldás. Osztályozzuk a rácspontokat koordinátáik paritása szerint. Négy ilyen osztály lesz (páros–páros, páros–páratlan, páratlan–páros, páratlan–páratlan). Mivel a pontok száma 5, így a skatulyaelv szerint szükségképpen van legalább két azonos osztályba eső pont. Világos, hogy az ezen pontok által meghatározott szakasz felezőpontja is rácspont, amivel az állítást beláttuk.

3. Egy sakktáblát átszelő egyenes legfeljebb hány mező belsején mehet keresztül?

 

Megoldás. A táblán 9 „vízszintes” és 9 „függőleges” rácsegyenes található. A vízszintes és függőleges rácsegyenesek is 8-8, egységnyi szélességű, illetve hosszúságú sávot hoznak létre. Egy tetszőleges „ferde” egyenes mind a 18 rácsegyenest metszi, csak nem biztos, hogy a sakktábla belsejében. Tekintsünk egy tetszőleges egyenest, amely valahol „belép” a sakktáblára. Számoljuk össze az innen rajta keletkező metszéspontokat. Ez tehát legfeljebb 18, amely 17 szakaszra és két félegyenesre osztja egyenesünket. A szakaszokkal számolhatjuk az egyenes által átszelt mezőket: két szomszédos metszéspont által meghatározott szakasz, amelynek belső pontjai a tábla belsejébe esnek, egy átszelt mezőt jelent. Akkor lép be egyenesünk a sakktábla belsejébe, ha mindkét irányú határegyenest metszett. Kilépéskor a helyzet hasonló. Ha egyszerre metszi a két határegyenest, akkor a metszéspontok száma kevesebb. 18 metszéspont úgy keletkezhet, ha nincs olyan metszéspont, amelyben egyszerre két rácsegyenest is metsz az egyenesünk. Ekkor 17 szakasz keletkezik, amelyek közül legalább kettő (egy belépéskor, egy kilépéskor) a táblán kívül helyezkedik el. 17 metszéspont úgy keletkezhet, hogy az egyenes a tábla egyik csúcsán átmegy (pl. a bal felső csúcson) és itt egyszerre két rácsegyenest metsz. Ekkor 16 szakasz keletkezik, amelyek közül legalább egy a táblán kívül helyezkedik el. Ha úgy helyezkedik el az egyenes, hogy a metszéspontok száma 17-nél kevesebb, akkor a keletkező szakaszok száma legfeljebb 15 (és ezek közül nem is mind van feltétlenül a tábla belsejében). Az egyenes által átszelt mezők száma tehát legfeljebb 15. Ez elő is fordulhat, ha pl. az átlót eltoljuk vízszintesen fél négyzetegységgel.

Az alábbi feladat hasonló a 3. feladathoz, csak térbeli gondolkodást igényel (a szerző által kitűzött feladat volt a 2005. évi Nemzetközi Magyar Matematikaversenyen).

4. Egységnyi élű fakockákból téglatestet építettünk, amelynek a méretei $10\times 802\times 2005$. Hány kiskockát lyukaszt ki az a pontszerű szú, amelyik a téglatest egyik testátlója mentén végigrágja magát?

Megoldás. Helyezzük a térbeli koordináta-rendszer origóját a téglatest egyik csúcsába! Legyen a „start” csúcsból kiinduló 3 él a 3 koordinátatengely pozitív fele.
Jellemezzük az egységkockákat az origótól legtávolabbi csúcsuk koordinátáival! A „start” kocka így az $(1;1;1)$, a „cél” pedig a $(10;802;2005)$.
Minden „határátlépés” (a továbbiakban röviden: lépés) során új kockába jut a szú, mégpedig
– csúcson (ekkor mindhárom koordináta nő),
– élen, de nem csúcson (ekkor 2 koordináta nő),
– lapon, de nem élen (ekkor pedig 1 koordináta nő).

Csúcson akkor lép át a szú, ha van az eredetihez hasonló rész-téglatest. Mivel 10, 802 és 2005 legnagyobb közös osztója 1, így ilyen eset nem fordulhat elő.

Az éleken történő áthaladások meghatározásához vizsgáljuk meg a különböző koordinátasíkokra eső merőleges vetületeket. Ekkor a téglatest lapjai egy-egy téglalapot, a síkra merőleges élek pedig ezekben a téglalapokban rácspontokat határoznak meg. Amikor a szú a térben egy élen áthalad, az vetületileg egy rácsponton történő átmenetelt jelent. A  $10\times 802$-es téglalaphoz hasonló legkisebb téglalap az $5\times 401$-es téglalap. A szú a mozgása során két ilyen téglalapot érint (hiszen a hasonlóság aránya 2), ami 1 lépést jelent. Hasonlóan kapjuk, hogy a $802\times 2005$-ös téglalap esetén (amelyhez hasonló legkisebb téglalap $2\times 5$-ös) 400, míg a $10\times 2005$-ös esetén (amelyhez pedig a $2\times 401$-es legkisebb téglalap tartozik) 4 lépést tesz meg a szú. Az éleken való áthaladás tehát $1+400+4=405$ lépést, azaz 810 koordinátaváltozást jelent.

Mivel a koordináták összváltozása $9+801+2004=2814$, amelyből 810 az előzőek értelmében éleken való áthaladás miatt történik, így $2814-810=2004$ lépés történik csak lapon.

Az összes lépés száma $2004+405=2409$, így a bejárt egységkockák száma 2410.

Megjegyzés. Eredményünk a, b, c oldalú téglatestre általánosítva szép szitaformulát eredményez: $a+b+c-(a;b)-(b;c)-(c;a)+(a;b;c)$, ahol a zárójeles kifejezések (szokásosan) a bennük szereplő számok legnagyobb közös osztóját jelentik.

Esetünkben: $10+802+2005-2-401-5+1=2410$, ami összhangban van a fent kapott eredménnyel.

5. Hányféleképpen juthatunk az origóból az $(m;n)$ pontba (ahol $m$ és $n$ egyaránt pozitív egész), ha csak jobbra vagy felfelé léphetünk egységnyit?

Megoldás. Minden lépés az egyik koordinátát 1-gyel növeli. Így a lépések száma $m+n$. Ebből $m$ lépés jobbra, $n$ pedig felfelé történik. Ezek száma pedig $\binom{m+n}{n}$.

6. Egy $(n\times n)$-es sakktábla széttörött úgy, hogy a mellékátlójára eső mezők és az ez alatti rész maradt épen. Hányféleképpen juthatunk el a bal alsó sarokból ($A$) a jobb felsőbe ($B$) felfelé és jobbra lépegetve?

 

Megoldás. A „rossz” utakat fogjuk összeszámlálni. Egy út rossz, ha kivezet a sakktábla épen maradt részéből, azaz metszi az alábbi ábrán látható átlót.

 

Tekintsünk egy „rossz” $A\to B$ utat. Az $A$ ponttól az átlóval való első metszéspontig terjedő útszakaszt tükrözzük az átlóra, ezáltal kapunk egy $A'\to B$ utat (lásd az ábrát). A „rossz” utak és az $A'\to B$ utak között kölcsönösen egyértelmű megfeleltetést létesít az említett tükrözés, ezért a „rossz” utak száma megegyezik az $A'\to B$ utakéval. Az összes $A\to B$ út számából kivonva az $A'\to B$ utak számát, megkapjuk az eredményt. Az $A$ pontból a $B$ pontba $2n-2$ lépéssel jutunk el, amelyből $(n-1)$-szer jobbra, $(n-1)$-szer felfelé lépünk. Felhasználva az 5. feladat eredményét, ezeknek az utaknak a száma $\binom{2n-2}{n-1}$. Az $A'$ pontból a $B$ pontba szintén $2n-2$ lépéssel jutunk el, amelyből $n$-szer lépünk jobbra, tehát az $A'\to B$ utak száma $\binom{2n-2}{n}$. Így a jó utak száma:

$\displaystyle \binom{2n-2}{n-1}-\binom{2n-2}{n}=\frac{1}{n}\binom{2n-2}{n-1}. $

 

Megjegyzés. Ezek az úgynevezett Catalan-számok.

7. A negyedik feladatban szereplő téglatest egyik csúcsából az onnan induló testátló másik végpontjába egységnyi lépésekkel folyton közeledve hányféleképpen juthatunk el, ha csak a téglatest valamely élével párhuzamosan léphetünk, és az út során a téglatestből nem léphetünk ki?

Megoldás. Az origóból kell egységnyi koordinátatengely-irányú lépésekkel eljutni a $(10;802;2005)$ pontba. Egy ilyen utat leírhatunk egy 10 darab $x$, 802 darab $y$ és 2005 darab $z$ betűből álló 2817 hosszúságú jelsorozattal. Ezek száma a betűk ismétléses permutációinak száma: $\frac{2817!}{10!\cdot 802!\cdot 2005!}$.

Ugyanerre az eredményre jutunk, ha a lehetséges 2817 lépés közül kiválasztjuk a 10 darab $x$ irányút, majd a maradékból a 802 $y$ irányút: 

$\displaystyle \binom{2817}{10}\cdot\binom{2807}{802}=\frac{2817!}{10!\cdot 2807!}\cdot\frac{2807!}{802!\cdot 2005!}=\frac{2817!}{10!\cdot 802!\cdot 2005!}. $

 

A következő (nem geometriai) feladatok megoldásánál segítségül hívjuk a négyzetrácsot.

8. A 2023-as női kézilabda világbajnokság döntőjében a francia válogatott Norvégia ellen a félidőben $20:17$-re vezetett. Azt tudjuk még, hogy a végeredmény $31:28$ lett a franciák javára. Ezek ismeretében hányféleképpen alakulhatott a második félidőben a mérkőzés?

Megoldás. A feladat ekvivalens azzal, hogy hányféleképpen juthatunk el a $(20;17)$ pontból a $(31;28)$-ba, avagy eltolással a $(0;0)$ pontból a $(11;11)$-be. Az 5. feladat alapján a válasz: $\binom{22}{11}$.

9. Bizonyítsuk be a következő összefüggéseket.

(a)   $\binom{n}{m}+\binom{n-1}{m-1}+\binom{n-2}{m-2}+\ldots+\binom{n-m}{0}=\binom{n+1}{m}$;

(b)  $\binom{n}{m}\binom{k}{0}+\binom{n-1}{m-1}\binom{k+1}{1}+\binom{n-2}{2}\binom{k+2}{2}+\ldots+\binom{n-m}{0}\binom{k+m}{m}=\binom{n+k+1}{m}$;

(c)   $\binom{n}{0}\binom{m}{k}+\binom{n}{1}\binom{m}{k-1}+\binom{n}{2}\binom{m}{k-2}+\ldots+\binom{n}{k}\binom{m}{0}=\binom{n+m}{k}$,

ahol $n>m>k>0$ egész számok.

Megoldás. Mindhárom esetben a koordináta-rendszer $A(0;0)$ pontjából $B$-be megyünk a már említett módon rácspontról rácspontra jobbra vagy felfelé haladva.

 

(a) Tegyük fel, hogy ez a $B$ pont a $B(n+1-m; m)$. Az 5. feladat értelmében az összes utak száma: $\binom{n+1}{m}$. Másrészt minden j-re ( $0\leq j\leq m$ ) azon utak száma, amelyekben a $(j+1)$-edik lépésünk az első jobbra történő elmozdulás, vagyis az első j lépés után az $A(0;j)$ pontból indulunk tovább:   $\binom{n-j}{m-j}$. Ezeket összegezve az összes lehetséges útvonalak száma valóban

$\displaystyle \binom{n}{m}+\binom{n-1}{m-1}+\binom{n-2}{m-2}+\ldots+\binom{n-m}{0}. $

 

(b) Tekintsük most a következő ábrát! $A$-ból $B(n-m+k+1;m)$-be összesen $n+k+1$ lépést kell tennünk, ebből $m$ lépést felfelé, $n-m+k+1$ lépést jobbra. Az ilyen utak száma a fent említettek szerint $\binom{n+k+1}{m}$, ami az összefüggés jobb oldala.

 

A másik fajta összeszámlálás: osztályozzuk az utakat aszerint, hogy hol lépik át az ábrán pirossal behúzott egyenest (minden út pontosan egyszer teszi ezt). A $C(k;r)$ pontból a $D(k+1;r)$ pontba lépve ($0<r<m$) az összes itt átvezető utak száma az $A$-ból a $C$-be, és a $D$-ből a $B$-be vezető utak számának szorzata: $\binom{k+r}{r}\binom{n-r}{m-r}$. Ezek összege (ami a bizonyítandó összefüggés bal oldala) adja az összes út számát.

(c) Az előbbihez hasonló módon számolhatunk. Most az $A(0;0)$ pontból a $B(n+m-k;k)$ pontba vezető utakat számoljuk össze. Az alábbi ábrán pirossal jelölt egyenest is minden út egyszer metszi (valamelyik rácspontban). Ennek a piros egyenesnek a rácspontjaiba $m$ lépésben jutunk el. Az $(m-i;i)$ pontba $\binom{m}{i}$, innen tovább $\binom{n}{k-i}$-féleképpen juthatunk, ahol $i=0$, 1, 2, ..., $k$. Az ilyen szorzatok összege az utak száma, azaz $\binom{n+m}{k}$.

 

Megjegyzés. A (b) és a (c) részek szép példát mutatnak a kettős leszámlálás módszerére.

10. Hány egész számpár megoldása van az $\vert x\vert+\vert y\vert<1000$ egyenlőtlenségnek?

Megoldás. Az alábbi ábrák kétféle összeszámlálást szemléltetnek:

     

A koordináta-rendszerben ábrázolva a ponthalmazt, egy négyzet rácspontjait kell összeszámlálnunk. Az egyik ábra „vízszintes” összeszámlálást sugall a $(0;-999)$ pontból kiindulva a vízszintes rácsegyeneseken felfelé haladva egészen a $(0;999)$ pontig. Ez, a szimmetriát kihasználva, az ábrán látható összeget eredményezi:

$\displaystyle 2\cdot (1+3+5+\ldots +1997)+1999. $

A másik ábra az origó középpontú hasonló négyzetek kerületi pontjait számolja össze, amelyek egy $d=4$ differenciájú számtani sorozat első 999 összegét eredményezik, amelyhez egyet hozzáadva (ez az origó) kapjuk az eredményt:

$\displaystyle 4+8+12+\ldots 4\cdot 999+1=4\cdot (1+2+3+\ldots +999)+1. $

Az összeg mindkét esetben $1\;998\;001$.

11. Melyek azok a pozitív egész számok, amelyek nem írhatók fel több egymást követő természetes szám összegeként?

Megoldás. Szomszédos pozitív egész számok összegét szemléltethetjük egy olyan „vízszintes” rácstrapéz segítségével, mint ami például az ábra bal oldalán látható. A trapéz alapjainak hossza az összeadandó számok legkisebbike, illetve legnagyobbika, valamint az alapokkal párhuzamos, egymást követő rácsszakaszok hossza éppen a szóban forgó számokkal egyezik meg. Itt most szakasz hossza alatt a szakaszon lévő rácspontok számát értjük. (Az ábrán látható bal oldali trapéz például a $3+4+5$ összeget szemlélteti.) Ha egy ilyen rácstrapézt egy vele egybevágó trapézzal összeillesztünk az ábrán látható módon (az $\times$-tel jelölt pontra tükrözve), akkor egy olyan rácstéglalaphoz jutunk, amelyben a rácspontok száma kétszerese az alapul vett trapéz rácspontjai számának.

 

Világos, hogy egy $N$ pozitív egész szám pontosan akkor állítható elő szomszédos pozitív egészek összegeként, ha található hozzá a fenti módon megfelelő rácstrapéz. Ez pedig ekvivalens azzal, hogy egy $2N$ rácspontot tartalmazó rácstéglalap szimmetriacentrumán áthaladó $45^{\circ}$-os egyenes a téglalapnak nem tartalmazza egyetlen rácspontját sem  Ez csakis páratlan $\times$ páros típusú rácstéglalapok esetén teljesül (amint az a következő három ábráról látható). Ez azt jelenti, hogy $N$-nek kell lennie páratlan osztójának.

          

Azt kaptuk tehát, hogy egy $N$ pozitív egész szám pontosan akkor nem állítható elő szomszédos egész számok összegeként, ha $N$-nek nincs páratlan osztója, következésképpen ha a szám 2-hatvány.

 

12. Egy könyvtár be- és kijáratánál egy-egy tábla áll. Minden be-, illetve kilépőnek fel kell írnia a megfelelő táblára, hogy hány embert talált bent, illetve hagyott ott a könyvtárban. Bizonyítsuk be, hogy egy teljes nap során ugyanazok a számok kerülnek a két táblára, legfeljebb más sorrendben (feltesszük, hogy egyszerre csak egy ember érkezik, vagy távozik).

Megoldás.

 

Az ábra egy nap lehetséges lefolyását ábrázolja.

 

A koordináta-rendszerben egy pont $x$ koordinátája azt jelölje, hogy hányadszorra változott a létszám, $y$ koordinátája pedig az éppen jelen lévő személyek számát. Az ezeket összekötő töröttvonal az $x$ tengellyel egy vagy több zárt sokszöget alkot. Nézzük meg, hogy egy $k$ szám hányszor kerül felírásra a bejáratnál, és hányszor a kijáratnál! Egy, az $x$ tengellyel párhuzamos egyenes a $k$ és $k+1$ szám között ugyanannyiszor lép be a sokszög(ek)be, ahányszor kilép belőle (belőlük). Tehát egyforma számú emelkedő és süllyedő szakaszt metsz át. Minden emelkedéskor a $k$ szám kerül a bejárati táblára, minden süllyedéskor pedig a kijárati táblára. Ezzel állításunkat bizonyítottuk.

13. Egy jegypénztárnál nyolcan állnak sorba. Négyüknél egy-egy ezerforintos, a másik négynél egy-egy kétezerforintos van, a sorrendjük ismeretlen. A jegy ára 1000 Ft, a kassza kezdetben üres. Mindenki egy jegyet szeretne vásárolni. Hány olyan sorrend van, hogy a pénztáros fennakadás nélkül ki tudja adni a jegyet? (Általánosítsunk $k$ darab 1000-es, $m$ darab 2000-esre!)

Megoldás. Jelölje adott sorban E az ezrest, K a kétezrest. Egy „jó” sorozat pl. a következő: EKEEKEK. Milyen is egy jó sorozat? Az, amelyet bárhol elvágva, az E-k száma nem kisebb a K-k számánál. Ha tekintünk egy sakktáblát, amelynek bal alsó sarkából indulva E esetén jobbra, K esetén felfelé lépünk, akkor éppen azok a jó utak, amelyek a 6. feladatban, és a megoldás szó szerint megismételhető.

Fejér Szabolcs, 
a miskolci Földes Ferenc Gimnázium nyugdíjazott tanára

Hivatkozások

[1]KÖMAL, OKTV, Kürschák versenyek és a Nemzetközi Magyar Matematikai versenyek példái

[2]Hajnal Péter: Elemi kombinatorikai feladatok (Polygon 1997.)

[3]Hajnal Péter: Összeszámlálási problémák (Polygon 1997.)

[4]Reiman István: A geometria és határterületei (Gondolat 1986.)

[5]A. M. Jaglom – I. M. Jaglom: Nem elemi feladatok elemi tárgyalásban (Typotex 2015.)