Регулярные графы

Это продолжение темы о графах, начало смотрите здесь.

Определение. Граф, степени всех вершин которого одинаковы, называется регулярным.

Задача 1. В некоторой компании любые два знакомых не имеют общих знакомых, а любые два незнакомых имеют ровно двух общих знакомых. Докажите, что в этой компании все имеют одинаковое число знакомых.

Показать решение

Задача 2. В лагере отдыхают 50 школьников. Известно, что среди любых школьников найдется по крайней мере один, знакомый с тремя остальными. Докажите, что найдется школьник, знакомый со всеми остальными школьниками. Читать полностью ‘Регулярные графы’ »

Теорема Содди

Фредерик Содди (1877—1956) — английский химик, изучавший проблемы радиоактивности совместно с Резерфордом, выдвинувший теорию изотопов, удостоенный Нобелевской премии по химии 1921 г. за вклад в теорию строения атома. Кроме химии, Ф. Содди интересовался экономическими, социальными и политическими теориями, написал несколько книг на эти темы, а также занимался некоторыми математическими задачами.

Следующая довольно красивая теорема, долгое время считавшаяся гипотезой, принадлежит именно ему, хотя доказал ее Коксетер.

Теорема Содди. Пусть три окружности с радиусами a,b,c касаются внешним образом. Пусть r — радиус окружности, касающейся трех данных окружностей внешним образом, а R — радиус окружности, касающейся трех данных окружностей внутренним образом. Тогда имеют место равенства

\displaystyle2\left(\frac{1}{a^2}+\frac{1}{b^2}+\frac{1}{c^2}+\frac{1}{r^2}\right)=\left(\frac{1}{a}+\frac{1}{b}+\frac{1}{c}+\frac{1}{r}\right)^2,

\displaystyle 2\left(\frac{1}{a^2}+\frac{1}{b^2}+\frac{1}{c^2}+\frac{1}{R^2}\right)=\left(\frac{1}{a}+\frac{1}{b}+\frac{1}{c}-\frac{1}{R}\right)^2.

Читать полностью ‘Теорема Содди’ »

Неверно названные теоремы

Это список из неверно названных теорем в математике. Он включает в себя теоремы (леммы, следствия, гипотезы, законы и, возможно, даже странный объект), которые хорошо известны в математике, но названы не по имени открывшего их человека.

Закон Бенфорда. Впервые о нем заявил в 1881 году Саймон Ньюкомб, заново он был открыт в 1938 году Фрэнком Бенфордом. Первая строгая формулировка и доказательство, кажется, принадлежат Теду Хиллу (1988 год).

Теорема Бертрана о выборах. Этот результат относительно вероятности того, что победитель выборов был впереди на каждом шаге подсчета голосов, впервые опубликовал В.А. Витворт в 1878 году, но носит имя Джозефа Луи Франсуа Бертрана, который переоткрыл его в 1887 году.

Теорема Безу. Вполне возможно, что ее впервые сформулировал Исаак Ньютон в 1665 году. Суть доказательства была представлена Колином Маклореном (ок. 1720 г.) и Леонардом Эйлером, а также Этьеном Безу (ок. 1750 г.). Тем не менее, “доказательство’’ Безу было неверным. Первое правильное доказательство, кажется, по большей части принадлежит Жоржу-Анри Альфану (1870 г.). Читать полностью ‘Неверно названные теоремы’ »

Эмми Нётер

Отец Эмми Нётер — Макс Нётер — был выдающимся математиком и профессором в Эрлангене. Ее мать, Ида Кауфман, происходила из богатой кельнской семьи. Оба родителя Эмми были евреи. Эмми была старшей из четырех детей, у нее было три младших брата. Читать полностью ‘Эмми Нётер’ »

Любители математики и пирогов, объединяйтесь! :)

Сегодня — международный день числа \pi. Причем здесь пироги? Дело в том, что по-английски слово “pi” читается как “пай”, точно так же звучит и слово пирог — “pie” ;)

Читать полностью ‘Любители математики и пирогов, объединяйтесь! :) ’ »

Немного о графах

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

Итак, что же такое граф?

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

Обычно в качестве множества V берут множество первых n натуральных чисел, т.е. вершины графа просто нумеруют по порядку. Слева на рисунке вы видите изображение графа с V=\{1,2,3,4,5,6,7,8\} и ребрами

E=\{ (1,2),(1,3),(2,3),(2,5),(2,8),(3,4),(4,6),(5,6),(5,7),(6,7),(7,8)\}.

Если две вершины графа соединены ребром, то они называются смежными, иначе — несмежными. Число ребер, выходящих из данной вершины, называется степенью этой вершины. Читать полностью ‘Немного о графах’ »