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

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

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

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

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

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

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

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

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

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

Задача 1#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$ закрашенных ячеек, что противоречит условию задачи. Значит, наше предположение было неверно.

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

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

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

Задача 2#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

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

Задача 3#68521

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

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

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

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

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

Задача 4#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

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

Задача 5#88876

Клетчатая доска $9× 9$ вся заполнена фишками. Петя и Вася играют в следующую игру: за один ход можно выбрать горизонталь или вертикаль, на которой ещё остались фишки, и снять оттуда все оставшиеся фишки. Выигрывает игрок, после хода которого доска опустеет. Первым ходит Петя. Кто выиграет при правильной игре?

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

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

Вася будет действовать так: если Петя убирает строку, Вася убирает столбец, и наоборот. Таким образом, оставшиеся фишки всегда будут образовывать квадрат. Так будет продолжаться, пока оставшиеся фишки не образуют квадрат $2×2.$ После этого Петя убирает две фишки, а Вася — две оставшиеся.

Ответ: Вася

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

Задача 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#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

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

Задача 8#99642

Палиндром — это слово, которое не меняется, если в нём переставить буквы в обратном порядке, например $abcba$ . Сколько различных $11$ -буквенных слов можно составить из букв $a,b,c,d,e$ так, чтобы они не содержали палиндромов длины больше $1?$

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

Подсказка 1

Что означает, что у нас есть палиндром? Это значит, что есть палиндром чётной длины или нечётной длины. А что следует из этого утверждения? Какое более просто условие на слово нам достаточно проверять, чтобы слово было свободно от палидромов?

Подсказка 2

Это значит, что не должно быть палиндрома длины 2 и длины 3. Ну отсутствие палиндрома длины 3, равносильно тому, что у нас буквы через 1 не совпадают. А отсутствие длины два, значит, что не совпадают соседние. Какое тогда условие равносильно отсутствию палиндромов длины 2 и 3?

Подсказка 3

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

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

Заметим, что две центральные буквы любого палиндрома чётной длины одинаковы, то есть образуют палиндром длины два. Точно так же три центральные буквы палиндрома нечётной длины образуют палиндромы длины три. Таким образом, отсутствие в слове палиндромов равносильно отсутствию палиндромов длины $2$ и $3.$ Это, в свою очередь, равносильно тому, что любые три подряд идущие буквы в слове различны.

Первая буква в слове выбирается пятью способами, для следующей остаётся $4$ способа. Каждая из последующих букв не может совпадать с двумя предыдущими, поэтому для неё остаётся $3$ способа. Все эти числа надо перемножить, поэтому мы получаем

5(5 − 1)(5 − 2)11−2 = 393600

Ответ:

$393660$

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

Задача 9#99651

Гензель и Гретель играют в игру, Гензель ходит первым. Они по очереди ставят фишки на клетчатую доску $7× 8$ ( $7$ строк и $8$ столбцов). Каждый раз, когда Гретель ставит фишку, она получает $4$ очка за каждую фишку, уже стоящую в той же строке и $3$ очка за каждую фишку, уже стоящую в том же столбце.

На одной клетке может стоять только одна фишка. Игра заканчивается, когда все клетки доски заполнены.

Какое наибольшее количество очков может заработать Гретель вне зависимости от действий Гензеля?

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

Подсказка 1

Предположим, что Гензель получает очки по тому же принципу. Тогда если мы выберем 2 клетки в одной линии, то тот, кто поставит в них фишку последним, заберёт свои очки за эту пару клеток. Может, у нас получится как-то посчитать общее количество очков, полученное за игру?

Подсказка 2

Верно, каждые две клетки в одном столбце дадут кому-то 4 очка, а в одной строке — 3 очка. Чтобы найти сумму набранных к концу игры очков, нужно просто посчитать количество пар клеток в строках и столбцах и сложить. Как Гретель заполучить как можно больше очков? После своего первого хода она может получить на 4 очка больше Гензеля... Как нам продолжить эту традицию?

Подсказка 3

Да, можно попробовать и дальше ставить фишки в одну строку с теми, куда только что ставил Гензель! А как это красиво оформить и понять? Может, посмотрим в сторону разбиений?

Подсказка 4

Например, разбиение 1х2! Как только Гензель займёт одну из клеток такого прямоугольника, Гретель закрывает вторую, каждым ходом забирая на 4 очка больше брата. Теперь можем найти миниальное количество очков, что она точно заберёт. Мы знаем, сколько очков они заработают на двоих и насколько больше очков Гретель получает каждым ходом. Остаётся только найти их общий отрыв по очкам, умножив на количество ходов Гретель, и составить уравнение!

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

Давайте скажем, что Гензель тоже получает очки по тому же принципу, что и Гретель. В таком случае, каждая пара клеток в одной строке даст в итоге какому-то из игроков $4$ очка, а каждая пара клеток в одном столбце — $3$ очка. В одной строке можно найти $8⋅7 2 = 28$ пар клеток, а в одном столбце — $7⋅6 2 =21$ пару. Общая сумма очков, набранных обоими игроками в конце игры, будет равна

7⋅28⋅4+ 8⋅21 ⋅3 =1288.

Приведём стратегию за Гретель, позволяющую ей каждый ход получать на $4$ очка больше, чем перед этим Гензель. Для этого разобъём каждую строку на 4 прямоугольника $1×2.$ Как только Гензель ставит фишку в одну из клеток прямоугольника, Гретель тут же занимает вторую. Столбцы, в которых находятся эти клетки, идентичны из-за стратегии Гретель, а в строке к моменту её хода находится на одну фишку больше — ровно на ту, которую поставил Гензель.

С другой стороны, если Гензель будет каждый раз выбирать клетку, которая приносит максимальное количество очков, Гретель своим следующим ходом сможет набрать максимум на $4$ очка больше, так как добавлением одной фишки Гензель повышает “ценность” каждой из оставшихся клеток не более, чем на $4.$

Каждый игрок сделает $28$ ходов и, при правильной игре, Гретель наберёт на $112$ очков больше. Зная сумму и разность двух чисел, можно легко найти сами числа, это $700$ и $588.$

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

Ответ:

$700$

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

Задача 10#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

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

Задача 11#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$

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

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

Задача 12#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$

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

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