KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

Problem B. 3859. (November 2005)

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 pont)

Deadline expired on 15 December 2005.


Sorry, the solution is available only in Hungarian. Google translation

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:

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.

Our web pages are supported by:   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