Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Az 1999. szeptemberi számban kitűzött A-jelű matematika feladatok megoldásai

A közöltek csak megoldásvázlatok, esetleg csak végeredmények. A maximális pontszám eléréséhez általában ennél részletesebb megoldás szükséges. A részletes megoldásokat a beküldött dolgozatok alapján a KöMaL-ban folyamatosan közöljük.


A. 215. A P, Q és R pontok úgy helyezkednek el az O középpontú egyenletű ellipszoidon, hogy az OP, OQ, OR szakaszok páronként merőlegesek egymásra. Mutassuk meg, hogy a PQR sík és O távolsága nem függ P, Q, és R megválasztásától.

Jugoszláv versenyfeladat

Megoldásvázlat. Legyen a három koordináta-egységvektor e1, e2, e3, ezen kívül OP=d1, , OQ=d2, , OR=d3, . Végül legyen uij=eivj (i,j=1,2,3).

Legyen T az origó vetülete a PQR síkra. Könnyen látható, hogy , és . Azt kell tehát igazolni, hogy az utóbbi összeg állandó.

A feltételek szerint a v1, v2, v3 vektorok egységnyi hosszúak és páronként merőlegesek. Ebből következik, hogy tetszőleges i-re

ui12+ui22+ui32=|ei|2=1.   (1)

Az ellipszoid egyenletébe behelyettesítve P, Q, R koordinátáit, azaz a (dju1j,dju2j,dju3j) számhármasokat,

,

azaz

.

Ezeket összegezve j értékeire,

= = .

Megjegyzés. A megoldás szó szerint ugyanígy megy akárhány dimenzióban.


A. 216. Bizonyítsuk be, hogy tetszőleges n pozitív egészhez létezik olyan legfeljebb n-edfokú, egész együtthatós p polinom, hogy páros x egész szám esetén p(x) osztható 2n-nel, páratlan x esetén pedig p(x)-1 osztható 2n-nel.

Javasolta: Hajnal Péter, Szeged

Megoldásvázlat.

1. lemma. Elég, ha a feltétel a p(0), p(1), ..., p(n) számokra teljesül, ebből már következik az összes többi egész számra.

Bizonyítás. Ismeretes, hogy ha a p polinom foka kisebb, mint m, akkor

.   (1)

Ezt mi természetesen az m=n+1 választással fogjuk használni.

Legyen r(x)=0 ha x páros, és legyen r(x)=1 ha x páratlan. Ha p helyett ezt a függvényt írjuk (1) baloldalára, akkor x paritásától függően 2n-t kapunk, mert a páros illetve páratlan indexű binomiális együtthatók összege 2n.

Tegyük fel, hogy p(x-1), p(x-2), ..., p(x-n-1) a megfelelő maradékot adja 2n-nel osztva. Ekkor

,

a jobboldalon minden tag osztható 2n-nel, tehát p(x)r(x) mod 2n, vagyis p(x) maradéka is jó. Hasonlóan kapjuk, hogy p(x-n-2) maradéka is megfelelő. A 0, 1, ..., n számokból kiindulva, ilyen lépésekkel bármelyik egész számhoz eljuthatunk.

2. lemma. Tetszőleges 0<n, 0kn egész számokra, a k!(n-k)! szám prímtényezős felbontrásában a 2 kitevője legfeljebb n-1.

Biz. A k!(n-k)! szám osztója az n!-nak (a hányadosuk , a Legendre formula szerint a 2 kitevője az n!-ban

.

Most teljes indukcióval igazoljuk a megfelelő p polinom létezését. Tegyük fel, hogy a q polinom megfelelő n helyett (n-1)-gyel. Ebből konstruáljuk p-t a következő alakban:

,   (2)

ahol a0, ..., an alkalmas egész számok.

Az 1. lemma alapján az a0, ..., an számokat úgy kell megválasztani, hogy 0kn esetén p(k) r(k) mod 2n teljesüljön. (2) alapján

p(k)=q(k)+(-1)n-kk!(n-k)!.ak.

Az indukciós feltevés szerint q(k)r(k) mod 2n-1, a 2. lemma szerint k!(n-k)!-ban a 2 kitevője legfeljebb n-1, ezért az ak biztosan megválasztható a kívánt módon.

Megjegyzés. Speciális n-ekre közvetlenül is lehet megfelelő polinomot konstruálni. Könnyen látható, hogy x2mr(x) mod 2m+1 tetszőleges x egész szám esetén, ugyanakkor az (x+1)(x+2)...(x+2m) polinom értéke minden egész helyen osztható 22m-1-nel. Mindezekből következik, hogy ha az x22m polinomot elosztjuk az (x+1)(x+2)...(x+2m) polinommal, akkor a maradékul kapott polinom megfelelő lesz n=(2m-1)-re.


A. 217. Az a1, a2, ..., an pozitív egészek legnagyobb közös osztója 1, és közülük bármelyik kettőnek ugyanaz a legkisebb közös többszöröse. Bizonyítsuk be, hogy létezik egy olyan p egész szám, hogy tetszőleges u egész szám esetén u és p-u közül pontosan az egyik írható fel a1x1+a2x2+...+anxn alakban, alkalmas x1, ..., xn nemnegatív egészekkel.

Megoldásvázlat.

Mint könnyen ellenőrizhető, az a1,..., an számokra vonatkozó feltétel azzal ekvivalens, hogy megfelelő, páronkét relatív prím b1,..., bn pozitív egészekkel ai=b1...bi-1bi+1...bn.

Bebizonyítjuk, hogy a feladat állításának megfelelő szám

p=(n-1)b1b2...bn-a1-...-an.    (1)

Legyen u tetszőleges egész szám, és tegyük fel, hogy felírható a kívánt alakban:

a1x1+...+anxn=u.

Vizsgáljuk ezt az egyenletet modulo bi. A baloldalon ai kivételével az összes együttható osztható ai-vel, ezért

aixi=(b1...bi-1bi+1...bn)xiu mod bi.

Legyen i(u) a legkisebb olyan nemnegatív egész, amelyre

(b1...bi-1bi+1...bn) i(u) u mod bi.

Az előbbiek alapján, figyelembe véve, hogy bi relatív prím (b1...bi-1bi+1...bn)-nel,

xii(u) mod bi,

másrészt, i(u) minimalitása miatt xii(u). Bevezetve tehát az jelölést,

egy nemnegatív egész szám.

Vezessük be a

   (2)

függvényt. Eddig azt láttuk, hogy ha u előállítható, akkor h(u) egy nemnegatív egész szám. Az is biztos, hogy h(u) mindig egész, mert (2) számálójában tetszőleges i-re u-aii(u) osztható bi-vel, a maradék tagokban pedig az aj együttható osztható vele. Ha a h(u) egész szám nemnegatív, akkor u egy megfelelő előállítását kapjuk az x1=1(u)+h(u), x2=2(u), ..., xn=n(u) számokkal.

Ezzel bebizonyítottuk, hogy u akkor és csak akkor állítható elő, ha h(u)0.

Vizsgáljuk most az u és p-u számokat. Tetszőleges i-re

aii(u)+aii(p-u)p-ai mod bi,

amiből

i(u)+i(p-u)-1 mod bi.   (3)

Mivel i értéke mindig 0 és bi-1 közé esik, (3) csak úgy teljesülhet, ha i(u)+i(p-u)=bi-1. Ezt beírva h(u)-ba és h(p-u)-ba,

h(u)+h(p-u)=u-a1 = = = = -1.

Ebből következik, hogy a h(u) és h(p-u) egész számok közül pontosan az egyik nemnegatív, azaz u és p-u közül pontosan az egyik állítható elő.