# Using your Head is Permitted

## December 2012 solution

Consider any specific choice of *f*. Let *G* be the undirected
graph that has [1,*n*]^{d} as its vertices
and edges from *X* to *Y* if ||*X*-*Y*||=1.
Let *G*_{f} be the directed
graph that has [1,*n*]^{d} as its vertices
and edges from *X* to *Y* if ||*X*-*Y*||=1 and
*f*(*X*)>*f*(*Y*).
Clearly, the value of *f*(*X*) for any *X* is bounded from above
by one more than *X*'s out degree in *G*_{f}. Summing this
over all vertices, we get the number of edges in *G*_{f} plus
the number of vertices in *G*_{f}, which is
certainly no greater than the number of edges plus the number of vertices
in *G*.

Thus, we have an upper bound for *g*(*d*,*n*) as one more than
the number of
edges in *G* divided by
*n*^{d}. This equals
1+*d*(*n*-1)*n*^{d-1}/*n*^{d}
= *d*(1-1/*n*)+1.

*g*(*d*), the limit when *n* tends to infinity, therefore has
*d*+1 as an upper bound.

We prove that this is also the lower bound by construction.

Let *H*(*X*) be the L_{1} distance from *X* to the
boundary of [1,*n*]^{d}.

Let *F*(*X*) be
Σ_{i=1...d} *i* *X*_{i} mod
(2*d*+1)+1, where *X*_{i} is the *i*'th coordinate of
*X*.

Let *f*(*X*) be the minimum between *H*(*X*) and
*F*(*X*). This function clearly satisfies the requirements.

For a large *n*, the effects of the boundary on the mean of
*f* are negligible, so we can consider *F* instead, even though
*F* does not satisfy the stipulated conditions at the boundaries.

The sum of *F*(*Y*) over any *X* and all its neighbors, except
at the boundaries, is Σ_{i=1...2d+1} *i*.
Summing
this over all *X* counts every *Y* (except at the boundaries)
2*d*+1 times. The mean is therefore
Σ_{i=1...2d+1} i/(2*d*+1)=*d*+1,
which is the same as the upper bound, therefore proving that the bound is
tight.

*g*(*d*)=*d*+1.

Back to riddle

Back to main page