img img img img img img img img img img img img img img img img img img img img img img
Логотип Человек живет, пока думает.
Решайте задачи и живите долго!
Для участия в проекте необходимо
и достаточно зарегистрироваться!
Rss Регистрация || Вход
Вход
Diofant.ru
Картинка
Отражение Отражение Картинка Картинка
отражение
Лента событий: MMM добавил комментарий к задаче "Дедушка и полтаблетки" (Математика):
+ 10

Задача 779. Змейка из клеток

постоянный адрес задачи: http://www.diofant.ru/problem/2411/
показать код для вставки на свой сайт >>
Задачу решили: 45
всего попыток: 76
поделиться задачей:

Задача опубликована: 20.08.12 08:00
Прислал: georgp img
Вес: 1
сложность: 1 img
класс: 8-10 img
баллы: 100
Лучшее решение: zmerch

Рассмотрим одноклеточное существо змейку – фигуру, первоначально содержащую один квадрат и растущую в плоскости за счет прибавления квадратных клеток того же размера к какой-нибудь его стороне. Стороны этой фигуры не должны выходить за пределы квадрата 1999 на 1999. Найти максимальное число клеток, которое может иметь связная фигура (в комбинаторике такая фигура называется полимино). Связность заключается в том, что в ней нет дыр. Кроме того, никакая точка фигуры не может одновременно принадлежать четырем клеткам, а каждая клетка не может иметь только одну точку общую с остальными клетками. 

Для иллюстрации приведен рисунок, показывающий процесс роста фигуры и запрещенные позиции, которые не может содержать фигура в процессе своего роста.

       ПРОЦЕСС РОСТА ФИГУРЫ                                                          

222.png

       ЗАПРЕЩЕННЫЕ ПОЗИЦИИ

    333.png                                                                           

             a)           b)         c)

 
Пожалуйста, не пишите нам, что Вы не можете решить задачу.
Если Вы не можете ее решить, значит Вы не можете ее решить :-)

Обсуждение Правила >>

Внимание! В обсуждении задачи запрещено публиковать ответы и давать подсказки.
Аватар 20.08.12 11:51

В зависимости от того, что есть дыра (или в каком смысле понимается связность), возникают разные задачи. Ждём разъяснений.

Мне нравится: + | пожаловаться
Аватар 20.08.12 19:41

Может быть я что-то не понял, но в данной задаче мне кажется, что условие полностью ясно (да и мой ответ был принят). Как раз приведно 3 примера (a, b, c) чего запрешенно, а остальное разрешенно. Попробуйте придумать фигуру, для которой не понятно из условия, "законная" ли она или нет.

Может быть такая формулировка: А. Из каждой клеточки фигуры можно перейти к любой другой по сторонам квадратиков: вверх, вниз, вправо, влево. Б. Из каждой клеточки (внутри квадрата 1999 на 1999), НЕ ПРИНАДЛЕЖАЩЕЙ фигуре, можно таким же образом "выйти наружу". В. Запреты "b" и "c".

Мне нравится: + | пожаловаться
Аватар 29.08.12 09:50

 <<Попробуйте придумать фигуру, для которой не понятно из условия, "законная" ли она или нет.>>

Да, существует ПРОЦЕСС РОСТА ФИГУРЫ (змеи) до 21-ой клетки! на квадрате 5*5 - И непонятно: "законная" ли она или нет, поскольку доказательство МАКСИМАЛЬНОСТИ ответа и к этой задаче 5*5, и к данной 779 при АВТОРСКОМ(!) условии оказывается совершенно очевидным!

Мне нравится: + | пожаловаться
 
Внимание! Если Вы увидите ошибку на нашем сайте, выделите её и нажмите Ctrl+Enter.