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

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

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

Решение

Пусть центр клетки А — начало координат. Клетки Б имеют смещения с , то есть .

Для подходят ( клеток), для подходят (по клетки), для подходит только (по клетке). Всего клеток, вместе с самой А.

Индекс внутренней клетки: . Число не степень нечётного простого, поэтому такие клетки в М не входят.

Если произведение индексов равно , то каждый индекс делит и сам является степенью числа . Значит, все индексы в М — степени одного нечётного простого .

Пусть — расстояния до левого, правого, нижнего, верхнего краёв (нужны значения , или не меньше ). Считаем индексы у края:

угловая клетка: , это клеток, индекс ;
клетка на краю, не рядом с углом: клеток, индекс ;
клетка на краю, вторая от угла: индекс ;
клетка во втором ряду от края, вдали от углов: клеток, индекс ;
клетка по диагонали от угла (вторая в обоих направлениях): индекс .

Остаются индексы , , . Для каждого простого считаем клетки:

: только угловые клетки;
: по клетки у каждого из углов, всего ;
: клетки второго ряда и второго столбца вдали от углов.

Для в доске строка и столбца:

второй и предпоследний столбцы: строки с расстоянием не меньше до краёв, это строки …, то есть клеток в каждом, всего ;
вторая и предпоследняя строки: столбцы с расстоянием не меньше до краёв, это столбцы …, то есть клеток в каждой, всего .

Итого клетки, и это максимум, так как для и клеток намного меньше.

💡 Почему так

Если произведение чисел — степень простого , то каждое из чисел само степень . Поэтому все индексы в М должны быть степенями одного и того же простого числа, и выгоднее всего брать клетки с индексом .

Ответ

✓ dzmen.ru

Помогло?

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