17 September 2013

# Puzzle time

Returning home from New York. Ergo puzzle time. Today’s is a simple yet challenging problem.

Think of the various pairs of two numbers you can make using the digits 1,2,3,4,5,6,7,8,9 (each used only once) e.g. (2345, 16789) or (743, 821569) and so on.

Which is the pair (of two numbers) has the maximum product value (compared to other pairs)?

Posted September 17, 2013 by Rajib Roy in category "Puzzles

1. By Sara Emily Bowling (Post author) on

2. By Antara Choudhuri (Post author) on

No limits for the number of pairs? It can be too many combinations!

3. By Rajib Roy (Post author) on

Yes. But which combination gives the highest product value (of those two numbers)

4. By Antara Choudhuri (Post author) on

I see… Lemme think…

5. By Subbu Subramanian (Post author) on

An intuitive guess..I have to chose between 9876 and 54321 and 98765 and 4321..Or may be 987654 and 321 too.

6. By Rajib Roy (Post author) on

You would be wrong in all those and also no posting answers in Comments section

7. By Mukund M Altekar (Post author) on

94321 and 8765

8. By Baishali Chakraborty (Post author) on

9. By Subbu Subramanian (Post author) on

Baishali .No… we have posted the wrong answers and misled others

10. By Baishali Chakraborty (Post author) on

According to Rajibda’s rule no answer (right/wrong) should be in comment section.

11. By Subbu Subramanian (Post author) on

students can be naughty..

12. By Rajib Roy (Post author) on

The answer to the puzzle is 9642 and 87531. While many came close, the correct answers were cracked by Bob and Subbu
If you want the methodical way to do it, I think the following should work:

Principle 1: For obvious reasons, the numbers will have descending order of digits (else, you can make the number itself bigger by rearranging the digits to make them descending and thus the product will be biggest).

So, we have one number starting with 9 and the other with 8.

Now let’s look at what to do with 7 and 6. Whether we arrive at 97 and 86 or 96 and 87, the sum is the same (183).

Principle 2: If you break a number into two parts, the product is higher when the difference between the parts is lower. So, if you break 10 into two parts, the product is highest when the two parts are 5 and 5 (difference 0). Product of 9 and 1 (with difference of 8) is less than product of 6 and 4 (with difference of 2). This can be proven algebraically too. (See below #1)

So, to break up 183, we are better off with 96 and 87 (lesser difference).

Now, take 5 and 4 and you come up with 964 and 875 (the other option will have greater difference).

Next take 3 and 2 and you come up with 9642 and 8753.

Now what to do with the 1? Go with 96421 and 8753 or 9642 and 87531? A quick multiplication – which can be proven algebraically (see below #2) will give you the answer.

Algebraic Proof #2
Given X and Y (X > Y) and having to add 1 to either gives you either 10X+1 and Y or X and 10Y+1
The products are 10XY+Y or 10XY+X.
Since X>Y, the second one is bigger. So add the 1 at the end of the lesser number.

Algebraic Proof #1
Let’s say the number is N and you break up it into x and (N-x).
The product is Nx – x(squared)
which is – ( x(squared) -Nx)
which is – (x(squared) – Nx + (N/2)(squared)) + (N/2)(squared)
which is (N/2)(squared) – (x – (N/2))(whole squared)
(N/2)(squared) is always positive.
the total becomes lower and lower as the (x-(N/2))(whole squared) becomes bigger and bigger.
That is true when x-(N/2) becomes bigger and bigger
That is true when you pick x further and further away from the midpoint.
(realize that the distance of x from midpoint is twice the difference between x and the other number N-x)
Ergo….

13. By Amitesh Mukherjee (Post author) on

My whole body was hurting after playing two sets with Anindya and now my head is starting to hurt, reading your solution to the puzzle. Need some Aspirin. 🙂

14. By Kuntal Sengupta (Post author) on

Classic Dynamic Programming from Algo 101 🙂

15. By Baishali Chakraborty (Post author) on

Ore baba!eto boro answer amar meyera je ki kore kare!! ora bollo oder ans naki almost close chilo, apni message diye chen. jak,apner puzzle solve kore jodi buddhi bare.

This site uses Akismet to reduce spam. Learn how your comment data is processed.