Главное меню

Как решить: дан клетчатый прямоугольник 5×7, где отмечены некоторые клетки?

Автор Tol, Март 15, 2024, 03:55

« назад - далее »

Tol

Дан клетчатый прямоугольник 5×7, на котором отмечены некоторые клетки. Известно, что любой трёхклеточный уголок на этой доске покрывает хотя бы 2 отмеченные клетки. Какое наименьшее количество клеток может быть отмечено?

Edin

Ознакомившись с вашим вопросом могу сказать, что данную задачку довольно легко решить, для начала нам стоит изобразить прямоугольник 5 (пять) на 7 (семь) на листе в клеточку или на простом листе. После этого нам остается закрасить трехклеточные уголки как сказано в данном задании. После этого вы сможете увидеть что в данном прямоугольнике 12 (двенадцать) клеток будут не закрашены и 23 (двадцать три) будут закрашены это и будет ответом на данное задание.
Ответ: 23
                                                                              

Eneta

Для начала давайте оценим такое количество. В прямоугольнике 5 х 7 будет 35 клеток
Предположим мы как то замостили весь прямоугольник не пересекающимися уголками из 3-х клеток. Таких уголков будет минимум 11 по 3 = 33 клетки и ещё 2 клетки останутся.
11 уголков должны иметь по 2 метки - это 22 клетки должны быть помечены.
И в две пустые клетки можно поместить часть уголка, который в лучшем варианте может иметь только 1 метку в третьей клетке и тогда понадобится ещё 1 метка в эти две клетки.
Итого получили 22+1 = 23 метки необходимо точно. Меньше нельзя.
Теперь нужен пример.
Для решения задачи нарисуем уголок из трех клеток и попробуем расставить две метки
Рассмотрим два случая: 1) метки по диагонали и 2) метки рядом.
В обоих случаях, если в этот же квадрат из четырех клеток вставить другой уголок (красный), то у него будет только одна метка. И для выполнения условия в такой квадрат надо  ставить более двух меток.
То есть должны быть места, где помечены три клетки.
Поэтому получим следующий пример
 Тут как раз 23 помеченных клетки.
Предоставили оценку + пример
Ответ: минимум 23 помеченных клетки.