Dajú sa každému zo siedmich študentov priradiť na riešenie práve tri zo siedmich rôznych príkladov tak, aby každý príklad dostali práve traja študenti a aby žiadna dvojica študentov nemala viac než jeden spoločný príklad?
Stačí nájsť kubický bipartitný graf s 14 vrcholmi, bez kružnice dĺžky 4. Obe partície majú 7 vrcholov, jedna reprezentuje študentov a druhá príklady. K-ty vrchol z prvej partície je spojený hranou s l-tým vrcholom z druhej partície práve vtedy, keď k-temu študentovi bol pridelený l-tý príklad. Graf neobsahuje kružnicu dĺžky 4 práve vtedy, keď dvom rôznym študentom nebola pridelená rovnaká dvojica príkladov. Taký graf existuje, napr. tento.
Katka: fajn. Tvoje riešenie som načrtol týmto obrázkom (rôzne príklady sú reprezentované štvorčekmi rôznych farieb). Dodal by som, že takýto problém je okrem teórie grafov možné formulovať aj v terminológii konečných geometrií, kde študenti sú "body" a príklady sú "priamky" (pozri Fano plane) a tiež v reči blokových designov.
Dajú sa každému zo siedmich študentov priradiť na riešenie práve tri zo siedmich rôznych príkladov tak, aby každý príklad dostali práve traja študenti a aby žiadna dvojica študentov nemala viac než jeden spoločný príklad?
3 komentáre:
Stačí nájsť kubický bipartitný graf s 14 vrcholmi, bez kružnice dĺžky 4. Obe partície majú 7 vrcholov, jedna reprezentuje študentov a druhá príklady. K-ty vrchol z prvej partície je spojený hranou s l-tým vrcholom z druhej partície práve vtedy, keď k-temu študentovi bol pridelený l-tý príklad. Graf neobsahuje kružnicu dĺžky 4 práve vtedy, keď dvom rôznym študentom nebola pridelená rovnaká dvojica príkladov. Taký graf existuje, napr. tento.
Katka: fajn. Tvoje riešenie som načrtol týmto obrázkom (rôzne príklady sú reprezentované štvorčekmi rôznych farieb). Dodal by som, že takýto problém je okrem teórie grafov možné formulovať aj v terminológii konečných geometrií, kde študenti sú "body" a príklady sú "priamky" (pozri Fano plane) a tiež v reči blokových designov.
Úloha by sa dala riešiť aj programovaním s obmedzujúcimi podmienkami.
Zverejnenie komentára