Guichard-Combinatorics-Graph-Theory · Problem 1.6.2

Fundamentals

Mathematics — Probability · pigeonhole-principle

Problem

Suppose that 501 distinct integers are selected from

1 \ldots 1000

. Show that there are distinct selected integers

a

and

b

such that

a \mid b

. Show that this is not always true if 500 integers are selected.

\Rightarrow