В левой верхней клетке прямоугольной клетчатой поляны 11 ×13 сидят1 жуков.Заодин ход один из жуков переползает на одну клетку вправо или на одну клетку вниз.Через несколько ходов все жуки собрались в правой нижней клетке. Найдите наименьшее количество клеток, не посещённых ни одним жуком.
Для решения данной задачи необходимо понять, как жуки перемещаются по клетчатому полю размером 11 × 13.
Каждый жук начинает в левой верхней клетке (0,0) и должен добраться до правой нижней клетки (10,12). Для этого жук может двигаться на одну клетку вправо или на одну клетку вниз.
Чтобы все жуки собрались в правом нижнем углу, каждому из них нужно сделать определенное количество шагов вправо и вниз. На этом пути жук пройдет через клетку (10,12), и для каждого из них общее количество шагов будет одинаковым: 10 шагов вниз и 12 шагов вправо. В итоге у нас будет 22 шага для каждого жука.
Теперь давайте выясним, какие клетки могут не быть посещены жуками. Жуки могут двигаться по любому маршруту, но один из минимальных маршрутов будет следовать вправо, а затем вниз, или вниз, а затем вправо. Таким образом, жуки будут проходить по всем клеткам, находящимся на линии между их стартовой позицией и конечной.
Клетки, которые могут остаться не посещёнными, будут теми, что находятся выше 10-й строки и правее 12-го столбца. Рассматривая размеры нашего поля, мы видим, что:
- В первой строке с 0 по 12 (всего 13 клеток).
- В первом столбце с 0 по 10 (всего 11 клеток).
Таким образом, все жуки, движущиеся и заканчивая свои движения, будут посещать клетки, находящиеся на пути от (0,0) до (10,12). Наиболее рациональный маршрут минимизирует количество не посещённых клеток.
В данном случае, единственные клетки, которые не будут посещены жуками, будут в самом верхнем ряду (строка 0) и последнем столбце (столбец 12), поскольку в пересеках жуки не будут ходить.
Если жуки расположены так, что один из них уже посещает 12-й столбец или 10-ю строку, с каждым шагом дополнительно, можно ожидать, что не посещённых клеток будет как минимум 1, то есть везде, где жуки не смогли пробраться.
В заключение, минимальное количество клеток, не посещённых ни одним жуком, может быть определено через более сложный анализ маршрутов, но для решения предложенной задачи, считают, что это будет минимально 1 клетка.
