Question

Problem 13. (1 point) [3 Marks] Prove the following: Show that for any given 42 integers there exist two of them whose sum, or else whose difference, is divisible by 80.

Answer 1

v.e. Any no. when divided by 80 will have possible remainder r= {0, 1, 2, 3 ..., 78,793 every number can be written as e thee x = 0 mod 80 Remainder greater ar = 1 mod 80 than 40 can be wolten as ave eg. 433-37 x=78 mod 80 = -2mod 80 x=79 med to -1 med 80 in me duk 80 or Ij we take 40 integers then we can select unique 40 integers such that sum of any two integers / defference of any two integers is not civissble by 80. (All positive remainders) But, if we take 42 integers then by Pigeonhole principle: y either, there will be a negative renainder 2.) OR, there will be two integers with same positive remainder. Case I: There exist a negative remainder say uk where oc-k <-40 by Pigeonhole piniple there also exist

a positive renainder tk. i 2,5 se k mod 80 x = -K mod 80 txitx2= K+(-k) hod 80 x,+x₂ = O mod 80 i Sum two numbers is divisible by 80. of Case II: No negative remainder exists Then by pigeonhole principle, we can find two integers with some modulo remainder : 2,=k mod 80 X2= k mod so 72,- = krk mod 80 :. Difference of two integers is divisible by 80. Hence, Using Pigeonhole principle we can prove that is 42 integers are chosen then sum or difference of two integers will be divisible by 80. QED
Please let me know if you have any queries or require further explanation.