Quoto

Learn / Library / Combinatorics

Forced divisibility

CombinatoricsHard

What is the smallest such that every set of different integers from to contains numbers where one divides the other?

Checking an answer needs JavaScript. The hint and the solution open without it.

A whole number, a decimal, a fraction like 3/8 or a percent.

Hint

Write each number as an odd number times a power of and group by the odd part.

Solution
  1. Every integer from to is an odd number times a power of , and there are odd numbers in that range.
  2. Numbers with the same odd part, such as and , always divide one another, so each odd part forms one group.
  3. A set of numbers has numbers in one group, so it contains a dividing pair.
  4. The set has numbers and no number divides another, because twice any member exceeds , so the answer is .

Answer: