Форум умных людей

Все в детстве любили рисовать и раскрашивать раскраски. Правда ведь?  :)

Для тех, у кого детство ещё не кончилось, предлагаю оригинальную головоломку-раскраску.
Раскраска эта с текущего конкурса программистов
http://infinitesearchspace.dyndns.org/monosquares
[я здесь вроде тему открывала об этом конкурсе; интереснейший конкурс! жалко, что здесь конкурс не вызвал интереса; на форуме dxdy.ru тема о конкурсе огромная, обсуждение активное, много участников, то есть участники обсуждения они же и участники конкурса; я тоже в конкурсе участвую].

Раскраcку выложил на форуме конкурса один участник - Tom Sirgedas.

(http://www.natalimak1.narod.ru/C5N27new.jpg)

Вы видите квадрат 27х27, можно назвать его сеткой 27х27. Каждую ячейку этого квадрата надо окрасить в один из 5 цветов. На картинке уже один цвет залит, это для первого цвета максимум ячеек, которые можно окрасить одним цветом в квадрате 27х27, чтобы не возникало запрещённых прямоугольников.

Что такое запрещённый прямоугольник? Это такой прямоугольник с вершинами в центрах ячеек сетки, в котором все 4 вершины одинаково окрашены, то есть одноцветные.

Вот теперь надо взять ещё 4 цвета (любых, кому какие нравятся, конечно, голубой уже не будем брать) и продолжить раскрашивание этого квадрата 27х27 так, чтобы не возникало запрещённых прямоугольников.

Решите головоломку - прославитесь на весь мир  :)

Такое решение на конкурсе ещё не нашли. Неизвестно даже, существует ли оно вообще.
Максимальный квадрат, который удалось раскрасить в 5 цветов, это квадрат 25х25.
Доказано, что раскрасить в 5 цветов квадрат 28х28 невозможно.
Что касается квадратов 26х26 и 27х27, тут ничего пока неизвестно.

Покажу квадрат 25х25, раскрашенный в 5 цветов:

(http://www.natalimak1.narod.ru/C5N25.jpg)

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

Ну, вот, например, так я начала раскрашивать вторым цветом:

(http://www.natalimak1.narod.ru/C5N27Ex.jpg)

Это, может быть, плохо, я не знаю  :) Сейчас попробую третьим цветом раскрашивать. Пока в раскраске нет ошибок.

Кстати, к конкурсу прикреплена замечательная программа, в которой можно вручную раскрашивать, там сразу видно ошибки, когда запрещённые прямоугольники появляются.
На главной странице конкурса ссылка на программу.

Но... вряд ли удастся эту раскраску одолеть вручную. Нужна, конечно, хорошая программа.

Алгоритм решения этой задачи достаточно прост:
имея поле 27х27 разрисовано 5-ю цветами, из которых уже размещения одного цвета известно может быть всего:
4 ^{(27 * 27 - 147)} = 2,5056e+350 комбинаций.
(27 * 27 - 147) - количество не закрашенных ячеек
4 - количество не использованных цветов
Если учитывать что на проверку каждой комбинации нужно не менее (27 * 27 - 147) операций, тогда проведя такие вычисления одновременно на 1млн компьютеров с вычислительной способностью 10 ¹⁵ операций в секунду получим:
2,5056 e +350 * (27 * 27 - 147) / (10 ¹⁵ * 10 ⁶) = 1,4583 e +332 сек = 1,6878 e +327 дней = 4,6242 e +324 лет.

Задача решена! Нужно только время  :laugh:

и еще столько же чтобы  перепроверить  :crazy:

Чего-о-о-о перепроверить?
Если в готовой раскраске будут ошибки, программа проверки найдёт их за сотую долю секунды.

Да, уж... Решили задачу. Ну, точно, то ж умные люди :)