Skip to content
Get started

Picks that force a divisor

MediumCombinatorics4 min

You choose distinct integers from {1,2,…,30}\{1, 2, \dots, 30\}. What is the smallest number of picks that guarantees two of the chosen numbers satisfy "one divides the other"?

Show hints (3)+
  1. Write each number as a power of 2 times an odd number.
  2. Numbers with the same odd part divide one another.
  3. Look at the top half for a large divisor-free set.

Answer

Reveal answer →

16

Create a free account to see the full worked solution and track your progress.

Interview format: Trading Aptitude Tests, Systematic & Data-Driven Trading

Related questions