Die Mathe-Redaktion - 19.08.2017 14:52 - Registrieren/Login
Auswahl
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Apr. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 414 Gäste und 13 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Mathematik: 120 Kugeln und eine Balkenwaage
Freigegeben von matroid am Do. 18. Februar 2016 22:32:25
Verfasst von JoeM -   2054 x gelesen [Gliederung] [Statistik] Druckbare Version Druckerfreundliche Version
Spiele+Rätsel

120 Kugeln und eine Balkenwaage



Gegeben sind  N = 120 Kugeln, die alle gleich aussehen. Eine Kugel ist schwerer, oder leichter, als alle anderen Kugeln. Mit einer Balkenwaage soll die >falsche Kugel< identifiziert werden incl. der Angabe, ob diese Kugel schwerer, oder leichter ist, als alle anderen Kugeln.

--  wie viele Wägungen W sind minimal erforderlich ?

--  wie laufen diese Wägungen ab ?

--  angenommen: Die Verteilung der Kugeln ist pro Wägung stets gleich.
     Man kennt nach Ablauf von W Wägungen nur den jeweiligen Ausschlag der
     Balkenwaage; Beispiel :

1. Wägung:  ▼ ( linke Waagschale ist schwerer, und geht nach unten )

2. Wägung:  ▲ ( linke Waagschale ist leichter, und geht nach oben )

3. Wägung : ▬  ( beide Schalen sind im Gleichgewicht )

4. Wägung:  ▲ ( linke Waagschale ist leichter, und geht nach oben )

etc.

Wie könnte so eine stets gleiche Verteilung der Kugeln pro Wägung aussehen, um nach W Wägungen etwa mit der Information  > ▼ ▲ ▬ ▲ ….. < die >falsche Kugel< zu identifizieren, incl. Gewichtsangabe (schwerer / leichter) ?

Autor: Dipl.- Ing. Josef Meiler


Link auf diesen Artikel Link auf diesen Artikel  Druckbare Version Druckerfreundliche Version  Einen Freund auf diesen Artikel aufmerksam machen Weitersagen Kommentare zeigen Kommentare  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Spiele+Rätsel :: automatisch eingefügt und unbearbeitet :
120 Kugeln und eine Balkenwaage [von JoeM]  
120 Kugeln und eine Balkenwaage Gegeben sind N = 120 Kugeln, die alle gleich aussehen. Eine Kugel ist schwerer, oder leichter, als alle anderen Kugeln. Mit einer Balkenwaage soll die >falsche Kugel
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
Verwandte Links
 
Besucherzähler 2054
 
Aufrufstatistik des Artikels
Insgesamt 22 externe Besuche zwischen 2017.08 und 2017.08 [Anzeigen]
DomainAnzahlProz
http://matheplanet.com29.1%9.1 %
http://google.de940.9%40.9 %
http://google.com418.2%18.2 %
http://google.pt418.2%18.2 %
http://www.kadaza.de14.5%4.5 %
http://images.google.de14.5%4.5 %
http://cn.bing.com14.5%4.5 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 2 Aufrufe in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2017.08.11-2017.08.16 (2x)https://www.google.de/

Häufige Aufrufer in früheren Monaten
Insgesamt 17 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
201702-07 (5x)http://google.de/
2016-2017 (4x)http://google.com/search
2016-2017 (4x)http://google.de/url?sa=t&rct=j&q=
2016.12 (4x)http://google.pt/search?source=android-browser&biw=180&bih=259&ei=JEZQWMnOEsf...

[Seitenanfang]

" Mathematik: 120 Kugeln und eine Balkenwaage " | 75 Kommentare
 
Für den Inhalt der Kommentare sind die Verfasser verantwortlich.

Re: 120 Kugeln und eine Balkenwaage
von dlchnr am Fr. 19. Februar 2016 01:15:14


minimal sind zwei Wägungen notwendig - ich nehme Kugel 1 und 2 und hab' das Glück, das die Waage kippt - ich nehm' dann die potentiell leichtere und vergleich sie mit einer dritten Kugel - kippt die Waage wieder, ist die potentiell leichtere Kugel wirklich leichter, ansonsten ist die potentiell schwerere Kugel wirklich schwerer  biggrin  biggrin  biggrin

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von dlchnr am Fr. 19. Februar 2016 01:19:11


natürlich ist mir klar, dass Du auf die minimale Maximalzahl abzielst, mit der das Rätsel immer gelöst werden kann  biggrin

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von Ex_Mitglied_44668 am Fr. 19. Februar 2016 01:36:13


Hier wie ich vorgehen würde:

Zunächst teile ich die 120 Kugeln in 3 Stapel (Stapel I, Stapel II und Stapel III) je 40 Kugeln auf und wiege zunächst Stapel I gegen Stapel II und dann Stapel II gegen Stapel III. Anhand dieser beiden Wiegungen erkenne sowohl in welchem Stapel die Kugel mit abweichendem Gewicht ist als auch ob diese Kugel leichter oder schwerer ist als alle anderen.

Ich konzentriere mich nun auf den 40er Stapel mit der Kugel mit abweichendem Gewicht und teile diese auf in zwei Stapel mit je 11 Kugeln (Stapel IV und Stapel V) und einen Stapel mit 18 Kugeln (Stapel VI). Nun wiege ich Stapel IV gegen Stapel V und weiss nun wiederum in welchem der drei Stapel sich die gesuchte Kugel befindet.

Befindet sich die Kugel im 18er-Stapel, dann teile ich diesen wiederum in drei 6er-Stapel auf, wiege zwei von denen gegeneinander, und teile denjenigen der drei Stapel, in dem sich die Kugel befindet, in drei Zweier-Stapel ein. Dann werden wieder zwei dieser Stapel gewogen... und nach 6 Wiegungen kenne ich das Ergebnis.

Befindet sich die Kugel im 11er-Stapel, teile ich diesen in zwei 3er-Stapel und einen 5er-Stapel auf. Der 5er-Stapel wiederum würde im nächsten Zug in zwei 2er-Stapel und einen 1er-Stapel aufgeteilt werden...

Insgesamt kenne ich mit dieser Strategie mit Wahrscheinlichkeit 3/10 das Ergebnis nach 5 Zügen und mit Wahrscheinlichkeit 7/10 nach 6 Zügen.

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von Ex_Mitglied_44668 am Fr. 19. Februar 2016 02:01:25


Noch besser:

40->15,15,10
     15->3,3,9
          3->1,1,1
          9->3,3,3
               3->1,1,1
     10->3,3,4
          3->1,1,1
          4->1,1,2
               2->1,1

Dann habe ich die Kugel mit Wahrscheinlichkeit 1/2 nach 5 Zügen und mit Wahrscheinlichkeit 1/2 in 6 Zügen gefunden.

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von Slash am Fr. 19. Februar 2016 02:28:43


Mir gefallen die lustigen Kugeln oben im Bild. smile

Leider ist es bei mir auf der Startseite nicht zu sehen, sondern nur wenn ich den Artikel aufrufe.

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am Fr. 19. Februar 2016 02:28:52


Hallo dlchnr,

Du schreibst:

>natürlich ist mir klar, dass Du auf die minimale Maximalzahl abzielst, mit der das Rätsel immer gelöst werden kann<

Der Ausdruck >minimale Maximalzahl< ist mir unbekannt.

Natürlich ist die Sache so zu verstehen, dass alle Fälle betrachtet werden müssen; es handelt sich nicht um ein >Glücksspiel<.

viele Grüße

JoeM  

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am Fr. 19. Februar 2016 02:50:46


Hallo Slash,

Du schreibst:

>Mir gefallen die lustigen Kugeln oben im Bild.
Leider ist es bei mir auf der Startseite nicht zu sehen, sondern nur wenn ich den Artikel aufrufe.<

Dazu folgendes:

Das finde ich auch schade: Anscheinend habe ich beim Einstellen des Artikels irgendwas >falsch gemacht<

Vielleicht kann das >matroid< noch ändern ?.

Wie das geht, weiss ich nicht; kannst Du dazu was beitragen ?

viele Grüße

JoeM

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am Fr. 19. Februar 2016 03:06:49


Hallo Trumpf,

Du schreibst in Deinem letzten Kommentar:

>Dann habe ich die Kugel mit Wahrscheinlichkeit 1/2 nach 5 Zügen und mit Wahrscheinlichkeit 1/2 in 6 Zügen gefunden.<

Dazu folgendes: Es geht nicht um Wahrscheinlichkeiten.

Es gibt einen absoluten min. Wert aller Wägungen W mit Wahrscheinlichkeit von 1,00 . Damit sind alle Möglichkeiten abgedeckt.

viele Grüße, und viel Spass beim weiteren Rätseln.

JoeM

 

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von Slash am Fr. 19. Februar 2016 04:09:25



Der Link muss so aussehen
<img src=uploads/9/44117_W6.jpg width=245 height=119 alt=''>

Gehe einfach zu "Meine früheren Uploads" und kopiere den Link aus dem Fenster - einfach anklicken, dann geht das Fenster auf. Ist ja eigentlich nur HTML-Code, wenn ich nicht irre. Habe es dir gerade geändert und eine Anfrage geschickt.

Gruß, Slash

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von Martin_Infinite am Fr. 19. Februar 2016 08:43:23


Wieso wird sowas nicht in die Knobelecke gepostet?

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von Ex_Mitglied_44668 am Fr. 19. Februar 2016 08:48:58


@JoeM: Ich verstehe deinen Einwand nicht.
Meine Strategie liefert mit 100%iger Wahrscheinlichkeit das Ergebnis nach spätestens 6 Zügen und mit Wahrscheinlichkeit 50% sogar früher. Letztgenannte Zusatzinformation ist hier auf jeden Fall interessant, wenn man die Qualität anderer Strategien mit der von mir genannten Strategie vergleichen will und wenn man dies nicht berücksichtigt, dann ist die von mir genannte Strategie bereits optimal, denn eine Strategie, die nach 5 Zügen sicher das Ergebnis liefert, gibt es nicht.

Um das Problem interessanter zu machen, würde ich es an deiner Stelle übrigens in folgendem Sinne stochastisch erweitern (andernfalls ist es ja bereits gelöst, wie ich behaupte):

"Es bezeichne T die minimale Anzahl an Versuchen, die nötig sind um das Problem sicher (also mit 100%iger Wahrscheinlichkeit) zu lösen. Man bezeichne eine Strategie S als optimal, wenn folgende Bedingungen erfüllt sind:
- Die Strategie S löst das Problem sicher in höchstens T Versuchen.
- Unter denjenigen Strategien, die das Problem sicher in höchstens T Versuchen lösen, gibt es keine Strategie, welche das Problem mit höherer Wahrscheinlichkeit in höchstens T-1 Versuchen löst als Strategie S.
- Unter denjenigen Strategien, die das Problem sicher in höchstens T Versuchen lösen und mit gleicher Wahrscheinlichkeit wie S in T-1 Versuchen lösen, gibt es keine Strategie, welche das Problem mit höherer Wahrscheinlichkeit in höchstens T-2 Versuchen löst als Strategie S.
- ...
Welches ist eine optimale Strategie?"

Die Existenz einer solchen Strategie dürfte klar sein. Fraglich ist nur, ob die von mir genannte Strategie bereits in diesem Sinne optimal ist.

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von salomeMe am Fr. 19. Februar 2016 09:55:52


Hallo JoeM,

mit zwei Wägungen von jeweils 40 Kugeln pro Waagschale werden die 40 Kugeln bestimmt, die die eine im Gewicht abweichende Kugel enthalten. Dabei ist auch gleich bestimmt ob diese leichter oder schwerer ist.

Jetzt werden noch 4 Wägungen benötigt um die Kugel zu selektieren.

Man kann mit 6 Wägungen diese Knobelaufgabe auch für 243 Kugeln lösen.

Viele Grüße
salomeMe

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am Sa. 20. Februar 2016 00:32:34


Hallo salomeMe,

Du schreibst :

>mit zwei Wägungen von jeweils 40 Kugeln pro Waagschale werden die 40 Kugeln bestimmt, die die eine im Gewicht abweichende Kugel enthalten. Dabei ist auch gleich bestimmt ob diese leichter oder schwerer ist.
Jetzt werden noch 4 Wägungen benötigt um die Kugel zu selektieren.
Man kann mit 6 Wägungen diese Knobelaufgabe auch für 243 Kugeln
lösen.<

Dazu folgendes:

Wenn man so vorgeht, wie Du es hier beschrieben hast, dann benötigt man für 120 Kugeln: 2 + 4 = 6 Wägungen, und
für 243 Kugeln: 2 + 5 = 7 Wägungen (und nicht 6, wie Du schreibst)

Diese Strategie ist nicht die beste !

viele Grüße

JoeM






 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am Sa. 20. Februar 2016 00:38:36


Hallo Trumpf,

Deine Strategie für >120 Kugeln< ist NICHT optimal.

Da geht noch was !

viele Grüße

JoeM

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von Ex_Mitglied_44668 am Sa. 20. Februar 2016 00:47:58


Nicht optimal im Sinne meiner Definition von Optimalität? Oder was genau verstehst du unter "optimal"? Glaubst du eine Strategie zu kennen, die stets mit weniger als 6 Versuchen zum Ziel führt?

MfG
Trumpf

P.S.: Ich heiße übrigens Trumpf, mit diesem Trump möchte ich nichts zu tun haben wink

P.S. 2: salomeMe hat Recht. Mit seiner Strategie benötigt er bei 243 Kugeln immer genau 6 Züge, denn 2+4 ist nicht gleich 7 xD

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am Sa. 20. Februar 2016 01:12:50


Hallo Trumpf,

ich glaube nicht nur, eine Strategie zu kennen, die stets mit weniger, als 6 Versuchen zum Ziel führt.

Ich weiss es:

Meine Strategie führt stets mit weniger, als 6 Versuchen zum Ziel.

Zu 100 %

PS: meine Nachricht an SalomeMe habe ich korrigiert; ich hatte mich verschrieben; es muss natürlich heissen > 2 + 5 = 7 <.

PS: Sorry; mit Trump will ich auch nichts zu tun haben !

viele Grüße

JoeM


 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von Ex_Mitglied_44668 am Sa. 20. Februar 2016 01:21:05


Trotzdem hat er Recht, er benötigt mit seiner Strategie immer genau 6 Züge.

P.S.: Ich hoffe deine Lösung wird nicht so enttäuschend ausfallen, wie deine letzte Lösung des Ziegenproblems (EDIT: siehe Kommentar unter deinem vorhergehenden Artikel) wink

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am Sa. 20. Februar 2016 01:37:41


Hallo Trumpf,

was ich verspreche, kann ich selbstverständlich halten.

Was die 243 Kugeln mit 6 Wägungen angeht:

Meine Strategie kann ich mit 6 Wägungen auf wesentlich mehr, als 243 Kugeln anwenden.

viele Grüße

JoeM


 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am Sa. 20. Februar 2016 01:46:13


Hallo Trumpf,

nebenbei:

was meinst Du mit Deiner Nachricht:

> P.S.: Ich hoffe deine Lösung wird nicht so enttäuschend ausfallen, wie deine letzte Lösung des Ziegenproblems <

Ich habe zwei >Ziegenprobleme< eingestellt; welches von beiden meinst Du ?

Was war für Dich daran so enttäuschend ?

Hast Du dafür andere Lösungen ?

viele Grüße

JoeM

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am Sa. 20. Februar 2016 02:46:56


Hallo fermat63,

Du hast mir eine private Nachricht gesendet.
Das Antworten über die private Nachricht klappt nicht.

Ich hab mir Deinen Link angesehen.

Anscheinend geht es um 12 Kugeln, und 3 Wägungen.

Ja... Mein Artikel hat damit was zu tun.

Könntest Du bitte Deine Fragen hier stellen; dann kann ich besser, und schneller antworten.

viele Grüße

JoeM

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von fermat63 am Sa. 20. Februar 2016 03:04:29


Ich stelle mal meine Frage an JoeM über PM(wie von ihm gewünscht) hier als Kommentar ein:

Hallo JoeM

Kurze Frage:
Hat das Rätsel mit Informations Theorie zu tun, also dem Shannon information content und entropy, wie in diesem Video mit David McKay "weighing problem with 12 balls" (etwa ab Min. 21):
 hier
Ein Buch von David McKay ist auch zum konstenfreien download als pdf erhältlich(nur zum eigenen Gebrauch, nicht zum Ausdrucken oder Kopieren, Weiterleiten ! Dieses ist im Copyright noch ausgeführt).

Viele Grüsse
fermat63  

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am Sa. 20. Februar 2016 03:14:51


Hallo Trumpf,

Dein Kommentar lautet u.a.:

>dann ist die von mir genannte Strategie bereits optimal, denn eine Strategie, die nach 5 Zügen sicher das Ergebnis liefert, gibt es nicht.
Um das Problem interessanter zu machen, würde ich es an deiner Stelle übrigens in folgendem Sinne stochastisch erweitern (andernfalls ist es ja bereits gelöst, wie ich behaupte)....<

Dazu folgendes:

1) Deine Strategie ist nicht optimal.

2) Deine Behauptung >gelöst< ist falsch.

3) Dein Ansatz > ... eine Strategie, die nach 5 Zügen sicher das
Ergebnis liefert, gibt es nicht <, ist ebenfalls falsch.

4) Dein Ansatz, das Problem interessanter zu machen durch eine stochastische Erweiterung ist nicht interessant.

viele Grüße

JoeM



 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von dlchnr am Sa. 20. Februar 2016 03:41:42


Also der Start mit 3 Gruppen a 40 Kugeln dürfte suboptimal sein.
Besser dürften 3 etwas kleinere Gruppen sein, die mittels zweier Wägungen eine schwerere oder leichtere Kugel in einer der drei Gruppen ergeben oder aber eine unbestimmt abweichende Kugel in der Restgruppe, die aber mit drei weiteren Wägungen lösbar ist.
z.B.:
120->->37,37,37 (9)
       9->->3,3,3
            3->1,1,1
      37-> ...

Vielleicht hat ja jemand eine Idee, wie man eine Restgruppe > 9 (also 12 oder 15 oder 18 ... mit drei Wägungen noch lösen kann, so dass der alternative Zweig nur noch 36 oder 35 oder 34 ... Kugeln abhandeln muss?

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von Ex_Mitglied_44668 am Sa. 20. Februar 2016 03:44:08


Hallo JoeM,

zu 1): Das stimmt, ich kenne die Lösung inzwischen. Das Problem ist leider nicht neu, man findet die Lösung im WWW. Ich habe übrigens geschrieben, dass es fraglich ist, ob meine Lösung optimal ist.

zu 2) & 3): Das hast du aus dem Kontext gerissen, ich hatte das als Hypothese gekennzeichnet ("wie ich behaupte").

zu 4): Das sehe ich anders. Es ist nämlich nicht gerade klar, dass die Lösung, auf die du hinaus möchtest, auch in diesem Sinne optimal ist.

MfG
Trumpf

P.S.: Hast du meine Kritik an deiner Lösung zum Ziegenproblem gelesen?

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am Sa. 20. Februar 2016 03:56:59


Hallo fermat63,

vielen Dank für Deinen Link >mit 12 Kugeln und 3 Wägungen<

Bei K = 12 Kugeln sind W = 3 Wägungen erforderlich.

Ich finde: Der Artikel ist >zu kompliziert<; es geht einfacher:

Mein Algorithmus ist allgemein, und deckt für max. K  min. Wägungen W ab.

Beispiel: Für max. K = 12 Kugeln sind min. W = 3 Wägungen erforderlich.
Beispiel: Für max. K = 120 Kugeln sind min. W = 5 Wägungen erforderlich.

viele Grüße

JoeM

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am Sa. 20. Februar 2016 04:10:47


Hallo Trumpf,

Deine Kritik zum Ziegenproblem habe ich nicht gelesen.

Ansonsten:

Ich habe das >Kugelproblem< bereits vor ca. 21 Jahren schon allgemein gelöst.
Da gab es noch kein www.
Nebenbei: wie viele Wägungen sind für 9840 Kugeln erforderlich ?
 
viele Grüße

JoeM

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von Ex_Mitglied_44668 am Sa. 20. Februar 2016 04:12:35


Neun.

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am Sa. 20. Februar 2016 04:29:58


Hallo Trumpf,

na endlich;

N = 3 Kugeln: W = 2 Wägungen

N = (3+1)*3 = 12 Kugeln: W = 3

N = (12+1)*3 = 39 Kugeln: W = 4

N = (39+1)*3 = 120 Kugeln: W = 5

N = (120+1)*3 = 363 Kugeln: W = 6

usw.

Wie erfolgt die Wägung z.B. für N = 120 Kugeln ?

viele Grüße

JoeM

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von Ex_Mitglied_44668 am Sa. 20. Februar 2016 04:43:19


Es konkrekt aufzuschreiben ist mir zu mühsam. Die Lösung lässt sich recht einfach aus dieser Lösung für das selbe Problem mit 12 Kugeln ableiten (<Link>).

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am Sa. 20. Februar 2016 04:46:15


Hallo dlchnr,

die Aufgabe ist nur dann optimal lösbar, wenn man zu Anfang 2- mal 40 Kugeln abwiegt.

Alles andere geht nicht.

viele Grüße

JoeM

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am Sa. 20. Februar 2016 04:58:37


Hallo Trumpf,

Du schreibst:

>Es konkret aufzuschreiben ist mir zu mühsam. Die Lösung lässt sich recht einfach aus dieser Lösung für das selbe Problem mit 12 Kugeln ableiten (<Link>).<

Dazu meine Meinung:

Wie soll man aus diesem Link mit 12 Kugeln auf 120 Kugeln schliessen ?

Kannst Du das näher erklären ?

Ansonsten:

In meiner Aufgabe stand noch folgendes:

--  angenommen: Die Verteilung der Kugeln ist pro Wägung stets gleich.
     Man kennt nach Ablauf von W Wägungen nur den jeweiligen Ausschlag der
     Balkenwaage; Beispiel :

1. Wägung:  ▼ ( linke Waagschale ist schwerer, und geht nach unten )

2. Wägung:  ▲ ( linke Waagschale ist leichter, und geht nach oben )

3. Wägung : ▬  ( beide Schalen sind im Gleichgewicht )

4. Wägung:  ▲ ( linke Waagschale ist leichter, und geht nach oben )

etc.

Wie könnte so eine stets gleiche Verteilung der Kugeln pro Wägung aussehen, um nach W Wägungen etwa mit der Information  > ▼ ▲ ▬ ▲ ….. < die >falsche Kugel< zu identifizieren, incl. Gewichtsangabe (schwerer / leichter) ?

Hast Du dazu eine Idee ?

viele Grüße

JoeM

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am Sa. 20. Februar 2016 05:18:49


Hallo Trumpf,

zu Deinem Kommentar:

>zu 4): Das sehe ich anders. Es ist nämlich nicht gerade klar, dass die Lösung, auf die du hinaus möchtest, auch in diesem Sinne optimal ist.<

Das sehe ich anders.

Meine Strategie ist optimal; es gibt keine bessere.

viele Grüße

JoeM

 

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von Ex_Mitglied_44668 am Sa. 20. Februar 2016 05:30:49


Ist das wirklich so klar? Theoretisch kann man mit 5 Wiegevorgänge 243 verschiedene Fälle unterscheiden, nicht nur 240.

Kannst du beweisen, dass es keine Strategie geben kann, welche mit positiver Wahrscheinlichkeit nur 4 Versuche benötigt?

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von salomeMe am Sa. 20. Februar 2016 18:44:52


Hallo JoeM,

zu Deiner Antwort auf meinen Vorschlag.
Wenn Deine Aufgabenstellung analog mit 243 Kugeln gestellt worden wäre, hätte ich natürlich 2 mal je 81 Kugel je Schale abgewogen. Danach je einmal je 27, 9, 3, 1 und wäre auch mit insgesamt 6 Wägungen fertig.

Wahrscheinlich könnte man mit 6 Wägungen sogar noch etwas mehr Kugeln behandeln, falls sich nach 2 Wägungen ergibt, dass die 243 gewogenen Kugel alle das gleiche Gewicht haben. Hätte man noch 4 Wägungen um aus dem Rest die eine herauszufiltern. Der Rest wären wohl 30, also zusammen 273 Kugeln.

Mit meiner Strategie könnte ich mit 5 Wägungen aber nur 91 Kugeln sicher filtern.

Könnte es sein, dass vergessen wurde, dass der Rest (den ich eingeführt habe) eine Kugel enthält von der noch nicht bekannt ist, ob sie leichter oder schwerer ist?

Beste Grüße
salomeMe




 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am So. 21. Februar 2016 00:11:47


Hallo salomeMe,

mit Deiner Methode kann man nach 2, 3, 4, 5, 6, ..... Wägungen
3, 9, 27, 81, 243,...... Kugeln erfassen.

Die optimale Methode bedeutet aber:
nach 2, 3, 4, 5, 6, ..... Wägungen kann man 3, 12, 39, 120, 363,...... Kugeln erfassen.

kleiner Tipp:

die 1. Wägung sieht aus, wie bei Dir; alle weiteren Wägungen verlaufen anders, als bei Deiner Vorgehensweise.

viele Grüße

JoeM


 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von Ex_Mitglied_44668 am So. 21. Februar 2016 00:56:45


Man kann die von JoeM beabsichtigte Lösung für 0,5*((3^n)-3) Kugeln (für n grössergleich 3) aus der von mir zuvor verlinkten Lösung für 12 Kugeln ableiten. Ich poste jetzt mal eine Beispiellösung für 120 Kugeln in der Hoffnung damit die Randdiskussionen, die sich hier ergeben haben, etwas zu befeuern.


Ich notiere die Zahlen von 1 bis 120. Ich beginne damit der Zahl 1 ihre eindeutige Darstellung als Summe/Differenz einer Teilmenge der Dreierpotenzen von Grad 0 bis Grad 4 zuzuordnen [1 = 1*3^0 + 0*3^1 + 0*3^2 + 0*3^3 + 0*3^4]. Dann notiere ich für die 1 ein positives Vorzeichen sowie einen fünfstelligen Vektor, welcher die obige Darstellung repräsentiert, d.h.
1<->(+,(1,0,0,0,0)).
Dann ändere ich jede "1" in diesem Vektor in eine "-1" und addiere zu allen anderen Komponenten eine 1, es ergibt sich also der Vektor
(-1,1,1,1,1),
dieser Vektor repräsentiert offenbar die Zahl 119 [119 = (-1)*3^0 + 1*3^1 + 1*3^2 + 1*3^3 + 1*3^4], also notiere ich (erneut mit positivem Vorzeichen, da 119 positiv ist)
119<->(+,(-1,1,1,1,1)).
Ich führe die gleiche Prozedur noch einmal durch und erhalte den Vektor
(0,-1,-1,-1,-1),
dieser repräsentiert die Zahl -120 [-120 = 0*3^0 + (-1)*3^1 + (-1)*3^2 + (-1)*3^3 + (-1)*3^4], also notiere nun (diesmal mit negativem Vorzeichen, da -120 negativ ist)
120<->(-,(0,-1,-1,-1,-1)).

Im nächsten Durchgang beginne ich mit der kleinsten noch nicht betrachteten Zahl. So erhalte ich beispielsweise im zweiten Durchgang die Verknüpfungen
2<->(+,(-1,1,0,0,0)),
114<->(+(0,-1,1,1,1)),
116<->(-(1,0,-1,-1,-1)).

Nach 40 Durchgängen habe ich jeder Zahl einen Vektor zugeordnet. Die Kugeln werden nun durchnummeriert mit den Zahlen von 1 bis 120. Nun können die einzelnen Wiegevorgänge folgendermaßen organisiert werden: Im k-ten der fünf Wiegeschritte werden genau diejenigen Kugeln, die Eintrag "-1" in der k-ten Komponente ihres Zahlenvektors tragen, auf die linke Seite der Waage gelegt und genau diejenigen Kugeln, die Eintrag "1" in der k-ten Komponente ihres Zahlenvektors tragen, auf die rechte Seite der Waage gelegt (also jeweils genau 40, je eine aus jedem 3er-Zyklus).


Nun werden die fünf Wiegevorgänge durchgeführt, die Ergebnisse werden notiert. Danach wird für den k-ten Wiegeschritt eine "-3^(k-1)" notiert, falls die Waage links nach unten ausschlug, eine "0" falls die Waage ausgeglichen war und eine "3^(k-1)", falls die Waage rechts nach unten ausschlug und diese fünf Zahlen werden dann addiert. Der Betrag dieser Summe gibt nun die Nummer der Kugel mit abweichendem Gewicht an und das Vorzeichen der Summe gibt an, ob die Kugel leichter oder schwerer ist als die anderen: Stimmt das Vorzeichen der Summe mit dem Vorzeichen überein, mit welchem die Nummer der Kugel gekennzeichnet wurde, so ist die Kugel schwerer als alle anderen und sind die Vorzeichen verschieden, so ist die Kugel leichter.

EDIT: Wie von salomeMe in seinem nächsten Beitrag angemerkt, ist diese Lösung nur dann zulässig, wenn man annimmt die Kugeln nummerieren zu können bzw. wenn man (durch spezielle Sortierungen der Kugeln außerhalb >und auch auf der Waage<) dazu in der Lage ist zu jedem Zeitpunkt für einzelne Kugeln zu wissen, auf welchen Seiten der Waage sie bisher in welcher Reihenfolge gelegen haben. Dem Einwand, dass dies nicht im Sinne der Aufgabenstellung ist ("Kugeln, die alle gleich aussehen" - Warum sollte das in der Aufgabenstellung erwähnt werden, wenn es letztendlich erlaubt wäre die optische Ununterscheidbarkeit der Kugeln trickreich, z.B. durch Nummerierung, zu umgehen?), muss ich mich anschließen.

EDIT: Selbiges gilt selbstverständlich für BEIDE im Folgenden (am 22.02 um 01:06 und um 02:37) vom Artikelautor geposteten Lösungen, welche übrigens sehr viel uneleganter sind als diese Lösung (sorry, aber das musste jetzt einfach sein biggrin ).

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am So. 21. Februar 2016 01:52:01


Hallo Trumpf,

Du schreibst:

>Ist das wirklich so klar? Theoretisch kann man mit 5 Wiegevorgänge 243 verschiedene Fälle unterscheiden, nicht nur 240.
Kannst du beweisen, dass es keine Strategie geben kann, welche mit positiver Wahrscheinlichkeit nur 4 Versuche benötigt?<

Ich sehe das so:

Bei 5 Wägungen gibt es 5^3 - 1 = 242 Möglichkeiten.
Eine Möglichkeit muss man abziehen (alle Kugeln gleich schwer)
Für 120 Kugeln ( eine leichter/schwerer) gibt es 120*2 =240 Möglichkeiten.

Nun könnte man meinen, die Sache sollte auch für 121 Kugeln funktionieren: 121*2 = 242 Möglichkeiten.

Aber das funktioniert nicht;

Beispiel 13 Kugeln ( statt 12 Kugeln ):

Hier gilt: 3 Wägungen; d.h. 3^3 - 1 = 26 Möglichkeiten; sowie
13*2 = 26 Möglichkeiten für schwer/leicht.

Bei 13 Kugeln, und 3 Wägungen kann man zwar die >falsche Kugel< identifizieren, aber man kann nicht sagen, ob diese Kugel leichter oder schwerer ist.
Es liegt wohl daran, dass 26 nicht durch 3 teilbar ist.

Was meinst Du mit >positiver Wahrscheinlichkeit<

viele Grüße

JoeM


 

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von Ex_Mitglied_44668 am So. 21. Februar 2016 02:23:23


Ich meine damit eine Strategie, bei der die zukünftigen Wiegevorgänge (sowie auch deren Anzahl) vom Ausgang vergangener sowie des gegenwärtigen Wiegevorgangs abhängen dürfen und für die ein Fall existiert, in dem sie schon nach 4 Versuchen das Ergebnis liefern (bzw. nach 2 Versuchen im 12er-Beispiel). Ich empfinde die Nichtexistenz solcher Strategien nicht als trivial. Und schon deswegen ist diese Erweiterung der Fragestellung für mich spannend.

Es muss sich dabei natürlich um eine Strategie handeln, für welche das Kriterium einer "stets gleiche[n] Verteilung der Kugeln pro Wägung" nicht erfüllt ist.

Wenn man den allgemeinen Fall betrachtet (sprich: wenn die Anzahl der Kugeln nicht gleich 0,5*(3^n-3) für ein n groessergleich 3 sein muss), dann dürfte übrigens leicht zu erkennen sein, dass diese Erweiterung der Fragestellung interessant ist. Und selbst wenn sich herausstellen sollte, dass die bezüglich dieser Erweiterung optimale Strategie in den genannten Spezialfällen dieselbe ist, wie in der von dir formulierten Problemstellung, ändert das für mich nichts daran, dass die erweiterte Problemstellung auch in diesen Fällen interessant ist. Auch dann wäre es nämlich immer noch eine allgemeinere Problemstellung.

Um es überspitzt zu formulieren: Dass die Zahl 1 das Problem "3-2" löst, heisst nicht, dass nicht andere Fragestellungen, die ebenfalls durch die Zahl 1 gelöst werden, interessanter sein können. wink

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am So. 21. Februar 2016 03:46:07


Hallo Trumpf,

ich habe gerade Deinen Kommentar zum meinem >Ziegenproblem< gelesen:

>P.S.: Ich hoffe deine Lösung wird nicht so enttäuschend ausfallen, wie deine letzte Lösung des Ziegenproblems (EDIT: siehe Kommentar unter deinem vorhergehenden Artikel)<

Du hast anscheinend mein >Ziegenproblem< falsch interpretiert;

siehe dazu meinen Kommentar zum Artikel >Ziegenproblem<.

Vielleicht kannst Du jetzt das >Ziegenproblem< lösen ?!

viele Grüße

JoeM

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am So. 21. Februar 2016 04:15:09


Hallo SalomeMe,

es gibt verschiedene Möglichkeiten, das Kugelproblem zu lösen.

Ich finde: Die eleganteste Methode ist folgende:

Nach W Wägungen hat man bei jeweils gleicher Verteilung der Kugeln nur z.B. die Info:

> ▼  ▲ ▬  ▲ ….. <

Beispiel mit N = 12 Kugeln, und W = 3 Wägungen:

Man kennt nach 3 Wägungen nur den jeweilige Ausschlag der Balkenwaage;
dann kann man die >falsche Kugel< identifizieren; etwa so:



beste Grüße

JoeM

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von Ex_Mitglied_44668 am So. 21. Februar 2016 04:46:36


"Vielleicht kannst Du jetzt das >Ziegenproblem< lösen ?!"

Dazu müsstest du zunächst ein vernünftiges Problem stellen. wink

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am So. 21. Februar 2016 05:08:11


Hallo Trumpf,

ich halte fest: Du hast meine Aufgabe (Ziegenproblem) leider nicht verstanden !
 
Zum Trost: Du bist nicht der Einzige.

viele Grüße

JoeM

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von Ex_Mitglied_44668 am So. 21. Februar 2016 05:11:58


Was hälst du davon in der Kommentarspalte des entsprechenden Artikel konkret auf meine Einwände einzugehen, statt hier herumzuschimpfen? Als Verfasser des Artikels solltest du dich dazu verpflichtet fühlen, ernsthaft zu versuchen Missverständnisse aufzuklären und auf handfeste Kritik angemessen zu reagieren. Das scheint bei dir aber leider nicht der Fall zu sein.

Ich werde in der Kommentarspalte dieses Artikels ab jetzt übrigens nur noch auf Anmerkungen mit Bezug zu diesem Artikel reagieren, so wie sich das ja eigentlich gehört (bzw. überhaupt nicht mehr, siehe unten).

EDIT:
Zu deinem Folgekommentar: "Ausreden"?! Wenn das dein Ernst ist, ist das eine Bestätigung dessen, was ich gerade geschrieben habe, wie sie klarer kaum sein könnte.

EDIT:
Auch aus der Kommentarspalte dieses Artikels halte ich mich von jetzt an vielleicht besser heraus.

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am So. 21. Februar 2016 05:21:19


Hallo Trumpf,

ich schimpf nicht herum;

ich halte nur fest, dass Du >mit Ausreden< keine Lösung gefunden hast.

Es sei denn; Du lieferst noch eine.

viele Grüße

JoeM

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von salomeMe am So. 21. Februar 2016 18:56:34


Hallo JoeM,

nehmen wir mal an, dass eine Strategie für 120 Kugeln existiert, die nach 5 Wägungen mit beginnenden zwei 40-er Wägungen zum Ziel führt.

Behauptung:
Dann muss auch eine Strategie für 130 Kugeln existieren, die mit 5 Wägungen zum Ziel führt.

Beweis:
Bei 130 Kugeln und beginnenden zwei 40-er Wägungen, kann es jetzt passieren, dass zweimal Gleichgewicht erzielt wird, die gesuchte Kugel also unter den 10 nicht gewogenen Kugeln ist. Mit den noch ausstehenden 3 Wägemöglichkeiten kann man mit traditionellen Mitteln die abweichende Kugel eindeutig bestimmen und auch, ob sie leichter oder schwerer ist.

Bemerkung:
Ob so etwas wie Durchnummerieren von Kugeln und Vektorzuweisungen zu den Nummern, noch etwas mit Knobeln zu tun hat, erscheint mir fraglich. Man sollte es schon ohne Manipulationen an den Versuchsgegenständen hinbekommen können.

Andererseits scheint mir aus mathematischer Sicht das Aufzeigen einer besseren Strategie als der, die bisher allgemein als optimale angesehen wurde, recht interessant. Sie wäre vielleicht als normaler Artikel auch veröffentlicht, wohl aber nicht so beachtet worden.

Ich warte jetzt nur noch auf die Auflösung und hoffe, dass ich angenehm überrascht werde.

Viele Grüße
salomeMe

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am Mo. 22. Februar 2016 01:06:46


Hallo salomeMe,

hier meine Lösung für N = 120 Kugeln, und W = 5 Wägungen.
Die Lösung habe ich rekursiv, beginnend mit N = 12 Kugeln (3 Wägungen)
entwickelt.
Die Lösung ist einfach gehalten, und kann auch von Schülern leicht nachvollzogen werden. Der Algorithmus gilt allgemein, und ist weiterführend rekursiv auch für
N = 363 (W = 6), N = 1092 (W = 7)...... usw. anwendbar.

Lösung der Aufgabe > 120 Kugeln und eine Balkenwaage < :

Folgendes Verfahren lässt sich beliebig anwenden auf  3, 12, 39, 120, 363, 1092 …. …..Kugeln; eine Kugel ist jeweils leichter, oder schwerer, als alle anderen Kugeln:


A) 12 Kugeln,  1 – 12  (3 Wägungen erforderlich) ;   12 = (3 + 1) * 3  

Bei der 1. Wägung sind in jede Waagschale 1/3 von 12 = 4 Kugeln zu geben:

1 2 3 4         5 6 7 8            ( 9 10 11 12  außerhalb der Waage )  

1. Wägung ohne Ausschlag

1 2 3 4         5 6 7 8              gleich

2. Wägung (wiege 3 Kugeln aus der 1. Wägung mit 3 Kugeln aus dem Rest)

1 2 3           9 10 11          

2 a) kein Ausschlag: Kugel 12 ist leicht oder schwer; eine weitere Wägung

2 b) Ausschlag: Kugel befindet sich unter 9, 10, 11; eine weitere Wägung
(Kugel 9 gegen Kugel 10 aufwiegen)

1. Wägung mit Ausschlag

1 2 3 4          5 6 7 8             auf/ab ; der andere Fall ab/auf ist äquivalent

2. Wägung (tausche eine Kugel li/re, und den Rest auf einer Seite gegen neutrale Kugeln)

5 2 3 4          1 9 10 11

2 a)  kein Ausschlag

5 2 3 4          1 9 10 11         gleich            

Folge: Eine Kugel aus  6 7 8, ist  schwer (3 Kugeln, 1 weitere Wägung)

2 b)  Ausschlag auf/ab

5 2 3 4          1 9 10 11         auf/ab            

Folge: Eine Kugel aus  2 3 4, ist leicht (3 Kugeln, 1 weitere Wägung)

2c)  Ausschlag ab/auf

5 2 3 4          1 9 10 11         ab/auf            

Folge: die Kugel 1 ist leicht, oder die Kugel 5 ist schwer (1 weitere Wägung)


B) 39 Kugeln, 1 – 39 (4 Wägungen erforderlich) ;    39 = (12 + 1) * 3

1. Wägung (in jede Waagschale sind 1/3 von 39 = 13 Kugeln zu geben):

1 2 3 4 5 6 7 8 9 10 11 12 13            14 15 16 17 18 19 20 21 22 23 24 25 26          

1. Wägung ohne Ausschlag

1 2 3 4 5 6 7 8 9 10 11 12 13            14 15 16 17 18 19 20 21 22 23 24 25 26
gleich

2. Wägung (wiege 9 Kugeln der 1. Wägung mit 9 Kugeln aus dem Rest)

1 2 3 4 5 6 7 8 9                            27 28 29 30 31 32 33 34 35  

2 a) kein Ausschlag: Kugel ist unter den restlichen 4 Kugeln 36 -39;
siehe A) 12 Kugeln

2 b) Ausschlag: restliche Wägungen dritteln.

1.Wägung mit Ausschlag

1 2 3 4 5 6 7 8 9 10 11 12 13            14 15 16 17 18 19 20 21 22 23 24 25 26
auf/ab

2.Wägung (tausche 4 Kugeln li/re, und den Rest auf einer Seite gegen neutrale Kugeln)

14 15 16 17 5 6 7 8 9 10 11 12 13         1 2 3 4 27 28 29 30 31 32 33 34 35

2 a) kein Ausschlag

14 15 16 17 5 6 7 8 9 10 11 12 13         1 2 3 4 27 28 29 30 31 32 33 34 35
gleich

Folge: Eine der Kugeln 18 19 20 21 22 23 24 25 26,  ist schwer
(9 Kugeln, 2 weitere Wägungen)

2 b) Ausschlag auf/ab
 
14 15 16 17 5 6 7 8 9 10 11 12 13         1 2 3 4 27 28 29 30 31 32 33 34 35
auf/ab

Folge: Eine der  Kugeln 5 6 7 8 9 10 11 12 13,  ist leicht (9 Kugeln, 2 weitere Wägungen)

2 c) Ausschlag ab/auf

14 15 16 17 5 6 7 8 9 10 11 12 13         1 2 3 4 27 28 29 30 31 32 33 34 35
ab/auf

Folge: 1 2 3 4          14 15 16 17           auf/ab

Dies ist genau folgender Fall: 1. Wägung mit Ausschlag für A) 12 Kugeln:
2 weitere Wägungen sind erforderlich (rekursive Anwendung von A) = 12 Kugeln).


C) 120 Kugeln, 1 – 120 (5 Wägungen erforderlich) ;   120 = (39 + 1) * 3

1. Wägung (in jede Waagschale sind 1/3 von 120 = 40 Kugeln zu geben):

Kugeln 1 - 40                                    Kugeln 41 – 80

1. Wägung ohne Ausschlag

Kugeln 1 - 40                                    Kugeln 41 – 80      gleich

2. Wägung (wiege 27 Kugeln der 1. Wägung mit 27 Kugeln aus dem Rest)

Kugeln 1 – 27                                    Kugeln  81 – 107      

2 a) kein Ausschlag: Kugel ist unter den restlichen 13 Kugeln 108 -120;
siehe B) 39 Kugeln

2 b) Ausschlag: restliche Wägungen dritteln

1. Wägung mit Ausschlag

Kugeln 1 - 40                                    Kugeln 41 – 80      auf/ab

2.Wägung (tausche 13 Kugeln li/re, und den Rest auf einer Seite gegen neutrale Kugeln)

Kugeln 41 – 53, 14 – 40                       Kugeln 1 – 13, 81 – 93

2 a) kein Ausschlag

Kugeln 41 – 53, 14 – 40                       Kugeln 1 – 13, 81 – 93   gleich

Folge: Eine der Kugeln 54 bis 80 ist schwer (27 Kugeln, 3 weitere Wägungen)

2 b) Ausschlag auf/ab

Kugeln 41 – 53, 14 – 40                       Kugeln 1 – 13, 81 – 93    auf/ab

Folge: Eine der  Kugeln 14 bis 40 ist leicht (27 Kugeln, 3 weitere Wägungen)

2 c) Ausschlag ab/auf

Kugeln 41 – 53, 14 – 40                       Kugeln 1 – 13, 81 – 93    ab/auf

Folge:

Kugeln 1 – 13                                    Kugeln 41 – 53               auf/ab

Dies ist genau folgender Fall: 1. Wägung mit Ausschlag für B) 39 Kugeln: 3 weitere Wägungen sind erforderlich (rekursive Anwendung von A) = 12 und B) = 39 Kugeln).

Das Verfahren lässt sich somit auf jede Anzahl von Kugeln (K = 363 etc.) anwenden.

viel Spass, und beste Grüße

JoeM





 
 

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am Mo. 22. Februar 2016 02:37:23


Hallo salomeMe,

im letzten Teil meiner Aufgabe wurde nach folgendem gefragt:

--  angenommen: Die Verteilung der Kugeln ist pro Wägung stets gleich.
     Man kennt nach Ablauf von W Wägungen nur den jeweiligen Ausschlag der
     Balkenwaage; Beispiel :

1. Wägung:  ▼ ( linke Waagschale ist schwerer, und geht nach unten )

2. Wägung:  ▲ ( linke Waagschale ist leichter, und geht nach oben )

3. Wägung : ▬  ( beide Schalen sind im Gleichgewicht )

4. Wägung:  ▲ ( linke Waagschale ist leichter, und geht nach oben )

etc.
 
Wie könnte so eine stets gleiche Verteilung der Kugeln pro Wägung aussehen, um nach W Wägungen etwa mit der Information  > ▼ ▲ ▬ ▲ ….. < die >falsche Kugel< zu identifizieren, incl. Gewichtsangabe (schwerer / leichter) ?

Meine Antwort lautet:

Ja, es gibt so eine Verteilung, die zum Ziel führt:











Es genügt, nach 5 Wägungen den jeweiligen Ausschlag der Balkenwaage zu kennen,
um die >falsche Kugel< incl. deren Gewicht (schwerer/leichter) zu identifizieren.

Du kannst das gerne testen; es funktioniert immer.

beste Grüße

JoeM





 




 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von trunx am Mo. 22. Februar 2016 09:41:55


hallo joem,

wie trumpf bereits gesagt hat, fehlt der beweis dafür, dass die von dir angegebene (aber wie ebenfalls bereits gesagt wurde, allgemein bekannte) strategie optimal ist. das wäre einen artikel wert gewesen, für diskussionen ist eig das forum, hier konkret die 'knobelecke' gedacht. der satz 'Meine Strategie ist optimal; es gibt keine bessere.' ist kein solcher beweis, übrigens auch nicht die wiederholte erklärung der strategie. sie wurde als EINE lösung des wägeproblems verstanden, dass es DIE lösung sein soll, gerade nicht. auch wenn vllt niemand eine bessere strategie auf lager hat, ist das kein beweis. insofern hältst du nicht was du versprichst. falls du noch nicht weisst, worauf ich hinaus will, schau mal hier.

probier es nochmal, ich bin sicher, du kannst das besser.

bye trunx

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von salomeMe am Mo. 22. Februar 2016 10:22:06


Hallo JoeM,

habe die beiden Auflösungsvarianten schnell mal überflogen. Danke für die Mühe, die dafür erforderlich war. Die erste Variante scheint ja eventuell ohne Nummerierung der Kugeln auszukommen, wenn die Waagschalen geeignet für die Separierung der entsprechenden Kugelteilmengen ausgelegt sind. Schüler mögen mit dem Wägealgorithmus eventuell zu recht kommen. Ich würde lieber eine Wägung mehr machen, wenn ich mir sicher sein wollte keinen Fehler gemacht zu haben.

Werde mir heute Abend mehr Zeit nehmen und eine nicht ganz so oberflächliche Meinung zu den Lösungsvarianten bilden.

Da beide Varianten die 120 Kugel nach 2 Wägungen nicht auf 40 Kugeln einschränken, wobei schon bekannt ist, dass die abweichende Kugel leichter oder schwerer ist, hat mein Gedanke die mögliche Anzahl auf 130 Kugeln auszudehnen, keinen Sinn gehabt.

Viele Grüße
salomeMe

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von salomeMe am Mo. 22. Februar 2016 21:42:52


Hallo JoeM,

zu Deinem Kommentar vom Mo. 22. Februar 2016 01:06:46

A) 12 Kugeln sieht ok aus

B) 39 Kugeln sieht ok aus

C) 120 Kugeln...

1. Wägung ohne Ausschlag ok
1. Wägung mit Ausschlag

Kugeln 1 - 40                                    Kugeln 41 – 80      auf/ab

2.Wägung (tausche 13 Kugeln li/re, und den Rest auf einer Seite gegen neutrale Kugeln)

Kugeln 41 – 53, 14 – 40                       Kugeln 1 – 13, 81 – 93
fed-Code einblenden

2 a) kein Ausschlag

Kugeln 41 – 53, 14 – 40                       Kugeln 1 – 13, 81 – 93   gleich



fed-Code einblenden

Folge: Eine der Kugeln 54 bis 80 ist schwer (27 Kugeln, 3 weitere Wägungen)

2 b) Ausschlag auf/ab

Kugeln 41 – 53, 14 – 40                       Kugeln 1 – 13, 81 – 93    auf/ab
Kugeln 41 – 53, 14 – 40                       Kugeln 1 – 13, 81 – 107   auf/ab

Folge: Eine der  Kugeln 14 bis 40 ist leicht (27 Kugeln, 3 weitere Wägungen)

2 c) Ausschlag ab/auf

Kugeln 41 – 53, 14 – 40                       Kugeln 1 – 13, 81 – 93    ab/auf
Kugeln 41 – 53, 14 – 40                       Kugeln 1 – 13, 81 – 107    ab/auf

Folge:

Kugeln 1 – 13                                    Kugeln 41 – 53               auf/ab

Dies ist genau folgender Fall: 1. Wägung mit Ausschlag für B) 39 Kugeln: 3 weitere Wägungen sind erforderlich (rekursive Anwendung von A) = 12 und B) = 39 Kugeln).

Das Verfahren lässt sich somit auf jede Anzahl von Kugeln (K = 363 etc.) anwenden.
fed-Code einblenden
de.math.wikia.com/wiki/Waage_und_12_Kugeln%2C_L%C3%B6sung_und_Diskussion

Ob das für n>3 aber eine optimale Strategie bleibt, ist fraglich. Aber Du wirst dort auch ein Argument dafür finden, von dem ich aber nicht 100% überzeugt bin.


Mit dem statischen Lösungsbeispiel werde ich mich nicht mehr beschäftigen. Da scheint mir auf den ersten Blick der Vorschlag von @Trumpf vom So. 21. Februar 2016 00:56:45 ein allgemeinerer Ansatz zu sein, wenn ich auch erst den Anfang davon beginne zu verstehen.

Wenn Du die Vorschläge von @trunx vom Mo. 22. Februar 2016 09:41:55 beherzigst, wirst Du künftig besser verstanden werden.
 Wenn man sich intensiv und vor Allem lange mit einem mathematischen Problem beschäftigt, vergisst man mit der Zeit oft auf welchem Wege man zu den Ergebnissen gekommen ist oder man verliert das Gefühl das Wichtige vom Unwichtigen trennen zu können. Funktionierende Beispiele sind zwar gut und schön, aber schöner ist erklären zu können, wie man auf das Beispiel gekommen ist. Dann wird man von Außenstehenden manchmal auch verstanden.

Viel Erfolg beim Beweisen Deiner Aussagen!

Beste Grüße
salomeMe

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am Di. 23. Februar 2016 00:14:40


Hallo salomeMe,

Du schreibst ... > Flüchtigkeitsfehler.... < bei N = 120 Kugeln.

Vielen Dank für Deinen Hinweis; da ist mir in der Eile eine Fehler unterlaufen; der aber keinen Einfluss auf die Gesamtlösung hat.
Natürlich müssen in beiden Schalen gleich viele Kugeln sein.

mit den besten Grüßen

JoeM

 





 

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am Di. 23. Februar 2016 01:25:37


Hallo salomeMe,

vielen Dank für Deinen Link (12 Kugeln, und 3 Wägungen).

Bei 12 Kugeln gibt es 24 Mögl. dafür, dass eine Kugel schwerer, oder leichter ist.
Mit 3 Wägungen kann man 3^3 – 1 = 26 Möglichkeiten abdecken (eine Möglichkeit muss man abziehen; das wäre der Fall, dass alle Kugeln gleich schwer sind ).  

Nun könnte man meinen, dass man auch 13 Kugeln mit 3 Wägungen  erfassen kann
(13 * 2 = 26 Möglichkeiten).

In Deinem Link wird aber bewiesen, dass das nicht geht:

Es funktioniert für N = (3^3 – 3)/2 = 12 Kugeln mit 3 Wägungen.;
Für N = 13 Kugeln kann man nach 3 Wägungen nur die >falsche Kugel< identifizieren, aber ohne Gewichtsangabe.

Da bei meinem Verfahren für N = 39, 120, 363, 1092, 3279, 9840,  …. immer rekursiv auf 12, 39, 120, …. Kugeln zurückgegriffen werden muss; sollte das als Beweis ausreichen.
Ansonsten würde man in bestimmten Fällen rekursiv auf 13 Kugeln mit restlichen
3 Wägungen treffen  ---> Widerspruch.

Natürlich wäre ein allgemeiner Nachweis durch Induktion schöner; ich denk mal drüber nach.

Mit besten Grüßen

JoeM  

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am Di. 23. Februar 2016 03:39:14


Hallo salomeMe,

Du schreibst:

>Mit dem statischen Lösungsbeispiel werde ich mich nicht mehr beschäftigen<.

Das finde ich sehr schade.

Meine Meinung ist: Dies ist die beste aller Lösungen.

Die Verteilung siehe auf den 1. Blick nicht schwer aus.

Die Lösung basiert auf meiner >Rekursion<, ist aber wesentlich schwieriger herzuleiten.

Das besondere ist:
Es genügt, nach 5 Wägungen jeweils den Ausschlag der Waage zu kennen;
hier 2 Beispiele:






Ich denke, es lohnt sich, die Sache näher anzusehen.

beste Grüße

JoeM



 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am Di. 23. Februar 2016 03:54:54



 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von trunx am Di. 23. Februar 2016 09:17:24


@joem: wieder wiederholst du nur zum zigsten Male dein Vorgehen und wieder 'beweist' du nur, dass das Verfahren auch für größere Kugelanzahlen FUNKTIONIERT (was beides, glaube ich, jetzt auch der Letzte verstanden hat und wirklich kein Problem mehr ist), aber immer noch nicht, dass dieses Verfahren das optimale ist. Einziger Fortschritt, den ich sehe 'Meine Meinung ist: Dies ist die beste aller Lösungen.'
Es ist schon mal eine Einsicht, dass das wirklich nur eine Meinung ist.

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von salomeMe am Di. 23. Februar 2016 09:35:46


Holla JoeM,

schon wieder hast Du Dir so viel Arbeit gemacht.
Zur optimalen Strategie:
 Dass sie mit 12 Kugeln eine optimale bezügliche der Wägeanzahl ist, war mir klar. Mir ist auch einigermaßen klar, dass bei größeren Kugelanzahlen eine optimale Strategie bezügliche der Wägeanzahl maximal eine Kugel mehr erledigen könnte als Deine. Es müsste also gezeigt werden, dass für größere Anzahlen, diese Kugel mehr nicht möglich ist.
Deinen Hinweis "(eine Möglichkeit muss man abziehen; das wäre der Fall, dass alle Kugeln gleich schwer sind)" verstehe ich nicht, da dieser Fall nach Voraussetzung nicht eintreten kann.

Zum Beweis für die unendlich vielen großen Kugelanzahlen:
 Ich denke ein Induktionsbeweis ist recht leicht zu führen - eigentlich nur eine Verallgemeinerung Deiner rückwärts gerichteten Begründungen in die andere Richtung.

Zu den statischen Beispielen:
 Wenn ich mit @Trumpf's Lösungsvorschlag abgeschlossen habe, werde ich prüfen, ob Deine Beispiele äquivalent sind. Wenn aus den 5 Wägeresultaten per Formel die Nummer der Kugel zu ermitteln wäre, wie es bei @Trumpf's Lösungsvorschlag der Fall sein soll, wäre es gut Deine Formel zu erfahren.

Viele Grüße
salomeMe



 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am Do. 25. Februar 2016 03:58:43


Hallo salomeMe,

Du schreibst:

> Zu den statischen Beispielen:
Wenn ich mit @Trumpf's Lösungsvorschlag abgeschlossen habe, werde ich prüfen, ob Deine Beispiele äquivalent sind. Wenn aus den 5 Wägeresultaten per Formel die Nummer der Kugel zu ermitteln wäre, wie es bei @Trumpf's Lösungsvorschlag der Fall sein soll, wäre es gut Deine Formel zu erfahren. <

Bitte melde Dich.

Mich würde Deine Meinung interessieren, wenn Du Deine Analyse von Trumps Lösungsvorschlag gecheckt hast.

beste Grüße

JoeM





 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von Ex_Mitglied_44668 am Do. 25. Februar 2016 05:08:15


"Mich würde Deine Meinung interessieren, wenn Du Deine Analyse von Trumps Lösungsvorschlag gecheckt hast."


 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von salomeMe am Do. 25. Februar 2016 13:10:05


Hallo Trumpf und JoeM,

Resultat: Trumpf hat gehalten, was er versprochen hat! Gratulation - es wäre schön, wenn man dazu irgendwann einmal einen Artikel lesen könnte, der verrät welche Geistesblitze nötig waren, um diese Lösung hervorzubringen.

Analyse kann ich das nicht nennen, was ich letztendlich getan habe. Habe nach längerer Abstinenz ein VBScript geschrieben, dass die @Trumpf-Strategie hoffentlich so realisiert wie sie gemeint war. Es schafft aber nur bis zu 5 Wägungen und bestätigt für 12, 39 und 120 Kugeln die vorgeschlagene Strategie - 263 Kugeln würden für VBScript wohl in Arbeit ausarten.
Da die Log-Files zunehmend länger werden, hier nur das für 12 Kugeln (Gewichte: 1 leicht, 2 normal und 3 schwer):
#######
Eigenschaften der Kugeln bei 3 Waegungen:
========================================

Kugelnummer | "Vorzeichen" | 3 hoch 0 | 3 hoch 1 | 3 hoch 2 |

1 | 1 | 1 | 0 | 0 |
2 | 1 | -1 | 1 | 0 |
3 | 1 | 0 | 1 | 0 |
4 | 1 | 1 | 1 | 0 |
5 | 1 | -1 | -1 | 1 |
6 | 1 | 0 | -1 | 1 |
7 | 1 | 1 | -1 | 1 |
8 | -1 | 1 | 0 | -1 |
9 | -1 | 0 | 0 | -1 |
10 | -1 | -1 | 0 | -1 |
11 | 1 | -1 | 1 | 1 |
12 | -1 | 0 | -1 | -1 |


Wägung 1 Linke und rechte Schale :

2 | 5 | 10 | 11 |

1 | 4 | 7 | 8 |


Wägung 2 Linke und rechte Schale :

5 | 6 | 7 | 12 |

2 | 3 | 4 | 11 |


Wägung 3 Linke und rechte Schale :

8 | 9 | 10 | 12 |

5 | 6 | 7 | 11 |



Ab hier kommen alle möglichen Lösungsvarianten:
===============================================

Waegung 1: Gewicht links: 8 Gewicht rechts: 9
Waegung 2: Gewicht links: 8 Gewicht rechts: 8
Waegung 3: Gewicht links: 8 Gewicht rechts: 8

Schwere Kugel war 1 Resultat ist 1

Waegung 1: Gewicht links: 8 Gewicht rechts: 7
Waegung 2: Gewicht links: 8 Gewicht rechts: 8
Waegung 3: Gewicht links: 8 Gewicht rechts: 8

Leichte Kugel war 1 Resultat ist 1

Waegung 1: Gewicht links: 9 Gewicht rechts: 8
Waegung 2: Gewicht links: 8 Gewicht rechts: 9
Waegung 3: Gewicht links: 8 Gewicht rechts: 8

Schwere Kugel war 2 Resultat ist 2

Waegung 1: Gewicht links: 7 Gewicht rechts: 8
Waegung 2: Gewicht links: 8 Gewicht rechts: 7
Waegung 3: Gewicht links: 8 Gewicht rechts: 8

Leichte Kugel war 2 Resultat ist 2

Waegung 1: Gewicht links: 8 Gewicht rechts: 8
Waegung 2: Gewicht links: 8 Gewicht rechts: 9
Waegung 3: Gewicht links: 8 Gewicht rechts: 8

Schwere Kugel war 3 Resultat ist 3

Waegung 1: Gewicht links: 8 Gewicht rechts: 8
Waegung 2: Gewicht links: 8 Gewicht rechts: 7
Waegung 3: Gewicht links: 8 Gewicht rechts: 8

Leichte Kugel war 3 Resultat ist 3

Waegung 1: Gewicht links: 8 Gewicht rechts: 9
Waegung 2: Gewicht links: 8 Gewicht rechts: 9
Waegung 3: Gewicht links: 8 Gewicht rechts: 8

Schwere Kugel war 4 Resultat ist 4

Waegung 1: Gewicht links: 8 Gewicht rechts: 7
Waegung 2: Gewicht links: 8 Gewicht rechts: 7
Waegung 3: Gewicht links: 8 Gewicht rechts: 8

Leichte Kugel war 4 Resultat ist 4

Waegung 1: Gewicht links: 9 Gewicht rechts: 8
Waegung 2: Gewicht links: 9 Gewicht rechts: 8
Waegung 3: Gewicht links: 8 Gewicht rechts: 9

Schwere Kugel war 5 Resultat ist 5

Waegung 1: Gewicht links: 7 Gewicht rechts: 8
Waegung 2: Gewicht links: 7 Gewicht rechts: 8
Waegung 3: Gewicht links: 8 Gewicht rechts: 7

Leichte Kugel war 5 Resultat ist 5

Waegung 1: Gewicht links: 8 Gewicht rechts: 8
Waegung 2: Gewicht links: 9 Gewicht rechts: 8
Waegung 3: Gewicht links: 8 Gewicht rechts: 9

Schwere Kugel war 6 Resultat ist 6

Waegung 1: Gewicht links: 8 Gewicht rechts: 8
Waegung 2: Gewicht links: 7 Gewicht rechts: 8
Waegung 3: Gewicht links: 8 Gewicht rechts: 7

Leichte Kugel war 6 Resultat ist 6

Waegung 1: Gewicht links: 8 Gewicht rechts: 9
Waegung 2: Gewicht links: 9 Gewicht rechts: 8
Waegung 3: Gewicht links: 8 Gewicht rechts: 9

Schwere Kugel war 7 Resultat ist 7

Waegung 1: Gewicht links: 8 Gewicht rechts: 7
Waegung 2: Gewicht links: 7 Gewicht rechts: 8
Waegung 3: Gewicht links: 8 Gewicht rechts: 7

Leichte Kugel war 7 Resultat ist 7

Waegung 1: Gewicht links: 8 Gewicht rechts: 9
Waegung 2: Gewicht links: 8 Gewicht rechts: 8
Waegung 3: Gewicht links: 9 Gewicht rechts: 8

Schwere Kugel war 8 Resultat ist 8

Waegung 1: Gewicht links: 8 Gewicht rechts: 7
Waegung 2: Gewicht links: 8 Gewicht rechts: 8
Waegung 3: Gewicht links: 7 Gewicht rechts: 8

Leichte Kugel war 8 Resultat ist 8

Waegung 1: Gewicht links: 8 Gewicht rechts: 8
Waegung 2: Gewicht links: 8 Gewicht rechts: 8
Waegung 3: Gewicht links: 9 Gewicht rechts: 8

Schwere Kugel war 9 Resultat ist 9

Waegung 1: Gewicht links: 8 Gewicht rechts: 8
Waegung 2: Gewicht links: 8 Gewicht rechts: 8
Waegung 3: Gewicht links: 7 Gewicht rechts: 8

Leichte Kugel war 9 Resultat ist 9

Waegung 1: Gewicht links: 9 Gewicht rechts: 8
Waegung 2: Gewicht links: 8 Gewicht rechts: 8
Waegung 3: Gewicht links: 9 Gewicht rechts: 8

Schwere Kugel war 10 Resultat ist 10

Waegung 1: Gewicht links: 7 Gewicht rechts: 8
Waegung 2: Gewicht links: 8 Gewicht rechts: 8
Waegung 3: Gewicht links: 7 Gewicht rechts: 8

Leichte Kugel war 10 Resultat ist 10

Waegung 1: Gewicht links: 9 Gewicht rechts: 8
Waegung 2: Gewicht links: 8 Gewicht rechts: 9
Waegung 3: Gewicht links: 8 Gewicht rechts: 9

Schwere Kugel war 11 Resultat ist 11

Waegung 1: Gewicht links: 7 Gewicht rechts: 8
Waegung 2: Gewicht links: 8 Gewicht rechts: 7
Waegung 3: Gewicht links: 8 Gewicht rechts: 7

Leichte Kugel war 11 Resultat ist 11

Waegung 1: Gewicht links: 8 Gewicht rechts: 8
Waegung 2: Gewicht links: 9 Gewicht rechts: 8
Waegung 3: Gewicht links: 9 Gewicht rechts: 8

Schwere Kugel war 12 Resultat ist 12

Waegung 1: Gewicht links: 8 Gewicht rechts: 8
Waegung 2: Gewicht links: 7 Gewicht rechts: 8
Waegung 3: Gewicht links: 7 Gewicht rechts: 8

Leichte Kugel war 12 Resultat ist 12
###########

Viele Grüße
salomeMe

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von Slash am Do. 25. Februar 2016 13:23:33


Herzlich willkommen in den Top 15 der meistkommentierten Artikel. wink

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am Fr. 26. Februar 2016 00:40:17


Hallo Trumpf,

Du schreibst:

"Mich würde Deine Meinung interessieren, wenn Du Deine Analyse von Trumps Lösungsvorschlag gecheckt hast."

Pardon !

Diesen Vorschlag kenne ich nicht; es war auch keine Absicht, Deinen Namen falsch zu schreiben.

viele Grüße

JoeM

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am Fr. 26. Februar 2016 03:16:52


Hallo salomeMe

siehe folgenden Link:

http://de.math.wikia.com/wiki/Waage_und_12_Kugeln,_L%C3%B6sung

was sagt Dir das ?

viele Grüße

JoeM

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am Fr. 26. Februar 2016 03:41:20


Hallo Trumpf,



Brave Hunde beissen nicht.

viele Grüße

JoeM

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von salomeMe am Fr. 26. Februar 2016 10:05:37


Hallo JoeM,

danke für den Link:
http://de.math.wikia.com/wiki/Waage_und_12_Kugeln,_L%C3%B6sung

Dessen Inhalt sagt mir, dass mir unklar ist, wie die 3 Kugelnummer-Konstelationen für die 3 Wägungen zustande gekommen sind - wohl zufällig. Die Auswertung der Wägungen erinnert an die von @Trumpf vorgeschlagene. Sie ist aber analog zu den 3 Kugelnummer-Konstelationen bestimmt schwerer nachvollziehbar, als @Trumpf's Auswertung. Ich vermute der Verfasser hat alle 24 Fälle durchgerechnet und dann die Lösungsstrategie so hingebogen, dass sie funktioniert.

Dann sagt sie mir natürlich noch, dass es eine große Anzahl geeigneter Kugelkonstellationen für die statische Lösung solcher Wägeprobleme gibt. Eventuell ist diese Anzahl identisch oder größer als die der dynamischen Lösungsvarianten.

Dahingegen ist @Trumpf's Strategie von Anfang bis Ende eindeutig festgelegt und für 3 bis 5 Wägungen, falls das Script keine Fehler enthält als richtig geprüft.

Ist der Induktionsbeweis für das dynamische Verfahren schon fertig? Der würde mich etwas interessieren. Auch von der allgemeinen Optimalität der dynamischen Wägelösung bin ich noch nicht überzeugt - lässt sich das Argument für das 12-Kugelproblem, auch auf die größeren Anzahlen ausweiten?

Viele Grüße
salomeMe

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am Fr. 26. Februar 2016 23:56:51


Hallo salomeMe,

zu Deiner letzten Mitteilung:

1) Ich hab mir die Lösung von Trumpf, sowie die Lösung nach dem Link, den
ich Dir gesendet habe, nur kurz angesehen.
Ich vermute, dass beide Verfahren ähnlich ablaufen.

2) einen Induktionsbeweis habe ich mir noch nicht überlegt.

3) was meinst Du mit:
>Auch von der allgemeinen Optimalität der dynamischen Wägelösung bin ich noch nicht überzeugt - lässt sich das Argument für das 12-Kugelproblem, auch auf die größeren Anzahlen ausweiten?<

viele Grüße

JoeM

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von salomeMe am Sa. 27. Februar 2016 08:33:08


Hollo JoeM,

zu 1) eventuell steckt in der verlinkten Lösung auch ein Fehler. Man müsste alle 24 Fälle testen, um das heraus zu bekommen.

zu 3) Auf jeden Fall kann man bei (3^n-3)/2 +1 Kugeln für die in den n Wägungen nicht berücksichtigte Kugel noch zusätzlich herausbekommen ob sie normal oder abweichend ist.

Unter

 http://de.math.wikia.com/wiki/Waage_und_12_Kugeln%2C_L%C3%B6sung_und_Diskussion

war ein Beweis der Optimalität des 12-Kugel-Problems angegeben, obwohl natürlich auch hier über eine 13-te Kugel eine Teilaussage getroffen werden kann.

Gruß
salomeMe

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von salomeMe am Sa. 27. Februar 2016 09:04:02


Hallo Allerseits,

ein Paar Gedanken zur Strategie von @Trumpf:

1.) Es wird davon ausgegangen, dass sich jede der (3^n-3)/2 Kugelnummern {1, 2, 3,  ... , (3^n-3)/2} eineindeutig als Summe von verschiedenen positiven oder negativen Dreierpotenzen <= 3^n darstellen lässt. Dass müsste bewiesen werden. Da es nicht meine Idee war, versuche ich es aber nicht.

2.) Die Bildungsvorschrift der n-komponentigen Vektoren zu den nummerierten Kugeln spiegelt diese eineindeutige Abbildung wieder, falls sich daraus wirklich genau die Kugelnummern ergeben (falls 1. nicht bewiesen wird, sollte wenigstens das bewiesen werden)

3.) Die Bildungsvorschrift der Vektoren zu den Kugeln macht auch klar (falls 2. gilt), dass in jeweils genau (3^n-3)/6 der Kugelnummern eine bestimmte Dreierpotenz <= 3^n entweder mit positiven oder mit negativem Vorzeichen enthalten ist. Das ist die Grundlage für die Bildung der 2n Wägemengen.

4.) Jede Kugel wird so oft gewogen, wie sie von 0 abweichende Vektorkomponenten hat. Genauer nur bei den i-ten Wägungen bei denen die entsprechenden i-ten Vektor-Komponenten der Kugel von 0 abweichen. Dabei wird auch noch entsprechend des Vorzeichens der Vektor-Komponente die Kugel bei - in die linke und bei + in die  rechte Waagschale gelegt. Nur die abweichende Kugel bestimmt den Ausschlag der Waage. Damit lässt sich @Trumpf's Bestimmung der Kugelnummer eindeutig herleiten und mit Hilfe des Kugelvorzeichens (vor dem Vektor) und des Vorzeichens der Summe der Wichtungen der Wägeresultate lässt sich auch bestimmen, ob sie leichter oder schwerer ist.

Gruß
salomeMe

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am So. 28. Februar 2016 02:45:34


Hallo salomeMe,

ich habe im Internet einen interessanten Artikel gefunden, der anscheinend einen allg. Beweis für folg. Behauptung liefert:

Mit W Wägungen ist es möglich, aus (3^W - 3)/2 Kugeln die >falsche Kugel< zu identifizieren, incl. Gewichtsangabe.

Siehe dazu folgenden Link:

http://www.brodo.de/pub/kugelproblem.pdf

viele Grüße

JoeM



   

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von Slash am So. 28. Februar 2016 03:09:01


Hi JoeM und salomeMe,

externe Links könnt ihr wie folgt angeben:
html
<a href='WEB_ADRESSE' target=_blank><u>LINK_TEXT_ZUM_ANZEIGEN</u></a>

Einfach unten unter Eingabehilfen auf "[Link extern]" klicken, dann erspart ihr euch auch das Schreiben des html-Codes. Die LINK_TEXT-Unterstreichung (u /u) kann man auch löschen oder entsprechend verändern.

Gruß, Slash

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am So. 28. Februar 2016 03:37:34


Hi Slash,

vielen Dank für Deinen Tipp.

Klingt auf den 1. Blick schwieriger, als die Aufgabe  smile

Vielleicht könntest Du mal einen weiteren Lösungsvorschlag für die Aufgabe
anbieten ?!

viele Grüße

JoeM

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von salomeMe am So. 28. Februar 2016 13:57:16


Hallo JoeM,

danke für den Link zu dem PDF von Dominik Brodowski, das dieser schon 1999 oder 2000 als Schüler verfasst hat. Wahrscheinlich war zu dieser Zeit dieses Wägeproblem in Mode. Die ersten beiden Seiten deuten darauf hin, dass Du Dir keine Gedanken mehr um die gewünschten Beweise machen musst, da sie in den 6 Seiten geführt werden - bei Gelegenheit werde ich versuchen sie zu verstehen.

Falls Du wieder mal ein Problem zum Erraten stellst, solltest Du die vollständigen und genauen Voraussetzungen nennen - in diesem Fall z.B. dass die Kugeln eindeutig an ihren Nummern zu erkennen sind. Außerdem wäre es gut, wenn Dir die Mathematik, die dahinter steckt, in möglichst eleganter und einleuchtender Form bekannt ist.
Trotzdem war diese Raterunde recht lehrreich für mich. Nur so viel Zeit wollte ich eigentlich nicht damit verbringen, zumal mir die praktische Relevanz sehr fraglich erscheint.

Viele Grüße
salomeMe

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am Di. 01. März 2016 03:27:52


Hallo salomeMe,

Du schreibst:

>Falls Du wieder mal ein Problem zum Erraten stellst, solltest Du die vollständigen und genauen Voraussetzungen nennen - in diesem Fall z.B. dass die Kugeln eindeutig an ihren Nummern zu erkennen sind. Außerdem wäre es gut, wenn Dir die Mathematik, die dahinter steckt, in möglichst eleganter und einleuchtender Form bekannt ist.<

Dazu:

Geh doch nicht so streng mit mir um. smile

Ich meine: Bei dieser Aufgabe sollte man gerade NICHT angeben, dass die Kugeln eindeutig an ihren Nummern erkennbar sind. Es ist Teil der Aufgabe, herauszufinden, ob das notwendig ist, oder nicht.

Und: Ich denke schon, dass ich die Mathematik, die hinter der Aufgabe,
beginnend mit 12, 39, 120 Kugeln, .... steckt, kenne.
Hinter den einzelnen Schritten in meiner Lösung per Rekursion von 12 auf 39, auf 120 Kugeln, usw. steckt ein System, das man auf den 1. Blick nicht sieht.
(vielleicht hast Du es erkannt ?)

Zugegeben: Dieses System habe ich in meiner Lösung nicht erläutert.

Ich habe auch in meiner >statischen Lösung< keinen Lösungsweg angegeben. Es sieht vielleicht aus, als wäre das leicht herstellbar; dem ist aber nicht so:
Meine >statische Lösung< kann man aus meiner Sicht nur herstellen, wenn man mein >Prinzip der Rekursion< konsequent anwendet; und das ist nicht >ohne<

mit besten Grüßen

JoeM

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von Tobias_Meyer am Do. 10. März 2016 21:55:18


Meine Lösung mit maximal 5 Wägungen

Bedingung 1: Wenn links und rechts gleich schwer, fahre mit den Kugeln neben der Waage fort, sonst fahre mit den schwereren Kugeln fort.
1.Wägung: 40 Kugeln links, 40 Kugeln rechts, 40 Kugeln neben der Waage
2.Wägung: 13 Kugeln links, 13 Kugeln rechts, 14 Kugeln neben der Waage
3.Wägung (vorher 13 Kugeln): 4 Kugeln links, 4 Kugeln rechts, 5 neben der Waage
3.Wägung (vorher 14 Kugeln): 4 Kugeln links, 4 Kugeln rechts, 6 neben der Waage
4.Wägung (vorher 4 Kugeln): 2 Kugeln links, 2 Kugeln rechts, 0 neben der Waage
4.Wägung (vorher 5 Kugeln): 2 Kugeln links, 2 Kugeln rechts, 1 neben der Waage
4.Wägung (vorher 6 Kugeln): 2 Kugeln links, 2 Kugeln rechts, 2 neben der Waage
5.Wägung: 1 Kugel links, 1 Kugel rechts


Edit: Gilt nur für den Fall, dass die schwerere/leichter Kugel gesucht wird. Also wenn bekannt ist, dass die Falsche mehr/weniger wiegt!

 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von JoeM am Fr. 11. März 2016 01:19:22


Hallo Tobias_Meyer,

Du schreibst in Deiner Lösung zu Anfang:

>Bedingung 1: Wenn links und rechts gleich schwer, fahre mit den Kugeln neben der Waage fort, sonst fahre mit den schwereren Kugeln fort.
1.Wägung: 40 Kugeln links, 40 Kugeln rechts, 40 Kugeln neben der Waage.<

Dazu folgendes:

Es geht darum, die >falsche Kugel< zu identifizieren, incl. der Angabe, ob diese Kugel leichter/schwerer ist.

Fall 1:

1.Wägung: 40 Kugeln links, 40 Kugeln rechts; die Waage rechts geht nach unten.

Das bedeutet:

a) in der rechten Waagschale ist eine Kugel, die schwerer ist, oder

b) in der linken Waagschale ist eine Kugel, die leichter ist.

Es ist aber NICHT bekannt, ob die >falsche Kugel< leichter, oder schwerer ist, als alle anderen Kugeln.
Somit kannst Du NICHT >mit den schwereren Kugeln< weiterfahren.
In der anderen Waagschale könnte auch die >leichtere Kugel< sein.

Fall 2:

1.Wägung: 40 Kugeln links, 40 Kugeln rechts; Waage im Gleichgewicht.

Dann allein >mit den 40 Kugeln neben der Waage< weiterzuarbeiten, funktioniert nicht. Mit weiteren 4 Wägungen die >falsche Kugel< aus 40 Kugeln zu identifizieren, geht nicht; das geht nur mit maximal (3^4 - 3)/2 = 39 Kugeln.

viele Grüße

JoeM









 [Bearbeiten]

Re: 120 Kugeln und eine Balkenwaage
von Tobias_Meyer am Fr. 11. März 2016 17:27:01


Ok - wer lesen kann, ist klar im Vorteil wink
Hatte die Aufgabe nicht richtig gelesen. Wenn nur bekannt ist, dass eine Kugel ungleich dem Gewicht der anderen ist, bleibt wohl nur deine komplexere Lösung vom 23.Feb...

 [Bearbeiten]

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2017 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]