9-11 класс, Универсальные методы (Лахтин А. А.), 16 ноября

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

Сегодня у нас на обсуждении...

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

То есть там хоть Олимпиада за 7 класс, хоть Олимпиада за 11 класс, вообще не без разницы, всегда есть какие-нибудь задачи, которые решаются с помощью этого метода.

А именно это инвариант, ну и полуинвариант.

Давайте поймем, что вообще такое invariant, то есть какая основная идея этого метода.

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

И если вы можете найти какую-то величину, которая будет неизменной, вне зависимости от того, какие вы действия делаете, то это вам достаточно много информации дает.

Вы, например, можете сравнить, вы зачастую знаете, чему эта величина равна изначально, потом смотрите на то, чему эта величина будет равна в конце,

И какой-то вывод этот вы делаете.

Это что-то, если в общих чертах, общими словами говорить, то идея какая-то такая.

Но чтобы получше понять, о чем вообще речь, нужно смотреть какие-то примеры и с ними разбираться.

Давайте судим такую задачу.

У нас изначально есть числа 1, 2, 3, 4, 5, 6.

Что мы можем сделать?

Мы можем к любым двум из них добавлять по единице.

То есть условно взять двойку и четверку.

и прибавить к ним по единице, получить ряд 1, 3, 3, 5, 5, 6.

Вот.

Ну и так далее.

Каждый ход мы выбираем какие-то два числа и увеличиваем их на один.

Вот.

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

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

Понятно, что раз вопрос «можно ли», то нам нужно либо построить пример, то есть предъявить какой-то конкретный порядок действий, который позволяет нам сделать все числа равными,

либо мы хотим доказать каким-то образом, что это сделать невозможно.

Вот.

Ну и на самом деле, если бы вы, допустим, сели и попробовали сначала руками как-то чисто эти прибавлять, то у вас бы не получилось сделать их равными.

Какого-то простого примера не существует.

Просто потому что на самом деле это сделать невозможно.

Обычно в такими наточках, если вы сходу не понимаете, какой ответ, то есть нет какой-то интуиции на этот счет, то полезно посмотреть, просто попробовать что-то поделать.

И, возможно, заметить какую-нибудь закономерность, из-за которой у вас не получается поставить пример.

Или просто попробовать и

Решить, что, наверное, раз долго не получается построить, то примера не существует.

А значит, нужно доказывать то, что это сделать невозможно.

Ну и теперь давайте поймем, как можно понять, почему это сделать невозможно.

Для этого полезно посмотреть на то, что у нас происходит в целом за одну операцию.

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

Ну, давайте посмотрим, что происходит.

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

Вот.

Что тогда можно заметить?

Давайте посмотрим на сумму всех чисел.

Это на самом деле довольно часто бывает полезно сделать, просто потому что это достаточно простая величина, за которой достаточно удобно следить.

Поймем, чему она равна изначально.

Она равна изначально 1 плюс 2 плюс 3 плюс 4 плюс 5 плюс 6.

Это получается 6 на 7 пополам, то есть 21.

Сумма изначально равна была 21, а каждый ход увеличивается на 2.

И это довольно удобно, потому что теперь у нас понятно, что происходит с этой величиной.

То есть до этого у нас была ситуация такая.

Мы не знали, каким числом мы что прибавляем, и из этого какой-то элемент неизвестности у нас присутствовал.

То есть мы никак не могли контролировать то, к каким именно элементам у нас добавляются единицы.

А здесь мы смотрим не на всю задачу, а чисто на сумму.

И тут уже явно понимаем, как эта сумма у нас изменяется.

Ну и давайте поймем, почему это удобно.

Поймем, что мы хотим получить в случае, если все числа равны.

Пусть все числа равны какому-то x.

Тогда чему у нас будет в итоге равна сумма?

Сумма будет равна 6х.

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

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

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

Вот.

То есть в данном случае у нас инвариант

будет четностью, инвариантом будет четность суммы всех чисел.

Как мы поняли, она увеличивается каждый раз на 2, сама сумма.

Значит, четность не меняется.

Изначально у нас сумма была нечетная.

А в конце она должна быть равна 6x, значит, она должна быть четной.

Ну и получаем противоречие.

То есть изначально она нечетная сумма.

Мы знаем, что четность не меняется.

а в конце должна стать сумма четной.

Получаем противоречие, значит, не существует такого набора действий, который нам делает все эти числа равными.

То есть ответ на эту задачу будет цвет нет.

Ну и пару слов о том, как это можно оформлять на олимпиадах.

Почему этот метод еще удобен для оформления.

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

То есть в какой-то момент вы этот вариант нашли.

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

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

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

Вы первое указываете инвариант,

В данном случае четность суммы.

Потом, очень важно, надо доказать, что это действительно инвариант.

В данном случае в качестве доказательства вы пишете, что сумма увеличивается на 2, значит четность суммы не меняется.

Это получается доказательство того, что наша величина найдена и действительно инвариант.

А потом вы, по сути, можете просто примерно то же самое сделать, как я вот тут нарисовал.

То есть смотрите на то, что в начале.

Вот.

И что в конце.

Вот.

И если получилось разное, то противоречие.

И, собственно, это все, что вам нужно написать.

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

Но если вы это уже заметили, то решение получается очень короткое.

Вот.

Ну и это плюс.

Окей.

Я надеюсь, что идея понятна.

Если у вас возникают какие-то вопросы по ходу рассказа, вы задавайте вопросы их либо в чате, либо можете просто микрофон включать и задавать.

Вот.

Но если пока вопросов нет, то давайте пойдем дальше.

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

То есть, возможно, мы еще тут... У нас получится понять, как можно этот вариант искать, то есть какие методы для этого существуют, на что полезно смотреть.

Вот.

В общем, задача такая.

У нас есть куб.

Вот.

И на вершинах написаны какие-то числа.

Изначально у нас в одной вершине написана единица.

Давайте для определенности перемещаем, что вот эта вершина, которая ближняя к нам, в ней написана единица.

А в остальных вершинах написано нули.

И задача такая.

За один ход мы можем прибавлять числа по единице,

к числам в концах любого ребра.

То есть мы берем любое ребро и делаем плюс один здесь, плюс один здесь.

Ну и тут в задаче два вопроса.

Давайте сначала разберемся с первым.

Первый вопрос.

Можно ли сделать так, чтобы все числа стали равными?

Можно заметить, что эта задача на самом деле очень похожа на предыдущую.

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

Изначально у нас есть 8 каких-то чисел.

Одна единица, остальные нули.

И, по сути, заход мы можем добавлять по единице к двум каким-то из этих чисел.

У нас еще есть какие-то дополнительные условия, что эти числа должны стоять в соседних першинах.

Но для первого вопроса нам это на самом деле не важно.

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

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

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

В общем, какие-то такие величины достаточно часто бывают вариантами.

Давайте опять же посмотрим здесь на сумму всех чисел.

Что нам нужно доказать?

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

Но опять, мы понимаем, что заход сумма

увеличивается на плюс 2, потому что к двум вершинам добавляется единица.

Отлично.

То есть, опять же, мы понимаем, что не меняется у нас именно четность суммы.

И в этот момент мы уже можем написать, что четность суммы – это инвариант.

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

А теперь давайте поймем, насколько этот инвариант нам полезен.

Мы посмотрим на сумму изначально и сумму в конце.

Изначально у нас сумма равна 1, а в конце, если мы сделали все числа равными, то сумма стала равна 8х.

Если все числа равны х, просто потому что у нас 8 вершин, значит сумма будет 8х.

Эта штука четная, а вот эта штука нечетная.

Опять же получаем противоречие, потому что мы знаем, что четность – это инвариант, то есть эта величина не меняется.

А у нас она поменялась.

Значит, такого произойти не могло.

То есть мы не можем добиться того, чтобы все числа стали равными.

Окей.

А теперь давайте посмотрим на второй вопрос.

Можно ли добиться того, чтобы все числа делились на 13?

И давайте поймем, почему наш предыдущий вариант, который мы уже нашли, почему он нам тут не поможет.

Потому что изначально сумма была равна единице.

И что мы можем сказать в случае, если все единицы делятся на 13?

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

Но ничего более содержательного мы про нее не знаем.

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

Никаких проблем нет.

Допустим, мы прибавили двойку просто... Сколько?

6 раз получается.

Получили 13.

И вот получили, что сумма в целом может быть кратно 13.

Поэтому никакого противоречия пока что с помощью вот этого инварианта мы получить не можем.

Поэтому хочется понять, какой еще инвариант можно тут поискать.

Но давайте заметим следующее.

Нам зачем-то дали еще условие на то, что...

мы прибавляем плюс один именно к соседним вершинам.

То есть пока что, как вы могли заметить, мы этим условием нигде не пользовались.

А если нам дают какое-то условие, а мы им не пользуемся, наверное, мы делаем что-то не так, и, наверное, в общем, это условие нам дали не просто так.

Ну и, собственно, давайте поймем, как этим условием можно воспользоваться.

Давайте я заново нарисую картинку.

Или вообще лучше я условия задачи еще раз сюда перенесу.

Вы можете пока я рисую картинку, подумать, есть ли у вас какие-то идеи о том, как можно доказать для 13.

Может, у вас есть мысли о том, какой вариант можно использовать.

Если есть идеи, можете предложить, попробуем их обсудить.

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

Окей, ладно.

Кстати, я зачем так сижу?

Извиняюсь.

Да, ну ладно, там вы ответили на вопрос.

В общем, да, нам тут нужно понять, какая величина...

не меняется вне зависимости от того, какие им действия делаем.

Причем, опять же, нам важно помнить о том, что мы добавляем по единице именно к концам ребер.

То есть это условие важно.

И мы, наверное, хотим получить какой-нибудь вариант, который нам...

доказывает, что невозможно сделать так, чтобы все числа делились на 13.

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

Но не суть.

Важно то, что мы хотим найти какой-нибудь вариант,

который в идеале вообще не будет меняться.

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

Давайте заметим следующее.

Допустим, до этого у нас была идея, что мы берем сумму.

Давайте попробуем как-то эту идею чуть-чуть модифицировать.

То есть мы не хотим, наверное, придумывать что-то суперсложное, какой-то суперсложный вариант, потому что непонятно, как это делать.

Давайте попробуем чуть-чуть модифицировать идею с суммой и попробовать не просто все числа в вершинах складывать, а складывать их с коэффициентом плюс один или минус один.

То есть у нас есть, по сути, вот эти вот числа.

Изначально это один, но и куча нулей.

И мы перед каждым из них записываем либо плюс, либо минус.

Вот.

И потом изменяем именно сами числа, вот эти вот, по тому правилу, которое у нас есть.

А вот эти коэффициенты оставляем.

Вот.

Окей, то есть по сути нам нужно все вот эти вершины разбить на две группы.

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

И у нас цель разбить на эти две группы так, чтобы в итоге полученная величина никак не менялась.

Давайте поймем, как мы это можем сделать.

Поймем, что происходит у нас при одной операции.

При операции у нас добавляется плюс 1 в соседние вершины ребра.

Но заметим, что если мы в группу с плюсом добавим плюс 1 и в группу с минусом добавим плюс 1, то в итоге, когда мы с нужными коэффициентами сложим, то есть вот эти с плюсом, а эти с минусом, вот эти плюс-единички сократятся.

То есть они друг друга уничтожат.

А значит, сумма с коэффициентами никак не поменяется.

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

Давайте вот эту вершину мы обозначили за плюс, вот эти все за минус.

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

Получаем, что вот тут плюсики.

Раз эта вершина с минусом, мы хотим вот эту вершину брать с плюсом.

И как бы она стала только вот эта вершина, у нее все соседи плюсы, значит она будет с минусом.

Вот.

Ну и по сути, вот у нас вот эти вершины оказались плюсом, остальные вершины оказались с минусом.

И получается числа на вот этих отмеченных вершинах мы берем с плюсом в нашу сумму, все остальные числа мы берем с минусом в нашу сумму.

И понимаем, что полученная величина является инвариантом, потому что при добавлении...

плюс 1, плюс 1 на ребре, у нас плюс 1 добавляется в положительную часть, и плюс 1 вычитается еще за счет этой писательной части.

То есть, как бы это получше написать, сумма чисел на отмеченных

минус сумма чисел на неотмеченных.

Это инвариант.

Отлично.

Теперь, опять же, мы нашли какой-то инвариант.

Но мы пока не очень понимаем, насколько он нам поможет в этой задаче.

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

Потому что прошлый вариант, который сумма просто, нам с этим вопросом не помог.

Давайте поймем, что тут происходит.

Изначально у нас сумма была равна...

Окей, давайте еще раз поймем, почему это инвариант.

То есть про плюс 1 и минус 1.

Смотрите, у нас есть два типа чисел.

Те, которые на отмеченных вершинах, вот на вот этих, которые мы плюсиком обозначили, и те, которые на неотмеченных.

Вот это вот множество.

Заметим, что если мы рассмотрим любое ребро,

в этом кубике, то один из концов будет отмечен, другой нет.

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

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

У нас вот здесь добавляется плюс 1, и вот к этому множеству тоже добавляется плюс 1.

Но за счет того, что тут нарисован минус, у нас получается вот такая вот штука, что здесь мы добавили плюс 1, тут мы добавили плюс 1, и когда раскроем скобки, то вот эти единички сократятся.

И получим, что вот эта сумма, сумма одних чисел минус сумма других чисел, она при каждой операции вообще никак не меняется.

Понятно?

Супер.

Отлично.

То есть мы нашли инвариант.

И теперь давайте посмотрим, что происходит на нашей картинке.

Нам осталось попробовать его применить.

Для этого смотрим на то, что было изначально.

Изначально у нас сумма с плюсом была равна 1.

потому что единственное ненулевое число у нас в этом множестве.

То есть получили 1 минус 0.

А в конце, если все числа делятся на 13, то у нас вот это значение тоже должно делиться на 13.

Можно вот так это писать.

Мы явно не знаем, чему эта сумма должна быть равна, но мы точно знаем, что если бы условие выполнялось, то она делилась бы на 13.

Но мы понимаем, что это значение, оно инвариант.

То есть оно вообще никак не меняется.

Значит, в конце оно тоже должно быть равно единице.

Ну а единица на 13 не делится, значит, мы получили противоречие.

Ну а значит, добиться того, чтобы все числа делились на 13, невозможно.

Вот.

Какая-то такая мысль.

В целом, еще что могу сказать.

В некоторых задачах, по сути, что мы тут сделали?

По сути, мы сказали, вот у нас есть какие-то числа, и мы с какими-то коэффициентами их поскладывали.

То есть вот эти числа, которые отмечены, мы сложили с коэффициентом плюс один, а вот эти числа, которые не отмечены, мы сложили с коэффициентом минус один.

Вот.

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

А как раз условия на эти коэффициенты, чтобы это был инвариант, мы берем из того, что...

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

Вот.

Это такая какая-то более общая идея, подобные задачи решать.

Вот.

Но такое встречается уже в достаточно сложных задачах.

Вот.

А...

Зачастую достаточно либо суммы, либо разности, либо какой-то знакопеременной суммы.

Теперь давайте поймем, что такое полуинвариант.

У нас сегодня тема «Инвариант и полуинвариант».

И, по сути, полуинвариант – это что-то очень похожее.

То есть на самом деле полуинвариант иногда можно сформулировать таким образом, чтобы это было инвариантом.

Но давайте поймем вообще, какое у этого определение.

Полуинвариант – это какая-то величина, которая меняется, но меняется всегда по каким-то определенным правилам.

То есть, например, если она все время увеличивается, то это полуинвариант.

То есть общего универсального определения, наверное, нет.

За исключением того, что я сказал, что это величина, которая меняется по каким-то фиксированным правилам.

И вот это как раз этими правилами...

За счет этих правил мы какие-то выводы о задаче можем делать.

То есть какие самые распространенные варианты.

Либо эта величина всегда увеличивается, либо там не уменьшается.

Либо эта величина всегда уменьшается, наоборот, или не увеличивается.

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

То есть если у нас есть какие-то два типа, в данном случае, например, четные и нечетные,

Если у нас величина каждый раз меняет тип, то это полуинвариант.

Вот такие дела.

В целом, как я уже сказал, это можно формулировать и в терминах инварианта.

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

Инвериантом условно является знак разности между соседями.

Как-то так можно сформулировать.

То есть понятно, что у нас есть что-то, что всегда постоянное.

В данном случае постоянность заключается в том, что величина всегда увеличивается.

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

Так, вот такая вот задача.

Что тут у нас происходит?

У нас есть шахматная доска стандартная, то есть это поле 8х8.

Ну и, соответственно, клетки А1 и H8 – это клетки, которые противоположные угловые.

Вот.

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

Вот.

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

Вот.

Как такое можно решать?

Ну, в первую очередь, как бы...

хочется попробовать найти как раз этот полуинвариант.

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

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

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

Давайте посмотрим на ход коня в таком случае.

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

Получается вот такая вот картинка.

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

В белую.

Ну и если бы это была клетка белой, то было бы наоборот.

Ну просто у нас бы сейчас тут все цвета поменялись на этой картинке.

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

Вот.

И именно вот это вот свойство для нас будет являться полуинвариантом.

То есть, ну скорее полуинвариант это цвет клетки, в которой находится конь.

А правило, по которому эта величина меняется, вот такое, что за один ход из черной он попадает в белую, из белой он попадает в черную.

Ну и теперь давайте поймем, может ли это нам помочь в данной задаче.

Ну, опять же, смотрим на то, что было изначально.

Изначально была черная клетка.

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

То есть в конце тоже у нас черная клетка.

Вот.

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

То есть мы начали с черной клетки, потом была белая, потом черная, потом белая, потом черная и так далее.

И закончили мы все на черной клетке.

Что мы тогда можем сказать про эту последовательность?

Заметим, что у нас цвета каждый раз чередуются.

То есть каждый новый цвет отличается от предыдущего.

А значит, так как у нас начальный цвет совпадает с конечным цветом, то количество элементов, то есть количество клеток в этой последовательности будет нечетным.

Это можно, например, себе просто так понять.

Объединим вот так вот на пары.

То есть черная-белая, потом еще раз черная-белая, потом еще раз черная-белая.

И тогда в каждой паре последняя будет белой, и останется еще одна черная.

Значит, суммарно нечетное количество клеток в этой последовательности.

Но мы знаем, что конь должен был обойти все клетки доски по одному разу.

То есть всего в этой последовательности должно было быть...

четное количество, а именно 64 клетки, а это четное количество.

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

А значит...

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

А значит, получаем, что конь не мог посетить все клетки доски по одному разу, начав в этой клетке, закончив вот в этой клетке.

Вот.

И дела.

Если есть вопросы, задавайте.

Но я думаю, что мысль была понятна.

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

Вот.

Теперь давайте...

Разберем еще одну задачу.

Опять же, задача будет на полный вариант.

И поймем, как ее можно решать.

Значит такая.

У нас изначально есть 200 курток.

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

Вот.

И спрашивается, может ли в итоге остаться 100 курток.

Ну, окей.

То есть в целом задача довольно простая в плане формулировки.

То есть у нас изначально, если математическую модель строить, у нас просто есть число 200.

Каждым шагом мы можем либо плюс, либо минус 1 сделать.

И спрашивается, можно ли мы последовательностью из 2025 шагов получить число в 100.

В сути формулировка примерно такая.

Что тут может быть в качестве полуинвариата?

В целом можно просто взять и сказать, что вот количество курток,

Это полный вариант, потому что оно меняется по каким-то достаточно простым правилам.

Но это не супер информативно, потому что мы задачу никак не облегчили.

Мы просто пересказали то же самое условие, только на язык полный вариант.

Вместо этого давайте попробуем вспомнить то,

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

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

Ну и тут на самом деле как раз написано, что зачастую меняется при подобном полуинвариате.

Получается, хочется посмотреть как-то на четность количества курток.

Ну, во-первых, поймем, почему это действительно полуинвариант, то есть почему, вернее, это удобный для нас полуинвариант.

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

И наоборот, если оно было нечетным, оно в любом случае стало четным.

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

То есть сказать, что если было так, то точно будет вот таким вот образом.

То есть если было четное, то точно в любом случае будет в итоге нечетное после одного действия.

Ну и наоборот, если было нечетное, то будет четное.

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

Вот смотрите.

У нас изначально четность количества курток была четной, то есть количество курток было четным в конце.

мы хотим тоже, чтобы это количество было четным.

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

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

Соответственно, будет нечетным.

Ой, да, нечетное количество чисел.

Ну, или там значений.

Вот.

А теперь давайте посмотрим, сколько значений у нас.

Изначально у нас было значение 200.

Потом мы добавили еще 2025 штук.

Следующая, которая будет нечетная, это после первой операции, потом еще одна после второй операции и так далее.

Финальная будет после 2025 операции.

Всего у нас 2026 значений.

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

А у нас в реальности по условию задачи количество значений в этой последовательности четное.

Ну а значит, раз мы получили противоречие,

Получаем, что такого количества курток в итоге после 2025 операций остаться не может.

Да, ну как бы на любой ход... Ну да, спрашивают, почему 2026 этих значений.

Но вот тут я нарисовал, почему это так.

То есть вот тут, когда мы писали четное, это как раз вот это вот четное число, то есть это 200, которое было, по сути, еще до того, как мы начали делать эти ходы.

Вот.

То есть как бы раз я здесь считал, включая это и это, то есть тут я считал не количество...

то есть не количество стрелочек, а количество значений.

Тогда и здесь я тоже должен считать количество значений.

То есть начиная с 200, потом опять какое-то несчетное число идет и так далее, а потом значения после 2025 хода.

Да.

Ну и получаем, что в такой последовательности 2026 значений, потому что одно здесь и еще вот эти вот 2025 пронумерованных.

Понятно?

Хорошо.

То есть в целом тут, по сути, опять же, пример инварианта, когда у нас есть какие-то типы объектов, и они меняются.

Пример полуинварианта.

И за счет того, что каждый раз эти типы меняются,

мы можем, зная начало и конец, что-то про четкость количества изменений сказать.

Если оно не совпадает с условием, то получается мы побеждаем.

Окей, хорошо.

Ну и давайте еще одну задачу обсудим.

Она будет чуть сложнее.

Но зато там будет еще одна идея полезная показана.

Вот.

Ну, что тут происходит?

У нас есть

Квадратная доска.

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

И в какой-то там клетке у нас стоит фишка.

Что может делать фишка?

Она в каждом ходу может либо двинуться вверх,

либо сдвинуться вправо, либо по диагонали вниз.

И спрашивается, может ли эта фишка обойти всю доску, побывав на каждом поле ровно по одному разу.

А, и при этом, начальная клетка, если вот эта, то финальная должна быть соседняя справа, то есть вот эта вот.

Ну и спрашивается, может ли быть такое.

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

И опять же известна начальная и финальная точка.

Соответственно, тоже хочется попробовать найти какой-то полный вариант.

Но здесь...

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

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

Соответственно, мы понимаем, что, наверное, хочется какой-то более хитрый вариант искать.

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

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

Что я имею в виду?

Давайте скажем, что у нас фишка находится в точке с координатами x, y. Например, пронумеруем все строки, все столбцы от одного до n и все строки от одного до n.

Например, таким образом.

Будто мы задали систему координат.

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

То есть вот этот вариант.

Если фишка сходит вверх, то она переместится в точку x, y плюс 1.

И если фишка сходит по диагонали вниз-влево, то, соответственно, у нее обе координаты уменьшатся на единичку, и получим, что она ходит на x минус 1, y минус 1.

И теперь опять у нас получается какая-то ситуация, как, например, в прошлый раз.

что если смотреть чисто на такую величину, то она может изменяться тремя разными способами.

А нам это не нравится.

Нам не нравится то, что мы никак не контролируем то, каким способом именно она изменяется.

У нас есть вот эта неопределенность, и очень хочется от нее избавиться.

Мы хотим найти какой-то полный вариант,

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

Ну как придумать такую величину?

Давайте сначала посмотрим на вот эти две стрелки и попробуем как-то объединить их.

Но что тут можно заметить?

Можно заметить, что в одном случае у нас х увеличилось на единицу, в другом случае у нас у увеличилось на единицу.

То есть и тогда, и тогда у нас какая-то из величин увеличилась на единицу.

Как это можно объединить?

Можно просто вместо величины х и величины у смотреть на сумму.

То есть вместо такой штуки давайте посмотрим на то, как меняется сумма х плюс у.

И мы получили, что уже вот в этих двух случаях, когда мы ходим направо и наверх, у нас сумма x и y увеличивается на 1.

То есть меняется каким-то одним определенным образом.

Но в этом случае у нас все еще проблема, потому что в таком случае сумма x и y уменьшается на 2.

Но теперь у нас количество вариантов, с чем вообще происходит, уменьшилось.

Сейчас у нас всего лишь два варианта, как меняется вот эта вот величина, которую мы нашли.

Давайте поймем, можем ли мы опять же вот эти две стрелки как-то объединить.

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

что может быть у этих двух величин общего.

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

То есть мы x плюс y плюс 1, и с x плюс y плюс 1 вычтем x плюс y минус 2.

Получим тройку, потому что вот эти части сократились, а из единицы мы вычитаем минус двойку, получаем тройку.

Отлично, то есть мы поняли, что вот эти вот величины отличаются на 3, то есть на какую-то константу, и это нам достаточно удобно.

Потому что это на самом деле значит, что остатки по модулю 3, ну то есть остатки ее определения на 3, у нас одинаковые.

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

Это будет остаток.

При, давайте, остаток суммы.

x плюс y 3 деление на 3.

Ну и поймем, как он изменяется.

Это легко понять вот по вот этой стрелке.

То есть, если у нас был остаток 0, то он у нас перешел в остаток 1.

Если у нас был остаток 1, то он перешел в остаток 2.

Если у нас был остаток 2, то он, соответственно, перешел в остаток 0.

Вот.

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

То есть до этого у нас было то, что четные переходы в нечетные, а нечетные в четные, и было такое правило.

А сейчас у нас опять же однозначное правило изменения в каждый момент времени.

Но вот уже участвуют три типа объектов, то есть остаток по модулю 3 равный 0, равный 1 и равный 2.

И мы каждый раз знаем, как он меняется за одну действие.

И вот этим мы уже теперь можем попробовать воспользоваться.

Опять же, когда мы как-то пообъединяли вот эти вот стрелочки и нашли полуинвариант, еще никто нам не гарантирует, что этот инвариант нам поможет.

Но раз мы что-то хорошее сделали, давайте проверим, насколько это вообще все было полезно.

Давайте скажем, что если изначально у нас была сумма x плюс y, допустим, была координата x и y, то в конце что происходит?

У нас должна быть координата какая?

x плюс 1, запятая y. Потому что это предка справа от начальника.

Соответственно, у нее предназначение будет вот такое.

Если что, у меня x по горизонтали, y по вертикали.

Но я думаю, это было понятно.

Достаточно стандартно.

Тогда что с суммой происходит?

Сумма...

у нас стало x плюс y плюс 1.

То есть, по сути, остатки определения на 3 у этой суммы, вот в таком цикле, он следующий по сравнению с вот этим остатком.

Если здесь был остаток 0, то тут должен быть остаток 1.

Если здесь 1, то тут 2, если тут 2, то тут 0.

Ну, понятно.

И...

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

По сути, давайте поймем, что значит, что у нас вот эти вот штуки, вернее, что вот эти вот остатки отличаются на единицу в таком цикле.

Вот пусть у нас был остаток

Допустим, 0.

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

Потом поймем, как это обобщать.

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

Потом опять единичка, опять двойка, опять 0.

И так далее.

И в конце он должен стать единичкой.

Так?

И что мы в таком случае можем понять?

Можем заметить, что у нас все разбивается на такие вот куски.

То есть 0, 1, 2, потом опять 0, 1, 2 и так далее.

И в конце у нас что происходит?

Давайте я дорисую.

У нас была последняя такая тройка 0, 1, 2, и раз мы закончили 1,

то у нас был еще один нолик и еще была одна единичка.

То есть что мы можем из этого сразу сказать про количество элементов такой последовательности?

По аналогии с тем, что мы говорили до этого про четность,

Тут мы то же самое можем сказать про количество по модулю 3.

То есть мы знаем, что вот тут есть группы по 3 штуки.

Если тут k групп, то будет количество элементов равно 3k плюс то, что в группы не вошло, то есть плюс 2.

То есть мы поняли, что количество элементов

по модулю 3 равно 2.

То есть имея на статус 2 определение на 3.

Отлично.

То есть какую-то информацию мы из нашего полуинварианта получили.

И давайте поймем, насколько нам эта информация полезна.

Но опять же, как в прошлой задаче, в задаче про коня, количество элементов

должно быть равно просто количеству клеток в этой таблице.

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

Значит, в этой последовательности каждая клетка встречается ровно один раз.

А значит, вот это количество элементов в действительности должно быть равно n квадрат.

То есть мы получаем такое условие, что n квадрат должно быть равно, давайте пока так напишу, равно 3k плюс 2 для какого-то k. Ну и утверждается, что такого быть не может.

Почему?

Ну вообще, почему такого быть не может?

Давайте посмотрим на остатки по модулю n.

3 для n2.

Для этого, ну, как такое можно рассматривать?

Ну, просто смотрим на то, какой остаток имеет n и на то, какой остаток имеет n2 в таком случае.

То есть, если n делится на 3, то есть, если остаток 0, то n2, очевидно, тоже делится на 3, то есть, тут остаток тоже 0.

Вот.

Если n квадрат сравнимо с 1 по модулю 3, то есть если остаток по модулю 3 для n равен 1, то как это можно записать?

Значит, n равно 3a плюс 1, а значит n в квадрате, это что такое?

3a плюс 1 в квадрате это 9a квадрат плюс 6a плюс 1.

То есть эта штука делится на 3, потому что каждый слагаемый делится на 3.

А значит, остаток определения на 3 у n квадрат будет равен 1.

И если у нас остаток у n твойка, то, соответственно, мы смотрим на 3a плюс 2 в квадрате.

Получаем это 9a квадрат плюс 6a плюс 4.

Только не 6a.

Что там?

12a плюс 4.

Получаем, что вот эти штуки делятся на 3.

Значит, остаток будет равен тоже единице.

Потому что 4 это 3 плюс 1.

И, собственно, мы получили, что в любом случае остатка 2 получиться не могло.

А он как бы у нас получился.

Но это плохо.

Получение противоречия.

Значит, мы не могли обойти всю доску так,

чтобы начать здесь, а закончить в соседних веках.

В целом, как это решение можно оформить чуть лучше?

Если вы знакомы с таким обозначением, вот таким или вот таким.

Обозначение читается так.

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

Можно просто говорить, что сумма увеличивается на единицу по модулю 3.

Ну и дальше тут аналогичное рассуждение провести.

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

А n квадрат...

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

И вот этот факт на самом деле полезно просто знать.

То есть он достаточно часто где-то может возникать.

Значит, что n квадрат не может давать остаток 2 при делении на 3.

Получаем вот этот полный вариант.

Вот это правило, по которому он меняется.

Вернее, вот это правило, по которому он меняется.

Из него мы получили условия на количество элементов.

И вот нашли противоречие.

Кстати говоря, я тут вспомнил, что я не показал, как это в общем виде записать.

То есть почему... Ну, как бы я составляю, начинаем, это понятно.

А почему в общем виде это верно?

Вот.

Но давайте поймем, почему это так.

Заметим, что, по сути, у нас есть такой вот цикл.

0, 1 и 2.

И мы ходим по такому циклу по числу стрелки, например.

Тогда посмотрим на то, как у нас эти остатки меняются.

Изначально пусть остаток был А.

потом встал B, потом встал C. Потому что, когда мы по циклу ходим, у нас каждый раз остаток меняется.

И, в общем, после трех ходов, вернее, после двух ходов, у нас как раз будут записаны три различных остатка.

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

потому что цикл длинный 3.

Потом опять идет B, потом опять идет C и так далее.

И мы знаем, что вот в конце, посмотрим последнюю такую тройку, которую мы нашли, ABC.

Дальше после C мы точно знаем, что идет A. А по условию у нас, если была сумма x плюс y, то стала сумма x плюс y плюс 1.

То есть остаток является следующим элементом в этом цикле.

А следующий элемент после а – это b. То есть мы понимаем, что сумма заканчивается именно таким вот образом.

Вернее, не сумма, а последовательность.

Ну и тут опять то же самое дело.

То есть тут вот блок из трех штук, вот блок из трех штук и так далее.

Это у нас последний блок из трех остатков разных.

И остается еще два остатка, которые в эти тройки не вошли.

Значит, суммарно элементов этой последовательности записано 3n плюс 2.

Вернее, 3k плюс 2, n у нас уже занято.

Вот это рассуждение я в общем виде провел.

Но я думаю, это и так было достаточно интуитивно понятно, почему нам не важно, с какой точки мы начинаем.

Вот.

Такая задача.

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

каждое следующее действие однозначно определено.

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

Основная идея полуинтерната именно такая.

Есть ли какие-то вопросы...

Или по этой задаче в первую очередь, или в целом по тому, что такое инвариант или полуинвариант.

Просто на этом примеры у меня закончились.

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

А если вопросов нет...

то, наверное, можно на этом заканчивать.

Если все уловили суть того, о чем я говорил.

Окей.

Видимо... А, где можно подробнее прочитать про это?

Ну, во-первых, почитать можно, ну, не знаю, просто загуглить, как минимум, можно, то есть и вариант, и полный вариант можно загуглить, там будет и определение вам дадут,

И какие-нибудь задачи, скорее всего, где-нибудь будут потренироваться.

Но задачи у вас и здесь будут порешать.

В будущем можно будет проверить себя с ответом, сравниться.

А в целом, если что-то не очень понятно, давайте я просто сейчас лучше поясню поподробнее, если есть какие-то вопросы.

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

Вернуться к тому, когда мы говорили, что остатки по модуле 3 одинаковы.

Про остатки по модуле 3 мы начали говорить вот в этом моменте.

Но вот смотрите, что у нас тут происходит.

Мы вот отсюда получили какую-то величину, ну а именно сумму, для которой у нас уже всего два варианта того, как она меняется.

То есть она либо увеличивается на единицу, либо уменьшается на двойку.

Давайте посмотрим на разность вот этих двух значений.

Разность мы получили, что она равна 3.

То есть если x плюс y плюс 1 имеет остаток, то есть равен 3k плюс r, где r это остаток по модулю 3, то что такое x плюс y минус 2?

Он равен вот этому значению.

Минус 3, потому что разность это 3.

То есть это равно 3k плюс r минус 3, но это мы можем переписать вот в таком виде.

3 на k минус 1 плюс r. То есть, опять же, если мы делим с остатком, то мы получаем вот это неполное частное и опять же тот же самый остаток r, который мы получили здесь.

То есть мы поняли, что если мы вот эту часть отбросим и будем смотреть чисто на остаток, то в любом случае из суммы x плюс y мы получим, которая была равна в свою очередь 3k плюс r минус 1.

И имела остаток либо r минус 1, либо если r равно 0, то оно соответственно имело остаток 2.

то отсюда мы точно получаем в любом случае остаток r. Ну и описывается это в общем случае так.

Если у нас был остаток 0, то он увеличится на 1.

То есть если r-1 было равно 0, то r будет равно 1.

Если у нас был остаток 1, то после действия,

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

А если тут была двойка, то что это значит?

То есть x плюс y равно 3k плюс 2, тогда x плюс y плюс 1 равно 3k плюс 3, то есть делится на 3.

Значит остаток 0.

И мы получили вот такую стрелку.

Если у суммы был остаток по модулю 3 равный двойке,

то после действия, которое мы совершили, в любом случае у нас получится остаток 0.

Понятно?

Супер.

С предыдущей задачей тоже все понятно было.

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

Всем спасибо за внимание.