Aufgabe:
Auf einer Feier macht ein Fotograf Bilder von Gästen, die sich die Hand geben. Nach der Feier ist leider die Teilnehmerliste verschwunden. Aus der Anzahl der Bilder soll errechnet werden, wie viele Personen mindestens anwesend gewesen sein müssen.
Auf jedem Bild sind immer nur zwei Personen zu sehen, die sich die Hand geben. Von jedem Personenpaar gibt es nur ein Bild. Eine Person kann aber natürlich auf mehreren Fotos zu sehen sein und dabei unterschiedlichen Personen die Hand geben.
Problem/Ansatz:
Die Aufgabe sollte programmiererisch gelöst werden.
Mein Ansatz war dieser:
anzahl_bilder = n
teilnehmer = 1
maximale_handshakes = 0
while maximale_handshakes < anzahl_bilder:
maximale_handshakes += teilnehmer (erhöhe maximale_handshakes um die anzahl der teilnehmer)
teilnehmer += 1 (erhöhe teilnehmer um 1)
return teilnehmer
es wird also beginnend mit 1 teilnehmern ermittelt, wie viele mögliche "handshakes"/bilder möglich sind und das gleiche für 2, 3, 4, 5, ... t Teilnehmer getan. So lange, bis die Anzahl an Teilnehmern es erlaubt, dass m "handshakes" bzw. Bilder möglich sind.
Ich habe nach der Lösung etwas recherchiert und im Grunde entspricht dies wohl der Gaußschen Summenformel da hier letztlich alle Zahlen von 1 bis t summiert werden.
Die Formel lautet ja bekanntlich:
$$\frac{n*(n+1)}{2}$$
Nun habe ich ein paar andere Lösungen zu dem Problem gesehen und eine hat mich etwas verwirrt und zwar folgende:
anzahl_bilder = n
teilnehmer = aufgerundet($$1/2 +(-) \sqrt{(8*anzahlbilder + 1)/4}$$)
Die Lösung wurde so erklärt:
Der erste Teilnehmer kann maximal mit t-1 Personen fotografiert worden sein. Die zweite Person mit t-2 Personen etc. Daher können t Personen maximal t*(t-1)/2 fotografiert worden sein.
$$n = \frac{t*(t-1)}{2}$$
Stellt man die Gleichung dann nach dem gesuchten t um erhält man:
$$1/2 +(-) \sqrt{(8*anzahlbilder + 1)/4}$$
Die Erklärung kann ich inhaltlich nachvollziehen und es fällt natürlich auf, dass hier eine ganz ähnliche Formel entsteht, wie bei der Gaußschen Summenformel.
$$n = \frac{t*(t-1)}{2}$$
Allerdings haben wir hier ja ein umgekehrte vorzeichen. Statt n*(n+1) haben wir ja t*(t-1)
Was sich mir jetzt nicht erschließen will ist, warum beide Formeln trotzt unterschiedlichen Vorzeichen zum gleichen Ergebnis kommen können?
