Играется круговой турнир с чётным числом участников (в шашки). Туры (т.е. кто с кем играет) назначались произвольно и наступил такой момент, что очередной тур невозможно составить. Вопросы:

1. Каков критерий? (т.е. как узнать не перебором, что очередной тур запустить невозможно)
2. За тур до описываемого события была возможность по-разному составить пары для игры. Каков критерий лушего выбора, т.е. существует ли такой ход (расписание) при которм турнир сможет продолжиться до конца?

Имхо, тема - полный оффтоп. Этот ответ - возможно (и вполне вероятно) бред .

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

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

Я склонна согласиться с Димой. Всё-таки это бриджевый форум, а не математический ( смотри описание форума)

Несмотря на мою симпатию к тебе, Алексей, и любовь ко всевозможным математическим задачам, я надеюсь, что в следующий раз ты найдёшь другую площадку для обсуждения подобных проблем.

Ко мне обратился Авгера с вопросом по поводу проведения бриджевых швейцарок. При большом числе команд в начале турнира ещё есть возможность по разному назначать туры, но он не знает критерия оптимального тура. Именно поэтому эта тема и была вынесена на обсуждение

Нормальная тема.
Критерий не знаю.