Ein Rätsel |
| 05.04.2014, 12:27 | weisbrot | Auf diesen Beitrag antworten » | ||
| Ein Rätsel wenn zum zeitpunkt t auf dem feld gras wächst, dann auch zum zeitpunkt t+1. außerdem: wenn zum zp t in mindestens zwei der direkt anliegenden felder (edit: das heißt, sie teilen sich mit dem betrachteten feld eine seite) gras wächst, dann wächst zu t+1 auch auf diesem feld gras (pollenflug und so). wieviele felder müssen nun zu t=0 mindestens mit gras bewachsen sein, damit irgendwann alle felder bewachsen sind? da man die antwort sicher leicht raten kann ist die eigentliche aufgabe einen beweis dafür zu finden. danach kann man versuchen, seine aussage auf beliebige (nicht-quadratische) nxm-felder zu verallgemeinern. viel spaß! |
||||
| 05.04.2014, 12:37 | 10001000Nick1 | Auf diesen Beitrag antworten » | ||
RE: ein rätsel
Ist damit gemeint: Wieviele Felder müssen mindestens bewachsen sein, damit bei jeder beliebigen Anordnung dieser Felder irgendwann alle Felder bewachsen sind? Oder: Wieviele Felder müssen mindestens bewachsen sein, damit bei optimaler Anordnung dieser Felder irgendwann alle Felder bewachsen sind? |
||||
| 05.04.2014, 13:06 | weisbrot | Auf diesen Beitrag antworten » | ||
| RE: ein rätsel ok: wieviele felder musst du mindestens mit gras bepflanzen, dass... also letzteres. lg |
||||
| 05.04.2014, 13:11 | 10001000Nick1 | Auf diesen Beitrag antworten » | ||
OK, dann denke ich, dass ich eine Lösung habe. Ich schreibe sie dir erstmal nur per Nachricht, damit die anderen hier noch rätseln können. |
||||
| 05.04.2014, 13:21 | ollie3 | Auf diesen Beitrag antworten » | ||
| RE: ein rätsel hallo, @nick: er meint wahrscheinlich bei optimaler anordnung, sonst würde die aufgabe sehr kompliziert werden, dann wäre die antwort >1/2* n^2. Falls optimale antwort gemeint ist, würde ich sagen mindestens 4. Meine beweisskizze: Bei n=1 würde nichts passieren, bei n=2 ebenfalls, bei n=3 würde man immer zu der fomation X kommen. ---------------- X X X ------------------ X Erst bei n=4 würde es funktionieren, sowohl bei rechtecken als auch bei quadratischen feldern. gruss ollie3 |
||||
| 05.04.2014, 13:27 | 10001000Nick1 | Auf diesen Beitrag antworten » | ||
4 Gras-Felder sollen bei beliebigem n reichen? Wie würdest du denn diese 4 Gras-Felder z.B. auf einem 100x100-Feld anordnen, damit am Ende alle Felder bewachsen sind? 
|
||||
| Anzeige | ||||
|
|
||||
| 05.04.2014, 14:04 | weisbrot | Auf diesen Beitrag antworten » | ||
@ollie: ich sehe nicht genau wie du das meinst, 4 ist allgemein jedenfalls falsch. vielleicht hast du die aufgabe etwas falsch verstanden(?) ich hätte vielleicht das wort "schachbrettartig" benutzen sollen, falls es bei der beschaffenheit des feldes zu missverständnissen kommt(?) falls man beliebige anordnungen zulassen würde wäre die antwort allerdings auch nicht besonders schwer zu finden - indem man eine "äußere" zeile/spalte frei lässt, kann man immer bekommen, dass das gesamte feld nie bewachsen wird, man braucht also mindestens n^2 - n bewachsene felder. und man kann auch sehen, dass es ab n^2 - n + 1 immer funktioniert. lg |
||||
| 05.04.2014, 14:20 | ollie3 | Auf diesen Beitrag antworten » | ||
hallo, ich hatte mir das so gedacht: Man nimmt 4 felder nebeneinander: X X X X nächster schritt: ----- X X ---X X X X ----- X X Dann würden die 2 kreuze oben und unten wieder jeweils 2 nachbarn haben und die sache würde sich dann "wie eine krebsgeschwulst" nach alllen seiten ausbreiten, bis das ganze quadrat bzw. rechteck ausgefüllt ist. Oder habe ich die aufgabe wirklich falsch verstanden?
gruss ollie3 |
||||
| 05.04.2014, 14:22 | 10001000Nick1 | Auf diesen Beitrag antworten » | ||
Ich glaube, Felder, die sich nur an einer Ecke berühren, zählen nicht als "benachbart":
Wie soll denn dann erstmal eins von den oberen oder unteren X-Feldern bewachsen? |
||||
| 05.04.2014, 14:23 | weisbrot | Auf diesen Beitrag antworten » | ||
ja - felder heißen "benachbart", wenn sie eine seite teilen, also das eine feld oben, unten, links oder rechts an das andere grenzt - nicht diagonal. würde man diagonal zulassen, wären wohl auch nur 2 felder nötig. lg |
||||
| 05.04.2014, 16:36 | ollie3 | Auf diesen Beitrag antworten » | ||
hallo, ja, ich hatte die aufgabenstellung falsch verstanden. Jetzt weiss ich,wie das gemeint war. 
Also, ich glaube die richtige lösung ist bei quadratischem n*n- raster einfach n, man nimmt als startmuster einfach eine diagonale von links oben nach rechts unten, dann baut sich nach und nach alles auf, und bei rechteckigem nxm- raster wäre die minimalzahl die grössere der beiden zahlen n und m, man ergänzt einfach die restlichen spalten durch jeweils ein kreuz. Na, ist das richtig?
gruss ollie3 |
||||
| 05.04.2014, 16:39 | weisbrot | Auf diesen Beitrag antworten » | ||
ja, kann schon sein
allerdings ist das erraten dieser minimalen felderzahl wie gesasgt der leichte teil, der beweis der minimalheit, also dass es nicht mit weniger geht, ist das eigentliche "rätsel". lg |
||||
| 06.04.2014, 07:09 | ollie3 | Auf diesen Beitrag antworten » | ||
hallo, habe weiter über die sache nachgedacht: Falls in dem startbild noch weniger als n kreuze sein sollten, würde das bedeuten, das es mindestens eine leere zeile und eine leere spalte geben würde. Und das muss man dann zum widerspruch führen. Ich glaube ich bin der lösung schon ziemlich nahe...
gruss ollie3 |
||||
| 15.05.2014, 10:10 | pandu1 | Auf diesen Beitrag antworten » | ||
Wird nicht ganz klappen, hier Gegenbeispiel: O X O O O X O O O O O O O O O O X O O X O O O X O Die mittleren Spalte und Zeile sind leer und trotzdem werden alle Felder mit der Zeit bewässert. |
||||
| 15.05.2014, 12:08 | ollie3 | Auf diesen Beitrag antworten » | ||
hallo, dein beispiel funktioniert deswegen, weil du ja in einer spalte gleich mehrere kreuze hast, und ich sprach ja von "noch weniger als n kreuzen", du hast ja hier 5 kreuze in einem 5x5-feld. Ich hatte den beweis ja leider nicht zu ende führen können, war kurz vor schluss steckengeblieben, und grüble noch, wie man das exakt beiweisen kann.
gruss ollie3 |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
| Die Neuesten » |
|
