Идеальные совпадения на шахматной доске?

14

Рассмотрим проблему определения максимального количества рыцарей, которых можно разместить на шахматной доске, чтобы двое из них не атаковали друг друга. Ответ 32: найти идеальное соответствие не так уж и сложно (график, индуцированный ходами коня, является двудольным, и есть идеальное соответствие для доски 4 × 4), которая, очевидно, является минимальным краевым покрытием. Также нетрудно доказать, что ответ дляшахматной доскиm×nвсякий раз,когдаm,n3: достаточно показать соответствия для3m,n6и выполнить небольшую индукционную работу.mn2m×nm,n33m,n6

С другой стороны, если бы шахматная доска была тороидальной, а - четными, для доказательства даже не потребовалось бы показывать соответствие для небольших досок: карта ( x , y ) ( x + 1 , y + 2 ) имеет только циклы равной длины, поэтому должно быть идеальное соответствие.m,n(x,y)(x+1,y+2)

Есть ли какой-нибудь эквивалент для прямоугольных шахматных досок, т.е. есть ли более простой способ показать, что для достаточно больших всегда есть идеальное соответствие шахматной доски? Для больших досок прямоугольная доска и тороидальная доска почти эквивалентны в том смысле, что доля отсутствующих краев сводится к нулю, но я не знаю каких-либо теоретических результатов, которые гарантировали бы идеальное соответствие в этом случае.m,n

Что если вместо прыжка в любом направлении конь выпрыгнет ( 2 , 3 ) на квадраты в любом направлении? Или, в этом отношении, ( p , q ) квадраты, с p + q нечетным и p , q взаимно простым? Если это простой способ доказать , что ответ м п(1,2)(2,3)(p,q)p+qp,qдля достаточно большихm,n(скажем,m,nC(p,q)), как выглядитC(p,q)?mn2m,nm,nC(p,q)C(p,q)

ctgPi
источник
это хороший вопрос
Суреш Венкат
Я предполагаю, что рыцарский тур достаточно. Очевидно, закрытые туры всегда существуют, когда и m n четно. m,n>8mn
Тимоти Сан

Ответы:

9

Ответ НЕ для всех большихm,n,если, например,p=6иq=3. Почему? Обратите внимание, что из-за остатковmn2m,np=6q=3 теперь граф является (вершинным) непересекающимся объединением трех двудольных графов, и из каждого мы можем выбрать большую половину. Например, если m = n = 100 , то таким образом мы можем разместить (как минимум) 5002 коня. (Это потому что х + уmod3m=n=100 имеет шесть классов, которые находятся в трех парах, различия между количествами пар составляет 1 , 1 , 2. )x+ymod61,1,2

pqp+qpqp+q

domotorp
источник
О, хорошая мысль; Я изменил вопрос, чтобы отразить ваше наблюдение.
ctgPi