"Flawless Harmony" Puzzle

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!


Comments

  1. Alex4:08 AM, August 27, 2014

    Awesome puzzle!

    ReplyDelete
  2. Pratik Poddar4:06 PM, October 23, 2014

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

    As 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 satisfies m' + n' = 987654321. Thus (m', n') is harmonious as well.

    In most cases, the pairs (m, n) and (m', n') are different. 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.

    ReplyDelete
    Replies
    1. Yo!6:03 PM, October 25, 2014

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

      Delete

Post a Comment

Popular posts from this blog

Buying Dimsums

Source: Alok Goyal (Stellaris VP, Ex-Helion VC) puzzle blog Problem: A fast food restaurant sells dimsums in boxes of 7 and 3. What’s the greatest number of dimsums a person cannot buy. Generalize it for p and q where p and q are relatively prime. I loved the puzzle. Hope you enjoy it too.
Read more

Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions.  In total, Siddhant scores 25 out of 34.  Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34. Note that a) Vaibhav scores more than Siddhant b) Siddhant score better than Vaibhav in both individual topics -  5/6 > 20/25 and 20/28 > 6/9 How is it possible? 
Read more

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially) ...
Read more