2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

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



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Задачка: несчётное множество букв Т на плоскости
Сообщение04.10.2005, 11:44 
Задачка: Доказать, что на плоскости нельзя разместить несчётное множество непересекающихся букв Т.
Буква Т- два перпендикулярных отрезка, один выходит из середины другого. Длины могут быть любые.

  
                  
 
 Re: Задачка:несчётное множество букв Т на плоскости
Сообщение04.10.2005, 12:22 


15/05/05
33
Нужно взять 3 точки с рациональными координатами и построить инъекцию букв Т на множество этих точек

 Профиль  
                  
 
 
Сообщение04.10.2005, 13:16 
Как? Можно поподробнее?

  
                  
 
 
Сообщение04.10.2005, 14:57 
Аватара пользователя


20/08/05
20
не ждали
Хм, а если рассмотреть отрезок [0,1] и на нем такие буквы Т: сначала берем точки 1 и 0, между ними можно вставить одну, а значит, 2 точки с иррациональными координатами, на них строим верхнюю перекладину буквы Т, в середине строим еще одну какую-то точку и строим ножку буквы Т(такая точка всегда найдется в силу усиленной плотности), далее между, скажем, самой левой иррациональной точкой и точкой 0 впихиваем еще 2 иррациональных точки и на них строим еще букву Т, и так далее, причем мы всегда сможем построить еще одну букву Т слева от 0 и не достигнуть его! Это я к тому, что как раз можно построить несчетное количество букв Т! Если что не так, поправьте плз :oops:

 Профиль  
                  
 
 
Сообщение04.10.2005, 15:55 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Zadov писал(а):
Хм, а если рассмотреть отрезок [0,1] и на нем такие буквы Т


Таким образом получается счетное число букв. Вы используете только счетное количество иррациональных чисел. Каждой построенной таким способом букве T соответствует некоторое рациональное число (любое лежащее на перекладине), причем разным буквам будут соответствовать разные числа. Значит, таких букв не более чем счетное число.

 Профиль  
                  
 
 ТТТ
Сообщение04.10.2005, 16:02 
Да, помнится, решал эту задачу лет так 27 назад - будучи матучеником маткласса. Попытаюсь вспомнить. Решение таково:

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

Проводим окружность диаметром d/2, - нет, лучше d/10 :), - с центром в вершине. Тогда отрезки, выходящие из вершины буквы, делят соотв. круг на 3 области (сектора).

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

Таким образом, мы построили отображение мн-ва букв Т во мн-во троек точек плоскости с рациональными координатами.

Теперь докажем, что никакие две различные буквы не могут отображаться на одну и ту же тройку точек. Это тот самый момент в доказательстве, где требуется максимальная аккуратность. Потому как про "три рациональные точки" помнят все, кто когда-либо сталкивался с этой задачей, а вот этот конкретный момент - немногие. Рассмотрим произвольную пару букв: T и T'. Пусть радиус круга для буквы Т' больше либо равен радиусу круга для буквы T. Рассмотрим 2 случая:

1. Вершина буквы T' лежит внутри круга буквы T. Но тогда в силу предположения d(T')>=d(T) все три "конца" буквы T' лежат вне этого круга. Из непересечения букв T и T' очевидно, что все три точки пересечения отрезков буквы T' с окружностью для T лежат в одном из трех секторов, на который отрезки буквы T делят соотв. круг. Но из этого следует, что, как минимум, 2 из 3 точек, соответствующих букве T', лежат в одном из этих секторов либо вообще вне круга. Но все три точки, соотв. букве T, лежат в _разных_ секторах _внутри_ круга. Следовательно, тройки точек для букв T' и T никак не могут совпадать.

2. Случай, когда вершина буквы T' лежит вне или на границе круга буквы T, рассматривается аналогично.

Таким образом, мы построили биекцию между мн-вом букв T на плоскости и некоторым подмножеством троек точек с рациональными координатами. Последнее конечно либо счетно, следовательно, мн-во букв T на плоскости также не более чем счетно.

  
                  
 
 
Сообщение04.10.2005, 16:08 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Вроде получается так. Выберем произвольную точку слева от ножки буквы T и под перекладинкой (т.е. попадающую внутрь левой части прямоугольника, в который вписана буква). Аналогичным образом выберем произвольную точку из правой части. Важно, что точки берутся именно в таком порядке: сначала левая, потом правая, если смотреть на букву "снизу". По-моему очевидно, что та же пара точек не может соответствовать другой букве Т, иначе эти буквы пересекаются. А значит, инъекция на счетное множество построена.

 Профиль  
                  
 
 ТТ
Сообщение04.10.2005, 17:59 
2PAV

Та ни, так нэ пойдэ.

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

А вообще, не надо изобратеть велосипед. Все уже давно изобретено.

  
                  
 
 
Сообщение04.10.2005, 19:42 


04/10/05
272
ВМиК МГУ
А есть такое простое решение.
Будем кодировать букву "T" вектором t=(xc,yc,xd,yd), где (xc,yc)-координаты центра горизонтальной палки, а (xd,yd) - вектор, задающий вертикальную палку (xd=xe-xc, yd=ye-yc, где xe,ye-координаты конца вертикальной палки). "Вертикальная" и "горизонтальная" - это в смысле традиционного написания буквы без поворотов (чтобы понятно было о чем речь идет).
Легко доказать, что для любого вектора t1, соответствующего некоторой букве "T" существует такое eps>0, что для любого вектора t2 такого, что |t1-t2|<=eps, соответствующие t1 и t2 буквы "T" пересекаются (|| - евклидовая норма). Т.е., если буквы "T" очень похожи по расположению, то они пересекаются (нужно просто случаи взаимного положения разобрать, если непонятно, могу написать).
Таким образом, если буквы нашего множества не пересекаются, то в пространстве R^4 существует несчетное множество непересекающихся шаров (вокруг каждого t1 шар радиуса eps/2). А такое невозможно (ну хотя бы потому, что любой шар содержит рациональную точку).

 Профиль  
                  
 
 Re: ТТ
Сообщение04.10.2005, 21:30 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Бывший вундеркинд писал(а):
2PAV

Та ни, так нэ пойдэ.

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

А вообще, не надо изобратеть велосипед. Все уже давно изобретено.


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

 Профиль  
                  
 
 
Сообщение04.10.2005, 22:55 


16/09/05
6
Москва
Да... было дело под Полтавой... давно, правда :roll:

Слушай сюда:
Очевидно, что эти буквы Т легко закодировать точками n-мерного пространства, где n - что-то между 3 и 6 (ну, понятно, не будем уж...) :lol:
Остается показать, что любое множество непересекающихся (на плоскости)букв состоит из изолированных точек в пространстве представления,
а это очевидно, так как "близкие в пространстве представления" буквы должны иметь не только близкие "центры", но и близкорасположенные... э... планки "почти одинаковой" длины

Правда как это (то, что очевидно :wink: ) строго доказать... :roll: но тоже, наверное, можно :wink:

 Профиль  
                  
 
 Re: ТТ
Сообщение05.10.2005, 08:55 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
PAV писал(а):
Бывший вундеркинд писал(а):
2PAV

Та ни, так нэ пойдэ.

Следовательно, ваш метод не подходит.



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


Я был неправ. Не подумал как следует. Действительно, описанным мною способом двумя точками не обойтись, им могут соответствовать одинаковые буквы.

 Профиль  
                  
 
 не уверен
Сообщение05.10.2005, 08:59 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Зомби писал(а):
Да... было дело под Полтавой... давно, правда :roll:

Слушай сюда:
Очевидно, что эти буквы Т легко закодировать точками n-мерного пространства, где n - что-то между 3 и 6 (ну, понятно, не будем уж...) :lol:
Остается показать, что любое множество непересекающихся (на плоскости)букв состоит из изолированных точек в пространстве представления,
а это очевидно, так как "близкие в пространстве представления" буквы должны иметь не только близкие "центры", но и близкорасположенные... э... планки "почти одинаковой" длины

Правда как это (то, что очевидно :wink: ) строго доказать... :roll: но тоже, наверное, можно :wink:


По-моему, так не пойдет. Такое же рассуждение можно провести не для букв Т, а для простых отрезков (или, например, окружностей). А их можно набрать несчетное число без пересечений. Они, конечно, будут "касаться" друг друга, но пересекаться не будут.

 Профиль  
                  
 
 
Сообщение05.10.2005, 14:14 


04/10/05
272
ВМиК МГУ
Я не имел в виду, что такое свойство выполняется для любой геометрической фигуры (если фигуры очень близки по расположению, то они пересекаются). Но оно выполняется для букв "Т".

И доказывается это просто разбиранием нескольких случаев взаимного расположения. Можно просто на бумажке нарисовать, и всё очевидно станет. Но на всякий случай приведу строго формальное доказательство. Во-первых, заметим, что достаточно рассматривать буквы "T" с одним и тем же соотношением длин (сразу не заметил, что соотношения могут быть разными). В каждой букве выберем маленькую "подбукву" с нужным соотношением, останется снова несчетное число непересекающихся букв. Будем считать, что если центр гор. отрезка имеет координаты (xc,yc), а направление вертикального - (xd,yd), то конец вертикального отрезка - (xc+xd; yc+yd), а концы горизонтального - (xc+yd; yc-xd), (xc-yd; yc-xd).

Зафиксируем одну букву "T"-t1. Без ограничения общности можно считать, что для неё xc1=0, yc1=0, xd1=0, yd1=1 (остальные случаи получаются преобразованием подобия). Докажем, что если
|xc|<=0.1, |yc|<=0.1, |xd|<=0.1, 0.9<=yd<=1.1, (*)
то буква t=(xc,yc,xd,yd) пересекает t1.

Для этого рассмотрим три случая:

1) yc<=0. Тогда пересечение вертикальной линии t и горизонтальной t1 имеет координаты
(xc;yc)+(xd;yd)*(-yc/yd)=(xc-xd*yc/yd;0). Ясно, что 0<=-yc/yd<=1/9<1 и -1<-1/9<=xc-xd*yc/yd<=1/9<1 => отрезки действительно пересекаются (а не их продолжения).

2) yc>=0 и xc<=0. Тогда возможны 2 подслучая:
2a) xc*xd+yc*yd>=0. Тогда пересечение горизонтальной линии t и вертикальной t1:
(xc;yc)+(yd;-xd)*(-xc/yd)=(0;(xc*xd+yc*yd)/yd).
Ясно, что 0<=-xc/yd<=1/9<=1 и 0<=xc*xd+yc*yd<=0.12<=1 => пересечение отрезков происходит.
2б) xc*xd+yc*yd<0. Тогда пересечение горизонтальной линии t и горизонтальной линии t1 имеет вид:
(xc;yc)+(yd;-xd)*(yc/xd)=(xc+yc*yd/xd; 0). В этом случае, |xc*xd|>|yc*yd| (т.к. yc,yd>=0) => |yc*yd/xd|<=|xc| => |xc+yc*yd/xd|<=2*|xc|<=0.2<1. Кроме того, |yc/xd|=|yc*yd/xd|/|yd|<=|xc|/|yd|<=2/9<1 => пересечение отрезков происходит.

3) yc>=0 и xc>0. Симметричен случаю 2.

Утверждение доказано. Ясно, что существует шар с центром (0,0,0,1) такой, что для любой точки (xc,yc,xd,yd) этого шара выполнены условия (*). То есть любая буква, соответствующая точке этого шара пересекает букву, соответствующую центру.

 Профиль  
                  
 
 Re: не уверен
Сообщение05.10.2005, 23:23 
PAV писал(а):
Зомби писал(а):
Да... было дело под Полтавой... давно, правда :roll:

Слушай сюда:
Очевидно, что эти буквы Т легко закодировать точками n-мерного пространства, где n - что-то между 3 и 6 (ну, понятно, не будем уж...) :lol:
Остается показать, что любое множество непересекающихся (на плоскости)букв состоит из изолированных точек в пространстве представления,
а это очевидно, так как "близкие в пространстве представления" буквы должны иметь не только близкие "центры", но и близкорасположенные... э... планки "почти одинаковой" длины

Правда как это (то, что очевидно :wink: ) строго доказать... :roll: но тоже, наверное, можно :wink:


По-моему, так не пойдет. Такое же рассуждение можно провести не для букв Т, а для простых отрезков (или, например, окружностей). А их можно набрать несчетное число без пересечений. Они, конечно, будут "касаться" друг друга, но пересекаться не будут.
???
Отрезков, очевидно, можно набрать любое множество
В отличие от букв "Т" - они "рогозливые" :wink: , и при близости параметров обязательно пересекаются
Что означает, что в пространстве представления у каждой из множества непересекающихся на плоскости букв Т есть целая "открытая окрестность" (скажем, шар), не содержащая никаких других букв Т из рассматриваемого множества - это и есть то, что "в пространстве представления (которое, видимо, 6-ти мерное: 2 координаты "центра", и два вектора-плеча) все элементы множества изолированы"
А такие множества в R^n не могут быть более чем счетными
Ну, или, по-другому, не может быть более чем счетным множество непересекающихся шаров в R^n
Это что-то непонятное или неизвестное?
"Этого нельзя" (т.е. требуется "элементарное" доказательство?)

  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 24 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group