Using your Head is Permitted

July 2015 riddle

UPDATE (8 July): The answer to the bonus riddle was found on the Internet by Li Li, and turns out to have quite a pedigree. Thank you so much for this, Li Li. It is greatly appreciated.

I'll publish the history of the riddle and its solution, as discovered by Li Li, on this month's solution. Now that this solution has been found, however, I am reinstating the usual restrictions regarding originality of solution. If you want to have your name with an asterisk this month, please solve the problem yourself.

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!
This is by no means an exhaustive list of examples, nor is this a bygone trend: several papers are in the works right now, based on material that has been published on the site, including papers related to riddles that were sent to me, which are now being written up by their inventors.

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 Sp,q={pxqy | x,y∈ℤ≥0}.

Radu's question was: show that any natural except for finitely many is a subset sum of S3,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 Sp,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:

Joseph DeVincentis (1 July 23:10)
Dan Dima (2 July 00:31)
Guangda Huzhang (2 July 01:42)
Uoti Urpala (3 July 05:21)
Harald Bögeholz (5 July 01:20)
Nis Jørgensen (7 July 23:59)
Li Li (*) (8 July 08:31)
Andreas Stiller (9 July 03:31)
Adrian Neacsu (14 July 01:43)
Oded Margalit (14 July 08:44)
Lorenzo Gianferrari Pini (20 July 22:01)
Daniel Bitin (21 July 19:07)

Elegant and original solutions can be submitted to the puzzlemaster at 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.


To solution

Back to main page