Rätsel

[Rinf]

(also eher nach Art der Brücken-Probleme).

Ja, deswegen meine Überlegungen zu "gerade/ungerade". Das Brückenproblem, also das Problem, in einem Graphen alle Kanten zusammenhängend auf einem Pfad genau einmal zu besuchen ist ja z.B. genau dann lösbar wenn entweder alle Knoten geraden Grades sind (also gradzahlig viele Kanten) oder genau 2 Knoten ungeraden Grades sind (diese müssen dann Start- und Endpunkt sein).

 

Graphentheoretisch kann man sicherlich einiges zeigen, aber hier haben wir es ja mit einer verkappten Optimierungsaufgabe mit echten numerischen Werten zu tun, nicht unähnlich dem Traveling-Salesman-Problem.

 

Also einen allgemeinen Beweis in der Art des Brückenproblems traue ich mir denn doch nicht zu.

[Rinf]

Bei der ersten und 3ten Messung benutzt Du 3 Zustände, bei der zweiten nur 2,...

Nein, das stimmt so nicht:

Die 2. Messung kann auch unentschieden ausgehen, nämlich in dem Fall, daß die gesuchte Kugel eine der 3 an der Messung nicht beteiligten ist.

[Sokrates]

Bei der ersten und 3ten Messung benutzt Du 3 Zustände, bei der zweiten nur 2,...

Nein, das stimmt so nicht:

Die 2. Messung kann auch unentschieden ausgehen, nämlich in dem Fall, daß die gesuchte Kugel eine der 3 an der Messung nicht beteiligten ist.

Ich hatte Maxis Lösung genommen. Gilt das da auch?

 

Nachtrag: Ja, Du hast recht.

bearbeitet 7. Dezember 2004 von Sokrates

[Sokrates]

Damit stimmt die Welt wieder:

 

Korrektur meiner Antwort von hier.

 

Also:

1 von 12 Kugeln benötigt ld (12) = 3,5849 bit Information

Die Frage ob schwerer oder leichter benötigt 1 bit (da beisst die Maus keinen Faden ab: es ist eine volle ja/nein Entscheidung).

 

Macht zusammen 4,5849 bit.

 

Pro Messung kriegt man maximal ld(3) = 1,5849 bit Information, macht zusammen 4,7548 bit, und das reicht.

 

Bei 13 Kugeln braucht man theoretisch 3,7004 bit, das ist zwar kleiner als die obigen 4,7548 bit, aber wegen des Digitalisierungsrauschens (nur bei durch 3 teilbaren Zahlen geht es rückstandsfrei) lässt sich das nicht umsetzen. Es bleibt eine unvermeidliche 5er Gruppe am Anfang (Aufteilung 4/4/5), und für diese braucht man bei zwei Messungen 3,32 bit Information, hat aber nur 3,17 bit aus zwei Messungen (2*1,5849), was nicht reicht.

[Rinf]

Ich hatte Maxis Lösung genommen. Gilt das da auch?

 

Nachtrag: Ja, Du hast recht.

Gilt für meine Lösung nebenbei auch, die ich bei dieser Gelegenheit jetzt doch mal einfach so unters Volk werfe:

 

Es geht natürlich um die knifflige 2. Wägung bei anfänglichem Ungleichgewicht und wieder oBdA A<B:

 

AABB <-> ABCC

 

Sind beide gleich, dann muß ich eine der nicht gewogenen (A oder B ) gegen eine C-Kugel wiegen.

An dieser Stelle könnte man eventuell mit mehr Kugeln noch mehr Information rausquetschen, denn bei A <-> C geht nur A=leichter oder nicht und bei B <-> C nur B=schwerer oder nicht.

Allerdings wäre das kein allgemeingültiger "Informationunterschuß", denn:

 

Ist AABB leichter, dann deswegen, weil eine der beiden linken AA leichter sind oder die rechte B schwerer.

Also die beiden linken AAs gegeneinander wiegen (wieder mit 3 informationträchtigen Zuständen!) und ich weiß Bescheid.

 

Für AABB = schwerer analog (das meinte ich mit "schön symmetrisch" )

[Rinf]

Damit stimmt die Welt wieder:

[...]

Macht zusammen 4,5849 bit.

 

Pro Messung kriegt man maximal ld(3) = 1,5849 bit Information, macht zusammen 4,7548 bit, und das reicht.

...

Wow - sehr schön!

 

Dann fällt also der obige Fall von "Informationsunterschuß-Wägung" zusammen mit dem, der bei der 3.Wägung ensteht, wenn bei 1. und 2. Wägung Gleichstand herrscht in diesen klitzekleinen "Gap" von 0,1699 Bit...faszinierend!

[Inge]

Irgendwie erscheint mir die 22-er Lösung zu trivial.

Komischerweise ist 22 aber genau die Summe aus Länge (13) und Breite ohne Doppellinien (9).

bearbeitet 7. Dezember 2004 von Inge

[Sokrates]

An dieser Stelle könnte man eventuell mit mehr Kugeln noch mehr Information rausquetschen, denn bei A <-> C geht nur A=leichter oder nicht und bei B <-> C nur B=schwerer oder nicht.

Aber ich denke, dass das nicht reicht, denn entscheidend ist der Verlust bei der 1 Wägung:

 

Bei der ersten Wägung muss man drei Gruppen bilden, um ein Maximum an Information aus den drei Waagezuständen rauszuholen. Bei 13 Kugeln ist mindestens daher mindestens eine 5er Gruppe dabei. Und für die bräuchte ich ld(5) = 2,32 bit Information plus das eine bit für schwer/leicht, macht zusammen 3,32 bit. Ich kriege aber nur weniger als 2*1,59 = 3,18 bit aus zwei Messungen. Daher ist 12 das Maximum mit dem es geht. Mein Posting vorhin war falscher Alarm, weil ich meinte, man könne "schwer/leicht" mit weniger als 1 bit rauskriegen. Das geht aber nicht.

[Rinf]

An dieser Stelle könnte man eventuell mit mehr Kugeln noch mehr Information rausquetschen, denn bei A <-> C geht nur A=leichter oder nicht und bei B <-> C nur B=schwerer oder nicht.

Aber ich denke, dass das nicht reicht, denn entscheidend ist der Verlust bei der 1 Wägung:

[...]

Nee - das hatte ich ja vor Deinem Beweis (bzw. während) geschrieben.

Das ginge höchstens, wenn in einer ganzen Wiegestufe für alle Fälle eine Information ungenutzt bliebe, aber diese Überlegungen sind eh obsolet:

Dein Beweis, daß 12 maximal ist, erscheint mir doch sehr wasserdicht und auf einem entzückend abstrakten Niveau, so daß man sich über eine vielleicht dann doch noch trickreichere Strategie einfach keinen Kopp mehr zu machen braucht.

 

Gruß Ralf

[Rinf]

Irgendwie erscheint mir die 22-er Lösung zu trivial.

Komischerweise ist 22 aber genau die Summe aus Länge (13) und Breite ohne Doppellinien (9).

Stimmt... ist mir gar nicht aufgefallen. Und - hast Du eine Ing'sche Vermutung?

 

Ich bin mittlerweile ziemlich sicher, daß 17,5 Yards zu wenig sind.

2. Versuch:

1,5 für den letzten Weg zum Anfang zurück wie gehabt.

7 Yards aus den bekannten Teilbarkeitserwägungen.

Bleiben noch 9 Yards über.

 

Da es geradezahlig viele waagerechte von links nach rechts gibt, müssen dieses genutzt werden - wir dürfen nicht noch einmal von links nach rechts.

 

Dadurch ergeben sich einige Zugzwänge.

Der 7-er Weg z.B. kann nur für das obere Mittellinienstück verbraten werden, damit das freie Ende da oben "versorgt" ist und jeder andere (waagerechte) Weg dorthin würde schon die ganzen 9 aufbrauchen.

Dieser Abstich kann nur auf dem Rückweg erfolgen und der Hinweg muß der untere 9-er sein.

 

Also in etwa so, alle die Pfeile da erscheinen mir zwingend:

 

 

 

Um von A nach B zu kommen muß man einen 6-er Weg doppelt gehen, da auf jeder Hälfte eien gerade Anzahl Vertikaler besucht werden müssen, und gerade ist schön, wenn man zum Ausgangspunkt zurück will, aber ganz blöd, wenn man von eben A nach B will.

Das gleiche gilt für den Weg von C nach D.

Und das macht summa summarum 12 Yards und 12 ist irgendwie größer als 9, da beißt die Maus keinen Faden ab.

 

Habe ich einen Fehler in meiner Überlegung?

 

Wenn nein, dann dürfte 22 als "bewiesen" gelten.

[maxinquaye]

Damit stimmt die Welt wieder:

 

Korrektur meiner Antwort von hier.

 

Also:

1 von 12 Kugeln benötigt ld (12) = 3,5849 bit Information

Die Frage ob schwerer oder leichter benötigt 1 bit (da beisst die Maus keinen Faden ab: es ist eine volle ja/nein Entscheidung).

 

Macht zusammen 4,5849 bit.

 

Pro Messung kriegt man maximal ld(3) = 1,5849 bit Information, macht zusammen 4,7548 bit, und das reicht.

 

Bei 13 Kugeln braucht man theoretisch 3,7004 bit, das ist zwar kleiner als die obigen 4,7548 bit, aber wegen des Digitalisierungsrauschens (nur bei durch 3 teilbaren Zahlen geht es rückstandsfrei) lässt sich das nicht umsetzen. Es bleibt eine unvermeidliche 5er Gruppe am Anfang (Aufteilung 4/4/5), und für diese braucht man bei zwei Messungen 3,32 bit Information, hat aber nur 3,17 bit aus zwei Messungen (2*1,5849), was nicht reicht.

Sokrates, genau das meinte ich. Genau diesen Fehler habe ich eben lange Zeit gemacht, die Informationsmenge falsch eingeschätzt. Ich hätte das einfach einfach rechnen sollen. Sehr schöne Ausführung.

[maxinquaye]

Ich habe das Tennisbeispiel nicht ganz mitverfolgt..aber wenn nur auf den Linien gehen darf, dann kannst Du dir doch einen Baum aufmalen und notfalls den Computer drauf los lassen, die paar Möglichkeiten hat der in nullkommanix.

 

Oder befriedigt Dich eine numerische Lösung nicht ?

bearbeitet 7. Dezember 2004 von maxinquaye

[Inge]

Komischerweise ist 22 aber genau die Summe aus Länge (13) und Breite ohne Doppellinien (9).

Stimmt... ist mir gar nicht aufgefallen. Und - hast Du eine Ing'sche Vermutung?

Nein. Ich halte das für Zulaff - äh Zufall.

[Ute]

Ähhmm. Warum hat eigentlich niemand die Möglichkeit genutzt, diagonal über den Tennisplatz zu laufen?

[Wally]

Ute, wie soll ->in der Aufgabe vom 06.12. der Balljunge die Linien kehren, wenn er diagonal über'n Platz läuft?

[maxinquaye]

Wally, rätselst Du Dich durch den Kalender ? Das neue Rätsel ist zienlich interessant..

[Wally]

Ja, das ->Stein - Schere - Papier-Spielen mit dem Osterhasen,

ich bin noch dabei ...

[Ute]

Ute, wie soll ->in der Aufgabe vom 06.12. der Balljunge die Linien kehren, wenn er diagonal über'n Platz läuft?

Ich kenne die Aufgabe, Wally. Nirgends steht, dass er überall da, wo er läuft, auch kehren muss. Es wird darauf hingewiesen, dass er nicht nur ab und zu auf einer Linie doppelt laufen muss, sondern auch, dass er die Linie verlassen kann. Und da bietet sich die Diagonale doch an, oder nicht?

[Ute]

Ja, das ->Stein - Schere - Papier-Spielen mit dem Osterhasen,

ich bin noch dabei ...

DAS finde ich total einfach gegenüber manchen anderen von dieser Woche.

[Wally]

Einfach??? Ich steh auf'm Schlauch

 

Es gibt folgende 6 Kombinationen von St(ein), Sch(ere) und P(apier):

Weihnachtsmann(1) Osterhase(2) es gewinnt

St St 0

Sch St 2

P St 1

St P 2

Sch P 1

P P 0

 

Wenn beide zufällig spielen, hat Weihnachtsmann keinen Vorteil.

 

Hase kann mit beidem je 1 mal gewinnen und verlieren.

 

Weihnachtsmann kann mit

• Stein nicht gewinnen
  
• Schere gewinnen oder verlierer (50:50-Chance)
  
• Papier nicht verlieren
  

Also sollte Weihnachtsmann oft Papier und selten Stein spielen, oder?

 

Da Hase das weiss, kontert er öfters mit Papier.

 

Da Weihnachtsmann das weiss, kontert er oft mit Schere.

 

Da Hase das weiss, kontert er gelegentlich mit Stein.

bearbeitet 7. Dezember 2004 von Wally

[maxinquaye]

Da haben wir den Salat. Mathematiker sind mindestens so schlimm wie Bisexuelle ..!

Das Problem steckt in dem kleinen, hübschen Wort : "optimal"

 

Ute, Du bist doch Lehrerin, und daher solltest Du Dich mit Gemeinheiten doch gut auskennen..

[Rinf]

Ähhmm. Warum hat eigentlich niemand die Möglichkeit genutzt, diagonal über den Tennisplatz zu laufen?

Ähhmm². Das habe ich - und ich habe mir die Hacken wund gelaufen bei dem Versuch. Aber bei all meinem Unvermögen, das Problem abstrakt wirklich in den Griff zu kriegen (als approximiertes DHC-Problem (TSR war nicht ganz treffend)) kann ich mir nicht vorstellen, was Diagonale da am Problem lindern könnten. Nichtsdestotrotz habe ich alle mir zumindestens nicht komplett blödsinnig erscheinenden Diagonalen ausgerechnet, kam aber nie auf den vorgegeben krummen Wert (und der Lösungsraum ist ja diskret vorgegeben).

 

Kannst Du mein "Es kann nicht Lösung B sein"- Argument denn widerlegen?

[Sokrates]

Beim Balljungenproblem muss man graphentheoretisch vorgehen:

 

Wenn der Balljunge das Feld auf einem geschlossenen Weg durchlaufen will (und doppelte Wege sind Hilfswege für einen geschlossenen Pfad) und an der gleichen Stelle verlassen,wie er rein ist, dann müssen alle STellen an denen Kanten zusammenstossen, eine gerade Anzahl von Kanten haben.

 

Insgesamt haben wir 10 Punkte mit ungerader Kantenanzahl (5 am Netz, 3 in der Mitte, 2 unten).

 

Wir müssen also insgesamt 5 Hilfsverbindungen einführen, damit wir ein Netz mit lauter geradzahligen Punkten haben. Wir müssenalso durch Probieren die 5 in der Summe kürzesten Verbindungen zwischen den 3er Schnittpunkten suchen.

 

Die kürzesten Hilfsverbindungen, die ich gefunden habe, sind insgesamt 22 Yards lang. (die beiden äussersten Netzlinien verbinden (2*1,5) und die Linien von Netz zur Mitte (7 yards) uund 2 mal die innere Seitenlinie a 6 yards). Zu probieren, ob es kürzere gibt, ist ein reines Probierverfahren mit 945 Möglichkeiten,m wenn ich richtig gerechnet habe (Zahl der verschiedenen möglichen Paare von 10 Punkten).

 

Mir scheint, 102 ist korrekt.

 

Hier ein Bild mit den zehn Punkten mit ungerader Linienanzahl und meinen 5 Hilfslinien:

 

 

PS. Natürlich könnte man diagonal laufen, aber ich wüsste nicht, wo das kürzer wäre.

 

Nachtrag in ausgeschlafenem Zustand:

 

Die oben angeführten Hilfslinien sind die kürzesten, weil:

 

a) Die Punkte 1,2,4,5,9 und 10 bereits mit ihren nächsten Nachbarn verbunden sind.

es genügt also die Punkte 3, 6, 7 und 8 anzuschauen, ob man was verkürzen kann, aus Symmetriegründen reichen 3, 6 und 7.

c) ein näherer Nachbar von 3 wäre 2 (man spart 2,5 yards). Dann verliert aber 1 seinen nächsten Nachbarn und muss zum übernächsten, der wäre diagonal 6, und das ist 7,158 yards, das ist mehr als 6 yards weiter als die ursprüngolichen 1,5 yards. Bilanz: 3 mit 2 verbinden kostet mindestens 6-2,5=3,5 yards mehr. 3 mit 1 verbinden ist auch kürzer als mit 7, aber da ist die Bilanz noch ungünstiger, weil ich 1 yard spare, aber bei 2 mit dem nächsten Nachbarn 6 (ohne Folgeschäden) 7 yards bringt. Also 4,5 yards schlehter in Summe.

d) Ein näherer Nachbar von 6 wäre 7. (spart 1,5 yards) Dann verliert aber 9 seinen nächsten Partner und muss zu 10, was 9 statt 6 yards bedeutet. Bilanz: 1,5 yards schlechter.

e) gleiches gilt für 7, dessen nächster Partner 6 wäre, mit analoger Überlegung.

 

Damit ist gezeigt, dass die oben eingezeichnete Anordnung von Hilfslinien die kürzeste paarweise Verbindung der 10 Dreierpunkte ist.

bearbeitet 8. Dezember 2004 von Sokrates

[Ute]

Wenn Weihnachtsmann Stein spielt, hat er eine Chance von 1 : 3. Schlecht.

Wenn W Schere spielt, hat er eine Chance von 1 : 1. Naja.

Wenn W Papier spielt, hat er eine Chance von 3 : 1. Also spielt er bevorzugt Papier, würde ich sagen. Osterhase weiß das auch, also spielt er wahrscheinlich Papier. W weiß das auch, und so wird er ab und zu wechseln, um O zu verunsichern. Trotzdem wird er hauptsächlich Papier spielen müssen, oder?

 

Grüße von Ute

[Sokrates]

Oops. Das Weihnachtsmann/Osterhase-Rätsel ist definitiv nichttrivial. Ich hab noch nicht mal eine Idee, was ich als Kriterium für eine optimale Strategie hernehmen soll. Eine "friedliche" Strategie wäre, wenn der Osterhase 50/50 Papier und Stein, und der Weihnachtsmann 50/50 Schere und Papier. (Stein ist für den Weihnachtsmann sinnlos, weil Stein nie gewinnt, nur verliert oder unentschieden macht, unabhängig von der Strategie des Osterhasen). Die "friedliche Lösung" ergibt einen Vorteil von 1/4 Kartoffel pro Spiel für den Weihnachtsmann. Die kann aber der Weihnachtsmann austricksen, indem er in seiner Strategie öfter Papier spielt. Da kann der Osterhase zwar kontern, indem er auch öfter Papier spielt, aber er muss "mehr" kontern, als der Weihnachtsmann vorlegt. Mir scheint also, die "friedliche Strategie" ist nicht stabil. Man muss einen anderen Punkt suchen, bei dem keiner der anderen einen Vorteil davon hätte, vom Optimum abzuweichen. Da suche ich noch.

 

Nachtrag: Mit meinem vorletzten Satz stimmt mein dritter nicht mehr: Jetzt habe ich nämlich eine Idee, was ich als Kriterium nehmen könnte. Man muss manchmal bloss seine Gedanken aufschreiben, um zu wissen, was man gedacht hat.

bearbeitet 8. Dezember 2004 von Sokrates