Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Kette mit schwarzen und weißen Kugeln
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Kette mit schwarzen und weißen Kugeln
Seligman
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 11.01.2020
Mitteilungen: 39
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-04-02


Abend Leute,

habe ein eigentlich einfaches mathematisches Rätsel aufgegabelt und auch gelöst, frage mich aber ob es einfacher geht oder besser gesagt ob es einen konzeptionelleren Weg gibt.

das problem lautet: sei eine Kette gegeben, auf der sich in equidistanten Abständen Kugeln befinden. Also wie eine unendliche aufgespannte Perlenkette. Jede Kugel ist entweder schwarz (S) oder weiß (W).


Und die Aufgabe ist zu überlegen, wie auf einer solchen Kette, auf der die Kugeln jeweils beliebig schwarz oder weiß gefärbt sein können, drei verschiedene Kugeln gefunden werden können, die alle gleiche Farbe haben und bei den ein Punkt genau in der Mitte zwischen den anderen beiden Kugeln liegt.

Ich habe es explizit konstruiert mit Ausschlussprinzip. Angenommen, solche drei glechfarbigen Kugeln existieren nicht. Zunächst muss dann auf der Gerade eine Teilsequenz der Form ...SWWS... oder ...WSSW... auftauchen, sonst würde die Kette die unendliche sequenz SWSWS... und wir hätten eine Lösung.

oE betrachte Teilsequenz ...SWWS... und wir werden erschließen, welche Farbe die nachbarn haben müssen. bezeiche mit ...U... eine Kugel, deren farbe zunächst unbekannt ist.

Wir nehmen nach wie vor an, das es solche gesuchten drei glechfarbigen Kugeln auf der Kette nicht gibt.

...dann muss von rechts die sequenz wie folgt fortlaufen: ...SWWSUUW...

...das impliziert, dass das erste U ein S ist: ...SWWSSUW...

...also ist was zweite U ein W: ...SWWSSWW...

...der nächste rechte nachbar muss S sein: ...SWWSSWWS...

...und was kann der linke nachbar U sein in  ...USWWSSWWS...?

Sowohl S als W liefert die gesuchen drei Kugeln!


Zwar habe ich eine Lösung gefunden, aber schön finde ich sie nicht. Was ist zB, wenn wir jetzt nach fünf gleichfarbigen kugeln die ähnlihces erfüllen suchen oder was ähnliches?

Kann ich die existenz von gesuchten drei gleichfarbigen Kugeln mit oben genannten eigenschaften etwas geschickter begründen ohne Basteleien? Ein symmetrisches und oder abstraktes Argument? Also so ein knapper Existenzbeweis, der auf explizite Konstruktion verzichtet, wie ich sie gemacht habe?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Yggdrasil
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 01.07.2004
Mitteilungen: 856
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-04-07


Hallo Seligman,

ich glaube man kann den Beweis vereinfachen und einen kürzeren, symmetrischen
Teilstring als Ausgangsbasis verwenden.

Betrachten wir einmal drei Positionen, im äquidistanten Abstand, die nicht direkt nebeneinander liegen: $X, X+2N, X+4N, N>=1$.

Offensichtlich (Schubfachprinzip) haben zwei der Positionen die gleiche Farbe. Wir wählen diese aus und nehmen noch den Mittelpunkt hinzu.

O.B.d.A haben wir damit die Kombination $WSW$ gewählt (wobei der Abstand  zwischen ihnen nicht unbedingt 1 betragen muss.)
Nun braucht man nur noch die zwei Positionen davor und danach betrachten, um ein passendes Tripel zu finden.
12 345 67  # Skizze der 16 Fälle
WW WSW WW
WS     SW
SW     WS
SS     SS

Ist Position 1 oder 7 weiß, sind (1,3,5) oder (3,5,7) eine Lösung.
Anderenfalls sind 1 und 7 schwarz und damit (1,4,7) eine Lösung.

Gruß Yggdrasil



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]