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

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

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

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

Сообщение Тоня » 01 фев 2017, 22:54

На плоскости проведено несколько прямых, никакие две из которых не параллельны, и никакие три не проходят через одну точку. Докажите, что в областях, на которые прямые поделили плоскость, можно расставить положительные числа так, чтобы суммы чисел по обе стороны относительно любой из проведённых прямых были равны.
Тоня
Популярный автор
Популярный автор
 
Сообщения: 1597
Зарегистрирован: 29 июн 2005, 21:45

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

Сообщение Юляша » 02 фев 2017, 00:14

Нарисуем круг, так что все точки пересечения прямых лежат внутри него. Наружу круга торчат 2n непересекющихся лучей (n - число прямых). В каждую наружную область, ограниченную дугой круга и двумя соседними лучами запишем число 1.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Юляша
Популярный автор
Популярный автор
 
Сообщения: 3163
Зарегистрирован: 15 янв 2009, 12:32

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

Сообщение Тоня » 02 фев 2017, 00:40

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

По поводу этой задачи было уточнение, сделанное прямо в аудитории во время олимпиады, простите, что я, перепечатывая с листочка заданий его упомянуть забыла. уточнение сводится к тому, что числа расставляются В КАЖДУЮ ОБЛАСТЬ, т.е. не только в "наружную область", но и в те области, что находятся в центре круга, не граничат с дугами.
Тоня
Популярный автор
Популярный автор
 
Сообщения: 1597
Зарегистрирован: 29 июн 2005, 21:45

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

Сообщение Инна » 02 фев 2017, 00:49

По индукции.
При проведении новой прямой нужно лишь разделить те области, которые она пересекает.
Напишем в левые области относительно ее маленькие E. А в правые - почти изначальные значения непересеченных областей.
Надо строго доказать, что в левой части сумма будет больше.
Аналогично наоборот, если в правые области маленькие Е, то сумма будет больше в правой половине.
Значит, непрерывно меняя соотношение между числами в одной из областей, можно достичь равенства.
Если не требовать положительности записанных чисел, то гораздо проще.
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...
Аватара пользователя
Инна
Популярный автор
Популярный автор
 
Сообщения: 1434
Зарегистрирован: 18 июл 2006, 18:44
Откуда: Калифорния

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

Сообщение Юляша » 02 фев 2017, 08:22

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

Для одной прямой задача тривиальна.
Пусть она решена для К прямых.
Проведем К+1-ю прямую. Она рассекает ровно К+1 область.
В каждой такой области удалим число М, которое в ней располагалось, и поставим М/2 в каждую из новых двух областей получившихся ее рассечением.
Для старых прямых суммы не изменились, для новой равенство сумм получается автоматически.

Кстати, натуральные числа получить легко.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Юляша
Популярный автор
Популярный автор
 
Сообщения: 3163
Зарегистрирован: 15 янв 2009, 12:32

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

Сообщение Dendr » 02 фев 2017, 10:01

Не работает алгоритм.
Рисуем одну прямую, пишем 720 с обеих сторон.
Рисуем вторую, перпендикулярно первой (получаем как бы координатные оси), в каждой четверти числа 360.
Рисуем третью, пусть она выглядит как y=1-x, то есть проходит через 1, 2 и 4 четверти. Теперь они поделены на две части, в каждой из которых записаны числа 180.
Справа-вверху получаем сумму 540, слева-внизу - 900. Не годится, даже зря числа "с запасом" взял сейчас.
Аватара пользователя
Dendr
Акула пера
Акула пера
 
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Откуда: Раменское, Мос.обл.

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

Сообщение Dendr » 02 фев 2017, 10:21

Лучше так.

Без ограничения общности можем считать, что сумма всех чисел в подходящей расстановке на плоскости равна 2.

Проводим первую линию, в получившихся полуплоскостях пишем 1.

Теперь индукция. Пусть мы провели K прямых и расставили в областях числа требуемым образом.
Проведем K+1-ю, она разделит на две части K+1 область.
Рассмотрим суммы в "целых" областях с разных сторон этой прямой, S1 и S2. До единицы не хватает, соответственно, r1 и r2. В разрезанных областях вместо числа M напишем M*r1/(r1+r2) в одной части и остальное - в другой. Тем самым мы получим, что сумма по обе стороны новой прямой равна 1.
Все числа, надо заметить, рациональные. Так что можно свести и к натуральным.

Осталось доказать, что r1>0, r2>0.
Аватара пользователя
Dendr
Акула пера
Акула пера
 
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Откуда: Раменское, Мос.обл.

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

Сообщение Dendr » 02 фев 2017, 10:24

Виноват, пропустил сообщение от Инны, она написала то же самое, только менее формально.

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

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

Сообщение Dendr » 02 фев 2017, 10:30

Пересечения N прямых (удовлетворяющие условию задачи) вроде бы гомоморфны друг другу?
Аватара пользователя
Dendr
Акула пера
Акула пера
 
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Откуда: Раменское, Мос.обл.

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

Сообщение Инна » 02 фев 2017, 11:23

Дендр, действительно с олимпиадным языком просто беда без практики. Но вот какой нюанс, почему r1 и r2 положительны? Как понимаю, это верно не всегда
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...
Аватара пользователя
Инна
Популярный автор
Популярный автор
 
Сообщения: 1434
Зарегистрирован: 18 июл 2006, 18:44
Откуда: Калифорния

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

Сообщение Dendr » 02 фев 2017, 19:31

Я вообще олимпиадного языка не знаю. Со школы еще решал, как решалось, без шаблонов (в результате получалось хуже, чем могло бы быть). Тем более что терминами высшей математики обращаться проще... Ну это неважно.

С положительностью r1 и r2 просто беда пока. Вот если гомоморфизм подтвердится, то можно устроить конструктор, то есть нумерацию построенных прямых с последующей расстановкой чисел. Хотя не факт, что от школяров требуют именно такого обоснования.
Аватара пользователя
Dendr
Акула пера
Акула пера
 
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Откуда: Раменское, Мос.обл.

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

Сообщение Инна » 02 фев 2017, 20:17

Вот какая идея возникла.
Вначале по описанному выше принципу ставим числа, чтобы условие выполнялось, но оставалось не более одного отрицательного числа.
Пусть все числа целые и больше например N^2 где N число прямых.
Задача - "нарастить" отрицательное число за счет имеющих ту же граничную прямую до положительного.
Можно использовать следующую трансформацию:
Если к прямой примыкают области с числами а , b, c и d (а и b имеют общий отрезок границы, c и d имеют общий отрезок границы, а и с по одну сторону на прямой), то их можно заменить соответственно на a+1, b-1, c+1, d-1.
Общая сумма при такой трансформации не меняется, выполнение условия задачи сохраняется.
При этом будем действовать так, чтобы новых неположительных чисел не возникало.
Следующая трансформация невозможна, только если вокруг отрицательного числа остались лишь единицы.
Тогда их такими же трансформациями надо наращивать за счет близлежащих чисел.
Надо строго доказать, что это возможно всегда.
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...
Аватара пользователя
Инна
Популярный автор
Популярный автор
 
Сообщения: 1434
Зарегистрирован: 18 июл 2006, 18:44
Откуда: Калифорния

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

Сообщение Инна » 02 фев 2017, 20:17

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

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

Сообщение Dendr » 02 фев 2017, 22:42

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

Для трех, очевидно, это выполняется: любые три прямые образуют треугольник, который переводится в правильный треугольник со стороной 1.

Для четырех тоже: мы можем всегда повернуть фигуру так, чтобы две прямые пересекались в координатах (1, 0), две другие - в (0, 1). Первые образуют острый угол с биссектрисой Ox, вторые - Oy.

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

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

Сообщение Инна » 02 фев 2017, 22:54

Нет конечно.
Например, N прямых могут образовать область в виде N-угольника, а могут - нет.
Уже 5 прямых могут как звезда, а могут иначе.
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...
Аватара пользователя
Инна
Популярный автор
Популярный автор
 
Сообщения: 1434
Зарегистрирован: 18 июл 2006, 18:44
Откуда: Калифорния

След.

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

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2

cron