I was like a boy playing on the sea-shore, and diverting myself now and then finding a smoother pebble or a prettier shell than ordinary, whilst the great ocean of truth lay all undiscovered before me.
— Isaac Newton
Yet More Prisons
You, together with a finite number n-1 of other ideal mathematicians, have been arrested on a whim by a generic evil dictator and are about to be locked up in a prison. The prison is circular, with n identical windowless cells arranged in a ring around a central court. There are some problems with the lighting system – the light switch in each cell controls the light in the next cell clockwise around the ring. Even worse, electric power is only provided to the lights for one tenth of a second each night, just after midnight.The warden is worried that you might use the lights to communicate (very slowly), so he will very often rearrange the prisoners, moving them about between the cells in any way he chooses and having all the cells cleaned to prevent prisoners leaving messages for one another. He might do this every day. This will all be done in such a way as to keep you all in ignorance; you will never see each other or any part of the prison except the inside of the cells. You do not even know how many other mathematicians are to be locked up with you.
The warden visits you in your cell, and explains that if you are able to communicate despite these precautions he will consider you all worthy of release. At any time, any prisoner who believes he has discovered how many prisoners there are may petition the warden for release. That prisoner will be allowed one guess at the number of prisoners; if they guess correctly, then all the prisoners will be released, but if they guess incorrectly then all the prisoners will be executed.
You have been chosen to devise a strategy by means of which you will be able to discover the number of prisoners. You may compose a single email outlining your strategy, which will be passed to all the prisoners. However, your strategy must be foolproof, as the warden (who has a deep hatred of ideal mathematicians) will also read your email.
Is there a strategy which will guarantee your release? If so, give one. If not, why not?
Remark: This version was found on XKCD Wiki. I have written up a solution for this puzzle though the puzzle itself is phrased in a different way.
Solve ALL of the Mazes
You’re minding your own business in the Land of Geometry, when suddenly a stupid robot runs up to you with a pen and paper. “Quick!” it squeaks. “Can you give me directions through the Featureless Maze?” Oh, dear. This is the third time today a robot has mistaken you for one of the service staff here. Well, you’d rather not disappoint it.
Problem is, you don’t actually know the layout of the Featureless Maze. You do know this:
- The maze is a 2013 by 2013 square grid. Each square is either a floor or a wall. The start is in the top-left square, and the exit is in the bottom-right square.
- In the maze, the robot can only move up, down, left, and right – no diagonals, and especially no moving through walls. The maze is solvable, i.e. there is at least one path from the start to the exit.
- Because the robot is so stupid, it can only understand a list of arrows like “←↑↓→”. Upon entering the maze, the robot will blindly follow your directions, moving one square at a time in the direction of the next arrow on the list. If a move would make the robot run into a wall, it simply stays where it is that move. If the robot gets to the end of the list without finding the exit, it begins to cry.
[Medium] Can you provide a clever (and finite) list of directions so that, no matter what the layout of the maze is, the robot will always reach the exit at some point?
[Super Hard] Is there an even cleverer list of directions where, no matter what the layout of the maze is, the robot will always finish on the exit square? Fair warning: I’ve thought about this version for a bit and I don’t know the answer.
Remark: This version is found on XKCD Forum.
Transfinite Subway
There is a subway line from the airport to the Hilbert hotel which operates as follows: there is a station at each ordinal number, and every station is assigned a unique ordinal. The subway stops at each station, in order. At each station people disembark and board, in order, as follows: if any passengers are on the subway, exactly 1 disembarks, then \aleph_0 passengers board the subway.
Station 0 is at the airport, and the Hilbert hotel is at station \omega_1 (the first uncountable ordinal). The subway starts its journey empty. \aleph_0 passengers board the subway to the Hilbert hotel at the airport (station 0), and off it goes.
When the subway pulls up to the Hilbert hotel at station \omega_1, how many passengers are on it?
Remark: I heard this problem from Chris Lambie-Hanson at Carnegie Mellon University Maths Department Graduate Student Seminar.