Математика, которая мне нравится

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

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

Определение. Пусть задано некоторое непустое множество

   

и множество

   

пар различных элементов из

   

. Элементы множества

   

называются вершинами графа, элементы множества

   

называются ребрами графа, а пара

   

, т.е. множество вершин и множество ребер, называется графом.

Обычно в качестве множества

   

берут множество первых

   

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

   

и ребрами

   

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

На рисунке слева степени вершин графа такие

   

—

   

,

   

—

   

,

   

—

   

,

   

—

   

,

   

—

   

,

   

—

   

,

   

—

   

,

   

—

   

.

Граф называется полным, если любые две его вершины смежные. Полный граф с

   

вершинами обозначается

   

.

Граф с

   

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

   

до

   

. Два помеченных графа считаются равными, если множества вершин и ребер у них совпадают.

Теорема. Число помеченных графов с

   

вершинами равно

   

, где

   

.

Доказательство. Рассмотрим множество всех вершин графа

   

и множество

   

всех потенциально возможных его ребер. Множество

   

содержит

   

элементов — столько же, сколько ребер в полном графе

   

.

Для каждого ребра

   

из множества

   

возможно два варианта: либо оно есть в нашем графе, либо его нет в графе. Тем самым число различных помеченных графов с

   

вершинами равно

   

.

А теперь задачи.

Задача 1. В игре “Спортлото-Шиш” розыгрыш главного приза проходит по следующим правилам. Каждый присутствующий в студии пишет независимо от других любое число различных пар различных натуральных чисел от

   

до

   

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

   

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

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

Задача 2. После жалоб на малое число участников, выигравших главный приз в лотерее “Спортлото-Шиш” организаторы игры изменили правила. Теперь каждый присутствующий в студии пишет независимо от других

   

различных пар различных натуральных чисел от

   

до

   

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

   

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

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

Источник: О.И. Мельников “Теория графов в занимательных задачах”, М.: Книжный дом “ЛИБРОКОМ”, 2011.