Idee der Rekursen: Wie viele Händeschüttelungen gibt es insgesamt?

Question

Aufgabe:

Es treffen sich n Personen. Jede schüttelt jeder anderen die Hand. Wie viele Händeschüttelungen gibt es insgesamt?

Problem/Ansatz:

Ich soll hier die Idee der Rekursiv verwenden.

Answer 1

Lösung: n*(n-1)/2 = (n^2-n)/2

https://www.mathelounge.de/234569/einer-party-personen-schuttelt-jedem-werden-hande-geschuttelt

vgl:

https://de.wikipedia.org/wiki/Gau%C3%9Fsche_Summenformel

Comments

Danke schonmal.

Könntest du mir dein Rechenweg erklären?

LG

Answer 2

Rekursiv

1 Person -- 0 Händeschütteln

2 Personen -- 1 Händeschütteln

3 Personen -- 3 Händeschütteln

4 Personen -- 6 Händeschütteln

5 Personen -- 10 Händeschütteln

n Personen -- a(n) = a(n - 1) + (n - 1)

Also wenn n - 1 Leute im Raum sind dann schüttelt erstmal jeder jedem die Hand. Eine Neue Person die den Raum betritt muss also n - 1 Leuten die Hand schütteln damit jeder jedem die Hand geschüttelt hat.

Ist das so verständlich?

Answer 3

Aloha :)

Stell dir vor, alle \(n\) Personen stehen in einer Reihe nebeneinander.

Nun geht die erste Person aus der Reihe los und schüttelt den \((n-1)\) anderen die Hand.

Danach geht die zweite Person aus der Reihe los und schütteln den \((n-2)\) anderen die Hand.

Danach geht die dritte Person aus der Reihe los und schütteln den \((n-3)\) anderen die Hand.

Die letzten 2 Personen ergeben ein Händeschütteln.

Die letzte Person schüttelt sich nicht selbst die Hand.

Du merkst, wie das funktioniert...

Mit der \(n\)-ten Person kommen \((n-1)\) Händeschüttelungen dazu.

Die Anzahl \(H\) der Händeschuttelungen bei \(n\) Personen beträgt daher als Rekrusionsformel:$$H(n)=H(n-1)+(n-1)\quad;\quad H(1)=0\quad;\quad n\ge2$$

Du kannst die Anzahl der Händeschüttelungen aber auch direkt ausrechnen::$$H(n)=(n-1)+(n-2)+(n-3)+\ldots+1=\pink{\frac{n^2-n}{2}}$$

Die pinke Summenformel ist auch als "Gauß-Formel" bekannt.