Rechenaufgabe: 500 Euro

[Martin Dunst]

Hallo,

Ich hab wieder eine kleine Rechenaufgabe auf meine private Website gestellt.
Wer mag: Die Aufgabe dreht sich um 500 Euro.
Bin gespannt, wer diesmal der/die Erste ist!

lg
Martin Dunst

[Vinzenz Mai]

Hallo Martin,

Ich hab wieder eine kleine Rechenaufgabe auf meine private Website gestellt.
Wer mag: Die Aufgabe dreht sich um 500 Euro.

nettes Rätsel (für Leute mit Programmiererfahrung sehr einfach).
Es gibt allerdings mehrere richtige Lösungen.

Freundliche Grüße

Vinzenz

[Vinzenz Mai]

Hallo Ingrid,

Es gibt allerdings mehrere richtige Lösungen.

die vier von mir getesteten und unterschiedlichen Lösungen wurden auch alle
akzeptiert :-)

Freundliche Grüße

Vinzenz

[Matze]

Hallo,

die vier von mir getesteten und unterschiedlichen Lösungen wurden auch alle
akzeptiert :-)

Cheater^^ *SCNR

Grüße, Matze

[Vinzenz Mai]

Hallo Matze,

die vier von mir getesteten und unterschiedlichen Lösungen wurden auch alle
akzeptiert :-)

gib doch mal eine Schätzung ab, wieviele richtige Lösungen es gibt:

[ ] weniger als 1 Million
[ ] mehr als 1 Million

Freundliche Grüße

Vinzenz

[Matze]

Hallo,

gib doch mal eine Schätzung ab, wieviele richtige Lösungen es gibt:

[ ] weniger als 1 Million
[ ] mehr als 1 Million

schätzen? Ts ts, also entweder man kennt die Antwort oder nicht.
Schätzen in Mathe geht ja gar nicht ;)

Nee nee, ich bin nicht sehr gut in solchen Rätseln, daher versuch ichs gar nicht erst^^
Die Formel dafür ist aber bestimmt gaaaanz einfach hehe...

Grüße, Matze

[Vinzenz Mai]

Hallo Matze,

schätzen? Ts ts, also entweder man kennt die Antwort oder nicht.
Schätzen in Mathe geht ja gar nicht ;)

selbstverständlich geht das. Und wird auch gern genutzt.

Nee nee, ich bin nicht sehr gut in solchen Rätseln, daher versuch ichs gar nicht erst^^
Die Formel dafür ist aber bestimmt gaaaanz einfach hehe...

die für die Gesamtzahl ist nicht ganz einfach, die für meine Abschätzung schon:
Ich weiß, dass es deutlich mehr als 417312000 Lösungen gibt, das ist 115•10!

Freundliche Grüße

Vinzenz

[Matze]

Hallo,

selbstverständlich geht das. Und wird auch gern genutzt.

mach das mal an der Supermarktkasse^^

Ich weiß, dass es deutlich mehr als 417312000 Lösungen gibt, das ist 115•10!

Und wie kommst du auf die 115? Geschätzt? Nach welcher Grundlage?
Die 10 kommt sicher von den 10 Säcken oder?

Grüße, Matze

[Vinzenz Mai]

Hallo

Ich weiß, dass es deutlich mehr als 417312000 Lösungen gibt, das ist 115•10!

Und wie kommst du auf die 115? Geschätzt? Nach welcher Grundlage?

ich kenne 115 Möglichkeiten mit 10 verschiedenen Zahlen und 7 mit neun verschiedenen Zahlen, ich habe mir aber keine Gedanken gemacht, ob das alle
Lösungen sind :-)

Die 10 kommt sicher von den 10 Säcken oder?

Eben, da die Säcke numeriert sind, gibt es für einen Satz mit 10 verschiedenen
Zahlen 10! verschiedene Möglichkeiten, diesen einen Satz auf die Säcke zu
verteilen, die 7 mir bekannten Fälle mit 9 verschiedenen Zahlen habe ich für
meine Schätzung einfach vernachlässigt.

Mir bisher noch unbekannte Lösungen habe ich ebenfalls vernachlässigt, aber
meine Untergrenze gilt.

Freundliche Grüße

Vinzenz

[Matze]

Hallo,

hm... ich hätte doch Abi machen sollen ^^
Das ist mir zu hoch.

Grüße, Matze

[Vinzenz Mai]

Hallo Matze,

hm... ich hätte doch Abi machen sollen ^^

dafür ist es nie zu spät. Es gibt Abendschulen.

Das ist mir zu hoch.

wir fangen einfach klein an, mit einer Zahl und einem Sack:

Zahl: 1
Sack: 1

Nun kannst Du auf genau eine Art Deine Zahl verteilen.

Nächste Stufe: zwei Zahlen (1, 2) und zwei Säcke

Jetzt hast Du zwei Möglichkeiten, das ist 1 * 2:

1 2
2 1

3. Stufe: drei Zahlen (1, 2, 3) und drei Säcke

1 2 3  - 3 an letzter Position eingefügt
2 1 3
1 3 2  - 3 an zweiter Position eingefügt
2 3 1
3 1 2  - 3 an erster Position eingefügt
3 2 1

Du hast also drei mal soviele Möglichkeiten wie bei zwei Säcken: 1 * 2 * 3

4. Stufe

Nimm die Möglichkeiten aus der dritten Stufe und füge die 4
 - an erster
 - an zweiter
 - an dritter
 - an vierter
Position ein.
Siehst Du, dass es jetzt viermal soviele Möglichkeiten gibt, wie bei drei Zahlen? Also 1 * 2 * 3 * 4

Analog werden es bei 5 Zahlen 5 mal soviele sein wie bei 4 Zahlen,
... und bei 10 Zahlen 10 mal soviele wie bei 9, das heisst bei x Zahlen

1 * 2 * 3 * 4 * ... * x = x!

Die Funktion, die diesen Wert hat, ist die Fakultätsfunktion, diese wird
mit einem Ausrufezeichen gekennzeichnet. Sie wächst verd^w sehr schnell.

Freundliche Grüße

Vinzenz

[Matze]

Hallo,

dafür ist es nie zu spät. Es gibt Abendschulen.

Soweit ich weiß kosten die aber was und auch wenn mein Einkommen zur Zeit recht gut ist, weiß ich nicht ob der Kosten/Nutzen Faktor für mich stimmt. Dabei bin ich eigentlich nichtmal bildungsfaul, vielleicht eher autodidaktisch.

wir fangen einfach klein an, mit einer Zahl und einem Sack:
(...)
Analog werden es bei 5 Zahlen 5 mal soviele sein wie bei 4 Zahlen,
... und bei 10 Zahlen 10 mal soviele wie bei 9, das heisst bei x Zahlen

1 * 2 * 3 * 4 * ... * x = x!

Die Funktion, die diesen Wert hat, ist die Fakultätsfunktion, diese wird
mit einem Ausrufezeichen gekennzeichnet. Sie wächst verd^w sehr schnell.

Aha. Jetzt muss ich mir nur noch überlegen wofür man das ausser zur Kernspaltung noch gebrauchen könnte^^
Danke.

Grüße, Matze

[Der Martin]

Hallo Matze,

Die Funktion, die diesen Wert hat, ist die Fakultätsfunktion, diese wird mit einem Ausrufezeichen gekennzeichnet. Sie wächst verd^w sehr schnell.
Aha. Jetzt muss ich mir nur noch überlegen wofür man das ausser zur Kernspaltung noch gebrauchen könnte^^

wenn man Wahrscheinlichkeitsrechnung, Kombinatorik, statistische Methoden anwenden will, kommt man um die Fakultät nicht herum. Also beispielsweise wenn man ausrechnen will, wie hoch die Wahrscheinlichkeit ist, 6 Richtige im Lotto zu haben:

49 * 48 * 47 * 46 * 45 * 44       49! / 43!          1
 -----------------------------  =  -----------  ~  ---------
              6!                        6!          84 Mio.

Die Division durch 6! kommt übrigens nur dadurch, dass die Reihenfolge der Zahlen keine Rolle spielt.
Aber wer will das wirklich wissen ... ?

So long,
 Martin

[Gert]

49 * 48 * 47 * 46 * 45 * 44       49! / 43!          1
-----------------------------  =  -----------  ~  ---------
              6!                        6!          84 Mio.

Das ist aber völlig falsch!
1. Zähler und Nenner vertauscht und zweitens sind es ca. 14 Mio.

[Der Martin]

Hallo Gert,

49 * 48 * 47 * 46 * 45 * 44       49! / 43!          1
-----------------------------  =  -----------  ~  ---------
              6!                        6!          84 Mio.

Das ist aber völlig falsch!

1. Zähler und Nenner vertauscht

stimmt, ich hatte im Ansatz "die Anzahl der Möglichkeiten" im Kopf. Die Wahrscheinlichkeit, mit der eine dieser Möglichkeiten auftritt, ist dann natürlich der Kehrwert.

und zweitens sind es ca. 14 Mio.

Stimmt auch. Aber wie zum Geier bin ich dann auf 84 gekommen? Sieht aus, als hätte ich mich vertippt und nicht durch 6!, sondern durch 5! dividiert.

Danke für die Klarstellung,
 Martin

[Matze]

Hallo nochmal,

Ich weiß, dass es deutlich mehr als 417312000 Lösungen gibt, das ist 115•10!

Was ist das eigentlich für eine Rechenart?
Wenn ich beim Win-Rechner x^y verwende, erhalte ich 404555773570791015625 !?
Das weicht irgendwie leicht von deinem Ergebnis ab.

Grüße, Matze

[Rouven]

Hello,

Ich weiß, dass es deutlich mehr als 417312000 Lösungen gibt, das ist 115•10!
Was ist das eigentlich für eine Rechenart?

die angegebene! :-) Das Satzzeichen gehört dazu, !=Fakultät, schematisch: 4!=4*3*2*1

MfG
Rouven

[Vinzenz Mai]

Hallo

Ich weiß, dass es deutlich mehr als 417312000 Lösungen gibt, das ist 115•10!

Was ist das eigentlich für eine Rechenart?

wie erwähnt, ist es die Fakultätsfunktion,

Wenn ich beim Win-Rechner x^y verwende, erhalte ich 404555773570791015625 !?

In der wissenschaftlichen Ansicht n! verwenden.

Freundliche Grüße

Vinzenz

[Ashanti]

Salam!

Ich weiß, dass es deutlich mehr als 417312000 Lösungen gibt, das ist 115•10!

In der Aufgabenstellung steht nix von nummerierten Säckchen, deswegen kannst du die 10! auch weglassen. Und selbst wenn würde man als erstes in einer allgemeinen Lösung o.B.d.A fordern das die Säckchen aufsteigend nummeriert werden, um solche Isomorphien auszuschließen.

Das hätte auch den Vorteil dass du alle 122 offensichtliche Lösungen nennen könntest, statt dich auf die 115 mit 10! Permutationen zu beschränken (die anderen 7 haben doppelte Säcke sodass man nur noch 10!/2 Permutationen hätte).

Ich möchte mal eine Annahme über den kompletten Lösungsraum anstellen:

Seien die Säcke aufsteigend durchnummeriert, d.h mit s_i Anzahl der Münzen im Sack i gelte s_i =< s_{i+1} für i aus {1,..,9}.

Annahme: Eine aufsteigende Zahlenfolge (s_1,..s_10)
mit S_i= s_1 + ... + s_i = Summe { s_j | j<i }
ist genau dann eine Lösung wenn gilt:

a) s_1 =  1

b) s_i =< 1 + S_{i-1} für i={2,..,10}

c) s_10 =  500 - S_9

d) S_10 =  500

insbesondere gilt s_10 =< 250!

Beispiel:
(1, 2, 4, 6, 10, 16, 33, 65, 129, 234)

s_1=2   =< 1+1=2
s_2=4   =< 1+1+2=4
s_3=6   =< 1+1+2+4=8
s_4=10  ist > 2^3 und <= 1+1+2+4+6=13
usw.

Beweis: vollständige Induktion:
Man zeigt einfach sukzessive für n =1 bis 10 dass für die Teilfolgen (s_1,..s_n) gilt, dass sich alle Zahlen kleinergleich S_n durch Addition aus Teilfolgenelementen darstellen lassen.

Für die Zahlen kleinergleich S_{n-1} brauchen wir das nicht zu zeigen, das folgt unmittelbar aus dem vorhergehenden Induktionsschritt. Und für alle Zahlen x im Intervall S_{n-1} bis S_n gilt wg. Bedingung b) unmittelbar dass x - s_n =< S_{n-1} womit wir eine Summendarstellung erhalten.

Für die Rückrichtung, dass es keine weiteren Lösungen gibt, muss man sich überlegen das mit

b*)   s_i > 1 + S_{i-1}

Folgen würde das 1 + S_{i-1} schon nicht mehr darstellbar wäre.

Und d) s_10 =< 250  gleichbedeutend mit S_9 >= 250

q.e.d.

bekomme ich jetzt 500€?

:) Ashanti

[Ashanti]

Salam!

In einfachen Worten ausgedrückt:

Die Säcke müssen von klein nach groß bestückt werden, dabei darf der jeweils nächste Sack höchstens so groß werden wie die Summe aller kleineren Säcke plus eins.

Konnte ich mit den kleineren Säcken alle Beträge kleiner ihrer Gesamtsumme darstellen, dann kann ich mit dem neuen Sack auch alle Beträge bis zur neuen Gesamtsumme darstellen.

Das Spielchen wiederholt man bis man 10 Säcke hat deren Gesmtsumme 500 ergibt.

Aleikum!
 Ashanti

[Vinzenz Mai]

Hallo

Ich weiß, dass es deutlich mehr als 417312000 Lösungen gibt, das ist 115•10!

In der Aufgabenstellung steht nix von nummerierten Säckchen, deswegen kannst du die 10! auch weglassen.

selbstverständlich sind die Säckchen numeriert, sonst muss man sie entweder öffnen oder wiegen :-)

Und selbst wenn würde man als erstes in einer allgemeinen Lösung o.B.d.A fordern das die Säckchen aufsteigend nummeriert werden, um solche Isomorphien auszuschließen.

Das ist aber nicht gefordert - und Du kannst selbstverständlich auch eine absteigende Folge eingeben, die Lösung wird korrekterweise als richtig akzeptiert. Also ist es eine korrekte Lösung. Daher gibt es ja soviele Lösungen, denn es gilt:

a) Die Säckchen sind unterscheidbar
b) Es gibt keine Einschränkung hinsichtlich: nur aufsteigend bestückbar o.ä.

Damit resultiert die hohe Gesamtzahl von möglichen Lösungen.

Annahme: Eine aufsteigende Zahlenfolge (s_1,..s_10)
mit S_i= s_1 + ... + s_i = Summe { s_j | j<i }
ist genau dann eine Lösung wenn gilt:

a) s_1 =  1
b) s_i =< 1 + S_{i-1} für i={2,..,10}
c) s_10 =  500 - S_9
d) S_10 =  500

das hatte ich mir inzwischen - ohne es mathematisch zu formulieren - auch
zusammengereimt.

Im Sinne: Es gibt konkrete Lösungen für die konkrete Aufgabenstellung bleibt
eben noch zu berechnen, wieviele verschiedene Lösungen das sind. Meine untere
Grenze bleibt selbstverständlich bestehen :-)

Die tatsächliche Gesamtzahl auszurechnen, bleibt als Übung :-)

Freundliche Grüße

Vinzenz

[Ashanti]

Hallo Vinzenz!

Ich weiß, dass es deutlich mehr als 417312000 Lösungen gibt, das ist 115•10!

In der Aufgabenstellung steht nix von nummerierten Säckchen, deswegen kannst du die 10! auch weglassen.

selbstverständlich sind die Säckchen numeriert, sonst muss man sie entweder öffnen oder wiegen :-)

Sorry mathematisch ist das blabla... du musst unterscheiden zwischen Aufgabenstellung und Implementierung, in der Aufgabenstellung redet er nur von einer Menge von 10 Säcken (keine Ordnung).

Und selbst wenn würde man als erstes in einer allgemeinen Lösung o.B.d.A fordern das die Säckchen aufsteigend nummeriert werden, um solche Isomorphien auszuschließen.

Das ist aber nicht gefordert - und Du kannst selbstverständlich auch eine absteigende Folge eingeben, die Lösung wird korrekterweise als richtig akzeptiert.

Das ist nur die Web-Implementierung die erlaubt die gleiche Lösung auf bis zu 10! Arten und Weisen einzugeben.

Eine korrekte Antwort auf die Aufgabenstellung könnte z.B. Lauten:
"2 Säcke mit 1 Münze, 3 mit 4, ...usw."

Ein Feedbackformular für sowas ist aber deutlich aufwendiger zu imlementieren.

Ein Mathematiker würde im erst beim Beweisen zur Bequemlichkeit und O.B.d.A. eine Ordnung einführen.

Glaub mir ich habe dank Doppelstudium zumindest ein Mathevordiplom einer der tollen "Eliteunis" in der Tasche udn kann das beurteilen.

b) Es gibt keine Einschränkung hinsichtlich: nur aufsteigend bestückbar o.ä.

Na ... schlag mal nach was O.B.d.A bedeutet. Sich hier mit Permutationen größer rumzuärgern ist (sorry) unprofessionel..

Salam!
  Ashanti

[Vinzenz Mai]

Hallo ashanti,

Na ... schlag mal nach was O.B.d.A bedeutet. Sich hier mit Permutationen größer rumzuärgern ist (sorry) unprofessionel..

wieso sollte ich etwas nachschlagen, was ich schon lange weiß?
Ich ärgere mich auch nicht mit Permutationen herum, wie kommst Du auf diese Idee?

Schließe bitte nicht von Dir auf andere. *scnr*

Professionelle Grüße

Vinzenz

[Ashanti]

Hallo

Ich ärgere mich auch nicht mit Permutationen herum, wie kommst Du auf diese Idee? Schließe bitte nicht von Dir auf andere. *scnr*

"So seltsam es auch klingen mag, die Stärke der Mathematik beruht auf dem Vermeiden jeder unnötigen Annahme und auf ihrer großartigen Einsparung an Denkarbeit."

Ernst Mach

habe den Lösungsalgo in Javascript realisiert, leider geht mein Firefox ab der 8 Rekursion bzw. Sack in die Knie, man müsste noch ein paar sinnvolle Schranken einbauen um den Suchbaum zu kürzen, d.h. z.B. mit einem Anfang wie (1,1,1,1,1) würde man sowieso nie die Gesamtsumme 500 erreichen.

Salam!
 Ashanti

[Ashanti]

Hi

habe den Lösungsalgo in Javascript realisiert, leider geht mein Firefox ab der 8 Rekursion bzw. Sack in die Knie, man müsste noch ein paar sinnvolle Schranken einbauen um den Suchbaum zu kürzen, d.h. z.B. mit einem Anfang wie (1,1,1,1,1) würde man sowieso nie die Gesamtsumme 500 erreichen.

OK, habe ein paar Baumabschneider eingebaut, aber alleine für 500€ mit 9 Säcken gibts bereits 14 Lösungen:

1: (1,2,4,8,16,32,64,128,245) rec:8
2: (1,2,4,8,16,32,64,127,246) rec:9
3: (1,2,4,8,16,32,64,126,247) rec:10
4: (1,2,4,8,16,32,64,125,248) rec:11
5: (1,2,4,8,16,32,64,124,249) rec:12
6: (1,2,4,8,16,32,64,123,250) rec:13
7: (1,2,4,8,16,32,63,127,247) rec:15
8: (1,2,4,8,16,32,63,126,248) rec:16
9: (1,2,4,8,16,32,63,125,249) rec:17
10: (1,2,4,8,16,32,63,124,250) rec:18
11: (1,2,4,8,16,32,62,126,249) rec:20
12: (1,2,4,8,16,32,62,125,250) rec:21
13: (1,2,4,8,16,31,63,126,249) rec:24
14: (1,2,4,8,16,31,63,125,250) rec:25

Bei 10 Säcken hat das Script nach 98.000 Rekursionen bereits 42.000 Lösungen ausgespuckt...da hab ich's dann auch abgebrochen.... Ohne Worte!

Salam!
 Ashanti

[Vinzenz Mai]

Hallo

habe den Lösungsalgo in Javascript realisiert, leider geht mein Firefox ab der 8 Rekursion bzw. Sack in die Knie, man müsste noch ein paar sinnvolle Schranken einbauen um den Suchbaum zu kürzen, d.h. z.B. mit einem Anfang wie (1,1,1,1,1) würde man sowieso nie die Gesamtsumme 500 erreichen.

Mit etwas Überlegung kannst Du z.B. 125 als kleinsten Wert für Sack 10 ermitteln :-)

1: (1,2,4,8,16,32,64,128,245) rec:8

Das ist die "triviale Lösung", die Grundlage meiner ersten 122 Lösungen war.
Weiter hab' ich gar nicht erst nachgedacht ...

2: (1,2,4,8,16,32,64,127,246) rec:9
3: (1,2,4,8,16,32,64,126,247) rec:10
4: (1,2,4,8,16,32,64,125,248) rec:11
5: (1,2,4,8,16,32,64,124,249) rec:12
6: (1,2,4,8,16,32,64,123,250) rec:13
7: (1,2,4,8,16,32,63,127,247) rec:15
8: (1,2,4,8,16,32,63,126,248) rec:16
9: (1,2,4,8,16,32,63,125,249) rec:17
10: (1,2,4,8,16,32,63,124,250) rec:18
11: (1,2,4,8,16,32,62,126,249) rec:20
12: (1,2,4,8,16,32,62,125,250) rec:21
13: (1,2,4,8,16,31,63,126,249) rec:24
14: (1,2,4,8,16,31,63,125,250) rec:25

Bei 10 Säcken hat das Script nach 98.000 Rekursionen bereits 42.000 Lösungen ausgespuckt...da hab ich's dann auch abgebrochen.... Ohne Worte!

wie wäre es, wenn Du Deinen Algorithmus bekannt gäbest, vielleicht kann der
eine oder andere eine Verbesserung vorschlagen.

Deine 42.000 Lösungen gelten nun ohne Berücksichtigung der Reihenfolge.
Stell' Dir vor, wenn nun - wie im Lösungsformular - noch numerierte Säcke
dazukommen :-)

Friede,

Vinzenz

[Ashanti]

Hi

Mit etwas Überlegung kannst Du z.B. 125 als kleinsten Wert für Sack 10 ermitteln :-)

ja aber in den Bereich dieser unteren Schranke würde der Algo eh nie kommen .. zumindest nicht bei Zahlen so nahe an einer 2er Potenz wie 500.

wie wäre es, wenn Du Deinen Algorithmus bekannt gäbest, vielleicht kann der
eine oder andere eine Verbesserung vorschlagen.

ähm den Algorithmus hab ich doch bereist beschrieben?!?

Du meinst den JS Code? ich schick die HTML-Seite unten mit.

Die Aufwandskomplexität  des Codes kann man m.E. kaum noch optimieren (fast jede zwote Rekursion spuckt eine Lösung aus)!

Interessanter wäre eine mathematische Betrachtung wie aus der Lösung für 9 Säcke sich die Lösungen für 10 Säcke konstruieren (grob gesprochen, man nimmt Münzen aus den 9 Säcken udn stopft sie so in nen 10. Sack, den man so einreiht dass die Reihenfolge gewahrt bleibt, aber keine Lösungen doppelt kosntruiert werden). Und aus dieser Mathematischen Betrachtung sollte sich mit etwas Glück auch ne Formel für die ANzahl der Lösungen ableiten lassen.

Aber ehrlich, das Problem ist ausgelutscht und nicht sonderlich ergiebig. Es gibt AFAIK Mathematiker/Informatiker die sich mit ählichen Aufgaben herumschlagen, wo man aber mit Münzen bestimmter unterschiedlicher Werte bezahlen muss. Dass hat dann auch einen echten praktischen Hintergrund, z.B. bei der Optimierung von Machinenlaufzeiten.

Viel Spass mit dem Code, ist ein Draft ... und nicht verwirren lassen dass er erst ab 1 indiziert aber trotzdem 0 ausgibt.

Salam
 Aschanti

------------------------- HTML+JS-Code 500Euro.html

<html>
  <head>
    <title>500 Euro Rtsel</title>
  </head>

<body>
    <h1>500 Euro Rtsel</h1>

<script>
var s=new Array(0,1);  // Scke, s[0] ignorieren, weil es keinen nullten Sack gibt
var S=new Array(0,1);  // Zwischensummen
var S_min=new Array(); // minimale Schranken fr Zwischensummen
var muenzen=500;
var saecke=10;
var rec=0;      // # Rekursionen

function sack(i) {
  rec++;

// letzter Sack erreicht => Ausgabe falls Lsung
  if ( i == saecke) {
    s[i]=muenzen-S[i-1];
    if ( s[i] <= S[i-1]+1 && s[i] >= s[i-1] ) {
   document.writeln (l++ + ": (" +s+ ") rec:"+rec+"<br>"); // nullten Index ignorieren
    }
    return;
  }

// ansonsten tiefer Suchen
  for (var j = S[i-1]+1; j >= s[i-1]; j-- ) {
 // Vorwrtszhlen liefert die Ergebnisse sehr spt
 //for (var j = s[i-1] ; j <= S[i-1]+1 ; j++ ) {

s[i]=j;
    S[i]=S[i-1]+s[i];

if ( S[i] >= S_min[i] ) {
   sack(i+1);
 }
  }
}

function init_schranken() {
  S_min[saecke]=muenzen;
  for (var i=saecke-1 ; i > 0 ; i--) {
 S_min[i]=Math.floor(S_min[i+1]/2);
  }
  document.writeln( "Minimale Zwischensummen:"+ S_min +"<br>");
}

var i=1; // Sack index
var l=1; // Lsung counter
init_schranken();
sack(2);

document.writeln( " Anzahl Rekursionen="+rec);

</script>
  </body>
</html>

[Ashanti]

hab mal Opera drauf angesetzt, läuft zwar 10 mal lamer als Firefox, fragt mich aber nicht alle 5 Sekunden ob ich das langsam laufende Skript unterbrechen möchte.

[Patrick Andrieu]

Hallo Ashanti!

Das war die Aufgabe:

500 Stück 1€-Münzen sollen in zehn Säckchen so verteilt werden, dass jede Summe zwischen 1€ und 500€ gebildet werden kann, ohne dass ein Säckchen geöffnet werden muss.
---> In jedem der zehn Säckchen muss sich mindestens eine Münze befinden. <---

Bei allem Respekt für Deine Programmierkunst, aber die ersten Zeilen, die mein Browser anzeigt (Sanduhr läuft noch, er wird es nicht schaffen - das Rechnen hat die CPU überstanden, das Rendern schafft der IE nicht mehr), sehen so aus:

1: (0,1,2,4,8,16,32,64,--- mehr sehe ich nicht, da ein Fenster davor stand, alle Reichen sind an der Kante abgeschnitten)

Von Säcken mit 0 Münzen war in der Aufgabe nie die Rede. Genauso wenig wie von einer 9-Säcken-Lösung ;)

Viele Grüße aus Frankfurt/Main,
Patrick

[Patrick Andrieu]

Ups...

alle Reichen sind an der Kante abgeschnitten

Ja. Und die Nicht-Reichen sind arm dran...

Viele Grüße aus Frankfurt/Main,
Patrick

[Vinzenz Mai]

Hallo,

meine völlig unelegante iterative Vorgehensweise kommt auf:
7302334 Iterationen durch die innerste Schleife und
6017023 Lösungen, die letzte ist

[1, 2, 4, 8, 16, 32, 64, 124, 124, 125]

Mein Code, alles andere als beispielhaft, die Wahl fiel deswegen auf Python,
weil es an der Konsole gerade verfügbar war:

  
# Belege die Saecke mit der Mindestanzahl von Muenzen vor  
sack  = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]  
summe = [1, 0, 0, 0, 0, 0, 0, 0, 0, 0]  
  
# Wir muellen das Wurzelverzeichnis von C: voll :-)  
namepart = 'c:/martin.'  
  
# Brute-Force mit nur wenig Ueberlegungen:  
# Grenzen  
# Index  Sack     Untergrenze   Obergrenze  
#   0      1        1             1          - trivial  
#   1      2        1             2          - trivial  
#   2      3        1             4          - trivial  
#   3      4        2             8          - Obergrenze trivial, Untergrenze, da sonst max. moegliche Zahl nicht erreichbar  
#   4      5        4            16          - Obergrenze trivial, Untergrenze, siehe Sack 4  
#   5      6        8            32          - Obergrenze trivial, Untergrenze, siehe vorher  
#   6      7       16            64          - Obergrenze trivial, Untergrenze wie gehabt  
#   7      8       32           128          - Obergrenze trivial, Untergrenze wie gehabt  
#   8      9       63           167          - Untergrenze wie gehabt, Obergrenze: 1/3 unterhalb, 1/3 oberhalb und 1/3 fuer Sack 9  
#   9     10      125           250          - aber Sack 10 = 500 - Summe(Saecke 1 bis 9)  
  
  
filename = namepart + '0'  
f = file(filename, "w")  
iter  = 0  
count = 0  
for sack[1] in range(1,3):  
  # der naechste Sack muss mindestens soviel enthalten, wie der vorhergehende  
  summe[1] = sack[0] + sack[1]  
  for sack[2] in range(max(1, sack[1]), min(summe[1] + 2, 5)):  
    summe[2] = summe[1] + sack[2]  
    for sack[3] in range(max(2, sack[2]), min(summe[2] + 2, 9)):  
      summe[3] = summe[2] + sack[3]  
      for sack[4] in range(max(4, sack[3]), min(summe[3] + 2, 17)):  
        summe[4] = summe[3] + sack[4]  
        for sack[5] in range(max(8, sack[4]), min(summe[4] + 2, 33)):  
          summe[5] = summe[4] + sack[5]  
          for sack[6] in range(max(16, sack[5]), min(summe[5] + 2, 65)):  
            summe[6] = summe[5] + sack[6]  
            for sack[7] in range(max(32, sack[6]), min(summe[6] + 2, 128)):  
              summe[7] = summe[6] + sack[7]  
              for sack[8] in range(max(63, sack[7]), min(summe[7] + 2, 168)):  
                # zaehle die Iterationen  
                iter = iter + 1  
                summe[8] = summe[7] + sack[8]  
                # 1. Bedingung erfuellt: Summe der Inhalte ist 500 durch  
                sack[9] = 500 - summe[8]  
  
                if ((sack[9] > 250) or (sack[9] < 125) or sack[9] < sack[8]):  
                  # Sack 10 nicht im richtigen Intervall, oder kleiner als vorhergehender  
                  # passt nicht  
                  break;  
  
                # Hier angelangt, haben wir eine richtige Loesung  
                # zaehle die Treffer  
                count = count + 1  
  
                # Ausgabevorbereitung  
                line = str(sack) + "\n"  
  
                # Dateihandling  
                # Nur 100.000 Eintraege je Datei - und auch nur dann eine Ausgabe auf die Konsole  
                if ((count % 100000 == 0) and (count / 100000 > 0)):  
                  f.close()  
                  filename = namepart + str((count / 100000))  
                  f = file(filename, "w")  
                  print iter, " - ", count, ":", line,  
  
                # Schreibe sie weg  
                f.write(line)  
  
# Fertig, Gesamtzahl noch ausgeben:  
print iter, " - ", count, ":", line,  
f.close()  

Freundliche Grüße

Vinzenz

[Ashanti]

Hi

Also offensichtlich ist einer unserer beiden Algos falsch, könten wir für kleinere Parameter vergleichen?

Was spuckt dein programm für Muenzen 500 Säcke 9 aus?

ich nix Python ...

Salam
 Ashanti

[Ashanti]

Hi

Brute-Force mit nur wenig Ueberlegungen:

Vielleicht zu wenig ?

#   7      8       32           128          - Obergrenze trivial, Untergrenze wie gehabt

Tatsächlich?

dann ist wohl ne Fälschung im Umlauf
(1,2,4,8,16,31,63,125,125,125)

SCNR!
 Ashanti

[Ashanti]

Ok, ich nehme alles zurück, aber sorry, ich verstehe deinen Code nicht.

Salam!
 Ashanti

[Ashanti]

Ok, ich nehme alles zurück, aber sorry, ich verstehe deinen Code nicht.

Gut nochmal, soweit ich es verstehe sollten deine Lösungen mit der Ausgabe lexikografisch wachsen.

Die erste Zeile die dein Script liefert ist:

[1, 1, 3, 5, 10, 21, 42, 84, 84, 249]

und sollte minimal sein.

Lasse ich mein Script aufwärts rechnen bekomme ich aber

1 1 1 4 8 16 31 63 125 250

was eine deutlich kleinere und korrekte Lösung ist.

=> Dein Script ist fehlerhaft!

... insbesondere verstehe ich nicht wie du deine Schranken herleitest, eine richtige Begründung gibst du leider nicht an (???)

Gute Nacht!
 Ashanti

[Vinzenz Mai]

Hallo

Ok, ich nehme alles zurück, aber sorry, ich verstehe deinen Code nicht.

Gut nochmal, soweit ich es verstehe sollten deine Lösungen mit der Ausgabe lexikografisch wachsen.

Die erste Zeile die dein Script liefert ist:

[1, 1, 3, 5, 10, 21, 42, 84, 84, 249]

und sollte minimal sein.

Lasse ich mein Script aufwärts rechnen bekomme ich aber

1 1 1 4 8 16 31 63 125 250

was eine deutlich kleinere und korrekte Lösung ist.

=> Dein Script ist fehlerhaft!

Du hast recht => man sollte um diese Zeit keinen Code mehr schreiben
und erst recht keine unnötigen "Abkürzungen" einbauen, die sich als Fehler
entpuppen

if ((sack[9] > 250) or (sack[9] < 125) or sack[9] < sack[8]):
                  # Sack 10 nicht im richtigen Intervall, oder kleiner als vorhergehender
                  # passt nicht

# hier steckt der Fehler
                    # verlaesst die innere Schleife statt direkt den
                    # naechsten Schleifendurchlauf vorzunehmen

# break;

# Entweder ein continue oder ein einfaches else
                    continue

  

> ... insbesondere verstehe ich nicht wie du deine Schranken herleitest, eine richtige Begründung gibst du leider nicht an (???)  
  
Zu den Grenzen:  
Die Obergrenzen sollten klar sein:  
  
1) Bis Sack 8 die Zweierpotenzen,  
  
2) bei Sack 9 ist es erforderlich:  
   a) die Summe von Sack 1-8 maximal um 1 kleiner ist als der Inhalt von Sack 9  
   b) Sack 10 hat mindestens soviel Inhalt wie Sack 9  
   => Minimale Summe = 3\* Inhalt von Sack 9 - 1  
   => 3 \* Inhalt von Sack 9 = 501  
   => Maximaler Inhalt von Sack 9 = 167  
  
3) Sack 10: Grenze klar (hast Du ja begründet)  
  
Die Untergrenzen ergaben sich durch gezieltes Probieren :-)  
Verkleinere die Untergrenze jeweils um 1 und ermittle die maximal erreichbare  
Summe, bis zu der jede Zahl darstellbar ist => die Summe wird kleiner als 500  
sein.  
  
Deine Vorgehensweise ist deutlich schneller :-)  
Freundliche Grüße  
  
Vinzenz

[Ashanti]

Salam Vinzenz

Deine Vorgehensweise ist deutlich schneller :-)

Heisst das du kannst mein Ergebnis bestätigen?

Und die Javascriptlösung ist schneller als die mit Python ???

Oder wieviele Ergebnisse bekommst du jetzt?
Bei wievielen Rekursionen?

(oder rechnet dein Script noch ;)

Viele Grüße
 Ashanti

[Ashanti]

Guten Morgen Vinzenz

Habe gerade die veränderte Überschrift registriert :)

Meine Fragen haben sich erübrigt, außer

Und die Javascriptlösung ist absolut schneller als die mit Python ???

Salam
  Ashanti

[Vinzenz Mai]

Hallo

Und die Javascriptlösung ist absolut schneller als die mit Python ???

zu absolut kann ich nichts sagen - hab' ich noch nicht getestet.
Derzeit gehe ich davon aus, dass vor allem die Dateizugriffe viel Zeit kosten.

Freundliche Grüße

Vinzenz

[Ashanti]

Hi

zu absolut kann ich nichts sagen - hab' ich noch nicht getestet.

ich schon hab aber hier nen alten P2:
35min ohne ausgabe
45min mit

Salam!
 Ashanti

[Vinzenz Mai]

Hallo

ich schon hab aber hier nen alten P2:
35min ohne ausgabe
45min mit

ohne Ausgabe, Celeron 3GHz, Dein Code 1:1 nach Python übersetzt:

rekursiv: 01:37 min
iterativ: 06:45 min (mein Notebook mit einem Pentium M, 1500MHz ist schneller)

Deine Ersparnis von ungefähr 48.000.000 macht sich da sicher bemerkbar.
Außerdem ist mein Code extrem unflexibel und nicht auf vergleichbare
Probleme anwendbar.

Freundliche Grüße

Vinzenz

[Ashanti]

Hi Vinzenz!

Deine Ersparnis von ungefähr 48.000.000 macht sich da sicher bemerkbar.
Außerdem ist mein Code extrem unflexibel und nicht auf vergleichbare
Probleme anwendbar.

Rekursiv ist natürlich flexibler als Iterativ, aber schneller sollte letzteres sein, (zumindest ein paar Prozent) man spart nämlcih 28.000.000 Funktiosnaufrufe.

Es liegt an der Art der Schrankenberechnung wenn mein Code schneller ist.

Aber wer will schon 25.000.000 Lösungen ausrechnen???

Oder kommt jetzt als nächstes ein Agent der die Webseite mit Lösungen zubombt??? ;-)

Salam
 Ashanti

[Vinzenz Mai]

Hallo

Oder kommt jetzt als nächstes ein Agent der die Webseite mit Lösungen zubombt??? ;-)

Wenn man jetzt noch berücksichtigt, dass man jede Lösung auf viele verschiedene
Arten eintragen könnte, könnte man gewaltig spammen, ohne das Formular zweimal
auf die gleiche Art und Weise auszufüllen. *g*

Die nächste Frage, die ich per brute-force und einer modifizierten Version
Deiner Lösung mir beantworten lassen will, ist folgende:

Bei welcher Anzahl von Münzen bei gegebener Anzahl von Säcken (Test natürlich mit 10) ist die Anzahl der Lösungen maximal.

Bei n Säcken und n Münzen gibt es ebenfalls genau eine Lösung
Bei n Säcken und (2^n)-1 Münzen gibt es genau ein Lösung

Bei wievielen Münzen gibt es die maximale Anzahl von Möglichkeiten.
Wäre jemand so freundlich gewesen und hätte das Problem mathematisch analysiert,
könnte man es einfach ausrechnen, bei 10 Säcken lasse ich lieber den Rechner laufen ...

Freundliche Grüße

Vinzenz

[Ashanti]

Hi

Die nächste Frage, die ich per brute-force und einer modifizierten Version
Deiner Lösung mir beantworten lassen will, ist folgende:

Bei welcher Anzahl von Münzen bei gegebener Anzahl von Säcken (Test natürlich mit 10) ist die Anzahl der Lösungen maximal.

Du bist schon ein  Optimist! Nur weil der Fall für 500 Münzen in knapp einer Minute durchgerechnet wurde muss das nicht für die anderen Fälle gelten.

ich würde versuchen aus den Schranken etwas abzuleiten, so in der Art "wenn die Summe der Differenzen aller min und max Schranken maximal ist dann auch die Anzahl der Löungen.

Übrigens probier mal 150 Münzen mit 9 Säcken :)

Salam
 Ashanti

[Ashanti]

Hi Vinzenz

und rechnet der Laptop immer noch :-)

Salam
 Ashanti

[Ashanti]

Hi Vinzenz

IMHO kann man den Algo nochmals rasant beschleunigen wenn man Zwischenergebnisse cachet.

Die rekursive Funktion müsste überprüfen ob sie schonmal mit der gleichen letzten Zwischensumme und Sackfüllung aufgerufen wurde, falls
nein: Anzahl der Folgelösungen berechnen und merken!
ja:   Anzahl der Folgelösungen übernehmen.

Beispiel:

Muenzen/Saecke: 30/6
...
53:   1 2 2 4 6 15  rec:70  ite:53
54:   1 2 2 3 9 13  rec:72  ite:54
55:   1 2 2 3 8 14  rec:73  ite:55
56:   1 2 2 3 7 15  rec:74  ite:56
57:   1 2 2 2 8 15  rec:76  ite:57
...
72:   1 1 3 4 6 15  rec:96  ite:72
73:   1 1 3 3 9 13  rec:98  ite:73
74:   1 1 3 3 8 14  rec:99  ite:74
75:   1 1 3 3 7 15  rec:100 ite:75
76:   1 1 2 5 10 11  rec:103 ite:76

die Teilsequenzen 1 2 2 3 und 1 1 3 3 haben die gleiche Summe
und die gleichen Endzahl, deswegen folgen immer 3 weitere Teillösungen (54-56 = 73-75).

Auf diese Art und Weise verlagert man effektiv Zeitkomplexität
auf Speicherkomplexität :)

Salam
 Ashanti

[Ashanti]

Hallo

IMHO kann man den Algo nochmals rasant beschleunigen wenn man Zwischenergebnisse cachet.

Tatsächlich ist so mehr als Faktor 100 Beschleunigung machbar:

Opera sagt:

"Maximum für Säcke=10 liegt bei Münzen=347 mit 47.493.951 Möglichkeiten"

Ich denke das Thema ist jetzt erschöpfend diskutiert ...

Salam!
  Ashanti

[Ashanti]

Lieber Patrick

1: (0,1,2,4,8,16,32,64,--- mehr sehe ich nicht, da ein Fenster davor stand, alle Reichen sind an der Kante abgeschnitten)

Der Code ist ein Hack ... aber wer lesen kann ist klar im Vorteil ... ich schrieb

"und nicht verwirren lassen dass er erst ab 1 indiziert aber trotzdem 0 ausgibt."

und im Code steht nochmal "nullten Index ignorieren"

Um analog zum beschriebenen Algo zu bleiben hab ich das Array
ab 1 indiziert, deswegen gibt er auch einen "0-ten Sack" aus.
Würde dein IE nicht beim Rendern zusammenbrechen, hättest du gesehen dass pro Zeile 11 Zahlen ausgegeben werden.

Habe nochmal rumoptimiert, und dieses "0-ter-Index-Feature" rausgeschmissen.

Die Optimierung hat aber wie befürchtet nur wenig
an Geschwindigkeit gebracht ich erhalte jetzt:

Anzahl Rekursionen= 28258321
Anzahl Lösungen= 24813353

habe also 165 Rekursionen und 1 Lösung eingespart (letzteres würde ich als Bug bezeichnen, den zu finden ich dem Forum überlasse)[*]

Ach ja dass die Browser Probleme haben 24 Millionen Zeilen auszugeben ist nachvollziehbar, deswegen habe ich auch beim 10 Sack-Fall die Ausgabe der Lösungen in Opera auskommentiert.

Um es dir einfacher zu machen hab ich dir jetzt ne GUI eingebaut, ob die allerdings in deinem IE funktioniert kann ich dir mangels Windoof nicht sagen (dafür gehen meine Umlaute beim cut&paste aus emacs flöten ... ).

Salam nach FFM
  Ashanti

[*] ich habs, ich habs!!! (TIP: das Alte Ergebnis war falsch)

---------------- neue version 500Euro.html

<html>
  <head>
    <title>500 Euro Rtsel</title>
  </head>

<body>
    <h1>500 Euro Rtsel </h1>

Aufgabestellung siehe
<a href="http://www.mindfile.org/Spiele/Eurosack">
http://www.mindfile.org/Spiele/Eurosack
</a>

<p>

<form>
Muenzen <input name="muenzen" value="500"><br>
Scke <input name="saecke" value="9"><br>
Ausgabe <input type="checkbox" name="ausgabe" checked>
<input type="submit" value="leg los" onClick="main()">
</form>

<script>

function main() {

var s=new Array();  // Scke,
var S=new Array();  // Zwischensummen
s[1]=1;S[1]=1;      //s[0] ignorieren, weil es keinen nullten Sack gibt
var S_min=new Array(); // minimale Schranken fr Zwischensummen
var s_max=new Array(); // maximale Schranken fr Scke

// Defaultwerte fr onLoad-Ausfhrung
var muenzen=500;
var saecke=10;
//var muenzen=250;
var saecke=9;
var ausgabe="on";

var l=0;    // init Lsung counter

var rec=0;      // init # Rekursionen

// Parameter einlesen
  saecke=document.forms[0].saecke.value;
  muenzen=document.forms[0].muenzen.value;
  ausgabe=document.forms[0].ausgabe.checked;

document.open();
   document.writeln( "<pre>");

init_schranken();

document.writeln( "<hr><h3>BERECHNUNG:</h3>" );
 start=write_Time();
 sack(2);  // Rekursion starten
 ende=write_Time();
 document.writeln( "Dauer: "+(ende-start)+" millisec" );

document.writeln( "<hr><h3>ERGEBNIS:</h3>" );
 document.writeln( "Anzahl Rekursionen=\t"+rec );
 document.writeln( "Anzahl Lsungen=\t"+l );
 document.writeln( "</pre>");
 document.close();

function sack(i) {
  rec++;

// letzter Sack erreicht => Ausgabe falls Lsung, Rekursion abbrechen
  if ( i == saecke) {
    s[i]=muenzen-S[i-1];
    if ( s[i] <= S[i-1]+1 && s[i] >= s[i-1] ) {
   l++;
   if (ausgabe ) {
  document.writeln (l + ":\t <b>" +s.join(" ")+ "</b>\t rec:"+rec); // Ausgabe hier auskommentieren
   }
    }
    return;
  }

// ansonsten tiefer Suchen
  var max,min;

max=S[i-1]+1;
  max=Math.min( max, s_max[i] );

min=s[i-1];
  s_min=S_min[i] -S[i-1];   // wg S[i] = S[i-1]+j >= S_min[i]
  min=Math.max( min, s_min);

for (var j = max ; j >= min ; j-- ) {
 // Abwrtsszhlen liefert eher Ergebnisse als Aufwrts
 //for (var j = min ; j <= max ; j++ ) {

s[i]=j;
    S[i]=S[i-1]+s[i];

//if ( S[i] >= S_min[i] ) {
 sack(i+1);
 //}
  }
}

function init_schranken() {
  S_min[saecke]=muenzen;
  for (var i=saecke-1 ; i > 0 ; i--) {
 S_min[i]=Math.floor(S_min[i+1]/2);
  }

// da Saecke aufsteigend sortiert, kann i-ter Sack hoechstens soviele
  // Muenzen enthalten wie man noch maximal in alle groeeren stecken kann.
  for (var i=saecke ; i >0 ; i--) {
 var kleinere_saecke=i-1;
 var groessgleich_saecke=saecke-kleinere_saecke;
 s_max[i]=Math.floor( (muenzen-kleinere_saecke)/groessgleich_saecke);
  }
  document.writeln( "<hr><h3>INIT:</h3>");
  document.writeln( "Minimale Zwischensummen:"+ S_min.join("\t"));
  document.writeln( "Maximale Sackfllung:\t"+ s_max.join("\t") );
  document.writeln( "Muenzen/Saecke:\t" + muenzen+"  "+saecke );
}

function write_Time() {
  var Jetzt = new Date();
  document.writeln("Zeit: "+Jetzt.toLocaleString());
  var Zeit = Jetzt.getTime();
  return Zeit;
}

}

</script>

</body>
</html>

[Don P]

Hallo,

Annahme: Eine aufsteigende Zahlenfolge (s_1,..s_10)
mit S_i= s_1 + ... + s_i = Summe { s_j | j<i }
ist genau dann eine Lösung wenn gilt:

a) s_1 =  1

b) s_i =< 1 + S_{i-1} für i={2,..,10}

c) s_10 =  500 - S_9

d) S_10 =  500

insbesondere gilt s_10 =< 250!

Beispiel:
(1, 2, 4, 6, 10, 16, 33, 65, 129, 234)

s_1=2   =< 1+1=2
s_2=4   =< 1+1+2=4
s_3=6   =< 1+1+2+4=8
s_4=10  ist > 2^3 und <= 1+1+2+4+6=13
usw.

In a) verlangst du s_1 = 1, aber im Beispiel erklärst du s_1 = 2. Soll das jetzt eher ein Gegenbeispiel sein, oder hattest du aus Versehen ein s_0 im Sinn und die Erklärung zum Beispiel (1, 2, 4, 6, 10, 16, 33, 65, 129, 234) ist also falsch?

Gruß, Don P

[Ashanti]

Hi Don,

s_1=2   =< 1+1=2 ...

In a) verlangst du s_1 = 1, aber im Beispiel erklärst du s_1 = 2. Soll das jetzt eher ein Gegenbeispiel sein, oder hattest du aus Versehen ein s_0 im Sinn und die Erklärung zum Beispiel (1, 2, 4, 6, 10, 16, 33, 65, 129, 234) ist also falsch?

Danke für den Hinweis, ist natürlich ein Versehen, sollte  s_2 heißen.

Das normale zerebrale Kuddelmuddel mit Indizierungen die mal mit 1 oder 0 anfangen. (So wie ich mir seit der Euroumstellung
nur noch Geldbeträge mit einer 2er Potenz Unschärfe merken kann. ;-)

Egal wie man jetzt indiziert, für den 2. Sack muss gelten:
 er hat mind. eine und höchstens 2 Münzen.

Salam
  Ashanti

[Sven Rautenberg]

Moin!

gib doch mal eine Schätzung ab, wieviele richtige Lösungen es gibt:

[X] weniger als 1 Million
[ ] mehr als 1 Million

Ich habe 10 Säcke. In jeden kann ich zwischen 1 und 500 Münzen reintun, also 500 Zustände erzeugen. Das mal 10 ergibt 5000 Lösungen.

Als obere Schranke sollte das also ausreichen. :)

- Sven Rautenberg

[Daniel Thoma]

Hallo Sven,

Ich habe 10 Säcke. In jeden kann ich zwischen 1 und 500 Münzen reintun, also 500 Zustände erzeugen. Das mal 10 ergibt 5000 Lösungen.

Was ist das denn für eine Rechnung? Wenn man einfach nur die Anzahl der Möglichkeiten in jedes Säckchen 1..500 Münzen zu tun (ohne die Summe zu berücksichtigen) hat man ja 499^10 Möglichkeiten also ... viele ;-)

Wenn man die Summe und die Unabhängigkeit von der Reihenfolge berücksichtigt, wird das deutlich weniger. Auf den ersten Blick sehe ich aber nicht, wie man das einfach berechnen kann.

Grüße

Daniel

[Cheatah]

Hi,

Cheater^^ *SCNR

hier bin ich. Und bitte schreib meinen Namen richtig. Was gibt's?

Cheatah, SCNR2 ;-)

[Daniel Thoma]

Hallo Martin,

Warum eigentlich 10 Säckchen wenn die naheliegendste Lösung mit 9 Säckchen auskommt? ;-)

Grüße

Daniel

[Vinzenz Mai]

Hallo Daniel,

Warum eigentlich 10 Säckchen wenn die naheliegendste Lösung mit 9 Säckchen auskommt? ;-)

das hat Martin bestimmt absichtlich gemacht, damit wir hier Stoff für eine
Diskussion haben :-) Vielleicht dürfen wir nachher auch raten, was die
häufigst genannte Lösung (ohne Beachtung der Reihenfolge) ist.

Freundliche Grüße

Vinzenz

[Frank (no reg)]

Hi,

der Bitte, eine Statistik über die Antworten auszugeben, ist er doch schon für die letzte (Tierquälerei-)Rechenaufgabe nicht nachgekommen. :(

So long, so short
Frank

[Micha]

Hallo Daniel Thoma,

Warum eigentlich 10 Säckchen

Habe ich mich auch gefragt, nachdem ich erstmal munter drauf los getippt habe und dann den Hinweis bekam, es seien mehr als 500 Taler ;-)

Mit freundlichem Gruß
Micha

[Ashanti]

Hallo Martin,

500 Euro.

ich habe auf der Webseite einen Eintrag hinterlassen das es um die 25 Millionen Lösungen für dein Problem gibt, kannst du mir erklären wieso du den kommentarlos löschst???

Salam!
  Ashanti

[Sven Rautenberg]

Moin!

500 Euro.

ich habe auf der Webseite einen Eintrag hinterlassen das es um die 25 Millionen Lösungen für dein Problem gibt, kannst du mir erklären wieso du den kommentarlos löschst???

Auszug aus dem Impressum: "Der Betreiber dieser Website behält sich vor, Leserkommentare ohne Angabe von Gründen teilweise oder ganz zu löschen."

- Sven Rautenberg

[Ashanti]

Hallo

Auszug aus dem Impressum: "Der Betreiber dieser Website behält sich vor, Leserkommentare ohne Angabe von Gründen teilweise oder ganz zu löschen."

Tja und ich behalte mir vor nachzufragen.

Auszug aus meinem Verständnis:

a) Er braucht nicht antworten
b) Ich brauch ihn dann künftig nicht zu beachten

Salam!
 Ashanti