Wägeproblem < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:47 So 26.02.2012 | | Autor: | clemenum |
| Aufgabe | Gegeben seien 90 gleichartige Eisenkugeln, von denen bekannt ist, dass genau eine schwerer ist als die anderen 89. Man bestimme die maximale Anzahl an Wägungen, die man mit einer Balkenwaage mit zwei Schalen durchführen muss.
Hinweis: Zeigen Sie, dass man mit maximal 5 Wägungen auskommt.
Frage: Geht es auch mit 4?
Wie läuft es allgemein mit n Kugeln? |
An meinem Anhang habe ich den Existenzbeweis konkret erbracht. Ich kann aber nicht (formal) beweisen, dass es nicht noch kürzer geht. Ich vermute aber, dass fünf Schritte wirklich der kürzeste Weg ist.
Meine Strategie ist im wesentlichen, dass ich die Kugelanzahl auf drei Teile aufteile. Ich betrachte so in etwa $ [mm] [\frac{n}{3} [/mm] ] $
Die Idee rührt von daher, dass es ja drei Fälle zu unterscheiden gibt. Wenn eine Zahl nicht durch 3 teilbar ist, nehme ich einfach den Rest: So etwa bei 92. Ich teile so auf: 30, 30, 32
Die Anzahl der Schritte bis zum Finden der aussätzigen Kugel dürfte sich so nicht verändern.
Die Frage ist nun: Wie schreibe ich das formal auf?
![[a]](/images/paperclip.gif "Dateianhänge") Datei-Anhang
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
|
|
| |
|
> Gegeben seien 90 gleichartige Eisenkugeln, von denen
> bekannt ist, dass genau eine schwerer ist als die anderen
> 89. Man bestimme die maximale Anzahl an Wägungen, die man
> mit einer Balkenwaage mit zwei Schalen durchführen muss.
> Hinweis: Zeigen Sie, dass man mit maximal 5 Wägungen
> auskommt.
> Frage: Geht es auch mit 4?
> Wie läuft es allgemein mit n Kugeln?
> An meinem Anhang habe ich den Existenzbeweis konkret
> erbracht. Ich kann aber nicht (formal) beweisen, dass es
> nicht noch kürzer geht. Ich vermute aber, dass fünf
> Schritte wirklich der kürzeste Weg ist.
>
> Meine Strategie ist im wesentlichen, dass ich die
> Kugelanzahl auf drei Teile aufteile. Ich betrachte so in
> etwa [mm][\frac{n}{3} ][/mm]
> Die Idee rührt von daher, dass es ja drei Fälle zu
> unterscheiden gibt. Wenn eine Zahl nicht durch 3 teilbar
> ist, nehme ich einfach den Rest: So etwa bei 92. Ich teile
> so auf: 30, 30, 32
> Die Anzahl der Schritte bis zum Finden der aussätzigen ![[haee]](/images/smileys/haee.gif "[haee]")
> Kugel dürfte sich so nicht verändern.
>
> Die Frage ist nun: Wie schreibe ich das formal auf?
>
> Datei-Anhang
Hallo clemenum,
in deinem "Wägeplan" (oder heißt es Wiegeplan ...?), den du
mit dem Baum dargestellt hast, ist mir nicht klar, warum du
bei noch 10 Kugeln je 5 auf die Waagschalen legen willst und
nicht je 4 ...
Für eine systematische Beschreibung lohnt es sich möglicher-
weise, gerade den allgemeinen Prozess zu betrachten und
dabei mit kleinen Kugelanzahlen zu beginnen.
Es sei w(n) die Mindestzahl von Wägungen, die notwendig
sind, um unter n Kugeln die (einzige) schwerste mit Sicher-
heit auszusortieren.
Man überlegt sich leicht, dass w(1)=0 (die eine Kugel ist
stets schwerer als alle übrigen, da es gar keine übrigen
Kugeln gibt), w(2)=1, w(3)=1, w(4)=2 .
Bei n=4 kann man bei der ersten Wägung entweder 1+1
oder 2+2 Kugeln gegeneinander abwägen und braucht dann
genau eine weitere Wägung, um aus 2 Kugeln die schwerere
zu isolieren.
Weiter ist klar, dass die Folge der w(n) monoton steigend
sein muss, also [mm] w(n+1)\ge{w(n)} [/mm] .
Nun kommt der Hauptschritt der Überlegung: wie ermittle
ich w(n), falls ich alle [mm] w_k [/mm] mit [mm] 1\le{k}\le{n-1} [/mm] schon kenne ?
Natürlich wird man die n Kugeln in drei "etwa" gleich große
Haufen unterteilen. Ist n durch 3 teilbar, lautet die
optimale Aufteilung n=k+k+k mit k=n/3 , und es wird klar, dass
w(n)=w(k)+1=w(n/3)+1 sein muss.
Jetzt verbleiben noch die Fälle zu betrachten, wo der
Rest der Division von n durch 3 gleich 1 oder 2 ist.
Das kann man sich mal etwa an den Beispielen n=16
und n=17 klar machen. Im Fall n=16 könnte man
entweder so aufteilen:
[mm] 16=\underbrace{2*5}_{1. W\ddot a gung}+6 [/mm]
oder so: [mm] 16=\underbrace{2*6}_{1. W\ddot a gung}+4 [/mm] .
Es zeigt sich mittels Einbezug der Monotonie der w(n) ,
dass offenbar w(16)=w(6)+1 sein muss. Diese Überlegungen
kann man nun bestimmt auch mittels Gauß-Klammer, wie du
ja schon gemerkt hast, allgemein auf den Punkt bringen.
Auf diesem Weg lassen sich schließlich die Werte w(n)
rekursiv darstellen und z.B. tabellieren, und zuguterletzt
wird dann wohl noch klar, dass man das Ergebnis in eine
handliche Formel stecken kann ...
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:16 So 26.02.2012 | | Autor: | clemenum |
Hallo Al. Chw.
Vielen Dank für deine Hilfe! 
Ich werde mich morgen weiter damit befassen!
Lg.
Clemenum
|
|
|
|
![[a]](uploads/forum/00871014/forum-i00871014-n001.jpg "Dateianhänge"){kind=small}
Datei-Anhang
