Есть такая задача:

Даны несколько различных натуральных чисел, среди любых $%n$% из которых можно выбрать два, делящихся друг на друга. Доказать, что все числа можно разбить на $%n − 1$% группу так, чтобы для любых двух чисел из одной группы одно число делилось на другое.

Вроде бы нужно воспользовать теоремой Дилуорса (наибольшее число элементов в антицепи равно наименьшему числу антицепей в разбиении) для частично упорядоченного множества из данных чисел, где порядок - это отношение делимости. Но как доказать, что наибольшее число элементов в антицепи в таком множестве равно $%n − 1$%?

задан 10 Ноя '19 0:28

изменен 10 Ноя '19 0:37

%D0%9A%D0%B0%D0%B7%D0%B2%D0%B5%D1%80%D1%82%D0%B5%D0%BD%D0%BE%D1%87%D0%BA%D0%B0's gravatar image


8.9k335

@elman: формулировка допускает наличие пустых групп. Условие лучше звучит, если сказать, что групп не более n-1. Тогда доказывать дополнительно ничего не надо.

Вообще, тут достаточно разбивать числа на группы по принципу наибольшего нечётного делителя. Среди них имеется < n значений, согласно условию.

(10 Ноя '19 10:49) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,463
×263
×43
×34
×1

задан
10 Ноя '19 0:28

показан
273 раза

обновлен
10 Ноя '19 10:49

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru