# Using your Head is Permitted

## April 2013 solution

The answer is that the naturals are *k*-resistant for exactly
*k*∈{1,2}.
We first note that the *k*-resistance property is monotone. That is, if
the naturals are *k*-resistant and *l*<*k*, then they are
also *l*-resistant. For this reason, we only need to prove two claims,
and the rest follows. The claims are that the naturals are 2-resistant, and
that they are *not* 3-resistant.

We begin with the first of these. Let π∈Π_{ℕ}. We
claim that there exist *a*,*d*∈ℕ, such that

π(*a*) < π(*a*+*d*) < π(*a*+2*d*).
Let *a*=1. For every *i* in the range 1≤*i*≤π(*a*)
there is some *x* such that *i*=π(*x*). The set of all these
*x* is of finite size *a*, so it is well-defined to set *e* to
be their maximum.

The upshot of this definition is that the sequence

π(*a*+*e*), π(*a*+2*e*),…
,π(*a*+2^{n}*e*),…
contains only elements that are larger than π(*a*).

This is an infinite sequence of naturals. The naturals are well-ordered, so it
cannot be a monotone decreasing sequence. For some *n*, it will be true
that π(*a*+2^{n}*e*)<π(*a*+2^{n+1}*e*).

Now choose *d*=2^{n}*e* and we are done.

We now turn to the second claim, namely that the naturals are not 3-resistant.
For this, we need to find a particular π∈Π_{ℕ} for
which no *a*,*d*∈ℕ satisfy

π(*a*) < π(*a*+*d*) < π(*a*+2*d*)
< π(*a*+3*d*).
We will, in fact, show the stricter condition that they cannot satisfy

π(*a*+*d*) < π(*a*+2*d*)
< π(*a*+3*d*). (1)
Let *len*_{3}(*x*) be the number of digits (trits) in the
base-3 representation of *x*. We define π as follows.

π(*x*)=4 × 3^{len3(x)-1}-1-*x*.
To show that this is a bijection, simply consider all *x* values that share
a given trit length. The function maps this set exactly to itself, but in
decreasing order.

Because of this property, for any *a* and *d* to satisfy
Equation (1), the three elements being compared must each have a distinct
trit length.

This, however, is not possible. Because

*a*+3*d*<3(*a*+*d*),
the length of the third element can be no more than one trit longer than the
first element. As such, the second element must share the length of at least
one of its neighbors.

Q.E.D.

Back to riddle

Back to main page