Lösungsdiskussion

[Fanbusfahrer]

PHP-Code:

Wir stellen eine Formel auf: s(m,n)=(m-1)(n-1)+2
Im schlimmsten Fall können die ersten m-1 Farben mit den ersten n-1 Farben kombiniert werden und dann noch Farbe m mit der Zahl n. Dann kann die letzte Karte nirgends angelegt werden. Also bedarf es der entsprechenden obigen Anzahl. Damit ist Antwort 6 korrekt. 


[Mathewichtel]

PHP-Code:

Wir stellen eine Formel auf: s(m,n)=(m-1)(n-1)+2
Im schlimmsten Fall können die ersten m-1 Farben mit den ersten n-1 Farben kombiniert werden und dann noch Farbe m mit der Zahl n. Dann kann die letzte Karte nirgends angelegt werden. Also bedarf es der entsprechenden obigen Anzahl. Damit ist Antwort 6 korrekt. 


Mit der Formel bin ich einverstanden, es ist aber nicht Antwort 6:
s(3,6)=12 >10
Richtig ist Antwort 10, wie sich durch Termumformungen zeigen lässt.

[Linsen_mit_Spatzle]

PHP-Code:

Wir stellen eine Formel auf: s(m,n)=(m-1)(n-1)+2
Im schlimmsten Fall können die ersten m-1 Farben mit den ersten n-1 Farben kombiniert werden und dann noch Farbe m mit der Zahl n. Dann kann die letzte Karte nirgends angelegt werden. Also bedarf es der entsprechenden obigen Anzahl. Damit ist Antwort 6 korrekt. 


Mit der Formel bin ich einverstanden, es ist aber nicht Antwort 6:
s(3,6)=12 >10
Richtig ist Antwort 10, wie sich durch Termumformungen zeigen lässt.

Ich habe die Formel auch verwendet, aber gibt es dafür auch einen Beweis? Warum ist dies der schlimmste Fall? Anschaulich vielleicht klar, aber ein Beweis ist das nicht.

[pierrot]

Der grafische Beweis sollte schon wasserdicht sein. 
Stellt man alle Karten in einem n x m Rechteck dar, wird klar, dass Anschlusskarten immer in der selben Zeile oder Spalte liegen müssen.

Schlechtester Fall, bei dem es gerade nicht geht, ist, dass eine Karte in ihrer Zeile + Spalte „solo“ sitzt. Dies erreicht man durch „diagonale Platzierung“ zu den restlichen n-1 x m-1 Karten. Dann wird anschaulich aber klar, dass bei einer Karte mehr die Bedingung: eine Karte sitzt solo in Zeile + Spalte gebrochen werden muss.

O.B.d.A (ohne Beschränktung der Allgemeinheit) habe ich die Solokarte links oben in Zeile und Spalte 1 gesetzt, dann wird es übersichtlicher (Durch reines Umtaufen der Zeilen und Spalten ist dies natürlich immer möglich). Maximales Auffüllen, dass die erste Karte solo bleibt bedeutet gerade, das n-1 x m-1 Rechteck rechts darunter aufzufüllen.
Somit hat man die Formel für die maximal Anzahl an Karten, bei denen einen nacheinander Auslegen der Karten NICHT möglich ist: (n-1)*(m-1)+1.

Plus 1 ergibt dann die gesuchte Formel.

Siehe Grafik:
https://www.dropbox.com/scl/fi/mgi3qnmy1...csyks&dl=0

Auch ne richtig nette Aufgabe! Gegen Ende des Kalenders gab es echt n ganzen Haufen sehr sehr schöner Aufgaben in Folge. Toll! Das macht Lust auf den Kalender 2025.

Dieser Beitrag wurde zuletzt bearbeitet: 12-31-2024, 09:59 AM von pierrot.

[tfry]

Ich hatte auch ziemlich schnell diesen Ansatz, mich dann aber noch eine ganze Weile mit der Idee herumgeschlagen, dass es ja auch unlösbare Konstellationen wie die Folgende geben könnte:

Code:

---X
--X-
-X--
XXXX

Hier ist ja von jeder Karte aus mindestens eine weitere zu erreichen, aber es gibt eben keinen Weg zu allen Karten. Nun liegt der Verdacht nahe, dass alle solchen Fälle weniger als (n-1)*(m-1)+2 Karten aufweisen, aber wirklich bewiesen habe ich das nicht.

Dieser Beitrag wurde zuletzt bearbeitet: 12-31-2024, 09:59 AM von tfry.

[umu]

Code:

---X
--X-
-X--
XXXX

Hier ist ja von jeder Karte aus mindestens eine weitere zu erreichen, aber es gibt eben keinen Weg zu allen Karten. Nun liegt der Verdacht nahe, dass alle solchen Fälle weniger als (n-1)*(m-1)+2 Karten aufweisen, aber wirklich bewiesen habe ich das nicht.

Richtig, die drei Farben der Einzelkarten müssten hier aber auch verbunden sein, sonst gäbe es zu viele Löcher. Durch diese Verbindungen ist dann doch wieder ein Weg möglich. Dieses Beispiel ist gerade die "Sternkonstellation". Mehr dazu gleich ...

Dieser Beitrag wurde zuletzt bearbeitet: 01-01-2025, 09:02 AM von umu.

[umu]

Im "Buch" erklärt sich das vermutlich ein wenig eleganter...  aber versuchen wir es trotzdem mal mit der Rückrichtung, der Hinlänglichkeit. Sie wirkt stellenweise ein wenig tricky, Irrtümer vorbehalten.

---
n Farben, m Symbole, oBdA m ≥ n.

Einfacher als das Vergleichen der Anzahl der ausgewählten Karten (als Produkt) scheint das Betrachten der Löcher (als Summe).

  mindestens (n-1)(m-1) + 2  Karten  ↔  maximal ( n + m - 3 ) Löcher

Ziel ist nun das Ablegen der Karten geordnet nach Farben in einer gewissen geeigneten Farbabfolge X1-X2-...-Xn, also erst alle Symbole der Farbe X1  mit abschließendem Verbindungssymbol zu X2, dann alle Symbole von X2 mit abschließendem Übergang zur nächsten Farbe, usw.

Zwei Farben heißen
  - "nicht verbunden", wenn sie kein gemeinsames Symbol haben
  - "verbunden" bei (mind.) einem gemeinsamen Symbol
  - "doppelt verbunden" bei (mind.) zwei gemeinsamen Symbolen
  - "einfach verbunden" bei genau einem gemeinsamen Symbol

Folgerungen:

→ Keine Farbe ist "isoliert", d.h. mit keiner anderen Farbe verbunden. (1

→ Keine Auswahl M von Farben ist "isoliert", d.h. es gibt immer eine Farbe in M, die mit einer Farbe außerhalb von M verbunden ist, (1

→ Drei Farben A,B,C paarweise nicht verbunden ist nicht möglich. (2

→ Es gibt keine vier (paarweise verschiedenen) Farben A,B,C,D, dass A,B "einfach verbunden" und C,D "einfach verbunden" sind. (3

Zwei Paare einfach verbundener Farben kann es also nur geben, wenn sie beide eine Farbe Z gemeinsam haben.

→ Sind A-Z und Z-B jeweils einfach verbunden, mit verschiedenen Symbolen, so ist A-B verbunden. (4a

→ Sind A-Z und Z-B jeweils einfach verbunden, mit dem gleichen Symbol, so ist A-B doppelt verbunden. (4b

Und damit final die "Sternkonstellation".

→ Gibt es mehr als zwei Einfachverbindungen zu einer Farbe Z, so sind die entsprechend verbundenen Farben paarweise doppelt verbunden. (5

---
Konstruieren nun schrittweise eine Farbabfolge X1-X2-...-Xn von verbundenen Farben.

Wir beginnen mit zwei verbundenen Farben X1-X2.

Zu jeder Folge X1-X2-...-Xi gibt es mind. eine verbleibende Farbe R, die mit einer der bisher verwendeten Farben verbunden ist, sonst wäre die Menge der Farben der bisherigen Folge ja isoliert.

Wenn möglich, wählen wir eine Farbe, die mit X1 oder Xi verbunden ist. In diesem Falle können wir sie einfach der Farbfolge voranstellen (mit entsprechender Änderung der Indizes) oder als X(i+1) = R anhängen.

Ist dies nicht möglich, gibt es nur Farben im Inneren der Folge, die mit R verbunden sind. Wählen eine solche Farbe Xj. Wären Anfang X1 und Ende Xi ihrerseits nicht verbunden, hätten wir drei paarweise nicht verbundene Farben {R,X1,Xi}, was ja nicht geht. Somit sind in diesem Falle auch Anfang und Ende der Folge verbunden, d.h. man kann die Folge "rotieren", bis Xj am Ende steht.  Und dann R anhängen.

Auf diese Weise erhalten wir schließlich die gewünschte Farbabfolge.

---
DAS Problem bei Farbübergängen ist, dass nicht das gleiche Übergangssymbol zum Verlassen einer Farbe verwendet werden kann, falls mit diesem vorher anfänglich schon in diese Farbe hinein gewechselt wurde.

Bei doppelt verbundenen Farben stellt dies kein Problem dar, da man im Falle einer solchen "Kollision" die Farbe mit dem anderen Symbol verlassen kann.

Auch im Falle einer einzigen Einfachverbindung kann man, ausgehend von dieser, die folgenden doppelten Verbindungen bei evtl. Kollisionen triggern. Ist die Einfachverbindung in der Mitte der Farbfolge, so erfolgt das Triggern davon ausgehend in beide Richtungen.

Abgesehen von den Verbindungsfällen 4a) 4b) 5) kann es später keine weiteren Einfachverbindungen mehr geben, wegen 3). Verbindungsfall 4a) stellt darunter wegen des dabei erfolgenden Symbolwechsels natürlich kein Problem dar.

Problematisch bleiben alleine 4b) und 5).

Die Entstehung zweier Einfachverbindungen zu solch einem "Sternzentrum" Z sollte daher gleich bei der Konstruktion der Farbfolge vermieden werden.

Wie?

Im Falle einer Sternkonstellation beginnt man mit Z, gefolgt von ALLEN Farben mit Einfachverbindung mit Z. Dies geht, da diese Farben wegen 4) 5) auch paarweise untereinander verbunden sein müssen. Damit gibt es entweder den Fall 4a) Z-A-B oder außer der ersten Einfachverbindung X1-X2 darauf folgend nur Doppelverbindungen. In der weiteren Konstruktionsfolge kann dann logischerweise keine weitere Einfachverbindung zu Z mehr entstehen.


#

---
(1
Beides folgt unmittelbar aus max. m + n - 3 Löchern,
→ minimale Lochzahl bei isolierter Einzelkarte

  x - - - - - - -
  - x x x x x x x
  - x x x x x x x
  - x x x x x x x
  - x x x x x x x

→ mehr Löcher bei Vergrößerung von isolierten Farb-/Symbol-Mengen

  x x x - - - - -
  - - - x x x x x
  - - - x x x x x
  - - - x x x x x
  - - - x x x x x

  x x x - - - - -
  x x x - - - - -
  - - - x x x x x
  - - - x x x x x
  - - - x x x x x

(2
sonst mind. 2m Löcher

(3
sonst gäbe es mind.  2m - 2 > m + n - 3 Löcher
A-B einfach verbunden →  mind. m-1 Löcher in {A,B}

(4a
sonst mind 2(m-2) + 2 = 2m -2 Löcher

  A  x - . . . .
  Z  x x . . . .
  C  - x . . . .

(4b
sonst mind. 2(m-1) Löcher

  A  x . . . . .
  Z  x . . . . .
  C  x . . . . .

(5
verbunden müssen sie sein, wegen 4)
dann sogar doppelt verbunden wegen 3)

---

Ein gesundes Neues Jahr !

Dieser Beitrag wurde zuletzt bearbeitet: 01-01-2025, 09:20 AM von umu.

[Tzimmo]

Ich habe einen anderen Beweis, dass mindestens (m-1)(n-1) + 2 Karten immer abgelegt werden können.

Der Beweis funktioniert mit Induktion nach n und m. Wenn n = 2 (der Fall m = 2 geht natürlich genauso), gibt es nur zwei Farben und mindestens m + 1 Karten. Ein Symbol x muss also in beiden Farben vorkommen. Spiele nun alle Karten außer x in der einen Farbe, dann beide x-Karten, dann die der anderen Farbe.

Seien nun m, n >= 3. OBdA ist  m <= n (sonst vertausche die Rollen von Farben und Symbolen). Von den m*n möglichen Karten fehlen höchstens m + n - 3 < 2n. Es muss also eine Farbe geben, von der höchstens eine Karte aussortiert wurde. Ansonsten würden ja mindestens zwei Karten pro Farbe fehlen, also insgesamt 2n. Sei nun f eine solche Farbe.

Fall 1: Alle m Karten der Farbe f sind vorhanden.
Entferne alle f-Karten und füge eine beliebige fehlende Karte x einer anderen Farbe hinzu (wenn es eine solche gibt). Dann hat man eine Situation mit m Symbolen, n-1 Farben und mindestens (m-1)(n-1)+2 - m + 1 = (m-1)(n-2)+2 vorhandenen Karten. Nach Induktion können diese Karten alle hintereinander abgelegt werden. Wähle eine Abfolge der Karten, mit der dies möglich ist.

Fall 1a: x ist erste oder letzte Karte der Abfolge, oder x wird zwischen zwei Karten mit dem gleichen Symbol gespielt.
Dann kann x aus der Abfolge entfernt werden, die Abfolge bleibt zulässig. Füge am Ende noch die Karten der Farbe f an (erst die mit dem gleichen Symbol wie die bisher letzte Karte, dann die anderen in beliebiger Reihenfolge). Das ergibt eine gültige Abfolge der anfangs gegebenen Karten.

Fall 1b: x wird zwischen zwei Karten mit verschiedenen Symbolen gespielt.
Ordne die Karten der Farbe f so an, dass die erste das gleiche Symbol hat wie die Karte vor x und die letzte das gleiche Symbol wie die Karte nach x. Ersetze x durch diese Abfolge und erhalte wieder eine zulässige Ablagereihenfolge.

Fall 2: Von Farbe f fehlt nur das Symbol s.
Entferne alle f-Karten. Dann hat man mindestens (m-1)(n-1) + 2 - (m-1) = (m-1)(n-2) + 2 Karten in n-1 Farben mit m Symbolen. Nach Induktion können diese Karten zu einer gültigen Ablagefolge angeordnet werden. Wähle eine solche Folge.

Fall 2a: Die erste oder letzte Karte dieser Folge hat nicht das Symbol s.
Dann gibt es eine f-Karte die direkt vor oder direkt nach der Folge ohne f abgelegt werden kann. Füge schließlich die restlichen f-Karten am Anfang bzw. am Ende an und erhalte eine gültige Ablagefolge.

Fall 2b: Die erste und letzte Karte tragen beide das Symbol s.
Dann passen erste und letzte Karte aneinander. Man kann also an einer beliebigen Stelle die Ablagefolge beginnen, bis zum Ende durchspielen und dann am Anfang beginnen, um die restlichen Karten abzulegen. Insbesondere kann man so erreichen, dass die Sequenz mit einem Symbol ungleich s endet. Ansonsten gab es nur s- und f-Karten am Anfang, ohne die Karte (f, s). Das wären maximal m + n - 2 < m+n-2 + (m-2)(n-2) + 1 = (m-1)(n-1) + 2. Nach dieser Umsortierung weiter wie in 2a.

[Linsen_mit_Spatzle]

Ich habe einen anderen Beweis, dass mindestens (m-1)(n-1) + 2 Karten immer abgelegt werden können.

...

Danke, so etwas hatte ich mir gewünscht