Untreue Minister []

19.02.2007, 16:47

pandu1

Auf diesen Beitrag antworten »

Untreue Minister []

Der Polizeichef kam zum König:
"Eure Majestät, aus sicheren Quelen ist mir bekannt geworden, dass euer Bruder gestern alle eure Minister zu sich eingeladen hat. Er bot jeden eine Million in Gold, falls sie ihm helfen, die Macht zu übernehmen. Zum Glück waren die meisten Minister dagegen. Aber jetzt weisst er genau, wer von den Minister euch untreu ist."
"Und wer ist mir untreu?" fragte der König.
"Dass weiss ich leider nicht."
"Ich gebe dir 30 Tage, Wenn du mir danach nicht genau sagst, wer von den Ministern untreu ist, wirst du meinen Hencker kennenlernen."

Es gibt insgesammt 21 Minister.
Auch für den Polizeichef ist es schwierig, einen Thermin bei Minister zu bekommen. Also darf er pro Tag nur einen Minister besuchen. Und nur eine Frage stellen, die mit "Ja" oder "Nein" beantwortet werden kann.
Jeder Minister weiss von jeden anderen, ob er treu oder untreu ist.
Jeder treuer Minister wird die Warheit sagen.
Jeder untreuer Minister wird entweder lügen, oder auch nicht.
Kann der Polizeichef es schaffen?

19.02.2007, 19:44

Snowfan

Auf diesen Beitrag antworten »

RE: Untreue Minister
Hallo Wink

Wink

Wenn du so fragst, würd ich mal sagen, ja! Der Polizeichef kanns schaffen Big Laugh

Big Laugh

LG
SF

19.02.2007, 20:00

kiste

Auf diesen Beitrag antworten »

Jaaa stimm dir vollkommen zu Streetfighter.

Offizieller Polizeicheffanclub

Offizieller Polizeicheffanclub

19.02.2007, 20:08

Snowfan

Auf diesen Beitrag antworten »

... es wurde ja nicht nach dem "wie" gefragt...

http://www.my-smileys.de/smileys3/567.gif

Dem Fanclub trete ich hiermit auch bei!

LG
SF

19.02.2007, 20:35

pandu1

Auf diesen Beitrag antworten »

OK

Hammer

, die richtige Frage ist "Wie kann er dass schaffen?" Lehrer

Lehrer

19.02.2007, 20:41

PrototypeX29A

Auf diesen Beitrag antworten »

Ab wievielen sind es "die meisten Minister"?

Anzeige

19.02.2007, 21:11

pandu1

Auf diesen Beitrag antworten »

11 oder mehr, höchstens aber 20, sind treu.

20.02.2007, 11:27

pandu1

Auf diesen Beitrag antworten »

Wir können es etwas vereinfachen.
Es gibt 7 Minister, mehr als die Hälfte davon sind treu (4,5 oder 6) Wie viele Tage braucht man um festzustellen, wer ist treu und wer nicht.
Man kann es zum Beispiel so lösen:
1. Wir fragen jeden Minister, ob der erster treu ist
2. Wenn die Mehrheit ja sagt, dann ist er auch treu. Dann können wir den 1. Minister über jeden anderen fragen.
3. Wenn die Mehrheit sagt, dass der erster Minister untreu ist, fragen wir jeden über den zweiten Minister.
4. Wenn die Mehrheit sagt, dass der zweiter treu ist, wird er über jeden anderen Minister gefragt.
5. Ist der zweiter Minister auch untreu, so fangen wir an, alle über den dritten zu befragen.
6. Ist der dritte treu, wird er befragt, sonst haben wir 3 untreue Minister gefunden. Damit ist der Fall geschlossen.

Also müssen wir in worst case 3*7+6 = 27 Fragen stellen.
Wie kann man es schneller lösen?

28.02.2007, 08:13

pandu1

Auf diesen Beitrag antworten »

Noch ein Hinweis:

Zitat:

Arthur Dent (c)
Gewöhnlich geht man bei sowas ja rekursiv vor

02.03.2007, 14:45

pandu1

Auf diesen Beitrag antworten »

Für 2N+1 Minister gibt es eine Befragungsstrategie mit höchstens 3N Fragen. Dabei ist es unwichtig, ob es überhaupt untreue Minister gibt. Aber ich habe keinen Beweis, dass es nicht noch schneller geht.

04.03.2007, 00:01

matze(2)

Auf diesen Beitrag antworten »

Es sei n = 1. Dann soll es also eine Befragungsstrategie geben, mit der man mit 3 Fragen die treuen und untreuen der 3 Minister ausfindig machen kann.
Die ersten beiden Fragen werden sich an den 2. und 3. Minister richten, ob der 1. treu oder untreu ist. Wenn beide sagen, dass der 1. treu ist, stimmt dies auch. Nun sind der 2. der 3. oder beide Minister treu. Mit einer Frage kann man zwar klären ob der 2. treu ist, wenn dies nicht der Fall ist, ist alles geklärt, wenn aber der 2. Minister treu ist, bleibt offen, ob der 3. treu oder untreu ist. So würde ich sagen, dass es nicht egal ist ob überhaupt ein Minister untreu ist. verwirrt

verwirrt

04.03.2007, 09:12

pandu1

Auf diesen Beitrag antworten »

Zitat:

Original von matze(2)
Die ersten beiden Fragen werden sich an den 2. und 3. Minister richten, ob der 1. treu oder untreu ist.(

Hier ist die zweite erste Frage überflüssig.
Wir fragen M2, ob M1 treu ist. Falls er ja sagt, dann ist der M1 auch treu. Entweder ist M2 ein treuer und sagt die Wahrheit, oder er ist untreu, aber mehr als einen darf es bei N=1 nicht geben.
Falls der zweite nein sagt, dann ist entweder M1 oder M2 untreu, also M3 treu.
So finden wir bei N=1 nach 1. Frage einen treuen.

04.03.2007, 20:21

Done

Auf diesen Beitrag antworten »

Ist das eventuel das gleiche wie mit den beiden schwestern:

es gibt 2 schwestern, eine sagt immmer die wahrheit eine lügt immer!
nun möchte man den weg wissen, sprich ob es nach links oder rechts geht.
Welche frage muss man nun stellen?
-Was würde deine schwester sagen?
Dann muss man nur noch das gegenteil machen und hat den weg!

Ist das vllt hier genauso?

04.03.2007, 22:18

pandu1

Auf diesen Beitrag antworten »

Nein, hier ist es anders.

05.03.2007, 08:51

pandu1

Auf diesen Beitrag antworten »

Nachdem wir den Fall mit N=1 (3 Minister) gelöst haben, können wir folgendes aussagen.
Für 2N+1 Minister, mit höchstens N untreuer gilt:
$\begin{eqnarray*} (T_1) \end{eqnarray*}$ Ein Minister $\begin{eqnarray*} M_i \end{eqnarray*}$ ist treu, falls ein treuer Minister sagt, dass er treu ist.
$\begin{eqnarray*} (T_2) \end{eqnarray*}$ Ein Minister $\begin{eqnarray*} M_i \end{eqnarray*}$ ist treu, falls N Minister sagen, dass er treu ist. Entweder sind die befragten Minister alle untreu, dann gibt es keine untreue Minister mehr. Oder es gab bei dieser Befragung mindestens einen treuen, der die Wahrheit sagt.
$\begin{eqnarray*} (U_1) \end{eqnarray*}$ Ein Minister $\begin{eqnarray*} M_i \end{eqnarray*}$ ist untreu, falls ein treuer Minister sagt, dass er untreu ist.
$\begin{eqnarray*} (U_2) \end{eqnarray*}$ Ein Minister $\begin{eqnarray*} M_i \end{eqnarray*}$ ist untreu, falls er einmal gelogen hat. Dass heisst er hat einen treuen minister untreu genannt, oder umgekehrt.
$\begin{eqnarray*} (X_1) \end{eqnarray*}$ Falls $\begin{eqnarray*} M_i \end{eqnarray*}$ sagt, dass $\begin{eqnarray*} M_j \end{eqnarray*}$ untreu ist, so ist mindestenst einer von $\begin{eqnarray*} \{M_i,M_j\} \end{eqnarray*}$ untreu.
$\begin{eqnarray*} (X_2) \end{eqnarray*}$ Falls $\begin{eqnarray*} M_j \end{eqnarray*}$ sagt, dass $\begin{eqnarray*} M_i \end{eqnarray*}$ untreu ist, und $\begin{eqnarray*} M_k \end{eqnarray*}$ sagt dass $\begin{eqnarray*} M_i \end{eqnarray*}$ treu ist, so ist mindestenst einer von $\begin{eqnarray*} \{M_j,M_k\} \end{eqnarray*}$ untreu.

Diese Aussagen sind ausreichend, um die Aufgabe zu lösen.
Bei der Lösung kommen wir mit einfachen Fragen wie "ist der Minister Mi treu" zu Recht.

06.03.2007, 08:16

pandu1

Auf diesen Beitrag antworten »

$\begin{eqnarray*} (A_1) \end{eqnarray*}$ Für N=1 ist die Aufgabe mit höchstens 3 Fragen lösbar
Schritt1: Wir Fragen $\begin{eqnarray*} M_2 \end{eqnarray*}$ ob $\begin{eqnarray*} M_1 \end{eqnarray*}$ treu ist. Sagt er ja, so ist $\begin{eqnarray*} M_1 \end{eqnarray*}$ laut $\begin{eqnarray*} (T_2) \end{eqnarray*}$ treu, sonst ist laut $\begin{eqnarray*} (X_2) \end{eqnarray*}$ $\begin{eqnarray*} M_3 \end{eqnarray*}$ treu.
Schritt2: Wir fragen den treuen Minister über zwei anderen
Insgesammt 3 Fragen.

$\begin{eqnarray*} (A_2) \end{eqnarray*}$ Für N=2 ist die Aufgabe mit höchstens 6 Fragen lösbar
Schritt1: Wir Fragen $\begin{eqnarray*} M_2 \end{eqnarray*}$ ob $\begin{eqnarray*} M_1 \end{eqnarray*}$ treu ist. Sagt er ja, so machen wir mit Schritt2 weiter. Falls er nein sagt ist nach $\begin{eqnarray*} (X_2) \end{eqnarray*}$ mindestenst einer von $\begin{eqnarray*} \{M_1,M_2\} \end{eqnarray*}$ untreu. Wir wenden $\begin{eqnarray*} (A_1) \end{eqnarray*}$ an $\begin{eqnarray*} \{M_3,M_4,M_5\} \end{eqnarray*}$ /3 Fragen/ und fragen anschliessend den treuen Minister über $\begin{eqnarray*} M_1 \end{eqnarray*}$ und $\begin{eqnarray*} M_2 \end{eqnarray*}$ .
Schritt2: Wir Fragen $\begin{eqnarray*} M_3 \end{eqnarray*}$ ob $\begin{eqnarray*} M_1 \end{eqnarray*}$ treu ist. Sagt er ja, so machen wir mit Schritt3 weiter. Falls er nein sagt ist nach $\begin{eqnarray*} (X_1) \end{eqnarray*}$ mindestenst einer von $\begin{eqnarray*} \{M_2,M_3\} \end{eqnarray*}$ untreu. Wir wenden $\begin{eqnarray*} (A_1) \end{eqnarray*}$ an $\begin{eqnarray*} \{M_1,M_4,M_5\} \end{eqnarray*}$ /3 Fragen/. Danach wissen wir wer von $\begin{eqnarray*} \{M_2,M_3\} \end{eqnarray*}$ gelogen hat $\begin{eqnarray*} (U_2) \end{eqnarray*}$ . Den treuen Minister fragen wir über den anderen.
Schritt3: Wir fragen den treuen Minister $\begin{eqnarray*} M_1 \end{eqnarray*}$ über vier anderen
Aber für eine allgemeine Lösung reicht es noch nicht

07.03.2007, 20:48

matze(2)

Auf diesen Beitrag antworten »

ooops, da habe ich nicht weit genug gedacht Hammer

Hammer

06.06.2007, 08:21

pandu1

Auf diesen Beitrag antworten »

Ich mach noch einen:
$\begin{eqnarray*} (A_3) \end{eqnarray*}$ Für N=3 ist die Aufgabe mit höchstens 9 Fragen lösbar
Schritt1: Wir Fragen $\begin{eqnarray*} M_2 \end{eqnarray*}$ ob $\begin{eqnarray*} M_1 \end{eqnarray*}$ treu ist. Sagt er ja, so machen wir mit Schritt2 weiter. Falls er nein sagt ist nach $\begin{eqnarray*} (X_2) \end{eqnarray*}$ mindestenst einer von $\begin{eqnarray*} \{M_1,M_2\} \end{eqnarray*}$ untreu. Wir wenden $\begin{eqnarray*} (A_2) \end{eqnarray*}$ an $\begin{eqnarray*} \{M_3,M_4,M_5,M_6,M_7\} \end{eqnarray*}$ /6 Fragen/ und fragen anschliessend den treuen Minister über $\begin{eqnarray*} M_1 \end{eqnarray*}$ und $\begin{eqnarray*} M_2 \end{eqnarray*}$ .
Schritt2: Wir Fragen $\begin{eqnarray*} M_3 \end{eqnarray*}$ ob $\begin{eqnarray*} M_1 \end{eqnarray*}$ treu ist. Sagt er ja, so machen wir mit Schritt3 weiter. Falls er nein sagt ist nach $\begin{eqnarray*} (X_1) \end{eqnarray*}$ mindestenst einer von $\begin{eqnarray*} \{M_2,M_3\} \end{eqnarray*}$ untreu. Wir wenden $\begin{eqnarray*} (A_2) \end{eqnarray*}$ an $\begin{eqnarray*} \{M_1,M_4,M_5,M_6,M_7\} \end{eqnarray*}$ /6 Fragen/. Danach wissen wir wer von $\begin{eqnarray*} \{M_2,M_3\} \end{eqnarray*}$ gelogen hat $\begin{eqnarray*} (U_2) \end{eqnarray*}$ . Den treuen Minister fragen wir über den anderen.
Schritt3: Wir Fragen $\begin{eqnarray*} M_4 \end{eqnarray*}$ ob $\begin{eqnarray*} M_1 \end{eqnarray*}$ treu ist. Sagt er ja, so machen wir mit Schritt4 weiter. Falls er nein sagt ist nach $\begin{eqnarray*} (X_1) \end{eqnarray*}$ mindestenst einer von $\begin{eqnarray*} \{M_3,M_4\} \end{eqnarray*}$ untreu. Wir wenden $\begin{eqnarray*} (A_2) \end{eqnarray*}$ an $\begin{eqnarray*} \{M_1,M_2,M_5,M_6,M_7\} \end{eqnarray*}$ , fangen aber direkt mit Schritt 2 /5 Fragen/. Danach wissen wir wer von $\begin{eqnarray*} \{M_3,M_4\} \end{eqnarray*}$ gelogen hat $\begin{eqnarray*} (U_2) \end{eqnarray*}$ . Den treuen Minister fragen wir über den anderen.

Schritt4: Wir fragen den treuen Minister $\begin{eqnarray*} M_1 \end{eqnarray*}$ über 6 anderen

01.09.2008, 18:35

pandu1

Auf diesen Beitrag antworten »

Schade, dass fast keiner versucht hat das zu lösen.
Natürlich versteht der Polizeischef nicht viel von Rekursivitäten, man kann auch ohne versuchen.

1

Verwandte Themen