Frage von Nattie123445, 24

Anwendung von Linearer Algebra?

Hey, Wir verzweifeln gerade im Mathematikstudium ein bisschen an einer Aufgabe die lautet:

Sei n Element der N). Zeigen Sie, dass jede Teilung der Ebene mit n Geraden mit zwei Farben eingefärbt werden kann, so dass je zwei Teile mit einer gemeinsamen Kante nie von der gleichen Farbe sind.

Unser Ansatz ist dass sobald man eine weitere Gerade durch die Ebene zieht, sich jeweils an einer Seite der gerade die Farben aller Felder in die jeweils andere tauschen. Allerdings wissen wir nicht inwiefern wir das aufschreiben sollen und ob man da noch etwas rechnen muss und ob man das jetzt als Induktion rechnen soll.

Ich würde mich wirklich sehr über Hilfe freuen :)

Antwort
von kreisfoermig, 2

Beweis (ohne Induktion).

Bezeichne mit E die ganze Ebene in ℝ².

Jede Gerade, g, lässt sich durch zwei Parameter erfassen: P einen Punkt auf der Geraden und u einen Einheitsvektor, der die Richtung von g angibt (hierfür gibt es zwei Möglichkeiten für u und Kontinuum viele für P, aber bei der Angabe einer Geraden werden wir fortan immer von einer festgelegten Parameterisierung ausgehen. Gegeben eine Gerade, (P,u) definiere 

Ger(P,u) = {P+tu | t∈ℝ}
E(P,u,0) = {x ∈ E |〈x–P; Rot(u,π/2)〉< 0}
E(P,u,1) = {x ∈ E |〈x–P; Rot(u,π/2)〉> 0}.

Dann ist (E(P, u,0); E(P,u,1)) eine offene Partition von (maßtheoretisch/kategorisch) „fast“ der ganzen Ebene, E.

Seien (P⁽ᵏ⁾,u⁽ᵏ⁾) für k=1;2;…;n Parameterisierungen für paarweise verschiedene Gerade, d. h. Ger(P⁽ⁱ⁾,u⁽ⁱ⁾) ≠ Ger(P⁽ʲ⁾,u⁽ʲ⁾) für alle i≠j.

Für s ∈ {0;1}ⁿ = die 0-1-Folgen der Länge n setze

E(s) := ⋂E(P⁽ᵏ⁾,u⁽ᵏ⁾,s(k)) über alle k.

Dann ist E(s) eine offene Menge für alle s und es gilt

⋃{E(s) | s∈{0;1}ⁿ}
= ⋃{⋂{E(P⁽ᵏ⁾,u⁽ᵏ⁾,s(k)) | k∈1;2;…;n} | s∈{0;1}ⁿ}
= ⋂{⋃{E(P⁽ᵏ⁾,u⁽ᵏ⁾,s(k)) | s(k)∈{0;1}} | k∈1;2;…;n}
= ⋂{E(P⁽ᵏ⁾,u⁽ᵏ⁾,0) ⋃ E(P⁽ᵏ⁾,u⁽ᵏ⁾,1) | k∈1;2;…;n}
=* E

da E(P⁽ᵏ⁾,u⁽ᵏ⁾,0) ⋃ E(P⁽ᵏ⁾,u⁽ᵏ⁾,1) =* E für alle k und der Schnitt endlich (also abzählbar) ist. Hier bedeutet =* „bis auf eine Lebesgue-Nullmenge/magere Teilmenge gleich“.

Darüber hinaus gilt für s,s´∈{0;1}ⁿ mit s´≠ s (also s´(j)≠s(j) für ein j)

E(s) ∩ E(s´) ⊆ E(P⁽ʲ⁾,u⁽ʲ⁾,s(j)) ∩ E(P⁽ʲ⁾,u⁽ʲ⁾,s´(j))
= Ø, da s(j)≠s´(j),

also E(s), E(s´) disjunkt für s,s´ verschieden.

Daraus folgt, dass {E(s) | s∈{0;1}ⁿ} eine offene maßtheoretische/kategorische Partition von E bildet und zwar stellt alle nicht leeren irreduziblen Gebiete, die die Geraden einschränken, dar. Es reicht also aus, jedem E(s) eine Farbe zuzordnen. Setze nun

ƒ(s) = mod(#{k | s(k)=1};2)

für alle s∈{0;1}ⁿ und ordne jedem nicht leeren E(s) die „Farbe“ ƒ(s) zu. Seien s, s´∈{0;1}ⁿ verschieden, so dass E(s), E(s´) benachbart (und nicht leer) sind. Zu zeigen: dass ƒ(s)≠ƒ(s´) gilt, d. h. benachbarte Gebiete werden unterschiedlich gefärbt. Doch was bedeutet es, dass nicht leere Gebiete E(s), E(s´) benachbart sind?

Behauptung. Seien E(s), E(s´) benachbart und nicht leer. Dann unterscheiden sich s, s´ in höchstens einem Index.

Beweis. Angenommen, E(s), E(s´) benachbart (und nicht leer) und, dass es j≠k gibt mit s(k)≠s´(k) und s(j)≠s´(j).

Es gilt E(s)⊆E(P⁽ᵏ⁾,u⁽ᵏ⁾,s(k))∩E(P⁽ᵏ⁾,u⁽ᵏ⁾,s(j))=:F und somit ist E(s) (wenn auch überflüssig) durch die k-te und j-te Geraden eingeschränkt.

Es gilt E(s´)⊆E(P⁽ᵏ⁾,u⁽ᵏ⁾,s´(k))∩E(P⁽ᵏ⁾,u⁽ᵏ⁾,s´(j))=:F´ und somit ist E(s´) (wenn auch überflüssig) durch die k-te und j-te Geraden eingeschränkt.

Per Voraussetzung sind die k-ten und j-ten Geraden verschieden und zerlegen die ganze Ebene E in 4 Teile (wie durch zwei Achsen).

Da s(k) ≠ s´(k) und s(j) ≠ s´(j) liegen F, F´ quer gegenüber von einander. Somit gilt ∂(F) ∩ ∂(F´) = {Q} für einen Punkt Q. Da E(s)⊆F und E(s´)⊆F´ und alle dieser Mengen offen und F, F´ disjunkt sind, gilt ∂(E(s)) ∩ ∂(E(s´)) ⊆ {Q}. Insbesondere ∂(E(s)) ∩ ∂(E(s´)) ⊉ eine Teilgerade. Das heißt, E(s), E(s´) grenzen sie auch an keiner gemeinsamen Geraden. Widerspruch! QED.

Darum gilt für E(s), E(s´) nicht leere benachbarte Gebiete, dass s(k)≠s(k´) für höchstens ein k (und mindestens eines, sonst wären sie gleich und nicht benachbart!). Daraus ergibt sich, dass

   #{k | s(k)=1} = #{k | s´(k)=1} ± 1
⟹ mod(#{k | s(k)=1};2) ≠ mod(#{k | s(k)=1};2)
⟹ ƒ(s)≠ƒ(s´).

Also lassen sich die durch die Geraden eingeschränkten Teilgebiete 2-farbig einfärben so, dass keine benachbarten Gebiete gleichfarbig sind.

Antwort
von FataMorgana2010, 24

Sehr schöner Ansatz. Und ja - das macht man per Induktion. Schon die Formulierung: Wenn man eine weitere Gerade zieht... ist ja quasi ein Übergang von n nach n+1. 

Einfach genau so aufschreiben: bei einer Gerade ist es klar, es gibt links und rechts, dann annehmen, dass es für n Geraden eine Lösung gibt, daraus die für n+1 ableiten und fertig. 

Keine passende Antwort gefunden?

Fragen Sie die Community