Question

Only need 2-5. Need it done ASAP, thank you in advance!!

Proofs 1) (1.7.16) Prove that if m and n are integers and nm is even, then m is even or n is even. * What is the best approach here, direct proof, proof by contraposition, or proof by contradiction why? * Complete the proof. 2) Prove that for any integer n, n is divisible by 3 iff n2 is divisible by 3. Does your proof work for divisibility by 4 - why or why not? Identify the kind of proof steps you used, and why. 3) Prove that V3 is irrational. What is the best proof approach to take, and why? 4) Prove that if you take 101 pigeons, and try to force them into 100 pigeonholes, there is some hole that has two pigeons. What is the best proof approach to take, and why? 5) Generalize the result of the previous problem: that if you take N pigeons and try to force them into M < N pigeonholes, some hole must have at least N/M many pigeons.

Answer 1

Solution 2:
Suppose 3 does not divide n. Then n can be written as 3a-1 or 3a-2 for some natural number a.
Case 1: n = 3a-1. Then n^2 = 9a^2-6a+1 which is not divisible by 3 since (3a^2-2a+1/3) is the sum of two natural numbers and a fraction, which is not a natural number.
Case 2: n = 3a-2. Then n^2 = 9a^2-12a+4 which is not divisible by three by similar reasoning. But we know n^2 is divisible by three so we have a contradiction. Therefore, n must also be divisible by 3.

Solution 3:

suppose 3–√ is rational, then 3√=ab for some (a,b) suppose we have a/b in simplest form.
3–√a2=ab=3b2
if b is even, then a is also even in which case a/b is not in simplest form.
if b is odd then a is also odd. Therefore:
ab(2n+1)24n2+4n+12n2+2n2(n2+n)=2n+1=2m+1=3(2m+1)2=12m2+12m+3=6m2+6m+1=2(3m2+3m)+1
Since (n^2+n) is an integer, the left hand side is even. Since (3m^2+3m) is an integer, the right hand side is odd and we have found a contradiction, therefore our hypothesis is false.

Solution 4 and Solution 5:
he pigeonhole principle is a simple idea with many applications. Imagine you own 101 pigeons. If
you have only 100 pigeonhole boxes in which to keep them, it is obvious that at least one of your 100
pigeonholes will need to contain two or more pigeons. In more general terms, we can say that if you
have n boxes and m objects with m> n, then at least one box will contain more than one object.
Same way if there are N pigeons and M pigeonholes such that M<N then some hole must have at least N/M many pigeons.