# The problem of the most visited point.

Represent the set $R_{n\times n}=\{1,2,\ldots, n\}\times\{1,2,\ldots, n\}$ as a rectangle of $n$ by $n$ points as in the figures below for example. How to calculate the number of circuits that visit a chosen point in this rectangle? What is the most visited point on this rectangle? Making the question more precise we fix the settings below.

• A circuitc $c$ in rectangle $R_{n\times n}$ is defined as a sequence of distinct points $x_{i_1j_1}, x_{i_2j_2},x_{i_2j_2},\ldots, x_{i_{m-1}j_{m-1}}$ and a point $x_{i_{m}j_{m}}=x_{i_{1}j_{1}}$ in $R_{n\times n}$ such that $|i_{k}-i_{k+1}|+|j_{k}-j_{k+1}|=1$ for $k=1,\ldots, m-1$.

• A circuit $c=\{x_{i_1j_1}, x_{i_2j_2},x_{i_2j_2},\ldots, x_{i_{m-1}j_{m-1}},x_{i_{m}j_{m}}\}$ visit a point $x_{ij}$ if $x_{ij}\in c$.

• Let $N_n(x_{ij})$ the total circuits in $R_{n\times n}$ who visit the point $x_{ij}$ .

Question. How to calculate the value of $N_n(x_{ij})$? If we draw a circuit randomly which point $x_{ij}$ has the highest probability to be visited?

Calculations case $n = 1,2,3$ are trivial. I'm trying to calculate the number $N_n(x_{ij})$ by a recursive procedure which reduces the calculation for the case $n$ to $n-1$. But I think the use of this recursion depends on some well-crafted trick that escaped my attempts.

• The following result might be helpful. Theorem: Let $G:=(V,E)$ be a graph and consider its adjacency matrix $A_G$. For all $k\in \mathbb N$, the number of paths of lenght $k$ from node $v_i$ to $v_j$is the the entry $i,j$ of the matrix $A^k_G$, for any $i,j\in \{m\in \mathbb N\colon m\leq |V|\}$. See the proof here. A couple of keyterms are adjacency matrix and number of paths. Dec 24, 2013 at 13:55
• @GitGud This is the classic solution to the problem of the most visited point. In this case I would have to calculate the number of two distinct paths connecting two points. It seems to be a promising approach. But I have not had progress with this approach. Dec 24, 2013 at 13:57
• I have a suggestion but it might be also hard to calculate. Instead of counting paths on this graph, count the number of coloring the squares in a continuous way. It is obvious that there is an upper bound of $2^{(n-1)(n-1)}$.
– mnz
Mar 3, 2014 at 15:20
• I think the way to approach it might be to relate the probability of each node's appearance in a circuit with its neighbors. Or maybe look at the probability of each edge appearing in a circuit instead. Jul 23, 2014 at 2:46
• see also another related question here. May 2, 2015 at 15:04

I think it' strictly linked to the self-avoiding path problem (which is slightly different as the circuit doesn't necessary ends where it started); there is also a detailed study , and a partial solution to what you called $N_n(x_{\left\lfloor\frac{n-1}{2}\right\rfloor\left\lfloor\frac{n-1}{2}\right\rfloor})$, all circuits which visit the origin. Anyway until now, any solution has been found. It can be an idea to consider a circuit that starts from $x_{ab}$ and arrives to $x_{cd}$, and then consider the reverse paths (from $x_{cd}$ to $x_{ab}$), remembering not to count the reverse paths which intersect the first one, as to create an Hamilton path.