Postage Stamp Problem als Al Zimmermann Wettbewerb "Son of Darts"

14/02/2010 - 14:27 von Rainer Rosenthal | Report spam
HP schrieb:

> Wenn Ihr hier ueber das "Postage Stamps"-Problem diskutieren wollt,
> dann waere es vielleicht angemessen, eine neue Diskussionfolge
> aufzumachen, weil es sonst unter dem von Rainer gewaehlten "Point
> Packing"-Titel fehlplatziert ist.



Guter Vorschlag! Ich transportiere darum schon mal Deine Hinweise hierher.
Es geht um den noch bis Juni laufenden Wettbewerb "Son of Darts", bei
dem das Postage Stamp Problem (Briefmarkenproblem) in folgender Ver-
kleidung auftritt:

Wir haben eine Dart-Scheibe, die in R
Regionen aufgeteilt ist. In jeder Region
steht eine Zahl, die ihren Wert bezeichnet.
Man darf mit einer Anzahl D von Dart-
Pfeilen auf die Scheibe schiessen. Dann
zàhlt man für jeden stecken gebliebenen
Pfeil den Wert der betreffenden Region und
addiert alle diese Werte. Dies ist das
Ergebnis der Wurfserie.

Wettbewerbsaufgabe, siehe
http://www.azspcs.net/Contest/SonOfDarts
Für gewisse Kombinationen D/R sollen
Dart-Scheiben entworfen werden, so dass
ein möglichst grosser Bereich von
Ergebnissen abgedeckt wird. Das Gütemaß
einer Dart-Scheibe ist der kleinste Wert,
der nicht als Ergebnis erzielt werden kann.

Um ein Beispiel für /R = 3/5 zu haben, zitiere ich Franz Fritsche:



>> Um ein wenig mit dem Problem vertraut zu werden, habe ich mal schnell auf
>> dem Papier so eine (ziemlich schlechte) Lösung erarbeitet. Und zwar für
>> dieselben Problemklasse, die auch für die Beispiele auf der Page gewàhlt
>> wurde: D = 3, R = 5.
>>
>> Mit ein wenig Herumprobieren, komme ich da z. B. auf
>>
>> {1, 4, 7, 10, 12}
>>
>> Und damit auf einen smallest unattainable score von 26 (wenn's stimmt);
>> nicht gerade berauschend, wenn man sieht, dass hier auch ein smallest
>> unattainable score von 37 erreicht werden kann! (Siehe Bsp. auf der Page.)





Wir haben hier also 5 Regionen (Felder) auf der Dart-Scheibe, die von FF
mit den Werten 1, 4, 7, 10 und 12 beschriftet wurde. Diese Scheibe ist besser
als er selbst glaubt, denn tatsàchlich ist 33 hier das erste nicht erreichbare
Ergebnis. Die 26 erzielt man ja leicht, indem man die drei Pfeile in die
Regionen schiesst, die mit 12, 10 und 4 beschriftet sind: 12+10+4 = 26.

Mein eigener Bestwert ist 37, also der bestmögliche überhaupt (das làsst sich ja
komplett durchprobieren). Bis hin zu R habe ich die TOP-Ergebnisse selbst
finden können, danach sieht es leider mau aus, und über 3/27 habe ich mich
noch nocht hinaus gewagt. Dabei kann bis 3/40 eingereicht werden. Andere
Kategorien sind D=4 mit R=1 ... 30, sowie D/R = 5/1 ... 5/20 und 6/1 ... 6/10.
Hier habe ich auch das eine oder andere Ergebnis finden können, TOP-Werte aber
nur in den trivialen Kategorien mit kleinem R.

Um diese Einstiegs-Posting (wenn denn Antworten kommen sollten) abzurunden,
möchte ich Hugo Pförtner zitieren:

==> > Ueber einen Link zu den alten Wettbewerben http://recmath.com/contest/archives.php

> kommt man auf den "historischen" ("Darts"-)Wettbewerb, beim dem nach
> den optimalen Markensaetzen mit 3 zu klebenden Werten gefragt wurde.
> http://recmath.com/contest/Darts/index.php
> Dort gibt es auch eine Ergebnistabelle http://recmath.com/contest/Darts/FinalReport.html
> , in der man auch die damals besten gefundenen Loesungen sehen kann.
> Bis einschliesslich R ist das inzwischen erschoepfend
> durchgerechnet und die angegebenen Loesungen sind gesichert. Dann
> kommt ein kleiner Bereich, in dem die alten Wettbewersloesung
> "ziemlich sicher" die optimalen sind, und dann wird's richtig
> interessant (siehe Bemerkung am Ende der OEIS A001213)
>
> Weitere Informationen auf:
> http://www.research.att.com/~njas/sequences/A001212
> http://www.research.att.com/~njas/sequences/A001213
> http://www.research.att.com/~njas/sequences/A001214
> http://www.research.att.com/~njas/sequences/A001215
> http://www.research.att.com/~njas/sequences/A001216
>
> Achtung: Die Definition in der OEIS bezieht sich auf den hoechsten
> darstellbaren Wert, waehrend im Wettbewerb nach dem ersten nicht
> darstellbaren Wert gefragt wird.
>
> Fuer Leute, die Zugriff auf eine ordentlich sortierte Uni-Bibliothek
> haben, lohnt sich ein Blick in den online nicht verfuegbaren Artikel
> "Two New Techniques for Computing Extremal h-bases A_k" von M.F.
> Challis im Computer Journal Vol. 36 No. 2, 1993, Seiten 117 - 126


==
Gruß,
Rainer Rosenthal <<< bitte mit ai, nicht mit ei.
r.rosenthal@web.de
 

Lesen sie die antworten

#1 Rainer Rosenthal
14/02/2010 - 14:47 | Warnen spam
Rainer Rosenthal schrieb:

Es geht um den noch bis Juni laufenden Wettbewerb "Son of Darts", bei
dem das Postage Stamp Problem (Briefmarkenproblem) in folgender Ver-
kleidung auftritt:

Wir haben eine Dart-Scheibe, die in R
Regionen aufgeteilt ist. In jeder Region
steht eine Zahl, die ihren Wert bezeichnet.
Man darf mit einer Anzahl D von Dart-
Pfeilen auf die Scheibe schiessen. Dann
zàhlt man für jeden stecken gebliebenen
Pfeil den Wert der betreffenden Region und
addiert alle diese Werte. Dies ist das
Ergebnis der Wurfserie.



Achtung: es dürfen Pfeile neben der Scheibe landen, d.h. es müssen nicht
alle einen Wert liefern, und es dürfen auch mehrere Pfeile in der
selben Region (im selben Feld) landen.

Zu der Ausage von Franz Fritsche
FF: Mit ein wenig Herumprobieren, komme ich da z. B. auf
FF:
FF: {1, 4, 7, 10, 12}
FF:
FF: Und damit auf einen smallest unattainable score von 26 (wenn's stimmt);

ist also zu sagen: 26 stimmt nicht. Der Wert 33 ergibt sich aus folgender
Aufstellung:

1: [1]
2: [1, 1]
3: [1, 1, 1]
4: [4]
5: [4, 1]
6: [4, 1, 1]
7: [7]
8: [7, 1]
9: [7, 1, 1]
10: [10]
11: [10, 1]
12: [12]
13: [12, 1]
14: [12, 1, 1]
15: [10, 4, 1]
16: [12, 4]
17: [12, 4, 1]
18: [10, 7, 1]
19: [12, 7]
20: [12, 7, 1]
21: [10, 10, 1]
22: [12, 10]
23: [12, 10, 1]
24: [12, 12]
25: [12, 12, 1]
26: [12, 10, 4]
27: [10, 10, 7]
28: [12, 12, 4]
29: [12, 10, 7]
30: [10, 10, 10]
31: [12, 12, 7]
32: [12, 10, 10]

33 geht nicht mehr.

Gruß,
Rainer Rosenthal

Ähnliche fragen