Knobelei zu Mengenlehre II

Neue Frage »

Opher19782808 Auf diesen Beitrag antworten »
Knobelei zu Mengenlehre II
Meine Frage:
Ein Hersteller von Murmeln testet sein Produkt, indem Murmeln von verschiedenen
Stockwerken des 100-stöckigen Bürogebäudes des Herstellers fallen gelassen werden.
Damit soll das höchste Stockwerk F zu gefunden, von welchem die Murmeln fallen
gelassen werden können ohne zu zerbrechen.
1. Angenommen man hat nur eine Murmel: wie oft muss man sie fallen lassen, um
F zu finden?
2. Angenommen man hat nun zwei Murmeln: wie oft muss man sie fallen lassen,
um F zu finden?
3. Wie viele Stockwerke hat das höchste Gebäude, in dem man das korrekte Stockwerk F mit k mal Fallenlassen bestimmen kann, wenn man zwei Murmeln hat?
Versuchen Sie zunächst das Ergebnis für k = 2, 3, 4 zu finden.
4. Finden Sie eine rekursive Formel für die höchste Zahl n(k, m) von Stockwerken,die ein Gebäude haben kann, bei dem man das Murmel-Test Problem mit m Murmeln und k mal Fallenlassen lösen kann.
5. Zeigen Sie:
n(k,m)


Meine Ideen:
Zu 1. F mal?
Zu 2. Man könnte überlegen die erste Kugel bei 5, 10 etc. Fallen zu lassen.
Sobald sie kaputt geht. fängt man im 1.,6., etc. Stockwerk an?
Mein Ansatz scheint falsch zu sein, weil die anderen Fragen so wenig Sinn machen?
Hat jemand netterweise einen Tip zum gesuchten Vorgehen?
sibelius84 Auf diesen Beitrag antworten »

Hi Opher,

deine Antwort zu 1 dürfte stimmen, da würde ich nur noch eine entsprechende Begründung dranhängen.
Zu 2 könnte man sich so etwas überlegen wie: Ich lasse Murmel 1 aus Stockwerk 50 fallen. Geht sie kaputt, so muss ich 1, ..., 49 durchprobieren - bleibt sie ganz, dann halt 51, ..., 100. Dies reduziert die maximal nötige Anzahl von Versuchen von 100 auf 51. Soweit, so gut. Geht es aber vielleicht noch besser? Was ist, wenn man zuerst 20 probiert, falls sie ganz bleibt als nächstes 40, usw.? Kriegt man damit eine bessere Anzahl? Kann man diese Anzahl dann noch weiter verbessern, zB durch Wahl einer geeigneten anderen Zahl als 20...?
(Deine Überlegung ergibt also m.E. durchaus Sinn! Du musst sie nur konsequent bis zu Ende durchhalten, immer weiter optimieren bzw. zum Schluss eben gerade durch den Versuch der weiteren Optimierung erkennen, warum eine solche nicht möglich ist.)

Soweit erstmal - zu 3 könnte man ja auch entsprechend des Tipps recht nett "naiv" anfangen zu überlegen für k=2,3,4.

LG
sibelius84
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »