Entwickler-Ecke :: Thema anzeigen - Beweis zu einer Multimengen-Aufgabe gesucht

Yaddle - Fr 20.01.12 17:55
Titel: Beweis zu einer Multimengen-Aufgabe gesucht

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 - Fr 20.01.12 18: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".

Martok - Fr 20.01.12 20:22

Das wichtigste vorneweg: das ist keine Zahlenfolge, sondern eine Menge! Wichtiger Unterschied :zwinker:
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 user defined image

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=10
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:

Man sieht, nur 2 Paare davon sind wirklich möglich.

Viele Grüße,
Martok

Yaddle - Fr 20.01.12 22:21

Also eine mathematische Lösung wäre mir lieber als so ein empirisches Schleifen-Wirr-Warr :D Ä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 - Sa 21.01.12 00: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.

Th69 - Sa 21.01.12 11:53

Hallo Martok,

streng mathematisch handelt es sich dabei aber auch um keine Menge [http://de.wikipedia.org/wiki/Menge_%28Mathematik%29] (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 [http://de.wikipedia.org/wiki/Abz%C3%A4hlende_Kombinatorik] (in diesem Fall: Variation ohne Zurücklegen), und dort heißt es dann einfach "Anordnung von Objekten".

Mathematiker - Sa 21.01.12 12: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 - Sa 21.01.12 13: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 - Sa 21.01.12 14:03

Yaddle hat folgendes geschrieben :

Also wäre echt toll, wenn jemand eine Antwort wüsste.

Auf welche Frage?

Yaddle hat folgendes geschrieben :

Ich habe mir schon den Kopf zermartert :(Grüße :)

Bei der Formulierung der Aufgabenstellung und der Beantwortung meiner Frage, nach welcher Bildungsvorschrift Du / Ihr "daraus zwei zahlen bilden" soll(s)t, sicher nicht.

Ralf Jansen - Sa 21.01.12 14: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.

Mathematiker - Sa 21.01.12 14: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!

Delphi-Laie - Sa 21.01.12 14:19

Martok hat folgendes geschrieben :

Das wichtigste vorneweg: das ist keine Zahlenfolge, sondern eine Menge! Wichtiger Unterschied :zwinker:

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 - Sa 21.01.12 14: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 :P

Mathematiker - Sa 21.01.12 14: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

Yaddle - Sa 21.01.12 15: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 ;)

Mathematiker - Sa 21.01.12 16:13

Yaddle hat folgendes geschrieben :

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.

Hallo Yaddle,
kann man, vielleicht nicht heute, aber irgendwann in der Zukunft schon.
Bei den ursprünglichen Zahlen (2,2,3,3,4,4,5,5) ging es noch problemlos.
Allerdings: Deine allgemeine Frage bis zu einem beliebigen n bedarf wesentlich mehr Anstrengungen und dürfte auch nicht so schnell zu lösen sein.
Ich vermute sogar (kann das aber nicht beweisen), dass diese Aufgabe einer Semesterarbeit eines fortgeschrittenen Mathematikstudenten würdig wäre.
Ich blende mich aus dem Thema aus und versuche viel lieber die Riemannsche Vermutung zu beweisen. :D

Mit freundlichen Grüßen
Mathematiker

Blup - Fr 27.01.12 11:36

Hallo,
ich habe die Aufgabenstellung so verstanden:
- eine Menge mit den Ziffern 1..n, (n >= 1) und (n <= 9)
- keine Lücken in der Ziffernfolge
- jede Ziffer kommt doppelt vor

Dazu diese Überlegungen:
Der Quotient soll 2 sein, damit kann der Divident maximal eine Stelle länger sein als der Divisor.
Da die Anzahl der Ziffern gerade ist, muss der Divident genauso viele Stellen haben wie der Divisor.

Quelltext

1:
2:
3:
4:
5:

(a(0) * 10^0 + a(1) * 10^1 + .. + a(n) * 10^n)
/
(b(0) * 10^0 + b(1) * 10^1 + .. + b(n) * 10^n)
=
2

Für a(n) und b(n) gilt jeweils genau eine dieser Bedingungen:

Quelltext

1:
2:
3:
4:

a(n) = b(n) * 2
a(n) = b(n) * 2 - 10                             {gilt nicht für n = nmax}
a(n) = b(n) * 2 + 1       {gilt nicht für n = 0}
a(n) = b(n) * 2 - 10 + 1  {gilt nicht für n = 0} {gilt nicht für n = nmax}

Dafür habe ich ein kleines Testprogramm geschrieben.
1..1: -
1..2: eine Lösung
1..3: -
1..4: -
1..5: -
1..6: -
1..7: -
1..8: 6192 Lösungen
1..9: 59112 Lösungen

Interessant ist, bis auf die Ausnahme 22/11 sind Divident und Divisor immer durch 3 teilbar.

mandras - Fr 27.01.12 16:05

Mathematiker hat folgendes geschrieben :

Vielen Dank an Mitmischer 1703!
Das ist ja wohl eine bodenlose Frechheit von Yaddle, uns hier im Forum für ihn(!) die aktuelle Bundeswettbewerbaufgabe lösen zu lassen.

Strafverschärfend: die originale Aufgabenstellung dortwar immerhin klar und präzise

Moderiert von Martok: Beiträge zusammengefasst

gut, war ganz nett. kleine denksportaufgabe.
müßte er sich aber auch selber herleiten können ohne weitere hilfe.

Hidden - Fr 27.01.12 21:53

Hallo ihr,

dass uns das erst jetzt auffällt :wall:. Naja, ich habe einmal mit der Aufgabenstellung von hier [http://www.mathe-wettbewerbe.de/bwm/bwm-wettbewerb-aktueller-lauf] verglichen und da ist die Aufgabe für 1,1, ... 9,9 gestellt. user profile icon

Yaddle fragte zunächst nur explizit nach dem Fall 1,1, ... 5,5.

Ich würde also mal nicht unterstellen, dass er damit (methodische) Tipps für den BWM wollte oder davon wusste. Klingt eher so, als hätte ihr Lehrer die Aufgabe für sie vereinfacht. ;)

user profile icon

Yaddle: Nach Einsendeschluss findest du auf der BWM-Seite dann eine schöne Lösung zu dem Problem :)

Edit: Weiter unten [http://www.delphi-forum.de/viewtopic.php?p=657561#657561] kommt dann aber doch nochmal weitgehend die selbe Formulierung. Schade! :|

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!