Using your Head is Permitted

To all my dear readers, whether you've been following this little site for years or whether you are seeing it now for the first time, I want to use this opportunity to thank you.

I am grateful that you have gone with me down this path where using one's head is permitted, where math is fun, exciting, challenging and unexpected, and where solving riddles can make one proud of one's achievement while also expanding one's horizons.

I tell you all this because I have decided that this occasion, "Using your Head is Permitted"'s 128'th month, should also be its last.

To the newcoming reader, my thanks come with 127 historical riddles that you are welcome to solve at your pleasure. The site will remain up and all riddles in it.

To the readers who have been here a while, my farewell this month consists of three riddles instead of one, to keep you busy for yet a while longer. You will recognise some of them as continuing long-running themes of the site.

Most especially, I would like to thank those readers who have helped me over the years, whether by sending a simple 'thank you' note of appreciation or by suggesting riddles of their own, or, indeed, solutions. This month's three riddles give representation to these, too.

I am closing the site down not for lack of riddles, lack of will, or lack of reader enthusiasm, but due to simple constraints of time. I have managed to continue this site for over a decade, never missing a publication date, through the birth of two children, a move to a new country, five jobs, a PhD, the writing and publication of a novel, and countless other major events. Now, however, with a third child on the way and a demanding new job, I feel I must throw in the towel. I can only hope you will not throw with it your enthusiasm for math, and will, rather, take this opportunity to make yourself your own puzzle-masters and come up, yourself, with bold new questions to ask.

The following are "Using your Head is Permitted"'s last three riddles.

Riddle 1:

Given the usual complexity assumptions, is there a program that solves the halting problem?

A program is considered to solve the halting problem if it can be given as input a software program, suitably encoded as a natural, and return for any such program whether it halts or not. The solver's computation may be long, but it must be finite in every case, whether the input program is a halting program or not. Famously, Alan Turing proved that no Turing machine can solve the halting problem, but Turing was not using the usual complexity assumptions.

Riddle 2:

For which values of n can the space ℝⁿ be represented as the direct union of a set of non-parallel, non-intersecting, straight lines?

To make matters more interesting, answer this question in the following two (unrelated) variants:

1. If one can assume the axiom of choice, and
2. If one can assume that there exists some open neighbourhood N in ℝⁿ in which the mapping from a point x to the direction of the line passing through x is a continuous mapping.

Riddle 3:

"You and a friend are trying to get out of prison. The gaoler sends your friend out of the room then shows you an N by N grid of light bulbs, some on some off. The gaoler then points to one of the light bulbs and you can choose whether or not to toggle it on/off. This process continues, with the gaoler pointing to a light bulb and letting you toggle its state if you wish, until the gaoler has pointed to all but one of the lights. Now, the gaoler may choose to toggle the state of the 'missed' light bulb but also might not.

After this your friend is invited back into the room. Your friend is allowed to point to N of the light bulbs and if the 'missed' light bulb is among them you both get to go free. Devise a strategy."

Kevin's own gaoler, however, is tougher than this riddle's original gaoler, and to solve this riddle you'll be required to answer whether such a strategy exists if the number of guesses your friend is allowed is O(N) with a multiplicative constant α<1 (i.e., if it is αN+o(N) for α<1).

Thanks, Kevin!

As usual: prove all your answers.

As every month, your are welcome to send in your solutions. Separate solver lists will be kept for each riddle. At the end of the month, the official solution will be posted (along with some more credits and thank yous) but no new riddle will join it.

If you want to show your appreciation of this 10+ year effort of maintaining the "Using your Head is Permitted" site, my preferred way for you to do it would be if you purchased a copy of Valkyries, my (rather well reviewed) science fiction novel, which in itself was a 10+ year effort. For you this would be a $3 token of appreciation, and for me it would mean the world. (And if you want to take the time to read it and leave a review, that would of course be even better.)

Thanks for that, in advance.

And for now, goodbye.

List of solvers:

Riddle 1:

Riddle 2:

Riddle 3: