[2479] Enkidu | 2007-12-05 13:31:00 |
Egy ezzel a példával kapcsolatos aranyos (bár elég egyszerű) példa a következő:
Sherlock Holmes ősi ellenfele Mortimer ellopta a Mona Lisát a párizsi Louvre-ból. Holmes éppen Péterváron volt és rögtön repülőre ült, hogy elkapja a gazfickót. (Európa repülőtereit a lenti ábra mutatja; egy lépésben csak egy szomszédos repülőtérre repülhetünk, azaz pl Pétervárról közvetlenül csak Moszkva, Vilnius és Stockholm érhető el.) Miután Holmes lépett egyet Mortimernek is lépnie kell (ha túl sokáig maradna egy helyen elkapnák a rendőrök). Vagyis a két játékos felváltva lép. Ha Holmesnak sikerül ugyanabba a városba repülnie, ahol éppen akkor Mortimer tartózkodik, akkor elkapja és vége a játéknak. Ha Mortimer 15 lépés után is szabad, végleg megmenekült. El lehet-e fogni Mortimert? Ha igen, hogyan?
|
|
Előzmény: [2468] rizsesz, 2007-12-04 08:45:58 |
|
|
|
[2476] HoA | 2007-12-05 11:11:43 |
Nem is tudom, most örüljek-e, hogy sikerült rájönni egy megoldásra, amihez valóban elég egy 8 éves tudása. Az ebben a megoldásban felhasznált tulajdonság felismeréséhez nem a 10 négyszög léte, hanem az segít, ami hiányzik az ábráról :-)
|
Előzmény: [2474] rizsesz, 2007-12-04 14:05:10 |
|
|
|
[2473] Hajba Károly | 2007-12-04 14:01:11 |
A vonalak 10 db négyszöget határoznak meg. Ha ezeket átalakítjuk egy újabb gráffá úgy, hogy a négyzetek a gráfcsúcsok és a csatlakozó él az új gráf élei, akkor ebben a gráfban is meg kellene tudni csinálni az összekötést. Ha nem sikerül, akkor az eredetiben sem lehet.
Persze tudom ez nem bizonyítás. Inkább csak morfondíroztam egyet. :o)
|
Előzmény: [2471] Csimby, 2007-12-04 12:47:51 |
|
[2472] rizsesz | 2007-12-04 13:58:02 |
Akkor gondolj arra, hogy a hivatalos megoldás tulajdonosa 2. osztályos volt. És nem középiskolás, hanem általános iskolás, azaz 8 éves. Szóval érdemes elrugaszkodni egy kicsit attól, amit az ember tud, és olyan fejjel gondolkodni, mintha csak nagyon alapvető eszközeink lennének. :)
|
Előzmény: [2470] Hajba Károly, 2007-12-04 12:38:43 |
|
[2471] Csimby | 2007-12-04 12:47:51 |
Szerintem is egy szép feladat :-) Ha alég sokáig nézi az ember a gráfot, akkor észre lehet venni valamit ami nagyon sokat segít.
|
|
[2470] Hajba Károly | 2007-12-04 12:38:43 |
Elvileg ez egy nyílt Hamilton-kör lenne, amire nincs egyértelmű megoldhatósági kritérium, mint az Euler-körre van. Nekem úgy tűnik, nem létezik Hemilton-kör, de a gráfok mélységében nem vagyok eléggé járatos, így nem tudom bizonyítani.
|
Előzmény: [2467] Csimby, 2007-12-04 01:26:25 |
|