Как додуматься до примера в задаче для 6 класса

[problemslover]

Доброго времени суток!

Имеется такая задача: закрасьте не менее 18 клеток доски 5х5 так, чтобы любая закрашенная клетка граничила по стороне не более, чем с двумя закрашенными клетками.

Понятное дело, что можно строить пример "на удачу", но, думаю, что таким способом вряд ли получится получить результат лучше 17 закрашенных клеток за небольшое время, а задача как раз с мат. боя, поэтому времени на неё дается мало. Нужна ваша помощь, какими соображениями тут можно помочь себе придумать пример (разумеется, помощь нужна только от тех, кто сможет решить задачу).

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

[ozheredov]

problemslover

Я придумал т.н. жадный алгоритм: понятно, что положение в углах и по сторонам (в таком порядке приоритетов) минимизирует число соседей. Ну и расставил всех по периметру. Потом добавил "аппендикс" из еще двух клеток, получилась НЕзакрашенная буква "пе".

[svv]

problemslover в сообщении #1622709 писал(а):

Нужна ваша помощь, какими соображениями тут можно помочь себе придумать пример (разумеется, помощь нужна только от тех, кто сможет решить задачу).

Привожу свои соображения.

Используется синтаксис C++

#include <iostream>
using namespace std;

int main()
{
   const int N=5, M=7, NN=N*N;
   bool A[N][N];
   int Y[NN],X[NN];
   {
      int b=0;
      for (int y=0; y<N; ++y)
      for (int x=0; x<N; ++x, ++b)
      {
         A[y][x]=true;
         Y[b]=y;
         X[b]=x;
      }
   }

   int B[M];
   for (int m=0; m<M; ++m)
      B[m]=m;

   int counter=0;
   while (true)
   {
      for (int m=0; m<M; ++m)
      {
         int b=B[m], y=Y[b], x=X[b];
         A[y][x]=false;
      }

      bool Success=true;
      for (int y=0; y<N && Success; ++y)
      for (int x=0; x<N && Success; ++x)
      {
         if (!A[y][x]) continue;
         int neigh=0;
         if (x>0   && A[y][x-1]) ++neigh;
         if (x<N-1 && A[y][x+1]) ++neigh;
         if (y>0   && A[y-1][x]) ++neigh;
         if (y<N-1 && A[y+1][x]) ++neigh;
         if (neigh>2)
            Success=false;
      }

      if (Success)
      {
         char c[N+1];
         c[N]='\0';
         for (int y=0; y<N; ++y)
         {
            for (int x=0; x<N; ++x)
               c[x]=A[y][x]? '*': ' ';
            cout << "[" << c << "]\n";
         }
         cout << "\n";
         ++counter;
      }

      for (int m=0; m<M; ++m)
      {
         int b=B[m], y=Y[b], x=X[b];
         A[y][x]=true;
      }

      int m;
      for (m=M-1; m>=0; --m)
         if (B[m]<NN-M+m) break;
      if (m==-1) break;
      for (++B[m++]; m<M; ++m)
         B[m]=B[m-1]+1;
   }
   cout << counter << " solution(s)\n";
}
 

Запустите, например, здесь.

[waxtep]

svv в сообщении #1622733 писал(а):

Привожу свои соображения.

Неужели, таки возможно? Запустить на исполнение у меня не получилось, видимо что-то не так делаю.
Промучавшись энное количество времени, я предполагал двигаться в сторону доказательства невозможности такой раскраски, следующим занудным образом:
- в первых двух строках может быть не более $8$ закрашенных клеток, причем если их ровно $8$ - в третьей строке будет максимум одна закрашенная клетка, и итого мы получим максимум $8+1+8=17$ закрашенных клеток (квадратики $2\times2$ по углам и клетка в центре; не единственный вариант для $17$ закрашенных клеток);
- другие возможные варианты: $7,5,6$ или $7,4,7$ закрашенных клеток в первых двух, третьей и последних двух строках, соответственно. В недостижимости первого варианта убедиться легко, да и второго кажется нетрудно...

-- 17.12.2023, 04:56 --

ozheredov в сообщении #1622718 писал(а):

Потом добавил "аппендикс" из еще двух клеток, получилась НЕзакрашенная буква "пе".

Тут у одной закрашенной клеточки под этой "П" будет три закрашенных соседа

[svv]

waxtep, сделайте, пожалуйста, ещё одну попытку.
Откройте ту страничку. Имеющуюся в окошке демо-программу сотрите, а мою вставьте. И ниже окошка нажмите кнопку Execute кирпичного цвета (она есть, только надо немного прокрутить содержимое странички). Программа подумает (от силы секунд 10) и выдаст 2 решения.
Получилось?

[waxtep]

svv, да, со второго раза получилось все таки $7,4,7$ значит:

[* ***]
[ ** *]
[** **]
[* ** ]
[*** *]

[*** *]
[* ** ]
[** **]
[ ** *]
[* ***]

2 solution(s)

[svv]

Ага!

[wrest]

Удивительное рядом.
Я вчера тоже минут 40 переставлял в экселе фишки, безуспешно.
Обычных змей сделал несколько но вот что можно уроборос скрутить - не допёр.
Уже думал открою PARI/GP да переберу всё. Открыл форум, а тут уже...

В решении, оказывается, аж две клетки не имеют соседей (угловые), так что всего соседей 16, что тоже удивительно. У каждого (кроме двух на выселках) по два, т.е. всего соседких отношений 32. А я стремился к 36.

Мне кажется, это не для 6 класса... А вопрос ТС остается актуальным -- а как тут догадаться-то?

[svv]

Для $6\times 6$ оптимальное решение тоже одно (с точностью до) и строится аналогично:

[waxtep]

svv в сообщении #1622833 писал(а):

Для $6\times 6$ оптимальное решение тоже одно (с точностью до) и строится аналогично:

В OEIS соответствующей последовательности $1,4,8,12,18,26,\ldots$ нет; ну, точнее, она есть - A311642 , но как будто бы не совсем о том, что-то на тему классификации покрытий плоскости. А вы говорите, как додуматься
И, да, имеющаяся в OEIS последовательность точно не о том: она немонотонна

[problemslover]

Ох, как замечательно. Вот почему пример так нелегко ищется - он, оказывается, единственный.

Единственные соображения, которые приходят в голову, но уже, честно говоря, после того, как увидел решение - это то, что можно попытаться упростить себе задачу с помощью симметрии, т.е. заполнить одну половинку с диагональю, но опять же неоткуда не следует, что пример будет симметричным, так что это тоже в своем роде удача. Возможно, если иметь опыт в решении подобных задач, то это будет казаться естественным ходом. Также можно перейти к незакрашенным клеткам.

Насчет оптимальности: вряд ли тут поможет раскраска какая-нибудь, возможно, только как-то по индукции нужно идти. Если перейти к незакрашенным клеткам, то при $n = 3, 4, 5, 6$ получится 1, 4, 7, 10, то есть $3n - 8$

[waxtep]

problemslover в сообщении #1623039 писал(а):

Если перейти к незакрашенным клеткам, то при $n = 3, 4, 5, 6$ получится 1, 4, 7, 10, то есть $3n - 8$

Здесь, кажется, другая тема: если рассматривать аналогичные незакрашенные диагональки для любого $n=3k+r\geqslant3$, то, во-первых, это будет допустимой раскраской, а, во-вторых, количество незакрашенных клеток в ней будет равно

$$w=n-2+2\sum\ind_{i=0}^{k-1}(3i+r)=3k^2+2rk+r-2$$

Т.е. все таки квадратично по $n$, а не линейно, что кажется логичным. Можно ли еще меньше? Пока неясно

-- 21.12.2023, 02:56 --

И это вот эта штуковина: A071408

A071408 писал(а):

a(n+1) - 2*a(n) + a(n-1) = (2/3)*(1 + w^(n+1) + w^(2*n+2)) with a(1)=0, a(2)=1, and where w is the imaginary cubic root of unity.

-- 21.12.2023, 03:05 --

А вот это, судя по всему, количество закрашенных клеток в таких раскрасках "с белыми диагональками": A053799

A053799 писал(а):

Number of basis partitions of n+9 with Durfee square size 3