Keresés

Keresendő kifejezés:

Toplista

Toplista
  • betöltés...

Segítség!

Ahhoz, hogy mások kérdéseit és válaszait megtekinthesd, nem kell beregisztrálnod, azonban saját kérdés kiírásához ez szükséges!

Termek

363
a, Egy múzeum egyik szintjén 16 terem van 4x4-es elrendezésben. Két szomszédos terem között mindenhol van ajtó. Melyik teremből elindulva járhatjuk be mind a 16 termet úgy, hogy minden teremben egyszer járunk?
b, A múzeum másik szintjén 25 terem van 5x5-ös elrendezésben. Két szomszédos terem között mindenhol van ajtó. Melyik teremből elindulva járhatjuk be mind a 25 termet úgy, hogy minden teremben egyszer járunk?
Jelenleg 1 felhasználó nézi ezt a kérdést.
0
Középiskola / Matematika

Válaszok

2
Nem tudom, hogy gráfokat tanultok-e éppen és valahogy úgy kellene-e megoldani, én abba most nem gondolok bele.

a)
Mivel lehet csinálni legalább egy olyan bejárást, ami visszajut a kiinduláshoz, ezért bármelyik teremből lehet indulni. (Csinálj egy ilyet, könnyen megy.)

b)
Itt nincs ilyen visszaérkező bejárás, legalábbis én nem találtam. (Most nincs ötletem pillanatnyilag, hogy hogyan lehetne bebizonyítani, hogy nem is lehet.)
Úgy látom, hogy olyan teremből, ami páratlanadik sor páratlanadik oszlopánál van, onnan lehet indítani a bejárást. Olyantól is lehet, ami páros-páros sor-oszlop.
Ami viszont páros-páratlan, onnan nem lehet.

A bizonyítás persze hiányzik...
Módosítva: 2 éve
1

bongolo jól mondja, tehát már csak a b,-t kell bizonyítani.
Az ilyen feladatoknál gyakran segít, ha sakktábla módjára kiszínezzük a mezőket.

Miért nincs visszatérő bejárás:
Az kéne hogy minden termet pontosan egyszer érintve körbe menjünk (az ilyet amúgy Hamilton-körnek nevezik a gráfelméletben, de ez most nem fontos).
Egy ilyen körbejárás során 25 ajtón kell áthaladni, ugyanis 25 terem van. De a ha sakktáblaszerűen kiszínezzük a termeket akkor minden egyes alkalommal amikor egy ajtón áthaladunk, változik a terem színe (fehérről feketére, ill feketéről fehérre). Ha a kiindulási terem mondjuk fekete volt, akkor mire vissza érünk fehér teremben kéne legyünk, mivel páratlan sokszor (25-ször) változott a teremszín. De egy terem nem lehet egyszerre fehér és fekete is, tehát nincs Hamilton-kör.

Miért csak azokról a mezőkről lehet indítani vissza nem térő bejárást, amiket bongolo mondott:
Ha úgy színezzük a termeket, hogy a sarkokban van a fekete, akkor 13 darab fekete, és 12 db. fehér terem van. Vagyis fekete teremből kell indulni, mert ugye felváltva jönnek a színek, és ha fehérből indítanánk, akkor a végére maradna két fekete. Az, hogy a fekete termek tényleg jók is, azt külön-külön megmutathatod róluk (a lehetetlenséget volt nehezebb bizonyítani).
Módosítva: 2 éve
2