Divisible pairs and reduce to nothing

Divisible pairs

Task 1 supplies us with a list of integers and asks us to count the pairs selected from the list whose sums are divisible by a supplied integer.

The obvious way to do this is to generate all the pairs and check their divisibility by the given divisor. All the examples given include only unique positive integers. The task is not significantly different if zero and negative integers are included, but if the same integer appears more than once (eg list = 1, 2, 3, 3, divisor = 4) do we count distinct pairings (1 and the first 3, 1 and the second 3)  or merely distinct pairs (just 1 and 3).

Reduce to nothing

Task 2 as stated is impossible. Applying the supplied rules to any pair of starting x and y will never result in both x and y reaching zero, because:

• Each operation reduces either x and y and leaves the other unchanged
• So the values before the last operation would have to be (0, n) or (n, 0) where n > 0
• But that isn't possible because subtracting 0 from n cannot result in 0.

Inspection of the examples suggests that what was intended is that the process finishes when either of x and y reaches zero, and indeed if the rules are applied in the order specified, it will be x that does so.

But is it the case that all starting values of x and y will result in x == 0?  The answer is yes, because:

• After each operation, x + y always reduces, but cannot become negative
• There cannot therefore be more than x + y - 1 steps, even if each step only reduces x + y by 1
• Unless x or y is zero, it is always possible to make another step

The maximum number of steps (x + y - 1) will be required if the starting value of x or y is 1 and the minimum number (1) if the starting values of x and y are equal.