@Rho-ny-theta Das reicht sogar als formaler schon
:)Ich nehme mir 6 der Kugeln heraus und lege jeweils 3 auf eine Seite.
Ist die waage gleich schwer weiß ich eine der verleibenden ist die schwerere und muss nurnoch einmal wiegen, undzwar indem ich zwei kugeln wiege und dann weiß, dass entweder die verbleibende oder eine der beiden die schwere ist.
Das ganze geht auch mit 9 Kugeln
Hauptsache ist, dass ich das ganze auf 3 Kugeln im letzten Wiegeprozess runterrechen kann, das heißt, dass von meiner kugelnanzahl (n-3)/2<=3 sein muss, damit das ganze aufgeht, wobei n die Kugelanzahl ist.
Um hier was zu beweisen muss ich das feld von hinten aufrollen:
wenn ich beim letzten wiegen das feld auf 3 runterbrechen muss, dann muss ich folglich beim n-1 mal wiegen das ganze auf 9 runtergebrochen haben.
Ich kann entsprechend mehr kugeln rausnehmen wenn ich öfter wiegen kann.
Wieg ich dreimal, kann ich 9 Kugeln rausnehmen, also immer das vormals größte ergebnis, welches mich noch genau unterscheiden lässt, welche die schwere kugel ist.
Nehmen wir uns also eine folge und An ist die anzahl der Kugeln, die ich mindestens haben darf, damit das ganze aufgeht, dann ist
(An-A(n-1))/2<=A(n-1) meine Bedingung, damit das ganze aufgehen kann, weil das bedeutet, dass, wenn ich also An Kugeln rausnehme und das ganze halbiere (weil ich das beim wiegen ja tue, die anzahl der potentiell schweren kugeln mindestens halbieren), weniger oder genausoviel haben darf wie die maximalkugelanzahl, wenn ich nur n-1 mal wiegen darf.
wenn ich also n mal wiegen darf, dann ist An meine maximale Kugelanzahl, die ich dann durch umformung berechne:
(An-A(n-1))/2<=A(n-1)
An-A(n-1)<=2*A(n-1)
An<=3*A(n-1)
Das heißt, wir müssen heir gar nicht komplizierte rekursion anwenden, weil die Formel sehr einfach ist, nämlich immer dreimal so viele kugeln wie bei n-1 mal wiegen.
Das heißt, da bei 1 mal wiegen drei kugeln erlaubt sind sind bei n mal wiegen 3^n Kugeln erlaubt.
Es reicht also zur lösung, sich nur anzuschauen, auf wieviel kugeln man immer beim ersten mal wiegen das ganze runterbrechen muss, und dann zu schauen, ob man das über den rausnehmen und halbieren prozess schafft.
Das war jetzt nicht super formal, aber ich hoffe doch es war richtig.
