Решена задача о раскраске дорог

Израильскому математику удалось обосновать гипотезу о раскраске дорог (Road Coloring), имеющую важное значение в теории автоматов.

Гипотеза о раскраске дорог (Road Coloring) была сформулирована в 1970 г. израильскими математиками Адлером и Вейссом в статье "Similarity of automorphisms of the torus". Гипотеза ставит вопрос о возможности синхронизации движения в конечном сильно связном графе с постоянной полустепенью исхода (постоянным числом ребер, исходящих из вершин).

Допустим, что это число равно двум, и каждое ребро имеет одну из двух характеристик, например, "окрашено" в красный или синий ("к" или "с") цвета. Из каждой вершины исходят одно "к" и одно "с" ребро, а длины циклов имеют общий делитель 1. Авторы гипотезы задают вопрос: всегда ли существует последовательность букв "к" и "с", одновременно (за равное количество шагов) приводящая к определенной вершине графа из любой другой вершины?

Аврааму Трахтману (Avraham Trahtman), бывшему жителю России и выпускнику Уральского государственного университета, а ныне профессору Университета Бар-Илан, удалось найти решение этой задачи. Его работа под названием "The road coloring problem" опубликована на сайте электронной библиотеки Корнельского университета arxiv.org.

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

Теорема Кантора доказана по-новому

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

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

Согласно предложенной им в 1874 г. теореме, множество всех действительных чисел является несчётным, то есть оно не эквивалентно бесконечному ряду натуральных чисел (его элементы нельзя последовательно и однозначно пронумеровать натуральными числами 1, 2, 3 и т.д.).

Свое доказательство Кантор построил от противного, предположив наличие счётности пронумерованного списка всех действительных чисел a1, a2, a3 и т.д., находящихся в интервале от 0 до 1. Эти числа он представил в виде бесконечных десятичных дробей (рациональным числам для этого пришлось добавить бесконечное число нулей начиная с определенного знака после запятой).

Затем Кантор предложил составить еще одну бесконечную десятичную дробь, у которой первый знак после запятой отличается от первого знака после запятой a1, второй знак отличается от второго знака a2 и так далее до бесконечности.

Полученная дробь не совпадает ни с одной десятичной дробью an, поскольку на n-й позиции у нее и an стоят разные цифры. Из этого следует, что полученная дробь не входит в нумерованный список чисел, а значит этот список не является счётным.

Недавно наш современник Мэтью Бейкер (Matthew Baker) из Технологического института Джорджии в Атланте предложил новое доказательство того, что множество действительных чисел несчётно. Его статья с решением опубликована в издании Mathematics Magazine.

Ученные доказали - без ориентиров человек ходит по кругу

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

"Заблудившиеся люди действительно не могут идти по прямой, не имея какого-нибудь ориентира в пространстве - высокой башни, горы, солнечного или лунного диска на небе. В такой ситуации они на самом деле ходят кругами", - сказал ведущий автор публикации Ян Соуман, исследователь из Института биологической кибернетики имени Макса Планка в Германии, слова которого приводит пресс-служба издательства Cell Press.

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

К таким выводам ученые пришли в результате экспериментов с добровольцами, которым было предписано перемещаться по густому и ровному лесу или пустыне, придерживаясь как можно более прямолинейного пути. При этом траектория движения добровольцев фиксировалась с помощью GPS навигатора, а сам эксперимент продолжался в течение 6 часов.

На правах рекламы
출장서비스 출장안마 예약비없는 후불제

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