Какое максимальное количество натуральных чисел от 1 до 50 можно выбрать так, чтобы среди них не было двух чисел, отличающихся ровно в 3 раза?

задан 9 Апр '14 23:07

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

Все числа надо разделить на группы вида $%x$%, $%3x$%, $%9x$% и так далее, где каждое следующее число втрое больше предыдущего. Каждая группа начинается числом, не делящимся на 3. Среди чисел от 1 до 50 имеется ровно 16, которые кратны трём, поэтому групп будет 50-16=34.

Рассмотрим первую группу чисел: 1, 3, 9, 27. Из неё мы не можем брать соседних чисел, поэтому выбрать можем не более двух. Пусть это будут 1 и 9. Числа из разных групп никак друг на друга не влияют -- в этом основная идея. Следующей группой будет 2, 6, 18. Здесь уже три числа, а не четыре, но можно отобрать два -- это 2 и 18.

Группы из трёх чисел будут также начинаться с 4 и 5. Из каждой из них отбираем по два числа. Всего на данный момент отобрано 8 чисел.

Оставшиеся группы (в количестве 30) состоят из двух чисел или из одного. Каждая вносит вклад из одного числа (по максимуму). Итого получается 38 чисел из 50. Это значение достигается: здесь указан конкретный способ выбора для каждой из групп.

ссылка

отвечен 9 Апр '14 23:44

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×224
×136

задан
9 Апр '14 23:07

показан
1301 раз

обновлен
9 Апр '14 23:44

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

по почте:

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

по RSS:

Ответы

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

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