Hier die Auflösung des Weihnachtsrätsels.

Teil I

Aufgabe 1

vieledreiecke
Wieviele Dreiecke sind im Bild?

Lösung: Es sind 27 Dreiecke: 20 mit der Spitze nach oben, 7 mit der Spitze nach unten.

Aufgabe 2

Finde alle natürlichen Zahlen n , welche die folgende Gleichung erfüllen:

\frac{1}{2}\sqrt{2+\sqrt{2+\sqrt{2}}}=\cos(\frac{\pi}{n})

Lösung: Weil der Kosinus zwischen 0 und pi/2 monoton fallend ist, kann man mit einem Taschenrechner leicht überprüfen, dass nur n=16 in Frage kommen kann. (-16 ist keine Lösung weil keine natürliche Zahl). Dass n=16 nicht nur ungefähr sondern tatsächlich die Aufgabe löst zeigt man mit der Formel cos(2x)=2\cos^2(x)-1 , aus der cos(y)=\frac{1}{2}\sqrt{2+2cos(2y)} folgt. Man erhält cos\frac{\pi}{4}=\frac{1}{2}\sqrt{2}, cos\frac{\pi}{8}=\frac{1}{2}\sqrt{2+\sqrt{2}}, cos\frac{\pi}{16}=\frac{1}{2}\sqrt{2+\sqrt{2+\sqrt{2}}}

Aufgabe 3

Gibt es eine Menge von 5 Personen, so dass es weder 3 Leute gibt, die sich (paarweise) nicht kennen, noch 3 Leute, die sich alle kennen?

Lösung: Das Bild zeigt eine Färbung der Kanten zwischen 5 Punkten mit den Kanten Rot und Blau. Wie man sieht, gibt es weder ein rotes Dreieck noch ein blaues Dreieck. Wenn man Rot als “kennen sich” und blau als “kennen sich nicht” interpretiert, gibt es weder 3 Leute, die sich kennen noch 3 Leute, die sich nicht kennen.

210px-RamseyTheory_K5_no_mono_K3

Teil II

Aufgabe 1

Wieviele unterschiedliche Würfel mit den Zahlen 1 bis 6 gibt es?

(Dabei sollen zwei Würfel als unterschiedlich gelten, wenn sie sich nicht durch eine Drehung ineinander überführen lassen. Gespiegelte Würfel gelten also als unterschiedlich. Und es geht nur um die Numerierung der Seitenflächen mit Zahlen 1-6, nicht wie das Bild suggerieren könnte darum, wie die Punkte auf den Seitenflächen angeordnet sind.)
dice_games

Lösung: Es gibt 30 Würfel. Eine der Seitenflächen muss die 1 sein, für die gegenüberliegende gibt es 5 Möglichkeiten. Dann kann man (modulo Drehungen) für eine der 4 verbleibenden Flächen eine beliebige der übrigen Zahlen haben und behält 6 Möglichkeiten für die anderen.

Aufgabe 2

Sei Fk die durch

F_1=F_2=1, F_{n+1}=F_n+F_{n-1}
für alle n\ge 1

definierte Folge. Berechne \sum_{k=1}^\infty \frac{F_k}{10^k} .

Lösung: Das Ergebnis ist 10/89. Falls man die Formel für die Fibonacci-Folge nicht kennt, kann man sie mit dem Ansatz F_n=c_1t_1^n+c_2t_2^n bestimmen. Weil t1/10 und t2/10 beide kleiner als 1 sind, konvergieren die geometrischen Reihen und man kann die Summenformel für geometrische Reihen verwenden.

Aufgabe 3

Ist es möglich, sieben Teilmengen M_1,M_2,\ldots,M_7\subset M aus einer sieben-elementigen Menge M=\left\{x_1,x_2,\ldots,x_7\right\} so auszuwählen, dass
– es zu je zwei Elementen x_i\not=x_j eine eindeutige Menge M_k mit \left\{x_i,x_j\right\}\subset M_k gibt,
– zu je zwei unterschiedlichen Teilmengen M_i\not=M_j der Durchschnitt M_i\cap M_j aus genau einem Element besteht?

Lösung: Ein Beispiel ist die Fano-Ebene im Bild unten. Ein anderes wäre eine aus 6 Punkten bestehende Gerade, für die jeder Punkt noch einmal mit dem siebenten Punkt eine Gerade bildet. Also M_1=\left\{x_1,\ldots,x_6\right\}, M_2=\left\{x_1,x_7\right\},\ldots, M_7=\left\{x_6,x_7\right\} .
220px-Fano_plane

Aufgabe 1

Finde die kleinste natürliche Zahl, die sich nicht in der Form x^2+2y^2+5z^2+5w^2 mit ganzen Zahlen x,y,z,w darstellen läßt.

Lösung: Die gesuchte Zahl ist 15. Man prüft leicht nach, dass es für alle kleineren Zahlen Lösungen gibt. Und dass es für 15 keine gibt, sieht man ebenfalls durch systematisches Durchgehen der endlich vielen Möglichkeiten.

Aufgabe 2

Die Eulersche Phi-Funktion φ(n) einer natürlichen Zahl n ist die Anzahl aller zu n teilerfremden natürlichen Zahlen, die kleiner als n sind. Zum Beispiel ist φ(p)=p-1 für eine Primzahl p, allgemeiner φ(pk)=pk-1(p-1) falls p eine Primzahl und k eine natürliche Zahl ist, und es ist φ(mn)=φ(m)φ(n) falls m,n teilerfremd sind.

Man finde alle Lösungen von \phi(\phi(n))=22

Lösung: Die Lösungen sind 47 und 94. Aus der Formel mit der Primfaktorenzerlegung sieht man, dass φ(x)=22 nur die Lösungen x=23 und x=46 hat. φ(n)=23 hat keine Lösungen. φ(n)=46 hat die Lösungen n=47 und n=94.

Aufgabe 3

Sei G die 4-elementige Gruppe \left\{1,a,b,c\right\} mit 1 als neutralem Element und den Verknüpfungen ab=ba=c,ac=ca=b, bc=cb=a^2=1, b^2=c^2=a.
Sei GL(2,R) die Gruppe der invertierbaren 2×2-Matrizen.
Finde einen Homomorphismus G\to GL(2,R), der nicht alle g\in G auf die Einheitsmatrix abbildet.

Lösung: 1 muss natürlich auf die Einheitsmatrix E abgebildet werden. Eine Möglichkeit für a,b,c sind die Drehungen um 180, 90 und 270 Grad. Eine andere Möglichkeit sind E,-E und -E oder E, P und P, wobei P die Permutationsmatrix (\begin{array}{cc}0&1\\  1&0\end{array}) bezeichnet.

Auswertung

Es gab 16 Einsendungen, von denen 6 (Frank S., Roland K., Jakob H., Armin K., Stephan W., Christian W.) alle Aufgaben richtig hatten und mir also möglichst bald ihre Adresse mitteilen sollten, damit die Kalender noch vor Jahresbeginn ihre Empfänger erreichen. Ich schicke auch noch mal Erinnerungsmails.

(Ich hatte eigentlich angekündigt, noch unter den Teilnehmern mit mindestens 3 Lösungen Kalender zu verlosen. Da die Zahl der 100%igen aber höher war als erwartet und ich nur 6 Kalender zur Verfügung habe, gewinnen nun leider nur die obengenannten. Sorry.)

Kommentare (8)

  1. #1 Clemens Robbenhaar
    Berlin
    21. Dezember 2014

    Herzlichen Glückwunsch an die Gewinner!

    Wer bei Teil III, Aufgabe 1 nicht gerne den Rechner anwirft, um wirklich alles durchzuprobieren, konnte sich übrigens mit der Beobachtung helfen, dass x^2 + 2*y^2 nur dann ein Vielfaches von 5 ist, wenn sowohl x als auch y Vielfache von 5 sind – jedenfalls wenn ich da nichts übersehen habe 😉

    Nämlich ist für x = 0,1,2,3,4 das x*x = 0,1,4,4,1 (mod 5) und 2*x*x = 0,2,3,3,2. Die Summe von zwei beliebigen Elementen aus beiden Folgen kann dann nur 0 (mod 5) sein, wenn x=0 und y=0 (mod 5).

    Jedenfalls ergeben dann die ersten beiden Terme entweder 0 oder größergleich 25, und müssen zur Konstruktion von 15 beide 0 sein, und dann bleiben nur noch die beiden letzten Terme, bei denen es deutlich weniger durchzuprobieren gibt.

    Ich bin übrigens an der Phi-funktion gescheitert, weil ich nicht an die Primfaktorzerlegung gedacht habe, sondern eine brute-force Methode versucht habe. Dummerweise bräuchte es dazu eine Aussage wie phi(m) >= m/C für ein C, um irgendwann die Suche nach Lösungen abbrechen zu können, weil m zu groß wird, um noch phi(m) = 46 zu erreichen.
    Weiß da jemand was? Die Graphik der Verteilung der ersten 1000 Werte bei Wikipedia legt ja so etwas wie C > 5 nahe, aber ich habe da nichts gefunden … eventuell geht es ja auch für kein C?

  2. #2 AmbiValent
    21. Dezember 2014

    C müsste am größsten sein, wenn möglichst viele verschiedene Primteiler ausgeschlossen sind. Dabei bringt es gar nichts, wenn ein Primteiler mehrfach beteiligt ist: wenn zum Beispiel schon alle geraden Zahlen ausgeschlossen sind, bringt es nichts, auch noch alle durch 4 teilbaren Zahlen auszuschließen… die sind nämlich schon weg.

    Bei m>=2 hat man also bei der Bestimmung von C alle durch 2 teilbaren Zahlen ausgeschlossen, bei m>=6 (2*3) auch noch alle durch 3 teilbaren, dann bei m>=30 (2*3*5) auch noch alle durch 5 teilbaren, bei m>=210 (2*3*5*7) alle durch 7 teilbaren und so weiter. Natürlich gibt es vor 210 massig Zahlen, die durch 7 teilbar sind, zum Beispiel 42 (2*3*7). Dabei würden dann aber erst die Hälfte, dann ein Drittel, dann ein Siebtel des Rests der Zahlen als nicht teilerfremd ausgeschlossen, das wären weniger als bei 30.

    Bei 210 wäre C also der Kehrwert von (1 – 1/2)(1 – 1/3)(1 – 1/5)(1 – 1/7) = 1/2 * 2/3 * 4/5 * 6/7 = 8/35, also C = 35/8 = 4,375

  3. #3 Clemens Robbenhaar
    22. Dezember 2014

    Ah, stimmt, die Zahlen, die Produkte aus den jeweils ersten Primzahlen sind, sind dann sozusagen der “worst case” mit dem relativ kleinsten phi.

    Wenn ich noch zwei Primzahlen weiter rechne, kommt für 2*3*5*7*11=2310 noch ein Wert für phi(n)/n = 8/35*10/11 = 16/77, und 2310*13 = 30030 dann phi(n)/n = 16/77*12/13 = 192/1001; also bei letzterem schon C = 1001/192 > 5 raus … ob sich das mit einem festen C einfangen lässt, ist dann schon mehr Primzahlentheorie als ich auf dem Kasten habe (was aber nicht sagt bei meinen äusserst bescheidenen Kenntnissen).

    Aber immerhin wäre damit herausgekommen, dass bei gegebenem m und gesuchten n mit phi(n) = m bei allen n >= 2*3*5…*p dann phi(n) >= (2-1)*(3-1)*(5-1)*… *(p-1) , und wenn das letztere größer als das m wird, dann kann der Rechner aufhören, nach Lösungen zu suchen … also z.B bei 22 < (2-1)*(3-1)*(5-1)*(7-1)=48 reicht 210, und bei 94 < (2-1)*(3-1)*(5-1)*(7-1)*(11-1)=480 reicht 2*3*5*7*11=2310 als Grenze, hinter der keine Lösungen mehr vorhanden sein können.

  4. #4 Stefan Wagner
    https://demystifikation.wordpress.com/2014/12/14/diy-marzipanboot/
    23. Dezember 2014

    Ein richtiger Würfel sieht so aus, dass die Summe der gegenüberliegenden Zahlen immer 7 ist, also 1:6, 2:5 und 3:4 gegenüberliegend sind.

    Daraus ergibt sich, dass wenn man die 1 als oben definiert, die 6 unten liegen muss. Dann kann die 2 vorne und die 5 hinten liegen oder umgekehrt, aber das eine lässt sich durch drehen in das andere überführen. Also lässt sich ein Würfel immer so legen, dass die 1 oben und die 6 unten, die 2 vorne und die 5 hinten ist. Ob die 3 dann links und die 4 rechts ist oder umgekehrt ist die einzige Freiheit, sprich: Es gibt nur 2 Möglichkeiten für einen Würfel.

    Leider hatte ich nicht die Zeit die Lösung rechtzeitig einzuschicken.

    Die 27 Dreiecke hatte ich auch richtig und die 15 habe ich mit einem kl. Scalaprogramm empirisch ermittelt:
    def f (x: Int, y: Int, z:Int, w: Int) = x*x + 2*y*y + 5*z*z + 5*w*w f: (x: Int, y: Int, z: Int, w: Int)Int scala> val vv = (0 to 10).map (x => (0 to 10).map (y => (0 to 10).map (z => (0 to 10).map (w => f (x, y, z, w))))) vv: scala.collection.immutable.IndexedSeq[scala.collection.immutable.IndexedSeq[scala.collection.immutable.IndexedSeq[scala.collection.immutable.IndexedSeq[Int]]]] = Vector(Vector(Vector(Vector(0, 5, 20, 45, 80, 125, 180, 245, 320, 405, 500), Vector(5, 10, 25, 50, 85, 130, 185, 250, 325, 410, 505), Vector(20, 25, 40, 65, 100, 145, 200, 265, 340, 425, 520), Vector(45, 50, 65, 90, 125, 170, 225, 290, 365, 450, 545), Vector(80, 85, 100, 125, 160, 205, 260, 325, 400, 485, 580), Vector(125, 130, 145, 170, 205, 250, 305, 370, 445, 530, 625), Vector(180, 185, 200, 225, 260, 305, 360, 425, 500, 585, 680), Vector(245, 250, 265, 290, 325, 370, 425, 490, 565, 650, 745), Vector(320, 325, 340, 365, 400, 445, 500, 565, 640, 725, 820), Vector(405, 410, 425, 450, 485, 530, 585, 650, 725, 810, 905), Vec... scala> vv.flatten.flatten.flatten.toSet.toList.sorted res11: List[Int] = List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 17...

  5. #5 Christian
    2. Januar 2015

    Nachdem seit fast einer Woche keine Post mehr in meinen Ort gefahren ist, kam sie heute endlich wieder vorbei – und darin war der Kalender. Vielen Dank dafür! Der ist echt toll, auch wenn ich meiner Familie kaum eine Anspielung im Kalender verständlich machen kann.^^

  6. #6 Siegfried
    Hannover
    6. Januar 2015

    Teil I, Aufgabe 2:
    Die Lösungsformel müsste richtig lauten:
    cos(y/2) = (1/2) * Wurzel( 2 + 2 * cos(y) ). Und der Startwert cos( pi / 2 ) = 0 zur Berechnung von cos( pi / 4 ).
    Ein erfolgreiches neues Jahr 2015.

  7. #7 Thilo
    6. Januar 2015

    Die 2 ist ergänzt. Die Wahl des Startwerts spielt aber keine Rolle, cos(pi/4) kann man z.B. mit dem Satz des Pythagoras berechnen.

  8. […] Jahresendrätsel gestellt hatte. (Ebenso wie den Eintrag bei der 2 übrigens, die Auflösungen sind hier.) Jeder rot und blau kantengefärbte vollständige Graph auf 14 Knoten hat mindestens einen […]