Треп о математике 2.2

Sergei Nickolaev написал(а) к All в Apr 23 15:10:22 по местному времени:

Привет, All!

В этом разделе задачки будут интереснее :-)

Счетные множества.

Множество называется счётным, если оно равномощно множеству N натуральных чисел, то есть, если его можно представить в виде {x0, x1, x2, . . . } (здесь xi - элемент, соответствующий числу i; соответствие взаимно однозначно, так что все xi различны).
Например, множество целых чисел Z счётно, так как целые числа можно расположить в последовательность 0, 1, -1, 2, -2, 3, -3, . . .

Несколько утверждений:
1. Подмножество счётного множества конечно или счётно.
Пусть B - подмножество счётного множества A. Представим множество A как {a0, a1, a2, . . . }. Выбросим из последовательности a0, a1, . . . те члены, которые не принадлежат B (сохраняя порядок оставшихся). Тогда оставшиеся члены образуют либо конечную последовательность (и тогда B конечно), либо бесконечную (и тогда
B счётно).

2. Всякое бесконечное множество содержит счётное подмножество.
Пусть A бесконечно. Тогда оно непусто и содержит некоторый элемент b0. Будучи бесконечным, множество A не исчерпывается элементом b0 - возьмём какой-нибудь другой элемент b1, и т. д.
Получится последовательность b0, b1, . . . ; построение не прервётся ни на каком шаге, поскольку A бесконечно. Теперь множество B = {b0, b1, . . . } и будет искомым счётным подмножеством. (Заметим, что B вовсе не обязано совпадать с A, даже если A счётно.)

3. Объединение конечного или счётного числа конечных или счётных множеств конечно или счётно.
Пусть имеется счётное число счётных множеств A1,A2, . . .
Расположив элементы каждого из них слева направо в последовательность (Ai = {ai0, ai1, . . . }) и поместив эти последовательности друг под другом, получим таблицу
a00 a01 a02 a03 . . .
a10 a11 a12 a13 . . .
a20 a21 a22 a23 . . .
a30 a31 a32 a33 . . .
. . . . . . . . . . . . . . .
Теперь эту таблицу можно развернуть в последовательность, например, проходя по очереди диагонали:
a00, a01, a10, a02, a11, a20, a03, a12, a21, a30, . . .
Если множества Ai не пересекались, то мы получили искомое представление для их объединения. Если пересекались, то из построенной последовательности надо выбросить повторения.
Если множеств конечное число или какие-то из множеств конечны, то в этой конструкции части членов не будет - и останется либо конечное, либо счётное множество.

Задачка 1:
Описанный проход по диагоналям задаёт взаимно однозначное соответствие между множеством всех пар натуральных чисел (которое обозначается N x N) и N.
Это соответствие задается простой формулой: многочленом второй степени с рациональными коэффициентами). Найдите этот многочлен.

Ещё несколько примеров счётных множеств:
1. Множество Q рациональных чисел счётно. В самом деле, рациональные числа представляются несократимыми дробями с целым числителем и знаменателем. Множество дробей с данным знаменателем счётно, поэтому Q представимо в виде объединения счётного числа счётных множеств.
2. Множество N^k, элементами которого являются наборы из k натуральных чисел, счётно. Это легко доказать индукцией по k.
Задачка 2: докажите :-)
3. По тем же причинам произведение двух счётных множеств A x B (множество пар, в которых 1-й элемент из A, 2-й элемент - из B) - счетно. Это же относится к произведению конечного количества счетных множеств (это произведение - упорядоченные наборы, в которых очередной элемент принадлежит очередному множеству).
4. Множество всех конечных последовательностей натуральных чисел счётно. В самом деле, множество всех последовательностей данной длины счётно (как мы только что видели), так что интересующее нас множество разбивается на счётное число счётных множеств.
5. В предыдущем примере не обязательно говорить о натуральных числах - можно взять любое счётное (или конечное) множество. Например, множество всех текстов, использующих русский алфавит (такой текст можно считать конечной последова-
тельностью букв, пробелов, знаков препинания и т. п.), счётно; то же самое можно сказать о множестве (всех мыслимых) компьютерных программ и т. д.
6. Число называют алгебраическим, если оно является корнем ненулевого многочлена с целыми коэффициентами. Множество алгебраических чисел счётно, так как многочленов счётное число (многочлен задаётся конечной последовательностью целых чисел - его коэффициентов), а каждый многочлен имеет конечное число корней (не более n для многочленов степени n).
7. Множество периодических дробей счётно. В самом деле, такая дробь может быть записана как конечная последовательность символов из конечного множества (запятая, цифры, скобки); например, дробь 0,16666. . . можно записать как 0,1(6). А таких последовательностей счётное множество.
8. Любое семейство непересекающихся интервалов на прямой конечно или счётно. Это утверждение опирается на то, что множество рациональных чисел всюду плотно в множестве вещественных чисел. Означает, что сколь угодно близко к любому вещественному числу можно найти рациональное число. Доказывать строго не буду, нестрого - если в бесконечной десятичной записи вещественного числа отбросить "хвост", получим рациональное число. Чем дальше начинается "хвост", тем ближе рациональное число к исходному вещественному.
Теперь берем середину интервала и находим рациональное число на расстоянии меньше половины длины интервала. Поскольку по условию интервалы не пересекаются, получаем взаимно-однозначное соответствие между множеством интервалов и некоторым множеством рациональных чисел. Последнее может быть только счетным или конечным.

Задачки:
3. Докажите, что любое множество непересекающихся восьмёрок на плоскости конечно или счётно. (Под "восьмеркой" будем понимать пару касающихся внешним образом окружностей, именно линий, а не плоских фигур, "восьмерка" полностью лежащая внутри одной из окружностей другой "восьмерки" без касания - не пересекается).
4. То же для непересекающихся букв "Т". (Пара перпендикулярных отрезков, конец одного из них расположен внутри другого отрезка).
5. Докажите, что множество точек строгого локального максимума любой функции действительного аргумента конечно или счётно. (Строгий локальный максимум - точка, в некоторой окрестности которой значения функции строго меньше, чем в этой точке).

С уважением - Sergei
--- GoldED+/W32-MINGW 1.1.5-b20120519 (Kubik 3.0)

Alexander Hohryakov написал(а) к Sergei Nickolaev в Apr 23 23:52:18 по местному времени:

Здpавствуй, Sergei!

Суббота 15 Апреля 2023 15:10, ты писал(а) All, в сообщении по ссылке area://starper.limited?msgid=2:6035/3.17+643aa6d7:


SN> Задачка 1:
SN> Описанный проход по диагоналям задаёт взаимно однозначное соответствие
SN> между множеством всех пар натуральных чисел (которое обозначается N x
SN> N) и N. Это соответствие задается простой формулой: многочленом второй
SN> степени с рациональными коэффициентами). Найдите этот многочлен.


0| 1 2 3 4 ...... X
_____________________
1| 1 2 4 7
|
2| 3 5 8
|
3| 6 9
|
4| 10
|
.
.
Y

Номер диагонали, в которой расположено то или иное число D=X+Y. В первой диагонали одно число, во второй два, в третьей три и т. д. Первое число в диагонали D -- Z=1+2+3+...D=1+D(D-1)/2 Число в столбце Y этой диагонали D+Y-1=((X+Y)(X+Y-1)/2)+Y, если я нигде не ошибся.


С уважением - Alexander
--- -

Sergei Nickolaev написал(а) к Alexander Hohryakov в Apr 23 23:14:34 по местному времени:

Привет, Alexander!

SN>> Задачка 1:
SN>> Описанный проход по диагоналям задаёт взаимно однозначное
SN>> соответствие между множеством всех пар натуральных чисел (которое
SN>> обозначается N x N) и N. Это соответствие задается простой
SN>> формулой: многочленом второй степени с рациональными
SN>> коэффициентами). Найдите этот многочлен.


AН> 0| 1 2 3 4 ...... X
AН> _____________________
AН> 1| 1 2 4 7
AН> |
AН> 2| 3 5 8
AН> |
AН> 3| 6 9
AН> |
AН> 4| 10
AН> |
AН> .
AН> .
AН> Y

AН> Номер диагонали, в которой расположено то или иное число D=X+Y. В
AН> первой диагонали одно число, во второй два, в третьей три и т. д.
AН> Первое число в диагонали D -- Z=1+2+3+...D=1+D*(D-1)/2 Число в столбце
AН> Y этой диагонали D+Y-1=((X+Y)*(X+Y-1)/2)+Y, если я нигде не ошибся.

Почти не ошибся :-) Для координат X, Y номер диагонали - X+Y-1, а не X+Y ...
Но идея - верная, полностью. Если все считать не с 1, а с 0, то формула получится чуть менее громоздкая ...

С уважением - Sergei
--- GoldED+/W32-MINGW 1.1.5-b20120519 (Kubik 3.0)

Alexander Hohryakov написал(а) к Sergei Nickolaev в Apr 23 13:53:50 по местному времени:

Здpавствуй, Sergei!

Понедельник 17 Апреля 2023 23:14, ты писал(а) мне, в сообщении по ссылке area://starper.limited?msgid=2:6035/3.17+643dabab:

AН>> 0| 1 2 3 4 ...... X
AН>> _____________________
AН>> 1| 1 2 4 7
AН>> |
AН>> 2| 3 5 8
AН>> |
AН>> 3| 6 9
AН>> |
AН>> 4| 10
AН>> |
AН>> .
AН>> .
AН>> Y

AН>> Номер диагонали, в которой расположено то или иное число D=X+Y. В
AН>> первой диагонали одно число, во второй два, в третьей три и т. д.
AН>> Первое число в диагонали D -- Z=1+2+3+...D=1+D*(D-1)/2 Число в
AН>> столбце Y этой диагонали D+Y-1=((X+Y)*(X+Y-1)/2)+Y, если я нигде
AН>> не ошибся.

SN> Почти не ошибся :-) Для координат X, Y номер диагонали - X+Y-1, а не
SN> X+Y ... Но идея - верная, полностью. Если все считать не с 1, а с 0,
SN> то формула получится чуть менее громоздкая ...

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


С уважением - Alexander
--- -

Alexander Hohryakov написал(а) к Sergei Nickolaev в Apr 23 12:27:52 по местному времени:

Здpавствуй, Sergei!

Суббота 15 Апреля 2023 15:10, ты писал(а) All, в сообщении по ссылке area://starper.limited?msgid=2:6035/3.17+643aa6d7:


SN> Задачки:
SN> 3. Докажите, что любое множество непересекающихся восьмёрок на
SN> плоскости конечно или счётно.

Тут моей фантазии не хватает.


С уважением - Alexander
--- -

Sergei Nickolaev написал(а) к Alexander Hohryakov в Apr 23 16:06:12 по местному времени:

Привет, Alexander!

SN>> Задачки:
SN>> 3. Докажите, что любое множество непересекающихся восьмёрок на
SN>> плоскости конечно или счётно.

AН> Тут моей фантазии не хватает.

Скорее, навыков, а не фантазии :-)

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

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

Факт: внутри любой окружности можно найти точку с рациональными координатами (их там всегда бесконечно много, счетное множество). Если непонятно, почему так - скажи, объясню, но надеюсь, что понятно, почему.

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

Покажем, что если две восьмерки не пересекаются, то у них могут совпадать не более одной из двух сопоставленных им точек.
Именно: есть два варианта расположения непересекающихся восьмерок.
1. Одна из восьмерок расположена полностью внутри одной из окружностей другой восьмерки. В этом случае одна из сопоставленных восьмеркам точек может совпасть, но другая не может принципиально.
2. Каждая из этих двух восьмерок расположена снаружи окружностей, составляющих другую восьмерку. В этом случае никакие совпадения точек невозможны.

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

Все доказано! :-)

Второе примечание: Если вместо восьмерок взять окружности, вместо букв Т - буквы Г и вместо строгих максимумов - нестрогие, то нифига не выйдет :-)

С уважением - Sergei
--- GoldED+/W32-MINGW 1.1.5-b20120519 (Kubik 3.0)

Alexander Hohryakov написал(а) к Sergei Nickolaev в Apr 23 18:34:52 по местному времени:

Здpавствуй, Sergei!

Воскресенье 23 Апреля 2023 16:06, ты писал(а) мне, в сообщении по ссылке area://starper.limited?msgid=2:6035/3.17+64452d46:

SN>>> 3. Докажите, что любое множество непересекающихся восьмёрок на
SN>>> плоскости конечно или счётно.

AН>> Тут моей фантазии не хватает.

SN> Скорее, навыков, а не фантазии :-)

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

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

SN> Примечание: для двух других задач, про буквы Т и про строгие локальные
SN> максимумы работает этот же подход, вся разница в том, что сопоставить
SN> ...

SN> Факт: внутри любой окружности можно найти точку с рациональными
SN> координатами (их там всегда бесконечно много, счетное множество). Если
SN> непонятно, почему так - скажи, объясню, но надеюсь, что понятно,
SN> почему.

Рациональных чисел на каждой из координатных осей бесконечно много, счетное множество, стало быть, и пар чисел счетное множество, это понятно.

SN> Сопоставим восьмерке две рациональных точки - одна внутри одной
SN> окружности, другая - внутри второй.

SN> Покажем, что если две восьмерки не пересекаются, то у них могут
SN> совпадать не более одной из двух сопоставленных им точек.
SN> Именно: есть два варианта расположения непересекающихся восьмерок.
SN> 1. Одна из восьмерок расположена полностью внутри одной из окружностей
SN> другой восьмерки. В этом случае одна из сопоставленных восьмеркам
SN> точек может совпасть, но другая не может принципиально. 2. Каждая из
SN> этих двух восьмерок расположена снаружи окружностей, составляющих
SN> другую восьмерку. В этом случае никакие совпадения точек невозможны.

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

SN> Все доказано! :-)

Семён Семёныч!

SN> Второе примечание: Если вместо восьмерок взять окружности, вместо букв
SN> Т - буквы Г и вместо строгих максимумов - нестрогие, то нифига не
SN> выйдет :-)

А вот об отличии Т от Г и О я задумался. Подсказок пока не надо.


С уважением - Alexander
--- -

Sergei Nickolaev написал(а) к Alexander Hohryakov в Apr 23 23:52:12 по местному времени:

Привет, Alexander!

AН> А вот об отличии Т от Г и О я задумался. Подсказок пока не надо.

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

С уважением - Sergei
--- GoldED+/W32-MINGW 1.1.5-b20120519 (Kubik 3.0)

Alexander Hohryakov написал(а) к Sergei Nickolaev в Apr 23 10:50:06 по местному времени:

Здpавствуй, Sergei!

Среда 26 Апреля 2023 23:52, ты писал(а) мне, в сообщении по ссылке area://starper.limited?msgid=2:6035/3.17+64498fd5:

SN> Вдогонку: задачка, которую я не смог решить в 9 классе.

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

На городской олимпиаде по физике я её не решил. Как потом узнал, никто не решил.

Прошло много лет. Сын возвращается с олимпиады по физике: "Все задачи решил, кроме одной. Найти коэффициент трения деревянного бруска о стол, используя... Пап, чего ты смеёшься?"

Прошло еще несколько лет, в ФИДО зашёл разговор о школьном образовании, и я задал эту задачу. Десяток взрослых дядей с высшим образованием, не решил никто.
На следующий день после того, как я не решил эту задачу, отец мой, школьный учитель, он принимал участие в подготовке олимпиады, рассказал, что её выбрали в качестве утешительной. Когда знаешь решение, она кажется такой простой...


С уважением - Alexander
--- -

Alexander Hohryakov написал(а) к Sergei Nickolaev в Apr 23 11:12:10 по местному времени:

Здpавствуй, Sergei!

Среда 26 Апреля 2023 23:52, ты писал(а) мне, в сообщении по ссылке area://starper.limited?msgid=2:6035/3.17+64498fd5:

SN> Вдогонку: задачка, которую я не смог решить в 9 классе.
SN> Найти функцию, определенную на всей числовой оси, принимающую каждое
SN> свое значение ровно два раза. Непрерывную искать не стоит, не
SN> получится :-)

Да, Y=abs(X) не годится из-за точки 0,0


С уважением - Alexander
--- -