vollständige Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 17:54 Mi 21.01.2009 | | Autor: | Juho |
| Aufgabe | | Einer von n nach außen hin identischen Tennisbällen ist leichter als die übrigen, die alle gleichschwer sind. Wieviele Wägungen mit einer gewöhnlichen Balkenwaage sind sachlimmstenfalls nötig, um den leichteren eindeutig zu ermitteln? |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Ich muss diese Aufgabe im Rahmen einer Hausarbeit, die ich überarbeiten muss lösen. Ich muss sie überarbeiten, weil mein Beweis unvollständig war.
Mein Ansatz:
Man braucht bei
[mm] 3^r [/mm] < Anzahl der Bälle <= [mm] 3^j [/mm] , r=j-1
j Wägungen
Ich versuche dies durch vollständige Induktion zu beweisen, komme jedoch nicht weiter.
Mein Anfang:
Vor: Es gibt x Bälle, einer davon ist leichter als die anderen
(IA) : x=1 3^-1 < x <= [mm] 3^0 [/mm] => = Wägungen
(IV) Man braucht j Wägungen bei [mm] 3^r [/mm] < x <= [mm] 3^j [/mm] , r=j-1
(IB) Fall 1: [mm] 3^r [/mm] < x+1 <= [mm] 3^j
[/mm]
Fall 2: [mm] 3^j [/mm] < x+1 <= [mm] 3^k [/mm] , j=k-1
Bei dem Induktionsschritt komme ich nicht weiter und ich bin mir auch unsicher, ob man diese fallunterscheidung machen muss/sollte.
Danke schon mal für die Hilfe
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:49 Mi 21.01.2009 | | Autor: | maxi85 |
Hallo Juho,
ich würde da glaube ich völlig anders rangehen.
sagen wir wir haben n bälle. über die beschaffenheit meiner balkenwaage wird ja nix ausgesagt, also nehme ich an die waagschalen sind groß genug.
wenn ich jetzt die eine hälfte der bälle in die eine schale legen und die andere hälfte in die andere schale ist der ball in der schale die nach oben geht, weil ja leichter. (wenn die anzahl der bälle ungerade war lasse ich einen weg und weiß das er es ist wenn die schalen sich nicht bewegen)
jetzt habe ich also nur noch halb so viele bälle wie vorher und nur einmal gewogen. jetzt kannst du die prozedur wiederholen bis du den ball raus hast.
fehlt nur noch das du dir überlegst wie man das in ner formel ausdrücken kann, denn die will ich dir eigentlich nicht vorgeben.
mfg maxi
|
|
|
| |
|
Hallo Julia,
eine Rückfrage:
ist die Aufgabe einfach so, als offene Frage
gestellt, oder ist da schon Vorwissen vorhanden ?
Ist sogar die zu beweisende Formel für die Anzahl
der Wägungen schon vorgegeben ?
Dass du Potenzen mit der Basis 3 benützen
willst, deutet wenigstens auf gewisse Vor-
kenntnisse hin. Kennst du schon eine Wäge-
strategie - wenigstens für kleine n ?
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:50 Mi 21.01.2009 | | Autor: | Juho |
Also ich habe schon rausgefunden, dass ich, wenn es neun Bälle sind nur 2 mal wiegen muss. Und zwar so: Ich teile die Bälle in 3 Teilemengen auf. Lege jeweils eine in eine Waagschale und eine neben die Wagge. Nun weiß ich in welcher Menge der leichtere Ball ist (entweder wenn die Waage ausschlägt in einer der Waagschlen, oder wenn sie im Gleichgewicht bleibt, in der Menge neben der Schale). Dann teile ich die 3 Bälle unter denen der leichtere Ball ist wieder auf, lege je einen in die Waagschalen und einen daneben. Schlägt die Waage aus, weiß ich welches der leichtere Ball ist, bleibt sie im Gleichgewicht weiß ich es auch, da es dann der Ball sein muss, der neben der Waage liegt.
Des weitere weiß ich auch, wie man vorgehen muss, wenn man Bälle n hat. Man bildet wieder 3 Teilmengen wie oben. Bleibt dabei ein Ball übrig, so legt man ihn zu der Menge die neben der Waage liegt. Bleiben 2 Bälle übrig, so legt man jeweils einen zu den beiden Teilmengen in den Waagschalen.
Dadurch dass ich dieses Vorgehen verallgemeinert habe, bin ich auf die Formel gekommen. Diese ist auch richtig. Ich überarbeite ja meine Hausarbeit, daher weiß ich das, weil der Prof sie nicht als flasch angemerkt hat, sondern gesagt hat, dass ich sie noch durch vollständige Induktion beweisen soll.
Ich hoffe damit habe ich die Rückfrage beantwortet
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:30 Do 22.01.2009 | | Autor: | felixf |
Hallo Juho
Erstmal vorweg: die Gleichung [mm] $3^{j-1} [/mm] < n [mm] \le 3^j$ [/mm] (lass doch bitte das $r$ beim Aufschreiben weg, das verwirrt nur!) ist aequivalent zu $j - 1 < [mm] \frac{\log n}{\log 3} \le [/mm] j$, womit $r = [mm] \lceil \frac{\log n}{\log 3} \rceil [/mm] = [mm] \lceil \log_3 [/mm] n [mm] \rceil$ [/mm] ist. Hier ist [mm] $\log_3$ [/mm] der Logarithmus zur Basis 3, und [mm] $\lceil [/mm] x [mm] \rceil$ [/mm] rundet $x$ auf die naechste ganze Zahl auf.
> Also ich habe schon rausgefunden, dass ich, wenn es neun
> Bälle sind nur 2 mal wiegen muss. Und zwar so: Ich teile
> die Bälle in 3 Teilemengen auf. Lege jeweils eine in eine
> Waagschale und eine neben die Wagge. Nun weiß ich in
> welcher Menge der leichtere Ball ist (entweder wenn die
> Waage ausschlägt in einer der Waagschlen, oder wenn sie im
> Gleichgewicht bleibt, in der Menge neben der Schale). Dann
> teile ich die 3 Bälle unter denen der leichtere Ball ist
> wieder auf, lege je einen in die Waagschalen und einen
> daneben. Schlägt die Waage aus, weiß ich welches der
> leichtere Ball ist, bleibt sie im Gleichgewicht weiß ich es
> auch, da es dann der Ball sein muss, der neben der Waage
> liegt.
>
> Des weitere weiß ich auch, wie man vorgehen muss, wenn man
> Bälle n hat. Man bildet wieder 3 Teilmengen wie oben.
> Bleibt dabei ein Ball übrig, so legt man ihn zu der Menge
> die neben der Waage liegt. Bleiben 2 Bälle übrig, so legt
> man jeweils einen zu den beiden Teilmengen in den
> Waagschalen.
Das stimmt auch so.
> Dadurch dass ich dieses Vorgehen verallgemeinert habe, bin
> ich auf die Formel gekommen. Diese ist auch richtig. Ich
> überarbeite ja meine Hausarbeit, daher weiß ich das, weil
> der Prof sie nicht als flasch angemerkt hat, sondern gesagt
> hat, dass ich sie noch durch vollständige Induktion
> beweisen soll.
Vielleicht ein allgemeiner Hinweis zur vollstaendigen Induktion. Die kann man naemlich auch anders Formulieren (dies wird oft als starke Induktion oder starke vollstaendige Induktion bezeichnet):
Induktionsanker: Hat man $n = 1$ Ball, so braucht man genau [mm] $\lceil\log_3 n\rceil [/mm] = 0$ Waegungen.
Induktionsbehauptung: Hat man $n [mm] \le n_0$ [/mm] Baelle, so braucht man hoechstens [mm] $\lceil\log_3 n\rceil$ [/mm] Waegungen um den leichtesten Ball zu finden.
Induktionsschritt: Zu zeigen: Hat man $n = [mm] n_0 [/mm] + 1$ Baelle, so braucht man hoechstens [mm] $\lceil\log_3 n\rceil$ [/mm] Waegungen um den leichtesten Ball zu finden.
Hier darfst du jetzt nicht nur die Behauptung fuer $n - 1$, sondern fuer ein beliebiges $n [mm] \le n_0$ [/mm] benutzen!
(Und das brauchst du hier auch.)
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:44 Do 22.01.2009 | | Autor: | Juho |
Hallo,
bin neu in diesem Froum, deswegen weiß ich noch nicht ganz so gut, wie's hier läuft. Meine erste Frage ist leider noch nicht so ganz beantwortet. Vielleicht hilft meine Antwort auf die Rückfrage weiter mein Problem zu verstehen.
Also, ich weiß, dass die Formel, die ich gepostet habe richtig ist, mein Problem ist, dass ich sie durch vollständige Induktion beweisen soll, und dabei komme ich eben nicht weiter. Meine Überlegungen dazu habe ich in meiner ersten Frage und in der Beantwortung der Rückfrage schon dargelegt.
Freue mich sehr auf Antworten + vielen Dank schon mal
Julia
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:56 Do 22.01.2009 | | Autor: | abakus |
> Hallo,
>
> bin neu in diesem Froum, deswegen weiß ich noch nicht ganz
> so gut, wie's hier läuft. Meine erste Frage ist leider noch
> nicht so ganz beantwortet. Vielleicht hilft meine Antwort
> auf die Rückfrage weiter mein Problem zu verstehen.
>
> Also, ich weiß, dass die Formel, die ich gepostet habe
> richtig ist, mein Problem ist, dass ich sie durch
> vollständige Induktion beweisen soll, und dabei komme ich
> eben nicht weiter. Meine Überlegungen dazu habe ich in
> meiner ersten Frage und in der Beantwortung der Rückfrage
> schon dargelegt.
>
> Freue mich sehr auf Antworten + vielen Dank schon mal
> Julia
Hallo,
Zerlege mal die zu beweisende Kettenungleichung in zwei einzelne Ungleichungen.
Dann musst du zeigen:
- Für mehr als [mm] 3^j [/mm] Bälle reichen j Wägungen nicht. Du musst dabei im Prinzip nur zeigen, dass es einen ungünstigen Fall gibt, in dem der zu findende Ball immer in der größten der drei Teilmengen ist.
- j+1 Wägungen reichen. Lasse einfach bei den ersten Wägungen links und rechts [mm] \bruch{3^j}{3} [/mm] Bälle auflegen. Wenn der gesuchte Ball da drinnen ist, ist die Fortsetzung so, als hättest du von Beginn an mit [mm] 3^{j+1} [/mm] Bällen getestet. Ist der falsche Ball im (kleineren) Resthaufen, kannst du für die zweite Wägung (beim Teilen dieses Resthaufens) die drei Teile durch Hinzufügen bereits gewogener Bälle so aufstocken, als hättest du von Beginn an mit [mm] 3^{j+1} [/mm] Bällen gearbeitet.
Das sind nur ein paar Impulse. Da es eine Hausarbeit ist, muss der Hauptteil schon von dir kommen
Gruß Abakus
|
|
|
|
