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

Дискретная непрерывность

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

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

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

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

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

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

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

Задача 1#90369

Есть несколько кусков сыра разного веса и разной цены за кг. Докажите, что можно, разрезав не более двух кусков, разложить куски на $2$ кучки равные по весу и по цене.

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Действительно, прокрутив диаметр по часовой стрелке на 180°, с помощью непрерывности можно доказать, что один из диаметров делит сыр на кучи с равными стоимостями.

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

Рассмотрим произвольную окружность, разобьём её на дуги, пропорциональные весам кусков сыра. Тогда любой проведённый диаметр соответствует разрезанию не более чем двух кусков сыра (концы диаметра пересекают дуги в местах разреза), что кучки из кусков по обе стороны диаметра имеют равные массы. Осталось доказать, что один из таких диаметров даст также факт, что кучки по обе его стороны имеют одинаковую стоимость. Зафиксируем диаметр и прокрутим его по часовой стрелке на $∘ 180,$ заметим что разность стоимостей куч сыра слева и справа от диаметра непрерывно изменялась и стала противоположной, значит, в некоторый момент она принимала значение $0,$ что и требовалось.

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

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

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

Задача 2#68180

Есть 8 белых кубиков одинакового размера. Марине нужно покрасить $24$ грани кубиков в синий цвет, а остальные $24$ грани — в красный. После этого Катя склеивает из них куб $2× 2× 2.$ Если на поверхности куба столько же синих квадратиков, сколько и красных, то Катя побеждает. Если нет, то побеждает Марина. Сможет ли Марина покрасить кубики так, чтобы Катя не смогла достичь цели?

Источники: ФЕ-2023, 11.2 (см. www.formulo.org)

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

Подсказка 1

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

Подсказка 2

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

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

Пусть Марина как-то покрасила кубики, а Катя как-то сложила из них куб. Пусть на поверхности куба $a$ синих и $24− a$ красных граней. Используя идею так называемой дискретной непрерывности, покажем, что Катя может постепенно привести куб к нужному ей виду. Заметим, что каждый из 8 кубиков можно повернуть так, чтобы все его грани, которые были снаружи, оказались внутри, и наоборот. Если сделать это со всеми восемью кубиками, то на поверхности окажутся как раз все те грани, которые изначально были внутри, то есть $24− a$ синих и $a$ красных. Заметим теперь, что каждый кубик можно поворачивать постепенно - так, чтобы за один ход две внешних грани оставались на месте и лишь третья заменялась на противоположную. При таком повороте количество синих граней на поверхности меняется не более, чем на $1.$ Итак, изначально синих квадратов было $a,$ в конце стало $24− a,$ а при каждом действии менялось не более, чем на $1.$ Поскольку число $12$ находится между $a$ и $24− a,$ то в какой-то момент их было ровно $12.$

Ответ: нет

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

Задача 3#74600

Датчик случайных чисел за одно действие уменьшает или увеличивает на 1 коэффициент перед $x$ или свободный член в квадратном трёхчлене. После некоторого числа таких операций он преобразовал трёхчлен $2 x − 20x+22$ в трехчлен $2 x − 202x +2$ . Верно ли, что среди полученных в процессе квадратных трёхчленов есть такой, у которого целые корни? Ответ обоснуйте.

Источники: Звезда - 2022 (см. zv.susu.ru)

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

Подсказка 1

Следить сразу за двумя целыми корнями как-то сложновато. Давайте для начала попробуем доказать, что в какой-то момент будет один целый корень. Может возьмем какой-нибудь конкретный?

Подсказка 2

А чего мелочится, давайте посмотрим на 1! Если у нашего трехчлена есть корень 1, то сумма его коэффициентов равна 0. Как меняется сумма наших коэффициентов после одной операции?

Подсказка 3

Верно, она меняется на 1! Изначально сумма была 3, а в конце -199. Значит в какой-то момент она станет равной 0. Итак, в какой-то момент у нашего трехчлена будет корень 1. Докажите, что тогда у него есть второй целый корень (возможно кратный)!

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

Давайте попробуем доказать, что в какой-то момент у квадратного трёхчлена будут целые корни. Для этого угадаем один из них. Если сумма коэффициентов многочлена равна 0, то есть корень $x =1.$ У начального многочлена $2 f1(x)= x − 20x+ 22$ сумма коэффициентов равна 3, а у конечного $2 f2(x)=x − 202x +2$ сумма коэффициентов равна -199, при этом за одно действие ровно один из коэффициентов меняется на 1, значит, сумма коэффициентов меняется на 1. Но если она была положительной, а потом стала отрицательной, то в какой-то момент обязательно была равна 0. То есть в какой-то момент у нас был трёхчлен $2 f(x)= x +bx+ c$ , один из корней которого равен 1! А по теореме Виета второй корень равен $c$ — тоже целому числу $=⇒$ у трёхчлена 2 целых корня!