UPDATE (7 October): I thought it would take more time for all
three riddles to be solved, but in only 4 days we already have our first
solver. To keep it all interesting for just a bit more time, I decided to add
a bonus riddle. For an asterisk next to your name on Riddle 3, answer with
proof the following question: is there a solution using only o(N) guesses?
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 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:Continuing and concluding the cycle of theory-of-computation riddles that have been a constant feature of the site (see last month's riddle for more details):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:The following riddle comes from David Dowe (Thanks, David!), who asks:
For which values of To make matters more interesting, answer this question in the following two (unrelated) variants:
- If one can assume the axiom of choice, and
- If one can assume that there exists some open neighbourhood
*N*in ℝ^{n}in which the mapping from a point*x*to the direction of the line passing through*x*is a continuous mapping.
## Riddle 3:Kevin Hendrey found the following riddle:
"You and a friend are trying to get out of prison. The gaoler sends your friend
out of the room then shows you an
After this your friend is invited back into the room. Your friend is allowed to
point to
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( 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
Thanks for that, in advance. And for now, goodbye. |
## List of solvers:## Riddle 1:Bart De Vylder (3 October 23:09)Uoti Urpala (4 October 07:11) Lin Jin (19 October 17:11) ## Riddle 2:Uoti Urpala (4 October 07:11)## Riddle 3:Uoti Urpala (4 October 07:11)Yury Volvovskiy (11 October 00:00) Lin Jin (19 October 17:11) |

Elegant and original solutions can be submitted to the puzzlemaster at __riddlesbrand.scso.com__.
Names of solvers will be posted on this page. Notify if you don't want
your name to be mentioned.

The solution will be published at the end of the month.

Enjoy!