KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

B. 3859. Find all natural numbers n greater than 1, for which there is an order a1,a2,...,an of the numbers 1,2,3,...,n, such that the products a1, a1a2, a1a2a3, ..., a1a2...an divided by n all leave different remainders.

(5 points)

Deadline expired on 15 December 2005.


Google Translation (Sorry, the solution is published in Hungarian only.)

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.


Statistics on problem B. 3859.
64 students sent a solution.
5 points: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 points: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 points:3 students.
2 points:10 students.
1 point:13 students.
0 point:4 students.


  • Problems in Mathematics of KöMaL, November 2005

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley