Счетность, континуум, биекция, задачи на множества Опции

[Кошка]

Помогите, плиз, решить задачи по доп. главам анализа
1. Док-ть, что кол-во всех пятёрок, которые можно нарисовать на плоскости (непересекающихся, разных размеров), - множество мощности континуума, а множество всех восьмёрок(непересекающихся) не более чем счётно
2. Док-ть, что множество всех непересекающихся следов(множеств трёх отрезков из одной точки) не более чем счётно
3. Пусть r1=1, r2n=rn +1, r(2n+1)=1/r2n, функция f из n в rn – биекция. Доказать, что функция f является биекцией из множества натуральных в множество рациональных чисел.

[Lapp]

Кошка,
не надо постить свои задачи в чужие темы - открывай новые.

Задачи хорошие, ответы будут

[Lapp]

1. Док-ть, что кол-во всех пятёрок, которые можно нарисовать на плоскости (непересекающихся, разных размеров), - множество мощности континуума,

Вопрос по условию: пятерки должны быть подобны между собой?
Если да, то при определенной форме пятерки доказательство, боюсь, невозможно. Поскольку в условии не определено точно, что есть пятерка, то будем считать, что они не обязательно должны быть подобны - главное, чтоб читались.

Тогда решение состоит в построении примера, и пример я приведу для пятерок вполне определенной формы, которые все же подобны между собой (и даже равны).

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

Если касательная наклонена в другую сторону или горизонтальна, то такое решение не годится, но непольшой коррекцией формы мы все же можем добиться набора пятерок, которые будут вложены друг в друга достаточно плотно:

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

а множество всех восьмёрок(непересекающихся) не более чем счётно

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

Во-первых разобъем все действительные числа на полуинтервалы (1^n, 1^(n+1)], где n - любое целое число. Полуинтервал, в записи которого стоит число n, будем называть n-ым интервалом.
Рассмотрим все восьмерки, у которых
а) площадь находится в пределах n-ого интервала квадратных метров (далее единицы измерения опускаю);
б) диаметр находится в пределах к-го интервала.
Будем называть такие восьмерки (n,k)-восьмерками.

Рассмотрим круг с центром в начале координат и радиусом равным максимальному диаметру (то есть 2^(k+1) ). В этот круг целиком может поместиться никак не более 2*S/(2^n) (n,k)-восьмерок (включая написанные внутри других таких же восьмерок; S - площадь круга), то есть конечное число.

Теперь учтем те восьмерки, которые не вошли в круг полностью. Для этого окружим круг кольцом ширины 2^(k+1). Все они окажутся внутри большого круга, ограниченного внешней границей кольца. Это означает, что их тоже конечное число.

Теперь увеличим радиус малого круга вдвое и повторим рассуждения. Таким образом, образовав бесконечную последовательность кругов, мы можем пересчитать все (n,k)-восьмерки. Тем самым мы доказали, что их множество счетно.

Осталось только сказать, что количество классов (n,k)-восьмерок тоже счетно. А счетное объединение счетных множество также счетно. Тем самым задача о восьмерках решена.


Задача о птичьих следах решается аналогично, с небольшой модификацией. Я напишу решение завтра (если никто не опередит ).

[Michael_Rybak]

Про восьмерки есть такое решение: поскольку множество рациональных чисел - счетно, то и множество точек с рациональными координатами - счетно, а, значит, счетно и множество *пар* точек с рациональными координатами. Выберем в каждом кругу восьмерки по точке с рац. координатами, и поставим эту пару ей в соответствие. Поскольку восьмерки не пересекаются, каждая пара может встретиться не больше одного раза.

Про птичьи следа - точно так же, только не пары, а тройки (соединяем концы отрезков, получаем треугольник, разбитый на три меньших следом. В каждом из меньших треугольников берем по рациональной точке). Хотя, в принципе, можно и двойками обойтись.



Сообщение отредактировано: Michael_Rybak - 2.10.2006 18:24

[Michael_Rybak]

3. Пусть r1=1, r2n=rn +1, r(2n+1)=1/r2n, функция f из n в rn – биекция. Доказать, что функция f является биекцией из множества натуральных в множество рациональных чисел.

Уточнение - "в множество *положительных* рациональных чисел*

Нужно показать, что каждое рациональное число встретится в последовательности ri, причем ровно 1 раз.

Эту последовательность удобно изобразить двоичным деревом:

Код

|        1
|      /   \
|     2      1/2
|    / \     / \
|   3  1/3  3/2  2/3
| / \  / \  / \  / \
|.....................

Теперь можем говорить об отцах и детях: у каждого числа, кроме 1, ровно 1 отец. У каждого числа ровно 2 сына.

Рассмотрим число a/b. Пусть х - его отец. Тогда либо x+1=a/b, либо 1/(x+1) = a/b, откуда x=(a-b)/b, либо x=(b-a)/a. Поскольку все числа, очевидно, положительные, один из вариантов возможного х отпадает, и остается другой, который поднимает нас на 1 уровень вверх по дереву. Продолжая подниматься, мы всегда приходим к единице, причем единственным способом. Процесс всегда завершится, потому что большее из числителя/знаметаля постоянно уменьшается.

[Lapp]

каждая пара может встретиться не больше одного раза.

Согласен. Ключ к решению - именно двусвязность, мое решение учитывает ее довольно сложным образом..

Про птичьи следа - точно так же, только не пары, а тройки (соединяем концы отрезков, получаем треугольник, разбитый на три меньших следом. В каждом из меньших треугольников берем по рациональной точке). Хотя, в принципе, можно и двойками обойтись.

Боюсь, не годится.. Вот два следа и три рациональных точки, характеризующих каждый из них.

[Michael_Rybak]

Да, вы правы. Я тут домучал до решения вроде, но даже не буду постить, т.к. так же изящно, как с восьмерками, не получилось (пока?).

[Lapp]

Да, вы правы. Я тут домучал до решения вроде, но даже не буду постить, т.к. так же изящно, как с восьмерками, не получилось (пока?).

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

PS
Спасибо за вклад в раздел! +1.

[Michael_Rybak]

Но если ничего лучшего все же не получится

Получилось!

Во-первых, будем рассматривать только следы, у которых все три отрезка равны - действительно, если бы удалось расположить континуум произвольных следов, то каждый след можно было бы обрезать до наименьшей из трех сторон, и получить континуум равносторонних следов. Поэтому, доказав счетность множества тех, покажем и счетность множества других.

Будем называть длину отрезков радиусом.

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

А теперь зафиксируем радиус r, и применим критерий, который я приводил - три точки, по одной - в каждом треугольнике. Легко убедиться, что теперь Ваш пример (и аналогичные) построить нельзя.

Значит, множество равносторонних следов одинакового рационального радиуса не более чем счетно, а, поскольку рациональных чисел - счетное количество, то и соответствующее декартово произведение (т.е. объединение следов всех радиусов) тоже не более чем счетно.

[Lapp]

Да, теперь лучше .
Единственное мое замечание состоит в том, что вместо фразы:

Легко убедиться, что теперь Ваш пример (и аналогичные) построить нельзя.

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

Мое решение в чем-то похоже (начало), в чем-то - нет (геометрия).
Оно тоже использует усечение лучей до минимального. Потом я использовал разбиение на классы, как в решении для восьмерок - согласен, что усечение до рационального радиуса проще и красивее.
Будем характеризовать каждый след его центром.
Далее я использовал то свойство, что один из трех углов должен не превышать 120 градусов. Рассмотрим следы с близкими минимальными углами (аналогично классам в восьмерках, усечение угла до рационального, боюсь, тут не катит). Назовем это приближенное значение а. Поскольку второй (по величине) угол (назовем b) больше a, их сумма двух a.

Таким образом, как видно из картинки, мы не можем расположить синий след (то есть его центр) ближе к черному следу, чем определяет некая граница (обозначена красным пунктиром). Значит, рядом с каждым (r,a)-следом находится некая "мертвая зона" фиксированной площади, в которой нету больше (r,a)-следов. Дальше понятно, полагаю..

[Michael_Rybak]

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

Соглашусь

Определимся более четко с тем, что такое след (равносторонний, с рациональным радиусом). След задается шестеркой (x, y, r, a1, a2, a3), где ai - углы, определяющие ветки. Из всех шестерок выбираем такую, в которой a1<a2<a3

В соответствие следу (x, y, r, a1, a2, a3) поставим шестерку рациональных чисел (x1, y1, x2, y2, x3, y3). Точку (x1, y1) выберем из сектора, ограниченного отрезками a1 и a2, причем не дальше от центра, чем на r/200. Аналогично выберем две другие точки из двух других секторов.

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

Теперь покажем, что двум непересекающимся следам с одинаковым радиусом не может соответствовать одна и та же шестерка.

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

Извините что без рисунков, медленно они у меня получаются :-/

[Lapp]

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

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

- ты настаиваешь?.. (руки чешутся нарисовать, но если ты предпочитаешь устно.. )

[Michael_Rybak]

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

[Lapp]

Вот елки

O'kay, принято

[Кошка]

Огромное спасибо за помощь!

[Гость]

помогите пожалуйста с вопросом-как доказать,что множество всех прямых на плоскости -континуально,и ещё:
можно ли расположить континуум непересекающихся контуров выпуклых равносторонних шестиугольников со стороной 1 на плоскости???

[andriano]

0. Насколько мне известно, настоятельно рекомендуется задавать новые вопросы в новых темах.
1. Свести к любому одномерному случаю: множество прямых, проходящих через одну точку либо параллельных прямых, проходящих через отрезок, после чего воспроизвести одномерное доказательство либо просто сослаться на него.
2. Нет.

[Lapp]

М

Гость, пожалуйста, зарегистрируйся и создавай свои собственные темы.

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

А как сводить? Это еще вопрос..
Все проще, мне кажется. Прямая задается уравнением ax+by=0. Числа a и b - действительные. Их можно интерперетировать как координаты в двумерном пространстве, а количество точек в нем - континуум.
[приведенное решение не совсем верное, см. исправление в посте #37]

2. Нет.

andriano необычно для него краток )).
Если речь идет о выпуклых шестиугольниках, то все совсем просто. Как известно, если выпуклый многоугольник А вложен в выпуклый многоугольник В, то периметр А меньше периметра В (доказательство могу привести). Тут же все периметры равны - следовательно, вложенности быть не должно. Далее, при ненулевой площади всегда можно найти внутри фигуры точку с рациональными координатами. Ставим эту точку в соответствие шестиугольнику - и все пересчитано.

Сообщение отредактировано: Lapp - 9.01.2010 5:20

[Гость]

спс!!!

[andriano]

А как сводить?

Было предложено 2 варианта.

Все проще, мне кажется. Прямая задается уравнением ax+by=0. Числа a и b - действительные. Их можно интерперетировать как координаты в двумерном пространстве, а количество точек в нем - континуум.

Можно и так, но это "двумерные" варианты. Предложенные мною варианты при данном подходе соответствуют b=0 и a=const соответственно.
Хотя бы для того, чтобы не доказывать, что квадрат континуума есть континуум.

andriano необычно для него краток )).

Я ответил на поставленный вопрос.
Если бы требовалось доказательство, я бы предложил выбрать один из многоугольников и перенумеровать остальные по спирали от него.