Разделы 
Дополнительно
Задача по математике - 3750
2019-06-16 
На шахматной доске размера $99 \times 99$ отмечена фигура (эта фигура будет разной в пунктах а), б), в)). В каждой клетке фигуры $\: Ф$ сидит по жуку. В какой-то момент жуки взлетели и сели снова в клетки той же фигуры $\: Ф$; при этом в одну клетку могло сесть несколько жуков. После перелета любые два жука, занимавшие соседние клетки, оказались снова в соседних клетках или попали на одну клетку. (Соседними называются клетки, имеющие общую сторону или общую вершину.)
а) Пусть фигура $\: Ф$ - это «центральный крест», т. е. объединение средней вертикали и средней горизонтали (рис. а). Докажите, что в этом случае какой-то жук вернулся на место либо перелетел в соседнюю клетку
б) Верно ли утверждение, если фигура - это «оконная рама», то есть объединение центрального креста и всех граничных клеток доски (рис. б)?
в) Верно ли утверждение, если фигура - это вся доска?
Решение:
а) Можно считать, что жук из центральной клетки сместился вправо на $k \geq 2$ клетки. Напишем в каждой из 49 клеток правого ряда, на какое число клеток по горизонтали сместился жук из соответствующей клетки; смещение вправо считаем положительным, влево - отрицательным. Очевидно, для самого правого жука смещение отрицательно, а написанные нами числа в соседних клетках отличаются не более чем на 2. Двигаясь по ряду от центральной клетки вправо, мы где-то должны «перейти через 0», поэтому одно из написанных чисел равно 1, 0 или -1, т. е. один из жуков должен сместиться не более чем на одну клетку.
б) На рис. приведен пример, когда все жуки оказываются далеко от своих начальных клеток (слева показано, какие номера мы приписываем каждому жуку, справа - куда должны лететь жуки с соответствующими номерами).
Ответ: утверждение не верно.
в) Докажем это утверждение сразу для прямоугольника из $m \times n$ клеток. Для квадратов $1 \times 1, 2 \times 2$ и прямоугольника $1 \times 2$ оно очевидно. (Вообще, для прямоугольников $1 \times n$ и $2 \times n$ его легко доказать так же, как а).) Пусть размеры прямоугольника $m \times n$ больше 2: $2 < m \leq n$. Мы докажем, что из него (отрезанием крайних рядов) можно получить меньший прямоугольник $П$, все жуки из которого вновь попадают в $П$, поэтому достаточно будет убедиться, что имеется нужный «почти неподвижный» жук.
Удобно измерять расстояние $p$ между клетками $A, B$ по числу ходов, за которые шахматный король может попасть из $A$ в $B$: множество клеток $M$ (на клетчатой бумаге), находящихся от данной клетки $C$ на расстоянии не большем $r$, для любого $r = 1, 2, \cdots$ заполняет квадрат $(2r + 1) \times (2r + 1)$ с центральной клеткой $C$. По условию, жук из клетки $k$ попадает в такую клетку $f(K)$, что для клеток $A, B$ на расстоянии 1 будет $ \rho (f(A),f(B)) \leq l$. Тогда для любых двух клеток $A$ и $B$
$\rho (f (A), f (B)) \leq \rho (A, B)$. (*)
В прямоугольнике $m \times n$ ($m \leq n$) будем называть «крайними» клетки, расстояние от которых до некоторых клеток прямоугольника равно $n-1$. Если $m < n$, такие клетки заполняют два крайних ряда (короткие стороны прямоугольника); в квадрате $n \times n$ они заполняют четыре крайних ряда (каемку). Заметим, что расстояние $p$ между двумя клетками противоположных крайних рядов равно $n - 1$, а для любых двух других клеток оно меньше.
Если в какой-то из крайних рядов не попадает ни один жук, то, убрав этот ряд, мы получим нужный прямоугольник $П$ размерами $m \times (n - 1)$; из любой клетки $k$ жук перелетает в клетку $f(K)$ из $П$.
В противном случае в качестве $П$ можно взять прямоугольник, полученный из данного отрезанием всех крайних рядов. Действительно, можно отметить несколько (две, три или четыре) клетки $K_i$ так, что в каждом крайнем ряду содержится одна из клеток $f(K_i)$. Поскольку $\rho (M, K_l) \leq n - 2$ для любой клетки $M$ из $П$ и каждой клетки K$_i$, то согласно (*) будет $\rho (f(M),f(K_i)) \leq n - 2$, а отсюда и из замечания о противоположных рядах следует, что $f(M)$ содержится в $П$.
Теперь доказательство очевидно проводится индукцией (по $n = max \{m, n \}$ или по $m + n$). Более того, из него следует, что всегда найдется квадрат $2 \times 2$ клетки, переходящий в себя.
Ответ: верно.
Эта задача - один из дискретных вариантов знаменитой теоремы Брауэра о том, что непрерывное отображение выпуклого множества в себя имеет неподвижную точку.
На шахматной доске размера $99 \times 99$ отмечена фигура (эта фигура будет разной в пунктах а), б), в)). В каждой клетке фигуры $\: Ф$ сидит по жуку. В какой-то момент жуки взлетели и сели снова в клетки той же фигуры $\: Ф$; при этом в одну клетку могло сесть несколько жуков. После перелета любые два жука, занимавшие соседние клетки, оказались снова в соседних клетках или попали на одну клетку. (Соседними называются клетки, имеющие общую сторону или общую вершину.)
а) Пусть фигура $\: Ф$ - это «центральный крест», т. е. объединение средней вертикали и средней горизонтали (рис. а). Докажите, что в этом случае какой-то жук вернулся на место либо перелетел в соседнюю клетку
б) Верно ли утверждение, если фигура - это «оконная рама», то есть объединение центрального креста и всех граничных клеток доски (рис. б)?
в) Верно ли утверждение, если фигура - это вся доска?
Решение:
а) Можно считать, что жук из центральной клетки сместился вправо на $k \geq 2$ клетки. Напишем в каждой из 49 клеток правого ряда, на какое число клеток по горизонтали сместился жук из соответствующей клетки; смещение вправо считаем положительным, влево - отрицательным. Очевидно, для самого правого жука смещение отрицательно, а написанные нами числа в соседних клетках отличаются не более чем на 2. Двигаясь по ряду от центральной клетки вправо, мы где-то должны «перейти через 0», поэтому одно из написанных чисел равно 1, 0 или -1, т. е. один из жуков должен сместиться не более чем на одну клетку.
б) На рис. приведен пример, когда все жуки оказываются далеко от своих начальных клеток (слева показано, какие номера мы приписываем каждому жуку, справа - куда должны лететь жуки с соответствующими номерами).
Ответ: утверждение не верно.
в) Докажем это утверждение сразу для прямоугольника из $m \times n$ клеток. Для квадратов $1 \times 1, 2 \times 2$ и прямоугольника $1 \times 2$ оно очевидно. (Вообще, для прямоугольников $1 \times n$ и $2 \times n$ его легко доказать так же, как а).) Пусть размеры прямоугольника $m \times n$ больше 2: $2 < m \leq n$. Мы докажем, что из него (отрезанием крайних рядов) можно получить меньший прямоугольник $П$, все жуки из которого вновь попадают в $П$, поэтому достаточно будет убедиться, что имеется нужный «почти неподвижный» жук.
Удобно измерять расстояние $p$ между клетками $A, B$ по числу ходов, за которые шахматный король может попасть из $A$ в $B$: множество клеток $M$ (на клетчатой бумаге), находящихся от данной клетки $C$ на расстоянии не большем $r$, для любого $r = 1, 2, \cdots$ заполняет квадрат $(2r + 1) \times (2r + 1)$ с центральной клеткой $C$. По условию, жук из клетки $k$ попадает в такую клетку $f(K)$, что для клеток $A, B$ на расстоянии 1 будет $ \rho (f(A),f(B)) \leq l$. Тогда для любых двух клеток $A$ и $B$
$\rho (f (A), f (B)) \leq \rho (A, B)$. (*)
В прямоугольнике $m \times n$ ($m \leq n$) будем называть «крайними» клетки, расстояние от которых до некоторых клеток прямоугольника равно $n-1$. Если $m < n$, такие клетки заполняют два крайних ряда (короткие стороны прямоугольника); в квадрате $n \times n$ они заполняют четыре крайних ряда (каемку). Заметим, что расстояние $p$ между двумя клетками противоположных крайних рядов равно $n - 1$, а для любых двух других клеток оно меньше.
Если в какой-то из крайних рядов не попадает ни один жук, то, убрав этот ряд, мы получим нужный прямоугольник $П$ размерами $m \times (n - 1)$; из любой клетки $k$ жук перелетает в клетку $f(K)$ из $П$.
В противном случае в качестве $П$ можно взять прямоугольник, полученный из данного отрезанием всех крайних рядов. Действительно, можно отметить несколько (две, три или четыре) клетки $K_i$ так, что в каждом крайнем ряду содержится одна из клеток $f(K_i)$. Поскольку $\rho (M, K_l) \leq n - 2$ для любой клетки $M$ из $П$ и каждой клетки K$_i$, то согласно (*) будет $\rho (f(M),f(K_i)) \leq n - 2$, а отсюда и из замечания о противоположных рядах следует, что $f(M)$ содержится в $П$.
Теперь доказательство очевидно проводится индукцией (по $n = max \{m, n \}$ или по $m + n$). Более того, из него следует, что всегда найдется квадрат $2 \times 2$ клетки, переходящий в себя.
Ответ: верно.
Эта задача - один из дискретных вариантов знаменитой теоремы Брауэра о том, что непрерывное отображение выпуклого множества в себя имеет неподвижную точку.
