Знаю довольно короткое решение задачи, особенно 3 пункт. Просьба если решение вам очевидно - его не писать, а дать решить задачу новым людям.

На доске написано число 8, за один ход на доску можно записать либо число с доски умноженное на 2, либо сумму 2 чисел с доски.

  1. Возможно ли получить на доске число 2012.
  2. Чтобы сумма всех чисел на доске было бы равно 72.
  3. За какое минимальное количество ходов, можно написать на доске 832

задан 18 Апр '12 21:41

изменен 18 Июн '12 22:29

Angry%20Bird's gravatar image


9125

Можно ли писать число, которое уже есть на доске? Например, после 8, 16, снова написат 16 (как 8*2)?

(18 Апр '12 22:25) DocentI

Числа повторяться могут

(19 Апр '12 22:49) Balon
10|600 символов нужно символов осталось
2

Думаю, тут хорошо использовать двоичное представление числа. Тогда 0 соответствует умножение, а 1 - прибавление чисел. Например, 832=8*104, а 104(dec) = 1101000 (bin). Поэтому можно предложить такой алгоритм. Первая 1 соответствует исходному числу, далее нулю соответствует умножение на 2, 1 - умножение на 2 и прибавление первого числа. Получаем для 104:

$%8\to (16\to 24)\to48\to(96\to104)\to208\to416\to832$%

Ясно, что таким образом можно получить число вида 8k за m шагов, где m = (число цифр в двоичном представлении k) + (число единиц в этом представлении) - 2. Вычитаем 2, так как первая 1 не учитывается.

Но почему это число шагов нельзя уменьшить - пока неясно. Это еще надо додумать.

По сути предложенный алгоритм повторяет схему Горнера для вычисления значений многочленов. Как известно, она - самая экономная в вычислительном смысле для многочлена с произвольными коэффициентами. Хотя для некоторых конкретных многочленов есть более быстрые схемы.

ссылка

отвечен 19 Апр '12 23:41

изменен 19 Апр '12 23:45

По моему мнению, двоичная система об'ясняет минимальность ходов. Так как умножение на 2 приписывает ноль справа, а прибавление другого числа либо складывает количество единиц , либо приписывает ноль справа.

Если честно аналогию со схемой Горнера не понял, можно , пожалуйста , поподробней про неё .

(21 Апр '12 20:26) Balon

Что такое позиционная запись числа? Это, по сути многочлен от основания системы счисления. Например, $%110100_2=1\cdot 2^5+1\cdot 2^4 + 1\cdot 2^2$%. Ну, а значение многочлена можно подсчитать по схеме Горнера. Например, число $%104=110100_2$% можно подсчитать так. Первую 1 "сносим". Потом умножаем ее на 2 и прибавляем 1. Потом снова умножаем на 2 и прибавляем 1. Далее стоит коэффициент 0, так что только умножаем на 2, и т.д. Т.е. все сводится к операциям, предложенным Вами.
Но у Вас можно прибавлять не только 1, но и другое промежуточне число. Даст ли это новые возможности - не знаю.

(21 Апр '12 22:29) DocentI
10|600 символов нужно символов осталось
1
  1. Нет, т.к. все числа на доске будут кратны 8, а 2012 не кратно 8.

  2. Да, но только в том случае, если числа могут повторяться, например 8, 16, 24, 24. Если же числа не могут повторяться, то нет, т.к. 72=8*9, а 9 можно представить в виде суммы попарно различных натуральных чисел, включающих 1, двумя способами 9=1+2+6 и 9=1+3+5, откуда получаются 2 возможных варианта 72=8+16+48 и 72=8+24+40. Но ни одна из этих троек чисел не может быть получена в результате указанной процедуры.

  3. За 8: 8 -> 16 -> 32 -> 64 -> 128 -> 256 -> 512 -> 768 -> 832

Дополнение (доказательство минимальности 8 шагов в п.3). Рассмотрим максимальные числа, которые можно получить за $%n$% шагов. Наибольшее из таких чисел равно $% N_0(n) = 8 \cdot 2^n = 2^{n+3}$%, следующее по величине $% N_1(n) = N_0(n-1) + N_0(n-2) = 2^{n+2} + 2^{n+1} = 3 \cdot 2^{n+1}$%. За $%n$% шагов невозможно получить число, большее, чем $% N_0(n)$%, а также находящееся в диапазоне от $% N_1(n)$% до $% N_0(n)$%. Из первой части этого утверждения следует, что число 832 нельзя получить менее, чем за 7 шагов, из второй части следует, что число 832 нельзя получить за 7 шагов, т.к. $% N_1(7) < 832 < N_0(7) $%, следовательно, число 832 невозможно получить менее, чем за 8 шагов. А то, что за 8 шагов получить можно, доказывает приведенный пример.

ссылка

отвечен 19 Апр '12 1:46

изменен 20 Апр '12 14:47

В 3 пункте наиболее интересно доказательство минимальности ходов, ответ 8 ходов верен

(19 Апр '12 22:48) Balon

Это доказательство очевидно. Первые 6 шагов обеспечивают максимальный рост числа, на седьмом шаге максимальный рост даст перебор, используем "предмаксимальный", восьмой шаг - единственно возможный.

(19 Апр '12 23:05) Андрей Юрьевич

Новое доказательство хоршее. Однако его трудно распространить на произвольное число, а хотелось бы. Подозреваю, что двоичная структура числа здесь важна.

(20 Апр '12 17:06) DocentI

Да, но это уже другая задача "За какое минимальное число шагов можно получить заданное число". Если так обобщить задачу, то тогда и начальное значение нужно брать либо произвольное, либо 2, иначе непонятно, чем 8 лучше других чисел?

(20 Апр '12 17:34) Андрей Юрьевич

Да, это другая задача, но она гораздо интереснее. Лучше брать за начальное число 1.

(20 Апр '12 20:05) DocentI

Думаю, что n-разрядное двоичное число, содержащее k единиц можно получить из единицы за n+k-2 шагов.

(21 Апр '12 18:00) Андрей Юрьевич

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

(21 Апр '12 22:52) DocentI

Я предложил схему, при которой на каждом шаге получается максимально большое число - сначала умножение на 2 (наибольшее возможное число раз), потом заполнение "внутренними" единицами. Эта схема наиболее быстрая в "локальном" смысле - каждый ее шаг дает максимальное увеличение числа. Думаю, она в "глобальном" смысле самая быстрая (или одна из нескольких самых быстрых).

(22 Апр '12 14:46) Андрей Юрьевич
показано 5 из 8 показать еще 3
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×32

задан
18 Апр '12 21:41

показан
2250 раз

обновлен
18 Июн '12 22:29

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

по почте:

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

по RSS:

Ответы

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

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