Viele Wissenschaftler nehmen an einer Konferenz teil. Manche unter ihnen sind befreundet. Keine zwei Wissenschaftler mit der gleichen Anzahl der Freunde haben gemeinsame Freunde. Können Sie beweisen, dass es unbedingt jemanden gibt, der nur einen bzw. keinen Freund hat?
Hi Gene,
danke für das schöne Rätsel!
Bedeutet „keinen gemeinsamen Freund“ auch, dass sie nicht untereinander befreundet sein können?
jartul
Hi Jartul,
Bedeutet „keinen gemeinsamen Freund“ auch, dass sie nicht
untereinander befreundet sein können?jartul
nein, zwei Personen können einander kennen und die gleiche Anzahl der Freunde haben. Sie haben nur verschiedene Freunde.
Viele Grüße,
Gene
Hi, wir nehmen an, alle haben mehr als 1 Freund:
es seien N Wissenschaftler. Davon haben ai je genau i Freunde.
Es gilt
2*a22 , weil keiner von ihnen einen gemeinsamen Freund haben darf. Natürlich kann a2 = 0 sein. a3 haben je genau 3 Freunde.
3*a32 - a3
usw.
…
(N-1)*aN-12 - a3 - … - aN-1
summiert man beide Seiten auf bekommt man
SUM(i=2 bis N-1,i*ai) i)
Die Summe auf der rechten Seite auf die linke Seite gebracht und zusammengefasst:
SUM(i=2 bis N-1, N*ai) i))
Bravo!
Bravo!
Meine Variante ist etwas einfacher und lautet:
Nehmen wir an, alle haben mehr als 1 Freund. Betrachten wir jetzt den Mann mit der größten Anzahl der Freunde: er hat laut Annahme mehr als 1 Freund - sagen wir, N Freunde. Diese N Freunde haben alle mehr als einen Freund laut Annahme und nicht mehr als N Freunde, weil N die größte Anzahl der Freunde ist. Sie haben alle auch verschiedene Anzahlen der Freunde, weil sie schon einen gemeinsamen Freund haben.
Also,
wir müssen N verschiedene Zahlen mehr als 1 und weniger als (N + 1) finden. Sowas gibt´s nicht und wir haben einen Widerspruch.
Gruß,
Gene
P.S. An unimportant: deine Lösung ist spitze - mathematisch korrekt und beeindruckend.
1 Like