Using your Head is Permitted

Again, thank you very much, Li Li.

Dear readers,

Thank you all for reading Using your Head is Permitted, and for sending in your riddle suggestions and your solutions. Using your Head is Permitted has published its one hundredth riddle last month, and I wanted to celebrate this "centenary" by mentioning some of what came out of the site over the years.

First off, as you know, Using your Head is Permitted is open to all, and requires only a desire to use one's head and tackle interesting mathematical problems. Those of you who have been listed on the site as solvers know that I ask solvers where they are from and what their mathematics background is. Turns out that a love of mathematics is global, and does not depend on what education you may have had. UyHiP solvers come from all over the world and from all walks of life. Some are high school students, others -- pre-eminent professors. Some are professional mathematicians or physicists, others journalists or career soldiers or retirees. The same can be said for the group of people who have sent me riddles during this time, to all of whom I owe a big thank you.

In other words, love of working out puzzles of the mind is universal across ages, disciplines, education and origin. (The only place where I see a major skew beyond what is explainable by unrelated factors is in gender bias. Among the site's triple-digit number of distinct solvers, virtually all are male. I can only conclude that female readers tend to not send in their solutions. So, consider this a call-out to all you women readers out there: let your voices be heard!)

Academically, the site has kept a high standard, and many of the riddles presented here ultimately found their way, in one roundabout way or another, to publication in high ranking journals. Here are some examples:

• Among the site's first riddles, in October 2007, was a question about jigsaw puzzles, a theme that later repeated itself in the July and September 2014 riddles. The October 2007 riddle was recently published in the "Fun With Algorithms" 2014 conference. The later riddles were published in Theoretical Computer Science.
• Between December 2008 and February 2009 the site ran three riddles to do with the theory of computation, and specifically with computations over integers. These ultimately found their way into publications in Information Processing Letters, Information and Computation and Acta Informatica.
• The April 2010 riddle on "Self Assembled Numbers" began for me a sustained interest in this topic, ultimately leading up to a publication in Discrete Applied Mathematics.
• The 75th anniversary riddle, published May 2013 and inspired by a series of papers by Tanya Khovanova, Konstantin Knop, Alexey Radul and Joel Brewster Lewis, was another that sparked a sustained interest in me. Improvements over the solution published in May 2013 that I managed to reach have since appeared in Discrete Mathematics, The Electronic Journal of Combinatorics and The Australasian Journal of Combinatorics.
• My favourite case of a publication that followed a UyHiP riddle is
  Angel, O., Holroyd, A.E., Soo, T.. Deterministic thinning of finite Poisson processes. Proc. Amer. Math. Soc., 139:707-720, 2011.
  Angel et al. worked on this problem way back in 2008 and it inspired a riddle that they sent me, which was published March 2009. However, the UyHiP solution to the riddle (which forms a small part in the larger problem of Poisson thinning) turned out to have some properties that were preferable to Angel et al.'s original solution, so they adopted it for the final paper and were able to use it to improve their results. Sweet!

And, of course, many (if not most) of UyHiP's 100 riddles bring to bear some existing mathematical theory. I did my best to mention this explicitly on the solution pages, so you, dear readers, can follow up on the state-of-the-art of the problem-space and its solutions. (And where I didn't have good references, I must thank the readers who were able to track down problems to their origins, who sent me the relevant information and links. It's great to see that you, readers, care as much about the quality of the mathematical material presented here as I do.)

Believe me, when I started this journey, back in 2007, I had no idea any of this was going to happen.

But enough self-congratulations. On to the riddle.

I had the tough duty to decide on a single riddle, from all the suggestions you have been sending me over the past two months, to be the 100'th-anniversary riddle.

The winning riddle is one sent to me by Radu-Alexandru Todor. Many thanks, Radu, and congratulations! Radu asks:

Let a natural n be called a subset sum of a set S if there is a subset of the elements of S that sums up to n. Critically, no element of S can be used more than once.

Let S_p,q={p^xq^y | x,y∈ℤ^≥0}.

Radu's question was: show that any natural except for finitely many is a subset sum of S_3,4. Answer this question for credit.

However, because this is the centenary riddle, I decided to post, additionally, something unusual for this site: a riddle for which I do not know the solution. This second riddle -- both for an asterisk next to your name and for explicit mention on the solution page -- is the following:

Is it true that for any co-prime p,q>1 the same holds, i.e. that any natural except for finitely many is a subset sum of S_p,q?

For this month's bonus riddle, feel free to search the Internet as much as you want and to collaborate, online or otherwise, as much as you want.

List of solvers: