На столе лежат 2007 кучек, сначала в каждой кучке по одному ореху. Каждым ходом Петя берет три кучки,в которых поровну орехов и объединяет их в одну. Через сколько ходов может закончиться это интересное занятие? (Процесс заканчивается только тогда,когда никакие кучки уже нельзя объединить)

задан 12 Мар '14 23:41

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

Рассмотрим такой процесс: сначала совершается $%2007/3=669$% ходов, в результате чего появляется столько же кучек, в каждой из которых по 3 ореха. Далее делаем $%669/3=223$% хода, и получается столько же кучек по 9 орехов в каждой. Здесь уже число $%223$% не делится на 3, и можно сделать $%222/3=74$% хода, одну кучку оставив, а из других создав кучки по 27 орехов в каждой. Теперь снова делим 74 на 3 с остатком, который равен двум, то есть оставляем две кучки, а остальные 72 соединяем за $%24$% хода в кучки по 81 ореху. Далее за $%8$% ходов получаем столько же кучек по 243 ореха, оставляем две, и из оставшихся шести за $%2$% хода делаем две кучки из 729 орехов. Больше ничего сделать уже нельзя.

Общее число ходов составило $%669+223+74+24+8+2=1000$%. Покажем, что по-иному быть не могло. Прежде всего, количество орехов при объединении кучек утраивается. Поэтому количество орехов в кучке равно степени тройки. Если процесс закончился, это означает, что кучек с одинаковым числом орехов имеется от 0 до 2. А это соответствует представлению числа в системе счисления с основанием 3. Здесь легко видеть, что $%2007=2202100_3$%, то есть $%2007=2\cdot3^6+2\cdot3^5+2\cdot3^3+1\cdot3^2$%.

Ввиду того, что представление натурального числа в системе счисления с заданным основанием единственно, отсюда следует единственность ответа. Зная троичное представление числа, можно вычислить этот результат по такой формуле. На создание кучки из $%3^n$% орехов ушло $%3^{n-1}+3^{n-2}+\cdots+3+1=\frac{3^n-1}2$% ходов. Суммирование всех встречающихся при этом величин даёт такой результат, который проще описать словесно. Это разность числа и суммы его троичных цифр, делённая на два.

В нашем случае сумма цифр составляет $%2+2+2+1=7$%, поэтому результат равен $%(2007-7)/2=1000$%.

ссылка

отвечен 13 Мар '14 0:36

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

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

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

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

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

отмечен:

×1,131

задан
12 Мар '14 23:41

показан
1296 раз

обновлен
13 Мар '14 0:36

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

по почте:

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

по RSS:

Ответы

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

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