Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Eindeutigkeit zeigen

Eindeutigkeit zeigen

Universität / Fachhochschule

Sonstiges

Tags: Sonstig

birdbox

13:34 Uhr, 05.05.2016

Hallo, ich hab hier eine Aufgabe wo ich wirklich nicht weiß wie ich das am besten angehen soll:

Bei einem Schachturnier mit

n

Teilnehmern spielt jeder Teilnehmer jeweils gegen alle übrigen Teilnehmer. Nehmen wir nun an, dass keine Partie mit einem Unentschieden endet. Ist es am Ende des Turniers immer möglich, die Teilnehmer so von 1 bis

n

durchzunummerieren, dass tatsächlich für alle

1 \leq i \leq n - 1

jeweils der

i

-te Teilnehmer gegen den (

i

+1)-ten Teilnehmer gewonnen hat. Ist diese Nummerierung immer eindeutig?

Freue mich auf jeden Tipp.

LG

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Roman-22

14:13 Uhr, 05.05.2016

"Gewinnen" ist nicht notwendigerweise transitiv.

>

die Teilnehmer so von 1 bis

n

durchzunummerieren
ist unklar. Müssen alle Nummern von 1 bis

n

vergeben werden? Darf eine Nummer mehrfahc vergeben werden?

Spiel es doch einmal mit einer kleinen Anzahl

n

anhand einiger Beispiele durch.

Etwa 3 Spieler,

A, B

und C.
Jetzt gewinnt A gegen

B, B

gewinnt gegen

C

und im letzten Spiel gewinnt

C

gegen A.
Wie würdest du jetzt nummerieren?

R

birdbox

21:10 Uhr, 05.05.2016

Danke Roman für deine Antwort.

hmm, also da ja ein

\leq

würd ich behaupten

A \leq B \leq C

, also eigentlich

A = B = C

.

Da ja jeder einmal gewonnen hat. Vermutlich darf man Nummern mehrfach vergeben.?

Roman-22

22:56 Uhr, 05.05.2016

>

also eigentlich

A = B = C

.
Entsprechend der Formulierung der Aufgabenstellung muss jeder eine Nummer erhalten, also zB alle die Nummer 1.

>

Vermutlich darf man Nummern mehrfach vergeben.?
Es ist deine Aufgabe. Falls man nicht darf, hast du ein Beispiel, in dem keine durchgehende Nummerierung möglich ist.
EDIT: Man darf keine Nummer mehrfach vergeben und es gibt sogar mehrere korrekte Nummerierungen für dieses Beispiel. Siehe unten.

>

Da ja jeder einmal gewonnen hat.
Diese Begründung ist nur vordergründig OK.
Nehmen wir noch einen dritten Spieler

D

dazu. Er verliert gegen A und

B,

gewinnt aber gegen C.

- - -

[

hier stand Unfug]

R

EDIT: Ich bemerke gerade beim nochmaligen Durchlesen der Aufgabenstellung, dass ich diese missverstanden bzw. zu eng interpretiert habe. Es muss "nur" der Spieler

i

gegen den Spieler

i + 1

gewonnen haben (nicht gegen alle folgenden). Daher kann man beim Beispiel mit den drei Spielern durchaus die Nummern

A = 1, B = 2

und

C = 3

vergeben.
Kontrolle: A hat gegen seinen Nachfolger

B

gewonnen, OK

B

hat gegen seinen Nachfolger

C

gewonnen.
Und mehr ist auch schon nicht mehr verlangt.
Natürlich wäre genau so gut auch die Zuordnung

B = 1, C = 2

und

A = 3

möglich, dann

B

hat gegen

C

gewonnen und

C

hat A geschlagen.

Auch im Bsp mit den vier Spielern ist die Reihenfolge

A - B - D - C

möglich, aber ebenso jede zyklische Vertauschung (das ist nicht immer so) wie zB

B - D - C - A

Die Frage der Eindeutigkeit wäre durch diese Beispiele daher geklärt.

Die Existenzfrage ist noch offen. Die könnte man relativ einfach durch Induktion positiv beantworten.

birdbox

00:30 Uhr, 06.05.2016

//edit: Aha okay, danke, so macht das ganze schon mal viel mehr Sinn :-)

Hast du bzgl. der Induktion noch einen Tipp? Wie geh ich die am sinnvollsten an?

LD90V aktiv_icon

01:55 Uhr, 06.05.2016

Naja... bei 2 Spielern ist es klar, dass es eine (eindeutige) Anordnung gibt. Wenn du einen weiteren Spieler zu n gegebenen hinzufügst, dann folgst du dem Algoritmus:

Hat er gegen den ersten Gewonnen? -> häng ihn vorne an.
wenn nicht, hat er gegen den nächsten gewonnen? -> dazwischen einfügen.
usw.

So kommt er immer hinter einen, der ihn besiegt hat und vor einen, gegen den er gewonnen hat. hat er alle verloren, landet er hinten auf der liste.

Daraus wird auch ohne die Beispiele ersichtlich, dass es im allgemeinen keine eindutige überführung geben muss, da nur bis zum ersten möglich platz durchgefragt wird, und seine siege/niederlagen gegen die später in der liste kommenden irrelevant sind.

birdbox

12:25 Uhr, 06.05.2016

Hmmm, danke für deine Antwort, nur wie zeige ich das ganze jetzt noch formal?

Roman-22

13:18 Uhr, 06.05.2016

Auch in der Mathematik darf man Texte und ganze Sätze zur Erklärung verwenden.

Du könntest aber natürlich eine Relation

G

("gewinnt") definieren und von einer Folge von Spielern

< S_{i} > i = 1 . . n

ausgehen mit der Eigenschaften, dass jedes Paar aus zwei benachbarten Gliedern in der Relation

G

enthalten ist. Jetzt führst du einen neuen Spieler SN ein und suchst den minimalen Index I mit

1 \leq I \leq n

für den

(S N, S_{I}) \in G

gilt.
Existiert I, dann wird SN vor diesem Spieler "eingehängt" (er erhält also die Nummer I und die Indexverschiebung für die nachfolgenden Glieder lässt sich sicher auch schön formal formulieren). Existiert I nicht (weil SN gegen alle anderen verloren hat), dann erhält SN die Nummer(n+1).

Facit: Vermöge der Relation

G

("gewinnt gegen") lässt sich die Menge der Spieler ordnen, jedoch ist die Ordnung nicht eindeutig.
Die Relation

G

ist aber keine Ordnungsrelation (allein schon wegen der nicht vorhandenen Transitivität).

R

anonymous

11:38 Uhr, 07.05.2016

Hallo
Vielleicht habe ich da irgendwas nicht richtig verstanden.
Aber wenn ich die Aufgabenstellung wörtlich nehme, dann lautet eine triviale Antwort:
Ein Gegenbeispiel wiederlegt die gesamte These.
Gegenbeispiel:
sei

n = 3,

> A

hat gegen

B

gewonnen,

> B

hat gegen

C

gewonnen,

> C

hat gegen A gewonnen.
Wie willst du dies nun von 1 bis

n (= 3)

durchnummerieren können?

Roman-22

00:16 Uhr, 10.05.2016

Hallo cositan.
in die gleiche Falle bin ich weiter oben am Anfang des Threads auch hineingetappt und hab dann gleich später gzeigt, wie man genau diesen Fall auf mehrere Arten durchnummerieren kann. Die Nummerierung muss nur so erfolgen, dass der Vorgänger den unmittelbaren Nachfolger (und nur diesen!) besiegt hat.

Also zB

A = 1, B = 2, C = 3

. Aber es wäre auch

B = 1, C = 2, A = 3

möglich.

Die Aufgabe ist ja eigentlich schon gelöst, der Thread aber leider nicht abgehakt worden.

R

birdbox

09:45 Uhr, 10.05.2016

Hallo Roman,

keine Sorge, ich hake alle meine Threads ab, nur bin ich damit noch nicht ganz fertig und es ist was dazwischen gekommen.

Ich bin immer noch nicht ganz sicher, wie ich das aufs Papier bringen soll...

ledum aktiv_icon

23:46 Uhr, 11.05.2016

Hallo
da du schon bei

n = 3

ein Gegenbeispiel hast, ist die Frage erledigt.weitere Mitspieler , die angeh#ngt (oder auch dazwischen geschoben) werden können daran nichts ändern.
Gruß ledum

birdbox

13:37 Uhr, 12.05.2016

Na eben nicht, wie Roman schon 2mal argumentiert hat.
LG

anonymous

18:02 Uhr, 14.05.2016

Hallo
Roman konnte mich leicht überzeugen.
Ich verstehe die Aufgabe jetzt selbst so, dass die benannte Reihenfolge offen ist,

d . h

. dass nicht geprüft oder erforderlich ist, dass der letzte in der Reihe gegen den ersten in der Reihe gewonnen oder verloren hat.
Das Beispiel

> A

gewinnt gegen

B

> B

gewinnt gegen

C

> C

gewinnt gegen A
hat drei gültige Reihenfolgen, nämlich

1 .) A, B, C

2 .) B, C, A

3 .) C, A, B

(und die Tatsache, dass der letztgenannte jeweils gegen den erstgenannten gewonnen hat, spielt in der Aufgabe keine Rolle).

Zu unser aller Erheiterung: Ich war auf den Einwand Romans natürlich erst mal trotzig, und suchte unter 4 Spielern

A, B, C, D

ein Gegenbeispiel.
Ich habe (natürlich) keines gefunden.
Aber - das systematische Suchen half mir, einen Beweis für die geforderte Reihenfolge/Durchnummerierung zu finden.
Tipp: vollständige Induktion.

Bevor ich jetzt viele Worte mache... angesichts der mühsamen Fortschritte und Stillephasen der letzten Tage wäre es jetzt hilfreich, birdbox, klar zu stellen, wo du stehst, wie weit du bist, ob du noch Hilfe suchst...

Roman-22

19:26 Uhr, 14.05.2016

Den Ansatz mit vollständiger Induktion hat eigentlich LD90V bereits eingebracht.

Ich glaube, das eigentliche Problem von birdbox ist die konkrete exakte Ausformulierung dieses "Einhängens" des (n+1)-ten Spielers in die vorhandene Kette an einer richtigen Stelle - sei es mit Relationen oder anders.

R

anonymous

20:26 Uhr, 14.05.2016

Upps, ja, hast Recht.
Es steht eigentlich alles schon da.
Wer lesen kann, ist klar im Vorteil...

Ich wage noch folgende Ergänzung, Verdeutlichung:
Für die Frage, ob die Reihenfolge/Durchnummerierung stets eindeutig wäre:
Hierfür aber genügt ein Gegenbeispiel.
ZB. das 'Gegenbeispiel' das wir jetzt schon mehrfach andiskutiert hatten.
Wenn

> A

gegen

B

gewinnt,

> B

gegen

C

gewinnt,

> C

gegen A gewinnt,
dann hatten wir ja schon 3 Lösungen angesprochen.
Tja, und 3 Lösungen sind eben nicht eindeutig.

birdbox

17:20 Uhr, 17.05.2016

Hmmm ich komm irgendwie noch nicht ganz dahinter, hab mal was formuliert:

Bereits sortierte Spieler:

S_{1}, . . ., S_{i}, . . . S_{n}

K (S_{j}) :=

eingeordnete Position, d.h.

K (S_{1}) = 1

S_{n e u}

gewinntGegen

S_{1} \Rightarrow K (S_{n e u}) = 1 \land K (S_{1 - a l t}, . . . S_{n}) = K (S_{1 - a l t}, . . . S_{n}) + 1

S_{n e u}

gewinntGegen

S_{n} \Rightarrow K (S_{n e u}) = K (S_{n}) + 1

S_{n e u}

gewinntGegen

S_{i} \Rightarrow K (S_{n e u}) = K (S_{i}) \land K (S_{i - a l t}, . . . S_{n}) = K (S_{i - a l t}, . . . S_{n}) + 1

Okay Induktionsbasis ist klar, ich mache n=2 und da gibt es 2 Fälle:
1) S1 gewinnt gegen S2, dann

K (S 1) = 1 \land K (S 2) = 2 \Rightarrow 1 \leq 2

2) S2 gewinnt gegen S1, dann

K (S 1) = 2 \land K (S 2) = 1 \Rightarrow 1 \leq 2

Aber was mach ich im Induktionsschritt, bzw. wie zeige ich den??? Hmm...

Roman-22

17:48 Uhr, 17.05.2016

>

Aber was mach ich im Induktionsschritt, bzw. wie zeige ich den??? Hmm...
Indem du eine Vorschrift angibst, wie du ZB aus der alten Folge von korrekt angeordneten Spielern

< S_{i} >

mit

i = 1, . . n

unter Hinzufügen eines neuen Spielers

N

eine neue Folge

< T_{i} >

mit

i = 1, . . n + 1

bildest, die der Forderung "

T_{i}

hat gegen

T_{i + 1}

gewonnen für

1 \leq i \leq n

" genügt.
Also indem du sagst, wie du den neuen Spieler einhängst.

In Worten vergleichst du den neuen

N

solange mit

S_{1}, S_{2},

etc. bis du auf den ersten Spieler

S_{I}

stößt, gegen den

N

gewonnen hat.

N

wird nun vor diesem eingereiht. Sollte

N

aber gegen alle anderen verloren haben, wird er als letzter in der Liste drangehängt.

Wir suchen also ein I mit der Eigenschaft I

= min (i \in {1 . . n} | N > S_{i})

. Dabei soll das

>

Zeichen die Relation "gewinnt gegen" bezeichnen. Das kannst natürlich noch formaler ausführen in dem du eine Relation

G \subseteq S \times S

definierst

. .

. Wobei

S

ja eigentlich eine Folge und keine Menge ist, also müsstest du erst noch die Menge aller Spieler definieren

. .

.
Anstelle der Folge kannst du auch eine bijektive Abbildung der Menge

{1,2, ..., n}

auf die Menge der Spieler definieren. Ja, das Ganze formal sauber und doch kurz aufzuschreiben ist sicher eine Herausforderung.

Jetzt sind jedenfalls zwei Fälle zu unterscheiden

1)

Dieses

I

existiert
Dann gilt

T_{i} = S_{i}

für

1 \leq i < I

T_{I} = N

T_{i} = S_{i - 1}

für

I < i \leq n + 1

2)

Dieses

I

existiert nicht (weil

N

gegen alle verloren hat), dann gilt

T_{i} = S_{i}

für

1 \leq i \leq n

und

T_{n + 1} = N

R

birdbox

22:40 Uhr, 17.05.2016

Hallo Roman, vielen Dank für deine Antwort.
Also das mit den 2 Fällen hab ich mir auch so ähnlich gedacht, ok also du ordnest ja schon erfolgreich ein, bzw. man kann eigtl sehen dass man einsortieren kann, aber ist das dann auch "schon" bewiesen? Ich hasse solch Art von Induktion :(

LG

Roman-22

23:17 Uhr, 17.05.2016

>

aber ist das dann auch "schon" bewiesen?
Ja.

Wenn du einen Induktionsanfang hast, der ja nicht schwer zu finden ist mit ZB zwei Spielern hast du damit gezeigt dass es, wenn

n

Spieler nach den Regeln anordenbar

sin,

es auch

n + 1

Spieler sind. Du machst das, indem zu von den

n + 1

Spielern zunächst einen beliebigen entfernst. Nun kann man die verbleibenden

n

Spielern sicher den Regeln gemäß linear anordnen (Induktionsvoraussetzung).
Danach zeigst zu, dass es mit der beschriebenen Vorgangsweise immer möglich ist, den letzten Spieler korrekt einzufügen. Daher sind auch

n + 1

Spieler immer anordenbar und das wars dann schon.

R

birdbox

20:43 Uhr, 18.05.2016

Super vielen Dank, habs hinbekommmen, habe es aber ein klein wenig anders gemacht.

Vielen Dank für deine tollen Tipps!!! Hast mir sehr geholfen.
Ihr habt mir alle sehr geholfen!

LG

1307697

1305421

	Status: nicht eingeloggt	Noch nicht registriert?