РЕШУ ОЛИМП — математика

Задания

П. В. Бибиков, тренер сборной Москвы на Всероссийской олимпиаде школьников по математике, предлагает вам решить следующую задачу: Дан клетчатый прямоугольник 2m × 2n, разбитый произвольным образом на доминошки 2 × 1. Если две доминошки образуют квадрат 2 × 2, разрешается повернуть их обе на 90° (сделать флип). Наша цель  — последовательностью флипов сделать все доминошки горизонтальными (кирпичная кладка) за как можно меньшее количество операций.

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

Пусть нам дано некоторое замощение прямоугольника доминошками, которое мы обозначим через T. Сопоставим замощению его функцию высоты  — это будет функция на вершинах клеток нашего прямоугольника, которую мы будем обозначать H_T(υ). Определим ее следующим образом.

Выберем левую нижнюю вершину υ₀ прямоугольника и положим ее высоту равной нулю; далее, каждую вершину υ соединим с υ₀ путем, который проходит по линиям сетки и не пересекает доминошек. Этот путь состоит из стрелок, каждая из которых проходится либо в попутном направлении (т. е. сонаправлена с путем), либо в противоположном. Положим высоту H_T(υ) равной разности числа попутных и противоположно направленных стрелок.

Пусть H(υ)  — функция на вершинах графа G, удовлетворяющая следующему свойству: для любых соседних вершин u и υ, ребро между которыми направлено от u к υ, либо $H левая круглая скобка v правая круглая скобка =H левая круглая скобка u правая круглая скобка плюс 1,$ либо $H левая круглая скобка v правая круглая скобка =H левая круглая скобка u правая круглая скобка минус 3.$ Докажите, что H(υ) является функцией высоты единственного замощения T.

P. Bibikov, coach of the Moscow team at the All-Russian Olympiad in mathematics, suggests you the

following problem:

There is a checkered rectangle 2m × 2n given, arbitrarily divided into rectangles 2 × 1 («dominoes»). If two dominoes form a 2 × 2 square, it is allowed to rotate them both by 90° (make a flip). Our goal is to make all dominoes horizontal (brickwork) by a sequence of flips in as few operations as possible.

Let’s color our rectangle in a chessboard color, assuming the bottom left corner to be black. Let’s draw the arrows along the sides of the squares so that the black squares go counterclockwise, and the white ones go clockwise.

Let us be given some tiling of a rectangle with dominoes, which we denote by T. Let us associate the tiling with its height function  — it will be the function at the vertices of the cells of our rectangle, which we will denote by H_T(υ). We define it as follows. Select the lower left vertex of the υ₀ rectangle and set its height to zero; further, each vertex υ is connected to υ₀ by a path that passes along the grid lines and does not intersect the dominoes. This path consists of arrows, each of which is traversed either in the same direction (i. e., co-directed with the path), or in the opposite direction. Let the height of H_T(υ) be equal to the difference in the number of trailing and oppositely directed arrows.

Let H(υ) be a function on the vertices of the graph G satisfying the following property: for any connected vertices u and υ, the edge between which is directed from u to υ there is $H левая круглая скобка v правая круглая скобка =H левая круглая скобка u правая круглая скобка плюс 1$ or $H левая круглая скобка v правая круглая скобка =H левая круглая скобка u правая круглая скобка минус 3.$ Prove that H(υ) is a function of the height of the unique tiling T.

Решение. Единственность следует из такого простого соображения. Рассмотрим те ребра, разность функций высоты на концах которых равна единице. Эти ребра будут образовывать границы доминошек нашего разбиения; напротив, те ребра, разность функций высоты на концах которых равна минус трем, будут «закрыты» доминошками.

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

Uniqueness follows from such a simple consideration. Consider those edges, the difference of the height functions at the ends of which is equal to one. These edges will form the boundaries of the dominoes of our tiling; on the contrary, those edges, the difference of the height functions at the ends of which is equal to minus three, will be «closed by dominoes.

Next, consider a cell. All arrows on its border point in the same direction: either clockwise or counterclockwise. Since the sum of the increments of the height function when traversing this cell is equal to zero, this means that there are exactly three edges out of four for whichthe difference in the valuesof the height function at their ends is equal to one, and one edge for which this difference is equal to minus three; it will be closed by the domino. The same can be said about the cell adjacent to the given one along this edge. Thus, all the cells will be divided into pairs, that is, in the end, we really get a tiling of our rectangle.

Критерии проверки:

Описание системы баллов за решение задач

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

0 — задача не решена или решена неверно из-за грубых ошибок в рассуждениях;

1 — задача решена неверно, но присутствует плодотворная идея, применимая для решения задачи;

2 — задача решена неверно, но присутствует и частично применена плодотворная идея, достигнут некоторый прогресс в решении;

3 — задача решена частично либо полностью, но с существенными арифметическими ошибками при наличии правильного хода рассуждений;

4 — задача решена верно, но с незначительными ошибками;

5 — задача полностью решена.

II. Для каждой задачи вычисляется средний балл (M) по результатам ее решения всеми участниками.

III. Весовой коэффициент (K) каждой задачи вычисляется по простой формуле:

$K=10 минус 1,8 умножить на M .$

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

IV. Балл каждого участника за каждую задачу умножается на весовой коэффициент этой задачи.

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

Specification of the score system

I. Pre-score of the solution to each problem is set on a 5-point scale, where

0 — a task was not solved or solved incorrectly due to gross reasoning blunder;

1 — a task was solved incorrectly but there is a fruitful idea that can be used to solve the task;

2 — a task was solved incorrectly but a fruitful idea is present and partially applied, some progress has been made in the solution;

3 — a task was solved partially or completely but with significant arithmetic errors in the presence of the correct line of reasoning;

4 — a task was solved correctly but with minor errors;

5 — a task was solved completely.

II. An average score (M) is calculated based on the results of all participants for each task.

III. The weighting factor (K) of each task is calculated using a simple formula:

$K=10 минус 1,8 умножить на M.$

Thus, the weighting coefficient of a task can vary from 1 to 10 , depending on the average score of the participants for this task.

IV. Each participant's score for each task is multiplied by the weighting factor of that task.

V. The points scored by the participant are summed and rounded up to the nearest integer.

Ключ