Aufgabendiskussion 19. Türchen

    Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

    • Nachtvogel schrieb:

      Stimmt meine Interpretetion: Ich soll die Karte mit 10 verschiedenen Helligkeiten so ausmalen, dass die maximale Differenz der Helligkeit von benachbarten Gebieten minimal wird?
      Nein, das stimmt so nicht.

      Die Karte besteht aus dem "Merry Christmas" Rechteck (fuer die Aufgabe irrelevant), und aus 10 Gebieten G_1,...,G_10.
      Diesen 10 Gebieten sollst Du Helligkeiten zuweisen, sodass Gebiet G_i einen Blauton mit Helligkeit H_i bekommt.

      Die Aufgabe stellt zwei Bedingungen an diese Helligkeiten:
      1. Verschiedene Gebiete G_i und G_j sollen immer verschiedene Helligkeiten H_i ungleich H_j erhalten.
      2. Wenn G_i und G_j benachbart sind und wenn G_x und G_y benachbart sind und wenn (i,j) ungleich (x,y) gilt,
      dann muessen die beiden Helligkeitsdifferenzen "H_i minus H_j" und "H_x minus H_y" verschieden sein.

      Unter allen diesen Helligkeitszuweisungen sollst Du nun eine finden, die den groessten verwendeten
      Helligkeitswert max(H_1,H_2,...,H_10) minimiert.
    • msp schrieb:

      Die Differenzbildung ist nicht kommuntativ ist. Ist der Betrag der Differenz gemeint?

      Falls nicht, wie wird die Differenz dann zwischen den Werten zweier Felder gebildet?

      Da kannst Du gar keinen Fehler machen:
      Beide Interpretationen funktionieren, und beide Interpretationen fuehren zur selben Antwort.

      1. Falls Du den Betrag der Differenz nimmst, betrachtest Du Differenzen fuer zwei-elementige Mengen {G_i,G_j} von Gebieten.
      2. Falls Du die Differenz direkt nimmst, betrachtest Du Differenzen fuer geordnete Paare (G_i,G_j) von Gebieten.
    • ThL schrieb:

      Igor Dudas schrieb:

      Nein, die Gebiete sollen unterschiedliche Helligkeiten haben, d.h. jede Helligkeitsstufe wird genau einmal verteilt
      Bist Du Dir da sicher? Entweder habe ich gerade einen großen Denkfehler, oder man bekommt ein Ergebnis, das nicht in der Ergebnisliste ist, wenn mal alle 10 Helligkeitswerte genau einmal verwendet. Außerdem wäre die Aufgabe dann nicht sehr anspruchsvoll - wenn ich alle 10 Helligkeitswerte verwenden muss, dann ist die Summe daraus schnell berechnet. Wenn ich aber einzelne Helligkeiten mehrfach verwenden darf (solange ich die Regeln bzgl. angrenzender Felder beachte), dann muss ich mir Gedanken machen, wie ich die verteile - und dann ist es eine interessante Aufgaben.
      Im Aufgabentext steht:
      "Die 10 Gebiete sollen mit Blautönen mit 10 verschiedenen Helligkeiten ausgemaltwerden."

      Das heisst:
      Verschiedene Gebiete muessen immer verschiedene Helligkeitswerte erhalten.

      Das heisst aber nicht:
      Jeder Wert zwischen kleinstem und groesstem verwendeten Helligkeitswert muss genau einmal verwendet werden.

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von WoegingerG ()

    • 1)I=16 ist die niedrigste Zahl, die man braucht, um alle Gebiete einzufärben, dass man die Bedingungen erfüllt.
      blau: Nr. des Gebiets
      rot:Differenz benachbarter Gebiete

      z.B.



      Es ist klar, dass im allerbesten Fall I mindestens 15 ist, da es 14 Grenzen für benachbarte Gebiete gibt, die alle verschieden sein sollen.

      2)Ist 16 wirklich die KLEINSTE Zahl?
      a) Kleiner als 15 ist für die Gebiete nicht möglich (siehe oben).
      b) I=15
      => Die "Grenzzahlen" laufen von 1 bis 14.

      Man beginnt bei Gebiet 1 und zieht einen "Rundkurs", sodass man jede bezifferte Grenze genau einmal überquert und diese Grenzwerte addiert. Dies ist möglich, da alle Gebiete entweder zwei oder vier benachbarte Gebiete haben. (In jedes Gebiet, in das man hinein kann, kommt man wieder auf einer noch nicht überschrittenen Grenze heraus.)


      Die Parität zweier benachbarter Gebiete bleibt genau dann gleich, wenn die Ziffer für die gemeinsame Grenze gerade ist.

      Ist sie ungerade, ändert sich die Parität.

      Nun habe ich die Grenzzahlen von 1, 2, ......14. Das sind 7 gerade Zahlen und 7 ungerade Zahlen.
      Das heißt, 7mal wurde die Parität geändert.
      Das darf aber bei einem Rundkurs nicht sein. Wenn ich bei 1 beginne, muss ich auch wieder bei 1 enden.
      Deshalb ist I=15 nicht möglich.
      ----------------------------

      Bin ich in diesem Thread mit der Lösung überhaupt richtig?
    • chryso schrieb:

      1)I=16 ist die niedrigste Zahl, die man braucht, um alle Gebiete einzufärben, dass man die Bedingungen erfüllt.
      blau: Nr. des Gebiets
      rot:Differenz benachbarter Gebiete

      z.B.



      Es ist klar, dass im allerbesten Fall I mindestens 15 ist, da es 14 Grenzen für benachbarte Gebiete gibt, die alle verschieden sein sollen.

      2)Ist 16 wirklich die KLEINSTE Zahl?
      a) Kleiner als 15 ist für die Gebiete nicht möglich (siehe oben).
      b) I=15
      => Die "Grenzzahlen" laufen von 1 bis 14.

      Man beginnt bei Gebiet 1 und zieht einen "Rundkurs", sodass man jede bezifferte Grenze genau einmal überquert und diese Grenzwerte addiert (oder subtrahiert), um den blauen Wert des angestrebten Gebiets zu erhalten.
      Dies ist möglich, da alle Gebiete entweder zwei oder vier benachbarte Gebiete haben. (In jedes Gebiet, in das man hinein kann, kommt man wieder auf einer noch nicht überschrittenen Grenze heraus.)

      Der Rundkurs für das oben gezeichneten Diagramms wäre hier in 1) beispielsweise:
      1 = 1 +8 - 5 + 6 + 3 - 4 + 2 - 1 -7 +12 - 14 + 15 - 13 + 9 - 11




      Die Parität zweier benachbarter Gebiete bleibt genau dann gleich, wenn die Ziffer für die gemeinsame Grenze gerade ist.

      Ist sie ungerade, ändert sich die Parität.

      Nun habe ich die Grenzzahlen von 1, 2, ......14. Das sind 7 gerade Zahlen und 7 ungerade Zahlen.
      Das heißt, 7mal wurde die Parität geändert.
      Das darf aber bei einem Rundkurs nicht sein. Wenn ich bei 1 beginne, muss ich auch wieder bei 1 enden.
      Deshalb ist I=15 nicht möglich.
      ----------------------------

      Bin ich in diesem Thread mit der Lösung überhaupt richtig?