Question

В каждой клетке квадрата 11x11, кроме одной, сидит по жуку. У всех жуков получилось одновременно переползти в соседнюю по стороне клетку так, что в каждой клетке вновь оказалось не более одного жука, а свободное изначально место оказалось занято. Сколько есть вариантов расположения клетки, в которой изначально не было жука?

Answer 1

Ответ:

120

Пошаговое объяснение:

В любом варианте расположения, кроме одного (когда пустая клетка в центре), будет выполняться условие "свободное изначально место оказалось занято". А всего клеток 11x11=121

Answer 2

Данная задача является классической задачей теории графов, и для её решения можно использовать графовые подходы. Предположим, что каждая клетка квадрата 11x11 представляет собой вершину графа, и две вершины соединены ребром, если клетки соседние по стороне.

Мы ищем количество вариантов расположения пустой клетки таких, чтобы все жуки переместились в соседние клетки. Это эквивалентно поиску эйлерова цикла в графе, так как в начальной позиции у нас есть эйлеров цикл (все жуки занимают клетки и есть замкнутый маршрут, по которому каждый жук может переместиться в соседнюю клетку).

Эйлеров цикл — это цикл в графе, который проходит через каждое ребро ровно один раз. Он существует только в том случае, если все вершины имеют четную степень (количество ребер, выходящих из вершины).

В нашем случае каждая вершина графа (клетка квадрата) имеет степень 4 (каждая клетка имеет четырех соседей по стороне). Кроме того, у нас есть одна вершина (пустая клетка), которая имеет степень 0. Таким образом, у нас есть 122 вершины с четной степенью (каждая с жуком) и одна вершина с нулевой степенью (пустая клетка).

Для того чтобы найти количество эйлеровых циклов в таком графе, можно использовать формулу Эйлера:

C = (m/2)^(n-1)

где C - количество эйлеровых циклов, m - количество вершин с четной степенью (в данном случае 122), n - общее количество вершин (в данном случае 123).

Подставим значения:

C = (122/2)^(123-1) = 61^122

Таким образом, количество вариантов расположения клетки, в которой изначально не было жука, равно 61^122, что является очень большим числом.