Школьникам комбинаторика

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

Школьникам комбинаторика

Сообщение Ian » 10 сен 2022, 12:40

На полке в библиотеке в ряд стоят 12 книг. Иногда Вася приходит и меняет местами какие-нибудь 2 соседних книги. Какое минимальное количество раз Вася должен прийти в библиотеку, чтобы после его ухода каждая книга побывала как на первом месте, так и на последнем?
Что-то вообще идей нет. И никаких теорем про группу перестановок конечно не проходили они
Последний раз редактировалось Ian 10 сен 2022, 22:00, всего редактировалось 3 раз.

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

Школьникам комбинаторика

Сообщение zykov » 10 сен 2022, 13:15

Мне кажется, что оптимально - переставить 1-2, потом 2-3 и так далее до конца 11-12.
При этом первая доедет до 12ого места, вторая приедет на 1ое место.
Потом повторить всё это ещё 10 раз. При этом 11ая доедет до 12ого места, после того как побывала на 1ом месте. А 12 приедет на 1ое место.
Всего будет [math] перестановок.

Наверно можно доказать, если сконструировать какую-то сумму.
Можно ещё посмотреть на доказательство алгоритма пузырьковой сортировки, что он грантированно заканчивается за столько то шагов.

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

Школьникам комбинаторика

Сообщение zykov » 10 сен 2022, 16:58

Вышло пооптимальнее сделать и довести до 96.
Идея такая, что минимальное количество движений для каждой книги - это дойти до ближайшего края, а потом весь путь до другого края.

Сначала делаетм 1-2, 2-3 ... 5-6, потом 1-2, 2-3 ... 4-5 и так далее до 1-2. (Инверитрует порядок в первой половине.) 15 движений.
Потом так же для другой половины. Ещё 15 движений.
Потом 6 раз делаем 6-7 и каждый раз после этого 5-6, 4-5 ... 1-2 и 7-8, 8-9 ... 11-12. Т.е. 6 раз по 11 движений.

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

Школьникам комбинаторика

Сообщение Ian » 10 сен 2022, 17:26

Действительно! Не 121, а 96. Путь каждой книги по полке не меньше чем "расстояние от начальной позиции до ближнего к ней края"+ 11 позиций от края до края+"расстояние от конечной позиции до ближнего к ней края". В среднем арифметическом это 2,5+11+2,5=16. Каждая транспозиция это 2 единицы пути,так как в ней участвуетдве книги. Поэтому транспозиций не может быть меньше чем 16*12/2=96. А способ сделать 96 Вы описали: левая половина книг идет каждая в левый край потом в правый, правая половина наоборот. А между собой так чтобы ни одна книга не двигалась в ненужную ей (согласно этому правилу) сторону.Тогда все 192 перемещения книг будут полезны

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

Школьникам комбинаторика

Сообщение zykov » 10 сен 2022, 18:53

Да, там идея такая, что каждая перестановка оптимальна. Что обе книги в ней движутся, каждая туда куда ей надо - либо к ближайшей стороне, либо уже к противоположенной.

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

Школьникам комбинаторика

Сообщение Ian » 13 сен 2022, 13:22

Еще одна задача, вызвавшая трудности.
В физико-математическом классе учатся 24 физика и несколько математиков, некоторые пары из которых дружат (взаимно). При этом каждый физик дружит ровно с тремя физиками, и каждый математик дружит ровно с тремя физиками. Также известно, что у каждых двух дружащих физиков есть хотя бы один общий друг- математик. Какое наименьшее количество математиков может быть в классе?
Ответ почему-то 16, я даже примера на 16 не имею

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

Школьникам комбинаторика

Сообщение zykov » 14 сен 2022, 14:15

Мне кажется, тут логика такая - каждый физик дружит как минимум с 2 математиками, т.к. если-би он дружил только с 1, то и 3 его друга дружили бы с этим же, а тогда этот математик дружил бы сразу с 4 физиками, а по условию может быть только 3.
Значит количество рёбер "физик-математик" не менее [math]. Но количество этих рёбер равно [math], где [math] - количество математиков. Значит [math].
Это правда не доказывает достижимости этого мимнимума.

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

Школьникам комбинаторика

Сообщение Ian » 15 сен 2022, 08:38

Значит для примера можно искать матрицу М отношений между физиками и математиками, из нулей и единиц:
1) в каждой из 24 строк ровно две единицы;
2)в каждом из 16 столбцов ровно 3 единицы.
А матрица F отношений между физиками 24*24 симметрична, на диагонали нули, в каждой строке и столбце ровно 3 единицы.
Тогда нужно удовлетворить условию [math](неравенство в смысле:каждый элемент не меньше), а так как F мы можем придумать и потом, и матрица [math] заведомо симметричная, условие формулируется так: в матрице [math] в каждой строке не менее 3 недиагональных элемента отличны от 0
Кажется вполне считабельна, но Excel не берет, нелинейная задача и много переменных

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

Школьникам комбинаторика

Сообщение zykov » 15 сен 2022, 09:18

Можно попробовать регулярный вариант придумать.
Или у физиков 6 кластеров по 4, где все 4 дружат друг с другом.
Или 3 кластера по 8 физиков, где внутри кластера дружат по рёбрам куба (8 физиков в вершинах куба).

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

Школьникам комбинаторика

Сообщение zykov » 15 сен 2022, 13:58

zykov писал(а):Source of the post Или у физиков 6 кластеров по 4, где все 4 дружат друг с другом.
С таким кластером не получается.
Пусть физик F1 дружит с математиками A и B.
Тогда каждый F2, F3, F4 дружит либо с A, либо с B, но все три не могут дружит только с одним.
Без потери общности будет F2-A, F3-A, F4-B.
Для F2-F3 уже есть общий математик. Для F2-F4 и F3-F4 пока нет общего.
Есть два варианта F2-C, F3-C, F4-C или F2-B, F3-C, F4-C.

И так, и так будет, что два математика имеют всех 3ёх друзей в этом кластере и один математик имеет 2ух друзей в этом кластере. Ему надо ещё одного друга из другого кластере, но там может быть только 3 или 2.

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

Школьникам комбинаторика

Сообщение Ian » 15 сен 2022, 14:45

Получена матрица M c условием , что сумма в каждой строке [math] , без учета диагональных элементов, не меньше 3

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

1   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0
1   0   1   0   0   0   0   0   0   0   0   0   0   0   0   0
1   0   0   1   0   0   0   0   0   0   0   0   0   0   0   0
0   1   0   0   1   0   0   0   0   0   0   0   0   0   0   0
0   0   1   0   0   1   0   0   0   0   0   0   0   0   0   0
0   0   0   1   0   0   1   0   0   0   0   0   0   0   0   0
0   1   0   0   1   0   0   0   0   0   0   0   0   0   0   0
0   0   1   0   0   1   0   0   0   0   0   0   0   0   0   0
0   0   0   1   0   0   1   0   0   0   0   0   0   0   0   0
0   0   0   0   1   0   0   1   0   0   0   0   0   0   0   0
0   0   0   0   0   1   0   0   1   0   0   0   0   0   0   0
0   0   0   0   0   0   1   0   0   1   0   0   0   0   0   0
0   0   0   0   0   0   0   1   0   0   1   0   0   0   0   0
0   0   0   0   0   0   0   0   1   0   0   1   0   0   0   0
0   0   0   0   0   0   0   0   0   1   0   0   1   0   0   0
0   0   0   0   0   0   0   0   0   0   1   0   0   1   0   0
0   0   0   0   0   0   0   1   0   0   0   1   0   0   0   0
0   0   0   0   0   0   0   0   1   0   0   0   1   0   0   0
0   0   0   0   0   0   0   0   0   1   0   0   0   1   0   0
0   0   0   0   0   0   0   0   0   0   1   0   0   0   1   0
0   0   0   0   0   0   0   0   0   0   0   1   0   0   0   1
0   0   0   0   0   0   0   0   0   0   0   0   1   0   0   1
0   0   0   0   0   0   0   0   0   0   0   0   0   1   1   0
0   0   0   0   0   0   0   0   0   0   0   0   0   0   1   1

На самом деле эта сумма чаще 4 чем 3, это соответствует варианту условия " каждый физик имеет НЕ МЕНЕЕ ТРЕХ друзей", казалось бы это хуже. Вот какая получилась для этого F(обращением в 0 диагональных элементов [math] и в 1 тех, которые оказались равны 2)

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

0   1   1   1   0   0   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
1   0   1   0   1   0   0   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
1   1   0   0   0   1   0   0   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
1   0   0   0   0   0   1   0   0   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0
0   1   0   0   0   0   0   1   0   0   1   0   0   0   0   0   0   0   0   0   0   0   0   0
0   0   1   0   0   0   0   0   1   0   0   1   0   0   0   0   0   0   0   0   0   0   0   0
1   0   0   1   0   0   0   0   0   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0
0   1   0   0   1   0   0   0   0   0   1   0   0   0   0   0   0   0   0   0   0   0   0   0
0   0   1   0   0   1   0   0   0   0   0   1   0   0   0   0   0   0   0   0   0   0   0   0
0   0   0   1   0   0   1   0   0   0   0   0   1   0   0   0   1   0   0   0   0   0   0   0
0   0   0   0   1   0   0   1   0   0   0   0   0   1   0   0   0   1   0   0   0   0   0   0
0   0   0   0   0   1   0   0   1   0   0   0   0   0   1   0   0   0   1   0   0   0   0   0
0   0   0   0   0   0   0   0   0   1   0   0   0   0   0   1   1   0   0   1   0   0   0   0
0   0   0   0   0   0   0   0   0   0   1   0   0   0   0   0   1   1   0   0   1   0   0   0
0   0   0   0   0   0   0   0   0   0   0   1   0   0   0   0   0   1   1   0   0   1   0   0
0   0   0   0   0   0   0   0   0   0   0   0   1   0   0   0   0   0   1   1   0   0   1   0
0   0   0   0   0   0   0   0   0   1   0   0   1   1   0   0   0   0   0   0   1   0   0   0
0   0   0   0   0   0   0   0   0   0   1   0   0   1   1   0   0   0   0   0   0   1   0   0
0   0   0   0   0   0   0   0   0   0   0   1   0   0   1   1   0   0   0   0   0   0   1   0
0   0   0   0   0   0   0   0   0   0   0   0   1   0   0   1   0   0   0   0   0   0   1   1
0   0   0   0   0   0   0   0   0   0   0   0   0   1   0   0   1   0   0   0   0   1   0   1
0   0   0   0   0   0   0   0   0   0   0   0   0   0   1   0   0   1   0   0   1   0   0   1
0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   1   0   0   1   1   0   0   0   1
0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   1   1   1   1   0

Теперь, чтобы удовлетворить исходному условию "каждый физик имеет ровно трех друзей", нужно некоторые единички заменить на 0 с сохранением симметрии, но именно это и не удается.

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

Школьникам комбинаторика

Сообщение zykov » 17 сен 2022, 13:57

Граф для физиков например может ещё иметь форму додекаэдра. Это будет 20 вершин. Оставшиеся 4 нужно тогда в отдельный кластер.
А вообще граф может быть полностью связанный. Можно взять тот же додекаэдр, вынуть одну вершину - останется 5 физиков. К трём рёбрам (что шли к вынутой вершине) присоединить 3 разных точки. А от каждой из этих трёх точек добавить по ребру к двум оставшимся точкам.

Как и для кластеров размера 4, имеет место утверждение, что для каждого физика один из его двух математиков будет так же другом для двух друзей этого физика. Т.е. все три друга этого математика - это этот физик и два его друга.
Так всегда можно найти хотя бы 6 физиков, которые не дружат друг с другом (6 для случая 6 кластеров по 4, в других случаях может быть и больше). А для них будет 6 (или больше, если физиков больше 6) математиков, которые полностью входят в круг этих физиков.
Это можно использовать для сужения перебора, если пытатся подобрать математиков для данного графа физиков.
Думается, что граф физиков нужно брать полностью связанным, т.к. изолированные кластеры в нём усложняют дело.

Мой граф из додекаэдра, где одна вершина заменена подграфом из 5 вершин, довольно регулярен, но не полностью. Может есть полностью регулярный граф на 24 вершины?

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

Школьникам комбинаторика

Сообщение Ian » 19 сен 2022, 07:38

zykov писал(а): Может есть полностью регулярный граф на 24 вершины?
Если бы он был многогранником, то по формуле Эйлера Г=Р+2-В=36+2-24=14 граней, тогда среднее число углов у одной грани 5.2.Ближе всего детский футбольный мячик из 5- и 6- угольников

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

Школьникам комбинаторика

Сообщение zykov » 21 сен 2022, 15:41

Вроде получилось подобрать регулярные графы для физиков и для математиков.

Для начала комментарий про "собственных" математиков.
Ранее я писал, что каждый физик имеет "собственного" математика. Такого, что оба других друга этого математика - это два из трёх друзей этого физика. Значит если два физика не дружат друг с другом, то у них точно разные "собственные" математики.
Т.к. физиков 24, а математиков 16, то некоторые математики должны быть "собственными" для более чем одного физика.
Если какой-то математик является собственным для физиков A и B, то эти A и B дружат. Кроме того, третий друг этого математика - физик C - будет другом для A и для B. Значит все три друга этого математика - физики A, B и C - дружат друг с другом и образуют треугольник. Этот математик "собственный" сразу для всех трёх.
Таких треугольников должно быть минимум 4. Тогда для оставшихся 12 физиков оставшиеся 12 математиков могут быть "собственными", каждый только для одного физика. Но может быть и больше треугольников. Вплоть до 8.

Насчёт регулярного графа для физиков, да, полностью симметричный граф (все вершины и все рёбра симметричны) - это многогранник, как додекаэдр для 20 вершин. Для 24 такой найти не получается. Но нашел другой регулярный граф. Возьмём куб и заменим каждую из 8 вершин на треугольник из 3 точек. Так что каждое из трёх рёбер шедших к удалённой вершине присоеднияется к разным вершинам треугольника. В таком графе все вершины будут симметричны. Но в отличии от правильного многогранника, рёбра не будут симметричны - будут рёбра в треугольнике (8 по 3) и рёбра в кубе (12).

Теперь построим граф математиков используя этот граф физиков.
Положим, что 4 треугольника из физиков - это собственные треугольники. Расположим их на верхней грани куба на концах диагонали "север-юг" и на нижней грани на концах диагонали "запад-восток". Тогда собственные треугольники не имеют прямого соединения с другими собственными (все три соседа - несобственные). И наоборот, несобственные треугольники (4 штуки) не имеют прямого соединения с другими несобственными (все три соседа - собственные). Для этих 4 треугольников будет 4 собственных математика в сумме.
Далее, пройдёмся по всем несобственным треугольникам, обойдём их вершины в каком-то направлении (не важно, по часовой или против) и назначим для каждой вершины собственного математика из оставшихся 12 (физиков тоже 4 треугольника по 3 физика). Этот математик будет так же другом для двух других друзей этого физика - тот физик, что в собственном треугольнике, и следующий по направлению обхода физик в этом же треугольнике.
Таким образом, мы построили регулярный граф между 24 физиками и 16 математиками, удовлетворяющий условиям задачи.

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

Школьникам комбинаторика

Сообщение Ian » 22 сен 2022, 11:31

Красиво. Я перевел Ваше решение на язык матриц. Матрица М (24*16) отношений физиков к математикам и матрица F отношений между физиками. Физики (вершины мелких треугольников) имеют имена типа А(В) где А- ближайшая вершина ИСХОДНОГО куба,В -следующая по близости вершина ИСХОДНОГО куба. https://en.wikipedia.org/wiki/Truncated_cube

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

M                                                
A(B)      1   0   0   0   1   0   0   0   0   0   0   0   0   0   0   0
A(D)      1   0   0   0   0   0   0   1   0   0   0   0   0   0   0   0
A(A1)   1   0   0   0   0   0   0   0   0   0   0   0   1   0   0   0
C(B)      0   1   0   0   0   1   0   0   0   0   0   0   0   0   0   0
C(D)      0   1   0   0   0   0   0   0   1   0   0   0   0   0   0   0
C(C1)   0   1   0   0   0   0   0   0   0   0   0   0   0   0   0   1
B1(A1)   0   0   1   0   0   0   0   0   0   0   1   0   0   0   0   0
B1(C1)   0   0   1   0   0   0   0   0   0   0   0   0   0   1   0   0
B1(B)   0   0   1   0   0   0   1   0   0   0   0   0   0   0   0   0
D1(A1)   0   0   0   1   0   0   0   0   0   0   0   1   0   0   0   0
D1(C1)   0   0   0   1   0   0   0   0   0   0   0   0   0   0   1   0
D1(D)   0   0   0   1   0   0   0   0   0   1   0   0   0   0   0   0
B(A)      0   0   0   0   1   1   0   0   0   0   0   0   0   0   0   0
B ( C )   0   0   0   0   0   1   1   0   0   0   0   0   0   0   0   0
B(B1)   0   0   0   0   1   0   1   0   0   0   0   0   0   0   0   0
D(A)      0   0   0   0   0   0   0   1   1   0   0   0   0   0   0   0
D( C )   0   0   0   0   0   0   0   0   1   1   0   0   0   0   0   0
D(D1)   0   0   0   0   0   0   0   1   0   1   0   0   0   0   0   0
A1(B1)   0   0   0   0   0   0   0   0   0   0   1   1   0   0   0   0
A1(D1)   0   0   0   0   0   0   0   0   0   0   0   1   1   0   0   0
A1(A)   0   0   0   0   0   0   0   0   0   0   1   0   1   0   0   0
C1(B1)   0   0   0   0   0   0   0   0   0   0   0   0   0   1   1   0
C1(D1)   0   0   0   0   0   0   0   0   0   0   0   0   0   0   1   1
C1 ( C )   0   0   0   0   0   0   0   0   0   0   0   0   0   1   0   1

F   
A(B)      0   1   1   0   0   0   0   0   0   0   0   0   1   0   0   0   0   0   0   0   0   0   0   0
A(D)      1   0   1   0   0   0   0   0   0   0   0   0   0   0   0   1   0   0   0   0   0   0   0   0
A(A1)   1   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   1   0   0   0
C(B)      0   0   0   0   1   1   0   0   0   0   0   0   0   1   0   0   0   0   0   0   0   0   0   0
C(D)      0   0   0   1   0   1   0   0   0   0   0   0   0   0   0   0   1   0   0   0   0   0   0   0
C(C1)   0   0   0   1   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   1
B1(A1)   0   0   0   0   0   0   0   1   1   0   0   0   0   0   0   0   0   0   1   0   0   0   0   0
B1(C1)   0   0   0   0   0   0   1   0   1   0   0   0   0   0   0   0   0   0   0   0   0   1   0   0
B1(B)   0   0   0   0   0   0   1   1   0   0   0   0   0   0   1   0   0   0   0   0   0   0   0   0
D1(A1)   0   0   0   0   0   0   0   0   0   0   1   1   0   0   0   0   0   0   0   1   0   0   0   0
D1(C1)   0   0   0   0   0   0   0   0   0   1   0   1   0   0   0   0   0   0   0   0   0   0   1   0
D1(D)   0   0   0   0   0   0   0   0   0   1   1   0   0   0   0   0   0   1   0   0   0   0   0   0
B(A)      1   0   0   0   0   0   0   0   0   0   0   0   0   1   1   0   0   0   0   0   0   0   0   0
B ( C )   0   0   0   1   0   0   0   0   0   0   0   0   1   0   1   0   0   0   0   0   0   0   0   0
B(B1)   0   0   0   0   0   0   0   0   1   0   0   0   1   1   0   0   0   0   0   0   0   0   0   0
D(A)      0   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   1   1   0   0   0   0   0   0
D( C )   0   0   0   0   1   0   0   0   0   0   0   0   0   0   0   1   0   1   0   0   0   0   0   0
D(D1)   0   0   0   0   0   0   0   0   0   0   0   1   0   0   0   1   1   0   0   0   0   0   0   0
A1(B1)   0   0   0   0   0   0   1   0   0   0   0   0   0   0   0   0   0   0   0   1   1   0   0   0
A1(D1)   0   0   0   0   0   0   0   0   0   1   0   0   0   0   0   0   0   0   1   0   1   0   0   0
A1(A)   0   0   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   1   1   0   0   0   0
C1(B1)   0   0   0   0   0   0   0   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   1   1
C1(D1)   0   0   0   0   0   0   0   0   0   0   1   0   0   0   0   0   0   0   0   0   0   1   0   1
C1 ( C )   0   0   0   0   0   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   1   1   0


Действительно [math] выполнено, и суммы М,F по строкам и столбцам все правильные


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

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

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