A C. 1504. feladat (2018. november)

C. 1504. Egy $\displaystyle 3\times3$-as táblázat celláit kitöltjük az ábra szerint. Egy lépésben megcserélhetünk egymás között $\displaystyle n$ darab olyan számot, melyek legnagyobb közös osztója $\displaystyle n$, úgy, hogy egyikük sem marad a helyén. Elérhető-e ilyen lépésekkel, hogy az eredeti táblázathoz képest az egyik, illetve a másik átlóra való tükrözés szerinti elrendezésbe kerüljenek a számok?

(5 pont)

A beküldési határidő 2018. december 10-én LEJÁRT.

Megoldás. Először vizsgáljuk meg, hogy elérhető-e az az elrendezés, amit a táblázat $\displaystyle 4,8,10$ átlóra tükrözésével kapunk:

A szabályok alapján vegyük észre, hogy az $\displaystyle 1$-et nem tudjuk mozgatni, hiszen az $\displaystyle 1$-nek bármely más számmal (számokkal) $\displaystyle 1$ a legnagyobb közös osztója, vagyis ilyenkor csak egy számot mozgathatnánk, az $\displaystyle 1$-et, ami ellentmondás.

Ebben az esetben az $\displaystyle 1$-nek át kellene kerülnie a szemközti csúcsba, így a kívánt elrendezés nem érhető el.

Most vizsgáljuk meg, elérhető-e az az elrendezés, amit úgy kapunk, ha a táblázatot az $\displaystyle 1,8,20$ átlóra tükrözzük:

Ebben az esetben a kívánt elrendezés elérhető, például a következő lépésekkel:

$\displaystyle ~$

$\displaystyle ~$

$\displaystyle ~$

Tehát először végrehajtunk egy $\displaystyle 4\leftrightarrow 10$ cserét, majd $\displaystyle 3\to 12\to 9\to 3$ ciklikus cserét, végül a $\displaystyle 3\to 6\to 9\to 3$ ciklikus cserét.

Statisztika:

208 dolgozat érkezett.
5 pontot kapott:	138 versenyző.
4 pontot kapott:	33 versenyző.
3 pontot kapott:	15 versenyző.
2 pontot kapott:	10 versenyző.
1 pontot kapott:	2 versenyző.
0 pontot kapott:	5 versenyző.
Nem számítjuk a versenybe a születési dátum vagy a szülői nyilatkozat hiánya miatt:	5 dolgozat.

A KöMaL 2018. novemberi matematika feladatai