Hardcore-Matherätsel?

    • Brutha2k
      Brutha2k
      Bronze
      Dabei seit: 12.05.2011 Beiträge: 378
      Tach zusammen, ich habe vor vielen Jahren ein Rätsel gestellt bekommen, mit dem ich mich schon etliche Stunden, auch zusammen mit Freunden, beschäftigt habe.
      Die einzige "Lösung", die ich jemals gehört habe, ist irgendwie so wenig zufriedenstellend, dass ich fragen möchte, ob jemand eine bessere kennt/findet oder man sich wirklich damit zufriedengeben muss...
      (und ja, ich habe das durchaus auch mal im Internet gesucht, aber nicht gefunden)


      Aaaalso, hier kommt das Rätsel:

      Wir haben das Gittermodell eines Tetraeders, also wirklich nur die 6 Außenkanten. Auf diesen sitzen 3 blinde Polizisten und 1 sehender Gangster (die selbstverständlich ohne Gravitationseinwirkungen auf den 6 Kanten rumlaufen können).
      Alle 4 sind sehr intelligent (verhalten sich also optimal). Die Polizisten können miteinander kommunizieren, sehen und hören den Gangster aber eben nicht, wissen also niemals, wo er sich gerade befindet.

      Die 3 Polizisten sind gleich schnell, der Gangster minimal schneller (glaube, das macht aber keinen Unterschied, auf jeden Fall ist er mindestens gleich schnell)...

      Frage: Können die Polizisten durch sinnvolle Absprache, wie sie laufen, den Gangster garantiert erwischen?

      Hier die wie gesagt nicht wirklich zufriedenstellende "Lösung":

      Die drei Polizisten starten an einer Ecke und gehen von dort aus jeweils eine andere Kante entlang. Am Endpunkt dieser Kante kann der Gangster nur irgendwo zwischen ihnen sein. Jetzt bleibt einer der Polizisten stehen (welcher ist zufällig!), die beiden anderen laufen auf ihn zu.
      Zu 67% Chance war er auf einer dieser beiden Kanten und wird erwischt, zu 33% war er auf der dritten und entkommt.
      Ausgehend von diesem Punkt wird das erneut - immer wieder - gemacht.
      Egal, wie der Gangster sich verhält, er wird zu 2/3 erwischt.
      Die Wahrscheinlichkeit, dass er beliebig oft hintereinander immer auf der dritten Kante sitzt, ist 0, deswegen wird er insgesamt zwingend gefasst.
  • 34 Antworten
    • Zabagad
      Zabagad
      Global
      Dabei seit: 24.01.2010 Beiträge: 1.145
      Sehr nett - Danke für das Rätsel.

      Innerhalb der ersten Minute bin ich auf genau die gespoilerte Lösung gekommen.
      Werde noch ein wenig drüber nachdenken, aber mein Gefühl ist, dass dies schon das Optimum sein dürfte...
    • Roven
      Roven
      Bronze
      Dabei seit: 21.04.2007 Beiträge: 3.053
      Das ist imo gar keine Lösung. Kannste genauso sagen, dass wenn sie unendlich lang kreuz und quer laufen, ihn irgendwann erwischen.

      Denke, dass es keine echte Lösung gibt.
    • Zabagad
      Zabagad
      Global
      Dabei seit: 24.01.2010 Beiträge: 1.145
      Ups -ich hab die Lösung - müsste aber noch ein wenig überlegen wie ich die formuliere bzw. aufzeichne...

      Es geht aber damit zu 100% immer direkt...
    • Silicernium
      Silicernium
      Bronze
      Dabei seit: 22.12.2009 Beiträge: 3.203
      Original von Zabagad
      Ups -ich hab die Lösung - müsste aber noch ein wenig überlegen wie ich die formuliere bzw. aufzeichne...

      Es geht aber damit zu 100% immer direkt...
      Da sind wir aber einmal gespannt.
    • josch2001
      josch2001
      Black
      Dabei seit: 25.03.2006 Beiträge: 17.253
      Würd auch sagen, dass es keine Lösung ist. Ist ja genauso wie die Verdoppelungsstrategie. Die Wahrscheinlichkeit ist eben nicht 0, dass er immer auf der dritten Stange steht sondern geht nur gegen null. Oder wie man das auch immer korrekt mathematisch ausdrückt.
    • Zabagad
      Zabagad
      Global
      Dabei seit: 24.01.2010 Beiträge: 1.145
      OK ich versuche es mal so:

      An der Spitze oben fangen wir an im Uhrzeigersinn die Linien nach "unten" mit Nummern zu beschriften.
      somit haben wir 3 Linien mit 1, 2 und 3.
      Die Verbindung zwischen Endpunkten 1 und 2 ist Linie 4.
      Die Verbindung zwischen Endpunkten 2 und 3 ist Linie 5.
      Die Verbindung zwischen Endpunkten 3 und 1 ist Linie 6.

      OK?

      1) Treffen sich dann alle 3 Polizisten an der Spitze.
      2) 2 laufen los auf Line 1 + 2 und der 3te blockiert die Spitze. (damit sind 1+2 save)
      3) Der der die 1 abgelaufen ist, läuft
      3) die 2 laufen auf der 4 bis sie sich in der Mitte treffen und laufen wieder zurück. (damit ist Linie 4 save)
      4) Beide laufen jetzt an linie 5 und 6 entlang bis sie sich treffen (damit sind 5 und 6 save und der rest bleibt save)
      5) beide laufen zur spitze oder der 3te kommt runter zu den beiden.


      Scheisse zu früh gefreut :D

      Sorry - war dann wohl doch nichts, da natürlich wenn die 2 Ps die 4 ablaufen er in die 1 oder 2 kommt... ;(
    • marc0506
      marc0506
      Bronze
      Dabei seit: 03.02.2006 Beiträge: 8.241
      eigenen fehler gefunden, ist auch was wert...;)
    • efde55
      efde55
      Bronze
      Dabei seit: 14.06.2011 Beiträge: 172
      Während die beiden Polizisten auf der 4 sind geht unser Gangsta über einen der freien Endpunkte 1 oder 2 auf Linie 1 oder 2 und während die Polizisten 5 und 6 ablaufen kann er sich fröhlich auf 1, 2, 4, 5 hinter dem Polizisten und 6 hinter dem Polizisten bewegen.

      Edit: Zu langsam /
    • Brutha2k
      Brutha2k
      Bronze
      Dabei seit: 12.05.2011 Beiträge: 378
      Original von josch2001
      Würd auch sagen, dass es keine Lösung ist. Ist ja genauso wie die Verdoppelungsstrategie. Die Wahrscheinlichkeit ist eben nicht 0, dass er immer auf der dritten Stange steht sondern geht nur gegen null. Oder wie man das auch immer korrekt mathematisch ausdrückt.
      Jo, eben, das macht das Ganze ja unbefriedigend, dass wir hier nur einen Grenzwert von 0 haben.
      Es wäre also wie eine Verdopplungsstrategie, bei der wir unendlich viel Geld haben (damit ist das Problem schonmal gelöst), aber eben nicht unendlich viel Zeit. Nun ist die Wahrscheinlichkeit, dass immer Rot kommt, bis ich sterbe, einfach nur noch lächerlich, aber sie ist nicht Null...

      Wäre hier von Göttern die Rede, die unsterblich sind, könnte man es noch halbwegs akzeptieren.

      Oder würde ich einen Beweis sehen, dass es eben keinen 100%-Algorithmus geben kann, wär ich ja auch happy... Aber die sind ja meistens noch schwerer ;)
    • CMBurns104
      CMBurns104
      Bronze
      Dabei seit: 18.06.2006 Beiträge: 2.752
      Die Antwort ist in der Tat unbefriedigend. Die Schlussfolgerung, dass der Gangster mit dieser Strategie zu 100% geschnappt wird, ist einfach falsch, es sei denn man geht davon aus, dass die Jungs unendlich viel Zeit haben, aber sowas wie "unendlich viel Zeit" gibt es einfach nicht. In endlicher Zeit ist die Wahrscheinlichkeit, mit der der Gangster sich retten konnte immer >0.

      Daraus folgt natürlich noch nicht, dass es keine andere Strategie geben kann, die zu 100% zum Erfolg führt. Kann deine Frustration über diese Antwort völlig nachvollziehen. :f_mad: ;)
    • sarc
      sarc
      Moderator
      Moderator
      Dabei seit: 06.06.2008 Beiträge: 12.512
      Hm... Ich glaub, ich hab die Aufgabenstellung nicht ganz verstanden... Wie auch immer, von dem was ich glaube wies aussieht, würd ich so vorgehen:

      Der Ganster wie auch die Polizisten stehen anfangs in der Mitte einer Kante, richtig? Es gibt 6 Kanten, an jede Kante schließen genau vier an. Das heißt, egal wie das Anfangsszenario ist, der Gangster kann immer in eine Richtung loslaufen, in der eine freie Kante ist, und sich dort in die Mitte dieser freien Kante stellen. Selbst wenn der Polizist auf der zweiten auf die gleiche Ecke zuläuft, erreicht diese der Gangster etwas früher, da er etwas schneller ist. Auf der neuen Kante angekommen wartet er eben, bis die Polizisten auch wieder in Position sind.
      Die Polizisten könnten das jetzt noch komplizierter machen, indem sie auch ihrerseits warten. Das macht die Entscheidungsmöglichkeiten für den Gangster, in welche Richtung er geht, aber eher einfacher.

      So, wo ist jetzt der Denkfehler? Das kanns denk ich nicht sein... Vor allem, weil das sogar funktionieren würd, wenn die Polizisten den auch sehen, es reicht da allein, dass er schneller ist...
    • KittenKaboodle
      KittenKaboodle
      Bronze
      Dabei seit: 29.01.2006 Beiträge: 3.527
      Polizisten und Gangster starten irgendwo auf dem Tetraeder. Ganster sieht Polizisten, Polizisten sehen den Gangster nicht, nur andere Poliszisten. Polizisten können miteinander kommunizieren. Bewegung findet entlang der Kanten statt. Gibt es einen Algorithmus, der den Gangster "fängt", also eine Kollision eines Polizisten mit dem Gangster garantiert?

      Gibt es nicht, weil man zu dritt nie feststellen kann, ob sich der Gangster auf einer Kante derjenigen Fläche des Tetraeders aufhält, welche durch die drei Position der Polizisten definiert wird, ohne einen Eckpunkt der Fläche aufgeben zu müssen, über die der Gangster prinzipell entkommen könnte.
    • emophiliac
      emophiliac
      SuperModerator
      SuperModerator
      Dabei seit: 08.03.2005 Beiträge: 4.631
      geht die lösung?



      eckpunkte A,B,C,D

      polizisten(P) stehen auf den eckpunkten A, D, B

      P2 geht nach A und P3 geht nach A
      P2 geht nach D und P3 geht nach B
      P1 geht nach C
      P1 geht von C nach D
      P1 geht von D nach C
      P1 geht von C nach B
      P1 geht von B nach D
    • emophiliac
      emophiliac
      SuperModerator
      SuperModerator
      Dabei seit: 08.03.2005 Beiträge: 4.631
      geht nicht.
    • SoWe
      SoWe
      Global
      Dabei seit: 10.01.2008 Beiträge: 2.397
      wenn mans andersrum betrachtet - kann der sehende räuber mit sicherheit flüchten?
      dann kommt man zur einfachen antwort - nein. zb mit der erklärung im op
    • hazz
      hazz
      Black
      Dabei seit: 13.02.2006 Beiträge: 4.771
      nein, gangster kann doch auf BC warten und nach a laufen. deine ersten 3 steps sind auch nix anderes als alle starten in a und gehen je nach bcd.

      edit: war auf emos post bezogen.
    • Rolo23
      Rolo23
      Bronze
      Dabei seit: 18.04.2005 Beiträge: 743
      lustig, Scotland Yard auf nem Tetraeder

      ich würde tippen, dass man den räuber nicht 100% sicher in endlicher zeit fangen kann
      um das zu beweisen müsste man eine geignete strategie des räubers angeben und dann zeigen dass man ihn nicht mit sicherheit kriegt
    • Silicernium
      Silicernium
      Bronze
      Dabei seit: 22.12.2009 Beiträge: 3.203
      Original von Rolo23
      lustig, Scotland Yard auf nem Tetraeder

      ich würde tippen, dass man den räuber nicht 100% sicher in endlicher zeit fangen kann
      um das zu beweisen müsste man eine geignete strategie des räubers angeben und dann zeigen dass man ihn nicht mit sicherheit kriegt
      Der Räuber kann keine Strategy haben, da es ja vom Zufall abhängt ob er gefasst wird. Er kann ja nicht wissen, welche beiden Polizisten auf den wartenden Polizisten zugehen.
    • Thurisaz
      Thurisaz
      Bronze
      Dabei seit: 15.07.2006 Beiträge: 16.587
      Das Problem ist imo nicht "echt" lösbar.

      Im ersten Schritt können die drei Polizisten maximal drei Kanten als verbrecherfrei einstufen, und das ist nur in zwei Fällen möglich. Entweder laufen sie alle auf die gleiche Ecke zu, oder von der gleichen Ecke ausgehend los. Nur so kann man garantieren, dass der Verbrecher auch nicht "wegläuft", wenn er auf einer dieser Kanten ist.

      In beiden Fällen kann man diese drei Kanten als verbrecherfrei einstufen, und der Typ hockt auf einer der übrigen drei Kanten. Aber nur im zweiten Fall nützt uns die Info etwas, weil wir die übrigen Kanten mit Polizisten "eingekesselt" haben.

      Jetzt kann man aber maximal zwei Kanten abgrasen, wie in der "Musterlösung", indem zwei Polizisten auf den dritten zulaufen. Der Verbrecher kann aber immer noch mit 1/3 W'keit auf der übrigen Kante hocken, und dann sind wir wieder da wo wir angefangen haben.

      Dass man mit 100%iger Sicherheit sagen kann "Der Spack ist jetzt auf dieser Kante" und ihn gleichzeitig eingekesselt hat ist also imo nicht möglich.

      Thurisaz
    • 1
    • 2