Применение классических комбинаторных методов к разным задачам

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

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

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

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

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

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

Пример. Пример при котором получается

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

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

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

С другой стороны,

что противоречит неравенству выше.

Рассмотрим самую правую муху если таких несколько, выберем любую. Расположим салфетку вертикально так, чтобы попала на середину правой стороны. Все мухи, от которых до расстояние не более попадут под эту салфетку.

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

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

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

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

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

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

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

имеем и Следовательно, и каждая невыписанная попарная сумма чисел равна одной из семи сумм, рассмотренных в длинном неравенстве. Всего нерассмотренных сумм три:

и все они больше и меньше По условию, они должны совпадать с суммами

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

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

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

(b) Пример на получение единицы можно вывести из предыдущего пункта, только делить будем на пары откуда получится единиц, то есть помимо нулей в разности получится дополнительная единица — далее от неё уже никак не избавиться, можно просто по очереди вычесть из неё все нули.

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

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

Значит, и через 98 операций наше выражение будет равно . То есть в конце будет выписано число

Первое решение.

Обозначим детей, давших ответы через А, Б, В соответственно. Заметим, что если в классе мальчиков, то первое число в ответах девочек имеет ту же чётность, что и , а в ответах мальчиков - противоположную. Следовательно, дети А и Б одного пола, а В - другого.

Первые числа в ответах А и Б отличаются на 4, значит, они оба неправильные. Таким образом, количество одноклассников у А и Б равно 15 , а количество одноклассниц - 11 .

Если А и Б - мальчики, то в классе 16 мальчиков и 11 девочек. При этом у девочки В тогда 16 одноклассников и 10 одноклассниц, и ее ответ противоречит условию. Значит, А и Б девочки, и в классе 15 мальчиков и 12 девочек. ______________________

Второе решение.

Пусть какой-то ребёнок написал числа . Если бы оба числа он написал правильно, то он бы написал один из четырёх вариантов: .

Тогда, если этот ребёнок — мальчик, то существует четыре варианта количества мальчиков и девочек в классе: и .

Аналогично, если этот ребёнок — девочка; возможные варианты в этом случае: .

Таким образом, каждый из ответов даёт нам восемь вариантов, сколько мальчиков и девочек могло быть в классе, один из которых должен быть верным:

для это ;

для это ;

для это .

Осталось заметить, что только вариант встречается во всех трёх строчках.

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

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

Предположим противное. Упорядочим данные числа и обозначим их за что Заметим, что если мы рассматриваем тройку вида то в силу соображения, что среднее арифметическое чисел лежит между их минимумом и максимумом, среднее арифметическое данной тройки будет равно

Рассмотрим сначала тройку

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

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

Но такого числа нет на доске, противоречие.

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

100 операций достаточно.

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Заметим, что на пересечении строки и столбца одинаковой чётности должна стоять красная клетка, а на пересечении строки и столбца разной чётности — синяя, иначе знак в этой клетке после всех операций не изменится. Следовательно, количество красных клеток в каждой чётной строке равно числу чётных столбцов, а количество синих — числу нечётных столбцов таблицы. Есть хотя бы одна чётная строка , значит, всего в таблице чётное число нечётных столбцов. Но количество красных клеток в каждой нечётной строке (нечётное!) равно числу нечётных столбцов, то есть чётному числу — противоречие с тем, что есть хотя бы один нечётный столбец. Следовательно, нельзя обойтись меньше, чем 100 операциями.

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

Действительно, от второго действия величина дроби не меняется, осталось проверить первое действие.

Пусть на некотором шаге имеется дробь , где . Мы из нее получаем дробь , тогда . Чтобы доказать неравенство

просто перемножим крест-накрест, получив

что равносильно

Последнее неравенство очевидно следует из .

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

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

Зафиксируем (это можно сделать способами). Тогда для него получится таких троек. Итого получается

С другой стороны можно сначала выбрать способов, потом способа (нужно вычесть его друзей и его самого). Тогда можно выбрать 6 способами, итого

Получим уравнение откуда

Пример.

Одну из сторон разобьём на отрезков длины а другую — на отрезков длины и оставшийся отрезок длины . Тогда только прямоугольников с узкой стороной длины имеют площадь меньше
Оценка.

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

По неравенству Коши-Буняковского-Шварца оно не превосходит

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