Denksportaufgabe

[*jiriki*]

Hi, da ich hier gerade so ne nette Stochastikaufgabe hab, und auf keinen grünen Zweig komme, möchte ich Eure Gehirnzellen mal etwas fordern:

Auf wieviele Art und Weisen können sich n Matrosen auf n Matten verteilen, ohne dass auch nur einer auf seiner eigenen liegt (man gehe davon aus, dass jedem Matrosen genau eine Matte gehöre und diese mit einem Namensschild versehen ist).

Greets, *jiriki*

[Christian Kruse]

你好 *jiriki*,

Auf wieviele Art und Weisen können sich n Matrosen auf n Matten
verteilen, ohne dass auch nur einer auf seiner eigenen liegt (man gehe
davon aus, dass jedem Matrosen genau eine Matte gehöre und diese mit
einem Namensschild versehen ist).

Ich wuerde vermuten: (n-1)!
Der erste Matrose hat n-1 Moeglichkeiten, der zweite n-2, der dritte n-3,
... => (n-1)!

再见,
 CK

[MudGuard]

Hi,

Auf wieviele Art und Weisen können sich n Matrosen auf n Matten
verteilen, ohne dass auch nur einer auf seiner eigenen liegt (man gehe
davon aus, dass jedem Matrosen genau eine Matte gehöre und diese mit
einem Namensschild versehen ist).
Ich wuerde vermuten: (n-1)!
Der erste Matrose hat n-1 Moeglichkeiten, der zweite n-2, der dritte n-3,

Belegt der 1. Matrose die Matratze des 2. Matrosen, hat der 2. Matrose aber n-1 Möglichkeiten ...

cu,
Andreas

[Tim Tepaße]

Hallo,

Belegt der 1. Matrose die Matratze des 2. Matrosen, hat der 2. Matrose aber
n-1 Möglichkeiten ...

Wobei dann die Matrosen dann aber auch noch für die »rekursiv folgenden«
Matrosen mitdenken müssen, bei drei Matrosen darf sich dann der zweite
Matrose nicht einfach auch auf die Matraze des ersten legen, um es dem
dritten Matrosen nicht unmöglich zu machen, sich auf eine andere Matraze
als auf dessen eigene zu legen.

Tim

[Tom]

Hello,

*ggg* +ber "-1" sind sich alle einig...
fangen wir also damit an:
Jeder liegt auf seiner Matratze.
Das zählt nicht, merken wir uns.
Nun kann jeder mit jedem tauschen. Jeder Matrose kann also mit (n-1) Matrosen tauschen.
Wie oft funktioniert das? Ich würde raten (n-1)/2 mal.

also kommt da ((n-1)*(n-1)/2)-1 raus, oder?

Und, stimmt das?

Harzliche Grüße aus http://www.annerschbarrich.de

Tom

[Tom]

Hello,

Ups, es ist doch fakultät(n-1)

Wie kann man darauf nun auf einen Blick kommen?

Harzliche Grüße aus http://www.annerschbarrich.de

Tom

[Henryk Plötz]

Moin,

Ups, es ist doch fakultät(n-1)

Noe ist es nicht. Die Lösung für n=3 ist 2 (312, 231) und für n=4 ist es 9 (2143, 2341, 2413, 3142, 3412, 3421, 4123, 4312, 4321).

[*jiriki*]

Hello,

Ups, es ist doch fakultät(n-1)

Wie kann man darauf nun auf einen Blick kommen?

Harzliche Grüße aus http://www.annerschbarrich.de

Tom

Hehe, also (n-1)! isses nicht. Das kann man sich für das überschaubare Beispiel von 4 Matrosen und 4 Matten vergegenwärtigen ( da gibt es 9 Möglichkeiten ).
Nach Engagieren meines Mathenachbarn kamen wir auf folgende Lösung, die mit ziemlich hoher Wahrscheinlichkeit stimmt:

b(0) = 1
b(n) = n! - sum[k=1...n] { (n über k) * b(n-k) }

Naja, da kommt man jetzt nicht so leicht drauf, is klar ;) Die n! am Anfang repräsentieren alle Permutationen. Von diesen ziehen wir nun die ab, bei denen mind. 1 Matrose auf seiner Matte liegt (das ab dem Summensymbol). In der Summe wird die Anzahl der Permutationen dafür berechnet, dass genau k=1 bis k=n Matrosen ihre Matte finden. Nun bekomme ich mit (n über k) genau die Anzahl von Belegungen, dass genau k Matten richtig belegt sind. Diese muss ich dann noch mal nehmen mit der Anzahl der Permutationen, dass die übrigen n-k falsch belegten Matten auf b(n-k)-verschiedene Art und Weisen komplett falsch belegt sind (Rekursion).

So kommt man auf folgenden Java-Code, der noch den Erwartungswert für die durchschnittl. richtig belegten Matten ausgibt.

---------------------

public class matrosen
{
 public matrosen(){}
 public static int fak( int n )
 {
  if( n == 0) return 1;
  else
  {
   for( int i = n-1; i>1; i-- ) n *= i;
   return n;
  }
 }
 public static int ueber( int n, int k )
 {
  return ( fak(n) / ( fak(n-k)*fak(k) ) );
 }
 public static int jo( int n )
 {
  if( n == 0 ) return 1;
  else
  {
   int erg = 0;
   for( int i=1; i<=n; i++ ) erg += ueber( n, i ) * jo( n-i );
   erg = fak(n) - erg;
   return erg;
  }
 }
 public static int ew( int n )
 {
  int erg = 0;
  for( int i=0; i<=n; i++ ) erg += ueber(n,i) * jo(i) * (n-i);
  erg /= fak(n);
  return erg;
 }
 public static void main( String args[] )
 {

for( int i=0; i<=5; i++ )
  {
   System.out.println( i+" Matrosen koennen auf "+jo(i)+" moegliche Art und Weisen auf "+i+" Matten verteilt werden, sodass keiner seine eigene Matte belegt." );
   System.out.println( "Durchschnittlich belegen "+ew(i)+" von "+i+" Matrose(n) ihre eigenen Matten.\n" );
  }
 }
}
--------------------------

Greets, *jiriki*

[gant]

Tach auch

n * (n-1), würd ich vermuten...

Gruss

[Ludger]

Hi,

n * (n-1), würd ich vermuten...

das waere die Loesung ohne der Namensschild-Einschraenkung.

Gruss,
Ludger

[Christian Kruse]

你好 Ludger,

n * (n-1), würd ich vermuten...

das waere die Loesung ohne der Namensschild-Einschraenkung.

Nein, die waere genau n!

再见,
 CK

[Ludger]

Hi,

n * (n-1), würd ich vermuten...
das waere die Loesung ohne der Namensschild-Einschraenkung.
Nein, die waere genau n!

die Aufgabenstellung ohne Einschraenkung lautet: "Auf wieviele Art und Weisen können sich n Matrosen auf n Matten verteilen?"

Nun, haben wir zwei Matrosen, dann gibt es
 Anzahl = 2 * (2 - 1) = 2 Moeglichkeiten
 [1a2b, 1b2a]
Nun, haben wir drei Matrosen, dann gibt es
 Anzahl = 3 * (3 - 1) = 6 Moeglichkeiten
 [1a2b3c, 1b2a3c, 1b2c3a, 1c2b3a, 1c2a3b, 1a2c3b]
Nun, haben wir vier Matrosen, dann gibt es
 Anzahl = 4 * (4 - 1) = 12 Moeglichkeiten
 [ ...

Gruss,
Ludger

[MudGuard]

Hi,

Nun, haben wir zwei Matrosen, dann gibt es
Anzahl = 2 * (2 - 1) = 2 Moeglichkeiten
[1a2b, 1b2a]

Die Anzahl stimmt, die Begründung eher weniger.

Der erste Matrose kann aus 2 Matten wählen.
Der zweite Matrose hat nur noch 1 Matte zur Wahl.
2*1

Nun, haben wir drei Matrosen, dann gibt es
Anzahl = 3 * (3 - 1) = 6 Moeglichkeiten

Die Anzahl stimmt, die Begründung eher weniger.
Der erste Matrose kann aus 3 Matten auswählen
Der zweite Matrose aus den restlichen 2.
Der dritte Matrose hat nur noch 1 übrig.

3*2*1

[1a2b3c, 1b2a3c, 1b2c3a, 1c2b3a, 1c2a3b, 1a2c3b]
Nun, haben wir vier Matrosen, dann gibt es
Anzahl = 4 * (4 - 1) = 12 Moeglichkeiten

Spätestens ab hier ist auch die Anzahl falsch.

Der erste Matrose kann aus 4 Matten auswählen
Der zweite Matrose aus den restlichen 3.
Der dritte Matrose aus den restlichen 2.
Der vierte Matrose hat nur noch 1 übrig.

4*3*2*1 Wahlmöglichkeit, m.a.W.: 4!

cu,
Andreas

[Ludger]

Hi,

die Formel "Anzahl = n * (n-1)" ermittelt immerhin die Anzahl der Begegnungen in einem "Jeder gegen jeden"-Wettbewerb bei n Teilnehmern mit Hin- und Rueckspiel. Und darunter duerfen auch Matrosen sein.   ;-)

Gruss,
Ludger

[Christian Kruse]

你好 Ludger,

Hi,

n * (n-1), würd ich vermuten...
das waere die Loesung ohne der Namensschild-Einschraenkung.
Nein, die waere genau n!

die Aufgabenstellung ohne Einschraenkung lautet: "Auf wieviele Art und
Weisen können sich n Matrosen auf n Matten verteilen?"

Richtig. Rechne mal aus. Der erste Matrose hat n Moeglichkeiten, sich
hinzulegen. Der zweite n-1. Der dritte n-2. Der vierte n-3. Der fuenfte
n-4. Und so weiter, und so fort -- das ist n!

Nun, haben wir zwei Matrosen, dann gibt es
Anzahl = 2 * (2 - 1) = 2 Moeglichkeiten
[1a2b, 1b2a]

Jepp, halt 2!

Nun, haben wir drei Matrosen, dann gibt es
Anzahl = 3 * (3 - 1) = 6 Moeglichkeiten
[1a2b3c, 1b2a3c, 1b2c3a, 1c2b3a, 1c2a3b, 1a2c3b]

Ja, 3!

Nun, haben wir vier Matrosen, dann gibt es
Anzahl = 4 * (4 - 1) = 12 Moeglichkeiten
[ ...

Nein, 24:

1a,2b,3c,4d
1a,2b,3d,4c
1a,2c,3b,4d
1a,2c,3d,4b
1a,2d,3b,4c
1a,2d,3c,4b
1b,2a,3c,4d
1b,2a,3d,4c
1b,2c,3a,4d
1b,2c,3d,4a
1b,2d,3a,4c
1b,2d,3c,4a
1c,2a,3b,4d
1c,2a,3d,4b
1c,2b,3a,4d
1c,2b,3d,4a
1c,2d,3a,4b
1c,2d,3b,4a
1d,2a,3b,4c
1d,2a,3c,4b
1d,2b,3a,4c
1d,2b,3c,4a
1d,2c,3a,4b
1d,2c,3b,4a

再见,
 CK

[Andreas Görtz]

Hi,

Auf wieviele Art und Weisen können sich n Matrosen auf n Matten verteilen, ohne dass auch nur einer auf seiner eigenen liegt (man gehe davon aus, dass jedem Matrosen genau eine Matte gehöre und diese mit einem Namensschild versehen ist).

das ist ein sogenanntes "derangement" - zu lösen durch die Subfakultät:

!n = n!(1 - 1/1! + 1/2! - 1/3! + ... +/- 1/n!)

bzw.

[n!/e]

wobei [x] == nächste Ganzzahl bei x.

Gruß,
Andreas.

[Daniela Koller]

Hi *jiriki*

Auf wieviele Art und Weisen können sich n Matrosen auf n Matten verteilen, ohne dass auch nur einer auf seiner eigenen liegt (man gehe davon aus, dass jedem Matrosen genau eine Matte gehöre und diese mit einem Namensschild versehen ist).

n! - (n-1)!

n! sind alle Möglichkeiten. (n-1)! sind alle Möglichkeiten wo mindestens einer falsch liegt.

Gruss Daniela

[seth]

gudn tach!

n! - (n-1)!

noe, siehe Andreas posting oder http://mathworld.wolfram.com/Derangement.html.

(n-1)! sind alle Möglichkeiten wo mindestens einer falsch liegt.

noe, (n-1)! ist die anzahl der moeglichkeiten, dass ein bestimmter (vorher festgelegter) matrose in seinem bett liegt und alle anderen irgendwie gemixt sind.

prost
seth

[Daniel Thoma]

Hallo *jiriki*,

Neben Andreas' Lösung kann man auch noch folgende Rekursionsformel verwenden:

a(1) = 0;
a(n) = n * (a(n-1) + a(n-2));

Da kann man recht leicht erkennen, dass das so funktioniert:
Beispiel 5:

Der erste Matrose A hat 4 Möglichkeiten (Matten 2 bis 5).
Nennen wir den Matrosen, auf dessen Matte sich Matrose A legt B.
Matrose B kann sich nun auf die Matte von Matrose A legen. In diesem Fall bleiben 3 Matten und 3 Matrosen übrige und man hat das Problem offensichtlich auf den Fall n = 3 reduziert.
Wenn wir diese Möglichkeit nun ausschließen so kann man die 1. Matte nun Matrose B zuordnen und das Problem so auf den Fall n = 4 reduzieren.

Grüße

Daniel

[seth]

gudn tach!

Neben Andreas' Lösung kann man auch noch folgende Rekursionsformel verwenden:

a(1) = 0;
a(n) = n * (a(n-1) + a(n-2));

die erklaerung von dir war zwar richtig, aber diese formel ist falsch.
es muesste heissen:
a(1)=0
a(2)=1
a(n)=(n-1)*(a(n-1) + a(n-2))

(siehe http://mathworld.wolfram.com/Derangement.html)

prost
seth

[Daniel Thoma]

Hallo seth,

a(1)=0
a(2)=1

Klar, das muss man noch definineren, sonst funktioniert das nicht.

a(n)=(n-1)*(a(n-1) + a(n-2))

Das war ein Tippfehler ;-)

Dafür hab ich noch einen kleinen Beweis, warum das das selbe ist, wie Andreas' Lösung:

Induktionsanfang:
a(1) = 0; 1! (1 - 1) = 0;
a(2) = 1; 2! (1 - 1 + 1/2) = 1;

Induktionsschritt:
a(n + 1) = n(a(n) + a(n - 1))
= n (n! SUM[k=0; n]((-1)^k / k!) + (n - 1)! SUM[k=0; n - 1]((-1)^k / k!))
= n n! SUM[k=0; n]((-1)^k / k!) + n! SUM[k=0; n]((-1)^k / k!) - n! (-1)^n / n!
= (n + 1)! SUM[k=0; n]((-1)^k / k!) + (n + 1)! (-1)^(n + 1) / (n + 1)!
= (n + 1)! SUM[k=0; n + 1]((-1)^k / k!)

Grüße

Daniel