о конфигурациях

Случайно наткнулся (в поисках книги с похожим названием, не имеющей отношения к математике) на математический учебник "Конфигурации точек и линий" Бранко Грюнбаума, известного геометра (1929-2018).

Вся книга посвящена следующему вопросу. Для разных n и k, существует ли на плоскости набор из n прямых линий, и n точек, лежащих на них, так что на каждой из линий есть ровно k из n точек, и каждая точка лежит на ровно k из n линий? Если существует, мы также хотим знать, сколько таких разных, плюс есть разные варианты расширения понятия "на плоскости".



Такие наборы называются "конфигурации". Кроме известных примеров 3-на-3 (см. картинку) я не знал об этом вопросе и этой терминологии. Теперь я знаю достаточно, чтобы поделиться тремя забавными цитатами:

1. ЗАВИСИМОСТЬ ОТ ТОЧКИ ЗРЕНИЯ.
Понравилась рецензия на эту книгу на Амазоне, цитирую ее в переводе:

"Единственная книга по этой теме. Действительно, эта книга без особых мучений доведёт вас до переднего края современных исследований в области конфигураций. Автор заслуживает похвалы за ясное, грамотное изложение и хорошую организацию материала. Также верно, что передний край в конфигурациях не так уж сложно достичь (одного семестра на продвинутом уровне бакалавриата/начальном уровне магистратуры более чем достаточно для работы над открытыми проблемами). В зависимости от вашей точки зрения, это либо горячая новая область с интересными и доступными открытыми проблемами, либо область, которая была изобретена в конце девятнадцатого века, а затем справедливо забыта на сто лет, пока Грюнбаум не возродил её."

2. ВЕЛИЧАЙШЕЕ ПРЕУВЕЛИЧЕНИЕ ИСТИНЫ.
В предисловии к книге Грюнбаум рассказывает историю этого вопроса, включая "забыта на сто лет", восемьдесят в его описании. В частности, он упоминает несколько книг, которые в виде исключения упоминали конфигурации в то время, и пишет:

"Через три года после публикации работы Леви вышла чрезвычайно хорошо принятая книга Гильберта и Кон-Фоссена "Наглядная геометрия". Двадцать лет спустя был опубликован английский перевод, но, к сожалению, редакторы Mathematical Reviews не сочли её достойной чего-то большего, чем простого упоминания; второе немецкое издание 1996 года не удостоилось даже этого. Это серьёзная ошибка, поскольку многие последующие исследователи (включая автора настоящей работы) заинтересовались конфигурациями, прочитав изложение в "Наглядной геометрии". Это представление основ теории конфигураций содержится лишь в части одной главы, но представляет привлекательный подход к теме. Её часто упоминают как обоснование для изучения конфигураций, цитируя следующее предложение из:
«...было время, когда изучение конфигураций считалось самой важной отраслью геометрии».

Автор хотел бы предположить, что это величайшее преувеличение истины, которое можно найти во всех трудах Гильберта. Хотя это факт, что — как упоминалось выше — в «классический период» истории конфигураций довольно много людей интересовались этой темой, конфигурации никогда не были центральной темой математических (или геометрических) исследований."

3. Из некролога:

"Осенью 1955 года Бранко [Грюнбаум] был призван на действительную службу в ВВС Израиля, где работал в подразделении исследования операций; тем временем Зденка получила степень магистра по химии. Их первый сын Рами родился в 1956 году. Бранко завершил докторскую диссертацию в 1957 году и в 1958 году закончил армейскую службу. Вскоре после этого он получил стипендию в Институте перспективных исследований в Принстоне, где провёл с семьей два года. Осенью 1960 года он получил приглашение в качестве временного преподавателя в Университет Вашингтона в Сиэтле, где в ноябре родился их второй сын Даниэль. Пока они планировали возвращение в Израиль, где Бранко принял должность лектора в Еврейском университете, они узнали, что его брак со Зденкой был аннулирован, поскольку он не был юридически евреем согласно ортодоксальной интерпретации (его мать не была еврейкой), поэтому он и Зденка снова поженились в мэрии Сиэтла перед переездом в Иерусалим."

не благодари

Линор Горалик нередко выкладывает новые мини-рассказы в свой фейсбук (а также тг-канал na_slovah). Вот этот недавний очень понравился:

Не благодари
Борису Филановскому — с любовью и благодарностью

Когда матери поставили диагноз, кашляющий врач сказал Сергею прямо в кабинете: «Только не делайте глупостей, бесплатно не лечитесь». Сергей тогда позвонил Асиму, - у него всю жизнь было чувство, что Асим — это как козырь в рукаве. Правда, стоило Сергею вбить цифры, как мгновенно стало ясно, что ответа не будет, потому что его телефон у Асима наверняка не записан. Но ответ, изумительным образом, последовал со второго гудка: не то Асим помнил его номер со школы, не то отвечал на все входящие без разбора, хотя и был тем, кем был. «Серега, — сказал Асим, — давай, привет», — он всегда так говорил, — и Сергей тут же успокоился и сказал без промедления: «Аська, я не за деньгами, я за работой. У меня у мамы рак. Только я ничего не умею, кроме как на скрипочке играть. Но могу, наверное, научиться…» Асим помолчал, а Сергей подождал, а потом Асим сказал: «Ты приходи завтра в восемь утра на Чистые пруды к глухой стене, там тебя Гоша будет ждать, он с носом, как ты да я. Только не благодари, ради бога», - и отключился. Сергей еще некоторое время думал, как на завтра одеться, — стоял хрусткий март, и нужно было что-то такое, чтобы если пахать придется снаружи, на холоде, то тепло, но без стеснения в движениях, а если внутри на каком-нибудь складе, то легко раздеться. Он выбрал комбез для рыбалки и под него старую футболку и отцовский неубиваемый свитер из девяностых, - и, чувствуя, что сделал все возможное, лег.

Нос Гоши оказался еще почище, чем у Сергея с Асимом, - мама про такие говорила, что на них можно яичницу жарить. Гоша с некоторой растерянностью посмотрел на свитер под комбезом и спросил:
— Сергей Владимирович, можно просто «Сергей», да? Ну наряд у вас неожиданный немножко. Пойдемте-пойдемте.

Сергей хотел было пуститься в долгое объяснение про «снаружи» и «внутри», но Гоша уже ловко шел вперед-вперед-вперед, вправо-влево-вправо-влево, и вдруг открылась какая-то дверка там, где никакой дверки, разумеется, и быть не могло, а за дверкой оказалась каморочка, а в каморочке унитаз, — унитаз! в метро! — а на унитазе сидел совершенно линчевский крошечный человек и ел куриную ножку. Гоша сказал ему:
— Матвей Семенович, сделайте одолжение, приоденьте мне товарища.

Крошечный человек поглядел внимательно на Сергея, спрыгнул с унитаза, поднял его крышку, и Сергей увидел много сложенных стопочкой вещей в целлофановых пакетах. Человек покопался в вещах, взял что-то черное и что-то белое, и через две минуты изумленный Сергей стоял перед своими новыми знакомыми в топорщащейся фрачной паре. А еще минут через пять появилась скрипка, - кажется, какой-то мастеровой немец в приличном состоянии. Гоша надел на Сергея свой плащ, чтобы скрыть фрак, сунул офутляренного немца в бездонный черный рюкзак, и они поехали на Серпуховскую, и стали переходить на Добрынинскую, и Сергею делалось все страшнее и страшнее, и тут Гоша остановился, поставил рюкзак у стены и сказал:
— Ну что ж, снимаем плащ.
Сергей медлил, вцепившись ладонями в длинные рукава, и вдруг Гоша так улыбнулся, что Сергей немедленно стал мокрым, снял плащ и отдал его Гоше, а тот достал скрипку из рюкзака, положил раззявленный футляр на пол и сказал, перекрестившись:
— С Богом, Сережа.
— А не свинтят? — спросил Сергей тихо, но Гоша снова улыбнулся, и Сергей, поднастроившись, заиграл. Гоша остановил его почти сразу.
— Можно совет? - спросил он. — Я, Сереж, знаю, ты виртуоз, вундеркинд, премии, конкурсы, красный диплом. Но только вот на этом ты здесь далеко не уедешь. Ты скажи, — ты извини, ради бога, — ты «Калинку-малинку» можешь по-виртуозному сыграть?

Сергей понял и смог, потом смог «Дубинушку», потом «Березку», а потом понял, что уже не видит Гошу из толпы. Денег в футляре вдруг стало ощутимо много, и внезапно протянувшаяся к ним когтистая белая рука вызвала у Сергея ужас, заставивший его остановиться, но Гоша, возникший у правого уха, шепнул: «Моя девушка, будет прибирать, вечером все отдаст, а я пошел». И Сергей заиграл «Пусть бегут неуклюже…», и люди стали прихлопывать, и стало весело, очень весело и очень легко.

( Read more... )

двух отражений

На этой картинке хорошо объясняется, мне кажется, то, что мне всегда почему-то было трудно интуитивно уловить: что любое вращение в плоскости это композиция (сочетание) двух зеркальных отражений от двух осей. Конкретно, на рисунке есть синие прямые a и b, между ними угол θ. Все точки желтого треугольника ABC сначала зеркально отражаются вокруг прямой a, получается треугольник A'B'C', и он затем отражается вокруг b, получается A"B"C".

Видим, что итог такой, как если бы мы взяли ABC и повернули его вокруг точки P (где встречаются наши оси) на угол 2θ. Почему так? Во-первых, расстояние любой точки до P от зеркальных отражений не меняется: видим, что например A, A', A" все лежат на одной окружности вокруг P. Далее, равенство углов отражения приводит к тому, что полный угол вращения между A и A" как раз дважды угол, заключенный между прямыми, т.е. θ. Эти равные углы обозначены на диаграмме.

Это только один из нескольких случаев - если бы мы начали с точки A', то сначала отразились бы в A, а потом в другую точку, но тоже на угол 2θ от той, что начали - и там углы частично вычитаются, а не складываются. На рисунке самый наглядный пример, но и по всем остальным легко убедиться геометрически. Или выписать координатные формулы вращения и отражений - но мне важно было именно интутивное геометрическое понимание.

Это мне напомнило, как во время работы в Гугле я очень много раз давал следующую задачу на интервью кандидатам: написать код, который принимает числовой квадратный массив размером NxN, и "поворачивает" его на 90 градусов по часовой стрелке - т.е. меняет все числа внутри так, как если бы мы его повернули (специально оговаривается, что нельзя взять новый пустой массив и в него все правильно скопировать, нужно менять прямо в существующем).

Я давал эту задачу на предварительном ("телефонном", хотя их много лет как перестали делать по телефону) интервью, где задания даются попроще, и упор на то, чтобы проверить, что кандидат умеет грамотно писать код, находить в нем ошибки итд. В этом случае самое напрашивающееся решение - это понять, что при повороте члены массива переходят в друг друга по циклу четверками. Можно сделать два вложенных цикла по 1/4 массива, для каждого i,j аккуратно записать индексы тех 4 ячеек массива, которые меняются местами по циклу, и поменять их местами. Сложность в том, чтобы не запутаться в индексах, правильно разобраться с четными/нечетными по размеру массивами, правильно сделать цикл по 1/4 массива, который каждую четверку "задевает" ровно один раз.

Я давал эту задачу наверное раз 80, очень много. Чаще кандидаты успешно решали ее, хорошие минут за 10-15, некоторые за все время интервью (45 минут), некоторые не справлялись вообще. И только один раз из всех этих кандидат подумал секунд 20, поднял взгляд на меня и сказал: вращение это композиция двух зеркальных отражений. И написал два простейших (по сравнению с циклами "четверок") цикла, отражающие массив вначале по горизонтальной середине, потом по диагонали. Минут за 5, кажется.