Комбинаторика для школьников

[Ian]

В группе из 1001 человека любые двое либо дружат, либо враждуют (дружба и вражда взаимны). Необходимо раздать им шляпы (каждый человек может получить несколько шляп) таким образом, чтобы любые два друга имели шляпу одного цвета, но никакие два врага не имели шляпы одного цвета. Каждый человек может получить несколько головных уборов. Какое минимальное количество цветов шляп требуется для того, чтобы это всегда можно было гарантированно сделать? (Шляп каждого цвета неограниченно много).
Примечание. Я долго вникал в условие. Например, человеку, который враг всем, незачем вообще давать какие-нибудь шляпы.
А если там 500 девочек и 501 мальчик, и всегда разнополые дружат, а однополые враждуют - шляп понадобится аж 501*500 цветов, по паре каждого цвета
Дружба нетранзитивна.

[zykov]

Source of the post А если там 500 девочек и 501 мальчик, и всегда разнополые дружат, а однополые враждуют - шляп понадобится аж 501*500 цветов

Видимо это и есть минимум.
Надо как-то наглядно показать, что для любого другого графа этого количества хватит.

[Ian]

Вот еще не решил
В городе N прошли 50 городских олимпиад по разным предметам, при этом в каждой из этих олимпиад участвовало ровно 30 школьников, но не было двух олимпиад с одним и тем же составом участников. Известно, что для любых 30 олимпиад найдётся школьник, который участвовал во всех этих 30 олимпиадах. Докажите, что найдётся школьник, который участвовал во всех 50 олимпиадах.

[zykov]

Что-то туго у меня теория графов идёт.
Думаю, можно для начала задачу поменьше рассмотреть - 5 олимпиад по 3 школьника.

А по первой как?
В приведенном случае, очевидно, меньше 501*500 не может быть. И вроде как по интуиции это наихудший случай. Есть подвижки с доказательством?

[Ian]

Для 5 олимпиад по 3 школьника , и для каждых трех олимпиад школьник - доказательство есть но длинное и почти переборное
Первая задача совсем не вышла
Это не мы. это комбинаторика непрерывно усложняется

[Ian]

Вот еще одна, тоже не довел
В стране 2n городов (n - натуральное) и некоторые из них соединены двусторонними авиалиниями. Из каждого города в другой можно добраться , возможно с пересадками. Если разбить страну на две области (каждый город в одну из областей), k будет означать число межобластных авиалиний, а m -число внутриобластных. Доказать, что можно так разбить, чтобы [math]k-m\geq n.
Критическим случаем является уже полный граф, только при разбиении поровну там равенство, иначе неравенство не выполняется.

[Ian]

Вот уж совсем, для 8го класса была предложена
Учащиеся одной из школ периодически проводят шахматные турниры. Под конец года оказалось, что Катя сыграла 31 партию, Коля – 29 партий, все остальные – ровно по 12. Могла ли Катя не сыграть с Колей ни одну партию?
(Тут имелось в виду, что турниры были любого количества и состава участников, но на нем каждый с каждым по разу сыграл. Если бы 2 круга, можно считать за два разных турнира, не меняет сути)

[peregoudov]

60 турниров по 2 человека в каждом, в 31 участвовала Катя, в 29 --- Коля, помимо них участвовали еще 5 человек. Или я чего-то не понимаю?

[zykov]

peregoudov
Получается, что так. Как раз для 8ого класса.
(Я то пытался доказать, что должны были сыграть.)

[Ian]

60 турниров по 2 человека в каждом, в 31 участвовала Катя, в 29 --- Коля, помимо них участвовали еще 5 человек.

Действительно.
Можно к ним еще добавить сколько угодно групп по 13 других человек и между ними турнир
Когда дан набор - у кого сколько участий и сходится проверка на четность суммы участий (31+29+12k), а также ни у кого не больше участий чем у всех остальных вместе взятых -то существует расписание (по индукции). Здесь был вопрос можно ли Катю и Колю заменить одним человеком с 60 участиями , и что же я вовремя не догадался.

[Ian]

Сегодня была задача на олимпиаде Ломоносов для 11кл. Рассматриваются все перестановки из 6 элементов. Для каждой перестановки [math]\pi вычислим число пар элементов (i,j) таких, что [math](i-j)(\pi(i)-\pi(j))<0 (то есть изменяющих порядок следования элементов в паре). Надо было найти число перестановок, для которых это число пар равно данному m

Обозначим [math]S_n(m) ответ задачи для перестановок из n элементов. Так как отображение 1цы в k=1,...n добавляет (k-1) пар, получаем рекуррентность
[math]S_n(m)=S_{n-1}(m)+S_{n-1}(m-1)+...+S_{n-1}(m-n+1)
(с учетом, что для невозможных значений аргумента S=0)
Откуда формируем табличку для S

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

n\m   0   1   2   3   4   5   6   7   8   9   10   11   12   13   14
1   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0
2   1   1   0   0   0   0   0   0   0   0   0   0   0   0   0
3   1   2   2   1   0   0   0   0   0   0   0   0   0   0   0
4   1   3   5   6   5   3   1   0   0   0   0   0   0   0   0
5   1   4   9   15   20   22   20   15   9   4   1   0   0   0   0
6   1   5   14   29   49   71   90   101   101   90   71   49   29   14   5


Сумма по n-й строке таблички равна n!, это следует из рекуррентности: в [math]\sum_mS_n(m) каждое [math]S_{n-1}(m) войдет ровно n раз
Но мне еще интересно:
А нет ли компактной формулы для [math]S_n(m). Например некоторые числа разбиений ее не имеют , а некоторые имеют