Startseite → Matherätsel → Im Kerker → Lösung
Lösung: 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 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 Java:
- import java.util.Arrays;
- public class Prison {
- public static void main(String[] args) {
- final int numberOfCells = 1000;
- Prison prison = new Prison(numberOfCells);
- for (int i = 0; i < numberOfCells; i++) {
- for (int j = i; j < numberOfCells; j += i + 1) {
- prison.toggleLock(j);
- }
- }
- System.out.println("Number of unlocked cells:");
- System.out.println(prison.getNumberOfUnlockedCells());
- }
- private final Cell[] cells;
- public Prison(int numberOfCells) {
- this.cells = new Cell[numberOfCells];
- for (int i = 0; i < numberOfCells; i++) {
- this.cells[i] = new Cell();
- }
- }
- public void toggleLock(int cellNumber) {
- this.cells[cellNumber].toggleLock();
- }
- public long getNumberOfUnlockedCells() {
- return Arrays.stream(this.cells)
- .filter(cell -> !cell.isLocked())
- .count();
- }
- }
- public class Cell {
- private boolean locked;
- public Cell() {
- this.locked = true;
- }
- public void toggleLock() {
- this.locked = !this.locked;
- }
- public boolean isLocked() {
- return this.locked;
- }
- }
Vielen Dank für folgende Lösung in MATLAB an Simon Soller:
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:
- #include <iostream>
- #include <bitset>
- int main()
- {
- std::bitset<1001> arr;
- for(std::size_t i = 1; i != arr.size(); ++i)
- {
- for(std::size_t c = i; c < arr.size(); c += i)
- {
- arr.flip(c);
- std::cout << "Zelle " << c << " wurde "
- << (arr[c]? "auf" : "zu") << "geschlossen!\n";
- }
- }
- std::cout << arr.count();
- }