Hallo,
ich habe mir gestern das Raetsel
http://www.wer-weiss-was.de/cgi-bin/forum/showarchiv…
noch mal angeschaut und inbesondere die Frage, ob das Lsg. Schema, das im Rahmen der Diskussion dort angegeben wurde
http://www.wer-weiss-was.de/cgi-bin/forum/showarchiv…
eindeutig ist. Nochmal zur Aufgabenstellung. Gegeben sei eine Zahlenfolge (xk)0 mit xk=#{i|xi=k, 0=7 und xk0, x1, …, xn gibt die Anzahl der Nullen, Einsen bzw. n-nen in der Folge wieder. Man macht sich leicht klar, dass die Summe aller Folgeglieder, der Laenge der Folge (n+1) gleich ist, also
(1) sum0 xk=n+1.
Fuer n=7, also eine Folge der Laenge 8 heisst das x0+x1+ … + x7=8.
Die letzten vier Folgeglieder sind nie groesser als 1
(2) xk=n-3
denn sei xk=a. Dann gilt ak0 xk=n+1, also a=7, / ganzzahlige Division).
Die Anzahl der Nullen in der Folge x0 ergibt sich als n-3 (fuer n=7 also 4 Nullen).
(3) x0=n-3
Wir nehmen x0n-3 an und fuehren das zum Widerspruch.
Sei x0>n-3. Wir unterscheiden die drei Faelle x0=n,n-1,n-2. Aus x0=n folgt mit 2 xn=1, woraus der Widerspruch x00=n-1 folgt mit 2 xn-1=1, daraus x1>0 und damit der Widerspruch x00=n-2 folgt aus 2 xn-2=1 daraus wieder x1>0 und damit x1>1 (x1=1 wuerde mit xn-2=1 zum Widerspruch fuehren). Falls x1n-2 wuerde x00,x1 und xn-20. Aber aus x1=n-2 folgt n+1=sum0 x_k>=(n-2)+(n-2)+1=2n-3 was n=7.
Der Fall x0=n-2 laesst sich auch ohne Verwendung von 2 wie folgt beweisen. Aus x0=n-2 folgt xn-2>0. Waere xn-2>2 und xn-2n-2, waere es nicht moeglich die n-2 Nullen auf die verbleibenden n-3 Folgeglieder zu verteilen. Der Fall xn-2=n-2 scheitert an 1 ((n-2)2>n+1 fuer n>=5). Falls xn-2=2 ist x2>0, was man analog zum Widerspruch fuehrt. Also gilt xn-2=1, womit die urspruengliche Argumentation wieder verwendet werden kann.
Sei nun x0=m0=m und xm>=1. Fuer die restlichen n-1-m von null verschiedenen Folgeglieder kommt jedes xi mit i0,m in Betracht. Ein xi>0 erzwingt aber das Vorhandensein mind. eines i in der Zahlenfolge. Mit dieser Ueberlegung ist die Summe dieser n-1-m Folgeglieder mind. so gross wie 1+2+…+(n-m-1)=((n-m-1)2+n-m-1)/2=(m2+m*(1-2*n)+n2-n)/2.
Insgesamt folgt fuer die Summe aller Folgeglieder sum0 xk>=m+1+(m2+m*(1-2n)+n2-n)/2. Wir untersuchen jetzt fuer welche m m+1+(m2+m(1-2n)+n2-n)/22+m(3-2n)+n2-3n1=2
denn aus 2+3 folgt x1>0. x1=1 wuerde mit xn-3=1 zum Widerspruch fuehren (es gebe mehr als zwei Einsen in der Folge, was x1=1 widerspricht). Also gilt x1>1. Waere x1>2, dann wuerde es mind. noch zwei Positionen j,k>1,n-3 mit xj=xk=1 geben. Das haette x02=1
denn aus 4 folgt x2>0. Wenn x2>1 gibt es noch eine Position k0,1,2,n-3 mit xk=2. Dann waere aber x_00=n-3, x1=2, x2=1, xn-3=1 und xk=0 fuer k0,1,2,n-3. Fuer n=7 ist dies z.B. genau (4,2,1,0,1,0,0,0).
Berachten wir jetzt die analoge Aufgabenstellung fuer n4,x50=n-3=2 und x2>0. Das zum Widerspruch zu fuehren ueberlasse ich jeden selbst. Geht analog zu obigen Ueberlegungen.
Gruss
Enno