Квант 1987, №2 · Страницы

ISSN 0130—2221
КВАНТ
Научно-популярный
физико-математический
журнал
1 2 3 4 5 6 7 8 9 10 11 12
87

В номере:

2 А. И. Кострикин. Простые группы
8 А. В. Сосинский. Конечные группы
13 С. Г. Семенчиский. Эффект Холла: год 1879 — год 1980
19 Д. Г. Крутоzin. Путешествие по микрокомпьютеру

Задачник «Квант»
22 Задачи M1026 — M1030; Ф1038 — Ф1042
24 Решения задач M1006 — M1009; Ф1017 — Ф1022
32 Трехначные числа и орграфы

«Квант» для младших школьников
37 Задачи
38 Н. А. Родина. О чем могут расскаать цифры

Школа в «Квант»
41 Математика 8, 9, 10

Лаборатория «Квант»
43 М. П. Бронштейн. Изобретатели радиотелеграфа

Практикум абитриента
48 В. Е. Белонучкин. Маневрирование в космосе

Варианты вступительных экзаменов

57 Ответы, указания, решения
«Квант» улыбается (18, 51)
Наша обложка (36)
Смесь (36)
Шахматная страница
Парадоксальные находы ЭВМ (3-я с. обложки)

Наша Бьюшека

На первой странице обложки показан многообразник, построенный по эпиру, приведенному на второй странице обложки. О том, как построить такой многообразник, расскаано на с. 36.

© Издательство «Нука». Главная редакция физико-mатематической литературы, «Квант», 1987

3

боглазый красавец, сосредоточенно заносивший танистенные знаки в небольший блокот и говоряший с акцентом, конечно же — немецкий шпинон.

В тюрьме недалеко от Парижа созревают глубокие иен Софуса Ли о применении теории групп в анализе, в частиности — в дифференциальных уравнениях. Зарождатся основы теории, плодотворно развивающейся и пося день, — теории групп Ли. А у себя на родине Клейн обдумывает роль групп в геометрии. Роль эта оказывается определяющей для самих оснований геометрической науки, и Клейн разъясняет это с блоком в своей значению эрганценской программы.*)

Задча классификации конечных групп

Группы выступают не только в качестве метода в различных областях математики, но постепенно становятся самостоятельным предметом изучения

*) См. «Квант», 1975, № 12, с. 6.

Спорадические конечные процесы групп

Группа | Год открытия | Порядок групп | Авторы

$$M_{11}$$ | 1861 | $2^4 3^2 5 \cdot 11=7920$ | { Матье }

$$M_{12}$$ | 1861 | $2^6 3^5 \cdot 11=95040$ | { Янко }

$$M_{22}$$ | 1873 | $2^7 3^2 5 \cdot 11=443 520$ | { Хигман, Симс }

$$M_{23}$$ | 1873 | $2^7 3^2 5 \cdot 7 \cdot 11 \cdot 23=10 200 960$ | { Холл, Уелс }

$$M_{24}$$ | 1873 | $2^{10} 3^3 5 \cdot 7 \cdot 11 \cdot 23=244 823 040$ | { Маклафлин }

$$J_1$$ | 1965 | $2^3 3 \cdot 5 \cdot 7 \cdot 11 \cdot 19=175 560$ | { Судзуки }

$$HS$$ | 1967 | $2^9 3^2 5^3 7 \cdot 11=44 353 000$ | { Хигман, Мак-Кей }

$$J_2=HJ$$ | 1967 | $2^7 3^3 5^2=604 800$ | { Конвей }

$$Mc$$ | 1968 | $2^7 3^0 5^3 7 \cdot 11=898 128 000$ | { Хилл, Уелс }

$$Sz$$ | 1968 | $2^{13} 3^7 5^2 7 \cdot 11 \cdot 13$ | { Фишер }

$$J_3=HJM$$ | 1968 | $2^7 3^5 5 \cdot 17 \cdot 19=50 232 960$ | { Хигман, Мак-Кей }

$$Co_1$$ | 1968 | $2^{21} 3^9 5^4 7^2 11 \cdot 13 \cdot 23$ | { Конвей }

$$Co_2$$ | 1968 | $2^{18} 3^6 5^3 7 \cdot 11 \cdot 23$ | { Хилл, Хигман и др. }

$$Co_3$$ | 1968 | $2^{10} 3^7 5^3 7 \cdot 11 \cdot 23$ | { Фишер }

$$He=HHM$$ | 1968 | $2^{10} 3^5 2^7 3 \cdot 17$ | { Хилл, Хигман и др. }

$$F_{22}$$ | 1969 | $2^{17} 3^9 5^2 7 \cdot 11 \cdot 13$ | { Фишер }

$$F_{23}$$ | 1969 | $2^{18} 3^13 5^2 7 \cdot 11 \cdot 13 \cdot 17 \cdot 23 \cdot 29$ | { Люонс, Симс }

$$F_{24}$$ | 1969 | $2^{21} 3^16 5^2 7^3 \cdot 11 \cdot 13 \cdot 17 \cdot 23 \cdot 29$ | { Рудвалис, Конвей и др. }

$$Ly=LyS$$ | 1970 | $2^8 3^7 5^6 \cdot 7 \cdot 11 \cdot 31 \cdot 37 \cdot 67$ | { Фишер, Симс }

$$Ru$$ | 1972 | $2^{14} 3^3 5^3 \cdot 7 \cdot 13 \cdot 29$ | { Симс }

$$O=O'NS$$ | 1973 | $2^9 3^4 5 \cdot 7^3 \cdot 11 \cdot 19 \cdot 31$ | { О’Нэн, Симс }

$$F_2=B$$ | 1973 | $2^{41} 3^13 5^6 7^2 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 23 \times 31 \cdot 47$ | { Симт, Томпсон }

$$F_3=E$$ | 1974 | $2^{15} 3^10 5^3 7^2 \cdot 13 \cdot 19 \cdot 31$ | { Конвей, Фишер и др. }

$$F_5=O$$ | 1974 | $2^{14} 3^6 5^6 \cdot 7 \cdot 11 \cdot 19$ | { Конвей, Фишер и др. }

$$M=F_1$$ | 1974 | $2^{46} 3^20 5^9 7^6 11^2 13^3 \cdot 17 \cdot 19 \cdot 23 \times 29 \cdot 31 \cdot 41 \cdot 47 \cdot 59 \cdot 71$ | { Фишер, Грисс }

$$J_4$$ | 1975 | $2^{21} 3^3 \cdot 5 \cdot 7 \cdot 11^3 \cdot 23 \cdot 29 \cdot 31 \times 37 \cdot 43$ | { Конвей, Янко и др. }

4

ваемых простых групп. И поэтому первоочередной становится задача классификации конечных простых групп.

Известно, что любая конечная группа является подгруппой одной из групп перестановок $S_n$, $n=1, 2, \dots$ (см. с. 9 этого номера). Поэтому поиск простых конечных групп можно начать с исследования подгрупп группы $S_n$.

Но что же такое простая группа? Назовем городофизим $\alpha$: $G \rightarrow H$ упрощающим, если в его образце $\alpha(G) \subset H$ более одного элемента, но меньше, чем в $G$. Конечная группа $G$ называется простой, если у нее нет упрощающих городофизмов.

Самый очевидный пример простой группы — это циклическая группа $Z_p$ любого простого порядка $p$:

$$Z_p = \begin{cases} z, z^2, \dots, z^p = e \\ z = \begin{pmatrix} 1 & 2 & \dots & (p-1) & p \\ 1 & 2 & \dots & p & 1 \end{pmatrix} \end{cases} \subset S_n.$$

Действенныйно, если бы существовал упрощающий городофизим $\alpha$: $Z_p \rightarrow H$, то один из не равных $e$ элементов $w \in Z_p$ перешел бы в единицу, но тогда и любой элемент из $Z_p$ перешел бы в единицу (подумайте, почему) и $\alpha(Z_p) = \{e\}$ — противоречие! Простота $p$ здесь существана, либо группу $Z_m$ при составном $m$ можно городофно отображить на $Z_k$, где $k$ — делитель $m$.

Простейшие простые группы: две алгебраические серии

Простых конечных групп $Z_p$ бесконечного много (так как простых чисел бесконечного много), так что группы $Z_p$ образуют (бесконечную) серию конечных простых групп. Имеется еще одна легко описываемая серия простых групп, так называемые знакопеременные группы $A_n$, $n=1, 2, \dots$, то же

5

менной группой n-й степени и обозначается через $A_n$. Можно доказать, что в группе $A_n$ имеется $n!/2$ элементов и что при $n > 4$ группа $A_n$ — простая. Таким образом, знакомеренные группы

$A_n$, $n = 5, 6, 7, \dots$,

составляют вторую серию конечных простых групп.

Шестнадцать геометрических серий

Конечные простые группы не исчерпываются сериями $Z_p$ и $A_n$. Имеется еще 16 других серий конечных простых групп. Они устроены уже более сложно. Группы этих серий, как правило, — конечные подгруппы «групп Ли». Можно сказать, что они скорей геометрической, чем алгебраической природы. В их открытии участвовали много математиков. Основополагающий роль сыграли работы француза К. Шевалле, выполненные вскоре после войны и завершенные в пятидесятьые годы. Бесконечные геометрические серии охватывают основную массу типичных простых групп и допускают много разных описаний, приспособленных для тех или иных целей.

Спорадические простые группы

Задолго до того как задача вывелиняя всех 18 бесконечных серий конечных простых групп уступила перед наиссом исследователей, было известно о существовании изолированных простых групп, названных «спорадическими». До 1965 г. их было всего пять, и все они были связаны с именем французского математика-аналитика Э. Матье. Слово «группа» не фигурировало в называях его работ перiodа 1861—1873 г., где были описаны функции и комбинаторы структуры в пространствах размерностей 12 и 24 с очень специальной и красной симметрией. Управляют этой симметрией пять групп, носящих теперь название групп Матье (см. таблицу на с. 3). Интересно, что в нашей время группы

Матье послужили основой для конструкирования высокозфективных корректирующих кодов.

В целом же пять простых групп Матьте простями особняком, получабыты, около столетия, пока в 1965 г. 3. Янко из Гейдельберга не нашел еще одну простую группу, то же не укладывающегося ни в какую бесконечную серию. Но найдена она была не случайным образом, а в ходе решения одной специальной классификации задачи. Подобными задачими занимались десяти других математиков. Успех 3. Янко, открывшего впоследствии еще три спорадические группы, послужил своего рода каталогизатором. Как грибы после джедя, для построенного наблюдается — без всякой причины, неопонято откуда, с помощью ЭВМ и без, стали появляться все новые спорадические простые группы. Имена удачливых «грибников», в сокращенном виде повторяемые названиями самих «грибов» — спорадические группы, приведены в уже упомянутой таблице, второй столбец которого указывает на год нахождения. Этот год не всегда совпадает с годом фактического построения группы.

«Вольшой монстр» и «бзби монстр»
Найбольшая из спорадических групп $F_1$, или $M$, заслуживает отдельного расскада. Ее существование впервые

baby monster

241 3.5 6.2
11·13·17·19
23·31·47

6

было предсказано независимо Б. Фищером, Дж. Томпсон и Р. Гриссом еще в 1974 г. Строгую конструкцию этой группы лишь в 1981 г. предложил Грисс, основываясь на некоторых семействе поворотов в пространстве размерности 196883 (!) Число элементов этой — с позволення сказать — простой группы равно 808 017 424 794 512 875 886 459 904 961 710 757 005 754 368·10⁹ (примерно 10⁵⁴). Не удивительно, что математики окрестили ее «big monster» («большой монстр») и долго подбирались к доказательству ее существования. Примечательно, что Грисс обошелся без помощи ЭВМ и тем самым избавил от первоначальных компьютерных родов многие другие спорадические группы, оказавшиеся «детенышами» (т. е. подгруппами) монстра F₁. К ним относятся, в частности, группа F₂, известная под названием «baby monster» и ранее реализованная перестановками в Sₙ при n, близком к 14·10⁹ (!). С течение времени были обнаружены позицительные связи монстра с классическими разделами математики (такими, как теория чисел) и получили широкое распространение «фантации на тему monстра», не исключаяшие далеки параллелей между симметрией типа F₁ и новейшими физическими теориими.

Teория и интуция

Хотя акционер вокруг упомянутых выше конструкций возникли не нужно думать, что поиск рекордных спорадических групп превращался в бессмысленное спортивное соревование, сроки популярным в США конкурсам по количеству студентов, помещенныхся в телефонную будку. Построение спорадических групп продолжило на пути глубочайшей интуции и развумных договора, предписываемых классификационной теории, которая была развитна на протяжении 25 лет цельным рядом крупных математиков. В самом начале этого удивительного периода в истории алгебры стоят Дж. Томпсон и У. Фейт, доказавшие, что всякая простая группа нечетного порядка (т. е. с нечетным числом элементов) должна быть циклической группой Zₚ для неотородного простого p. Это доказательство занял 250 страниц сухого журнального текста (!), но это оно содержало в зародышке всего последующую теории.

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

Поччитательный пример *)

Рассмотрим квадрат со стороны длиной 4 с центром в начале координат плоскости R². В его четыре угла в пшеничем четыре окружности радиуса 1, так как показано на рисунке. Каждый элемент квадрат со стороны длиной 4 с центром в начале координат и помещив в его 8 углов сферы радиуса 1. Каждая из сфера классификации теории, которая была развитна на протяжении 25 лет цельным рядом крупных математиков. В самом начале этого удивительного периода в истории алгебры стоят Дж. Томпсон и У. Фейт, доказавшие, что всякая простая группа нечетного порядка (т. е. с нечетным числом элементов) должна быть циклической группой Zₚ для неотородного простого p. Это доказательство занял 250 страниц сухого журнального текста (!), но это оно содержало в зародышке всего последующую теории.

Перейдем теперь в трехмерное пространство R³ и повторим процесс, начав с куба ребром 4 с центром в начале координат и помещив в его 8 углов сферы радиуса 1. Каждая из сфера классификации теории, которая была развитна на протяжении 25 лет цельным рядом крупных математиков. В самом начале этогоzewithе пространство R³ рассмотрим n-мерный куб с ребром 4 с центром в начале координат и помещим в его

*) По Дж. Ивинуг (The Mathematical Intelligencer, 1980, 3, № 1, c. 45—46).

8

КОНЕЧНЫЕ ГРУППЫ

Кандидат физико-математических наук
А. В. СОСИНСКИЙ

Понятие группы, в частности, конечной группы — одно из важнейших понятий математики. И вместе с тем одно из самых распространенных и наиболее полезных для приложений.

Без конечных группы нельзя, например, указать, какие алгебраические уравнения разрешимы в радиках, а какие — нет, описать, как устроены кристаллы, создавать коды, исправляющие ошибки. Об этом, однако, мы здесь расссказывать не будем, а ограничимся простейшими примерами конечных группы.

Иллюстрации: группы действий

Непустой набор некоторых действий, которые можно последовательно выполнять, называют группой, если в этом наборе для каждой действия обязательно присутствует обратное к нему, а результат последовательного выполнения любых двух действий тоже является действием из этого набора.

В качестве иллюстрации рассмотрим действия сдата, выполяющего команды стревой подготовки (рис. 1). Эти цепи действия составляют группы $R(\square) = \{C, \Pi, J, K\}$. Так, результат последовательного выполнения действий П и К (направо и крутом) будет совпадать с результатом действия Л (налево); это записьается в виде равенства $K \cdot \Pi = J$. Точно так же $J \cdot \Pi = \Pi \cdot J = K \cdot K = C$. Остальные соответствия в группе можно извлечь из ее таблицы умножения, показанной на рисунке 1. Особую роль играет здесь действие С, которое можно назвать «ничегонедельное». (Такое действие обязательно есть в любой группе: мы его получим, выполив произвольное действие, а затем обратное к нему). У нас действия П и Л обратные друг к другу, действие К — обратно к самому себе, и т. д.

Рассмотрим другую группу, тоже состоящую из повторов. Именно — группу повторов пятиконечной звезды $\Pi(\star)$ относительно ее центра (рис. 2). «Ничего-neделение» (в этом случае — повтор на $0^\circ$) обозначает через $R_0$, а остальные повторы (на $72^\circ, 144^\circ, 216^\circ, 288^\circ$) — через $R_1, R_2, R_3, R_4$. Здесь $R_2 \cdot R_1 = R_1 \cdot R_2 = R_3$,

Рис. 2.

$R_3 \cdot R_3 = R_1, R_1 \cdot R_4 = R_0$ (последнее означает, что $R_4$ обратно к $R_1$) и т. д. Набор $\Pi(\star) = \{R_0, R_1, R_2, R_3, R_4\}; \circ$ образует группу.

Рассмотрим, наконец, «группу надевания носка» (рис. 3), состоящую из следующих действий:

$O = \text{Оставь, как есть}$,
$\Pi = \text{Сними и надень на другую ногу}$,
$B = \text{Сними, выверни и надень на ту же ногу}$,
$\Pi' = \text{Сними, выверни и надень на другую ногу}$.

Здесь ничего не делает — это $O$, далее $\Pi \cdot B = \Pi', \Pi \cdot B = \Pi' \cdot \Pi' = 0, \Pi' \cdot \Pi = B$ и т. д.

Снова получается группа $H = \{O, \Pi, B, \Pi'; \circ\}$, состоящая, как и $R(\square)$, из четырех действий. Группы $H$ и $R(\square)$, однako, принимаются разные: у них таблицы умножения отличаться не только обозначением элементов, но и своим строением. Так, по диагонали таблицы умножения $H$ стоит одно и то же действие $O$, в то время как на этой диагонали $y R(\square)$ стоит разные элементы.

Подозреваю, что у самых серверных читателей нарастает возможность кака-то там стревой подготовка, надеванные носок — что за глупости также, не научно это все! Спешу возразить: научно, даже очень. Знаете, как на самом деле называется набор действий сдата? Циклическая группа 4-ю порядка или группа вычетов по modulo 4. А нашей «надеванные носок» — группа Клейна. Повороты же звезды — это одна из таких называемых простых конечных групп, о которых в этом номере «Кваната» написана целая статья (см. с. 2), а в других журналах — тысячи статьей.

Группы симметричной геометрических функций

С каждой геометрической функцией F можно связать в полне определению группу S(F), называемую группой самообразец или группой симметричной этой функции; по определению, ее набор действия состоит из всех перемещений, совмещающих функцию F с собой. Например, S(□) состоит из 8 действий: четырех поворотов квадрата (относительно его центра, в том числе на 0°) и четырех отражений (относительно двух диагоналей и двух «средних линей» квадрата).

В группе S(△) самообразец правильно треугольника — 6 действий, в группе S(□) прямого квадрата — 4. Таблица умножения группы S(□) изображена на рисунке 4.

Рис. 4.

Если сравнить таблицу умножения для группы S(□) с таблицей умножения для группы H, можно заметить, что эти таблицы отличются только обозначением действий. Если переменная действия так:
$$\begin{array}{c} O \rightarrow R_0, \quad \Pi \rightarrow R_1, \quad B \rightarrow S_1, \quad \Pi' \rightarrow S_2, \\ \text{то одна таблица превращится в другую.} \end{array}$$

Группы с совпадениями (при подходящем переменании действий) таблицами умножения называются изоморфными. Мы сейчас установили, что группы S(□) и H изоморфны (их обычно в честь Ф. Клейна обозначают буквой K), а ранее заметили, что эти группы не изоморфны группе R(□) действий слагаются.

Читатель, возможно, договорался, почему мы обозначили группу действий слагается R(□): она изоморфна группе поворотов квадрата относительно его центра на углы 2kπ/4, k=0, 1, 2, 3. Эта группа — частный случай (при n=4) группы поворотов правильно n-уzelника (относительно его центра), которая еще называется циклической группой n-zo порядка и обычно обозначается через Zn.

В альгебре группы изучают «с точностью до изоморфизма», т. е. не различают изоморфные группы: алгебраисту не интересно, как называется группа и ее действия, ему важно знать структуру таблицы умножения группы.

Группы перестановок и их подгруппы

Рассмотрим конечный набор предметов — скажем, пять. Обозначим предметы цифрами, а вес набор через N5={1, 2, 3, 4, 5}. Перестановкой i∈S5 этих предметов называется любое взаимно однозначное отображение i: N5→N5, т. е., попросту говоря, переменная предметов. Новый номер i(k) k-го предмета мы будем обозначать через ik. Для наглідності перестановку i обично представляют в виде таблицы:

$$i = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ i_1 & i_2 & i_3 & i_4 & i_5 \end{pmatrix}.$$

Это позволяет легко находить произведение перестановок i и j. Например, если

$$i = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 5 & 1 & 2 \end{pmatrix}, \quad j = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 5 & 4 & 1 \end{pmatrix},$$

то k(3)=(i∘j)(3)=i(j(3))=i(5)=2, так что

$$i∘j = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 2 & 1 & 4 \end{pmatrix}$$

(обратите внимание, что при k=i∘j сначала выполняется j, а потом i, причем это не все равно: i∘j≠j∘i — проверьте!)

Также легко находить обратные перестановки («чтением спизу вверх»):

$$i^{-1} = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 5 & 1 & 2 \end{pmatrix}^{-1} = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 5 & 2 & 1 & 3 \end{pmatrix}.$$

Нетрудно проверить, что S5 образует группу, состоящую из 5!=120 перестановок. Эта группа называется группой перестановок для предметов или симметрической группой пять стенени. Совершенно аналогично определяется симметрическая группа Sn n-ч стенени для любого натурального n.

Группы перестановок интересны в частиности тем, что содержат много подгрупп (т. е. частины, которые сами являются группами). В группах перестановок содержатся подгруппы, изоморфные всем нашим ране рассмотренным группам. Заните-

10

Трупла $Z_{12} = \{R^{25/12} = £, £^2, £^3, \dots, £^{10}, £^{11}, £^{12} = e\}$
1 элемент II порядка : $\{Z_6, e\} \cong Z_2$
2 элемент III порядка : $\{Z^4, Z^8, e\} \cong Z_3$
2 элемент IV поряд : $\{Z^3, Z^6, Z^9, e\} \cong Z_4$
2 элемент VII поряд : $\{Z^2, Z^4, Z^6, Z^8, Z^{10}, e\} \cong Z_6$
4 элемент XII поряд : $Z, Z^5, Z^7, Z^{11}$

Трупла $S_4 = \{(1 2 3 4)_{i_1 i_2 i_3 i_4} : \text{всего } 4! = 24\text{ перест.}\}$
Ядели II поряд $A_4 = e$
Ядели III поряд $B_4 = e$
Бдели II поряд $(2341), (3412), (4123), e \cong Z_4$
$(2431), (4312), (3124), e \cong Z_4$
$\{(12), (34), (12), (34), e\} \cong K$ (гр. Жилина)
$\{(12, 34), (12), (34), e\} \cong S_3 \cong S(\Delta)$

Трупла $S_5 = \{(1 2 3 4 5)_{i_1 i_2 i_3 i_4} : i_n \in \{1, 2, 3\} \cong S_3 \cong S(\Delta)\}$
Есть элементы порядков II, III, IV, V, VII;
приверг элемента порядка VII: $(1 2 3 4 5)_{2 1 4 5 3}$.
Есть подгурупы, идентичные $Z_2, Z_3, Z_4, Z_5, Z_6$.
Есть подгурупы, идентичные $S_3, S_4, u.K.$
Есть подгурупы, идентины $A_4$ ($12^{20}$ порядка).
Есть единственный подгуруп $A_5$ порядка 60.

13

Нобелевская premя по физике в 1985 году была присуждена ученому из ФРГ профессору Клаусу фон Клитицну за цикл работ по физике полупроводников. Основным результатом этих работ было открытие квантового эфекта Холла — эфекта, в котором оказались «замешаными» классический эфект Холла, известный ужесто лет, квантовые законы поведения электронных систем, формирование в середине XX века, необученные свойства «двумерных» структур, впервые обнаруженные в 1966 году, и МОП-траницICTоры, создание которых относится к патидесятым годам. Открытие К. фон Клитицга заинтересовало физков самых различных специалностей, поскольку оно открыло новые возможности измеренияFundamentals константы и создания нового эталона сопротивления.

В чем суть этого открытия? Чтоы понять это, научем с открытия столейдневности.

Классический эфект Холла

В 1879 году американский физик Эдвин Холл обнаружил, что если проводник с током помещить в магнитное поле, перpendикулярное току, то в проводнике возникнет электростатическое поле, направленное перpendикулярно магнитному полю и току (рисунок 1).

Напряжение этого поля мы можем рассчитать. Ток в проводнике — это направление движения электровов. Величина тока и средняя скорость этого движения связаны соотношение $v = I/(nes)$, где $n$ — концентрация электронов в проводнике, $e$ — заряд электрона, $s$ — площадь сечения проводника. Поместим прямогольный образец, по которой течет ток $I$, в магнитное поле с индукцией $B$ (см. рисунок 1). На движущиеся электроны со стороны магнитного поля действует сила Лоренца $F = evB$, направленная perpendикулярно $\vec{v}$ и $\vec{B}$.

В результате действия этой силы электроны будут смешаться к боковой грани образца, так что на одной из граней возникнет избыток электронов, а на другой — недостаток. Это приводит к возникновению электростатического поля, перpendикулярного току, — его называют полем Холла. Перемещение электронов поперек тока прекратиется, как только сила, действующая на электрон со стороны поля Холла, сравняется с силой Лоренца: $E_X e = evB$, откуда $E_X = vB$, или

$$E_X = \frac{IB}{nes}.$$

Холловское поле создает на гранах проводника разность потенциалов, равную

$$U_X = E_X b = \frac{IBb}{nes} = \frac{IB}{nea},$$

где $b$ — ширина проводника, $a$ — его толщина. Эту разность потенциалов на гранах можно неисредственно изменять в экспериментах, и также изменяется до очень важные сведения о количестве электронов в единице объема проводника, так как относение напряжения Холла $U_X$ к току $I$, пропускаемому через проводник, как следует из приведенных расчётов, зависит от $n$. Это относение объясняется направлением perpendикулярно магнитному полю и току (рисунок 1).

Как видно из формулы (1), $R_X$ пропорционально индукции магнитного

14

поля $B$ и обратно пропорционально концентрации электронов $n$.

Наличие магнитного поля сказывается и на общном сопротивлении проводника (на сопротивлении протекающей току) — оно, как правило, увеличивается.

Качественное это можно посящить следующим образом. Причиной электрического сопротивления является рассеяние электронов на прейстствиях, встречающся на их пути, — на примесях, на дефектах кристаллической решетки и т. д. При стольновении с прейстствиями направления скоростей электронов могут изменяться производным образом. Оdnako в промежутках между стольновениями электроны разогнются электрическим полем — проекции их скоростей вдоль поля расчету. Таким образом, в проводнике установливается отличная от нуля средняя скорость дрейфа электронов вдоль поля — по проводнику течет ток. При наличии магнитного поля тракторами движения электронов между стольновениями искривляются, и в результате скорость их дрейфа несокольную уменьшается. Следовательно, при той же разности потенциалов уменьшается ток, т. е. расчет сопротивление. Следует, однako, отметить, что холодское поле частично ослабляет описанный эффект (а иногда и компенсирует его полностью).

За это лет, прошедших со дня открытия эффициента Холла, в его изучении было сделано много. Было выяслено, как влияет на холодское сопротивление приступные примесей в материале образца, наличие носителей другого знака, изменения температуры и т. д. Оdnako формула (1) все это время, в основном, не вызывала комнату у физков.

И вот в 1980 году К. фон Клицинг обнаружил, что в особых системах, называемых двумерными электронными слоями, зависимость холодного сопротивления от индекции магнитного поля и концентрации электронов совсем не такие, как это предписывает формула (1). И сопротивление току в двумерном электронном слое при наличии магнитного поля ведет себя по-особенноу.

Причины этих «необучностей» кровотся в свойствах самого объекта, на котором они наблюдаются.

Двумерный электронный слой

Что это такое? Как его создается?

Оказывается, двумерный слой электронов возникает в электронных приборах, имеющих самое широкое применение, — в полевых МОП-транзисторах. Этот прибор схематически изображен на рисунке 2. Пластина получа—

проводника — например кремния — покрыта слоем диэлектрика (оксидом кремния), на который сверху напылен так называемый затвор — пленка металла (объчно алюминия; по первым буквам слов металл — оксид — получовидик прибор и назван МОП-транзистором). Если к затвору приложить положительное напряжение относительно полупроводника, то электроны, находящиеся в полупроводнике, принятуются к затвору. Но прояты сквозь оксид они не смогут и образуют близи него тонкий слой (его толщина 20—30 Å, т. е. ~10⁻⁹ м). Этот слой можно назвать двумерным — в том смысле, что в двух измерениях вдоль слоя электроны могут двигаться свободно, в то время как отчеты вллубь полупроводника им не дает электростатические поле затвора.

Затвор и слой образуют плоский конденсатор, емкость которого можно с достающим точностью считать равной $C = \varepsilon_0 \varepsilon S/d$, где $\varepsilon$ — диэлектрическая пропищевая осида, $d$ — его толщина, $S$ — площадь слоя. Заряд слоя можно определить по формуле $Q = CU_3$, где $U_3$ — напряжение между затвором и полупроводником. Таким образом, число электронов в слое

$$N = \frac{Q}{e} = \frac{CU_3}{e} = \varepsilon_0 \varepsilon \frac{S}{de} U_3$$

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

15

водника станет бесконечным, так как его собственные носители тока исчезнут — получоводник станет изолятором. Теперь ничего не помещает нам изучать свойства двумерного слоя, измеряя padение напряжения между контакками к слою. Ток через образец при этом пропускают между контакками, называемых, по волне понятным причинам, истоком и стоком (см. рисунок 2). Если нас интересует холодское сопротивление $R_X$, то его можно определить, измерив напряжение $U_X$ между контакками 1 и 2 или 3 и 4 и разделив результат на величины тока $I$. Информацию о сопротивлении протекающей току $R$ можно получить, измеряя напряжение между контакками 1 и 3 или 2 и 4. Для измерения холодного сопротивления такого двумерного слоя надо, разумется, поместить его в магнитное поле, направленное перпендикулярно плоскости слоя. Но в достаточно сильном поле под действием силы Лоренца электроды будут движаться по окружности с одной и той же частотой вращения

$$\omega = Be/m,$$

(3)

где $m$ — масса электрода.

Таким образом, мы получили электронную систему, в котором движение электродов ограничено в любом из направлений — в плоскости слоя их закручивает магнитное поле, а уйти из этой плоскости им не дает электрическое поле затвора.

С точки зрения классической физики двумерный проводник качественно не отличается от трехмерного. Так через такой проводник все так же связан с дрейфом электронов (вдоль слоя). Холодское сопротивление должно определиться по формуле (1), с той, однako, разницей, что под $n$ надо помнить количество электронов, приходящих на единицу площади, и в значенателе, таким образом, уже не будет толщины проводника:

$$R_X = \frac{B}{ne}.$$

(4)

Ничего необычного не должно просходить и с сопротивлением протекающей через слой току — оно должно возрасти с увеличением $B$. Однако…

Квантовые причины двумерного слоя

С точки зрения квантовой механики, однako, у такой системы электронов должны возникнуть прициппальное новые свойства. Вы, верятоно, знаете, что энергия микрочастицы, которая движется в ограниченной области пространства, согласно квантовой теории не может быть произвольной. Например, при движении электронов в atomе энергия электронов может принимать лишь определенные значения $W_0$, $W_1$, $W_2$, … и не может — промежуточные. В этом случае говорят, что возникают разрешенные уровни энергии $W_0$, $W_1$, $W_2$, …. To же происходит и с электронами, врашающимся в магнитном поле. Оказывается, их энергия может быть равна только дискретным значением

$$W_i = \left( i + \frac{1}{2} \right) \frac{\omega}{2\pi},$$

(5)

где $i$ — целое число, а $\omega$ — частота вращения, определяемая формулой (3). Эти разрешенные уровни энергии принято называют называемыми Ландду.

Согласно законам квантовой механики, электроны, находящиеся в одном и том же месте пространства, должны хотеть чем-нибудь отличаться — иметь разные энергии, разные спины и т. д. Попробуем подсчитать, сколько электронов с энергией $W_0$ ($i=0$) — это нижний уровень Ландду — может поместиться на единицу площади. Пусть электрон вращается по окружности радиуса $r$ с частотой $\omega$, определяемой формулой (3). Его кинетическая энергия равна $m\omega^2r^2/2$. Приравняем эту энергию $W_0$:

$$\frac{h\omega}{4\pi} = \frac{m\omega^2r^2}{2},$$

или $$\frac{h}{4\pi} \frac{Be}{m} = \frac{m}{2} \frac{B^2e^2}{m^2} r^2.$$

Отсюда находится на один электрон с энергией $W_0$: $\pi r^2 = h/(2Be)$. На этой же площадке может разместиться еще один электрон с той же энергией $W_0$, но с противоположно направленным спином — так велиит приципп Паули (тот же приципп Паули, который участвует в «расселении» электронов в atomе). Другие электроны с энергией $W_0$ могут поместиться рядом, так, чтобы «орбиты» электронов не перекрывали. Таким образом, на единицу площади можно разместить $n = \frac{2}{\pi r^2} = \frac{4Be}{h}$ электрон с энергией $W_0$.

В наших расчетах мы пользовались чисто механической моделью движения электронов в магнитном поле. Точный квантово-меchanическая рас-

18

нитном поле с индукцией 9 Тл вихревой ток «живет» столько, сколько длиться эксперимент, то есть часы. За это время ток затухает столь незначительно, что оценка полного времени его затухания дает много годы. Оценки сопротивления $R$, сделанные по результатам этих экспериментов, дают значение $R \lesssim 10^{-11}$ Ом. Это, возможно, означает, что равенство (7) выполняется лучше, чем до пятнадцатого знака!

Новый этапон ома?

Открытие эффективка квантования холодного сопротивления вызвало огромный интерес у физиков. Интерес этот понятен — сейчас известно не так много способов измеренияfundamentальных физических постоянных, и появление новых возможности в этом направлении всегда в конечном итоге приводит к уточнению значений этих постоянных, что крайне важно для всех направлений физики. Однако не менее интерес к этому открытию проявили и специализы в области измерения — метрологии. Интерес метрологов вызван тем, что они разглядели в эффективке квантования холодного сопротивления способ поддержания точных значений электрического сопротивления. Вы знаете, конечно, что у единц всех основных физических величины есть этаоны. Такой этапон есть и у единцы электрического сопротивления «Ом». Этalon представляет собой набор проводочных сопротивлений, и измеряя любое сопротивление любым прибором, мы, в конечном итоге, сравниваем его с сопротивлением этой группы катушки. Но у такого этаона есть недостатки. Во-первых, его сопротивление, пустые незначительно, но все же измеряется со временем, что очень существенно сказывается на той точности, с которой можно верить измерениям сопротивления. Во-вторых, такой этаон может быть только один — если мы заведем два одинаковых этаона, а из значения через некоторое время перестановить совпадать, то нам все равно придется выбрать, кто из них «главаный». В-третьих, этаон может проactить — скажем, он может погибнуть от стихийного бедствия, и это сразу нарушит строойность всей системы измерения электрического сопротивления. Если же создается этаон 1 Ом на основе эффективка квантования холодного сопротивления, то все перечисленные недостатки исчезнут. Поэтому во многих странах сейчас ведут работу по созданию этаона, основанного на квантованном эффективке Холла. Уже доступную соглашение, что переход на такие этаоны начинается, как только в laboratorиях по крайней мере трех стран удостоивается квантованные значения $R_x$, отличающееся между собой не более, чем на $2 \cdot 10^{-7}$ Ом. По-видимому, это произойдет скоро.

Новости археологии

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

Простота математики

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

математика — только очень малая и очень простая часть жизни. Когда в ответ на это аудитория запущела фон Нейман добавил: «Если люди не верят в то, что математика проста, то только потом, что они не осознают, как сложна жизнь».

Материалы представили В. А. Пилюш, В. Е. Явелов

19

ПУТЕШЕСТВИЕ
ПО МИКРОКОМПЬЮТЕРУ

Капидат технических наук Д. Г. КРУТОГИН

Год назад мы рассмотрели «процесс строительства» большой интерральной схемы (БИС), сравнивая его со строительством города («Кваит», 1986, № 2). Тогда мы интерсовались в основном технологический строительноо

дела, а теперь приглашаем вас познакомиться с самим городом, его структурой, прочитать по отдельным районам и кварталам, осмотреть архитектурные достопримечательности…

Размышления у панарамы

Для знакомства выберем сверхбольшую интерральную схему (СБИС) — например, микросхему однокристалльно микроэBM. Такая схема содержит 10⁵—10⁶ отдельных трансисторов. Что имеет делать микроэBM, или, как ее часто называют, микрокомпьютер (МК)? Во-первых, считать, т. е. выпол-

19

20

нать математические действия с довольно высокой скоростью — до миллиона простых операций в секунду. Простыми мы будем называть те немного операции, которые ЭВМ имеет выполнять «отрождания»; в основном это сложение (вычитание) и сравнение. Для выполнения сложных действия нужно сначала научить машину «преобразовывать» эти действия в последовательность простых операций. Во-вторых, выполнять логические операции с такой же быстротой. Недаваясь в тонкости логических операций, рассмотрим подходящий пример: требуется составить алфавитный список из заданного множества в один миллион фамилии. Это, в общем, простая, не требующая вычисления работы — нужно сравнить фамилии по первой, затем второй, затем третьей и т. д. буквам, и по результатам сравнения запосить фамилии в список под соответствующими номерами. Для человека эта работа и утомительна, и скучна, и весма продолжительная. ЭВМ, в том числе микроЭВМ, выполнит эту работу довольно быстро. В-третьих, микрокомпьютер может управлять машинами, производственных агрегатами, процессами. Эта его способность складывать из первых двух, либо очень упрощенно процесс управления можно представить как расчетные нескольких допустимых вариантов действия, сравнение результатов и выбор оптимального решения.

Понятно, что самая прекрасная СБИС «мертва», бесполезна, если лишена системы питания, средств ввода информации (например, клавиатуры) и отображения результатов (например, экрана или печатающего устройства). Управляющему компьютеру также нужна система связи с использовыми механизмами. (Так, мозг человека, наш многоцелевой персональный компьютер, бессилен без двусторонней связи с глазами, ушами, ptом, руками.)

Итак, конструкруем: СБИС — это мощный компьютера, сложнейшая его часть. Именно СБИС микрокомпьютера будет целю нашего путешествия, и, несколько упрощая, именно СБИС мы будем называть городом МК.

Посмотрите на фотографию, помещенную на этой странице (она сделана с увеличением 1,5): из корпуса СБИС выходит несколько десятовыводов. Это дороги, связывающее город МК с «перipherей» — так несколько пребрежительного называют клавиатуру, дисплеей, цифровачающее устройство и т. п., и дороги, по которым в город поступает питание — постоянное напряжение (чаще всего это 5 В). В случае работы с задачами большой сложности или большого объема (например, тот же список из миллиона фамилии) на помощь привлекается архивная, или внешняя, память; для связи с внешними запоминающими устройствами (ВЗУ) тоже предусмотрены выводы-дороги.

Напомним, что сверхбольшая интергральная схема — очень маленькая. Кристал кремния — основание СБИС — имеет размер около 5×5 мм, а сама СБИС в корпусе и с выводами — это коробочка не больше 40×25 мм, и весит она 15—20 г. Поэтому для удобства путешествия по городу МК предлагаем вам мысленную уменьшиться в миллион раз. (В сказачной литературе такой пример не раз использовался, хотя коэффициент подобия был поменше.) При таком уменьшении, когда наш рост стал 1,5—1,8 мкм, экскурсия по СБИС МК — это то же, что в нашем обикновенном масштабе знакомство с городом площадью около 30 квадратных километров.

Obviously, если есть такая возможность, города остатривают с возвшенной точки (с Останкинской телегаши, с Исаакиевского собора и т. п.). Мы же с вами остановимся на краю корпуса СБИС на высоте около 1000 метров (с учетом масштаба!) над городом МК и отсюда начнем.

Внизу, в долине — наш город. Он построен на берегу моря Физики Твердого Тела, у залива Полупровдников, и, без сомнения, это один из крупнейших населенных пунктов на побе-

21

режеъ*). Своеобразие нашего города, так же, например, как город Сочи или Юрмала, в том, что он построен для приема и обслуживания большого количества туристов. Постоянное насеелене города только этим и занимается. Как это часто бывают, в таком городе постоянных жителей намного меньше, чем гостей. Город МК — новостройка, подобные крупные схемы-ансамбли созданы в течение последних пяты лет. Впервые столкнул крупный город построен на одной площадке. Ранее задан туристского обслуживания решались целым комплексом небольших поселков, расположенных иногда в сотнях километров друг от друга (не забудьте умножить на 10⁻⁶!). Представляется, сколько было переездов?

Слово о словах

Теперь следует посянить, о каких туристах идет речь. Туристами в МК являются отрезки (элементы) информации, для которых хорошо подходит навание «машинное слово». Это никак не те стихийные толпы отдельноших «дикарей», которые летом рутисят надучу в приморские города-курорты. Наши туристы — частцы организационной информации потока, называемого программировой ЭВМ. Потеря любого слова угрожает разрушить смысл всей программы, но и лишихх слов быть не должно. (В этом отношении хорошоая программа подобна хорошоим стихам.)

Ну, а постоянные жители города, кто они? Это тоже машинные слова, «прописанные», или записанные, в самом МК. Они необходимы для того, чтобы пройти обращение с программими.

Слова машинные, как и слова общные, несут неокоторую конкретную информацию. Для себя мы можем разделить машинные слова на две группы: слова-команды (что сделать) и слова-данные (что числа или логические величины, то, чем распорядятся, чем операуют команды; их еще называют операндами, по созданию с командами). Но это — для себя,

*) По берегам залива Полупроводниковы вы прошли, если читали книгу «Знакомство с полупроводниками» М. Е. Левинштейна и Г. С. Симина, выпущенную в Виблотечеке «Квант» (вып. 33, с. 238).

а для электронных схем МК любое машинное слово — всего лишь последовательность единиц и нулей, а точнее, высоких (обычно более 2,5 В) и низких (менее 0,5 В) напряжений на входах трансисторных элементов. Таким образом, машинные слова — это серии электрических импульсов, пробегающих по дорогам и кварталам МК.

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

И еще немного о словах. Мы обычно почти не затрудняемся в выборе слов для выражения своих мыслей. У всех ЭВМ, и в том числе у нашого МК, есть жесткий порядок — можно пользоваться словами одной определенной длины: например, из 8 или 16 букв притом буквы — это 0 или 1 (такие буквы называют битами). Для сравнения отметим, что больше ЭВМ «разговариают» словами в 64 и 128 бит, а лучшие микрокомпьютеры пока лишь 32-битовые. Конечно, слова коротких слов (8- или 16-битовых), менее выражительен, зато намного комплектнее. Для «карманной» ЭВМ нужен и карманный словарь!

В общении человека с машиной есть неизбежные трудности. Составление программы на машинном языке — дело трудомкое, оно требует определенного навыка. Нам гордзо удобнее общаться с машиной на языке, логических блоком к человекскому (скажем, русскому или английскому). Таких языков-посредников для задачи назначения создания несколько десятков: это фортран, алгол, колол и т. д. Ну, а там, где использует несколько языков, не обойтись без переводчика… Но разговор о переводчиках и о бюро переводов, которое есть в нашем городе, мы продолжим в следующем номере.

22

Задачи
M1026—M1030, Ф1038—Ф1042

М1026. а) Пять равных двух AB, BC, CD, DE, EA расположены так, что каждая delitтя соседними на три равные части (рис. 1). Найдите величины каждой дуги (в градусах).
6) Тот же вопрос для «розетки» из m равных дуг, каждая из которых delitтя соседними на три равные части.
А. В. Швецов

M1027. Докажите, что число 1985!! + 1986!! delitтя на 1987. (Через n!! обозначается произведение всех натуральных чисел, не превосходящих n и имеющих ту же четность, т. е. n!! = n (n − 2)(n − 4)….)
В. В. Произвольов

M1028. а) На плоскости заданы две пересекающие прямые, и на них отмещено по одной точке (D и E). Построите треугольник ABC, у которого биссектрисы CD и AE лежат на данных прямых, а их основания — данные точки D и E (рис. 2).
6)* Докажите, что если при этом ∠CDE = 30°, то один из углов треугольника ABC равен 60° или 120°.
M. Волкевич, ученик 10 кл. (Москва)

M1029. Среди n членов арифметической прогрессии удалось выбрать k членов, образующих возрастуюго геометрическую прогрессию. Докажите, что n ≥ 2k−1.
В. Ф. Лев

M1030. Для выпуклого многогранника M обозначим через S(M) сумму площадей его граней, через P(M) — сумму произведений длины всех его ребер на соответствующие им внешние углы многогранника (внешний угол при данном ребре — это угол между перпендикулярами к граям, примыкающим к ребру, и направленными во внешнюю область многогранника; он равен 180° минус величина соответствующего другранного угла). Докажите, что многогранник M₁ лежит внутри многогранника M₂, то
a) S(M₁) ≤ S(M₂);
b) P(M₁) ≤ P(M₂).
А. В. Гончаров

Ф1038. При одинаковые нерастяжимые нити прикреплены на одинаковых расстояниях друг от друга к колцу радиусом r₀ и аналогичным образом — к колцу радиусом 2r₀. Нити пропущены через треугольник радиусом r₀ (рис. 3). Кольцо 1 закреплено в горизонтальной плоскости, и все системы нахождения. Найти расстояние между центрами колццей 2 и 3. Все колца сделаны из одной и той же проволоки. Треннем пренебречь.
В. П. Бородин

Ф1039. К бруску, лежащему на наклонной плоскости, прикреплена нить, перекинула через проволочную петлю; на другом конце нить высит грузик (рис. 4). При этом брусок неподвижен. Когда грузикачну, брусок начал двигаться. Объясните явление.
Г. В. Меледин

Ф1040. При одинаковые проводящие плоские площадь S каждая расположенье параллельного друг друга

24

М1006. Через две вершины треугольника проведены две прямы, разбиаются его на три треугольника и четырехугольник.
а) Могут ли площади всех четырехугольник?
б) Какие три из этих частей могут иметь равные площади?
Во сколько раз от них площadb четырехугольник?

Решения задач
M1006—M1009; Ф1017—Ф1022

В решении много раз будет использована следующая почти оценная
Лемма. Отношение, в котором прямая, проведенная через вершину треугольника, делит его площadb равно отношению, в котором она делит его основание (см. рис. 1).

a) Ответ: не могут. Если бы даже только три треугольника разбиения были равновелики (предположение о величины площади четырехугольника нам и не нужно), то по лемме отрезки, разбиающее данный треугольник, должны быть делить друг друга пополам (рис. 2), т. е. были бы диагоналими параллельрам. Но это невозможно, поскольку две противоположные стороны этого «параллелограмма» лежат на пересекающихся прямых — сторонах данного треугольника.

б) Ответ: равновелики могут быть четырехугольник и любые два треугольника разбиения; отношение площади 4-й части к площади каждой из трех равновеликих частей может быть равно либо 3, либо $\sqrt{5}-2$.

Введем обозначения, как на рисунке 3. Из решения задачи a) видно, что одна из равновеликих частей — это четырехугольник CLPK, другая — один из треугольников APL и BPK; будем считать, что это треугольник APL (случай треугольника BPK рассматривается точно так же). Третья часть — это треугольник BPK или APB; эти два случая надо рассмотреть отдельно.

25

Обозначим площад трех равновеликх частей через $s$ ($s=S_{CLPK}=S_{APL}$), площад 4-й части через $s_1$. Чтобы найти искомое отношение $s_1/s$, выразим двумя способами отношения, в которых точки $L$ и $K$ делят стороны $AC$ и $BC$, через площад с помощью леммы:

$$\frac{CL}{LA} = \frac{S_{CLB}}{S_{LAB}} = \frac{S_{CLP}}{S_{LAP}},$$

$$\frac{CK}{KB} = \frac{S_{CKA}}{S_{KBA}} = \frac{S_{CKP}}{S_{KBP}},$$

(*)

а входящие сода площад — через $s$, $s_1$ и $x=S_{CPL}$.

В первом случае (рис. 3, а) имеем:

$$\frac{2s}{s+s_1} = \frac{x}{s}, \frac{2s}{s+s_1} = \frac{s-x}{s}.$$

Отсюда легко найти, что $x=s/2$, $s_1/s=3$.

Во втором случае (рис. 3, б) система запишется так:

$$\frac{s+s_1}{2s} = \frac{x}{s}, \frac{2s}{s+s_1} = \frac{s-x}{s}.$$

Первое из этих уравнений дает $x=(s+s_1)/2$; подставляя это выражение во второе уравнение, получим, что отношение $s_1/s$ удовлетворяет квадратному уравнению $(s_1/s)^2+4(s_1/s)-1=0$, т. е. $s_1/s=\sqrt{5}-2$.

Остается еще проверить, что если разделить стороны треугольника $ABC$ в отношениях

$$CL : LA=CK : KB=2s : (s+s_1)=1 : 2$$

в 1-м случае и

$$CL : LA=BK : KC=(s+s_1):2s=(\sqrt{5}-1)/2$$

во 2-м случае, то соответствующие три части разбиения действительно будут равновелик们. Пользовать равенствами (*), это совсем легко сделать в 1-м случае и несколько сложнее во 2-м. Мы приведем для 2-го случая другое рассуждение, пояснющее, почему в нашей задаче возникло число $\alpha=(\sqrt{5}-1)/2$. (Число $\tau=\frac{1}{\alpha}=\frac{\sqrt{5}+1}{2}$ — это значение «золотое решение».) Заметим, что нашей утверждение является, как говоря, аффициным, т. е. содержит только такие геометрические понятия и величины, которые сохраняются при параллельном проектировании: прямая, отношение длины отрезков одной прямой, равенство площадей и т. п. (Напротив, такие понятия, как величины угла, отношение длины сторон треугольника или, скажем, bicсектораса, не сохраняются при проекции — и не входят в нашей утверждение.) А поскольку любой треугольник можно с помощью неокоторой параллельной проекции превращать в треугольник заданной формы (подумайте, почему!), нашей утверждение достаточно проверить только для треугольников какого-то одного, наиболее удобного вида. В качестве такого «хорошого» треугольника возьмем треугольник $ABC$, образованный двумя диагоналими и сторонами правильно пятуюугольника (рис. 4). Нетрудно показать, что отношение сторон правильно пятуюугольника к его диагонали равно $\alpha$. Отсюда ясно, что на рисунке 4

$$CL : LA=BK : KC=BD : AC=\alpha;$$

и в то же время $S_{APB}=S_{APL}=S_{CKPL}$, поскольку очень видно, что $BP=PL$, а треугольник $APL$ просто равносствлен с четырехугольником $CKPL$.

Г. А. Гальперин,
А. П. Савин

26

М1007. Докажите, что треугольники с длинами сторон a, b, с и a₁, b₁, c₁ подобны, если и только если
$$\sqrt{a a_1} + \sqrt{b b_1} + \sqrt{c c_1} = \sqrt{(a_1 + b_1 + c_1)(a + b + c)}.$$

После возведения обих частей доказываемого равенства в квадрат и несколько преобразований оно приводится к виду
$$(\sqrt{a b_1} - \sqrt{a_1 b})^2 + (\sqrt{c a_1} - \sqrt{c_1 a})^2 + (\sqrt{b c_1} - \sqrt{b_1 c})^2 = 0,$$
и следовательно, оно равносильно равенствам $a/a_1 = b/b_1 = c/c_1$, т. е. подобно треугольников.

Другое доказательство можно получить, затем, что левая часть равна скалярному произведению векторов с координатами $(\sqrt{a}, \sqrt{b}, \sqrt{c})$ и $(\sqrt{a_1}, \sqrt{b_1}, \sqrt{c_1})$ и не может быть больше правой части, которая равна произведению длины этих векторов; равенство возможно лишь, когда угол между векторами нулевой, т. е. они пропорциональны друг другу.

По существу, мы используем во втором рассужении так называемое неравенство Коши—Буняковского:
$$x_1 y_1 + x_2 y_2 + \dots + x_n y_n \leq \sqrt{(x_1^2 + x_2^2 + \dots + x_n^2)(y_1^2 + y_2^2 + \dots + y_n^2)},$$
которые обращаются в равенство, лишь когда наборы чисел $(x_1, \dots, x_n)$ и $(y_1, \dots, y_n)$ пропорциональны (у нас $n=3$, $(x_1, x_2, x_3) = (\sqrt{a}, \sqrt{b}, \sqrt{c}), (y_1, y_2, y_3) = (\sqrt{a_1}, \sqrt{b_1}, \sqrt{c_1})$).

В. П. Чучин, В. Н. Дубровский

M1008. Лестница состоит из 2n+1 ступеней. На пinnixх ступенях лежит по одному камню. Двое по очереди такжеат камни. Первый может переложить любой камень вверх на первый свободную ступенку, а второй — переложить камень на одну ступенку вниз, если она свободна. Цель первого — положить камень на верхнюю ступенку. может ли второй ему помещать?

Ответ: может.

Во избежание путаницы будем номера действующих лиц задачи (их «имена») писать с большой буквы. Правило действия Второго такое: он всякий раз кладет камень на ступень, освободившуюся после хода Первого (это всегда возможно, поскольку камень на следующее ступен里 либо лежал еще до хода

Рис. 1. Рис. 2.

Первого — и остался там после этого хода, либо оказался там в результате хода Первого). Если Второй будет следовать этому правилу, то после любого хода Первого и ответа Второго или ничего не изменится (рис. 1), или на некотором участке лестницы, все ступени которого, кроме верхней, заняты, освободятся вторяя ступень и ставится камень на верхнюю (рис. 2). Ясно, что при этом нижняя ступень всегда занята и не может образовать группы из двух или более идущих подряд пунктных ступеней (не считая, конечно, ступеней над верхним камнем, с самого начала свободных ступеней, лежащих ниже верхнего (n-го) камня, перед любым ходом Первого не преводходит n—1, т. е. две верхние ступеня будут свободны, и Первый не может занять верхнюю ступень.

С. Л. Елисеев, Н. Н. Константинов

M1009. Биссектриса удел А параллелограмма ABCD пересекает прямые BC и

Обозначим центр окружности СКЛ через O; нам достаточно доказать, что $\angle BOD = \angle BCD$ (см. рисунок). Заметим сначала, что отрезки AB и BK, а также LC

27

CD в точках K и L соответственно. Доказите, что центр окружности, проведенной через точки C, K и L, лежит на окружности, проведенной через точки B, C и D.

Ф1017. Кругнейший в мире сетевой телефон имеет в качестве объекта зеркало диаметром D=6 м. Какое время потребуется, чтобы, сравнивая полученные на этом телефоне фотосимки, можно было заметить взаимное вращение нашей Галактики и туманности Андромеды воkrуле общего центра масс? Расстояние до Андромеды R=1,42·10¹¹ R₀, где R₀ — радиус орбиты Земли. Массы Галактики и Андромеды равны, соответствно, M₇=2,5·10¹¹ M₀, M₄=3,6·10¹¹ M₀, где M₀ — масса Солнца. Фотоэффицирование ведется ввидимом свете на длина волны λ=5·10⁻⁷ м.

Ф1018. Катер, призывающий у берега большого озера (береговая линия — пряма), неожиданно отвязался, и ветер понал его с постоянной скоростью v₀=2,5 km/ч под углом α=15° к березу. Сможете ли вы догнать катер, если ваша скорость и SK равны, поскольку в треугольнике ABK равны углы при стороне AK (∠BAK=∠KAD=∠AKB), и прямая LC параллельна AB. Отсюда, в частиности, следует равенство треугольников OKC и OCL (OK=OC=OL, KC=CL). Повернем плоскость вокруг точки O так, чтобы треугольник OKC совпал с треугольником OCL. Тогда луч KC совместится с луком CL, поэтому угол между этими луцами, т. е. ∠BCD, равен углу поворота. В то же время точка B при этом повороте перейдет в D, так как KB=AB=CD, следовательно, угол BOD также равен углу поворота; тем самым равенство углов BOD и BCD доказано.

Рисунок на полях иллюстрирует случай, когда AB>BC, а угол BAD — острый, однako наше рассуждение без каких-либо изменений применимо и во всех других случаях.

Минimalное угловое расстояние между двумя объектами, при котором их можно наблюдать разделно, определяется диффракцией и равно приблизительно λ/D. Чтобы можно было заметить, что Андромеда изменила свое положение, она должна сдивнуть именно на такой угол:

$$\varphi_0 \approx \frac{\lambda}{D} = \frac{5 \cdot 10^{-7}}{6} \text{ рад} \approx 8 \cdot 10^{-8} \text{ рад.}$$

Если перiod обращения Галактики и Андромеды воkrуле центра масс равен T, то поворот на угол φ₀ происходит за время:

$$\tau = \frac{T}{2\pi} \varphi_0.$$

Перiod T можно найти из обобщенного (в школьном учебнике астрономии он называется уточненным) III закона Кеплера:

$$\left(\frac{T}{T_2}\right)^2 \left(\frac{M_1+m_1}{M_2+m_2}\right) = \left(\frac{R_1}{R_2}\right)^3.$$

Записывая его для систем Земля — Солнце и Галактика — Андромеда и пренебрегая массой Земли, получаем:

$$\left(\frac{T}{T_0}\right)^2 \left(\frac{M_\Gamma+M_A}{M_0}\right) = \left(\frac{R}{R_0}\right)^3,$$

где T₀=1 год (земной).

Из уравнений (1), (2) и (3) находим:

$$\tau = \frac{\lambda}{2\pi D} T_0 \left(\frac{R}{R_0}\right)^{3/2} \left(\frac{M_0}{M_\Gamma+M_A}\right)^{1/2} \approx 10^3 \text{ лет.}$$

В.Е. Белонучкин

Пусть в момент обнаружения объекта катара вы находились на берегу в точке O (см. рисунок), а катар, оторвашись в точке E, движется по прямой EF, составляющей с линейной береза угол α=15°, со скоростью v₀=2,5 km/ч. Чтобы ответить на вопрос задачи, построим границу области достижимости — той области, в которой спустя время t после начала вашего движения вы можете оказаться, «комбинируя» хождение и плавание. Эта граница (см. рисунок) представляет собой дуг AB окружности радиусом |OA|=

28

на берегу $v_1=4$ km/ч, в воде — $v_2=2$ km/ч? При какой скорости катара это вообщество возможно?

$$= |OB|=v_2t$$ и два отрезка касательных к этой okружности — CA и DB, причем $|OC|=|OD|=v_1t$ (подробно о построении этой границы рассказывалось в стате «Об оптимальных траекториях движения» в «Кванте» № 6 за 1982 год, с. 30). Спустя время $\Delta t$ граница области доступности займет новое положение $C'A'B'D'$, причем $|CC'|=|DD'|=v_1 \cdot \Delta t$, $|AA'|=|BB'|=v_2 \cdot \Delta t$. Легко понять, что если проекция скорости катара на направление OA (в этом направлении распространяется со скоростью $v_2$ плоский участок границы области доступности) будет больше скорости $v_2$, то вы никогда не договоритекат. Minimalное значение скорости катара, при которой догнатькат уже невозможно, определяется из условия (см. рис.ок)

$$v_{\min}\cos \beta=v_2,$$ где $\beta=\varphi-a$.

Поскольку $\varphi=\arcsin \frac{v_2}{v_1}=\arcsin \frac{1}{2}=30^\circ$, $\cos \beta=\cos 45^\circ=\frac{1}{\sqrt{2}}$, и

$$v_{\min}=v_2\sqrt{2}\approx 2.8$$ km/ч.

При движении катара со скоростью $v_0=2.5$ km/ч ($v_0<v_{\min}$) проекция скорости катара на направление OA меньше $v_2$, поэтому, как бы долго вы ни задержались на берегу, приправленный стратегией передвижения догнатькат можно (граница области доступности обязательно нагонит катер).

С. С. Крогов

Ф1019. В большой сосуд с жидкостью, плотность которого $\rho_1$, опущен маленький цилиндрический сосуд с площадью основания S, в dicho которого оставлена трубочка длиной l (рис.1); стенки сосудов жестко скреплены между собой. В маленький сосуд наливают подкрашенную жидкость плотностью $\rho_2$ ($\rho_2>\rho_1$) до высоты H так, что уровни жидкости в большом и малом сосудах совпадают. В некоторых момент времени отверстия в трубочке жидкости плотностью $\rho_2$ будет вытекать в больший сосуд до тех пор, пока давление в точке A (рис.2) со стороны жидкости плотностью $\rho_1$ не станет равно давлению жидкости плотностью $\rho_2$. Из этого условия легко находится масса жидкости, которая вытечет из маленького сосуда в первый раз.

Для этого запишем условия равновесия (см. рис.2):

$$\rho_1g(H+l)=\rho_2g(h+l)=\rho_2g(H-\Delta h+l),$$

(1)

где $\Delta h=(H-h)$ — понжение уровня жидкости в маленьком сосуде. Отсюда

$$h=\frac{\rho_1}{\rho_2}H-\frac{\rho_2-\rho_1}{\rho_2}l,$$

и

$$\Delta m=\rho_2 \cdot \Delta h \cdot s=(\rho_2-\rho_1)(H+l)s$$

(s — площадь основания маленького сосуда).

Для проекции дальнейшего решения сделаем некоторые предложения.

1. Площадь сечения большого сосуда настоящего велика, что если жидкость вытекает из маленького сосуда или вытекает в него, то уровень жидкости в большом сосуде не меняется.

2. Динамир трубочки и длина ее настоящего малы, что объемом этой трубочки по сравнению с объемами сосудов можно пренебреть, т. е. когда жидкость из

29

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

На первый взгляд может показаться, что, после того как давления в точке $A$ выравниются, процесс должен остановится; но это не так. Такое положение неустойчиво. Предположим, что жидкость плотностью $\rho_1$ в течение в трубку на небольшую высоту $\Delta x$ (рис. 3); тогда давление в точке $A'$ со стороны жидкости плотностью $\rho_1$ будет больше, чем давление в точке $A'$ со стороны жидкости плотностью $\rho_2$.

Дейстительно, давление в точке $A'$ со стороны жидкости плотностью $\rho_1$ будет равно $p_1 = \rho_1 g(H + l - \Delta x)$, а со стороны жидкости плотностью $\rho_2 - p_2 = \rho_2 g(h + l - \Delta x)$; разность этих давлений

$$\Delta p = p_1 - p_2 = (\rho_2 - \rho_1) g \cdot \Delta x$$

будет двигать жидкости вверх, поскольку $\rho_1 g(H + l) = \rho_2 g(h + l)$ — условие равновесия (см. (1)). Жидкость плотностью $\rho_1$ будет в маленький соусе до тех пор, пока давления сверху и снизу в точке $B$ (см. рис. 3) не выравниются. Жидкость плотностью $\rho_1$ будет всплывать над жидкостью плотностью $\rho_2$ (по условию задачи они не смешиваются).

Запишем условие равновесия в точке $B$:

$$\rho_1 g H = \rho_1 g \Delta h_1 + \rho_2 g h,$$

где $\Delta h_1$ — высота жидкости плотностью $\rho_1$, которая в маленький соусе.

Из (1) и (2) находим: $\Delta h_1 = \frac{\rho_2 - \rho_1}{\rho_1} l$, и

$$\Delta m_1 = (\rho_2 - \rho_1) l s.$$

Теперь, когда стала ясна причина перетеканий жидкости из одного соуса в другой, написем уравнения равновесия в более общем случае. Предположим, что равновесие в точке $B$ наступает в момент, когда

$$\rho_1 g H = \rho_1 g h_1 + \rho_2 g h_2,$$

где $h_1$ — высота жидкости плотностью $\rho_1$ и $h_2$ — высота жидкости плотностью $\rho_2$ в маленьком соусе (рис. 4). Мы уже знаем, что положение равновесия неустойчиво, и жидкость будет вытекать из маленького соуса, пока давления в точке $A$ не выравниются, а это значит, что

$$\rho_1 g(H + l) = \rho_1 g h_1 + \rho_2 g(h'_2 + l).$$

Из (3) и (4) получаем: $\Delta h_2 = h_2 - h'_2 = \frac{\rho_2 - \rho_1}{\rho_2} l$, и

$$\Delta m_2 = (\rho_2 - \rho_1) l s.$$

Когда давления в точке $A$ равны, положение неустойчиво, и жидкость плотностью $\rho_1$ будет вытекать в маленький соусе до тех пор, пока давления в точке $B$ не выравниются, а это значит, что

$$\rho_1 g H = \rho_1 g h'_1 + \rho_2 g h'_2.$$

Из (4) и (5) получаем: $\Delta h_3 = h'_1 - h_1 = \frac{\rho_2 - \rho_1}{\rho_1} l$, и

$$\Delta m_3 = (\rho_2 - \rho_1) l s = \Delta m_2.$$

Значит, каждый раз из маленького соуса будет вытекать и в тексте одинаковые массы жидкости

$$\Delta m = (\rho_2 - \rho_1) l s.$$

Заметим, что объемы жидкости, которые вытекают из соуса, будут разные; почему это так, подумайте самостояльно.

В. Е. Скороваров

30

Ф1020. Подвижный поршень делит цилиндр на две одинаковые части объемом $V_0=10^{-3}$ м³. В одной части находится сухой воздуха, в другой — водяной пар и $m=4$ г воды. При медленном нагревании цилиндра поршень приходит в движение. После смешения поршня на 1/4 длины цилиндра движение прекратилось. Какая масса водыных паров находилась в сосуде до нагревания? Какова масса воздуха, находящая в сосуде, и его начальная температура? При какой температуре поршень перестал движаться? Зависимость давления насыщенных паров воды от температуры приведена в таблице.

| $t, \text{°C}$ | $p_H \cdot 10^{-5}$, Па |
| :— | :— |
| 100 | 1 |
| 120 | 2 |
| 133 | 3 |
| 152 | 5 |
| 180 | 10 |

Ф1021. В цепи, показаной на рисунке, $R=100$ Ом, $C=10$ мКФ, $U_0=10$ В, внутреннее сопротивление батареи и сопротивление амператора пребрежимо малы. Клиоч К перiodическая ампература пребрежимо малы. Клиоч К перiodическая ампература пребрежимо малы. Клиоч К перiodическая ампература пребрежимо малы. Клиоч К перiodическая ампература пребрежимо малы.

Ф1020. Подвижный поршень делит цилиндр на две одинаковые части объемом $V_0=10^{-3}$ м³. В одной части находится сухой воздуха, в другой — водяной пар и $m=4$ г воды. При медленном нагревании цилиндра поршень приходит в движение. После смешения поршня на 1/4 длины цилиндра движение прекратилось. Какая масса водыных паров находилась в сосуде до нагревания? Какова масса воздуха, находящая в сосуде, и его начальная температура? При какой температуре поршень перестал движаться? Зависимость давления насыщенных паров воды от температуры приведена в таблице.

| $t, \text{°C}$ | $p_H \cdot 10^{-5}$, Па |
| :— | :— |
| 100 | 1 |
| 120 | 2 |
| 133 | 3 |
| 152 | 5 |
| 180 | 10 |

Движение поршня прекратиется, когда все вода испарится; при этом слева и справа от поршня будут газы (воздух и водяной пар), состояние которых описывается уравнением Менделеева—Клапейрона. Легко понять, что до этого при движении поршня уменьшался объем воздуха от $V_0$ до $V_0/2$, а водяной пар все время оставался насыщенным.

Пусть начальные температура и давление $T_0$ и $p_0$, конечные — $T_1$ и $p_1$, и масса водяного пара до нагревания $M$. Тогда мы можем записать следующие уравнения: для воздуха —

$$\frac{p_0V_0}{T_0} = \frac{p_1V_0}{2T_1};$$

для пара в начальной момент —

$$p_0V_0 = \frac{M}{\mu_\pi}RT_0, \quad p_0 = p_H(t_0),$$

в конце процесса —

$$p_1\frac{3}{2}V_0 = \frac{M+m}{\mu_\pi}RT_1, \quad p_1 = p_H(t_1),$$

где $\mu_\pi$ — молярная масса водяного пара. Решая совместно уравнения (1) — (3), находим массу водяного пара до нагревания:

$$M = m/2 = 2\text{ г.}$$

Пользовясь приведенной в условия таблицей, построим график зависимости $p_H(t)$ для водяного пара (см. рисунок). Тогда температура $T_0$ определяется из условия пересечения этого графика с прямой $p = \frac{M}{\mu_\pi}\frac{R}{V_0}T$, а $T_1$ — с прямой $p = \frac{M+m}{\mu_\pi}\frac{2R}{3V_0}$. Используя этот графикческий метод решения, находим:

$$t_0 = 140 \text{ °C}, \quad t_1 = 170 \text{ °C},$$

$$p_0 \approx 3,8 \cdot 10^5 \text{ Па.}$$

Зная температура $T_0=413$ К и величины $p_0$, из уравнения Менделеева—Клапейрона для воды ($\mu_B = 29 \text{ г/mоль}$) находим массу воды $M_0$:

$$M_0 = \frac{p_0V_0\mu_B}{RT_0} \approx 3,2 \text{ г.}$$

А. И. Вуздин

При замыкании ключа конденсаторы почти мгновенно (сопротивление амператора и внутреннее сопротивление батареи пребрежимо малы) заряжаются до напряжения $U_3 = \frac{U_0}{2}$, а при замыкании ключа практические полностью разряжаются. Поясим это.

Разряжается каждый конденсатор через резistor $R$. Ток разряда в первый момент —

$$I_0 = \frac{U_3}{R} = \frac{U_0}{2R}.$$

Если бы этот ток не изменился, то конденсатор полностью разряДЛЯ бы за время

$$\tau = \frac{q}{I_0} = \frac{CU_3}{I_0} = RC.$$

На самом деле ток уменшается по мере разряда конденсатора, и конденсатор разрядает все медлен-

31

нее; формально говоря, он полностью не разрядаетникогда. Нас же интересует не абсолотно полный его разряд, а такой, при котором просто $U \ll U_3$; для этого достаточно потребовать, чтобы $T_{\text{pa3p}} \gg \tau$. В нашем случае $T_{\text{pa3p}} = \tau_2 = 20 \cdot 10^{-3} \text{ c} \gg \tau = 1 \cdot 10^{-3} \text{ c}$.

Рассчитаем заряд, протекший через амператор при замыкании ключа:

$$q_1 = \frac{U_0}{2R} \tau_1 - C \frac{U_0}{2}$$

(напряжение на резистор равно $\frac{U_0}{2}$, ток резисторов протекает через амператор).

При размыкинии оба конденсатора разряжаются через амператор:

$$q_2 = 2 \frac{CU_0}{2}$$

Средний ток

$$I_{\text{cp}} = \frac{q_1 + q_2}{\tau_1 + \tau_2} = \frac{-C \frac{U_0}{2} + \frac{U_0}{2R} \tau_1 + CU_0}{\tau_1 + \tau_2} = \frac{U_0}{2R} \frac{\tau_1 + RC}{\tau_1 + \tau_2} \approx 4,8 \cdot 10^{-3} \text{ A}$$

A. P. Зильберман

Ф1022. «Черный ящик» содержит катушка, резистор и конденсатор и имеет три вывода. При его исследовании были получены следующие результаты.

В схеме, показанной на рисунке 1, амператор показал $I_1 = 0,1$ А при частоте генератора $v_1 = 1000 \text{ Гц}$; ток через-amператор отсутствал по фазе от входного напряжения на $\Delta \varphi_1 = \pi/6$. Когда частоту генератора уменьшили в 100 раз, ток возрос менее чем в 2 раза. Частоту генератора вернули к прежнему значению и вместе-amператора в цепь включили волтметр (рис. 2). Волтметр

Возможных схем (из упомянутых в условия задания трех элементов) довольно много — 24. Поэтому нужно вначале их нарисовать и решить — какие из них в принципи могут удовлетворять поставленным условиям. Чтобы не пропустить какой-либо схемы, нужно их разумно классифицировать — например: нарисуем вначале все схемы, в которых к точке 2 («обещей») присоединен только резистор, потом — только конденсатор, потом — только катушка. Таких схем всего 12. Затем нарисуем схемы, где к этому выводу подключеныровно два элемента — этих схем 6. Остались еще схемы: ни один из элементов не подключен к общему проводу — их 5, и все три элемента подключены к общему проводу — такая схема одна. (Мы тут не рассматриваем схем, в которых точки 1 или 3 оказываются не подключенными,— понятно почему.)

Довольно простой анализ показывает, что условия задания может удовлетворять только схема, приведенная на рисунке 3. В схеме с-amператором, включенным параллельно конденсатору (см. рис. 1), можно «выбросить» конденсатор —-amператор идеальный, значит, ток через конденсатор вообше не идет. На рисунке 4 приведена такая «упрощенная» схема (рис. 4, а) и векторная диаграмма направлений (рис. 4, б). Из диаграммы имеем:

$$\frac{X_L}{R} = tg \frac{\pi}{6} = \frac{1}{\sqrt{3}},$$

откуда

$$X_L = \frac{1}{\sqrt{3}} R$$

$$I_1 \sqrt{R^2 + X_L^2} = I_1 \frac{2R}{\sqrt{3}} = U_0 \Rightarrow I_1 = \frac{\sqrt{3}}{2} \frac{U_0}{R}$$

На рисунке 5 приведена схема «черного ящика» с подключенным волтметром (рис. 5, а) и диаграмма направлений (рис. 5, б):

33

Рис. 1.

Отсюда, кстати, следует, что в случае «крайнего невезения» меньше, чем в 1002 с, не уложиться: если нужная комбинация из трех цифровистетится последней, то конфики с этим тремия цифрами будут нажаты в 1000-ю, 1001-ю и 1002-ю секунды.

Цель ясна: упорядочить все трехначные коды так, чтобы каждый следующий начался с двух последних цифрами предыдущего, но достижима ли она?

Вот близкая ситuation, где достичь ее не удается.

Пусть известно, что цифры трехзначного кода различны и что это — цифры 1, 2 и 3. Иными словами, нужно проверить всего 6 кодов: 123, 132, 213, 231, 312 и 321. Если удассязывать вытянуть их в цепочку, то подбор кода займет 8с. Но вытянуть их в одну цепочку нельзя! Они образуют две цепочки (какие?), так что на подбор кода уйдет не 8, а 10с (проверьте!).

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

Рис. 2.

чаются стрелки-netли, соединяющие вершину саму с собой.

ОргrafФ $T_{10}$

Построим орграф, с помощью которого решается задача a). Возьмем 100 точек. Занутем их парамети цифр: 00, 01, 02, …, 98, 99. От точки $ab$ к точке $dc$ проведем стрелку, если $b=d$. Например $13\rightarrow 38$, $45\rightarrow 55$; в частности, любую точку с номером из двух одинаковых цифровыми соединениями саму с собой.

Обозначим построенный орграф $T_{10}$.

На стрелке от $ab$ к $bc$ наипшем трехзначный код $abc$: $13 \rightarrow 38$, $33 \rightarrow 333$. Любоий трехзначный код будет написанровно 1 раз: скажем, 455 будет написано на стрелке от 45 к 55. Тем самым $T_{10}$ содержит 10 вершин и 1000 стрелок со всемозможными трехзначными номерами. При этом из каждой вершины выходит 10 стрелок и в каждой вершину входит 10 стрелок: из $ab$ выходит стрелки $ab0$, $ab1$, …, $ab9$, в $ab$ входят стрелки $0ab, 1ab$, …, $9ab$.

Идя по стрелкам, можно попасть из любой вершины $ab$ в любую вершину $cd$:

$$ab \xrightarrow{abc} bc \xrightarrow{bcd} cd.$$

Оргrafы, обладающие таким свойством, будем называть связными.

Напомним: наша цель — вытянуть все трехзначные коды в цепочку; цель будет достигнуть, если мы обойдем $T_{10}$ по стрелкам, пройдя по каждой стрелкеровно 1 раз.

Существование такого объекта обеспечивает теорема об эйлеровом цикле.

Назовем орграф правильным, если для каждой его вершины $A$ число стрелок, выходящих из $A$, равно числу стрелок, входящих в $A$; будем обозначать это число $p_A$.

При меры: в $T_{10}$ для каждой вершины $ab$

$$p_{ab}=10;$$

на рисунке 1 изображены два правильных связных орграфа (или, если хотите, один правильный несвязный орграф), в них для некоторых вершин $p_A=2$, для других — $p_A=1$.

Теорема. В любом правильном связном орграфе существует цикл (замкнутый путь по стрелкам), проходящий по каждой стрелкеровно один раз (рис. 2).

Будем назвать такие циклы эйлеровыми.

Доказательство теоремы об эйлеровом цикле

Возьмем любую вершину $A$ и подdem из нее по стрелкам произвольным образом, «сжигая за собой месты» — стирая стрелки, по которым уже прошли. Посокльку стрелок конечное число, на каком-то шагу мы застрянем — придем в тупик, из которого нет выхода. Застрять в вершине $B \neq A$ не можем, так как из $B$ выходит столько же стрелок, сколько входит в $B$. Значит, тупик — это исходная вершина $A$.

Итак, наш путь — цикл $c$, начинающийся и кончующийся в $A$. Так как мы сразу стирали каждой стрелку, по которой прошли, цикл $c$ ни по какой стрелке не проходит дважды.

Если цикл $c$ содержит все стрелки орграфа, то он — эйлеров, и теорема доказана.

Если нет, то среди вершин, через которых проходит $c$, найдется вершина $A_1$, из которой торчит нестерта стрелка $s_1$ (если бы такой вершин не нашлось, наш орграф оказался бы не несвязным, рис. 3).

35

Рис. 7.

Из теоремы об эйлеровом цикле следует:
в задаче в) время $t_{\min} = 722$ с (вобше при $n > 3$ время $t_{\min} = n(n-1)(n-2) + 2$ с); при $n = 3$ из-за несязности $D_3$ на попск кода уходят лишние 2 с: $t_{\min} = \text{не 8}, \text{а 10 с}.$

Итак, $t_{\min}$ в задачах a), 6) и в) найдено. Попробуйте тем же методом найти $t_{\min}$, если

1. кнопок 10 и известно, что по крайней мере одна из цифр трехзначного кода — девятка;
2. кнопок 10 и известно, чторовно две цифры трехзначного кода одинаковы;
3. $2 \leq k \leq n$, кнопок $n$, а код — $k$-значный;
4. кнопок 6, на кнопках цифры 0, 1, …, 5, все цифры трехзначного кода различны и код содержит цифру 5.

Перейдем к обсуждению второго вопроса:

Как отыскать забытый код за наименьшее время?

Из предыдущого следует, что можно действовать так.

1. Взять подходящий орграф ($T_{10}, T_3$ или $D_{10}$ в задачах a), 6) и в) соответственно).
2. Отыскать в нем эйлеров цикл e.
3. Произвольно фиксировав стрелку $S_1$, взять стрелки, идущие в цикле e вслед за $S_1$:
   $S_1, S_2, ..., S_N$,
   $N = \begin{cases} 1000 \text{ в задаче a)}, \\ 27 \text{ в задаче 6)}, \\ 720 \text{ в задаче b)}. \end{cases}$
4. Выписать один за другим трехзначные номера стрелок $S_1, S_2, ..., S_N$.
   Поскольку номер $S_{i+1}$ добавляет к номеру $S_i$ лишь одну новую цифру, то можно указывать только ее (a не весь номер $S_{i+1}$); поэтому п. 4) можно заменить таким:
   4’ Приписать к номеру $S_1$ третью цифру номера $S_2$, затем третью цифру номера $S_3$ и т. д. — вплоть до $S_N$; получится последовательность $\Pi$ из $(N+2)$ цифр. Нажимая на кнопки с этими цифрами по одной в секунду, мы за $(N+2)$ с (т. е. за время $t_{\min}$) переберем все требующие проверки трехзначные коды и, значит, не более чем за $(N+2)$ с отыщем забытыый код.

Пример: циклу $e$ в орграфе $T_3$ с первой стрелкой 113 (рис. 6) соответствует последовательность $\Pi$ из 29 цифр: 113 332 331 322 321 312 311 2 221 211 1.

Так как $e$ — цикл, то первая и последняя пара цифр в последовательности $\Pi$ совпадает (это номер вершины, из которой выходит стрелка $S_1$ и в котором входит стрелка $S_N$). Поэтому вместе того, чтобы писать $N+2$ цифры $\Pi$ в строкуку, можно написать $N$ цифр по кругу (см. рис. 9, где $N=27$).

На рисунке 9 по ободу колеса (будем именовать его колеском $B$) идут в особом порядке 9 единиц, 9 двое и 9 треок. В этой записи заключено полное решение задачи 6). Остается нарисовать такие же заменательные колеса $A$ и $B$ для задачи а) и в).

Такие же заменательные? А что это значит?

Диалог о колеках $A, B$ и $B$
— Итак, чем же заменательное колесно $B$?
— Какую бы цифру на нем ни взять, если иdit们 от нее по часовой стрелке, читая по одной цифре, то за 29 с встретишь все трехзначные числа цифр 1, 2, 3.
— Да, это заменатель (и аналогичными свойствами должны обладать колеса $A$ и $B$), но не это самое замененное!
— Можно с равным числом иdit们 против часовой стрелки!

— Можно, но это свойство следует из первого. И оба они выполняются для колеса, построенного по любому эйлерову циклу $e$ в $T_n$.
— Так, значит, цикл $e$ на рисунке 6 — особенный?
— Да! Он построен не по общему рецепту, пригодному для любого правильного связного орграфа, а по специальному алгоритму, используемого $T_n$.
— И что это дает?
— При $n=3$ разница не велика. А в $T_{10}$ уже тысяча стрелок, и поиск $e$ в $T_{10}$ по общему рецепту может оказаться слишком долгим и трудоемким — даже если использовать ЭВМ.
— А специальный алгоритм имеет $e$ быстро?
— Да, я берсь выписать тысячу цифр на колесе $A$ за тысячу секунд! Мне не нужно ЭВМ, не нужно заполнить, какие цифры я уже пишил, нужно помнить только последние 3—4 цифры. Моя последовательность почти так же проста, как натуральный ряд.
— Эдоров! А последовательность из 720 цифр на колесе $B$ тоже проста? Ее можно выписать за 720 с?
— Да! Хотя придущать эту простую последовательность было не просто…
…Здесь мы перевем этот диалог, чтобы не лишать читателя удобства самим придущать заменательности цифр для колесе $A$ и $B$, или даже в общем случае — для $k$-значных кодов из $n$ чисел. (В тексте и на рисунках скрыты подсказки, появяющие секреты построения и быстро выписывания последовательности $\Pi$; но, может быть, они вам не понадобятся, и вы пойдете своим путем.) А мы надемемся, получив ваши письма, вернуть к этой задаче в одном из следующих номеров журнала.

М. Л. Гервер