Singles und Paare prosten einander zu ... Graphentheorie? Kombinatorik?

XFame

Wenn man das konsequent weiter macht, was du angefangen hast, kommt man auch auf eine Loesung.

Christoph

SideWinder schrieb:

Das habe ich ja geschrieben:

f(n) = n-1 + n-2 + n-3 + ... + 1 + 0 Mal

Man kann es noch hübsch in eine arithmetische Reihe verpacken, aber imho ist daran nicht viel zu rütteln, oder?

Genau, das sagt dir, wie oft angestoßen wird. Jetzt müsstest du rausfinden, wieviele Personen man braucht, damit mindestens 100 Mal angestoßen wird (durch das Bilden von Paaren wird diese Zahl nur kleiner, deswegen "mindestens").

In Pseudo-Code könnte das z.B. so aussehen:
find (\n -> sum [1 .. n-1] >= 100) [2..]

Wenn du die Lösung hast, musst du nur noch beweisen, dass die Lösung eindeutig ist (das gehört auch dazu).

volkard

SideWinder schrieb:

Auf einer Party befinden sich Paare und Singles. Alle trinken ein Glas Sekt. Jeder Gast stößt mit jedem anderen Gast mit Ausnahme seiner Partnerin/seines Partners an (Singles stoßen also mit allen anderen Gästen an). Insgesamt wird 100 mal angestoßen. Wieviele Personen und wieviele Paare sind auf dieser Party.
AnzPersonen = 2 * AnzPaare + AnzSingles

n ... AnzPersonen
P ... AnzPaare
p ... AnzPaare * 2
s ... AnzSingles

Anstoßen von Singles:
1. Single: n-1 Mal
2. Single: n-2 Mal
usw.

S1: Summe von i=1 bis s: (n-i)

Anstoßen von Paaren:
Jeweils zwei p würden n-2 Mal anstoßen, aber sie haben schon mit allen Singles angestoßen, sie müssen also nur noch mit anderen p anstoßen.

S2: 2 * Summe i = 1 bis (n-s)/2: (n-s-2i)

100 = S1 + S2
Und nun?

MfG SideWinder

ich mach mal
n ... AnzPersonen
P ... AnzPaare
p ... AnzPartner = AnzPaare * 2
s ... AnzSingles

und ich lasse jede paarung zweimal anstoßen.
jeder single stößt mit n-1 leuten an
jeder partner stößt mit n-2 leuten an

macht
s*(n-1)+p*(n-2)=200

macht nach wenigen umformungen

s^2 + (2*p-1)*s + (p^2-2*p-200) = 0

pq-formel

s = -(2*p-1)/2 + sqrt((4*p+801)/4)

da s ganzzahlig sein soll, muß

801+4*p eine quadratzahl sein

sqrt(801)=28.3019...

29^2=841

jo, trifft schon. also p=10

nächste möglichkeit

31^2=961, also p=40 sprengt schon ren rehmen, weil die partner allein schon zu oft anstoßen.

p=10 würde ich sagen. sogar eindeutig. nur finde ich das gerechne nicht gerade hübsch.

XFame

Ich geb mal einen Tipp: Die Loesung fuer die Anzahl der Personen sollte zwischen 10 und 25 liegen. Die Anzahl der Singles betraegt zwischen 1/4 und 3/4 von der Anzahl aller Personen.

/edit: Wort vergessen...

SideWinder

Eure Posts klingen allesamt nach "ausprobieren und dann beweisen, dass es die einzig Lösung ist"?

MfG SideWinder

XFame

Nein, so meinte ich das eben nicht. Das sollte nur ein Hinweis sein, der nicht alles verraet. Mach doch mal bei S1 + S2 = 100 weiter.

volkard

SideWinder schrieb:

Eure Posts klingen allesamt nach "ausprobieren und dann beweisen, dass es die einzig Lösung ist"?

ja. unter einbeziehung der negativen zahlen gips nämlich tierisch viele lösungen, zum beispiel
s:-10000 p:9900
s:-9799 p:9700
s:-9799 p:9900
s:-9600 p:9502
s:-9600 p:9700
...
da hab ich dann nicht mehr versucht, noch eine aussage zu finden, die ohne probieren auskommt, sondern hab nur das probieren getunt.

Ähnlicher Lösungsweg wie Volkard, nur vielleicht etwas hübschere Formeln:

Es gibt n Gäste, darunter p Paare.
Wäre p=0, wird (n-1) + (n-2) + ... + (n-n) mal angestoßen.
Umformen:
(n-1) + (n-2) + ... + (n-n) = n^2 - ( 1 + 2 + ... + n) = n^2 - n(n+1)/2 = n(n-1)/2 mal angestoßen.

Aus n(n-1)/2 >= 100 und n>0 folgt n >= 15.

Sind p Paare da, wird p mal weniger angestoßen, also n(n-1)/2 - p mal.

Setzen wir n=15 ein, erhalten wir 105 - p = 100, also p = 5.
Setzen wir n=16 ein, erhalten wir 120 - p = 100, also p = 20. -> geht nicht, weil es nicht mehr Paare geben kann als Leute.

Da n(n-1)/2 für n > 1/2 streng monoton steigend ist, gibt es keine weitere, sinnvolle Lösung.

volkard

cool
so ist es schon fast zu einfach.

SideWinder schrieb:

Eure Posts klingen allesamt nach "ausprobieren und dann beweisen, dass es die einzig Lösung ist"?

MfG SideWinder

Daran ist doch nichts falsches. Schau dir z.B. mal die Determinante an, dort werden normal Axiome an eine Determinantenfunktion postuliert und kurz darauf wird bewiesen, dass die Determinantenfunktion eindeutig ist und direkt hinterher wird nachgerechnet, dass die Leibnizformel die Axiome erfüllt.
Ist ganz normal, dass man ausprobiert und danach dann beim Aufschreiben alles vom Himmel fallen lässt. Lösung raten und dann nachrechnen ist vollkommen legitim