|
В соревнования по спидвею записалось $%N$% спортсменов. В каждом заезде стартует $%K$% участников. При каких $%N$% и $%K$% ($%N>K>2$%) возможно организовать заезды так, чтобы каждый участник встретился с каждым ровно в $%М=1$% заездах? Особенно интересует $%К=4$%. Можно ли обобщить для $%М>1$%? Должно быть что-то весьма элементарное. Когда-то очень давно решал эту задачу для $%M=1$%, получилось, вроде бы, ни при каких $%K>2$%. Сейчас второй день не могу сообразить. //----- Забыл написать. Есть очевидное решение для $%M=(N-1)/((K-1)!(N-K))!$% и кратных: просто тперебираем все выборки из $%N$% по $%K$%.
Так что пока хочется разобраться с $%M=1$%. задан 4 Авг '13 9:56 
behemothus |
|
Мне кажется, эта задача тесно связана с вопросом о конечных проективных плоскостях. Исчерпывающей информации на этот счёт не имеется. Но можно взять конечную проективную плоскость порядка $%d$%, где $%d$% -- степень простого числа. Тогда можно взять $%N=d^2+d+1$% и $%K=d+1$%. То есть примеры такого рода известны, и они охватывают случаи $%K=3$% и $%K=4$%. Если $%M > 1$%, то формально можно повторить всё $%M$% раз. Если подразумевается, что повторять заезд с теми же участниками нельзя, то можно ввести подходящую перенумерацию точек проективной плоскости. отвечен 4 Авг '13 14:05 
falcao Я, признаться, давно оторвался от математики, не понимаю, при чем тут при чем проективные плоскости. Вы можете привести хоть один пример, пусть даже для М=1?
Это и так понятно, если есть решение для М=1. Вопрос, если ли решения для М>1, когда их нет при М=1?
Можно. Только в том, похоже нет никакого смысла, если только не найдено решения для меньшего М. Вообще не замыкайте пока на обобщених. Сначала - хоть одно решение для М=1.
(4 Авг '13 15:00)
behemothus
1
Простейшая конкретная конструкция такова. Рассмотрим треугольник $%ABC$%. Выберем внутри него точку $%O$%. Проведём через неё и через каждую из вершин прямые до пересечения с противоположными сторонами в точках $%A_1$%, $%B_1$%, $%C_1$%. Всего имеется $%N=7$% точек. Проведём 7 заездов, в каждом из которых участвуют трое. Это $%\{A,B_1,C\}$% и симметричные ему, $%\{A,O,A_1\}$% вместе с симметричными, а также $%\{A_1,B_1,C_1\}$%. Легко видеть, что любые два участника встречаются вместе ровно в одном из заездов. Это и есть проективная плоскость порядка $%2$%.
(4 Авг '13 17:02)
falcao
Красиво. Хотя при чем тут проективные плоскости, все еще не понимаю. Ну да бог с ними. Хотелось бы, конечно, общее решение. Возможно, раньше я доказывал для, К>3. Да, посмотрел. Легко адаптируется на N=13, К=4. Забавно...
(4 Авг '13 20:04)
behemothus
Участники -- это точки проективной плоскости, а заезды соответствуют прямым. Любые две различные прямые на проективной плоскости пересекаются в одной точке. Если $%K=d+1$%, где $%d$% есть степень простого числа, то такие примеры существуют (при $%N=d^2+d+1$%). Общую конструкцию можно найти в лиетратуре (она довольно длинно описывается).
(4 Авг '13 20:24)
falcao
Я понимаю определение проективной плоскости. Я не понимаю, зачем оно тут. Ну допустим, в вашем примере с треугольником еще можно придумать, что 6 из семи заездов - это прямые упомянутой плоскости. А седьмая? Тем более для К=4. там-то какая связь с ПП? Мне понятно как строить расписание при любых N=КxК-К+1. Это обобщение идеи треугольником. Пока - не более.
(4 Авг '13 22:05)
behemothus
Здесь речь идёт о конечных проективных плоскостях -- это можно считать частным случаем поставленной Вами задачи. См. информацию здесь. При $%M=1$% легко доказать, что числа $%N$% и $%K$%, если они существуют, связаны равенством $%N=K^2-K+1$%. Но этого условия не достаточно, и в обратную сторону заключение верно не для всех $%K$%. Например, $%K=5$% уже не подходит (см. теорему Брука - Райзера по ссылке).
(5 Авг '13 0:52)
falcao
Вроде понял. Вы хотите сказать, что между участниками и заездами "подходящего" расписания с одной стороны и точками и прямыми соответствующей проективной плоскости порядка К с другой всегда можно установить взаимно-однозначное соответствие? И тем самым первое (расписание) существует тогда и только тогда, когда есть второе (плоскость)? Интерсно... Хотя я не уверен, что это так... А чем К=5 не подходит? 5=4+1, 4 - степень двойки? Ко сему прочему, я вроде, набросал подобное расписание для К=5, N=21. Сейчас проверю, выложу, если не ошибся.
(5 Авг '13 6:03)
behemothus
Я только сейчас заметил, что в условии задачи могут быть "параллельные" заезды, то есть две "прямые" могут и не пересекаться. Дано только то, что через любые две "точки" проходит одна и только одна "прямая". В этом случае существование проективной плоскости достаточно, но не необходимо, то есть условие является более "мягким". Скорее всего, эта версия задачи несколько проще, то есть тут для любых $%N$% и $%K$% можно попытаться дать точное описание -- когда соответствующая конструкция возможна, а когда нет. Но придётся немножко подумать. Насчёт $%K=5$% я ошибся: должно быть $%d=6$%, $%K=7$%.
(5 Авг '13 12:23)
falcao
Поскольку комментировать уже не могу, пишу тут.
Да. Я уже понял, в чем мы разошлись. В Вашей модели плоскость вполне может быть афинной. Вас, видимо, несколько сбило с толку красивое решение на рисунке к аксиоме Фано. Разумеется нет никакого требования чтобы любые два заезда содержали хотя бы одного общего участника, это требование совершенно непонятно.
Я сейчас вспоминаю, что решал эту задачу для карточек "Спортлото". Видимо поэтому и попутал результат. В карточке из N чисел зачеркивается К, в тираже выпадает L=2 чисел, сколько карточек надо купить и как заполнить, чтобы всегда угадать L чисел ровно в М=1 карточках.
(5 Авг '13 16:43)
behemothus
Я поначалу не осмыслил до конца те рамки, в которых можно строить примеры, и ограничился случаем проективной плоскости, который гарантирует существование примера. Поскольку Вы говорили о предположительно отрицательном результате, я заметил, что примеры для $%K=3$% и $%K=4$% имеются. На самом деле, здесь ограничения "мягкие", и даже аффинность плоскости не требуется. Она тоже подходит, как и проективная, но там тоже есть ограничения, которых хотелось бы избежать. Суть в том, что не требуется выполнение аксиомы Евклида: через точку вне прямой может проходить много прямых, параллельных данной.
(5 Авг '13 17:30)
falcao
У меня сейчас почти нет времени, но я собираюсь сходить на море и возьму с собой туда бумагу и ручку. Попробую осмыслить, при каких $%N$% и $%K$% возможны примеры. Задачи про заполнение карточек и им подобные возникают довольно часто. Одна из них обсуждалась на форуме здесь.
(5 Авг '13 17:37)
falcao
показано 5 из 11
показать еще 6
|
|
отвечен 6 Авг '13 13:28 
AlexGolovnev Там, вроде, одни разговоры. Решения как такового нет. Да и постановка, похоже, не совсем та.
(6 Авг '13 19:02)
behemothus
Объект, который Вы ищете, называется (N,K,M)-комбинаторный дизайн. Вот здесь описаны необходимые и достаточные условия его существования: http://books.google.de/books?id=g6X2VWuB8qIC&lpg=PP1&hl=de&pg=PA153#v=onepage&q&f=false
(7 Авг '13 16:45)
AlexGolovnev
Насколько понял, там нет ключевого требования М=1, вместо него М>=1. Нет? У меня плохо открываются ссылки на pdf-документы, я не вижу первичного определения.
(7 Авг '13 19:23)
behemothus
Теоремы 13.2 и 13.3 работают для случая M=1 (в книге это lambda=1), все определения там на странице 153.
(8 Авг '13 1:05)
AlexGolovnev
|
@behemothus, Если вы получили исчерпывающий ответ, отметьте его как принятый.