в левой верхней клетке прямоугольной клетчатой поляны 11 на 12 сидят 7 жуков.За один ход один из жуков переползает на однуклетку вправо или на одну клетку вниз .через несколько…
В левой верхней клетке прямоугольной клетчатой поляны 11 на 12 сидят 7 жуков.За один ход один из жуков переползает на однуклетку вправо или на одну клетку вниз .через несколько ходов все жуки собрались в правой нижней клетке .Найдите наименьшее количество клеток не посещенных ни одним жуком
Чтобы решить задачу, нужно рассмотреть положение жуков на поле 11 на 12 клеток. Жуки начинают в верхнем левом углу (в клетке (1, 1)) и перемещаются в правый нижний угол (в клетку (11, 12)). Каждый жук может перемещаться только вправо или вниз за один ход.
Для того чтобы жуки собрались в правом нижнем углу, каждый из них должен пройти одинаковое количество клеток: 10 клеток вниз и 11 клеток вправо. Это означает, что каждый жук должен пройти в общей сложности 21 шаг, а целевое положение (11, 12) - это (10, 11) перемещений.
В процессе перемещения каждый жук будет занимать новую клетку. Однако важно заметить, что в пути жуки могут проходить через одни и те же клетки. Поэтому, чтобы минимизировать количество клеток, которые не были посещены жучками, необходимо определить, какие клетки будут посещены при минимальных перемещениях.
На нашем 11 на 12 поле (всего 132 клетки) каждый жук будет заниматься 21 клеткой, и так как у нас есть 7 жуков, это может привести к тому, что некоторые клетки будут посещены многократно.
Однако, если рассматривать, что жуки могут следовать по одному пути, например, сначала перемещаясь вправо, а затем вниз, или наоборот, можно организовать их движение так, чтобы они минимально перекрывались.
Предполагая, что жуки максимально координированы в своих движениях, выходит такая ситуация:
- Первые 7 клеток в правом нижнем углу могут быть заняты жуками, пока они движутся вниз.
- Таким образом, жуки покроют клетки в диапазоне от (1, 1) до (7, 12) и (11, 1) до (11, 12).
В результате, можно посчитать, что жуки, двигаясь таким образом (право и вниз), обязательно перекроют 21 клетку, а также общие клетки, куда они переступают в процессе.
Так, минимальное количество клеток, не посещённых ни одним жуком, будет равно:
132 (всего клеток) - 21 (посещенных клеток) = 111 клеток.
Таким образом, наименьшее количество клеток, не посещенных ни одним жуком, составляет 111.
