2er potenz < Sonstiges < Analysis < Oberstufe < Schule < Mathe < Vorhilfe
|
| Aufgabe | Es gelte [mm] a^{j}t=a^{j}a^{2^{i+j}-i}
[/mm]
Es stand die Behauptung im Raum: [mm] |a^{j}t|=2^{i+j} [/mm] +j-i ist nur dann 2er potenz wenn [mm] j-i=2^{i+j}. [/mm] |
Das was mich störte, war das "nur", auch wenn ich viele Möglichkeiten das es anders sein könnte schon ausschliessen kann. Aber wie kann ich wissen, dass dies für alle anderen Zahlen nicht geht? Kennt ihr da vielleicht einen coolen trick?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:37 Fr 29.12.2017 | | Autor: | leduart |
Hallo
wenn [mm] j-i=2^k-2^{i+j} [/mm] ist es auch eine 2er Potenz , k beliebig. ausserdem natürlich j-i=0
Gruß ledum
|
|
|
| |
|
ach sehr schön ,vielen dank, das werd ich demjenigen mal kurz vorn latz knallen, mal sehen :)
|
|
|
| |
|
| Aufgabe | | also ich sehe das ein ,was Du sagst, aber mein tutor nicht, er sagt(im dialog mit mir): |
Willkommen zum Forum für das Modul "Grundlagen der Theoretischen Informatik" (Kurse 01657 u. 01658).
1657 EA3 Aufgabenlösung zu Aufgabe 2
0 Punkte
Ich versuche gerade die Lösung nachzuvollziehen und bleibe folgendermaßen stecken:
Ich versuche gerade zu verstehen, warum [mm] |a^{j}t|=2^{i+j}
[/mm]
+j-i ist nur dann 2er potenz wenn [mm] j-i=2^{i+j}. [/mm] Man könnt z.b. [mm] j-i=2^{k}-2^{i+j}
[/mm]
nehmen, k beliebig , oder?
Gefragt vor 3 Tagen von scratchy (240 Punkte)
1 Antwort
0 Punkte
antwortvtutor:
[mm] j-i=2^{k}-2{i+j}
[/mm]
Nein, für ein "beliebiges" k ist das nicht möglich. k ist hier in hohem Maße von i und j abhängig. Sieht man leicht, wenn man es umformt:
[mm] j-i=2^{k}-2{i+j}
[/mm]
[mm] ⇔2^{k}=j-i+2{i+j}
[/mm]
und damit diese Formel für ein k
erfüllbar ist, sind wir wieder beim ursprünglichen Problem.
Beantwortet vor 1 Tag von Oliver Burger (3,755 Punkte)
wieder angezeigt vor 1 Tag von Oliver Burger
Ergänzende Frage von User Scratchy:
warum? wenn [mm] |a^{j}t|=2^{i+j}+j-i [/mm] und [mm] j-i=2^k-2^{i+j} [/mm] und ich die rechte seite in die linke gleichung einsetze, dann erhalte ich [mm] |a^{j}t|=2^{i+j}+2^k-2^{i+j} [/mm] und wenn es sich rechts und links immer auflöst, kann ich k beliebig wechseln und es bliebe immer eine 2er potenz. selbst wenn ich jetzt falsch liege, verstehe ich immer noch nicht, warum [mm] 2^{i+j} [/mm] die einzige lösung sein kann.
Kommentiert vor 4 Stunden von Oliver Burger (tutor):
Ausgangsbasis ist die Formel:
[mm] |a^{j}t|=2^{i+j}+j-i [/mm]
und wir wissen als Nebenbedingung, dass das Wort eine Länge [mm] a^{j}t [/mm] der Art [mm] 2^{irgendwas} [/mm] haben muss.
Wir müssen diesen Term
[mm] |a^{j}t|=2^{i+j}+j-i [/mm]
so zusammenfassen, dass rechts nur noch etwas der [mm] Art2^{irgendwas} [/mm] steht. Wenn wir in die Formel rechts ein [mm] 2^{k} [/mm] oder ähnliches einfügen, dann muss dass auch links erfolgen.
[mm] |a^{j}t|+2^{k}=2^{i+j}+j-i+2^{k}
[/mm]
Hilft uns das?
Wenn man j−i durch etwas substituieren möchte, dann ergibt sich für k die von mir ausgeführte Abhängigkeit.
Aber unser Ziel ist es, dass am Ende der rechte Teil der Formel zusammengefasst ist, ohne dass die Formel ihre Gültigkeit verliert:
[mm] |ajt|=2^{i+j}+j-i
[/mm]
Wie fasst man nun [mm] 2^{i+j}+j-i [/mm] zusammen, so dass [mm] 2^{irgendwas} [/mm] entsteht?
Wenn es eine Belegung von j und i gäbe, so dass [mm] 2^{i+j}=j-i [/mm] gilt, dann könnte man für diese konkrete Belegung (ich verwende für diese konkreten Werte nun i1 und j1), Die Formel wie folgt umstellen:
[mm] |a^{j1}t1|=2^{i1+j1}+j1-i1
[/mm]
[mm] ⇔|a^{j1}t1|=2^{i1+j1}+2^{i1+j1}
[/mm]
[mm] ⇔|a^{j1}t1|=2*2^{i1+j1}
[/mm]
[mm] ⇔|aj1t1|=2^{i1+j1+1}
[/mm]
... Ziel erreicht.
Der Lösungsvorschlag zeigt, dass es ein solche Belegung aber nicht geben kann. Eine Erweiterung um [mm] 2^{k} [/mm] kann nicht nur auf einer Seite der Formel erfolgen.
Eine andere Möglichkeit die beiden Terme zusammenzufassen (abgesehen von j=i und weiteren ähnlichen Erweiterungen, wie [mm] 2^{i+j}+2^{i+j}+2^{i+j}=j-i
[/mm]
) sehe ich auch nicht. Du?
Kommentiert vor 3 Stunden von Oliver Burger
Bearbeitet vor 3 Stunden von Oliver Burger
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:26 Mo 01.01.2018 | | Autor: | leduart |
Hallo
ich verstehe die Antwort deines Tutors nicht, wir fügen ja rechts nicht [mm] 2^k [/mm] dazu sondern wie substituieren j-i durch 2^(k)-2^(j+i)
er dagegen schreibt zurück
$ [mm] j-i=2^{k}-2{i+j} [/mm] $
ohne das 2 hoch
und ich sehe nicht, warum das nicht geht.
ich sehe auch nicht, dass ich [mm] 2^k [/mm] addiere, und es deshalb auch links addieren muss, wie er an anderer Stelle schreibt.
Gruß ledum
|
|
|
| |
|
hi ledu, ja ich seh das genauso, wobei das 2i+j mein fehler war ,ich hab das hoch vergessen, muss also natürlich [mm] 2^{i+j} [/mm] heissen . aber selbst damit finde ich das alles immer noch nicht plausibel. Wenn man mal bei Aufgaben so steckenbleibt, ist das immer wie ein Damm, den mein Lernfluss immer brechen muss, es sei denn ich find ne alternativlösung.(Das ganze war nur eine Teilaufgabe, ursprünlich sollte ich zeigen, dass die Sprache [mm] {a^{2^{n}}|n \ge 0} [/mm] unendlich viele Klassen in der Myhill-Nerode-Relation hat. Die Klassen sind hir [mm] [\varepsilon], [/mm] [a],[aa],[aaaa] usw. wobei das in den Klammern Wörter aus der Sprache sind. Mein Argument wäre jetzt einfach nur gewesen, dass für n [mm] \to [/mm] n+1 immer eine neue Klasse begründet wird, die in der vorigen nicht existiert.)
|
|
|
| |
|
> Es gelte [mm]a^{j}t=a^{j}a^{2^{i+j}-i}[/mm]
Hallo,
also [mm] a^{j}t=a^{2^{i+j}+j-i}.
[/mm]
> Es stand die Behauptung im Raum: [mm]|a^{j}t|=2^{i+j}[/mm] +j-i ist dann [...]
Warum ist jetzt plötzlich [mm] |a^{j}t|=2^{i+j}+j-i?
[/mm]
EDIT: okay, ein Tippfehler...
Du willst wissen, für welche i,j der Exponent [mm] 2^{i+j}+j-i [/mm] eine Zweierpotenz ist, bzw. ob er eine Zweierpotenz sein kann.
i,j sollen ganzzahlig sein? Oder natürliche Zahlen? Oder natürliche Zahlen und j>i?
Wenn i und j ganzzahlig sind, hat der Tutor nicht recht:
z.B. mit i=-5 und j=7 bekommt man
[mm] 2^{-5+7}+7-(-5)=2^4.
[/mm]
Allerdings vermute ich, daß diese Lösung nicht gewünscht ist, weil [mm] i,j\in \IN [/mm] sein sollen.
LG Angela
|
|
|
| |
|
Hallo Angela, also es handelt sich um natürliche Zahlen und
[mm] |a^{j}t|=2^{i+j}+j-i [/mm] steht deswegen als Betrag da, weil mich der Exponent interessiert, um rauszukriegen wann das ganze Gebilde, also bei welchem k gilt [mm] 2^{k}=2^{i+j}+j-i [/mm] ?
Ich hab die Lösung von ihm verstanden, nur nicht, warum sie eindeutig sein sollte.
Als Behelf hab ich ihm eine Alternativlösung ohne obige Spielchen, stattdessen mit Induktion angeboten und warte, ob und was er nun dazu sagt.
|
|
|
| |
|
> Hallo Angela, also es handelt sich um natürliche Zahlen
> und
> [mm]|a^{j}t|=2^{i+j}+j-i[/mm] steht deswegen als Betrag da, weil
> mich der Exponent interessiert, um rauszukriegen wann das
> ganze Gebilde, also bei welchem k gilt [mm]2^{k}=2^{i+j}+j-i[/mm] ?
> Ich hab die Lösung von ihm verstanden, nur nicht, warum
> sie eindeutig sein sollte.
> Als Behelf hab ich ihm eine Alternativlösung ohne obige
> Spielchen, stattdessen mit Induktion angeboten und warte,
> ob und was er nun dazu sagt.
>
Hallo,
irgendwie verstehe ich das ganze nicht. Für natürliche Zahlen i,j ist [mm]2^{i+j}+j-i[/mm] genau dann eine Zweierpotenz, wenn i=j. Ist die 0 erlaubt, so gibt es zusätzlich noch die Lösungen i=1,j=0 und i=2,j=0. Ansonsten ist immer [mm]2^{i+j-1}<2^{i+j}+j-i<2^{i+j+1}[/mm], woraus obige Behauptung folgt.
|
|
|
| |
|
Hallo donquijote, welche obige Behauptung meinst Du denn jetzt genau?
|
|
|
| |
|
> Hallo donquijote, welche obige Behauptung meinst Du denn
> jetzt genau?
dass [mm]2^{i+j}+j-i[/mm] nur dann eine Zweierpotenz ist, wenn i=j (und somit j-i=0) oder j=0 und [mm]i\in\{1,2\}[/mm].
Die Aussage in deinem Eingangsposting ergibt für mich keinen Sinn (so wie ich es verstanden habe), denn die Bedingung [mm]j-j=2^{i+j}[/mm] kann für [mm]i,j\ge 0[/mm] niemals erfüllt sein. Denn es gilt immer [mm]j-i\le j+i<2^{j+i}[/mm].
|
|
|
| |
|
> Die Aussage in deinem Eingangsposting ergibt für mich
> keinen Sinn (so wie ich es verstanden habe), denn die
> Bedingung [mm]j-j=2^{i+j}[/mm] kann für [mm]i,j\ge 0[/mm] niemals erfüllt
> sein. Denn es gilt immer [mm]j-i\le j+i<2^{j+i}[/mm].
Wenn ich es recht verstehe sollte im Verlaufe der Bearbeitung einer Aufgabe gezeigt werden, daß [mm] 2^{i+j}+j-i [/mm] für [mm] i,j\in \IN [/mm] nie eine Zweierpotenz ist.
Der (meiner Meinung nach ziemlich ungeschickte) Plan des Tutors war wohl, dies per Widerspruch zu zeigen:
Angenommen [mm] 2^{i+j}+j-i [/mm] wäre Zweierpotenz.
Nun sagt der Tutor: wenn es so wäre, dann kann es nicht anders sein, als daß [mm] j-i=2^{i+j},
[/mm]
und diesem Gedanken konnte pumpernickel nicht folgen,
was zur Eröffnung dieses Threads geführt hat.
So habe ich mir das zusammengereimt.
LG Angela
|
|
|
|
