Using your Head is Permitted

September 2017 riddle

Spoiler alert: The following riddle builds on ideas that were discussed in the riddles of December 2008 through February 2009 and their solutions. If you still mean to tackle those other riddles (and if you haven't yet, I recommend that you do; they are some of my favourite Using your Head is Permitted riddles), then you may want to hold on before you continue to this one. On the solution page I will assume familiarity with those older riddles.

Zhang Kaiyuan sent in the following wonderful question (Thanks Zhang!):

Given the usual complexity assumptions, can you sort n real numbers in O(n) time?

As usual: prove your answer.

List of solvers:

Lin Jin (8 September 00:01)
Uoti Urpala (9 September 12:42)

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!

Back to main page