- В этой теме 49 ответов, 12 участников, последнее обновление 13 лет, 10 месяцев назад сделано
.
-
Сообщения
-
Ну если два лидера, то согласен. А если три ? 😆 Или так — лидеров два, а выходящих мест одно 💡
А вообще-то в Америке почти все турниры проводятся по швейцарке, и я всю эту статистику на своей шкуре испытал. Могу сказать одно — для 16-24 участников достаточно 7-8 туров, для 25-36 — около 9.
АЛЕМО
А Вас, Александр, не удивляет, что системы линейных уравнений, если не ошибаюсь, 11-го порядка не под силу современной вычислительной технике?
Но ведь на решение надо O(n^3) операций умножения и деления, почему им не удается решить системы из 11 уравнений?
И все-таки на изначальный вопрос о максимальном k ответ дан верный — n-2.
Речь надо вести о минимальном k, при котором мы можем столкнуться с данной проблемой.
Очевидно, что k>n/2. Поэтому, исходя из практики, вопрос отпадает сам собой.
Предлагаемые критерии.
1. Спуски подъемы.
2. Цвет.
3. Коэффициент.Причем
А. Нельзя играть одним цветом более трех раз подряд. Ещё лучше, на случай судьи-ортодокса и, к тому же, если речь будет идти о поединке из одной партии, должна быть возможность уменьшить вручную это число до «двух».
Б. Если по результатам пункта 1. количество претендентов на спуск (подъем) более одного, повышается игрок с минимальным коэффициентом, понижается — с максимальным.
С. На распределение пар внутри одной очковой группы влияет только цвет и, ни в коем случае, не текущий коэффициент или там рейтинг. Иначе при двух разных запусках программы будет один и тот же результат. т.е. имея в наличии данную программу можно ознакомиться с жеребьевкой раньше соперника.
Д. Если по итогам соревнований при равенстве очков место определяет Бухгольц — значит и при жеребьевке туров прога смотрит на Бухгольц. Цалкофф — значит Цалкофф. Сидоров — значит и при жеребьевке Сидоров.Всё ИМХО.
Тем, кто легко скачивает три мега, предлагаю скачать программу жеребьевки для шахмат. На первый взгляд мне очень понравилась, даже показалась слишком навороченной..
http://www.shashki.com/files/setup.rarИ вот эту программу предлагаю обсудить. Что от нее полезно взять для шашечной, а что лишнее.
Программа очень понятная и простая в освоении и пользовании. Пока не заметил ничего лишнего. Не понятно назначение жирных и тонких горизонтальных линий в списке игроков и в финальных итогах. По-моему совсем не много надо переделки, чтобы применить к шашечным соревнованиям.
1. Отредактировать набор критериев, добавить «количество побед» и «результат личной встречи»
2. Предусмотреть возможность импорта списка игроков из TDam, в идеале возможность связать эти программы так, чтобы набор партии в TDam автоматически вводил информацию(результат) в Администратор, и наоборот клик на результате вызывал партию из TDam.
3. Добавить в окно создания турнира поле «Вид шашек» с автоматическим изменением способа записи результата (1/2:1/2 или 1:1)
4. До конца сделать перевод интерфейса на русский язык.
5. Переработать формы отчетов, таблиц, карточек применительно к принятым в шашках, возможно формы бланков необходимо заложить на 3-х языках.
6. Не нашел форму таблицы «Движение по турам»
7. Проверить систему критериев по котором составляются пары.В турнире по швейцарке играют n (n — чётное число) человек. При каком максимальном k всегда можно утверждать, что если сыграно k туров, то всегда можно сделать жеребьёвку k+1-го тура с учётом одного-единственного критерия: «Игроки не играют между собой дважды».
Владимир, подкинул вчера Вашу задачку на форум ВМиК МГУ, пока за сутки родилось достаточно тривиальное «если мы смогли организовать n-2 тура, то n-1 — й тур возможен всегда.» Но заинтересовавшиеся есть.
Вот, только что «родилось» на форуме. Я так давно учился математике, что ясно понял только что К<= n/2-1 - это впринципе мы и предполагали. Ну а для Вас переводите :
«Кстати, возможно, Вам поможет замечательная теорема: если в графе на n вершинах все степени вершин больше или равны (n-1)/2, то в этом графе есть гамильтонов цикл (цикл, проходящий через каждую вершину ровно по одному разу). В точности формулировки не уверен, возможно там (n+1)/2.
Таким образом, ваше утверждение верно при всех k<=n/2-1.
Действительно, пусть k<=n/2-1. Все ещё не игравшие пары участников образуют граф, степени вершин которого равны n-1-k >= (n-1)/2. Следовательно, в этом графе есть гамильтонов цикл. А если в графе с чётным числом вершин есть гамильтонов цикл, то есть и совершенное паросочетание (то разбиение на пары, которое Вам нужно), просто нужно в этом цикле взять «каждое второе» ребро (например, если цикл A1,A2,…A2n,A1, то играть в следующем туре будут A1-A2, A3-A4, …, A2n-1 — A2n).
Кстати, Вашим примером Вы показали, что если n=4m+2, то при k=n/2 утверждение уже не верно. То есть при n=4m+2 получено что-то типа точной оценки (если правильно сформулировать задачу).»В турнире по швейцарке играют n (n — чётное число) человек. При каком максимальном k всегда можно утверждать, что если сыграно k туров, то всегда можно сделать жеребьёвку k+1-го тура с учётом одного-единственного критерия: «Игроки не играют между собой дважды».
Владимир, подкинул вчера Вашу задачку на форум ВМиК МГУ, пока за сутки родилось достаточно тривиальное «если мы смогли организовать n-2 тура, то n-1 — й тур возможен всегда.» Но заинтересовавшиеся есть.
Да я эту задачу (при 6 участниках) раньше в разные годы несколько раз давал школьникам на матолимпиадах и матбоях. Правда — не выше областного уровня. Никто не решил..
Программа очень понятная и простая в освоении и пользовании. Пока не заметил ничего лишнего. Не понятно назначение жирных и тонких горизонтальных линий в списке игроков и в финальных итогах. По-моему совсем не много надо переделки, чтобы применить к шашечным соревнованиям.
1. Отредактировать набор критериев, добавить «количество побед» и «результат личной встречи»
2. Предусмотреть возможность импорта списка игроков из TDam, в идеале возможность связать эти программы так, чтобы набор партии в TDam автоматически вводил информацию(результат) в Администратор, и наоборот клик на результате вызывал партию из TDam.
3. Добавить в окно создания турнира поле «Вид шашек» с автоматическим изменением способа записи результата (1/2:1/2 или 1:1)
4. До конца сделать перевод интерфейса на русский язык.
5. Переработать формы отчетов, таблиц, карточек применительно к принятым в шашках, возможно формы бланков необходимо заложить на 3-х языках.
6. Не нашел форму таблицы «Движение по турам»
7. Проверить систему критериев по котором составляются пары.1. Ну лишнее — это специпично шахматные документы для отправки в ФИДЕ, поддержка рейтинг-листа в форме, в которой он раньше публиковался на его сайте, теперь там другая форма, поддержка электронных досок (у нас это только развивается, впрочем, последнее — Вам видней).
2. Нет таблицы с указанием соперников, не говоря уже о кросс-таблице, а всё это есть даже в более древней шахматной программе SW-46.
3. При жеребьёвке, простановке результатов и т.д. бестолковая необходимость периодически открывать и закрывать окна.
4. Сказать честно, я не вижу (даже без учёта следущего пункта) никаких преимуществ над sw46. Если только то, что написана под Windows, а не под DOS. Эта программа (начиная с беты) у нас уже 3 года, но мы используем по прежнему sw46. Кажется никакие шахматисты Chess Tournament Administrator не используют.
5. Но всё это ерунда по сравнению с главным. Проведите эксперемент (я это делал несколько раз несколько лет назад). Заведите турнир на 200 человек, ставьте от фонаря результаты, пусть, например, выигрывает всегда товарищ с меньшим номером. У Вас не зависло?
Более точное достаточное условие — это теорема Хватала: Если G -обыкновенный граф и d1<= ... <= dn - последовательность степеней вершин графа, то если для всех k верно, что из
dk(т.е. d катое)<=k=n-k, то граф гамильтонов. Более точное достаточное условие — это теорема Хватала: Если G -обыкновенный граф и d1<= ... <= dn - последовательность степеней вершин графа, то если для всех k верно, что из
dk(т.е. d катое)<=k=n-k, то граф гамильтонов. 1) Обыкновенный граф — это тот, когда любые 2 вершины соединины не более 1 раза?
2) То есть предполагается, что есть одновременно вершины со степенями как меньшими, так и большими n/2? Но какое тогда эта теорема имеет отношение к нашей задаче? К тому же, у нас степени всех вершин вообще одинаковые (=n-1-число сыгранных туров).
P.S. На самом деле, для нас гамильтоновость графа — это даже слишком много. Нам достаточно иметь всего лишь (при n=18):
1-2, 3-4, 5-6, …, 17-18, а вовсе не обязательно:
1-2-3-4-5-6-…-16-17-18-1.Да, обыкновенный граф – это неориентированный граф без петель и кратных ребер. Теорема вобщем-то ни при чем, просто это более точное условие гамильтоновости. Если все время надо искать полное паросочетание, то алгоритм Куна ищет его за O(n^3). Может быть, сделать какую-нибудь весовую функцию, которая делала бы одни пары более желательными, другие менее желательными, и искать полное паросочетание наименьшего веса? Или так и делают? Венгерский алгоритм делает это за O(n^4). (Все оценки из книги «Дискретная математика: матроиды, графы, алгоритмы» М.О. Асанов, В.А. Баранский, В.В. Расин, http://lib.mexmat.ru/)
Для Владимира и других интересующихся
Вот еще одна интересная работа по обсуждаемой темеAdaptive paired comparison design, Mark Glickman, Shane Jensen, 2005
Последнюю работу по этой теме я нашел датированной 1999 годом, The Stable Roommates Problem and Chess Tournament Pairings, Eija Kujansu с соавторами, цифры взяты оттуда.
Там эта формула просто приводится без объяснений. Но это не важно, мне примерно понятно, откуда берётся такая оценка. Но верно это в типичных случаях, но не в критических, о чём идёт речь.
- Для ответа в этой теме необходимо авторизоваться.