Автор Тема: Вылечить всех пчел  (Прочитано 532 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн hripunov

  • Эксперт
  • ******
  • Сообщений: 5433
    • Просмотр профиля
    • E-mail
Вылечить всех пчел
« : 24 Март 2019, 02:41:15 »
Имеются пчелиные  соты из 37 ячеек, расположенные как показано на рисунке. Здоровой ячейкой назовем ту, где живет здоровая пчела. Нездоровая  ячейка - та, где пчела нуждается в медицинской  помощи.
Действует закономерность: если три здоровые ячейки имеют общую сторону с нездоровой, то эта нездоровая становится здоровой. Затем процесс продолжается.
В стартовой позиции все ячейки нездоровые.

Требуется единовременно заменить минимально необходимое  количество ячеек на здоровые, чтобы запустился процесс оздоровления, который сделает здоровыми все ячейки.

1)   Отметить здоровые ячейки  на стадии запуска  процесса
2)   Доказать, что заменено минимально необходимое  количество ячеек.

« Последнее редактирование: 24 Март 2019, 02:43:11 от hripunov »
Сеня! По-быстрому объясни товарищу, почему Володька сбрил усы!...

Оффлайн Artem of 93

  • Эксперт
  • ******
  • Сообщений: 1530
    • Просмотр профиля
    • Mozgovarka
Re: Вылечить всех пчел
« Ответ #1 : 24 Март 2019, 13:31:20 »
По пункту 1 задачи предположу, что достаточно 8 здоровых ячеек в начале. Для наглядности прилагаю рисунки каждого шага, где зелёным цветом обозначены здоровые ячейки.

Оффлайн hripunov

  • Эксперт
  • ******
  • Сообщений: 5433
    • Просмотр профиля
    • E-mail
Re: Вылечить всех пчел
« Ответ #2 : 24 Март 2019, 15:19:33 »
Artem of 93, близко, но можно еще чуточку поменьше.
Для разминки можно сначала найти вариант для других сеток.  Ясно, что для сетки из семи ячеек (одна в центре, шесть вокруг) - нужно изначально оздоровить три ячейки. А вот для сетки из 19 ячеек, изображенной на рисунке, потребуется 5 ячеек.  Если найти это решение для сетки из 19-ти,   то для остальных подобных сеток , даже если они огромного размера, будет подходить аналогичная  схема  решения.
Сеня! По-быстрому объясни товарищу, почему Володька сбрил усы!...

Оффлайн Artem of 93

  • Эксперт
  • ******
  • Сообщений: 1530
    • Просмотр профиля
    • Mozgovarka
Re: Вылечить всех пчел
« Ответ #3 : 24 Март 2019, 15:35:40 »
Artem of 93, близко, но можно еще чуточку поменьше.

Может быть, 7 ячеек достаточно? Рисунки ниже.

Оффлайн hripunov

  • Эксперт
  • ******
  • Сообщений: 5433
    • Просмотр профиля
    • E-mail
Re: Вылечить всех пчел
« Ответ #4 : 24 Март 2019, 18:35:16 »
Artem of 93, верно  :bravo:!

Уменьшить количество стартовых здоровых ячеек не получится. Семь, и не меньше.    В том, чтобы это доказать, состоит второй вопрос задачи!
Сеня! По-быстрому объясни товарищу, почему Володька сбрил усы!...

Оффлайн Artem of 93

  • Эксперт
  • ******
  • Сообщений: 1530
    • Просмотр профиля
    • Mozgovarka
Re: Вылечить всех пчел
« Ответ #5 : 24 Март 2019, 19:08:06 »
В том, чтобы это доказать, состоит второй вопрос задачи!

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

Очевидно, что к каждой ячейке максимально прилегают ещё шесть таких же ячеек. Значит, одна ячейка может "поучаствовать" в лечении максимум шести ячеек через некоторое количество шагов. На рисунке ниже расставим шесть здоровых ячеек (зелёные) таким образом, чтобы ячейки вокруг них заполнили как можно больше пространства. Как видно на рисунке, у нас есть смежные ячейки (фиолетовые). Количество несмежных ячеек (жёлтые) вокруг каждой здоровой ячейки максимально может достигать четырёх. Также вокруг шести здоровых ячеек есть шесть смежных. Значит, на каждую здоровую ячейку приходится пять неповторяющихся ячеек, которые эта здоровая ячейка может теоретически излечить через некоторое количество шагов.

У нас всего 37 ячеек. Если мы поставим на стартовой позиции 6 здоровых ячеек, то 31 ячейка останется нездоровой. 31/6 больше 5. Значит, 6 и менее здоровых ячеек не дадут нам излечение 31 нездоровой ячейки через любое сколько угодно большое количество шагов.

Оффлайн hripunov

  • Эксперт
  • ******
  • Сообщений: 5433
    • Просмотр профиля
    • E-mail
Re: Вылечить всех пчел
« Ответ #6 : 25 Март 2019, 01:57:05 »
Artem of 93, это вроде бы  вполне  убедительное доказательство.  У меня - другое; я его попозже выложу.   А по поводу комбинаций, надеюсь, всем очевидно: найденный способ позволяет решить задачу для сетки такой формы любого размера: 19, 37, и т.д. в сторону увеличения.  А требуемое количество   здоровых ячеек будет равно:  N *2 - 1 , где N - количество ячеек в нижнем ряду.
« Последнее редактирование: 25 Март 2019, 01:59:43 от hripunov »
Сеня! По-быстрому объясни товарищу, почему Володька сбрил усы!...

Оффлайн hripunov

  • Эксперт
  • ******
  • Сообщений: 5433
    • Просмотр профиля
    • E-mail
Re: Вылечить всех пчел
« Ответ #7 : 26 Март 2019, 13:21:13 »
Доказательство может быть очень простым: при названных условиях появления новых здоровых ячеек суммарный периметр всех здоровых фигур не увеличивается. Значит и в самом начале он не может быть меньше 42.
Сеня! По-быстрому объясни товарищу, почему Володька сбрил усы!...