% Preamble
\documentclass{article}
\usepackage[latin1]{inputenc}
\usepackage{german}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage[slant]{complexity}
\usepackage{listings}

% Document
\begin{document}

\sffamily

\begin{titlepage}

\thispagestyle{empty}

\begin{center}
\line(1,0){250}
\end{center}

\begin{center}
\Huge \textbf{MATHEMATIQ}
\end{center}

\begin{center}
\line(1,0){250}
\end{center}

\begin{center}
\Large Der Newsletter der MathSIG
\\ \normalsize (Interessensgruppe innerhalb der Mensa \"{O}sterreich)
\end{center}

\begin{center}
\Large Ausgabe 29
\end{center}

\begin{center}
\normalsize \url{http://www.hugi.scene.org/adok/mensa/mathsig/}
\end{center}

\end{titlepage}

\newpage

\begin{center}
\Large \textbf{Editorial}
\end{center}
\normalsize Liebe Leserinnen und Leser!
\\
\\ Dies ist die neunundzwanzigste Ausgabe von MATHEMATIQ, dem Newsletter der MathSIG. Die MathSIG wurde gegr\"{u}ndet, um die spezifischen Interessen mathematisch hochbegabter Menschen zu f\"{o}rdern. In erster Linie soll sie sich also den Themengebieten Mathematik, Informatik, Physik und Philosophie widmen. Beitr\"{a}ge von Lesern sind herzlich willkommen. Wenn in ihnen mathematische Sonderzeichen vorkommen, bitte ich aber, sie zwecks m\"{o}glichst einfacher und fehlerfreier Formatierung im \TeX-Format einzusenden. Als Vorlage ist eine Fassung des jeweils aktuellen Newsletters im \TeX-Format auf Anfrage bei mir erh\"{a}ltlich. Au\ss{}er Artikeln sind nat\"{u}rlich auch Illustrationen f\"{u}r das Titelblatt willkommen. Die Rechte an diesen m\"{u}ssen aber eindeutig bei euch selbst liegen, Kopieren von Bildern aus dem Internet ist nicht erlaubt.
\\
\\ \textbf{Hinweis: Autoren sind f\"{u}r den Inhalt ihrer Artikel oder Werke selbst verantwortlich. Die in MATHEMATIQ ver\"{o}ffentlichten Beitr\"{a}ge widerspiegeln ausschlie\ss{}lich die Meinung ihrer Autoren und nicht jene des Vereins Mensa. Die Zusendung von Beitr\"{a}gen gilt auch als Einverst\"{a}ndnis zu deren Ver\"{o}ffentlichung in MATHEMATIQ.}
\\
\\ \textbf{Diese Ausgabe} stellt einen Wiederabdruck des Artikels ``Zahlenreihen mit Computern l\"{o}sen'' dar, der einmal in TOPIQ ver\"{o}ffentlicht worden ist. Das ist notwendig geworden, weil die alten TOPIQ-Ausgaben auf der Mensa-Homepage nicht mehr \"{o}ffentlich zug\"{a}nglich sind.
\\
\\ In diesem Sinne: Viel Spa\ss{} beim Lesen und Lernen!
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\newpage

\begin{center}
\Large \textbf{Zahlenreihen mit Computern l\"{o}sen}
\end{center}
\normalsize In gebr\"{a}uchlichen Intelligenztests, wie auch im Mensa-Aufnahmetest, kommen h\"{a}ufig Zahlenreihen vor, die man vervollst\"{a}ndigen muss. Beispielsweise 3, 5, 8, 12 - wie lautet die n\"{a}chste Zahl? Wenn es ein Zeichen von Intelligenz ist, wenn Menschen diese Aufgaben l\"{o}sen k\"{o}nnen, stellt sich die Frage, ob es sich um eine spezifisch menschliche Eigenschaft handelt. Oder k\"{o}nnen auch Computer Zahlenreihen l\"{o}sen? Die Antwort ist: ja, sie k\"{o}nnen es, wenn sie entsprechend programmiert worden sind. Im folgenden Artikel m\"{o}chte ich zeigen, wie es geht.
\\
\\ Beginnen wir mit ganz kurzen Zahlenreihen, wo nur zwei Zahlen vorgegeben sind. 1, 2 - wie lautet die n\"{a}chste in der Reihe? Es gibt zwei M\"{o}glichkeiten: 3 oder 4. Vorerst m\"{o}chten wir uns auf additive Zahlenreihen beschr\"{a}nken; in diesem Fall w\"{a}re die 3 richtig. Wenn die Zahlenreihe allgemein a, b lautet, wie kommt man dann auf c? Man rechnet c = b + (b - a) = 2b - a. Das w\"{a}re eine allgemeine L\"{o}sungformel f\"{u}r additive Zahlenreihen, die nur aus zwei Zahlen bestehen. Wenn wir nun drei Zahlen haben, a, b, c, wie berechnen wir dann die vierte Zahl d? Beispiel: 1, 2, 3. Nun, in diesem Fall gibt es zwei M\"{o}glichkeiten: d = c + (c - b) = 2c - b oder d = c + (b - a). Beide f\"{u}hren zum selben Ergebnis. Das gilt aber nur, weil die Differenz c - b gleich b - a ist. Was w\"{a}re, wenn sie verschieden w\"{a}ren? Beispiel: 1, 2, 4. Da wir davon ausgehen, dass es sich um eine additive Zahlenreihe handelt, m\"{u}sste das Ergebnis 7 lauten (2 - 1 = 1, 4 - 2 = 2, also m\"{u}ssen wir 4 + 3 = 7 rechnen). Symbolisch haben wir also gerechnet: d = c + (c - b) + ((c - b) - (b - a)) = 3(c - b) + a. Dies ist die allgemeine Formel f\"{u}r additive Zahlenreihen, die aus drei Zahlen bestehen. Damit k\"{o}nnen wir jede Zahlenreihe dieser Art l\"{o}sen.
\\
\\ F\"{u}r Zahlenreihen, die aus vier oder mehr Zahlen bestehen, lassen sich analoge Formeln berechnen. Um das Ganze etwas anschaulicher zu gestalten, legen wir folgende Notation fest: b` = b - a; c` = c - b; usw., weiters: c`` = c` - b`, d`` = d` - c` usw. Bei einer Zahlenreihe, die aus vier Zahlen besteht, ergibt sich dann als L\"{o}sungsformel: e = d + d` + d`` + d```.
\\
\\ Wenn man einen Computer programmieren will, damit er in der Lage ist, additive Zahlenreihen selbstt\"{a}tig zu l\"{o}sen, gibt es zwei M\"{o}glichkeiten: Entweder man berechnet m\"{o}glichst einfache Formeln f\"{u}r Zahlenreihen aus zwei, drei, vier,... Zahlen. Dann gen\"{u}gt es, in diese Formeln einzusetzen. Das macht die Berechnung sehr effizient. Oder man programmiert den Computer so, damit er in der Lage ist, Zahlenreihen zu l\"{o}sen, die aus einer beliebigen Anzahl von Zahlen bestehen. In diesem Fall speichert man die letzte Zahl (z. B. f) ab, berechnet dann b` bis f` und addiert f` zum Ergebnis, berechnet weiters b`` bis f`` usw. Da man die Zahlen der aktuellen Generation \"{u}berschreiben kann (sobald man f zwischengespeichert hat, kann man f mit f` \"{u}berschreiben, danach e mit e` usw.), entsteht kein zus\"{a}tzlicher Speicherbedarf, doch dauert die Berechnung eben l\"{a}nger. Die Anzahl der Subtraktionen, die durchgef\"{u}hrt werden m\"{u}ssen, betr\"{a}gt (wenn n die Anzahl der vorgegebenen Zahlen ist) n(n - 1)/2, in der Sprache der Informatiker also $O(n^2)$. Das ist nicht gerade effizient, aber daf\"{u}r erlaubt dieser Ansatz, mit beliebig langen Zahlenreihen zu arbeiten.
\\
\\ Dieser zweite Ansatz ist aber auch hilfreich, wenn wir unser Programm erg\"{a}nzen wollen, dass es auch mit Zahlenreihen zurecht kommt, die multiplikative Elemente enthalten. Wenn man 1, 2, 4 als multiplikative Zahlenreihe behandelt, ist die L\"{o}sung nicht 7, sondern 8. Darauf kommt man leicht, indem man genauso wie vorhin verf\"{a}hrt, aber nicht Differenzen, sondern Quotienten berechnet und das Ergebnis nicht addiert, sondern multipliziert. Rein multiplikative Zahlenreihen zu l\"{o}sen, ist also auch kein Problem. Wie l\"{o}st man aber nun 1, 3, 7 oder 1, 4, 10? Zun\"{a}chst sollte man den multiplikativen Ansatz versuchen. Da aber 7 nicht ohne Rest durch 3 teilbar ist (und 10 nicht durch 4), muss man additiv vorgehen. Es ergeben sich die Differenzen 2, 4 bzw. 3, 6. Jetzt k\"{o}nnen wir multiplikativ vorgehen. Es ergibt sich also als L\"{o}sungformel f\"{u}r die erste Reihe d = 7 + 4 * 2 = 15 und f\"{u}r die zweite Reihe d = 10 + 6 * 2 = 22. Indem wir bei jedem Schritt zuerst den multiplikativen Ansatz versuchen und, wenn dieser nicht geht, additiv vorgehen, k\"{o}nnen wir also solche gemischten Zahlenreihen l\"{o}sen. Selbstverst\"{a}ndlich gilt aber Punktrechnung vor Strichrechnung. Wir k\"{o}nnen nicht, wie bei rein additiven bzw. rein multiplikativen Zahlenreihen, einfach die Differenz c` zu c hinzuaddieren, sondern wir m\"{u}ssen die Differenz c` zuerst mit dem Quotienten c`` multiplizieren. Das kann man realisieren, indem man mit einem primitiven Stack arbeitet. Man speichert in der Variablen r1 den Wert von c zwischen, dann in r2 den Wert der Differenz c`. W\"{u}rde im n\"{a}chsten Schritt wieder der additive Ansatz erfolgen, k\"{o}nnte man den Wert von r2 zu r1 dazuaddieren und c`` in r2 speichern. Da aber nun multiplikativ vorgegangen wird, muss r2 mit c`` multipliziert werden und erst im n\"{a}chsten Schritt r2 zu r1 addiert werden.
\\
\\ Man sieht also, dass manches von dem, was der Mensch f\"{u}r spezifisch menschliche Talente hielt, auch von Computern bewerkstelligt werden kann - aber es bedarf immer noch eines klugen Menschen, der in der Lage ist, den Computer entsprechend zu programmieren.
\begin{flushright}
Claus D. Volko, cdvolko@gmail.com
\end{flushright}

\end{document}
