2
1
  У Кати и Миши есть калькуляторы. Катин калькулятор может либо увеличивать число на 1, либо умножать число на 2. Калькулятор Миши также может увеличивать число на 1, однако умножает на 3. Никаких других операций калькуляторы не выполняют. Изначально на обеих калькуляторах 0.
1. Катя и Миша хотят получить на своих калькуляторах вместо нуля число 2013. Какое наименшее колличество операций понадобится для этого Кате, а какое Мише?
2. Приведите примеры чисел, для получения каких Катя может выполнить на своём калькуляторе меньше операций, чем Миша.
3. Докажите, что существует бесконечное множество натуральных чисел, для получения каких Миша может выполнять на своём калькуляторе меньше операций, чем Катя.
4. Будет ли бесконечным множество всех натуральных чисел, для получения которых Катя может выполнять на своём калькуляторе меньше операций, чем Миша?

задан 27 Авг '14 18:32

изменен 28 Авг '14 23:17

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

Заранее благодарна за решение!

(27 Авг '14 18:33) Алла71

Задача с действующей олимпиады https://dl.dropboxusercontent.com/u/15765938/TYM/2014/TYM-2014-LYST_PROBLEMS.pdf

(25 Окт '14 21:39) EdwardTurJ
10|600 символов нужно символов осталось
2

Наименьшее количество ходов для Кати: Запишем двоичное представление числа $%n$%: $%a_k\cdot 2^k+\ldots+a_1\cdot 2+a_0$%. Тогда число ходов - это сумма $%a_k+\ldots+a_0+k$%.

Аналогично находим число ходов Миши: если запись в троичной системе счисления для числа $%n$% имеет вид $%b_l\cdot 3^l+\ldots+b_1\cdot 3+b_0$%, то число наименьшее число ходов - $%b_l+\ldots+b_0+l$%.

Тогда в случае числа $%n=2013$% мы имеем $%n=(11111011101)_2=(2202120)_3$%. Откуда легко видеть, что число ходов равно 19 и 15, соответственно.

ссылка

отвечен 27 Авг '14 22:14

изменен 27 Авг '14 22:16

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

1. Пойдем от обратного. Пусть у нас есть 2013, будем из него вычитать и его делить.

Что может сделать Миша: 2013/3 = 671. Далее два раза отнимает 1, получает 669. Далее делим на 3, получаем 223. Отнимает 1. Делим на 3. Получаем 74. Отнимаем 2 раза 1. Делим 2 раза на 3, получаем 8. Отнимаем единицу 2 раза, делим на 3, отнимаем 1 два раза, получаем 0. И всего 15 операций. Катя: Отнимаем единицу, получаем 2012. Делим это число 2 раза на 2, получаем 503. Отнимаем 1, получаем 502. Делим на 2, получаем 251. Отнимаем 1, получаем 250. Делим на 2, получаем 125. И так далее. Получаем число операций большее, чем 15.

2. Числа 8,16,32.

3. Для доказательства приведем пример бесконечной последовательности, где Мишин калькулятор позволяет делать меньше действий: это все числа вида 3 в степени N > 0, 3, 27, 81 и так далее.

4. Наибольшее преимущество: Катин калькулятор имеет при числах - степенях двойки. Мне кажется, можно придумать доказательство того, что, начиная с какого-то числа Мишин калькулятор будет выигрывать. Но, как это сделать, еще не придумал.

ссылка

отвечен 27 Авг '14 20:41

изменен 28 Авг '14 23:21

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

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

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

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

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

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

отмечен:

×590

задан
27 Авг '14 18:32

показан
1061 раз

обновлен
25 Окт '14 21:39

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

по почте:

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

по RSS:

Ответы

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

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