KV75.RU

О САЙТЕ
МАТЕМАТИКА
ИГРЫ
ИНТЕРНЕТ

Оценки и результаты в задаче о раскраске квадрата.

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

Итак, N - длина стороны квадрата.
Q(N) - максимально возможное число закрашенных ячеек.
Важную роль в данной задаче играет величина k(N) = [ √(N - 3/4) + 1/2 ].
При этом N может быть представлено в виде N = k2 - k + 1 + L,
где 0 ≤ L ≤ 2k-1.

Q' и Q'' - верхние оценки для величины Q(N), полученные мной.

Q' = [ N(k+1)/2 + N(N-1)/(2k) ] = Nk + [NL/(2k)].

Q'' = Nk + [Nk/(3k-L)].

Q'' ≤ Q' при N > k2+1.
Для N = k2+1 обе эти оценки дают одинаковый результат, который, тем не менее, иногда (скорее всего, при k≥3) завышен (например, при N=10).

Источники: 370858, 369472.