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 a₁,a₂,...,a_n sorrendje, hogy az a₁, a₁a₂, a₁a₂a₃, ..., a₁a₂^...a_n 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 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.

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

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ő.

Már regisztráltál?
Új vendég vagy?