7
$\begingroup$

Find the largest integer that is a product of three-digit number and a one-digit number and also a product of two two-digit numbers.

For example, 200 x 1 = 10 x 20. Of course, 200 is not the largest.

$\endgroup$
  • 4
    $\begingroup$ 3d x 1d = 2d x 2d; d = 0 $\endgroup$ – Avigrail Jan 29 '15 at 14:34
  • $\begingroup$ @Avigrail You're right :-) $\endgroup$ – P.-S. Park Jan 29 '15 at 14:35
9
$\begingroup$

$8928 = 992 \times 9 = 96 \times 93$.

Explanation:

The only way to get to a number larger than $8000$ is if the number is of the form $(100-n)(100-m)=9(1000-k)$. The last two digits of the result equal minus a multiple of $9$ modulo $100$: $19$, $28$, $37$, $46$, $55$, $64$, $73$, $82$, or $91$. The smallest number in this list that occurs in the standard multiplication tables is $28$. So, the solution sought is $n=4$, $m=7$ and $100-9k=28$ or $k=8$.

$\endgroup$
  • $\begingroup$ So the second smallest is $n=1, m=19$, which results in $81 * 99 = 8019 = 9 * 891$? $\endgroup$ – durron597 Jan 29 '15 at 18:18
  • $\begingroup$ @durron597 - for the above argument to hold, $m$ and $n$ need to be single-digit numbers. $\endgroup$ – Johannes Jan 29 '15 at 19:13
  • $\begingroup$ So the second smallest is $8464=92*92=9*940$ cos $37,46,55$ can't be expressed as the product of two one digit numbers but $64$ can. Beyond that, this argument doesn't hold and it can be that the third is indeed $8019$ but that would require a different proof. $\endgroup$ – chx Jan 29 '15 at 20:17
  • $\begingroup$ @chx except that $9 * 940 = 8460$, not $8464$. However, $64 = 4 * 16 \rightarrow 96 * 84 = 8064 = 9 * 896 > 8019$ $\endgroup$ – durron597 Jan 30 '15 at 13:10
10
$\begingroup$

8928 = 992 * 9 = 96 * 93
9 - is obviosly largest 1-digit number, so we need to maximize 3-digit number so that their product can be a product of two 2-digit numbers.
Candidates are 993, 994, 995, 996, 997, 998, 999.
Let's find divisors of their products with 9 to show that they can't be products of 2-digit numbers. Write them in a row and in second row in reversed order. Example for 9*993:
1, 3, 9, 27, 331, 993, 2979, 8937
8937, 2979, 993, 331, 27, 9, 3, 1
Now it's easy to see that it cannot be product of 2-digit number (there will be two 2-digit numbers one above second if it is possible). In same way you check other candidates (not showing here, because long lists of divisors).

$\endgroup$
7
$\begingroup$

It took just a couple of minutes to come up with a program that quickly calculates this. It takes about 0.2 seconds to run. The variables I use are simply A*B=C*D and the for loops take care of the number of digits in each variable. Here's the output:

Largest Product = 8928
Largest A = 992
Largest B = 9
Largest C = 93
Largest D = 96

Here's the C# code:

static void Main(string[] args)
{
    int largestProduct = 200;
    int[] largestABCD = { 200, 1, 10, 20 };

    for(int a = 100; a <= 999; a++)
    {
        for(int b = 1; b <= 9; b++)
        {
            int product1 = a * b;

            for(int c = 10; c <= 99; c++)
            {
                for(int d = 10; d <= 99; d++)
                {
                    int product2 = c * d;
                    if(product1 == product2)
                    {
                        if (product1 > largestProduct)
                        {
                            largestProduct = product1;
                            largestABCD[0] = a;
                            largestABCD[1] = b;
                            largestABCD[2] = c;
                            largestABCD[3] = d;
                        }
                    }
                }
            }
        }
    }

    Console.WriteLine("Largest Product = " + largestProduct.ToString());
    Console.WriteLine("Largest A = " + largestABCD[0].ToString());
    Console.WriteLine("Largest B = " + largestABCD[1].ToString());
    Console.WriteLine("Largest C = " + largestABCD[2].ToString());
    Console.WriteLine("Largest D = " + largestABCD[3].ToString());

    Console.ReadLine();
}

I could probably come up with some optimizations for this code. I could constrain the D loop counter. Or I could break out of a loop once product2 is greater than product1. But the code runs so fast that it doesn't matter.

$\endgroup$
  • $\begingroup$ The problem with writing software to solve these sorts of problems is that they does not scale to larger problems well, whereas more mathematical approaches do. $\endgroup$ – BlueRaja - Danny Pflughoeft Jan 29 '15 at 22:17
2
$\begingroup$

I have a simpler way to get to the answer. Clearly, if the 1 digit number is $8$, the highest possible product will be less than $8000$ because $8 * 999 < 8000$. Therefore, assume the 1 digit number is $9$.

This means the product of the two 2-digit numbers must, between them, one must be divisible by $9$, or both must be divisible by 3.

One number is divisible by 9:

$$ \frac{99 * (99, 98, 97, 96, 95, 94, 93, 92, 91, 90)}{9} \rightarrow \\ (1089, 1078, 1067, 1056, 1045, 1034, 1023, 1012, 1001, 990) $$

So the first solution candidate is $99 * 90 = 8910 = 9 * 990$.

Both numbers are divisible by 3:

$$ 99 * 96 \rightarrow 9504 \rightarrow 1056 * 9\\ 96 * 96 \rightarrow 9216 \rightarrow 1024 * 9\\ 96 * 93 \rightarrow 8928 \rightarrow 992 * 9 $$

Since $8928 > 8910$, we have our answer, and the second place answer.

These two processes can be continued to generate further answers.

  1. $99$ times any two digit below $90$ will also result in a valid answer.
  2. Any two multiples of 3 equal to or below $96$ and $93$ will also result in a valid answer.
  3. Of course, once we get under $8000$, the product no longer needs to be a multiple of $9$ as the 1 digit number doesn't need to be $9$ anymore.

Exhaustive list of answers above $8000$:

$$ 8928 = 9 * 992 = 96 * 93 \\ 8910 = 9 * 990 = 99 * 90 \\ 8820 = 9 * 980 = 98 * 90 \\ 8811 = 9 * 979 = 99 * 89 \\ 8730 = 9 * 970 = 97 * 90 \\ 8712 = 9 * 968 = 99 * 88 \\ 8649 = 9 * 961 = 93 * 93 \\ 8640 = 9 * 960 = 96 * 90 \\ 8613 = 9 * 957 = 99 * 87 \\ 8550 = 9 * 950 = 95 * 90 \\ 8514 = 9 * 946 = 99 * 86 \\ 8460 = 9 * 940 = 94 * 90 \\ 8415 = 9 * 935 = 99 * 85 \\ 8370 = 9 * 930 = 93 * 90 \\ 8352 = 9 * 928 = 96 * 87 \\ 8316 = 9 * 924 = 99 * 84 \\ 8280 = 9 * 920 = 92 * 90 \\ 8217 = 9 * 913 = 99 * 83 \\ 8190 = 9 * 910 = 91 * 90 \\ 8118 = 9 * 902 = 99 * 82 \\ 8100 = 9 * 900 = 90 * 90 \\ 8091 = 9 * 899 = 93 * 87 \\ 8064 = 9 * 896 = 96 * 84 \\ 8019 = 9 * 891 = 99 * 81 \\ 8010 = 9 * 890 = 89 * 90 \\ $$

$\endgroup$
2
$\begingroup$

A longer, more thorough attempt at finding the solution without doing actual multiplications (except for $32\times32 = 2^5\times2^5 = 2^10 = 1024$). Hopefully it's easier to understand.

Notations:

$$\begin{align} ab &=\text{number with first digit}\ a\ \text{and second digit}\ b\\ a \times b &= a\ \text{multiplied by}\ b \end{align}$$

First phase is to observe that

$1d$ must be $9$.

The highest solution that can be made with $1d = 8$ is:

$8\times999 = 8 \times 111 \times 9 = 9 \times 888 < 9 \times 900 = 90 \times 90$
Ergo there are solutions with $1d = 9$ higher than can be made with $1d = 8$.

The important thing to note is that the number is $9*3d$, which is divisible by $9$.

The second phase is to determine/guess the number starting with the highest possible factors. Note that

$2d\times2d$ is divisible by $9$, so either one of the factors is divisible by $9$ ($99,90,$etc) or both factors are divisible by $3$ ($96,93,$etc)

This leads to the following cases (we stop when it's obvious we can't find better solutions):

$$\begin{align}99\times9x &= 9 \times 11 \times 9x \\&= 9 \times 9(9+x)x \\&\implies x = 0 \\&\implies\text{solution}: 99 \times 90 = 9 \times 990\\ 96\times96 &= 9 \times 32 \times 32 \\&= 9 \times 1024 \\&\implies\text{no solution}\\ 96\times93 &= 9 \times 32 \times 31 \\&= 9 \times (1024-32) \\&= 9 \times 992 \\&\implies\text{solution}: 96 \times 93 = 9 \times 992\\ 93\times93 &\ \text{irrelevant as it's smaller than}\ 96\times93\\ 90\times9x &\ \text{the best solution is obviously}\ 99\times90=9\ \text{discovered above}\end{align}$$

Obviously the best solution is

$$\boxed{9\times992=96\times93}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.