Élszínezés 2.

2015-08-26 6:55

Továbbra is rajzolgatunk, színezgetünk, számolgatunk...
Nehéz, beküldte: bolnyi*, szerkesztő: csibe08

Van egy 17 szögpontú teljes gráfunk, amelynek minden élét pirosra, kékre, vagy sárgára színezzük. Teljes gráf alatt az összes lehetséges él berajzolását értjük. Vezessük be a következő definíciót: a gráf akkor tartalmaz egyszínű háromszöget, ha van három olyan pontja, amelyek között futó mindhárom él azonos színű.

Először bizonyítsuk be, hogy ebben a gráfban - tetszőleges színezés mellett - mindenképpen lesz egyszínű háromszög! (5 pont)

Aztán színezzük ki egy 16 szögpontú gráf éleit három színnel úgy, hogy legfeljebb 8 db egyszínű háromszöget tartalmazzon! (5 pont)

A beküldési határidő lejárt, a regisztrálatlanul beküldött új megoldásokat már nem értékeljük!

Új hozzászólás beküldése (már csak regisztráltan beküldött megoldást értékeljük)

A Élszínezés 2. című feladvány statisztikája: A feladványt eddig 5473 felhasználó olvasta, és 40 megoldást küldtek be rá. A feladványt 8 látogató fejtette meg helyesen. Akik helyes megfejtést küldtek be (vastaggal aki határidőn belül): elszin (vendég), horsa, kuvaszkusz, nklari, ocotillo, puosoqop, rizsesz, szmoni65

Ajánld a feladványt másoknak:

Címzett neve: E-mail címe:

Ha be lennél jelentkezve, itt megnézhetnéd a beküldött megoldásokat