Задача7 «Положительные числа» (Олимпиада школьников-2017)

Логические задачи

Модераторы: Азарапетыч, Администрация

Аватара пользователя
Инна
Популярный автор
Популярный автор
Сообщения: 1434
Зарегистрирован: 18 июл 2006, 18:44
Пол: Женский
Откуда: Калифорния

Re: Задача7 «Положительные числа» (Олимпиада школьников-2017

Сообщение Инна »

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

Аватара пользователя
Инна
Популярный автор
Популярный автор
Сообщения: 1434
Зарегистрирован: 18 июл 2006, 18:44
Пол: Женский
Откуда: Калифорния

Re: Задача7 «Положительные числа» (Олимпиада школьников-2017

Сообщение Инна »

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

Юляша
Популярный автор
Популярный автор
Сообщения: 3352
Зарегистрирован: 15 янв 2009, 12:32
Пол: Женский

Re: Задача7 «Положительные числа» (Олимпиада школьников-2017

Сообщение Юляша »

Есть еще такой странный подход (в счет моей первоначальной идеи с кругом)

Во все внутренние области поставим единички.
Снаружи у нас останется 2К областей и К уравнений вида А(1)+А(2)+...+A(K)=A(K+1)+A(K+2)+...+A(K+K)+M1, где M1 - разница в количестве единичек по разные стороны одной соответствующей прямой может быть как положительной так и отрицательной.

Обратим внимание, что следующее уравнение имеет вид А(2)+...+A(K+1)=A(K+2)+...+A(K+K)+A(1)+M2.

Вычтем из первого уравнения второе. Получим А(1)-А(К+1)=А(К+1)-А(1)+М1-М2. Или А(1)-А(К+1)=(М1-М2)/2.

То есть, в итоге мы получаем, что в уравнениях отделяются пары переменных и наличие положительных корней не вызывает сомнения. Вот иллюстрация. Нужные значения М показаны в квадратиках. Где косяк?
Круг.png
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.

Аватара пользователя
Инна
Популярный автор
Популярный автор
Сообщения: 1434
Зарегистрирован: 18 июл 2006, 18:44
Пол: Женский
Откуда: Калифорния

Re: Задача7 «Положительные числа» (Олимпиада школьников-2017

Сообщение Инна »

Все же постараюсь описать аккуратно.
Лемма 1. Если есть два заполнения, удовлетворяющие условиям, то их сумма (заполнение, где в каждой области сумма соответствующих чисел из этих заполнений), тоже удовлетворяет условию.
Лемма 2. Для любой области О существует заполнение целыми числами с положительной суммой, так что все числа, кроме, возможно, находящегося в О больше нуля. Доказывается по индукции: Убирается прямая П, образующая кусок границы О, и производится правильное заполнение. Числа в областях, не ограниченных П, удваиваются, в соприкасающихся с П кроме О - остаются без изменения, в О ставится число, чтобы суммы слева и справа от П были равны.

Построение.
Для каждой области О(i) строится базовое заполнение Б(i), так что все числа кроме находящегося в О(i) положительны.

Затем, прибавлением заполнений из множества Б строится последовательность заполнений З(1) З(2) З(3) З(4)...

В качестве З(1) берется Б с самым меньшим по модулю отрицательным числом.
На каждом ходу в имеющемся заполнении З(к) выбирается область О(k) c наибольшим числом и добавляется заполнение Б(к), где число в О(к) отрицательно. И так до тех пор, пока отрицательных чисел не останется.
Почему процесс прекратится рано или поздно?
Поскольку общая сумма возрастает, начиная с некоторого момента в заполнении будет находиться число больше по модулю, чем все отрицательные числа из множества Б.
С этого момента новых отрицательных чисел появляться не будет.
А старые будут увеличиваться с каждым ходом - то есть в какой-то момент тоже все станут положительными.
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...

Аватара пользователя
Инна
Популярный автор
Популярный автор
Сообщения: 1434
Зарегистрирован: 18 июл 2006, 18:44
Пол: Женский
Откуда: Калифорния

Re: Задача7 «Положительные числа» (Олимпиада школьников-2017

Сообщение Инна »

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

Аватара пользователя
Dendr
Акула пера
Акула пера
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Пол: Мужской
Откуда: Раменское, Мос.обл.
Контактная информация:

Re: Задача7 «Положительные числа» (Олимпиада школьников-2017

Сообщение Dendr »

А вот это реально здорово.
К уравнений для 2К переменных дает К свободных параметров.

Фактически, надо доказать, что существует такой вектор в К-мерном пространстве, что известный линейный оператор (зависящий от расположения узлов) переводит его в вектор в той же области декартового пространства (первой четверти в случае К=2 и т.д.)

"на пальцах" это прибавление положительного числа, "достаточно большого", ко всем векторам. Более математически надо подумать..

Аватара пользователя
Dendr
Акула пера
Акула пера
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Пол: Мужской
Откуда: Раменское, Мос.обл.
Контактная информация:

Re: Задача7 «Положительные числа» (Олимпиада школьников-2017

Сообщение Dendr »

А. Все проще. После расстановки единиц (или ЛЮБЫХ положительных чисел) во внутренние области, начинаем составлять уравнения для каждой прямой.

Построим окружность еще большего (много большего) радиуса. При этом масштабе все прямые пересекаются практически в одной точке, то есть, идя по кругу, мы дважды встретим их пересечения с окружностью в одном и том же порядке.
Обозначаем искомые числа a, b, ... z до тех пор, пока мы не пройдем прямую, с которой начали. Дальше пишем a', b', ... z'.
Видно, что в уравнении числа p и p' стоят с разным знаком и единичным коэффициентом. Просто вводим новую переменную P=p-p'.

Итак, количество переменных совпадает с количеством уравнений, причем по условию линейно независимых.
Находим все A, B, ...Z.
Остается взять два числа 1 и 1+|P| и поставить их вместо p и p' в зависимости от знака P.

Задача решена!

Ответить

Вернуться в «Задачки»