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 régi honlapot akarom!!! :-)

A B. 3859. feladat (2005. november)

B. 3859. Keressük meg az összes olyan 1-nél nagyobb n természetes számot, amelyre az 1,2,3,...,n számoknak létezik olyan a1,a2,...,an sorrendje, hogy az a1, a1a2, a1a2a3, ..., a1a2...an szorzatok mind különböző maradékot adnak n-nel osztva.

(5 pont)

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


Megoldás: Szükségképpen an=n, máskülönben a szorzatok között több n-nel osztható is lenne. Ugyanez a probléma merülne fel akkor is, ha az a_1, a_2,\ldots, a_{n-1} számok között lenne kettő, amelyek szorzata osztható n-nel. Ha n\ne4 összetett szám, akkor ez tényleg elő is fordul, hiszen ha n nem egy prímszám négyzete, akkor n felírható ab alakban, ahol a és b egymástól különböző, n-nél kisebb számok, ha pedig n egy 2-nél nagyobb p prímszám négyzete, akkor az a_1, a_2,\ldots, a_{n-1} számok között megtalálható p és 2p is. Tehát csak akkor létezhet a kívánt tulajdonsággal rendelkező sorrend, ha n=4, vagy pedig n prímszám. Ha n=4, akkor az 1,3,2,4 sorrend megfelelő.

A továbbiakban megmutatjuk, hogy akkor is létezik megfelelő sorrend, ha n prímszám. Az a1,a2,...,an-1 számokat úgy fogjuk megválasztani, hogy az a_1a_2\ldots a_{i} szorzat n-nel osztva éppen i maradékot adjon, minden 1\lei\len esetén. Ehhez szükséges és elegendő, hogy a1=1, an=n, és 1\lei\len-1 esetén (i-1)ai n-nel osztva éppen i maradékot adjon, vagyis (i-1)(ai-1) n-nel osztva 1 maradékot adjon. Ekkor ugyanis az a_2,\ldots,a_{n-1} számok nyilván 0-tól, 1-től és egymástól is különböző maradékot adnak, tehát a 2,\ldots, n-1 számok egy permutációját fogják alkotni, amelyre a kívánalom teljesül. Legyen tehát 1\lei-1\len-2, és tekintsük az (i-1).0, (i-1).1, \ldots (i-1)(n-1) számokat, ezek n-nel osztva különböző maradékot adnak. Közülük valamelyik, mondjuk (i-1)j, n-nel osztva 1 maradékot ad. Nyilván j\ne0, és j\nen-1, hiszen (i-1)(n-1) n-nel osztva n-(i-1)\ne1 maradékot ad. Az ai=j+1 vásztás tehát megfelelő lesz.


Statisztika:

64 dolgozat érkezett.
5 pontot kapott:Blázsik Zoltán, Dányi Zsolt, Farkas Ádám László, Honner Balázs, Károlyi Márton, Kornis Kristóf, Kovács 111 Péter, Kovács 129 Péter, Kunovszki Péter, Kutas Péter, Mészáros Gábor, Nagy 235 János, Szabó 108 Tamás, Szaller Dávid, Szalóki Dávid, Szegvári Gábor, Szentandrási István, Szilágyi 987 Csaba, Szűcs Gergely, Tomon István, Tóthmérész Lilla, Udvari Balázs, Varga 111 Péter, Varga 171 László, Véges Márton.
4 pontot kapott:Bartha Éva Lili, Csató László, Cseh Ágnes, Farkas Márton, Milotai Zoltán, Prőhle Zsófia, Sümegi Károly, Szabó Levente, Szalkai Balázs.
3 pontot kapott:3 versenyző.
2 pontot kapott:10 versenyző.
1 pontot kapott:13 versenyző.
0 pontot kapott:4 versenyző.

A KöMaL 2005. novemberi matematika feladatai