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

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

Vi2>

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

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

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

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

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

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

Les>11. Докажите, что для любых трех бесконечных последовательностей натуральных чисел
Les> a1, a2, ... , an, ...
Les> b1, b2, ... , bn, ...
Les> c1, c2, ... , cn, ...
Les>найдутся такие номера p и q, что
Les>ap >=aq,
Les>bp >=bq,
Les>cp >=cq
Les>(вторая буква — индекс)

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

Попробуем построить такую последовательность X векторов (a,b,c), чтобы система равенств не выполнялась ни для каких p и q.
Очевидно, все вектора последовательности X должны быть различными.

Пусть X1=(A,B,C) (A, B, C — натуральные).

Тогда существует лишь конечное число различных векторов (a,b,c), таких, что a < A, b < B, c < C.
Поэтому, X содержит бесконечное количество векторов, таких, что или a > A, или b > B, или с > C.
Из этого следует, что, по крайней мере, одно из утверждений истинно:
1) X содержит бесконечное количество векторов, таких, что a > A
2) X содержит бесконечное количество векторов, таких, что b > B
3) X содержит бесконечное количество векторов, таких, что с > C

Допустим, справедливо утверждение 1.
Тогда из векторов, удовлетворяющих условию a > A, можно выделить бесконечную подпоследовательность Y векторов (a',b',c').
Для любого n > 0:
a'n > A
следовательно,
либо b'n < B ,
либо c'n < C

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

Cуществует лишь конечное число различных пар (b',c'), таких, что b' < B, c' < C.
Поэтому, Y содержит бесконечное количество векторов, таких, что или b' < B, или c' < C.
Из этого следует, что, по крайней мере, одно из утверждений истинно:
4) Y содержит бесконечное количество векторов, таких, что b' > B
5) Y содержит бесконечное количество векторов, таких, что с' > C

Допустим, справедливо утверждение 4.
Тогда из векторов, удовлетворяющих условию b' > B, можно выделить бесконечную подпоследовательность Z векторов (a",b",c").
Для любого n > 0:
a"n > A
b"n > B
следовательно,
c"n < C

Также очевидно, что все значения с" последовательности Z должны быть различными.
Но это невозможно, т.к. существует лишь конечное число натуральных чисел c" < C.

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

11. Докажите, что для любых трех бесконечных последовательностей натуральных чисел
a1, a2, ... , an, ...
b1, b2, ... , bn, ...
c1, c2, ... , cn, ...
найдутся такие номера p и q, что
ap >=aq,
bp >=bq,
cp >=cq
(вторая буква — индекс)

12. В прямоугольник со сторонами 20х25 бросают 120 квадратов со стороной 1. Докажите, что в прямоугольник можно поместить круг диаметра 1, не пересекающийся ни с одним из квадратов.

7. см. 9 класс

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

6б. Расстояние от фиксированной точки Р плоскости до двух вершин А, В равностороннего треугольника АВС равны АР=2, ВР=3. Определить, какое максимальное значение может иметь расстояние СР.

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

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

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

Здравствуйте, 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...
При каждом шаге, очевидно, свойство неубывания для предыдущих последовательностей не нарушается.
В конце концов мы получим последовательности, для которых справедливо Сильное Утверждение.
Всё. Правильно?

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

LCR>Ответ: минимальное расстояние = 1.
А максимальное = 5.

Кошмар, у меня глюки я искал минимальное расстояние вместо максимального. Максимальное расстояние естественно равно 5, оно достигается тогда, когда точка C расположена в самой дальней точке своей окружности. Максимальный треугольник показан красным.

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

Les>6б. Расстояние от фиксированной точки Р плоскости до двух вершин А, В равностороннего треугольника АВС равны АР=2, ВР=3. Определить, какое максимальное значение может иметь расстояние СР.

Ответ: минимальное расстояние = 1.

Доказательство. Рассмотрим две концентрические окружности: окружность радиуса 3, окружность радиуса 2, центр окружностей — точка P. Понятно, что точка B лежит где-то на первой окружности, точка A — где-то на второй окружности.
Без ограничения общности можно считать, что точка B зафиксирована.

Так вот: ГМТ вершины C этого треугольника образует окружность радиуса 2, если точка A пробегает по всем точкам своей окружности. Вот именно этот тезис и есть ключевая точка в решении этой задачи.

Найдём точку Q так, чтобы треугольник PQB был равносторонний. Треугольники APB и CQB равны, поскольку BA=BC (треугольник ABC равносторонний), BP=BQ (треугольник PQB равносторонний), углы ABP=CBQ поскольку они являются
углами между сторонами равных углов (в нашем случае углов в 60 градусов при вершине B треугольников PBQ и ABC). Поскольку треугольники равны, то PA=QC. То есть при любом положении точки A на своей окружности точка C
будет на одном и том же расстоянии от точки Q, то есть образует окружность.

Тот самый минимальный треугольник изображён красным, окружность радиуса 3 я не рисовал, чтобы не загромождать чертёж.

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

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

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

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

Les>6б. Расстояние от фиксированной точки Р плоскости до двух вершин А, В равностороннего треугольника АВС равны АР=2, ВР=3. Определить, какое максимальное значение может иметь расстояние СР.

Метод прост: находится растояние CP в зависимости от угла APB смотрим его на промежутке от 0 до 180 градусов.
Формула получилась такой =) r = sqrt(17-12*cos(j)-4*sqrt(13-12*cos(j))*cos(pi/3+asin(3*sin(j)/sqrt(13-12*cos(j)))));
Ищем производную приравниваем 0 и находим максимум. Сделать это мне не удалось. Но путем написания простенькой проги удалось показать что максимум равен 5 когда угол ABP равен 120 градусов длиннаа стороны равносторонненго треугльника равна sqrt(19)

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

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

Les>>12. В прямоугольник со сторонами 20х25 бросают 120 квадратов со стороной 1. Докажите, что в прямоугольник можно поместить круг диаметра 1, не пересекающийся ни с одним из квадратов.

A>Если круг пересекается с квадратом, то его центр попадает в Round Rectangle 2х2, который помещается в квадрат 2х2.
A>Т.о. если после покрытия квадратами и расширения их соответствующим образом до размера 2х2 остается свободное место, то помещаем в него центр круга, который не будет пересекаться ни с одним из квадратов.
A>Площадь квадратов 2х2: 120*4=480.
A>Площадь всего прямоугольника 25*20=500.
A>Т.е. свободное место останется.

На самом деле площадь расширенного до Round Rectangle квадрата равна S=3+pi/4, 500/S=132,0865..., т.е. можно бросить 132 (!) квадрата, и все равно можно будет разместить крут диаметром 1.
Если же бросить 133 квадрата, то я лично не уверен, что их можно будет разместить так, чтобы их расширения покрывали весь прямоугольник. Не уверен из-за скругленных углов...

Здравствуйте, 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.

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

Задачи Супер! Хотел решить с наскоку не вышло Видно надо над ними много думат

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

Les>12. В прямоугольник со сторонами 20х25 бросают 120 квадратов со стороной 1. Докажите, что в прямоугольник можно поместить круг диаметра 1, не пересекающийся ни с одним из квадратов.

Если круг пересекается с квадратом, то его центр попадает в Round Rectangle 2х2, который помещается в квадрат 2х2.

Т.о. если после покрытия квадратами и расширения их соответствующим образом до размера 2х2 остается свободное место, то помещаем в него центр круга, который не будет пересекаться ни с одним из квадратов.
Площадь квадратов 2х2: 120*4=480.
Площадь всего прямоугольника 25*20=500.
Т.е. свободное место останется.

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

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

Les>>12. В прямоугольник со сторонами 20х25 бросают 120 квадратов со стороной 1. Докажите, что в прямоугольник можно поместить круг диаметра 1, не пересекающийся ни с одним из квадратов.

A>Если круг пересекается с квадратом, то его центр попадает в Round Rectangle 2х2, который помещается в квадрат 2х2.
[ картинка ]
A>Т.о. если после покрытия квадратами и расширения их соответствующим образом до размера 2х2 остается свободное место, то помещаем в него центр круга, который не будет пересекаться ни с одним из квадратов.
A>Площадь квадратов 2х2: 120*4=480.
A>Площадь всего прямоугольника 25*20=500.
A>Т.е. свободное место останется.

А если некоторые квадраты расположены под углом 45?

Тогда, по грубой оценке сверху, надо брать объемлющие квадраты стороной 2*sqrt(2). И тогда свободного места не остаётся...

(Извиняюсь)

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

M>А если некоторые квадраты расположены под углом 45?

M>Тогда, по грубой оценке сверху, надо брать объемлющие квадраты стороной 2*sqrt(2). И тогда свободного места не остаётся...

M>(Извиняюсь)

Еще раз...

Кидаем 120 квадратов.
Расширяем их так, как они лежат.
Размещаем произвольно круг.
Если он пересекается с квадратом, то его центр попадает в расширение соответствующего квадрата. Если же его центр лежит вне всех расширений, то он не пересекается ни с одним квадратом.
Площадь всех расширений максимум 480 (скругленных — 360+30pi). Площадь всего прямоугольника 500.

P.S. Выше я отметил, что подобное доказательство проходит и для 132 квадратов!
P.P.S. Либо я прав, либо конкретно заблуждаюсь. Но, как говорил товарищ Сухов, "Это вряд ли"...

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

A>Еще раз...

A>Кидаем 120 квадратов.
A>Расширяем их так, как они лежат.
A>Размещаем произвольно круг.
A>Если он пересекается с квадратом, то его центр попадает в расширение соответствующего квадрата. Если же его центр лежит вне всех расширений, то он не пересекается ни с одним квадратом.
A>Площадь всех расширений максимум 480 (скругленных — 360+30pi). Площадь всего прямоугольника 500.

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

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

Пара мелких придирок:

LCR>Ответ: минимальное расстояние = 1.

Требовалось найти макс. расстояние (впрочем, оно теперь очевидно)

LCR>То есть при любом положении точки A на своей окружности точка C
LCR>будет на одном и том же расстоянии от точки Q,
LCR>то есть образует окружность.
... или фрагмент окружности

LCR>
Не нарисовался твой чертежик
LCR>Тот самый минимальный треугольник изображён красным, окружность радиуса 3 я не рисовал, чтобы не загромождать чертёж.

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

A>Если круг пересекается с квадратом, то его центр попадает в Round Rectangle 2х2, который помещается в квадрат 2х2.
A>
A>Т.о. если после покрытия квадратами и расширения их соответствующим образом до размера 2х2 остается свободное место, то помещаем в него центр круга, который не будет пересекаться ни с одним из квадратов.
A>Площадь квадратов 2х2: 120*4=480.
A>Площадь всего прямоугольника 25*20=500.

Вот только центр круга должен отстоять от края по крайней мере на 1. Так что не
25*20=500, а
23*18=414

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

Les>Не нарисовался твой чертежик
Или опять прокся, или, что менее вероятно, сервер rsdn. Чертёжик можно увидеть в моём следующем сообщении, где я наконец даю ответ к этой задаче здесь

Автор: LCR
Дата: 26.05.03

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

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, Вы писали:

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.

P.S. Мне с самого начала казалось странным, что в задаче на столько "заложилсь" — вместо 132 написали 120. Ну я, естественно, подумал, что это, должно быть, сделано для того, чтобы школьники не возились с pi и не оценивали 30pi, а взяли квадрат 2х2. "О, боже мой, как ошибалась я!"

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

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

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

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

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

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

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

Здравствуйте, 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).

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

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