Autor |
Beitrag |
Yaddle
Hält's aus hier
Beiträge: 9
|
Verfasst: Fr 20.01.12 16:55
Hey Leute,
ich habe die zahlenfolge 2,2,3,3,4,4,5,5 und soll prüfen, ob ich daraus zwei zahlen bilden kann, bei deren division das ergebnis 2 entsteht. Gibt es da ein Patentrezept oder kriegt man das nur durch probieren hin? Unser Mathelehrer hat uns die Aufgabe gestellt und wir sollen die bearbeiten.
Danke schonmal im Vorraus
Moderiert von Th69: Titel geändert.
|
|
Delphi-Laie
Beiträge: 1600
Erhaltene Danke: 232
Delphi 2 - RAD-Studio 10.1 Berlin
|
Verfasst: Fr 20.01.12 17:58
Yaddle hat folgendes geschrieben : | ich habe die zahlenfolge 2,2,3,3,4,4,5,5 und soll prüfen, ob ich daraus zwei zahlen bilden kann, |
Wie willst Du denn "daraus zwei zahlen bilden"? Nach welcher Bildungsvorschrift?
Yaddle hat folgendes geschrieben : | bei deren division das ergebnis 2 entsteht. Gibt es da ein Patentrezept oder kiregt man das nur durch probieren hin? |
Systematisches Probieren ist auch ein, wenn nicht das "Patentrezept".
|
|
ujr
Beiträge: 102
Erhaltene Danke: 12
|
Verfasst: Fr 20.01.12 18:36
Hallo,
besser als die Division zu "probieren" wäre, Zahl für Zahl mit 2 zu multiplizieren und nachzuschauen, ob das Ergebnis Teil der Zahlenfolge ist.
|
|
Martok
Beiträge: 3661
Erhaltene Danke: 604
Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
|
Verfasst: Fr 20.01.12 19:22
Das wichtigste vorneweg: das ist keine Zahlenfolge, sondern eine Menge! Wichtiger Unterschied
Was dann auch heißt, dass dein Thread-Titel nicht wirklich zum Problem passt (und sowieso etwas sehr kurz ist).
Bitte ändere daher den Titel des Topics. Einfach unten in deinem ersten Beitrag auf klicken und den Titel ändern. Danke Dir!
Und jetzt zur Frage.
Man kann das auch durch nachdenken lösen. Bei so wenigen möglichen Ziffern ist schon klar was an letzter Stelle stehen muss:
Die letzte Ziffer von der einen Zahl (A0) muss also aus der Menge stammen, die andere (B0) muss der letzten Ziffer von A0*2 entsprechen. Also: 2*2= 4, 3*2= 6, 4*2= 8, 5*2=1 0
Drei davon haben wir gar nicht verfügbar, also ist die letzte Ziffer von beiden Zahlen klar: A0=2, B0=4.
Jetzt ist nur noch die Frage was man davor schreiben kann. Das kann ich grad nicht schlüssig beweisen, aber ich vermute dass man einfach rekursiv mit der gleichen Begründung arbeiten kann
ujr hat folgendes geschrieben : | Hallo,
besser als die Division zu "probieren" wäre, Zahl für Zahl mit 2 zu multiplizieren und nachzuschauen, ob das Ergebnis Teil der Zahlenfolge ist. |
Dazu brauchst du nur alle bis 4-Stelligen Zahlen generieren (bei der Divison durch 2 hat das Ergebnis auch entweder die gleichen Stellen oder eine Stelle weniger; daher maximal 4 Stellen für 2 4-Stellige Zahlen als Lösung) und für die in die Regeln passenden prüfen, ob die Multiplikation mit 2 wieder eine mögliche Zahl ergibt.
Ich hab das mal schnell ohne Prüfung auf mehrfachvorkommen einer Ziffer gemacht, und erhalte:
Quelltext 1: 2: 3: 4:
| 2 4 22 44 222 444 2222 4444 |
Man sieht, nur 2 Paare davon sind wirklich möglich.
Viele Grüße,
Martok
_________________ "The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
|
|
Yaddle
Hält's aus hier
Beiträge: 9
|
Verfasst: Fr 20.01.12 21:21
Also eine mathematische Lösung wäre mir lieber als so ein empirisches Schleifen-Wirr-Warr Ähm also man hat diese Menge Zahlen und darf wirklich nur diese benutzen. Jede nur zweimal, alle müssen benutzt werden und wie gesagt, soll die eine doppelt so groß wie die andere sein. Die Zahlen sind dabei als Ziffern einer größeren Gesamtzahl zu betrachten und dürfen beliebig angeordnet und auf die zwei Zahlen verteilt werden. Die Zahlen müssen nicht die gleiche Anzahl an Ziffern haben, aber wahrscheinlich haben die gesuchten zwei es
Also wäre echt toll, wenn jemand eine Antwort wüsste. Ich habe mir schon den Kopf zermartert
Grüße
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Fr 20.01.12 23:54
Durch Martok wurde schon ausgeführt, dass die letzte Ziffer von A eine 2 sein muss, die letzte von B eine 4, d.h. A = xxx2 , B = xxx4.
Die erste Ziffer von A kann nur eine 2 sein, andernfalls müsste die erste Ziffer von B mindestens 6 sein. Damit ist die erste Ziffer von B eine 4 oder 5 (Übertrag), d.h. A = 2xx2 , B = 4xx4 oder 5xx4.
Da die zwei Dreien verarbeitet werden müssen, können Sie nur an den mittleren Stellen auftreten. Bei A ist dies nicht möglich, da das Doppelte dann eine 6 verlangt, die nicht zur Menge gehört.
Bei B kann an zweiter und dritter Stelle keine 3 auftreten, da diese beim Verdoppeln nur durch einen Übertrag entstehen könnte. Bei den gegebenen Ziffern ist dies nicht möglich, da nur durch Verdoppeln der 5 ein Übertrag entsteht und dieser nur durch Verdoppeln einer 1 (ist nicht in der Menge) in der Summe eine Drei ergibt.
Fazit: Mit den gegebenen Ziffern können keine Zahlen, wie gewünscht, erzeugt werden.
Eine drei- und eine fünfstellige Zahl schließt sich sofort aus.
Beste Grüße
Mathematiker
Kleiner Nachtrag: Solltest Du Dir wirklich den "Kopf zermartert" haben, ist das schon bedenklich. Die Aufgabe ist nämlich ziemlich trivial.
Für diesen Beitrag haben gedankt: Martok
|
|
Martok
Beiträge: 3661
Erhaltene Danke: 604
Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
|
Verfasst: Sa 21.01.12 01:30
Danke Mathematiker!
Freut mich, dass meine BruteForce-Schleife offensichtlich keinen Fehler hatte
Ich frage mich nur ein wenig, was die Aufgabe für einen Sinn hat. Rätselaufgabe?
_________________ "The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
|
|
Yaddle
Hält's aus hier
Beiträge: 9
|
Verfasst: Sa 21.01.12 10:00
Und wie sähe das ganze bei einer verlängerten Zahlenfolge aus? Welche wären möglich? Wie ist es bei doppelt so vielen Ziffern???
2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9 Hier dürfte die letzte Zahl nicht eindeutig bestimmbar sein oder???
|
|
Th69
Beiträge: 4763
Erhaltene Danke: 1051
Win10
C#, C++ (VS 2017/19/22)
|
Verfasst: Sa 21.01.12 10:53
Hallo Martok,
streng mathematisch handelt es sich dabei aber auch um keine Menge (denn dann wäre die Anzahl gleichartiger Elemente nämlich immer 1, da mehrfach vorkommende Elemente nicht beachtet werden).
Daher ist dies eher ein Problem der Abzählenden Kombinatorik (in diesem Fall: Variation ohne Zurücklegen), und dort heißt es dann einfach "Anordnung von Objekten".
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Sa 21.01.12 11:39
Sorry Th69,
es ist doch eine Menge.
Nach der Cantorschen Definition ist eine Menge "jede Zusammenfassung von bestimmten wohlunterschiedenen Objekten unserer Anschauung oder unseres Denkens; welche die "Elemente" der Menge genannt werden; zu einem Ganzen".
Durch die Angabe von gleichen Ziffern in {2,2,3,3,4,4,5,5} werden die Elemente dennoch (im Denken!) unterscheidbar, da die Ziffern einen Index tragen, der allerdings nicht geschrieben wird. D.h. es gibt formal gesehen eine "2a" und eine "2b" usw.
Beschränkt man Mengen auf Elemente, die hingeschrieben(!) nicht gleich aussehen, so steuert man sofort in die Widersprüche der klassischen Mengenlehre.
In der Mengendefinition der axiomatischen Mengenlehre wird das noch klarer. Die nicht ganz einfache Definition spare ich mir hier. Bei Wikipedia findet man's.
Ich gebe aber zu, dass die Frage "Menge" oder "nicht Menge" von verschiedenen Mathematikern auch verschieden gesehen wird. Eine absolut eindeutige Festlegung gibt es nicht.
Dass das Problem zur Abzählenden Kombinatorik gehört, ist klar.
Für die erweiterte Menge {2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9} wird das Problem erheblich schwieriger.
Unüberlegtes BruteForce benötigt über 20 Billionen (= 16!) Tests. Bedenkt man, dass die letzten Ziffern 2/4, 3/6, 4/8, 6/2, 7/4, 8/6 und 9/8 sein können, wird es etwas weniger.
Mal sehen, ob ich wenigstens eine Lösung finde.
Beste Grüße
Mathematiker
|
|
Yaddle
Hält's aus hier
Beiträge: 9
|
Verfasst: Sa 21.01.12 12:55
Für die Begriffsreiter: Die Bezeichnung "Menge" ist inkorrekt aber nah dran, denn in einer Menge darf jedes Element nur einmal enthalten sein. Sind eines oder mehrere Elemente öfter als einmal enthalten, spricht man von einer "Multimenge". Aber ich glaube dieses formelle Problem, stellt nicht die größte Schwierigkeit im Problem dar. Aber wäre cool, wenn man sich mal aufs eigentliche Problem beschränkt und die Formalien ein wenig zur Seite schiebt. Solange jeder versteht, was gemeint ist, stellt das nämlich kein Problem dar.
Gruß
|
|
Delphi-Laie
Beiträge: 1600
Erhaltene Danke: 232
Delphi 2 - RAD-Studio 10.1 Berlin
|
Verfasst: Sa 21.01.12 13:03
|
|
Ralf Jansen
Beiträge: 4700
Erhaltene Danke: 991
VS2010 Pro, VS2012 Pro, VS2013 Pro, VS2015 Pro, Delphi 7 Pro
|
Verfasst: Sa 21.01.12 13:07
Zitat: | Solange jeder versteht, was gemeint ist, stellt das nämlich kein Problem dar. |
Korrekt. Da du aber immer noch nicht beantwortet hast wie man die Zahlen aus deinem Haufen (hoffentlich unverfänglicher Begriff) Zahlen den genau bilden darf (eine, Kombination aus 2 oder n, zwangsweise alle, zwangsweise alle eindeutigen etc.) versteht man, zumindest ich, nicht was deine Frage genau ist. Dazu kommt noch das unklar ist ob du eine bestimmte Zahlenfolge (zum Beispiel die aus deinem ersten Beitrag) meinst oder eine beliebige.
|
|
Th69
Beiträge: 4763
Erhaltene Danke: 1051
Win10
C#, C++ (VS 2017/19/22)
|
Verfasst: Sa 21.01.12 13:12
Hallo Yaddle,
bitte ändere (wie von Martok schon geschrieben) trotzdem den Titel dieses Topics.
P.S. Den Begriff "Abzählende Kombinatorik" habe ich u.a. deswegen in den Raum geworfen.
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Sa 21.01.12 13:16
Um das Thema vielleicht abzuschließen, füge ich die Exe und den Quelltext eines Programms an, das nach den Zahlen sucht.
Das Programm ist ein "Schnellschuss", d.h. der Algorithmus kann sicher verbessert werden. Außerdem ist ein hässliches Label drin, das natürlich alle Profiprogrammierer zur Verzweiflung bringt.
Außerdem funktioniert es nur, wenn eine gerade Anzahl von Ziffern eingegeben wird.
Sorry, aber es ist eben ein Schnellschuss.
Auf jeden Fall, kann man aus der Menge, Multimenge, Haufen, Zusammenstellung, "sinnlose Anordnung", usw. (2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9) keine Zahlen konstruieren, deren Division 2 ergibt.
Versucht es mal mit ( 1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8 ). Da gibt es Lösungen.
Beste Grüße
Mathematiker
Nachtrag: Mit Ziffern 0 funktioniert es nicht richtig. In der Anzeigeliste werden die Nullen am Ende der Zahlen abgeschnitten.
Problem behoben!
Zuletzt bearbeitet von Mathematiker am Sa 21.01.12 13:45, insgesamt 2-mal bearbeitet
|
|
Delphi-Laie
Beiträge: 1600
Erhaltene Danke: 232
Delphi 2 - RAD-Studio 10.1 Berlin
|
Verfasst: Sa 21.01.12 13:19
Martok hat folgendes geschrieben : | Das wichtigste vorneweg: das ist keine Zahlenfolge, sondern eine Menge! Wichtiger Unterschied |
Nun, warum es keine Folge sein kann, erschließt sich mir nicht ganz. Eine Folge ist es m.E. dann, wenn eine wohldefinierte Reihenfolge existert. Ob nur diese eine Reihenfolge möglich ist, erschließt sich aus der Ausgangsfrage nicht zweifelsfrei, die Sortierung anhand der Größe ist allerdings augenfällig. Womöglich liegt der Menge (oder Folge) eine Bildungsvorschrift zugrunde, dann wäre es tatsächlich eine Folge.
Um auch akribisch zu sein:
Martok hat folgendes geschrieben : | Bei so wenigen möglichen Ziffern ist schon klar was an letzter Stelle stehen muss: |
Um Ziffern kann es sich hier nicht handeln, weil der Diskussionseröffner von einer Zahlenfolge sprach.
|
|
Hidden
Beiträge: 2242
Erhaltene Danke: 55
Win10
VS Code, Delphi 2010 Prof.
|
Verfasst: Sa 21.01.12 13:32
Hallo Yaddle,
schön, dass du dich für eine mathematische Lösung interessierst (dazu gehört aber auch eine scharfe Formulierung, vielleicht ist der Teil der Diskussion für dich also doch nicht so ganz uninteressant, wenn du es richtig aufschreiben willst).
Mir ist aber noch gar nicht klar, wie denn genau zusammengesetzt werden soll. So vielleicht?
>>
Existieren für x = (1,1,2,2,3,3,4,4,5,5) Permutationen P,Q: \N^{10} nach \N^{10}, sodass
Summe 10^i * x_(P_i) = 2 Summe 10^i * x_(Q_i)?
Für 1 <= x_i <= 4 äquivalent:
x_P = 2 x_Q (Eindeutigkeit der Dezimalschreibweise).
<<
Mathematiker: Du meinst, man kann das Problem mit einer Menge formulieren? Th69 hat Recht, {1,1} ist /keine/ Menge. Wenn du die Elemente durch ihren Index unterscheiden willst, musst du so etwas schreiben wie {(1,i1), (1,i2)}. Korrekter wäre 'Tupel' (2,2,3,3,4,4,5,5) oder im unendlichen Fall wie im Titel 'Folge' 1,1,2,2,3,3,4,4,5,5,... (es gibt aber keine endlichen/abbrechenden Folgen, der ist also falsch).
Delphi-Laie: Auch eine Ziffernfolge wäre eine Zahlenfolge(wenn man Ziffern als Zahlen auffasst). Dies ist aber keine Folge (:
lg,
Daniel
PS: Mathematiker, studierst du aktuell? Ich bin Drittsemester in Jena
Edit: okay, mit der äquivalenten Formulierung für 1 <= x_i <= 9 war ich doch etwas zu opimistisch
_________________ Centaur spears can block many spells, but no one tries to block if they see that the spell is a certain shade of green. For this purpose it is useful to know some green stunning hexes. (HPMoR)
Für diesen Beitrag haben gedankt: Kha
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Sa 21.01.12 13:51
Hallo Hidden,
nein, im Moment studiere ich nicht! Bei meinem Alter wäre das auch lustig.
Mein Studium ist schon sehr sehr lange her (bis 1981).
Noch eine kurze Erklärung zum Algorithmus des obigen Programms.
Es werden unter "kpermu" alle möglichen Permutationen von n Elementen zur n/2.ten Klasse ermittelt. Dadurch sinkt die Gesamtzahl der notwendigen Tests erheblich.
Grüße
Mathematiker
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Sa 21.01.12 14:51
Anbei die überarbeitete Version.
Nun wird auch eine ungerade Anzahl von Ziffern, inkl. 0, verarbeitet. Außerdem werden nur Zahlen ausgegeben, die keine führende Null haben.
Viel Spaß beim Testen
Mathematiker
|
|
Yaddle
Hält's aus hier
Beiträge: 9
|
Verfasst: Sa 21.01.12 14:57
Ok um das ganze Problem präziser zu beschreiben. Wir haben eine Multimenge z.B. {1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9}. Jetzt werden diese Zahlen in einer beliebigen Reihenfolge aufgeschrieben und dann irgendwo in die diese Reihenfolge ein Divisionzeichen gesetzt, sodass man eine Divisionsaufgabe erhält. Jetzt ist die Frage ob diese Division zwei ergeben kann und ob man das irgendwie auf mathematischen Wege, nicht empirisch durch Brutforce, zeigen bzw. widerlegen kann. Erweitert man das Problem kann man für eine Multimenge {1,1,2,2,...,n,n} zeigen, dass man durch oben dargelegte Divisionsbildung eine Division erhalten kann, deren Ergebnis zwei beträgt.
Hoffe das war klar genug
|
|
|