мини-плоскости
Купил я себе сегодня новую клавиатуру (всего за 200 рублей :)) Старая была вполне работоспособна, но на ней стёрлись многие буквы, и меня это постоянно раздражало. Так что теперь я могу печатать быстрее, чем раньше. И под это дело у меня возникла мысль, а не написать ли новый пост? Тем более, что тема "подвернулась" сама собой: сегодня я вспомнил об одной старой задаче, которая предлагалась в самом первом выпуске журнала "Квант". Было это в далёком 1970 году. Задача достаточно непростая, и её решение, приведённое несколькими номерами позже, было длинным и сложным. Но сама постановка задачи весьма проста, и смысл должен быть понятен каждому. Прежде всего, вот ссылка на тот номер журнала, в котором приведено решение. Речь идёт о задаче М5. Там, среди прочего, даются и "занимательные" переформулировки, но я не буду из них исходить, и вообще по этой ссылке ходить не обязательно. Сейчас всё будет изложено "с нуля".
Журнал у меня с некоторого времени почти весь "под замком", но посты на математическую тему я обычно делаю открытыми для всех. Итак, приступим. Этот пост можно ещё "приурочить" к началу учебного года, хотя у меня пока продолжается отпуск :)
Все, кто учились в школе, так или иначе слышали об аксиомах геометрии. Наверное, не каждый специалист может на память воспроизвести весь список аксиом (тем более, что аксиоматизаций у евклидовой геометрии много: можно её излагать по Гильберту, по Вейлю, по Колмогорову или как-то ещё). Но мне кажется, что почти всякий выпусник школы в силах припомнить хотя бы одну геометрическую аксиому. Одной из самых простых является следующая (я выделю её):
(А1) Через любые две различные точки проходит одна и только одна прямая.
Если рассматривать "обычные" точки и прямые, то эта аксиома для всех должна быть "наглядно-очевидной". Сейчас я упомяну ещё об одной аксиоме -- она во многом выглядит ещё проще, и у неё очень простой смысл. Далее мы её даже почти не будем привлекать. Важно здесь то, что этими двумя аксиомами мы в данном изложении и ограничимся. Интерес представляет то, что даже из таких совсем простых положений можно извлечь весьма интересные и нетривиально доказываемые факты.
(А2) Существуют по крайней мере три точки, не лежащие на одной прямой.
Смысл у этой аксиомы очень простой: не все точки лежат на одной и той же прямой. Этим постулируется, что мы имеем дело не с одной прямой, а с чем-то вроде плоскости. В курсе планиметрии именно эти аксиомы излагаются в самом начале.
Возникает вопрос: что эти две простые аксиомы могут описывать? Здесь надо абстрагироваться от обычной геометрии и представить себе следующее. "Точками" разрешается называть любые объекты. Например, роль "точек" могут играть люди, составляющие некоторую компанию. А "прямыми" будут называться те или иные совокупности точек. Например, в случае людей это могут быть какие-нибудь комиссии, создаваемые из отдельных участников.
Всем известно, что на плоскости имеется бесконечное число точек. Нас же будет интересовать случай, когда общая совокупность "точек", которую мы рассматриваем, конечна. Скажем, речь идёт об учениках школьного класса. Пусть в этом классе организовано несколько кружков, или комиссий, или чего-то ещё. Будем тогда говорить, что совокупность учеников, входящих в одну такую "комиссию", представляет собой "прямую".
Можно сделать такой наглядный рисунок. Чтобы приблизить ситуацию к обычной геометрической, изобразим учеников точками, а в роли "прямых" у нас будут выступать линии (их можно мыслить разноцветными), которые соответствуют "комиссиям". Для каждой такой "комиссии" можно нарисовать линию, проходящую через те и только те точки, которые соответствуют входящим в неё людям. Линии могут быть какие угодно: хоть прямые, хоть кривые. Внешне это будет напоминать нечто вроде схемы метро.
То, что у нас получилось, будет называться "мини-плоскостью", если при этом выполняются условия А1 и А2. Второе условие и его проверка совсем очевидны: не должно быть линии, проходящей через все наши точки. Что касается А1, то выполнение этого условия означает, что для любых двух (различных) участников у нас есть ровно одна линия, на которой оба они находятся.
Приведём простейший пример "мини-плоскости", например, из 10 точек. Расположим 9 точек вдоль одной прямой, а десятую точку поместим вне этой прямой и соединим линиями с каждой из девяти точек. Получится схема, в которой точек 10, и линий нарисовано тоже 10.
Можно привести примеры, когда линий будет больше, чем точек. В частности, аксиомы А1 и А2 не запрещают проводить линию всего лишь через одну точку. Это ничему не помогает и не мешает -- просто увеличивает число линий. Если такие линии есть, то их можно просто стереть, сравнивая далее количество линий и количество точек. Так вот, оказывается, что на "мини-плоскости" линий всегда имеется столько же, сколько точек, или больше. Это и есть то утверждение, о котором далее пойдёт речь, и это точная переформулировка задачи из "Кванта".
Далее я намерен изложить её решение в такой форме, чтобы оно содержало минимум формул и обозначений, и чтобы смысл был наиболее "прозрачен" для читателя. Я буду основываться на доказательстве, идею которого предложил известный американский математик Джон Конвей. Сам же доказываемый факт был впервые установлен в работе 1948 года, авторами которой были де Брёйн и Эрдёш.
( Collapse )
В конце хочу дать ссылку, не имеющую отношения к содержанию поста. На данный момент (07.09.13) в журнале моего френда, коллеги и тёзки
fiviol проходит интересная игра. Я в ней уже завершил участие, но приглашаю всех тех, кто любит разгадывать анаграммы. Которые в исполнении автора бывают обычно интересными и остроумными. Кто любит такие задания, добро пожаловать сюда.
Журнал у меня с некоторого времени почти весь "под замком", но посты на математическую тему я обычно делаю открытыми для всех. Итак, приступим. Этот пост можно ещё "приурочить" к началу учебного года, хотя у меня пока продолжается отпуск :)
Все, кто учились в школе, так или иначе слышали об аксиомах геометрии. Наверное, не каждый специалист может на память воспроизвести весь список аксиом (тем более, что аксиоматизаций у евклидовой геометрии много: можно её излагать по Гильберту, по Вейлю, по Колмогорову или как-то ещё). Но мне кажется, что почти всякий выпусник школы в силах припомнить хотя бы одну геометрическую аксиому. Одной из самых простых является следующая (я выделю её):
(А1) Через любые две различные точки проходит одна и только одна прямая.
Если рассматривать "обычные" точки и прямые, то эта аксиома для всех должна быть "наглядно-очевидной". Сейчас я упомяну ещё об одной аксиоме -- она во многом выглядит ещё проще, и у неё очень простой смысл. Далее мы её даже почти не будем привлекать. Важно здесь то, что этими двумя аксиомами мы в данном изложении и ограничимся. Интерес представляет то, что даже из таких совсем простых положений можно извлечь весьма интересные и нетривиально доказываемые факты.
(А2) Существуют по крайней мере три точки, не лежащие на одной прямой.
Смысл у этой аксиомы очень простой: не все точки лежат на одной и той же прямой. Этим постулируется, что мы имеем дело не с одной прямой, а с чем-то вроде плоскости. В курсе планиметрии именно эти аксиомы излагаются в самом начале.
Возникает вопрос: что эти две простые аксиомы могут описывать? Здесь надо абстрагироваться от обычной геометрии и представить себе следующее. "Точками" разрешается называть любые объекты. Например, роль "точек" могут играть люди, составляющие некоторую компанию. А "прямыми" будут называться те или иные совокупности точек. Например, в случае людей это могут быть какие-нибудь комиссии, создаваемые из отдельных участников.
Всем известно, что на плоскости имеется бесконечное число точек. Нас же будет интересовать случай, когда общая совокупность "точек", которую мы рассматриваем, конечна. Скажем, речь идёт об учениках школьного класса. Пусть в этом классе организовано несколько кружков, или комиссий, или чего-то ещё. Будем тогда говорить, что совокупность учеников, входящих в одну такую "комиссию", представляет собой "прямую".
Можно сделать такой наглядный рисунок. Чтобы приблизить ситуацию к обычной геометрической, изобразим учеников точками, а в роли "прямых" у нас будут выступать линии (их можно мыслить разноцветными), которые соответствуют "комиссиям". Для каждой такой "комиссии" можно нарисовать линию, проходящую через те и только те точки, которые соответствуют входящим в неё людям. Линии могут быть какие угодно: хоть прямые, хоть кривые. Внешне это будет напоминать нечто вроде схемы метро.
То, что у нас получилось, будет называться "мини-плоскостью", если при этом выполняются условия А1 и А2. Второе условие и его проверка совсем очевидны: не должно быть линии, проходящей через все наши точки. Что касается А1, то выполнение этого условия означает, что для любых двух (различных) участников у нас есть ровно одна линия, на которой оба они находятся.
Приведём простейший пример "мини-плоскости", например, из 10 точек. Расположим 9 точек вдоль одной прямой, а десятую точку поместим вне этой прямой и соединим линиями с каждой из девяти точек. Получится схема, в которой точек 10, и линий нарисовано тоже 10.
Можно привести примеры, когда линий будет больше, чем точек. В частности, аксиомы А1 и А2 не запрещают проводить линию всего лишь через одну точку. Это ничему не помогает и не мешает -- просто увеличивает число линий. Если такие линии есть, то их можно просто стереть, сравнивая далее количество линий и количество точек. Так вот, оказывается, что на "мини-плоскости" линий всегда имеется столько же, сколько точек, или больше. Это и есть то утверждение, о котором далее пойдёт речь, и это точная переформулировка задачи из "Кванта".
Далее я намерен изложить её решение в такой форме, чтобы оно содержало минимум формул и обозначений, и чтобы смысл был наиболее "прозрачен" для читателя. Я буду основываться на доказательстве, идею которого предложил известный американский математик Джон Конвей. Сам же доказываемый факт был впервые установлен в работе 1948 года, авторами которой были де Брёйн и Эрдёш.
( Collapse )
В конце хочу дать ссылку, не имеющую отношения к содержанию поста. На данный момент (07.09.13) в журнале моего френда, коллеги и тёзки