Получить 2010 нулей

[Xenia1996]

Нетрудная задачка, но мне понравилась.

На доске написано 2011 натуральных чисел, каждое из которых не превосходит 2011. Если $n$ и $m$ — какие-то два из этих чисел и $n\ge m$, то разрешается вместо числа $n$ написать число $n-m$. С новым набором чисел можно выполнить эту же операцию и т.д.

а) Доказать, что через не более чем 4020 шагов можно добиться того, чтобы среди написанных на доске чисел 2010 чисел были нулями.
б) Доказать, что вначале могут быть написаны такие числа, что будет невозможно получить 2010 нулей раньше, чем через 4020 шагов.

[Sonic86]

Совсем уж просто:
а) алгоритм Евклида;
б) первые $n$ чисел Фибоначчи (на них алгоритм Евклида всегда работает дольше всего)

[Xenia1996]

Sonic86 в сообщении #440612 писал(а):

б) первые $n$ чисел Фибоначчи (на них алгоритм Евклида всегда работает дольше всего)

А почему не 2011 и 2010 единичек?

И что такое $n$?

Если у Вас $n=2011$, то 2011-ое число Фибоначчи намнооого превосходит 2011. А в условии написано "каждое из которых не превосходит 2011".

[Xenia1996]

(Оффтоп)

Честно говоря, я не понимаю, в чём прикол решать задачу, не прочитав её условие

-- Вс май 01, 2011 16:44:50 --

Я вижу, задачка слишком лёгкая, решать никто не хочет. Посему выскажу пару собственных соображений.

Разрыв между наибольшим и наименьшим из чисел не может превышать 2010. После каждой операции разрыв можно уменьшить как минимум на 1, так что за 2010 операций можно все числа равными сделать.
А потом ещё за 2010 сделать 2010 нулей.

Если же изначально стоит число 2011 и ещё 2010 единичек, то менее, чем за 4020 не получится.

Я права?

[Xenia1996]

Мне уже подсказали, что я ошиблась.
Если наибольших чисел более одного, моё решение не катит, ибо разрыв не сокращается.
Так что, не так всё просто

[Xenia1996]

Короче, так:

Среди чисел могут быть равные. Посему с каждым ходом либо наибольшее уменьшается на 1 (если оно единственное), либо появляется один новый нолик. Значит, за 4020 шагов всегда можно добиться 2010 нулей.

А вот если записано число 2011, а за ним 2010 единичек, то меньше, чем за 4020 не выйдет...

Могу снова ошибиться...