| Autor |
Beitrag |
    
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Montag, den 29. Juli, 2002 - 11:14: | 
|
Bei einer Spielshow konnte das Sieger-Team die Höhe des Gewinnes selbst beeinflussen. Die 10 Spieler trugen T-Shirts mit den Nummern 1 bis 10. Nun mussten sie sich innerhalb einer Minute in beliebiger Reihenfolge an einen runden Tisch setzen. Dann wurde abgerechnet: Die Nummern von je zwei Sitznachbarn wurden multipliziert und alle Ergebnisse (=Gewinnpunkte) zusammengezählt. Für jeden Gewinnpunkt gab's schließlich 100 Euro!
Die Kandidaten waren natürlich völlig unvorbereitet auf dieses mathematische Problem und irrten hektisch umher, angefeuert von den gut gemeinten aber auch widersprüchlichen Zurufen aus dem Publikum. So sah ihre Sitzordnung dann aus: 9 - 10 - 3 - 6 - 1 - 8 - 5 - 4 - 7 - 2 - (9).
Das ergab 9*10+10*3+3*6+6*1+1*8+8*5+5*4+4*7+7*2+2*9 = 272 Punkte, also 27.200 Euro!
(1) Welcher Gewinn wäre das Minimum/Maximum gewesen?
(2) Gibt es eine allgemeine Formel für die min./max. Punktezahl bei n Spielern?
|
Martin (martin243)
Senior Mitglied
Benutzername: martin243
Nummer des Beitrags: 712
Registriert: 02-2001
| | Veröffentlicht am Montag, den 29. Juli, 2002 - 11:32: |
|
Hi sol@ti!
Irgendwie beschleicht mich ganz spontan das Gefühl, als wären die Leutchen gut beraten gewesen, wenn sie sich ordentlich sortiert hingesetzt hätten, also von 1 bis 10.
Aber ich werde mal bei Gelegenheit nach einer richtigen Begründung suchen.
MfG
Martin |
Christian Schmidt (christian_s)
Mitglied
Benutzername: christian_s
Nummer des Beitrags: 26
Registriert: 02-2002
| | Veröffentlicht am Montag, den 29. Juli, 2002 - 12:04: |
|
Hi Martin
Ich glaube das stimmt nicht.(ausser ich habe mich verrechnet)
Wenn sie sich ordentlich hingesetzt hätten, komme ich auf einen Gewinn von 34.000Euro.
Ich hab mal ein bißchen rumprobiert und auf jeden Fall eine gefunden mit höherem Gewinn:
2-1-3-4-5-6-7-8-10-9
Gewinn:
42.500Euro
MfG
C. Schmidt |
Jan Martin Krämer (species5672)
Mitglied
Benutzername: species5672
Nummer des Beitrags: 37
Registriert: 07-2002
| | Veröffentlicht am Montag, den 29. Juli, 2002 - 13:21: |
|
@Martin
Das habe ich zuerst auch gedacht weil z.B. 10*9+8*7 > 10*7 + 8*9, allerdings wird bei dir die 10 verschwendet, da sie mit der 1 multipliziert wird.
@Christian:
Dein Ergebnis ist auf jeden Fall besser, allerdings erhalte ich beim nachrechnen nicht 425 Punkte, sondern 353 (kann das jemand bestätigen?).
Mein Vorschlag wäre
2-4-6-8-10-9-7-5-3-1 = 368 (?)
Ich nehme mal die Frechheit in Anspruch zu behaupten, das diese Lösung ziemlich nahe an dem Maximum ist (falls meine Begründung stimmtm die ich allerdings noch mal überprüfen muss). |
Christian Schmidt (christian_s)
Mitglied
Benutzername: christian_s
Nummer des Beitrags: 28
Registriert: 02-2002
| | Veröffentlicht am Montag, den 29. Juli, 2002 - 13:31: |
|
Hi Jan
Stimmt, hatte mich verrechnet, die 353 stimmen.
MfG
C. Schmidt |
Juppy
Unregistrierter Gast
| | Veröffentlicht am Montag, den 29. Juli, 2002 - 18:49: |
|
Hallo sol@ti, Martin, Christian und Jan, mein Tipp für das Minimum ist:
2-10-1-9-3-7-5-6-4-8
das ergibt bei mir 224.
MfG
Juppy |
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Montag, den 29. Juli, 2002 - 19:25: |
|
Bravo Jan & Juppy!
Die Mindestgewinnsumme bei diesem Spiel ist tatsächlich 22.400 *Juppy* Euro, der Maximalgewinn 36.800 *Jan* Euro. Damit ist Punkt (1) erledigt.
Nun zu Punkt (2): n Spieler, also Nummern von 1 bis n. Bin schon sehr gespannt, wer das Prinzip für die optimale Reihenfolge als Erste(r) verallgemeinern und in eine Formel fassen kann!
Viele Grüße
sol@ti
|
Juppy
Unregistrierter Gast
| | Veröffentlicht am Dienstag, den 30. Juli, 2002 - 12:21: |
|
Hallo sol@ti,
die Formel für das Maximum habe ich, aber ich bin mir nicht ganz sicher, ob es als Beweis ausreicht, wenn ich einfach so argumentiere, dass es ähnlich der vollständigen Induktion abläuft, (jedenfalls benenne ich die Schritte auch dementsprechend):
(Induktions-)Anfang:
In der Mitte stehen bereits die beiden Zahlen n und n-1.
Ihr Produkt ist offensichtlich das größtmögliche aller Produkte zweier Zahlen aus {1..n}.
Hinreichende Bedingung dafür, dass die maximale Summe erreicht wird, ist, dass die einzelnen Summanden jeweils maximale Produkte sind. Also ist es klar, dass man nun immer die beiden nächstniedrigeren Zahlen dazusetzt, also zwei Zahlen, die sich nur um 1 unterscheiden, denn niedrigere würden nicht ein maximales Produkt ergeben, und dann wäre die hinreichende Bedingung nicht erfüllt.
Diese beiden Zahlen seien k und k-1.
(Induktions-)Schritt (von k auf k-2 und von k-1 auf k-3):
Es seien nun bereits einige Plätze besetzt, so dass die auf die vorgegebene Art gebildete Summe bisher maximal ist. Dann haben die momentanen Randplätze die Nummern:
k und k-1.
Um diese beiden herum werden jetzt die Zahlen k-2 und k-3 platziert, denn von allen noch übrigen Zahlen aus {1..k-2} ergeben sie die größten Produkte mit den beiden am momentanen Rand platzierten k und k-1.
Es gibt zwei Möglichkeiten, wie sie platziert werden:
a) (k-2) k .... (k-1) (k-3)
b) (k-3) k .... (k-1) (k-2)
bei a) ergibt sich außer dem Produkt k*(k-1) noch:
(k-2)*k + (k-1)*(k-3) = 2k² -6k +3
bei b) (k-3)*k + (k-1)*(k-2) = 2k² -6k +2
bei a) wird die Summe also größer als bei b).
was wurde bei a) gemacht?
es wurden k und (k-2) miteinander multipliziert, also wurden zwei Zahlen multipliziert, die den gleichen Rest bezüglich Teilung durch 2 haben (... wie sagt man das kurz? - "gleiches Moduloverhalten bzgl. 2" ?) - also sie sind beide gleichzeitig gerade oder sie sind beide gleichzeitig ungerade.
das (k-1) wurde mit (k-3) multipliziert, also wurden zwei Zahlen multipliziert, die auch wieder gleichzeitig denselben Rest bei einer Teilung durch 2 lassen würden.
also kann man sich darauf festlegen, dass man (die im Kreis anzuordnenden Zahlen) so anordnet, dass links die ungeraden 1, 3, 5, ... aufsteigend
bis zum (n-1) (wenn n gerade ist) bzw.
bis zum n, wenn n ungerade ist,
und rechts die geraden Zahlen absteigend stehen: ..., 6, 4, 2
Also nochmal der bisherige Ablauf:
man setzt den Spieler mit der größten Zahl (n) zuerst an den Tisch.
nun unterscheidet man, ob n gerade oder ungerade ist:
ist n gerade:
links daneben die dann ungerade Zahl n-1,
daneben wiederum die nächstkleinere ungerade Zahl n-3 usw.
bis 1 erreicht ist.
rechts neben n die gerade Zahl n-2,
rechts daneben wiederum die nächstkleinere gerade Zahl n-4 usw.
bis 2 erreicht ist.
Das sind zwei Fälle zur Unterscheidung: 1) n ist ungerade 2) n ist gerade
1) n ist ungerade: später
2) n ist gerade
wenn n eine gerade Zahl ist, dann kommt folgendes ganz gut hin:
hier nochmal am Beispiel n=10:
es stehen links die Produkte aus ungeraden Faktoren, rechts die aus geraden:
1-3-5-7-9-10-8-6-4-2
hier 1*3 + 3*5 + 5*7 + 7*9, allgemein dann
1*3 + 3*5 + ... + (n-5)*(n-3) + (n-3)*(n-1) (L)
in der Mitte steht dann ein Faktor (n-1)*n, und dann kommen rechts die Produkte aus geraden Faktoren:
n*(n-2) + (n-2)*(n-4) + (n-4)*(n-6) + ... + 6*4 + 4*2 (R)
und schließlich noch die 2 als Produkt aus den benachbarten Werten 2 und 1, die den Kreis schließen.
Die Summe (L) besteht aus n/2 - 1 Summanden und die Summe (R) auch.
es gelten folgende Summenformeln (die sich auch beweisen lassen)
(L) 1*3 + 3*5 + ... + (n-5)*(n-3) + (n-3)*(n-1)
= Sn/2-1 k=1 (2k-1)*(2k+1) = (n-2)*(n²-n-3)/6
(R) n*(n-2) + (n-2)*(n-4) + (n-4)*(n-6) + ... + 6*4 + 4*2
= Sn/2-1 k=1 2k*(2k+2) = n*(n-2)*(n+2)/6
so dass sich zusammen mit dem mittleren Faktor (n-1)*n und der 2 ergibt:
(n-2)*(n²-n-3)/6 + (n-1)*n + 2 + n*(n²-4)/6 = (2n³ +3n² -11n + 18)/6
also können n Spieler maximal (2n³ + 3n² -11n)/6 + 3 Punkte erreichen.
nun noch der Fall
1) n ist ungerade
ist n eine ungerade Zahl, besteht die Summe auf der linken Seite:
... (n-6)*(n-4) + (n-4)*(n-2) + (n-2)*n,
deren Summanden sämtlich ungeradzahlig sind, aus (n-1)/2 Summanden
und die Summe auf der rechten Seite:
(n-1)*(n-3) + (n-3)*(n-5) + (n-5)*(n-7) + ...,
deren Summanden alle geradzahlig sind, aus (n-3)/2 Summanden.
die (n-1)/2 Summanden auf der linken Seite:
S(n-1)/2 k=1 (2k-1)*(2k+1) = (n³-4n+3)/6
die (n-3)/2 Summanden auf der rechten Seite:
S(n-3)/2 k=1 2k*(2k+2) = (n-3)*(n²-1)/6
zusammen mit dem größten Summanden n*(n-1) und der 2 ergibt das
(2n³ + 3n² - 11n)/6 + 3
was dasselbe ist, wie für gerade Zahlen.
Gruß
Juppy |
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Dienstag, den 30. Juli, 2002 - 12:46: |
|
Super Juppy, ganz ausgezeichnet!
Du hat wirklich einen *Sonderapplaus* verdient!
Vielen Dank für deine ausführliche Herleitung der korrekten Formel. Aber hattest du nicht gerade das Minimum gefunden? Und jetzt die Maximumsformel? - Mann, du bist ganz schön vielseitig!
Jetzt ist eigentlich nur noch ein Problem offen ...
Herzlichen Glückwunsch und viele Grüße
sol@ti
|
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Dienstag, den 30. Juli, 2002 - 13:04: |
|
Hallo Juppy, hab gerade den dummen Tippfehler "du hat" entdeckt (klingt so nach den alten Häschenwitzen "Hattu Probleme? - Muttu lösen"). Entschuldige bitte, der Sonderapplaus war wirklich ehrlich gemeint!
sol@ti
|
|
