Здравствуйте, LCR, Вы писали:

MP>>Легко убедится, что результирующая операция эквивалентна вращению на 2 и XOR с исходным.
LCR>Не понял Почему эквивалентна?

Рассмотрим число стоящее на нулевой позиции:
1-ая операция: 0 XOR 1
2-ая операция: (0 XOR 1) XOR (1 XOR 2) == (0 XOR 2)

Из-за симметрии задачи относительно вращений, для других мест — аналогично.

Здравствуйте, MichaelP, Вы писали:

Les>>5б. Дан произвольный набор из чисел 1 и -1 длиной 2^k. Из него получается новый по следующему правилу: каждое число умножается на следующее за ним, последнее, 2^k-ое число умножается на первое. С новым набором 1 и -1 проделывается тоже самое и т.д. Докажите, что в конце концов получится набор, состоящий из одних единиц.

MP>Для начала заметим, что приведенное правило эквивалентно следующей операции (просто мне удобней в этих терминах):
MP>Заменим -1 на 1, +1 на 0. Далее повернем весь набор влево на 1 и XOR с исходным.
MP>Прведем операцию два раза. Легко убедится, что результирующая операция эквивалентна вращению на 2 и XOR с исходным.
MP>Т.е. после двух опреаций мы получили, что можно исходный набор разделить на два (четные и нечетные места) и провести одну опреацию над каждым.
MP>Далее легко убеждаемся, что если опреацию провести два раза по два, что эквивалентно двум операциям на половинных наборах, то мы получим, что результат эквивалентен вращению на 4 и XOR с исходным.
MP>Продолжая "удвоение" далее до 2^k, получим вращение 2^k и XOR с исходным. Т.е. каждое число XOR-ится само с собой. Отсюда все элементы равны 0 или, для исходной задачи, +1.

Ёёёёёёёёёёёёёёёёёёёё твою! — сказал я, когда прочитал решение MichaelP.
Поясню ниже!

Я рассуждал следующим образом.
1. Рассматривать последовательность или произведение нескольких последовательностей — одно и то же. Мы просто проделываем с каждой из них ту же процедуру, а потом перемножаем. Поэтому можно рассмотреть просто последовательность с одной -1 на последнем месте, например. Если в изначальной последовательности m -1, то мы рассматриваем m последовательностей с одной -1 на соответствующем месте.
2. Если у нас одна -1 в конце последовательности, то она за 1 шаг превращается в -,- в конце. За два шага в -,+,-. Следовательно за 4 шага в -,+,-*-=+,+,-. И т.д. По индукции: если за 2^t шагов в -,+,...,+,-, где 2^t-1 +, то за следующие 2^t шагов каждая -1 точно так же как начальная превращается в -,+,...,+,-, где 2^t-1 +. Причем две -1 приходятся на одно место, т.е. там получается +1. Итак за 2^t шагов мы получаем -1 на месте, отстоящем на 2^t по кругу от последнего.
3. Если бы нам удалось показать, что однажды эта -1 по кругу попадет в себя, то мы бы в каждой последовательности, а следовательно и в их произведении, получили бы одни 1!

Вот тут я и сидел... Дело в том, что я прочитал условие как 2k, а не 2^k!
Ёёёёёёёёёёёёёёёёёёёё твою! — сказал я, когда прочитал решение MichaelP.

Здравствуйте, MichaelP:
Реально!

Здравствуйте, Apapa, Вы писали:

A>Ёёёёёёёёёёёёёёёёёёёё твою! — сказал я, когда прочитал решение MichaelP.

Да уж, я тоже искал минимальное расстояние вместо максимального...

Не расстраивайся, задач ещё мноооооооого.

Здравствуйте, LCR, Вы писали:

LCR>Не расстраивайся, задач ещё мноооооооого.

Ага, только мне поработать надо для разнообразия.

Здравствуйте, Apapa, Вы писали:

Vi2>>

A>>>Что-то никакой реакции — не убедил?
A>>>Похоже это на правду в конце-концов или нет? Аж самому интересно стало!!!

Vi2>>На правду похоже. Но рассуждения по площади — это необходимое условие. Пример — расположение в круге R других кругов r. При определенном радиусе r площадь маленького круга будет меньше 1/2 площади большого, но располжить два таких круга в этом круге не удасться, потому что диаметр маленького круга будет чуть больше радиуса большого. Т.е. r > R/2, но Sr < SR/2.

Vi2>>Таким образом нужно еще показать, что оставшаяся площадь как-то расположена регулярно. Что там возможно расположение нужного круга радиуса 1. Вобщем, то, что и нужно-то было доказать.

A>Отличное замечание!!! Одним словом, ты хотел сказать, что надо было круг располагать целиком внутри прямоугольника!

A>Ну что же. Рассмотрим внутренность 24х19=456 (отступили по 0.5 от краев). 120 квадратов с их расширениями до Round Rectangle занимают максимум 120*(3+pi/4)=360+30pi<454,25 площади! Т.е. внутри квадрата 24х19=456 останется еще немного места. Туда и помещаем центр круга диаметра 1. Т.к. мы отступили по 0.5 от краев, то круг целиком лежит в прямоугольнике 25х20.

Здравствуйте, Apapa, Вы писали:

...

Vi2>>Таким образом нужно еще показать, что оставшаяся площадь как-то расположена регулярно. Что там возможно расположение нужного круга радиуса 1. Вобщем, то, что и нужно-то было доказать.

A>Отличное замечание!!! Одним словом, ты хотел сказать, что надо было круг располагать целиком внутри прямоугольника!

A>Ну что же. Рассмотрим внутренность 24х19=456 (отступили по 0.5 от краев). 120 квадратов с их расширениями до Round Rectangle занимают максимум 120*(3+pi/4)=360+30pi<454,25 площади! Т.е. внутри квадрата 24х19=456 останется еще немного места. Туда и помещаем центр круга диаметра 1. Т.к. мы отступили по 0.5 от краев, то круг целиком лежит в прямоугольнике 25х20.

Замечательное решение!

Фактически задача свелась к доказательству того, что в прямоугольнике 24х19 нельзя расположить 120 Round Rectangle так, чтобы не осталось свободного места. Где-то что-то подобное уже было...

И естественно, возникает очевидный вопрос: каково минимальное количество таких Round Rectangle ?
Имхо, найти такое решение, а тем более доказать его — будет совсем не просто.

Здравствуйте, zee, Вы писали:

zee>От противного.

...

zee>Этим доказано, что построить последовательность X невозможно.



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

Здравствуйте, mrhru, Вы писали:

M>Здравствуйте, zee, Вы писали:

zee>>От противного.

M>...

zee>>Этим доказано, что построить последовательность X невозможно.

M>

M>Аналогично по индукции можно доказать, что задача справедлива для любого числа бесконечных последовательностей натуральных чисел.

Нет!

Индукция сломается вот здесь:

z> Также очевидно, что все пары (b',c') последовательности Y должны быть различными.
z> [ Дк-во: если bi=bj, ci=cj, то в случае ai >= aj имеем p=i, q=j, а в случае ai < aj имеем p=j, q=i ]


т.е. если у нас будет последовательность Y векторов (a',b',c,d), таких, что a'> A, b' > B,
c', d' — произвольные, то все пары (c',d') последовательности Y уже НЕ должны быть различными.

При
A < a'i < a'j
B < b'j < b'i
С < c'i = c'j
D < d'i = d'j
уже не подходит ни случай (p=i, q=j), ни (p=j, q=i)

===========

Пример последовательности для n=4:
a = n (1, 2, 3, 4, ...)
b = 2 + (-1)^n (1, 3, 1, 3, ...)
c = 2 — (-1)^n (3, 1, 3, 1, ...)
d = 2 + (-1)^n (1, 3, 1, 3, ...)
Совершенно очевидно, что найти p и q уже не удастся.

Ой, меня малость глюкануло:
zee>Пример последовательности для n=4:
zee>a = n (1, 2, 3, 4, ...)
zee>b = 2 + (-1)^n (1, 3, 1, 3, ...)
zee>c = 2 — (-1)^n (3, 1, 3, 1, ...)
zee>d = 2 + (-1)^n (1, 3, 1, 3, ...)
фигня
p = 3, q = 1
(3,1,3,1) и (1,1,3,1)

Возможно, я не прав насчёт существования такой последовательности.
Однако, моё доказательство для индукции все равно не подходит

Здравствуйте, zee, Вы писали:

zee>Пример последовательности для n=4:

zee>a = n           (1, 2, 3, 4, ...)
zee>b = 2 + (-1)^n  (1, 3, 1, 3, ...)
zee>c = 2 - (-1)^n  (3, 1, 3, 1, ...)
zee>d = 2 + (-1)^n  (1, 3, 1, 3, ...)

zee>Совершенно очевидно, что найти p и q уже не удастся.

Опровержение примера:

a = n           (1, 2, 3, 4, ...)
b = 2 + (-1)^n  (1, 3, 1, 3, ...)
c = 2 - (-1)^n  (3, 1, 3, 1, ...)
d = 2 + (-1)^n  (1, 3, 1, 3, ...)

p = 3, q = 1

a3(3) >= a1(1)
b3(1) >= b1(1)
c3(3) >= c1(3)
d3(1) >= d1(1)

Условие выполняется (для любого нечётного p >= 3).

Насчёт индЮкции — ещё подумаю.

Здравствуйте, mrhru, Вы писали:

M>Насчёт индЮкции — ещё подумаю.

Вот что придумал.

Для придания наукообразности , докажем вспомогательную Клемму:

Клемма:

В любой бесконечной последовательностей натуральных чисел a1, a2, ... , an, ... 
можно выделить бесконечную неубывающую подпоследовательность, т.е. 
ai1 <= ai2 <= ... <= ain <= ...

Доказательство бесконечности очевидно — кол-во чисел, меньших заданного — конечно.

А теперь с помощью Клеммы, можно доказать более Сильное Утверждение, чем исходное:

Для любого (усиление1) числа бесконечных последовательностей натуральных чисел 
 a1, a2, ... , an, ... 
 b1, b2, ... , bn, ... 
 ...
 k1, k2, ... , kn, ... 
 ...

найдутся такие номера p и q, что 
ap >= aq, 
bp >= bq, 
...
kp >= kq 
...

и (усиление2)
p > q

Построим с помощью Клеммы подпоследовательность из последовательности a
ai1 <= ai2 <= ... <= ain <= ...

При этом, выбирая элементы из оставшихся последовательностей на тех же местах ij,
мы получим подпоследовательности
bi1, bi2, ... , bin, ...
...
ki1, ki2, ... , kin, ...
...

Повторяем процесс для последовательности b, c...
При каждом шаге, очевидно, свойство неубывания для предыдущих последовательностей не нарушается.
В конце концов мы получим последовательности, для которых справедливо Сильное Утверждение.
Всё. Правильно?

Полностью согласен!