
\documentclass[14pt]{elsarticle-mod}

%\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{Summer conference of the International mathematical tournament of towns}
\dates{2--10 August 2010}

\usepackage[pdftex,%
            colorlinks,linkcolor=red,citecolor=blue,urlcolor=blue,%
            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*}{Definition}
\newtheorem{pr}{}[section]


\begin{document}

\Large

%

\begin{frontmatter}

%\begin{titlepage}

\title{Random walks through electrical networks}

\author{Dmitry Baranov}

\author{Mikhail Skopenkov}
\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{Alexey Ustinov}


\begin{abstract}
The aim of the project is to prove the following result and investigate related problems.

\noindent{\bf The Polya Theorem.}
\textbf{(a)} \emph{A man which is randomly walking in a $2$-dimensional lattice will return to the initial point with probability $1$}.

\noindent\textbf{(b)} \emph{A man which is randomly walking in a $3$-dimensional lattice will return to the initial point with probability strictly less than $1$.}

Accurate statements are given in the project. The suggested approach to the result is based on a physical interpretation. However, no physical background is assumed.

\begin{center}
\includegraphics[width=12cm]{networks-fig0.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{Walking in one dimension}\label{random}

Let us first state a problem and then give all the necessary definitions.

\begin{pr}\label{1-1}
A man walks along a $5$-block stretch of Madison Avenue. He starts
at corner $x$ and, with probability $1/2$, walks one block to the right and,
with probability $1/2$, walks one block to the left; when he comes to
the next corner he again randomly chooses his direction along Madison
Avenue. He continues until he reaches corner $5$, which is home, or
corner $0$, which is a bar. If he reaches either home or the bar, he stays
there; see Figure~\ref{fig1}.

\begin{figure}[hb]
\includegraphics[width=10cm]{networks-fig1.png}
\caption{Random walk along Madison Avenue; see Problem~\ref{1-1}.}
\label{fig1}
\end{figure}

\noindent\textbf{(A)*} Write a computer program which models the motion of the man.
Run the program a large number of times, and find the percentage of cases in which the man
returns home. You may use this to guess the answers in further problems.

\noindent\textbf{(B)} Let $P_T(x)$ be the probability that the man, starting at corner $x$ and making at most $T$ ''moves'', will reach home. Complete the following table by $2$-digit decimals.

\begin{table}[h]
\caption{The probabilities $P_T(x)$ for small $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)} Find the probability $P(x)$ that the man will reach home eventually.
\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)} Suppose that an experiment has $n$ \emph{equally possible} outcomes, and an event $X$ occurs in exactly $m$ of the outcomes. Then the \emph{probability} of the event $X$ is by definition the number
$P_1(X):=m/n$.

For instance, the probability of getting tails in a coin throw is $1/2$; the probability of getting $6$ points in a die roll is $1/6$; the probability that our walker moves one block to the right is $1/2$.

\noindent\textbf{(B)} Now suppose that the event $X$ depends on a sequence of such experiments. A sequence of $T$ experiments has $n^T$ possible outcomes.
%, each of them being a sequence $(r_1,r_2,\dots,r_T)$ of outcomes of individual experiments.
Assume that $X$ occurs for exactly $m_T$ outcomes %$(r_1,r_2,\dots,r_T)$
among them. Then the \emph{probability} of $X$ is the number $P_T(X):=m_T/n^T$.

For instance, there are $4$ possible outcomes of throwing a coin $2$ times:
%\smallskip
\begin{center}
{\normalsize
\begin{tabular}{l}
1st throw \\
2nd throw
\end{tabular}\qquad
\begin{tabular}{|c|}
\hline
heads \\
heads \\
\hline
\end{tabular}\quad
\begin{tabular}{|c|}
\hline
heads \\
tails \\
\hline
\end{tabular}\quad
\begin{tabular}{|c|}
\hline
tails \\
heads \\
\hline
\end{tabular}\quad
\begin{tabular}{|c|}
\hline
tails \\
tails \\
\hline
\end{tabular}
}
\end{center}
%\smallskip
Let the event $X$ be getting tails in at least one throw. The event $X$ occurs
for $3$ cases among the $4$ possible ones. Thus the probability of the event $X$ is $P_2(X)=3/4$.

The probability of getting more than $10$ points in two die rolls is $1/12$ because
this event occurs for $3$ cases ($5+6$, $6+5$ or $6+6$) among the $36$ possible ones.
The probability that our walker, starting at corner $3$, consequently moves right twice is $1/4$.

\noindent\textbf{(C)} Finally, suppose that the event $X$ depends on an infinite sequence of such experiments.
We say that the \emph{probability} of the event $X$ is $P(X)$, if the probabilities $P_T(X)$ tend to a number $P(X)$ as $T$ tends to infinity\footnote{Formally, this means that for each $\varepsilon>0$ there is a number $T_0$ such that for each $T>T_0$ we have $|P(X)-P_T(X)|<\varepsilon$.}.

For instance, the probability of getting tails at least once in an infinite sequence of coin throws is $P(X)=1$, because $P_T(X)=1-1/2^T$ tends to $1$ as $T$ tends to infinity.

You may use without proof that the probability $P(X)$ \emph{exists} for all the events $X$ considered in the project.
\end{definition*}

\begin{pr}\label{1-2}
%In another form, the problem is posed in terms of the following game:
Peter and Paul match pennies; they have a total of $5$ pennies; on each
match, Peter wins one penny from Paul with probability $1/2$ and loses
one with probability $1/2$; they play until Peter's fortune reaches $0$ (he
is ruined) or reaches $5$ (he wins all Paul's money). Find the
probability $P(x)$ that Peter wins if he starts with $x$ pennies.
\end{pr}

\begin{pr}\label{1-3} Assume that our walker has a tendency to drift in one
direction: more specifically, assume that each step is to the right with
probability $p$ or to the left with probability $q = 1-p$. Find the probability $P(x)$ in this case.
\end{pr}

\begin{pr}\label{1-4}  You are gambling against a professional gambler; you
start with $20$ dollars and the gambler with $50$ dollars; you play a game
in which you win one dollar with probability $0.45$ and lose one dollar
with probability $0.55$; play continues until you or the gambler runs
out of money. Find the probability of being ruined.
\end{pr}

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

\begin{definition*} An \emph{electrical network} is a connected finite graph with a positive real number (\emph{conductance}\footnote{The reciprocal of conductance is called \emph{resistance}.} $C(xy)$) assigned to each edge $xy$, and two disjoint marked sets of vertices ($P$ and $N$). The vertices of the set $N$ are joined with the ground and the negative pole of a battery, and the vertices of~$P$ are joined with the positive pole; see Figure~\ref{fig2}.

The \emph{voltages} $v(x)$ of the vertices in the network are defined by the following axioms:
\begin{enumerate}
\item\label{BC} \emph{Boundary condition}. If $x\in N$ then $v(x)=0$; if $x\in P$ then $v(x)=1$.
\item\label{KCL} \emph{Kirchhoff current law}. If $x\not\in P\cup N$ then
$\sum_{xy} C(xy)\left(v(x)-v(y)\right)=0$, where the summation is over all the edges $xy$ containing the vertex~$x$.
\end{enumerate}
The number $i(xy):=C(xy)\left(v(x)-v(y)\right)$ is the \emph{current} through edge $xy$;\ $i(x):=\sum_{xy} i(xy)$ is the \emph{current} flowing inside the network through vertex $x$ (thus $i(x)=0$ for each $x\not\in P\cup N$ by axiom~\ref{KCL}); \ $C:=\sum_{x\in P} i(x)$ is the \emph{effective conductance} of the network between the subsets $P$ and $N$;\  $Q:=\sum_{xy} C(xy)\left(v(x)-v(y)\right)^2$, where the summation is over all the edges of the network, is the \emph{heat power} of the network.
\end{definition*}

\begin{pr}\label{1-5}  We connect equal resistors in series and put a unit voltage across the ends as in
Figure~\ref{fig2}. Find the voltages $v(x)$ established at the points $x = 0, 1, 2, 3, 4, 5$.
Hereafter you may use network-simulation software to guess the answer.
\end{pr}

\begin{figure}[hb]
\includegraphics[width=10cm]{networks-fig2.png}
\caption{An electrical network; see Problem~\ref{1-5}.}
\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) defined 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} Consider the network with the vertices $0,1,\dots,n$, the edges $01,12,\dots,(n-1)n$ of unit conductance, and marked sets $N=\{0\}$, $P=\{n\}$.

\noindent\textbf{(A)} \emph{Maximum Principle}.
A function $v(x)$ satisfying the above axiom~\ref{KCL} takes on its maximum value and its minimum value on the set $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{Uniqueness Principle}. If $v(x)$ and $u(x)$ are two functions satisfying the above axioms~\ref{BC}--\ref{KCL} then $v(x) = u(x)$ for all $x$.

\noindent\textbf{(C)} Find the voltages $v(x)$ and the effective conductance of the network. To which numbers tend these values as $n$ tends to infinity?
\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} State and prove an analogue of the Polya theorem for the $1$-dimensional lattice.
\end{pr}



\section{Walking in two dimensions}\label{random2}

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

\begin{pr}\label{2-1}
Consider the town in Figure~\ref{fig3} to the left. Segments represent streets. Large dots marked $E$ indicate escape routes and those marked $P$ are police. Find with $2$-digit precision the probability $P(x)$
that our walker, starting at an interior point $x$, will reach an escape
route before he reaches a policeman. The walker moves from $x = (a, b)$
to each of the four neighboring points $(a + 1, b), (a - 1, b), (a, b + 1),
(a, b-1)$ with probability $1/4$. If he reaches one of the points $E$ or $P$, he remains
at this point.
\end{pr}

\begin{pr}\label{2-1a} Find the voltages $v(x)$ in the network (of unit resistors) in Figure~\ref{fig3} to the right.
\end{pr}

\begin{figure}[htb]
\begin{tabular}{ll}
\includegraphics[width=7cm]{networks-fig3.png} & \qquad
\includegraphics[width=7cm]{networks-fig4.png}
\end{tabular}
\caption{Random walk in a town and an electrical network; see Problems~\ref{2-1} and~\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} A bug walks randomly on the edges of

\noindent\textbf{(A)} a cube; \quad \textbf{(B)} an octahedron; \quad \textbf{(C)} a dodecahedron;
\quad \textbf{(D)} an icosahedron;

\noindent If the bug starts at a vertex $a$, what is the probability that it reaches food at the opposite vertex $h$ before returning to $a$; see Figure~\ref{fig5} to the left?
\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{Random walk in a cube and an electrical network; see Problems~\ref{2-3}(A) and~\ref{2-6}(A).}
\label{fig5}
\end{figure}

\begin{pr}\label{2-5} The following transformations preserve the effective conductance of a network:

\noindent\textbf{(A)} replacing two resistors connected in series
by a single resistor whose conductance is $1/\left(\frac{1}{C_1}+\frac{1}{C_2}\right)$; see Figure~\ref{fig8} to the left;

\noindent\textbf{(B)} replacing two resistors connected in parallel by a single resistor
whose conductance is $C_1+C_2$; see Figure~\ref{fig8} to the right;
%the sum of the two conductances; see Figure~\ref{fig8} to the right;

\noindent\textbf{(C)} shortening together two vertices having the same voltage.
\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{Series and parallel connections; see Problem~\ref{2-5}.}
\label{fig8}
\end{figure}

\begin{pr}\label{2-6} Find the effective conductance between \textbf{(1)} opposite; \textbf{(2)}* adjacent; vertices of

\noindent\textbf{(A)} a cube; \quad \textbf{(B)} an octahedron; \quad \textbf{(C)} a dodecahedron;
\quad \textbf{(D)} an icosahedron;

\noindent with edges of unit conductance; see Figure~\ref{fig5} to the right.
\end{pr}



\begin{pr}\label{2-4} A drunken tourist starts at her hotel and walks at
random through the streets of the idealized Paris shown in Figure~\ref{fig7} to the left.
Find the probability that she reaches the Arc de Triomphe before she
reaches the outskirts of town.
\end{pr}

\begin{pr}\label{2-10} The conductance between vertices \textbf{(A)*} $a$ and $b$; \textbf{(B)**} $a$ and $c$; of the $2$-dimensional lattice (of unit resistors) equals to $2$ and $\pi/2$, respectively; see Figure~\ref{fig7} to the right.

Notice that for the $2$-dimensional lattice we need to modify the definition of the
voltages $v(x)$ by adding one more axiom:
\begin{enumerate}
\item[3.] %\label{CI}
\emph{Condition at infinity}. $v(x)$ tends to $1/2$ as
the distance between $x$ and a fixed vertex tends to infinity.
\end{enumerate}
It is allowed to use without proof that there exists a function $v(x)$ satisfying axioms~1--3.
%Prove that in the $2$-dimensional lattice of unit resistors the conductance between two vertices \textbf{(A)*} at distance $1$ equals to $2$; \textbf{(B)**} at distance $\sqrt{2}$ equals to~$\pi/2$.
\end{pr}

\begin{figure}[htb]
\includegraphics[width=7cm]{networks-fig7.png}\qquad\qquad\qquad
\includegraphics[width=7cm]{networks-fig13.png}
\caption{Paris tourist map and a lattice network; see Problems~\ref{2-4} and~\ref{2-10}.}
\label{fig7}
\end{figure}

\begin{pr}\label{2-7} \emph{Rayleigh's Monotonicity Law}.
Cutting certain edges can only decrease the effective
conductance between two given nodes; see Figure~\ref{fig11} to the left.
Shorting certain sets of nodes together can only increase the
effective conductance of the network between two given nodes;
see Figure~\ref{fig11} in the middle.
%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)} Prove that the conductance between the center and the boundary of a square $4\times 4$ lattice of unit resistors is less than $3$; see Figure~\ref{fig11} to the right.

\noindent\textbf{(B)} To which number tends the conductance between the center and the boundary of a square $2n\times 2n$ lattice of unit resistors as $n$ tends to infinity?
\end{pr}

\begin{figure}[htb]
%\begin{tabular}{ll}
\begin{tabular}{l}
\includegraphics[width=8cm]{networks-fig12.png}
\end{tabular}
\qquad
\begin{tabular}{l}
\includegraphics[width=3.6cm]{networks-fig11.png}
\end{tabular}
\caption{Cutting, shortening, and a square $4\times 4$ lattice; see Problems~\ref{2-7} and~\ref{2-8}.}
\label{fig11}
\end{figure}

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

\begin{pr}\label{2-9} Prove the Polya theorem for the $2$-dimensional lattice.
\end{pr}

%

%\setcounter{section}{2}
%\setcounter{page}{5}

\section{Conductances of symmetric graphs}\label{symmetric}

The problems of this sections may help to solve the problems from the previous one.

A function $v(x)$ on vertices of an electrical network is \emph{harmonic},
if it satisfies axiom~\ref{KCL} from the definition of an electrical network. The vertices from the set $P\cup N$ are called \emph{boundary} vertices, the remaining vertices are called \emph{interior} ones.

\begin{pr}\label{9.99} \textbf{(A)} \emph{Superposition principle.} If functions $u(x)$ and $v(x)$ are harmonic and $a,b\in\mathbb{R}$ then the function $au(x)+bv(x)$ is harmonic.

\noindent\textbf{(B)} \emph{Maximum principle.} Prove that a harmonic function $u(x)$ defined on a finite electrical network takes its maximum and minimum values on boundary vertices.

\noindent\textbf{(C)} \emph{Uniqueness principle.} If harmonic functions $u(x)$ and $v(x)$ coincide at each boundary vertex of a finite network then $u(x)=v(x)$ for each vertex $x$ of the network.

\noindent\textbf{(D)} A man randomly walking in a finite town visits all street corners with probability~$1$.
\end{pr}

\begin{pr}\label{suschestvovanie} \textbf{(A)*} \emph{Fredholm's alternative.} Take a system of linear equations
$$\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.,$$
in which the number of equations equals to the number of unknowns.
%с квадратной матрицей коэффициентов $a_{j,k}$.
%с фиксированной матрицей коэффициентов $a_{j,k}$
%$(1\le j,k\le n)$ и столбцом $B$, составленным из чисел $b_1$,
%$b_2$, \ldots, $b_n$.
Then exactly one of the following alternatives holds:
\begin{enumerate}
\item for any $b_1$, \ldots, $b_n$ the system has a unique solution (in particular, for $b_1=\ldots=b_n=0$ there is only zero solution);
\item for some $b_1$, \ldots, $b_n$ the system has no solutions, and for some other (in particular, for $b_1=\ldots=b_n=0$) it has infinitely many solutions.
\end{enumerate}

\noindent\textbf{(B)*} \emph{Dirichlet's problem.}
Prove that for any finite electrical network there exist a function $v(x)$ satisfying axioms \ref{BC}--\ref{KCL}.
% на всем графе, совпадающая с функцией $b(x)$ во всех граничных точках.
\end{pr}

\begin{pr}\label{9.101} \textbf{(A)} \emph{Variational principle.} Let $v(x)$
be an arbitrary function on vertices of a finite electrical network satisfying
axiom~\ref{BC}, but \emph{not} necessarily axiom~\ref{KCL}.
Enumerate the vertices by $1,\dots,n$ and let $1,\dots,k$ be the interior vertices. Denote by $v_1:=v(1)$, $v_2:=v(2)$, \dots, $v_n=v(n)$. Consider $v_1,\dots,v_k$ as independent variables. Consider the heat power $Q(v_1,\dots,v_k):=\sum_{xy} C(xy)\left(v_x-v_y\right)^2$ as a function
in variables $v_1,\dots,v_k$.
Prove that the function $Q(v_1,\dots,v_k)$ takes its minimum when the function $v(x)$ is harmonic.

\noindent\textbf{(B)} Prove that for the function $Q(v_1,\dots,v_k)$
there exist a unique sequence $v_1,\dots,v_k$, for which the function takes its minimum. Apply this to obtain the second proof that for each finite electrical network there is a unique function $v(x)$ satisfying axioms~\ref{BC}--\ref{KCL}.

\noindent\textbf{(C)} \emph{Energy conservation law}. Prove that the minimal
value of the heat power $Q(v_1,\dots,v_k)$ numerically equals to the effective conductance $C$.

\noindent\textbf{(D)} \emph{Rayleigh's Monotonicity Law}.
If the conductances of the edges of a network are increased, the effective conductance can only increase.

\noindent\textbf{(E)} One removed an arbitrary set of edges from the $2$-dimensional lattice. Prove that a random walk still returns to the initial vertex with probability $1$.
\end{pr}

Let $\Gamma$ be an electrical network of unit resistors. Take a pair of adjacent edges $AB$ and $AC$ of the network. These edges are called \emph{equivalent},
if there is a permutation of vertices of the network, taking adjacent vertices to adjacent ones, and taking $A$ to $A$ and $B$ to
$C$. A vertex is a \emph{symmetry center} of the network $\Gamma$, if
all the edges containing the vertex are equivalent. The network $\Gamma$ is
\emph{regular}, if all its vertices are symmetry centers.

Examples of regular graphs: regular polyhedra of arbitrary dimensions,
regular lattices of arbitrary dimensions, regular lattices in a torus etc.
A nontrivial example: graph of a rombododecahedron. %This polyhedron is obtained from a cube by attaching a pyramid to each face so that each pair of triangles sharing an edge of the cube forms a rombus. %The surface of rombododecahedron consists of $12$ rombi.
The vertices of this polyhedron have different degrees ($3$ and $4$).

\begin{pr}\label{formula} \textbf{(A)} A regular network contains $n$ vertices. Let $A_1$ and $A_2$ be two adjacent vertices of degrees $k_1$ and $k_2$, respectively. Prove that the resistance between them is
$$\left(\frac{1}{k_1}+\frac{1}{k_2}\right)\left(1-\frac{1}{n}\right).$$

\noindent\textbf{(B)} If the network is $2$-dimensional lattice
then $1/n$ should be replaced by $0$.
\end{pr}



\begin{pr}\label{protivotok} The battery is joined with two adjacent vertices of \textbf{(A)} an icosahedron; \textbf{(B)} a dodecahedron; so that the current through the edge joining the two vertices is $I$. Find the current through the opposite edge.
\end{pr}


\begin{pr}\label{posle_3.114'}{\bf*} Prove that the sums $D_n=
\sum_{k=0}^{n}\dfrac{1}{C_n^k}$ and $F_n=\dfrac{n+1}{2^{n+1}}\sum_{k=1}^{n+1}\dfrac{2^k}{k}$ are equal.
How these sums are connected with the conductance of an $n$-dimensional cube? Apply this to prove that the order of $2$ in the number
$\sum_{k=1}^{n}\frac{2^k}{k}$ tends to infinity as
$n$ tends to infinity.
\end{pr}



\section{Walking in three dimensions}\label{random3}

\begin{figure}[htb]
\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{(Left) A binary tree of depth $3$; (middle) a modified binary tree of depth $3$;
(right) allowed intersections of edges of the trees; see Problems~\ref{3-1}, \ref{3-2}, and~\ref{3-5}.}
\label{fig079}
\end{figure}

\begin{pr}\label{3-1} Find the conductance of a binary tree of depth
\textbf{(A)} $3$; \quad \textbf{(B)} $2010$;

\noindent made of unit resistors; see Figure~\ref{fig079} to the left.
\end{pr}

\begin{pr}\label{3-2} Find the conductance of a \emph{modified} binary and a trinary trees of depth $2010$, in which each resistor at $k$-th level is replaced by $2^k$ unit resistors in series; see Figure~\ref{fig079} in the middle.\end{pr}




%\begin{figure}[hb]
%\includegraphics[width=4cm]{networks-fig15.png}
%\caption{A binary tree with $2^k$ resistors at $k$-th level; see
%Problem~\ref{3-2}.} \label{fig089}
%\end{figure}

%\begin{figure}[hb]
%\includegraphics[width=4cm]{doyle-snell091.eps}
%\caption{}
%\end{figure}

\begin{pr}\label{3-4} Which trees from \textbf{(A)} Problem~\ref{3-1}; \quad \textbf{(B)} Problem~\ref{3-2}; \quad can be cut out from the $3$-dimensional lattice?\end{pr}

\begin{pr}\label{3-5} --- And if one allows intersections of edges at equal distance from the root of the tree; see Figure~\ref{fig079} to the right?
\end{pr}

%\begin{figure}[hb]
%\includegraphics[width=5cm]{networks-fig16.png}
%\caption{Allowed intersections of edges; see Problem~\ref{3-5}}
%\label{tran}
%\end{figure}

\begin{pr}\label{3-6} Prove the Polya theorem for the $3$-dimensional lattice.\end{pr}



\section{Conductance of a ring*}

Consider a metal $2$-dimensional lattice with unit resistance of each edge.

\begin{pr} \label{ring-0} The battery is joined with nodes
$(0,0)$ and $(1,0)$. Prove that the voltages at the nodes
$(2,2)$ and $(3,2)$ are the same; see the remark in Problem~\ref{formula}(B).
\end{pr}

\begin{pr} \label{ring-1} Prove that the resistance between any node of a square $n\times n$ lattice and the boundary is less than $\sqrt{n}$.
\end{pr}

\begin{pr} \label{ring-2} The battery is joined with an interior node $A$ of the square $n\times n$ lattice and with the boundary. The voltage at the boundary is zero.
Prove that if the current through node $A$ is
$\varepsilon$, then the voltage at each other node is less than $\varepsilon\sqrt{n}$.
\end{pr}

\begin{pr} \label{ring-3} Denote by %дискретный оператор Лапласа равенством
$\Delta f(x,y)=f(x-1,y) + f(x+1,y) + f(x,y-1) +
f(x,y+1)-4f(x,y)$ and $r(x,y)=\sqrt{x^2+y^2}$.
%~--- евклидова норма вектора $(x,y)$.
If $f(x,y)=\ln r(x,y)$ for $r(x,y)\ge 2$ then $\Delta
f(x,y)=O\left(\frac1{r^4(x,y)}\right).$
\end{pr}

Hereafter for two functions $A$ and $B$ we write $A=O(B)$, if there exist a positive constant $c$ we have $|A|\le c B.$

\begin{pr} \label{ring-4} A ring with inner radius
$r_1n$, outer radius $r_2n$, and center at the origin
is cut out from the $2$-dimensional lattice.
If an edge is cut then the resistance of the part is proportional
to its length. Assign the voltage
$\ln nr_1$ to the inner boundary circle and $\ln nr_2$ --- to the outer one.
Let $U_n(x,y)$ be the voltage at node $(x,y)$.
Prove that for each $(x,y)$ inside the ring
$U_n(x,y)=\ln r(x,y) + O\left(\frac1{n^{3/2}}\right).$
\end{pr}

\begin{pr} \label{ring-5.0} Using $\arctan x=x+O(x^3)$ prove that for each
$0\le y< R$ we have
$\frac{R}{R^2+y^2}=\arctan\frac{y+1}R-\arctan\frac{y}R+O\left(\frac1{R^2}\right).$
\end{pr}

\begin{pr} \label{ring-5.1} Prove that
$\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} Assume that in Problem~\ref{ring-4}  $r_2>3r_1/2$ (so that our ring contains a square).
Prove that the current incoming through the inner boundary is
$2\pi+O\left(\frac1{\sqrt{n}}\right).$ Apply this to get the following formula for the conductance of the ring:
\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} Prove formula~\eqref{ring_eq_1}
without additional assumption $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}.
Using~\eqref{ring_eq_1} make estimations in Problems~\ref{ring-1}, \ref{ring-2} more precise and prove more precise formulas in Problems~\ref{ring-4},  \ref{ring-5}:
$$U_n(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{Challenge*}

\begin{pr} \emph{Liouville's theorem}. Suppose that a function $f(m,n)$ on $\mathbb{Z}^2$ satisfies the inequality $0\le f(m,n)\le 1$ and the equality
\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}
for each $m,n\in\mathbb{Z}$. Prove that the function $f(m,n)$ is constant.
\end{pr}

\begin{pr} \emph{Existence of a voltage}. Prove that there exists a function $f(m,n)$ on $\mathbb{Z}^2$ such that $f(0,0)=0$, $f(0,1)=1$, for each $(m,n)\ne (0,0),(0,1)$
equality (\ref{harm}) holds,
%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)$,
and $f(m,n)$ tends to $1/2$ as $r(m,n):=\sqrt{m^2+n^2}$ tends to infinity.
\end{pr}

\begin{pr} \emph{Green's function}. Let $f(m,n)$ be the resistance of the $2$-dimensional lattice between the origin and the point $(m,n)$.

\noindent\textbf{(A)} Prove that for each $(m,n)\ne (0,0)$
equality (\ref{harm}) holds.
%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)} Prove that $f(m,n)=g(r(m,n))+O(1)$ for some function $g(x)$.

\noindent\textbf{(C)} Prove that the resistance between the center and the boundary of a disc of radius $r$ cut from the $2$-dimensional lattice equals to
$\frac{1}{2\pi}\ln r+O(1)$.

\noindent\textbf{(D)} Prove that $f(m,n)=\frac{1}{2\pi}\ln r(m,n)+O(1)$.
\end{pr}

\begin{pr} Find with $2$ digit precision the probability that a random walk on a $3$-dimensional lattice eventually returns to the initial point.
\end{pr}

\begin{pr} Robot walks on the vertices of the $3$-dimensional lattice, each time moving from a vertex to one of the neighbors. One of the vertices contains a treasure, which is found when the robot reaches the vertex.
Is there a program for a robot using a finite memory and a random number generator such that the robot finds the treasure with probability~$1$?
\end{pr}


\newpage
\large

\section{Hints to the solutions}

\noindent\textbf{\ref{1-1}} \textbf{(A)} To check the correctness of the program we use the following criterion: the difference between the percentage and the probability should be approximately inverse proportional
to the square root of the number of times the program is run.

%\emph{An example of the program by the students Goncharenko, Khayrullin and Busygin (Delphi)}:






\noindent\textbf{(B)} See the answer in the table. The proof is straightforward.

\begin{table}[h]
\caption{The probabilities $P_T(x)$ and $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{Answer}: $P(x)=x/5$; see the last row of the above table.

\noindent\emph{Proof}. Consider a random walk on the integers $0, 1, 2, \dots , n$.
Let $P(x)$ be the probability, starting at $x$, of reaching $N$ before $0$.
We regard $P(x)$ as a function defined on the points $x = 0, 1, 2, \dots , n$.
The function $P(x)$ has the following properties:
\begin{enumerate}
\item $P(0) = 0$ and $P(n) = 1$.
\item $P(x) = \frac12 P(x - 1) + \frac12 P(x + 1)$ for each $x = 1, 2, . . . , n-1$.
\end{enumerate}
Property 1 follows from our convention that $0$ and $n$ are
traps; if the walker reaches one of these positions, he stops there; in
the game interpretation, the game ends when one player has all of the
pennies. Property 2 states that, for an interior point, the probability
$P(x)$ of reaching home from $x$ is the average of the probabilities $P(x-1)$
and $P(x + 1)$ of reaching home from the points that the walker may
go to from $x$. We can derive property 2 from the following basic fact about
probability:

\smallskip
\noindent\textbf{Basic Fact.} \emph{Let $E$ be any event, and $F$ and $G$ be events such that one and only one of the events $F$ or $G$ will occur. Then}
$$
P(E) = P(F) \cdot P(E \text{ given } F) + P(G) \cdot P(E \text{ given }G).
$$
%\smallskip

In this case, let $E$ be the event ``the walker ends at the bar'', $F$
the event ``the first step is to the left'', and $G$ the event ``the first
step is to the right''. Then, if the walker starts at $x$, $P(E) = P(x)$,
$P(F ) = P(G) = 1/2$ , $P(E \text{ given }F ) = P(x-1)$, $P(E \text{ given }G) = P(x+1)$,
and property 2 follows.

Properties 1--2 imply together that $P(x)$ is the arithmetic progression $P(x)=x/n$.



\smallskip
\noindent\textbf{\ref{1-2}} \emph{Answer}: $P(x)=x/5$; in fact this problem is equivalent to~\ref{1-1}(C).



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

\noindent\emph{Hint}: Argue as in the solution of Problem~\ref{1-1}(C). Show that
properties 1--2 in the solution should be replaced by
\begin{enumerate}
\item $P(0) = 0$ and $P(n) = 1$.
\item $P(x) = q P(x - 1) + p P(x + 1)$ for each $x = 1, 2, . . . , n-1$.
\end{enumerate}
Show that you can choose $A$ and $B$ so that the function $f (x) = A(q/p)^x + B$ satisfies these modified properties.

\smallskip
\noindent\textbf{\ref{1-4}} \emph{Answer}: $\approx 99.995\%$. The exact answer is $1-\frac{(0.55/0.45)^{20} - 1}{(0.55/0.45)^{70} - 1}$; the problem is equivalent to% a particular case of
~\ref{1-3}.



\smallskip
\noindent\textbf{\ref{1-5}} \emph{Answer}: $v(x)=x/5$. \emph{Hint}. Axioms \ref{BC}--\ref{KCL} imply that $v(x)$ is linear %an arithmetic progression
for this network.



\smallskip
\noindent\textbf{\ref{1-6}} \textbf{(A)} Let $M$ be the largest value of $v(x)$. Then if $v(x) = M$ for
$x\not\in P\cup N$, the same must be true for $v(x-1)$ and $v(x + 1)$ since $v(x)$ is
the average of these two values. If $x - 1$ is still an interior point, the
same argument implies that $f (x - 2) = M$; continuing in this way, we
eventually conclude that $f (0) = M$. That same argument works for
the minimum value $m$.

\noindent\textbf{(B)} Let $h(x) = v (x) - u(x)$. Then if $x$ is any interior point,
$$
\frac{h(x - 1) + h(x + 1)}{2}=\frac{v (x - 1) + v (x + 1)}{2} - \frac{u(x - 1) + u(x + 1)}{2}
$$
and $h(x)$ also satisfies axiom~\ref{KCL}. But $h(x) = 0$ for $x$ in $P\cup N$, and hence, by the Maximum Principle, the maximum and minimum values of $h$ are $0$. Thus $h(x) = 0$ for all $x$, and $v (x) = u(x)$ for all $x$.

\noindent\textbf{(C)} \emph{Answer}: $v(x)=x/n$, $C=1/n$; $C\to 0$ and $v(x)\to 0$ for each fixed $x$ as $n\to \infty$.

\noindent\emph{Hint}: It is easy to check that the function $f(x):=x/n$ satisfies axioms \ref{BC}--\ref{KCL}. By uniqueness principle it follows that $v(x)=x/n$.




\smallskip
\noindent\textbf{\ref{1-9}} \textbf{Theorem.} \emph{A random walk, starting at the origin of the $1$-dimensional lattice, eventually returns to the origin with probability $1$.}

\noindent\emph{Proof}. Let $P$ be the probability that a random walk, starting at the origin, eventually returns to the origin. Let $P_n$ be the probability that a random walk, starting at the origin, returns to the origin before reaching the points $n$ and $-n$. Assume that all these probabilities exist. Clearly, then $P_n\le P\le 1$ for each $n$.

Let us prove that $P_n=1-1/n$. After first ``move'' our walker comes to either point $1$ or $-1$ with probability $1/2$. Given that he comes to $1$ by Problem~\ref{1-1}(C) the probability that he returns to the origin before reaching the point $n$ equals to $1-1/n$. Analogously, given that he comes to $-1$ the probability that he returns to the origin before reaching the point $-n$ equals to $1-1/n$. Applying Basic Fact from the solution of Problem~\ref{1-1}(C) one gets
$P_n=\frac12\left(1-\frac1n\right)+\frac12\left(1-\frac1n\right)=1-\frac1n$.
(Alternatively, one can observe that $P_n=1-C$, where $C=1/n$ is the conductance of the network from Problem~\ref{1-6}.)

So $1-1/n\le P\le 1$ for each $n$, hence $P$ must be $1$.
$\square$



\smallskip
\noindent\textbf{\ref{2-1}} \emph{Answer}: see Figure~\ref{fig51} to the left.

\begin{figure}[htb]
\begin{tabular}{ll}
\includegraphics[width=3cm]{networks-fig51.png} & \qquad
\includegraphics[width=3cm]{networks-fig52.png}
\end{tabular}
\caption{The probabilities $P(x)$ or, equivalently, the voltages $v(x)$; see Problems~\ref{2-1} and~\ref{2-1a}.}
\label{fig51}
\end{figure}

\noindent\emph{Hint}. The town is shown again in Figure~\ref{fig51} to the right.
The probabilities $P(x)$ are denoted by $a$, $b$, $c$, $d$, and $e$. Similarly to $1$-dimensional case, the function $P(x)$ satisfies axioms~\ref{BC}--\ref{KCL} from the definition of an electrical network. Thus we get a system os linear equations:
\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*}
Solving the system, we get the answer.

\smallskip
\noindent

\emph{Remark}. Finding the exact solution to a ``Dirichlet problem'' in two dimensions is
not always a simple matter, so we will
consider two methods for generating approximate solutions.

First let us present a method using random walks. This method
is known as a \emph{Monte Carlo method}, since random walks are random,
and gambling involves randomness, and there is a famous gambling
casino in Monte Carlo. We start many random walks at $x$ and count the percentage of walks
reaching the points marked by $E$. By the law of
averages (the law of large numbers in probability theory), the estimate
that we obtain this way will approach the true expected probability $P(x)$.
This method is a colorful way to solve the problem, but quite inefficient.

Now let us present the more efficient \emph{method of relaxations}.
Recall that we are looking for a function that has specified boundary values, for which the value at any
interior point is the average of the values at its neighbors. Begin with
any function having the specified boundary values, pick an interior
point, and see what is happening there. In general, the value of the
function at the point we are looking at will not be equal to the average
of the values at its neighbors. So adjust the value of the function to be
equal to the average of the values at its neighbors. Now run through
the rest of the interior points, repeating this process. When you have
adjusted the values at all of the interior points, the function that
results will not satisfy axiom~\ref{KCL}, because most of the time after adjusting the
value at a point to be the average value at its neighbors, we afterwards
came along and adjusted the values at one or more of those neighbors,
thus destroying the harmony. However, the function that results after
running through all the interior points is more nearly
to satisfy axiom~\ref{KCL} than the function we started with; if we keep repeating this averaging process, running through all of the interior points again and
again, the function will approximate more and more closely the solution
to our problem.



\smallskip
\noindent\textbf{\ref{2-1a}} \emph{Answer}: see Figure~\ref{fig51} to the left; this problem is equivalent to~\ref{2-1}.



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


\noindent\emph{Hint}.
Reduce to Problem~\ref{2-6} using the following simple result:

\smallskip
\noindent\textbf{Physical interpretation of probability.} \emph{The probability that a random walk in a graph $G$, starting at a vertex $a$, reaches a vertex $h$ before returning to the initial point $a$, equals to}
$$
P=C/\mathop{deg}a,
$$
where $C$ is the conductance of the graph $G$ (of unit resistors) between $a$ and $h$, and $\mathop{deg}a$ is the number of edges containing the vertex $a$.



\smallskip
\noindent\textbf{\ref{2-5}} \textbf{(C)} \emph{Hint}. The function $v(x)$ is well-defined on the vertices of the network obtained by the shortening. Check that $v(x)$ still satisfies axioms \ref{BC}--\ref{KCL}.




\smallskip
\noindent\textbf{\ref{2-6}} \emph{Answer}: \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$.

For a short solution refer to section~\ref{symmetric}.

\noindent\textbf{(2A)} \emph{Hint}. We put a unit battery between $a$ and $b$; see Figure~\ref{fig5} to the right. Then, by symmetry, the voltages at $c$ and $d$ will be the same as will those at
$e$ and $f$. Thus our circuit is equivalent to the circuit shown in Figure~\ref{fig54} to the left.

Using the laws for the effective resistance of resistors in series and
parallel, this network can be successively reduced to a single resistor
of resistance $7/12$ ohms, as shown in Figure~\ref{fig54} to the right. Thus the effective resistance is $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{Simplification of a network; see the solution of Problem~\ref{2-6}.}
\label{fig54}
\end{figure}



\smallskip
\noindent\textbf{\ref{2-4}} \emph{Answer}: $1/7$. Argue analogously to the solution of Problem~\ref{2-3}.


\smallskip
\noindent\textbf{\ref{2-10}} \textbf{(A)}. For a short solution refer to section~\ref{symmetric}.

\noindent\textbf{(B)} The authors do not know elementary solution of the problem. A nice solution based on discrete Fourier transformation can be found in the book \cite{S}.

\smallskip
\noindent\textbf{\ref{2-7}} Refer to section~\ref{symmetric}.

\smallskip
\noindent\textbf{\ref{2-8}} \textbf{(B)} \emph{Answer}: $C\to 0$ as $n\to \infty$.

\noindent \emph{Hint}. We apply Monotonicity Law as follows: short together
nodes on squares about the origin, as shown in Figure~\ref{fig55} in the top. The network
we obtain is equivalent to the network shown in Figure~\ref{fig55} in the middle.
Now as $n$ $1$-ohm resistors in parallel are equivalent to a single resistor
of resistance $1/n$ ohms, the modified network is equivalent to the network
shown in Figure~\ref{fig55} in the bottom. The conductance of this network is
$$
\frac{1}{\sum_{k=1}^n \frac{1}{8k-4}}.
$$
This number tends to zero as $n$ tends to infinity. As the conductance of the old network can only be smaller, we conclude that it too must tend to zero.

\begin{figure}[htbp]
\begin{tabular}{l}
\includegraphics[width=3.5cm]{networks-fig55.png}\\[15pt]
\includegraphics[width=11cm]{networks-fig56.png}\\[15pt]
\includegraphics[width=11cm]{networks-fig57.png}
\end{tabular}
\caption{Shortening a square network and an equivalent network; see the solution of Problem~\ref{2-8}.}
\label{fig55}
\end{figure}




\smallskip
\noindent\textbf{\ref{2-9}} \emph{Hint}. Let $P$ be the probability that a random walk on the $2$-dimensional lattice, starting at the origin, eventually returns to the origin. Let $P_n$ be the probability that a random walk, starting at the origin, returns to the origin before reaching the boundary points of the $2n\times 2n$
square centered at the origin. Assume that all these probabilities exist. Clearly, then $P_n\le P\le 1$ for each $n$. By the physical interpretation of the probability one gets $P_n=1-C/4$, where $C$ is the effective conductance between the center and the boundary of the $2n\times 2n$ square. By Problem~\ref{2-8}(B) $C$ tends to zero as $n$ tends to infinity. Thus $P_n\to 1$ as $n\to\infty$, hence $P$ must be $1$.
$\square$


\smallskip
\noindent\textbf{\ref{9.99}--\ref{9.101}} E. g., see \cite{PS}.


\smallskip
\noindent\textbf{\ref{formula}} \textbf{(A)}
First consider the following network: a current flowing through the vertex $A_1$ equals to $\frac{n-1}{n}$ and to $-\frac{1}{n}$ for all other vertices. Since graph network is regular the current flowing through the edge $A_1A_2$ equals to $\frac{1}{k_1}\left(1-\frac{1}{n}\right)$. Now consider a similar network: a current flowing through the vertex $A_2$ equals to $-\frac{n-1}{n}$ and to $\frac{1}{n}$ for all other vertices. Sum two networks and obtain by superposition principle the network with unit current source connected to $A_1$ and $A_2$. The current flowing through the edge $A_1A_2$ in obtained network equals to $\left(\frac{1}{k_1}+\frac{1}{k_2}\right)\left(1-\frac{1}{n}\right)$. Therefore, the resistance between $A_1$ and $A_2$ equals to $\left(\frac{1}{k_1}+\frac{1}{k_2}\right)\left(1-\frac{1}{n}\right)$.

If the graph is infinite substitute $\frac1{n}$ by zero. An explanation of this answer bases on limiting process.

The formula of the resistance between two adjacent vertices of the regular graph is due to A.B.Hodulev. The definition of a regular graph and this formula are taken from \cite{G}.

\textbf{(B)} First we introduce some physical explanations. Apply a bus of zero resistance to the boundary of rectangle $[-N,N+1]\times[-N,N].$ Since the potential tends to zero at infinity, applying a bus changes the resistance a little bit. (Next we give our explanations with error which tends to zero as $N$ grows to infinity). If a current source of unit current is connected with point $(0,0)$ and the bus then the current flowing through the edges outgoing from $(0,0)$ equals to $\frac14.$ If current source of unit current is connected to the bus and the point $(1,0)$ then the current flowing through the edges ingoing to $(1,0)$ equals to $\frac14.$ Therefore if both current sources are connected then the current flowing through the edge $(0,0)-(1,0)$ equals to $\frac12$. So  a potential difference between these points equals to $\frac12$ also. But the current flowing through source connecting these points equals to $1$. Therefore the resistance between these points equals to $\frac12$.

Now we make our arguments more strict. Again suppose that a current source is connected to the point $(0,0)$ and a bus of zero resistance applied to the boundary of rectangle $[-N,N+1]\times[-N,N]$. According to Problem~\ref{ring-1} the resistance of such graph is at most $N^{1/2}$. Hence if the bus is joined with the ground, the potential at the point $(0,0)$ is at most $N^{\frac12}$:
\begin{equation}
\label{Resist.Pot} V=IR=R\le N^{1/2}.
\end{equation}

We will show that the potential at the points which are close to the bus differs from zero a little. Denote the maximal potential at the points of the boundary of the rectangle $[-j,j+1]\times[-j,j]$ by $u_j$. From harmonicity of potential distribution it follows that $u_{j-1}\ge 2u_j-u_{j+1}$ ($1\le j\le N-1$). So if $u_{N-1}=\varepsilon$ (by assumption $u_n=0$) then for all $j$ such that $0\le j\le N$ an inequality $u_j\ge(N-j)\varepsilon$ holds. In particular, $u_0=V\ge N\varepsilon$. Using inequality~\eqref{Resist.Pot}, we obtain that $\varepsilon\le N^{-1/2}$.

This time apply a bus to the boundary of the square $[-N,N]\times[-N,N]$. The obtained potential distribution is symmetric. Due to the maximum principle it differs from the initial one at most by $N^{-1/2}$. Therefore, before the moving of the right side of the bus four currents outcoming from the point $(0,0)$ differed from $\frac14$ at most by $N^{-\frac12}.$ Similarly, if the source is connected to a bus and the point $(1,0)$ then ingoing currents to the point $(1,0)$ differ from $\frac14$ at most by $N^{-\frac12}$.

Unite these two situations. So by superposition principle we obtain that in the network obtained from the rectangle by short-circuiting its boundary and connecting the unit current source to the points $(0,0)$ and $(1,0)$ the current flowing through the edge $(0,0)-(1,0)$ equals to $1/2+O(N^{-1/2})$. Hence the potential difference and, therefore, resistance equal to $1/2+O(N^{-1/2})$.

Consider the initial network. To finish the proof apply the axiom~3. Assume that potentials at the points $(0,0)$ and $(1,0)$ equal to $\frac14$ and $-\frac14$ respectively. Denote the current flowing through the source by $I$. Choose the rectangle $[-N,N+1]\times[-N,N]$ such that a potential on its boundary is smaller than some $\varepsilon>0$. By maximum principle if one substitute all potentials at the boundary of the rectangle by zero (fixing the current through the battery) then potentials at all points will change at most by $\varepsilon$. In particular the potential difference between $(0,0)$ and $(1,0)$ will equal to $1/2+O(\varepsilon)$. But resistance between them equals to $1/2+O(N^{-1/2})$. Therefore $I=1+O(\varepsilon)+O(N^{-1/2})$. As $\varepsilon$ tends to zero, $N$ grows to infinity and we obtain that $I=1$. Therefore the resistance of the lattice between adjacent vertices equals to $\frac12$.

\smallskip
\noindent\textbf{\ref{protivotok}} Let $B_1$ and $B_2$ be the vertices of the graph which are opposite to $A_1$ and $A_2$ respectively. By  Problem~\ref{formula}(A) the current flowing through the edge $A_1A_2$ equals to $I=\left(\frac{1}{k_1}+\frac{1}{k_2}\right)\left(1-\frac{1}{n}\right)$ if the source of given network is of unit current. Denote the current flowing through the edge $B_2B_1$ by $x$. Additionally connect the unit current source to vertices $B_1$ and $B_2$ such that the current flows in the vertex $B_2$.
Then the current flowing through edges $A_1A_2$ and $B_2B_1$ equals to $I+x$. But if one connect two unit current sources to $A_1,B_1$ and $B_2,A_2$ (current flows in $A_1$ and in $B_2$) then the current distribution will be the same. By Problem~\ref{formula} the first source gives a current $\frac{1}{k_1}$ through $A_1A_2$ and the second --- $\frac{1}{k_2}$. Therefore
\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*}
So for icosahedron the answer is $\frac{I}{11}$, for a dodecahedron~--- $\frac{I}{19}$, for a rhombdodecahedron~--- $\frac{I}{13}$, for a cube~--- $\frac{I}{7}$.

\smallskip
\noindent\textbf{\ref{posle_3.114'}} \emph{Hint}. Sums $D_n$ and $F_n$ fit the same recurrence relation. For instance, $D_n=1+\dfrac{n+1}{2n}D_{n-1}$. Also $D_0=F_0=1$. Therefore $D_n=F_n$. So if $n\ge1$ then $$\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}.$$
To finish the proof bound the power of the number $2$ in the factorization of the common denominator of the fractions from the obtained sum using Legendre formula for the power of the prime number in the factorization of a factorial.


The resistance $R_n$ between two opposite vertices of an $n$-dimensional cube
(with unit resistance on each its edge) is related with the sums $D_n$ and $F_n$
by the relations
$$
  D_n=F_n=(n+1)R_{n+1}
$$
(see details in the paper \cite{NS}).



\smallskip
\noindent\textbf{\ref{3-1}} \emph{Hint}.
Prove by induction that the resistance of a binary tree of depth $n$
constructed of unit resistors equals to $1-\frac{1}{2^n}$.

\smallskip
\noindent\textbf{\ref{3-2}} \emph{Hint}.
Voltages at points situated at the same distance from the tree root
are equal in virtue of symmetry. Shortening such points in a binary
tree we receive a series from Figure~\ref{fig31zrus}. It's resistance
equals to $\frac{1}{2}\cdot n=\frac{n}{2}$.
Similarly for a trinary tree we receive
$R=\frac{1}{3}+\frac{2}{9}+\dots+\frac{2^{n-1}}{3^n}$.
Hence $R=1-\frac{2^n}{3^n}$.

\begin{figure}
\includegraphics[width=10cm]{networks-fig31zrus.png}
\caption{Calculation of the resistance of a tree; see solution of
Problem~\ref{3-2}.} \label{fig31zrus}
\end{figure}

\smallskip
\noindent\textbf{\ref{3-4}} \emph{Hint}.
It is not difficult to cut a tree of depth $3$. Let us show that
it is impossible to cut a tree of depth $2010$. Suppose we cut it,
thus all it's vertices are situated at the distance not more than
$2010$ from the root; hence the tree is contained in a cube with
the side $2\cdot2010+1$. So it has no more than $4021^3\leq2^{36}$
vertices. On the other hand the number of it's vertices equals to
$2^{2011}-1$. The contradiction completes the proof. The problem
of cutting of a modified tree couldn't be solved easily.


\smallskip
\noindent\textbf{\ref{3-5}} \emph{Hint}.
A binary tree could not be cut; the arguments are similar
to the solution~\ref{3-4}, taking in account that more than two
vertices could not be glued. A modified binary tree could be cut
from the plane(see Figure~\ref{fig58}), and similarly a trinary tree
could be cut from the space (see Figure~\ref{fig59}). Proofs could
be done using induction by the tree depth.

\begin{figure}
\includegraphics[width=10cm]{networks-fig58.png}
\caption{Cutting of a binary tree with intersections from the plain;
see solution~\ref{3-5}.} \label{fig58}
\end{figure}

\begin{figure}
\includegraphics[width=10cm]{networks-fig59.png}
\caption{Cutting of a trinary tree with intersections from the space;
see solution~\ref{3-5}.} \label{fig59}
\end{figure}

\smallskip
\noindent\textbf{\ref{3-6}} \emph{Hint}. For any $n=2^i-1$
let us consider the set of vertices
$(x,y,z)$, where $|x|+|y|+|z| \leq n$.
Let $R_i$ be the resistance between the origin and the border of the
figure. As we already know from Problem~\ref{3-5}, it is possible
to cut from such a part of the lattice a modified trinary tree of
depth $i$ with edges intersections at the same distance from the root.
As we know from Problem~\ref{3-2}, the resistances of modified
trinary trees not more than $1$. So the resistances of modified
trinary trees also not more than $1$. From the monotonicity law we
receive that $R_i\leq 1$. Hence switching on a battery of $1$ Volt
%(откуда появилась размерная величина???)
the current will be not more than $1$.
Hence the voltages at the vertices joint to the origin will be not
more than $1-\frac{1}{6}=\frac{5}{6}$.
They equal to the probability or returning to the origin before reaching
of the border.
Taking the limit we obtain the statement we need.

\smallskip
\noindent\textbf{\ref{ring-0}}
Consider the points $A(2,3)$, $B(3,3)$, $C(1,2)$,
$D(2,2)$, $E(3,2)$, $F(4,2)$, $G(2,1)$, $H(3,1)$. First let
the power supply deliver a unit current to the origin,
the second clip being connected to the
perimeter of the square $[-R,R]^2$ (we set the zero resistance to this perimeter).
From the symmetry reasons we get the equalities $i(CD)=i(GD)=i(DA)=i(DE)=I$
for some number~$I$.

Now, consider the second situation, when the same current is delivered to the
perimeter of the same square (with zero resistance as well), the second clip being connected to the point $(1,0)$. Then we get $i(DE)\approx
i(HE)\approx i(EB)\approx i(EF)\approx -I$, where the equalties are accurate within some small~$\varepsilon$ which tends to zero as $R\to\infty$ (similarly to Problem~\ref{formula}, it follows from axiom~3). Combining both situations, we get the following. Suppose that the power supply is connected to $(0,0)$ and $(1,0)$, while the perimeter of square~$[-R,R]^2$
is replaced by a zero resistance loop; then the current flowing through edge~$DE$ is less than~$\varepsilon$. Taking the limit as $R\to\infty$ (and applying axiom~3 again), we obtain the desired statement.

Note that we used without proof a difficult fact on the existence and uniqueness.

\smallskip
\noindent\textbf{\ref{ring-1}}
Consider an arbitrary tree connecting the given point with the perimeter of the square.

\smallskip
\noindent\textbf{\ref{ring-2}}
Apply the maximum principle.

\smallskip
\noindent\textbf{\ref{ring-3}}
Write the Laplace operator in the form
$$\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).$$
Then for the function $f(x,y)=\ln r(x,y)$ we get
\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*}
Similarly,
\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*}
Hence
\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}}
For a point $(x,y)$ nearby the boundary of the ring, it makes sense to
change the definition of the Laplace operator, in order to agree with the Kirchhoff rules.
For instance, if the points $(x-a,y)$ and $(x,y-b)$ for some $a$, $b\in[0,1)$ lie on the boundary, then we set
$$\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).$$
Thus, considering the function the function $f(x,y)=\ln r(x,y)$ in such a point we have
$$\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).$$
Analogously,
$$\frac{f(x,y-b)-f(x,y)}b + f(x,y+1) -f(x,y)=O\left(\frac{1}{r^2}\right).$$
So, we get $\Delta f(x,y)=O\left(r^{-2}\right)$; moreover, this estimate remains valid
if only one of the points neighboring to~$(x,y)$ lies outside the ring.

Consider now the function $f(x,y)=U_n(x,y)-\ln r(x,y)$.
It vanishes on the boundary of the ring, while in each interior point it satisfies the
equation  $\Delta f(x,y)=\varphi(x,y)$, where
$\varphi(x,y)=O(n^{-2})$ at the points nearby the boundary, and
$\varphi(x,y)=O(n^{-4})$ at all other points of the ring.

Interpret the values  $\varphi(x,y)$ as the currents delivered to the
corresponding points of the ring. The potentials at the points
nearby the boundary can be estimated by the
maximum principle (cf. Problem~\ref{9.99}).
Actually, the potential on the boundary is zero, the current between
our point~$(x,y)$ and the closest point of the boundary is $O(n^{-2})$,
therefore the potential at $(x,y)$  is $O(n^{-2})$ as well.
By the maximum principle, all such currents
induce the potentials not exceeding $O(n^{-2})$ in all points of our region.

Now, we are left to estimate the potentials generated by the currents at
other points of the ring  (that are those far from the boundary).
The number of those points is  $O(n^2)$, and the current in each of them
induces the potentials not exceeding $O(n^{-7/2})$ (according to Problem~\ref{ring-2}).
Thus, the total potential generated by our points is $O(n^{-3/2})$. Hence, we finally get $f(x,y)=O(n^{-3/2})$.

\smallskip
\noindent\textbf{\ref{ring-5.0}} We involve the relation $$\arctan x-\arctan y=\arctan
\frac{x-y}{1+xy},$$ which holds when $|xy|<1$. So, we get
\begin{gather*}
\arctan\frac{y+1}R-\arctan\frac{y}R=\arctan\frac{1/R}{1+y(y+1)/R^2}=\\=
\arctan\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}} Sum up the formula from problem~\ref{ring-5.0}.

\smallskip
\noindent\textbf{\ref{ring-5}} To find the resistance of the ring, we find the current flowing through it
when the inner and the outer loops of the ring are under the voltages $\ln nr_1$ and $\ln nr_2$
respectively. Let us find the current through the perimeter of a square $[-R-1/2,R+1/2]^2$, where $R=[r_1n]+1$. We will calcuat it approximately, changing the potentials at all the points by the corresponding values of the function $\ln r(x,y)$. Thus, we sum up $O(n)$ of currents, each with the error of $O(n^{-3/2})$. Hence the total error is~$O(n^{-1/2})$.

By the symmetry of the square, the current flowing trough its perimeter can be found as
$$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).$$
Since $$\ln r(R+1,y)-\ln
r(R,y)=\frac{R}{R^2+y^2}+O\left(\frac1{R^{2}}\right),$$
we can apply the formula from problem~\ref{ring-5.1} obtaining the desired relation $I=2\pi+O(n^{-1/2}).$

\smallskip
\noindent\textbf{\ref{ring-6}}
Similarly to the previous problem, to calculate the resistance
we will find the current flowing through some closed broken line.
Again, for the approximate calculation we replace the potentials
by the values of the function $\ln r(x,y)$. Now let us replace
our broken line by the square circumscribed around it;
there will be $O(n^2)$ new current sources inside this contour,
in each of them there appears an (incoming or outcoming) current of order $O(n^{-4})$.
Therefore, the desired value of the total current differs from
the current $I=2\pi+O(n^{-1/2})$ through the perimeter of the square
(which was found above) by at most $O(n^{-2})$.

\smallskip
\noindent\textbf{\ref{ring-7}} Let us prove that in Problem~5.2 %\ref{ring-1} 
the resistance between any vertex of the square and its boundary equals to $O(\ln n)$. This allows us to multiply residual terms by $\frac{\ln n}{\sqrt n}$ in solutions of all next problems.

Instead of the square consider a triangle cut from the square lattice by lines $x=0$, $y=0$, $x+y=n$, and bound its resistance between its origin and its hypotenuse. Assume that a potential at integer points of the segment $x+y=k$, $x,y\ge0$ equals to $V_k=\sum_{j=2}^{k+1}\frac1j$ ($0\le k\le n$). In particular the potential at the origin equals zero. Also assume that the current flowing into each vertex at the line $x+y=k$ equals to $\frac1{k}$, i.e. through each level flows unit current. Increase resistances inside the triangle to fit Ohm law. (Resistances connecting points of the form $(0,k),(k,0)$ with points $(0,k+1)$, $(k+1,0)$ stay unit.) To fit Kirchhoff law currents flowing from the point $(j, k-j)$ should equal to $\frac{k-j}{k(k+1)}$ and $\frac{j+1}{k(k+1)}$ and flow to the points $(j,k-j+1)$ and $(j+1,k-j)$ respectively. Since potential difference equals to $\frac1{n+1}$ then unit resistances must be substituted by $\frac{k}{k-j}$ and $\frac{k}{j+1}$ respectively. The resistance of the obtained network equals to $V_n\le \ln n$. So the resistance of the initial network is smaller than $\ln n$ also.




\section{Acknowledgements}

Most of the problems from sections 1, 2 and 4 are taken from the paper of P. Doyle and J. Snell \cite{DS}. The authors are grateful to I. Bogdanov, V. Bugaenko and M. Prasolov for help in translation.


\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} G. A. Galperin, My friend Andrey Khodulev, Mat. Prosv. 3rd series, \textbf{4} (2000), 8--32,
%Г.А.\,Гальперин ``Мой друг Андрей Ходулёв'' (Математическое просвещение, сер. 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.

\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}
