Дана клетчатая доска 102 × 105… (вероятность и статистика)

№ Клетчатая доска, индексы клеток

Дана клетчатая доска $102 \times 105$ , размер каждой клетки $1 \times 1$ . Для каждой клетки A посчитали количество клеток Б, отличных от клетки A, таких, что расстояние между центрами клеток A и Б не больше 2. Это число будем называть индексом клетки A. На доске выделили максимальное по количеству клеток множество M клеток, произведение индексов которых — степень нечётного простого числа. Сколько клеток содержит множество M?

Решение

Центры клеток находятся в узлах решётки. Клетка Б лежит на расстоянии не больше от клетки A, если сдвиг удовлетворяет условию . Таких сдвигов , включая . Это:

: ( сдвигов);
: ( сдвигов);
: ( сдвига).

Для внутренней клетки индекс равен . У клеток возле границы часть сдвигов выходит за доску.

По каждой оси клетка бывает трёх типов:

Е — крайняя;
S — вторая от края;
М — остальные (на расстоянии не меньше от обоих краёв).

Считаем индекс для каждой пары типов (первый тип — по горизонтали, второй — по вертикали):

	E	S	M
E
S
M

Индексы , , чётные, поэтому такие клетки в M не входят. Остаются индексы , и . Это степени разных простых чисел, а произведение индексов должно быть степенью одного простого числа. Поэтому в M можно брать клетки только с одним значением индекса.

Считаем клетки с каждым значением:

Индекс (углы): клетки.
Индекс (типы E,S и S,E): клеток.
Индекс (типы S,M и M,S): клеток.

Максимум достигается на индексе .

💡 Почему так

Индекс клетки зависит только от её близости к границе. Произведение индексов может быть степенью одного простого числа только если все индексы — степени этого числа, поэтому берём клетки с одним значением индекса. Больше всего их с индексом .

Ответ

✓ dzmen.ru

Помогло?

Дана клетчатая доска 102 × 105, размер каждой клетки 1 × 1.…