В группе из 1001 человека любые двое либо дружат, либо враждуют (дружба и вражда взаимны). Необходимо раздать им шляпы (каждый человек может получить несколько шляп) таким образом, чтобы любые два друга имели шляпу одного цвета, но никакие два врага не имели шляпы одного цвета. Каждый человек может получить несколько головных уборов. Какое минимальное количество цветов шляп требуется для того, чтобы это всегда можно было гарантированно сделать? (Шляп каждого цвета неограниченно много).
Примечание. Я долго вникал в условие. Например, человеку, который враг всем, незачем вообще давать какие-нибудь шляпы.
А если там 500 девочек и 501 мальчик, и всегда разнополые дружат, а однополые враждуют - шляп понадобится аж 501*500 цветов, по паре каждого цвета
Дружба нетранзитивна.
Комбинаторика для школьников
Комбинаторика для школьников
Видимо это и есть минимум.Ian писал(а):Source of the post А если там 500 девочек и 501 мальчик, и всегда разнополые дружат, а однополые враждуют - шляп понадобится аж 501*500 цветов
Надо как-то наглядно показать, что для любого другого графа этого количества хватит.
Комбинаторика для школьников
Вот еще не решил
В городе N прошли 50 городских олимпиад по разным предметам, при этом в каждой из этих олимпиад участвовало ровно 30 школьников, но не было двух олимпиад с одним и тем же составом участников. Известно, что для любых 30 олимпиад найдётся школьник, который участвовал во всех этих 30 олимпиадах. Докажите, что найдётся школьник, который участвовал во всех 50 олимпиадах.
В городе N прошли 50 городских олимпиад по разным предметам, при этом в каждой из этих олимпиад участвовало ровно 30 школьников, но не было двух олимпиад с одним и тем же составом участников. Известно, что для любых 30 олимпиад найдётся школьник, который участвовал во всех этих 30 олимпиадах. Докажите, что найдётся школьник, который участвовал во всех 50 олимпиадах.
Комбинаторика для школьников
Что-то туго у меня теория графов идёт.
Думаю, можно для начала задачу поменьше рассмотреть - 5 олимпиад по 3 школьника.
А по первой как?
В приведенном случае, очевидно, меньше 501*500 не может быть. И вроде как по интуиции это наихудший случай. Есть подвижки с доказательством?
Думаю, можно для начала задачу поменьше рассмотреть - 5 олимпиад по 3 школьника.
А по первой как?
В приведенном случае, очевидно, меньше 501*500 не может быть. И вроде как по интуиции это наихудший случай. Есть подвижки с доказательством?
Комбинаторика для школьников
Для 5 олимпиад по 3 школьника , и для каждых трех олимпиад школьник - доказательство есть но длинное и почти переборное
Первая задача совсем не вышла
Это не мы. это комбинаторика непрерывно усложняется
Первая задача совсем не вышла
Это не мы. это комбинаторика непрерывно усложняется
Комбинаторика для школьников
Вот еще одна, тоже не довел
В стране 2n городов (n - натуральное) и некоторые из них соединены двусторонними авиалиниями. Из каждого города в другой можно добраться , возможно с пересадками. Если разбить страну на две области (каждый город в одну из областей), k будет означать число межобластных авиалиний, а m -число внутриобластных. Доказать, что можно так разбить, чтобы [math].
Критическим случаем является уже полный граф, только при разбиении поровну там равенство, иначе неравенство не выполняется.
В стране 2n городов (n - натуральное) и некоторые из них соединены двусторонними авиалиниями. Из каждого города в другой можно добраться , возможно с пересадками. Если разбить страну на две области (каждый город в одну из областей), k будет означать число межобластных авиалиний, а m -число внутриобластных. Доказать, что можно так разбить, чтобы [math].
Критическим случаем является уже полный граф, только при разбиении поровну там равенство, иначе неравенство не выполняется.
Комбинаторика для школьников
Вот уж совсем, для 8го класса была предложена
Учащиеся одной из школ периодически проводят шахматные турниры. Под конец года оказалось, что Катя сыграла 31 партию, Коля – 29 партий, все остальные – ровно по 12. Могла ли Катя не сыграть с Колей ни одну партию?
(Тут имелось в виду, что турниры были любого количества и состава участников, но на нем каждый с каждым по разу сыграл. Если бы 2 круга, можно считать за два разных турнира, не меняет сути)
Учащиеся одной из школ периодически проводят шахматные турниры. Под конец года оказалось, что Катя сыграла 31 партию, Коля – 29 партий, все остальные – ровно по 12. Могла ли Катя не сыграть с Колей ни одну партию?
(Тут имелось в виду, что турниры были любого количества и состава участников, но на нем каждый с каждым по разу сыграл. Если бы 2 круга, можно считать за два разных турнира, не меняет сути)
-
- Сообщений: 620
- Зарегистрирован: 29 дек 2015, 13:17
Комбинаторика для школьников
60 турниров по 2 человека в каждом, в 31 участвовала Катя, в 29 --- Коля, помимо них участвовали еще 5 человек. Или я чего-то не понимаю?
Комбинаторика для школьников
peregoudov
Получается, что так. Как раз для 8ого класса.
(Я то пытался доказать, что должны были сыграть.)
Получается, что так. Как раз для 8ого класса.
(Я то пытался доказать, что должны были сыграть.)
Комбинаторика для школьников
Действительно.peregoudov писал(а):60 турниров по 2 человека в каждом, в 31 участвовала Катя, в 29 --- Коля, помимо них участвовали еще 5 человек.
Можно к ним еще добавить сколько угодно групп по 13 других человек и между ними турнир
Когда дан набор - у кого сколько участий и сходится проверка на четность суммы участий (31+29+12k), а также ни у кого не больше участий чем у всех остальных вместе взятых -то существует расписание (по индукции). Здесь был вопрос можно ли Катю и Колю заменить одним человеком с 60 участиями , и что же я вовремя не догадался.
Комбинаторика для школьников
Сегодня была задача на олимпиаде Ломоносов для 11кл. Рассматриваются все перестановки из 6 элементов. Для каждой перестановки [math] вычислим число пар элементов (i,j) таких, что [math] (то есть изменяющих порядок следования элементов в паре). Надо было найти число перестановок, для которых это число пар равно данному m
Обозначим [math] ответ задачи для перестановок из n элементов. Так как отображение 1цы в k=1,...n добавляет (k-1) пар, получаем рекуррентность
[math]
(с учетом, что для невозможных значений аргумента S=0)
Откуда формируем табличку для S
Сумма по n-й строке таблички равна n!, это следует из рекуррентности: в [math] каждое [math] войдет ровно n раз
Но мне еще интересно:
А нет ли компактной формулы для [math]. Например некоторые числа разбиений ее не имеют , а некоторые имеют
Обозначим [math] ответ задачи для перестановок из n элементов. Так как отображение 1цы в k=1,...n добавляет (k-1) пар, получаем рекуррентность
[math]
(с учетом, что для невозможных значений аргумента 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] каждое [math] войдет ровно n раз
Но мне еще интересно:
А нет ли компактной формулы для [math]. Например некоторые числа разбиений ее не имеют , а некоторые имеют
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 0 гостей