Question

Show that from any subset of 51 numbers taken from {1, 2, 3, ..., 100}, there exists a pair of elements such that one divides another.

Answer 1

Consider the 50 odd numbers 1,3, 5, ..., 99.

For each one, form a box containing the number and all powers of 2 times

the number.

So the first box contains {1,2,4,8, 16,..}

the next box contains {3,6,12,24,48, ...}

Then among the 51 numbers chosen, the pigeonhole principle tells us that there are two that are contained in the same box. They must be of the form $2^{m} k$ and $2^{n} k$ with the same odd number k. So one will divide the other.

What is pigeonhole principle?

According to the pigeonhole principle, if n items are placed in m containers, with n > m, at least one container must contain more than one item.

For example, if you have three gloves (and none of them are ambidextrous/reversible), you must have at least two right-handed gloves or at least two left-handed gloves, because there are three objects but only two categories of handedness to put them into.

To learn more about pigeonhole principle from the given link

brainly.com/question/13982786

#SPJ4