Теорема Штайнхауза о шахматной доске
— Теорема Штейнхауза о шахматной доске это следующая теорема Хьюго Штейнхауза : [1]
Рассмотрим шахматную доску , на которой в некоторых клетках находятся мины . Тогда либо король может пересечь доску слева направо, не встретив заминированного поля, либо ладья может пересечь доску сверху вниз, двигаясь только по заминированным полям.
Двумерные варианты
[ редактировать ]Гейл [2] доказал вариант теоремы, в котором плитки на шахматной доске представляют собой шестиугольники, как в игре Hex . В этом варианте нет разницы между ходами короля и ладьи.
Кульпа, Соча и Турзанский [1] доказать обобщенный вариант теоремы о шахматной доске, в котором доску можно разбить на произвольные многоугольники, а не только на квадраты. Они также дают алгоритм для поиска маршрута короля или ладьи.
n-мерные варианты
[ редактировать ]Ткач и Турзанский [3] обобщить теорему о шахматной доске на n-мерную доску:
Рассмотрим сетку из n-мерных кубов. Раскрасьте каждый кубик одним из n цветов 1,..., n . Тогда существует набор кубиков, окрашенных в цвет i , которые соединяют противоположные стороны сетки в измерении i .
Альбах [4] представить доказательство Ткача и Турзанского n -мерной теоремы о шахматной доске и использовать его для доказательства теоремы Пуанкаре-Миранды . Интуитивная идея заключается в следующем. Предположим от противного, что n -мерная функция f , удовлетворяющая условиям теоремы Миранды, не имеет нуля. Другими словами, для каждой точки x существует хотя бы одна координата i, которой fi для ( x ) не равно нулю. Раскрасим каждую точку x в некоторый цвет i, для которого f i ( x ) не равно нулю. По теореме Штейнхауза о шахматной доске существует некоторый i , для которого существует путь из точек цвета i, соединяющий две противоположные стороны в измерении i . По условиям Пуанкаре-Миранды fi )> 0 ( x в начале пути и fi ( )< 0 x в конце пути, и функция непрерывна вдоль пути. Следовательно, на пути должна быть точка, на которой f i ( x )=0 – противоречие.
См. также
[ редактировать ]- Другая теорема Штейнгауза, связанная с расстановкой ладей на шахматной доске, которую можно доказать с помощью теоремы Холла о браке . [5]
Ссылки
[ редактировать ]- ^ Перейти обратно: а б Кулпа, Владислав; Соча, Леслав; Туржанский, Мариан (2000). «Теория шахматной доски Штейнгауза» . Журнал Университета Каролины. Математика и физика 041 (2): 47–50. ISSN 0001-7140 .
- ^ Гейл, Дэвид (декабрь 1979 г.). «Игра в шестнадцатеричные числа и теорема Брауэра о неподвижной точке» . Американский математический ежемесячник . 86 (10): 818–827. дои : 10.1080/00029890.1979.11994922 . ISSN 0002-9890 .
- ^ Ткач, Пшемыслав; Туржанский, Мариан (1 января 2008 г.). «N-мерная версия теоремы Штейнхауза о шахматной доске» . Топология и ее приложения . Труды десятого Пражского симпозиума по общей топологии и ее связи с современным анализом и алгеброй. 155 (4): 354–361. дои : 10.1016/j.topol.2007.07.005 . ISSN 0166-8641 .
- ^ Альбах, Коннор (12 мая 2013 г.). «Дискретный подход к теореме Пуанкаре-Миранды» . Старшие диссертации HMC .
- ^ Моравец, Адам (01 марта 2019 г.). «О ладьях, браках и матчах, или Штейнгауз через Холл» . Графы и комбинаторика . 35 (2): 503–511. дои : 10.1007/s00373-019-02015-4 . ISSN 1435-5914 .