Maths Olympiad Prep

Library / /3 of 11

Combinatorics Difficulty 5.4 AIME, harder Prove it Estonia

Find the number of solutions of the equation ab=bc|a - b| = |b - c| in integers from 00 to 3636.

Solution

The equation ab=bc|a - b| = |b - c| is satisfied if and only if either ab=bca - b = b - c or ab=cba - b = c - b. The first equality is equivalent to a+c=2ba + c = 2b, the second is equivalent to a=ca = c.

To fulfill the condition a+c=2ba + c = 2b, the numbers aa and cc must have the same parity. Then their sum is even and bb lies between aa and cc, whence it also falls between the required bounds. There are 1919 possibilities for choosing aa or cc as an even number (0,2,,360, 2, \ldots, 36 are suitable) which gives 361361 possibilities in total. The number of possibilities to choose an odd number aa or cc is 1818 (1,3,,351, 3, \ldots, 35 are suitable) which gives 324324 possibilities in total. There are therefore 685685 triples satisfying a+c=2ba + c = 2b.

The number of triples satisfying a=ca = c is 13691369, since aa and bb can be chosen arbitrarily. There are 3737 solutions that satisfy both a+c=2ba + c = 2b and a=ca = c and hence being counted twice, since these two conditions hold simultaneously if and only if a=b=ca = b = c.

Consequently, the total number of solutions meeting the conditions of the problem is 685+136937685 + 1369 - 37 which equals 20172017.

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.