а) Натуральные числа от 1 до 1000 разбиты на 20 групп. Докажите, что произведение чисел в какой-то из групп делится на миллион.

б) Натуральные числа от 1 до 1000 разбиты на 20 групп. Докажите, что произведение чисел в какой-то из групп делится на десять миллионов.

По первому пункту, кажется, несложно. Всего у нас 100 чисел, кратных 10. Если в какой-то из групп есть 6 таких чисел, то задача решена. В противном случае имеем 20 групп, в каждой по 5 чисел кратных 10. В одной из таких групп будет и число 1000, которое вместе с остальными 4 числами, кратными 10, и даст произведение, кратное миллиону (и даже десяти миллионам).

По второму пункту возникли затруднения. А задача-то для 5-го класса! Хотя и с матбоя. А я не могу решить. Мне очень стыдно. Пожалуйста, помогите решить. Зарангеш благодарю!

задан 30 Авг '17 15:51

@Аллочка Шакед, а 2-ки и 5-ки уже и за числа не считаем?

Разве Вы сами не ответили на свой вопрос? 10 миллионов это семь нулей?

(30 Авг '17 18:40) kipot_l

"...1000, которое вместе с остальными 4 числами, кратными 10" даст произведение, кратное миллиону (и даже ДЕСЯТИ миллионам)?

(30 Авг '17 20:55) kipot_l
2

А эта задача просто неверна

(30 Авг '17 21:21) knop
1

Разобьём на группы числа, кратные 10. В группу с 1000 добавим ещё 3 таких числа, в 9 чисел кратных 100 собьём в три группы, остальные 90 чисел забьем в 16 остальных групп по 5-6 чисел. Теперь все остальные четные засунем в какую-то одну из 20 групп, все кратные 5 - в другую, а прочие числа не волнуют совсем. Итого нигде нет делимости на 10^7

(30 Авг '17 21:27) knop
1

@knop, у Вас второпях получилось больше ста чисел, делящихся на 10. Нехорошо...

А так, вроде всё правильно, построен контрпример. В новомодных задачниках немало ошибок и опечаток, "если ты не нашёл в книге ни одной ошибки, значит ты невнимательно её читал!".

(30 Авг '17 22:07) kipot_l
1

@knop: если числа, кратные 10, распределять как угодно, то контрпримера не получается. В какую-то группу могут попасть 20 и 50, что даст дополнительную делимость на 10. И таких вариантов довольно много: любое кратное 20 вместе с любым кратным 50 даёт тот же эффект.

(30 Авг '17 22:17) falcao

@knop, @falcao, Большое спасибо!

(31 Авг '17 0:21) Аллочка Шакед
1

Та-а-к...! Задача становится поинтереснее...

(31 Авг '17 0:42) kipot_l
1

@kipot_l: мне она с самого начала показалась интересной. Общий ход мысли понятен, но решения я пока не знаю. Надо заметить, что мне за это совершенно не "стыдно", а на матбоях довольно часто предлагают задачи с кажущимися "очевидными" решениями в ту или другую сторону :)

(31 Авг '17 1:10) falcao
1

@kipot_l - вроде нет, у меня ровно 100 чисел распределены. Другой вопрос, что я таки сделал это неаккуратно, и @falcao пришлось затыкать дырку. Но с количеством вроде всё нормально

(31 Авг '17 18:06) knop
показано 5 из 10 показать еще 5
10|600 символов нужно символов осталось
2

Я думаю, что @knop в конечном счёте прав: утверждение пункта б) неверно. Осталось аккуратно построить контрпример.

Удобно с каждым числом n от 1 до 1000 связать двумерный вектор (k,m) из максимальных показателей степеней чисел 2 и 5 в каноническом разложении n. Например, числу 800 соответствует вектор (5;2). Требуется показать, что 1000 полученных пар можно разбить на 20 групп так, что у суммы векторов в каждой группе, хотя бы одна из координат не превосходит 6.

Для начала рассмотрим 100 чисел, делящихся на 10, то есть это векторы с обеими ненулевыми координатами. Остальные числа будут распределены в последнюю очередь. При этом нулевые векторы можно распределять как угодно.

У нас есть один вектор (3;3), соответствующий 1000. Есть ещё 9 векторов, соответствующих остальным числам, делящимся на 100. Это 4 вектора (2;2), два вектора (3;2), и по одному вектору типов (4;2), (5;2), (2;3). Далее смотрим на 90 векторов, соответствующим числам, делящимся на 10, но не на 100. Их подразделим на три категории: в одну из них войдут т.н. ординарные числа с векторами (1,1): это числа, делящиеся на 10, но не делящиеся ни на 20, ни на 50. Вторую категорию образуют числа, делящиеся на 20, но не на 50. Третью -- числа, не делящиеся на 20 и делящиеся на 50.

Простой анализ показывает, что имеется по 40 чисел в каждой из категорий 1 и 2, и 10 чисел в категории 3. Идея в том, чтобы не смешивать числа категорий 2 и 3. Числа категории 1 "безобидны", и ими можно дополнять уже сформированные группы.

Итак, из 40 чисел категории 2 формируем 6 групп по 6 чисел в каждой. Произведение делится на 10^6, но не делится на 10^7. Остаётся 4 числа, и их дополняем двумя "ординарными". Далее, из 10 чисел, делящихся на 100, формируем группы, дополняя ординарными (ord): 1000, 500, ord; 200, 400, 800; 100, 300, 700; 600, 900 с двумя ординарными. Это ещё 4 группы, и в запасе остаётся 35 ординарных.

Из 10 чисел третьей категории формируем одну группу из 6 чисел, и одну из оставшихся четырёх с добавлением двух ординарных. Итого сформировано 13 групп, и осталось 33 ординарных числа. Формируем из них 5 групп по 6 чисел в каждой. Оставшиеся три числа формируют 19-ю группу. К ним добавляем все оставшиеся числа (из тысячи), делящиеся на 2, но не на 5. Наконец, в 20-ю группу поместим все нечётные числа (из тысячи).

ссылка

отвечен 31 Авг '17 17:22

@falcao, большое спасибо!

(31 Авг '17 23:03) Аллочка Шакед
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,399
×1,114
×211
×150
×128

задан
30 Авг '17 15:51

показан
768 раз

обновлен
31 Авг '17 23:03

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

по почте:

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

по RSS:

Ответы

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

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