Оценка + пример

Пример: 9 монет по 1 рублю, 9 монет по 2 рубля, 9 монет по 5 рублей и 1 монета по 10 рублей. Заметим, что в кошельке всего монет достоинством не 1 рубль, пюэтому среди любых 20 монет обязательно встретится рублевая. Аналогично проверяется и про все остальные номиналы.

Оценка: Предположим, что в кошельке лежит монет. Так как монет достоинством не 1 рубль не больше 19 (иначе наплось бы 20 монет, не содержащих рублевую), рублевых монет должно быть не менее 19. Аналогично двухрублевых и пятирублевых. Следовательно, всего монет не менее . Получаем неравенство , откуда . Так как - целое, оно не превосходит 28 .

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

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

Предположим, что в -буквенном алфавите существует хорошее слово длины Тогда какая-то буква (скажем, встречается в нём хотя бы три раза. Отметим её второе и предпоследнее вхождение в слово (тогда стоит не правее, чем

Любая другая буква встречается не более одного раза перед а также не более одного раза после иначе вычёркиванием можно получить запрещённую последовательность. Значит, каждая из букв встречается не более двух раз. Более того, если такая буква и встречается дважды, то одно из её вхождений стоит до а другое — после

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

что противоречит нашему предположению.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Приведём другое доказательство того, что длина хорошего слова не превосходит Индукция по В базовом случае буквы в слове чередуются, и слово длины хотя бы содержит фрагмент вида из которого вычёркиванием букв можно получить Для перехода предположим, что в -буквенном алфавите есть хорошее слово длины, не меньшей Тогда какая-то буква встречается в этом слове хотя бы три раза. Предположим, что букв, встречающихся хотя бы раза, две — и Пусть, без ограничения общности, второе вхождение стоит раньше второго вхождения тогда вычёркиванием букв можно получить слово что невозможно. Значит, буква встречается в слове раз, а все остальные — максимум по два раза. Тогда длина слова не меньше, чем и не больше, чем откуда Между вторым и третьим вхождением буквы есть какая-то буква Эта буква не может встречаться в других местах: если она встречается после второго вхождения то вычёркиванием букв можно получить а если до него — то (поскольку Пусть соседи буквы различны. Тогда, удалив её из слова, мы получим хорошее слово в -буквенном алфавите (без буквы Длина этого слова будет не меньше что противоречит индукционному предположению. Если же соседи буквы одинаковы, удалим из слова и букву перед ней; тогда на этом «стыке» останутся различные буквы. Поэтому мы опять получим хорошее слово в -буквенном алфавите, длина которого не меньше, чем это опять же невозможно по индукционному предположению.

Пример. Рассмотрим все слов, у которых начиная с -ой все буквы Ш, а первые — У или Я. Этот набор слов удовлетворяет условию.

Оценка. Каждому из наших слов сопоставим слов, заменяя каждую букву Ш, на У или Я (всеми возможными способами). Заметим, что полученные слов состоят из букв У и Я и попарно различны (для слов, полученных из одного и того же, это ясно из построения, а для слов, полученных из двух разных, следует из условия). Таким образом, и

______________________________________________________________________________________________________________________________________________________

Замечание. Оценку можно получить по-другому.

Способ 1. Подкинем монетку раз. Для каждого слова рассмотрим такое событие: при всяком если на некоторой позиции стоит буква У, то при -м подбрасывании выпала решка, а если буква Я, то орёл. Вероятность такого события равна и они не совместные, поэтому количество слов не больше чем

Способ 2. Пусть выбрано более слов. Присвоим каждому слову вес Пусть первая буква у слов У, у слов — Я и Удвоим веса всех слов с первой буквой У, и обнулим — с первой буквой Я. Далее посмотрим на вторую букву и т.д. Опишем шаг рассмотрения -ой буквы. Пусть — сумма весов слов, у которых -ая буква У, — сумма весов слов, у которых -ая буква Я. Если удваиваем веса у слов с -й буквой Я и обнуляем — с -й буквой У. Иначе — наоборот. В результате таких операций сумма весов не уменьшается. После операций сумма весов всех слов будет больше В каждом слове только букв У или Я, поэтому вес каждого слова не больше Значит, найдутся два слова с одинаковыми весами. Тогда для них не найдется позиции, в которой у одного У, а у другого Я или наоборот, противоречие.

Оценка:

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

Разобьем доску x на таких прямоугольников x В каждом из них нужно закрасить минимум клетки, тогда всего на доске нужно закрасить хотя бы клеток.

_________________________________________________________________________________________________________________________________________________________________________________

Пример с клетками приведен на рисунке:

Пример, когда клеток хватает:

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

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

троек гномиков (первый гномик может быть выбран не более, чем способами, второй — способами, третий — способами, при этом порядок выбора гномиков не важен).

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

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

Значит, существует сдвиг, в котором будет не более совпадений с исходной расстановкой.

Рассмотрим такую расстановку чашек:

Непосредственной проверкой можно убедиться, что все её циклические сдвиги имеют с ней ровно совпадений.

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

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

В качестве примера рассмотрим табличку с отмеченными клетками

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

Предположим, что при постояльцах директор не может осуществить переселение. Разобъём комнаты на пары по вместимости: Отметим, что для каждой пары комнат суммарное количество человек, живущих в двух комнатах, больше, чем вместимость большей комнаты из пары, иначе всех человек из этой пары можно было бы собрать в комнате с большей вместимостью. Таким образом, общее количество человек не меншше Поэтому при постояльцах директор может освободить комнату.

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

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

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

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

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

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

противоречие.

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

Где различными суммами будут .

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

Пример при на рисунке.

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

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

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

Теперь покажем, что меньше сумма оценок быть не может, то при сумме меньше все ученики могут получить подарки, если такая сумма вообще возможна. Обозначим сумму оценок через Сначала выставим всем пятерки по обоим предметам. В этот момент сумма оценок ровно Далее, первому ученику вместо пятерки по музыке поставим двойку. Теперь сумма Оценку по рисованию первому ученику изменим на или так, чтобы остаток у новой суммы и при делении на совпали. Теперь будем менять всем школьникам пятерки на двойки, пока сумма не станет равна Если такой момент не настал, то даже после замены всех пятерок на двойки полученная сумма больше а так как остатки у и текущей суммы при делении на одинаковы, то эта сумма больше хотя бы на Значит, даже если у первого ученика изменить оценку по рисованию на двойку (если она еще не была заменена), все равно текущая сумма останется больше При этом теперь у всех школьников и по музыке, и по рисованию двойки. Значит, текущая сумма равна а то есть такой суммы просто не может быть.

Оценка. Рассмотрим ряд монет, в котором нет тройки. Если в нем есть хотя бы монеты, то среди первых двух монет есть и и копейки, как и среди третьей и четвертой монеты. Две копеечные монеты не могут идти рядом, поэтому между двумя двухкопеечными монетами лежит не более одной монеты. Противоречие. Следовательно, без трехкопеечных монет может идти не более трех монет.

Если трехкопеечных монет не более то промежутков без них не более и всего монет не более Противоречие, поэтому трехкопеечных не менее

Если трехкопеечных монет хотя бы то промежутков без них хотя бы и всего монет хотя бы Противоречие, поэтому трехкопеечных не более

Пример. Поставим монеты. На четные места поставим по копейке, на места вида поставим трехкопеечные, на места вида поставим двухкопеечные. Промежуток с по монеты дает пример на трехкопеечных монет. Промежуток с по монету дает пример на трехкопеечных монет.

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

Рассмотрим бревно длины его распилили на брёвнышки длины меньше значит, их было не меньше то есть хотя бы Итак, самое правое из этих брёвнышек по длине меньше чем

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

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

Пример. Чтобы отдохнуть дней, достаточно сначала отработать раз по неделе, беря при этом два выходных (в итоге за дня получится выходных), а из оставшихся дней отработать дня, после чего взять один выходной.

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

Пример. школьников достаточно, для этого им достаточно сесть через одного и чередовать верхнюю и нижнюю строчки.

Оценка. и меньше школьников не хватит. Заметим, что один школьник “занимает” не более четырех мест: остальные школьники не могут садиться на его место, а также на не более чем три соседних с ним места. Поэтому школьников займут не более мест, а всего места, значит, еще один школьник точно влезет.

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

Рассмотрим грань, содержащую вершину, в которой стоит число Поскольку сумма чисел, стоящих в остальных трёх вершинах, не меньше сумма всех чисел в вершинах этой грани не меньше

Пример расстановки, при которой наименьшая сумма чисел, стоящих в вершинах одной грани, равна приведён на рисунке: сумма чисел в передней грани равна