Beiträge von Pi mal Daumen

    Man kann den Endpunkt T auch vom Start in D aus erreichen: D nach I und zurück (2er Weg "verbraten"), dann nach C von C nach I (4er- Weg "verbraten") und dann den Eulerweg von C nach T.

    Stimmt! Geht dann logischerweise auch von B aus (2er nach G), dann regulär nach C und von dort 4er nach G - anschließend normaler Eulerweg von C nach T.

    Wenn etwas vorwissen über die Lösungsvorschriften für Sudoku da ist, ist diese Aufgabe schnell gelöst gewesen, deswegen mein Vorschlag für zuzkünftige Aufgaben solcher Art: es wird eine solche Aufgabe gestellt, die allerdings nicht vollständig eindeutig lösbar ist.

    Was wäre an einer nicht eindeutigen Lösung besser? Damit mögen vielleicht ein paar spezielle Lösungsstrategien nicht funktionieren, aber wirklich komplizierter wird es damit auch nicht. Denn das Standardverfahren, welches iterativ ein Sudoku durch Ausschließen aller unmöglichen Fälle so weit reduziert, dass meist schon sofort die Lösung rausfällt oder aber zumindest nur wenige Abhängigkeitsketten existieren, die man prüfen muss, steht natürlich immer zur Verfügung. Und das käme wunderbar auch mit mehrdeutigen Lösungen zurecht.


    Zumal im Extremfall übrigens selbst für solch spezielle Sudoku-Varianten wie hier passende Solver im Netz zu finden sind (zunächst mit der Maus die einzelnen Felder der farbigen Gebiete an die passenden Stellen ziehen, dann die Zahlen eintragen und lösen lassen - kommt übrigens sogar mit nicht eindeutigen Varianten zurecht, indem dann die verschiedenen möglichen Belegungen nacheinander ausgegeben werden).

    Der Hinweis das die gefärbten Gebiete gleich groß sind, ist völlig unerheblich und wäre nur nötig gewesen, wenn die Farbe von Gebiet 7 nicht mit der seiner Nachbarn 6 und 8 kollidiert wäre, also der Graph prinzipiell mit 3 Farben färbbar gewesen wäre.


    Das ist definitiv falsch. Beispielsweise könnte man in Blackhearts verlinkter Grafik auch Gebiet 6 schwarz färben und hätte eine legitime Färbung (es gäbe auch noch andere Möglichkeiten, in dem von GraphZahl genannten kritischen Teilgraphen die Färbung so zu wählen, dass ein anderes Gebiet als 7 schwarz ist und der restliche Graph dreifärbbar ist). Ohne dass mit der Nebenbedinung der gleichen Größe der restlichen drei Färbungen sichergestellt wird, dass zwingend ein Gebiet mit 5 Feldern schwarz gefärbt sein muss, wäre die Sache also nicht eindeutig.

    Einfach eine der Flaschen separieren und auf den verbleibenden 5 alle 3er-Paarungen in die Maschine stellen (das sind 10 Stück). Wenn sich einmal grün ergibt, dann eine der drei Flaschen nehmen. Wenn sich nie grün ergibt, dann ist die separierte Flasche unbedenklich.

    Du hast vermutlich vergessen, dass wenn man in A startet, man über die zwei geradzahlig oft begangenen Wege nach T gehen kann und schließlich in dieser Variante in C endet.


    Somit sind von A aus die Endpunkte C oder T (je nachdem, ob man die beiden geradzahligen Weg zwischen A und C bzw. A und T legt), von B bzw. D aus die Endpunkte J, S oder U (einen geradzahligen Weg von B bzw. D nach C und einen geradzahligen Weg von T nach J, S oder U) und von C aus die Endpunkte A, E, F, O, J, S erreichbar (von T aus zwei geradzahlige Wege nach A, E, F, O, J oder S).


    Damit ergeben sich insgesamt 9 mögliche Endpunkte: A, C, E, F, J, O, S, T und U.

    Eine Lösung, die für 15 Tage funktioniert:


    Tag 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
    Temperatur ° C
    5 5 -12 5 5 -12 5 5 5 -12 5 5 -12 5 5


    Die Durchschnittstemperatur von 7 aufeinanderfolgenden Tagen beträgt dabei jeweils +1/7° C, von 10 aufeinanderfolgenden Tagen jeweils -1/10° C.


    Beweis, dass es keine Lösung mehr für 16 Tage geben kann:


    Die Durchschnittstemperatur der Tage 8-14 müsste positiv sein (7-Tage-Regel), die Durchschnittstemperatur der Tage 5-14 dagegen negativ (10-Tage-Regel). Da in diesem Abschnitt aber die Tage 8-14 eine positive Durchschnittstemperatur haben, geht das überhaupt nur, wenn die verbleibenden Tage 5-7 eine negative Durchschnittstemperatur hätten.


    Also:

    Tage 8-14 positiv (7 Tage)

    Tage 5-7 negativ (10 Tage 5-14 mit 8-14 positiv)


    Mit der gleichen Logik geht es weiter:

    Tage 2-8 positiv (7 Tage)

    Tage 9-11 negativ (10 Tage 2-11 mit 2-8 positiv)

    Tag 8 positiv (Tage 5-11 positiv, da 7 Tage, aber Tage 5-7 negativ und 9-11 negativ)

    Tage 9-15 positiv (7 Tage)

    Tage 6-8 negativ (10 Tage 6-15 mit 9-15 positiv)

    Tage 3-9 positiv (7 Tage)

    Tage 10-12 negativ (10 Tage 3-12 mit 3-9 positiv)

    Tag 9 positiv (Tage 6-12 positiv, da 7 Tage, aber Tage 6-8 negativ und 10-12 negativ)

    Tage 10-16 positiv (7 Tage)

    Tage 7-9 negativ (10 Tage 7-16 mit 10-16 positiv)

    Tag 7 negativ (Tage 7-9 negativ, aber Tag 8 positiv und Tag 9 positiv)

    Tage 4-10 positiv (7 Tage)

    Tage 1-3 negativ (10 Tage 1-10 mit 4-10 positiv)

    Tage 7-13 positiv (7 Tage)

    Tage 4-6 negativ (10 Tage 4-13 mit 7-13 positiv)


    Widerspruch: Tage 1-7 müssten im Durchschnitt positiv sein (7 Tage), aber Tage 1-3 im Durchschnitt neagtiv, Tage 4-6 im Durchschnitt negativ und Tag 7 negativ.


    Es gibt also keine Lösung für 16 Tage oder mehr.

    Fast schon eine "Scherzaufgabe", die trival wird, wenn man sie rückwärts angeht: Egal, welchen Schnitt der Wichtel am Ende per "Laser-Sch.Wer.T." durch den Quader macht - wenn dieser nicht parallel zur xy-, xz- bzw. yz-Ebene liegt (was durch Verbot der Achsenparallelität ausgeschlossen war), kann man den Quader parallel zu jeder dieser Ebenen stets so teilen, dass der "Laser-Sch.Wer.T.-Schnitt" durch beide Teilquader geht (und seien diese auch noch so minimal davon betroffen). Damit ist das Problem rekursiv sofort zu lösen, denn natürlich kann man dann auch diese beiden Teilquader selbst wiederum passend teilen, dass die daraus entstehende Teile ebenfalls allesamt vom Schnitt betroffen sind usw.


    Im Ergebnis können also alle 512 Geschenke zerstört sein.

    Wenn man sich die Aufgabe mit einer Skizze verdeutlicht, wird sie recht einfach:


    Skizze


    Die Radien der unteren beiden Halbkugelkuchen sind trivial zu ermitteln, wenn man die Hälfte eines Kugelvolumens ansetzt. Damit gilt:


    V = 1/2 * 4/3 * π * r3
    r = (3/2 * V / π)1/3


    r1 = (3/2 * V1 / π)1/3
    r2 = (3/2 * V2 / π)1/3


    Der Durchmesser des oberen Kuchen ergibt sich aus dem Dreieck M1M2A per Pythagoras :


    d0 = sqrt((r1+r2)² - (r1-r2)²) = sqrt(r1² + 2r1r2 + r2² - r1² + 2r1r2 - r2²) = 2 * sqrt(r1*r2)


    Nun kann man einsetzen:


    d0 = 2 * sqrt((3/2 * V1 / π)1/3 * (3/2 * V2 / π)1/3) = 2 * (9/4 * V1 * V2 / π²)1/6

    Für das Halbkugelvolumen in Abhängigkeit des Durchmesser gilt wiederum:


    V = 1/2 * 1/6 * π * d3


    Also: V0 = 1/2 * 1/6 * π * d03 = 1/12 * π * (2 * (9/4 * V1 * V2 / π²)1/6)3 = 8/12 * π * sqrt(9/4 * V1 * V2 / π²) = 8/12 * 3/2 * π / π * sqrt(V1 * V2) = sqrt(V1 * V2) = sqrt(10 * 15) = 5 * sqrt(6)


    V0 = 12,25 l

    Hier hatte man schnell Gebiet 18 als verdächtig ausgemacht, da der "Nachbarring" (die Nachbarn bilden einen Ring um Gebiet 18) ungeradzahlige Anzahl hat (=5) und damit nicht abwechselnd koloriert werden kann.


    Das haut als Logik nicht hin, denn dann wäre beispielsweise auch Gebiet 30 in gleicher Weise verdächtig (7 derartige "Nachbarn"). Man muss hier beachten, dass durch die Berührung nur in der Diagonale prinzipiell die Gebiete 18 und 6 gleich gefärbt sein dürfen. Somit wäre eine Färbung mit nur 3 Farben dort durchaus denkbar: 7+22, 17+19, 6+18


    Der Widerspruch kann sich also erst in größerem Kontext ergeben.

    Lösungsidee: Mantelfläche in die Ebene abrollen und dort den kürzesten Weg berechnen.


    Skizze


    Die Mantelfläche ist ein Kreissektor mit der Mantellinie des Zuckerhuts s = 60 km als Radius. Der Mittelpunktswinkel dieses Kreissektors wird durch das Verhältnis des Umfangs der Grundfläche des Zuckerhuts zum Umfang des Kreises mit dem Radius der Mantellinie definiert:

    α = 2 * π * 20 km / (2 * π * 60 km) * 360° = 1/3 * 360° = 120°

    Nun kann man das Bonbontal und die Weingummihöhe an den beiden begrenzden Kreisradien eintragen. Eine Umrundung des Zuckerhuts ist dann einfach die Länge der Strecke zwischen Bonbontal und Weingummihöhe quer durch den Kreissektor.

    Seien die Korrdinaten der Punkte:


    G = (0; 60)

    B = (-60 * sin(60°); 60 - 60 * cos(60°)) = (-30 * sqrt(3); 30)

    W = (50 * sin(60°), 60 - 50 * cos(60°)) = (25 * sqrt(3); 35)

    Damit ergibt sich ein Weg "x" als Entfernung BW: x = sqrt((25 * sqrt(3) + 30 * sqrt(3))² + (35 - 30)²) = sqrt((55 * sqrt(3))² + 5²) = sqrt(9100)
    x = 95,39 km

    Der höchste Punkt der Strecke ist dort erreicht, wo die Entfernung zum Gipfel am kleinsten ist. Das ist am Lotfußpunkt H des Lots von G auf die Strecke BW der Fall. Bis dorthin nimmt von B aus die Entfernung zum Gipfel stetig ab (ansteigend), ab dort nimmt bis W die Entfernung vom Gipfel wiederum stetig zu (abfallend).

    Geradengleichung BW aufstellen:

    y = mx + c

    m = (35 - 30) / (25 * sqrt(3) + 30 * sqrt(3)) = 5 / (55 * sqrt(3)) = 1 / (11 * sqrt(3))
    Einsetzen von W: c = y - mx = 35 - 1 / (11 * sqrt(3)) * 25 * sqrt(3) = 35 - 25/11 = 360/11


    y = 1 / (11 * sqrt(3)) * x + 360/11

    Geradengleichung GH aufstellen, die senkrecht auf BW steht:

    y = -1/m * x + d = -11 * sqrt(3) * x + d
    Einsetzen von G: d = y + 11 * sqrt(3) * x = 60


    y = -11 * sqrt(3) * x + 60

    Gleichsetzen der beiden Geraden, um H zu ermitteln:


    1/(11 * sqrt(3)) * x + 360/11 = -11 * sqrt(3) * x + 60

    (11 * sqrt(3) + 1 / (11 * sqrt(3))) * x = 60 - 360/11

    (121 * 3 + 1) / (11 * sqrt(3)) * x = 300/11
    364 * x = 300 * sqrt(3)
    x = 75/91 * sqrt(3)
    Einsetzen von x in BW: y = 1 / (11 * sqrt(3)) * 75/91 * sqrt(3) + 360/11
    y = 75/1001 + 360/11 = (75 + 32760) / 1001 = 32835/1001 = 2985/91

    H = (75/91 * sqrt(3), 2985/91)

    Entfernung HW als Wert "y" berechnen:


    y = sqrt((25 * sqrt(3) - 75/91 * sqrt(3))² + (35 - 2985/91)²) = sqrt(3 * (25 - 75/91)² + 200²/91²) = sqrt(3 * 2200²/91² + 200²/91²) = sqrt(3 * 11² * 200²/91² + 200²/91²) = 200/91 * sqrt(3 * 121 + 1) = 200/91 * sqrt(4 * 91) = 400/91 * sqrt(91)
    y = 41,93 km

    Hier meine Lösung dieser wirklich tollen Aufgabe:


    Es genügen 16 Atome mit jedes Atomgewichts g. Die Verteilung auf die Schritte ist wie folgt:


    Schritt k
    4g - 3
    4g - 2
    4g - 1
    4g 4g + 1 4g + 2
    4g + 3
    Benötigte Atome mit Gewicht g
    1 2 3 4 3 2 1



    Man kann sich leicht verdeutlichen, dass das Schema funktioniert: Beispielsweise setzt sich der Schritt 11 zusammen aus 1 Atom des Atomgewichts 2 (k = 11 = 4 * 2 + 3) und 3 Atomen des Atomgewichts 3 (k = 11 = 4 * 3 - 1). Somit also Gesamtatomgewicht der Runde 11: 1 * 2 + 3 * 3 = 11.



    Beweis, dass es kein Schema gibt, welches mit weniger als 16 Atomen jedes Atomgewichts auskommt:


    Annahme: Für die Atomgewichte 0, 1, 2, ..., 18, 19 stehen jeweils maximal 15 Atome zur Verfügung. Das sind insgesamt 300 Atome. Damit ergibt sich in der Summe ein Minimalgewicht für 300 Atome von 19 * 20 / 2 * 15 = 190 * 15 = 2850.


    Man betrachte nun die ersten 76 Schritte. Die Summe der Atomgewichte all dieser Schritte beträgt 76 * 77 / 2 = 2926. Dafür müssen insgesamt 76 * 4 = 304 Atome entnommen werden. Das Minimalgewicht für 300 Atome beträgt aber 2850. Die restlichen 4 Atome dürfen also zusammen nicht mehr als 76 wiegen.
    Allerdings sind die Atomgewichte 0 ... 19 bereits ausgeschöpft. Das minimal noch zur Verfügung stehende Atomgewicht wäre somit 20. 4 * 20 ist aber bereits 80. Wenn also maximal 15 Atome von jeder Sorte zur Verfügung stünden, würde die Entnahme für Schritt 76 nicht mehr funktionieren.


    16 Atome jeder Sorte ist damit die Minimallösung.

    Die Umsteigezeiten sollen also minimiert werden, und das könnte man mit Sitzenbleiben ja vielleicht erreichen.

    Das "Sitzenbleiben" an der Endhaltestelle ist eine Erfindung zusätzlicher Gegebenheiten, die nicht durch die Aufgabenstellung gedeckt ist. Wer sagt denn, dass das Fahrzeug auf der Linie wieder zurückfährt? Die Aufgabe gibt nur her, dass man an der Endhaltestelle ankommen und wieder abfahren kann. Allerdings geht das wiederum nicht, wenn es sich in beiden Fällen um die gleiche Linie handelt, weil ein Umstieg zwei verschiedene Linien erforderte.

    Du kannst in Winterwald nicht von Linie 5 in Linie 5 der Gegenrichtung umsteigen, weil die Bedingung aus der Aufgabenstellung hieß: "Umstiege finden immer zwischen verschiedenen Linien statt."

    Die letzte Aufgabe ist wirklich nochmals ein schöner Brocken! Glücklicherweise ist sie dann aber auch nicht ganz so schlimm, wie sie zunächst ausschaut, wenn man sich ein paar Prinzipien überlegt hat. Ich kann also doch die Weihnachtstage mit ein paar anderen Dingen zubringen. ^^


    Vielen Dank, dass es auch dieses Jahr wieder einen solch tollen Mathekalender in der Vorweihnachtszeit gab! Er hat wieder viel Freude bereitet und hatte einige gute Herausforderungen dabei. Ich wünsche allen nun ein frohes Weihnachtsfest und einen guten Rutsch ins neue Jahr!


    Bis zur Lösungsdiskussion... :thumbsup:

    Wie ist denn folgende Aussage von Rolando zu verstehen: "Ich will auf keinen Fall länger als 12h von unserem Startpunkt in Grönland zu unserem Endpunkt ebenda unterwegs sein."?


    Es kann ja im Dienstplan eine Route geben, die mehrfach an Grönland vorbeiführt. Würde es für diesen Wunsch reichen, wenn dann kein Teilabschnitt dieser Route länger als 12 Stunden von Grönland wegführt? Oder darf die komplette Route dann nicht länger als 12 Stunden sein (wobei das etwas witzlos ist, wenn die Rentiere ohnehin endlos unterwegs sind) mit Start und Ende in Grönland, unabhängig davon, wie oft sie zwischendurch wieder nach Grönland führt?