Mar 18, 2008 - Weiteres Matherätsel: die zwei Kristallkugeln

Ein weiteres Rätsel aus der Liste mit Interviewfragen für Mathematikerjobs vom letzten mal hat mir keine Ruhe gelassen, nämlich die

Aufgabe 2: Mit zwei identischen Kristallkugeln soll bei einem 100-stöckigen Hochhaus ermittelt werden, ab welchem Stock die Kristallkugeln kaputtgehen, wenn sie aus dieser Höher fallengelassen werden. Wieviele Messungen (d.h. Fallenlassen einer Kugel) muss man schlimmstenfalls durchführen, d.h. was ist die beste Strategie für die Messungen, gemessen am jeweils schlimmsten Fall (d.h. die maximale Anzahl, die bei einer Strategie benötigt werden)? Beide Kugeln dürfen kaputtgehen, aber die Antwort muss korrekt sein.

Ausnahmsweise ist die Antwort mal weder "binäre Suche" noch "Hashtabelle" (das sind die häufigsten Fragen bei Informatiker-Jobinterviews). Nachdem mir die Antwort nicht gleich eingefallen ist, habe ich auch hierfür ein Scheme-Programm geschrieben, welches durch "brute force" die beste Lösung ermitteln sollte. Dummerweise braucht das Programm aber zu lange, es läuft jetzt schon seit ein paar Stunden und hat noch keine Antwort ausgespuckt. Nachdem ich es an kleineren Fällen ausprobiert habe (z.b. 10-stöckiges Hochhause), ist mir aber doch noch eingefallen, wie ich die Aufgabe auf theoretischem Weg lösen kann (im nachhinein war es natürlich gar nicht so schwer...). Es folgt meine Lösung, wer es selbst probieren will, sollte also ab hier nicht weiterlesen.

Lösung: Ich beweise gleich Allgemein für n-stöckige Hochhäuser. Eine Strategie sei eine Folge von k Schritten s_1, s_2,...,s_k mit s_1 + s_2 + ... + s_k = n, so zu interpretieren, dass im ersten Schritt eine Kugel aus dem s_1-ten Stock geworfen wird. Zerbricht sie nicht, wird sie im zweiten Schritt aus dem s_1 + s_2-ten Stock geworfen, und so weiter. Sollte die erste Kugel zerbrechen, muss mit der zweiten Kugel sequentiell weitergetestet werden, da sonst das richtige Stockwerk nicht mit Sicherheit ermittelt werden könnte. Zerbricht die erste Kugel also im Schritt i, müssen mit der zweiten Kugel noch maximal s_i - 1 Tests durchgeführt werden, die Stockwerke s_1 + ... + s_(i-1) + 1 bist s_1 + ... + s_i - 1 müssen getestet werden.

Nun behaupte ich

I) Sei Max die maximal nötige Anzahl an Messungen. Dann gibt es eine optimale Strategie mit s_1 = Max.

Beweis: Zerbricht die erste Kugel im Stockwerk s_1 = Max, so sind noch maximal Max-1 Messungen mit der zweiten Kugel nötig, also maximal Max Messungen, falls die Kugel in s_1 zerbricht. Desweiteren sind für weniger Stockwerke auf keinen Fall mehr Messungen nötig, d.h. das Vergrössern von s_1 kann den "schlimmsten Fall" für die restlichen Messungen nicht verschlechtern, da ja weniger zu testende Stockwerke übrigbleiben (könnte man mathematisch exakter Formulieren, aber das hier ist ja nur ein Blog).

Ausserdem gilt

II) Es gibt eine optimale Strategie s_1,...,s_k mit s_1 = Max und s_(i+1) = s_i +1 für i < k und s_k < s_(k-1).

Beweis: nach I) können wir von s_1 = Max ausgehen. Daher ist s_2 < s_1. Analog zum Beweise von I) folgt, dass s_2 auf Max-1 erhöht werden kann, und so weiter für s_3,...,s_(k-1). s_k muss als Sonderfall nur so gross sein, wie Stockwerke nach den vorherigen Schritten übrig sind. (Wieder Erspare ich mir im Sinne der Kürze die exakte mathematische Formulierung).

Aus I) und II) folgt, dass es eine optimale Strategie der Form Max, Max-1, ..., Max-k-2, s_k gibt mit s_k < Max-k-2. Nun ist ja 1 + 2 +...+Max eine arithmetische Folge mit Wert Max*(Max+1)/2. Die Gleichung Max*(Max+1)/2 = n lässt sich lösen (quadratische Gleichung Max²+Max-2n = 0). Für n = 100 ist die Lösung Max = 13,65..., da Max eine ganze Zahl sein muss ergibt sich als optimale Strategie 14,13,12,11,10,9,8,7,6,5,4,1, mit der maximal 14 Messungen benötigt werden.

Praktische Anwendungen sind mir nicht bekannt...

Mar 17, 2008 - Scheme-Übung mit einem Matherätsel (das Summe- und Produkt-Rätsel)

Da Anne Rice es in ihren Romanen unterschlagen hat, ist es wenig bekannt, aber es gibt wohl einen Volksglauben, demzufolge Vampire einen Zählzwang haben. Neben Knoblauch empfiehlt sich zur Vampirabwehr also eine Handvoll Reis in der Tasche, die man einem Vampir vor die Füsse werfen kann. Während das Monster versucht, die Reiskörner zu zählen, kann man bequem das Weite suchen. Laut diesem Artikel wurden in Rumänien deshalb tatsächlich manchmal Gefässe mit Getreidesamen als Grabbeilagen verwendet, um die Toten von den Gedanken an die Wiederauferstehung abzulenken. Eine amüsante Referenz auf diese Legende ist auch Graf Zahl aus der Sesamstraße.

So wie Vampire mit dem Reis, kann man Hacker wohl mit Logikrätseln packen. Auf den Hacker News werden regelmässig Links zu neuen Rätselseiten gepostet, die dann die Aufmerksamkeit eines nicht unerheblichen Teils der Hackerpopulation für ein paar Stunden absorbieren dürften. Vielleicht gar keine schlechte Strategie, um die Konkurrenz auszubremsen: ab und zu ein paar neue Rätsel veröffentlichen? Zuletzt im Angebot: eine Liste mit angeblichen Interviewfragen für Mathematik-Jobs.

Eigentlich hatte ich diesmal gar keine Lust, mich abzulenken, aber es kam wie es kommen musste: in einer etwas müderen Minute habe ich mir die Rätsel doch angeschaut und fand einige dann doch ganz interessant, z.B. #2. Warnung vorweg: einige der Aufgaben sind unlösbar, und ich meine z.B. auch für Aufgabe 10 einen Beweis erdacht zu haben, dass sich ein Quadrat NICHT mit endlich vielen unterschiedlichen Quadraten pflastern lässt, anders als dort behauptet wird (UPDATE: meine Beweisidee war falsch, es gibt tatsächlich perfekte Quadratzerlegungen). Das "infamous 2-envelope-problem" (Aufgabe 9) scheint auch sehr umstritten zu sein, ich zweifele bislang noch daran, dass es eine Lösung gibt.

Der Lösungsweg für Aufgabe 13 erschien mir recht offensichtlich, aber mit viel Fleissarbeit verbunden. Da ich schon seit einiger Zeit wieder Scheme lernen wollte (vor 8 Jahren konnte ich es schon mal), beschloss ich, die Lösung als Übung in Scheme zu implementieren. Allerdings habe ich dann doch länger dafür gebraucht als gedacht, zumal ich auch erst wieder das Arbeiten mit Emacs lernen musste.

In der Zwischenzeit ist die dazugehörige Diskussion bei Hacker News längst wieder Schnee von Gestern, so dass mir nur noch dieses Blog bleibt, um mit meiner Lösung zu prahlen.

Im folgenden die Lösung, wer es selber probieren will, sollte also nicht weiterlesen. Der Ersteller der Rätselliste hat das Rätsel anscheinend im Blog von Lance Fortnow gefunden, dort finden sich auch Links zur Geschichte des Rätsels, und in den Kommentaren auch Links zu Lösungen, die ich aber nicht überprüft habe.

Aufgabe (Summe- und Produkt-Rätsel): Gegeben sind zwei ganze Zahlen x und y mit den Eigenschaften 1<x<y und x+y <= 100. Person A erfährt nur die Summe x+y, Person B nur das Produkt x*y. A und B tauschen sich daraufhin wahrheitsgemäss aus wie folgt:

1. B sagt er kennt die Zahlen x und y nicht.
2. A sagt, dass er dies schon wusste.
3. B verkündet daraufhin, dass er x und y dann kennt.
4. In Folge kennt auch A die Zahlen x und y

Gesucht sind die Zahlen x und y.

Lösungsansatz:
Aus Aussage 1 folgt, dass x*y sich nicht nur auf eine Weise als Produkt zweier Zahlen grösser als 1 darstellen lässt, mit anderen Worten, x und y sind nicht beide Primzahlen und es ist auch nicht y = x*x mit x prim.

Aus Aussage 2 folgt, dass x+y nicht als Summe zweier Primzahlen (oder x+x*x mit x Prim) dargestellt werden kann. Im ersten Schritt gilt es also eine Liste der Zahlen zwischen 1 und 100 zu erstellen, die nicht als Summe zweier Primzahlen dargestellt werden kann (den Fall x+x*x erwähne ich in Zukunft nicht mehr, er muss korrekterweise aber wohl auch untersucht werden). Als niedrigste Zahl findet man hier z.B. die 11 = 2+9 = 3+8 = 4+7 = 5+6. Wäre x+y=11, wüsste A also zumindest, dass x*y eine der Zahlen 18 = 2*9, 24 = 3*8, 28 = 4*7 oder 30 = 5*6 sein müsste.

Was erfahren wir weiter aus Aussage 3? Nun, B kennt die möglichen Zwei-Faktor-Darstellungen der Zahl x*y und hat daher seinerseits eine Liste der Kandidaten für die Zahl x+y. Aus Aussage 3 folgt, dass nur genau einer dieser Kandidaten die Eigenschaft hat, nicht als Summe zweier Primzahlen dargestellt werden zu können. Beispiel: angenommen x*y = 30 = 3*10 = 6*5 = 2*15, dann wüsste B, dass x+y eine der Zahlen 13 = 3+10, 11 = 6+5 oder 17 = 2*15 sein muss. Sowohl 11 als auch 17 können aber nicht als Summe zweier Primzahlen dargestellt werden (weiss man durch Fleissarbeit), daher scheidet 30 als Kandidat für x*y aus. Wäre x*y = 18 = 3*6 = 2*9, so wüsste B dass nur 11 und 9 mögliche Kandidaten für x+y sind. 9 = 2+7 ist als Summe zweier Primzahlen darstellbar, also wüsste B in diesem Fall, dass x+y = 11 sein muss.

Verbleibt noch die Aussage 4. Aus dieser folgt, dass nur einer der möglichen Kandidaten für x*y, die A kennt, für B einen eindeutigen Rückschluss auf x+y zulassen würde. Bleiben wir beim Beispiel x+y = 11. Wie oben schon beschrieben, würde A dann die Kandidaten 18, 24, 28 und 30 für x*y kennen (30 wurde durch Aussage 3 schon eliminiert). Wir haben bereits gesehen, dass B eindeutig auf 11 schliessen könnte, wenn x*y = 18 wäre. Was, wenn x*y = 24 = 2*12 = 4*6 = 8*3? B würde als Kandidaten demnach 14 = 2+12, 10 = 4+6 und 11 = 8+3 in Betracht ziehen. Davon sind 14 = 3+11 und 10 = 3+7 als Summe zweier Primzahlen darstellbar, so dass B wieder x+y = 11 folgern könnte. Dies steht im Wiederspruch zur Aussage 4, denn sowohl 18 als auch 24 würden B die Aussage 3 erlauben. Jetzt wissen wir, dass x+y != 11 ist (!= bedeutet "ungleich"), wir müssen also weitersuchen.

Diese Erkentnisse reichen denn auch aus, um ein Programm zur Lösungsfindung zu schreiben. Zuvor aber noch ein paar Überlegungen zur manuellen Lösung, wobei ich da nicht allzulange über Abkürzungen nachgedacht habe. Woran ich mich noch dunkel erinnern konnte, ist die Goldbach'sche Vermutung: jede gerade Zahl grösser als 2 kann als Summe zweier Primzahlen geschrieben werden. Dies wurde zwar noch nicht bewiesen, für die Zahlen unter 100 aber schon verifiziert. Bei der Suche nach Kandidaten für x+y kann man also schon mal alle geraden Zahlen auslassen. Bei den ungeraden Zahlen n reicht es wiederum zu überprüfen, ob n-2 eine Primzahl ist - einer der Summanden in einer Primzahlsumme müsste auf jeden Fall 2 sein, da die Summe zweier ungerader Primzahlen gerade wäre.

Damit kann man die Kandidaten für x+y vermutlich relativ schnell ermitteln, laut meinem Programm gibt es aber 24 solche Zahlen, zu viel Rechnerei für meinen Geschmack. Für jede dieser Zahlen müsste man dann mindestens soviele Produkte ihrer Zwei-Summanden-Darstellung durchtesten, bis man mindestens zwei gefunden hat, die Aussage 3 erlauben würden, wodurch man sie eliminieren könnte. Tricks zur Abkürzung dieser Aufgabe sind mir keine eingefallen (habe auch nicht weiter drüber nachgedacht), würde mich aber interessieren, falls jemand was weiss. Theoretisch dürfte dann nur noch ein Kandidat für x+y übrigbleiben, womit man die Lösung in der Tasche hätte. Um es nicht zu spannend zu machen: so war es denn auch tatsächlich. Andererseits könnte man aus der Lösbarkeit der Aufgabe auch Folgern, dass nur eine Zahl übrig bleibt, und daher bei der ersten Lösung aufhören weiterzurechnen. Wie die endgültige Lösung zeigt, wäre die Aufgabe auf diesem Weg doch auch von Hand lösbar gewesen.

Im folgenden also mein Scheme-Programm, geschrieben für MzScheme. Wie gesagt, es wurde leider deutlich komplizierter, als ich gehofft hatte. Sicher liegt dies auch zum Teil an meiner Unerfahrenheit mit Scheme, nachdem es immer länger dauerte, hatte ich am Ende auch keine Geduld mehr, um den Code zu schönen. Lösung nach dem Code.

;; 1 < x < y
;; x+y <= 100
;; A know x+y
;; B knows x*y
;;
;; A says doesn't know x and y
;; B says knew that A doesn't know
;; A says then knows
;; B says then knows

;; strategy: find number that is not sum of two primes
;; then check products of all sums making that number
;; factorize, build possible sums of combinations of factors
;; only one should have exactly one result that is not sum of two primes. 

(define (prime-factors n)
  (let ((root (sqrt n)))
    (let loop ((p 2))
      (cond 
       ((> p root) (list n))
       ((= 0 (remainder n p)) (cons p (prime-factors (/ n p))))
       (else (loop (+ p 1)))))))


;;inefficient, but throwaway, so I don't care
(define (prime? p)
  (= p (car (prime-factors p))))

;could be made simpler by using Goldbach conjecture (which is verified for n <= 100): just check uneven numbers,
;hence only check if n-2 is prime
;but this works, too
;update: also check that not sum of p+p*p with p prime
(define (has-2-prime-summands? n)
  (let ((half-n (/ n 2)))
    (let loop ((s 2))
      (if (> s half-n)
        #f
      (if (and (prime? s) (or (prime? (- n s)) (= (- n s) (* s s))))
          #t
          (loop (+ s 1)))))))

;only sums <= 100
(define (sums-of-two-factors n)
  (let ((sums (make-hash-table 'equal)))
    (let collect-sums ((factors (prime-factors n))
               (summands (cons 1 1)))
      (let* ((factor (car factors))
         (summands1 (cons (* (car summands) factor) (cdr summands)))
         (summands2 (cons (car summands) (* (cdr summands) factor)))
         (sum1 (+ (car summands1) (cdr summands1)))
         (sum2 (+ (car summands2) (cdr summands2))))
    (cond 
     ((= 1 (length factors))
      (when (and (<= sum1 100) (> (cdr summands1) 1)) (hash-table-put! sums sum1 summands1))
      (when (and (<= sum2 100) (> (car summands2) 1)) (hash-table-put! sums sum2 summands2)))
     (else (collect-sums (cdr factors) summands1) 
           (collect-sums (cdr factors) summands2)))))
    sums))

(define (list-sums sums-table)
  (hash-table-map sums-table cons))

(define (count-candidate-sums list-of-sums)
  (apply + (map (lambda (sum) (if (has-2-prime-summands? (car sum)) 0 1)) list-of-sums)))

(define (solution? n)
  ;count products of summands that have only one sum of factors that is a non-prime-sum candidate
  (let ((count 0)
    (solution #f)
    (half-n (/ n 2)))
    (let loop ((a 2))
      (if (> a half-n)
      (if (= 1 count) solution #f)
      (let* ((product (* a (- n a)))
         (list-of-sums (list-sums (sums-of-two-factors product)))
         (count-of-candidates (count-candidate-sums list-of-sums)))
        ;(display (list product "has sums " list-of-sums))
        ;(newline)
        (cond 
         ((= 1 count-of-candidates)
          (begin 
        (set! count (+ count 1))
        (set! solution (list product list-of-sums))
        (loop (+ a 1))))
         (else (loop (+ a 1)))))))))

(define (check-candidates)
  (let ((count 0))
    (let loop ((n 4))
      (if (> n 100)
      count
      (begin
        (when (not (has-2-prime-summands? n))
          (set! count (+ count 1))
          (display (list "checking candidate" n))
          (newline)
          (let ((solution (solution? n)))
            (when solution
              (display (list "solution" n solution))
              (newline))))
        (loop (+ n 1)))))))

(check-candidates)

Zur Verschönerung der Ausgabe hatte ich auch keine Geduld mehr, der Zeile "(solution 17 (52 ((17 13 . 4) (28 2 . 26))))" entnehme ich aber, dass x+y = 17 und x*y = 52, und x = 4 und y = 13 die gewünschten Zahlen sind. Tja, hätte ich doch nur etwas länger von Hand gerechnet, 17 wäre nach 11 gleich der nächste Kandidate gewesen, so dass die Lösung doch relativ schnell zu finden gewesen wäre.

Feb 24, 2008 - Flash-Adventures

Die folgenden Flash-Adventures sind zwar schon etwas Älter, doch ich bin erst kürzlich auf sie gestossen:

Samorost und The Quest for The Rest von Amanita Design faszinieren mich durch ihre melancholisch-surreale Stimmung. Die Spiele sind nicht schwer zu lösen und fast eher interaktive Geschichten als richtige Spiele.

Die Hapland-Spiele von foon.co.uk sind dagegen richtige Rätsel, an denen man auch mehrere Tage knabbern kann. Dabei spielt sich alles nur auf einem einzigen "Screen" ab. Vorsicht, schwarzer Humor! Ich finde das Spielprinzip aber sehr erfrischend, denn es ist nicht nur eine vordefinierte Folge von Ereignissen, die der Spieler durch die passenden Clicks weitertreibt, sondern der Spieler kann sich auch in eine unerwünschte Lage bringen, so dass er von vorne Anfangen muss. Meistens gehen die Aktionen des Spielers auf makabere Weise schief - die Spielwelt fühlt sich dadurch aber viel lebendiger an als sonst in Spielen üblich.