Rechenaufgaben

[kad]

Drei Personen - A, B und C - waren alle perfekte Logiker. Jeder von ihnen konnte sofort alle Konsequenzen aus einer beliebigen Menge von Prämissen ableiten. Außerdem war sich jeder bewusst, dass jeder der anderen ein perfekter Logiker war. Den dreien wurden sieben Briefmarken gezeigt: zwei rote, zwei gelbe und drei grüne. Dann wurden ihnen die Augen verbunden und jeweils eine Briefmarke auf die Stirn geklebt; die restlichen vier Briefmarken wurden in eine Schublade gelegt. Als die Augenbinden abgenommen wurden, wurde A gefragt: „Kennen Sie eine Farbe, die Sie definitiv nicht haben? A antwortete: ''Nein.'' Dann wurde B die gleiche Frage gestellt und er antwortete: „Nein.
Ist es möglich, aus dieser Information die Farbe der Briefmarke von A, von B oder von C abzuleiten?

[wepe]

C müsste Grün tragen? Ich kann das nicht mathematisch berechnen.
Weder A noch B dürfen die gleichen Farben rot oder gelb sehen, wenn sie gefragt werden - sonst hätten sie eine eindeutige Antwort, da nur 2 gelbe und rote Marken im Spiel sind. Wenn C Grün trägt, bleiben für A und B noch mehrere Optionen, denn es sind ja 3 Marken vorhanden.

[kad]

C müsste Grün tragen? Ich kann das nicht mathematisch berechnen.
Weder A noch B dürfen die gleichen Farben rot oder gelb sehen, wenn sie gefragt werden - sonst hätten sie eine eindeutige Antwort, da nur 2 gelbe und rote Marken im Spiel sind. Wenn C Grün trägt, bleiben für A und B noch mehrere Optionen, denn es sind ja 3 Marken vorhanden.

Spoiler

Das stimmt, C muss eine grüne Briefmarke auf der Stirne haben!

Wieso?

Spoiler

Angenommen, C hat eine rote Briefmarke auf der Stirn. A kann nur wissen, welche Farbe sie nicht hat, wenn B und C beide eine rote Briefmarke auf der Stirn haben. Wenn A also sagt, dass sie das nicht weiß, erfährt B, dass sie keine rote Briefmarke auf der Stirn hat. Würde man B nun fragen, ob sie eine Farbe kennt, die sie nicht auf ihrer Stirn hat, würde sie antworten: „Ich weiß, dass die Briefmarke auf meiner Stirn nicht rot ist.“ Aber B sagt, dass sie keine Farbe kennt, die sie definitiv nicht hat. Daher kann C keine rote Briefmarke auf ihrer Stirn haben. Ein analoges Argument lässt sich unter der Annahme vorbringen, dass C eine gelbe Briefmarke auf der Stirn hat. Wenn C weder eine rote noch eine gelbe Briefmarke hat, muss sie eine grüne Briefmarke auf der Stirn haben.

[giffi marauder]

Nur im Sinne von 02, 20

Spoiler

ok,
wir beginnen mit n=1
dann betrachten wir nur jeweils die letzte Stelle ob die 0,1 oder 2 ist.
Alle bisherherigen gültigen Wörter ergänzen wir mit 0, mit 1 und mit 2
n=1-> 1,1,1 (gültige Wörter endend auf 0,1,2) P(1)=3
+0-> 1,1,0=2
+1->1,1,1=3
+2->0,1,1=2
n=2-> 2,3,2 (gültige Wörter endend auf 0,1,2) P(2)=7
+0-> 2,3,0=5
+1->2,3,2=7
+2->0,3,2=5
n=3-> 5,7,5 (gültige Wörter endend auf 0,1,2) P(3)=17
+0-> 0,7,5=12
+1->5,7,5=17
+2->5,7,0=12
n=4-> 12,17,12 (gültige Wörter endend auf 0,1,2) P(4)=41
...
Offensichtlich gilt für P(n+1)
P(n) ergänzt mit 1
+(P(n)-P(n-1))/2+P(n-1) ergänzt mit 0
+(P(n)-P(n-1))/2+P(n-1) ergänzt mit 2
=2*P(n)+P(n-1)

Sei P(0)=1
P(1)=3
->
P(2)=2*3+1=7
P(3)=2*7+3=17
P(4)=2*17+7=41
99,239...

PS.:
Die Lösung falls auch 00 und 22 auch nicht erlaubt wären, wäre dann P(n+1)=P(n)+2*P(n-1) (mit P(0)=1)
also 3,5,11,21,43,85...

Spoiler

Genau, so sieht die Rekursionsformel aus!
Hat eine ähnliche Struktur wie bei den Fibonacci Zahlen. Dort kann man eine explizite Formel herleiten.
Hier auch?

Spoiler

Nun ja, der Quotient zweier aufeinanderfolgender Glieder P(n+1)/P(n) konvergiert gegen 2,41421356 = 1+Wurzel(2) =x
Die explizite Formel hat dann wohl die Form a*x^n+b(n).

Wenn wir jetzt noch den Faktor (a) mit P(n)/x^n bestimmten sind wir so gut wie am Ziel.
Dieser ist 1,20710678 bzw. x/2
->x/2*x^n+b(n) bzw. 1/2*x^(n+1) +b(n)

Wir bilden die Differenzen von P(n)-1/2*x^(n+1) und stellen fest:
a) Der Fehler bei n=0 beträgt genau (1-wurzel(2))/2
b) Der fehler konviergiert ziemlich schnell gegen 0
und damit ist wohl (1-wurzel(2))^(n+1)/2 genau das, was wir suchen.
Mit dem Korrekturglied b(n) haben wir nun die finalen Lösung
=1/2*((1+wurzel(2))^(n+1)+((1-wurzel(2))^n+1))
Voila.

[kad]

Nur im Sinne von 02, 20

Spoiler

ok,
wir beginnen mit n=1
dann betrachten wir nur jeweils die letzte Stelle ob die 0,1 oder 2 ist.
Alle bisherherigen gültigen Wörter ergänzen wir mit 0, mit 1 und mit 2
n=1-> 1,1,1 (gültige Wörter endend auf 0,1,2) P(1)=3
+0-> 1,1,0=2
+1->1,1,1=3
+2->0,1,1=2
n=2-> 2,3,2 (gültige Wörter endend auf 0,1,2) P(2)=7
+0-> 2,3,0=5
+1->2,3,2=7
+2->0,3,2=5
n=3-> 5,7,5 (gültige Wörter endend auf 0,1,2) P(3)=17
+0-> 0,7,5=12
+1->5,7,5=17
+2->5,7,0=12
n=4-> 12,17,12 (gültige Wörter endend auf 0,1,2) P(4)=41
...
Offensichtlich gilt für P(n+1)
P(n) ergänzt mit 1
+(P(n)-P(n-1))/2+P(n-1) ergänzt mit 0
+(P(n)-P(n-1))/2+P(n-1) ergänzt mit 2
=2*P(n)+P(n-1)

Sei P(0)=1
P(1)=3
->
P(2)=2*3+1=7
P(3)=2*7+3=17
P(4)=2*17+7=41
99,239...

PS.:
Die Lösung falls auch 00 und 22 auch nicht erlaubt wären, wäre dann P(n+1)=P(n)+2*P(n-1) (mit P(0)=1)
also 3,5,11,21,43,85...

Spoiler

Genau, so sieht die Rekursionsformel aus!
Hat eine ähnliche Struktur wie bei den Fibonacci Zahlen. Dort kann man eine explizite Formel herleiten.
Hier auch?

Spoiler

Nun ja, der Quotient zweier aufeinanderfolgender Glieder P(n+1)/P(n) konvergiert gegen 2,41421356 = 1+Wurzel(2) =x
Die explizite Formel hat dann wohl die Form a*x^n+b(n) mit Konvergenz von b(n) nach 0.

Wenn wir jetzt noch den Faktor (a) mit P(n)/x^n bestimmten sind wir so gut wie am Ziel.
Dieser ist 1,20710678 bzw. x/2
->x/2*x^n+b(n) bzw. 1/2*x^(n+1) +b(n)

Der Fehler bei n=0 beträgt genau (1-wurzel(2))/2 bzw. (1-wurzel(2))^(n+1)/2

Damit haben wir auch das Korrekturglied b(n) und die finalen Lösung
=1/2*((1+wurzel(2))^(n+1)+((1-wurzel(2))^n+1))

Spoiler

Super!

Eine frühere Variante von dir mit der gaussschen Abrundungsfunktion ist eben so richtig.

[kad]

Wie gross ist die Quersumme der Quersumme der Quersumme von 2000 hoch 2000?

[giffi marauder]

Wie gross ist die Quersumme der Quersumme der Quersumme von 2000 hoch 2000?

Spoiler

wir haben 2^2000*1000^2000
der zweite Teil ist für die Quersumme irrelevant.
damit ist die gesuchte Quersumme jene von 2^2000

2^2000 hat gut 600 Stellen. 1+(je +3 Stellen für 2^10)^200
Die Quersumme einer 1111'stelligen Zahl ist mit maximal 1111*9=9999 <= 4-stellig.
Mit den ca. 600 Stellen sind wir da klar drunter.
Die zweite Quersumme ist somit mit maximal 4*9= 36 <=2-stellig
Die dritte Quersumme damit maximal 9 und somit einstellig.

Die 3-fach Quersummen der Potenzen von 2 sind damit einstellig und ausserdem zyklisch
2^0=1
2^1=2
2^2=4
2^3=8
2^4=7
2^5=5
2^6=1
....
2000/6=333+1/3
Damit ist die Quersumme von 2^(6*333)=2^1998=1
von 2^1999=2
von 2^2000=4
bzw. von 2000^2000=4

[kad]

Wie gross ist die Quersumme der Quersumme der Quersumme von 2000 hoch 2000?

Spoiler

wir haben 2^2000*1000^2000
der zweite Teil ist für die Quersumme irrelevant.
damit ist die gesuchte Quersumme jene von 2^2000

2^2000 hat gut 600 Stellen. 1+(je +3 Stellen für 2^10)^200
Die Quersumme einer 1111'stelligen Zahl ist mit maximal 1111*9=9999 <= 4-stellig.
Mit den ca. 600 Stellen sind wir da klar drunter.
Die zweite Quersumme ist somit mit maximal 4*9= 36 <=2-stellig
Die dritte Quersumme damit maximal 9 und somit einstellig.

Die 3-fach Quersummen der Potenzen von 2 sind damit einstellig und ausserdem zyklisch
2^0=1
2^1=2
2^2=4
2^3=8
2^4=7
2^5=5
2^6=1
....
2000/6=333+1/3
Damit ist die Quersumme von 2^(6*333)=2^1998=1
von 2^1999=2
von 2^2000=4
bzw. von 2000^2000=4

Spoiler

Das stimmt!

[kad]

Neun 1 x 1 Zellen eines 10 x 10 Quadrats sind infiziert. Innerhalb einer Zeiteinheit werden die Zellen mit mindestens zwei infizierten Nachbarn (mit einer gemeinsamen Seite) infiziert. Kann sich die Infektion auf das gesamte Quadrat ausbreiten?

[wepe]

zu den bunten Briefmarken und Giffis Auflösung: Ich weiß schon, warum ich "5" vor dem Abi in Mathe hatte ...
Solche Formeln sind für mich der Horror!
Gerettet hat mich damals Bestimmung eines Kompasskurses nach Mercator - ich war zu blöde, den zu berechnen, konnte aber mit Winkelmesser und Strahlensatz den Kurs grafisch bestimmen. Es wurde punktmäßig anerkannt, dass ich angekommen wäre ...

[giffi marauder]

zu den bunten Briefmarken und Giffis Auflösung: Ich weiß schon, warum ich "5" vor dem Abi in Mathe hatte ...
Solche Formeln sind für mich der Horror!
Gerettet hat mich damals Bestimmung eines Kompasskurses nach Mercator - ich war zu blöde, den zu berechnen, konnte aber mit Winkelmesser und Strahlensatz den Kurs grafisch bestimmen. Es wurde punktmäßig anerkannt, dass ich angekommen wäre ...

Ja, Mathe ist ein ziemlicher Horror.
Formel, Sätze, Lemma stur auswendiglernen ist nicht so mein Ding und bei Mathe III im Studium hab ich nur mit Glück
die kommissionelle 4. Prüfung vermeiden können.

Ich muss selbst bei den einfachsten Sachen ab und an mal googeln, ob die Ereinnerung da nicht einbisschen trügt.
Das Grübeln macht mir aber ziemlichen Spaß.
Meist starte ich bei, hm, war da nicht mal was?

[kad]

Ja, Mathe ist ein ziemlicher Horror.
Formel, Sätze, Lemma stur auswendiglernen….

Ich finde Mathe ist etwas sehr Schönes .
Wie bei fast allem, müssen gewisse Grundlagen schnell abrufbar sein (ie „auswendiglernen“), um schwierigere Aufgaben lösen zu können.

[giffi marauder]

Drei Personen - A, B und C - waren alle perfekte Logiker. Jeder von ihnen konnte sofort alle Konsequenzen aus einer beliebigen Menge von Prämissen ableiten. Außerdem war sich jeder bewusst, dass jeder der anderen ein perfekter Logiker war. Den dreien wurden sieben Briefmarken gezeigt: zwei rote, zwei gelbe und drei grüne. Dann wurden ihnen die Augen verbunden und jeweils eine Briefmarke auf die Stirn geklebt; die restlichen vier Briefmarken wurden in eine Schublade gelegt. Als die Augenbinden abgenommen wurden, wurde A gefragt: „Kennen Sie eine Farbe, die Sie definitiv nicht haben? A antwortete: ''Nein.'' Dann wurde B die gleiche Frage gestellt und er antwortete: „Nein.
Ist es möglich, aus dieser Information die Farbe der Briefmarke von A, von B oder von C abzuleiten?

Spoiler

Spät aber doch.
Ich hab mal wieder ganz flüchtig das "oder" in der Frage überlesen.
"Ist es möglich, aus dieser Information die Farbe der Briefmarke von A, von B oder von C abzuleiten?"
Die Suche nach der Lösung für allen drei Farben, ist ohne Antwort von C aber gescheitert.

Also hier meine "oder" Lösung:
Ich benamse rot, gelb, grün =blau in r,g,b um.
Als Informatiker fühl ich mich damit einfach wohler.

Das Trippel xyz steht für A=x, B=y, C=z

Wäre die Konstellation xrr (oder xgg) wüßte A, dass er !r (oder !g) hat, da es diese Farben ja nur 2x gibt.
Da A das aber nicht weiss, sind die Farben von B und C entweder verschieden oder beide blau.
Das weiß nun auch B.
Da B die Farbe von C sieht, wüßte er, wenn diese rot oder gelb wäre, dass er diese Farbe nicht hat.
Da B das aber nicht weiss, ist die Farbe von C blau, äh grün.

[giffi marauder]

Wie gross ist die Quersumme der Quersumme der Quersumme von 2000 hoch 2000?

Spoiler

wir haben 2^2000*1000^2000
der zweite Teil ist für die Quersumme irrelevant.
damit ist die gesuchte Quersumme jene von 2^2000

2^2000 hat gut 600 Stellen. 1+(je +3 Stellen für 2^10)^200
Die Quersumme einer 1111'stelligen Zahl ist mit maximal 1111*9=9999 <= 4-stellig.
Mit den ca. 600 Stellen sind wir da klar drunter.
Die zweite Quersumme ist somit mit maximal 4*9= 36 <=2-stellig
Die dritte Quersumme damit maximal 9 und somit einstellig.

Die 3-fach Quersummen der Potenzen von 2 sind damit einstellig und ausserdem zyklisch
2^0=1
2^1=2
2^2=4
2^3=8
2^4=7
2^5=5
2^6=1
....
2000/6=333+1/3
Damit ist die Quersumme von 2^(6*333)=2^1998=1
von 2^1999=2
von 2^2000=4
bzw. von 2000^2000=4

Das stimmt!

Das mag ja sein, aber meine Argutmentation enthält eine Denkfehler.
Wer ihn findet, darf ihn behalten.

[kad]

Drei Personen - A, B und C - waren alle perfekte Logiker. Jeder von ihnen konnte sofort alle Konsequenzen aus einer beliebigen Menge von Prämissen ableiten. Außerdem war sich jeder bewusst, dass jeder der anderen ein perfekter Logiker war. Den dreien wurden sieben Briefmarken gezeigt: zwei rote, zwei gelbe und drei grüne. Dann wurden ihnen die Augen verbunden und jeweils eine Briefmarke auf die Stirn geklebt; die restlichen vier Briefmarken wurden in eine Schublade gelegt. Als die Augenbinden abgenommen wurden, wurde A gefragt: „Kennen Sie eine Farbe, die Sie definitiv nicht haben? A antwortete: ''Nein.'' Dann wurde B die gleiche Frage gestellt und er antwortete: „Nein.
Ist es möglich, aus dieser Information die Farbe der Briefmarke von A, von B oder von C abzuleiten?

Spoiler

Spät aber doch.
Ich hab mal wieder ganz flüchtig das "oder" in der Frage überlesen.
"Ist es möglich, aus dieser Information die Farbe der Briefmarke von A, von B oder von C abzuleiten?"
Die Suche nach der Lösung für allen drei Farben, ist ohne Antwort von C aber gescheitert.

Also hier meine "oder" Lösung:
Ich benamse rot, gelb, grün =blau in r,g,b um.
Als Informatiker fühl ich mich damit einfach wohler.

Das Trippel xyz steht für A=x, B=y, C=z

Wäre die Konstellation xrr (oder xgg) wüßte A, dass er !r (oder !g) hat, da es diese Farben ja nur 2x gibt.
Da A das aber nicht weiss, sind die Farben von B und C entweder verschieden oder beide blau.
Das weiß nun auch B.
Da B die Farbe von C sieht, wüßte er, wenn diese rot oder gelb wäre, dass er diese Farbe nicht hat.
Da B das aber nicht weiss, ist die Farbe von C blau, äh grün.

Spoiler

Ja, blau ist richtig