ottogal: Mathematik für unterwegs

Ein Reisender hat das Zahlenschloss seines Koffers verriegelt, aber den Code vergessen.
Der besteht aus 3 voneinander unabhängigen Ziffern von 0 bis 9.

Um seinen Koffer wieder zu öffnen, müsste er im schlimmsten Fall (als eine Art "brute force") 1000 Kombinationen durchprobieren.
Er erinnert sich aber, dass die Quersumme der 3 Ziffern seines Codes 11 war.

Frage: Wie viele Kombinationen muss er höchstens probieren, um das Schloss zu öffnen?

Zusatzfrage: Man ermittle diese Anzahl für jede mögliche Quersumme q.

  1. Hallo in die Runde,

    @Gunnar Bittersmann, @Rolf B und @Matthias Apsel haben mir Lösungen zukommen lassen, die ganz unterschiedliche Wege gehen, was sehr interessant ist. Deshalb schlage ich vor, dass ihr sie hier alle öffentlich macht.

    Da meine eigene Lösung für die Quersumme 11 von eurer übereinstimmenden (69 Kombinationen) abwich, hatte ich sie erst noch zu korrigieren. 😟
    (Mein "Widerspruch" an euch war voreilig und vorwitzig - so spiele ich auch Schach: Nach langem Abwägen mache ich den Zug, den ich aus guten Gründen zu allererst verworfen habe...).

    Hier nun meine korrigierte Lösung:



    Wir verwenden im Folgenden die Dreieckszahlen

    $$D(1)=1$$, $$D(2)=3$$, $$D(3)=6$$, $$D(4)=10$$ ...

    Die Dreieckszahl $$D(n)$$ zur Basis $$n$$ ist die Summe der natürlichen Zahlen von $$1$$ bis $$n$$ und errechnet sich nach Gauß zu $$D(n)=\frac{1}{2} n (n+1)$$.


    Seien $$x$$, $$y$$, $$z$$ die drei Ziffern des Codes, $$s$$ ihre Summe.

    (Ich schreibe hier $$s$$ statt $$q$$, weil ich beim Rechnen per Hand immer wieder $$q$$ mit $$9$$ verwechselt hatte.)

    Somit gilt $$x+y=s-z$$ und $$0 \leq s \leq 27$$.

    Wegen $$z \leq 9$$ gilt

    |$$(1)\quad\quad x+y \geq s-9$$|

    und wegen $$z \geq 0$$ gilt

    |$$(2)\quad\quad x+y \leq s$$|


    1. Fall: $$s \leq 9$$

    Dann ist $$s-9 \leq 0$$. Wegen $$x \geq 0$$, $$y \geq 0$$ ist daher die Ungleichung (1) erfüllt.

    Die Punkte $$(x;y)$$, die die Ungleichung (2) erfüllen, liegen unterhalb oder auf der Geraden $$y=-x+s$$.

    Sie bilden die Figur der Dreieckszahl $$D(s+1)$$, ihre Anzahl (also die Anzahl der Kombinationen mit diesen Bedingungen) ist also

    $$k_1=D(s+1)=\frac{1}{2}(s+1)(s+2)$$.

    Beispiel: $$s=5$$ ergibt $$k_1=D(6)=\frac{1}{2} \cdot 6 \cdot 7=21$$.

    Fall1_Bsp.png


    2. Fall: $$s \geq 18$$

    Wir nutzen die Symmetrie der Situation aus: Es gibt genau so viele Kombinationen für die Summe $$s$$ wie für die Summe $$27-s$$.

    Begründung: Man stelle sich vor (o.B.d.A.), die Ziffern auf den Einstellrädern seien so angeordnet, dass je zwei gegenüberliegende sich zu 9 ergänzen:

    Einstellrad.png

    Dann ist klar, dass es z.B. für die Summe $$s=20$$ genau gleich viele Kombinationen gibt wie für die Summe $$s=7$$; denn zur Kombination 794 mit $$s=20$$ gehört die komplementäre Kombination 205 mit $$s=7$$.

    Für $$s \geq 18$$ berechnet man daher die Anzahl der Kombinationen mit $$t=27-s$$ gemäß Fall 1 zu $$k_2=D(t+1)=D(28-s)=\frac{1}{2}(28-s)(29-s)$$.

    Beispiel: $$s=20$$ ergibt $$k_2=D(28-20)=D(8)=\frac{1}{2} \cdot 8 \cdot 9=36$$.


    3. Fall: $$9 < s < 18$$

    Also ist hier $$0 < s-9 < 9$$.

    Die Punkte, die die Ungleichungen (1) und (2) erfüllen, liegen zwischen oder auf den parallelen Geraden

    $$g_1$$: $$y=-x+(s-9)$$ und

    $$g_2$$: $$y=-x+s$$

    Diejenigen von den 100 Punkten der möglichen (x;y)-Paare, die nicht beide Ungleichungen erfüllen, verteilen sich auf zwei Dreieckszahl-Figuren:

    Die untere hat wegen $$g_1(0)=s-9$$ die Basis $$s-9$$ und enthält somit
    $$D(s-9)=\frac{1}{2}(s-9)(s-8)$$ Punkte;
    die obere hat wegen $$g_2(9)=s-9$$ die Basis $$9-(s-9)=18-s$$ und enthält somit
    $$D(18-s)=\frac{1}{2}(18-s)(19-s)$$ Punkte.

    Beides zusammen ergibt

    $$D(s-9)+D(18-s)=\tfrac{1}{2} \left( (s-9)(s-8)+(18-s)(19-s) \right)=$$

    $$=\tfrac{1}{2} \left( s^2-17s+72+342-37s+s^2 \right)=$$

    $$= s^2-27s+207=$$

    $$=207-s(27-s)$$

    Dies ist die Anzahl der Kombinationen, die die Bedingung nicht erfüllen. Die Anzahl der gesuchten Kombinationen ist daher

    $$k_3=100-(207-s(27-s))=s(27-s)-107$$.

    Beispiel: $$s=11$$ ergibt $$k_3=11 \cdot 16 -107=69$$.

    Fall3_Bsp.png



    Diese Aufgabe habe ich mir übrigens beim Warten am Flughafen ausgedacht.
    Praktische Erfahrung war vorhanden: Vor Jahren habe ich mal ein Kofferschloss (ohne Kenntnis der Quersumme) mit mehr als 800 Versuchen geknackt... 😉 (Feyman hätte es sicher schneller geschafft.)

    Beste Grüße
    ottogal

    1. Hallo ottogal,

      ich habe mir die Lösung auf einer Wanderung (Hin und wieder zurück – Bilbo Beutlin) überlegt:

      Wanderweg


      Wenn man sich die Folge der Quersumme q(n) für 0 ≤ n ≤ 999 anschaut, macht die immer dann einen Sprung, wenn sich die Einerstelle von 9 auf 0 ändert. Es gilt q(10k) < q(10k - 1). Es gibt 99 solcher Stellen.

      Also 100 Intervalle, in denen q(n) Teil einer arithmetischen Zahlenfolge mit der Differenz 1 ist. Zunächst kann in jedem dieser Intervalle die Quersumme 11 vorkommen, solange die Summe aus Hunderter- und Zehnerstelle zwischen 2 und 11 einschließlich liegt. Damit fallen folgende Intervalle raus:

      00

      01
      10

      93 84 75 66
      39 48 57

      94 85 76
      49 58 67

      95 86 77
      59 68

      96 87
      69 78

      97 88
      79

      98
      89

      99

      Wenn ich mich nicht verzählt habe sind es 31, damit sind also 69 Zahlenkombinationen zu prüfen.

      PHP angeworfen: Ich hab mich nicht verzählt.

      Bis demnächst
      Matthias

      --
      Pantoffeltierchen haben keine Hobbys.
      1. Hallo Matthias,

        … damit sind also 69 Zahlenkombinationen zu prüfen.

        das letzte mal, als ich ein billiges Zahlenschloss geknackt habe, habe ich weniger als zehn Versuche gebraucht. Hilfreich war dabei nicht die Mathematik, sonder das Wissen über das Innenleben eines einfachen Zahlenschlosses. 😎

        Gruß
        Jürgen

        1. @@JürgenB

          das letzte mal, als ich ein billiges Zahlenschloss geknackt habe, habe ich weniger als zehn Versuche gebraucht. Hilfreich war dabei nicht die Mathematik, sonder das Wissen über das Innenleben eines einfachen Zahlenschlosses. 😎

          Hilfreich: Talkum, Handschuhe, Stethoskop. Guckst du (ab 11:11).

          „Der gute alte Franz!“

          LLAP 🖖

          --
          „Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“ —Kurt Weidemann
    2. Hallo ottogal,

      deine Lösung ist mir zum schnellen Überfliegen zu hoch, ich verstehe kein Wort.

      Matthias Lösung ist clever.

      Meine Lösung war brute force: Ich habe mir erstmal für alle Kombinationen aus 2 Ziffern die Quersummen aufgeschrieben. Dabei habe ich nur die geordneten Paare (x,y) mit x<=y betrachtet, weil ich nachher sowieso Permutationen bilde und keine Duplikate haben will. Es gibt pro Quersumme ein (q=0,18) bis fünf (q=8,9,10) geordneter Zahlenpaare mit dieser Quersumme, insgesamt 1+1+2+2+3+3+4+4+5+5+5+4+4+3+3+2+2+1+1=59 Zahlenpaare. Für jedes dieser Paare habe ich eine 3-er Gruppe von Spalten in Excel aufgemacht, sowie Zeilen für die Quersummen 0-27. Dann habe ich jedes Paar mit den Ziffern 0-9 kombiniert und die Kombination in der Zeile mit der entsprechenden Quersumme eingetragen. Auch hier habe ich darauf geachtet, geordnete Tripel zu erhalten, d.h. wenn die Einzelziffer größer war als die erste Stelle des Paares, habe ich die Kombination nicht gezählt.

      Ein solches Tripel zählt nun für 1, 3 oder 6 mögliche Kombinationen, je nach dem, ob es aus 1, 2 oder 3 unterschiedlichen Ziffern besteht. Mit etwas Excel-Akrobatik kann man das pro Kombination bestimmen.

      D.h. ich habe nun eine Gruppe aus 3 Spalten und 2 Zeilen, die so aussieht:

      z xy _
      _ _  k
      

      z und xy sind Einzelziffer und Zahlenpaar, k die Anzahl der Kombinationen, die sich daraus bilden lassen. k steht eine Zeile tiefer, um Anzahl der Kombinationen für eine Quersumme einfach mit der SUMME-Funktion ermitteln zu können. Mit etwas bedingter Formatierung habe ich die zu zählenden Kombinationen noch hervorgehoben. Der Rest war Copy+Paste, zunächst die 6er Gruppe neunfach wiederholt für z=0 bis z=9, danach diese 3x20 Gruppen eingerahmt und passend in die Quersummenspalten übertragen. Da Excel bei richtigem Einsatz der $ Zeichen die Formeln automatisch anpasst, war die Kopiererei ein No-Brainer.

      Das Ergebnis sieht so aus:

      Betrachtet man nur die Quersummen und die auszuprobierenden Kombis für diese Quersumme, gibt's eine schöne Glocke:

      Quersummen

      Zu doof für Mathe, aber ein Wizard mit Excel 😂

      Rolf

      --
      sumpsi - posui - clusi
    3. @@ottogal

      @Gunnar Bittersmann, @Rolf B und @Matthias Apsel haben mir Lösungen zukommen lassen, die ganz unterschiedliche Wege gehen, was sehr interessant ist. Deshalb schlage ich vor, dass ihr sie hier alle öffentlich macht.

      Dann lass ich mich mal nicht lumpen.

      Es gibt folgende Kombinationen abc mit a ≤ b ≤ c und a + b + c = 11: 029, 038, 047, 056, 128, 137, 146, 236, 245 und 119, 155, 227, 335, 344.

      Ich hab sie vorsorglich schon mal in zwei Gruppen sortiert. Die in der ersten Gruppe haben alle Ziffern verschieden; durch Vertauschen gibt das für jede der 9 Kombinationen 3! = 6 Permutationen. Die in der zweiten Gruppe haben jeweils eine Ziffer doppelt; durch Vertauschen gibt das für jede der 5 Kombinationen 3! / 2! = 3 Permutationen.

      Die Gesamtzahl der Kombinationen ist also 9 × 6 + 5 × 3 = 54 + 15 = 69.

      Wie man das auf beliebige Quersummen verallgemeinern könnte, weiß ich jetzt auch nicht.


      Zuvor hatte ich mit dem Holzhammer auf das Problem draufgehauen: ein kleines Script, das alle Kombinationen von 000 bis 999 (d.h. die Zahlen von 0 bis 999) durchgeht, jeweils die Quersumme berechnet und die Häufigkeit des Auftretens der möglichen Quersummen von 0 bis 27 zählt.

      Mit dem meter-Element hat man dann auch gleich ein Balkendiagramm.

      LLAP 🖖

      --
      „Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“ —Kurt Weidemann
    4. Vor Jahren habe ich mal ein Kofferschloss (ohne Kenntnis der Quersumme) mit mehr als 800 Versuchen geknackt...

      Bei allen Kofferschlössern die mir bisher untergekommen sind, konnte man die Lösung in wenigen Minuten ertasten. Die Zahlen die sich dabei ergeben sind völlig uninteressant 😉

      1. Hallo pl,

        in wenigen Minuten

        das war dann aber schon ein Gutes.

        Normalerweise gibt man ordentlich Druck auf den Öffnungsknopf und dreht, und ratz fatz rastet eine Zahl nach der anderen ein, weil diese Billigdinger einfach zu wacklig aufgebaut sind.

        Rolf

        --
        sumpsi - posui - clusi