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
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.
>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.
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
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.
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.
>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.
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.
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...
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? ;-)
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.
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
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 ;)
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.
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.
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
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
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
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
> 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?
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
> 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 :-)
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. ;-)
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
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.
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...