IPB
ЛогинПароль:

> Компиляция правил для данного раздела

1. Заголовок темы должен быть информативным. В противном случае тема закрывается и удаляется ...
2. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
3. Одна тема - один вопрос (задача)
4. Спрашивайте и отвечайте четко и по существу!!!

3 страниц V  1 2 3 >  
 Ответить  Открыть новую тему 
> Счетность, континуум, биекция, задачи на множества
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 9
Пол: Женский
Реальное имя: Светлана

Репутация: -  0  +


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


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Кошка @ 29.09.2006 4:56) *

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

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

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

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

Цитата(Кошка @ 29.09.2006 4:56) *

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

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

Во-первых разобъем все действительные числа на полуинтервалы (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)-восьмерок тоже счетно. А счетное объединение счетных множество также счетно. Тем самым задача о восьмерках решена.


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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

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



Сообщение отредактировано: Michael_Rybak -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата(Кошка @ 29.09.2006 3:56) *

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 уровень вверх по дереву. Продолжая подниматься, мы всегда приходим к единице, причем единственным способом. Процесс всегда завершится, потому что большее из числителя/знаметаля постоянно уменьшается.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Michael_Rybak @ 2.10.2006 15:16) *

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

Согласен. Ключ к решению - именно двусвязность, мое решение учитывает ее довольно сложным образом..
Цитата(Michael_Rybak @ 2.10.2006 15:16) *

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

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


Эскизы прикрепленных изображений
Прикрепленное изображение

--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Да, вы правы. Я тут домучал до решения вроде, но даже не буду постить, т.к. так же изящно, как с восьмерками, не получилось (пока?).
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Michael_Rybak @ 2.10.2006 16:42) *

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

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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата(lapp @ 3.10.2006 1:34) *

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


Получилось! smile.gif

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

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

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

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

Значит, множество равносторонних следов одинакового рационального радиуса не более чем счетно, а, поскольку рациональных чисел - счетное количество, то и соответствующее декартово произведение (т.е. объединение следов всех радиусов) тоже не более чем счетно.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Да, теперь лучше smile.gif.
Единственное мое замечание состоит в том, что вместо фразы:
Цитата(Michael_Rybak @ 3.10.2006 18:34) *
Легко убедиться, что теперь Ваш пример (и аналогичные) построить нельзя.
- хотелось бы видеть некое геометрическое рассуждение с доказательством, а не ссылку на отсутствие гипотетических примеров. Думаю, ты согласишься.

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата(lapp @ 4.10.2006 5:58) *

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


Соглашусь smile.gif

Определимся более четко с тем, что такое след (равносторонний, с рациональным радиусом). След задается шестеркой (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 друг от друга. А из этого следует, что каждый из следов обязательно полностью лежит в одной из граней другого. А это значит, с учетом близости центров, что из трех точек, которые мы поставим в соответствие одному следу, как минимум две будут лежать в одной грани другого. Поэтому совпадение шестерок невозможно.

Извините что без рисунков, медленно они у меня получаются :-/
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Ты согласен, что в цепочке рассуждений, являющих доказательство, все промежуточные выводы должны быть верными? smile.gif
Цитата(Michael_Rybak @ 4.10.2006 13:00) *

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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Вот елки smile.gif
Ну чуть-чуть вылазить может smile.gif. Но у нас ведь точки очень близко к центру, поэтому следующее за этим утверждение остается правильным - две из трех точек попадут в эту грань.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Michael_Rybak @ 4.10.2006 16:27) *

Вот елки smile.gif

O'kay, принято smile.gif


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15





Группа: Пользователи
Сообщений: 9
Пол: Женский
Реальное имя: Светлана

Репутация: -  0  +


Огромное спасибо за помощь! respect2.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Гость






помогите пожалуйста с вопросом-как доказать,что множество всех прямых на плоскости -континуально,и ещё:
можно ли расположить континуум непересекающихся контуров выпуклых равносторонних шестиугольников со стороной 1 на плоскости??? blink.gif
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Гуру
*****

Группа: Пользователи
Сообщений: 1 168
Пол: Мужской
Реальное имя: Сергей Андрианов

Репутация: -  28  +


0. Насколько мне известно, настоятельно рекомендуется задавать новые вопросы в новых темах.
1. Свести к любому одномерному случаю: множество прямых, проходящих через одну точку либо параллельных прямых, проходящих через отрезок, после чего воспроизвести одномерное доказательство либо просто сослаться на него.
2. Нет.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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


Цитата(andriano @ 4.01.2010 20:45) *
1. Свести к любому одномерному случаю: множество прямых, проходящих через одну точку либо параллельных прямых, проходящих через отрезок, после чего воспроизвести одномерное доказательство либо просто сослаться на него.
А как сводить? Это еще вопрос..
Все проще, мне кажется. Прямая задается уравнением ax+by=0. Числа a и b - действительные. Их можно интерперетировать как координаты в двумерном пространстве, а количество точек в нем - континуум.
[приведенное решение не совсем верное, см. исправление в посте #37]

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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Гость






спс!!! yes2.gif
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


Гуру
*****

Группа: Пользователи
Сообщений: 1 168
Пол: Мужской
Реальное имя: Сергей Андрианов

Репутация: -  28  +


Цитата(Lapp @ 5.01.2010 0:36) *
А как сводить?
Было предложено 2 варианта.
Цитата
Все проще, мне кажется. Прямая задается уравнением ax+by=0. Числа a и b - действительные. Их можно интерперетировать как координаты в двумерном пространстве, а количество точек в нем - континуум.
Можно и так, но это "двумерные" варианты. Предложенные мною варианты при данном подходе соответствуют b=0 и a=const соответственно.
Хотя бы для того, чтобы не доказывать, что квадрат континуума есть континуум.
Цитата

andriano необычно для него краток )).
Я ответил на поставленный вопрос.
Если бы требовалось доказательство, я бы предложил выбрать один из многоугольников и перенумеровать остальные по спирали от него.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

3 страниц V  1 2 3 >
 Ответить  Открыть новую тему 
2 чел. читают эту тему (гостей: 2, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 22:22
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name