об одной математической проблеме
Я давно уже не писал постов популярно-математического характера. Сейчас возникло желание это сделать. Цель данного поста вот какая. Есть одна знаменитая проблема в области теории групп (это раздел алгебры), которой я очень давно интересуюсь. Мне всегда казалось, что сформулировать её в более или менее элементарных терминах, не вводя каких-либо специальных понятий, почти невозможно. Однако на днях я придумал такую переформулировку, которая является совершенно строгой, точно отражает суть дела, и при этом может быть понята неспециалистом. В каком-то смысле можно сказать, что задача получилась похожей на "олимпиадную".
Основной текст идёт под "катом" -- я думаю, что математическая проблематика интересует далеко не всех. Эту запись нет смысла помещать в режиме "френдс-онли", поэтому я делаю её открытой. Я начну с формулировки известной задачи о "паросочетаниях". Имеется некоторое конечное число "юношей", которых будем обозначать в виде 1, 2, 3, ... и некоторое число "девушек", которых обозначим при помощи заглавных букв латинского алфавита: A, B, C, ... . Про каждого юношу известно, с какими из девушек он знаком. Скажем, пусть на этот счёт имеются такие данные:
1. D,F,H
2. A,G
3. D,E,F
4. F,G,H
5. A,B,C,H
6. B,C,D
7. B,G,H
В этих записях у каждого юноши перечислены все девушки, с которыми он знаком. Требуется узнать, возможно ли паросочетание, то есть может ли каждый из юношей выбрать себе в пару одну из знакомых ему девушек, чтобы при этом разные юноши не выбрали одну и ту же девушку.
В приведённом примере возможно, например, такое паросочетание: 1D 2A 3E 4F 5H 6B 7G (при этом не утверждается, что оно единственно). Сразу обычно бывает трудно сказать, есть ли такое паросочетание вообще. Задачу можно решить при помощи полного перебора вариантов, хотя это в общем случае ведёт к длинным вычислениям. Есть намного более эффективные способы, которые я здесь обсуждать не буду.
Пока что замечу, что паросочетания может и не найтись. Рассмотрим вот какой пример:
1. A,D
2. B,G
3. B,F
4. C,G
5. C,E
6. B,C
7. E,G
Обратим внимание на юношей под номерами 2, 4, 5, 6, 7. Никто из них не знаком ни с какой девушкой кроме B,C,E,G. Поэтому ясно, что уже для этих пяти юношей паросочетание, требуемое в условии задачи, невозможно. Наличие препятствий этого рода, когда можно выделить часть юношей, которым не хватает знакомых девушек просто по количеству, является необходимым и достаточным условием невозможности паросочетания. Если хотя бы одно такое препятствие есть, то паросочетание не подобрать; если же такие препятствия отсутствуют, то некоторое паросочетание всегда возможно. В этом состоит содержание известной Теоремы Холла о свадьбах.
Тот "матримониальный" сюжет, который здесь рассмотрен, является далеко не единственным. Можно, например, вместо "юношей" рассматривать тех, кто подал заявку на "биржу труда", а вместо "девушек" тут будут те специальности, по которым готов работать заявитель.
А сейчас я предлагаю рассмотреть некоторый вариант задачи о паросочетаниях -- так называемую "задачу о гареме" :) Сразу хочу попросить воздержаться здесь от "йумора", потому что все шутки на этот счёт являются, как это принято называть, "бояном" :)
В этой задаче имеются те же данные, только теперь юноша должен выбрать уже не одну знакомую ему девушку, а ровно двух. Эта задача легко сводится к предыдущей вот каким образом. Для каждого юноши рассмотрим его "клон" (или "виртуального двойника") с тем же набором знакомых девушек. Для такого удвоенного набора юношей рассмотрим обычную задачу о паросочетаниях -- с выбором одной девушки. Если такая задача решается, то решается и "задача о гареме" -- просто два "клона" соединяются в одно лицо :)
Здесь, как и выше, необходимым и достаточным условием возможности выбора является условие "количественного" типа. Это значит, что какие бы мы ни взяли k юношей из общего числа, на них должно прийтись по крайней мере 2k девушек, которые знакомы хотя бы с одним из выбранных юношей.
А теперь я хочу коротко обсудить задачи на тему "удвоения". Как-то я для олимпиады предложил такую задачу. Имеется целочисленная решётка на плоскости. В каждом узле решётки сидит блоха. В некоторый момент все блохи одновременно совершают прыжки на некоторое расстояние, не превосходящее какой-то фиксированной постоянной величины. Спрашивается, могло ли оказаться так, что в каждом узле окажется две блохи или более?
Ответ здесь отрицателен, но он не слишком очевиден. Поскольку общее число блох бесконечно, мы не можем прибегнуть к соображениям сохранения количества. В частности, если позволить блохам прыгать сколь угодно далеко, то тут "удвоение" очень легко организовать.
Сейчас я приведу простой пример похожей конфигурации, когда "удвоение популяции" возможно в силу очень простого плана перемещений. Как и в предыдущем примере с решёткой, сделаем так, чтобы в каждом "узле" сходились 4 соединения, но сейчас поступим вот как. Нарисуем на плоскости точку (это один из "узлов"), и от неё проведём в нижнюю сторону 4 отрезка. От каждого из получившихся концов этих отрезков (тоже "узлов") проведём по три идущих вниз новых отрезка -- так, чтобы никакие линии друг с другом не пересекались. Далее проделаем то же самое с концами только что проведённых отрезков, и так до бесконечности.
У нас получится при этом растущее вниз "дерево", напоминающее "корневую систему". Если мы поселим в каждом из "узлов" по одной "блохе", то далее план их "переселения" будет такой: самая верхняя блоха остаётся на своём месте, а все остальные ползут вверх по отрезку (такой всегда один). Легко понять, что в самом верхнем "узле" сойдутся пять блох, а в каждом из остальных окажется ровно по три (пришедшие снизу). То есть произойдёт желаемое "удвоение", и даже с "пеервыполнением плана" :) Этот способ можно слегка модифицировать, если задаться целью, чтобы в каждом "узле" оказалось ровно две блохи.
В общем случае, если имеется некий, как говорят математики, граф, то есть система "узлов", некоторые из которых между собой соединены, то можно ставить вопрос о том, возможен ли на этом графе описанный выше эффект "удвоения популяции". (Предполагается, что каждая из "блох" уходит от своего прежнего места на расстояние, не превосходящее фиксированной константы.) Итоговым ответом может быть "да" или "нет", и это обстоятельство отражает внутренние свойства рассматриваемого графа, который можно также назвать "сетью". Одно поверхностное наблюдение состоит в том, что если в графе имеется много "циклов", как в случае (двумерной) решётки (кстати, вместо неё можно брать и трёхмерную, и решётки более высоких размерностей -- ответ будет тот же), то "удвоение" невозможно. Если "циклов" в каком-то смысле "мало" (или нет вообще -- как в случае "дерева"), то "удвоить популяцию" можно.
Имеется огромное количество разного рода полезных критериев, при помощи которых граф ("сеть") можно протестировать на предмет возможности его "удвоить" в описанном выше смысле. В подавляющем большинстве случаев ответ оказывается возможно дать, так как срабатывает какой-нибудь из признаков. Однако попадаются редкие очень сложно устроенные графы, возникающие в недрах некоторых разделах математики, где ответ на вопрос получить никак не удаётся.
Следующая фраза адресована только специалистам; всем остальным не надо в неё даже вдумываться. Та проблема, о которой я здесь веду речь, имеет следующую математическую формулировку: является ли группа Ричарда Томпсона F аменабельной? (Предполагается, что нет, что соответствует возможности построить на ней "парадоксальное разбиение"; оно же -- "удвоение" на её графе Кэли.)
Описать ту интересную конфигурацию, которую я здесь прежде всего имею в виду, хотя и можно, но это описание, если его проводить во всех деталях, получилось бы очень длинным. Кроме того, представить себе результат зрительно будет всё равно затруднительно -- во всех случаях, когда это сделать легко, ответ на вопрос тоже даётся легко. Поэтому я ниже скажу об этой конфигурации лишь пару слов, а пока что хочу определить некие важные для дальнейшего рассмотрения простые геометрические объекты.
Мне потребуется понятие корневого двоичного дерева. Все такие "деревья" будут конечными -- в отличие от примера, рассмотренного выше. Каждое "дерево" надо понимать как некую картинку, которую очень легко нарисовать. Я снова попрошу принять соглашение, что все "деревья" будут расти не "снизу вверх", как это обычно происходит, а "сверху вниз" -- подобно корневым системам. Это всего лишь условность, но так в целом будет удобнее.
Итак, рисуем на плоскости точку -- это будет "корень" нашего "дерева". Далее из неё проводим два отрезка вниз -- один чуть влево, а второй -- чуть вправо. Эти два отрезка образуют фигуру, напоминающую русскую букву "Л" или греческую букву "Λ" -- "лямбда". Такую фигуру я буду в дальнейшем называть "кареткой" (за неимением лучшего термина); в английском языке часто используют слово "caret".
Итак, нарисована одна "каретка". У неё есть две нижние точки. К каждой из них разрешается пририсовать ещё по одной "каретке". Это надо сделать так, чтобы проводимые линии не пересекали друг друга. Этот процесс можно продолжать конечное число раз. К каким-то точкам мы пририсовываем снизу новые "каретки", а какие-то точки не "ветвим" вниз.
Каждое наше "дерево" будет состоять из конечного числа "кареток". (Далее я буду опускать кавычки.) Если такая каретка всего одна, то дерево в точности из неё и состоит. Если кареток две, то возможны два варианта. В обоих случаях есть самая верхняя каретка, а снизу к ней добавлена вторая, подсоединённая к концу либо левого, либо правого отрезка верхней каретки. Здесь и далее подразумевается, что верхние точки добавляемых снизу кареток совпадают с нижними концами отрезков верхних кареток. К сожалению, из-за несовершенства техники создания рисунков мне не удалось в полной мере добиться желаемого эффекта.
Вот какие две (отдельные) картинки возникают для деревьев из двух кареток:
/\ /\
/\ /\
Для того, чтобы окончательно стало понятно, что мы здесь определяем, я хотел бы перечислить все деревья, состоящие из трёх кареток. Их имеется ровно ПЯТЬ, и я их сейчас изображу. Тот, кто поймёт, почему это так, освоил определяемое понятие. Итак, вот рисунок, на котором перечислены все варианты. Самую верхнюю каретку я везде рисую более крупно -- размеры здесь условны. Надо иметь в виду, что соединительные линии здесь должны считаться сплошными, а не "пунктирными".
/\ /\ /\ /\ /\
/ \ / \ / \ / \ / \
/\ /\ /\ /\ /\ /\
/\ /\ /\ /\
На всякий случай я бы добавил ещё вот что. Прежде всего, все эти деревья можно нарисовать чуть иначе, продлив некоторые линии так, чтобы все их нижние концы располагались на одной прямой. Для верхней картинки у нас получится вот что:
/\ /\
/\ \ / /\
Легко понять, что нижних вершин у каждого из деревьев ровно три (вообще, если кареток k, то нижних вершин, называемых листьями, ровно на единицу больше, то есть всего k+1). Если мы сопоставим этим точкам буквы a,b,c (слева направо) в каждой из картинок, то деревьям этим будут естественным образом соответствовать следующие скобочные выражения: (ab)c для картинки слева и a(bc) для картинки справа. Можно было бы деревья вообще не рассматривать, а обойтись одними такими выражениями, но я исходил из того, что привлечение деревьев способствует большей наглядности.
Вот какая получается ситуация для деревьев с тремя каретками, в которых все линии продолжены (на средней картинке мне пришлось чуть-чуть раздвинуть верхнюю каретку посередине, дабы избежать слияния линий):
/\ /\ / \ /\ /\
/ \ / \ / \ / \ / \
/\ \ /\ \ /\ /\ / /\ / /\
/\ \ \ / /\ \ / \ / \ / /\ \ / / /\
Здесь у каждого дерева нижние точки можно закодировать буквами a,b,c,d, и тогда получается пять скобочных выражений: ((ab)c)d, (a(bc))d, (ab)(cd), a((bc)d), a(b(cd)).
А сколько деревьев будет, если они состоят из четырёх кареток? Можно проверить, что ровно 14. Вообще, количество таких деревьев с n каретками есть n-ое число Каталана, находимое по формуле c_{n}=(2n)!/(n!(n+1)!).
Заметим, что мы можем также рассматривать и случай, когда число кареток равно нулю; такое дерево имеется в точности одно и состоит оно из одной точки. Это будет важно для дальнейшего.
Последовательность чисел возникает такая: 1, 1, 2, 5, 14, 42, 132, 429, ..., причём нумерация начинается с числа c_{0}=1. Например, 429 -- это c_{7}, то есть количество деревьев из семи кареток.
Сейчас мы введём понятие леса. Под этим будет пониматься несколько деревьев, следующих друг за другом. Эти деревья могут иметь любое число кареток -- не обязательно одно и то же; в том числе они могут состоять из одной точки. Лес может быть нарисован так, что все верхние точки деревьев будут лежать на одной горизонтальной прямой, хотя соблюдение этого требования не считается обязательным. Вот пример леса из семи деревьев:
/\ * /\ /\ * / \ /\
/\ /\ /\ /\ /\
/\ /\
/\
Здесь второе и пятое деревья состоят из одной точки, изображённой в виде "звёздочки". Четвёртое дерево состоит из одной каретки, первое и седьмое -- из двух, третье -- из трёх, шестое -- из пяти.
Всякое дерево также считается частным случаем леса, который из одного этого дерева и состоит.
Представим себе какой-то лес и два соседних дерева в нём. Можно превратить их в одно, добавляя сверху к ним одну каретку, нижние точки которой подсоединены к верхним точкам этих деревьев. Получается лес, у которого число деревьев стало на единицу меньше. Продолжая соединять при помощи кареток какие-то соседние деревья (что можно делать многими способами), мы придём к одному дереву. Возникает вопрос: а сколькими способами можно заданный лес превратить в одно дерево? Ответ на этот вопрос очень прост.
В самом деле, представим себе тот лес из семи деревьев, который мы нарисовали выше. Превратим его каким-то способом в дерево, добавляя каретки сверху. У получившегося дерева раскрасим все добавленные нами каретки в красный цвет. При этом получается дерево, у которого число кареток ровно на единицу меньше числа деревьев, составляющих лес. В нашем случае таких кареток будет ровно 6. Легко также понять, что можно взять любое дерево из шести кареток и подсоединить его к нашему лесу сверху, что превратит его в дерево. То есть количество способов превратить наш лес в дерево будет равно в точности количеству деревьев с шестью каретками. А это число равно c_{6}=132.
А теперь перейдём непосредственно к той формулировке, ради которой всё затевалось. Прежде всего, зафиксируем некоторое число k и будем рассматривать все леса, состоящие из k деревьев. (Для конкретности, если кто желает, можно представлять себе значение k=5, если не оговорено противное.) Через n обозначим общее число кареток, входящих в рассматриваемый нами лес. Например, для того леса, который был нарисован выше, имеем значения k=7, n=13. (Случай n=0 нами тоже допускается -- такой лес будет просто состоять из k отдельных "звёздочек".)
Итак, при выбранных двух значениях k и n рассмотрим все леса из k деревьев с общим числом кареток, равным n. Их имеется конечное число, и при желании можно все такие леса нарисовать -- например, каждый на отдельном листе бумаги. Можно также указать явную формулу для подсчёта их количества. Эти леса будут нашими "персонажами" (их при желании можно уподобить "юношам" из "задачи о гареме"). Каждый "персонаж" заказывает себе "шляпу" -- то есть тот способ превратить лес в дерево, который состоит в добавлении кареток (красного цвета) сверху. Как мы знаем, всего имеется ровно c_{k-1} способов сделать такой "заказ". Например, при k=4 имеется ровно 5 способов, которые соответствуют деревьям из трёх кареток, изображённых на одном из рисунков выше. А при k=5 способов будет уже 14, то есть довольно много.
Заметим, что у каждого нашего "персонажа" способы выбора в точности одни и те же; поскольку самих "персонажей" может быть очень много, какие-то из них неизбежно закажут "шляпу" одного и того же "фасона", что следует считать совершенно нормальным явлением. Можно даже рассмотреть случай, когда все сделали один и тот же заказ. В этом случае все "персонажи" с надетыми шляпами будут выглядеть по-разному, потому что с них всех можно просто снять одинаковые "шляпы".
Но теперь наложим вот какое условие: пусть каждый наш "персонаж" хочет выбрать себе не одну шляпу, а ДВЕ (на всякий случай оговорим, что количество экземпляров "шляп" у нас очень велико, и их всем хватает). Далее, будем считать, что каждый надевает на себя сначала одну "шляпу", а потом другую, и в каждом случае делает "снимок" себя с надетой "шляпой", который выглядит как некоторое дерево. Причём на снимке -- это здесь самое главное -- уже не видно, где кончается "шляпа", и где начинается надевший её "персонаж": всё сливается в единое целое.
Сейчас рекомендуется пронаблюдать на примере очень простое явление, состоящее в том, что разные "персонажи", заказавшие себе разные "шляпы", могут в них выглядеть на снимках совершенно одинаково. Я здесь возьму за основу случай k=4, когда леса состоят из четырёх деревьев. Пусть один из наших "персонажей" имеет вид * /\ * * (здесь всего одна каретка), а второй пусть имеет вид * * * /\ (с тем же числом кареток). Теперь заглянем в наш "шляпный салон", где изображены все 5 деревьев из трёх кареток -- я не буду их здесь перерисовывать. Допустим, что первый "персонаж" заказал третью слева "шляпу", а второй -- вторую слева. Как будут при этом они выглядеть, каждый в своей "шляпе"? Я предлагаю осмыслить этот момент аккуратно и прийти к выводу, что выглядеть оба будут совершенно одинаково, а именно так:
/\
/ \
/\ /\
/\
Если кому-то покажется, что это не так, то просьба разобраться; можно задать вопрос в обсуждении. Чтобы было более убедительно, я предлагаю провести такой мысленный эксперимент: нарисовать эту картинку дважды и сначала закрасить белым цветом контур "шляпы" номер 3 на этом рисунке -- это будет верхняя каретка и две примыкающие к ней. Если мы посмотрим на то, что осталось, то увидим в точности следующее: * /\ * * -- а это и есть наш первый "персонаж". При этом надо иметь в виду, что "звёздочки" -- это самые нижние точки некоторых кареток, которые в белый цвет как бы не раскрашиваются.
Аналогично, если мы на отдельном рисунке раскрасим у того же изображения в белый цвет контур "шляпы" номер 2 (начиная сверху), то останется * * * /\ -- это второй наш "персонаж". Здесь надо заметить, что рассмотренный пример не является каким-то уникальным. Наоборот, он очень типичен, потому что такие совпадения изображений весьма часты. Мы же ставим целью осуществить такой выбор двух "шляп" для каждого нашего "персонажа", чтобы среди сделанных "снимков" не было никаких совпадений. Вопрос в том, можно ли этого добиться.
Прежде всего, пусть k=3 (меньшие значения не имеет смысла рассматривать). Тут "шляп" всего две, и поэтому каждый именно их и выбирает. Очевидно, что * /\ и /\ * будут выглядеть совершенно одинаково в некоторых "шляпах", а это нас не устраивает.
Случай k=4 уже довольно сложен, и могло показаться, что для него есть шанс организовать требуемый выбор, поскольку выбирается две "шляпы" из пяти. Дело в том, что если выбор невозможен, то в силу соображений типа Теоремы Холла, о которой говорилась выше, должна существовать такая группа "юношей" для которых количественно не хватило бы "девушек". В нашем случае это означало бы, что можно предъявить некоторый набор из, скажем, N "персонажей", надеть каждого из них каждую из пяти "шляп" и получить в итоге 5N снимков. На них, конечно, имеется много повторений, и если их устранить, то различных снимков окажется существенно меньше. Не очень легко поверить в то, что это число может оказаться строго меньше 2N. Однако такие примеры возможны, что выяснилось вообще-то буквально на днях :) При этом в построенных примерах велико как число "кареток" (более 100 с лишним), так и число привлекаемых "персонажей" (оно составляет где-то порядка 10 в пятидесятой степени :))
Для k=5, где каждый выбирает две шляпы из 14, уже ничего не известно. Конечно, с очень большим трудом верится в то, что при анализе сделанных 14N снимков окажется так много повторений, что различных вариантов снимков будет менее 2N. Но даже если это так (во что я лично верю с трудом), то можно брать большие значения k.
Таким образом, для решения проблемы достаточно сделать следующее. Предъявить значение k (предположительно, подойдёт уже k=5), рассмотреть все леса, состоящие из k деревьев и каждому из них по какому-то фиксированному правилу (скорее всего, весьма "изощрённому") сопоставить какие то две "шляпы", то есть деревья из k-1 каретки (их общее число составляет c_{k-1}). При этом требуется, чтобы все получаемые при этом "изображения", то есть деревья, возникающие при "навешивании" сверху "шляп", оказались попарно различными.
Если предъявить такое значение можно, то это на математическом языке будет означать, что группа Ричарда Томпсона F является неаменабельной. Если никакое значение не приводит к удачному выбору "шляп" (или положительному решению соответствующей "задачи о гареме"), то группа является аменабельной.
Комментарии к данному посту отключены, а обсуждение проводится здесь. Я при этом прошу воздержаться от "сакраментальных" вопросов типа "а зачем это нужно" или "а где это можно применить". Если кто-то вник в содержание, и предмет рассмотрения показался интересным, то это уже даёт ответ на оба вопроса, ну а если нет, то вопросы излишни :)
Основной текст идёт под "катом" -- я думаю, что математическая проблематика интересует далеко не всех. Эту запись нет смысла помещать в режиме "френдс-онли", поэтому я делаю её открытой. Я начну с формулировки известной задачи о "паросочетаниях". Имеется некоторое конечное число "юношей", которых будем обозначать в виде 1, 2, 3, ... и некоторое число "девушек", которых обозначим при помощи заглавных букв латинского алфавита: A, B, C, ... . Про каждого юношу известно, с какими из девушек он знаком. Скажем, пусть на этот счёт имеются такие данные:
1. D,F,H
2. A,G
3. D,E,F
4. F,G,H
5. A,B,C,H
6. B,C,D
7. B,G,H
В этих записях у каждого юноши перечислены все девушки, с которыми он знаком. Требуется узнать, возможно ли паросочетание, то есть может ли каждый из юношей выбрать себе в пару одну из знакомых ему девушек, чтобы при этом разные юноши не выбрали одну и ту же девушку.
В приведённом примере возможно, например, такое паросочетание: 1D 2A 3E 4F 5H 6B 7G (при этом не утверждается, что оно единственно). Сразу обычно бывает трудно сказать, есть ли такое паросочетание вообще. Задачу можно решить при помощи полного перебора вариантов, хотя это в общем случае ведёт к длинным вычислениям. Есть намного более эффективные способы, которые я здесь обсуждать не буду.
Пока что замечу, что паросочетания может и не найтись. Рассмотрим вот какой пример:
1. A,D
2. B,G
3. B,F
4. C,G
5. C,E
6. B,C
7. E,G
Обратим внимание на юношей под номерами 2, 4, 5, 6, 7. Никто из них не знаком ни с какой девушкой кроме B,C,E,G. Поэтому ясно, что уже для этих пяти юношей паросочетание, требуемое в условии задачи, невозможно. Наличие препятствий этого рода, когда можно выделить часть юношей, которым не хватает знакомых девушек просто по количеству, является необходимым и достаточным условием невозможности паросочетания. Если хотя бы одно такое препятствие есть, то паросочетание не подобрать; если же такие препятствия отсутствуют, то некоторое паросочетание всегда возможно. В этом состоит содержание известной Теоремы Холла о свадьбах.
Тот "матримониальный" сюжет, который здесь рассмотрен, является далеко не единственным. Можно, например, вместо "юношей" рассматривать тех, кто подал заявку на "биржу труда", а вместо "девушек" тут будут те специальности, по которым готов работать заявитель.
А сейчас я предлагаю рассмотреть некоторый вариант задачи о паросочетаниях -- так называемую "задачу о гареме" :) Сразу хочу попросить воздержаться здесь от "йумора", потому что все шутки на этот счёт являются, как это принято называть, "бояном" :)
В этой задаче имеются те же данные, только теперь юноша должен выбрать уже не одну знакомую ему девушку, а ровно двух. Эта задача легко сводится к предыдущей вот каким образом. Для каждого юноши рассмотрим его "клон" (или "виртуального двойника") с тем же набором знакомых девушек. Для такого удвоенного набора юношей рассмотрим обычную задачу о паросочетаниях -- с выбором одной девушки. Если такая задача решается, то решается и "задача о гареме" -- просто два "клона" соединяются в одно лицо :)
Здесь, как и выше, необходимым и достаточным условием возможности выбора является условие "количественного" типа. Это значит, что какие бы мы ни взяли k юношей из общего числа, на них должно прийтись по крайней мере 2k девушек, которые знакомы хотя бы с одним из выбранных юношей.
А теперь я хочу коротко обсудить задачи на тему "удвоения". Как-то я для олимпиады предложил такую задачу. Имеется целочисленная решётка на плоскости. В каждом узле решётки сидит блоха. В некоторый момент все блохи одновременно совершают прыжки на некоторое расстояние, не превосходящее какой-то фиксированной постоянной величины. Спрашивается, могло ли оказаться так, что в каждом узле окажется две блохи или более?
Ответ здесь отрицателен, но он не слишком очевиден. Поскольку общее число блох бесконечно, мы не можем прибегнуть к соображениям сохранения количества. В частности, если позволить блохам прыгать сколь угодно далеко, то тут "удвоение" очень легко организовать.
Сейчас я приведу простой пример похожей конфигурации, когда "удвоение популяции" возможно в силу очень простого плана перемещений. Как и в предыдущем примере с решёткой, сделаем так, чтобы в каждом "узле" сходились 4 соединения, но сейчас поступим вот как. Нарисуем на плоскости точку (это один из "узлов"), и от неё проведём в нижнюю сторону 4 отрезка. От каждого из получившихся концов этих отрезков (тоже "узлов") проведём по три идущих вниз новых отрезка -- так, чтобы никакие линии друг с другом не пересекались. Далее проделаем то же самое с концами только что проведённых отрезков, и так до бесконечности.
У нас получится при этом растущее вниз "дерево", напоминающее "корневую систему". Если мы поселим в каждом из "узлов" по одной "блохе", то далее план их "переселения" будет такой: самая верхняя блоха остаётся на своём месте, а все остальные ползут вверх по отрезку (такой всегда один). Легко понять, что в самом верхнем "узле" сойдутся пять блох, а в каждом из остальных окажется ровно по три (пришедшие снизу). То есть произойдёт желаемое "удвоение", и даже с "пеервыполнением плана" :) Этот способ можно слегка модифицировать, если задаться целью, чтобы в каждом "узле" оказалось ровно две блохи.
В общем случае, если имеется некий, как говорят математики, граф, то есть система "узлов", некоторые из которых между собой соединены, то можно ставить вопрос о том, возможен ли на этом графе описанный выше эффект "удвоения популяции". (Предполагается, что каждая из "блох" уходит от своего прежнего места на расстояние, не превосходящее фиксированной константы.) Итоговым ответом может быть "да" или "нет", и это обстоятельство отражает внутренние свойства рассматриваемого графа, который можно также назвать "сетью". Одно поверхностное наблюдение состоит в том, что если в графе имеется много "циклов", как в случае (двумерной) решётки (кстати, вместо неё можно брать и трёхмерную, и решётки более высоких размерностей -- ответ будет тот же), то "удвоение" невозможно. Если "циклов" в каком-то смысле "мало" (или нет вообще -- как в случае "дерева"), то "удвоить популяцию" можно.
Имеется огромное количество разного рода полезных критериев, при помощи которых граф ("сеть") можно протестировать на предмет возможности его "удвоить" в описанном выше смысле. В подавляющем большинстве случаев ответ оказывается возможно дать, так как срабатывает какой-нибудь из признаков. Однако попадаются редкие очень сложно устроенные графы, возникающие в недрах некоторых разделах математики, где ответ на вопрос получить никак не удаётся.
Следующая фраза адресована только специалистам; всем остальным не надо в неё даже вдумываться. Та проблема, о которой я здесь веду речь, имеет следующую математическую формулировку: является ли группа Ричарда Томпсона F аменабельной? (Предполагается, что нет, что соответствует возможности построить на ней "парадоксальное разбиение"; оно же -- "удвоение" на её графе Кэли.)
Описать ту интересную конфигурацию, которую я здесь прежде всего имею в виду, хотя и можно, но это описание, если его проводить во всех деталях, получилось бы очень длинным. Кроме того, представить себе результат зрительно будет всё равно затруднительно -- во всех случаях, когда это сделать легко, ответ на вопрос тоже даётся легко. Поэтому я ниже скажу об этой конфигурации лишь пару слов, а пока что хочу определить некие важные для дальнейшего рассмотрения простые геометрические объекты.
Мне потребуется понятие корневого двоичного дерева. Все такие "деревья" будут конечными -- в отличие от примера, рассмотренного выше. Каждое "дерево" надо понимать как некую картинку, которую очень легко нарисовать. Я снова попрошу принять соглашение, что все "деревья" будут расти не "снизу вверх", как это обычно происходит, а "сверху вниз" -- подобно корневым системам. Это всего лишь условность, но так в целом будет удобнее.
Итак, рисуем на плоскости точку -- это будет "корень" нашего "дерева". Далее из неё проводим два отрезка вниз -- один чуть влево, а второй -- чуть вправо. Эти два отрезка образуют фигуру, напоминающую русскую букву "Л" или греческую букву "Λ" -- "лямбда". Такую фигуру я буду в дальнейшем называть "кареткой" (за неимением лучшего термина); в английском языке часто используют слово "caret".
Итак, нарисована одна "каретка". У неё есть две нижние точки. К каждой из них разрешается пририсовать ещё по одной "каретке". Это надо сделать так, чтобы проводимые линии не пересекали друг друга. Этот процесс можно продолжать конечное число раз. К каким-то точкам мы пририсовываем снизу новые "каретки", а какие-то точки не "ветвим" вниз.
Каждое наше "дерево" будет состоять из конечного числа "кареток". (Далее я буду опускать кавычки.) Если такая каретка всего одна, то дерево в точности из неё и состоит. Если кареток две, то возможны два варианта. В обоих случаях есть самая верхняя каретка, а снизу к ней добавлена вторая, подсоединённая к концу либо левого, либо правого отрезка верхней каретки. Здесь и далее подразумевается, что верхние точки добавляемых снизу кареток совпадают с нижними концами отрезков верхних кареток. К сожалению, из-за несовершенства техники создания рисунков мне не удалось в полной мере добиться желаемого эффекта.
Вот какие две (отдельные) картинки возникают для деревьев из двух кареток:
/\ /\
/\ /\
Для того, чтобы окончательно стало понятно, что мы здесь определяем, я хотел бы перечислить все деревья, состоящие из трёх кареток. Их имеется ровно ПЯТЬ, и я их сейчас изображу. Тот, кто поймёт, почему это так, освоил определяемое понятие. Итак, вот рисунок, на котором перечислены все варианты. Самую верхнюю каретку я везде рисую более крупно -- размеры здесь условны. Надо иметь в виду, что соединительные линии здесь должны считаться сплошными, а не "пунктирными".
/\ /\ /\ /\ /\
/ \ / \ / \ / \ / \
/\ /\ /\ /\ /\ /\
/\ /\ /\ /\
На всякий случай я бы добавил ещё вот что. Прежде всего, все эти деревья можно нарисовать чуть иначе, продлив некоторые линии так, чтобы все их нижние концы располагались на одной прямой. Для верхней картинки у нас получится вот что:
/\ /\
/\ \ / /\
Легко понять, что нижних вершин у каждого из деревьев ровно три (вообще, если кареток k, то нижних вершин, называемых листьями, ровно на единицу больше, то есть всего k+1). Если мы сопоставим этим точкам буквы a,b,c (слева направо) в каждой из картинок, то деревьям этим будут естественным образом соответствовать следующие скобочные выражения: (ab)c для картинки слева и a(bc) для картинки справа. Можно было бы деревья вообще не рассматривать, а обойтись одними такими выражениями, но я исходил из того, что привлечение деревьев способствует большей наглядности.
Вот какая получается ситуация для деревьев с тремя каретками, в которых все линии продолжены (на средней картинке мне пришлось чуть-чуть раздвинуть верхнюю каретку посередине, дабы избежать слияния линий):
/\ /\ / \ /\ /\
/ \ / \ / \ / \ / \
/\ \ /\ \ /\ /\ / /\ / /\
/\ \ \ / /\ \ / \ / \ / /\ \ / / /\
Здесь у каждого дерева нижние точки можно закодировать буквами a,b,c,d, и тогда получается пять скобочных выражений: ((ab)c)d, (a(bc))d, (ab)(cd), a((bc)d), a(b(cd)).
А сколько деревьев будет, если они состоят из четырёх кареток? Можно проверить, что ровно 14. Вообще, количество таких деревьев с n каретками есть n-ое число Каталана, находимое по формуле c_{n}=(2n)!/(n!(n+1)!).
Заметим, что мы можем также рассматривать и случай, когда число кареток равно нулю; такое дерево имеется в точности одно и состоит оно из одной точки. Это будет важно для дальнейшего.
Последовательность чисел возникает такая: 1, 1, 2, 5, 14, 42, 132, 429, ..., причём нумерация начинается с числа c_{0}=1. Например, 429 -- это c_{7}, то есть количество деревьев из семи кареток.
Сейчас мы введём понятие леса. Под этим будет пониматься несколько деревьев, следующих друг за другом. Эти деревья могут иметь любое число кареток -- не обязательно одно и то же; в том числе они могут состоять из одной точки. Лес может быть нарисован так, что все верхние точки деревьев будут лежать на одной горизонтальной прямой, хотя соблюдение этого требования не считается обязательным. Вот пример леса из семи деревьев:
/\ * /\ /\ * / \ /\
/\ /\ /\ /\ /\
/\ /\
/\
Здесь второе и пятое деревья состоят из одной точки, изображённой в виде "звёздочки". Четвёртое дерево состоит из одной каретки, первое и седьмое -- из двух, третье -- из трёх, шестое -- из пяти.
Всякое дерево также считается частным случаем леса, который из одного этого дерева и состоит.
Представим себе какой-то лес и два соседних дерева в нём. Можно превратить их в одно, добавляя сверху к ним одну каретку, нижние точки которой подсоединены к верхним точкам этих деревьев. Получается лес, у которого число деревьев стало на единицу меньше. Продолжая соединять при помощи кареток какие-то соседние деревья (что можно делать многими способами), мы придём к одному дереву. Возникает вопрос: а сколькими способами можно заданный лес превратить в одно дерево? Ответ на этот вопрос очень прост.
В самом деле, представим себе тот лес из семи деревьев, который мы нарисовали выше. Превратим его каким-то способом в дерево, добавляя каретки сверху. У получившегося дерева раскрасим все добавленные нами каретки в красный цвет. При этом получается дерево, у которого число кареток ровно на единицу меньше числа деревьев, составляющих лес. В нашем случае таких кареток будет ровно 6. Легко также понять, что можно взять любое дерево из шести кареток и подсоединить его к нашему лесу сверху, что превратит его в дерево. То есть количество способов превратить наш лес в дерево будет равно в точности количеству деревьев с шестью каретками. А это число равно c_{6}=132.
А теперь перейдём непосредственно к той формулировке, ради которой всё затевалось. Прежде всего, зафиксируем некоторое число k и будем рассматривать все леса, состоящие из k деревьев. (Для конкретности, если кто желает, можно представлять себе значение k=5, если не оговорено противное.) Через n обозначим общее число кареток, входящих в рассматриваемый нами лес. Например, для того леса, который был нарисован выше, имеем значения k=7, n=13. (Случай n=0 нами тоже допускается -- такой лес будет просто состоять из k отдельных "звёздочек".)
Итак, при выбранных двух значениях k и n рассмотрим все леса из k деревьев с общим числом кареток, равным n. Их имеется конечное число, и при желании можно все такие леса нарисовать -- например, каждый на отдельном листе бумаги. Можно также указать явную формулу для подсчёта их количества. Эти леса будут нашими "персонажами" (их при желании можно уподобить "юношам" из "задачи о гареме"). Каждый "персонаж" заказывает себе "шляпу" -- то есть тот способ превратить лес в дерево, который состоит в добавлении кареток (красного цвета) сверху. Как мы знаем, всего имеется ровно c_{k-1} способов сделать такой "заказ". Например, при k=4 имеется ровно 5 способов, которые соответствуют деревьям из трёх кареток, изображённых на одном из рисунков выше. А при k=5 способов будет уже 14, то есть довольно много.
Заметим, что у каждого нашего "персонажа" способы выбора в точности одни и те же; поскольку самих "персонажей" может быть очень много, какие-то из них неизбежно закажут "шляпу" одного и того же "фасона", что следует считать совершенно нормальным явлением. Можно даже рассмотреть случай, когда все сделали один и тот же заказ. В этом случае все "персонажи" с надетыми шляпами будут выглядеть по-разному, потому что с них всех можно просто снять одинаковые "шляпы".
Но теперь наложим вот какое условие: пусть каждый наш "персонаж" хочет выбрать себе не одну шляпу, а ДВЕ (на всякий случай оговорим, что количество экземпляров "шляп" у нас очень велико, и их всем хватает). Далее, будем считать, что каждый надевает на себя сначала одну "шляпу", а потом другую, и в каждом случае делает "снимок" себя с надетой "шляпой", который выглядит как некоторое дерево. Причём на снимке -- это здесь самое главное -- уже не видно, где кончается "шляпа", и где начинается надевший её "персонаж": всё сливается в единое целое.
Сейчас рекомендуется пронаблюдать на примере очень простое явление, состоящее в том, что разные "персонажи", заказавшие себе разные "шляпы", могут в них выглядеть на снимках совершенно одинаково. Я здесь возьму за основу случай k=4, когда леса состоят из четырёх деревьев. Пусть один из наших "персонажей" имеет вид * /\ * * (здесь всего одна каретка), а второй пусть имеет вид * * * /\ (с тем же числом кареток). Теперь заглянем в наш "шляпный салон", где изображены все 5 деревьев из трёх кареток -- я не буду их здесь перерисовывать. Допустим, что первый "персонаж" заказал третью слева "шляпу", а второй -- вторую слева. Как будут при этом они выглядеть, каждый в своей "шляпе"? Я предлагаю осмыслить этот момент аккуратно и прийти к выводу, что выглядеть оба будут совершенно одинаково, а именно так:
/\
/ \
/\ /\
/\
Если кому-то покажется, что это не так, то просьба разобраться; можно задать вопрос в обсуждении. Чтобы было более убедительно, я предлагаю провести такой мысленный эксперимент: нарисовать эту картинку дважды и сначала закрасить белым цветом контур "шляпы" номер 3 на этом рисунке -- это будет верхняя каретка и две примыкающие к ней. Если мы посмотрим на то, что осталось, то увидим в точности следующее: * /\ * * -- а это и есть наш первый "персонаж". При этом надо иметь в виду, что "звёздочки" -- это самые нижние точки некоторых кареток, которые в белый цвет как бы не раскрашиваются.
Аналогично, если мы на отдельном рисунке раскрасим у того же изображения в белый цвет контур "шляпы" номер 2 (начиная сверху), то останется * * * /\ -- это второй наш "персонаж". Здесь надо заметить, что рассмотренный пример не является каким-то уникальным. Наоборот, он очень типичен, потому что такие совпадения изображений весьма часты. Мы же ставим целью осуществить такой выбор двух "шляп" для каждого нашего "персонажа", чтобы среди сделанных "снимков" не было никаких совпадений. Вопрос в том, можно ли этого добиться.
Прежде всего, пусть k=3 (меньшие значения не имеет смысла рассматривать). Тут "шляп" всего две, и поэтому каждый именно их и выбирает. Очевидно, что * /\ и /\ * будут выглядеть совершенно одинаково в некоторых "шляпах", а это нас не устраивает.
Случай k=4 уже довольно сложен, и могло показаться, что для него есть шанс организовать требуемый выбор, поскольку выбирается две "шляпы" из пяти. Дело в том, что если выбор невозможен, то в силу соображений типа Теоремы Холла, о которой говорилась выше, должна существовать такая группа "юношей" для которых количественно не хватило бы "девушек". В нашем случае это означало бы, что можно предъявить некоторый набор из, скажем, N "персонажей", надеть каждого из них каждую из пяти "шляп" и получить в итоге 5N снимков. На них, конечно, имеется много повторений, и если их устранить, то различных снимков окажется существенно меньше. Не очень легко поверить в то, что это число может оказаться строго меньше 2N. Однако такие примеры возможны, что выяснилось вообще-то буквально на днях :) При этом в построенных примерах велико как число "кареток" (более 100 с лишним), так и число привлекаемых "персонажей" (оно составляет где-то порядка 10 в пятидесятой степени :))
Для k=5, где каждый выбирает две шляпы из 14, уже ничего не известно. Конечно, с очень большим трудом верится в то, что при анализе сделанных 14N снимков окажется так много повторений, что различных вариантов снимков будет менее 2N. Но даже если это так (во что я лично верю с трудом), то можно брать большие значения k.
Таким образом, для решения проблемы достаточно сделать следующее. Предъявить значение k (предположительно, подойдёт уже k=5), рассмотреть все леса, состоящие из k деревьев и каждому из них по какому-то фиксированному правилу (скорее всего, весьма "изощрённому") сопоставить какие то две "шляпы", то есть деревья из k-1 каретки (их общее число составляет c_{k-1}). При этом требуется, чтобы все получаемые при этом "изображения", то есть деревья, возникающие при "навешивании" сверху "шляп", оказались попарно различными.
Если предъявить такое значение можно, то это на математическом языке будет означать, что группа Ричарда Томпсона F является неаменабельной. Если никакое значение не приводит к удачному выбору "шляп" (или положительному решению соответствующей "задачи о гареме"), то группа является аменабельной.
Комментарии к данному посту отключены, а обсуждение проводится здесь. Я при этом прошу воздержаться от "сакраментальных" вопросов типа "а зачем это нужно" или "а где это можно применить". Если кто-то вник в содержание, и предмет рассмотрения показался интересным, то это уже даёт ответ на оба вопроса, ну а если нет, то вопросы излишни :)