Feladat: F.2513 Korcsoport: 16-17 Nehézségi fok: nehéz
Füzet: 1985/november, 366. oldal  PDF file
Témakör(ök): Gráfelmélet, Kombinatorikus geometria térben, Legnagyobb közös osztó, Feladat
Hivatkozás(ok):Feladatok: 1985/február: F.2513

Igaz-e, hogy bármely poliéder csúcsaira lehet úgy pozitív egész számokat írni, hogy bármely két csúcson pontosan akkor állnak egymáshoz relatív prím számok, ha a két csúcs szomszédos a poliéderen?

Kössünk össze képzeletben két csúcsot egy ,,piros'' éllel, ha nem szomszédosak, és ,,írjunk rá'' minden ilyen ,,piros'' élre egy prímszámot, mindegyikre különbözőt. A szomszédos csúcsokat összekötő élek mindegyikére írjuk az 1-es számot. Ezután minden egyes csúcsra számítsuk ki a belőle induló piros és valódi élekre írt számok szorzatát, és írjuk ezt a számot az adott csúcsra.
Két számnak akkor és csak akkor van 1-nél nagyobb közös osztója, ha van közös prímosztójuk is. Ez most a két csúcshoz kiszámított szorzatra pontosan akkor teljesül, ha a két csúcsot piros él köti össze. Ez pedig éppen akkor fordul elő, ha a két csúcs nem szomszédos a poliéderen. A csúcsokra felírt számok közül így pontosan akkor lesz kettő relatív prím, ha a megfelelő két csúcs szomszédos.
A feladat kérdésére tehát igenlő a válasz.
 

Megjegyzés. A bizonyításban felhasználtuk, hogy bármennyi legyen is a ,,piros élek'' száma, létezik különböző prímszám. De ismeretes, hogy végtelen sok prímszám van. Nem használtuk viszont fel, hogy poliéderről van szó. Bármely gráf csúcsaira írhatók pozitív egészek úgy, hogy két csúcsot pontosan akkor köt össze él, ha a ráírt számok relatív prímek.