Falcão (falcao) wrote,
Falcão
falcao

  • Mood:
  • Music:

мини-плоскости

Купил я себе сегодня новую клавиатуру (всего за 200 рублей :)) Старая была вполне работоспособна, но на ней стёрлись многие буквы, и меня это постоянно раздражало. Так что теперь я могу печатать быстрее, чем раньше. И под это дело у меня возникла мысль, а не написать ли новый пост? Тем более, что тема "подвернулась" сама собой: сегодня я вспомнил об одной старой задаче, которая предлагалась в самом первом выпуске журнала "Квант". Было это в далёком 1970 году. Задача достаточно непростая, и её решение, приведённое несколькими номерами позже, было длинным и сложным. Но сама постановка задачи весьма проста, и смысл должен быть понятен каждому. Прежде всего, вот ссылка на тот номер журнала, в котором приведено решение. Речь идёт о задаче М5. Там, среди прочего, даются и "занимательные" переформулировки, но я не буду из них исходить, и вообще по этой ссылке ходить не обязательно. Сейчас всё будет изложено "с нуля".

Журнал у меня с некоторого времени почти весь "под замком", но посты на математическую тему я обычно делаю открытыми для всех. Итак, приступим. Этот пост можно ещё "приурочить" к началу учебного года, хотя у меня пока продолжается отпуск :)

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

(А1) Через любые две различные точки проходит одна и только одна прямая.

Если рассматривать "обычные" точки и прямые, то эта аксиома для всех должна быть "наглядно-очевидной". Сейчас я упомяну ещё об одной аксиоме -- она во многом выглядит ещё проще, и у неё очень простой смысл. Далее мы её даже почти не будем привлекать. Важно здесь то, что этими двумя аксиомами мы в данном изложении и ограничимся. Интерес представляет то, что даже из таких совсем простых положений можно извлечь весьма интересные и нетривиально доказываемые факты.

(А2) Существуют по крайней мере три точки, не лежащие на одной прямой.

Смысл у этой аксиомы очень простой: не все точки лежат на одной и той же прямой. Этим постулируется, что мы имеем дело не с одной прямой, а с чем-то вроде плоскости. В курсе планиметрии именно эти аксиомы излагаются в самом начале.

Возникает вопрос: что эти две простые аксиомы могут описывать? Здесь надо абстрагироваться от обычной геометрии и представить себе следующее. "Точками" разрешается называть любые объекты. Например, роль "точек" могут играть люди, составляющие некоторую компанию. А "прямыми" будут называться те или иные совокупности точек. Например, в случае людей это могут быть какие-нибудь комиссии, создаваемые из отдельных участников.

Всем известно, что на плоскости имеется бесконечное число точек. Нас же будет интересовать случай, когда общая совокупность "точек", которую мы рассматриваем, конечна. Скажем, речь идёт об учениках школьного класса. Пусть в этом классе организовано несколько кружков, или комиссий, или чего-то ещё. Будем тогда говорить, что совокупность учеников, входящих в одну такую "комиссию", представляет собой "прямую".

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

То, что у нас получилось, будет называться "мини-плоскостью", если при этом выполняются условия А1 и А2. Второе условие и его проверка совсем очевидны: не должно быть линии, проходящей через все наши точки. Что касается А1, то выполнение этого условия означает, что для любых двух (различных) участников у нас есть ровно одна линия, на которой оба они находятся.

Приведём простейший пример "мини-плоскости", например, из 10 точек. Расположим 9 точек вдоль одной прямой, а десятую точку поместим вне этой прямой и соединим линиями с каждой из девяти точек. Получится схема, в которой точек 10, и линий нарисовано тоже 10.

Можно привести примеры, когда линий будет больше, чем точек. В частности, аксиомы А1 и А2 не запрещают проводить линию всего лишь через одну точку. Это ничему не помогает и не мешает -- просто увеличивает число линий. Если такие линии есть, то их можно просто стереть, сравнивая далее количество линий и количество точек. Так вот, оказывается, что на "мини-плоскости" линий всегда имеется столько же, сколько точек, или больше. Это и есть то утверждение, о котором далее пойдёт речь, и это точная переформулировка задачи из "Кванта".

Далее я намерен изложить её решение в такой форме, чтобы оно содержало минимум формул и обозначений, и чтобы смысл был наиболее "прозрачен" для читателя. Я буду основываться на доказательстве, идею которого предложил известный американский математик Джон Конвей. Сам же доказываемый факт был впервые установлен в работе 1948 года, авторами которой были де Брёйн и Эрдёш.

Кратко повторим условие. Имеется "мини-плоскость", то есть конечное множество "точек". Некоторые совокупности точек объявляются "прямыми" (или "линиями"), и при этом известно, что выполняются условия А1 и А2. Это значит, что через любые две точки проходит ровно одна линия, и при этом не возникает "вырожденного" случая, когда все точки лежат на одной линии. Требуется доказать, что линий проведено не меньше, чем было точек.

Я сразу хотел бы предостеречь читателя от поисков "совсем очевидного" доказательства. Можно попробовать подумать, но с целью убедиться в том, что совсем лёгкие способы рассуждения (типа индукции), скорее всего, не проходят.

Введём обозначения: пусть далее n есть число точек, а m -- число линий. Доказать надо то, что m>=n. Хотя далее нам это не понадобится, но заметим, что максимально возможное число линий равно n(n-1)/2 -- это если их провести через каждую пару точек, то есть на каждой линии точек будет ровно две. Мы же сейчас думаем о том, как можно минимизировать, а не максимизировать число линий.

Точки мы будем обозначать буквами из конца латинского алфавита (типа x,y,z), а линии -- буквами из начала алфавита (типа a,b,c). Основным объектом, которому мы уделим внимание, будет произвольная пара вида (x,a), где точка x не лежит на прямой a. За неимением лучшего термина, я буду далее называть такой объект отметкой: мы как бы отмечаем точку x и прямую a, которая через неё не проходит.

Разных отметок можно сделать, вообще говоря, много, но нас их количество интересовать не будет. Заметим только то, что отметки вообще существуют: это нам гарантирует условие А2, которое более нигде не используется. Зададимся вопросом, каким образом можно выбрать "случайную" отметку? Укажем два таких способа.

Первый: случайно выбирается одна из точек (с равной вероятностью), а затем, когда точка x выбрана, мы рассматриваем не все прямые, а только те, которые через точку x не проходят. И уже среди них с равной вероятностью выбираем одну прямую a. В итоге получается отметка (x,a). Какова вероятность, что описанном способе выбора будет выбрана конретная отметка (x,a)?

Здесь нетрудно увидеть, что мы не знаем, сколько прямых (из общего числа m) проходят через точку, а сколько не проходят. Поэтому введём обозначение: для произвольной точки x пусть L(x) есть количество проходящих через эту точку линий ("прямых") -- от слова "lines". Теперь легко подсчитать нужную вероятность. Сначала мы с вероятностью 1/n выбираем конкретную загаданную точку x, а затем на втором шаге независимо выбираем одну прямую из общего числа m-L(x). Вероятность того, что ей окажется заранее загаданная прямая a, равна 1/(m-L(x)). А итоговая вероятность будет равна произведению вероятностей независимых событий, и это будет 1/(n(m-L(x))).

Теперь рассмотрим второй способ случайного выбора. Сначала мы случайным образом выбираем прямую. То, что ей окажется конкретная прямая a, есть событие, происходящее с вероятностью 1/m. Далее, когда прямая a уже выбрана, мы случайно выбираем точку, на ней не лежащую. Здесь потребуется второе обозначение: для числа точек, лежащих на заданной прямой: для разных линий оно может быть разным. Это число мы обозначим в виде P(a) -- от слова "points". Точки, лежащие на прямой a, мы не выбираем, поэтому выбор осуществляется из общего числа точек, равного n-P(a). Поэтому вероятность выбрать загаданную точку x составит 1/(n-P(a)). А перемножение вероятностей приводит к ответу 1/(m(n-P(a))). Это вероятность выбрать отметку (x,a) при втором способе случайного выбора.

Что можно сказать о вероятностях, получаемых первым и вторым способом? На самом деле, они вовсе не обязаны совпадать, и нетрудно привести примеры, из которых видно, что вероятности выбрать ту же отметку (x,a) при первом и втором способе могут отличаться. Но что можно заведомо утверждать, так это то, что "отклонения" не могут быть "однонаправленными" в следующем смысле: не может так оказаться, что вероятности, получаемые первым способом, больше вероятностей, получаемых вторым способом, для каждой отметки (x,a). Это очевидно в силу того, что сумма вероятностей в каждом случае равна 1, и если бы имела место "игра в одни ворота", то после суммирования мы получили бы, что 1 строго больше 1. Ясно, что так быть не может, поэтому вывод мы имеем следующий. Найдётся такая отметка (x,a), для которой вероятность выбрать её, применяя первый способ, не больше вероятности выбрать её, применяя второй способ. На языке неравенств это значит, что 1/(n(m-L(x))) <= 1/(m(n-P(a))). Переходя к обратным величинам, мы имеем равносильное неравенство n(m-L(x)) >= m(n-P(a)) со сменой знака на противоположный. Раскрывая скобки и сокращая обе части на одинаковое слагаемое mn, мы получаем неравенство -nL(x) >= -mP(a), что после домножения на -1 ведёт к смене знака, то есть к неравенству nL(x) <= mP(a) для некоторой "отдельно взятой" отметки (x,a).

Заметим теперь, что для любой отметки (x,a) верно следующее неравенство: L(x) >= P(a). Чтобы понять, почему это так, достаточно сделать рисунок: изобразить прямую a, на которой имеется ровно P(a) точек, взять какую-то точку x вне этой прямой, а затем провести (согласно аксиоме А1) всевозможные прямые через точку x и через какую-то из точек на прямой a. Все эти прямые, для каждой из P(a) точек, будут различны. Проверим это чисто логически: если допустить, что прямая, проведённая через x и y совпала с прямой, проведённой через x и z, где y,z -- разные точки на прямой a, то оказалось бы, что через эти две точки проходит как прямая a, на которой нет точки x, так и другая прямая, на которой точка x есть. Но наша аксиома А1 говорит о том, что такая прямая может быть только одна! Таким образом, мы имеем "запас" из P(a) прямых, проходящих через x. При этом через точку x могут проходить и какие-то другие прямые, не пересекающие a, но в любом случае общее количество L(x) будет не меньше того, что мы уже имеем, то есть P(a).

А теперь всё просто: сравним два неравенства: nL(x) <= mP(a) и L(x) >= P(a). Второе неравенство можно домножить на m и сравнить с первым; получится mL(x) >= mP(a) >=nL(x). Это даёт mL(x) >= nL(x), и осталось поделить на положительное число L(x), окончательно приходя к неравенству m>=n, которое требовалось доказать. Линий не меньше, чем точек -- как и утверждалось.

Замечу, что само доказательство достаточно короткое -- длинной была лишь "преамбула", описывающая весь "сюжет".

"Вот и сказочке конец, а кто дослушал -- молодец" (с) :)


В конце хочу дать ссылку, не имеющую отношения к содержанию поста. На данный момент (07.09.13) в журнале моего френда, коллеги и тёзки fiviol проходит интересная игра. Я в ней уже завершил участие, но приглашаю всех тех, кто любит разгадывать анаграммы. Которые в исполнении автора бывают обычно интересными и остроумными. Кто любит такие задания, добро пожаловать сюда.
Tags: математика
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 40 comments