Graph Coloring and Pigeonhole Principle
Added on 2020-04-21
4 Pages979 Words56 Views
|
|
|
Answers Question 1Let X be a non-empty set and it has a maximal element.Let s4 be the maximal element of X, then s≤s4 for all s∈X and if for any y∈Xwithy≥s4 then y = s4, We have the definition of supxs = least upper bounded of XThen, a ≤¿xs for all a ∈ XSince s4 is the maximal element with supxs ≥ s4.We get that; X4 = supxsUsing the principle of Pigeonhole Since there are 4 possible when an integer is divided by 4 that at least one of n+1 integer in the set, must have a remainder when divided 4, but if they have the same remainder when divided by 4, their difference is divisible by 4Hence in the set x1, x2, x3 and x4 there are one number xi and xj with i≠j that have the same remainder when they are divided by 4.Thus, there exist k, m, r ∈Nk,m,r,∈N with 0≤r≤4Such that;Xixj = 4k+ r =4 m +rXi = 4k+rxj = 4m+rIf we take their difference, we obtainXi – xj = (4k+r) – (4n+r) = 4k -4n = 4(k-m)Therefore; Xi – xixj – xj is divisible by 4Points to noteHence in the set x1, x2, x3 and x4 there are one number xi and xj with i≠j that have the same remainderwhen they are divided by 4.Thus, there exist k, m, r ∈Nk,m,r,∈N with 0≤r≤4Such that;
Xixj = 4k+ r =4 m +rXi = 4k+rxj = 4m+rIf we take their difference, we obtainXi – xj = (4k+r) – (4n+r) = 4k -4n = 4(k-m)Therefore; Xi – xixj – xj is divisible by 4I have used it to justify principle of Pigeonhole on testing if the set are divisible by any number, holding most on the difference at the end, with a common factor as shown, this will guarantee a clear demonstration of divisibility.Just like in the calculation Xi – xj = (4k+r) – (4n+r) = 4k -4n = 4(k-m) the solution is found to have a common factor of 4, meaning that it holds the divisibility of 4.
End of preview
Want to access all the pages? Upload your documents or become a member.