# Show me where I have made a mistake in interpreting or solving this number puzzle

The following number puzzle was published in the Sunday Times on 25th August this year. It is credited to Danny Roth.

George and Martha have a book of puzzles numbered from 1 to 30. The solutions are also numbered from 1 to 30, but a solution number is not necessarily the same as the number of the puzzle. George and Martha have solved some of the puzzles. If you look at the number of the puzzle and the number of the solution, then the sum of the two is a perfect power of the difference of the two. George has added up the numbers of the solved puzzles and got a three-figure total. Martha has added up the numbers of the solutions of the solved puzzles and got a higher three-digit total. In fact her total used the same non-zero digits as George's, but in a different order. What (in increasing order) are the numbers of the solved puzzles?

I seem to have deduced that no solution exists. This indicates that I have probably either made a mistake in my reasoning, or misinterpreted some part of the question. Maybe someone can tell me which it is and what is the nature of my error. What follows is my reasoning.

Let $\mathbb{N}_{30}$ denote the set $\{1, 2, 3, \ldots, 30\}$. Let $f \colon \mathbb{N}_{30} \to \mathbb{N}_{30}$ be the permutation that takes each puzzle number to the number of the corresponding solution. We are given that for each $i \in \mathbb{N}_{30}$ there exists an integer $j$ such that $f(i) + i = |f(i) - i|^{j}$. Let $r \colon \mathbb{N}_{30} \to \mathbb{Z}$ be the function that takes each $i$ to its corresponding $j$.

1. For each $i \in \mathbb{N}_{30}$, we have $2 \leq f(i) + i \leq 60$. Immediate.
2. For each $i \in \mathbb{N}_{30}$, we have $f(i) \neq i$. Indeed, if $f(i) = i$ then every (well-defined) integer power of $|f(i) - i|$ is either 0 or 1. But this contradicts the lower bound in (1).
3. For each $i \in \mathbb{N}_{30}$, we have $|f(i) - i| \neq 1$. Indeed, if $|f(i) - i|$ is equal to 1 then so is its every integer power, and this again contradicts the lower bound in (1).
4. For each $i \in \mathbb{N}_{30}$, we have $2 \leq |f(i) - i| \leq 7$. That $|f(i) - i| \geq 2$ follows from (2) and (3). Suppose for a contradiction that $|f(i) - i| \geq 8$. We know that $r(i) \geq 2$ since $|f(i) - i|^{r(i)}$ is an integer, and greater than 1 (by the lower bound in (1)). Now $|f(i) - i| \geq 8^2 = 64$, which contradicts the upper bound in (1).
5. $f(1) = 3$, and $f(3) = 1$. By (4), $f(1)$ must be 3, 4, 5, 6, 7 or 8. The only one of these that satisfies the "perfect power" requirement is 3, so $f(1) = 3$. A similar argument establishes that $f^{-1}(1) = 3$.
6. No possible values for $f(2)$. By (4) and (5), $f(2)$ must be 4, 5, 6, 7, 8 or 9. None of these satisfy the "perfect power" requirement.
-
I think this perfect power property is only meant to hold for a subset of 'solved' puzzles, not for all of them –  Cocopuffs Aug 26 '13 at 21:51
I don't understand why $r(i)$ should be larger than $2$ ? –  Arnaud Aug 26 '13 at 23:05
I don't think I claim anywhere that $r(i)$ should be larger than 2. I claim in (4) that it should be greater than or equal to 2. In more detail: if $r(i)$ is negative then (given that $|f(i) - i| > 1$) it follows that $|f(i) - i|^{r(i)}$ is a non-integer. If $r(i) = 0$ then $|f(i) - i|^{r(i)} = 1$, which is less than the lower bound from (1). If $r(i) = 1$ then $|f(i) - i|^{r(i)} = |f(i) - i| = f(i) + i$. But it may be shown that this latter condition necessitates at least one of $i$ and $f(i)$ being zero, when by assumption each of them is positive. –  Hammerite Aug 26 '13 at 23:47
Okay, sorry, I was mistaken. –  Arnaud Aug 27 '13 at 11:42

Unless I've also misunderstood the task, there are at least two solutions:

sumQ: 112; sumA: 121
1 -> 3 (1 + 3 = 4 = 2^2 = |1 - 3|^2)
3 -> 5 (3 + 5 = 8 = 2^3 = |3 - 5|^3)
6 -> 10 (6 + 10 = 16 = 4^2 = |6 - 10|^2)
7 -> 9 (7 + 9 = 16 = 2^4 = |7 - 9|^4)
9 -> 7 (9 + 7 = 16 = 2^4 = |9 - 7|^4)
10 -> 6 (10 + 6 = 16 = 4^2 = |10 - 6|^2)
12 -> 15 (12 + 15 = 27 = 3^3 = |12 - 15|^3)
15 -> 17 (15 + 17 = 32 = 2^5 = |15 - 17|^5)
21 -> 28 (21 + 28 = 49 = 7^2 = |21 - 28|^2)
28 -> 21 (28 + 21 = 49 = 7^2 = |28 - 21|^2)

sumQ: 101; sumA: 110
5 -> 3 (5 + 3 = 8 = 2^3 = |5 - 3|^3)
6 -> 10 (6 + 10 = 16 = 4^2 = |6 - 10|^2)
7 -> 9 (7 + 9 = 16 = 2^4 = |7 - 9|^4)
9 -> 7 (9 + 7 = 16 = 2^4 = |9 - 7|^4)
10 -> 15 (10 + 15 = 25 = 5^2 = |10 - 15|^2)
15 -> 17 (15 + 17 = 32 = 2^5 = |15 - 17|^5)
21 -> 28 (21 + 28 = 49 = 7^2 = |21 - 28|^2)
28 -> 21 (28 + 21 = 49 = 7^2 = |28 - 21|^2)


This is the PERL program (I'm aware that it's messy and unoptimized) I used to solve this:

#!/usr/bin/perl

use strict;
use warnings;

sub min($$) { return _[0] < _[1] ? _[0] : _[1]; } sub max($$) { return $_[0] >$_[1] ? $_[0] :$_[1]; }

sub getPow() {
my ($x,$y) = @_;
my $t =$x;
my $p = 1; while ($t < $y) {$t *= $x;$p++;
}
return ($t >$x && $t ==$y ? $p : 0); } my$possibilities = {};

for my $i (1..30) { for my$j (max(1,$i-7)..min(30,$i+7)) {
my $diff = abs($i - $j); next if$diff <= 1;
push @{$possibilities->{$i}}, $j if getPow($diff, $i +$j);
}
}

my $candidates = [ keys %$possibilities ];
my $use = { map {$_ => 0 } @$candidates }; sub try { my$which = shift;

if ($which >= 0) { for my$c (reverse 0..scalar @{$possibilities->{$candidates->[$which]}}) { try($which - 1);
$use->{$candidates->[$which]} =$c;
}
return;
}

my $sumQ = 0; map {$sumQ += $_ } grep {$use->{$_} } @$candidates;
return if $sumQ < 100; my$sol = {};
my $used = {}; for my$i (sort { scalar @{$possibilities->{$a}} <=> scalar @{$possibilities->{$b}} } keys %$possibilities) { next unless$use->{$i}; my$j = $possibilities->{$i}->[$use->{$i} - 1];
if (!defined $used->{$j}) {
$used->{$j} = 1;
$sol->{$i} = $j; } }$sumQ = 0;
map { $sumQ +=$_ } keys %$sol; my$sumA = 0;
map { $sumA +=$sol->{$_} } keys %$sol;

if ($sumQ >= 100 &&$sumA > $sumQ && join("", sort split(//,$sumQ)) eq join("", sort split(//, $sumA))) { print "sumQ:$sumQ; sumA: $sumA\n"; for my$i (sort { $a <=>$b } keys %$sol) { my$j = $sol->{$i};
my $diff = abs($i - $j); my$sum = $i +$j;
my $p = getPow($diff, $sum); print "$i -> ", $j, " ($i + $j =$sum = $diff^$p = |$i -$j|^$p)\n"; } print "\n"; } } try($#\$candidates);

-
This is very nice, but it doesn't answer the question asked, which was what problems exist with my attempt at the problem. –  Hammerite Aug 26 '13 at 23:42
That was answered by @Cocopuffs in the comments, so I felt it was pointless to repeat. If you still don't understand, I can write how I understood it (and programmed it). –  Vedran Šego Aug 26 '13 at 23:44