schwere kombinatorikfrage... |
| 14.05.2005, 13:51 | Cache | Auf diesen Beitrag antworten » | ||
| schwere kombinatorikfrage... ich weiss das kombinatorik nicht 100%ig zu stochastik gehört aber hab es trotzdem mal hier rein gesetzt. also die sache sieht folgender maßen aus, in meinem skript steht es gibt 9099 verschiedene möglichkeiten die seitenflächen eines würfels mit drei farben zu bemalen. das ergebniss ist richtig hab nochmal nachgefragt aber ich komme nicht auf 9099. meine erste überlegung wäre einfach 3^6 gewesen aber das kann ja nicht stimmen. gibts dafür eine geschickte möglichkeit drauf zu kommen ohne jede einzelne kombinationen aufzulisten(was ewigkeiten dauert) mfg cache |
||||
| 14.05.2005, 14:00 | AD | Auf diesen Beitrag antworten » | ||
| RE: schwere kombinatorikfrage... Also 9099 sind auf jeden Fall schon mal falsch, egal in welcher Interpretationsvariante von 3 Farben. Aber zur richtigen Zahl: Sind die Seitenflächen numeriert, d.h., im Sinne von unterscheidbar? Dann stimmen deine 3^6 Varianten. Was anderes ist es, wenn die Seiten nicht unterscheidbar sind, dann sind zwei Färbungen, die bei Drehung des Würfels um eine beliebige Achse ineinander übergehen, als gleich anzusehen. Deren Anzahl ist deutlich kleiner als 3^6 und etwas schwieriger zu bestimmen. |
||||
| 14.05.2005, 14:06 | cache | Auf diesen Beitrag antworten » | ||
ich hab auch nicht verstanden wie die möglichkeiten entstehen können. bin momentan dran mit dem burnside lemma was zu probieren aber da komme ich bis jetzt auch noch nicht weiter. bist du dir ganz sicher das 9099 falsch ist? könnte auch ne fangfrage vom prof sein aber kann ich mir fast nicht vorstellen. mfg cache |
||||
| 14.05.2005, 14:11 | AD | Auf diesen Beitrag antworten » | ||
Also mal ganz vorsichtige Antwort: Wenn jede Seite einfarbig gefärbt werden soll, nur drei Farben zur Verfügung stehen, und der Würfel wie jeder normale Würfel genau sechs Seiten hat, dann sind die 9099 garantiert falsch. 
|
||||
| 14.05.2005, 14:26 | cache | Auf diesen Beitrag antworten » | ||
also davon gehe ich stark aus, das diese voraussetzungen erfüllt sind. ansonsten wäre es ein witz der unlösbar ist. da es eh freiwillig ist die aussage im skript zu bestätigen, werde ich jetzt wohl aussteigen müssen. was mich auch etwas irretiert hat war das schon paar spinner aus meinem kurs möglichkeiten über 3000-4000 hatten(durch burnside lemma) und über meine 3^6 bin ich noch nicht gekommen. hätte eigentlich darauf wetten können das 9099 stimmen muss aber vielleicht ist es ja wirklich nur ne fangfrage. ich meine mit burnside lemma sollte man die möglichkeiten rausbekommen,wenn die Seiten nicht unterscheidbar sind. und unterscheidbar wäre dann ja 3^6. werde mich jetzt noch ein bisschen mit dem burnside lemma beschäftigen, die anwendunge mit den dreifarben ist mir noch nicht ganz klar. fällt dir noch eine andere interpretation ein die er meinten könnte oder wären die beiden möglichkeiten alle? weil wenn ich alle möglichkeiten habe kann ich die aussage von ihm ja wiederlegen. sollte keiner mehr was wissen werde die antwort dann so in ca. 2 wochen hier wieder reinposten(sofern du/ihr das wollt). danke für deine hilfe schonmal. mfg cache |
||||
| 14.05.2005, 23:19 | AD | Auf diesen Beitrag antworten » | ||
Ich habe inzwischen mal nachgedacht, ob die 9099 für irgendeine Anzahl von Farben stimmen könnte - die Antwort ist Nein: Für Farben ergeben sich nämlich geordnete Färbungen des Würfels, und bei Anwendung des Burnside-Lemmas (musste mich erstmal belesen, was das besagt
) erhält man die Anzahl von ungeordneten Färbungen. Das ergibt folgende ListeVon 9099 also keine Spur... |
||||
| Anzeige | ||||
|
|
||||
| 15.05.2005, 11:55 | quan | Auf diesen Beitrag antworten » | ||
super das du die tabelle reingemacht hast. hast du zufällig im internet eine gute beschreibung des burnside lemmas gefunden? wäre nett wenn du den link posten würdest. mfg cache |
||||
| 15.05.2005, 12:13 | brunsi | Auf diesen Beitrag antworten » | ||
| antwort @quan: ich hab für dich nen link gefunden, aber ob du das verstehst weiß ich nicht. kannst ja mal reinschauen udn versuchen das nachzuvollziehen. http://www.mathe-online.at/materialien/matroid/files/sitz/sitz.html |
||||
| 15.05.2005, 13:03 | AD | Auf diesen Beitrag antworten » | ||
http://en.wikipedia.org/wiki/Burnside%27s_lemma ist kurz und prägnant, außerdem ist da exakt dein Beispiel auch drin.
In der deutschen Wikipedia ist es leider noch nicht vertreten. 
|
||||
| 15.05.2005, 13:18 | quan | Auf diesen Beitrag antworten » | ||
@brunsi: danke für den link, hatte den aber auch schon gefunden. hab den text mehr oder weniger verstanden aber sobald es interressant wird verweisst er leider auf einen englischen link. @athurdent: hab probiert deine lösung zu verstehen, aber bin nicht ganz durchgestiegen. könntest du bitte noch etwas erklären zu der formel. deine formel sieht ja folgendermassen aus: 1/24*(k^6 + 3*k^4 + 12*k^2 + 8*k^2) Die permutationengruppe des Würfels ist ja die S4 und besteht aus 24 elementen. damit wäre schonmal das 1/24 klar. gut jetzt kommt die summe der ordnung der fixpunktmenge und da fangen schon meine probleme an. ich verstehe irgendwie nicht ganz wie ich die fixpkt menge bestimmen kann und ich weiss auch nicht über welche elemente der index der summe beim würfel laufen soll. hoffe es sind nicht zu viele fragen.... mfg quan |
||||
| 15.05.2005, 13:38 | AD | Auf diesen Beitrag antworten » | ||
Hast du die einzelnen Punkte auf der Wikipedia-Seite verstanden:
Die 24 Elemente der S4 werden also in 1,6,3,8,6 aufgeteilt - ist ja beschrieben, wie (wenn ich es schnell aufmalen könnte, würde ich es tun). In diesen einzelnen Fällen gibt es 6,3,4,2,3 Freiheitsgrade zur Wahl der Farben, und damit entsprechende Potenzen von 3 für die zugeordneten Anzahlen. Und bei meinen Betrachtungen oben ist es völlig analog, nur mit k^ statt 3^ . |
||||
| 15.05.2005, 13:52 | quan | Auf diesen Beitrag antworten » | ||
also ich glaub ich bin zu blöd für die aufgabe... hab das ganze prinzip noch nicht verstanden kommt mir langsam vor. warum wird es in 1,6,3,8,6 aufgeteilt. macht für mich irgendwie keinen sinn. ich bekomme mit 90 grad nur 4 hin dann bin ich wieder bei der identität. und die 90 grad drehung und die 180 grad drehungen sind doch die gleichen???? und wie ich auf die freiheitsgrade komme ist mir auch unklar. |
||||
| 15.05.2005, 14:09 | AD | Auf diesen Beitrag antworten » | ||
Vielleicht ist es das Englisch, was dir Probleme bereitet. Die 24 "Würfelverdrehungen" können folgendermaßen klassifiziert werden: * Identität, der Würfel bleibt in seiner Lage (Anzahl=1) * Drehungen um +-90 Grad bei Draufsicht auf eine Seitenfläche (Anzahl=3*2=6) * Drehungen um 180 Grad bei Draufsicht auf eine Seitenfläche (Anzahl=3) * Drehungen um 120 Grad um eine fixierte Ecke (Anzahl=4*2=8) * Drehungen einer Kante um 180 Grad, d.h. Vertauschung ihrer Ecken (Anzahl=6) Und in jedem dieser 5 Fälle kann man sich überlegen, welche Seiten jeweils gleich gefärbt sein müssen, daraus ergeben sich die Freiheitsgrade - also Anzahl Farben, die noch gewählt werden dürfen. So kommt man auf die Anzahl der geordneten Würfelfärbungen, die der jeweiligen "Verdrehung" zugeordnet werden können. Vielleicht liegen deine Probleme aber auch grundsätzlich noch beim Verständnis des Burnside-Lemma, und nicht erst bei der Anwendung auf dieses konkrete Problem? 
|
||||
| 15.05.2005, 14:26 | quan | Auf diesen Beitrag antworten » | ||
wo die probleme liegen ist mir selber noch unklar aber glaube das es am burnside lemma liegt. hab aber jetzt im internet eine gute deutsche seite bzw. gruppentheorie skript gefunden, das ich mal durcharbeiten werde. sollte mir dann noch was unklar bleiben hoffe ich das du noch offen für fragen bist. aber danke für die ganze anstrengung. mfg quan |
||||
| 15.05.2005, 18:00 | quan | Auf diesen Beitrag antworten » | ||
nach ca. 3 stunden jetzt hab ich das bsp verstanden. hab mich auch ziemlich dumm angestellt aber für die drehungen fehlt mir einfach mein vorstellungsvermögen, mitl einen würfel zur hand ging es dann einigermassen. hab jetzt direkt noch eine fragestellung aus meinem skript probiert zu lösen, hab aber diesmal kein ergebniss dafür und deswegen bräuchte ich deine hilfe. folgende frage: wieviel möglichkeiten gibt es die kanten eines würfels mit 2 farben zu bemalen. eigentlich ja das gleiche in grün aber bin mir trotzdem sicher das ich da paar fehler drin hab. ich schreib mal meinen lösungsweg auf: i)drehungen um achse durch gegenüberliegenden seitenflächen ii).... durch gegenüberliegenden kanten iii) ... diagonalen gegen überliegenden ecken also alles wie vorher jetzt die anzahlen: i) 90grad: anzahl 3 fixmenge 0 180g: anzahl 3 fix 0 (bin ich mir nicht ganz sicher) 270g: anzahl 3 fix 0 ii)180g: anzahl 6 fix 7 ( sehr unsicher) iii)120g: anzahl 3 fix 0 (bin ich mir auch nicht sicher aber keine kante bleibt gleich) 240g: anzahl 3 fix 0 das heisst: 1/24*(2^12+6*7) naja das wird sicher falsch sein... mfg quan |
||||
| 15.05.2005, 18:48 | AD | Auf diesen Beitrag antworten » | ||
Dass das falsch ist, sieht man allein daran, dass 1/24*(2^12+6*7) = 172,4166... keine ganze Zahl ist. Die Klassifikation von oben
hilft auch hier, du musst dir jetzt eigentlich pro Fall "nur" noch überlegen, wieviele der 12 Kanten du frei färben kannst. Sind das die Anzahlen , dann folgt nach dem Burnside-Lemma unmittelbar die gesuchte Anzahl Also nimm deinen Würfel zur Hand und strapaziere noch mal dein räumliches Vorstellungsvermögen!
|
||||
| 15.05.2005, 19:09 | quan | Auf diesen Beitrag antworten » | ||
also werde es nochmal genau durchgehen aber eine frage hab ich noch vorher. .also die n1,..n5 sind doch einfach nur die fixpunktemengen. n1 bleibt alles gleich also kann ich 2^12 mal färben, da es 12 kanten gibt. n2= ist ja welche bei +-90 grad gleich bleiben. bei mir bleibt keine kante gleich(oder?) also kann ich auch keine kante frei färben.sehe ich das richtig. bei n3= 180 grad geht jede kante auf ihre gebenüberliegende kante also bleibt doch auch keine kante auf der selben stelle? wo ist da mein denkfehler drin? auch bei dem vorigen bsp war ja für 90 grad drehung(um die achse, die untere und obere seite schneidet) nur die untere und obere seite fix. wie ist man da genau auf 3^3 gekommen zum frei färben. ich dachte einfach man kann die obere und untere seite frei färben aber wo bleibt die 3? |
||||
| 15.05.2005, 19:15 | AD | Auf diesen Beitrag antworten » | ||
ist richtig: Beim "Rest" denk mal an folgendes: Jede der 24 Bewegungen kannst du eine Permutation der 12 Kanten zuordnen. Wenn du diese Permutationen in Zyklen schreibst - inklusive allerdings der 1er-Zyklen, die man sonst gern weglässt - dann entspricht die Anzahl (ja Anzahl, nicht Länge) der Zyklen der Anzahl der Freiheitsgrade, also dem . Denn alle Kanten eines Zyklus müssen gleich gefärbt sein! |
||||
| 15.05.2005, 19:28 | quan | Auf diesen Beitrag antworten » | ||
aha... verstehe zwar nicht wieso das funktioniert und weiss auch nicht ob ich dich richtig verstanden habe aber ich habs mal mit 90 grad probiert. wie ich die kanten nummeriert hab istja egal sofern es richtig ist. also in zykelschreibweise sieht es so aus: (1 2 3 4)(5 6 7 8)(9 10 11 12) sprich 3 zykel. wäre dann n1=3? und warum funktioniert das? mein hauptproblem liegt glaub ich daran das ich nicht verstanden habe in der burnside defintion was die genau mit fixmenge gemeint ist. jetzt im nachhinein ist mir auch wieder das vorige bsp unklar mit dem 3^3. wenn ich beim vorigen bsp um 90 bzw. 270 grad drehe bleiben ja 2 flächen komplett fix. wie kann ich anhand dieser 2 fixen flächen auf 3^3 kommen? hoffe es wird dir nicht zu viel arbeit... danke, quan |
||||
| 15.05.2005, 19:34 | quan | Auf diesen Beitrag antworten » | ||
ach so... wäre dann das 3^3 beim vorigen bsp der zykel (1)(2345)(6) gewesen. und deswegen die 3... jetzt glaube ich habs vestanden... |
||||
| 15.05.2005, 19:35 | AD | Auf diesen Beitrag antworten » | ||
Ich glaube, ich kann dir jetzt nicht so richtig helfen, das mit den Zyklen zu verstehen - da musst du selber noch mal in Ruhe drüber nachdenken. Bei der obigen Seitenflächenrechnung klappt das auch: Der Fall
entspricht der Flächenpermutation: (1) (2) (3456) Dabei ist 1 die Fläche, die man dreht, 2 die gegenüberliegende, und 3,4,5,6 der Rest. EDIT: Diesmal freu ich mich, dass ich mit meinem Beitrag zu spät war - Selbsterkenntnis deinerseits ist nämlich am besten! 
|
||||
| 15.05.2005, 20:25 | quan | Auf diesen Beitrag antworten » | ||
also das es am ende doch noch gut geklappt hat freut mich natürlich auch. will mich recht herzlich bei dir bedanken, war ja sicher kein leichter schüler
. hoffe auch das mir der burnside nie wieder in meinem studium über den weg läuft, hab mich den ganzen tag mit dem mist befasst und das schlimmste war das ich zuhause nichtmal einen richtigen würfel gefunden habe sondern die ganze zeit mit so einem kleinen backgammen würfel das nachgestellt hab, war kurz vor dem durchdrehn. hab jetzt auch nochmal die aufgabe zuende probiert, ist zwar noch ein fehler drin aber den such ich dann morgen.also n1=12, n2=3, n3=6, n4=7, n5=4, ergebniss ist leider wieder ein bruch. schätze das n4 falsch ist aber das regel ich morgen. naja hoffe dir nutzt der burnside mehr als mir
mfg quan |
||||
| 15.05.2005, 20:34 | AD | Auf diesen Beitrag antworten » | ||
12,3,6,7,4 habe ich auch, aber in leicht anderer Reihenfolge...
Übrigens: Nichts zu danken, ich habe ja auch was kennengelernt - das Burnside-Lemma. Was ich zwar (intuitiv) schon gekannt und benutzt habe, aber nie unter diesem Namen. |
||||
| 22.05.2005, 12:39 | Bachelor01 | Auf diesen Beitrag antworten » | ||
Hätt mal nen Vorschlag, da ihr euch recht verzweifelt den Kopf über diese Färbungen zerbrecht: Überprüft mal, ob es sich wirklich um die Färbungen eines Würfels handelt und nicht um die des Dodekaeders, denn von denen gibt es nämlich exakt die von euch gesuchten 9099 Möglichkeiten, vom Würfel gibt es allerdings lediglich 57, da werdet ihr euch schwer tun, mehr zu finden!! Hoff, ich konnte euch helfen! Lg, Bachelor01 |
||||
| 23.05.2005, 10:31 | AD | Auf diesen Beitrag antworten » | ||
Ich hatte ja auch schon andere Körper als den Würfel erwogen, habe das aber nach deutlicher Verneinung der Anfrage
nicht weiter verfolgt. Aber schön, wenn du die Zahlen des Dodekaeders so parat hast... 
EDIT: ...und die zugehörige Rechnung lautet: Also nachträglich 
für quan für seine "Würfelbestätigung". |
||||
| 23.05.2005, 20:42 | quan | Auf diesen Beitrag antworten » | ||
danke. habs letzte woche schon erfahren. war fehler vom prof.. und von alleine drauf zu kommen ist ja fast unmöglich. schätze mal bachelor hatte die lösung auch nicht nur zufällig parat
. mfg quan |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
