Maths Olympiad Prep

Library / /21 of 94

Number theory Difficulty 4.4 AIME Find the answer United States

Problem:

How many pairs of integers (a,b)(a, b), with 1ab601 \leq a \leq b \leq 60, have the property that bb is divisible by aa and b+1b+1 is divisible by a+1a+1?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:

The divisibility condition is equivalent to bab-a being divisible by both aa and a+1a+1, or, equivalently (since these are relatively prime), by a(a+1)a(a+1). Any bb satisfying the condition is automatically a\geq a, so it suffices to count the number of values ba{1a,2a,,60a}b-a \in \{1-a, 2-a, \ldots, 60-a\} that are divisible by a(a+1)a(a+1) and sum over all aa. The number of such values will be precisely 60/[a(a+1)]60 / [a(a+1)] whenever this quantity is an integer, which fortunately happens for every a5a \leq 5; we count:

a=1a=1 gives 30 values of bb;
a=2a=2 gives 10 values of bb;
a=3a=3 gives 5 values of bb;
a=4a=4 gives 3 values of bb;
a=5a=5 gives 2 values of bb;
a=6a=6 gives 2 values (b=6b=6 or 4848);
any a7a \geq 7 gives only one value, namely b=ab=a, since b>ab>a implies ba+a(a+1)>60b \geq a+a(a+1)>60.

Adding these up, we get a total of 106 pairs.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.