Найти наибольшее натуральное число $%n$% с таким свойством: существуют такие $%n$% неотрицательных чисел $%x_1, x_2,...,x_n$%, что для любых чисел $$e_1,e_2,...,e_n \in \left \{ -1;0;1\right \},$$ не все из которых нули, число $%e_1x_1+e_2x_2+...+e_nx_n$% не делится на $%n^3$%.

задан 6 Апр '15 17:44

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

Пусть $%n\ge10$%. Рассмотрим все суммы вида $%e_1x_1+\cdots+e_nx_n$%, где $%e_1,\ldots,e_n\in\{0;1\}$%. Их имеется ровно $%2^n$%. Легко доказать методом математической индукции, что $%2^n > n^3$% при $%n\ge10$% (это упражнение часто встречается в задачниках). Тогда по принципу Дирихле найдутся две суммы с различными коэффициентами, дающие при делении на $%n^3$% одинаковые остатки. Берём разность этих сумм. Коэффициенты не все нулевые, и при этом они принимают значения из множества $%\{-1;0;1\}$%.

При $%n=9$% рассмотрим числа $%x_1=1$%, $%x_2=2$%, $%x_3=4$%, ... , $%x_9=2^8=256$%. Рассмотрим наибольшее число, коэффициент при котором в выражении $%e_1x_1+\cdots+e_nx_n$% отличен от нуля. Можно считать, что он равен 1. Тогда сумма больше нуля, так как каждое число списка больше суммы всех предыдущих, и она меньше суммы всех чисел, равной 511. Следовательно, на $%n^3=9^3=729$% никакое из чисел этого вида не делится.

ссылка

отвечен 6 Апр '15 20:14

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

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

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

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

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

отмечен:

×47

задан
6 Апр '15 17:44

показан
636 раз

обновлен
6 Апр '15 20:14

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

по почте:

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

по RSS:

Ответы

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

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