Числовые наборы на карточках и досках — ЕГЭ профиль

Суть темы: числовые наборы и операции над ними

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

Сложность в том, что прямой перебор не работает. Главное оружие здесь - инвариант: величина, которая не меняется ни при одной из разрешённых операций. Если в начальном наборе инвариант равен $A,$ а в конечном должен быть $B \neq = A,$ то переход невозможен - и это мгновенное доказательство для пункта «б» или для оценки в пункте «в».

Ключевые понятия

Для работы с задачами на операции нужно чётко различать три типа величин.

ВАЖНОЕ

Инвариант

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

Самые частые инварианты на ЕГЭ:

Сумма всех чисел (если операция её сохраняет).
Чётность суммы. Если каждая операция меняет сумму на чётное число, чётность суммы - инвариант.
Остаток суммы при делении на $k$ (например, на 3).
Сумма квадратов (например, при замене $a, b$ на $\frac{a + b}{2}$ и $\frac{a - b}{2}$ ).
Количество нечётных чисел по $mod 2 .$

Смысл: если инвариант начального набора не совпадает с инвариантом целевого, цель недостижима.

ВАЖНОЕ

Полуинвариант (монотонная величина)

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

Пример: операция «заменить $a$ и $b$ на $a + b$ и $∣ a - b ∣$ » умножает сумму квадратов на 2:

a^{2} + b^{2} \to (a + b)^{2} + (a - b)^{2} = 2 (a^{2} + b^{2})

Сумма квадратов растёт монотонно - это даёт оценку числа шагов.

ВАЖНОЕ

Принцип «оценка плюс пример»

В пункте «в» практически всегда работает связка из двух частей:

1. Оценка. С помощью инварианта или неравенства докажи, что искомая величина не может быть больше (или меньше) числа $X .$
2. Пример. Предъяви конкретный начальный набор и последовательность операций, на которой достигается значение $X .$

Без примера пункт «в» оценивается в 0 баллов - одна оценка не зачтётся как решение.

iЗАМЕЧАНИЕ

Принцип Дирихле

Если $n + 1$ объект распределить по $n$ ящикам, хотя бы в одном окажется не менее двух. В задачах на числовые наборы это звучит так: среди $N$ чисел с остатками по $mod k$ обязательно найдутся два с одним и тем же остатком при $N > k .$

Как искать инвариант

Угадать инвариант с первого раза получается редко. Есть рабочий порядок действий.

АЛГОРИТМ

Алгоритм поиска инварианта

1. Выпиши операцию формально. Если разрешено заменять $a, b$ на $f (a, b)$ и $g (a, b),$ посмотри, как меняются сумма, произведение, сумма квадратов, количество чисел, максимум и минимум.
2. Проверь стандартный набор: сумма, сумма $mod 2,$ сумма $mod 3,$ сумма квадратов, количество нечётных чисел, произведение знаков.
3. Проведи 2-3 шага на маленьком примере. Возьми набор из 3-4 чисел, выполни операцию дважды, сверь, какая из перечисленных величин не изменилась.
4. Сравни инвариант начального и целевого наборов. Если они совпадают - инвариант не даёт ограничения, ищи другой или строй пример. Если различаются - цель недостижима, и это готовое доказательство.
5. Для оценки в пункте «в» ищи полуинвариант (что монотонно растёт или убывает). Его общий ход от начала до конца даст границу.

Примеры решения

Ниже две задачи. Первая - классический сюжет с операцией $∣ a - b ∣$ и инвариантом чётности суммы. Вторая - задача на замену пары $(a, b) \to (a + b, a - b)$ с полуинвариантом «сумма квадратов».

ПРИМЕР 1

Замена пары чисел и чётность

Условие:
На доске написаны числа $1, 2, 3, \dots, 20 .$ За один ход разрешается стереть любые два числа $a$ и $b$ и вместо них записать одно число $∣ a - b ∣ .$ Операции выполняют до тех пор, пока на доске не останется ровно одно число.

а) Может ли в конце остаться число 3?
б) Может ли в конце остаться число 0?
в) Какое наибольшее число может остаться на доске?

ПРИМЕР 2

Карточки и замена парой

Условие:
На доске написаны числа $1, 2, 3, \dots, 10 .$ За один ход можно выбрать любые два числа $a$ и $b,$ стереть их и записать вместо них два новых числа: $a + b$ и $a - b .$

а) Может ли после одного хода сумма всех чисел на доске оказаться равной 63?
б) Может ли после нескольких ходов на доске появиться набор из десяти нулей?
в) Какое наименьшее значение может принимать сумма квадратов чисел на доске после любого числа ходов?

Частые ошибки

!ЧАСТАЯ ОШИБКА

Неправильный выбор инварианта

Ошибка: объявить инвариантом сумму чисел, когда операция её меняет. Например, в задаче про замену $a, b$ на $∣ a - b ∣$ сумма уменьшается на $2 b$ - она не инвариант, а инвариант только её чётность.

Правильно: явно выпиши изменение величины $Δ = (после) - (до) .$ Инвариант - это только те характеристики, для которых $Δ = 0$ всегда. Для полуинварианта $Δ$ должно быть одного знака или обнуляться.

!ЧАСТАЯ ОШИБКА

Пример без пошаговой последовательности

Ошибка: в пункте «а» или «в» написать «можно за 5 ходов получить 3» и не указать, какие именно ходы.

Правильно: полный пример - это список операций. Например: «ход 1: стираем 7 и 4, пишем 3; ход 2: стираем 3 и 3, пишем 0; ...». Без пошагового протокола пример не засчитывается.

!ЧАСТАЯ ОШИБКА

Оценка без примера в пункте «в»

Ошибка: доказать, что больше $X$ быть не может, и записать $X$ в ответ.

Правильно: оценка показывает «нельзя больше $X$ », но не гарантирует, что $X$ достижимо. Обязательно покажи конкретный начальный набор и протокол операций с результатом ровно $X .$ Без примера - 0 баллов за пункт «в».

Стратегия на экзамене

✓СОВЕТ

Стратегия выполнения задания 20

Время: 30-40 минут, в самом конце работы.
Пункт «а» почти всегда «да». Не пытайся сразу строить теорию - прямо на черновике попробуй получить нужный результат маленьким примером (5-10 чисел, 2-3 хода). Это 1 балл за 5 минут.
Пункт «б» почти всегда «нет». Если перебор не даёт пример, ищи инвариант: чётность суммы, остаток по $mod 3,$ сумму квадратов, количество нечётных. Продемонстрируй, что инварианты начального и целевого наборов не совпадают.
Пункт «в»: сначала гипотеза максимума (посмотри, какое значение получается в «естественных» примерах), затем оценка через полуинвариант или неравенство, и только потом пример.
Оформление примера: выписывай ходы в столбик или таблицу - проверяющему легче проследить, что на каждом шаге набор меняется по правилам задачи.

За что дают баллы

Задание 20 даёт до 4 первичных баллов по следующей шкале:

4 балла: обоснованно получены верные ответы во всех трёх пунктах (а, б, в). В пункте «в» есть и оценка, и пример.
3 балла: полностью верно решён пункт «в» (и оценка, и пример) И верно решён пункт «а» ИЛИ «б».
2 балла: верно решены пункты «а» и «б». ИЛИ полностью верно решён только пункт «в».
1 балл: верно решён только пункт «а» ИЛИ только пункт «б».
0 баллов: записаны только ответы «да/нет» без обоснований. Или в пункте «в» есть оценка, но нет примера (и наоборот). Или приведённый пример не удовлетворяет условию задачи.

Проверь себя0 из 4

1.На доске стирают два числа

a

b

и пишут

∣ a - b ∣ .

Какая величина является инвариантом?

2.На доске числа

1, 2, \dots, 20,

операция - замена пары на

∣ a - b ∣ .

Может ли в конце остаться число 3?

3.Пару

(a, b)

заменяют на

(a + b, a - b) .

Что происходит с вкладом этой пары в сумму квадратов?

4.В пункте «в» доказана оценка «не больше

X

». Что ещё обязательно для полного решения?