Agenten mit Pudeln aufem Kopp [gelöst] - Seite 2

11.10.2005, 14:36

Ach, ich hatte erst mit Vektoren aus $\begin{eqnarray*} \mathbb{Z}_2^m \end{eqnarray*}$ hantiert, die jeder abzählen und sich merken musste; dabei war dann noch eine Fehler in dieser Überlegung, ... , kurzum: Ein Irrweg.

11.10.2005, 15:11

MrPSI

Auf diesen Beitrag antworten »

ähm... ich hab vergessen zu fragen, wieso eigentlich bei Arthur Dents Lösungsweg immer der ganzzahlige Rest berechnet wird?
Kann mir das bitte jemand erklären?

11.10.2005, 15:23

JochenX

Auf diesen Beitrag antworten »

versuche doch erstmal die einfache lösung mit zwei farben zu begreifen, wo jeder der agenten nur weiß, die summe aller vor ihm sitzenden pudel + seiner ist gerade bzw. ungerade

wenn man das versteht, ist eigentlich arthurs und pis erweiterung "trivial"
jeder der agenten weiß, welchen pudel er haben muss, da die gesamtsumme (mod m) einen speziellen wert haben muss

11.10.2005, 17:42

KimmeY

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent

Zitat:

Original von MrPSI
verstellt die Tonhöhe seiner Stimme um den nächsten die Pudelfarbe zu verraten.

... und wird daraufhin von Dr.No erschossen. unglücklich

EDIT:

OK, dann mal mein Lösungsweg, vermutlich sehr ähnlich dem von Pimaniac. Wir betrachten $\begin{eqnarray*} m \end{eqnarray*}$ verschiedene Pudelfarben, numeriert von $\begin{eqnarray*} 1,\ldots,m \end{eqnarray*}$ . Sei nun $\begin{eqnarray*} f_k \end{eqnarray*}$ die Farbe des Pudels von 00k. Dann kann 00k die Summe $\begin{eqnarray*} s_k:=f_{k+1}+f_{k+2}+\cdots+f_N \end{eqnarray*}$ durch bloßes Sehen berechnen.

001 verkündet nun (uneigennützig) die Farbe $\begin{eqnarray*} s_1\mod m \end{eqnarray*}$ . Damit kann 002 den Wert $\begin{eqnarray*} f_2\equiv s_1-s_2\mod m \end{eqnarray*}$ eindeutig bestimmen und verkünden. Anschließend kann 003 über $\begin{eqnarray*} f_3\equiv s_1-f_2-s_3\mod m \end{eqnarray*}$ eindeutig bestimmen und verkünden, usw.

Allgemein kann 00k über $\begin{eqnarray*} f_k\equiv s_1-f_2-\cdots-f_{k-1}-s_k\mod m \end{eqnarray*}$ seine Pudelfarbe bestimmen: Denn $\begin{eqnarray*} s_k \end{eqnarray*}$ kennt er (s.o.) und die anderen Werte $\begin{eqnarray*} s_1,f_2,\ldots,f_{k-1} \end{eqnarray*}$ hört er. Das war's schon!

erm kannst du das nochmal für dumme erklären? ich verstehs einfach net, was genau soll bitte mod m sein und wie genau kann man sich dies dann ausrechnen??? verwirrt

oder ist das nur was was man versteht wenn man mathe studiert hat??? *mal als dume schülerin fragen tu*

11.10.2005, 18:35

Auf diesen Beitrag antworten »

http://de.wikipedia.org/wiki/Modulo_%28Rest%29

In der Informatik-Variante würde man allerdings die Farbe m mit Farbe 0 gleichsetzen - anders gesagt: Man betrachtet die Farb-Nummern 0 bis (m-1) statt 1..m. Aber das ist rum wie num.

11.10.2005, 19:59

MrPSI

Auf diesen Beitrag antworten »

Lieg ich richtig in der Annahme, dass das Identisch-Zeichen im Lösungsweg daher rührt:

s1=s2+f2
f2=s1-s2

Dann wird "moduliert".

f2 mod 2 = (s1-s2) mod 2

und da f2 identisch mit f2 mod 2 (f2 kann ja hier nur 0[=rosa] oder 1[=weiß] sein und daher kann auch f2 mod 2 nur 0 oder 1 sein)

folgt

f2 identisch mit (s1-s2) mod 2

11.10.2005, 20:07

Auf diesen Beitrag antworten »

Ja, so kann man es sagen.

11.10.2005, 20:43

KimmeY

Auf diesen Beitrag antworten »

ok, das prinzip hab ich verstanden, wie das geht, aber
1. wie teilt der erste den anderen das mit, wenn er nur weiß und rosa sagen darf
und
2.was genau bringt denen das, dass hab ich noch immer nicht verstanden.

11.10.2005, 20:52

Auf diesen Beitrag antworten »

Da die Agenten sich vor dem Pudel-Aufsetzen über ihre Strategie verständigen dürfen, legen sie natürlich einen Code fest, z.B.

0 = weiß
1 = rosa

11.10.2005, 22:27

MrPSI

Auf diesen Beitrag antworten »

*Lösungsweg gecheckt hab*

was mir beim Verständnis Schwierigkeiten bereitet hat, ist, dass ich nicht wusste wie man aus dem s1 Modulo 2 auf s1 schließen kann, weil es es ja praktisch unendlich viele Lösungen dafür geben kann(wenn man ein vielfaches des Divisors dazuzählt).
Doch dann bin ich draufgekommen, dass wenn man in die Formel zur Berechnung von f2 auch ein Vielfaches von 2 zum Dividenden dazuzählen kann, ohne dass sich das Ergebnis ändert.
Kurz gesagt, der Spion braucht nur ein beliebiges s1 zu wählen, das die mod 2-Bedingung erfüllt, um das richtige Ergebnis zu erhalten.

11.10.2005, 22:42

Auf diesen Beitrag antworten »

Zitat:

Original von MrPSI
Kurz gesagt, der Spion braucht nur ein beliebiges s1 zu wählen, das die mod 2-Bedingung erfüllt, um das richtige Ergebnis zu erhalten.

"Wählen" ist gut - im Bereich der verfügbaren Farben (also {0, 1}) ist das genau eine Farbe, da gibt es nicht viel zu wählen.

11.10.2005, 22:53

MrPSI

Auf diesen Beitrag antworten »

wieso denn? s1 ist ja eine Summe aus Nullen und Einsen(Farbwerten), deshalb kanns auch >1 sein.

11.10.2005, 22:55

JochenX

Auf diesen Beitrag antworten »

aber erwählt ja nicht s1, dass "sieht" er ja
und e verkündet ja s1 mod m, also in unserem falle signalisiert er gerade bzw. ungerade

11.10.2005, 22:59

Auf diesen Beitrag antworten »

Vielleicht sollten wir mal ein Beispiel durchspielen. Also, MrPSI, wähle mal m, N und eine konkrete Pudelverteilung auf die N Agenten, und wir zeigen dir, wie das dann genau abläuft.

11.10.2005, 23:14

JochenX

Auf diesen Beitrag antworten »

na gut, arthur ich lege einfach mal ein einfaches Beispiel vor

wir haben 7 Agenten (damits auch was zu rechnen gibt)
ihnen werden die Pudelfarben rot, blau, tieforsa und burlywood aufgesetzt

die agenten entscheiden sich im vorgespräch rot=0, blau=1, rosa=2 und undefinierbar=3 zu setzen

wir als zuschauer finden folgende pudelfarben vor:
001 rot
002 blau
003 rot
004 blau
005 tieforsa
006 tieforsa
007 rot

nun gehts los, wer will rechnen?

edit: juhu, den ersten habe ich geschlachtet smile

habe noch die zahlwahlen verbuntet
burlywood ist echt ein dämlicher name für eine farbe

11.10.2005, 23:29

Auf diesen Beitrag antworten »

Na gut, dann rechne ich mal. Zuerst die Vorbereitungen, also die Farbzahlzuordnungen und die Summen der Farbzahlen, die die Agenten vor sich sehen können: Insgesamt haben wir m=4 Farben und

001 0 , $\begin{eqnarray*} s_1=6 \end{eqnarray*}$
002 1 , $\begin{eqnarray*} s_2=5 \end{eqnarray*}$
003 0 , $\begin{eqnarray*} s_3=5 \end{eqnarray*}$
004 1 , $\begin{eqnarray*} s_4=4 \end{eqnarray*}$
005 2 , $\begin{eqnarray*} s_5=2 \end{eqnarray*}$
006 2 , $\begin{eqnarray*} s_6=0 \end{eqnarray*}$
007 0 , $\begin{eqnarray*} s_7=0 \end{eqnarray*}$

Agent 001 rechnet jetzt $\begin{eqnarray*} s_1=6\equiv 2\mod 4 \end{eqnarray*}$ , nennt also Farbe 2, und das ist rosa - er ruhe in Frieden. traurig

So, jetzt muss ich mich erstmal von der schweren Rechnerei ausruhen.

EDIT: Mist, schon verrechnet - korrigiert.

11.10.2005, 23:37

JochenX

Auf diesen Beitrag antworten »

genau, einen haben wir tot, aber mehr kriegen wir nicht

denn agent 2 weiß: ahaaha "gesamtsumme von den pudeln von 002 bis 00N" ist mod 4 kongruent zu 2.
ich sehe vor mir 5. also muss 5+x eine viererzahl +2 sein, also, da x aus {0,1,2,3} muss x=1 sein => x=1 heißt blauer pudel, sagt also blau und ist frei

agent 003 hat nun das wissen, dass 002 bis 00N zusammen pudel im werte viererzahl + 2 besitzen UND, da agent 002 nicht dumm ist, auch dass 002 tatsächlich einen blauen pudel (vom werte 1) haben muss
folglich sollte der pudelsummenwert von 003 bis 00N genau eine viererzahl +1 sein. sieht vor sich 5 pudel, daraus folgt, dass er einen 0erpudel aufhat.
sagt also rot und ist frei.
agent 004....

jetzt sollte es klar sein, oder?

preisfrage: was passiert, wenn agent 00M (M<N) sich verrechnet? Augenzwinkern

MASSENSTERBEN

11.10.2005, 23:43

Auf diesen Beitrag antworten »

Temporär gelöscht - wird wieder restauriert, später ... Augenzwinkern

12.10.2005, 00:59

pimaniac

Auf diesen Beitrag antworten »

Ok ich versteh dass noch immer nicht

Wenn der blaue Pudel jetzt mal gediegen kotzen muss weil Agent 006 eine heiße Nacht mir einer Asiatischen Schönheit verbracht hat und sich danach weder geduscht noch die Zähne geputzt hat, und ergo stinkt wie ein schwein, nehmen wir mal an der Pudel ist jetzt plötzlich kreidebleich... was machen wir dann?

Ok Frage anders gestellt. Angenommen die Agenten machen sich n Farben aus aber plötzlich sind k (der einfach heit halber mal k=n+1) Farben da. Wieviel kommen dann mindestens frei?

Meine Lösung:

naja ich würd sagen immer um die Differenz der neuen Farbanzahl und der ursprünglichen Farbanzahl weniger

12.10.2005, 01:09

JochenX

Auf diesen Beitrag antworten »

jaja, arthur und seine offtopics, die häufen sich in diesem thread

pi, du kannst es nicht lassen, oder?
müssen so aber noch einige fragen geklärt werden: wird allen agenten gesagt, dass es plötzlich eine farbe mehr gibt?

wenn ja, sollte es einfach sein, da alle natürlich sofort wissen, dass 001 einfach das system von oben erweitert (zugekommene farbe gibt neue zahl n);
und da sie natürlich mit dieser diabolität doktor nos gerechnet haben, planen sie auch, dass (sollte er statt n farben n+m farben auffahren) 001 das ganze so erweitert, dass die m zsuatzafarben der alphabetischen reihenfolge der zusatzfarben nach die zahlenwerte n bis n+m-1 bekommen (das einzige was sie dann noch schocken kann sind undefinierbare farben wie burlywood)

wenn sie allerdings NICHT vorher gesagt bekommen, dass es mehr farben gibt, dann sehe ich schwarz.
sie allerdings nicht, denn schwarz ist bekanntlich keine farbe.
aber zumindest kann 001 durch coolness mindestens alle bis zur ersten wechselfarbe retten (es sei denn, die agenten 002 etc. sehen, dass vorne die farbe wechselt und rechnen mit einem anderen system ARGH) unglücklich

edit: gespiggelt, wie du auf deine lösung kommst ist mir grad schleierhaft

12.10.2005, 17:17

pimaniac

Auf diesen Beitrag antworten »

erstens mal könnt das bitte einer auf wichtig setzen damit es wieder vorne angezeigt wird... sonst mach ich einen neuen thread auf...

Neues prolem konkretisiert lautet folgendermaßen:

Sie erfahren von Dr. No dass n Farben existieren und erfahren auch welche wissen aber dass es auch mehr sein könnten erfahren aber nicht in welcher Reihenfolge welche dazukommen. Sie wissen also erst von den neuen Farben wenn sie sie am nächsten Tag sehen. Sie dürfen als Antwort nur einen existenten Farbnamen sagen, keine Stimmenverstellungen oder anderswertigen Unsinn.

12.10.2005, 18:03

Auf diesen Beitrag antworten »

Ich steige erst wieder ein, wenn das mal jemand verständlich formuliert, ohne Haken und Wendungen nach jedem Halbsatz. smile

12.10.2005, 18:22

pimaniac

Auf diesen Beitrag antworten »

ja ich weiß deutsche sache schwere sprache... also ich werd propieren

Es gibt k Agenten die folgendes Wissen besitzen:

A) Sie werden am nächsten Tag in der Früh in einen Raum gesetzt, sie sehen nur ihre Vordermänner die Pudel am Kopf haben.

B) Einer nach dem anderen muss wie bisher gehabt eine Farbe sagen, stimmt die Farbe mit dem Pudel auf seinem Kopf überein kommt er frei.

C) Ihnen wird gesagt dass es m verschiedene Farben geben wird, die sie auch kennen. Falls weniger als m tatsächlich vorkommen dürfen sie aber natürlich trotzdem diese m Farbnamen zu ihrer Kommunikation verwenden. Das System ist sauber also keine Tricks alla Stimme verstellen oder schwul stöhnen.

D) Ihnen wird aber auch gesagt dass es unter Umständen auch mehr Farben verwendet werden könnten, ihnen wird aber weder eine Höchstgrenze noch die Namen der Farben die der Reihe nach als nächstes eingesetzt werden genannt.

Frage ist nun wieviele nun mindestens freikommen.

12.10.2005, 18:44

KimmeY

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Na gut, dann rechne ich mal. Zuerst die Vorbereitungen, also die Farbzahlzuordnungen und die Summen der Farbzahlen, die die Agenten vor sich sehen können: Insgesamt haben wir m=4 Farben und

001 0 , $\begin{eqnarray*} s_1=6 \end{eqnarray*}$
002 1 , $\begin{eqnarray*} s_2=5 \end{eqnarray*}$
003 0 , $\begin{eqnarray*} s_3=5 \end{eqnarray*}$
004 1 , $\begin{eqnarray*} s_4=4 \end{eqnarray*}$
005 2 , $\begin{eqnarray*} s_5=2 \end{eqnarray*}$
006 2 , $\begin{eqnarray*} s_6=0 \end{eqnarray*}$
007 0 , $\begin{eqnarray*} s_7=0 \end{eqnarray*}$

Agent 001 rechnet jetzt $\begin{eqnarray*} s_1=6\equiv 2\mod 4 \end{eqnarray*}$ , nennt also Farbe 2, und das ist rosa - er ruhe in Frieden. traurig

So, jetzt muss ich mich erstmal von der schweren Rechnerei ausruhen.

EDIT: Mist, schon verrechnet - korrigiert.

ahso, und es kann also nie irgendwas rauskommen, wo jetzt keine ahnung irgendwas mit 13 rauskommen als mod, sondern immer nur was <=m ???

12.10.2005, 19:49

JochenX

Auf diesen Beitrag antworten »

Zitat:

ahso, und es kann also nie irgendwas rauskommen, wo jetzt keine ahnung irgendwas mit 13 rauskommen als mod, sondern immer nur was <=m ???

das ist das schöne am modulorechnen, also nur den rest beim teilen durch die pudelzahl betrachten

@pimaniac: möglich wäre natürlich, dass alle agenten die weiteren farben, die sie sehen aufzählen, sobald ein agent keine farben mehr sieht, die die vorderen agenten nicht kennen, könnte er das übliche spiel betreiben
verwirrt

12.10.2005, 19:58

pimaniac

Auf diesen Beitrag antworten »

ja darauf läufts hinaus... aber ich glaub eine kleinigkeit fehlt dir noch.... weiterdenken!

12.10.2005, 20:09

JochenX

Auf diesen Beitrag antworten »

hm, also was mir auf jeden fall noch zur taktik einfallen würde:
kommt eine der neuen farben nur hinten vor, ist es eventuell möglich einen agenten zu sparen, indem diese farbe gar nicht erwähnt wird

sie beginnen deswegen mit der farbe, die von den nichtgenanntebn am weitesten vorne ist, denn diese muss auf jeden fall genannt werden.

desweiteren können sie abschätzen, wieviele kollegen sich opfern müssen, können es damit evtl hinbiegen, dass zumindest einer seine richtige farbe sagt (indem sie insbesondere nicht weggesagt wird)

diese beiden vorschläge widersprechen sich allerdings und sind deswegen schlecht Augenzwinkern

mehr ideen habe ich gerade nicht mehr wie man noch mehr agenten retten kann

12.10.2005, 20:24

pimaniac

Auf diesen Beitrag antworten »

Ergebnis, nur um dich weiter anzuspornen,

m=ursprüngliche Farbzahl
n=neue Farbzahl
k=Anzahl der Agenten

Retten können sie mindestens

k-1+m-n

Also z.B. bei ursprünglich 3 Farben und plötzlich 2 weiteren

k-3 statt k-1 Agenten

VIel Spaß beim Kopfzerbrechen

:-)

12.10.2005, 22:30

KimmeY

Auf diesen Beitrag antworten »

also ich würd mir das so vorstellen. der erste agent sagt die erste farbe die man nicht weiß,die bekommt dann sozusagen die nächste zahl zugeordnet die man für dieses mod braucht.
also wenn s z.b. 5 farben (mit 0-4 belegt)gibts dann ist die nächste farbe halt 5 die genannt wird.der rest der agenten hört gut zu merkt sich das alles. der nächste agent sieht ja welche farben fehlen.
das ganze geht so lange weiter bis es keine neuen farben mehr gibt.
so wenns keine neuen farben mehr gibt wäre dann der nächste mit dem mod dingens dran und würde sich opfern, der rest ab da würde freikommen.

also, wir haben k agenten,davon ziehen wir den ab der sich opfert (-1) und wir ziehen nochmal die differenz der farben ab, weil (n-m) agenten erstmal die vorbereitung wie oben besprochen weiter vorrantreiben müssen, damit der rest auch funktioniert.also die farben nennen damit der rest rechnen kann smile

hätten dann also k-1-(n-m) = k-1+m-n

hoffe das klingt so halbwegs logisch^^

12.10.2005, 22:41

pimaniac

Auf diesen Beitrag antworten »

Kluge KimmeY

« vorherige Seite 12

Neue Frage »

Antworten »

Agenten mit Pudeln aufem Kopp [gelöst] - Seite 2

Verwandte Themen