Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Wägeproblem - minimale Schrittanzahl im Baum

Wägeproblem - minimale Schrittanzahl im Baum

Universität / Fachhochschule

Kombinatorische Optimierung

Rekursives Zählen

Tags: Kombinatorische Optimierung, Rekursives Zählen

Clemensum aktiv_icon

17:47 Uhr, 29.02.2012

Man betrachte folgendes Wiegeproblem:
Es seien 90 Kugeln gegeben, von denen exakt 89 Kugeln gleichschwer sind und genau eine ist schwerer als jede andere.
Wie groß ist nun die minimale Wägeanzahl um DIE schwerere Kugel zu identifizieren?
Hinweis: Zeigen Sie, dass 5 Wiegungen möglich sind.
Frage: Sind 4 Wiegungen auch möglich?
Können Sie das Problem auf

n

Kugeln verallgemeinern?

Nun, ich versuche hier das Vorgehen am zugehörigen Baumdiagramm formal darzustellen. Zuerst betrachte ich mal eine geringere Anzahl von Kugeln, sodass das (hoffentlich) dahintersteckende (Zähl-)Prinzip zum Vorschein kommt. Dabei unterteile ich (wegen der jeweils frei ausgehden Äste) das

n

die Reste

m o d u l o 3

ein.
Sei dazu

w (n)

die minimale Anzahl an Wiegungen bis zur SICHEREN Identifikation der schwereren Kugel im Baumdiagramm. Die paar ersten Fäll sind (fast) trivial:

w (1) = 0

w (2) = 1

w (3) = 1

w (4) = 2

21 = 2 \cdot 7 + 7

7 = 2 \cdot 3 + 1

-----------------------

\Rightarrow w (21) = 1 + w (7) = 1 + 2 = 3

22 = 2 \cdot 7 + 8

8 = 2 \cdot 3 + 2

--------------------------

\Rightarrow w (22) = 1 + w (8) = 1 + 1 + w (2) = 1 + 1 + 1 = 3

23 = 2 \cdot 7 + 9

9 = 2 \cdot 3 + 3

3 = 2 \cdot 1 + 1

-----------------------

\Rightarrow w (23) = 1 + w (9) = 1 + 1 + 1 = 3

So, nun zu meinem Hausaufgabenbeispiel:

90 = 2 \cdot 30 + 30

30 = 2 \cdot 10 + 10

10 = 2 \cdot 3 + 4

4 = 2 \cdot 1 + 2

----------------------

\Rightarrow w (90) = 5

Es geht sich also tatsächlich nur mit 5 Schritten aus!
Meine Begründung dafür, dass 4 Schritte nicht die minimale Anzazhl sein kann:
Wäre die minimale Anzahl 4, so würde die Summe der Knoten im Baumdiagramm entlang der "=" - Äste 89 betragen müssen. Das steht aber im Widerspruch dazu, dass man auf die Waage jeweils eine gerade Anzahl von Kugeln liegt (alles andere wäre klarerweise kein Informationsgewinn!).

Ich sehe rein intuitiv, dass gelten muss:

w (n) \geq w (n - 1) \forall n \in N

So, jetzt zum Hauptschritt (zur Generalisierung des Problems):
Wie kann

w (n)

berechnet werden, wenn ich alle

i

mit

1 \leq i \leq n - 1

schon vor mir habe?

Sei dazu (wie bereits erwähnt) in drei Fälle unterschieden:
I Sei

n = 3 i = 2 i + i

für

i \in N

beliebig aber fest

\Rightarrow w (n) = 1 + w (i)

(wohl ein starker Beleg für meine vermutete Monotonieeigenschaft)
II Sei

n = 3 i + 1 = 2 i + i + 1

\Rightarrow w (n) = 1 + w (i) + w (1) = 1 + w (i)

(also genau so groß wie bei Fall I)
III Sei

n = 3 i + 2 = 2 i + i + 2

\Rightarrow w (n) = 1 + w (i) + w (2) = 2 + w (i)

(also genau um eins mehr als in Fall II (bzw. Fall I) )

So, jetzt kommen die Großen Fragen:
1. Wieso stimmt das nicht mit meinem obigen konkreten Beispiel überein?
2. Wie kann ich daraus eine explizite Formel gewinnen?

Hat jemand Hinweise/Tipps für mich?

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich bräuchte bitte einen kompletten Lösungsweg." (setzt voraus, dass der Fragesteller alle seine Lösungsversuche zur Frage hinzufügt und sich aktiv an der Problemlösung beteiligt.)

hagman aktiv_icon

23:55 Uhr, 29.02.2012

Jede Wägung kann eine von drei Antworten liefern: "linke Schale schwerer", "rechte Schale schwerer", "beide gleich"; je nach Situation kann es auch der Fall sein, dass aufgrund des Vorwissens nicht alle drei möglich sind..
Demnach hat jeder Knoten des Baumes höchstens drei "Nachkommen".
In jeder Ebene finden sich alse höchstens dreimal so viele Knoent wie in der vorhergehenden Ebene des Baumes.
An der Wurzel (0-te Ebene) ist ein Knoten.
Bei einem Verfahren mit

w

Wägungen hat man in der w-ten Ebene höchstens

3^{w}

Knoten.
Es folgt

n \leq 3^{w}

bzw.

w (n) \geq {log}_{3} (n)

.
Es gilt wohl sogar die genaue Abschätzung

{log}_{3} (n) \leq w (n) < {log}_{3} (n) + 1

.
Die rechte Ungleichung folgt im Prinzip so, wie du es auch vorhattest, leichter vielleicht so:

Satz: Wenn

n \leq 3^{k},

dann

w (n) \leq k

.
Beweis:
Die Ungleichung folgt per Induktion nach

k :

Die Anfangswerte

w (0) = w (1) = 0

liefern den Fall

k = 0

.
Für

n > 1

ist insbesondere

k \geq 1

. Folgende Strategie führt in höchstens

k

Schritten zum Erfolg:
Schreibe

n = 3 m - r

mit

0 \leq r \leq 2

.
Dann ist

n + r

durch 3 teilbar und

\leq 3^{k} + 2,

also

n + r \leq 3^{k}

und schließlich

m \leq 3^{k - 1}

.
Es ist

m \geq r,

denn

n = 2

führt auf

m = 1, r = 1; n = 3

auf

m = 1, r = 0; n \geq 4

auf

m \geq 2 \geq r

.
Somit

n = 2 m + (m - r) \geq 2 m

Vergleiche in einer ersten Wägung die ersten

m

mit den zweiten

m

Kugeln.
Falls eine Gruppe schwerer ist, braucht man noch höchstens

w (m)

weiter Wägungen.
Bei Gleichstand dagegen braucht man höchstens

w (m - r)

weitere Wägungen.
Wegen

m - r \leq m \leq 3^{k - 1}

gilt hierfür die Induktionsannahme und man kommt insgesamt auf höchstens

(k - 1) + 1 = k

Wägungen

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

978265

978117

	Status: nicht eingeloggt	Noch nicht registriert?