Feladat: N.56 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Bárász Tamás ,  Burcsi Péter ,  Elek Péter ,  Gröller Ákos ,  Izsák Ferenc ,  Pap Gyula ,  Póczos Barnabás ,  Szádeczky-Kardoss Szabolcs ,  Tóth Gábor Zsolt ,  Valkó Benedek ,  Zubcsek Péter Pál 
Füzet: 1995/október, 422 - 423. oldal  PDF file
Témakör(ök): Konstruktív megoldási módszer, Algoritmikus eljárások, Vektorok lineáris kombinációi, Nehéz feladat
Hivatkozás(ok):Feladatok: 1995/január: N.56

A kétdimenziós koordináta-rendszer rácspontjain egy méretei miatt nem látható bolha ugrál. Az origóból indul, és minden perc huszadik másodpercében az u1, u2, u3 vektorok valamelyikével ugrik arrébb, esetleg nem mozdul. Az általunk is ismert u1, u2, u3 vektorok nem fekszenek egy félsíkban. Mi minden perc negyvenedik másodpercében megmérgezhetünk két rácspontot. Ha a bolha éppen ezek egyikén áll, vagy később mérgezett rácspontra ugrik, jól hallható hangon felkiált: ,,NYEKK!'', és örökre elnémul. El tudjuk-e pusztítani a bolhát?

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Meg fogjuk mutatni, hogy létezik egy olyan A0, A1, ..., An pontsorozat, amelynek első és utolsó eleme az origó, és a bolha mindegyik Ai-ből tud ugrani Ai+1-be. Bebizonyítjuk, hogy ez elégséges ahhoz, hogy a bolhát el tudjuk pusztítani.
Az Ai pontból a u1, u2, u3 vektorok három különböző pontba mutatnak, ezek közül az egyik az Ai+1 pont. A másik két pontot jelöljük Bi-vel és Ci-vel.
Az első n lépésben mérgezzük meg sorban a B0 és C0, B1 és C1, ..., Bn-1 és Cn-1 pontokat. Az F. 3048. feladat megoldásában leírtakhoz hasonlóan igazolható, hogy k perc eltelte után (0kn) a bolha vagy már elpusztult, vagy az A0, ..., Ak pontok valamelyikén tartózkodik.
Az n-edik perc letelte után a bolha (ha még él) már csak az A0A1A2...An-1A0 körpályán ugrálhat, mert mind megmérgeztük a B0, ..., Bn-1, C0, ..., Cn-1 pontokat. A körpálya pontjait sorban megmérgezve biztosan elpusztíthatjuk a bolhát.
A megfelelő A0, ..., An pontok létezése azzal ekvivalens, hogy létezzenek olyan a1, a2, a3 nemnegatív egész számok, amelyek nem mind 0-k, és teljesül rájuk, hogy

a1u1+a2u2+a3u3=0.(1)
Bebizonyítjuk, hogy ha az u1, u2, u3 vektorok nincsenek egy félsíkban, akkor léteznek ilyen számok. Először azt mutatjuk meg, hogy ha (1) teljesül valamilyen valós együtthatókkal (feltéve, hogy van köztük 0-tól különböző), akkor az együtthatók közül egyik sem lehet 0, és az együtthatók azonos előjelűek. Ha valamelyik együttható 0 lenne, akkor a másik két vektor konstansszorosa lenne egymásnak, és a három vektor egy félsíkba esne. Az együtthatók tehát 0-tól különböznek.
A három együttható között biztosan van két azonos előjelű; a szimmetria miatt feltehetjük, hogy ez a két szám a1 és a2. Ha a3 előjele ezekkel ellentétes, akkor u3 felírható u1 és u2 olyan lineáris kombinációjaként, amelyben az együtthatók pozitívak:
u3=-a1a3u1+-a2a3u2.
Ebből viszont következik, hogy u3 benne van abban a szögtartományban, amelyet u1 és u2 zár be, a három vektor ismét egy félsíkba esik, ami ellentmondás. Az a1, a2, a3 együtthatók tehát csak azonos előjelűek lehetnek.
Legyenek az ui vektor koordinátái xi és yi. Könnyen ellenőrizhető, hogy
(x2y3-x3y2)u1+(x3y1-x1y3)u2+(x1y2-x2y1)u3=0.
Ebben az azonosságban az együtthatók egész számok, amelyek csak akkor lehetnének 0-k, ha a megfelelő két vektor párhuzamos lenne. Az előbb látottak alapján vagy mindhárom szám pozitív, vagy mindhárom negatív. Az előbbi esetben ezeket az együtthatókat, az utóbbi esetben az ellentettjeiket választhatjuk a1, a2, a3-nak. Ezzel bebizonyítottuk, hogy léteznek megfelelő A0, A1, ..., An pontok, következésképpen a bolha elpusztítható.
 Zubcsek Péter Pál (Fazekas M. Főv. Gyak. Gimn., I. o.t.) dolgozata alapján