Forum: Offtopic Mathe Beweis mit Potenzen


von Test T. (meinbenutzeraccount)


Lesenswert?

Hallo,

Die Zahl 2*n (n ist eine natürliche Zahl) kann auf k verschiedene 
Möglichkeiten als Summe von 2er-Potenzen mit natürlichem Exponenten 
(auch 0 erlaubt) dargestellt werden, wobei jeder Summand höchstens 3 mal 
in der Summe vorkommen darf.

Beweise, dass die Zahl 2*(n+1) auf k+1 verschiedene Arten als Summe von 
2er Potenzen dargestellt werden kann.

Bsp.:
 ,    also 3 verschiedene Möglichkeiten.
,   also 4 Möglichkeiten.

Ich bin auch mit Ansätzen zufrieden.

Maik

von Uwe N. (ex-aetzer)


Lesenswert?

Hab mir grad einen Tee angesetzt. Reicht das auch, Maik oder Mark oder 
wie heisst du denn nun ??

Siehe: Beitrag "Buch schreiben"

von Daniel R. (daniel_r)


Lesenswert?

Hi,

das sieht nach diskreter Mathematik aus. Da muss man eine Weile drüber 
nachdenken. Solche Lösungen schüttelt man nicht mal eben aus dem Ärmel. 
Da ich momentan keine Lust habe, darüber nachzudenken, empfehle ich Dir 
das Buch "Diskrete Strukturen 1" von Angelika Steger. Da steht das 
nötige Rüstzeug drin, sowas zu lösen.

von Jean G. (chivas)


Lesenswert?

>Ich bin auch mit Ansätzen zufrieden.

Hilft dir vollständige Induktion schon weiter? Such einfach mal im Netz 
nach ein paar Beispielen, vielleicht kommst du dann drauf.

von Test T. (meinbenutzeraccount)


Lesenswert?

Ich weiß wohl was vollständige Induktion ist. Um das Verfahren hier 
anwenden zu können, müsste man hier aber zeigen, dass wenn eine Zahl 
2n_0  k Möglichkeiten hat als Summe geschrieben werden zu werden, die 
Folgezahl 2n_0+2 eben k+1 Möglichkeiten hat.
Das erscheint mir nicht wirklich leichter zu sein als das 
Ausgangsproblem.

Maik

von Läubi .. (laeubi) Benutzerseite


Lesenswert?

Irgendwie fehlt mir da die Angabe wodurch k festgelegt ist...
Soll das irgnedwas sein wie (k-1)*2 = n ??
ansonsten würde ich hier die Induktion über k führen.

von D. I. (Gast)


Lesenswert?

Daniel R. schrieb:
> Hi,
>
> das sieht nach diskreter Mathematik aus. Da muss man eine Weile drüber
> nachdenken. Solche Lösungen schüttelt man nicht mal eben aus dem Ärmel.
> Da ich momentan keine Lust habe, darüber nachzudenken, empfehle ich Dir
> das Buch "Diskrete Strukturen 1" von Angelika Steger. Da steht das
> nötige Rüstzeug drin, sowas zu lösen.

Das ist wohl ein wenig mit Kanonen auf Spatzen geschossen :)

Edit: Auch scheint mir die Aufgabenstellung ein wenig unschlüssig.

3*2^1 ist für mich keine 2er Potenz

Edit 2: Auch die angegeben Lösungen scheinen mir falsch: 4 = 2^0 + 2^0 + 
2^1
also gibt es noch mehr Möglichkeiten, aber das Problem scheint mir nicht 
sonderlich schwierig bis auf diese Beschränkung.

von Daniel R. (daniel_r)


Lesenswert?

>Das ist wohl ein wenig mit Kanonen auf Spatzen geschossen :)

Mag sein, aber das Buch ist sehr gut. Kombinatorik wird ausgiebig 
behandelt und man kann es sich bei Springer kostenlos herunterladen.

Induktion ist tendentiell der falsche Ansatz, da man nichts "für alle n" 
beweisen muss, sondern nur einen Fall.

>Irgendwie fehlt mir da die Angabe wodurch k festgelegt ist...
k braucht man nicht. Man soll ja lediglich zeigen, dass es eine 
Möglichkeit mehr gibt, 2(n+1) darzustellen, als 2n.

von Wegstaben V. (wegstabenverbuchsler)


Lesenswert?

ich versteh bis heute nicht genau, was die Mathematiker mit ihren 
merkwürdigen "beweisen sie dies, beweisen sie jenes"  bezwecken, und 
warum oder ob da jemanden einer abgeht, wenn ein Beweis (vielleicht noch 
besonders "elegant") geführt werden konnte. Das scheint mir eine 
brotlose Kunst zu sein.

Naja, die Schönheit von surjektiven Homomorphismen von Monoiden 
erschließt sich halt nicht jedem.

von Gerry E. (micky01)


Lesenswert?

Ich habe lange überlegt, ob ich das hier absenden soll; aber es hat dann 
doch gereicht auf den Knopf zu drücken:

Wegstaben Verbuchsler schrieb:
> ich versteh bis heute nicht genau, was die Mathematiker mit ihren
> merkwürdigen "beweisen sie dies, beweisen sie jenes"  bezwecken, und
> warum oder ob da jemanden einer abgeht, wenn ein Beweis (vielleicht noch
> besonders "elegant") geführt werden konnte. Das scheint mir eine
> brotlose Kunst zu sein.
>
> Naja, die Schönheit von surjektiven Homomorphismen von Monoiden
> erschließt sich halt nicht jedem.

Ist ja auch nicht nötig. Im Endeffekt reicht es aus, dass gewisse 
Ergebnisse der Mathematik von vielen benutzt werden können, sich in der 
realen Welt zurecht zu finden. Schließlich handelt es sich immer nur um 
Modellbildung, die aber in sich schlüssig sein muss.

Beispiele:
1. Dreisatz
2. Prozentrechnung
3. FFT
...

Man glaubt es nicht, aber die gängigen mathematischen Beweisverfahren 
sind keinesfalls Selbstzweck, sondern vielmehr ein Werkzeugkasten 
(Neudeutsch Toolbox) der dazu dient, neue Ideen und Ansätze in einer 
Theorie entweder zu verankeren oder sie zu verwerfen. Die Benutzung 
einer solchen Toolbox muss aber erlernt werden!!!

Du hast es ja bereits erwähnt mit dem Begriff "elegant". Da mehrere 
Verfahren zum Ziel führen können, so nimmt der Fachmann einfach 
dasjenige mit dem geringsten Aufwand. Das tut doch jeder erfahrene 
Praktiker. Ihr kennt alle den Spruch "Übung macht den Meister". Warum 
sollte es in Mathe anders sein?

Wie kommst Du eigentlich auf "brotlos"? Mathematik ist doch die 
Wissenschaft schlechthin. Alle mir bekannten seriösen 
Naturwissenschaften benutzen Ergebnisse der Mathematik. Sogar der 
Elektriker von nebenan, obwohl der oft nur mit Wissen schafft...

von Stephan M. (stephanm)


Lesenswert?

Wegstaben Verbuchsler schrieb:
> ich versteh bis heute nicht genau, was die Mathematiker mit ihren
> merkwürdigen "beweisen sie dies, beweisen sie jenes"  bezwecken, und
> warum oder ob da jemanden einer abgeht, wenn ein Beweis (vielleicht noch
> besonders "elegant") geführt werden konnte.

Ein Beweis ist der Schluss von bekannten, als Wahr angenommenen Aussagen 
auf neue Aussagen mit einem gewissen Sinngehalt. Insofern fällt in der 
Mathematik - im Gegensatz zu so manch anderer Wissenschaft - sehr wenig 
vom Himmel. Das meiste ist, wie die Aussage von Kronecker sagt: "Die 
ganzen Zahlen hat der liebe Gott gemacht, alles andere ist 
Menschenwerk".

Es gibt halt nicht nur eine Handvoll Mathematiker auf diesem Planeten, 
sondern eine gewisse Menge, und wie immer bei wissenschaftlichen 
Aussagen - "man", also die Forschungsgemeinschaft, möchte sie 
nachvollziehen können. Je eleganter ein Beweis, d.h. je verständlicher, 
klarer er (in der Sprache der Mathematiker) formuliert ist, um so größer 
ist der Kreis derjenigen, die sich aktiv mit aktuellen Themen anderer 
Forschungsgruppen beschäftigen können. Elegante Beweise sind demnach 
deutlich mehr als nur Gewichse von Universitätsdödeln. Wie ists denn in 
der Elektronik? - Die meistgenutzten Theorien, denke ich, sind die, die 
sich in prägnanten kurzen Aussagen und Formeln merken, niederschreiben 
und anwenden lassen, oder?

Die Mathematik fusst auf einem gewissen, nicht wirklich abwegigen 
Logikkalkül und darüber hinaus auf recht wenigen Grundaussagen. Das ist 
IMHO sowohl Segen als auch Fluch dieser Wissenschaft. Gib einem 
Mathematiker die natürlichen Zahlen und eine Hand voll Regeln für 
logische Deduktion und er wird Dir in einer halben Stunde erzählen, wie 
man von dort zur Differentialgeometrie kommt, die in der theoretischen 
Physik verwendet wird, um z.B. kosmologische Phänomene zu beschreiben.

Andererseits produziert die Mathematik immer wieder Aussagen, die so 
garnicht in das hübsche Bild passen mögen, das man als 
Mathematikanwender von dieser Wissenschaft so gerne haben möchte. Das 
Banach-Tarski-Paradoxon ist meiner Meinung nach eines der schönsten 
Beispiele dafür, dass Mathematik halt eben nicht diese griffige, 
gefällige Wissenschaft ist, die sich nahtlos in den uns beliebenden 
Vorstellungsraum projezieren lässt: Lass die Mathematiker einen Begriff 
für Volumina von Körpen begründen und sie erzählen Dir am Schluss, dass 
man aus einem Liter Wasser problemlos zwei machen kann, zumindest wenn 
man dem "Liter", um den es hier geht, (s)eine mathematische Auffassung 
zu Grunde legt.

Allerdings sind diese Dinge auch in den Kreisen der Mathematiker nicht 
unumstritten. Manche Mathematiker lehnen Aussagen wie das 
Banach-Tarski-Paradoxon ab und versuchen, eine Mathematik zu betreiben, 
die ohne diese zwangsläufigen Schlussfolgerungen auskommen kann. 
Interessanterweise wird dabei aber nicht etwa die Mathematik völlig 
umgekrempelt - oh nein, es wird geringfügig an den Grundfesten der 
Mathematik herumgeschraubt (ZF- vs. ZF+C-Mengenlehre), und schon landet 
man in einer deutlich anders gearteten mathematischen Welt.

Das wahre Juwel dieser Wissenschaft ist, dass die (reine) Mathematik 
völlig ohne jede Empirik eine Wissenschaft aufgebaut hat, die universell 
und präzise zur Formulierung naturwissenschaftlicher Phänomene 
herangezogen werden kann. Ohne sie würden viele hier vermutlich 
immernoch am Lagerfeuer mit den Mammuts kuscheln und möglicherweise 
Elektronen zählen, aber über die 12 (= ca. 6 eigene Finger + die 
ungefähr 11 des Nachbarn) nicht hinauskommen...

Und übrigens: Ein gestandener Mathematiker kann Dir ohne Probleme die 
Wurstkatastrophe erklären, ohne je eine derartige Bude besucht oder gar 
von Innen gesehen zu haben ;-)

Stephan (der sich während seines Studiums irgendwann sehr geärgert hat, 
dass er nicht Mathematik studiert hat!)

P.S., um auch mal wieder On-Topic zu werden: Nein, trotz einiger Stunden 
Überlegungen weis ich für das Eingangs genannte Problem keinen Rat. 
Vielleicht ein geschickt gewählter Isomorphismus und dann ein 
Dimensionsargument? ;-)

von D. I. (Gast)


Lesenswert?

So habe mir noch Gedanken gemacht. Ich habe zwar keinen vollständigen 
Beweis aber die Idee kann ich liefern:

Was du nun zeigen musst:

Eine neue Zahl bildet sich immer durch die vorangegangene + 2, also:

Zeige: Es gibt nur (k+1) gültige Kombinationen (ohne wiederholung oder 
mehr als 3 mal derselbe Summand) zwischen den k Termen von 2*n und den 2 
Termen von 2.

Ich kann auch noch einen Fakt zum besten geben da ich das mal in einer 
Programmieraufgabe programmieren musste:

Für jede natürlich Zahl r existiert eine Zahl nichtnegative ganze Zahl k 
so dass gilt: Die letzten r Stellen der Zahl 2^k besteht nur aus 1en und 
2en.

  

von Test T. (meinbenutzeraccount)


Lesenswert?

Christopher D. schrieb:
> So habe mir noch Gedanken gemacht. Ich habe zwar keinen vollständigen
> Beweis aber die Idee kann ich liefern:
>
> Was du nun zeigen musst:
>
> Eine neue Zahl bildet sich immer durch die vorangegangene + 2, also:
> Zeige: Es gibt nur (k+1) gültige Kombinationen (ohne wiederholung oder
> mehr als 3 mal derselbe Summand) zwischen den k Termen von 2*n und den 2
> Termen von 2.

Hallo,

ich kann nicht erkennen, wie mir das helfen soll. Du hast doch nur die 
Aufgabe leicht umformuliert, oder?

Maik

von Paul B. (paul_baumann)


Lesenswert?

Wenn man das so liest, bekommt man direkt Potenzstörungen...;-)

MfG Paul

von Läubi .. (laeubi) Benutzerseite


Lesenswert?

Daniel R. schrieb:
> Induktion ist tendentiell der falsche Ansatz, da man nichts "für alle n"
> beweisen muss, sondern nur einen Fall.
Also für einen Fall hat er es doch schon gezeigt, landläufig bekannt als 
Induktionsanfang.

>>Irgendwie fehlt mir da die Angabe wodurch k festgelegt ist...
> k braucht man nicht. Man soll ja lediglich zeigen, dass es eine
> Möglichkeit mehr gibt, 2(n+1) darzustellen, als 2n.

Also wäre doch die Induktionsbehauptung das wenn 2n, k Möglichkeiten 
hat, 2(n+1), k+1 Möglichkeiten hat.

Wie der Induktionsschritt aussehen könnte hat ja  Christopher D. schon 
angedeutet.

Ggf. ist es auch einfacher anzunehmen das für beliebig großes n die 
Aussage gilt und das wenn 2n die Aussage gilt das es k Kombinationen 
gibt, dann 2(n-1) nur k-1 Kombinationen hat.

Das Problem des Anfangs sit aber auch, das man erstmal beweisen müsste 
das es nicht noch andere Kombinationen gibt ;)

von Daniel R. (daniel_r)


Lesenswert?

Gut, "falscher Ansatz" ist auch der falsche Ausdruck. Das könnte schon 
klappen mit Induktion (könnte aber auch nicht). Was ich sagen wollte 
ist, dass man solche Probleme eher mit kombinatorischen Beweisen angeht 
oder versucht, das Problem auf elementare Zählprobleme zurückzuführen.

von Filth _. (filth)


Lesenswert?

Bin ich froh, dass die Zeiten vorbei sind :D

von Anon N. (fuechslein)


Lesenswert?

Ne paar Tips:
- Schau dir die darstellung von der zahl 6 sehr genau an.
- ueberleg dir ob es drei terme mit 2^0 geben kann, warum nicht?
- ueberleg dir wie du die +2 von 2N+2 darstellen kannst und was passiert 
falls falls du diese darstellungen hinzuaddierst und ueberleg dir welche 
faelle auftreten koennen (3 faelle).

Dann solltest du fertig sein.

von Test T. (meinbenutzeraccount)


Lesenswert?

Anon Nymous schrieb:
> - Schau dir die darstellung von der zahl 6 sehr genau an.

???

> - ueberleg dir ob es drei terme mit 2^0 geben kann, warum nicht?
Natürlich nicht, da immer gilt 2|2N, was falls ein Term oder drei Terme 
2^0 auftauchen, nicht gegeben wäre.


> - ueberleg dir wie du die +2 von 2N+2 darstellen kannst und was passiert
> falls falls du diese darstellungen hinzuaddierst und ueberleg dir welche
> faelle auftreten koennen (3 faelle).

1. Möglichkeit:
Die Darstellung hat keine Terme 2^0. In diesem Fall kann man einfach 
2^0+2^0 dazu addieren, um neue Ausdrücke zu erhalten. Gibt es für 2N X 
Darstellungen, in denen keine Terme mit 2^0 vorkommen, gibt es für 2N+2 
wieder X Darstellungen.

2. Möglichkeit:
Die Darstellung hat 2 Terme 2^0. In diesem Fall kann es möglich sein, 
muss es aber nicht, dass man neue Darstellungen der Art 2^0+2^0+2^1 oder 
2^1+2^1 findet.



Ich weiß nicht, wie das weiterhelfen soll.

Maik

von Yalu X. (yalu) (Moderator)


Lesenswert?

@Maik:
Woher oder von wem stammt eigentlich diese Aufgabe? Sich so ein Problem
auszudenken, ist noch ein ganzes Stück schwieriger als es zu lösen.

von Test T. (meinbenutzeraccount)


Lesenswert?

Sie stammt aus einer Übung 3. Semester Informatik.

Bisher hat aber niemand die Aufgabe gelöst. Es wurden nur wage 
Vorgehensweisen vorgeschlagen.
(Daher ist es schwierig zu sagen, ob die Lösung der Aufgabe leichter ist 
als sich solch ein Problem auszudenken)

Maik

von D. I. (Gast)


Lesenswert?

Yalu X. schrieb:
> @Maik:
> Woher oder von wem stammt eigentlich diese Aufgabe? Sich so ein Problem
> auszudenken, ist noch ein ganzes Stück schwieriger als es zu lösen.

Wahrscheinlich so Leute die sich die diesjährigen World Finals Aufgaben 
ausgedacht haben welche gestern stattfanden ;)

http://acm.uva.es/archive/nuevoportal/region.php?r=wfi&year=2009

von S. B. (Gast)


Lesenswert?

Wenn ich das richtig verstanden habe, läuft der Beweis wie folgt:

2*n :

1.)    2*1 = 2 = 0*2⁰ + 1*2¹
2.)    2*2 = 4 = 0*2⁰ + 0*2¹ + 1*2²
3.)    2*3 = 6 = 0*2⁰ + 1*2¹ + 1*2²
....
k.)    2*k =  a*2⁰ + b*2¹ + c*2²


2*(n+1) :

1.)    2*(1+1) = 4 = 0*2⁰ + 0*2¹ + 1*2²
2.)    2*(2+1) = 6 = 0*2⁰ + 1*2² + 1*2²
....
k.)    2*(k+1) = 2*k + 2 = a*2⁰ + (b+1)*2¹ + c*2²

Wenn man jetzt für 2*n die k+1. Möglichkeit errechnen würde käme man auf 
die k. Möglichkeit für 2*(1+k)

qed

von Test T. (meinbenutzeraccount)


Lesenswert?

Hallo,

geht es wirklich so?

Es geht doch darum eine bestimmte Zahl 2*n auf k verschiedene Arten als 
Summe darzustellen und dann festzustellen, dass die Zahl 2*(n+1) auf k+1 
Arten dargestellt werden kann!

Was du aufschreibst ist doch nur, dass man eine Zahl 2*n, wobei n im 
Intervall zwischen 2 und k liegt, auf EINE bestimmte Art und Weise als 
Summe schreiben kann. Dann schreibst du, dass man aus einer Darstellung 
der Zahl 2*n automatisch auf eine Darstellung der Zahl 2*(n+1) schließen 
kann.

Aber das reicht doch nicht aus!?

Maik

von Uhu U. (uhu)


Lesenswert?

> das Buch "Diskrete Strukturen 1" von Angelika Steger

Daniel R. schrieb:
> Mag sein, aber das Buch ist sehr gut. Kombinatorik wird ausgiebig
> behandelt und man kann es sich bei Springer kostenlos herunterladen.

Wo?

von Yalu X. (yalu) (Moderator)


Angehängte Dateien:

Lesenswert?

Test Test schrieb:
> Sie stammt aus einer Übung 3. Semester Informatik.

Und ich dachte, du gehst noch zur Schule:

  Beitrag "Buch schreiben"

Irgendwie erinnert mich diese Aufgabe bzgl. Qualität und Schwierigkeits-
grad an mathematische Schülerwettbewerbe, die ich natürlich nicht durch
die Veröffentlichung einer Lösung kaputt machen möchte.

Da die Aufgabe aber zumindest im gerade laufenden Bundeswettbewerb
Mathematik nicht auftaucht und sie auch nicht mehr ganz neu zu sein
scheint¹, gehe ich jetzt davon aus, dass sie tatsächlich aus irgendeiner
Übung stammt und poste hier mal meinen Lösungsvorschlag. Weil er einige
Formeln im laufenden Text enthält, was das Forum nicht unterstützt, habe
ich ihn als PDF angehängt (sieht auch schöner aus).

Ich bin mir fast sicher, dass es einen eleganteren Weg gibt, der auch
auf einer Seite Platz hat, aber der Grundgedanke dürfte schon der
richtige sein.

Maik, jetzt musst du mir nur noch verraten, ob der Professor bzw. der
Übungsleiter eine Lösung der Aufgabe hat :)

————————————————
¹) Sie tauchte — allerdings ohne Lösung — letzten November hier auf
   http://www.physicsforums.com/showthread.php?t=358341
   und vor knapp zwei Jahren in ähnlicher Form hier
   http://www.mathlesstraveled.com/?p=113

von Daniel R. (daniel_r)


Lesenswert?


von S. B. (Gast)


Lesenswert?

> wobei jeder Summand höchstens 3 mal in der Summe vorkommen darf.

stimmt, das habe ich falsch interpretiert - die Zweierpotenzen können 
tatsächlich bis unendlich gehen, dürfen aber nur maximal 3 mal 
vorkommen.
Die Lösung des Übungsleiters würde mich auch mal interessieren :-)

von Jörg W. (dl8dtl) (Moderator) Benutzerseite


Lesenswert?

Yalu X. schrieb:
> Weil er einige
> Formeln im laufenden Text enthält, was das Forum nicht unterstützt, habe
> ich ihn als PDF angehängt (sieht auch schöner aus).

Doch, doch. ;-)

von Yalu X. (yalu) (Moderator)


Lesenswert?

Jörg Wunsch schrieb:
> Yalu X. schrieb:
>> Weil er einige
>> Formeln im laufenden Text enthält, was das Forum nicht unterstützt, habe
>> ich ihn als PDF angehängt (sieht auch schöner aus).
>
> Doch, doch. ;-)

Mit "Formeln im laufenden Text" meinte ich eher so etwas:

  … mit

von Yalu X. (yalu) (Moderator)


Lesenswert?

Upps, im letzten Post wurde einfach mein Text abgeschnitten :-/

Ich wollte eigentlich schreiben:

8><---------------------------------------------------------------------

Jörg Wunsch schrieb:
> Yalu X. schrieb:
>> Weil er einige
>> Formeln im laufenden Text enthält, was das Forum nicht unterstützt, habe
>> ich ihn als PDF angehängt (sieht auch schöner aus).
>
> Doch, doch. ;-)

Mit "Formeln im laufenden Text" meinte ich eher so etwas:

  … mit i ∈ ℕ₀ dargestellt werden …
        ^^^^^^
Das geht m.W. im Forum derzeit nur mit Unicode-Zeichen, mit denen man
sich aber fast einen abbricht.

Aber auch der LaTeX-Modus für abgesetzte Formeln ist manchmal etwas
nervig, weil die Eingaben auf Grund fehlender Fehlermeldungen schwer zu
debuggen sind. Bei einem längeren Text wie dem in meinem letzten Beitrag
ist es deswegen angenehmer, ihn offline zu schreiben, zu TeXen und dann
als PDF zu posten.

8><---------------------------------------------------------------------

allerdings mit einem "mathematical small letter i" (U1D456) statt des
normalen 'i'. Das hat die Forensoftware wohl etwas verwirrt. Die anderen
Sonderzeichen scheinen keine Probleme zu machen.

In der Vorschau wurde der Text übrigens vollständig und richtig
dargestellt.

von Andreas S. (andreas) (Admin) Benutzerseite


Lesenswert?

Interessanter Bug den du da gefunden hast. MySQL unterstützt keine 
4-Byte-Zeichen in UTF-8, und schneidet den Text intelligenterweise 
einfach da ab wo das Zeichen steht. Informiert wird man darüber nur wenn 
man den Server nach den "warnings" fragt...

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.