Mumbai University > Computer Engineering > Sem 3 > Discrete Structures

Marks: 4 Marks

Year: Dec 2015

Any positive integer n can be written as n=2r m, where m is odd and r≥0. Let us designate m the odd part of n. If 11 numbers are chosen from the set

(1, 2, … ,20), then two of them must have the same odd part. This follows from the pigeonhole principle because there are 11 numbers, but only 10 odd numbers between 1 and 20 that can be odd parts of these numbers.

Let n1 and n2 be two chosen numbers with the same odd part. Then n1 =2r1 m and n2 = 2r2 m, for some r1 and r2. If $r_1≥r_2$ then n1 is a multiple of n2 ; otherwise n¬2 is a multiple of n1.