Projekt:Mathe-Werkstatt/Ene-Mene-Muh-Problem

Das Ene-Mene-Muh-Problem

Problem gestellt von Christine Bescherer und Christian Spannagel --Cspannagel 23:42, 28. Nov. 2008 (CET)

Kontext

Jeder kennt das altbekannte Ene-Mene-Muh-Spiel: Personen einer Gruppe stellen sich im Kreis auf und beginnen durchzuzählen: "Ene Mene Muh und raus bist du". Diese Person muss den Kreis verlassen, und es wird ab der nächsten Person von neuem gezählt. Es wird so lange abgezählt, bis nur noch eine Person (der "Gewinner") übrig bleibt.

Problemstellung

Ene-Mene-Muh-Problem: Wo muss man sich beim Ene-Mene-Muh-Spiel hinstellen, wenn man selbst als Gewinner übrig bleiben möchte?

Verallgemeinertes Ene-Mene-Muh-Problem:

Gegeben sei eine zyklische Sequenz von n Elementen $1,2,3,\ldots ,n$. Es wird mit einer m-Abzählfolge abgezählt (d.h. jedes m-te Element fällt heraus). Welches Element ist der Gewinner, wenn bei Element 1 mit dem Zählen begonnen wird?

Überlegungen

• Jede m-te Person muss die Gruppe verlassen.
• Die Anzahl der Personen in der Gruppe nimmt pro Zählvorgang um 1 ab.

Lösungsideen und Ansätze

Beispiel mit 6 Personen:

1 2 3 4 5 6

Annahmen:

• Abzählen immer in der gleichen Richtung
• Abzählen in aufsteigender Richtung der Nummerierung

1. Abzählen:

Die Person mit der Nummer $7{\bmod {6}}=1$ fällt heraus. (Der Abzählreim hat 7 Wörter und es gibt 6 Personen.)

1 2 3 4 5 6

Nun werden die Nummern neu verteilt: Person 2 bekommt Nummer 1, Person 3 Nummer 2, ...

$2\rightarrow 1$

$3\rightarrow 2$

$4\rightarrow 3$

$5\rightarrow 4$

$6\rightarrow 5$

$n_{1}\rightarrow n_{2}=(n_{1}-7{\bmod {6}}){\bmod {6}}$

($7{\bmod {6}}$ ist die Nummer, die heraus fällt, und ${\bmod {6}}$ danach ergibt sich aus 5 Plätzen.)

2. Abzählen:

Die Person mit der Nummer $7{\bmod {5}}=2$ fällt heraus.

1 2 3 4 5

Nun werden die Nummern neu verteilt: Person 3 bekommt Nummer 1, Person 4 Nummer 2, ...

$3\rightarrow 1$

$4\rightarrow 2$

$5\rightarrow 3$

$1\rightarrow 4$

$n_{2}\rightarrow n_{3}=(n_{2}-7{\bmod {5}}){\bmod {5}}$

3. Abzählen:

Die Person mit der Nummer $7{\bmod {4}}=3$ fällt heraus.

1 2 3 4

Nun werden die Nummern neu verteilt: Person 4 bekommt Nummer 1, Person 1 Nummer 2, ...

$4\rightarrow 1$

$1\rightarrow 2$

$2\rightarrow 3$

$n_{3}\rightarrow n_{4}=(n_{3}-7{\bmod {4}}){\bmod {4}}$

4. Abzählen:

Die Person mit der Nummer $7{\bmod {3}}=1$ fällt heraus.

1 2 3

Nun werden die Nummern neu verteilt: Person 2 bekommt Nummer 1, Person 3 Nummer 2, ...

$2\rightarrow 1$

$3\rightarrow 2$

$n_{4}\rightarrow n_{5}=(n_{4}-7{\bmod {3}}){\bmod {3}}$

5. Abzählen:

Die Person mit der Nummer $7{\bmod {2}}=1$ fällt heraus.

1 2

Nun werden die Nummern neu verteilt: Person 2 bekommt Nummer 1.

$2\rightarrow 1$

$n_{5}\rightarrow n_{6}=(n_{5}-7{\bmod {2}}){\bmod {2}}$

• Siehe auch Josephus-Problem

Rekursive Lösung

Im Kreis mit n Personen nehme ich die Position ab der 7. Stelle ein, die mich bei dem (n-1) Kreis zum Sieger macht.

Um einfach mit Modulo zu rechnen, zähle ich als Informatiker ab der Position 0.

Demnach: pos(n) = (pos(n-1)+7) mod n (für n >2)

oder für Informatiker:

public class EneMeneMuh {

	public static void main (String args[]) {
	    for ( int i = 2; i < 42; i++ )
		System.out.println( "Bei " + i + " Personen: Position " + pos( i ) );
	} // main( )


	public static int pos( int n ) {
	    if ( n == 2 ) return 1; 
	    else return ( 7 + pos( n-1 ) ) % n;
	} // pos( )

} // class EneMeneMuh

--Uschroeder 12:47, 16. Jan. 2009 (CET)

Wirklich coole Lösung! :-) --Cspannagel 23:30, 16. Jan. 2009 (CET)

Bemerkung

• Das Problem wurde wohl bereits einmal von einer Schülerin im Rahmen von Jugend forscht gelöst (Link1, Link2). Allerdings ist die Lösung leider nirgendwo aufzufinden.
• Eine ausführliche Behandlung in allgemeiner Form findet man bei: Helmut Siemon: Das Josephus-Problem. In: Praxis der Mathematik 27 (1985), S.200-212; Helmut Siemon: Das Josephus-Problem im Schulunterricht. In: Praxis der Mathematik 28 (1986), S.433-443
  • Vielen Dank für diesen tollen Literaturtipp! --Cspannagel 00:10, 9. Jan. 2009 (CET)--Cspannagel 00:10, 9. Jan. 2009 (CET)

Modulo

ene mene... sind 7 Silben, d.h. x%7...

Daraus folgt, wenn weniger als 7 Menschen, dann solltest du an Position 1 stehen und selbst abzählen, ansonsten bei 7 oder mehr an Position 2 und warten, bis sich Nr. 1 selbst ausgezählt hat und bei den 6 übrigen du selbst die Nr. 1 wirst und abzählst...