Wieviele Kugeln dürfen es maximal sein, bei n mal wiegen?

Question

Aufgabe:

Wieviele Kugeln dürfen es maximal sein, bei n mal wiegen?
Problem/Ansatz:

Gegeben seien (k-1) identische Kugeln und eine optisch identische Kugel mit einem geringfügig anderen Gewicht.

Zur Bestimmung eben dieser Kugel wie auch ob sie leichter oder schwerer ist als die anderen, darf eine Balkenwaage n mal benutzt werden.

Gesucht ist die Funktion der maximalen k(n) für n>=3, so dass es stets gelingt zu eruieren, welche der k Kugeln etwas anders ist.

Tipp: Für n=3 ist k=12.

Comments

vgl:

https://www.focus.de/finanzen/karriere/bewerbung/vorstellungsgespraech/brainteaser-kopfnuss-im-bewerbungsgespraech_id_1722285.html

https://www.youtube.com/watch?v=FZtby90vMFI

---

Das Video zeigt einen ersten Ansatz für n=2 und die gesuchte Kugel ist schwerer.

In der Fragestellung ist die gesuchte Kugel aber entweder leichter oder schwerer und es darf z.B. 100 mal gewogen werden und die Frage ist, wieviel Kugeln dürfen es dann maximal sein, dass die eine Kugel stets gefunden werden kann.

Der Ansatz wurde verstanden, jetzt folgt der Weg vom Einfachen hin zum Komplexen ...

---

Kleiner Hinweis:

Bei 3 mal wiegen dürfen es maximal 12 Kugeln sein,

bei 4 mal wiegen dürfen es maximal 38 Kugeln sein,

wieviele Kugeln dürfen es maximal sein bei n mal wiegen?

---

Also wenn man die Strategie die ich für \(n=3\) verwendet habe erweitert kann man relativ einfach induktiv beweisen, dass \(k(n)\geq 4\cdot 3^{n-2}\) gilt. Über andere Strategien habe ich noch nicht nachgedacht, aber wenn wenn \(k(4)=38\) gilt gibt es ja offensichtlich eine Bessere.

Aus Interesse: Hast du einen Beweis dafür, dass deine Werte tatsächlich maximal sind oder "nur" einen Beweis dafür, dass man sie erreichen kann?

Answer 1

Hallo

willst du die Lösung oder soll das ein Rätsel sein? Lösungen gibt es viele im Netz, ausführlich etwa in https://www.eurocg.org/tizian.cs.uni-bonn.de/Lehre/Seminare/PSAchilles08/Ausarbeitungen/Wiegeprobleme.pdf

lul

Comments

Dieser Link liefert nicht die exakte Funktion von maximalen Kugeln in Abhängigkeit einer gegebenen Anzahl an Wiegungen.

Für 4 Wiegungen ergibt die falsche Formel 81 - 3 >= 2 * Anzahl Kugeln.

Dem Zufolge könnten mit 4 Wiegungen 39 Kugeln bewältigt werden.

Tatsächlich sind nur 38 Kugeln möglich, Die Formel ist somit falsch.

Je großer die Anzahl der Wiegungen ist, desto weiter entfernt sich die falsche Lösung von der tatsächlich machbaren maximalen Kugelanzahl.

Habe einen konstruktiven Beweis für die Gültigkeit meiner Formel mit meiner Methode.

---

Kommando zurück:

Habe eben eine Lösung für 39 Kugeln mit 4 mal wiegen gefunden. Die Aussage mit den 38 Kugeln war falsch - sry.