РЕШУ ОЛИМП: задания, ответы, решения

Задания

Версия для печати и копирования в MS Word

Тип 21 № 19 Добавить в вариант

Найти минимальное натуральное число n такое, что в любом множестве из n различных натуральных чисел, не превосходящих 1000, всегда можно выбрать два числа, большее из которых не делится нацело на меньшее.

Спрятать решение

Решение.

Среди 10 первых степеней двойки $1=2 в степени левая круглая скобка 0 правая круглая скобка , 2=2 в степени левая круглая скобка 1 правая круглая скобка , 4=2 в квадрате , \ldots, 512=2 в степени левая круглая скобка 9 правая круглая скобка ,$ в каждой паре чисел большее делится на меньшее, следовательно, $n больше или равно 11.$ С другой стороны, пусть в некотором множестве из $n больше или равно 11$ чисел большее число каждой пары чисел делится на меньшее. Расположим все числа по возрастанию, из предположения следует, что каждое следующее число как минимум в 2 раза больше предыдущего. Значит, самое большое число не меньше, чем в $2 в степени левая круглая скобка 10 правая круглая скобка =1024$ раз больше первого, то есть больше 1000  — противоречие.

Ответ: $n=11.$

Спрятать критерии

Критерии проверки:

Критерии оценивания выполнения задания	Баллы
Верное решение.	7
Доказано $n \geq 11$ с примером.	3
Доказано только $n \leq 11$ (вторая часть).	4
Решение не соответствует ни одному из перечисленных выше критериев.	0
Максимальный балл	7

Всесибирская олимпиада школьников, 9 класс, 1 тур (отборочный), 2016 год

Классификатор: Алгебра: числа. Разные вопросы о целых числах

Спрятать решение · Спрятать критерии · Помощь