Schwarz - Weiss

scrub

Dravere schrieb:

Als Tipp wird noch angegeben, dass man das Prinzip der vollständigen Induktion im Beweis verwenden kann.

Und ich habe nicht die geringste Ahnung, wie ich das anstellen soll.

Natürlich, da steht es doch: vollständige Induktion. Also fang einfach mit einer Skizze an: Ein Rechteck. Und da beginnst Du mit einer "Linie" und guckst, was beim Hinzufügen einer "Linie" passieren kann.

Dravere

Jester schrieb:

Du mußt also ein bißchen genauer spezifizieren wie das gemeint ist.

Die Linien sind Geraden und zerschneiden das Rechteck. Gehen als von einer Kante des Rechtecks zu einer anderen in einer geraden Linie und nicht in einer Kurve. Es gibt keine "Linien" welche nur im Innenbereich des Rechtecks existieren. Besser? ^^

@Scrub
Was meinst du habe ich getan, einfach blindlings schnell ins Forum gerannt? Skizzen sind hier schon in riesigen Haufen vorhanden. Brauche bald eine eigene Müllabfuhr :p
Wenn sich die Linien nicht schneiden würden, dann wäre es irgendwie etwas einfacher. Aber weil sie sich schneiden und das Rechteck so zerteilen dürfen, wie sie wollen, habe ich da ein wenig Probleme. Bin sowieso nicht so das Mathegenie, als wird ein wenig genauer
Und wenn du die Lösung weisst, dann sag sie mir doch. Ich werde sie sicher nicht nur einfach hinnehmen, sondern dich so lange mit Fragen löchern, bis ich sie verstehe ... hmmm könnte jetzt allerdings für dich auch ein Grund sein die Lösung nicht raus zu rücken

Grüssli

Bashar

Dravere schrieb:

Was meinst du habe ich getan, einfach blindlings schnell ins Forum gerannt? Skizzen sind hier schon in riesigen Haufen vorhanden. Brauche bald eine eigene Müllabfuhr :p

Du könntest ja mal posten, wie weit du gekommen bist ...

scrub

.. oder wie Deine Skizzen aussehen.

MamboKurt

tip: eine Linie teilt ein Rechteck (oder auch ein polyerder) in _2_ Teile (du hast auch _2_farben).

Jester

MamboKurt schrieb:

tip: eine Linie teilt ein Rechteck (oder auch ein polyerder) in _2_ Teile (du hast auch _2_farben).

Das reicht aber nicht wirklich aus. Es ist klar, daß er ggf. umfärben muß. Er muß aber zeigen, daß das konsistent geht, sich also alles so umfärben läßt, daß das gesamte Rechteck wieder korrekt gefärbt ist. Dafür muß man schon ein paar Argumente mehr ankarren.

MamboKurt

deswegen steht da auch "tip" und nicht "lösung"

doppelmuffe

hi,

unterscheide mal die fälle
(a) die neu hinzugekommene linie liegt auf einer alten
und
(b) sie tut es nicht.

(ok, ich glaube, der tipp ist zu schwach...)

Ist noch simpel.
Das ist etwas schwieriger:
http://i11www.iti.uni-karlsruhe.de/members/mecke/publications/files/4Color.pdf

Naja, eure Hausaufgaben werde ich mal nicht machen:

Buzzwords:
- Domainen als Knoten
- Befriedigung von Constraint-Graphen
- Eigenschaften von binären Constraint-Netzwerken
- Arc-Consistency

das problem hier ist einfacher, es handelt sich nicht um beliebige graphen. wenn man das ganze als ein graphenproblem auffassen möchte, ergibt sich durch die konstruktionsvorlage nämlich die interessante eigenschaft, dass die inneren knoten alle eine gerade anzahl an kanten besitzen.

Prof84@home schrieb:

Das ist etwas schwieriger:
http://i11www.iti.uni-karlsruhe.de/members/mecke/publications/files/4Color.pdf

Du Held! Mit 4 Farben ausmalen ist doch viel leichter, als mit 2 !

Jester

Dafür darfste bei den 4 Farben aber nicht nur mit geraden Linien unterteilen, sondern ganz beliebig.
Dann isses ein bißchen schwieriger.

thordk

najo, also im grunde steht da nur "linie", nichts von gerade. könnte also ebenso was gebogenes sein sollte nicht eindeutig "gerade" gemeint sein, ist die lösung sehr einfach: unmöglich.

Dravere

Bitte noch um ein wenig mehr Hilfe. Wo ich stehe ist immer noch so gut wie bei null. Vor allem habe ich auch das Problem das ganze zu erfassen, also was ich eigentlich verwenden muss im Beweis.

Also ich kann ja zum Beispiel sagen, dass wenn ich n = 1 nehme, dass ich dann die zwei Flächen korrekt einfärben kann. Wie kann ich nun beweisen, dass dies auch für n+1 gilt?
Ich habe dann ja zum Beispiel 4 oder 3 Flächen. Die kann man genau aufteilen mit schwarz und weiss. Allerdings bringt mir das so nichts, denn die Flächen müssen ja noch entsprechen korrekt zueinander stehen. Was irgendwie durch die Geraden gegeben ist, also das nicht irgendwo am Rande ein Dreieck liegen kann. Zudem weiss ich auch, dass an einem weissen Polygon es an allen Kanten schwarze Polygone hat und bei den schwarzen Polygonen ist es umgekehrt.

Wäre also wirklich sehr dankbar um weiter Hilfe. Wieso nicht sogar gleich die Lösung? ^^
Will das nun endlich verstehen!

Grüssli

CStoll

OK, du hast ein durch n Geraden zerlegtes Rechteck korrekt eingefärbt (IV) und nimmst nun die Gerade g_n+1 dazu. Dann ist klar, daß du einige Flächen umfärben mußt (weil die durch n+1 zerschnittenen Flächen sich in zwei neue zerteilt haben) - also invertieren wir alle Flächen links von der Gerade^*.

Wenn wir uns jetzt zwei benachbarte Flächen a und b ansehen, gibt es zu ihrer Lage bezüglich g_n+1 drei mögliche Fälle:

a und b liegen beide rechts von g
a und b liegen beide links von g
g ist die gemeinsame Kante von a und b

Was kannst du in jedem Fall über die Farben von a und b aussagen? (du hast die IV und in Fall 3 auch die Vorraussetzung, daß a und b aus einer einzigen Fläche entstanden sind)

^(*) "links" ist recht willkürlich gewählt Wichtig ist, daß g das Rechteck in zwei Teile zerlegt - und die nenne ich mal "links" und "rechts".

Dravere

Hey danke CStoll. Ich glaub ich habe es nun kapiert und habe was niedergeschrieben und werde es morgen, bzw. heute abgeben. Ob es dann stimmt, werde ich erst am Montag sehen. Aber dein "Tipp" hat mich extrem auf die Sprünge geholfen und ich denke eigentlich wirklich, dass ich es begriffen habe, wie es denn nun geht ^^

Vielen Dank für die ganzen Mühen!

Grüssli