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>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 невозможно.
Здравствуйте, 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). И тогда свободного места не остаётся...
Здравствуйте, 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 квадрата, то я лично не уверен, что их можно будет разместить так, чтобы их расширения покрывали весь прямоугольник. Не уверен из-за скругленных углов...
Здравствуйте, 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.
Что-то никакой реакции — не убедил?
Похоже это на правду в конце-концов или нет? Аж самому интересно стало!!!
Здравствуйте, 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 я не рисовал, чтобы не загромождать чертёж.
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)
Здравствуйте, LCR, Вы писали:
LCR>Ответ: минимальное расстояние = 1.
А максимальное = 5.
Кошмар, у меня глюки я искал минимальное расстояние вместо максимального. Максимальное расстояние естественно равно 5, оно достигается тогда, когда точка C расположена в самой дальней точке своей окружности. Максимальный треугольник показан красным.
Здравствуйте, 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.
Пара мелких придирок:
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. Чертёжик можно увидеть в моём следующем сообщении, где я наконец даю ответ к этой задаче здесь
Здравствуйте, 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.
Здравствуйте, 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.
Здравствуйте, 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 с исходным.
Не понял Почему эквивалентна?
Видно надо над ними много думат 
Apapa.gif)
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
я искал минимальное расстояние вместо максимального. Максимальное расстояние естественно равно 5, оно достигается тогда, когда точка C расположена в самой дальней точке своей окружности. Максимальный треугольник показан красным.
