Eine schöne Denkaufgabe < Wettbewerbe < Schule < Mathe < Vorhilfe
|
| Status: |
(Übungsaufgabe) Übungsaufgabe  | | Datum: | 17:49 Do 22.07.2004 | | Autor: | Hanno |
Hiho.
Ich habe grad ein wenig auf den Wettbewerbsseiten rumgeschnüffelt und habe aus der 40. Mathematik-Olympiade, der dritten ( also Landesebene ) Runde für 11-13-Klässler eine Aufgabe herausgesucht, sie fast gelöst, finde sie aber so schön, dass ich sie hier gerne zeigen will:
Eine ganze Zahl "z" wird "kuhl" genannt, wenn sie sich als Summe von Potenzen mit nichtnegativen Exponenten der Zahl (-2) schreiben lässt, wobei jeder Exponent nur 1 mal vorkommen darf.
Man beweise nun, dass jede ganze Zahl außer der Null kuhl ist.
Viel Spaß!
Gruß,
Hanno
Ich habe diese Frage in keinem weiteren Forum gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:49 Do 22.07.2004 | | Autor: | SirJective |
Hallo Hanno,
ich werde diese Aufgabe jetzt nicht lösen, da ich durch mein Studium in engen Kontakt mit Problemstellungen dieser Art gekommen bin.
Ich bemerke aber zu dieser Aufgabe, dass dieselbe Aussage gilt, wenn man (-2) durch (-n) ersetzt für eine beliebige natürliche Zahl n >= 2, und zusätzlich die Vorfaktoren 0, 1, ..., n-1 für jeden Summanden zulässt. (Für n=2 heißt das also, dass die Vorfaktoren nur 0 und 1 sind, und weggelassen werden.)
Übrigens sind 24h ein ziemlich knapper Rahmen für eine Online-Wettbewerbsaufgabe, findest du nicht?
Gruss,
SirJective
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:18 Fr 23.07.2004 | | Autor: | Stefan |
Lieber Christian, lieber Hanno!
> Ich bemerke aber zu dieser Aufgabe, dass dieselbe Aussage
> gilt, wenn man (-2) durch (-n) ersetzt für eine beliebige
> natürliche Zahl n >= 2, und zusätzlich die Vorfaktoren 0,
> 1, ..., n-1 für jeden Summanden zulässt. (Für n=2 heißt das
> also, dass die Vorfaktoren nur 0 und 1 sind, und
> weggelassen werden.)
Aha, so eine Art $g$-adische Darstellung mit negativem $g$. Kannst du das vielleicht nicht doch bitte mal beweisen oder einen Link auf eine dementsprechende Aussage (mit Beweis) setzen? Das interessiert mich jetzt. 
Wie hast du die Aufgabe denn gelöst, Hanno? Ich hatte zwar sofort eine Lösung, aber die ist unschön und gefällt mir nicht.
Liebe Grüße
Stefan
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:22 Fr 23.07.2004 | | Autor: | Hanno |
Hi Stefan.
Ich hatte nicht sofort eine Lösung, ich habe ungefähr 15-20 Minuten Testzahlen "gekuhlt", bis ich das Verfahren raus hatte. Im Anschluss daran brauchte ich noch lange, um es halbwegs verständlich auszuformulieren.
Du kannst es dir auf
http://www.hanno-becker.de/Guhle_Zahlen.pdf
ansehen, auf der letzten Seite. Tut mir leid, dass da noch so viele andere Sachen sind und dass da grammatikalisch einiges nicht ganz ok ist, aber ich schreibe nunmal alles auf, was mir grad in den Kopf kommt, und das muss nicht perfekt sein, es muss einfach irgendwo festgehalten sein 
Und gerade dieses Problem ist verbal wirklich halsbrecherisch ( für mich war es das )
Gruß,
Hanno
|
|
|
| |
|
Hallo Stefan,
> Aha, so eine Art [mm]g[/mm]-adische Darstellung mit negativem [mm]g[/mm].
> Kannst du das vielleicht nicht doch bitte mal beweisen oder
> einen Link auf eine dementsprechende Aussage (mit Beweis)
> setzen? Das interessiert mich jetzt.
Der folgende Beweis basiert auf einer Idee von Irrlicht, die formal einfacher ist als meine (meine Idee benutzt die g-adische Darstellung, und wandelt diese schrittweise in eine (-g)-adische um).
Sei also unsere Basis g eine natuerliche Zahl, g>=2, und z eine ganze Zahl.
Wir beweisen mit Induktion ueber den Betrag von z:
Jede ganze Zahl z laesst sich darstellen als Summe der Form $z = [mm] \sum_{i=0}^n a_i (-g)^i$ [/mm] mit einer natuerlichen Zahl n (incl. 0) und ganzen Zahlen [mm] $0\leq a_i \leq [/mm] g-1$.
Ist z=0, dann ist ihre (-g)-adische Darstellung wahlweise [mm] $z=0\cdot (-g)^0$ [/mm] oder die leere Summe.
Ist $z [mm] \neq [/mm] 0$, dann teilen wir z mit Rest duch (-g), und erhalten eine Darstellung $z = y(-g) + r$ mit einem Rest [mm] $0\leq [/mm] r<g$ und einer ganzen Zahl y, deren Betrag kleiner ist als der von z. Aus der Darstellung $y = [mm] \sum_{i=0}^n a_i (-g)^i$ [/mm] erhalten wir die Darstellung $z = [mm] \sum_{i=0}^n a_i (-g)^{i+1} [/mm] + r [mm] (-g)^0$.
[/mm]
Dieser Beweis entspricht im wesentlichen dem Verfahren, die g-adische Darstellung einer vorgegebenen ganzen oder natuerlichen Zahl durch fortgesetzte Division mit Rest zu bestimmen. Das einzige technische Problem bei einer Umsetzung ist, dass der Rest zwischen 0 und g-1 liegen muss (was bei den modulo-Befehlen vieler Programmiersprachen nicht gewaehrleistet ist).
Gruss,
SirJective
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:16 Fr 23.07.2004 | | Autor: | Hanno |
Hi.
Ich habe mich wohl nicht klar ausgedrückt :-(
Jeder Exponent darf nur ein Mal vorkommen, d.h. Potenzen dürfen weder summiert noch multipliziert werden. Dies tut ihr aber meines Erachtens bei eurem Beweis mit [mm]a_i[/mm], auch wenn ich ihn noch nicht verstanden habe.
Gruß,
Hanno
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:56 Fr 23.07.2004 | | Autor: | Stefan |
Lieber Hanno!
Ich antworte mal lieber schnell, bevor sich hier jemand angegriffen fühlt.
Nein, der Beweis ist völlig in Ordnung. Jede Potenz kommt doch nur genau einmal vor, bei der Darstellung von $z$ am Schluss.
Es ist ja nicht verboten, dass man während des Beweises, also bei der Herleitung der Darstellung, Potenzen multipliziert und so weiter. Es ist ja nur ein induktiver Existenzbeweis. Wenn du eine Konstruktion und keinen Existenzbeweis haben möchtest, kannst du dir den Beweis aber auch zu Hilfe nehmen. Führe eine Division (durch $-2$) mit Rest durch. Dann machst du das Gleiche wieder mit dem entstehenden Quotienten usw. Wenn du dann (am Schluss oder zwischendurch) die Potenzen zusammenfasst, kommst du auf das Ergebnis.
Beispiel:
$101$
$= (-50) [mm] \cdot [/mm] (-2) + 1$
$ = 25 [mm] \cdot [/mm] (-2) [mm] \cdot [/mm] (-2) + 1$
$= 25 [mm] \cdot (-2)^2 [/mm] + 1$
$= ((-12) [mm] \cdot [/mm] (-2) + 1) [mm] \cdot (-2)^2 [/mm] + 1$
$= (-12) [mm] \cdot (-2)^3 [/mm] + [mm] (-2)^2 [/mm] + 1$
$= 6 [mm] \cdot (-2)^{4} [/mm] + [mm] (-2)^2 [/mm] + 1$
$= (-3) [mm] \cdot (-2)^5 [/mm] + [mm] (-2)^2 [/mm] + 1$
$= ((2 [mm] \cdot [/mm] (-2) + 1) [mm] \cdot (-2)^5 [/mm] + [mm] (-2)^2 [/mm] + 1$
$= 2 [mm] \cdot (-2)^6 [/mm] + [mm] (-2)^5 [/mm] + [mm] (-2)^2 [/mm] + 1$
$= (-1) [mm] \cdot (-2)^7 [/mm] + [mm] (-2)^5 [/mm] + [mm] (-2)^2 [/mm] + 1$
$= (1 [mm] \cdot [/mm] (-2) + 1) [mm] \cdot (-2)^7 [/mm] + [mm] (-2)^5 [/mm] + [mm] (-2)^2 [/mm] + 1$
$= [mm] (-2)^8 [/mm] + [mm] (-2)^7 [/mm] + [mm] (-2)^5 [/mm] + [mm] (-2)^2 [/mm] + 1$
[mm] $=(-2)^8 [/mm] + [mm] (-2)^7 [/mm] + [mm] (-2)^5 [/mm] + [mm] (-2)^2 [/mm] + [mm] (-2)^0$.
[/mm]
Probe:
[mm] $(-2)^8 [/mm] + [mm] (-2)^7 [/mm] + [mm] (-2)^5 [/mm] + [mm] (-2)^2 [/mm] + [mm] (-2)^0 [/mm] = 256 - 128 - 32 + 4 + 1 = 101$.
Ist es jetzt klarer, was die beiden gemacht haben?
Probiere das Verfahren doch mal mit anderen Zahlen aus...
Frage demnächst vielleicht lieber erst mal bei mir per PN nach, bevor du meinst bei SirJective einen Fehler gefunden zu haben. Er macht nämlich eigentlich nie Fehler (im Gegensatz zu mir ) und ist dann (auch im Hinblick auf eure gemeinsame Vergangenheit) vielleicht nicht so glücklich, wenn du ihn irrtümlich auf vermeintliche Fehler hinweist. Normalerweise ist das bei uns kein Problem nachzufragen und auf Fehler hinzuweisen (und du weißt, dass ich da immer sehr froh darüber bin, wenn bei mir jemand nachfragt und vielleicht Fehler sieht und es ist auch nicht schlimm, wenn es dann doch kein Fehler, sonder ein Irrtum des Hinweisenden oder Nachfragenden war), aber es gibt Konstellationen, da ist man lieber vorsichtig. Ist nicht böse gemeint, soll nur ein Rat sein. Also demnächst, um Unruhe zu vermeiden, kannst du gerne erst mich fragen.
Liebe Grüße
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:12 Fr 23.07.2004 | | Autor: | Marc |
Hallo zusammen,
ich beteilige mich auch mal!
> Ich antworte mal lieber schnell, bevor sich hier jemand
> angegriffen fühlt.
?
> Frage demnächst vielleicht lieber erst mal bei mir per PN
> nach, bevor du meinst bei SirJective einen Fehler gefunden
> zu haben. Er macht nämlich eigentlich nie Fehler (im
> Gegensatz zu mir ) und ist dann (auch im Hinblick auf
> eure gemeinsame Vergangenheit) vielleicht nicht so
> glücklich, wenn du ihn irrtümlich auf vermeintliche Fehler
> hinweist. Normalerweise ist das bei uns kein Problem
> nachzufragen und auf Fehler hinzuweisen (und du weißt, dass
> ich da immer sehr froh darüber bin, wenn bei mir jemand
> nachfragt und vielleicht Fehler sieht und es ist auch nicht
> schlimm, wenn es dann doch kein Fehler, sonder ein Irrtum
> des Hinweisenden oder Nachfragenden war), aber es gibt
> Konstellationen, da ist man lieber vorsichtig. Ist nicht
> böse gemeint, soll nur ein Rat sein. Also demnächst, um
> Unruhe zu vermeiden, kannst du gerne erst mich fragen.
>
Ich sehe nicht, dass sich jemand angegriffen fühlen könnte, weswegen ich diesen Abschnitt auch nicht verstehe.
Was ich aber eigentlich beisteuern wollte, ist, dass SirJectives Vorfaktoren [mm] $a_i$ [/mm] ja zwischen 0 und g-1 liegen, für g=2 also entweder [mm] $a_i\in\{0,1\}$, [/mm] woraus sich doch ergibt (siehe auch SirJectives erstes Posting), dass jeder Exponent höchstens einmal in der Summe vorkommt. Oder meintest du etwas anderes, Hanno?
Das waren meine 0.2 Cent.
Viele Grüße,
Marc
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:18 Fr 23.07.2004 | | Autor: | Stefan |
Lieber Marc!
> Ich sehe nicht, dass sich jemand angegriffen fühlen könnte,
> weswegen ich diesen Abschnitt auch nicht verstehe.
Lass mich mal machen , das hat schon seinen Sinn, glaube mir.
Liebe Grüße
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:32 Fr 23.07.2004 | | Autor: | Hanno |
Hi Stefan.
Ist ok, machen wir so ab jetzt.
Hast du lust auf eine Aufgabe?
Gruß,
Hanno
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:00 Fr 23.07.2004 | | Autor: | Hanno |
Hi Stefan.
Ok, ich sitze hier nämlich schon 30 Minuten und komme kein Stück voran, obwohl ich glaube, dass der "Trick" ( wenn es übehraupt einer ist ) ziemlich simpel ist.
Es handelt sich um die Aufgabe 211322 der Mathematikolympiade ( 41. Runde 3 Klasse 11-13 ):
Man bestimme alle reellen Zahlen [mm]x_1,x_2,...,x_{2001}[/mm], die die Gleichung [mm]x_1^2+(x_2-x_1)^2+(x_3-x_2)^2+...+(1-x_{2001})^2=\frac{1}{2002}[/mm]
erfüllen.
Ich bin noch nicht weit. Ich glaube, dass es nur ein Lösung gibt ( [mm]x_n=\frac{n}{2002}[/mm], doch kriege ich den Beweis dafür nicht hin.
Vielleicht kannst mir ja ein paar Tips geben.
Gruß
Hanno
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:44 Fr 23.07.2004 | | Autor: | Stefan |
Lieber Hanno!
Für jede Lösung gilt (beachte: [mm] $x_0=0$ [/mm] und [mm] $x_{2002}=1$) [/mm] :
[mm] $\sum\limits_{i=0}^{2001} (x_{i+1} [/mm] - [mm] x_i)^2 [/mm] = [mm] \sum\limits_{i=0}^{2001} \left( \frac{1}{2002} + \varepsilon_i \right)^2$
[/mm]
mit noch zu bestimmen [mm] $\varepsilon_i$, [/mm] die die Normierungsbedingung
[mm] $\sum\limits_{i=0}^{2001} \varepsilon_i [/mm] = 0$
erfüllen
(denn [mm] $\sum\limits_{i=0}^{2001} (x_{i+1} [/mm] - [mm] x_i) [/mm] = 1 - 0 = 1$ (Teleskopsumme)
und daher $1 = [mm] \sum\limits_{i=0}^{2001} (\frac{1}{2002} [/mm] + [mm] \varepsilon_i) [/mm] = 1 + [mm] \sum\limits_{i=0}^{2001} \varepsilon_i$).
[/mm]
Daraus folgt:
[mm] $\sum\limits_{i=0}^{2001} (x_{i+1} [/mm] - [mm] x_i)^2$
[/mm]
$= [mm] \sum\limits_{i=0}^{2001} \left( \frac{1}{2002} + \varepsilon_i \right)^2$
[/mm]
$= [mm] \frac{1}{2002} [/mm] + [mm] \frac{2}{2002} \sum\limits_{i=0}^{2001} \varepsilon_i [/mm] + [mm] \sum\limits_{i=0}^{2001} \varepsilon_i^2$.
[/mm]
$= [mm] \frac{1}{2002} [/mm] + [mm] \sum\limits_{i=0}^{2001} \varepsilon_i^2$.
[/mm]
Daraus folgt:
[mm] $\varepsilon_i [/mm] = 0$ für alle [mm] $i=0,1,\ldots,2001$.
[/mm]
Fertig! ![[sunny]](/images/smileys/sunny.gif "[sunny]")
Liebe Grüße
Stefan
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:55 Fr 23.07.2004 | | Autor: | Hanno |
Hi Stefan.
Wunderbar, schön gelöst. Ich habs mir mal wieder zu kompliziert gemacht mit Erweitern und PiPaPo, schrecklich. Und du führst einfach eine Konstante ein
Klasse, hoffentlich lern ich draus!
Gruß und Dank
Hanno
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:44 Fr 23.07.2004 | | Autor: | Hanno |
Hi Stefan :)
Du scheinst ja wirklcih viel von mir zu erwarten )
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:59 Fr 23.07.2004 | | Autor: | Stefan |
Lieber Hanno!
Naja, die Tatsache mathematisch besser zu werden als ich, ist eine so hohe Erwartung nun auch wieder nicht. Da solltest du dir auf jeden Fall höhere Ziele setzen, sonst erreichst du nicht notwendig viel. Ja, klar, ich glaube ganz fest daran, dass du mathematisch sehr gut werden kannst. Das habe ich schon immer getan, und ich habe da ein ganz gutes Gespür für, durch meine Arbeit mit begabten Jugendlichen.
Und so viele gute Nachwuchsmathematiker haben wir hier zur Zeit nicht im Matheraum. Ein paar zum Glück schon (diejenigen wissen, wer gemeint ist, ich habe das im Blick ), und die muss man fördern. Aber uns geht es wie der französischen Nationalmannschaft (uiih, wie vermessen, so gut waren wir natürlich nie ): die glorreiche Zeit haben wir zum Großteil bereits hinter uns. Man wird alt, Körper und Geist werden müde, man muss noch mehr trainieren als früher um das Niveau zu halten. Es wird Zeit ein neues U18-Team aufzubauen. Und im Moment bist du der Spielmacher und Kapitän dieser Nachwuchsmannschaft. Das heißt noch nicht, dass du auch im Erwachsenenbereich zur Spitze zählst, aber das Talent hast du (auch wenn das nicht alle so sehen, ich aber schon).
Liebe Grüße
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:02 Fr 23.07.2004 | | Autor: | Hanno |
Hi Stefan.
Bin ich der Matheraum-Mannschafts-Kapitän?
Evt. dies, aber bedenke, dass es duzende, wenn nicht hunderte bessere Schüler gibt als ich, die seit sie 11 sind beiden Wettbewerben mitmachen. Die sind dann doch deutlich besser als ich - besser => kreativer,wissen mehr,intelligenter.
Dennoch freut es mich, dass du mich so einschätzt :)
Gruß
Hanno
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:10 Fr 23.07.2004 | | Autor: | Stefan |
Lieber Hanno!
> Bin ich der Matheraum-Mannschafts-Kapitän?
Nein, das ist Marc. Aber der Kapitän der Nachwuchsmannschaft!
> Evt. dies, aber bedenke, dass es duzende, wenn nicht
> hunderte bessere Schüler gibt als ich, die seit sie 11 sind
> beiden Wettbewerben mitmachen. Die sind dann doch deutlich
> besser als ich - besser => kreativer,wissen
> mehr,intelligenter.
Es gibt sicherlich einige, die besser sind, klar. Ich kenne zum Beispiel jemanden, der mit 17 angefangen hat zu studieren (Grundstudium übersprungen), mit 20 seine Diplomarbeit abgegeben hat und mit 23 promoviert war. Also zur absoluten Spitze zählst du nicht. Aber so viele zählen nun auch wieder nicht zu dieser höchsten Kategorie. Ich meine, du bist gerade mal 16 geworden und hantierst hier mit Dingen locker rum, die man im Studium erst lernt. Das ist schon beachtlich. Allerdings musst du noch exakter argumentieren und die Dinge mehr auf den Punkt bringen. Aber das kriegen wir schon noch hin. Ich hoffe mein Lob führt nicht dazu, dass du völlig abhebst. Dann wäre es kontraproduktiv gewesen. Aber eigentlich glaube ich das nicht.
Liebe Grüße
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:31 Fr 23.07.2004 | | Autor: | Hanno |
Hi marc.
Danke, hast recht, habe nicht aufmerksam gelesen.
Gruß,
Hanno
|
|
|
|
![[applaus]](/images/smileys/applaus.gif "[applaus]"){kind=small}
