--> Archiwum Forum
wikser [ Pretorianin ]
zgadka logiczna
mialem wlasnie kolosa z grafow :) pytanie jedfno bylo takie: czy ruchem konika szachowego mozna "objechac" plansze 3 x 5 nie wstepujac 2 razy na to samo pole? jezeli nie ile mozna najwiecej?
Lookash [ Generaďż˝ ]
Ehh... Stary - ferie swiateczne sie zaczely, mozg mam juz dawno wylaczony ;) Sprobuj w przyszlym tygodniu w okolicach srody ;P
Polski Gracz [ Legionista ]
nie zal ci ludzi tak z rana zadawac takie pytania? zlituj sie chlopie przerwa swiateczna sie zaczela :)
grish_em_all [ Hairless Cobra ]
człowieku, błagam zapytaj o pogodę a nie męczysz zmęczonych ludzi jakimiś dziwnymi pytaniami.
za trzy tygodnie (niecałe) mam maturę i muszę choć trochę odpocząć
draczeek [ Konsul ]
>> czy ruchem konika szachowego mozna "objechac" plansze 3 x 5 nie wstepujac 2 razy na to samo pole?
nie można.
>>jezeli nie ile mozna najwiecej?
Na teorii grafów się nie wyznaję, ale rozwiązanie optymalne mogłoby wyglądać tak jak na rysunku obok.
Ciekawe jak się wyznacza optimum takiego problemu.
diuk [ Konsul ]
wikser --> nie można, graf wszelkich możliwych ruchów konika szachowego na takiej planszy nie spełnia twierdzenia Ore (dla każdej pary niepołączonych wierzchołków suma wychodzących krawędzi musiała by być większa lub równa ilości wierzchołków grafu).
wikser [ Pretorianin ]
nie znalem twierdzenia ore :) nie mialem jeszcze czegos takiego :)
draczek >> a rozwiazanie jest lepsze przynajmniej o 1 ale nie pamietam go