|
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. Megoldás. Ha a számok között van három 3-mal osztható, akkor a feladat állítása teljesül, hiszen ezek közül bármely kettő legnagyobb közös osztója 0 maradékot ad 3-mal osztva. Feltehetjük tehát, hogy a számok között legfeljebb kettő 3-mal osztható van. Ebben az esetben ki tudunk közülük választani hatot úgy, hogy azok között legfeljebb egy legyen 3-mal osztható. Ekkor a hat szám közül bármely kettő legnagyobb közös osztója 1 vagy 2 maradékot ad 3-mal osztva. Tekintsük azt a 6 csúcsú gráfot, amelynek csúcsai ennek a 6 számnak felelnek meg, két csúcsot piros éllel kötünk össze, ha a végpontjainak megfelelő számok legnagyobb közös osztója 1 maradékot ad 3-mal osztva, és kék színnel, ha 2 maradékot ad. Elegendő megmutatnunk, hogy a gráfban van egyszínű háromszög. Válasszuk ki az egyik csúcsot, -t, ebből a skatulya-elv miatt biztosan indul három azonos színű, mondjuk piros él. Ha ezen élek végpontjai közül kettőt piros színű él köt össze, akkor -val együtt egy egyszínű piros háromszöget alkotnak. Ha viszont bármely kettőt kék színű él köt össze, akkor azok a csúcsok egy egyszínű kék háromszöget alkotnak. Minden esetben létrejön egyszínű háromszög, így beláttuk, hogy kiválasztható három szám a feltételeknek megfelelően.
|
|
PDF |