Anzahl mgl. Bitwörter < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 01:45 Do 10.12.2009 | | Autor: | dayscott |
| Aufgabe 1 | | wieviele Zahlen 1..1000015 gibt es, die die Quersumme 15 haben? |
| Aufgabe 2 | | Wieviele Binärwörter der Länge n gibt es, so dass die Folge '00' genau 2x enthalten ist? (die Folge 000 enthält die 00 2x ) |
hallo liebe matheraum Gemeinde, meine Ansätze lauten wie folgt:
Aufg1: Mit einem kleinen Code Stück habe ich das Problem bruto force gelöst, aber das ist nicht Sinn der Aufgabe ^^ - weis aus mathematischer Sicht nicht, wie ich rangehen soll :(
Aufg2: Wenn n= 5 ist, dann ist die Lsg 2, nämlich: 10000 10001 (ich nehme an 0100 ist keine 4 stellige sondern eine 3 stellige Bitfolge)
aber auch hier sehe ich nicht ganz wie ich mit dem abstrakten n umgehen soll. Mit größerem n wächst ja die Anzahl der möglichen Bitwörter...
|
|
| |
|
Hallo,
zur ersten Aufgabe hätte ich einen Ansatz. Zähle doch erstmal die Möglichkeiten um mit 6 Ziffern (0-9) die Summe 15 zu bilden. Nun musst du nur noch wissen wie viele Variationen dieser Möglichkeiten jeweils existieren. Beispiel:
15=0+0+0+0+6+9
Das wäre jetzt eine Variation. Wie viele gibt es? 6*5=30 Stück.
Die weiteren Zerlegungen von 15 musst du halt erstmal aufschreiben - das ist etwas Arbeit - macht aber nichts...
Wenn du dann alles addierst, bist du fertig. Unter den 7stelligen Zahlen gibt es keine mehr mit der Quersumme 15.
Viel Erfolg,
Roland.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:27 Do 10.12.2009 | | Autor: | dayscott |
wie kommst du auf genau 6 ziffern ?
|
|
|
| |
|
Hallo,
vielleicht hab ich auch die Aufgabe falsch verstanden, aber die größte Zahl der zu untersuchenden Zahlen ist doch 1000015, oder? Die hat 7 Ziffern. Da keine 7stellige Zahl (mit 1 am Anfang) existiert, die kleiner gleich 1000015 und deren Quersumme 15 ist, kann man auch gleich alle 6stelligen Zahlen betrachten.
Viel Erfolg,
Roland.
|
|
|
| |
|
Hallo dayscott,
> Wieviele Binärwörter der Länge n gibt es, so dass die
> Folge '00' genau 2x enthalten ist? (die Folge 000 enthält
> die 00 2x )
> Aufg2: Wenn n= 5 ist, dann ist die Lsg 2, nämlich: 10000
> 10001 (ich nehme an 0100 ist keine 4 stellige sondern
> eine 3 stellige Bitfolge)
Dazu zweierlei:
Zum einen würde ich nicht die Annahme treffen, dass 0100 eine dreistellige Bitfolge ist, obwohl sich die Lösung gar nicht so wesentlich verändert (Indexverschiebung um 1). n-stellige Bitfolgen sollten aber [mm] 2^n [/mm] Möglichkeiten haben. Mit Deiner Festlegung müsste eine Bitfolge immer mit einer 1 beginnen, das scheint mir nicht sinnvoll.
Zum andern stimmen Deine Lösungen nicht. Beachte mal den Tipp aus der Aufgabenstellung. Demnach wäre auch 11000 eine Lösung, 10000 aber nicht - denn nach der Zählung des Aufgabenstellers kommt darin dreimal die Folge 00 vor (beginnend an der 2., 3. oder 4. Stelle).
Allgemein können Lösungen ja nur zwei mögliche Formen haben: entweder sie enthalten die Folge 000 und bestehen sonst aus Einsen, oder sie enthalten zweimal die Folge 00, aber mit mindestens einer Eins dazwischen.
Der erste Fall ist sehr leicht zu bestimmen, der zweite nicht ganz so. Für n=5 bietet er nur eine Lösung, für n=6 drei, für n=7 sechs Lösungen, für n=8 zehn Lösungen...
Ach so: Lösungsangaben auf der Grundlage beliebiger Bitfolgen, also auch solcher, die mit Null(en) beginnen.
Kommt Dir diese Zahlenfolge (1,3,6,10...) bekannt vor? Wenn ja, kannst Du begründen, warum sie hier anwendbar ist?
Wenn nein, findest Du ihre Bildungsvorschrift (am liebsten nicht-rekursiv)?
lg
reverend
|
|
|
| |
|
Also ich muss ja leider sagen, dass die Lösung die jetzt gegeben worden ist inkorrekt ist. Und zu noch größerem Bedaueren muss ich sagen dass ich die richtige Lösung auch nicht weiß.
Falsch daher da die Annahme dass das Bitwort sonst nur aus 1en besteht nicht mit der Angabe übereinstimmt.
Das Bitwort (bei n = 8) 10010010 ist wohl zweifellsfall ein zulässiges wird aber von der Lösung von reverend außer acht gelassen.
Genauso wie: 10001010,10001110,10001011,....
Vielleicht hat noch jemand eine Idee wie man auf die Lösung kommen könnte?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:34 Sa 12.12.2009 | | Autor: | reverend |
Hallo blublublub,
> Falsch daher da die Annahme dass das Bitwort sonst nur aus
> 1en besteht nicht mit der Angabe übereinstimmt.
>
> Das Bitwort (bei n = 8) 10010010 ist wohl zweifellsfall ein
> zulässiges wird aber von der Lösung von reverend außer
> acht gelassen.
Da hast Du ohne Zweifel Recht. Aber dann weißt Du doch auch, wie Du jetzt zur richtigen Lösung kommst, oder?
lg
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:20 Mo 14.12.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:42 So 13.12.2009 | | Autor: | dayscott |
"Kommt Dir diese Zahlenfolge (1,3,6,10...) bekannt vor? "
nein leider nicht - kannst du das näher erläutern?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:47 So 13.12.2009 | | Autor: | Loddar |
Hallo dayscott!
Das sind die Summen der ersten n natürlichen Zahlen:
[mm] $$s_1 [/mm] \ = \ 1$$
[mm] $$s_2 [/mm] \ = \ 1+2 \ = \ 3$$
[mm] $$s_3 [/mm] \ = \ 1+2+3 \ = \ 6$$
etc.
Diese Folge kann man auch abgekürzt schreiben mit:
[mm] $$s_n [/mm] \ = \ 1+2+3+...+n \ = \ [mm] \summe_{k=1}^{n}k [/mm] \ = \ [mm] \bruch{n*(n+1)}{2}$$
[/mm]
Gruß
Loddar
|
|
|
| |
|
unabhängig von mir wurde die Aufgabe hier gepostet: http://www.matheplanet.com/matheplanet/nuke/html/viewtopic.php?topic=133191
(ist ne aktuelle HA in einer großen Uni in München)
die Aufgabe scheint etwas schwerer zu sein als anfangs gedacht - aber die Idee die dort genannt wird ist gut:
Es gibt 2 Gruppen:
entweder es kommt im Bitstring 1000 vor, dann haben wir was wir brauchen oder es kommt 2x 100 100 vor, dann haben wir auch was wir brauchen, - die genau formel steht im anderen forum. was haltet ihr von dem drübigen Lösungsvorschlag?
|
|
|
| |
|
Hallo dayscott,
das sieht ganz gut aus, scheint mir aber auch noch nicht die vollständige Lösung zu sein. Will heißen: die erste (beginnend mit dem Programm) sieht mir vertrauenswürdiger aus als die später folgende kombinatorische Herleitung, die ja auch ein anderes Ergebnis liefert.
Du hast Recht, dass die Aufgabe deutlich komplizierter ist, als ich sie anfangs gesehen habe. Ich verfolge gerade einen anderen Ansatz, komme aber heute nicht dazu, ihm Zeit zu widmen.
Ich suche drei Werte:
[mm] m_l(n): [/mm] Zahl der Bitfolgen ohne Doppelnull, die links von einer solchen stehen dürfen
[mm] m_m(n): [/mm] Zahl der Bitfolgen ohne Doppelnull, die zwischen zwei solchen stehen dürfen
[mm] m_r(n): [/mm] Zahl der Bitfolgen ohne Doppelnull, die rechts von einer solchen stehen dürfen
Klar ist, dass [mm] m_l [/mm] auf 1 enden und [mm] m_r [/mm] mit einer 1 beginnen muss, [mm] m_m [/mm] sogar beides.
Auch klar ist [mm] m_l(n)=m_r(n), [/mm] es genügt, die Bitfolgen zu spiegeln.
Nun zeichne ich mir einen Baum, der frei von Doppelnullen ist, und versuche so, ein Bildungsprinzip für [mm] m_l(n) [/mm] und [mm] m_m(n) [/mm] zu ermitteln.
[Dateianhang nicht öffentlich]
Wenn ich das habe (und das sieht ja nicht schwer aus), bin ich aber leider immer noch nicht auf dem einfachsten Weg. Weiter gehts ja dann mit der Ermittlung der Möglichkeiten, wie diese Folgen um die Doppel- oder Dreifachnullen zu verteilen sind.
Der Ansatz sieht darum noch zu kompliziert aus, ist aber systematisch lösbar. Alle anderen Ansätze, die ich sehe, sind das nicht und sind daher auch nicht zielführend.
Mal sehen, ob jemand eine bessere Idee hat oder aus dieser etwas machen kann.
Die Frage bleibt also halboffen.
Viel Erfolg!
reverend
Dateianhänge:
Anhang Nr. 1 (Typ: PNG) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:20 Mi 16.12.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
