Пусть S - множество делителей числа $%2004^{100}$%. Обозначим через T подмножество S, в котором нет двух элементов, один из которых делится на другой. Какое наибольшее число элементов может быть в подмножестве T? Сколько всего существует таких подмножеств Т?

задан 4 Июл '15 0:07

10|600 символов нужно символов осталось
2

$$204=2^2\cdot3\cdot167.$$ Множество $%S$% - это числа вида $%204=2^a\cdot3^b\cdot167^c$%, причём $%0\le b,c\le100$%. Предположим, что в $%S$% более $%101^2$% элементов. Тогда согласно принципа Дирихле у некоторых двух чисел пара $%(b,c)$% одинакова и одно из этих чисел делится на другое.

Пример из $%101^2$% элементов: $%2^{200-(b+c)}\cdot3^b\cdot167^c$%, $%0\le b\le100,0\le c\le100$%.

ссылка

отвечен 4 Июл '15 11:49

@EdwardTurJ Cпасибо за решение! Оценку понял, а вот как построить пример - не очень. Можете, пожалуйста, объяснить как Вы к нему пришли?

(4 Июл '15 16:42) sapere aude
1

@sapere aude: Из доказательства оценки количества элементов следует, что в примере из $%101^2$% элементов должны присутствовать в качестве сомножителей всевозможные пары $%3^b$% и $%167^c$%. Рассмотрим два элемента $%2^{a_1}3^{b_1}167^{c_1}$% и $%2^{a_2}3^{b_2}167^{c_2}$%. Не ограничивая общности, будем считать, что $%b_1\ge b_2$%.

Если $%c_1< c_2$%, то ни один из них не делится на другой.

Если же $%c_1\ge c_2$%, то для "неделимости" необходимо, чтобы $%a_1< a_2$%. Для этого достаточно положить $%a_i=200-(b_i+c_i)$%.

(4 Июл '15 17:39) EdwardTurJ
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,866
×1,507
×985
×295

задан
4 Июл '15 0:07

показан
690 раз

обновлен
4 Июл '15 17:41

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

по почте:

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

по RSS:

Ответы

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

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