StartseiteMatherätselIm KerkerLösung

Lösung: Im Kerker

Rätsel einblenden

Lösung

Ausblenden

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 t1, der kleiner als die Wurzel der Zahl ist, einen zugehörigen Teiler t2 = n/t1, 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 (312 = 961). Folglich sind am Ende 31 Türen offen, so dass 31 Gefangene fliehen konnten.

Lösungssuche mit Hilfe eines Computerprogramms

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

  1. #include <iostream>
  2. using namespace std;

  3. const int ZELLEN = 1000;

  4. class gefaengnis {

  5.   private:
  6.   bool arrZellen[ZELLEN];

  7.   public:
  8.   gefaengnis();
  9.   void begnadigung();
  10.   void verschliessen(int nr);
  11.   void aufschliessen(int nr);
  12.   void offeneZellen();

  13. };

  14. int main() {

  15.   gefaengnis kerker;

  16.   kerker.begnadigung();
  17.   cout << endl;
  18.   kerker.offeneZellen();

  19.   return 0;

  20. }

  21. gefaengnis::gefaengnis() {
  22.   for (int x=0;x<ZELLEN;x++) {
  23.   this->arrZellen[x] = false;
  24.   }
  25. }

  26. void gefaengnis::begnadigung() {
  27.   for (int x=0;x<ZELLEN;x++) {
  28.   for (int y=x;y<ZELLEN;y+=(x+1)) {
  29.   if (this->arrZellen[y]) {
  30.   this->verschliessen(y);
  31.   } else {
  32.   this->aufschliessen(y);
  33.   }
  34.   }
  35.   }
  36. }

  37. void gefaengnis::verschliessen(int nr) {
  38.   this->arrZellen[nr] = false;
  39.   cout << "Zelle " << nr+1 << " wurde verschlossen." << endl;
  40. }

  41. void gefaengnis::aufschliessen(int nr) {
  42.   this->arrZellen[nr] = true;
  43.   cout << "Zelle " << nr+1 << " wurde aufgeschlossen." << endl;
  44. }

  45. void gefaengnis::offeneZellen() {
  46.   int anzahl = 0;
  47.   for (int x=0;x<ZELLEN;x++) {
  48.   if (this->arrZellen[x]) {
  49.   cout << "Zelle " << x+1 << " ist offen." << endl;
  50.   anzahl++;
  51.   }
  52.   }
  53.   cout << endl
  54.   << anzahl << " Zellen sind offen." << endl;
  55. }

Vielen Dank für folgende Lösung in MATLAB an Simon Soller:

  1. function Kerker()
  2.   % 0=Zelle geschlossen
  3.   % 1=Zelle offen
  4.   zellen = zeros(1000,1);
  5.   for i=1:1000
  6.   l=i;
  7.   while l<=1000
  8.   if( zellen(l,1)==0 )
  9.   zellen(l,1) = 1;
  10.   else
  11.   zellen(l,1) = 0;
  12.   end
  13.   l=l+i;
  14.   end
  15.   end
  16.   AnzahlZellenOffen = sum(zellen);
  17.   fprintf( 'Es sind %d Zellen offen.\n', AnzahlZellenOffen );
  18. end

Das Rätsel lässt sich noch viel kürzer in C++ lösen, wenn man auf die Objektorientierung verzichtet. Vielen Dank an Robert Haberlach für den folgenden Code:

  1. #include <iostream>
  2. #include <bitset>

  3. int main()
  4. {
  5.   std::bitset<1001> arr;
  6.   for( std::size_t i = 1; i != arr.size(); ++i )
  7.   for( std::size_t c = i; c < arr.size(); c += i )
  8.   {
  9.   arr.flip(c);
  10.   std::cout << "Zelle " << c << " wurde "
  11.   << (arr[c]? "auf" : "zu") << "geschlossen!\n";
  12.   }
  13.   std::cout << arr.count();
  14. }