Feladat: Gy.2583 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Matolcsi Máté 
Füzet: 1990/szeptember, 257 - 259. oldal  PDF  |  MathML 
Témakör(ök): Gráfok összefüggősége, Gráfok komplementere, Partíciós problémák, Gyakorlat
Hivatkozás(ok):Feladatok: 1989/november: Gy.2583

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.

I. megoldás. Írjuk számainkat egy 13 oldalú konvex sokszög csúcsaira, rajzoljuk meg a sokszög 13⋅12=78 átlóját és oldalát, és közülük színezzük pirosra mindazokat, amelyekről tudjuk, hogy a végpontjaira írt számok összege egész. Ábránkon a feltétel szerint így 11 darab nem piros szakasz van.
Szemeljünk ki ezután a számok közül kettőt, jelölje őket ‐ és a sokszög megfelelő csúcsait is ‐ A és B, a további 11 darab számot és a megfelelő csúcsokat C1, C2, ..., C11.
Megadunk 12 olyan, az A-ból a B-be ‐ a megrajzolt élek mentén ‐ haladó útvonalat, hogy semelyik kettőnek nincs közös szakasza. Ezek az AB, AC1C2B AC2C3B, ..., AC10C11B, végül az AC11C1B. Mivel összesen 11 nem piros él van, a fenti útvonalak között van olyan, amelynek minden egyes szakasza piros. Ha ez maga az AB, akkor készen vagyunk, A+B egész. Ha pedig az ACiCi+1B (ahol C12=C1) útvonal szakaszai pirosak, akkor A+B=(A+Ci)-(Ci+Ci+1)+(Ci+1+B) miatt ismét azt kapjuk, hogy a kiszemelt számok összege, A+B egész. Ezzel a bizonyítást befejeztük.

 
Megjegyzések. 1. Hasonlóan igazolható, hogy ha n≧5 és n adott valós számból készíthető (n2) darab összeg közül (n-12)+1 darabról tudjuk, hogy egész, akkor ebből következik, hogy valamennyi kéttagú összeg egész. Az, hogy maguk a számok is egészek, természetesen nem következik a feltételből, amelyik nyilván teljesül, ha például valamennyi megadott szám értéke 1/2.
2. A feladat állítása nem igaz, ha n=3 vagy 4, ahogy a {8, 1; 0, 1; 0, 9}, illetve a {8, 1; 0, 1; 10, 9; 0, 9}, példák mutatják. A bizonyításból is kiolvasható, hogy a C-típusú pontokból legalább háromra van szükség.
3. A feladat állítása nyilván éles. Ha csak 66 ‐ illetve általában n-1choose2 ‐ összegről tudjuk, hogy egész, akkor ez lehetséges úgy, hogy az n darab szám közül n-1 egész, egy pedig nem az.
4. A fenti bizonyítás során lényegében arra volt szükségünk, hogy ha n≧5 és egy n pontú gráfnak (n-12)+1 éle van, akkor a gráf bármely két pontja között vezet páratlan hosszú út.
 

II. megoldás. Néhány gráfelméleti alapfogalom és a rájuk vonatkozó elemi ismeretek birtokában másik megoldás is készíthető. Legyen n≧5, és adott n darab valós szám, melyekről tudjuk, hogy a belőlük készíthető kéttagú összegek közül (n-12)+1 egész. Készítsük el az első megoldás G gráfját ‐ a piros élekből. Ismeretes, hogy egy n pontú összefüggő gráfnak legalább n-1 éle van, másfelől, hogy bármely G gráf és a komplementere közül legalább az egyik összefüggő. Mivel most G komplementerének (n2)-(n-12)-1=n-2 éle van, így nem lehet összefüggő; tehát a G gráf az.
Ez azt jelenti, hogy a G gráf bármely két A,B csúcsa között vezet út. Ha ennek a hossza páratlan, akkor az első megoldás szerint az út kezdő és végpontjához írt számok összege egész, ha pedig páros, akkor hasonlóan kapjuk, hogy A-B egész szám.
Helyettesítsük most mindegyik számot a törtrészével, ez az összegek egész, vagy nem egész voltát nem befolyásolja. Szemeljünk ki egy tetszőleges csúcsot, legyen a ráírt szám α. Ekkor 0≦α<1. Ha α=0, akkor persze a többi csúcsokon is egész számok állnak, ha pedig α>0, akkor minden más csúcson vagy α, vagy pedig 1-α áll.
Megmutatjuk, hogy ekkor α=1-α, azaz mindegyik számnak 1/2 a törtrésze. Tegyük fel, hogy ez nem így van, és osszuk két csoportba a G csúcsait aszerint, hogy α vagy 1-α van-e rájuk írva: Ha az első csoportba k csúcs került, akkor 1≦k<n. (k=n nem lehetséges, mivel akkor egyetlen éle sem volna a gráfnak.) Feltevésünk szerint a≠1-α, így az egyes csoportokon belül nem haladhat éle a G-nek, hisz máskülönben 2α=1, vagy 2(1-α)=1 miatt α=1-α=12. Így viszont a gráfnak legfeljebb k(n-k) darab éle lehet.
Ez az érték azonban kisebb a G élei számánál, ugyanis n≧5 esetén k(n-k)≦n24<(n-12)+1.