A C. 1078. feladat (2011. április)

C. 1078. A 26 betűből álló angol abc-ből készítünk legfeljebb tízbetűs karaktersorozatokat, amelyeket ,,szavaknak'' nevezünk. (Egy ,,szó'' készíthető akár csak egy betű felhasználásával, és két ,,szó'' különböző, ha legalább egy betűben eltérnek egymástól.) Igazoljuk, hogy az így kapott összes lehetséges ,,szavak'' száma osztható 27-tel.

(5 pont)

A beküldési határidő 2011. május 10-én LEJÁRT.

Megoldás. Ha egy "szó" $\displaystyle k$ karakterből áll, akkor az ilyen "szavak" száma $\displaystyle 26^k$, mert ez egyes helyekre egymástól függetlenül bármely betűt választhatjuk az abc-ből. Összesen $\displaystyle N=26+26^2+\dots 26^{10}=26\cdot \frac{26^{10}-1}{25}$ "szót" alkottunk. Ha 27 osztja $\displaystyle 26^{10}-1$-t, akkor $\displaystyle N$-t is, mert 27 és 25 relatív prímek. $\displaystyle 26^{10}-1=(26^5-1)(26^5+1)=(26^5-1)(26+1)(26^4-26^3+26^2-26+1)$, mely szorzatnak 27 osztója.

Statisztika:

141 dolgozat érkezett.
5 pontot kapott:	98 versenyző.
4 pontot kapott:	31 versenyző.
3 pontot kapott:	6 versenyző.
2 pontot kapott:	1 versenyző.
0 pontot kapott:	5 versenyző.

A KöMaL 2011. áprilisi matematika feladatai