Имеется $%n$% целых чисел $%0;1;2;...;n-1$%. Переставив эти числа в случайном порядке, получим их некоторую перестановку $%\big(i_{1}; i_{2} ;...; i_{n} \big)$%. Из исходного набора чисел $% \big(0;1;2;...n-1\big)$% и этой перестановки $%\big(i_{1}; i_{2} ;...; i_{n} \big)$% получим новый набор чисел $%\big(a_{1}; a_{2} ;...; a_{n} \big)$% по правилу: $% a_{1}= r_{n} \big(0+ i_{1} \big); a_{2}= r_{n} \big(1+ i_{2} \big);...;a_{n}= r_{n} \big( \big(n-1\big) + i_{n} \big) $% , где $% r_{n} \big(m\big) $% - остаток от деления числа $%m$% на число $%n$%.

(Например, пусть $%n=3$%. Тогда, из исходного набора $% \big(0;1;2\big)$% и перестановки $%\big( i_{1}; i_{2}; i_{3} \big)= \big(1;2;0\big)$% получится набор $%\big( a_{1}; a_{2}; a_{3} \big)= \big(1;0;2\big)$%, т.к. $%r_{3} \big(0+1\big) =1; r_{3} \big(1+2\big)=0; r_{3} \big(2+0\big)= 2$% ).

a) При $%n=9$% приведите пример такой перестановки $% \big( i_{1}; i_{2} ;...; i_{9} \big)$%, что в соответствующем наборе $% \big( a_{1}; a_{2} ;...; a_{9} \big)$% все числа различны;

б) докажите, что, если $%n=10$%, то какую бы перестановку $% \big( i_{1}; i_{2} ;...; i_{10} \big)$% мы не взяли, в наборе $% \big( a_{1}; a_{2} ;...; a_{10} \big)$% обязательно встретятся одинаковые числа.

задан 27 Янв '15 1:52

изменен 27 Янв '15 2:07

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

При нечетном числе элементов можно взять числа по порядку. В итоге они удвоятся, и все остатки будут разные. Это следует из того, что 2х-2у не делится на нечетное число, если х-у не делится. Для 9 чисел у нас будет 024681357.

Для 10 чисел обратим внимание только на четность. У нас 5 четных чисел и столькоже нечетных. К ним в каком-то порядке прибавляется 5 четных и 5 нечетных. Пусть к четным числам прибавляется х четных. Тогда к ним прибавляется 5-х нечетных, и оставшиеся х нечетных прибавляется к нечетным. В итоге ровно 2х чисел станут четными, а в перестановке их должно быть пять.

ссылка

отвечен 27 Янв '15 9:43

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

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

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

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

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

отмечен:

×2,760

задан
27 Янв '15 1:52

показан
268 раз

обновлен
27 Янв '15 9:43

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

по почте:

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

по RSS:

Ответы

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

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