Задача как бы на составление расписания
Задача как бы на составление расписания
Это было предложено на контрольной с запасом времени 20 минут. Я вот уже час думаю, вроде верно, но как доказать. Из кого-то готовят гениев?
Доказательство ясно только при m=2. Пусть 1ца в одной строке с k. Зафиксируем эту строку,что в ней перестановка окончена, берем другую, в которой тоже есть k, и если надо делаем в ней перестановку, чтобы k были в разных столбцах, другое число рядом с k -ищем в какой строке оно еще, и т.д. пока не замкнется цикл на 1цу. Тогда несколько строк уже в порядке и столько же чисел уже расставлены как надо. Начинаем новый цикл и т.д.
Задача как бы на составление расписания
Вот например вариант задачи для n=4,m=13.
52 карты розданы 4-м игрокам (в бридж) по 13. Доказать, что они , сговорившись, могут делать свои ходы в таком порядке (не соблюдая правила бриджа давать в масть), что в каждой из 13 взяток будут представлены все 4 масти.
Или наоборот, 13 игрокам розданы по 4 карты. Тогда они могли бы обеспечить в каждой взятке 13 карт разного достоинства.
52 карты розданы 4-м игрокам (в бридж) по 13. Доказать, что они , сговорившись, могут делать свои ходы в таком порядке (не соблюдая правила бриджа давать в масть), что в каждой из 13 взяток будут представлены все 4 масти.
Или наоборот, 13 игрокам розданы по 4 карты. Тогда они могли бы обеспечить в каждой взятке 13 карт разного достоинства.
Задача как бы на составление расписания
Да, как-то сложно...
Немного напоминает Теорию Рамсея, но наверно всё же не то.
Это контрольная для студентов? В рамках какой темы?
Немного напоминает Теорию Рамсея, но наверно всё же не то.
Это контрольная для студентов? В рамках какой темы?
Задача как бы на составление расписания
Есть идея сделать индукцией по .
При оно очевидно - просто один столбец, где каждое число по одному разу.
При можно перестановками составить один столбец, так чтобы там были все числа по одному разу. Тогда этот столбец можно убрать из матрицы и оставшаяся матрица отвечает индукционному случаю .
Правда задача составить один столбец тоже не тривиальная, но она проще исходной.
При оно очевидно - просто один столбец, где каждое число по одному разу.
При можно перестановками составить один столбец, так чтобы там были все числа по одному разу. Тогда этот столбец можно убрать из матрицы и оставшаяся матрица отвечает индукционному случаю .
Правда задача составить один столбец тоже не тривиальная, но она проще исходной.
Задача как бы на составление расписания
Предмет "дискретная математика" (графы. элементы алгебры. логики, все в куче)zykov писал(а):Это контрольная для студентов? В рамках какой темы?
При [math]можно перестановками составить один столбец, так чтобы там были все числа по одному разу.
Да, этого достаточно, но почему при m>2 его можно составить? При m=2 я доказал по теореме о разбиении перестановки на независимые циклы, там также можно упорядочить матрицу в двудольный граф.(соединив как элементы одной строки, так и и одинаковые элементы).
А при m>2 очевиднее. но сложнее
Задача как бы на составление расписания
Точно не знаю.
Мне кажется, что "жадный" алгоритм должен составить такой столбец, но это надо доказать.
Просто так выбирать строку нельзя. Если например все 3 только в 1ой и 2ой строках и ещё в первой есть 1, а во второй есть 2, и мы скажем выбрали 1 для первой строки и 2 для второй, то 3 мы уже в столбец не поместим.
Но если строки отсортировать и выбрать строку с максимальным количеством повторов какого-то числа (если несколько таких строк, то любую из них), и выбрать это число для данной строки. И так далее, для других строк (уже не учитывая выбранные числа и использованные строки). То мне кажется, должно сойтись.
Мне кажется, что "жадный" алгоритм должен составить такой столбец, но это надо доказать.
Просто так выбирать строку нельзя. Если например все 3 только в 1ой и 2ой строках и ещё в первой есть 1, а во второй есть 2, и мы скажем выбрали 1 для первой строки и 2 для второй, то 3 мы уже в столбец не поместим.
Но если строки отсортировать и выбрать строку с максимальным количеством повторов какого-то числа (если несколько таких строк, то любую из них), и выбрать это число для данной строки. И так далее, для других строк (уже не учитывая выбранные числа и использованные строки). То мне кажется, должно сойтись.
Задача как бы на составление расписания
Код: Выбрать все
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
Задача как бы на составление расписания
Да, это контрпример.
Такой "жадный" алгоритм не сработает.
Тут наверно какая-то теорема из теории графов нужна (не силён в этой области).
Например такую конструкцию можно рассмотреть.
Двудольный граф, у которого с левой стороны вершин (по одной для каждой строки) и с правой стороны вершин (по одной для каждого числа). Ребро между левой и правой вершинами, если это число есть в данной строке. Каждая левая и каждая правая вершины принадлежат не менее одному ребру. (Наверно ещё какие-то ограничения на граф возникают.)
Нужно из всех рёбер выбрать рёбер, так чтобы выбранные рёбра не имели общих вершин.
Такой "жадный" алгоритм не сработает.
Тут наверно какая-то теорема из теории графов нужна (не силён в этой области).
Например такую конструкцию можно рассмотреть.
Двудольный граф, у которого с левой стороны вершин (по одной для каждой строки) и с правой стороны вершин (по одной для каждого числа). Ребро между левой и правой вершинами, если это число есть в данной строке. Каждая левая и каждая правая вершины принадлежат не менее одному ребру. (Наверно ещё какие-то ограничения на граф возникают.)
Нужно из всех рёбер выбрать рёбер, так чтобы выбранные рёбра не имели общих вершин.
Задача как бы на составление расписания
zykov писал(а):Source of the post Нужно из всех рёбер выбрать рёбер, так чтобы выбранные рёбра не имели общих вершин.
В теории графов это называется "совершенным паросочетанием" (Matching).
Если не ошибаюсь, то теорема Холла (теорема о свадьбах, теорема о мальчиках и девочках) тут работает (английский вариант на wiki более подробный).
Если нельзя саму теорему использовать, то можно её доказательство переписать для данного конкретного случая.
Доказательство следует немедленно из венгерского алгоритма для поиска максимального паросочетания в графе; также утверждение легко выводится из теоремы Форда — Фалкерсона о разрезаниях транспортных сетей.
Задача как бы на составление расписания
Ian писал(а):Source of the post Из кого-то готовят гениев?
Ну если изобретать теорию графов с нуля, то да, сложно.
А если студентам на лекциях рассказали про теорему Холла, то не сложно её применить за 20 минут.
Там в английском варианте есть список похожих теорем. Полезно ознакомиться, чтобы не "изобретать велосипед", если встретится что-то похожее.
Задача как бы на составление расписания
Теорема Холла должна быть верна для графов с кратными (дублирующими друг друга) ребрами [когда в одной строке несколько одинаковых чисел] , предполагал ли это Холл
В общем да, это неважно. В любом подмножестве из k строк есть как минимум k различных чисел, так как всего там mk чисел. Поэтому марьяж-условие выполнено и есть совершенное паросочетание строк и чисел, задающее 1й столбец из различных чисел.
Вероятность того, что лектор прочел Теорему Холла-50% (не все ее читают)
В общем да, это неважно. В любом подмножестве из k строк есть как минимум k различных чисел, так как всего там mk чисел. Поэтому марьяж-условие выполнено и есть совершенное паросочетание строк и чисел, задающее 1й столбец из различных чисел.
Вероятность того, что лектор прочел Теорему Холла-50% (не все ее читают)
Последний раз редактировалось Ian 28 июн 2020, 17:18, всего редактировалось 1 раз.
Задача как бы на составление расписания
Ian писал(а):Source of the post Теорема Холла должна быть верна для графов с кратными (дублирующими друг друга) ребрами
Не понял.
На русской wiki про теорему написано:
если в двудольном графе для любого натурального k любые k вершин одной из долей связаны по крайней мере с k вершинами другой, то граф разбивается на пары
У нас, для любого подмножества чисел размера k найдётся минимум k строк, где есть эти числа (очевидно, доказывается от противного в одну строчку). Аналогично, для любых k строк найдется не менее k разных числе которые есть в этих строках.
Задача как бы на составление расписания
Да у меня постоянно отключаются то мышка то экран, ждите, бойкие диалоги это всегда плохие диалоги
Задача как бы на составление расписания
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
Даже если стденты не знали теоремы Холла (которая тут имеет наиболее прямое отношение), они должны были бы знать какую-то другую теорему из этого списка (например теорему Форда — Фалкерсона) и могли бы доказать это утверждение на базе той теоремы.
Задача как бы на составление расписания
Ian писал(а):Source of the post Теорема Холла должна быть верна для графов с кратными (дублирующими друг друга) ребрами [когда в одной строке несколько одинаковых чисел]
Я имел ввиду граф отражающий логическое соотношение "данное число присутствует в данной строке". В этом графе не более одного ребра между любыми двумя вершинами.
Если взять другой граф, где может быть много рёбер между двумя вершинами, то с точки зрения теоремы оно ничего не меняет. Множество вершин связанных с вершинами из данного множества от этого не изменится.
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 1 гость