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.