Az A. 887. feladat (2024. október)

A. 887. A derékszögű koordináta-rendszerben adott egy önmagát nem metsző sokszög, melynek a kerületén nincs rácspont, és a csúcsainak nincs egész koordinátája. Egy pontot félegésznek nevezünk, ha pontosan az egyik koordinátája egész. Jelölje $\displaystyle P_1$, $\displaystyle P_2$, $\displaystyle \ldots$, $\displaystyle P_k$ a sokszög kerületén lévő félegész pontokat. Jelölje $\displaystyle n_i$ a $\displaystyle P_i$ pont nem egész koordinátájának alsó egészrészét. Bizonyítsuk be, hogy az $\displaystyle n_1$, $\displaystyle n_2$, $\displaystyle \ldots$, $\displaystyle n_k$ számokat két részre lehet úgy osztani, hogy a két részben a számok összege megegyezzen.

Javasolta: Bán-Szabó Áron (Budapest)

(7 pont)

A beküldési határidő 2024. november 11-én LEJÁRT.

Világos, hogy a feladat azzal ekvivalens, hogy az $\displaystyle n_1, n_2, \ldots , n_k$ számoknak tudjuk venni egy olyan előjeles összegét, melynek 0 az értéke. Először abban az esetben bizonyítjuk az állítást, amikor a sokszög a pozitív síknegyedbe esik.

A $\displaystyle P=(x_P,y_P)$ pozitív síknegyedben lévő pont alatti rácspontok alatt értsük azon $\displaystyle (x,y)$ rácspontok halmazát, melyekre $\displaystyle 0<x\leq x_P$ és $\displaystyle 0<y\leq y_P$. Világos, hogy a $\displaystyle P$ alatti rácspontok száma $\displaystyle \lfloor x_P\rfloor\cdot \lfloor y_P \rfloor$. Legyen $\displaystyle AB$ a sokszög egyik oldala, ahol $\displaystyle A=(x_A,y_A)$ és $\displaystyle B=(x_B,y_B)$. A feltételek miatt véges sok félegész pont van az $\displaystyle AB$ oldalon, és ezek közül egyik sem az $\displaystyle A$ vagy a $\displaystyle B$. Tegyük fel, hogy $\displaystyle x_A \leq x_B$. Két esetet különböztetünk meg az $\displaystyle y$-koordináták viszonya szerint.

1. eset: $\displaystyle y_A \leq y_B$.

Az $\displaystyle AB$ oldal félegész pontjainak nemegész koordinátáinak egészrészei éppen megmondják, hogy az adott vízszintes vagy függőleges egyenesen hány rácspont van a megfelelő tengelyig (a tengelyen lévő pontot nem beleszámolva). Tehát ha összeadjuk az alsó egészrészeket erre az oldalra, akkor minden $\displaystyle B$ alatti rácspontot pontosan egyszer számoltunk, kivéve azokat a rácspontokat, melyek sem az oldal alatt, sem tőle balra nincsenek, és mindegyik számolt rácspont csak egyszer van számolva, hiszen egy nemnegatív meredekségű oldal esetén nem lehet egyszerre tőle balra és lent is egy pont. A $\displaystyle B$ alatti nem számolt rácspontok éppen azok, amik $\displaystyle A$ alatt is vannak. Tehát az $\displaystyle AB$ oldal félegész pontjaihoz tartozó alsó egészrészek összege $\displaystyle \lfloor x_B\rfloor\cdot \lfloor y_B\rfloor-\lfloor x_A\rfloor\cdot\lfloor y_A\rfloor$.

2. eset: $\displaystyle y_A > y_B$.

Megint számoljuk össze az $\displaystyle AB$ oldal félegész pontjai alatt, és balra lévő rácspontokat a tengelyekig. Azonban most tekintsük az $\displaystyle AB$ oldal azon félegész pontjait, melyeknek $\displaystyle y$-koordinátája az egész negatív előjellel, a többit pozitívval. Nézzük meg, hogy ekkor melyik pontot hányszor számoljuk le. Azon pontokat, amik $\displaystyle A$ és $\displaystyle B$ alatt is vannak egyszer se. Amik $\displaystyle A$ alatt vannak, de nincsenek $\displaystyle B$ alatt, azokat $\displaystyle (-1)$-szer számoljuk. Amik $\displaystyle B$ alatt vannak, de nincsenek $\displaystyle A$ alatt, azokat egyszer számoljuk. És végül azon rácspontokat, melyek az $\displaystyle AB$ oldaltól balra vannak, de nincsenek se az $\displaystyle A$, se a $\displaystyle B$ alatt, azokat egyszer pozitív, egyszer negatív előjellel is megszámoljuk. Ezeket összevetve látható, hogy ezzel az előjelezéssel ebben az esetben is éppen $\displaystyle \lfloor x_B\rfloor\cdot \lfloor y_B\rfloor-\lfloor x_A\rfloor\cdot\lfloor y_A\rfloor$ az előjeles összeg.

Összegezve, tetszőleges $\displaystyle AB$ oldalon lévő félegész pontokhoz tartozó $\displaystyle n_i$ számok megfelelő előjeles összege éppen $\displaystyle \lfloor x_B\rfloor\cdot \lfloor y_B\rfloor-\lfloor x_A\rfloor\cdot\lfloor y_A\rfloor$. Ezt bebizonyítottuk, ha $\displaystyle x_A \leq x_B$, a fordított esetben azt láttuk be, hogy van olyan előjeles összeg, melynek értéke $\displaystyle \lfloor x_A\rfloor\cdot \lfloor y_A\rfloor-\lfloor x_B\rfloor\cdot\lfloor y_B\rfloor$, ám ekkor az összes előjelet megfordítva éppen a $\displaystyle \lfloor x_B\rfloor\cdot \lfloor y_B\rfloor-\lfloor x_A\rfloor\cdot\lfloor y_A\rfloor$ számot kapjuk. Tehát ha $\displaystyle A_1A_2 \ldots A_m$ a sokszög, akkor az összes oldalon megfelelő előjelezéssel az $\displaystyle n_i$-k összege $\displaystyle \lfloor x_{A_i}\rfloor\cdot \lfloor y_{A_i}\rfloor-\lfloor x_{A_{i+1}}\rfloor\cdot\lfloor y_{A_{i+1}}\rfloor$ (ahol $\displaystyle A_{m+1}=A_1$), és ezeket a számokat összeadva minden kiesik, így tényleg 0-t kapunk (itt használtuk, hogy a csúcsok nem lehetnek félegészek).

Most vizsgáljuk meg azt az esetet, amikor a sokszög nem feltétlenül a pozitív síknegyedben van. Legyen $\displaystyle a=\min\{n_1, n_2, \ldots , n_k\}$ és $\displaystyle b=\max\{n_1, n_2, \ldots , n_k\}$. Toljuk el az egész sokszöget az $\displaystyle (N,N)$ vektorral, ahol $\displaystyle N$ olyan nagy egész szám, hogy az eltolt sokszög a pozitív síknegyedbe kerüljön, és $\displaystyle \frac{k-1}{2}(N+b)<\frac{k+1}{2}(N+a)$ teljesüljön. Ilyen $\displaystyle N$ létezik, mert az egyenlőtlenség mindkét oldala lineáris $\displaystyle N$-ben, és a jobb oldalon nagyobb $\displaystyle N$ együtthatója. Világos, hogy ha így eltoljuk a sokszöget, akkor a kapott sokszög félegész pontjainak nem egész koordinátáinak alsó egészrészei éppen az $\displaystyle n_1+N, n_2+N, \ldots , n_k+N$ számok lesznek. Tudjuk, hogy ezekre igaz a feladat állítása. Ráadásul annak is teljesülnie kell, hogy ezen számok tetszőleges előjelezésére, melyre 0 az előjeles összeg, ugyanannyi pozitív és negatív előjel szerepel. Ugyanis ha valamelyikből több lenne (feltehetjük, hogy a pozitívból), akkor legalább $\displaystyle \frac{k+1}{2}$ lenne, így a pozitívak összege legalább $\displaystyle \frac{k+1}{2}(N+a)$. A negatívak összege pedig legfeljebb $\displaystyle \frac{k-1}{2}(N+b)$ lenne, és $\displaystyle N$ választása szerint ezek nem lehetnek egyenlőek. Emiatt tetszőleges előjelezés, melyre az $\displaystyle n_1+N, n_2+N, \ldots , n_k+N$ számok előjeles összege 0, megadja az $\displaystyle n_1, n_2, \ldots , n_k$ számok egy előjelezését, amelyhez tartozó összeg szintén 0 lesz, mert a $\displaystyle +N$ tagok ugyanannyiszor szerepelnek pozitív és negatív előjellel. Ezzel a bizonyítást befejeztük.

2. megoldás

A feladat megoldásának az alapgondolata a következő: számoljuk meg a sokszög belsejében lévő rácspontokat egyszer vízszintes rácsegyenesenként, egyszer pedig függőleges rácsegyenesenként.

Először koncentráljunk azokra félegész pontokra, melyek $\displaystyle x$-koordinátája egész. Azt állítjuk, hogy alkalmas előjellel összeadva ezeket a sokszög belsejében lévő rácspontok számát kapjuk meg. A jelölések egyszerűsítése érdekében jelölje $\displaystyle f(P)$ a $\displaystyle P$ félegész pont nem egész koordinátájának (alsó) egészrészét.

Az állítás bizonyításához haladjunk végig pozitív körüljárás szerint a sokszög kerületén. Ha egy egész $\displaystyle x$-koordinátájú félegész pont egy olyan oldalon van, amely a pozitív körüljárás szerint balról jobbra halad, akkor negatív előjellel vegyük az $\displaystyle y$-koordinátájának egészrészét, ha pedig jobbról balra, akkor pozitívval (függőleges oldalon nem szerepelhet egész $\displaystyle x$-koordinátájú félegész pont, mert akkor lenne egész $\displaystyle x$-koordinátájú csúcs is, ami nem volt megengedve). Így összegezve megkapjuk a rácspontok számát a sokszög belsejében: vegyünk egy függőleges rácsegyenest, amely belemetsz a sokszögbe (csúcson nem mehet át a feltétel miatt). Messe ez az egyenes a sokszöget alulról felfelé az $\displaystyle A_1$, $\displaystyle A_2$,..., $\displaystyle A_{2k}$ pontokban (páros sok pontban kell metszenie, mert a sokszög felváltva van az adott rácsegyenes bal és jobb oldalán, mert csúcs nem lehet rácsegyenesen a feltétel szerint). Azt is tudjuk, hogy az $\displaystyle A_1$ ponton balról jobbra haladunk át, $\displaystyle A_2$-n jobbról balra, és így tovább, váltogatva az irányt. Azt kell tehát belátnunk, hogy a választott rácsegyenesen $\displaystyle -f(A_1)+f(A_2)-f(A_3)+...+f(A_{2k})$ darab rácspont van.

Figyeljük meg, hogy az $\displaystyle A_{2i-1}A_{2i}$ szakaszok a sokszög belsejében vannak, míg az $\displaystyle A_{2i}A_{2i+2}$ szakaszok a sokszögön kívül vannak. Az pedig egyszerűen látható, hogy $\displaystyle f(A_{2i})-f(A_{2i-1})$ éppen az $\displaystyle A_{2i-1}A_{2i}$ szakaszon lévő rácspontok számát adja meg (ehhez egyébként az is elég, ha csak az $\displaystyle A_{2i}$ pontról tudjuk, hogy enm rácspont), ezekből pedig azonnal adódik az előző bekezdés végén lévő állítás.

Ha ezt minden olyan függőleges rácsegyenesre megcsináljuk, amely belemetsz a sokszögünkbe, akkor minden rácspontot számba vettünk pontosan egyszer a sokszög belsejében, és minden egész $\displaystyle x$-koordinátájú félegész pont $\displaystyle y$-koordinátájának egészrészét is szerepeltettük az öszegben + vagy - előjellel pontosan egyszer.

Hasonló elmondható azokkal a félegész pontokkal is, amelyeknek az $\displaystyle y$-koordinátája egész: ha egy ilyen pont olyan oldalon szerepel, amely felülről lefelé haladó oldalon szerepel a pozitív körüljárás szerint végigsétálva a kerületen, akkor negatív előjellel szerepeltessük az $\displaystyle x$-koordinátájának egészrészét, ha pedig alulról felfelé, akkor pozitívval. A fentiekkel analóg módon belátható, hogy ez az előjeles összeg is a sokszög belsejében lévő rácspontokat számolja meg.

A sokszög belsejében lévő rácspontok számának kétféle felírását egyenlővé téve látjuk, hogy minden félegész pont pontosan egyszer szerepel az egyenlőség valamelyik oldalán (aszerint, hogy az $\displaystyle x$- vagy az $\displaystyle y$-koordinátája az egész; mivel nincs rácspont a kerületen, így ez minden félegész pont esetén egyértelműen eldönthető), így ha mindkét oldalról a negatív előjelű tagokat a másik oldalra átvisszük, megkapjuk a bizonyítandót.

Statisztika:

21 dolgozat érkezett.
7 pontot kapott:	Aravin Peter, Bodor Mátyás, Bui Thuy-Trang Nikolett, Czanik Pál, Forrai Boldizsár, Gyenes Károly, Hodossy Réka, Holló Martin, Keresztély Zsófia, Kocsis 827 Péter, Sánta Gergely Péter, Szakács Ábel, Varga Boldizsár, Virág Tóbiás, Wágner Márton.
6 pontot kapott:	Morvai Várkony Albert, Tianyue DAI, Vámosi Bendegúz Péter, Vödrös Dániel László.
3 pontot kapott:	1 versenyző.
2 pontot kapott:	1 versenyző.

A KöMaL 2024. októberi matematika feladatai