Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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?

1 3 4
6 8 9
10 12 20

(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:

20 9 4
12 8 3
10 6 1

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:

1 6 10
3 8 12
4 9 20

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

1 3 4
6 8 9
10 12 20

\(\displaystyle ~\)

1 3 10
6 8 9
4 12 20

\(\displaystyle ~\)

1 9 10
6 8 12
4 3 20

\(\displaystyle ~\)

1 6 10
3 8 12
4 9 20

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