Nettes Rätsel

Freizeit & Hobby Rätsel
#1

… in einen anderen Forum gefunden.

  1. Gibt es eine 20-stellige Zahl, in der jede der zehn Ziffern genau zweimal vorkommt, so daß die beiden Nullen nebeneinander stehen, zwischen den beiden Einsen genau eine Ziffer steht, zwischen den Zweiern genau zwei Ziffern … und zwischen den Neuern genau neun Ziffern stehen ?

  2. Wie sieht es für eine 16-stellige Zahl gebildet aus den Ziffern 0,1,…,7 aus ?

  3. Betrachten wir ein Alphabet mit n Ziffern und eine daraus gebildete 2n-stellige Zahl. Gibt es bei analoger Verteilung der Ziffern immer eine Lsg. resp. überhaupt eine Lsg. und wie wie hängt die Lösbarkeit von n ab ?

Gruss
Enno

PS: Wer das Rätsel oder das zugehörige math. Problem schon kennt möge schweigen :wink:

#2

Ergänzend …

  1. Betrachten wir ein Alphabet mit n Ziffern und eine daraus
    gebildete 2n-stellige Zahl.

… hier sollen die „Ziffern“ 0,1,2,…,n-1 betrachtet werden.

Gruss
Enno

#3

Anfangsverdacht
Hallo,

meine noch unbewiesene (durch Probieren gefundene) These lautet:

Eine Loesung existiert genau dann, wenn n mod 4 in {0,1}.
D.h. eine Loesung existiert, wenn n bei Division durch 4 den Rest 0 oder 1 hat, wenn der Rest 2 oder 3 ist, gibt es keine Loesung.

Fuer n=10 gibt es somit keine Loesung, wohl aber fuer n=8.

Ich bin noch auf der Suche nach einem Beweis.

Viele Gruesse
Jens

#4

Hallo,
die These ist schonmal richtig. Ausreichend wäre schon der Beweis der Notwendigkeit dieser Bedingung, also nur wenn diese Bedingung gilt, kann es überhaupt eine Lsg. geben. Betrachte einfach mal die Positionen an denen z.B. die erste 0 und die zweite stehen, die erste 1 und die zweite 1 etc. Damit läßt sich etwas anfangen.

Gruss
Enno

#5

Zwischenstand
Hallo,

ich habe noch keinen vollständigen Beweis, bin aber ein Stück weiter.
Ich kann zeigen, dass für alle Lösungen bei festem n die Summe der Anfangspositionen der Ziffern konstant ist.
Desweiteren habe ich eine Vermutung, wie diese Summe von n abhängt: Nummeriert man die Positionen der Zahlen in der 2*n-stelligen Zahlennfolge (Zahlen 0…n) von 1 beginnend bis 2*n durch, so lautet diese Summe

S(n) = 3*n^2/4 + n/4 = n*(3*n+1)/4.

Da diese Summe ganzzahlig sein muss, folgt hieraus die notwendige Bedingung, dass n durch 4 teilbar sein oder bei Division durch 4 den Rest 1 lassen muss.

Leider konnte ich bisher noch nicht beweisen, dass obige Summe stimmt (empirisch geprüft für endlich viele n).

Gruß
jens

#6

Beweis!
Hallo nochmal,

Kurz vorm Einschlafen traf mich der Geistesblitz, hier nun der komplette Beweis:

Die Gesamtsumme A aller Positionen in der Zahlenfolge (nummeriert von 1 bis 2*n) ist gegeben durch

S(n) = sum(k, k=1…2*n) = (2*n)*(2*n+1)/2 (Beweis durch vollständige Induktion).

Die Summe A aller Anfangspositionen der Zahlen in der Folge sei A(n) und die Summe aller Endpositionen in der Folge bezeichne ich mit E(n). Es gilt dann

S(n) = A(n) + E(n).

Die Differenz D(n) der Anfangsposition und der Endposition einer bestimmten Zahl z (z aus {0,…,n-1}) beträgt nach Voraussetzung z+1. Damit lässt sich die Differenz E(n)-A(n) wie folgt berechnen:

D(n) = E(n) - A(n) = sum(z+1, z=0…n-1) = n*(n+1)/2.

Insgesamt gilt also

E(n) + A(n) = S(n) = (2*n)*(2*n+1)/2 und
E(n) - A(n) = D(n) = n*(n+1)/2.

Addieren und Subtrahieren dieser Gleichungen liefert

A(n) = n*(3*n+1)/4 und
E(n) = n*(5*n+3)/4.

A(n) und B(n) müssen ganzzahlig sein, woraus folgt, dass (n mod 4) aus {0, 1} sein muss.

Ob diese Bedingung auch hinreichend ist, konnte ich noch nicht beweisen. Für n

1 Like
#7

Hallo,
bestens. Ist genau der Ansatz, den ich auch hatte. Das Problem ist als „Langford“ Problem in geringfügig anderer Art (i.allg. fehlt die 0) in der Literatur bekannt. Beim Beweis das dieses Kriterium hinreichend ist, habe ich mich selbst verhaspelt. Der Literatur zufolge ist es aber so.

Gruss
Enno