Solution: 2015 Winter Final - 10
Author: Michiel SmidQuestion
Let $S$ be the set of ordered pairs of integers that is recursively defined in the following way:
- $(1,6) \in S$.
- If $(a,b) \in S$ then $(a+3, b+4) \in S$.
- If $(a,b) \in S$ then $(a+5, b+2) \in S$.
(a)
For every element $(a,b)$ in $S$, $a + b$ is divisible by 7.
(b)
None of the above.
(c)
For every element $(a,b)$ in $S$, $a + b$ is not divisible by 7.
(d)
$S = \{(a,b) : a > 0$ and $b > 0$ are integers and $a + b$ is divisible by 7$\}$.
Solution
The sum of 1 and 6 is divisible by 7.
Upon adding 3 and 4 to the total sum, it adds 7. This means it’s still divisible by 7.
Upon adding 5 and 2 to the total sum, it adds 7. This means it’s still divisible by 7.
As a result, every element (a,b) in S, a+b is divisible by 7