Maths Olympiad Prep

Library / /34 of 42

Algebra Difficulty 6.6 National olympiad Prove it Ireland

The equation AB×CD=EFGHAB \times CD = EFGH, where each of the letters A,B,C,D,E,F,G,HA, B, C, D, E, F, G, H represents a different digit and the values of A,CA, C and EE are all non-zero, has many solutions, e.g. 46×85=391046 \times 85 = 3910. Prove that the largest value of EFGHEFGH for which there is a solution, is 72×95=684072 \times 95 = 6840.

Solution

We cannot have B=0B = 0 or D=0D = 0, as this would imply H=0H = 0. Similarly, we cannot have B=1B = 1 or D=1D = 1, as this would imply H=DH = D or H=BH = B. For a solution EFGHEFGH to be bigger than 68406840 one of the numbers needs to be greater than 8686 because otherwise the product would not exceed 7986=679479 \cdot 86 = 6794. If we assume AB<CDAB < CD then CDCD needs to be one of the following numbers 87,89,92,93,94,95,96,97,9887, 89, 92, 93, 94, 95, 96, 97, 98.

For each of these we can find the possible values of ABAB which would make the product greater than 68406840, i.e. we work with the inequality
CD>AB6840CD. CD > AB \geq \left\lfloor \frac{6840}{CD} \right\rfloor .
For C=8C = 8 we need to have AB<80AB < 80. If CD=87CD = 87 we even need to have AB<70AB < 70 to avoid repeated digits. But 7087<7090=6300<684070 \cdot 87 < 70 \cdot 90 = 6300 < 6840. If CD=89CD = 89, we get 6840CD=77\lfloor \frac{6840}{CD} \rfloor = 77 and none of 77,78,7977, 78, 79 is possible for ABAB because of repeated digits.

Note that when AB<70AB < 70 we have AB×CD<7098<7000AB \times CD < 70 \cdot 98 < 7000 and E=6E = 6 whenever AB×CD>6840AB \times CD > 6840. Hence, we need to have AB72AB \ge 72 to avoid repeated digits. Suppose now that CD92CD \ge 92, then A=7A = 7 or A=8A = 8.

If A=7A = 7, we have AB×CD<8098<8000AB \times CD < 80 \cdot 98 < 8000 which implies that E=6E = 6 whenever we have a solution with AB×CD>6840AB \times CD > 6840. This implies
72AB7000CD. 72 \leq AB \leq \left\lfloor \frac{7000}{CD} \right\rfloor.
We now list all possibilities in a table where we have excluded some by keeping in mind E=6E = 6 and by checking the last digits.

CD9293949598
7000/CD7675747371
AB75747372
AB7472

For example, when CD=92CD = 92 we excluded AB=73AB = 73 because the last digit of the product would be 66. We excluded CD=96CD = 96 and CD=97CD = 97 because E=6E = 6 and A=7A = 7. We now check that none of these possibilities leads to a solution. Indeed,
7592=690075 \cdot 92 = 6900
7492=680874 \cdot 92 = 6808
7493=688274 \cdot 93 = 6882
7394=686273 \cdot 94 = 6862
7294=676872 \cdot 94 = 6768
do not give solutions, except of course for 7295=684072 \cdot 95 = 6840.

If A=8A = 8, we have AB×CD<9098<9000AB \times CD < 90 \cdot 98 < 9000 and AB×CD8292=7544AB \times CD \geq 82 \cdot 92 = 7544 which implies that EE must be 77. As FF can now be at most 66, we actually have AB×CD<7700AB \times CD < 7700, hence
82AB7700CD. 82 \leq AB \leq \left\lfloor \frac{7700}{CD} \right\rfloor.
Because 9482=770894 \cdot 82 = 7708, the only values left for CDCD are 9292 and 9393. If CD=93CD = 93, 7700/93<837700/93 < 83 and the only possibility is AB=82AB = 82. But 8293=762682 \cdot 93 = 7626, no solution. If CD=92CD = 92, AB82AB \neq 82 and 7700/92<847700/92 < 84, hence ABAB could only be 8383. But 8392=763683 \cdot 92 = 7636. Thus 68406840 is the largest possible EFGHEFGH.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.