Отметьте несколько клеток в этом квадрате 4 × 4… (математика)

№ Выбор клеток без общих точек с наибольшей суммой

Отметьте несколько клеток в этом квадрате $4 \times 4$ так, чтобы никакие две отмеченные клетки не имели общей точки, а сумма чисел в отмеченных клетках была максимально возможной.

5	6	7	8
16	17	18	9
15	20	19	10
14	13	12	11

Решение

Разобьём квадрат на четыре квадрата . В каждом из них можно отметить не больше одной клетки, иначе у двух клеток будет общая точка. Значит, отметить можно не больше клеток, а так как все числа положительные, выгодно отметить ровно : по одной в каждом квадрате .

Квадраты:

левый верхний: , , , ;
правый верхний: , , , ;
левый нижний: , , , ;
правый нижний: , , , .

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

Берём . Тогда в левом нижнем квадрате остаётся только , в правом верхнем — или , в правом нижнем — , или . Лучший вариант: .
Берём . Тогда в левом верхнем квадрате остаётся или , в правом верхнем — , или , в правом нижнем — или . Лучший вариант: .
Берём . Тогда остаются (левый верхний), (правый верхний), (левый нижний). Сумма: .
Берём . Тогда в левом верхнем квадрате остаются и , в левом нижнем — , и , в правом нижнем — и . Лучший вариант: .
Если центральные клетки не берём, то суммы будут меньше (в каждом квадрате остаются числа не больше , , , , и подходящих по условию наборов с суммой больше нет).

Наибольшая сумма:

Проверка: клетки и стоят во второй строке через одну клетку, и — в четвёртой через одну клетку, а между второй и четвёртой строками есть третья строка, поэтому общих точек нет.

💡 Почему так

В каждом квадрате можно отметить не больше одной клетки, поэтому отмеченных клеток не больше четырёх. Перебор показал, что наибольшая сумма — .

Ответ

✓ dzmen.ru

Отметить клетки , , , . Сумма равна .

Помогло?

Отметьте несколько клеток в этом квадрате 4 × 4 так, чтобы никакие…