В ряд выписаны числа 12, 22, ..., (N−1)2, N2. Между ними произвольным образом расставляют знаки «+» и «-» и находят получившуюся сумму. Может ли такая сумма равняться:
а) 4, если N=12?
б) 0, если N=69?
в) 0, если N=64?
г) 5, если N=90?
Посмотреть решение
Предварительное решение, не проверено экспертом.
Ранее доступное решение переведено в общий параметрический рецепт; новая независимая проверка не проводилась.
Шаг 1. Первый квадрат 12 записан без предшествующего знака и остаётся положительным. Пусть полная положительная сумма Q=6N(N+1)(2N+1), а квадраты с отрицательным знаком имеют сумму P. Тогда итог равен Q−2P. Для результата T нужно P=2Q−T - неотрицательное целое. Ищем подмножество квадратов 22,…,N2 с этой суммой.
N=12
T=4
Шаг 2. Начинаем с достижимой суммы 0. При обработке квадрата j2 каждая прежняя достижимая сумма s даёт два случая: не брать квадрат или взять и получить s+j2. Каждый квадрат обрабатывается один раз. По индукции это ровно все подмножества. Найденный список отрицательных индексов даёт конструкцию; недостижимость нужной суммы исключает возможность.
T=(2;3;4;7;8;9;10)
Шаг 3. Да. Приведённая конструкция удовлетворяет условию.
Шаг 1. Первый квадрат 12 записан без предшествующего знака и остаётся положительным. Пусть полная положительная сумма Q=6N(N+1)(2N+1), а квадраты с отрицательным знаком имеют сумму P. Тогда итог равен Q−2P. Для результата T нужно P=2Q−T - неотрицательное целое. Ищем подмножество квадратов 22,…,N2 с этой суммой.
N=69
T=0
Шаг 2. Начинаем с достижимой суммы 0. При обработке квадрата j2 каждая прежняя достижимая сумма s даёт два случая: не брать квадрат или взять и получить s+j2. Каждый квадрат обрабатывается один раз. По индукции это ровно все подмножества. Найденный список отрицательных индексов даёт конструкцию; недостижимость нужной суммы исключает возможность.
T={}
Шаг 3. Нет. Необходимое условие или полная конечная область исключает возможность.
Шаг 1. Первый квадрат 12 записан без предшествующего знака и остаётся положительным. Пусть полная положительная сумма Q=6N(N+1)(2N+1), а квадраты с отрицательным знаком имеют сумму P. Тогда итог равен Q−2P. Для результата T нужно P=2Q−T - неотрицательное целое. Ищем подмножество квадратов 22,…,N2 с этой суммой.
N=64
T=0
Шаг 2. Начинаем с достижимой суммы 0. При обработке квадрата j2 каждая прежняя достижимая сумма s даёт два случая: не брать квадрат или взять и получить s+j2. Каждый квадрат обрабатывается один раз. По индукции это ровно все подмножества. Найденный список отрицательных индексов даёт конструкцию; недостижимость нужной суммы исключает возможность.
Шаг 3. Да. Приведённая конструкция удовлетворяет условию.
Шаг 1. Первый квадрат 12 записан без предшествующего знака и остаётся положительным. Пусть полная положительная сумма Q=6N(N+1)(2N+1), а квадраты с отрицательным знаком имеют сумму P. Тогда итог равен Q−2P. Для результата T нужно P=2Q−T - неотрицательное целое. Ищем подмножество квадратов 22,…,N2 с этой суммой.
N=90
T=5
Шаг 2. Начинаем с достижимой суммы 0. При обработке квадрата j2 каждая прежняя достижимая сумма s даёт два случая: не брать квадрат или взять и получить s+j2. Каждый квадрат обрабатывается один раз. По индукции это ровно все подмножества. Найденный список отрицательных индексов даёт конструкцию; недостижимость нужной суммы исключает возможность.