**Source:**AUSTMS Puzzle Corner 35

**Problem:**

Call a nine-digit number flawless if it has all the digits from 1 to 9 in some order. An unordered pair of flawless numbers is called harmonious if they sum to 987654321. Note that (a, b) and (b, a) are considered to be the same unordered pair.

Without resorting to an exhaustive search, prove that the number of harmonious pairs is odd.

Update (23 Oct 2014):

**Solution:**Posted by me (Pratik Poddar) in comments!

Awesome puzzle!

ReplyDeleteProof at https://www.austms.org.au/Publ/Gazette/2014/May14/Puzzle.pdf

ReplyDeleteAs an example, one harmonious pair is given by (123456789, 864197532).

If we switch the order of the last two digits, the new pair (123456798, 864197523)

also happens to harmonious.

This is not a coincidence. In general, suppose we have a pair (m, n) with m = 100X + 10a + b, n = 100Y + 10c + d, where 2 ≤ a, b, c, d ≤ 9. In order for (m, n) to be harmonious, or m+n = 987654321, we must have a + c = b + d = 11. Then it is clear that the pair (m' , n') given by m' = 100X + 10b + a, n' = 100Y + 10d + c

also satisﬁes m' + n' = 987654321. Thus (m', n') is harmonious as well.

In most cases, the pairs (m, n) and (m', n') are diﬀerent. The notable exception is when we have m = n' and n = m'. This can only happen if A = C, a = d and b = c. It is easy to check (by working out the digits of A = C backwards) that the only pair satisfying these equalities is given by (493827156, 493827165).

Therefore the number of harmonious pairs must be odd.

Your statement "only pair satisfying these equalities is given by (493827156, 493827165)" isn't that state forward! Can u pls elaborate its proof.

Delete