Feladat: A.494 Korcsoport: 18- Nehézségi fok: nehéz
Füzet: 2009/december, 542. oldal  PDF  |  MathML 
Témakör(ök): Nehéz feladat, Gráfok összefüggősége, Teljesgráfok, Oszthatóság, Prímszámok, Skatulyaelv

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 p1,...,pk prímszámok, és legyen S az egész számok azon részhalmaza, melynek elemei nem oszthatók p1,...,pk-tól különböző prímszámmal. Az egészek egy véges A részhalmaza esetén jelöljük G(A)-val azt a gráfot, melynek csúcsai az A elemei, élei pedig azon a,bA párok, melyekre a-bS. Létezik-e minden m3-ra egészeknek olyan m elemű A részhalmaza, melyre
(a) G(A) teljes?
(b) G(A) összefüggő, de minden csúcsának a fokszáma legfeljebb 2?