Zahlenkombinationen

Hallo Wissende,

@Kubi, ja, ich habe die Brettbeschreibung gelesen und finde trotzdem meine Anfrage gehört hier rein und nicht ins Rätselbrett :smile:

In einem reinen Excelforum tauchte als Anfrage diese Problematik auf:

Mit 16 Zahlen von 1 bis 100 sollen ALLE Zahlen von 1 bis 100 mit maximal 2 Zahlen gebildet werden. Z.B. 1=1; 2=1+1; 3=2+1…100= 50+50.

Ich habe nun rumprobiert um dies mal mit den Zahlen 1-10 nachzubauen und kam dafür auf eine Lösung wo man diese Aufgabe mit 5 Zahlen (1,2,3,4,5) lösen kann:
1
1+1
1+2
1+3
1+4
1+5
2+5
3+5
4+5
5+5

Möglicherweise ginge dies auch nur mit nur 4 Zahlen bei geschickterer Aufteilung aber das ist gar nicht meine eigentliche Anfrage hier.

Aus der dortigen Anfrage hat sich eine Beitragsfolge entwickelt und darin ist zu lesen daß jmd. durch manuelles Ausprobieren auf die 16 Zahlen:
49,51,1,2,4,8,16,32,46,42,25,7,13,60,69,86
kam und angeblich dadurch schon 83 Zahlen erzeugen konnte
Er sprach von insgesamt 10^18 Möglichkeiten, ein Anderer sprach von 2^16 Möglichkeiten.

Jetzt meine Fragen:

a) Wieviele Möglichkeiten sind es denn nun?

b) Bei eigenen Gedanken zur Problematik kam ich darauf daß die höchste benutzte Zahl die 50 ist, ist dieser Gedanke falsch oder richtig? Immerhin wurden ja schon 83 Zahlen gefunden indem man höher als 50 ging.

Achja, an sich ging/geht die Anfrage dahin Excel-Vba Code also ein makro zu basteln was alle Kombinationen durchgeht bis es die Lösungszahlen hat.

Wenn man nun alle Möglichkeiten durchgeht, also in Schleifen 16 Variabelen die Werte von 1 bis 100 zuweist, eine sogenannte Brute-Force Attake, so dauert es auf meinem Rechner mindestens bis Weihnachten bis da eine Lösung kommt *gg*

Deshalb wäre mir eine Antwort zu b) lieb um ggfs. Rechenzeit zu sparen.
Aus dem gleichen Grund wäre mir auch jede Information wichtig die besagt daß z.B. die ersten 5 Zahlen die Zahlen 1,2,4,7,11 sein müssen, denn dann muß ich nur noch 11 Zahlen variabel gestalten…

Danke ^ Gruß
Reinhard

Hi…

Mit 16 Zahlen von 1 bis 100 sollen ALLE Zahlen von 1 bis 100
mit maximal 2 Zahlen gebildet werden. Z.B. 1=1; 2=1+1;
3=2+1…100= 50+50.

Also nur Addition.

Er sprach von insgesamt 10^18 Möglichkeiten, ein Anderer
sprach von 2^16 Möglichkeiten.

a) Wieviele Möglichkeiten sind es denn nun?

Möglichkeiten für was?
Vermutung: „Wieviele Möglichkeiten gibt es, 16 verschiedene Zahlen zwischen 1 und 100 auszuwählen?“
Das wären 100!/(100-16+1)! = 2,8 * 1031, also wesentlich mehr als die beiden Vorschläge.

b) Bei eigenen Gedanken zur Problematik kam ich darauf daß die
höchste benutzte Zahl die 50 ist, ist dieser Gedanke falsch
oder richtig? Immerhin wurden ja schon 83 Zahlen gefunden
indem man höher als 50 ging.

Ich denke, man wird deutlich über 50 gehen müssen, kann das aber nicht aus dem Handgelenk beweisen.

Achja, an sich ging/geht die Anfrage dahin Excel-Vba Code also
ein makro zu basteln was alle Kombinationen durchgeht bis es
die Lösungszahlen hat.

Wenn man nun alle Möglichkeiten durchgeht, also in Schleifen
16 Variabelen die Werte von 1 bis 100 zuweist, eine sogenannte
Brute-Force Attake, so dauert es auf meinem Rechner mindestens
bis Weihnachten bis da eine Lösung kommt *gg*

Weihnachten welches Jahr? :wink:

Deshalb wäre mir eine Antwort zu b) lieb um ggfs. Rechenzeit
zu sparen.
Aus dem gleichen Grund wäre mir auch jede Information wichtig
die besagt daß z.B. die ersten 5 Zahlen die Zahlen 1,2,4,7,11
sein müssen, denn dann muß ich nur noch 11 Zahlen variabel
gestalten…

Klar ist, daß die 1 dabei sein muß, weil man anders keine 1 darstellen kann. Weiterhin muß entweder die 2 oder die 3 dabei sein, um die 3 erzeugen zu können. Spinnt man diese Denkweise weiter, kommt als nächster Schritt:

  • Habe ich 1 und 2, dann kann ich 1,2,3,4 erzeugen. Die kleinste Zahl, die ich nicht schaffe, ist die 5. Um die zu erzeugen, brauche ich 3,4 oder 5
  • Habe ich 1 und 3, dann kann ich 1,2,3,4,6 erzeugen. Die kleinste Zahl, die ich nicht schaffe, ist (zufällig) wieder die 5. Ich brauche 2 oder 4.

In den folgenden Schritten gibt es natürlich noch viel mehr Möglichkeiten, aber sie steigen lange nicht in so astronomische Höhen wie beim blinden Probieren. Wenn es Dir also gelingt, diesen Denkprozess zu automatisieren, hast Du gute Chancen, daß Dein Programm in vernünftiger Zeit durchläuft.
Problematisch könnte der Speicherbedarf für die Zwischenergebnisse sein, aber das gehört dann wirklich in ein Programmierforum.

genumi

Hallo Genumi,

Mit 16 Zahlen von 1 bis 100 sollen ALLE Zahlen von 1 bis 100
mit maximal 2 Zahlen gebildet werden. Z.B. 1=1; 2=1+1;
3=2+1…100= 50+50.
Er sprach von insgesamt 10^18 Möglichkeiten, ein Anderer
sprach von 2^16 Möglichkeiten.

a) Wieviele Möglichkeiten sind es denn nun?

Möglichkeiten für was?
Vermutung: „Wieviele Möglichkeiten gibt es, 16 verschiedene
Zahlen zwischen 1 und 100 auszuwählen?“
Das wären 100!/(100-16+1)! = 2,8 *
1031, also wesentlich mehr als die
beiden Vorschläge.

Ich kenne mich in Kombinationen nicht aus um sagen zu können welche Möglichkeiten ich eigentlich genau meine:frowning:

b) Bei eigenen Gedanken zur Problematik kam ich darauf daß die
höchste benutzte Zahl die 50 ist, ist dieser Gedanke falsch
oder richtig? Immerhin wurden ja schon 83 Zahlen gefunden
indem man höher als 50 ging.

Ich denke, man wird deutlich über 50 gehen müssen, kann das
aber nicht aus dem Handgelenk beweisen.

Ach, deine Vermutung es geht weit übe 50 reicht mir schon um das dann anzunehmen.

Wenn man nun alle Möglichkeiten durchgeht, also in Schleifen
16 Variabelen die Werte von 1 bis 100 zuweist, eine sogenannte
Brute-Force Attake, so dauert es auf meinem Rechner mindestens
bis Weihnachten bis da eine Lösung kommt *gg*

Weihnachten welches Jahr? :wink:

-) Gute Frage *gg*

Klar ist, daß die 1 dabei sein muß, weil man anders keine 1
darstellen kann. Weiterhin muß entweder die 2 oder die 3 dabei
sein, um die 3 erzeugen zu können. Spinnt man diese Denkweise
weiter, kommt als nächster Schritt:

  • Habe ich 1 und 2, dann kann ich 1,2,3,4 erzeugen. Die
    kleinste Zahl, die ich nicht schaffe, ist die 5. Um die zu
    erzeugen, brauche ich 3,4 oder 5
  • Habe ich 1 und 3, dann kann ich 1,2,3,4,6 erzeugen. Die
    kleinste Zahl, die ich nicht schaffe, ist (zufällig) wieder
    die 5. Ich brauche 2 oder 4.
    In den folgenden Schritten gibt es natürlich noch viel mehr
    Möglichkeiten, aber sie steigen lange nicht in so
    astronomische Höhen wie beim blinden Probieren. Wenn es Dir
    also gelingt, diesen Denkprozess zu automatisieren, hast Du
    gute Chancen, daß Dein Programm in vernünftiger Zeit
    durchläuft.

Danke dir für deine Mühen, probiere ich halt zu denken und zu knobeln, mal schauen wie weit ich komme…

Problematisch könnte der Speicherbedarf für die
Zwischenergebnisse sein, aber das gehört dann wirklich in ein
Programmierforum.

Ja, aber da hat bislang noch keiner einen Grundansatz, also Programmcode entwickelt.

Gruß
Reinhard

Hallo,

Mit 16 Zahlen von 1 bis 100 sollen ALLE Zahlen von 1 bis 100
mit maximal 2 Zahlen gebildet werden. Z.B. 1=1; 2=1+1;
3=2+1…100= 50+50.

sind denn 2 gleiche Zahlen erlaubt? Also kann z.B. die 100 gebildet werden, wenn nur einmal die 50 da ist?

Olaf

Holla.

Dass man die 1 braucht, ist wohl unbestritten.

Primzahlen:2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97 sind 25 Stück, so ich mich nicht verzöhl.

Dann können wir 1,2,3,2+2,5,3+3,7,5+3,5+5,11,11+1,11+2,11+3,13+2,13+3,17,13+5,19,17+3,
19+2,19+3,23,23+1,23+2,23+3,23+5,29,29+1,31,31+1,31+2,31+3,31+5,37,
37+1,37+2,37+3,41,41+1,43,43+1,43+2,43+3,47,47+1,47+2,47+3,47+5,53,
53+1,53+2,53+3,53+5,59,59+1,61,61+1,61+2,61+3,61+5,67,67+1,67+2,67+3,
71,71+1,73,73+1,73+2,73+3,73+5,79,79+1,79+2,79+3,83,83+1,83+2,83+3,
83+5,89,89+1,89+2,89+3,89+5,89+7,97,97+1,97+2,97+3

Fehlt die 9, die 27, die 35, die 51, die 57, die 65, die 77, die 87, die 93, die 95.

9-4=5;27-4=23;35-4=31;51-4=47;57-4=53;65-4=61;77-4=73;87-4=83;93-4=89;95-4 ist schade, also noch die 6: 95-6=89.

Zu der 1 und den 25 Primzahlen noch die 4 und die 6, dann kann man alle Zahlen von 1 bis 100 mit maximal zwei Summanden schreiben.

Und wie kommt das? Die maximale Differenz zweier Primzahlen zwischen 1 und 100 beträgt 8, nämlich zwischen 89 und 97. Von 1 bis 8 brauchen wir als Summe nur die 4 (1+3), die 6(5+1) und die 8(5+3) als Summe zu schreiben, alle anderen sind eh da.

Gruß Eillicht zu Vensre

1 „Gefällt mir“

Hallo,

Ich denke, man wird deutlich über 50 gehen müssen, kann das
aber nicht aus dem Handgelenk beweisen.

das denke ich nicht.

Beispiel: Du nimmst die Zahlen 1, 2, 3 und 4. Dann kannst du die Zahlen 5, 6, 7 und 8 durch Addition bilden und brauchst als nächste Zahl die 9. Von da aus kannst du wieder vier Zahlen durch Addition erhalten usw. - du hast also in deiner Zahlenkette immer Lücken von mindestens 4 Zahlenwerten. Da kommt man dann auf unter 50 Zahlen. 40 oder so dürften es aber trotzdem sein, also groß ist der Unterschied nicht :smile:

So, ich hoffe das war jetzt nicht ganz Schwachsinnig, mein Bus fährt nämlich in fünf Minuten… und tschüss :wink:

mfg
MB

interessante fragestellung, bin gespannt, ob wir jemals auf eine wirklich elegante lösung kommen.

ich hab mal ein bißchen herumprobiert nach dem prinzip „alle zahlen von 1 bis x, und dann jeweils 2x+1, 3x+2 usw.“. die beste lösung ist [1,2,3,4,5,6,7,8,9,19,29,39,49,59,69,79,89,99], das sind 18 zahlen, mit denen man alle bis 108 bilden kann. läßt man die 99 weg, kommt man mit 17 zahlen immerhin bis 98.

bei x=9 scheint es so einen wendepunkt zu geben, ich kanns jetzt aus dem stegreif nicht beweisen, aber die ergebnisse werden sowohl nach unten als auch nach oben hin schlechter (x=8 => 19 zahlen, alles bis 105; x=10 => 18 zahlen bis 108, aber 17 nur bis 97; x=11 => 18 zahlen bis 106).

natürlich ist das nicht unbedingt die optimale lösung, war nur eine idee, der ich nachgegangen bin.

ich würde es auch mit einem großen baum angehen, der allerdings wirklich schnell recht groß wird. im prinzip ist gleich die erste frage, ob man die 2 als zahl dazunimmt oder als 1+1 bildet, und bei jeder weiteren zahl kommen immer mehr möglichkeiten dazu. ich habe auf die schnelle auch kein kriterium gefunden, wie man einzelne äste des baumes aussiebt.

ich habe exemplarisch mit [1,2] begonnen und habe bereis 21 möglichkeiten für fünf zahlen, von denen allerdings nur zwölf die 12 und nur zwei die 13 bilden können. 14 und 15 sind wiederum bei vielen kein problem. ich wüßte nicht, wie ich entscheiden sollte, welche der möglichen kombinationen sich auf lange sicht als mächtiger erweist.

b) Bei eigenen Gedanken zur Problematik kam ich darauf daß die
höchste benutzte Zahl die 50 ist, ist dieser Gedanke falsch
oder richtig? Immerhin wurden ja schon 83 Zahlen gefunden
indem man höher als 50 ging.

man kann ja rückwärts überlegen. mit der 50 kann man 100 bilden, aber schon für die 99 brauchen wir mindestens noch die 49. die reicht wiederum für 98, aber für 97 brauchen wir entweder die 48 oder die 47. man kann also 100 durchaus mit zahlen bis zu 50 bilden, aber es wird auch so herum schnell ein unübersichtlicher baum, und es gibt keine garantie, daß es sich mit 16 zahlen ausgeht.

eine idee hab ich noch: wenn man davon ausgeht, daß die zahlen [a,a+a;b,a+b,b+b;c,a+c,b+c,c+c;usw.] voneinander verschieden sind, kommt man mit 16 verschiedenen zahlen meiner berechnung nach auf 152 mögliche summen. das bedeutet, daß wir uns bis 100 genau 52 redundanzen (summen, die man auf mehr als eine art bilden kann) leisten können. das ist nicht viel, wenn man bedenkt, daß man bereits bei [1,2,3,4] fünf redundanzen hat.

eventuell schafft es jemand, diesen gedankengang weiterzuführen und in die bewertung der äste der oben genannten bäume einfließen zu lassen.

Hallo,

Ich habe die Kette nun mal verfolgt.
Mir ist auf gefallen, dass man an verschiedenen Stellen auch die Primzahlen einsparen kann. Beispiel 31. Diese könnte man mit 29+2 einsparen.Die 2 ist ohnehin schon in Verwendung. Primzahlen unterliegen lediglich der Teilbarkeit durch 1 und sich selbst. Hat keinerlei Berührung mit der vorliegenden Problematik der Summenfindung dur Addition.

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

Hallo,

Gedanke zurücksetzen!

Ich habe die Kette nun mal verfolgt.
Mir ist auf gefallen, dass man an verschiedenen Stellen auch
die Primzahlen einsparen kann. Beispiel 31. Diese könnte man
mit 29+2 einsparen.Die 2 ist ohnehin schon in Verwendung.
Primzahlen unterliegen lediglich der Teilbarkeit durch 1 und
sich selbst. Hat keinerlei Berührung mit der vorliegenden
Problematik der Summenfindung dur Addition.

Dann reist meine Kette ab, und müsste die 4 hinzuziehen.

Jetzt mit 4 weiterknobeln.

Danke für das Interesse und die Ansätze,

Mit 16 Zahlen von 1 bis 100 sollen ALLE Zahlen von 1 bis 100
mit maximal 2 Zahlen gebildet werden. Z.B. 1=1; 2=1+1;
3=2+1…100= 50+50.

Hallo,

ich habe auch rumprobiert, kam auch mit 18-19 Zahlen auf über 100, aber halt nicht mit 16.
1, 2, 3, 4, 5, 6, 7, 15, 23, 31, 39, 47, 55, 63, 71, 79, 87, 95
bzw.
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 22, 33, 44, 55, 66, 77, 88, 99
bzw.
1, 2, 3, 4, 5, 6, 7, 8, 17, 26, 35, 44, 53, 62, 71, 80, 89, 98

Ich bin mathematisch nicht fit (Mittlere Reife, 40 Jahre her), habe das z.B. mit den Primzahlen nicht so ganz verstanden, habe halt beim Testen festgestellt, man kann z.B. „anfangs“ die 6 und/oder 3 weglassen, aber irgendwann fehlt sie bei höheren Zahlen.

Und, ich bin in Excel-Vba schn fit genug 16 variablen die Werte von 1-100 annehmen zu lassen und dann abzuprüfen ob wenn ich eine oder zwei von nehme ich damit dann alle Zahlen von 1 bis 100 erzeugen kann durch Addition wobei auch mal keine Addition vorkommt.

Nur, wenn ich da vorher nicht einiges ausschließen kann dauert dieser Code ewig.
Ausschließen bedeutet, eine Variable muß die 1 sein, eine andere muß die 2, sind also feste Konstanten.

Dann muß ich nur noch 14 Variablen hochzählen und austesten.
Aber das ist für die Lauftzeitlänge des Programmes immer noch eweng zuviel, ich hab ja keinen Gray-Computer oder wie die Superrechner inzwischen heißen :smile:

Und zu der Nachfrage zur Anzahl der Möglichkeiten, nehmen wir das eben Geschrieben mal an, also 2 Variablen sind konstant, 14 andere durchlaufen die Werte von 1-100, aus diesen 16 Variablen picke ich mir alle 2er Additionen und Einzelvorkommen heraus und prüfe ob ich damit alle Zahlen von 1-100 gemäß der Regel erzeugen kann, dann habe ich doch eine exakte Anzahl an Möglichkeiten.

Und diese Anzahl an Möglichkeiten müßte m.E. doch berechenbar sein *glaub aber nix genaues weiß*

Gruß
Reinhard

Hi…

Nur, wenn ich da vorher nicht einiges ausschließen kann dauert
dieser Code ewig.
Ausschließen bedeutet, eine Variable muß die 1 sein, eine
andere muß die 2, sind also feste Konstanten.

Bei der 2 wäre ich mir nichtmal sicher.

Und zu der Nachfrage zur Anzahl der Möglichkeiten, nehmen wir
das eben Geschrieben mal an, also 2 Variablen sind konstant,
14 andere durchlaufen die Werte von 1-100, aus diesen 16
Variablen picke ich mir alle 2er Additionen und
Einzelvorkommen heraus und prüfe ob ich damit alle Zahlen von
1-100 gemäß der Regel erzeugen kann, dann habe ich doch eine
exakte Anzahl an Möglichkeiten.

Und diese Anzahl an Möglichkeiten müßte m.E. doch berechenbar
sein *glaub aber nix genaues weiß*

Das geht:
Variable A läuft von 1-100 – klare Sache, 100 Möglichkeiten
Für jeden Wert von A läuft B von A+1 bis 100 – Dann sind wir bei 99*100
So geht es weiter, d.h. bei 14 Variablen gibt es
100*99*98*…*87 = 3,8 * 1027 Möglichkeiten. Für jede diese Möglichkeiten möchtest Du alle Kombinationen von 1 oder zwei Variablen berechnen, das sind 14 (eine Variable) + 14*14 (zwei Variablen, die auch identisch sein können), macht 210.
Das bedeutet, Du musst 8 * 1029 Kombinationen berechnen. Das dauert auch auf einem Großrechner mehrere Millionen Jahre.
Selbst wenn Du auf 10 Variablen reduzieren könntest, würde der aktuell schnellste Rechner der Welt mindestens ein Jahr brauchen.

Fazit: Dieser Ansatz ist zum Scheitern verurteilt.

genumi

Eine Lösung
Hallo Interessierte,

1,3,4,9,11,16,20,25,30,34,39,41,46,47,49,50

soll eine von mehreren Lösungen sein. Ich habe das nachstehend mal bis zur Zahl 30 nachgestellt, scheint zu funktionieren.

Die Lösung wurde klassisch, also ohne PC nur mit Blatt Papier und was zu schreiben und Hirn *gg* entwickelt.

Zur Lösung der ursprünglichen Anfrage wie man diese Zahlen denn per Excel-Vba herausfindet nützt mir das nix.
Denn, abgesehen von der unbestrittenen 1 muß ich alle anderen 15 Zahlen als Variablen immer noch von 1 bis 100 durchlaufen lassen denn diese Lösung beweist ja nicht daß es keine Lösung gibt mit Zahlen die auch über 50 gehen.

Danke für das Interesse und Impulse
Gruß
Reinhard

Tabellenblatt: [Mappe1]!Tabelle1
 │ A │ B │ C │
───┼────┼────┼────┤
 1 │ 1 │ │ 1 │
───┼────┼────┼────┤
 2 │ 1 │ 1 │ 2 │
───┼────┼────┼────┤
 3 │ 3 │ │ 3 │
───┼────┼────┼────┤
 4 │ 3 │ 1 │ 4 │
───┼────┼────┼────┤
 5 │ 4 │ 1 │ 5 │
───┼────┼────┼────┤
 6 │ 3 │ 3 │ 6 │
───┼────┼────┼────┤
 7 │ 3 │ 4 │ 7 │
───┼────┼────┼────┤
 8 │ 4 │ 4 │ 8 │
───┼────┼────┼────┤
 9 │ 9 │ │ 9 │
───┼────┼────┼────┤
10 │ 9 │ 1 │ 10 │
───┼────┼────┼────┤
11 │ 11 │ │ 11 │
───┼────┼────┼────┤
12 │ 11 │ 1 │ 12 │
───┼────┼────┼────┤
13 │ 9 │ 4 │ 13 │
───┼────┼────┼────┤
14 │ 11 │ 3 │ 14 │
───┼────┼────┼────┤
15 │ 11 │ 4 │ 15 │
───┼────┼────┼────┤
16 │ 16 │ │ 16 │
───┼────┼────┼────┤
17 │ 16 │ 1 │ 17 │
───┼────┼────┼────┤
18 │ 9 │ 9 │ 18 │
───┼────┼────┼────┤
19 │ 16 │ 3 │ 19 │
───┼────┼────┼────┤
20 │ 11 │ 9 │ 20 │
───┼────┼────┼────┤
21 │ 20 │ 1 │ 21 │
───┼────┼────┼────┤
22 │ 11 │ 11 │ 22 │
───┼────┼────┼────┤
23 │ 20 │ 3 │ 23 │
───┼────┼────┼────┤
24 │ 20 │ 4 │ 24 │
───┼────┼────┼────┤
25 │ 25 │ │ 25 │
───┼────┼────┼────┤
26 │ 25 │ 1 │ 26 │
───┼────┼────┼────┤
27 │ 16 │ 11 │ 27 │
───┼────┼────┼────┤
28 │ 25 │ 3 │ 28 │
───┼────┼────┼────┤
29 │ 20 │ 9 │ 29 │
───┼────┼────┼────┤
30 │ 30 │ │ 30 │
───┴────┴────┴────┘
Benutzte Formeln:
C1 : =A1+B1
C2 : =A2+B2
C3 : =A3+B3
C4 : =A4+B4
C5 : =A5+B5
C6 : =A6+B6
C7 : =A7+B7
C8 : =A8+B8
C9 : =A9+B9
C10: =A10+B10
C11: =A11+B11
C12: =A12+B12
C13: =A13+B13
C14: =A14+B14
C15: =A15+B15
C16: =A16+B16
C17: =A17+B17
C18: =A18+B18
C19: =A19+B19
C20: =A20+B20
C21: =A21+B21
C22: =A22+B22
C23: =A23+B23
C24: =A24+B24
C25: =A25+B25
C26: =A26+B26
C27: =A27+B27
C28: =A28+B28
C29: =A29+B29
C30: =A30+B30

A1:C30
haben das Zahlenformat: Standard

Tabellendarstellung erreicht mit dem Code in FAQ:2363