A 2003 márciusi A-jelű matematika feladatok megoldása

A. 314. Adott egy egységnyi oldalú négyzetben egy töröttvonal úgy, hogy bármely egyenes, amely egy csúcsára sem illeszkedik, legfeljebb hét oldalát metszi. Legfeljebb milyen hosszú lehet a töröttvonal?

Soukup Lajos ötletéből

Megoldásvázlat. Legyen a töröttvonal hossza l, végpontjai A és B. Tetszőleges $\displaystyle \varphi$ irányban legyen a négyzet vetületének hossza n($\displaystyle \varphi$), az AB szakasz vetületének hossza h($\displaystyle \varphi$), a töröttvonalat alkotó szakaszok vetületének összege v($\displaystyle \varphi$).

Ha egy $\displaystyle \varphi$ irányú egyenes nem választja el egymástól az A és B pontokat, akkor a töröttvonalat páros sokszor, tehát legfeljebb csak 6-szor metszi. Ezért

v($\displaystyle \varphi$)$\displaystyle \le$6n($\displaystyle \varphi$)+h($\displaystyle \varphi$).

(Lásd az 1. ábrát.)

1. ábra	2. ábra

Vegyük az egyenlőtlenség $\displaystyle \varphi$ szerinti átlagát, azaz integráljunk $\displaystyle \varphi$ szerint 0-tól $\displaystyle \pi$-ig, és osszuk el az integrált $\displaystyle \pi$-vel. Könnyen ellenőrizhető, hogy egy x hosszú szakasz vetületének átlaga $\displaystyle {2\over\pi}x$, az egységnégyzeté $\displaystyle {4\over\pi}$, tehát

$\displaystyle {2\over\pi}l\le6\cdot{4\over\pi}+{2\over\pi}AB,$

$\displaystyle l\le12+AB\le12+\sqrt2.$

Ez az eredmény éles. Ha a töröttvonal háromszor végigfut a négyzet kerületén és tartalmazza az egyik átlót, akkor megfelel a feltételnek és a hossza éppen $\displaystyle 12+\sqrt2$ (2. ábra).

A. 315. Egy szabályos (n²+n+1)-szögnek kiválasztottuk n+1 csúcsát. Bizonyítsuk be, hogy ha az n szám 12k-2 alakú, akkor a kiválasztott csúcsok közötti távolságok nem lehetnek mind különbözők.

Megoldás. Tegyük fel indirekten, hogy n=12k-2 és a kiválasztott csúcsok között futó $\displaystyle {n+1\choose2}$ átló mind különböző hosszúságú. A szabályos (n²+n+1)-szögben éppen ennyiféle hosszúságú átló van.

Az n²+n+1 szám osztható 3-mal. Számozzuk meg a csúcsokat sorban 1-től (n²+n+1)-ig, és csoportosítsuk a kiválasztott csúcsok indexeit modulo 3. A három csoportba eső indexek száma legyen a, b, illetve c; a kiválasztott csúcsok száma összesen a+b+c=n+1=12k-1.

Számoljuk össze azokat az átlókat, amelyek hossza a kerületen mérve hárommal osztható, tehát a harmad-, hatod-, kilenced- stb. szomszédos átlókat. Ezek száma $\displaystyle \big[{n+1\choose2}/3\big]=24k^2-6k$. Ilyen átlókat úgy kaphatunk, hogy azonos csoportba tartozó csúcsokat kötünk össze, tehát

$\displaystyle 24k^2-6k={a\choose2}+{b\choose2}+{c\choose2}.$

Ebből

a²+b²+c²=48k-12k+a+b+c=48k-1.

A 8k-1 és speciálisan a 48k-1 alakú számok nem írhatók fel három négyzetszám összegeként. Az indirekt feltevésből ellentmondásra jutottunk.

A. 316. Adott n pozitív egész számhoz tekintsük azon A$\displaystyle \subset${1,2,...,n} halmazokat, amelyekben az x+y$\displaystyle \equiv$u+v (mod n) kongruenciának nincs más megoldása, mint az x=u, y=v, illetve x=v, y=u triviális megoldások. Legyen f(n) az ilyen halmazok elemszámának maximuma.

a) Bizonyítsuk be, hogy $\displaystyle f(n)<\sqrt{n}+1$.

b) Mutassunk példát végtelen sok olyan n-re, amikor $\displaystyle f(n$\sqrt{n}-1">.

A 2002. évi Schweitzer-verseny 4. feladata nyomán

Megoldásvázlat. a) Tekintsük az A-beli elemek különbségeit modulo n; az x-y és y-x különbségeket különböztessük meg. Ha |A|=k, akkor összesen k(k-1) ilyen van, egyik sem 0. Ha valamelyik két különbség megegyezne, akkor azokból nemtriviális megoldást kapnánk. Ezért k(k-1)$\displaystyle \le$n-1, amiből $\displaystyle k\le{1\over2}+\sqrt{n-{3\over4}}<\sqrt{n}+1$.

b) Legyen p tetszőleges prímszám és n=p(p-1); legyen továbbá g egy primitív gyök modulo p. Az A halmaz álljon azokból az x számokból, amelyekre x$\displaystyle \equiv$g^x (mod p). Először is bebizonyítjuk, hogy a modulo n maradékosztályok között pontosan p-1 ilyen van.

Legyen r egy tetszőleges, 0-tól különböző maradék modulo p, és keressük az x$\displaystyle \equiv$r, g^x$\displaystyle \equiv$r (mod p) kongruenciarendszer megoldásait. Az x számot az x$\displaystyle \equiv$r kongruencia meghatározza modulo p, a g^x$\displaystyle \equiv$r kongruencia pedig meghatározza modulo (p-1). Mivel p és p-1 relatív prímek, a kínai maradéktétel szerint a megoldások az egyik modulo p(p-1) maradékosztály elemei.

Konkrét példa: Legyen p=7, n=42 és g=3. (A 3 primitív gyök modulo 7, mivel a 3 hatványai 7-tel osztva minden 0-tól különböző maradékot kiadnak: 3⁰=1, 3¹=3, 3²$\displaystyle \equiv$2, 3³$\displaystyle \equiv$6, 3⁴$\displaystyle \equiv$4 és 3⁵$\displaystyle \equiv$5 (mod 7).) Az x$\displaystyle \equiv$3^x (mod 7) kongruencia megoldásait az alábbi táblázatban foglaltuk össze:

r 3x$\displaystyle \equiv$r (mod 7) megoldása x$\displaystyle \equiv$r, 3x$\displaystyle \equiv$r (mod 7) megoldása 1 x$\displaystyle \equiv$0 (mod 6) x$\displaystyle \equiv$36 (mod 42) 2 x$\displaystyle \equiv$2 (mod 6) x$\displaystyle \equiv$2 (mod 42) 3 x$\displaystyle \equiv$1 (mod 6) x$\displaystyle \equiv$31 (mod 42) 4 x$\displaystyle \equiv$4 (mod 6) x$\displaystyle \equiv$4 (mod 42) 5 x$\displaystyle \equiv$5 (mod 6) x$\displaystyle \equiv$5 (mod 42) 6 x$\displaystyle \equiv$3 (mod 6) x$\displaystyle \equiv$27 (mod 42)

Az A halmaz elemei tehát: 2,4,5,27,31,36.

Végül megmutatjuk, hogy az A halmaz eleget tesz a feltételeknek. Mint láttuk, az A halmaz elemei páronként különbözők modulo p. Tetszőleges x,y$\displaystyle \in$A esetén az x+y érték meghatározza a szorzatot is modulo p, hiszen xy$\displaystyle \equiv$g^xg^y$\displaystyle \equiv$g^x+y. Ha tehát ismerjük x+y-t, akkor meghatározhatjuk xy-t is modulo p, és felírhatunk egy modulo p másodfokú egyenletet, amelynek két gyöke x és y. A másodfokú egyenlet pedig - a sorrendtől eltekintve - egyértelműen meghatározza a gyökpárt. Ha tehát ismerjük x+y értékét, akkor x és y értékét is meghatározhatjuk modulo p; ez pedig meghatározza magát a két elemet is.

Az előbbi példában tegyük fel, hogy azokat az x,y elemeket keressük, amelyekre x+y$\displaystyle \equiv$16 (mod 42). Ekkor x+y$\displaystyle \equiv$2 (mod 7) és xy$\displaystyle \equiv$3¹⁶$\displaystyle \equiv$4 (mod 7). Az x és y számok tehát a t²-2t+4$\displaystyle \equiv$0 (mod 7) kongruencia gyökei. Mivel t²-2t+4$\displaystyle \equiv$(t-3)(t-6) (mod 7), az x,y számok egyike 7-tel osztva 3-at ad maradékul a másik pedig 6-ot. Az egyik szám tehát a 31, a másik a 27.

A bemutatott konstrukcióban n=p(p-1) és |A|=p-1, ezért $\displaystyle f(n)\ge p-$\sqrt{n}-1">. Végtelen sok olyan n-et sikerült tehát találni, amikor $\displaystyle f(n$\sqrt{n}-1">.