Water Problem Wasser Problem

The water problem goes as follows: given an n*n grid, you're allowed to place water in as many cells as you want. In each timestep, every cell that has two neighbouring (direct neighbour: top, bottom, right, left) water cells or more will get filled with water also. What's the ideal placement of water such that the timestep after which nothing changes is as large as possible? Das Wasserproblem lautet wie folgt: Gegeben ist ein n×n-Gitter, in dem du beliebig viele Zellen mit Wasser füllen darfst. In jedem Zeitschritt wird jede Zelle, die mindestens zwei benachbarte (direkte Nachbarn: oben, unten, rechts, links) Wasserzellen hat, ebenfalls mit Wasser gefüllt. Wie muss man das Wasser ideal platzieren, sodass die Anzahl der Zeitschritte, nach denen sich nichts mehr verändert, so groß wie möglich ist?

Below is a simulation of this, you can click cells to place intial water (1), it will then fill the rest of the grid out with the timestep-indeces if you click "simulate". Unten ist eine Simulation dieses Problems. Du kannst auf Zellen klicken, um anfängliches Wasser (1) zu platzieren. Anschließend wird der Rest des Gitters mit den Zeitschritt-Indizes ausgefüllt, wenn du "Simulieren" clickst.

For an n*n grid, we define f(n) to be the maximum number in the grid after simulation. Using computer simulations, we figured out that f(1)=1 (trivial case), f(2)=2 (also easy), f(3)=5 (simple), f(4)=10 (hard!), and f(5)=16 (harder!). For 8*8, the maximum we found is 41 (see "optimal solution?" button). Hence, f(8) >= 41. For large enough n, we managed to show that 13/18 · n² - 2n ≤ f(n) ≤ n² - n. Für ein n×n-Gitter definieren wir f(n) als die größte Zahl im Gitter nach der Simulation. Mithilfe von Computersimulationen haben wir herausgefunden, dass f(1) = 1 (trivialer Fall), f(2) = 2 (ebenfalls einfach), f(3) = 5 (simpel), f(4) = 10 (schon schwieriger!) und f(5) = 16 (noch schwieriger!) ist. Für ein 8×8-Gitter haben wir ein Maximum von 41 gefunden (siehe "Optimale Lösung?"-button). Daher gilt: f(8) ≥ 41. Für ausreichend großes n konnten wir zeigen, dass gilt:
13/18 · n² - 2n ≤ f(n) ≤ n² - n.

Have any ideas? Try them out and come to the next weekly recreational math meeting! Hast du Ideen zum Problem? Probiere sie aus und komm zum nächsten wöchentlichen Treffen für Freizeitmathematik!