In this sentence the number of occurrences of 1 is 2, of 2 is 3, of 3 is 2, of 4 is 1.
This self-referential, true sentence is a variant of a puzzle attributed to the logician Raphael Robinson, popularized in Douglas Hofstadter’s book Metamagical Themas. In the book the puzzle appears in the following form:
Fill in the gaps such as to make the sentence true:
In this sentence the number of occurrences of the digit 0 is __, of digit 1 is __, of digit 2 is __, ..., of digit 9 is __.
With some trial and error you can find two different solutions, and it has been shown that no other solutions are possible. The problem has also been studied using some theory from the field of dynamical systems. Here are two interesting links, both containing the solution of the puzzle.
In this post, however, I would like to look at a slightly different puzzle. Instead of counting digits, I am counting the numbers as indivisible units. If, for instance, “15″ appears in the sentence, I count it as “15″, not as one “1″ and one “5″. In this way the problem is independent of the base in which the numbers are represented.
In both of the following two puzzles the task is to fill in the gaps such as to make the sentences true. In the first sentence the values can be between 1 and n (including 1 and n), in the second sentence the values can be between 0 and n-1 (both included). For what values of n are the problems solvable? How many solutions are there?
In this sentence the number of occurrences of 1 is __, of 2 is __, ..., of n is __.
In this sentence the number of underlined occurrences of 0 is __, of 1 is __, of 2 is __, ..., of n-1 is __.
Think about the puzzles for some time, or scroll down for the solution. Let me know if you find a simpler solution. I also wrote a follow-up post, with a different variant of the problem.
It can be shown that the two problems are equivalent: let’s denote the numbers written in the gaps of the first sentence by f(1), …, f(n). It can be seen easily that f(1), …, f(n) form a solution for the first problem if and only if f(1)-1, …, f(n)-1 form a solution for the second problem. So it’s enough to look at the first puzzle only.
With some case-based analysis we can show that there is no solution for the cases n=1, n=2, n=3 and n=6.
For n=4, there are two solutions, the one given in the beginning of the post and the following: f(1)=3, f(2)=1, f(3)=3, f(4)=1.
For n=5, the solution is given by the sequence: f(1)=3, f(2)=2, f(3)=3, f(4)=1, f(5)=1 and it is unique. These can be verified manually.
For every n>=7, there is a solution, given by f(1)=n-3, f(2)=3, f(3)=2, f(n-3)=2, and f(k)=1, for every k other than 1,2,3, and n-3. Let’s prove that this is the only solution:
Suppose there is some other solution.
If f(1)=n-3, then f(n-3)>=2.
—> If f(n-3)=2, then we need f(2)>=3.
——> If f(2)=3, then we get the same solution.
——> If f(2)>3, then there exist distinct x and y (also different from n-3, 1 and 2), for which f(x)=f(y)=2, so we have a value different from 1 at places 1,2,x,y,n-3, which means that we don’t have enough places to put 1′s, to satisfy f(1)=n-3.
—> If f(n-3)>2, then we have some x (different from 1 and n-3), for which f(x)=n-3. But then there are n-4 places where we need to put x, again not leaving enough places to satisfy f(1)=n-3.
If f(1)>n-3, then f(f(1))>=2.
—> If f(f(1))=2, then we need f(2)>=3 and f(f(2))>=2. We ran out of places for 1′s, since 1,2,f(2) and f(1) are distinct and they map to values different from 1.
—> If f(f(1))>2, then there is some x (other than 1) with f(x)=f(1)>=n-2, which means that we need to fill at least n-3 places with the value x, not leaving enough place for the 1′s.
The interesting case remains when f(1)<n-3. This condition means that in at least 5 places we need to write a number different from 1.
Suppose there are exactly k places, corresponding to the indices x1, …, xk, where we have an entry different from 1. This means that f(x1), …, f(xk) are different from 1 and k>=5. Let x1=1, since we know that in place 1 we have an entry different from 1.
Observe that among f(x1), …, f(xk) there have to be exactly k-1 distinct elements. This is because we need a value different from 1 in all places 1, f(x1), …, f(xk), and unless there are exactly k such places, we reached a contradiction. Since we have k-1 distinct elements all different from 1, the maximum among them is at least k and the second largest element is at least k-1. This means that there is a number t different from 1, such that f(t)>=k-1, therefore, t appears as a count in at least k-2 places. If out of k counts we have k-2 equal, we cannot have k-1 distinct values, so we reached a blatant contradiction. Therefore this case is impossible and the solution given above is unique.