Using your Head is Permitted

July 2007 solution

Part 1:

If the i'th digit of n is d, then the i'th digit of 2n is either 2d mod 10 or 2d+1 mod 10. This means that, for example, if the i'th digit of n is either 2 or 7, the i'th digit of 2n must be either 4 or 5. The converse is also true: if the i'th digit of 2n is either 4 or 5, the i'th digit of n must be either 2 or 7. The total number of 2's and 7's in n must therefore equal the total number of 4's and 5's in 2n. If n and 2n were digit anagrams of each other, this would have lead to the following equation:

#2+#7=#4+#5

where #d indicates the number of appearances of the digit d in n. There are 4 other equations of a similar nature that can be formulated for the other digits. Similarly, we can count the number of places where there was a carry between digits. A carry occurs in every digit of n that is greater or equal to 5. On the other hand, only in those places where there was a carry will the next digit in 2n be odd. This would have lead to the equation

#5+#6+#7+#8+#9=#1+#3+#5+#7+#9

if n and 2n were digit anagrams of each other.

In part 1 of the riddle, it is n and 2n-1 that are anagrams, but we also know that n's least significant digit is 3, meaning that by subtracting one we are, in effect, making the number of "6" digits smaller by one and the number of "5" digits larger by one on the right-hand-side of the equations. Ultimately, we reach the following set of linear equations:

A: #0+#5=#0+#1
B: #1+#6=#2+#3
C: #2+#7=#4+#5-1
D: #3+#8=#6+#7+1
E: #4+#9=#8+#9
F: #5+#6+#7+#8+#9=#1+#3+#5+#7+#9-1

Consider, for example, the linear combination D+F-A-C-E of these equations. It yields

3*#8-1=#2+2*#7

If there were no "8"s in n, this equation would have indicated that either the number of "2"s or the number of "7"s is negative, which is, of course, impossible.

Part 2:

There are many ways of solving this part. The following solution has the advantage of providing a closed-form formula for k, but its solutions are typically much larger than the necessary minimum.

If n and 2n are digit anagrams of each other, there are several ways of finding from them new number pairs, l and 2l, that also satisfy that l and 2l are digit anagrams. For example, one can add zero digits between any two digits of n that don't have carry between them when multiplied by two. Alternatively, one can add a "9" between any two digits that do pass a carry digit between them. Finally, one can concatenate the digits of any two solutions to get a new valid solution.

Of these, we will consider multiple concatentations of the same solution and adding a zero in the place of the least significant digit, both of which cause the original number to be multiplied by a known factor.

We'll begin with the arbitrarily chosen solution n=125874.

Note that for any integers a≥0 and b>0, n 10^a (1000000^b-1) / 999999 is a number that becomes an anagram of itself when multiplied by two. Now, let us divide m into three parts: m=2^t 5^f r, where r is divisible by neither 2 nor 5. Clearly, if a=max(t,f) then 10^a is a multiple of 2^t 5^f. If r=1, we can choose k=n 10a/m and we are done. Otherwise, let us use Euler's theorem, which states that for any relativley prime x and y, x^φ(y)=1 (mod y), where φ denotes Euler's phi function. So, choosing x=1000000 and y=999999 r, we get 1000000^{φ(999999 r)}=1 (mod 999999 r). Alternatively, choosing b=φ(999999 r), we get that (1000000^b-1) is divisible by 999999 r and that (1000000^b-1) / 999999 is divisible by r. Therefore, n 10^a (1000000^b-1) / 999999 is a multiple of m and choosing k=n 10^a (1000000^b-1) / (999999 m) yields a valid solution.

Back to riddle

Back to main page