2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Комбинаторная задача о шахматных конях
Сообщение10.01.2013, 02:05 
Аватара пользователя
Можно ли на доске $4\times 4$ расставить чёрных и белых коней по одному в каждой клетке так, чтобы каждый белый конь бил ровно одного чёрного, а каждый чёрный конь бил ровно одного белого?

(А. Смирнов, Ленинградская олимпиада)

Если да, то сколькими способами это можно сделать?

Я нашла только один способ (с точностью до поворота доски): белые кони стоят на полях $a3, a4, b2, b4, c2, c4, d3, d4$, а на остальных полях -- чёрные.

Как найти остальные способы или доказать, что их нет?

 
 
 
 Re: Комбинаторная задача о шахматных конях
Сообщение10.01.2013, 11:02 
У меня получилась вот такая расстановка
$
\begin{pmatrix}
x_2 & \bar{x_3} & \bar{x_4} & \bar{x_1} \\
\bar{x_3} & x_3 & x_4 & \bar{x_4}\\
x_4 & \bar{x_4} & \bar{x_3} & x_3\\
x_1 & x_4 & x_3 & \bar{x_2}
\end{pmatrix}$
Т.е. задаем левый нижний и левый верхний углы, а также значения по стороне в центральном квадрате.
Ну и поскольку переменой цвета и транспонированием мы можем всегда вывести $x_1=x_2=0$, то получается 4 различных решения.

 
 
 
 Re: Комбинаторная задача о шахматных конях
Сообщение10.01.2013, 11:09 
Аватара пользователя
Cash, спасибо!
Как-то не додумалась перевести задачу на матричный язык.

 
 
 
 Re: Комбинаторная задача о шахматных конях
Сообщение10.01.2013, 12:19 

(Оффтоп)

Ну, от матричного языка здесь только запись ответа.
Я хотел как таблицу записать, но с tabularом у меня почему-то не сложилось.

 
 
 
 Re: Комбинаторная задача о шахматных конях
Сообщение10.01.2013, 14:22 
А как для больших размеров?

 
 
 
 Re: Комбинаторная задача о шахматных конях
Сообщение10.01.2013, 15:19 
Аватара пользователя
Yu_K в сообщении #669751 писал(а):
А как для больших размеров?

Для бОльших размеров, по-моему, невозможно.

 
 
 
 Re: Комбинаторная задача о шахматных конях
Сообщение10.01.2013, 15:21 
Аватара пользователя
Для $5\times 5$ нельзя, проверяется руками.

 
 
 
 Re: Комбинаторная задача о шахматных конях
Сообщение10.01.2013, 15:36 
Да, если поставить коня в центральную клетку и ещё 8, которых он бьёт, все остальные определяются однозначно.

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group