В соревнования по спидвею записалось $%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

изменен 26 Апр '14 15:12

Angry%20Bird's gravatar image


9125

@behemothus, Если вы получили исчерпывающий ответ, отметьте его как принятый.

(26 Апр '14 15:13) Angry Bird
10|600 символов нужно символов осталось
2

Мне кажется, эта задача тесно связана с вопросом о конечных проективных плоскостях. Исчерпывающей информации на этот счёт не имеется. Но можно взять конечную проективную плоскость порядка $%d$%, где $%d$% -- степень простого числа. Тогда можно взять $%N=d^2+d+1$% и $%K=d+1$%. То есть примеры такого рода известны, и они охватывают случаи $%K=3$% и $%K=4$%.

Если $%M > 1$%, то формально можно повторить всё $%M$% раз. Если подразумевается, что повторять заезд с теми же участниками нельзя, то можно ввести подходящую перенумерацию точек проективной плоскости.

ссылка

отвечен 4 Авг '13 14:05

Я, признаться, давно оторвался от математики, не понимаю, при чем тут при чем проективные плоскости. Вы можете привести хоть один пример, пусть даже для М=1?

Если M>1, то формально можно повторить всё M раз.

Это и так понятно, если есть решение для М=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
10|600 символов нужно символов осталось
2
ссылка

отвечен 6 Авг '13 13:28

Там, вроде, одни разговоры. Решения как такового нет. Да и постановка, похоже, не совсем та.

(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
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×730

задан
4 Авг '13 9:56

показан
1227 раз

обновлен
26 Апр '14 15:13

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru