Доказательство нескольких утверждений по графам

[Piteryo]

Никак не получается, понять как грамотно доказать некоторые утверждения, например:

1) Доказать, что если в графе (без петель и кратных ребер) более 4 вершин, то либо в самом графе, либо в его дополнении содержится цикл.

попытки доказать

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


2) Если v - разделяющая вершина графа, то она не является разделяющей в его дополнении.

домыслы

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


3) Показать, что самодополнительный граф связен

@темы: Теория графов, Дискретная математика

---

Задача по теории вероятностей

[IDP]

Добрый день!
Подскажите, пожалуйста, верно ли решена задача? Что-то я сомневаюсь((

@темы: Теория вероятностей, Комбинаторика

---

Восстановить треугольник

[MestnyBomzh]

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

@темы: Планиметрия

---

[Дилетант]

С днем рождения, Alidoro!

Здоровья, счастья, радости, побольше всего интересного и замечательного!

@темы: Праздники, Люди

---

Исследование функции

[wpoms.]

Дана функция `y = |x^2 - 4*x + 3|`. Исследуйте ее на непрерывность и дифференцируемость в точке с абсциссой `1`. Ее график с осью `Ох` образует замкнутую фигуру. Найдите площадь этой фигуры.

@темы: Приложения определенного интеграла, Математический анализ, Исследование функций

---

[mkutubi]

С 8 марта!

@темы: Праздники

---

Рекуррентное соотношение

[wammy]

Здравствуйте.

Имеется следующее рекуррентное соотношение:
Т(0) = 2;
T(1) = 2;
T(n) = T(n-2) + 2n+7;

Получается следующая последовательность чисел: 2, 2, 13, 15, 28, . . .
Вопрос состоит в следующем:
Найти вид функции f(n), задающей данную последовательность чисел без рекурсии.
Это задание из лабораторки по алгоритмам. Под видом функции f(n) подразумевается что-то типа f(n) = 2*n + 3 или f(n) = n^2-2*n+1. На практике такие задачи решались "угадыванием", а тут что-то прям в упор ничего не вижу. Может опечатка? Заранее прошу прощения, если в сообществе такие задачи не разбираются.

@темы: Математический анализ

---

Домашняя работа по геометрии за 10 класс к учебнику «Геометрия. 10-11 класс»Д.Терешин

[Romerion]

Здравствуйте, не могу решить задачу по стереометрии: Длина ребра куба ABCDA1B1C1D1 равна a. На ребрах AD и B1C1 взяты соответственно точки M и Q, а на ребре CD - точки P и N так, что AM=C1Q=CP=DN=a/3. Постройте сечение куба плоскостью, проходящей через прямую MP параллельно прямой NQ, и найдите его площадь. Не могу построить сечение, у меня зовут есть идея, как это сделать, но сомневаюсь, что она правильная. Ниже фотография моего решения, не могли бы вы поправить меня, где ошибка. Помогите, пожалуйста, до завтра 13:00, 8 марта

@темы: Стереометрия

---

Геометрическая задача по физике

[Груша Вильямс]

Предлагаю Вашему вниманию задачу со Всероссийской студенческой олимпиады (Московский тур) по физике (в технических вузах) от 27.02.2016 г.

Первая частица движется по окружности радиуса `r` со скоростью `v`. Вторая частица догоняет первую, двигаясь по окружности с постоянной скоростью. Вторая частица в начальный момент времени находится от первой на расстоянии `l` под углом `alpha` к вектору скорости первой частицы в сторону от окружности радиуса `r` и движется таким образом, что в любой момент времени векторы скоростей обеих частиц параллельны друг другу. Определить радиус траектории `R` и скорость второй частицы `u`.

p.s. вся физика здесь - при равномерном движении по окружности скорость перпендикулярна радиусу.

@темы: Планиметрия

---

Задачи по терверу

[mathdon]

Помогите, пожалуйста, решить задачи:
1) Из 52 карт вынимаются сразу 4 карты. Найти вероятность того, что все эти 4 карты будут разных мастей при условии, что каждая карта после вынимания возвращается обратно в колоду.
2) В общежитии проживает 10% студентов университета. 75% студентов, проживающих в общежитии, увлекается спортом, среди них 46% юношей. Какова вероятность встретить в студенческом городке юношу, увлекающегося спортом и живущего в общежитии?
3) У человека имеется N ключей, из которых только один подходит к двери. Он последовательно испытывает их. Процесс испытания может закончиться при 1, 2, …., N испытаниях. Показать, что каждый из этих исходов имеет вероятность 1/N.
4) На обувной фабрике в отдельных цехах производятся подметки, каблуки и верхи ботинок. Дефектными оказываются 1% каблуков, 4% подметок и 5% верхов. Каблуки, верхи и подметки случайно комбинируются в цехе, где шьют ботинки. Какой процент ботинок будет испорчен?

@темы: Теория вероятностей

---

[Amicus Plato]

Продолжила читать найденную в поисках информации о Байесе книгу Бёрда Киви "Книга о странном". Сама книга довольно своеобразная и даже странная, хотя какой еще быть книге о странном? Я даже думала сперва, что Киви Бёрд это вообще фейковое имя — транслитерация "птички киви" — Kiwi bird. Но оказалось, что имя пишется не так. Зато нашла удивительный отрывок. Рекомендую.

Врата и ключ всех наук – математика… Сперва я докажу это в отношении человеческих наук и мирских дел, затем в отношении божественной науки.
Весной 1999 года научный мир был буквально ошарашен удивительным открытием. Благодаря историческим изысканиям, предпринятым немецким профессором комбинаторики Робертом Шипке, всеобщим достоянием стали гениальные труды малоизвестного прежде немецкого ученого Удо Ахенского, монаха-бенедиктинца, жившего и работавшего в период примерно с 1200 по 1270 годы.
Манускрипт, заинтересовавший Шипке

Как-то раз по случаю Роберту Шипке довелось посетить кафедральный собор г. Ахена (ФРГ), где в одной из витрин с примечательными древними экспонатами он увидел церковный манускрипт XIII века, приковавший внимание математика. Все дело было в иллюстрации, изображавшей вполне традиционный сюжет со Святым семейством, но где каионическая Вифлеемская звезда в небе имела, однако, совершенно необычный вид.
Приглядевшись как следует, Шипке с изумлением обнаружил, что звезда явно имеет характерную форму фрактала Мандельброта, одного из популярнейших ныне символов эры компьютерных вычислений.

Открытое в 1976 году исследователем IBM Бенуа Мандельбротом, это удивительное множество дробной размерности стало наиболее знаменитым фрактальным объектом, несущим в себе неисчерпаемое число самоподобных деталей. Поскольку для построения фрактала Мандельброта требуется гигантское количество итераций-пересчетов положения точек на комплексной плоскости, всегда было принято считать, что получить этот объект можно лишь с помощью быстродействующей вычислительной техники… Древний же манускрипт наглядно свидетельствовал о совершенно ином. Роберт Шипке настоял, чтобы ему дали возможность изучить документ подробнее и установил имя переписчика, которым оказался некто Удо Ахенский. Дальнейшие поиски привели профессора в Баварию, в старинный монастырь бенедиктинского ордена под Мюнхеном. С помощью местных историков удалось добраться до архива монастыря, где и был найден толстенный фолиант Codex Udolphus, собственноручно написанный монахом Удо Ахенским.
Эта книга была известна историкам еще с XIX века, но в те времена ее сочли сугубо богословской. Однако в первой же части книги Шипке обнаружил изложение основ теории вероятностей, несколько замысловато упакованных в форму порицания пристрастий к азартным играм с попутным изложением стратегий для игры в карты и кости. Вторая часть книги почти целиком была посвящена вычислению числа «пи», а вот третья, под названием «Salus» («Спасение»), неопровержимо свидетельствовала, что за семь веков до Мандельброта его удивительный фрактал был открыт никому не известным монахом Удольфом, попутно создавшим декартову систему координат и основы теории комплексных чисел.
Целью труда Удо была разработка метода для определения того, при каких условиях душе удастся достичь небес. Он предполагал, что всякая душа состоит из двух независимых частей, которые Удо назвал «profanus» (мирская) и «animi» (духовная), а затем стал представлять данные части как пару чисел на плоскости (любопытно, что ныне эти элементы комплексного числа семантически называются весьма похоже: «действительной» и «мнимой» частью). Разработав правила для сложения и перемножения чисел, Удо стал исследовать, как «душа каждого человека проходит испытания в течение жизни, из года в год колеблется между добром и злом, и в конечном итоге, согласно своей природе, либо засасывается во внешнюю тьму, либо навсегда притягивается к Господу». Выражаясь современным языком, Удо начинал с произвольного числа z, затем итерировал его примерно 70 раз по правилу z – » z2 + c, пока z не уходило в бесконечность, либо не притягивалось в множество Мандельброта. Объект, получившийся в результате итераций многих тысяч точек, Удо назвал «Divinitas» («Божественное»), сообщив в тексте книги, что на вычисления у него ушло 9 лет…
Короче говоря, нынешнему ученому миру оставалось бы лишь поражаться столь удивительной монашеской целеустремленности, сочетавшейся с гениальными прозрениями, если бы не единственное «но». Сообщение о сенсационном открытии датировано первым апреля 1999 года. Увы, это был всего лишь остроумный розыгрыш, хотя и сфабрикованный на редкость добротно.

@темы: Про самолеты

---

[Amicus Plato]

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

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

Википедия
Томас Байес (Бейес, англ. Reverend Thomas Bayes [beɪz]) (1702 — 7 апреля 1761) — английский математик и пресвитерианский священник, член Лондонского королевского общества (1742).
А вот кстати, когда я училась в университете, наш преподаватель по теорверу действительно говорил "Бейес", как и написано в скобках в Википедии.

Биография
Родился в 1702 году в Лондоне. Отец — Джошуа Байес — пресвитерианский священник, был представителем известного нонконформистского рода из Шеффилда. Томас обучался дома и в 1719 году поступил в Эдинбургский университет изучать логику и богословие. По возвращению домой в 1722 году, Байес помогал отцу в часовне проводить службу, а вскоре, в 30-х годах, сам стал священником в пресвитерианской церкви. В 1734 году переехал в Танбридж Уэллс, графство Кент. В 1752 году он вышел в отставку. Умер в 1761 году.

Работы Байеса
Он, как известно, опубликовал две работы в своей жизни, одна богословская и одна математическая:

1. Divine Benevolence, or an Attempt to Prove That the Principal End of the Divine Providence and Government is the Happiness of His Creatures (1731)
2. An Introduction to the Doctrine of Fluxions, and a Defence of the Mathematicians Against the Objections of the Author of The Analyst (опубликовано анонимно в 1736)

Достижения
Математические интересы Байеса относились к теории вероятностей. Он сформулировал и решил одну из основных задач этого раздела математики (теорема Байеса). Работа, посвящённая этой задаче, была опубликована в 1763 году, уже после его смерти. Формула Байеса, дающая возможность оценить вероятность событий эмпирическим путём, играет важную роль в современной математической статистике и теории вероятностей. Другая крупная его работа — «Очерки к решению проблемы доктрины шансов». Используется терминология: байесовская вероятность, байесовская сеть доверия, байесовская оценка решения, байесовское программирование и т. п.

Байесовская вероятность
Байесовская вероятность — это интерпретация понятия вероятности, используемая в байесовской теории. Вероятность определяется как степень уверенности в истинности суждения. Для определения степени уверенности в истинности суждения при получении новой информации в байесовской теории используется теорема Байеса.

Соотношение с частотной вероятностью
Байесовская вероятность противопоставляется частотной, в которой вероятность определяется относительной частотой появления случайного события при достаточно длительных наблюдениях.

Теория вероятности и статистики, основанная на частотной вероятности была разработана Р. А. Фишером, Э. Пирсоном и Е. Нейманом в первой половине XX века. А. Колмогоров также использовал частотную интерпретацию при описании своей аксиоматики, основанной на интеграле Лебега.

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

Теорема Байеса

Голубой неоновый знак, обозначающий простое выражение формулы Байеса (с) Википедия

Теорема Байеса (или формула Байеса) — одна из основных теорем элементарной теории вероятностей, которая позволяет определить вероятность какого-либо события при условии, что произошло другое статистически взаимозависимое с ним событие. Другими словами, по формуле Байеса можно более точно пересчитать вероятность, взяв в расчет как ранее известную (априорную) информацию, так и новые данные (постеприорную информацию). Формула Байеса может быть выведена из основных аксиом теории вероятностей, в частности из условной вероятности. Особенность теоремы Байеса заключается в том, что для её практического применения требуется большое количество расчетов, вычислений, поэтому байесовские оценки стали активно использовать только после революции в компьютерных и сетевых технологиях.

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

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

Теорема Байеса названа в честь её автора Томаса Байеса (1702—1761) — английского математика и священника, который первым предложил использование теоремы для корректировки убеждений, основываясь на обновлённых данных. Его работа «An Essay towards solving a Problem in the Doctrine of Chances» впервые опубликована в 1763 году, через 2 года после смерти автора. До того, как посмертная работа Байеса была принята и прочитана в Королевском обществе, она была значительно отредактирована и обновлена Ричардом Прайсом. Однако эти идеи не предавались публичной огласке до тех пор, пока не были вновь открыты и развиты Лапласом, впервые опубликовавшим современную формулировку теоремы в своей книге 1812 года «Аналитическая теория вероятностей».

Сэр Гарольд Джеффрис писал, что теорема Байеса «является основой теории вероятности, точно так же как и теорема Пифагора есть основа геометрии».


Берд Киви. Книга о странном. "Томас Байес"

@темы: История математики, Люди

---

[Дилетант]

В Яндексе грядет очередная контрольная "Что и требовалось доказать". Об этом уже был топик в нашем сообществе.
Она состоится 12 марта 2016 года.
Вот тренировочный вариант, который можно порешать.
yandex.ru/math/test/
Я только что прошла

Если есть желание что-то обсудить, давайте обсудим.

Задачи

Задачи
1. Мастер по ремонту телефонов Алексей заключает договор с клиентом. Алексей знает, что подоходный налог составляет 13% от суммы, указанной в договоре. Какую сумму нужно указать в договоре, если за замену разбитого экрана в телефоне после уплаты налога Алексей хочет получить на руки 3500 рублей? Ответ округлите до целого числа.

2. Пришельцы передали моделисту Михаилу чертежи космической станции, чтобы он построил у себя во дворе её модель в масштабе 1:24. Какую длину будет иметь постройка, если длина настоящей станции, согласно данным в чертежах, — 480 галактических футов?* Ответ укажите в метрах.
* В одном галактическом футе, утверждают пришельцы, примерно 23,1 сантиметра.

3. Самолёт перевёз бурых медведей из Москвы в зоопарк Буэнос-Айреса. По пути он совершил две промежуточные посадки: одну для того, чтобы взять на борт дрессировщика, а вторую для того, чтобы загрузить дополнительные касалетки с мёдом. Продолжительность первой стоянки составила 1 час 10 минут, а второй — 1 час 55 минут. Сколько времени самолёт провёл в воздухе, если он вылетел из Москвы в 16:50, а приземлился в Буэнос-Айресе в 08:55 следующего дня?*

* Разница во времени между Москвой и Буэнос-Айресом составляет 6 часов. Время отправления и прибытия — местное.

4. Задача от Уральского федерального университета.
Вася вынес на улицу прямоугольный аквариум размером 40 см × 20 см × 25 см и доверху наполнил его снегом. Когда Вася вернулся домой, снег растаял, и оказалось, что объём получившейся воды равен 2 литрам. Во сколько раз плотность воды больше плотности снега?

5. Задача от Московского физико-технического института.
Олег хочет выложить плиткой пол подсобного помещения размером 3 м × 3 м. В продаже имеются два типа подходящей плитки по одинаковой цене — 1000 руб./м2. Плитка первого типа имеет размер 20 см × 20 см и продаётся коробками по 20 штук. Плитка второго типа имеет размер 30 см × 30 см и продаётся коробками по 12 штук. Сколько рублей Олег потратит на плитку, если выберет более дешёвый вариант?*
* Олег — консерватор, поэтому все плитки на полу должны быть одинакового размера.

6. Ученики пятого «Б» поспорили о цвете платья на фотографии. Половина класса посчитала, что оно чёрно-синее, а половина была совершенно уверена, что бело-золотое. После уроков ученики взглянули на фотографию ещё раз, и некоторые из них поменяли мнение: 6 человек заявили, что платье всё-таки бело-золотое, а двое стали считать, что оно чёрно-синее. При этом сторонников бело-золотого варианта оказалось в два раза больше, чем сторонников чёрно-синего. Сколько человек учится в пятом «Б»?

7. Задача от Дальневосточного федерального университета.
Оля нарисовала прямую и отметила на ней пять точек. Коля нарисовал параллельную прямую и тоже отметил на ней пять точек. Сколько разных треугольников с вершинами в этих точках можно построить?

8. Кирилл передвигается на самокате со скоростью 12 км/ч. Он выехал из дома, рассчитывая прибыть на работу за 5 минут до начала совещания. Проехав некоторое расстояние, Кирилл вспомнил, что забыл дома пропуск, и решил за ним вернуться. Доехав до дома, Кирилл обнаружил пропуск в заднем кармане джинсов, развернулся и поехал на работу. Какое расстояние Кирилл проехал до того, как впервые подумал о пропуске, если в итоге он опоздал к началу совещания на 7 минут? Ответ дайте в километрах.

9. Задача от Казанского федерального университета.
Аня разговаривает по телефону и крутит в руках листок бумаги и ножницы. Сначала она 6 раз сложила листок пополам — поочерёдно вдоль и поперёк, — а потом, не разворачивая, отрезала у него 4 угла. Если теперь Аня развернёт листок, сколько в нём будет дыр? Отрезанный на границе листа кусок дырой не считается.

10. Задача от Высшей школы экономики.
На зачёт к преподавателю английского языка пришли 30 студентов: 13 с факультета экономики, 9 с факультета математики и 8 с факультета компьютерных наук. Их одинаковые внешне и на ощупь зачётные книжки лежат на столе. Какое наибольшее количество зачётных книжек должен взять преподаватель, чтобы быть уверенным, что среди оставшихся на столе присутствуют зачётки хотя бы 7 студентов одного факультета и 4 студентов другого?

@темы: Про самолеты, Порешаем?!

---

СЛАУ

[mathdon]

Помогите, пожалуйста, с заданием: как задать для матрицы коэффициентов системы линейных уравнений столбец свободных членов таким образом, чтобы сразу (наглядно, не решая, без вычислений) были видны корни СЛАУ? Буду очень благодарен за помощь!!!

@темы: Линейная алгебра, Системы линейных уравнений

---

Бриллиант

[wpoms.]

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

@темы: Задачи на экстремум

---

Матрица

[wpoms.]

Дана квадратная матрица `M` размера `n xx n` над полем вещественных чисел. Выразите через `M` две матрицы, одну симметричную и одну антисимметричную, такие, что их сумма в точности равна `M`.

@темы: Матрицы

---

Задания по теории графов

[Piteryo]

Вот не приходят идеи мне к этим 2 задачкам по теории графов:
1) Доказать, что в мультиграфе всякий замкнутый маршрут нечетной длины l>=3 содержит простой цикл. Доказать, что это несправедливо для маршрутов четной длины.

мои мысли

Здесь вообще чего-то не пойму, на что влияет четность/нечетность, и с чего это маршрут обязан иметь простой цикл.

2) Пусть p(G) - наименьшая из степеней вершин графа G, не имеющего петель и кратных ребер и содержащего n вершин (n >= 2)
Доказать, что если p(G) >= (n-1)/2, то граф связен.

очевидное рассуждение

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

@темы: Теория графов, Дискретная математика

---

Корни уравнения

[wpoms.]

Покажите, что уравнение `z^4 + 4*(i + 1)*z +1 =0` имеет корень в каждой четверти комплексной плоскости.

@темы: Комплексные числа

---

Шестиугольники

[All_ex]

Разбирали решение задачи:
Середины сторон выпуклого шестиугольника `A_1A_2...A_6` являются вершинами шестиугольника `B_1B_2...B_6`, у которого противоположные стороны параллельны...

Не буду пока говорить, что требуется доказать....

Понятно, что треугольники `A_1A_3A_5` и `A_4A_6A_2` подобны... но откуда следует, что они гомотетичны?...

---

Помогите, пожалуйста. 10 класс

[Frek Pyro]

Через вершину А прямоугольника АВСD проведена наклонная АМ к плоскости прямоугольника, составляющая 50 градусов со сторонами АD и АВ. Найдите угол между этой наклонной и плоскостью прямоугольника. Нашел ссылку на рисунок, а решить не могу. Подскажите.
www.geogebra.org/m/2481945

@темы: Стереометрия