Max. Quersum. bei Querprod. <K < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Gegeben ist eine Zahl mit 5 (aber eigentlich beliebig vielen) Ziffern. Für welche Zahl wird die Quersumme maximal, wenn das Querprodukt nach oben beschränkt durch eine Konstante K ist? |
Hallo!
Ich habe folgende obenstehende Aufgabe.
Ich habe herausgefunden (durch ein Programm), dass erst die erste Ziffer maximiert wird, dann die zweite, usw., wenn ich die Konstante K erhöht habe.
D.h. bei fester Konstante K = 200 ist z.B.
99211 mit Quersumme 22
das Maximum, bei Konstante K = 1000
99911 mit Quersumme 29.
Nun möchte ich das gern "beweisen" bzw. sinnvoll begründen, bis jetzt ist mir aber noch keine Idee gekommen. Kann mir jemand helfen?
Vielen Dank für eure Mühe,
Stefan.
|
|
| |
|
> Gegeben ist eine Zahl mit 5 (aber eigentlich beliebig
> vielen) Ziffern. Für welche Zahl wird die Quersumme
> maximal, wenn das Querprodukt nach oben beschränkt durch
> eine Konstante K ist?
> D.h. bei fester Konstante K = 200 ist z.B.
>
> 99211 mit Quersumme 22
wie wäre es z.B. mit 99990 ? ---> Quersumme 36
> das Maximum, bei Konstante K = 1000
>
> 99911 mit Quersumme 29.
99099 ---> Quersumme ebenfalls 36
oder sind Nullen etwa verboten ?
|
|
|
| |
|
Hallo!
> oder sind Nullen etwa verboten ?
Ja, habe ich vergessen zu erwähnen: Nullen sind natürlich verboten 
Stefan.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:56 Sa 30.08.2008 | | Autor: | pelzig |
Also versteh ich das richtig, du suchst ne zahl [mm] $z=\sum_{i=0}^4z_i10^i=:z_4z_3z_2z_1z_0$ [/mm] mit [mm] $z_i\in{1,2,...,9}$ [/mm] und dem Querprodukt [mm] $\prod z_i
Dass dein Programm diese Zahlen produziert ist "Zufall", liegt am Algorithmus, außerdem ist nicht mal klar ob das Programm überhaupt funktioniert, d.h. eine Lösung produziert.
Andere Fragestellungen wären vielleicht:
1) Sind die Ziffern einer Lösung bis auf die Reihenfolge eindeutig bestimmt?
2) Gibt es unter den Ziffern einer Lösung höchstens eine, die von 1 und 9 verschieden ist?
beides wage ich zu bezweifeln, denn wenn man das erste deiner Beispiele leicht verändert:
K=217, [mm] z_1=99211 z_2=98311
[/mm]
Haben beide die gleiche Quersumme und 99311 wäre bereits keine Lösung mehr wegen K=217. Falls also die von dir berechneten Lösungen stimmen (das musst erstmal bewiesen werden), wäre damit bereits meine Vermutung 1) und 2) widerlegt.
Vielleicht könnte man es soweit abschwächen dass man sagt: "Es gibt stets eine Lösung für die gilt: höchstens eine der Ziffern ist von 1 und 9 verschieden"...
Trotzdem... Dranbleiben! Und erzähl uns wenn du was interessantes herausgefunden hast
Gruß, Robert
|
|
|
| |
|
Hallo!
Danke Robert für deine Antwort. Da muss ich mich wohl mindestens nochmal präzisieren.
Ich habe eine Zahl, bei welcher die Reihenfolge der n Ziffern keine Rolle spielt. Zu einem gegebenem K möchte ich nun nachweisen, dass für die max. Quersumme von z bei Querprodukt < K für die Zahl z eine Konstellation von Ziffern existiert, bei welcher höchstens eine Ziffer von 1 und 9 verschiedene enthalten ist.
Frage: Ist das einfach nachzuweisen? Mit einfach meine ich einen Beweis, der höchstens eine halbe A4-Seite einnimmt . Wenn jemand darauf eine Antwort kennt, könnte er mir dann Tipps zur Lösung geben?
Was man ja irgendwie zeigen muss, ist dass eine Kombination von vielen Neunen "günstig" ist für die Größe der Quersumme (möglichst hoher "Einfluss") und für die Größe des Querprodukts (möglichst niedriger "Einfluss").
Doch wie kann ich das konkret mit "Formeln" o.ä. nachweisen?
Vielen Dank für Eure Hilfe,
Stefan.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:55 Sa 30.08.2008 | | Autor: | felixf |
Hallo zusammen
> Also versteh ich das richtig, du suchst ne zahl
> [mm]z=\sum_{i=0}^4z_i10^i=:z_4z_3z_2z_1z_0[/mm] mit
> [mm]z_i\in{1,2,...,9}[/mm] und dem Querprodukt [mm]\prod z_i
> die Quersumme [mm]\sum z_i[/mm] maximal wird... ? Ok das kann man
> machen, aber wenn man die Ziffern einer Lösung beliebig
> vertauscht hat man doch wieder eine Lösung, denn am
> Querprodukt und der Quersumme ändert sich nix. Also ist
> deine Behauptung, dass für eine Lösung immer [mm]z_4\ge z_3\ge ... \ge z_0[/mm]
> gilt, natürlich falsch.
Genau, aber man kann es einfach so waehlen, um den Suchraum etwas zu verkleinern, ohne ein richtiges Ergebnis wegfallen zu lassen.
Also. Meine Idee ist wie folgt: man schaut sich nicht fuer ein begrenztes Querprodukt alle Moeglichkeiten an, sondern fuer eine feste Quersumme alle moeglichen Zahlen (die diese ergeben) und sucht unter diesen die mit dem kleinsten Querprodukt.
Dazu beobachtet man, dass man von einer beliebigen Zahl mit fester Quersumme $n$ zu einer anderen belieibgen Zahl mit der gleichen Quersumme gelangen kann, indem man in endlich vielen Schritten jeweils eine Ziffer verringert und dafuer eine andere erhoeht.
Jetzt kann man sich anschauen, wie sich unter dieser Operation (eine Ziffer verkleinern, eine andere erhoehen) das Querprodukt verhaelt. Ohne Einschraenkung wird die erste Ziffer verkleinert und die zweite Vergroessert; das neue Querprodukt ist dann [mm] $(z_1 [/mm] - 1) [mm] (z_2 [/mm] + 1) [mm] \prod_{i=3}^k z_i$ [/mm] (bei $k$ Ziffern), das alte ist [mm] $\prod_{i=1}^k z_i$. [/mm] Der Faktor um den sich das Querprodukt also aendert ist [mm] $\frac{(z_1 - 1) (z_2 + 1)}{z_1 z_2} [/mm] = (1 - [mm] \frac{1}{z_1}) [/mm] (1 + [mm] \frac{1}{z_2})$.
[/mm]
Um das Querprodukt also moeglichst stark zu verkleinern, sollte [mm] $z_1$ [/mm] moeglichst klein sein und [mm] $z_2$ [/mm] moeglichst gross.
Wenn man also eine beliebige $k$-stellige Zahl mit Quersumme $n$ gegeben hat, kann man ihr Querprodukt verkleinern, indem man kleine Ziffern (die nicht schon 1 sind) verkleinert und dafuer eine groessere Ziffer vergroessert. Als Ziel erreicht man immer, das ein Teil der Ziffern 9 ist, ein anderer Teil 1, und eventuell eine andere eine Zahl dazwischen einnimmt (die maximal ist so dass die Quersumme aufgeht unter den anderen beiden Bedingungen).
Insofern: 99211 ist eine richtige Loesung: groesser bekommt man die Quersumme nicht, ohne das Querprodukt ueber $K$ waehlen zu muessen. Es gibt natuerlich moeglicherweise mehrere richtige Loesungen, aber unter allen ist 99211 die mit dem kleinsten Querprodukt (und der Bedingung [mm] $z_1 \ge z_2 \ge \dots \ge z_k$).
[/mm]
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:20 Sa 30.08.2008 | | Autor: | pelzig |
Sehr hübsch...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:28 Sa 30.08.2008 | | Autor: | felixf |
Hallo
Ein Zusatz noch: etwas technische Finesse fehlt noch, man sollte sich naemlich ueberlegen wann der Ausdruck
> [mm]\frac{(z_1 - 1) (z_2 + 1)}{z_1 z_2} = (1 - \frac{1}{z_1}) (1 + \frac{1}{z_2})[/mm].
kleinergleich 1 ist; dies ist genau dann der Fall, wenn [mm] $z_1 [/mm] < [mm] z_2$ [/mm] ist. Jetzt bleibt die Frage, was man tun soll, wenn alle Ziffern den gleichen Wert haben: in dem Fall ist eine Verkleinerung des Querproduktes durch eine solche Aenderung nicht moeglich. Dieser Fall ist allerdings relativ selten und kann vermutlich getrennt behandelt werden: in dem Fall muss $n$ durch $k$ teilbar sein, und das Querprodukt ist [mm] $(n/k)^k$. [/mm] Wenn also das Querprodukt kleinergleich $K$ sein soll, muss $n [mm] \le [/mm] k [mm] \sqrt[k]{K}$ [/mm] sein, und die maximale solche Quersumme ist $k [mm] \lfloor \sqrt[k]{K} \rfloor$. [/mm] Und ob dies groesser der Quersumme von $9...9a1...1$ mit $a [mm] \in \{ 1, \dots, 9 \}$ [/mm] ist kann man leicht ueberpruefen.
LG Felix
|
|
|
| |
|
Hallo und Danke erstmal für den hübschen Lösungsweg!
Ich komme mir zwar grad ein bisschen blöd vor, wenn ich das frage, aber für mich ist es im Moment noch nicht "klar", wie ich dann meine Ausgangsbehauptung folgern kann. Wenn ich jetzt eine Zahl habe, deren feste Quersumme 22 ist, dann weiß ich dass
22
[mm] \textbackslash
[/mm]
[mm] \textbackslash
[/mm]
[mm] \textbackslash
[/mm]
[mm] \textbackslash
[/mm]
162
das kleinste Querprodukt ist, weil ich dann alle Ziffern entsprechend verkleinert und vergrößert habe. Nun ist die Behauptung ja, dass zu diesem (festen) Querprodukt 162 die größte Quersumme 22 ist. Ich weiß, dass das (fast) logisch ist, aber es könnte ja sein dass noch eine Quersumme mit dem Querprodukt existiert?
Stefan.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:22 So 31.08.2008 | | Autor: | felixf |
Hallo
> Ich komme mir zwar grad ein bisschen blöd vor, wenn ich das
> frage, aber für mich ist es im Moment noch nicht "klar",
> wie ich dann meine Ausgangsbehauptung folgern kann. Wenn
> ich jetzt eine Zahl habe, deren feste Quersumme 22 ist,
> dann weiß ich dass
>
> 22
> [mm]\textbackslash[/mm]
> [mm]\textbackslash[/mm]
> [mm]\textbackslash[/mm]
> [mm]\textbackslash[/mm]
> 162
>
> das kleinste Querprodukt ist, weil ich dann alle Ziffern
> entsprechend verkleinert und vergrößert habe. Nun ist die
> Behauptung ja, dass zu diesem (festen) Querprodukt 162 die
> größte Quersumme 22 ist. Ich weiß, dass das (fast) logisch
> ist, aber es könnte ja sein dass noch eine Quersumme mit
> dem Querprodukt existiert?
Die muss dann aber auch von der Form sein, dass sie nur aus 9en und 1en besteht bis hoechstens eine weitere Ziffer, oder das alle Ziffern gleich sind (was hier nicht geht, da 22 nicht durch 5 teilbar ist): wenn nicht, koennte man wieder eine Ziffer erhoehen und eine andere verkleinern und wuerd eine Zahl mit gleicher Quersumme, aber niedrigerem Querprodukt herausbekommen -- was ein Widerspruch dazu waere, dass 162 das kleinstmoegliche Querprodukt zur Quersumme 22 ist.
LG Felix
|
|
|
| |
|
> > Nun ist die
> > Behauptung ja, dass zu diesem (festen) Querprodukt 162 die
> > größte Quersumme 22 ist. Ich weiß, dass das (fast) logisch
> > ist, aber es könnte ja sein dass noch eine Quersumme mit
> > dem Querprodukt existiert?
>
> Die muss dann aber auch von der Form sein, dass sie nur aus
> 9en und 1en besteht bis hoechstens eine weitere Ziffer,
> oder das alle Ziffern gleich sind (was hier nicht geht, da
> 22 nicht durch 5 teilbar ist): wenn nicht, koennte man
> wieder eine Ziffer erhoehen und eine andere verkleinern und
> wuerd eine Zahl mit gleicher Quersumme, aber niedrigerem
> Querprodukt herausbekommen -- was ein Widerspruch dazu
> waere, dass 162 das kleinstmoegliche Querprodukt zur
> Quersumme 22 ist.
>
> LG Felix
Zunächst nochmal vielen Dank für Eure Antworten! Dadurch habe ich schon fast alles verstanden! Nur bei der obigen Frage leuchtet mir deine Erklärung leider noch nicht ganz ein...
Angenommen ich habe eine Zahl aus 5 Ziffern, dann könnte ich mittlerweile zeigen, dass zur Quersumme 22 das kleinste mögliche Querprodukt 162 ist (99211). Nun möchte ich aber zeigen, dass im Umkehrschluss beim begrenzten Produkt 162 als maximale Quersumme 22 entstehen kann.
Ich würde also nach deinem Vorschlag zunächst behaupten, es gäbe eine noch größere Quersumme als 22, z.B. 23. Wieso muss diese Quersumme jetzt notwendigerweise nur aus 9en und 1en und der einen Zahl dazwischen bestehen? Das folgt für mich nicht unmittelbar...
Ich verstehe das Grundprinzip deines Tipps, aber die obige Stelle verstehe ich noch nicht. Kannst du (oder auch jemand anders ) mir nochmal helfen?
Vielen Dank!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:29 Mi 03.09.2008 | | Autor: | felixf |
Hallo
> Zunächst nochmal vielen Dank für Eure Antworten! Dadurch
> habe ich schon fast alles verstanden! Nur bei der obigen
> Frage leuchtet mir deine Erklärung leider noch nicht ganz
> ein...
>
> Angenommen ich habe eine Zahl aus 5 Ziffern, dann könnte
> ich mittlerweile zeigen, dass zur Quersumme 22 das kleinste
> mögliche Querprodukt 162 ist (99211). Nun möchte ich aber
> zeigen, dass im Umkehrschluss beim begrenzten Produkt 162
> als maximale Quersumme 22 entstehen kann.
>
> Ich würde also nach deinem Vorschlag zunächst behaupten, es
> gäbe eine noch größere Quersumme als 22, z.B. 23. Wieso
> muss diese Quersumme jetzt notwendigerweise nur aus 9en und
> 1en und der einen Zahl dazwischen bestehen? Das folgt für
> mich nicht unmittelbar...
Muss sie nicht. Nur wenn du irgendetwas mit Quersumme 23 hast und sagen wir mal Querprodukt $K$, so hat die Zahl mit Quersumme 23 die nur aus 9en, 1en und hoechstens einer Zahl dazwischen besteht, ein Querprodukt von [mm] $\le [/mm] K$. Und wenn das Querprodukt von dieser Zahl schon $> 162$ ist, dann kann $K$ insbesondere nicht kleiner 162 sein.
HTH :)
LG Felix
|
|
|
| |
|
Hallo!
Ich schreib das jetzt mal so auf, wie ich es (leider noch nicht) verstehe:
(Vortext:)
Angenommen ich habe eine Zahl aus 5 Ziffern, dann könnte
ich mittlerweile zeigen, dass zur Quersumme 22 das kleinste
mögliche Querprodukt 162 ist (99211). Nun möchte ich aber
zeigen, dass im Umkehrschluss beim begrenzten Produkt 162
als maximale Quersumme 22 entstehen kann.
Ich nehme also zunächst an, dass es zu dem festen Querprodukt K = 162 noch eine "maximalere" Quersumme, z.B. 23 gibt. Deren niedrigstes Querprodukt wäre dann <= 162 = K, weil sie ja noch nicht in der Form 99.11 vorliegen muss...
Aber das Querprodukt von welcher Zahl ist jetzt schon >162, wie du schreibst? Was genau führt den Widerspruch herbei?
Danke für deine Mühe,
Stefan.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:16 Mi 03.09.2008 | | Autor: | abakus |
> Hallo!
>
> Ich schreib das jetzt mal so auf, wie ich es (leider noch
> nicht) verstehe:
>
> (Vortext:)
> Angenommen ich habe eine Zahl aus 5 Ziffern, dann könnte
> ich mittlerweile zeigen, dass zur Quersumme 22 das kleinste
> mögliche Querprodukt 162 ist (99211). Nun möchte ich aber
> zeigen, dass im Umkehrschluss beim begrenzten Produkt 162
> als maximale Quersumme 22 entstehen kann.
>
> Ich nehme also zunächst an, dass es zu dem festen
> Querprodukt K = 162 noch eine "maximalere" Quersumme, z.B.
> 23 gibt. Deren niedrigstes Querprodukt wäre dann <= 162 =
> K, weil sie ja noch nicht in der Form 99.11 vorliegen
> muss...
>
> Aber das Querprodukt von welcher Zahl ist jetzt schon >162,
> wie du schreibst? Was genau führt den Widerspruch herbei?
>
> Danke für deine Mühe,
>
> Stefan.
Hallo,
ich habe den Thread nur überflogen. Ich möchte nur generell an folgendes erinnern:
Für ein fest vorgegebenes n gilt:
Haben n Ziffern das arithmetische Mittel a und das geometrische Mittel g, so gilt
Quersumme=n*a
Querprodukt [mm] =g^n.
[/mm]
Die Quersumme von n Zahlen ist also minimal/maximal/konstant genau dann wenn auch das arithmetische Mittel dieser Zahlen minimal/maximal/konstant ist.
Das Querprodukt von n Zahlen ist minimal/maximal/konstant genau dann wenn auch das geometrische Mittel dieser Zahlen minimal/maximal/konstant ist.
Das geometrische Mittel von nichtnegativen Zahlen ist immer kleiner oder gleich dem arithmetischen Mittel dieser Zahlen. Die Gleichheit tritt nur ein, wenn alle Zahlen gleich groß sind.
Gruß Abakus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:46 Mi 03.09.2008 | | Autor: | pelzig |
Ich verstehe irgendwie nicht worauf du damit hinaus willst.
Außerdem ist es irgendwie keine Antwort auf Stefans Frage...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:14 Mi 03.09.2008 | | Autor: | pelzig |
> Ich nehme also zunächst an, dass es zu dem festen
> Querprodukt K = 162 noch eine "maximalere" Quersumme, z.B.
> 23 gibt. Deren niedrigstes Querprodukt wäre dann <= 162 =
> K, weil sie ja noch nicht in der Form 99.11 vorliegen
> muss...
Angenommen es gäbe eine 5-stellige Zahl z mit einer Quersumme $QS(z)>22$ und einem Querprodukt [mm] $QP(z)\le162$. [/mm] Laut unserem tollen Satz gibt es [mm] $\hat{z}$ [/mm] mit [mm] $QS(\hat{z})=QS(z), QP(\hat{z})\le QP(z)\le [/mm] 162$, die die Form $99x11$ hat. Da [mm] $QS(\hat{z})=QS(z)>22$ [/mm] ist, folgt $x>2$. Damit ist [mm] $QP(\hat{z})=9*9*x>9*9*2=162$ [/mm] - Widerspruch zu [mm] $QP(\hat{z})\le [/mm] 162$.
Liest sich fast wie ein Krimi 
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:02 So 31.08.2008 | | Autor: | pelzig |
Ich denke eine Kleinigkeit ist hier noch faul, meiner Meinung nach muss man den Fall dass alle Ziffern gleich sind gar nicht gesondert betrachten:
> > [mm]\frac{(z_1 - 1) (z_2 + 1)}{z_1 z_2} = (1 - \frac{1}{z_1}) (1 + \frac{1}{z_2})[/mm].
>
> kleinergleich 1 ist; dies ist genau dann der Fall, wenn [mm]z_1 < z_2[/mm]
Also wenn ich das mal nachrechne:
[mm] $(z_1-1)(z_2+1)\le z_1z_2\gdw z_1z_2+z_1-z_2-1\le z_1z_2 \gdw z_1\le z_2+1$
[/mm]
Insbesondere ist dies auch für [mm] $z_1=z_2$ [/mm] wahr, daher nicht äquivalent zu [mm] $z_1
Und tatsächlich: betrachte Die Zahl 22, Querprodukt 4, aber 31 gleiche Quersumme und niedrigeres Querprodukt.
Daher wird das Querprodukt bei gegebener Quersumme nur dann minimal, wenn höchstens eine Ziffer verschieden von 1 und 9 ist.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:08 So 31.08.2008 | | Autor: | felixf |
Hallo
> Ich denke eine Kleinigkeit ist hier noch faul, meiner
> Meinung nach muss man den Fall dass alle Ziffern gleich
> sind gar nicht gesondert betrachten:
>
> > > [mm]\frac{(z_1 - 1) (z_2 + 1)}{z_1 z_2} = (1 - \frac{1}{z_1}) (1 + \frac{1}{z_2})[/mm].
>
> >
> > kleinergleich 1 ist; dies ist genau dann der Fall, wenn [mm]z_1 < z_2[/mm]
>
> Also wenn ich das mal nachrechne:
> [mm](z_1-1)(z_2+1)\le z_1z_2\gdw z_1z_2+z_1-z_2-1\le z_1z_2 \gdw z_1\le z_2+1[/mm]
Genau das hatte ich auch.
> Insbesondere ist dies auch für [mm]z_1=z_2[/mm] wahr, daher nicht
> äquivalent zu [mm]z_1
Aeh ja stimmt. Irgendwie hatte ich das uebersetzt zu [mm] $z_1 [/mm] < [mm] z_2$, [/mm] aber es ist ja eher [mm] $z_1 [/mm] < [mm] z_2 [/mm] + 2$...
Da war ich wohl noch nicht bzw. nicht mehr ganz wach
Sinn macht das allerdings auch: wenn [mm] $z_1 [/mm] = [mm] z_2 [/mm] + 1$ ist und man [mm] $z_1$ [/mm] verkleinert und [mm] $z_2$ [/mm] vergroessert, vertauscht man ja im Endeffekt die beiden Ziffern. Das aendert ja weder Quersumme noch Querprodukt, sollte also problemlos moeglich sein.
Danke fuer den Hinweis!
LG Felix
|
|
|
|
