umzugrätsel

Neue Frage »

weisbrot Auf diesen Beitrag antworten »
umzugrätsel
hallo alle! hier ein kleines rätsel:
es gibt 5 mal 5 grundstücke (also so rasterartig angeordnet), auf jedem steht ein haus, in dem jeweils eine person wohnt. nun wollen alle umziehen. regeln dafür: jeder zieht genau einmal um, alle gleichzeitig, jeweils nur in das haus eines jeweils waagerecht oder senkrecht (also im osten, westen, norden oder süden) angrenzenden grundstücks, also nicht diagonal. und natürlich muss am ende wieder genau eine person in genau einem eigenen haus wohnen.
gib hierfür eine möglichkeit an, oder beweise, dass das nicht möglich ist.
viel spaß/erfolg beim rätseln smile
galoisseinbruder Auf diesen Beitrag antworten »

Ich würd´sagen das es nicht möglich ist.
Mein Beweis ist aber nur, dass ich per Brute-Force keinen Hamiltonkreis finde. Das geht bestimmt aber deutlich schöner, oder?
weisbrot Auf diesen Beitrag antworten »

keine ahnung was brute-force ist, aber ja, der beweis ist sehr einfach (im sinne von "kurz") und schön.
es gibt aber natürlich verschiedene schöne beweismöglichkeiten.
galoisseinbruder Auf diesen Beitrag antworten »

brute-force ist auf deutsch rohe Gewalt und heißt nichts anderes als alle Möglichkeiten durchzugehen.
weisbrot Auf diesen Beitrag antworten »

haha mach das mal geschockt
das ist in der tat nicht besonders elegant

edit: man kann das ganze ja auf größere raster ausdehnen, dann ist diese methode ziemlich unmöglich

edit2: jaja computerbeweis - das ist die steigerung von unelegant smile
galoisseinbruder Auf diesen Beitrag antworten »

Wenn man brute-force per Hand und nicht per Computer ist es ein bisschen leichter ein paar Fälle rauszuschmeisen (so wie hier Fälle die durch Drehungen und Spiegelungen entstehen), aber es ist trotzdem das Gegenteil zu elegant.
 
 
sk1982 Auf diesen Beitrag antworten »
RE: umzugrätsel
man kann das ganze als schachbrett sehen, gekachelt mit weissen und schwarzen feldern.

nun überdeckt man das mit kacheln der größe 2, so dass jede kachel genau 1 schwarzes und 1 weisses feld abdeckt. ist eine solche überdeckung möglich, so auch ein entsprechender tausch (die beiden auf der kachel tauschen einfach wohnungen).

oder man geht so vor: es ist möglich, wenn man das "feld" so zerlegen kann, dass jeder teil "funktioniert".
weisbrot Auf diesen Beitrag antworten »
RE: umzugrätsel
ging schonmal fast in die richtige richtung, aber das ist natürlich keine lösung für dieses rätsel.

Zitat:
nun überdeckt man das mit kacheln der größe 2, so dass jede kachel genau 1 schwarzes und 1 weisses feld abdeckt. ist eine solche überdeckung möglich, so auch ein entsprechender tausch (die beiden auf der kachel tauschen einfach wohnungen).

oder man geht so vor: es ist möglich, wenn man das "feld" so zerlegen kann, dass jeder teil "funktioniert".

wenn du zeigen kannst, dass diese hinreichende(n) bedeingung(en) für das funktionieren des umziehens hier gelten, kauf ich dir ein eis Augenzwinkern
sk1982 Auf diesen Beitrag antworten »
RE: umzugrätsel
ja, ist auch noch unvollständig, das kam mir dann danach, muss mal die tage nochmal drüber nachdenken.
René Gruber Auf diesen Beitrag antworten »

Ich hab den Thread erst heute entdeckt, aufgrund dieses Hinweises.

Die Lösung ist doch denkbar einfach:

Wir färben die ganze Siedlung schachbrettartig ein, d.h. etwas mit 13 weißen und 12 schwarzen Feldern, wo die einzelnen Häuser stehen. Die Umzugsregeln bedeuten nun, dass jeder Bewohner eines weißen Hauses in ein schwarzes umziehen muss, und umgekehrt. Wegen ist das offenbar unmöglich zu realisieren. Augenzwinkern


P.S.: Also künftig bitte etwas mehr Zurückhaltung bei Einschätzungen wie "dieses Rätsel wohl zu knifflig für das Matheboard". smile
weisbrot Auf diesen Beitrag antworten »

yay! geht doch!

aber schon klar wie das gemeint war, oder? smile
sk1982 Auf diesen Beitrag antworten »

ah, schade, du warst schneller als ich smile
Neue Frage »
Antworten »



Verwandte Themen