
\documentclass[14pt]{elsarticle-mod}

% корректная обработка переносов, в том числе при поиске и копировании
\usepackage{cmap}
\defaulthyphenchar=127
\lccode`\-=`\-
\newcommand\softhyphen{\char127\relax}
% также в локальную копию файла t2a.cmap внесено изменение:
%  <7F> <002D>   заменено на   <7F> <00AD>

%\usepackage[TS1,T2A]{fontenc}
\usepackage[russian]{babel}
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{geometry}
\geometry{a4paper,top=1.3cm,bottom=2.0cm,left=1cm,right=1cm}
%\long\def\comment#1\endcomment{}



\biboptions{comma,square}

\journal{Летняя конференция Международного математического Турнира
Городов}
\dates{2--10 августа 2010 г.}

\usepackage[pdftex,%
            colorlinks,linkcolor=red,citecolor=blue,urlcolor=blue,
            bookmarks=false,%
            pdfauthor={Dmitry Baranov,Mikhail Skopenkov,Alexey Ustinov},%
            pdftitle={Random walks through electrical networks},%
            %pdfsubject={Computational Geometry and Object Modeling},
            pdfkeywords={Random walks, electrical networks}%
           ]{hyperref}
%\usepackage{pgf,tikz}
%\usetikzlibrary{arrows}

\theoremstyle{definition}
\newtheorem*{definition*}{Определение}
\newtheorem{pr}{}[section]


\begin{document}

\Large

\begin{frontmatter}

%\begin{titlepage}

\title{Случайные блуждания и электрические цепи}

\author{Дмитрий Баранов}

\author{Михаил Скопенков}
\ead {dimbaranov@mail.ru, skopenkov@rambler.ru, ustinov.alexey@gmail.com}
%\address [add2] {Institute for information transmission problems of the Russian Academy of Sciences}

\author{Алексей Устинов}


\begin{abstract}
Цель нашего проекта --- доказать следующую теорему и изучить
смежные вопросы.

\noindent{\bf Теорема Пойа.} \textbf{(a)} \emph{Если человек
случайным образом перемещается по $2$-мерной решетке, то он
вернется в начальную точку с вероятностью $1$}.

\noindent\textbf{(b)} \emph{Если же он перемещается по $3$-мерной
решетке, то вероятность его возврата в начальную точку строго
меньше $1$.}

Точные формулировки даны ниже. Предлагаемый подход к доказательству основан на физической интерпретации. Никаких специальных знаний физики не
требуется.

\begin{center}
\includegraphics[width=12cm]{networks-fig0rus.png}
\end{center}

\end{abstract}

\end{frontmatter}

%\begin{figure}[hb]
%\includegraphics[width=16cm]{networks-fig0.png}
%\caption{Lattices of dimensions $1$, $2$, and $3$.}
%\label{fig0}
%\end{figure}

\section{Одномерные блуждания}\label{random}

Мы сначала сформулируем задачу и лишь потом дадим необходимые
определения.

\begin{pr}\label{1-1}
Человек ходит по отрезку улицы, состоящему из $5$ кварталов. Начав
свой путь на границе кварталов в точке $x$, он с вероятностью
$1/2$ перемещается на один квартал влево и с вероятностью $1/2$
--- на один квартал вправо. Подойдя к границе кварталов, он опять
выбирает направление движения случайным образом. Если он
оказывается в точке $5$ (его дом) или в точке $0$ (бар), то он
прекращает движение: см Рис~\ref{fig1}.


\begin{figure}[hb]
\includegraphics[width=10cm]{networks-fig1rus.png}
\caption{Случайное движение по улице; см.  задачу~\ref{1-1}.}
\label{fig1}
\end{figure}

\noindent\textbf{(A)*} Напишите компьютерную программу,
моделирующую движение этого человека. Запустите ее много раз и
определите процент числа случаев, в которых он приходит домой. Вы
можете использовать этот способ для угадывания ответов в
последующих задачах.

\noindent\textbf{(B)} Пусть $P_T(x)$ --- вероятность того, что
человек, начавший свое движение в точке $x$ и сделавший не более
$T$ ходов, оказался дома. Заполните следующую таблицу десятичными
дробями с точностью до сотых.

\begin{table}[h]
\caption{Вероятности $P_T(x)$ для малых $T$}
\begin{center}
%\normalsize
\begin{tabular}{|cc|c|c|c|c|c|c|}
\hline
    & $x$ & $0$ & $1$ & $2$ & $3$ & $4$ & $5$  \\
$T$ &     &     &     &     &     &     &      \\
\hline
$1$ &     & $0.00$ & $0.00$ & $0.00$ & $0.00$ & $0.50$ & $1.00$  \\
\hline
$2$ &     &     &     &     &     &     &      \\
\hline
$3$ &     &     &     &     &     &     &      \\
\hline
$4$ &     &     &     &     &     &     &      \\
\hline
\end{tabular}
\end{center}
\end{table}

\noindent\textbf{(C)} Найдите вероятность $P(x)$ того, что человек
дойдет до дома через какое-то количество ходов.
\end{pr}

\smallskip
\begin{definition*}
%Let us explain informally what is the \emph{probability} $P(x)$. Suppose that we have a computer program which models the motion of the man starting at corner $x$. Run the programm $n$ times, where $n$ is a large number. Suppose that $m$ times (among $n$) the man reaches home. Then the \emph{probability} of reaching home is \emph{approximately} $m/n$, and it becomes more and more close to $P(x)$ if the number $n$ increases.
\textbf{(A)} Предположим, что у некоторого эксперимента имеется
$n$ \emph{равновероятных} исходов, и событие $X$ происходит ровно
в $m$ из них. Тогда \emph{вероятностью} события $X$ называется число
$P_1(X):=m/n$.

Например, вероятность выпадения орла при бросании монеты ---
$1/2$; вероятность выпадения $6$ очков на кубике --- $1/6$;
вероятность пойти направо по нашей улице --- $1/2$.

\noindent\textbf{(B)} Теперь предположим, что событие $X$ зависит
от последовательности таких экспериментов. Последовательность из
$T$ экспериментов имеет $n^T$ возможных исходов.
%, each of them being a sequence $(r_1,r_2,\dots,r_T)$ of outcomes of individual experiments.
Предположим, что событие $X$ происходит ровно при $m_T$ исходов %$(r_1,r_2,\dots,r_T)$
из них. Тогда \emph{вероятностью} события $X$ называется число
$P_T(X):=m_T/n^T$.

Например, есть ровно $4$ возможных исхода при бросании монеты $2$
раза:
%\smallskip
\begin{center}
{\normalsize
\begin{tabular}{l}
1-ый бросок \\
2-ой бросок
\end{tabular}\qquad
\begin{tabular}{|c|}
\hline
орел \\
орел \\
\hline
\end{tabular}\quad
\begin{tabular}{|c|}
\hline
орел \\
решка \\
\hline
\end{tabular}\quad
\begin{tabular}{|c|}
\hline
решка \\
орел \\
\hline
\end{tabular}\quad
\begin{tabular}{|c|}
\hline
решка \\
решка \\
\hline
\end{tabular}
}
\end{center}
%\smallskip
Пусть событие $X$ состоит в появлении решки хотя бы один раз.
Событие $X$ происходит в $3$ случаях из $4$ возможных. Поэтому
вероятность события $X$ есть $P_2(X)=3/4$.

Вероятность получения более $10$ очков при бросании двух кубиков
--- $1/12$, так как это событие происходит в ровно $3$ случаях ($5+6$, $6+5$ или $6+6$) из $36$ возможных.
Вероятность того, что человек, начавший с точки $3$, сдвинется
вправо два раза подряд составляет $1/4$.

\noindent\textbf{(C)} Пусть теперь событие $X$ зависит от бесконечной
последовательности таких экспериментов. Мы будем называть число
$P(X)$ \emph{вероятностью} события $X$, если  вероятности $P_T(X)$
стремятся к числу $P(X)$ при стремлении $T$ к
бесконечности\footnote{Формально это означает, что для каждого
$\varepsilon>0$ существует число $T_0$ такое, что для каждого
$T>T_0$ выполнено $|P(X)-P_T(X)|<\varepsilon$.}.

Например, вероятность выпадения решки хотя бы один раз в
бесконечной серии бросков составляет $P(X)=1$, так как
$P_T(X)=1-1/2^T$ стремится к $1$ при стремлении $T$ к
бесконечности.

То, что вероятности $P(X)$ \emph{существуют} для всех событий $X$,
рассматриваемых в проекте, можно использовать без доказательства.
\end{definition*}

\begin{pr}\label{1-2}
%In another form, the problem is posed in terms of the following game:
Петя и Паша играют на монетки; всего у них есть $5$ монеток; в
каждом раунде Петя выигрывает у Паши одну монетку с вероятностью
$1/2$ и проигрывает с вероятностью $1/2$; они играют до тех пор,
пока у Пети не станет $0$ монеток (он проиграл) или $5$ (он
выиграл все монеты Паши). Найдите вероятность $P(x)$ того, что
Петя выиграет, начав игру с $x$ монетками.
\end{pr}

\begin{pr}\label{1-3} Предположим, нашего ''путешественника'' сносит в
одну сторону; точнее, пусть он каждый раз перемещается вправо с вероятностью $p$
и влево с вероятностью $q = 1-p$. Найдите вероятности
$P(x)$ в этом случае.
\end{pr}

\begin{pr}\label{1-4}  Предположим, что вы играете на деньги;
сначала у вас $20$ монет, а у вашего соперника --- $50$ монет; в
каждой игре вы выигрываете одну монету с веротностью 0.45 и
проигрываете с вероятностью 0.55; игра продолжается до тех пор,
пока у кого-либо не закончатся деньги. Найдите вероятность своего
разорения.
\end{pr}

%Since we are going to apply electrical networks to a mathematical problem, we need their formal definition.

\begin{definition*} \emph{Электрическая цепь} --- это связный конечный граф,
у которого каждому ребру $xy$ приписано положительное вещественное
число, называемое его \emph{проводимостью}\footnote{Величина, обратная проводимости, называется \emph{сопротивлением}.} $C(xy)$, и задано два
непересекающихся выделенных множества вершин ($P$ и $N$). Вершины
из множества $N$ соединены с отрицательным полюсом батарейки и
землей, а вершины из множества $P$ --- с положительным; см
рисунок~\ref{fig2}.

\emph{Потенциалы} вершин $v(x)$ определяются следующими аксиомами:
\begin{enumerate}
\item\label{BC} \emph{Граничные условия}. Если $x\in N$, то $v(x)=0$. Если $x\in P$, то
$v(x)=1$. \item\label{KCL} \emph{Закон Кирхгофа}. Если $x\not\in
P\cup N$, то $\sum_{xy} C(xy)\left(v(x)-v(y)\right)=0$, где
суммирование ведется по всем ребрам $xy$, содержащим вершину~$x$.
\end{enumerate}
Число $i(xy):=C(xy)\left(v(x)-v(y)\right)$ называется
\emph{током}, идущим по ребру $xy$;\ $i(x):=\sum_{xy} i(xy)$
--- \emph{током}, втекающим в цепь через вершину $x$
(так, $i(x)=0$ для каждого $x\not\in P\cup N$ по
аксиоме~\ref{KCL}); \ $C:=\sum_{x\in P} i(x)$ называется
\emph{эффективной проводимостью} цепи между множествами $P$ и
$N$;\ $Q:=\sum_{xy} C(xy)\left(v(x)-v(y)\right)^2$, где
суммирование ведется по всем ребрам цепи, называется
\emph{тепловой мощностью} цепи.
\end{definition*}

\begin{pr}\label{1-5} Одинаковые резисторы соединены
последовательно и подключены к батарейке в 1 вольт как показано на
рисунке~\ref{fig2}. Найдите потенциалы $v(x)$ в точках $x = 0, 1,
2, 3, 4, 5$. Вы можете использовать программы, эмулирующие
электрические цепи, для угадывания ответа.
\end{pr}

\begin{figure}[hb]
\includegraphics[width=10cm]{networks-fig2rus.png}
\caption{Электрическая цепь; см. задачу~\ref{1-3}.} \label{fig2}
\end{figure}

%\smallskip
%Let S be the set of points $S = \{0, 1, 2, . . . , N\}$. We call the points of the set $D = \{1, 2, . . . , N-1\}$ the interior points of S and those of $B = \{0, N\}$ the boundary points of S. A function f (x) deп¬Ѓned on S is harmonic if, at points of D, it satisп¬Ѓes the averaging property $$f (x) = \frac{f (x-1) + f (x + 1)}{2}.$$

\begin{pr}\label{1-6} Рассмотрим цепь с вершинами $0,1,\dots,n$,
ребрами $01,12,\dots,(n-1)n$ единичной проводимости, и выделенными
множествами $N=\{0\}$, $P=\{n\}$.

\noindent\textbf{(A)} \emph{Принцип максимума}. Функция $v(x)$,
удовлетворяющая аксиоме \ref{KCL} достигает своего максимума и минимума в
вершинах из множества $P\cup N$.
%A harmonic function f (x) defined on S takes on its maximum value M and its minimum value m on the boundary.

\noindent\textbf{(B)} \emph{Единственность}. Если $v(x)$ и $u(x)$
--- две функции, удовлетворяющие аксиомам \ref{BC}--\ref{KCL}, то $v(x) = u(x)$ для всех $x$.

\noindent\textbf{(C)} Найдите потенциалы $v(x)$ и эффективную
проводимость данной цепи. К чему они стремятся при стремлении числа $n$ к
бесконечности?
\end{pr}

%\begin{pr}\label{1-8} Consider the network with infinitely many verices $0,1,2,\dots$, with infinitely many edges $01,12,23,\dots$ of unit conductance, and with marked sets $N=\{0\}$, $P=\varnothing$. Find all the possible voltages $v(x)$ on the network.
%\end{pr}

%\begin{pr}\label{1-8a}  Find the expected duration of the walk down Madison
%Avenue as a function of the walker's starting point (1, 2, 3, or 4).
%\end{pr}

\begin{pr}\label{1-9} Сформулируйте и докажите $1$-мерную теорему Пойа.
\end{pr}



\section{Двумерные блуждания}\label{random2}

%If you find the following problems difficult then read the definition below first.

\begin{pr}\label{2-1}
Рассмотрим город, схема которого приведена на рисунке~\ref{fig3}
слева. Отрезки обозначают улицы. Пути отхода помечены буквой $E$,
а буквой $P$ помечены точки, занятые полицией. Найдите с точностью до сотых
вероятность $P(x)$  того, что начав свой путь в точке $x$,
человек убежит, а не попадет в руки полиции. Из точки $x = (a, b)$
он перемещается в каждую из точек $(a + 1, b), (a - 1, b), (a, b +
1), (a, b-1)$ с вероятностью $1/4$. Если он достигает одной из
точек $E$ или $P$, то его передвижения заканчиваются.
\end{pr}

\begin{pr}\label{2-1a} Найдите потенциалы $v(x)$ в цепи из единичных резисторов на рисунке~\ref{fig3} справа.
\end{pr}

\begin{figure}[htb]
\begin{tabular}{ll}
\includegraphics[width=7cm]{networks-fig3.png} & \qquad
\includegraphics[width=7cm]{networks-fig4rus.png}
\end{tabular}
\caption{Случайное движение по городу и электрическая цепь; см.
задачи~\ref{2-1} и~\ref{2-1a}.} \label{fig3}
\end{figure}

%\begin{figure}[htb]
%\caption{Another electrical network; see Problem~\ref{2-1a}.}
%\label{fig4}
%\end{figure}

%\begin{pr}\label{2-2} You play a game in which you start a random walk
%at the center in the grid shown in Figure~\ref{fig5} to the left. When the walk reaches
%the boundary, you receive a payment of $+1$ or $-1$ as indicated at the
%boundary points. Is it a favorable game?
%\end{pr}

\begin{pr}\label{2-3} Паук перемещается случайным образом по ребрам

\noindent\textbf{(A)} куба; \quad \textbf{(B)} октаэдра; \quad
\textbf{(C)} додекаэдра; \quad \textbf{(D)} икосаэдра;

\noindent если он начинает движение в точке $a$, то какова
вероятность того, что он достигнет противоположной вершины $h$
быстрее, чем вернется в начальную вершину $a$; см. рисунок~\ref{fig5} слева?
\end{pr}

\begin{figure}[htb]
\begin{tabular}{ll}
%\includegraphics[width=5cm]{networks-fig5.png} & \qquad
\includegraphics[width=3cm]{networks-fig6.png} & \qquad
\includegraphics[width=3cm]{networks-fig10.png}
\end{tabular}
\caption{Случайное блуждание по кубу и электрическая цепь; см.
задачи~\ref{2-3}(A) и~\ref{2-6}(A).} \label{fig5}
\end{figure}

\begin{pr}\label{2-5} Следующие преобразования сохраняют эффективную проводимость цепи:

\noindent\textbf{(A)} замена двух резисторов, соединенных
последовательно, на один резистор проводимости
$1/\left(\frac{1}{C_1}+\frac{1}{C_2}\right)$; см.
рисунок~\ref{fig8} слева;

\noindent\textbf{(B)} замена двух параллельно соединенных
резисторов на один резистор с проводимостью $C_1+C_2$; см.
рисунок~\ref{fig8} справа;

\noindent\textbf{(C)} объединение двух вершин с одинаковыми
потенциалами в одну новую вершину.
\end{pr}

\begin{figure}[hb]
\begin{tabular}{ll}
\includegraphics[width=4.8cm]{networks-fig8.png} & \qquad
\includegraphics[width=2.4cm]{networks-fig9.png}
\end{tabular}
\caption{Последовательное и параллельное соединение; см.
задачу~\ref{2-5}.} \label{fig8}
\end{figure}

\begin{pr}\label{2-6} Найдите эффективную проводимость между

\noindent\textbf{(1)} противоположными вершинами; \textbf{(2)}* смежными вершинами;


\noindent\textbf{(A)} куба; \quad \textbf{(B)} октаэдра; \quad
\textbf{(C)} додекаэдра; \quad \textbf{(D)} икосаэдра;

\noindent с ребрами единичной проводимости; см рисунок~\ref{fig5}
справа.
\end{pr}



\begin{pr}\label{2-4} Пьяный турист выходит из отеля и перемещается
случайным образом по улицам Парижа, схема центра которого
приведена на рисунке~\ref{fig6} слева. Найдите вероятность того, что он
дойдет до Триумфальной арки до того, как доберется до окраины
города.
\end{pr}

\begin{figure}[htb]
\includegraphics[width=7cm]{networks-fig7rus.png}\qquad\qquad\qquad
\includegraphics[width=7cm]{networks-fig13.png}
\caption{Туристическая карта Парижа и решеточная цепь; см. задачи~\ref{2-4} и~\ref{2-10}.}
\label{fig6}
\end{figure}


\begin{pr}\label{2-10} Проводимость между вершинами \textbf{(A)*} $a$ и $b$; \textbf{(B)**} $a$ и $c$; двумерной решетки из единичных резисторов равна $2$ и $\pi/2$, соответственно; см. Рис.~\ref{fig6} справа.

Для $2$-мерной решетки в определении потенциала мы добавляем еще
одну аксиому:
\begin{enumerate}
\item[3.] $v(x)$ стремится к $1/2$ при стремлении расстояния между
$x$ и некоторой фиксированной вершиной к бесконечности.
\end{enumerate}
Разрешается пользоваться без доказательства существованием функции $v(x)$, удовлетворяющей аксиомам 1--3.
\end{pr}



%\begin{definition*} An \emph{}
%\end{definition}

\begin{pr}\label{2-7} \emph{Закон монотонности}.
Разрезание каких-либо ребер цепи может только уменьшить эффективную
проводимость между данными вершинами; см. рисунок~\ref{fig7} слева.
Объединение каких-либо вершин в одну вершину может только увеличить
эффективную проводимость между данными вершинами; см.
рисунок~\ref{fig7} в центре.
%If the conductances of the edges of a network are increased, the effective conductance
%can only increase. If they are decreased, it can only decrease.
\end{pr}

\begin{pr}\label{2-8} \textbf{(A)} Докажите, что эффективная
проводимость между центром и границей квадратной решетки $4\times
4$ из единичных резисторов меньше $3$; см рисунок~\ref{fig7}
справа.

\noindent\textbf{(B)} К чему стремится проводимость между центром
и границей квадратной решетки $2n\times 2n$ из единичных
резисторов при стремлении $n$ к бесконечности?
\end{pr}

\begin{figure}[htb]
%\begin{tabular}{ll}
\begin{tabular}{l}
\includegraphics[width=8cm]{networks-fig12rus.png}
\end{tabular}
\qquad
\begin{tabular}{l}
\includegraphics[width=3.6cm]{networks-fig11.png}
\end{tabular}
\caption{Разрезание, соединение, и квадратная решетка $4\times 4$;
см. задачи~\ref{2-7} и~\ref{2-8}.} \label{fig7}
\end{figure}

%\begin{pr}\label{2-10}* Find the conductance between two adjacent vertices of the $2$-dimensional lattice
%made of unit resistors.
%\end{pr}

%\begin{pr}\label{2-11}
%\end{pr}

\begin{pr}\label{2-9} Докажите теорему Пойа для $2$-мерной решетки.
\end{pr}




\section{Сопротивление правильных графов}\label{symmetric}

Задачи данного раздела могут помочь при решении задач предыдущего.

Функция $v(x)$ на вершинах электрической цепи называется \emph{гармонической}, если она удовлетворяет аксиоме~\ref{KCL} из определения электрической цепи. Вершины из множества $P\cup N$ назовем \emph{граничными}, остальные --- \emph{внутренними}.

%Пусть дан конечный граф и некоторое подмножество $B$ его вершин. Вершины из множества $B$ назовем \emph{граничными}, остальные --- \emph{внутренними}. Функция $v(x)$ на всех вершинах графа называется \emph{гармонической}, если ее значение в каждой внутренней вершине $x$ равно среднему арифметическому ее значений во всех соседних вершинах (то есть соединенных ребром с $x$).

%Пусть $\Z^n$  ($n\ge2$)~--- целочисленная решетка точек и $e_1$, $e_2$, \ldots, $e_n$~--- единичные базисные векторы. Для любой точки $z\in\Z$ назовем \textit{соседними} с ней точки $z \pm e_k$ ($k =1,2,\ldots,n)$; сумма и разность определяется как действия над векторами. Если $B$~--- подмножество $\Z^n$, то \textit{границей} $\partial B$ назовем множество точек $z\in\Z^n\setminus B$, которые имеют хотя бы одну соседнюю точку из $B$; под \textit{замыканием}  $B$ будем понимать множество $\bar B=B\cup\partial B$.

%\begin{Def}
%\index{Функция!гармоническая} Действительнозначную функцию
%$f(z)$, определенную на $\bar B$ назовем \textit{дискретной
%гармонической функцией} в $B$, если для любой точки $z\in B$
%значение функции $f(z)$ равно среднему арифметическому ее
%значений в соседних точках.

%В частности, при $n = 2$  в координатной записи это означает, что для любой точки $(x,y)\in B$ имеет место равенство $$4f(x,y)=f(x+1,y)+f(x-1,y)+f(x,y+1)+f(x,y-1).$$


\begin{pr}\label{9.99} \textbf{(A)} \emph{Принцип суперпозиции.} Если функции $u(x)$ и $v(x)$ --- гармонические и $a,b\in\mathbb{R}$, то и функция $au(x)+bv(x)$ --- гармоническая.

\noindent\textbf{(B)} \emph{Принцип максимума.} Гармоническая  на
конечной электрической цепи функция принимает свое наибольшее и наименьшее значения на
граничных вершинах.

\noindent\textbf{(C)} \emph{Единственность}. Если $u(x)$ и $v(x)$ --- две гармонические функции, совпадающие во всех граничных вершинах конечной электрической цепи, то $u(x)=v(x)$ во всех вершинах $x$ графа.

\noindent\textbf{(D)} Человек, случайно блуждающий по конечному городу, с вероятностью $1$ побывает на всех перекрестках его улиц.
\end{pr}


%\textbf{Лучше переписать, не используя матриц, чтобы было понятно большему числу школьников:}

\begin{pr}\label{suschestvovanie} \textbf{(A)*} \emph{Альтернатива Фредгольма.} \index{Альтернатива
Фредгольма} Пусть имеется система линейных уравнений
$$\left\{\begin{array}{c}a_{1,1}x_1+\ldots+a_{1,n}x_n=b_1,\\\hbox to 4cm{\dotfill}\\
a_{n,1}x_1+\ldots+a_{n,n}x_n=b_n
\end{array}\right.,$$
в которой число уравнений равно числу неизвестных.
%с квадратной матрицей коэффициентов $a_{j,k}$.
%с фиксированной матрицей коэффициентов $a_{j,k}$
%$(1\le j,k\le n)$ и столбцом $B$, составленным из чисел $b_1$,
%$b_2$, \ldots, $b_n$.
Докажите, что всегда выполняется одна из
следующих возможностей:
\begin{enumerate}
\item для любых $b_1$, \ldots, $b_n$ система имеет ровно одно
решение (в частности, при $b_1=\ldots=b_n=0$ существует только
нулевое решение);
\item для некоторых  $b_1$, \ldots, $b_n$ система неразрешима, а для
некоторых (в том числе нулевых) имеет бесконечно много решений.
\end{enumerate}

\noindent\textbf{(B)*} \emph{Задача Дирихле.}
%Пусть $b(x)$ --- произвольная функция, заданная в граничных вершинах.
%Пусть $B$~---
%ограниченная область в $\Z^2$ и на $\partial B$ задана некоторая
%функция $\varphi(x,y)$, $(x,y)\in \partial B.$
Докажите, что для любой конечной электрической цепи существует %единственная
%в области $B$ функция $H$
функция $v(x)$, удовлетворяющая аксиомам \ref{BC}--\ref{KCL}.
% на всем графе, совпадающая с функцией $b(x)$ во всех граничных точках.
\end{pr}


%\s \z {\bf Принцип Дирихле для ограниченной области.} Пусть $B$~--- ограниченная область. Определим на множестве  $\Omega$ всех функций $u(P)$, $P\in \overline{B}$, функционал (функционал Дирихле) $$Du =\sum\limits_{(P,Q)}(u(P)-u(Q))^2  ,$$ где суммирование ведется по множеству всех неупорядоченных пар соседних точек $P$, $Q\in\overline{B}$     таких, что хотя бы одна из них принадлежит $B$. Докажите, что для любой функции $u\in\Omega$     имеет место неравенство $$Dh\le Du,$$ где $h$~--- гармоническая в $B$ функция и такая, что  $h\equiv u$ на $\partial B$, причем равенство достигается только в том случае, если $u\equiv h$ на $\overline{B}$.

%\begin{large}
%\begin{center}
%\textsc{Правила Кирхгофа} \end{center}
%\end{large}

%\s \z\label{9.100} {\bf Правила Кирхгофа.}
%\index{Правило!Кирхгофа} Для расчета схем постоянного тока используется следующий алгоритм. На каждом участке цепи ставится ток, идущий в произвольном направлении. Затем составляется система линейных уравнений с помощью двух правил Кирхгофа:

%1) алгебраическая сумма токов, сходящихся в любом узле цепи равна нулю;

%2) для любого замкнутого контура алгебраическая сумма падений напряжений равна алгебраической сумме ЭДС.

%Например, для схемы, изображенной ниже, получается следующая
%система уравнений, из которой можно однозначно найти токи $I_1$,
%\ldots, $I_5$:
%\begin{center}
%\begin{circuit}{1}
%\.1 \- 3 u \- 1 r \R1 {$\overrightarrow{I_1}$} h \frompin R1r \- 2
%r \.2 \- 2 r \R2 {$\overrightarrow{I_2}$} h  \- 1 r  \- 3 d \.3
%\- 3 d \frompin .1 \- 3 d \- 1 r \R4 {$\overrightarrow{I_4}$} h
%\- 2 r \.4  \- 1 u \R3 {$I_3\!\!\uparrow\!\!$} u \- 1 u \frompin
%.4 \- 2 r
%  \R5 {$\overrightarrow{I_5}$} h \- 1 r \frompin .3 \- 1 r \- 6 d \- 7 l \frompin .1 \-
%  1 l
%  \- 6 d \- 6 r \nl\U1 {$U$} + r
%\end{circuit}\qquad\qquad
%$\left\{\begin{array}{rcl} R_1\cdot I_1+R_2\cdot I_2=U,\\
% R_1\cdot
%I_1-R_3\cdot I_3-R_4\cdot
%I_4=0,\\
%R_3\cdot I_3+R_2\cdot I_2-R_5\cdot
%I_5=0,\\
%I_1-I_2+I_3=0,\\
%-I_3+I_4-I_5=0.\\
%\end{array}\right.$
%\end{center}

%Узлы электрической цепи будем обозначать $\left<1\right>$, \ldots, $\left<n\right>$. Для каждой пары соседних узлов $\left<j\right>$ и $\left<k\right>$ запись $\left<j,k\right>$ будет обозначать соединяющий их проводник, $R_{j,k}$~--- его сопротивление, $I_{j,k}$~--- текущий из $\left<j\right>$ в $\left<k\right>$  ток ($I_{j,k}=-I_{k,j}$).

%Докажите, что если токи удовлетворяют уравнениям, составленным по второму правилу Кирхгофа, то каждому узлу $\left<j\right>$ электрической цепи можно поставить в соответствие некоторое число $\varphi_j$ (потенциал) так, что для любых соседних узлов $\left<j\right>$ и $\left<k\right>$ будет выполняться равенство $$I_{j,k}\cdot R_{j,k}=\varphi_j-\varphi_k$$ (падение напряжения равно разности потенциалов).

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% А КАКОЕ ФИЗИЧЕСКОЕ РЕШЕНИЕ ИЗВЕСТНО ? %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Существование: понятно, что токи как-то текут.
% Единственность: если они текут по-разному, то ,вычитая одну ситуацию из другой, получаем токи текущие без батарейки.

%\s \otv{9.100} Будем считать, что система линейных уравнений
%составлена относительно неизвестных $\varphi_1$, \ldots,
%$\varphi_n$ (потенциалов в узлах сети). В этом случае равенства,
%составленные для токов по второму правилу Кирхгофа будут
%выполняться автоматически\index{Правило!Кирхгофа}. Таким образом,
%система будет состоять из $n$ уравнений, составленных по первому
%правилу Кирхгофа. Если она будет иметь два решения, то, вычитая
%одно из другого, получим нетривиальное решение однородной системы
%(с нулевыми потенциалами на батарейках). Выберем тот узел, в
%котором потенцал максимален (или минимален). Тогда из этого узла
%токи будут только вытекать (втекать), что будет противоречить
%соответствующему уравнению, составленному  по первому правилу
%Кирхгофа. Существование решения системы вытекает из его
%единственности (см.\ альтернативу Фредгольма из
%задачи~\ref{9.99}).\index{Альтернатива Фредгольма}


\begin{pr}\label{9.101} \textbf{(A)} \emph{Вариационный принцип.} Пусть $v(x)$ --- произвольная функция на вершинах конечной электрической цепи, удовлетворяющая аксиоме \ref{BC}, но не обязательно аксиоме \ref{KCL}.
Занумеруем вершины графа числами $1,\dots,n$ и пусть $1,\dots,k$ --- внутренние вершины. Обозначим $v_1:=v(1)$, $v_2:=v(2)$, \dots, $v_n=v(n)$.
Будем рассматривать $v_1,\dots,v_k$ как переменные. Рассмотрим тепловую мощность $Q(v_1,\dots,v_k):=\sum_{xy} C(xy)\left(v_x-v_y\right)^2$ как функцию переменных $v_1,\dots,v_k$.
%{\bf Тепловая мощность цепи.} Рассмотрим цепь, которая состоит из сопротивлений и одного источника напряжения. При прохождении тока $I_{j,k}$ по проводнику с сопротивлением $R_{j,k}$, соответствующего разности потенциалов $U_{j,k}=\varphi_j-\varphi_k$ на проводнике $\left<j,k\right>$, выделяется тепловая мощность
%$$q_{j,k}=R_{j,k}\cdot I_{j,k}^2=U_{j,k}\cdot I_{j,k}= \dfrac{(\varphi_j-\varphi_k)^2}{R_{j,k}}.$$
%Рассмотрим величину
%$$Q=\sum\limits_{j,k}q_{j,k}$$ (суммарную мощность цепи) как
%функцию от потенциалов $\varphi_1$, \ldots, $\varphi_n$. Будем
%считать, что потенциалы $\varphi_1$ и $\varphi_n$ соответствуют
%концам источника напряжения и, таким образом, фиксированы.
Докажите, что функция $Q(v_1,\dots,v_k)$ принимает наименьшее значение, когда функция $v(x)$ --- гармоническая.

\noindent\textbf{(B)*} Докажите, что для функции $Q(v_1,\dots,v_k)$ существует ровно один набор значений $v_1,\dots,v_k$, при котором она достигает своего минимального значения. Используя это, дайте второе доказательство того факта, что для конечной электрической цепи функция $v(x)$, заданная аксиомами \ref{BC}--\ref{KCL},
существует и единственна.
% что система уравнений, составленная по правилам Кирхгофа разрешима и имеет ровно одно решение. Проверьте также, что для токов, удовлетворяющих правилам Кирхгофа, потенциалы в узлах цепи распределены так, что тепловая мощность цепи минимальна.

\noindent\textbf{(С)}
\emph{Закон сохранения энергии}. Докажите, что минимальное значение величины $Q(v_1,\dots,v_k)$ численно равно
эффективной проводимости $C$.
%$U\cdot I=R\cdot I^2$, где $U=\varphi_1-\varphi_n$, $I$~--- текущий через источник напряжения ток, и $R$~--- общее сопротивление цепи, определяемое равенством $R=U/I$.

\noindent\textbf{(D)} \emph{Принцип монотонности.} Докажите, что если в цепи одну проводимость %сопротивление
увеличить, то эффективная проводимость
%общее сопротивление цепи
не уменьшится.

\noindent\textbf{(E)} Из $2$-мерной решетки выбросили произвольное множество ребер. Докажите, что по-прежнему случайное блуждание с вероятностью $1$ вернется в исходную вершину.
\end{pr}

%\s \z Каждый резистор в цепи, изображенной на рис\ldots
%имеет сопротивление 1 Ом. Через резистор, расположенный
%справа, течет ток 1 А. Какова разность потенциалов на
%входных клеммах цепи? Каково эквивалентное сопротивление
%цепи? Как изменится эквивалентное сопротивление цепи, если
%к ней подсоединить еще один или два резистора? Сравните это
%результат с эквивалентным сопротивлением бесконечной цепи.

%\s \z а) Бесконечная сетка с квадратными ячейками состоит
%из одинаковых резисторов сопротивлением $R$. Каково
%эквивалентное сопротивление между двумя соседними точками
%сетки?
%
%Какова бы была эквивалентная емкость между соседними
%точками сетки, если бы сетка состояла из конденсаторов
%емкость $C$?  Какой была бы соответствующая эквивалентная
%индуктивность, если бы сетка состояла из катушек
%индуктивностью $L$?
%
%б) На той же бесконечной сети из одинаковых резисторов
%найдите сопротивление между узлами, соединенными ходом
%шахматного коня.

%\s \z Одинаковые резисторы сопротивлением 1 Ом каждый соединены
%между собой так, что они образуют правильный многогранник (куб,
%тетраэдр, додекаэдр,\ldots). Каково эквивалентное сопротивление
%между двумя соседними вершинами такого многогранника.

%\s \z Найдите эквивалентное сопротивление сеток,
%рассмотренных в двух предыдущих задачах, между соседними
%точками, если резистор, соединяющий эти точки, удален.

%\s \z\label{11.22.3} Соседние точки плоской целочисленной решетки
%соединяются единичными сопротивлениями (соседними считаются узлы
%решетки, находящиеся на расстоянии $1$ друг от друга).
%
%а) Найдите сопротивление между узлами с координатами $(0,0)$ и
%$(0,1)$.
%
%б) Источник тока подключается к узлам с координатами $(0,0)$ и
%$(1,0)$. Докажите, что для любого $n>0$  в узлах $(n,n)$ и
%$(n+1,n)$ будут одинаковые потенциалы.
%
%в)  Источник тока подключается к узлам  $(0,0)$ и $(2,1)$.
%Докажите, что в узлах $(1,1)$ и $(1,2)$ потенциалы равны.
%
%
%
%\s \z\label{11.23} а) Докажите, что при целом $x$ и $p\ge 2$
%$$\sum\limits_{x=0}^{p-1}\sin\dfrac{\pi kx}{p}\sin\dfrac{\pi lx}{p}
%=\dfrac{p}{2}\delta_p(k-l),$$ где
%$$\delta_p(x)=\begin{cases}
%1,&x\equiv 0\pmod{p};\\0,&x\not\equiv 0\pmod{p}.
%\end{cases}$$
%
%б) Пусть функция $f(x)$, заданная на множестве целых чисел, имеет
%период $p\ge2$ и $f(0)=0$. Проверьте, что для всех целых $x$
%выполняется равенство
%$$f(x)=\sum\limits_{k=1}^{p-1}C(k)\sin\dfrac{\pi kx}{p},$$
%где
%$$C(k)=\dfrac{2}{p}\sum\limits_{y=1}^{p-1}f(y)\sin\dfrac{\pi
%ky}{p}.$$
%
%
%\s \z\label{11.23>>} Докажите, что решением уравнения
%$$\Delta f(x,y)=\varphi(x,y)$$ в области $-p\le x,y\le p$
%с нулевыми условиями на границе, где $\Delta=P-E$ %(см. зад.~\ref{Poten})
%и
%$$\varphi(x,y)=\sum\limits_{k,l=1}^{2p-1}C(k,l)
%\sin\dfrac{\pi kx}{2p}\sin\dfrac{\pi ly}{2p},$$ является функция
%$$f(x,y)=-\sum\limits_{k,l=1}^{2p-1}\frac{C(k,l)}{\lambda_k+\lambda_l}
%\sin\dfrac{\pi kx}{2p}\sin\dfrac{\pi ly}{2p},\qquad
%\lambda_j=4\sin^2\dfrac{\pi j}{4p}.$$

%\begin{large}

%\begin{center}
%\textsc{Сопротивление правильных графов} \end{center}
%\end{large}

%\s \z Все ребра куба представляют собой резисторы сопротивлением 1 Ом. Каково эквивалентное сопротивление куба между двумя вершинами одной из его пространственных диагоналей? Найдите общую формулу для случая $n$-мерного куба.


%\textbf{ Лучше сформулировать без использования символов lim и ord2:}


%\medskip

%\otv{posle_3.114'} Указание: суммы $D_n$ и $F_n$ удовлетворяют
%одному и тому же рекуррентному соотношению. Например,
%$D_n=1+\dfrac{n+1}{2n}D_{n-1}.$ Кроме того, $D_0=F_0=1$.
%Следовательно, они равны друг другу. Значит, при $n\ge1$
%$$\sum\limits_{k=1}^{n}\dfrac{2^k}{k}=\dfrac{2^n}{n}F_{n-1}=
%\dfrac{2^n}{n}D_{n-1}=\dfrac{2^n}{n}\sum\limits_{k=0}^{n-1}\dfrac{1}{C_{n-1}^k}.$$
%Для завершения доказательства нужно с помощью результата
%задачи~\ref{posle_3.114} оценить степень вхождения числа $2$ в
%общий знаменатель полученной суммы.

Предположим, что имеется граф $\Gamma$, у которого сопротивление
каждого ребра равно $1$. Возьмем в графе $\Gamma$ два смежных
ребра $AB$ и $AC$. Эти ребра назовем \textit{эквивалентными},
если существует перестановка вершин графа, переводящая соединенные ребром вершины
в соединенные ребром вершины, при
которой $A$ переходит в $A$ и $B$ --- в $C$. Вершину графа назовем \emph{центром симметрии} графа $\Gamma$, если
все ребра, содержащие ее, эквивалентны. Граф $\Gamma$ называется
\textit{правильным}, если все его вершины~--- центры симметрии
графа.

Примеры правильных графов: правильные многогранники любой
размерности; правильные решетки на евклидовой плоскости,
плоскости Лобачевского и их многомерных аналогах; симметричные
решетки на торе и т.\ п.
Нетривиальный пример: граф ромбододекаэдра. Это многогранник, который получается, если к каждой грани куба приставить по четырехугольной пирамиде так, что все треугольники, граничащие по ребрам куба, сольются в ромбы. Поверхность ромбододекаэдра состоит из $12$ ромбов. Он нетривиален тем, что его вершины имеют разную степень ($3$ и $4$).

\begin{pr}\label{formula} \textbf{(A)} Пусть правильный граф содержит $n$ вершин, $A_1$ и $A_2$~---
соседние вершины степеней $k_1$ и $k_2$, соответственно. Докажите,
что сопротивление между ними равно
$$\left(\frac{1}{k_1}+\frac{1}{k_2}\right)\left(1-\frac{1}{n}\right).$$

\noindent\textbf{(B)} Если же взять $2$-мерную решетку, то $1/n$ в
последней формуле нужно заменить нулем.
\end{pr}

\begin{pr}\label{protivotok} К двум соседним вершинам проволочного
\textbf{(A)} икосаэдра; \textbf{(B)} додекаэдра; подвели напряжение так, что по соединяющему их
ребру потек ток $I$. Какой при этом будет течь ток по диаметрально
противоположному ребру?
\end{pr}


\begin{pr}\label{posle_3.114'}{\bf *} Докажите, что суммы $D_n=
\sum\limits_{k=0}^{n}\dfrac{1}{C_n^k}$ и $F_n=
\dfrac{n+1}{2^{n+1}}\sum\limits_{k=1}^{n+1}\dfrac{2^k}{k}$ равны
друг другу. Как эти суммы связаны с сопротивлением многомерного
куба?
В качестве следствия получите, что порядок вхождения двойки в число
$\sum_{k=1}^{n}\frac{2^k}{k}$ стремится к бесконечности с ростом
$n$.
\end{pr}



\section{Трехмерные блуждания}\label{random3}

\begin{figure}[hbt]
\includegraphics[width=3.5cm]{networks-fig14.png}\qquad\qquad\qquad
\includegraphics[width=3.5cm,angle=90]{networks-fig15.png}\qquad\qquad\qquad
\includegraphics[width=5cm]{networks-fig16.png}
\caption{(Слева) бинарное дерево глубины $3$; (в центре) модифицированное бинарное дерево глубины $3$;
(справа) разрешенные пересечения ребер в этом дереве; см. задачи~\ref{3-1}, ~\ref{3-2} и~\ref{3-5}.
}
\label{fig079}
\end{figure}

\begin{pr}\label{3-1} Найдите сопротивление
бинарного дерева глубины  \noindent\textbf{(A)} $3$; \quad
\textbf{(B)} $2010$, составленного из единичных резисторов (см.
рис.~\ref{fig079} слева).
\end{pr}

%\begin{figure}[hb]
%\includegraphics[width=4cm]{networks-fig14.png}
%\caption{Бинарное дерево глубины $3$ как электрическая цепь; см. задачу~\ref{3-1}.} \label{fig079}
%\end{figure}

\begin{pr}\label{3-2} Найдите сопротивление \emph{модифицированного} бинарного и троичного
деревьев глубины $2010$, в которых каждый резистор на $k$-ом уровне заменяется на $2^k$ последовательно соединенных единичных резисторов
(см. рис.~\ref{fig079} в центре).\end{pr}






%\begin{figure}[hb]
%\includegraphics[width=4cm]{networks-fig15.png}
%\caption{Бинарное дерево с $2^k$ резисторами на $k$-ом уровне; см.
%задачу~\ref{3-2}.} \label{fig089}
%\end{figure}

%\begin{figure}[hb]
%\includegraphics[width=4cm]{doyle-snell091.eps}
%\caption{}
%\end{figure}
\begin{pr}\label{3-4} Какие из деревьев, упомянутых \textbf{(A)} в задаче~\ref{3-1}; \quad
\textbf{(B)} в задаче~\ref{3-2}; \quad можно вырезать из трехмерной решетки?\end{pr}

\begin{pr}\label{3-5} А если разрешаются пересечения (см. рис.~\ref{fig079} справа) ребер на равном расстоянии от корня?\end{pr}

%\begin{figure}[hb]
%\includegraphics[width=8cm]{networks-fig16.png}
%\caption{Разрешенные пересечения ребер; см. задачу~\ref{3-5}}
%\label{tran}
%\end{figure}

\begin{pr}\label{3-6} Докажите теорему Пойа для $3$-мерной решетки.\end{pr}



\section{Сопротивление кольца*}

%\textbf{Всюду вместо сопротивления предлагается использовать проводимость, как в других частях. Вместо сетки можно говорить ''$2$-мерная решетка'', последнее понятие уже определено в проекте.}

%\textsc{Здесь лучше именно сетка, потому что окружность пересекает кучу ребер не в концах, и тогда у них получаются сопротивления, пропорциональные длинам.}

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

\begin{pr} \label{ring-0} Источник тока подключается к узлам сетки с координатами
$(0,0)$ и $(1,0)$. Докажите, что в узлах
$(2,2)$ и $(3,2)$ будут одинаковые потенциалы (см. замечание в задаче~\ref{formula}(B)).
\end{pr}

\begin{pr} \label{ring-1} Из сетки вырезан квадрат размерами $n\times n$,
граничные точки которого соединены шиной с нулевым
сопротивлением. Докажите, что сопротивление между любым узлом
квадрата и его границей не превосходит $\sqrt{n}$. 
\end{pr}

\begin{pr} \label{ring-2} В условиях задачи~\ref{ring-1} источник тока
подключен к внутреннему узлу квадрата и к границе. Потенциал на
границе равен нулю. Докажите, что если источник подает ток
$\varepsilon$, то в каждой из точек квадрата потенциал не
превосходит $\varepsilon\sqrt{n}$.
\end{pr}

%\textbf{Нужно объяснить детям обозначение O большое и всегда указывать, какая величина стремится к бесконечности:}

\begin{pr} \label{ring-3} Для функций, заданных в узлах целочисленной
решетки определим %дискретный оператор Лапласа равенством
$$\Delta f(x,y):=f(x-1,y) + f(x+1,y) + f(x,y-1) +
f(x,y+1)-4f(x,y).$$ Пусть $r(x,y)=\sqrt{x^2+y^2}$.
%~--- евклидова норма вектора $(x,y)$.
Докажите, что для функции $f(x,y):=\ln r(x,y)$ (при $r(x,y)\ge 2$) выполнено $\Delta
f(x,y)=O\left(\frac1{r^4(x,y)}\right).$
\end{pr}

Здесь и далее для двух функций $A$ и $B$ запись $A=O(B)$ означает, что для некоторой положительной константы $c$ всегда выполняется неравенство
$|A|\le c B.$

\begin{pr} \label{ring-4} Из металлической сетки вырезано кольцо с
внутренним радиусом $r_1n$ и внешним~--- $r_2n$ (центры обоих
кругов~--- в начале координат). Если некоторое ребро разрезано, то
сопротивление оставшегося куска пропорционально его длине. На
внутренний контур кольца подается напряжение $\ln r_1$, а на
внешний~--- $\ln r_2$. Докажите, что в каждой точке кольца
$(x,y)$ потенциал имеет вид
$U_n(x,y)=\ln r(x,y)+O\left(\frac1{n^{3/2}}\right).$
\end{pr}

\begin{pr} \label{ring-5.0} С помощью равенства $\arctg x=x+O(x^3)$ докажите, что при
$0\le y< R$ выполнено
$\frac{R}{R^2+y^2}=\arctg\frac{y+1}R-\arctg\frac{y}R+O\left(\frac1{R^2}\right).$
\end{pr}


\begin{pr} \label{ring-5.1} Докажите, что
$\sum_{y=0}^{R-1}\frac{R}{R^2+y^2}=\frac{\pi}4+O\left(\frac1R\right).$
\end{pr}

\begin{pr} \label{ring-5} Пусть в условиях задачи~\ref{ring-4} имеется
дополнительное ограничение $r_2>3r_1/2$ (достаточное для того,
чтобы квадрат, описанный около внутреннего круга, целиком
содержался бы во внешнем). Докажите, что между внутренним и
внешним контурами течет ток
$2\pi+O\left(\frac1{\sqrt{n}}\right).$ Выведите отсюда
формулу для сопротивления кольца
\begin{equation}\label{ring_eq_1}
R(r_1n,r_2n)=\frac{1}{2\pi}\ln\frac{r_2}{r_1}+O\left(\frac1{\sqrt{n}}\right).
\end{equation}
\end{pr}

\begin{pr}\label{ring-6} Докажите, что формула~\eqref{ring_eq_1}
выполняется и без дополнительного ограничения $r_2>3r_1/2$.
\end{pr}


%\textbf{Условие может оказаться непонятно школьникам:}

%\textsc{Так лучше?}

\begin{pr} \label{ring-7} %С помощью равенства~\eqref{ring_eq_1} уточните
%утверждения задач~\ref{ring-1}, \ref{ring-2}, \ref{ring-4},
%\ref{ring-5}, \ref{ring-6}.
%С помощью равенства~\eqref{ring_eq_1} уточните оценки в задачах~\ref{ring-1}, \ref{ring-2}, \ref{ring-4}, \ref{ring-5}, \ref{ring-6}.
С помощью равенства~\eqref{ring_eq_1} уточните оценки в
задачах~\ref{ring-1}, \ref{ring-2} и докажите формулы с более
точными остаточными членами в задачах \ref{ring-4} и \ref{ring-5}:
$$U(x,y)=\ln r(x,y)+O\left(\frac{\ln n}{n^{2}}\right),\qquad
R(r_1n,r_2n)=\frac{1}{2\pi}\ln\frac{r_2}{r_1}+O\left(\frac{\ln
n}{n}\right).$$
\end{pr}


\section{Сложные задачи*}

\begin{pr} \emph{Теорема Лиувилля}.Пусть заданная на $\mathbb{Z}^2$ функция $f(m,n)$ удовлетворяет неравенству $0\le f(m,n)\le 1$ и условию
\begin{equation}\label{harm}
f(m,n)=\frac{1}{4}\left(f(m-1,n)+f(m+1,n)+f(m,n-1)+f(m,n+1)\right)
\end{equation}
для всех $m,n\in\mathbb{Z}$. Докажите, что $f(m,n)$ является
константой.
\end{pr}

\begin{pr} \emph{Существование потенциалов}. Докажите, что существует такая функция $f(m,n)$ на $\mathbb{Z}^2$, что $f(0,0)=0$, $f(0,1)=1$, для каждого $(m,n)\ne (0,0),(0,1)$
условие (\ref{harm}) выполняется,
%we have $f(m,n)=\frac{1}{4}\left(f(m-1,n)+f(m+1,n)+f(m,n-1)+f(m,n+1)\right)$,
и $f(m,n)$ стремится к $1/2$ при стремлении
$r(m,n):=\sqrt{m^2+n^2}$ к бесконечности.
\end{pr}

\begin{pr} \emph{Функция Грина}. Пусть $f(m,n)$ --- сопротивление $2$-мерной решетки между началом координат и точкой $(m,n)$.

\noindent\textbf{(A)} Докажите, что для каждого $(m,n)\ne (0,0)$
условие (\ref{harm}) выполнено.
%we have $r(m,n)=\frac{1}{4}\left(r(m-1,n)+r(m+1,n)+r(m,n-1)+r(m,n+1)\right)$.

\noindent\textbf{(B)} Докажите, что $f(m,n)=g(r(m,n))+O(1)$ для
некоторой функции $g(x)$.

\noindent\textbf{(C)} Докажите, что сопротивление между и центром
и границей диска радиуса $r$, вырезанного из $2$-мерной решетки
равно $\frac{1}{2\pi}\ln r+O(1)$.

\noindent\textbf{(D)} Докажите, что $f(m,n)=\frac{1}{2\pi}\ln
r(m,n)+O(1)$.
\end{pr}

\begin{pr} Найдите с точностью до сотых вероятность того, что при случайном блуждании по $3$-мерной решетке мы вернемся в начальную точку.
\end{pr}

\begin{pr} Робот ходит по вершинам $3$-мерной решетки, переходя каждый раз в одну из соседних вершин. В одной из вершин находится клад; робот находит его, когда оказывается в вершине с кладом.
Существует ли программа, управляющая движением робота и
использующая конечный объем памяти и генератор случайных чисел,
такая, что робот найдет клад с вероятностью~$1$?
\end{pr}


\newpage
\large


\section{Указания и решения}

\noindent\textbf{\ref{1-1}} \textbf{(A)} Правильность работы
программы проверяется следующим образом: разность между
``настоящей'' и посчитанной вероятностями должна быть
пропорциональна числу $\frac{1}{\sqrt{n}}$, где $n$ --- число
экспериментов.



\noindent\textbf{(B)} Ответ смотрите в таблице.

\begin{table}[h]
\caption{Вероятности $P_T(x)$ и $P(x)$}
\begin{center}
%\normalsize
\begin{tabular}{|cc|c|c|c|c|c|c|}
\hline
    & $x$ & $0$ & $1$ & $2$ & $3$ & $4$ & $5$  \\
$T$ &     &     &     &     &     &     &      \\
\hline
$1$ &     & $0.00$ & $0.00$ & $0.00$ & $0.00$ & $0.50$ & $1.00$ \\
\hline
$2$ &     & $0.00$ & $0.00$ & $0.00$ & $0.25$ & $0.50$ & $1.00$ \\
\hline
$3$ &     & $0.00$ & $0.00$ & $0.13$ & $0.25$ & $0.63$ & $1.00$ \\
\hline
$4$ &     & $0.00$ & $0.06$ & $0.13$ & $0.38$ & $0.63$ & $1.00$ \\
\hline
 & $P(x)$ & $0.00$ & $0.20$ & $0.40$ & $0.60$ & $0.80$ & $1.00$ \\
\hline
\end{tabular}
\end{center}
\end{table}

\noindent\textbf{(C)} \emph{Ответ}: $P(x)=x/5$; см последнюю
строку в таблице выше.

\noindent\emph{Доказательство}. Рассмотрим случайное блуждание по
точкам $0, 1, 2, \dots , n$. Обозначим за $P(x)$ вероятность дойти
из $x$ до $N$ раньше, чем до $0$. Рассмотрим получившуюся функцию
$P(x)$, определенную в точках $x = 0, 1, 2, \dots , n$. Она
обладает следующими свойствами:
\begin{enumerate}
\item $P(0) = 0$ и $P(n) = 1$. \item $P(x) = \frac12 P(x - 1) +
\frac12 P(x + 1)$ для каждого $x = 1, 2, . . . , n-1$.
\end{enumerate}
Свойство 1 следует из того, что при достижении точек $0$ и $n$
перемещения заканчиваются; для игры на монетки это означает конец
игры. Свойство 2 заключается в том, что вероятность попасть домой
из внутренней точки $x$ равна среднему арифметическому
вероятностей попадания домой из соседних точек. Свойство 2
выводится из следующего утверждения:

\smallskip
\noindent\textbf{Базовое Утверждение.} \emph{Пусть $E$ ---
некоторое событие, $F$ и $G$ --- два события, из которых всегда
случается ровно одно. Тогда}
$$
P(E) = P(F) \cdot P(E \text{ последует за } F) + P(G) \cdot P(E
\text{ последует за }G).
$$
%\smallskip

В нашем случае $E$=``человек дойдет до бара'', $F$=``первый раз он
пойдет налево'' и $G$=``первый раз он пойдет направо''. Тогда
получаем $P(E) = P(x)$, $P(F ) = P(G) = 1/2$ , $P(E \text{
последует за }F ) = P(x-1)$, $P(E \text{ последует за }G) =
P(x+1)$ и свойство 2 доказано.

Из этих двух свойств вытекает, что $P(x)$ представляет собой
арифметическую прогрессию $P(x)=x/n$.


\smallskip
\noindent\textbf{\ref{1-2}} \emph{Ответ}: $P(x)=x/5$; эта задача
эквивалентна задаче~\ref{1-1}(C).


\smallskip
\noindent\textbf{\ref{1-3}} \emph{Ответ}: $P(x)=\frac{(q/p)^x -
1}{(q/p)^5 - 1}$.

\noindent\emph{Указание}: Рассуждайте так же, как в решении
задачи~\ref{1-1}(C). Покажите, что свойства 1--2 надо заменить на
такие:
\begin{enumerate}
\item $P(0) = 0$ и $P(n) = 1$. \item $P(x) = q P(x - 1) + p P(x +
1)$ для каждого $x = 1, 2, . . . , n-1$.
\end{enumerate}
Выберите $A$ и $B$ такими, чтобы функция $f (x) = A(q/p)^x + B$
удовлетворяла новым свойствам 1--2.

\smallskip
\noindent\textbf{\ref{1-4}} \emph{Ответ}: $\approx 99.995\%$.
Точное значение: $1-\frac{(0.55/0.45)^{20} - 1}{(0.55/0.45)^{70} - 1}$; смотрите решение задачи% a particular case of
~\ref{1-3}.


\smallskip
\noindent\textbf{\ref{1-5}} \emph{Ответ}: $v(x)=x/5$.
\emph{Указание}. Из аксиом \ref{BC}--\ref{KCL} следует, что
функция $v(x)$ будет линейной для этой цепи.


\smallskip
\noindent\textbf{\ref{1-6}} \textbf{(A)} Пусть $M$ --- максимум
функции $v(x)$. Тогда если $v(x) = M$ для $x\not\in P\cup N$, то
это же равенство должно быть выполнено для $v(x-1)$ и $v(x + 1)$
так как $v(x)$ --- среднее арифметическое $v(x-1)$ и $v(x + 1)$.
Если $x - 1$ оказалась внутренней точкой, применяем то же самое
рассуждение и получаем $f (x - 2) = M$; продолжая рассуждение,
получаем $f (0) = M$. Для минимального значения аналогично.

\noindent\textbf{(B)} Положим $h(x) = v (x) - u(x)$. Тогда для
любой внутренней точки $x$ имеем:
$$
\frac{h(x - 1) + h(x + 1)}{2}=\frac{v (x - 1) + v (x + 1)}{2} -
\frac{u(x - 1) + u(x + 1)}{2}
$$
и поэтому функция $h(x)$ также удовлетворяет аксиоме~\ref{KCL}. Но
$h(x) = 0$ при $x$ из $P\cup N$; из принципа максимума получаем,
что максимальное и минимальное значения $h$ равны $0$. Значит,
$h(x) = 0$ и  $v (x) = u(x)$.

\noindent\textbf{(C)} \emph{Ответ}: $v(x)=x/n$, $C=1/n$; $C\to 0$
и $v(x)\to 0$ для каждого фиксированного $x$ при $n\to \infty$.

\noindent\emph{Указание}: Легко проверить, что функция $f(x):=x/n$
удовлетворяет аксиомам \ref{BC}--\ref{KCL}. Из единственности (см
\ref{1-6}(B)) следует, что $v(x)=x/n$.


\smallskip
\noindent\textbf{\ref{1-9}} \textbf{Теорема.} \emph{При случайном
блуждании по $1$-мерной решетке вероятность вернуться когда-либо в
начальную точку равна $1$.}

\noindent\emph{Доказательство}. Пусть $P$ --- вероятность
вернуться когда-либо в начальную точку. Обозначим $P_n$
вероятность вернуться в начальную точку до попадания в $n$ или
$-n$. Предположим, что все эти вероятности существуют. Тогда
$P_n\le P\le 1$ для любого $n$.

Сейчас мы докажем, что $P_n=1-1/n$. После первого ``хода'' человек
попадает в одну из точек $1$ и $-1$ с вероятностью $1/2$. Если он
оказался в точке $1$, то из задачи~\ref{1-1}(C) получаем, что
вероятность вернуться в начало до попадания в точку $n$ равна
$1-1/n$. Если он оказался в точке $-1$, рассуждаем аналогично.
Применяя Базовое Утверждение из решения задачи~\ref{1-1}(C),
получаем
$P_n=\frac12\left(1-\frac1n\right)+\frac12\left(1-\frac1n\right)=1-\frac1n$.
(Еще можно было заметить, что $P_n=1-C$, где $C=1/n$ ---
проводимость цепи из задачи~\ref{1-6}.)

Так как $1-1/n\le P\le 1$ для каждого $n$, то $P$ равно $1$.
$\square$



\smallskip
\noindent\textbf{\ref{2-1}} \emph{Ответ}: см. рисунок~\ref{fig51}
слева.

\begin{figure}[htb]
\begin{tabular}{ll}
\includegraphics[width=3cm]{networks-fig51.png} & \qquad
\includegraphics[width=3cm]{networks-fig52.png}
\end{tabular}
\caption{Вероятности $P(x)$ или потенциалы $v(x)$; см.
задачи~\ref{2-1} и~\ref{2-1a}.} \label{fig51}
\end{figure}

\noindent\emph{Указание}. Схема города представлена на
рисунке~\ref{fig51} справа. Вероятности $P(x)$ обозначены за $a$,
$b$, $c$, $d$, и $e$. Как и в $1$-мерном случае, функция $P(x)$
удовлетворяет аксиомам~\ref{BC}--\ref{KCL} из опредления
электрической цепи. Отсюда мы получаем систему линейных уравнений:
\begin{align*}
a &= (b + d + 2)/4;\\
b &= (a + c + 2)/4;\\
c &= (d + 3)/4;\\
d &= (a + c + e)/4;\\
e &= (b + d)/4.
\end{align*}
Ответ получаем, решая эту систему.

\smallskip
\noindent\emph{Замечание}. Нахождение точного решения для
двухмерной ``задачи Дирихле'' --- дело сложное; поэтому мы
рассмотрим два метода нахождения приближенных решений.

Первый метод использует случайные блуждания. Он называется
\emph{методом Монте-Карло}, так как случайные блуждания связаны с
вероятностями, а в Монте-Карло находится известные игорные дома,
азартные игры в которых тоже связаны с вероятностями. Мы
моделируем много случайных блужданий из точки $x$ и находим долю
путей, закончившихся в точках $E$. Из закона больших чисел
следует, что полученная оценка будет приближением для
``настоящей'' вероятности $P(x)$. Этот яркий и простой метод
позволяет находить решения, но он не очень эффективен.

Теперь опишем более эффективный \emph{метод релаксации}. Напомним,
что мы ищем функцию с заданными значениями на границе у которое
значение в любой внутренней точке равно среднему арифметическому
значений ее соседей. Возьмем какую-нибудь функцию с подходящими
граничными значениями и возьмем некоторую внутреннюю точку. В
общем случае значение функции не будет равно среднему
арифметическому значений в соседних точках. Тогда попробуем
``подогнать'': положим новое значение функции в этой точке равным
среднему арифметическому значений в соседних точках. Теперь будем
по очереди брать остальные внутренние точки и делать с ними ту же
операцию. Когда мы пройдем по всем внутренним точкам, функция не
будет удовлетворять аксиоме~\ref{KCL}, так как после изменения
значения функции в одной точке мы могли изменить значения в
соседних с ней точках, нарушив равенство. Тем не менее, полученная
функция будет ``лучше'' удовлетворять аксиоме~\ref{KCL}, чем та
функция, с которой мы начали; повторяя этот процесс (проходя
каждый раз по всем внутренним точкам) мы будем получать
приближения к решению лучше и лучше.



\smallskip
\noindent\textbf{\ref{2-1a}} \emph{Ответ}: см. рисунок~\ref{fig51}
слева; эта задача эквивалентна задаче~\ref{2-1}.



\smallskip
\noindent\textbf{\ref{2-3}}
\emph{Ответ}: \textbf{(A)} $2/5$;  \textbf{(B)} $1/2$; \textbf{(C)} $2/7$; \textbf{(D)} $2/5$.


\noindent\emph{Указание}.
Сведем задачу к задаче~\ref{2-6} при помощи следующего
утверждения:

\smallskip
\noindent\textbf{Физическая интерпретация вероятности.}
\emph{Вероятность того, что случайное блуждание по графу $G$ из
вершины $a$ достигнет вершины $h$ до возврата в $a$, равна}
$$
P=C/\mathop{deg}a,
$$
где $C$ --- проводимость графа $G$ (все резисторы единичные) между
$a$ и $h$, а $\mathop{deg}a$ --- число ребер, выходящих из вершины
$a$.



\smallskip
\noindent\textbf{\ref{2-5}} \textbf{(C)} \emph{Указание}. Функция
$v(x)$ однозначно определена на вершинах получившейся цепи.
Проверьте, что она удовлетворяет аксиомам \ref{BC}--\ref{KCL}.



\smallskip
\noindent\textbf{\ref{2-6}}
\emph{Ответ}: \textbf{(1A)} $6/5$; \textbf{(1B)} $2$; \textbf{(1C)} $6/7$; \textbf{(1D)} $2$.

\noindent\textbf{(2A)} $12/7$; \textbf{(2B)} $12/5$; \textbf{(2C)} $30/19$; \textbf{(2D)} $30/11$.

Короткое решение смотрите в разделе~\ref{symmetric}.

\noindent\textbf{(2A)} \emph{Указание}. Соединим точки $a$ и $b$ с
батарейкой; см. рисунок~\ref{fig5} справа. Потенциалы в точках $c$
и $d$ равны из симметрии; аналогично в точках $e$ и $f$. Таким
образом, наша схема эквивалентна схеме, изображенной на
рисунке~\ref{fig54} слева.

Используя формулы для параллельного и последовательного соединения
резисторов, эта цепь сводится в к цепи из одного резистора
сопротивлением $7/12$ ом (см рисунок~\ref{fig54} справа). Таким
образом, сопротивление равно $7/12$.

\begin{figure}[htbp]
\begin{tabular}[b]{l}
\includegraphics[width=3cm]{networks-fig53.png}\\
\end{tabular}
\begin{tabular}[t]{l}
\\
\includegraphics[width=3.5cm]{networks-fig54.png}
%\includegraphics[width=3cm]{networks-fig52.png}
\end{tabular}
\caption{Упрощение цепи; см решение задачи~\ref{2-6}.}
\label{fig54}
\end{figure}


\smallskip
\noindent\textbf{\ref{2-4}} \emph{Ответ}: $1/7$.
Решение аналогично решению задачи~\ref{2-3}.


\smallskip
\noindent\textbf{\ref{2-10}} \textbf{(A)}. Короткое решение
смотрите в разделе~\ref{symmetric}.

\noindent\textbf{(B)} Авторам неизвестно элементарное решение
задачи. Красивое решение, использующее дискретное преобразование
Фурье, вы можете найти в книге \cite{S}.

\smallskip
\noindent\textbf{\ref{2-7}} Смотрите раздел~\ref{symmetric}.

\smallskip
\noindent\textbf{\ref{2-8}} \textbf{(B)} \emph{Ответ}: $C\to 0$
при $n\to \infty$.

\noindent \emph{Указание}. Применим закон монотонности: объединим
вместе точки, расположенные на квадратах, как показано на
рисунке~\ref{fig55} сверху. Полученная цепь эквивалентна цепи на
рисунке~\ref{fig55} в центре. Так как можно заменить $n$
параллельных резисторов в $1$ ом на один резистор в $1/n$ ом, цепь
эквивалентна цепи на рисунке~\ref{fig55} снизу. Проводимость этой
цепи равна
$$
\frac{1}{\sum_{k=1}^n \frac{1}{8k-4}}.
$$
Это число стремится к нулю при стремлении $n$ к бесконечности. Так
как проводимость старой цепи не больше, она тоже стремится к нулю.

\begin{figure}[htbp]
\begin{tabular}{l}
\includegraphics[width=3.5cm]{networks-fig55.png}\\[15pt]
\includegraphics[width=11cm]{networks-fig56rus.png}\\[15pt]
\includegraphics[width=11cm]{networks-fig57rus.png}
\end{tabular}
\caption{Объединение в квадратной цепи и эквивалентная цепь; см
решение задачи~\ref{2-8}.} \label{fig55}
\end{figure}




\smallskip
\noindent\textbf{\ref{2-9}} \emph{Указание}. Пусть $P$ ---
вероятность того, что при случайном блуждании по $2$-мерной
решетке мы вернемся в начальную точку. Обозначим за $P_n$
вероятность того, что случайное блуждание вернется в начальную
точку до достижения граничных точек квадрата $2n\times 2n$ с
центром в начальной точке. Предположим, что все эти вероятности
существуют. Ясно, что $P_n\le P\le 1$ для каждого $n$. Из
физической интерпретации вероятности получаем, что $P_n=1-C/4$,
где $C$ --- эффективное сопротивление между центром и границей
квадрата $2n\times 2n$. Из решения задачи~\ref{2-8}(B) следует,
что $C$ стремится к нулю при стремлении $n$ к бесконечности.
Поэтому $P_n\to 1$ при $n\to\infty$ и $P$ равно $1$. $\square$


\smallskip
\noindent\textbf{\ref{9.99}} См., например, статью \cite{PS}.




\smallskip
\noindent\textbf{\ref{suschestvovanie}} \textbf{(B)} Рассмотрим случайное блуждание по электрической
цепи. Пусть $P_T(x)$ --- вероятность того, что, стартуя из вершины $x$ и делая
$T$ шагов, мы достигнем положительного полюса батареи раньше, чем
отрицательного. Ясно, что при фиксированном $x$ последовательность $P_T(x)$
возрастает, значит, имеет предел $P(x)$. Функция $P(x)$ удовлетворяет аксиомам \ref{BC}--\ref{KCL}.

\emph{Замечание}. Существование и единственность решения системы
Кирхгофа - факты действительно фундаментальные. Например, из
единственности решения следует теорема Дена о том, что
прямоугольник с иррациональным отношением сторон нельзя разрезать
на квадраты. Из существования решения (в непрерывном случае)
следует теорема Римана о конформном отображении \cite{CF}.

%В статье есть любопытная дискуссия на эту тему.

\smallskip
\noindent\textbf{\ref{9.101}} См., например, статью \cite{PS}.


\smallskip
\noindent\textbf{\ref{formula}} \textbf{(A)} Пусть правильный граф содержит $n$ вершин и $A_1$,
$A_2$~--- соседние вершины степеней $k_1$ и $k_2$ соответственно.
Рассмотрим сначала ситуацию, когда в вершину $A_1$ подается ток
$\frac{n-1}{n}$, а из всех остальных вершин вытекает ток
$\frac{1}{n}$. В силу правильности графа по ребру $A_1A_2$ будет
течь ток $\frac{1}{k_1}\left(1-\frac{1}{n}\right)$. Если же ток
$\frac{n-1}{n}$ подается в вершину $A_2$, а из остальных вершин
вытекает ток $\frac{1}{n}$, то по ребру $A_1A_2$ будет течь ток
$\frac{1}{k_2}\left(1-\frac{1}{n}\right)$. Объединим обе
ситуации, заменив во втором случае все токи на противоположные.
Тогда получится, что в вершину $A_1$ подается единичный ток,
который вытекает из вершины $A_2$. При этом по ребру $A_1A_2$
течет ток
$\left(\frac{1}{k_1}+\frac{1}{k_2}\right)\left(1-\frac{1}{n}\right)$.
Значит, сопротивление между вершинами $A_1A_2$ равно
$\left(\frac{1}{k_1}+\frac{1}{k_2}\right)\left(1-\frac{1}{n}\right)$.

Если граф бесконечный, то $1/n$ нужно заменить нулем.
Корректность обосновывается с помощью предельного перехода.

Формула для сопротивления между соседними вершинами правильного
графа принадлежит А.Б.\,Ходулёву. Вместе с определением
правильного графа она взята из статьи \cite{G}.

\noindent\textbf{(B)} Решим сначала задачу на физическом уровне строгости. Наложим шину с нулевым сопротилением на периметр
прямоугольника $[-N,N+1]\times[-N,N]$. Поскольку при подключении
батарейки к узлам $(0,0)$ и $(1,0)$ потенциалы на бесконечности
стремятся к нулю, то наложение шины мало повлияет на значение
искомого сопротивления. (Дальнейшие рассуждения также проводятся с
точностью до погрешности, которая стремится к нулю с ростом $N$.)
Если источник единичного тока подключен к точке $(0,0)$ и шине,
то из точки $(0,0)$ в каждый из четырех соседних узлов течет ток
равный $1/4$. Если же источник единичного тока подключен к шине и
точке $(1,0)$, то из четырех соседних узлов в точку $(1,0)$
втекает ток равный $1/4$. Значит, при подключении обоих
источников тока по ребру $(0,0)-(1,0)$ будет течь ток $1/2$, и
разность потенциалов в этих точках тоже будет равна $1/2$. Но
между ними течет общий ток равный единице, поэтому эквивалентное
сопротивление решетки между соседними узлами равно $1/2$.

Придадим этим рассуждениям математическую строгость. Снова
предположим, что источник единичного тока подключен к точке
$(0,0)$ и шине с нулевым сопротилением, наложенной на периметр
прямоугольника $[-N,N+1]\times[-N,N]$. Согласно задаче~\ref{ring-1}
сопротивление $R$ такого графа не превосходит $N^{1/2}$, поэтому
при нулевом потенциале на шине потенциал $V$ в точке $(0,0)$ не
превосходит $N^{1/2}$:
\begin{equation}
\label{Resist.Pot} V=IR=R\le N^{1/2}.
\end{equation}
Покажем, что потенциал в точках, близких к наложенной шине, мало
отличается от нуля. Обозначим через $u_j$ наибольший потенциал на
периметре прямоугольника $[-j,j+1]\times[-j,j]$. Тогда из
гармоничности распределения потенциалов следует, что $u_{j-1}\ge
2u_j-u_{j+1}$ ($1\le j\le N-1$). Поэтому, если
$u_{N-1}=\varepsilon$ (по предположению $u_N=0$), то для всех $j$
в пределах $0\le j\le N$ будет выполняться неравенство $u_j\ge
(N-j)\varepsilon$. В частности, $u_0=V\ge N\varepsilon$. Учитывая
неравенство~\eqref{Resist.Pot}, получаем, что $\varepsilon\le
N^{-1/2}.$

Если теперь наложить шину по периметру квадрата
$[-N,N]\times[-N,N]$, то получится новое (симметричное)
распределение потенциалов, которое, согласно принципу максимума,
отличается от исходного не более чем на $N^{-1/2}.$ Значит, до
переноса правого края шины четыре тока, выходящие из точки
$(0,0)$ отличались от $1/4$ не более чем на $N^{-1/2}.$
Аналогично, если источник тока подключен к шине и к точке $(1,0)$,
то из четырех соседних узлов в точку $(1,0)$ втекают четыре тока,
отличающиеся от $1/4$ не более чем на $N^{-1/2}.$

Объединяя обе ситуации, получаем, что в прямоугольнике
$[-N,N+1]\times[-N,N]$ с закороченным периметром источник
единичного тока подключен к узлам  $(0,0)$ и $(1,0)$, а по ребру
$(0,0)-(1,0)$  течет ток $1/2+O(N^{-1/2})$. Значит, разность
потенциалов, а соответственно и сопротивление, равны
$1/2+O(N^{-1/2})$.

Для завершения доказательства применим аксиому~3.
Рассмотрим батарейку, подключенную к точкам $(0,0)$ и $(1,0)$
так, что потенциалы в этих точках равны $1/4$ и $-1/4$
соответственно. Ток, протекающий между $(0,0)$ и $(1,0)$
обозначим через $I$. Выберем прямоугольник $[-N,N+1]\times[-N,N]$
так, чтобы потенциалы на его периметре по модулю не превосходили
некоторого $\varepsilon>0$. При замене всех потенциалов на
периметре прямоугольника нулями, согласно принципу максимума, все
потенциалы внутри так же изменятся не более чем на
$\varepsilon>0$. Тогда получится, что ток $I$ течет между узлами
с разностью потенциалов $1/2+O(\varepsilon)$, а сопротивление
между которыми равно $1/2+O(N^{-1/2})$. Следовательно
$I=1+O(\varepsilon)+O(N^{-1/2})$. Так как $\varepsilon$ может
быть выбрано сколь угодно малым, а $N$ растет при уменьшении
$\varepsilon$, то ток $I$ в точности равен единице. Он течет
между узлами с разностью потенциалов $1/2$, значит, эквивалентное
сопротивление решетки между соседнми узлами в точности равно
$1/2$.




%\textbf{Решение} задачи можно разбить на два шага: 1) вычисление
%сопротивления между соседними вершинами; 2) нахождение тока по
%противоположному ребру. Оба эти шага можно сделать не только для
%икосаэдра, но и более общем случае.

%Предположим, что имеется граф $\Gamma$, у которого сопротивление
%каждого ребра равно $1$. Возьмем в графе $\Gamma$ два смежных
%ребра $AB$ и $AC$. Эти ребра назовем \textit{эквивалентными},
%если существует автоморфизм графа, переводящий $A$ в $A$ и $B$ в
%$C$. Вершину графа назовем центром симметрии графа $\Gamma$, если
%все ребра, инцидентные ей, эквивалентны. Граф $\Gamma$ называется
%\textit{правильным}, если все его вершины~--- центры симметрии
%графа. Примеры правильных графов: правильные многогранники любой
%размерности; правильные решетки на евклидовой плоскости и
%плоскости Лобачевского и их многомерных аналогах; симметричные
%решетки на торе и т.\ п. Нетривиальный пример: граф
%ромбододекаэдра. Это многогранник, который получается, если к
%каждой грани куба приставить по четырехугольной пирамиде так, что
%все треугольники, граничащие по ребрам куба, сольются в ромбы.
%Поверхность ромбододекаэдра состоит из $12$ ромбов. Он
%нетривиален тем, что его вершины имеют разную степень ($3$ и $4$).

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

\smallskip
\noindent\textbf{\ref{protivotok}} Пусть теперь $B_1$ и $B_2$~--- вершины графа,
диаметрально противоположные $A_1$ и $A_2$ соответственно. Мы
доказали, что если в $A_1$ подается единичный ток, который
вытекает из вершины $A_2$, то по ребру $A_1A_2$ течет ток
$I=\left(\frac{1}{k_1}+\frac{1}{k_2}\right)\left(1-\frac{1}{n}\right)$.
Ток текущий при этом по ребру $B_2B_1$ обозначим через $x$.
Дополнительно подключим источник единичного тока к вершинам $B_1$
и $B_2$ (в $B_2$ подается, из $B_1$~--- вытекает). Тогда по
каждому из ребер $A_1A_2$ и $B_2B_1$ будет течь ток $I+x$. Но то
же распределение токов получится, если единичный ток подается в
вершину $A_1$ и вытекает из $B_1$, а дополнительный ток подается
в $B_2$ и вытекает из $A_2$. В такой ситуации в силу правильности
графа первый источник по ребру $A_1A_2$ дает ток $\frac{1}{k_1}$,
а второй~--- $\frac{1}{k_2}$. Отсюда
\begin{gather*}
I+x=\left(\frac{1}{k_1}+\frac{1}{k_2}\right)\left(1-\frac{1}{n}\right)+x=\frac{1}{k_1}+\frac{1}{k_2},\\
x=\left(\frac{1}{k_1}+\frac{1}{k_2}\right)\frac{1}{n},\qquad
\frac{x}{I}=\frac{1}{n-1}.
\end{gather*}
Поэтому для икосаэдра получается ток $\frac{I}{11}$,
додекаэдра~--- $\frac{I}{19}$, ромбододекаэдра~---
$\frac{I}{13}$, куба~--- $\frac{I}{7}$. %(что неинтересно, потому
%что и так легко посчитать).

\smallskip
\noindent\textbf{\ref{posle_3.114'}} \emph{Указание}. Суммы $D_n$ и $F_n$ удовлетворяют
одному и тому же рекуррентному соотношению. Например,
$D_n=1+\dfrac{n+1}{2n}D_{n-1}.$ Кроме того, $D_0=F_0=1$.
Следовательно, они равны друг другу. Значит, при $n\ge1$
$$\sum\limits_{k=1}^{n}\dfrac{2^k}{k}=\dfrac{2^n}{n}F_{n-1}=
\dfrac{2^n}{n}D_{n-1}=\dfrac{2^n}{n}\sum\limits_{k=0}^{n-1}\dfrac{1}{C_{n-1}^k}.$$
Для завершения доказательства нужно оценить степень вхождения
числа $2$ в общий знаменатель дробей из полученной суммы с помощью
формулы Лежандра для показателя, с которым простое число входит в
разложение факториала.

Сопротивление $n$-мерного проволочного куба (у которого каждое
ребро имеет единичное сопротивление) между противоположными
вершинами  $R_n$ связанно с данными суммами равенствами (более
подробно см. в статье \cite{NS}).
$$D_n=F_n=(n+1)R_{n+1}.$$

\smallskip
\noindent\textbf{\ref{3-1}} \emph{Указание}. Докажите по индукции,
что сопротивление бинарного дерева глубины $n$ из единичных
резисторов равно $1-\frac{1}{2^n}$.

\smallskip
\noindent\textbf{\ref{3-2}} \emph{Указание}. Потенциалы в точках,
расположенных на одинаковом расстоянии от корня дерева, равны из
симметрии. Объединив такие точки в бинарном дереве, получим цепь,
изображенную на рисунке~\ref{fig31zrus}. Ее сопротивление равно
$\frac{1}{2}\cdot n=\frac{n}{2}$. Для троичного дерева аналогично
получаем $R=\frac{1}{3}+\frac{2}{9}+\dots+\frac{2^{n-1}}{3^n}$.
Отсюда $R=1-\frac{2^n}{3^n}$.

\begin{figure}
\includegraphics[width=10cm]{networks-fig31zrus.png}
\caption{Подсчет сопротивления дерева; см решение
задачи~\ref{3-2}.} \label{fig31zrus}
\end{figure}

\smallskip
\noindent\textbf{\ref{3-4}} \emph{Указание}. Двоичное дерево
глубины $3$ вырезать не сложно. Покажем, что двоичное дерево
глубины $2010$ вырезать нельзя. Если его удалось вырезать, то все
его вершины расположены на расстоянии не более $2010$ от корня;
отсюда получаем, что дерево находится в кубе со стороной
$2\cdot2010+1$. Поэтому число его вершин не превосходит
$4021^3\leq2^{36}$. С другой стороны, число его вершин равно
$2^{2011}-1$. Полученное противоречие завершает доказательство.
Задача о вырезании модифицированного дерева решается не просто.

\smallskip
\noindent\textbf{\ref{3-5}} \emph{Указание}. Двоичное дерево
вырезать нельзя; рассуждайте аналогично решению задачи \ref{3-4},
пользуясь тем, что более двух вершин склеиться не могут.
Модифицированное двоичное дерево можно вырезать из плоскости (см
рисунок \ref{fig58}), а троичное из пространства аналогичным
образом (см рисунок \ref{fig59}). Доказательство проводится
индукцией по глубине дерева.
\begin{figure}

\includegraphics[width=10cm]{networks-fig58.png}
\caption{Вырезание двоичного дерева с пересечениями из плоскости;
см решение задачи~\ref{3-5}.} \label{fig58}
\end{figure}
\begin{figure}

\includegraphics[width=10cm]{networks-fig59.png}
\caption{Вырезание троичного дерева с пересечениями из
пространства; см решение задачи~\ref{3-5}.} \label{fig59}
\end{figure}

\smallskip
\noindent\textbf{\ref{3-6}} \emph{Указание}. Для любого $n=2^i-1$
рассмотрим множество вершин $(x,y,z)$, где $|x|+|y|+|z| \leq n$.
Пусть $R_i$ --- сопротивление между началом координат и границей
такой фигуры. Как известно из задачи \ref{3-5}, из такой части
решетки можно вырезать модифицированное троичное дерево глубины
$i$ с пересечениями ребер на равном расстоянии от корня. Легко
заметить, что сопротивление дерева с такими пересечениями равно
сопротивлению такого же дерева без пересечений. Как известно из
задачи~\ref{3-2}, сопротивления модифицированных троичных деревьев
не превосходят $1$. Поэтому не превосходят $1$ и сопротивления
вырезаемых деревьев с пересечениями. Из закона монотонности
получаем, что $R_i\leq 1$. Значит, при подключении батарейки в 1
вольт ток будет не меньше $1$. Следовательно, потенциалы в
вершинах, соседних с началом координат будут не больше
$1-\frac{1}{6}=\frac{5}{6}$. Они равны вероятности возврата в
начало координат до попадания на границу. Переходя к пределу,
получаем требуемое.


\smallskip
\noindent\textbf{\ref{ring-0}} Рассмотрим точки $A(2,3)$, $B(3,3)$, $C(1,2)$,
$D(2,2)$, $E(3,2)$, $F(4,2)$, $G(2,1)$, $H(3,1)$. Сначала
подсоединим источник тока, который подает единичный ток в начало
координат, а вторым концом подсоединен к контуру с нулевым
сопротивлением, наложенному на периметр квадрата $[-R,R]^2$.
Из-за симметрии для некоторого числа $I$ будут выполняться
равенства $i(CD)=i(GD)=i(DA)=i(DE)=I$. Рассмотрим теперь другую
ситуацию, когда единичный ток подается на периметр квадрата
$[-R,R]^2$ и выходит из точки $(1,0)$. Тогда $i(DE)\approx
i(HE)\approx i(EB)\approx i(EF)\approx -I$. Здесь равенство
понимается с точностью до малого $\varepsilon$, которое стремится
к нулю с ростом $R$ (как и в задаче~\ref{formula}, это следует из
аксиомы~3). Комбинируя обе ситуации получаем, что когда
источник тока подключен к узлам $(0,0)$, $(1,0)$, а на периметр
квадрата $[-R,R]^2$ наложен контур с нулевым сопротивлением, по
ребру $DE$ течет ток меньший, чем $\varepsilon$. Устремляя $R$ в
бесконечность (и снова применяя аксиому~3), приходим к
утверждению задачи.

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

\smallskip
\noindent\textbf{\ref{ring-1}}
Рассмотрите какое-нибудь дерево, соединяющее данную
точку с периметром квадрата.

\smallskip
\noindent\textbf{\ref{ring-2}} Примените принцип максимума.

\smallskip
\noindent\textbf{\ref{ring-3}} Запишем оператор Лапласа в виде $$\Delta
f(x,y)=f(x-1,y) + f(x+1,y)-2f(x,y) + f(x,y-1) +
f(x,y+1)-2f(x,y).$$ Тогда для функции $f(x,y)=\ln r(x,y)$
\begin{gather*}
f(x-1,y) +
f(x+1,y)-2f(x,y)=\frac12\ln\frac{((x+1)^2+y^2)((x-1)^2+y^2)}{(x^2+y^2)^2}=\\=
\frac12\ln\left(1+\frac{2x+1}{r^2}\right)\left(1+\frac{-2x+1}{r^2}\right)=
\frac12\ln\left(\left(1+\frac{1}{r^2}\right)^2-\frac{4x^2}{r^4}\right).
\end{gather*}
Аналогично
\begin{gather*}
f(x,y-1) + f(x,y+1)-2f(x,y)=
\frac12\ln\left(\left(1+\frac{1}{r^2}\right)^2-\frac{4y^2}{r^4}\right).
\end{gather*}
Поэтому
\begin{gather*}
\Delta f(x,y)=
\frac12\ln\left(\left(1+\frac{1}{r^2}\right)^2-\frac{4x^2}{r^4}\right)\left(\left(1+\frac{1}{r^2}\right)^2-\frac{4y^2}{r^4}\right)=\\=
\frac12\ln\left(1-\frac{1}{r^4}+\frac{16x^2y^2}{r^8}\right)=
\frac12\ln\left(1+O\left(\frac{1}{r^4}\right)\right)=O\left(\frac{1}{r^4}\right).
\end{gather*}

\smallskip
\noindent\textbf{\ref{ring-4}} Если точка $(x,y)$ лежит вблизи границы кольца, то в
ней имеет смысл изменить определение оператора Лапласа, чтобы оно
согласовывалось с правилами Кирхгофа. Например, если для
некоторых $a$, $b\in[0,1)$ точки $(x-a,y)$ и $(x,y-b)$ попадают
на границу, то будем считать, что
$$\Delta f(x,y)=\frac{f(x-a,y)-f(x,y)}a + \frac{f(x,y-b)-f(x,y)}b +f(x+1,y) +
f(x,y+1)-2f(x,y).$$ Тогда для функции $f(x,y)=\ln r(x,y)$ в такой
точке
$$\frac{f(x-a,y)-f(x,y)}a + f(x+1,y) -f(x,y)=\frac1{2a}\ln\left(1+\frac{-2ax+a^2}{r^2}\right)+
\frac1{2}\ln\left(1+\frac{2x+1}{r^2}\right)=O\left(\frac{1}{r^2}\right).$$
Аналогично
$$\frac{f(x,y-b)-f(x,y)}b + f(x,y+1) -f(x,y)=O\left(\frac{1}{r^2}\right).$$
Таким образом $\Delta f(x,y)=O\left(r^{-2}\right)$, причем эта
оценка остается справедливой, если из четырех соседних с $(x,y)$
точек лишь одна лежит за пределами кольца.

Рассмотрим теперь функцию $f(x,y)=U_n(x,y)-\ln r(x,y).$ Она равна
нулю на границе кольца, а во всех внутренних точках удовлетворяет
уравнению $\Delta f(x,y)=\varphi(x,y)$, где
$\varphi(x,y)=O(n^{-2})$ в точках вблизи границы, и
$\varphi(x,y)=O(n^{-4})$ в остальных точках кольца.

Значения функции $\varphi(x,y)$~--- это токи, которые подаются в
соотвествующие узлы кольца. Потенциалы, индуцированные токами в
точках вблизи границы оцениваются как $O(n^{-2})$. Действительно,
если, считать, что во все внутренние точки области имеют равный
потенциал $U$, то в точки границы текут токи не меньше чем $U$.
Поэтому, при замене всех токов на $U$ потенциалы внутри области
не увеличатся.

Оценим теперь потенциал порождаемый токами в остальных точках
(отделенных от границы). Число таких точек есть $O(n^2)$, и ток в
каждой из них (согласно задаче~\ref{ring-2}) приводит к
потенциалам не превосходящим $O(n^{-7/2})$. Поэтому общий
потенциал, порожденный внутренними токами есть $O(n^{-3/2})$. То
есть $f(x,y)=O(n^{-3/2})$.

\smallskip
\noindent\textbf{\ref{ring-5.0}} Воспользуемся равенством $$\arctg x-\arctg y=\arctg
\frac{x-y}{1+xy},$$ которое справедливо при $|xy|<1$. Тогда
\begin{gather*}
\arctg\frac{y+1}R-\arctg\frac{y}R=\arctg\frac{1/R}{1+y(y+1)/R^2}=\\=
\arctg\left(\frac{R}{y^2+R^2}+O\left(\frac{1}{R^2}\right)\right)=\frac{R}{R^2+y^2}+O\left(\frac1{R^2}\right).\end{gather*}




\smallskip
\noindent\textbf{\ref{ring-5.1}} Просуммируйте формулу из задачи~\ref{ring-5.0}.

\smallskip
\noindent\textbf{\ref{ring-5}} Для нахождения сопротивления кольца найдем ток,
который будет через него протекать при условии, что на внутренний
контур кольца подается напряжение $\ln nr_1$, а на внешний~---
$\ln nr_2$. Будем искать ток протекающий через периметр квадрата
$[-R-1/2,R+1/2]^2$, где $R=[r_1n]+1$. Посчитаем его приближенно,
заменяя потенциалы в узлах на значения функции $\ln r(x,y)$.
Всего будет просуммировано $O(n)$ токов, каждый с погрешностью
$O(n^{-3/2})$. Поэтому итоговая погрешность будет равна
$O(n^{-1/2})$.

В силу симеетрии квадрата, протекающий через его периметр ток
может быть записан в виде
$$I=8\sum\limits_{y=0}^R\left(\ln r(R+1,y)-\ln r(R,y)\right)+O\left(\frac1{n^{1/2}}\right).$$
Так как $$\ln r(R+1,y)-\ln
r(R,y)=\frac{R}{R^2+y^2}+O\left(\frac1{R^{2}}\right),$$ то,
применяя формулу из задачи~\ref{ring-5.1}, получаем нужное
равенство $I=2\pi+O(n^{-1/2}).$

\smallskip
\noindent\textbf{\ref{ring-6}} Как и в предыдущей задаче, для вычисления
сопротивления нужно найти ток, протекающий через замкнутую
ломаную, опоясывающую внутреннюю окружность. Снова для
приближенного нахождения тока потенциалы в узлах решетки можно
заменить на значения функции $\ln r(x,y)$. Если теперь ломаную
заменить на описанный около нее квадрат, то внутри полученного
контура появится $O(n^2)$ новых источников тока, в каждом из
которых втекает или вытекает ток равный $O(n^{-4})$. Значит,
искомое значение для суммарного тока отличается от уже найденного
тока через периметр квадрата $I=2\pi+O(n^{-1/2})$ не более чем на
$O(n^{-2})$.

\smallskip
\noindent\textbf{\ref{ring-7}} Докажем, что в задаче \ref{ring-1} сопротивление
между любым узлом квадрата и его границей есть $O(\ln n)$. Тогда и
во всех следующих задачах при буквальном повторении доказательств
все остаточные члены умножаться на $\frac{\ln n}{\sqrt n}$.

Вместо квадрата рассмотрим треугольник, вырезанный из квадратной
сетки прямыми $x=0$, $y=0$, $x+y=n$, и оценим его сопротивление
между началом координат и гипотенузой. Будем предполагать, что в
целых точках на отрезка $x+y=k$, $x$, $y\ge0$ потенциалы равны
$V_k=\sum_{j=2}^{k+1}\frac1j$ ($0\le k\le n$). В частности, в
начале координат потенциал нулевой. Будем также предполагать, что
в каждую точку на прямой $x+y=k$ втекает ток $1/k$, то есть через
каждый уровень протекает единичный ток. Чтобы ситуация не
противоречила закону Ома, сопротивления внутри треугольника нужно
будет увеличить. (Сопротивления, соединяющие точки вида $(0,k)$,
$(k,0)$ с точками $(0,k+1)$, $(k+1,0)$ остаются единичными.)
Чтобы выполнялся закон Кирхгофа, из точки $(j, k-j)$ должны течь
токи $\frac{k-j}{k(k+1)}$ и $\frac{j+1}{k(k+1)}$ в точки
$(j,k-j+1)$ и $(j+1,k-j)$ соответственно. Посколку разность
потенциалов равна $1/(n+1)$, то единичные сопротивления нужно
будет заменить на сопротивления $\frac{k}{k-j}$ и $\frac{k}{j+1}$
соответственно. Полученная схема имеет сопротивление $V_n\le \ln
n$. Значит, сопротивление исходной схемы также не превосходит
$\ln n$.



\section{Благодарности}

Большинство задач частей 1, 2 и 4 данного проекта заимствованы из статьи П. Дойля и Дж. Снелл \cite{PS}. Авторы благодарны И. Богданову, В.~Бугаенко и М. Прасолову за помощь при переводе данногог проекта.


 

\begin{thebibliography}{9}

\bibitem{BS} I. Benjamini and O. Schramm, \textrm{Random walks and harmonic functions on infinite planar graphs using square tilings}, Ann. Prob. \textbf{24:3} (1996), 1219--1238.

\bibitem{CF} J. Cannon, W. Floyd, W. Parry, \textrm{Squaring rectangles: the finite Riemann mapping theorem},
Contemp. Math. \textbf{169} (1994), 133--211.

\bibitem{DS} P. G. Doyle and J. L. Snell,
  \textrm{Random walks and electric networks},
  Mathematical Association of America, 1984,
  \url{http://arxiv.org/abs/math.PR/0001057}.


\bibitem{G} Г.А.\,Гальперин ``Мой друг Андрей Ходулёв'' (Математическое просвещение, сер. 3, вып. 4 (2000), 8--32,\\
\url{http://www.mccme.ru/free-books/matpros/i5008032.pdf.zip}.

\bibitem{NS} %F. Nedemeyer, A. Smorodinskiy, \textit{Resistance of edges of higher dimensional cube}, Kvant \textbf{6} (1986), in Russian.
Ф.\,Недемейер и Я.\,А.\,Смородинский,
\textit{Сопротивление ребер многомерного куба}, Квант, \No~6, 1986.

\bibitem{PS} M. Prasolov and M. Skopenkov, \textit{Tiling by rerctangles and alternating current}, submitted (2010). \url{http://arxiv.org/abs/1002.1356}.

\bibitem{S} F. Spitzer, \textrm{Principles of random walks}, Springer--Verlag, 1976.



\end{thebibliography}



\end{document}
