Legyen S egy olyan síktartomány, melynek területe nagyobb, mint a pozitív egész n szám. Mutassuk meg, hogy el lehet tolni S-et úgy, hogy legalább n+1 rácspontot lefedjen?
Tegyük fel, hogy az S síktartomány területe nagyobb, mint a pozitív egész n szám. Készítsünk egy rácsot, amelyben a rácsponthoz tartozó koordináták egész számok.
Vegyük észre, hogy ha az S síktartomány területe nagyobb, mint n, akkor az S területén található legalább egy olyan rácsponthoz tartozó pont, amely nem fedett rácspontra esik. Jelöljük ezt a pontot P_1-gyel.
Most eltoljuk az S síktartományt úgy, hogy a pont P_1 a rács egyik pontjára essen. Az eltolás során az S tartomány területe változatlan marad.
Ezután nézzük meg, hogy az S területén található további pontok közül hány olyan van, amely nem fedett rácspontra esik. Jelöljük az új pontot P_2-vel.
Ismét eltoljuk az S síktartományt úgy, hogy a pont P_2 a rács egyik pontjára essen. Ekkor az S tartomány területe továbbra is változatlan marad.
Folytathatjuk ezt az eltolási folyamatot mindaddig, amíg az összes pont, amely nem fedett rácspontra esik, rácspontra nem kerül.
Mivel az S síktartomány területe nagyobb, mint n, és minden eltolás során az S területe változatlan marad, így a fenti eltolási folyamat végén legalább n+1 rácspontra eső pont fog található lenni az S területén.
Ez tehát bebizonyítja, hogy az S síktartományt el lehet tolni úgy, hogy legalább n+1 rácspontra lefedje.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!