Using your Head is Permitted

December 2012 riddle

UPDATE (3 December): I received many solutions so far that handle the case of the infinite lattice. The case asked about here is the asymptotic case. You need to show a construction that works for an arbitrarily large but finite value of n, before you can take the limit.

Also, please note that solutions to the riddle presented here should be sent here, whereas solutions to the Ponder This portion of the riddle should be sent to Ponder This.

This month we continue in the tradition of joint riddles with IBM's Ponder This.

We describe a function, f from [1,n]d to the naturals that has the following property: if f(X)=x, then for every y in the range [1,x-1] there is a Y such that f(Y)=y and ||X-Y||=1.

Let g(d,n,f) be the mean of f's values over its entire domain.

Let g(d,n) be the maximum of g(d,n,f) over all possible choices for f.

Let g(d) be the limit of g(d,n) when n tends to infinity.

This month's riddle: calculate g(d).

Credit for inventing the riddle goes to Oded Margalit. An accompanying riddle, relating to a specialized version of this problem, appears in this month's Ponder This.

List of solvers:

Alex Wagner (5 December 03:44)
Dan Dima (5 December 06:39)
Radu-Alexandru Todor (5 December 07:46)
Deron Stewart (5 December 08:07)
Omer Angel (8 December 07:59)
Robin Ryder (10 December 02:31)
Colin Benner (10 December 09:27)
Daniel Bitin (13 December 02:24)
Todd Will (16 December 06:24)
Naftali Peles (17 December 07:26)
Øyvind Grotmol (20 December 00:01)
Luke Pebody (20 December 18:25)
Wenqi Zhang (20 December 19:00)
Tomek Czajka (27 December 08:53)

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