Quelltext der Seite Projekt:Mathe-Werkstatt/Ene-Mene-Muh-Problem

= Das Ene-Mene-Muh-Problem =

Problem gestellt von Christine Bescherer und Christian Spannagel --[[Benutzer:Cspannagel|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 <math>1,2,3,\ldots ,n</math>. 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 <math>7 \bmod 6 = 1</math> fällt heraus. (Der Abzählreim hat 7 Wörter und es gibt 6 Personen.)

<s>1</s> 2 3 4 5 6

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

<math>2 \rightarrow 1</math>

<math>3 \rightarrow 2</math>

<math>4 \rightarrow 3</math>

<math>5 \rightarrow 4</math>

<math>6 \rightarrow 5</math>

<math>n_1 \rightarrow n_2= (n_1 - 7 \bmod 6) \bmod 6</math>

(<math>7 \bmod 6</math> ist die Nummer, die heraus fällt, und <math>\bmod 6</math> danach ergibt sich aus 5 Plätzen.)

'''''2. Abzählen:'''''

Die Person mit der Nummer <math>7 \bmod 5 = 2</math> fällt heraus.

1 <s>2</s> 3 4 5

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

<math>3 \rightarrow 1</math>

<math>4 \rightarrow 2</math>

<math>5 \rightarrow 3</math>

<math>1 \rightarrow 4</math>

<math>n_2 \rightarrow n_3 = (n_2 - 7 \bmod 5) \bmod 5</math>

'''''3. Abzählen:'''''

Die Person mit der Nummer <math>7 \bmod 4 = 3</math> fällt heraus.

1 2 <s>3</s> 4

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

<math>4 \rightarrow 1</math>

<math>1 \rightarrow 2</math>

<math>2 \rightarrow 3</math>

<math>n_3 \rightarrow n_4 = (n_3 - 7 \bmod 4) \bmod 4</math>

'''''4. Abzählen:'''''

Die Person mit der Nummer <math>7 \bmod 3 = 1</math> fällt heraus.

<s>1</s> 2 3

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

<math>2 \rightarrow 1</math>

<math>3 \rightarrow 2</math>

<math>n_4 \rightarrow n_5 = (n_4 - 7 \bmod 3) \bmod 3</math>

'''''5. Abzählen:'''''

Die Person mit der Nummer <math>7 \bmod 2 = 1</math> fällt heraus.

<s>1</s> 2

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

<math>2 \rightarrow 1</math>

<math>n_5 \rightarrow n_6 = (n_5 - 7 \bmod 2) \bmod 2</math>


* Siehe auch [[w:Josephus-Problem|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:

<pre>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</pre>

--[[Benutzer:Uschroeder|Uschroeder]] 12:47, 16. Jan. 2009 (CET)

: Wirklich coole Lösung! :-) --[[Benutzer:Cspannagel|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 ([http://www.jugend-forscht-oberfranken.de/index.php?id=274 Link1], [http://www.stadt.bamberg.de/pres.phtml?FID=332.5426.1&La=1&call=detail 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! --[[Benutzer:Cspannagel|Cspannagel]] 00:10, 9. Jan. 2009 (CET)--[[Benutzer:Cspannagel|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...