Anwendung von Linearer Algebra?

... komplette Frage anzeigen

2 Antworten

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 bewerten Vielen Dank für Deine Bewertung

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. 

Antwort bewerten Vielen Dank für Deine Bewertung

Was möchtest Du wissen?