Zahlenkreis
Christian Arndt
Es wäre nett, wenn ihr mir bei folgendem Problem helfen könntet:
Die natürlichen Zahlen 1 bis 10 werden in beliebiger Reihenfolge
zu einem Kreis angeordnet (jeder Seite eines Zehnecks wird eine
der 10 Zahlen zugeordnet).
Wie groß ist die größte Summe von 3 benachbarten Zahlen dann
mindestens bei einem solchen Kreis (bzw. Zehneck)?
Georg Kraml
[Sorry wegen Beinahe-Fullquote]
Äh... also entweder habe ich dich absolut falsch verstanden,
oder die Aufgabe ist absolut trivial.
Die drei benachbarten Zahlen sind sicher alle >= 1. Mindestens
zwei davon sind außerdem >= 2, mindestens eine davon ist
darüberhinaus >= 3. Die Summe ist damit >= 1 + 2 + 3.
Folgerung: Die kleinste mögliche Summe ist 6.
Etwas ratlos,
Georg
--
Georg Kraml ge...@ads.tuwien.ac.at
Rainer Rosenthal
Christian Arndt <ch-a...@gmx.net>
Hallo Christian,
die Aufgabe ist lustig. Und wäre sie in de.rec.denksport
gepostet worden, dann hätte ich einfach
18
sagen können ( mit genügend grossem Spoiler *g*).
Aber hier in d.s.m. ist das natürlich unmöglich. Schade.
Und mit folgendem Gekritzel bin ich zu dieser Idee gekommen:
10
1 2
7 6
3 8
9 4
5
Hier sind die grössten Summen schön rundum verteilt:
10+2+6 = 6+8+4 = 4+5+9 = 7+1+10 = 18
und an einer Stelle haben wir 5+9+3 = 17 und gleich
daneben 9+3+7 = 19.
Bei soviel harmonischem Verteil-Dingens bin ich ziemlich
sicher, dass ich nicht allzusehr daneben liegen werde.
Und wenn die Antwort falsch sein sollte, dann war sie doch
zumindest schnell :-)
Gruss,
Rainer
Christian Arndt
"Georg Kraml" <ge...@ads.tuwien.ac.at> wrote:
>Folgerung: Die kleinste mögliche Summe ist 6.
Ich meinte das eigentlich so:
In jedem Kreis ist eine von den "Dreiersummen" am _größten_.
zB: -1-8-9-3-4-7-2-6-5-10-
In diesem Beispiel wäre die größte Summe dreier benachbarter
Zahlen 6+5+10=21. Alle anderen solcher Summen sind kleiner.
In einem anderen Beispiel -10-3-6-8-5-7-4-2-9-1- wäre die
größte Summe nur 9+1+10=8+5+7=20.
Wie kann man jetzt beweisen, dass die größtmögliche "Dreier-
summe" bei einem beliebigen Kreis mindestens x groß sein muss?
Danke und Gruß, Christian.
Christian Arndt
"Rainer Rosenthal" <r.ros...@web.de> wrote :
>
> dann hätte ich einfach
> 18
> Aber hier in d.s.m. ist das natürlich unmöglich. Schade.
> Und mit folgendem Gekritzel bin ich zu dieser Idee gekommen:
>
>
> 10
> 1 2
> 7 6
>
> 3 8
>
> 9 4
> 5
>
> Hier sind die grössten Summen schön rundum verteilt:
> 10+2+6 = 6+8+4 = 4+5+9 = 7+1+10 = 18
>
> und an einer Stelle haben wir 5+9+3 = 17 und gleich
> daneben 9+3+7 = 19.
Ersteinmal Danke für die schnelle Antwort.
Ich muss zugeben, dass meine verwendete Formulierung etwas
verwirrend ist. In deinem Kreis ist die größte Summe 19.
In einem anderen Kreis, zB -1-8-9-3-4-7-2-6-5-10- ist die
größte Summe 6+5+10=21, alle anderen Summen sind kleiner.
Gibt es jetzt Kreise in denen die größte Summe kleiner als
19 ist? Wenn nein, wäre 19 die Lösung. Wenn ja, dann wäre eben
diese kleinere Summe die Lösung.
(Jeder beliebige Kreis hat eine größte Summe, wie klein kann
diese sein?)
Gruss, Christian.
Rainer Rosenthal
Christian Arndt <ch-a...@gmx.net> wrote
> > > Die natürlichen Zahlen 1 bis 10 werden in beliebiger
> > > Reihenfolge zu einem Kreis angeordnet (jeder Seite
> > > eines Zehnecks wird eine der 10 Zahlen zugeordnet).
> > > Wie groß ist die größte Summe von 3 benachbarten
> > > Zahlen dann mindestens ?
Ich schrieb ein Beispiel:
> >
> > 10
> > 1 2
> > 7 6
> >
> > 3 8
> >
> > 9 4
> > 5
> >
> > Hier sind die grössten Summen schön rundum verteilt:
> > 10+2+6 = 6+8+4 = 4+5+9 = 7+1+10 = 18
> >
> > und an einer Stelle haben wir 5+9+3 = 17 und gleich
> > daneben 9+3+7 = 19.
>
> Ersteinmal Danke für die schnelle Antwort.
> Gibt es jetzt Kreise in denen die größte Summe kleiner als
> 19 ist? Wenn nein, wäre 19 die Lösung. Wenn ja, dann wäre eben
> diese kleinere Summe die Lösung.
> (Jeder beliebige Kreis hat eine größte Summe, wie klein kann
> diese sein?)
Hallo Christian,
die Aufgabe hatte mir so gut gefallen, dass ich schon gestern Nacht
die Antwort hingeschrieben hatte. Dann hatte ich sie aber mal wieder
in der "Outbox" hängen lassen .... Als ich sah, dass noch keine
fundierten Erkenntnisse vorlagen, habe ich sie dann vorhin rausgeschickt.
Und jetzt strichle ich fleissig, um ein klares Bild zu bekommen. Schon
bei n=5 Zahlen beginnt es witzig zu werden:
3
4 2
1 5
Hier deutet alles auf die Lösung G = 10 hin.
Die Aufgabenstellung ist übrigens klar und deutlich formuliert.
Woher kommt diese schöne Fragestellung ?
Wenn mir keiner zuvorkommt, will ich gerne die ersten G(n)
sammeln und als Sequenz im NJAS-Archiv unterbringen.
Bisher habe ich nur:
G(3) = 6, G(4) = 9, G(5) = 10
Und G(10) >= 18 scheint mir eine ausgemachte Sache zu sein.
Für die praktische Suche muss man die "Riesen" schön weit
auseinandersetzen und die kleineren Zahlen gefühl- und
geschmackvoll verteilen. Hat was von einer Weihnachtsbastelei :-)
Gruss,
Rainer Rosenthal
r.ros...@web.de
Rainer Rosenthal
Christian Arndt <ch-a...@gmx.net>
Hallo Christian,
die Fragestellung ist interessant für andere Zahlen als n=10 und
führt dann auf eine Funktion G(n), die für n >= 3 definiert ist und
so beginnt: 6, 9, 10, ...
Schon bei n=6 beginnt das Tüfteln und es hat ein wenig gebraucht,
bis ich G(6) = 11 herausgefunden hatte. Ich will den Spass nicht
verderben und male den Kreis nicht hin.
Allerdings will ich mal eine Formalisierung versuchen - schon um
eine gute Erklärung für das NJAS-Archiv zu üben :-)
Wir betrachten alle Permutationen p: {1..n} --> {1..n} und in jeder
Permutation alle Teilsummen T(p,i) = p(i-1) + p(i) + p(i+1) für alle
i = 1..n. Dabei ist p(0) = p(n) und p(n+1) = p(1).
Mit g(p) bezeichne ich die grösste dieser Teilsummen.
Mit G(n) bezeichne ich das kleinste g(p).
Zu meiner Lösung G(6) = 11 gehört eine Permutation p, bei der
sich die Teilsummen 10 und 11 abwechseln. Das riecht nach
"optimal". Und es übt ganz gut für n = 10.
Nachhilfe in Sachen Formulierung nehme ich gerne an.
Aber bitte redet mir nicht zu, dass ich bei Null zu zählen anfangen
soll. Natürlich ist dann modulo-Rechnen easy, aber "Null ist doof".
Tja, jetzt werde ich dann an n=7 gehen.
Gruss,
Rainer Rosenthal
r.ros...@web.de
Thomas Nordhaus
Hallo Christian. Hier ein Ansatz: Indiziere deine Zahlen im
Uhrzeigersinn von 0 bis 9 also n_0 bis n_9
Bilde S = Summe (k=0..9) ( n_k + n_(k+1 mod 10) + n_(k+2 mod 10) ).
Dann ist leicht zu sehen, dass: S = 3*(1+2+...10) = 3*11*10/2 = 165. Von
deinen 10 Tripeln muss also mindestens 1 Tripel die Summe 17 haben (16,5
gibts nicht und 16 wäre zu klein): Dirichlet's Schubkastenprinzip!.
Dein "kleinstes grösstes Tripel" hat also eine Summe von mindestens 17.
Das löst dein Problem natürlich noch nicht vollständig aber gibt
immerhin eine untere Grenze. Rainer behauptet ja, dass die kleinste
grösste Summe 18 beträgt...
Gruss, Thomas
Christian Arndt
> Wenn mir keiner zuvorkommt, will ich gerne die ersten G(n)
> sammeln und als Sequenz im NJAS-Archiv unterbringen.
Was ist denn überhaupt das NJAS-Archiv?
> Hat was von einer Weihnachtsbastelei :-)
Finde ich auch.
Gruss, Christian.
Christian Arndt
"Thomas Nordhaus" <Thomas....@t-systems.de> wrote:
>
> Hallo Christian. Hier ein Ansatz: Indiziere deine Zahlen im
> Uhrzeigersinn von 0 bis 9 also n_0 bis n_9
> Bilde S = Summe (k=0..9) ( n_k + n_(k+1 mod 10) + n_(k+2 mod 10) ).
>
> Dann ist leicht zu sehen, dass: S = 3*(1+2+...10) = 3*11*10/2 = 165. Von
> deinen 10 Tripeln muss also mindestens 1 Tripel die Summe 17 haben (16,5
> gibts nicht und 16 wäre zu klein): Dirichlet's Schubkastenprinzip!.
>
> Dein "kleinstes grösstes Tripel" hat also eine Summe von mindestens 17.
> Das löst dein Problem natürlich noch nicht vollständig aber gibt
> immerhin eine untere Grenze. Rainer behauptet ja, dass die kleinste
> grösste Summe 18 beträgt...
>
spiel finden können.
Gruss, Christian.
Christian Arndt
"Rainer Rosenthal" <r.ros...@web.de> wrote:
>
> Schon bei n=6 beginnt das Tüfteln und es hat ein wenig gebraucht,
> bis ich G(6) = 11 herausgefunden hatte. Ich will den Spass nicht
> verderben und male den Kreis nicht hin.
> Tja, jetzt werde ich dann an n=7 gehen.
Bis jetzt habe ich da G(7)=14, aber ich bin mir nicht sicher, da die
Teilsummen weit auseinanderliegen.
Für n=8 habe ich (bis jetzt) G(8)=16.
Gruss, Christian.
Georg Kraml
> Ich meinte das eigentlich so:
> In jedem Kreis ist eine von den "Dreiersummen" am _größten_.
> zB: -1-8-9-3-4-7-2-6-5-10-
> In diesem Beispiel wäre die größte Summe dreier benachbarter
> Zahlen 6+5+10=21.
OK, kapiert.
> Wie kann man jetzt beweisen, dass die größtmögliche "Dreier-
> summe" bei einem beliebigen Kreis mindestens x groß sein muss?
Das "beweisen" zu wollen, hieße IMHO mit Kanonen auf Webdesigner
schießen. Du bist schneller, wenn du einfach alle Möglichkeiten
durchprobierst. (Es gibt *höchstens* 10!/20 Möglichkeiten.)
Moment, ich probier das mal eben aus.
lg,
Daniel Grund
durchprobiert und habs rennen lassen.
1-4-9-5-3-7-8-2-6-10
Min of all Max=18
Daniel
Helmut Richter
Damit ist, ohne das Programm anzuschauen, allein aus dem Ergebnis
bewiesen, dass das Minimum höchstens 18 ist. Dass es nicht 17 sein kann,
dazu muss man dem Programm glauben. Aber das geht auch ohne.
Wegen des Durchschnitts von 16.5 muss das Maximum mindestens bei 17 liegen.
Zwei benachbarte Dreiergruppen können nicht die gleiche Summe haben:
wäre a+b+c=b+c+d, so wäre a=d.
Damit ist der Schnitt von 16.5 bei einem Maximum von 17 nur noch zu
erreichen, wenn 16 und 17 sich überall abwechseln. Hat man 3
nebeneinanderliegende Zahlen, lässt sich daraus jetzt der Rest konstruieren.
Die 1 kann nicht am Rand einer 17er-Gruppe 1+a+b=17 liegen, sonst wird aus
der benachbarten Gruppe keine 16er-Gruppe mehr a+b+x=16 => x=0. Also liegt
die 1 in der Mitte einer 17er-Gruppe. Damit kommt entweder das Tripel 6+1+10
oder 7+1+9 vor. Die versuchen wir zu einem ganzen Kreis zu ergänzen:
6+1+10=17
1+10+5=16
10+5+2=17
5+2+9=16
2+9+x=17, aber x=6 ist schon verbraucht
7+1+9=17
1+9+6=16
9+6+2=17
6+2+8=16
2+8+x=17, aber x=7 ist schon verbraucht
Damit gibt es keine Lösung für 17.
Was noch fehlt, ist ein Weg, einfach auf das Ergebnis zu kommen.
Helmut Richter
Daniel Grund
1-4-9-5-3-7-8-2-6-10- G(10)=18
1-5-8-2-6-7-3-4-9- G(9)=16
1-5-6-2-7-3-4-8- G(8)=15
1-2-5-6-3-4-7- G(7)=14
1-4-5-2-3-6- G(6)=11
1-4-2-3-5- G(5)=10
1-2-3-4- G(4)=9
1-2-3- G(3)=6
Delphi Source. Es ist ein schnell geschriebenes Programm also bitte keine
"Das hätt man doch vieeeel besser machen können...":
unit Unit1;
interface
uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls,
Forms, Dialogs, StdCtrls;
type
TForm1 = class(TForm)
Button1: TButton;
Edit1: TEdit;
procedure Button1Click(Sender: TObject);
end;
var Form1: TForm1;
implementation
{$R *.dfm}
const anz=3;
maxz=anz-1;
procedure TForm1.Button1Click(Sender: TObject);
var i0,i1,i2,i3,i4,i5,i6,i7,i8,i9 : integer;
o, s, min, max : integer;
f, sol : array[0..9] of integer;
str : string;
begin
min:=999999999;
for o:=0 to 9 do f[o]:=0;
for i0:=0 to maxz do
for i1:=0 to maxz do if (i1<>i0)then
for i2:=0 to maxz do if (i2<>i0)and(i2<>i1)then
{ for i3:=0 to maxz do if (i3<>i0)and(i3<>i1)and(i3<>i2)then
//das sollte man auskommentieren siehe Zusammenhang mit CONST anz=3
for i4:=0 to maxz do if (i4<>i0)and(i4<>i1)and(i4<>i2)and(i4<>i3)then
for i5:=0 to maxz do if
(i5<>i0)and(i5<>i1)and(i5<>i2)and(i5<>i3)and(i5<>i4)then
for i6:=0 to maxz do if
(i6<>i0)and(i6<>i1)and(i6<>i2)and(i6<>i3)and(i6<>i4)and(i6<>i5)then
for i7:=0 to maxz do if
(i7<>i0)and(i7<>i1)and(i7<>i2)and(i7<>i3)and(i7<>i4)and(i7<>i5)and(i7<>i6)th
en
for i8:=0 to maxz do if
(i8<>i0)and(i8<>i1)and(i8<>i2)and(i8<>i3)and(i8<>i4)and(i8<>i5)and(i8<>i6)an
d(i8<>i7)then
for i9:=0 to maxz do if
(i9<>i0)and(i9<>i1)and(i9<>i2)and(i9<>i3)and(i9<>i4)and(i9<>i5)and(i9<>i6)an
d(i9<>i7)and(i9<>i8)then {}begin
max:=0;
f[0]:=i0+1;
f[1]:=i1+1;
f[2]:=i2+1;
{ f[3]:=i3+1; // ebenfalls auskommentieren
f[4]:=i4+1;
f[5]:=i5+1;
f[6]:=i6+1;
f[7]:=i7+1;
f[8]:=i8+1;
f[9]:=i9+1;{}
for o:=0 to maxz do begin
s:=f[(o+maxz) mod anz]+f[o]+f[(o+1) mod anz];
if s>max then max:=s;
end;
if max<min then begin
min:=max;
sol:=f;
end;
end;
str:='';
for o:=0 to maxz do str:=str+inttostr(sol[o])+'-';
str:=str+' G('+inttostr(anz)+')='+inttostr(min);
Edit1.Text:=Str;
end;
end.
Christian Arndt
"Daniel Grund" <Daniel...@gmx.de> wrote:
> Hier sind die Lösungen für n=3..10 (mit meinem Programm errechnet)
>
> 1-4-9-5-3-7-8-2-6-10- G(10)=18
> 1-5-8-2-6-7-3-4-9- G(9)=16
> 1-5-6-2-7-3-4-8- G(8)=15
> 1-2-5-6-3-4-7- G(7)=14
> 1-4-5-2-3-6- G(6)=11
> 1-4-2-3-5- G(5)=10
> 1-2-3-4- G(4)=9
> 1-2-3- G(3)=6
>
Gruss, Christian.
Georg Kraml
Moment! Ich sehe hier das Tripel 6-10-1, Summe 17.
Sebastian Kapfer
writes...
| Hallo!
| Es wäre nett, wenn ihr mir bei folgendem Problem helfen könntet:
| Die natürlichen Zahlen 1 bis 10 werden in beliebiger Reihenfolge
Hilft dir vermutlich nicht weiter, aber wenn du ein halbes Jahr warten
kannst (*g) dann besorg dir die Lösungen zum diesjährigen
Bundeswettbewerb Mathematik (1. Runde). Die Aufgabe 4 ist fast
identisch, aber mit einem Zwölfeck.
"Aus zwölf Strecken der Längen 1, 2, 3, 4, ... 12 wird irgendwie ein
Zwölfeck zusammengesetzt.
Man beweise, dass es dann stets in diesem Zwölfeck drei
aufeinanderfolgende Seiten gibt, deren Gesamtlänge größer als 20 ist."
Nein, ich hab auch noch keine Lösung :)
Philipp Zumstein
<r.ros...@web.de> wrote:
>
>Christian Arndt <ch-a...@gmx.net>
>
>> Es wäre nett, wenn ihr mir bei folgendem Problem helfen könntet:
>> Die natürlichen Zahlen 1 bis 10 werden in beliebiger Reihenfolge
>> zu einem Kreis angeordnet (jeder Seite eines Zehnecks wird eine
>> der 10 Zahlen zugeordnet).
>> Wie groß ist die größte Summe von 3 benachbarten Zahlen dann
>> mindestens bei einem solchen Kreis (bzw. Zehneck)?
>
>die Fragestellung ist interessant für andere Zahlen als n=10 und
>führt dann auf eine Funktion G(n), die für n >= 3 definiert ist und
>so beginnt: 6, 9, 10, ...
>
>Schon bei n=6 beginnt das Tüfteln und es hat ein wenig gebraucht,
>bis ich G(6) = 11 herausgefunden hatte. Ich will den Spass nicht
>verderben und male den Kreis nicht hin.
Ich bestätige deine Zahlen. Mit etwas Rechenpower bekam ich auch G(6)
= 11. Die kommt aber nur zweimal vor. Und diese Kreisanordnung sind
eigentlich diesselben. Bis, dass einmal im Uhrzeigersinn angefangen
wird und einmal gegen den Uhrzeigersinn.
Wie kann man eigentlich am besten alle möglichen Permutationen
programmieren? Dies geht wohl rekursiv am besten, oder? Leider kann
ich auf meinem Taschenrechner icht rekursiv programmieren, aber dieser
ist ja für grössere Berechnungen sowieso nicht schnell genug.
Gruss
Philipp
Georg Kraml
> Moment! Ich sehe hier das Tripel 6-10-1, Summe 17.
Aua, *peinlich*, heute ist irgendwie nicht mein Tag.
OK, wie einige andere bereits gepostet haben, ist das Ergebnis 18.
Hier sind kanonische Repräsentanten aller entsprechenden
Äquivanlenzklassen unter Rotationssymmetrie:
1 7 9 2 5 10 3 4 6 8
1 9 7 2 5 10 3 4 6 8
1 7 9 2 5 10 3 4 8 6
1 9 7 2 5 10 3 4 8 6
1 10 6 2 7 8 3 4 9 5
1 10 6 2 8 7 3 4 9 5
1 10 6 2 7 8 3 5 9 4
1 10 6 2 8 7 3 5 9 4
1 6 10 2 4 9 5 3 7 8
1 6 10 2 4 9 5 3 8 7
1 10 6 2 4 9 5 3 8 7
1 7 9 2 4 6 8 3 5 10
1 7 9 2 4 8 6 3 5 10
1 10 6 2 9 4 5 3 8 7
1 7 9 2 6 4 8 3 5 10
1 6 10 2 5 9 4 3 7 8
1 6 10 2 5 9 4 3 8 7
1 10 6 2 5 9 4 3 8 7
1 10 6 2 9 5 4 3 8 7
1 7 9 2 6 8 4 3 5 10
1 7 9 2 6 8 4 3 10 5
1 9 7 2 6 8 4 3 10 5
1 9 7 2 8 6 4 3 10 5
1 10 6 2 9 4 5 8 3 7
1 7 9 2 6 4 8 5 3 10
1 10 6 2 9 5 4 8 3 7
1 7 9 2 6 8 4 5 3 10
1 10 3 5 4 8 6 2 9 7
1 7 3 8 4 5 9 2 6 10
1 10 3 5 8 4 6 2 9 7
1 7 3 8 5 4 9 2 6 10
1 5 10 3 4 6 8 2 7 9
1 5 10 3 4 8 6 2 7 9
1 5 10 3 4 8 6 2 9 7
1 10 5 3 4 8 6 2 9 7
1 7 8 3 4 5 9 2 6 10
1 7 8 3 4 9 5 2 6 10
1 7 8 3 4 9 5 2 10 6
1 8 7 3 4 9 5 2 10 6
1 10 5 3 8 4 6 2 9 7
1 7 8 3 5 4 9 2 6 10
1 10 5 3 6 8 4 2 9 7
1 10 5 3 8 6 4 2 9 7
1 7 8 3 5 9 4 2 6 10
1 7 8 3 5 9 4 2 10 6
1 8 7 3 5 9 4 2 10 6
1 4 9 5 3 7 8 2 6 10
1 4 9 5 3 8 7 2 6 10
1 5 9 4 3 7 8 2 6 10
1 5 9 4 3 8 7 2 6 10
1 6 8 4 3 10 5 2 7 9
1 6 8 4 3 10 5 2 9 7
1 8 6 4 3 10 5 2 7 9
1 8 6 4 3 10 5 2 9 7
--
Georg Kraml ge...@ads.tuwien.ac.at
Rainer Rosenthal
Christian Arndt <ch-a...@gmx.net> wrote
>
> Es wäre nett, wenn ihr mir bei folgendem Problem helfen könntet:
> zu einem Kreis angeordnet (jeder Seite eines Zehnecks wird eine
> der 10 Zahlen zugeordnet).
> Wie groß ist die größte Summe von 3 benachbarten Zahlen dann
>
> >
> > Woher kommt diese schöne Fragestellung ?
> Die hat uns unsere Mathematiklehrerin gegeben.
>
Hallo Christian,
einen schönen Gruss an Deine Lehrerin !
Die Frage hat ja lebhaftes Interesse und viele Antworten
erbracht. Ich fasse mal zusammen.
Sebastian Kapfer hat wahrscheinlich die Quelle gefunden:
Diesjähriger Bundeswettbewerb Mathematik
(1. Runde). Die Aufgabe 4 ist fast identisch,
aber mit einem Zwölfeck.
Die Lehrerin hat es Euch vielleicht einfacher machen wollen,
indem sie n = 10 gewählt hat statt n = 12. Tatsächlich ist
aber n = 12 viel einfacher. Denn das gesuchte G(n) ist nach
der klaren Rechnung von Thomas Nordhaus nach unten in
folgender Weise beschränkt:
G(n) >= ceil( 3*(n+1)/2 )
wobei ceil(x) kleinste ganze Zahl z >= x ist ( ceiling=Decke ).
Für n = 12 ist ceil(3*13/2) = ceil(39/2) = 20. Das ist die Lösung,
die Sebastian bei seinem Posting noch nicht hatte.
Aber für n = 10 ist es wesentlich komplizierter ! Denn da gibt
diese Ungleichung nur ceil(3*11/2) = 17 her. Und dann braucht es
richtig knüppelharte Denkarbeit, wie sie Helmut Richter ausgeführt
hat, um zu zeigen, dass G(10) echt grösser sein muss als 17.
Ich habe bisher sein Posting nur überflogen, werde es mir aber
nachher noch genauer durchlesen.
> > Wenn mir keiner zuvorkommt, will ich gerne die ersten G(n)
> > sammeln und als Sequenz im NJAS-Archiv unterbringen.
> Was ist denn überhaupt das NJAS-Archiv?
>
Das NJAS-Archiv ist eine Sammelstelle für Folgen von ganzen Zahlen.
http://www.research.att.com/~njas/sequences/
Als ich es das erste Mal gesehen hatte, dachte ich, ich spinne. Was
da für ein absurdes Zeug drin ist. Aber inzwischen weiss ich es besser.
Es sind jede Menge tolle Referenzen und spannende Zusammenhänge
angegeben. Jeder kann mitmachen, wodurch der Quatschfaktor auch
nicht zu kurz kommt. Unser Beispiel G(n) habe ich aufgesucht, indem
ich unter der angegebenen Web-Adresse eingegeben habe, was
Daniel Grund herausgefunden hatte: 9 10 11 14 15 16 18
ID Number: A014155
Sequence: 0,1,2,3,4,6,7,8,9,10,11,14,15,16,18,21,22,23,27,28,29,
30,33,36,37,42,44,45,46,48,53,55,56,63,64,65,67,70,72,74,
79,82,85,92,100,109,119,125,126,128,131,135,140,146
Name: Sum of a cube and a triangular number.
Ohne das jetzt für wirklich wichtig halten zu wollen - es wird sich wohl
nur um eine zufällige Übereinstimmung handeln, weil ich nur so ein
kleines Stückchen unserer Folge eingegeben hatte - aber hier haben
wir schon einen typischen Fall, für den NJAS gedacht ist: Zusammen-
hänge herzustellen. Übrigens: "cube" ist klar, oder ? das sind die Zahlen
n^3, die auch in deutschen Landen einst als Kuben gehandelt wurden.
Und "triangular number" ist bei uns als "Dreieckszahl" bekannt. Das sind
die Zahlen, die man durch Stapeln erhält: 1+2+3+4 = 10 ist z.B. eine.
> > Hat was von einer Weihnachtsbastelei :-)
> Finde ich auch.
Eventuell können wir Georg Kraml sogar davon überzeugen, dass hier
in dieser Aufgabe Mathe-Spass vom Feinsten vorliegt. Er schrieb ja
sehr lustig:
Das "beweisen" zu wollen, hieße IMHO mit Kanonen auf
Webdesigner schießen. Du bist schneller, wenn du einfach
alle Möglichkeiten durchprobierst.
(Es gibt *höchstens* 10!/20 Möglichkeiten.)
Aber andererseits sagte er auch:
Aua, *peinlich*, heute ist irgendwie nicht mein Tag.
Das ist zwar fies von mir, das in Zusammenhang zu setzen, weil es so ja
nicht gemeint war. Aber Georg wird mir verzeihen und sicher zugeben,
dass es eine gute Sache ist, dass man mit der ceil()-Formel noch über den
Daumen gute untere Schranken für G(n) findet, wenn n so gross ist, dass
das Durchprobieren für schnelle Webdesigner einfach langweilig wird :-)
Mit freundlichem Gruss
Rainer Rosenthal
r.ros...@web.de
Philipp Zumstein
(Helmut Richter) wrote:
>On Sat, 22 Dec 2001 14:59:47 +0100, Daniel Grund <Daniel...@gmx.de> wrote:
>
>>Hab mal schnell eben ein programm geschrieben das alle Permutationen
>>durchprobiert und habs rennen lassen.
>>
>>
>>1-4-9-5-3-7-8-2-6-10
>>
>>Min of all Max=18
>
>Damit ist, ohne das Programm anzuschauen, allein aus dem Ergebnis
>bewiesen, dass das Minimum höchstens 18 ist. Dass es nicht 17 sein kann,
>dazu muss man dem Programm glauben. Aber das geht auch ohne.
> [...hübscher Beweis...]
>
>Was noch fehlt, ist ein Weg, einfach auf das Ergebnis zu kommen.
Ich hatte heute Nachmittag etwas Zeit ein Bisschen herumzuspielen. Was
dabei rausgekommen ist, möchte ich Euch im folgenden mitteilen:
Ich verfolge die Strategie "2er Blöcke separieren". Also d.h. bei n=6
kann man zwei 2er Blöcke separieren. Diese entalten die 4 grössten
Zahlen so, dass die Summe der 2er Blöcke minimiert wird. Also d.h.
hier [6,3] und [4,5] ist ein 2er Block. Dazwischen füllt man mit den
übrigen Zahlen auf:
1, [6,3], 2, [5,4]
Die grösste Dreiersumme ergibt sich am Ende: s_max=2+4+5=11. Weil die
Durchschnittsdreiersumme d=10.5 beträgt ist dieser Zahlenkreis
minimal.
Weiterhin erhält man:
1, [7,4], 2, [6,5], 3
n=7, s_max=14, d=12
1, [8,5], 2, 3, [7,6], 4
n=8, s_max=17, d=13.5
1, [9,4], 2, [8,5], 3, [7,6]
n=9, s_max=16, d=15
1, [10,5], 2, [9,6], 3, [8,7], 4
n=10, s_max=19, d=16.5
Für n=6,7,9 ist die Strategie minimal.
Beweis:
n=6:
Der minimalste Zahlenkreis mit Durchschnitt d=10.5 enthält
Dreiersummen vom Wert 10 und 11.
n=9:
Es kann keinen Zahlenkreis mit s_max=15 geben. Weil wegen d=15 folgt
alle Dreiersummen sind gleich 15. Aber zwei aufeinanderfolgende
Dreiersummen sind verschieden voneinander. [siehe Posting von Helmut
Richter].
n=7:
Falls es einen Zahlenkreis mit s_max=13 gibt, dann wechseln sich die
Dreiersummen ab mit den Werten 12, 11, 13, wobei gleichviele Male die
11 wie die 13 vorkommt.
1 kann nicht in einer 13er Gruppe liegen [cf. H.R.].
Fall a: 1 liegt in einer 12er Gruppe, d.h. 1+a+b=12 =>a+b+2=13 =>
1,a,b,2 liegen nebeneinander. Die restlichen drei Zahlen besitzen die
Summe 28-12-2=14 also s_max=14. Widerspruch
Fall b: 1 liegt in einer 11er Gruppe, d.h. 1+a+b=11 => 1,a,b,2 oder
1,a,b,3 liegen nebeneinander. Die restlichen drei Zahlen besitzen die
Summe 28-11-2 bzw. 28-11-3 also s_max=15 bzw. s_max=14. Widerspruch.
q.e.d.
Leider stimmt die Strategie für n=8,10 nicht. Es gibt kleiner
Zahlenkreise. Aber zumindest kann man daraus eine obere Schranke
finden für die g(n):
g(3m+n) <= 1+5m+3n, für n=0,1,2.
Bei n=0 ist die Formel am besten bzw. der Fehler zum genauem Wert ist
am kleinsten.
Gruss
Philipp
Philipp Zumstein
<r.ros...@web.de> wrote:
>Christian Arndt <ch-a...@gmx.net> wrote
>>
>> Es wäre nett, wenn ihr mir bei folgendem Problem helfen könntet:
>> Die natürlichen Zahlen 1 bis 10 werden in beliebiger Reihenfolge
>> zu einem Kreis angeordnet (jeder Seite eines Zehnecks wird eine
>> der 10 Zahlen zugeordnet).
>> Wie groß ist die größte Summe von 3 benachbarten Zahlen dann
>> mindestens bei einem solchen Kreis (bzw. Zehneck)?
>>
>Die Lehrerin hat es Euch vielleicht einfacher machen wollen,
>indem sie n = 10 gewählt hat statt n = 12. Tatsächlich ist
>aber n = 12 viel einfacher. Denn das gesuchte G(n) ist nach
>der klaren Rechnung von Thomas Nordhaus nach unten in
>folgender Weise beschränkt:
>
> G(n) >= ceil( 3*(n+1)/2 )
>
>wobei ceil(x) kleinste ganze Zahl z >= x ist ( ceiling=Decke ).
>Für n = 12 ist ceil(3*13/2) = ceil(39/2) = 20. Das ist die Lösung,
>die Sebastian bei seinem Posting noch nicht hatte.
Gilt g(12) = 20? Ich habe "mit meiner Strategie" eine Zahlenkreis
gefunden mit g*(12)=21:
1, 12, 5, 2, 11, 6, 3, 10, 7, 4, 9, 8
Gibt es noch einen kleineren? Im Wettbewerb, muss man da ">" oder ">="
beweisen?
Gruss
Philipp
Rainer Rosenthal
Philipp Zumstein <hzum...@bluewin.ch>
>
> Gilt g(12) = 20? Ich habe "mit meiner Strategie" eine Zahlenkreis
> gefunden mit g*(12)=21:
>
> 1, 12, 5, 2, 11, 6, 3, 10, 7, 4, 9, 8
>
> Gibt es noch einen kleineren? Im Wettbewerb, muss man da ">" oder ">="
> beweisen?
>
Hallo Philipp,
ich zitiere aus dem Posting von Sebastian Kapfer:
"Aus zwölf Strecken der Längen 1, 2, 3, 4, ... 12 wird irgendwie ein
Zwölfeck zusammengesetzt.
Man beweise, dass es dann stets in diesem Zwölfeck drei
aufeinanderfolgende Seiten gibt, deren Gesamtlänge größer als 20 ist."
Da G(n) nach unten durch ceil(3(n+1)/2) beschränkt ist und dies
für n = 12 gerade den Wert 20 hat, weiss man:
G(12) >= 20
und weil G(12) die kleinste maximale Dreiersumme g(p) besitzt unter
allen Permutationen p von {1..12}, ist g(p) >= 20 für alle Permutationen.
Du hast aber recht: Die Lösung ist damit noch nicht gefunden. G(12) = 21
ist durchaus denkbar. Ich war da zu voreilig.
An meiner Bemerkung ist aber trotzdem ein "guter Kern", denn die Original-
Aufgabenstellung in diesem Thread ist ja:
"Wie groß ist die größte Summe von 3 benachbarten Zahlen
dann mindestens bei einem solchen Kreis (bzw. Zehneck)?"
Und wenn man hier mit ceil(3(n+1)/2) argumentiert, dann kann man nur sagen:
Die Summe ist mindestens 17. Das ist aber nicht wesentlich netter als wenn
man
sagen würde: die Summe ist mindestens 6 = 1+2+3.
Im Unterschied zum Wettbewerb wurde ja hier die Angabe einer Schranke
gesucht
und nicht die Bestätigung für eine vorgegebene. Die Lehrerin hätte also
besser
so formuliert:
" ... zeige, dass die Summe von 3 benachbarten Zahlen mindestens 17
ist."
Nichtsdestotrotz war das eine sehr schöne Aufgabe. Es juckt mich fast, mal
wieder
was Schönes zu programmieren. Und für grössere n bis 100 scheint mir schon
einiges
Gehirnschmalz notwendig. Insbesondere möchte ich gerne sehen, ob es noch ein
paar Takte lang synchron mit der NJAS-Sequenz A014155 weitergeht.
Wie schaut es aus ? Hat einer schon ein paar weitere Werte ? Wann macht Dein
Programm schlapp, Daniel ?
Gruss,
Rainer Rosenthal
r.ros...@web.de
Ralf Muschall
> 1, 12, 5, 2, 11, 6, 3, 10, 7, 4, 9, 8
> Gibt es noch einen kleineren? Im Wettbewerb, muss man da ">" oder ">="
IMHO nicht. Mein Rechner probiert gerade (brute force) im Hintergrund
für n>=3 die Werte durch, bisher hat er 3,6,7,8,11,12,13,15,17,18. Da
die Originalaufgabe off-by-one-Werte an die Ecken malt, sind meine
Werte um 3 kleiner als die gesuchten, d.h. f(12,3)=21.
Da ich zu faul bin, ein effektives Programm zu schreiben (ich hatte
noch eine Funktion, die die N-te (für 0<=N<n!) Permutation von
[0,...,n-1] erzeugt, herumliegen, und der Rest war trivial), werden
in Anbetracht der O(n^n)-Laufzeit nicht mehr viele Werte kommen :-)
Wer mitspielen will, kann per GA oder Annealing o.ä. obere Schranken
suchen.
Ralf
--
GS d->? s:++>+++ a C++++ UL+++ UH++ P++ L++ E+++ W- N++ o-- K- w--- !O M- V-
PS+>++ PE Y+>++ PGP+ !t !5 !X !R !tv b+++ DI+++ D? G+ e++++ h+ r? y?
Philipp Zumstein
<r.ros...@web.de> wrote:
>
>Philipp Zumstein <hzum...@bluewin.ch>
>>
>> Gilt g(12) = 20? Ich habe "mit meiner Strategie" eine Zahlenkreis
>> gefunden mit g*(12)=21:
>>
>> 1, 12, 5, 2, 11, 6, 3, 10, 7, 4, 9, 8
>>
>> Gibt es noch einen kleineren? Im Wettbewerb, muss man da ">" oder ">="
>> beweisen?
>>
>
>Hallo Philipp,
>
>ich zitiere aus dem Posting von Sebastian Kapfer:
>
>"Aus zwölf Strecken der Längen 1, 2, 3, 4, ... 12 wird irgendwie ein
>Zwölfeck zusammengesetzt.
>Man beweise, dass es dann stets in diesem Zwölfeck drei
>aufeinanderfolgende Seiten gibt, deren Gesamtlänge größer als 20 ist."
>
>Da G(n) nach unten durch ceil(3(n+1)/2) beschränkt ist und dies
>für n = 12 gerade den Wert 20 hat, weiss man:
>
> G(12) >= 20
>
>und weil G(12) die kleinste maximale Dreiersumme g(p) besitzt unter
>allen Permutationen p von {1..12}, ist g(p) >= 20 für alle Permutationen.
>
>Du hast aber recht: Die Lösung ist damit noch nicht gefunden. G(12) = 21
>ist durchaus denkbar. Ich war da zu voreilig.
Ich hab's mir etwas genauer angeschaut und es gilt G(12)=21.
Beweis (analog zum Beweis von Helmut Richter):
******
Ann.: Es existiert ein Zahlenkreis mit s_max=20.
*****
Weil Durchschnitt d=19.5 => 19er Gruppen, 20er Gruppen
1 kann nicht am Anfang einer 20er Gruppe sein, somit ist 1 in der
Mitte einer 20er Gruppe, d.h. ...,a,1,b,... mit a+b=19. Für diese
Summe gibt es drei Möglichkeiten 19=12+7=11+8=10+9. Weil die 1 in der
Mitte ist und die anderen Zahlen a,b darum herum, ist die Reihenfolge
von a und b nicht egal.
Fall a: a=12, b=7
*******
12,1,7,11,2,6,12 Widerspruch
Fall b: a=11, b=8
*******
11,1,8,10,2,7,11 Widerspruch
Fall c: a=10, b=9
*******
10,1,9,9 Widerspruch
q.e.d.
Gruss
Philipp
Philipp Zumstein
On 22 Dec 2001 23:12:32 +0100, Ralf Muschall <ra...@lipsia.de> wrote:
>Da ich zu faul bin, ein effektives Programm zu schreiben (ich hatte
>noch eine Funktion, die die N-te (für 0<=N<n!) Permutation von
>[0,...,n-1] erzeugt, herumliegen, und der Rest war trivial), werden
>in Anbetracht der O(n^n)-Laufzeit nicht mehr viele Werte kommen :-)
Wie sieht diese Funktion aus, die dier die N-te Permutation erzeugt?
Falls sie gross ist, kannst du mir diese Funktion mal schicken?
Gruss
Philipp
Daniel Grund
Danke?
Gruß
Daniel
Rainer Rosenthal
Philipp Zumstein <hzum...@bluewin.ch>
>
> Ich hab's mir etwas genauer angeschaut und es gilt G(12)=21.
>
> Beweis (analog zum Beweis von Helmut Richter):
> ******
> Ann.: Es existiert ein Zahlenkreis mit s_max=20.
> *****
Hallo Philipp,
habe ebenfalls noch ein wenig gepuzzelt und bin so frech, die
folgenden Erkenntnisse für gültig zu halten:
G(11) = 20: 1-8-7-2-9-5-4-11-3-6-10-
G(12) = 21: 1-7-11-2-8-9-4-6-10-5-3-12
G(13) = 23: 1-5-12-6-3-10-9-4-8-11-2-7-13-
G(14) = 25: 1-14-2-6-13-3-7-12-4-8-11-5-9-10-
Mit der Zeit kriegt man ja einen "Blick" und ein "Händchen" für
dies Puzzle :-)
Bitte sofort schreien, wenn ich zu grosse G(n) angegeben haben
sollte. Ich habe nämlich meine Drohung wahrgemacht und die
Sequenz der G(n) für n=3,4,... ins NJAS-Archiv gesendet.
Von dort habe ich schon mal die automatische Rückmeldung be-
kommen, die so aussieht:
+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*
The following is a copy of the email message that was sent to njas
containing the sequence you submitted.
All greater than and less than signs have been replaced by their html
equivalents. They will be changed back when the message is processed.
This copy is just for your records. No reply is expected.
Subject: NEW SEQUENCE FROM Rainer Rosenthal
%I A000001
%S A000001 6,9,10,11,14,15,16,18,20,21,23,25
%N A000001 Smallest maximum of consecutive three-sums in permuted n-cycle
%C A000001 In the "Bundeswettbewerb 2001" contest we are give 12 sticks of
lengths 1,..,12 put in a ring in random order. It has to be proved,
that there are at least 3 consecutive sticks with total length not
less than 20.
A closer look shows, that the total length is at least a(12)=21.
The problem of the contest is a consequence of the following
observation: Every term a(n) is at least ceil(3*(n+1)/2), since
n*a(n) >= sum{i=1..n}(p(i-1)+p(i)+p(i+1)) = 3*sum{i=1..n}(i)
=3*n*(n+1)/2.
So in the case n=12 we have (total length) >= a(12)=21 >= 20.
%D A000001 "Bundeswettbewerb Mathematik 2001"
%D A000001 Thread "Zahlenkreis" in de.sci.mathematik, December 2001
%F A000001 Let p be a permutation of 1..n and let g(p) be the maximum of the
consecutive three-sums p(i-1)+p(i)+p(i+1), where p(0)=p(n) and
p(n+1)=p(1).
a(n) is the minimum of all the g(p) taken over all permutations p.
%e A000001 a(6)=11 because cycle 1-4-5-2-3-6- has three-sums
11,10,11,10,11,10 with max=11
%O A000001 3
%K A000001 ,nice,nonn,unkn,
%A A000001 Rainer Rosenthal (r.ros...@web.de), Dec 23 2001
RH
RA 62.54.39.147
RU
RI
+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*
Gruss,
Rainer Rosenthal
r.ros...@web.de
Klaus Nagel
> Wer mitspielen will, kann per GA oder Annealing o.ä. obere Schranken
> suchen.
Genetischer Algorithmus ist vielleicht ein zu großes Wort für folgende
Zufallsmethode:
1. Nimm eine zufällige Permutation.
2. Such ein Tripel mit maximaler Summe.
3. Vertausche die mittlere Zahl dieses Tripels mit einer zufälligen anderen.
4. Berechne die maximale Tripelsumme. Ist sie ein neues Minimum, so gib
die Permutation aus.
5. Weiter bei Schritt 2.
Gewaltsam abbrechen, wenn man denkt, daß es keine Verbesserung mehr gibt.
Das Verfahren war sehr einfach zu programmieren und hat in kurzer Zeit
folgende Werte geliefert:
N 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 50
F(N) 11 14 15 16 18 20 21 23 25 27 28 29 31 33 35 90
F(50) = 90 ist vermutlich noch nicht das Optimum.
Frohe Weihnachten,
Klaus Nagel
Philipp Zumstein
Nein. Ich habe (nur mit reiner Kopfarbeit) einen Zahlenkreis gefunden
mit 85 als maximaler Dreiersumme. Auch deine anderen Zahlen würde ich
nicht alle als gesichert betrachten. Z.B. F(15) =/= 27, weil ich habe
einen Zahlenkreis mit 26 als maximale Dreiersumme:
1,15,6,2,14,7,3,13,8,4,12,9,5,11,10
6,15,1,7,14,2,8,13,3,9,12,4,10,11,5
Bei der 50:
Setze jeweils Paare zusammen: (50,1), (49,2), ..., (35,16)
Zwischen diese Paare setze die restliche Zahlen. Wenn man dies
geschickt macht kann man mit einer maximalen Dreiersumme von
85=51+34=50+1+(50-16) erreichen.'
Helmut Richter
>Das Verfahren war sehr einfach zu programmieren und hat in kurzer Zeit
>folgende Werte geliefert:
>
>N 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 50
>F(N) 11 14 15 16 18 20 21 23 25 27 28 29 31 33 35 90
Ich habe auch das Programmieren nicht bleiben lassen können und
verschiedene dieser Werte verbessert. Was mich an meinem Programm
beunruhigt, ist, dass es deine Lösung für N=9 nicht gefunden hat, sondern
17 gebraucht hat. Es hätte nämlich alles absuchen sollen.
Aber jetzt höre ich auf. Die bisherigen Ergebnisse stehen in
http://www.lrz-muenchen.de/~hr/tmp/zahlenkreis
und werden von alleine immer mehr, weil das Programm weiterläuft.
Helmut Richter
Rainer Rosenthal
Philipp Zumstein <hzum...@bluewin.ch>
> nicht alle als gesichert betrachten. Z.B. F(15) =/= 27, weil ich habe
> einen Zahlenkreis mit 26 als maximale Dreiersumme:
>
> 1,15,6,2,14,7,3,13,8,4,12,9,5,11,10
> 6,15,1,7,14,2,8,13,3,9,12,4,10,11,5
>
Es dürfte G(15) = 25 sein:
1-9-13-2-10-11-4-8-12-5-7-14-3-6-15-
Gruss,
Rainer
-
P.S. Ich sag's ja: Weihnachtsbastelei ...
Helmut Richter
wrote:
>Es dürfte G(15) = 25 sein:
>
>1-9-13-2-10-11-4-8-12-5-7-14-3-6-15-
Komisch, bei mir kommt 5+7+14=26 raus.
Helmut Richter
Rainer Rosenthal
Helmut Richter <a28...@lxhri01.lrz.lrz-muenchen.de> wrote
> Auf meine dumm abgeschriebene Lösung:
> >Es dürfte G(15) = 25 sein:
> >
> >1-9-13-2-10-11-4-8-12-5-7-14-3-6-15-
>
> Komisch, bei mir kommt 5+7+14=26 raus.
>
> Helmut Richter
Hallo Helmut,
stimmt, kam bei mir ja auch raus. Und deshalb hatte ich
einen Tausch 7 <--> 6 markiert, den ich aber beim Posten
übersehen hatte:
Richtig ist:
1-9-13-2-10-11-4-8-12-5-6-14-3-7-15-
Gruss,
Rainer Rosenthal
r.ros...@web.de
Daniel Böhm
Was sagen denn Eure Frauen dazu, dass ihr am 4. Advent stundenlang da sitzt
und Zahlenkreise bastelt??
Gruß und frohe Weihnachten,
Daniel
Helmut Richter
>G(14) = 25: 1-14-2-6-13-3-7-12-4-8-11-5-9-10-
>
>Mit der Zeit kriegt man ja einen "Blick" und ein "Händchen" für
>dies Puzzle :-)
>Bitte sofort schreien, wenn ich zu grosse G(n) angegeben haben
>sollte. Ich habe nämlich meine Drohung wahrgemacht und die
14 24 1 8 11 4 9 10 2 12 5 6 13 3 7 14
Vielen Dank für die anderen Beispiele, anhand derer ich einen blöden
Fehler in meinem Programm finden konnte. Ich habe den korrigiert und die
Sache neu aufgesetzt. Jetzt spuckt das verbesserte Programm wieder
fortlaufend Ergebnisse nach
http://www.lrz-muenchen.de/~hr/tmp/zahlenkreis .
Helmut Richter
Ralf Muschall
> Wie sieht diese Funktion aus, die dier die N-te Permutation erzeugt?
Hier ist das ganze Programm (wüster alte Kram von der Platte
gemischt mit ein paar Additionen), wie gesagt weder schnell noch
schön, aber in ein paar Minuten zusammengetippt.
#include <iostream>
#include <stdlib.h>
typedef unsigned long long u64;
u64
fact(int n)
{
if (n<2) return 1;
return n*fact(n-1);
}
/* zerlege N positionssystemartig in Koeffizienten
s[0] ... s[n-1] mit 0<=s[i]<i+2
*/
void
num2vect(int n, u64 N, int * s)
{
u64 m=2, d=1;
for(int i=0;i<n-1;i++)
{
u64 x=N%m; N-=x; x/=d; s[i]=(int)x; d=m; m*=(i+3);
}
}
/* erzeuge N-the permutation des Vektors a[0 ... n-1]
s[] muss allokiert sein */
void
perm(int n, u64 N, int * a, int * s)
{
num2vect(n,N,s);
for(int i=n-1;i;i--)
{
int z=s[i-1];
if(z!=i) { int h=a[z]; a[z]=a[i]; a[i]=h; }
}
}
/* subsum(permlen,sumlen,p[])
groesste Teilsumme von sumlen benachbarten Dingern in einer permlen
lange Permutation
*/
int
subsum(int permlen, int sumlen, int * p)
{
int maxsum=0;
for (int i=0;i<permlen;i++)
{
int sum=0;
for (int j=0;j<sumlen;j++) sum+=p[(i+j)%permlen];
if (sum>maxsum) maxsum=sum;
}
return maxsum;
}
int
bestsubsum(int permlen, int sumlen)
{
int * p=new int[permlen]; // array for permutation
int * s=new int[permlen]; // aux. array for perm generator
for (int i=0;i<permlen;i++) p[i]=i;
u64 N=fact(permlen);
int minsum=permlen*permlen;
for (u64 I=0;I<N;I++)
{
perm(permlen,I,p,s);
int s=subsum(permlen,sumlen,p);
if (s<minsum) minsum=s;
}
delete[] s;
delete[] p;
return minsum;
}
int
main(int argc, char ** argv)
{
if (argc!=3) return !(cerr << "usage: " << argv[0] << " permlen sumlen\n");
int permlen=atoi(argv[1]);
int sumlen=atoi(argv[2]);
cout << permlen << ' ' << sumlen << ' ' << bestsubsum(permlen,sumlen) << endl;
return 0;
}
> Falls sie gross ist, kannst du mir diese Funktion mal schicken?
Zur Strafe für unangekündigtes Post+Mail musst Du sie jetzt sogar
zweimal lesen.
Daniel Grund
Mein Programm ist jetzt fertig, hat aber noch einen kleinen Fehler
(Algorithmus noch nicht 100% richtig). Bis jetzt liefert es ziemlich gute
_obere Schranken_ für f(n).
Auf http://www.uni-karlsruhe.de/~uy7y/zahlen.txt gibts diese für n=3..200.
Gruß
Daniel
Ralf Muschall
> für n>=3 die Werte durch, bisher hat er 3,6,7,8,11,12,13,15,17,18. Da
Soeben gab es einen neuen Wert: 13|->20 (d.h. 23 mit Eurer
off-by-one-Belegung).
Mehr wird es wegen O(n^n) wohl dieses Jahr nicht mehr. Langsam sollte
mal jemand eine schnellere und trotzdem sichere Methode erfinden.
Helmut Richter
>Ralf Muschall <ra...@lipsia.de> writes:
>
>> für n>=3 die Werte durch, bisher hat er 3,6,7,8,11,12,13,15,17,18. Da
>
>Soeben gab es einen neuen Wert: 13|->20 (d.h. 23 mit Eurer
>off-by-one-Belegung).
Das meine ist schon bei 22, umd probiert auch alles durch (allerdings in
einer intelligenteren Reihenfolge).
http://www.lrz-muenchen.de/~hr/tmp/zahlenkreis bekommt die Ergebnisse.
Helmut Richter
Rainer Rosenthal
Daniel Grund <Daniel...@gmx.de> wrote
Hallo Daniel,
gratuliere, das sieht ja schon Klasse aus !
Ich habe heute früh mit Papier und Bleistift eine Lösung
für n = 50 gefunden, die ebenfalls G(50) <= 83 bestätigt:
1-34-24-18-36-29-17-37-20-14-40-28-8-42-23-9-44-25-2-46-31-3-48-22-11-50-
12-13-49-21-5-35-33-4-45-30-6-43-27-7-41-32-10-39-26-15-38-19-16-47-
Basis-Idee ist, dass ich von 50 abwärts mit Zwischenraum 2 alle grossen
Brocken verteile und wenn die Zwischenräume der Länge 2 verbraten sind,
weiter abwärts marschiere und appetitliche Zweiergruppen baue. Dabei hatte
ich zuerst streng auf möglichst gleiche Verteilung geachtet - das war aber
blöd,
denn es bleiben ja noch eine Menger 1-er-Lücken zu füllen am Schluss. Die
dürfen natürlich nicht alle etwa gleich gross sein. Also muss man schon bei
den
Zweiergruppen für etwas Abwechslung sorgen.
Mit diesem Plan und mit dem Ziel, alle Dreiersummen kleiner als 85 zu
halten,
hatte ich dann recht bald eine 84-er-Lösung mit nur wenigen Stellen, an
denen
die 84 auftrat. Durch ein wenig Tauschen kam dann die obige 83-er-Lösung
heraus.
Ich hätte nicht gedacht, dass die Programmiererzunft so schnell zu
Ergebnissen
kommt bei den grossen n.
Vielleicht erklärst Du auch ein wenig die "eingebaute Intelligenz" ?
Hast Du auch so ein Grundgerüst und eine Zielzahl (wie z.B. 85), die Dir
hilft, recht-
zeitig mit dem Probieren aufzuhören ?
Mir ist eine hübsche Einkleidung der Aufgabe eingefallen, die ich jetzt den
Leuten
in de.rec.denksport vorsetzen werde :-)
Gruss,
Rainer Rosenthal
r.ros...@web.de
Rainer Rosenthal
Helmut Richter <a28...@lxhri01.lrz.lrz-muenchen.de>
>
> 14 24 1 8 11 4 9 10 2 12 5 6 13 3 7 14
>
> Vielen Dank für die anderen Beispiele, anhand derer ich einen blöden
> Fehler in meinem Programm finden konnte. Ich habe den korrigiert und die
> Sache neu aufgesetzt. Jetzt spuckt das verbesserte Programm wieder
> fortlaufend Ergebnisse nach
> http://www.lrz-muenchen.de/~hr/tmp/zahlenkreis .
>
> Helmut Richter
>
Hallo Helmut,
danke für diese schöne Lösung zu n=14. Meinst Du, dass man nun
sicher sein kann, dass G(14) = 24 ist ? Ich war ja schon von meiner
25 überzeugt. Und auch das enorme Programm von Daniel Grund
hat erst G(n) <= 25 bisher gefunden. Enorm sage ich wegen der
beeindruckenden Zahl n=200, an die es sich heranwagt und wegen
der gefundenen Schranke G(50) <= 83, auf die ich selbst so stolz war.
Im folgenden hänge ich mal das Posting an, das ich in der Gruppe
de.rec.denksport losgelassen habe. Darin wird ein interessanter
Gedanke genannt, wie ich meine: Nämlich die Betrachtung nicht
nur der maximalen Dreiergruppe in einer "Bestückung" sondern
auch der minimalen Dreiergruppe. Bisher haben wir entsprechend
der Originalaufgabe das Max zu drücken versucht. Genausogut
könnte man aber mal das Min zu heben versuchen oder daraufhin
optimieren, dass die Differenz zwischen Max und Min minimiert
wird (um Gleichmässigkeit zu erzielen). In Deinem Beispiel n=14
haben wir Max=11+4+9=24 und Min=2+12+5=19, was immer noch
ein komfortables Band der Breite 24-19=5 ist ... Ist da noch was drin ?
******* mein Posting in de.rec.denksport ******
Auf den letzten Drücker soll zu Heiligabend eine geschlossene
Lichterkette gebastelt werden. Die verwendbaren Lichtlein sind
ein schlimmes Sammelsurium:
Von der kleinsten Funzel mit Leuchtstärke 1 bis zur hellen Birne
mit Leuchtstärke 50 ist alles vertreten.
Wie kriegt man aus diesen 50 unterschiedlichen Lichtern
eine einigermassen gleichmässig leuchtende geschlossene
Lichterkette zusammen ?
Ach ja: Immer zwischen zwei helle eine dunklere und zwischen
zwei hellere eine dunkle, bzw. auch mal 3 etwa gleich helle
zusammen. Kurz und gut, man sieht zu, dass je drei benachbarte
Lichter an der geschlossenen Kette eine mittlere Gesamt-
Leuchtstärke haben.
Ein paar Gedanken dazu: Wie man unschwer nachrechnet, ist
die mittlere Leuchtstärke in den Dreiergruppen 76,5. Wäre eine
supergleichmässige Bestückung möglich, dann hätten wir lauter
Dreiergruppen mit Leuchtstärke 76 bzw. 77. Sowas ist aber
sehr schwierig und evtl. gar nicht möglich. Und die Zeit drängt
sowieso, denn die Lichterkette sollte am besten heute noch
fertig werden. Nach Heilig Drei Könige will sie wirklich keiner
mehr :-)
Frage:
Kann man die geschlossenen Lichterkette so mit den
50 Lichtlein der Leuchtstärken 1 bis 50 bestücken, dass
die Leuchtstärke jeder Dreiergruppe kleiner ist als 85 ?
Leser von de.sci.mathematik dürften da etwas wiedererkennen.
So wie ich die Aufgabe hier formuliert habe, ergibt sich dabei
ein in d.s.m. noch nicht erwähnter Aspekt: Statt sich eine möglichst
kleine maximale Leuchtstärke in den Dreiergruppen zu wünschen,
also allzu helle zu vermeiden, kann man ja umgekehrt auch fragen
nach einer Bestückung mit möglichst nicht zu dunklen Stellen.
Oder - was der Suche nach "Gleichmässigkeit" am meisten ent-
sprechen sollte: Suche nach Bestückung mit minimalem Abstand
zwischen den Leuchtstärken der hellsten und der dunkelsten
Dreiergruppe.
Aber ... wünschen kann man sich ja viel :-)
Gruss,
Rainer Rosenthal
r.ros...@web.de
Daniel Grund
1 n-1 2 3 4 5 .... n-2 (das werd ich wohl jetzt als nächstes ändern.
s.u.)
Jetzt bestimme ich alle Stellen an denen ein Max auftritt
z.B. bei
Stelle: 0 1 2 3 4 5
permut: 0 5 1 2 3 4
ist 2+3+4=9 und 4+0+4=9 und 9 ist max.
Somit sind bei mir nach Def 0,1,3,4,5 die Maxstellen.
Jetzt sortier ich diese Maxstellen der Große nach.
MaxSt.: 1 5 4 3 0
Inhalt: 5 4 3 2 0 hier also absteigend
Jetzt: Nimm den Inhalt der ersten Maxstelle M=5 und tausche ihn probeweise
mit der Zahl T (Tauschpartner) für die gilt:
T<M und T nicht selbst Maxstelle.
Würde man T>=M zulassen, so wüde sich an der Maxstelle nach Vertauschen
mindestens eine Summe Bilden die größer ist als Max.
Würde man T aus einer anderen Maxstelle zulassen gilt vor Tausch:
a+b+c = max = e+f+g sei o.B.d.A. f>b
und danach:
a+f+c > Max > e+b+g
Führt dies zu keiner echten Verbesserung mach ich T:=T-1 und probiers
wieder.
Sollte das für alle T<M nix bringen dann nehm ich die nächste Maxstelle
M:=4.
Dann gehts wieder von vorne los.
Mein einziges Problem, weshalb ich _nur_ Näherungswerte bekomme, was ich im
Voraus nicht ahnen konnte aber, als Info aber hätte testen müssen ist
folgendes:
Es gibt Situationen, in denen die Zahlen so verteilt sind, dass eine
Vertauschung keine _echte_ Verbesserung bringt (also max NICHT um mind. 1
kleiner wird) Dann sagt mein Programm ja: "Bin fertig!".
Das genau kann aber falsch sein, wenn z.B. eine Vertauschung das Max der
Perm
unverändert läßt, aber sich einige 3-er-Gruppen dem Durschnitt nähern. Dies
kann
in einer folgenden Vertauschung danach dazu führen dass sich ein besseres
Max einstellt.
Hat irgendjemand einen Vorschlag, wie ich mein letztes Problem lösen kann?
spontane Ideeen von mir:
1. Chi-Quadrat-Test (=Chi^2) über die 3-erSummen um Ausreißer zu erkennen.
Da müßte man aber zuerst folgendes beweisen:
Das Max wird genau dann minimal wenn Chi^2 optimal wird.
2. Andere Initialisierung des Feldes könnte gaaanz vielleicht diesen Effekt
verhindern. Nahezu unmöglich dies zu beweisen.
3. Zuerst meinen Algo durchlaufen lassen und dann einen Suchbaum aufbauen
(Knoten enthalten permutation, Kanten sind Vertauschungen), der auch gleiche
Max
nach Vertauschen zuläßt und dann mit Backtracking Optimumsuche laufen
lassen.
4. ?
Das Berechnen für alle n=3..200 dauert auf diese Weise ca. 30 sec auf PIII
800
So weit so breit
Daniel
PS: viel Spaß beim Geschenkeauspacken....
Philipp Zumstein
Hallo Helmut,
Dein Beweisverfahren kann man verallgemeinern:
Für k gerade, k>6; d(k)=3/2*(k+1)=:z+0.5,
existiert kein Zahlenkreis mit s_max = z+1.
Bei deinem Beispiel:
k=10, d(k)=16.5, z=16
On 22 Dec 2001 14:09:23 GMT, a28...@lxhri01.lrz.lrz-muenchen.de
(Helmut Richter) wrote:
>Wegen des Durchschnitts von 16.5 muss das Maximum mindestens bei 17 liegen.
>
>Zwei benachbarte Dreiergruppen können nicht die gleiche Summe haben:
>wäre a+b+c=b+c+d, so wäre a=d.
>
>Damit ist der Schnitt von 16.5 bei einem Maximum von 17 nur noch zu
>erreichen, wenn 16 und 17 sich überall abwechseln.
Bemerkung:
Müsste man vielleicht noch etwas genauer begründen:
Warum ist es nicht möglich, dass die Dreiersummen
17,17,17,15,17,16,17,16,17,16 in irgendeiner Reihenfolge besitzen?
Weil man dann mehr 17 hat als andere Zahlen und somit kann man nicht
immer abwechseln.
>Hat man 3
>nebeneinanderliegende Zahlen, lässt sich daraus jetzt der Rest konstruieren.
>
>Die 1 kann nicht am Rand einer 17er-Gruppe 1+a+b=17 liegen, sonst wird aus
>der benachbarten Gruppe keine 16er-Gruppe mehr a+b+x=16 => x=0. Also liegt
>die 1 in der Mitte einer 17er-Gruppe. Damit kommt entweder das Tripel 6+1+10
>oder 7+1+9 vor. Die versuchen wir zu einem ganzen Kreis zu ergänzen:
>
>6+1+10=17
>1+10+5=16
>10+5+2=17
>5+2+9=16
>2+9+x=17, aber x=6 ist schon verbraucht
allgemein:
a + 1 + b = z+1
1 + b + (a-1) = z
b + (a-1) + 2 = z+1
(a-1) + 2 + (b-1) = z
2 + (b-1) + a = z+1, aber a wurde schon am Anfang gebraucht!
q.e.d.
Leider kann man so etwas nicht auf allgemeinere Klassen anwenden. Es
scheitert an meiner Bemerkung. z.B. ein minimaler Zahlenkreis mit 10
Elementen besitzt die folgenden Dreiersummen:
18,17,18,17,12,18,15,16,18,16.
Somit weiss ich nicht, wie ich z.B. beweisen soll, dass es keinen
Zahlenkreis mit 15 Elementen gibt wobei s_max=25 ist; d(15)=24.
Gruss
Philipp
Daniel Grund
Jetzt:
Für alle n=3..200 nur noch 10 sec
und
bessere obere Schranken auf
http://www.uni-karlsruhe.de/~uy7y/zahlen2.txt
Als nächstes kommt ein Sackgassendetektor, der sich merkt ob
mein Problem aufgetreten ist. Wenn nicht kann man 100% sicher sein,
dass das kleinste Max gefunden wurde.
Philipp Zumstein
On 24 Dec 2001 07:45:16 GMT, a28...@lxhri01.lrz.lrz-muenchen.de
(Helmut Richter) wrote:
>Das meine ist schon bei 22, umd probiert auch alles durch (allerdings in
>einer intelligenteren Reihenfolge).
>
>http://www.lrz-muenchen.de/~hr/tmp/zahlenkreis bekommt die Ergebnisse.
Ich hab's mir mal angeschaut. Und nun behaupte ich einfach mal etwas:
g(2*k) = 3*(k+1) mit der Ausnahme g(6) = 11.
Ich kann beweisen, dass g(2*k) >= 3*(k+1) ist (mit meiner
Verallgemeinerung Deines Beweises). Nun müsste ich noch einen
allgemeinen Zahlenkreis finden der als maximale Dreiersumme 3*(k+1)
hat. Dann könnte man dies beweisen. Naja vielleicht stimmt es ja auch
gar nicht mehr für grosse k. Aber bei Deiner Tabelle (bis 22) stimmt
es.
Gruss
Philipp
Rainer Rosenthal
Helmut Richter <a28...@lxhri01.lrz.lrz-muenchen.de>
> Das meine ist schon bei 22, umd probiert auch alles durch (allerdings in
> einer intelligenteren Reihenfolge).
>
> http://www.lrz-muenchen.de/~hr/tmp/zahlenkreis bekommt die Ergebnisse.
>
Hallo Helmut,
in der Gruppe de.rec.denksport hat Kurt Stege ein offenbar
sehr leistungsfähiges Programm aus dem Boden gestampft,
das für n=50 den Max-Wert 78 liefert.
Ich habe ihm dazu schon gratuliert, allerdings mit etwas
belegter Stimme, denn ich war doch sooo stolz, dass ich das
Ergebnis auch gefunden hatte, sogar mit Kopfrechnen und
einer netten Idee.
Es hat sich also gelohnt, die de.rec.denksport-Köpfe mit zum
Qualmen zu bringen ! Weil die Leserschaft aber doch nicht
gerade deckungsgleich ist, setze ich meine Info zur Lösung
G(50) <= 78 hierher. Die Begründung von Kurt Stege dafür, dass
G(509 = 78 sein muss, habe ich noch nicht nachvollzogen, aber
es leuchtet sehr ein, dass es eine nur aus Dreiersummen 76 und
77 bestehende Lösung nicht geben wird.
***** Mein heutiges Posting in d.rec.denksport ****
Hallo Kurt,
Gratulation zu dem schnellen und optimalen Ergebnis !
Da bin ich also mit meiner Lösung einen Tick zu spät dran:
1 50 25 3 49 23 6 47 22 9 46 20 12 44 19 15 43 17 18
41 16 21 40 14 24 38 13 27 37 11 30 35 10 33 34 8 36
32 7 39 31 5 42 29 4 45 28 2 48 26
Sie entspringt einer "zündenden" Idee unter dem Weihnachts-
baum und konnte mit Papier und Bleistift ermittelt werden.
Das freut mich, denn ich kann auch gerne das Bauprinzip
mitteilen. Mir war aufgefallen, dass das Nachrechnen der
Dreiersummen erleichtert wird, wenn man ausnutzt, dass man
von der Summe S = a+b+c zur Summe b+c+d kommt, indem
man die Differenz d-a benutzt: S + (d-a) = b+c+d ist zwar
nicht gerade höhere Mathematik, aber es zeigt, wie wichtig der
Dreierabstand ist: Man muss die Kette so bauen, dass diese
Differenzen d-a möglichst klein bleiben.
Also habe ich meine Kette so angefangen:
1 x x 3 x x 6 x x 9 x x 12 x x usw. x x 42 x x 45 x x 48 x
Und ab Platz 2 habe ich dann im Dreier-Rhythmus die Zahlen ab
50 abwärts eingetragen (unter Auslassung der schon notierten Zahlen),
also: 50 - - 49 - - 47 - - usw.
Ist doch richtig angenehm einfach, oder ? Zumindest im Nachhinein :-)
Gruss,
Rainer Rosenthal
r.ros...@web.de
Daniel Grund
f(n):= min ( max S(p,i) )
p i
S(p,i):= p(i mod n) + p((i+1) mod n) + p((i+2) mod n)
p Permutation der Länge n (zero-based, wegen modulo)
i E {0..n-1)
Was wir bisher wissen:
1) f(n) für n=3..22
2) f(n) >= ceil( 3*(n+1)/2 )
3) Zwei aufeinanderfolgende 3-er:
a+b+c = b+c+d geht nur für a=d also nur mit n=4.
4) Formal beweisen könnt ich es nicht auf die Schnelle aber:
f(n+1) > f(n)
Was ich gerne wissen würde ist ob folgendes gilt:
5) Wenn für ein p gilt dass
f(n) = max S(p,i)
folgt dann daraus, dass ein i existiert mit
p(i)=0 und ( p(i+1)=n-1 oder p(i-1)=n-1 )
6) Oder gilt wenigstens?
Es existiert ein p mit f(n) = max S(p,i) so dass
p(i)=0 und ( p(i+1)=n-1 oder p(i-1)=n-1 )
vor 7)
Seien m_k alle Stellen in der Permutation p, die zu einem 3-er gehören,
dessen Summe maximal ist. Es kann mehrere 3-er mit gleichem Max geben.
Wenn man 2 Zahlen x und y zwischen solchen Stellen m_k austauscht
gilt sicherlich:
Max_neu >= Max_alt vielleicht sogar Max_neu > Max_alt
Es bringt aber sicherlich keine Verbesserung denn betrachtet man 2 3er
die sich nicht überlappen dann:
Sei oBdA x>y:
Vorher : a+b+x = Max_alt = c+d+y
Nachher: a+b+y < Max_alt < c+d+x
Soweit noch klar?
Jetzt vertausche ich bzw. mein Prog. solange Zahlen in p aus den
Max-Stellen mit anderen, die keine MaxStelle sind, bis sich nix
mehr verbessert.
Leider gilt danach _nicht_: f(n) = max S(p,i) denn Bsp.:
p : 0 8 1 4 7 2 3 6 5
m_k: ^ ^ ^
Max: 3+6+5 = 14
Es gibt keine Tauschmöglichkeiten für 6, 5 oder 3, die Max kleiner
machen würden.
Aber f(9) = 13 < 14 (13 und nicht 16 weil zero-based!)
Und deshlab jetzt 7)
Ist p derart, dass durch solche Vertauschungen keine echte Reduzierung
des Max erreicht wird, aber es mind. einen Tausch gibt mit
Max_Alt = Max_Neu komme ich dann zum Ziel, einem minimalen p, wenn ich
wie folgt vorgehe?
Ich bilde einen Suchbaum mit Wurzel p_w, der nur Knoten (=Permutationen)
enthält, deren Max<=Max(p_w) sind. Finde ich ein p_neu mit
Max(p_neu) < Max(p_w) so erstelle ich nen neuen Baum mit Wurzel p_neu,
schmeiß den alten auf den Müll und such nur im neuen weiter.
Was schief gehn könnte erkannt? Wer sagt mir, dass ich zum Minimum-Max
komme, ohne das Max zwischendurch kurzzeitig durch ein Vertauschen zu
verschlechtern?
Wenn diese direkte Vorgehen irgendwie beweisbar zum Minimum-Max führt,
müßt ich meinen Algo "nur noch" mit den Baum erweitern und dann dürfte
das alles ziemlich flott gehen, denn alle Näherungslösungen für
n=3..200 bekomm ich in ca. 10 sec.
Hat jemand sonstige Vorschläge, die man noch so anschauen könnte, die
einen Vorteil bringen?
Trotz 3km Text einen geruhsamen Abend
Daniel
Rainer Rosenthal
Sebastian Kapfer <skapf...@yahoo.de>
> Hilft dir vermutlich nicht weiter, aber wenn du ein halbes Jahr warten
> kannst (*g) dann besorg dir die Lösungen zum diesjährigen
> Bundeswettbewerb Mathematik (1. Runde). Die Aufgabe 4 ist fast
> identisch, aber mit einem Zwölfeck.
>
> "Aus zwölf Strecken der Längen 1, 2, 3, 4, ... 12 wird irgendwie ein
> Zwölfeck zusammengesetzt.
> Man beweise, dass es dann stets in diesem Zwölfeck drei
> aufeinanderfolgende Seiten gibt, deren Gesamtlänge größer als 20 ist."
>
Hallo Sebastian,
inzwischen hat das NJAS-Archiv die Folge G(n) akzeptiert.
Und offenbar ist mein Beitrag verständig eingeordnet worden. Denn aus
meinem Hinweis auf den Bundeswettbewerb haben sie gleich den
folgenden Link gemacht.
http://www.bundeswettbewerb-mathematik.de/wettbewerb/wettb2001.htm
Nun kann ich darin aber unseren Zahlenkreis bzw. die von Dir angegebene
Aufgabe 4 nicht finden. Kannst Du bitte Deine Referenz angeben ? Ich
werde dies als Korrektur ins NJAS-Archiv nachschieben, wohin ich auch
schon den zu grossen Wert 25 für n=14 zur Berichtigung gegeben habe,
da ja nach Helmut Richters Beispiel G(14) = 24 ist, falls nicht jemand was
noch kleineres findet.
Gruss,
Rainer Rosenthal
r.ros...@web.de
Philipp Zumstein
<r.ros...@web.de> wrote:
>Nun kann ich darin aber unseren Zahlenkreis bzw. die von Dir angegebene
>Aufgabe 4 nicht finden. Kannst Du bitte Deine Referenz angeben ? Ich
>werde dies als Korrektur ins NJAS-Archiv nachschieben, wohin ich auch
>schon den zu grossen Wert 25 für n=14 zur Berichtigung gegeben habe,
>da ja nach Helmut Richters Beispiel G(14) = 24 ist, falls nicht jemand was
>noch kleineres findet.
Etwas kleineres für n=14 ist nach meinen Beiträgen nicht möglich. Weil
der Durdchschnitt d(14)=3/2*15=22.5 ist. Ein Zahlenkreis mit G(14)=23
gibt es nicht nach meiner Begründung weil 14>6 und sich so eine
Zahlenkreis bereits ab dem 6. Glied wiederholen würde.
Falls du meiner Begründung Glauben schenken willst, kannst du alle
(zumindest) alle geraden Werte von Helmut (bis 24) als gesichert
betrachten. Für diese gilt nämlich (ausser der 6) G(2*k) = 3*k+3.
Gruss
Philipp
Sebastian Kapfer
writes...
| http://www.bundeswettbewerb-mathematik.de/wettbewerb/wettb2001.htm
Wie bereits gemailt, läuft schon der BWM 2002. War eine blöde
Formulierung von mir...
Aber ich hätte mal eine Frage zu deiner Formulierung:
| It has to be proved that there are at least 3 consecutive sticks with
| total length not less than 20.
Der O-Text lautet:
| Man beweise, dass es dann stets in diesem Zwölfeck drei aufeinander
| folgende Seiten gibt, deren Gesamtlänge größer als 20 ist.
Ich lese da ein s_max > 20 raus, aus deiner englischen Formulierung eher
ein s_max >= 20. Stimmt das? Ich mache relativ wenig Mathematik auf
Englisch :)
Für den Wettbewerb macht das einen wesentlichen Unterschied, s_max >= 20
ist nämlich viel einfacher als > 20. Wie auch immer, ich bilde mir ein,
eine (eigene!) Lösung gefunden zu haben, auch für > 20.
Rainer Rosenthal
Sebastian Kapfer <skapf...@yahoo.de>
>
> Aber ich hätte mal eine Frage zu deiner Formulierung:
>
> | It has to be proved that there are at least 3 consecutive sticks with
> | total length not less than 20.
>
> Der O-Text lautet:
>
> | Man beweise, dass es dann stets in diesem Zwölfeck drei aufeinander
> | folgende Seiten gibt, deren Gesamtlänge größer als 20 ist.
>
> Ich lese da ein s_max > 20 raus, aus deiner englischen Formulierung eher
> ein s_max >= 20. Stimmt das? Ich mache relativ wenig Mathematik auf
> Englisch :)
>
> Für den Wettbewerb macht das einen wesentlichen Unterschied, s_max >= 20
> ist nämlich viel einfacher als > 20. Wie auch immer, ich bilde mir ein,
> eine (eigene!) Lösung gefunden zu haben, auch für > 20.
Hallo Sebastian,
au weia, Du hast völlig recht. Die Aufgabe im Wettbewerb ist ja wirklich
in voller Härte formuliert. Also muss ich das ebenfalls noch berichtigend
nachtragen. Danke.
Hier in der Gruppe gibt es von Philipp Zumstein die Behauptung, er habe
den Beweis für allgemeines gerades n = 2*k, dass G(n) = 3*k+3. Für
n=10 springt dabei G(n)=18 heraus.
Verstanden habe ich das allerdings noch nicht. Muss es wohl mal ernsthaft
durchlesen ...
Aber: Immer her mit Deinem Beweis für n=12 bitte !
Gruss,
Rainer Rosenthal
r.ros...@web.de
Philipp Zumstein
<r.ros...@web.de> wrote:
>Hier in der Gruppe gibt es von Philipp Zumstein die Behauptung, er habe
>den Beweis für allgemeines gerades n = 2*k, dass G(n) = 3*k+3. Für
>n=10 springt dabei G(n)=18 heraus.
>Verstanden habe ich das allerdings noch nicht. Muss es wohl mal ernsthaft
>durchlesen ...
Achtung!
Diese Behauptung habe ich nur halb bewiesen. Der schwierigere Teil
bleibt noch. Ich habe nur bewiesen dass G(2*k) >= 3*k+3. Damit das
Gleichheitszeichen gilt muss man noch so einen Zahlenkreis finden
(z.B. die Computerprogramme liefern einem ja solche Beispiele). Die
Gleichung ist nur eine Vermutung von mir (gestützt auf die
Computerergebnisse von H.R.). Die Ungleichung kann ich beweisen. Falls
man einen allgemeinen Zahlenkreis konstruieren kann für den G(2*k) =
3*k+3 gilt dann gilt nach meinem Beitrag, dass es keinen Zahlenkreis
gibt, der minimaler ist.
Gruss
Philipp
Philipp Zumstein
<hzum...@bluewin.ch> wrote:
Leider stimmt der Beweis für n=7 nicht. Aber, ich weiss nicht, ob dies
hier jemanden interessiert. Aber vollständigkeitshalber wollte ich
dies mitteilen.
>n=7:
>Falls es einen Zahlenkreis mit s_max=13 gibt, dann wechseln sich die
>Dreiersummen ab mit den Werten 12, 11, 13, wobei gleichviele Male die
>11 wie die 13 vorkommt.
Falsch!
Es gibt vier Möglichkeiten:
1x12er Gruppe
3x11er Gruppe
3x13er Gruppe
oder
3x12er Gruppe
2x11er Gruppe
2x13er Gruppe
oder
1x10er Gruppe
3x13er Gruppe
1x11er Gruppe
2x12er Gruppe
oder
1x9er Gruppe
3x13er Gruppe
3x12er Gruppe
> [Beweis für die ersten beiden Fälle]
Der vierte Fall kann ich auch beweisen, der dritte sieht mir aber
nicht ganz einfach aus.
Gruss
Philipp
Ralf Muschall
> Das meine ist schon bei 22, umd probiert auch alles durch (allerdings in
> einer intelligenteren Reihenfolge).
D.h. meins ist irgendwo ganz krank (brute force *muss* ja eigentlich
alles finden).
Inzwischen habe ich manuell ein paar obere Schranken gefunden.
n=3k: 5k+1
n=3k+1: 5k+4
n=3k+2: 5k+5
Belegungen (alles nullbasiert, man addiere 1 in jedem Feld, um zur
Originalformulierung oder den o.g. Summen zu kommen):
n=3k: a[3i]=i, a[3i+1]=2ki-1, a[3i+2]=2k+i
n=3k+1: a[3i]=i, a[3i+1]=2k-i, a[3i+2]=2k+i+1
n=3k+2: a[3i]=i, a[3i+1]=2k+i+1, a[3i+2]=2k-i
Die 3k+1-Variante sieht besonders suboptimal aus (hat ein paar sehr
kleine Dreiersummen).
Das gibt:
n 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 50
os(n) 11 14 15 16 19 20 21 24 25 26 29 30 31 34 35 85
bm(n) 11 14 15 16 18 20 21 23* ??
pz(n) 11 14 15 16 18 20 21 23 25 27 28 29 31 33 35 90
os=obere Schranke nach o.g. Formeln bm=bekanntes Maximum nach brute
force, die 23 dort ist 22, falls Helmut rechthat und mein
brute-force-Programm spinnt. pz sind die Zahlen von Philipp aus
<ju8c2u0dfsd9gvtop...@4ax.com>. Asymptotisch hat man
jedenfalls os(n)=5n/3+const.
Helmut Richter
<hzum...@bluewin.ch> wrote:
>Falls du meiner Begründung Glauben schenken willst, kannst du alle
>(zumindest) alle geraden Werte von Helmut (bis 24) als gesichert
>betrachten. Für diese gilt nämlich (ausser der 6) G(2*k) = 3*k+3.
So, wie der Algorithmus entworfen ist, soll er *nur* optimale Werte
finden. Findet er nicht optimale, ist er falsch programmiert. Anstatt
Plilipps Begründung kann man also auch meinem Programm glauben. Na,
dann vielleicht doch besser Philipps Begründung.
Helmut Richter
Helmut Richter
<r.ros...@web.de> wrote:
>Daniel Grund <Daniel...@gmx.de> wrote
>> Soooooo!!!
>> Mein Programm ist jetzt fertig, hat aber noch einen kleinen Fehler
>> (Algorithmus noch nicht 100% richtig). Bis jetzt liefert es ziemlich gute
>> _obere Schranken_ für f(n).
>>
>> Auf http://www.uni-karlsruhe.de/~uy7y/zahlen.txt gibts diese für n=3..200.
Berauschend sind die Schranken aber nicht. Für 25 steht 44 drin, aber
es geht auch mit 41:
1 5 24 10 7 22 11 8 20 12 9 19 13 6 17 18 4 16 21 3 15 23 2 14 25
Ich bin ziemlich sicher, dass es nicht besser geht, kanns aber nicht
beweisen. Und das Programm, das die Lösung gefunden hat, hat auch
nicht alles abgesucht.
>Ich hätte nicht gedacht, dass die Programmiererzunft so schnell zu
>Ergebnissen kommt bei den grossen n.
Nu ja, *irgendwelche* Schranken sollten sich schnell finden lassen.
Helmut Richter
Philipp Zumstein
(Helmut Richter) wrote:
>On Mon, 24 Dec 2001 10:40:03 +0100, Rainer Rosenthal
><r.ros...@web.de> wrote:
>
>>Daniel Grund <Daniel...@gmx.de> wrote
>>> Soooooo!!!
>>> Mein Programm ist jetzt fertig, hat aber noch einen kleinen Fehler
>>> (Algorithmus noch nicht 100% richtig). Bis jetzt liefert es ziemlich gute
>>> _obere Schranken_ für f(n).
>>>
>>> Auf http://www.uni-karlsruhe.de/~uy7y/zahlen.txt gibts diese für n=3..200.
>
>Berauschend sind die Schranken aber nicht. Für 25 steht 44 drin, aber
>es geht auch mit 41:
>1 5 24 10 7 22 11 8 20 12 9 19 13 6 17 18 4 16 21 3 15 23 2 14 25
>
>Ich bin ziemlich sicher, dass es nicht besser geht, kanns aber nicht
>beweisen. Und das Programm, das die Lösung gefunden hat, hat auch
>nicht alles abgesucht.
Ich versuch mich mal mit einem Beweis:
Der Durchschnitt der Dreiersummen beträgt 3/2*26 = 39. Einen
Zahlenkreis mit maximaler Dreiersumme von 39 kann es nicht geben (c.f.
deine Erklärung).
Angenommen es gebe einen Zahlenkreis mit 40 als maximale Dreiersumme.
Dann kommt darin sicherlich auch mal die 1 vor:
...,1,a,b,k,...
Es folgt 1+a+b+k <= 41. [ Alle 25 Zahlen zusammen ergeben die Summe
s_ges = 25 * 26 / 2 = 325.] Für die restlichen 21 Zahlen ergibt sich
somit die Summe von s_rest >= 325 - 41 = 284. Diese Summe kann man
aber auch als die Summe von 7 Dreiersummen sehen. Für diese
Dreiersummen ergibt sich demnach einen Durchschnittswert von d >=
(325-41) / 7 = 40.57. Weil aber die Dreiersummen nach Annahme alle
kleiner (oder gleich) 40 sind, kann sich dieser Durchschnitt niemals
einstellen. Widerspruch.
Stimmt dies? Wäre schön, wenn es stimmt, aber ich bin mir irgendwie
nicht sicher. Dies sieht fast zu einfach aus; im Gegensatz dazu welch
komplizierte Dinge ich sonst so probiert habe.
Gruss
Philipp
Kurt Stege
>Problem: Suche f(n) mit:
>
>f(n):= min ( max S(p,i) )
> p i
>
>S(p,i):= p(i mod n) + p((i+1) mod n) + p((i+2) mod n)
>
>p Permutation der Länge n (zero-based, wegen modulo)
>i E {0..n-1)
Und Rainers G(n) ist dann f(n) + 3.
Bitte nicht schlagen, wenn ich gelegentlich mal (in anderen
Postings) zero-based und one-based durcheinanderschmeiße...
>Was wir bisher wissen:
>
>1) f(n) für n=3..22
>
>2) f(n) >= ceil( 3*(n+1)/2 )
Wo kommt dies eigentlich her? Das Posting ist mir
entweder durch die Lappen gegangen, oder es ist eines
der wenigen Postings, die ich als noch ungelesen liegengelassen
habe.
>3) Zwei aufeinanderfolgende 3-er:
>a+b+c = b+c+d geht nur für a=d also nur mit n=4.
Du meinst für n=3.
>4) Formal beweisen könnt ich es nicht auf die Schnelle aber:
>f(n+1) > f(n)
Da würde ich lieber nicht meine Hand drauf verwetten. Es klingt
zwar auf den ersten Blick plausibel, aber mir sind hier zuviele
Eigenschaften im Spiel, die davon abhängig sind, ob n durch
2 oder durch 3 teilbar ist. f(n+6) > f(n) würde ich auch erwarten.
Und wahrscheinlich stimmt auch f(n+1) > f(n), aber ich halte
Zweifel für gerechtfertigt.
>Was ich gerne wissen würde ist ob folgendes gilt:
>
>5) Wenn für ein p gilt dass
> f(n) = max S(p,i)
>folgt dann daraus, dass ein i existiert mit
> p(i)=0 und ( p(i+1)=n-1 oder p(i-1)=n-1 )
Willkürlich rausgegriffen ein Beispiel für n=10
1 7 9 2 6 8 4 3 10 5 (one-based)
>6) Oder gilt wenigstens?
>Es existiert ein p mit f(n) = max S(p,i) so dass
>p(i)=0 und ( p(i+1)=n-1 oder p(i-1)=n-1 )
Wahrscheinlich, habe aber noch keine Beweisidee.
>Hat jemand sonstige Vorschläge, die man noch so anschauen könnte, die
>einen Vorteil bringen?
>
>
>Trotz 3km Text einen geruhsamen Abend
Die 2.5 km von vor-7 und 7 waren mir dann doch zuviel...
Hier noch etwas "Müll", den ich schon versehendlich zusammengeschrieben
hatte, und hier nun doch nicht reinpaßt. Wenn also noch jemand kleines
Datenmaterial zum Spielen braucht:
Für n=10 gibt es zum Beispiel genau sechs Lösungen, bei denen
alle 3-er (ich nenne sie Triple-Summen) zwischen 15 und 18 liegen:
1 5 9 4 3 8 7 2 6 10
1 5 10 3 4 8 6 2 7 9
1 6 10 2 4 9 5 3 7 8
1 8 7 3 5 9 4 2 10 6
1 9 7 2 6 8 4 3 10 5
1 10 6 2 7 8 3 4 9 5
(one-based, meine Permutationen fangen oBdA alle mit 1 an,
es sind nur drei Lösungen, weil ich die gespiegelten auch aufgeführt
habe.)
Gruß,
Kurt.
Kurt Stege
>Problem: Suche f(n) mit:
>
>f(n):= min ( max S(p,i) )
> p i
>
>S(p,i):= p(i mod n) + p((i+1) mod n) + p((i+2) mod n)
>
>p Permutation der Länge n (zero-based, wegen modulo)
>i E {0..n-1)
Das ist doch eine schöne, knappe, präzise Formulierung von f().
Du verstehst p als Permutation von 0...n-1 nach 0...n-1.
Wenn ich gelegentlich mal Permutationen von 0...n-1 nach 1...n
verwende, dann bitte ich um Nachsicht.
>Was wir bisher wissen:
1)...4) gesnippt.
Was ich inzwischen weiß, möchte ich nochmal kurz zusammenfassen.
Alles, was ich hier schreibe, gilt nur für n>=4. Bei n=1...3
ist das ganze langweilig; es gibt nur wenige Permutationen, und
alle S(p,i) sind nur noch von n abhängig.
Zunächst einmal noch zwei Funktionen. Sei p eine Permutation,
dann sei
min_S(p) := min S(p,i)
und
max_S(p) := max S(p,i)
min_S(n) := min S(p) über alle Permutationen p
max_S(n) := max S(p)
Ich habe ein Programm mit Brute-Force-Algorithmus, dem ich
die Parameter n, min_S(n) und max_S(n) vorgebe, das mir
dann alle Permutationen p berechnet, die diese Einschränkungen
erfüllen. Den genauen Algorithmus hatte ich gerade in einem
anderen Posting geschildert.
Hier soll es jetzt um eine nachvollziehbare mathematische
Analyse gehen.
Klar ist:
a) \sum_i S(p,i) = n*(n-1)*(3/2)
Oder anders ausgedrückt: Die durschnittliche Summe S(p,i) von
drei aufeinanderfolgenden Zahlen ist exakt (n-1)*(3/2).
Diesen Durchschnittswert brauche ich noch häufiger, deshalb
gebe ich ihm einen Namen:
avg_S(n) = (n-1)*(3/2).
n avg_S(n)
4 4.5
5 6
6 7.5
7 9
8 10.5
9 12
10 13.5
11 15
12 16.5
50 73.5
Klar ist auch, daß min_S(n) <= avg_S(n) <= max_S(n).
Nun gilt auch (und hier brauche ich die Einschränkung n>=4),
daß S(p,i) != S(p,i+1) gilt, denn sonst wäre p(i-1) = p(i+2).
Alle i sind immer modulo n; das lasse ich der Übersicht halber
lieber weg.
Das heißt sogar, das min_S(n) != max_S(n) sein muß, also:
min_S(n) < avg_S(n) < max_S(n)
Nun kommt eine große Fallunterscheidung:
Ist n gerade, dann ist avg_S(n) keine ganze Zahl.
Dann sind
aplus(n) := avg_S(n) + 0.5 und
aminus(n) := avg_S(n) - 0.5 = aplus(n) - 1
natürliche Zahlen.
max_S(n) >= aplus(n) hatten wir schon. Wäre sogar
max_S(n) == aplus(n), würde es eine Permutation p geben, für das
S(p,i) = aplus, aminus, aplus, aminus immer abwechselnd wäre.
Man kann sich wahrscheinlich schnell überlegen, daß es eine
solche Permutation nicht gibt.
Dann ist aber sogar:
max_S(n) >= aplusplus(n) := aplus(n) + 1 = avg_S(n) + 1.5
Aus Symmetriegründen ist (womoglich für eine andere Permutation):
min_S(n) <= aminusminus(n) := amins(n) - 1 = avg_S(n) - 1.5
Mein numerisches Datenmaterial liefert (bei geraden n)
jeweils die folgende Anzahl von Permutationen, die gleichzeitig
avg_S(n) - 1.5 == min_S(n) < max_S(n) == avg_S(n) + 1.5
erfüllen:
n anz
4 6 (hier ist jede Permutation eine Lösung)
6 20
8 14
10 6
12 176
14 6
16 6
18 308
20 6
22 6
24 256
26 6
Dabei habe ich eine besondere Art, die Anzahl Lösungen zu zählen:
p(0) = 0 lege ich fest; Verschiebungen zähle ich also nicht mit,
aber Spiegelungen zähle ich mit; die "sechs" Lösungen sind also
in Wirklichkeit nur drei.
Für n=26 zum Beispiel:
0 13 23 1 15 20 3 16 17 4 18 14 6 19 11 7 21 8 9 22 5 10 24 2 12 25
0 13 24 1 14 21 2 16 18 4 17 15 5 19 12 7 20 9 8 22 6 10 23 3 11 25
0 14 22 2 15 19 3 17 16 5 18 13 6 20 10 8 21 7 9 23 4 11 24 1 12 25
0 25 11 3 23 10 6 22 8 9 20 7 12 19 5 15 17 4 18 16 2 21 14 1 24 13
0 25 12 1 24 11 4 23 9 7 21 8 10 20 6 13 18 5 16 17 3 19 15 2 22 14
0 25 12 2 24 10 5 22 9 8 21 7 11 19 6 14 18 4 17 16 3 20 15 1 23 13
Die nachfolgende Strategie, hier für n=26 dargestellt, funktioniert
für jedes gerade n, das nicht durch 3 teilbar ist:
00 .. .. 01 .. .. 03 .. .. 04 .. .. 06 .. .. 07 .. .. 09 .. .. 10 .. .. 12 ..
.. 13 .. .. 15 .. .. 16 .. .. 18 .. .. 19 .. .. 21 .. .. 22 .. .. 24 .. .. 25
.. .. 23 .. .. 20 .. .. 17 .. .. 14 .. .. 11 .. .. 08 .. .. 05 .. .. 02 .. ..
Man fängt bei 0 an, verteilt an jeden dritten Platz eine Zahl. Alle
zwei Zahlen läßt man eine Zahl ausfallen. Wenn man das zweite Mal rum ist,
hat man n-1 verteilt. Dann beginnt man in umgekehrter Reihenfolge in die
übriggebliebenen Plätze von oben nach unten die letzen Zahlen reinzupacken.
Übersichtlich in drei Zeilen zu schreiben, die am Schluß zusammengeschoben
werden zu:
00 13 23 01 15 20 03 16 17 ...
n = 10 (als Beispiel für 6m-2):
00 .. .. 01 .. .. 03 .. .. 04
.. .. 06 .. .. 07 .. .. 09 ..
.. 08 .. .. 05 .. .. 02 .. ..
Für n der Form 6m geht das sicherlich ähnlich, aber das mache
ich nicht mehr heute nacht.
Wenn man diese Muster sauber durchformuliert und etwas rumrechnet,
kann man sicherlich nachweisen, daß damit
avg_S(n) - 1.5 == min_S(n) < max_S(n) == avg_S(n) + 1.5
erreicht wird.
Damit ist die Aufgabe für gerade n abgeschlossen!
Es gilt f(n) = avg_S(n) + 1.5 = (n)*(3/2).
Irgendwie ist f(n) langweilig, zumindest für gerade n...
Nun der Fall für ungerade n:
Nun ist avg_S(n) = (n-1)*(3/2) eine natürliche Zahl, und
es gilt immer noch:
min_S(n) < avg_S(n) < max_S(n)
Nun seien
aplus(n) := avg_S(n) + 1.0 = (n-1)*(3/2) + 1 und
aminus(n) := avg_S(n) - 1.0 = aplus(n) - 2 = (n-1)*(3/2) - 1
(also 1.0 statt 0.5 im Fall gerade n)
Dann gilt, wie gehabt:
max_S(n) >= aplus(n) und min_S(n) <= aminus(n).
Der Fall n ungerade ist viel interessanter als der für gerade n,
denn hier gibt es tatsächlich Permutationen, die die Gleichheit
erzielen, und zwar für n=5, n=9 und n=15.
Für andere n (ich habe allerdings noch nicht weit gesucht),
habe ich dieses Phänomen noch nicht gefunden.
Hier die 4 Lösungen für n=15 mit 20...22
0 8 12 1 9 10 3 7 11 4 5 13 2 6 14
0 9 11 2 8 10 4 6 12 3 5 14 1 7 13
0 13 7 1 14 5 3 12 6 4 10 8 2 11 9
0 14 6 2 13 5 4 11 7 3 10 9 1 12 8
Allerdings scheint es mit aplusplus und aminusminus, also
die Grenzen wieder um eins weitergeseckt, wieder Lösungen
zu geben, und zwar so richtig viele:
Bei zum Beispiel n=23 gibt es 8562 Permutationen mit 31...35,
aber, wie gesagt, keine einzige mit 0...34.
aplusplus(n) = (n-1)*(3/2) + 2 = n*(3/2) + 0.5
Ob immer, oder ob dies auch irgendwann zusammenbricht,
werde ich heue nacht nicht mehr untersuchen. Wenn es für
größere ungerade n keine Überraschungen mehr gibt (entweder
doch schon mit aplus oder noch nicht einmal mehr mit aplusplus),
sieht die f(n) Funktion wie folgt aus:
f(1) = 1
f(2) = 3
f(3) = 6
f(n) = n*3/2 für gerade n
f(5) = 7
f(9) = 13
f(15) = 22
f(n) = n*3/2 + 1/2 für alle anderen n.
Die letzte Zeile ist Spekulation; dort ist nur f(n) >= n*3/2 - 1/2
gesichert. Alles andere scheint mir sicher zu sein; wenn ich nicht
schon einfach zu müde bin.
>1) f(n) für n=3..22
Stimmen meine Ergebnisse hiermit überein?
Ich habe inzwischen den Überblick verloren.
>2) f(n) >= ceil( 3*(n+1)/2 )
Ich hatte mal gefragt warum. Jetzt habe ich mir
selbst die Antwort gegeben.
Gute Nacht,
Kurt.
Kurt Stege
Vielen Dank Rainer für Deine "Einladung".
"Rainer Rosenthal" <r.ros...@web.de> wrote:
>Helmut Richter <a28...@lxhri01.lrz.lrz-muenchen.de>
>
>> Das meine ist schon bei 22, umd probiert auch alles durch (allerdings in
>> einer intelligenteren Reihenfolge).
>>
>> http://www.lrz-muenchen.de/~hr/tmp/zahlenkreis bekommt die Ergebnisse.
Da muß ich gleich auch mal reinschauen.
>in der Gruppe de.rec.denksport hat Kurt Stege ein offenbar
>sehr leistungsfähiges Programm aus dem Boden gestampft,
>das für n=50 den Max-Wert 78 liefert.
Dann muß ich das Programm wohl mal kurz vortellen. Es ist Weihnachten
entstanden, weil Rainers Weihnachtsaufgabe in drs so kompliziert war,
daß ich auf Anhieb keine vernünftige per Hand konstruierte Lösung
gefunden hatte, und ich deshalb einen Brute-Force-Algorithmus habe
laufen lassen.
Ich habe offenbar zwei Tricks, die in Euren Brute-Force-Programmen
nicht drin sind.
1. Wenn ich eine Lösung für n=50 mit Max-Wert 78 suche, brauche ich
auch lange. Wenn ich aber eine Lösung mit Max-Wert 78 und Min-Wert 75
suche, bin ich in einer halben Stunde komplett durch (und habe die
ersten drei Lösungen nach wenigen Sekunden, und finde ganz am Schluß
nochmal dieselben drei Lösungen in anderer Reihenfolge.).
2. Wenn ich den Max-Wert von 78 vorgebe, nutze ich eine einfache Abschätzung
aus: Der Durchschnittswert aller Triple-Summen liegt ja bei
n*(n+1*(3/2) = 76.5. Wenn die bisherigen Triple-Summen aufsummiert so
klein sind, daß selbst für den optimistischten Fall, daß bis zum Schluß
nur noch Triple-Summen von dem vorgegebenen Max-Wert 78 vorkommen, und
dann immer noch nicht der Durchschnittswert von 76.5 erreicht wird,,
naja, dann war der Anfang der bisherigen Permutation falsch; sie kann nicht
mehr zu einer Lösung führen.
Wenn ich Lösungen suchen will (bei mittelgroßen n wie n=50) suche
ich nach engen Intervallen; bei Minwert=75, Maxwert=78 finde ich
dann Lösungen. Dann gibt es für jede Position innerhalb der Permutation
zunächst vier Möglichkeiten, damit die eine dieser vorgegebenen Summen
erreicht wird. Eine davon wurde schon direkt vorher (drei Postionen
vorher) verbraucht, bleiben also im rechenintensivsten Fall drei
Möglichkeiten; oftmals weniger. Aus 50! Permutationen (10^64) werden
dann viel viel weniger als 3^50 (10^23) Kombinationen fällig. So viel
weniger, daß mein Single-User-PC in einer halben Stunde alle durch hat.
Wenn ich nachweisen will, daß es keine Lichterkette (so hat Rainer
die Permutation in dard genannt) mit 77 oder kleiner gibt, setze
ich den Minwert auf 0, und den Maxwert auf 77. Dann greift nämlich
die zweite Abschätzung extrem gut: Selbst wann 49 Triplesummen
exakt den Wert 77 haben sollten (wir wissen ja inzwischen, das die
77 sogar nur jedes zweite mal auftreten kann), muß bereits die allererste
Triple-Summe 52 sein. Bei allen kleineren Triplesummen kann der
Durchschnittswert von 76.5 nicht mehr erreicht werden, ohne nicht mindestens
einmal 78 oder noch mehr zu haben. Für n=50 und das Intervall 0...77
braucht derselbe PC ebenfalls eine halbe Stunde, um alle Kombinationen
durchprobiert zu haben, und zu wissen, das es keine Lösung gibt.
Den Sourcecode brauche ich jetzt wahrscheinlich nicht mehr zu posten,
denn wie man die Permutationen abklappert, wie ein Backtracking-Algorithmus
aussieht, wisst ihr mathematischen Programmierer sowieso alle.
Ich versuche gleich noch etwas Kombinatorik zu treiben, in einem
anderen Posting, um auch am Schreibtisch, also hier auf dem Bildschirm,
nachzuweisen, daß es Rainers G(50) >= 78 ist. G(78) <= 78 wurde ja
schon hier durch Rainers Folge und in dard durch meine Folge auch
mathematisch haltbar (durch Beispiel) bewiesen.
>Ich habe ihm dazu schon gratuliert, allerdings mit etwas
>belegter Stimme, denn ich war doch sooo stolz, dass ich das
>Ergebnis auch gefunden hatte, sogar mit Kopfrechnen und
>einer netten Idee.
>Es hat sich also gelohnt, die de.rec.denksport-Köpfe mit zum
>Qualmen zu bringen ! Weil die Leserschaft aber doch nicht
>gerade deckungsgleich ist, setze ich meine Info zur Lösung
>G(50) <= 78 hierher.
Stimmt. Die Leserschaft ist nicht deckungsgleich. In dard sitzen
zum einen Rätsellöser im Sinne von herkömmlichen Rätseln, und
zum anderen Mathematiker, die den Sinn für Spaß behalten haben.
Viele der Mathematiker in dard meiden diese Gruppe, weil hier
ziemlich viel Traffic ist, der jeden Tag merkbare Downloadzeit
und noch viel mehr Überfliegzeit kostet. Zumindest gilt das für
mich so.
>Die Begründung von Kurt Stege dafür, dass
>G(50) = 78 sein muss, habe ich noch nicht nachvollzogen, aber
>es leuchtet sehr ein, dass es eine nur aus Dreiersummen 76 und
>77 bestehende Lösung nicht geben wird.
Meine Begründung ist ja auch nicht "nachvollziehbar". Ich behaupte
ja einfach nur, daß mein Programm alle relevanten Kombinationen
durchprobiert hat, und eben keine Lösung gefunden hat.
Ich könnte auch ein Logfile produzieren lassen, das vielleicht als
mathematischer Beweis durchgehen könnte, zumindest formal. Aber
dieser Beweis wäre nur speziell für n=50, und extrem lang und unelegant...
Ich befürchte, ich komme heute nacht nicht mehr ins Bett, weil
ich durch das Lesen dieses ganzen Threads irgendwie das Gefühl habe,
daß völlig klar ist, daß eine Lösung mit G(50)=77 nicht bestehen kann.
Hier schon mal ein paar Stichwörter:
- Der Durchschnitt ist 76.5.
- Zwei aufeinanderfolgende Triple-Summen können nicht denselben
Wert haben (für n>3). Dazu müssten nämlich die erste und vierte
Zahl von vier aufeinanderfolgenden Positionen identisch sein,
und das geht nur bei n<=3.
- Die 77 kann also nur jedes zweite Mal vorkommen.
- Um den Durchschnitt von 76.5 zu halten, muß also jedes zweite
Mal die 76 kommen.
- Eine Kette mit immer abwechselnd 76 und 77 kann es nicht geben;
das kann man sogar per Hand durchprobieren.
Gruß,
Kurt.
Philipp Zumstein
wrote 250 lines:
>a) \sum_i S(p,i) = n*(n-1)*(3/2)
>
>Oder anders ausgedrückt: Die durschnittliche Summe S(p,i) von
>drei aufeinanderfolgenden Zahlen ist exakt (n-1)*(3/2).
>
>Diesen Durchschnittswert brauche ich noch häufiger, deshalb
>gebe ich ihm einen Namen:
>
>avg_S(n) = (n-1)*(3/2).
>
>Ist n gerade, dann ist avg_S(n) keine ganze Zahl.
>Dann sind
>aplus(n) := avg_S(n) + 0.5 und
>aminus(n) := avg_S(n) - 0.5 = aplus(n) - 1
>natürliche Zahlen.
>
>max_S(n) >= aplus(n) hatten wir schon. Wäre sogar
>max_S(n) == aplus(n), würde es eine Permutation p geben, für das
>S(p,i) = aplus, aminus, aplus, aminus immer abwechselnd wäre.
>
>Man kann sich wahrscheinlich schnell überlegen, daß es eine
>solche Permutation nicht gibt.
Ja. Dies stimmt für n=/=3 (wenn ich das jetzt richtig übersetzt habe
in zero-based). Also ich meine so etwas, wie: 1,4,5,2,3,6. Die
Begründung, warum es nicht funktioniert läuft daraus auf, dass so eine
alternierende Dreiersummenkonstellation sich genau nach dem sechsten
Element wiederholt. Also muss dort der Kreis geschlossen sein, sonst
funktioniert's nicht.
>Wenn man diese Muster sauber durchformuliert und etwas rumrechnet,
>kann man sicherlich nachweisen, daß damit
>
>avg_S(n) - 1.5 == min_S(n) < max_S(n) == avg_S(n) + 1.5
>
>erreicht wird.
Naja, ich hab's nicht geschafft. Das Muster erscheint mir auch nicht
"soooo" einfach.
>Damit ist die Aufgabe für gerade n abgeschlossen!
>Es gilt f(n) = avg_S(n) + 1.5 = (n)*(3/2).
>
>Irgendwie ist f(n) langweilig, zumindest für gerade n...
Uff... Ja wenn du mir das Muster zeigen kannst...
>Der Fall n ungerade ist viel interessanter als der für gerade n,
>denn hier gibt es tatsächlich Permutationen, die die Gleichheit
>erzielen, und zwar für n=5, n=9 und n=15.
dies ist wohl one-based, denn diese Zahlen stimmen mit meinen überein.
>Für andere n (ich habe allerdings noch nicht weit gesucht),
>habe ich dieses Phänomen noch nicht gefunden.
Ich kann - glaub ich - beweisen, dass für n=6*k+1 (one-based) die
Gleichheit nicht erfüllt werden kann.
>f(1) = 1
Was meinst du damit?
0,1 hat Dreiersumme von 1? Aber 1+0+1=2.
Man könnte natürlich auch noch soetwas wie f(0)=0 hinzunehmen.
Achtung, deine Nummerierung ist wohl etwas durcheinandergekommen (oder
meine):
>f(2) = 3
G(3) = 3
>f(3) = 6
G(4) = 9
>f(n) = n*3/2 für gerade n
G(2*k) = 3*k+3, für 4 <= k <= 12
>f(5) = 7
G(5) = 10
>f(9) = 13
G(9) = 16
>f(15) = 22
G(15) = 25
>f(n) = n*3/2 + 1/2 für alle anderen n.
>
>Die letzte Zeile ist Spekulation; dort ist nur f(n) >= n*3/2 - 1/2
>gesichert. Alles andere scheint mir sicher zu sein; wenn ich nicht
>schon einfach zu müde bin.
Ja. Dies hatte ich auch schon mal behauptet an etwas anderer Stelle
>>1) f(n) für n=3..22
>
>Stimmen meine Ergebnisse hiermit überein?
>Ich habe inzwischen den Überblick verloren.
Hoffe konnte dir den Überblick etwas zurück geben. Sind deine
Ergebnisse auch irgendwie zugänglich? Oder vielleicht das Programm?
Dann könnte ich noch etwas damit herumspielen. Übrigens die untere
Schranke (habe deine Bezeichnung vergessen) ist nicht beliebig. Nach
meinen Überlegungen ist testest du mit k=25, obere Schranke=40, untere
Schranke=27 alle Möglichkeiten durch. Aber solch einen Zahlenkreis
gibt es m.M. nicht.
Gruss
Philipp
Philipp Zumstein
<hzum...@bluewin.ch> wrote:
> snip
>> snip
>>> snip
Ich habe den Beweis - glaub ich - einfacher und allgemeiner
hingekriegt:
Für n = 6*k+1 ist die Durchschnittdreiersumme d = 3/2*(6*k+2) = 9*k+3,
alle Zahlen zusammen ergeben s_ges = (6*k+1)*(6*k+2) / 2 =
(6*k+1)*(3*k+1) = 18*k^2+9*k+1.
Irgendwo steht die Eins. Die restlichen Zahlen summieren sich auf zu
s_rest = 18*k^2+9*k.
Diese 6*k Zahlen bilden 2*k Dreiersummen. Auf solch eine Dreiersumme
fallen im Durchschnitt s_rest / (2*k) = (18*k^2+9*k) / (2*k) =
9*k+4.5.
==> G(6*k+1) >= 9*k+5.
Setze k=4 ein, dann erhält man den Spezialfall G(25) >= 41.
Kann dies vielleicht jemand durchdenken? Stimmt meine Argumentation?
Gruss
Philipp
Kurt Stege
Zunächst vorweg noch ein paar Begriffsklärungen:
Für mich war und ist n immer die Anzahl der Kanten des n-Ecks.
Diese Kanten oder Positionen kann man durchnumerieren. Ob diese
von 0 bis n-1 oder von 1 bis n bezeichnet werden, ist egal, da
diese Postionsbezeichnungen bislang nur selten genutzt werden.
Ich numeriere die Positionen von 0 bis n-1.
Und dann gibt es noch die Werte, die an die Position geschrieben
werden. Auch diese können von 0 bis n-1 (zero-based) oder von
1 bis n (one-based) gewählt werden. In de.rec.denksport hatte
ich noch one-based gearbeitet; hier in dsm habe ich nach zero-based
konvertiert.
Der Unterschied zwischen zero-based und one-based liegt also
nur darin, daß jede Dreier-Summer bei one-based um 3 größer ist;
n bleibt unverändert die Anzahl. In dem ganzen Thread hat noch
keiner mit 0...n gearbeitet.
Die Funktion, die eine Postion auf einen Wert abbildet, wird hier
regelmäßig "Permutation" genannt. Wer jetzt Positionen von 0...n-1
und Werte von 1...n bezeichnet, hat mit dem engen Begriff Permutation
Probleme, aber wir sind hier ja alle Mathematiker und brauchen
uns deshalb nicht über Begriffe streiten.
Philipp Zumstein <hzum...@bluewin.ch> wrote:
>On Fri, 28 Dec 2001 04:19:13 +0100, Kurt Stege <kurt-...@online.de>
>wrote 250 lines:
>>max_S(n) >= aplus(n) hatten wir schon. Wäre sogar
>>max_S(n) == aplus(n), würde es eine Permutation p geben, für das
>>S(p,i) = aplus, aminus, aplus, aminus immer abwechselnd wäre.
>>
>>Man kann sich wahrscheinlich schnell überlegen, daß es eine
>>solche Permutation nicht gibt.
>
>Ja. Dies stimmt für n=/=3 (wenn ich das jetzt richtig übersetzt habe
>in zero-based). Also ich meine so etwas, wie: 1,4,5,2,3,6. Die
>Begründung, warum es nicht funktioniert läuft daraus auf, dass so eine
>alternierende Dreiersummenkonstellation sich genau nach dem sechsten
>Element wiederholt. Also muss dort der Kreis geschlossen sein, sonst
>funktioniert's nicht.
Mit n=/=3 meinst Du "n kein Vielfaches von 3"? Ist =/= ein
durchgestrichenes teilt-Zeichen? Hast Du n und 3 vertauscht?
Viel wichtigere Frage: Für n, die Vielfache von 6 sind, muß ich
mir also noch was überlegen, um die Ungleichheit zu zeigen?
>>Wenn man diese Muster sauber durchformuliert und etwas rumrechnet,
>>kann man sicherlich nachweisen, daß damit
>>
>>avg_S(n) - 1.5 == min_S(n) < max_S(n) == avg_S(n) + 1.5
>>
>>erreicht wird.
>
>Naja, ich hab's nicht geschafft. Das Muster erscheint mir auch nicht
>"soooo" einfach.
Gut. Dann werde ich mir etwas Mühe geben, hier den Durchbruch zu
schaffen.
>>Der Fall n ungerade ist viel interessanter als der für gerade n,
>>denn hier gibt es tatsächlich Permutationen, die die Gleichheit
>>erzielen, und zwar für n=5, n=9 und n=15.
>
>dies ist wohl one-based, denn diese Zahlen stimmen mit meinen überein.
Jein. Wie gesagt, interpretiere ich zerobased ala n Werte von
0 bis n-1.
>>Für andere n (ich habe allerdings noch nicht weit gesucht),
>>habe ich dieses Phänomen noch nicht gefunden.
>
>Ich kann - glaub ich - beweisen, dass für n=6*k+1 (one-based) die
>Gleichheit nicht erfüllt werden kann.
Yep. Ich werde jetzt auch anfangen, die sechs Fälle n=6*k+m für
m=0...5 einzeln zu untersuchen.
>>f(1) = 1
>
>Was meinst du damit?
>0,1 hat Dreiersumme von 1? Aber 1+0+1=2.
Nein, aber fast:
n = 1. Die "Lichterkette" hat eine Kerze mit Helligkeit 0.
Ergibt eine Dreiersumme von 0+0+0 = 0.
Also f(1) = 0, oder G(1) = 3.
Deine Lichterkette 0,1 gilt für n=2.
Also f(2) = 2 bzw. G(2) = 5.
Ich war wohl wirklich schon müde, gestern abend.
>Man könnte natürlich auch noch soetwas wie f(0)=0 hinzunehmen.
Einverstanden. Das ist auch nicht spitzfindiger, als die Werte
für 1 und 2 anzugeben.
>Achtung, deine Nummerierung ist wohl etwas durcheinandergekommen (oder
>meine):
f(n) ist zero-based, G(n) ist one-based. Es ist f(n)+3 = G(n).
(Nach meinem Verständnis von f() und G().)
>>f(2) = 3
>G(3) = 3
>>f(3) = 6
n = 3, Permutation 0,1,2 (bzw. 1,2,3)
f(3) = 3, G(3)=6.
(Jetzt kann ich wieder nachvollziehen, was ich eigentlich gerechnet
hatte: Bei f(1)...f(3) hatte ich, auch noch falsch, die G(n) ausgerechnet,
indem ich einfach die Summen von 1 bis n berechnet hab...)
>G(4) = 9
>>f(n) = n*3/2 für gerade n
>G(2*k) = 3*k+3, für 4 <= k <= 12
>>f(5) = 7
>G(5) = 10
>>f(9) = 13
>G(9) = 16
>>f(15) = 22
>G(15) = 25
Gut. Hier sind wir uns also einig.
>Hoffe konnte dir den Überblick etwas zurück geben.
Ja, vielen Dank.
>Übrigens die untere
>Schranke (habe deine Bezeichnung vergessen) ist nicht beliebig. Nach
>meinen Überlegungen ist testest du mit k=25, obere Schranke=40, untere
>Schranke=27 alle Möglichkeiten durch. Aber solch einen Zahlenkreis
>gibt es m.M. nicht.
k=25? Meinst Du n=25 oder n=2*k=50?
Die Schranken gebe ich derzeitig genauso wie das n willkürlich vor,
compiliere das Programm einmal und lasse es suchen.
Für n=25 kann ich, für möglichst wenig Rechenaufwand, zum einen
die Schranken 34...38 vorgeben, und finde 10220 Lösungen, die
da genau reinpassen. Also weiß ich: f(25) <= 38 bzw. G(25) <= 41.
Und dann lasse ich das Programm noch ein zweites Mal laufen mit
den Schranken 0...37 und finde in weniger als einer Sekunde
Laufzeit, daß es keine Lösung gibt. Also weiß ich: f(25) > 37).
Eine untere Schranke gebe ich selbst nicht mehr vor. Die findet
mein Programm schon von selbst: Wenn es anfängt, z.B. 0,1,22
zu probieren, stellt es folgende Überlegung an: Bislang tatsächlich
vergeben ist eine Dreiersumme von (nur) 23. Es kommen noch 24
weitere Dreiersummen hinzu, die laut Vorgabe nur höchstens 37
sein dürfen, und prinzipiell bestenfalls immer 37 und 36 abwechseln
können. Die verbleibenden 24 Dreiersummen können also abgeschätzt
werden durch 12*27+12*36 = 876. Insgesamt kann die Summer aller
25 Dreiersummen also nur höchstens 899 betragen. Sie muß aber genau
900 sein, also kann eine Lösung mit obere Schranke von 37 gar nicht
mit 0,1,22 anfangen.
Dieser Schneidemechanismus ist entscheidend für die Suche nach
den Lösungen, von denen wir hier alle vermuten, daß es sie
sowieso nicht mehr gibt.
Wichtig: Wenn die Folge z.B. mit 0,1,25 angesetzt wird, wird
automatisch die implizite Schranke von 24 (one-based 27)
angehoben, weil mit einer Dreiersumme von 26 schon der Großteil
des "Bonus" verbraucht ist.
Gruß,
Kurt.
Kurt Stege
>Sind deine Ergebnisse auch irgendwie zugänglich?
Ja. Ich poste sie hier...
>Oder vielleicht das Programm?
Bislang noch nicht. Den Algorithmus hatte ich schon gestern beschrieben.
Der Sourcecode kommt jetzt.
Disclaimer: Lieber zukünftiger Arbeitgeber. Ja, dieser Sourcecode
ist von mir. Aber so programmiere ich (normalerweise) nicht. So
sieht nur ein Sourcecode aus, wenn er geschrieben wird, um einmal
laufengelassen zu werden, und nach spätestens 24 Stunden gelöscht
wird. Referenzen für "echte" Praxisbeispiele auf Anfrage ;-)
Sprache ist C++, aber _nicht_ objektorientiert, auch wenn es
eine Klasse gibt. Läßt sich auch in C compilieren, wenn man ein
paar Doppelpunkte löscht...
Und das Programm ist nur vom Algorithmus her auf beste Performance,
beste Größenordnung, getrimmt. Ein linearer Faktor läßt sich durch
Code-Optimierung noch rausholen.
Gruß, und viel Spaß beim Experimentieren und Ausschlachten,
Kurt.
#include <stdio.h>
#include <math.h>
#include <time.h>
#define SUPPORT_REST_ABSCHAETZUNG() (1)
class lichter
{
public:
lichter(void);
void main(void);
private:
// Zeiten stammen aus einer Zeit, in der die Rest-Abschätzung
// noch nicht so präzise war. Werte sind one-based. Inzwischen
// sind alle Ein- und Ausgaben zero-based zu verstehen.
// Ergebnisse: (Zeiten mit Release-Version gemessen)
// 71...74 -> 0 Lösungen in 10 Sekunden
// 70...74 -> 0 Lösungen in 178 Sekunden.
// 1...74 -> 0 Solutions in 1858 Seconds
// 72...75 -> 3 bzw. 6 Lösungen in 1587 Sekunden
enum
{
num = 25,
#if 0 // auto, avg +- etwas zur Suche nach der vermeintlich optimalen Lösung
minsum = num&1 ? num*3/2 - 3 : num*3/2 - 3,
maxsum = num&1 ? num*3/2 + 1 : num*3/2 + 0,
#elif 1 // auto, 0...avg+wenig zum Nachweis, daß die vermeintlich optimale
Lösung wirklich optimal ist
minsum = 0,
maxsum = num&1 ? num*3/2 + 0 : num*3/2 + -1,
#else // manuell
minsum = 0,
maxsum = 3*num,
#endif
total_sum = 3 * num * (num-1) / 2,
verbose = 1
};
int kette[num];
bool is_used[num];
int current;
#if SUPPORT_REST_ABSCHAETZUNG()
int current_sum;
int min_restsum[num];
int max_restsum[num];
#endif
int number_of_found_solutions;
int best_solution_min_sum;
int best_solution_max_sum;
void search (void);
void display_lichterkette (void);
int triple_sum (int pos);
};
lichter::lichter(void)
{
if (current == num)
{
return;
}
}
void lichter::main(void)
{
int i;
time_t start_time;
time_t end_time;
printf ("lichter (num = %d, intervall %d to %d)\n", num, minsum, maxsum);
for (i=0; i<num; i++)
{
is_used[i] = false;
}
#if SUPPORT_REST_ABSCHAETZUNG()
bool odd;
current_sum = 0;
min_restsum[num-1] = minsum*2 + 1;
max_restsum[num-1] = maxsum*2 - 1;
odd = false;
for (i=num-2; i>=0; i--)
{
min_restsum[i] = minsum + min_restsum[i+1];
max_restsum[i] = maxsum + max_restsum[i+1];
if (odd)
{
min_restsum[i] ++;
max_restsum[i] --;
}
odd = !odd;
}
#endif
number_of_found_solutions = 0;
best_solution_min_sum = 0;
best_solution_max_sum = 3*num;
start_time = time(NULL);
i = 0; // oder i = num-1 oder irgendwas anderes
kette[0] = i;
is_used[i] = true;
for (i=0; i<num; i++)
{
if (is_used[i]) continue;
kette[1] = i;
is_used[i] = true;
current = 2;
end_time = time(NULL);
if (verbose > 1)
{
printf ("time = %ld, sol = %d, lichter search %d %d ...\n",
(long)(end_time-start_time), number_of_found_solutions,
kette[0], kette[1]);
}
search ();
is_used[i] = false;
}
end_time = time(NULL);
printf ("total found %d solutions in %ld seconds\n",
number_of_found_solutions, (long)(end_time-start_time));
printf ("found intervall: %d ... %d\n", best_solution_min_sum,
best_solution_max_sum);
printf ("lichter ende\n");
}
void lichter::search (void)
{
if (current >= num)
{
int sum;
sum = triple_sum(0);
if (sum < minsum) return;
if (sum > maxsum) return;
sum = triple_sum(num-1);
if (sum < minsum) return;
if (sum > maxsum) return;
number_of_found_solutions ++;
display_lichterkette ();
return;
}
for (int val=0; val<num; val++)
{
if (is_used[val]) continue;
int sum = kette[current-2] + kette[current-1] + val;
if (sum < minsum) continue;
if (sum > maxsum) continue;
#if SUPPORT_REST_ABSCHAETZUNG()
if (current_sum + sum + min_restsum[current] > total_sum) continue;
if (current_sum + sum + max_restsum[current] < total_sum) continue;
current_sum += sum;
#endif
kette[current] = val;
is_used[val] = true;
current ++;
search ();
current --;
is_used[val] = false;
#if SUPPORT_REST_ABSCHAETZUNG()
current_sum -= sum;
#endif
}
}
void lichter::display_lichterkette (void)
{
int i;
int sum;
int min_sum, max_sum;
min_sum = triple_sum(0);
max_sum = triple_sum(0);
if (verbose > 3) printf ("solution found:\n");
for (i=0; i<num; i++)
{
sum = triple_sum(i);
if (verbose > 3)
{
printf ("%d %d\n", kette[i], sum);
}
else
{
printf (" %d", kette[i]);
}
if (sum < min_sum) min_sum = sum;
if (sum > max_sum) max_sum = sum;
}
if (verbose > 0)
{
printf (" (%d...%d)", min_sum, max_sum);
}
printf ("\n");
if (min_sum > best_solution_min_sum) best_solution_min_sum = min_sum;
if (max_sum < best_solution_max_sum) best_solution_max_sum = max_sum;
}
int lichter::triple_sum (int pos)
{
int sum;
sum = kette[pos];
if (pos-1 >= 0) sum += kette[pos-1];
else sum += kette[pos+num-1];
if (pos+1 < num) sum += kette[pos+1];
else sum += kette[pos-num+1];
return sum;
}
int main(int argc, char* argv[])
{
lichter data;
data.main();
return 0;
}
Kurt Stege
>On Fri, 28 Dec 2001 04:19:13 +0100, Kurt Stege <kurt-...@online.de>
>wrote 250 lines:
>>f(n) = n*3/2 für gerade n
>G(2*k) = 3*k+3, für 4 <= k <= 12
Ich sehe gerade: f(6) = 8, nicht 9 bzw. G(6) = 11 statt 12:
0 3 4 1 2 5
War aber, glaube ich, hier auch schon irgendwo erwähnt,
daß das Argument für die Unmöglichkeit erst ab n>6 gelten
würde.
Gruß,
Kurt.
Kurt Stege
>"Daniel Grund" <Daniel...@gmx.de> wrote:
>
>>Problem: Suche f(n) mit:
>>
>>f(n):= min ( max S(p,i) )
>> p i
>>
>>S(p,i):= p(i mod n) + p((i+1) mod n) + p((i+2) mod n)
>>
>>p Permutation der Länge n (zero-based, wegen modulo)
>>i E {0..n-1)
>Zunächst einmal noch zwei Funktionen. Sei p eine Permutation,
>dann sei
>
>min_S(p) := min S(p,i)
>
>und
>
>max_S(p) := max S(p,i)
>
>min_S(n) := min S(p) über alle Permutationen p
>max_S(n) := max S(p)
>avg_S(n) = (n-1)*(3/2).
>min_S(n) < avg_S(n) < max_S(n)
>
>
>Nun kommt eine große Fallunterscheidung:
Fall n = 6*k + 2. (für k>= 1)
Vermutung: Es gibt eine Permutation p, so daß max_S(p) = n * 3/2 = 9k+3
Schon gestern hatte ich:
>Die nachfolgende Strategie, hier für n=26 dargestellt, funktioniert
>für jedes gerade n, das nicht durch 3 teilbar ist:
>
> 00 .. .. 01 .. .. 03 .. .. 04 .. .. 06 .. .. 07 .. .. 09 .. .. 10 .. .. 12 ..
> .. 13 .. .. 15 .. .. 16 .. .. 18 .. .. 19 .. .. 21 .. .. 22 .. .. 24 .. .. 25
> .. .. 23 .. .. 20 .. .. 17 .. .. 14 .. .. 11 .. .. 08 .. .. 05 .. .. 02 .. ..
>
>Man fängt bei 0 an, verteilt an jeden dritten Platz eine Zahl. Alle
>zwei Zahlen läßt man eine Zahl ausfallen. Wenn man das zweite Mal rum ist,
>hat man n-1 verteilt. Dann beginnt man in umgekehrter Reihenfolge in die
>übriggebliebenen Plätze von oben nach unten die letzen Zahlen reinzupacken.
>
>Übersichtlich in drei Zeilen zu schreiben, die am Schluß zusammengeschoben
>werden zu:
> 00 13 23 01 15 20 03 16 17 ...
k = 1, n = 8:
00 .. .. 01 .. .. 03 ..
.. 04 .. .. 06 .. .. 07
.. .. 05 .. .. 02 .. ..
00 04 05 01 06 02 03 07
k = 2, n = 14
00 .. .. 01 .. .. 03 .. .. 04 .. .. 06 ..
.. 07 .. .. 09 .. .. 10 .. .. 12 .. .. 13
.. .. 11 .. .. 08 .. .. 05 .. .. 02 .. ..
00 07 11 01 09 08 03 10 05 04 12 02 06 13
Allgemein ergibt sich so folgende Permutation:
00 .. .. 01 .. .. 03 .. .. ...... 3k-2 .. .. 3k+0 ..
.. 3k+1 .. .. 3k+3 .. .. 3k+4 .. ...... .. 6k+0 .. .. 6k+1
.. .. 6k-1 .. .. 6k-4 .. .. 6k-7 .... .. .. 02 .. ..
(Die letzte Zeile ist 3m+2 für m = 2k-1 ... 0.)
Der Schritt von k nach k+1 fügt irgendwo in der Mitte sechs neue
Zahlen ein und bewirkt, daß jede Dreiersumme um genau drei ansteigt.
Ich mache es mir mal einfach, und sage: Offensichtlich und nach
Konstruktion ergibt sich so für jedes natürliche k>=1 eine Permutation
(also jede Zahl von 0 bis 6k+1 kommt genau einmal vor) mit Dreiersumen,
die alle zwischen 9k und 9k+3 liegen.
Und 9k+3 = n*(3/2).
Fall n = 6*k + 4. (für k>= 1)
Ich verwende dieselbe Bauvorschrift:
>Man fängt bei 0 an, verteilt an jeden dritten Platz eine Zahl. Alle
>zwei Zahlen läßt man eine Zahl ausfallen. Wenn man das zweite Mal rum ist,
>hat man n-1 verteilt. Dann beginnt man in umgekehrter Reihenfolge in die
>übriggebliebenen Plätze von oben nach unten die letzen Zahlen reinzupacken.
k = 1, n = 10
00 .. .. 01 .. .. 03 .. .. 04
.. .. 06 .. .. 07 .. .. 09 ..
.. 08 .. .. 05 .. .. 02 .. ..
k = 2, n = 16
00 .. .. 01 .. .. 03 .. .. 04 .. .. 06 .. .. 07
.. .. 09 .. .. 10 .. .. 12 .. .. 13 .. .. 15 ..
.. 14 .. .. 11 .. .. 08 .. .. 05 .. .. 02 .. ..
Allgemein:
00 .. .. 01 .. .. ...... .. .. 3k+0 .. .. 3k+1
.. .. 3k+3 .. .. 3k+4 ...... .. 6k+1 .. .. 6k+3 ..
.. 6k+2 .. .. 6k-1 .. ...... 05 .. .. 02 .. ..
Hier kommen nur Dreiersummen von 9k+3 bis 9k+6 vor.
Und 9k+6 = n*(3/2).
Für den Fall, daß n durch drei teilbar ist, funktioniert die
ansonsten bewährte Bauvorschrift nicht mehr. Noch schlimmer:
Es muß noch unterschieden werden, ob n durch 12 teilbar ist
oder nicht.
Fall n = 6*k + 0. (für k>= 1)
Einschub:
Hier eine Bauvorschrift für n = 9k+6: (gilt sogar ab k >= 0)
Darstellung wie gehabt in drei Zeilen, wobei ebenfalls wie gehabt
die erste Zeile die Positionen 0, 3, 6, ... der Permutation darstellt,
die wweite Zeile Positionen 1, 3, 7, ... und die dritte Zeile den Rest.
Die erste Zeile erhält die Zahlen 0...3k+1, nach folgendem Muster:
2k+2 Zahlen: 0 1 3 4 6 7 ... 3k+0 3k+1
k Zahlen: 3k-1 3k-4 ... 8 5 2
Die zweite Zeile besteht aus den höchsten Zahlen 6k+4 ... 9k+5:
k+1 Zahlen: 9k+4 9k+1 9k-2 ... 6k+7 6k+4
2k+1 Zahlen: 6k+5 6k+6 6k+8 6k+9 ... 9k+2 9k+3 9k+5
Die dritte Zeile ist etwas komplexer als die ersten beiden. Sie
hat die mittleren Zahlen von 3k+2 bis 6k+3, die sich in drei
Gruppen zusammensetzen:
k Zahlen: ... 6k-2 6k-1 6k+1 6k+2
k+1 Zahlen: 6k+3 6k 6k-3 ... 3k+6 3k+3
k+1 Zahlen: 3k+2 3k+4 3k+5 3k+7 3k+8 ...
Die allerletzte Zahl schließt bündig im Muster an die erste
Zahl an.
k = 0, n = 6:
00 .. .. 01 .. ..
.. 04 .. .. 05 ..
.. .. 03 .. .. 02
k = 1, n = 15:
00 .. .. 01 .. .. 03 .. .. 04 .. .. 02 .. ..
.. 13 .. .. 10 .. .. 11 .. .. 12 .. .. 14 ..
.. .. 08 .. .. 09 .. .. 06 .. .. 05 .. .. 07
k = 2, n = 24:
00 .. .. 01 .. .. 03 .. .. 04 .. .. 06 .. .. 07 .. .. 05 .. .. 02 .. ..
.. 22 .. .. 19 .. .. 16 .. .. 17 .. .. 18 .. .. 20 .. .. 21 .. .. 23 ..
.. .. 13 .. .. 14 .. .. 15 .. .. 12 .. .. 09 .. .. 08 .. .. 10 .. .. 11
Ähnliche Bauvorschriften werde ich für 9k+3 und 9k+0 nachliefern,
ebenfalls eine bessere Darstellung, aus der man ersehen kann,
daß diese Permutationen die gewünschten Eigenschaften haben.
Mit diesen drei Bauvorschriften, die zusammen n=3k+0 abdecken,
wäre der Fall n = 6*k + 0. (für k>= 1) auch erledigt.
Ebenfalls wäre damit 6k+3 abgehakt.
Bleibt dann noch offen: 6k+1 und 6k+5. Dafür werde ich sicherlich
auch ähnliche Bauvorschriften finden können.
Das reicht für heute nacht,
Kurt.
Philipp Zumstein
wrote:
>Zunächst vorweg noch ein paar Begriffsklärungen:
Tschuldigung, habe ich nicht so genau gelesen und hoffe einfach wir
sprechen immer vom Gleichen:-)
>Philipp Zumstein <hzum...@bluewin.ch> wrote:
>
>>On Fri, 28 Dec 2001 04:19:13 +0100, Kurt Stege <kurt-...@online.de>
>>wrote 250 lines:
>
>>>max_S(n) >= aplus(n) hatten wir schon. Wäre sogar
>>>max_S(n) == aplus(n), würde es eine Permutation p geben, für das
>>>S(p,i) = aplus, aminus, aplus, aminus immer abwechselnd wäre.
>>>
>>>Man kann sich wahrscheinlich schnell überlegen, daß es eine
>>>solche Permutation nicht gibt.
>>
>>Ja. Dies stimmt für n=/=3 (wenn ich das jetzt richtig übersetzt habe
>>in zero-based). Also ich meine so etwas, wie: 1,4,5,2,3,6. Die
>>Begründung, warum es nicht funktioniert läuft daraus auf, dass so eine
>>alternierende Dreiersummenkonstellation sich genau nach dem sechsten
>>Element wiederholt. Also muss dort der Kreis geschlossen sein, sonst
>>funktioniert's nicht.
>
>Mit n=/=3 meinst Du "n kein Vielfaches von 3"? Ist =/= ein
>durchgestrichenes teilt-Zeichen? Hast Du n und 3 vertauscht?
>
>Viel wichtigere Frage: Für n, die Vielfache von 6 sind, muß ich
>mir also noch was überlegen, um die Ungleichheit zu zeigen?
"n=/=3" gesprochen "n ungleich 3". Es soll eine durchgestrichenes
Gleichheitszeichen darstellen. Bzw. one-based heisst das n=/=6 (n
ungleich 6). Daher rührt auch mein Zahlenkreis: 1,4,5,2,3,6. Ein
Nichgleichheitszeichen genügt, du musst kein Grösserzeichen haben, wie
du an anderer Stelle geposted hast.
>>>Wenn man diese Muster sauber durchformuliert und etwas rumrechnet,
>>>kann man sicherlich nachweisen, daß damit
>>>
>>>avg_S(n) - 1.5 == min_S(n) < max_S(n) == avg_S(n) + 1.5
>>>
>>>erreicht wird.
>>
>>Naja, ich hab's nicht geschafft. Das Muster erscheint mir auch nicht
>>"soooo" einfach.
>
>Gut. Dann werde ich mir etwas Mühe geben, hier den Durchbruch zu
>schaffen.
Das muss ich mir wohl etwas genauer in deinem anderen Posting
anschauen.
>>Ich kann - glaub ich - beweisen, dass für n=6*k+1 (one-based) die
>>Gleichheit nicht erfüllt werden kann.
Ich schreib dir hier mal meine Argumentation (Beweis) hin:
=========================
Für n = 6*k+1 ist die Durchschnittdreiersumme d = 3/2*(6*k+2) = 9*k+3,
alle Zahlen zusammen ergeben s_ges = (6*k+1)*(6*k+2) / 2 =
(6*k+1)*(3*k+1) = 18*k^2+9*k+1.
Irgendwo steht die Eins. Die restlichen Zahlen summieren sich auf zu
s_rest = 18*k^2+9*k.
Diese 6*k Zahlen bilden 2*k Dreiersummen. Auf solch eine Dreiersumme
fallen im Durchschnitt s_rest / (2*k) = (18*k^2+9*k) / (2*k) =
9*k+4.5.
==> G(6*k+1) >= 9*k+5.
Setze k=4 ein, dann erhält man den Spezialfall G(25) >= 41.
==========================
Vielleicht kannst du dies mal durchdenken und (hoffentlich)
bestätigen, dass die Argumentation richtig ist.
>>Übrigens die untere
>>Schranke (habe deine Bezeichnung vergessen) ist nicht beliebig. Nach
>>meinen Überlegungen ist testest du mit k=25, obere Schranke=40, untere
>>Schranke=27 alle Möglichkeiten durch. Aber solch einen Zahlenkreis
>>gibt es m.M. nicht.
>
>k=25? Meinst Du n=25 oder n=2*k=50?
Ich meine n=25 (also 25 Kerzen). Die Durchschnittsdreiersumme beträgt
d=3/2*26=39. Wenn man die obere Schranke auf 40 setzt ist dies der
einzige Wert der kleinere Werte ausgleichen kann, d.h. den
Durchschnitt auf 39 züruckbringen kann. Also z.B. wähle ich eine
Dreiersumme von 27, dann bin ich 12 vom Durchschnitt 39 weg. Diese 12
muss ich noch oben ausgleichen durch 40er Summen. Nämlich müssen dies
12x40er Summe sein. Aber mehr 40er Summen können nicht vorkommen, denn
ansonsten müssen einmal zwei 40er Summen nebeneinander kommen, dies
ist aber nicht möglich, weil zwei aufeinanderfolgende Summen nicht
gleich sein können (für genügend grosse n's).
>Eine untere Schranke gebe ich selbst nicht mehr vor. Die findet
>mein Programm schon von selbst: Wenn es anfängt, z.B. 0,1,22
>zu probieren, stellt es folgende Überlegung an: Bislang tatsächlich
>vergeben ist eine Dreiersumme von (nur) 23. Es kommen noch 24
>weitere Dreiersummen hinzu, die laut Vorgabe nur höchstens 37
>sein dürfen, und prinzipiell bestenfalls immer 37 und 36 abwechseln
>können. Die verbleibenden 24 Dreiersummen können also abgeschätzt
>werden durch 12*27+12*36 = 876. Insgesamt kann die Summer aller
>25 Dreiersummen also nur höchstens 899 betragen. Sie muß aber genau
>900 sein, also kann eine Lösung mit obere Schranke von 37 gar nicht
>mit 0,1,22 anfangen.
>
>Dieser Schneidemechanismus ist entscheidend für die Suche nach
>den Lösungen, von denen wir hier alle vermuten, daß es sie
>sowieso nicht mehr gibt.
Schau dir mal meine Argumentation von oben an. Die geht in die gleiche
Richtung.
Gruss
Philipp
Kurt Stege
>On Sat, 29 Dec 2001 01:55:25 +0100, Kurt Stege <kurt-...@online.de>
>wrote:
>
>>Zunächst vorweg noch ein paar Begriffsklärungen:
>
>Tschuldigung, habe ich nicht so genau gelesen und hoffe einfach wir
>sprechen immer vom Gleichen:-)
So ganz tun wir es noch nicht. Solltest Du nachholen, es wenigstens
zu überfliegen.
>>Philipp Zumstein <hzum...@bluewin.ch> wrote:
>>>Ja. Dies stimmt für n=/=3 (wenn ich das jetzt richtig übersetzt habe
>>>in zero-based). Also ich meine so etwas, wie: 1,4,5,2,3,6.
>"n=/=3" gesprochen "n ungleich 3". Es soll eine durchgestrichenes
>Gleichheitszeichen darstellen. Bzw. one-based heisst das n=/=6 (n
>ungleich 6).
Gut. Als C-Programmierer schreibe ich dafür immer n!=6, und hätte
auch n <> 6 verstanden (kleiner oder größer). =/= verstehe ich
ab sofort auch.
Also Du meinst: Das stimmt für n != 6. Die Übersetzung nach
zero-based war falsch.
one-based: n = 6, Permutation p = 1,4,5,2,3,6
zero-based: n = 6, Permutation p = 0,3,4,1,2,5
>>>Ich kann - glaub ich - beweisen, dass für n=6*k+1 (one-based) die
>>>Gleichheit nicht erfüllt werden kann.
>
>Ich schreib dir hier mal meine Argumentation (Beweis) hin:
>
>=========================
>Für n = 6*k+1 ist die Durchschnittdreiersumme d = 3/2*(6*k+2) = 9*k+3,
>alle Zahlen zusammen ergeben s_ges = (6*k+1)*(6*k+2) / 2 =
>(6*k+1)*(3*k+1) = 18*k^2+9*k+1.
Stimmt.
>Irgendwo steht die Eins. Die restlichen Zahlen summieren sich auf zu
>s_rest = 18*k^2+9*k.
Stimmt.
>Diese 6*k Zahlen bilden 2*k Dreiersummen. Auf solch eine Dreiersumme
>fallen im Durchschnitt s_rest / (2*k) = (18*k^2+9*k) / (2*k) =
>9*k+4.5.
Aus allen 6k+1 vorhandenen Dreiersummen suchst Du Dir 2k Dreiersummen
willkürlich aus, die dann den Durchschnitt s_rest bilden.
>==> G(6*k+1) >= 9*k+5.
Verblüffend, aber einleuchtend. Man muß ja gar nicht alle Dreiersummen
betrachten; es reicht ja eine einzige. Und wenn diese in den ausgewählten
2k Dreiersummen drin ist, ist alles klar.
Stimmt also.
>Vielleicht kannst du dies mal durchdenken und (hoffentlich)
>bestätigen, dass die Argumentation richtig ist.
Ja. Ist von mir als Beweis akzeptiert.
Diese Beweisidee klaue ich gleich, und führe sie für n=6k+3 und n=6k+5 durch.
Sei n = 6k + 3 (k >= 1).
Dann ist d = 9k+6 und s_ges = 18k^2 + 21k + 6.
Auch hier werden wieder 2k Dreiergruppen ausgesucht, die nicht-überlappend
sind.
(Einschub zur Herleitung des Beweises, wird für den Beweis selbst
nicht benötigt:
Damit G(n) > 9k + 6 folgt, muß s_rest größer als (9k+6)*(2k) = 18k^2+12k sein.
s_ges - s_rest muß also kleiner als 9k+6 sein. Die drei Kugeln, die in den
2k Dreiersummen nicht vorkommen, müssen also zusammen höchstens 9k+5 sein.
Einschub Ende)
Ich wähle die 2k Dreiergruppen wie folgt:
- Der kleinste Wert, die 1, soll nicht drin sein.
- Von allen Positionen, die nicht dieselbe Position
modulo 3 haben, wie die 1, suche ich den kleinsten Wert
und lasse diese Postion weg. Es sind nur 1/3 n Positionen
ausgeschlossen, die im schlimmsten Fall die Werte von
1 bis 1/3 n besetzen. Diese Position hat also höchstens
den Wert 1/3 n + 1.
- Irgendeine beliebige dritte Position kommt in den 2k ausgewählten
Dreiersummen auch nicht vor. Diese hat höchstens den Wert n.
Die Summe dieser drei Werte ist also kleiner oder gleich
(1) + (1/3 n + 1) + (n) = 1 + (2k + 2) + (6k + 3) = 8k + 6.
Damit ist s_rest >= s_ges - 8k + 6 = 18k^2 + 13k.
Die durchschnittliche Dreiersumme in diesen 2k Dreiersummen
beträgt also mindestens (18k^2 + 13k) / 2k = 9k + 6.5
Also ist G(2k+3) >= 9k + 7.
Sei n = 6k + 5 (k >= 1).
Dann ist d = 9k+9 und s_ges = 18k^2 + 31k + 15.
(Einschub:
Diesmal bleiben 2k+1 Dreiersummen übrig. Damit G(n) > 9k + 9 folgt,
muß s_rest größer als (9k+9)*(2k+1) = 18k^2+27k+9 sein.
s_ges - s_rest muß also kleiner als 4k+6 sein. Die zwei Kugeln, die in den
2k+1 Dreiersummen nicht vorkommen, müssen also zusammen höchstens 4k+5 sein.
Einschub Ende)
Aus den 6k+5 Zahlen werden zwei ausgesucht:
- Die kleinste Zahl, die 1.
- Die kleinste der folgenden Zahlen: Der rechte Nachbar von der 1 oder
davon ausgehend in Dreierschritten weiter, bis zur letzten Möglichkeit,
dem linken Nachbar der 1. Insgesamt stehen also etwa 1/3 n, genau 2k+2
Plätze zur Auswahl. Die kleinste Zahl auf diesen Positionen hat höchstens
den Wert n - (2k+2) + 1 = 4k + 4.
Die Summe dieser beiden Zahlen ist höchstens 4k + 5; der Rest geht wie gehabt.
Also ist G(2k+5) >= 9k + 10.
>>>Übrigens die untere
>>>Schranke (habe deine Bezeichnung vergessen) ist nicht beliebig. Nach
>>>meinen Überlegungen ist testest du mit n=25, obere Schranke=40, untere
>>>Schranke=27 alle Möglichkeiten durch. Aber solch einen Zahlenkreis
>>>gibt es m.M. nicht.
>Die Durchschnittsdreiersumme beträgt
>d=3/2*26=39. Wenn man die obere Schranke auf 40 setzt ist dies der
>einzige Wert der kleinere Werte ausgleichen kann, d.h. den
>Durchschnitt auf 39 züruckbringen kann. Also z.B. wähle ich eine
>Dreiersumme von 27, dann bin ich 12 vom Durchschnitt 39 weg. Diese 12
>muss ich noch oben ausgleichen durch 40er Summen. Nämlich müssen dies
>12x40er Summe sein. Aber mehr 40er Summen können nicht vorkommen, denn
>ansonsten müssen einmal zwei 40er Summen nebeneinander kommen, dies
>ist aber nicht möglich, weil zwei aufeinanderfolgende Summen nicht
>gleich sein können (für genügend grosse n's).
Ja, das verstehe ich. Genau diese Argumentation verwende ich in
meinem Suchprogramm, um den Suchbaum abzuschneiden, wenn in der
angefangenen Lichterkette die Summe der "zu kleinen Werte" so
groß geworden ist, daß sie nicht mehr durch die noch denkbaren
39er- und 40er-Dreiersummen ausgeglichen werden können.
>>Eine untere Schranke gebe ich selbst nicht mehr vor. Die findet
>>mein Programm schon von selbst: Wenn es anfängt, z.B. 0,1,22
>>zu probieren, stellt es folgende Überlegung an: Bislang tatsächlich
>>vergeben ist eine Dreiersumme von (nur) 23. Es kommen noch 24
>>weitere Dreiersummen hinzu, die laut Vorgabe nur höchstens 37
>>sein dürfen, und prinzipiell bestenfalls immer 37 und 36 abwechseln
>>können. Die verbleibenden 24 Dreiersummen können also abgeschätzt
>>werden durch 12*27+12*36 = 876. Insgesamt kann die Summer aller
>>25 Dreiersummen also nur höchstens 899 betragen. Sie muß aber genau
>>900 sein, also kann eine Lösung mit obere Schranke von 37 gar nicht
>>mit 0,1,22 anfangen.
>>
>>Dieser Schneidemechanismus ist entscheidend für die Suche nach
>>den Lösungen, von denen wir hier alle vermuten, daß es sie
>>sowieso nicht mehr gibt.
>
>Schau dir mal meine Argumentation von oben an. Die geht in die gleiche
>Richtung.
Ja. Wir meinen beide genau dasselbe.
Viele Grüsse,
Kurt.
Philipp Zumstein
wrote:
Musste mich zuerst etwas an deine Notation gewöhnen mit den vielen
Punkten. Ich habe dies zuerst überhaupt nicht verstanden. Aber nun ist
es mir klar.
>>Nun kommt eine große Fallunterscheidung:
>
>Fall n = 6*k + 2. (für k>= 1)
>
>Vermutung: Es gibt eine Permutation p, so daß max_S(p) = n * 3/2 = 9k+3
Dies ist eine obere Abschätzung. Nach unten abschätzen kann man dies
durch 9k+1.5. Wenn man dann diese alternierende Summen ausschliesst
bekommt man eine Abschätzung durch 9k+3.
D.h. also f(6*k+2) = 9*k+3 bzw. G(6*k+2) = 9*k+6.
>Schon gestern hatte ich:
>>Die nachfolgende Strategie, hier für n=26 dargestellt, funktioniert
>>für jedes gerade n, das nicht durch 3 teilbar ist:
> snip
>
>Allgemein ergibt sich so folgende Permutation:
>
>00 .. .. 01 .. .. | 03 .. ........ 3k-2 .. .. | 3k+0 ..
>.. 3k+1 .. .. 3k+3 .. | .. 3k+4 ... .. 6k+0 .. | .. 6k+1
>.. .. 6k-1 .. .. 6k-4 | .. .. 6k-7 ......... .. .. | 02 .. ..
>
>(Die letzte Zeile ist 3m+2 für m = 2k-1 ... 0.)
>
>Der Schritt von k nach k+1 fügt irgendwo in der Mitte sechs neue
>Zahlen ein und bewirkt, daß jede Dreiersumme um genau drei ansteigt.
>
>Ich mache es mir mal einfach, und sage: Offensichtlich und nach
>Konstruktion ergibt sich so für jedes natürliche k>=1 eine Permutation
>(also jede Zahl von 0 bis 6k+1 kommt genau einmal vor) mit Dreiersumen,
>die alle zwischen 9k und 9k+3 liegen.
>
>Und 9k+3 = n*(3/2).
Ich würde nicht sagen "offensichtlich". Entweder verbergt sich hinter
dem "offensichtlich" eine Begründung, die einem aber so klar
erscheint, dass man sie gar nicht sagen will; oder hinter dem
"offensichtlich" steckt nicht viel mehr als "eventuell",
"wahrscheinlich".
Meine Begründung (beachte auch meine Trennstriche in deiner Notation
oben):
Bezeichnen a1, a2, a3, ..., a6 die ersten Glieder deines
Zahlenkreises. Die nächsten erhält man folgendermassen: a1 + 3, a2 +
3, a3 - 6, a4 + 1, a5 + 1, a6 - 6. Der Zahlenkreis ist so etwas wie
periodisch. Also kann man die Dreiersummen zurückführen auf
Dreiersummen von den ersten 6 Zahlen. Darum muss man nur diese und die
Dreiersummen, die sich am Ende ergeben betrachten: am Anfang: 9k,
9k+1, 9k+3, 9k, 9k+2, 9k+3 und am Ende: 9k, 9k+2.
Alle Zahlen kommen genau einmal vor, weil du mit den Sequenzen 3*l,
3*l+1, 3*l+2 vollständig den Bereich abdeckst. Diese Sequenzen sind
disjunkt.
>Fall n = 6*k + 4. (für k>= 1)
>
>Ich verwende dieselbe Bauvorschrift:
>
>Allgemein:
>
>00 .. .. 01 .. .. ...... .. .. 3k+0 .. .. 3k+1
>.. .. 3k+3 .. .. 3k+4 ...... .. 6k+1 .. .. 6k+3 ..
>.. 6k+2 .. .. 6k-1 .. ...... 05 .. .. 02 .. ..
>
>Hier kommen nur Dreiersummen von 9k+3 bis 9k+6 vor.
Mit der gleichen Begründung wie beim Fall n=6*k+2.
>Für den Fall, daß n durch drei teilbar ist, funktioniert die
>ansonsten bewährte Bauvorschrift nicht mehr. Noch schlimmer:
>Es muß noch unterschieden werden, ob n durch 12 teilbar ist
>oder nicht.
Meinst du wirklich 12 oder eher 2?
>Fall n = 6*k + 0. (für k>= 1)
> snip
Dies ist mir wohl doch ein Bisschen zu heuristisch bzw. es ist mir
einfach etwas zu kompliziert.
>Mit diesen drei Bauvorschriften, die zusammen n=3k+0 abdecken,
>wäre der Fall n = 6*k + 0. (für k>= 1) auch erledigt.
Ja, falls du begründen kannst das deine "Bauvorschrift" funktioniert
in der gewünschen Weise.
>Ebenfalls wäre damit 6k+3 abgehakt.
>
>Bleibt dann noch offen: 6k+1 und 6k+5. Dafür werde ich sicherlich
>auch ähnliche Bauvorschriften finden können.
n=6*k+1:
Das gleiche wie oben aber vertausche die Rolle der dritten und zweiten
Zeile:
z.B.:
00 .. .. 01 .. .. 03 .. .. 04 .. .. 06
.. .. 07 .. .. 09 .. .. 10 .. .. 12
.. 11 .. .. 08 .. .. 05 .. .. 02 ..
=> 0, 11, 7, 1, 8, 9, 3, 5, 10, 4, 2, 12, 6
n=6*k+5 habe ich noch nicht raus.
Gruss
Philipp
Rainer Rosenthal
Kurt Stege <kurt-...@online.de> wrote > >
> >Schau dir mal meine Argumentation von oben an. Die geht in die gleiche
> >Richtung.
>
> Ja. Wir meinen beide genau dasselbe.
>
Hallo Kurt und Philipp,
es ist ein Vergnügen, Euren Erkundungen zu folgen !
Nach Schnecken-Manier habe ich den Fall n = 6k+2
mal gemütlich (wie schön, Urlaub zu haben !) nachvoll-
zogen und bin sehr, sehr erfreut über das sich ein-
stellende Muster. ( Ich habe n=14 auch hingefummelt, und
es ist keinesfalls trivial. Um so interessanter, dass sich das
so konsequent herleiten lässt. Und die Theorie-Lösung ist
auch viel glatter als meine, die Sprünge +7 und -7 enthält.)
Das Programm von Kurt habe ich 1:1 übernommen und es
läuft auch - bringt aber leider Null Lösungen :-(
Und im Code finde ich auch nichts von den schönen theoretischen
Überlegungen. Macht nix, dann programmiere ich halt selber
mal ein wenig ...
Eine kleine Bitte: Die letzte aktuelle G(n)-Tabelle ist noch immer
die von Helmut Richter (s.u.), die aber bei n=22 endet.
Könntet Ihr mal so nett sein, eine kleine Zwischen-Zusamenfassung
für die interessierte Leserschaft zu posten, die sich an der
kompakten Schreibweise von Helmut Richter orientiert. Sagen wir
mal bis n=50 wenigstens.
Und dazu noch eine kurze Zusammenfassung der Zauberformeln wie
z.B. G(6k+2) = 9k+6
(Nix gegen zero-based als Arbeits-Notation, aber es dürfte hilfreich
sein, wenn es nach aussen hin bei einheitlicher Notation bleibt. Danke.)
Wenn alles unter Dach und Fach ist und ein paar Tage unwidersprochen
bleibt, will ich gerne die aktuellen Ergebnisse mit Euren Namen im
NJAS-Archiv nachtragen. Und zur Sicherheit werde ich dann diesen
Nachtrag erst mal von Euch begutachten lassen :-)
Es ist doch eine feine Sache, wenn sich das verbrauchte Hirnschmalz
in fester Form im NJAS-Archiv wiederfindet für "die Nachwelt".
Inzwischen habe ich auch schon mal das wunderbare Buch von R.K.Guy
"Unsolved Problems in Number Theory" durchgeforstet, ob unser Thema
darin zu finden ist - habe aber nix gefunden.
Aus der Website von Helmut Richter
http://www.lrz-muenchen.de/~hr/tmp/zahlenkreis
habe ich die aktuellen Werte abgekupfert:
n G(n) Beispiel
-----------------------------------------
6 11 1 4 5 2 3 6
7 14 1 2 5 6 3 4 7
8 15 1 5 6 2 7 3 4 8
9 16 1 5 8 2 6 7 3 4 9
10 18 1 4 9 5 3 7 8 2 6 10
11 20 1 5 4 10 6 3 8 9 2 7 11
12 21 1 5 10 3 8 9 4 6 11 2 7 12
13 23 1 3 9 10 4 7 11 5 6 12 2 8 13
14 24 1 8 11 4 9 10 2 12 5 6 13 3 7 14
15 25 1 9 12 3 10 11 4 7 13 5 6 14 2 8 15
16 27 1 7 15 5 6 13 8 4 11 12 3 10 14 2 9 16
17 29 1 7 13 5 11 12 3 14 6 8 15 4 9 16 2 10 17
18 30 1 7 16 6 8 15 3 12 13 5 11 14 4 9 17 2 10 18
19 32 1 4 18 8 6 16 9 7 15 10 5 13 14 3 12 17 2 11 19
20 33 1 11 18 2 13 14 4 15 12 5 16 7 9 17 6 8 19 3 10 20
21 35 1 5 20 6 9 18 7 10 15 8 11 16 4 14 17 3 13 19 2 12 21
22 36 1 10 21 5 8 19 9 7 18 11 6 14 16 4 15 17 3 13 20 2 12 22
Anmerkung:
Der Zahlenkreis zu n=14=6*2+2 gemäss (6k+2)-Theorie von Kurt ist:
14 24 1 8 12 2 10 9 4 11 6 5 13 3 7 14
Noch eine Frage an die Experten:
Aus der Tatsache "Die Summe der 3-er-Päckchen ist das 3-fache der
Summe der einzelnen Zahlen" folgte ja die Abschätzung G(n) >= C(n),
wobei C(n) = ceiling(3*(n+1)/2). Und die wirklich pfiffige Erkenntnis, dass
Gleichheit nur für n=6 sein kann, ergibt dann G(n) - C(n) >= 1 für n > 6.
Daraus folgt dann z.B. die Antwort auf Aufgabe 4 des Bundeswettbewerbs
Mathematik 2002, weil C(12)=ceiling(3*13/2)=ceiling(39/2)=20 und 12 > 6,
mit der Konsequenz G(12) > 20.
Hier die Frage: Habt Ihr evtl. eine allgemeingültige Antwort darauf, wann
G(n) - C(n) = 1 ist, wann 2 herauskommt und ob evtl. mal ein Wert > 2 zu
erwarten ist ?
Hier ist die entsprechende Tabelle für die ersten bekannten Werte:
n C(n) G(n) G(n)-C(n)
----------------------------------
6 11 11 0
7 12 14 2
8 14 15 1
9 15 16 1
10 17 18 1
11 18 20 2
12 20 21 1
13 21 23 2
14 23 24 1
15 24 25 1
16 26 27 1
17 27 29 2
18 29 30 1
19 30 32 2
20 32 33 1
21 33 35 2
22 35 36 1
Ach ja, noch ein letztes zur Theorie-Diskussion. Ich denke, dass
es gar nicht schlecht wäre, unsere zyklischen Permutationen
gleich auf den ganzen Zahlen Z zu definieren. Also p: Z -> {1..n}
mit der Eigenschaft p(x) = p(y) für x=y mod n. Dann ist es wurscht,
"wo man anfängt". Knipst man das Lichtlein auf Position 5 an,
dann gehen alle Lichtlein auf den Positionen 5+n, 5-n, 5+2n, 5-2n
usw. mit an.
Herzliche Grüsse und - vorsorglich - ein Gutes Neues Jahr
Rainer Rosenthal
r.ros...@web.de
Kurt Stege
>>Nun kommt eine große Fallunterscheidung:
>
>Fall n = 6*k + 2. (für k>= 1)
>Fall n = 6*k + 4. (für k>= 1)
Diese beiden Bauvorschriften habe ich gesnippt, da sie unten
durch allgemeinere Bauanleitungen für 3k+2 und 3k+1 ersetzt
sind.
Der Fall 3k+0 ist aufgespaltet in die Unterfälle
9k+0, 9k+3 und 9k+6:
>Hier eine Bauvorschrift für n = 9k+6: (gilt sogar ab k >= 0)
>
>Darstellung wie gehabt in drei Zeilen, wobei ebenfalls wie gehabt
>die erste Zeile die Positionen 0, 3, 6, ... der Permutation darstellt,
>die wweite Zeile Positionen 1, 3, 7, ... und die dritte Zeile den Rest.
>
>Die erste Zeile erhält die Zahlen 0...3k+1, nach folgendem Muster:
>2k+2 Zahlen: 0 1 3 4 6 7 ... 3k+0 3k+1
>k Zahlen: 3k-1 3k-4 ... 8 5 2
>
>Die zweite Zeile besteht aus den höchsten Zahlen 6k+4 ... 9k+5:
>k+1 Zahlen: 9k+4 9k+1 9k-2 ... 6k+7 6k+4
>2k+1 Zahlen: 6k+5 6k+6 6k+8 6k+9 ... 9k+2 9k+3 9k+5
>
>Die dritte Zeile ist etwas komplexer als die ersten beiden. Sie
>hat die mittleren Zahlen von 3k+2 bis 6k+3, die sich in drei
>Gruppen zusammensetzen:
>k Zahlen: ... 6k-2 6k-1 6k+1 6k+2
>k+1 Zahlen: 6k+3 6k 6k-3 ... 3k+6 3k+3
>k+1 Zahlen: 3k+2 3k+4 3k+5 3k+7 3k+8 ...
>Die allerletzte Zahl schließt bündig im Muster an die erste
>Zahl an.
>Ähnliche Bauvorschriften werde ich für 9k+3 und 9k+0 nachliefern,
>ebenfalls eine bessere Darstellung, aus der man ersehen kann,
>daß diese Permutationen die gewünschten Eigenschaften haben.
Hier eine Bauvorschrift für n = 9k+3: (gilt sogar ab k >= 0)
1. Zeile: Zahlen 0 ... 3k
2k+1 Werte: 0 1 3 4 6 7 ... 3k-3 3k-2 3k
k Werte: 3k-1 3k-4 ... 8 5 2
2. Zeile: Zahlen 6k+2 ... 9k+2
k Werte: 9k+1 9k-2 9k-5 ... 6k+7 6k+4
2k+1 Werte: 6k+2 6k+3 6k+5 6k+6 ... 9k-4 9k-3 9k-1 9k-0 9k+2
3. Zeile: Zahlen 3k+1 ... 6k+1
k Werte: ... 6k-5 6k-4 6k-2 6k-1 6k+1
k Werte: 6k 6k-3 6k-6 ... 3k+6 3k+3
k+1 Werte: 3k+1 3k+2 3k+4 3k+5 ...
Beispiele zur Übersicht:
k=0 (n=3):
0 2 1
k=1 (n=12):
0 1 3 2
10 8 9 11
7 6 4 5
(also die Permutation 0 10 7 1 8 6 3 9 4 2 11 5)
k=3 (n=30):
00 01 03 04 06 07 09 08 05 02
28 25 22 20 21 23 24 26 27 29
16 17 19 18 15 12 10 11 13 14
(Also die Reihe 00 28 16 01 25 17 ... 02 29 14)
k=4 (n=39):
00 01 03 04 06 07 09 10 12 11 08 05 02
37 34 31 28 26 27 29 30 32 33 35 36 38
20 22 23 25 24 21 18 15 13 14 16 17 19
Hier eine Bauvorschrift für n = 9k+0: (gilt ab k >= 1)
1. Zeile: Zahlen 0 ... 3k-1
2k Werte: 0 1 3 4 6 7 ... 3k-3 3k-2
k Werte: 3k-1 3k-4 ... 8 5 2
2. Zeile: Zahlen 6k ... 9k-1
k Werte: 9k-2 9k-5 ... 6k+4 6k+1
2k Werte: 6k 6k+2 6k+3 6k+5 6k+6 ... 9k-4 9k-3 9k-1
3. Zeile: Zahlen 3k ... 6k-1
k Werte: ... 6k-5 6k-4 6k-2 6k-1
k Werte: 6k-3 6k-6 ... 3k+3 3k
k Werte: 3k+1 3k+2 3k+4 3k+5 ...
Beispiele zur Übersicht:
k = 1, n = 9:
0 1 2
7 6 8
5 3 4
k = 2, n = 18:
00 01 03 04 05 02
16 13 12 14 15 17
10 11 09 06 07 08
k = 3, n = 27:
00 01 03 04 06 07 08 05 02
25 22 19 18 20 21 23 24 26
14 16 17 15 12 09 10 11 13
k = 4, n = 36:
00 01 03 04 06 07 09 10 11 08 05 02
34 31 28 25 24 26 27 29 30 32 33 35
19 20 22 23 21 18 15 12 13 14 16 17
>Mit diesen drei Bauvorschriften, die zusammen n=3k+0 abdecken,
>wäre der Fall n = 6*k + 0. (für k>= 1) auch erledigt.
>
>Ebenfalls wäre damit 6k+3 abgehakt.
>
>Bleibt dann noch offen: 6k+1 und 6k+5. Dafür werde ich sicherlich
>auch ähnliche Bauvorschriften finden können.
Hier eine Bauvorschrift für n = 3k+1: (gilt ab k >= 1):
1. Zeile mit k+1 Werten: 0 1 3 4 6 7 ...
2. Zeile mit k Werten: 3k-1 3k-4 3k-7 ... 8 5 2
3. Zeile mit k Werten: ... 3k-6 3k-5 3k-3 3k-2 3k
Das ergibt die Permutation: 0 3k-1 . 1 3k-4 . 3 3k-7 ... 5 3k-2 . 2 3k 7
Beispiel für k=5, n=16:
00 01 03 04 06 07
14 11 08 05 02
09 10 12 13 15
Hier eine Bauvorschrift für n = 3k+2: (gilt ab k >= 1):
1. Zeile mit k+1 Werten: 0 1 3 4 6 7 ...
2. Zeile mit k+1 Werten: ... 3k-5 3k-4 3k-2 3k-1 3k+1 3k+2
3. Zeile mit k Werten: 3k 3k-3 3k-6 ... 8 5 2
Beispiel für k=5, n=17:
00 01 03 04 06 07
09 10 12 13 15 16
14 11 08 05 02
Also: 0 9 14 1 10 11 3 12 8 4 13 5 6 15 2 7 16
Damit habe ich für alle n jeweils eine konkrete Permutationen p(n)
angegeben. Ich behaupte, ohne es hier konkret gezeigt zu haben,
daß diese Permutationen jeweils als größte Dreiersumme
genau den Wert ceil(3/2 n) hat. Für "mittelkleine" n habe ich
dies exemplarisch überprüft. Es allgemein nachzurechnen, ist
eine Fleißaufgabe, die ich zumindest heute nicht mehr machen
werde. Bei ganz kleinen n mag es noch Ausnahmefälle geben,
die aber hier mittlerweile gut bekannt sind.
Was auch bekannt und als nachgewiesen gilt, ist:
Für gerade n (außer n=6) ist die größte Dreiersumme
mindestens 3/2 n, also zusammen mit diesem Ergebnis hier
sogar genau 3/2 n. (Bei geraden n ist ceil(3/2 n) = 3/2 n.)
Was noch fehlt, aber bereits in diesem Thread in Arbeit ist,
ist die untere Abschätzung für die minimale größte Dreiersumme
für ungerade n. Wenn diese Arbeiten durch sind, und die Ergebnisse
dieses Threads nachgerechnet wurden, ist die gesuchte Funktion
f(n) gut bekannt, und nicht mehr sonderlich aufregend.
Gruß,
Kurt Stege.
Kurt Stege
>Ich habe den Beweis - glaub ich - einfacher und allgemeiner
>hingekriegt:
>
>Für n = 6*k+1 ist die Durchschnittdreiersumme d = 3/2*(6*k+2) = 9*k+3,
>alle Zahlen zusammen ergeben s_ges = (6*k+1)*(6*k+2) / 2 =
>(6*k+1)*(3*k+1) = 18*k^2+9*k+1.
>
>Irgendwo steht die Eins. Die restlichen Zahlen summieren sich auf zu
>s_rest = 18*k^2+9*k.
>
>Diese 6*k Zahlen bilden 2*k Dreiersummen. Auf solch eine Dreiersumme
>fallen im Durchschnitt s_rest / (2*k) = (18*k^2+9*k) / (2*k) =
>9*k+4.5.
>
>==> G(6*k+1) >= 9*k+5.
Yup. Stimmt.
Eine Kopie hiervon hattest Du mittlerweile auch als Reply auf eins
meiner Postings geschickt. Dieses Original war bei mir noch liegen
geblieben, und kann jetzt auch abgehakt werden.
Drei Postings von Dir, Philipp, habe ich noch auf Warteposition
liegen...
Gruß,
Kurt.
Kurt Stege
>f(n) ist zero-based, G(n) ist one-based. Es ist f(n)+3 = G(n).
>(Nach meinem Verständnis von f() und G().)
Außer natürlich für n=0. Dort ist, wenn man es überhaupt definieren
will, sicherlich f(0) = G(0) = 0, nämlich eine leere Summe.
Gruß,
Kurt.
Kurt Stege
Hier schon mal ein paar Bugfixes:
Kurt Stege <kurt-...@online.de> wrote:
>Sei n = 6k + 3 (k >= 1).
Die gesuchte Eigenschaft gilt nur für k >= 3. n=9 und n=15 sind
gut bekannte Ausnahmen.
>Dann ist d = 9k+6 und s_ges = 18k^2 + 21k + 6.
>Auch hier werden wieder 2k Dreiergruppen ausgesucht, die nicht-überlappend
>sind.
>
>(Einschub zur Herleitung des Beweises, wird für den Beweis selbst
>nicht benötigt:
>
>Damit G(n) > 9k + 6 folgt, muß s_rest größer als (9k+6)*(2k) = 18k^2+12k sein.
>s_ges - s_rest muß also kleiner als 9k+6 sein. Die drei Kugeln, die in den
>2k Dreiersummen nicht vorkommen, müssen also zusammen höchstens 9k+5 sein.
Es soll bewiesen werden, daß G(n) > 9k+7.
Damit G(n) > 9k + 7 folgt, muß s_rest größer als (9k+7)*(2k) = 18k^2+14k sein.
s_ges - s_rest muß also kleiner als 7k+6 sein.
>Einschub Ende)
>
>Ich wähle die 2k Dreiergruppen wie folgt:
>- Der kleinste Wert, die 1, soll nicht drin sein.
>- Von allen Positionen, die nicht dieselbe Position
> modulo 3 haben, wie die 1, suche ich den kleinsten Wert
> und lasse diese Postion weg. Es sind nur 1/3 n Positionen
> ausgeschlossen, die im schlimmsten Fall die Werte von
> 1 bis 1/3 n besetzen. Diese Position hat also höchstens
> den Wert 1/3 n + 1.
>- Irgendeine beliebige dritte Position kommt in den 2k ausgewählten
> Dreiersummen auch nicht vor. Diese hat höchstens den Wert n.
>
>Die Summe dieser drei Werte ist also kleiner oder gleich
>(1) + (1/3 n + 1) + (n) = 1 + (2k + 2) + (6k + 3) = 8k + 6.
8k+6 ist natürlich noch nicht kleiner als 7k+6. Da müssen
noch andere drei Zahlen ausgesucht werden. Dabei muß ausgenutzt
werden, daß k ziemlich groß ist.
>Damit ist s_rest >= s_ges - 8k + 6 = 18k^2 + 13k.
Hier fehlten Klammern: s_rest >= s_ges - (8k + 6) = 18k^2 + 13k.
>Die durchschnittliche Dreiersumme in diesen 2k Dreiersummen
>beträgt also mindestens (18k^2 + 13k) / 2k = 9k + 6.5
>
>Also ist G(2k+3) >= 9k + 7.
Tippfehler: ^
Also ist G(6k+3) >= 9k + 7
Aber zeigen wollte ich G(6k+3) >= 9k+8, und das ist mir noch
nicht gelungen.
Gruß,
Kurt.
Kurt Stege
>Eine kleine Bitte: Die letzte aktuelle G(n)-Tabelle ist noch immer
>die von Helmut Richter (s.u.), die aber bei n=22 endet.
>Könntet Ihr mal so nett sein, eine kleine Zwischen-Zusamenfassung
>für die interessierte Leserschaft zu posten, die sich an der
>kompakten Schreibweise von Helmut Richter orientiert. Sagen wir
>mal bis n=50 wenigstens.
>Und dazu noch eine kurze Zusammenfassung der Zauberformeln wie
>z.B. G(6k+2) = 9k+6
>(Nix gegen zero-based als Arbeits-Notation, aber es dürfte hilfreich
>sein, wenn es nach aussen hin bei einheitlicher Notation bleibt. Danke.)
Diese Bitte nutze ich mal, um die bisherigen theoretischen,
also mathematischen Erkenntnisse zusammenzufassen. Die Auflistung
des bekannten numerischen Datenmaterials lasse ich mal weg,
weil wir mit der Theorie fast bis ganz durch sind.
Für jedes n gibt es (mindestens) ein Polynom p(n), welches nur
Dreiersummen zwischen (one-based) floor(n*3/2) und ceil(n*3/2)+3
enthält. Beispiele für solche Polynome habe ich in Form von
"Bauvorschriften" in verschiedenen Postings angegeben. Es bleibt
jedoch der Nachweis fällig, daß die Dreiersummen tatsächlich alle
in diesem Intervall liegen. [1]
Also G(n) <= ceil(n*3/2) + 3.
Für jedes n gibt es eine Abschätzung, daß gilt
G(n) >= ceil(n*3/2) + 3. Diese Abschätzungen haben Philipp und
ich gemacht, wobei bei meinen Abschätzungen noch die Verifikation
aussteht. [2]
Wenn Nachweis und Verifikation erbracht ist, gilt also:
G(n) = ceil(n*3/2) + 3
mit Ausnahme von manchen kleinen n=1, 2, 3, 5, 6, 9 und 15.
Details und Quellen:
[1] Die Bauvorschriften sind von mir in
Message-ID: <fj8s2u40vaqm582hq...@4ax.com>
angegeben, und zwar für die folgenden Fälle:
9k+0 (k>=1)
9k+3 (k>=0)
9k+6 (k>=0)
3k+1 (k>=1)
3k+2 (k>=1)
Die hiervon nicht erfaßten Fälle n=1 und 2 triviale Sonderfälle.
[2] Diese Abschätzungen wurden schon frühzeitig für gerade n
durchgeführt. Dies hat Helmut Richter am 22.12.2001 für den
Spezialfall n=10 gemacht, und Philipp am 24.12.2001 in
Message-ID: <t1be2u0efkacb7c38...@4ax.com>
für alle geraden n != 6 erweitert.
Für ungerade n hat Philipp Zumstein die zündene Idee gehabt und in
Message-ID: <bu7p2ug35r28icn0g...@4ax.com>
am 28.12. für den Fall n=6k+1 bewiesen.
Ich habe die Idee aufgegriffen und auf die Fälle 6k+3 und 6k+5
angewandt. Siehe dazu
Message-ID: <88lr2u423fv81pm4p...@4ax.com>.
Von meinen Erweiterungen steht noch die Verifizierung aus.
Noch schlimmer: Der Beweis für 6k+3 ist mangelhaft; und kann
erst ab k>=3 gelten.
Gruß,
Kurt.
Kurt Stege
>Es wäre nett, wenn ihr mir bei folgendem Problem helfen könntet:
>Die natürlichen Zahlen 1 bis 10 werden in beliebiger Reihenfolge
>zu einem Kreis angeordnet (jeder Seite eines Zehnecks wird eine
>der 10 Zahlen zugeordnet).
>Wie groß ist die größte Summe von 3 benachbarten Zahlen dann
>mindestens bei einem solchen Kreis (bzw. Zehneck)?
Liest Du noch mit, Christian?
Hättest Du diese Frage auch gestellt, wenn Du geahnt hättest,
welche Lawine Du damit auslöst?
Ich hoffe doch schon. Zumindest vielen Dank dafür.
Gruß, und guten Rutsch ins neue Jahr,
Kurt.
Kurt Stege
>On Sat, 29 Dec 2001 06:09:57 +0100, Kurt Stege <kurt-...@online.de>
>wrote:
>
>Musste mich zuerst etwas an deine Notation gewöhnen mit den vielen
>Punkten. Ich habe dies zuerst überhaupt nicht verstanden. Aber nun ist
>es mir klar.
Glück gehabt. Ich hätte auch vielleicht deutlicher schreiben können,
wie ich das meinte. In meinen späteren Postings habe ich die
Auslassungs-Punkte nicht mehr hingeschrieben, um Platz zu sparen.
>>>Nun kommt eine große Fallunterscheidung:
>>
>>Fall n = 6*k + 2. (für k>= 1)
>>
>>Vermutung: Es gibt eine Permutation p, so daß max_S(p) = n * 3/2 = 9k+3
>
>Dies ist eine obere Abschätzung. Nach unten abschätzen kann man dies
>durch 9k+1.5. Wenn man dann diese alternierende Summen ausschliesst
>bekommt man eine Abschätzung durch 9k+3.
>
>D.h. also f(6*k+2) = 9*k+3 bzw. G(6*k+2) = 9*k+6.
Richtig. Damit ist f(n) bzw. G(n) für gerade n konkret berechnet,
vorausgesetzt, alle Vermutungen stimmen.
>>Schon gestern hatte ich:
>>>Die nachfolgende Strategie, hier für n=26 dargestellt, funktioniert
>>>für jedes gerade n, das nicht durch 3 teilbar ist:
>> snip
>>
>>Allgemein ergibt sich so folgende Permutation:
>>
>>00 .. .. 01 .. .. | 03 .. ........ 3k-2 .. .. | 3k+0 ..
>>.. 3k+1 .. .. 3k+3 .. | .. 3k+4 ... .. 6k+0 .. | .. 6k+1
>>.. .. 6k-1 .. .. 6k-4 | .. .. 6k-7 ......... .. .. | 02 .. ..
>>
>>(Die letzte Zeile ist 3m+2 für m = 2k-1 ... 0.)
>>
>>Der Schritt von k nach k+1 fügt irgendwo in der Mitte sechs neue
>>Zahlen ein und bewirkt, daß jede Dreiersumme um genau drei ansteigt.
>>
>>Ich mache es mir mal einfach, und sage: Offensichtlich und nach
>>Konstruktion ergibt sich so für jedes natürliche k>=1 eine Permutation
>>(also jede Zahl von 0 bis 6k+1 kommt genau einmal vor) mit Dreiersumen,
>>die alle zwischen 9k und 9k+3 liegen.
>>
>>Und 9k+3 = n*(3/2).
>
>Ich würde nicht sagen "offensichtlich". Entweder verbergt sich hinter
>dem "offensichtlich" eine Begründung, die einem aber so klar
>erscheint, dass man sie gar nicht sagen will; oder hinter dem
>"offensichtlich" steckt nicht viel mehr als "eventuell",
>"wahrscheinlich".
Da hast Du mich und meine Faulheit ertappt. Was ich nachgerechnet
hatte:
- Für einige kleine k ergibt sich eine Permutation mit der
gewünschten Eigenschaft.
- Wenn man drei benachbarte Zahlen aus der Permutation aufsummiert,
kommt unabhängig von k immer dieselbe Summe raus.
- In den "..." passiert nichts besonderes. Dieses hast Du im
folgenden als "Der Zahlenkreis ist so etwas wie periodisch"
ausgedrückt.
>Meine Begründung (beachte auch meine Trennstriche in deiner Notation
>oben):
>
>Bezeichnen a1, a2, a3, ..., a6 die ersten Glieder deines
>Zahlenkreises. Die nächsten erhält man folgendermassen: a1 + 3, a2 +
>3, a3 - 6, a4 + 1, a5 + 1, a6 - 6. Der Zahlenkreis ist so etwas wie
>periodisch. Also kann man die Dreiersummen zurückführen auf
>Dreiersummen von den ersten 6 Zahlen. Darum muss man nur diese und die
>Dreiersummen, die sich am Ende ergeben betrachten: am Anfang: 9k,
>9k+1, 9k+3, 9k, 9k+2, 9k+3 und am Ende: 9k, 9k+2.
>
>Alle Zahlen kommen genau einmal vor, weil du mit den Sequenzen 3*l,
>3*l+1, 3*l+2 vollständig den Bereich abdeckst. Diese Sequenzen sind
>disjunkt.
Ja. Genau diese Begründung fehlte mir noch, und habe sie ungerechtfertigt
als "offensichtlich" deklariert.
>>Für den Fall, daß n durch drei teilbar ist, funktioniert die
>>ansonsten bewährte Bauvorschrift nicht mehr. Noch schlimmer:
>>Es muß noch unterschieden werden, ob n durch 12 teilbar ist
>>oder nicht.
>
>Meinst du wirklich 12 oder eher 2?
Weiß ich zugegebenermaßen auch nicht mehr. Zumindest habe
ich mittlerweile für alle n Permutationen angegeben.
Diese Permutationen, muß ich zur Vermeidung von Mißverständnissen
noch deutlich sagen, konstruieren jeweils eine Lösung, die auch
mein numerisches Programm ausspuckt. Es gibt aber noch zahlreiche
weitere Lösungen, die ähnlich aufgebaut sind. Von den tatsächlich
vorhandenen Lösungen habe ich willkürlich eine ausgewählt und in
diese allgemeine Form gebracht. Die ausgewählte Lösung ist durch
nichts (mir bekanntes) "schöner" als wenigstens andere 5 verfügbare
Lösungen (mit der 0 an Position 0).
>>Mit diesen drei Bauvorschriften, die zusammen n=3k+0 abdecken,
>>wäre der Fall n = 6*k + 0. (für k>= 1) auch erledigt.
>
>Ja, falls du begründen kannst das deine "Bauvorschrift" funktioniert
>in der gewünschen Weise.
Da werde ich noch dran basteln, an genau dieser Begründung (für alle
meine Bauvorschriften).
Gruß,
Kurt.
Kurt Stege
>Hallo Kurt und Philipp,
>
>es ist ein Vergnügen, Euren Erkundungen zu folgen !
Vielen Dank für diese Aufmunterung. Ich hatte mir schon,
noch nicht ganz ernsthaft, überlegt, ob wir das ganze
per Email fortführen sollten. Aber wenn tatsächlich noch
jemand mitliest, lohnt es sich, öffentlich weiterzumachen.
>Das Programm von Kurt habe ich 1:1 übernommen und es
>läuft auch - bringt aber leider Null Lösungen :-(
Seltsam. Was habe ich denn da gepostet?
: #if 0 // auto, avg +- etwas zur Suche nach der vermeintlich optimalen Lösung
: minsum = num&1 ? num*3/2 - 3 : num*3/2 - 3,
: maxsum = num&1 ? num*3/2 + 1 : num*3/2 + 0,
: #elif 1 // auto, 0...avg+wenig zum Nachweis, daß die vermeintlich optimale
: Lösung wirklich optimal ist
: minsum = 0,
: maxsum = num&1 ? num*3/2 + 0 : num*3/2 + -1,
: #else // manuell
: minsum = 0,
: maxsum = 3*num,
: #endif
Wenn Du aus dem #if 0 ein #if 1 machst, werden die unteren und oberen
Schranken so eingestellt, daß es auch Lösungen gibt. Und den dritten
Fall "manuell" hatte ich vorgesehen, um selber beliebige Zahlen
reinzuschreiben.
>Und im Code finde ich auch nichts von den schönen theoretischen
>Überlegungen.
Brute-Force-Suche eben. Was da noch drinsteckt sind zwei Sachen
aus unserer Theorie:
a) Die Vermutung, daß f(num) = ceil(num*3/2) ist, steckt hier:
: minsum = num&1 ? num*3/2 - 3 : num*3/2 - 3,
: maxsum = num&1 ? num*3/2 + 1 : num*3/2 + 0,
Dazu kommt noch die symmetrische Vermutung, das das Gegenstück von
f(), nämlich die kleinste vorkommende Dreiersumme bei floor(num*3/2)-3
liegt. Und (das ist neu) das es _eine_ Permutation gibt, die beide
Eigenschaften gleichzeitig erfüllt.
b) Die Abschätzung, wenn zuweit vom zu erreichenden Mittelwert
abgewichen wird und deshalb der Anfang der Permutation nicht mehr
zu einer Lösung führen kann, steckt hier:
: #if SUPPORT_REST_ABSCHAETZUNG()
: if (current_sum + sum + min_restsum[current] > total_sum) continue;
: if (current_sum + sum + max_restsum[current] < total_sum) continue;
: #endif
Und das entsprechende Know-How steckt bei der Initialisierung der
Arrays min_restsum und max_restsum.
>Macht nix, dann programmiere ich halt selber
>mal ein wenig ...
Es macht auch viel mehr Spaß, Ideen auszutauschen, nicht Programmcode.
>Wenn alles unter Dach und Fach ist und ein paar Tage unwidersprochen
>bleibt, will ich gerne die aktuellen Ergebnisse mit Euren Namen im
>NJAS-Archiv nachtragen. Und zur Sicherheit werde ich dann diesen
>Nachtrag erst mal von Euch begutachten lassen :-)
Von mir aus gerne.
In meinen "Bauvorschriften" für die Permutationen erschaffe ich eine
willkürlich ausgewählte Lösung. Es gibt mehrere Lösungen, von denen
sowohl Helmut als auch ich jeweils eine willkürlich rausgewählt haben.
Das wir verschiedene erwischen, ist dabei normal.
Aber damit sind wir bei einer anderen Frage, die auch noch
geklärt werden könnte, nämlich wieviele Permutationen gibt es,
die nur Dreiersummen zwischen
(one-based) floor(n*3/2) und ceil(n*3/2)+3
(zero-based) floor(n*3/2)-3 und ceil(n*3/2)
haben.
Meine Numerik liefert:
n Anzahl Permutationen
3 2
4 6
5 8
6 20
7 30
8 14
9 144
10 6
11 250
12 176
13 298
14 6
15 6294
16 6
17 1252
18 308
19 1884
20 6
21 45728
22 6
23 8562
24 256
25 10220
26 6
27 337750
28 6
29 44654
30 84
31 54536
32 6
Nochmal meine Zählweise der Anzahl Permutationen: Einzige Festlegung
ist, daß die 0 an Postion 0 steht. Die Anzahl der Permutationen müsste
also noch mit n multipliziert werden.
Auffällig ist, daß es für n = 6*k+2 und n = 6*k+4 jeweils nur
sechs Lösungen gibt, die auch noch alle quasi-gleich sind, also
nach denselben Strickmustern aufgebaut sind.
Ausnahme: n=8 hat mehr Lösungen.
Hingegen gibt es für n = 6k+3 extrem viele passende Permutationen.
Hier scheint es ziemlich viel Spielraum zu geben, durch Vertauschungen
gleichgute Lösungen zu erzielen.
>Noch eine Frage an die Experten:
>Aus der Tatsache "Die Summe der 3-er-Päckchen ist das 3-fache der
>Summe der einzelnen Zahlen" folgte ja die Abschätzung G(n) >= C(n),
>wobei C(n) = ceiling(3*(n+1)/2). Und die wirklich pfiffige Erkenntnis, dass
>Gleichheit nur für n=6 sein kann, ergibt dann G(n) - C(n) >= 1 für n > 6.
>Daraus folgt dann z.B. die Antwort auf Aufgabe 4 des Bundeswettbewerbs
>Mathematik 2002, weil C(12)=ceiling(3*13/2)=ceiling(39/2)=20 und 12 > 6,
>mit der Konsequenz G(12) > 20.
>Hier die Frage: Habt Ihr evtl. eine allgemeingültige Antwort darauf, wann
>G(n) - C(n) = 1 ist, wann 2 herauskommt und ob evtl. mal ein Wert > 2 zu
>erwarten ist ?
Wir sind nach meiner Einschätzung kurz davor, bewiesen zu haben,
daß G(n) = ceil(n*3/2)+3, außer für die bekannten Ausnahmen
für n=3, 5, 6, 9 und 15. Ich habe bis n=99 oder 100 nach weiteren
Ausreißern nach unten gesucht, und keine gefunden. Wenn meine
Bauvorschriften stimmen, gibt es auch keine Ausreißer nach oben.
Deine Differenz G(n)-C(n) ist also irgendwann immer abwechselnd 1 und 2.
>Hier ist die entsprechende Tabelle für die ersten bekannten Werte:
> n C(n) G(n) G(n)-C(n)
>----------------------------------
> 6 11 11 0
> 7 12 14 2
> 8 14 15 1
> 9 15 16 1
>10 17 18 1
>11 18 20 2
>12 20 21 1
>13 21 23 2
>14 23 24 1
>15 24 25 1
>16 26 27 1
>17 27 29 2
>18 29 30 1
>19 30 32 2
>20 32 33 1
>21 33 35 2
>22 35 36 1
Bis n=33 kannst Du das Muster als numerisch gesichert fortsetzen.
Mindestens dort stimmt G(n) = ceil(n*3/2)+3.
>Ach ja, noch ein letztes zur Theorie-Diskussion. Ich denke, dass
>es gar nicht schlecht wäre, unsere zyklischen Permutationen
>gleich auf den ganzen Zahlen Z zu definieren. Also p: Z -> {1..n}
>mit der Eigenschaft p(x) = p(y) für x=y mod n. Dann ist es wurscht,
>"wo man anfängt". Knipst man das Lichtlein auf Position 5 an,
>dann gehen alle Lichtlein auf den Positionen 5+n, 5-n, 5+2n, 5-2n
>usw. mit an.
Und alle diese Lichtlein haben dieselbe Helligkeit. Kann man machen,
und macht vielleicht Sinn, wenn man das ganze sauber aufschreiben
will und verstärkt mit den Bezeichnungen der Positionen zu tun
hat (und nicht ständig modulo schreiben will).
>Herzliche Grüsse und - vorsorglich - ein Gutes Neues Jahr
>Rainer Rosenthal
Danke schön. Aber da Du ja offenbar auch im Urlaub die News liest,
wirst Du sicherlich noch häufiger in diesem Jahr von uns hören...
Gruß,
Kurt.
Rainer Rosenthal
Kurt Stege <kurt-...@online.de> schrieb
[ klare und weitreichende Analyse zum Zahlenkreis ]
Hallo Kurt,
ich bin wirklich beeindruckt nicht bloss von dem Eifer
sondern inzwischen auch von den Resultaten
Ihr scheint ja die Funktion G(n) vollends ausgegraben
zu haben und ihre schöne einfache Formel gefunden
zu haben. Lediglich im unteren Zahlenbereich gibt es
ein paar Ausnahmen, die nun als solche erkannt sind.
Wenn dies Resultat rigoros bestätigt ist, halte ich das
für eine richtig Applaus-würdige und im NJAS-Archiv
unbedingt festzuhaltende mathematische Errungenschaft.
*** Das schaue ich mir doch gleich mal an
*** C2(n)=ceiling(3n/2)+3 ***
n C2(n) G(n) G(n)-C2(n)
--------------------------------------
1 5 3 -2 Ausnahme
2 6 4 -2 Ausnahme
3 8 6 -2 Ausnahme
4 9 9 0
5 11 10 -1 Ausnahme
6 12 11 -1 Ausnahme
7 14 14 0
8 15 15 0
9 17 16 -1 Ausnahme
10 18 18 0
11 20 20 0
12 21 21 0
13 23 23 0
14 24 24 0
15 26 25 -1 Ausnahme
16 27 27 0
17 29 29 0
18 30 30 0
19 32 32 0
20 33 33 0
21 35 35 0
22 36 36 0
Die Ausnahmen werden "immer seltener". Ob wohl
n=15 die letzte Ausnahme war ?
Gutes Gelingen weiterhin,
Gruss,
Rainer Rosenthal
r.ros...@web.de
Philipp Zumstein
wrote:
>>>>Ich kann - glaub ich - beweisen, dass für n=6*k+1 (one-based) die
>>>>Gleichheit nicht erfüllt werden kann.
>>
>>Ich schreib dir hier mal meine Argumentation (Beweis) hin:
>>
>>=========================
>>Für n = 6*k+1 ist die Durchschnittdreiersumme d = 3/2*(6*k+2) = 9*k+3,
>>alle Zahlen zusammen ergeben s_ges = (6*k+1)*(6*k+2) / 2 =
>>(6*k+1)*(3*k+1) = 18*k^2+9*k+1.
>
>Stimmt.
>
>>Irgendwo steht die Eins. Die restlichen Zahlen summieren sich auf zu
>>s_rest = 18*k^2+9*k.
>
>Stimmt.
>
>>Diese 6*k Zahlen bilden 2*k Dreiersummen. Auf solch eine Dreiersumme
>>fallen im Durchschnitt s_rest / (2*k) = (18*k^2+9*k) / (2*k) =
>>9*k+4.5.
>
>Aus allen 6k+1 vorhandenen Dreiersummen suchst Du Dir 2k Dreiersummen
>willkürlich aus, die dann den Durchschnitt s_rest bilden.
>
>>==> G(6*k+1) >= 9*k+5.
>
>Verblüffend, aber einleuchtend. Man muß ja gar nicht alle Dreiersummen
>betrachten; es reicht ja eine einzige. Und wenn diese in den ausgewählten
>2k Dreiersummen drin ist, ist alles klar.
>Stimmt also.
>
>>Vielleicht kannst du dies mal durchdenken und (hoffentlich)
>>bestätigen, dass die Argumentation richtig ist.
>
>Ja. Ist von mir als Beweis akzeptiert.
Juhui!
>Diese Beweisidee klaue ich gleich, und führe sie für n=6k+3 und n=6k+5 durch.
Dies habe ich auch probiert aber nicht auf Anhieb geschafft. Ich habe
das Ganze auch etwas anders angeschaut als du. Aber deine Beweise hier
klappen m.A. siehe aber Zwischenbemerkungen.
>Sei n = 6k + 3 (k >= 1).
>
>Dann ist d = 9k+6 und s_ges = 18k^2 + 21k + 6.
>Auch hier werden wieder 2k Dreiergruppen ausgesucht, die nicht-überlappend
>sind.
>
>(Einschub zur Herleitung des Beweises, wird für den Beweis selbst
>nicht benötigt:
>
>Damit G(n) > 9k + 6 folgt, muß s_rest größer als (9k+6)*(2k) = 18k^2+12k sein.
>s_ges - s_rest muß also kleiner als 9k+6 sein. Die drei Kugeln, die in den
>2k Dreiersummen nicht vorkommen, müssen also zusammen höchstens 9k+5 sein.
>
>Einschub Ende)
>
>Ich wähle die 2k Dreiergruppen wie folgt:
>- Der kleinste Wert, die 1, soll nicht drin sein.
>- Von allen Positionen, die nicht dieselbe Position
> modulo 3 haben, wie die 1, suche ich den kleinsten Wert
> und lasse diese Postion weg. Es sind nur 1/3 n Positionen
> ausgeschlossen, die im schlimmsten Fall die Werte von
> 1 bis 1/3 n besetzen. Diese Position hat also höchstens
> den Wert 1/3 n + 1.
>- Irgendeine beliebige dritte Position kommt in den 2k ausgewählten
> Dreiersummen auch nicht vor. Diese hat höchstens den Wert n.
>
>Die Summe dieser drei Werte ist also kleiner oder gleich
>(1) + (1/3 n + 1) + (n) = 1 + (2k + 2) + (6k + 3) = 8k + 6.
>
>Damit ist s_rest >= s_ges - 8k + 6 = 18k^2 + 13k.
Klammer vergessen: s_rest >= s_ges - (8k + 6) = 18k^2 + 13k.
>Die durchschnittliche Dreiersumme in diesen 2k Dreiersummen
>beträgt also mindestens (18k^2 + 13k) / 2k = 9k + 6.5
>
>Also ist G(2k+3) >= 9k + 7.
Dies sollte wohl eine 6 statt eine 2 sein:
G(6k+3) >= 9k + 7.
>Sei n = 6k + 5 (k >= 1).
>
>Dann ist d = 9k+9 und s_ges = 18k^2 + 31k + 15.
Achtung: (6k+5)*(3k+3) = 18k^2 + 33k + 15.
>(Einschub:
>
>Diesmal bleiben 2k+1 Dreiersummen übrig. Damit G(n) > 9k + 9 folgt,
>muß s_rest größer als (9k+9)*(2k+1) = 18k^2+27k+9 sein.
>s_ges - s_rest muß also kleiner als 4k+6 sein. Die zwei Kugeln, die in den
Hier muss es 6k + 6 (oben) und 6k+5 (unten) heissen.
>2k+1 Dreiersummen nicht vorkommen, müssen also zusammen höchstens 4k+5 sein.
>
>Einschub Ende)
>
>Aus den 6k+5 Zahlen werden zwei ausgesucht:
>- Die kleinste Zahl, die 1.
>- Die kleinste der folgenden Zahlen: Der rechte Nachbar von der 1 oder
> davon ausgehend in Dreierschritten weiter, bis zur letzten Möglichkeit,
> dem linken Nachbar der 1. Insgesamt stehen also etwa 1/3 n, genau 2k+2
> Plätze zur Auswahl. Die kleinste Zahl auf diesen Positionen hat höchstens
> den Wert n - (2k+2) + 1 = 4k + 4.
>
>Die Summe dieser beiden Zahlen ist höchstens 4k + 5; der Rest geht wie gehabt.
Genauer:
s_rest = s_ges -(4k+5) = 18k^2 + 29k + 10
==> (18k^2+29k+10) / (2k+1) = 9k+10.
>Also ist G(2k+5) >= 9k + 10.
Also ist G(6k+5) >= 9k + 10.
Schöne Weiterführung meiner Argumentation, aber im Allgemeinen sind
deine Abschätzung relativ schwach. Denn du beweist damit z.B.
G(3*6+5) = G(23) >= 37 = 3*9+10
Aber weil d(23) = 3/2*(24) = 36 ist, ist sowieso schon klar, dass es
keinen Zahlenkreis mit 36 gibt. Viel nützlicher/interessanter wäre zu
beweisen dass G(23) >= 38 ist. Dann kann man mit deinen schönen
Mustern folgern, dass G(23) <= 38 ist, und somit schlussendlich G(23)
= 38.
Ich versuche hier mal einen Beweis für die
Beh.: G(11) = G(6+5) >= 20.
*****
Bew.:
*****
Ich ordne die 11 Zahlen in einem Kreis folgendermassen an (Zeichnung
hier wird halt statt Kreis eine Linie sein):
.. a_4 .. .. a_1 1 a_2 .. .. a_3 ..
Die a_i sind deiner Konstruktion folgend; ich nenne sie die "Nachbarn"
von 1 (es kommt mir kein besserer Name so auf die Schnelle in den
Sinn). Im günstigsten Fall gibt es ein a_i <= 7, ansonsten sind a_1
bis a_4 die Zahlen 11 bis 8.
Fall a) Es gibt ein a_i <= 7:
*******
Schliesse die 1 und diese Zahl a_i aus.
Fall b) Es gibt kein a_i <= 7:
*******
Die Zahl 2 ist in einem der übrigen 6 Plätze. Sie besitzt 3
"Nachbarn", die nicht "Nachbarn" der 1 sind. Im ungüngstigsten Fall
sind dies 7,6,5. Schliesse die Werte 2 und 5 (oder kleiner) aus.
Nach beiden Fällen besitzt man eine Restsumme:
s_rest >= 11*12/2 - 8 = 66 -8 = 58.
Diese Restsumme ist genau die Summe von 3 Dreiersummen. Auf diese 3
Dreiersummen fällt im Mittel genau 58 / 3 = 19.33. Also muss
mindestens eine Dreiersumme grösser als 19 sein.
==> G(11) >= 20.
q.e.d.
Ich hoffe es stimmt noch. Dieses Beweisverfahren kann man
wahrscheinlich verallgemeiner auf n=6k+5. Ich werde dies wohl noch
etwas vesuchen. Ob der Fall n=6k+3 auch so leicht geht, bezweifle ich,
denn da muss man noch auf die Spezialfälle n=9,15 aufpassen. Und ich
weiss ja nicht ob es noch mehr Spezialfälle gibt.
Gruss
Philipp
Kurt Stege
>Die Ausnahmen werden "immer seltener". Ob wohl
>n=15 die letzte Ausnahme war ?
Da bin ich mir mittlerweile nicht mehr ganz so sicher.
Meinen "Beweis" für den Fall n=6k+3, in denen die
Ausnahmen 9 und 15 ja vorkommen, habe ich zumindest
zurückziehen müssen. Meine numerischen Ausertungen
haben für n=21, 27, 33 und 39 ergeben, daß es dort
keine Ausnahme gibt, aber die Suche nach möglichen
Lösungen dauert doch in diesem Fall recht lange.
search for n = 3 (0...4)
found 2 solutions in 0 seconds
search for n = 9 (0...13)
found 16 solutions in 0 seconds
search for n = 15 (0...22)
found 8 solutions in 0 seconds
search for n = 21 (0...31)
found 0 solutions in 0 seconds
search for n = 27 (0...40)
found 0 solutions in 5 seconds
search for n = 33 (0...49)
found 0 solutions in 89 seconds
search for n = 39 (0...58)
found 0 solutions in 1866 seconds
search for n = 45 (0...67)
... habe ich vorerst abgebrochen, wegen zu erwartender Rechenzeit
von über 10 Stunden.
Man merkt schon, daß die Suche ziemlich viele Bäume abklappern muß,
und es nicht so einfach ist, frühzeitig die Unmöglichkeit der
Lösung zu finden.
Bei geraden n findet der Suchalgorithmus sofort (nach einer konstanten
Zeit unabhänig von n) raus, das keine Lösung möglich ist. Dort wird
wohl immer nach spätestens sechs Schritten die Schleife gefunden,
mit der ja auch der Beweis arbeitet.
Bei ungeraden n reicht die einfache Abschätzung noch nicht aus; dort
findet das Programm immer Permutationen, die erst kurz vor Schluß
zusammenbrechen, wenn schon fast alle Elemente verteilt worden sind.
Gruß,
Kurt.
Kurt Stege
>On Sat, 29 Dec 2001 17:42:49 +0100, Kurt Stege <kurt-...@online.de>
>wrote:
>>Diese Beweisidee klaue ich gleich, und führe sie für n=6k+3 und n=6k+5 durch.
>>Sei n = 6k + 3 (k >= 1).
Das verschiebe ich auf später...
>>Sei n = 6k + 5 (k >= 1).
>>
>>Dann ist d = 9k+9 und s_ges = 18k^2 + 31k + 15.
>
>Achtung: (6k+5)*(3k+3) = 18k^2 + 33k + 15.
Oh, ja. Da habe ich 18+15 nicht mehr rechnen können.
>>(Einschub:
>>
>>Diesmal bleiben 2k+1 Dreiersummen übrig. Damit G(n) > 9k + 9 folgt,
>>muß s_rest größer als (9k+9)*(2k+1) = 18k^2+27k+9 sein.
>>s_ges - s_rest muß also kleiner als 4k+6 sein. Die zwei Kugeln, die in den
>
>Hier muss es 6k + 6 (oben) und 6k+5 (unten) heissen.
Vor allem vermuten wir ja G(6k+5) = 9k+11. Also will ich zeigen,
daß G(6k+5) > 9k+10 gilt.
(9k+10) * (2k+1) = 18k^2+29k+10.
s_ges - (9k+10) * (2k+1) = 4k+5
Ich muß also zwei Zahlen finden, deren Summe kleiner als 4k+5
ist, und die angeordnet sind, daß der Rest noch 2k+1 disjunkte
Dreiersummen ergibt.
>>2k+1 Dreiersummen nicht vorkommen, müssen also zusammen höchstens 4k+5 sein.
>>
>>Einschub Ende)
>>
>>Aus den 6k+5 Zahlen werden zwei ausgesucht:
>>- Die kleinste Zahl, die 1.
>>- Die kleinste der folgenden Zahlen: Der rechte Nachbar von der 1 oder
>> davon ausgehend in Dreierschritten weiter, bis zur letzten Möglichkeit,
>> dem linken Nachbar der 1. Insgesamt stehen also etwa 1/3 n, genau 2k+2
>> Plätze zur Auswahl. Die kleinste Zahl auf diesen Positionen hat höchstens
>> den Wert n - (2k+2) + 1 = 4k + 4.
>>
>>Die Summe dieser beiden Zahlen ist höchstens 4k + 5; der Rest geht wie gehabt.
Die beiden ausgewählten Zahlen liegen also nur um eins zu groß. Kriege ich
die Summe immer um eins kleiner, ist das gesuchte gezeigt.
Wenn _nicht_ der Worst-Case vorliegt, also nicht gerade die Zahlen
von 4k+4 bis 6k+5 rechter Nachbar von eins (modulo 3) sind, ist die
Sache einfach: Dann bleibt der Auswahlalgorithmus unverändert, und
die zweite Zahl ist kleiner als 4k+4.
Liegt genau dieser Worst-Case vor, wird ein anderer Algorithmus
verwendet:
OBdA sei in diesem Worst-Case 1 auf Position 1, und damit die
großen Zahlen 4k+4 ... 6k+5 irgendwie auf den Postionen 2, 5, 8,
11, ..., 6k+2, 6k+5=n verteilt. Dann wähle folgende beiden
Zahlen aus:
a = die kleinste Zahl auf den Positionen 3, 6, 9, ..., 6k+3
b = die kleinste Zahl auf den Positionen 4, 7, 10, ..., 6k+4
Für a und b stehen jeweils 2k+1 Zahlen zur Auswahl (die 2k+2
größten Zahlen und die eine kleinste Zahl 1 wurden ausdrücklich
von der Auswahl ausgenommen).
Eine der beiden Zahlen ist die 2. Die andere Zahl ist höchstens
2k+3 (nämlich wenn in der Gruppe, in der die 2 steht, auch die
anderen kleinen Zahlen 2, 3, ..., 2k+2 stehen).
Es ist also a+b <= 2k+5 < 4k+5 für k>=1.
Bingo!
>Schöne Weiterführung meiner Argumentation, aber im Allgemeinen sind
>deine Abschätzung relativ schwach.
Ja. Gute Idee, aber schlechte Durchführung. Zu oft verrechnet, und
deshalb was anderes gezeigt, als ich wollte. Ziel war in beiden Fällen
schon die starke Version.
Ja. Scheint naheliegend zu sein. Habe ich oben genauso repariert,
und ausdrücklich mir diese Version vorher noch nicht so genau
angeschaut, um nicht voreingenommen zu werden.
>Dieses Beweisverfahren kann man
>wahrscheinlich verallgemeiner auf n=6k+5. Ich werde dies wohl noch
>etwas vesuchen.
Ja, kann man. Siehe oben.
>Ob der Fall n=6k+3 auch so leicht geht, bezweifle ich,
>denn da muss man noch auf die Spezialfälle n=9,15 aufpassen. Und ich
>weiss ja nicht ob es noch mehr Spezialfälle gibt.
Ich werde für 6k+3 sicherlich noch etwas tüfteln.
Das ist wohl die letzte echte Lücke in der G-Funktion.
Selbst wenn die von mir angegebenen Musterlösungen/Bauvorschriften
noch kaputt sein sollten, werden es nur Tippfehler sein.
Wenn wir viel Pech haben, müssen wir die Fälle
18k+3
18k+9
18k+15
getrennt angehen. Zumindest sind die Spezialfälle dann
durch k>0 abgedeckt.
Gruß,
Kurt.
Philipp Zumstein
Ich habe dieses Posting nur ausgedruckt und mal überflogen. Dieses
Folgeposting ist also nur andeutungsweise geschrieben (hoffentlich
versteht man hier mein Deutsch).
On Sun, 30 Dec 2001 00:39:31 +0100, Kurt Stege <kurt-...@online.de>
wrote:
>Der Fall 3k+0 ist aufgespaltet in die Unterfälle
>9k+0, 9k+3 und 9k+6:
>
>>Hier eine Bauvorschrift für n = 9k+6: (gilt sogar ab k >= 0)
>>snip
Diese Bauvorschrift für n = 9k+6 habe ich mir nicht so genau
angeschaut, aber sie sehen ja alle relativ ähnlich aus.
>Hier eine Bauvorschrift für n = 9k+3: (gilt sogar ab k >= 0)
>
>1. Zeile: Zahlen 0 ... 3k
>2k+1 Werte: 0 1 3 4 6 7 ... 3k-3 3k-2 3k
+3 periodisch
>k Werte: 3k-1 3k-4 ... 8 5 2
-6 periodisch
>
>2. Zeile: Zahlen 6k+2 ... 9k+2
>k Werte: 9k+1 9k-2 9k-5 ... 6k+7 6k+4
-6 periodisch
>2k+1 Werte: 6k+2 6k+3 6k+5 6k+6 ... 9k-4 9k-3 9k-1 9k-0 9k+2
+3 periodisch
>
>3. Zeile: Zahlen 3k+1 ... 6k+1
>k Werte: ... 6k-5 6k-4 6k-2 6k-1 6k+1
+3 periodisch
>k Werte: 6k 6k-3 6k-6 ... 3k+6 3k+3
-6 periodisch
>k+1 Werte: 3k+1 3k+2 3k+4 3k+5 ...
+3 periodisch
Zur Untersuchung der Eigenschaften, schlage ich eine Trennung der
Bereiche vor: die ersten 3k Zahlen, die zweiten 3k Zahlen, die letzten
3k Zahlen und der Rest. Natürlich darf man auch die Dreiersummen
zwischen diesen Bereichen nicht vergessen. Aber in diesem Bereichen
gilt die von mir oben skizzierte Periodizität. Darum genügt es die
ersten 6 Dreiersummen von diesen jeweiligen Bereichen zu untersuchen
und die Dreiersummen zwischen den Bereichen. So ähnlich wie ich dies
beim Fall 6k+2 gemacht habe.
>Beispiele zur Übersicht:
>
>k=0 (n=3):
>0 2 1
>
>k=1 (n=12):
> 0 1 3 2
>10 8 9 11
> 7 6 4 5
>(also die Permutation 0 10 7 1 8 6 3 9 4 2 11 5)
Die Dreiersummen hier betragen:
20,21,19,18; dreimal wiederholend
>k=3 (n=30):
>00 01 03 04 06 07 09 08 05 02
>28 25 22 20 21 23 24 26 27 29
>16 17 19 18 15 12 10 11 13 14
Die Dreiersummen hier betragen:
47,48,45,46,48,45,47,48,46,45; dreimal wiederholend
>(Also die Reihe 00 28 16 01 25 17 ... 02 29 14)
> snipped [Weil ich noch nichts dazu zu sagen weiss.]
>Hier eine Bauvorschrift für n = 3k+1: (gilt ab k >= 1):
>
>1. Zeile mit k+1 Werten: 0 1 3 4 6 7 ...
+3 periodisch
>2. Zeile mit k Werten: 3k-1 3k-4 3k-7 ... 8 5 2
-6 periodisch
>3. Zeile mit k Werten: ... 3k-6 3k-5 3k-3 3k-2 3k
+3 periodisch
>
>Das ergibt die Permutation: 0 3k-1 . 1 3k-4 . 3 3k-7 ... 5 3k-2 . 2 3k 7
>
>Beispiel für k=5, n=16:
>00 01 03 04 06 07
>14 11 08 05 02
>09 10 12 13 15
>
>
>
>Hier eine Bauvorschrift für n = 3k+2: (gilt ab k >= 1):
>
>1. Zeile mit k+1 Werten: 0 1 3 4 6 7 ...
+3 periodisch
>2. Zeile mit k+1 Werten: ... 3k-5 3k-4 3k-2 3k-1 3k+1 3k+2
+3 periodisch
>3. Zeile mit k Werten: 3k 3k-3 3k-6 ... 8 5 2
-6 periodisch
>
>Beispiel für k=5, n=17:
>00 01 03 04 06 07
>09 10 12 13 15 16
>14 11 08 05 02
>
>Also: 0 9 14 1 10 11 3 12 8 4 13 5 6 15 2 7 16
Diese beiden letzten Fälle sind ja einfach eine Verallgemeinerung
deiner Fälle 6n+2 und 6n+4. Diese sind wieder schön periodisch, so
dass der Nachweis der gewünschten Eigenschaften relative leicht fallen
sollte.
>Damit habe ich für alle n jeweils eine konkrete Permutationen p(n)
>angegeben. Ich behaupte, ohne es hier konkret gezeigt zu haben,
>daß diese Permutationen jeweils als größte Dreiersumme
>genau den Wert ceil(3/2 n) hat. Für "mittelkleine" n habe ich
>dies exemplarisch überprüft. Es allgemein nachzurechnen, ist
>eine Fleißaufgabe, die ich zumindest heute nicht mehr machen
>werde. Bei ganz kleinen n mag es noch Ausnahmefälle geben,
>die aber hier mittlerweile gut bekannt sind.
>
>Was auch bekannt und als nachgewiesen gilt, ist:
>Für gerade n (außer n=6) ist die größte Dreiersumme
>mindestens 3/2 n, also zusammen mit diesem Ergebnis hier
>sogar genau 3/2 n. (Bei geraden n ist ceil(3/2 n) = 3/2 n.)
>
>Was noch fehlt, aber bereits in diesem Thread in Arbeit ist,
>ist die untere Abschätzung für die minimale größte Dreiersumme
>für ungerade n. Wenn diese Arbeiten durch sind, und die Ergebnisse
>dieses Threads nachgerechnet wurden, ist die gesuchte Funktion
>f(n) gut bekannt, und nicht mehr sonderlich aufregend.
Schöne Zusammenfassung des Standes der Dinge. Ich muss da in diesem
anderen Thread auch noch etwas hinzufügen bzw. mein Posting
korrigieren.
Gruss
Philipp
Philipp Zumstein
<hzum...@bluewin.ch> wrote:
>On Sat, 29 Dec 2001 17:42:49 +0100, Kurt Stege <kurt-...@online.de>
>wrote:
> [Herleitung gesnipped; unten korrigiert]
>>Also ist G(6k+3) >= 9k + 7.
> [Herleitung schon wieder weggesnipped]
>Also ist G(6k+5) >= 9k + 10.
>
>Ich versuche hier mal einen Beweis für die
>Beh.: G(11) = G(6+5) >= 20.
>*****
Ja, beim Versuch ist es wohl geblieben. Denn der Beweis ist
fehlerhaft.
>Bew.:
>*****
>Ich ordne die 11 Zahlen in einem Kreis folgendermassen an (Zeichnung
>hier wird halt statt Kreis eine Linie sein):
>
>.. a_4 .. .. a_1 1 a_2 .. .. a_3 ..
>
>Die a_i sind deiner Konstruktion folgend; ich nenne sie die "Nachbarn"
>von 1 (es kommt mir kein besserer Name so auf die Schnelle in den
>Sinn). Im günstigsten Fall gibt es ein a_i <= 7, ansonsten sind a_1
>bis a_4 die Zahlen 11 bis 8.
>
>Fall a) Es gibt ein a_i <= 7:
>*******
>Schliesse die 1 und diese Zahl a_i aus.
>
>Fall b) Es gibt kein a_i <= 7:
>*******
>Die Zahl 2 ist in einem der übrigen 6 Plätze. Sie besitzt 3
>"Nachbarn", die nicht "Nachbarn" der 1 sind. Im ungüngstigsten Fall
>sind dies 7,6,5. Schliesse die Werte 2 und 5 (oder kleiner) aus.
Falsch. Dies ist im Allgemeinen nicht richtig. Die Zwei kann 3
unabhängige Nachbarn besitzen aber sie kann auch 2 oder nur 1
unabhängigen Nachbarn besitzen. ["unabhängig" soll hier und von nun an
bedeuten dass sie nicht auch noch Nachbarn von einer anderen Zahl,
also hier von der Eins sind.] Einen unabhängigen Nachbarn besitzt die
Zwei mindestens. Dies ist gerade einer der beiden angrenzenden Zahlen
zur Zwei.
>Nach beiden Fällen besitzt man eine Restsumme:
>s_rest >= 11*12/2 - 8 = 66 -8 = 58.
>Diese Restsumme ist genau die Summe von 3 Dreiersummen. Auf diese 3
>Dreiersummen fällt im Mittel genau 58 / 3 = 19.33. Also muss
>mindestens eine Dreiersumme grösser als 19 sein.
>==> G(11) >= 20.
>q.e.d.
>
>Ich hoffe es stimmt noch. Dieses Beweisverfahren kann man
>wahrscheinlich verallgemeiner auf n=6k+5. Ich werde dies wohl noch
>etwas vesuchen.
Es stimmt also nicht mehr. Aber nun kommt hier mein Rettungsversuch:
Falls die Zwei mehr als einen unabhängigen Nachbarn besitzt sind wir
fertig (weil einer von diesen beiden kleiner oder gleich 6 ist, damit
wird s_rest genügend gross).
Falls die Zwei nur einen unabhängigen Nachbarn besitzt und dieser ist
noch gerade die 7, dann geht man weiter zur Drei. Falls diese mehr als
zwei unabhängige Nachbarn besitzt, ist man fertig. Falls sie nur einen
unabhängigen Nachbarn besitzt der kleiner oder gleich 5 ist, ist man
fertig. Ansonsten besitzt die Drei nur einen unabhängigen Nachbarn die
6. Dies kann man weiter durchdenken, bis man wirklich zum "worst case"
kommt. Dies stellt folgende Anordnung (in einem Kreis sieht es
natürlich schöner aus) dar:
1, a1, 7, 2, a4, 6, 3, a3, 5, 4, a2
Weil nun aber eines der a_i = 11 ist, ergibt sich eine Dreiersumme von
9+11=20.
So. Nun der allgemeine Fall: n = 6*k+5:
Es gibt 2*k+1 Dreierblöcke.
Die Eins hat 2*k+1+1 = 2*k+2 Nachbarn.
Im ungünstigsten Fall ist der kleinste dieser Nachbarn:
(6*k+5)-(2*k+2)+1 = 4*k+4.
Die Zwei ist an einem der übrigen 4*k+2 Plätze. Sie besitzt im
ungünstigsten Fall nur einen unabhängigen Nachbarn.
ect.=>worst case: 2, ..., 2*k+2 haben nur einen Nachbarn und dieser
ist 4*k+3, ..., 2*k13.
Zusammen ergeben diese immer 4*k+5. Irgendwo steht die 6*k+5. Daraus
folgt es gibt eine Dreiersumme von 10*k+10 > 9*k+10, für k>=0.
Das heisst nun z.B. für n=17 folgt, im günstigeren Fällen ist die
maximale Dreiersumme strikt grösser als 9*2+10=28; und im
ungünstigsten Fall (ungünstig für den Beweis) ist die maximale
Dreiersumme grösser als 10*2+10=30. Daraus folgere ich, dass der
ungüngstigste Fall nur für k=0 und k=1 auftritt. Ansonsten ergibt der
ungünstigste Fall einen zu schlechten Zahlenkreis.
Nun, hoffe ich, dass - ohne Fehler; vielleicht noch nicht so schön
ausformuliert - gilt G(6*k+5) >= 9*k+11.
> Ob der Fall n=6k+3 auch so leicht geht, bezweifle ich,
>denn da muss man noch auf die Spezialfälle n=9,15 aufpassen. Und ich
>weiss ja nicht ob es noch mehr Spezialfälle gibt.
Ich habe auch noch keine genaue Strategie, aber "schau'mer mal".
Gruss
Philipp
Kurt Stege
Naja, macht nix.
Kurt Stege <kurt-...@online.de> wrote:
>Ich muß also zwei Zahlen finden, deren Summe kleiner als 4k+5
>ist, und die angeordnet sind, daß der Rest noch 2k+1 disjunkte
>Dreiersummen ergibt.
>Liegt genau dieser Worst-Case vor, wird ein anderer Algorithmus
>verwendet:
>
>OBdA sei in diesem Worst-Case 1 auf Position 1, und damit die
>großen Zahlen 4k+4 ... 6k+5 irgendwie auf den Postionen 2, 5, 8,
>11, ..., 6k+2, 6k+5=n verteilt. Dann wähle folgende beiden
>Zahlen aus:
>a = die kleinste Zahl auf den Positionen 3, 6, 9, ..., 6k+3
>b = die kleinste Zahl auf den Positionen 4, 7, 10, ..., 6k+4
Diese beiden Zahlen sind schlecht ausgewählt. Liegt zum Beispiel
b auf Position 4, muß a als "Nachbar" von Position 4 gewählt
werden (5, 8, 11, ... oder 3, 0, -3, ...), aber sicherlich nicht
auf Postion 6.
Philipp hat den Fall n=6k+5 inzwischen ausreichend abgeschlossen.
Gruß,
Kurt.
Kurt Stege
>On Sun, 30 Dec 2001 13:45:23 +0100, Philipp Zumstein
><hzum...@bluewin.ch> wrote:
>>Fall b) Es gibt kein a_i <= 7:
>>*******
>>Die Zahl 2 ist in einem der übrigen 6 Plätze. Sie besitzt 3
>>"Nachbarn", die nicht "Nachbarn" der 1 sind. Im ungüngstigsten Fall
>>sind dies 7,6,5. Schliesse die Werte 2 und 5 (oder kleiner) aus.
>
>Falsch. Dies ist im Allgemeinen nicht richtig. Die Zwei kann 3
>unabhängige Nachbarn besitzen aber sie kann auch 2 oder nur 1
>unabhängigen Nachbarn besitzen.
Das stimmt. Und läßt mich stutzig werden...
Ja, meine Version des "Beweises" ist auch Humbug.
>Es stimmt also nicht mehr. Aber nun kommt hier mein Rettungsversuch:
<snip>
>Dies kann man weiter durchdenken, bis man wirklich zum "worst case"
>kommt. Dies stellt folgende Anordnung (in einem Kreis sieht es
>natürlich schöner aus) dar:
>
>1, a1, 7, 2, a4, 6, 3, a3, 5, 4, a2
Dieses rekursive "dann muß es aber so sein" war mir doch ein
wenig zuviel. Erst schaue ich mir noch Deinen allgemeinen Fall
an, und wenn das nicht hilft, das Beispiel für n=11 in aller Ruhe.
>So. Nun der allgemeine Fall: n = 6*k+5:
>
>Es gibt 2*k+1 Dreierblöcke.
Und die übrigbleibenden beiden Zahlen sollen aussortiert werden
und eine Summe von kleiner als 4k+5 haben.
>Die Eins hat 2*k+1+1 = 2*k+2 Nachbarn.
>Im ungünstigsten Fall ist der kleinste dieser Nachbarn:
>(6*k+5)-(2*k+2)+1 = 4*k+4.
In allen anderen Fällen sind wir schon fertig.
Siehe Anmerkung [2].
>Die Zwei ist an einem der übrigen 4*k+2 Plätze. Sie besitzt im
>ungünstigsten Fall nur einen unabhängigen Nachbarn.
Soweit noch klar. Womit ich noch Schwierigkeiten habe, ist Dein
nachfolgendes "etc". Im Falle der "2" ist noch klar, daß mindestens
ein unabhängiger Nachbar existiert. Ich sehe sogar ein, daß dafür
die 2 genau drei Felder rechts oder links von der 1 stehen muß.
OK. Nun bin ich einverstanden, auch mit "etc": Die noch "freien
Felder", also die Felder, die noch nicht Nachbar sind, und daher
potentiell als unabhängiger Nachbar zur Verfügugn stehen, treten
immer in Zweiergruppen auf. ObdA steht die 1 an Position 1. Dann
sind 3,4, 6,7, 9,10, ... die 4k+2 freien Felder (in 2k+1 Zweiergruppen).
Die 2 steht in einem dieser freien Felder; der eine direkte Nachbar
der 2 ist ein unabhängiger Nachbar. Da nach Annahme des worst-case
dies der einzige unabhängige Nachbar ist, bleiben jetzt noch 2k+0
Zweiergruppen als freie Felder übrig.
Nun hat, laut worst-case, auch die 3 nur einen unabhängigen Nachbarn,
und schon ist die nächste Zweiergruppe "belegt", also nicht mehr "frei".
(Einer der abhängigen Nachbarn der 3 kann, nach Definition von "unabhängig",
der ehemals unabhängige Nachbar von 2 sein.)
Und noch eine Erkenntnis ist wichtig: Der [1] unabhängige Nachbar ist
jeweils ein direkter Nachbar, also ein Feld links oder rechts davon.
>ect.=>worst case: 2, ..., 2*k+2 haben nur einen Nachbarn und dieser
>ist 4*k+3, ..., 2*k+1.
(Ich habe den Tippfehler "2*k13" nach "2*k+1" korrigiert.)
>Zusammen ergeben diese immer 4*k+5. Irgendwo steht die 6*k+5. Daraus
>folgt es gibt eine Dreiersumme von 10*k+10 > 9*k+10, für k>=0.
Einverstanden. Die Argumentation halte ich für korrekt, will sagen,
ich kann sie nachvollziehen. Ich bin mir aber sicher, es wird etwas
eleganteres geben. Vielleicht nächstes Jahr, jetzt ist 6k+3 wichtiger.
>Nun, hoffe ich, dass - ohne Fehler; vielleicht noch nicht so schön
>ausformuliert - gilt G(6*k+5) >= 9*k+11.
Ja.
Gruß,
Kurt.
Anmerkungen:
[1] Zu diesem Zeitpunkt hatte ich plötzlich die Idee zu [2].
[2] Und hier sind wir schon fertig: Die beiden direkten Nachbarn
von der 1 sind auch Nachbarn im weiteren Sinne, sind also
mindestens 4k+4 und 4k+5, eventuell sogar größer.
Diese drei Felder sind zusammen mindestens 4k+4 + 1 + 4k+5 = 8k+10
aufsummiert. Unser Ring hatte aber als höchste Dreiersumme 9k+10.
Shit. Diese Abkürzung geht doch nicht. Aber die Idee kann in anderen
Fällen weiterhelfen. Deshalb lösche ich sie nicht sofort.
Rainer Rosenthal
Kurt Stege <kurt-...@online.de>
>
> Diese drei Felder sind zusammen mindestens 4k+4 + 1 + 4k+5 = 8k+10
> aufsummiert. Unser Ring hatte aber als höchste Dreiersumme 9k+10.
> Shit. Diese Abkürzung geht doch nicht. Aber die Idee kann in anderen
> Fällen weiterhelfen. Deshalb lösche ich sie nicht sofort.
Hallo Kurt,
kann man bei Euch noch irgendwie mitspielen ?
Welche Baupläne sind denn nach Euer beider Meinung
inzwischen definitiv abgehakt und an welchen seid Ihr
jetzt noch am Basteln ?
Irgendwie hatte ich mitgekriegt, dass Ihr den Fall n=11
nochmal gründlich untersucht. Das ist doch was Handliches
zum Mitdenken ...
Andererseits scheint 6*k+5 jetzt komplett abgehakt. Wo
finde ich den Bauplan ?
Falls ich jetzt ungelegen komme, dann bitte - nicht stören
lassen. Es ist gut, dass die gnadenlose Wühlarbeit so
öffentlich durchgeführt wird - man kann dann im Einzelfall
doch noch mal auf die Begründungen und pfiffigen Einzel-
Einfälle zurückgreifen (wie z.B. den oben zitierten).
Erst waren wir bei Analysen, bei denen der Rest von n mod 3
interessant war, dann kamen die Superdurchbrüche bei mod 6.
Aber zwischendrin habt Ihr das sogar bis mod 18 verfeinert.
Ist das noch amtlich ? Oder wie sieht der aktuelle "Fahrplan" aus ?
Bestimmt werdet Ihr mir das nicht übelnehmen, wenn ich mit
Übersichts-Zwischenfragen "nerve". Es gibt doch auch die
Gelegenheit, dass Ihr selbst Euch nochmal - nachvollziehbar für
alle Mitleser (ich tippe mal auf mindestens 7 (?)) - abstimmt
über den Gesamterfolg bisher und über die anzugehenden Ziele.
Ein wenig ziele ich dabei auch schon auf den zu schreibenden
NJAS-Beitrag, in dem ja diese Bauplan-Arbeit übersichtlich
darzustellen ist.
Mir scheint, dass als Knaller ersten Ranges diese Tatsache zu
erwähnen sein wird (für Euch inzwischen Kalter Kaffee :-), dass
eine Folge x,y,x,y,x,y,x von Dreifachsummen mit y=x+1 für n > 6
nicht möglich ist.
Das könnte z.B. motivierend sein für die Aufspaltung der Fälle
nach den Resten von n modulo 6.
( Dass x,x für n > 3 ausgeschlossen wedren kann, ist wirklich
nur eine putzige Einleitungsbemerkung wert. Aber immerhin für den
interessierten Neuling evtl. ein Anreiz, sich weiter einzulesen, weil
das immerhin ein kurzes Mitdenken erfordert ) - Ich weiss, ich weiss,
Ihr habt ganz andere Sorgen - also: lasst Euch nicht stören, gebt aber
zu gegebener Zeit doch so ein "gemeinsames Communique" heraus,
bitte.
Mit weiter aufmunternden Grüssen,
Rainer Rosenthal
r.ros...@web.de
Kurt Stege
>Ich schreib dir hier mal meine Argumentation (Beweis) hin:
>
>=========================
>Für n = 6*k+1 ist die Durchschnittdreiersumme d = 3/2*(6*k+2) = 9*k+3,
>alle Zahlen zusammen ergeben s_ges = (6*k+1)*(6*k+2) / 2 =
>(6*k+1)*(3*k+1) = 18*k^2+9*k+1.
>
>Irgendwo steht die Eins. Die restlichen Zahlen summieren sich auf zu
>s_rest = 18*k^2+9*k.
>
>Diese 6*k Zahlen bilden 2*k Dreiersummen. Auf solch eine Dreiersumme
>fallen im Durchschnitt s_rest / (2*k) = (18*k^2+9*k) / (2*k) =
>9*k+4.5.
>
>==> G(6*k+1) >= 9*k+5.
>
>Setze k=4 ein, dann erhält man den Spezialfall G(25) >= 41.
>==========================
Die Fälle für 6k+1 (hier) und für 6k+5 und erst recht für 2k
sind mittlerweile abgehakt.
Ich versuche mich jetzt mal wieder an dem wahrscheinlich
schwierigsten Fall, n = 6k+3.
Heute mal wieder die one-based Schreibweise.
Gezeigt werden soll G(6k+3) > 9k+7 für k>=3.
Anders ausgedrückt für die neue Leser ohne den bisher abgemachten
Notationshintergrund:
Sei p eine Permutation, die die Zahlen 1...n auf 1...n abbildet.
Dann gibt es mindestens eine Stelle, bei der die Summe drei
aufeinanderfolgender Zahlen größer als 9k+7 ist (bei einem n
der Form n=6k+3 und k>=3). Dazu wird die Permutation zu einem
Kreis geschlossen, also p(1) ist rechter Nachbar von p(n).
Beweis:
Annahme, dies sei nicht der Fall. Dann gibt es ein Polynom p,
bei dem alle Dreiersummen <= 9k+7 sind.
OBdA. sei p(1) = 1, also die 1 an der ersten Stelle.
Betrachte nun zum einen die Zahlen in Dreierabständen
davon, an Postion 4, 7, 10, ..., 6k-2, 6k+1.
Die größte dieser 2k Zahlen ist mindestens 2k+1 (nämlich
wenn an diesen Postionen die Zahlen von 2 bis 2k+1
verteilt sind), eventuell sogar größer.
Und betrachte zum anderen die Zweiergruppen, die in
den Lücken übrig bleiben:
2,3
5,6
8,9
...
2k+2,2k+3
Es handelt sich insgesamt um 2k+1 Zweiergruppen.
Über die Summe der beiden Zahlen jeder dieser Zweiergruppen
läßt sich einiges aussagen:
Die Summe beträgt mindestens 7k+5. Wäre sie kleiner, könnte
man diese beiden Zahlen zusammen mit der 1 entfernen,
und hätte drei Zahlen entfernt, deren Summe kleiner als
7k+6 wäre. Ein schon häufiger genutztes Argument, siehe
Anmerkung [1], ergibt dann, daß die Permutation p doch
nicht die angenommenen Eigenschaften hat.
Da alle Dreiersummen höchstens 9k+7 sind, kann die
größte vorkommende Zahl auf den verbleibenden Positionen
1, 4, 7, ..., 6k+1 nur 2k+2 betragen.
Auf den 2k+1 Positionen zwischen den Zweiergruppen befinden
sich fast alle kleinen Zahlen von 1 bis 2k+2. Nur eine einzige
davon (nicht die 1, "wahrscheinlich" die 2k+2) ist in einer
der Zweiergruppen enthalten. Noch wichtiger: Zwischen den
Zweiergruppen befinden sich nur die kleinen Zahlen.
Die großen Zahlen in den 2k+1 Zweiergruppen umfassen auf
jeden Fall die 4k+1 Zahlen von 2k+3 bis 6k+3. Diese
Zahlen haben eine Summe von S1 = (2k+3 + 6k+3) * (4k+1)/2 =
16k^2 + 16k + 3.
(Da jede Zweiergruppe als Summe mindestens 7k+5 ist, ist
die Summer aller Zweiergruppen mindestens (7k+1)*(2k+1) =
14k^2 + 17k + 5. Dies paßt noch.)
Jede Dreiergruppe hat ja höchstens 9k+7 als Summe.
Die Einzelzahlen waren von 1 bis 2k+1 (eventuell ist
eine der Zahlen durch 2k+2 ausgetauscht).
Die 2k+1 hat zwei benachbarte Zweiergruppen, die zusammen
mit 2k+1 höchstens 9k+7 groß sind, also einzeln höchstens
7k+6. Die Einzelzahl 2k+0 mag eine dieser beiden als
Nachbar haben, hat aber noch einen zweite Zweiergruppe
als Nachbar, deren Summe höchstens 7k+7 ist.
Alle weiteren Zweiergruppen lassen sich durch 7k+8, 7k+9, ...
abschätzen.
Die Summe aller 2k+1 Zweiergruppen beträgt also mindestens
7k+6 + 7k+6 + 7k+7 + 7k+8 + 7k+9 + ... + 9k+4 + 9k+5 =: S2.
Das ist (2k+1)*(7k+5 + 9k+5)/2 + 1 = 16k^2 + 18k + 6.
Wir wissen aber schon: Die 4k+1 großen Zahlen haben eine
Summe von genau S1 = 16k^2 + 16k + 3. Die letzte Zahl ist
höchstens 2k+2, also kann die Summe aller Zahlen nur
höchstens 16k^2 + 18k + 5 betragen. Und das ist weniger
als S2.
lol :-)
Gruß,
Kurt.
Anmerkung [1]:
Bekannt ist, das
d := 9k+6 der Durchschnitt aller Dreisersummen ist und
s_ges := 18k^2 + 21k + 6 die Summe aller n Zahlen ist.
Der Beweis funktioniert grob so, daß von den 9k+3 Zahlen
drei ausgesucht werden, mit zwei Eigenschaften:
a) Die Summe der drei Zahlen ist kleiner als 7k+6
b) Die restlichen 9k Zahlen bilden 3k disjunkte Dreiersummen.
Über diese 3k Dreiersummen sind zwei Aussagen gültig:
1) Sie ist identisch mit der Summe der 6k beteiligten Zahlen.
Und diese ist größer als s_ges (Summe aller 6k+3 Zahlen)
minus 7k+6 (Abschätzung der Summe der drei ausgenommenen Zahlen).
Also: summe > 18k^2 + 14k
2) Die Summe ist höchstens 2k * (9k+7) = 18k^2 + 14k, da jede
einzelne der 2k Dreiersummen laut Voraussetzung höchstens 9k+7 groß
ist, also: summe <= 18k^2 + 14k
Aus diesem Widerspruch folgt, das das Polynom p gar nicht existieren
kann, wenn wir denn die drei Zahlen mit den beiden Eigenschaften
a) und b) finden.
Anmerkung 2: Der Rest ist Müll, Beweisansätze, die in die Sackgasse
gelaufen sind oder noch nicht zuende geführt sind. Muß nicht
gelesen werden. Ich mag ihn nur noch nicht löschen für den
Fall, daß oben noch der dicke Wurm drin ist.
(Anmerkung: Man könnte auch sechs Zahlen entfernen, so daß nur
2k-1 disjunkte Dreiersummen übrigbleiben. Die Summe dieser sechs
Zahlen muß dann kleiner als 16k+13 sein.)
Wegen b) muß die Auswahl der drei Zahlen wie folgt geschehen:
eine Zahl auf Position 1, 4, 7, ..., 6k+1
eine Zahl auf Position 2, 5, 8, ..., 6k+2
eine Zahl auf Position 3, 6, 9, ..., 6k+3
Es gibt noch weitere Einschränkungen an der Auswahl,
zum Beispiel dürfen nicht die Positionen 1, 3 und 5
ausgewählt werden.
OBdA. sei die 1 an der ersten Postion 1, also p(1) = 1.
Die 1 ist auch die erste der drei Zahlen, die wir wählen.
Damit Bedingung b) erfüllt wird, dürfen die 2. und 3. Zahl
nicht auf den Postionen 4, 7, 10, 6k+1 gewählt werden.
Im Worst-Case sind auf diesen 2k Positionen die Zahlen
2...2k+1 verteilt.
Die 1 hat zwei Nachbarn (an Position 2 und n). Wähle den
kleineren davon. Nach Voraussetzung ist
p(n) + p(1) + p(2) <= 9k+7, wie jede andere Dreiersumme auch.
Da p(1)=1 ist p(n)+p(2) <= 9k+6.
Als zweite Zahl wird p(2) oder p(n) gewählt, jenachdem,
wie das Polynom genau aussieht.
Die dritte Zahl muß wegen Bedingung b) auf einer schon
eingeschränkten Auswahl von Positionen stehen:
Wurde p(2) gewählt, bleiben 2k+1 Positionen zur Auswahl,
nämlich die Positionen 3, 6, 9, ..., 6k, 6k+3.
Wurde p(n) gewählt, bleiben entsprechend ebenfalls 2k+1
Postionen zur Auswahl, nämlich 2, 5, 9, ..., 6k+2.
Sei m2 der kleinste Wert an den Postionen 3, 6, ...
und m3 der kleinste Wert an den Postionen 2, 5, ...
Kurt Stege
Auf Wunsch von Rainer im Posting
Message-ID: <a0o3eo$m6hc6$1...@ID-54909.news.dfncis.de>
hier noch ein Update der Zusammenfassung des bisher
Erreichten sowie ein Ausblick, was im Anschluß erforscht
werden könnte.
Kurt Stege <kurt-...@online.de> wrote:
>Für jedes n gibt es (mindestens) ein Polynom p(n), welches nur
>Dreiersummen zwischen (one-based) floor(n*3/2) und ceil(n*3/2)+3
>enthält. Beispiele für solche Polynome habe ich in Form von
>"Bauvorschriften" in verschiedenen Postings angegeben. Es bleibt
>jedoch der Nachweis fällig, daß die Dreiersummen tatsächlich alle
>in diesem Intervall liegen. [1]
>
>Also G(n) <= ceil(n*3/2) + 3.
>
>Für jedes n gibt es eine Abschätzung, daß gilt
>G(n) >= ceil(n*3/2) + 3. Diese Abschätzungen haben Philipp und
>ich gemacht, wobei bei meinen Abschätzungen noch die Verifikation
>aussteht. [2]
>
>Wenn Nachweis und Verifikation erbracht ist, gilt also:
>
>G(n) = ceil(n*3/2) + 3
>
>mit Ausnahme von manchen kleinen n=1, 2, 3, 5, 6, 9 und 15.
>
>
>Details und Quellen:
>
>[1] Die Bauvorschriften sind von mir in
>Message-ID: <fj8s2u40vaqm582hq...@4ax.com>
>angegeben, und zwar für die folgenden Fälle:
>
>9k+0 (k>=1)
>9k+3 (k>=0)
>9k+6 (k>=0)
>
>3k+1 (k>=1)
>3k+2 (k>=1)
Diese Bauvorschriften sind alle vom Prinzip her sehr
ähnlich und haben die folgenden Eigenschaften:
- Sie sind "gleichmäßig" zwischen jeweils endlich
vielen (maximal sechs) Übergangstellen.
- Dies ist noch nicht korrekt und systematisch nachgewiesen,
sondern von mir nur so gebaut, und von Philipp in einem
Beispiel nachvollzogen:
Die Dreiersummen sind sämtlichst zwischen
(one-based) floor(n*3/2) und ceil(n*3/2)+3.
Achtung: Ich habe die Bauvorschriften für zero-based angegeben.
Was eben noch fehlt, ist, das jemand die Dreiersummen der
Permutationen nach "Bauvorschrift" sauber berechnet und
zweifelsfrei nachweist, daß diese im angegebenen Intervall
liegen. Bislang wurden nur unmathematische, intuitive "Sichtproben"
durchgeführt.
>Die hiervon nicht erfaßten Fälle n=1 und 2 triviale Sonderfälle.
>
>[2] Diese Abschätzungen wurden schon frühzeitig für gerade n
>durchgeführt. Dies hat Helmut Richter am 22.12.2001 für den
>Spezialfall n=10 gemacht, und Philipp am 24.12.2001 in
>Message-ID: <t1be2u0efkacb7c38...@4ax.com>
>für alle geraden n != 6 erweitert.
>
>Für ungerade n hat Philipp Zumstein die zündene Idee gehabt und in
>Message-ID: <bu7p2ug35r28icn0g...@4ax.com>
>am 28.12. für den Fall n=6k+1 bewiesen.
Der Fall 6k+5 ist von Philipp erstmals in
Message-ID: <q8bu2ukne1ad9b6fp...@4ax.com>
komplett bewiesen.
Der Fall 6k+3 wurde gerade von mir in
Message-ID: <rd1v2usa1daga97lb...@4ax.com>
bewiesen. Eine Überprüfung durch Philipp steht noch aus.
(Der muß noch ein Bug drin sein, die Einschränkung k>=3
habe ich gar nicht gebraucht!)
Wenn die Restarbeiten durch sind und das ganze sauber
aufgeschrieben wurde (wer macht das?), kann es noch
beliebig weitergehen.
Zum einen gibt es neben G(n), dem Minimum der maximalen
Dreiersumme, ja noch ein H(n), dem Maximum der minimalen
Dreiersumme. Aus Symmetriegründen (ersetze p(i) durch
n+1-p(i)) gibt es hier nichts mehr zu tun. Außer, das es
sich um eine zweite Folge für Rainer handelt, nämlich
H(n) = floor(n*3/2) und denselben Ausnahmen wie bei G(n).
Insbesondere gilt für den Durchschnittswert D(n) der Dreiersummen
G(n)-D(n) = D(n)-H(n).
Wenn p eine Permutation ist, die G(n) erfüllt, ist p' mit
p'(i) = n+1-p(i) eine Permutation die H(n) erfüllt.
Ich nenne eine Permutation p, die gleichzeitig beides
erfüllt, mal für dieses eine Posting provisorisch "schöne
Permutation".
Zunächst einmal ist aber nicht klar, ob es überhaupt
"schöne" Permutationen gibt. Da habe ich aber schon
vorgearbeitet; die Antwort lautet ja; meine Bauvorschriften
habe ich so gewählt, daß gleich diese Permutationen erzeugt
werden.
Aber spannend kann es noch werden, die Anzahl s(n) der "schönen"
Permutationen zu bestimmen. Das dürfte Kombinatorik vom feinsten
sein, und wieder eine schöne Folge für Rainers Sammlung ergeben.
In einem anderen Posting hatte ich schon ein paar Werte von s(n)
gepostet: Message-ID: <aqos2u4897piotcge...@4ax.com>
n s(n)/n
Gruß,
Kurt.
Kurt Stege
"Rainer Rosenthal" <r.ros...@web.de> wrote:
>kann man bei Euch noch irgendwie mitspielen ?
Aber klar. Siehe auch mein anderes Posting von jetzt:
Message-ID: <h0bv2ucgrnsltlmod...@4ax.com>
>Welche Baupläne sind denn nach Euer beider Meinung
>inzwischen definitiv abgehakt und an welchen seid Ihr
>jetzt noch am Basteln ?
Die Baupläne sind aus meiner Sicht fertig. Ich habe
für alle n Baupläne angegeben. Was noch fehlt, ist ein
mathematischer Beweis, daß diese Baupläne tatsächlich
zu Permutationen führen, deren Dreiersummen sämtlichst
in den behaupteten Schranken liegen (und daß es sich
überhaupt um Permutationen handelt).
Auch Philipp hat sich, wenn ich ihn richtig verstanden
habe, zunächst mit der Existenz dieser Baupläne ohne
vollständigen mathematischen Beweis abgefunden. Sie
"sehen einfach so aus", als ob sie das Behauptete auch
erfüllen.
Mit den Beweisen für die Baupläne wäre die obere
Schranke von G(n) gesichert.
Am Basteln sind wir an der unteren Schranke von G(n).
>Irgendwie hatte ich mitgekriegt, dass Ihr den Fall n=11
>nochmal gründlich untersucht. Das ist doch was Handliches
>zum Mitdenken ...
>Andererseits scheint 6*k+5 jetzt komplett abgehakt.
Die untere Schranke hat Philipp abgeliefert.
>Wo finde ich den Bauplan ?
Der Bauplan für die obere Schranke steht im selben
Posting von mir wie alle anderen Baupläne auch.
Message-IDs sind in der Übersichts-Liste
Message-ID: <h0bv2ucgrnsltlmod...@4ax.com>
>Falls ich jetzt ungelegen komme, dann bitte - nicht stören
>lassen.
Manchmal ist es ganz gut, einen Moderator zu haben, der
die Arbeit etwas kanalisieren kann.
>Es ist gut, dass die gnadenlose Wühlarbeit so
>öffentlich durchgeführt wird - man kann dann im Einzelfall
>doch noch mal auf die Begründungen und pfiffigen Einzel-
>Einfälle zurückgreifen (wie z.B. den oben zitierten).
Zumindest macht es Spaß. Dies ist mathematische Arbeit,
wie ich sie mir idealerweise vorstelle. Wieso nur bin
ich nach dem Mathe-Studium bloß Programmierer geworden...
>Erst waren wir bei Analysen, bei denen der Rest von n mod 3
>interessant war, dann kamen die Superdurchbrüche bei mod 6.
>Aber zwischendrin habt Ihr das sogar bis mod 18 verfeinert.
>Ist das noch amtlich ? Oder wie sieht der aktuelle "Fahrplan" aus ?
Steht alles in meinem Übersichts-Posting. Mod 18 war eine
Befürchtung von mir, die sich, wie es aussieht, als nicht
notwendig erwiesen hat.
>Bestimmt werdet Ihr mir das nicht übelnehmen, wenn ich mit
>Übersichts-Zwischenfragen "nerve". Es gibt doch auch die
>Gelegenheit, dass Ihr selbst Euch nochmal - nachvollziehbar für
>alle Mitleser (ich tippe mal auf mindestens 7 (?)) - abstimmt
>über den Gesamterfolg bisher und über die anzugehenden Ziele.
Doch soviel? Ich schätzte eher zwei Arbeiter und ein "Moderator".
Insbesondere machen Philipp und ich soviele Fehler, die wir
alle selber aufdeckem müssen. Wenn es noch mehr Mitleser
gibt: Traut euch, euch zu melden, und sei es nur, uns unsere
Fehler aufzudecken.
>Ein wenig ziele ich dabei auch schon auf den zu schreibenden
>NJAS-Beitrag, in dem ja diese Bauplan-Arbeit übersichtlich
>darzustellen ist.
Wieviele Folgen möchtest Du noch kriegen? Im Übersichts-Posting
habe ich auch einen kleinen Ausblick auf weitere Folgen angedeutet.
>Mit weiter aufmunternden Grüssen,
>Rainer Rosenthal
Vielen Dank,
Kurt.
Ralf Muschall
> Hallo Kurt,
ich heiße zwar anders, aber melde mich auch mal ...
> kann man bei Euch noch irgendwie mitspielen ?
Man könnte z.B. die Konstante 3 durch etwas anderes ersetzen.
Die Fälle 0 und 1 übernehme ich schon mal :-)
Ralf
--
GS d->? s:++>+++ a C++++ UL+++ UH++ P++ L++ E+++ W- N++ o-- K- w--- !O M- V-
PS+>++ PE Y+>++ PGP+ !t !5 !X !R !tv b+++ DI+++ D? G+ e++++ h+ r? y?
Kurt Stege
Kurt Stege <kurt-...@online.de> wrote:
>Heute mal wieder die one-based Schreibweise.
>Gezeigt werden soll G(6k+3) > 9k+7 für k>=3.
...
>Jede Dreiergruppe hat ja höchstens 9k+7 als Summe.
^^^^^^^^^
>Die Einzelzahlen waren von 1 bis 2k+1 (eventuell ist
>eine der Zahlen durch 2k+2 ausgetauscht).
>Die 2k+1 hat zwei benachbarte Zweiergruppen, die zusammen
>mit 2k+1 höchstens 9k+7 groß sind, also einzeln höchstens
>7k+6. Die Einzelzahl 2k+0 mag eine dieser beiden als
>Nachbar haben, hat aber noch einen zweite Zweiergruppe
>als Nachbar, deren Summe höchstens 7k+7 ist.
>Alle weiteren Zweiergruppen lassen sich durch 7k+8, 7k+9, ...
>abschätzen.
>
>Die Summe aller 2k+1 Zweiergruppen beträgt also mindestens
^^^^^^^^^^
Nein. Höchstens.
>lol :-)
col :-(
Gruß,
Kurt.
Kurt Stege
>"Rainer Rosenthal" <r.ros...@web.de> writes:
>
>> Hallo Kurt,
>
>ich heiße zwar anders, aber melde mich auch mal ...
>
>> kann man bei Euch noch irgendwie mitspielen ?
>
>Man könnte z.B. die Konstante 3 durch etwas anderes ersetzen.
Gute Idee.
Naheliegende Vermutung, auch wenn ich nicht dran glaube:
für m statt 3 ist G(n,m) = n*m/2 + const.
Ihr kennt doch sicherlich alle die Dartscheiben mit ihren
20 Feldern (n=20). Sind diese Permutationen nach diesen
Zahlenkreisen optimiert? Für m=3, für m=5 oder gar beides?
>Die Fälle 0 und 1 übernehme ich schon mal :-)
Einverstanden. Dann übernehme ich die Fälle 2...m.
Kurt.
Rainer Rosenthal
Kurt Stege <kurt-...@online.de>
>
> Zumindest macht es Spaß. Dies ist mathematische Arbeit,
> wie ich sie mir idealerweise vorstelle. Wieso nur bin
> ich nach dem Mathe-Studium bloß Programmierer geworden...
>
SCNR - spontane Reaktion - aber nur mit Pssssst!!! per mail.
Denn ich bin selbst ein solcher (aber nur mit einem Zehntel Herzen).
Ich würde mal sagen:
Als Programmierer kriegt man für den grössten Mist noch Geld.
Unter Umständen kriegt man schon Geld dafür, dass man den
Mist von anderen Leuten umgraben muss - und ist trotzdem fein
heraus, weil man für alles eine Ausrede hat.
Aber als Mathematiker kriegste für die schweisstreibendsten
und hirnverrenkendsten Arbeiten nur ein höhnisches Lachen.
Denn schliesslich sieht "hinterher" alles so sauber und klar aus,
dass "es eigentlich trivial" ist. Wieso soll man also einem Deppen,
der sich so reinsteigert, auch noch Geld zahlen - sagen sich die,
die Geld zu verteilen haben.
Zynisch ? Na ja - ein wenig.
Mir fällt da übrigens ein verräterischer Satz ein, den Du selbst gebraucht
hattest. warte mal ... such ... such wühl ... äh, wo war denn ... Ach ja:
Ich zitiere aus einem Posting von gestern:
Was noch fehlt, aber bereits in diesem Thread in Arbeit ist,
ist die untere Abschätzung für die minimale größte Dreiersumme
für ungerade n. Wenn diese Arbeiten durch sind, und die Ergebnisse
dieses Threads nachgerechnet wurden, ist die gesuchte Funktion
f(n) gut bekannt, und nicht mehr sonderlich aufregend.
Das ist typisch für "uns". Machen unsere eigene Arbeit "klein". Das
freut Leute, die Geld zu verteilen haben. Ich weiss ja nicht, in was
für einem Laden Du Dein Geld verdienst. Aber ich arbeite in einem
ziemlich kleinen Ing-Büro mit jetzt bloss noch 12 Leuten - vor wenigen
Jahren waren wir noch 19, bei etwa gleicher Arbeit. Was da zusammen-
geschustert wird, das geht auf keine Kuhhaut :-(
Aber wie gesagt: Psssssst !
Und bitte nie wieder: Ach das war ja gar nichts, volltrivial usw.
Denn: Was soll das ? Man hat sich eins abgestrampelt und es gibt einen
Haufen Leute, die das nie auf die Reihe bringen würden (z.B. der Chef).
Also sollte man doch stolz sein auf die geleistete Arbeit.
Gruss, Rainer
Jetzt lese ich weiter im Thread ....
Rainer Rosenthal
Kurt Stege <kurt-...@online.de>
>
>
> Wenn die Restarbeiten durch sind und das ganze sauber
> aufgeschrieben wurde (wer macht das?),
na ich ... wenn ich es kapiert habe :-) So soll es doch ins NJAS-
Archiv.
> kann es noch
> beliebig weitergehen.
>
> Zum einen gibt es neben G(n), dem Minimum der maximalen
> Dreiersumme, ja noch ein H(n), dem Maximum der minimalen
> Dreiersumme. Aus Symmetriegründen (ersetze p(i) durch
> n+1-p(i)) gibt es hier nichts mehr zu tun. Außer, das es
> sich um eine zweite Folge für Rainer handelt, nämlich
> H(n) = floor(n*3/2) und denselben Ausnahmen wie bei G(n).
> Insbesondere gilt für den Durchschnittswert D(n) der Dreiersummen
> G(n)-D(n) = D(n)-H(n).
>
> Wenn p eine Permutation ist, die G(n) erfüllt, ist p' mit
> p'(i) = n+1-p(i) eine Permutation die H(n) erfüllt.
>
> Ich nenne eine Permutation p, die gleichzeitig beides
> erfüllt, mal für dieses eine Posting provisorisch "schöne
> Permutation".
Der oben erwähnte Rainer - identisch mit dem Poster dieses
Beitrags - hatte am 24. Dezember in de.rec.denksport im Thread
"Lichterkette mit 50 Lichtern" folgendes geschrieben:
#Leser von de.sci.mathematik dürften da etwas wiedererkennen.
#So wie ich die Aufgabe hier formuliert habe, ergibt sich dabei
#ein in d.s.m. noch nicht erwähnter Aspekt: Statt sich eine möglichst
#kleine maximale Leuchtstärke in den Dreiergruppen zu wünschen,
#also allzu helle zu vermeiden, kann man ja umgekehrt auch fragen
#nach einer Bestückung mit möglichst nicht zu dunklen Stellen.
#Oder - was der Suche nach "Gleichmässigkeit" am meisten ent-
#sprechen sollte: Suche nach Bestückung mit minimalem Abstand
#zwischen den Leuchtstärken der hellsten und der dunkelsten
#Dreiergruppe.
#Aber ... wünschen kann man sich ja viel :-)
Schön, dass diese Suche jetzt auch schon möglich wird. Was bisher
zutage gefördert wurde, ist schon eine grosse Weihnachtsüberraschung.
>
> Aber spannend kann es noch werden, die Anzahl s(n) der "schönen"
> Permutationen zu bestimmen. Das dürfte Kombinatorik vom feinsten
> sein, und wieder eine schöne Folge für Rainers Sammlung ergeben.
Ach nee, ich glaube nicht - sorry. Ist mir irgendwie zu abgehoben.
Mich würde es weit mehr interessieren, wo hinter all der Mordsarbeit
der tiefere Zusammenhang ist.
By the way: Wo ist eigentlich BAU(6k+0) abgehandelt ?
*** das habe ich im Thread gefunden (Philipp am 29.12.) ***
>Fall n = 6*k + 0. (für k>= 1)
> snip
Dies ist mir wohl doch ein Bisschen zu heuristisch bzw. es ist mir
einfach etwas zu kompliziert.
>Mit diesen drei Bauvorschriften, die zusammen n=3k+0 abdecken,
>wäre der Fall n = 6*k + 0. (für k>= 1) auch erledigt.
Ja, falls du begründen kannst das deine "Bauvorschrift" funktioniert
in der gewünschen Weise.
*** Ende der Fundstelle ***
Hier mal der Versuch einer eigenen Formulierung der von Dir
erfundenen Bauvorschrift für den Fall 6*k + 2:
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
# BAU(6k+2):
# p(6i) = 3i+1 für 0 <= i <= floor(n/3)
# p(6i+3) = 3i+2 für 0 <= i <= floor(n/3)
# p(-3i-3) = 3i+3 für 0 <= i < floor(n/3) [ echt kleiner! ]
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
Beispiel: n = 14 = 6*2 + 2. floor(n/3) = 4
p(6i): 0:1 6:4 12:7 18:10 24:13
p(6i+3): 3:2 9:5 15:8 21:11 27:14
p(3i-3): -3:3 -6:6 -9:9 -12:12
Plätze 0,6,12,18,24,3,9,15,21,27,-3,-6,-9,-12 in der verständ-
licheren Form als Reste mod n, d.h. mod 14 geschrieben, d.h. als
0,6,12,4,10,3,9,1,7,13,11,8,5,2 - gibt die Bauvorschrift also vor:
p(6i): 0:1 6:4 12:7 4:10 10:13
p(6i+3): 3:2 9:5 1:8 7:11 13:14
p(3i-3): 11:3 8:6 5:9 2:12
Oder vollends übersichtlich:
p = (01 08 12 02 10 09 04 11 06 05 13 03 07 14)
mit den Dreiersummen d(i) = p(i-1)+p(i)+p(i+1) wie folgt:
d = (23 21 22 24 21 23 24 21 22 24 21 23 24 22)
Interessant an BAU(6k+2) ist zum einen die witzige Aufteilung
der Plätze in (um beim Beispiel n=14 zu bleiben) 5+5+4, die
in einer auf Anhieb gar nicht ersichtlichen Weise alle Reste
modulo n abdeckt.
Und zum anderen natürlich die wesentliche Eigenschaft, dass
die Dreiersummen d(i) nicht zu sehr voneinander abweichen.
Und das ist noch viel weniger offensichtlich, wenn es auch
sicher wahr ist. Einige Versuche zum Nachrechnen sind bisher
nicht wirklich zur Veröffentlichung geeignet :-) Habe den Ein-
druck, dass es da "was Eleganteres" geben müsste. Immerhin
habe ich hiermit einen Beitrag zur Formalisierung gebracht, der
zumindest nicht falsch ist. Und in Ermangelung einer zündenden
Idee werde ich wohl weiter einen Fuss vor den anderen setzen
und doch aus BAU(6k+2) herzuleiten versuchen, dass die d(i)
sich in den engen Grenzen bewegen.
Freundliche Grüsse
Rainer Rosenthal
r.ros...@web.de
-
P.S. Ich rate davon ab, die "Betreff"-Zeile abzuwandeln. Mir schien
das früher auch pfiffig. Aber wenn man sowas in groups.google.com
wieder lesen will, dann ist alles zerfleddert, der Thread als solcher
nicht mehr zusammenhängend. Darum bin ich auf "Zahlenkreis"
zurück gegangen.
Philipp Zumstein
wrote:
>Die Fälle für 6k+1 (hier) und für 6k+5 und erst recht für 2k
>sind mittlerweile abgehakt.
Sehe ich auch so, vielleicht noch nicht ganz sauber ausformuliert,
aber sonst fertig.
>Ich versuche mich jetzt mal wieder an dem wahrscheinlich
>schwierigsten Fall, n = 6k+3.
> sinpped
Diesen Fall habe ich gestern auch noch probiert, aber erfolglos. Jetzt
werde ich mir mal dieses Posting hier von dir ausdrucken und "zu
Gemüte führen". Bin schon gespannt.
Melde mich dann wieder.
Gruss
Philipp
Philipp Zumstein
Das habe ich ja vorhin noch gar nicht gelesen.
On Mon, 31 Dec 2001 03:35:59 +0100, Kurt Stege <kurt-...@online.de>
wrote:
>Diesen Beweis muß ich leider wieder vollständig zurückziehen.
Nun ja, der Beweis ist ja nicht vollständiger "Bullshit". Sondern
"nur" der Widerspruch funktioniert nicht auf deine Weise.
>Kurt Stege <kurt-...@online.de> wrote:
>>Die Summe aller 2k+1 Zweiergruppen beträgt also mindestens
> ^^^^^^^^^^
>Nein. Höchstens.
Ja, leider.
Gruss
Philipp
Philipp Zumstein
Um es gleich vorne-weg-zunehmen, dein Beweis ist noch unvollständig.
Sorry. Aber ich habe ihn auch noch nicht hingekriegt, die Ansätze
deines Beweises finde ich aber genial.
On Mon, 31 Dec 2001 01:01:11 +0100, Kurt Stege <kurt-...@online.de>
wrote:
>Ich versuche mich jetzt mal wieder an dem wahrscheinlich
>schwierigsten Fall, n = 6k+3.
>
>Heute mal wieder die one-based Schreibweise.
>Gezeigt werden soll G(6k+3) > 9k+7 für k>=3.
Das Problem bei deinem Beweis ist doch auch irgendwie, dass du gar nie
k>=3 gebraucht hast...
So konnte ich mit deiner Argumentation auch zeigen, dass G(9) > 16
ist. Aber es gilt ja G(9) = 16.
> snipped
>
>Beweis:
>
>Annahme, dies sei nicht der Fall. Dann gibt es ein Polynom p,
>bei dem alle Dreiersummen <= 9k+7 sind.
Du meinst wohl eine Permutation? Nicht ein Polynom? Oder verstehe ich
unter einen Polynom nicht dasgleich wie du? Du hast nämlich mehre Male
Polynom verwendet, wo ich in Gedanken einfach Permutation gelesen
habe.
Stimmt alles noch.
>(Da jede Zweiergruppe als Summe mindestens 7k+5 ist, ist
>die Summer aller Zweiergruppen mindestens (7k+1)*(2k+1) =
>14k^2 + 17k + 5. Dies paßt noch.)
>
>Jede Dreiergruppe hat ja höchstens 9k+7 als Summe.
>Die Einzelzahlen waren von 1 bis 2k+1 (eventuell ist
>eine der Zahlen durch 2k+2 ausgetauscht).
>Die 2k+1 hat zwei benachbarte Zweiergruppen, die zusammen
>mit 2k+1 höchstens 9k+7 groß sind, also einzeln höchstens
>7k+6. Die Einzelzahl 2k+0 mag eine dieser beiden als
>Nachbar haben, hat aber noch einen zweite Zweiergruppe
>als Nachbar, deren Summe höchstens 7k+7 ist.
>Alle weiteren Zweiergruppen lassen sich durch 7k+8, 7k+9, ...
>abschätzen.
Achtung...
>Die Summe aller 2k+1 Zweiergruppen beträgt also mindestens
... hier muss ein "höchsten" stehen. Du hast ja im vorherigen
Abschnitt die einzelnen 2er Summen nach oben abgeschätzt. Damit geht
dein Widerspruch kaputt.
>7k+6 + 7k+6 + 7k+7 + 7k+8 + 7k+9 + ... + 9k+4 + 9k+5 =: S2.
>Das ist (2k+1)*(7k+5 + 9k+5)/2 + 1 = 16k^2 + 18k + 6.
>
>Wir wissen aber schon: Die 4k+1 großen Zahlen haben eine
>Summe von genau S1 = 16k^2 + 16k + 3. Die letzte Zahl ist
>höchstens 2k+2, also kann die Summe aller Zahlen nur
>höchstens 16k^2 + 18k + 5 betragen. Und das ist weniger
>als S2.
Ich habe dir hier in der folgenden Anmerkung noch ein paar Zahlen
korrigiert: 9k->6k, 3k->2k:
>Anmerkung [1]:
>
>Bekannt ist, das
>d := 9k+6 der Durchschnitt aller Dreisersummen ist und
>s_ges := 18k^2 + 21k + 6 die Summe aller n Zahlen ist.
>
>Der Beweis funktioniert grob so, daß von den 6k+3 Zahlen
>drei ausgesucht werden, mit zwei Eigenschaften:
>a) Die Summe der drei Zahlen ist kleiner als 7k+6
>b) Die restlichen 6k Zahlen bilden 2k disjunkte Dreiersummen.
>
>Über diese 2k Dreiersummen sind zwei Aussagen gültig:
> snipped
Ich versuche weiterhin noch den Beweis zu retten.
Gruss
Philipp