Комбинаторика на ИТМО: способы, графы, логика, клетки, комбигео —Каталог задач по Олимпиадной математике

Главная
Каталог задач
Каталог заданий по Олимпиады - Математика
Комбинаторика на ИТМО: способы, графы, логика, клетки, комбигео

Тема ИТМО (открытка)

Комбинаторика на ИТМО: способы, графы, логика, клетки, комбигео

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела итмо (открытка)

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#82293

100 человек пришли на представление в шляпах. Фокусник поменял местами их шляпы. После этого каждую минуту каждый человек находил свою шляпу и передавал тому, у кого эта шляпа в данный момент находилась, ту шляпу, которая в этот момент была у него самого. (Если на каком-то шаге у человека $A$ оказывается шляпа, принадлежащая человеку $B$ , а у человека $C$ оказывается шляпа, принадлежащая человеку самому $A$ , то на следующем шаге у $C$ оказывается шляпа, принадлежащая $B$ ).

Фокусник изначально раздал шляпы так, чтобы в итоге они вернулись к своим настоящим хозяевам, но при этом это произошло бы как можно позже. Через сколько минут, самое позднее, это может произойти в первый раз?

Источники: ИТМО-2024, 11.8 (см. olymp.itmo.ru)

Подсказки к задаче

Подсказка 1

Условие про то, как передвигаются шляпы достаточно сложное, поэтому, чтобы хорошо его понять, нужно самому подвигать шляпы на каком-то количестве человек. Давайте рассмотрим какого-то человека А₀, так как мы сами вводим обозначения, то давайте изначально его шляпа была у А₁. Тогда человека, держащего шляпу А₁, назовём А₂ и так далее. В какой момент цепочка А₀- А₁-А₂ остановится? Обязательно поймите, почему это точно произойдёт.

Подсказка 2

Цепочка остановится в момент, когда шляпа какого-то Аₙ₋₁ окажется у Aₖ, которого мы уже записывала в нее. Тогда чему может быть равно k?

Подсказка 3

Через минуту шляпа А₀ окажется у того, кто держал раньше шляпу А₁, то есть у А₂, шляпа А₁ будет у А₃. Тогда можно сделать вывод, что для каждого k шляпа Aₖ через минуту окажется у Aₖ₊₂.

Подсказка 4

Через m минут шляпа Aₖ будет находиться у человека с номером k + 2ᵐ. Тогда при каком количестве человек шляпа сможет вернутся к исходному владельцу? Воспользуйтесь тем, что Aₖ = Аₙ₊ₖ.

Подсказка 5

Шляпа может вернуться к исходном владельцу только в случае, если количество человек в цикле является степенью двойки! По условию фокусник изначально раздал шляпы так, чтобы в итоге они вернулись к своим настоящим хозяевам. Это значит, что все 100 человек разобьются на некоторое количество циклов (цикл из одного человека тоже может быть). Но мы уже получили условие на длины циклов. Тогда какая может быть наибольшая, учитывая ограничение в 100 человек?

Показать ответ и решение

Рассмотрим некоторого человека, назовём его $A 0$ . Пусть его шляпа изначально оказалась у какого-то $A 1$ , шляпа $A 1$ оказалась у $A 2$ , и т.д. Рассмотренный нами процесс нумерации рано или поздно закончится тем, что для какого-то $An−1$ его шляпа окажется у какого-то $Ak$ , который был уже нами пронумерован ранее. При этом это может быть только $A0$ , т.к. про всех остальных мы уже знаем, откуда взялись находящиеся у них шляпы.

Значит, шляпа $An−1$ в начале представления оказалась у $A0$ и мы получили так называемый цикл из $n$ человек. Для удобства будем считать, что $An =A0,An+1 =A1$ и т.д., чтобы иметь возможность говорить, что каждый человек с номером $k$ передал свою шляпу человеку с номером $k+1$ (то есть, мы на самом деле нумеруем людей остатками (классами вычетов) при делении на $n$ ).

После того, как джентльмены передадут свои шляпы, шляпа $A0$ окажется у того, у кого раньше была шляпа $A1$ , то есть у $A2$ , шляпа $A1$ окажется у $A3$ и т.д. Шляпа каждого $Ak$ окажется у $Ak+2$ . После второй передачи шляпа каждого $Ak$ окажется у $Ak+4$ и т.д. Через $m$ минут шляпа $Ak$ окажется у $Ak+2m$ .

Если это тот же человек, что и $Ak$ , разность их номеров, то есть $2m$ , должна делится на $n$ . Значит, шляпа может вернуться к исходном владельцу, только если количество человек в цикле является степенью двойки. При этом фокусник хочет, чтобы был цикл как можно большей длины.

Самая большая степень двойки, не превосходящая 100, это $64= 26$ . Фокусник в начале должен разбить пришедших на представление на циклы, длины одного из которых равна 64, а длины остальных — меньшие степени двойки, не важно какие. Тогда через 6 минут все шляпы окажутся у своих настоящих владельцев (у некоторых они окажутся раньше, но в этот момент это впервые произойдёт для всех сразу).

Ответ: 6

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#82289

Клетчатый куб $9× 9× 9$ состоит из ячеек, представляющих из себя единичные кубики. 361 ячейка закрашена. Докажите, что в каком-то кубике $2× 2×2$ закрашено хотя бы четыре ячейки.

Источники: ИТМО-2024, 11.4 (см. olymp.itmo.ru)

Подсказки к задаче

Подсказка 1

Дан куб со стороной 9, а надо понять что-то про кубики со стороной 2. Конечно, неудобно, что большой куб ровно не разбиваются на маленькие. Но мы можем попробовать разбить на кубики 2*2*2 хотя-бы ту часть куба, которую возможно, и применить для нее предположение, противоположное вопросу задачи.

Подсказка 2

Но у нас остается еще часть большого куба, не разбитая на кубы 2*2*2. Эту часть тоже можно как-то разбить хорошо (удобно, что 4 ячейки укладываются в квадратик 2*2) и понять, какое максимальное кол-во закрашенных ячеек может быть, если в каждом кубике 2*2*2 их не более 3!

Показать доказательство

Вырежем из нашего куба куб $8× 8×8$ и разобьём его на 64 куба $2×2 ×2$ .

Предположим, что в каждом кубике закрашено не более трёх ячеек, то есть всего не более 192.

В исходном кубе после этого остались кубики на трёх гранях, имеющих общую вершину. Рассмотрим 64 клетки на одной из этих граней, которые не лежат ни на какой из двух других. Они разбиваются на 16 квадратов $2×2$ , в каждом из которых не более трёх закрашенных ячеек. Итого на трёх гранях получаем не более $3× 16× 3=144$ .

У нас остались не рассмотренными 25 ячеек, образующих три ребра исходного куба, сходящиеся в одной вершине. Среди них закрашены не более 24, так как общая ячейка трёх этих рёбер и три её соседних лежат в одном кубике $2× 2× 2$ , значит, среди этих четырёх ячеек не более трёх закрашенных.

Таким образом, мы получаем максимум $192+144+ 24= 360$ закрашенных ячеек, что противоречит условию задачи. Значит, наше предположение было неверно.

Ошибка.
Попробуйте повторить позже

Задача 3#68710

На бесконечной клетчатой плоскости некоторые клетки покрашены в красный цвет, некоторые — в синий, а некоторые остались непокрашенными. Известно, что в каждой строчке, где есть хотя бы одна синяя клетка, есть также хотя бы 5 красных, а в каждом столбце, где есть хотя бы одна красная клетка, есть хотя бы 6 синих. Какое наименьшее положительное число покрашенных клеток может быть на плоскости?

Источники: ИТМО-2023, 11.8 (см. olymp.itmo.ru)

Подсказки к задаче

Подсказка 1

Для начала заметим, что мы можем избавиться от всех столбцов, в которых все клетки синие и от всех строк, в которых все клетки красные. Теперь в каждом столбце и строке у нас и синие, и красные клетки. Пусть у нас есть m строк и n столбцов ,x-кол-во красных клеток, y-кол-во синих клеток. По условию в каждом столбце хотя бы 6 синих клеток => y>=6n, аналогично x>=5m. В каждой строке есть хотя бы одна синяя клетка и 5 красных, n>=6.Аналогично m>=7.Чтобы догадаться до ответа, бывает полезно рассмотреть частный случай. Попробуйте рассмотреть случай, когда все закрашенные клетки будут находиться только на пересечении строк и столбцов.

Подсказка 4

Так как n<=9 и x>=60, то в каком-то столбце >=7 красных клеток, тогда в каком-то столбце >=13 клеток, тогда m>=13 и x>=65 и y<55. Вам не кажется это похожим на предыдущий шаг? Попробуйте теперь сами сделать то же самое.

Подсказка 5

После нескольких таких шагов мы получим, что n<=5, но у нас n>=6. Противоречие! Со вторым случаем делаем то же самое. Оценка доказана. Значит, наш ответ 120.

Показать ответ и решение

Примеров для 120 закрашенных клеток несколько, они все отличаются перестановкой строк и столбцов. Можно взять прямоугольник $12× 10$ и раскрасить его в шахматном порядке в красный и синий цвет.

Докажем теперь, что меньше 120 закрашенных клеток не может быть.

Если в каком-то столбце есть закрашенные клетки, то по условию они либо только синие, либо обоих цветов. При этом, если в каком-то столбце все закрашенные клетки синие, можно превратить их все в незакрашенные. При этом условие задачи сохранится, а количество закрашенных клеток уменьшится (но не до нуля, так как в строчках с этими синими клетками останутся какие-то красные). Аналогичным образом можно избавиться от строчек, в которых есть красные клетки, но нет синих. Теперь можно считать, что во всех строчках и столбцах, где есть закрашенные клетки, присутствуют клетки обоих цветов.

Пусть у нас $x$ красных клеток и $y$ синих, при этом закрашенные клетки находятся в $m$ строках и $n$ столбцах. Так как в каждом из этих $n$ столбцов присутствуют хотя бы 6 синих клеток, выполняется неравенство $y ≥6n$ или, что то же самое, $y n ≤ 6.$ Аналогично, $x ≥5m$ или, что то же самое, $m ≤ x . 5$ Также заметим, что в каждой строке есть хотя бы одна синяя клетка и 5 красных, $n≥ 6.$ Аналогично $m ≥7.$

Сравним числа $6x$ и $5y.$

Пусть $6x ≥5y,$ то есть $x≥ 5y. 6$ В каждом столбце присутствуют хотя бы 6 синих клеток. Из взятого в качестве предположения неравенства следует, что в каком-то столбце количество красных клеток хотя бы $5 6y$ от количества синих, то есть хотя бы 5, поэтому общее количество закрашенных клеток в данном столбце хотя бы 11, откуда $m ≥11$ и, следовательно, $x ≥55.$ Если $y ≥ 65,$ $x+ y ≥ 120$ и оценка доказана. Предположим, $y < 65,$ тогда $n< 11,$ то есть не превосходит 10.

Но раз $n≤ 10,$ а $x≥ 55,$ в каком-то из наших не более чем 10 столбцов присутствуют хотя бы 6 красных клеток. Так как в нём должно быть ещё и 6 синих, мы получаем, что общее количество закрашенных клеток в этом столбце хотя бы 12, то есть, $m≥ 12$ и $x≥ 5m≥ 60.$ Тогда, чтобы $x+ y$ было меньше 120, необходимо $y ≤ 59.$ Продолжим эти рассуждения.

Поскольку $y ≤ 59,$ значит $n ≤9.$ Значит, в каком-то столбце присутствуют хотя бы $60 -9 ,$ то есть хотя бы 7 красных клеток, откуда $m ≥ 7+ 6= 13,$ $x ≥5m ≥ 65,$ $y ≤54.$

Поскольку $x≥ 65,$ в каком-то столбце присутствуют хотя бы $65 9-,$ то есть хотя бы 8 красных клеток, откуда $m ≥8+ 6= 14,$ $x ≥5m ≥ 70,$ $y ≤49.$

Поскольку $y ≤ 49,$ значит, $n ≤ 8.$ Значит, в каком-то столбце присутствуют хотя бы $65-, 8$ то есть хотя бы 9 красных клеток, откуда $m ≥ 9+ 6= 15,$ $x ≥5m ≥ 75,$ $y ≤44.$

Поскольку $y ≤ 44,$ значит, $n ≤ 7.$ Значит, в каком-то столбце присутствуют хотя бы $75, 7$ то есть хотя бы 11 красных клеток, откуда $m ≥ 11+6 =17,$ $x≥ 5m ≥85,$ $y ≤ 34.$

Поскольку $y ≤ 34,$ значит, $n≤ 5.$ Значит, в каком-то столбце присутствуют хотя бы $85, 6$ то есть хотя бы 15 красных клеток, откуда $m ≥15+ 6= 21,$ $x≥ 5m≥ 105,$ $y ≤ 14.$ Отсюда получаем, что $n≤ 2,$ что противоречит доказанному ранее.

Аналогично разбираем случай, когда $6x< 5y,$ то есть $x< 5y. 6$ В каждой строке присутствуют хотя бы 5 красных клеток. Из взятого в качестве предположения неравенства следует, что в какой-то строке есть хотя бы 6 синих клеток, то есть общее количество закрашенных клеток в данной строке хотя бы 11, откуда $n≥ 11$ и, следовательно, $y ≥66.$ Если $x ≥54,$ $x+ y ≥ 120$ и оценка доказана. Предположим, $x <54,$ тогда $m< 11,$ то есть не превосходит 10.

Но раз $m ≤ 10,$ а $y ≥66,$ в какой-то из наших не более чем 10 строк присутствуют хотя бы 7 синих клеток. Так как в ней должно быть ещё и 5 красных, мы получаем, что общее количество закрашенных клеток в этой строке хотя бы 12, то есть, $n ≥12$ и $y ≥ 6n≥ 72.$ Тогда, чтобы $x +y$ было меньше 120, необходимо $x ≤47.$ Продолжим эти рассуждения.

Поскольку $y ≥ 72,$ в какой-то строке присутствуют хотя бы $72-, 9$ то есть хотя бы 8 синих клеток, откуда $n ≥8 +5= 13,$ $y ≥ 6n≥ 78,$ $x ≤41.$

Поскольку $x≤ 41,$ значит $m ≤ 8.$ Значит, в какой-то строке присутствуют хотя бы $78, 8$ то есть хотя бы 10 синих клеток, откуда $n≥ 10+ 5= 15,$ $y ≥6n ≥90,$ $x≤ 29.$ Отсюда получаем, что $m ≤ 5,$ что противоречит доказанному ранее.

Таким образом, мы разобрали оба случая и доказали, что ситуация, в которой $x+ y < 120$ невозможна.

Ответ: 120

Ошибка.
Попробуйте повторить позже

Задача 4#68521

На конференцию приехали $100$ учёных. Оказалось, что у любых двоих как минимум двое общих знакомых. Докажите, что у кого-то из них хотя бы $15$ знакомых.

Источники: ИТМО - 2023, 10.7

Показать доказательство

Предположим противное. Рассмотрим граф, вершинами которого будут являться учёные, две вершины будем соединять ребром, если соответствующие учёные знакомы. Из нашего предположения степень каждой вершины не превосходит $14$ . Посчитаем двумя способами количество растопырок, то есть конфигураций из $3$ вершин, одна из которых (будем называть её главной) соединена с двумя другими). С одной стороны для каждой пары вершин к ним в растопырку можно выбрать хотя бы $2$ главные. Итого растопырок не меньше, чем $100⋅99⋅2 ---2----=9900$ . С другой стороны для каждой вершины количество растопырок, в которых она является главной, не превосходит $14⋅13= 91 2$ . То есть всего растопырок не больше $100⋅91= 9100 <9900$ , откуда получаем противоречие.

Ошибка.
Попробуйте повторить позже

Задача 5#74587

В таблице $8× 8$ какие-то $23$ клетки чёрные, а остальные — белые. В каждой белой клетке написали суммарное количество чёрных, находящихся с ней на одной горизонтали и находящихся с ней на одной вертикали; в чёрных клетках ничего не написано. Какое наибольшее значение может принимать сумма чисел во всей таблице?

Источники: ИТМО-2022, 11.8 (см. olymp.itmo.ru)

Подсказки к задаче

Подсказка 1

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

Подсказка 2

Пусть в строке находится x черных 8-x белых. Теперь мы можем посчитать сумму во всех строках. Для того чтобы максимизировать такую сумму, нам нужно минимизировать сумму восьми квадратов с фиксированной суммой. Как?

Подсказка 3

Сумма квадратов чисел уменьшается при сближении этих чисел к их среднему арифметическом, поэтому для целых чисел минимум достигается, когда семь из восьми чисел равны 3, а оставшееся равно 2. Теперь мы можем проделать аналогичные действия с вертикалями и построить пример!

Показать ответ и решение

Число в белой клетке состоит из двух слагаемых: "горизонтального"и "вертикального". Рассмотрим отдельно сумму всех "горизонтальных"и отдельно сумму всех "вертикальных"слагаемых по всей таблице. Если мы максимизируем каждую из этих двух сумм по отдельности, общая сумма также будет наибольшей.

Рассмотрим сумму "горизонтальных"слагаемых. Если в строке находится $xi$ чёрных клеток и $8 − xi$ белых, то сумма горизонтальных слагаемых в этой строке составляет $xi(8− xi)$ . Просуммировав эту сумму по всем строкам, мы получаем

( ) 8(x1 +...+ x8)− x21− ...− x28 = 8⋅23− x21+ ...+ x28

Нам нужно максимизировать это выражение, т.е. минимизировать сумму квадратов восьми чисел, сумма которых составляет 23. Как известно, сумма квадратов чисел уменьшается при сближении этих чисел к их среднему арифметическом, поэтому для целых чисел минимум достигается, когда семь из восьми чисел равны 3, а оставшееся равно 2.

Таким образом, мы получаем, что наименьшая возможная сумма "горизонтальных"слагаемых равна

8⋅23− 7 ⋅32− 22 = 117

Аналогичную оценку можно получить для суммы "вертикальных"слагаемых, что даёт нам итоговое значение 234.

Осталось убедиться, что существует раскраска таблицы, при которой обе суммы максимальны одновременно, то есть в которой в каждом столбце или строке по 2 или 3 закрашенных клетки.

$PIC$

Ответ: 234

Ошибка.
Попробуйте повторить позже

Задача 6#74585

Дан правильный $n$ -угольник $(n= 4k+ 2),$ в котором проведены все диагонали. Докажите, что они образуют не больше

n(n-− 1)(n-− 2)(n-− 3) n (n ) n (n ) ( n ) 24 − 4 ⋅ 2 − 1 + 1− 2 ⋅ 2 − 1 ⋅ 2 − 3

точек пересечения (не считая вершин).

Источники: ИТМО-2022, 11.7 (см. olymp.itmo.ru)

Подсказки к задаче

Подсказка 1

Нам дали уж слишком какое-то магическое число, но каждое его слагаемое похоже на какой-то комбинаторный подсчёт. Может быть, у нас получится объяснить, как получить каждое из этих слагаемых?

Подсказка 2

1-ое слагаемое: эта формула нам так и кричит, что в ней выбрали 4 вершины многоугольника без учёта их порядка. А как выбор 4-ёх вершин связан с диагоналями?

Подсказка 3

2-ое слагаемое: с помощью какого предположения было получено первое слагаемое? Заметьте, что почти каждое следующее слагаемое стоит со знаком минус, а значит, они как-то уточняют нашу первоначальную оценку.

Подсказка 4

2-ое слагаемое: давайте вспомним, что у нас в условии правильный многоугольник, попробуйте порисовать разные правильные многоугольники и диагонали в них, чтобы найти такую точку, в которой всегда пересекаются много диагоналей, что это за точка?

Подсказка 5

2-ое слагаемое: верно, это центр нашего многоугольника. Остаётся только посчитать, сколько раз мы посчитали её и вычесть так, чтобы по итогу в нашем подсчёте точка осталась учтена.

Подсказка 6

3-е слагаемое: оно явно содержит похожие диагонали на те, которые мы выбирали, когда рассуждали про центр, потому что в нём тоже фигурирует n/2. Может быть стоит опять порассуждать про такие диагонали?

Подсказка 7

3-е слагаемое: первый множитель в слагаемом это n/2, давайте тогда зафиксируем какую-то диагональ, проходящую через центр многоугольника. Попробуйте понять, что означают остальные множители, последовательно распутывая, за что отвечает каждый из множителей.

Подсказка 8

3-е слагаемое: верно, слева и справа от диагонали осталось по n/2-1 точке. А значит, вторым действием мы скорее всего выбрали с одной из сторон одну из точек. Почему тогда последний множитель не такой же, а имеет на 2 точки меньше? Понятно, что, выкинув 2 точки с другой стороны, мы запретили какие-то 2 диагонали, остаётся понять - какие?

Подсказка 9

3-е слагаемое: кажется, что пока наши рассуждения задают только пару диагоналей и проблем не видно, но можно ли как-то для этой пары найти однозначно третью диагональ, которая бы проходила через их точку пересечения?

Подсказка 10

3-е слагаемое: да, можно, если отразить симметрично вторую диагональ относительно "центральной".

Подсказка 11

3-е слагаемое: а вы заметили, что на самом деле это слагаемое содержит в себе удвоенное количество ситуаций, про которые мы рассуждали? Ведь, когда мы брали диагональ-1 с концами по разные стороны от "центральной" диагонали и отражали её, то получалась диагональ-2, которая тоже может быть посчитана нашими рассуждениями, а так как симметричная для 2-ой диагонали - 1-ая, то мы посчитали всё дважды. А сколько раз мы посчитали такие ситуации в 1-ом слагаемом?

Подсказка 12

Верно, по 3 раза, потому что там мы выбираем неупорядоченную пару диагоналей, а в наших рассуждениях мы получали неупорядоченные тройки диагоналей (если учесть, что мы посчитали их дважды), а значит 1 наша тройка содержит по 3 пары. Но вычесть всё равно придётся удвоенное количество, поэтому мы победили!!!

Показать доказательство

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

n(n− 1)(n− 2)(n− 3) --------24--------

Однако, при таком подсчёте точки, в которых пересекаются больше двух диагоналей, посчитаны несколько раз.

Во-первых, поскольку количество вершин чётно, $n2$ "длинных"диагоналей (соединяющий противоположные вершины многоугольника) пересекаются в центре многоугольника. Эта точка посчитана

n (n ) 2-⋅-2 −-1 2

раз, в то время как должна быть посчитана 1 раз. Значит, из вычисленного количества надо вычесть

n ( n ) 2 ⋅-2 −-1-− 1 2

Во-вторых, для каждой "длинной"диагонали можно взять две симметричные относительно неё диагонали, не проходящие через центр многоугольника. "Длинную"диагональ можно выбрать $n 2$ способами. Для удобства представим себе, что выбранная диагональ расположена вертикально. По каждую сторону от этой диагонали остаётся $n 2 − 1$ вершина. Мы выбираем вершину $A$ слева от “длинной” диагонали, после чего для выбора вершины $B$ справа у нас остаётся $n 2 − 3$ варианта: мы не можем выбрать вершину, симметричную $A$ относительно "длинной"диагонали (иначе диагональ $AB$ будет симметрична сама себе) и вершину, симметричную относительно центра, иначе $AB$ будет "длинной а эти точки пересечения мы уже учли.

Симметричная диагональ $′ ′ A B$ выбирается единственным образом. Однако каждую пару диагоналей $AB$ и $′′ A B$ мы посчитали дважды, потому что в качестве первой выбранной диагонали могла быть взята любая из них. Таким образом, точку пересечения трёх диагоналей мы умеем искать

n (n ) ( n ) 2 ⋅ 2 − 1 ⋅ 2 − 3 --------2--------

способами. В исходной формуле каждая такая точка посчитана трижды, то есть два лишних раза. Значит, мы получаем ещё на

n (n ) ( n ) 2 ⋅ 2 − 1 ⋅ 2 − 3

точек меньше.

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

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#68795

На собрании присутствовали рыцари, всегда говорящие правду и лжецы, которые всегда лгут (точно есть и те, и другие). Каждый сказал: “Я знаком хотя бы с $15$ рыцарями на этом собрании” и “Я знаком хотя бы с $11$ лжецами на этом собрании”. Какое наименьшее количество человек могло собраться?

Источники: ИТМО-2020, 11.5 (см. olymp.itmo.ru)

Показать ответ и решение

Рассмотрим произвольного рыцаря. Из его фразы следует, что на собрании $≥16$ рыцарей и $≥ 11$ лжецов. Построим двудольный граф знакомств рыцарей и лжецов, в первой доле вершины — рыцари, во второй — лжецы. Из каждой из хотя бы $16$ вершин первой доли исходит минимум $11$ ребер, следовательно, ребер в графе $≥16⋅11= 176.$ C другой стороны, лжец знаком не более, чем с $14$ рыцарями, а значит, если лжецов $k,$ то имеем $k⋅14≥ 176⇔ k≥ 13.$

Приведем пример на $16$ рыцарей и $13$ лжецов: пронумеруем рыцарей и лжецов. Рассмотрим первых $13$ рыцарей. Пусть среди них рыцари и лжецы с одинаковыми номерами будут не знакомы. А также со сдвигом на один: второй рыцарь не знаком с первым лжецом, третий рыцарь со вторым и так далее. Все остальные знакомы, рыцари попарно знакомы между собой, а лжецы попарно не знакомы. Такая ситуация подходит, так как каждый лжец не знаком хотя бы с двумя рыцарями, и каждый рыцарь знаком хотя бы с $11$ лжецами.

Ответ: 29

Ошибка.
Попробуйте повторить позже

Задача 8#67077

Сколькими разными способами можно в таблице $2 ×7$ расставить натуральные числа от 1 до 14 (все по одному разу) так, чтобы сумма чисел в каждом из семи столбцов была нечётна?

Источники: ИТМО-2019, 11.6 (см. olymp.itmo.ru)

Подсказки к задаче

Подсказка 1

Какие должны быть два числа, чтобы их сумма была нечетной? Очевидно, одно - четным, другое - нечетным. Кстати, у нас всего 7 четных и 7 нечетных чисел. Сколько способов выбрать, какое по четности число будет в верхней клетке столбцов?

Подсказка 2

Конечно, выбираем из четного или нечетного числа - 2 способа заполнить столбец, но для каждой расстановки в первом столбце подходят все расстановки остальных столбцов, значит, применяем правило умножения и получаем коэффициент 2⁷. Теперь подумаем, сколько способов есть расставить все четные числа в одном из 2⁷ возможных вариантов по четности/нечетности.

Подсказка 3

7 чисел на 7 мест, причём важен порядок -> получили 7! способов. Но не кажется ли вам, что столько же способов и для нечетных чисел, ибо логика действий сохраняется и для них. А еще для каждой расстановки четных чисел подходят все расстановки нечетных чисел, следовательно, 7! возведётся в квадрат. Вспоминаем про коэффициент из 2 подсказки и получаем ответ.

Показать ответ и решение

В каждом столбце стоит одно чётное и одно нечётное число. Где стоит чётное число, а где нечётное, выбирается двумя способами, итого $27$ способов для всей таблицы. Далее, существует $7!$ способов расставить чётные числа по выбранных для них местам и столько же способов расставить нечётные. Итого $7 2 2 ⋅(7!)$ способов.

Ответ:

$27⋅(7!)2$

Ошибка.
Попробуйте повторить позже

Задача 9#61483

Сколькими способами можно расставить натуральные числа от $1$ до $9$ в квадратной таблице $3× 3$ так, чтобы сумма чисел в каждой строке и в каждом столбце была чётна? (Числа могут повторяться)

Показать ответ и решение

Будем расставлять в таблицу нули и единицы. Каждый $0$ можно поставить четырьмя способами, а $1$ — пятью. Заметим, что в каждой строчке чётное количество единиц, потому единиц суммарно в таблице может быть $0,2,4,6$ ( $8$ быть не может, поскольку в каждой строчке не более двух). Также заметим, что двух единиц быть не может, поскольку тогда бы они стояли в одной строчке и их было бы по одной в столбце. Разберём остальные случаи

Пусть единиц нет. Тогда имеем $9$ чётных чисел и $9 4$ способов в этом случае.
Пусть единиц четыре. Тогда они стоят на пересечении двух строчек и двух столбцов. Выбираем строчки и столбцы $2 2 C 3 ⋅C3 = 9$ способами, в итоге имеем $5 4 9⋅4 ⋅5$ способов.
Пусть единиц шесть. Тогда оставшиеся нули стоят в разных строчках (в каждой строчке и в каждом столбце должно быть ровно по две единицы). Число способов так расставить нули равно $3!=6$ , откуда имеем $6⋅56⋅43$ .

Ответ:

$49+ 9⋅45⋅54 +6⋅56⋅43$

Ошибка.
Попробуйте повторить позже

Задача 10#73684

В некоторой стране $450$ городов и $6$ авиакомпаний. Каждые два города соединены рейсами одной из шести авиакомпаний. Можно ли утверждать, что найдется авиакомпания и больше $150$ городов, между любыми двумя из которых можно добраться рейсами этой авиакомпании (возможно, с пересадками)?

Показать ответ и решение

Построим контрпример. Разобьём города на $6$ групп по $75$ городов. Назовём эти группы $A,B,C,D,E,F.$

Внутри каждой группы соединим города рейсами компании номер $1.$

Компания номер $2$ будет соединять города группы $A$ с городами группы $B,C$ с $D,$ а $E$ с $F.$

Компания номер $3$ будет соединять города группы $A$ с городами группы $D,B$ с $E,$ а $C$ с $F.$

Компания номер $4$ будет соединять города группы $A$ с городами группы $C,B$ с $F,$ а $D$ с $E.$

Компания номер $5$ будет соединять города группы $A$ с городами группы $E,B$ с $C,$ а $D$ с $F.$

Компания номер $6$ будет соединять города группы $A$ с городами группы $F,B$ с $D,$ а $C$ с $E.$

Таким образом, рейсы компании номер $1$ связывают по $75$ городов, а рейсы остальных компаний ровно по $150.$

Это построение схематически изображено на рисунке. Разные компании обозначены разными цветами.

$PIC$

Ответ:

Нет

Ошибка.
Попробуйте повторить позже

Задача 11#36854

В городе Джентльвилле живут $15$ джентльменов, любые двое из которых либо дружат, либо враждуют. В какой-то момент каждый джентльмен попросил каждого из своих друзей послать открытку ненависти каждому из своих врагов (джентльмен $A$ просит джентльмена $B$ послать открытку всем врагам джентльмена $B$ ). Каждый из джентльменов выполнил все просьбы; при этом он посылал каждому из своих врагов такое количество открыток, сколько раз его об этом просили. Какое наибольшее количество открыток могло быть послано?

Источники: ИТМО-2016, отборочный тур, 11 класс (см. olymp.itmo.ru)

Подсказки к задаче

Подсказка 1!

1) Так, было бы здорово оценить количество открыток как-то, в зависимости от количества друзей, чтобы попробовать посчитать максимум..... Например, если у человека друзей будет х, а врагов соответственно 14-х, то сколько открыток он пошлет?

Подсказка 2!

2) Так, хорошо, х(14-х)! Нужно понять, где это выражение принимает максимум, и проверить, получится ли наш максимум достигнуть... Было тут у нас какое-то утверждение про степени вершин в графе... Хм...

Подсказка 3!

3) Ага, вот оно! Лемма о рукопожатиях! Теперь идейно задачу решили, осталось только немного разобраться, как все же получить новый максимум!

Показать ответ и решение

Рассмотрим полный граф на $15$ вершинах, вершинами которого являются джентльмены, а рёбрами — отношения между ними. Покрасим между двумя вершинами в белый цвет, если джентльмены, соответствующие этим вершинам дружат. А чёрные ребра будут символизировать вражду между людьми.

Оценка.

Пусть у джентльмена с номером $n$ ( $1≤ n≤ 15$ ) ровно $xn$ друзей и $14 − xn$ врагов ( $xn ∈ ℕ∪ {0}$ ). Тогда он отправил ровно $xn⋅(14− xn)$ писем. Это выражение является квадратным трёхчленом, наибольшее значение которого достигается при $xn =7$ и равно $49.$ Тогда число отправленных всеми джентльменами писем не превосходит $49 ⋅15.$

Покажем, что отправить ровно $49⋅15$ писем невозможно по лемме о рукопожатиях (в любом графе количество вершин нечётной степени чётно). Действительно, в таком случае у каждого джентльмена должно быть $7$ друзей и $7$ врагов. Рассмотрим подграф из всех вершин и только белых рёбер. В этом подграфе количество рёбер (количество пар друзей среди джентльменов) равно половине от суммы степеней вершин (у каждого по $7$ друзей, но одну и ту же пару считаем дважды), то есть $7⋅125.$ Противоречие с тем, что это число должно быть целым.

Пример.

Покажем, что отправить $49 ⋅15− 1= 734$ писем возможно. Достаточно построить “чёрный” подграф: нужно соединить каждого джентльмена с тремя следующими — получим однородный граф степени $6,$ затем останется соединить каких-то $7$ подряд с джентльменами, которые идут на $7$ позиций позже по кругу. То есть $1 ⇐ ⇒ 8,2 ⇐⇒ 9...7 ⇐⇒ 14.$ Тогда степени первых $14$ -и вершин станут равны $7,$ а у $15$ -й она останется равной $6.$

Ответ:

$734$

Предыдущий раздел

Следующий раздел