If n1 integers are chosen from the set 1232n where n is a po

If n+1 integers are chosen from the set {1,2,3,....,2n}, where n is a positive integer, must at least one of them be even? Why?

Solution

consider n positive integers {1,2,3,.....2n}

setup n pigeonholes 1,2,4,6,...2n+1 (all even numbers lie between 1&2n) where n is a positive integer

there exists atleast one of the even integer because,

each positive integer K>=2n has unique representation of the form 2^aj,where j belongs to{1,2,4,....2n+1} where a<=0

(by dividing 1 until the number becomes even number of times dividing by 1 is a so the resulting number is j)

put the number k into hole j

therefore,there exixts atleast one even integer