Abzählbarkeit Teufel < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:51 Fr 29.10.2010 | | Autor: | emulb |
| Aufgabe | Der Teufel steckt eine beliebige Anzahl Zettel, die jeweils mit einer natürlichen Zahl beschriftet sind in dem Umschlag. Er sagt nicht, wieviele solcher Zettel er augesucht hat. Ihr sollt nun jeden jeden Tag einmal raten, as im Umschlag steckt. (Ein solcher Versuch könnte z.B. so aussehen: "Im Umschlag sind 6 Zettel mit den Zahlen 0,976,1,23,1000,100.1234,...)
Gibt es eine Ratestrategie. mit der man auf jeden Fall und nach endlicher Zeit die Hölle verlassen kann? |
Eine Bonusaufgabe 
Ich komm nicht auf das Ergebnis: Ich bin nur darauf gekommen, dass ich mit dem cantorschem diagonalverfahren auf ein ergebnis komme, d.h. ich würde irgendwann aus der hölle kommen.
aber für beliebige anzahl an zettel + natürlich zahl komm ich nicht drauf. ![[keineahnung]](/images/smileys/keineahnung.gif "[keineahnung]")
helft mir bitte...ist ja auch ne bonusaufgabe für euch
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
|
|
| |
|
Hallo rewolf,
mit den vorliegenden Angaben ist die Aufgabe nicht zu lösen. Mal abgesehen davon, dass offenbar unterstellt (aber nicht definiert) wird, dass das richtige Erraten des Umschlaginhalts das Recht verleiht, die Hölle zu verlassen, sind auch andere Dinge nicht klar.
Müssen die Zahlen in der richtigen Reihenfolge (wie im Umschlag) vorliegen?
Kann eine Zahl zweimal im gleichen Umschlag liegen?
Kann eine Zahl an verschiedenen Tagen verwendet werden oder insgesamt nur einmal?
All das müsstest Du wissen, bevor Du Cantors Diagonalbeweis darauf loslässt. Ich frage mich sowieso, wie das hier gehen soll, denn der Witz an der Sache ist das Wort "endlich". Die Antwort hierauf kann nur "nein" lauten, aber es mag sein, dass es einen Lösungsweg gibt, der eine abzählbar unendliche Ratetaktik liefert.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:05 Fr 29.10.2010 | | Autor: | emulb |
hallo reverend
also an der uni haben wir eine ähnliche aufgabe gelöst: der teufel hat einen umschlag und hat einen zettel mit [mm] \IN [/mm] . Jeden Tag darf ich eine Zahl sagen. Es ist kein Intervall vorgegeben. Die frage ist nun: wie gehe ich taktisch vor um irgendwann auf das ergebnis zu kommen. -> logisch ist: bei 1 anfangen und einfach weiterzählen Tag für Tag. Irgendwann ist die gesuchte zahl gefunden.
Die zweite aufgabe ging dann so: Der Teufel hat nun zwei umschläge und in jede davon schreib er eine [mm] \IQ. [/mm] Eine von ihm gewählte zahl. logisch ist: ich gehe diagonal voran, dh: [mm] \bruch{1}{1} [/mm] -> [mm] \bruch{1}{2} [/mm] -> [mm] \bruch{2}{1} [/mm] -> [mm] \bruch{3}{1} [/mm] -> [mm] \bruch{2}{2} [/mm] (cantorsches diagonalverfahren).
So, jetzt das aktuelle problem: beliebige umschläge mit beliebigen zettel mit natürlichen zahlen. theoretisch ist es abzählbar unendlich.
anscheinend wäre es sehr schwer, deshalb bonus.
|
|
|
| |
|
Hallo nochmal,
ah, ok.
Dann verstehe ich die Vorgeschichte. Manche der Regeln sind also mindestens implizit gegeben. So z.B., dass keine Zahl zweimal im gleichen Umschlag steckt, aber jeden Tag wieder neu verwendet werden kann. Und über die Bedingungen für eine Entlassung aus der Situation kann ich nur spekulieren, dass eine komplett richtig geratene Lösung die Befreiung des Raters zur Folge hat.
Du weißt bestimmt, dass [mm] \IR^n [/mm] gleich mächtig wie [mm] \IR [/mm] ist.
Das gilt entsprechend für [mm] \IN^k, [/mm] wobei das aufgrund der unbekannten Zahl von Zetteln noch nicht hinreichend ist. Erst die Tatsache, dass [mm] \IN^{k+1} [/mm] gleich mächtig wie [mm] \IN [/mm] ist, wird genügen...
Das eigentliche Problem aber ist nicht, das abstrakt zu zeigen, sondern eine Anordnung zu finden, die es offenbar macht. Dazu reicht es nicht, erst alle Lösungen mit einer einzigen natürlichen Zahl anzugehen, dann die mit zweien etc., weil ja schon der erste Teil (abzählbar) unendlich viele Lösungen beinhaltet. Eine Lösung mit zwei oder mehr Zahlen kannst Du dann nicht in endlich vielen Schritten erreichen.
Es ist hier aber möglich. Dazu zwei Tipps:
1) Nimm erst eine geordnete Zusammenstellung von k natürlichen Zahlen an (einen geordneten k-Tupel). Er enthält eine größte Zahl, je nach Ordnung am Anfang oder am Ende. Wie lassen sich nun alle möglichen Tupel für alle k irgendwie lexikalisch ordnen? Das ist der wesentliche Schritt.
(1), (2), (2,1), (3), (3,1), (3,2), (3,2,1), (4) ... wäre der Anfang meiner Liste. Sie hat aber ein Problem: der Tupel (1,1) taucht nicht auch, wie auch andere Tupel mit zwei oder mehr gleichen Elementen. Du brauchst einen anderen oder zumindest modifizierten Weg. Darum die Klassifizierung als Bonus-Aufgabe. 
2) Wenn die geordneten Tupel anzuordnen sind, findest Du sicher leicht einen Weg, auch alle Umordnungen mit abzuarbeiten.
Das Problem verlangt ein bisschen Einsicht in die (abzählbar) unendliche Abfolge unendlicher Kardinalitäten, wie Bolzano zeigte und Cantor vertiefte. Eigentlich genügt aber ein tiefer Einblick in [mm] \aleph_0. [/mm] Schon wenn Du zeigen kannst, dass [mm] \IN^k [/mm] nicht die Mächtigkeit [mm] \aleph_1 [/mm] besitzt, wäre das Kontinuumsproblem fast gelöst.
In diesem Sinne, viel Erfolg auf dem Weg zu Bonus.
reverend
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:31 Sa 30.10.2010 | | Autor: | emulb |
aha klingt logisch
bist du auf die lösung gekommen?
|
|
|
| |
|
Hallo emulb,
ja, ich habe eine Lösung. Man bleibt aber ziemlich lange in der Hölle.
Dafür gibt es garantiert ein endliches Ende der Zeit dort...
Im Moment sehe ich nur nicht, wie ich Dir einen besseren Tipp geben könnte als den vorliegenden. Summa summarum bleibt also vorerst nur, selbst weiter zu suchen. Hast Du schon eine Idee, an der wir hier herumbasteln könnten?
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:00 Mi 03.11.2010 | | Autor: | emulb |
ich hab keine ahnung....
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:36 Mi 03.11.2010 | | Autor: | reverend |
Hallo nehcmülb,
der letzte Tipp war in der Formulierung "summa summarum" verborgen.
$ 1=1 (1) $
$ 2=2=1+1 (2) $
$ 3=3=2+1=1+2=1+1+1 (4) $
$ 4=4=3+1=1+3=2+2=2+1+1=1+2+1=1+1+2=1+1+1+1 (8) $
$ [mm] \cdots [/mm] $
$ [mm] 5319=5319=5318+1=\cdots =\underbrace{1+1+\cdots+1+1}_{\mbox{5319 mal}} (2^{5319-1}) [/mm] $
Klarer?
Grüße
reverend
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:23 Sa 30.10.2010 | | Autor: | Sax |
Hi,
dann müsste doch folgendes Diagonalverfahren funktionieren :
es gibt eine Tabelle mit abzählbar vielen Einträgen in jeder Zeile und in jeder Spalte, die nach folgendem Schema aufgebaut ist :
in der ersten Spalte stehen die Zahlen, die man der Reihe nach raten würde, wenn man von einer Zahl im Umschlag ausgeht (also die natürlichen Zahlen),
in der zweiten Spalte stehen die Zahlen, die man der Reihe nach raten würde, wenn zwei Zahlen im Umschlag stehen (also die Cantorsche Abzählung von [mm] \IN\times\IN), [/mm]
in der dritten Spalte die Zahlen von [mm] \IN^3
[/mm]
und so fort.
Dieses Schema arbeitet man nach dem Diagonalverfahren ab.
Gruß Sax.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:42 Sa 30.10.2010 | | Autor: | reverend |
Hallo Sax,
ich sehe nicht, wie Du diese Tabelle bauen willst. Schon für 3-Tupel ist der Cantorsche Weg nur noch mühsam zu beschreiben, bei 4-Tupeln versagt er meines Erachtens.
Darüber hinaus finde ich aber auch, dass wenigstens eine Bonusaufgabe weitestgehend selbst gelöst werden sollte.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:51 Sa 30.10.2010 | | Autor: | Sax |
Hi,
wegen [mm] \IN^3 [/mm] = [mm] \IN^2\times\IN [/mm] kann doch [mm] \IN^3 [/mm] nach dem Cantorschen Weg abgezählt werden, weil [mm] \IN^2 [/mm] und [mm] \IN [/mm] abzählbar sind.
Analog für [mm] \IN^4.
[/mm]
Gruß Sax.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:52 Sa 30.10.2010 | | Autor: | emulb |
Naja es ist eine Bonusaufgabe und ich will sie ja lösen. Desahlb hab ich sie auch ins Forum gestellt, damit mir jemand sagen kann, wie ich vorgehen muss um damit auf ein "ergebnis" zu kommen.
Wenn ich sie hätte selber lösen können, wieso mach ich mir die mühe und stell sie ins Forum.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:58 Sa 30.10.2010 | | Autor: | reverend |
Hallo emulb,
Du scheinst Dich angegriffen zu fühlen. Das ist überhaupt nicht meine Absicht.
Na, Du bekommst doch genügend Tipps. Das ist auch Sinn des Forums: Dir dabei zu helfen, selbst auf eine Lösung zu kommen.
Welchen Sinn hätte Euer Bonussystem, wenn Du die Punkte für eine nicht von Dir stammende Lösung bekämst?
Wir machen hier ja auch nicht für Schüler ihre Hausaufgaben. So habe ich Deine Frage allerdings auch nicht verstanden.
Also frag ruhig, einen Anstoß bekommst Du normalerweise bestimmt.
Herzliche Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:09 Sa 30.10.2010 | | Autor: | emulb |
Das Forum soll auch nicht meine Hausaufgaben machen aber ich wollte nur einen anreiz wie ich vorgehen soll und dann kommt so ein kommentar. ich hab jetzt gelernt, dass ich nie wieder hinschreiben werde, dass es eine bonusaufgabe ist.
Vielen Dank an euch alle. Ich pick mir jetzt von allem etwas raus, mal schauen was raus kommt.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:22 Sa 30.10.2010 | | Autor: | reverend |
Hallo emulb,
ich verstehe Deine Reaktion nicht. Oder vielleicht sehe ich auch nur nicht, was Dich an meinem Kommentar so stört. Du arbeitest doch selbst an der Aufgabe, aus meiner Sicht ist alles gut. Mein Kommentar zum Thema Bonusaufgabe ging an Sax, der besser sah als ich, worum es geht, aber auch entsprechend mehr dazu schrieb. Da wollte ich halt nur daran erinneren, dass es nicht um einen Wettbewerb unter den Helfern geht, wer die Aufgabe schneller oder besser lösen kann, wobei mir genau diese Anmerkung zu weit gegangen wäre. Ich schreibe sie hier auch nur zur Erläuterung.
Du kannst ruhig angeben, wenn es eine Bonusaufgabe ist, das ist doch für alle Seiten fair. Nur bei Wettbewerbsaufgaben reagieren wir allergischer -vor allem wenn sie nicht als solche deklariert werden! - und (für mich) gehen Bonusaufgaben ein bisschen in diese Richtung, aber eben nur ein bisschen. Übungsaufgaben muss man machen, Bonusaufgaben kann man machen - wenn man kann. Dafür bekommt man dann eben einen Bonus. Es sind also keine Bonusaufgaben für uns, wie Du in Deinem ersten Post schriebst, sondern es ist eine für Dich.
Also wie gesagt, Hilfestellung jederzeit gern. Und ansonsten reagierst Du vielleicht auch etwas zu verschnupft auf eine recht gewöhnliche Äußerung.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:55 Sa 30.10.2010 | | Autor: | emulb |
ach ok wie ich gerade merke redeten wir voll aneinander vorbei. tut mir leid. es ist alles in ordnung.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:39 Sa 30.10.2010 | | Autor: | reverend |
Hallo nochmal,
natürlich darf der Teufel den Umschlag nicht jeden Tag neu befüllen. Dann kann es kein System geben (was man nachweisen kann).
Der Umschlag wird einmalig befüllt, und dann darfst Du jeden Tag einen neuen Tipp abgeben.
Sorry. Ich bin offenbar gerade abgelenkt.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:08 Sa 30.10.2010 | | Autor: | felixf |
Moin,
ganz abstrakt: zeige, dass die abzaehlbare Vereinigung endlicher Mengen wieder abzaehlbar ist.
(Allgemeiner: die abzaehbare Vereinigung abzaehlbarer Mengen ist wieder abzaehlbar.)
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:10 Sa 30.10.2010 | | Autor: | emulb |
Ich hab da mal eine Idee:
cantorsche Paarungstabelle:
| 0 1 2 3 4 y
--+----------------------->
0 | 0 2 5 9 14 .
1 | 1 4 8 13 .
2 | 3 7 12 .
3 | 6 11 .
4 |10 .
| .
x v
wie würde das funktionieren? ich bin mir da nicht so ganz sicher.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:01 Sa 30.10.2010 | | Autor: | felixf |
Moin!
> Ich hab da mal eine Idee:
>
> cantorsche Paarungstabelle:
>
> | 0 1 2 3 4 y
> --+----------------------->
> 0 | 0 2 5 9 14 .
> 1 | 1 4 8 13 .
> 2 | 3 7 12 .
> 3 | 6 11 .
> 4 |10 .
> | .
> x v
>
> wie würde das funktionieren? ich bin mir da nicht so ganz
> sicher.
Was genau tust du da? Eine Aufzaehlung von [mm] $\IN \times \IN$ [/mm] konstruieren? Was willst du damit machen? Z.B. eine der beiden Aussagen, die ich hingeschrieben hab, beweisen?
LG Felix
|
|
|
| |
|
Du musst ein Verfahren angeben, wie du nach endlich vielen Schritten jede mögliche Kombination, die der Teufel ausgewählt haben könnte, errätst.
Dabei ist klar: Der Umschlag wird nur einmal bestückt, denn sonst kann man die Lösung nur durch Zufall erreichen.
Hier die Strategie:
Du stellst dir vor, dass du - wenn du die Lösung kennen würdest - alle Zahlen auf den Zetteln und die Anzahl der Zettel addieren würdest. Das gibt eine neue natürliche Zahl S. Zu jeder möglichen Kombination des Teufels gibt es genau so eine Zahl S, aber zu je einer solchen Zahl S viele mögliche Kombinationen, aber jeweils nur endlich viele.
Jetzt gehst du Tag für Tag so vor: Du setzt die Zahl S zunächst auf 1 und gehst alle Mgl. durch. Dafür gibt es keine, denn es muss mindestens einen Zettel mit mindestens der Zahl 1 geben, was S=2 bedeutet. Also fängst du mit S=2 an und behauptest, es gibt einen Zettel mit einer 1. Weitere Mgl. für S=2 gibt es nicht. Sagt der Teufel nein, Setzt du S=3 und fragst ab: 1 Zettel mit einer 2 (oder 2 Zettel mit einer 1 und ... halt, wir sind schon bei S=3, auf dem 2. Zettel dürfte schon gar nichts mehr stehen, also geht das nicht). Dann S=4: 1 Zettel mit 3 oder 2 Zettel mit 1 und 1. Dann S=5: 1 Zettel mit 4 oder 2 Zettel mit 1 und 2 oder 3 Zettel mit ...(nein, geht nicht).
S=6: 1 Zettel mit 5 oder 2 Zettel mit 1 und 3 oder 2 und 2 oder 3 Zettel mit 1, 1 und 1 ....
Jetzt noch mal als Beispiel S=10:
1 Zettel mit 9
2 Zettel mit 1,7 oder 2,6 oder 3,5 oder 4,4
3 Zettel mit 1,1,5 oder 1,2,4 oder 1,3,3 oder 2,2,3
4 Zettel mit 1,1,1,3 oder 1,1,2,2
5 Zettel mit 1,1,1,1,1
Auf diese Weise klopfst du alle denkbaren Möglichkeiten an Zettelzahlen und an Zahlen, die darauf stehen könnten ab, ohne eine Möglichkeit auszulassen.
|
|
|
|
