Problem 1 (20 pts.) Expected Time: 1-2 hours. Similar to: Tutorial 6 Problem 3, Claims in Pigeonhole Principle lecture Type of Practice: Modify Existing Proof to Prove a Similar Claim. This problem asks you to construct a proof by Pigeonhole Principle by modifying the proof of a very similar result. (a) (16 pts.) Use the Pigeonhole Principle to fill out the following proof of the claim below: Claim. Vw, I, y, z EZ: 3 | (w - y)(w - z)(x - w)(x - y)(x - =)(y - =). Proof. We will prove this claim using the Pigeonhole Principle. . Let the pigeons (A) be the set . Let the pigeonholes (B) be the set . Let f : A -+ B be defined by f (a) := Note that f is a well-defined function: (1) for any pigeon a E f(a) = is computable because (2) for any pigeon a E if = b and = c then b = c, because (3) for any pigeon a E f(a) = is within the codomain because Mathematical Statement Reason this Statement is True (From the Approved List) A = because A = B = because B = A JBI 3a1, a2 E A : [(a, # a2) A (f (a1) = f(a2))] (i.e. pigeons an * az with same pigeonhole) by the def of A and f 3| (w - y)(w -=)(r - w)(x - y)(x -=)(y-=) (b) (4 pts.) Would the result still hold if we removed one of the terms? E.g. Claim 2. Vw, r, y, Z E Z, we have 3 | (w - 2)(x - w)(x - y)(x - 2)(y - z). If yes, make the modifications to your proof from (a). If not, clearly indicate the first line of your proof that would break (if you were to remove the (w - y)), explain why it would break, and provide a counter-example to prove the claim no longer holds