Инварианты и операции
Немного теории
В задачах, где требуется выяснить, можно ли с помощью заданных операций перейти от одного из объектов к другому, часто полезно найти «инвариант» – числовую характеристику объектов (или функцию с какими-то другими значениями на множестве объектов), которая не меняется при указанных операциях. Если при этом значение инварианта на двух объектах различно, то превратить один в другой нельзя. В целочисленных и других «дискретных» задачах инвариантом часто служит остаток от деления на 2 (четность) или на другое натуральное число.
Если все выполняемые операции обратимы, то все множество объектов, над которыми они выполняются, разбивается на классы эквивалентности (два объекта эквивалентны, если один из них может быть получен из другого заданными операциями).
В задачах, где требуется оценить количество операций или доказать, что их нельзя проделывать бесконечное числе раз (скажем, убедиться в отсутствии «цикла»), иногда бывает полезно придумать функцию, которая при каждой операции возрастает или при каждой операции убывает.
Задачи с решениями
1. Дано три числа:
Разрешается любые два из них заменить двумя следующими: суммой, делённой на квадратный корень числа 2, и разностью, делённой на квадратный корень числа 2. Возможно ли, выполнив эту процедуру несколько раз, получить тройку чисел:
Заметим, что
то есть при выполнении процедуры по замене двух чисел двумя другими, описанной в условии задачи, сумма квадратов заменяемой пары, а значит и всей тройки чисел, остаётся постоянной. Найдём начальную и предполагаемую конечную суммы квадратов троек чисел:
Это позволяет дать отрицательный ответ на вопрос, поставленный в условии задачи.
Ответ: не возможно.
2. На доске написано несколько нулей, единиц и двоек. Разрешается стереть две неравные цифры и вписать цифру, отличную от стёртых (вместо 0 и 1 – цифру 2, вместо 1 и 2 – цифру 0, вместо 0 и 2 – цифру 1). Докажите, что если в результате таких операций на доске останется одно число, то оно не зависит от порядка, в котором производились стирания.
Пусть p – число нулей, q – число единиц, r – число двоек. После каждой операции все три числа p, q, r изменяются на 1, тем самым меняют чётность. Когда на доске остаётся одна цифра, одно из чисел p, q, r становится равным 1, два другие – 0. Следовательно, вначале чётность одного из этих чисел была отлична от чётности двух других. Соответствующая цифра и остаётся на доске.
3. Можно ли все натуральные числа от 1 до 30 записать в таблицу, имеющую 5 строк и 6 столбцов, так, чтобы:
а) суммы чисел в каждом столбце были одинаковы;
б) суммы чисел в каждой строке были одинаковы?
а) Сумма всех чисел от 1 до 30 равна 465. Она не делится на 6, и поэтому числа от 1 до 30 нельзя разместить в 6 столбцов так, чтобы суммы чисел в каждом столбце была одна и та же.
б) Числа 1 до 30 можно разбить на 15 пар: 1 и 30, 2 и 29, … , 14 и 17, 15 и 16. Сумма чисел в каждой паре равна 31. Если в каждую строку записать любые три из указанных пар, то сумма чисел в строке будет равна 93, а таблица, строки которой заполнены тройками таких пар, будет обладать требуемым свойством: суммы чисел в каждой строке будет одна и та же.
4. На каждом из 44 деревьев, растущих по кругу, сидит один воробей. Время от времени какие-то два воробья перелетают на соседнее дерево – один по часовой стрелке, другой – против. Могут ли воробьи собраться на одном дереве?
Пронумеруем деревья по кругу с 1-го по 44-е. Будем считать дальше сумму номеров деревьев, на которых сидят воробьи. С самого начала эта сумма равна 990. При перелёте воробьёв эта сумма либо не меняется (ни один из воробьёв не пересёк границу между 1-м деревом и 44-м или воробьи, сидящие на 1-м и 44-м деревьях, поменялись местами), либо меняется на 44 (только один из воробьёв пересёк границу между 1-м и 44-м деревьями). Таким образом, остаток от деления суммы номеров деревьев, на которых сидят воробьи, на 44 не изменяется и равен 22, остатку от деления 990 на 44.
Если предположить, что все 44 воробья соберутся на одном дереве, то рассматриваемая нами сумма будет равна 44·k, где k – одно из чисел от 1 до 44. Остаток же от деления 44·k на 44 равен 0, чего быть не должно.
Итак, воробьи не могут собраться на одном дереве.
5. В каждой клетке квадратной таблицы 25 на 25 написано число +1 или –1. Обозначим через ai произведение всех чисел i-й строки, через bj – произведение всех чисел j-го столбца. Показать, что сумма
a1 + b1 + a2 + b2 + … + a25 + b25
не равна 0.
Заметим, что a1 · a2 · … · a25= b1 · b2 · … · b25, так как каждое из этих произведений равно произведению всех чисел таблицы.
Предположим, что
a1 + b1 + a2 + b2 + … + a25 + b25 = 0,
тогда среди слагаемых было бы 25 положительных чисел равных +1 и 25 отрицательных чисел равных –1. Поэтому, если имеется n отрицательных чисел среди ai, то среди bj отрицательных будет 25–n. Числа n и 25–n разной чётности, поэтому одно из произведений a1 · a2 · … · a25 или b1 · b2 · … · b25 положительно, а другое отрицательно, что противоречит ранее доказанному их равенству.
Предположение ложно, рассматриваемая сумма не равна 0.
6. В одной клетке квадратной таблицы со стороной 8 стоит знак минус, а в остальных стоят плюсы. Разрешается за один ход в некотором квадрате со стороной 2 изменять знаки на противоположные. Доказать, что с помощью таких ходов нельзя получить таблицу с одними плюсами.
При замене знаков в квадрате со стороной 2 на противоположные количество минусов может измениться только на 2 или 4. Следовательно, во всей таблице число, выражающее количество минусов, остаётся всегда нечётным, а потому не может стать равным 0, что и требовалось доказать.
7. Квадратное поле поделено на 100 одинаковых квадратных участка, 9 из которых заросли травой. Известно, что трава за год распространяется на те и только те участки, у которых не меньше двух соседних участков (то есть таких, которые имеют общую сторону) уже заросли травой. Докажите, что поле никогда не зарастет травой полностью.
Нетрудно проверить, что длина границы участка, заросшего травой (или сумма длин границ нескольких участков) не возрастает. В начальный момент она не превышает 9·4=36, поэтому через любой промежуток времени не станет равной периметру всего поля, равному 40.
8. В вершине А1 правильного 12-угольника А1А2 … А12 стоит знак минус, а в остальных – плюсы. Разрешается одновременно менять знак на противоположный в любых k последовательных вершинах многоугольника. Докажите, что за несколько таких операций нельзя добиться того, чтобы в вершине А2 оказался знак минус, а в остальных вершинах – плюсы, если
а) k = 6;
б) k = 4;
в) k = 3.
а) Разрешается менять знаки в 6 последовательных вершинах. Разобьём все 12 вершин на 6 пар противоположных вершин: А1А7, А2А8, А3А9, … , А6А12. При каждой операции в каждой паре меняет знак только одна вершина. Поэтому в парах А2А8, А3А9, … , А6А12 после нечётного количества операций будут разные знаки, а после чётного – одинаковые. Значит, не может случится так, что в паре А2А8 знаки будут разные (в частности, А2 с минусом, А8 с плюсом), а в паре А3А9, например, – одинаковые (плюсы).
б) Разрешается менять знаки в 4 последовательных вершинах. Рассмотрим разбиение на 4 группы по три вершины: А1А5А9, А2А6А10, А3А7А11, А4А8А12 и будем рассуждать так же, как выше. Четность числа минусов в каждой группе меняется при каждой операции, и у групп А2А6А10, А3А7А11 она одинаковая.
в) Разрешается менять знаки в 3 последовательных вершинах. Следует применить аналогичные рассуждения для разбиения на 3 группы: А1А4А7А10, А2А5А8А11, А3А6А9А12.
9. Домино состоит из двух квадратов. Назовём «тримино» фигуру, состоящую из трёх квадратов, расположенных друг за другом в одну линию. Стандартная шахматная доска из 64 полей покрыта двадцатью одним тримино, так, что, каждое тримино покрывает три поля. Одно поле остаётся свободным. Какое это может быть поле?
Занумеруем двумя способами клетки шахматной доски числами 1, 2, 3, как показано на рисунках ниже. Нумерацию ведём по горизонталям начиная с верхней. Первый раз начинаем с верхней левой клетки и движемся слева направо, второй раз наоборот – от правой верхней клетки движемся справа налево.
Заметим, что каждое тримино обязательно покрывает поля, занумерованные разными числами. Заметим так же, что при обоих способах нумерации на доске написано 22 единицы, 21 двойка и 21 тройка. Поэтому свободным может остаться лишь поле, на котором в обоих случаях стоит единица. Таких полей ровно четыре. Они выделены на рисунках приведённых выше. Один из способов укладки тримино, при котором остаётся свободной верхняя левая из выделенных клеток, приведён на следующем рисунке.
Расположения тримино, при которых будут оставаться свободными другие указанные поля доски, легко получить поворотом предложенного на 90°, 180° и 270°.
10. «Дельфин» – фигура, которая ходит на одно поле вверх, вправо или по диагонали налево вниз, как показано на рисунке.
Может ли «дельфин», начиная из левого нижнего угла квадратной доски со стороной 8, обойти всю эту доску, побывав в каждой клетке ровно по одному разу?
Занумеруем горизонтали доски снизу вверх числами 0, 1, 2, … , 7 и вертикали доски слева направо теми же числами (смотрите рисунок ниже). Каждой клетке доски поставим в соответствие сумму номеров вертикали и горизонтали, на пересечении которых эта клетка находится (на рисунке эти суммы выписаны зелёным цветом лишь для нескольких клеток). Обозначим эту сумму s.
«Дельфин» начинает свой путь в клетке, для которой s = 0. При каждом ходе «дельфин» перемещается в клетку, которой соответствует число s либо большее на 1, либо меньшее на 2 по сравнению с предыдущей. Значит, остаток от деления на 3 числа s изменяется в следующей последовательности: 0, 1, 2, 0, 1, 2, … (на рисунке эти остатки для некоторых клеток выписаны красным цветом).
Предположим, что «дельфин» обошёл всю доску, побывав в каждой клетке по одному разу. Отбросим начальную клетку и разобьём оставшиеся 63 клетки на 21 тройку клеток, подряд идущих по ходу «дельфина». Тогда в каждой тройке ровно одной клетке соответствует число, кратное 3 (красные нули). Однако таких клеток (выделены на рисунке) имеется лишь 20.
Полученное противоречие опровергает предположение и доказывает, что «дельфин» не может обойти всю доску.
Задачи без решений
1. В одной вершине куба написали число 1, в остальных – ноли. Можно прибавлять по 1 к числам, записанным на концах одного ребра. Можно ли добиться того, чтобы все числа делились на 3?
2. На доске записаны числа от 1 до 20. Пару чисел (х;у) можно заменить на число х+у+ху. Какое число останется на доске после 19 операций?
3. а) Во 15 клетках квадратной таблицы со стороной 4 расставлены плюсы. Единственный минус записан у края таблицы в не угловой клетке. Разрешается одновременно менять знак во всех клетках, расположенных в одной строке, в одном столбце или на прямой, параллельной какой-нибудь диагонали (в частности, в любой угловой клетке). Докажите, что сколько бы мы не провели таких перемен знака, нам не удастся получить таблицу из одних плюсов.
б) Во всех клетках квадратной таблицы со стороной 8 расставлены плюсы, за исключением одной не угловой клетки, где стоит минус. Разрешается одновременно менять знак во всех клетках одной горизонтали, одной вертикали или одной диагонали (в частности, в любой угловой клетке; диагональ – линия, по которой ходит шахматный слон). Докажите, что сколько бы мы не провели таких перемен знака, нам не удастся получить таблицу из одних плюсов.
4. По кругу расставлены числа от 1 до 22...2 (запись числа состоит из n двоек, n>1). Числа, стоящие на соседних местах, можно поменять местами. После некоторого количества таких операций оказалось, что каждое число переместилось на диаметрально противоположное место. Доказать, что в некоторый момент меняли местами числа, сумма которых равна 22...3 (запись числа состоит из n–1 двойки и одной тройки в конце).
5. На плоскости дан правильный шестиугольник. Каждая его сторона разделена на 1000 равных частей, и точки деления соединены отрезками, параллельными сторонам шестиугольника. Выберем какие-либо три узла получившейся сетки, являющиеся вершинами правильного треугольника (любого размера и расположения), и окрасим их. Будем продолжать окрашивать таким способом тройки узлов до тех пор, пока это возможно. Докажите, что если неокрашенным останется один узел, то он не может быть вершиной исходного шестиугольника.
Создано на конструкторе сайтов Okis при поддержке Flexsmm - инстаграм накрутка подписчиков