Форум умных людей

Новый город построен в виде 12 прямоугольных кварталов домов, разделенных улицами; на каждом углу квартала и на каждом перекрестке улиц висит по почтовому ящику. Кварталы соприкасаются друг с другом целыми сторонами или имеют только один общий угол. Предположим, что всего имеется 37 отрезков улиц, ограничивающих городские кварталы, т. е. 37 интервалов между почтовыми ящиками. Сколько почтовых ящиков имеется в этом городе?

три разных варианта дают цифру 26. Почему не знаю, думаю что-то из теории графов

Действительно, всегда будет 26.

Можно заметить, что для каждой из конфигураций число почтовых ящиков равно 26. На самом деле это число не зависит от деталей плана города. Эйлер доказал следующую теорему. Если число вершин, ребер и граней (т. е. ограниченных ребрами областей) какого-либо плоского графа соответственно равно b, p и r, то b—p+r=2. В нашем случае b — число вершин, т. е. почтовых ящиков, р=37 — число ребер, т. е. отрезков улиц, и r= 12+1 = 13 — число граней, т.е. число кварталов, увеличенное на 1, что обусловлено наличием внешней(бесконечной) грани. Таким образом, имеем b—37+13=2, т. е. b=26.

А что такое бесконечная грань?

(http://i018.radikal.ru/1210/33/5cfa992eede4.jpg)
13 грань - внешняя