Im Kerker

Lösung

Ein Schloss wird beim n. Durchgang auf- bzw. zugeschlossen, wenn n Teiler der jeweiligen Zellennummer ist. Da am Anfang alle Zellen verschlossen sind, sind am Ende alle Zellen offen, deren Nummer eine ungerade Anzahl von Teilern hat. Das ist genau bei den Quadratzahlen der Fall, denn bei allen anderen Zahlen n gibt es zum Teiler t₁, der kleiner als die Wurzel der Zahl ist, einen zugehörigen Teiler t₂ = n/t₁, der größer als die Wurzel der Zahl ist. Bei Quadratzahlen n hat ein Teiler t keinen solchen "Partner", nämlich wenn t die Wurzel aus n ist.
Bis 1000 gibt es 31 Quadratzahlen (31² = 961). Folglich sind am Ende 31 Türen offen, so dass 31 Gefangene fliehen konnten.

Dieses Rätsel lässt sich auch hervorragend durch ein Computerprogramm simulieren. Hier ist der Quellcode eines solchen Programms in C++:

C++-Code
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70:	#include <iostream> using namespace std; const int ZELLEN = 1000; class gefaengnis { private: bool arrZellen[ZELLEN]; public: gefaengnis(); void begnadigung(); void verschliessen(int nr); void aufschliessen(int nr); void offeneZellen(); }; int main() { gefaengnis kerker; kerker.begnadigung(); cout << endl; kerker.offeneZellen(); return 0; } gefaengnis::gefaengnis() { for (int x=0;x<ZELLEN;x++) { this->arrZellen[x] = false; } } void gefaengnis::begnadigung() { for (int x=0;x<ZELLEN;x++) { for (int y=x;y<ZELLEN;y+=(x+1)) { if (this->arrZellen[y]) { this->verschliessen(y); } else { this->aufschliessen(y); } } } } void gefaengnis::verschliessen(int nr) { this->arrZellen[nr] = false; cout << "Zelle " << nr+1 << " wurde verschlossen." << endl; } void gefaengnis::aufschliessen(int nr) { this->arrZellen[nr] = true; cout << "Zelle " << nr+1 << " wurde aufgeschlossen." << endl; } void gefaengnis::offeneZellen() { int anzahl = 0; for (int x=0;x<ZELLEN;x++) { if (this->arrZellen[x]) { cout << "Zelle " << x+1 << " ist offen." << endl; anzahl++; } } cout << endl << anzahl << " Zellen sind offen." << endl; }

C++-Code

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:

#include <iostream>
using namespace std;
 
const int ZELLEN = 1000;
 
class gefaengnis {
 
  private:
    bool arrZellen[ZELLEN];
 
  public:
    gefaengnis();
    void begnadigung();
    void verschliessen(int nr);
    void aufschliessen(int nr);
    void offeneZellen();
 
};
 
int main() {
 
  gefaengnis kerker;
 
  kerker.begnadigung();
  cout << endl;
  kerker.offeneZellen();
 
  return 0;
 
}
 
gefaengnis::gefaengnis() {
  for (int x=0;x<ZELLEN;x++) {
    this->arrZellen[x] = false;
  }
}
 
void gefaengnis::begnadigung() {
  for (int x=0;x<ZELLEN;x++) {
    for (int y=x;y<ZELLEN;y+=(x+1)) {
      if (this->arrZellen[y]) {
        this->verschliessen(y);
      } else {
        this->aufschliessen(y);
      }
    }
  }
}
 
void gefaengnis::verschliessen(int nr) {
  this->arrZellen[nr] = false;
  cout << "Zelle " << nr+1 << " wurde verschlossen." << endl;
}
 
void gefaengnis::aufschliessen(int nr) {
  this->arrZellen[nr] = true;
  cout << "Zelle " << nr+1 << " wurde aufgeschlossen." << endl;
}
 
void gefaengnis::offeneZellen() {
  int anzahl = 0;
  for (int x=0;x<ZELLEN;x++) {
    if (this->arrZellen[x]) {
      cout << "Zelle " << x+1 << " ist offen." << endl;
      anzahl++;
    }
  }
  cout << endl
       << anzahl << " Zellen sind offen." << endl;
}