Combinatorics and Graph Theory · Problem 1.6.2

Fundamentals — David Guichard

Mathematics — Combinatorics · 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.