Задача как бы на составление расписания

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Задача как бы на составление расписания

Сообщение Ian » 26 июн 2020, 15:53

86.png
86.png (200.47 KiB) 19858 просмотра

Это было предложено на контрольной с запасом времени 20 минут. Я вот уже час думаю, вроде верно, но как доказать. Из кого-то готовят гениев?
Доказательство ясно только при m=2. Пусть 1ца в одной строке с k. Зафиксируем эту строку,что в ней перестановка окончена, берем другую, в которой тоже есть k, и если надо делаем в ней перестановку, чтобы k были в разных столбцах, другое число рядом с k -ищем в какой строке оно еще, и т.д. пока не замкнется цикл на 1цу. Тогда несколько строк уже в порядке и столько же чисел уже расставлены как надо. Начинаем новый цикл и т.д.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Задача как бы на составление расписания

Сообщение Ian » 27 июн 2020, 09:46

Вот например вариант задачи для n=4,m=13.
52 карты розданы 4-м игрокам (в бридж) по 13. Доказать, что они , сговорившись, могут делать свои ходы в таком порядке (не соблюдая правила бриджа давать в масть), что в каждой из 13 взяток будут представлены все 4 масти.
Или наоборот, 13 игрокам розданы по 4 карты. Тогда они могли бы обеспечить в каждой взятке 13 карт разного достоинства.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Задача как бы на составление расписания

Сообщение zykov » 27 июн 2020, 12:30

Да, как-то сложно...
Немного напоминает Теорию Рамсея, но наверно всё же не то.

Это контрольная для студентов? В рамках какой темы?

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Задача как бы на составление расписания

Сообщение zykov » 27 июн 2020, 15:11

Есть идея сделать индукцией по $m$.
При $m=1$ оно очевидно - просто один столбец, где каждое число по одному разу.
При $m>1$ можно перестановками составить один столбец, так чтобы там были все числа по одному разу. Тогда этот столбец можно убрать из матрицы и оставшаяся матрица $n \times (m-1)$ отвечает индукционному случаю $m-1$.

Правда задача составить один столбец тоже не тривиальная, но она проще исходной.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Задача как бы на составление расписания

Сообщение Ian » 27 июн 2020, 16:20

zykov писал(а):Это контрольная для студентов? В рамках какой темы?
Предмет "дискретная математика" (графы. элементы алгебры. логики, все в куче)
При [math]можно перестановками составить один столбец, так чтобы там были все числа по одному разу.

Да, этого достаточно, но почему при m>2 его можно составить? При m=2 я доказал по теореме о разбиении перестановки на независимые циклы, там также можно упорядочить матрицу в двудольный граф.(соединив как элементы одной строки, так и и одинаковые элементы).
А при m>2 очевиднее. но сложнее

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Задача как бы на составление расписания

Сообщение zykov » 27 июн 2020, 16:43

Точно не знаю.
Мне кажется, что "жадный" алгоритм должен составить такой столбец, но это надо доказать.
Просто так выбирать строку нельзя. Если например все 3 только в 1ой и 2ой строках и ещё в первой есть 1, а во второй есть 2, и мы скажем выбрали 1 для первой строки и 2 для второй, то 3 мы уже в столбец не поместим.
Но если строки отсортировать и выбрать строку с максимальным количеством повторов какого-то числа (если несколько таких строк, то любую из них), и выбрать это число для данной строки. И так далее, для других строк (уже не учитывая выбранные числа и использованные строки). То мне кажется, должно сойтись.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Задача как бы на составление расписания

Сообщение Ian » 27 июн 2020, 17:25

Код: Выбрать все

1   1   1   3   3   4   4
2   2   3   4   5   5   1
6   6   3   4   5   2   2
5   5   1   6   3   4   6
6   6   3   3   4   4   2
2   2   5   5   1   1   6
Вот при наличие жадности либо тройку либо 4-ку в 1й столбец поставить не сможет Выбирали наибольшее число вхождений одинаковой цифры в строку, при прочих равных в более высокую строку, при прочих равных в более ранние столбцы. 1,2.6.5 разместились и тупик.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Задача как бы на составление расписания

Сообщение zykov » 27 июн 2020, 19:20

Да, это контрпример.
Такой "жадный" алгоритм не сработает.

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

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Задача как бы на составление расписания

Сообщение zykov » 27 июн 2020, 22:29

zykov писал(а):Source of the post Нужно из всех рёбер выбрать $n$ рёбер, так чтобы выбранные рёбра не имели общих вершин.

В теории графов это называется "совершенным паросочетанием" (Matching).

Если не ошибаюсь, то теорема Холла (теорема о свадьбах, теорема о мальчиках и девочках) тут работает (английский вариант на wiki более подробный).

Если нельзя саму теорему использовать, то можно её доказательство переписать для данного конкретного случая.
Доказательство следует немедленно из венгерского алгоритма для поиска максимального паросочетания в графе; также утверждение легко выводится из теоремы Форда — Фалкерсона о разрезаниях транспортных сетей.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Задача как бы на составление расписания

Сообщение zykov » 28 июн 2020, 00:09

Ian писал(а):Source of the post Из кого-то готовят гениев?

Ну если изобретать теорию графов с нуля, то да, сложно.
А если студентам на лекциях рассказали про теорему Холла, то не сложно её применить за 20 минут.

Там в английском варианте есть список похожих теорем. Полезно ознакомиться, чтобы не "изобретать велосипед", если встретится что-то похожее.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Задача как бы на составление расписания

Сообщение Ian » 28 июн 2020, 17:08

Теорема Холла должна быть верна для графов с кратными (дублирующими друг друга) ребрами [когда в одной строке несколько одинаковых чисел] , предполагал ли это Холл
В общем да, это неважно. В любом подмножестве из k строк есть как минимум k различных чисел, так как всего там mk чисел. Поэтому марьяж-условие выполнено и есть совершенное паросочетание строк и чисел, задающее 1й столбец из различных чисел.
Вероятность того, что лектор прочел Теорему Холла-50% (не все ее читают)
Последний раз редактировалось Ian 28 июн 2020, 17:18, всего редактировалось 1 раз.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Задача как бы на составление расписания

Сообщение zykov » 28 июн 2020, 17:14

Ian писал(а):Source of the post Теорема Холла должна быть верна для графов с кратными (дублирующими друг друга) ребрами

Не понял.

На русской wiki про теорему написано:
если в двудольном графе для любого натурального k любые k вершин одной из долей связаны по крайней мере с k вершинами другой, то граф разбивается на пары

У нас, для любого подмножества чисел размера k найдётся минимум k строк, где есть эти числа (очевидно, доказывается от противного в одну строчку). Аналогично, для любых k строк найдется не менее k разных числе которые есть в этих строках.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Задача как бы на составление расписания

Сообщение Ian » 28 июн 2020, 17:19

Да у меня постоянно отключаются то мышка то экран, ждите, бойкие диалоги это всегда плохие диалоги

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Задача как бы на составление расписания

Сообщение zykov » 28 июн 2020, 21:40

Ian писал(а):Source of the post Вероятность того, что лектор прочел Теорему Холла-50% (не все ее читают)

По той ссылке про другие теоремы написано:
all of which are related to each other in an informal sense in that it is more straightforward to prove one of these theorems from another of them than from first principles


Даже если стденты не знали теоремы Холла (которая тут имеет наиболее прямое отношение), они должны были бы знать какую-то другую теорему из этого списка (например теорему Форда — Фалкерсона) и могли бы доказать это утверждение на базе той теоремы.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Задача как бы на составление расписания

Сообщение zykov » 29 июн 2020, 14:00

Ian писал(а):Source of the post Теорема Холла должна быть верна для графов с кратными (дублирующими друг друга) ребрами [когда в одной строке несколько одинаковых чисел]

Я имел ввиду граф отражающий логическое соотношение "данное число присутствует в данной строке". В этом графе не более одного ребра между любыми двумя вершинами.
Если взять другой граф, где может быть много рёбер между двумя вершинами, то с точки зрения теоремы оно ничего не меняет. Множество вершин связанных с вершинами из данного множества от этого не изменится.


Вернуться в «Математика»

Кто сейчас на форуме

Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 18 гостей