Rätsel Zahl Freunde Summe Anzahl konferenz Wissenschaftler

Freunde

Von: , Frage gestellt am Do, 22. Jul 2004

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?

4 Antworten zu dieser Frage

1. Antwort von nach 3 Stunden 0 hilfreich

   Re: Freunde

   Hi Gene,
   danke für das schöne Rätsel!
   Bedeutet "keinen gemeinsamen Freund" auch, dass sie nicht untereinander befreundet sein können?
   
   
   jartul
   

   • Antwort von nach 4 Stunden 0 hilfreich

     Re^2: Freunde

     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
     

2. Antwort von nach 8 Stunden 1 hilfreich

   Re: Freunde

   Hi, wir nehmen an, alle haben mehr als 1 Freund:
   
   es seien N Wissenschaftler. Davon haben a_i je genau i Freunde.
   Es gilt
   2*a₂ <= N-a₂ , weil keiner von ihnen einen gemeinsamen Freund haben darf. Natürlich kann a₂ = 0 sein. a₃ haben je genau 3 Freunde.
   3*a₃ <= N-a₂ - a₃
   
   usw.
   .....
   
   (N-1)*a_N-1 <= N -a₂ - a₃ - ... - a_N-1
   
   summiert man beide Seiten auf bekommt man
   
   SUM(i=2 bis N-1,i*a_i) <= (N-2)*N - SUM(i=2 bis N-1,(N-i)*a_i)
   
   Die Summe auf der rechten Seite auf die linke Seite gebracht und zusammengefasst:
   
   SUM(i=2 bis N-1, N*a_i) <= (N-2)*N
   
   N aus der Summe herausgezogen und links und rechts durch N dividiert folgt:
   
   SUM(i=2 bis N-1, a_i)) <= (N-2)
   
   die linke Seite der Summe ist aber gerade exakt gleich N
   
   Widerspruch!
   
   grüße
   
   unimportant 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?
   

   • Antwort von nach einem Tag 1 hilfreich

     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.
     

Keine passende Antwort gefunden? Jetzt eigene Frage stellen!