+211 Ich habe mir gedacht, nach all den inaktiven Jahren könnte ich nochmal vorbei schauen und erneut den ein oder anderen Denker unter den Anwesenden auf die Probe stellen.
Um meinem alten Stil treu zu bleiben, eröffne ich meine Rückkehr mit einem netten Problem am Quadratraster:
Gegeben ist ein 10x10 Quadrat, von dem 9 Felder zu Beginn "infiziert" sind.
In jedem Schritt wird nun jedes Feld, das an mindestens 2 infizierte Felder direkt horizontal oder vertikal angrenzt, ebenfalls infiziert.
Beweise: Unabhängig von der Position der infizierten Felder zu Beginn ist nie nach endlich vielen Schritten jedes Feld infiziert.
Einfach zu lösen, schwierig zu erklären...
Damit alle Reihen ausgefüllt werden können bräuchte man 10 infizierte Felder, ansonsten bleibt immer mindestens eine Reihe über
In Ermangelung richtiger Lösungen bisher hier ein Hinweis:
Betrachtet mal den Umfang des infizierten Gebiets!
+3976 DIe Aufgabe ist tatsächlich knifflig!
Klar ist schonmal, dass die Aussage mit 10 zu Beginn infizierten Feldern nicht stimmen würde - man betrachte beispielsweise die Startsituation mit den 10 infizierten Feldern auf der Diagonale.
Theoretisch könnte man hier natürlich mit roher Gewalt vorgehen und beispielsweise in Python ein Programm schreiben, welches einfach alle Lösungen durchprobiert und testet, ob am Ende irgendwo eine vollständig infizierte Matrix rauskommt. Ist nicht der Plan, das ist klar, würde aber gehen.
Ich denk' später gern nochmal drüber nach, möcht aber vorab schonmal eine Frage zu der Aufgabe stellen: Gilt das allgemein, also für ein NxN-Quadrat mit N-1 infizierten Feldern? Intuitiv würde ich sagen "ja", aber das beweist ja noch lange nichts.
Schöne Aufgabe auf jeden Fall, danke dafür!
+211 Hallo Probolobo,
schön, dass du dich an der Aufgabe versuchst!
Ja, sie verallgemeinert auf N-1 Felder in einem NxN-Feld, und auch das Diagonalenargument funktioniert da :-)
+3976 Also ich seh', auf was es rausläuft, bin aber noch nicht sicher, wie ich's in voller Allgemeinheit zu Papier bekomm.
Die "Chance", dass das Infizieren des kompletten Quadrates klappt, sinkt, wenn schon zu Beginn benachbarte Felder infiziert sind.
Es werden nur Felder infiziert, die neben zwei diagonal angeordneten infizierten Felder sind, also etwa so:
X O X X
O X --> X X
So entstehen nach&nach Rechtecke, die bei einem ein Kästchen breiten Zwischenraum auch noch verbunden werden.
Betrachtet man den Umfang der infizierten Fläche (danke für den Hinweis ;) ), so ist zu erkennen, dass der mit jedem "Infektions-Schritt" bestenfalls kleiner wird. Bei der Entstehung der Rechtecke verändert er sich gar nicht, wenn sich zwei infizierte Flächen zusammenschließen oder "Löcher" in den infizierten Flächen gefüllt werden kann er kleiner werden.
Der Umfang ist am Anfang maximal 4*9=36 groß (nämlich dann, wenn alle Felder "einzeln" im Quadrat liegen, also keine benachbart sind), das Quadrat hat aber gesamt den Flächenumfang 4*10=40. Da 40>36 kann nie das gesamte Quadrat infiziert sein.
-> So ungefähr stelle ich mir die Lösung vor. Ist an einigen Stellen noch etwas knapp, das seh' ich wohl ein, aber die Kernaussage müsste passen. Wie nah dran bin ich? ;)
