Feladat: N.62 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Burcsi Péter ,  Elek Péter ,  Gyarmati Katalin ,  Izsák Ferenc ,  Makai Márton ,  Pap Gyula ,  Póczos Barnabás ,  Tóth Gábor Zsolt ,  Valkó Benedek 
Füzet: 1995/december, 543 - 544. oldal  PDF file
Témakör(ök): Prímtényezős felbontás, Négyzetrács geometriája, Nehéz feladat
Hivatkozás(ok):Feladatok: 1995/március: N.62

Egy rácspontot (az origóból) láthatónak nevezünk, ha a koordinátái relatív prím (egész) számok. Van-e olyan rácspont, amelynek távolsága minden látható rácsponttól legalább 1995 egység?

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.

Legyenek a prímek rendre p1, p2, .... Tekintsük a következő számokat:

A1=p1p2...pk,A2=pk+1pk+2...p2k,Ai=p(i-1)k+1p(i-1)k+2...pik,Ak=p(k-1)k+1p(k-1)k+2...pk2;
és
B1=p1pk+1...p(k-1)k+1,B2=p2pk+2...p(k-1)k+2,Bj=pjpk+j...p(k-1)k+j,Bk=pkp2k...pk2.
Az Ai-k páronként relatív prímek, ugyanis mindnek más-más prímtényezői vannak. Tehát találhatók olyan a1, a2, ..., akN pozitív egész számok, amelyekre A1a1, A2a2, ..., Akak egymást követő pozitív egészek lesznek.
Hasonlóan találhatók b1, b2, ..., bkN, amelyekre B1b1, B2b2, ..., Bkbk egymást követő pozitív egészek lesznek.
Tekintsük az x=A1a1,A2a2,...,Akak és y=B1b1,B2b2,...,Bkbk koordinátákhoz tartozó rácsnégyzetet. Aiai és Bjbj (ahol 1i,jk) oszthatók p(i-1)k+j-vel, tehát nem relatív prímek. Ebből következik, hogy a négyzet nem tartalmaz látható pontot.
Legyen k=21995+1. Ekkor a fentiek szerint konstruált négyzet középpontja megfelel a feladatnak: ettől a ponttól minden látható pont több, mint 1995 egységre van, hiszen a négyzet nem tartalmaz látható pontot.