Васе подарили солидную шоколадку 17 на 17. Как всегда, он начал ломать ее по “бороздкам” на части (за один раз можно наложить друг на друга несколько частей и разломать их одновременно). За какое наименьшее число действий Вася сумеет разломать шоколадку на отдельные квадратики 1 на 1?

задан 16 Апр '14 12:33

Хотелось бы узнать, имеется ли в этой задаче какой-либо скрытый "подвох". На первый взгляд, кажется, что наиболее выгодная стратегия -- ломать "приблизительно пополам". В данном случае -- на части 17x9 и 17x8. Обоснованием может являться то, что если одна шоколадка "вкладывается" в другую, то её, вроде бы, нельзя поломать быстрее. Тогда получается, что задача сводится к случаю 17x9. Его можно свести к 9x9 или 17x5 -- в зависимости от того, что будет быстрее. Но я не уверен, что здесь "жадный алгоритм" работает.

(16 Апр '14 14:58) falcao

Здравствуйте! Подвоха нет. Это задача из школьного мат.кружка. Главный вопрос: обосновать, что предоставленное решение действительно оптимальною

(17 Апр '14 12:31) make78
1

@make78: мне так и казалось, что здесь нет "подводных камней", но хотелось в этом точнее убедиться. Строгое обоснование можно получить методом математической индукции. То есть сначала надо вывести "эмпирическую" формулу, а потом её доказать. Для $%m\times n$% берутся степени двойки со свойством $%m\le2^s$% и $%n\le2^t$% (с минимальными показателями), и тогда ответом будет $%s+t$%.

(17 Апр '14 14:45) falcao
10|600 символов нужно символов осталось
0

Мой вариант: задачу можно свести к одномерной - сначала делить в одном направлении, потом - в другом. Затем сложить количество делений в каждом направлении. Таким образом, нам нужно разделить отрезок [0;17] по целочисленным меткам. 17=2^4+1. Поэтому разделить менее, чем за 5 шагов не удастся. Итого - 10.

ссылка

отвечен 16 Апр '14 21:32

Здравствуйте, Анна! Да, мне это решение видится правильным. Но как строго обосновать его правильность? Благодарю за участие.

(17 Апр '14 12:32) make78
1

Обосновать, что не менее 5? Каждое деление может увеличить число кусков не более, чем вдвое. Поэтому за 4 операции из одного куска может получиться не более 2^4 кусков.

(17 Апр '14 12:44) cartesius
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×69

задан
16 Апр '14 12:33

показан
1224 раза

обновлен
17 Апр '14 14:45

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

по почте:

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

по RSS:

Ответы

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

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