Навчання / Бібліотека / Комбінаторика

Вимушена подільність

КомбінаторикаСкладне

Яке найменше $n$ таке, що кожна множина з $n$ різних цілих чисел від $1$ до $24$ містить $2$ числа, з яких одне ділиться на інше?

Для перевірки відповіді потрібен JavaScript. Підказка й розв’язок відкриваються і без нього.

Підказка

Запиши кожне число як непарне, помножене на степінь числа $2$ , і згрупуй за непарною частиною.

Розв’язок

Кожне ціле від $1$ до $24$ є непарним числом, помноженим на степінь числа $2$ , а непарних чисел у цьому діапазоні $12$ .
Числа з однаковою непарною частиною, як-от $3$ і $12$ , завжди діляться одне на одне, тож кожна непарна частина утворює одну групу.
Множина з $13$ чисел має $2$ числа в одній групі, отже містить пару з подільністю.
Множина ${13, 14, \dots, 24}$ має $12$ чисел, і жодне не ділить інше, бо подвоєне будь-яке з них перевищує $24$ , тому відповідь $13$ .

Відповідь: $13$