Hexominorätsel

[Andreas Last]

Hallo Leute,
ich hab mal ein Rätsel für die Chefmathemathen unter uns. Jeder andere darf aber auch mitmachen :-D Und hier kommt das Rätsel:

Existiert ein Raster aus x Spalten und x Zeilen, das unter beliebig häufiger Verwendung aller Hexominos, die sich aus einem Würfel auffalten lassen vollständig gefüllt werden kann? Wenn ja, wie groß müsste es mindestens sein?

Zur Erklärung:
Hexominos sind zweidimensionale Gebilde aus 6 zusammenhängenden Quadraten. Aus einem Würfel lassen sich 11 Hexominos bilden. Hier ein Link mit den 11 Möglichkeiten:
http://matheplanet.com/default3.html?call=article.php?sid=964&ref=http%3A%2F%2Fwww.google.de%2Fsearch%3Fq%3Dw%25C3%25BCrfel%2Bauffaltung%26sourceid%3Dnavclient-ff%26ie%3DUTF-8%26rls%3DGGGL%2CGGGL%3A2006-45%2CGGGL%3Ade
Es sind keine Überlagerungen von Hexominos erlaubt.

Ich selber kenne die Antwort nicht, glaube aber, dass es nicht möglich ist. Ich bin sehr gespannt, ob jemand von euch etwas anderes herausfindet :-)

Andreas (der momentan kräftig mit Hexominos um sich wirft)

[Heinrich Glumpler]

Hi,

die einzig sichere Aussage, die ich auf Anhieb machen kann - und viel mehr ist mir die Aufgabe zeitmäßig nicht wert ;-):

Wenn es eine Lösung gibt, ist x mindestens gleich 12.



SPOILER (siehe unten meine Argumentation).























Es müssen alle 11 verschiedenen Hexominos vorkommen, d.h. die Fläche muss mindestens 66 Felder haben.
66 ist keine Quadratzahl, also ist diese Fläche nicht gefüllt.
Die nächstgrößere Fläche, die theoretisch gefüllt sein könnte, besteht aus 12x12 Feldern = 144 Feldern. 144 ist die kleinste Felderzahl eines quadratischen Planes, deren Differenz zu 66 durch 6 teilbar ist (66 + 78 = 144).

Alle kleineren Pläne (9x9=81, 10x10=100, 11x11=121) haben Differenzen zu 66, die nicht durch 6 teilbar sind und damit auf keinen Fall mit Hexominos vollständig gefüllt werden können).

Grüße
Heinrich

[Ingo Althöfer]

Hallo Andreas,

Gibt es einen Preis, der für Studenten attraktiv ist?
Falls ja, werde ich das Problem mal als *-Aufgabe in
einer Übserie stellen.

Ingo.

Andreas Last schrieb:
> ... mal ein Rätsel für die Chefmathemathen unter uns.
> Jeder andere darf aber auch mitmachen :-D Und hier kommt das
>
> Existiert ein Raster aus x Spalten und x Zeilen, das unter
> beliebig häufiger Verwendung aller Hexominos, die sich aus
> einem Würfel auffalten lassen vollständig gefüllt werden
> kann? Wenn ja, wie groß müsste es mindestens sein?
>
> Zur Erklärung:
> Hexominos sind zweidimensionale Gebilde aus 6
> zusammenhängenden Quadraten. Aus einem Würfel lassen sich 11
> Hexominos bilden. Hier ein Link mit den 11 Möglichkeiten:
> http://matheplanet.com/default3.html?call=article.php?sid=964&ref=http%3A%2F%2Fwww.google.de%2Fsearch%3Fq%3Dw%25C3%25BCrfel%2Bauffaltung%26sourceid%3Dnavclient-ff%26ie%3DUTF-8%26rls%3DGGGL%2CGGGL%3A2006-45%2CGGGL%3Ade
> Es sind keine Überlagerungen von Hexominos erlaubt.

[Hartmut]

Hallo Andreas,

hättest mal hier mitmachen sollen:
http://opti.logic-masters.de/index.php?page=aufgabe&nr=16

Hartmut (glücklich über den 6. Platz)

[Arne Hoffmann]

Hallo Hartmut,

Glückwunsch zu Deinem 6. Platz und der damit verbundenen besten Plazierung für einen deutschen Teilnehmer!

Waren sehr interessante Rätsel dabei - nur leider bei mir viel zu wenig Zeit abseits so mancher Mittagspause, mich damit beschäftigen zu können.

Schöne Grüße

- Arne -

[raccoon]

...beim Anblick der Bilder werden dunkle Ubongo-Erinnerungen wach... ;)

[Hartmut]

"Arne Hoffmann" hat am 27.03.2007 geschrieben:
> Hallo Hartmut,
>
> Glückwunsch zu Deinem 6. Platz und der damit verbundenen
> besten Plazierung für einen deutschen Teilnehmer!
>
> Waren sehr interessante Rätsel dabei - nur leider bei mir
> viel zu wenig Zeit abseits so mancher Mittagspause, mich
> damit beschäftigen zu können.
>
> Schöne Grüße
>
> - Arne -

Hallo Arne,

danke für die Blumen! Ja, das war schon 'ne recht einladende Angelegenheit. Da ich werktäglich zweimal eine Stunde Fahrzeiten in der Bahn totzuschlagen habe, war schon eine Menge Zeit gegeben, die ich auch sonst nicht so sehr viel sinnvoller hätte nutzen können. Hinzu kamen so manche abendlichen Sessions mit Laptop im Sessel. Die Familie ist froh, dass ich das Ding jetzt wieder einmal öfter beiseite lege :-)

Bei Sichtung der Bestlösungen war das Erstaunen bei mir recht groß, was man noch so alles an Chancen übersehen hat. Die Fülle an Bestlösungen des japanischen Siegers ist sehr eindrucksvoll, er hat sicher nicht viel anderes in den letzten 4 Wochen gemacht ;-)

Alles in allem hat es mich aber auch "gepackt", so dass ich nächstes Jahr wohl wieder mitmachen werde.

Hartmut
- www.hiespielchen.de -

[Christian Hildenbrand]

Von mir auch einen Riesen-Glückwunsch!

Ich hatte mich an ein paar der Rätsel intensiver rangesetzt, aber bin dennoch nie über 80% der Punkte des Besten gekommen. Unglaublich...

Am Schluss fehlte mir schlicht die Zeit wie auch Arne ... aber ich bin vor ihm, das ist auch nicht ganz unerheblich für die gute Laune. :-P

Viele Grüße und bis nächstes Jahr! :-)

Christian

[Martin Windischer]

Es ist leider nicht möglich.
Auf das Ergebnis kommt man, wenn man mit brute force versucht, eine Ecke des Rechtecks aufzufüllen.

LG, Martin

[Ingo Althöfer]

Hallo Martin,

Deine Rechnung muss leider falsch sein.
Schon allein mit dem Hexomino Nr.7 aus der Liste
auf der von Andreas im Ausgangsposting angegebenen
Webseite laesst sich eine Ecke samt beliebig langem
Anschluss lueckenlos fuellen.

Das Teil ist (hoffentlich nicht zu sehr verzerrt):
---xx-----
----xx----
-----xx---

(also eine Art Treppe)

Die 11 Teile duerfen naemlich auch beliebig
gedreht und gespiegelt verwandt werden.

Gruss, Ingo.


Martin Windischer schrieb:
> Es ist leider nicht möglich.
> Auf das Ergebnis kommt man, wenn man mit brute force
> versucht, eine Ecke des Rechtecks aufzufüllen.
>
> LG, Martin

[Martin Windischer]

naja, die Frage ist, wie man die Lücke unter der Treppe füllt, das geht nur entweder mit einer weiteren Treppe oder mit dem Teil

xxx---
---xxx

Bei beiden Teilen entsteht eine weitere Lücke, die man wieder mit einem dieser beiden Teile füllen muss, und da geht man unendlich lang den Rand entlang un kommt nie zu einem Ende.

LG, Martin

[Ingo Althöfer]

Hallo Martin,

Martin Windischer schrieb:
> naja, die Frage ist, wie man die Lücke unter der Treppe
> füllt, das geht nur entweder mit einer weiteren Treppe oder
> mit dem Teil
>
> xxx---
> ---xxx
>
> Bei beiden Teilen entsteht eine weitere Lücke, die man wieder
> mit einem dieser beiden Teile füllen muss, und da geht man
> unendlich lang den Rand entlang un kommt nie zu einem Ende.

Wenn das Dein Argument ist, hattest Du Dich aber im
ursprünglichen Posting falsch ausgedrückt. Es geht
also nicht darum, dass Eckenfüllen zum Widerspruch zu
bringen, sondern das Füllen einer Seite.

Eine Frage dazu: Wieviel Kästchenzeilen einer Seite
des Quadrates brauchst Du für den Widerspruch:
3 oder 4 oder 5 (oder gar nur 2)?

Gespannte Gruesse, Ingo.




> LG, Martin

[Andreas Last]

Moin Heinrich,
schade, dass es dir die Zeit nicht wert ist. Ich wär nämlich für ein neues Spiel von mir an der Antwort interessiert.

Andreas

[Andreas Last]

Moin Ingo,

> Gibt es einen Preis, der für Studenten attraktiv ist?
> Falls ja, werde ich das Problem mal als *-Aufgabe in
> einer Übserie stellen.

mich interessiert das an sich nur wegen Hexamigo :-) Als Hilfe für die Wahl der Spielfeldgröße, Steineanzahl etc.

Andreas

[Andreas Last]

Moin Hartmut,
die Hexominos sind ja leider andere. Für mich ist das halt für einen Prototypen interessant unter den Bedingungen, die ich gestellt habe.

Andreas

[Andreas Last]

Übrigens, jedes Hexomino darf beliebig oft vorkommen, also auch gar nicht.

[Martin Windischer]

> Wenn das Dein Argument ist, hattest Du Dich aber im
> ursprünglichen Posting falsch ausgedrückt. Es geht
> also nicht darum, dass Eckenfüllen zum Widerspruch zu
> bringen, sondern das Füllen einer Seite.

Ja, die Ecke geht schon, die Seite geht auch, aber die Ecke erzwingt auf der Seite Teile, die dann weitere Teile erzwingen, so dass man nie zur nächsten Ecke gelangen kann, sondern unendlich lang auf der Kante weiterwandert.

> Eine Frage dazu: Wieviel Kästchenzeilen einer Seite
> des Quadrates brauchst Du für den Widerspruch:
> 3 oder 4 oder 5 (oder gar nur 2)?

demnach unendlich

[Andreas Last]

Ja, das war auch mein Gedankengang auf dem Weg zur Arbeit. Ich sehe keinen Weg eine Kante komplett zu füllen. Dafür wären Hexominos erforderlich, die nach meinen Vorgaben nicht legal sind.

Interessant wäre jetzt noch (jedenfalls für mich), wie viele der erlaubten Hexominos maximal in ein 15x15, ein 16x16, ein 17x17 und ein 18x18 Feld passen. Wobei mich das erste und das letzte Feld am meisten niteressieren würden :-) 18x18 hab ich bisher übrigens auf 36 leere Felder gebracht.

Andreas

[Ingo Althöfer]

Hallo Martin,

Martin Windischer schrieb:
> ...
> Ja, die Ecke geht schon, die Seite geht auch, aber die Ecke
> erzwingt auf der Seite Teile, die dann weitere Teile
> erzwingen, so dass man nie zur nächsten Ecke gelangen kann,
> sondern unendlich lang auf der Kante weiterwandert.
>
> > Eine Frage dazu: Wieviel Kästchenzeilen einer Seite
> > des Quadrates brauchst Du für den Widerspruch:
> > 3 oder 4 oder 5 (oder gar nur 2)?
>
> demnach unendlich

Du hast nicht richtig verstanden, was ich meine.
Das Quadrat habe n x n Kästchen, mit n sehr gross.
Vom Rand dieses Quadrates kannst Du eine einzelne
Zeile betrachten, also 1 x n Kästchen, oder
zwei Zeielen (= 2 x n Kästchen), usw.
Die Frage war und ist: "Für welches (möglichst kleine)
k musst Du den Rand der Breite k (also k x n Kästchen)
betrachten, damit Du nachweisen kannst, dass diese k x n
(unbeschadet möglicher weiterer Kollisionen) nicht
komplett gefüllt werden kann.

Schlaf am besten vor Deiner nächsten Antwort
mal eine Nacht drüber.

Ingo.

[Ingo Althöfer]

Hallo Andreas,

da muss ich den Mathematiker-Kollegen
Heinrich in Schutz nehmen. Er hat sich einige
Minuten für grundsätzliche Überlegungen genommen
und gemerkt, dass ihm der zündende Funke für eine
Gesamtlösung nicht gekommen ist.

Es ist ja gerade der Witz in der Mathematik, dass man sehr
schwere und auch unlösbare Fragen stellen kann, wobei
die Frage selbst nur 5 Sekunden dauert.

Und auch, wenn Martin (von unten) seine Idee zu einem
wasserdichten Beweis ausführen kann, wird es ihn eine
ganze Menge Zeit gekostet haben. (Dabei erscheint mir
sein Ansatz aber vielversprechend.)

Ingo.

Andreas Last schrieb:
> Moin Heinrich,
> schade, dass es dir die Zeit nicht wert ist. Ich wär nämlich
> für ein neues Spiel von mir an der Antwort interessiert.
>
> Andreas

[Andreas Last]

Moin Ingo,
was heißt in Schutz nehmen? Ich habe Heinrich ja nicht angegriffen. Ich finde einfach nur die Aussage "und viel mehr ist mir die Aufgabe zeitmäßig nicht wert" trotz Smiley etwas schade.

Andreas

[Heinrich Glumpler]

Hi Andreas,

tja - tut mir leid. Aber ich habe keinen Ansatz gesehen, wie ich es beweisen könnte (und welche der beiden Aussagen: ja oder nein).

Und es wäre auch - wie ich jetzt erkannt habe - sinnlose Zeitverschwendung gewesen, denn ich bin davon ausgegangen, dass jedes Teil mindestens ein Mal vorkommen muss.

Das scheint aber nicht der Fall zu sein. Wenn ich einen Beweis gefunden hätte, wäre er eventuell völlig uninteressant gewesen.

Ich hätte mich furchtbar geärgert, wenn ich mehr Zeit aufgewendet hätte und es dir dann gar nichts gebracht hätte.

Noch mal Glück gehabt, würde ich sagen.

Grüße
Heinrich

[Arne Hoffmann]

Ja ja - läster Du nur. ;-)

Wir Hartmut auch, war ich sehr erstaunt darüber, wie gut man so manches Rätsel optimieren konnte. Interessant fand ich auch zu sehen, wie viele Kontrahenten sich z.T. den ersten Platz mit der besten Lösung teilten. Gibt m.E. einen guten Aufschluss über die Komplexität der Rätsel (z.B. bei der Quadratzerlegung). Habe aber auch Hochachtung vor den Teilnehmern auf den ersten Rängen, die z.T. durch fast alle Rätsel hindurch nahe an der optimalen Lösung waren.

Bin letztlich recht zufrieden, dass ich noch Platz 105 erreicht habe - mit nur 6 (oder waren es 7) angegangenen Rätseln, die ich meist nur einmal während der Mittagspause angeschaut hatte. Ganz vorne hätte ich eh nicht landen können, da mir z.B. das Poker- oder auch das Schach-Rätsel überhaupt nicht zusagten und ich mir diese gar nicht weiter angeschaut habe. Und das Cuyo war ja sehr witzig in seiner Art aber für mich zu bunt und zu unübersichtlich. ;-)

Aber der Ehrgeiz wurde geweckt. Im kommenden Jahr, sollte es eine 2. offene deutsche Meisterschaft geben, werde ich mehr Hirnschmalz darein stecken. Und wenn ich schon nicht Hartmut schlagen kann, dann muss ich doch immerhin vor Christian landen. :-P


Schöne Grüße

- Arne - (sieht Christian hoffentlich dieses Jahr noch das ein oder andere mal)

[Christian Fechner]

Hallo,

vielleicht hilft es dir für diese Fragestellung, mal Kontakt mit dem Autor des Polyomino-Solvers unter
http://www.xs4all.nl/~gp/PolyominoSolver/Polyomino.html
aufzunehmen. Bestimmt stellt er dir seinen Quellcode zur Verfügung oder hat bereits eine Anpassung in der Tasche, die die Anzahl der freien Felder miniminert.

Oder du fragst ihn, ob er oder jemand anders sich schon eingehend mit deiner speziellen Untermenge der Hexominos beschäftigt hat.

Gruß
Christian

[Andreas Last]

Moin Christian,
danke für den interessanten Link. Habe da folgende Aussage gefunden:

It is not possible to fit the hexominoes into a perfect rectangle.

Das ist zwar kein Beweis, aber die Seite scheint sich ausreichend mit dem Thema beschäftigt zu haben, um davon auszugehen, dass diese Aussage schon begründet sein wird. Folglich kann auch mit keiner Teilmenge der Hexominos ein perfektes Viereck, geschweige denn ein Quadrat gebildet werden.

Andreas