Metallkugeln 2 |
| 24.06.2010, 06:54 | pandu1 | Auf diesen Beitrag antworten » | ||
| Metallkugeln 2 |
||||
| 24.06.2010, 08:54 | kurellajunior | Auf diesen Beitrag antworten » | ||
Ich biete die offensichtlichen 7. Sieben Kugeln messen, dann weiß man es sicher 
Wer kann weniger? |
||||
| 24.06.2010, 09:13 | sulo | Auf diesen Beitrag antworten » | ||
RE: Metallkugeln 2
Was für eine Art Rätsel ist das? Eine Hausaufgabe? Ein Wettbewerb? Sollen wir das für dich lösen, ohne dass du einen Beitrag dazu lieferst? Oder kennst du die Antwort und es ist ein echtes Rätsel für uns? 
|
||||
| 24.06.2010, 09:39 | wisili | Auf diesen Beitrag antworten » | ||
| RE: Metallkugeln 2 Das Rätsel ist nicht präzise genug formuliert: 1. Zeigt das Messgerät ein Vorzeichen an? (oder nur den Betrag) 2. Falls ja: Muss man das Ladungsvorzeichen mitbestimmen? (oder nur das Paar der geladenen Kugeln) |
||||
| 24.06.2010, 09:50 | cutcha | Auf diesen Beitrag antworten » | ||
höchstens 6 mal habe ich raus. Im schlimmsten Falle hat man am Ende 2 neutrale, diese beiden sind dann + und - |
||||
| 24.06.2010, 09:54 | pandu1 | Auf diesen Beitrag antworten » | ||
RE: Metallkugeln 2
Ist ein echtes Rätsel, habe zwei unterschiedliche Lösungswege gefunden und grob bewiesen, dass es nicht mit weniger Messungen geht. |
||||
| Anzeige | ||||
|
|
||||
| 24.06.2010, 09:57 | pandu1 | Auf diesen Beitrag antworten » | ||
RE: Metallkugeln 2
Mit Vorzeichen, drei möglichkeiten: -1,0,+1 Und man muss auch bestimmen, welche positiv und welche negativ geladen ist. |
||||
| 24.06.2010, 10:11 | wisili | Auf diesen Beitrag antworten » | ||
Also braucht es dann noch die 7. Messung. |
||||
| 24.06.2010, 10:42 | cutcha | Auf diesen Beitrag antworten » | ||
Dann ja. Ich verstehe übrigens nicht wo das Rätsel dahinter steckt ^^ |
||||
| 24.06.2010, 11:23 | cutcha | Auf diesen Beitrag antworten » | ||
Habe doch herausgefunden wie es mit 6 geht. Man macht 2 4er Stapel. Den ersten misst man. Ist es neutral, nimmt man eine weg und misst nochmal. Die 3 sind wieder neutral. man nimm eine Weg und misst nochmal, wieder neutral. 2 unbekannte über. Vom zweiten Stapel nimmt man sich nun 3 Stück, legt eine von den übrigen des ersten Stapels dazu, misst. Ist das Ergebnis neutral, fallen die beiden vom ersten Stapel somit weg. Von den drei übrigen des 2. Stapels wieder eine wegnehmen und messen, ist es neutral, braucht man nurnoch eine messen. Hoffe da steckt kein Gedankenfehler drin ^^ Jedes messen ist nun schwarz markiert. |
||||
| 24.06.2010, 12:21 | wisili | Auf diesen Beitrag antworten » | ||
Es geht auch mit 5 Messungen: Ordnet man die 8 Kugeln in den Ecken eines Würfels an und misst dann die 4 Kugeln je einer von 3 nichtparallelen Würfelflächen so findet man: Ergibt keine Messung 0, dann sind die gesuchten Ladungen auf einer Würfelkörperdiagonale, und sind bereits bestimmt. Ergibt eine Messung 0, dann sind die gesuchten Ladungen auf einer Würfelflächendiagonale, und es kommen nur noch 2 parallele in Frage (und deren Orientierung betreff Ladungsvorzeichen ist bestimmt). Ergeben zwei Messungen 0, dann sind die gesuchten Ladungen auf einer Würfelkante, und es kommen nur noch 4 parallele in Frage (und deren Orientierung betreff Ladungsvorzeichen ist bestimmt). Zwei weitere Messungen genügen somit, um Eindeutigkeit zu erzwingen. Informationstheoretisch kann es nicht mit weniger als 4 Messungen gehen: Der Informationsgehalt des Ortes der Ladungen beträgt ld(8*7) = 5.8 bit. Der Informationsgehalt von 4 Messungen beträgt ld(3^4) = 6.3 bit. Der Informationsgehalt von 3 Messungen beträgt ld(3^3) = 4.8 bit. (Dass die ersten 3 Messungen nicht dreimal 0 geben können, stört diese Abschätzung nicht.) Wer findet also die Lösung mit bloss 4 Messungen? |
||||
| 24.06.2010, 14:14 | kurellajunior | Auf diesen Beitrag antworten » | ||
Kannst Du mir das mal etwas ausführlicher Erklären (oder Wiki-linken) was ist ld()? |
||||
| 24.06.2010, 14:36 | wisili | Auf diesen Beitrag antworten » | ||
wikipedia ld = logarithmus dualis, Logarithmus zur Basis 2, auch als Zweierlogarithmus oder dyadischer oder binärer Logarithmus bezeichnet (manchmal auch mit der Abkürzung lb); wird in der Informatik aufgrund des Binärsystems verwendet. |
||||
| 24.06.2010, 14:56 | kurellajunior | Auf diesen Beitrag antworten » | ||
Und was hat der jetzt mit dem Informationsgehalt zu tun? Hab ich da die entscheidende Vorlesung verpennt? |
||||
| 24.06.2010, 16:10 | AD | Auf diesen Beitrag antworten » | ||
Kann sein, aber was kann man nicht alles nachholen. 
|
||||
| 24.06.2010, 19:52 | Huggy | Auf diesen Beitrag antworten » | ||
Um die Sache mit dem Informationsgehalt mal für das gemeine mathematische Fußvolk (Leute wie mich) zu veranschaulichen: Wenn eine Messung 3 mögliche Ergebnisse hat, dann man kann man mit 3 Messungen maximal 3^3 = 27 Konfigurationen unterscheiden. Man hat aber am Anfang 30 mögliche Konfigurationen. Oder umgekehrt: Vor einer Messung habe man n zulässige Konfigurationen. Die werden durch die Messung in drei Gruppen unterteilt. Die größte davon muss >= n/3 Konfigurationen enthalten. Also geht es ausgehend von 30 Konfigurationen nicht mit 3 Messungen. Mit 4 Messungen geht es tatsächlich, falls mir kein Fall durch die Lappen gegangen ist. Aber heute werde ich das nicht mehr ins Board stellen. |
||||
| 25.06.2010, 09:22 | kurellajunior | Auf diesen Beitrag antworten » | ||
Hrumpf. Immer wenn es technisch wird hilft wikipedia wenig weiter. Muss ich mir noch ein Buch besorgen, damit ich den Sinn dahinter verstehe. |
||||
| 25.06.2010, 10:04 | Huggy | Auf diesen Beitrag antworten » | ||
Autsch! ich brauche eine Brille. Ich habe 6 Kugeln gelesen, aber da steht 8 Kugeln in der Aufgabe. Also gilt es neu nachzudenken. |
||||
| 27.06.2010, 14:12 | Mystic | Auf diesen Beitrag antworten » | ||
Zunächst einmal ist das wirklich ein außerordentlich nettes Rätsel...Leider ist Sonntag und ich bin einfach zu faul, um selbst darüber nachzudenken, also habe ich Derive damit beauftragt, nach einer Lösung zu suchen...Immerhin habe ich aber die Programme dazu selbst geschrieben...
Die generelle Strategie ist es "Fragen", wie z.B. 1234 (= Wähle die Kugeln 1-4 für die Messung) so zu stellen, dass die potenziellen Antworten anzahlmäßig möglichst gleichverteilt sind... Dabei stellt sich heraus, dass in 8 Fällen die Anzahl der Fragen 3 beträgt, in 40 Fällen ist sie 4, in den restlichen 8 Fällen dann 5, der Erwartungswert ist also exakt 4... |
||||
| 27.06.2010, 14:31 | wisili | Auf diesen Beitrag antworten » | ||
@mystic Ich durchschaue noch nicht , was du damit sagen willlst: Hast du alle Mess-Auswahl-strategien durchforstet ? Oder steht der Beweis, dass es mit 4 Messungen doch nicht geht, noch immer aus? |
||||
| 27.06.2010, 18:25 | Mystic | Auf diesen Beitrag antworten » | ||
Naja, meine Strategie ist wie gesagt, die nächste "Frage" immer so zu wählen, dass die potenziell möglichen Antworten (keine, positive, negative Ladung) unter allen Möglichkeiten, die es aufgrund der bisherigen "Antworten" noch gibt, möglichst gleich verteilt sind, führt immerhin in 48 von 56 Versuchen nach maximal 4 Fragen zum Ziel...In 8 Fällen braucht man mit dieser Strategie leider 5 Fragen...Ich habe diese nachfolgend aufgelistet: [1, 0, -1, 0, 0, 0, 0, 0] [1234, 1256, 1237, 1345, 1236] [-1, 0, 1, 0, 0, 0, 0, 0] [1234, 1256, 1237, 1345, 1236] [0, 0, 1, 0, 0, 0, 0, -1] [1234, 1256, 1257, 1345, 1235] [0, 0, -1, 0, 0, 0, 0, 1] [1234, 1256, 1257, 1345, 1235] [0, 0, 0, 1, 0, 0, 0, -1] [1234, 1256, 1257, 1345, 1235] [0, 0, 0, -1, 0, 0, 0, 1] [1234, 1256, 1257, 1345, 1235] [0, 0, 0, 0, 0, 1, 0, -1] [1234, 1256, 1237, 1345, 1236] [0, 0, 0, 0, 0, -1, 0, 1] [1234, 1256, 1237, 1345, 1236] Leider ist es so, dass selbst wenn man mit einer anderen Strategie zeigen könnte, dass diese 8 Fälle in weniger als 5 Fragen machbar sind, ja dann noch nicht sicher ist, dass damit dann die anderen 48 Fälle weiterhin mit höchstens 4 Fragen machbar bleiben... Das ist zumindestens einmal der Stand der Dinge aus meiner Sicht...Ein strenger Beweis, dass es mit maximal 4 Versuchen nicht geht, ist es also noch nicht, aber die Ergebnisse gehen doch eher in die Richtung, dass es nicht möglich sein sollte... Edit: Falls jemand versuchen sollte, für obige Vorgaben bessere Strategien als die angegebenen zu entwickeln, dann bitte die ersten 2 Fragen 1234 und 1256 unverändert lassen...Die sind nämlich noch 100% optimal und auch für die anderen 48 Vorgaben stets die zwei ersten Fragen... |
||||
| 30.06.2010, 16:02 | Mystic | Auf diesen Beitrag antworten » | ||
Hier nun noch ein Resümee, nachdem ich jetzt etwas mehr Zeit hatte, mich mit der Sache nochmals zu beschäftigen: Es steht für mich eigentlich nun zweifelsfrei fest, dass man mit maximal 4 Fragen nicht auskommt, wobei "Frage" wie schon bisher für eine Auswahl von Metallkugeln, die man sich von 1 bis 8 nummeriert denkt, steht, und eine "Antwort" dann -1,0 oder 1 ist, je nachdem was die Ladung dieser Auswahl ist... Des weiteren soll im Folgenden die Anzahl der Kugeln in der jeweiligen Auswahl die "Länge" der Frage sein... Ein logisch einwandfreier Beweis muss natürlich alle denkbaren Ratestrategien berücksichtigen, wobei eine Strategie einfach eine Tabelle ist, welche genau angibt, was in Abhängigkeit von den bisherigen Fragen und Antworten dann die nächste Frage sein soll... Da es zunächst 127 sinnvolle Fragen gibt, nämlich 8 Fragen der Länge 1, 28 der Länge 2, 56 der Länge 3 und 35 der Länge 4 (o.B.d.A. vereinbaren wir, dass die Kugel 8 in Fragen der Länge 4 nicht vorkommen soll!), sieht das zunächst einmal nach einer "gewaltigen" Menge von Strategien aus... In Hinblick auf unser Ziel und auf viele offensichtlich "äquivalente" (in der Algebra würde man wohl auch sagen "isomorphe") Strategien, kann man den Suchbaum aber sehr leicht "beschneiden"... Zuerst sollte man sich sich über die optimale Länge der ersten Frage Klarheit verschaffen, wobei für die erste Frage noch alle Fragen gleicher Länge untereinander äquivalent sind... Dazu die Häufigkeitsverteilungen der möglichen Antworten unter allen 56 Belegungen, wobei ich o.B.d.A. jeweils eine Frage der gegebenen Länge herausgreife: H(1) = (7,42,7) (=7 Antworten sind -1, 42 Anworten sind 0, 7 Antworten sind 1) H(12) = (12,32,12) (=12 Antworten sind -1, 32 Anworten sind 0, 12 Antworten sind 1) H(123) = (15,26,15) (=15 Antworten sind -1, 26 Anworten sind 0, 15 Antworten sind 1) H(1234) = (16,24,16) (=16 Antworten sind -1, 24 Anworten sind 0, 16 Antworten sind 1) Wenn wir nun mit maximal 4 Fragen auskommen wollen, ist es offensichtlich, dass für die erste Frage keine der drei Häufigkeiten 27, für die zweite Frage keine der drei Häufigkeiten 9, usw. übersteigen darf, allgemein darf für die k-te Frage keine Häufigkeit größer als sein, sonst haben wir ein Problem, wenn wir es mit 4 maximal Fragen schaffen wollen... Aus diesem Grund scheiden schon mal Fragen der Länge 1 und 2 für die erste Frage aus... Betrachten wir nun nach den potenziell ersten Fragen 123 bzw. 1234 die zweite Frage, wobei wir aber nun schon die Anworten auf die erste Frage berücksichtigen müssen... Nun gibt es aber für die erste Frage 123 und die Antwort 0 darauf keine zweite Frage mehr, wo die Größe aller Häufigigkeitsklassen dann höchstens 9 ist, weshalb wir im Folgenden nur mehr 1234 als erste Frage betrachten... Zu dieser ist die einzig mögliche zweite Frage (bis auf "Äquivalenz" versteht sich), wenn die Anwort 0 war, dann 1256 mit der Häufigkeitsverteilung H(1256 | 1234 -> 0) = (8,8,8) Leider läßt sich dann aber zu den unten angegebenen Anworten auf die beiden ersten Fragen keine dritte Frage f mehr finden mit der Eigenschaft wie wir sie brauchen würden, wenn es mit maximal 4 Fragen klappen sollte...Man braucht also in Einzelfällen mehr Fragen, allerdings maximal 5, wie von wisili (und unabhängig davon von mir oben) schon festgestellt... Bei Anwendung einerr optimalen Strategie, für welche die beiden ersten Fragen die Länge 4 mit genau 2 gemeinsamen Ziffern haben müssen, ist das höchstens dann der Fall, wenn die beiden Anworten darauf unterschiedlich und mit genau einer Antwort 0 sind...In diesem Fall kommt als nächstes z.B. die Frage 17...Wird sie mit 0 beantwortet, kommt als nächstes z.B. die Frage 35...Ist die Antwort ebenfalls 0, so hat man den "worst case", der in genau 8 von den 56 Vorbelegungen auftritt, dass man wirklich genau eine weitere Frage braucht... |
||||
| 06.07.2010, 19:04 | Holgi77 | Auf diesen Beitrag antworten » | ||
Was ich mich frage, wieso die Kugeln geladen sind. Da macht das ganze doch nur Kompliziert. 1. Dürfen die Kugeln sich nicht berühren, da sonst Ladungen übertragen werden. 2. Muss ich die Isoliert anfassenum sie zu Gruppen zusammen zu legen. Hätte mann nicht viel einfacher sagen können das 8 gleich aussehende Kugeln sind, von denen 6 je genau 100 g wiegen, eine 90g und eine 110g wiegt, und man eine Küchenwaage (anzeige in g ) also keine Balkenwaage hat, und man mit möglichst wenig Messungen die leichtere und die schwerere Kugel heraus finden will. Mach das ganze irgendwie anschaulicher, und auch "realer" |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
| Die Neuesten » |