Doppeltes Abzählen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | 1.In einer Vorlesung sitzen 70 Studenten und n Studentinnen. Jeder Student kennt genau 7 Studentinnen aus der Vorlesung, während jede Studentin genau 10 Studenten aus der Vorlesung kennt. Berechnen Sie mittels "doppelten Abzählen", wieviele Studentinnen in der Vorlesung sitzen (beachten Sie , dass die Relation "a kennt b" symmetrisch ist.
2.Die Studenten eines Studienganges müssen drei Kurse besuchen, die sie aus einem Angebot von 5 Kursen auswählen können. In den Kursen 1,2,3,4 und 5 befinden sich 13,32,37,40 und 15 Studenten. Was können Sie daraus schließen? (Selbstverständlich besucht keiner der Studenten mehr als 3 Kurse) |
Hallo erstmal, und schon mal vielen Dank für die hilfe...
nun hab ich das Problem, dass ich nicht weiß wie ich das angehe, daher würde ich gerne mögliche Rechenschritte und allgemeine Lösungshinweise (für andere der artige Aufgaben)
schön wäre natürlich auch die Lösung ;)
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:11 Di 29.04.2008 | | Autor: | felixf |
Hallo
> 2.Die Studenten eines Studienganges müssen drei Kurse
> besuchen, die sie aus einem Angebot von 5 Kursen auswählen
> können. In den Kursen 1,2,3,4 und 5 befinden sich
> 13,32,37,40 und 15 Studenten. Was können Sie daraus
> schließen? (Selbstverständlich besucht keiner der Studenten
> mehr als 3 Kurse)
Kann es sein, dass du dich evtl. vertippt hast? Ansonsten wuerde meine Antwort lauten: ``Ich kann daraus schliessen, dass mindestens eine der Aussagen falsch ist.''
LG Felix
|
|
|
| |
|
> Hallo
>
> > 2.Die Studenten eines Studienganges müssen drei Kurse
> > besuchen, die sie aus einem Angebot von 5 Kursen auswählen
> > können. In den Kursen 1,2,3,4 und 5 befinden sich
> > 13,32,37,40 und 15 Studenten. Was können Sie daraus
> > schließen? (Selbstverständlich besucht keiner der Studenten
> > mehr als 3 Kurse)
>
> Kann es sein, dass du dich evtl. vertippt hast? Ansonsten
> wuerde meine Antwort lauten: ''Ich kann daraus schliessen,
> dass mindestens eine der Aussagen falsch ist.''
>
> LG Felix
ich hab gerade noch mal nachgeschaut, aber nein , ich hab nichtmal einen Tippfehler (zumindest gesehen)... solltest du im bezug auf die anzahl der Teilnehmer ansprechen, die aufgabe bezieht sich nicht auf die oben genannte aufgabe 1 sondern, sie soll scheinbar irgendwie mit "doppeltem Abzählen" zu tun haben , aber wie kommst du auf die Aussage ist falsch?
bzw. du hast recht, wenn man die summe addiert und dann durch 3 dividiert kommt man nicht auf eine [mm] \IN, [/mm] was man ja müsste... aber da werde ich nochmal Nachfragen....
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:48 Di 29.04.2008 | | Autor: | felixf |
Hallo
> > > 2.Die Studenten eines Studienganges müssen drei Kurse
> > > besuchen, die sie aus einem Angebot von 5 Kursen auswählen
> > > können. In den Kursen 1,2,3,4 und 5 befinden sich
> > > 13,32,37,40 und 15 Studenten. Was können Sie daraus
> > > schließen? (Selbstverständlich besucht keiner der Studenten
> > > mehr als 3 Kurse)
> >
> > Kann es sein, dass du dich evtl. vertippt hast? Ansonsten
> > wuerde meine Antwort lauten: ''Ich kann daraus schliessen,
> > dass mindestens eine der Aussagen falsch ist.''
>
> ich hab gerade noch mal nachgeschaut, aber nein , ich hab
> nichtmal einen Tippfehler (zumindest gesehen)... solltest
> du im bezug auf die anzahl der Teilnehmer ansprechen, die
> aufgabe bezieht sich nicht auf die oben genannte aufgabe 1
> sondern, sie soll scheinbar irgendwie mit "doppeltem
> Abzählen" zu tun haben , aber wie kommst du auf die Aussage
> ist falsch?
> bzw. du hast recht, wenn man die summe addiert und dann
> durch 3 dividiert kommt man nicht auf eine [mm]\IN,[/mm] was man
> ja müsste... aber da werde ich nochmal Nachfragen....
Genau das meine ich 
Was das ganze mit dem doppelten Abzaehlen zu tun hat:
Wenn du eine $5 [mm] \times [/mm] n$-Matrix nimmst, $n$ die Anzahl der Studenten (gesucht), und in dem $(i, j)$-Eintrag eine 1 hast wenn Student $j$ den Kurs $i$ besucht und 0 sonst, dann ist die Summe ueber alle Eintraege in der $i$-ten Zeile gerade die Anzahl der Leute die den Kurs $i$ besuchen. Und die Summe ueber die $j$-te Spalte ist die Anzahl der Kurse, die Student Nr. $j$ besucht, also hier 3.
Insgesamt hast du also $n [mm] \cdot [/mm] 3$ Eintraege ungleich 0, womit die Summe ueber alle Eintraege $n [mm] \cdot [/mm] 3$ ist. Gleichzeitig ist sie aber auch die Summe der Teilnehmer der Kurse...
(Diese Erklaerung hilft dir jetzt vielleicht auch Aufgabe 1 zu loesen: es heisst uebrigens doppeltes Abzaehlen weil man einmal zuerst ueber die Zeilen summiert und dann die Zeilensummen zusammenaddiert, und einmal zuerst ueber die Spalten summiert und dann die Spaltensummen zusammenaddiert -- beide male muss das gleiche herauskommen, aber oft bekommt man so die noetige Information die man zum Ausrechnen einer Unbestimmten braucht.)
Deswegen muesste die Summe halt durch 3 teilbar sein, und da sie es nicht ist, muss irgendeine Aussage (etwa: jeder Student besucht genau drei Kurse, oder: Kurs x hat y Teilnehmer) falsch gewesen sein...
LG Felix
|
|
|
| |
|
also gut....
ich kann so ziemlich alles mit ner Matrix machen, AUßER eine selbst erstellen... könntest du mir am Beispiel der ersten Aufgabe erklären, wie ich das machen müsste? Bzgl. Was setz ich wo hin, woher weiß ich, dass es horizontal und nicht vertikal geschrieben wird? wäre echt super....
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 02:24 Do 01.05.2008 | | Autor: | Zneques |
Hallo,
Die Matrix hat 70 Zeilen (für jeden Studenten eine) und n (noch unbekannt viele) Spalten.
In der x-ten Zeile (also der von Student x) steht in Spalte y eine 1, wenn er die Studentin y kennt.
Somit gibt es pro Zeile 7x "1".
Wieviele sind das insgesammt ?
Wenn pro Spalte genau 10x "1" stehen, wieviele Spalten gibt es dann ?
Ciao.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:17 Do 01.05.2008 | | Autor: | koepper |
Hallo zusammen,
nur für Interessierte:
Solche Situationen sind (auch in allgemeinerem Kontext) sehr schön graphentheoretisch modellierbar.
Zu 1 betrachte man einen Graphen, dessen Knoten aus allen Studenten und Studentinnen besteht. Wenn jede "Kennt-Beziehung" nun durch eine Kante zwischen einem Studenten und einer Studentin modelliert wird, ist dieser Graph bipartit (das heißt, die Knotenmenge ist so in 2 Teilmengen zerlegbar, daß jede Kante einen Knoten der einen Teilmenge mit einem Knoten der anderen Teilmenge verbindet). Für bipartite Graphen gilt aber stets, daß die Summe der Knotengrade (=Anzahl der mit einem Knoten verbundenen [=inzidenten] Kanten) für die beiden Teilmengen jeder bipartiten Zerlegung gleich ist.
In dem Graphen zu 1 haben wir offenbar 490 Kanten.
LG
Will
PS: Eine Situation aus verschiedenen Blickwinkeln zu betrachten ist für einen Anfänger verwirrend, für Fortgeschrittene ist es jedoch erleuchtend, weil so Beziehungen zwischen ehemals vermeintlich getrennten Gebieten sichtbar werden. In allen Aspekten dieser Schöpfung treffen wir doch immer wieder auf die selben Strukturen und Funktionsprinzipien. Diese "Handschrift Gottes" in der Schöpfung zu erkennen und zu verstehen, ist die Aufgabe des Mathematikers, die mich immer wieder mit großer Freude und auch großem Respekt erfüllt.
|
|
|
|
