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+2d).

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+2e),… ,π(a+2ne),…

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+2ne)<π(a+2n+1e).

Now choose d=2ne 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+2d) < π(a+3d).

We will, in fact, show the stricter condition that they cannot satisfy

π(a+d) < π(a+2d) < π(a+3d).    (1)

Let len3(x) be the number of digits (trits) in the base-3 representation of x. We define π as follows.

π(x)=4 × 3len3(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


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.


Back to riddle

Back to main page