Theorem: In any set of (n+1) distinct integers there exists two whose difference is divisible by n.
Proof: Each of these integers leaves a remainder between 0 and n-1 inclusive upon division by n. Since there are n possible remainders and (n+1) integers that means there exist two which have the same remainder by the PigeonHole Principle. So their difference is divisible by n. Theorem: Given any positive integer n there exists a positive number consisting of only 1's and 0's which is divisible by n. Proof: Construct the sequence of (n+1) integers: 1,11,111,....,111...1 By the first theorem two of these numbers have a difference divisible by n. That difference will be a number consisting of only 1's and 0's. On Mar 7, 1:17 pm, karthikeya s <karthikeya.a...@gmail.com> wrote: > A math problem: Prove that for all positive integer n, there exist at least > one positive integer whose digits are only 1s and 0s and is divisible by n. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
