Для каких n, принадлежащие N у последовательности $%C_2^2,C_3^2, ..., C_n^2 ...$% будут все возможные остатки деления на n? Пожалуйста, помогите решить мне эту задачку с доказательством... Очень нужно!`

задан 24 Дек '12 1:06

изменен 24 Дек '12 15:06

%D0%A5%D1%8D%D1%88%D0%9A%D0%BE%D0%B4's gravatar image


5525

Что означают эти С с цифрами? Какая последовательность?

(24 Дек '12 2:06) DocentI

Да, так вставилось....Сорри. Теперь исправила...

(24 Дек '12 2:16) Катя

Исправила формулы. Последовательность бесконечна?

(24 Дек '12 2:22) DocentI

Вы же уже давали эту задачу, см. здесь. Зачем повторяться?

(24 Дек '12 2:26) DocentI

Потому что это оказалось для бесконечной последовательности...А не для конечной...Вот...А обосновать как для бесконечной - не знаю...

(24 Дек '12 2:33) Катя

Про бесконечность выяснили уже тогда. Никто не отозвался. Думаете, во второй раз решат?

(24 Дек '12 3:08) DocentI
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
1

Может, конечно, я жестко туплю, но в последовательности будет ровно н-1 разных членов, а возможных остатков ровно н. Поэтому получается, что ни при каком н не будет выполняться данное условие. Всё бы хорошо, но при н=1 я задумался.... А как? Ведь не существует же С по 2 из 1, но формально 1 принадлежит натуральным... И еще. Не хочу никого обидеть, но, по-моему, ответ DocentI о том, что при н=2 все остатки будут, неверен, так как нет остатка 0. Приношу заранее свои извинения.

ссылка

отвечен 24 Дек '12 4:58

изменен 24 Дек '12 15:05

%D0%A5%D1%8D%D1%88%D0%9A%D0%BE%D0%B4's gravatar image


5525

Почему именно n - 1? Последовательность бесконечная. Посмотрите по ссылке в моем комменте предыдущее появление этого вопроса. Ответ там есть. Только доказательства нет.

Я сделала численный эксперимент и оказалось, что условие выполняется, если n - степень двоки. Например, если n = 2: среди сочетаний есть как четные, так и нечетные.

(24 Дек '12 12:44) DocentI
10|600 символов нужно символов осталось
1

Я понял условие следующим образом. Имеется последовательность "треугольных" чисел $%1, 3, 6, ..., n(n-1)/2, ...$%; требуется выяснить, при каких натуральных $%m$% среди чисел данной последовательности будут встречаться все возможные остатки от деления на $%m$%.

Например, при $%m=3$% получаются остатки $%1,0,0,1,0,0,...$%, среди которых нет $%2$%, то есть $%m=3$% нам не подходит. А если $%m=4$%, то остатки будут равны $%1,3,2,2,3,1,0,...$%, где встречаются все остатки, и потому $%m=4$% нам подходит.

Ответом в этом случае действительно будут степени двойки. Докажем это.

Пусть $%m$% не есть степень двойки. Тогда $%m$% обладает нечётным делителем $%d>1$%. Достаточно доказать, что при делении на $%d$% некоторый из остатков не встречается. Тогда он же не будет встречаться и при делении на $%m$%.

Обозначим через $%r$% остаток от деления $%n(n-1)/2$% на $%m$%. Тогда удвоенная разность числа и остатка, то есть $%n(n-1)-2r$%, делится на $%m$%. То же самое будет верно для числа, умноженного на $%4$%, то есть для $%4n^2-4n-8r=(2n-1)^2-(8r+1)$%.

Теперь обратим внимание на то, что квадрат целого числа при делении на $%d$% не может давать все возможные остатки. Действительно, достаточно возводить в квадрат только числа от $%0$% до $%d-1$% включительно. Это дало бы все $%d$% значений только при отсутствии повторений у остатков, но $%(d-1)^2$% даёт в остатке $%1$%, как и $%1^2$%. Заметим, что у нас $%d>1$%, а потому $%d-1$% и $%1$% -- это разные числа. (Здесь можно также заметить, что $%d-2$% при возведении в квадрат даст то же, что $%2$% и так далее, но этот факт на самом деле не требуется.)

Итак, мы выяснили, что существует такой остаток $%s$%, который не мог возникнуть при делении $%(2n-1)^2$% на $%d$%. Теперь осталось заметить, что при нечётном $%d$%, если $%r$% пробегает все значения от $%0$% до $%d-1$%, то и остаток от деления $%2r$% в каком-то порядке пробегает эти же значения. Значит, то же самое будет верно для $%4r$% и для $%8r$%, а также для $%8r+1$%. В частности, для какого-то $%r$% значение остатка для $%8r+1$% будет равно $%s$%, а у нас было сказано, что $%(2n-1)^2-(8r+1)$% делится на $%d$%. Но это невозможно в силу того, что квадрат остатка $%s$% давать не может.

Осталось выяснить, что все значения вида $%m=2^k$% нам подходят. Установим это методом математической индукции. При $%m=1$%, $%m=2$% всё очевидно. Пусть $%k>1$%, и пусть уже установлено, что числа вида $%n(n-1)/2$% при делении на $%2^{k-1}$% дают все возможные значения для остатков. Пусть $%r$% -- остаток от деления $%n(n-1)/2$% на $%2^{k-1}$%. Тогда при делении на $%2^k$% того же самого числа, остаток принимает одно из значений $%r$% или $%r+2^{k-1}$%. Увеличим значение $%n$% на $%2^k$%, то есть рассмотрим число $$\frac{(n+2^k)(n+2^k-1)}2=\frac{n(n-1)}2+n\cdot2^k+2^{2k-1}-2^{k-1}.$$ Отсюда видно, что остатки от деления на $%2^k$% у двух рассмотренных нами "треугольных" чисел (с номерами $%n$% и $%n+2^k$%), отличаются на $%2^{k-1}$%. Значит, оба остатка $%r$% и $%r+2^{k-1}$% принимаются этими числами в том или другом порядке. Поскольку $%r$% принимало все значения от $%0$% до $%2^{k-1}-1$%, то теперь мы имеем в распоряжении все значения остатков от $%0$% до $%2^k-1$%, что завершает доказательство.

ссылка

отвечен 7 Фев '13 23:09

Вы просто герой труда! Не уверена, что хватит времени разбираться, но я Вам верю.

(8 Фев '13 2:12) DocentI

Когда на работу не надо идти, можно и потрудиться :)

Кстати, этой задачи про остатки треугольных чисел я раньше не встречал, а она довольно красивая!

(8 Фев '13 2:19) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,306
×1,169
×797
×393

задан
24 Дек '12 1:06

показан
1736 раз

обновлен
8 Фев '13 2:19

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

по почте:

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

по RSS:

Ответы

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

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