Занимательные математические задачи про Алису и не только...

[Алексей Н.]

5. По прикидкам, можно взять

Да.

Добавлено спустя 2 часа 57 минут 2 секунды:
Re: Занимательные математические задачи про Алису и не только...
Опс, оказывается, в условии задачи 7а) была ошибка. На самом деле там надо 3 кнопки, а двух может быть недостаточно. Исправил условие.

[Весельчак Ы]

На самом деле там надо 3 кнопки, а двух может быть недостаточно.

И то правда - реализовываем пересечениями циклический граф из пяти вершин.
Задача, вроде, делается так. Поскольку проект «Связь времен» завершен, то считаем, что число писем конечно. Пусть С – семья наших прямоугольников – писем. Спроектируем все прямоугольники на ось абсцисс – край стола. Получим семью \pi(С) отрезков, удовлетворяющих условию задачи. Среди концов этих отрезков выберем две точки: самый левый из правых концов и самый правый из левых. Легко показать, что любой отрезок из \pi(С) обязан содержать одну из этих точек. Выберем одну из этих точек А. Пусть, для определенности, это будет самый левый из правых концов. Рассмотрим семью C’ прямоугольников, проекции на ось абсцисс которых не содержат точки А. Пусть П – прямоугольник из С, правый конец которого проектируется в точку А. Тогда, поскольку ни один из прямоугольников семьи С’ не проектируется на точку А, то любые два прямоугольника из С’ не пересекаются с П, поэтому они пересекаются между собой. Применяя теорему Хелли к проекциям семьи С’ на координатные оси, получаем, что все прямоугольники семьи С’ имеют общую точку. Воткнем в нее кнопку. По построению, все прямоугольники из С\С’ пересекают прямую, проходящую через точку А параллельно оси ординат. Рассмотрим семью с(С\С’) отрезков – пересечений прямоугольников семьи С\С’ с этой прямой. Оставшиеся две кнопки воткнем в самый верхний из нижних концов и самый нижний из верхних концов отрезков семьи с(С\С’).

[Evgenij]

Это не так, дело в другом.

Закипел мозг - долил антифриза!
Два раза начинал писать опровержения Вам на третий раз понял - вы правы.

[Алексей Н.]

Весельчак Ы

Все верно.

Evgenij

Ну а в чем правильное объяснение поняли?

[Evgenij]

Сначало про гепотинузу мне показалось нелепостью. В конце до меня дошло что если бы гипотенузой треугольников получалась бы прямая, то площадь фигур не менялась бы и под лишнюю клетку не хватило бы места при перестановки фигур. Если я опять не прав объясните или убейте! (пошел доливать антифриз)

[Весельчак Ы]

Алексей Н.

Задача 2.Опять прикидки. Решение этой задачи состоит из последовательных и естественных шагов, причем для выбора каждого следующего шага особых альтернатив у нас нет. Итак, будем считать цвета элементами группы $G=\mathbb Z^{11}_2$ с нулевой суммой кооординат. Обозначим через $s$ сумму цветов всех чатлан, через $x_i$ - цвет $i-$того чатланина, а через $\pi_i$ -- проекцию $G$ на $i$-тую координату. Пусть теперь значение, передаваемое $i$-тым чатланином равно $\pi_i(s-x_i)$. Поскольку для $j\not=i$ $j$-тый чатланин может найти значение $\pi_i(s-x_i-x_j)$, то он может также найти значение $\pi_i(x_j)$. Значение $\pi_j(x_j)$ он находит из равенства $\sum \pi_i(x_j)=0$.

[Алексей Н.]

Evgenij, живите и не убивайтесь! По-моему, Вы теперь правильно задачку понимаете. А антифриз Вам еще пригодится

Весельчак Ы, а почему прикидки? Вполне себе полное решение. Даже симметричнее моего

[Весельчак Ы]

Алексей Н.

Прикидки потому, что я не проверяю выкладок, а пишу то, что мне кажется правдоподобным.

Добавлено спустя 10 часов 44 минуты 38 секунд:
Re: Занимательные математические задачи про Алису и не только...

Задача 6. Вы будете смеяться, но в статье Дэвида Барнетта (David V. Barnette) «Projections of 3-polytopes», которую я сейчас читаю (На ее основной результат опирается доказательство Бранко Грюнбаума (Branko Grunbaum) другого результата, очень желательного для нас, но очень сильного, и тем странного. Поэтому, чтобы прояснить ситуацию, мы решили детальней разобрать эти доказательства), есть лемма, использование которой могло бы редуцировать эту задачу. Однако, размышляя о применении этой леммы к решению Вашей задачи, я, как мне кажется, обнаружил контрпример к лемме. Я сейчас выясняю, есть ли у Барнетта прокол в доказательстве – действительно ли я обнаружил контрпример, или я просто что-то не так понял (я не графист, и, кроме того, статья написана в 1970 году и в ней используется старая терминология и обозначения).

[Алексей Н.]

У Грюнбаума в

Gr¨unbaum B. Gr¨otzsch’s theorem on 3-coloring, Michigan Math. J., 10:3 (1963), 303–310.

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

Аксенов В. А. О продолжении 3-раскраски на плоских графах, Дискретный анализ: Сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, Вып. 26 (1974), 3–19.
(Aksionov V. A. On continuation of 3-colouring of planar graphs (in Russian), Diskret. Anal. Novosibirsk 26 (1974), 3–19.)

Там он дал правильную формулировку и доказательство теоремы о продолжении. Теперь уже и буржуи на это ссылаются в работах по плоским графам. Такая вот история. Поэтому в статьях с 1963 по 1974 (да и позже) могли появляться проколы, связанные с использованием той работы Грюнбаума.

[Весельчак Ы]

Подумать только, какое совпадение – (еще ?) один прокол, связанный с работой Грюнбаума по графам.

Но мы рассматриваем другую проблему. Согласно теореме Стейнитца (Steinitz), граф G изоморфен 1-скелету выпуклого многогранника, тогда и только тогда, когда G планарный и 3-связный. Такие графы называются полиэдральными. Для полиэдрального графа G нас интересуют наибольшее количество вершин v(G) (соответственно, граней f(G)) которые могут находиться в одной плоскости (соответственно, пересекаться одной плоскостью) в некоторой реализации графа G в виде 1-скелета выпуклого многогранника (т. е. v(G) и f(G) это соответствующие максимумы по реализациям и плоскостям), и, в особенности, асимптотические (в зависимости от числа вершин графа) оценки наименьших значений v и f в различных классах графов. (Откуда взялся наш интерес к этой проблеме – это отдельный вопрос).

Ясно, что f(G)\le c(G*), где G* – дуальный граф к G, а с(G*) – длина наибольшего цикла в G*. У нас есть гипотеза, что Грюнбаум в статье «Cutting convex polyhedra by planes» доказал, что f(G)=c(G*). Но этот результат мне кажется странным, поскольку, например, в этом случае должна существовать реализация 1-скелета глобуса в виде выпуклого многогранника, в котором можно пересечь почти все грани одной плоскостью. Поэтому мы сейчас разбираемся в доказательстве Грюнбаума и основном результате статьи Барнетта, на которую оно опирается.

[Алексей Н.]

Не знаю, вроде довольно естественно выглядит результат. Нарисуем на поверхности многогранника G замкнутый контур Z, проходящий через наибольшее число его граней (т.е. через c(G*) граней). По теореме Жордана Z делит поверхность G на две области D1, D2, гомеоморфные дискам. Непрерывно преобразуем поверхность G в сферу так, чтобы Z перешел в большую окружность этой сферы, а области D1, D2 (вместе с содержащимися в них вершинами и ребрами) - в две полусферы с общей границей Z. Теперь единственная проблема - реализовать все так, чтобы ребра были отрезками прямых, но по-моему, это должно решаться в стиле теорем о существовании плоских реализаций планарных графов с прямыми ребрами. Или я не прав?

Скажем, если G* гамильтонов, т. е. с(G*) = |F(G)|, то внутри областей D1 и D2 будут находиться деревья из вершин и ребер G (так называемое древесное 2-разбиение вершин G), а все грани G (и вообще все циклы) будут пересекать экваториальную плоскость, проходящую через Z.

[Весельчак Ы]

Алексей Н.

Нарисуем на поверхности многогранника G замкнутый контур Z, проходящий через наибольшее число его граней (т.е. через c(G*) граней). По теореме Жордана Z делит поверхность G на две области D1, D2, гомеоморфные дискам. Непрерывно преобразуем поверхность G в сферу так, чтобы Z перешел в большую окружность этой сферы, а области D1, D2 (вместе с содержащимися в них вершинами и ребрами) - в две полусферы с общей границей Z.

Подход Грюнбаума непосредственно основан не на топологии, а на геометрии (см. предпоследний абзац на с. 5 его статьи).

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

Кстати, зафиксировав концы этих ребер также можно было пробовать доказать, что v(G)\ge c(G*)\ge f(G).

Собственно, прямолинейными изображениями (straight-line drawings) графов мы и занимаемся. Но, в то время как теорема Вагнера-Фари-Стейна (Wagner-Fáry-Stein) о существовании прямолинейного изображения планарного графа, доказывается, видимо, относительно нетрудной индукцией, наверное, по числу вершин, в предлагаемой Вами идее есть ограничение на расположение вершин (в данном случае внешних граней). А доказательство подобных теорем может быть довольно трудным (например, следующая проблема открыта:

Suppose that $\pi$ is a crossing-free drawing of a graph $G$. A set of vertices $S\subseteq \pi(V_G)$ in $\pi$ is \emph{collinear} if all of them lie on a line $\ell$. By a \emph{conformal displacement} of $S$ we mean a relocation $\delta\function S\ell$ preserving the relative order in which the vertices in $S$ lie in $\ell$. We call $S$ \emph{free} if every conformal displacement $\delta\function S\ell$ is extendable to a mapping $\delta\function{\pi(V_G)}{\reals^2}$ so that $\delta\circ\pi$ is a crossing-free drawing of $G$ (i.e., whenever we shift vertices in $S$ along $\ell$ without breaking their relative order, then all edge crossings that may arise can be eliminated by subsequently moving the vertices in $\pi(V_G)\setminus S$). Is every collinear set in any straight line drawing free?

Вроде доказано, что ответ положителен для прямолинейных изображений специального вида (так называемых folded drawings)) С другой стороны, есть теорема Хонга и Нагамочи [HN]: Given a triconnected plane graph H, every drawing δ* of the outer facial cycle of H on a star-shaped polygon P can be extended in linear time to a plane drawing of H (even one where all inner faces are convex).

Кроме того, есть проблема с двухстороннестью связи между выпуклыми многогранниками и прямолинейными изображениями на плоскости. Вот что пишет мой соавтор по этой тематике, занимающийся графами и доктор наук: «Proposition … is based on the fact that a polyhedron can be projected to a straight line drawing. It seems that for the backward inequality we would need a kind of the converse, say, that any straight line drawing of a polyhedral graph can be “lifted” to a polyhedron. I do not know if this is true and am pessimistic about this: this statement is even stronger than Steinitz's theorem, whose known proofs are fairly uneasy».

[HN] Seok-Hee Hong and Hiroshi Nagamochi. «Convex drawing of graphs with non-convex boundary». In Fedor V. Fomin, editor, Proc. 32nd Internat. Workshop Graph-Theoretic Concepts in Comput. Sci. (WG’06), volume 4271 of Lecture Notes Comput. Sci., pages 113–124. Springer-Verlag, 2006.

[Алексей Н.]

Да я уж понял, что здесь все упирается в геометрию, а не в топологию. Мы то, раскрасочники, этими проблемами прямолинейности не грузимся. Что касается гипотезы, то бесспорной она не выглядит. Даже не знаю, к какому ответу я больше склоняюсь. Если говорить о моей идее, то вроде бы в упомянутой Вами статье Барнетта как раз реализуется нечто похожее, то есть доказывается, что заданный цикл в полиэдральном графе можно реализовать как "экваториальный" для соответствующего многогранника. В том смысле, что при проецировании перпендикулярно "экваториальной плоскости" он отображается во внешний цикл проекции.

Добавлено спустя 2 дня 4 часа 6 минут 13 секунд:
Re: Занимательные математические задачи про Алису и не только...
На мой взгляд дилетанта в вопросах прямолинейных реализаций, трудности, возникающие при построении плоских реализаций, совсем иные, чем при построении полиэдральных реализаций. Если в первом случае надо бороться за непересекаемость отрезков, то во втором это само по себе уже не актуально (в ge 3-мерном пространстве), а все упирается в компланарность вершин каждой грани. В этом смысле, есть ощущение, что строить полиэдральные реализации триангуляций проще всего (ведь треугольник всегда в одной плоскости), а вот строить их плоские реализации максимально трудно.

Вот не очень сложная задачка, слегка по теме:

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

Добавлено спустя 14 минут 16 секунд:
Re: Занимательные математические задачи про Алису и не только...
Есть вопрос: верна ли теорема HN для любых (не трехсвязных) плоских графов, у которых внешняя грань ограничена простым циклом? Если да, то неужели не удается ее применить для положительного решения гипотезы? Если нет, то каковы контрпримеры? Вроде неясно, с чего ей быть неверной, ведь мы всегда можем достроить внутренность внешнего цикла H до триангуляции, а такой граф будет трехсвязным.

[Весельчак Ы]

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

Мы то, раскрасочники, этими проблемами прямолинейности не грузимся.

За время нашего обсуждения, я начал читать одну новую статью [CTU] по нашей тематике, и теперь у нас тоже есть проблема, связанная с раскраской. Я собираюсь на днях дочитать эту статью, вникнуть в эту проблему, а также начать переписку с авторами статьи и своими соавторами.

Также в этой статье, вроде, доказывается аналог равенства f(G)=c(G*) для плоских прямолинейных изображений планарных триангуляций.

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

Это естественное и разумное замечание. Как-то мы его, в явном виде, не сформулировали.

мы всегда можем достроить внутренность внешнего цикла H до триангуляции, а такой граф будет трехсвязным.

Точно будет? Мне кажется, что нет. Например, для случая, когда мы имеем граф «два квадрата с общей стороной» (6 вершин, 2 внутренних грани, 7 ребер), триангуляция внутренности вроде не делает его трехсвязным. Или что Вы понимаете под простым циклом? Если Вы имеете в виду цикл без хорд, то добавим вершину в центр симметрии предыдущего графа.

Опять таки, у нас есть гипотеза и на случай цикла без хорд: «Let C be a chordless cycle in a planar graph G. Then G can be drawn so that all but one vertices of C are collinear». В частности, эта гипотеза вроде верна, когда C является границей грани: «Recall that a triangulation is a plane graph where every face (including the outer face) is a triangle, and a near-triangulation is a plane graph where every face except possibly the outer face is a triangle. Tutte [12] proved that every near-triangulation has a straight-line embedding such that the outer face is mapped to a given convex polygon». [CTU]

верна ли теорема HN для любых (не трехсвязных) плоских графов, у которых внешняя грань ограничена простым циклом? Если да, то неужели не удается ее применить для положительного решения гипотезы? Если нет, то каковы контрпримеры?

Честно говоря, самого доказательства теоремы HN я не видел. Если допускать циклы с хордами, то контрпример, кажется, придумать несложно. Например, вроде, такой:



---
[CTU] Javier Cano, Csaba D. Tóth, Jorge Urrutia «Upper bound constructions for untangling planar geometric graphs»

[Алексей Н.]

Например, для случая, когда мы имеем граф «два квадрата с общей стороной» (6 вершин, 2 внутренних грани, 7 ребер), триангуляция внутренности вроде не делает его трехсвязным.

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

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

[Весельчак Ы]

Может быть, в доказательстве интересующих нас утверждений можно как-то
использовать индукцию, подобно доказательству Леммы 4 в [CTU].

я начал читать одну новую статью [CTU] по нашей тематике, и теперь у нас тоже есть проблема, связанная с раскраской.

Дочитал. Итак, наша проблема состоит в том, можно ли улучшить оценки, связанные с Проблемой 2 (стр. 5) из этой статьи. Ее авторы [CTU] пишут, что «Our upper bounds for f(n) depend on the value \log_b c* of an (a; b; c)-triangulation. The (a; b; c)-triangulations we considered are all derived from counterexamples for Tait's conjecture. Since these are counterexamples for Hamiltonicity, they all have a = b > c > 0. It is conceivable, though, that there are better constructions for (a; b; c)-triangulations in which a > b**».

Кажется, все планарные триангуляции, имеющие больше 3-х вершин, 3-связны, а дуальные графы к ним это в точности кубические (т. е. со степенью каждой вершины 3) полиэдральные (т. е., в данном случае, 3-связные) графы. Таким образом, для случая a=b, искомые примеры графов, с возможно меньшими значениями выражения \log_{b-1} (c-1) тесно связаны с примерами графов, с возможно меньшими значениями выражения \log_a c, т. е. с возможно меньшим отношением логарифма длины своего наибольшего цикла к логарифму количества своих вершин. Lim-inf этого отношения по всем графам некоторого бесконечного класса графов называется shortness exponent для этого класса. В частности, известны следующие оценки shortness exponent \sigma для класса кубических 3-связных графов: 0.694…=\log_2(1+\sqrt5)-1\le\sigma [Jac] и \sigma\le\frac{\log26}{\log27}=0.988… [GruWal].

Однако, авторы [CTU] вместо графов с малым значением своей «shortness exponent», дающих соответствующие оценки сверху на \sigma, используют пример Bernette, Bosák и Lenderberg [CTU, c.4], дающий, видимо, более слабую оценку \log_{b-1} (c-1)=\frac{\log36}{\log37}.

* Я подозреваю, что выражение «\log_b c» здесь и в доказательстве Теоремы 1 является систематической опиской, а вместо него должно быть выражение «\log_{b-1} (c-1)», поскольку в статье в начале конструкции в доказательстве Теоремы 1 появляется оценка O(n^{\kappa \log_b c}) на количество граней, которые могут пересекаться прямой (со ссылкой на Лемму 2), хотя в самой Лемме 2 есть лишь оценка O(n^{\kappa \log_{b-1} (c-1)}), а выражение «\log_{b-1} (c-1)}» опять появляется в Conclusion.

** Также я подозреваю, что условие a > b не даст конструкций с меньшими значениями соответствующих выражений \log_{b-1} (c-1) и \log_b c.

[GruWal] B. Grünbaum, H. Walther. Shortness exponents of families of graphs. J. Combin. Theory A 14:364--385 (1973).

[Jac] B. Jackson. Longest cycles in 3-connected cubic graphs. J. Combin. Theory B 41:17--26 (1986).

[tktyf]

http://sverhrazum.livejournal.com/630338.html

Учитель начальных классов Ирина Яковлевна Матюхина разработала для первоклашек на основе мультфильма "Тайна Третьей планеты" урок математики "Космическое путешествие", посвящённый числам 1-5.

[Весельчак Ы]

Итак, наша проблема состоит в том, можно ли улучшить оценки, связанные с Проблемой 2 (стр. 5) из этой статьи.

Похоже, что и наша проблема, и Проблема 2 уже не актуальны, поскольку мы заметили, что
\sigma =\lim\inf \log_a c = \inf \log_a c = \inf \log_{a-1} (c-1).
Кроме того, \log_{b-1} (c-1)\ge\sigma для любой (a,b,c)-триангуляции. Csaba Toth с нами согласился.