об индукции

Эта запись может быть интересна людям, любящим математику.

Есть один довольно частый способ использования доказательства по индукции, в котором индукция используется, чтобы установить какие-то дополнительные свойства общего случая, облегчающие доказательство, а потом о ней забывают и продолжают доказывать общий случай напрямую. Мы хотим доказать какое-то утверждение P(n) для всех n, и глядя на общий случай, мы видим, что если выполняется некое X, тогда P(n) можно легко свести к P(k) для k меньших, чем n. Ага, говорим мы, в этом случае - "по индукции", поэтому продолжим теперь обсуждать общий случай, предполагая, что X неверно, и доказываем его, уже не рассматривая другие значения n, напрямую.

Формально все доказательство выходит обернутым в индукцию, но по сути дела индукция помогла нам, "бесплатно" подарив информацию "не-X", а потом ушла в сторону. Мавр сделал свое дело, мавр может уходить. Этакое доказательство по полу-индукции.

Вчера попался хороший пример, опять из веблога по теории сложности, на который я несколько раз в последнее время ссылался. Рассмотрим связный граф без циклов, т.е. дерево; у него есть n вершин и n-1 ребер. Если мы добавим еще одно ребро, то обязательно получится цикл, но, вообще говоря, он может быть очень длинный. Однако если мы станем еще и еще добавлять ребра, то рано или поздно в графе появятся довольно короткие циклы - мы не сможем удерживать связанные циклами вершины далеко друг от друга. Сколько ребер надо добавить, чтобы получить очень короткие циклы, например, логарифмической длины от размера графа?

Утверждение: если в графе из n вершин есть 2n или более ребер, в нем есть цикл длиной 2log(n) или меньше.

( доказательство... )

надменный взгляд

"Эту миловидную женщину с немного надменным взглядом..."

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

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