Johannes Waldmann am 10.3.2009 im VL Schneeberg


Klasse 11/12 (eine Stunde):


Aufgabe "Wires under the Hudson" aus Peter Winkler: Mathematical Mind-Benders; http://www.akpeters.com/product.asp?ProdCode=3363

Fünfzig gleichaussehende Kabel verlaufen durch ein Rohr unter dem Hudson. (Wahrscheinlich geht auch die Elbe.) Ein Elektriker soll herausfinden, welche Kabelenden auf der einen Seite zu welchen Enden auf der anderen Seite gehören (d. h. die Bijektion finden). Er kann auf der einen Seite Kabelpaare verbinden und dann auf der anderen Seite feststellen (mit Batterie und Lampe), welches die verbundenen Enden sind. Wie oft muß er dazu den Fluß überqueren?

Lösung: dreimal reicht.

Verbinde a1 - a2, a3 - a4, .. a47 - a48; dann rüber und alles ausmessen (und aufschreiben), dann zurück,

dann a2 - a3, a4 - a5, .. a48 - a49, dann rüber, messen, nachdenken und fertig.

(wenn man die Lösung hat, ist es leicht)

Aufgabe 58 (Seite 32) aus Bollobas: Modern Graph Theory, Springer 1998:

Jeder von n >= 4 älteren Professoren kennt ein Gerücht, von dem keiner der anderen etwas weiß. Sie telefonieren miteinander. Bei jedem Gespräch erzählen sich beide Teilnehmer alles, was sie bis dahin wissen. Beweise, daß frühestens nach 2*n-4 Gesprächen jeder alles weiß.

(daß es mit 2*n - 4 geht, ist leicht; daß es nicht besser geht, ist umständlich.)

Lösung siehe: C A J Hurkens: Spreading gossip efficiently, Nieuw Archief voor Wiskunde, Juni 2000, http://www.math.leidenuniv.nl/~naw/serie5/deel01/jun2000/pdf/hurkens.pdf

Klasse 9/10 (zwei Stunden):


  • Wdhlg: elementare Begriffe zu Graphen; P_n, C_n, K_n; Graph-Operationen (Komplement, disjunkte Summe); Beweisprinzipien Schubfachschluß, "kleinstes Gegenbeispiel"
  • chi(G) <= Delta(G) + 1
  • Satz von Brooks: G zshg. und G keine Clique und G kein ungerader Kreis => chi(G) <= Delta(G).
  • Wenn |V| = 2n und |E| > n2, dann enthält (V,E) ein Dreieck
  • Defn. Ramseyzahlen R(a,b);
  • Existenzbeweis durch Abschätzung R(a+1,b+1) <= R(a+1,b) + R(a,b+1)
  • R(3,4) = 9 (d.h. eins besser als die Abschätzung)

Das ist für 9/10 nicht viel, und es ging auch wirklich recht langsam (viele Schüler => Niveau und Mitarbeit unterschiedlich)