| |
| Autor |
 Rest einer Summe |
|
Ehemaliges_Mitglied
 |  Themenstart: 2022-07-06
|
Hallo,
ich habe zu folgender Aufgabe eine FRage:
Auf einer Tafel stehen die Zahlen 1, 2, ..., 2012. Jede Minute geht ein Schüler zur Tafel, wählt zwei Zahlen x und y, löscht sie und schreibt die Zahl 2x + 2y an die Tafel. Dies wird fortgesetzt, bis nur noch eine Zahl N übrig bleibt.
Finden Sie den Rest, wenn der maximal mögliche Wert von N durch 1000 geteilt wird (OMU2012).
Ich habe als Beispiel mal die FOlge 1, 2, 3,4, 5 betrachtet.
Man muss immer die zwei größten Zahlen streichen, damit N möglichst groß wird.
1 2 3 4 5 -> 1 2 3 18
1 2 3 18 -> 1 2 42
1 2 42 -> 1 88
1 88 -> 178
Für die SUmmen habe ich gerechnet:
(5+4)*2 = 18
(18+3)*2 = ((5+4)*2+3)*2)=42
(42+2)*2 = (((5+4)*2+3)*2)+2)*2)=88
(88+1)*2= ((((5+4)*2+3)*2)+2)*2)+1)*2=178
Dann hätte ich für N die SUmme:
5*2^(5-1)+4*2^(5-1)+3*2^(5-2)+2*2^(5-3)+1*2^(5-4)=178
Ist meine überlegugn für die FOlge 1, 2, ..., 2012 dann so richtig:
N=2012*2^(2012-1)+2011*2^(2012-1)+2010*2^(2012-2)+...+1*2^(2012-2011)
??
Wie kann man zeigen, dass diese Formel dann für die Zahlen bis 2012 richtig wäre (falls meine Gedanken richtig waren)?
Wie kann ich die Summe dann berechnen? Die gauß-Formel kenne ich. Und die Summe hätte ich so mit dem Summenzeichen geschrieben:
N=2012*2^2011+sum(i*2^i,i=1,2011)=??
Im Summensymbol kommt i in beiden Faktoren vor. Hier kenne ich noch keine Formel.
Würde mich sehr über eine Hilfe freuen. DAnke!!!
|
 Profil
|
tactac
Senior 
Dabei seit: 15.10.2014
Mitteilungen: 2870
 | Beitrag No.1, eingetragen 2022-07-06
|
Es bietet sich häufig an, OEIS zu benutzen, wenn man etwas über Zahlenfolgen wissen will.
Hier liefert diese Suche eine Formel a(n) für die Summen, bei denen der Index bis n läuft. (Und die Summe hier ist a(2011).)
|
Profil
|
Ehemaliges_Mitglied
| Beitrag No.2, vom Themenstarter, eingetragen 2022-07-07
|
Dass es so eine Suche nach Folgen gibt, wusste ich bis jetzt noch nicht.
Wie kann man die Summenformel beweisen?
Und ist mein Term für N richtig?
Von N muss ich dann nur noch den rest bei der Division durch 1000 feststellen.
|
Profil
|
tactac
Senior
Dabei seit: 15.10.2014
Mitteilungen: 2870
| Beitrag No.3, eingetragen 2022-07-07
|
\quoteon(2022-07-07 07:10 - sebast2004 in Beitrag No. 2)
Dass es so eine Suche nach Folgen gibt, wusste ich bis jetzt noch nicht.
Wie kann man die Summenformel beweisen?
\quoteoff
Das naheliegendste ist Induktion.
\quoteon
Und ist mein Term für N richtig?
\quoteoff
Scheint so.
\quoteon
Von N muss ich dann nur noch den rest bei der Division durch 1000 feststellen.
\quoteoff
Jop.
|
Profil
|
Ehemaliges_Mitglied
| Beitrag No.4, vom Themenstarter, eingetragen 2022-07-07
|
Danke.
Induktion habe ich:
n=1: …
n nach n+1:
sum(i*2^i,i=1,n+1)= sum(i*2^i, i=1, n) + (n+1)*2^(n+1)= 2+2^(n-1)+(n+1)*2^(n+1)= usw. =2+2^(n+2)*n
Ich komme dann für meinen obigen Term auf N=2^2016.
Wegen dem Rest komme ich nur mit vielen Zwischenschritten aufbringen Ergebnis. Ist das richtig und gibt es einen „schnelleren“ Weg?
2^2016 == (2^30)^60 *2^216 == (824)^60*(2^20)^10*2^16 ==( (824)^3)^20*(576)^10*576==(224)^20*(576^2)^5*536==(224^2)^10*(776)^5*536==(176)^10*(776)^2*(776)^2*776*536==(176)^4*(176)^4*(176)^2*176*176*776*536==(176)^4*(176)^4*(176)^4*776*536==576*576*576*776*536==(576)^2*576*776*536==776*576*776*536==(776)^2*576*536==176*576*536== 536 Modulo 1000
Vielen Dank
|
Profil
|
Wauzi
Senior
Dabei seit: 03.06.2004
Mitteilungen: 11655
Wohnort: Bayern
 | Beitrag No.5, eingetragen 2022-07-07
|
Hallo,
S(N)=sum(i*2^i,i=0,N)=sum((i-1)*2^(i-1),i=1,N+1) | | Indexverschiebung
=sum(i*2^(i-1),i=1,N+1)-sum(2^(i-1),i=1,N+1)=
=1/2*sum(i*2^i,i=1,N+1)-sum(2^i,i=0,N)=
=1/2*sum(i*2^i,i=0,N+1)-sum(2^i,i=0,N)= \ Summand mit i=0 dazu, ändert nichts
=1/2*sum(i*2^i,i=0,N)+1/2*(N+1)*2^(N+1)-sum(2^i,i=0,N)=
=1/2*S(N)+1/2*(N+1)*2^(N+1)-sum(2^i,i=0,N)
Die rechte Summe ist die bekannte geometrische Summe.
Auflösen der Gleichung nach S(N) bringt die gesuchte Formel
Dies geht mit anderen Methoden einfacher, aber nicht so elementar.
Gruß Wauzi
|
Profil
|
Kuestenkind
Senior 
Dabei seit: 12.04.2016
Mitteilungen: 2583
| Beitrag No.6, eingetragen 2022-07-07
|
Huhu sebast2004,
\quoteon(2022-07-07 11:52 - sebast2004 in Beitrag No. 4)
Ist das richtig und gibt es einen „schnelleren“ Weg?
\quoteoff
das liegt ja auch etwas an deinem Kenntnisstand. Kennst du z. B. den chinesischen Restsatz und die Eulersche Phi-Funktion? Es ist offensichtlich \(2^{2016}\equiv 0 \pmod{8}\) und mit \(\phi(125)=\phi(5^3)=5^2(5-1)=100\) folgt dann \(2^{100}\equiv 1\pmod{125}\) und somit \(2^{2016}\equiv 2^{16}=2^7\cdot 2^7\cdot 2^2 \equiv 3\cdot 3\cdot 4 \equiv 36\pmod{125}\). Es gilt dann also ein \(x\) zu finden, für das \(36+125x\equiv 0\pmod{8}\) ist. Nun ist \(36+125x\equiv 4+5x\) und somit tut es \(x=4\). Setzen wir es ein erhalten wir \(36+125\cdot 4=536\). Dein Ergebnis scheint also zu stimmen.
Gruß,
Küstenkind
|
Profil
|
Ehemaliges_Mitglied
| Beitrag No.7, vom Themenstarter, eingetragen 2022-07-07
|
Hallo Wautzi,
deine Herleitung für die Formel zur Berechnung der SUmme habe ich nicht verstanden.
Auch die geometrische Summe sehe ich nicht.
Ich kenne nur:
sum(q^k,k=0,\inf)=1/(1-q)
und die Formel von Gauß sowie für Quadrat- und Kubikzahlen.
|
Profil
| Folgende Antworten hat der Fragensteller vermutlich noch nicht gesehen.
Er/sie war noch nicht wieder auf dem Matheplaneten |
Wauzi
Senior 
Dabei seit: 03.06.2004
Mitteilungen: 11655
Wohnort: Bayern
| Beitrag No.8, eingetragen 2022-07-07
|
Hallo,
die endliche Summe ergibt sich so:
sum(q^k,k=0,N)=sum(q^k,k=0,\inf )-sum(q^k,k=N+1,\inf )=
=1/(1-q)-q^(N+1)*sum(q^k,k=0,\inf )=
=1/(1-q)-q^(N+1)*1/(1-q)=(1-q^(N+1))/(1-q)
Die anderen Probleme müßtest Du konkretisieren.
Gruß Wauzi
|
Profil
|
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
