Учеба и наука
Закрыт
vip
1000
Из натуральных чисел от 1 до 1907 Дима хочет выбрать несколько и выписать в ряд так, чтобы сумма любых четырех идущих подряд чисел не делилась на... - вопрос №1643582
три, а сумма любых пяти последовательных в этом ряду чисел делилась на три. Какое наибольшее количество чисел может выбрать Дима?
сентябрь 29, 2015 г.
-
Всего ответов: 3
-
Вместо заданных чисел 1,2,...,1907 можно рассматривать их остатки от деления на три: 1,2,0,1,2,0,...,0,1,2. Нуль нельзя выбирать, иначе в пятерке, где нуль крайний, найдётся четвёрка с суммой, кратной трём. Выбранная последовательность единиц и двоек периодична с периодом, равным пяти. Короткий перебор показывает, что в периоде должно быть ровно четыре одинаковых числа. Поскольку в исходном наборе единиц и двоек поровну, то искомым набором может быть такой
2,1,1,1,1,2,1,1,1,1,...,2,1,1,1,1,2.В нём 636 единиц и 145 двоек.
итого 636+145=771 числа -
Рассмотрим получившийся ряд. Для удобства будем запишем новый ряд, состоящий из остатков при делении на 3 чисел из первого ряда.
Например, у нас получился ряд:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10.
Тогда второй ряд будет выглядеть так:
1, 2, 0, 1, 2, 0, 1, 2, 0, 1.
Покажем, что во втором ряду не может быть 0.
Возьмем любые 5 последовательные числа, так, чтобы 0 был или первым или пятым, по условию сумма должна делиться на 3, но если, мы теперь возьмем 4 числа без этого крайнего 0, то сумма тоже будет делиться на 3, а этого не должно быть. Следовательно, во втором ряду есть только цифры 1 и 2 – т.е. в нашем ряду который мы ищем есть только числа, которые при делении на 3 имеют остаток 1 и 2.
Рассмотрим все возможные пятерки чисел из получившейся последовательности, состоящей из 1 и 2.
Возможны несколько вариантов
1) Из 5 чисел все единицы, двоек нет, или зеркально – все двойки, единиц нет – т.е. все числа одинаковые, следовательно, вся последовательность будет состоять только из 2, или только из 1, следовательно, сумма любых 5 чисел не будет делиться на 3, что противоречит условию.
2) Из 5 чисел 2 единицы и 3 двойки, или 3 единицы и 2 двойки, но тогда их сумма не будет делиться на 3, что противоречит условию.
3) Из 5 чисел 1 двойка и 4 единицы, либо наоборот 1 единица и 4 двойки.
Т.е. наш второй ряд выглядеть так:
111121111211112111121111211112…..
Или
222212222122221222212222122221…
Как мы можем убедиться, эти ряды соответствуют нашему условию:
В любой пятерке сумма чисел или 6, или 9, т.е. число делится на 3
В любой четверке сумма чисел 4 или 5 (в первом ряду), или 8 или 7 (во втором ряду)
Но какой же ряд будет длиннее? Проверим, каких же чисел больше, запишем все натуральные числа от 1 до 1907 в ряд и посмотрим.
(1,2,3)(4,5,6)…(1903,1904,1905),1906,1907
Как видим, чисел, которые имеют остаток 0 – 635 штук, 1 – 636 штук, 2-636штук (итого 635+636+636=1907 чисел). Следовательно, наши ряды вида
111121111211112111121111211112…..
Или
222212222122221222212222122221…
Будут одинаковыми по длине.
Рассмотрим первый из них.
Так как у нас всего 636 чисел, которые при делении на 3 дают остаток 1, то мы используем их все, а те которые дают остаток 2 – их в 4 раза меньше, т.е. мы используем только 159 чисел.
Итого наш ряд будет состоять из 159+636=795 чисел
Пример такой последовательности
1 4 7 10 11 13 16 19 22 23 25 28 31 34 35…… 1897 1900 1903 1906 1907
Ответ: 795 чисел может выбрать Дима.
-
Как-то маловато выходит;
вопрос по второму ответу: разве числа 2, 3, 5,9 и т.д. лишние в этом ряду? 6 и 8 — согласен, лишние.
Я, конечно, мало что в этом понимаю… на всякий случай.
Похожие вопросы
Данный пример использовался на экзамене upsc в декабре 2013 и лишь один человек смог решить его ... 1,3,5,7,9,11,13,15 нужно взять 3 числа и только сложением получить 30.
апрель 13, 2015 г.
коробка с виноградом в 4 раза легче,чем коробка с бананам.Коробка с бананами на 12 кг тяжелее коробки с виноградом. Найди массу коробки с виноградом....
сентябрь 29, 2014 г.
Решено
В корзине лежат 25 грибов: рыжики и грузди. Известно, что среди любых 11 грибов имеется хотя бы один рыжик ,а среди любых 16 грибов хотя бы один груздь. Сколько рыжиков в корзине?
октябрь 18, 2014 г.
Решено
Вася проходит серию тестов, за каждый из которых он может получить от 0 до 100 баллов. Перед выполнением последнего теста Вася подсчитал, что если он...
сентябрь 6, 2015 г.