Problem B. 3859. (November 2005)

B. 3859. Find all natural numbers n greater than 1, for which there is an order a₁,a₂,...,a_n of the numbers 1,2,3,...,n, such that the products a₁, a₁a₂, a₁a₂a₃, ..., a₁a₂^...a_n divided by n all leave different remainders.

(5 pont)

Deadline expired on December 15, 2005.

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

Megoldás: Szükségképpen a_n=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 $\ne$ 4 ö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 a₁,a₂,...,a_n-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 $\le$ i $\le$ n esetén. Ehhez szükséges és elegendő, hogy a₁=1, a_n=n, és 1 $\le$ i $\le$ n-1 esetén (i-1)a_i n-nel osztva éppen i maradékot adjon, vagyis (i-1)(a_i-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 $\le$ i-1 $\le$ n-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 $\ne$ 0, és j $\ne$ n-1, hiszen (i-1)(n-1) n-nel osztva n-(i-1) $\ne$ 1 maradékot ad. Az a_i=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.

Problems in Mathematics of KöMaL, November 2005

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.

Already signed up?
New to KöMaL?