Coding-Rätsel | Forumspiel

[Shadow992]

Okay ich hau mal ein kleines Rätsel für zwischendurch rein:

Ist Smith der Mörder?

Du bist Detektiv und sollst herausfinden ob Smith mit 100% Sicherheit der Mörder war, dazu hast du genau folgende Zeugenaussagen:

John: "Smith ist der Mörder und ich habe ihn zur Tatzeit gesehen war aber nach Mitternacht nicht am Tatort, was heißt, dass die Tatzeit vor Mitternacht war"
Smith: "Wenn ich der Mörder bin und der Mord nach Mitternacht war, dann kann ich John nicht getroffen haben"
William: "Der Mord ist nach Mitternacht passiert"

Von den Aussagen oben ist genau eine gelogen, die zwei anderen sind die Wahrheit (wir wissen jedoch nicht welche wahr/gelogen sind).
Die Frage ist jetzt, kann man eindeutig sagen, dass Smith der Mörder ist und wenn ja warum? Wenn nein warum nicht?

P.S.
Nein es geht nicht um irgendwelche versteckte Keywörter o.ä. es geht hier wirklich nur um die Logik-Frage an sich.

[algernong]

Ich komme nicht drauf. Mein Ansatz wäre:

 Spoiler

A: Smith ist Mörder
B: Mord nach Mitternacht
C: John und Smith haben sich getroffen

Dann sind die Aussagen:

John: A und nicht(B) und C
Smith: (A und B) impliziert nicht(C)
William: B

Angenommen, John lügt. Dann sagt William die Wahrheit, also B = 1. Das widerspricht schon John. Smith muss die Wahrheit sagen, also (A impliziert nicht(C)) = 1. Dazu reicht A = 1, oder A = 0 und C = 1. Also kann er es gewesen sein, oder auch nicht?

[DrackenDarck]

Originally Posted by Shadow992

Okay ich hau mal ein kleines Rätsel für zwischendurch rein:

Ist Smith der Mörder?



P.S.
Nein es geht nicht um irgendwelche versteckte Keywörter o.ä. es geht hier wirklich nur um die Logik-Frage an sich.

- Die Thematik des Rätsels muss sich zwingend mit Informatik beschäftigen.

Sicher,dass es darauf zutrifft und nicht einfach ein Rätsel ist? Weil dann wäre es hier falsch
Weil dann können wir auch einfach ein Finde den Fehler in einem Bild spielen

[onahoe]

Originally Posted by DrackenDarck

Sicher,dass es darauf zutrifft und nicht einfach ein Rätsel ist? Weil dann wäre es hier falsch
Weil dann können wir auch einfach ein Finde den Fehler in einem Bild spielen

Naja im Entfernten hat es was mit Logikprogrammierung zu tun, also gar nicht soo abwegig, aber das war auch mein erster Gedanke. Aber ich lasse es mal gelten, solange es fortan nicht ständig solche Logikscheiße zu sehen gibt Achja, dein Rätsel war übrigens nicht zu schwer. Habe es in 3 Minuten geknackt, nur leider 'ne Stunde zu spät gesehen ^^

[alpines]

Originally Posted by Shadow992

Nein es geht nicht um irgendwelche versteckte Keywörter o.ä. es geht hier wirklich nur um die Logik-Frage an sich.

Ich würde vermuten das man eine Wahrheitstabelle aufstellen muss und eine der drei aufsagen eliminiert und schaut wo sich alle drei Tabellen schneiden?

[onahoe]

Originally Posted by alpines

Ich würde vermuten das man eine Wahrheitstabelle aufstellen muss und eine der drei aufsagen eliminiert und schaut wo sich alle drei Tabellen schneiden?

Es ist ja an sich 'ne einfache Aufgabe, sodass man es mit Probieren rauskriegen könnte, aber es formaler wäre, wenn man 'ne aussagenlogische Formel aufstellt und dann mit 'ner Wahrheitstabelle auswertet. Da man 100% will muss es am Ende 'ne Tautologie also allgemeingültig sein. Aber macht mal, ich bin dafür eh zu blöde

[Shadow992]

Originally Posted by algernong

Ich komme nicht drauf. Mein Ansatz wäre:

 Spoiler

A: Smith ist Mörder
B: Mord nach Mitternacht
C: John und Smith haben sich getroffen

Dann sind die Aussagen:

John: A und nicht(B) und C
Smith: (A und B) impliziert nicht(C)
William: B

Angenommen, John lügt. Dann sagt William die Wahrheit, also B = 1. Das widerspricht schon John. Smith muss die Wahrheit sagen, also (A impliziert nicht(C)) = 1. Dazu reicht A = 1, oder A = 0 und C = 1. Also kann er es gewesen sein, oder auch nicht?

Das ist eine mögliche Lösung, also seh ich es als gelöst an auch wenn da ein Fragezeichen am Ende ist (wollte ja nur nen kleines für Zwischendurch reinhauen bis sich jemand ein neues überlegt hat).

Das heißt:
Nein man kann nicht sicher sagen, dass Smith der Mörder ist.

Edit:
@Logik
Ihr werdet nicht glauben wie oft sich ein Informatiker mit Logikfragen beschäftigen muss und wie viele verschiedene Ansätze es dafür in der Informatik gibt.
Da Informatik ja sowieso eine Kombination von Mathe, "Computer-Konzepte" und bissel Physik ist, ist es schwer Fragen zu stellen, die sich nicht auch mit Mathe/Physik beschäftigen.

@Wahrheitstafel
Kann man natürlich machen, ist aber doch bissel Aufwand, dafür dass man relativ schnell sehen kann (und sicher die Intuition einem das auch sagt), dass man nicht sicher sagen kann, dass Smith der Mörder ist.

@Tautologie
Ebenfalls eine Möglichkeit aber dauert halt bissel

[algernong]

Ich habe auch eins (ist aber nicht von mir, nur umgeschrieben):

Wir haben 100 SRAM Speicherzellen für je ein Bit. Nach dem Einschalten sind die Speicherzellen in unbekanntem Zustand: Wir wissen nicht, welche Zelle im Zustand "1" und welche im Zustand "0" ist. Leider haben wir auch unser Messgerät vergessen, weswegen wir keine Möglichkeit haben, die Zustände irgendwie herauszufinden.

Einzig erinnern wir uns an die letzte Unterrichtseinheit "Quacksalberei mit Mr. Info", nach der SRAM Speicherzellen genau im Verhältnis 1:9 den Zustand "1" annehmen. Haargenau 10 der 100 Speicherzellen haben also den Zustand "1", währen die anderen 90 den Zustand "0" haben.

Für eine magische Voodoo-Anwendung müssen wir den Speicher nun derart in zwei Bereiche unterteilen, dass in beiden Bereichen genau gleich viele Bits den Zustand "1" haben. Die Bereiche müssen nicht gleich groß sein, die Anzahl der 0en ist egal, die Bereiche müssen disjunkt sein und den Speicher komplett abdecken. Der erste Speicherbereich umfasst also die Bits 1..x, der zweite Speicherbereich die Bits (x+1)..100.

Wegen einem Defekt in der ALU steht uns außerdem nur das logische Nicht zur Verfügung. Also kein bitweises Und, Oder, ... und keine arithmetischen Operationen.

Wie bekommen wir die Voodoo Anwendung zum Laufen?

[Shadow992]

Originally Posted by algernong

Ich habe auch eins (ist aber nicht von mir, nur umgeschrieben):

Ich bin verwirrt?
Heißt das ich kann genau folgende "Operationen" verwenden?

- Logisches Nicht

Und das alles ist nicht möglich:

- Auslesen einzelner Bits
- Vergleichsoperatoren
- Arithmetische Operatoren
- Verknüpfen der Bits in jeglicher Art und Weise

Das heißt ich habe im Grunde die Infos:

- 10% sind 1
- 2 Teile sind gefordert

Und alles was ich damit machen kann ist im Grunde ein:

Not(SRAM_KOMPLETT)
bzw. NOT(NOT(SRAM_KOMPLETT))

Wie soll man damit das Rätsel lösen oder habe ich was falsch verstanden?

[algernong]

Du darfst NOT auch auf einzelnen Speicherzellen anwenden, nicht nur auf den kompletten SRAM. NOT(10) oder NOT(50..62) usw. geht also auch

Und das alles ist nicht möglich:

Genau

Und am Ende muss das Verhältnis 1:9 nicht mehr gelten; es müssen nur genau gleich viele 1en in beiden Bereichen sein, wobei die genaue Anzahl egal ist.

[Shadow992]

Originally Posted by algernong

Du darfst NOT auch auf einzelnen Speicherzellen anwenden, nicht nur auf den kompletten SRAM. NOT(10) oder NOT(50..62) usw. geht also auch


Genau

Und am Ende muss das Verhältnis 1:9 nicht mehr gelten; es müssen nur genau gleich viele 1en in beiden Bereichen sein, wobei die genaue Anzahl egal ist.

Ich hab dazu 3 Ideen, wobei ich für die eine schon ein ganz grobes Grundgerüst habe (scheint aber nicht in jedem Fall zu funktionieren).

1. Alle 1en bzw. 0en entfernen, dann ist es egal wie man partitioniert (scheint mir schwer/nicht möglich zu sein)

2. Alle 1en ans Ende/an den Anfang verschieben. Eine Einzige 1 lässt sich zum Beispiel mit einem abwechselnden Not verschieben:

1000

-> Verschieben, indem man auf Bit 0,1 dann auf Bit 1,2 und dann auf 2,3 ein Not anwendet:

1000 -> 0100 -> 0010 -> 0001

Ich weiß nur nicht wie man das allgemeingültig anwendbar macht. Sehe hier aber großes potential.

3. Einen Algorithmus erdenken, der egal wo die Zahlen sind, nach einer bestimmten Anzahl Wiederholungen die 1en immer an dieselbe Stelle bringt (sowas wie abgewandeltes Bogosort ).

Aber keine konkreten Ideen, ich bin kurz davor da einmal Evolutionäre-Programmierung drauf zuhauen, mal sehen

[Menan]

Das mit dem Verschieben müsste sich ja aufheben dann.. Bei genau 10 Bits die 1en sind.

Angenommen du hast folgende Struktur und fängst an bei der 1 mit dem verschieben nach Rechts, also ein Not auf die Bits 3,4:

0010001  -> 0001001 -> 00000101 -> 00000011 -> 00000000

somit müsste sich ja über kurz oder lang alle 1en entfernen, bei einer Geraden Anzahl von Einsen. Wenn keine 1 mehr vorhanden ist, ist auch die Bedigung erfüllt.

[Shadow992]

Originally Posted by Menan

Das mit dem Verschieben müsste sich ja aufheben dann.. Bei genau 10 Bits die 1en sind.

Angenommen du hast folgende Struktur und fängst an bei der 1 mit dem verschieben nach Rechts, also ein Not auf die Bits 3,4:

0010001  -> 0001001 -> 00000101 -> 00000011 -> 00000000

somit müsste sich ja über kurz oder lang alle 1en entfernen, bei einer Geraden Anzahl von Einsen. Wenn keine 1 mehr vorhanden ist, ist auch die Bedigung erfüllt.

Prinzipiell ja, da du aber nicht weiß wo die 1en sind und ein plumpes "verschieben" von vorne bis hinten würde bei deinem Beispiel das produzieren:

0010001 -> 1110001 -> 1000001 -> 1011001 -> 1010101-> 1010011 -> 1010000

Das heißt hier hättest du eher eine Verschiebung nach links. Das ist eben das Problem, es funktioniert nicht in jedem Fall sondern nur in ein paar bestimmten Fällen, theoretisch muss es aber für alle Verteilungen passen.

[Menan]

Stimmt, da hast du recht.

Aber kannst du nicht garantieren, dass der Zustand nach einer gewissen Anzahl an Iterationen immer gleich sein könnte, egal wie die Bits am Anfang belegt waren?

Und dann von diesem einem "bekannten" Zustand weiter machen?

[Shadow992]

Originally Posted by Menan

Stimmt, da hast du recht.

Aber kannst du nicht garantieren, dass der Zustand nach einer gewissen Anzahl an Iterationen immer gleich sein könnte, egal wie die Bits am Anfang belegt waren?

Und dann von diesem einem "bekannten" Zustand weiter machen?

Ich habe hier auch einmal einen quick & dirty C++ Code aufgesetzt und bissel rumprobiert, tatsächlich gibt es Fälle wo das ganze oszilliert (das heißt nach 10x durchgehen fängts wieder von vorne an). Das liegt aber immer daran wie die Bits verteilt sind.

Das beste ist echt, wenn man es schafft einen Algorithmus zu machen, der immer genau 1 Bit von links nach rechts bringt und keine Bits sich auflösen/überschreiben.

Da man weiß, dass es genau 10 sind müsste man immer nur die letzten 5 und die restlichen 95 jeweils in eine Partition packen.

Aber mir fehlt noch dieser Tausch-Algorithmus. :/

Falls es jemand hilft mein Quick&Dirty C++ Code:

#include <iostream>
#include <vector>

using namespace std;

void NOT_ARR(vector<bool>& arr,int start, int endIdx)
{
    for(int i=start;i<endIdx;i++)
    {
        arr[i] = !arr[i];
    }
}

void printArr(vector<bool>& arr)
{
    for(int i=0;i<100;i++)
    {
        cout<<arr[i];
        if(i%20==19)
            cout<<endl;
    }
    cout<<endl;
}

int main()
{
    const int bitsToSetCount=1;
    const int step=2;
    const int halfstep=step/2;

    srand(time(NULL));

    vector<bool> arr(100,0);
    int addedBits=0;

    while(addedBits<bitsToSetCount)
    {
        //uncomment to set first bit
        int bitToSet=0;

        //uncomment to set random bit
        //int bitToSet=rand()%100;
        if(arr[bitToSet]==false && rand()%10==0)
        {
            addedBits++;
            arr[bitToSet]=true;
        }
    }

    printArr(arr);

    for(int a =0;a<4;a++)
    {
        //NOT_ARR(arr,0,1);
        for(int i=0;i<100-1;i+=halfstep)
        {
            NOT_ARR(arr,i,i+step);
        }
        printArr(arr);
    }
}