7. (Grid Coverage) Consider the x-y plane that represents R 2 . Let P = {(x, y) : x, y N, x + y p} be the set of p-relevant positions. Michael (for his homework) needs to cover all p-relevant positions. The constraint is that Michael is only allowed to use lines (for example, no circles may be used) to cover these positions. Answer the following questions to eventually develop an efficient covering scheme for Michael :

(a) Count the number of pairs (a, b) N 2 satisfying a + b = k (for a fixed k N).

(b) Given a fixed value of p, how many positions must Michael cover? (in other words, what is |P|?)

(c) Prove that covering all p-relevant positions will require using at least (p + 1) lines (for every p N).

(d) Can you provide an efficient strategy for Michael to cover all p-relevant positions? Efficiency here