Задача эквивалентна такой: при каких квадратичная форма под знаком квадратного корня положительно определена. Запишем матрицу этой квадратичной формы:

и применим критерий Сильвестра (положительная определённость равносильна положительности угловых миноров):

Ответ: .

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

Значит инвертирование монеты осуществляет биекцию между событием и его дополнением. Откуда следует, что

Ответ:

Заметим, что если или больше единицы, то

Рассмотрим положительные . Напомним неравенство Бернулли:

при и . Имеем неравенства

Следовательно,

Из симметрии, получается неравенство

Значит

С другой стороны, при очевидно, что . Таким образом, мы показли, что

Ответ: .

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

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

Площадь треугольника очевидно равна . Далее вспомним два простых свойства биссектрисы. Сформулируем их для биссектрисы :

1. Теорема о биссектрисе треугольника: биссектриса угла треугольника делит противолежащую сторону на отрезки, пропорциональные прилежащим к этому углу сторонам. Следовательно,

   

2. Теорема о площадях через центр вписанной окружности: площади треугольников пропорциональны соответствующим сторонам треугольника

   

   Из теоремы о площадях сразу находим

Если опустить высоту в треугольнике из точки , то легко увидеть, что

Значит,

Аналогично, находим

Окончательно, искомая вероятность равна

Ответ:

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

Сначала найдём все компоненты сильной связности ор. графа . Это можно сделать, например, алгоритмом Косарайю или Тарьяна; оба алгоритма основаны на поиске в глубину и работают за врем .

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

Граф-конденсат всегда является ориентированным ациклическим графом (DAG). Действительно, если бы в графе-конденсате существовал цикл, то все компоненты, лежащие на этом цикле, были бы взаимно достижимы, а значит, должны были бы образовывать в одну компоненту сильной связности. Это противоречит построению конденсата.

Далее рассмотрим стоки графа-конденсата, то есть вершины, из которых не выходит ни одного ребра. Если в графе-конденсате существует ровно один сток , то каждая вершина конденсата имеет путь в этот сток. В самом деле, в любом конечном DAG из любой вершины можно двигаться по исходящим рёбрам до некоторого стока; поскольку сток единственный, этот путь неизбежно заканчивается именно в . Следовательно, из любой компоненты сильной связности исходного графа достижима компонента , а значит, все вершины компоненты достижимы из любой вершины исходного графа. Поэтому именно вершины компоненты являются искомыми. Вершина является стоком, если её список смежности пуст — это условие легко проверяется за .

Если же в графе-конденсате имеется несколько стоков, то искомых вершин не существует. Действительно, пусть и — два различных стока. Из нельзя попасть в , поскольку из вообще не выходит рёбер, и аналогично из нельзя попасть в . Следовательно, не существует компоненты, достижимой из всех остальных компонент, а значит, в исходном графе нет вершины, достижимой из всех вершин графа.

Таким образом, алгоритм имеет следующий вид:

1. Найти компоненты сильной связности графа.

2. Построить граф-конденсат

3. Посчитать число его стоков

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

5. Если стоков несколько, вернуть пустое множество.

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