Abbildung/Knöpfe und Löcher am Hemd/Aufgabe

Mathematiker haben, so ein weitverbreitetes Vorurteil, Schwierigkeiten, ihre Hemden korrekt zuzuknöpfen. Ein Hemd hat auf der einen Seite eine von oben nach unten geordnete Knopfreihe bestehend aus ${}n$ Knöpfen und auf der anderen Seite eine ebenso geordnete Lochreihe aus ${}n$ Löchern. Beide Reihen seien von oben nach unten mit ${}1$ bis ${}n$ durchnummeriert. Eine Zuknöpfung ${}\sigma$ ordnet jedem Knopf genau ein Loch zu, sie ist also eine Abbildung

$\sigma \colon {\{1,\ldots ,n\}}\longrightarrow {\{1,\ldots ,n\}},\,i\longmapsto \sigma (i),$

wobei die identische Abbildung ${}i\mapsto i$ als korrekte (oder triviale) Zuknöpfung gilt. Der Zerstreutheitsindex ${}Z(\sigma )$ ist ein wichtiges numerisches Maß für die Zerstreutheit (oder Kreativität) einer Zuknöpfung ${}\sigma$. Er ist definiert über die Abbildung

$Z\colon A_{n}=\operatorname {Abb} \,{\left({\{1,\ldots ,n\}},{\{1,\ldots ,n\}}\right)}\longrightarrow \mathbb {N} ,\,\sigma \longmapsto Z(\sigma )=\sum _{i=1}^{n}\vert {i-\sigma (i)}\vert .$

1. Zeige: Eine Zuknöpfung ${}\sigma$ ist genau dann korrekt, wenn ${}Z(\sigma )=0$ ist.
2. Kann eine Zuknöpfung den Zerstreutheitsindex ${}1$ haben? Wie sieht es bei bijektiven Zuknöpfungen aus?
3. Bestimme

   $a_{n}=\max {\left\{Z(\sigma )\mid {\sigma \in A_{n}}\right\}}$

   in Abhängigkeit von ${}n\in \mathbb {N}$.

4. Es sei ${}B_{n}\subseteq A_{n}$ die Menge aller bijektiven Zuknöpfungen. Bestimme

   $b_{n}=\max {\left\{Z(\sigma )\mid {\sigma \in B_{n}}\right\}}$

   für ${}n=0,1,2,3,4,5$.

5. Es sei ${}C_{n}\subseteq A_{n}$ die Menge aller konstanten Zuknöpfungen. Bestimme

   $c_{n}=\max {\left\{Z(\sigma )\mid {\sigma \in C_{n}}\right\}}$

   in Abhängigkeit von ${}n\in \mathbb {N}$.

6. Eine Zuknöpfung ${}\sigma$ heißt semikorrekt, wenn ${}Z(\sigma )\leq n$ ist. Klassifiziere alle semikorrekten Zuknöpfungen bei ${}n\leq 3$.

Eine Lösung erstellen