Elf mal elf Gitterpunkte überdecken

78 views
Skip to first unread message

Rainer Rosenthal

unread,
Oct 2, 2021, 5:59:53 PMOct 2
to
Ein 11 x 11 Quadrats soll mit quadratischen Deckeln überdeckt(*) werden.
Die Deckel sind Quadrate mit Diagonalenlänge 6, die gegenüber dem 11 x
11 Quadrat um 45 Grad gedreht sind.


Frage 1:
Wie viele Deckel werden mindestens benötigt, um alle 121 Gitterpunkte zu
bedecken?

Frage 2:
Wie viele Deckel werden mindestens benötigt, um alle Punkte des 11 x 11
Quadrats zu bedecken?

Gruß,
Rainer Rosenthal
r.ros...@web.de

(*) Auch die Punkte unter dem Deckelrand gelten als bedeckt.

Martin Vaeth

unread,
Oct 3, 2021, 1:04:29 AMOct 3
to
Rainer Rosenthal <r.ros...@web.de> wrote:
> Ein 11 x 11 Quadrats soll mit quadratischen Deckeln überdeckt(*) werden.
> Die Deckel sind Quadrate mit Diagonalenlänge 6, die gegenüber dem 11 x
> 11 Quadrat um 45 Grad gedreht sind.

Nehman wir mal ein viel größeres QUadrat als 11 x 11.

Offensichtlich ist es doch so, dass man die kleinen Quadrate zunächst
mal in einer Reihe (um 45 Grad gedreht) aneinenandersetzen kann.
Danach setzt man mehrere solche Reihen nebeneinander.
Wie das Nebeneinandersetzen der Reihen und das Überdecken des gegebenen
QUadrats mit dem großen Objekt genau passiert, hängt dann vom "Rand"
das gegebenen Quadrats ab.

Ich behaupte nicht, dass das zur optimalen Lösung bei 11 x 11 führt,
denn die kann wegen des Randes suboptimal sein - vielleicht kann man
ein Quadrat aus einer anderen Reihe etwas verschieben um eines zu sparen.

Aber wie wäre es, diese Idee auf das ursprüngliche Problem auf dem
Hyperwürfel mit Hamming-Abstand anzuwenden?

Das führt auf folgenden Greedy-ähnlichen Algorithmus:

1.Das erste 11-Tupel wird beliebig gewählt - aus Symmetriegründen
ist dies o.B.d.A.

2. Sind n 11-Tupel bereits gewählt, wähle das (n+1)-te Tupel durch
"direktes Anlegen":

a. Lege um die n 11-Tupel Hamming-Kugeln mit Radius 3;
nenne die Vereinigung dieser Kugeln G_n (zur effektiven Berechnung
markiere diese Menge jeweils in einem 2048 Array).

b. Bestimme nun die Menge M_{n,0} aller 11-Tupel mit der Eigenschaft,
dass die Hamming-Kugel mit Radius 3 um diese Tupel disjunkt ist zu G_n;
falls M_{n,0} bereits leer ist, berechne sukzessive allgemeiner die
Mengen M_{n,k}, bei denen die Überschneidung nur aus k Punkten besteht.
Sei M_n = M_{n,k} mit minimalem k.
M_n besteht also informell aus denjenigen Hammingkugeln, die möglichst
nicht schon von den vorherigen Kugeln abgedeckt sind.

c. Betrachte aus M_n nun die Teilmenge T_n derjenigen Punkte, bei denen
die Hammingkugel mit Radius 4 einen möglichst *großen* Schnitt mit G_n hat.
Informell sind dies diejenigen Kugeln, die
"an die vorherigen Kugeln anliegen".

d. Um die Menge T_n weiter zu verkleinern, betrachte die Teilmenge S_n
derjenigen Punkte, deren Hammingkugel mit Radius 5 einen möglichst
großen Schnitt mit G_n hat. Informell sind das diejenigen Kugeln, die
mit den vorherigen Kugeln zusammen möglichst dichtgedrängte Cluster
bilden.

e. Man kann noch weiter verkleinern, indem man die Menge U_n
derjenigen Punkte aus S_n betrachtet, deren Hammingkugel mit Radius 6
einen möglichst großen Schnitt mit G_n hat, die also gewissermaßen
"Mega-Cluster" bilden. Weiter als 6 zu gehen, hat wohl keinen Sinn,
weil 6 gerade der Doppelte Hammingabstand ist, der uns interessiert -
größere "Clusterisierung" bringt für unser Problem nichts.

Welches Element aus der Menge U_n das richtige ist, ist jetzt natürlich
immer noch nicht kanonisch. Man kann zufällig wählen.
Vielleicht ist diese Menge aber jetzt so klein, dass man hiermit einen
Backtracking-Algorithmus zur Bestimmung der optimalen Wahl machen kann.

Zwar habe ich keinen formalen Beweis, dass dies eine optimale Lösung
liefert, aber die geometrische Intuition spricht dafür, dass der
Backtracking-Algorithmus (falls er bereits machbar ist), eine optimale
Lösung liefern sollte.

Falls jemand Zeit und Muße hat, den Algorithmus zu probieren, würde
mich das sehr freuen. Ich komme im Moment nicht dazu.

Martin Vaeth

unread,
Oct 3, 2021, 3:27:02 AMOct 3
to
Martin Vaeth <mar...@mvath.de> schrieb:
>
> Aber wie wäre es, diese Idee auf das ursprüngliche Problem auf dem
> Hyperwürfel mit Hamming-Abstand anzuwenden?
>
> Das führt auf folgenden Greedy-ähnlichen Algorithmus:
>
> 1.Das erste 11-Tupel wird beliebig gewählt - aus Symmetriegründen
> ist dies o.B.d.A.
>
> 2. Sind n 11-Tupel bereits gewählt, wähle das (n+1)-te Tupel durch
> "direktes Anlegen":
>
> a. Lege um die n 11-Tupel Hamming-Kugeln mit Radius 3;
> nenne die Vereinigung dieser Kugeln G_n (zur effektiven Berechnung
> markiere diese Menge jeweils in einem 2048 Array).
>
> b. Bestimme nun die Menge M_{n,0} aller 11-Tupel mit der Eigenschaft,
> dass die Hamming-Kugel mit Radius 3 um diese Tupel disjunkt ist zu G_n;
> falls M_{n,0} bereits leer ist, berechne sukzessive allgemeiner die
> Mengen M_{n,k}, bei denen die Überschneidung nur aus k Punkten besteht.
> Sei M_n = M_{n,k} mit minimalem k.
> M_n besteht also informell aus denjenigen Hammingkugeln, die möglichst
> nicht schon von den vorherigen Kugeln abgedeckt sind.

Ich habe jetzt doch etwas Zeit gefunden, und Backtracking nur mit M_n
versucht - bei den zusätzlichen Verkleinerungen bin ich weitaus weniger
sicher, dass man eine optimale Lösung erhält.

Das wird zwar wohl mehrere Stunden/Tage Tage rechnen, aber er hat schon
mehrere Lösungen mit 11 Antworten gefunden.

Bitte verifizert es mal mit Euren Tools, da ich den Algorithmus nur sehr
schnell hingeschmiert habe; er könnte durchaus buggy sein:

[00000000000, 11001100001, 01011010101, 00111100110, 11110000111,
11111111000, 00110011001, 01010101010, 10100101101, 11000011110,
00001111111]

[00000000000, 11001100001, 01100110101, 00111100110, 11110000111,
11111111000, 00110011001, 01010101010, 10011001101, 11000011110,
00001111111]

[00000000000, 11001100001, 10010110101, 00111100110, 11110000111,
11111111000, 00110011001, 01010101010, 01101001101, 11000011110,
00001111111]

[00000000000, 11001100001, 01101010011, 10010110101, 00111100110,
11110000111, 11111111000, 00110011001, 01010101010, 11000011110,
00001111111]

[00000000000, 11001100001, 01101010100, 10010110101, 00111100110,
11110000111, 11111111000, 00110011001, 01010101010, 11000011110,
00001111111]

Die kamen sehr schnell zusammen mit ein zwar 12-ern, seitdem kam
nichts mehr unter 13.
Da hier so viele übereinstimmen, wage ich schon jetzt die Voraussage,
dass mein Algorithmus auch nach in paar Tagen keine bessere Lösung
mehr finden wird.

Martin Vaeth

unread,
Oct 3, 2021, 3:57:21 AMOct 3
to
Martin Vaeth <mar...@mvath.de> wrote:
>
> Das wird zwar wohl mehrere Stunden/Tage Tage rechnen, aber er hat schon
> mehrere Lösungen mit 11 Antworten gefunden.
>
> Da hier so viele übereinstimmen, wage ich schon jetzt die Voraussage,
> dass mein Algorithmus auch nach in paar Tagen keine bessere Lösung
> mehr finden wird.

Ähm, nein: Ich hatte übersehen, dass die Lösungen sortiert sind,
und damit die Verschiedenheit des 3. Elements nicht schon bedeutet,
dass "nur" noch i.W. 1 Rekursionslevel fehlt.
Nachdem ich jetzt die Ausgabe verbessert habe, ist klar:
Der Algorithmus wird nicht in absehbarer Zeit enden, und meine
Voraussage war Blödsinn.
Ich lasse diesen Algorithmus nicht mehr weiter laufen.

Rainer Rosenthal

unread,
Oct 3, 2021, 5:04:26 AMOct 3
to
Am 03.10.2021 um 07:04 schrieb Martin Vaeth:
>
> Zwar habe ich keinen formalen Beweis, dass dies eine optimale Lösung
> liefert, aber die geometrische Intuition spricht dafür, dass der
> Backtracking-Algorithmus (falls er bereits machbar ist), eine optimale
> Lösung liefern sollte.
>
Danke fürs Mitspielen!
Die geometrische Intuition ist das Feuer, aber man braucht feste Töpfe,
um was zu kochen :-)

Ich freue mich aber wirklich sehr, dass die Fragestellung zum Mitknobeln
anregt. Für meine Intuition habe ich auch schon was aus dem Beispiel
gewonnen, das als Bild an anderer Stelle zu finden ist. Den direkten
Verweis schreibe ich hier nicht (spoiler, s. 03.10.2021, 00:14 Uhr).

Mir scheint ein Schlüssel zum Erfolg auf der Suche nach der minimalen
Deckel-Anzahl, dass erst einmal die Ecken(*) abgedeckt werden.
Jedenfalls konnte ich auf diese Weise mit Papier, Bleistift und
Karo-Papier fündig werden. Die exakte Zeichnung per Computer und mit
farbigen Deckeln habe ich nur aus Jux und Dollerei gemacht, um sozusagen
"den Deckel drauf zu machen" auf die Abschweifung vom Hauptthema: ob die
16 11-dimensionalen Deckel von Uwe Weiss schon die minimale Anzahl
haben, oder ob man auch mit 15 Erfolg hat.

Aber wie das so ist: als mir diese "Einkerbungen" am Rand des 11 x 11
Quadrats auffielen, merkte ich, dass man die gar nicht schließen kann,
wenn man die Deckel nur schiebt und nicht dreht.

Gruß und schönen Sonntag,
Rainer

(*) allgemeiner: irgendwelche voneinander weit entfernte Punkte, die man
ja doch irgendwann bedecken muss. Fängt man mit ihnen an, dann stochert
man nicht mehr ganz so im Nebel.
Bei den 2^11 Binärmustern bieten sich da die zueinader 0-1-inversen
Muster an wie z.B. 00000000000 und 11111111111 und andere solcher
Pärchen wie z.B. 00011000010 und 11100111101.

@Uwe Weiss: hast Du noch was am Laufen bzgl. dieses Themas?
Dein "Rauskegeln"-Ansatz könnte mit der "Ecken"-Idee vielleicht
verstärkt werden? Ziemlich zu Beginn haben Mitdiskutierende bereits
geschrieben, dass maximal voneinander entfernte Punkte wichtig sind. Ich
behaupte also nicht, dass die Idee von mir ist, aber das bereits
Gelesene zusammen mit dem Bild hat mich weiter gebracht.


Martin Vaeth

unread,
Oct 3, 2021, 5:10:13 AMOct 3
to
Martin Vaeth <mar...@mvath.de> schrieb:
>
> Bitte verifizert es mal mit Euren Tools

Passt nicht: Der Algorithmus enthält einen Bug. Keine Zeit mehr, weiterzusuchen.

Martin Vaeth

unread,
Oct 3, 2021, 5:22:56 AMOct 3
to
Rainer Rosenthal <r.ros...@web.de> schrieb:
>
> Mir scheint ein Schlüssel zum Erfolg auf der Suche nach der minimalen
> Deckel-Anzahl, dass erst einmal die Ecken(*) abgedeckt werden.
>
> (*) allgemeiner: irgendwelche voneinander weit entfernte Punkte, die man
> ja doch irgendwann bedecken muss. Fängt man mit ihnen an, dann stochert
> man nicht mehr ganz so im Nebel.

Ich halte es für eine schlechte Idee, dort die *Zentren* der
Kugeln zu platzieren. In der Ebene ist das offensichtlich eine sehr
schlechte Idee, weil dann viele Punkte über den Rand verloren gehen.
(In der Ebene sind Kugeln eben nicht immer gleich groß).

Aber auch beim Hyperwürfel - der ja keinen Rand hat - heißt das nicht
unbedingt, dass das eine gute Wahl ist: Der Rest des Gebietes ist jetzt
u.U. schon zu verkorkst, als dass man da problemlos die Lücken füllen
könnte.

Den Algorithmus mit dem "Nebeneinanderlegen" der Kugeln halte ich
für vielversprechender:

> Bei den 2^11 Binärmustern bieten sich da die zueinader 0-1-inversen
> Muster an wie z.B. 00000000000 und 11111111111

Wie andernorts geschrieben: Mit 00000000000 kann man o.B.d.A. beginnen.
Aber ob sich die Wahl 11111111111 dann zu einer optimalen Lösung
ergänzen lässt, ist schon fraglich. Irgendetwas, das viel "näher"
an der 0 liegt und dennoch die 11111111111 enthält, scheint für das
Abdecken dieser Ecke besser geeignet zu sein. Aber das ist natürlich
alles nur wilde Spekulation.

Rainer Rosenthal

unread,
Oct 3, 2021, 5:46:04 AMOct 3
to
Am 03.10.2021 um 11:22 schrieb Martin Vaeth:
> Rainer Rosenthal <r.ros...@web.de> schrieb:
>>
>> Mir scheint ein Schlüssel zum Erfolg auf der Suche nach der minimalen
>> Deckel-Anzahl, dass erst einmal die Ecken(*) abgedeckt werden.
>>
> Ich halte es für eine schlechte Idee, dort die *Zentren* der
> Kugeln zu platzieren.

Das halte ich auch für eine schlechte Idee.
Davon hatte ich aber auch nichts gesagt, sondern ich sagte, dass die
Ecken "abgedeckt" werden müssen. Es muss in der Nähe jeder Ecke
wenigstens ein Kugelzentrum sein.

Im Übrigen hat der Raum der 2^11 Binärcodes gar keine "Ecken", auch wenn
man alle Punkte als Ecken eines 11-dimensionalen Hyperwürfels betrachten
kann. Wir wissen ja, dass jede Lösung nur eindeutig ist bis auf
Isomorphie: beliebige Platztauschungen (Vertauschung der Koordinaten)
oder Vertauschungen von 0 und 1 in einer Koordinate bringen nichts Neues
und die Überdeckungseigenschaft bleibt erhalten.

So gesehen muss ich vielleicht doch noch mal genauer hinschauen und das
eckigen 11 x 11 Quadrats zu einem Torus zusammenbiegen.

Schade, dass Du keine Zeit mehr hast. Aber vielleicht in drei Wochen wieder?
Dann ist evtl. auch noch alles offen :-)

Gruß,
Rainer

Martin Vaeth

unread,
Oct 3, 2021, 6:13:16 AMOct 3
to
Martin Vaeth <mar...@mvath.de> wrote:
> Martin Vaeth <mar...@mvath.de> schrieb:
>>
>> Bitte verifizert es mal mit Euren Tools
>
> Passt nicht: Der Algorithmus enthält einen Bug.

Jetzt sollte es passen. Der Algorithmus hat bislang 2145 Lösungen der
Länge 16 gefunden; die erste davon ist:

[00000000000, 00001111111, 11110000111, 11111111000,
00110011001, 00111100110, 11000011110, 11001100001,
01010101010, 01011010101, 10100101101, 10101010010,
01100110011, 01101001100, 10010110100, 10011001011]

Ich breche den Algorithmus aber nach ein paar Minuten ab, weil ein Ende
nicht abzusehen ist. Wenn ich mal wieder Zeit habe, implementiere ich
den ganzen Algorithmus mit der Vorfilterung - das sollte die Laufzeit
merklich drücken.

Martin Vaeth

unread,
Oct 3, 2021, 6:17:01 AMOct 3
to
Rainer Rosenthal <r.ros...@web.de> schrieb:
>
> Das halte ich auch für eine schlechte Idee.
> Davon hatte ich aber auch nichts gesagt, sondern ich sagte, dass die
> Ecken "abgedeckt" werden müssen. Es muss in der Nähe jeder Ecke
> wenigstens ein Kugelzentrum sein.

Ja, aber Dein Vorschlag mit 00000000000 und 1111111111 zu beginnen,
legt dort die Zentren hin. Und diesen Vorschlag halt ich genau
deswegen nicht für zielführend.

> Im Übrigen hat der Raum der 2^11 Binärcodes gar keine "Ecken"

In dem Sinne von am weitesten entfernten Punkten schon; nicht in
dem Sinne, dass die Kugeln mit den Zentren dort "kleiner" wären.

Carlo XYZ

unread,
Oct 3, 2021, 7:17:20 AMOct 3
to
Martin Vaeth schrieb am 03.10.21 um 12:16:
Um in dem Kontext meinen Vorschlag (besser gesagt: wild guess)
klarzustellen: aus einem bislang erzeugten "Rand" neue Vektoren
durch Ändern von d(=3) Stellen maximal entfernte neue als neue
Zentren zu finden. In meinem kleinen Beispiel war L=5 und d=2.

Rainer Rosenthal

unread,
Oct 3, 2021, 8:39:16 AMOct 3
to
Am 03.10.2021 um 12:16 schrieb Martin Vaeth:
> Rainer Rosenthal <r.ros...@web.de> schrieb:
>>
>> Es muss in der Nähe jeder Ecke wenigstens ein Kugelzentrum sein.
>
> Ja, aber Dein Vorschlag mit 00000000000 und 1111111111 zu beginnen,
> legt dort die Zentren hin.
>
Nein, ich hatte sie beschrieben als "irgendwelche voneinander weit
entfernte Punkte, die man ja doch irgendwann bedecken muss".
Das ist was anderes, als dass sie Zentren sein sollen.

Es ist ja auch genau das, was das Bild (bei "Mathematisches") auf meiner
Homepage www.rwro.de zeigt: die Ecken werden von Manhattan-Kugeln mit
Radius 3 bedeckt, deren Zentren Manhatten-Distanz 2 zur Ecke haben.

Ich werde mir wahrscheinlich wirklich noch anschauen, was geschieht,
wenn ich die Ecken des 11 x 11 Quadrats dadurch verschwinden lasse, dass
ich es auf einen Torus wickle.

Es ist ein Missverständnis, 00000000000 und 1111111111 als Ecken zu
verstehen. Diese beiden Muster zeichnet nichts aus, als dass sie
diametral zueinander sind. Das sind aber 00100100100 und 1101101101
ebenfalls. Der Lösungsraum ist hoch-symmetrisch, es wimmelt von Isomorphen.

Gruß,
Rainer


Martin Vaeth

unread,
Oct 4, 2021, 1:32:54 AMOct 4
to
Martin Vaeth <mar...@mvath.de> schrieb:
> Wenn ich mal wieder Zeit habe, implementiere ich
> den ganzen Algorithmus mit der Vorfilterung - das sollte die Laufzeit
> merklich drücken.

Jetzt habe ich die paar Zeilen heute morgen doch noch geschrieben.
Aber das Ergebnis ist enttäuschend.

Ob man zur "Berührung" nur diejenigen mit maximalem Hamming-Abstand 4
zulässt oder daraus noch diejeniggen mit maximalem Hamming-Abstand 5
filtert, scheint praktisch keinen Unterschied zu machen.

Außerdem scheint man auch nicht so viel auszuschließen:
Statt 10^13 Tage braucht man dann "nur" noch 10^11 Tage Rechenzeit.

(Für die Abschätzung nehme ich jeweils an, dass die ersten 9 Wahlen
repräsentativ sind.)

Es scheint einfach so zu sein, dass zufälligerweise eine niedrig
hängende Frucht von 16ern bei dieser Art von Suche zu finden ist.

Danach kommt dann anscheinend nichts mehr innerhalbe der ersten Stunden
(ich hatte gestern Nacht noch laufen lassen): Letzteres ist nicht
überraschend; man müsste halt die ersten 9 Wahlen verändern, und bis der
Backtracking-Algorithmus dahin kommt, dauert es halt ca. einen Tag.

Die Frucht ist genauer gesagt 1009 Einträge groß.
(Bei meinem letzten Posting gab es noch einen Typo im Algorithmus,
der bewirkte, dass Lösungsduplikate gesucht wurden.)

Martin Vaeth

unread,
Oct 4, 2021, 1:52:21 AMOct 4
to
Martin Vaeth <mar...@mvath.de> schrieb:
> Martin Vaeth <mar...@mvath.de> schrieb:
>> Wenn ich mal wieder Zeit habe, implementiere ich
>> den ganzen Algorithmus mit der Vorfilterung - das sollte die Laufzeit
>> merklich drücken.
>
> Jetzt habe ich die paar Zeilen heute morgen doch noch geschrieben.
> Aber das Ergebnis ist enttäuschend.
>
> Ob man zur "Berührung" nur diejenigen mit maximalem Hamming-Abstand 4
> zulässt oder daraus noch diejeniggen mit maximalem Hamming-Abstand 5
> filtert, scheint praktisch keinen Unterschied zu machen.
>
> Außerdem scheint man auch nicht so viel auszuschließen

Korrektur: Mit Hamming-Abstand 5 bin ich schon nach wenigen Minuten auf
weitere "Früchte" von 16ern gestoßen, und das Backtracking probiert
schon die 10te (von 64) Wahl von 8er-Anfängen. Die Zahl der 16er-Lösungen
liegt im Moment bei 3346 und steigt schnell weiter.
(Der Trick ist, die Berührungsheuristik nach Level 9 auszuschalten,
weil sie dann mehr Zeit kostet als nützt.)

Die Heuristik bringt also doch merklich etwas und findet anscheinend
gerade bei den ersten Wahlen bessere Möglichkeiten. Was natürlich auch
Zufall sein kann.

In jedem Fall ist es utopisch, mit diesem Backtracking den gesamten
Raum zu durchsuchen.

Vielleicht ist es realistisch, wenn man zusätzlich die "offensichtlichen"
Symmetrien in der Suche ausblenden könnte, aber das wäre ziemlich aufwändig
zu implementieren und vermutlich speichermäßig irgendwann nicht mehr
machbar.

Michael Koch

unread,
Oct 5, 2021, 4:59:21 PM (13 days ago) Oct 5
to
> Frage 1:
> Wie viele Deckel werden mindestens benötigt, um alle 121 Gitterpunkte zu
> bedecken?

7 Deckel

> Frage 2:
> Wie viele Deckel werden mindestens benötigt, um alle Punkte des 11 x 11
> Quadrats zu bedecken?

12 Deckel. Allerdings geht aus der Fragestellung nicht klar hervor, ob man die Deckel auch verdrehen darf. Falls ja, dann bräuchte man nur 9 Deckel.

Gruß
Michael

Rainer Rosenthal

unread,
Oct 6, 2021, 7:45:36 AM (13 days ago) Oct 6
to
Am 05.10.2021 um 22:59 schrieb Michael Koch:
>> Frage 1:
>> Wie viele Deckel werden mindestens benötigt, um alle 121 Gitterpunkte zu
>> bedecken?
>
> 7 Deckel

Wie soll das gehen?
Mein Bild auf http://www.rwro.de/ benötigt 8 Deckel.
Wenn die Ecken des 11 x 11 Quadrats die Koordinaten [0,0], [10,0],
[10,10], [0,10] haben, dann sind die Zentren der Deckel:
Vier nahe den Ecken: [1,1], [9,1], [9,9], [1,9] und vier
nahe den Seitenmitten: [2,5], [5,2], [8,5], [5,8].

Wo sind die Zentren Deiner 7 Deckel?
Ich kann mir nicht vorstellen, wie das mit 7 Deckeln klappen soll.

>
>> Frage 2:
>> Wie viele Deckel werden mindestens benötigt, um alle Punkte des 11 x 11
>> Quadrats zu bedecken?
>
> 12 Deckel. Allerdings geht aus der Fragestellung nicht klar hervor, ob man die Deckel auch verdrehen darf. Falls ja, dann bräuchte man nur 9 Deckel.
>
In der Fragestellung steht:
Die Deckel sind Quadrate mit Diagonalenlänge 6, die gegenüber dem 11 x
11 Quadrat um 45 Grad gedreht sind.

Also: weitere Verdrehungen sind nicht erlaubt.
Die 12 Deckel glaube ich sofort, denn wenn Du zu den 8 Deckeln aus
meinem genannten Bild noch 4 dazu nimmst, mit denen die "Einkerbungen am
Rand" zugedeckt werden, dann ist das gesamte Quadrat überdeckt.

Gruß,
Rainer


Michael Koch

unread,
Oct 6, 2021, 8:17:02 AM (13 days ago) Oct 6
to
Rainer Rosenthal schrieb am Mittwoch, 6. Oktober 2021 um 13:45:36 UTC+2:
> Am 05.10.2021 um 22:59 schrieb Michael Koch:
> >> Frage 1:
> >> Wie viele Deckel werden mindestens benötigt, um alle 121 Gitterpunkte zu
> >> bedecken?
> >
> > 7 Deckel
> Wie soll das gehen?

https://bilderupload.org/bild/28a522518-7-deckel

Gruß
Michael

Rainer Rosenthal

unread,
Oct 6, 2021, 10:40:36 AM (12 days ago) Oct 6
to
Oh ja, sehr richtig!
100 Punkte für Dich.

Ich hatte etwas vergessen, was zu der Ursprungsfrage dazu gehören sollte:
Die gedrehten Quadrate repräsentieren "Kugeln" um einen Gitterpunkt mit
Radius 3, wobei der Abstand zweier Punkte die Summe der Absolutbeträge
der Differenzen ist (Manhattan-Metrik).
Bspl: Abstand zwischen [2,3] und [1,5] ist |2-1| + |3-5| = 1 + 2 = 3.

Ich schreibe die korrigieret Aufgabenstellung neu.

Gruß und Dank,
Rainer

Rainer Rosenthal

unread,
Oct 6, 2021, 10:47:41 AM (12 days ago) Oct 6
to
Ein 11 x 11 Quadrats soll mit quadratischen Deckeln überdeckt(*) werden.
Die Deckel sind Quadrate mit Diagonalenlänge 6, die gegenüber dem 11 x
11 Quadrat um 45 Grad gedreht sind.
Die Deckel-Zentren sind Gitterpunkte. <========= NEU!

Rainer Rosenthal

unread,
Oct 6, 2021, 6:41:57 PM (12 days ago) Oct 6
to
Ich habe die Antworten hier bebildert: www.rwro.de

Frage 1 wird dort so beantwortet:
8 Bierdeckel bedecken 121 Punkte auf der Tischdecke.

Frage 2 wird anschließend beantwortet:
... und 10 bedecken den ganzen Tisch.

Gruß,
Rainer Rosenthal
r.ros...@web.de

Rainer Rosenthal

unread,
Oct 6, 2021, 6:44:06 PM (12 days ago) Oct 6
to
Am 05.10.2021 um 22:59 schrieb Michael Koch:
>> Frage 2:
>> Wie viele Deckel werden mindestens benötigt, um alle Punkte des 11 x 11
>> Quadrats zu bedecken?
>
> 12 Deckel. Allerdings geht aus der Fragestellung nicht klar hervor, ob man die Deckel auch verdrehen darf. Falls ja, dann bräuchte man nur 9 Deckel.
>
Ohne Verdrehen: 10 Deckel sind ausreichend. Siehe www.rwro.de

Gruß und danke fürs Miträtseln,
Rainer R.


Rainer Rosenthal

unread,
Oct 6, 2021, 7:05:25 PM (12 days ago) Oct 6
to
Hmm, eigentlich gehören die 7 Deckel von Michael Koch auch in die
Mini-Galerie.

Aber: ach was, ich warte einfach ab, bis wütende Mails eintreffen, dass
man die 121 Punkte der Tischdecke schon mit 7 Bierdeckeln dieser Art
zudecken kann. Dann schreibe ich zurück, dass Michael Koch einen
eventuellen Prioritätsstreit gewinnen würde, so wahr ich Rainer
Rosenthal heiße.

Gruß,
RR

Michael Koch

unread,
Oct 7, 2021, 3:52:54 AM (12 days ago) Oct 7
to
Rainer Rosenthal schrieb am Donnerstag, 7. Oktober 2021 um 00:44:06 UTC+2:
> Am 05.10.2021 um 22:59 schrieb Michael Koch:
> >> Frage 2:
> >> Wie viele Deckel werden mindestens benötigt, um alle Punkte des 11 x 11
> >> Quadrats zu bedecken?
> >
> > 12 Deckel. Allerdings geht aus der Fragestellung nicht klar hervor, ob man die Deckel auch verdrehen darf. Falls ja, dann bräuchte man nur 9 Deckel.
> >
> Ohne Verdrehen: 10 Deckel sind ausreichend. Siehe www.rwro.de

Das würde ich jetzt aber als 10x10 Quadrat bezeichnen. Wenn ich "11x11 Quadrat" lese, dann gehe ich davon aus dass die Kantenlänge gemeint ist und nicht die Anzahle der Rasterpunkte.

Gruß
Michael

Rainer Rosenthal

unread,
Oct 7, 2021, 4:07:09 AM (12 days ago) Oct 7
to
*seufz*

Wo Du Recht hast, hast Du Recht.
Muss mir was überlegen.

Dank und Gruß,
Rainer

Andreas Leitgeb

unread,
Oct 7, 2021, 6:47:11 AM (12 days ago) Oct 7
to
Nicht verdrießen... Im Betreff stands ja von Anfang an so:
"Elf mal elf Gitterpunkte ..."
und nicht etwa: "Ein Quadrat von Elf Seitenlänge..."

War also alles ok.

Rainer Rosenthal

unread,
Oct 7, 2021, 5:55:35 PM (11 days ago) Oct 7
to
Schönen Dank für die Trostworte.
Die Formulierung auf meiner Homepage www.rwro.de ist OK.
Zu Bild 1 heißt es:
"8 Bierdeckel bedecken 121 Punkte auf der Tischdecke."
Und der "Tisch" ist zart eingezeichnet als kleinstes Quadrat um die 11 x
11 = 121 Gitterpunkte.

Zu Bild 2 heißt es:
"... und 10 bedecken den ganzen Tisch."
Da benenne ich die Größe nicht, sondern man sieht, was mit "Tisch"
gemeint ist.

Zur Abrundung gehört natürlich noch irgendwo das Bild mit den 7 Deckeln
von Michael Koch hin. Vielleicht mache ich das noch.

Gruß,
Rainer




Reply all
Reply to author
Forward
0 new messages